Eric Dumazet a écrit :
Stephen Hemminger a écrit :
Combine the prefix information and the leaf together into one
allocation. This is furthur simplified by converting the hlist
into a simple bitfield.
Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]>
This patch is experimental (ie it boots and loads routes), but
is slower for the 163,000 route dump test.
Its also very memory expensive. That was not Robert suggestion I believe.
Its suggestion is to embedd one info into each leaves.
Please find attached to this mail a preliminary and incomplete patch I
wrote this morning before coffee :), to get the idea.
Oops, patch reversed, sorry, and against another work pending in my tree.
Now time for cofee :)
--- net/ipv4/fib_trie.c.old
+++ net/ipv4/fib_trie.c
@@ -97,22 +97,30 @@
#define IS_LEAF(n) (n->parent & T_LEAF)
struct node {
- unsigned long parent;
- t_key key;
+ unsigned long parent;
+ t_key key;
};
struct leaf {
- unsigned long parent;
- t_key key;
- struct hlist_head list;
- struct rcu_head rcu;
+ unsigned long parent;
+ t_key key;
+ /*
+ * Because we have at least one info per leaf, we embedd one here
+ * to save some space and speedup lookups (sharing cache line)
+ * Note : not inside a structure so that we dont have holes on 64bit
+ */
+ int plen_iinfo;
+ struct list_head falh_iinfo;
+
+ struct hlist_head list;
+ struct rcu_head rcu;
};
struct leaf_info {
- struct hlist_node hlist;
- struct rcu_head rcu;
- int plen;
- struct list_head falh;
+ struct hlist_node hlist;
+ int plen;
+ struct list_head falh;
+ struct rcu_head rcu;
};
struct tnode {
@@ -373,11 +381,13 @@
call_rcu(&tn->rcu, __tnode_free_rcu);
}
-static struct leaf *leaf_new(void)
+static struct leaf *leaf_new(int plen)
{
struct leaf *l = kmalloc(sizeof(struct leaf), GFP_KERNEL);
if (l) {
l->parent = T_LEAF;
+ l->plen_iinfo = plen;
+ INIT_LIST_HEAD(&l->falh_iinfo);
INIT_HLIST_HEAD(&l->list);
}
return l;
@@ -899,7 +909,12 @@
static inline struct list_head * get_fa_head(struct leaf *l, int plen)
{
- struct leaf_info *li = find_leaf_info(l, plen);
+ struct leaf_info *li;
+
+ if (plen == l->plen_iinfo)
+ return &l->falh_iinfo;
+
+ li = find_leaf_info(l, plen);
if (!li)
return NULL;
@@ -1056,21 +1071,22 @@
goto done;
}
t->size++;
- l = leaf_new();
+ l = leaf_new(plen);
if (!l)
return NULL;
l->key = key;
- li = leaf_info_new(plen);
-
- if (!li) {
- tnode_free((struct tnode *) l);
- return NULL;
- }
+// li = leaf_info_new(plen);
- fa_head = &li->falh;
- insert_leaf_info(&l->list, li);
+// if (!li) {
+// tnode_free((struct tnode *) l);
+// return NULL;
+// }
+
+// fa_head = &li->falh;
+// insert_leaf_info(&l->list, li);
+ fa_head = &l->falh_iinfo;
if (t->trie && n == NULL) {
/* Case 2: n is NULL, and will just insert a new leaf */
@@ -1100,7 +1116,7 @@
}
if (!tn) {
- free_leaf_info(li);
+// free_leaf_info(li);
tnode_free((struct tnode *) l);
return NULL;
}
@@ -1624,7 +1640,7 @@
li = find_leaf_info(l, plen);
list_del_rcu(&fa->fa_list);
-
+// FIXME
if (list_empty(fa_head)) {
hlist_del_rcu(&li->hlist);
free_leaf_info(li);
@@ -2366,10 +2382,11 @@
seq_indent(seq, iter->depth);
seq_printf(seq, " |-- %d.%d.%d.%d\n", NIPQUAD(val));
for (i = 32; i >= 0; i--) {
- struct leaf_info *li = find_leaf_info(l, i);
- if (li) {
+// struct leaf_info *li = get_fa_head(l, i);
//find_leaf_info(l, i);
+ struct list_head *fa_head = get_fa_head(l, i);
+ if (fa_head) {
struct fib_alias *fa;
- list_for_each_entry_rcu(fa, &li->falh, fa_list)
{
+ list_for_each_entry_rcu(fa, fa_head, fa_list) {
seq_indent(seq, iter->depth+1);
seq_printf(seq, " /%d %s %s", i,
rtn_scope(fa->fa_scope),
@@ -2448,17 +2465,18 @@
return 0;
for (i=32; i>=0; i--) {
- struct leaf_info *li = find_leaf_info(l, i);
+ //struct leaf_info *li = find_leaf_info(l, i);
+ struct list_head *fa_head = get_fa_head(l, i);
struct fib_alias *fa;
__be32 mask, prefix;
- if (!li)
+ if (!fa_head)
continue;
- mask = inet_make_mask(li->plen);
+ mask = inet_make_mask(i);
prefix = htonl(l->key);
- list_for_each_entry_rcu(fa, &li->falh, fa_list) {
+ list_for_each_entry_rcu(fa, fa_head, fa_list) {
const struct fib_info *fi = fa->fa_info;
unsigned flags = fib_flag_trans(fa->fa_type, mask, fi);
