Something went wrong. Try again.
Linux kernel mirror (for testing) git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456// SPDX-License-Identifier: GPL-2.0-or-later/* * Squashfs - a compressed read only filesystem for Linux * * Copyright (c) 2002, 2003, 2004, 2005, 2006, 2007, 2008 * Phillip Lougher <phillip@squashfs.org.uk> * * 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 issues with vmalloc the cache * uses sequences of kmalloced PAGE_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/pagemap.h>
#include "squashfs_fs.h"#include "squashfs_fs_sb.h"#include "squashfs.h"#include "page_actor.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 = cache->curr_blk, n = 0; n < cache->entries; n++) { if (cache->entry[i].block == block) { cache->curr_blk = i; break; } i = (i + 1) % cache->entries; }
if (n == 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 chosen 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, block, length, &entry->next_index, entry->actor);
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 (IS_ERR(cache) || 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[i].actor); }
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_SIZE buffers. */struct squashfs_cache *squashfs_cache_init(char *name, int entries, int block_size){ int i, j; struct squashfs_cache *cache;
if (entries == 0) return NULL;
cache = kzalloc_obj(*cache); if (cache == NULL) { ERROR("Failed to allocate %s cache\n", name); return ERR_PTR(-ENOMEM); }
cache->entry = kzalloc_objs(*(cache->entry), entries); if (cache->entry == NULL) { ERROR("Failed to allocate %s cache\n", name); goto cleanup; }
cache->curr_blk = 0; cache->next_blk = 0; cache->unused = entries; cache->entries = entries; cache->block_size = block_size; cache->pages = block_size >> PAGE_SHIFT; cache->pages = cache->pages ? cache->pages : 1; 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_SIZE, GFP_KERNEL); if (entry->data[j] == NULL) { ERROR("Failed to allocate %s buffer\n", name); goto cleanup; } }
entry->actor = squashfs_page_actor_init(entry->data, cache->pages, 0); if (entry->actor == NULL) { ERROR("Failed to allocate %s cache entry\n", name); goto cleanup; } }
return cache;
cleanup: squashfs_cache_delete(cache); return ERR_PTR(-ENOMEM);}
/* * Copy up to 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_SIZE] + (offset % PAGE_SIZE); int bytes = min_t(int, entry->length - offset, PAGE_SIZE - (offset % PAGE_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, res = length; struct squashfs_cache_entry *entry;
TRACE("Entered squashfs_read_metadata [%llx:%x]\n", *block, *offset);
if (unlikely(length < 0)) return -EIO;
if (unlikely(*offset < 0 || *offset >= SQUASHFS_METADATA_SIZE)) return -EIO;
while (length) { entry = squashfs_cache_get(sb, msblk->block_cache, *block, 0); if (entry->error) { res = entry->error; goto error; } else if (*offset >= entry->length) { res = -EIO; goto error; }
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 res;
error: squashfs_cache_put(entry); return res;}
/* * 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 */void *squashfs_read_table(struct super_block *sb, u64 block, int length){ int pages = (length + PAGE_SIZE - 1) >> PAGE_SHIFT; int i, res; void *table, *buffer, **data; struct squashfs_page_actor *actor;
table = buffer = kmalloc(length, GFP_KERNEL); if (table == NULL) return ERR_PTR(-ENOMEM);
data = kcalloc(pages, sizeof(void *), GFP_KERNEL); if (data == NULL) { res = -ENOMEM; goto failed; }
actor = squashfs_page_actor_init(data, pages, length); if (actor == NULL) { res = -ENOMEM; goto failed2; }
for (i = 0; i < pages; i++, buffer += PAGE_SIZE) data[i] = buffer;
res = squashfs_read_data(sb, block, length | SQUASHFS_COMPRESSED_BIT_BLOCK, NULL, actor);
kfree(data); kfree(actor);
if (res < 0) goto failed;
return table;
failed2: kfree(data);failed: kfree(table); return ERR_PTR(res);}