ieee80211_amrr.c revision 257412 
1/*	$OpenBSD: ieee80211_amrr.c,v 1.1 2006/06/17 19:07:19 damien Exp $	*/
2
3/*-
4 * Copyright (c) 2010 Rui Paulo <rpaulo@FreeBSD.org>
5 * Copyright (c) 2006
6 *	Damien Bergamini <damien.bergamini@free.fr>
7 *
8 * Permission to use, copy, modify, and distribute this software for any
9 * purpose with or without fee is hereby granted, provided that the above
10 * copyright notice and this permission notice appear in all copies.
11 *
12 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
13 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
14 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
15 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
16 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
17 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
18 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
19 */
20
21#include <sys/cdefs.h>
22__FBSDID("$FreeBSD: head/sys/net80211/ieee80211_amrr.c 257412 2013-10-31 02:04:53Z adrian $");
23
24/*-
25 * Naive implementation of the Adaptive Multi Rate Retry algorithm:
26 *
27 * "IEEE 802.11 Rate Adaptation: A Practical Approach"
28 *  Mathieu Lacage, Hossein Manshaei, Thierry Turletti
29 *  INRIA Sophia - Projet Planete
30 *  http://www-sop.inria.fr/rapports/sophia/RR-5208.html
31 */
32#include "opt_wlan.h"
33
34#include <sys/param.h>
35#include <sys/kernel.h>
36#include <sys/module.h>
37#include <sys/socket.h>
38#include <sys/sysctl.h>
39
40#include <net/if.h>
41#include <net/if_var.h>
42#include <net/if_media.h>
43#include <net/ethernet.h>
44
45#ifdef INET
46#include <netinet/in.h>
47#include <netinet/if_ether.h>
48#endif
49
50#include <net80211/ieee80211_var.h>
51#include <net80211/ieee80211_ht.h>
52#include <net80211/ieee80211_amrr.h>
53#include <net80211/ieee80211_ratectl.h>
54
55#define is_success(amn)	\
56	((amn)->amn_retrycnt < (amn)->amn_txcnt / 10)
57#define is_failure(amn)	\
58	((amn)->amn_retrycnt > (amn)->amn_txcnt / 3)
59#define is_enough(amn)		\
60	((amn)->amn_txcnt > 10)
61
62static void	amrr_setinterval(const struct ieee80211vap *, int);
63static void	amrr_init(struct ieee80211vap *);
64static void	amrr_deinit(struct ieee80211vap *);
65static void	amrr_node_init(struct ieee80211_node *);
66static void	amrr_node_deinit(struct ieee80211_node *);
67static int	amrr_update(struct ieee80211_amrr *,
68    			struct ieee80211_amrr_node *, struct ieee80211_node *);
69static int	amrr_rate(struct ieee80211_node *, void *, uint32_t);
70static void	amrr_tx_complete(const struct ieee80211vap *,
71    			const struct ieee80211_node *, int,
72			void *, void *);
73static void	amrr_tx_update(const struct ieee80211vap *vap,
74			const struct ieee80211_node *, void *, void *, void *);
75static void	amrr_sysctlattach(struct ieee80211vap *,
76			struct sysctl_ctx_list *, struct sysctl_oid *);
77
78/* number of references from net80211 layer */
79static	int nrefs = 0;
80
81static const struct ieee80211_ratectl amrr = {
82	.ir_name	= "amrr",
83	.ir_attach	= NULL,
84	.ir_detach	= NULL,
85	.ir_init	= amrr_init,
86	.ir_deinit	= amrr_deinit,
87	.ir_node_init	= amrr_node_init,
88	.ir_node_deinit	= amrr_node_deinit,
89	.ir_rate	= amrr_rate,
90	.ir_tx_complete	= amrr_tx_complete,
91	.ir_tx_update	= amrr_tx_update,
92	.ir_setinterval	= amrr_setinterval,
93};
94IEEE80211_RATECTL_MODULE(amrr, 1);
95IEEE80211_RATECTL_ALG(amrr, IEEE80211_RATECTL_AMRR, amrr);
96
97static void
98amrr_setinterval(const struct ieee80211vap *vap, int msecs)
99{
100	struct ieee80211_amrr *amrr = vap->iv_rs;
101	int t;
102
103	if (msecs < 100)
104		msecs = 100;
105	t = msecs_to_ticks(msecs);
106	amrr->amrr_interval = (t < 1) ? 1 : t;
107}
108
109static void
110amrr_init(struct ieee80211vap *vap)
111{
112	struct ieee80211_amrr *amrr;
113
114	KASSERT(vap->iv_rs == NULL, ("%s called multiple times", __func__));
115
116	amrr = vap->iv_rs = malloc(sizeof(struct ieee80211_amrr),
117	    M_80211_RATECTL, M_NOWAIT|M_ZERO);
118	if (amrr == NULL) {
119		if_printf(vap->iv_ifp, "couldn't alloc ratectl structure\n");
120		return;
121	}
122	amrr->amrr_min_success_threshold = IEEE80211_AMRR_MIN_SUCCESS_THRESHOLD;
123	amrr->amrr_max_success_threshold = IEEE80211_AMRR_MAX_SUCCESS_THRESHOLD;
124	amrr_setinterval(vap, 500 /* ms */);
125	amrr_sysctlattach(vap, vap->iv_sysctl, vap->iv_oid);
126}
127
128static void
129amrr_deinit(struct ieee80211vap *vap)
130{
131	free(vap->iv_rs, M_80211_RATECTL);
132}
133
134/*
135 * Return whether 11n rates are possible.
136 *
137 * Some 11n devices may return HT information but no HT rates.
138 * Thus, we shouldn't treat them as an 11n node.
139 */
140static int
141amrr_node_is_11n(struct ieee80211_node *ni)
142{
143
144	if (ni->ni_chan == NULL)
145		return (0);
146	if (ni->ni_chan == IEEE80211_CHAN_ANYC)
147		return (0);
148	if (IEEE80211_IS_CHAN_HT(ni->ni_chan) && ni->ni_htrates.rs_nrates == 0)
149		return (0);
150	return (IEEE80211_IS_CHAN_HT(ni->ni_chan));
151}
152
153static void
154amrr_node_init(struct ieee80211_node *ni)
155{
156	const struct ieee80211_rateset *rs = NULL;
157	struct ieee80211vap *vap = ni->ni_vap;
158	struct ieee80211_amrr *amrr = vap->iv_rs;
159	struct ieee80211_amrr_node *amn;
160	uint8_t rate;
161
162	if (ni->ni_rctls == NULL) {
163		ni->ni_rctls = amn = malloc(sizeof(struct ieee80211_amrr_node),
164		    M_80211_RATECTL, M_NOWAIT|M_ZERO);
165		if (amn == NULL) {
166			if_printf(vap->iv_ifp, "couldn't alloc per-node ratectl "
167			    "structure\n");
168			return;
169		}
170	} else
171		amn = ni->ni_rctls;
172	amn->amn_amrr = amrr;
173	amn->amn_success = 0;
174	amn->amn_recovery = 0;
175	amn->amn_txcnt = amn->amn_retrycnt = 0;
176	amn->amn_success_threshold = amrr->amrr_min_success_threshold;
177
178	/* 11n or not? Pick the right rateset */
179	if (amrr_node_is_11n(ni)) {
180		/* XXX ew */
181		IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
182		    "%s: 11n node", __func__);
183		rs = (struct ieee80211_rateset *) &ni->ni_htrates;
184	} else {
185		IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
186		    "%s: non-11n node", __func__);
187		rs = &ni->ni_rates;
188	}
189
190	/* Initial rate - lowest */
191	rate = rs->rs_rates[0];
192
193	/* XXX clear the basic rate flag if it's not 11n */
194	if (! amrr_node_is_11n(ni))
195		rate &= IEEE80211_RATE_VAL;
196
197	/* pick initial rate from the rateset - HT or otherwise */
198	for (amn->amn_rix = rs->rs_nrates - 1; amn->amn_rix > 0;
199	    amn->amn_rix--) {
200		/* legacy - anything < 36mbit, stop searching */
201		/* 11n - stop at MCS4 / MCS12 / MCS28 */
202		if (amrr_node_is_11n(ni) &&
203		    (rs->rs_rates[amn->amn_rix] & 0x7) < 4)
204			break;
205		else if ((rs->rs_rates[amn->amn_rix] & IEEE80211_RATE_VAL) <= 72)
206			break;
207		rate = rs->rs_rates[amn->amn_rix] & IEEE80211_RATE_VAL;
208	}
209
210	/* if the rate is an 11n rate, ensure the MCS bit is set */
211	if (amrr_node_is_11n(ni))
212		rate |= IEEE80211_RATE_MCS;
213
214	/* Assign initial rate from the rateset */
215	ni->ni_txrate = rate;
216	amn->amn_ticks = ticks;
217
218	IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
219	    "AMRR: nrates=%d, initial rate %d",
220	    rs->rs_nrates,
221	    rate);
222}
223
224static void
225amrr_node_deinit(struct ieee80211_node *ni)
226{
227	free(ni->ni_rctls, M_80211_RATECTL);
228}
229
230static int
231amrr_update(struct ieee80211_amrr *amrr, struct ieee80211_amrr_node *amn,
232    struct ieee80211_node *ni)
233{
234	int rix = amn->amn_rix;
235	const struct ieee80211_rateset *rs = NULL;
236
237	KASSERT(is_enough(amn), ("txcnt %d", amn->amn_txcnt));
238
239	/* 11n or not? Pick the right rateset */
240	if (amrr_node_is_11n(ni)) {
241		/* XXX ew */
242		rs = (struct ieee80211_rateset *) &ni->ni_htrates;
243	} else {
244		rs = &ni->ni_rates;
245	}
246
247	IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
248	    "AMRR: current rate %d, txcnt=%d, retrycnt=%d",
249	    rs->rs_rates[rix] & IEEE80211_RATE_VAL,
250	    amn->amn_txcnt,
251	    amn->amn_retrycnt);
252
253	/*
254	 * XXX This is totally bogus for 11n, as although high MCS
255	 * rates for each stream may be failing, the next stream
256	 * should be checked.
257	 *
258	 * Eg, if MCS5 is ok but MCS6/7 isn't, and we can go up to
259	 * MCS23, we should skip 6/7 and try 8 onwards.
260	 */
261	if (is_success(amn)) {
262		amn->amn_success++;
263		if (amn->amn_success >= amn->amn_success_threshold &&
264		    rix + 1 < rs->rs_nrates) {
265			amn->amn_recovery = 1;
266			amn->amn_success = 0;
267			rix++;
268			IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
269			    "AMRR increasing rate %d (txcnt=%d retrycnt=%d)",
270			    rs->rs_rates[rix] & IEEE80211_RATE_VAL,
271			    amn->amn_txcnt, amn->amn_retrycnt);
272		} else {
273			amn->amn_recovery = 0;
274		}
275	} else if (is_failure(amn)) {
276		amn->amn_success = 0;
277		if (rix > 0) {
278			if (amn->amn_recovery) {
279				amn->amn_success_threshold *= 2;
280				if (amn->amn_success_threshold >
281				    amrr->amrr_max_success_threshold)
282					amn->amn_success_threshold =
283					    amrr->amrr_max_success_threshold;
284			} else {
285				amn->amn_success_threshold =
286				    amrr->amrr_min_success_threshold;
287			}
288			rix--;
289			IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
290			    "AMRR decreasing rate %d (txcnt=%d retrycnt=%d)",
291			    rs->rs_rates[rix] & IEEE80211_RATE_VAL,
292			    amn->amn_txcnt, amn->amn_retrycnt);
293		}
294		amn->amn_recovery = 0;
295	}
296
297	/* reset counters */
298	amn->amn_txcnt = 0;
299	amn->amn_retrycnt = 0;
300
301	return rix;
302}
303
304/*
305 * Return the rate index to use in sending a data frame.
306 * Update our internal state if it's been long enough.
307 * If the rate changes we also update ni_txrate to match.
308 */
309static int
310amrr_rate(struct ieee80211_node *ni, void *arg __unused, uint32_t iarg __unused)
311{
312	struct ieee80211_amrr_node *amn = ni->ni_rctls;
313	struct ieee80211_amrr *amrr = amn->amn_amrr;
314	const struct ieee80211_rateset *rs = NULL;
315	int rix;
316
317	/* 11n or not? Pick the right rateset */
318	if (amrr_node_is_11n(ni)) {
319		/* XXX ew */
320		rs = (struct ieee80211_rateset *) &ni->ni_htrates;
321	} else {
322		rs = &ni->ni_rates;
323	}
324
325	if (is_enough(amn) && (ticks - amn->amn_ticks) > amrr->amrr_interval) {
326		rix = amrr_update(amrr, amn, ni);
327		if (rix != amn->amn_rix) {
328			/* update public rate */
329			ni->ni_txrate = rs->rs_rates[rix];
330			/* XXX strip basic rate flag from txrate, if non-11n */
331			if (amrr_node_is_11n(ni))
332				ni->ni_txrate |= IEEE80211_RATE_MCS;
333			else
334				ni->ni_txrate &= IEEE80211_RATE_VAL;
335			amn->amn_rix = rix;
336		}
337		amn->amn_ticks = ticks;
338	} else
339		rix = amn->amn_rix;
340	return rix;
341}
342
343/*
344 * Update statistics with tx complete status.  Ok is non-zero
345 * if the packet is known to be ACK'd.  Retries has the number
346 * retransmissions (i.e. xmit attempts - 1).
347 */
348static void
349amrr_tx_complete(const struct ieee80211vap *vap,
350    const struct ieee80211_node *ni, int ok,
351    void *arg1, void *arg2 __unused)
352{
353	struct ieee80211_amrr_node *amn = ni->ni_rctls;
354	int retries = *(int *)arg1;
355
356	amn->amn_txcnt++;
357	if (ok)
358		amn->amn_success++;
359	amn->amn_retrycnt += retries;
360}
361
362/*
363 * Set tx count/retry statistics explicitly.  Intended for
364 * drivers that poll the device for statistics maintained
365 * in the device.
366 */
367static void
368amrr_tx_update(const struct ieee80211vap *vap, const struct ieee80211_node *ni,
369    void *arg1, void *arg2, void *arg3)
370{
371	struct ieee80211_amrr_node *amn = ni->ni_rctls;
372	int txcnt = *(int *)arg1, success = *(int *)arg2, retrycnt = *(int *)arg3;
373
374	amn->amn_txcnt = txcnt;
375	amn->amn_success = success;
376	amn->amn_retrycnt = retrycnt;
377}
378
379static int
380amrr_sysctl_interval(SYSCTL_HANDLER_ARGS)
381{
382	struct ieee80211vap *vap = arg1;
383	struct ieee80211_amrr *amrr = vap->iv_rs;
384	int msecs = ticks_to_msecs(amrr->amrr_interval);
385	int error;
386
387	error = sysctl_handle_int(oidp, &msecs, 0, req);
388	if (error || !req->newptr)
389		return error;
390	amrr_setinterval(vap, msecs);
391	return 0;
392}
393
394static void
395amrr_sysctlattach(struct ieee80211vap *vap,
396    struct sysctl_ctx_list *ctx, struct sysctl_oid *tree)
397{
398	struct ieee80211_amrr *amrr = vap->iv_rs;
399
400	SYSCTL_ADD_PROC(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
401	    "amrr_rate_interval", CTLTYPE_INT | CTLFLAG_RW, vap,
402	    0, amrr_sysctl_interval, "I", "amrr operation interval (ms)");
403	/* XXX bounds check values */
404	SYSCTL_ADD_UINT(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
405	    "amrr_max_sucess_threshold", CTLFLAG_RW,
406	    &amrr->amrr_max_success_threshold, 0, "");
407	SYSCTL_ADD_UINT(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
408	    "amrr_min_sucess_threshold", CTLFLAG_RW,
409	    &amrr->amrr_min_success_threshold, 0, "");
410}
411