Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/ad-namecache]: src/sys - Put all the namecache stuff back into vnode_imp...
details: https://anonhg.NetBSD.org/src/rev/07002cf6992d
branches: ad-namecache
changeset: 1025047:07002cf6992d
user: ad <ad%NetBSD.org@localhost>
date: Fri Jan 24 16:48:58 2020 +0000
description:
- Put all the namecache stuff back into vnode_impl_t.
- Tidy vfs_cache.c up, finish the comments.
- Finalise how ID information is entered to the cache.
- Handle very small/old systems.
diffstat:
sys/fs/tmpfs/tmpfs_subr.c | 10 +-
sys/fs/tmpfs/tmpfs_vfsops.c | 7 +-
sys/kern/vfs_cache.c | 793 +++++++++++++++++++++----------------------
sys/sys/namei.src | 12 +-
sys/ufs/ffs/ffs_vfsops.c | 11 +-
sys/ufs/ufs/ufs_vnops.c | 12 +-
6 files changed, 407 insertions(+), 438 deletions(-)
diffs (truncated from 1599 to 300 lines):
diff -r e8ecd70bd55b -r 07002cf6992d sys/fs/tmpfs/tmpfs_subr.c
--- a/sys/fs/tmpfs/tmpfs_subr.c Fri Jan 24 16:05:37 2020 +0000
+++ b/sys/fs/tmpfs/tmpfs_subr.c Fri Jan 24 16:48:58 2020 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: tmpfs_subr.c,v 1.105.2.1 2020/01/17 22:26:25 ad Exp $ */
+/* $NetBSD: tmpfs_subr.c,v 1.105.2.2 2020/01/24 16:48:58 ad Exp $ */
/*
* Copyright (c) 2005-2013 The NetBSD Foundation, Inc.
@@ -73,7 +73,7 @@
*/
#include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: tmpfs_subr.c,v 1.105.2.1 2020/01/17 22:26:25 ad Exp $");
+__KERNEL_RCSID(0, "$NetBSD: tmpfs_subr.c,v 1.105.2.2 2020/01/24 16:48:58 ad Exp $");
#include <sys/param.h>
#include <sys/cprng.h>
@@ -148,7 +148,7 @@
node->tn_vnode = vp;
uvm_vnp_setsize(vp, node->tn_size);
KASSERT(node->tn_mode != VNOVAL);
- cache_set_id(vp, node->tn_mode, node->tn_uid, node->tn_gid);
+ cache_enter_id(vp, node->tn_mode, node->tn_uid, node->tn_gid);
}
/*
@@ -1039,7 +1039,7 @@
node->tn_mode = (mode & ALLPERMS);
tmpfs_update(vp, TMPFS_UPDATE_CTIME);
VN_KNOTE(vp, NOTE_ATTRIB);
- cache_update_id(vp, node->tn_mode, node->tn_uid, node->tn_gid);
+ cache_enter_id(vp, node->tn_mode, node->tn_uid, node->tn_gid);
return 0;
}
@@ -1084,7 +1084,7 @@
node->tn_gid = gid;
tmpfs_update(vp, TMPFS_UPDATE_CTIME);
VN_KNOTE(vp, NOTE_ATTRIB);
- cache_update_id(vp, node->tn_mode, node->tn_uid, node->tn_gid);
+ cache_enter_id(vp, node->tn_mode, node->tn_uid, node->tn_gid);
return 0;
}
diff -r e8ecd70bd55b -r 07002cf6992d sys/fs/tmpfs/tmpfs_vfsops.c
--- a/sys/fs/tmpfs/tmpfs_vfsops.c Fri Jan 24 16:05:37 2020 +0000
+++ b/sys/fs/tmpfs/tmpfs_vfsops.c Fri Jan 24 16:48:58 2020 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: tmpfs_vfsops.c,v 1.75.2.2 2020/01/19 21:21:54 ad Exp $ */
+/* $NetBSD: tmpfs_vfsops.c,v 1.75.2.3 2020/01/24 16:48:58 ad Exp $ */
/*
* Copyright (c) 2005, 2006, 2007 The NetBSD Foundation, Inc.
@@ -42,7 +42,7 @@
*/
#include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: tmpfs_vfsops.c,v 1.75.2.2 2020/01/19 21:21:54 ad Exp $");
+__KERNEL_RCSID(0, "$NetBSD: tmpfs_vfsops.c,v 1.75.2.3 2020/01/24 16:48:58 ad Exp $");
#include <sys/param.h>
#include <sys/atomic.h>
@@ -182,7 +182,8 @@
mp->mnt_stat.f_namemax = TMPFS_MAXNAMLEN;
mp->mnt_fs_bshift = PAGE_SHIFT;
mp->mnt_dev_bshift = DEV_BSHIFT;
- mp->mnt_iflag |= IMNT_MPSAFE | IMNT_CAN_RWTORO | IMNT_SHRLOOKUP;
+ mp->mnt_iflag |= IMNT_MPSAFE | IMNT_CAN_RWTORO | IMNT_SHRLOOKUP |
+ IMNT_NCLOOKUP;
vfs_getnewfsid(mp);
/* Allocate the tmpfs mount structure and fill it. */
diff -r e8ecd70bd55b -r 07002cf6992d sys/kern/vfs_cache.c
--- a/sys/kern/vfs_cache.c Fri Jan 24 16:05:37 2020 +0000
+++ b/sys/kern/vfs_cache.c Fri Jan 24 16:48:58 2020 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: vfs_cache.c,v 1.126.2.10 2020/01/23 12:33:18 ad Exp $ */
+/* $NetBSD: vfs_cache.c,v 1.126.2.11 2020/01/24 16:48:59 ad Exp $ */
/*-
* Copyright (c) 2008, 2019, 2020 The NetBSD Foundation, Inc.
@@ -64,45 +64,46 @@
* Name caching:
*
* Names found by directory scans are retained in a cache for future
- * reference. It is managed pseudo-LRU, so frequently used names will
- * hang around. The cache is indexed by directory.
+ * reference. It is managed LRU, so frequently used names will hang
+ * around. The cache is indexed by hash value obtained from the name.
*
- * Background:
+ * The name cache (or directory name lookup cache) is the brainchild of
+ * Robert Elz and made its first appearance in 4.3BSD.
*
- * XXX add a bit of history
- *
- * Data structures
+ * Data structures:
*
- * Typically DNLCs use a global hash table for lookup, which works very
- * well but can cause challenges for the CPU cache on modern CPUs, and
- * concurrency headaches for the kernel hacker. The focus of interest
- * in this implementation is the directory itself: a per-directory data
- * structure is used to index names. Currently this is a red-black
- * tree. There are no special concurrency requirements placed on the
- * index, so it should not be difficult to experiment with other
- * structures.
+ * Most Unix namecaches very sensibly use a global hash table to index
+ * names. The global hash table works well, but can cause concurrency
+ * headaches for the kernel hacker. In the NetBSD 10.0 implementation
+ * we are not sensible, and use a per-directory data structure to index
+ * names, but the cache otherwise functions the same.
+ *
+ * The index is a red-black tree. There are no special concurrency
+ * requirements placed on it, because it's per-directory and protected
+ * by the namecache's per-directory locks. It should therefore not be
+ * difficult to experiment with other data structures.
*
* Each cached name is stored in a struct namecache, along with a
- * pointer the associated vnode (nc_vp). For simplicity (and economy
- * of storage), names longer than a maximum length of NCHNAMLEN are
- * allocated with kmem_alloc(); they occur infrequently. Names shorter
- * than this are stored directly in struct namecache. If it is a
- * "negative" entry, (i.e. for a name that is known NOT to exist) the
- * vnode pointer will be NULL.
+ * pointer to the associated vnode (nc_vp). Names longer than a
+ * maximum length of NCHNAMLEN are allocated with kmem_alloc(); they
+ * occur infrequently, and names shorter than this are stored directly
+ * in struct namecache. If it is a "negative" entry, (i.e. for a name
+ * that is known NOT to exist) the vnode pointer will be NULL.
*
- * The nchnode (XXXAD vnode) and namecache structures are connected together thusly
+ * For a directory with 3 cached names for 3 distinct vnodes, the
+ * various vnodes and namecache structs would be connected like this
* (the root is at the bottom of the diagram):
*
* ...
* ^
- * |- nn_tree
+ * |- vi_nc_tree
* |
* +----o----+ +---------+ +---------+
* | VDIR | | VCHR | | VREG |
- * | nchnode o-----+ | nchnode o-----+ | nchnode o------+
+ * | vnode o-----+ | vnode o-----+ | vnode o------+
* +---------+ | +---------+ | +---------+ |
* ^ | ^ | ^ |
- * |- nc_nn |- nn_list |- nc_nn |- nn_list |- nc_nn |
+ * |- nc_vp |- vi_nc_list |- nc_vp |- vi_nc_list |- nc_vp |
* | | | | | |
* +----o----+ | +----o----+ | +----o----+ |
* +---onamecache|<----+ +---onamecache|<----+ +---onamecache|<-----+
@@ -110,12 +111,12 @@
* | ^ | ^ | ^
* | | | | | |
* | | +----------------------+ | |
- * |-nc_dnn | +-------------------------------------------------+
- * | |/- nn_tree | |
- * | | |- nc_dnn |- nc_dnn
+ * |-nc_dvp | +-------------------------------------------------+
+ * | |/- vi_nc_tree | |
+ * | | |- nc_dvp |- nc_dvp
* | +----o----+ | |
* +-->| VDIR |<----------+ |
- * | nchnode |<------------------------------------+
+ * | vnode |<------------------------------------+
* +---------+
*
* START HERE
@@ -123,44 +124,53 @@
* Replacement:
*
* As the cache becomes full, old and unused entries are purged as new
- * entries are added. It would be too expensive to maintain a strict
- * LRU list based on last access, so instead we ape the VM system and
- * maintain lits of active and inactive entries. New entries go to the
- * tail of the active list. After they age out, they are placed on the
- * tail of the inactive list. Any subsequent use of the cache entry
- * reactivates it, saving it from impending doom; if not reactivated,
- * the entry will eventually be purged.
+ * entries are added. The synchronization overhead in maintaining a
+ * strict ordering would be prohibitive, so the VM system's "clock" or
+ * "second chance" page replacement algorithm is aped here. New
+ * entries go to the tail of the active list. After they age out and
+ * reach the head of the list, they are moved to the tail of the
+ * inactive list. Any use of the deactivated cache entry reactivates
+ * it, saving it from impending doom; if not reactivated, the entry
+ * eventually reaches the head of the inactive list and is purged.
*
* Concurrency:
*
- * From a performance perspective, cache_lookup(nameiop == LOOKUP) and
- * its siblings are what really matters; insertion of new entries with
- * cache_enter() is comparatively infrequent. This dictates the
- * concurrency strategy: lookups must be easy, never difficult.
+ * From a performance perspective, cache_lookup(nameiop == LOOKUP) is
+ * what really matters; insertion of new entries with cache_enter() is
+ * comparatively infrequent, and overshadowed by the cost of expensive
+ * file system metadata operations (which may involve disk I/O). We
+ * therefore want to make everything simplest in the lookup path.
*
* struct namecache is mostly stable except for list and tree related
- * entries, which don't affect the cached name or vnode, and entries
- * are purged in preference to modifying them. Read access to
- * namecache entries is made via tree, list, or LRU list. A lock
- * corresponding to the direction of access should be held. See
- * definition of "struct namecache" in src/sys/namei.src, and the
- * definition of "struct nchnode" XXXAD vnode for the particulars.
+ * entries, changes to which don't affect the cached name or vnode.
+ * For changes to name+vnode, entries are purged in preference to
+ * modifying them.
*
- * Per-CPU statistics, and "numcache" are read unlocked, since an
- * approximate value is OK. We maintain uintptr_t sized per-CPU
+ * Read access to namecache entries is made via tree, list, or LRU
+ * list. A lock corresponding to the direction of access should be
+ * held. See definition of "struct namecache" in src/sys/namei.src,
+ * and the definition of "struct vnode" for the particulars.
+ *
+ * Per-CPU statistics, and LRU list totals are read unlocked, since
+ * an approximate value is OK. We maintain uintptr_t sized per-CPU
* counters and 64-bit global counters under the theory that uintptr_t
* sized counters are less likely to be hosed by nonatomic increment.
*
* The lock order is:
*
- * 1) nn->nn_lock (tree or parent->child direction)
- * 2) nn->nn_listlock (list or child->parent direction)
- * 3) cache_lru_lock (LRU list direction)
- * 4) vp->v_interlock
+ * 1) vi->vi_nc_lock (tree or parent -> child direction,
+ * used during forward lookup)
+ *
+ * 2) vi->vi_nc_listlock (list or child -> parent direction,
+ * used during reverse lookup)
+ *
+ * 3) cache_lru_lock (LRU list direction, used during reclaim)
+ *
+ * 4) vp->v_interlock (what the cache entry points to)
*/
#include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: vfs_cache.c,v 1.126.2.10 2020/01/23 12:33:18 ad Exp $");
+__KERNEL_RCSID(0, "$NetBSD: vfs_cache.c,v 1.126.2.11 2020/01/24 16:48:59 ad Exp $");
#define __NAMECACHE_PRIVATE
#ifdef _KERNEL_OPT
@@ -186,31 +196,6 @@
#include <miscfs/genfs/genfs.h>
-/*
- * Per-vnode state for the namecache. Field markings and corresponding
- * locks. XXXAD this needs to be folded back into struct vnode, but
- * struct vnode_impl_t needs to be folded back into struct vnode first.
- *
- * - stable throught the lifetime of the vnode
- * n protected by nn_lock
- * l protected by nn_listlock
- */
-struct nchnode {
- /* First cache line: frequently used stuff. */
- rb_tree_t nn_tree; /* n namecache tree */
- TAILQ_HEAD(,namecache) nn_list; /* l namecaches (parent) */
- mode_t nn_mode; /* n cached mode or VNOVAL */
- uid_t nn_uid; /* n cached UID or VNOVAL */
- gid_t nn_gid; /* n cached GID or VNOVAL */
- uint32_t nn_spare; /* - spare (padding) */
-
- /* Second cache line: locks and infrequenly used stuff. */
- krwlock_t nn_lock /* - lock on node */
- __aligned(COHERENCY_UNIT);
- krwlock_t nn_listlock; /* - lock on nn_list */
- struct vnode *nn_vp; /* - backpointer to vnode */
-};
-
static void cache_activate(struct namecache *);
static int cache_compare_key(void *, const void *, const void *);
static int cache_compare_nodes(void *, const void *, const void *);
@@ -223,7 +208,6 @@
/* Global pool cache. */
static pool_cache_t cache_pool __read_mostly;
-static pool_cache_t cache_node_pool __read_mostly;
/* LRU replacement. */
enum cache_lru_id {
@@ -250,7 +234,7 @@
/* Tunables */
static const int cache_lru_maxdeact = 2; /* max # to deactivate */
-static const int cache_lru_maxscan = 128; /* max # to scan/reclaim */
+static const int cache_lru_maxscan = 64; /* max # to scan/reclaim */
static int doingcache = 1; /* 1 => enable the cache */
/* sysctl */
@@ -312,23 +296,22 @@
static int
cache_compare_key(void *context, const void *n, const void *k)
Home |
Main Index |
Thread Index |
Old Index