Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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> |
Arjan van de Ven | 4a3e2f7 | 2006-03-20 22:33:17 -0800 | [diff] [blame] | 23 | #include <linux/mutex.h> |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 24 | #include <net/flow.h> |
| 25 | #include <asm/atomic.h> |
| 26 | #include <asm/semaphore.h> |
Trent Jaeger | df71837 | 2005-12-13 23:12:27 -0800 | [diff] [blame] | 27 | #include <linux/security.h> |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | |
Eric Dumazet | ba89966 | 2005-08-26 12:05:31 -0700 | [diff] [blame] | 47 | static kmem_cache_t *flow_cachep __read_mostly; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | |
KAMEZAWA Hiroyuki | 6f91204 | 2006-04-10 22:52:50 -0700 | [diff] [blame] | 81 | for_each_possible_cpu(i) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | |
James Morris | 134b0fc | 2006-10-05 15:42:27 -0500 | [diff] [blame] | 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 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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; |
James Morris | 134b0fc | 2006-10-05 15:42:27 -0500 | [diff] [blame] | 111 | flow_entry_kill(cpu, fle); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | |
Venkat Yekkirala | e0d1caa | 2006-07-24 23:29:07 -0700 | [diff] [blame] | 172 | void *flow_cache_lookup(struct flowi *key, u16 family, u8 dir, |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | { |
James Morris | 134b0fc | 2006-10-05 15:42:27 -0500 | [diff] [blame] | 228 | int err; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 229 | void *obj; |
| 230 | atomic_t *obj_ref; |
| 231 | |
James Morris | 134b0fc | 2006-10-05 15:42:27 -0500 | [diff] [blame] | 232 | err = resolver(key, family, dir, &obj, &obj_ref); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 233 | |
| 234 | if (fle) { |
James Morris | 134b0fc | 2006-10-05 15:42:27 -0500 | [diff] [blame] | 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); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 241 | |
James Morris | 134b0fc | 2006-10-05 15:42:27 -0500 | [diff] [blame] | 242 | if (fle->object) |
| 243 | atomic_dec(fle->object_ref); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 244 | |
James Morris | 134b0fc | 2006-10-05 15:42:27 -0500 | [diff] [blame] | 245 | fle->object = obj; |
| 246 | fle->object_ref = obj_ref; |
| 247 | if (obj) |
| 248 | atomic_inc(fle->object_ref); |
| 249 | } |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 250 | } |
| 251 | local_bh_enable(); |
| 252 | |
James Morris | 134b0fc | 2006-10-05 15:42:27 -0500 | [diff] [blame] | 253 | if (err) |
| 254 | obj = ERR_PTR(err); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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; |
Arjan van de Ven | 4a3e2f7 | 2006-03-20 22:33:17 -0800 | [diff] [blame] | 302 | static DEFINE_MUTEX(flow_flush_sem); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 303 | |
| 304 | /* Don't want cpus going down or up during this. */ |
| 305 | lock_cpu_hotplug(); |
Arjan van de Ven | 4a3e2f7 | 2006-03-20 22:33:17 -0800 | [diff] [blame] | 306 | mutex_lock(&flow_flush_sem); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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); |
Arjan van de Ven | 4a3e2f7 | 2006-03-20 22:33:17 -0800 | [diff] [blame] | 316 | mutex_unlock(&flow_flush_sem); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 **) |
Andrew Morton | 77d04bd | 2006-04-07 14:52:59 -0700 | [diff] [blame] | 332 | __get_free_pages(GFP_KERNEL|__GFP_ZERO, order); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 333 | if (!flow_table(cpu)) |
| 334 | panic("NET: failed to allocate flow cache order %lu\n", order); |
| 335 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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), |
Alexey Dobriyan | e5d679f | 2006-08-26 19:25:52 -0700 | [diff] [blame] | 360 | 0, SLAB_HWCACHE_ALIGN|SLAB_PANIC, |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 361 | NULL, NULL); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | |
KAMEZAWA Hiroyuki | 6f91204 | 2006-04-10 22:52:50 -0700 | [diff] [blame] | 371 | for_each_possible_cpu(i) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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); |