[dpdk-dev] lpm patches

[dpdk-dev] lpm patches

[Bruce Richardson]

Hi all,

there have been a lot of patches submitted in the 2.2 release cycle with
extensions to the LPM library. [Referring to just LPM for IPv4 here] 
Given the fact that we now have - by my count - four different patchsets
to extend this lib, we probably need to take some time to reconcile the 
differences between these submissions and determine what, if anything, can be
applied for 2.2, and what should be done for 2.3.

References:
>From Vladimir Medvedkin    - http://dpdk.org/dev/patchwork/patch/8065/
>From Stephen Hemminger     - http://dpdk.org/dev/patchwork/patch/7981/
>From Michal K. & Michal J. - http://dpdk.org/dev/patchwork/patch/7937/
>From Matthew Hall          - http://dpdk.org/dev/patchwork/patch/7984/ [since
Matthew's patches were attachments, I don't think they came through in patchwork 
correctly :-(, but that is the relevant link there anyway.]

What's common:
* increasing the number of bits in the next-hop field

However, just about everything else seems to be different [thanks to Michal
Jastrzebski for doing some analysis on the patches to help me out]:
* Some patches increase the next-hop to 16 bits, others to 24-bits. In both cases
  a single entry still only occupies 32-bits, so can be read/written to 
  atomically
* Only Michal's set appears to take into account ABI versioning, which is
  a difficult problem for this lib, with inlined functions.
* Matthew's patchset moves the lookup functions to be non-inlined, which will
  make future updates easier from ABI compatibility - at the cost of lookup
  performance.
* Vladimir's patchset merges in the tbl24 and tbl8 entries into a single data
  type.
* That patchset also introduces an extra optional 32-bit field "as_num", allowing
  64-bit lpm table entries - obviously at a cost of increased memory/cache
  footprint.
* Stephen's patchset includes a range of other fixes e.g. for more efficient
  management of the rules array, and dynamic allocation of the TBL8s.
* Matthew's patchset also includes change to LPM for IPv6, which I'm considering
  out-of-scope for now, so as to focus on LPM v4 only.

Overall, most of the above changes seem reasonable, so therefore, I would suggest
that a combined approach would be:

* Increase next hops to be the full 24 bits, so as to allow maximum flexibility
  and not waste the extra 8 bits of space in the 32-bit entries.
* Move the lookup functions which work on multiple packets to be non-inlined
* Merge in the tbl24 and tbl8 structures to make the code that little bit shorter
* Look to pull in as many of Stephen's other improvements as possible - though
  this may be in a separate patchset to the other changes.

Other suggestions that I'd look for feedback on would be:
* I would recommend keeping the single value lpm lookup function as a static
  inline function in the header file. For a single packet the cost of the
  function call overhead will be significant, so I don't believe we should move
  this to be an API call in the library.
* I'm uncertain as to the extra 32-bit as_num field. Adding it as an extra
  #define is trivial, but adds to the compile-time config. Having it as a run-time
  option is possible, but likely will make the code a lot more complicated, as
  we no longer have arrays of a fixed size.

Naturally, with whatever solution is come up with, ABI compatibility must be
taken into account and functions versionned appropriately!

Question: 
---------
do we want to have some of these changes in 2.2? If so, having Michal's
patch merged looks like the only viable option as it takes ABI into account,
and does not preclude any other changes being made to add the extra features
(merged structures, optimized rule handling, moving functions to non-inline etc.)
in the 2.3 timeframe.

Matthew, Stephen, Vladimir, Michal, Thomas - thoughts on this? 
[do I accurately sum up the situation?]

Regards,
/Bruce

Re: [dpdk-dev] lpm patches

[Matthew Hall]

On Fri, Oct 30, 2015 at 12:00:18PM +0000, Bruce Richardson wrote:
> Matthew's patches were attachments, I don't think they came through in patchwork 
> correctly :-(, but that is the relevant link there anyway.]

Let me know if there is something I can do better there. I was having a 
difficult time figuring out how to preserve the thread ID in the middle of the 
thread and not cause a new thread. The git email workflows are very confusing 
and I figured it was better to send something as soon as I could.

> * Some patches increase the next-hop to 16 bits, others to 24-bits. In both cases
>   a single entry still only occupies 32-bits, so can be read/written to 
>   atomically

I went with 24 because it was the biggest amount I could get that still had 
this property.

> * Only Michal's set appears to take into account ABI versioning, which is
>   a difficult problem for this lib, with inlined functions.

Agreed. His patches are the most professional from this perspective. This is 
why I was trying to contribute to you and to him so we get the most 
professional result for the customers.

> * Matthew's patchset moves the lookup functions to be non-inlined, which will
>   make future updates easier from ABI compatibility - at the cost of lookup
>   performance.

This point is optional for me. I did it, because without it, it was totally 
impossible for me to work on the code in a debugger as I am a security 
engineering guy not a crazy embedded C coder or kernel hacker.

> * Vladimir's patchset merges in the tbl24 and tbl8 entries into a single data
>   type.

I really liked this feature of Vladimir's patches, it makes it easier to 
maintain and less confusing. I had a lot of headaches keeping all those 
structs straight with the separate types, but I didn't know we had the chance 
for a great big MEGA-REFACTOR. I love this community!

> * That patchset also introduces an extra optional 32-bit field "as_num", allowing
>   64-bit lpm table entries - obviously at a cost of increased memory/cache
>   footprint.

Is there a way we could test it? Vladimir, did you test the performance? If 
so, what happened?

> * Stephen's patchset includes a range of other fixes e.g. for more efficient
>   management of the rules array, and dynamic allocation of the TBL8s.
> * Matthew's patchset also includes change to LPM for IPv6, which I'm considering
>   out-of-scope for now, so as to focus on LPM v4 only.

Any chance that is inconsistent betwen LPM4 and LPM6 really hoses me, because 
I am writing green-field code which treats both protocols as first-class 
citizens and I'd really not like to have totally inconsistent and inferior 
support in one versus the other.

> * Increase next hops to be the full 24 bits, so as to allow maximum flexibility
>   and not waste the extra 8 bits of space in the 32-bit entries.

+1

> * Move the lookup functions which work on multiple packets to be non-inlined

Open to opinions on the performance of this. I am not an expert on this area.

> * Merge in the tbl24 and tbl8 structures to make the code that little bit shorter

+1

> * Look to pull in as many of Stephen's other improvements as possible - though
>   this may be in a separate patchset to the other changes.

+1. Perhaps if we get a pre-release on a branch with everything else, we could 
see if Stephen is willing to rebase his non-duplicate changes.

> * I'm uncertain as to the extra 32-bit as_num field. Adding it as an extra
>   #define is trivial, but adds to the compile-time config. Having it as a run-time
>   option is possible, but likely will make the code a lot more complicated, as
>   we no longer have arrays of a fixed size.
> 
> Naturally, with whatever solution is come up with, ABI compatibility must be
> taken into account and functions versionned appropriately!

Normally I am not a big define guy. But it seems like a define is good here. 
Somebody is going to need to know beforehand if they are making a Core Router 
where they want this, or a Security Inspection system like mine, etc.

So it seems easier than doing a bunch of crazy size-juggling in the code.

> do we want to have some of these changes in 2.2?

Personally I am OK to wait as I have it working in my copy. I am just trying 
to be a good citizen of the community and contribute back when I see some core 
engineers going after the same code.

In particular, for me, having LPM4 only with no LPM6 is not worth much so I'd 
be happy to wait for a single upgrade to both of them.

> Matthew, Stephen, Vladimir, Michal, Thomas - thoughts on this? 
> [do I accurately sum up the situation?]

This email was top-quality and very well done by you guys.

Matthew.

Re: [dpdk-dev] lpm patches

[Vladimir Medvedkin]

Hi all,

2015-10-30 20:59 GMT+03:00 Matthew Hall <mhall@mhcomputing.net>:

> On Fri, Oct 30, 2015 at 12:00:18PM +0000, Bruce Richardson wrote:
> > Matthew's patches were attachments, I don't think they came through in
> patchwork
> > correctly :-(, but that is the relevant link there anyway.]
>
> Let me know if there is something I can do better there. I was having a
> difficult time figuring out how to preserve the thread ID in the middle of
> the
> thread and not cause a new thread. The git email workflows are very
> confusing
> and I figured it was better to send something as soon as I could.
>
> > * Some patches increase the next-hop to 16 bits, others to 24-bits. In
> both cases
> >   a single entry still only occupies 32-bits, so can be read/written to
> >   atomically
>
> I went with 24 because it was the biggest amount I could get that still had
> this property.
>
> > * Only Michal's set appears to take into account ABI versioning, which is
> >   a difficult problem for this lib, with inlined functions.
>
> Agreed. His patches are the most professional from this perspective. This
> is
> why I was trying to contribute to you and to him so we get the most
> professional result for the customers.
>
> > * Matthew's patchset moves the lookup functions to be non-inlined, which
> will
> >   make future updates easier from ABI compatibility - at the cost of
> lookup
> >   performance.
>
> This point is optional for me. I did it, because without it, it was totally
> impossible for me to work on the code in a debugger as I am a security
> engineering guy not a crazy embedded C coder or kernel hacker.
>
> > * Vladimir's patchset merges in the tbl24 and tbl8 entries into a single
> data
> >   type.
>
> I really liked this feature of Vladimir's patches, it makes it easier to
> maintain and less confusing. I had a lot of headaches keeping all those
> structs straight with the separate types, but I didn't know we had the
> chance
> for a great big MEGA-REFACTOR. I love this community!
>
> > * That patchset also introduces an extra optional 32-bit field "as_num",
> allowing
> >   64-bit lpm table entries - obviously at a cost of increased
> memory/cache
> >   footprint.
>
> Is there a way we could test it? Vladimir, did you test the performance? If
> so, what happened?
>
Performance regression depends on the traffic pattern and cache size.

>
> > * Stephen's patchset includes a range of other fixes e.g. for more
> efficient
> >   management of the rules array, and dynamic allocation of the TBL8s.
> > * Matthew's patchset also includes change to LPM for IPv6, which I'm
> considering
> >   out-of-scope for now, so as to focus on LPM v4 only.
>
> Any chance that is inconsistent betwen LPM4 and LPM6 really hoses me,
> because
> I am writing green-field code which treats both protocols as first-class
> citizens and I'd really not like to have totally inconsistent and inferior
> support in one versus the other.
>
> > * Increase next hops to be the full 24 bits, so as to allow maximum
> flexibility
> >   and not waste the extra 8 bits of space in the 32-bit entries.
>
> +1
>
+1. Split of next hop and forwarding class I can do in app logic.

>
> > * Move the lookup functions which work on multiple packets to be
> non-inlined
>
> Open to opinions on the performance of this. I am not an expert on this
> area.
>
> > * Merge in the tbl24 and tbl8 structures to make the code that little
> bit shorter
>
> +1
>
> > * Look to pull in as many of Stephen's other improvements as possible -
> though
> >   this may be in a separate patchset to the other changes.
>
> +1. Perhaps if we get a pre-release on a branch with everything else, we
> could
> see if Stephen is willing to rebase his non-duplicate changes.
>
> > * I'm uncertain as to the extra 32-bit as_num field. Adding it as an
> extra
> >   #define is trivial, but adds to the compile-time config. Having it as
> a run-time
> >   option is possible, but likely will make the code a lot more
> complicated, as
> >   we no longer have arrays of a fixed size.
> >
> > Naturally, with whatever solution is come up with, ABI compatibility
> must be
> > taken into account and functions versionned appropriately!
>
> Normally I am not a big define guy. But it seems like a define is good
> here.
> Somebody is going to need to know beforehand if they are making a Core
> Router
> where they want this, or a Security Inspection system like mine, etc.
>
For example in case of core router as_num feature can be necessary for
netflow. It can be necessary in case of security device such as my ddos
mitigation system.

>
> So it seems easier than doing a bunch of crazy size-juggling in the code.
>
> > do we want to have some of these changes in 2.2?
>
> Personally I am OK to wait as I have it working in my copy. I am just
> trying
> to be a good citizen of the community and contribute back when I see some
> core
> engineers going after the same code.
>
> In particular, for me, having LPM4 only with no LPM6 is not worth much so
> I'd
> be happy to wait for a single upgrade to both of them.
>
> > Matthew, Stephen, Vladimir, Michal, Thomas - thoughts on this?
> > [do I accurately sum up the situation?]
>
> This email was top-quality and very well done by you guys.
>
> Matthew.
>

Regards,
Vladimir

Re: [dpdk-dev] lpm patches

[Bruce Richardson]

On Fri, Oct 30, 2015 at 10:34:54PM +0300, Vladimir Medvedkin wrote:
> Hi all,
> 
> 2015-10-30 20:59 GMT+03:00 Matthew Hall <mhall@mhcomputing.net>:
> 
> > On Fri, Oct 30, 2015 at 12:00:18PM +0000, Bruce Richardson wrote:
> > > Matthew's patches were attachments, I don't think they came through in
> > patchwork
> > > correctly :-(, but that is the relevant link there anyway.]
> >
> > Let me know if there is something I can do better there. I was having a
> > difficult time figuring out how to preserve the thread ID in the middle of
> > the
> > thread and not cause a new thread. The git email workflows are very
> > confusing
> > and I figured it was better to send something as soon as I could.
> >
> > > * Some patches increase the next-hop to 16 bits, others to 24-bits. In
> > both cases
> > >   a single entry still only occupies 32-bits, so can be read/written to
> > >   atomically
> >
> > I went with 24 because it was the biggest amount I could get that still had
> > this property.
> >
> > > * Only Michal's set appears to take into account ABI versioning, which is
> > >   a difficult problem for this lib, with inlined functions.
> >
> > Agreed. His patches are the most professional from this perspective. This
> > is
> > why I was trying to contribute to you and to him so we get the most
> > professional result for the customers.
> >
> > > * Matthew's patchset moves the lookup functions to be non-inlined, which
> > will
> > >   make future updates easier from ABI compatibility - at the cost of
> > lookup
> > >   performance.
> >
> > This point is optional for me. I did it, because without it, it was totally
> > impossible for me to work on the code in a debugger as I am a security
> > engineering guy not a crazy embedded C coder or kernel hacker.
> >
> > > * Vladimir's patchset merges in the tbl24 and tbl8 entries into a single
> > data
> > >   type.
> >
> > I really liked this feature of Vladimir's patches, it makes it easier to
> > maintain and less confusing. I had a lot of headaches keeping all those
> > structs straight with the separate types, but I didn't know we had the
> > chance
> > for a great big MEGA-REFACTOR. I love this community!
> >
> > > * That patchset also introduces an extra optional 32-bit field "as_num",
> > allowing
> > >   64-bit lpm table entries - obviously at a cost of increased
> > memory/cache
> > >   footprint.
> >
> > Is there a way we could test it? Vladimir, did you test the performance? If
> > so, what happened?
> >
> Performance regression depends on the traffic pattern and cache size.
> 
> >
> > > * Stephen's patchset includes a range of other fixes e.g. for more
> > efficient
> > >   management of the rules array, and dynamic allocation of the TBL8s.
> > > * Matthew's patchset also includes change to LPM for IPv6, which I'm
> > considering
> > >   out-of-scope for now, so as to focus on LPM v4 only.
> >
> > Any chance that is inconsistent betwen LPM4 and LPM6 really hoses me,
> > because
> > I am writing green-field code which treats both protocols as first-class
> > citizens and I'd really not like to have totally inconsistent and inferior
> > support in one versus the other.
> >
> > > * Increase next hops to be the full 24 bits, so as to allow maximum
> > flexibility
> > >   and not waste the extra 8 bits of space in the 32-bit entries.
> >
> > +1
> >
> +1. Split of next hop and forwarding class I can do in app logic.
> 
> >
> > > * Move the lookup functions which work on multiple packets to be
> > non-inlined
> >
> > Open to opinions on the performance of this. I am not an expert on this
> > area.
> >
> > > * Merge in the tbl24 and tbl8 structures to make the code that little
> > bit shorter
> >
> > +1
> >
> > > * Look to pull in as many of Stephen's other improvements as possible -
> > though
> > >   this may be in a separate patchset to the other changes.
> >
> > +1. Perhaps if we get a pre-release on a branch with everything else, we
> > could
> > see if Stephen is willing to rebase his non-duplicate changes.
> >
> > > * I'm uncertain as to the extra 32-bit as_num field. Adding it as an
> > extra
> > >   #define is trivial, but adds to the compile-time config. Having it as
> > a run-time
> > >   option is possible, but likely will make the code a lot more
> > complicated, as
> > >   we no longer have arrays of a fixed size.
> > >
> > > Naturally, with whatever solution is come up with, ABI compatibility
> > must be
> > > taken into account and functions versionned appropriately!
> >
> > Normally I am not a big define guy. But it seems like a define is good
> > here.
> > Somebody is going to need to know beforehand if they are making a Core
> > Router
> > where they want this, or a Security Inspection system like mine, etc.
> >
> For example in case of core router as_num feature can be necessary for
> netflow. It can be necessary in case of security device such as my ddos
> mitigation system.
> 
> >
> > So it seems easier than doing a bunch of crazy size-juggling in the code.
> >
> > > do we want to have some of these changes in 2.2?
> >
> > Personally I am OK to wait as I have it working in my copy. I am just
> > trying
> > to be a good citizen of the community and contribute back when I see some
> > core
> > engineers going after the same code.
> >
> > In particular, for me, having LPM4 only with no LPM6 is not worth much so
> > I'd
> > be happy to wait for a single upgrade to both of them.
> >
> > > Matthew, Stephen, Vladimir, Michal, Thomas - thoughts on this?
> > > [do I accurately sum up the situation?]
> >
> > This email was top-quality and very well done by you guys.
> >
> > Matthew.
> >
> 
> Regards,
> Vladimir

Thanks for the feedback guys. Looks like we need to find a way to get the ability
to have either 32-bit or 64-bit LPM entries supported, as well as the additional
enhancements proposed :-)

We'll see what we can do in 2.3 timeframe.

Regards,
/Bruce

Re: [dpdk-dev] lpm patches

[Matthew Hall]

On Fri, Oct 30, 2015 at 09:55:16PM +0000, Bruce Richardson wrote:
> We'll see what we can do in 2.3 timeframe.

Thanks for taking all of this up and helping us make a solid plan. I'll do my 
best to help out from the community side. I have done some lightweight 
functionality tests of my patched LPM to good effect.

I'm working on finishing the last key feature and acquiring a Skylake system 
in the next few weeks so I can start doing some performance testing of my 
application with the community license of VTune, so I can make a proper 
release of some kind.

Just so I know what things I should monitor when, what is the approximate 
schedule for 2.3? Can we host a private branch or tree somewhere to be able to 
access any progress made with the various changes and report back?

Matthew.

Re: [dpdk-dev] lpm patches

[Nikita Kozlov]

On 10/30/2015 11:25 PM, Matthew Hall wrote:
> On Fri, Oct 30, 2015 at 09:55:16PM +0000, Bruce Richardson wrote:
>> We'll see what we can do in 2.3 timeframe.
> Thanks for taking all of this up and helping us make a solid plan. I'll do my 
> best to help out from the community side. I have done some lightweight 
> functionality tests of my patched LPM to good effect.
>
> I'm working on finishing the last key feature and acquiring a Skylake system 
> in the next few weeks so I can start doing some performance testing of my 
> application with the community license of VTune, so I can make a proper 
> release of some kind.
>
> Just so I know what things I should monitor when, what is the approximate 
> schedule for 2.3? Can we host a private branch or tree somewhere to be able to 
> access any progress made with the various changes and report back?
>
> Matthew.
Hello,
I wanted to know if there was something new or if I can help on this topic ?
I'm using rte_lpm in a project so I may (at least) do some tests or reviews.

Re: [dpdk-dev] lpm patches

[Matthew Hall]

On Mon, Feb 01, 2016 at 01:51:29AM +0100, Nikita Kozlov wrote:
> Hello,
> I wanted to know if there was something new or if I can help on this topic ?
> I'm using rte_lpm in a project so I may (at least) do some tests or reviews.

If you search the archive of the list some patch came out recently which is 
some help. But sadly won't help much for me as it is IPv4 only so I'll be 
sticking with my existing set that does IPv4 and IPv6.

Matthew.