1 files changed, 191 insertions, 147 deletions

diff --git a/net/mac80211/rc80211_minstrel.c b/net/mac80211/rc80211_minstrel.c
index eea45a2c7c3..ac7ef5414bd 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 (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);
+	}
 
-		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++;
-		}
+	/* 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;