← Back to branch summary

~ubuntu-branches/ubuntu/trusty/grub2/trusty

« back to all changes in this revision

Viewing changes to debian/grub-extras/disabled/gpxe/src/net/80211/rc80211.c

  • Committer: Package Import Robot
  • Author(s): Colin Watson
  • Date: 2014-01-16 15:18:04 UTC
  • mfrom: (17.6.38 experimental)
  • Revision ID: package-import@ubuntu.com-20140116151804-3foouk7fpqcq3sxx
Tags: 2.02~beta2-2
* Convert patch handling to git-dpm.
* Add bi-endian support to ELF parser (Tomohiro B Berry).
* Adjust restore_mkdevicemap.patch to mark get_kfreebsd_version as static,
  to appease "gcc -Werror=missing-prototypes".
* Cherry-pick from upstream:
  - Change grub-macbless' manual page section to 8.
* Install grub-glue-efi, grub-macbless, grub-render-label, and
  grub-syslinux2cfg.
* grub-shell: Pass -no-pad to xorriso when building floppy images.

Show diffs side-by-side

added added

removed removed

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