From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from brevard.conman.org (brevard.conman.org [66.252.224.242]) by huchra.bufferbloat.net (Postfix) with ESMTP id D45AE200411 for ; Mon, 14 Nov 2011 00:20:37 -0800 (PST) Received: by brevard.conman.org (Postfix, from userid 500) id 75DBA2EBD51D; Mon, 14 Nov 2011 03:20:37 -0500 (EST) Date: Mon, 14 Nov 2011 03:20:37 -0500 From: Sean Conner To: bloat-devel@lists.bufferbloat.net Subject: Re: A tiny almost sorta kinda nearly minimal perfect hash for a mac classifier? Message-ID: <20111114082036.GC5769@brevard.conman.org> Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit User-Agent: Mutt/1.4.1i X-BeenThere: bloat-devel@lists.bufferbloat.net X-Mailman-Version: 2.1.13 Precedence: list List-Id: "Developers working on AQM, device drivers, and networking stacks" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 14 Nov 2011 08:20:38 -0000 It was thus said that the Great Dave Taht once stated: > On Mon, Nov 14, 2011 at 3:41 AM, Fred Baker 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 ... )