summaryrefslogtreecommitdiffstats
path: root/src/segtree.c
Commit message (Collapse)AuthorAgeFilesLines
...
* 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