nf_tables: basic dynamic support for set intervals
Subsystems (2)
Pablo Neira Ayuso
maintainercover nf_tables: basic dynamic support for set intervals
This patchset resolves the main issues with the dynamic support for range and its existing rb-tree implementation.
-ruleset.file-
table ip test {
set myset {
type ipv4_addr
flags interval
}
chain input {
type filter hook input priority 0; policy accept;
ip daddr @myset counter packets 0 bytes 0
}
}-EOF-
# nft -f ruleset.file
Then, we add range elements:
# nft add element test myset { 127.0.0.0/24 }
# nft add element test myset { 127.0.1.0/24 }
# nft add element test myset { 127.0.2.0/24 }
# nft add element test myset { 127.0.3.0/24 } # nft list set ip test myset
table ip test {
set myset {
type ipv4_addr
flags interval
elements = { 127.0.0.0/24, 127.0.1.0/24, 127.0.2.0/24, 127.0.3.0/24}
}
} # nft delete element test myset { 127.0.2.0/24 }
# nft delete element test myset { 127.0.1.0/24 }
# nft delete element test myset { 127.0.0.0/24 }
# nft delete element test myset { 127.0.3.0/24 } # nft list set ip test myset
table ip test {
set myset {
type ipv4_addr
flags interval
}
}There is more work coming on this front, the bitmap set implementation is on its way too. Will post the userspace patchset for nft soon.
Pablo Neira Ayuso (4):
netfilter: nf_tables: introduce nft_setelem_parse_flags() helper
netfilter: nf_tables: parse element flags from nft_del_setelem()
netfilter: nft_rbtree: introduce nft_rbtree_interval_end() helper
netfilter: nft_rbtree: allow adjacent intervals with dynamic updates
net/netfilter/nf_tables_api.c | 72 +++++++++++++++++++++++++++++++++---------- net/netfilter/nft_rbtree.c | 49 ++++++++++++++++++++++++----- 2 files changed, 96 insertions(+), 25 deletions(-)
Signature · 1 line
2.1.4
Pablo Neira Ayuso
maintainerPATCH 1/4 netfilter: nf_tables: introduce nft_setelem_parse_flags() helper
This function parses the set element flags, thus, we can reuse the same handling when deleting elements.
--- net/netfilter/nf_tables_api.c | 34 ++++++++++++++++++++++------------ 1 file changed, 22 insertions(+), 12 deletions(-)
net/netfilter/nf_tables_api.c +22 -12
@@ -3419,6 +3419,22 @@ void nft_set_elem_destroy(const struct nft_set *set, void *elem) }EXPORT_SYMBOL_GPL (nft_set_elem_destroy); +static int nft_setelem_parse_flags (const struct nft_set *set, +const struct nlattr *attr,u32 *flags) +{ +if (attr ==NULL ) +return 0 ; + + *flags =ntohl (nla_get_be32 (attr)); +if (*flags & ~NFT_SET_ELEM_INTERVAL_END ) +return -EINVAL ; +if (!(set->flags &NFT_SET_INTERVAL ) && + *flags &NFT_SET_ELEM_INTERVAL_END ) +return -EINVAL ; + +return 0 ; +} +static int nft_add_set_elem (struct nft_ctx *ctx,struct nft_set *set,const struct nlattr *attr) {
@@ -3432,8 +3448,8 @@ static int nft_add_set_elem(struct nft_ctx *ctx, struct nft_set *set,struct nft_data data;enum nft_registers dreg;struct nft_trans *trans; +u32 flags =0 ;u64 timeout; -u32 flags;u8 ulen;int err;
@@ -3447,17 +3463,11 @@ static int nft_add_set_elem(struct nft_ctx *ctx, struct nft_set *set,nft_set_ext_prepare (&tmpl); - flags =0 ; -if (nla[NFTA_SET_ELEM_FLAGS ] !=NULL ) { - flags =ntohl (nla_get_be32 (nla[NFTA_SET_ELEM_FLAGS ])); -if (flags & ~NFT_SET_ELEM_INTERVAL_END ) -return -EINVAL ; -if (!(set->flags &NFT_SET_INTERVAL ) && - flags &NFT_SET_ELEM_INTERVAL_END ) -return -EINVAL ; -if (flags !=0 ) -nft_set_ext_add (&tmpl,NFT_SET_EXT_FLAGS ); - } + err =nft_setelem_parse_flags (set, nla[NFTA_SET_ELEM_FLAGS ], &flags); +if (err <0 ) +return err; +if (flags !=0 ) +nft_set_ext_add (&tmpl,NFT_SET_EXT_FLAGS );if (set->flags &NFT_SET_MAP ) { if (nla[NFTA_SET_ELEM_DATA] == NULL &&
Signature · 1 line
2.1.4
Pablo Neira Ayuso
maintainerPATCH 2/4 netfilter: nf_tables: parse element flags from nft_del_setelem()
In reply to Pablo Neira AyusoParse flags and pass them to the set via ->deactivate() to check if we remove the right element from the intervals.
--- net/netfilter/nf_tables_api.c | 38 +++++++++++++++++++++++++++++++++----- 1 file changed, 33 insertions(+), 5 deletions(-)
net/netfilter/nf_tables_api.c +33 -5
@@ -3636,9 +3636,13 @@ static int nft_del_setelem(struct nft_ctx *ctx, struct nft_set *set, const struct nlattr *attr) {struct nlattr *nla[NFTA_SET_ELEM_MAX +1 ]; +struct nft_set_ext_tmpl tmpl;struct nft_data_desc desc;struct nft_set_elem elem; +struct nft_set_ext *ext;struct nft_trans *trans; +u32 flags =0 ; +void *priv;int err; err = nla_parse_nested(nla, NFTA_SET_ELEM_MAX, attr,
@@ -3650,6 +3654,14 @@ static int nft_del_setelem(struct nft_ctx *ctx, struct nft_set *set,if (nla[NFTA_SET_ELEM_KEY ] ==NULL ) goto err1; +nft_set_ext_prepare (&tmpl); + + err =nft_setelem_parse_flags (set, nla[NFTA_SET_ELEM_FLAGS ], &flags); +if (err <0 ) +return err; +if (flags !=0 ) +nft_set_ext_add (&tmpl,NFT_SET_EXT_FLAGS ); + err =nft_data_init (ctx, &elem.key.val,sizeof (elem.key), &desc, nla[NFTA_SET_ELEM_KEY ]);if (err <0 )
@@ -3659,24 +3671,40 @@ static int nft_del_setelem(struct nft_ctx *ctx, struct nft_set *set,if (desc.type !=NFT_DATA_VALUE || desc.len != set->klen) goto err2; +nft_set_ext_add_length (&tmpl,NFT_SET_EXT_KEY , desc.len); + + err = -ENOMEM ; + elem.priv =nft_set_elem_init (set, &tmpl, elem.key.val.data,NULL ,0 , +GFP_KERNEL ); +if (elem.priv ==NULL ) + goto err2; + + ext =nft_set_elem_ext (set, elem.priv); +if (flags) + *nft_set_ext_flags (ext) = flags; + trans =nft_trans_elem_alloc (ctx,NFT_MSG_DELSETELEM , set);if (trans ==NULL ) { err = -ENOMEM ; - goto err2; + goto err3; } - elem.priv = set->ops->deactivate (set, &elem); -if (elem.priv ==NULL ) { + priv = set->ops->deactivate (set, &elem); +if (priv ==NULL ) { err = -ENOENT ; - goto err3; + goto err4; } +kfree (elem.priv); + elem.priv = priv;nft_trans_elem (trans) = elem;list_add_tail (&trans->list, &ctx->net->nft.commit_list);return 0 ; -err3: +err4:kfree (trans); +err3: +kfree (elem.priv); err2:nft_data_uninit (&elem.key.val, desc.type); err1:
Signature · 1 line
2.1.4
Pablo Neira Ayuso
maintainerPATCH 3/4 netfilter: nft_rbtree: introduce nft_rbtree_interval_end() helper
In reply to Pablo Neira AyusoAdd this new nft_rbtree_interval_end() helper function to check in the end interval is set.
--- net/netfilter/nft_rbtree.c | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-)
net/netfilter/nft_rbtree.c +6 -3
@@ -29,6 +29,11 @@ struct nft_rbtree_elem {struct nft_set_ext ext; }; +static bool nft_rbtree_interval_end (const struct nft_rbtree_elem *rbe) +{ +return nft_set_ext_exists (&rbe->ext,NFT_SET_EXT_FLAGS ) && + (*nft_set_ext_flags (&rbe->ext) &NFT_SET_ELEM_INTERVAL_END ); +}static bool nft_rbtree_lookup (const struct nft_set *set,const u32 *key,const struct nft_set_ext **ext)
@@ -56,9 +61,7 @@ found: parent = parent->rb_left;continue ; } -if (nft_set_ext_exists (&rbe->ext,NFT_SET_EXT_FLAGS ) && - *nft_set_ext_flags (&rbe->ext) & -NFT_SET_ELEM_INTERVAL_END ) +if (nft_rbtree_interval_end (rbe)) goto out;spin_unlock_bh (&nft_rbtree_lock);
Signature · 1 line
2.1.4
Pablo Neira Ayuso
maintainerPATCH 4/4 netfilter: nft_rbtree: allow adjacent intervals with dynamic updates
In reply to Pablo Neira AyusoThis patch fixes dynamic element updates for adjacent intervals in the rb-tree representation.
Since elements are sorted in the rb-tree, in case of adjacent nodes with the same key, the assumption is that an interval end node must be placed before an interval opening.
In tree lookup operations, the idea is to search for the closer element that is larger than the one we're searching for. Given that we'll have to matching, we have to take the opening interval in case of adjacent nodes.
Range merges are not trivial with the current representation, specifically we have to check if node extensions are equal and make sure we keep the existing internal states around.
--- net/netfilter/nft_rbtree.c | 40 +++++++++++++++++++++++++++++++++++----- 1 file changed, 35 insertions(+), 5 deletions(-)
net/netfilter/nft_rbtree.c +35 -5
@@ -35,6 +35,12 @@ static bool nft_rbtree_interval_end(const struct nft_rbtree_elem *rbe) (*nft_set_ext_flags (&rbe->ext) &NFT_SET_ELEM_INTERVAL_END ); } +static bool nft_rbtree_equal (const struct nft_set *set,const void *this, +const struct nft_rbtree_elem *interval) +{ +return memcmp (this,nft_set_ext_key (&interval->ext), set->klen) ==0 ; +} +static bool nft_rbtree_lookup (const struct nft_set *set,const u32 *key,const struct nft_set_ext **ext) {
@@ -42,6 +48,7 @@ static bool nft_rbtree_lookup(const struct nft_set *set, const u32 *key,const struct nft_rbtree_elem *rbe, *interval =NULL ;const struct rb_node *parent;u8 genmask =nft_genmask_cur (read_pnet (&set->pnet)); +const void *this;int d;spin_lock_bh (&nft_rbtree_lock);
@@ -49,9 +56,16 @@ static bool nft_rbtree_lookup(const struct nft_set *set, const u32 *key,while (parent !=NULL ) { rbe = rb_entry(parent, struct nft_rbtree_elem, node); - d =memcmp (nft_set_ext_key (&rbe->ext), key, set->klen); + this =nft_set_ext_key (&rbe->ext); + d =memcmp (this, key, set->klen);if (d <0 ) { parent = parent->rb_left; +/* In case of adjacent ranges, we always see the high +* part of the range in first place, before the low one. +* So don't update interval if the keys are equal. +*/ +if (interval &&nft_rbtree_equal (set, this, interval)) +continue ; interval = rbe; }else if (d >0 ) parent = parent->rb_right;
@@ -101,9 +115,16 @@ static int __nft_rbtree_insert(const struct nft_set *set,else if (d >0 ) p = &parent->rb_right;else { -if (nft_set_elem_active (&rbe->ext, genmask)) -return -EEXIST ; - p = &parent->rb_left; +if (nft_set_elem_active (&rbe->ext, genmask)) { +if (nft_rbtree_interval_end (rbe) && + !nft_rbtree_interval_end (new)) + p = &parent->rb_left; +else if (!nft_rbtree_interval_end (rbe) && +nft_rbtree_interval_end (new)) + p = &parent->rb_right; +else +return -EEXIST ; + } } }rb_link_node (&new->node, parent, p);
@@ -148,7 +169,7 @@ static void *nft_rbtree_deactivate(const struct nft_set *set, {const struct nft_rbtree *priv =nft_set_priv (set);const struct rb_node *parent = priv->root.rb_node; -struct nft_rbtree_elem *rbe; +struct nft_rbtree_elem *rbe, *this = elem->priv;u8 genmask =nft_genmask_cur (read_pnet (&set->pnet));int d;
@@ -166,6 +187,15 @@ static void *nft_rbtree_deactivate(const struct nft_set *set, parent = parent->rb_left;continue ; } +if (nft_rbtree_interval_end (rbe) && + !nft_rbtree_interval_end (this)) { + parent = parent->rb_left; +continue ; + }else if (!nft_rbtree_interval_end (rbe) && +nft_rbtree_interval_end (this)) { + parent = parent->rb_right; +continue ; + }nft_set_elem_change_active (set, &rbe->ext);return rbe; }
Signature · 1 line
2.1.4
Pablo Neira Ayuso
maintainerQuoted 2 lines · Pablo Neira Ayuso
This patchset resolves the main issues with the dynamic support for range and its existing rb-tree implementation.
I'm applying this series now.