Home | History | Annotate | Download | only in fs 
      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 void cache_init(struct device *dev, int block_size_shift)
     19 {
     20     struct cache *prev, *cur;
     21     char *data = dev->cache_data;
     22     struct cache *head, *cache;
     23     int i;
     24 
     25     dev->cache_block_size = 1 << block_size_shift;
     26 
     27     if (dev->cache_size < dev->cache_block_size + 2*sizeof(struct cache)) {
     28 	dev->cache_head = NULL;
     29 	return;			/* Cache unusably small */
     30     }
     31 
     32     /* We need one struct cache for the headnode plus one for each block */
     33     dev->cache_entries =
     34 	(dev->cache_size - sizeof(struct cache))/
     35 	(dev->cache_block_size + sizeof(struct cache));
     36 
     37     dev->cache_head = head = (struct cache *)
     38 	(data + (dev->cache_entries << block_size_shift));
     39     cache = head + 1;		/* First cache descriptor */
     40 
     41     head->prev  = &cache[dev->cache_entries-1];
     42     head->prev->next = head;
     43     head->block = -1;
     44     head->data  = NULL;
     45 
     46     prev = head;
     47 
     48     for (i = 0; i < dev->cache_entries; i++) {
     49         cur = &cache[i];
     50         cur->data  = data;
     51         cur->block = -1;
     52         cur->prev  = prev;
     53         prev->next = cur;
     54         data += dev->cache_block_size;
     55         prev = cur++;
     56     }
     57 
     58     dev->cache_init = 1; /* Set cache as initialized */
     59 }
     60 
     61 /*
     62  * Lock a block permanently in the cache by removing it
     63  * from the LRU chain.
     64  */
     65 void cache_lock_block(struct cache *cs)
     66 {
     67     cs->prev->next = cs->next;
     68     cs->next->prev = cs->prev;
     69 
     70     cs->next = cs->prev = NULL;
     71 }
     72 
     73 /*
     74  * Check for a particular BLOCK in the block cache,
     75  * and if it is already there, just do nothing and return;
     76  * otherwise pick a victim block and update the LRU link.
     77  */
     78 struct cache *_get_cache_block(struct device *dev, block_t block)
     79 {
     80     struct cache *head = dev->cache_head;
     81     struct cache *cs;
     82     int i;
     83 
     84     cs = dev->cache_head + 1;
     85 
     86     for (i = 0; i < dev->cache_entries; i++) {
     87 	if (cs->block == block)
     88 	    goto found;
     89 	cs++;
     90     }
     91 
     92     /* Not found, pick a victim */
     93     cs = head->next;
     94 
     95 found:
     96     /* Move to the end of the LRU chain, unless the block is already locked */
     97     if (cs->next) {
     98 	cs->prev->next = cs->next;
     99 	cs->next->prev = cs->prev;
    100 
    101 	cs->prev = head->prev;
    102 	head->prev->next = cs;
    103 	cs->next = head;
    104 	head->prev = cs;
    105     }
    106 
    107     return cs;
    108 }
    109 
    110 /*
    111  * Check for a particular BLOCK in the block cache,
    112  * and if it is already there, just do nothing and return;
    113  * otherwise load it from disk and update the LRU link.
    114  * Return the data pointer.
    115  */
    116 const void *get_cache(struct device *dev, block_t block)
    117 {
    118     struct cache *cs;
    119 
    120     cs = _get_cache_block(dev, block);
    121     if (cs->block != block) {
    122 	cs->block = block;
    123         getoneblk(dev->disk, cs->data, block, dev->cache_block_size);
    124     }
    125 
    126     return cs->data;
    127 }
    128 
    129 /*
    130  * Read data from the cache at an arbitrary byte offset and length.
    131  * This is useful for filesystems whose metadata is not necessarily
    132  * aligned with their blocks.
    133  *
    134  * This is still reading linearly on the disk.
    135  */
    136 size_t cache_read(struct fs_info *fs, void *buf, uint64_t offset, size_t count)
    137 {
    138     const char *cd;
    139     char *p = buf;
    140     size_t off, cnt, total;
    141     block_t block;
    142 
    143     total = count;
    144     while (count) {
    145 	block = offset >> fs->block_shift;
    146 	off = offset & (fs->block_size - 1);
    147 	cd = get_cache(fs->fs_dev, block);
    148 	if (!cd)
    149 	    break;
    150 	cnt = fs->block_size - off;
    151 	if (cnt > count)
    152 	    cnt = count;
    153 	memcpy(p, cd + off, cnt);
    154 	count -= cnt;
    155 	p += cnt;
    156 	offset += cnt;
    157     }
    158     return total - count;
    159 }
    160