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  * Note: the name is in the caller's address space
 196  */
 197 unsigned long ext2_dcache_lookup (unsigned short dev, unsigned long dir,
     /*  */
 198                                   const char *name, int len)
 199 {
 200         char our_name[EXT2_NAME_LEN];
 201         int queue;
 202         struct dir_cache_entry *p;
 203 
 204         if (!cache_initialized)
 205                 init_cache ();
 206         if (len > EXT2_NAME_LEN)
 207                 len = EXT2_NAME_LEN;
 208         memcpy (our_name, (char *) name, len);
 209         our_name[len] = '\0';
 210 #ifdef EXT2FS_DEBUG_CACHE
 211         printk ("dcache_lookup (%04x, %d, %s, %d)\n", dev, dir, our_name, len);
 212 #endif
 213         queue = hash(dev, dir);
 214         if ((p = find_name (queue, dev, dir, our_name, len))) {
 215                 if (p != first) {
 216                         remove_from_cache (p);
 217                         add_to_cache (p);
 218                 }
 219                 if (p != queue_head[queue]) {
 220                         remove_from_queue (queue, p);
 221                         add_to_queue (queue, p);
 222                 }
 223 #ifdef EXT2FS_DEBUG_CACHE
 224                 hits ++;
 225                 printk ("dcache_lookup: %s,hit,inode=%d,hits=%d,misses=%d\n",
 226                         our_name, p->ino, hits, misses);
 227                 show_cache ("dcache_lookup");
 228 #endif
 229                 return p->ino;
 230         } else {
 231 #ifdef EXT2FS_DEBUG_CACHE
 232                 misses ++;
 233                 printk ("dcache_lookup: %s,miss,hits=%d,misses=%d\n",
 234                         our_name, hits, misses);
 235                 show_cache ("dcache_lookup");
 236 #endif
 237                 return 0;
 238         }
 239 }
 240 
 241 /*
 242  * Add a directory entry to the cache
 243  *
 244  * This function is called by ext2_lookup(), ext2_readdir()
 245  * and the functions which create directory entries
 246  *
 247  * Note: the name is in the kernel address space
 248  */
 249 void ext2_dcache_add (unsigned short dev, unsigned long dir, const char *name,
     /*  */
 250                       int len, int ino)
 251 {
 252         struct dir_cache_entry *p;
 253         int queue;
 254 
 255         if (!cache_initialized)
 256                 init_cache ();
 257 #ifdef EXT2FS_DEBUG_CACHE
 258         printk ("dcache_add (%04x, %d, %s, %d, %d)\n",
 259                 dev, dir, name, len, ino);
 260 #endif
 261         if (len > EXT2_NAME_LEN)
 262                 len = EXT2_NAME_LEN;
 263         queue = hash(dev, dir);
 264         if ((p = find_name (queue, dev, dir, name, len))) {
 265                 p->dir = dir;
 266                 p->ino = ino;
 267                 if (p != first) {
 268                         remove_from_cache (p);
 269                         add_to_cache (p);
 270                 }
 271                 if (p != queue_head[queue]) {
 272                         remove_from_queue (queue, p);
 273                         add_to_queue (queue, p);
 274                 }
 275         } else {
 276                 if (first_free) {
 277                         p = first_free;
 278                         first_free = p->next;
 279                 } else {
 280                         if (!last)
 281                                 panic ("dcache_add: last == NULL\n");
 282                         else {
 283                                 p = last;
 284                                 last = p->prev;
 285                                 if (last)
 286                                         last->next = NULL;
 287                                 remove_from_queue (hash (p->dev, p->dir), p);
 288                         }
 289                 }
 290                 p->dev = dev;
 291                 p->dir = dir;
 292                 p->ino = ino;
 293                 strncpy (p->name, name, len);
 294                 p->len = len;
 295                 p->name[len] = '\0';
 296                 add_to_cache (p);
 297                 add_to_queue (queue, p);
 298         }
 299 #ifdef EXT2FS_DEBUG_CACHE
 300         show_cache ("dcache_add");
 301 #endif
 302 }
 303 
 304 /*
 305  * Remove a directory from the cache
 306  *
 307  * This function is called by the functions which remove directory entries
 308  *
 309  * Note: the name is in the kernel address space
 310  */
 311 void ext2_dcache_remove (unsigned short dev, unsigned long dir,
     /*  */
 312                          const char *name, int len)
 313 {
 314         struct dir_cache_entry *p;
 315         int queue;
 316 
 317         if (!cache_initialized)
 318                 init_cache ();
 319 #ifdef EXT2FS_DEBUG_CACHE
 320         printk ("dcache_remove (%04x, %d, %s, %d)\n", dev, dir, name, len);
 321 #endif
 322         if (len > EXT2_NAME_LEN)
 323                 len = EXT2_NAME_LEN;
 324         queue = hash(dev, dir);
 325         if ((p = find_name (queue, dev, dir, name, len))) {
 326                 remove_from_cache (p);
 327                 remove_from_queue (queue, p);
 328                 p->next = first_free;
 329                 first_free = p;
 330         }
 331 #ifdef EXT2FS_DEBUG_CACHE
 332         show_cache ("dcache_remove");
 333 #endif
 334 }
 335 
 336 #endif
/* */
root/fs/ext2/dcache.c

DEFINITIONS
