net/mac80211/rc80211_pid.h

   1 /*
   2  * Copyright 2007, Mattias Nissler <mattias.nissler@gmx.de>
   3  * Copyright 2007, Stefano Brivio <stefano.brivio@polimi.it>
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License version 2 as
   7  * published by the Free Software Foundation.
   8  */
   9
  10 #ifndef RC80211_PID_H
  11 #define RC80211_PID_H
  12
  13 /* Sampling period for measuring percentage of failed frames in ms. */
  14 #define RC_PID_INTERVAL                 125
  15
  16 /* Exponential averaging smoothness (used for I part of PID controller) */
  17 #define RC_PID_SMOOTHING_SHIFT          3
  18 #define RC_PID_SMOOTHING                (1 << RC_PID_SMOOTHING_SHIFT)
  19
  20 /* Sharpening factor (used for D part of PID controller) */
  21 #define RC_PID_SHARPENING_FACTOR        0
  22 #define RC_PID_SHARPENING_DURATION      0
  23
  24 /* Fixed point arithmetic shifting amount. */
  25 #define RC_PID_ARITH_SHIFT              8
  26
  27 /* Fixed point arithmetic factor. */
  28 #define RC_PID_ARITH_FACTOR             (1 << RC_PID_ARITH_SHIFT)
  29
  30 /* Proportional PID component coefficient. */
  31 #define RC_PID_COEFF_P                  15
  32 /* Integral PID component coefficient. */
  33 #define RC_PID_COEFF_I                  9
  34 /* Derivative PID component coefficient. */
  35 #define RC_PID_COEFF_D                  15
  36
  37 /* Target failed frames rate for the PID controller. NB: This effectively gives
  38  * maximum failed frames percentage we're willing to accept. If the wireless
  39  * link quality is good, the controller will fail to adjust failed frames
  40  * percentage to the target. This is intentional.
  41  */
  42 #define RC_PID_TARGET_PF                14
  43
  44 /* Rate behaviour normalization quantity over time. */
  45 #define RC_PID_NORM_OFFSET              3
  46
  47 /* Push high rates right after loading. */
  48 #define RC_PID_FAST_START               0
  49
  50 /* Arithmetic right shift for positive and negative values for ISO C. */
  51 #define RC_PID_DO_ARITH_RIGHT_SHIFT(x, y) \
  52         (x) < 0 ? -((-(x)) >> (y)) : (x) >> (y)
  53
  54 enum rc_pid_event_type {
  55         RC_PID_EVENT_TYPE_TX_STATUS,
  56         RC_PID_EVENT_TYPE_RATE_CHANGE,
  57         RC_PID_EVENT_TYPE_TX_RATE,
  58         RC_PID_EVENT_TYPE_PF_SAMPLE,
  59 };
  60
  61 union rc_pid_event_data {
  62         /* RC_PID_EVENT_TX_STATUS */
  63         struct {
  64                 struct ieee80211_tx_status tx_status;
  65         };
  66         /* RC_PID_EVENT_TYPE_RATE_CHANGE */
  67         /* RC_PID_EVENT_TYPE_TX_RATE */
  68         struct {
  69                 int index;
  70                 int rate;
  71         };
  72         /* RC_PID_EVENT_TYPE_PF_SAMPLE */
  73         struct {
  74                 s32 pf_sample;
  75                 s32 prop_err;
  76                 s32 int_err;
  77                 s32 der_err;
  78         };
  79 };
  80
  81 struct rc_pid_event {
  82         /* The time when the event occured */
  83         unsigned long timestamp;
  84
  85         /* Event ID number */
  86         unsigned int id;
  87
  88         /* Type of event */
  89         enum rc_pid_event_type type;
  90
  91         /* type specific data */
  92         union rc_pid_event_data data;
  93 };
  94
  95 /* Size of the event ring buffer. */
  96 #define RC_PID_EVENT_RING_SIZE 32
  97
  98 struct rc_pid_event_buffer {
  99         /* Counter that generates event IDs */
 100         unsigned int ev_count;
 101
 102         /* Ring buffer of events */
 103         struct rc_pid_event ring[RC_PID_EVENT_RING_SIZE];
 104
 105         /* Index to the entry in events_buf to be reused */
 106         unsigned int next_entry;
 107
 108         /* Lock that guards against concurrent access to this buffer struct */
 109         spinlock_t lock;
 110
 111         /* Wait queue for poll/select and blocking I/O */
 112         wait_queue_head_t waitqueue;
 113 };
 114
 115 struct rc_pid_events_file_info {
 116         /* The event buffer we read */
 117         struct rc_pid_event_buffer *events;
 118
 119         /* The entry we have should read next */
 120         unsigned int next_entry;
 121 };
 122
 123 /**
 124  * struct rc_pid_debugfs_entries - tunable parameters
 125  *
 126  * Algorithm parameters, tunable via debugfs.
 127  * @dir: the debugfs directory for a specific phy
 128  * @target: target percentage for failed frames
 129  * @sampling_period: error sampling interval in milliseconds
 130  * @coeff_p: absolute value of the proportional coefficient
 131  * @coeff_i: absolute value of the integral coefficient
 132  * @coeff_d: absolute value of the derivative coefficient
 133  * @smoothing_shift: absolute value of the integral smoothing factor (i.e.
 134  *      amount of smoothing introduced by the exponential moving average)
 135  * @sharpen_factor: absolute value of the derivative sharpening factor (i.e.
 136  *      amount of emphasis given to the derivative term after low activity
 137  *      events)
 138  * @sharpen_duration: duration of the sharpening effect after the detected low
 139  *      activity event, relative to sampling_period
 140  * @norm_offset: amount of normalization periodically performed on the learnt
 141  *      rate behaviour values (lower means we should trust more what we learnt
 142  *      about behaviour of rates, higher means we should trust more the natural
 143  *      ordering of rates)
 144  * @fast_start: if Y, push high rates right after initialization
 145  */
 146 struct rc_pid_debugfs_entries {
 147         struct dentry *dir;
 148         struct dentry *target;
 149         struct dentry *sampling_period;
 150         struct dentry *coeff_p;
 151         struct dentry *coeff_i;
 152         struct dentry *coeff_d;
 153         struct dentry *smoothing_shift;
 154         struct dentry *sharpen_factor;
 155         struct dentry *sharpen_duration;
 156         struct dentry *norm_offset;
 157         struct dentry *fast_start;
 158 };
 159
 160 void rate_control_pid_event_tx_status(struct rc_pid_event_buffer *buf,
 161                                              struct ieee80211_tx_status *stat);
 162
 163 void rate_control_pid_event_rate_change(struct rc_pid_event_buffer *buf,
 164                                                int index, int rate);
 165
 166 void rate_control_pid_event_tx_rate(struct rc_pid_event_buffer *buf,
 167                                            int index, int rate);
 168
 169 void rate_control_pid_event_pf_sample(struct rc_pid_event_buffer *buf,
 170                                              s32 pf_sample, s32 prop_err,
 171                                              s32 int_err, s32 der_err);
 172
 173 void rate_control_pid_add_sta_debugfs(void *priv, void *priv_sta,
 174                                              struct dentry *dir);
 175
 176 void rate_control_pid_remove_sta_debugfs(void *priv, void *priv_sta);
 177
 178 struct rc_pid_sta_info {
 179         unsigned long last_change;
 180         unsigned long last_sample;
 181
 182         u32 tx_num_failed;
 183         u32 tx_num_xmit;
 184
 185         /* Average failed frames percentage error (i.e. actual vs. target
 186          * percentage), scaled by RC_PID_SMOOTHING. This value is computed
 187          * using using an exponential weighted average technique:
 188          *
 189          *           (RC_PID_SMOOTHING - 1) * err_avg_old + err
 190          * err_avg = ------------------------------------------
 191          *                       RC_PID_SMOOTHING
 192          *
 193          * where err_avg is the new approximation, err_avg_old the previous one
 194          * and err is the error w.r.t. to the current failed frames percentage
 195          * sample. Note that the bigger RC_PID_SMOOTHING the more weight is
 196          * given to the previous estimate, resulting in smoother behavior (i.e.
 197          * corresponding to a longer integration window).
 198          *
 199          * For computation, we actually don't use the above formula, but this
 200          * one:
 201          *
 202          * err_avg_scaled = err_avg_old_scaled - err_avg_old + err
 203          *
 204          * where:
 205          *      err_avg_scaled = err * RC_PID_SMOOTHING
 206          *      err_avg_old_scaled = err_avg_old * RC_PID_SMOOTHING
 207          *
 208          * This avoids floating point numbers and the per_failed_old value can
 209          * easily be obtained by shifting per_failed_old_scaled right by
 210          * RC_PID_SMOOTHING_SHIFT.
 211          */
 212         s32 err_avg_sc;
 213
 214         /* Last framed failes percentage sample. */
 215         u32 last_pf;
 216
 217         /* Sharpening needed. */
 218         u8 sharp_cnt;
 219
 220 #ifdef CONFIG_MAC80211_DEBUGFS
 221         /* Event buffer */
 222         struct rc_pid_event_buffer events;
 223
 224         /* Events debugfs file entry */
 225         struct dentry *events_entry;
 226 #endif
 227 };
 228
 229 /* Algorithm parameters. We keep them on a per-algorithm approach, so they can
 230  * be tuned individually for each interface.
 231  */
 232 struct rc_pid_rateinfo {
 233
 234         /* Map sorted rates to rates in ieee80211_hw_mode. */
 235         int index;
 236
 237         /* Map rates in ieee80211_hw_mode to sorted rates. */
 238         int rev_index;
 239
 240         /* Did we do any measurement on this rate? */
 241         bool valid;
 242
 243         /* Comparison with the lowest rate. */
 244         int diff;
 245 };
 246
 247 struct rc_pid_info {
 248
 249         /* The failed frames percentage target. */
 250         unsigned int target;
 251
 252         /* Rate at which failed frames percentage is sampled in 0.001s. */
 253         unsigned int sampling_period;
 254
 255         /* P, I and D coefficients. */
 256         int coeff_p;
 257         int coeff_i;
 258         int coeff_d;
 259
 260         /* Exponential averaging shift. */
 261         unsigned int smoothing_shift;
 262
 263         /* Sharpening factor and duration. */
 264         unsigned int sharpen_factor;
 265         unsigned int sharpen_duration;
 266
 267         /* Normalization offset. */
 268         unsigned int norm_offset;
 269
 270         /* Fast starst parameter. */
 271         unsigned int fast_start;
 272
 273         /* Rates information. */
 274         struct rc_pid_rateinfo *rinfo;
 275
 276         /* Index of the last used rate. */
 277         int oldrate;
 278
 279 #ifdef CONFIG_MAC80211_DEBUGFS
 280         /* Debugfs entries created for the parameters above. */
 281         struct rc_pid_debugfs_entries dentries;
 282 #endif
 283 };
 284
 285 #endif /* RC80211_PID_H */