cvs commit: src/sbin/ipfw ipfw2.c

[Julian Elischer]

Andrey V. Elsukov wrote:

> Julian Elischer wrote:
>
>> great.. I have been in ipfw(2) the last week and have some sugestions 
>> for
>> increasing its efficiency.. especially the code that times out 
>> dynamic rules.
>
> Can you explain your suggestions in detail?
>
I sent the following to luigi:
I repeat it here..

------------ start comment to Luigi --------------

I haven't coded it yet but we run with maybe 50,000 dynamic rules at a
time. (hopefully a lot more, maybe 200,000 in the near future)
We need to simplify the code that times out the rules so that it doesn't 
have to
scan through ALL the dynamic rules every clocktick.

Basically I  was thinking of  implementing a timing wheel  representing 
the next "600" seconds or so.
(600 slots).      "now" moves around the wheel.
(The size of the wheel is the size of the largest lifetime value.)
(maybe with a backup wheel at 600 seconds per slot or something)

Each dynamic entry has an extra linkage to allow it to be linked
onto the appropriate slot. whenever you use an entry you take it out
of where-ever it is and put it into it's new slot X seconds into the 
future.

At each tick you take all the entries that have reached "now"
and do whatever needs t be done on  only those entries.
thus at each tick you only have a small amount of work to
do instead fo looking at all 50,000 entries.