A tiny almost sorta kinda nearly minimal perfect hash for a mac classifier?
Sean Conner
spc at conman.org
Mon Nov 14 03:13:30 EST 2011
It was thus said that the Great Dave Taht once stated:
> On Mon, Nov 14, 2011 at 3:41 AM, Fred Baker <fred at cisco.com> wrote:
> >
> > On Nov 14, 2011, at 10:22 AM, Sean Conner wrote:
> >
> >> Why not just use the lower N bits as the hash function?
> >
> > or
> >
> > unsigned macHash (unsigned long long macAddressClone) {
> > return 0xFFF & (macAddressClone ^ (macAddressClone >> 12));
> > }
> >
> > That allows you to keep different OUIs separated somewhat.
>
> I should probably not have used 'arp' as an example, but suggested tcpdump.
>
> Multicast and broadcast on 802.11 are 'special'. They are always
> transmitted at the lowest rate possible (and eat up correspondingly
> far more airtime), and in the case of power save mode, can be deferred
> up to 200 ms, to wait for stations to be awake enough to 'hear' them.
> So anything with the multicast mac bit set should end up dumped in a
> special queue to manage that better.
>
> Virtual interfaces on a given radio twiddle on the local mac bit and
> then do arbitrary transforms elsewhere on the mac
The format for a MAC address is:
+--------+--------+--------+--------+--------+--------+
| lg| | | | | |
+--------+--------+--------+--------+--------+--------+
\______||____OUI___________/
||
|+-- group/individual bit (1 = multicast/broadcast)
+--- global/local assigned address (1 = local)
Given that, I would then write the hash code as:
typdef union macaddr
{
uint8_t bit8[6];
uint16_t bit16[3];
} macaddr__t;
typedef enum macqueue
{
MACQ_NORMAL,
MACQ_SPECIAL
} macqueue__t;
macqueue__t mac_hash(unsigned int *phash,macaddr__t addr)
{
*phash = addr.bit16[2] & 0x0FFF;
if (addr.bit8[0] & 0x01)
return MACQ_SPECIAL;
else
return MACQ_NORMAL;
/*------------
; if I was very concerned with speed, I would do:
; return addr.bit8[0] & 0x01;
; but I opted for clarity here, not speed
;---------------*/
}
The broadcast MAC address is FF:FF:FF:FF:FF:FF while a multicast MAC address
is based off the IP multicast address, but the global bit is set, for
example: 01:00:5E:7F:00:01. This way, if you want to set
broadcasts/multicasts on their own special queue, you can (heck, you can
even have a separate hash table for them given this). I don't see how
locally defined addresses will mess this up, unless I see actual, real world
evidence.
-spc (Measure twice, cut once and all that ... )
More information about the Bloat-devel
mailing list