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

DEFINITIONS
