From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail.mhcomputing.net (master.mhcomputing.net [74.208.46.186]) by dpdk.org (Postfix) with ESMTP id EC9DFC81A for ; Mon, 22 Jun 2015 04:29:36 +0200 (CEST) Received: from [192.168.1.160] (99-34-229-174.lightspeed.sntcca.sbcglobal.net [99.34.229.174]) by mail.mhcomputing.net (Postfix) with ESMTPSA id 7D55980C003; Sun, 21 Jun 2015 19:27:01 -0700 (PDT) From: Matthew Hall Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: quoted-printable Date: Sun, 21 Jun 2015 19:29:33 -0700 Message-Id: <5A3882CB-0DE0-43DB-8DCA-051D561AA943@mhcomputing.net> To: "" Mime-Version: 1.0 (Mac OS X Mail 7.3 \(1878.6\)) X-Mailer: Apple Mail (2.1878.6) Subject: [dpdk-dev] rte_lpm with larger nexthops or another method? X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 22 Jun 2015 02:29:37 -0000 Hello, I have gone out on the internet for days looking at a bunch of different = radix tree implementations to see if I could figure a way to implement = my own tree, just to work around the really low 255 CIDR block = limitation in librte_lpm. Unfortunately every single one I could find = falls into one of these two annoying categories: 1) bloated with a lot of irrelevant kernel code I don't care about = (especially the Linux version but also the BSD one, which also makes a = weird assumption every address object stores its length in byte 0 of the = address struct). These are hard to convert into something that plays = nice with raw packet data. 2) very seemingly simple code, which breaks horribly if you try to add = IPv6 support (such as the radix tree from University of Michigan / LLVM = compiler benchmark suite, and the one from the old unmaintained mrt = daemon, which includes a bizarre custom reference-counted memory manager = that is very convoluted). These are easy to set up, but cause a lot of = weird segfaults which I am having a difficult time to try to debug. So it seems like I am going nowhere with this approach. Instead, I'd = like to know, what would I need to do to add this support to my local = copy of librte_lpm? Let's assume for the sake of this discussion, that I = don't care one iota about any performance cost, and I am happy if I need = to prefetch two cachelines instead of just one (which I recall from a = past thread is why librte_lpm has such a low nexthop limit to start = with). Failing that, does anybody have a known good userspace version of any of = these sort of items: 1) Hash Based FIB (forwarding information base), 2) Tree Based FIB, 3) Patricia trie (which does not break horribly on IPv6 or make bad = assumptions about data format besides uint8_t* and length), 4) Crit-Bit tree 5) any other good way of taking IPv4 and IPv6 and finding the longest = prefix match against a table of pre-loaded CIDR blocks? I am really pulling out my hair trying to find a way to do something = which doesn't seem like it should have to be be this difficult. I must = be missing a more obvious way to handle this. Thanks, Matthew=