xt_limit.c 6.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217
  1. /* Kernel module to control the rate
  2. *
  3. * 2 September 1999: Changed from the target RATE to the match
  4. * `limit', removed logging. Did I mention that
  5. * Alexey is a fucking genius?
  6. * Rusty Russell (rusty@rustcorp.com.au). */
  7. /* (C) 1999 Jérôme de Vivie <devivie@info.enserb.u-bordeaux.fr>
  8. * (C) 1999 Hervé Eychenne <eychenne@info.enserb.u-bordeaux.fr>
  9. *
  10. * This program is free software; you can redistribute it and/or modify
  11. * it under the terms of the GNU General Public License version 2 as
  12. * published by the Free Software Foundation.
  13. */
  14. #include <linux/module.h>
  15. #include <linux/skbuff.h>
  16. #include <linux/spinlock.h>
  17. #include <linux/interrupt.h>
  18. #include <linux/netfilter/x_tables.h>
  19. #include <linux/netfilter/xt_limit.h>
  20. MODULE_LICENSE("GPL");
  21. MODULE_AUTHOR("Herve Eychenne <rv@wallfire.org>");
  22. MODULE_DESCRIPTION("iptables rate limit match");
  23. MODULE_ALIAS("ipt_limit");
  24. MODULE_ALIAS("ip6t_limit");
  25. /* The algorithm used is the Simple Token Bucket Filter (TBF)
  26. * see net/sched/sch_tbf.c in the linux source tree
  27. */
  28. static DEFINE_SPINLOCK(limit_lock);
  29. /* Rusty: This is my (non-mathematically-inclined) understanding of
  30. this algorithm. The `average rate' in jiffies becomes your initial
  31. amount of credit `credit' and the most credit you can ever have
  32. `credit_cap'. The `peak rate' becomes the cost of passing the
  33. test, `cost'.
  34. `prev' tracks the last packet hit: you gain one credit per jiffy.
  35. If you get credit balance more than this, the extra credit is
  36. discarded. Every time the match passes, you lose `cost' credits;
  37. if you don't have that many, the test fails.
  38. See Alexey's formal explanation in net/sched/sch_tbf.c.
  39. To get the maxmum range, we multiply by this factor (ie. you get N
  40. credits per jiffy). We want to allow a rate as low as 1 per day
  41. (slowest userspace tool allows), which means
  42. CREDITS_PER_JIFFY*HZ*60*60*24 < 2^32. ie. */
  43. #define MAX_CPJ (0xFFFFFFFF / (HZ*60*60*24))
  44. /* Repeated shift and or gives us all 1s, final shift and add 1 gives
  45. * us the power of 2 below the theoretical max, so GCC simply does a
  46. * shift. */
  47. #define _POW2_BELOW2(x) ((x)|((x)>>1))
  48. #define _POW2_BELOW4(x) (_POW2_BELOW2(x)|_POW2_BELOW2((x)>>2))
  49. #define _POW2_BELOW8(x) (_POW2_BELOW4(x)|_POW2_BELOW4((x)>>4))
  50. #define _POW2_BELOW16(x) (_POW2_BELOW8(x)|_POW2_BELOW8((x)>>8))
  51. #define _POW2_BELOW32(x) (_POW2_BELOW16(x)|_POW2_BELOW16((x)>>16))
  52. #define POW2_BELOW32(x) ((_POW2_BELOW32(x)>>1) + 1)
  53. #define CREDITS_PER_JIFFY POW2_BELOW32(MAX_CPJ)
  54. static int
  55. ipt_limit_match(const struct sk_buff *skb,
  56. const struct net_device *in,
  57. const struct net_device *out,
  58. const struct xt_match *match,
  59. const void *matchinfo,
  60. int offset,
  61. unsigned int protoff,
  62. int *hotdrop)
  63. {
  64. struct xt_rateinfo *r = ((struct xt_rateinfo *)matchinfo)->master;
  65. unsigned long now = jiffies;
  66. spin_lock_bh(&limit_lock);
  67. r->credit += (now - xchg(&r->prev, now)) * CREDITS_PER_JIFFY;
  68. if (r->credit > r->credit_cap)
  69. r->credit = r->credit_cap;
  70. if (r->credit >= r->cost) {
  71. /* We're not limited. */
  72. r->credit -= r->cost;
  73. spin_unlock_bh(&limit_lock);
  74. return 1;
  75. }
  76. spin_unlock_bh(&limit_lock);
  77. return 0;
  78. }
  79. /* Precision saver. */
  80. static u_int32_t
  81. user2credits(u_int32_t user)
  82. {
  83. /* If multiplying would overflow... */
  84. if (user > 0xFFFFFFFF / (HZ*CREDITS_PER_JIFFY))
  85. /* Divide first. */
  86. return (user / XT_LIMIT_SCALE) * HZ * CREDITS_PER_JIFFY;
  87. return (user * HZ * CREDITS_PER_JIFFY) / XT_LIMIT_SCALE;
  88. }
  89. static int
  90. ipt_limit_checkentry(const char *tablename,
  91. const void *inf,
  92. const struct xt_match *match,
  93. void *matchinfo,
  94. unsigned int hook_mask)
  95. {
  96. struct xt_rateinfo *r = matchinfo;
  97. /* Check for overflow. */
  98. if (r->burst == 0
  99. || user2credits(r->avg * r->burst) < user2credits(r->avg)) {
  100. printk("Overflow in xt_limit, try lower: %u/%u\n",
  101. r->avg, r->burst);
  102. return 0;
  103. }
  104. /* For SMP, we only want to use one set of counters. */
  105. r->master = r;
  106. if (r->cost == 0) {
  107. /* User avg in seconds * XT_LIMIT_SCALE: convert to jiffies *
  108. 128. */
  109. r->prev = jiffies;
  110. r->credit = user2credits(r->avg * r->burst); /* Credits full. */
  111. r->credit_cap = user2credits(r->avg * r->burst); /* Credits full. */
  112. r->cost = user2credits(r->avg);
  113. }
  114. return 1;
  115. }
  116. #ifdef CONFIG_COMPAT
  117. struct compat_xt_rateinfo {
  118. u_int32_t avg;
  119. u_int32_t burst;
  120. compat_ulong_t prev;
  121. u_int32_t credit;
  122. u_int32_t credit_cap, cost;
  123. u_int32_t master;
  124. };
  125. /* To keep the full "prev" timestamp, the upper 32 bits are stored in the
  126. * master pointer, which does not need to be preserved. */
  127. static void compat_from_user(void *dst, void *src)
  128. {
  129. struct compat_xt_rateinfo *cm = src;
  130. struct xt_rateinfo m = {
  131. .avg = cm->avg,
  132. .burst = cm->burst,
  133. .prev = cm->prev | (unsigned long)cm->master << 32,
  134. .credit = cm->credit,
  135. .credit_cap = cm->credit_cap,
  136. .cost = cm->cost,
  137. };
  138. memcpy(dst, &m, sizeof(m));
  139. }
  140. static int compat_to_user(void __user *dst, void *src)
  141. {
  142. struct xt_rateinfo *m = src;
  143. struct compat_xt_rateinfo cm = {
  144. .avg = m->avg,
  145. .burst = m->burst,
  146. .prev = m->prev,
  147. .credit = m->credit,
  148. .credit_cap = m->credit_cap,
  149. .cost = m->cost,
  150. .master = m->prev >> 32,
  151. };
  152. return copy_to_user(dst, &cm, sizeof(cm)) ? -EFAULT : 0;
  153. }
  154. #endif /* CONFIG_COMPAT */
  155. static struct xt_match xt_limit_match[] = {
  156. {
  157. .name = "limit",
  158. .family = AF_INET,
  159. .checkentry = ipt_limit_checkentry,
  160. .match = ipt_limit_match,
  161. .matchsize = sizeof(struct xt_rateinfo),
  162. #ifdef CONFIG_COMPAT
  163. .compatsize = sizeof(struct compat_xt_rateinfo),
  164. .compat_from_user = compat_from_user,
  165. .compat_to_user = compat_to_user,
  166. #endif
  167. .me = THIS_MODULE,
  168. },
  169. {
  170. .name = "limit",
  171. .family = AF_INET6,
  172. .checkentry = ipt_limit_checkentry,
  173. .match = ipt_limit_match,
  174. .matchsize = sizeof(struct xt_rateinfo),
  175. .me = THIS_MODULE,
  176. },
  177. };
  178. static int __init xt_limit_init(void)
  179. {
  180. return xt_register_matches(xt_limit_match, ARRAY_SIZE(xt_limit_match));
  181. }
  182. static void __exit xt_limit_fini(void)
  183. {
  184. xt_unregister_matches(xt_limit_match, ARRAY_SIZE(xt_limit_match));
  185. }
  186. module_init(xt_limit_init);
  187. module_exit(xt_limit_fini);