Re: [netfilter-core] asymptotic complexity when creating new chains and rules

[Rusty Russell <rusty@rustcorp.com.au>]

In message <200401031636.11291.mail@stefan-winter.de> you write:
> But, if you iterate this process a hundred times (with increasing "N" in the 
> chain name, so that you get 200 chains with 200*62 rules altogether), adding 
> the chains slows down with every new chain (first chain: 20 ms, all chains 
> together 150 SECONDS). This seems to imply that adding a chain (or rule) is 
> of complexity O(n) with n being the number of rules/chains already in the 
> table, where one would expect O(1). Is that right?

Yes.  In particular, the userspace is theoretically O(1), in that if
you read the chains once, kept that copy, and every time updated it
and committed it to the kernel, that would be O(1).  But most uses of
libiptc do "read all rules, insert new one, repeat".  Secondly, the
kernel isn't O(1): it checks for loops, and actually calls all the
rules' matches and targets to check they like where they are.

This is why Harald is working on pkttables, which abandons the whole
"flip the whole table into the kernel approach".

Cheers,
Rusty.
PS.  netfilter-devel is the correct mailing list.
--
  Anyone who quotes me in their sig is an idiot. -- Rusty Russell.