[PATCH nf 1/2] netfilter: nft_set_rbtree: move sync GC from insert path to set->ops->commit

[PATCH nf 1/2] netfilter: nft_set_rbtree: move sync GC from insert path to set->ops->commit

[Pablo Neira Ayuso]

According to 2ee52ae94baa ("netfilter: nft_set_rbtree: skip sync GC for
new elements in this transaction"), new elements in this transaction
might expire before such transaction ends. Skip sync GC is needed for
such elements otherwise commit path might walk over an already released
object.

However, Florian found that while iterating the tree from the insert
path for sync GC, it is possible that stale references could still
happen for elements in the less-equal and great-than boundaries to
narrow down the tree descend to speed up overlap detection, this
triggers bogus overlap errors.

This patch skips expired elements in the overlap detection routine which
iterates on the reversed ordered list of elements that represent the
intervals. Since end elements provide no expiration extension, check for
the next non-end element in this interval, hence, skip both elements in
the iteration if the interval has expired.

Moreover, move GC sync to the set->ops->commit interface to collect
expired interval. The GC run needs to ignore the gc_interval because the
tree cannot store duplicated expired elements, otherwise bogus
mismatches might occur.

Fixes: f6c383b8c31a ("netfilter: nf_tables: adapt set backend to use GC transaction API")
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
Hi Florian,

I picked up on issue, this proposed as an alternative to:
https://patchwork.ozlabs.org/project/netfilter-devel/patch/20230928131247.3391-1-fw@strlen.de/

Note this ignores the specified gc_interval. For this to work, a copy of the
tree would need to be maintained, similar to what pipapo does.

This approach should clear the path to support for set element timeout
update/refresh.

I still spinning over this one and running test to see if I see any failure
with sets/0044_interval_overlap_{0,1}.

 net/netfilter/nft_set_rbtree.c | 57 +++++++++++++++++++++++++---------
 1 file changed, 43 insertions(+), 14 deletions(-)

diff --git a/net/netfilter/nft_set_rbtree.c b/net/netfilter/nft_set_rbtree.c
index 487572dcd614..de6d812fc790 100644
--- a/net/netfilter/nft_set_rbtree.c
+++ b/net/netfilter/nft_set_rbtree.c
@@ -235,8 +235,7 @@ static void nft_rbtree_gc_remove(struct net *net, struct nft_set *set,
 
 static int nft_rbtree_gc_elem(const struct nft_set *__set,
 			      struct nft_rbtree *priv,
-			      struct nft_rbtree_elem *rbe,
-			      u8 genmask)
+			      struct nft_rbtree_elem *rbe)
 {
 	struct nft_set *set = (struct nft_set *)__set;
 	struct rb_node *prev = rb_prev(&rbe->node);
@@ -254,8 +253,7 @@ static int nft_rbtree_gc_elem(const struct nft_set *__set,
 	 */
 	while (prev) {
 		rbe_prev = rb_entry(prev, struct nft_rbtree_elem, node);
-		if (nft_rbtree_interval_end(rbe_prev) &&
-		    nft_set_elem_active(&rbe_prev->ext, genmask))
+		if (nft_rbtree_interval_end(rbe_prev))
 			break;
 
 		prev = rb_prev(prev);
@@ -289,6 +287,34 @@ static int nft_rbtree_gc_elem(const struct nft_set *__set,
 	return 0;
 }
 
+static void nft_rbtree_commit(const struct nft_set *set)
+{
+	struct nft_rbtree *priv = nft_set_priv(set);
+	struct rb_node *node, *next, *first;
+	struct nft_rbtree_elem *rbe;
+
+	if (!(set->flags & NFT_SET_TIMEOUT))
+		return;
+
+	/* ignore GC interval here, unless two copies of the tree are
+	 * maintained, it is not possible to postpone removal of expired
+	 * elements.
+	 */
+
+	first = rb_first(&priv->root);
+
+	for (node = first; node != NULL; node = next) {
+		next = rb_next(node);
+
+		rbe = rb_entry(node, struct nft_rbtree_elem, node);
+
+		if (!nft_set_elem_expired(&rbe->ext))
+			continue;
+
+		nft_rbtree_gc_elem(set, priv, rbe);
+	}
+}
+
 static bool nft_rbtree_update_first(const struct nft_set *set,
 				    struct nft_rbtree_elem *rbe,
 				    struct rb_node *first)
@@ -312,9 +338,8 @@ static int __nft_rbtree_insert(const struct net *net, const struct nft_set *set,
 	struct nft_rbtree_elem *rbe, *rbe_le = NULL, *rbe_ge = NULL;
 	struct rb_node *node, *next, *parent, **p, *first = NULL;
 	struct nft_rbtree *priv = nft_set_priv(set);
-	u8 cur_genmask = nft_genmask_cur(net);
 	u8 genmask = nft_genmask_next(net);
-	int d, err;
+	int d;
 
 	/* Descend the tree to search for an existing element greater than the
 	 * key value to insert that is greater than the new element. This is the
@@ -358,16 +383,19 @@ static int __nft_rbtree_insert(const struct net *net, const struct nft_set *set,
 		if (!nft_set_elem_active(&rbe->ext, genmask))
 			continue;
 
-		/* perform garbage collection to avoid bogus overlap reports
-		 * but skip new elements in this transaction.
+		/* skip expired intervals to avoid bogus overlap reports:
+		 * end element has no expiration, check next start element.
 		 */
-		if (nft_set_elem_expired(&rbe->ext) &&
-		    nft_set_elem_active(&rbe->ext, cur_genmask)) {
-			err = nft_rbtree_gc_elem(set, priv, rbe, genmask);
-			if (err < 0)
-				return err;
+		if (nft_rbtree_interval_end(rbe) && next) {
+			struct nft_rbtree_elem *rbe_next;
 
-			continue;
+			rbe_next = rb_entry(next, struct nft_rbtree_elem, node);
+
+			if (nft_set_elem_expired(&rbe_next->ext)) {
+				/* skip expired next start element. */
+				next = rb_next(next);
+				continue;
+			}
 		}
 
 		d = nft_rbtree_cmp(set, rbe, new);
@@ -755,5 +783,6 @@ const struct nft_set_type nft_set_rbtree_type = {
 		.lookup		= nft_rbtree_lookup,
 		.walk		= nft_rbtree_walk,
 		.get		= nft_rbtree_get,
+		.commit		= nft_rbtree_commit,
 	},
 };
-- 
2.30.2

[PATCH nf 2/2] netfilter: nft_set_rbtree: remove async GC

[Pablo Neira Ayuso]

Let sync GC remove entries from the tree instead. The sync GC read
spinlock might still stall an update from the control plane with a
sufficiently large tree.

Fixes: 96b33300fba8 ("netfilter: nft_set_rbtree: use read spinlock to avoid datapath contention")
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
Hi Florian,

You asked for this.

 net/netfilter/nft_set_rbtree.c | 90 ----------------------------------
 1 file changed, 90 deletions(-)

diff --git a/net/netfilter/nft_set_rbtree.c b/net/netfilter/nft_set_rbtree.c
index de6d812fc790..17500f4f6f1d 100644
--- a/net/netfilter/nft_set_rbtree.c
+++ b/net/netfilter/nft_set_rbtree.c
@@ -19,7 +19,6 @@ struct nft_rbtree {
 	struct rb_root		root;
 	rwlock_t		lock;
 	seqcount_rwlock_t	count;
-	struct delayed_work	gc_work;
 };
 
 struct nft_rbtree_elem {
@@ -626,89 +625,6 @@ static void nft_rbtree_walk(const struct nft_ctx *ctx,
 	read_unlock_bh(&priv->lock);
 }
 
-static void nft_rbtree_gc(struct work_struct *work)
-{
-	struct nft_rbtree_elem *rbe, *rbe_end = NULL;
-	struct nftables_pernet *nft_net;
-	struct nft_rbtree *priv;
-	struct nft_trans_gc *gc;
-	struct rb_node *node;
-	struct nft_set *set;
-	unsigned int gc_seq;
-	struct net *net;
-
-	priv = container_of(work, struct nft_rbtree, gc_work.work);
-	set  = nft_set_container_of(priv);
-	net  = read_pnet(&set->net);
-	nft_net = nft_pernet(net);
-	gc_seq  = READ_ONCE(nft_net->gc_seq);
-
-	if (nft_set_gc_is_pending(set))
-		goto done;
-
-	gc = nft_trans_gc_alloc(set, gc_seq, GFP_KERNEL);
-	if (!gc)
-		goto done;
-
-	read_lock_bh(&priv->lock);
-	for (node = rb_first(&priv->root); node != NULL; node = rb_next(node)) {
-
-		/* Ruleset has been updated, try later. */
-		if (READ_ONCE(nft_net->gc_seq) != gc_seq) {
-			nft_trans_gc_destroy(gc);
-			gc = NULL;
-			goto try_later;
-		}
-
-		rbe = rb_entry(node, struct nft_rbtree_elem, node);
-
-		if (nft_set_elem_is_dead(&rbe->ext))
-			goto dead_elem;
-
-		/* elements are reversed in the rbtree for historical reasons,
-		 * from highest to lowest value, that is why end element is
-		 * always visited before the start element.
-		 */
-		if (nft_rbtree_interval_end(rbe)) {
-			rbe_end = rbe;
-			continue;
-		}
-		if (!nft_set_elem_expired(&rbe->ext))
-			continue;
-
-		nft_set_elem_dead(&rbe->ext);
-
-		if (!rbe_end)
-			continue;
-
-		nft_set_elem_dead(&rbe_end->ext);
-
-		gc = nft_trans_gc_queue_async(gc, gc_seq, GFP_ATOMIC);
-		if (!gc)
-			goto try_later;
-
-		nft_trans_gc_elem_add(gc, rbe_end);
-		rbe_end = NULL;
-dead_elem:
-		gc = nft_trans_gc_queue_async(gc, gc_seq, GFP_ATOMIC);
-		if (!gc)
-			goto try_later;
-
-		nft_trans_gc_elem_add(gc, rbe);
-	}
-
-	gc = nft_trans_gc_catchall_async(gc, gc_seq);
-
-try_later:
-	read_unlock_bh(&priv->lock);
-
-	if (gc)
-		nft_trans_gc_queue_async_done(gc);
-done:
-	queue_delayed_work(system_power_efficient_wq, &priv->gc_work,
-			   nft_set_gc_interval(set));
-}
-
 static u64 nft_rbtree_privsize(const struct nlattr * const nla[],
 			       const struct nft_set_desc *desc)
 {
@@ -725,11 +641,6 @@ static int nft_rbtree_init(const struct nft_set *set,
 	seqcount_rwlock_init(&priv->count, &priv->lock);
 	priv->root = RB_ROOT;
 
-	INIT_DEFERRABLE_WORK(&priv->gc_work, nft_rbtree_gc);
-	if (set->flags & NFT_SET_TIMEOUT)
-		queue_delayed_work(system_power_efficient_wq, &priv->gc_work,
-				   nft_set_gc_interval(set));
-
 	return 0;
 }
 
@@ -740,7 +651,6 @@ static void nft_rbtree_destroy(const struct nft_ctx *ctx,
 	struct nft_rbtree_elem *rbe;
 	struct rb_node *node;
 
-	cancel_delayed_work_sync(&priv->gc_work);
 	rcu_barrier();
 	while ((node = priv->root.rb_node) != NULL) {
 		rb_erase(node, &priv->root);
-- 
2.30.2

Re: [PATCH nf 1/2] netfilter: nft_set_rbtree: move sync GC from insert path to set->ops->commit

[Pablo Neira Ayuso]

Hi,

On Fri, Sep 29, 2023 at 06:44:03PM +0200, Pablo Neira Ayuso wrote:
> According to 2ee52ae94baa ("netfilter: nft_set_rbtree: skip sync GC for
> new elements in this transaction"), new elements in this transaction
> might expire before such transaction ends. Skip sync GC is needed for
> such elements otherwise commit path might walk over an already released
> object.
> 
> However, Florian found that while iterating the tree from the insert
> path for sync GC, it is possible that stale references could still
> happen for elements in the less-equal and great-than boundaries to
> narrow down the tree descend to speed up overlap detection, this
> triggers bogus overlap errors.
> 
> This patch skips expired elements in the overlap detection routine which
> iterates on the reversed ordered list of elements that represent the
> intervals. Since end elements provide no expiration extension, check for
> the next non-end element in this interval, hence, skip both elements in
> the iteration if the interval has expired.
> 
> Moreover, move GC sync to the set->ops->commit interface to collect
> expired interval. The GC run needs to ignore the gc_interval because the
> tree cannot store duplicated expired elements, otherwise bogus
> mismatches might occur.

I should have tagged this as RFC, this is partially cooked:

- read spin lock is required for the sync GC to make sure this does
  not zap entries that are being used from the datapath.

- the full GC batch could be used to amortize the memory allocation
  (not only two slots as it happens now, I am recycling an existing
   function).

- ENOMEM on GC sync commit path could be an issue. It is too late to
  fail. The tree would start collecting expired elements that might
  duplicate existing, triggering bogus mismatches. In this path the
  commit_mutex is held, and this set backend does not support for
  lockless read, so it might be possible to simply grab the spinlock
  in write mode and release entries inmediately, without requiring the
  sync GC batch infrastructure that pipapo is using.

> Fixes: f6c383b8c31a ("netfilter: nf_tables: adapt set backend to use GC transaction API")
> Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
> ---
> Hi Florian,
> 
> I picked up on issue, this proposed as an alternative to:
> https://patchwork.ozlabs.org/project/netfilter-devel/patch/20230928131247.3391-1-fw@strlen.de/
> 
> Note this ignores the specified gc_interval. For this to work, a copy of the
> tree would need to be maintained, similar to what pipapo does.
> 
> This approach should clear the path to support for set element timeout
> update/refresh.
> 
> I still spinning over this one and running test to see if I see any failure
> with sets/0044_interval_overlap_{0,1}.
> 
>  net/netfilter/nft_set_rbtree.c | 57 +++++++++++++++++++++++++---------
>  1 file changed, 43 insertions(+), 14 deletions(-)
> 
> diff --git a/net/netfilter/nft_set_rbtree.c b/net/netfilter/nft_set_rbtree.c
> index 487572dcd614..de6d812fc790 100644
> --- a/net/netfilter/nft_set_rbtree.c
> +++ b/net/netfilter/nft_set_rbtree.c
> @@ -235,8 +235,7 @@ static void nft_rbtree_gc_remove(struct net *net, struct nft_set *set,
>  
>  static int nft_rbtree_gc_elem(const struct nft_set *__set,
>  			      struct nft_rbtree *priv,
> -			      struct nft_rbtree_elem *rbe,
> -			      u8 genmask)
> +			      struct nft_rbtree_elem *rbe)
>  {
>  	struct nft_set *set = (struct nft_set *)__set;
>  	struct rb_node *prev = rb_prev(&rbe->node);
> @@ -254,8 +253,7 @@ static int nft_rbtree_gc_elem(const struct nft_set *__set,
>  	 */
>  	while (prev) {
>  		rbe_prev = rb_entry(prev, struct nft_rbtree_elem, node);
> -		if (nft_rbtree_interval_end(rbe_prev) &&
> -		    nft_set_elem_active(&rbe_prev->ext, genmask))
> +		if (nft_rbtree_interval_end(rbe_prev))
>  			break;
>  
>  		prev = rb_prev(prev);
> @@ -289,6 +287,34 @@ static int nft_rbtree_gc_elem(const struct nft_set *__set,
>  	return 0;
>  }
>  
> +static void nft_rbtree_commit(const struct nft_set *set)
> +{
> +	struct nft_rbtree *priv = nft_set_priv(set);
> +	struct rb_node *node, *next, *first;
> +	struct nft_rbtree_elem *rbe;
> +
> +	if (!(set->flags & NFT_SET_TIMEOUT))
> +		return;
> +
> +	/* ignore GC interval here, unless two copies of the tree are
> +	 * maintained, it is not possible to postpone removal of expired
> +	 * elements.
> +	 */
> +
> +	first = rb_first(&priv->root);
> +
> +	for (node = first; node != NULL; node = next) {
> +		next = rb_next(node);
> +
> +		rbe = rb_entry(node, struct nft_rbtree_elem, node);
> +
> +		if (!nft_set_elem_expired(&rbe->ext))
> +			continue;
> +
> +		nft_rbtree_gc_elem(set, priv, rbe);
> +	}
> +}
> +
>  static bool nft_rbtree_update_first(const struct nft_set *set,
>  				    struct nft_rbtree_elem *rbe,
>  				    struct rb_node *first)
> @@ -312,9 +338,8 @@ static int __nft_rbtree_insert(const struct net *net, const struct nft_set *set,
>  	struct nft_rbtree_elem *rbe, *rbe_le = NULL, *rbe_ge = NULL;
>  	struct rb_node *node, *next, *parent, **p, *first = NULL;
>  	struct nft_rbtree *priv = nft_set_priv(set);
> -	u8 cur_genmask = nft_genmask_cur(net);
>  	u8 genmask = nft_genmask_next(net);
> -	int d, err;
> +	int d;
>  
>  	/* Descend the tree to search for an existing element greater than the
>  	 * key value to insert that is greater than the new element. This is the
> @@ -358,16 +383,19 @@ static int __nft_rbtree_insert(const struct net *net, const struct nft_set *set,
>  		if (!nft_set_elem_active(&rbe->ext, genmask))
>  			continue;
>  
> -		/* perform garbage collection to avoid bogus overlap reports
> -		 * but skip new elements in this transaction.
> +		/* skip expired intervals to avoid bogus overlap reports:
> +		 * end element has no expiration, check next start element.
>  		 */
> -		if (nft_set_elem_expired(&rbe->ext) &&
> -		    nft_set_elem_active(&rbe->ext, cur_genmask)) {
> -			err = nft_rbtree_gc_elem(set, priv, rbe, genmask);
> -			if (err < 0)
> -				return err;
> +		if (nft_rbtree_interval_end(rbe) && next) {
> +			struct nft_rbtree_elem *rbe_next;
>  
> -			continue;
> +			rbe_next = rb_entry(next, struct nft_rbtree_elem, node);
> +
> +			if (nft_set_elem_expired(&rbe_next->ext)) {
> +				/* skip expired next start element. */
> +				next = rb_next(next);
> +				continue;
> +			}
>  		}
>  
>  		d = nft_rbtree_cmp(set, rbe, new);
> @@ -755,5 +783,6 @@ const struct nft_set_type nft_set_rbtree_type = {
>  		.lookup		= nft_rbtree_lookup,
>  		.walk		= nft_rbtree_walk,
>  		.get		= nft_rbtree_get,
> +		.commit		= nft_rbtree_commit,
>  	},
>  };
> -- 
> 2.30.2
> 

Re: [PATCH nf 1/2] netfilter: nft_set_rbtree: move sync GC from insert path to set->ops->commit

[Florian Westphal]

Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> - read spin lock is required for the sync GC to make sure this does
>   not zap entries that are being used from the datapath.

It needs to grab the write spinlock for each rb_erase, plus
the seqcount increase to make sure that parallel lookup doesn't
miss an element in the tree.

> - the full GC batch could be used to amortize the memory allocation
>   (not only two slots as it happens now, I am recycling an existing
>    function).

Yes.

> - ENOMEM on GC sync commit path could be an issue. It is too late to
>   fail. The tree would start collecting expired elements that might
>   duplicate existing, triggering bogus mismatches. In this path the
>   commit_mutex is held, and this set backend does not support for
>   lockless read,

It does.  If lockless doesn't return a match it falls back to readlock.

>   it might be possible to simply grab the spinlock
>   in write mode and release entries inmediately, without requiring the
>   sync GC batch infrastructure that pipapo is using.

Is there evidence that the on-demand GC is a problem?
It only searches in the relevant subtree, it should rarely, if ever,
encounter any expired element.

Re: [PATCH nf 1/2] netfilter: nft_set_rbtree: move sync GC from insert path to set->ops->commit

[Pablo Neira Ayuso]

Hi Florian,

On Sat, Sep 30, 2023 at 10:10:38AM +0200, Florian Westphal wrote:
> Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> > - read spin lock is required for the sync GC to make sure this does
> >   not zap entries that are being used from the datapath.
> 
> It needs to grab the write spinlock for each rb_erase, plus
> the seqcount increase to make sure that parallel lookup doesn't
> miss an element in the tree.

Right, read lock is not enough for sync GC, and it would be also
required by this approach.

> > - the full GC batch could be used to amortize the memory allocation
> >   (not only two slots as it happens now, I am recycling an existing
> >    function).
> 
> Yes.
> 
> > - ENOMEM on GC sync commit path could be an issue. It is too late to
> >   fail. The tree would start collecting expired elements that might
> >   duplicate existing, triggering bogus mismatches. In this path the
> >   commit_mutex is held, and this set backend does not support for
> >   lockless read,
> 
> It does.  If lockless doesn't return a match it falls back to readlock.

And it will in case of the update to remove the expired element, right?

> >   it might be possible to simply grab the spinlock
> >   in write mode and release entries inmediately, without requiring the
> >   sync GC batch infrastructure that pipapo is using.
> 
> Is there evidence that the on-demand GC is a problem?

After your last fix, not really, other than we have to be care not to
zap elements that are in any of the pending transaction in this batch.

> It only searches in the relevant subtree, it should rarely, if ever,
> encounter any expired element.

Not a problem now, but this path that we follow blocks a requested
feature.

I currently do not know how to support for set element timeout update
with this on-demand GC on the rbtree. This feature will require a new
update state in the transaction to update the timer for an element. We
will have to be careful because on-demand GC might zap an expired
element that got just refreshed in this transaction (unless we
reintroduce some sort of 'busy' bit for updates again which is
something I prefer we do not). With 2ee52ae94baa ("netfilter:
nft_set_rbtree: skip sync GC for new elements in this transaction")
I could fix by looking at the generation mask to infer that this
element is 'busy' by some pending transaction, but I do not see a way
with an element update command in place.

Maybe take your patch and then follow up to nf-next with this approach
based once set element timer update is introduced? Otherwise, rbtree
will block the introduction of this new feature for other sets too.

Re: [PATCH nf 1/2] netfilter: nft_set_rbtree: move sync GC from insert path to set->ops->commit

[Florian Westphal]

Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> On Sat, Sep 30, 2023 at 10:10:38AM +0200, Florian Westphal wrote:
> > It does.  If lockless doesn't return a match it falls back to readlock.
> 
> And it will in case of the update to remove the expired element, right?

Yes, but I don't think its a huge problem, this is short and we do not
grab wrlock until we actually unlink.

> > >   it might be possible to simply grab the spinlock
> > >   in write mode and release entries inmediately, without requiring the
> > >   sync GC batch infrastructure that pipapo is using.
> > 
> > Is there evidence that the on-demand GC is a problem?
> 
> After your last fix, not really, other than we have to be care not to
> zap elements that are in any of the pending transaction in this batch.

Right.  I don't see a problem with zapping those (newly added ones)
from the point-of-no-return phase, however, we don't have to worry about
rollback then.

> > It only searches in the relevant subtree, it should rarely, if ever,
> > encounter any expired element.
> 
> Not a problem now, but this path that we follow blocks a requested
> feature.
>
> I currently do not know how to support for set element timeout update
> with this on-demand GC on the rbtree. This feature will require a new
> update state in the transaction to update the timer for an element. We
> will have to be careful because on-demand GC might zap an expired
> element that got just refreshed in this transaction (unless we
> reintroduce some sort of 'busy' bit for updates again which is
> something I prefer we do not). With 2ee52ae94baa ("netfilter:
> nft_set_rbtree: skip sync GC for new elements in this transaction")
> I could fix by looking at the generation mask to infer that this
> element is 'busy' by some pending transaction, but I do not see a way
> with an element update command in place.

Not convinced. In particular, I don't understand what this has to do
with async vs. sync gc.  To me this depends how we want to handle
elements that have expired or expire during transaction.

Example:

Element E1, times out in 1 hour
Element E2, times out in 1 second
Element E3, timed out (1 second ago, 3 minutes ago, doesn't matter).

Userspace batch to kernel:
Update Element E1 to time out in 2 hours.
Update Element E2 to time out in 1 hour.
Update Element E3 to time out in 1 hour.

What is the expected outcome of this request?

Ignore E3 being reaped already and refresh the timeout (resurrection?)
Ignore E3 being reaped already and ignore the request?
Fail the transaction as E3 timed out already ("does not exist")?

Now, what about E2?  If transaction is large, it could become
like E3 *during the transaction* unless we introduce some freezing
mechanism.  Whats the expected outcome?

Whats the expected outcome if there is some other, unrelated
failure? I assume we have to roll back all the timeout updates, right?
If so, why not temporarily make the timeouts effective right away
and then roll back?

What if userspace asks to *shrink* timeouts? Same scenario:

Update Element E1 to time out in 1 second
Update Element E2 to time out in 1 second
Update Element E3 to time out in 1 second

We could say 'not supported' of course, would avoid the
rollback headache, because in this case long transaction
gc would definitely start to pick some of those elements
up for reaping...

> Maybe take your patch and then follow up to nf-next with this approach
> based once set element timer update is introduced? Otherwise, rbtree
> will block the introduction of this new feature for other sets too.

See above, I would first like to understand the expected
semantics of the timeout update facility.

I've pushed a (not very much tested) version of gc overhaul
to passive lookups based on expiry candidates, this removes
the need for gc sequence counters.

Its vs. nf.git but really should be re-targetted to nf-next, I'll
try to do this next week:

https://git.kernel.org/pub/scm/linux/kernel/git/fwestphal/nf.git/log/?h=nft_set_gc_query_08

Re: [PATCH nf 1/2] netfilter: nft_set_rbtree: move sync GC from insert path to set->ops->commit

[Pablo Neira Ayuso]

Hi Florian,

Looking at your series, I don't think we are that far each other, see
below.

On Sun, Oct 01, 2023 at 11:08:16PM +0200, Florian Westphal wrote:
> I've pushed a (not very much tested) version of gc overhaul
> to passive lookups based on expiry candidates, this removes
> the need for gc sequence counters.

This patch ("netfilter: nft_set_rbtree: prefer sync gc to async
worker")

https://git.kernel.org/pub/scm/linux/kernel/git/fwestphal/nf.git/commit/?h=nft_set_gc_query_08&id=edfeb02d758d6a96a3c1c9a483b69e43e5528e87

goes in the same direction I would like to go with my incomplete patch
I posted. However:

+static void nft_rbtree_commit(struct nft_set *set)
+{
+	struct nft_rbtree *priv = nft_set_priv(set);
+
+	if (time_after_eq(jiffies, priv->last_gc + nft_set_gc_interval(set)))
+		nft_rbtree_gc(set);
+}

I don't think this time_after_eq() to postpone element removal will
work. According to Stefano, you cannot store in the rbtree tree
duplicated elements. Same problem already exists for this set backend
in case a transaction add and delete elements in the same batch.
Unless we maintain two copies. I understand you don't want to maintain
the two copies but then this time_after_eq() needs to go away.

This patch above to add .commit interface to rbtree basically undoes:

https://git.kernel.org/pub/scm/linux/kernel/git/fwestphal/nf.git/commit/?h=nft_set_gc_query_08&id=ee48e86518d62db058efafb6ec1b9f426c441a9d

so better fix it by adding the .commit interface to the rbtree in
first place?

According to what I read it seems we agree on that, the only subtle
difference between your patch and my incomplete patch is this
time_after_eq().

> Its vs. nf.git but really should be re-targetted to nf-next, I'll
> try to do this next week:
> 
> https://git.kernel.org/pub/scm/linux/kernel/git/fwestphal/nf.git/log/?h=nft_set_gc_query_08

Thanks. The gc sequence removal is a different topic we have been
discussing for a while. Would it be possible to incorrect zap an entry
with the transaction semantics? I mean:

#1 transaction to remove element k in set x y
#2 flush set x y (removes dead element k)
#3 add element k to set x y expires 3 minutes
#4 gc transaction freshly added new element

In this case, no dead flag is set on in this new element k on so GC
transaction will skip it.

As for the element timeout update semantics, I will catch up in a
separated email renaming this thread, as this is a new feature and I
prefer to re-focus the conversation on your branch, it has been me
that has been mixing up different topics anyway.

Re: [PATCH nf 1/2] netfilter: nft_set_rbtree: move sync GC from insert path to set->ops->commit

[Florian Westphal]

Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> Looking at your series, I don't think we are that far each other, see
> below.

Agree.

> On Sun, Oct 01, 2023 at 11:08:16PM +0200, Florian Westphal wrote:
> > I've pushed a (not very much tested) version of gc overhaul
> > to passive lookups based on expiry candidates, this removes
> > the need for gc sequence counters.
> 
> This patch ("netfilter: nft_set_rbtree: prefer sync gc to async
> worker")
> 
> https://git.kernel.org/pub/scm/linux/kernel/git/fwestphal/nf.git/commit/?h=nft_set_gc_query_08&id=edfeb02d758d6a96a3c1c9a483b69e43e5528e87
> 
> goes in the same direction I would like to go with my incomplete patch
> I posted. However:
> 
> +static void nft_rbtree_commit(struct nft_set *set)
> +{
> +	struct nft_rbtree *priv = nft_set_priv(set);
> +
> +	if (time_after_eq(jiffies, priv->last_gc + nft_set_gc_interval(set)))
> +		nft_rbtree_gc(set);
> +}
> 
> I don't think this time_after_eq() to postpone element removal will
> work. According to Stefano, you cannot store in the rbtree tree
> duplicated elements.

Note that in this series the on-demand part is still in place,
there will be no duplicate elements.

> Same problem already exists for this set backend
> in case a transaction add and delete elements in the same batch.
> Unless we maintain two copies. I understand you don't want to maintain
> the two copies but then this time_after_eq() needs to go away.

I can remove it, I don't think a full traversal (without doing
anything) will be too costly.

> According to what I read it seems we agree on that, the only subtle
> difference between your patch and my incomplete patch is this
> time_after_eq().

Yes, your patch gets rid of on-demand gc, I agree that we cannot
postpone full run in that case.

> > Its vs. nf.git but really should be re-targetted to nf-next, I'll
> > try to do this next week:
> > 
> > https://git.kernel.org/pub/scm/linux/kernel/git/fwestphal/nf.git/log/?h=nft_set_gc_query_08
> 
> Thanks. The gc sequence removal is a different topic we have been
> discussing for a while.

Yup.  I wanted to explore how much work this is, and it turns
out it gets a lot less ugly of we don't have to hande rbtree and
its end elements.

> Would it be possible to incorrect zap an entry
> with the transaction semantics? I mean:

Nope, should not happen.

> #1 transaction to remove element k in set x y
> #2 flush set x y (removes dead element k)
> #3 add element k to set x y expires 3 minutes
> #4 gc transaction freshly added new element
>
> In this case, no dead flag is set on in this new element k on so GC
> transaction will skip it.

The GC will do lookup, will find the element, will
see its neither dead nor expired so it will be skipped.

At least thats the idea, entries get zapped only
if they are expired or dead (to handle packet path deletion).

> As for the element timeout update semantics, I will catch up in a
> separated email renaming this thread

Thanks!

Re: [PATCH nf 1/2] netfilter: nft_set_rbtree: move sync GC from insert path to set->ops->commit

[Pablo Neira Ayuso]

On Mon, Oct 02, 2023 at 10:47:46AM +0200, Florian Westphal wrote:
> Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> > Looking at your series, I don't think we are that far each other, see
> > below.
> 
> Agree.
> 
> > On Sun, Oct 01, 2023 at 11:08:16PM +0200, Florian Westphal wrote:
> > > I've pushed a (not very much tested) version of gc overhaul
> > > to passive lookups based on expiry candidates, this removes
> > > the need for gc sequence counters.
> > 
> > This patch ("netfilter: nft_set_rbtree: prefer sync gc to async
> > worker")
> > 
> > https://git.kernel.org/pub/scm/linux/kernel/git/fwestphal/nf.git/commit/?h=nft_set_gc_query_08&id=edfeb02d758d6a96a3c1c9a483b69e43e5528e87
> > 
> > goes in the same direction I would like to go with my incomplete patch
> > I posted. However:
> > 
> > +static void nft_rbtree_commit(struct nft_set *set)
> > +{
> > +	struct nft_rbtree *priv = nft_set_priv(set);
> > +
> > +	if (time_after_eq(jiffies, priv->last_gc + nft_set_gc_interval(set)))
> > +		nft_rbtree_gc(set);
> > +}
> > 
> > I don't think this time_after_eq() to postpone element removal will
> > work. According to Stefano, you cannot store in the rbtree tree
> > duplicated elements.
> 
> Note that in this series the on-demand part is still in place,
> there will be no duplicate elements.

Right.

> > Same problem already exists for this set backend
> > in case a transaction add and delete elements in the same batch.
> > Unless we maintain two copies. I understand you don't want to maintain
> > the two copies but then this time_after_eq() needs to go away.
> 
> I can remove it, I don't think a full traversal (without doing
> anything) will be too costly.

OK, so what is your proposal to move on?

> > According to what I read it seems we agree on that, the only subtle
> > difference between your patch and my incomplete patch is this
> > time_after_eq().
> 
> Yes, your patch gets rid of on-demand gc, I agree that we cannot
> postpone full run in that case.

Yes.

> > > Its vs. nf.git but really should be re-targetted to nf-next, I'll
> > > try to do this next week:
> > > 
> > > https://git.kernel.org/pub/scm/linux/kernel/git/fwestphal/nf.git/log/?h=nft_set_gc_query_08
> > 
> > Thanks. The gc sequence removal is a different topic we have been
> > discussing for a while.
> 
> Yup.  I wanted to explore how much work this is, and it turns
> out it gets a lot less ugly of we don't have to hande rbtree and
> its end elements.

OK.

> > Would it be possible to incorrect zap an entry
> > with the transaction semantics? I mean:
> 
> Nope, should not happen.
> 
> > #1 transaction to remove element k in set x y
> > #2 flush set x y (removes dead element k)
> > #3 add element k to set x y expires 3 minutes
> > #4 gc transaction freshly added new element
> >
> > In this case, no dead flag is set on in this new element k on so GC
> > transaction will skip it.
> 
> The GC will do lookup, will find the element, will
> see its neither dead nor expired so it will be skipped.
>
> At least thats the idea, entries get zapped only
> if they are expired or dead (to handle packet path deletion).

Agreed, it is an extra lookup, but it is safer approach.

Thanks.

update element timeout support [was Re: [PATCH nf 1/2] netfilter: nft_set_rbtree: move sync GC from insert path to set->ops->commit]

[Pablo Neira Ayuso]

On Sun, Oct 01, 2023 at 11:08:16PM +0200, Florian Westphal wrote:
> Not convinced. In particular, I don't understand what this has to do
> with async vs. sync gc.  To me this depends how we want to handle
> elements that have expired or expire during transaction.
> 
> Example:
> 
> Element E1, times out in 1 hour
> Element E2, times out in 1 second
> Element E3, timed out (1 second ago, 3 minutes ago, doesn't matter).
> 
> Userspace batch to kernel:
> Update Element E1 to time out in 2 hours.
> Update Element E2 to time out in 1 hour.
> Update Element E3 to time out in 1 hour.
> 
> What is the expected outcome of this request?
> 
> Ignore E3 being reaped already and refresh the timeout (resurrection?)

No resurrection, the element might have counters, it already expired.

> Ignore E3 being reaped already and ignore the request?
> Fail the transaction as E3 timed out already ("does not exist")?

Add a new E3. If NLM_F_EXCL is specified, then fail with "does not exist"

> Now, what about E2?  If transaction is large, it could become
> like E3 *during the transaction* unless we introduce some freezing
> mechanism.  Whats the expected outcome?
> 
> Whats the expected outcome if there is some other, unrelated
> failure? I assume we have to roll back all the timeout updates, right?

We annotate the new timeout in transaction object, then refresh the
timeout update in the commit phase.

> If so, why not temporarily make the timeouts effective right away
> and then roll back?

You mean, from the preparation phase? Then we need to undo what has
been done, in case of --check / abort path is exercised, this might
just create a bogus element listing.

> What if userspace asks to *shrink* timeouts? Same scenario:
> 
> Update Element E1 to time out in 1 second
> Update Element E2 to time out in 1 second
> Update Element E3 to time out in 1 second
> 
> We could say 'not supported' of course, would avoid the
> rollback headache, because in this case long transaction
> gc would definitely start to pick some of those elements
> up for reaping...

No need for rollback if new timeout is store in the transaction
object, we just set the new timeout from _commit() step in the
NEWSETELEM case, which has to deal with updates. Other objects follow
a similar approach.

Re: update element timeout support [was Re: [PATCH nf 1/2] netfilter: nft_set_rbtree: move sync GC from insert path to set->ops->commit]

[Florian Westphal]

Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> On Sun, Oct 01, 2023 at 11:08:16PM +0200, Florian Westphal wrote:
> > Element E1, times out in 1 hour
> > Element E2, times out in 1 second
> > Element E3, timed out (1 second ago, 3 minutes ago, doesn't matter).
> > 
> > Userspace batch to kernel:
> > Update Element E1 to time out in 2 hours.
> > Update Element E2 to time out in 1 hour.
> > Update Element E3 to time out in 1 hour.
> > 
> > What is the expected outcome of this request?
> > 
> > Ignore E3 being reaped already and refresh the timeout (resurrection?)
> 
> No resurrection, the element might have counters, it already expired.

OK.

> > Ignore E3 being reaped already and ignore the request?
> > Fail the transaction as E3 timed out already ("does not exist")?
> 
> Add a new E3. If NLM_F_EXCL is specified, then fail with "does not exist"

OK.

> > Now, what about E2?  If transaction is large, it could become
> > like E3 *during the transaction* unless we introduce some freezing
> > mechanism.  Whats the expected outcome?
> > 
> > Whats the expected outcome if there is some other, unrelated
> > failure? I assume we have to roll back all the timeout updates, right?
> 
> We annotate the new timeout in transaction object, then refresh the
> timeout update in the commit phase.

OK, so as per "E3-example", you're saying that if E2 expires during
the transaction, then if F_EXCL is given the transaction will fail while
otherwise it will be re-added.

> > If so, why not temporarily make the timeouts effective right away
> > and then roll back?
> 
> You mean, from the preparation phase? Then we need to undo what has
> been done, in case of --check / abort path is exercised, this might
> just create a bogus element listing.

True.  Am I correct that we can't implement the "expand" via
del+add because of stateful objects?

I fear we will need to circle back to rbtree then, I'll followup
there (wrt. on-demand gc).

> No need for rollback if new timeout is store in the transaction
> object, we just set the new timeout from _commit() step in the
> NEWSETELEM case, which has to deal with updates. Other objects follow
> a similar approach.

Got it.

Re: update element timeout support [was Re: [PATCH nf 1/2] netfilter: nft_set_rbtree: move sync GC from insert path to set->ops->commit]

[Florian Westphal]

Florian Westphal <fw@strlen.de> wrote:
> > You mean, from the preparation phase? Then we need to undo what has
> > been done, in case of --check / abort path is exercised, this might
> > just create a bogus element listing.
> 
> True.  Am I correct that we can't implement the "expand" via
> del+add because of stateful objects?
> 
> I fear we will need to circle back to rbtree then, I'll followup
> there (wrt. on-demand gc).

Found another corner case, lets assume rhash set to not mix it
with the rbtree issue.

Element E exists and has not timed out yet

Userspace generates:
Refresh timeout of E to <bignum>
<other unrelated stuff, time passes, E expires>
Add E again.  As existing E has timed out already,
this passes...

How to prevent an outcome where E now exists twice?

Variant:
Refresh timeout of E to <bignum>
Delete E

Care has to be taken to not add UAF here.

ATM deletion (unlink) would take effect before the sets' commit
hooks are called, so we refresh timeout of an unlinked element.

AFAICS there won't be UAF because the element memory won't be
released until after mutex unlock and synchronize_rcu, but its
not nice either.

Re: update element timeout support [was Re: [PATCH nf 1/2] netfilter: nft_set_rbtree: move sync GC from insert path to set->ops->commit]

[Pablo Neira Ayuso]

Hi Florian,

I am collecting here your comments for the model we are defining for
set elements:

https://people.netfilter.org/pablo/setelems-timeout.txt

Let me know if you have more possible scenarios that you think that
might not be address by this model:

- Annotate current time at the beginning of the transaction, use it
  in _expired() check (=> timeout is not a moving target anymore).
- Annotate element timeout update in transaction, update timeout from
  _commit() path not to refresh it.

Thanks.

Re: update element timeout support [was Re: [PATCH nf 1/2] netfilter: nft_set_rbtree: move sync GC from insert path to set->ops->commit]

[Florian Westphal]

Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> Hi Florian,
> 
> I am collecting here your comments for the model we are defining for
> set elements:
> 
> https://people.netfilter.org/pablo/setelems-timeout.txt

LGTM.  I think your proposal to snapshot current time and
remove the "moving target" is key.

> Let me know if you have more possible scenarios that you think that
> might not be address by this model:
> 
> - Annotate current time at the beginning of the transaction, use it
>   in _expired() check (=> timeout is not a moving target anymore).
> - Annotate element timeout update in transaction, update timeout from
>   _commit() path not to refresh it.

Right, I think that will work.
For rbtree, sync gc is kept in place, elements are not zapped,
they get tagged as DEAD, including the end element.

Then from commit, do full scan and remove any and all elements
that are flagged as DEAD or have expired.

Re: update element timeout support [was Re: [PATCH nf 1/2] netfilter: nft_set_rbtree: move sync GC from insert path to set->ops->commit]

[Pablo Neira Ayuso]

On Tue, Oct 03, 2023 at 11:04:10AM +0200, Florian Westphal wrote:
> Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> > Hi Florian,
> > 
> > I am collecting here your comments for the model we are defining for
> > set elements:
> > 
> > https://people.netfilter.org/pablo/setelems-timeout.txt
> 
> LGTM.  I think your proposal to snapshot current time and
> remove the "moving target" is key.

Agreed.

> > Let me know if you have more possible scenarios that you think that
> > might not be address by this model:
> > 
> > - Annotate current time at the beginning of the transaction, use it
> >   in _expired() check (=> timeout is not a moving target anymore).
> > - Annotate element timeout update in transaction, update timeout from
> >   _commit() path not to refresh it.
> 
> Right, I think that will work.
> For rbtree, sync gc is kept in place, elements are not zapped,
> they get tagged as DEAD, including the end element.
> 
> Then from commit, do full scan and remove any and all elements
> that are flagged as DEAD or have expired.

Sounds good.

Would you follow this approach to fix the existing issue with the
rbtree on-demand GC in nf.git?

Re: update element timeout support [was Re: [PATCH nf 1/2] netfilter: nft_set_rbtree: move sync GC from insert path to set->ops->commit]

[Florian Westphal]

Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> > Right, I think that will work.
> > For rbtree, sync gc is kept in place, elements are not zapped,
> > they get tagged as DEAD, including the end element.
> > 
> > Then from commit, do full scan and remove any and all elements
> > that are flagged as DEAD or have expired.
> 
> Sounds good.
> 
> Would you follow this approach to fix the existing issue with the
> rbtree on-demand GC in nf.git?

Actually, I don't see why its needed. With your proposal
to make the "is_expired" check during transaction consistently based on
a fixed tstamp, expiry during transaction becomes impossible.
So we can keep immediate rb_erase around.

I suggest to take my proposal to erase, signal -EAGAIN to caller,
then have caller retry.  Apply this to nf.git as a bug fix.

Then, I can take my patches that are mixed into the gc rework;
split those up, and we take the "no more async rbtree gc" for nf-next.

Do you still spot a problem if we retain the on-insert node erase?

To give some numbers (async gc disabled):

Insert 20k ranges into rbtree (takes ~4minutes).
Wait until all have expired.
Insert a single range: takes 250ms (entire tree has to be purged).

Don't think it will be any faster with dead-bit approach,
we simply move cost to later in the transaction.

The only nf.git "advantage" is that we typically won't have
to zap the entire tree during transaction, but thats due to
async gc and I'd rather remove it.

What do you think?

Re: update element timeout support [was Re: [PATCH nf 1/2] netfilter: nft_set_rbtree: move sync GC from insert path to set->ops->commit]

[Pablo Neira Ayuso]

On Tue, Oct 03, 2023 at 08:24:47PM +0200, Florian Westphal wrote:
> Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> > > Right, I think that will work.
> > > For rbtree, sync gc is kept in place, elements are not zapped,
> > > they get tagged as DEAD, including the end element.
> > > 
> > > Then from commit, do full scan and remove any and all elements
> > > that are flagged as DEAD or have expired.
> > 
> > Sounds good.
> > 
> > Would you follow this approach to fix the existing issue with the
> > rbtree on-demand GC in nf.git?
> 
> Actually, I don't see why its needed. With your proposal
> to make the "is_expired" check during transaction consistently based on
> a fixed tstamp, expiry during transaction becomes impossible.
> So we can keep immediate rb_erase around.

Makes sense.

> I suggest to take my proposal to erase, signal -EAGAIN to caller,
> then have caller retry.  Apply this to nf.git as a bug fix.
> 
> Then, I can take my patches that are mixed into the gc rework;
> split those up, and we take the "no more async rbtree gc" for nf-next.
> 
> Do you still spot a problem if we retain the on-insert node erase?

Apart from this unbound loop, which sooner or later will not hit
EAGAIN, no.

> To give some numbers (async gc disabled):
> 
> Insert 20k ranges into rbtree (takes ~4minutes).
> Wait until all have expired.
> Insert a single range: takes 250ms (entire tree has to be purged).
> 
> Don't think it will be any faster with dead-bit approach,
> we simply move cost to later in the transaction.
>
> The only nf.git "advantage" is that we typically won't have
> to zap the entire tree during transaction, but thats due to
> async gc and I'd rather remove it.
> 
> What do you think?

I am fine with this approach.

What it comes, will be redo in nf-next.

Re: update element timeout support [was Re: [PATCH nf 1/2] netfilter: nft_set_rbtree: move sync GC from insert path to set->ops->commit]

[Pablo Neira Ayuso]

On Mon, Oct 02, 2023 at 03:58:38PM +0200, Florian Westphal wrote:
> Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> > On Sun, Oct 01, 2023 at 11:08:16PM +0200, Florian Westphal wrote:
> > > Element E1, times out in 1 hour
> > > Element E2, times out in 1 second
> > > Element E3, timed out (1 second ago, 3 minutes ago, doesn't matter).
> > > 
> > > Userspace batch to kernel:
> > > Update Element E1 to time out in 2 hours.
> > > Update Element E2 to time out in 1 hour.
> > > Update Element E3 to time out in 1 hour.
> > > 
> > > What is the expected outcome of this request?
> > > 
> > > Ignore E3 being reaped already and refresh the timeout (resurrection?)
> > 
> > No resurrection, the element might have counters, it already expired.
> 
> OK.
> 
> > > Ignore E3 being reaped already and ignore the request?
> > > Fail the transaction as E3 timed out already ("does not exist")?
> > 
> > Add a new E3. If NLM_F_EXCL is specified, then fail with "does not exist"
> 
> OK.

Actually not correct what I said in this case: NLM_F_EXCL means create
in newsetelem() path, then add new E3 always succeeds if there is a
timed out E3, regardless the flag.

No "does not exist" error is possible.

> > > Now, what about E2?  If transaction is large, it could become
> > > like E3 *during the transaction* unless we introduce some freezing
> > > mechanism.  Whats the expected outcome?
> > > 
> > > Whats the expected outcome if there is some other, unrelated
> > > failure? I assume we have to roll back all the timeout updates, right?
> > 
> > We annotate the new timeout in transaction object, then refresh the
> > timeout update in the commit phase.
> 
> OK, so as per "E3-example", you're saying that if E2 expires during
> the transaction, then if F_EXCL is given the transaction will fail while
> otherwise it will be re-added.

Please, revisit if the semantics look correct to you after my
correction on the NLM_F_EXCL flag.

> > > If so, why not temporarily make the timeouts effective right away
> > > and then roll back?
> > 
> > You mean, from the preparation phase? Then we need to undo what has
> > been done, in case of --check / abort path is exercised, this might
> > just create a bogus element listing.
> 
> True.  Am I correct that we can't implement the "expand" via
> del+add because of stateful objects?

I think it is not a good idea to expand a element that has already
expired. There might be another possible corner case:

Refresh element E1 with timeout X -> not expired yet
Element E1 expires
Refresh element E1 with timeout Y -> already expired, ENOENT.

This looks fine to me, this handling is possible because the timeout
is not updated from the preparation phase, only later in the commit
phase.

> I fear we will need to circle back to rbtree then, I'll followup
> there (wrt. on-demand gc).
>
> > No need for rollback if new timeout is store in the transaction
> > object, we just set the new timeout from _commit() step in the
> > NEWSETELEM case, which has to deal with updates. Other objects follow
> > a similar approach.
> 
> Got it.

Re: update element timeout support [was Re: [PATCH nf 1/2] netfilter: nft_set_rbtree: move sync GC from insert path to set->ops->commit]

[Pablo Neira Ayuso]

On Mon, Oct 02, 2023 at 11:10:42PM +0200, Pablo Neira Ayuso wrote:
> I think it is not a good idea to expand a element that has already
> expired. There might be another possible corner case:
> 
> Refresh element E1 with timeout X -> not expired yet
> Element E1 expires
> Refresh element E1 with timeout Y -> already expired, ENOENT.

Oh, I see, you mentioned this problem in another email.

This actually results in a new element to be added, with my proposal,
no ENOENT is ever hit.

I get your point, this needs to be sorted out.

Re: [PATCH nf 1/2] netfilter: nft_set_rbtree: move sync GC from insert path to set->ops->commit

[Florian Westphal]

Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> According to 2ee52ae94baa ("netfilter: nft_set_rbtree: skip sync GC for
> new elements in this transaction"), new elements in this transaction
> might expire before such transaction ends. Skip sync GC is needed for
> such elements otherwise commit path might walk over an already released
> object.
> 
> However, Florian found that while iterating the tree from the insert
> path for sync GC, it is possible that stale references could still
> happen for elements in the less-equal and great-than boundaries to
> narrow down the tree descend to speed up overlap detection, this
> triggers bogus overlap errors.
> 
> This patch skips expired elements in the overlap detection routine which
> iterates on the reversed ordered list of elements that represent the
> intervals. Since end elements provide no expiration extension, check for
> the next non-end element in this interval, hence, skip both elements in
> the iteration if the interval has expired.

10.1.2.3 - 10.1.2.30  (expired!)

transaction wants to add:
10.1.2.2 - 10.1.2.29

AFAICS, this is now mismerged into:

10.1.2.2 - 10.1.2.30, because walking back to
next end element from expired 10.1.2.3 will
find 10.1.2.29 as first preceeding end element, no?

and the "commit" operation comes after genid bump, so we can't
restrict that to "not active in next gen" or similar :-/

Can you use dead-bit instead?

Element has expired -> Mark element and the end-pair as dead,
then reap all expired and dead nodes from commit callback.

Problem is what to do after reset-inerval support is added,
because the newly-marked-dead elements could have a timeout
refresh already pending, and I don't see how this can be handled.

Re: [PATCH nf 1/2] netfilter: nft_set_rbtree: move sync GC from insert path to set->ops->commit

[Pablo Neira Ayuso]

On Mon, Oct 02, 2023 at 04:23:12PM +0200, Florian Westphal wrote:
> Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> > According to 2ee52ae94baa ("netfilter: nft_set_rbtree: skip sync GC for
> > new elements in this transaction"), new elements in this transaction
> > might expire before such transaction ends. Skip sync GC is needed for
> > such elements otherwise commit path might walk over an already released
> > object.
> > 
> > However, Florian found that while iterating the tree from the insert
> > path for sync GC, it is possible that stale references could still
> > happen for elements in the less-equal and great-than boundaries to
> > narrow down the tree descend to speed up overlap detection, this
> > triggers bogus overlap errors.
> > 
> > This patch skips expired elements in the overlap detection routine which
> > iterates on the reversed ordered list of elements that represent the
> > intervals. Since end elements provide no expiration extension, check for
> > the next non-end element in this interval, hence, skip both elements in
> > the iteration if the interval has expired.
> 
> 10.1.2.3 - 10.1.2.30  (expired!)
> 
> transaction wants to add:
> 10.1.2.2 - 10.1.2.29
> 
> AFAICS, this is now mismerged into:
> 
> 10.1.2.2 - 10.1.2.30, because walking back to
> next end element from expired 10.1.2.3 will
> find 10.1.2.29 as first preceeding end element, no?
> 
> and the "commit" operation comes after genid bump, so we can't
> restrict that to "not active in next gen" or similar :-/
> 
> Can you use dead-bit instead?
> 
> Element has expired -> Mark element and the end-pair as dead,
> then reap all expired and dead nodes from commit callback.

This makes sense.

> Problem is what to do after reset-inerval support is added,
> because the newly-marked-dead elements could have a timeout
> refresh already pending, and I don't see how this can be handled.

Yes, refresh set element timeout semantics depends on what the timeout
says in the preparation phase. The same problem that is being
discussed in the other two emails in different thread.

We could annotate the current time at the beginning of the
transaction and use it to check if the element has expired, so set
element expiration stops being a moving target.

Re: [PATCH nf 1/2] netfilter: nft_set_rbtree: move sync GC from insert path to set->ops->commit

[Pablo Neira Ayuso]

On Mon, Oct 02, 2023 at 04:23:12PM +0200, Florian Westphal wrote:
> Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> > According to 2ee52ae94baa ("netfilter: nft_set_rbtree: skip sync GC for
> > new elements in this transaction"), new elements in this transaction
> > might expire before such transaction ends. Skip sync GC is needed for
> > such elements otherwise commit path might walk over an already released
> > object.
> > 
> > However, Florian found that while iterating the tree from the insert
> > path for sync GC, it is possible that stale references could still
> > happen for elements in the less-equal and great-than boundaries to
> > narrow down the tree descend to speed up overlap detection, this
> > triggers bogus overlap errors.
> > 
> > This patch skips expired elements in the overlap detection routine which
> > iterates on the reversed ordered list of elements that represent the
> > intervals. Since end elements provide no expiration extension, check for
> > the next non-end element in this interval, hence, skip both elements in
> > the iteration if the interval has expired.
> 
> 10.1.2.3 - 10.1.2.30  (expired!)
> 
> transaction wants to add:
> 10.1.2.2 - 10.1.2.29
> 
> AFAICS, this is now mismerged into:
> 
> 10.1.2.2 - 10.1.2.30, because walking back to
> next end element from expired 10.1.2.3 will
> find 10.1.2.29 as first preceeding end element, no?

Yes, this corner case is currently possible.

> and the "commit" operation comes after genid bump, so we can't
> restrict that to "not active in next gen" or similar :-/
> 
> Can you use dead-bit instead?

Yes, on-demand GC remains in place from insert path and it uses the
dead bit.

> Element has expired -> Mark element and the end-pair as dead,
> then reap all expired and dead nodes from commit callback.
>
> Problem is what to do after reset-inerval support is added,
> because the newly-marked-dead elements could have a timeout
> refresh already pending, and I don't see how this can be handled.

You mean:

transaction
set element E is refreshed
set element E expires
set element E is marked as dead by on-demand GC (when walking down for different element E2)
end transaction

This can probably be addressed by using a curren time snapshot at the
beginning of the transaction to check for the expiration, instead of
checking for the current real time which is a moving target.

Let's consolidate this discussion in one single email thread, all
these issues are interrelated :)