X-Git-Url: http://ftp.safe.ca/?a=blobdiff_plain;f=net%2Fipv4%2Ffib_trie.c;h=004a437bd7b50bffbcccd2f83cecc83d82160bca;hb=e905a9edab7f4f14f9213b52234e4a346c690911;hp=2a580eb2579bdf86bd40b7aec1b89e5246a01700;hpb=1af5a8c4a11cfed0c9a7f30fcfb689981750599c;p=safe%2Fjmp%2Flinux-2.6 diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c index 2a580eb..004a437 100644 --- a/net/ipv4/fib_trie.c +++ b/net/ipv4/fib_trie.c @@ -7,13 +7,13 @@ * Robert Olsson Uppsala Universitet * & Swedish University of Agricultural Sciences. * - * Jens Laas Swedish University of + * Jens Laas Swedish University of * Agricultural Sciences. - * + * * Hans Liss 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/ @@ -172,7 +172,7 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn); 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; @@ -224,34 +224,34 @@ static inline int tkey_mismatch(t_key a, int offset, t_key b) } /* - 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 | @@ -263,23 +263,23 @@ static inline int tkey_mismatch(t_key a, int offset, t_key b) 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. @@ -294,7 +294,7 @@ static inline void check_tnode(const struct tnode *tn) 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) @@ -355,7 +355,7 @@ static inline void tnode_free(struct tnode *tn) struct leaf *l = (struct leaf *) tn; call_rcu_bh(&l->rcu, __leaf_free_rcu); } - else + else call_rcu(&tn->rcu, __tnode_free_rcu); } @@ -461,7 +461,7 @@ static struct node *resize(struct trie *t, struct tnode *tn) 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", @@ -556,7 +556,7 @@ static struct node *resize(struct trie *t, struct tnode *tn) if(!tn->parent) inflate_threshold_use = inflate_threshold_root; - else + else inflate_threshold_use = inflate_threshold; err = 0; @@ -587,7 +587,7 @@ static struct node *resize(struct trie *t, struct tnode *tn) if(!tn->parent) halve_threshold_use = halve_threshold_root; - else + else halve_threshold_use = halve_threshold; err = 0; @@ -665,10 +665,10 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn) 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); @@ -890,23 +890,23 @@ static inline struct list_head * get_fa_head(struct leaf *l, int plen) 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 */ @@ -1124,17 +1124,14 @@ err: 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; @@ -1142,11 +1139,7 @@ fn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta, 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); @@ -1157,10 +1150,11 @@ fn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta, 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; @@ -1185,23 +1179,23 @@ fn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta, 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; @@ -1224,28 +1218,28 @@ fn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta, 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. @@ -1262,7 +1256,8 @@ fn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta, (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; @@ -1548,28 +1543,21 @@ static int trie_leaf_remove(struct trie *t, t_key key) 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) @@ -1598,13 +1586,12 @@ fn_trie_delete(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta, 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; } @@ -1614,7 +1601,8 @@ fn_trie_delete(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta, 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); @@ -1712,7 +1700,7 @@ static struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf) /* Decend if tnode */ while (IS_TNODE(c)) { p = (struct tnode *) c; - idx = 0; + idx = 0; /* Rightmost non-NULL branch */ if (p && IS_TNODE(p)) @@ -1846,7 +1834,7 @@ static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fi int i, s_i; struct fib_alias *fa; - u32 xkey = htonl(key); + __be32 xkey = htonl(key); s_i = cb->args[4]; i = 0; @@ -1866,7 +1854,7 @@ static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fi tb->tb_id, fa->fa_type, fa->fa_scope, - &xkey, + xkey, plen, fa->fa_tos, fa->fa_info, 0) < 0) { @@ -2001,6 +1989,10 @@ static struct node *fib_trie_get_next(struct fib_trie_iter *iter) 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: @@ -2049,11 +2041,18 @@ static struct node *fib_trie_get_first(struct fib_trie_iter *iter, 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; @@ -2291,25 +2290,26 @@ static int fib_trie_seq_show(struct seq_file *seq, void *v) if (v == SEQ_START_TOKEN) return 0; + if (!NODE_PARENT(n)) { + if (iter->trie == trie_local) + seq_puts(seq, ":\n"); + else + seq_puts(seq, "
:\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, ":\n"); - else - seq_puts(seq, "
:\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)); @@ -2372,7 +2372,7 @@ static struct file_operations fib_trie_fops = { .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, @@ -2381,7 +2381,7 @@ static unsigned fib_flag_trans(int type, u32 mask, const struct fib_info *fi) 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; @@ -2415,7 +2415,7 @@ static int fib_route_seq_show(struct seq_file *seq, void *v) 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;