shrink memory usage for interval sets
Pablo Neira Ayuso
maintainercover shrink memory usage for interval sets
Hi,
This is a continuation in the effort to reduce memory consumption for sets from userspace.
Patch #1 adds a helper function as preparation work.
Patch #2 fixes invalid auto-merging of elements with different timeout.
Patch #3 add EXPR_RANGE_VALUE to reduce memory consumption of ranges, which now require two struct expr instead of four.
Patch #4 makes a simple constification of a helper function to detect interval sets with single key.
Patch #5 renames a field from set to init in mnl_nft_setelem_batch() to prepare for passing struct set.
Patch #6 reworks the transformation from range to the singleton elements that represents intervals through EXPR_F_INTERVAL_END to create them only before the netlink message.
This shrinks runtime userspace memory consumption from 70.50 Mbytes to 43.38 Mbytes for a 100k intervals set sample.
Pablo Neira Ayuso (6):
intervals: add helper function to set previous element
intervals: do not merge intervals with different timeout
src: add EXPR_RANGE_VALUE expression and use it
rule: constify set_is_non_concat_range()
mnl: rename list of expression in mnl_nft_setelem_batch()
src: rework singleton interval transformation to reduce memory consumption
include/expression.h | 13 ++ include/intervals.h | 2 + include/list.h | 8 ++ include/mnl.h | 3 +- include/rule.h | 2 +- src/expression.c | 85 +++++++++++++ src/intervals.c | 280 +++++++++++++++++++++++++------------------ src/mergesort.c | 2 + src/mnl.c | 81 +++++++++++-- src/rule.c | 4 +- 10 files changed, 345 insertions(+), 135 deletions(-)
Signature · 1 line
2.30.2
Pablo Neira Ayuso
maintainerPATCH 1/6 intervals: add helper function to set previous element
Add helper function to set previous element during the automerge iteration. No functional changes are intended.
--- 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 2/6 intervals: do not merge intervals with different timeout
In reply to Pablo Neira AyusoIf timeout/expiration of contiguous intervals is different, then do not merge them.
--- src/intervals.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-)
src/intervals.c +3 -1
@@ -175,7 +175,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 3/6 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.
--- include/expression.h | 13 +++++++ src/expression.c | 85 +++++++++++++++++++++++++++++++++++++++++ src/intervals.c | 90 +++++++++++++++++++++++--------------------- src/mergesort.c | 2 + 4 files changed, 147 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 +85 -0
109 lines not on this page · raw message
src/intervals.c +47 -43
201 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 4/6 rule: constify set_is_non_concat_range()
In reply to Pablo Neira AyusoThis is read-only, constify it.
--- 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 5/6 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.
--- 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 6/6 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.
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. The set size used to be monotonically incremented from set_to_intervals() during the expansion from range to singleton elements. After this patch, mnl_nft_set_add() calculates the set size based on the expansion to individual elements.
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.
--- include/intervals.h | 2 + include/list.h | 8 ++ include/mnl.h | 3 +- src/intervals.c | 180 ++++++++++++++++++++++++++------------------ src/mnl.c | 73 ++++++++++++++++-- src/rule.c | 4 +- 6 files changed, 185 insertions(+), 85 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 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 +106 -74
203 lines not on this page · raw message
src/mnl.c +65 -8
131 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