path: root/sys/net80211/ieee80211_mira.c

/*	$OpenBSD: ieee80211_mira.c,v 1.8 2017/01/12 18:06:57 stsp Exp $	*/

/*
 * Copyright (c) 2016 Stefan Sperling <stsp@openbsd.org>
 * Copyright (c) 2016 Theo Buehler <tb@openbsd.org>
 * Copyright (c) 2006 Damien Bergamini <damien.bergamini@free.fr>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <sys/param.h>
#include <sys/systm.h>
#include <sys/socket.h>

#include <net/if.h>
#include <net/if_media.h>

#include <netinet/in.h>
#include <netinet/if_ether.h>

#include <net80211/ieee80211_var.h>
#include <net80211/ieee80211_mira.h>

/* Allow for aggressive down probing when channel quality changes. */
#define MIRA_AGGRESSIVE_DOWNWARDS_PROBING

const struct ieee80211_mira_rateset *	ieee80211_mira_get_rateset(int);
void	ieee80211_mira_probe_timeout_up(void *);
void	ieee80211_mira_probe_timeout_down(void *);
uint64_t ieee80211_mira_get_txrate(int);
uint16_t ieee80211_mira_legacy_txtime(uint32_t, int, struct ieee80211com *);
uint32_t ieee80211_mira_ht_txtime(uint32_t, int, int);
int	ieee80211_mira_best_basic_rate(struct ieee80211_node *);
int	ieee80211_mira_ack_rate(struct ieee80211_node *);
uint64_t ieee80211_mira_toverhead(struct ieee80211_mira_node *,
	    struct ieee80211com *, struct ieee80211_node *);
void	ieee80211_mira_update_stats(struct ieee80211_mira_node *,
	    struct ieee80211com *, struct ieee80211_node *);
void	ieee80211_mira_reset_goodput_stats(struct ieee80211_mira_node *);
void	ieee80211_mira_reset_driver_stats(struct ieee80211_mira_node *);
int	ieee80211_mira_next_lower_intra_rate(struct ieee80211_mira_node *,
	    struct ieee80211_node *);
int	ieee80211_mira_next_intra_rate(struct ieee80211_mira_node *,
	    struct ieee80211_node *);
const struct ieee80211_mira_rateset * ieee80211_mira_next_rateset(
		    struct ieee80211_mira_node *, int);
int	ieee80211_mira_best_mcs_in_rateset(struct ieee80211_mira_node *,
	    const struct ieee80211_mira_rateset *);
void	ieee80211_mira_probe_next_rateset(struct ieee80211_mira_node *,
	    struct ieee80211_node *, const struct ieee80211_mira_rateset *);
int	ieee80211_mira_next_mcs(struct ieee80211_mira_node *,
	    struct ieee80211_node *);
int	ieee80211_mira_prev_mcs(struct ieee80211_mira_node *,
	    struct ieee80211_node *);
int	ieee80211_mira_probe_valid(struct ieee80211_mira_node *,
	    struct ieee80211_node *);
int	ieee80211_mira_intra_mode_ra_finished(
	    struct ieee80211_mira_node *, struct ieee80211_node *);
void	ieee80211_mira_trigger_next_rateset(struct ieee80211_mira_node *mn,
	    struct ieee80211_node *);
int	ieee80211_mira_inter_mode_ra_finished(
	    struct ieee80211_mira_node *, struct ieee80211_node *);
int	ieee80211_mira_best_rate(struct ieee80211_mira_node *,
	    struct ieee80211_node *);
void	ieee80211_mira_update_probe_interval(struct ieee80211_mira_node *,
	    struct ieee80211_mira_goodput_stats *);
void	ieee80211_mira_schedule_probe_timers(struct ieee80211_mira_node *,
	    struct ieee80211_node *);
int	ieee80211_mira_check_probe_timers(struct ieee80211_mira_node *,
	    struct ieee80211_node *);
void	ieee80211_mira_probe_next_rate(struct ieee80211_mira_node *,
	    struct ieee80211_node *);
uint32_t ieee80211_mira_valid_rates(struct ieee80211com *,
	    struct ieee80211_node *);
uint32_t ieee80211_mira_mcs_below(struct ieee80211_mira_node *, int);

/* We use fixed point arithmetic with 64 bit integers. */
#define MIRA_FP_SHIFT	21
#define MIRA_FP_INT(x)	(x ## ULL << MIRA_FP_SHIFT) /* the integer x */
#define MIRA_FP_1	MIRA_FP_INT(1)

/* Multiply two fixed point numbers. */
#define MIRA_FP_MUL(a, b) \
	(((a) * (b)) >> MIRA_FP_SHIFT)

/* Divide two fixed point numbers. */
#define MIRA_FP_DIV(a, b) \
	(b == 0 ? (uint64_t)-1 : (((a) << MIRA_FP_SHIFT) / (b)))

#ifdef MIRA_DEBUG
#define DPRINTF(x)	do { if (mira_debug > 0) printf x; } while (0)
#define DPRINTFN(n, x)	do { if (mira_debug >= (n)) printf x; } while (0)
int mira_debug = 0;
#else
#define DPRINTF(x)	do { ; } while (0)
#define DPRINTFN(n, x)	do { ; } while (0)
#endif

#ifdef MIRA_DEBUG
void
mira_fixedp_split(uint32_t *i, uint32_t *f, uint64_t fp)
{
	uint64_t tmp;

	/* integer part */
	*i = (fp >> MIRA_FP_SHIFT);

 	/* fractional part */
	tmp = (fp & ((uint64_t)-1 >> (64 - MIRA_FP_SHIFT)));
	tmp *= 100;
	*f = (uint32_t)(tmp >> MIRA_FP_SHIFT);
}

char *
mira_fp_sprintf(uint64_t fp)
{
	uint32_t i, f;
	static char buf[64];
	int ret;

	mira_fixedp_split(&i, &f, fp);
	ret = snprintf(buf, sizeof(buf), "%u.%02u", i, f);
	if (ret == -1 || ret >= sizeof(buf))
		return "ERR";

	return buf;
}
#endif /* MIRA_DEBUG */

/*
 * Rate tables.
 */

/* Index into ieee80211_mira_ratesets[] array. */
#define IEEE80211_MIRA_RATESET_SISO	0
#define IEEE80211_MIRA_RATESET_MIMO2	1
#define IEEE80211_MIRA_RATESET_MIMO3	2
#define IEEE80211_MIRA_RATESET_MIMO4	3

#define IEEE80211_MIRA_RATESET_MAX 8 /* Maximum number of rates in a rateset. */
struct ieee80211_mira_rateset {
	uint32_t nrates;
	uint32_t rates[IEEE80211_MIRA_RATESET_MAX];
	uint32_t mcs_mask;
	int min_mcs;
	int max_mcs;
} ieee80211_mira_ratesets[] = {
/* XXX We only support MCS 0-31, for now. */
#ifdef notyet
	/* Legacy rates on a 2GHz channel. */
	{ 12, { 2, 4, 11, 22, 12, 18, 24, 36, 48, 72, 96, 108 }, 0x0, -1, -1 },

	/* Legacy rates on a 5GHz channel. */
	{ 8, { 12, 18, 24, 36, 48, 72, 96, 108 }, 0x0, -1, -1 },
#endif
	/* MCS 0-7, 20MHz channel, no SGI */
	{ 8, { 13, 26, 39, 52, 78, 104, 117, 130 }, 0x000000ff, 0, 7 },

	/* MCS 8-15, 20MHz channel, no SGI */
	{ 8, { 26, 52, 78, 104, 156, 208, 234, 260 }, 0x0000ff00, 8, 15 },

	/* MCS 16-23, 20MHz channel, no SGI */
	{ 8, { 39, 78, 117, 156, 234, 312, 351, 390  }, 0x00ff0000, 16, 23 },

	/* MCS 24-31, 20MHz channel, no SGI */
	{ 8, { 52, 104, 156, 208, 312, 416, 468, 520 }, 0xff000000, 24, 31 },
};

/* XXX We only support HT rates, for now. With legacy added, these differ. */
#define IEEE80211_MIRA_NUM_MCS	IEEE80211_MIRA_NUM_RATES

const struct ieee80211_mira_rateset *
ieee80211_mira_get_rateset(int mcs)
{
	const struct ieee80211_mira_rateset *rs;
	int i;

	for (i = 0; i < nitems(ieee80211_mira_ratesets); i++) {
		rs = &ieee80211_mira_ratesets[i];
		if (mcs >= rs->min_mcs && mcs <= rs->max_mcs)
			return rs;
	}

	panic("MCS %d is not part of any rateset", mcs);
}

/*
 * Probe timers.
 */

/* Constants related to timeouts for time-driven rate probing. */
#define IEEE80211_MIRA_PROBE_TIMEOUT_MIN	2		/* in msec */
#define IEEE80211_MIRA_PROBE_INTVAL_MAX		(1 << 10)	/* 2^10 */

void
ieee80211_mira_probe_timeout_up(void *arg)
{
	struct ieee80211_mira_node *mn = arg;
	int s;

	s = splnet();
	mn->probe_timer_expired[IEEE80211_MIRA_PROBE_TO_UP] = 1;
	DPRINTFN(3, ("probe up timeout fired\n"));
	splx(s);
}

void
ieee80211_mira_probe_timeout_down(void *arg)
{
	struct ieee80211_mira_node *mn = arg;
	int s;

	s = splnet();
	mn->probe_timer_expired[IEEE80211_MIRA_PROBE_TO_DOWN] = 1;
	DPRINTFN(3, ("probe down timeout fired\n"));
	splx(s);
}

/*
 * Update goodput statistics.
 */

uint64_t
ieee80211_mira_get_txrate(int mcs)
{
	const struct ieee80211_mira_rateset *rs;
	uint64_t txrate;

	rs = ieee80211_mira_get_rateset(mcs);
	txrate = rs->rates[mcs - rs->min_mcs];
	txrate <<= MIRA_FP_SHIFT; /* convert to fixed-point */
	txrate *= 500; /* convert to kbit/s */
	txrate /= 1000; /* convert to mbit/s */

	return txrate;
}

/* Based on rt2661_txtime in the ral(4) driver. */
uint16_t
ieee80211_mira_legacy_txtime(uint32_t len, int rate, struct ieee80211com *ic)
{
#define MIRA_RATE_IS_OFDM(rate) ((rate) >= 12 && (rate) != 22)
	uint16_t txtime;

	if (MIRA_RATE_IS_OFDM(rate)) {
		/* IEEE Std 802.11g-2003, pp. 44 */
		txtime = (8 + 4 * len + 3 + rate - 1) / rate;
		txtime = 16 + 4 + 4 * txtime + 6;
	} else {
		/* IEEE Std 802.11b-1999, pp. 28 */
		txtime = (16 * len + rate - 1) / rate;
		if (rate != 2 && (ic->ic_flags & IEEE80211_F_SHPREAMBLE))
			txtime +=  72 + 24;
		else
			txtime += 144 + 48;
	}
	return txtime;
}

uint32_t
ieee80211_mira_ht_txtime(uint32_t len, int mcs, int is2ghz)
{
	const struct ieee80211_mira_rateset *rs;
	/* XXX These constants should be macros in ieee80211.h instead. */
	const uint32_t t_lstf = 8; /* usec legacy short training field */
	const uint32_t t_lltf = 8; /* usec legacy long training field */
	const uint32_t t_lsig = 4; /* usec legacy signal field */
	const uint32_t t_htstf = 4; /* usec HT short training field */
	const uint32_t t_ltstf = 4; /* usec HT long training field */
	const uint32_t t_htsig = 8; /* usec HT signal field */
	const uint32_t t_sym = 4; /* usec symbol interval */
	uint32_t n_sym, n_dbps;
	uint32_t t_plcp;
	uint32_t t_data;
	uint32_t txtime;

	/*
	 * Calculate approximate frame Tx time in usec.
	 * See 802.11-2012, 20.4.3 "TXTIME calculation" and
	 * 20.3.11.1 "Equation (20-32)".
	 * XXX Assumes a 20MHz channel, HT-mixed frame format, no STBC.
	 */
	t_plcp = t_lstf + t_lltf + t_lsig + t_htstf + 4 * t_ltstf + t_htsig;
	rs = ieee80211_mira_get_rateset(mcs);
	n_dbps = rs->rates[mcs - rs->min_mcs] * 2;
	n_sym = ((8 * len + 16 + 6) / n_dbps); /* "Equation (20-32)" */
	t_data = t_sym * n_sym;

	txtime = t_plcp + t_data;
	if (is2ghz)
		txtime += 6; /* aSignalExtension */

	return txtime;
}

int
ieee80211_mira_best_basic_rate(struct ieee80211_node *ni)
{
	struct ieee80211_rateset *rs = &ni->ni_rates;
	int i, best, rval;

	/* Default to 1 Mbit/s on 2GHz and 6 Mbit/s on 5GHz. */
	best = IEEE80211_IS_CHAN_2GHZ(ni->ni_chan) ? 2 : 12;

	for (i = 0; i < rs->rs_nrates; i++) {
		if ((rs->rs_rates[i] & IEEE80211_RATE_BASIC) == 0)
			continue;
		rval = (rs->rs_rates[i] & IEEE80211_RATE_VAL);
		if (rval > best)
			best = rval;
	}

	return best;
}

/* 
 * See 802.11-2012, 9.7.6.5 "Rate selection for control response frames".
 * XXX Does not support BlockAck.
 */
int
ieee80211_mira_ack_rate(struct ieee80211_node *ni)
{
	/* 
	 * Assume the ACK was sent at a mandatory ERP OFDM rate.
	 * In the worst case, the firmware has retried at non-HT rates,
	 * so for MCS 0 assume we didn't actually send an OFDM frame
	 * and ACKs arrived at a basic rate.
	 */
	if (ni->ni_txmcs == 0)
		return ieee80211_mira_best_basic_rate(ni);
	else if (ni->ni_txmcs == 1)
		return 12;	/* 6 Mbit/s */
	else if (ni->ni_txmcs >= 2)
		return 24;	/* 12 Mbit/s */
	else
		return 48;	/* 24 Mbit/s */
}

uint64_t
ieee80211_mira_toverhead(struct ieee80211_mira_node *mn,
    struct ieee80211com *ic, struct ieee80211_node *ni)
{
/* XXX These should be macros in ieee80211.h. */
#define MIRA_RTSLEN IEEE80211_MIN_LEN
#define MIRA_CTSLEN (sizeof(struct ieee80211_frame_cts) + IEEE80211_CRC_LEN)
	uint32_t overhead;
	uint64_t toverhead;
	int rate, rts;
	enum ieee80211_htprot htprot;

	overhead = ieee80211_mira_ht_txtime(0, ni->ni_txmcs,
	    IEEE80211_IS_CHAN_2GHZ(ni->ni_chan));

	htprot = (ic->ic_bss->ni_htop1 & IEEE80211_HTOP1_PROT_MASK);
	if (htprot == IEEE80211_HTPROT_NONMEMBER ||
	    htprot == IEEE80211_HTPROT_NONHT_MIXED)
		rts = 1;
	else if (htprot == IEEE80211_HTPROT_20MHZ &&
		(ic->ic_htcaps & IEEE80211_HTCAP_CBW20_40))
		rts = 1;
	else
		rts = (mn->ampdu_size > ic->ic_rtsthreshold);

	if (rts) {
		/* Assume RTS/CTS were sent at a basic rate. */
		rate = ieee80211_mira_best_basic_rate(ni);
		overhead += ieee80211_mira_legacy_txtime(MIRA_RTSLEN, rate, ic);
		overhead += ieee80211_mira_legacy_txtime(MIRA_CTSLEN, rate, ic);
	}

	/* XXX This does not yet support BlockAck. */
	rate = ieee80211_mira_ack_rate(ni);
	overhead += ieee80211_mira_legacy_txtime(IEEE80211_ACK_LEN, rate, ic);

	toverhead = overhead;
	toverhead <<= MIRA_FP_SHIFT; /* convert to fixed-point */
	toverhead /= 1000; /* convert to msec */
	toverhead /= 1000; /* convert to sec */

#ifdef MIRA_DEBUG
	if (mira_debug > 3) {
		uint32_t txtime;
		txtime = ieee80211_mira_ht_txtime(mn->ampdu_size, ni->ni_txmcs,
		    IEEE80211_IS_CHAN_2GHZ(ni->ni_chan));
		txtime += overhead - ieee80211_mira_ht_txtime(0, ni->ni_txmcs,
		    IEEE80211_IS_CHAN_2GHZ(ni->ni_chan));
		DPRINTFN(4, ("txtime: %u usec\n", txtime));
		DPRINTFN(4, ("overhead: %u usec\n", overhead));
		DPRINTFN(4, ("toverhead: %s\n", mira_fp_sprintf(toverhead)));
	}
#endif
	return toverhead;
}

void
ieee80211_mira_update_stats(struct ieee80211_mira_node *mn,
    struct ieee80211com *ic, struct ieee80211_node *ni)
{
	/* Magic numbers from MiRA paper. */
	static const uint64_t alpha = MIRA_FP_1 / 8; /* 1/8 = 0.125 */
	static const uint64_t beta =  MIRA_FP_1 / 4; /* 1/4 = 0.25 */
	uint64_t sfer, delta, toverhead;
	uint64_t agglen = mn->agglen;
	uint64_t ampdu_size = mn->ampdu_size * 8; /* convert to bits */
	uint64_t rate = ieee80211_mira_get_txrate(ni->ni_txmcs);
	struct ieee80211_mira_goodput_stats *g = &mn->g[ni->ni_txmcs];

	g->nprobes += mn->agglen;
	g->nprobe_bytes += mn->ampdu_size;

	ampdu_size <<= MIRA_FP_SHIFT; /* convert to fixed-point */
	agglen <<= MIRA_FP_SHIFT;
	/* XXX range checks? */

	ampdu_size = ampdu_size / 1000; /* kbit */
	ampdu_size = ampdu_size / 1000; /* mbit */

	/* Compute Sub-Frame Error Rate (see section 2.2 in MiRA paper). */
	sfer = (mn->frames * mn->retries + mn->txfail);
	if ((sfer >> MIRA_FP_SHIFT) != 0)
		panic("sfer overflow"); /* bug in wifi driver */
	sfer <<= MIRA_FP_SHIFT; /* convert to fixed-point */
	sfer /= ((mn->retries + 1) * mn->frames);
	if (sfer > MIRA_FP_1)
		panic("sfer > 1"); /* bug in wifi driver */

	/* Store current loss percentage SFER. */
	g->loss = sfer * 100;
#ifdef MIRA_DEBUG
	if (g->loss && ieee80211_mira_probe_valid(mn, ni))
		DPRINTFN(2, ("frame error rate at MCS %d: %s%%\n",
		    ni->ni_txmcs, mira_fp_sprintf(g->loss)));
#endif

	/*
	 * Update goodput statistics (see section 5.1.2 in MiRA paper).
	 * We use a slightly modified but equivalent calculation which
	 * is tuned towards our fixed-point number format.
	 */

	g->average = MIRA_FP_MUL(MIRA_FP_1 - alpha, g->average);
	g->average += MIRA_FP_MUL(alpha, g->measured);

	g->stddeviation = MIRA_FP_MUL(MIRA_FP_1 - beta, g->stddeviation);
	if (g->average > g->measured)
		delta = g->average - g->measured;
	else
		delta = g->measured - g->average;
	g->stddeviation += MIRA_FP_MUL(beta, delta);

	g->average_agg = MIRA_FP_MUL(MIRA_FP_1 - alpha, g->average_agg);
	g->average_agg += MIRA_FP_MUL(alpha, agglen);

	toverhead = ieee80211_mira_toverhead(mn, ic, ni);
	toverhead = MIRA_FP_MUL(toverhead, rate);
	g->measured = MIRA_FP_DIV(MIRA_FP_1 - sfer, MIRA_FP_1 +
	    MIRA_FP_DIV(toverhead, MIRA_FP_MUL(ampdu_size, g->average_agg)));
	g->measured = MIRA_FP_MUL(g->measured, rate);
}

void
ieee80211_mira_reset_goodput_stats(struct ieee80211_mira_node *mn)
{
	int i;

	for (i = 0; i < nitems(mn->g); i++) {
		struct ieee80211_mira_goodput_stats *g = &mn->g[i];
		memset(g, 0, sizeof(*g));
		g->average_agg = 1;
		g->probe_interval = IEEE80211_MIRA_PROBE_TIMEOUT_MIN;
	}
}

void
ieee80211_mira_reset_driver_stats(struct ieee80211_mira_node *mn)
{
	mn->frames = 0;
	mn->retries = 0;
	mn->txfail = 0;
	mn->ampdu_size = 0;
	mn->agglen = 1;
}

/*
 * Rate selection.
 */

/* A rate's goodput has to be at least this much larger to be "better". */
#define IEEE80211_MIRA_RATE_THRESHOLD	(MIRA_FP_1 / 64) /* ~ 0.015 */

#define IEEE80211_MIRA_LOSS_THRESHOLD	10	/* in percent */

/* Number of (sub-)frames which render a probe valid. */
#define IEEE80211_MIRA_MIN_PROBE_FRAMES	4

/* Number of bytes which, alternatively, render a probe valid. */
#define IEEE80211_MIRA_MIN_PROBE_BYTES IEEE80211_MAX_LEN

int
ieee80211_mira_next_lower_intra_rate(struct ieee80211_mira_node *mn,
    struct ieee80211_node *ni)
{
	const struct ieee80211_mira_rateset *rs;
	int i, next;

	rs = ieee80211_mira_get_rateset(ni->ni_txmcs);
	if (ni->ni_txmcs == rs->min_mcs)
		return rs->min_mcs;

	next = ni->ni_txmcs;
	for (i = rs->nrates - 1; i >= 0; i--) {
		if ((mn->valid_rates & (1 << (i + rs->min_mcs))) == 0)
			continue;
		if (i + rs->min_mcs < ni->ni_txmcs) {
			next = i + rs->min_mcs;
			break;
		}
	}

	return next;
}

int
ieee80211_mira_next_intra_rate(struct ieee80211_mira_node *mn,
    struct ieee80211_node *ni)
{
	const struct ieee80211_mira_rateset *rs;
	int i, next;

	rs = ieee80211_mira_get_rateset(ni->ni_txmcs);
	if (ni->ni_txmcs == rs->max_mcs)
		return rs->max_mcs;

	next = ni->ni_txmcs;
	for (i = 0; i < rs->nrates; i++) {
		if ((mn->valid_rates & (1 << (i + rs->min_mcs))) == 0)
			continue;
		if (i + rs->min_mcs > ni->ni_txmcs) {
			next = i + rs->min_mcs;
			break;
		}
	}

	return next;
}

const struct ieee80211_mira_rateset *
ieee80211_mira_next_rateset(struct ieee80211_mira_node *mn, int mcs)
{
	const struct ieee80211_mira_rateset *rs, *rsnext;
	int next;

	rs = ieee80211_mira_get_rateset(mcs);
	if (mn->probing & IEEE80211_MIRA_PROBING_UP) {
		if (rs->max_mcs == 7)	/* MCS 0-7 */
			next = IEEE80211_MIRA_RATESET_MIMO2;
		else if (rs->max_mcs == 15)	/* MCS 8-15 */
			next = IEEE80211_MIRA_RATESET_MIMO3;
		else if (rs->max_mcs == 23)	/* MCS 16-23 */
			next = IEEE80211_MIRA_RATESET_MIMO4;
		else				/* MCS 24-31 */
			return NULL;
	} else if (mn->probing & IEEE80211_MIRA_PROBING_DOWN) {
		if (rs->min_mcs == 24)	/* MCS 24-31 */
			next = IEEE80211_MIRA_RATESET_MIMO3;
		else if (rs->min_mcs == 16)	/* MCS 16-23 */
			next = IEEE80211_MIRA_RATESET_MIMO2;
		else if (rs->min_mcs == 8)	/* MCS 8-15 */
			next = IEEE80211_MIRA_RATESET_SISO;
		else				/* MCS 0-7 */
			return NULL;
	} else
		panic("invalid probing mode %d", mn->probing);

	rsnext = &ieee80211_mira_ratesets[next];
	if ((rsnext->mcs_mask & mn->valid_rates) == 0)
		return NULL;

	return rsnext;
}

int
ieee80211_mira_best_mcs_in_rateset(struct ieee80211_mira_node *mn,
    const struct ieee80211_mira_rateset *rs)
{
	uint64_t gmax = 0;
	int i, best_mcs = rs->min_mcs;

	for (i = 0; i < rs->nrates; i++) {
		int mcs = rs->min_mcs + i;
		struct ieee80211_mira_goodput_stats *g = &mn->g[mcs];
		if (((1 << mcs) & mn->valid_rates) == 0)
			continue;
		if (g->measured > gmax + IEEE80211_MIRA_RATE_THRESHOLD) {
			gmax = g->measured;
			best_mcs = mcs;
		}
	}

	return best_mcs;
}
    
void
ieee80211_mira_probe_next_rateset(struct ieee80211_mira_node *mn,
    struct ieee80211_node *ni, const struct ieee80211_mira_rateset *rsnext)
{
	const struct ieee80211_mira_rateset *rs;
	struct ieee80211_mira_goodput_stats *g;
	int best_mcs, i;

	/* Find most recently measured best MCS from the current rateset. */
	rs = ieee80211_mira_get_rateset(ni->ni_txmcs);
	best_mcs = ieee80211_mira_best_mcs_in_rateset(mn, rs);

	/* Switch to the next rateset. */
	ni->ni_txmcs = rsnext->min_mcs;
	if ((mn->valid_rates & (1 << rsnext->min_mcs)) == 0)
		ni->ni_txmcs = ieee80211_mira_next_intra_rate(mn, ni);

	/* Select the lowest rate from the next rateset with loss-free
	 * goodput close to the current best measurement. */
	g = &mn->g[best_mcs];
	for (i = 0; i < rsnext->nrates; i++) {
		int mcs = rsnext->min_mcs + i;
		uint64_t txrate = rsnext->rates[i];

		if ((mn->valid_rates & (1 << mcs)) == 0)
			continue;

		txrate = txrate * 500; /* convert to kbit/s */
		txrate <<= MIRA_FP_SHIFT; /* convert to fixed-point */
		txrate /= 1000; /* convert to mbit/s */

		if (txrate > g->measured + IEEE80211_MIRA_RATE_THRESHOLD) {
			ni->ni_txmcs = mcs;
			break;
		}
	}

	/* Add rates from the next rateset as candidates. */
	mn->candidate_rates |= (1 << ni->ni_txmcs);
	if (mn->probing & IEEE80211_MIRA_PROBING_UP) {
		mn->candidate_rates |=
		  (1 << ieee80211_mira_next_intra_rate(mn, ni));
	} else if (mn->probing & IEEE80211_MIRA_PROBING_DOWN) {
#ifdef MIRA_AGGRESSIVE_DOWNWARDS_PROBING
		mn->candidate_rates |= ieee80211_mira_mcs_below(mn,
		    ni->ni_txmcs);
#else
		mn->candidate_rates |=
		    (1 << ieee80211_mira_next_lower_intra_rate(mn, ni));
#endif
	} else
		panic("invalid probing mode %d", mn->probing);
}

int
ieee80211_mira_next_mcs(struct ieee80211_mira_node *mn,
    struct ieee80211_node *ni)
{
	int next;

	if (mn->probing & IEEE80211_MIRA_PROBING_DOWN)
		next = ieee80211_mira_next_lower_intra_rate(mn, ni);
	else if (mn->probing & IEEE80211_MIRA_PROBING_UP)
		next = ieee80211_mira_next_intra_rate(mn, ni);
	else
		panic("invalid probing mode %d", mn->probing);

	return next;
}

int
ieee80211_mira_prev_mcs(struct ieee80211_mira_node *mn,
    struct ieee80211_node *ni)
{
	int next;

	if (mn->probing & IEEE80211_MIRA_PROBING_DOWN)
		next = ieee80211_mira_next_intra_rate(mn, ni);
	else if (mn->probing & IEEE80211_MIRA_PROBING_UP)
		next = ieee80211_mira_next_lower_intra_rate(mn, ni);
	else
		panic("invalid probing mode %d", mn->probing);

	return next;
}

int
ieee80211_mira_probe_valid(struct ieee80211_mira_node *mn,
    struct ieee80211_node *ni)
{
	struct ieee80211_mira_goodput_stats *g = &mn->g[ni->ni_txmcs];

	return (g->nprobes >= IEEE80211_MIRA_MIN_PROBE_FRAMES ||
	    g->nprobe_bytes >= IEEE80211_MIRA_MIN_PROBE_BYTES);
}

int
ieee80211_mira_intra_mode_ra_finished(struct ieee80211_mira_node *mn,
    struct ieee80211_node *ni)
{
	const struct ieee80211_mira_rateset *rs;
	struct ieee80211_mira_goodput_stats *g = &mn->g[ni->ni_txmcs];
	int next_mcs, best_mcs, probed_rates;
	uint64_t next_rate;

	if (!ieee80211_mira_probe_valid(mn, ni))
		return 0;

	probed_rates = (mn->probed_rates | (1 << ni->ni_txmcs));

	/* Check if the min/max MCS in this rateset has been probed. */
	rs = ieee80211_mira_get_rateset(ni->ni_txmcs);
	if (mn->probing & IEEE80211_MIRA_PROBING_DOWN) {
		if (ni->ni_txmcs == rs->min_mcs ||
		    probed_rates & (1 << rs->min_mcs)) {
			ieee80211_mira_trigger_next_rateset(mn, ni);
			return 1;
		}
	} else if (mn->probing & IEEE80211_MIRA_PROBING_UP) {
		if (ni->ni_txmcs == rs->max_mcs ||
		    probed_rates & (1 << rs->max_mcs)) {
			ieee80211_mira_trigger_next_rateset(mn, ni);
			return 1;
		}
	}

	/*
	 * Check if the measured goodput is better than the
	 * loss-free goodput of the candidate rate.
	 */
	next_mcs = ieee80211_mira_next_mcs(mn, ni);
	if (next_mcs == ni->ni_txmcs) {
		ieee80211_mira_trigger_next_rateset(mn, ni);
		return 1;
	}
	next_rate = ieee80211_mira_get_txrate(next_mcs);
	if (g->measured >= next_rate + IEEE80211_MIRA_RATE_THRESHOLD) {
		ieee80211_mira_trigger_next_rateset(mn, ni);
		return 1;
	}

	/* Check if we had a better measurement at a previously probed MCS. */
	best_mcs = ieee80211_mira_best_mcs_in_rateset(mn, rs);
	if ((mn->probed_rates & (1 << best_mcs))) {
		if ((mn->probing & IEEE80211_MIRA_PROBING_UP) &&
		    best_mcs < ni->ni_txmcs) {
			ieee80211_mira_trigger_next_rateset(mn, ni);
			return 1;
		}
		if ((mn->probing & IEEE80211_MIRA_PROBING_DOWN) &&
		    best_mcs > ni->ni_txmcs) {
			ieee80211_mira_trigger_next_rateset(mn, ni);
			return 1;
		}
	}

	/* Check if all rates in the set of candidate rates have been probed. */
	if ((mn->candidate_rates & probed_rates) == mn->candidate_rates) {
		/* Remain in the current rateset until above checks trigger. */
		return 1;
	}

	return 0;
}

void
ieee80211_mira_trigger_next_rateset(struct ieee80211_mira_node *mn,
    struct ieee80211_node *ni)
{
	const struct ieee80211_mira_rateset *rsnext;

	rsnext = ieee80211_mira_next_rateset(mn, ni->ni_txmcs);
	if (rsnext) {
		ieee80211_mira_probe_next_rateset(mn, ni, rsnext);
		mn->probing |= IEEE80211_MIRA_PROBING_INTER;
	} else
		mn->probing &= ~IEEE80211_MIRA_PROBING_INTER;
}

int
ieee80211_mira_inter_mode_ra_finished(struct ieee80211_mira_node *mn,
    struct ieee80211_node *ni)
{
	return ((mn->probing & IEEE80211_MIRA_PROBING_INTER) == 0);
}

int
ieee80211_mira_best_rate(struct ieee80211_mira_node *mn,
    struct ieee80211_node *ni)
{
	int i, best = 0;
	uint64_t gmax = 0;

	for (i = 0; i < nitems(mn->g); i++) {
		struct ieee80211_mira_goodput_stats *g = &mn->g[i];
		if (((1 << i) & mn->valid_rates) == 0)
			continue;
		if (g->measured > gmax + IEEE80211_MIRA_RATE_THRESHOLD) {
			gmax = g->measured;
			best = i;
		}
	}

#ifdef MIRA_DEBUG
	if (mn->best_mcs != best) {
		DPRINTF(("MCS %d is best; MCS{Mbps|probe interval}:", best));
		for (i = 0; i < IEEE80211_MIRA_NUM_MCS; i++) {
			struct ieee80211_mira_goodput_stats *g = &mn->g[i];
			if ((mn->valid_rates & (1 << i)) == 0)
				continue;
			DPRINTF((" %d{%s|%dms}", i,
			    mira_fp_sprintf(g->measured),
			    g->probe_interval));
		}
		DPRINTF(("\n"));
	}
#endif
	return best;
}

/* See section 5.1.1 (at "Adaptive probing interval") in MiRA paper. */
void
ieee80211_mira_update_probe_interval(struct ieee80211_mira_node *mn,
    struct ieee80211_mira_goodput_stats *g)
{
	uint64_t lt;
	int intval;

	lt = g->loss / IEEE80211_MIRA_LOSS_THRESHOLD;
	if (lt < MIRA_FP_1)
		lt = MIRA_FP_1;
	lt >>= MIRA_FP_SHIFT; /* round to integer */

	intval = (1 << g->nprobes); /* 2^nprobes */
	if (intval > IEEE80211_MIRA_PROBE_INTVAL_MAX)
		intval = IEEE80211_MIRA_PROBE_INTVAL_MAX;

	g->probe_interval = IEEE80211_MIRA_PROBE_TIMEOUT_MIN * intval * lt;
}

void
ieee80211_mira_schedule_probe_timers(struct ieee80211_mira_node *mn,
    struct ieee80211_node *ni)
{
	struct ieee80211_mira_goodput_stats *g;
	struct timeout *to;
	int mcs;

	mcs = ieee80211_mira_next_intra_rate(mn, ni);
	to = &mn->probe_to[IEEE80211_MIRA_PROBE_TO_UP];
	g = &mn->g[mcs];
	if (mcs != ni->ni_txmcs && !timeout_pending(to) &&
	    !mn->probe_timer_expired[IEEE80211_MIRA_PROBE_TO_UP]) {
		timeout_add_msec(to, g->probe_interval);
		DPRINTFN(3, ("start probing up for node %s at MCS %d in at "
		    "least %d msec\n",
		    ether_sprintf(ni->ni_macaddr), mcs, g->probe_interval));
	}

	mcs = ieee80211_mira_next_lower_intra_rate(mn, ni);
	to = &mn->probe_to[IEEE80211_MIRA_PROBE_TO_DOWN];
	g = &mn->g[mcs];
	if (mcs != ni->ni_txmcs && !timeout_pending(to) &&
	    !mn->probe_timer_expired[IEEE80211_MIRA_PROBE_TO_DOWN]) {
		timeout_add_msec(to, g->probe_interval);
		DPRINTFN(3, ("start probing down for node %s at MCS %d in at "
		    "least %d msec\n",
		    ether_sprintf(ni->ni_macaddr), mcs, g->probe_interval));
	}
}

int
ieee80211_mira_check_probe_timers(struct ieee80211_mira_node *mn,
    struct ieee80211_node *ni)
{
	int ret = 0, expired_timer = IEEE80211_MIRA_PROBE_TO_INVALID;
	int mcs;

	if (mn->probe_timer_expired[IEEE80211_MIRA_PROBE_TO_UP] &&
	    mn->probe_timer_expired[IEEE80211_MIRA_PROBE_TO_DOWN]) {
	    	if (arc4random_uniform(2))
			expired_timer = IEEE80211_MIRA_PROBE_TO_UP;
		else
			expired_timer = IEEE80211_MIRA_PROBE_TO_DOWN;
	} else if (mn->probe_timer_expired[IEEE80211_MIRA_PROBE_TO_DOWN])
		expired_timer = IEEE80211_MIRA_PROBE_TO_DOWN;
	else if (mn->probe_timer_expired[IEEE80211_MIRA_PROBE_TO_UP])
		expired_timer = IEEE80211_MIRA_PROBE_TO_UP;

	if (expired_timer != IEEE80211_MIRA_PROBE_TO_INVALID)
		mn->probe_timer_expired[expired_timer] = 0;

	switch (expired_timer) {
	case IEEE80211_MIRA_PROBE_TO_UP:
		/* Do time-based upwards probing on next frame. */
		DPRINTFN(2, ("probe timer expired: probe upwards\n"));
		mn->probing = IEEE80211_MIRA_PROBING_UP;
		mcs = ieee80211_mira_next_intra_rate(mn, ni);
		mn->candidate_rates = (1 << mcs);
		ret = 1;
		break;
	case IEEE80211_MIRA_PROBE_TO_DOWN:
		/* Do time-based downwards probing on next frame. */
		DPRINTFN(2, ("probe timer expired: probe downwards\n"));
		mn->probing = IEEE80211_MIRA_PROBING_DOWN;
		mcs = ieee80211_mira_next_lower_intra_rate(mn, ni);
		mn->candidate_rates = (1 << mcs);
		ret = 1;
		break;
	case IEEE80211_MIRA_PROBE_TO_INVALID:
	default:
		ret = 0;
		break;
	}

	return ret;
}

void
ieee80211_mira_probe_next_rate(struct ieee80211_mira_node *mn,
    struct ieee80211_node *ni)
{
	struct ieee80211_mira_goodput_stats *gprev, *g;
	int prev_mcs;

	prev_mcs = ieee80211_mira_prev_mcs(mn, ni);
	gprev = &mn->g[prev_mcs];
	g = &mn->g[ni->ni_txmcs];
	/* If the previous rate was worse, increase its probing interval. */
	if (prev_mcs != ni->ni_txmcs &&
	    gprev->measured + IEEE80211_MIRA_RATE_THRESHOLD < g->measured)
		ieee80211_mira_update_probe_interval(mn, gprev);

	/* Select the next rate to probe. */
	mn->probed_rates |= (1 << ni->ni_txmcs);
	ni->ni_txmcs = ieee80211_mira_next_mcs(mn, ni);
}

uint32_t
ieee80211_mira_valid_rates(struct ieee80211com *ic, struct ieee80211_node *ni)
{
	uint32_t valid_mcs = 0;
	int i;

	for (i = 0;
	    i < MIN(IEEE80211_MIRA_NUM_MCS, IEEE80211_HT_NUM_MCS); i++) {
		if (isset(ic->ic_sup_mcs, i) && isset(ni->ni_rxmcs, i))
			valid_mcs |= (1 << i);
	}

	return valid_mcs;
}

uint32_t
ieee80211_mira_mcs_below(struct ieee80211_mira_node *mn, int mcs)
{
	const struct ieee80211_mira_rateset *rs;
	uint32_t mcs_mask;
	int i;

	rs = ieee80211_mira_get_rateset(mcs);
	mcs_mask = (1 << rs->min_mcs);
	for (i = rs->min_mcs + 1; i < mcs; i++) {
		if ((mn->valid_rates & (1 << i)) == 0)
			continue;
		mcs_mask |= (1 << i);
	}

	return mcs_mask;
}

void
ieee80211_mira_choose(struct ieee80211_mira_node *mn, struct ieee80211com *ic,
    struct ieee80211_node *ni)
{
	struct ieee80211_mira_goodput_stats *g = &mn->g[ni->ni_txmcs];
	int s;

	s = splnet();

	if (mn->valid_rates == 0)
		mn->valid_rates = ieee80211_mira_valid_rates(ic, ni);

	DPRINTFN(5, ("%s: driver stats:\n", __func__));
	DPRINTFN(5, ("mn->frames = %u\n", mn->frames));
	DPRINTFN(5, ("mn->retries = %u\n", mn->retries));
	DPRINTFN(5, ("mn->txfail = %u\n", mn->txfail));
	DPRINTFN(5, ("mn->ampdu_size = %u\n", mn->ampdu_size));
	DPRINTFN(5, ("mn->agglen = %u\n", mn->agglen));

	ieee80211_mira_update_stats(mn, ic, ni);

	if (mn->probing) {
		/* Probe another rate or settle at the best rate. */
		if (!ieee80211_mira_intra_mode_ra_finished(mn, ni)) {
			if (ieee80211_mira_probe_valid(mn, ni)) {
				ieee80211_mira_probe_next_rate(mn, ni);
				ieee80211_mira_reset_driver_stats(mn);
			}
			DPRINTFN(4, ("probing MCS %d\n", ni->ni_txmcs));
		} else if (ieee80211_mira_inter_mode_ra_finished(mn, ni)) {
			int best = ieee80211_mira_best_rate(mn, ni);
			mn->probing = IEEE80211_MIRA_NOT_PROBING;
			mn->probed_rates = 0;
			if (mn->best_mcs != best) {
				mn->best_mcs = best;
				ni->ni_txmcs = best;
				/* Reset probe interval for new best rate. */
				mn->g[best].probe_interval =
				    IEEE80211_MIRA_PROBE_TIMEOUT_MIN;
				mn->g[best].nprobes = 0;
				mn->g[best].nprobe_bytes = 0;
			} else
				ni->ni_txmcs = mn->best_mcs;

		}

		splx(s);
		return;
	} else {
		ieee80211_mira_reset_driver_stats(mn);
		ieee80211_mira_schedule_probe_timers(mn, ni);
	}

	if (ieee80211_mira_check_probe_timers(mn, ni)) {
		/* Time-based probing has triggered. */
		splx(s);
		return;
	}

	/* Check if event-based probing should be triggered. */
	if (g->measured <= g->average - 2 * g->stddeviation) {
		/* Channel becomes bad. Probe downwards. */
		DPRINTFN(2, ("channel becomes bad; probe downwards\n"));
		DPRINTFN(3, ("measured: %s Mbit/s\n",
		    mira_fp_sprintf(g->measured)));
		DPRINTFN(3, ("average: %s Mbit/s\n",
		    mira_fp_sprintf(g->average)));
		DPRINTFN(3, ("stddeviation: %s\n",
		    mira_fp_sprintf(g->stddeviation)));
		mn->probing = IEEE80211_MIRA_PROBING_DOWN;
		mn->probed_rates = 0;
#ifdef MIRA_AGGRESSIVE_DOWNWARDS_PROBING
		/* Allow for probing all the way down within this rateset. */
		mn->candidate_rates = ieee80211_mira_mcs_below(mn,
		    ni->ni_txmcs);
#else
		/* Probe the lower candidate rate to see if it's any better. */
		mn->candidate_rates =
		    (1 << ieee80211_mira_next_lower_intra_rate(mn, ni));
#endif
	} else if (g->measured >= g->average + 2 * g->stddeviation) {
		/* Channel becomes good. */
		DPRINTFN(2, ("channel becomes good; probe upwards\n"));
		DPRINTFN(3, ("measured: %s Mbit/s\n",
		    mira_fp_sprintf(g->measured)));
		DPRINTFN(3, ("average: %s Mbit/s\n",
		    mira_fp_sprintf(g->average)));
		DPRINTFN(3, ("stddeviation: %s\n",
		    mira_fp_sprintf(g->stddeviation)));
		mn->probing = IEEE80211_MIRA_PROBING_UP;
		mn->probed_rates = 0;
		/* Probe the upper candidate rate to see if it's any better. */
		mn->candidate_rates =
		    (1 << ieee80211_mira_next_intra_rate(mn, ni));
	} else {
		/* Remain at current rate. */
		mn->probing = IEEE80211_MIRA_NOT_PROBING;
		mn->probed_rates = 0;
	}

	splx(s);
}

void
ieee80211_mira_node_init(struct ieee80211_mira_node *mn)
{
	memset(mn, 0, sizeof(*mn));
	mn->agglen = 1;
	ieee80211_mira_reset_goodput_stats(mn);

	timeout_set(&mn->probe_to[IEEE80211_MIRA_PROBE_TO_UP],
	    ieee80211_mira_probe_timeout_up, mn);
	timeout_set(&mn->probe_to[IEEE80211_MIRA_PROBE_TO_DOWN],
	    ieee80211_mira_probe_timeout_down, mn);
}

void
ieee80211_mira_cancel_timeouts(struct ieee80211_mira_node *mn)
{
	int t;

	for (t = 0; t < nitems(mn->probe_to); t++)
		timeout_del(&mn->probe_to[t]);
}