1 /* flow.c: Generic flow cache.
3 * Copyright (C) 2003 Alexey N. Kuznetsov (kuznet@ms2.inr.ac.ru)
4 * Copyright (C) 2003 David S. Miller (davem@redhat.com)
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>
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 <linux/mutex.h>
25 #include <asm/atomic.h>
26 #include <linux/security.h>
28 struct flow_cache_entry
{
29 struct flow_cache_entry
*next
;
38 atomic_t flow_cache_genid
= ATOMIC_INIT(0);
40 static u32 flow_hash_shift
;
41 #define flow_hash_size (1 << flow_hash_shift)
43 static DEFINE_PER_CPU_LOCKED(struct flow_cache_entry
**, flow_tables
);
45 #define flow_table(cpu) (per_cpu_var_locked(flow_tables, cpu))
47 static struct kmem_cache
*flow_cachep __read_mostly
;
49 static int flow_lwm
, flow_hwm
;
51 struct flow_percpu_info
{
56 static DEFINE_PER_CPU(struct flow_percpu_info
, flow_hash_info
) = { 0 };
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)
65 static struct timer_list flow_hash_rnd_timer
;
67 #define FLOW_HASH_RND_PERIOD (10 * 60 * HZ)
69 struct flow_flush_info
{
71 struct completion completion
;
73 static DEFINE_PER_CPU(struct tasklet_struct
, flow_flush_tasklets
) = { NULL
};
75 #define flow_flush_tasklet(cpu) (&per_cpu(flow_flush_tasklets, cpu))
77 static void flow_cache_new_hashrnd(unsigned long arg
)
81 for_each_possible_cpu(i
)
82 flow_hash_rnd_recalc(i
) = 1;
84 flow_hash_rnd_timer
.expires
= jiffies
+ FLOW_HASH_RND_PERIOD
;
85 add_timer(&flow_hash_rnd_timer
);
88 static void flow_entry_kill(int cpu
, struct flow_cache_entry
*fle
)
91 atomic_dec(fle
->object_ref
);
92 kmem_cache_free(flow_cachep
, fle
);
96 static void __flow_cache_shrink(int cpu
, int shrink_to
)
98 struct flow_cache_entry
*fle
, **flp
;
101 for (i
= 0; i
< flow_hash_size
; i
++) {
104 flp
= &flow_table(cpu
)[i
];
105 while ((fle
= *flp
) != NULL
&& k
< shrink_to
) {
109 while ((fle
= *flp
) != NULL
) {
111 flow_entry_kill(cpu
, fle
);
116 static void flow_cache_shrink(int cpu
)
118 int shrink_to
= flow_lwm
/ flow_hash_size
;
120 __flow_cache_shrink(cpu
, shrink_to
);
123 static void flow_new_hash_rnd(int cpu
)
125 get_random_bytes(&flow_hash_rnd(cpu
), sizeof(u32
));
126 flow_hash_rnd_recalc(cpu
) = 0;
128 __flow_cache_shrink(cpu
, 0);
131 static u32
flow_hash_code(struct flowi
*key
, int cpu
)
133 u32
*k
= (u32
*) key
;
135 return (jhash2(k
, (sizeof(*key
) / sizeof(u32
)), flow_hash_rnd(cpu
)) &
136 (flow_hash_size
- 1));
139 #if (BITS_PER_LONG == 64)
140 typedef u64 flow_compare_t
;
142 typedef u32 flow_compare_t
;
145 /* I hear what you're saying, use memcmp. But memcmp cannot make
146 * important assumptions that we can here, such as alignment and
149 static int flow_key_compare(struct flowi
*key1
, struct flowi
*key2
)
151 flow_compare_t
*k1
, *k1_lim
, *k2
;
152 const int n_elem
= sizeof(struct flowi
) / sizeof(flow_compare_t
);
154 BUILD_BUG_ON(sizeof(struct flowi
) % sizeof(flow_compare_t
));
156 k1
= (flow_compare_t
*) key1
;
157 k1_lim
= k1
+ n_elem
;
159 k2
= (flow_compare_t
*) key2
;
164 } while (k1
< k1_lim
);
169 void *flow_cache_lookup(struct net
*net
, struct flowi
*key
, u16 family
, u8 dir
,
170 flow_resolve_t resolver
)
172 struct flow_cache_entry
**table
, *fle
, **head
= NULL
/* shut up GCC */;
177 table
= get_cpu_var_locked(flow_tables
, &cpu
);
180 /* Packet really early in init? Making flow_cache_init a
181 * pre-smp initcall would solve this. --RR */
185 if (flow_hash_rnd_recalc(cpu
))
186 flow_new_hash_rnd(cpu
);
187 hash
= flow_hash_code(key
, cpu
);
190 for (fle
= *head
; fle
; fle
= fle
->next
) {
191 if (fle
->family
== family
&&
193 flow_key_compare(key
, &fle
->key
) == 0) {
194 if (fle
->genid
== atomic_read(&flow_cache_genid
)) {
195 void *ret
= fle
->object
;
198 atomic_inc(fle
->object_ref
);
199 put_cpu_var_locked(flow_tables
, cpu
);
209 if (flow_count(cpu
) > flow_hwm
)
210 flow_cache_shrink(cpu
);
212 fle
= kmem_cache_alloc(flow_cachep
, GFP_ATOMIC
);
216 fle
->family
= family
;
218 memcpy(&fle
->key
, key
, sizeof(*key
));
225 put_cpu_var_locked(flow_tables
, cpu
);
232 err
= resolver(net
, key
, family
, dir
, &obj
, &obj_ref
);
235 fle
->genid
= atomic_read(&flow_cache_genid
);
238 atomic_dec(fle
->object_ref
);
241 fle
->object_ref
= obj_ref
;
243 atomic_inc(fle
->object_ref
);
253 static void flow_cache_flush_tasklet(unsigned long data
)
255 struct flow_flush_info
*info
= (void *)data
;
256 struct flow_cache_entry
**table
;
260 table
= get_cpu_var_locked(flow_tables
, &cpu
);
261 for (i
= 0; i
< flow_hash_size
; i
++) {
262 struct flow_cache_entry
*fle
;
265 for (; fle
; fle
= fle
->next
) {
266 unsigned genid
= atomic_read(&flow_cache_genid
);
268 if (!fle
->object
|| fle
->genid
== genid
)
272 atomic_dec(fle
->object_ref
);
275 put_cpu_var_locked(flow_tables
, cpu
);
277 if (atomic_dec_and_test(&info
->cpuleft
))
278 complete(&info
->completion
);
281 static void flow_cache_flush_per_cpu(void *) __attribute__((__unused__
));
282 static void flow_cache_flush_per_cpu(void *data
)
284 struct flow_flush_info
*info
= data
;
286 struct tasklet_struct
*tasklet
;
288 cpu
= smp_processor_id();
290 tasklet
= flow_flush_tasklet(cpu
);
291 tasklet
->data
= (unsigned long)info
;
292 tasklet_schedule(tasklet
);
295 void flow_cache_flush(void)
297 struct flow_flush_info info
;
298 static DEFINE_MUTEX(flow_flush_sem
);
300 /* Don't want cpus going down or up during this. */
302 mutex_lock(&flow_flush_sem
);
303 atomic_set(&info
.cpuleft
, num_online_cpus());
304 init_completion(&info
.completion
);
307 smp_call_function(flow_cache_flush_per_cpu
, &info
, 0);
308 flow_cache_flush_tasklet((unsigned long)&info
);
311 wait_for_completion(&info
.completion
);
312 mutex_unlock(&flow_flush_sem
);
316 static void __init
flow_cache_cpu_prepare(int cpu
)
318 struct tasklet_struct
*tasklet
;
322 (PAGE_SIZE
<< order
) <
323 (sizeof(struct flow_cache_entry
*)*flow_hash_size
);
327 flow_table(cpu
) = (struct flow_cache_entry
**)
328 __get_free_pages(GFP_KERNEL
|__GFP_ZERO
, order
);
329 if (!flow_table(cpu
))
330 panic("NET: failed to allocate flow cache order %lu\n", order
);
332 flow_hash_rnd_recalc(cpu
) = 1;
335 tasklet
= flow_flush_tasklet(cpu
);
336 tasklet_init(tasklet
, flow_cache_flush_tasklet
, 0);
339 static int flow_cache_cpu(struct notifier_block
*nfb
,
340 unsigned long action
,
343 if (action
== CPU_DEAD
|| action
== CPU_DEAD_FROZEN
)
344 __flow_cache_shrink((unsigned long)hcpu
, 0);
348 static int __init
flow_cache_init(void)
352 flow_cachep
= kmem_cache_create("flow_cache",
353 sizeof(struct flow_cache_entry
),
356 flow_hash_shift
= 10;
357 flow_lwm
= 2 * flow_hash_size
;
358 flow_hwm
= 4 * flow_hash_size
;
360 setup_timer(&flow_hash_rnd_timer
, flow_cache_new_hashrnd
, 0);
361 flow_hash_rnd_timer
.expires
= jiffies
+ FLOW_HASH_RND_PERIOD
;
362 add_timer(&flow_hash_rnd_timer
);
364 for_each_possible_cpu(i
)
365 flow_cache_cpu_prepare(i
);
367 hotcpu_notifier(flow_cache_cpu
, 0);
371 module_init(flow_cache_init
);
373 EXPORT_SYMBOL(flow_cache_genid
);
374 EXPORT_SYMBOL(flow_cache_lookup
);