Daniel Hartmeier wrote:
There is one change that I'm worried, it's the following in calc_skip_steps:On Fri, Dec 20, 2002 at 07:11:12PM +0100, Cedric Berger wrote:Yes, it's a valid address, but not a valid mask :)Oh, misread the 'm->'. Hmm, it's not an invalid mask, actually, but one pfctl can't load yet. There were a couple of requests to allow arbitrary masks (like 0.0.0.10/0x000000ff would match *.10), and the kernel would already deal with them, just the parser doesn't support it. I guess even when we reserve the option to eventually support more masks than 'the left-most n bits are set' of /n, there is a mask that nobody ever wants to use (like 0xCAFEBABE). pfctl could check and refuse that value, when someone tries to use it normally. Well, the pf part is small, and it's easily verified that it doesn't break existing behavior (as long as you don't actually use the new tables). And, well, the new code could simply be put into a separate source file. Doesn't increase complexity or decrease stability of the existing code in any way, if the new tables are not actually used.
- PF_AEQ(&s->src.addr.addr, &r->src.addr.addr, r->af) &&
- PF_AEQ(&s->src.mask, &r->src.mask, r->af) &&
+ PF_AEQ(&s->src.addr.addr, &r->src.addr.addr, 0) &&
+ PF_AEQ(&s->src.mask, &r->src.mask, 0) &&
I'm doing that because PF_AEQ only compare the first 32 bits if
AF_INET is used, but I need that code to compare the whole pf_addr
even in the case of AF_INET, when I store a table reference in there.
Now that change could result in a missed skip-step optimization if there
are two identical AF_INET addresses loaded with a different values in
words 1-3. I've added some code in pf_ioctl to always zero words 1-3
when we load the ruleset, but I'm not sure if I've cached all occurences.
We've just added anchors to deal with large sub-rulesets, for instance I load 12000 rules like block in quick on kue0 from 1.2.3.4 to any port 25 block in quick on kue0 from 2.3.4.5/28 to any port 25 ... into an anchor to keep it managable. But, of course, using a hash table to put all 12000 source addresses/networks into a single rule would solve that significantly better. Wouldn't obsolete the anchors, as you'd still use them for sub-rulesets that don't just consist of simple variations like the above. The patricia tree idea is excellent. We talked about using a simple hash table, but that wouldn't have allowed to store networks (just addresses). So, do I understand that right, I can store arbitrary CIDR blocks and the lookup with an address of a packet is still O(1)? That's very neat.
Yes, it works exactly like the routing table, with the following additional
feature: you can enter a "negative" entry. for example, you can put the
following into the tree:
home# pfradix -s a:a 10.0.0.0/8 '!10.0.0.0/16' 10.0.0.1
This would cause the table to match 10/8 entries which are not in 10.0/16,
but 10.0.0.1 would also match, this can be verified with "pfradix -tv":
home# pfradix -tv a:a 10.0.0.1 10.0.0.2 10.1.0.1
10.0.0.1 match
10.0.0.2 nomatch
10.1.0.1 match
Cedric
