From owner-p4-projects@FreeBSD.ORG Thu Mar 10 23:31:57 2005 Return-Path: Delivered-To: p4-projects@freebsd.org Received: by hub.freebsd.org (Postfix, from userid 32767) id 2ABC816A4D0; Thu, 10 Mar 2005 23:31:57 +0000 (GMT) Delivered-To: perforce@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id F124216A4CE for ; Thu, 10 Mar 2005 23:31:56 +0000 (GMT) Received: from repoman.freebsd.org (repoman.freebsd.org [216.136.204.115]) by mx1.FreeBSD.org (Postfix) with ESMTP id 6547743D1D for ; Thu, 10 Mar 2005 23:31:56 +0000 (GMT) (envelope-from sam@freebsd.org) Received: from repoman.freebsd.org (localhost [127.0.0.1]) by repoman.freebsd.org (8.13.1/8.13.1) with ESMTP id j2ANVuWJ042167 for ; Thu, 10 Mar 2005 23:31:56 GMT (envelope-from sam@freebsd.org) Received: (from perforce@localhost) by repoman.freebsd.org (8.13.1/8.13.1/Submit) id j2ANVu1Q042164 for perforce@freebsd.org; Thu, 10 Mar 2005 23:31:56 GMT (envelope-from sam@freebsd.org) Date: Thu, 10 Mar 2005 23:31:56 GMT Message-Id: <200503102331.j2ANVu1Q042164@repoman.freebsd.org> X-Authentication-Warning: repoman.freebsd.org: perforce set sender to sam@freebsd.org using -f From: Sam Leffler To: Perforce Change Reviews Subject: PERFORCE change 72868 for review X-BeenThere: p4-projects@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: p4 projects tree changes List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 10 Mar 2005 23:31:57 -0000 http://perforce.freebsd.org/chv.cgi?CH=72868 Change 72868 by sam@sam_ebb on 2005/03/10 23:31:44 updated version; seems to work in sta+ap, untested in adhoc Obtained from: madwifi Affected files ... .. //depot/projects/wifi/sys/dev/ath/ath_rate/sample/sample.c#2 edit .. //depot/projects/wifi/sys/dev/ath/ath_rate/sample/sample.h#2 edit Differences ... ==== //depot/projects/wifi/sys/dev/ath/ath_rate/sample/sample.c#2 (text+ko) ==== @@ -113,6 +113,20 @@ static void ath_rate_ctl_start(struct ath_softc *, struct ieee80211_node *); +static __inline int size_to_bin(int size) +{ + int x = 0; + for (x = 0; x < NUM_PACKET_SIZE_BINS; x++) { + if (size < packet_size_bins[x]) { + return x; + } + } + return NUM_PACKET_SIZE_BINS-1; +} +static __inline int bin_to_size(int index) { + return packet_size_bins[index]; +} + /* * Setup rate codes for management/control frames. We force * all such frames to the lowest rate. @@ -148,13 +162,13 @@ * returns the ndx with the lowest average_tx_time, * or -1 if all the average_tx_times are 0. */ -static __inline int best_rate_ndx(struct sample_node *sn) +static __inline int best_rate_ndx(struct sample_node *sn, int size_bin) { int x = 0; int best_rate_ndx = 0; int best_rate_tt = 0; for (x = 0; x < sn->num_rates; x++) { - int tt = sn->rates[x].average_tx_time; + int tt = sn->stats[size_bin][x].average_tx_time; if (tt > 0) { if (!best_rate_tt || best_rate_tt > tt) { best_rate_tt = tt; @@ -162,7 +176,6 @@ } } } - return (best_rate_tt) ? best_rate_ndx : -1; } @@ -171,10 +184,10 @@ * is less than the best bit-rate's average_tx_time * and the ndx has not had four successive failures. */ -static __inline int pick_sample_ndx(struct sample_node *sn) +static __inline int pick_sample_ndx(struct sample_node *sn, int size_bin) { int x = 0; - int best_ndx = best_rate_ndx(sn); + int best_ndx = best_rate_ndx(sn, size_bin); int best_tt = 0; int num_eligible = 0; @@ -183,8 +196,8 @@ return 0; } - best_tt = sn->rates[best_ndx].average_tx_time; - sn->sample_num++; + best_tt = sn->stats[size_bin][best_ndx].average_tx_time; + sn->sample_num[size_bin]++; /* * first, find the number of bit-rates we could potentially @@ -193,18 +206,18 @@ */ for (x = 0; x < sn->num_rates; x++) { if (x != best_ndx && - sn->rates[x].perfect_tx_time < best_tt && - sn->rates[x].successive_failures < 4) { + sn->stats[size_bin][x].perfect_tx_time < best_tt && + sn->stats[size_bin][x].successive_failures < 4) { num_eligible++; } } if (num_eligible > 0) { - int pick = sn->sample_num % num_eligible; + int pick = sn->sample_num[size_bin] % num_eligible; for (x = 0; x < sn->num_rates; x++) { if (x != best_ndx && - sn->rates[x].perfect_tx_time < best_tt && - sn->rates[x].successive_failures < 4) { + sn->stats[size_bin][x].perfect_tx_time < best_tt && + sn->stats[size_bin][x].successive_failures < 4) { if (pick == 0) { return x; } @@ -215,26 +228,30 @@ return best_ndx; } - void ath_rate_findrate(struct ath_softc *sc, struct ath_node *an, HAL_BOOL shortPreamble, size_t frameLen, u_int8_t *rix, int *try0, u_int8_t *txrate) { - struct sample_softc *osc = ATH_SOFTC_SAMPLE(sc); struct sample_node *sn = ATH_NODE_SAMPLE(an); - int ndx, best_ndx; - + struct sample_softc *ssc = ATH_SOFTC_SAMPLE(sc); + int x; + int ndx = 0; + int size_bin = size_to_bin(frameLen); + int best_ndx = best_rate_ndx(sn, size_bin); + if (sn->static_rate_ndx != -1) { *try0 = 4; *rix = sn->rates[sn->static_rate_ndx].rix; *txrate = sn->rates[sn->static_rate_ndx].rateCode; return; } - ndx = 0; - *try0 = 4; - best_ndx = best_rate_ndx(sn); - if (!sn->packets_sent || sn->packets_sent % osc->ath_sample_rate > 0) { + + *try0 = 2; + + best_ndx = best_rate_ndx(sn, size_bin); + if (!sn->packets_sent[size_bin] || + sn->packets_sent[size_bin] % ssc->ath_sample_rate > 0) { /* * for most packets, send the packet at the bit-rate with * the lowest estimated transmission time. @@ -246,19 +263,33 @@ * no packet has succeeded, try the highest bitrate * that hasn't failed. */ - *try0 = 2; for (ndx = sn->num_rates-1; ndx >= 0; ndx--) { - if (sn->rates[ndx].successive_failures == 0) { + if (sn->stats[size_bin][ndx].successive_failures == 0) { break; } } } + if (size_bin == 0) { + /* update the visible txrate for this node */ + an->an_node.ni_txrate = ndx; + } } else { + /* + * before we pick a bit-rate to "sample", clear any + * stale stuff out. + */ + for (x = 0; x < sn->num_rates; x++) { + if (ticks - sn->stats[size_bin][x].last_tx > ((hz * 10000)/1000)) { + sn->stats[size_bin][x].average_tx_time = sn->stats[size_bin][x].perfect_tx_time; + sn->stats[size_bin][x].successive_failures = 0; + sn->stats[size_bin][x].tries = 0; + sn->stats[size_bin][x].total_packets = 0; + sn->stats[size_bin][x].packets_acked = 0; + } + } + /* send the packet at a different bit-rate */ - ndx = pick_sample_ndx(sn); - if (best_ndx != ndx) { - *try0 = 2; - } + ndx = pick_sample_ndx(sn, size_bin); } @@ -270,13 +301,7 @@ *txrate = sn->rates[ndx].rateCode; } - - sn->packets_sent++; - DPRINTF(sc, "packets %d rate %d ndx %d rateCode %d try0 %d average %d\n", - sn->packets_sent, - sn->rates[ndx].rate, ndx, sn->rates[ndx].rateCode, - *try0, sn->rates[*rix].average_tx_time); - + sn->packets_sent[size_bin]++; } void @@ -284,25 +309,44 @@ struct ath_desc *ds, HAL_BOOL shortPreamble, u_int8_t rix) { struct sample_node *sn = ATH_NODE_SAMPLE(an); - int best_ndx = best_rate_ndx(sn); - int rateCode = 0; - if (best_ndx == -1) { + int rateCode = -1; + int frame_size; + int size_bin; + int best_ndx; + + frame_size = ds->ds_ctl0 & 0x0fff; /* low-order 12 bits of ds_ctl0 */ + if (frame_size == 0) + frame_size = 1500; + size_bin = size_to_bin(frame_size); + best_ndx = best_rate_ndx(sn, size_bin); + + if (best_ndx == -1 || !sn->stats[size_bin][best_ndx].packets_acked) { /* * no packet has succeeded, so also try twice at the lowest bitate. */ - rateCode = sn->rates[0].shortPreambleRateCode; + if (shortPreamble) { + rateCode = sn->rates[0].shortPreambleRateCode; + } else { + rateCode = sn->rates[0].rateCode; + } } else if (sn->rates[best_ndx].rix != rix) { /* * we're trying a different bit-rate, and it could be lossy, * so if it fails try at the best bit-rate. */ - rateCode = sn->rates[best_ndx].shortPreambleRateCode; + if (shortPreamble) { + rateCode = sn->rates[MAX(0,best_ndx-1)].shortPreambleRateCode; + } else { + rateCode = sn->rates[MAX(0,best_ndx-1)].rateCode; + } + } + if (rateCode != -1) { + ath_hal_setupxtxdesc(sc->sc_ah, ds + , rateCode, 1 /* series 1 */ + , rateCode, 1 /* series 2 */ + , rateCode, 1 /* series 3 */ + ); } - ath_hal_setupxtxdesc(sc->sc_ah, ds - , rateCode, 2 /* series 1 */ - , 0, 0 /* series 2 */ - , 0, 0 /* series 3 */ - ); } @@ -310,18 +354,24 @@ ath_rate_tx_complete(struct ath_softc *sc, struct ath_node *an, const struct ath_desc *ds) { - struct sample_softc *osc = ATH_SOFTC_SAMPLE(sc); struct sample_node *sn = ATH_NODE_SAMPLE(an); + struct sample_softc *ssc = ATH_SOFTC_SAMPLE(sc); int rate = sc->sc_hwmap[ds->ds_txstat.ts_rate &~ HAL_TXSTAT_ALTRATE].ieeerate; - int used_alt_rate = ds->ds_txstat.ts_rate & HAL_TXSTAT_ALTRATE; int retries = ds->ds_txstat.ts_longretry; - int pktlen, tt, rix, x; - + int initial_rate_failed = ((ds->ds_txstat.ts_rate & HAL_TXSTAT_ALTRATE) + || ds->ds_txstat.ts_status != 0 || + retries > 3); + int tt = 0; + int rix = -1; + int x = 0; + int frame_size; /* low-order 12 bits of ds_ctl0 */ + int size_bin; + int size; + if (!sn->num_rates) { DPRINTF(sc, "%s: no rates yet\n", __func__); return; } - rix = -1; for (x = 0; x < sn->num_rates; x++) { if (sn->rates[x].rate == rate) { rix = x; @@ -334,30 +384,51 @@ return; } - pktlen = ds->ds_ctl0 & 0xfff; - if (pktlen == 0) /* XXX multi-descriptor tx */ - pktlen = 1500; - tt = calc_usecs_wifi_packet(pktlen, rate, MIN(retries, 4)); + frame_size = ds->ds_ctl0 & 0x0fff; /* low-order 12 bits of ds_ctl0 */ + if (frame_size == 0) + frame_size = 1500; + size_bin = size_to_bin(frame_size); + size = bin_to_size(size_bin); + tt = calc_usecs_unicast_packet(sc, size, sn->rates[rix].rix, + retries); + + DPRINTF(sc, "%s: rate %d rix %d frame_size %d (%d) retries %d status %d tt %d avg_tt %d perfect_tt %d ts-rate %d\n", + __func__, rate, rix, frame_size, size, retries, initial_rate_failed, tt, + sn->stats[size_bin][rix].average_tx_time, + sn->stats[size_bin][rix].perfect_tx_time, + ds->ds_txstat.ts_rate); - DPRINTF(sc, "%s: rate %d rix %d retries %d tt %d pktlen %d success %d ts_rate %d\n", - __func__, rate, rix, retries, tt, pktlen, used_alt_rate, ds->ds_txstat.ts_rate); - - if (!sn->rates[rix].average_tx_time) { - sn->rates[rix].average_tx_time = tt; + if (sn->stats[size_bin][rix].total_packets < 7) { + /* just average the first few packets */ + int avg_tx = sn->stats[size_bin][rix].average_tx_time; + int packets = sn->stats[size_bin][rix].total_packets; + sn->stats[size_bin][rix].average_tx_time = (tt+(avg_tx*packets))/(packets+1); } else { - sn->rates[rix].average_tx_time = - ((sn->rates[rix].average_tx_time * osc->ath_smoothing_rate) + - (tt * (100 - osc->ath_smoothing_rate))) / 100; + /* use a ewma */ + sn->stats[size_bin][rix].average_tx_time = + ((sn->stats[size_bin][rix].average_tx_time * ssc->ath_smoothing_rate) + + (tt * (100 - ssc->ath_smoothing_rate))) / 100; } - if (!used_alt_rate) { - sn->rates[rix].packets_acked++; - sn->rates[rix].successive_failures = 0; + if (initial_rate_failed) { + /* + * this packet failed - count this as a failure + * for larger packets also, since we assume + * if a small packet fails at a lower bit-rate + * then a larger one will also. + */ + int y; + for (y = size_bin; y < NUM_PACKET_SIZE_BINS; y++) { + sn->stats[y][rix].successive_failures++; + sn->stats[y][rix].last_tx = ticks; + } } else { - sn->rates[rix].successive_failures++; + sn->stats[size_bin][rix].packets_acked++; + sn->stats[size_bin][rix].successive_failures = 0; } - sn->rates[rix].tries += (1+retries); - + sn->stats[size_bin][rix].tries += (1+retries); + sn->stats[size_bin][rix].last_tx = ticks; + sn->stats[size_bin][rix].total_packets++; } void @@ -368,6 +439,44 @@ ath_rate_ctl_start(sc, &an->an_node); } +static void +ath_rate_ctl_reset(struct ath_softc *sc, struct ieee80211_node *ni) +{ + struct ath_node *an = ATH_NODE(ni); + struct sample_node *sn = ATH_NODE_SAMPLE(an); + int x = 0; + int y = 0; + + for (y = 0; y < NUM_PACKET_SIZE_BINS; y++) { + int size = bin_to_size(y); + sn->packets_sent[y] = 0; + sn->sample_num[y] = 0; + + for (x = 0; x < ni->ni_rates.rs_nrates; x++) { + sn->stats[y][x].successive_failures = 0; + sn->stats[y][x].tries = 0; + sn->stats[y][x].total_packets = 0; + sn->stats[y][x].packets_acked = 0; + sn->stats[y][x].last_tx = 0; + sn->stats[y][x].perfect_tx_time = calc_usecs_unicast_packet(sc, size, + sn->rates[x].rix, + 0); + sn->stats[y][x].average_tx_time = sn->stats[y][x].perfect_tx_time; + + + DPRINTF(sc, "%s: %d rate %d rix %d rateCode %d perfect_tx_time %d \n", __func__, + x, sn->rates[x].rate, + sn->rates[x].rix, sn->rates[x].rateCode, + sn->stats[0][x].perfect_tx_time); + } + + } + + /* set the visible bit-rate to the lowest one available */ + ni->ni_txrate = 0; + +} + /* * Initialize the tables for a node. */ @@ -379,9 +488,10 @@ struct ath_node *an = ATH_NODE(ni); struct sample_node *sn = ATH_NODE_SAMPLE(an); const HAL_RATE_TABLE *rt = sc->sc_currates; + + int x; int srate; - int x = 0; - + DPRINTF(sc, "%s:\n", __func__); KASSERT(rt != NULL, ("no rate table, mode %u", sc->sc_curmode)); KASSERT(ni->ni_rates.rs_nrates > 0, ("no rates")); @@ -407,7 +517,6 @@ } sn->num_rates = ni->ni_rates.rs_nrates; - for (x = 0; x < ni->ni_rates.rs_nrates; x++) { sn->rates[x].rate = ni->ni_rates.rs_rates[x] & IEEE80211_RATE_VAL; sn->rates[x].rix = sc->sc_rixmap[sn->rates[x].rate]; @@ -415,16 +524,9 @@ sn->rates[x].shortPreambleRateCode = rt->info[sn->rates[x].rix].rateCode | rt->info[sn->rates[x].rix].shortPreamble; - sn->rates[x].perfect_tx_time = calc_usecs_wifi_packet(1500, - sn->rates[x].rate, - 0); - - DPRINTF(sc, "%s: %d rate %d rix %d rateCode %d perfect_tx_time %d \n", __func__, - x, sn->rates[x].rate, - sn->rates[x].rix, sn->rates[x].rateCode, - sn->rates[x].perfect_tx_time); + } + ath_rate_ctl_reset(sc, ni); - } #undef RATE } @@ -435,18 +537,9 @@ ath_rate_newstate(struct ath_softc *sc, enum ieee80211_state state) { struct ieee80211com *ic = &sc->sc_ic; - struct ieee80211_node *ni; - if (ic->ic_opmode == IEEE80211_M_STA) { - /* - * Reset local xmit state; this is really only - * meaningful when operating in station mode. - */ - ni = ic->ic_bss; - if (state == IEEE80211_S_RUN) { - ath_rate_ctl_start(sc, ni); - } - } + if (state == IEEE80211_S_RUN) + ath_rate_newassoc(sc, ATH_NODE(ic->ic_bss), 1); } static void @@ -475,7 +568,7 @@ if (osc == NULL) return NULL; osc->arc.arc_space = sizeof(struct sample_node); - osc->ath_smoothing_rate = 90; /* ewma percentage (out of 100) */ + osc->ath_smoothing_rate = 95; /* ewma percentage (out of 100) */ osc->ath_sample_rate = 10; /* send a different bit-rate 1/X packets */ ath_rate_sysctlattach(sc, osc); return &osc->arc; ==== //depot/projects/wifi/sys/dev/ath/ath_rate/sample/sample.h#2 (text+ko) ==== @@ -50,49 +50,43 @@ #define ATH_SOFTC_SAMPLE(sc) ((struct sample_softc *)sc->sc_rc) struct rate_info { - int rate; - int rix; - int rateCode; - int shortPreambleRateCode; + int rate; + int rix; + int rateCode; + int shortPreambleRateCode; +}; + - int average_tx_time; - int successive_failures; - int tries; - int packets_acked; - int perfect_tx_time; /* transmit time for 0 retries */ +struct rate_stats { + int average_tx_time; + int successive_failures; + int tries; + int total_packets; + int packets_acked; + int perfect_tx_time; /* transmit time for 0 retries */ + int last_tx; }; +/* + * for now, we track performance for three different packet + * size buckets + */ +#define NUM_PACKET_SIZE_BINS 3 +static int packet_size_bins[NUM_PACKET_SIZE_BINS] = {250, 1600, 3000}; /* per-node state */ struct sample_node { - int packets_sent; + int static_rate_ndx; + int num_rates; - int static_rate_ndx; - int num_rates; + struct rate_info rates[IEEE80211_RATE_MAXSIZE]; + + struct rate_stats stats[NUM_PACKET_SIZE_BINS][IEEE80211_RATE_MAXSIZE]; + int sample_num[NUM_PACKET_SIZE_BINS]; + int packets_sent[NUM_PACKET_SIZE_BINS]; - struct rate_info rates[IEEE80211_RATE_MAXSIZE]; - int sample_num; }; - - -#define WIFI_SLOT_B 20 -#define WIFI_DIFS_B 50 -#define WIFI_SIFS_B 10 -#define WIFI_ACK_B 304 -#define WIFI_PLCP_HEADER_LONG_B 192 -#define WIFI_PLCP_HEADER_SHORT_B 192 - -#define WIFI_SLOT_A 9 -#define WIFI_DIFS_A 28 -#define WIFI_SIFS_A 9 -#define WIFI_ACK_A 30 -#define WIFI_PLCP_HEADER_A 20 - - -#define is_b_rate(b) ((b == 2) || (b == 4) || (b == 11) || (b == 22)) - -#define WIFI_CW_MIN 31 -#define WIFI_CW_MAX 1023 +#define ATH_NODE_SAMPLE(an) ((struct sample_node *)&an[1]) #ifndef MIN #define MIN(a,b) ((a) < (b) ? (a) : (b)) @@ -101,74 +95,41 @@ #define MAX(a,b) ((a) > (b) ? (a) : (b)) #endif -/* - * transmit time for data payload + plcp_header - */ -static unsigned calc_transmit_time(int rate, int length) { - unsigned t_plcp_header = 96; - if (rate == 1) { - t_plcp_header = 192; - } else if (!is_b_rate(rate)) { - t_plcp_header = 20; - } - return (2 * (t_plcp_header + ((length * 8))))/ rate; -} +#define WIFI_CW_MIN 31 +#define WIFI_CW_MAX 1023 /* - * expected backoff for t tries. + * Calculate the transmit duration of a frame. */ -static unsigned calc_backoff(int rate, int t) -{ - int t_slot = is_b_rate(rate) ? WIFI_SLOT_B : WIFI_SLOT_A; - int cw = WIFI_CW_MIN; - int x = 0; +static unsigned calc_usecs_unicast_packet(struct ath_softc *sc, + int length, + int rix, int retries) { + const HAL_RATE_TABLE *rt = sc->sc_currates; - /* there is backoff, even for the first packet */ - for (x = 0; x < t; x++) { - cw = MIN(WIFI_CW_MAX, (cw + 1) * 2); - } - return t_slot * cw / 2; + + /* pg 205 ieee.802.11.pdf */ + unsigned t_slot = 20; + unsigned t_difs = 50; + unsigned t_sifs = 10; + int tt = 0; + int x = 0; + int cw = WIFI_CW_MIN; + int cix = rt->info[rix].controlRate; + KASSERT(rt != NULL, ("no rate table, mode %u", sc->sc_curmode)); + + if (rt->info[rix].phy == IEEE80211_T_OFDM) { + t_slot = 9; + t_sifs = 9; + t_difs = 28; + } + tt += t_difs; + tt += (retries+1)*(t_sifs + rt->info[cix].spAckDuration); + tt += (retries+1)*ath_hal_computetxtime(sc->sc_ah, rt, length, + rix, AH_TRUE); + for (x = 0; x <= retries; x++) { + cw = MIN(WIFI_CW_MAX, (cw + 1) * 2); + tt += (t_slot * cw/2); + } + return tt; } - - - -static unsigned calc_usecs_wifi_packet_tries(int length, - int rate, - int try0, int tryN) { - if (!rate || !length || try0 > tryN) { - return 99999; - } - - /* pg 205 ieee.802.11.pdf */ - unsigned t_slot = 20; - unsigned t_ack = 304; // 192 + 14*8/1 - unsigned t_difs = 50; - unsigned t_sifs = 10; - - - if (!is_b_rate(rate)) { - /* with 802.11g, things are at 6 mbit/s */ - t_slot = 9; - t_sifs = 9; - t_difs = 28; - t_ack = 30; - } - - int tt = 0; - int x = 0; - for (x = try0; x <= tryN; x++) { - tt += calc_backoff(rate, x) + - calc_transmit_time(rate, length) + - t_sifs + t_ack; - } - return tt; -} - -static unsigned calc_usecs_wifi_packet(int length, - int rate, int retries) { - return calc_usecs_wifi_packet_tries(length, rate, - 0, retries); -} - -#define ATH_NODE_SAMPLE(an) ((struct sample_node *)&an[1]) #endif /* _DEV_ATH_RATE_SAMPLE_H */