route.c

一个基于linux的TCP/IP协议栈的实现

	u32 tos = RT_FL_TOS(oldflp);
	unsigned char hop;
	unsigned hash;
	int err = -EINVAL;
	struct rtable *rth = NULL;

	if( res->fi && res->fi->fib_nhs > 1) {
		unsigned char hopcount = res->fi->fib_nhs;
		for( hop = 0; hop < hopcount; hop++ ){
			struct net_device *dev2nexthop;
			res->nh_sel = hop;
			dev2nexthop = FIB_RES_DEV(*res);
			dev_hold(dev2nexthop);
			if( hop )
				ip_rt_put(*rp);
			err = __mymkroute_output( &rth, res, fl, oldflp, dev2nexthop, flags );
			if (err != 0)
				goto cleanup;

			hash = rt_hash_code(oldflp->fl4_dst, oldflp->fl4_src ^ (oldflp->oif << 5), tos);
			err = rt_intern_hash(hash, rth, rp);

			multipath_set_nhinfo(rth, FIB_RES_NETWORK(*res), FIB_RES_NETMASK(*res),
							res->prefixlen, &FIB_RES_NH(*res));
cleanup:
			dev_put(dev2nexthop);
			if (err != 0)
				return err;
		}
		return err;
	}else{
		return myip_mkroute_output_def( rp, res, fl, oldflp, dev_out, flags );
	}
#else
*/
	PR_DEBUG( "dev: %s, count: %d\n", myloopback_dev.name, atomic_read(&myloopback_dev.refcnt));
	return myip_mkroute_output_def( rp, res, fl, oldflp, dev_out, flags );
//#endif
}

static int myip_route_output_slow(struct rtable **rp, const struct flowi *oldflp)
{

	u32 tos	= RT_FL_TOS(oldflp);
	struct flowi fl = { .nl_u = { .ip4_u =
			{ .daddr = oldflp->fl4_dst,
					.saddr = oldflp->fl4_src,
					.tos = tos & IPTOS_RT_MASK,
					.scope = ((tos & RTO_ONLINK) ?
									RT_SCOPE_LINK :
									RT_SCOPE_UNIVERSE),
#ifdef CONFIG_IP_ROUTE_FWMARK
					.fwmark = oldflp->fl4_fwmark
#endif
			} },
				 .iif = myloopback_dev.ifindex,
				 .oif = oldflp->oif };
	struct fib_result res;
	unsigned flags = 0;
	struct net_device *dev_out = NULL;
	int free_res = 0;
	int err;


	res.fi		= NULL;
#ifdef CONFIG_IP_MULTIPLE_TABLES
	res.r		= NULL;
#endif
	
	if( oldflp->fl4_src ){
		err = -EINVAL;
		if( MULTICAST(oldflp->fl4_src) || BADCLASS(oldflp->fl4_src) ||
						ZERONET(oldflp->fl4_src) )
			goto out;
		dev_out = myip_dev_find( oldflp->fl4_src );
		if (dev_out == NULL)
			goto out;
		if( oldflp->oif == 0
						&& ( MULTICAST(oldflp->fl4_dst) || oldflp->fl4_dst == 0xFFFFFFFF) ){
			fl.oif = dev_out->ifindex;
			goto make_route;
		}
		if( dev_out )
			dev_put( dev_out );
		dev_out = NULL;
	}
	PR_DEBUG( "dev: %s, count: %d\n", myloopback_dev.name, atomic_read(&myloopback_dev.refcnt));
	if( oldflp->oif ){
		dev_out = dev_get_by_index( oldflp->oif );
		err = -ENODEV;
		if( dev_out == NULL )
			goto out;
		if( __in_dev_get_rtnl(dev_out) == NULL ){
			dev_put(dev_out);
			goto out;
		}
		if( LOCAL_MCAST(oldflp->fl4_dst) || oldflp->fl4_dst == 0xFFFFFFFF ){
			if( !fl.fl4_src )
				fl.fl4_src = myinet_select_addr( dev_out, 0, RT_SCOPE_LINK );
			goto make_route;
		}
		if( !fl.fl4_src ){
			if( MULTICAST(oldflp->fl4_dst) )
				fl.fl4_src = myinet_select_addr( dev_out, 0, fl.fl4_scope );
			else if( !oldflp->fl4_dst )
				fl.fl4_src = myinet_select_addr( dev_out, 0, RT_SCOPE_HOST );
		}
	}

	if( !fl.fl4_dst ){
		fl.fl4_dst = fl.fl4_src;
		if( !fl.fl4_dst )
			fl.fl4_dst = fl.fl4_src = htonl(INADDR_LOOPBACK);
		if( dev_out )
			dev_put(dev_out);
		dev_out = &myloopback_dev;
		dev_hold( dev_out );
		fl.oif = myloopback_dev.ifindex;
		res.type = RTN_LOCAL;
		flags |= RTCF_LOCAL;
		goto make_route;
	}

	if( myfib_lookup(&fl, &res) ){
		res.fi = NULL;
		if( oldflp->oif ){
			if (fl.fl4_src == 0)
				fl.fl4_src = myinet_select_addr( dev_out, 0, RT_SCOPE_LINK );
			res.type = RTN_UNICAST;
			goto make_route;
		}
		if (dev_out)
			dev_put(dev_out);
		err = -ENETUNREACH;
		goto out;
	}
	free_res = 1;

	if( res.type == RTN_LOCAL ){
		if( !fl.fl4_src )
			fl.fl4_src = fl.fl4_dst;
		if( dev_out )
			dev_put(dev_out);
		dev_out = &myloopback_dev;
		dev_hold(dev_out);
		fl.oif = dev_out->ifindex;
		if( res.fi )
			myfib_info_put(res.fi);
		res.fi = NULL;
		flags |= RTCF_LOCAL;
		goto make_route;
	}

#ifdef CONFIG_IP_ROUTE_MULTIPATH
	if( res.fi->fib_nhs > 1 && fl.oif == 0 )
		myfib_select_multipath( &fl, &res );
	else
#endif
	if( !res.prefixlen && res.type == RTN_UNICAST && !fl.oif )
		myfib_select_default(&fl, &res);

	if( !fl.fl4_src )
		fl.fl4_src = MYFIB_RES_PREFSRC(res);
	if (dev_out)
		dev_put(dev_out);
	dev_out = FIB_RES_DEV(res);
	dev_hold(dev_out);
	fl.oif = dev_out->ifindex;

make_route:
	err = myip_mkroute_output( rp, &res, &fl, oldflp, dev_out, flags );

	if( free_res )
		myfib_res_put(&res);
	if( dev_out )
		dev_put(dev_out);
out:
	return err;
}

int __myip_route_output_key(struct rtable **rp, const struct flowi *flp)
{
	unsigned hash;
	struct rtable *rth;
	int ret;

	hash = myrt_hash_code( flp->fl4_dst, flp->fl4_src ^ (flp->oif << 5), flp->fl4_tos );

	rcu_read_lock_bh();
	for( rth = rcu_dereference( myrt_hash_table[hash].chain ); rth;
					rth = rcu_dereference(rth->u.rt_next) ){
		if (rth->fl.fl4_dst == flp->fl4_dst && rth->fl.fl4_src == flp->fl4_src &&
						rth->fl.iif == 0 && rth->fl.oif == flp->oif &&
#ifdef CONFIG_IP_ROUTE_FWMARK
						rth->fl.fl4_fwmark == flp->fl4_fwmark &&
#endif
						!((rth->fl.fl4_tos ^ flp->fl4_tos) & (IPTOS_RT_MASK | RTO_ONLINK)) ){
			rth->u.dst.lastuse = jiffies;
			dst_hold(&rth->u.dst);
			rth->u.dst.__use++;
			MYRT_CACHE_STAT_INC(out_hit);
			rcu_read_unlock_bh();
			*rp = rth;
			return 0;
		}
		MYRT_CACHE_STAT_INC( out_hlist_search );
	}
	rcu_read_unlock_bh();

	ret = myip_route_output_slow(rp, flp);
	return ret;
}

int myip_route_output_flow(struct rtable **rp, struct flowi *flp, struct sock *sk, int flags)
{
	int err;

	if( (err = __myip_route_output_key(rp, flp)) != 0 )
		return err;

	if( flp->proto ){
		if( !flp->fl4_src )
			flp->fl4_src = (*rp)->rt_src;
		if( !flp->fl4_dst )
			flp->fl4_dst = (*rp)->rt_dst;
		//return xfrm_lookup((struct dst_entry **)rp, flp, sk, flags);
	}
	return 0;
}

static void * myalloc_large_system_hash(const char *tablename, unsigned long bucketsize,
				unsigned long numentries, int scale, int flags, unsigned int *_hash_shift,
				unsigned int *_hash_mask, unsigned long limit, unsigned long *table_order )
{
	unsigned long long max = limit;
	unsigned long log2qty, size;
	void *table = NULL;

	if( !numentries ){
		numentries = num_physpages;
		numentries += (1UL << (20 - PAGE_SHIFT)) - 1;
		numentries >>= 20 - PAGE_SHIFT;
		numentries <<= 20 - PAGE_SHIFT;

		if (scale > PAGE_SHIFT)
			numentries >>= (scale - PAGE_SHIFT);
		else
			numentries <<= (PAGE_SHIFT - scale);
	}
	numentries = 1UL << (long_log2(numentries) + 1);
	if (max == 0) {
		max = ((unsigned long long)num_physpages << PAGE_SHIFT) >> 4;
		do_div(max, bucketsize);
	}

	if( numentries > max )
		numentries = max;

	PR_DEBUG( "numentries: %lu, max: %llu\n", numentries, max );

	log2qty = long_log2( numentries );

	do{
		size = bucketsize << log2qty;
		PR_DEBUG( "bucketsize: %lu, %lu\n", size, bucketsize );
		{
			unsigned long order;
			for (order = 0; ((1UL << order) << PAGE_SHIFT) < size; order++);
			table = (void*) __get_free_pages(GFP_ATOMIC, order);
			*table_order = order;
		}
	}while( !table && size > PAGE_SIZE && --log2qty );

	if( !table )
		panic("Failed to allocate %s hash table\n", tablename);
	PR_DEBUG("%s hash table entries: %d (order: %d, %lu bytes)\n",
					tablename, (1U << log2qty), long_log2(size) - PAGE_SHIFT, size );

	if( _hash_shift )
		*_hash_shift = log2qty;
	if( _hash_mask )
		*_hash_mask = (1 << log2qty) - 1;
	return table;
}

static void myrt_run_flush( unsigned long dummy )
{
	int i;
	struct rtable *rth, *next;

	myrt_deadline = 0;

	get_random_bytes( &myrt_hash_rnd, 4 );

	for( i = myrt_hash_mask; i >= 0; i-- ){
		rth = myrt_hash_table[i].chain;
		if( rth )
			myrt_hash_table[i].chain = NULL;

		for( ; rth; rth = next ){
			next = rth->u.rt_next;
			myrt_free(rth);
		}
	}
}

#ifdef CONFIG_IP_ROUTE_MULTIPATH_CACHED
static struct rtable **myrt_remove_balanced_route(struct rtable **chain_head,
						struct rtable *expentry, int *removed_count)
{
	int passedexpired = 0;
	struct rtable **nextstep = NULL;
	struct rtable **rthp = chain_head;
	struct rtable *rth;

	if( removed_count )
		*removed_count = 0;

	while( (rth = *rthp) != NULL ){
		if( rth == expentry )
			passedexpired = 1;
		if( ((*rthp)->u.dst.flags & DST_BALANCED) != 0  &&
						mycompare_keys(&(*rthp)->fl, &expentry->fl) ){
			if( *rthp == expentry ){
				*rthp = rth->u.rt_next;
				continue;
			}else{
				*rthp = rth->u.rt_next;
				myrt_free(rth);
				if( removed_count )
					++(*removed_count);
			}
		}else{
			if( !((*rthp)->u.dst.flags & DST_BALANCED) &&
							passedexpired && !nextstep )
				nextstep = &rth->u.rt_next;

			rthp = &rth->u.rt_next;
		}
	}

	myrt_free(expentry);
	if( removed_count )
		++( *removed_count );
	return nextstep;
}
#endif /* CONFIG_IP_ROUTE_MULTIPATH_CACHED */

static void myrt_check_expire(unsigned long dummy)
{
	static unsigned int rover;
	unsigned int i = rover, goal;
	struct rtable *rth, **rthp;
	unsigned long now = jiffies;
	u64 mult;

	mult = ((u64)myip_rt_gc_interval) << myrt_hash_log;
	if( myip_rt_gc_timeout > 1 )
		do_div( mult, myip_rt_gc_timeout );
	goal = (unsigned int)mult;
	if( goal > myrt_hash_mask ) 
		goal = myrt_hash_mask + 1;

	for( ; goal > 0; goal-- ){
		unsigned long tmo = myip_rt_gc_timeout;

		i = (i + 1) & myrt_hash_mask;
		rthp = &myrt_hash_table[i].chain;

		if (*rthp == 0)
			continue;
		//spin_lock( myrt_hash_lock_addr(i) );
		while( (rth = *rthp) != NULL ){
			if( rth->u.dst.expires ){
				if( time_before_eq(now, rth->u.dst.expires) ){
					tmo >>= 1;
					rthp = &rth->u.rt_next;
					continue;
				}
			}else if( !myrt_may_expire(rth, tmo, myip_rt_gc_timeout) ){
				tmo >>= 1;
				rthp = &rth->u.rt_next;
				continue;
			}
#ifdef CONFIG_IP_ROUTE_MULTIPATH_CACHED
			if( rth->u.dst.flags & DST_BALANCED ){
				rthp = myrt_remove_balanced_route( &myrt_hash_table[i].chain,
								rth, NULL);
				if (!rthp)
					break;
			}else{
				*rthp = rth->u.rt_next;
				myrt_free(rth);
			}
#else /* CONFIG_IP_ROUTE_MULTIPATH_CACHED */
 			*rthp = rth->u.rt_next;
 			myrt_free(rth);
#endif /* CONFIG_IP_ROUTE_MULTIPATH_CACHED */
		}
		//spin_unlock( myrt_hash_lock_addr(i) );

		if( time_after(jiffies, now) )
			break;
	}
	rover = i;
	mod_timer( &myrt_periodic_timer, jiffies + myip_rt_gc_interval );
}

static void myrt_secret_rebuild(unsigned long dummy)
{
	unsigned long now = jiffies;

	myrt_cache_flush(0);
	mod_timer( &myrt_secret_timer, now + myip_rt_secret_interval);

}

static DEFINE_SPINLOCK( myrt_flush_lock );
void myrt_cache_flush(int delay)
{
	unsigned long now = jiffies;
	int user_mode = !in_softirq();

	if (delay < 0)
		delay = myip_rt_min_delay;

	multipath_flush();

	spin_lock_bh( &myrt_flush_lock );

	if( del_timer( &myrt_flush_timer ) && delay > 0 && myrt_deadline ){
		long tmo = (long)( myrt_deadline - now );
		if(  user_mode && tmo < myip_rt_max_delay - myip_rt_min_delay )
			tmo = 0;
		if (delay > tmo)
			delay = tmo;
	}

	if (delay <= 0) {
		spin_unlock_bh( &myrt_flush_lock );
		myrt_run_flush(0);
		return;
	}

	if( myrt_deadline == 0 )
		myrt_deadline = now + myip_rt_max_delay;

	mod_timer( &myrt_flush_timer, now+delay );
	spin_unlock_bh( &myrt_flush_lock );
}

static __initdata unsigned long myrhash_entries;
int __init myip_rt_init(void)
{
	int rc = 0;
	myrt_hash_rnd = (int)( (num_physpages ^ (num_physpages>>8)) ^ (jiffies^(jiffies >> 7)) );
	
#ifdef CONFIG_NET_CLS_ROUTE
	{
		int order;
		for (order = 0; (PAGE_SIZE << order) < 256 * sizeof(struct ip_rt_acct) * NR_CPUS; order++)
			;//NOTHING.
		myip_rt_acct = (struct ip_rt_acct *)__get_free_pages(GFP_KERNEL, order);
		if( !myip_rt_acct )
			panic("IP: failed to allocate ip_rt_acct\n");
		memset( myip_rt_acct, 0, PAGE_SIZE << order );
	}
#endif
	myipv4_dst_ops.kmem_cachep = kmem_cache_create( "myip_dst_cache",
					sizeof(struct rtable), 0, SLAB_HWCACHE_ALIGN, NULL, NULL );
	if( !myipv4_dst_ops.kmem_cachep )
		panic("IP: failed to allocate ip_dst_cache\n");

	myrt_hash_table = (struct rt_hash_bucket *)myalloc_large_system_hash("MYIP route cache",
					sizeof(struct rt_hash_bucket), myrhash_entries,
					(num_physpages >= 128 * 1024) ? 15 : 17, HASH_HIGHMEM,
					&myrt_hash_log, &myrt_hash_mask, 0, &mytable_order );
	memset( myrt_hash_table, 0, ( myrt_hash_mask + 1) * sizeof(struct rt_hash_bucket) );

	PR_DEBUG( "myrt_hash_table: %p\n", myrt_hash_table );

	myrt_hash_lock_init();

	myipv4_dst_ops.gc_thresh = ( myrt_hash_mask + 1 );
	myip_rt_max_size = ( myrt_hash_mask + 1 ) * 16;

	init_timer( &myrt_flush_timer );
	myrt_flush_timer.function = myrt_run_flush;

	init_timer( &myrt_periodic_timer );
	myrt_periodic_timer.function = myrt_check_expire;

	init_timer( &myrt_secret_timer );
	myrt_secret_timer.function = myrt_secret_rebuild;

	myrt_periodic_timer.expires = jiffies + net_random() % myip_rt_gc_interval +
					myip_rt_gc_interval;
	add_timer( &myrt_periodic_timer );

	myrt_secret_timer.expires = jiffies + net_random() % myip_rt_secret_interval +
			myip_rt_secret_interval;
	add_timer( &myrt_secret_timer );

	myip_fib_init();
/*
#ifdef CONFIG_PROC_FS
	{
		struct proc_dir_entry *rtstat_pde = NULL;
		if( !proc_net_fops_create("rt_cache", S_IRUGO, &rt_cache_seq_fops ) ||
						!(rtstat_pde = create_proc_entry("rt_cache", S_IRUGO, 
										proc_net_stat))) {
			return -ENOMEM;
		}
		rtstat_pde->proc_fops = &rt_cpu_seq_fops;
	}
#ifdef CONFIG_NET_CLS_ROUTE
	create_proc_read_entry("rt_acct", 0, proc_net, ip_rt_acct_read, NULL);
#endif
#endif
*/
	return 0;
}

void __exit myip_rt_exit(void)
{
	struct rtable *rth;
	int i;
	myip_fib_exit();

	del_timer( &myrt_periodic_timer );
	del_timer( &myrt_secret_timer );
	del_timer( &myrt_flush_timer );

	for( i = 0; i < myrt_hash_mask + 1; i ++ ){
		for( rth = rcu_dereference( myrt_hash_table[i].chain ); rth;
						rth = rcu_dereference(rth->u.rt_next) ){
			dev_put( rth->u.dst.dev );
			kmem_cache_free( myipv4_dst_ops.kmem_cachep, rth );
        }
    }

	if( myrt_hash_table )
		__free_pages( virt_to_page((void *)myrt_hash_table), mytable_order );

	if( myipv4_dst_ops.kmem_cachep )
		kmem_cache_destroy( myipv4_dst_ops.kmem_cachep );
#ifdef CONFIG_NET_CLS_ROUTE
	if( myip_rt_acct ){
		int order;
		for (order = 0; (PAGE_SIZE << order) < 256 * sizeof(struct ip_rt_acct) * NR_CPUS; order++);
		__free_pages( virt_to_page((void *)myip_rt_acct), order );
	}
#endif 
}

EXPORT_SYMBOL_GPL( myipv4_dst_ops );
EXPORT_SYMBOL_GPL( myip_route_output_flow );