1. 18 Dec, 2018 27 commits
  2. 17 Dec, 2018 6 commits
  3. 16 Dec, 2018 7 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
    • Nir Dotan's avatar
      mlxsw: reg: Activate Bloom filter · 03ce5bd1
      Nir Dotan authored
      Now that mlxsw driver handles all aspects of updating
      the Bloom filter mechanism, set bf_bypass value to false
      and allow HW to use Bloom filter.
      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>
      03ce5bd1
    • Nir Dotan's avatar
      mlxsw: spectrum_acl: Set master RP index on transition to eRP · dd97d85f
      Nir Dotan authored
      Bloom filter is updated on transitions from a single rule pattern,
      also called master RP, to eRP table and vice versa. Since rules are
      being written to or deleted from the Bloom filter on such transitions,
      it is not required to keep the same eRP bank ID for the master RP.
      
      Change master RP index assignment so it will be assigned with zero.
      This is consistent with the assignment of the first available spot
      that is used for allocating eRP's indices.
      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>
      dd97d85f
    • Nir Dotan's avatar
      mlxsw: spectrum_acl: Update Bloom filter on eRP transitions · 135fd957
      Nir Dotan authored
      Bloom filter update is required only for rules which reside on an
      eRP. When the region has only a single rule pattern then eRP table
      is not used, however insertion of another pattern would trigger a
      move to an active eRP table so it is imperative to update the Bloom
      filter with all previously configured rules.
      
      Add a method that updates Bloom filter entries for all rules
      currently configured in the region, on the event of a transition
      from master mask to eRP, or vice versa. For that purpose, maintain
      a list of all A-TCAM rules within mlxsw_sp_acl_atcam_region.
      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>
      135fd957