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
--
2.20.0
