intervals: add helper function to set previous element
Pablo Neira Ayuso
maintainerPATCH v2 1/7 intervals: add helper function to set previous element
Add helper function to set previous element during the automerge iteration. No functional changes are intended.
---
v2: no changes
src/intervals.c | 16 ++++++++++------ 1 file changed, 10 insertions(+), 6 deletions(-)
src/intervals.c +10 -6
@@ -148,6 +148,14 @@ static void set_sort_splice(struct expr *init, struct set *set) } } +static void set_prev_elem (struct expr **prev,struct expr *i, +struct range *prev_range,struct range *range) +{ + *prev = i; +mpz_set (prev_range->low, range->low); +mpz_set (prev_range->high, range->high); +} +static void setelem_automerge (struct set_automerge_ctx *ctx) {struct expr *i, *next, *prev =NULL ;
@@ -168,9 +176,7 @@ static void setelem_automerge(struct set_automerge_ctx *ctx)range_expr_value_high (range.high, i);if (!prev) { - prev = i; -mpz_set (prev_range.low, range.low); -mpz_set (prev_range.high, range.high); +set_prev_elem (&prev, i, &prev_range, &range);continue ; }
@@ -192,9 +198,7 @@ static void setelem_automerge(struct set_automerge_ctx *ctx) } } - prev = i; -mpz_set (prev_range.low, range.low); -mpz_set (prev_range.high, range.high); +set_prev_elem (&prev, i, &prev_range, &range); }mpz_clear (prev_range.low);
Signature · 1 line
2.30.2
Pablo Neira Ayuso
maintainerPATCH v2 2/7 intervals: do not merge intervals with different timeout
If timeout/expiration of contiguous intervals is different, then do not merge them.
---
v2: missing forward declaration, otherwise patch breaks bisection.
src/intervals.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-)
src/intervals.c +5 -1
@@ -156,6 +156,8 @@ static void set_prev_elem(struct expr **prev, struct expr *i,mpz_set (prev_range->high, range->high); } +static struct expr *interval_expr_key (struct expr *i); +static void setelem_automerge (struct set_automerge_ctx *ctx) {struct expr *i, *next, *prev =NULL ;
@@ -175,7 +177,9 @@ static void setelem_automerge(struct set_automerge_ctx *ctx)range_expr_value_low (range.low, i);range_expr_value_high (range.high, i); -if (!prev) { +if (!prev || +interval_expr_key (prev)->timeout !=interval_expr_key (i)->timeout || +interval_expr_key (prev)->expiration !=interval_expr_key (i)->expiration) {set_prev_elem (&prev, i, &prev_range, &range);continue ; }
Signature · 1 line
2.30.2
Pablo Neira Ayuso
maintainerPATCH v2 3/7 src: add EXPR_RANGE_VALUE expression and use it
In reply to Pablo Neira Ayusoset element with range takes 4 instances of struct expr:
EXPR_SET_ELEM -> EXPR_RANGE -> (2) EXPR_VALUE
where EXPR_RANGE represents two references to struct expr with constant value.
This new EXPR_RANGE_VALUE trims it down to two expressions:
EXPR_SET_ELEM -> EXPR_RANGE_VALUE
with two direct low and high values that represent the range:
struct {
mpz_t low;
mpz_t high;
};this two new direct values in struct expr do not modify its size.
setelem_expr_to_range() translates EXPR_RANGE to EXPR_RANGE_VALUE, this conversion happens at a later stage.
constant_range_expr_print() translates this structure to constant values to reuse the existing datatype_print() which relies in singleton values.
The automerge routine has been updated to use EXPR_RANGE_VALUE.
This requires a follow up patch to rework the conversion from range expression to singleton element to provide a noticeable memory consumption reduction.
---
v2: add constant_range_expr_print_one() and use it.
include/expression.h | 13 +++++++ src/expression.c | 83 +++++++++++++++++++++++++++++++++++++++++ src/intervals.c | 88 ++++++++++++++++++++++---------------------- src/mergesort.c | 2 + 4 files changed, 143 insertions(+), 43 deletions(-)
include/expression.h +13 -0
@@ -48,6 +48,7 @@* @EXPR_XFRM XFRM (ipsec) expression * @EXPR_SET_ELEM_CATCHALL catchall element expression * @EXPR_FLAGCMP flagcmp expression +* @EXPR_RANGE_VALUE constant range expression */ enum expr_types {EXPR_INVALID ,
@@ -80,6 +81,7 @@ enum expr_types {EXPR_XFRM ,EXPR_SET_ELEM_CATCHALL ,EXPR_FLAGCMP , +EXPR_RANGE_VALUE , EXPR_MAX = EXPR_FLAGCMP };
@@ -278,6 +280,11 @@ struct expr {/* EXPR_VALUE */ mpz_t value; }; +struct { +/* EXPR_RANGE_VALUE */ +mpz_t low; +mpz_t high; + } range;struct {/* EXPR_PREFIX */ struct expr *prefix;
@@ -473,6 +480,12 @@ extern struct expr *constant_expr_join(const struct expr *e1, const struct expr *e2);extern struct expr *constant_expr_splice (struct expr *expr,unsigned int len); +extern struct expr *constant_range_expr_alloc (const struct location *loc, +const struct datatype *dtype, +enum byteorder byteorder, +unsigned int len, +mpz_t low,mpz_t high); + extern struct expr *flag_expr_alloc(const struct location *loc, const struct datatype *dtype, enum byteorder byteorder,
src/expression.c +83 -0
107 lines not on this page · raw message
src/intervals.c +45 -43
193 lines not on this page · raw message
src/mergesort.c +2 -0
@@ -38,6 +38,8 @@ static mpz_srcptr expr_msort_value(const struct expr *expr, mpz_t value)return expr_msort_value (expr->left, value);case EXPR_VALUE :return expr->value; +case EXPR_RANGE_VALUE : +return expr->range.low;case EXPR_CONCAT :concat_expr_msort_value (expr, value);break ;
Signature · 1 line
2.30.2
Pablo Neira Ayuso
maintainerPATCH v2 4/7 rule: constify set_is_non_concat_range()
In reply to Pablo Neira AyusoThis is read-only, constify it.
---
v2: no changes
include/rule.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
include/rule.h +1 -1
@@ -423,7 +423,7 @@ static inline bool set_is_interval(uint32_t set_flags)return set_flags &NFT_SET_INTERVAL ; } -static inline bool set_is_non_concat_range (struct set *s) +static inline bool set_is_non_concat_range (const struct set *s) {return (s->flags &NFT_SET_INTERVAL ) && s->desc.field_count <=1 ; }
Signature · 1 line
2.30.2
Pablo Neira Ayuso
maintainerPATCH v2 5/7 mnl: rename list of expression in mnl_nft_setelem_batch()
In reply to Pablo Neira AyusoRename set to init to prepare to pass struct set to this function in the follow up patch. No functional changes are intended.
---
v2: no changes.
src/mnl.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-)
src/mnl.c +6 -6
@@ -1731,7 +1731,7 @@ static int mnl_nft_setelem_batch(const struct nftnl_set *nls, struct cmd *cmd,struct nftnl_batch *batch, enum nf_tables_msg_types msg_type, unsigned int flags, uint32_t *seqnum, - const struct expr *set, + const struct expr *init, struct netlink_ctx *ctx) { struct nlattr *nest1, *nest2;
@@ -1743,8 +1743,8 @@ static int mnl_nft_setelem_batch(const struct nftnl_set *nls, struct cmd *cmd,if (msg_type ==NFT_MSG_NEWSETELEM ) flags |=NLM_F_CREATE ; -if (set) - expr = list_first_entry(&set->expressions, struct expr, list); +if (init) + expr = list_first_entry(&init->expressions, struct expr, list); next: nlh = nftnl_nlmsg_build_hdr(nftnl_batch_buffer(batch), msg_type,
@@ -1764,13 +1764,13 @@ next: htonl(nftnl_set_get_u32(nls, NFTNL_SET_ID))); } -if (!set ||list_empty (&set->expressions)) +if (!init ||list_empty (&init->expressions))return 0 ;assert (expr); nest1 =mnl_attr_nest_start (nlh,NFTA_SET_ELEM_LIST_ELEMENTS ); -list_for_each_entry_from (expr, &set->expressions, list) { - nlse =alloc_nftnl_setelem (set, expr); +list_for_each_entry_from (expr, &init->expressions, list) { + nlse =alloc_nftnl_setelem (init, expr);cmd_add_loc (cmd, nlh, &expr->location); nest2 =mnl_attr_nest_start (nlh, ++i);
Signature · 1 line
2.30.2
Pablo Neira Ayuso
maintainerPATCH v2 6/7 mnl: do not send set size when set is constant set
In reply to Pablo Neira AyusoWhen turning element range into the interval representation based on singleton elements for the rbtree tree set backend, userspace adjusts the size to the internal kernel implementation.
For constant sets, this is leaking an internal kernel implementation detail that is fixed by kernel patch ("netfilter: nf_tables: fix set size with rbtree backend"). For non-constant sets, set size is just broken.
This patch is required by the follow up patch ("src: rework singleton interval transformation to reduce memory consumption").
On top of this, constant sets cannot be updated once they are bound, set size is not useful in this case. Remove this implicit set size for constant sets.
---
v2: new in this series.
src/mnl.c | 2 -- 1 file changed, 2 deletions(-)
src/mnl.c +0 -2
@@ -1265,8 +1265,6 @@ int mnl_nft_set_add(struct netlink_ctx *ctx, struct cmd *cmd,if (set->desc.size !=0 )nftnl_set_set_u32 (nls,NFTNL_SET_DESC_SIZE , set->desc.size); - }else if (set->init) { -nftnl_set_set_u32 (nls,NFTNL_SET_DESC_SIZE , set->init->size); } udbuf =nftnl_udata_buf_alloc (NFT_USERDATA_MAXLEN );
Signature · 1 line
2.30.2
Pablo Neira Ayuso
maintainerPATCH v2 7/7 src: rework singleton interval transformation to reduce memory consumption
In reply to Pablo Neira Ayusoset_to_intervals() expands range expressions into a list of singleton elements before building the netlink message that is sent to userspace. This is because the kernel expects this list of singleton elements where EXPR_F_INTERVAL_END denotes a closing interval. This expansion significantly increases memory consumption in userspace.
This patch updates the logic to transform the range expression up to two temporary singleton element expressions through setelem_to_interval(). Then, these two elements are used to allocate the nftnl_set_elem objects through alloc_nftnl_setelem_interval() to build the netlink message, finally all these temporary objects are released. For anonymous sets, when adjacent ranges are found, the end element is not added to the set to pack the set representation as in the original set_to_intervals() routine.
After this update, set_to_intervals() only deals with adding the non-matching all zero element to the interval set when it is not there as the kernel expects.
In combination with the new EXPR_RANGE_VALUE expression, this shrinks runtime userspace memory consumption from 70.50 Mbytes to 43.38 Mbytes for a 100k intervals set sample.
---
v2: - restore set_to_intervals() to use loop to iterate elements.
- added handling to pack adjacents ranges in anonymous sets for mnl_nft_setelem_batch() and setelem_to_interval().
- fix handling of all-zero never-match element in setelem_to_interval() leading to bogus zero element in set.
include/intervals.h | 2 + include/list.h | 8 ++ include/mnl.h | 3 +- src/intervals.c | 187 +++++++++++++++++++++++++++++--------------- src/mnl.c | 70 +++++++++++++++-- src/rule.c | 4 +- 6 files changed, 202 insertions(+), 72 deletions(-)
include/intervals.h +2 -0
@@ -7,5 +7,7 @@ int set_delete(struct list_head *msgs, struct cmd *cmd, struct set *set, struct expr *init, unsigned int debug_mask);int set_overlap (struct list_head *msgs,struct set *set,struct expr *init);int set_to_intervals (const struct set *set,struct expr *init,bool add); +int setelem_to_interval (const struct set *set,struct expr *elem, +struct expr *next_elem,struct list_head *interval_list);#endif
include/list.h +8 -0
@@ -348,6 +348,14 @@ static inline void list_splice_tail_init(struct list_head *list,#define list_first_entry (ptr, type, member) \ list_entry((ptr)->next, type, member) +/** +* list_prev_entry - get the prev element in list +* @ptr: the type * to cursor +* @member: the name of the list_head within the struct. +*/ +#define list_prev_entry (ptr, member) \ + list_entry((ptr)->member.prev, typeof(*(ptr)), member) +/** * list_last_entry - get the last element from a list * @ptr: the list head to take the element from.
include/mnl.h +2 -1
@@ -66,7 +66,8 @@ int mnl_nft_setelem_add(struct netlink_ctx *ctx, struct cmd *cmd, const struct set *set, const struct expr *expr, unsigned int flags);int mnl_nft_setelem_del (struct netlink_ctx *ctx,struct cmd *cmd, -const struct handle *h,const struct expr *init); +const struct handle *h,const struct set *set, +const struct expr *init);int mnl_nft_setelem_flush (struct netlink_ctx *ctx,const struct cmd *cmd);int mnl_nft_setelem_get (struct netlink_ctx *ctx,struct nftnl_set *nls,bool reset);
src/intervals.c +125 -62
220 lines not on this page · raw message
src/mnl.c +63 -7
122 lines not on this page · raw message
src/rule.c +2 -2
@@ -1550,14 +1550,14 @@ static int do_command_insert(struct netlink_ctx *ctx, struct cmd *cmd)static int do_delete_setelems (struct netlink_ctx *ctx,struct cmd *cmd) { +const struct set *set = cmd->elem.set;struct expr *expr = cmd->elem.expr; -struct set *set = cmd->elem.set;if (set_is_non_concat_range (set) &&set_to_intervals (set, expr, false) <0 )return -1 ; -if (mnl_nft_setelem_del (ctx, cmd, &cmd->handle, cmd->elem.expr) <0 ) +if (mnl_nft_setelem_del (ctx, cmd, &cmd->handle, set, cmd->elem.expr) <0 )return -1 ;return 0 ;
Signature · 1 line
2.30.2