Squashfs: cache operations

Signed-off-by: Phillip Lougher <phillip@lougher.demon.co.uk>

diff --git a/fs/squashfs/cache.c b/fs/squashfs/cache.c
new file mode 100644 (file)
index 0000000..f29eda1
--- /dev/null
+++ b/fs/squashfs/cache.c
@@ -0,0 +1,412 @@
+/*
+ * Squashfs - a compressed read only filesystem for Linux
+ *
+ * Copyright (c) 2002, 2003, 2004, 2005, 2006, 2007, 2008
+ * Phillip Lougher <phillip@lougher.demon.co.uk>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2,
+ * or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * cache.c
+ */
+
+/*
+ * Blocks in Squashfs are compressed.  To avoid repeatedly decompressing
+ * recently accessed data Squashfs uses two small metadata and fragment caches.
+ *
+ * This file implements a generic cache implementation used for both caches,
+ * plus functions layered ontop of the generic cache implementation to
+ * access the metadata and fragment caches.
+ *
+ * To avoid out of memory and fragmentation isssues with vmalloc the cache
+ * uses sequences of kmalloced PAGE_CACHE_SIZE buffers.
+ *
+ * It should be noted that the cache is not used for file datablocks, these
+ * are decompressed and cached in the page-cache in the normal way.  The
+ * cache is only used to temporarily cache fragment and metadata blocks
+ * which have been read as as a result of a metadata (i.e. inode or
+ * directory) or fragment access.  Because metadata and fragments are packed
+ * together into blocks (to gain greater compression) the read of a particular
+ * piece of metadata or fragment will retrieve other metadata/fragments which
+ * have been packed with it, these because of locality-of-reference may be read
+ * in the near future. Temporarily caching them ensures they are available for
+ * near future access without requiring an additional read and decompress.
+ */
+
+#include <linux/fs.h>
+#include <linux/vfs.h>
+#include <linux/slab.h>
+#include <linux/vmalloc.h>
+#include <linux/sched.h>
+#include <linux/spinlock.h>
+#include <linux/wait.h>
+#include <linux/zlib.h>
+#include <linux/pagemap.h>
+
+#include "squashfs_fs.h"
+#include "squashfs_fs_sb.h"
+#include "squashfs_fs_i.h"
+#include "squashfs.h"
+
+/*
+ * Look-up block in cache, and increment usage count.  If not in cache, read
+ * and decompress it from disk.
+ */
+struct squashfs_cache_entry *squashfs_cache_get(struct super_block *sb,
+       struct squashfs_cache *cache, u64 block, int length)
+{
+       int i, n;
+       struct squashfs_cache_entry *entry;
+
+       spin_lock(&cache->lock);
+
+       while (1) {
+               for (i = 0; i < cache->entries; i++)
+                       if (cache->entry[i].block == block)
+                               break;
+
+               if (i == cache->entries) {
+                       /*
+                        * Block not in cache, if all cache entries are used
+                        * go to sleep waiting for one to become available.
+                        */
+                       if (cache->unused == 0) {
+                               cache->num_waiters++;
+                               spin_unlock(&cache->lock);
+                               wait_event(cache->wait_queue, cache->unused);
+                               spin_lock(&cache->lock);
+                               cache->num_waiters--;
+                               continue;
+                       }
+
+                       /*
+                        * At least one unused cache entry.  A simple
+                        * round-robin strategy is used to choose the entry to
+                        * be evicted from the cache.
+                        */
+                       i = cache->next_blk;
+                       for (n = 0; n < cache->entries; n++) {
+                               if (cache->entry[i].refcount == 0)
+                                       break;
+                               i = (i + 1) % cache->entries;
+                       }
+
+                       cache->next_blk = (i + 1) % cache->entries;
+                       entry = &cache->entry[i];
+
+                       /*
+                        * Initialise choosen cache entry, and fill it in from
+                        * disk.
+                        */
+                       cache->unused--;
+                       entry->block = block;
+                       entry->refcount = 1;
+                       entry->pending = 1;
+                       entry->num_waiters = 0;
+                       entry->error = 0;
+                       spin_unlock(&cache->lock);
+
+                       entry->length = squashfs_read_data(sb, entry->data,
+                               block, length, &entry->next_index,
+                               cache->block_size);
+
+                       spin_lock(&cache->lock);
+
+                       if (entry->length < 0)
+                               entry->error = entry->length;
+
+                       entry->pending = 0;
+
+                       /*
+                        * While filling this entry one or more other processes
+                        * have looked it up in the cache, and have slept
+                        * waiting for it to become available.
+                        */
+                       if (entry->num_waiters) {
+                               spin_unlock(&cache->lock);
+                               wake_up_all(&entry->wait_queue);
+                       } else
+                               spin_unlock(&cache->lock);
+
+                       goto out;
+               }
+
+               /*
+                * Block already in cache.  Increment refcount so it doesn't
+                * get reused until we're finished with it, if it was
+                * previously unused there's one less cache entry available
+                * for reuse.
+                */
+               entry = &cache->entry[i];
+               if (entry->refcount == 0)
+                       cache->unused--;
+               entry->refcount++;
+
+               /*
+                * If the entry is currently being filled in by another process
+                * go to sleep waiting for it to become available.
+                */
+               if (entry->pending) {
+                       entry->num_waiters++;
+                       spin_unlock(&cache->lock);
+                       wait_event(entry->wait_queue, !entry->pending);
+               } else
+                       spin_unlock(&cache->lock);
+
+               goto out;
+       }
+
+out:
+       TRACE("Got %s %d, start block %lld, refcount %d, error %d\n",
+               cache->name, i, entry->block, entry->refcount, entry->error);
+
+       if (entry->error)
+               ERROR("Unable to read %s cache entry [%llx]\n", cache->name,
+                                                       block);
+       return entry;
+}
+
+
+/*
+ * Release cache entry, once usage count is zero it can be reused.
+ */
+void squashfs_cache_put(struct squashfs_cache_entry *entry)
+{
+       struct squashfs_cache *cache = entry->cache;
+
+       spin_lock(&cache->lock);
+       entry->refcount--;
+       if (entry->refcount == 0) {
+               cache->unused++;
+               /*
+                * If there's any processes waiting for a block to become
+                * available, wake one up.
+                */
+               if (cache->num_waiters) {
+                       spin_unlock(&cache->lock);
+                       wake_up(&cache->wait_queue);
+                       return;
+               }
+       }
+       spin_unlock(&cache->lock);
+}
+
+/*
+ * Delete cache reclaiming all kmalloced buffers.
+ */
+void squashfs_cache_delete(struct squashfs_cache *cache)
+{
+       int i, j;
+
+       if (cache == NULL)
+               return;
+
+       for (i = 0; i < cache->entries; i++) {
+               if (cache->entry[i].data) {
+                       for (j = 0; j < cache->pages; j++)
+                               kfree(cache->entry[i].data[j]);
+                       kfree(cache->entry[i].data);
+               }
+       }
+
+       kfree(cache->entry);
+       kfree(cache);
+}
+
+
+/*
+ * Initialise cache allocating the specified number of entries, each of
+ * size block_size.  To avoid vmalloc fragmentation issues each entry
+ * is allocated as a sequence of kmalloced PAGE_CACHE_SIZE buffers.
+ */
+struct squashfs_cache *squashfs_cache_init(char *name, int entries,
+       int block_size)
+{
+       int i, j;
+       struct squashfs_cache *cache = kzalloc(sizeof(*cache), GFP_KERNEL);
+
+       if (cache == NULL) {
+               ERROR("Failed to allocate %s cache\n", name);
+               return NULL;
+       }
+
+       cache->entry = kcalloc(entries, sizeof(*(cache->entry)), GFP_KERNEL);
+       if (cache->entry == NULL) {
+               ERROR("Failed to allocate %s cache\n", name);
+               goto cleanup;
+       }
+
+       cache->next_blk = 0;
+       cache->unused = entries;
+       cache->entries = entries;
+       cache->block_size = block_size;
+       cache->pages = block_size >> PAGE_CACHE_SHIFT;
+       cache->name = name;
+       cache->num_waiters = 0;
+       spin_lock_init(&cache->lock);
+       init_waitqueue_head(&cache->wait_queue);
+
+       for (i = 0; i < entries; i++) {
+               struct squashfs_cache_entry *entry = &cache->entry[i];
+
+               init_waitqueue_head(&cache->entry[i].wait_queue);
+               entry->cache = cache;
+               entry->block = SQUASHFS_INVALID_BLK;
+               entry->data = kcalloc(cache->pages, sizeof(void *), GFP_KERNEL);
+               if (entry->data == NULL) {
+                       ERROR("Failed to allocate %s cache entry\n", name);
+                       goto cleanup;
+               }
+
+               for (j = 0; j < cache->pages; j++) {
+                       entry->data[j] = kmalloc(PAGE_CACHE_SIZE, GFP_KERNEL);
+                       if (entry->data[j] == NULL) {
+                               ERROR("Failed to allocate %s buffer\n", name);
+                               goto cleanup;
+                       }
+               }
+       }
+
+       return cache;
+
+cleanup:
+       squashfs_cache_delete(cache);
+       return NULL;
+}
+
+
+/*
+ * Copy upto length bytes from cache entry to buffer starting at offset bytes
+ * into the cache entry.  If there's not length bytes then copy the number of
+ * bytes available.  In all cases return the number of bytes copied.
+ */
+int squashfs_copy_data(void *buffer, struct squashfs_cache_entry *entry,
+               int offset, int length)
+{
+       int remaining = length;
+
+       if (length == 0)
+               return 0;
+       else if (buffer == NULL)
+               return min(length, entry->length - offset);
+
+       while (offset < entry->length) {
+               void *buff = entry->data[offset / PAGE_CACHE_SIZE]
+                               + (offset % PAGE_CACHE_SIZE);
+               int bytes = min_t(int, entry->length - offset,
+                               PAGE_CACHE_SIZE - (offset % PAGE_CACHE_SIZE));
+
+               if (bytes >= remaining) {
+                       memcpy(buffer, buff, remaining);
+                       remaining = 0;
+                       break;
+               }
+
+               memcpy(buffer, buff, bytes);
+               buffer += bytes;
+               remaining -= bytes;
+               offset += bytes;
+       }
+
+       return length - remaining;
+}
+
+
+/*
+ * Read length bytes from metadata position <block, offset> (block is the
+ * start of the compressed block on disk, and offset is the offset into
+ * the block once decompressed).  Data is packed into consecutive blocks,
+ * and length bytes may require reading more than one block.
+ */
+int squashfs_read_metadata(struct super_block *sb, void *buffer,
+               u64 *block, int *offset, int length)
+{
+       struct squashfs_sb_info *msblk = sb->s_fs_info;
+       int bytes, copied = length;
+       struct squashfs_cache_entry *entry;
+
+       TRACE("Entered squashfs_read_metadata [%llx:%x]\n", *block, *offset);
+
+       while (length) {
+               entry = squashfs_cache_get(sb, msblk->block_cache, *block, 0);
+               if (entry->error)
+                       return entry->error;
+               else if (*offset >= entry->length)
+                       return -EIO;
+
+               bytes = squashfs_copy_data(buffer, entry, *offset, length);
+               if (buffer)
+                       buffer += bytes;
+               length -= bytes;
+               *offset += bytes;
+
+               if (*offset == entry->length) {
+                       *block = entry->next_index;
+                       *offset = 0;
+               }
+
+               squashfs_cache_put(entry);
+       }
+
+       return copied;
+}
+
+
+/*
+ * Look-up in the fragmment cache the fragment located at <start_block> in the
+ * filesystem.  If necessary read and decompress it from disk.
+ */
+struct squashfs_cache_entry *squashfs_get_fragment(struct super_block *sb,
+                               u64 start_block, int length)
+{
+       struct squashfs_sb_info *msblk = sb->s_fs_info;
+
+       return squashfs_cache_get(sb, msblk->fragment_cache, start_block,
+               length);
+}
+
+
+/*
+ * Read and decompress the datablock located at <start_block> in the
+ * filesystem.  The cache is used here to avoid duplicating locking and
+ * read/decompress code.
+ */
+struct squashfs_cache_entry *squashfs_get_datablock(struct super_block *sb,
+                               u64 start_block, int length)
+{
+       struct squashfs_sb_info *msblk = sb->s_fs_info;
+
+       return squashfs_cache_get(sb, msblk->read_page, start_block, length);
+}
+
+
+/*
+ * Read a filesystem table (uncompressed sequence of bytes) from disk
+ */
+int squashfs_read_table(struct super_block *sb, void *buffer, u64 block,
+       int length)
+{
+       int pages = (length + PAGE_CACHE_SIZE - 1) >> PAGE_CACHE_SHIFT;
+       int i, res;
+       void **data = kcalloc(pages, sizeof(void *), GFP_KERNEL);
+       if (data == NULL)
+               return -ENOMEM;
+
+       for (i = 0; i < pages; i++, buffer += PAGE_CACHE_SIZE)
+               data[i] = buffer;
+       res = squashfs_read_data(sb, data, block, length |
+               SQUASHFS_COMPRESSED_BIT_BLOCK, NULL, length);
+       kfree(data);
+       return res;
+}