svn commit: r195083 - projects/mesh11s/sys/net80211

Sam Leffler sam at FreeBSD.org
Fri Jun 26 22:58:22 UTC 2009 

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,

More information about the svn-src-projects mailing list