core/fs/cache.c

   1 /*
   2  * core/cache.c: A simple LRU-based cache implementation.
   3  *
   4  */
   5
   6 #include <stdio.h>
   7 #include <string.h>
   8 #include <dprintf.h>
   9 #include "core.h"
  10 #include "cache.h"
  11
  12
  13 /*
  14  * Initialize the cache data structres. the _block_size_shift_ specify
  15  * the block size, which is 512 byte for FAT fs of the current
  16  * implementation since the block(cluster) size in FAT is a bit big.
  17  *
  18  */
  19 void cache_init(struct device *dev, int block_size_shift)
  20 {
  21     struct cache *prev, *cur;
  22     char *data = dev->cache_data;
  23     struct cache *head, *cache;
  24     int i;
  25
  26     dev->cache_block_size = 1 << block_size_shift;
  27
  28     if (dev->cache_size < dev->cache_block_size + 2*sizeof(struct cache)) {
  29         dev->cache_head = NULL;
  30         return;                 /* Cache unusably small */
  31     }
  32
  33     /* We need one struct cache for the headnode plus one for each block */
  34     dev->cache_entries =
  35         (dev->cache_size - sizeof(struct cache))/
  36         (dev->cache_block_size + sizeof(struct cache));
  37
  38     dev->cache_head = head = (struct cache *)
  39         (data + (dev->cache_entries << block_size_shift));
  40     cache = dev->cache_head + 1; /* First cache descriptor */
  41
  42     head->prev  = &cache[dev->cache_entries-1];
  43     head->next->prev = dev->cache_head;
  44     head->block = -1;
  45     head->data  = NULL;
  46
  47     prev = head;
  48
  49     for (i = 0; i < dev->cache_entries; i++) {
  50         cur = &cache[i];
  51         cur->data  = data;
  52         cur->block = -1;
  53         cur->prev  = prev;
  54         prev->next = cur;
  55         data += dev->cache_block_size;
  56         prev = cur++;
  57     }
  58 }
  59
  60 /*
  61  * Lock a block permanently in the cache
  62  */
  63 void cache_lock_block(struct cache *cs)
  64 {
  65     cs->prev->next = cs->next;
  66     cs->next->prev = cs->prev;
  67
  68     cs->next = cs->prev = NULL;
  69 }
  70
  71 /*
  72  * Check for a particular BLOCK in the block cache,
  73  * and if it is already there, just do nothing and return;
  74  * otherwise pick a victim block and update the LRU link.
  75  */
  76 struct cache *_get_cache_block(struct device *dev, block_t block)
  77 {
  78     struct cache *head = dev->cache_head;
  79     struct cache *cs;
  80     int i;
  81
  82     cs = dev->cache_head + 1;
  83
  84     for (i = 0; i < dev->cache_entries; i++) {
  85         if (cs->block == block)
  86             goto found;
  87         cs++;
  88     }
  89
  90     /* Not found, pick a victim */
  91     cs = head->next;
  92
  93 found:
  94     /* Move to the end of the LRU chain, unless the block is already locked */
  95     if (cs->next) {
  96         cs->prev->next = cs->next;
  97         cs->next->prev = cs->prev;
  98
  99         cs->prev = head->prev;
 100         head->prev->next = cs;
 101         cs->next = head;
 102         head->prev = cs;
 103     }
 104
 105     return cs;
 106 }
 107
 108 /*
 109  * Check for a particular BLOCK in the block cache,
 110  * and if it is already there, just do nothing and return;
 111  * otherwise load it from disk and update the LRU link.
 112  * Return the data pointer.
 113  */
 114 const void *get_cache(struct device *dev, block_t block)
 115 {
 116     struct cache *cs;
 117
 118     cs = _get_cache_block(dev, block);
 119     if (cs->block != block) {
 120         cs->block = block;
 121         getoneblk(dev->disk, cs->data, block, dev->cache_block_size);
 122     }
 123
 124     return cs->data;
 125 }