A tiny almost sorta kinda nearly minimal perfect hash for a mac classifier?

[Dave Taht <dave.taht@gmail.com>]

There's this class of non-algorithms where stupid and brute force
nearly works. Then there are the be-all end-all algorithms which scale
beautifully O(1) over n - so long as n is large enough to wipe out the
overhead of the be-all-end-all algorithm, and taking locks, allocating
memory at bad times, etc, is ok.

I keep running into problems where brute force and a simple table
lookup is almost enough.

Here's one. I'd like to classify network streams so that they end up
in a unique queue[x], based on their nexthop mac address in the ip
header.

One of a small number (say, x < 2048) of queues, that needs to be
absolutely unique per mac. It's ok if 99% of the queues
are idle at any given point. It's OK if the initial classification
collides with another mac so long as eventually it doesn't.

Algo needs to be fast and lock free, relying only on a very few atomic
increment and/or swaps, only in rare cases...

On most networks today, you are usually talking to a VERY few
machines. The number of machines that appear and disappear is rather
small and stable over very long periods of time (proof: go type arp -a
on your home network)

Yet mac addresses are 48 bits wide.

Even in the case of an access point, you are never going to see more
than 2048 of them, and most APs stop at around 127 stations, and most
wireless networks have many fewer endpoints than that...

So great, I figure a mere 2 bin table lookup and random replacement
will work fine, I stuck my first attempt up at
http://www.teklibre.com/~d/mactoclass.c

and I hate it. Didn't get so far as writing garbage collection.
(double buffer it) Does anything elegant exist? Anything worthy in the
kernel?

-- 
Dave Täht
SKYPE: davetaht
US Tel: 1-239-829-5608
FR Tel: 0638645374
http://www.bufferbloat.net