K 10
svn:author
V 5
luigi
K 8
svn:date
V 27
2009-12-22T16:06:38.725944Z
K 7
svn:log
V 1154
complete the code for improved rule lookup in ipfw.
Now we should have the following (Old is the code in HEAD;
"Now" means the code in this commit; "Planned" is what i
expect to achieve with small changes):

  Function				Old	Now	  Planned
-------------------------------------------------------------------
  + skipto X, non cached		O(N)	O(log N)
XXX skipto X, cached			O(1)	O(log N)  O(1) NOTE 1
XXX dynamic rule lookup			O(1)	O(log N)  O(1) NOTE 1
  + skipto tablearg			O(N)	O(log N)  O(1) NOTE 2
  + reinject from dummynet, non cached	O(N)	O(log N)
  + reinject from dummynet, cached	O(1)	O(1)
  + kernel blocked during setsockopt()	O(N)	O(1)

NOTE 1: validating the cached entries requires an extra field
	in the rule structure, which in turn requires a bit of work
	to preserve the kernel-userland ABI.

NOTE 2: currently there is no cache for skipto tablearg.
	It can be implemented rather trivially to achieve
	O(1) time on repeated jumps to the same target.

As you can see there are a couple of places where we have a bit
of regression, but in most cases there is a huge improvement,
especially in the interference between userland and kernel.

END