summaryrefslogtreecommitdiffstats
path: root/src/intervals.c
Commit message (Collapse)AuthorAgeFilesLines
* intervals: deletion should adjust range not yet in the kernelPablo Neira Ayuso2022-05-071-3/+0
| | | | | | | | | | | | | | | Do not remove the range if it does not exists yet in the kernel, adjust it instead. Uncovered by use-after-free error. ==276702==ERROR: AddressSanitizer: heap-use-after-free on address 0x60d00190663c at pc 0x7ff310ab526f bp 0x7fffeb76f750 sp 0x7fffeb76f748 READ of size 4 at 0x60d00190663c thread T0 #0 0x7ff310ab526e in __adjust_elem_right .../nftables/src/intervals.c:300 #1 0x7ff310ab59a7 in adjust_elem_right .../nftables/src/intervals.c:311 #2 0x7ff310ab6daf in setelem_adjust .../nftables/src/intervals.c:354 #3 0x7ff310ab783a in setelem_delete .../nftables/src/intervals.c:411 #4 0x7ff310ab80e6 in __set_delete .../nftables/src/intervals.c:451 Fixes: 3e8d934e4f72 ("intervals: support to partial deletion with automerge") Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* src: fix always-true assertionsFlorian Westphal2022-04-261-2/+3
| | | | | | | assert(1) is a no-op, this should be assert(0). Use BUG() instead. Add missing CATCHALL to avoid BUG(). Signed-off-by: Florian Westphal <fw@strlen.de>
* intervals: set on EXPR_F_KERNEL flag for new elements in set cachePablo Neira Ayuso2022-04-181-0/+3
| | | | | | | | | So follow up command in this batch that update the set assumes this element is already in the kernel. Fixes: 3da9643fb9ff ("intervals: add support to automerge with kernel elements") Fixes: 3ed9fadaab95 ("intervals: build list of elements to be added from cache") Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* intervals: build list of elements to be added from cachePablo Neira Ayuso2022-04-181-40/+30
| | | | | | | | | | | Loop over the set cache and add elements that have no EXPR_F_KERNEL, meaning that these are new elements in the set that have resulted from adjusting/split existing ranges. This fixes several partial deletions of the same interval in one command. Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* intervals: fix deletion of multiple ranges with automergePablo Neira Ayuso2022-04-181-12/+22
| | | | | | | | | Iterate over the list of elements to be deleted, then splice one EXPR_F_REMOVE element at a time to update the list of existing sets incrementally. Fixes: 3e8d934e4f722 ("intervals: support to partial deletion with automerge") Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* intervals: add elements with EXPR_F_KERNEL to purge list onlyPablo Neira Ayuso2022-04-181-3/+7
| | | | | | | | Do not add elements to purge list which are not in the kernel, otherwise, bogus ENOENT is reported. Fixes: 3e8d934e4f722 ("intervals: support to partial deletion with automerge") Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* intervals: Simplify element sanity checksPhil Sutter2022-04-141-16/+10
| | | | | | | | | | Since setelem_delete() assigns to 'prev' pointer only if it doesn't have EXPR_F_REMOVE flag set, there is no need to check that flag in called functions. Fixes: 3e8d934e4f722 ("intervals: support to partial deletion with automerge") Signed-off-by: Phil Sutter <phil@nwl.cc> Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* intervals: unset EXPR_F_KERNEL for adjusted elementsPablo Neira Ayuso2022-04-131-3/+3
| | | | | | | | | | | | | | | | This element is adjusted, reset the EXPR_F_KERNEL flag, this is a new element and the old is purged from the kernel. The existing list of elements in the kernel is spliced to the elements to be removed, then merge-sorted. The EXPR_F_REMOVE flag specifies that this element represents a deletion. The EXPR_F_REMOVE and EXPR_F_KERNEL allows to track objects: whether element is in the kernel (EXPR_F_KERNEL), element is new (no flag) or element represents a removal (EXPR_F_REMOVE). Reported-by: Phil Sutter <phil@nwl.cc> Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* src: restore interval sets work with string datatypesPablo Neira Ayuso2022-04-131-0/+6
| | | | | | | | | | | Switch byteorder of string datatypes to host byteorder. Partial revert of ("src: make interval sets work with string datatypes") otherwise new interval code complains with conflicting intervals. testcases/sets/sets_with_ifnames passes fine again. Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* intervals: support to partial deletion with automergePablo Neira Ayuso2022-04-131-0/+250
| | | | | | | | | | | | | | | | | | | | | | | | Splice the existing set element cache with the elements to be deleted and merge sort it. The elements to be deleted are identified by the EXPR_F_REMOVE flag. The set elements to be deleted is automerged in first place if the automerge flag is set on. There are four possible deletion scenarios: - Exact match, eg. delete [a-b] and there is a [a-b] range in the kernel set. - Adjust left side of range, eg. delete [a-b] from range [a-x] where x > b. - Adjust right side of range, eg. delete [a-b] from range [x-b] where x < a. - Split range, eg. delete [a-b] from range [x-y] where x < a and b < y. Update nft_evaluate() to use the safe list variant since new commands are dynamically registered to the list to update ranges. This patch also restores the set element existence check for Linux kernels <= 5.7. Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* intervals: add support to automerge with kernel elementsPablo Neira Ayuso2022-04-131-26/+118
| | | | | | | | | | | | | | | | | | Extend the interval codebase to support for merging elements in the kernel with userspace element updates. Add a list of elements to be purged to cmd and set objects. These elements representing outdated intervals are deleted before adding the updated ranges. This routine splices the list of userspace and kernel elements, then it mergesorts to identify overlapping and contiguous ranges. This splice operation is undone so the set userspace cache remains consistent. Incrementally update the elements in the cache, this allows to remove dd44081d91ce ("segtree: Fix add and delete of element in same batch"). Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* src: replace interval segment tree overlap and automergePablo Neira Ayuso2022-04-131-0/+392
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>