OpenWrt – Blame information for rev 1
?pathlinks?
Rev | Author | Line No. | Line |
---|---|---|---|
1 | office | 1 | From: Alexander Duyck <alexander.h.duyck@redhat.com> |
2 | Date: Wed, 31 Dec 2014 10:56:00 -0800 |
||
3 | Subject: [PATCH] fib_trie: Optimize fib_find_node |
||
4 | |||
5 | This patch makes use of the same features I made use of for |
||
6 | fib_table_lookup to streamline fib_find_node. The resultant code should be |
||
7 | smaller and run faster than the original. |
||
8 | |||
9 | Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com> |
||
10 | Signed-off-by: David S. Miller <davem@davemloft.net> |
||
11 | --- |
||
12 | |||
13 | --- a/net/ipv4/fib_trie.c |
||
14 | +++ b/net/ipv4/fib_trie.c |
||
15 | @@ -892,28 +892,34 @@ static void insert_leaf_info(struct hlis |
||
16 | } |
||
17 | |||
18 | /* rcu_read_lock needs to be hold by caller from readside */ |
||
19 | - |
||
20 | static struct tnode *fib_find_node(struct trie *t, u32 key) |
||
21 | { |
||
22 | struct tnode *n = rcu_dereference_rtnl(t->trie); |
||
23 | - int pos = 0; |
||
24 | |||
25 | - while (n && IS_TNODE(n)) { |
||
26 | - if (tkey_sub_equals(n->key, pos, n->pos-pos, key)) { |
||
27 | - pos = n->pos + n->bits; |
||
28 | - n = tnode_get_child_rcu(n, |
||
29 | - tkey_extract_bits(key, |
||
30 | - n->pos, |
||
31 | - n->bits)); |
||
32 | - } else |
||
33 | + while (n) { |
||
34 | + unsigned long index = get_index(key, n); |
||
35 | + |
||
36 | + /* This bit of code is a bit tricky but it combines multiple |
||
37 | + * checks into a single check. The prefix consists of the |
||
38 | + * prefix plus zeros for the bits in the cindex. The index |
||
39 | + * is the difference between the key and this value. From |
||
40 | + * this we can actually derive several pieces of data. |
||
41 | + * if !(index >> bits) |
||
42 | + * we know the value is cindex |
||
43 | + * else |
||
44 | + * we have a mismatch in skip bits and failed |
||
45 | + */ |
||
46 | + if (index >> n->bits) |
||
47 | + return NULL; |
||
48 | + |
||
49 | + /* we have found a leaf. Prefixes have already been compared */ |
||
50 | + if (IS_LEAF(n)) |
||
51 | break; |
||
52 | - } |
||
53 | - /* Case we have found a leaf. Compare prefixes */ |
||
54 | |||
55 | - if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) |
||
56 | - return n; |
||
57 | + n = rcu_dereference_rtnl(n->child[index]); |
||
58 | + } |
||
59 | |||
60 | - return NULL; |
||
61 | + return n; |
||
62 | } |
||
63 | |||
64 | static void trie_rebalance(struct trie *t, struct tnode *tn) |