summaryrefslogtreecommitdiffstats
path: root/src/segtree.c
Commit message (Collapse)AuthorAgeFilesLines
* src: add debugging mask to context structurePablo Neira Ayuso2017-08-231-12/+15
| | | | | | | So this toggle is not global anymore. Update name that fits better with the semantics of this variable. Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* src: remove ifdef DEBUG pollutionPablo Neira Ayuso2017-08-231-2/+1
| | | | | | | | | | | | | | | Get rid of lots of ifdef DEBUG pollution in the code. The --debug= option is useful to get feedback from users, so it should be always there. And we really save nothing from keeping this code away from the control plane with a compile time option. Just running tests/shell/ before and after this patch, time shows almost no difference. So this patch leaves --enable-debug around to add debugging symbols in your builds, this is left set on by default. Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* segtree: Introduce flag for half-open range elementsPhil Sutter2017-07-191-0/+5
| | | | | | | | | This flag is required by userspace only, so can live within userdata. It's sole purpose is for 'nft monitor' to detect half-open ranges (which are comprised of a single element only). Signed-off-by: Phil Sutter <phil@nwl.cc> Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* segtree: Fix expr_value_cmp()Phil Sutter2017-07-171-4/+6
| | | | | | | | | Instead of returning the result of mpz_cmp(), this function returned 1 unless both elements were equal and the first one had EXPR_F_INTERVAL_END set. Signed-off-by: Phil Sutter <phil@nwl.cc> Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* src: Pass stateless, numeric, ip2name and handle variables as structure members.Varsha Rao2017-06-181-1/+3
| | | | | | | | | | | | | | | | | libnftables library will be created soon. So declare numeric_output, stateless_output, ip2name_output and handle_output as members of structure output_ctx, instead of global variables. Rename these variables as following, numeric_output -> numeric stateless_output -> stateless ip2name_output -> ip2name handle_output -> handle Also add struct output_ctx *octx as member of struct netlink_ctx. Signed-off-by: Varsha Rao <rvarsha016@gmail.com> Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* segtree: reset element size counter before adding intervals to setPablo Neira Ayuso2017-05-261-0/+2
| | | | | | | Otherwise we get double the real size in terms of set elements during the interval expansion to individual elements. Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* src: remove SET_F_* flag definitionsPablo Neira Ayuso2017-01-031-2/+2
| | | | | | | They map exactly one to one to we have in the kernel headers, so use kernel definitions instead. Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* segtree: allocate memory for arrays on heapOleksandr Natalenko2017-01-031-1/+10
| | | | | | | | | Huge sets may cause stack to be exhausted. So, put allocate memory for arrays in interval_map_decompose() function on heap. Signed-off-by: Oleksandr Natalenko <oleksandr@natalenko.name> Signed-off-by: Florian Westphal <fw@strlen.de>
* segtree: don't trigger error on exact overlapsPablo Neira Ayuso2016-12-131-0/+4
| | | | | | | | | | | | | | | | So adding the same element doesn't trigger any error: # nft add element filter bogons { 3.3.3.123/24 } # nft add element filter bogons { 3.3.3.123/24 } Still kernel reports an error if we use create instead: # nft create element filter bogons { 3.3.3.123/24 } <cmdline>:1:1-46: Error: Could not process rule: File exists create element filter bogons { 3.3.3.123/24 } ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* segtree: wrong prefix expression length on interval_map_decompose()Pablo Neira Ayuso2016-12-131-1/+2
| | | | | | | | | | | | | | | | | interval_map_decompose() sets expr->len to zero. This causes problems from expr_to_intervals() that calls range_expr_value_high() and calculates: expr->len - expr->prefix_len this operation underflows, then mpz_init_bitmask() allocates a huge bitmask. Use expr_value(i)->len given that we already use this to calculate the prefix length. Reported-by: Richard Mörbitz <richard.moerbitz@tu-dresden.de> Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* segtree: keep element comments in set intervalsPablo Neira Ayuso2016-11-091-3/+7
| | | | | | | | | The conversion from the set element range representation to element intervals doesn't keep the comment information around. Fixes: https://bugzilla.netfilter.org/show_bug.cgi?id=1090 Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org> Tested-by: Arturo Borrero Gonzalez <arturo@debian.org>
* segtree: don't check for overlaps if set definition is emptyPablo Neira Ayuso2016-06-221-1/+1
| | | | | | | If the set comes without definition (ie. no elements) then skip check for overlaps since set->init is NULL. Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* src: declare interval_map_decompose() from header filePablo Neira Ayuso2016-05-131-2/+0
| | | | | | Instead of having several extern function declarations. Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* segtree: add interval overlap detection for dynamic updatesPablo Neira Ayuso2016-04-271-3/+52
| | | | | | | Make sure the new intervals that we want to add are not overlapping with any of the existing ones. Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* segtree: rename set expression set_to_segtree()Pablo Neira Ayuso2016-04-271-7/+7
| | | | | | | This function is modified by a follow up patch to take the set object, so rename it to init. Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* segtree: add expr_to_intervals()Pablo Neira Ayuso2016-04-271-8/+26
| | | | | | | | | | | Refactor code to add the new expr_to_intervals(). This function takes the list of set element expressions and convert them to a list of half-closed intervals. This is useful for different purposes, such as interval overlap and conflicts detection. Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* segtree: set expr->len for prefix expression from interval_map_decompose()Pablo Neira Ayuso2016-04-271-0/+1
| | | | | | This field needs to be set for the new interval overlap detection. Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* segtree: special handling for the first non-matching segmentPablo Neira Ayuso2016-04-251-6/+40
| | | | | | | Add the first non-matching segment if the set is empty or if the set becomes empty after the element removal. Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* segtree: explicit initialization via set_to_intervals()Pablo Neira Ayuso2016-04-251-7/+8
| | | | | | | Allow explicit compound expression to initialize the set intervals. Incremental updates to interval sets require this. Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* segtree: handle adjacent interval nodes from expr_value_cmp()Pablo Neira Ayuso2016-04-251-1/+8
| | | | | | | Named sets may contain adjacent interval nodes, when equal in key, look at the flags. Those with EXPR_F_INTERVAL_END should come in first place. Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* segtree: clone full expression from interval_map_decompose()Pablo Neira Ayuso2016-04-251-1/+1
| | | | | | | Instead of cloning just its value, expr_value() expects a set element or mapping. Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* segtree: perform stricter expression type validation from expr_value()Pablo Neira Ayuso2016-04-251-2/+6
| | | | | | | | | | This helper function returns a expression value type that represents the set element key. This functions currently expects two kind of expressions: set elements and mappings. Bail out otherwise, if we see anything else, we have to fix our code. Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* expr: add set_elem_expr as container for set element attributesPatrick McHardy2015-04-121-2/+6
| | | | | | | | | | | | | | | | | | | | | | | | Add a new expression type "set_elem_expr" that is used as container for the key in order to attach different attributes, such as timeout values, to the key. The expression hierarchy is as follows: Sets: elem | key Maps: mapping / \ elem data | key Signed-off-by: Patrick McHardy <kaber@trash.net>
* src: modify pr_debug() to use printf and introduce to pr_gmp_debug()Pablo Neira Ayuso2015-01-081-11/+11
| | | | | | | | | | | | | Modify pr_debug() to use printf so we get debugging traces for proto-ctx when --with-mini-gmp is enabled. Add pr_gmp_debug(), this is disabled with --with-mini-gmp since it relies on the gmp_printf(), which is not available in the mini-gmp implementation. Suggested by Patrick. Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* expr: make range_low()/range_high() usable outside of segtreePatrick McHardy2014-09-241-40/+2
| | | | | | | Their functionality is also needed for set descriptions, move the functions to expressions.c and give them a more suitable name for global functions. Signed-off-by: Patrick McHardy <kaber@trash.net>
* segtree: sort set elements before decompositionPatrick McHardy2014-03-071-6/+22
| | | | | | | | The decomposition phase currently depends on the kernel returning elements in sorted order. This is a fragile assumption, change the code to sort the elements itself. Signed-off-by: Patrick McHardy <kaber@trash.net>
* set: abort on interval conflictsPatrick McHardy2014-03-071-6/+15
| | | | | | | | | | | We currently print a debug message (with debugging) and continue. Output a proper error message and abort. While at it, make sure we only report a conflict if there actually is one. This is not the case similar actions, IOW in case of sets, never, in case of maps, only if the mapping differs. Signed-off-by: Patrick McHardy <kaber@trash.net>
* segtree: fix decomposition of unclosed intervalsPatrick McHardy2014-01-161-9/+30
| | | | | | | | | | | | | | | | | | | | | | | | | | | If intervals are directly adjacent or extend to the right end of the dimension, they are not closed by a EXPR_F_INTERVAL_END entry. This leads to multiple errors when decomposing the intervals: - the last unclosed interval is not shown at all. - if a range is unclosed and the set is a map, the starting point of the next interval is set to the data, not the key, leading to nonsensical output. - if a prefix is unclosed, the interval is assumed to be a prefix as well and the same starting point is kept. This makes sense for cases like 192.168.0.0/24, 192.168.0.0/16, but leads to hard to understand results if the next interval is not representable as a prefix. Fix this by doing two things: - add an EXPR_F_INTERVAL_END element for each unclosed interval during preprocessing. - process the final unclosed interval extending to the right end of the dimension, if present. Signed-off-by: Patrick McHardy <kaber@trash.net>
* segtree: only use prefix expressions for ranges for selected datatypesPatrick McHardy2014-01-161-1/+3
| | | | | | | | | | | | | | | | | | | | | | It is uncommon to represent f.i. port number ranges as prefix expressions. Introduce a datatype DTYPE_F_PREFIX flag to indicate that the preferred representation of a range is a prefix and use it for segtree decomposition to decide whether to use a range or prefix expression. The ipaddr, ip6addr, mark and realm datatypes are changed to include the DTYPE_F_PREFIX flag. This fixes completely unreadable output in cases where the ranges are representable as prefixes, f.i. in case of port number: { 0/6 => jump chain1, 0/5 => jump chain2, 0/4 => continue} becomes: { 0-1023 => jump chain1, 1024-2047 => jump chain2, 2048-4095 => continue} Signed-off-by: Patrick McHardy <kaber@trash.net>
* segtree: add new segtree debugging optionPablo Neira Ayuso2014-01-151-10/+33
| | | | | | | | | Currently, nft displays the debugging information if it's compiled with --enable-debug (which seems a good idea) and when intervals are used in maps. Add a new option to enable debugging to segtree, so we only get this information when explicitly requested. Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* seqtree: update mapping data when keeping the basePatrick McHardy2012-12-081-3/+8
| | | | | | | | When a prefix expression is followed by another prefix expression using the same base but a wider prefix, we need to update the mapping data to that of the second expression. Signed-off-by: Patrick McHardy <kaber@trash.net>
* segtree: fix segtree to properly support mappingsPatrick McHardy2012-12-081-32/+59
| | | | | | | Requires to use proper types for keys and data and using the key values for reverse transformation. Signed-off-by: Patrick McHardy <kaber@trash.net>
* debug: include verbose message in all BUG statementsroot2012-12-081-2/+2
| | | | Signed-off-by: Patrick McHardy <kaber@trash.net>
* expression: Differentiate expr among anonymous structures in struct exprTomasz Bursztyka2012-08-031-2/+2
| | | | | | | This fixes compilation with gcc-4.7 Signed-off-by: Tomasz Bursztyka <tomasz.bursztyka@linux.intel.com> Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
* Initial commitv0.01-alpha1Patrick McHardy2009-03-181-0/+541