1/* 2 * Copyright 2002-2005, Instant802 Networks, Inc. 3 * Copyright 2005, Devicescape Software, Inc. 4 * Copyright 2007, Mattias Nissler <mattias.nissler@gmx.de> 5 * Copyright 2007-2008, Stefano Brivio <stefano.brivio@polimi.it> 6 * 7 * This program is free software; you can redistribute it and/or modify 8 * it under the terms of the GNU General Public License version 2 as 9 * published by the Free Software Foundation. 10 */ 11 12#include <linux/netdevice.h> 13#include <linux/types.h> 14#include <linux/skbuff.h> 15#include <linux/debugfs.h> 16#include <linux/slab.h> 17#include <net/mac80211.h> 18#include "rate.h" 19#include "mesh.h" 20#include "rc80211_pid.h" 21 22 23/* This is an implementation of a TX rate control algorithm that uses a PID 24 * controller. Given a target failed frames rate, the controller decides about 25 * TX rate changes to meet the target failed frames rate. 26 * 27 * The controller basically computes the following: 28 * 29 * adj = CP * err + CI * err_avg + CD * (err - last_err) * (1 + sharpening) 30 * 31 * where 32 * adj adjustment value that is used to switch TX rate (see below) 33 * err current error: target vs. current failed frames percentage 34 * last_err last error 35 * err_avg average (i.e. poor man's integral) of recent errors 36 * sharpening non-zero when fast response is needed (i.e. right after 37 * association or no frames sent for a long time), heading 38 * to zero over time 39 * CP Proportional coefficient 40 * CI Integral coefficient 41 * CD Derivative coefficient 42 * 43 * CP, CI, CD are subject to careful tuning. 44 * 45 * The integral component uses a exponential moving average approach instead of 46 * an actual sliding window. The advantage is that we don't need to keep an 47 * array of the last N error values and computation is easier. 48 * 49 * Once we have the adj value, we map it to a rate by means of a learning 50 * algorithm. This algorithm keeps the state of the percentual failed frames 51 * difference between rates. The behaviour of the lowest available rate is kept 52 * as a reference value, and every time we switch between two rates, we compute 53 * the difference between the failed frames each rate exhibited. By doing so, 54 * we compare behaviours which different rates exhibited in adjacent timeslices, 55 * thus the comparison is minimally affected by external conditions. This 56 * difference gets propagated to the whole set of measurements, so that the 57 * reference is always the same. Periodically, we normalize this set so that 58 * recent events weigh the most. By comparing the adj value with this set, we 59 * avoid pejorative switches to lower rates and allow for switches to higher 60 * rates if they behaved well. 61 * 62 * Note that for the computations we use a fixed-point representation to avoid 63 * floating point arithmetic. Hence, all values are shifted left by 64 * RC_PID_ARITH_SHIFT. 65 */ 66 67 68/* Adjust the rate while ensuring that we won't switch to a lower rate if it 69 * exhibited a worse failed frames behaviour and we'll choose the highest rate 70 * whose failed frames behaviour is not worse than the one of the original rate 71 * target. While at it, check that the new rate is valid. */ 72static void rate_control_pid_adjust_rate(struct ieee80211_supported_band *sband, 73 struct ieee80211_sta *sta, 74 struct rc_pid_sta_info *spinfo, int adj, 75 struct rc_pid_rateinfo *rinfo) 76{ 77 int cur_sorted, new_sorted, probe, tmp, n_bitrates, band; 78 int cur = spinfo->txrate_idx; 79 80 band = sband->band; 81 n_bitrates = sband->n_bitrates; 82 83 /* Map passed arguments to sorted values. */ 84 cur_sorted = rinfo[cur].rev_index; 85 new_sorted = cur_sorted + adj; 86 87 /* Check limits. */ 88 if (new_sorted < 0) 89 new_sorted = rinfo[0].rev_index; 90 else if (new_sorted >= n_bitrates) 91 new_sorted = rinfo[n_bitrates - 1].rev_index; 92 93 tmp = new_sorted; 94 95 if (adj < 0) { 96 /* Ensure that the rate decrease isn't disadvantageous. */ 97 for (probe = cur_sorted; probe >= new_sorted; probe--) 98 if (rinfo[probe].diff <= rinfo[cur_sorted].diff && 99 rate_supported(sta, band, rinfo[probe].index)) 100 tmp = probe; 101 } else { 102 /* Look for rate increase with zero (or below) cost. */ 103 for (probe = new_sorted + 1; probe < n_bitrates; probe++) 104 if (rinfo[probe].diff <= rinfo[new_sorted].diff && 105 rate_supported(sta, band, rinfo[probe].index)) 106 tmp = probe; 107 } 108 109 /* Fit the rate found to the nearest supported rate. */ 110 do { 111 if (rate_supported(sta, band, rinfo[tmp].index)) { 112 spinfo->txrate_idx = rinfo[tmp].index; 113 break; 114 } 115 if (adj < 0) 116 tmp--; 117 else 118 tmp++; 119 } while (tmp < n_bitrates && tmp >= 0); 120 121#ifdef CONFIG_MAC80211_DEBUGFS 122 rate_control_pid_event_rate_change(&spinfo->events, 123 spinfo->txrate_idx, 124 sband->bitrates[spinfo->txrate_idx].bitrate); 125#endif 126} 127 128/* Normalize the failed frames per-rate differences. */ 129static void rate_control_pid_normalize(struct rc_pid_info *pinfo, int l) 130{ 131 int i, norm_offset = pinfo->norm_offset; 132 struct rc_pid_rateinfo *r = pinfo->rinfo; 133 134 if (r[0].diff > norm_offset) 135 r[0].diff -= norm_offset; 136 else if (r[0].diff < -norm_offset) 137 r[0].diff += norm_offset; 138 for (i = 0; i < l - 1; i++) 139 if (r[i + 1].diff > r[i].diff + norm_offset) 140 r[i + 1].diff -= norm_offset; 141 else if (r[i + 1].diff <= r[i].diff) 142 r[i + 1].diff += norm_offset; 143} 144 145static void rate_control_pid_sample(struct rc_pid_info *pinfo, 146 struct ieee80211_supported_band *sband, 147 struct ieee80211_sta *sta, 148 struct rc_pid_sta_info *spinfo) 149{ 150 struct rc_pid_rateinfo *rinfo = pinfo->rinfo; 151 u32 pf; 152 s32 err_avg; 153 u32 err_prop; 154 u32 err_int; 155 u32 err_der; 156 int adj, i, j, tmp; 157 unsigned long period; 158 159 /* In case nothing happened during the previous control interval, turn 160 * the sharpening factor on. */ 161 period = msecs_to_jiffies(pinfo->sampling_period); 162 if (jiffies - spinfo->last_sample > 2 * period) 163 spinfo->sharp_cnt = pinfo->sharpen_duration; 164 165 spinfo->last_sample = jiffies; 166 167 /* This should never happen, but in case, we assume the old sample is 168 * still a good measurement and copy it. */ 169 if (unlikely(spinfo->tx_num_xmit == 0)) 170 pf = spinfo->last_pf; 171 else 172 pf = spinfo->tx_num_failed * 100 / spinfo->tx_num_xmit; 173 174 spinfo->tx_num_xmit = 0; 175 spinfo->tx_num_failed = 0; 176 177 /* If we just switched rate, update the rate behaviour info. */ 178 if (pinfo->oldrate != spinfo->txrate_idx) { 179 180 i = rinfo[pinfo->oldrate].rev_index; 181 j = rinfo[spinfo->txrate_idx].rev_index; 182 183 tmp = (pf - spinfo->last_pf); 184 tmp = RC_PID_DO_ARITH_RIGHT_SHIFT(tmp, RC_PID_ARITH_SHIFT); 185 186 rinfo[j].diff = rinfo[i].diff + tmp; 187 pinfo->oldrate = spinfo->txrate_idx; 188 } 189 rate_control_pid_normalize(pinfo, sband->n_bitrates); 190 191 /* Compute the proportional, integral and derivative errors. */ 192 err_prop = (pinfo->target - pf) << RC_PID_ARITH_SHIFT; 193 194 err_avg = spinfo->err_avg_sc >> pinfo->smoothing_shift; 195 spinfo->err_avg_sc = spinfo->err_avg_sc - err_avg + err_prop; 196 err_int = spinfo->err_avg_sc >> pinfo->smoothing_shift; 197 198 err_der = (pf - spinfo->last_pf) * 199 (1 + pinfo->sharpen_factor * spinfo->sharp_cnt); 200 spinfo->last_pf = pf; 201 if (spinfo->sharp_cnt) 202 spinfo->sharp_cnt--; 203 204#ifdef CONFIG_MAC80211_DEBUGFS 205 rate_control_pid_event_pf_sample(&spinfo->events, pf, err_prop, err_int, 206 err_der); 207#endif 208 209 /* Compute the controller output. */ 210 adj = (err_prop * pinfo->coeff_p + err_int * pinfo->coeff_i 211 + err_der * pinfo->coeff_d); 212 adj = RC_PID_DO_ARITH_RIGHT_SHIFT(adj, 2 * RC_PID_ARITH_SHIFT); 213 214 /* Change rate. */ 215 if (adj) 216 rate_control_pid_adjust_rate(sband, sta, spinfo, adj, rinfo); 217} 218 219static void rate_control_pid_tx_status(void *priv, struct ieee80211_supported_band *sband, 220 struct ieee80211_sta *sta, void *priv_sta, 221 struct sk_buff *skb) 222{ 223 struct rc_pid_info *pinfo = priv; 224 struct rc_pid_sta_info *spinfo = priv_sta; 225 unsigned long period; 226 struct ieee80211_tx_info *info = IEEE80211_SKB_CB(skb); 227 228 if (!spinfo) 229 return; 230 231 /* Ignore all frames that were sent with a different rate than the rate 232 * we currently advise mac80211 to use. */ 233 if (info->status.rates[0].idx != spinfo->txrate_idx) 234 return; 235 236 spinfo->tx_num_xmit++; 237 238#ifdef CONFIG_MAC80211_DEBUGFS 239 rate_control_pid_event_tx_status(&spinfo->events, info); 240#endif 241 242 /* We count frames that totally failed to be transmitted as two bad 243 * frames, those that made it out but had some retries as one good and 244 * one bad frame. */ 245 if (!(info->flags & IEEE80211_TX_STAT_ACK)) { 246 spinfo->tx_num_failed += 2; 247 spinfo->tx_num_xmit++; 248 } else if (info->status.rates[0].count > 1) { 249 spinfo->tx_num_failed++; 250 spinfo->tx_num_xmit++; 251 } 252 253 /* Update PID controller state. */ 254 period = msecs_to_jiffies(pinfo->sampling_period); 255 if (time_after(jiffies, spinfo->last_sample + period)) 256 rate_control_pid_sample(pinfo, sband, sta, spinfo); 257} 258 259static void 260rate_control_pid_get_rate(void *priv, struct ieee80211_sta *sta, 261 void *priv_sta, 262 struct ieee80211_tx_rate_control *txrc) 263{ 264 struct sk_buff *skb = txrc->skb; 265 struct ieee80211_supported_band *sband = txrc->sband; 266 struct ieee80211_tx_info *info = IEEE80211_SKB_CB(skb); 267 struct rc_pid_sta_info *spinfo = priv_sta; 268 int rateidx; 269 270 if (txrc->rts) 271 info->control.rates[0].count = 272 txrc->hw->conf.long_frame_max_tx_count; 273 else 274 info->control.rates[0].count = 275 txrc->hw->conf.short_frame_max_tx_count; 276 277 /* Send management frames and NO_ACK data using lowest rate. */ 278 if (rate_control_send_low(sta, priv_sta, txrc)) 279 return; 280 281 rateidx = spinfo->txrate_idx; 282 283 if (rateidx >= sband->n_bitrates) 284 rateidx = sband->n_bitrates - 1; 285 286 info->control.rates[0].idx = rateidx; 287 288#ifdef CONFIG_MAC80211_DEBUGFS 289 rate_control_pid_event_tx_rate(&spinfo->events, 290 rateidx, sband->bitrates[rateidx].bitrate); 291#endif 292} 293 294static void 295rate_control_pid_rate_init(void *priv, struct ieee80211_supported_band *sband, 296 struct ieee80211_sta *sta, void *priv_sta) 297{ 298 struct rc_pid_sta_info *spinfo = priv_sta; 299 struct rc_pid_info *pinfo = priv; 300 struct rc_pid_rateinfo *rinfo = pinfo->rinfo; 301 int i, j, tmp; 302 bool s; 303 304 305 /* Sort the rates. This is optimized for the most common case (i.e. 306 * almost-sorted CCK+OFDM rates). Kind of bubble-sort with reversed 307 * mapping too. */ 308 for (i = 0; i < sband->n_bitrates; i++) { 309 rinfo[i].index = i; 310 rinfo[i].rev_index = i; 311 if (RC_PID_FAST_START) 312 rinfo[i].diff = 0; 313 else 314 rinfo[i].diff = i * pinfo->norm_offset; 315 } 316 for (i = 1; i < sband->n_bitrates; i++) { 317 s = 0; 318 for (j = 0; j < sband->n_bitrates - i; j++) 319 if (unlikely(sband->bitrates[rinfo[j].index].bitrate > 320 sband->bitrates[rinfo[j + 1].index].bitrate)) { 321 tmp = rinfo[j].index; 322 rinfo[j].index = rinfo[j + 1].index; 323 rinfo[j + 1].index = tmp; 324 rinfo[rinfo[j].index].rev_index = j; 325 rinfo[rinfo[j + 1].index].rev_index = j + 1; 326 s = 1; 327 } 328 if (!s) 329 break; 330 } 331 332 spinfo->txrate_idx = rate_lowest_index(sband, sta); 333} 334 335static void *rate_control_pid_alloc(struct ieee80211_hw *hw, 336 struct dentry *debugfsdir) 337{ 338 struct rc_pid_info *pinfo; 339 struct rc_pid_rateinfo *rinfo; 340 struct ieee80211_supported_band *sband; 341 int i, max_rates = 0; 342#ifdef CONFIG_MAC80211_DEBUGFS 343 struct rc_pid_debugfs_entries *de; 344#endif 345 346 pinfo = kmalloc(sizeof(*pinfo), GFP_ATOMIC); 347 if (!pinfo) 348 return NULL; 349 350 for (i = 0; i < IEEE80211_NUM_BANDS; i++) { 351 sband = hw->wiphy->bands[i]; 352 if (sband && sband->n_bitrates > max_rates) 353 max_rates = sband->n_bitrates; 354 } 355 356 rinfo = kmalloc(sizeof(*rinfo) * max_rates, GFP_ATOMIC); 357 if (!rinfo) { 358 kfree(pinfo); 359 return NULL; 360 } 361 362 pinfo->target = RC_PID_TARGET_PF; 363 pinfo->sampling_period = RC_PID_INTERVAL; 364 pinfo->coeff_p = RC_PID_COEFF_P; 365 pinfo->coeff_i = RC_PID_COEFF_I; 366 pinfo->coeff_d = RC_PID_COEFF_D; 367 pinfo->smoothing_shift = RC_PID_SMOOTHING_SHIFT; 368 pinfo->sharpen_factor = RC_PID_SHARPENING_FACTOR; 369 pinfo->sharpen_duration = RC_PID_SHARPENING_DURATION; 370 pinfo->norm_offset = RC_PID_NORM_OFFSET; 371 pinfo->rinfo = rinfo; 372 pinfo->oldrate = 0; 373 374#ifdef CONFIG_MAC80211_DEBUGFS 375 de = &pinfo->dentries; 376 de->target = debugfs_create_u32("target_pf", S_IRUSR | S_IWUSR, 377 debugfsdir, &pinfo->target); 378 de->sampling_period = debugfs_create_u32("sampling_period", 379 S_IRUSR | S_IWUSR, debugfsdir, 380 &pinfo->sampling_period); 381 de->coeff_p = debugfs_create_u32("coeff_p", S_IRUSR | S_IWUSR, 382 debugfsdir, (u32 *)&pinfo->coeff_p); 383 de->coeff_i = debugfs_create_u32("coeff_i", S_IRUSR | S_IWUSR, 384 debugfsdir, (u32 *)&pinfo->coeff_i); 385 de->coeff_d = debugfs_create_u32("coeff_d", S_IRUSR | S_IWUSR, 386 debugfsdir, (u32 *)&pinfo->coeff_d); 387 de->smoothing_shift = debugfs_create_u32("smoothing_shift", 388 S_IRUSR | S_IWUSR, debugfsdir, 389 &pinfo->smoothing_shift); 390 de->sharpen_factor = debugfs_create_u32("sharpen_factor", 391 S_IRUSR | S_IWUSR, debugfsdir, 392 &pinfo->sharpen_factor); 393 de->sharpen_duration = debugfs_create_u32("sharpen_duration", 394 S_IRUSR | S_IWUSR, debugfsdir, 395 &pinfo->sharpen_duration); 396 de->norm_offset = debugfs_create_u32("norm_offset", 397 S_IRUSR | S_IWUSR, debugfsdir, 398 &pinfo->norm_offset); 399#endif 400 401 return pinfo; 402} 403 404static void rate_control_pid_free(void *priv) 405{ 406 struct rc_pid_info *pinfo = priv; 407#ifdef CONFIG_MAC80211_DEBUGFS 408 struct rc_pid_debugfs_entries *de = &pinfo->dentries; 409 410 debugfs_remove(de->norm_offset); 411 debugfs_remove(de->sharpen_duration); 412 debugfs_remove(de->sharpen_factor); 413 debugfs_remove(de->smoothing_shift); 414 debugfs_remove(de->coeff_d); 415 debugfs_remove(de->coeff_i); 416 debugfs_remove(de->coeff_p); 417 debugfs_remove(de->sampling_period); 418 debugfs_remove(de->target); 419#endif 420 421 kfree(pinfo->rinfo); 422 kfree(pinfo); 423} 424 425static void *rate_control_pid_alloc_sta(void *priv, struct ieee80211_sta *sta, 426 gfp_t gfp) 427{ 428 struct rc_pid_sta_info *spinfo; 429 430 spinfo = kzalloc(sizeof(*spinfo), gfp); 431 if (spinfo == NULL) 432 return NULL; 433 434 spinfo->last_sample = jiffies; 435 436#ifdef CONFIG_MAC80211_DEBUGFS 437 spin_lock_init(&spinfo->events.lock); 438 init_waitqueue_head(&spinfo->events.waitqueue); 439#endif 440 441 return spinfo; 442} 443 444static void rate_control_pid_free_sta(void *priv, struct ieee80211_sta *sta, 445 void *priv_sta) 446{ 447 kfree(priv_sta); 448} 449 450static struct rate_control_ops mac80211_rcpid = { 451 .name = "pid", 452 .tx_status = rate_control_pid_tx_status, 453 .get_rate = rate_control_pid_get_rate, 454 .rate_init = rate_control_pid_rate_init, 455 .alloc = rate_control_pid_alloc, 456 .free = rate_control_pid_free, 457 .alloc_sta = rate_control_pid_alloc_sta, 458 .free_sta = rate_control_pid_free_sta, 459#ifdef CONFIG_MAC80211_DEBUGFS 460 .add_sta_debugfs = rate_control_pid_add_sta_debugfs, 461 .remove_sta_debugfs = rate_control_pid_remove_sta_debugfs, 462#endif 463}; 464 465int __init rc80211_pid_init(void) 466{ 467 return ieee80211_rate_control_register(&mac80211_rcpid); 468} 469 470void rc80211_pid_exit(void) 471{ 472 ieee80211_rate_control_unregister(&mac80211_rcpid); 473} 474