Date: Fri, 26 Jun 2009 22:58:22 +0000 (UTC) From: Sam Leffler <sam@FreeBSD.org> To: src-committers@freebsd.org, svn-src-projects@freebsd.org Subject: svn commit: r195083 - projects/mesh11s/sys/net80211 Message-ID: <200906262258.n5QMwMPd012707@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: sam Date: Fri Jun 26 22:58:22 2009 New Revision: 195083 URL: http://svn.freebsd.org/changeset/base/195083 Log: import the mac address hash function from bridge and use it for node table hashing and calculating hash codes for mesh packets q'd waiting path discovery Modified: projects/mesh11s/sys/net80211/ieee80211.c projects/mesh11s/sys/net80211/ieee80211_hwmp.c projects/mesh11s/sys/net80211/ieee80211_node.c projects/mesh11s/sys/net80211/ieee80211_node.h projects/mesh11s/sys/net80211/ieee80211_var.h Modified: projects/mesh11s/sys/net80211/ieee80211.c ============================================================================== --- projects/mesh11s/sys/net80211/ieee80211.c Fri Jun 26 22:26:07 2009 (r195082) +++ projects/mesh11s/sys/net80211/ieee80211.c Fri Jun 26 22:58:22 2009 (r195083) @@ -269,6 +269,7 @@ ieee80211_ifattach(struct ieee80211com * ic->ic_update_mcast = null_update_mcast; ic->ic_update_promisc = null_update_promisc; + ic->ic_hash_key = arc4random(); ic->ic_bintval = IEEE80211_BINTVAL_DEFAULT; ic->ic_lintval = ic->ic_bintval; ic->ic_txpowlimit = IEEE80211_TXPOWER_MAX; @@ -1574,3 +1575,39 @@ ieee80211_media2rate(int mword) ieeerates[IFM_SUBTYPE(mword)] : 0; #undef N } + +/* + * The following hash function is adapted from "Hash Functions" by Bob Jenkins + * ("Algorithm Alley", Dr. Dobbs Journal, September 1997). + */ +#define mix(a, b, c) \ +do { \ + a -= b; a -= c; a ^= (c >> 13); \ + b -= c; b -= a; b ^= (a << 8); \ + c -= a; c -= b; c ^= (b >> 13); \ + a -= b; a -= c; a ^= (c >> 12); \ + b -= c; b -= a; b ^= (a << 16); \ + c -= a; c -= b; c ^= (b >> 5); \ + a -= b; a -= c; a ^= (c >> 3); \ + b -= c; b -= a; b ^= (a << 10); \ + c -= a; c -= b; c ^= (b >> 15); \ +} while (/*CONSTCOND*/0) + +uint32_t +ieee80211_mac_hash(const struct ieee80211com *ic, + const uint8_t addr[IEEE80211_ADDR_LEN]) +{ + uint32_t a = 0x9e3779b9, b = 0x9e3779b9, c = ic->ic_hash_key; + + b += addr[5] << 8; + b += addr[4]; + a += addr[3] << 24; + a += addr[2] << 16; + a += addr[1] << 8; + a += addr[0]; + + mix(a, b, c); + + return c; +} +#undef mix Modified: projects/mesh11s/sys/net80211/ieee80211_hwmp.c ============================================================================== --- projects/mesh11s/sys/net80211/ieee80211_hwmp.c Fri Jun 26 22:26:07 2009 (r195082) +++ projects/mesh11s/sys/net80211/ieee80211_hwmp.c Fri Jun 26 22:58:22 2009 (r195083) @@ -804,11 +804,14 @@ hwmp_recv_prep(struct ieee80211vap *vap, struct mbuf *m, *next; /* * Check for frames queued awaiting path discovery. - * XXX how can we tell + * XXX probably can tell exactly and avoid remove call + * NB: hash may have false matches, if so they will get + * stuck back on the stageq because there won't be + * a path. */ m = ieee80211_ageq_remove(&ic->ic_stageq, (struct ieee80211_node *)(uintptr_t) - IEEE80211_NODE_HASH(fi->fi_dest)); + ieee80211_mac_hash(ic, fi->fi_dest)); for (; m != NULL; m = next) { next = m->m_nextpkt; m->m_nextpkt = NULL; @@ -1056,15 +1059,16 @@ done: IEEE80211_DISCARD_MAC(vap, IEEE80211_MSG_HWMP, dest, NULL, "%s", "no valid path to this node"); if (sendpreq) { + struct ieee80211com *ic = vap->iv_ic; /* * Queue packet for transmit when path discovery * completes. If discovery never completes the * frame will be flushed by way of the aging timer. */ m->m_pkthdr.rcvif = (void *)(uintptr_t) - IEEE80211_NODE_HASH(dest); + ieee80211_mac_hash(ic, dest); /* XXX age chosen randomly */ - ieee80211_ageq_append(&vap->iv_ic->ic_stageq, m, + ieee80211_ageq_append(&ic->ic_stageq, m, IEEE80211_INACT_WAIT); } else m_freem(m); Modified: projects/mesh11s/sys/net80211/ieee80211_node.c ============================================================================== --- projects/mesh11s/sys/net80211/ieee80211_node.c Fri Jun 26 22:26:07 2009 (r195082) +++ projects/mesh11s/sys/net80211/ieee80211_node.c Fri Jun 26 22:58:22 2009 (r195083) @@ -55,6 +55,11 @@ __FBSDID("$FreeBSD$"); #include <net/bpf.h> /* + * IEEE80211_NODE_HASHSIZE must be a power of 2. + */ +CTASSERT((IEEE80211_NODE_HASHSIZE & (IEEE80211_NODE_HASHSIZE-1)) == 0); + +/* * Association id's are managed with a bit vector. */ #define IEEE80211_AID_SET(_vap, b) \ @@ -1083,7 +1088,7 @@ ieee80211_alloc_node(struct ieee80211_no ether_sprintf(macaddr), nt->nt_name); IEEE80211_ADDR_COPY(ni->ni_macaddr, macaddr); - hash = IEEE80211_NODE_HASH(macaddr); + hash = IEEE80211_NODE_HASH(ic, macaddr); ieee80211_node_initref(ni); /* mark referenced */ ni->ni_chan = IEEE80211_CHAN_ANYC; ni->ni_authmode = IEEE80211_AUTH_OPEN; @@ -1247,7 +1252,7 @@ ieee80211_find_node_locked(struct ieee80 IEEE80211_NODE_LOCK_ASSERT(nt); - hash = IEEE80211_NODE_HASH(macaddr); + hash = IEEE80211_NODE_HASH(nt->nt_ic, macaddr); LIST_FOREACH(ni, &nt->nt_hash[hash], ni_hash) { if (IEEE80211_ADDR_EQ(ni->ni_macaddr, macaddr)) { ieee80211_ref_node(ni); /* mark referenced */ @@ -1297,7 +1302,7 @@ ieee80211_find_vap_node_locked(struct ie IEEE80211_NODE_LOCK_ASSERT(nt); - hash = IEEE80211_NODE_HASH(macaddr); + hash = IEEE80211_NODE_HASH(nt->nt_ic, macaddr); LIST_FOREACH(ni, &nt->nt_hash[hash], ni_hash) { if (ni->ni_vap == vap && IEEE80211_ADDR_EQ(ni->ni_macaddr, macaddr)) { Modified: projects/mesh11s/sys/net80211/ieee80211_node.h ============================================================================== --- projects/mesh11s/sys/net80211/ieee80211_node.h Fri Jun 26 22:26:07 2009 (r195082) +++ projects/mesh11s/sys/net80211/ieee80211_node.h Fri Jun 26 22:58:22 2009 (r195083) @@ -57,11 +57,9 @@ /* threshold for aging overlapping non-ERP bss */ #define IEEE80211_NONERP_PRESENT_AGE msecs_to_ticks(60*1000) -#define IEEE80211_NODE_HASHSIZE 32 -/* simple hash is enough for variation of macaddr */ -#define IEEE80211_NODE_HASH(addr) \ - (((const uint8_t *)(addr))[IEEE80211_ADDR_LEN - 1] % \ - IEEE80211_NODE_HASHSIZE) +#define IEEE80211_NODE_HASHSIZE 32 /* NB: hash size must be pow2 */ +#define IEEE80211_NODE_HASH(ic, addr) \ + (ieee80211_mac_hash(ic, addr) & (IEEE80211_NODE_HASHSIZE-1)) struct ieee80211_node_table; struct ieee80211com; Modified: projects/mesh11s/sys/net80211/ieee80211_var.h ============================================================================== --- projects/mesh11s/sys/net80211/ieee80211_var.h Fri Jun 26 22:26:07 2009 (r195082) +++ projects/mesh11s/sys/net80211/ieee80211_var.h Fri Jun 26 22:58:22 2009 (r195083) @@ -195,6 +195,7 @@ struct ieee80211com { int ic_max_keyix; /* max h/w key index */ struct ieee80211_node_table ic_sta; /* stations/neighbors */ struct ieee80211_ageq ic_stageq; /* frame staging queue */ + uint32_t ic_hash_key; /* random key for mac hash */ /* XXX multi-bss: split out common/vap parts */ struct ieee80211_wme_state ic_wme; /* WME/WMM state */ @@ -665,6 +666,8 @@ struct ieee80211_channel *ieee80211_find int ieee, int flags); int ieee80211_setmode(struct ieee80211com *, enum ieee80211_phymode); enum ieee80211_phymode ieee80211_chan2mode(const struct ieee80211_channel *); +uint32_t ieee80211_mac_hash(const struct ieee80211com *, + const uint8_t addr[IEEE80211_ADDR_LEN]); void ieee80211_radiotap_attach(struct ieee80211com *, struct ieee80211_radiotap_header *th, int tlen,
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200906262258.n5QMwMPd012707>