ip6_fib.c

ipv6地址转换器

 *	Routing tree lookup
 *
 */

struct lookup_args {
	int		offset;		/* key offset on rt6_info	*/
	struct in6_addr	*addr;		/* search key			*/
};

static struct fib6_node * fib6_lookup_1(struct fib6_node *root,
					struct lookup_args *args)
{
	struct fib6_node *fn;
	int dir;

	/*
	 *	Descend on a tree
	 */

	fn = root;

	for (;;) {
		struct fib6_node *next;

		dir = addr_bit_set(args->addr, fn->fn_bit);

		next = dir ? fn->right : fn->left;

		if (next) {
			fn = next;
			continue;
		}

		break;
	}

	while ((fn->fn_flags & RTN_ROOT) == 0) {
#ifdef CONFIG_IPV6_SUBTREES
		if (fn->subtree) {
			struct fib6_node *st;
			struct lookup_args *narg;

			narg = args + 1;

			if (narg->addr) {
				st = fib6_lookup_1(fn->subtree, narg);

				if (!(st->fn_flags & RTN_ROOT))
				{
					return st;
				}
			}
		}
#endif

		if (fn->fn_flags & RTN_RTINFO) {
			struct rt6key *key;

			key = (struct rt6key *) ((u8 *) fn->leaf +
						 args->offset);

			if (addr_match(&key->addr, args->addr, key->plen))
				return fn;
		}

		fn = fn->parent;
	}

	return NULL;
}

struct fib6_node * fib6_lookup(struct fib6_node *root, struct in6_addr *daddr,
			       struct in6_addr *saddr)
{
	struct lookup_args args[2];
	struct rt6_info *rt = NULL;
	struct fib6_node *fn;

	args[0].offset = (u8*) &rt->rt6i_dst - (u8*) rt;
	args[0].addr = daddr;

#ifdef CONFIG_IPV6_SUBTREES
	args[1].offset = (u8*) &rt->rt6i_src - (u8*) rt;
	args[1].addr = saddr;
#endif

	fn = fib6_lookup_1(root, args);

	if (fn == NULL)
		fn = root;

	return fn;
}

/*
 *	Get node with sepciafied destination prefix (and source prefix,
 *	if subtrees are used)
 */


static struct fib6_node * fib6_locate_1(struct fib6_node *root,
					struct in6_addr *addr,
					int plen, int offset)
{
	struct fib6_node *fn;

	for (fn = root; fn ; ) {
		struct rt6key *key = (struct rt6key *)((u8 *)fn->leaf + offset);

		/*
		 *	Prefix match
		 */
		if (plen < fn->fn_bit ||
		    !addr_match(&key->addr, addr, fn->fn_bit))
			return NULL;

		if (plen == fn->fn_bit)
			return fn;

		/*
		 *	We have more bits to go
		 */
		if (addr_bit_set(addr, fn->fn_bit))
			fn = fn->right;
		else
			fn = fn->left;
	}
	return NULL;
}

struct fib6_node * fib6_locate(struct fib6_node *root,
			       struct in6_addr *daddr, int dst_len,
			       struct in6_addr *saddr, int src_len)
{
	struct rt6_info *rt = NULL;
	struct fib6_node *fn;

	fn = fib6_locate_1(root, daddr, dst_len,
			   (u8*) &rt->rt6i_dst - (u8*) rt);

#ifdef CONFIG_IPV6_SUBTREES
	if (src_len) {
		BUG_TRAP(saddr!=NULL);
		if (fn == NULL)
			fn = fn->subtree;
		if (fn)
			fn = fib6_locate_1(fn, saddr, src_len,
					   (u8*) &rt->rt6i_src - (u8*) rt);
	}
#endif

	if (fn && fn->fn_flags&RTN_RTINFO)
		return fn;

	return NULL;
}


/*
 *	Deletion
 *
 */

static struct rt6_info * fib6_find_prefix(struct fib6_node *fn)
{
	if (fn->fn_flags&RTN_ROOT)
		return &ip6_null_entry;

	while(fn) {
		if(fn->left)
			return fn->left->leaf;

		if(fn->right)
			return fn->right->leaf;

		fn = SUBTREE(fn);
	}
	return NULL;
}

/*
 *	Called to trim the tree of intermediate nodes when possible. "fn"
 *	is the node we want to try and remove.
 */

static void fib6_repair_tree(struct fib6_node *fn)
{
	int children;
	int nstate;
	struct fib6_node *child, *pn;
	struct fib6_walker_t *w;
	int iter = 0;

	for (;;) {
		RT6_TRACE("fixing tree: plen=%d iter=%d\n", fn->fn_bit, iter);
		iter++;

		BUG_TRAP(!(fn->fn_flags&RTN_RTINFO));
		BUG_TRAP(!(fn->fn_flags&RTN_TL_ROOT));
		BUG_TRAP(fn->leaf==NULL);

		children = 0;
		child = NULL;
		if (fn->right) child = fn->right, children |= 1;
		if (fn->left) child = fn->left, children |= 2;

		if (children == 3 || SUBTREE(fn) 
#ifdef CONFIG_IPV6_SUBTREES
		    /* Subtree root (i.e. fn) may have one child */
		    || (children && fn->fn_flags&RTN_ROOT)
#endif
		    ) {
			fn->leaf = fib6_find_prefix(fn);
#if RT6_DEBUG >= 2
			if (fn->leaf==NULL) {
				BUG_TRAP(fn->leaf);
				fn->leaf = &ip6_null_entry;
			}
#endif
			atomic_inc(&fn->leaf->rt6i_ref);
			return;
		}

		pn = fn->parent;
#ifdef CONFIG_IPV6_SUBTREES
		if (SUBTREE(pn) == fn) {
			BUG_TRAP(fn->fn_flags&RTN_ROOT);
			SUBTREE(pn) = NULL;
			nstate = FWS_L;
		} else {
			BUG_TRAP(!(fn->fn_flags&RTN_ROOT));
#endif
			if (pn->right == fn) pn->right = child;
			else if (pn->left == fn) pn->left = child;
#if RT6_DEBUG >= 2
			else BUG_TRAP(0);
#endif
			if (child)
				child->parent = pn;
			nstate = FWS_R;
#ifdef CONFIG_IPV6_SUBTREES
		}
#endif

		FOR_WALKERS(w) {
			if (child == NULL) {
				if (w->root == fn) {
					w->root = w->node = NULL;
					RT6_TRACE("W %p adjusted by delroot 1\n", w);
				} else if (w->node == fn) {
					RT6_TRACE("W %p adjusted by delnode 1, s=%d/%d\n", w, w->state, nstate);
					w->node = pn;
					w->state = nstate;
				}
			} else {
				if (w->root == fn) {
					w->root = child;
					RT6_TRACE("W %p adjusted by delroot 2\n", w);
				}
				if (w->node == fn) {
					w->node = child;
					if (children&2) {
						RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
						w->state = w->state>=FWS_R ? FWS_U : FWS_INIT;
					} else {
						RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
						w->state = w->state>=FWS_C ? FWS_U : FWS_INIT;
					}
				}
			}
		}

		node_free(fn);
		if (pn->fn_flags&RTN_RTINFO || SUBTREE(pn))
			return;

		rt6_release(pn->leaf);
		pn->leaf = NULL;
		fn = pn;
	}
}

static void fib6_del_route(struct fib6_node *fn, struct rt6_info **rtp)
{
	struct fib6_walker_t *w;
	struct rt6_info *rt = *rtp;

	RT6_TRACE("fib6_del_route\n");

	/* Unlink it */
	*rtp = rt->u.next;
	rt->rt6i_node = NULL;
	rt6_stats.fib_rt_entries--;

	/* Adjust walkers */
	FOR_WALKERS(w) {
		if (w->state == FWS_C && w->leaf == rt) {
			RT6_TRACE("walker %p adjusted by delroute\n", w);
			w->leaf = rt->u.next;
			if (w->leaf == NULL)
				w->state = FWS_U;
		}
	}

	rt->u.next = NULL;

	/* If it was last route, expunge its radix tree node */
	if (fn->leaf == NULL) {
		fn->fn_flags &= ~RTN_RTINFO;
		rt6_stats.fib_route_nodes--;
		fib6_repair_tree(fn);
	}

#ifdef CONFIG_RTNETLINK
	inet6_rt_notify(RTM_DELROUTE, rt);
#endif
	rt6_release(rt);
}

int fib6_del(struct rt6_info *rt)
{
	struct fib6_node *fn = rt->rt6i_node;
	struct rt6_info **rtp;

#if RT6_DEBUG >= 2
	if (rt->u.dst.obsolete>0) {
		BUG_TRAP(rt->u.dst.obsolete>0);
		return -EFAULT;
	}
#endif
	if (fn == NULL || rt == &ip6_null_entry)
		return -ENOENT;

	BUG_TRAP(fn->fn_flags&RTN_RTINFO);

	if (!(rt->rt6i_flags&RTF_CACHE))
		fib6_prune_clones(fn, rt);

	/*
	 *	Walk the leaf entries looking for ourself
	 */

	for (rtp = &fn->leaf; *rtp; rtp = &(*rtp)->u.next) {
		if (*rtp == rt) {
			fib6_del_route(fn, rtp);
			return 0;
		}
	}
	return -ENOENT;
}

/*
 *	Tree transversal function.
 *
 *	Certainly, it is not interrupt safe.
 *	However, it is internally reenterable wrt itself and fib6_add/fib6_del.
 *	It means, that we can modify tree during walking
 *	and use this function for garbage collection, clone pruning,
 *	cleaning tree when a device goes down etc. etc.	
 *
 *	It guarantees that every node will be traversed,
 *	and that it will be traversed only once.
 *
 *	Callback function w->func may return:
 *	0 -> continue walking.
 *	positive value -> walking is suspended (used by tree dumps,
 *	and probably by gc, if it will be split to several slices)
 *	negative value -> terminate walking.
 *
 *	The function itself returns:
 *	0   -> walk is complete.
 *	>0  -> walk is incomplete (i.e. suspended)
 *	<0  -> walk is terminated by an error.
 */

int fib6_walk_continue(struct fib6_walker_t *w)
{
	struct fib6_node *fn, *pn;

	for (;;) {
		fn = w->node;
		if (fn == NULL)
			return 0;

		if (w->prune && fn != w->root &&
		    fn->fn_flags&RTN_RTINFO && w->state < FWS_C) {
			w->state = FWS_C;
			w->leaf = fn->leaf;
		}
		switch (w->state) {
#ifdef CONFIG_IPV6_SUBTREES
		case FWS_S:
			if (SUBTREE(fn)) {
				w->node = SUBTREE(fn);
				continue;
			}
			w->state = FWS_L;
#endif	
		case FWS_L:
			if (fn->left) {
				w->node = fn->left;
				w->state = FWS_INIT;
				continue;
			}
			w->state = FWS_R;
		case FWS_R:
			if (fn->right) {
				w->node = fn->right;
				w->state = FWS_INIT;
				continue;
			}
			w->state = FWS_C;
			w->leaf = fn->leaf;
		case FWS_C:
			if (w->leaf && fn->fn_flags&RTN_RTINFO) {
				int err = w->func(w);
				if (err)
					return err;
				continue;
			}
			w->state = FWS_U;
		case FWS_U:
			if (fn == w->root)
				return 0;
			pn = fn->parent;
			w->node = pn;
#ifdef CONFIG_IPV6_SUBTREES
			if (SUBTREE(pn) == fn) {
				BUG_TRAP(fn->fn_flags&RTN_ROOT);
				w->state = FWS_L;
				continue;
			}
#endif
			if (pn->left == fn) {
				w->state = FWS_R;
				continue;
			}
			if (pn->right == fn) {
				w->state = FWS_C;
				w->leaf = w->node->leaf;
				continue;
			}
#if RT6_DEBUG >= 2
			BUG_TRAP(0);
#endif
		}
	}
}

int fib6_walk(struct fib6_walker_t *w)
{
	int res;

	w->state = FWS_INIT;
	w->node = w->root;

	fib6_walker_link(w);
	res = fib6_walk_continue(w);
	if (res <= 0)
		fib6_walker_unlink(w);
	return res;
}

static int fib6_clean_node(struct fib6_walker_t *w)
{
	int res;
	struct rt6_info *rt;
	struct fib6_cleaner_t *c = (struct fib6_cleaner_t*)w;

	for (rt = w->leaf; rt; rt = rt->u.next) {
		res = c->func(rt, c->arg);
		if (res < 0) {
			w->leaf = rt;
			res = fib6_del(rt);
			if (res) {
#if RT6_DEBUG >= 2
				printk(KERN_DEBUG "fib6_clean_node: del failed: rt=%p@%p err=%d\n", rt, rt->rt6i_node, res);
#endif
				continue;
			}
			return 0;
		}
		BUG_TRAP(res==0);
	}
	w->leaf = rt;
	return 0;
}

/*
 *	Convenient frontend to tree walker.
 *	
 *	func is called on each route.
 *		It may return -1 -> delete this route.
 *		              0  -> continue walking
 *
 *	prune==1 -> only immediate children of node (certainly,
 *	ignoring pure split nodes) will be scanned.
 */

void fib6_clean_tree(struct fib6_node *root,
		     int (*func)(struct rt6_info *, void *arg),
		     int prune, void *arg)
{
	struct fib6_cleaner_t c;

	c.w.root = root;
	c.w.func = fib6_clean_node;
	c.w.prune = prune;
	c.func = func;
	c.arg = arg;

	start_bh_atomic();
	fib6_walk(&c.w);
	end_bh_atomic();
}

static int fib6_prune_clone(struct rt6_info *rt, void *arg)
{
	if (rt->rt6i_flags & RTF_CACHE) {
		RT6_TRACE("pruning clone %p\n", rt);
		return -1;
	}

	return 0;
}

static void fib6_prune_clones(struct fib6_node *fn, struct rt6_info *rt)
{
	fib6_clean_tree(fn, fib6_prune_clone, 1, rt);
}

/*
 *	Garbage collection
 */

static struct fib6_gc_args
{
	int			timeout;
	int			more;
} gc_args;

static int fib6_age(struct rt6_info *rt, void *arg)
{
	unsigned long now = jiffies;

	/* Age clones. Note, that clones are aged out
	   only if they are not in use now.
	 */

	if (rt->rt6i_flags & RTF_CACHE) {
		if (atomic_read(&rt->u.dst.use) == 0 &&
		    (long)(now - rt->u.dst.lastuse) >= gc_args.timeout) {
			RT6_TRACE("aging clone %p\n", rt);
			return -1;
		}
		gc_args.more++;
	}

	/*
	 *	check addrconf expiration here.
	 *	They are expired even if they are in use.
	 */

	if (rt->rt6i_flags&RTF_EXPIRES && rt->rt6i_expires) {
		if ((long)(now - rt->rt6i_expires) > 0) {
			RT6_TRACE("expiring %p\n", rt);
			return -1;
		}
		gc_args.more++;
	}

	return 0;
}

void fib6_run_gc(unsigned long dummy)
{
	if (dummy != ~0UL)
		gc_args.timeout = (int)dummy;
	else
		gc_args.timeout = ip6_rt_gc_interval;

	gc_args.more = 0;

	fib6_clean_tree(&ip6_routing_table, fib6_age, 0, NULL);

	del_timer(&ip6_fib_timer);

	ip6_fib_timer.expires = 0;
	if (gc_args.more) {
		ip6_fib_timer.expires = jiffies + ip6_rt_gc_interval;
		add_timer(&ip6_fib_timer);
	}
}

#ifdef MODULE
void fib6_gc_cleanup(void)
{
	del_timer(&ip6_fib_timer);
}
#endif