1. 18 Dec, 2018 30 commits
  2. 17 Dec, 2018 6 commits
  3. 16 Dec, 2018 4 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
    • Nir Dotan's avatar
      selftests: mlxsw: Add Bloom filter simple test · 095c7208
      Nir Dotan authored
      Add a test that exercises Bloom filter code.
      Activate eRP table in the region by adding multiple rule patterns which
      with very high probability use different entries in the Bloom filter.
      Then send packets in order to check lookup hits on all relevant rules.
      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>
      095c7208