Hi,
I started looking at the fib_trie implementation, and it's pretty neat
stuff. However, it's a bit hard to read; the nesting of indentation
is really deep at certain places and CodingStyle hasn't been followed
very closely.
Below is a patch that cleans up some of this. It shouldn't change any
behaviour and only cleans up some of the logic causing deep nesting as
well as whitespace stuff.
There's more to work on -- locking and list traversal seems a bit iffy
at a couple of places, but Robert said they're looking at using RCU
instead so I guess it might not be worth visiting just yet.
Sorry for the large patch, but I figured it's better to take care of
most of it now rather than later given that it just was added to the tree.
I unfortunately don't have a good way to regression test this, so a couple
of eyes on the patch could be a good thing. Or is there a regression
suite available?
-Olof
---
Some of the fib_trie stuff is a bit hard to read; the nesting of
indentation is really deep at certain places and CodingStyle hasn't been
followed very closely.
Below is a patch that cleans up some of this. It shouldn't change any
behaviour and only cleans up some of the logic causing deep nesting as
well as whitespace stuff. A couple of naming changes are included as
well.
Signed-off-by: Olof Johansson <[EMAIL PROTECTED]>
Index: 2.6/net/ipv4/fib_trie.c
===================================================================
--- 2.6.orig/net/ipv4/fib_trie.c 2005-07-22 11:11:15.000000000 -0500
+++ 2.6/net/ipv4/fib_trie.c 2005-07-22 11:15:16.000000000 -0500
@@ -80,7 +80,8 @@
#define EXTRACT(p, n, str) ((str)<<(p)>>(32-(n)))
#define KEYLENGTH (8*sizeof(t_key))
#define MASK_PFX(k, l) (((l)==0)?0:(k >> (KEYLENGTH-l)) << (KEYLENGTH-l))
-#define TKEY_GET_MASK(offset, bits) (((bits)==0)?0:((t_key)(-1) << (KEYLENGTH
- bits) >> offset))
+#define TKEY_GET_MASK(offset, bits) (((bits)==0)?0:((t_key)(-1) \
+ << (KEYLENGTH - bits) >> offset))
static DEFINE_RWLOCK(fib_lock);
@@ -89,27 +90,23 @@ typedef unsigned int t_key;
#define T_TNODE 0
#define T_LEAF 1
#define NODE_TYPE_MASK 0x1UL
-#define NODE_PARENT(_node) \
-((struct tnode *)((_node)->_parent & ~NODE_TYPE_MASK))
-#define NODE_SET_PARENT(_node, _ptr) \
-((_node)->_parent = (((unsigned long)(_ptr)) | \
- ((_node)->_parent & NODE_TYPE_MASK)))
-#define NODE_INIT_PARENT(_node, _type) \
-((_node)->_parent = (_type))
-#define NODE_TYPE(_node) \
-((_node)->_parent & NODE_TYPE_MASK)
+#define NODE_PARENT(node) ((struct tnode *)((node)->parent & ~NODE_TYPE_MASK))
+#define NODE_SET_PARENT(node, ptr) \
+ ((node)->parent = (((unsigned long)(ptr)) |
((node)->parent & NODE_TYPE_MASK)))
+#define NODE_INIT_PARENT(node, type) ((node)->parent = (type))
+#define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)
-#define IS_TNODE(n) (!(n->_parent & T_LEAF))
-#define IS_LEAF(n) (n->_parent & T_LEAF)
+#define IS_TNODE(n) (!(n->parent & T_LEAF))
+#define IS_LEAF(n) (n->parent & T_LEAF)
struct node {
- t_key key;
- unsigned long _parent;
+ t_key key;
+ unsigned long parent;
};
struct leaf {
- t_key key;
- unsigned long _parent;
+ t_key key;
+ unsigned long parent;
struct hlist_head list;
};
@@ -120,13 +117,13 @@ struct leaf_info {
};
struct tnode {
- t_key key;
- unsigned long _parent;
- unsigned short pos:5; /* 2log(KEYLENGTH) bits needed */
- unsigned short bits:5; /* 2log(KEYLENGTH) bits needed */
- unsigned short full_children; /* KEYLENGTH bits needed */
- unsigned short empty_children; /* KEYLENGTH bits needed */
- struct node *child[0];
+ t_key key;
+ unsigned long parent;
+ unsigned short pos:5; /* 2log(KEYLENGTH) bits needed */
+ unsigned short bits:5; /* 2log(KEYLENGTH) bits needed */
+ unsigned short full_children; /* KEYLENGTH bits needed */
+ unsigned short empty_children; /* KEYLENGTH bits needed */
+ struct node *child[0];
};
#ifdef CONFIG_IP_FIB_TRIE_STATS
@@ -147,14 +144,14 @@ struct trie_stat {
unsigned int leaves;
unsigned int nullpointers;
unsigned int nodesizes[MAX_CHILDS];
-};
+};
struct trie {
- struct node *trie;
+ struct node *trie;
#ifdef CONFIG_IP_FIB_TRIE_STATS
struct trie_use_stats stats;
#endif
- int size;
+ int size;
unsigned int revision;
};
@@ -171,10 +168,10 @@ static void tnode_free(struct tnode *tn)
static void trie_dump_seq(struct seq_file *seq, struct trie *t);
extern struct fib_alias *fib_find_alias(struct list_head *fah, u8 tos, u32
prio);
extern int fib_detect_death(struct fib_info *fi, int order,
- struct fib_info **last_resort, int *last_idx, int
*dflt);
+ struct fib_info **last_resort, int *last_idx, int
*dflt);
extern void rtmsg_fib(int event, u32 key, struct fib_alias *fa, int z, int
tb_id,
- struct nlmsghdr *n, struct netlink_skb_parms *req);
+ struct nlmsghdr *n, struct netlink_skb_parms *req);
static kmem_cache_t *fn_alias_kmem;
static struct trie *trie_local = NULL, *trie_main = NULL;
@@ -185,56 +182,38 @@ static void trie_bug(char *err)
BUG();
}
-static inline struct node *tnode_get_child(struct tnode *tn, int i)
+static inline struct node *tnode_get_child(struct tnode *tn, int i)
{
- if (i >= 1<<tn->bits)
- trie_bug("tnode_get_child");
+ if (i >= 1 << tn->bits)
+ trie_bug("tnode_get_child");
- return tn->child[i];
+ return tn->child[i];
}
static inline int tnode_child_length(struct tnode *tn)
{
- return 1<<tn->bits;
+ return 1 << tn->bits;
}
-/*
- _________________________________________________________________
- | 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
-
- _________________________________________________________________
- | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
- -----------------------------------------------------------------
- 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
-
- tp->pos = 7
- tp->bits = 3
- n->pos = 15
- n->bits=4
- KEYLENGTH=32
-*/
-
static inline t_key tkey_extract_bits(t_key a, int offset, int bits)
{
- if (offset < KEYLENGTH)
+ if (offset < KEYLENGTH)
return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
- else
+ else
return 0;
}
static inline int tkey_equals(t_key a, t_key b)
{
- return a == b;
+ return a == b;
}
static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
{
- if (bits == 0 || offset >= KEYLENGTH)
- return 1;
- bits = bits > KEYLENGTH ? KEYLENGTH : bits;
- return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
+ if (bits == 0 || offset >= KEYLENGTH)
+ return 1;
+ bits = MIN(bits, KEYLENGTH);
+ return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
}
static inline int tkey_mismatch(t_key a, int offset, t_key b)
@@ -242,9 +221,9 @@ static inline int tkey_mismatch(t_key a,
t_key diff = a ^ b;
int i = offset;
- if(!diff)
- return 0;
- while((diff << i) >> (KEYLENGTH-1) == 0)
+ if (!diff)
+ return 0;
+ while ((diff << i) >> (KEYLENGTH-1) == 0)
i++;
return i;
}
@@ -321,9 +300,8 @@ static void fn_free_alias(struct fib_ali
static void check_tnode(struct tnode *tn)
{
- if(tn && tn->pos+tn->bits > 32) {
+ if (tn && tn->pos + tn->bits > 32)
printk("TNODE ERROR tn=%p, pos=%d, bits=%d\n", tn, tn->pos,
tn->bits);
- }
}
static int halve_threshold = 25;
@@ -332,20 +310,25 @@ static int inflate_threshold = 50;
static struct leaf *leaf_new(void)
{
struct leaf *l = kmalloc(sizeof(struct leaf), GFP_KERNEL);
- if(l) {
- NODE_INIT_PARENT(l, T_LEAF);
- INIT_HLIST_HEAD(&l->list);
- }
+
+ if (!l)
+ return NULL;
+
+ NODE_INIT_PARENT(l, T_LEAF);
+ INIT_HLIST_HEAD(&l->list);
+
return l;
}
static struct leaf_info *leaf_info_new(int plen)
{
struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL);
- if(li) {
- li->plen = plen;
- INIT_LIST_HEAD(&li->falh);
- }
+ if (!li)
+ return NULL;
+
+ li->plen = plen;
+ INIT_LIST_HEAD(&li->falh);
+
return li;
}
@@ -365,14 +348,15 @@ static struct tnode *tnode_alloc(unsigne
return kmalloc(size, GFP_KERNEL);
} else {
return (struct tnode *)
- __get_free_pages(GFP_KERNEL, get_order(size));
+ __get_free_pages(GFP_KERNEL, get_order(size));
}
}
static void __tnode_free(struct tnode *tn)
{
- unsigned int size = sizeof(struct tnode) +
- (1<<tn->bits) * sizeof(struct node *);
+ unsigned int size;
+
+ size = sizeof(struct tnode) + (1<<tn->bits) * sizeof(struct node *);
if (size <= PAGE_SIZE)
kfree(tn);
@@ -386,7 +370,7 @@ static struct tnode* tnode_new(t_key key
int sz = sizeof(struct tnode) + nchildren * sizeof(struct node *);
struct tnode *tn = tnode_alloc(sz);
- if(tn) {
+ if (tn) {
memset(tn, 0, sz);
NODE_INIT_PARENT(tn, T_TNODE);
tn->pos = pos;
@@ -395,30 +379,26 @@ static struct tnode* tnode_new(t_key key
tn->full_children = 0;
tn->empty_children = 1<<bits;
}
- if(trie_debug > 0)
+ if (trie_debug > 0)
printk("AT %p s=%u %u\n", tn, (unsigned int) sizeof(struct
tnode),
- (unsigned int) (sizeof(struct node) * 1<<bits));
+ (unsigned int) (sizeof(struct node) * 1<<bits));
return tn;
}
static void tnode_free(struct tnode *tn)
{
- if(!tn) {
+ if (!tn)
trie_bug("tnode_free\n");
- }
- if(IS_LEAF(tn)) {
+
+ if (IS_LEAF(tn)) {
free_leaf((struct leaf *)tn);
- if(trie_debug > 0 )
+ if (trie_debug > 0)
printk("FL %p \n", tn);
- }
- else if(IS_TNODE(tn)) {
+ } else {
__tnode_free(tn);
- if(trie_debug > 0 )
+ if (trie_debug > 0)
printk("FT %p \n", tn);
}
- else {
- trie_bug("tnode_free\n");
- }
}
/*
@@ -428,28 +408,28 @@ static void tnode_free(struct tnode *tn)
static inline int tnode_full(struct tnode *tn, struct node *n)
{
- if(n == NULL || IS_LEAF(n))
+ if (n == NULL || IS_LEAF(n))
return 0;
return ((struct tnode *) n)->pos == tn->pos + tn->bits;
}
-static inline void put_child(struct trie *t, struct tnode *tn, int i, struct
node *n)
+static inline void put_child(struct trie *t, struct tnode *tn, int i, struct
node *n)
{
tnode_put_child_reorg(tn, i, n, -1);
}
- /*
+ /*
* Add a child at position i overwriting the old value.
* Update the value of full_children and empty_children.
*/
-static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int
wasfull)
+static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int
wasfull)
{
struct node *chi;
int isfull;
- if(i >= 1<<tn->bits) {
+ if (i >= 1 << tn->bits) {
printk("bits=%d, i=%d\n", tn->bits, i);
trie_bug("tnode_put_child_reorg bits");
}
@@ -461,25 +441,25 @@ static void tnode_put_child_reorg(struct
tn->empty_children++;
else if (n != NULL && chi == NULL)
tn->empty_children--;
-
+
/* update fullChildren */
- if (wasfull == -1)
+ if (wasfull == -1)
wasfull = tnode_full(tn, chi);
isfull = tnode_full(tn, n);
- if (wasfull && !isfull)
+ if (wasfull && !isfull)
tn->full_children--;
- else if (!wasfull && isfull)
+ else if (!wasfull && isfull)
tn->full_children++;
- if(n)
+ if (n)
NODE_SET_PARENT(n, tn);
tn->child[i] = n;
write_unlock_bh(&fib_lock);
}
-static struct node *resize(struct trie *t, struct tnode *tn)
+static struct node *resize(struct trie *t, struct tnode *tn)
{
int i;
int err = 0;
@@ -487,9 +467,9 @@ static struct node *resize(struct trie *
if (!tn)
return NULL;
- if(trie_debug)
- printk("In tnode_resize %p inflate_threshold=%d
threshold=%d\n",
- tn, inflate_threshold, halve_threshold);
+ if (trie_debug)
+ printk("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
+ tn, inflate_threshold, halve_threshold);
/* No children */
if (tn->empty_children == tnode_child_length(tn)) {
@@ -502,10 +482,9 @@ static struct node *resize(struct trie *
write_lock_bh(&fib_lock);
if (tn->child[i] != NULL) {
-
/* compress one level */
struct node *n = tn->child[i];
- if(n)
+ if (n)
NODE_INIT_PARENT(n, NODE_TYPE(n));
write_unlock_bh(&fib_lock);
@@ -514,7 +493,7 @@ static struct node *resize(struct trie *
}
write_unlock_bh(&fib_lock);
}
- /*
+ /*
* Double as long as the resulting node has a number of
* nonempty nodes that are above the threshold.
*/
@@ -564,16 +543,16 @@ static struct node *resize(struct trie *
*
* expand not_to_be_doubled and to_be_doubled, and shorten:
* 100 * (tnode_child_length(tn) - tn->empty_children +
- * tn->full_children ) >= inflate_threshold * new_child_length
+ * tn->full_children) >= inflate_threshold * new_child_length
*
* expand new_child_length:
* 100 * (tnode_child_length(tn) - tn->empty_children +
- * tn->full_children ) >=
+ * tn->full_children) >=
* inflate_threshold * tnode_child_length(tn) * 2
*
* shorten again:
* 50 * (tn->full_children + tnode_child_length(tn) -
- * tn->empty_children ) >= inflate_threshold *
+ * tn->empty_children) >= inflate_threshold *
* tnode_child_length(tn)
*
*/
@@ -582,12 +561,12 @@ static struct node *resize(struct trie *
err = 0;
while ((tn->full_children > 0 &&
- 50 * (tn->full_children + tnode_child_length(tn) -
tn->empty_children) >=
+ 50 * (tn->full_children + tnode_child_length(tn) -
tn->empty_children) >=
inflate_threshold * tnode_child_length(tn))) {
tn = inflate(t, tn, &err);
- if(err) {
+ if (err) {
#ifdef CONFIG_IP_FIB_TRIE_STATS
t->stats.resize_node_skipped++;
#endif
@@ -604,12 +583,12 @@ static struct node *resize(struct trie *
err = 0;
while (tn->bits > 1 &&
- 100 * (tnode_child_length(tn) - tn->empty_children) <
- halve_threshold * tnode_child_length(tn)) {
+ 100 * (tnode_child_length(tn) - tn->empty_children) <
+ halve_threshold * tnode_child_length(tn)) {
tn = halve(t, tn, &err);
- if(err) {
+ if (err) {
#ifdef CONFIG_IP_FIB_TRIE_STATS
t->stats.resize_node_skipped++;
#endif
@@ -617,18 +596,17 @@ static struct node *resize(struct trie *
}
}
-
+
/* Only one child remains */
if (tn->empty_children == tnode_child_length(tn) - 1)
for (i = 0; i < tnode_child_length(tn); i++) {
-
write_lock_bh(&fib_lock);
if (tn->child[i] != NULL) {
/* compress one level */
struct node *n = tn->child[i];
- if(n)
+ if (n)
NODE_INIT_PARENT(n, NODE_TYPE(n));
write_unlock_bh(&fib_lock);
@@ -648,7 +626,7 @@ static struct tnode *inflate(struct trie
int olen = tnode_child_length(tn);
int i;
- if(trie_debug)
+ if (trie_debug)
printk("In inflate\n");
tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);
@@ -665,30 +643,29 @@ static struct tnode *inflate(struct trie
* of tnode is ignored.
*/
- for(i = 0; i < olen; i++) {
+ for (i = 0; i < olen; i++) {
struct tnode *inode = (struct tnode *)
tnode_get_child(oldtnode, i);
- if (inode &&
- IS_TNODE(inode) &&
+ if (inode && IS_TNODE(inode) &&
inode->pos == oldtnode->pos + oldtnode->bits &&
inode->bits > 1) {
struct tnode *left, *right;
t_key m = TKEY_GET_MASK(inode->pos, 1);
-
+
left = tnode_new(inode->key&(~m), inode->pos + 1,
inode->bits - 1);
- if(!left) {
- *err = -ENOMEM;
+ if (!left) {
+ *err = -ENOMEM;
break;
}
right = tnode_new(inode->key|m, inode->pos + 1,
inode->bits - 1);
- if(!right) {
- *err = -ENOMEM;
+ if (!right) {
+ *err = -ENOMEM;
break;
}
@@ -697,12 +674,12 @@ static struct tnode *inflate(struct trie
}
}
- if(*err) {
+ if (*err) {
int size = tnode_child_length(tn);
int j;
- for(j = 0; j < size; j++)
- if( tn->child[j])
+ for (j = 0; j < size; j++)
+ if (tn->child[j])
tnode_free((struct tnode *)tn->child[j]);
tnode_free(tn);
@@ -711,18 +688,18 @@ static struct tnode *inflate(struct trie
return oldtnode;
}
- for(i = 0; i < olen; i++) {
+ for (i = 0; i < olen; i++) {
struct node *node = tnode_get_child(oldtnode, i);
-
+
/* An empty child */
if (node == NULL)
continue;
/* A leaf or an internal node with skipped bits */
- if(IS_LEAF(node) || ((struct tnode *) node)->pos >
+ if (IS_LEAF(node) || ((struct tnode *) node)->pos >
tn->pos + tn->bits - 1) {
- if(tkey_extract_bits(node->key, oldtnode->pos +
oldtnode->bits,
+ if (tkey_extract_bits(node->key, oldtnode->pos +
oldtnode->bits,
1) == 0)
put_child(t, tn, 2*i, node);
else
@@ -738,10 +715,8 @@ static struct tnode *inflate(struct trie
put_child(t, tn, 2*i+1, inode->child[1]);
tnode_free(inode);
- }
-
+ } else {
/* An internal node with more than two children */
- else {
struct tnode *left, *right;
int size, j;
@@ -769,17 +744,15 @@ static struct tnode *inflate(struct trie
left = (struct tnode *) tnode_get_child(tn, 2*i);
put_child(t, tn, 2*i, NULL);
- if(!left)
- BUG();
+ BUG_ON(!left);
right = (struct tnode *) tnode_get_child(tn, 2*i+1);
put_child(t, tn, 2*i+1, NULL);
- if(!right)
- BUG();
+ BUG_ON(!right);
size = tnode_child_length(left);
- for(j = 0; j < size; j++) {
+ for (j = 0; j < size; j++) {
put_child(t, left, j, inode->child[j]);
put_child(t, right, j, inode->child[j + size]);
}
@@ -800,9 +773,10 @@ static struct tnode *halve(struct trie *
int i;
int olen = tnode_child_length(tn);
- if(trie_debug) printk("In halve\n");
-
- tn=tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
+ if (trie_debug)
+ printk("In halve\n");
+
+ tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
if (!tn) {
*err = -ENOMEM;
@@ -816,29 +790,29 @@ static struct tnode *halve(struct trie *
* of tnode is ignored.
*/
- for(i = 0; i < olen; i += 2) {
+ for (i = 0; i < olen; i += 2) {
left = tnode_get_child(oldtnode, i);
right = tnode_get_child(oldtnode, i+1);
-
+
/* Two nonempty children */
- if( left && right) {
+ if (left && right) {
struct tnode *newBinNode =
tnode_new(left->key, tn->pos + tn->bits, 1);
- if(!newBinNode) {
- *err = -ENOMEM;
+ if (!newBinNode) {
+ *err = -ENOMEM;
break;
}
put_child(t, tn, i/2, (struct node *)newBinNode);
}
}
- if(*err) {
+ if (*err) {
int size = tnode_child_length(tn);
int j;
- for(j = 0; j < size; j++)
- if( tn->child[j])
+ for (j = 0; j < size; j++)
+ if (tn->child[j])
tnode_free((struct tnode *)tn->child[j]);
tnode_free(tn);
@@ -847,30 +821,30 @@ static struct tnode *halve(struct trie *
return oldtnode;
}
- for(i = 0; i < olen; i += 2) {
+ for (i = 0; i < olen; i += 2) {
left = tnode_get_child(oldtnode, i);
right = tnode_get_child(oldtnode, i+1);
-
+
/* At least one of the children is empty */
if (left == NULL) {
if (right == NULL) /* Both are empty */
continue;
put_child(t, tn, i/2, right);
- } else if (right == NULL)
- put_child(t, tn, i/2, left);
-
- /* Two nonempty children */
- else {
- struct tnode *newBinNode =
- (struct tnode *) tnode_get_child(tn, i/2);
- put_child(t, tn, i/2, NULL);
-
- if(!newBinNode)
- BUG();
-
- put_child(t, newBinNode, 0, left);
- put_child(t, newBinNode, 1, right);
- put_child(t, tn, i/2, resize(t, newBinNode));
+ } else {
+ if (right == NULL) {
+ put_child(t, tn, i/2, left);
+ } else {
+ /* Two nonempty children */
+ struct tnode *newBinNode =
+ (struct tnode *) tnode_get_child(tn,
i/2);
+ put_child(t, tn, i/2, NULL);
+
+ BUG_ON(!newBinNode);
+
+ put_child(t, newBinNode, 0, left);
+ put_child(t, newBinNode, 1, right);
+ put_child(t, tn, i/2, resize(t, newBinNode));
+ }
}
}
tnode_free(oldtnode);
@@ -879,12 +853,12 @@ static struct tnode *halve(struct trie *
static void *trie_init(struct trie *t)
{
- if(t) {
+ if (t) {
t->size = 0;
t->trie = NULL;
t->revision = 0;
#ifdef CONFIG_IP_FIB_TRIE_STATS
- memset(&t->stats, 0, sizeof(struct trie_use_stats));
+ memset(&t->stats, 0, sizeof(struct trie_use_stats));
#endif
}
return t;
@@ -896,8 +870,7 @@ static struct leaf_info *find_leaf_info(
struct leaf_info *li;
hlist_for_each_entry(li, node, head, hlist) {
-
- if ( li->plen == plen )
+ if (li->plen == plen)
return li;
}
return NULL;
@@ -905,35 +878,34 @@ static struct leaf_info *find_leaf_info(
static inline struct list_head * get_fa_head(struct leaf *l, int plen)
{
- struct list_head *fa_head=NULL;
struct leaf_info *li = find_leaf_info(&l->list, plen);
- if(li)
- fa_head = &li->falh;
-
- return fa_head;
+ if (li)
+ return &li->falh;
+ else
+ return NULL;
}
static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
{
- struct leaf_info *li=NULL, *last=NULL;
+ struct leaf_info *li = NULL, *last = NULL;
struct hlist_node *node, *tmp;
write_lock_bh(&fib_lock);
- if(hlist_empty(head))
+ if (hlist_empty(head)) {
hlist_add_head(&new->hlist, head);
- else {
+ } else {
hlist_for_each_entry_safe(li, node, tmp, head, hlist) {
-
- if (new->plen > li->plen)
+ if (new->plen > li->plen)
break;
last = li;
}
- if(last)
+
+ if (last)
hlist_add_after(&last->hlist, &new->hlist);
- else
+ else
hlist_add_before(&new->hlist, &li->hlist);
}
write_unlock_bh(&fib_lock);
@@ -947,18 +919,17 @@ fib_find_node(struct trie *t, u32 key)
struct node *n;
pos = 0;
- n=t->trie;
+ n = t->trie;
while (n != NULL && NODE_TYPE(n) == T_TNODE) {
- tn = (struct tnode *) n;
+ tn = (struct tnode *)n;
check_tnode(tn);
- if(tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
- pos=tn->pos + tn->bits;
+ if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
+ pos = tn->pos + tn->bits;
n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos,
tn->bits));
- }
- else
+ } else
break;
}
/* Case we have found a leaf. Compare prefixes */
@@ -977,23 +948,24 @@ static struct node *trie_rebalance(struc
t_key cindex, key;
struct tnode *tp = NULL;
- if(!tn)
- BUG();
+ BUG_ON(!tn);
key = tn->key;
i = 0;
while (tn != NULL && NODE_PARENT(tn) != NULL) {
-
- if( i > 10 ) {
+ if (i > 10) {
printk("Rebalance tn=%p \n", tn);
- if(tn) printk("tn->parent=%p \n",
NODE_PARENT(tn));
+ if (tn)
+ printk("tn->parent=%p \n", NODE_PARENT(tn));
printk("Rebalance tp=%p \n", tp);
- if(tp) printk("tp->parent=%p \n",
NODE_PARENT(tp));
+ if (tp)
+ printk("tp->parent=%p \n", NODE_PARENT(tp));
}
- if( i > 12 ) BUG();
+ BUG_ON(i > 12);
+
i++;
tp = NODE_PARENT(tn);
@@ -1002,19 +974,19 @@ static struct node *trie_rebalance(struc
tn = (struct tnode *) resize (t, (struct tnode *)tn);
tnode_put_child_reorg((struct tnode *)tp, cindex,(struct
node*)tn, wasfull);
- if(!NODE_PARENT(tn))
+ if (!NODE_PARENT(tn))
break;
tn = NODE_PARENT(tn);
}
/* Handle last (top) tnode */
- if (IS_TNODE(tn))
+ if (IS_TNODE(tn))
tn = (struct tnode*) resize(t, (struct tnode *)tn);
return (struct node*) tn;
}
-static struct list_head *
+static struct list_head *
fib_insert_node(struct trie *t, int *err, u32 key, int plen)
{
int pos, newpos;
@@ -1022,12 +994,12 @@ fib_insert_node(struct trie *t, int *err
struct node *n;
struct leaf *l;
int missbit;
- struct list_head *fa_head=NULL;
+ struct list_head *fa_head = NULL;
struct leaf_info *li;
t_key cindex;
pos = 0;
- n=t->trie;
+ n = t->trie;
/* If we point to NULL, stop. Either the tree is empty and we should
* just put a new leaf in if, or we have reached an empty child slot,
@@ -1052,17 +1024,16 @@ fib_insert_node(struct trie *t, int *err
check_tnode(tn);
- if(tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
+ if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
tp = tn;
pos=tn->pos + tn->bits;
n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos,
tn->bits));
- if(n && NODE_PARENT(n) != tn) {
+ if (n && NODE_PARENT(n) != tn) {
printk("BUG tn=%p, n->parent=%p\n", tn,
NODE_PARENT(n));
BUG();
}
- }
- else
+ } else
break;
}
@@ -1072,20 +1043,18 @@ fib_insert_node(struct trie *t, int *err
* tp is n's (parent) ----> NULL or TNODE
*/
- if(tp && IS_LEAF(tp))
- BUG();
-
+ BUG_ON(tp && IS_LEAF(tp));
/* Case 1: n is a leaf. Compare prefixes */
- if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
- struct leaf *l = ( struct leaf *) n;
+ if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
+ struct leaf *l = (struct leaf *)n;
li = leaf_info_new(plen);
- if(! li) {
+ if (!li) {
*err = -ENOMEM;
- goto err;
+ goto out_err;
}
fa_head = &li->falh;
@@ -1095,97 +1064,90 @@ fib_insert_node(struct trie *t, int *err
t->size++;
l = leaf_new();
- if(! l) {
+ if (!l) {
*err = -ENOMEM;
- goto err;
+ goto out_err;
}
l->key = key;
li = leaf_info_new(plen);
- if(! li) {
+ if (!li) {
tnode_free((struct tnode *) l);
*err = -ENOMEM;
- goto err;
+ goto out_err;
}
fa_head = &li->falh;
insert_leaf_info(&l->list, li);
- /* Case 2: n is NULL, and will just insert a new leaf */
if (t->trie && n == NULL) {
-
+ /* Case 2: n is NULL, and will just insert a new leaf */
NODE_SET_PARENT(l, tp);
- if (!tp)
- BUG();
-
- else {
- cindex = tkey_extract_bits(key, tp->pos, tp->bits);
- put_child(t, (struct tnode *)tp, cindex, (struct node
*)l);
- }
- }
- /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
- else {
- /*
- * Add a new tnode here
- * first tnode need some special handling
+ BUG_ON(!tp);
+
+ cindex = tkey_extract_bits(key, tp->pos, tp->bits);
+ put_child(t, (struct tnode *)tp, cindex, (struct node *)l);
+ } else {
+ /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
+ /*
+ * Add a new tnode here. First tnode need some special handling
*/
if (tp)
- pos=tp->pos+tp->bits;
+ pos = tp->pos+tp->bits;
else
- pos=0;
- if(n) {
+ pos = 0;
+
+ if (n) {
newpos = tkey_mismatch(key, pos, n->key);
tn = tnode_new(n->key, newpos, 1);
- }
- else {
+ } else {
newpos = 0;
- tn = tnode_new(key, newpos, 1); /* First tnode */
+ tn = tnode_new(key, newpos, 1); /* First tnode */
}
- if(!tn) {
+ if (!tn) {
free_leaf_info(li);
tnode_free((struct tnode *) l);
*err = -ENOMEM;
- goto err;
+ goto out_err;
}
NODE_SET_PARENT(tn, tp);
- missbit=tkey_extract_bits(key, newpos, 1);
+ missbit = tkey_extract_bits(key, newpos, 1);
put_child(t, tn, missbit, (struct node *)l);
put_child(t, tn, 1-missbit, n);
- if(tp) {
+ if (tp) {
cindex = tkey_extract_bits(key, tp->pos, tp->bits);
put_child(t, (struct tnode *)tp, cindex, (struct node
*)tn);
- }
- else {
+ } else {
t->trie = (struct node*) tn; /* First tnode */
tp = tn;
}
}
- if(tp && tp->pos+tp->bits > 32) {
- printk("ERROR tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
- tp, tp->pos, tp->bits, key, plen);
+ if (tp && tp->pos+tp->bits > 32) {
+ printk("ERROR tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
+ tp, tp->pos, tp->bits, key, plen);
}
/* Rebalance the trie */
t->trie = trie_rebalance(t, tp);
done:
t->revision++;
-err:;
+out_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)
+ struct nlmsghdr *nlhdr, struct netlink_skb_parms *req)
{
struct trie *t = (struct trie *) tb->tb_data;
struct fib_alias *fa, *new_fa;
- struct list_head *fa_head=NULL;
+ struct list_head *fa_head = NULL;
struct fib_info *fi;
int plen = r->rtm_dst_len;
int type = r->rtm_type;
@@ -1198,28 +1160,28 @@ fn_trie_insert(struct fib_table *tb, str
return -EINVAL;
key = 0;
- if (rta->rta_dst)
+ if (rta->rta_dst)
memcpy(&key, rta->rta_dst, 4);
key = ntohl(key);
- if(trie_debug)
+ if (trie_debug)
printk("Insert table=%d %08x/%d\n", tb->tb_id, key, plen);
- mask = ntohl( inet_make_mask(plen) );
+ mask = ntohl(inet_make_mask(plen));
- if(key & ~mask)
+ if (key & ~mask)
return -EINVAL;
key = key & mask;
if ((fi = fib_create_info(r, rta, nlhdr, &err)) == NULL)
- goto err;
+ goto out_err;
l = fib_find_node(t, key);
fa = NULL;
- if(l) {
+ if (l) {
fa_head = get_fa_head(l, plen);
fa = fib_find_alias(fa_head, tos, fi->fib_priority);
}
@@ -1235,8 +1197,7 @@ fn_trie_insert(struct fib_table *tb, str
* and we need to allocate a new one of those as well.
*/
- if (fa &&
- fa->fa_info->fib_priority == fi->fib_priority) {
+ if (fa && fa->fa_info->fib_priority == fi->fib_priority) {
struct fib_alias *fa_orig;
err = -EEXIST;
@@ -1260,9 +1221,9 @@ fn_trie_insert(struct fib_table *tb, str
fib_release_info(fi_drop);
if (state & FA_S_ACCESSED)
- rt_cache_flush(-1);
+ rt_cache_flush(-1);
- goto succeeded;
+ goto succeeded;
}
/* Error if we find a perfect match which
* uses the same scope, type, and nexthop
@@ -1284,7 +1245,7 @@ fn_trie_insert(struct fib_table *tb, str
fa = fa_orig;
}
err = -ENOENT;
- if (!(nlhdr->nlmsg_flags&NLM_F_CREATE))
+ if (!(nlhdr->nlmsg_flags & NLM_F_CREATE))
goto out;
err = -ENOBUFS;
@@ -1297,24 +1258,23 @@ fn_trie_insert(struct fib_table *tb, str
new_fa->fa_type = type;
new_fa->fa_scope = r->rtm_scope;
new_fa->fa_state = 0;
-#if 0
- new_fa->dst = NULL;
-#endif
/*
* Insert new entry to the list.
*/
- if(!fa_head) {
+ if (!fa_head) {
fa_head = fib_insert_node(t, &err, key, plen);
err = 0;
- if(err)
+ if (err)
goto out_free_new_fa;
}
write_lock_bh(&fib_lock);
- list_add_tail(&new_fa->fa_list,
- (fa ? &fa->fa_list : fa_head));
+ if (fa)
+ list_add_tail(&new_fa->fa_list, &fa->fa_list);
+ else
+ list_add_tail(&new_fa->fa_list, fa_head);
write_unlock_bh(&fib_lock);
@@ -1327,11 +1287,12 @@ out_free_new_fa:
kmem_cache_free(fn_alias_kmem, new_fa);
out:
fib_release_info(fi);
-err:;
+out_err:
return err;
}
-static inline int check_leaf(struct trie *t, struct leaf *l, t_key key, int
*plen, const struct flowi *flp,
+static inline int check_leaf(struct trie *t, struct leaf *l, t_key key,
+ int *plen, const struct flowi *flp,
struct fib_result *res, int *err)
{
int i;
@@ -1341,10 +1302,9 @@ static inline int check_leaf(struct trie
struct hlist_node *node;
hlist_for_each_entry(li, node, hhead, hlist) {
-
i = li->plen;
mask = ntohl(inet_make_mask(i));
- if (l->key != (key & mask))
+ if (l->key != (key & mask))
continue;
if (((*err) = fib_semantic_match(&li->falh, flp, res, l->key,
mask, i)) == 0) {
@@ -1369,14 +1329,14 @@ fn_trie_lookup(struct fib_table *tb, con
struct node *n;
struct tnode *pn;
int pos, bits;
- t_key key=ntohl(flp->fl4_dst);
+ t_key key = ntohl(flp->fl4_dst);
int chopped_off;
t_key cindex = 0;
int current_prefix_length = KEYLENGTH;
n = t->trie;
read_lock(&fib_lock);
- if(!n)
+ if (!n)
goto failed;
#ifdef CONFIG_IP_FIB_TRIE_STATS
@@ -1385,19 +1345,18 @@ fn_trie_lookup(struct fib_table *tb, con
/* Just a leaf? */
if (IS_LEAF(n)) {
- if( check_leaf(t, (struct leaf *)n, key, &plen, flp, res, &ret)
)
+ if (check_leaf(t, (struct leaf *)n, key, &plen, flp, res, &ret))
goto found;
goto failed;
}
pn = (struct tnode *) n;
chopped_off = 0;
- while (pn) {
-
+ while (pn) {
pos = pn->pos;
bits = pn->bits;
- if(!chopped_off)
+ if (!chopped_off)
cindex = tkey_extract_bits(MASK_PFX(key,
current_prefix_length), pos, bits);
n = tnode_get_child(pn, cindex);
@@ -1446,7 +1405,7 @@ fn_trie_lookup(struct fib_table *tb, con
if (current_prefix_length < pos+bits) {
if (tkey_extract_bits(cn->key,
current_prefix_length,
- cn->pos -
current_prefix_length) != 0 ||
+ cn->pos -
current_prefix_length) != 0 ||
!(cn->child[0]))
goto backtrace;
}
@@ -1500,16 +1459,16 @@ fn_trie_lookup(struct fib_table *tb, con
if (current_prefix_length >= cn->pos)
current_prefix_length=mp;
- }
+ }
#endif
- pn = (struct tnode *)n; /* Descend */
- chopped_off = 0;
- continue;
- }
+ pn = (struct tnode *)n; /* Descend */
+ chopped_off = 0;
+ continue;
+ }
if (IS_LEAF(n)) {
- if( check_leaf(t, (struct leaf *)n, key, &plen, flp,
res, &ret))
+ if (check_leaf(t, (struct leaf *)n, key, &plen, flp,
res, &ret))
goto found;
- }
+ }
backtrace:
chopped_off++;
@@ -1527,10 +1486,10 @@ backtrace:
* chopped off all bits in this tnode walk up to our parent.
*/
- if(chopped_off <= pn->bits)
+ if (chopped_off <= pn->bits) {
cindex &= ~(1 << (chopped_off-1));
- else {
- if( NODE_PARENT(pn) == NULL)
+ } else {
+ if (NODE_PARENT(pn) == NULL)
goto failed;
/* Get Child's index */
@@ -1542,7 +1501,7 @@ backtrace:
t->stats.backtrack++;
#endif
goto backtrace;
- }
+ }
}
failed:
ret = 1;
@@ -1558,7 +1517,7 @@ static int trie_leaf_remove(struct trie
struct node *n = t->trie;
struct leaf *l;
- if(trie_debug)
+ if (trie_debug)
printk("entering trie_leaf_remove(%p)\n", n);
/* Note that in the case skipped bits, those bits are *not* checked!
@@ -1566,21 +1525,21 @@ static int trie_leaf_remove(struct trie
* T_LEAF may or may not match our key.
*/
- while (n != NULL && IS_TNODE(n)) {
+ while (n != NULL && IS_TNODE(n)) {
struct tnode *tn = (struct tnode *) n;
check_tnode(tn);
- n = tnode_get_child(tn ,tkey_extract_bits(key, tn->pos,
tn->bits));
+ n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos,
tn->bits));
- if(n && NODE_PARENT(n) != tn) {
- printk("BUG tn=%p, n->parent=%p\n", tn,
NODE_PARENT(n));
- BUG();
- }
- }
+ if (n && NODE_PARENT(n) != tn) {
+ printk("BUG tn=%p, n->parent=%p\n", tn, NODE_PARENT(n));
+ BUG();
+ }
+ }
l = (struct leaf *) n;
- if(!n || !tkey_equals(l->key, key))
+ if (!n || !tkey_equals(l->key, key))
return 0;
-
+
/*
* Key found.
* Remove the leaf and rebalance the tree
@@ -1592,7 +1551,7 @@ static int trie_leaf_remove(struct trie
tp = NODE_PARENT(n);
tnode_free((struct tnode *) n);
- if(tp) {
+ if (tp) {
cindex = tkey_extract_bits(key, tp->pos, tp->bits);
put_child(t, (struct tnode *)tp, cindex, NULL);
t->trie = trie_rebalance(t, tp);
@@ -1605,7 +1564,7 @@ static int trie_leaf_remove(struct trie
static int
fn_trie_delete(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
- struct nlmsghdr *nlhdr, struct netlink_skb_parms *req)
+ struct nlmsghdr *nlhdr, struct netlink_skb_parms *req)
{
struct trie *t = (struct trie *) tb->tb_data;
u32 key, mask;
@@ -1615,23 +1574,23 @@ fn_trie_delete(struct fib_table *tb, str
struct list_head *fa_head;
struct leaf *l;
- if (plen > 32)
+ if (plen > 32)
return -EINVAL;
key = 0;
- if (rta->rta_dst)
+ if (rta->rta_dst)
memcpy(&key, rta->rta_dst, 4);
key = ntohl(key);
- mask = ntohl( inet_make_mask(plen) );
+ mask = ntohl(inet_make_mask(plen));
- if(key & ~mask)
+ if (key & ~mask)
return -EINVAL;
key = key & mask;
l = fib_find_node(t, key);
- if(!l)
+ if (!l)
return -ESRCH;
fa_head = get_fa_head(l, plen);
@@ -1677,16 +1636,16 @@ fn_trie_delete(struct fib_table *tb, str
list_del(&fa->fa_list);
- if(list_empty(fa_head)) {
+ if (list_empty(fa_head)) {
hlist_del(&li->hlist);
kill_li = 1;
}
write_unlock_bh(&fib_lock);
- if(kill_li)
+ if (kill_li)
free_leaf_info(li);
- if(hlist_empty(&l->list))
+ if (hlist_empty(&l->list))
trie_leaf_remove(t, key);
if (fa->fa_state & FA_S_ACCESSED)
@@ -1707,10 +1666,9 @@ static int trie_flush_list(struct trie *
struct fib_info *fi = fa->fa_info;
if (fi && (fi->fib_flags&RTNH_F_DEAD)) {
-
write_lock_bh(&fib_lock);
list_del(&fa->fa_list);
- write_unlock_bh(&fib_lock);
+ write_unlock_bh(&fib_lock);
fn_free_alias(fa);
found++;
@@ -1727,14 +1685,13 @@ static int trie_flush_leaf(struct trie *
struct leaf_info *li = NULL;
hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
-
found += trie_flush_list(t, &li->falh);
if (list_empty(&li->falh)) {
- write_lock_bh(&fib_lock);
+ write_lock_bh(&fib_lock);
hlist_del(&li->hlist);
- write_unlock_bh(&fib_lock);
+ write_unlock_bh(&fib_lock);
free_leaf_info(li);
}
@@ -1748,30 +1705,29 @@ static struct leaf *nextleaf(struct trie
struct tnode *p;
int idx;
- if(c == NULL) {
- if(t->trie == NULL)
+ if (c == NULL) {
+ if (t->trie == NULL)
return NULL;
- if (IS_LEAF(t->trie)) /* trie w. just a leaf */
+ if (IS_LEAF(t->trie)) /* trie w. just a leaf */
return (struct leaf *) t->trie;
- p = (struct tnode*) t->trie; /* Start */
- }
- else
+ p = (struct tnode *) t->trie; /* Start */
+ } else
p = (struct tnode *) NODE_PARENT(c);
+
while (p) {
int pos, last;
/* Find the next child of the parent */
- if(c)
- pos = 1 + tkey_extract_bits(c->key, p->pos, p->bits);
- else
+ if (c)
+ pos = 1 + tkey_extract_bits(c->key, p->pos, p->bits);
+ else
pos = 0;
last = 1 << p->bits;
- for(idx = pos; idx < last ; idx++) {
- if( p->child[idx]) {
-
+ for (idx = pos; idx < last ; idx++) {
+ if (p->child[idx]) {
/* Decend if tnode */
while (IS_TNODE(p->child[idx])) {
@@ -1779,11 +1735,12 @@ static struct leaf *nextleaf(struct trie
idx = 0;
/* Rightmost non-NULL branch */
- if( p && IS_TNODE(p) )
- while ( p->child[idx] == NULL
&& idx < (1 << p->bits) ) idx++;
+ if (p && IS_TNODE(p))
+ while (p->child[idx] == NULL &&
idx < (1 << p->bits))
+ idx++;
/* Done with this tnode? */
- if( idx >= (1 << p->bits) ||
p->child[idx] == NULL )
+ if (idx >= (1 << p->bits) ||
p->child[idx] == NULL)
goto up;
}
return (struct leaf*) p->child[idx];
@@ -1791,7 +1748,7 @@ static struct leaf *nextleaf(struct trie
}
up:
/* No more children go up one step */
- c = (struct node*) p;
+ c = (struct node *) p;
p = (struct tnode *) NODE_PARENT(p);
}
return NULL; /* Ready. Root of trie */
@@ -1816,7 +1773,7 @@ static int fn_trie_flush(struct fib_tabl
if (ll && hlist_empty(&ll->list))
trie_leaf_remove(t, ll->key);
- if(trie_debug)
+ if (trie_debug)
printk("trie_flush found=%d\n", found);
return found;
}
@@ -1841,14 +1798,13 @@ fn_trie_select_default(struct fib_table
read_lock(&fib_lock);
l = fib_find_node(t, 0);
- if(!l)
+
+ if (!l)
goto out;
fa_head = get_fa_head(l, 0);
- if(!fa_head)
- goto out;
- if (list_empty(fa_head))
+ if (!fa_head || list_empty(fa_head))
goto out;
list_for_each_entry(fa, fa_head, fa_list) {
@@ -1865,18 +1821,20 @@ fn_trie_select_default(struct fib_table
continue;
fa->fa_state |= FA_S_ACCESSED;
- if (fi == NULL) {
- if (next_fi != res->fi)
- break;
- } else if (!fib_detect_death(fi, order, &last_resort,
- &last_idx, &trie_last_dflt)) {
+ if (fi == NULL && next_fi != res->fi)
+ break;
+
+ if (!fib_detect_death(fi, order, &last_resort,
+ &last_idx, &trie_last_dflt)) {
if (res->fi)
fib_info_put(res->fi);
res->fi = fi;
atomic_inc(&fi->fib_clntref);
trie_last_dflt = order;
+
goto out;
}
+
fi = next_fi;
order++;
}
@@ -1901,7 +1859,7 @@ fn_trie_select_default(struct fib_table
atomic_inc(&last_resort->fib_clntref);
}
trie_last_dflt = last_idx;
- out:;
+ out:
read_unlock(&fib_lock);
}
@@ -1911,9 +1869,9 @@ static int fn_trie_dump_fa(t_key key, in
int i, s_i;
struct fib_alias *fa;
- u32 xkey=htonl(key);
+ u32 xkey = htonl(key);
- s_i=cb->args[3];
+ s_i = cb->args[3];
i = 0;
list_for_each_entry(fa, fah, fa_list) {
@@ -1944,10 +1902,10 @@ static int fn_trie_dump_fa(t_key key, in
fa->fa_info, 0) < 0) {
cb->args[3] = i;
return -1;
- }
+ }
i++;
}
- cb->args[3]=i;
+ cb->args[3] = i;
return skb->len;
}
@@ -1957,7 +1915,8 @@ static int fn_trie_dump_plen(struct trie
int h, s_h;
struct list_head *fa_head;
struct leaf *l = NULL;
- s_h=cb->args[2];
+
+ s_h = cb->args[2];
for (h=0; (l = nextleaf(t, l)) != NULL; h++) {
@@ -1965,22 +1924,22 @@ static int fn_trie_dump_plen(struct trie
continue;
if (h > s_h)
memset(&cb->args[3], 0,
- sizeof(cb->args) - 3*sizeof(cb->args[0]));
+ sizeof(cb->args) - 3*sizeof(cb->args[0]));
fa_head = get_fa_head(l, plen);
- if(!fa_head)
+ if (!fa_head)
continue;
- if(list_empty(fa_head))
+ if (list_empty(fa_head))
continue;
if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb)<0) {
- cb->args[2]=h;
+ cb->args[2] = h;
return -1;
}
}
- cb->args[2]=h;
+ cb->args[2] = h;
return skb->len;
}
@@ -1992,13 +1951,13 @@ static int fn_trie_dump(struct fib_table
s_m = cb->args[1];
read_lock(&fib_lock);
- for (m=0; m<=32; m++) {
+ for (m = 0; m <= 32; m++) {
if (m < s_m)
continue;
if (m > s_m)
memset(&cb->args[2], 0,
- sizeof(cb->args) - 2*sizeof(cb->args[0]));
+ sizeof(cb->args) - 2*sizeof(cb->args[0]));
if (fn_trie_dump_plen(t, 32-m, tb, skb, cb)<0) {
cb->args[1] = m;
@@ -2048,10 +2007,10 @@ struct fib_table * __init fib_hash_init(
trie_init(t);
- if (id == RT_TABLE_LOCAL)
- trie_local=t;
- else if (id == RT_TABLE_MAIN)
- trie_main=t;
+ if (id == RT_TABLE_LOCAL)
+ trie_local = t;
+ else if (id == RT_TABLE_MAIN)
+ trie_main = t;
if (id == RT_TABLE_LOCAL)
printk("IPv4 FIB: Using LC-trie version %s\n", VERSION);
@@ -2063,7 +2022,8 @@ struct fib_table * __init fib_hash_init(
static void putspace_seq(struct seq_file *seq, int n)
{
- while (n--) seq_printf(seq, " ");
+ while (n--)
+ seq_printf(seq, " ");
}
static void printbin_seq(struct seq_file *seq, unsigned int v, int bits)
@@ -2080,63 +2040,60 @@ static void printnode_seq(struct seq_fil
seq_printf(seq, "|");
else
seq_printf(seq, "+");
+
if (bits) {
seq_printf(seq, "%d/", cindex);
printbin_seq(seq, cindex, bits);
seq_printf(seq, ": ");
- }
- else
+ } else
seq_printf(seq, "<root>: ");
- seq_printf(seq, "%s:%p ", IS_LEAF(n)?"Leaf":"Internal node", n);
- if (IS_LEAF(n))
- seq_printf(seq, "key=%d.%d.%d.%d\n",
- n->key >> 24, (n->key >> 16) % 256, (n->key >> 8) %
256, n->key % 256);
- else {
- int plen=((struct tnode *)n)->pos;
- t_key prf=MASK_PFX(n->key, plen);
- seq_printf(seq, "key=%d.%d.%d.%d/%d\n",
- prf >> 24, (prf >> 16) % 256, (prf >> 8) % 256, prf
% 256, plen);
- }
if (IS_LEAF(n)) {
- struct leaf *l=(struct leaf *)n;
+ struct leaf *l = (struct leaf *)n;
struct fib_alias *fa;
int i;
- for (i=32; i>=0; i--)
- if(find_leaf_info(&l->list, i)) {
-
- struct list_head *fa_head = get_fa_head(l, i);
+
+ seq_printf(seq, "Leaf:%p ", n);
+
+ seq_printf(seq, "key=%d.%d.%d.%d\n",
+ n->key >> 24, (n->key >> 16) % 256,
+ (n->key >> 8) % 256, n->key % 256);
+
+ for (i = 32; i >= 0; i--) {
+ struct list_head *fa_head = get_fa_head(l, i);
+
+ if (!find_leaf_info(&l->list, i))
+ continue;
- if(!fa_head)
- continue;
+ if (!fa_head || list_empty(fa_head))
+ continue;
- if(list_empty(fa_head))
- continue;
+ putspace_seq(seq, indent+2);
+ seq_printf(seq, "{/%d...dumping}\n", i);
+ list_for_each_entry(fa, fa_head, fa_list) {
putspace_seq(seq, indent+2);
- seq_printf(seq, "{/%d...dumping}\n", i);
-
- list_for_each_entry(fa, fa_head, fa_list) {
- putspace_seq(seq, indent+2);
- if (fa->fa_info->fib_nh == NULL) {
- seq_printf(seq, "Error
_fib_nh=NULL\n");
- continue;
- }
- if (fa->fa_info == NULL) {
- seq_printf(seq, "Error
fa_info=NULL\n");
- continue;
- }
-
- seq_printf(seq, "{type=%d scope=%d
TOS=%d}\n",
- fa->fa_type,
- fa->fa_scope,
- fa->fa_tos);
+ if (!fa->fa_info || !fa->fa_info->fib_nh) {
+ seq_printf(seq, "Error _fib_nh=NULL\n");
+ continue;
}
+
+ seq_printf(seq, "{type=%d scope=%d TOS=%d}\n",
+ fa->fa_type, fa->fa_scope, fa->fa_tos);
}
- }
- else if (IS_TNODE(n)) {
- struct tnode *tn=(struct tnode *)n;
+ }
+ } else {
+ struct tnode *tn = (struct tnode *)n;
+ int plen = ((struct tnode *)n)->pos;
+ t_key prf = MASK_PFX(n->key, plen);
+
+ seq_printf(seq, "Internal node:%p ", n);
+
+ seq_printf(seq, "key=%d.%d.%d.%d/%d\n",
+ prf >> 24, (prf >> 16) % 256,
+ (prf >> 8) % 256, prf % 256, plen);
+
putspace_seq(seq, indent); seq_printf(seq, "| ");
seq_printf(seq, "{key prefix=%08x/", tn->key&TKEY_GET_MASK(0,
tn->pos));
printbin_seq(seq, tkey_extract_bits(tn->key, 0, tn->pos),
tn->pos);
@@ -2152,191 +2109,170 @@ static void printnode_seq(struct seq_fil
static void trie_dump_seq(struct seq_file *seq, struct trie *t)
{
- struct node *n=t->trie;
- int cindex=0;
- int indent=1;
- int pend=0;
- int depth = 0;
+ struct node *n = t->trie;
+ int cindex = 0;
+ int indent = 4;
+ int pend = 0;
+ int depth = 1;
+ struct tnode *tn = (struct tnode *)n;
read_lock(&fib_lock);
seq_printf(seq, "------ trie_dump of t=%p ------\n", t);
- if (n) {
- printnode_seq(seq, indent, n, pend, cindex, 0);
- if (IS_TNODE(n)) {
- struct tnode *tn=(struct tnode *)n;
- pend = tn->pos+tn->bits;
- putspace_seq(seq, indent); seq_printf(seq, "\\--\n");
- indent += 3;
- depth++;
- while (tn && cindex < (1 << tn->bits)) {
- if (tn->child[cindex]) {
-
- /* Got a child */
-
- printnode_seq(seq, indent,
tn->child[cindex], pend, cindex, tn->bits);
- if (IS_LEAF(tn->child[cindex])) {
- cindex++;
-
- }
- else {
- /*
- * New tnode. Decend one level
- */
-
- depth++;
- n=tn->child[cindex];
- tn=(struct tnode *)n;
- pend=tn->pos+tn->bits;
- putspace_seq(seq, indent);
seq_printf(seq, "\\--\n");
- indent+=3;
- cindex=0;
- }
- }
- else
- cindex++;
+ if (!n || !IS_TNODE(n)) {
+ seq_printf(seq, "------ trie is empty\n");
+ read_unlock(&fib_lock);
+ return;
+ }
+
+ printnode_seq(seq, indent, n, pend, cindex, 0);
+ pend = tn->pos+tn->bits;
+ putspace_seq(seq, indent);
+ seq_printf(seq, "\\--\n");
+ while (tn && cindex < (1 << tn->bits)) {
+ if (tn->child[cindex]) {
+ /* Got a child */
+
+ printnode_seq(seq, indent, tn->child[cindex], pend,
cindex, tn->bits);
+ if (IS_LEAF(tn->child[cindex])) {
+ cindex++;
+ } else {
/*
- * Test if we are done
+ * New tnode. Decend one level
*/
- while (cindex >= (1 << tn->bits)) {
+ depth++;
+ n = tn->child[cindex];
+ tn = (struct tnode *)n;
+ pend = tn->pos+tn->bits;
+ putspace_seq(seq, indent);
+ seq_printf(seq, "\\--\n");
+ indent += 3;
+ cindex = 0;
+ }
+ } else
+ cindex++;
- /*
- * Move upwards and test for root
- * pop off all traversed nodes
- */
-
- if (NODE_PARENT(tn) == NULL) {
- tn = NULL;
- n = NULL;
- break;
- }
- else {
- cindex =
tkey_extract_bits(tn->key, NODE_PARENT(tn)->pos, NODE_PARENT(tn)->bits);
- tn = NODE_PARENT(tn);
- cindex++;
- n=(struct node *)tn;
- pend=tn->pos+tn->bits;
- indent-=3;
- depth--;
- }
- }
+ /*
+ * Test if we are done
+ */
+
+ while (cindex >= (1 << tn->bits)) {
+ /*
+ * Move upwards and test for root
+ * pop off all traversed nodes
+ */
+
+ if (NODE_PARENT(tn) == NULL) {
+ tn = NULL;
+ n = NULL;
+ break;
}
+
+ cindex = tkey_extract_bits(tn->key,
NODE_PARENT(tn)->pos, NODE_PARENT(tn)->bits);
+ tn = NODE_PARENT(tn);
+ cindex++;
+ n = (struct node *)tn;
+ pend = tn->pos+tn->bits;
+ indent -= 3;
+ depth--;
}
- else n = NULL;
}
- else seq_printf(seq, "------ trie is empty\n");
read_unlock(&fib_lock);
}
static struct trie_stat *trie_stat_new(void)
{
- struct trie_stat *s = kmalloc(sizeof(struct trie_stat), GFP_KERNEL);
+ struct trie_stat *s;
int i;
+
+ s = kmalloc(sizeof(struct trie_stat), GFP_KERNEL);
+
+ if (!s)
+ return NULL;
- if(s) {
- s->totdepth = 0;
- s->maxdepth = 0;
- s->tnodes = 0;
- s->leaves = 0;
- s->nullpointers = 0;
-
- for(i=0; i< MAX_CHILDS; i++)
- s->nodesizes[i] = 0;
- }
+ s->totdepth = 0;
+ s->maxdepth = 0;
+ s->tnodes = 0;
+ s->leaves = 0;
+ s->nullpointers = 0;
+
+ for (i=0; i < MAX_CHILDS; i++)
+ s->nodesizes[i] = 0;
+
return s;
-}
+}
static struct trie_stat *trie_collect_stats(struct trie *t)
{
struct node *n=t->trie;
struct trie_stat *s = trie_stat_new();
int cindex = 0;
- int indent = 1;
int pend = 0;
int depth = 0;
+ struct tnode *tn = (struct tnode *)n;
+
+ if (!s || !n)
+ return s;
+
+ if (!IS_TNODE(n))
+ return s;
read_lock(&fib_lock);
- if (s) {
- if (n) {
- if (IS_TNODE(n)) {
- struct tnode *tn = (struct tnode *)n;
- pend=tn->pos+tn->bits;
- indent += 3;
+ pend = tn->pos+tn->bits;
+ s->nodesizes[tn->bits]++;
+ depth++;
+
+ while (tn && cindex < (1 << tn->bits)) {
+ if (tn->child[cindex]) {
+ /* Got a child */
+
+ if (IS_LEAF(tn->child[cindex])) {
+ cindex++;
+
+ /* stats */
+ if (depth > s->maxdepth)
+ s->maxdepth = depth;
+ s->totdepth += depth;
+ s->leaves++;
+ } else {
+ /*
+ * New tnode. Decend one level
+ */
+
+ s->tnodes++;
s->nodesizes[tn->bits]++;
depth++;
+
+ n = tn->child[cindex];
+ tn = (struct tnode *)n;
+ pend = tn->pos+tn->bits;
- while (tn && cindex < (1 << tn->bits)) {
- if (tn->child[cindex]) {
- /* Got a child */
-
- if (IS_LEAF(tn->child[cindex]))
{
- cindex++;
-
- /* stats */
- if (depth > s->maxdepth)
- s->maxdepth =
depth;
- s->totdepth += depth;
- s->leaves++;
- }
-
- else {
- /*
- * New tnode. Decend
one level
- */
-
- s->tnodes++;
-
s->nodesizes[tn->bits]++;
- depth++;
-
- n = tn->child[cindex];
- tn = (struct tnode *)n;
- pend = tn->pos+tn->bits;
-
- indent += 3;
- cindex = 0;
- }
- }
- else {
- cindex++;
- s->nullpointers++;
- }
-
- /*
- * Test if we are done
- */
-
- while (cindex >= (1 << tn->bits)) {
-
- /*
- * Move upwards and test for
root
- * pop off all traversed nodes
- */
-
-
- if (NODE_PARENT(tn) == NULL) {
- tn = NULL;
- n = NULL;
- break;
- }
- else {
- cindex =
tkey_extract_bits(tn->key, NODE_PARENT(tn)->pos, NODE_PARENT(tn)->bits);
- tn = NODE_PARENT(tn);
- cindex++;
- n = (struct node *)tn;
- pend=tn->pos+tn->bits;
- indent -= 3;
- depth--;
- }
- }
- }
+ cindex = 0;
}
- else n = NULL;
+ } else {
+ cindex++;
+ s->nullpointers++;
}
+
+ /*
+ * Test if we are done
+ */
+
+ while (NODE_PARENT(tn) && cindex >= (1 << tn->bits)) {
+ /*
+ * Move upwards and pop off all traversed nodes
+ */
+
+ cindex = tkey_extract_bits(tn->key,
NODE_PARENT(tn)->pos, NODE_PARENT(tn)->bits) + 1;
+ tn = NODE_PARENT(tn);
+ pend = tn->pos + tn->bits;
+ depth--;
+ }
}
read_unlock(&fib_lock);
@@ -2357,17 +2293,22 @@ static struct fib_alias *fib_triestat_ge
static void *fib_triestat_seq_start(struct seq_file *seq, loff_t *pos)
{
- void *v = NULL;
+ if (!ip_fib_main_table)
+ return NULL;
- if (ip_fib_main_table)
- v = *pos ? fib_triestat_get_next(seq) : SEQ_START_TOKEN;
- return v;
+ if (*pos)
+ return fib_triestat_get_next(seq);
+ else
+ return SEQ_START_TOKEN;
}
static void *fib_triestat_seq_next(struct seq_file *seq, void *v, loff_t *pos)
{
++*pos;
- return v == SEQ_START_TOKEN ? fib_triestat_get_first(seq) :
fib_triestat_get_next(seq);
+ if (v == SEQ_START_TOKEN)
+ return fib_triestat_get_first(seq);
+ else
+ return fib_triestat_get_next(seq);
}
static void fib_triestat_seq_stop(struct seq_file *seq, void *v)
@@ -2375,7 +2316,7 @@ static void fib_triestat_seq_stop(struct
}
-/*
+/*
* This outputs /proc/net/fib_triestats
*
* It always works in backward compatibility mode.
@@ -2386,24 +2327,26 @@ static void collect_and_show(struct trie
{
int bytes = 0; /* How many bytes are used, a ref is 4 bytes */
int i, max, pointers;
- struct trie_stat *stat;
+ struct trie_stat *stat;
int avdepth;
stat = trie_collect_stats(t);
- bytes=0;
+ bytes = 0;
seq_printf(seq, "trie=%p\n", t);
if (stat) {
if (stat->leaves)
- avdepth=stat->totdepth*100 / stat->leaves;
+ avdepth = stat->totdepth*100 / stat->leaves;
else
- avdepth=0;
- seq_printf(seq, "Aver depth: %d.%02d\n", avdepth / 100, avdepth
% 100 );
+ avdepth = 0;
+
+ seq_printf(seq, "Aver depth: %d.%02d\n", avdepth / 100, avdepth
% 100);
seq_printf(seq, "Max depth: %4d\n", stat->maxdepth);
seq_printf(seq, "Leaves: %d\n", stat->leaves);
bytes += sizeof(struct leaf) * stat->leaves;
+
seq_printf(seq, "Internal nodes: %d\n", stat->tnodes);
bytes += sizeof(struct tnode) * stat->tnodes;
@@ -2413,14 +2356,16 @@ static void collect_and_show(struct trie
max--;
pointers = 0;
- for (i = 1; i <= max; i++)
+ for (i = 1; i <= max; i++)
if (stat->nodesizes[i] != 0) {
seq_printf(seq, " %d: %d", i,
stat->nodesizes[i]);
pointers += (1<<i) * stat->nodesizes[i];
}
+
+ bytes += sizeof(struct node *) * pointers;
+
seq_printf(seq, "\n");
seq_printf(seq, "Pointers: %d\n", pointers);
- bytes += sizeof(struct node *) * pointers;
seq_printf(seq, "Null ptrs: %d\n", stat->nullpointers);
seq_printf(seq, "Total size: %d kB\n", bytes / 1024);
@@ -2444,19 +2389,17 @@ static void collect_and_show(struct trie
static int fib_triestat_seq_show(struct seq_file *seq, void *v)
{
char bf[128];
-
+
if (v == SEQ_START_TOKEN) {
seq_printf(seq, "Basic info: size of leaf: %Zd bytes, size of
tnode: %Zd bytes.\n",
sizeof(struct leaf), sizeof(struct tnode));
- if (trie_local)
+ if (trie_local)
collect_and_show(trie_local, seq);
- if (trie_main)
+ if (trie_main)
collect_and_show(trie_main, seq);
- }
- else {
- snprintf(bf, sizeof(bf),
- "*\t%08X\t%08X", 200, 400);
+ } else {
+ snprintf(bf, sizeof(bf), "*\t%08X\t%08X", 200, 400);
seq_printf(seq, "%-127s\n", bf);
}
@@ -2473,24 +2416,20 @@ static struct seq_operations fib_triesta
static int fib_triestat_seq_open(struct inode *inode, struct file *file)
{
struct seq_file *seq;
- int rc = -ENOMEM;
+ int err = -ENOMEM;
- rc = seq_open(file, &fib_triestat_seq_ops);
- if (rc)
- goto out_kfree;
+ err = seq_open(file, &fib_triestat_seq_ops);
+ if (!err)
+ seq = file->private_data;
- seq = file->private_data;
-out:
- return rc;
-out_kfree:
- goto out;
+ return err;
}
static struct file_operations fib_triestat_seq_fops = {
.owner = THIS_MODULE,
- .open = fib_triestat_seq_open,
- .read = seq_read,
- .llseek = seq_lseek,
+ .open = fib_triestat_seq_open,
+ .read = seq_read,
+ .llseek = seq_lseek,
.release = seq_release_private,
};
@@ -2518,22 +2457,27 @@ static struct fib_alias *fib_trie_get_ne
static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
{
- void *v = NULL;
+ if (!ip_fib_main_table)
+ return NULL;
- if (ip_fib_main_table)
- v = *pos ? fib_trie_get_next(seq) : SEQ_START_TOKEN;
- return v;
+ if (*pos)
+ return fib_trie_get_next(seq);
+ else
+ return SEQ_START_TOKEN;
}
static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
{
++*pos;
- return v == SEQ_START_TOKEN ? fib_trie_get_first(seq) :
fib_trie_get_next(seq);
+ if (v == SEQ_START_TOKEN)
+ return fib_trie_get_first(seq);
+ else
+ return fib_trie_get_next(seq);
+
}
static void fib_trie_seq_stop(struct seq_file *seq, void *v)
{
-
}
/*
@@ -2548,14 +2492,12 @@ static int fib_trie_seq_show(struct seq_
char bf[128];
if (v == SEQ_START_TOKEN) {
- if (trie_local)
+ if (trie_local)
trie_dump_seq(seq, trie_local);
- if (trie_main)
+ if (trie_main)
trie_dump_seq(seq, trie_main);
- }
-
- else {
+ } else {
snprintf(bf, sizeof(bf),
"*\t%08X\t%08X", 200, 400);
seq_printf(seq, "%-127s\n", bf);
@@ -2578,20 +2520,18 @@ static int fib_trie_seq_open(struct inod
rc = seq_open(file, &fib_trie_seq_ops);
if (rc)
- goto out_kfree;
+ goto out;
- seq = file->private_data;
+ seq = file->private_data;
out:
return rc;
-out_kfree:
- goto out;
}
static struct file_operations fib_trie_seq_fops = {
.owner = THIS_MODULE,
- .open = fib_trie_seq_open,
- .read = seq_read,
- .llseek = seq_lseek,
+ .open = fib_trie_seq_open,
+ .read = seq_read,
+ .llseek = seq_lseek,
.release = seq_release_private,
};
-
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
