Skip to content

L
linux
Switch branch/tag
  1. 18 Dec, 2018 31 commits
  3. 17 Dec, 2018 6 commits
  5. 16 Dec, 2018 3 commits
    • David S. Miller's avatar
      Merge branch 'mlxsw-spectrum_acl-Add-Bloom-filter-support' · ae6750e0
      David S. Miller authored 
      Ido Schimmel says:

====================
mlxsw: spectrum_acl: Add Bloom filter support

Nir says:

Spectrum-2 uses Bloom filter to reduce the number of lookups in the
algorithmic TCAM (A-TCAM). HW performs multiple exact match lookups in a
given region using a key composed of { packet & mask, mask ID, region ID }.
The masks which are used in a region are called rule patterns or RP.
When such multiple masks are used, the A-TCAM region uses an eRP
(extended RP) table that describes which rule patterns are in use and
defines the order of the lookup. When eRP table is used in a region, one
way to reduce the number of the lookups is to consult a Bloom filter
before doing the lookup.

A Bloom filter is a space-efficient probabilistic data structure, on
which a query returns either "possibly in set" or "definitely not in
set". HW can skip a lookup if a query on the Bloom filter results a
"definitely not set" response. The mlxsw driver implements a "counting
filter" and when either a new entry is marked or the last entry is
removed it will update the HW. Update of this counting filter occurs
when rule is configured or deleted from a region.

Patch #1 adds PEABFE register which is used for setting Bloom filter
entries.

Patch #2 adds Bloom filter resources.

Patch #3 and patch #4 provide Bloom filter handling within mlxsw, by
adding initialization and logic for updating the Bloom bit vector in HW.

Patch #5 and patch #6 add required calls for Bloom filter update as part
of rule configuration flow.

Patch #7 handles transitions to and from eRP table. It uses a list to
keep A-TCAM rules in order to update rules in Bloom filter, in cases of
transitions from master mask based A-TCAM region to an eRP table based
region and vice versa.

Patch #8 removes a trick done on master RP index to a remaining RP,
since Bloom filter is updated on eRP transitions.

Finally, patch #9 activates Bloom filter mechanism in HW, by cancelling
the bypass that was configured before and the remaining three patches
are selftests that exercise the new code.
====================
Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      ae6750e0
    • Nir Dotan's avatar
      selftests: mlxsw: Add Bloom delta test · 5d06a76d
      Nir Dotan authored 
      The eRP table is active when there is more than a single rule
pattern. It may be that the patterns are close enough and use delta
mechanism. Bloom filter index computation is based on the values of
{rule & mask, mask ID, region ID} where the rule delta bits must be
cleared.

Add a test that exercises Bloom filter with delta mechanism.
Configure rules within delta range and pass a packet which is
supposed to hit the correct rule.
Signed-off-by: default avatarNir Dotan <nird@mellanox.com>
Signed-off-by: default avatarIdo Schimmel <idosch@mellanox.com>
Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      5d06a76d
    • Nir Dotan's avatar
      selftests: mlxsw: Add Bloom filter complex test · 5118ca4e
      Nir Dotan authored 
      Bloom filter index computation is based on the values of
{rule & mask, mask ID, region ID} and the computation also varies
according to the region key size.

Add a test that exercises the possible combinations by creating
multiple chains using different key sizes and then pass a frame that
is supposed to to produce a hit on all of the regions.
Signed-off-by: default avatarNir Dotan <nird@mellanox.com>
Signed-off-by: default avatarIdo Schimmel <idosch@mellanox.com>
Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      5118ca4e
GitLab Nexedi Edition | About GitLab | About Nexedi | 沪ICP备2021021310号-2 | 沪ICP备2021021310号-7