root/fs/dcache.c

/* */

DEFINITIONS

1. remove_lru
2. add_lru
3. update_lru
4. namehash
5. remove_hash
6. add_hash
7. find_entry
8. move_to_level2
9. dcache_lookup
10. dcache_add
11. name_cache_init

   1 /*
   2  *  linux/fs/dcache.c
   3  *
   4  *  (C) Copyright 1994 Linus Torvalds
   5  */
   6 
   7 /*
   8  * The directory cache is a "two-level" cache, each level doing LRU on
   9  * its entries.  Adding new entries puts them at the end of the LRU
  10  * queue on the first-level cache, while the second-level cache is
  11  * fed by any cache hits.
  12  *
  13  * The idea is that new additions (from readdir(), for example) will not
  14  * flush the cache of entries that have really been used.
  15  *
  16  * There is a global hash-table over both caches that hashes the entries
  17  * based on the directory inode number and device as well as on a
  18  * string-hash computed over the name. 
  19  */
  20 
  21 #include <stddef.h>
  22 
  23 #include <linux/fs.h>
  24 #include <linux/string.h>
  25 
  26 /*
  27  * Don't bother caching long names.. They just take up space in the cache, and
  28  * for a name cache you just want to cache the "normal" names anyway which tend
  29  * to be short.
  30  */
  31 #define DCACHE_NAME_LEN 15
  32 #define DCACHE_SIZE 128
  33 
  34 struct hash_list {
  35         struct dir_cache_entry * next;
  36         struct dir_cache_entry * prev;
  37 };
  38 
  39 /*
  40  * The dir_cache_entry must be in this order: we do ugly things with the pointers
  41  */
  42 struct dir_cache_entry {
  43         struct hash_list h;
  44         kdev_t dc_dev;
  45         unsigned long dir;
  46         unsigned long version;
  47         unsigned long ino;
  48         unsigned char name_len;
  49         char name[DCACHE_NAME_LEN];
  50         struct dir_cache_entry ** lru_head;
  51         struct dir_cache_entry * next_lru,  * prev_lru;
  52 };
  53 
  54 #define COPYDATA(de, newde) \
  55 memcpy((void *) &newde->dc_dev, (void *) &de->dc_dev, \
  56 sizeof(kdev_t) + 3*sizeof(unsigned long) + 1 + DCACHE_NAME_LEN)
  57 
  58 static struct dir_cache_entry level1_cache[DCACHE_SIZE];
  59 static struct dir_cache_entry level2_cache[DCACHE_SIZE];
  60 
  61 /*
  62  * The LRU-lists are doubly-linked circular lists, and do not change in size
  63  * so these pointers always have something to point to (after _init)
  64  */
  65 static struct dir_cache_entry * level1_head;
  66 static struct dir_cache_entry * level2_head;
  67 
  68 /*
  69  * The hash-queues are also doubly-linked circular lists, but the head is
  70  * itself on the doubly-linked list, not just a pointer to the first entry.
  71  */
  72 #define DCACHE_HASH_QUEUES 19
  73 #define hash_fn(dev,dir,namehash) ((HASHDEV(dev) ^ (dir) ^ (namehash)) % DCACHE_HASH_QUEUES)
  74 
  75 static struct hash_list hash_table[DCACHE_HASH_QUEUES];
  76 
  77 static inline void remove_lru(struct dir_cache_entry * de)
     /*  */
  78 {
  79         de->next_lru->prev_lru = de->prev_lru;
  80         de->prev_lru->next_lru = de->next_lru;
  81 }
  82 
  83 static inline void add_lru(struct dir_cache_entry * de, struct dir_cache_entry *head)
     /*  */
  84 {
  85         de->next_lru = head;
  86         de->prev_lru = head->prev_lru;
  87         de->prev_lru->next_lru = de;
  88         head->prev_lru = de;
  89 }
  90 
  91 static inline void update_lru(struct dir_cache_entry * de)
     /*  */
  92 {
  93         if (de == *de->lru_head)
  94                 *de->lru_head = de->next_lru;
  95         else {
  96                 remove_lru(de);
  97                 add_lru(de,*de->lru_head);
  98         }
  99 }
 100 
 101 /*
 102  * Stupid name"hash" algorithm. Write something better if you want to,
 103  * but I doubt it matters that much
 104  */
 105 static inline unsigned long namehash(const char * name, int len)
     /*  */
 106 {
 107         return len * *(const unsigned char *) name;
 108 }
 109 
 110 /*
 111  * Hash queue manipulation. Look out for the casts..
 112  */
 113 static inline void remove_hash(struct dir_cache_entry * de)
     /*  */
 114 {
 115         if (de->h.next) {
 116                 de->h.next->h.prev = de->h.prev;
 117                 de->h.prev->h.next = de->h.next;
 118                 de->h.next = NULL;
 119         }
 120 }
 121 
 122 static inline void add_hash(struct dir_cache_entry * de, struct hash_list * hash)
     /*  */
 123 {
 124         de->h.next = hash->next;
 125         de->h.prev = (struct dir_cache_entry *) hash;
 126         hash->next->h.prev = de;
 127         hash->next = de;
 128 }
 129 
 130 /*
 131  * Find a directory cache entry given all the necessary info.
 132  */
 133 static struct dir_cache_entry * find_entry(struct inode * dir, const char * name, int len, struct hash_list * hash)
     /*  */
 134 {
 135         struct dir_cache_entry * de = hash->next;
 136 
 137         for (de = hash->next ; de != (struct dir_cache_entry *) hash ; de = de->h.next) {
 138                 if (de->dc_dev != dir->i_dev)
 139                         continue;
 140                 if (de->dir != dir->i_ino)
 141                         continue;
 142                 if (de->version != dir->i_version)
 143                         continue;
 144                 if (de->name_len != len)
 145                         continue;
 146                 if (memcmp(de->name, name, len))
 147                         continue;
 148                 return de;
 149         }
 150         return NULL;
 151 }
 152 
 153 /*
 154  * Move a successfully used entry to level2. If already at level2,
 155  * move it to the end of the LRU queue..
 156  */
 157 static inline void move_to_level2(struct dir_cache_entry * old_de, struct hash_list * hash)
     /*  */
 158 {
 159         struct dir_cache_entry * de;
 160 
 161         if (old_de->lru_head == &level2_head) {
 162                 update_lru(old_de);
 163                 return;
 164         }       
 165         de = level2_head;
 166         level2_head = de->next_lru;
 167         remove_hash(de);
 168         COPYDATA(old_de, de);
 169         add_hash(de, hash);
 170 }
 171 
 172 int dcache_lookup(struct inode * dir, const char * name, int len, unsigned long * ino)
     /*  */
 173 {
 174         struct hash_list * hash;
 175         struct dir_cache_entry *de;
 176 
 177         if (len > DCACHE_NAME_LEN)
 178                 return 0;
 179         hash = hash_table + hash_fn(dir->i_dev, dir->i_ino, namehash(name,len));
 180         de = find_entry(dir, name, len, hash);
 181         if (!de)
 182                 return 0;
 183         *ino = de->ino;
 184         move_to_level2(de, hash);
 185         return 1;
 186 }
 187 
 188 void dcache_add(struct inode * dir, const char * name, int len, unsigned long ino)
     /*  */
 189 {
 190         struct hash_list * hash;
 191         struct dir_cache_entry *de;
 192 
 193         if (len > DCACHE_NAME_LEN)
 194                 return;
 195         hash = hash_table + hash_fn(dir->i_dev, dir->i_ino, namehash(name,len));
 196         if ((de = find_entry(dir, name, len, hash)) != NULL) {
 197                 de->ino = ino;
 198                 update_lru(de);
 199                 return;
 200         }
 201         de = level1_head;
 202         level1_head = de->next_lru;
 203         remove_hash(de);
 204         de->dc_dev = dir->i_dev;
 205         de->dir = dir->i_ino;
 206         de->version = dir->i_version;
 207         de->ino = ino;
 208         de->name_len = len;
 209         memcpy(de->name, name, len);
 210         add_hash(de, hash);
 211 }
 212 
 213 unsigned long name_cache_init(unsigned long mem_start, unsigned long mem_end)
     /*  */
 214 {
 215         int i;
 216         struct dir_cache_entry * p;
 217 
 218         /*
 219          * Init level1 LRU lists..
 220          */
 221         p = level1_cache;
 222         do {
 223                 p[1].prev_lru = p;
 224                 p[0].next_lru = p+1;
 225                 p[0].lru_head = &level1_head;
 226         } while (++p < level1_cache + DCACHE_SIZE-1);
 227         level1_cache[0].prev_lru = p;
 228         p[0].next_lru = &level1_cache[0];
 229         p[0].lru_head = &level1_head;
 230         level1_head = level1_cache;
 231 
 232         /*
 233          * Init level2 LRU lists..
 234          */
 235         p = level2_cache;
 236         do {
 237                 p[1].prev_lru = p;
 238                 p[0].next_lru = p+1;
 239                 p[0].lru_head = &level2_head;
 240         } while (++p < level2_cache + DCACHE_SIZE-1);
 241         level2_cache[0].prev_lru = p;
 242         p[0].next_lru = &level2_cache[0];
 243         p[0].lru_head = &level2_head;
 244         level2_head = level2_cache;
 245 
 246         /*
 247          * Empty hash queues..
 248          */
 249         for (i = 0 ; i < DCACHE_HASH_QUEUES ; i++)
 250                 hash_table[i].next = hash_table[i].next =
 251                         (struct dir_cache_entry *) &hash_table[i];
 252         return mem_start;
 253 }

/* */