fib_hash.c

嵌入式系统设计与实验教材二源码linux内核移植与编译

/*
 * INET		An implementation of the TCP/IP protocol suite for the LINUX
 *		operating system.  INET is implemented using the  BSD Socket
 *		interface as the means of communication with the user level.
 *
 *		IPv4 FIB: lookup engine and maintenance routines.
 *
 * Version:	$Id: fib_hash.c,v 1.13 2001/10/31 21:55:54 davem Exp $
 *
 * Authors:	Alexey Kuznetsov, <[e-mail]>
 *
 *		This program is free software; you can redistribute it and/or
 *		modify it under the terms of the GNU General Public License
 *		as published by the Free Software Foundation; either version
 *		2 of the License, or (at your option) any later version.
 */

#include <linux/config.h>
#include <asm/uaccess.h>
#include <asm/system.h>
#include <asm/bitops.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/sched.h>
#include <linux/mm.h>
#include <linux/string.h>
#include <linux/socket.h>
#include <linux/sockios.h>
#include <linux/errno.h>
#include <linux/in.h>
#include <linux/inet.h>
#include <linux/netdevice.h>
#include <linux/if_arp.h>
#include <linux/proc_fs.h>
#include <linux/skbuff.h>
#include <linux/netlink.h>
#include <linux/init.h>

#include <net/ip.h>
#include <net/protocol.h>
#include <net/route.h>
#include <net/tcp.h>
#include <net/sock.h>
#include <net/ip_fib.h>

#define FTprint(a...)
/*
   printk(KERN_DEBUG a)
 */

static kmem_cache_t * fn_hash_kmem;

/*
   These bizarre types are just to force strict type checking.
   When I reversed order of bytes and changed to natural mask lengths,
   I forgot to make fixes in several places. Now I am lazy to return
   it back.
 */

typedef struct {
	u32	datum;
} fn_key_t;

typedef struct {
	u32	datum;
} fn_hash_idx_t;

struct fib_node
{
	struct fib_node		*fn_next;
	struct fib_info		*fn_info;
#define FIB_INFO(f)	((f)->fn_info)
	fn_key_t		fn_key;
	u8			fn_tos;
	u8			fn_type;
	u8			fn_scope;
	u8			fn_state;
};

#define FN_S_ZOMBIE	1
#define FN_S_ACCESSED	2

static int fib_hash_zombies;

struct fn_zone
{
	struct fn_zone	*fz_next;	/* Next not empty zone	*/
	struct fib_node	**fz_hash;	/* Hash table pointer	*/
	int		fz_nent;	/* Number of entries	*/

	int		fz_divisor;	/* Hash divisor		*/
	u32		fz_hashmask;	/* (1<<fz_divisor) - 1	*/
#define FZ_HASHMASK(fz)	((fz)->fz_hashmask)

	int		fz_order;	/* Zone order		*/
	u32		fz_mask;
#define FZ_MASK(fz)	((fz)->fz_mask)
};

/* NOTE. On fast computers evaluation of fz_hashmask and fz_mask
   can be cheaper than memory lookup, so that FZ_* macros are used.
 */

struct fn_hash
{
	struct fn_zone	*fn_zones[33];
	struct fn_zone	*fn_zone_list;
};

static __inline__ fn_hash_idx_t fn_hash(fn_key_t key, struct fn_zone *fz)
{
	u32 h = ntohl(key.datum)>>(32 - fz->fz_order);
	h ^= (h>>20);
	h ^= (h>>10);
	h ^= (h>>5);
	h &= FZ_HASHMASK(fz);
	return *(fn_hash_idx_t*)&h;
}

#define fz_key_0(key)		((key).datum = 0)
#define fz_prefix(key,fz)	((key).datum)

static __inline__ fn_key_t fz_key(u32 dst, struct fn_zone *fz)
{
	fn_key_t k;
	k.datum = dst & FZ_MASK(fz);
	return k;
}

static __inline__ struct fib_node ** fz_chain_p(fn_key_t key, struct fn_zone *fz)
{
	return &fz->fz_hash[fn_hash(key, fz).datum];
}

static __inline__ struct fib_node * fz_chain(fn_key_t key, struct fn_zone *fz)
{
	return fz->fz_hash[fn_hash(key, fz).datum];
}

extern __inline__ int fn_key_eq(fn_key_t a, fn_key_t b)
{
	return a.datum == b.datum;
}

extern __inline__ int fn_key_leq(fn_key_t a, fn_key_t b)
{
	return a.datum <= b.datum;
}

static rwlock_t fib_hash_lock = RW_LOCK_UNLOCKED;

#define FZ_MAX_DIVISOR 1024

#ifdef CONFIG_IP_ROUTE_LARGE_TABLES

/* The fib hash lock must be held when this is called. */
static __inline__ void fn_rebuild_zone(struct fn_zone *fz,
				       struct fib_node **old_ht,
				       int old_divisor)
{
	int i;
	struct fib_node *f, **fp, *next;

	for (i=0; i<old_divisor; i++) {
		for (f=old_ht[i]; f; f=next) {
			next = f->fn_next;
			for (fp = fz_chain_p(f->fn_key, fz);
			     *fp && fn_key_leq((*fp)->fn_key, f->fn_key);
			     fp = &(*fp)->fn_next)
				/* NONE */;
			f->fn_next = *fp;
			*fp = f;
		}
	}
}

static void fn_rehash_zone(struct fn_zone *fz)
{
	struct fib_node **ht, **old_ht;
	int old_divisor, new_divisor;
	u32 new_hashmask;
		
	old_divisor = fz->fz_divisor;

	switch (old_divisor) {
	case 16:
		new_divisor = 256;
		new_hashmask = 0xFF;
		break;
	case 256:
		new_divisor = 1024;
		new_hashmask = 0x3FF;
		break;
	default:
		printk(KERN_CRIT "route.c: bad divisor %d!\n", old_divisor);
		return;
	}
#if RT_CACHE_DEBUG >= 2
	printk("fn_rehash_zone: hash for zone %d grows from %d\n", fz->fz_order, old_divisor);
#endif

	ht = kmalloc(new_divisor*sizeof(struct fib_node*), GFP_KERNEL);

	if (ht)	{
		memset(ht, 0, new_divisor*sizeof(struct fib_node*));
		write_lock_bh(&fib_hash_lock);
		old_ht = fz->fz_hash;
		fz->fz_hash = ht;
		fz->fz_hashmask = new_hashmask;
		fz->fz_divisor = new_divisor;
		fn_rebuild_zone(fz, old_ht, old_divisor);
		write_unlock_bh(&fib_hash_lock);
		kfree(old_ht);
	}
}
#endif /* CONFIG_IP_ROUTE_LARGE_TABLES */

static void fn_free_node(struct fib_node * f)
{
	fib_release_info(FIB_INFO(f));
	kmem_cache_free(fn_hash_kmem, f);
}


static struct fn_zone *
fn_new_zone(struct fn_hash *table, int z)
{
	int i;
	struct fn_zone *fz = kmalloc(sizeof(struct fn_zone), GFP_KERNEL);
	if (!fz)
		return NULL;

	memset(fz, 0, sizeof(struct fn_zone));
	if (z) {
		fz->fz_divisor = 16;
		fz->fz_hashmask = 0xF;
	} else {
		fz->fz_divisor = 1;
		fz->fz_hashmask = 0;
	}
	fz->fz_hash = kmalloc(fz->fz_divisor*sizeof(struct fib_node*), GFP_KERNEL);
	if (!fz->fz_hash) {
		kfree(fz);
		return NULL;
	}
	memset(fz->fz_hash, 0, fz->fz_divisor*sizeof(struct fib_node*));
	fz->fz_order = z;
	fz->fz_mask = inet_make_mask(z);

	/* Find the first not empty zone with more specific mask */
	for (i=z+1; i<=32; i++)
		if (table->fn_zones[i])
			break;
	write_lock_bh(&fib_hash_lock);
	if (i>32) {
		/* No more specific masks, we are the first. */
		fz->fz_next = table->fn_zone_list;
		table->fn_zone_list = fz;
	} else {
		fz->fz_next = table->fn_zones[i]->fz_next;
		table->fn_zones[i]->fz_next = fz;
	}
	table->fn_zones[z] = fz;
	write_unlock_bh(&fib_hash_lock);
	return fz;
}

static int
fn_hash_lookup(struct fib_table *tb, const struct rt_key *key, struct fib_result *res)
{
	int err;
	struct fn_zone *fz;
	struct fn_hash *t = (struct fn_hash*)tb->tb_data;

	read_lock(&fib_hash_lock);
	for (fz = t->fn_zone_list; fz; fz = fz->fz_next) {
		struct fib_node *f;
		fn_key_t k = fz_key(key->dst, fz);

		for (f = fz_chain(k, fz); f; f = f->fn_next) {
			if (!fn_key_eq(k, f->fn_key)) {
				if (fn_key_leq(k, f->fn_key))
					break;
				else
					continue;
			}
#ifdef CONFIG_IP_ROUTE_TOS
			if (f->fn_tos && f->fn_tos != key->tos)
				continue;
#endif
			f->fn_state |= FN_S_ACCESSED;

			if (f->fn_state&FN_S_ZOMBIE)
				continue;
			if (f->fn_scope < key->scope)
				continue;

			err = fib_semantic_match(f->fn_type, FIB_INFO(f), key, res);
			if (err == 0) {
				res->type = f->fn_type;
				res->scope = f->fn_scope;
				res->prefixlen = fz->fz_order;
				goto out;
			}
			if (err < 0)
				goto out;
		}
	}
	err = 1;
out:
	read_unlock(&fib_hash_lock);
	return err;
}

static int fn_hash_last_dflt=-1;

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

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

static void
fn_hash_select_default(struct fib_table *tb, const struct rt_key *key, struct fib_result *res)
{
	int order, last_idx;
	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(&fib_hash_lock);
	for (f = fz->fz_hash[0]; f; f = f->fn_next) {
		struct fib_info *next_fi = FIB_INFO(f);

		if ((f->fn_state&FN_S_ZOMBIE) ||
		    f->fn_scope != res->scope ||
		    f->fn_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;
		f->fn_state |= FN_S_ACCESSED;

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

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

	if (!fib_detect_death(fi, order, &last_resort, &last_idx)) {
		if (res->fi)
			fib_info_put(res->fi);
		res->fi = fi;
		atomic_inc(&fi->fib_clntref);
		fn_hash_last_dflt = order;
		goto out;
	}

	if (last_idx >= 0) {
		if (res->fi)
			fib_info_put(res->fi);
		res->fi = last_resort;
		if (last_resort)
			atomic_inc(&last_resort->fib_clntref);
	}
	fn_hash_last_dflt = last_idx;
out:
	read_unlock(&fib_hash_lock);
}

#define FIB_SCAN(f, fp) \
for ( ; ((f) = *(fp)) != NULL; (fp) = &(f)->fn_next)

#define FIB_SCAN_KEY(f, fp, key) \
for ( ; ((f) = *(fp)) != NULL && fn_key_eq((f)->fn_key, (key)); (fp) = &(f)->fn_next)

#ifndef CONFIG_IP_ROUTE_TOS
#define FIB_SCAN_TOS(f, fp, key, tos) FIB_SCAN_KEY(f, fp, key)
#else
#define FIB_SCAN_TOS(f, fp, key, tos) \
for ( ; ((f) = *(fp)) != NULL && fn_key_eq((f)->fn_key, (key)) && \
     (f)->fn_tos == (tos) ; (fp) = &(f)->fn_next)
#endif


static void rtmsg_fib(int, struct fib_node*, int, int,
		      struct nlmsghdr *n,
		      struct netlink_skb_parms *);

static int
fn_hash_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
		struct nlmsghdr *n, struct netlink_skb_parms *req)
{
	struct fn_hash *table = (struct fn_hash*)tb->tb_data;
	struct fib_node *new_f, *f, **fp, **del_fp;
	struct fn_zone *fz;
	struct fib_info *fi;

	int z = r->rtm_dst_len;
	int type = r->rtm_type;
#ifdef CONFIG_IP_ROUTE_TOS
	u8 tos = r->rtm_tos;
#endif
	fn_key_t key;
	int err;

FTprint("tb(%d)_insert: %d %08x/%d %d %08x\n", tb->tb_id, r->rtm_type, rta->rta_dst ?
*(u32*)rta->rta_dst : 0, z, rta->rta_oif ? *rta->rta_oif : -1,
rta->rta_prefsrc ? *(u32*)rta->rta_prefsrc : 0);
	if (z > 32)
		return -EINVAL;
	fz = table->fn_zones[z];
	if (!fz && !(fz = fn_new_zone(table, z)))
		return -ENOBUFS;

	fz_key_0(key);
	if (rta->rta_dst) {
		u32 dst;
		memcpy(&dst, rta->rta_dst, 4);