Is there an efficient way to delete multiple elements from a set?

Is there an efficient way to delete multiple elements from a set?

[Anton]

Hello, I've been experimenting with nftables sets for the purpose of
geoip blocking. Let's say I'd like to add ip blocks for multiple
countries to a blacklist or to a whitelist. Perhaps the most efficient
way to do that would be by combining all required ip blocks in one set
(for each family). However since country ip blocks are a moving
target, I would need to regularly refresh parts of that set. My idea
was to delete all ip addresses corresponding to an ip block from the
set and then add the updated ip block. The problem is, this is very
slow. While adding an ip block takes (in my VM) 0.09s, deleting all
ip's from that same block takes 14.5s.

This is how I'm doing the deletion and the time measurement:
printf '%s\n' "delete element inet test testset { $(cat test.set) };"
| /usr/bin/time -f %es nft -f -

(the test.set file stores a comma-separated list of subnets)

Is there a more efficient way to do this? I could of course flush the
set and rebuild it every time I need to update some part of it, but I
thought I'd ask before deciding to implement that.

Re: Is there an efficient way to delete multiple elements from a set?

[Reindl Harald]

Am 31.01.24 um 09:14 schrieb Anton:
> Hello, I've been experimenting with nftables sets for the purpose of
> geoip blocking. Let's say I'd like to add ip blocks for multiple
> countries to a blacklist or to a whitelist. Perhaps the most efficient
> way to do that would be by combining all required ip blocks in one set
> (for each family). However since country ip blocks are a moving
> target, I would need to regularly refresh parts of that set. My idea
> was to delete all ip addresses corresponding to an ip block from the
> set and then add the updated ip block. The problem is, this is very
> slow. While adding an ip block takes (in my VM) 0.09s, deleting all
> ip's from that same block takes 14.5s.
> 
> This is how I'm doing the deletion and the time measurement:
> printf '%s\n' "delete element inet test testset { $(cat test.set) };"
> | /usr/bin/time -f %es nft -f -
> 
> (the test.set file stores a comma-separated list of subnets)
> 
> Is there a more efficient way to do this? I could of course flush the
> set and rebuild it every time I need to update some part of it, but I
> thought I'd ask before deciding to implement that.

that's what swap is for - you don't mangle around live in a large ipset

/usr/sbin/ipset -exist create IANA_RESERVED_IPV4_TMP hash:net maxelem 
512 family inet
/usr/sbin/ipset flush IANA_RESERVED_IPV4_TMP

/usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 127.0.0.0/8
/usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 10.0.0.0/8
/usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 100.64.0.0/10
/usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 169.254.0.0/16
/usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 172.16.0.0/12
/usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 192.0.0.0/24
/usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 192.0.2.0/24
/usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 192.168.0.0/16
/usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 192.88.99.0/24
/usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 198.18.0.0/15
/usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 198.51.100.0/24
/usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 203.0.113.0/24
/usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 240.0.0.0/4

/usr/sbin/ipset swap IANA_RESERVED_IPV4_TMP IANA_RESERVED_IPV4
/usr/sbin/ipset destroy IANA_RESERVED_IPV4_TMP

Re: Is there an efficient way to delete multiple elements from a set?

[Anton]

Thank you for your input. As I mentioned, I am specifically
considering nftables sets, not 'ipset' sets. nftables sets do not
support swap AFAIK. Now I could use separate sets for each country
regardless and replace them when needed, however this way the firewall
won't be as efficient as with one rule and one set. I may eventually
do it this way if there is no better option.

On Wed, Jan 31, 2024 at 10:21 AM Reindl Harald <h.reindl@thelounge.net> wrote:
>
>
>
> Am 31.01.24 um 09:14 schrieb Anton:
> > Hello, I've been experimenting with nftables sets for the purpose of
> > geoip blocking. Let's say I'd like to add ip blocks for multiple
> > countries to a blacklist or to a whitelist. Perhaps the most efficient
> > way to do that would be by combining all required ip blocks in one set
> > (for each family). However since country ip blocks are a moving
> > target, I would need to regularly refresh parts of that set. My idea
> > was to delete all ip addresses corresponding to an ip block from the
> > set and then add the updated ip block. The problem is, this is very
> > slow. While adding an ip block takes (in my VM) 0.09s, deleting all
> > ip's from that same block takes 14.5s.
> >
> > This is how I'm doing the deletion and the time measurement:
> > printf '%s\n' "delete element inet test testset { $(cat test.set) };"
> > | /usr/bin/time -f %es nft -f -
> >
> > (the test.set file stores a comma-separated list of subnets)
> >
> > Is there a more efficient way to do this? I could of course flush the
> > set and rebuild it every time I need to update some part of it, but I
> > thought I'd ask before deciding to implement that.
>
> that's what swap is for - you don't mangle around live in a large ipset
>
> /usr/sbin/ipset -exist create IANA_RESERVED_IPV4_TMP hash:net maxelem
> 512 family inet
> /usr/sbin/ipset flush IANA_RESERVED_IPV4_TMP
>
> /usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 127.0.0.0/8
> /usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 10.0.0.0/8
> /usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 100.64.0.0/10
> /usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 169.254.0.0/16
> /usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 172.16.0.0/12
> /usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 192.0.0.0/24
> /usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 192.0.2.0/24
> /usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 192.168.0.0/16
> /usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 192.88.99.0/24
> /usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 198.18.0.0/15
> /usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 198.51.100.0/24
> /usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 203.0.113.0/24
> /usr/sbin/ipset add IANA_RESERVED_IPV4_TMP 240.0.0.0/4
>
> /usr/sbin/ipset swap IANA_RESERVED_IPV4_TMP IANA_RESERVED_IPV4
> /usr/sbin/ipset destroy IANA_RESERVED_IPV4_TMP

Re: Is there an efficient way to delete multiple elements from a set?

[Kerin Millar]

On Wed, 31 Jan 2024, at 8:14 AM, Anton wrote:
> Hello, I've been experimenting with nftables sets for the purpose of
> geoip blocking. Let's say I'd like to add ip blocks for multiple
> countries to a blacklist or to a whitelist. Perhaps the most efficient
> way to do that would be by combining all required ip blocks in one set
> (for each family). However since country ip blocks are a moving
> target, I would need to regularly refresh parts of that set. My idea
> was to delete all ip addresses corresponding to an ip block from the
> set and then add the updated ip block. The problem is, this is very
> slow. While adding an ip block takes (in my VM) 0.09s, deleting all
> ip's from that same block takes 14.5s.
>
> This is how I'm doing the deletion and the time measurement:
> printf '%s\n' "delete element inet test testset { $(cat test.set) };"
> | /usr/bin/time -f %es nft -f -
>
> (the test.set file stores a comma-separated list of subnets)
>
> Is there a more efficient way to do this? I could of course flush the
> set and rebuild it every time I need to update some part of it, but I
> thought I'd ask before deciding to implement that.

Indeed there is. Your method isn't optimal because the command substitution causes the shell to needlessly assign memory for the sole purpose of containing the entirety of the output of cat(1). Further, cat(1) will have to complete before the printf builtin can even be executed, which defeats the asynchronicity of the pipeline. You should feed nft(8) with a command list instead.

{
	printf 'delete element inet test testset { '
	cat test.set
	printf ' }'
} | nft -f -

If you would prefer to express it as a one-liner then you may, in which case you must also terminate each of the three commands in the { command list } with a semicolon.

-- 
Kerin Millar

Re: Is there an efficient way to delete multiple elements from a set?

[Anton]

While this is better in theory, in practice no performance improvement
is observed. This sort of detail is worth paying attention to in a
loop. In a single operation, the 0.01s saved is insignificant.

On Wed, Jan 31, 2024 at 2:20 PM Kerin Millar <kfm@plushkava.net> wrote:
>
> On Wed, 31 Jan 2024, at 8:14 AM, Anton wrote:
> > Hello, I've been experimenting with nftables sets for the purpose of
> > geoip blocking. Let's say I'd like to add ip blocks for multiple
> > countries to a blacklist or to a whitelist. Perhaps the most efficient
> > way to do that would be by combining all required ip blocks in one set
> > (for each family). However since country ip blocks are a moving
> > target, I would need to regularly refresh parts of that set. My idea
> > was to delete all ip addresses corresponding to an ip block from the
> > set and then add the updated ip block. The problem is, this is very
> > slow. While adding an ip block takes (in my VM) 0.09s, deleting all
> > ip's from that same block takes 14.5s.
> >
> > This is how I'm doing the deletion and the time measurement:
> > printf '%s\n' "delete element inet test testset { $(cat test.set) };"
> > | /usr/bin/time -f %es nft -f -
> >
> > (the test.set file stores a comma-separated list of subnets)
> >
> > Is there a more efficient way to do this? I could of course flush the
> > set and rebuild it every time I need to update some part of it, but I
> > thought I'd ask before deciding to implement that.
>
> Indeed there is. Your method isn't optimal because the command substitution causes the shell to needlessly assign memory for the sole purpose of containing the entirety of the output of cat(1). Further, cat(1) will have to complete before the printf builtin can even be executed, which defeats the asynchronicity of the pipeline. You should feed nft(8) with a command list instead.
>
> {
>         printf 'delete element inet test testset { '
>         cat test.set
>         printf ' }'
> } | nft -f -
>
> If you would prefer to express it as a one-liner then you may, in which case you must also terminate each of the three commands in the { command list } with a semicolon.
>
> --
> Kerin Millar

Re: Is there an efficient way to delete multiple elements from a set?

[Kerin Millar]

On Thu, 1 Feb 2024 00:13:37 +0200
Anton <anton.khazan@gmail.com> wrote:

> While this is better in theory, in practice no performance improvement
> is observed. This sort of detail is worth paying attention to in a
> loop. In a single operation, the 0.01s saved is insignificant.

It's not true that it is only worth paying attention to in a loop but I won't argue about it here. Suffice to say that it depends, in part, upon the ability of the program reading from the pipe to perform useful work while reading. There are plenty of programs that can. It seems that nft is not such a program, which I suppose makes sense.

Anyway, if the performance of nft seems unusually bad for deletions, it could be bug material.

-- 
Kerin Millar

Re: Is there an efficient way to delete multiple elements from a set?

[Anton]

I don't know whether this is actually a bug, or is it by design.
Perhaps a netfilter dev could comment on that.

On Thu, Feb 1, 2024 at 12:39 AM Kerin Millar <kfm@plushkava.net> wrote:
> Anyway, if the performance of nft seems unusually bad for deletions, it could be bug material.

Re: Is there an efficient way to delete multiple elements from a set?

[Pablo Neira Ayuso]

On Wed, Jan 31, 2024 at 10:14:41AM +0200, Anton wrote:
> Hello, I've been experimenting with nftables sets for the purpose of
> geoip blocking. Let's say I'd like to add ip blocks for multiple
> countries to a blacklist or to a whitelist. Perhaps the most efficient
> way to do that would be by combining all required ip blocks in one set
> (for each family). However since country ip blocks are a moving
> target, I would need to regularly refresh parts of that set. My idea
> was to delete all ip addresses corresponding to an ip block from the
> set and then add the updated ip block. The problem is, this is very
> slow. While adding an ip block takes (in my VM) 0.09s, deleting all
> ip's from that same block takes 14.5s.
> 
> This is how I'm doing the deletion and the time measurement:
> printf '%s\n' "delete element inet test testset { $(cat test.set) };"
> | /usr/bin/time -f %es nft -f -
> 
> (the test.set file stores a comma-separated list of subnets)
> 
> Is there a more efficient way to do this? I could of course flush the
> set and rebuild it every time I need to update some part of it, but I
> thought I'd ask before deciding to implement that.

It is possible to flush the set and fill up with content again:

flush set inet test testset
add element inet test testset { ...  }

Re: Is there an efficient way to delete multiple elements from a set?

[Pablo Neira Ayuso]

On Thu, Feb 01, 2024 at 10:41:21AM +0100, Pablo Neira Ayuso wrote:
> On Wed, Jan 31, 2024 at 10:14:41AM +0200, Anton wrote:
> > Hello, I've been experimenting with nftables sets for the purpose of
> > geoip blocking. Let's say I'd like to add ip blocks for multiple
> > countries to a blacklist or to a whitelist. Perhaps the most efficient
> > way to do that would be by combining all required ip blocks in one set
> > (for each family). However since country ip blocks are a moving
> > target, I would need to regularly refresh parts of that set. My idea
> > was to delete all ip addresses corresponding to an ip block from the
> > set and then add the updated ip block. The problem is, this is very
> > slow. While adding an ip block takes (in my VM) 0.09s, deleting all
> > ip's from that same block takes 14.5s.
> > 
> > This is how I'm doing the deletion and the time measurement:
> > printf '%s\n' "delete element inet test testset { $(cat test.set) };"
> > | /usr/bin/time -f %es nft -f -
> > 
> > (the test.set file stores a comma-separated list of subnets)
> > 
> > Is there a more efficient way to do this? I could of course flush the
> > set and rebuild it every time I need to update some part of it, but I
> > thought I'd ask before deciding to implement that.
> 
> It is possible to flush the set and fill up with content again:
> 
> flush set inet test testset
> add element inet test testset { ...  }

I forgot to mention: Run this a batch .nft file, then:

        # nft -f update-set.nft

Re: Is there an efficient way to delete multiple elements from a set?

[Jozsef Kadlecsik]

On Thu, 1 Feb 2024, Pablo Neira Ayuso wrote:

> On Thu, Feb 01, 2024 at 10:41:21AM +0100, Pablo Neira Ayuso wrote:
> > On Wed, Jan 31, 2024 at 10:14:41AM +0200, Anton wrote:
> > > Hello, I've been experimenting with nftables sets for the purpose of
> > > geoip blocking. Let's say I'd like to add ip blocks for multiple
> > > countries to a blacklist or to a whitelist. Perhaps the most efficient
> > > way to do that would be by combining all required ip blocks in one set
> > > (for each family). However since country ip blocks are a moving
> > > target, I would need to regularly refresh parts of that set. My idea
> > > was to delete all ip addresses corresponding to an ip block from the
> > > set and then add the updated ip block. The problem is, this is very
> > > slow. While adding an ip block takes (in my VM) 0.09s, deleting all
> > > ip's from that same block takes 14.5s.
> > > 
> > > This is how I'm doing the deletion and the time measurement:
> > > printf '%s\n' "delete element inet test testset { $(cat test.set) };"
> > > | /usr/bin/time -f %es nft -f -
> > > 
> > > (the test.set file stores a comma-separated list of subnets)
> > > 
> > > Is there a more efficient way to do this? I could of course flush the
> > > set and rebuild it every time I need to update some part of it, but I
> > > thought I'd ask before deciding to implement that.
> > 
> > It is possible to flush the set and fill up with content again:
> > 
> > flush set inet test testset
> > add element inet test testset { ...  }
> 
> I forgot to mention: Run this a batch .nft file, then:
> 
>         # nft -f update-set.nft

I'd like to add that the nft command above is atomic and either it 
succeeds and the set content is replaced with the new elements or it fails 
and the original set is kept intact. (It is important that the "flush" and 
"add" subcommands be executed by a single nft command invocation as in the 
example above.)

So it's roughly equivalent with

	ipset create temp-set ...
	ipset add temp-set ...
	ipset swap production-set temp-set
	ipset destroy temp-set

Best regards,
Jozsef
-- 
E-mail  : kadlec@blackhole.kfki.hu, kadlecsik.jozsef@wigner.hu
PGP key : https://wigner.hu/~kadlec/pgp_public_key.txt
Address : Wigner Research Centre for Physics
          H-1525 Budapest 114, POB. 49, Hungary

Re: Is there an efficient way to delete multiple elements from a set?

[Kerin Millar]

Hi Pablo,

On Thu, 1 Feb 2024, at 9:41 AM, Pablo Neira Ayuso wrote:
> On Wed, Jan 31, 2024 at 10:14:41AM +0200, Anton wrote:
>> Hello, I've been experimenting with nftables sets for the purpose of
>> geoip blocking. Let's say I'd like to add ip blocks for multiple
>> countries to a blacklist or to a whitelist. Perhaps the most efficient
>> way to do that would be by combining all required ip blocks in one set
>> (for each family). However since country ip blocks are a moving
>> target, I would need to regularly refresh parts of that set. My idea
>> was to delete all ip addresses corresponding to an ip block from the
>> set and then add the updated ip block. The problem is, this is very
>> slow. While adding an ip block takes (in my VM) 0.09s, deleting all
>> ip's from that same block takes 14.5s.
>> 
>> This is how I'm doing the deletion and the time measurement:
>> printf '%s\n' "delete element inet test testset { $(cat test.set) };"
>> | /usr/bin/time -f %es nft -f -
>> 
>> (the test.set file stores a comma-separated list of subnets)
>> 
>> Is there a more efficient way to do this? I could of course flush the
>> set and rebuild it every time I need to update some part of it, but I
>> thought I'd ask before deciding to implement that.
>
> It is possible to flush the set and fill up with content again:
>
> flush set inet test testset
> add element inet test testset { ...  }

I figured that this approach was already on the cards ("I could of course flush the set and rebuild"), though it is possible that Anton wasn't aware that it can be done atomically.

As far I understand the original post, he is aggregating multiple country blocklists to form a single set - a blacklist or a whitelist, as it was put. That would explain his interest in deleting subsets to begin with. The flush/rebuild approach may well be faster but it would also require reading in all of the subsets again - even those that haven't changed. Perhaps not a big deal in the greater scheme of things but it does make me wonder whether there's room for improvement as far as deletions go. I might test this on the next occasion that I'm experimenting with set behaviour.

-- 
Kerin Millar

Re: Is there an efficient way to delete multiple elements from a set?

[Anton]

At this point I have moved on from the idea of aggregating multiple ip
blocks in a single set because I want my project to work well on
embedded devices which have limited memory and CPU power, and, as I
discovered by trial and error, currently adding elements is not an
option for this application because of high memory consumption and
other performance issues (which I reported in Bug 1735).
I figured that nftables provides a way to swap sets without offline
time, and it's good to have this confirmed. That said, it would be
really nice to have a swap command for nftables sets. This would be a
quality of life improvement that I'm sure many people would
appreciate.
Thanks everyone for your help.

On Thu, Feb 1, 2024 at 2:21 PM Kerin Millar <kfm@plushkava.net> wrote:
>
> Hi Pablo,
>
> On Thu, 1 Feb 2024, at 9:41 AM, Pablo Neira Ayuso wrote:
> > On Wed, Jan 31, 2024 at 10:14:41AM +0200, Anton wrote:
> >> Hello, I've been experimenting with nftables sets for the purpose of
> >> geoip blocking. Let's say I'd like to add ip blocks for multiple
> >> countries to a blacklist or to a whitelist. Perhaps the most efficient
> >> way to do that would be by combining all required ip blocks in one set
> >> (for each family). However since country ip blocks are a moving
> >> target, I would need to regularly refresh parts of that set. My idea
> >> was to delete all ip addresses corresponding to an ip block from the
> >> set and then add the updated ip block. The problem is, this is very
> >> slow. While adding an ip block takes (in my VM) 0.09s, deleting all
> >> ip's from that same block takes 14.5s.
> >>
> >> This is how I'm doing the deletion and the time measurement:
> >> printf '%s\n' "delete element inet test testset { $(cat test.set) };"
> >> | /usr/bin/time -f %es nft -f -
> >>
> >> (the test.set file stores a comma-separated list of subnets)
> >>
> >> Is there a more efficient way to do this? I could of course flush the
> >> set and rebuild it every time I need to update some part of it, but I
> >> thought I'd ask before deciding to implement that.
> >
> > It is possible to flush the set and fill up with content again:
> >
> > flush set inet test testset
> > add element inet test testset { ...  }
>
> I figured that this approach was already on the cards ("I could of course flush the set and rebuild"), though it is possible that Anton wasn't aware that it can be done atomically.
>
> As far I understand the original post, he is aggregating multiple country blocklists to form a single set - a blacklist or a whitelist, as it was put. That would explain his interest in deleting subsets to begin with. The flush/rebuild approach may well be faster but it would also require reading in all of the subsets again - even those that haven't changed. Perhaps not a big deal in the greater scheme of things but it does make me wonder whether there's room for improvement as far as deletions go. I might test this on the next occasion that I'm experimenting with set behaviour.
>
> --
> Kerin Millar