[Click] [PATCH] speedup radiotap parser

[Matteo Croce]

Scan the radiotap header once per packet thus reducing
the parser complexity from O(n^2) to O(n)
---
 elements/wifi/radiotapdecap.cc | 37 ++++++++++++++++---------------------
 1 file changed, 16 insertions(+), 21 deletions(-)

diff --git a/elements/wifi/radiotapdecap.cc b/elements/wifi/radiotapdecap.cc
index e30f84d..ab91788 100644
--- a/elements/wifi/radiotapdecap.cc
+++ b/elements/wifi/radiotapdecap.cc
@@ -50,6 +50,8 @@ static const int radiotap_elem_to_bytes[NUM_RADIOTAP_ELEMENTS] =
 	 1, /* IEEE80211_RADIOTAP_DATA_RETRIES */
 	};
 
+static u_int8_t *offsets[NUM_RADIOTAP_ELEMENTS];
+
 static int rt_el_present(struct ieee80211_radiotap_header *th, u_int32_t element)
 {
 	if (element > NUM_RADIOTAP_ELEMENTS)
@@ -61,6 +63,8 @@ static int rt_check_header(struct ieee80211_radiotap_header *th, int len)
 {
 	int bytes = 0;
 	int x = 0;
+	u_int8_t *ptr = (u_int8_t *)(th + 1);
+
 	if (th->it_version != 0) {
 		return 0;
 	}
@@ -70,8 +74,10 @@ static int rt_check_header(struct ieee80211_radiotap_header *th, int len)
 	}
 
 	for (x = 0; x < NUM_RADIOTAP_ELEMENTS; x++) {
-		if (rt_el_present(th, x))
+		if (rt_el_present(th, x)) {
+		    offsets[x] = ptr + bytes;
 		    bytes += radiotap_elem_to_bytes[x];
+		}
 	}
 
 	if (le16_to_cpu(th->it_len) < sizeof(struct ieee80211_radiotap_header) + bytes) {
@@ -85,17 +91,6 @@ static int rt_check_header(struct ieee80211_radiotap_header *th, int len)
 	return 1;
 }
 
-static u_int8_t *rt_el_offset(struct ieee80211_radiotap_header *th, u_int32_t element) {
-	unsigned int x = 0;
-	u_int8_t *offset = ((u_int8_t *) th) + sizeof(ieee80211_radiotap_header);
-	for (x = 0; x < NUM_RADIOTAP_ELEMENTS && x < element; x++) {
-		if (rt_el_present(th, x))
-			offset += radiotap_elem_to_bytes[x];
-	}
-
-	return offset;
-}
-
 RadiotapDecap::RadiotapDecap()
 {
 }
@@ -121,7 +116,7 @@ RadiotapDecap::simple_action(Packet *p)
 		ceh->magic = WIFI_EXTRA_MAGIC;
 
 		if (rt_el_present(th, IEEE80211_RADIOTAP_FLAGS)) {
-			u_int8_t flags = *((u_int8_t *) rt_el_offset(th, IEEE80211_RADIOTAP_FLAGS));
+			u_int8_t flags = *offsets[IEEE80211_RADIOTAP_FLAGS];
 			if (flags & IEEE80211_RADIOTAP_F_DATAPAD) {
 				ceh->pad = 1;
 			}
@@ -131,36 +126,36 @@ RadiotapDecap::simple_action(Packet *p)
 		}
 
 		if (rt_el_present(th, IEEE80211_RADIOTAP_RATE)) {
-			ceh->rate = *((u_int8_t *) rt_el_offset(th, IEEE80211_RADIOTAP_RATE));
+			ceh->rate = *offsets[IEEE80211_RADIOTAP_RATE];
 		}
 
 		if (rt_el_present(th, IEEE80211_RADIOTAP_DBM_ANTSIGNAL))
-			ceh->rssi = *((u_int8_t *) rt_el_offset(th, IEEE80211_RADIOTAP_DBM_ANTSIGNAL));
+			ceh->rssi = *offsets[IEEE80211_RADIOTAP_DBM_ANTSIGNAL];
 
 		if (rt_el_present(th, IEEE80211_RADIOTAP_DBM_ANTNOISE))
-			ceh->silence = *((u_int8_t *) rt_el_offset(th, IEEE80211_RADIOTAP_DBM_ANTNOISE));
+			ceh->silence = *offsets[IEEE80211_RADIOTAP_DBM_ANTNOISE];
 
 		if (rt_el_present(th, IEEE80211_RADIOTAP_DB_ANTSIGNAL))
-			ceh->rssi = *((u_int8_t *) rt_el_offset(th, IEEE80211_RADIOTAP_DB_ANTSIGNAL));
+			ceh->rssi = *offsets[IEEE80211_RADIOTAP_DB_ANTSIGNAL];
 
 		if (rt_el_present(th, IEEE80211_RADIOTAP_DB_ANTNOISE))
-			ceh->silence = *((u_int8_t *) rt_el_offset(th, IEEE80211_RADIOTAP_DB_ANTNOISE));
+			ceh->silence = *offsets[IEEE80211_RADIOTAP_DB_ANTNOISE];
 
 		if (rt_el_present(th, IEEE80211_RADIOTAP_RX_FLAGS)) {
-			u_int16_t flags = le16_to_cpu(*((u_int16_t *) rt_el_offset(th, IEEE80211_RADIOTAP_RX_FLAGS)));
+			u_int16_t flags = le16_to_cpu(*((u_int16_t *) offsets[IEEE80211_RADIOTAP_RX_FLAGS]));
 			if (flags & IEEE80211_RADIOTAP_F_RX_BADFCS)
 				ceh->flags |= WIFI_EXTRA_RX_ERR;
 		}
 
 		if (rt_el_present(th, IEEE80211_RADIOTAP_TX_FLAGS)) {
-			u_int16_t flags = le16_to_cpu(*((u_int16_t *) rt_el_offset(th, IEEE80211_RADIOTAP_TX_FLAGS)));
+			u_int16_t flags = le16_to_cpu(*((u_int16_t *) offsets[IEEE80211_RADIOTAP_TX_FLAGS]));
 			ceh->flags |= WIFI_EXTRA_TX;
 			if (flags & IEEE80211_RADIOTAP_F_TX_FAIL)
 				ceh->flags |= WIFI_EXTRA_TX_FAIL;
 		}
 
 		if (rt_el_present(th, IEEE80211_RADIOTAP_DATA_RETRIES))
-			ceh->retries = *((u_int8_t *) rt_el_offset(th, IEEE80211_RADIOTAP_DATA_RETRIES));
+			ceh->retries = *offsets[IEEE80211_RADIOTAP_DATA_RETRIES];
 
 		p->pull(le16_to_cpu(th->it_len));
 		p->set_mac_header(p->data());  // reset mac-header pointer
-- 
1.8.3.2