(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.

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);