cvs commit: src/sbin/ipfw ipfw2.c

[Luigi Rizzo]

On Mon, Aug 07, 2006 at 10:40:54PM -0700, Julian Elischer wrote:
> 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.

agreed.
On the other hand, i think that a simpler solution could be used.
Consider that the granularity of keepalives and expire can be much
coarser than 1 tick - basically there are no adverse side effects
if you round it up to 500-1000ms.
So i'd just keep everything as it is now, except that at every call
ipfw_tick() will only scan curr_dyn_buckets/HZ lists.
This should reduce the load by 2-3 orders of magnitude and
is trivial to implement.

	cheers
	luigi

> 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.
> 
> 
> _______________________________________________
> freebsd-net at freebsd.org mailing list
> http://lists.freebsd.org/mailman/listinfo/freebsd-net
> To unsubscribe, send any mail to "freebsd-net-unsubscribe at freebsd.org"