* Robert Olsson <robert.olsson@its.uu.se> Uppsala Universitet
* & Swedish University of Agricultural Sciences.
*
- * Jens Laas <jens.laas@data.slu.se> Swedish University of
+ * Jens Laas <jens.laas@data.slu.se> Swedish University of
* Agricultural Sciences.
- *
+ *
* Hans Liss <hans.liss@its.uu.se> Uppsala Universitet
*
* This work is based on the LPC-trie which is originally descibed in:
- *
+ *
* An experimental study of compression methods for dynamic tries
* Stefan Nilsson and Matti Tikkanen. Algorithmica, 33(1):19-33, 2002.
* http://www.nada.kth.se/~snilsson/public/papers/dyntrie2/
static struct tnode *halve(struct trie *t, struct tnode *tn);
static void tnode_free(struct tnode *tn);
-static kmem_cache_t *fn_alias_kmem __read_mostly;
+static struct kmem_cache *fn_alias_kmem __read_mostly;
static struct trie *trie_local = NULL, *trie_main = NULL;
}
/*
- To understand this stuff, an understanding of keys and all their bits is
- necessary. Every node in the trie has a key associated with it, but not
+ To understand this stuff, an understanding of keys and all their bits is
+ necessary. Every node in the trie has a key associated with it, but not
all of the bits in that key are significant.
Consider a node 'n' and its parent 'tp'.
- If n is a leaf, every bit in its key is significant. Its presence is
- necessitated by path compression, since during a tree traversal (when
- searching for a leaf - unless we are doing an insertion) we will completely
- ignore all skipped bits we encounter. Thus we need to verify, at the end of
- a potentially successful search, that we have indeed been walking the
+ If n is a leaf, every bit in its key is significant. Its presence is
+ necessitated by path compression, since during a tree traversal (when
+ searching for a leaf - unless we are doing an insertion) we will completely
+ ignore all skipped bits we encounter. Thus we need to verify, at the end of
+ a potentially successful search, that we have indeed been walking the
correct key path.
- Note that we can never "miss" the correct key in the tree if present by
- following the wrong path. Path compression ensures that segments of the key
- that are the same for all keys with a given prefix are skipped, but the
- skipped part *is* identical for each node in the subtrie below the skipped
- bit! trie_insert() in this implementation takes care of that - note the
+ Note that we can never "miss" the correct key in the tree if present by
+ following the wrong path. Path compression ensures that segments of the key
+ that are the same for all keys with a given prefix are skipped, but the
+ skipped part *is* identical for each node in the subtrie below the skipped
+ bit! trie_insert() in this implementation takes care of that - note the
call to tkey_sub_equals() in trie_insert().
- if n is an internal node - a 'tnode' here, the various parts of its key
+ if n is an internal node - a 'tnode' here, the various parts of its key
have many different meanings.
- Example:
+ Example:
_________________________________________________________________
| i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
-----------------------------------------------------------------
- 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
+ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
_________________________________________________________________
| C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
n->pos = 15
n->bits = 4
- First, let's just ignore the bits that come before the parent tp, that is
- the bits from 0 to (tp->pos-1). They are *known* but at this point we do
+ First, let's just ignore the bits that come before the parent tp, that is
+ the bits from 0 to (tp->pos-1). They are *known* but at this point we do
not use them for anything.
The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
- index into the parent's child array. That is, they will be used to find
+ index into the parent's child array. That is, they will be used to find
'n' among tp's children.
The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
for the node n.
- All the bits we have seen so far are significant to the node n. The rest
+ All the bits we have seen so far are significant to the node n. The rest
of the bits are really not needed or indeed known in n->key.
- The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
+ The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
n's child array, and will of course be different for each child.
-
+
The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
at this point.
static int halve_threshold = 25;
static int inflate_threshold = 50;
static int halve_threshold_root = 15;
-static int inflate_threshold_root = 25;
+static int inflate_threshold_root = 25;
static void __alias_free_mem(struct rcu_head *head)
struct leaf *l = (struct leaf *) tn;
call_rcu_bh(&l->rcu, __leaf_free_rcu);
}
- else
+ else
call_rcu(&tn->rcu, __tnode_free_rcu);
}
int inflate_threshold_use;
int halve_threshold_use;
- if (!tn)
+ if (!tn)
return NULL;
pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
if(!tn->parent)
inflate_threshold_use = inflate_threshold_root;
- else
+ else
inflate_threshold_use = inflate_threshold;
err = 0;
if(!tn->parent)
halve_threshold_use = halve_threshold_root;
- else
+ else
halve_threshold_use = halve_threshold;
err = 0;
right = tnode_new(inode->key|m, inode->pos + 1,
inode->bits - 1);
- if (!right) {
+ if (!right) {
tnode_free(left);
goto nomem;
- }
+ }
put_child(t, tn, 2*i, (struct node *) left);
put_child(t, tn, 2*i+1, (struct node *) right);
static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
{
- struct leaf_info *li = NULL, *last = NULL;
- struct hlist_node *node;
+ struct leaf_info *li = NULL, *last = NULL;
+ struct hlist_node *node;
- if (hlist_empty(head)) {
- hlist_add_head_rcu(&new->hlist, head);
- } else {
- hlist_for_each_entry(li, node, head, hlist) {
- if (new->plen > li->plen)
- break;
+ if (hlist_empty(head)) {
+ hlist_add_head_rcu(&new->hlist, head);
+ } else {
+ hlist_for_each_entry(li, node, head, hlist) {
+ if (new->plen > li->plen)
+ break;
- last = li;
- }
- if (last)
- hlist_add_after_rcu(&last->hlist, &new->hlist);
- else
- hlist_add_before_rcu(&new->hlist, &li->hlist);
- }
+ last = li;
+ }
+ if (last)
+ hlist_add_after_rcu(&last->hlist, &new->hlist);
+ else
+ hlist_add_before_rcu(&new->hlist, &li->hlist);
+ }
}
/* rcu_read_lock needs to be hold by caller from readside */
return fa_head;
}
-static int
-fn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
- struct nlmsghdr *nlhdr, struct netlink_skb_parms *req)
+static int fn_trie_insert(struct fib_table *tb, struct fib_config *cfg)
{
struct trie *t = (struct trie *) tb->tb_data;
struct fib_alias *fa, *new_fa;
struct list_head *fa_head = NULL;
struct fib_info *fi;
- int plen = r->rtm_dst_len;
- int type = r->rtm_type;
- u8 tos = r->rtm_tos;
+ int plen = cfg->fc_dst_len;
+ u8 tos = cfg->fc_tos;
u32 key, mask;
int err;
struct leaf *l;
if (plen > 32)
return -EINVAL;
- key = 0;
- if (rta->rta_dst)
- memcpy(&key, rta->rta_dst, 4);
-
- key = ntohl(key);
+ key = ntohl(cfg->fc_dst);
pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
key = key & mask;
- fi = fib_create_info(r, rta, nlhdr, &err);
-
- if (!fi)
+ fi = fib_create_info(cfg);
+ if (IS_ERR(fi)) {
+ err = PTR_ERR(fi);
goto err;
+ }
l = fib_find_node(t, key);
fa = NULL;
struct fib_alias *fa_orig;
err = -EEXIST;
- if (nlhdr->nlmsg_flags & NLM_F_EXCL)
+ if (cfg->fc_nlflags & NLM_F_EXCL)
goto out;
- if (nlhdr->nlmsg_flags & NLM_F_REPLACE) {
+ if (cfg->fc_nlflags & NLM_F_REPLACE) {
struct fib_info *fi_drop;
u8 state;
err = -ENOBUFS;
- new_fa = kmem_cache_alloc(fn_alias_kmem, SLAB_KERNEL);
+ new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
if (new_fa == NULL)
goto out;
fi_drop = fa->fa_info;
new_fa->fa_tos = fa->fa_tos;
new_fa->fa_info = fi;
- new_fa->fa_type = type;
- new_fa->fa_scope = r->rtm_scope;
+ new_fa->fa_type = cfg->fc_type;
+ new_fa->fa_scope = cfg->fc_scope;
state = fa->fa_state;
new_fa->fa_state &= ~FA_S_ACCESSED;
break;
if (fa->fa_info->fib_priority != fi->fib_priority)
break;
- if (fa->fa_type == type &&
- fa->fa_scope == r->rtm_scope &&
+ if (fa->fa_type == cfg->fc_type &&
+ fa->fa_scope == cfg->fc_scope &&
fa->fa_info == fi) {
goto out;
}
}
- if (!(nlhdr->nlmsg_flags & NLM_F_APPEND))
+ if (!(cfg->fc_nlflags & NLM_F_APPEND))
fa = fa_orig;
}
err = -ENOENT;
- if (!(nlhdr->nlmsg_flags & NLM_F_CREATE))
+ if (!(cfg->fc_nlflags & NLM_F_CREATE))
goto out;
err = -ENOBUFS;
- new_fa = kmem_cache_alloc(fn_alias_kmem, SLAB_KERNEL);
+ new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
if (new_fa == NULL)
goto out;
new_fa->fa_info = fi;
new_fa->fa_tos = tos;
- new_fa->fa_type = type;
- new_fa->fa_scope = r->rtm_scope;
+ new_fa->fa_type = cfg->fc_type;
+ new_fa->fa_scope = cfg->fc_scope;
new_fa->fa_state = 0;
/*
* Insert new entry to the list.
(fa ? &fa->fa_list : fa_head));
rt_cache_flush(-1);
- rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id, nlhdr, req);
+ rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
+ &cfg->fc_nlinfo);
succeeded:
return 0;
return 1;
}
-static int
-fn_trie_delete(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
- struct nlmsghdr *nlhdr, struct netlink_skb_parms *req)
+static int fn_trie_delete(struct fib_table *tb, struct fib_config *cfg)
{
struct trie *t = (struct trie *) tb->tb_data;
u32 key, mask;
- int plen = r->rtm_dst_len;
- u8 tos = r->rtm_tos;
+ int plen = cfg->fc_dst_len;
+ u8 tos = cfg->fc_tos;
struct fib_alias *fa, *fa_to_delete;
struct list_head *fa_head;
struct leaf *l;
struct leaf_info *li;
-
if (plen > 32)
return -EINVAL;
- key = 0;
- if (rta->rta_dst)
- memcpy(&key, rta->rta_dst, 4);
-
- key = ntohl(key);
+ key = ntohl(cfg->fc_dst);
mask = ntohl(inet_make_mask(plen));
if (key & ~mask)
if (fa->fa_tos != tos)
break;
- if ((!r->rtm_type ||
- fa->fa_type == r->rtm_type) &&
- (r->rtm_scope == RT_SCOPE_NOWHERE ||
- fa->fa_scope == r->rtm_scope) &&
- (!r->rtm_protocol ||
- fi->fib_protocol == r->rtm_protocol) &&
- fib_nh_match(r, nlhdr, rta, fi) == 0) {
+ if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
+ (cfg->fc_scope == RT_SCOPE_NOWHERE ||
+ fa->fa_scope == cfg->fc_scope) &&
+ (!cfg->fc_protocol ||
+ fi->fib_protocol == cfg->fc_protocol) &&
+ fib_nh_match(cfg, fi) == 0) {
fa_to_delete = fa;
break;
}
return -ESRCH;
fa = fa_to_delete;
- rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id, nlhdr, req);
+ rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
+ &cfg->fc_nlinfo);
l = fib_find_node(t, key);
li = find_leaf_info(l, plen);
/* Decend if tnode */
while (IS_TNODE(c)) {
p = (struct tnode *) c;
- idx = 0;
+ idx = 0;
/* Rightmost non-NULL branch */
if (p && IS_TNODE(p))
int i, s_i;
struct fib_alias *fa;
- u32 xkey = htonl(key);
+ __be32 xkey = htonl(key);
s_i = cb->args[4];
i = 0;
tb->tb_id,
fa->fa_type,
fa->fa_scope,
- &xkey,
+ xkey,
plen,
fa->fa_tos,
fa->fa_info, 0) < 0) {
unsigned cindex = iter->index;
struct tnode *p;
+ /* A single entry routing table */
+ if (!tn)
+ return NULL;
+
pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
iter->tnode, iter->index, iter->depth);
rescan:
if(!iter)
return NULL;
- if (n && IS_TNODE(n)) {
- iter->tnode = (struct tnode *) n;
- iter->trie = t;
- iter->index = 0;
- iter->depth = 1;
+ if (n) {
+ if (IS_TNODE(n)) {
+ iter->tnode = (struct tnode *) n;
+ iter->trie = t;
+ iter->index = 0;
+ iter->depth = 1;
+ } else {
+ iter->tnode = NULL;
+ iter->trie = t;
+ iter->index = 0;
+ iter->depth = 0;
+ }
return n;
}
return NULL;
if (v == SEQ_START_TOKEN)
return 0;
+ if (!NODE_PARENT(n)) {
+ if (iter->trie == trie_local)
+ seq_puts(seq, "<local>:\n");
+ else
+ seq_puts(seq, "<main>:\n");
+ }
+
if (IS_TNODE(n)) {
struct tnode *tn = (struct tnode *) n;
- t_key prf = ntohl(MASK_PFX(tn->key, tn->pos));
+ __be32 prf = htonl(MASK_PFX(tn->key, tn->pos));
- if (!NODE_PARENT(n)) {
- if (iter->trie == trie_local)
- seq_puts(seq, "<local>:\n");
- else
- seq_puts(seq, "<main>:\n");
- }
seq_indent(seq, iter->depth-1);
seq_printf(seq, " +-- %d.%d.%d.%d/%d %d %d %d\n",
- NIPQUAD(prf), tn->pos, tn->bits, tn->full_children,
+ NIPQUAD(prf), tn->pos, tn->bits, tn->full_children,
tn->empty_children);
-
+
} else {
struct leaf *l = (struct leaf *) n;
int i;
- u32 val = ntohl(l->key);
+ __be32 val = htonl(l->key);
seq_indent(seq, iter->depth);
seq_printf(seq, " |-- %d.%d.%d.%d\n", NIPQUAD(val));
.release = seq_release_private,
};
-static unsigned fib_flag_trans(int type, u32 mask, const struct fib_info *fi)
+static unsigned fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
{
static unsigned type2flags[RTN_MAX + 1] = {
[7] = RTF_REJECT, [8] = RTF_REJECT,
if (fi && fi->fib_nh->nh_gw)
flags |= RTF_GATEWAY;
- if (mask == 0xFFFFFFFF)
+ if (mask == htonl(0xFFFFFFFF))
flags |= RTF_HOST;
flags |= RTF_UP;
return flags;
for (i=32; i>=0; i--) {
struct leaf_info *li = find_leaf_info(l, i);
struct fib_alias *fa;
- u32 mask, prefix;
+ __be32 mask, prefix;
if (!li)
continue;
git://ftp.safe.ca / safe / jmp / linux-2.6 / blobdiff