| Message ID | 20181216084851.4967-1-idosch@mellanox.com |
|---|---|
| Headers | show |
| Series | mlxsw: spectrum_acl: Add Bloom filter support | expand |
From: Ido Schimmel <idosch@mellanox.com> Date: Sun, 16 Dec 2018 08:49:23 +0000 > 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. ... As usual, great work and a high quality patch series with test cases and everything from the mlxsw team. Series applied, thank you.
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. Nir Dotan (12): mlxsw: reg: Add Policy Engine Algorithmic Bloom Filter Entries Register mlxsw: resources: Add Spectrum-2 Bloom filter resource mlxsw: spectrum_acl: Introduce Bloom filter mlxsw: spectrum_acl: Add Bloom filter handling mlxsw: spectrum_acl: Add Bloom filter update mlxsw: spectrum_acl: Set A-TCAM rules in Bloom filter mlxsw: spectrum_acl: Update Bloom filter on eRP transitions mlxsw: spectrum_acl: Set master RP index on transition to eRP mlxsw: reg: Activate Bloom filter selftests: mlxsw: Add Bloom filter simple test selftests: mlxsw: Add Bloom filter complex test selftests: mlxsw: Add Bloom delta test drivers/net/ethernet/mellanox/mlxsw/Makefile | 2 +- drivers/net/ethernet/mellanox/mlxsw/reg.h | 71 ++++- .../net/ethernet/mellanox/mlxsw/resources.h | 2 + .../mellanox/mlxsw/spectrum_acl_atcam.c | 20 ++ .../mlxsw/spectrum_acl_bloom_filter.c | 249 ++++++++++++++++++ .../mellanox/mlxsw/spectrum_acl_erp.c | 123 ++++++++- .../mellanox/mlxsw/spectrum_acl_tcam.h | 28 ++ .../drivers/net/mlxsw/spectrum-2/tc_flower.sh | 175 +++++++++++- 8 files changed, 661 insertions(+), 9 deletions(-) create mode 100644 drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_bloom_filter.c