<html>
<head>
<base href="https://bugzilla.netfilter.org/" />
</head>
<body><table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Bug ID</th>
<td><a class="bz_bug_link
bz_status_NEW "
title="NEW - nft_table_validate() exceptionally slow for some configurations"
href="https://bugzilla.netfilter.org/show_bug.cgi?id=1460">1460</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>nft_table_validate() exceptionally slow for some configurations
</td>
</tr>
<tr>
<th>Product</th>
<td>nftables
</td>
</tr>
<tr>
<th>Version</th>
<td>unspecified
</td>
</tr>
<tr>
<th>Hardware</th>
<td>x86_64
</td>
</tr>
<tr>
<th>OS</th>
<td>All
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Severity</th>
<td>enhancement
</td>
</tr>
<tr>
<th>Priority</th>
<td>P5
</td>
</tr>
<tr>
<th>Component</th>
<td>kernel
</td>
</tr>
<tr>
<th>Assignee</th>
<td>pablo@netfilter.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>steve@opendium.com
</td>
</tr></table>
<p>
<div>
<pre>Created <span class=""><a href="attachment.cgi?id=606" name="attach_606" title="Example pathological configuration">attachment 606</a> <a href="attachment.cgi?id=606&action=edit" title="Example pathological configuration">[details]</a></span>
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.</pre>
</div>
</p>
<hr>
<span>You are receiving this mail because:</span>
<ul>
<li>You are watching all bug changes.</li>
</ul>
</body>
</html>