On Sun, 26 Aug 2018 22:13:53 -0400 "Md. Islam" <misl...@kent.edu> wrote:
> This patch implements Poptrie [1] based FIB lookup. It exhibits pretty > impressive lookup performance compared to LC-trie. This poptrie > implementation however somewhat deviates from the original > implementation [2]. I tested this patch very rigorously with several > FIB tables containing half a million routes. I got same result as > LC-trie based fib_lookup(). It sounds really promising performance wise. The article [1] claim lookup speeds up-to 240 Million lookups per second. That is a crazy speed. This is 4.166 nanosec per lookup (1/240*1000), and their test CPU is 3.9GHz, which gives them 16.25 CPU cycles for a lookup, with 3 insn per cycle, that gives them max 48 perfectly pipelined instructions per lookup. > Poptrie is intended to work in conjunction with LC-trie (not replace > it). It is primarily designed to overcome many issues of TCAM based > router [1]. [1] shows that the Poptrie can achieve very impressive > lookup performance on CPU. This patch will mainly be used by XDP > forwarding. > > 1. Asai, Hirochika, and Yasuhiro Ohara. "Poptrie: A compressed trie > with population count for fast and scalable software IP routing table > lookup." ACM SIGCOMM Computer Communication Review. 2015. > > 2. https://github.com/pixos/poptrie > > From c5e05ea66b06eb9313749bc8969b4c2798fcf96a Mon Sep 17 00:00:00 2001 > From: tamimcse <ta...@csebuet.org> > Date: Sun, 26 Aug 2018 21:12:38 -0400 > Subject: [PATCH] Implented Poptrie This above "commit-info" should not be part of the patch description. > Signed-off-by: tamimcse <ta...@csebuet.org> Use you real/full name here. > --- First of order of business: You need to conform to the kernels coding standards! https://www.kernel.org/doc/html/v4.18/process/coding-style.html There is a script avail to check this called: scripts/checkpatch.pl It summary says: total: 139 errors, 238 warnings, 6 checks, 372 lines checked (Not good, more error+warnings than lines...) Please fix up those... > include/net/ip_fib.h | 40 +++++++ > net/ipv4/Makefile | 2 +- > net/ipv4/fib_poptrie.c | 295 > +++++++++++++++++++++++++++++++++++++++++++++++++ > net/ipv4/fib_trie.c | 3 + > 4 files changed, 339 insertions(+), 1 deletion(-) > create mode 100644 net/ipv4/fib_poptrie.c [...] > diff --git a/net/ipv4/fib_poptrie.c b/net/ipv4/fib_poptrie.c > new file mode 100644 > index 0000000..b3a88ab > --- /dev/null > +++ b/net/ipv4/fib_poptrie.c > @@ -0,0 +1,295 @@ [....] > +/*Insert a new node at index*/ > +static void insert_chield_node(struct poptrie_node *node, > + char index) > +{ You are misspelling "child" as "chield" > + int i, j; > + struct poptrie_node *arr; > + int arr_size = (int)hweight64(node->nodevec); > + > + arr = kcalloc(arr_size + 1, sizeof(*arr), GFP_ATOMIC); > + for (i = 0, j = 0; i < (arr_size + 1); i++) { > + if (i != index && j < arr_size) > + arr[i] = node->chield_nodes[j++]; > + } > + > + kfree(node->chield_nodes); > + node->chield_nodes = arr; > +} [...] > +/*We assume that pt->root is not NULL*/ > +void poptrie_lookup(struct poptrie *pt, __be32 dest, struct net_device **dev) > +{ > + register u32 index; > + register u64 bitmap, bitmask; > + register unsigned long leaf_index; > + register unsigned long node_index; > + register struct poptrie_node *node = pt->root; > + register u8 fib_index = pt->def_nh; > + register u8 carry = 0; > + register u8 carry_bit = 2; Do you have performance data, that tell you that "register" is needed here? > + while (1) { > + /*Extract 6 bytes from dest */ > + if (likely(carry_bit != 8)) { > + index = ((dest & 252) >> carry_bit) | carry; > + carry = (dest & ((1 << carry_bit) - 1)) << (6 - carry_bit); > + carry_bit = carry_bit + 2; > + dest = dest >> 8; > + } else { > + index = carry; > + carry = 0; > + carry_bit = 2; > + } > + > + /*Create a bitmap based on the the extracted value*/ > + bitmap = 1ULL << index; > + bitmask = bitmap - 1; > + > + /*Find corresponding leaf*/ > + if (likely(node->vector & bitmap)) { > + leaf_index = hweight64(node->leafvec & bitmask); Just as help for reviewers, the popcnt instruction is here. hweight64 == popcnt > + if (!(node->leafvec & bitmap)) > + leaf_index--; > + fib_index = node->leaves[leaf_index]; > + } > + > + /*Find corresponding node*/ > + if (likely(node->nodevec & bitmap)) { > + node_index = hweight64(node->nodevec & bitmask); And here. > + node = &node->chield_nodes[node_index]; > + continue; > + } > + > + *dev = get_fib(&pt->nhs, fib_index); > + return; > + } > +} -- Best regards, Jesper Dangaard Brouer MSc.CS, Principal Kernel Engineer at Red Hat LinkedIn: http://www.linkedin.com/in/brouer