diff options
author | Linus Torvalds <torvalds@linux-foundation.org> | 2013-05-02 01:08:52 +0400 |
---|---|---|
committer | Linus Torvalds <torvalds@linux-foundation.org> | 2013-05-02 01:08:52 +0400 |
commit | 73287a43cc79ca06629a88d1a199cd283f42456a (patch) | |
tree | acf4456e260115bea77ee31a29f10ce17f0db45c /net/mac80211/rc80211_minstrel.c | |
parent | 251df49db3327c64bf917bfdba94491fde2b4ee0 (diff) | |
parent | 20074f357da4a637430aec2879c9d864c5d2c23c (diff) | |
download | linux-73287a43cc79ca06629a88d1a199cd283f42456a.tar.xz |
Merge git://git.kernel.org/pub/scm/linux/kernel/git/davem/net-next
Pull networking updates from David Miller:
"Highlights (1721 non-merge commits, this has to be a record of some
sort):
1) Add 'random' mode to team driver, from Jiri Pirko and Eric
Dumazet.
2) Make it so that any driver that supports configuration of multiple
MAC addresses can provide the forwarding database add and del
calls by providing a default implementation and hooking that up if
the driver doesn't have an explicit set of handlers. From Vlad
Yasevich.
3) Support GSO segmentation over tunnels and other encapsulating
devices such as VXLAN, from Pravin B Shelar.
4) Support L2 GRE tunnels in the flow dissector, from Michael Dalton.
5) Implement Tail Loss Probe (TLP) detection in TCP, from Nandita
Dukkipati.
6) In the PHY layer, allow supporting wake-on-lan in situations where
the PHY registers have to be written for it to be configured.
Use it to support wake-on-lan in mv643xx_eth.
From Michael Stapelberg.
7) Significantly improve firewire IPV6 support, from YOSHIFUJI
Hideaki.
8) Allow multiple packets to be sent in a single transmission using
network coding in batman-adv, from Martin Hundebøll.
9) Add support for T5 cxgb4 chips, from Santosh Rastapur.
10) Generalize the VXLAN forwarding tables so that there is more
flexibility in configurating various aspects of the endpoints.
From David Stevens.
11) Support RSS and TSO in hardware over GRE tunnels in bxn2x driver,
from Dmitry Kravkov.
12) Zero copy support in nfnelink_queue, from Eric Dumazet and Pablo
Neira Ayuso.
13) Start adding networking selftests.
14) In situations of overload on the same AF_PACKET fanout socket, or
per-cpu packet receive queue, minimize drop by distributing the
load to other cpus/fanouts. From Willem de Bruijn and Eric
Dumazet.
15) Add support for new payload offset BPF instruction, from Daniel
Borkmann.
16) Convert several drivers over to mdoule_platform_driver(), from
Sachin Kamat.
17) Provide a minimal BPF JIT image disassembler userspace tool, from
Daniel Borkmann.
18) Rewrite F-RTO implementation in TCP to match the final
specification of it in RFC4138 and RFC5682. From Yuchung Cheng.
19) Provide netlink socket diag of netlink sockets ("Yo dawg, I hear
you like netlink, so I implemented netlink dumping of netlink
sockets.") From Andrey Vagin.
20) Remove ugly passing of rtnetlink attributes into rtnl_doit
functions, from Thomas Graf.
21) Allow userspace to be able to see if a configuration change occurs
in the middle of an address or device list dump, from Nicolas
Dichtel.
22) Support RFC3168 ECN protection for ipv6 fragments, from Hannes
Frederic Sowa.
23) Increase accuracy of packet length used by packet scheduler, from
Jason Wang.
24) Beginning set of changes to make ipv4/ipv6 fragment handling more
scalable and less susceptible to overload and locking contention,
from Jesper Dangaard Brouer.
25) Get rid of using non-type-safe NLMSG_* macros and use nlmsg_*()
instead. From Hong Zhiguo.
26) Optimize route usage in IPVS by avoiding reference counting where
possible, from Julian Anastasov.
27) Convert IPVS schedulers to RCU, also from Julian Anastasov.
28) Support cpu fanouts in xt_NFQUEUE netfilter target, from Holger
Eitzenberger.
29) Network namespace support for nf_log, ebt_log, xt_LOG, ipt_ULOG,
nfnetlink_log, and nfnetlink_queue. From Gao feng.
30) Implement RFC3168 ECN protection, from Hannes Frederic Sowa.
31) Support several new r8169 chips, from Hayes Wang.
32) Support tokenized interface identifiers in ipv6, from Daniel
Borkmann.
33) Use usbnet_link_change() helper in USB net driver, from Ming Lei.
34) Add 802.1ad vlan offload support, from Patrick McHardy.
35) Support mmap() based netlink communication, also from Patrick
McHardy.
36) Support HW timestamping in mlx4 driver, from Amir Vadai.
37) Rationalize AF_PACKET packet timestamping when transmitting, from
Willem de Bruijn and Daniel Borkmann.
38) Bring parity to what's provided by /proc/net/packet socket dumping
and the info provided by netlink socket dumping of AF_PACKET
sockets. From Nicolas Dichtel.
39) Fix peeking beyond zero sized SKBs in AF_UNIX, from Benjamin
Poirier"
* git://git.kernel.org/pub/scm/linux/kernel/git/davem/net-next: (1722 commits)
filter: fix va_list build error
af_unix: fix a fatal race with bit fields
bnx2x: Prevent memory leak when cnic is absent
bnx2x: correct reading of speed capabilities
net: sctp: attribute printl with __printf for gcc fmt checks
netlink: kconfig: move mmap i/o into netlink kconfig
netpoll: convert mutex into a semaphore
netlink: Fix skb ref counting.
net_sched: act_ipt forward compat with xtables
mlx4_en: fix a build error on 32bit arches
Revert "bnx2x: allow nvram test to run when device is down"
bridge: avoid OOPS if root port not found
drivers: net: cpsw: fix kernel warn on cpsw irq enable
sh_eth: use random MAC address if no valid one supplied
3c509.c: call SET_NETDEV_DEV for all device types (ISA/ISAPnP/EISA)
tg3: fix to append hardware time stamping flags
unix/stream: fix peeking with an offset larger than data in queue
unix/dgram: fix peeking with an offset larger than data in queue
unix/dgram: peek beyond 0-sized skbs
openvswitch: Remove unneeded ovs_netdev_get_ifindex()
...
Diffstat (limited to 'net/mac80211/rc80211_minstrel.c')
-rw-r--r-- | net/mac80211/rc80211_minstrel.c | 342 |
1 files changed, 193 insertions, 149 deletions
diff --git a/net/mac80211/rc80211_minstrel.c b/net/mac80211/rc80211_minstrel.c index eea45a2c7c35..ac7ef5414bde 100644 --- a/net/mac80211/rc80211_minstrel.c +++ b/net/mac80211/rc80211_minstrel.c @@ -55,7 +55,6 @@ #include "rate.h" #include "rc80211_minstrel.h" -#define SAMPLE_COLUMNS 10 #define SAMPLE_TBL(_mi, _idx, _col) \ _mi->sample_table[(_idx * SAMPLE_COLUMNS) + _col] @@ -70,16 +69,75 @@ rix_to_ndx(struct minstrel_sta_info *mi, int rix) return i; } +/* find & sort topmost throughput rates */ +static inline void +minstrel_sort_best_tp_rates(struct minstrel_sta_info *mi, int i, u8 *tp_list) +{ + int j = MAX_THR_RATES; + + while (j > 0 && mi->r[i].cur_tp > mi->r[tp_list[j - 1]].cur_tp) + j--; + if (j < MAX_THR_RATES - 1) + memmove(&tp_list[j + 1], &tp_list[j], MAX_THR_RATES - (j + 1)); + if (j < MAX_THR_RATES) + tp_list[j] = i; +} + +static void +minstrel_set_rate(struct minstrel_sta_info *mi, struct ieee80211_sta_rates *ratetbl, + int offset, int idx) +{ + struct minstrel_rate *r = &mi->r[idx]; + + ratetbl->rate[offset].idx = r->rix; + ratetbl->rate[offset].count = r->adjusted_retry_count; + ratetbl->rate[offset].count_cts = r->retry_count_cts; + ratetbl->rate[offset].count_rts = r->retry_count_rtscts; +} + +static void +minstrel_update_rates(struct minstrel_priv *mp, struct minstrel_sta_info *mi) +{ + struct ieee80211_sta_rates *ratetbl; + int i = 0; + + ratetbl = kzalloc(sizeof(*ratetbl), GFP_ATOMIC); + if (!ratetbl) + return; + + /* Start with max_tp_rate */ + minstrel_set_rate(mi, ratetbl, i++, mi->max_tp_rate[0]); + + if (mp->hw->max_rates >= 3) { + /* At least 3 tx rates supported, use max_tp_rate2 next */ + minstrel_set_rate(mi, ratetbl, i++, mi->max_tp_rate[1]); + } + + if (mp->hw->max_rates >= 2) { + /* At least 2 tx rates supported, use max_prob_rate next */ + minstrel_set_rate(mi, ratetbl, i++, mi->max_prob_rate); + } + + /* Use lowest rate last */ + ratetbl->rate[i].idx = mi->lowest_rix; + ratetbl->rate[i].count = mp->max_retry; + ratetbl->rate[i].count_cts = mp->max_retry; + ratetbl->rate[i].count_rts = mp->max_retry; + + rate_control_set_rates(mp->hw, mi->sta, ratetbl); +} + static void minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi) { - u32 max_tp = 0, index_max_tp = 0, index_max_tp2 = 0; - u32 max_prob = 0, index_max_prob = 0; + u8 tmp_tp_rate[MAX_THR_RATES]; + u8 tmp_prob_rate = 0; u32 usecs; - u32 p; int i; - mi->stats_update = jiffies; + for (i=0; i < MAX_THR_RATES; i++) + tmp_tp_rate[i] = 0; + for (i = 0; i < mi->n_rates; i++) { struct minstrel_rate *mr = &mi->r[i]; @@ -87,27 +145,32 @@ minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi) if (!usecs) usecs = 1000000; - /* To avoid rounding issues, probabilities scale from 0 (0%) - * to 18000 (100%) */ - if (mr->attempts) { - p = (mr->success * 18000) / mr->attempts; + if (unlikely(mr->attempts > 0)) { + mr->sample_skipped = 0; + mr->cur_prob = MINSTREL_FRAC(mr->success, mr->attempts); mr->succ_hist += mr->success; mr->att_hist += mr->attempts; - mr->cur_prob = p; - p = ((p * (100 - mp->ewma_level)) + (mr->probability * - mp->ewma_level)) / 100; - mr->probability = p; - mr->cur_tp = p * (1000000 / usecs); - } + mr->probability = minstrel_ewma(mr->probability, + mr->cur_prob, + EWMA_LEVEL); + } else + mr->sample_skipped++; mr->last_success = mr->success; mr->last_attempts = mr->attempts; mr->success = 0; mr->attempts = 0; + /* Update throughput per rate, reset thr. below 10% success */ + if (mr->probability < MINSTREL_FRAC(10, 100)) + mr->cur_tp = 0; + else + mr->cur_tp = mr->probability * (1000000 / usecs); + /* Sample less often below the 10% chance of success. * Sample less often above the 95% chance of success. */ - if ((mr->probability > 17100) || (mr->probability < 1800)) { + if (mr->probability > MINSTREL_FRAC(95, 100) || + mr->probability < MINSTREL_FRAC(10, 100)) { mr->adjusted_retry_count = mr->retry_count >> 1; if (mr->adjusted_retry_count > 2) mr->adjusted_retry_count = 2; @@ -118,35 +181,32 @@ minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi) } if (!mr->adjusted_retry_count) mr->adjusted_retry_count = 2; - } - for (i = 0; i < mi->n_rates; i++) { - struct minstrel_rate *mr = &mi->r[i]; - if (max_tp < mr->cur_tp) { - index_max_tp = i; - max_tp = mr->cur_tp; - } - if (max_prob < mr->probability) { - index_max_prob = i; - max_prob = mr->probability; + minstrel_sort_best_tp_rates(mi, i, tmp_tp_rate); + + /* To determine the most robust rate (max_prob_rate) used at + * 3rd mmr stage we distinct between two cases: + * (1) if any success probabilitiy >= 95%, out of those rates + * choose the maximum throughput rate as max_prob_rate + * (2) if all success probabilities < 95%, the rate with + * highest success probability is choosen as max_prob_rate */ + if (mr->probability >= MINSTREL_FRAC(95,100)) { + if (mr->cur_tp >= mi->r[tmp_prob_rate].cur_tp) + tmp_prob_rate = i; + } else { + if (mr->probability >= mi->r[tmp_prob_rate].probability) + tmp_prob_rate = i; } } - max_tp = 0; - for (i = 0; i < mi->n_rates; i++) { - struct minstrel_rate *mr = &mi->r[i]; + /* Assign the new rate set */ + memcpy(mi->max_tp_rate, tmp_tp_rate, sizeof(mi->max_tp_rate)); + mi->max_prob_rate = tmp_prob_rate; - if (i == index_max_tp) - continue; + /* Reset update timer */ + mi->stats_update = jiffies; - if (max_tp < mr->cur_tp) { - index_max_tp2 = i; - max_tp = mr->cur_tp; - } - } - mi->max_tp_rate = index_max_tp; - mi->max_tp_rate2 = index_max_tp2; - mi->max_prob_rate = index_max_prob; + minstrel_update_rates(mp, mi); } static void @@ -195,9 +255,9 @@ minstrel_get_retry_count(struct minstrel_rate *mr, { unsigned int retry = mr->adjusted_retry_count; - if (info->control.rates[0].flags & IEEE80211_TX_RC_USE_RTS_CTS) + if (info->control.use_rts) retry = max(2U, min(mr->retry_count_rtscts, retry)); - else if (info->control.rates[0].flags & IEEE80211_TX_RC_USE_CTS_PROTECT) + else if (info->control.use_cts_prot) retry = max(2U, min(mr->retry_count_cts, retry)); return retry; } @@ -207,10 +267,10 @@ static int minstrel_get_next_sample(struct minstrel_sta_info *mi) { unsigned int sample_ndx; - sample_ndx = SAMPLE_TBL(mi, mi->sample_idx, mi->sample_column); - mi->sample_idx++; - if ((int) mi->sample_idx > (mi->n_rates - 2)) { - mi->sample_idx = 0; + sample_ndx = SAMPLE_TBL(mi, mi->sample_row, mi->sample_column); + mi->sample_row++; + if ((int) mi->sample_row >= mi->n_rates) { + mi->sample_row = 0; mi->sample_column++; if (mi->sample_column >= SAMPLE_COLUMNS) mi->sample_column = 0; @@ -226,111 +286,96 @@ minstrel_get_rate(void *priv, struct ieee80211_sta *sta, struct ieee80211_tx_info *info = IEEE80211_SKB_CB(skb); struct minstrel_sta_info *mi = priv_sta; struct minstrel_priv *mp = priv; - struct ieee80211_tx_rate *ar = info->control.rates; - unsigned int ndx, sample_ndx = 0; - bool mrr; - bool sample_slower = false; - bool sample = false; - int i, delta; - int mrr_ndx[3]; - int sample_rate; - + struct ieee80211_tx_rate *rate = &info->control.rates[0]; + struct minstrel_rate *msr, *mr; + unsigned int ndx; + bool mrr_capable; + bool prev_sample = mi->prev_sample; + int delta; + int sampling_ratio; + + /* management/no-ack frames do not use rate control */ if (rate_control_send_low(sta, priv_sta, txrc)) return; - mrr = mp->has_mrr && !txrc->rts && !txrc->bss_conf->use_cts_prot; - - ndx = mi->max_tp_rate; - - if (mrr) - sample_rate = mp->lookaround_rate_mrr; + /* check multi-rate-retry capabilities & adjust lookaround_rate */ + mrr_capable = mp->has_mrr && + !txrc->rts && + !txrc->bss_conf->use_cts_prot; + if (mrr_capable) + sampling_ratio = mp->lookaround_rate_mrr; else - sample_rate = mp->lookaround_rate; + sampling_ratio = mp->lookaround_rate; + /* increase sum packet counter */ mi->packet_count++; - delta = (mi->packet_count * sample_rate / 100) - + + delta = (mi->packet_count * sampling_ratio / 100) - (mi->sample_count + mi->sample_deferred / 2); - /* delta > 0: sampling required */ - if ((delta > 0) && (mrr || !mi->prev_sample)) { - struct minstrel_rate *msr; - if (mi->packet_count >= 10000) { - mi->sample_deferred = 0; - mi->sample_count = 0; - mi->packet_count = 0; - } else if (delta > mi->n_rates * 2) { - /* With multi-rate retry, not every planned sample - * attempt actually gets used, due to the way the retry - * chain is set up - [max_tp,sample,prob,lowest] for - * sample_rate < max_tp. - * - * If there's too much sampling backlog and the link - * starts getting worse, minstrel would start bursting - * out lots of sampling frames, which would result - * in a large throughput loss. */ - mi->sample_count += (delta - mi->n_rates * 2); - } + /* delta < 0: no sampling required */ + mi->prev_sample = false; + if (delta < 0 || (!mrr_capable && prev_sample)) + return; - sample_ndx = minstrel_get_next_sample(mi); - msr = &mi->r[sample_ndx]; - sample = true; - sample_slower = mrr && (msr->perfect_tx_time > - mi->r[ndx].perfect_tx_time); - - if (!sample_slower) { - if (msr->sample_limit != 0) { - ndx = sample_ndx; - mi->sample_count++; - if (msr->sample_limit > 0) - msr->sample_limit--; - } else { - sample = false; - } - } else { - /* Only use IEEE80211_TX_CTL_RATE_CTRL_PROBE to mark - * packets that have the sampling rate deferred to the - * second MRR stage. Increase the sample counter only - * if the deferred sample rate was actually used. - * Use the sample_deferred counter to make sure that - * the sampling is not done in large bursts */ - info->flags |= IEEE80211_TX_CTL_RATE_CTRL_PROBE; - mi->sample_deferred++; - } + if (mi->packet_count >= 10000) { + mi->sample_deferred = 0; + mi->sample_count = 0; + mi->packet_count = 0; + } else if (delta > mi->n_rates * 2) { + /* With multi-rate retry, not every planned sample + * attempt actually gets used, due to the way the retry + * chain is set up - [max_tp,sample,prob,lowest] for + * sample_rate < max_tp. + * + * If there's too much sampling backlog and the link + * starts getting worse, minstrel would start bursting + * out lots of sampling frames, which would result + * in a large throughput loss. */ + mi->sample_count += (delta - mi->n_rates * 2); + } + + /* get next random rate sample */ + ndx = minstrel_get_next_sample(mi); + msr = &mi->r[ndx]; + mr = &mi->r[mi->max_tp_rate[0]]; + + /* Decide if direct ( 1st mrr stage) or indirect (2nd mrr stage) + * rate sampling method should be used. + * Respect such rates that are not sampled for 20 interations. + */ + if (mrr_capable && + msr->perfect_tx_time > mr->perfect_tx_time && + msr->sample_skipped < 20) { + /* Only use IEEE80211_TX_CTL_RATE_CTRL_PROBE to mark + * packets that have the sampling rate deferred to the + * second MRR stage. Increase the sample counter only + * if the deferred sample rate was actually used. + * Use the sample_deferred counter to make sure that + * the sampling is not done in large bursts */ + info->flags |= IEEE80211_TX_CTL_RATE_CTRL_PROBE; + rate++; + mi->sample_deferred++; + } else { + if (!msr->sample_limit != 0) + return; + + mi->sample_count++; + if (msr->sample_limit > 0) + msr->sample_limit--; } - mi->prev_sample = sample; /* If we're not using MRR and the sampling rate already * has a probability of >95%, we shouldn't be attempting * to use it, as this only wastes precious airtime */ - if (!mrr && sample && (mi->r[ndx].probability > 17100)) - ndx = mi->max_tp_rate; - - ar[0].idx = mi->r[ndx].rix; - ar[0].count = minstrel_get_retry_count(&mi->r[ndx], info); - - if (!mrr) { - if (!sample) - ar[0].count = mp->max_retry; - ar[1].idx = mi->lowest_rix; - ar[1].count = mp->max_retry; + if (!mrr_capable && + (mi->r[ndx].probability > MINSTREL_FRAC(95, 100))) return; - } - /* MRR setup */ - if (sample) { - if (sample_slower) - mrr_ndx[0] = sample_ndx; - else - mrr_ndx[0] = mi->max_tp_rate; - } else { - mrr_ndx[0] = mi->max_tp_rate2; - } - mrr_ndx[1] = mi->max_prob_rate; - mrr_ndx[2] = 0; - for (i = 1; i < 4; i++) { - ar[i].idx = mi->r[mrr_ndx[i - 1]].rix; - ar[i].count = mi->r[mrr_ndx[i - 1]].adjusted_retry_count; - } + mi->prev_sample = true; + + rate->idx = mi->r[ndx].rix; + rate->count = minstrel_get_retry_count(&mi->r[ndx], info); } @@ -351,26 +396,21 @@ static void init_sample_table(struct minstrel_sta_info *mi) { unsigned int i, col, new_idx; - unsigned int n_srates = mi->n_rates - 1; u8 rnd[8]; mi->sample_column = 0; - mi->sample_idx = 0; - memset(mi->sample_table, 0, SAMPLE_COLUMNS * mi->n_rates); + mi->sample_row = 0; + memset(mi->sample_table, 0xff, SAMPLE_COLUMNS * mi->n_rates); for (col = 0; col < SAMPLE_COLUMNS; col++) { - for (i = 0; i < n_srates; i++) { + for (i = 0; i < mi->n_rates; i++) { get_random_bytes(rnd, sizeof(rnd)); - new_idx = (i + rnd[i & 7]) % n_srates; + new_idx = (i + rnd[i & 7]) % mi->n_rates; - while (SAMPLE_TBL(mi, new_idx, col) != 0) - new_idx = (new_idx + 1) % n_srates; + while (SAMPLE_TBL(mi, new_idx, col) != 0xff) + new_idx = (new_idx + 1) % mi->n_rates; - /* Don't sample the slowest rate (i.e. slowest base - * rate). We must presume that the slowest rate works - * fine, or else other management frames will also be - * failing and the link will break */ - SAMPLE_TBL(mi, new_idx, col) = i + 1; + SAMPLE_TBL(mi, new_idx, col) = i; } } } @@ -385,12 +425,16 @@ minstrel_rate_init(void *priv, struct ieee80211_supported_band *sband, unsigned int i, n = 0; unsigned int t_slot = 9; /* FIXME: get real slot time */ + mi->sta = sta; mi->lowest_rix = rate_lowest_index(sband, sta); ctl_rate = &sband->bitrates[mi->lowest_rix]; mi->sp_ack_dur = ieee80211_frame_duration(sband->band, 10, ctl_rate->bitrate, !!(ctl_rate->flags & IEEE80211_RATE_ERP_G), 1); + memset(mi->max_tp_rate, 0, sizeof(mi->max_tp_rate)); + mi->max_prob_rate = 0; + for (i = 0; i < sband->n_bitrates; i++) { struct minstrel_rate *mr = &mi->r[n]; unsigned int tx_time = 0, tx_time_cts = 0, tx_time_rtscts = 0; @@ -433,6 +477,8 @@ minstrel_rate_init(void *priv, struct ieee80211_supported_band *sband, } while ((tx_time < mp->segment_size) && (++mr->retry_count < mp->max_retry)); mr->adjusted_retry_count = mr->retry_count; + if (!(sband->bitrates[i].flags & IEEE80211_RATE_ERP_G)) + mr->retry_count_cts = mr->retry_count; } for (i = n; i < sband->n_bitrates; i++) { @@ -444,6 +490,7 @@ minstrel_rate_init(void *priv, struct ieee80211_supported_band *sband, mi->stats_update = jiffies; init_sample_table(mi); + minstrel_update_rates(mp, mi); } static void * @@ -542,9 +589,6 @@ minstrel_alloc(struct ieee80211_hw *hw, struct dentry *debugfsdir) mp->lookaround_rate = 5; mp->lookaround_rate_mrr = 10; - /* moving average weight for EWMA */ - mp->ewma_level = 75; - /* maximum time that the hw is allowed to stay in one MRR segment */ mp->segment_size = 6000; |