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

DEFINITIONS
