[dpdk-dev] lpm patches

[Bruce Richardson <bruce.richardson@intel.com>]

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