netdev - Re: [PATCH RFC net-next] net/fib: Poptrie based FIB lookup

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20180827092420.791bb1ad@shemminger-XPS-13-9360>
Date:   Mon, 27 Aug 2018 09:24:20 -0700
From:   Stephen Hemminger <stephen@...workplumber.org>
To:     "Md. Islam" <mislam4@...t.edu>
Cc:     Netdev <netdev@...r.kernel.org>,
        David Miller <davem@...emloft.net>,
        David Ahern <dsahern@...il.com>,
        Eric Dumazet <edumazet@...gle.com>,
        Alexey Kuznetsov <kuznet@....inr.ac.ru>,
        makita.toshiaki@....ntt.co.jp, panda@...go.wide.ad.jp,
        yasuhiro.ohara@....com, john.fastabend@...il.com,
        alexei.starovoitov@...il.com
Subject: Re: [PATCH RFC net-next] net/fib: Poptrie based FIB lookup

On Sun, 26 Aug 2018 22:28:48 -0400
"Md. Islam" <mislam4@...t.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().
> 
> 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]. It [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


I am glad to see more research in to lookup speed. Here are some non-technical
feedback. Looking deeper takes longer.

The license in github version is not compatiable with GPL. If you based your
code off that, you need to get approval from original copyright holder.

The code is not formatted according to current kernel coding style.
Please use checkpatch to see what the issues are.

It is preferred that a function return a value, rather than being void
and returing result by reference. Example:

> +
> +/*We assume that pt->root is not NULL*/
> +void poptrie_lookup(struct poptrie *pt, __be32 dest, struct net_device **dev)
> +{
...

> +        *dev = get_fib(&pt->nhs, fib_index);
> +        return;
> +    }

Why not?
static struct net_device *poptrie_lookup(struct poptrie *pt, __be32 dest)

Also, as Dave mentioned any implementation needs to handle multiple namespaces
and routing tables.

Could this alternative lookup be enabled via sysctl at runtime rather than kernel config?