[Click] [PATCH] speedup radiotap parser
Matteo Croce
matteo at openwrt.org
Tue Nov 19 10:50:52 EST 2013
I made the pull request on github
2013/11/15 Eddie Kohler <ekohler at gmail.com>
> 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
>
--
Matteo Croce
OpenWrt Developer
_______ ________ __
| |.-----.-----.-----.| | | |.----.| |_
| - || _ | -__| || | | || _|| _|
|_______|| __|_____|__|__||________||__| |____|
|__| W I R E L E S S F R E E D O M
-----------------------------------------------------
BARRIER BREAKER
-----------------------------------------------------
* 1/2 oz Galliano Pour all ingredients into
* 4 oz cold Coffee an irish coffee mug filled
* 1 1/2 oz Dark Rum with crushed ice. Stir.
* 2 tsp. Creme de Cacao
-----------------------------------------------------
More information about the click
mailing list