1. 18 Dec, 2018 31 commits
  2. 17 Dec, 2018 6 commits
  3. 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