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: stable/10/sys/net80211/ieee80211_amrr.c 343036 2019-01-15 02:26:03Z avos $");
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_media.h>
42
43#ifdef INET
44#include <netinet/in.h>
45#include <netinet/if_ether.h>
46#endif
47
48#include <net80211/ieee80211_var.h>
49#include <net80211/ieee80211_ht.h>
50#include <net80211/ieee80211_amrr.h>
51#include <net80211/ieee80211_ratectl.h>
52
53#define is_success(amn)	\
54	((amn)->amn_retrycnt < (amn)->amn_txcnt / 10)
55#define is_failure(amn)	\
56	((amn)->amn_retrycnt > (amn)->amn_txcnt / 3)
57#define is_enough(amn)		\
58	((amn)->amn_txcnt > 10)
59
60static void	amrr_setinterval(const struct ieee80211vap *, int);
61static void	amrr_init(struct ieee80211vap *);
62static void	amrr_deinit(struct ieee80211vap *);
63static void	amrr_node_init(struct ieee80211_node *);
64static void	amrr_node_deinit(struct ieee80211_node *);
65static int	amrr_update(struct ieee80211_amrr *,
66    			struct ieee80211_amrr_node *, struct ieee80211_node *);
67static int	amrr_rate(struct ieee80211_node *, void *, uint32_t);
68static void	amrr_tx_complete(const struct ieee80211vap *,
69    			const struct ieee80211_node *, int,
70			void *, void *);
71static void	amrr_tx_update(const struct ieee80211vap *vap,
72			const struct ieee80211_node *, void *, void *, void *);
73static void	amrr_sysctlattach(struct ieee80211vap *,
74			struct sysctl_ctx_list *, struct sysctl_oid *);
75
76/* number of references from net80211 layer */
77static	int nrefs = 0;
78
79static const struct ieee80211_ratectl amrr = {
80	.ir_name	= "amrr",
81	.ir_attach	= NULL,
82	.ir_detach	= NULL,
83	.ir_init	= amrr_init,
84	.ir_deinit	= amrr_deinit,
85	.ir_node_init	= amrr_node_init,
86	.ir_node_deinit	= amrr_node_deinit,
87	.ir_rate	= amrr_rate,
88	.ir_tx_complete	= amrr_tx_complete,
89	.ir_tx_update	= amrr_tx_update,
90	.ir_setinterval	= amrr_setinterval,
91};
92IEEE80211_RATECTL_MODULE(amrr, 1);
93IEEE80211_RATECTL_ALG(amrr, IEEE80211_RATECTL_AMRR, amrr);
94
95static void
96amrr_setinterval(const struct ieee80211vap *vap, int msecs)
97{
98	struct ieee80211_amrr *amrr = vap->iv_rs;
99	int t;
100
101	if (!amrr)
102		return;
103
104	if (msecs < 100)
105		msecs = 100;
106	t = msecs_to_ticks(msecs);
107	amrr->amrr_interval = (t < 1) ? 1 : t;
108}
109
110static void
111amrr_init(struct ieee80211vap *vap)
112{
113	struct ieee80211_amrr *amrr;
114
115	KASSERT(vap->iv_rs == NULL, ("%s called multiple times", __func__));
116
117	nrefs++;		/* XXX locking */
118	amrr = vap->iv_rs = malloc(sizeof(struct ieee80211_amrr),
119	    M_80211_RATECTL, M_NOWAIT|M_ZERO);
120	if (amrr == NULL) {
121		if_printf(vap->iv_ifp, "couldn't alloc ratectl structure\n");
122		return;
123	}
124	amrr->amrr_min_success_threshold = IEEE80211_AMRR_MIN_SUCCESS_THRESHOLD;
125	amrr->amrr_max_success_threshold = IEEE80211_AMRR_MAX_SUCCESS_THRESHOLD;
126	amrr_setinterval(vap, 500 /* ms */);
127	amrr_sysctlattach(vap, vap->iv_sysctl, vap->iv_oid);
128}
129
130static void
131amrr_deinit(struct ieee80211vap *vap)
132{
133	free(vap->iv_rs, M_80211_RATECTL);
134	KASSERT(nrefs > 0, ("imbalanced attach/detach"));
135	nrefs--;		/* XXX locking */
136}
137
138static int
139amrr_node_is_11n(struct ieee80211_node *ni)
140{
141
142	if (ni->ni_chan == NULL)
143		return (0);
144	if (ni->ni_chan == IEEE80211_CHAN_ANYC)
145		return (0);
146	return (IEEE80211_IS_CHAN_HT(ni->ni_chan));
147}
148
149static void
150amrr_node_init(struct ieee80211_node *ni)
151{
152	const struct ieee80211_rateset *rs = NULL;
153	struct ieee80211vap *vap = ni->ni_vap;
154	struct ieee80211_amrr *amrr = vap->iv_rs;
155	struct ieee80211_amrr_node *amn;
156	uint8_t rate;
157
158	if (!amrr) {
159		if_printf(vap->iv_ifp, "ratectl structure was not allocated, "
160		    "per-node structure allocation skipped\n");
161		return;
162	}
163
164	if (ni->ni_rctls == NULL) {
165		ni->ni_rctls = amn = malloc(sizeof(struct ieee80211_amrr_node),
166		    M_80211_RATECTL, M_NOWAIT|M_ZERO);
167		if (amn == NULL) {
168			if_printf(vap->iv_ifp, "couldn't alloc per-node ratectl "
169			    "structure\n");
170			return;
171		}
172	} else
173		amn = ni->ni_rctls;
174	amn->amn_amrr = amrr;
175	amn->amn_success = 0;
176	amn->amn_recovery = 0;
177	amn->amn_txcnt = amn->amn_retrycnt = 0;
178	amn->amn_success_threshold = amrr->amrr_min_success_threshold;
179
180	/* 11n or not? Pick the right rateset */
181	if (amrr_node_is_11n(ni)) {
182		/* XXX ew */
183		IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
184		    "%s: 11n node", __func__);
185		rs = (struct ieee80211_rateset *) &ni->ni_htrates;
186	} else {
187		IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
188		    "%s: non-11n node", __func__);
189		rs = &ni->ni_rates;
190	}
191
192	/* Initial rate - lowest */
193	rate = rs->rs_rates[0];
194
195	/* XXX clear the basic rate flag if it's not 11n */
196	if (! amrr_node_is_11n(ni))
197		rate &= IEEE80211_RATE_VAL;
198
199	/* pick initial rate from the rateset - HT or otherwise */
200	for (amn->amn_rix = rs->rs_nrates - 1; amn->amn_rix > 0;
201	    amn->amn_rix--) {
202		/* legacy - anything < 36mbit, stop searching */
203		/* 11n - stop at MCS4 / MCS12 / MCS28 */
204		if (amrr_node_is_11n(ni) &&
205		    (rs->rs_rates[amn->amn_rix] & 0x7) < 4)
206			break;
207		else if ((rs->rs_rates[amn->amn_rix] & IEEE80211_RATE_VAL) <= 72)
208			break;
209		rate = rs->rs_rates[amn->amn_rix] & IEEE80211_RATE_VAL;
210	}
211
212	/* if the rate is an 11n rate, ensure the MCS bit is set */
213	if (amrr_node_is_11n(ni))
214		rate |= IEEE80211_RATE_MCS;
215
216	/* Assign initial rate from the rateset */
217	ni->ni_txrate = rate;
218	amn->amn_ticks = ticks;
219
220	IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
221	    "AMRR: nrates=%d, initial rate %d",
222	    rs->rs_nrates,
223	    rate);
224}
225
226static void
227amrr_node_deinit(struct ieee80211_node *ni)
228{
229	free(ni->ni_rctls, M_80211_RATECTL);
230}
231
232static int
233amrr_update(struct ieee80211_amrr *amrr, struct ieee80211_amrr_node *amn,
234    struct ieee80211_node *ni)
235{
236	int rix = amn->amn_rix;
237	const struct ieee80211_rateset *rs = NULL;
238
239	KASSERT(is_enough(amn), ("txcnt %d", amn->amn_txcnt));
240
241	/* 11n or not? Pick the right rateset */
242	if (amrr_node_is_11n(ni)) {
243		/* XXX ew */
244		rs = (struct ieee80211_rateset *) &ni->ni_htrates;
245	} else {
246		rs = &ni->ni_rates;
247	}
248
249	IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
250	    "AMRR: current rate %d, txcnt=%d, retrycnt=%d",
251	    rs->rs_rates[rix] & IEEE80211_RATE_VAL,
252	    amn->amn_txcnt,
253	    amn->amn_retrycnt);
254
255	/*
256	 * XXX This is totally bogus for 11n, as although high MCS
257	 * rates for each stream may be failing, the next stream
258	 * should be checked.
259	 *
260	 * Eg, if MCS5 is ok but MCS6/7 isn't, and we can go up to
261	 * MCS23, we should skip 6/7 and try 8 onwards.
262	 */
263	if (is_success(amn)) {
264		amn->amn_success++;
265		if (amn->amn_success >= amn->amn_success_threshold &&
266		    rix + 1 < rs->rs_nrates) {
267			amn->amn_recovery = 1;
268			amn->amn_success = 0;
269			rix++;
270			IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
271			    "AMRR increasing rate %d (txcnt=%d retrycnt=%d)",
272			    rs->rs_rates[rix] & IEEE80211_RATE_VAL,
273			    amn->amn_txcnt, amn->amn_retrycnt);
274		} else {
275			amn->amn_recovery = 0;
276		}
277	} else if (is_failure(amn)) {
278		amn->amn_success = 0;
279		if (rix > 0) {
280			if (amn->amn_recovery) {
281				amn->amn_success_threshold *= 2;
282				if (amn->amn_success_threshold >
283				    amrr->amrr_max_success_threshold)
284					amn->amn_success_threshold =
285					    amrr->amrr_max_success_threshold;
286			} else {
287				amn->amn_success_threshold =
288				    amrr->amrr_min_success_threshold;
289			}
290			rix--;
291			IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
292			    "AMRR decreasing rate %d (txcnt=%d retrycnt=%d)",
293			    rs->rs_rates[rix] & IEEE80211_RATE_VAL,
294			    amn->amn_txcnt, amn->amn_retrycnt);
295		}
296		amn->amn_recovery = 0;
297	}
298
299	/* reset counters */
300	amn->amn_txcnt = 0;
301	amn->amn_retrycnt = 0;
302
303	return rix;
304}
305
306/*
307 * Return the rate index to use in sending a data frame.
308 * Update our internal state if it's been long enough.
309 * If the rate changes we also update ni_txrate to match.
310 */
311static int
312amrr_rate(struct ieee80211_node *ni, void *arg __unused, uint32_t iarg __unused)
313{
314	struct ieee80211_amrr_node *amn = ni->ni_rctls;
315	struct ieee80211_amrr *amrr;
316	const struct ieee80211_rateset *rs = NULL;
317	int rix;
318
319	/* XXX should return -1 here, but drivers may not expect this... */
320	if (!amn)
321	{
322		ni->ni_txrate = ni->ni_rates.rs_rates[0];
323		return 0;
324	}
325
326	amrr = amn->amn_amrr;
327
328	/* 11n or not? Pick the right rateset */
329	if (amrr_node_is_11n(ni)) {
330		/* XXX ew */
331		rs = (struct ieee80211_rateset *) &ni->ni_htrates;
332	} else {
333		rs = &ni->ni_rates;
334	}
335
336	if (is_enough(amn) && (ticks - amn->amn_ticks) > amrr->amrr_interval) {
337		rix = amrr_update(amrr, amn, ni);
338		if (rix != amn->amn_rix) {
339			/* update public rate */
340			ni->ni_txrate = rs->rs_rates[rix];
341			/* XXX strip basic rate flag from txrate, if non-11n */
342			if (amrr_node_is_11n(ni))
343				ni->ni_txrate |= IEEE80211_RATE_MCS;
344			else
345				ni->ni_txrate &= IEEE80211_RATE_VAL;
346			amn->amn_rix = rix;
347		}
348		amn->amn_ticks = ticks;
349	} else
350		rix = amn->amn_rix;
351	return rix;
352}
353
354/*
355 * Update statistics with tx complete status.  Ok is non-zero
356 * if the packet is known to be ACK'd.  Retries has the number
357 * retransmissions (i.e. xmit attempts - 1).
358 */
359static void
360amrr_tx_complete(const struct ieee80211vap *vap,
361    const struct ieee80211_node *ni, int ok,
362    void *arg1, void *arg2 __unused)
363{
364	struct ieee80211_amrr_node *amn = ni->ni_rctls;
365	int retries = *(int *)arg1;
366
367	if (!amn)
368		return;
369
370	amn->amn_txcnt++;
371	if (ok)
372		amn->amn_success++;
373	amn->amn_retrycnt += retries;
374}
375
376/*
377 * Set tx count/retry statistics explicitly.  Intended for
378 * drivers that poll the device for statistics maintained
379 * in the device.
380 */
381static void
382amrr_tx_update(const struct ieee80211vap *vap, const struct ieee80211_node *ni,
383    void *arg1, void *arg2, void *arg3)
384{
385	struct ieee80211_amrr_node *amn = ni->ni_rctls;
386	int txcnt = *(int *)arg1, success = *(int *)arg2, retrycnt = *(int *)arg3;
387
388	amn->amn_txcnt = txcnt;
389	amn->amn_success = success;
390	amn->amn_retrycnt = retrycnt;
391}
392
393static int
394amrr_sysctl_interval(SYSCTL_HANDLER_ARGS)
395{
396	struct ieee80211vap *vap = arg1;
397	struct ieee80211_amrr *amrr = vap->iv_rs;
398	int msecs, error;
399
400	if (!amrr)
401		return ENOMEM;
402
403	msecs = ticks_to_msecs(amrr->amrr_interval);
404	error = sysctl_handle_int(oidp, &msecs, 0, req);
405	if (error || !req->newptr)
406		return error;
407	amrr_setinterval(vap, msecs);
408	return 0;
409}
410
411static void
412amrr_sysctlattach(struct ieee80211vap *vap,
413    struct sysctl_ctx_list *ctx, struct sysctl_oid *tree)
414{
415	struct ieee80211_amrr *amrr = vap->iv_rs;
416
417	if (!amrr)
418		return;
419
420	SYSCTL_ADD_PROC(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
421	    "amrr_rate_interval", CTLTYPE_INT | CTLFLAG_RW, vap,
422	    0, amrr_sysctl_interval, "I", "amrr operation interval (ms)");
423	/* XXX bounds check values */
424	SYSCTL_ADD_UINT(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
425	    "amrr_max_sucess_threshold", CTLFLAG_RW,
426	    &amrr->amrr_max_success_threshold, 0, "");
427	SYSCTL_ADD_UINT(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
428	    "amrr_min_sucess_threshold", CTLFLAG_RW,
429	    &amrr->amrr_min_success_threshold, 0, "");
430}
431