xref: /freebsd/sys/net80211/ieee80211_amrr.c (revision 15c433351f54e7cd5bec8d36c8e89e6a7fa55b26)
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$");
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/malloc.h>
37 #include <sys/module.h>
38 #include <sys/socket.h>
39 #include <sys/sysctl.h>
40 
41 #include <net/if.h>
42 #include <net/if_var.h>
43 #include <net/if_media.h>
44 #include <net/ethernet.h>
45 
46 #ifdef INET
47 #include <netinet/in.h>
48 #include <netinet/if_ether.h>
49 #endif
50 
51 #include <net80211/ieee80211_var.h>
52 #include <net80211/ieee80211_ht.h>
53 #include <net80211/ieee80211_amrr.h>
54 #include <net80211/ieee80211_ratectl.h>
55 
56 #define is_success(amn)	\
57 	((amn)->amn_retrycnt < (amn)->amn_txcnt / 10)
58 #define is_failure(amn)	\
59 	((amn)->amn_retrycnt > (amn)->amn_txcnt / 3)
60 #define is_enough(amn)		\
61 	((amn)->amn_txcnt > 10)
62 
63 static void	amrr_setinterval(const struct ieee80211vap *, int);
64 static void	amrr_init(struct ieee80211vap *);
65 static void	amrr_deinit(struct ieee80211vap *);
66 static void	amrr_node_init(struct ieee80211_node *);
67 static void	amrr_node_deinit(struct ieee80211_node *);
68 static int	amrr_update(struct ieee80211_amrr *,
69     			struct ieee80211_amrr_node *, struct ieee80211_node *);
70 static int	amrr_rate(struct ieee80211_node *, void *, uint32_t);
71 static void	amrr_tx_complete(const struct ieee80211vap *,
72     			const struct ieee80211_node *, int,
73 			void *, void *);
74 static void	amrr_tx_update(const struct ieee80211vap *vap,
75 			const struct ieee80211_node *, void *, void *, void *);
76 static void	amrr_sysctlattach(struct ieee80211vap *,
77 			struct sysctl_ctx_list *, struct sysctl_oid *);
78 
79 /* number of references from net80211 layer */
80 static	int nrefs = 0;
81 
82 static const struct ieee80211_ratectl amrr = {
83 	.ir_name	= "amrr",
84 	.ir_attach	= NULL,
85 	.ir_detach	= NULL,
86 	.ir_init	= amrr_init,
87 	.ir_deinit	= amrr_deinit,
88 	.ir_node_init	= amrr_node_init,
89 	.ir_node_deinit	= amrr_node_deinit,
90 	.ir_rate	= amrr_rate,
91 	.ir_tx_complete	= amrr_tx_complete,
92 	.ir_tx_update	= amrr_tx_update,
93 	.ir_setinterval	= amrr_setinterval,
94 };
95 IEEE80211_RATECTL_MODULE(amrr, 1);
96 IEEE80211_RATECTL_ALG(amrr, IEEE80211_RATECTL_AMRR, amrr);
97 
98 static void
99 amrr_setinterval(const struct ieee80211vap *vap, int msecs)
100 {
101 	struct ieee80211_amrr *amrr = vap->iv_rs;
102 	int t;
103 
104 	if (msecs < 100)
105 		msecs = 100;
106 	t = msecs_to_ticks(msecs);
107 	amrr->amrr_interval = (t < 1) ? 1 : t;
108 }
109 
110 static void
111 amrr_init(struct ieee80211vap *vap)
112 {
113 	struct ieee80211_amrr *amrr;
114 
115 	KASSERT(vap->iv_rs == NULL, ("%s called multiple times", __func__));
116 
117 	amrr = vap->iv_rs = IEEE80211_MALLOC(sizeof(struct ieee80211_amrr),
118 	    M_80211_RATECTL, IEEE80211_M_NOWAIT | IEEE80211_M_ZERO);
119 	if (amrr == NULL) {
120 		if_printf(vap->iv_ifp, "couldn't alloc ratectl structure\n");
121 		return;
122 	}
123 	amrr->amrr_min_success_threshold = IEEE80211_AMRR_MIN_SUCCESS_THRESHOLD;
124 	amrr->amrr_max_success_threshold = IEEE80211_AMRR_MAX_SUCCESS_THRESHOLD;
125 	amrr_setinterval(vap, 500 /* ms */);
126 	amrr_sysctlattach(vap, vap->iv_sysctl, vap->iv_oid);
127 }
128 
129 static void
130 amrr_deinit(struct ieee80211vap *vap)
131 {
132 	IEEE80211_FREE(vap->iv_rs, M_80211_RATECTL);
133 }
134 
135 /*
136  * Return whether 11n rates are possible.
137  *
138  * Some 11n devices may return HT information but no HT rates.
139  * Thus, we shouldn't treat them as an 11n node.
140  */
141 static int
142 amrr_node_is_11n(struct ieee80211_node *ni)
143 {
144 
145 	if (ni->ni_chan == NULL)
146 		return (0);
147 	if (ni->ni_chan == IEEE80211_CHAN_ANYC)
148 		return (0);
149 	if (IEEE80211_IS_CHAN_HT(ni->ni_chan) && ni->ni_htrates.rs_nrates == 0)
150 		return (0);
151 	return (IEEE80211_IS_CHAN_HT(ni->ni_chan));
152 }
153 
154 static void
155 amrr_node_init(struct ieee80211_node *ni)
156 {
157 	const struct ieee80211_rateset *rs = NULL;
158 	struct ieee80211vap *vap = ni->ni_vap;
159 	struct ieee80211_amrr *amrr = vap->iv_rs;
160 	struct ieee80211_amrr_node *amn;
161 	uint8_t rate;
162 
163 	if (ni->ni_rctls == NULL) {
164 		ni->ni_rctls = amn = IEEE80211_MALLOC(sizeof(struct ieee80211_amrr_node),
165 		    M_80211_RATECTL, IEEE80211_M_NOWAIT | IEEE80211_M_ZERO);
166 		if (amn == NULL) {
167 			if_printf(vap->iv_ifp, "couldn't alloc per-node ratectl "
168 			    "structure\n");
169 			return;
170 		}
171 	} else
172 		amn = ni->ni_rctls;
173 	amn->amn_amrr = amrr;
174 	amn->amn_success = 0;
175 	amn->amn_recovery = 0;
176 	amn->amn_txcnt = amn->amn_retrycnt = 0;
177 	amn->amn_success_threshold = amrr->amrr_min_success_threshold;
178 
179 	/* 11n or not? Pick the right rateset */
180 	if (amrr_node_is_11n(ni)) {
181 		/* XXX ew */
182 		IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
183 		    "%s: 11n node", __func__);
184 		rs = (struct ieee80211_rateset *) &ni->ni_htrates;
185 	} else {
186 		IEEE80211_NOTE(ni->ni_vap, IEEE80211_MSG_RATECTL, ni,
187 		    "%s: non-11n node", __func__);
188 		rs = &ni->ni_rates;
189 	}
190 
191 	/* Initial rate - lowest */
192 	rate = rs->rs_rates[0];
193 
194 	/* XXX clear the basic rate flag if it's not 11n */
195 	if (! amrr_node_is_11n(ni))
196 		rate &= IEEE80211_RATE_VAL;
197 
198 	/* pick initial rate from the rateset - HT or otherwise */
199 	/* Pick something low that's likely to succeed */
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 */
204 		if (amrr_node_is_11n(ni)) {
205 			if ((rs->rs_rates[amn->amn_rix] & 0x1f) < 4)
206 				break;
207 		} else if ((rs->rs_rates[amn->amn_rix] & IEEE80211_RATE_VAL) <= 72)
208 			break;
209 	}
210 	rate = rs->rs_rates[amn->amn_rix] & IEEE80211_RATE_VAL;
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 
226 static void
227 amrr_node_deinit(struct ieee80211_node *ni)
228 {
229 	IEEE80211_FREE(ni->ni_rctls, M_80211_RATECTL);
230 }
231 
232 static int
233 amrr_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  */
311 static int
312 amrr_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 = amn->amn_amrr;
316 	const struct ieee80211_rateset *rs = NULL;
317 	int rix;
318 
319 	/* 11n or not? Pick the right rateset */
320 	if (amrr_node_is_11n(ni)) {
321 		/* XXX ew */
322 		rs = (struct ieee80211_rateset *) &ni->ni_htrates;
323 	} else {
324 		rs = &ni->ni_rates;
325 	}
326 
327 	if (is_enough(amn) && (ticks - amn->amn_ticks) > amrr->amrr_interval) {
328 		rix = amrr_update(amrr, amn, ni);
329 		if (rix != amn->amn_rix) {
330 			/* update public rate */
331 			ni->ni_txrate = rs->rs_rates[rix];
332 			/* XXX strip basic rate flag from txrate, if non-11n */
333 			if (amrr_node_is_11n(ni))
334 				ni->ni_txrate |= IEEE80211_RATE_MCS;
335 			else
336 				ni->ni_txrate &= IEEE80211_RATE_VAL;
337 			amn->amn_rix = rix;
338 		}
339 		amn->amn_ticks = ticks;
340 	} else
341 		rix = amn->amn_rix;
342 	return rix;
343 }
344 
345 /*
346  * Update statistics with tx complete status.  Ok is non-zero
347  * if the packet is known to be ACK'd.  Retries has the number
348  * retransmissions (i.e. xmit attempts - 1).
349  */
350 static void
351 amrr_tx_complete(const struct ieee80211vap *vap,
352     const struct ieee80211_node *ni, int ok,
353     void *arg1, void *arg2 __unused)
354 {
355 	struct ieee80211_amrr_node *amn = ni->ni_rctls;
356 	int retries = *(int *)arg1;
357 
358 	amn->amn_txcnt++;
359 	if (ok)
360 		amn->amn_success++;
361 	amn->amn_retrycnt += retries;
362 }
363 
364 /*
365  * Set tx count/retry statistics explicitly.  Intended for
366  * drivers that poll the device for statistics maintained
367  * in the device.
368  */
369 static void
370 amrr_tx_update(const struct ieee80211vap *vap, const struct ieee80211_node *ni,
371     void *arg1, void *arg2, void *arg3)
372 {
373 	struct ieee80211_amrr_node *amn = ni->ni_rctls;
374 	int txcnt = *(int *)arg1, success = *(int *)arg2, retrycnt = *(int *)arg3;
375 
376 	amn->amn_txcnt = txcnt;
377 	amn->amn_success = success;
378 	amn->amn_retrycnt = retrycnt;
379 }
380 
381 static int
382 amrr_sysctl_interval(SYSCTL_HANDLER_ARGS)
383 {
384 	struct ieee80211vap *vap = arg1;
385 	struct ieee80211_amrr *amrr = vap->iv_rs;
386 	int msecs = ticks_to_msecs(amrr->amrr_interval);
387 	int error;
388 
389 	error = sysctl_handle_int(oidp, &msecs, 0, req);
390 	if (error || !req->newptr)
391 		return error;
392 	amrr_setinterval(vap, msecs);
393 	return 0;
394 }
395 
396 static void
397 amrr_sysctlattach(struct ieee80211vap *vap,
398     struct sysctl_ctx_list *ctx, struct sysctl_oid *tree)
399 {
400 	struct ieee80211_amrr *amrr = vap->iv_rs;
401 
402 	SYSCTL_ADD_PROC(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
403 	    "amrr_rate_interval", CTLTYPE_INT | CTLFLAG_RW, vap,
404 	    0, amrr_sysctl_interval, "I", "amrr operation interval (ms)");
405 	/* XXX bounds check values */
406 	SYSCTL_ADD_UINT(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
407 	    "amrr_max_sucess_threshold", CTLFLAG_RW,
408 	    &amrr->amrr_max_success_threshold, 0, "");
409 	SYSCTL_ADD_UINT(ctx, SYSCTL_CHILDREN(tree), OID_AUTO,
410 	    "amrr_min_sucess_threshold", CTLFLAG_RW,
411 	    &amrr->amrr_min_success_threshold, 0, "");
412 }
413