neighbour.c

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

		atomic_inc( &neigh->probes );
		if( skb )
			kfree_skb(skb);
	}else{
out:
		write_unlock(&neigh->lock);
	}
	PR_DEBUG( "neigh refcnt: %d\n", atomic_read(&neigh->refcnt) );
	myneigh_release(neigh);
}

static struct neighbour *myneigh_alloc( struct neigh_table *tbl )
{
	struct neighbour *n = NULL;
	unsigned long now = jiffies;
	int entries;

	entries = atomic_inc_return( &tbl->entries ) - 1;
	PR_DEBUG( "the entryies alrady in tbl: %d\n", entries );

	if( entries >= tbl->gc_thresh3 || (entries >= tbl->gc_thresh2 &&
							time_after(now, tbl->last_flush + 5 * HZ)) ){
		if( !myneigh_forced_gc( tbl ) && entries >= tbl->gc_thresh3 )
			goto out_entries;
	}

	n = kmem_cache_alloc( tbl->kmem_cachep, SLAB_ATOMIC );
	if( !n )
		goto out_entries;

	memset( n, 0, tbl->entry_size );
	skb_queue_head_init( &n->arp_queue );
	rwlock_init( &n->lock );
	n->updated		= n->used = now;
	n->nud_state	= NUD_NONE;
	n->output		= myneigh_blackhole;
	n->parms		= myneigh_parms_clone(&tbl->parms);
	init_timer( &n->timer );
	n->timer.function = myneigh_timer_handler;
	n->timer.data	  = (unsigned long)n;

	NEIGH_CACHE_STAT_INC(tbl, allocs);
	n->tbl		  	= tbl;
	atomic_set(&n->refcnt, 1);
	n->dead		  	= 1;
out:
	return n;
out_entries:
	atomic_dec( &tbl->entries );
	goto out;
}

static struct neighbour **myneigh_hash_alloc( unsigned int entries )
{
	unsigned long size = entries * sizeof(struct neighbour *);
	struct neighbour **ret;

	if (size <= PAGE_SIZE) {
		ret = kmalloc(size, GFP_ATOMIC);
	} else {
		ret = (struct neighbour **)
			__get_free_pages(GFP_ATOMIC, get_order(size));
	}
	if (ret)
		memset(ret, 0, size);

	return ret;
}

static void myneigh_hash_grow( struct neigh_table *tbl, unsigned long new_entries )
{
	struct neighbour **new_hash, **old_hash;
	unsigned int i, new_hash_mask, old_entries;

	PR_DEEP_DEBUG( "grow the tbl hash to size: %lu\n", new_entries );

	NEIGH_CACHE_STAT_INC(tbl, hash_grows);
	BUG_ON( new_entries & (new_entries - 1) );

	new_hash = myneigh_hash_alloc( new_entries );
	if (!new_hash)
		return;

	old_entries = tbl->hash_mask + 1;
	new_hash_mask = new_entries - 1;
	old_hash = tbl->hash_buckets;

	get_random_bytes(&tbl->hash_rnd, sizeof(tbl->hash_rnd));
	for( i = 0; i < old_entries; i++ ){
		struct neighbour *n, *next;
		for( n = old_hash[i]; n; n = next ){
			unsigned int hash_val = tbl->hash( n->primary_key, n->dev );
			hash_val &= new_hash_mask;
			next = n->next;
			n->next = new_hash[hash_val];
			new_hash[hash_val] = n;
		}
	}
	tbl->hash_buckets = new_hash;
	tbl->hash_mask = new_hash_mask;
	myneigh_hash_free( old_hash, old_entries );
}

struct neighbour *myneigh_lookup(struct neigh_table *tbl, const void *pkey,
				struct net_device *dev)
{
	struct neighbour *n;
	int key_len = tbl->key_len;
	u32 hash_val = tbl->hash(pkey, dev) & tbl->hash_mask;

	PR_DEEP_DEBUG( "the pkey is %u.%u.%u.%u, the hash value is: %u\n",
					NIPQUAD( *((u32 *)pkey) ), hash_val );

	NEIGH_CACHE_STAT_INC(tbl, lookups);

	read_lock_bh( &tbl->lock );
	for( n = tbl->hash_buckets[hash_val]; n; n = n->next ){
		PR_DEBUG("%u.%u.%u.%u\n", NIPQUAD(*((u32 *)(n->primary_key))) );
		if( /*dev == n->dev &&*/ !memcmp(n->primary_key, pkey, key_len) ){	//tmp code FIXME!!
			neigh_hold( n );
			NEIGH_CACHE_STAT_INC( tbl, hits );
			PR_DEEP_DEBUG( "find a neighbour in hash_buckets: %p\n", n );
			break;
		}
	}
	read_unlock_bh( &tbl->lock );
	return n;
}

struct neighbour *myneigh_create( struct neigh_table *tbl, const void *pkey,
			       struct net_device *dev )
{
	u32 hash_val;
	int key_len = tbl->key_len;
	int error;
	struct neighbour *n1, *rc, *n = myneigh_alloc( tbl );

	if( !n ){
		rc = ERR_PTR(-ENOBUFS);
		goto out;
	}
	
	memcpy(n->primary_key, pkey, key_len);
	n->dev = dev;
	dev_hold(dev);

	if( tbl->constructor &&	(error = tbl->constructor(n)) < 0 ){
		PR_ERR( "tbl->constructor failed!\n" );
		rc = ERR_PTR(error);
		goto out_neigh_release;
	}

	if( n->parms->neigh_setup && (error = n->parms->neigh_setup(n)) < 0 ){
		PR_ERR( "n->parms->neigh_setup failed!\n" );
		rc = ERR_PTR(error);
		goto out_neigh_release;
	}

	n->confirmed = jiffies - (n->parms->base_reachable_time << 1);

	write_lock_bh(&tbl->lock);
	if( atomic_read(&tbl->entries) > (tbl->hash_mask + 1) )
		myneigh_hash_grow( tbl, (tbl->hash_mask + 1) << 1 );

	hash_val = tbl->hash(pkey, dev) & tbl->hash_mask;

	if( n->parms->dead ){
		rc = ERR_PTR(-EINVAL);
		goto out_tbl_unlock;
	}

	for (n1 = tbl->hash_buckets[hash_val]; n1; n1 = n1->next) {
		if (dev == n1->dev && !memcmp(n1->primary_key, pkey, key_len)) {
			neigh_hold(n1);
			rc = n1;
			goto out_tbl_unlock;
		}
	}

	n->next = tbl->hash_buckets[hash_val];
	tbl->hash_buckets[hash_val] = n;
	n->dead = 0;
	neigh_hold(n);
	PR_DEBUG( "neigh: %d\n", atomic_read( &n->refcnt ) );
	write_unlock_bh(&tbl->lock);
	PR_DEEP_DEBUG( "the hash val: %d, the hash: %p\n", hash_val, tbl->hash_buckets[hash_val] );
	PR_DEBUG( "neigh %p is created.\n", n );
	rc = n;
out:
	return rc;
out_tbl_unlock:
	write_unlock_bh(&tbl->lock);
out_neigh_release:
	myneigh_release(n);
	goto out;
}

static inline void myneigh_add_timer(struct neighbour *n, unsigned long when)
{
	if( unlikely(mod_timer(&n->timer, when)) ){
		PR_ERR( "NEIGH: BUG, double timer add, state is %x\n", n->nud_state);
		dump_stack();
	}
}

int __myneigh_event_send(struct neighbour *neigh, struct sk_buff *skb)
{
	int rc;
	unsigned long now;
	write_lock_bh(&neigh->lock);

	rc = 0;
	if( neigh->nud_state & (NUD_CONNECTED | NUD_DELAY | NUD_PROBE) )
		goto out_unlock_bh;

	now = jiffies;
	
	if( !(neigh->nud_state & (NUD_STALE | NUD_INCOMPLETE)) ){
		if( neigh->parms->mcast_probes + neigh->parms->app_probes ){
			atomic_set( &neigh->probes, neigh->parms->ucast_probes );
			neigh->nud_state     = NUD_INCOMPLETE;
			neigh_hold(neigh);
			PR_DEBUG( "neigh: %d\n", atomic_read(&neigh->refcnt) );
			myneigh_add_timer(neigh, now + 1);
		}else{
			neigh->nud_state = NUD_FAILED;
			write_unlock_bh(&neigh->lock);
			if (skb)
				kfree_skb(skb);
			return 1;
		}
	}else if( neigh->nud_state & NUD_STALE ) {
		PR_DEBUG( "neigh %p is delayed.\n", neigh );
		neigh_hold(neigh);
		neigh->nud_state = NUD_DELAY;
		myneigh_add_timer( neigh, jiffies + neigh->parms->delay_probe_time );
	}

	if( neigh->nud_state == NUD_INCOMPLETE ){
		if( skb ){
			if( skb_queue_len(&neigh->arp_queue) >= neigh->parms->queue_len ){
				struct sk_buff *buff;
				buff = neigh->arp_queue.next;
				__skb_unlink( buff, &neigh->arp_queue );
				kfree_skb( buff );
			}
			__skb_queue_tail( &neigh->arp_queue, skb );
		}
		rc = 1;
	}
	PR_DEBUG( "mcast_probes: %d, app_probes: %d\n", neigh->parms->mcast_probes, 
					neigh->parms->app_probes );
out_unlock_bh:
	write_unlock_bh(&neigh->lock);
	return rc;
}

static void myneigh_hh_init(struct neighbour *n, struct dst_entry *dst, u16 protocol)
{
	struct hh_cache	*hh;
	struct net_device *dev = dst->dev;

	for (hh = n->hh; hh; hh = hh->hh_next)
		if (hh->hh_type == protocol)
			break;

	if( !hh && (hh = kmalloc(sizeof(*hh), GFP_ATOMIC)) != NULL ){
		memset(hh, 0, sizeof(struct hh_cache));
		rwlock_init(&hh->hh_lock);
		hh->hh_type = protocol;
		atomic_set(&hh->hh_refcnt, 0);
		hh->hh_next = NULL;
		if( dev->hard_header_cache(n, hh) ){
			kfree(hh);
			hh = NULL;
		}else{
			atomic_inc(&hh->hh_refcnt);
			hh->hh_next = n->hh;
			n->hh = hh;
			if (n->nud_state & NUD_CONNECTED)
				hh->hh_output = n->ops->hh_output;
			else
				hh->hh_output = n->ops->output;
		}
	}
	if (hh)	{
		atomic_inc(&hh->hh_refcnt);
		dst->hh = hh;
	}
}

int myneigh_resolve_output(struct sk_buff *skb)
{
	struct dst_entry *dst = skb->dst;
	struct neighbour *neigh;
	int rc = 0;

	PR_DEBUG( "in myneigh_resolve_output!\n");
	if (!dst || !(neigh = dst->neighbour)){
		PR_ERR( "dst is NULL, discard!\n");
		goto discard;
	}
	__skb_pull(skb, skb->nh.raw - skb->data);

	if( !myneigh_event_send(neigh, skb) ){
		int err;
		struct net_device *dev = neigh->dev;
		if( dev->hard_header_cache && !dst->hh ){
			write_lock_bh(&neigh->lock);
			if (!dst->hh)
				myneigh_hh_init(neigh, dst, dst->ops->protocol);
			err = dev->hard_header(skb, dev, ntohs(skb->protocol),neigh->ha, NULL, skb->len);
			write_unlock_bh(&neigh->lock);
		}else{
			read_lock_bh(&neigh->lock);
			err = dev->hard_header(skb, dev, ntohs(skb->protocol), neigh->ha, NULL, skb->len);
			read_unlock_bh(&neigh->lock);
		}
		if (err >= 0)
			rc = neigh->ops->queue_xmit(skb);
		else
			goto out_kfree_skb;
	}
out:
	return rc;
discard:
	PR_DEBUG( "neigh_resolve_output: dst=%p neigh=%p\n",
					dst, dst ? dst->neighbour : NULL);
out_kfree_skb:
	rc = -EINVAL;
	kfree_skb(skb);
	goto out;
}

int myneigh_connected_output( struct sk_buff *skb )
{
	int err;
	struct dst_entry *dst = skb->dst;
	struct neighbour *neigh = dst->neighbour;
	struct net_device *dev = neigh->dev;

	__skb_pull(skb, skb->nh.raw - skb->data);

	read_lock_bh(&neigh->lock);
	err = dev->hard_header(skb, dev, ntohs(skb->protocol),
			       neigh->ha, NULL, skb->len);
	read_unlock_bh(&neigh->lock);
	if (err >= 0)
		err = neigh->ops->queue_xmit(skb);
	else {
		err = -EINVAL;
		kfree_skb(skb);
	}
	return err;

}

int myneigh_compat_output( struct sk_buff *skb )
{
	return 0;
}

void myneigh_parms_destroy(struct neigh_parms *parms)
{
	kfree(parms);
}

static int myneigh_del_timer(struct neighbour *n)
{
	if( (n->nud_state & NUD_IN_TIMER) && del_timer(&n->timer) ){
		myneigh_release(n);
		return 1;
	}
	return 0;
}

void myneigh_destroy(struct neighbour *neigh)
{
	struct hh_cache *hh;

	NEIGH_CACHE_STAT_INC( neigh->tbl, destroys );

	if( !neigh->dead ){
		PR_WARN( "Destroying alive neighbour %p\n", neigh );
		dump_stack();
		return;
	}
	if( myneigh_del_timer(neigh) )
		PR_WARN( "Impossible event.\n" );

	while( (hh = neigh->hh) != NULL ){
		neigh->hh = hh->hh_next;
		hh->hh_next = NULL;
		write_lock_bh(&hh->hh_lock);
		hh->hh_output = myneigh_blackhole;
		write_unlock_bh(&hh->hh_lock);
		if( atomic_dec_and_test(&hh->hh_refcnt) )
			kfree( hh );
	}

	if( neigh->ops && neigh->ops->destructor )
		(neigh->ops->destructor)(neigh);

	skb_queue_purge( &neigh->arp_queue );

	dev_put(neigh->dev);
	myneigh_parms_put(neigh->parms);

	PR_DEBUG( "neigh %p is destroyed.\n", neigh);

	atomic_dec(&neigh->tbl->entries);
	kmem_cache_free( neigh->tbl->kmem_cachep, neigh );
}

static void myneigh_periodic_timer(unsigned long arg)
{
	struct neigh_table *tbl = (struct neigh_table *)arg;
	struct neighbour *n, **np;
	unsigned long expire, now = jiffies;

	NEIGH_CACHE_STAT_INC(tbl, periodic_gc_runs);
	write_lock(&tbl->lock);

	//PR_DEBUG( "%lu, %lu\n", now/HZ, tbl->last_rand/HZ + 300 );

	if( time_after(now, tbl->last_rand + 300 * HZ) ){
		struct neigh_parms *p;
		tbl->last_rand = now;
		for( p = &tbl->parms; p; p = p->next )
			p->reachable_time = neigh_rand_reach_time( p->base_reachable_time );
	}

	np = &tbl->hash_buckets[ tbl->hash_chain_gc ];
	tbl->hash_chain_gc = ( (tbl->hash_chain_gc + 1) & tbl->hash_mask );

	while ((n = *np) != NULL) {
		unsigned int state;

		write_lock(&n->lock);
		state = n->nud_state;
		if (state & (NUD_PERMANENT | NUD_IN_TIMER)) {
			write_unlock(&n->lock);
			goto next_elt;
		}

		if (time_before(n->used, n->confirmed))
			n->used = n->confirmed;

		PR_DEBUG( "refcnt: %d\n", atomic_read(&n->refcnt) );
		if (atomic_read(&n->refcnt) == 1 && (state == NUD_FAILED ||
								time_after(now, n->used + n->parms->gc_staletime))) {
			*np = n->next;
			n->dead = 1;
			write_unlock( &n->lock );
			myneigh_release( n );
			continue;
		}
		write_unlock(&n->lock);

next_elt:
		np = &n->next;
	}