/* * core/cache.c: A simple LRU-based cache implementation. * */ #include #include #include #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; }