home *** CD-ROM | disk | FTP | other *** search
/ Il CD di internet / CD.iso / SOURCE / KERNEL-S / V1.0 / LINUX-1.0 / LINUX-1 / linux / fs / ext2 / dcache.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-31  |  7.3 KB  |  339 lines
  1. /*
  2.  *  linux/fs/ext2/dcache.c
  3.  *
  4.  *  Copyright (C) 1992, 1993, 1994  Remy Card (card@masi.ibp.fr)
  5.  *                                  Laboratoire MASI - Institut Blaise Pascal
  6.  *                                  Universite Pierre et Marie Curie (Paris VI)
  7.  *
  8.  */
  9.  
  10. /*
  11.  * dcache.c contains the code that handles the directory cache used by
  12.  * lookup() and readdir()
  13.  */
  14.  
  15. #include <asm/segment.h>
  16.  
  17. #include <linux/fs.h>
  18. #include <linux/ext2_fs.h>
  19. #include <linux/string.h>
  20.  
  21. #ifndef DONT_USE_DCACHE
  22.  
  23. #define DCACHE_NAME_LEN    32
  24.  
  25. struct dir_cache_entry {
  26.     unsigned short dev;
  27.     unsigned long dir;
  28.     unsigned long ino;
  29.     char name[DCACHE_NAME_LEN + 1];
  30.     int len;
  31.     struct dir_cache_entry * queue_prev;
  32.     struct dir_cache_entry * queue_next;
  33.     struct dir_cache_entry * prev;
  34.     struct dir_cache_entry * next;
  35. };
  36.  
  37. static struct dir_cache_entry * first = NULL;
  38. static struct dir_cache_entry * last = NULL;
  39. static struct dir_cache_entry * first_free = NULL;
  40. static int cache_initialized = 0;
  41. #ifdef EXT2FS_DEBUG_CACHE
  42. static int hits = 0;
  43. static int misses = 0;
  44. #endif
  45.  
  46. #define CACHE_SIZE 128
  47.  
  48. static struct dir_cache_entry dcache[CACHE_SIZE];
  49.  
  50. #define HASH_QUEUES 16
  51.  
  52. static struct dir_cache_entry * queue_head[HASH_QUEUES];
  53. static struct dir_cache_entry * queue_tail[HASH_QUEUES];
  54.  
  55. #define hash(dev,dir)    ((dev ^ dir) % HASH_QUEUES)
  56.  
  57. /*
  58.  * Initialize the cache
  59.  */
  60. static void init_cache (void)
  61. {
  62.     int i;
  63.  
  64.     dcache[0].prev = NULL;
  65.     dcache[0].next = &dcache[1];
  66.     dcache[0].queue_next = dcache[0].queue_prev = NULL;
  67.     for (i = 1; i < CACHE_SIZE - 1; i++) {
  68.         dcache[i].prev = &dcache[i - 1];
  69.         dcache[i].next = &dcache[i + 1];
  70.         dcache[i].queue_next = dcache[i].queue_prev = NULL;
  71.     }
  72.     dcache[i].prev = &dcache[i - 1];
  73.     dcache[i].next = NULL;
  74.     dcache[i].queue_next = dcache[i].queue_prev = NULL;
  75.     first_free = &dcache[0];
  76.     for (i = 0; i < HASH_QUEUES; i++)
  77.         queue_tail[i] = queue_head[i] = NULL;
  78.     cache_initialized = 1;
  79. }
  80.  
  81. /*
  82.  * Find a name in the cache
  83.  */
  84. static struct dir_cache_entry * find_name (int queue, unsigned short dev,
  85.                        unsigned long dir,
  86.                        const char * name, int len)
  87. {
  88.     struct dir_cache_entry * p;
  89.  
  90.     for (p = queue_head[queue]; p != NULL && (p->dev != dev ||
  91.          p->dir != dir || p->len != len ||
  92.          strncmp (name, p->name, p->len) != 0);
  93.          p = p->queue_next)
  94.         ;
  95.     return p;
  96. }
  97.  
  98. #ifdef EXT2FS_DEBUG_CACHE
  99. /*
  100.  * List the cache entries for debugging
  101.  */
  102. static void show_cache (const char * func_name)
  103. {
  104.     struct dir_cache_entry * p;
  105.  
  106.     printk ("%s: cache status\n", func_name);
  107.     for (p = first; p != NULL; p = p->next)
  108.         printk ("dev:%04x, dir=%4lu, name=%s\n",
  109.             p->dev, p->dir, p->name);
  110. }
  111. #endif
  112.  
  113. /*
  114.  * Add an entry at the beginning of the cache
  115.  */
  116. static void add_to_cache (struct dir_cache_entry * p)
  117. {
  118.     p->prev = NULL;
  119.     p->next = first;
  120.     if (first)
  121.         first->prev = p;
  122.     if (!last)
  123.         last = p;
  124.     first = p;
  125. }
  126.  
  127. /*
  128.  * Add an entry at the beginning of a queue
  129.  */
  130. static void add_to_queue (int queue, struct dir_cache_entry * p)
  131. {
  132.     p->queue_prev = NULL;
  133.     p->queue_next = queue_head[queue];
  134.     if (queue_head[queue])
  135.         queue_head[queue]->queue_prev = p;
  136.     if (!queue_tail[queue])
  137.         queue_tail[queue] = p;
  138.     queue_head[queue] = p;
  139. }
  140.  
  141. /*
  142.  * Remove an entry from the cache
  143.  */
  144. static void remove_from_cache (struct dir_cache_entry * p)
  145. {
  146.     if (p->prev)
  147.         p->prev->next = p->next;
  148.     else
  149.         first = p->next;
  150.     if (p->next)
  151.         p->next->prev = p->prev;
  152.     else
  153.         last = p->prev;
  154.     p->prev = NULL;
  155.     p->next = NULL;
  156. }
  157.  
  158. /*
  159.  * Remove an entry from a queue
  160.  */
  161. static void remove_from_queue (int queue, struct dir_cache_entry * p)
  162. {
  163.     if (p->queue_prev)
  164.         p->queue_prev->queue_next = p->queue_next;
  165.     else
  166.         queue_head[queue] = p->queue_next;
  167.     if (p->queue_next)
  168.         p->queue_next->queue_prev = p->queue_prev;
  169.     else
  170.         queue_tail[queue] = p->queue_prev;
  171.     p->queue_prev = NULL;
  172.     p->queue_next = NULL;
  173. }
  174.  
  175. /*
  176.  * Invalidate all cache entries on a device (called by put_super() when
  177.  * a file system is unmounted)
  178.  */
  179. void ext2_dcache_invalidate (unsigned short dev)
  180. {
  181.     struct dir_cache_entry * p;
  182.     struct dir_cache_entry * p2;
  183.  
  184.     if (!cache_initialized)
  185.         init_cache ();
  186.     for (p = first; p != NULL; p = p2) {
  187.         p2 = p->next;
  188.         if (p->dev == dev) {
  189.             remove_from_cache (p);
  190.             remove_from_queue (hash (p->dev, p->dir), p);
  191.             p->next = first_free;
  192.             first_free = p;
  193.         }
  194.     }
  195. #ifdef EXT2FS_DEBUG_CACHE
  196.     show_cache ("dcache_invalidate");
  197. #endif
  198. }
  199.  
  200. /*
  201.  * Lookup a directory entry in the cache
  202.  */
  203. unsigned long ext2_dcache_lookup (unsigned short dev, unsigned long dir,
  204.                   const char * name, int len)
  205. {
  206.     char our_name[EXT2_NAME_LEN];
  207.     int queue;
  208.     struct dir_cache_entry * p;
  209.  
  210.     if (!cache_initialized)
  211.         init_cache ();
  212.     if (len > DCACHE_NAME_LEN)
  213.         return 0;
  214.     memcpy (our_name, (char *) name, len);
  215.     our_name[len] = '\0';
  216. #ifdef EXT2FS_DEBUG_CACHE
  217.     printk ("dcache_lookup (%04x, %lu, %s, %d)\n", dev, dir, our_name, len);
  218. #endif
  219.     queue = hash (dev, dir);
  220.     if ((p = find_name (queue, dev, dir, our_name, len))) {
  221.         if (p != first) {
  222.             remove_from_cache (p);
  223.             add_to_cache (p);
  224.         }
  225.         if (p != queue_head[queue]) {
  226.             remove_from_queue (queue, p);
  227.             add_to_queue (queue, p);
  228.         }
  229. #ifdef EXT2FS_DEBUG_CACHE
  230.         hits++;
  231.         printk ("dcache_lookup: %s,hit,inode=%lu,hits=%d,misses=%d\n",
  232.             our_name, p->ino, hits, misses);
  233.         show_cache ("dcache_lookup");
  234. #endif
  235.         return p->ino;
  236.     } else {
  237. #ifdef EXT2FS_DEBUG_CACHE
  238.         misses++;
  239.         printk ("dcache_lookup: %s,miss,hits=%d,misses=%d\n",
  240.             our_name, hits, misses);
  241.         show_cache ("dcache_lookup");
  242. #endif
  243.         return 0;
  244.     }
  245. }
  246.  
  247. /*
  248.  * Add a directory entry to the cache
  249.  *
  250.  * This function is called by ext2_lookup(), ext2_readdir()
  251.  * and the functions which create directory entries
  252.  */
  253. void ext2_dcache_add (unsigned short dev, unsigned long dir, const char * name,
  254.               int len, unsigned long ino)
  255. {
  256.     struct dir_cache_entry * p;
  257.     int queue;
  258.  
  259.     if (!cache_initialized)
  260.         init_cache ();
  261. #ifdef EXT2FS_DEBUG_CACHE
  262.     printk ("dcache_add (%04x, %lu, %s, %d, %lu)\n",
  263.         dev, dir, name, len, ino);
  264. #endif
  265.     if (len > DCACHE_NAME_LEN)
  266.         return;
  267.     queue = hash (dev, dir);
  268.     if ((p = find_name (queue, dev, dir, name, len))) {
  269.         p->dir = dir;
  270.         p->ino = ino;
  271.         if (p != first) {
  272.             remove_from_cache (p);
  273.             add_to_cache (p);
  274.         }
  275.         if (p != queue_head[queue]) {
  276.             remove_from_queue (queue, p);
  277.             add_to_queue (queue, p);
  278.         }
  279.     } else {
  280.         if (first_free) {
  281.             p = first_free;
  282.             first_free = p->next;
  283.         } else {
  284.             if (!last)
  285.                 panic ("dcache_add: last == NULL\n");
  286.             else {
  287.                 p = last;
  288.                 last = p->prev;
  289.                 if (last)
  290.                     last->next = NULL;
  291.                 remove_from_queue (hash (p->dev, p->dir), p);
  292.             }
  293.         }
  294.         p->dev = dev;
  295.         p->dir = dir;
  296.         p->ino = ino;
  297.         strncpy (p->name, name, len);
  298.         p->len = len;
  299.         p->name[len] = '\0';
  300.         add_to_cache (p);
  301.         add_to_queue (queue, p);
  302.     }
  303. #ifdef EXT2FS_DEBUG_CACHE
  304.     show_cache ("dcache_add");
  305. #endif
  306. }
  307.  
  308. /*
  309.  * Remove a directory from the cache
  310.  *
  311.  * This function is called by the functions which remove directory entries
  312.  */
  313. void ext2_dcache_remove (unsigned short dev, unsigned long dir,
  314.              const char * name, int len)
  315. {
  316.     struct dir_cache_entry * p;
  317.     int queue;
  318.  
  319.     if (!cache_initialized)
  320.         init_cache ();
  321. #ifdef EXT2FS_DEBUG_CACHE
  322.     printk ("dcache_remove (%04x, %lu, %s, %d)\n", dev, dir, name, len);
  323. #endif
  324.     if (len > DCACHE_NAME_LEN)
  325.         return;
  326.     queue = hash (dev, dir);
  327.     if ((p = find_name (queue, dev, dir, name, len))) {
  328.         remove_from_cache (p);
  329.         remove_from_queue (queue, p);
  330.         p->next = first_free;
  331.         first_free = p;
  332.     }
  333. #ifdef EXT2FS_DEBUG_CACHE
  334.     show_cache ("dcache_remove");
  335. #endif
  336. }
  337.  
  338. #endif
  339.