1. 26 Jul, 2018 22 commits
  2. 25 Jul, 2018 18 commits
    • David S. Miller's avatar
      Merge branch 'mlxsw-Introduce-algorithmic-TCAM-support' · 756cd366
      David S. Miller authored
      Ido Schimmel says:
      
      ====================
      mlxsw: Introduce algorithmic TCAM support
      
      The Spectrum-2 ASIC uses an algorithmic TCAM (A-TCAM) where multiple
      exact matches lookups are performed instead of a single lookup as with
      standard circuit TCAM (C-TCAM) memory. This allows for higher scale and
      reduced power consumption.
      
      The lookups are performed by masking a packet using different masks
      (e.g., {dst_ip/24, ethtype}) defined for the region and looking for an
      exact match. Eventually, the rule with the highest priority will be
      picked.
      
      Since the number of masks per-region is limited, the ASIC includes a
      C-TCAM that can be used as a spill area for rules that do not fit into
      the A-TCAM.
      
      The driver currently uses a C-TCAM only mode which is similar to
      Spectrum-1. However, this mode severely limits both the number of
      supported ACL rules and the performance of the ACL lookup.
      
      This patch set introduces initial support for the A-TCAM mode where the
      C-TCAM is only used for rule spillage.
      
      The first five patches add the registers and ASIC resources needed in
      order to make use of the A-TCAM.
      
      Next three patches are the "meat" and add the eRP core which is used to
      manage the masks used by each ACL region. The individual commit messages
      are lengthy and aim to thoroughly explain the subject.
      
      The next seven patches perform small adjustments in the code and the
      related data structures and are meant to prepare the code base to the
      introduction of the A-TCAM in the last two patches.
      
      Various A-TCAM optimization will be the focus of follow-up patch sets:
      
      * Pruning - Used to reduce the number of lookups. Each rule will include
        a prune vector that indicates which masks should not be considered for
        further lookups as they cannot result in a higher priority match
      
      * Bloom filter - Used to reduce the number of lookups. Before performing
        a lookup with a given mask the ASIC will consult a bloom filter
        (managed by the driver) that indicates whether a match might exist using
        the considered mask
      
      * Masks aggregation - Used to increase scale and reduce lookups. Masks
        that only differ by up to eight consecutive bits (delta bits) can be
        aggregated into a single mask. The delta bits then become a part of the
        rule's key. For example, dst_ip/16 and dst_ip/17 can be represented as
        dst_ip/16 with a delta bit of one. Rules using the aggregated mask then
        specify whether the 17-th bit should be masked or not and its value
      ====================
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      756cd366
    • Ido Schimmel's avatar
      mlxsw: spectrum_acl: Start using A-TCAM · a0a777b9
      Ido Schimmel authored
      Now that all the pieces are in place we can start using the A-TCAM
      instead of only using the C-TCAM. This allows for much higher scale and
      better performance (to be improved further by follow-up patch sets).
      
      Perform the integration with the A-TCAM and the eRP core by reverting
      the changes introduced by "mlxsw: spectrum_acl: Enable C-TCAM only mode
      in eRP core" and add calls from the C-TCAM code into the eRP core.
      Signed-off-by: default avatarIdo Schimmel <idosch@mellanox.com>
      Reviewed-by: default avatarJiri Pirko <jiri@mellanox.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      a0a777b9
    • Ido Schimmel's avatar
      mlxsw: spectrum_acl: Add A-TCAM rule insertion and deletion · a8758b67
      Ido Schimmel authored
      Implement rule insertion and deletion into the A-TCAM before we flip the
      driver to start using the A-TCAM.
      
      Rule insertion into the A-TCAM is very similar to C-TCAM, but there are
      subtle differences between regions of different sizes (i.e., different
      number of key blocks).
      
      Specifically, as explained in "mlxsw: spectrum_acl: Allow encoding a
      partial key", in 12 key blocks regions a rule is split into two and the
      two halves of the rule are linked using a "large entry key ID".
      
      Such differences are abstracted away by using different region
      operations per region type.
      Signed-off-by: default avatarIdo Schimmel <idosch@mellanox.com>
      Reviewed-by: default avatarJiri Pirko <jiri@mellanox.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      a8758b67
    • Ido Schimmel's avatar
      mlxsw: spectrum_acl: Pass C-TCAM region and entry to insert function · a20ff8eb
      Ido Schimmel authored
      When A-TCAM will be used together with C-TCAM, the C-TCAM code will need
      to call into the eRP core in order to get an eRP for an inserted entry.
      
      The eRP core takes an A-TCAM region as one of its arguments, so pass the
      C-TCAM region to the insertion function which will later allow us to
      derive the A-TCAM region, given it contains the C-TCAM one.
      Signed-off-by: default avatarIdo Schimmel <idosch@mellanox.com>
      Reviewed-by: default avatarJiri Pirko <jiri@mellanox.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      a20ff8eb
    • Ido Schimmel's avatar
      mlxsw: spectrum_acl: Add A-TCAM region initialization · 6d240650
      Ido Schimmel authored
      Before we start using the A-TCAM we need to make sure the region is
      properly initialized.
      
      This includes the setting of its type (which affects the size of its eRP
      table, for example) and its registration with the eRP core.
      Signed-off-by: default avatarIdo Schimmel <idosch@mellanox.com>
      Reviewed-by: default avatarJiri Pirko <jiri@mellanox.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      6d240650
    • Ido Schimmel's avatar
      mlxsw: spectrum_acl: Make global TCAM resources available to regions · f58df510
      Ido Schimmel authored
      Each TCAM region currently uses its own resources and there is no
      sharing between the different regions.
      
      This is going to change with A-TCAM as each region will need to allocate
      an eRP table from the global eRP tables array.
      
      Make the global TCAM resources available to each region by passing the
      TCAM private data to the region initialization routine.
      Signed-off-by: default avatarIdo Schimmel <idosch@mellanox.com>
      Reviewed-by: default avatarJiri Pirko <jiri@mellanox.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      f58df510
    • Ido Schimmel's avatar
      mlxsw: spectrum_acl: Encapsulate C-TCAM region in A-TCAM region · 57e56d36
      Ido Schimmel authored
      In Spectrum-2 the C-TCAM is only used for rules that can't fit in the
      A-TCAM due to a limited number of masks per A-TCAM region.
      
      In addition, rules inserted into the C-TCAM may affect rules residing in
      the A-TCAM, by clearing their C-TCAM prune bit.
      
      The two regions are thus closely related and can be thought of as if the
      C-TCAM region is encapsulated in the A-TCAM one.
      
      Change the data structures to reflect that before introducing A-TCAM
      support and make C-TCAM region initialization part of the A-TCAM region
      initialization sequence.
      Signed-off-by: default avatarIdo Schimmel <idosch@mellanox.com>
      Reviewed-by: default avatarJiri Pirko <jiri@mellanox.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      57e56d36
    • Ido Schimmel's avatar
      mlxsw: spectrum_acl: Add A-TCAM initialization · 174c0adb
      Ido Schimmel authored
      Initialize the A-TCAM as part of the driver's initialization routine.
      
      Specifically, initialize the eRP tables so that A-TCAM regions will be
      able to perform allocations of eRP tables upon rule insertion in
      subsequent patches.
      Signed-off-by: default avatarIdo Schimmel <idosch@mellanox.com>
      Reviewed-by: default avatarJiri Pirko <jiri@mellanox.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      174c0adb
    • Ido Schimmel's avatar
      mlxsw: spectrum_acl: Allow encoding a partial key · ca49544e
      Ido Schimmel authored
      When working with 12 key blocks in the A-TCAM, rules are split into two
      records, which constitute two lookups. The two records are linked using
      a "large entry key ID". The ID is assigned to key blocks 6 to 11 and
      resolved during the first lookup. The second lookup is performed using
      the ID and the remaining key blocks.
      
      Allow encoding a partial key so that it can be later used to check if an
      ID can be reused.
      
      This is done by adding two arguments to the existing encode function
      that specify the range of the block indexes we would like to encode. The
      key and mask arguments become optional, as we will not need to encode
      both of them all the time.
      Signed-off-by: default avatarIdo Schimmel <idosch@mellanox.com>
      Reviewed-by: default avatarJiri Pirko <jiri@mellanox.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      ca49544e
    • Ido Schimmel's avatar
      mlxsw: spectrum_acl: Extend Spectrum-2 region struct · befc7747
      Ido Schimmel authored
      In a similar fashion to Spectrum-1's region struct, Spectrum-2's struct
      needs to store a pointer to the common region struct.
      
      The pointer will be used in follow-up patches that implement rules
      insertion and deletion.
      Signed-off-by: default avatarIdo Schimmel <idosch@mellanox.com>
      Reviewed-by: default avatarJiri Pirko <jiri@mellanox.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      befc7747
    • Ido Schimmel's avatar
      mlxsw: spectrum_acl: Add support for C-TCAM eRPs · b17b113e
      Ido Schimmel authored
      The number of eRPs that can be used by a single A-TCAM region is limited
      to 16. When more eRPs are needed, an ordinary circuit TCAM (C-TCAM) can
      be used to hold the extra eRPs.
      
      Unlike the A-TCAM, only a single (last) lookup is performed in the
      C-TCAM and not a lookup per-eRP. However, modeling the C-TCAM as extra
      eRPs will allow us to easily introduce support for pruning in a
      follow-up patch set and is also logically correct.
      
      The following diagram depicts the relation between both TCAMs:
                                                                       C-TCAM
      +-------------------+               +--------------------+    +-----------+
      |                   |               |                    |    |           |
      |  eRP #1 (A-TCAM)  +----> ... +----+  eRP #16 (A-TCAM)  +----+  eRP #17  |
      |                   |               |                    |    |    ...    |
      +-------------------+               +--------------------+    |  eRP #N   |
                                                                    |           |
                                                                    +-----------+
      Lookup order is from left to right.
      
      Extend the eRP core APIs with a C-TCAM parameter which indicates whether
      the requested eRP is to be used with the C-TCAM or not.
      
      Since the C-TCAM is only meant to absorb rules that can't fit in the
      A-TCAM due to exceeded number of eRPs or key collision, an error is
      returned when a C-TCAM eRP needs to be created when the eRP state
      machine is in its initial state (i.e., 'no masks'). This should only
      happen in the face of very unlikely errors when trying to push rules
      into the A-TCAM.
      
      In order not to perform unnecessary lookups, the eRP core will only
      enable a C-TCAM lookup for a given region if it knows there are C-TCAM
      eRPs present.
      Signed-off-by: default avatarIdo Schimmel <idosch@mellanox.com>
      Reviewed-by: default avatarJiri Pirko <jiri@mellanox.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      b17b113e
    • Ido Schimmel's avatar
      mlxsw: spectrum_acl: Enable C-TCAM only mode in eRP core · c19df1d8
      Ido Schimmel authored
      Currently, no calls are performed into the eRP core, but in order to
      make review easier we would like to gradually add these calls.
      
      Have the eRP core initialize a region's master mask to all ones and
      allow it to use an empty eRP table. This directs the lookup to the
      C-TCAM and allows the C-TCAM only mode to continue working.
      Signed-off-by: default avatarIdo Schimmel <idosch@mellanox.com>
      Reviewed-by: default avatarJiri Pirko <jiri@mellanox.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      c19df1d8
    • Ido Schimmel's avatar
      mlxsw: spectrum_acl: Implement common eRP core · f465261a
      Ido Schimmel authored
      When rules are inserted into the A-TCAM they are associated with a mask,
      which is part of the lookup key: { masked key, mask ID, region ID }.
      
      These masks are called rule patterns (RP) and the aggregation of several
      masks into one (to be introduced in follow-up patch sets) is called an
      extended RP (eRP).
      
      When a packet undergoes a lookup in an ACL region it is masked by the
      current set of eRPs used by the region, looking for an exact match.
      Eventually, the rule with the highest priority is picked.
      
      These eRPs are stored in several global banks to allow for lookup to
      occur using several eRPs simultaneously.
      
      At first, an ACL region will only require a single mask - upon the
      insertion of the first rule. In this case, the region can use the
      "master RP" which is composed by OR-ing all the masks used by the
      region. This mask is a property of the region and thus there is no need
      to use the above mentioned banks.
      
      At some point, a second mask will be needed. In this case, the region
      will need to allocate an eRP table from the above mentioned banks and
      insert its masks there.
      
      >From now on, upon lookup, the eRP table used by the region will be
      fetched from the eRP banks - using {eRP bank, Index within the bank} -
      and the eRPs present in the table will be used to mask the packet. Note
      that masks with consecutive indexes are inserted into consecutive banks.
      
      When rules are deleted and a region only needs a single mask once again
      it can free its eRP table and use the master RP.
      
      The above logic is implemented in the eRP core and represented using the
      following state machine:
      
          +------------+   create mask - as master RP   +---------------+
          |            +-------------------------------->               |
          |  no masks  |                                |  single mask  |
          |            <--------------------------------+               |
          +------------+          delete mask           +-----+--^------+
                                                              |  |
                                                              |  |
                                        create mask -         |  |  delete mask -
          create mask                   transition to use eRP |  |  transition to
           +--------+                   table                 |  |  use master RP
           |        |                                         |  |
           |        |                                         |  |
      +----v--------+----+         create mask           +----v--+-----+
      |                  <-------------------------------+             |
      |  multiple masks  |                               |  two masks  |
      |                  +------------------------------->             |
      +------------------+      delete mask - if two     +-------------+
                                remaining
      
      The code that actually configures rules in the A-TCAM will interface
      with the eRP core by getting or putting an eRP based on the required
      mask used by the rule.
      Signed-off-by: default avatarIdo Schimmel <idosch@mellanox.com>
      Reviewed-by: default avatarJiri Pirko <jiri@mellanox.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      f465261a
    • Ido Schimmel's avatar
      mlxsw: resources: Add Spectrum-2 eRP resources · 489142ec
      Ido Schimmel authored
      Add the following resources to be used by A-TCAM code:
      * Maximum number of eRP banks
      * Maximum size of eRP bank
      * Number of eRP entries required for a 2/4/8/12 key blocks mask
      Signed-off-by: default avatarIdo Schimmel <idosch@mellanox.com>
      Reviewed-by: default avatarJiri Pirko <jiri@mellanox.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      489142ec
    • Ido Schimmel's avatar
      mlxsw: resources: Add Spectrum-2 maximum large key ID resource · 541e249c
      Ido Schimmel authored
      Add a resource to make sure we do not exceed the maximum number of
      supported large key IDs in a region.
      Signed-off-by: default avatarIdo Schimmel <idosch@mellanox.com>
      Reviewed-by: default avatarJiri Pirko <jiri@mellanox.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      541e249c
    • Ido Schimmel's avatar
      mlxsw: reg: Add Policy-Engine eRP Table Register · 8c0d1cdd
      Ido Schimmel authored
      The register is used to add and delete eRPs from the eRP table.
      Signed-off-by: default avatarIdo Schimmel <idosch@mellanox.com>
      Reviewed-by: default avatarJiri Pirko <jiri@mellanox.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      8c0d1cdd
    • Ido Schimmel's avatar
      mlxsw: reg: Add Policy-Engine TCAM Entry Register Version 3 · aecefac9
      Ido Schimmel authored
      The register is used to configure rules in the A-TCAM.
      Signed-off-by: default avatarIdo Schimmel <idosch@mellanox.com>
      Reviewed-by: default avatarJiri Pirko <jiri@mellanox.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      aecefac9
    • Ido Schimmel's avatar
      mlxsw: reg: Prepare PERERP register for A-TCAM usage · 91329e27
      Ido Schimmel authored
      Before introducing A-TCAM support we need to make sure all the necessary
      fields are configurable and not hard coded to values that worked for the
      C-TCAM only use case.
      
      This includes - for example - the ability to configure the eRP table
      used by the TCAM region.
      Signed-off-by: default avatarIdo Schimmel <idosch@mellanox.com>
      Reviewed-by: default avatarJiri Pirko <jiri@mellanox.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      91329e27