[PATCH net-next] fib_trie: only calc for the un-first node
From: "baker.zhang"
This is a enhancement.
for the first node in fib_trie, newpos is 0, bit is 1.
Only for the leaf or node with unmatched key need calc pos.
Signed-off-by: baker.zhang
---
net/ipv4/fib_trie.c |6 +-
1 file changed, 1 insertion(+), 5 deletions(-)
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 45c74ba..ec9a9ef 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -1117,12 +1117,8 @@ static struct list_head *fib_insert_node(struct trie *t,
u32 key, int plen)
* first tnode need some special handling
*/
- if (tp)
- pos = tp->pos+tp->bits;
- else
- pos = 0;
-
if (n) {
+ pos = tp ? tp->pos+tp->bits : 0;
newpos = tkey_mismatch(key, pos, n->key);
tn = tnode_new(n->key, newpos, 1);
} else {
--
1.7.9.5
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[PATCH net-next] fib_trie: avoid a redundant bit judgement in inflate
From: "baker.zhang"
Because 'node' is the i'st child of 'oldnode',
thus, here 'i' equals
tkey_extract_bits(node->key, oldtnode->pos, oldtnode->bits)
we just get 1 more bit,
and need not care the detail value of this bits.
Signed-off-by: baker.zhang
---
net/ipv4/fib_trie.c | 9 +++--
1 file changed, 3 insertions(+), 6 deletions(-)
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 3df6d3e..92a4c7f8 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -762,12 +762,9 @@ static struct tnode *inflate(struct trie *t, struct tnode
*tn)
if (IS_LEAF(node) || ((struct tnode *) node)->pos >
tn->pos + tn->bits - 1) {
- if (tkey_extract_bits(node->key,
- oldtnode->pos + oldtnode->bits,
- 1) == 0)
- put_child(tn, 2*i, node);
- else
- put_child(tn, 2*i+1, node);
+ put_child(t, tn,
+ tkey_extract_bits(node->key, oldtnode->pos,
oldtnode->bits + 1),
+ node);
continue;
}
--
1.8.1.2
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[PATCH V2 net-next] fib_trie: avoid a redundant bit judgement in inflate
From: "baker.zhang"
Because 'node' is the i'st child of 'oldnode',
thus, here 'i' equals
tkey_extract_bits(node->key, oldtnode->pos, oldtnode->bits)
we just get 1 more bit,
and need not care the detail value of this bits.
Signed-off-by: baker.zhang
---
net/ipv4/fib_trie.c | 9 +++--
1 file changed, 3 insertions(+), 6 deletions(-)
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 3df6d3e..45c74ba 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -762,12 +762,9 @@ static struct tnode *inflate(struct trie *t, struct tnode
*tn)
if (IS_LEAF(node) || ((struct tnode *) node)->pos >
tn->pos + tn->bits - 1) {
- if (tkey_extract_bits(node->key,
- oldtnode->pos + oldtnode->bits,
- 1) == 0)
- put_child(tn, 2*i, node);
- else
- put_child(tn, 2*i+1, node);
+ put_child(tn,
+ tkey_extract_bits(node->key, oldtnode->pos,
oldtnode->bits + 1),
+ node);
continue;
}
--
1.8.1.2
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[PATCH V3 net-next] fib_trie: avoid a redundant bit judgement in inflate
From: "baker.zhang"
Because 'node' is the i'st child of 'oldnode',
thus, here 'i' equals
tkey_extract_bits(node->key, oldtnode->pos, oldtnode->bits)
we just get 1 more bit,
and need not care the detail value of this bits.
I apologize for the mistake.
I generated the patch on a branch version,
and did not notice the put_child has been changed.
I have redone the test on HEAD version with my patch.
two cases are used.
case 1. inflate a node which has a leaf child node.
case 2: inflate a node which has a an child node with skipped bits
test env:
ip link set eth0 up
ip a add dev eth0 192.168.11.1/32
here, we just focus on route table(MAIN),
so I use a "192.168.11.1/32" address to simplify the test case.
call trace:
+ fib_insert_node
+ + trie_rebalance
+ + + resize
+ + + + inflate
Test case 1: inflate a node which has a leaf child node.
===
step 1. prepare a fib trie
--
ip r a 192.168.0.0/24 via 192.168.11.1
ip r a 192.168.1.0/24 via 192.168.11.1
we get a fib trie.
root@baker:~# cat /proc/net/fib_trie
Main:
+-- 192.168.0.0/23 1 0 0
|-- 192.168.0.0
/24 universe UNICAST
|-- 192.168.1.0
/24 universe UNICAST
Local:
.
step 2. Add the third route
--
root@baker:~# ip r a 192.168.2.0/24 via 192.168.11.1
A fib_trie leaf will be inserted in fib_insert_node before trie_rebalance.
For function 'inflate':
'inflate' is called with following trie.
+-- 192.168.0.0/22 1 1 0 <=== tn node
+-- 192.168.0.0/23 1 0 0<== node a
|-- 192.168.0.0
/24 universe UNICAST
|-- 192.168.1.0
/24 universe UNICAST
|-- 192.168.2.0 <== leaf(node b)
When process node b, which is a leaf. here:
i is 1,
node key "192.168.2.0"
oldnode is (pos:22, bits:1)
unpatch source:
tkey_extract_bits(node->key, oldtnode->pos + oldtnode->bits, 1)
it equals:
tkey_extract_bits("192.168,2,0", 22 + 1, 1)
thus got 0, and call put_child(tn, 2*i, node); <== 2*i=2.
patched source:
tkey_extract_bits(node->key, oldtnode->pos, oldtnode->bits + 1),
tkey_extract_bits("192.168,2,0", 22, 1 + 1) <== get 2.
Test case 2: inflate a node which has a an child node with skipped bits
==
step 1. prepare a fib trie.
ip link set eth0 up
ip a add dev eth0 192.168.11.1/32
ip r a 192.168.128.0/24 via 192.168.11.1
ip r a 192.168.0.0/24 via 192.168.11.1
ip r a 192.168.16.0/24 via 192.168.11.1
ip r a 192.168.32.0/24 via 192.168.11.1
ip r a 192.168.48.0/24 via 192.168.11.1
ip r a 192.168.144.0/24 via 192.168.11.1
ip r a 192.168.160.0/24 via 192.168.11.1
ip r a 192.168.176.0/24 via 192.168.11.1
check:
root@baker:~# cat /proc/net/fib_trie
Main:
+-- 192.168.0.0/16 1 0 0
+-- 192.168.0.0/18 2 0 0
|-- 192.168.0.0
/24 universe UNICAST
|-- 192.168.16.0
/24 universe UNICAST
|-- 192.168.32.0
/24 universe UNICAST
|-- 192.168.48.0
/24 universe UNICAST
+-- 192.168.128.0/18 2 0 0
|-- 192.168.128.0
/24 universe UNICAST
|-- 192.168.144.0
/24 universe UNICAST
|-- 192.168.160.0
/24 universe UNICAST
|-- 192.168.176.0
/24 universe UNICAST
Local:
...
step 2. add a route to trigger inflate.
ip r a 192.168.96.0/24 via 192.168.11.1
This command will call serveral times inflate.
In the first time, the fib_trie is:
+-- 192.168.128.0/(16, 1) <== tn node
+-- 192.168.0.0/(17, 1) <== node a
+-- 192.168.0.0/(18, 2)
|-- 192.168.0.0
|-- 192.168.16.0
|-- 192.168.32.0
|-- 192.168.48.0
|-- 192.168.96.0
+-- 192.168.128.0/(18, 2) <== node b.
|-- 192.168.128.0
|-- 192.168.144.0
|-- 192.168.160.0
|-- 192.168.176.0
NOTE: node b is a interal node with skipped bits.
here,
i:1,
node->key "192.168.128.0",
oldnode:(pos:16, bits:1)
so
tkey_extract_bits(node->key, oldtnode->pos + oldtnode->bits, 1)
it equals:
tkey_extract_bits("192.168,128,0", 16 + 1, 1) <=== 0
tkey_extract_bits(node->key, oldtnode->pos, oldtnode->bits, 1)
it equals:
tkey_extract_bits("192.168,128,0", 16, 1+1) <=== 2
2*i + 0 == 2, so the result is same.
Signed-off-by: baker.zhang
---
net/ipv4/fib_trie.c | 9 +++--
1 file changed, 3 insertions(+), 6 deletions(-)
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 3df6d3e..45c74ba 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -762,12 +762,9 @@ static struct tnode *inflate(struct trie *t, struct tnode
*tn)
if (IS_LEAF(node) || ((struct tnode *) node)->pos >
tn->pos + tn->bits - 1) {
- if (tkey_extract_bits(node->key,
- oldtnode->pos + oldtnode->bits,
- 1) == 0)
-
[PATCH v3 net-next] xfrm: Add check to prevent un-complete key manager
From: Baker Zhang
"acquire" and "compile_policy" callbacks are necessary for a key manager.
Signed-off-by: Baker Zhang
---
Thanks for all reply.
V1:
For current kernel source, there is no problem.
In our vpn product, we need a xfrm_km in kernel module
to monitor the xfrm state change.
thus, the 'acquire' and 'compile_policy' may be NULL.
So I think we should do the check before use it.
V2:
Align the continuation line according the networking coding style.
V3:
Add check to prevent un-complete key manager at register time.
net/xfrm/xfrm_state.c | 3 +++
1 file changed, 3 insertions(+)
diff --git a/net/xfrm/xfrm_state.c b/net/xfrm/xfrm_state.c
index b9c3f9e..178283e 100644
--- a/net/xfrm/xfrm_state.c
+++ b/net/xfrm/xfrm_state.c
@@ -1806,6 +1806,9 @@ static DEFINE_SPINLOCK(xfrm_km_lock);
int xfrm_register_km(struct xfrm_mgr *km)
{
+ if (km->acquire == NULL || km->compile_policy == NULL)
+ return -EINVAL;
+
spin_lock_bh(&xfrm_km_lock);
list_add_tail_rcu(&km->list, &xfrm_km_list);
spin_unlock_bh(&xfrm_km_lock);
--
1.8.3.2
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[PATCH net-next] fib_trie: remove duplicated rcu lock
From: "baker.zhang"
fib_table_lookup has included the rcu lock protection.
Signed-off-by: baker.zhang
---
net/ipv4/fib_frontend.c | 4
1 file changed, 4 deletions(-)
diff --git a/net/ipv4/fib_frontend.c b/net/ipv4/fib_frontend.c
index b3f627a..0e9127d 100644
--- a/net/ipv4/fib_frontend.c
+++ b/net/ipv4/fib_frontend.c
@@ -170,12 +170,10 @@ static inline unsigned int __inet_dev_addr_type(struct
net *net,
local_table = fib_get_table(net, RT_TABLE_LOCAL);
if (local_table) {
ret = RTN_UNICAST;
- rcu_read_lock();
if (!fib_table_lookup(local_table, &fl4, &res,
FIB_LOOKUP_NOREF)) {
if (!dev || dev == res.fi->fib_dev)
ret = res.type;
}
- rcu_read_unlock();
}
return ret;
}
@@ -933,7 +931,6 @@ static void nl_fib_lookup(struct fib_result_nl *frn, struct
fib_table *tb)
local_bh_disable();
frn->tb_id = tb->tb_id;
- rcu_read_lock();
frn->err = fib_table_lookup(tb, &fl4, &res, FIB_LOOKUP_NOREF);
if (!frn->err) {
@@ -942,7 +939,6 @@ static void nl_fib_lookup(struct fib_result_nl *frn, struct
fib_table *tb)
frn->type = res.type;
frn->scope = res.scope;
}
- rcu_read_unlock();
local_bh_enable();
}
}
--
1.8.1.2
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[PATCH v2 net-next] fib_trie: remove duplicated rcu lock
From: "baker.zhang"
fib_table_lookup has included the rcu lock protection.
Signed-off-by: baker.zhang
---
Thanks for Eric Dumazet's review.
The V1 patch remove a necessary rcu read lock.
net/ipv4/fib_frontend.c | 2 --
1 file changed, 2 deletions(-)
diff --git a/net/ipv4/fib_frontend.c b/net/ipv4/fib_frontend.c
index b3f627a..d846304 100644
--- a/net/ipv4/fib_frontend.c
+++ b/net/ipv4/fib_frontend.c
@@ -933,7 +933,6 @@ static void nl_fib_lookup(struct fib_result_nl *frn, struct
fib_table *tb)
local_bh_disable();
frn->tb_id = tb->tb_id;
- rcu_read_lock();
frn->err = fib_table_lookup(tb, &fl4, &res, FIB_LOOKUP_NOREF);
if (!frn->err) {
@@ -942,7 +941,6 @@ static void nl_fib_lookup(struct fib_result_nl *frn, struct
fib_table *tb)
frn->type = res.type;
frn->scope = res.scope;
}
- rcu_read_unlock();
local_bh_enable();
}
}
--
1.8.1.2
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
