Adding set elements

Adding set elements

[Thomas Köller]

What exactly happens if an attempt is made to add another element to a 
set that is already full? I ran into this condition and found that a 
subsequent 'nft list ruleset' would display the set with no contained 
elements at all.

I think that a reasonable way to handle this case would be to apply sume 
LRU strategy to free up a slot, but that is apparently not the case?

Thomas

Re: Adding set elements

[Pablo Neira Ayuso]

Hi,

On Thu, Nov 14, 2024 at 02:53:04PM +0100, Thomas Köller wrote:
> What exactly happens if an attempt is made to add another element to a set
> that is already full? I ran into this condition and found that a subsequent
> 'nft list ruleset' would display the set with no contained elements at all.

I don't see this here.

Would you post a reproducer for a current kernel in -stable?

> I think that a reasonable way to handle this case would be to apply sume LRU
> strategy to free up a slot, but that is apparently not the case?

Could you develop your usecase?

Re: Adding set elements

[Thomas Köller]

Am 15.11.24 um 13:01 schrieb Pablo Neira Ayuso:
> Hi,
> 
> On Thu, Nov 14, 2024 at 02:53:04PM +0100, Thomas Köller wrote:
>> What exactly happens if an attempt is made to add another element to a set
>> that is already full? I ran into this condition and found that a subsequent
>> 'nft list ruleset' would display the set with no contained elements at all.
> 
> I don't see this here.
> 
> Would you post a reproducer for a current kernel in -stable?
> 
>> I think that a reasonable way to handle this case would be to apply sume LRU
>> strategy to free up a slot, but that is apparently not the case?
> 
> Could you develop your usecase?
> 

I wanted to create a blacklist that the ipv4 source addresses of packets 
that matched certain criteria were added to, like so:

add set ip tbl_ipv4 blacklist { type ipv4_addr; flags dynamic,timeout; 
timeout 1h; gc-interval 6h; size 256; }

and later:

add rule ip tbl_ipv4 syn add @blacklist { ip saddr timeout 1h } counter drop

I noticed that set elements were accumulating over time as expected, but 
after some time the set showed up as empty in the output of 'nft list 
ruleset'. However, I cannot state with certainty that it was the 
overflow condition that caused this to happen, that was just a guess.

I since reduced the element timeout to 10m and the gc-interval to 30m, 
and haven't encountered the problem for a while now.

Assuming that the storage allocated to deleted elements is reused if new 
elements are added before the set is garbage-collected, I would reason 
that the choice of gc interval is not critical and it probably makes 
sense to choose a rather large value in relation to element timeout, is 
this correct?

Re: Adding set elements

[Pablo Neira Ayuso]

On Sat, Nov 16, 2024 at 12:17:27PM +0100, Thomas Köller wrote:
> 
> 
> Am 15.11.24 um 13:01 schrieb Pablo Neira Ayuso:
> > Hi,
> > 
> > On Thu, Nov 14, 2024 at 02:53:04PM +0100, Thomas Köller wrote:
> > > What exactly happens if an attempt is made to add another element to a set
> > > that is already full? I ran into this condition and found that a subsequent
> > > 'nft list ruleset' would display the set with no contained elements at all.
> > 
> > I don't see this here.
> > 
> > Would you post a reproducer for a current kernel in -stable?
> > 
> > > I think that a reasonable way to handle this case would be to apply sume LRU
> > > strategy to free up a slot, but that is apparently not the case?
> > 
> > Could you develop your usecase?
> > 
> 
> I wanted to create a blacklist that the ipv4 source addresses of packets
> that matched certain criteria were added to, like so:
> 
> add set ip tbl_ipv4 blacklist { type ipv4_addr; flags dynamic,timeout;
> timeout 1h; gc-interval 6h; size 256; }

Any reason why you picked such a large gc-interval?

> and later:
> 
> add rule ip tbl_ipv4 syn add @blacklist { ip saddr timeout 1h } counter drop
> 
> I noticed that set elements were accumulating over time as expected, but
> after some time the set showed up as empty in the output of 'nft list
> ruleset'. However, I cannot state with certainty that it was the overflow
> condition that caused this to happen, that was just a guess.

What you observe is an empty listing because all elements have expired
but garbage collector did not remove them yet, so the elements are
still there taking a memory slot in the set until gc runs, ie. set is
full with expired elements, therefore, no more elements can be added.

> I since reduced the element timeout to 10m and the gc-interval to 30m, and
> haven't encountered the problem for a while now.
>
> Assuming that the storage allocated to deleted elements is reused if new
> elements are added before the set is garbage-collected, I would reason that
> the choice of gc interval is not critical and it probably makes sense to
> choose a rather large value in relation to element timeout, is this correct?

There is on-demand garbage collection in the rbtree (which stores
intervals) from (add element) control plane path, but not for the hash
type. From packet path, some sort of on-demand garbage collection
needs to be put in place to support your "storage allocated deleted
elements is reused" assumption.

Re: Adding set elements

[Thomas Köller]

Am 20.11.24 um 23:37 schrieb Pablo Neira Ayuso:
> On Sat, Nov 16, 2024 at 12:17:27PM +0100, Thomas Köller wrote:
>>
>>
>> Am 15.11.24 um 13:01 schrieb Pablo Neira Ayuso:
>>> Hi,
>>>
>>> On Thu, Nov 14, 2024 at 02:53:04PM +0100, Thomas Köller wrote:
>>>> What exactly happens if an attempt is made to add another element to a set
>>>> that is already full? I ran into this condition and found that a subsequent
>>>> 'nft list ruleset' would display the set with no contained elements at all.
>>>
>>> I don't see this here.
>>>
>>> Would you post a reproducer for a current kernel in -stable?
>>>
>>>> I think that a reasonable way to handle this case would be to apply sume LRU
>>>> strategy to free up a slot, but that is apparently not the case?
>>>
>>> Could you develop your usecase?
>>>
>>
>> I wanted to create a blacklist that the ipv4 source addresses of packets
>> that matched certain criteria were added to, like so:
>>
>> add set ip tbl_ipv4 blacklist { type ipv4_addr; flags dynamic,timeout;
>> timeout 1h; gc-interval 6h; size 256; }
> 
> Any reason why you picked such a large gc-interval?
> 
>> and later:
>>
>> add rule ip tbl_ipv4 syn add @blacklist { ip saddr timeout 1h } counter drop
>>
>> I noticed that set elements were accumulating over time as expected, but
>> after some time the set showed up as empty in the output of 'nft list
>> ruleset'. However, I cannot state with certainty that it was the overflow
>> condition that caused this to happen, that was just a guess.
> 
> What you observe is an empty listing because all elements have expired
> but garbage collector did not remove them yet, so the elements are
> still there taking a memory slot in the set until gc runs, ie. set is
> full with expired elements, therefore, no more elements can be added.

So there is no re-use of expired elements when adding new ones? That's 
what I expected to be the case, because to me it seemed to be the 
'obvious' way of implementing dynamic sets. And that misconception led 
me to choose a relatively large gc-interval, assuming that its purpose 
was just to free up resources if the set 'shrinks' permanently.

I guess this means that in order to make use of the full capacity of a 
set, garbage collection has to be performed rather frequently, because 
otherwise expired elements will block addition of new ones, correct?

> 
>> I since reduced the element timeout to 10m and the gc-interval to 30m, and
>> haven't encountered the problem for a while now.
>>
>> Assuming that the storage allocated to deleted elements is reused if new
>> elements are added before the set is garbage-collected, I would reason that
>> the choice of gc interval is not critical and it probably makes sense to
>> choose a rather large value in relation to element timeout, is this correct?
> 
> There is on-demand garbage collection in the rbtree (which stores
> intervals) from (add element) control plane path, but not for the hash
> type. From packet path, some sort of on-demand garbage collection
> needs to be put in place to support your "storage allocated deleted
> elements is reused" assumption.
>