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