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 <linux/fs.h>
  22 #include <linux/string.h>
  23 
  24 /*
  25  * Don't bother caching long names.. They just take up space in the cache, and
  26  * for a name cache you just want to cache the "normal" names anyway which tend
  27  * to be short.
  28  */
  29 #define DCACHE_NAME_LEN 15
  30 #define DCACHE_SIZE 128
  31 
  32 struct hash_list {
  33         struct dir_cache_entry * next;
  34         struct dir_cache_entry * prev;
  35 };
  36 
  37 /*
  38  * The dir_cache_entry must be in this order: we do ugly things with the pointers
  39  */
  40 struct dir_cache_entry {
  41         struct hash_list h;
  42         kdev_t dc_dev;
  43         unsigned long dir;
  44         unsigned long version;
  45         unsigned long ino;
  46         unsigned char name_len;
  47         char name[DCACHE_NAME_LEN];
  48         struct dir_cache_entry ** lru_head;
  49         struct dir_cache_entry * next_lru,  * prev_lru;
  50 };
  51 
  52 #define dcache_offset(x) ((unsigned long)&((struct dir_cache_entry*)0)->x)
  53 #define dcache_datalen (dcache_offset(lru_head) - dcache_offset(dc_dev))
  54 
  55 #define COPYDATA(de, newde) \
  56 memcpy((void *) &newde->dc_dev, (void *) &de->dc_dev, dcache_datalen)
  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 32
  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         struct dir_cache_entry * next = de->next_lru;
  80         struct dir_cache_entry * prev = de->prev_lru;
  81 
  82         next->prev_lru = prev;
  83         prev->next_lru = next;
  84 }
  85 
  86 static inline void add_lru(struct dir_cache_entry * de, struct dir_cache_entry *head)
     /*  */
  87 {
  88         struct dir_cache_entry * prev = head->prev_lru;
  89 
  90         de->next_lru = head;
  91         de->prev_lru = prev;
  92         prev->next_lru = de;
  93         head->prev_lru = de;
  94 }
  95 
  96 static inline void update_lru(struct dir_cache_entry * de)
     /*  */
  97 {
  98         if (de == *de->lru_head)
  99                 *de->lru_head = de->next_lru;
 100         else {
 101                 remove_lru(de);
 102                 add_lru(de,*de->lru_head);
 103         }
 104 }
 105 
 106 /*
 107  * Stupid name"hash" algorithm. Write something better if you want to,
 108  * but I doubt it matters that much
 109  */
 110 static inline unsigned long namehash(const char * name, int len)
     /*  */
 111 {
 112         return len +
 113                 ((const unsigned char *) name)[0]+
 114                 ((const unsigned char *) name)[len-1];
 115 }
 116 
 117 /*
 118  * Hash queue manipulation. Look out for the casts..
 119  */
 120 static inline void remove_hash(struct dir_cache_entry * de)
     /*  */
 121 {
 122         struct dir_cache_entry * next = de->h.next;
 123 
 124         if (next) {
 125                 struct dir_cache_entry * prev = de->h.prev;
 126                 next->h.prev = prev;
 127                 prev->h.next = next;
 128                 de->h.next = NULL;
 129         }
 130 }
 131 
 132 static inline void add_hash(struct dir_cache_entry * de, struct hash_list * hash)
     /*  */
 133 {
 134         struct dir_cache_entry * next = hash->next;
 135         de->h.next = next;
 136         de->h.prev = (struct dir_cache_entry *) hash;
 137         next->h.prev = de;
 138         hash->next = de;
 139 }
 140 
 141 /*
 142  * Find a directory cache entry given all the necessary info.
 143  */
 144 static inline struct dir_cache_entry * find_entry(struct inode * dir, const char * name, int len, struct hash_list * hash)
     /*  */
 145 {
 146         struct dir_cache_entry * de = hash->next;
 147 
 148         for (de = hash->next ; de != (struct dir_cache_entry *) hash ; de = de->h.next) {
 149                 if (de->dc_dev != dir->i_dev)
 150                         continue;
 151                 if (de->dir != dir->i_ino)
 152                         continue;
 153                 if (de->version != dir->i_version)
 154                         continue;
 155                 if (de->name_len != len)
 156                         continue;
 157                 if (memcmp(de->name, name, len))
 158                         continue;
 159                 return de;
 160         }
 161         return NULL;
 162 }
 163 
 164 /*
 165  * Move a successfully used entry to level2. If already at level2,
 166  * move it to the end of the LRU queue..
 167  */
 168 static inline void move_to_level2(struct dir_cache_entry * old_de, struct hash_list * hash)
     /*  */
 169 {
 170         struct dir_cache_entry * de;
 171 
 172         if (old_de->lru_head == &level2_head) {
 173                 update_lru(old_de);
 174                 return;
 175         }       
 176         de = level2_head;
 177         level2_head = de->next_lru;
 178         remove_hash(de);
 179         COPYDATA(old_de, de);
 180         add_hash(de, hash);
 181 }
 182 
 183 int dcache_lookup(struct inode * dir, const char * name, int len, unsigned long * ino)
     /*  */
 184 {
 185         struct hash_list * hash;
 186         struct dir_cache_entry *de;
 187 
 188         if (len > DCACHE_NAME_LEN)
 189                 return 0;
 190         hash = hash_table + hash_fn(dir->i_dev, dir->i_ino, namehash(name,len));
 191         de = find_entry(dir, name, len, hash);
 192         if (!de)
 193                 return 0;
 194         *ino = de->ino;
 195         move_to_level2(de, hash);
 196         return 1;
 197 }
 198 
 199 void dcache_add(struct inode * dir, const char * name, int len, unsigned long ino)
     /*  */
 200 {
 201         struct hash_list * hash;
 202         struct dir_cache_entry *de;
 203 
 204         if (len > DCACHE_NAME_LEN)
 205                 return;
 206         hash = hash_table + hash_fn(dir->i_dev, dir->i_ino, namehash(name,len));
 207         if ((de = find_entry(dir, name, len, hash)) != NULL) {
 208                 de->ino = ino;
 209                 update_lru(de);
 210                 return;
 211         }
 212         de = level1_head;
 213         level1_head = de->next_lru;
 214         remove_hash(de);
 215         de->dc_dev = dir->i_dev;
 216         de->dir = dir->i_ino;
 217         de->version = dir->i_version;
 218         de->ino = ino;
 219         de->name_len = len;
 220         memcpy(de->name, name, len);
 221         add_hash(de, hash);
 222 }
 223 
 224 unsigned long name_cache_init(unsigned long mem_start, unsigned long mem_end)
     /*  */
 225 {
 226         int i;
 227         struct dir_cache_entry * p;
 228 
 229         /*
 230          * Init level1 LRU lists..
 231          */
 232         p = level1_cache;
 233         do {
 234                 p[1].prev_lru = p;
 235                 p[0].next_lru = p+1;
 236                 p[0].lru_head = &level1_head;
 237         } while (++p < level1_cache + DCACHE_SIZE-1);
 238         level1_cache[0].prev_lru = p;
 239         p[0].next_lru = &level1_cache[0];
 240         p[0].lru_head = &level1_head;
 241         level1_head = level1_cache;
 242 
 243         /*
 244          * Init level2 LRU lists..
 245          */
 246         p = level2_cache;
 247         do {
 248                 p[1].prev_lru = p;
 249                 p[0].next_lru = p+1;
 250                 p[0].lru_head = &level2_head;
 251         } while (++p < level2_cache + DCACHE_SIZE-1);
 252         level2_cache[0].prev_lru = p;
 253         p[0].next_lru = &level2_cache[0];
 254         p[0].lru_head = &level2_head;
 255         level2_head = level2_cache;
 256 
 257         /*
 258          * Empty hash queues..
 259          */
 260         for (i = 0 ; i < DCACHE_HASH_QUEUES ; i++)
 261                 hash_table[i].next = hash_table[i].next =
 262                         (struct dir_cache_entry *) &hash_table[i];
 263         return mem_start;
 264 }

/* */