minstrel.c

最新之atheros芯片driver source code, 基于linux操作系统,內含atheros芯片HAL全部代码

/*-
 * 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
 * approach. Wander around the different rates, singing wherever 
 * you can. And then, look at the performance, 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 "if_ath_hal.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("%s: " _fmt, SC_DEV_NAME(sc), __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"
#if 0
static char *version = "1.2 (" RELEASE_VERSION ")";
#endif
static char *dev_info = "ath_rate_minstrel";

#define STALE_FAILURE_TIMEOUT_MS 10000
#define ENABLE_MRR 1

/* Interval (in ms) between successive rate statistics, default to 100 ms. */
static int ath_timer_interval = 100;

/* 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 = 0, cts = 0;
		int cw = ATH_DEFAULT_CWMIN;

		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:
#if 0
			t_slot = 9;
			t_sifs = 16;
			t_difs = 28;
			/* fall through */
#endif
		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;
		}

		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(ATH_DEFAULT_CWMAX, (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, unsigned 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 " MAC_FMT "?\n",
			           dev_info,
			           MAC_ADDR(an->an_node.ni_macaddr));
			    return;
		}

		mrr = sc->sc_mrretry &&
			!(ic->ic_flags & IEEE80211_F_USEPROT) &&
			ENABLE_MRR;

		if (sn->static_rate_ndx >= 0) {
			    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->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];

				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)