From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id 5104BA0548 for ; Sun, 28 Nov 2021 13:57:23 +0100 (CET) Received: from [217.70.189.124] (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 18C734275E; Sun, 28 Nov 2021 13:57:17 +0100 (CET) Received: from mail-lf1-f48.google.com (mail-lf1-f48.google.com [209.85.167.48]) by mails.dpdk.org (Postfix) with ESMTP id 3210D42738 for ; Fri, 26 Nov 2021 14:53:36 +0100 (CET) Received: by mail-lf1-f48.google.com with SMTP id b1so24380237lfs.13 for ; Fri, 26 Nov 2021 05:53:36 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=nStr2xP8AD9NK1rNLsgeZnKSQRtV/rVpPfZbsTAAMKQ=; b=N5cdwMUv+/Vb8zCRb4mykmLeT3aILpHyBw8bN+M09YCu+T8TyiGAAGJkvTbdpxTUWK ng0pgrQKK8kOlMpu2KDogIDmQ2tkbtLrnnVNayl03jH4/Luuip0EJNfwm1OOervbc5zs t2+Ofs22HfBc6WCJKX86neEdQeFcEntLHCiazd6zM3pCvzoV7oF5djsl1FuNzsLw/uYH r27l++Rp7pCT5xOINZpDrWiyR0OaIwu9l384mgn4iFY+lPuJEMBc1y6ifeP+sdlVEakG 7sE4EgoVOizx4uq0q8dFVspjOwr0hjeLFnXkWtOnhvZ7wgCBbAmgO8Raojo7HrKNHsuL KkLA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=nStr2xP8AD9NK1rNLsgeZnKSQRtV/rVpPfZbsTAAMKQ=; b=tYK4U+dt7XaIRuyP27w/d6hEAz3LteDSLyH+dC2exWfUj6po2TcqmNjfS+bZuJHzNf hcmv1QFEjBED/MvEbLJisd+j3x/WhsLKI1PX6hY4thewIWOCxM3JY2EezFThyeyNqD9+ 3k5cNY5W/5gm7vezrS2nV6l+hr+Ue75xVJgAwxxjskBzY5RDMLI45yXDR04eCOazgEgp GSVoa4Q0t6+ygAfRFJ5XCi/h8hrKaXSHS9CeDoLd8/PX9/oXQCR7JF683g6fYesWvCI7 v1A8eDqoNBvPlAKBKMWg7NV1OSothYV09sH/0dcWPmMHFXQFqzsxkvkgVo6Y8pmSRChe amFg== X-Gm-Message-State: AOAM531WKasQYvwU7hmIuu18BOdJkcghtKtzkZ63Cn3dnaQYQG4QTFCc N88+BNtC0Nths+JmtvCDZ7ymCs7CuZ5/vkyr1x1zLBpp X-Google-Smtp-Source: ABdhPJzzk4mPt7o06gKzo11LYXNhIM7QpbfJHBZ4BIDq+eg/oKhbLEm4/riaRE59CdOREU7RFw0kt3vNPWSjogrJw7o= X-Received: by 2002:a05:6512:3216:: with SMTP id d22mr30590809lfe.604.1637934815725; Fri, 26 Nov 2021 05:53:35 -0800 (PST) MIME-Version: 1.0 References: <20211124181958.212f1179@sovereign> In-Reply-To: <20211124181958.212f1179@sovereign> From: =?UTF-8?B?0JTQvNC40YLRgNC40Lkg0KHRgtC10L/QsNC90L7Qsg==?= Date: Fri, 26 Nov 2021 16:53:24 +0300 Message-ID: Subject: Re: Find all matches with DPDK ACL To: Dmitry Kozlyuk Cc: Steffen Weise , users@dpdk.org Content-Type: multipart/alternative; boundary="000000000000db4bd105d1b16ac7" X-Mailman-Approved-At: Sun, 28 Nov 2021 13:57:15 +0100 X-BeenThere: users@dpdk.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: DPDK usage discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: users-bounces@dpdk.org --000000000000db4bd105d1b16ac7 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi! I have a big number of IPv4 5-tuple rules, every rule corresponds to some action. I need to find all matched rules and perform all tied actions. The search time greatly affects overall system performance, so I can't just scan all rules. ACL is based on multi-bit tries and provides great performance, so I'm looking for nearly the same performance with the ability to find all matches within a single request. =D1=81=D1=80, 24 =D0=BD=D0=BE=D1=8F=D0=B1. 2021 =D0=B3. =D0=B2 18:20, Dmitr= y Kozlyuk : > 2021-11-24 11:06 (UTC+0100), Steffen Weise: > > > Hi folks! > > > > > > I'm using DPDK's ACL library to classify incoming packets by IPv4 5 > tuple > > > match (src address, dst address, src port, dst port, protocol). Right > now > > > it is possible to find only the best match based on the rule's > priority. > > > Is there any way (maybe a custom patch for the ACL library exists?) t= o > > > find all matches in a single request? Decreased performance and even > some > > > false-positive matches are acceptable. > > > It could be a big number of matches so using categories is not an > option. > > > > > > Thanks, > > > Dmitriy Stepanov > > > > > > > Hi, > > > > I have the very same question. Such a mechanism would help me in my > > applications. Currently I go for lookup on multiple separate tables. > > > > Cheers, > > Steffen Weise > > Hi, > > I wonder what is the original problem you're solving. > > A set of IPv4 5-tuple rules can be viewed as a set of regular expressions= : > > ACL: src 1.1.1.0/24 dst 2.2.2.2/32 sport any dport 0x0035 proto tcp > Regex: ^\x01\x01\x01.\x02\x02\x02\x02..\x00\x35\x06$ > > Here, "." stands for "any byte". > For masks/ranges not aligned on 8 bits regex ranges can be used, e.g.: > > ACL: sport 100-200 > # this one is easy, just one byte varies > Regex: \x00[\x64-\xC8] > > ACL: sport 200-300 > # this one is hard, needs an algorithm to transform > # 200-300 =3D> 200-255,256-300 =3D> 0xC8-0xFF,0x0100-0x012C > Regex: (?:\x00[\xC8-xFF]|\x01[\x00-\x2C]) > > ACL: src 192.0.2.64/26 > # this one is easy, there are also hard examples like above > Regex: \xC0\x00\x02[\x40-\x7F] > > IIUC, you need all matching expressions for every packet, > which is represented as a 4+4+2+2+1 byte "string". > This is exactly what Hyperscan library does, for example: > http://intel.github.io/hyperscan/dev-reference/runtime.html > > There is now regexdev in DPDK, > take a look at it, maybe it will suit your needs and HW. > --000000000000db4bd105d1b16ac7 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi!
I have a big number of IPv4 5-tuple rules, every r= ule corresponds to some action. I need to find all matched rules and perfor= m all tied actions.
The search time greatly affects overall syste= m performance, so I can't just scan all rules. ACL is based on multi-bi= t tries and provides great performance, so I'm looking for nearly the s= ame performance with the ability to find all matches within a single reques= t.=C2=A0

=D1=81=D1=80, 24 =D0=BD=D0=BE=D1=8F=D0=B1. 2021 =D0=B3. =D0= =B2 18:20, Dmitry Kozlyuk <d= mitry.kozliuk@gmail.com>:
2021-11-24 11:06 (UTC+0100), Steffen Weise:
> > Hi folks!
> >
> > I'm using DPDK's ACL library to classify incoming packets= by IPv4 5 tuple
> > match (src address, dst address, src port, dst port, protocol). R= ight now
> > it is possible to find only the best match based on the rule'= s priority.
> > Is there any way (maybe a custom patch for the ACL library exists= ?) to
> > find all matches in a single request? Decreased performance and e= ven some
> > false-positive matches are acceptable.
> > It could be a big number of matches so using categories is not an= option.
> >
> > Thanks,
> > Dmitriy Stepanov
> >=C2=A0
>
> Hi,
>
> I have the very same question. Such a mechanism would help me in my > applications. Currently I go for lookup on multiple separate tables. >
> Cheers,
> Steffen Weise

Hi,

I wonder what is the original problem you're solving.

A set of IPv4 5-tuple rules can be viewed as a set of regular expressions:<= br>
ACL:=C2=A0 =C2=A0 src 1.1.1.0/24 dst 2.2.2.2/32 sport any dport 0x0035 proto tcp Regex:=C2=A0 ^\x01\x01\x01.\x02\x02\x02\x02..\x00\x35\x06$

Here, "." stands for "any byte".
For masks/ranges not aligned on 8 bits regex ranges can be used, e.g.:

ACL:=C2=A0 =C2=A0 sport 100-200
=C2=A0 =C2=A0 =C2=A0 =C2=A0 # this one is easy, just one byte varies
Regex:=C2=A0 \x00[\x64-\xC8]

ACL:=C2=A0 =C2=A0 sport 200-300
=C2=A0 =C2=A0 =C2=A0 =C2=A0 # this one is hard, needs an algorithm to trans= form
=C2=A0 =C2=A0 =C2=A0 =C2=A0 # 200-300 =3D> 200-255,256-300 =3D> 0xC8-= 0xFF,0x0100-0x012C
Regex:=C2=A0 (?:\x00[\xC8-xFF]|\x01[\x00-\x2C])

ACL:=C2=A0 =C2=A0 src 192.0.2.64/26
=C2=A0 =C2=A0 =C2=A0 =C2=A0 # this one is easy, there are also hard example= s like above
Regex:=C2=A0 \xC0\x00\x02[\x40-\x7F]

IIUC, you need all matching expressions for every packet,
which is represented as a 4+4+2+2+1 byte "string".
This is exactly what Hyperscan library does, for example:
http://intel.github.io/hyperscan/dev-refe= rence/runtime.html

There is now regexdev in DPDK,
take a look at it, maybe it will suit your needs and HW.
--000000000000db4bd105d1b16ac7--