Something went wrong. Try again.
(I'm so sorry!) Linux kernel mirror (for testing) git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
kernel os linux
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558// 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"
/* * Waiters on cache->wait_queue are keyed by the block they want, so a wakeup * can name who it is for. A NULL key is a capacity wakeup: one entry became * free, so wake one waiter. A block key is a publication wakeup: that block * now has an entry, so wake every waiter which can share it. */struct squashfs_cache_wait { wait_queue_entry_t wait; u64 block; bool capacity_wake;};
static int squashfs_cache_wake_function(wait_queue_entry_t *wait, unsigned int mode, int sync, void *key){ struct squashfs_cache_wait *cache_wait = container_of(wait, struct squashfs_cache_wait, wait); u64 *block = key;
if (block && cache_wait->block != *block) return 0;
WRITE_ONCE(cache_wait->capacity_wake, !block);
/* * Wake and unlink unconditionally instead of using * autoremove_wake_function(), which unlinks only when it changed the * task state. A waiter can be made runnable by something which does * not go through this queue: wake_up_process() takes TASK_NORMAL, and * a cgroup v2 thaw calls it on every task in the cgroup, as do * free_pid() on a pid namespace init and a late rcuwait_wake_up(). * try_to_wake_up() then fails. Leaving such a waiter queued with a * reason already recorded would let it act on a freed entry it was not * given, and the failure would not consume the exclusive budget, so a * second waiter would be woken for the same entry. * * list_del_init_careful() must be the last access to @cache_wait: it * releases the waiter, whose wait structure lives on its stack, and it * pairs with list_empty_careful() in finish_wait() to publish the * store above. __wake_up_common() samples ->flags and the next entry * before calling here, so it does not touch @wait afterwards either. */ default_wake_function(wait, mode, sync, key); list_del_init_careful(&wait->entry);
return 1;}
static void squashfs_cache_wake_block(struct squashfs_cache *cache, u64 block){ /* nr_exclusive == 0: wake every waiter which matches the key. */ __wake_up(&cache->wait_queue, TASK_NORMAL, 0, &block);}
/* * Look-up block in cache, and increment usage count. If not in cache, read * and decompress it from disk. * * A caller which finds no free entry sleeps on cache->wait_queue as an * exclusive waiter, so squashfs_cache_put() releasing one entry wakes exactly * one task. Because a wakee may find its block published in the meantime and * share that entry rather than claim the free one, a wakee which shares hands * its wakeup on to the next waiter. */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; bool capacity_wake = false;
spin_lock(&cache->lock);
while (1) { bool pending, wake_next, wake_block;
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) { struct squashfs_cache_wait wait = { .block = block, .capacity_wake = false, };
init_wait_func(&wait.wait, squashfs_cache_wake_function); cache->num_waiters++; /* * Enqueue while still holding cache->lock, so * that a concurrent lookup either sees us * queued or we see the block it publishes. */ prepare_to_wait_exclusive(&cache->wait_queue, &wait.wait, TASK_UNINTERRUPTIBLE); spin_unlock(&cache->lock); schedule(); finish_wait(&cache->wait_queue, &wait.wait); capacity_wake = READ_ONCE(wait.capacity_wake); 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; wake_block = cache->num_waiters > 0; spin_unlock(&cache->lock);
/* * The entry is now findable, so release everybody * queued for this block to share it rather than each * waiting for an entry of their own. They will block * on entry->wait_queue below until the read completes. */ if (wake_block) squashfs_cache_wake_block(cache, block);
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--; /* This claims the capacity we were woken for. */ capacity_wake = false; } entry->refcount++;
/* * If the entry is currently being filled in by another process * go to sleep waiting for it to become available. */ pending = entry->pending; if (pending) entry->num_waiters++;
/* * We were woken because an entry became free, but shared a * block instead of claiming it. Hand the wakeup on, otherwise * the free entry sits unclaimed while others sleep. */ wake_next = capacity_wake && cache->unused && cache->num_waiters; spin_unlock(&cache->lock);
if (wake_next) wake_up(&cache->wait_queue); if (pending) wait_event(entry->wait_queue, !entry->pending);
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 || offset < 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);}