Module Name: src Committed By: riastradh Date: Sat Mar 18 21:03:28 UTC 2017
Modified Files: src/sys/kern: vfs_cache.c src/sys/sys: namei.src Log Message: Rework namecache locking commentary. - Annotate struct namecache declaration in namei.src/namei.h. - Bulleted lists, not walls of texts. - Identify lock order too. - Note subtle exceptions. To generate a diff of this commit: cvs rdiff -u -r1.116 -r1.117 src/sys/kern/vfs_cache.c cvs rdiff -u -r1.38 -r1.39 src/sys/sys/namei.src Please note that diffs are not public domain; they are subject to the copyright notices on the relevant files.
Modified files: Index: src/sys/kern/vfs_cache.c diff -u src/sys/kern/vfs_cache.c:1.116 src/sys/kern/vfs_cache.c:1.117 --- src/sys/kern/vfs_cache.c:1.116 Sat Mar 18 20:01:44 2017 +++ src/sys/kern/vfs_cache.c Sat Mar 18 21:03:28 2017 @@ -1,4 +1,4 @@ -/* $NetBSD: vfs_cache.c,v 1.116 2017/03/18 20:01:44 riastradh Exp $ */ +/* $NetBSD: vfs_cache.c,v 1.117 2017/03/18 21:03:28 riastradh Exp $ */ /*- * Copyright (c) 2008 The NetBSD Foundation, Inc. @@ -58,7 +58,7 @@ */ #include <sys/cdefs.h> -__KERNEL_RCSID(0, "$NetBSD: vfs_cache.c,v 1.116 2017/03/18 20:01:44 riastradh Exp $"); +__KERNEL_RCSID(0, "$NetBSD: vfs_cache.c,v 1.117 2017/03/18 21:03:28 riastradh Exp $"); #ifdef _KERNEL_OPT #include "opt_ddb.h" @@ -103,71 +103,95 @@ __KERNEL_RCSID(0, "$NetBSD: vfs_cache.c, */ /* - * The locking in this subsystem works as follows: + * Locking. * - * When an entry is added to the cache, via cache_enter(), - * namecache_lock is taken to exclude other writers. The new - * entry is added to the hash list in a way which permits - * concurrent lookups and invalidations in the cache done on - * other CPUs to continue in parallel. - * - * When a lookup is done in the cache, via cache_lookup() or - * cache_lookup_raw(), the per-cpu lock below is taken. This - * protects calls to cache_lookup_entry() and cache_invalidate() - * against cache_reclaim() but allows lookups to continue in - * parallel with cache_enter(). - * - * cache_revlookup() takes namecache_lock to exclude cache_enter() - * and cache_reclaim() since the list it operates on is not - * maintained to allow concurrent reads. - * - * When cache_reclaim() is called namecache_lock is held to hold - * off calls to cache_enter()/cache_revlookup() and each of the - * per-cpu locks is taken to hold off lookups. Holding all these - * locks essentially idles the subsystem, ensuring there are no - * concurrent references to the cache entries being freed. - * - * 32 bit per-cpu statistic counters (struct nchstats_percpu) are - * incremented when the operations they count are performed while - * running on the corresponding CPU. Frequently individual counters - * are incremented while holding a lock (either a per-cpu lock or - * namecache_lock) sufficient to preclude concurrent increments - * being done to the same counter, so non-atomic increments are - * done using the COUNT() macro. Counters which are incremented - * when one of these locks is not held use the COUNT_UNL() macro - * instead. COUNT_UNL() could be defined to do atomic increments - * but currently just does what COUNT() does, on the theory that - * it is unlikely the non-atomic increment will be interrupted - * by something on the same CPU that increments the same counter, - * but even if it does happen the consequences aren't serious. + * L namecache_lock Global lock for namecache table and queues. + * C struct nchcpu::cpu_lock Per-CPU lock to reduce read contention. + * N struct namecache::nc_lock Per-entry lock. + * V struct vnode::v_interlock Vnode interlock. + * + * Lock order: C -> N -> L -> V + * + * All use serialized by namecache_lock: + * + * nclruhead / struct namecache::nc_lru + * ncvhashtbl / struct namecache::nc_vhash + * struct vnode_impl::vi_dnclist / struct namecache::nc_dvlist + * struct vnode_impl::vi_nclist / struct namecache::nc_vlist + * nchstats + * + * - Insertion serialized by namecache_lock, + * - read protected by per-CPU lock, + * - insert/read ordering guaranteed by memory barriers, and + * - deletion allowed only under namecache_lock and *all* per-CPU locks + * in CPU_INFO_FOREACH order: + * + * nchashtbl / struct namecache::nc_hash + * + * The per-CPU locks exist only to reduce the probability of + * contention between readers. We do not bind to a CPU, so + * contention is still possible. + * + * All use serialized by struct namecache::nc_lock: + * + * struct namecache::nc_dvp + * struct namecache::nc_vp + * struct namecache::nc_gcqueue (*) + * struct namecache::nc_hittime (**) + * + * (*) Once on the queue, only cache_thread uses this nc_gcqueue, unlocked. + * (**) cache_prune reads nc_hittime unlocked, since approximate is OK. + * + * Unlocked because stable after initialization: + * + * struct namecache::nc_dvp + * struct namecache::nc_vp + * struct namecache::nc_flags + * struct namecache::nc_nlen + * struct namecache::nc_name + * + * Unlocked because approximation is OK: + * + * struct nchcpu::cpu_stats + * struct nchcpu::cpu_stats_last + * + * Updates under namecache_lock or any per-CPU lock are marked with + * COUNT, while updates outside those locks are marked with COUNT_UNL. + * + * - The theory seems to have been that you could replace COUNT_UNL by + * atomic operations -- except that doesn't help unless you also + * replace COUNT by atomic operations, because mixing atomics and + * nonatomics is a recipe for failure. + * - We use 32-bit per-CPU counters and 64-bit global counters under + * the theory that 32-bit counters are less likely to be hosed by + * nonatomic increment. + */ + +/* + * The comment below is preserved for posterity in case it is + * important, but it is clear that everywhere the namecache_count_*() + * functions are called, other cache_*() functions that take the same + * locks are also called, so I can't imagine how this could be a + * problem: * * N.B.: Attempting to protect COUNT_UNL() increments by taking * a per-cpu lock in the namecache_count_*() functions causes * a deadlock. Don't do that, use atomic increments instead if * the imperfections here bug you. + */ + +/* + * struct nchstats_percpu: * - * The 64 bit system-wide statistic counts (struct nchstats) are - * maintained by sampling the per-cpu counters periodically, adding - * in the deltas since the last samples and recording the current - * samples to use to compute the next delta. The sampling is done - * as a side effect of cache_reclaim() which is run periodically, - * for its own purposes, often enough to avoid overflow of the 32 - * bit counters. While sampling in this fashion requires no locking - * it is never-the-less done only after all locks have been taken by - * cache_reclaim() to allow cache_stat_sysctl() to hold off - * cache_reclaim() with minimal locking. - * - * cache_stat_sysctl() takes its CPU's per-cpu lock to hold off - * cache_reclaim() so that it can copy the subsystem total stats - * without them being concurrently modified. If CACHE_STATS_CURRENT - * is defined it also harvests the per-cpu increments into the total, - * which again requires cache_reclaim() to be held off. - * - * The per-cpu data (a lock and the per-cpu stats structures) - * are defined next. + * Per-CPU counters. */ struct nchstats_percpu _NAMEI_CACHE_STATS(uint32_t); +/* + * struct nchcpu: + * + * Per-CPU namecache state: lock and per-CPU counters. + */ struct nchcpu { kmutex_t cpu_lock; struct nchstats_percpu cpu_stats; Index: src/sys/sys/namei.src diff -u src/sys/sys/namei.src:1.38 src/sys/sys/namei.src:1.39 --- src/sys/sys/namei.src:1.38 Sat Mar 18 19:43:31 2017 +++ src/sys/sys/namei.src Sat Mar 18 21:03:28 2017 @@ -1,4 +1,4 @@ -/* $NetBSD: namei.src,v 1.38 2017/03/18 19:43:31 riastradh Exp $ */ +/* $NetBSD: namei.src,v 1.39 2017/03/18 21:03:28 riastradh Exp $ */ /* * Copyright (c) 1985, 1989, 1991, 1993 @@ -201,21 +201,28 @@ NAMEIFL PARAMASK 0x02ee300 /* mask of pa * accessed and mostly read-only data is toward the front, with * infrequently accessed data and the lock towards the rear. The * lock is then more likely to be in a seperate cache line. - */ -struct namecache { - LIST_ENTRY(namecache) nc_hash; /* hash chain */ - LIST_ENTRY(namecache) nc_vhash; /* directory hash chain */ - struct vnode *nc_dvp; /* vnode of parent of name */ - struct vnode *nc_vp; /* vnode the name refers to */ - int nc_flags; /* copy of componentname's ISWHITEOUT */ - char nc_nlen; /* length of name */ - char nc_name[NCHNAMLEN]; /* segment name */ - void *nc_gcqueue; /* queue for garbage collection */ - TAILQ_ENTRY(namecache) nc_lru; /* psuedo-lru chain */ - LIST_ENTRY(namecache) nc_dvlist; - LIST_ENTRY(namecache) nc_vlist; - kmutex_t nc_lock; /* lock on this entry */ - int nc_hittime; /* last time scored a hit */ + * + * Locking rules: + * + * - stable after initialization + * L namecache_lock + * C struct nchcpu::cpu_lock + * N struct namecache::nc_lock + */ +struct namecache { + LIST_ENTRY(namecache) nc_hash; /* L hash chain */ + LIST_ENTRY(namecache) nc_vhash; /* L directory hash chain */ + struct vnode *nc_dvp; /* - vnode of parent of name */ + struct vnode *nc_vp; /* - vnode the name refers to */ + int nc_flags; /* - copy of componentname ISWHITEOUT */ + char nc_nlen; /* - length of name */ + char nc_name[NCHNAMLEN]; /* - segment name */ + void *nc_gcqueue; /* N queue for garbage collection */ + TAILQ_ENTRY(namecache) nc_lru; /* L psuedo-lru chain */ + LIST_ENTRY(namecache) nc_dvlist;/* L dvp's list of cache entries */ + LIST_ENTRY(namecache) nc_vlist; /* L vp's list of cache entries */ + kmutex_t nc_lock; /* lock on this entry */ + int nc_hittime; /* N last time scored a hit */ }; #ifdef _KERNEL