fib_hash.c

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

		memcpy( &dst, rta->rta_dst, 4 );
		if( dst & ~FZ_MASK(fz) )
			return -EINVAL;
		key = myfz_key(dst, fz);
	}
	f = myfib_find_node( fz, key );

	if( !f )
		fa = NULL;
	else
		fa = myfib_find_alias(&f->fn_alias, tos, 0);
	if (!fa)
		return -ESRCH;

	fa_to_delete = NULL;
	fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
	list_for_each_entry_continue(fa, &f->fn_alias, fa_list) {
		struct fib_info *fi = fa->fa_info;
		if (fa->fa_tos != tos)
			break;
		if( (!r->rtm_type || fa->fa_type == r->rtm_type) &&
						(r->rtm_scope == RT_SCOPE_NOWHERE || fa->fa_scope == r->rtm_scope) &&
						(!r->rtm_protocol || fi->fib_protocol == r->rtm_protocol) &&
						myfib_nh_match(r, n, rta, fi) == 0) {
			fa_to_delete = fa;
			break;
		}
	}

	if( fa_to_delete ){
		int kill_fn;
		fa = fa_to_delete;
		//rtmsg_fib(RTM_DELROUTE, key, fa, z, tb->tb_id, n, req);

		kill_fn = 0;
		write_lock_bh( &myfib_hash_lock );
		list_del( &fa->fa_list );
		if( list_empty(&f->fn_alias) ){
			hlist_del( &f->fn_hash );
			kill_fn = 1;
		}
		myfib_hash_genid++;
		write_unlock_bh( &myfib_hash_lock );

		if (fa->fa_state & FA_S_ACCESSED)
			myrt_cache_flush(-1);
		myfn_free_alias(fa);
		if( kill_fn ){
			myfn_free_node(f);
			fz->fz_nent--;
		}
		return 0;
	}
	return -ESRCH;
}

static int myfn_flush_list(struct fn_zone *fz, int idx)
{
	struct hlist_head *head = &fz->fz_hash[idx];
	struct hlist_node *node, *n;
	struct fib_node *f;
	int found = 0;

	hlist_for_each_entry_safe(f, node, n, head, fn_hash) {
		struct fib_alias *fa, *fa_node;
		int kill_f;

		kill_f = 0;
		list_for_each_entry_safe(fa, fa_node, &f->fn_alias, fa_list) {
			struct fib_info *fi = fa->fa_info;

			if( fi && (fi->fib_flags & RTNH_F_DEAD) ){
				write_lock_bh( &myfib_hash_lock );
				list_del(&fa->fa_list);
				if( list_empty(&f->fn_alias) ){
					hlist_del(&f->fn_hash);
					kill_f = 1;
				}
				myfib_hash_genid++;
				write_unlock_bh( &myfib_hash_lock );
				myfn_free_alias( fa );
				found++;
			}
		}
		if( kill_f ){
			myfn_free_node(f);
			fz->fz_nent--;
		}
	}
	return found;
}

static int myfn_hash_flush(struct fib_table *tb)
{
	struct fn_hash *table = (struct fn_hash *) tb->tb_data;
	struct fn_zone *fz;
	int found = 0;

	for( fz = table->fn_zone_list; fz; fz = fz->fz_next ){
		int i;
		for( i = fz->fz_divisor - 1; i >= 0; i-- )
			found += myfn_flush_list(fz, i);
	}
	return found;
}

int myfib_detect_death(struct fib_info *fi, int order,
				struct fib_info **last_resort, int *last_idx, int *dflt)
{
	struct neighbour *n;
	int state = NUD_NONE;

	n = myneigh_lookup( &myarp_tbl, &fi->fib_nh[0].nh_gw, fi->fib_dev );
	if( n ){
		state = n->nud_state;
		myneigh_release(n);
	}
	if( state==NUD_REACHABLE )
		return 0;
	if( (state & NUD_VALID) && order != *dflt )
		return 0;
	if( (state & NUD_VALID) || (*last_idx < 0 && order > *dflt) ){
		*last_resort = fi;
		*last_idx = order;
	}
	return 1;
}

static int myfn_hash_last_dflt=-1;
static void myfn_hash_select_default(struct fib_table *tb, 
				const struct flowi *flp, struct fib_result *res)
{
	int order, last_idx;
	struct hlist_node *node;
	struct fib_node *f;
	struct fib_info *fi = NULL;
	struct fib_info *last_resort;
	struct fn_hash *t = (struct fn_hash*)tb->tb_data;
	struct fn_zone *fz = t->fn_zones[0];

	if (fz == NULL)
		return;

	last_idx = -1;
	last_resort = NULL;
	order = -1;
	
	read_lock( &myfib_hash_lock );
	hlist_for_each_entry( f, node, &fz->fz_hash[0], fn_hash ){
		struct fib_alias *fa;
		list_for_each_entry(fa, &f->fn_alias, fa_list) {
			struct fib_info *next_fi = fa->fa_info;
			if( fa->fa_scope != res->scope || fa->fa_type != RTN_UNICAST )
				continue;
			if( next_fi->fib_priority > res->fi->fib_priority )
				break;
			if( !next_fi->fib_nh[0].nh_gw || next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK )
				continue;
			fa->fa_state |= FA_S_ACCESSED;

			if( fi == NULL ){
				if( next_fi != res->fi )
					break;
			}else if( !myfib_detect_death(fi, order, &last_resort,
									&last_idx, &myfn_hash_last_dflt) ){
				if (res->fi)
					myfib_info_put(res->fi);
				res->fi = fi;
				atomic_inc(&fi->fib_clntref);
				myfn_hash_last_dflt = order;
				goto out;
			}
			fi = next_fi;
			order++;
		}
	}

	if( order <= 0 || fi == NULL ){
		myfn_hash_last_dflt = -1;
		goto out;
	}

	if( !myfib_detect_death(fi, order, &last_resort, &last_idx, &myfn_hash_last_dflt) ){
		if (res->fi)
			myfib_info_put(res->fi);
		res->fi = fi;
		atomic_inc(&fi->fib_clntref);
		myfn_hash_last_dflt = order;
		goto out;
	}

	if( last_idx >= 0 ){
		if( res->fi )
			myfib_info_put(res->fi);
		res->fi = last_resort;
		if( last_resort )
			atomic_inc(&last_resort->fib_clntref);
	}
	myfn_hash_last_dflt = last_idx;
out:
	read_unlock( &myfib_hash_lock );
}

static inline int myfn_hash_dump_bucket( struct sk_buff *skb, struct netlink_callback *cb,
		     struct fib_table *tb, struct fn_zone *fz, struct hlist_head *head )
{
	struct hlist_node *node;
	struct fib_node *f;
	int i, s_i;

	s_i = cb->args[3];
	i = 0;
	hlist_for_each_entry(f, node, head, fn_hash) {
		struct fib_alias *fa;
		list_for_each_entry(fa, &f->fn_alias, fa_list) {
			if( i < s_i )
				goto next;
			if( myfib_dump_info(skb, NETLINK_CB(cb->skb).pid,
					  cb->nlh->nlmsg_seq, RTM_NEWROUTE,
					  tb->tb_id, fa->fa_type, fa->fa_scope,
					  &f->fn_key, fz->fz_order, fa->fa_tos,
					  fa->fa_info, NLM_F_MULTI) < 0 ){
				cb->args[3] = i;
				return -1;
			}
next:
			i++;
		}
	}
	cb->args[3] = i;
	return skb->len;
}

static inline int myfn_hash_dump_zone(struct sk_buff *skb, struct netlink_callback *cb,
				struct fib_table *tb, struct fn_zone *fz)
{
	int h, s_h;

	s_h = cb->args[2];
	for (h=0; h < fz->fz_divisor; h++) {
		if( h < s_h ) 
			continue;
		if( h > s_h )
			memset(&cb->args[3], 0, sizeof(cb->args) - 3 * sizeof(cb->args[0]) );
		if( fz->fz_hash == NULL || hlist_empty(&fz->fz_hash[h]) )
			continue;
		if( myfn_hash_dump_bucket(skb, cb, tb, fz, &fz->fz_hash[h])<0 ){
			cb->args[2] = h;
			return -1;
		}
	}
	cb->args[2] = h;
	return skb->len;
}

static int myfn_hash_dump(struct fib_table *tb,
				struct sk_buff *skb, struct netlink_callback *cb)
{
	int m, s_m;
	struct fn_zone *fz;
	struct fn_hash *table = (struct fn_hash*)tb->tb_data;

	s_m = cb->args[1];
	read_lock( &myfib_hash_lock );
	for (fz = table->fn_zone_list, m=0; fz; fz = fz->fz_next, m++) {
		if( m < s_m ) 
			continue;
		if( m > s_m )
			memset( &cb->args[2], 0, sizeof(cb->args) - 2 * sizeof(cb->args[0]) );
		if( myfn_hash_dump_zone(skb, cb, tb, fz) < 0 ){
			cb->args[1] = m;
			read_unlock( &myfib_hash_lock );
			return -1;
		}
	}
	read_unlock( &myfib_hash_lock );
	cb->args[1] = m;
	return skb->len;
}

struct fib_table *myfib_hash_init( int id )
{
	struct fib_table *tb;

	if( myfn_hash_kmem == NULL )
		myfn_hash_kmem = kmem_cache_create("myip_fib_hash", sizeof(struct fib_node),
						0, SLAB_HWCACHE_ALIGN, NULL, NULL );
	if( myfn_alias_kmem == NULL )
		myfn_alias_kmem = kmem_cache_create("myip_fib_alias", sizeof(struct fib_alias),
						  0, SLAB_HWCACHE_ALIGN, NULL, NULL );

	tb = kmalloc( sizeof(struct fib_table) + sizeof(struct fn_hash), GFP_KERNEL );
	if( tb == NULL )
		return NULL;

	tb->tb_id = id;
	tb->tb_lookup = myfn_hash_lookup;
	tb->tb_insert = myfn_hash_insert;
	tb->tb_delete = myfn_hash_delete;
	tb->tb_flush = myfn_hash_flush;
	tb->tb_select_default = myfn_hash_select_default;
	tb->tb_dump = myfn_hash_dump;
	memset(tb->tb_data, 0, sizeof(struct fn_hash));
	return tb;
}

#if 1
void dump_fib_node( struct fib_table *tb )
{
	struct fn_hash *table = (struct fn_hash *) tb->tb_data;
	struct fn_zone *plist = table->fn_zone_list;
	int i;

	struct hlist_head *head;
    struct hlist_node *node;
    struct fib_node *f;

	printk( KERN_NOTICE "the table id: %d\n", tb->tb_id );
	while( plist != NULL ){
		printk( KERN_NOTICE "the dst len: %d, %x\n", plist->fz_order, plist->fz_mask );
		printk( KERN_NOTICE "the hash: %d, %x\n", plist->fz_divisor, plist->fz_hashmask );
		printk( KERN_NOTICE "the num of fib_node: %d\n", plist->fz_nent );
		for( i = 0; i < plist->fz_divisor; i ++ ){	
			head = &(plist->fz_hash[i]);
			hlist_for_each_entry( f, node, head, fn_hash ){			
				struct list_head *head2;
				struct fib_alias *f2;
				head2 = &(f->fn_alias);	
				printk( KERN_NOTICE "\tfn_key: %u.%u.%u.%u\n", NIPQUAD(f->fn_key) );
				list_for_each_entry( f2, head2, fa_list ){
					printk( KERN_NOTICE "\t\ttos: %x\n", f2->fa_tos );
					printk( KERN_NOTICE "\t\ttype: %d\n", f2->fa_type );
					printk( KERN_NOTICE "\t\tscope: %d\n", f2->fa_scope );
					printk( KERN_NOTICE "\t\tstate: %d\n", f2->fa_state );
				}
            }
		}
		plist = plist->fz_next;
	}
}
#else
void dump_fib_node( struct fib_table *tb )
{
}
#endif

void __exit myfn_zone_free( struct fn_zone* zone )
{
	struct hlist_head *head;
    struct hlist_node *node;
    struct hlist_node *tmp;
    struct fib_node *f;
    int i;

    for( i = 0; i < zone->fz_divisor; i ++ ){
        f = NULL;
        head = &(zone->fz_hash[i]);
        hlist_for_each_entry_safe( f, node, tmp, head, fn_hash ){
			struct list_head *head2;
			struct fib_alias *node2;
			struct fib_alias *f2;
			
            hlist_del( node );
			head2 = &(f->fn_alias);
			list_for_each_entry_safe( f2, node2, head2, fa_list ){
				list_del( &f2->fa_list );
				kmem_cache_free( myfn_alias_kmem, f2 );
			}

			kmem_cache_free( myfn_hash_kmem, f );
        }
    }
}

void __exit myfib_hash_exit(void)
{
	if( myfn_hash_kmem )
		kmem_cache_destroy( myfn_hash_kmem );
	if( myfn_alias_kmem )
		kmem_cache_destroy( myfn_alias_kmem );

	myfib_info_exit();
}