flow.c revision fe1a5f031e76bd8761a7803d75b95ee96e84a574
11da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds/* flow.c: Generic flow cache. 21da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * 31da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * Copyright (C) 2003 Alexey N. Kuznetsov (kuznet@ms2.inr.ac.ru) 41da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * Copyright (C) 2003 David S. Miller (davem@redhat.com) 51da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds */ 61da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 71da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/kernel.h> 81da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/module.h> 91da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/list.h> 101da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/jhash.h> 111da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/interrupt.h> 121da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/mm.h> 131da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/random.h> 141da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/init.h> 151da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/slab.h> 161da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/smp.h> 171da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/completion.h> 181da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/percpu.h> 191da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/bitops.h> 201da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/notifier.h> 211da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/cpu.h> 221da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/cpumask.h> 234a3e2f711a00a1feb72ae12fdc749da10179d185Arjan van de Ven#include <linux/mutex.h> 241da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <net/flow.h> 251da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <asm/atomic.h> 26df71837d5024e2524cd51c93621e558aa7dd9f3fTrent Jaeger#include <linux/security.h> 271da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 281da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsstruct flow_cache_entry { 29fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs struct flow_cache_entry *next; 30fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs u16 family; 31fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs u8 dir; 32fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs u32 genid; 33fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs struct flowi key; 34fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs struct flow_cache_object *object; 351da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds}; 361da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 37d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Terässtruct flow_cache_percpu { 38fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs struct flow_cache_entry **hash_table; 39d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs int hash_count; 40d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs u32 hash_rnd; 41d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs int hash_rnd_recalc; 42d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs struct tasklet_struct flush_tasklet; 435f58a5c8725b48f3e32851f9748527c8d1ff71b2Eric Dumazet}; 441da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 451da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsstruct flow_flush_info { 46fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs struct flow_cache *cache; 47d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs atomic_t cpuleft; 48d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs struct completion completion; 491da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds}; 501da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 51d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Terässtruct flow_cache { 52d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs u32 hash_shift; 53d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs unsigned long order; 54fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs struct flow_cache_percpu *percpu; 55d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs struct notifier_block hotcpu_notifier; 56d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs int low_watermark; 57d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs int high_watermark; 58d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs struct timer_list rnd_timer; 59d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs}; 60d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs 61d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräsatomic_t flow_cache_genid = ATOMIC_INIT(0); 62d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Terässtatic struct flow_cache flow_cache_global; 63d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Terässtatic struct kmem_cache *flow_cachep; 64d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs 65d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs#define flow_cache_hash_size(cache) (1 << (cache)->hash_shift) 66d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs#define FLOW_HASH_RND_PERIOD (10 * 60 * HZ) 671da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 681da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsstatic void flow_cache_new_hashrnd(unsigned long arg) 691da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 70d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs struct flow_cache *fc = (void *) arg; 711da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds int i; 721da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 736f912042256c12b0927438122594f5379b364f5dKAMEZAWA Hiroyuki for_each_possible_cpu(i) 74d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs per_cpu_ptr(fc->percpu, i)->hash_rnd_recalc = 1; 751da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 76d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs fc->rnd_timer.expires = jiffies + FLOW_HASH_RND_PERIOD; 77d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs add_timer(&fc->rnd_timer); 781da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 791da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 80fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Terässtatic int flow_entry_valid(struct flow_cache_entry *fle) 81fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs{ 82fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs if (atomic_read(&flow_cache_genid) != fle->genid) 83fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs return 0; 84fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs if (fle->object && !fle->object->ops->check(fle->object)) 85fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs return 0; 86fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs return 1; 87fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs} 88fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs 89d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Terässtatic void flow_entry_kill(struct flow_cache *fc, 90d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs struct flow_cache_percpu *fcp, 91d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs struct flow_cache_entry *fle) 92134b0fc544ba062498451611cb6f3e4454221b3dJames Morris{ 93134b0fc544ba062498451611cb6f3e4454221b3dJames Morris if (fle->object) 94fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs fle->object->ops->delete(fle->object); 95134b0fc544ba062498451611cb6f3e4454221b3dJames Morris kmem_cache_free(flow_cachep, fle); 96d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs fcp->hash_count--; 97134b0fc544ba062498451611cb6f3e4454221b3dJames Morris} 98134b0fc544ba062498451611cb6f3e4454221b3dJames Morris 99d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Terässtatic void __flow_cache_shrink(struct flow_cache *fc, 100d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs struct flow_cache_percpu *fcp, 101d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs int shrink_to) 1021da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 1031da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds struct flow_cache_entry *fle, **flp; 1041da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds int i; 1051da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 106d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs for (i = 0; i < flow_cache_hash_size(fc); i++) { 107fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs int saved = 0; 1081da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 109d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs flp = &fcp->hash_table[i]; 1101da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds while ((fle = *flp) != NULL) { 111fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs if (saved < shrink_to && 112fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs flow_entry_valid(fle)) { 113fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs saved++; 114fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs flp = &fle->next; 115fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs } else { 116fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs *flp = fle->next; 117fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs flow_entry_kill(fc, fcp, fle); 118fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs } 1191da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds } 1201da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds } 1211da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 1221da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 123d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Terässtatic void flow_cache_shrink(struct flow_cache *fc, 124d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs struct flow_cache_percpu *fcp) 1251da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 126d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs int shrink_to = fc->low_watermark / flow_cache_hash_size(fc); 1271da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 128d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs __flow_cache_shrink(fc, fcp, shrink_to); 1291da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 1301da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 131d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Terässtatic void flow_new_hash_rnd(struct flow_cache *fc, 132d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs struct flow_cache_percpu *fcp) 1331da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 134d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs get_random_bytes(&fcp->hash_rnd, sizeof(u32)); 135d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs fcp->hash_rnd_recalc = 0; 136d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs __flow_cache_shrink(fc, fcp, 0); 1371da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 1381da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 139d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Terässtatic u32 flow_hash_code(struct flow_cache *fc, 140d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs struct flow_cache_percpu *fcp, 141d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs struct flowi *key) 1421da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 1431da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds u32 *k = (u32 *) key; 1441da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 145d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs return (jhash2(k, (sizeof(*key) / sizeof(u32)), fcp->hash_rnd) 146d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs & (flow_cache_hash_size(fc) - 1)); 1471da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 1481da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 1491da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#if (BITS_PER_LONG == 64) 1501da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldstypedef u64 flow_compare_t; 1511da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#else 1521da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldstypedef u32 flow_compare_t; 1531da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#endif 1541da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 1551da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds/* I hear what you're saying, use memcmp. But memcmp cannot make 1561da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * important assumptions that we can here, such as alignment and 1571da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * constant size. 1581da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds */ 1591da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsstatic int flow_key_compare(struct flowi *key1, struct flowi *key2) 1601da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 1611da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds flow_compare_t *k1, *k1_lim, *k2; 1621da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds const int n_elem = sizeof(struct flowi) / sizeof(flow_compare_t); 1631da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 164f0fe91ded36bab95541e960ae8a115abc1f5ba03Pavel Emelyanov BUILD_BUG_ON(sizeof(struct flowi) % sizeof(flow_compare_t)); 1651da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 1661da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds k1 = (flow_compare_t *) key1; 1671da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds k1_lim = k1 + n_elem; 1681da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 1691da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds k2 = (flow_compare_t *) key2; 1701da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 1711da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds do { 1721da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds if (*k1++ != *k2++) 1731da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds return 1; 1741da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds } while (k1 < k1_lim); 1751da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 1761da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds return 0; 1771da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 1781da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 179fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Terässtruct flow_cache_object * 180fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräsflow_cache_lookup(struct net *net, struct flowi *key, u16 family, u8 dir, 181fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs flow_resolve_t resolver, void *ctx) 1821da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 183d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs struct flow_cache *fc = &flow_cache_global; 184d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs struct flow_cache_percpu *fcp; 1851da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds struct flow_cache_entry *fle, **head; 186fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs struct flow_cache_object *flo; 1871da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds unsigned int hash; 1881da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 1891da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds local_bh_disable(); 190d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs fcp = per_cpu_ptr(fc->percpu, smp_processor_id()); 1911da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 1921da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds fle = NULL; 193fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs flo = NULL; 1941da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds /* Packet really early in init? Making flow_cache_init a 1951da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * pre-smp initcall would solve this. --RR */ 196d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs if (!fcp->hash_table) 1971da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds goto nocache; 1981da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 199d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs if (fcp->hash_rnd_recalc) 200d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs flow_new_hash_rnd(fc, fcp); 2011da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 202fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs hash = flow_hash_code(fc, fcp, key); 203d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs head = &fcp->hash_table[hash]; 2041da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds for (fle = *head; fle; fle = fle->next) { 2051da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds if (fle->family == family && 2061da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds fle->dir == dir && 207fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs flow_key_compare(key, &fle->key) == 0) 2081da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds break; 2091da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds } 2101da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 211fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs if (unlikely(!fle)) { 212d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs if (fcp->hash_count > fc->high_watermark) 213d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs flow_cache_shrink(fc, fcp); 2141da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 21554e6ecb23951b195d02433a741c7f7cb0b796c78Christoph Lameter fle = kmem_cache_alloc(flow_cachep, GFP_ATOMIC); 2161da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds if (fle) { 2171da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds fle->next = *head; 2181da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds *head = fle; 2191da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds fle->family = family; 2201da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds fle->dir = dir; 2211da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds memcpy(&fle->key, key, sizeof(*key)); 2221da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds fle->object = NULL; 223d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs fcp->hash_count++; 2241da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds } 225fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs } else if (likely(fle->genid == atomic_read(&flow_cache_genid))) { 226fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs flo = fle->object; 227fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs if (!flo) 228fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs goto ret_object; 229fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs flo = flo->ops->get(flo); 230fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs if (flo) 231fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs goto ret_object; 232fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs } else if (fle->object) { 233fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs flo = fle->object; 234fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs flo->ops->delete(flo); 235fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs fle->object = NULL; 2361da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds } 2371da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2381da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsnocache: 239fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs flo = NULL; 240fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs if (fle) { 241fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs flo = fle->object; 242fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs fle->object = NULL; 243fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs } 244fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs flo = resolver(net, key, family, dir, flo, ctx); 245fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs if (fle) { 246fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs fle->genid = atomic_read(&flow_cache_genid); 247fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs if (!IS_ERR(flo)) 248fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs fle->object = flo; 249fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs else 250fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs fle->genid--; 251fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs } else { 252fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs if (flo && !IS_ERR(flo)) 253fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs flo->ops->delete(flo); 2541da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds } 255fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräsret_object: 256fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs local_bh_enable(); 257fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs return flo; 2581da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 2591da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2601da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsstatic void flow_cache_flush_tasklet(unsigned long data) 2611da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 2621da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds struct flow_flush_info *info = (void *)data; 263d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs struct flow_cache *fc = info->cache; 264d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs struct flow_cache_percpu *fcp; 2651da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds int i; 2661da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 267d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs fcp = per_cpu_ptr(fc->percpu, smp_processor_id()); 268d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs for (i = 0; i < flow_cache_hash_size(fc); i++) { 2691da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds struct flow_cache_entry *fle; 2701da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 271d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs fle = fcp->hash_table[i]; 2721da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds for (; fle; fle = fle->next) { 273fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs if (flow_entry_valid(fle)) 2741da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds continue; 2751da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 276fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs if (fle->object) 277fe1a5f031e76bd8761a7803d75b95ee96e84a574Timo Teräs fle->object->ops->delete(fle->object); 2781da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds fle->object = NULL; 2791da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds } 2801da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds } 2811da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2821da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds if (atomic_dec_and_test(&info->cpuleft)) 2831da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds complete(&info->completion); 2841da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 2851da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2861da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsstatic void flow_cache_flush_per_cpu(void *data) 2871da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 2881da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds struct flow_flush_info *info = data; 2891da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds int cpu; 2901da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds struct tasklet_struct *tasklet; 2911da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2921da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds cpu = smp_processor_id(); 293d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs tasklet = &per_cpu_ptr(info->cache->percpu, cpu)->flush_tasklet; 2941da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds tasklet->data = (unsigned long)info; 2951da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds tasklet_schedule(tasklet); 2961da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 2971da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2981da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsvoid flow_cache_flush(void) 2991da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 3001da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds struct flow_flush_info info; 3014a3e2f711a00a1feb72ae12fdc749da10179d185Arjan van de Ven static DEFINE_MUTEX(flow_flush_sem); 3021da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 3031da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds /* Don't want cpus going down or up during this. */ 30486ef5c9a8edd78e6bf92879f32329d89b2d55b5aGautham R Shenoy get_online_cpus(); 3054a3e2f711a00a1feb72ae12fdc749da10179d185Arjan van de Ven mutex_lock(&flow_flush_sem); 306d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs info.cache = &flow_cache_global; 3071da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds atomic_set(&info.cpuleft, num_online_cpus()); 3081da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds init_completion(&info.completion); 3091da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 3101da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds local_bh_disable(); 3118691e5a8f691cc2a4fda0651e8d307aaba0e7d68Jens Axboe smp_call_function(flow_cache_flush_per_cpu, &info, 0); 3121da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds flow_cache_flush_tasklet((unsigned long)&info); 3131da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds local_bh_enable(); 3141da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 3151da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds wait_for_completion(&info.completion); 3164a3e2f711a00a1feb72ae12fdc749da10179d185Arjan van de Ven mutex_unlock(&flow_flush_sem); 31786ef5c9a8edd78e6bf92879f32329d89b2d55b5aGautham R Shenoy put_online_cpus(); 3181da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 3191da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 320d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Terässtatic void __init flow_cache_cpu_prepare(struct flow_cache *fc, 321d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs struct flow_cache_percpu *fcp) 3221da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 323d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs fcp->hash_table = (struct flow_cache_entry **) 324d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs __get_free_pages(GFP_KERNEL|__GFP_ZERO, fc->order); 325d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs if (!fcp->hash_table) 326d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs panic("NET: failed to allocate flow cache order %lu\n", fc->order); 327d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs 328d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs fcp->hash_rnd_recalc = 1; 329d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs fcp->hash_count = 0; 330d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs tasklet_init(&fcp->flush_tasklet, flow_cache_flush_tasklet, 0); 3311da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 3321da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 3331da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsstatic int flow_cache_cpu(struct notifier_block *nfb, 3341da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds unsigned long action, 3351da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds void *hcpu) 3361da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 337d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs struct flow_cache *fc = container_of(nfb, struct flow_cache, hotcpu_notifier); 338d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs int cpu = (unsigned long) hcpu; 339d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs struct flow_cache_percpu *fcp = per_cpu_ptr(fc->percpu, cpu); 340d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs 3418bb7844286fb8c9fce6f65d8288aeb09d03a5e0dRafael J. Wysocki if (action == CPU_DEAD || action == CPU_DEAD_FROZEN) 342d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs __flow_cache_shrink(fc, fcp, 0); 3431da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds return NOTIFY_OK; 3441da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 3451da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 346d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Terässtatic int flow_cache_init(struct flow_cache *fc) 3471da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 348d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs unsigned long order; 3491da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds int i; 3501da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 351d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs fc->hash_shift = 10; 352d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs fc->low_watermark = 2 * flow_cache_hash_size(fc); 353d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs fc->high_watermark = 4 * flow_cache_hash_size(fc); 354d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs 355d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs for (order = 0; 356d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs (PAGE_SIZE << order) < 357d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs (sizeof(struct flow_cache_entry *)*flow_cache_hash_size(fc)); 358d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs order++) 359d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs /* NOTHING */; 360d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs fc->order = order; 361d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs fc->percpu = alloc_percpu(struct flow_cache_percpu); 3621da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 363d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs setup_timer(&fc->rnd_timer, flow_cache_new_hashrnd, 364d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs (unsigned long) fc); 365d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs fc->rnd_timer.expires = jiffies + FLOW_HASH_RND_PERIOD; 366d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs add_timer(&fc->rnd_timer); 3671da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 3686f912042256c12b0927438122594f5379b364f5dKAMEZAWA Hiroyuki for_each_possible_cpu(i) 369d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs flow_cache_cpu_prepare(fc, per_cpu_ptr(fc->percpu, i)); 370d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs 371d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs fc->hotcpu_notifier = (struct notifier_block){ 372d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs .notifier_call = flow_cache_cpu, 373d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs }; 374d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs register_hotcpu_notifier(&fc->hotcpu_notifier); 3751da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 3761da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds return 0; 3771da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 3781da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 379d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Terässtatic int __init flow_cache_init_global(void) 380d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs{ 381d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs flow_cachep = kmem_cache_create("flow_cache", 382d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs sizeof(struct flow_cache_entry), 383d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs 0, SLAB_PANIC, NULL); 384d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs 385d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs return flow_cache_init(&flow_cache_global); 386d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs} 387d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräs 388d7997fe1f4584da12e9c29fb682c18e9bdc13b73Timo Teräsmodule_init(flow_cache_init_global); 3891da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 3901da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus TorvaldsEXPORT_SYMBOL(flow_cache_genid); 3911da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus TorvaldsEXPORT_SYMBOL(flow_cache_lookup); 392