fs/ext2/dcache.c

/* */
This source file includes following definitions.
init_cache
find_name
show_cache
add_to_cache
add_to_queue
remove_from_cache
remove_from_queue
ext2_dcache_invalidate
ext2_dcache_lookup
ext2_dcache_add
ext2_dcache_remove
   1 /*
   2  *  linux/fs/ext2/dcache.c
   3  *
   4  *  Copyright (C) 1992, 1993  Remy Card (card@masi.ibp.fr)
   5  *
   6  */
   7 
   8 /*
   9  * dcache.c contains the code that handles the directory cache used by
  10  * lookup() and readdir()
  11  */
  12 
  13 #include <asm/segment.h>
  14 
  15 #include <linux/fs.h>
  16 #include <linux/ext2_fs.h>
  17 #include <linux/kernel.h>
  18 #include <linux/string.h>
  19 
  20 #ifndef DONT_USE_DCACHE
  21 
  22 #define DCACHE_NAME_LEN 32
  23 
  24 struct dir_cache_entry {
  25         unsigned short dev;
  26         unsigned long dir;
  27         unsigned long ino;
  28         char name[DCACHE_NAME_LEN + 1];
  29         int len;
  30         struct dir_cache_entry * queue_prev;
  31         struct dir_cache_entry * queue_next;
  32         struct dir_cache_entry * prev;
  33         struct dir_cache_entry * next;
  34 };
  35 
  36 static struct dir_cache_entry * first = NULL;
  37 static struct dir_cache_entry * last = NULL;
  38 static struct dir_cache_entry * first_free = NULL;
  39 static int cache_initialized = 0;
  40 #ifdef EXT2FS_DEBUG_CACHE
  41 static int hits = 0;
  42 static int misses = 0;
  43 #endif
  44 
  45 #define CACHE_SIZE 128
  46 
  47 static struct dir_cache_entry dcache[CACHE_SIZE];
  48 
  49 #define HASH_QUEUES 16
  50 
  51 static struct dir_cache_entry * queue_head[HASH_QUEUES];
  52 static struct dir_cache_entry * queue_tail[HASH_QUEUES];
  53 
  54 #define hash(dev,dir)   ((dev ^ dir) % HASH_QUEUES)
  55 
  56 /*
  57  * Initialize the cache
  58  */
  59 static void init_cache (void)
     /*  */
  60 {
  61         int i;
  62 
  63         dcache[0].prev = NULL;
  64         dcache[0].next = &dcache[1];
  65         dcache[0].queue_next = dcache[0].queue_prev = NULL;
  66         for (i = 1; i < CACHE_SIZE - 1; i++) {
  67                 dcache[i].prev = &dcache[i - 1];
  68                 dcache[i].next = &dcache[i + 1];
  69                 dcache[i].queue_next = dcache[i].queue_prev = NULL;
  70         }
  71         dcache[i].prev = &dcache[i - 1];
  72         dcache[i].next = NULL;
  73         dcache[i].queue_next = dcache[i].queue_prev = NULL;
  74         first_free = &dcache[0];
  75         for (i = 0; i < HASH_QUEUES; i++)
  76                 queue_tail[i] = queue_head[i] = NULL;
  77         cache_initialized = 1;
  78 }
  79 
  80 /*
  81  * Find a name in the cache
  82  */
  83 static struct dir_cache_entry * find_name (int queue, unsigned short dev,
     /*  */
  84                                            unsigned long dir,
  85                                            const char * name, int len)
  86 {
  87         struct dir_cache_entry * p;
  88 
  89         for (p = queue_head[queue]; p != NULL && (p->dev != dev ||
  90              p->dir != dir || p->len != len ||
  91              strncmp (name, p->name, p->len) != 0);
  92              p = p->queue_next)
  93                 ;
  94         return p;
  95 }
  96 
  97 #ifdef EXT2FS_DEBUG_CACHE
  98 /*
  99  * List the cache entries for debugging
 100  */
 101 static void show_cache (const char * func_name)
     /*  */
 102 {
 103         struct dir_cache_entry * p;
 104 
 105         printk ("%s: cache status\n", func_name);
 106         for (p = first; p != NULL; p = p->next)
 107                 printk ("dev:%04x, dir=%4lu, name=%s\n",
 108                         p->dev, p->dir, p->name);
 109 }
 110 #endif
 111 
 112 /*
 113  * Add an entry at the beginning of the cache
 114  */
 115 static void add_to_cache (struct dir_cache_entry * p)
     /*  */
 116 {
 117         p->prev = NULL;
 118         p->next = first;
 119         if (first)
 120                 first->prev = p;
 121         if (!last)
 122                 last = p;
 123         first = p;
 124 }
 125 
 126 /*
 127  * Add an entry at the beginning of a queue
 128  */
 129 static void add_to_queue (int queue, struct dir_cache_entry * p)
     /*  */
 130 {
 131         p->queue_prev = NULL;
 132         p->queue_next = queue_head[queue];
 133         if (queue_head[queue])
 134                 queue_head[queue]->queue_prev = p;
 135         if (!queue_tail[queue])
 136                 queue_tail[queue] = p;
 137         queue_head[queue] = p;
 138 }
 139 
 140 /*
 141  * Remove an entry from the cache
 142  */
 143 static void remove_from_cache (struct dir_cache_entry * p)
     /*  */
 144 {
 145         if (p->prev)
 146                 p->prev->next = p->next;
 147         else
 148                 first = p->next;
 149         if (p->next)
 150                 p->next->prev = p->prev;
 151         else
 152                 last = p->prev;
 153         p->prev = NULL;
 154         p->next = NULL;
 155 }
 156 
 157 /*
 158  * Remove an entry from a queue
 159  */
 160 static void remove_from_queue (int queue, struct dir_cache_entry * p)
     /*  */
 161 {
 162         if (p->queue_prev)
 163                 p->queue_prev->queue_next = p->queue_next;
 164         else
 165                 queue_head[queue] = p->queue_next;
 166         if (p->queue_next)
 167                 p->queue_next->queue_prev = p->queue_prev;
 168         else
 169                 queue_tail[queue] = p->queue_prev;
 170         p->queue_prev = NULL;
 171         p->queue_next = NULL;
 172 }
 173 
 174 /*
 175  * Invalidate all cache entries on a device (called by put_super() when
 176  * a file system is unmounted)
 177  */
 178 void ext2_dcache_invalidate (unsigned short dev)
     /*  */
 179 {
 180         struct dir_cache_entry * p;
 181         struct dir_cache_entry * p2;
 182 
 183         if (!cache_initialized)
 184                 init_cache ();
 185         for (p = first; p != NULL; p = p2) {
 186                 p2 = p->next;
 187                 if (p->dev == dev) {
 188                         remove_from_cache (p);
 189                         remove_from_queue (hash (p->dev, p->dir), p);
 190                         p->next = first_free;
 191                         first_free = p;
 192                 }
 193         }
 194 #ifdef EXT2FS_DEBUG_CACHE
 195         show_cache ("dcache_invalidate");
 196 #endif
 197 }
 198 
 199 /*
 200  * Lookup a directory entry in the cache
 201  */
 202 unsigned long ext2_dcache_lookup (unsigned short dev, unsigned long dir,
     /*  */
 203                                   const char * name, int len)
 204 {
 205         char our_name[EXT2_NAME_LEN];
 206         int queue;
 207         struct dir_cache_entry * p;
 208 
 209         if (!cache_initialized)
 210                 init_cache ();
 211         if (len > DCACHE_NAME_LEN)
 212                 return 0;
 213         memcpy (our_name, (char *) name, len);
 214         our_name[len] = '\0';
 215 #ifdef EXT2FS_DEBUG_CACHE
 216         printk ("dcache_lookup (%04x, %lu, %s, %d)\n", dev, dir, our_name, len);
 217 #endif
 218         queue = hash (dev, dir);
 219         if ((p = find_name (queue, dev, dir, our_name, len))) {
 220                 if (p != first) {
 221                         remove_from_cache (p);
 222                         add_to_cache (p);
 223                 }
 224                 if (p != queue_head[queue]) {
 225                         remove_from_queue (queue, p);
 226                         add_to_queue (queue, p);
 227                 }
 228 #ifdef EXT2FS_DEBUG_CACHE
 229                 hits++;
 230                 printk ("dcache_lookup: %s,hit,inode=%lu,hits=%d,misses=%d\n",
 231                         our_name, p->ino, hits, misses);
 232                 show_cache ("dcache_lookup");
 233 #endif
 234                 return p->ino;
 235         } else {
 236 #ifdef EXT2FS_DEBUG_CACHE
 237                 misses++;
 238                 printk ("dcache_lookup: %s,miss,hits=%d,misses=%d\n",
 239                         our_name, hits, misses);
 240                 show_cache ("dcache_lookup");
 241 #endif
 242                 return 0;
 243         }
 244 }
 245 
 246 /*
 247  * Add a directory entry to the cache
 248  *
 249  * This function is called by ext2_lookup(), ext2_readdir()
 250  * and the functions which create directory entries
 251  */
 252 void ext2_dcache_add (unsigned short dev, unsigned long dir, const char * name,
     /*  */
 253                       int len, unsigned long ino)
 254 {
 255         struct dir_cache_entry * p;
 256         int queue;
 257 
 258         if (!cache_initialized)
 259                 init_cache ();
 260 #ifdef EXT2FS_DEBUG_CACHE
 261         printk ("dcache_add (%04x, %lu, %s, %d, %lu)\n",
 262                 dev, dir, name, len, ino);
 263 #endif
 264         if (len > DCACHE_NAME_LEN)
 265                 return;
 266         queue = hash (dev, dir);
 267         if ((p = find_name (queue, dev, dir, name, len))) {
 268                 p->dir = dir;
 269                 p->ino = ino;
 270                 if (p != first) {
 271                         remove_from_cache (p);
 272                         add_to_cache (p);
 273                 }
 274                 if (p != queue_head[queue]) {
 275                         remove_from_queue (queue, p);
 276                         add_to_queue (queue, p);
 277                 }
 278         } else {
 279                 if (first_free) {
 280                         p = first_free;
 281                         first_free = p->next;
 282                 } else {
 283                         if (!last)
 284                                 panic ("dcache_add: last == NULL\n");
 285                         else {
 286                                 p = last;
 287                                 last = p->prev;
 288                                 if (last)
 289                                         last->next = NULL;
 290                                 remove_from_queue (hash (p->dev, p->dir), p);
 291                         }
 292                 }
 293                 p->dev = dev;
 294                 p->dir = dir;
 295                 p->ino = ino;
 296                 strncpy (p->name, name, len);
 297                 p->len = len;
 298                 p->name[len] = '\0';
 299                 add_to_cache (p);
 300                 add_to_queue (queue, p);
 301         }
 302 #ifdef EXT2FS_DEBUG_CACHE
 303         show_cache ("dcache_add");
 304 #endif
 305 }
 306 
 307 /*
 308  * Remove a directory from the cache
 309  *
 310  * This function is called by the functions which remove directory entries
 311  */
 312 void ext2_dcache_remove (unsigned short dev, unsigned long dir,
     /*  */
 313                          const char * name, int len)
 314 {
 315         struct dir_cache_entry * p;
 316         int queue;
 317 
 318         if (!cache_initialized)
 319                 init_cache ();
 320 #ifdef EXT2FS_DEBUG_CACHE
 321         printk ("dcache_remove (%04x, %lu, %s, %d)\n", dev, dir, name, len);
 322 #endif
 323         if (len > DCACHE_NAME_LEN)
 324                 return;
 325         queue = hash (dev, dir);
 326         if ((p = find_name (queue, dev, dir, name, len))) {
 327                 remove_from_cache (p);
 328                 remove_from_queue (queue, p);
 329                 p->next = first_free;
 330                 first_free = p;
 331         }
 332 #ifdef EXT2FS_DEBUG_CACHE
 333         show_cache ("dcache_remove");
 334 #endif
 335 }
 336 
 337 #endif
/* */
root/fs/ext2/dcache.c

DEFINITIONS
