From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pg0-f66.google.com (mail-pg0-f66.google.com [74.125.83.66]) by dpdk.org (Postfix) with ESMTP id B638B7F2D for ; Fri, 27 Apr 2018 00:24:51 +0200 (CEST) Received: by mail-pg0-f66.google.com with SMTP id i194so16992091pgd.0 for ; Thu, 26 Apr 2018 15:24:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=networkplumber-org.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=ExLMnEwNXqzrJ5xH1LDo1JZ3y70jC22NY89JRLe25Dc=; b=Qznmf5R3WPxs3rIYEdZVSkymcJOWepB7DyZe8yEKM7pGf1+pfA7MMXem7Cel+gbaQ6 JMRVSu1O5teDcNfcJCePjF9dlq9Yvq8fUdQgBRqnYMxntl7SLgO41xUTB4tCmeaaI20Z mnA6SIucOZztG/JlEvPxtTVpKrLNAprNg3r9BUuu72YImvhmfQGiUMbI1gQj0DdjdfX8 OaJzg8lHvHtTlKwiuCLiqzTZY6nIBc4tJFu0WOeIooED8CR7COpQ6uGCZ0NU8geKkqdx /Gj1L5V8SsmurB8q7nkPw90xpxUHENj+18Ulze3sw02YbG/KmETH8rJ0A2xlD0R8k/OV D8WQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=ExLMnEwNXqzrJ5xH1LDo1JZ3y70jC22NY89JRLe25Dc=; b=BswF+/EJz79wWkiK4ctYGujpu+wFPhoocg5HshsCo1l1je7rvxkIyruRp1Ugnx6Vsv xQA+lIjhqj99Q/Jns31XG3fmU0ICAlE1ZiGZYjnX2SgqFrKdZ6gdqOJhfi7hyBgBUWAk OxjPLKfx/FXVOyzldl/S2FcTfcuvPw+hwvFYxO2e0qJbQ7FTHj/tqWWIUc+Qvu6pvVBZ R4nYbi77j2Jqyy3uGC37ijMsYpWVItDqdwMVH0y6CYzP9ZbvGwadnxP0HrSSYKQK/hjM qJLFYEPxHM2njACr+higiCWfi/HYHRTMnn/PWTvypQl18M91T66EXAyyv40466twWJoY 6SqA== X-Gm-Message-State: ALQs6tBWbqCypiOH87lC0gcMdwL0i/EoWZ1lt9Km1i6Eh624CWtirXoP H6YAbsre571w/qopVdiHB/Iohw== X-Google-Smtp-Source: AIpwx4/VuBllYSytX33+54+7A+nr1vTKBJmCpizssB1/M2fjctla7SgiuSnC3mclTQJtW60VLqJYmA== X-Received: by 10.99.45.70 with SMTP id t67mr28754626pgt.439.1524781490863; Thu, 26 Apr 2018 15:24:50 -0700 (PDT) Received: from xeon-e3 (204-195-71-95.wavecable.com. [204.195.71.95]) by smtp.gmail.com with ESMTPSA id y17sm9735464pfl.19.2018.04.26.15.24.50 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Thu, 26 Apr 2018 15:24:50 -0700 (PDT) Date: Thu, 26 Apr 2018 15:24:48 -0700 From: Stephen Hemminger To: Medvedkin Vladimir Cc: dev@dpdk.org, bruce.richardson@intel.com, thomas@monjalon.net, cristian.dumitrescu@intel.com Message-ID: <20180426152448.0c21dc13@xeon-e3> In-Reply-To: <1524780214-23196-1-git-send-email-medvedkinv@gmail.com> References: <1524780214-23196-1-git-send-email-medvedkinv@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Subject: Re: [dpdk-dev] [PATCH v4 0/4] lib/rib: Add Routing Information Base library X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 26 Apr 2018 22:24:52 -0000 On Fri, 27 Apr 2018 01:03:30 +0300 Medvedkin Vladimir wrote: > This patch series introduces new library librte_rib which potentially could > replace librte_lpm. > > RIB is an alternative to current LPM library. > It solves the following problems > - Increases the speed of control plane operations against lpm such as > adding/deleting routes > - Adds abstraction from dataplane algorithms, so it is possible to add > different ip route lookup algorythms such as DXR/poptrie/lpc-trie/etc > in addition to current dir24_8 > - It is possible to keep user defined application specific additional > information in struct rte_rib_node which represents route entry. > It can be next hop/set of next hops (i.e. active and feasible), > pointers to link rte_rib_node based on some criteria (i.e. next_hop), > plenty of additional control plane information. > > v4: > fix various bugs > make struct rte_rib opaque > make inline functions instead of macro > remove RTE_RIB_MALLOC node allocation type > add new lookup functions > remove rte_dir24_8_lookup() > add rte_dir24_8_get_lookup() > add meson support > add fib configuration > > > Medvedkin Vladimir (4): > Add RIB library > Add dir24_8 implementation for rib library > Add autotests for RIB library The existing DPDK LPM code does need more work it does trade space for time. It does have some advantages though: * LPM lookup table is independent of number of routes. * LPM lookup table can be lock free reader safe using RCU. The existing slowness of add and delete was fixed at Vyatta/Brocade by replacing list with red-black tree. Patches were submitted but never merged.