best way to optimize ipfw-dummynet interaction ?

[Luigi Rizzo]

Hi,
I am trying to solve the following problem:

when ipfw passes a packet to dummynet, the packet is tagged with a
'pipe number' which dummynet needs to look up to find the pointer
to the correct object -- something like this:

        IPFW_LOCK()
        rule = find_matching_rule();
    1.  ... pkt.tag.pipeNR = rule->pipe_number;
        IPFW_UNLOCK()
	...
        // now ipfw_pfil_hook calls dummynet:
        DUMMYNET_LOCK()
    2.  pipePTR = lookup(pkt.tag.pipeNR)
        ... dummynet processing
        DUMMYNET_UNLOCK()

        // ... after some time the packet is delivered
    3.  ip_output(pkt)

It would be nice to cache the result of a lookup in the ipfw rule
or in the table entry so we don't have to pay the cost all the times 
(the result would be stored as a <pipeNR:pipePTR:generation> tuple
same as ipfw rule pointers, so you can detect changes and do a
lookup if the generation number changes.)

But i cannot think of a good way of doing it -- i have two options
in mind:
 
A) right after #1, call into dummynet while still holding the IPFW LOCK:

        if (rule->pipePTR.generation != dummynet.generation) {
            DUMMYNET_LOCK()
                rule->pipePTR = lookup(pkt.tag.pipeNR)
            DUMMYNET_UNLOCK()
        }
   
   We can probably do the check outside the lock because the cached
   value is only advisory and if wrong we will detect it some other
   time (as long as the dummynet.generation variable does not go away).
   
B) + right after #1, store a reference to the rule (in the usual way
   involving a generation number) in the packet tag;
   + right after #2, store a reference to the pipePTR in the packet tag;
   + after #3, if the packet happens to enter IPFW again (or if it
   does not, do it on purpose) and the rulePTR is still valid, then
   store the result in rulePTR.

Solution A is somewhat simpler because the code is exactly the one i
wrote above, but i am not particularly fond of the nesting of the locks.

Solution B solves the lock nesting problem by piggybacking the message
onto the packet, but it might require a bit of extra work for copying
and checking those "safe references". Finally, we should make sure
that the 'reinjection' of information occurs even if packets are
systematically dropped (not unlikely to configure an ipfw rule that
points to a non-existing pipe, in which case we have useless lookups;
we could cache a negative info and save the lookup).

Comments or suggestions anyone ? With the recent optimization work
on ipfw and dummynet this is probably the last piece that uses
a suboptimal algorithm (the lookup is through a hash table but
constants do matter here).

	cheers
	luigi