path: root/net/ipv6/ip6_fib.c

/*
 *	Linux INET6 implementation 
 *	Forwarding Information Database
 *
 *	Authors:
 *	Pedro Roque		<roque@di.fc.ul.pt>	
 *
 *	$Id: ip6_fib.c,v 1.25 2001/10/31 21:55:55 davem Exp $
 *
 *	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.
 */

/*
 * 	Changes:
 * 	Yuji SEKIYA @USAGI:	Support default route on router node;
 * 				remove ip6_null_entry from the top of
 * 				routing table.
 */
#include <linux/config.h>
#include <linux/errno.h>
#include <linux/types.h>
#include <linux/net.h>
#include <linux/route.h>
#include <linux/netdevice.h>
#include <linux/in6.h>
#include <linux/init.h>

#ifdef 	CONFIG_PROC_FS
#include <linux/proc_fs.h>
#endif

#include <net/ipv6.h>
#include <net/ndisc.h>
#include <net/addrconf.h>

#include <net/ip6_fib.h>
#include <net/ip6_route.h>

#define RT6_DEBUG 2

#if RT6_DEBUG >= 3
#define RT6_TRACE(x...) printk(KERN_DEBUG x)
#else
#define RT6_TRACE(x...) do { ; } while (0)
#endif

struct rt6_statistics	rt6_stats;

static kmem_cache_t * fib6_node_kmem;

enum fib_walk_state_t
{
#ifdef CONFIG_IPV6_SUBTREES
	FWS_S,
#endif
	FWS_L,
	FWS_R,
	FWS_C,
	FWS_U
};

struct fib6_cleaner_t
{
	struct fib6_walker_t w;
	int (*func)(struct rt6_info *, void *arg);
	void *arg;
};

DEFINE_RWLOCK(fib6_walker_lock);


#ifdef CONFIG_IPV6_SUBTREES
#define FWS_INIT FWS_S
#define SUBTREE(fn) ((fn)->subtree)
#else
#define FWS_INIT FWS_L
#define SUBTREE(fn) NULL
#endif

static void fib6_prune_clones(struct fib6_node *fn, struct rt6_info *rt);
static struct fib6_node * fib6_repair_tree(struct fib6_node *fn);

/*
 *	A routing update causes an increase of the serial number on the
 *	affected subtree. This allows for cached routes to be asynchronously
 *	tested when modifications are made to the destination cache as a
 *	result of redirects, path MTU changes, etc.
 */

static __u32 rt_sernum;

static struct timer_list ip6_fib_timer = TIMER_INITIALIZER(fib6_run_gc, 0, 0);

struct fib6_walker_t fib6_walker_list = {
	.prev	= &fib6_walker_list,
	.next	= &fib6_walker_list, 
};

#define FOR_WALKERS(w) for ((w)=fib6_walker_list.next; (w) != &fib6_walker_list; (w)=(w)->next)

static __inline__ u32 fib6_new_sernum(void)
{
	u32 n = ++rt_sernum;
	if ((__s32)n <= 0)
		rt_sernum = n = 1;
	return n;
}

/*
 *	Auxiliary address test functions for the radix tree.
 *
 *	These assume a 32bit processor (although it will work on 
 *	64bit processors)
 */

/*
 *	test bit
 */

static __inline__ int addr_bit_set(void *token, int fn_bit)
{
	__u32 *addr = token;

	return htonl(1 << ((~fn_bit)&0x1F)) & addr[fn_bit>>5];
}

/*
 *	find the first different bit between two addresses
 *	length of address must be a multiple of 32bits
 */

static __inline__ int addr_diff(void *token1, void *token2, int addrlen)
{
	__u32 *a1 = token1;
	__u32 *a2 = token2;
	int i;

	addrlen >>= 2;

	for (i = 0; i < addrlen; i++) {
		__u32 xb;

		xb = a1[i] ^ a2[i];

		if (xb) {
			int j = 31;

			xb = ntohl(xb);

			while ((