core/fs/cache.c

/*
 * core/cache.c: A simple LRU-based cache implementation.
 *
 */

#include <stdio.h>
#include <string.h>
#include <dprintf.h>
#include "core.h"
#include "cache.h"


/*
 * Initialize the cache data structres. the _block_size_shift_ specify
 * the block size, which is 512 byte for FAT fs of the current 
 * implementation since the block(cluster) size in FAT is a bit big.
 */
void cache_init(struct device *dev, int block_size_shift)
{
    struct cache *prev, *cur;
    char *data = dev->cache_data;
    struct cache *head, *cache;
    int i;

    dev->cache_block_size = 1 << block_size_shift;

    if (dev->cache_size < dev->cache_block_size + 2*sizeof(struct cache)) {
	dev->cache_head = NULL;
	return;			/* Cache unusably small */
    }

    /* We need one struct cache for the headnode plus one for each block */
    dev->cache_entries =
	(dev->cache_size - sizeof(struct cache))/
	(dev->cache_block_size + sizeof(struct cache));

    dev->cache_head = head = (struct cache *)
	(data + (dev->cache_entries << block_size_shift));
    cache = head + 1;		/* First cache descriptor */

    head->prev  = &cache[dev->cache_entries-1];
    head->prev->next = head;
    head->block = -1;
    head->data  = NULL;

    prev = head;
    
    for (i = 0; i < dev->cache_entries; i++) {
        cur = &cache[i];
        cur->data  = data;
        cur->block = -1;
        cur->prev  = prev;
        prev->next = cur;
        data += dev->cache_block_size;
        prev = cur++;
    }

    dev->cache_init = 1; /* Set cache as initialized */
}

/*
 * Lock a block permanently in the cache by removing it
 * from the LRU chain.
 */
void cache_lock_block(struct cache *cs)
{
    cs->prev->next = cs->next;
    cs->next->prev = cs->prev;

    cs->next = cs->prev = NULL;
}

/*
 * Check for a particular BLOCK in the block cache, 
 * and if it is already there, just do nothing and return;
 * otherwise pick a victim block and update the LRU link.
 */
struct cache *_get_cache_block(struct device *dev, block_t block)
{
    struct cache *head = dev->cache_head;
    struct cache *cs;
    int i;

    cs = dev->cache_head + 1;

    for (i = 0; i < dev->cache_entries; i++) {
	if (cs->block == block)
	    goto found;
	cs++;
    }
    
    /* Not found, pick a victim */
    cs = head->next;

found:
    /* Move to the end of the LRU chain, unless the block is already locked */
    if (cs->next) {
	cs->prev->next = cs->next;
	cs->next->prev = cs->prev;
	
	cs->prev = head->prev;
	head->prev->next = cs;
	cs->next = head;
	head->prev = cs;
    }

    return cs;
}    

/*
 * Check for a particular BLOCK in the block cache, 
 * and if it is already there, just do nothing and return;
 * otherwise load it from disk and update the LRU link.
 * Return the data pointer.
 */
const void *get_cache(struct device *dev, block_t block)
{
    struct cache *cs;

    cs = _get_cache_block(dev, block);
    if (cs->block != block) {
	cs->block = block;
        getoneblk(dev->disk, cs->data, block, dev->cache_block_size);
    }

    return cs->data;
}

/*
 * Read data from the cache at an arbitrary byte offset and length.
 * This is useful for filesystems whose metadata is not necessarily
 * aligned with their blocks.
 *
 * This is still reading linearly on the disk.
 */
size_t cache_read(struct fs_info *fs, void *buf, uint64_t offset, size_t count)
{
    const char *cd;
    char *p = buf;
    size_t off, cnt, total;
    block_t block;

    total = count;
    while (count) {
	block = offset >> fs->block_shift;
	off = offset & (fs->block_size - 1);
	cd = get_cache(fs->fs_dev, block);
	if (!cd)
	    break;
	cnt = fs->block_size - off;
	if (cnt > count)
	    cnt = count;
	memcpy(p, cd + off, cnt);
	count -= cnt;
	p += cnt;
	offset += cnt;
    }
    return total - count;
}