gen_estimator.c 6.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249
  1. /*
  2. * net/sched/gen_estimator.c Simple rate estimator.
  3. *
  4. * This program is free software; you can redistribute it and/or
  5. * modify it under the terms of the GNU General Public License
  6. * as published by the Free Software Foundation; either version
  7. * 2 of the License, or (at your option) any later version.
  8. *
  9. * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
  10. *
  11. * Changes:
  12. * Jamal Hadi Salim - moved it to net/core and reshulfed
  13. * names to make it usable in general net subsystem.
  14. */
  15. #include <asm/uaccess.h>
  16. #include <asm/system.h>
  17. #include <asm/bitops.h>
  18. #include <linux/module.h>
  19. #include <linux/types.h>
  20. #include <linux/kernel.h>
  21. #include <linux/jiffies.h>
  22. #include <linux/string.h>
  23. #include <linux/mm.h>
  24. #include <linux/socket.h>
  25. #include <linux/sockios.h>
  26. #include <linux/in.h>
  27. #include <linux/errno.h>
  28. #include <linux/interrupt.h>
  29. #include <linux/netdevice.h>
  30. #include <linux/skbuff.h>
  31. #include <linux/rtnetlink.h>
  32. #include <linux/init.h>
  33. #include <net/sock.h>
  34. #include <net/gen_stats.h>
  35. /*
  36. This code is NOT intended to be used for statistics collection,
  37. its purpose is to provide a base for statistical multiplexing
  38. for controlled load service.
  39. If you need only statistics, run a user level daemon which
  40. periodically reads byte counters.
  41. Unfortunately, rate estimation is not a very easy task.
  42. F.e. I did not find a simple way to estimate the current peak rate
  43. and even failed to formulate the problem 8)8)
  44. So I preferred not to built an estimator into the scheduler,
  45. but run this task separately.
  46. Ideally, it should be kernel thread(s), but for now it runs
  47. from timers, which puts apparent top bounds on the number of rated
  48. flows, has minimal overhead on small, but is enough
  49. to handle controlled load service, sets of aggregates.
  50. We measure rate over A=(1<<interval) seconds and evaluate EWMA:
  51. avrate = avrate*(1-W) + rate*W
  52. where W is chosen as negative power of 2: W = 2^(-ewma_log)
  53. The resulting time constant is:
  54. T = A/(-ln(1-W))
  55. NOTES.
  56. * The stored value for avbps is scaled by 2^5, so that maximal
  57. rate is ~1Gbit, avpps is scaled by 2^10.
  58. * Minimal interval is HZ/4=250msec (it is the greatest common divisor
  59. for HZ=100 and HZ=1024 8)), maximal interval
  60. is (HZ*2^EST_MAX_INTERVAL)/4 = 8sec. Shorter intervals
  61. are too expensive, longer ones can be implemented
  62. at user level painlessly.
  63. */
  64. #define EST_MAX_INTERVAL 5
  65. struct gen_estimator
  66. {
  67. struct gen_estimator *next;
  68. struct gnet_stats_basic *bstats;
  69. struct gnet_stats_rate_est *rate_est;
  70. spinlock_t *stats_lock;
  71. unsigned interval;
  72. int ewma_log;
  73. u64 last_bytes;
  74. u32 last_packets;
  75. u32 avpps;
  76. u32 avbps;
  77. };
  78. struct gen_estimator_head
  79. {
  80. struct timer_list timer;
  81. struct gen_estimator *list;
  82. };
  83. static struct gen_estimator_head elist[EST_MAX_INTERVAL+1];
  84. /* Estimator array lock */
  85. static DEFINE_RWLOCK(est_lock);
  86. static void est_timer(unsigned long arg)
  87. {
  88. int idx = (int)arg;
  89. struct gen_estimator *e;
  90. read_lock(&est_lock);
  91. for (e = elist[idx].list; e; e = e->next) {
  92. u64 nbytes;
  93. u32 npackets;
  94. u32 rate;
  95. spin_lock(e->stats_lock);
  96. nbytes = e->bstats->bytes;
  97. npackets = e->bstats->packets;
  98. rate = (nbytes - e->last_bytes)<<(7 - idx);
  99. e->last_bytes = nbytes;
  100. e->avbps += ((long)rate - (long)e->avbps) >> e->ewma_log;
  101. e->rate_est->bps = (e->avbps+0xF)>>5;
  102. rate = (npackets - e->last_packets)<<(12 - idx);
  103. e->last_packets = npackets;
  104. e->avpps += ((long)rate - (long)e->avpps) >> e->ewma_log;
  105. e->rate_est->pps = (e->avpps+0x1FF)>>10;
  106. spin_unlock(e->stats_lock);
  107. }
  108. mod_timer(&elist[idx].timer, jiffies + ((HZ<<idx)/4));
  109. read_unlock(&est_lock);
  110. }
  111. /**
  112. * gen_new_estimator - create a new rate estimator
  113. * @bstats: basic statistics
  114. * @rate_est: rate estimator statistics
  115. * @stats_lock: statistics lock
  116. * @opt: rate estimator configuration TLV
  117. *
  118. * Creates a new rate estimator with &bstats as source and &rate_est
  119. * as destination. A new timer with the interval specified in the
  120. * configuration TLV is created. Upon each interval, the latest statistics
  121. * will be read from &bstats and the estimated rate will be stored in
  122. * &rate_est with the statistics lock grabed during this period.
  123. *
  124. * Returns 0 on success or a negative error code.
  125. */
  126. int gen_new_estimator(struct gnet_stats_basic *bstats,
  127. struct gnet_stats_rate_est *rate_est, spinlock_t *stats_lock, struct rtattr *opt)
  128. {
  129. struct gen_estimator *est;
  130. struct gnet_estimator *parm = RTA_DATA(opt);
  131. if (RTA_PAYLOAD(opt) < sizeof(*parm))
  132. return -EINVAL;
  133. if (parm->interval < -2 || parm->interval > 3)
  134. return -EINVAL;
  135. est = kzalloc(sizeof(*est), GFP_KERNEL);
  136. if (est == NULL)
  137. return -ENOBUFS;
  138. est->interval = parm->interval + 2;
  139. est->bstats = bstats;
  140. est->rate_est = rate_est;
  141. est->stats_lock = stats_lock;
  142. est->ewma_log = parm->ewma_log;
  143. est->last_bytes = bstats->bytes;
  144. est->avbps = rate_est->bps<<5;
  145. est->last_packets = bstats->packets;
  146. est->avpps = rate_est->pps<<10;
  147. est->next = elist[est->interval].list;
  148. if (est->next == NULL) {
  149. init_timer(&elist[est->interval].timer);
  150. elist[est->interval].timer.data = est->interval;
  151. elist[est->interval].timer.expires = jiffies + ((HZ<<est->interval)/4);
  152. elist[est->interval].timer.function = est_timer;
  153. add_timer(&elist[est->interval].timer);
  154. }
  155. write_lock_bh(&est_lock);
  156. elist[est->interval].list = est;
  157. write_unlock_bh(&est_lock);
  158. return 0;
  159. }
  160. /**
  161. * gen_kill_estimator - remove a rate estimator
  162. * @bstats: basic statistics
  163. * @rate_est: rate estimator statistics
  164. *
  165. * Removes the rate estimator specified by &bstats and &rate_est
  166. * and deletes the timer.
  167. */
  168. void gen_kill_estimator(struct gnet_stats_basic *bstats,
  169. struct gnet_stats_rate_est *rate_est)
  170. {
  171. int idx;
  172. struct gen_estimator *est, **pest;
  173. for (idx=0; idx <= EST_MAX_INTERVAL; idx++) {
  174. int killed = 0;
  175. pest = &elist[idx].list;
  176. while ((est=*pest) != NULL) {
  177. if (est->rate_est != rate_est || est->bstats != bstats) {
  178. pest = &est->next;
  179. continue;
  180. }
  181. write_lock_bh(&est_lock);
  182. *pest = est->next;
  183. write_unlock_bh(&est_lock);
  184. kfree(est);
  185. killed++;
  186. }
  187. if (killed && elist[idx].list == NULL)
  188. del_timer(&elist[idx].timer);
  189. }
  190. }
  191. /**
  192. * gen_replace_estimator - replace rate estimator configruation
  193. * @bstats: basic statistics
  194. * @rate_est: rate estimator statistics
  195. * @stats_lock: statistics lock
  196. * @opt: rate estimator configuration TLV
  197. *
  198. * Replaces the configuration of a rate estimator by calling
  199. * gen_kill_estimator() and gen_new_estimator().
  200. *
  201. * Returns 0 on success or a negative error code.
  202. */
  203. int
  204. gen_replace_estimator(struct gnet_stats_basic *bstats,
  205. struct gnet_stats_rate_est *rate_est, spinlock_t *stats_lock,
  206. struct rtattr *opt)
  207. {
  208. gen_kill_estimator(bstats, rate_est);
  209. return gen_new_estimator(bstats, rate_est, stats_lock, opt);
  210. }
  211. EXPORT_SYMBOL(gen_kill_estimator);
  212. EXPORT_SYMBOL(gen_new_estimator);
  213. EXPORT_SYMBOL(gen_replace_estimator);