[infiniband] Use "%#lx" as format specifier for queue pair numbers
[ipxe.git] / src / net / 80211 / rc80211.c
1 /*
2 * Simple 802.11 rate-control algorithm for iPXE.
3 *
4 * Copyright (c) 2009 Joshua Oreman <oremanj@rwcr.net>.
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License as
8 * published by the Free Software Foundation; either version 2 of the
9 * License, or any later version.
10 *
11 * This program is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
19 * 02110-1301, USA.
20 */
21
22 FILE_LICENCE ( GPL2_OR_LATER );
23
24 #include <stdlib.h>
25 #include <ipxe/net80211.h>
26
27 /**
28 * @file
29 *
30 * Simple 802.11 rate-control algorithm
31 */
32
33 /** @page rc80211 Rate control philosophy
34 *
35 * We want to maximize our transmission speed, to the extent that we
36 * can do that without dropping undue numbers of packets. We also
37 * don't want to take up very much code space, so our algorithm has to
38 * be pretty simple
39 *
40 * When we receive a packet, we know what rate it was transmitted at,
41 * and whether it had to be retransmitted to get to us.
42 *
43 * When we send a packet, we hear back how many times it had to be
44 * retried to get through, and whether it got through at all.
45 *
46 * Indications of TX success are more reliable than RX success, but RX
47 * information helps us know where to start.
48 *
49 * To handle all of this, we keep for each rate and each direction (TX
50 * and RX separately) some state information for the most recent
51 * packets on that rate and the number of packets for which we have
52 * information. The state is a 32-bit unsigned integer in which two
53 * bits represent a packet: 11 if it went through well, 10 if it went
54 * through with one retry, 01 if it went through with more than one
55 * retry, or 00 if it didn't go through at all. We define the
56 * "goodness" for a particular (rate, direction) combination as the
57 * sum of all the 2-bit fields, times 33, divided by the number of
58 * 2-bit fields containing valid information (16 except when we're
59 * starting out). The number produced is between 0 and 99; we use -1
60 * for rates with less than 4 RX packets or 1 TX, as an indicator that
61 * we do not have enough information to rely on them.
62 *
63 * In deciding which rates are best, we find the weighted average of
64 * TX and RX goodness, where the weighting is by number of packets
65 * with data and TX packets are worth 4 times as much as RX packets.
66 * The weighted average is called "net goodness" and is also a number
67 * between 0 and 99. If 3 consecutive packets fail transmission
68 * outright, we automatically ratchet down the rate; otherwise, we
69 * switch to the best rate whenever the current rate's goodness falls
70 * below some threshold, and try increasing our rate when the goodness
71 * is very high.
72 *
73 * This system is optimized for iPXE's style of usage. Because normal
74 * operation always involves receiving something, we'll make our way
75 * to the best rate pretty quickly. We tend to follow the lead of the
76 * sending AP in choosing rates, but we won't use rates for long that
77 * don't work well for us in transmission. We assume iPXE won't be
78 * running for long enough that rate patterns will change much, so we
79 * don't have to keep time counters or the like. And if this doesn't
80 * work well in practice there are many ways it could be tweaked.
81 *
82 * To avoid staying at 1Mbps for a long time, we don't track any
83 * transmitted packets until we've set our rate based on received
84 * packets.
85 */
86
87 /** Two-bit packet status indicator for a packet with no retries */
88 #define RC_PKT_OK 0x3
89
90 /** Two-bit packet status indicator for a packet with one retry */
91 #define RC_PKT_RETRIED_ONCE 0x2
92
93 /** Two-bit packet status indicator for a TX packet with multiple retries
94 *
95 * It is not possible to tell whether an RX packet had one or multiple
96 * retries; we rely instead on the fact that failed RX packets won't
97 * get to us at all, so if we receive a lot of RX packets on a certain
98 * rate it must be pretty good.
99 */
100 #define RC_PKT_RETRIED_MULTI 0x1
101
102 /** Two-bit packet status indicator for a TX packet that was never ACKed
103 *
104 * It is not possible to tell whether an RX packet was setn if it
105 * didn't get through to us, but if we don't see one we won't increase
106 * the goodness for its rate. This asymmetry is part of why TX packets
107 * are weighted much more heavily than RX.
108 */
109 #define RC_PKT_FAILED 0x0
110
111 /** Number of times to weight TX packets more heavily than RX packets */
112 #define RC_TX_FACTOR 4
113
114 /** Number of consecutive failed TX packets that cause an automatic rate drop */
115 #define RC_TX_EMERG_FAIL 3
116
117 /** Minimum net goodness below which we will search for a better rate */
118 #define RC_GOODNESS_MIN 85
119
120 /** Maximum net goodness above which we will try to increase our rate */
121 #define RC_GOODNESS_MAX 95
122
123 /** Minimum (num RX + @c RC_TX_FACTOR * num TX) to use a certain rate */
124 #define RC_UNCERTAINTY_THRESH 4
125
126 /** TX direction */
127 #define TX 0
128
129 /** RX direction */
130 #define RX 1
131
132 /** A rate control context */
133 struct rc80211_ctx
134 {
135 /** Goodness state for each rate, TX and RX */
136 u32 goodness[2][NET80211_MAX_RATES];
137
138 /** Number of packets recorded for each rate */
139 u8 count[2][NET80211_MAX_RATES];
140
141 /** Indication of whether we've set the device rate yet */
142 int started;
143
144 /** Counter of all packets sent and received */
145 int packets;
146 };
147
148 /**
149 * Initialize rate-control algorithm
150 *
151 * @v dev 802.11 device
152 * @ret ctx Rate-control context, to be stored in @c dev->rctl
153 */
154 struct rc80211_ctx * rc80211_init ( struct net80211_device *dev __unused )
155 {
156 struct rc80211_ctx *ret = zalloc ( sizeof ( *ret ) );
157 return ret;
158 }
159
160 /**
161 * Calculate net goodness for a certain rate
162 *
163 * @v ctx Rate-control context
164 * @v rate_idx Index of rate to calculate net goodness for
165 */
166 static int rc80211_calc_net_goodness ( struct rc80211_ctx *ctx,
167 int rate_idx )
168 {
169 int sum[2], num[2], dir, pkt;
170
171 for ( dir = 0; dir < 2; dir++ ) {
172 u32 good = ctx->goodness[dir][rate_idx];
173
174 num[dir] = ctx->count[dir][rate_idx];
175 sum[dir] = 0;
176
177 for ( pkt = 0; pkt < num[dir]; pkt++ )
178 sum[dir] += ( good >> ( 2 * pkt ) ) & 0x3;
179 }
180
181 if ( ( num[TX] * RC_TX_FACTOR + num[RX] ) < RC_UNCERTAINTY_THRESH )
182 return -1;
183
184 return ( 33 * ( sum[TX] * RC_TX_FACTOR + sum[RX] ) /
185 ( num[TX] * RC_TX_FACTOR + num[RX] ) );
186 }
187
188 /**
189 * Determine the best rate to switch to and return it
190 *
191 * @v dev 802.11 device
192 * @ret rate_idx Index of the best rate to switch to
193 */
194 static int rc80211_pick_best ( struct net80211_device *dev )
195 {
196 struct rc80211_ctx *ctx = dev->rctl;
197 int best_net_good = 0, best_rate = -1, i;
198
199 for ( i = 0; i < dev->nr_rates; i++ ) {
200 int net_good = rc80211_calc_net_goodness ( ctx, i );
201
202 if ( net_good > best_net_good ||
203 ( best_net_good > RC_GOODNESS_MIN &&
204 net_good > RC_GOODNESS_MIN ) ) {
205 best_net_good = net_good;
206 best_rate = i;
207 }
208 }
209
210 if ( best_rate >= 0 ) {
211 int old_good = rc80211_calc_net_goodness ( ctx, dev->rate );
212 if ( old_good != best_net_good )
213 DBGC ( ctx, "802.11 RC %p switching from goodness "
214 "%d to %d\n", ctx, old_good, best_net_good );
215
216 ctx->started = 1;
217 return best_rate;
218 }
219
220 return dev->rate;
221 }
222
223 /**
224 * Set 802.11 device rate
225 *
226 * @v dev 802.11 device
227 * @v rate_idx Index of rate to switch to
228 *
229 * This is a thin wrapper around net80211_set_rate_idx to insert a
230 * debugging message where appropriate.
231 */
232 static inline void rc80211_set_rate ( struct net80211_device *dev,
233 int rate_idx )
234 {
235 DBGC ( dev->rctl, "802.11 RC %p changing rate %d->%d Mbps\n", dev->rctl,
236 dev->rates[dev->rate] / 10, dev->rates[rate_idx] / 10 );
237
238 net80211_set_rate_idx ( dev, rate_idx );
239 }
240
241 /**
242 * Check rate-control state and change rate if necessary
243 *
244 * @v dev 802.11 device
245 */
246 static void rc80211_maybe_set_new ( struct net80211_device *dev )
247 {
248 struct rc80211_ctx *ctx = dev->rctl;
249 int net_good;
250
251 net_good = rc80211_calc_net_goodness ( ctx, dev->rate );
252
253 if ( ! ctx->started ) {
254 rc80211_set_rate ( dev, rc80211_pick_best ( dev ) );
255 return;
256 }
257
258 if ( net_good < 0 ) /* insufficient data */
259 return;
260
261 if ( net_good > RC_GOODNESS_MAX && dev->rate + 1 < dev->nr_rates ) {
262 int higher = rc80211_calc_net_goodness ( ctx, dev->rate + 1 );
263 if ( higher > net_good || higher < 0 )
264 rc80211_set_rate ( dev, dev->rate + 1 );
265 else
266 rc80211_set_rate ( dev, rc80211_pick_best ( dev ) );
267 }
268
269 if ( net_good < RC_GOODNESS_MIN ) {
270 rc80211_set_rate ( dev, rc80211_pick_best ( dev ) );
271 }
272 }
273
274 /**
275 * Update rate-control state
276 *
277 * @v dev 802.11 device
278 * @v direction One of the direction constants TX or RX
279 * @v rate_idx Index of rate at which packet was sent or received
280 * @v retries Number of times packet was retried before success
281 * @v failed If nonzero, the packet failed to get through
282 */
283 static void rc80211_update ( struct net80211_device *dev, int direction,
284 int rate_idx, int retries, int failed )
285 {
286 struct rc80211_ctx *ctx = dev->rctl;
287 u32 goodness = ctx->goodness[direction][rate_idx];
288
289 if ( ctx->count[direction][rate_idx] < 16 )
290 ctx->count[direction][rate_idx]++;
291
292 goodness <<= 2;
293 if ( failed )
294 goodness |= RC_PKT_FAILED;
295 else if ( retries > 1 )
296 goodness |= RC_PKT_RETRIED_MULTI;
297 else if ( retries )
298 goodness |= RC_PKT_RETRIED_ONCE;
299 else
300 goodness |= RC_PKT_OK;
301
302 ctx->goodness[direction][rate_idx] = goodness;
303
304 ctx->packets++;
305
306 rc80211_maybe_set_new ( dev );
307 }
308
309 /**
310 * Update rate-control state for transmitted packet
311 *
312 * @v dev 802.11 device
313 * @v retries Number of times packet was transmitted before success
314 * @v rc Return status code for transmission
315 */
316 void rc80211_update_tx ( struct net80211_device *dev, int retries, int rc )
317 {
318 struct rc80211_ctx *ctx = dev->rctl;
319
320 if ( ! ctx->started )
321 return;
322
323 rc80211_update ( dev, TX, dev->rate, retries, rc );
324
325 /* Check if the last RC_TX_EMERG_FAIL packets have all failed */
326 if ( ! ( ctx->goodness[TX][dev->rate] &
327 ( ( 1 << ( 2 * RC_TX_EMERG_FAIL ) ) - 1 ) ) ) {
328 if ( dev->rate == 0 )
329 DBGC ( dev->rctl, "802.11 RC %p saw %d consecutive "
330 "failed TX, but cannot lower rate any further\n",
331 dev->rctl, RC_TX_EMERG_FAIL );
332 else {
333 DBGC ( dev->rctl, "802.11 RC %p lowering rate (%d->%d "
334 "Mbps) due to %d consecutive TX failures\n",
335 dev->rctl, dev->rates[dev->rate] / 10,
336 dev->rates[dev->rate - 1] / 10,
337 RC_TX_EMERG_FAIL );
338
339 rc80211_set_rate ( dev, dev->rate - 1 );
340 }
341 }
342 }
343
344 /**
345 * Update rate-control state for received packet
346 *
347 * @v dev 802.11 device
348 * @v retry Whether the received packet had been retransmitted
349 * @v rate Rate at which packet was received, in 100 kbps units
350 */
351 void rc80211_update_rx ( struct net80211_device *dev, int retry, u16 rate )
352 {
353 int ridx;
354
355 for ( ridx = 0; ridx < dev->nr_rates && dev->rates[ridx] != rate;
356 ridx++ )
357 ;
358 if ( ridx >= dev->nr_rates )
359 return; /* couldn't find the rate */
360
361 rc80211_update ( dev, RX, ridx, retry, 0 );
362 }
363
364 /**
365 * Free rate-control context
366 *
367 * @v ctx Rate-control context
368 */
369 void rc80211_free ( struct rc80211_ctx *ctx )
370 {
371 free ( ctx );
372 }