[linuxkernelnewbies] Linux/net/ipv4/route.c: routing table / cache implementation

[Peter Teoh]

http://lxr.free-electrons.com/source/net/ipv4/route.c /* * Route cache. */ /* The locking scheme is rather straight forward: * * 1) Read-Copy Update protects the buckets of the central route hash. * 2) Only writers remove entries, and they hold the lock * as they look at rtable reference counts. * 3) Only readers acquire references to rtable entries, * they do so with atomic increments and with the * lock held. */ struct rt_hash_bucket { struct rtable *chain; }; #if defined(CONFIG_SMP) || defined(CONFIG_DEBUG_SPINLOCK) || \ defined(CONFIG_PROVE_LOCKING) /* * Instead of using one spinlock for each rt_hash_bucket, we use a table of spinlocks * The size of this table is a power of two and depends on the number of CPUS. * (on lockdep we have a quite big spinlock_t, so keep the size down there) */ #ifdef CONFIG_LOCKDEP # define RT_HASH_LOCK_SZ 256 #else # if NR_CPUS >= 32 # define RT_HASH_LOCK_SZ 4096 # elif NR_CPUS >= 16 # define RT_HASH_LOCK_SZ 2048 # elif NR_CPUS >= 8 # define RT_HASH_LOCK_SZ 1024 # elif NR_CPUS >= 4 # define RT_HASH_LOCK_SZ 512 # else # define RT_HASH_LOCK_SZ 256 # endif #endif static spinlock_t *rt_hash_locks; # define rt_hash_lock_addr(slot) &rt_hash_locks[(slot) & (RT_HASH_LOCK_SZ - 1)] static __init void rt_hash_lock_init(void) { int i; rt_hash_locks = kmalloc(sizeof(spinlock_t) * RT_HASH_LOCK_SZ, GFP_KERNEL); if (!rt_hash_locks) panic("IP: failed to allocate rt_hash_locks\n"); for (i = 0; i < RT_HASH_LOCK_SZ; i++) spin_lock_init(&rt_hash_locks[i]); } #else # define rt_hash_lock_addr(slot) NULL static inline void rt_hash_lock_init(void) { } #endif static struct rt_hash_bucket *rt_hash_table __read_mostly; static unsigned rt_hash_mask __read_mostly; static unsigned int rt_hash_log __read_mostly; static DEFINE_PER_CPU(struct rt_cache_stat, rt_cache_stat); #define RT_CACHE_STAT_INC(field) \ (__raw_get_cpu_var(rt_cache_stat).field++) static inline unsigned int rt_hash(__be32 daddr, __be32 saddr, int idx, int genid) { return jhash_3words((__force u32)(__be32)(daddr), (__force u32)(__be32)(saddr), idx, genid) & rt_hash_mask; } static inline int rt_genid(struct net *net) { return atomic_read(&net->ipv4.rt_genid); } #ifdef CONFIG_PROC_FS struct rt_cache_iter_state { struct seq_net_private p; int bucket; int genid; }; static struct rtable *rt_cache_get_first(struct seq_file *seq) { struct rt_cache_iter_state *st = seq->private; struct rtable *r = NULL; for (st->bucket = rt_hash_mask; st->bucket >= 0; --st->bucket) { if (!rt_hash_table[st->bucket].chain) continue; rcu_read_lock_bh(); r = rcu_dereference(rt_hash_table[st->bucket].chain); while (r) { if (dev_net(r->u.dst.dev) == seq_file_net(seq) && r->rt_genid == st->genid) return r; r = rcu_dereference(r->u.dst.rt_next); } rcu_read_unlock_bh(); } return r; } static struct rtable *__rt_cache_get_next(struct seq_file *seq, struct rtable *r) { struct rt_cache_iter_state *st = seq->private; r = r->u.dst.rt_next; while (!r) { rcu_read_unlock_bh(); do { if (--st->bucket < 0) return NULL; } while (!rt_hash_table[st->bucket].chain); rcu_read_lock_bh(); r = rt_hash_table[st->bucket].chain; } return rcu_dereference(r); } static struct rtable *rt_cache_get_next(struct seq_file *seq, struct rtable *r) { struct rt_cache_iter_state *st = seq->private; while ((r = __rt_cache_get_next(seq, r)) != NULL) { if (dev_net(r->u.dst.dev) != seq_file_net(seq)) continue; if (r->rt_genid == st->genid) break; } return r; } static struct rtable *rt_cache_get_idx(struct seq_file *seq, loff_t pos) { struct rtable *r = rt_cache_get_first(seq); if (r) while (pos && (r = rt_cache_get_next(seq, r))) --pos; return pos ? NULL : r; } static void *rt_cache_seq_start(struct seq_file *seq, loff_t *pos) { struct rt_cache_iter_state *st = seq->private; if (*pos) return rt_cache_get_idx(seq, *pos - 1); st->genid = rt_genid(seq_file_net(seq)); return SEQ_START_TOKEN; } static void *rt_cache_seq_next(struct seq_file *seq, void *v, loff_t *pos) { struct rtable *r; if (v == SEQ_START_TOKEN) r = rt_cache_get_first(seq); else r = rt_cache_get_next(seq, v); ++*pos; return r; }