[Click] [PATCH] speedup radiotap parser
Eddie Kohler
ekohler at gmail.com
Fri Nov 15 10:53:36 EST 2013
Hi Matteo,
(1) Can you send patches like this via Github pull requests?
(2) I'd prefer for `offsets` to be a parameter rather than a global
(for multithread safety). If you can't do this I will sometime.
Eddie
On Thu, Nov 14, 2013 at 1:31 PM, Matteo Croce <matteo at openwrt.org> wrote:
> 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
>
> _______________________________________________
> click mailing list
> click at amsterdam.lcs.mit.edu
> https://amsterdam.lcs.mit.edu/mailman/listinfo/click
More information about the click
mailing list