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

DEFINITIONS
