/*
* 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 __read_mostly;
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 DEFINE_TIMER(ip6_fib_timer, 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];
}
static __inline__ struct fib6_node * node_alloc(void)
{
struct fib6_node *fn;
if ((fn = kmem_cache_alloc(fib6_node_kmem, SLAB_ATOMIC)) != NULL)
memset(fn, 0, sizeof(struct fib6_node));
return fn;
}
static __inline__ void node_free(struct fib6_node * fn)
{
kmem_cache_free(fib6_node_kmem, fn);
}
static __inline__ void rt6_release(struct rt6_info *rt)
{
if (atomic_dec_and_test(&rt->rt6i_ref))
dst_free(&rt->u.dst);
}
/*
* Routing Table
*
* return the appropriate node for a routing tree "add" operation
* by either creating and inserting or by returning an existing
* node.
*/
static struct fib6_node * fib6_add_1(struct fib6_node *root, void *addr,
int addrlen, int plen,
int offset)
{
struct fib6_node *fn, *in, *ln;
struct fib6_node