blob: f289570b15a3b3e3ba442d14ca6e133a8dff575e [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/* 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
7#include <linux/kernel.h>
8#include <linux/module.h>
9#include <linux/list.h>
10#include <linux/jhash.h>
11#include <linux/interrupt.h>
12#include <linux/mm.h>
13#include <linux/random.h>
14#include <linux/init.h>
15#include <linux/slab.h>
16#include <linux/smp.h>
17#include <linux/completion.h>
18#include <linux/percpu.h>
19#include <linux/bitops.h>
20#include <linux/notifier.h>
21#include <linux/cpu.h>
22#include <linux/cpumask.h>
23#include <net/flow.h>
24#include <asm/atomic.h>
25#include <asm/semaphore.h>
26
27struct 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
37atomic_t flow_cache_genid = ATOMIC_INIT(0);
38
39static u32 flow_hash_shift;
40#define flow_hash_size (1 << flow_hash_shift)
41static DEFINE_PER_CPU(struct flow_cache_entry **, flow_tables) = { NULL };
42
43#define flow_table(cpu) (per_cpu(flow_tables, cpu))
44
45static kmem_cache_t *flow_cachep;
46
47static int flow_lwm, flow_hwm;
48
49struct flow_percpu_info {
50 int hash_rnd_recalc;
51 u32 hash_rnd;
52 int count;
53} ____cacheline_aligned;
54static DEFINE_PER_CPU(struct flow_percpu_info, flow_hash_info) = { 0 };
55
56#define flow_hash_rnd_recalc(cpu) \
57 (per_cpu(flow_hash_info, cpu).hash_rnd_recalc)
58#define flow_hash_rnd(cpu) \
59 (per_cpu(flow_hash_info, cpu).hash_rnd)
60#define flow_count(cpu) \
61 (per_cpu(flow_hash_info, cpu).count)
62
63static struct timer_list flow_hash_rnd_timer;
64
65#define FLOW_HASH_RND_PERIOD (10 * 60 * HZ)
66
67struct flow_flush_info {
68 atomic_t cpuleft;
69 struct completion completion;
70};
71static DEFINE_PER_CPU(struct tasklet_struct, flow_flush_tasklets) = { NULL };
72
73#define flow_flush_tasklet(cpu) (&per_cpu(flow_flush_tasklets, cpu))
74
75static void flow_cache_new_hashrnd(unsigned long arg)
76{
77 int i;
78
79 for_each_cpu(i)
80 flow_hash_rnd_recalc(i) = 1;
81
82 flow_hash_rnd_timer.expires = jiffies + FLOW_HASH_RND_PERIOD;
83 add_timer(&flow_hash_rnd_timer);
84}
85
86static void __flow_cache_shrink(int cpu, int shrink_to)
87{
88 struct flow_cache_entry *fle, **flp;
89 int i;
90
91 for (i = 0; i < flow_hash_size; i++) {
92 int k = 0;
93
94 flp = &flow_table(cpu)[i];
95 while ((fle = *flp) != NULL && k < shrink_to) {
96 k++;
97 flp = &fle->next;
98 }
99 while ((fle = *flp) != NULL) {
100 *flp = fle->next;
101 if (fle->object)
102 atomic_dec(fle->object_ref);
103 kmem_cache_free(flow_cachep, fle);
104 flow_count(cpu)--;
105 }
106 }
107}
108
109static void flow_cache_shrink(int cpu)
110{
111 int shrink_to = flow_lwm / flow_hash_size;
112
113 __flow_cache_shrink(cpu, shrink_to);
114}
115
116static void flow_new_hash_rnd(int cpu)
117{
118 get_random_bytes(&flow_hash_rnd(cpu), sizeof(u32));
119 flow_hash_rnd_recalc(cpu) = 0;
120
121 __flow_cache_shrink(cpu, 0);
122}
123
124static u32 flow_hash_code(struct flowi *key, int cpu)
125{
126 u32 *k = (u32 *) key;
127
128 return (jhash2(k, (sizeof(*key) / sizeof(u32)), flow_hash_rnd(cpu)) &
129 (flow_hash_size - 1));
130}
131
132#if (BITS_PER_LONG == 64)
133typedef u64 flow_compare_t;
134#else
135typedef u32 flow_compare_t;
136#endif
137
138extern void flowi_is_missized(void);
139
140/* I hear what you're saying, use memcmp. But memcmp cannot make
141 * important assumptions that we can here, such as alignment and
142 * constant size.
143 */
144static int flow_key_compare(struct flowi *key1, struct flowi *key2)
145{
146 flow_compare_t *k1, *k1_lim, *k2;
147 const int n_elem = sizeof(struct flowi) / sizeof(flow_compare_t);
148
149 if (sizeof(struct flowi) % sizeof(flow_compare_t))
150 flowi_is_missized();
151
152 k1 = (flow_compare_t *) key1;
153 k1_lim = k1 + n_elem;
154
155 k2 = (flow_compare_t *) key2;
156
157 do {
158 if (*k1++ != *k2++)
159 return 1;
160 } while (k1 < k1_lim);
161
162 return 0;
163}
164
165void *flow_cache_lookup(struct flowi *key, u16 family, u8 dir,
166 flow_resolve_t resolver)
167{
168 struct flow_cache_entry *fle, **head;
169 unsigned int hash;
170 int cpu;
171
172 local_bh_disable();
173 cpu = smp_processor_id();
174
175 fle = NULL;
176 /* Packet really early in init? Making flow_cache_init a
177 * pre-smp initcall would solve this. --RR */
178 if (!flow_table(cpu))
179 goto nocache;
180
181 if (flow_hash_rnd_recalc(cpu))
182 flow_new_hash_rnd(cpu);
183 hash = flow_hash_code(key, cpu);
184
185 head = &flow_table(cpu)[hash];
186 for (fle = *head; fle; fle = fle->next) {
187 if (fle->family == family &&
188 fle->dir == dir &&
189 flow_key_compare(key, &fle->key) == 0) {
190 if (fle->genid == atomic_read(&flow_cache_genid)) {
191 void *ret = fle->object;
192
193 if (ret)
194 atomic_inc(fle->object_ref);
195 local_bh_enable();
196
197 return ret;
198 }
199 break;
200 }
201 }
202
203 if (!fle) {
204 if (flow_count(cpu) > flow_hwm)
205 flow_cache_shrink(cpu);
206
207 fle = kmem_cache_alloc(flow_cachep, SLAB_ATOMIC);
208 if (fle) {
209 fle->next = *head;
210 *head = fle;
211 fle->family = family;
212 fle->dir = dir;
213 memcpy(&fle->key, key, sizeof(*key));
214 fle->object = NULL;
215 flow_count(cpu)++;
216 }
217 }
218
219nocache:
220 {
221 void *obj;
222 atomic_t *obj_ref;
223
224 resolver(key, family, dir, &obj, &obj_ref);
225
226 if (fle) {
227 fle->genid = atomic_read(&flow_cache_genid);
228
229 if (fle->object)
230 atomic_dec(fle->object_ref);
231
232 fle->object = obj;
233 fle->object_ref = obj_ref;
234 if (obj)
235 atomic_inc(fle->object_ref);
236 }
237 local_bh_enable();
238
239 return obj;
240 }
241}
242
243static void flow_cache_flush_tasklet(unsigned long data)
244{
245 struct flow_flush_info *info = (void *)data;
246 int i;
247 int cpu;
248
249 cpu = smp_processor_id();
250 for (i = 0; i < flow_hash_size; i++) {
251 struct flow_cache_entry *fle;
252
253 fle = flow_table(cpu)[i];
254 for (; fle; fle = fle->next) {
255 unsigned genid = atomic_read(&flow_cache_genid);
256
257 if (!fle->object || fle->genid == genid)
258 continue;
259
260 fle->object = NULL;
261 atomic_dec(fle->object_ref);
262 }
263 }
264
265 if (atomic_dec_and_test(&info->cpuleft))
266 complete(&info->completion);
267}
268
269static void flow_cache_flush_per_cpu(void *) __attribute__((__unused__));
270static void flow_cache_flush_per_cpu(void *data)
271{
272 struct flow_flush_info *info = data;
273 int cpu;
274 struct tasklet_struct *tasklet;
275
276 cpu = smp_processor_id();
277
278 tasklet = flow_flush_tasklet(cpu);
279 tasklet->data = (unsigned long)info;
280 tasklet_schedule(tasklet);
281}
282
283void flow_cache_flush(void)
284{
285 struct flow_flush_info info;
286 static DECLARE_MUTEX(flow_flush_sem);
287
288 /* Don't want cpus going down or up during this. */
289 lock_cpu_hotplug();
290 down(&flow_flush_sem);
291 atomic_set(&info.cpuleft, num_online_cpus());
292 init_completion(&info.completion);
293
294 local_bh_disable();
295 smp_call_function(flow_cache_flush_per_cpu, &info, 1, 0);
296 flow_cache_flush_tasklet((unsigned long)&info);
297 local_bh_enable();
298
299 wait_for_completion(&info.completion);
300 up(&flow_flush_sem);
301 unlock_cpu_hotplug();
302}
303
304static void __devinit flow_cache_cpu_prepare(int cpu)
305{
306 struct tasklet_struct *tasklet;
307 unsigned long order;
308
309 for (order = 0;
310 (PAGE_SIZE << order) <
311 (sizeof(struct flow_cache_entry *)*flow_hash_size);
312 order++)
313 /* NOTHING */;
314
315 flow_table(cpu) = (struct flow_cache_entry **)
316 __get_free_pages(GFP_KERNEL, order);
317 if (!flow_table(cpu))
318 panic("NET: failed to allocate flow cache order %lu\n", order);
319
320 memset(flow_table(cpu), 0, PAGE_SIZE << order);
321
322 flow_hash_rnd_recalc(cpu) = 1;
323 flow_count(cpu) = 0;
324
325 tasklet = flow_flush_tasklet(cpu);
326 tasklet_init(tasklet, flow_cache_flush_tasklet, 0);
327}
328
329#ifdef CONFIG_HOTPLUG_CPU
330static int flow_cache_cpu(struct notifier_block *nfb,
331 unsigned long action,
332 void *hcpu)
333{
334 if (action == CPU_DEAD)
335 __flow_cache_shrink((unsigned long)hcpu, 0);
336 return NOTIFY_OK;
337}
338#endif /* CONFIG_HOTPLUG_CPU */
339
340static int __init flow_cache_init(void)
341{
342 int i;
343
344 flow_cachep = kmem_cache_create("flow_cache",
345 sizeof(struct flow_cache_entry),
346 0, SLAB_HWCACHE_ALIGN,
347 NULL, NULL);
348
349 if (!flow_cachep)
350 panic("NET: failed to allocate flow cache slab\n");
351
352 flow_hash_shift = 10;
353 flow_lwm = 2 * flow_hash_size;
354 flow_hwm = 4 * flow_hash_size;
355
356 init_timer(&flow_hash_rnd_timer);
357 flow_hash_rnd_timer.function = flow_cache_new_hashrnd;
358 flow_hash_rnd_timer.expires = jiffies + FLOW_HASH_RND_PERIOD;
359 add_timer(&flow_hash_rnd_timer);
360
361 for_each_cpu(i)
362 flow_cache_cpu_prepare(i);
363
364 hotcpu_notifier(flow_cache_cpu, 0);
365 return 0;
366}
367
368module_init(flow_cache_init);
369
370EXPORT_SYMBOL(flow_cache_genid);
371EXPORT_SYMBOL(flow_cache_lookup);