[Bug 1460] New: nft_table_validate() exceptionally slow for some configurations

[bugzilla-daemon at netfilter.org]

https://bugzilla.netfilter.org/show_bug.cgi?id=1460

            Bug ID: 1460
           Summary: nft_table_validate() exceptionally slow for some
                    configurations
           Product: nftables
           Version: unspecified
          Hardware: x86_64
                OS: All
            Status: NEW
          Severity: enhancement
          Priority: P5
         Component: kernel
          Assignee: pablo at netfilter.org
          Reporter: steve at opendium.com

Created attachment 606
  --> https://bugzilla.netfilter.org/attachment.cgi?id=606&action=edit
Example pathological configuration

nf_tables_check_loops() and nft_table_validate() are executed when new rules
are added to nftables.  These are brute-force validation functions which walk
over the entire ruleset, following all jumps and gotos.  Chains which are
jumped/goto'd to multiple times are walked over multiple times.

nft_table_validate() can become extremely slow with some configurations.  The
attached test-case takes 5 seconds to validate on my test machine, during which
time the CPU is locked up and the machine is unresponsive.  Worse
configurations are trivial to implement, locking the machine up for many
minutes at a time.

I'm not sure why, but nf_table_check_loops() seems comparatively fast.  As far
as I can see it walks over the ruleset in the same way as nft_table_validate()
(although it doesn't always start from the root chains, so doesn't always check
the whole ruleset).

There are more efficient algorithms for checking for loops, and adding some
caching to nft_chain_validate() so that chains aren't revisited multiple times
would be a big help.

-- 
You are receiving this mail because:
You are watching all bug changes.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.netfilter.org/pipermail/netfilter-buglog/attachments/20200828/66d47bc4/attachment.html>