]> git.ipfire.org Git - thirdparty/nftables.git/commit
src: replace interval segment tree overlap and automerge
authorPablo Neira Ayuso <pablo@netfilter.org>
Wed, 13 Apr 2022 02:01:13 +0000 (04:01 +0200)
committerPablo Neira Ayuso <pablo@netfilter.org>
Wed, 13 Apr 2022 11:43:48 +0000 (13:43 +0200)
commit81e36530fcace45a354a09ff3fd2697ff6ff4510
tree7741db1cabb9cab2eb276dbe56797c23dfd4ccc2
parentf1cc44edb2182ce745d008cc6932afad165d02c6
src: replace interval segment tree overlap and automerge

This is a rewrite of the segtree interval codebase.

This patch now splits the original set_to_interval() function in three
routines:

- add set_automerge() to merge overlapping and contiguous ranges.
  The elements, expressed either as single value, prefix and ranges are
  all first normalized to ranges. This elements expressed as ranges are
  mergesorted. Then, there is a linear list inspection to check for
  merge candidates. This code only merges elements in the same batch,
  ie. it does not merge elements in the kernela and the userspace batch.

- add set_overlap() to check for overlapping set elements. Linux
  kernel >= 5.7 already checks for overlaps, older kernels still needs
  this code. This code checks for two conflict types:

  1) between elements in this batch.
  2) between elements in this batch and kernelspace.

  The elements in the kernel are temporarily merged into the list of
  elements in the batch to check for this overlaps. The EXPR_F_KERNEL
  flag allows us to restore the set cache after the overlap check has
  been performed.

- set_to_interval() now only transforms set elements, expressed as range
  e.g. [a,b], to individual set elements using the EXPR_F_INTERVAL_END
  flag notation to represent e.g. [a,b+1), where b+1 has the
  EXPR_F_INTERVAL_END flag set on.

More relevant updates:

- The overlap and automerge routines are now performed in the evaluation
  phase.

- The userspace set object representation now stores a reference to the
  existing kernel set object (in case there is already a set with this
  same name in the kernel). This is required by the new overlap and
  automerge approach.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
include/Makefile.am
include/expression.h
include/intervals.h [new file with mode: 0644]
include/rule.h
src/Makefile.am
src/evaluate.c
src/intervals.c [new file with mode: 0644]
src/mergesort.c
src/rule.c
src/segtree.c