/*
- * Linux INET6 implementation
+ * Linux INET6 implementation
* Forwarding Information Database
*
* Authors:
- * Pedro Roque <roque@di.fc.ul.pt>
+ * Pedro Roque <roque@di.fc.ul.pt>
*
* $Id: ip6_fib.c,v 1.25 2001/10/31 21:55:55 davem Exp $
*
struct rt6_statistics rt6_stats;
-static kmem_cache_t * fib6_node_kmem __read_mostly;
+static struct kmem_cache * fib6_node_kmem __read_mostly;
enum fib_walk_state_t
{
static struct fib6_walker_t fib6_walker_list = {
.prev = &fib6_walker_list,
- .next = &fib6_walker_list,
+ .next = &fib6_walker_list,
};
#define FOR_WALKERS(w) for ((w)=fib6_walker_list.next; (w) != &fib6_walker_list; (w)=(w)->next)
/*
* Auxiliary address test functions for the radix tree.
*
- * These assume a 32bit processor (although it will work on
+ * These assume a 32bit processor (although it will work on
* 64bit processors)
*/
{
struct fib6_node *fn;
- if ((fn = kmem_cache_alloc(fib6_node_kmem, GFP_ATOMIC)) != NULL)
- memset(fn, 0, sizeof(struct fib6_node));
+ fn = kmem_cache_zalloc(fib6_node_kmem, GFP_ATOMIC);
return fn;
}
int res;
struct rt6_info *rt;
- for (rt = w->leaf; rt; rt = rt->u.next) {
+ for (rt = w->leaf; rt; rt = rt->u.dst.rt6_next) {
res = rt6_dump_route(rt, w->args);
if (res < 0) {
/* Frame is full, suspend walking */
struct fib6_node *pn = NULL;
struct rt6key *key;
int bit;
- __be32 dir = 0;
+ __be32 dir = 0;
__u32 sernum = fib6_new_sernum();
RT6_TRACE("fib6_add_1\n");
if (plen < fn->fn_bit ||
!ipv6_prefix_equal(&key->addr, addr, fn->fn_bit))
goto insert_above;
-
+
/*
* Exact match ?
*/
-
+
if (plen == fn->fn_bit) {
/* clean up an intermediate node */
if ((fn->fn_flags & RTN_RTINFO) == 0) {
rt6_release(fn->leaf);
fn->leaf = NULL;
}
-
+
fn->fn_sernum = sernum;
-
+
return fn;
}
/*
* We have more bits to go
*/
-
+
/* Try to walk down on tree. */
fn->fn_sernum = sernum;
dir = addr_bit_set(addr, fn->fn_bit);
if (ln == NULL)
return NULL;
ln->fn_bit = plen;
-
+
ln->parent = pn;
ln->fn_sernum = sernum;
insert_above:
/*
- * split since we don't have a common prefix anymore or
+ * split since we don't have a common prefix anymore or
* we have a less significant route.
* we've to insert an intermediate node on the list
* this new node will point to the one we need to create
See comment in __ipv6_addr_diff: bit may be an invalid value,
but if it is >= plen, the value is ignored in any case.
*/
-
+
bit = __ipv6_addr_diff(addr, &key->addr, addrlen);
- /*
- * (intermediate)[in]
+ /*
+ * (intermediate)[in]
* / \
* (new leaf node)[ln] (old node)[fn]
*/
if (plen > bit) {
in = node_alloc();
ln = node_alloc();
-
+
if (in == NULL || ln == NULL) {
if (in)
node_free(in);
return NULL;
}
- /*
- * new intermediate node.
+ /*
+ * new intermediate node.
* RTN_RTINFO will
* be off since that an address that chooses one of
* the branches would not match less specific routes
}
} else { /* plen <= bit */
- /*
+ /*
* (new leaf node)[ln]
* / \
* (old node)[fn] NULL
ln->parent = pn;
ln->fn_sernum = sernum;
-
+
if (dir)
pn->right = ln;
else
fn->leaf == &ip6_null_entry &&
!(rt->rt6i_flags & (RTF_DEFAULT | RTF_ADDRCONF)) ){
fn->leaf = rt;
- rt->u.next = NULL;
+ rt->u.dst.rt6_next = NULL;
goto out;
}
- for (iter = fn->leaf; iter; iter=iter->u.next) {
+ for (iter = fn->leaf; iter; iter=iter->u.dst.rt6_next) {
/*
* Search for duplicates
*/
if (iter->rt6i_metric > rt->rt6i_metric)
break;
- ins = &iter->u.next;
+ ins = &iter->u.dst.rt6_next;
}
+ /* Reset round-robin state, if necessary */
+ if (ins == &fn->leaf)
+ fn->rr_ptr = NULL;
+
/*
* insert node
*/
out:
- rt->u.next = iter;
+ rt->u.dst.rt6_next = iter;
*ins = rt;
rt->rt6i_node = fn;
atomic_inc(&rt->rt6i_ref);
RT6_TRACE("fib6_del_route\n");
/* Unlink it */
- *rtp = rt->u.next;
+ *rtp = rt->u.dst.rt6_next;
rt->rt6i_node = NULL;
rt6_stats.fib_rt_entries--;
rt6_stats.fib_discarded_routes++;
+ /* Reset round-robin state, if necessary */
+ if (fn->rr_ptr == rt)
+ fn->rr_ptr = NULL;
+
/* Adjust walkers */
read_lock(&fib6_walker_lock);
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;
+ w->leaf = rt->u.dst.rt6_next;
if (w->leaf == NULL)
w->state = FWS_U;
}
}
read_unlock(&fib6_walker_lock);
- rt->u.next = NULL;
+ rt->u.dst.rt6_next = NULL;
if (fn->leaf == NULL && fn->fn_flags&RTN_TL_ROOT)
fn->leaf = &ip6_null_entry;
* Walk the leaf entries looking for ourself
*/
- for (rtp = &fn->leaf; *rtp; rtp = &(*rtp)->u.next) {
+ for (rtp = &fn->leaf; *rtp; rtp = &(*rtp)->u.dst.rt6_next) {
if (*rtp == rt) {
fib6_del_route(fn, rtp, info);
return 0;
* 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.
+ * 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.
continue;
}
w->state = FWS_L;
-#endif
+#endif
case FWS_L:
if (fn->left) {
w->node = fn->left;
struct rt6_info *rt;
struct fib6_cleaner_t *c = (struct fib6_cleaner_t*)w;
- for (rt = w->leaf; rt; rt = rt->u.next) {
+ for (rt = w->leaf; rt; rt = rt->u.dst.rt6_next) {
res = c->func(rt, c->arg);
if (res < 0) {
w->leaf = rt;
/*
* Convenient frontend to tree walker.
- *
+ *
* func is called on each route.
* It may return -1 -> delete this route.
* 0 -> continue walking