convert rbtree to binary search array
Get series with b4
b4 am [email protected]Versions newest first · linked by author and title
- v2 Latest4 patches 0 repliesNew
- v13 patches 1 replySuperseded
Patches in v2 No applies recorded yet
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/4 | netfilter: nf_tables: add .abort_skip_removal flag for set typesinclude/ net/ net/ | +6 | 0 replies | |
| 2/4 | netfilter: nft_set_rbtree: translate rbtree to array for binary searchnet/ | +257 | 0 replies | |
| 3/4 | netfilter: nft_set_rbtree: use binary search array in get commandnet/ | +64 | 0 replies | |
| 4/4 | netfilter: nft_set_rbtree: remove seqcount_rwlock_tnet/ | +0 | 0 replies |
Reviews trailers per patch
No Reviewed-by, Acked-by or Tested-by trailers for v2 yet.
Cover letter [PATCH nf-next,v2 0/4] convert rbtree to binary search array
Hi,
v2: - fix kdoc in 1/4
- fix sparse warning in nft_rbtree_destroy() in 2/4
- add 4/4, new in this series.
Florian reported that there is currently an issue with interval matching in the rbtree, allowing for false negative lookup during transaction.
This series addresses this issue by translating the rbtree, which keeps the intervals in order, to binary search. The array is published to packet path through RCU. The idea is to keep using the rbtree datastructure for control plane, which needs to deal with updates, then generate an array using this rbtree for binary search lookups.
Patch #1 allows to call .remove in case .abort is defined, which is needed by this new approach. Only pipapo needs to skip .remove to speed.
Patch #2 add the binary search array approach for interval matching.
Patch #3 updates .get to use the binary search array to find for (closest or exact) interval matching.
Patch #4 removes seqcount_rwlock_t as it is not needed anymore (new in this series).
This can possibly go to nf.git alternatively since it qualifies as bugfix, feel free to pick the best route for it.
Pablo Neira Ayuso (4):
netfilter: nf_tables: add .abort_skip_removal flag for set types
netfilter: nft_set_rbtree: translate rbtree to array for binary search
netfilter: nft_set_rbtree: use binary search array in get command
netfilter: nft_set_rbtree: remove seqcount_rwlock_t
include/net/netfilter/nf_tables.h | 2 + net/netfilter/nf_tables_api.c | 3 +- net/netfilter/nft_set_pipapo.c | 2 + net/netfilter/nft_set_rbtree.c | 429 ++++++++++++++++++++---------- 4 files changed, 291 insertions(+), 145 deletions(-)
Signature · 1 line
2.47.3