Message-ID: <20181216084851.4967-1-idosch@mellanox.com>
Date:   Sun, 16 Dec 2018 08:49:23 +0000
From:   Ido Schimmel <idosch@...lanox.com>
To:     "netdev@...r.kernel.org" <netdev@...r.kernel.org>
CC:     "davem@...emloft.net" <davem@...emloft.net>,
        Jiri Pirko <jiri@...lanox.com>, Nir Dotan <nird@...lanox.com>,
        mlxsw <mlxsw@...lanox.com>, Ido Schimmel <idosch@...lanox.com>
Subject: [PATCH net-next 00/12] 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.

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

Powered by blists - more mailing lists