[802.11] Add rate control support; fix two bugs; remove high rate bits
authorJoshua Oreman <oremanj@xenon.get-linux.org>
Sat, 20 Jun 2009 05:56:21 +0000 (22:56 -0700)
committerJoshua Oreman <oremanj@xenon.get-linux.org>
Sat, 20 Jun 2009 05:56:21 +0000 (22:56 -0700)
The idea of using the upper two bits of a bitrate number for future flags
was bad from the start; do away with it, and the ugly NET80211_RATE_VALUE()
macros that resulted from it. 802.11n support is going to require a lot
more than a couple spare bits.

Add a rate-control algorithm, using a lightweight heuristic approach designed
for gPXE's environment that worked quite well in my testing. It aims for as
high a rate as the sending AP is using, higher in cases of very low packet
loss, and degrades gracefully under poorer conditions.

Add a flag in dev->state, NET80211_AUTO_SSID, that tracks whether our
association was based on a specific SSID or a best-signal pick from an
unfiltered probe. The distinction is relevant in the settings applicator,
so that we can know whether an empty netX/ssid setting represents a change
we must act upon. This fixes a bug that made the 802.11 layer attempt to
reassociate during the post-DHCP settings application, sometimes picking
a different network and rendering the DHCP moot.

Fix a bug that made the auto-association task sometimes start in the middle
of its state machine without initializing things as it expected.

src/include/gpxe/net80211.h
src/include/gpxe/rc80211.h [new file with mode: 0644]
src/net/net80211.c
src/net/rc80211.c [new file with mode: 0644]

index b719db9..c233a8f 100644 (file)
@@ -5,6 +5,7 @@
 #include <gpxe/ieee80211.h>
 #include <gpxe/iobuf.h>
 #include <gpxe/netdevice.h>
+#include <gpxe/rc80211.h>
 
 /** @file
  * The gPXE 802.11 MAC layer.
@@ -198,9 +199,26 @@ enum net80211_crypto_alg {
 /** Whether the auto-association task is waiting for a reply from the AP */
 #define NET80211_WAITING        (1 << 13)
 
-/** Whether the auto-association task should be suppressed */
+/** Whether the auto-association task should be suppressed
+ *
+ * This is set by the `iwlist' command so that it can open the device
+ * without starting another probe process that will interfere with its
+ * own.
+ */
 #define NET80211_NO_ASSOC      (1 << 14)
 
+/** Whether this association was performed using a broadcast SSID
+ *
+ * If the user opened this device without netX/ssid set, the device's
+ * SSID will be set to that of the network it chooses to associate
+ * with, but the netX/ssid setting will remain blank. If we don't
+ * remember that we started from no specified SSID, it will appear
+ * every time settings are updated (e.g. after DHCP) that we need to
+ * reassociate due to the change.
+ */
+#define NET80211_AUTO_SSID     (1 << 15)
+
+
 /** @} */
 
 
@@ -235,21 +253,6 @@ enum net80211_crypto_alg {
 /** @} */
 
 
-/** @defgroup net80211_ratedefs 802.11 layer rate flags */
-/** @{ */
-
-/** Get rate (in 100 kbps) from a ratecode */
-#define NET80211_RATE_VALUE(r) ((r) & 0x3fff)
-
-/** Rate flag 1 (reserved) */
-#define NET80211_RATE_FLAG1    0x8000
-
-/** Rate flag 2 (reserved) */
-#define NET80211_RATE_FLAG2    0x4000
-
-/** @} */
-
-
 /** The maximum number of TX rates we allow to be configured simultaneously */
 #define NET80211_MAX_RATES     16
 
@@ -650,9 +653,7 @@ struct net80211_device
 
        /** A list of all possible TX rates we might use
         *
-        * Rates are in units of 100 kbps. We reserve two bits for
-        * future flags (e.g. for 802.11n), meaning we can represent
-        * rates up to 1.6 Gbps.
+        * Rates are in units of 100 kbps.
         */
        u16 rates[NET80211_MAX_RATES];
 
@@ -750,7 +751,7 @@ struct net80211_device
         * To prevent association when opening the device, user code
         * can set the NET80211_NO_ASSOC bit.
         */
-       short state;
+       u16 state;
 
        /** gPXE error code associated with @c state */
        int assoc_rc;
@@ -789,6 +790,9 @@ struct net80211_device
        /** Signal strength of last received packet */
        int last_signal;
 
+       /** Rate control state */
+       struct rc80211_ctx *rctl;
+
        /* ---------- Packet handling state ---------- */
 
        /** Fragment reassembly state */
@@ -896,8 +900,9 @@ struct net80211_wlan
 /* Associate with the best or user-specified network: */
 void net80211_autoassociate ( struct net80211_device *dev );
 
-/* Change channel: */
+/* Set physical-layer parameters: */
 int net80211_change_channel ( struct net80211_device *dev, int channel );
+void net80211_set_rate_idx ( struct net80211_device *dev, int rate );
 
 /* Find networks: */
 struct net80211_probe_ctx * net80211_probe_start ( struct net80211_device *dev,
@@ -936,7 +941,7 @@ int net80211_register ( struct net80211_device *dev,
                        struct net80211_device_operations *ops,
                        struct net80211_hw_info *hw );
 void net80211_rx ( struct net80211_device *dev, struct io_buffer *iob,
-                  int signal );
+                  int signal, u16 rate );
 void net80211_rx_err ( struct net80211_device *dev,
                       struct io_buffer *iob, int rc );
 void net80211_tx_complete ( struct net80211_device *dev,
diff --git a/src/include/gpxe/rc80211.h b/src/include/gpxe/rc80211.h
new file mode 100644 (file)
index 0000000..0b82536
--- /dev/null
@@ -0,0 +1,18 @@
+#ifndef _GPXE_RC80211_H
+#define _GPXE_RC80211_H
+
+/** @file
+ * Rate-control algorithm for 802.11.
+ */
+
+FILE_LICENCE ( GPL2_OR_LATER );
+
+struct net80211_device;
+struct rc80211_ctx;
+
+struct rc80211_ctx * rc80211_init ( struct net80211_device *dev );
+void rc80211_update_tx ( struct net80211_device *dev, int retries, int rc );
+void rc80211_update_rx ( struct net80211_device *dev, int retry, u16 rate );
+void rc80211_free ( struct rc80211_ctx *ctx );
+
+#endif /* _GPXE_RC80211_H */
index 88bdd55..63f357d 100644 (file)
@@ -20,7 +20,6 @@
 
 FILE_LICENCE ( GPL2_OR_LATER );
 
-#include <stdio.h>
 #include <string.h>
 #include <byteswap.h>
 #include <stdlib.h>
@@ -183,7 +182,6 @@ net80211_marshal_request_info ( struct net80211_device *dev,
 
 static void net80211_step_associate ( struct process *proc );
 static void net80211_set_rtscts_rate ( struct net80211_device *dev );
-static void net80211_set_rate_intelligently ( struct net80211_device *dev );
 static void net80211_handle_auth ( struct net80211_device *dev,
                                   struct io_buffer *iob );
 static void net80211_handle_assoc_reply ( struct net80211_device *dev,
@@ -396,7 +394,7 @@ static inline int net80211_rate_is_erp ( u16 rate )
 static u16 net80211_duration ( struct net80211_device *dev, int bytes )
 {
        struct net80211_channel *chan = &dev->channels[dev->channel];
-       u16 rate = NET80211_RATE_VALUE ( dev->rates[dev->rate] );
+       u16 rate = dev->rates[dev->rate];
        u32 kbps = rate * 100;
 
        if ( chan->band == NET80211_BAND_5GHZ || net80211_rate_is_erp ( rate ) ) {
@@ -784,6 +782,7 @@ void net80211_unregister ( struct net80211_device *dev )
 void net80211_free ( struct net80211_device *dev )
 {
        free ( dev->hw );
+       free ( dev->rctl );
        netdev_nullify ( dev->netdev );
        netdev_put ( dev->netdev );
 }
@@ -932,7 +931,7 @@ static int net80211_process_capab ( struct net80211_device *dev,
 static int net80211_process_ie ( struct net80211_device *dev,
                                 union ieee80211_ie *ie, void *ie_end )
 {
-       u16 old_rate = NET80211_RATE_VALUE ( dev->rates[dev->rate] );
+       u16 old_rate = dev->rates[dev->rate];
        u16 old_phy = dev->phy_flags;
        int have_rates = 0, i;
        int ds_channel = 0;
@@ -1025,7 +1024,7 @@ static int net80211_process_ie ( struct net80211_device *dev,
                        int ok = 0;
                        for ( j = 0; j < dev->hw->nr_supported_rates; j++ ) {
                                if ( dev->hw->supported_rates[j] ==
-                                    NET80211_RATE_VALUE ( dev->rates[i] ) ) {
+                                    dev->rates[i] ) {
                                        ok = 1;
                                        break;
                                }
@@ -1042,6 +1041,16 @@ static int net80211_process_ie ( struct net80211_device *dev,
 
                dev->nr_rates -= delta;
 
+               /* Sort available rates - sorted subclumps tend to already
+                  exist, so insertion sort works well. */
+               for ( i = 1; i < dev->nr_rates; i++ ) {
+                       u16 rate = dev->rates[i];
+
+                       for ( j = i - 1; j >= 0 && dev->rates[j] >= rate; j-- )
+                               dev->rates[j + 1] = dev->rates[j];
+                       dev->rates[j + 1] = rate;
+               }
+
                net80211_set_rtscts_rate ( dev );
 
                if ( dev->rates[dev->rate] != old_rate )
@@ -1084,7 +1093,7 @@ net80211_marshal_request_info ( struct net80211_device *dev,
        ie->id = IEEE80211_IE_RATES;
        ie->len = dev->nr_rates;
        for ( i = 0; i < ie->len; i++ ) {
-               ie->rates[i] = NET80211_RATE_VALUE ( dev->rates[i] ) / 5;
+               ie->rates[i] = dev->rates[i] / 5;
                if ( dev->basic_rates & ( 1 << i ) )
                        ie->rates[i] |= 0x80;
        }
@@ -1542,6 +1551,12 @@ static void net80211_step_associate ( struct process *proc )
                        goto fail;
                }
 
+               /* If we probed using a broadcast SSID, record that
+                  fact for the settings applicator before we clobber
+                  it with the specific SSID we've chosen. */
+               if ( ! dev->essid[0] )
+                       dev->state |= NET80211_AUTO_SSID;
+
                DBGC ( dev, "802.11 %p found network %s (%s)\n", dev,
                       dev->associating->essid,
                       eth_ntoa ( dev->associating->bssid ) );
@@ -1626,6 +1641,8 @@ static void net80211_step_associate ( struct process *proc )
        net80211_free_wlan ( dev->associating );
        dev->associating = NULL;
 
+       dev->rctl = rc80211_init ( dev );
+
        process_del ( proc );
 
        DBGC ( dev, "802.11 %p associated with %s (%s)\n", dev,
@@ -1671,10 +1688,10 @@ int net80211_check_ssid_update ( void )
                                      IEEE80211_MAX_SSID_LEN );
                ssid[len] = 0;
 
-               if ( strcmp ( ssid, dev->essid ) != 0 ) {
+               if ( strcmp ( ssid, dev->essid ) != 0 &&
+                    ! ( ! ssid[0] && ( dev->state & NET80211_AUTO_SSID ) ) ) {
                        DBGC ( dev, "802.11 %p updating association: "
                               "%s -> %s\n", dev, dev->essid, ssid );
-                       net80211_set_state ( dev, NET80211_PROBED, 0, 0 );
                        net80211_autoassociate ( dev );
                }
        }
@@ -1707,7 +1724,7 @@ void net80211_autoassociate ( struct net80211_device *dev )
        dev->essid[len] = 0;
        dev->ctx.probe = NULL;
        dev->associating = NULL;
-       net80211_set_state ( dev, NET80211_ASSOCIATED, NET80211_WORKING, 0 );
+       net80211_set_state ( dev, NET80211_PROBED, NET80211_WORKING, 0 );
 }
 
 /**
@@ -1720,13 +1737,13 @@ void net80211_autoassociate ( struct net80211_device *dev )
  */
 static void net80211_set_rtscts_rate ( struct net80211_device *dev )
 {
-       u16 datarate = NET80211_RATE_VALUE ( dev->rates[dev->rate] );
+       u16 datarate = dev->rates[dev->rate];
        u16 rtsrate = 0;
        int rts_idx = -1;
        int i;
 
        for ( i = 0; i < dev->nr_rates; i++ ) {
-               u16 rate = NET80211_RATE_VALUE ( dev->rates[i] );
+               u16 rate = dev->rates[i];
 
                if ( ! ( dev->basic_rates & ( 1 << i ) ) || rate > datarate )
                        continue;
@@ -1746,42 +1763,22 @@ static void net80211_set_rtscts_rate ( struct net80211_device *dev )
 }
 
 /**
- * Pick TX rate from the rate list we have
+ * Set data transmission rate for 802.11 device
  *
  * @v dev      802.11 device
- *
- * This needs to be expanded into an algorithm that adapts to large
- * numbers of dropped packets by lowering the rate, and tries raising
- * the rate if we've been running well for a while at a lower one.
+ * @v rate     Rate to set, as index into @c dev->rates array
  */
-static void net80211_set_rate_intelligently ( struct net80211_device *dev )
+void net80211_set_rate_idx ( struct net80211_device *dev, int rate )
 {
-       int i, oldrate = dev->rate;
-
-       if ( dev->nr_rates == 0 ) {
-               for ( i = 0; i < dev->hw->nr_supported_rates; i++ ) {
-                       u16 rate = dev->hw->supported_rates[i];
-                       dev->rates[dev->nr_rates++] = rate;
-               }
-               oldrate = -1;   /* always reconfigure */
-       }
-
-       /* For now, stick with something safe: the last (probably
-          fastest) 802.11b-compatible rate. */
-
-       dev->rate = dev->nr_rates;
-       for ( i = 0; i < dev->nr_rates; i++ ) {
-               if ( net80211_rate_is_erp ( dev->rates[i] ) )
-                       continue;
-               dev->rate = i;
-               break;
-       }
-
-       if ( dev->rate == dev->nr_rates ) /* no non-ERP rates */
-               dev->rate = 0;  /* first ERP rate */
+       if ( rate >= 0 && rate < dev->nr_rates && rate != dev->rate ) {
+               DBGC2 ( dev, "802.11 %p changing rate from %d->%d Mbps\n",
+                       dev, dev->rates[dev->rate] / 10,
+                       dev->rates[rate] / 10 );
 
-       if ( dev->rate != oldrate )
+               dev->rate = rate;
+               net80211_set_rtscts_rate ( dev );
                dev->op->config ( dev, NET80211_CFG_RATE );
+       }
 }
 
 /**
@@ -1848,11 +1845,15 @@ int net80211_prepare_probe ( struct net80211_device *dev, int band,
                                                NET80211_REG_TXPOWER );
        }
 
+       /* Use channel 1 for now */
        dev->channel = 0;
        dev->op->config ( dev, NET80211_CFG_CHANNEL );
 
-       dev->nr_rates = 0;
-       net80211_set_rate_intelligently ( dev );
+       /* Always do active probes at 1Mbps */
+       dev->rate = 0;
+       dev->nr_rates = 1;
+       dev->rates[0] = 10;
+       dev->op->config ( dev, NET80211_CFG_RATE );
 
        return 0;
 }
@@ -1892,7 +1893,9 @@ int net80211_prepare_assoc ( struct net80211_device *dev,
        if ( rc )
                return rc;
 
-       net80211_set_rate_intelligently ( dev );
+       /* Associate at the lowest rate so we know it'll get through */
+       dev->rate = 0;
+       dev->op->config ( dev, NET80211_CFG_RATE );
 
        return 0;
 }
@@ -2322,7 +2325,7 @@ static void net80211_rx_frag ( struct net80211_device *dev,
                                    net80211_accum_frags ( dev, i, fragnr,
                                                           size );
                                net80211_free_frags ( dev, i );
-                               net80211_rx ( dev, niob, signal );
+                               net80211_rx ( dev, niob, signal, 0 );
                        } else {
                                DBGC ( dev, "802.11 %p dropping fragmented "
                                       "packet due to out-of-order arrival, "
@@ -2340,9 +2343,12 @@ static void net80211_rx_frag ( struct net80211_device *dev,
  * @v dev      802.11 device
  * @v iob      I/O buffer
  * @v signal   Received signal strength
+ * @v rate     Bitrate at which frame was received, in 100 kbps units
+ *
+ * If the rate or signal is unknown, 0 should be passed.
  */
 void net80211_rx ( struct net80211_device *dev, struct io_buffer *iob,
-                  int signal )
+                  int signal, u16 rate )
 {
        struct ieee80211_frame *hdr = iob->data;
        u16 type = hdr->fc & IEEE80211_FC_TYPE;
@@ -2393,14 +2399,11 @@ void net80211_rx ( struct net80211_device *dev, struct io_buffer *iob,
        if ( ( hdr->fc & IEEE80211_FC_SUBTYPE ) != IEEE80211_STYPE_DATA )
                goto drop;      /* drop QoS, CFP, or null data packets */
 
-       if ( hdr->fc & IEEE80211_FC_RETRY ) {
-               DBGCP ( dev, "802.11 %p rx RETX packet %04x\n",
-                       dev, hdr->seq );
-       } else {
-               DBGCP ( dev, "802.11 %p rx ok   packet %04x\n",
-                       dev, hdr->seq );
-       }
+       /* Update rate-control algorithm */
+       if ( dev->rctl )
+               rc80211_update_rx ( dev, hdr->fc & IEEE80211_FC_RETRY, rate );
 
+       /* Pass packet onward */
        if ( netdev_link_ok ( dev->netdev ) ) {
                netdev_rx ( dev->netdev, iob );
                return;
@@ -2425,7 +2428,6 @@ void net80211_rx ( struct net80211_device *dev, struct io_buffer *iob,
 void net80211_rx_err ( struct net80211_device *dev,
                       struct io_buffer *iob, int rc )
 {
-       DBGCP ( dev, "802.11 %p rx FAIL\n", dev );
        netdev_rx_err ( dev->netdev, iob, rc );
 }
 
@@ -2437,7 +2439,8 @@ void net80211_rx_err ( struct net80211_device *dev,
  * @v rc       Error code, or 0 for success
  *
  * This logs an error with the wrapping net_device if one occurred,
- * and removes and frees the I/O buffer from its TX queue.
+ * and removes and frees the I/O buffer from its TX queue. The
+ * provided retry information is used to tune our transmission rate.
  *
  * If the packet did not need to be retransmitted because it was
  * properly ACKed the first time, @a retries should be 0.
@@ -2445,20 +2448,10 @@ void net80211_rx_err ( struct net80211_device *dev,
 void net80211_tx_complete ( struct net80211_device *dev,
                            struct io_buffer *iob, int retries, int rc )
 {
-       if ( retries ) {
-               if ( rc ) {
-                       DBGCP ( dev, "802.11 %p tx FAIL after %d retx\n", dev,
-                               retries );
-               } else {
-                       DBGCP ( dev, "802.11 %p tx RETX %d times\n", dev,
-                               retries );
-               }
-       } else {
-               if ( rc ) {
-                       DBGCP ( dev, "802.11 %p tx FAIL outright\n", dev );
-               } else {
-                       DBGCP ( dev, "802.11 %p tx ok\n", dev );
-               }
-       }
+       /* Update rate-control algorithm */
+       if ( dev->rctl )
+               rc80211_update_tx ( dev, retries, rc );
+
+       /* Pass completion onward */
        netdev_tx_complete_err ( dev->netdev, iob, rc );
 }
diff --git a/src/net/rc80211.c b/src/net/rc80211.c
new file mode 100644 (file)
index 0000000..7a16638
--- /dev/null
@@ -0,0 +1,276 @@
+/*
+ * Simple 802.11 rate-control algorithm for gPXE.
+ *
+ * Copyright (c) 2009 Joshua Oreman <oremanj@rwcr.net>.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ */
+
+FILE_LICENCE ( GPL2_OR_LATER );
+
+#include <stdlib.h>
+#include <gpxe/net80211.h>
+
+/*
+ * Rate control philosophy:
+ *
+ * We want to maximize our transmission speed, to the extent that we
+ * can do that without dropping undue numbers of packets. We also
+ * don't want to take up very much code space, so our algorithm has to
+ * be pretty simple
+ *
+ * When we receive a packet, we know what rate it was transmitted at,
+ * and whether it had to be retransmitted to get to us.
+ *
+ * When we send a packet, we hear back how many times it had to be
+ * retried to get through, and whether it got through at all.
+ *
+ * Indications of TX success are more reliable than RX success, but RX
+ * information helps us know where to start.
+ *
+ * To handle all of this, we keep for each rate and each direction (TX
+ * and RX separately) some "goodness" information for the most recent
+ * packets on that rate and the number of packets for which we have
+ * information. The "goodness" indicator is a 32-bit unsigned integer
+ * in which two bits represent a packet: 11 if it went through well,
+ * 10 if it went through with one retry, 01 if it went through with
+ * more than one retry, or 00 if it didn't go through at all. The
+ * goodness is the sum of all the 2-bit fields divided by the number
+ * of them that contain valid data (eventually 16, but less when we're
+ * starting out). It's measured as a percent.
+ *
+ * In deciding which rates are best, we find the weighted average of
+ * TX and RX goodness, where the weighting is by number of packets
+ * with data and TX packets are worth 4 times as much as RX packets.
+ * If 3 consecutive packets fail transmission outright, we
+ * automatically ratchet down the rate; otherwise, we switch to the
+ * best rate whenever the current rate's goodness falls below some
+ * threshold, and try increasing our rate when the goodness is really
+ * high.
+ *
+ * This system is optimized for gPXE's style of usage. Because normal
+ * operation always involves receiving something, we'll make our way
+ * to the best rate pretty quickly. We tend to follow the lead of the
+ * sending AP in choosing rates, but we won't use rates for long that
+ * have asymmetry properties in the current environment. We assume
+ * gPXE won't be running for long enough that rate patterns will
+ * change much, so we don't have to keep time counters or the like.
+ * And if this doesn't work well in practice there are many ways it
+ * could be tweaked.
+ *
+ * To avoid staying at 1Mbps for a long time, we don't track any
+ * transmitted packets until we've set our rate based on received
+ * packets. 
+ */
+
+#define RC_PKT_OK              0x3
+#define RC_PKT_RETRIED_ONCE    0x2
+#define RC_PKT_RETRIED_MULTI   0x1
+#define RC_PKT_FAILED          0x0
+
+#define RC_TX_FACTOR           4
+#define RC_TX_EMERG_FAIL       3
+
+#define RC_GOODNESS_MIN                85
+#define RC_GOODNESS_MAX                95
+
+#define RC_UNCERTAINTY_THRESH  4
+
+#define TX     0
+#define RX     1
+
+/** A rate control context */
+struct rc80211_ctx 
+{
+       /** Goodness state for each rate, TX and RX */
+       u32 goodness[2][NET80211_MAX_RATES];
+
+       /** Number of packets recorded for each rate */
+       u8 count[2][NET80211_MAX_RATES];
+
+       /** Indication of whether we've set the device rate yet */
+       int started;
+
+       /** Counter of all packets sent and received */
+       int packets;
+};
+
+struct rc80211_ctx * rc80211_init ( struct net80211_device *dev __unused )
+{
+       struct rc80211_ctx *ret = zalloc ( sizeof ( *ret ) );
+       return ret;
+}
+
+static int rc80211_calc_net_goodness ( struct rc80211_ctx *ctx,
+                                      int rate_idx )
+{
+       int sum[2], num[2], dir, pkt;
+
+       for ( dir = 0; dir < 2; dir++ ) {
+               u32 good = ctx->goodness[dir][rate_idx];
+
+               num[dir] = ctx->count[dir][rate_idx];
+               sum[dir] = 0;
+
+               for ( pkt = 0; pkt < num[dir]; pkt++ )
+                       sum[dir] += ( good >> ( 2 * pkt ) ) & 0x3;
+       }
+
+       if ( ( num[TX] * RC_TX_FACTOR + num[RX] ) < RC_UNCERTAINTY_THRESH )
+               return -1;
+
+       return ( 33 * ( sum[TX] * RC_TX_FACTOR + sum[RX] ) /
+                     ( num[TX] * RC_TX_FACTOR + num[RX] ) );
+}
+
+/* rc80211_pick_best => set 'started' */
+
+static int rc80211_pick_best ( struct net80211_device *dev )
+{
+       struct rc80211_ctx *ctx = dev->rctl;
+       int best_net_good = 0, best_rate = -1, i;
+
+       for ( i = 0; i < dev->nr_rates; i++ ) {
+               int net_good = rc80211_calc_net_goodness ( ctx, i );
+
+               if ( net_good > best_net_good ||
+                    ( best_net_good > RC_GOODNESS_MIN &&
+                      net_good > RC_GOODNESS_MIN ) ) {
+                       best_net_good = net_good;
+                       best_rate = i;
+               }
+       }
+
+       if ( best_rate >= 0 ) {
+               int old_good = rc80211_calc_net_goodness ( ctx, dev->rate );
+               if ( old_good != best_net_good )
+                       DBGC ( ctx, "802.11 RC %p switching from goodness "
+                              "%d to %d\n", ctx, old_good, best_net_good );
+
+               ctx->started = 1;
+               return best_rate;
+       }
+
+       return dev->rate;
+}
+
+static inline void rc80211_set_rate ( struct net80211_device *dev,
+                                     int rate )
+{
+       DBGC ( dev->rctl, "802.11 RC %p changing rate %d->%d Mbps\n", dev->rctl,
+              dev->rates[dev->rate] / 10, dev->rates[rate] / 10 );
+
+       net80211_set_rate_idx ( dev, rate );
+}
+
+static void rc80211_maybe_set_new ( struct net80211_device *dev )
+{
+       struct rc80211_ctx *ctx = dev->rctl;
+       int net_good;
+
+       net_good = rc80211_calc_net_goodness ( ctx, dev->rate );
+
+       if ( ! ctx->started ) {
+               rc80211_set_rate ( dev, rc80211_pick_best ( dev ) );
+               return;
+       }
+
+       if ( net_good < 0 )     /* insufficient data */
+               return;
+
+       if ( net_good > RC_GOODNESS_MAX && dev->rate + 1 < dev->nr_rates ) {
+               int higher = rc80211_calc_net_goodness ( ctx, dev->rate + 1 );
+               if ( higher > net_good || higher < 0 )
+                       rc80211_set_rate ( dev, dev->rate + 1 );
+               else
+                       rc80211_set_rate ( dev, rc80211_pick_best ( dev ) );
+       }
+
+       if ( net_good < RC_GOODNESS_MIN ) {
+               rc80211_set_rate ( dev, rc80211_pick_best ( dev ) );
+       }
+}
+
+static void rc80211_update ( struct net80211_device *dev, int direction,
+                            int rate_idx, int retries, int failed ) 
+{
+       struct rc80211_ctx *ctx = dev->rctl;
+       u32 goodness = ctx->goodness[direction][rate_idx];
+
+       if ( ctx->count[direction][rate_idx] < 16 )
+               ctx->count[direction][rate_idx]++;
+
+       goodness <<= 2;
+       if ( failed )
+               goodness |= RC_PKT_FAILED;
+       else if ( retries > 1 )
+               goodness |= RC_PKT_RETRIED_MULTI;
+       else if ( retries )
+               goodness |= RC_PKT_RETRIED_ONCE;
+       else
+               goodness |= RC_PKT_OK;
+
+       ctx->goodness[direction][rate_idx] = goodness;
+
+       ctx->packets++;
+
+       rc80211_maybe_set_new ( dev );
+}
+
+void rc80211_update_tx ( struct net80211_device *dev, int retries, int rc )
+{
+       struct rc80211_ctx *ctx = dev->rctl;
+
+       if ( ! ctx->started )
+               return;
+
+       rc80211_update ( dev, TX, dev->rate, retries, rc );
+
+       /* Check if the last RC_TX_EMERG_FAIL packets have all failed */
+       if ( ! ( ctx->goodness[TX][dev->rate] &
+                ( ( 1 << ( 2 * RC_TX_EMERG_FAIL ) ) - 1 ) ) ) {
+               if ( dev->rate == 0 )
+                       DBGC ( dev->rctl, "802.11 RC %p saw %d consecutive "
+                              "failed TX, but cannot lower rate any further\n",
+                              dev->rctl, RC_TX_EMERG_FAIL );
+               else {
+                       DBGC ( dev->rctl, "802.11 RC %p lowering rate (%d->%d "
+                              "Mbps) due to %d consecutive TX failures\n",
+                              dev->rctl, dev->rates[dev->rate] / 10,
+                              dev->rates[dev->rate - 1] / 10,
+                              RC_TX_EMERG_FAIL );
+
+                       rc80211_set_rate ( dev, dev->rate - 1 );
+               }
+       }
+}
+
+void rc80211_update_rx ( struct net80211_device *dev, int retry, u16 rate )
+{
+       int ridx;
+
+       for ( ridx = 0; ridx < dev->nr_rates && dev->rates[ridx] != rate;
+             ridx++ )
+               ;
+       if ( ridx >= dev->nr_rates )
+               return;         /* couldn't find the rate */
+
+       rc80211_update ( dev, RX, ridx, retry, 0 );
+}
+
+void rc80211_free ( struct rc80211_ctx *ctx )
+{
+       free ( ctx );
+}