summaryrefslogtreecommitdiff
path: root/libdiskfs
diff options
context:
space:
mode:
authorMiles Bader <miles@gnu.org>1996-04-10 23:53:07 +0000
committerMiles Bader <miles@gnu.org>1996-04-10 23:53:07 +0000
commit4fbc3d2ee286970b171f64020f38b2a5befa2628 (patch)
tree64353fa9cc9a42a0b738fd73c2d6777159167ec8 /libdiskfs
parent969b3eaa5d27ede6efeb25e8ccd0ee08a161a300 (diff)
(struct lookup_cache):
Add NEXT & PREV fields. Rename LEN back to NAME_LEN. (lru_cache, mru_cache): New variables. (first_cache, last_cache): Variables removed. (make_mru, make_lru, find_cache, init_lookup_cache): New functions. (diskfs_enter_lookup_cache, diskfs_purge_lookup_cache, diskfs_check_lookup_cache): Rewrite to use the linked list. Deal with negative entries. Reuse old entries for the given name.
Diffstat (limited to 'libdiskfs')
-rw-r--r--libdiskfs/name-cache.c240
1 files changed, 175 insertions, 65 deletions
diff --git a/libdiskfs/name-cache.c b/libdiskfs/name-cache.c
index ecb67e6d..daf54bed 100644
--- a/libdiskfs/name-cache.c
+++ b/libdiskfs/name-cache.c
@@ -1,6 +1,7 @@
/* Directory name lookup caching
+
Copyright (C) 1996 Free Software Foundation, Inc.
- Written by Michael I. Bushnell, p/BSG.
+ Written by Michael I. Bushnell, p/BSG, & Miles Bader.
This file is part of the GNU Hurd.
@@ -21,7 +22,7 @@
#include "priv.h"
#include <string.h>
-
+
/* Maximum number of names to cache at once */
#define MAXCACHE 256
@@ -31,25 +32,31 @@
/* Cache entry */
struct lookup_cache
{
+ /* Used to indentify nodes to the fs dependent code. 0 for NODE_CACHE_ID
+ means a `negative' entry -- recording that there's definitely no node with
+ this name. */
int dir_cache_id, node_cache_id;
- size_t len; /* strlen of name */
-
+ /* Name of the node NODE_CACHE_ID in the directory DIR_CACHE_ID. Entries
+ with names too long to fit in this buffer aren't cached at all. */
char name[CACHE_NAME_LEN];
+
+ /* Strlen of NAME. If this is zero, it's an unused entry. */
+ size_t name_len;
+
+ /* Next and prev entries in the cache, linked in LRU order. */
+ struct lookup_cache *next, *prev;
};
/* The contents of the cache in no particular order */
static struct lookup_cache lookup_cache[MAXCACHE];
-/* A rotating buffer of cache entries, maintaining an LRU
- ordering of lookup_cache. */
-static int cache_indexes[MAXCACHE];
-
-/* The current live entries start at first_cache and run through to
- last_cache. When the cache is full, first_cache == last_cache,
- and these point at the lru element; lower indexes in cache_indexes
- are successively less recently used. */
-static int first_cache, last_cache;
+/* The least, and most, recently used entries in the cache. These point to
+ either end of a linked list composed of all the elements of LOOKUP_CACHE.
+ This list will always be the same length -- if an element is `removed',
+ its entry is simply marked inactive, and moved to the LRU end of the list
+ so it will be reused first. */
+static struct lookup_cache *lru_cache = 0, *mru_cache = 0;
static spin_lock_t cache_lock = SPIN_LOCK_INITIALIZER;
@@ -61,51 +68,154 @@ static struct
long miss;
long fetch_errors;
} statistics;
+
+/* Move C to the most-recently-used end of the cache. CACHE_LOCK must be
+ held. */
+static void
+make_mru (struct lookup_cache *c)
+{
+ if (c != mru_cache)
+ {
+ /* First remove it. We known C->prev isn't 0 because C wasn't
+ previously == MRU_CACHE. */
+ c->prev->next = c->next;
+ if (c->next)
+ c->next->prev = c->prev;
+ else
+ lru_cache = c->prev;
+
+ /* Now make it MRU_CACHE. */
+ c->next = mru_cache;
+ c->prev = 0;
+ mru_cache->prev = c;
+ mru_cache = c;
+ }
+}
+
+/* Move C to the least-recently-used end of the cache. CACHE_LOCK must be
+ held. */
+static void
+make_lru (struct lookup_cache *c)
+{
+ if (c != lru_cache)
+ {
+ /* First remove it. We known C->next isn't 0 because C wasn't
+ previously == LRU_CACHE. */
+ c->next->prev = c->prev;
+ if (c->prev)
+ c->prev->next = c->next;
+ else
+ mru_cache = c->next;
+
+ /* Now make it LRU_CACHE. */
+ c->prev = lru_cache;
+ c->next = 0;
+ lru_cache->next = c;
+ lru_cache = c;
+ }
+}
+
+/* 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. */
+static struct lookup_cache *
+find_cache (struct node *dir, const char *name, size_t name_len)
+{
+ struct lookup_cache *c;
+
+ /* 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 = mru_cache; c && c->name_len; c = c->next)
+ 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;
+
+ return 0;
+}
+
+/* Put all the elements of the LOOKUP_CACHE array in a doubly linked list
+ pointed to at either end by LRU_CACHE and MRU_CACHE, and initialize each
+ entry. */
+static void
+init_lookup_cache ()
+{
+ int i;
+ lru_cache = mru_cache = &lookup_cache[0];
+
+ lru_cache->name_len = 0;
+ lru_cache->next = 0;
+
+ for (i = 1; i < MAXCACHE; i++)
+ {
+ struct lookup_cache *c = &lookup_cache[i];
+ c->name_len = 0;
+ c->next = mru_cache;
+ mru_cache->prev = c;
+ mru_cache = c;
+ }
+
+ mru_cache->prev = 0;
+}
+
/* Node NP has just been found in DIR with NAME. If NP is null, that
means that this name has been confirmed as absent in the directory. */
void
diskfs_enter_lookup_cache (struct node *dir, struct node *np, char *name)
{
- size_t len = strlen (name);
- struct lookup_cache *lc;
+ struct lookup_cache *c;
+ size_t name_len = strlen (name);
- if (len > CACHE_NAME_LEN - 1)
+ if (name_len > CACHE_NAME_LEN - 1)
return;
spin_lock (&cache_lock);
- /* Take first_cache + 1 and fill it with the new entry */
- lc = &lookup_cache[cache_indexes[first_cache + 1]];
- lc->dir_cache_id = dir->cache_id;
- lc->node_cache_id = np->cache_id;
- lc->len = len;
- strcpy (lc->name, name);
-
- /* Increment first_cache, and possibly last_cache too. */
- if (last_cache == first_cache)
- last_cache++;
- first_cache++;
-
+ if (lru_cache == 0)
+ /* There should always be an lru_cache; this being zero means that the
+ cache hasn't been initialized yet. Do so. */
+ init_lookup_cache ();
+
+ /* See if there's an old entry for NAME in DIR. If not, replace the least
+ recently used entry. */
+ c = find_cache (dir, name, name_len) ?: lru_cache;
+
+ /* Fill C with the new entry. */
+ c->dir_cache_id = dir->cache_id;
+ c->node_cache_id = np ? np->cache_id : 0;
+ strcpy (c->name, name);
+ c->name_len = name_len;
+
+ /* Now C becomes the MRU entry! */
+ make_mru (c);
+
spin_unlock (&cache_lock);
}
-
+
/* Purge all references in the cache to NP as a node inside
directory DP. */
void
diskfs_purge_lookup_cache (struct node *dp, struct node *np)
{
- int i;
+ struct lookup_cache *c, *next;
spin_lock (&cache_lock);
- for (i = 0; i < MAXCACHE; i++)
- if (lookup_cache[i].len
- && lookup_cache[i].dir_cache_id == dp->cache_id
- && lookup_cache[i].node_cache_id == np->cache_id)
- lookup_cache[i].len = 0;
+ for (c = mru_cache; c; c = next)
+ {
+ /* Save C->next, since we may delete C from this position in the list. */
+ next = c->next;
+
+ if (c->name_len
+ && c->dir_cache_id == dp->cache_id
+ && c->node_cache_id == np->cache_id)
+ {
+ c->name_len = 0;
+ make_lru (c); /* Use C as the next free entry. */
+ }
+ }
spin_unlock (&cache_lock);
}
-
+
/* 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
not exist, then return -1. Otherwise, return NP for the entry, with
@@ -113,37 +223,37 @@ diskfs_purge_lookup_cache (struct node *dp, struct node *np)
struct node *
diskfs_check_lookup_cache (struct node *dir, char *name)
{
- int i;
- size_t len = strlen (name);
-
+ struct lookup_cache *c;
+
spin_lock (&cache_lock);
- /* Maybe we really ought to look up in lru order...who knows. */
-
- for (i = 0; i < MAXCACHE; i++)
- if (lookup_cache[i].len == len
- && lookup_cache[i].dir_cache_id == dir->cache_id
- && lookup_cache[i].name[0] == name[0]
- && !strcmp (lookup_cache[i].name, name))
- {
- int id = lookup_cache[i].node_cache_id;
-
- statistics.pos_hits++;
- spin_unlock (&cache_lock);
-
- if (id == dir->cache_id)
- /* The cached node is the same as DIR. */
- {
- diskfs_nref (dir);
- return dir;
- }
- else
- {
- struct node *np;
- error_t err = diskfs_cached_lookup (id, &np);
- return err ? 0 : np;
- }
- }
+ c = find_cache (dir, name, strlen (name));
+ if (c)
+ {
+ int id = c->node_cache_id;
+
+ make_mru (c); /* Record C as recently used. */
+
+ statistics.pos_hits++;
+ spin_unlock (&cache_lock);
+
+ if (id == 0)
+ /* A negative cache entry. */
+ return (struct node *)-1;
+ else if (id == dir->cache_id)
+ /* The cached node is the same as DIR. */
+ {
+ diskfs_nref (dir);
+ return dir;
+ }
+ else
+ /* Just a normal entry in DIR; get the actual node. */
+ {
+ struct node *np;
+ error_t err = diskfs_cached_lookup (id, &np);
+ return err ? 0 : np;
+ }
+ }
statistics.miss++;
spin_unlock (&cache_lock);