home *** CD-ROM | disk | FTP | other *** search
/ Il CD di internet / CD.iso / SOURCE / KERNEL-S / V1.2 / LINUX-1.2 / LINUX-1 / linux / fs / dcache.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-12-28  |  6.1 KB  |  254 lines
  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.     unsigned long 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->dev, (void *) &de->dev, \
  56. 4*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) (((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 * *(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->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->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. }
  254.