1. 18 Dec, 2018 23 commits
  2. 17 Dec, 2018 6 commits
  3. 16 Dec, 2018 11 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
    • Nir Dotan's avatar
      mlxsw: spectrum_acl: Set A-TCAM rules in Bloom filter · 8c81b743
      Nir Dotan authored
      Add calls to eRP module for updating Bloom filter when a rule is
      added or removed from the A-TCAM. eRP module will update the Bloom
      filter only for cases in which the region has an active eRP table.
      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>
      8c81b743
    • Nir Dotan's avatar
      mlxsw: spectrum_acl: Add Bloom filter update · f5a2852e
      Nir Dotan authored
      Add Bloom filter update for rule insertion and rule removal scenarios.
      This is done within eRP module in order to assure that Bloom filter
      updates are done only for rules which are part of an eRP, as HW does not
      consult Bloom filter for entries when there is a single (master) mask in
      the 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>
      f5a2852e
    • Nir Dotan's avatar
      mlxsw: spectrum_acl: Add Bloom filter handling · 7585cacd
      Nir Dotan authored
      Spectrum-2 HW uses Bloom filter in order to skip lookups on specific
      eRPs. It uses crc-16-Msbit-first calculation over a specific layout
      of a rule's key fields combined with eRP ID as well as region ID.
      Per potential lookup, iff the Bloom filter entry of the calculated
      index is empty, then the lookup can be skipped. Hence, the mlxsw
      driver should update the Bloom filter entry per each rule insertion
      or deletion when rules are part of an eRP.
      
      Add functions for adding and deleting entries in the Bloom filter.
      In order to do so also add crc-16 computation based on the specific
      Spectrum-2 polynomial and a function for encoding the crc-16 input
      in the manner dictated by HW implementation.
      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>
      7585cacd
    • Nir Dotan's avatar
      mlxsw: spectrum_acl: Introduce Bloom filter · 0487cfba
      Nir Dotan authored
      Lay the foundations for Bloom filter handling. Introduce a new file for
      Bloom filter actions.
      
      Add struct mlxsw_sp_acl_bf to struct mlxsw_sp_acl_erp_core and initialize
      the Bloom filter data structure. Also take care of proper destruction when
      terminating.
      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>
      0487cfba