minstrel.c

madwifi driver, linux system

/*-
 * Copyright (c) 2005 John Bicket
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer,
 *    without modification.
 * 2. Redistributions in binary form must reproduce at minimum a disclaimer
 *    similar to the "NO WARRANTY" disclaimer below ("Disclaimer") and any
 *    redistribution must be conditioned upon including a substantially
 *    similar Disclaimer requirement for further binary redistribution.
 * 3. Neither the names of the above-listed copyright holders nor the names
 *    of any contributors may be used to endorse or promote products derived
 *    from this software without specific prior written permission.
 *
 * Alternatively, this software may be distributed under the terms of the
 * GNU General Public License ("GPL") version 2 as published by the Free
 * Software Foundation.
 *
 * NO WARRANTY
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF NONINFRINGEMENT, MERCHANTIBILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
 * THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY,
 * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
 * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
 * THE POSSIBILITY OF SUCH DAMAGES.
 *
 * $Id: minstrel.c 1525 2006-04-23 21:05:57Z dyqith $
 */

/* And then Indranet Technologies Ltd sponsored Derek Smithies to work
 * on this code. Derek Smithies ([e-mail]) took parts of the 
 * adm module and pasted it into this code base. 
 *
 * This version of John Bicket's code takes the experimental approach one
 * step further.
 * When in auto rate mode, packets are sent at the selected rate.
 * The Hal asks for what alternative rate to use if the selected rate fails.
 * We provide the alternative rate from a random selection of 1.. max rate.
 * Given the probability of success, multiplied with the transmission time,
 * we can determine the rate which maximises packet throughput.
 *
 * Different rates are used for every remote node - some nodes will work 
 * better on different rates.
 * Every second, a timer fires, to assess the throughput at each rate with 
 * each remote node.
 * This timer will then determine the optimum rate for each remote node, based
 * on the performance figures.
 *
 * This code is called minstrel, because we have taken a wandering minstrel
 * apporoch. Wander around the different rates, singing wherever 
 * you can. And then, look at the performacnce, and make a choice.
 *
 * It is not an aimless search, there is some direction to the search
 * pattern. But then, the minstels of old only sung where they thought
 * they would get an income. Similarily, we direct thesearch a little.
 *
 *  Enjoy.  Derek Smithies. */

/* This file is an implementation of the SampleRate algorithm
 * in "Bit-rate Selection in Wireless Networks"
 * (http://www.pdos.lcs.mit.edu/papers/jbicket-ms.ps)
 *
 * SampleRate chooses the bit-rate it predicts will provide the most
 * throughput based on estimates of the expected per-packet
 * transmission time for each bit-rate.  SampleRate periodically sends
 * packets at bit-rates other than the current one to estimate when
 * another bit-rate will provide better performance. SampleRate
 * switches to another bit-rate when its estimated per-packet
 * transmission time becomes smaller than the current bit-rate's.
 * SampleRate reduces the number of bit-rates it must sample by
 * eliminating those that could not perform better than the one
 * currently being used.  SampleRate also stops probing at a bit-rate
 * if it experiences several successive losses.
 *
 * The difference between the algorithm in the thesis and the one in this
 * file is that the one in this file uses an EWMA instead of a window.
 *
 * Also, this implementation tracks the average transmission time for
 * a few different packet sizes independently for each link. */

#ifndef AUTOCONF_INCLUDED
#include <linux/config.h>
#endif

#include <linux/version.h>
#include <linux/module.h>
#include <linux/init.h>
#include <linux/skbuff.h>
#include <linux/netdevice.h>
#include <linux/random.h>
#include <linux/delay.h>
#include <linux/cache.h>
#include <linux/sysctl.h>
#include <linux/proc_fs.h>
#include <linux/if_arp.h>
#include <linux/net.h>		/* for net_random */
#include <linux/vmalloc.h>

#include <asm/uaccess.h>

#include <net80211/if_media.h>
#include <net80211/ieee80211_var.h>
#include <net80211/ieee80211_rate.h>

#include "if_athvar.h"
#include "ah_desc.h"

#include "minstrel.h"

#define MINSTREL_DEBUG
#ifdef MINSTREL_DEBUG
enum {
	ATH_DEBUG_RATE		= 0x00000010	/* rate control */
};
#define DPRINTF(sc, _fmt, ...) do {		\
	if (sc->sc_debug & ATH_DEBUG_RATE)	\
		printk(_fmt, __VA_ARGS__);	\
} while(0)
#else
#define	DPRINTF(sc, _fmt, ...)
#endif

#define ONE_SECOND (1000 * 1000)  /* 1 second, or 1000 milliseconds, eternity in other words */

#include "release.h"

static char *version = "1.2 (" RELEASE_VERSION ")";
static char *dev_info = "ath_rate_minstrel";

#define STALE_FAILURE_TIMEOUT_MS 10000
#define ENABLE_MRR 1

static int ath_timer_interval = (1000 / 10); /* every 1/10 second, timer runs */
static void ath_timer_function(unsigned long data);

/* 10% of the time, send a packet at something other than the optimal rate, which fills
 * the statistics tables nicely. This percentage is applied to the first packet of the
 * multi rate retry chain. */
static int ath_lookaround_rate = 10;
static int ath_ewma_level      = 75;
static int ath_segment_size    = 6000;
static void ath_rate_ctl_reset(struct ath_softc *, struct ieee80211_node *);

/* Calculate the throughput and probability of success for each node
 * we are talking on, based on the statistics collected during the
 * last timer period. */
static void ath_rate_statistics(void *arg, struct ieee80211_node *ni);


#if (LINUX_VERSION_CODE < KERNEL_VERSION(2,5,52))
MODULE_PARM(ath_lookaround_rate, "i");
MODULE_PARM(ath_ewma_level, "i");
MODULE_PARM(ath_segment_size, "i");
#else
#include <linux/moduleparam.h>
module_param(ath_lookaround_rate, 	int, 0600);
module_param(ath_ewma_level, 		int, 0600);
module_param(ath_segment_size, 		int, 0600);
#endif
MODULE_PARM_DESC(ath_lookaround_rate, " % of packets sent to fill statistics table (10) ");
MODULE_PARM_DESC(ath_ewma_level, " scaling % used in ewma rolloff calculations  (75) ");
MODULE_PARM_DESC(ath_segment_size, " max duration of time to spend in either of the first two mrr segments (6000)");


static __inline int 
rate_to_ndx(struct minstrel_node *sn, int rate)
{
	unsigned int x = 0;
	for (x = 0; x < sn->num_rates; x++)
		if (sn->rates[x].rate == rate)
			return x;
	return -1;
}

/* Calculate the transmit duration of a frame. */
static unsigned
calc_usecs_unicast_packet(struct ath_softc *sc, int length, 
	int rix, int short_retries, int long_retries)
{
	const HAL_RATE_TABLE *rt = sc->sc_currates;
	struct ieee80211com *ic = &sc->sc_ic;
	unsigned t_slot = 20;
	unsigned t_difs = 50; 
	unsigned t_sifs = 10; 
	unsigned int x = 0, tt = 0;
	unsigned int cix = rt->info[rix].controlRate;
	int rts, cts;
	int cw = WIFI_CW_MIN;

	KASSERT(rt != NULL, ("no rate table, mode %u", sc->sc_curmode));

	if (!rt->info[rix].rateKbps) {
		printk(KERN_WARNING "rix %d (%d) bad ratekbps %d mode %u\n",
		       rix, rt->info[rix].dot11Rate,
		       rt->info[rix].rateKbps,
		       sc->sc_curmode);
		return 0;
	}
	
	/* XXX getting MAC/PHY level timings should be fixed for turbo
	 * rates, and there is probably a way to get this from the
	 * HAL... */
	switch (rt->info[rix].phy) {
	case IEEE80211_T_OFDM:
		t_slot = 9;
		t_sifs = 16;
		t_difs = 28;
		/* fall through */
		/* XXX: WTF? */
	case IEEE80211_T_TURBO:
		t_slot = 9;
		t_sifs = 8;
		t_difs = 28;
		break;
	case IEEE80211_T_DS:
		/* fall through to default */
	default:
		/* pg 205 ieee.802.11.pdf */
		t_slot = 20;
		t_difs = 50;
		t_sifs = 10;
	}

	rts = cts = 0;

	if ((ic->ic_flags & IEEE80211_F_USEPROT) &&
	    rt->info[rix].phy == IEEE80211_T_OFDM) {
		if (ic->ic_protmode == IEEE80211_PROT_RTSCTS)
			rts = 1;
		else if (ic->ic_protmode == IEEE80211_PROT_CTSONLY)
			cts = 1;

		cix = rt->info[sc->sc_protrix].controlRate;
	}

#if 0
	if (length > ic->ic_rtsthreshold)
		rts = 1;
#endif

	if (rts || cts) {
		int ctsrate = rt->info[cix].rateCode;
		int ctsduration = 0;

		if (!rt->info[cix].rateKbps) {
#if 0
			printk(KERN_WARNING "cix %d (%d) bad ratekbps %d mode %u\n",
			       cix, rt->info[cix].dot11Rate,
			       rt->info[cix].rateKbps,
			       sc->sc_curmode);
#endif
			return 0;
		}
		

		ctsrate |= rt->info[cix].shortPreamble;
		if (rts)	/* SIFS + CTS */
			ctsduration += rt->info[cix].spAckDuration;

		ctsduration += ath_hal_computetxtime(sc->sc_ah,
						     rt, length, rix, AH_TRUE);

		if (cts)	/* SIFS + ACK */
			ctsduration += rt->info[cix].spAckDuration;

		tt += (short_retries + 1) * ctsduration;
	}
	tt += t_difs;
	tt += (long_retries + 1) * (t_sifs + rt->info[rix].spAckDuration);
	tt += (long_retries + 1) * ath_hal_computetxtime(sc->sc_ah, rt, length, 
						rix, AH_TRUE);
	for (x = 0; x <= short_retries + long_retries; x++) {
		cw = MIN(WIFI_CW_MAX, (cw + 1) * 2);
		tt += (t_slot * cw / 2);
	}
	return tt;
}

static void
ath_rate_node_init(struct ath_softc *sc, struct ath_node *an)
{
	/* NB: assumed to be zero'd by caller */
	ath_rate_ctl_reset(sc, &an->an_node);
}


static void
ath_rate_node_cleanup(struct ath_softc *sc, struct ath_node *an)
{
}

#if 0
static void
ath_rate_node_copy(struct ath_softc *sc,
	struct ath_node *dst, const struct ath_node *src)
{
	struct minstrel_node *odst = ATH_NODE_MINSTREL(dst);
	const struct minstrel_node *osrc = (const struct minstrel_node *)&src[1];
	memcpy(odst, osrc, sizeof(struct minstrel_node));
}
#endif

static void
ath_rate_findrate(struct ath_softc *sc, struct ath_node *an,
        int shortPreamble, size_t frameLen,
        u_int8_t *rix, int *try0, u_int8_t *txrate)
{
        struct minstrel_node *sn = ATH_NODE_MINSTREL(an);
        struct ieee80211com *ic = &sc->sc_ic;
        unsigned int ndx, offset;
	int mrr;

        if (sn->num_rates <= 0) {
                printk(KERN_WARNING "%s: no rates for %s?\n",
                       dev_info,
                       ether_sprintf(an->an_node.ni_macaddr));
                return;
        }
  
        mrr = sc->sc_mrretry && !(ic->ic_flags & IEEE80211_F_USEPROT) && ENABLE_MRR;

        if (sn->static_rate_ndx != -1) {
                ndx = sn->static_rate_ndx;
        } else {
		sn->packet_count++;
		sn->random_n = (sn->a*sn->random_n) + sn->b;
		offset = sn->random_n & 0xf;
		if ((((100 * sn->sample_count)/(sn->sample_count + sn->packet_count)) < ath_lookaround_rate) && (offset < 2)) {
			sn->sample_count++;
			sn->is_sampling = 1;
			if (sn->packet_count >= (10000)) {
				sn->sample_count = 0;
				sn->packet_count = 0;
			}				

			/* Don't look for slowest rate (i.e. slowest
			 * base rate) We must presume that the slowest
			 * rate works fine, or else other management
			 * frames will also be failing - therefore the
			 * link will soon be broken anyway. Indeed,
			 * the slowest rate was used to establish the
			 * link in the first place. */
			ndx = sn->rs_sampleTable[sn->rs_sampleIndex][sn->rs_sampleColumn];
			if (ndx >= sn->num_rates)
			    ndx = 1;
			sn->rs_sampleIndex++;
			if (sn->rs_sampleIndex > (sn->num_rates - 2)) {
				sn->rs_sampleIndex = 0;
				sn->rs_sampleColumn++;
				if (sn->rs_sampleColumn == MINSTREL_COLUMNS)
					sn->rs_sampleColumn = 0;
			}
			sn->rs_sample_rate = ndx;
			sn->rs_sample_rate_slower =
				sn->perfect_tx_time[ndx] >  sn->perfect_tx_time[sn->max_tp_rate];
			if (sn->rs_sample_rate_slower)