diff options
| -rw-r--r-- | libdiskfs/name-cache.c | 186 |
1 files changed, 77 insertions, 109 deletions
diff --git a/libdiskfs/name-cache.c b/libdiskfs/name-cache.c index 38688777..ecb67e6d 100644 --- a/libdiskfs/name-cache.c +++ b/libdiskfs/name-cache.c @@ -25,26 +25,33 @@ /* Maximum number of names to cache at once */ #define MAXCACHE 256 -/* Current number of names cached */ -static int cache_cur; +/* Maximum length of file name we bother caching */ +#define CACHE_NAME_LEN 100 /* Cache entry */ struct lookup_cache { - struct lookup_cache *next, *prev; - - /* These do not hold references; special code exists to call - purge routines when the nodes lose refs. */ - struct node *dp; /* directory */ - struct node *np; /* node */ - - /* strlen of name member */ - size_t namelen; - char name[0]; + int dir_cache_id, node_cache_id; + + size_t len; /* strlen of name */ + + char name[CACHE_NAME_LEN]; }; -/* Cache itself */ -static struct lookup_cache *lookup_cache_head, *lookup_cache_tail; +/* 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; + +static spin_lock_t cache_lock = SPIN_LOCK_INITIALIZER; /* Buffer to hold statistics */ static struct @@ -52,98 +59,51 @@ static struct long pos_hits; long neg_hits; long miss; + long fetch_errors; } statistics; /* 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_cache (struct node *dir, struct node *np, char *name) +diskfs_enter_lookup_cache (struct node *dir, struct node *np, char *name) { - struct lookup_cache *lc, *tmp = 0; - size_t len = strlen (name) + 1; - - - lc = malloc (sizeof (struct lookup_cache) + len); - lc->dp = dir; - lc->np = np; - lc->namelen = len - 1; - bcopy (name, lc->name, len); - - spin_lock (&diskfs_node_refcnt_lock); - if (cache_cur == MAXCACHE) - { - /* Free the entry at the tail */ - tmp = lookup_cache_tail; - lookup_cache_tail = lookup_cache_tail->prev; - if (lookup_cache_tail) - lookup_cache_tail->next = 0; - else - lookup_cache_head = 0; - } - else - cache_cur++; + size_t len = strlen (name); + struct lookup_cache *lc; - /* Add the new entry at the front */ - lc->next = lookup_cache_head; - lc->prev = 0; - if (lc->next) - lc->next->prev = lc; - lookup_cache_head = lc; - if (!lc->next) - lookup_cache_tail = lc; + if (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); - spin_unlock (&diskfs_node_refcnt_lock); + /* Increment first_cache, and possibly last_cache too. */ + if (last_cache == first_cache) + last_cache++; + first_cache++; - if (tmp) - free (tmp); + spin_unlock (&cache_lock); } /* Purge all references in the cache to NP as a node inside directory DP. */ void -diskfs_purge_cache (struct node *dp, struct node *np) -{ - struct lookup_cache *lc, *nxt; - - spin_lock (&diskfs_node_refcnt_lock); - for (lc = lookup_cache_head; lc; lc = nxt) - if (lc->np == np && lc->dp == dp) - { - if (lc->prev) - lc->prev->next = lc->next; - if (lc->next) - lc->next->prev = lc->prev; - nxt = lc->next; - if (lookup_cache_tail == lc) - lookup_cache_tail = lc->prev; - free (lc); - } - else - nxt = lc->next; - spin_unlock (&diskfs_node_refcnt_lock); -} - -/* Purge all references in the cache to NP, either as a node or as a - directory. diskfs_node_refcnt_lock must be held around this call. */ -void -_diskfs_purge_cache_deletion (struct node *np) +diskfs_purge_lookup_cache (struct node *dp, struct node *np) { - struct lookup_cache *lc, *nxt; + int i; - for (lc = lookup_cache_head; lc; lc = nxt) - if (lc->np == np || lc->dp == np) - { - if (lc->prev) - lc->prev->next = lc->next; - if (lc->next) - lc->next->prev = lc->prev; - nxt = lc->next; - if (lookup_cache_tail == lc) - lookup_cache_tail = lc->prev; - free (lc); - } - else - nxt = lc->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; + spin_unlock (&cache_lock); } /* Scan the cache looking for NAME inside DIR. If we don't know @@ -151,34 +111,42 @@ _diskfs_purge_cache_deletion (struct node *np) not exist, then return -1. Otherwise, return NP for the entry, with a newly allocated reference. */ struct node * -diskfs_check_cache (struct node *dir, char *name) +diskfs_check_lookup_cache (struct node *dir, char *name) { - struct lookup_cache *lc; + int i; size_t len = strlen (name); - - spin_lock (&diskfs_node_refcnt_lock); - for (lc = lookup_cache_head; lc; lc = lc->next) - if (lc->dp == dir - && lc->namelen == len - && lc->name[0] == name[0] - && !strcmp (lc->name, name)) + + 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)) { - if (lc->np) + 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. */ { - lc->np->references++; - statistics.pos_hits++; - spin_unlock (&diskfs_node_refcnt_lock); - return lc->np; + diskfs_nref (dir); + return dir; } else { - statistics.neg_hits++; - spin_unlock (&diskfs_node_refcnt_lock); - return (struct node *) -1; + struct node *np; + error_t err = diskfs_cached_lookup (id, &np); + return err ? 0 : np; } } + statistics.miss++; - spin_unlock (&diskfs_node_refcnt_lock); + spin_unlock (&cache_lock); + return 0; } - |