From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lb0-f178.google.com (mail-lb0-f178.google.com [209.85.217.178]) by dpdk.org (Postfix) with ESMTP id 1DC02C694 for ; Mon, 22 Jun 2015 12:11:15 +0200 (CEST) Received: by lbbwc1 with SMTP id wc1so105680232lbb.2 for ; Mon, 22 Jun 2015 03:11:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=P1VU/WDWnf13LO8Txewd0fyokaf3dvV6HbtkPClqG7M=; b=fHGSIM0V6FCwA9a5Vhmjr9R5WyHkt+0H51EumsKbal642IWkew/pAYcaFx1ksg534q rb9LZZ+Ela9vskzRHgDiQq1a4TlF02/3Sha1jlKpLhlCMqiHVnGLuCkGkBZwHDZh7ael MUlzH4wkSz4Oqcyip3aP3BqNmNNBfGi2dgpdci/X57GMNr+dUgdPCkGCWmAc7hXIcrKW wAuZBr0GZOF1Gwtf2ndzr29WR/vDrwIkKVTLSQ7PP0cfFdUdhn7nf4KNl5DqgsM/mKaN uwF4miHZaLNIGO54TBY1I/MSkeh4GJAThoilqSYsDOctLOfuTwX6ht5ANSvz1CgUue8D t9pQ== MIME-Version: 1.0 X-Received: by 10.112.199.10 with SMTP id jg10mr29160145lbc.24.1434967874732; Mon, 22 Jun 2015 03:11:14 -0700 (PDT) Received: by 10.114.10.229 with HTTP; Mon, 22 Jun 2015 03:11:14 -0700 (PDT) In-Reply-To: <5A3882CB-0DE0-43DB-8DCA-051D561AA943@mhcomputing.net> References: <5A3882CB-0DE0-43DB-8DCA-051D561AA943@mhcomputing.net> Date: Mon, 22 Jun 2015 13:11:14 +0300 Message-ID: From: Vladimir Medvedkin To: Matthew Hall Content-Type: text/plain; charset=UTF-8 X-Content-Filtered-By: Mailman/MimeDel 2.1.15 Cc: "" Subject: Re: [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 10:11:15 -0000 Hi Matthew, I just recently thought about next_hop extension. For ipv4 we can do something like: struct rte_lpm_tbl24_entry { /* Stores Next hop or group index (i.e. gindex)into tbl8. */ union { uint32_t next_hop :24; uint32_t tbl8_gindex :24; }__attribute__((__packed__)); /* Using single uint8_t to store 3 values. */ uint32_t valid :1; /**< Validation flag. */ uint32_t ext_entry :1; /**< External entry. */ uint32_t depth :6; /**< Rule depth. */ }; so we have 24 bit for next_hop. 2015-06-22 5:29 GMT+03:00 Matthew Hall : > 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