From ad593a5f3264eeef8d8cc3dd95202d49de2e376a Mon Sep 17 00:00:00 2001 From: Thomas Bushnell Date: Wed, 4 Sep 1996 12:47:04 +0000 Subject: *** empty log message *** --- libdiskfs/ChangeLog | 57 +++++++++++++++++++++++++ libdiskfs/lookup.c | 35 +++++++++++++++- libdiskfs/name-cache.c | 112 ++++++++++++++++++++++++++++++++++++++++--------- 3 files changed, 184 insertions(+), 20 deletions(-) (limited to 'libdiskfs') diff --git a/libdiskfs/ChangeLog b/libdiskfs/ChangeLog index 3ae2e004..a0d446e8 100644 --- a/libdiskfs/ChangeLog +++ b/libdiskfs/ChangeLog @@ -1,3 +1,60 @@ +Tue Sep 3 10:48:05 1996 Thomas Bushnell, n/BSG + + * name-cache.c (diskfs_enter_lookup_cache): Cache `.' and `..' + just like other nodes. + (diskfs_check_lookup_cache): If we get a cache hit on `..', then + do the inverse locking semantic, and only return success if things + are stable around the call. + +Fri Aug 30 21:57:18 1996 Thomas Bushnell, n/BSG + + * lookup.c (cache_misses): New variable, to find out what sort of + thing all the cache misses are. + (cm_lock): New variable. + (diskfs_lookup): Keep track of cache misses in cache_misses. + + * name-cache.c (MAXCACHE): 200 now. After experimentation, this + appears to be a pretty good value. Very little benefit after + this. + +Fri Aug 30 20:41:27 1996 Thomas Bushnell, n/BSG + + * name-cache.c (struct lookup_cache): Delete member `hits'. + New member `stati'. + (diskfs_enter_lookup_cache): Don't initialize C->hits. + (find_cache): Set C->stati before returning. + (build_partial): Delete function. + (diskfs_check_lookup_cache): Delete calls to build_partial. + Register all statistics through register_neg_hit, + register_pos_hit, and register_miss. + (MAXCACHE): 2000 now. + +Wed Aug 28 12:20:53 1996 Thomas Bushnell, n/BSG + + * name-cache.c (MAXCACHE): 500 for now. + +Mon Aug 26 15:10:55 1996 Thomas Bushnell, n/BSG + + * name-cache.c (MAXCACHE): Increase to 50000. + (struct lookup_cache): New member `hits'. + (statistics): Name struct type `struct stats'. + (diskfs_enter_lookup_cache): Initialize C->hits. + (PARTIAL_THRESH, NPARTIALS): New macros. + (partial_stats): New variable. + (build_partial): New function. + (diskfs_check_lookup_cache): Call build_partial after statistics + frobbing. + + * name-cache.c (diskfs_check_lookup_cache): Increment members of + statistics while still holding CACHE_LOCK. + +Fri Aug 16 18:23:25 1996 Thomas Bushnell, n/BSG + + * name-cache.c (diskfs_check_lookup_cache): Keep track of negative + hits properly. + * lookup.c (diskfs_lookup): On LOOKUPs that fail to find the node, + enter a negative cache entry. + Thu Aug 15 16:07:23 1996 Miles Bader * opts-version.c (diskfs_extra_version): New (weak) reference. diff --git a/libdiskfs/lookup.c b/libdiskfs/lookup.c index 40ce8937..282d829f 100644 --- a/libdiskfs/lookup.c +++ b/libdiskfs/lookup.c @@ -20,6 +20,17 @@ #include "priv.h" +static struct +{ + int present; + int absent; + int errors; + int dot; + int dotdot; +} cache_misses; +static spin_lock_t cm_lock = SPIN_LOCK_INITIALIZER; + + /* Lookup in directory DP (which is locked) the name NAME. TYPE will either be LOOKUP, CREATE, RENAME, or REMOVE. CRED identifies the user making the call. @@ -71,7 +82,7 @@ diskfs_lookup (struct node *dp, char *name, enum lookup_type type, struct protid *cred) { error_t err; - + if (type == REMOVE || type == RENAME) assert (np); @@ -119,6 +130,26 @@ diskfs_lookup (struct node *dp, char *name, enum lookup_type type, } err = diskfs_lookup_hard (dp, name, type, np, ds, cred); + + spin_lock (&cm_lock); + if (type == LOOKUP) + { + if (err == ENOENT) + cache_misses.absent++; + else if (err) + cache_misses.errors++; + else + cache_misses.present++; + if (name[0] == '.') + { + if (name[1] == '\0') + cache_misses.dot++; + else if (name[1] == '.' && name[2] == '\0') + cache_misses.dotdot++; + } + } + spin_unlock (&cm_lock); + if (err && err != ENOENT) return err; @@ -137,6 +168,8 @@ diskfs_lookup (struct node *dp, char *name, enum lookup_type type, if ((type == LOOKUP || type == CREATE) && !err && np) diskfs_enter_lookup_cache (dp, *np, name); + else if (type == LOOKUP && err == ENOENT) + diskfs_enter_lookup_cache (dp, 0, name); return err; } diff --git a/libdiskfs/name-cache.c b/libdiskfs/name-cache.c index 2cf1ed8b..808c16f4 100644 --- a/libdiskfs/name-cache.c +++ b/libdiskfs/name-cache.c @@ -24,7 +24,7 @@ #include /* Maximum number of names to cache at once */ -#define MAXCACHE 256 +#define MAXCACHE 200 /* Maximum length of file name we bother caching */ #define CACHE_NAME_LEN 100 @@ -44,7 +44,10 @@ struct lookup_cache char name[CACHE_NAME_LEN]; /* Strlen of NAME. If this is zero, it's an unused entry. */ - size_t name_len; + size_t name_len; + + /* XXX */ + int stati; }; /* The contents of the cache in no particular order */ @@ -53,13 +56,18 @@ static struct cacheq lookup_cache = { sizeof (struct lookup_cache) }; static spin_lock_t cache_lock = SPIN_LOCK_INITIALIZER; /* Buffer to hold statistics */ -static struct +static struct stats { long pos_hits; long neg_hits; long miss; long fetch_errors; } statistics; + +#define PARTIAL_THRESH 100 +#define NPARTIALS MAXCACHE / PARTIAL_THRESH +struct stats partial_stats [NPARTIALS]; + /* If there's an entry for NAME, of length NAME_LEN, in directory DIR in the cache, return it's entry, otherwise 0. CACHE_LOCK must be held. */ @@ -67,15 +75,21 @@ static struct lookup_cache * find_cache (struct node *dir, const char *name, size_t name_len) { struct lookup_cache *c; + int i; /* Search the list. All unused entries are contiguous at the end of the list, so we can stop searching when we see the first one. */ - for (c = lookup_cache.mru; c && c->name_len; c = c->hdr.next) + for (i = 0, c = lookup_cache.mru; + c && c->name_len; + c = c->hdr.next, i++) if (c->name_len == name_len && c->dir_cache_id == dir->cache_id && c->name[0] == name[0] && strcmp (c->name, name) == 0) - return c; - + { + c->stati = i / 100; + return c; + } + return 0; } @@ -90,13 +104,6 @@ diskfs_enter_lookup_cache (struct node *dir, struct node *np, char *name) if (name_len > CACHE_NAME_LEN - 1) return; - /* Never cache . or ..; it's too much trouble to get the locking - order right. */ - if (name[0] == '.' - && (name[1] == '\0' - || (name[1] == '.' && name[2] == '\0'))) - return; - spin_lock (&cache_lock); if (lookup_cache.length == 0) @@ -144,6 +151,47 @@ diskfs_purge_lookup_cache (struct node *dp, struct node *np) } spin_unlock (&cache_lock); } + +/* Register a negative hit for an entry in the Nth stat class */ +void +register_neg_hit (int n) +{ + int i; + + statistics.neg_hits++; + + for (i = 0; i < n; i++) + partial_stats[i].miss++; + for (; i < NPARTIALS; i++) + partial_stats[i].neg_hits++; +} + +/* Register a positive hit for an entry in the Nth stat class */ +void +register_pos_hit (int n) +{ + int i; + + statistics.pos_hits++; + + for (i = 0; i < n; i++) + partial_stats[i].miss++; + for (; i < NPARTIALS; i++) + partial_stats[i].pos_hits++; +} + +/* Register a miss */ +void +register_miss () +{ + int i; + + statistics.miss++; + for (i = 0; i < NPARTIALS; i++) + partial_stats[i].miss++; +} + + /* Scan the cache looking for NAME inside DIR. If we don't know anything entry at all, then return 0. If the entry is confirmed to @@ -163,15 +211,18 @@ diskfs_check_lookup_cache (struct node *dir, char *name) cacheq_make_mru (&lookup_cache, c); /* Record C as recently used. */ - statistics.pos_hits++; - spin_unlock (&cache_lock); - if (id == 0) /* A negative cache entry. */ - return (struct node *)-1; + { + register_neg_hit (c->stati); + spin_unlock (&cache_lock); + return (struct node *)-1; + } else if (id == dir->cache_id) /* The cached node is the same as DIR. */ { + register_pos_hit (c->stati); + spin_unlock (&cache_lock); diskfs_nref (dir); return dir; } @@ -179,12 +230,35 @@ diskfs_check_lookup_cache (struct node *dir, char *name) /* Just a normal entry in DIR; get the actual node. */ { struct node *np; - error_t err = diskfs_cached_lookup (id, &np); + error_t err; + + register_pos_hit (c->stati); + spin_unlock (&cache_lock); + + if (name[0] == '.' && name[1] == '.' && name[2] == '\0') + { + mutex_unlock (&dir->lock); + err = diskfs_cached_lookup (id, &np); + mutex_lock (&dir->lock); + + /* In the window where DP was unlocked, we might + have lost. So check the cache again, and see + if it's still there; if so, then we win. */ + c = find_cache (dir, "..", 2); + if (!c || c->node_cache_id != id) + { + /* Lose */ + mutex_unlock (&np->lock); + return 0; + } + } + else + err = diskfs_cached_lookup (id, &np); return err ? 0 : np; } } - statistics.miss++; + register_miss (); spin_unlock (&cache_lock); return 0; -- cgit v1.2.3