[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Optimizing rules.

On Sun, Dec 08, 2002 at 10:13:18AM -0300, Alejandro G. Belluscio wrote:
> I was wondering if there was any performance difference from ordering
> the rules in a certain way. For example. I usually order my rules
> first for interface, then for direction, IP type and then by IP
> protocol.
The feature is called 'skip steps'. When two subsequent rules specify
the same value for a parameter (like 'on fxp0'), and a packet mismatches
the parameter (because it arrived on interface fxp1, for instance), the
second rule is not evaluated (as it couldn't possibly match), but
Since parameters are checked in a fixed order, the skip step values of
the parameters checked earlier are more effective, and ordering your
rules sorted by these parameters maximizes skip steps on average.
The order is
  interface, direction, address family, protocol, source address,
  source port, destination address, destination port.
If your firewall is overloaded to the point where it drops packets due
to the cost of rule set evaluation, you can reduce the cost by
re-arranging your rules. Except for such extreme cases, I'd suggest you
just write the rules in an order that makes most sense to you, and don't
worry about skip steps performance gain.
> Does this affect the loading speed of the rules?
Calculation of the skip step values is done automatically when you
reload the rule set, and only once, after the last rule of the rule set
is loaded. You'll need to load a pretty large rule set to notice the
delay caused by skip step calculation, and it only occurs once, when you
load the rule set. Even in worst case, rule evaluation is never slower
using skip steps.
> That being the case, do you think it
> would be worth to have a switch not to optimize in that way the rule
> set? May be for high availability instalations? And may be let the
> optimizer be run to standard output so it can be done offline. Just a
> thought.
It's not really that computationally expensive. The current algorithm is
O(n*n) worst case, where n is the number or rules. Notably, the worse
the cost of calculating the skip step values gets, the larger they
become, and the more you gain in evaluation later on, on average.
A rule set with no similar parameters in nearby rules will have O(n)
cost for skip step calculation.
If you really have a huge rule set and wonder how much of the rule loading
time is caused by skip step calculation, you can just comment out the calls
to pf_calc_skip_steps() in sys/net/pf_ioctl.c and compare. I'd be surprised
if it made a significant difference, as the one-by-one transfer of rules
through ioctl is what is taking most of the time.