From mboxrd@z Thu Jan  1 00:00:00 1970
From: Stephen Hemminger <stephen@networkplumber.org>
Subject: Re: perfomance of rte_lpm rule subsystem
Date: Tue, 19 Apr 2016 08:46:40 -0700
Message-ID: <20160419084640.52235b05@xeon-e3>
References: <CAMKNYbzETqi3UJkdvMAcdoLVWx_3MQUiDxnmBrWT_49w5tXKRg@mail.gmail.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Cc: dev@dpdk.org
To: =?UTF-8?B?0JDQu9C10LrRgdCw0L3QtNGAINCa0LjRgdC10LvQtdCy?=
 <kiselev99@gmail.com>
Return-path: <dev-bounces@dpdk.org>
Received: from mail-pa0-f47.google.com (mail-pa0-f47.google.com
 [209.85.220.47]) by dpdk.org (Postfix) with ESMTP id 9F9D2379E
 for <dev@dpdk.org>; Tue, 19 Apr 2016 17:46:27 +0200 (CEST)
Received: by mail-pa0-f47.google.com with SMTP id r5so7117194pag.1
 for <dev@dpdk.org>; Tue, 19 Apr 2016 08:46:27 -0700 (PDT)
In-Reply-To: <CAMKNYbzETqi3UJkdvMAcdoLVWx_3MQUiDxnmBrWT_49w5tXKRg@mail.gmail.com>
List-Id: patches and discussions about DPDK <dev.dpdk.org>
List-Unsubscribe: <http://dpdk.org/ml/options/dev>,
 <mailto:dev-request@dpdk.org?subject=unsubscribe>
List-Archive: <http://dpdk.org/ml/archives/dev/>
List-Post: <mailto:dev@dpdk.org>
List-Help: <mailto:dev-request@dpdk.org?subject=help>
List-Subscribe: <http://dpdk.org/ml/listinfo/dev>,
 <mailto:dev-request@dpdk.org?subject=subscribe>
Errors-To: dev-bounces@dpdk.org
Sender: "dev" <dev-bounces@dpdk.org>

On Tue, 19 Apr 2016 14:11:11 +0300
=D0=90=D0=BB=D0=B5=D0=BA=D1=81=D0=B0=D0=BD=D0=B4=D1=80 =D0=9A=D0=B8=D1=81=
=D0=B5=D0=BB=D0=B5=D0=B2 <kiselev99@gmail.com> wrote:

> Hi.
>=20
> Doing some test with rte_lpm (adding/deleting bgp full table rules) I
> noticed that
> rule subsystem is very slow even considering that probably it was never
> designed for using
> in a data forwarding plane. So I want to propose some changes to the "rul=
e"
> subsystem.
>=20
> I reimplemented rule part ot the lib using rte_hash, and perfomance of
> adding/deleted routes have increased dramatically.
> If increasing speed of adding deleting routes makes sence for anybody else
> I would like to discuss my patch.
> The patch also include changes that make next_hop 64 bit, so please just
> ignore them. The rule changes are in the following
> functions only:
>=20
> rte_lpm2_create
>=20
> rule_find
> rule_add
> rule_delete
> find_previous_rule
> delete_depth_small
> delete_depth_big
>=20
> rte_lpm2_add
> rte_lpm2_delete
> rte_lpm2_is_rule_present
> rte_lpm2_delete_all
>=20

We forked LPM back several versions ago.
I sent the patches to use BSD red-black tree for rules but the patches were
ignored. mostly because it broke ABI.