)]}' { "commit": "bbe34cf8a1a2cc174e6516fc230b91b531da7ddf", "tree": "37be9ef58a6dbe2297cb21c611d604da72f97aa6", "parents": [ "84557783c5574f436826d88cd1bd035f20a4427f" ], "author": { "name": "baker.zhang", "email": "baker.kernel@gmail.com", "time": "Tue Oct 01 07:45:09 2013 +0800" }, "committer": { "name": "David S. Miller", "email": "davem@davemloft.net", "time": "Wed Oct 02 16:37:15 2013 -0400" }, "message": "fib_trie: avoid a redundant bit judgement in inflate\n\nBecause \u0027node\u0027 is the i\u0027st child of \u0027oldnode\u0027,\nthus, here \u0027i\u0027 equals\ntkey_extract_bits(node-\u003ekey, oldtnode-\u003epos, oldtnode-\u003ebits)\n\nwe just get 1 more bit,\nand need not care the detail value of this bits.\n\nI apologize for the mistake.\n\nI generated the patch on a branch version,\nand did not notice the put_child has been changed.\n\nI have redone the test on HEAD version with my patch.\n\ntwo cases are used.\ncase 1. inflate a node which has a leaf child node.\ncase 2: inflate a node which has a an child node with skipped bits\n\ntest env:\n ip link set eth0 up\n ip a add dev eth0 192.168.11.1/32\nhere, we just focus on route table(MAIN),\nso I use a \"192.168.11.1/32\" address to simplify the test case.\n\ncall trace:\n+ fib_insert_node\n+ + trie_rebalance\n+ + + resize\n+ + + + inflate\n\nTest case 1: inflate a node which has a leaf child node.\n\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\nstep 1. prepare a fib trie\n------------------------------------------\n ip r a 192.168.0.0/24 via 192.168.11.1\n ip r a 192.168.1.0/24 via 192.168.11.1\n\nwe get a fib trie.\nroot@baker:~# cat /proc/net/fib_trie\nMain:\n +-- 192.168.0.0/23 1 0 0\n |-- 192.168.0.0\n /24 universe UNICAST\n |-- 192.168.1.0\n /24 universe UNICAST\nLocal:\n.....\n\nstep 2. Add the third route\n------------------------------------------\nroot@baker:~# ip r a 192.168.2.0/24 via 192.168.11.1\n\nA fib_trie leaf will be inserted in fib_insert_node before trie_rebalance.\n\nFor function \u0027inflate\u0027:\n\u0027inflate\u0027 is called with following trie.\n +-- 192.168.0.0/22 1 1 0 \u003c\u003d\u003d\u003d tn node\n +-- 192.168.0.0/23 1 0 0 \u003c\u003d\u003d node a\n |-- 192.168.0.0\n /24 universe UNICAST\n |-- 192.168.1.0\n /24 universe UNICAST\n |-- 192.168.2.0 \u003c\u003d\u003d leaf(node b)\n\nWhen process node b, which is a leaf. here:\ni is 1,\nnode key \"192.168.2.0\"\noldnode is (pos:22, bits:1)\n\nunpatch source:\ntkey_extract_bits(node-\u003ekey, oldtnode-\u003epos + oldtnode-\u003ebits, 1)\nit equals:\ntkey_extract_bits(\"192.168,2,0\", 22 + 1, 1)\n\nthus got 0, and call put_child(tn, 2*i, node); \u003c\u003d\u003d 2*i\u003d2.\n\npatched source:\ntkey_extract_bits(node-\u003ekey, oldtnode-\u003epos, oldtnode-\u003ebits + 1),\ntkey_extract_bits(\"192.168,2,0\", 22, 1 + 1) \u003c\u003d\u003d get 2.\n\nTest case 2: inflate a node which has a an child node with skipped bits\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\nstep 1. prepare a fib trie.\n ip link set eth0 up\n ip a add dev eth0 192.168.11.1/32\n ip r a 192.168.128.0/24 via 192.168.11.1\n ip r a 192.168.0.0/24 via 192.168.11.1\n ip r a 192.168.16.0/24 via 192.168.11.1\n ip r a 192.168.32.0/24 via 192.168.11.1\n ip r a 192.168.48.0/24 via 192.168.11.1\n ip r a 192.168.144.0/24 via 192.168.11.1\n ip r a 192.168.160.0/24 via 192.168.11.1\n ip r a 192.168.176.0/24 via 192.168.11.1\n\ncheck:\nroot@baker:~# cat /proc/net/fib_trie\nMain:\n +-- 192.168.0.0/16 1 0 0\n +-- 192.168.0.0/18 2 0 0\n |-- 192.168.0.0\n /24 universe UNICAST\n |-- 192.168.16.0\n /24 universe UNICAST\n |-- 192.168.32.0\n /24 universe UNICAST\n |-- 192.168.48.0\n /24 universe UNICAST\n +-- 192.168.128.0/18 2 0 0\n |-- 192.168.128.0\n /24 universe UNICAST\n |-- 192.168.144.0\n /24 universe UNICAST\n |-- 192.168.160.0\n /24 universe UNICAST\n |-- 192.168.176.0\n /24 universe UNICAST\nLocal:\n ...\n\nstep 2. add a route to trigger inflate.\n ip r a 192.168.96.0/24 via 192.168.11.1\n\nThis command will call serveral times inflate.\nIn the first time, the fib_trie is:\n________________________\n+-- 192.168.128.0/(16, 1) \u003c\u003d\u003d tn node\n +-- 192.168.0.0/(17, 1) \u003c\u003d\u003d node a\n +-- 192.168.0.0/(18, 2)\n |-- 192.168.0.0\n |-- 192.168.16.0\n |-- 192.168.32.0\n |-- 192.168.48.0\n |-- 192.168.96.0\n +-- 192.168.128.0/(18, 2) \u003c\u003d\u003d node b.\n |-- 192.168.128.0\n |-- 192.168.144.0\n |-- 192.168.160.0\n |-- 192.168.176.0\n\nNOTE: node b is a interal node with skipped bits.\nhere,\ni:1,\nnode-\u003ekey \"192.168.128.0\",\noldnode:(pos:16, bits:1)\nso\ntkey_extract_bits(node-\u003ekey, oldtnode-\u003epos + oldtnode-\u003ebits, 1)\nit equals:\ntkey_extract_bits(\"192.168,128,0\", 16 + 1, 1) \u003c\u003d\u003d\u003d 0\n\ntkey_extract_bits(node-\u003ekey, oldtnode-\u003epos, oldtnode-\u003ebits, 1)\nit equals:\ntkey_extract_bits(\"192.168,128,0\", 16, 1+1) \u003c\u003d\u003d\u003d 2\n\n2*i + 0 \u003d\u003d 2, so the result is same.\n\nSigned-off-by: baker.zhang \u003cbaker.kernel@gmail.com\u003e\nSigned-off-by: David S. Miller \u003cdavem@davemloft.net\u003e\n", "tree_diff": [ { "type": "modify", "old_id": "3df6d3edb2a15a98cb0e90a4e5ed935f42f15f1c", "old_mode": 33188, "old_path": "net/ipv4/fib_trie.c", "new_id": "45c74ba039709681e48a219163a74aec737995f5", "new_mode": 33188, "new_path": "net/ipv4/fib_trie.c" } ] }