From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: <users-bounces@dpdk.org> Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id 5104BA0548 for <public@inbox.dpdk.org>; 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 <users@dpdk.org>; Fri, 26 Nov 2021 14:53:36 +0100 (CET) Received: by mail-lf1-f48.google.com with SMTP id b1so24380237lfs.13 for <users@dpdk.org>; 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: <CA+-SuJ1G8zBPWgvVCZd_D5KQeXkMyrUkWjHfPXwFkhy08prU-g@mail.gmail.com> <CAOBD2Betu-U9hznd3oA0y-Av7dPp2RsvVOrsWUC5Qiqo7j8Jcg@mail.gmail.com> <20211124181958.212f1179@sovereign> In-Reply-To: <20211124181958.212f1179@sovereign> From: =?UTF-8?B?0JTQvNC40YLRgNC40Lkg0KHRgtC10L/QsNC90L7Qsg==?= <stepanov.dmit@gmail.com> Date: Fri, 26 Nov 2021 16:53:24 +0300 Message-ID: <CA+-SuJ1HQTHKYeTbTGDVYvdnvo9DMV1DwekKCEAvtiFC8mQbSg@mail.gmail.com> Subject: Re: Find all matches with DPDK ACL To: Dmitry Kozlyuk <dmitry.kozliuk@gmail.com> Cc: Steffen Weise <stweise.linux@gmail.com>, 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 <users.dpdk.org> List-Unsubscribe: <https://mails.dpdk.org/options/users>, <mailto:users-request@dpdk.org?subject=unsubscribe> List-Archive: <http://mails.dpdk.org/archives/users/> List-Post: <mailto:users@dpdk.org> List-Help: <mailto:users-request@dpdk.org?subject=help> List-Subscribe: <https://mails.dpdk.org/listinfo/users>, <mailto:users-request@dpdk.org?subject=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 <dmitry.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). 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 <div dir=3D"ltr">Hi!<div>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.</div><div>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</div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class= =3D"gmail_attr">=D1=81=D1=80, 24 =D0=BD=D0=BE=D1=8F=D0=B1. 2021 =D0=B3. =D0= =B2 18:20, Dmitry Kozlyuk <<a href=3D"mailto:dmitry.kozliuk@gmail.com">d= mitry.kozliuk@gmail.com</a>>:<br></div><blockquote class=3D"gmail_quote"= style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);p= adding-left:1ex">2021-11-24 11:06 (UTC+0100), Steffen Weise:<br> > > Hi folks!<br> > ><br> > > I'm using DPDK's ACL library to classify incoming packets= by IPv4 5 tuple<br> > > match (src address, dst address, src port, dst port, protocol). R= ight now<br> > > it is possible to find only the best match based on the rule'= s priority.<br> > > Is there any way (maybe a custom patch for the ACL library exists= ?) to<br> > > find all matches in a single request? Decreased performance and e= ven some<br> > > false-positive matches are acceptable.<br> > > It could be a big number of matches so using categories is not an= option.<br> > ><br> > > Thanks,<br> > > Dmitriy Stepanov<br> > >=C2=A0 <br> > <br> > Hi,<br> > <br> > I have the very same question. Such a mechanism would help me in my<br= > > applications. Currently I go for lookup on multiple separate tables.<b= r> > <br> > Cheers,<br> > Steffen Weise<br> <br> Hi,<br> <br> I wonder what is the original problem you're solving.<br> <br> A set of IPv4 5-tuple rules can be viewed as a set of regular expressions:<= br> <br> ACL:=C2=A0 =C2=A0 src <a href=3D"http://1.1.1.0/24" rel=3D"noreferrer" targ= et=3D"_blank">1.1.1.0/24</a> dst <a href=3D"http://2.2.2.2/32" rel=3D"noref= errer" target=3D"_blank">2.2.2.2/32</a> sport any dport 0x0035 proto tcp<br= > Regex:=C2=A0 ^\x01\x01\x01.\x02\x02\x02\x02..\x00\x35\x06$<br> <br> Here, "." stands for "any byte".<br> For masks/ranges not aligned on 8 bits regex ranges can be used, e.g.:<br> <br> ACL:=C2=A0 =C2=A0 sport 100-200<br> =C2=A0 =C2=A0 =C2=A0 =C2=A0 # this one is easy, just one byte varies<br> Regex:=C2=A0 \x00[\x64-\xC8]<br> <br> ACL:=C2=A0 =C2=A0 sport 200-300<br> =C2=A0 =C2=A0 =C2=A0 =C2=A0 # this one is hard, needs an algorithm to trans= form<br> =C2=A0 =C2=A0 =C2=A0 =C2=A0 # 200-300 =3D> 200-255,256-300 =3D> 0xC8-= 0xFF,0x0100-0x012C<br> Regex:=C2=A0 (?:\x00[\xC8-xFF]|\x01[\x00-\x2C])<br> <br> ACL:=C2=A0 =C2=A0 src <a href=3D"http://192.0.2.64/26" rel=3D"noreferrer" t= arget=3D"_blank">192.0.2.64/26</a><br> =C2=A0 =C2=A0 =C2=A0 =C2=A0 # this one is easy, there are also hard example= s like above<br> Regex:=C2=A0 \xC0\x00\x02[\x40-\x7F]<br> <br> IIUC, you need all matching expressions for every packet,<br> which is represented as a 4+4+2+2+1 byte "string".<br> This is exactly what Hyperscan library does, for example:<br> <a href=3D"http://intel.github.io/hyperscan/dev-reference/runtime.html" rel= =3D"noreferrer" target=3D"_blank">http://intel.github.io/hyperscan/dev-refe= rence/runtime.html</a><br> <br> There is now regexdev in DPDK,<br> take a look at it, maybe it will suit your needs and HW.<br> </blockquote></div> --000000000000db4bd105d1b16ac7--