449 lines · c
1// SPDX-License-Identifier: GPL-2.0-or-later2/*3 * Squashfs - a compressed read only filesystem for Linux4 *5 * Copyright (c) 2002, 2003, 2004, 2005, 2006, 2007, 20086 * Phillip Lougher <phillip@squashfs.org.uk>7 *8 * cache.c9 */10 11/*12 * Blocks in Squashfs are compressed. To avoid repeatedly decompressing13 * recently accessed data Squashfs uses two small metadata and fragment caches.14 *15 * This file implements a generic cache implementation used for both caches,16 * plus functions layered ontop of the generic cache implementation to17 * access the metadata and fragment caches.18 *19 * To avoid out of memory and fragmentation issues with vmalloc the cache20 * uses sequences of kmalloced PAGE_SIZE buffers.21 *22 * It should be noted that the cache is not used for file datablocks, these23 * are decompressed and cached in the page-cache in the normal way. The24 * cache is only used to temporarily cache fragment and metadata blocks25 * which have been read as as a result of a metadata (i.e. inode or26 * directory) or fragment access. Because metadata and fragments are packed27 * together into blocks (to gain greater compression) the read of a particular28 * piece of metadata or fragment will retrieve other metadata/fragments which29 * have been packed with it, these because of locality-of-reference may be read30 * in the near future. Temporarily caching them ensures they are available for31 * near future access without requiring an additional read and decompress.32 */33 34#include <linux/fs.h>35#include <linux/vfs.h>36#include <linux/slab.h>37#include <linux/vmalloc.h>38#include <linux/sched.h>39#include <linux/spinlock.h>40#include <linux/wait.h>41#include <linux/pagemap.h>42 43#include "squashfs_fs.h"44#include "squashfs_fs_sb.h"45#include "squashfs.h"46#include "page_actor.h"47 48/*49 * Look-up block in cache, and increment usage count. If not in cache, read50 * and decompress it from disk.51 */52struct squashfs_cache_entry *squashfs_cache_get(struct super_block *sb,53 struct squashfs_cache *cache, u64 block, int length)54{55 int i, n;56 struct squashfs_cache_entry *entry;57 58 spin_lock(&cache->lock);59 60 while (1) {61 for (i = cache->curr_blk, n = 0; n < cache->entries; n++) {62 if (cache->entry[i].block == block) {63 cache->curr_blk = i;64 break;65 }66 i = (i + 1) % cache->entries;67 }68 69 if (n == cache->entries) {70 /*71 * Block not in cache, if all cache entries are used72 * go to sleep waiting for one to become available.73 */74 if (cache->unused == 0) {75 cache->num_waiters++;76 spin_unlock(&cache->lock);77 wait_event(cache->wait_queue, cache->unused);78 spin_lock(&cache->lock);79 cache->num_waiters--;80 continue;81 }82 83 /*84 * At least one unused cache entry. A simple85 * round-robin strategy is used to choose the entry to86 * be evicted from the cache.87 */88 i = cache->next_blk;89 for (n = 0; n < cache->entries; n++) {90 if (cache->entry[i].refcount == 0)91 break;92 i = (i + 1) % cache->entries;93 }94 95 cache->next_blk = (i + 1) % cache->entries;96 entry = &cache->entry[i];97 98 /*99 * Initialise chosen cache entry, and fill it in from100 * disk.101 */102 cache->unused--;103 entry->block = block;104 entry->refcount = 1;105 entry->pending = 1;106 entry->num_waiters = 0;107 entry->error = 0;108 spin_unlock(&cache->lock);109 110 entry->length = squashfs_read_data(sb, block, length,111 &entry->next_index, entry->actor);112 113 spin_lock(&cache->lock);114 115 if (entry->length < 0)116 entry->error = entry->length;117 118 entry->pending = 0;119 120 /*121 * While filling this entry one or more other processes122 * have looked it up in the cache, and have slept123 * waiting for it to become available.124 */125 if (entry->num_waiters) {126 spin_unlock(&cache->lock);127 wake_up_all(&entry->wait_queue);128 } else129 spin_unlock(&cache->lock);130 131 goto out;132 }133 134 /*135 * Block already in cache. Increment refcount so it doesn't136 * get reused until we're finished with it, if it was137 * previously unused there's one less cache entry available138 * for reuse.139 */140 entry = &cache->entry[i];141 if (entry->refcount == 0)142 cache->unused--;143 entry->refcount++;144 145 /*146 * If the entry is currently being filled in by another process147 * go to sleep waiting for it to become available.148 */149 if (entry->pending) {150 entry->num_waiters++;151 spin_unlock(&cache->lock);152 wait_event(entry->wait_queue, !entry->pending);153 } else154 spin_unlock(&cache->lock);155 156 goto out;157 }158 159out:160 TRACE("Got %s %d, start block %lld, refcount %d, error %d\n",161 cache->name, i, entry->block, entry->refcount, entry->error);162 163 if (entry->error)164 ERROR("Unable to read %s cache entry [%llx]\n", cache->name,165 block);166 return entry;167}168 169 170/*171 * Release cache entry, once usage count is zero it can be reused.172 */173void squashfs_cache_put(struct squashfs_cache_entry *entry)174{175 struct squashfs_cache *cache = entry->cache;176 177 spin_lock(&cache->lock);178 entry->refcount--;179 if (entry->refcount == 0) {180 cache->unused++;181 /*182 * If there's any processes waiting for a block to become183 * available, wake one up.184 */185 if (cache->num_waiters) {186 spin_unlock(&cache->lock);187 wake_up(&cache->wait_queue);188 return;189 }190 }191 spin_unlock(&cache->lock);192}193 194/*195 * Delete cache reclaiming all kmalloced buffers.196 */197void squashfs_cache_delete(struct squashfs_cache *cache)198{199 int i, j;200 201 if (cache == NULL)202 return;203 204 for (i = 0; i < cache->entries; i++) {205 if (cache->entry[i].data) {206 for (j = 0; j < cache->pages; j++)207 kfree(cache->entry[i].data[j]);208 kfree(cache->entry[i].data);209 }210 kfree(cache->entry[i].actor);211 }212 213 kfree(cache->entry);214 kfree(cache);215}216 217 218/*219 * Initialise cache allocating the specified number of entries, each of220 * size block_size. To avoid vmalloc fragmentation issues each entry221 * is allocated as a sequence of kmalloced PAGE_SIZE buffers.222 */223struct squashfs_cache *squashfs_cache_init(char *name, int entries,224 int block_size)225{226 int i, j;227 struct squashfs_cache *cache = kzalloc(sizeof(*cache), GFP_KERNEL);228 229 if (cache == NULL) {230 ERROR("Failed to allocate %s cache\n", name);231 return NULL;232 }233 234 cache->entry = kcalloc(entries, sizeof(*(cache->entry)), GFP_KERNEL);235 if (cache->entry == NULL) {236 ERROR("Failed to allocate %s cache\n", name);237 goto cleanup;238 }239 240 cache->curr_blk = 0;241 cache->next_blk = 0;242 cache->unused = entries;243 cache->entries = entries;244 cache->block_size = block_size;245 cache->pages = block_size >> PAGE_SHIFT;246 cache->pages = cache->pages ? cache->pages : 1;247 cache->name = name;248 cache->num_waiters = 0;249 spin_lock_init(&cache->lock);250 init_waitqueue_head(&cache->wait_queue);251 252 for (i = 0; i < entries; i++) {253 struct squashfs_cache_entry *entry = &cache->entry[i];254 255 init_waitqueue_head(&cache->entry[i].wait_queue);256 entry->cache = cache;257 entry->block = SQUASHFS_INVALID_BLK;258 entry->data = kcalloc(cache->pages, sizeof(void *), GFP_KERNEL);259 if (entry->data == NULL) {260 ERROR("Failed to allocate %s cache entry\n", name);261 goto cleanup;262 }263 264 for (j = 0; j < cache->pages; j++) {265 entry->data[j] = kmalloc(PAGE_SIZE, GFP_KERNEL);266 if (entry->data[j] == NULL) {267 ERROR("Failed to allocate %s buffer\n", name);268 goto cleanup;269 }270 }271 272 entry->actor = squashfs_page_actor_init(entry->data,273 cache->pages, 0);274 if (entry->actor == NULL) {275 ERROR("Failed to allocate %s cache entry\n", name);276 goto cleanup;277 }278 }279 280 return cache;281 282cleanup:283 squashfs_cache_delete(cache);284 return NULL;285}286 287 288/*289 * Copy up to length bytes from cache entry to buffer starting at offset bytes290 * into the cache entry. If there's not length bytes then copy the number of291 * bytes available. In all cases return the number of bytes copied.292 */293int squashfs_copy_data(void *buffer, struct squashfs_cache_entry *entry,294 int offset, int length)295{296 int remaining = length;297 298 if (length == 0)299 return 0;300 else if (buffer == NULL)301 return min(length, entry->length - offset);302 303 while (offset < entry->length) {304 void *buff = entry->data[offset / PAGE_SIZE]305 + (offset % PAGE_SIZE);306 int bytes = min_t(int, entry->length - offset,307 PAGE_SIZE - (offset % PAGE_SIZE));308 309 if (bytes >= remaining) {310 memcpy(buffer, buff, remaining);311 remaining = 0;312 break;313 }314 315 memcpy(buffer, buff, bytes);316 buffer += bytes;317 remaining -= bytes;318 offset += bytes;319 }320 321 return length - remaining;322}323 324 325/*326 * Read length bytes from metadata position <block, offset> (block is the327 * start of the compressed block on disk, and offset is the offset into328 * the block once decompressed). Data is packed into consecutive blocks,329 * and length bytes may require reading more than one block.330 */331int squashfs_read_metadata(struct super_block *sb, void *buffer,332 u64 *block, int *offset, int length)333{334 struct squashfs_sb_info *msblk = sb->s_fs_info;335 int bytes, res = length;336 struct squashfs_cache_entry *entry;337 338 TRACE("Entered squashfs_read_metadata [%llx:%x]\n", *block, *offset);339 340 if (unlikely(length < 0))341 return -EIO;342 343 while (length) {344 entry = squashfs_cache_get(sb, msblk->block_cache, *block, 0);345 if (entry->error) {346 res = entry->error;347 goto error;348 } else if (*offset >= entry->length) {349 res = -EIO;350 goto error;351 }352 353 bytes = squashfs_copy_data(buffer, entry, *offset, length);354 if (buffer)355 buffer += bytes;356 length -= bytes;357 *offset += bytes;358 359 if (*offset == entry->length) {360 *block = entry->next_index;361 *offset = 0;362 }363 364 squashfs_cache_put(entry);365 }366 367 return res;368 369error:370 squashfs_cache_put(entry);371 return res;372}373 374 375/*376 * Look-up in the fragmment cache the fragment located at <start_block> in the377 * filesystem. If necessary read and decompress it from disk.378 */379struct squashfs_cache_entry *squashfs_get_fragment(struct super_block *sb,380 u64 start_block, int length)381{382 struct squashfs_sb_info *msblk = sb->s_fs_info;383 384 return squashfs_cache_get(sb, msblk->fragment_cache, start_block,385 length);386}387 388 389/*390 * Read and decompress the datablock located at <start_block> in the391 * filesystem. The cache is used here to avoid duplicating locking and392 * read/decompress code.393 */394struct squashfs_cache_entry *squashfs_get_datablock(struct super_block *sb,395 u64 start_block, int length)396{397 struct squashfs_sb_info *msblk = sb->s_fs_info;398 399 return squashfs_cache_get(sb, msblk->read_page, start_block, length);400}401 402 403/*404 * Read a filesystem table (uncompressed sequence of bytes) from disk405 */406void *squashfs_read_table(struct super_block *sb, u64 block, int length)407{408 int pages = (length + PAGE_SIZE - 1) >> PAGE_SHIFT;409 int i, res;410 void *table, *buffer, **data;411 struct squashfs_page_actor *actor;412 413 table = buffer = kmalloc(length, GFP_KERNEL);414 if (table == NULL)415 return ERR_PTR(-ENOMEM);416 417 data = kcalloc(pages, sizeof(void *), GFP_KERNEL);418 if (data == NULL) {419 res = -ENOMEM;420 goto failed;421 }422 423 actor = squashfs_page_actor_init(data, pages, length);424 if (actor == NULL) {425 res = -ENOMEM;426 goto failed2;427 }428 429 for (i = 0; i < pages; i++, buffer += PAGE_SIZE)430 data[i] = buffer;431 432 res = squashfs_read_data(sb, block, length |433 SQUASHFS_COMPRESSED_BIT_BLOCK, NULL, actor);434 435 kfree(data);436 kfree(actor);437 438 if (res < 0)439 goto failed;440 441 return table;442 443failed2:444 kfree(data);445failed:446 kfree(table);447 return ERR_PTR(res);448}449