flow.c 8.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373
  1. /* flow.c: Generic flow cache.
  2. *
  3. * Copyright (C) 2003 Alexey N. Kuznetsov (kuznet@ms2.inr.ac.ru)
  4. * Copyright (C) 2003 David S. Miller (davem@redhat.com)
  5. */
  6. #include <linux/kernel.h>
  7. #include <linux/module.h>
  8. #include <linux/list.h>
  9. #include <linux/jhash.h>
  10. #include <linux/interrupt.h>
  11. #include <linux/mm.h>
  12. #include <linux/random.h>
  13. #include <linux/init.h>
  14. #include <linux/slab.h>
  15. #include <linux/smp.h>
  16. #include <linux/completion.h>
  17. #include <linux/percpu.h>
  18. #include <linux/bitops.h>
  19. #include <linux/notifier.h>
  20. #include <linux/cpu.h>
  21. #include <linux/cpumask.h>
  22. #include <linux/mutex.h>
  23. #include <net/flow.h>
  24. #include <asm/atomic.h>
  25. #include <asm/semaphore.h>
  26. #include <linux/security.h>
  27. struct flow_cache_entry {
  28. struct flow_cache_entry *next;
  29. u16 family;
  30. u8 dir;
  31. struct flowi key;
  32. u32 genid;
  33. void *object;
  34. atomic_t *object_ref;
  35. };
  36. atomic_t flow_cache_genid = ATOMIC_INIT(0);
  37. static u32 flow_hash_shift;
  38. #define flow_hash_size (1 << flow_hash_shift)
  39. static DEFINE_PER_CPU(struct flow_cache_entry **, flow_tables) = { NULL };
  40. #define flow_table(cpu) (per_cpu(flow_tables, cpu))
  41. static struct kmem_cache *flow_cachep __read_mostly;
  42. static int flow_lwm, flow_hwm;
  43. struct flow_percpu_info {
  44. int hash_rnd_recalc;
  45. u32 hash_rnd;
  46. int count;
  47. } ____cacheline_aligned;
  48. static DEFINE_PER_CPU(struct flow_percpu_info, flow_hash_info) = { 0 };
  49. #define flow_hash_rnd_recalc(cpu) \
  50. (per_cpu(flow_hash_info, cpu).hash_rnd_recalc)
  51. #define flow_hash_rnd(cpu) \
  52. (per_cpu(flow_hash_info, cpu).hash_rnd)
  53. #define flow_count(cpu) \
  54. (per_cpu(flow_hash_info, cpu).count)
  55. static struct timer_list flow_hash_rnd_timer;
  56. #define FLOW_HASH_RND_PERIOD (10 * 60 * HZ)
  57. struct flow_flush_info {
  58. atomic_t cpuleft;
  59. struct completion completion;
  60. };
  61. static DEFINE_PER_CPU(struct tasklet_struct, flow_flush_tasklets) = { NULL };
  62. #define flow_flush_tasklet(cpu) (&per_cpu(flow_flush_tasklets, cpu))
  63. static void flow_cache_new_hashrnd(unsigned long arg)
  64. {
  65. int i;
  66. for_each_possible_cpu(i)
  67. flow_hash_rnd_recalc(i) = 1;
  68. flow_hash_rnd_timer.expires = jiffies + FLOW_HASH_RND_PERIOD;
  69. add_timer(&flow_hash_rnd_timer);
  70. }
  71. static void flow_entry_kill(int cpu, struct flow_cache_entry *fle)
  72. {
  73. if (fle->object)
  74. atomic_dec(fle->object_ref);
  75. kmem_cache_free(flow_cachep, fle);
  76. flow_count(cpu)--;
  77. }
  78. static void __flow_cache_shrink(int cpu, int shrink_to)
  79. {
  80. struct flow_cache_entry *fle, **flp;
  81. int i;
  82. for (i = 0; i < flow_hash_size; i++) {
  83. int k = 0;
  84. flp = &flow_table(cpu)[i];
  85. while ((fle = *flp) != NULL && k < shrink_to) {
  86. k++;
  87. flp = &fle->next;
  88. }
  89. while ((fle = *flp) != NULL) {
  90. *flp = fle->next;
  91. flow_entry_kill(cpu, fle);
  92. }
  93. }
  94. }
  95. static void flow_cache_shrink(int cpu)
  96. {
  97. int shrink_to = flow_lwm / flow_hash_size;
  98. __flow_cache_shrink(cpu, shrink_to);
  99. }
  100. static void flow_new_hash_rnd(int cpu)
  101. {
  102. get_random_bytes(&flow_hash_rnd(cpu), sizeof(u32));
  103. flow_hash_rnd_recalc(cpu) = 0;
  104. __flow_cache_shrink(cpu, 0);
  105. }
  106. static u32 flow_hash_code(struct flowi *key, int cpu)
  107. {
  108. u32 *k = (u32 *) key;
  109. return (jhash2(k, (sizeof(*key) / sizeof(u32)), flow_hash_rnd(cpu)) &
  110. (flow_hash_size - 1));
  111. }
  112. #if (BITS_PER_LONG == 64)
  113. typedef u64 flow_compare_t;
  114. #else
  115. typedef u32 flow_compare_t;
  116. #endif
  117. extern void flowi_is_missized(void);
  118. /* I hear what you're saying, use memcmp. But memcmp cannot make
  119. * important assumptions that we can here, such as alignment and
  120. * constant size.
  121. */
  122. static int flow_key_compare(struct flowi *key1, struct flowi *key2)
  123. {
  124. flow_compare_t *k1, *k1_lim, *k2;
  125. const int n_elem = sizeof(struct flowi) / sizeof(flow_compare_t);
  126. if (sizeof(struct flowi) % sizeof(flow_compare_t))
  127. flowi_is_missized();
  128. k1 = (flow_compare_t *) key1;
  129. k1_lim = k1 + n_elem;
  130. k2 = (flow_compare_t *) key2;
  131. do {
  132. if (*k1++ != *k2++)
  133. return 1;
  134. } while (k1 < k1_lim);
  135. return 0;
  136. }
  137. void *flow_cache_lookup(struct flowi *key, u16 family, u8 dir,
  138. flow_resolve_t resolver)
  139. {
  140. struct flow_cache_entry *fle, **head;
  141. unsigned int hash;
  142. int cpu;
  143. local_bh_disable();
  144. cpu = smp_processor_id();
  145. fle = NULL;
  146. /* Packet really early in init? Making flow_cache_init a
  147. * pre-smp initcall would solve this. --RR */
  148. if (!flow_table(cpu))
  149. goto nocache;
  150. if (flow_hash_rnd_recalc(cpu))
  151. flow_new_hash_rnd(cpu);
  152. hash = flow_hash_code(key, cpu);
  153. head = &flow_table(cpu)[hash];
  154. for (fle = *head; fle; fle = fle->next) {
  155. if (fle->family == family &&
  156. fle->dir == dir &&
  157. flow_key_compare(key, &fle->key) == 0) {
  158. if (fle->genid == atomic_read(&flow_cache_genid)) {
  159. void *ret = fle->object;
  160. if (ret)
  161. atomic_inc(fle->object_ref);
  162. local_bh_enable();
  163. return ret;
  164. }
  165. break;
  166. }
  167. }
  168. if (!fle) {
  169. if (flow_count(cpu) > flow_hwm)
  170. flow_cache_shrink(cpu);
  171. fle = kmem_cache_alloc(flow_cachep, GFP_ATOMIC);
  172. if (fle) {
  173. fle->next = *head;
  174. *head = fle;
  175. fle->family = family;
  176. fle->dir = dir;
  177. memcpy(&fle->key, key, sizeof(*key));
  178. fle->object = NULL;
  179. flow_count(cpu)++;
  180. }
  181. }
  182. nocache:
  183. {
  184. int err;
  185. void *obj;
  186. atomic_t *obj_ref;
  187. err = resolver(key, family, dir, &obj, &obj_ref);
  188. if (fle && !err) {
  189. fle->genid = atomic_read(&flow_cache_genid);
  190. if (fle->object)
  191. atomic_dec(fle->object_ref);
  192. fle->object = obj;
  193. fle->object_ref = obj_ref;
  194. if (obj)
  195. atomic_inc(fle->object_ref);
  196. }
  197. local_bh_enable();
  198. if (err)
  199. obj = ERR_PTR(err);
  200. return obj;
  201. }
  202. }
  203. static void flow_cache_flush_tasklet(unsigned long data)
  204. {
  205. struct flow_flush_info *info = (void *)data;
  206. int i;
  207. int cpu;
  208. cpu = smp_processor_id();
  209. for (i = 0; i < flow_hash_size; i++) {
  210. struct flow_cache_entry *fle;
  211. fle = flow_table(cpu)[i];
  212. for (; fle; fle = fle->next) {
  213. unsigned genid = atomic_read(&flow_cache_genid);
  214. if (!fle->object || fle->genid == genid)
  215. continue;
  216. fle->object = NULL;
  217. atomic_dec(fle->object_ref);
  218. }
  219. }
  220. if (atomic_dec_and_test(&info->cpuleft))
  221. complete(&info->completion);
  222. }
  223. static void flow_cache_flush_per_cpu(void *) __attribute__((__unused__));
  224. static void flow_cache_flush_per_cpu(void *data)
  225. {
  226. struct flow_flush_info *info = data;
  227. int cpu;
  228. struct tasklet_struct *tasklet;
  229. cpu = smp_processor_id();
  230. tasklet = flow_flush_tasklet(cpu);
  231. tasklet->data = (unsigned long)info;
  232. tasklet_schedule(tasklet);
  233. }
  234. void flow_cache_flush(void)
  235. {
  236. struct flow_flush_info info;
  237. static DEFINE_MUTEX(flow_flush_sem);
  238. /* Don't want cpus going down or up during this. */
  239. lock_cpu_hotplug();
  240. mutex_lock(&flow_flush_sem);
  241. atomic_set(&info.cpuleft, num_online_cpus());
  242. init_completion(&info.completion);
  243. local_bh_disable();
  244. smp_call_function(flow_cache_flush_per_cpu, &info, 1, 0);
  245. flow_cache_flush_tasklet((unsigned long)&info);
  246. local_bh_enable();
  247. wait_for_completion(&info.completion);
  248. mutex_unlock(&flow_flush_sem);
  249. unlock_cpu_hotplug();
  250. }
  251. static void __devinit flow_cache_cpu_prepare(int cpu)
  252. {
  253. struct tasklet_struct *tasklet;
  254. unsigned long order;
  255. for (order = 0;
  256. (PAGE_SIZE << order) <
  257. (sizeof(struct flow_cache_entry *)*flow_hash_size);
  258. order++)
  259. /* NOTHING */;
  260. flow_table(cpu) = (struct flow_cache_entry **)
  261. __get_free_pages(GFP_KERNEL|__GFP_ZERO, order);
  262. if (!flow_table(cpu))
  263. panic("NET: failed to allocate flow cache order %lu\n", order);
  264. flow_hash_rnd_recalc(cpu) = 1;
  265. flow_count(cpu) = 0;
  266. tasklet = flow_flush_tasklet(cpu);
  267. tasklet_init(tasklet, flow_cache_flush_tasklet, 0);
  268. }
  269. static int flow_cache_cpu(struct notifier_block *nfb,
  270. unsigned long action,
  271. void *hcpu)
  272. {
  273. if (action == CPU_DEAD)
  274. __flow_cache_shrink((unsigned long)hcpu, 0);
  275. return NOTIFY_OK;
  276. }
  277. static int __init flow_cache_init(void)
  278. {
  279. int i;
  280. flow_cachep = kmem_cache_create("flow_cache",
  281. sizeof(struct flow_cache_entry),
  282. 0, SLAB_HWCACHE_ALIGN|SLAB_PANIC,
  283. NULL, NULL);
  284. flow_hash_shift = 10;
  285. flow_lwm = 2 * flow_hash_size;
  286. flow_hwm = 4 * flow_hash_size;
  287. init_timer(&flow_hash_rnd_timer);
  288. flow_hash_rnd_timer.function = flow_cache_new_hashrnd;
  289. flow_hash_rnd_timer.expires = jiffies + FLOW_HASH_RND_PERIOD;
  290. add_timer(&flow_hash_rnd_timer);
  291. for_each_possible_cpu(i)
  292. flow_cache_cpu_prepare(i);
  293. hotcpu_notifier(flow_cache_cpu, 0);
  294. return 0;
  295. }
  296. module_init(flow_cache_init);
  297. EXPORT_SYMBOL(flow_cache_genid);
  298. EXPORT_SYMBOL(flow_cache_lookup);