projects/linux·blob master · refs

557 lines · 14.7 KiB

1// SPDX-License-Identifier: GPL-2.0-or-later
2/*
3 * Squashfs - a compressed read only filesystem for Linux
4 *
5 * Copyright (c) 2002, 2003, 2004, 2005, 2006, 2007, 2008
6 * Phillip Lougher <[email protected]>
7 *
8 * cache.c
9 */
10
11/*
12 * Blocks in Squashfs are compressed. To avoid repeatedly decompressing
13 * 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 to
17 * access the metadata and fragment caches.
18 *
19 * To avoid out of memory and fragmentation issues with vmalloc the cache
20 * uses sequences of kmalloced PAGE_SIZE buffers.
21 *
22 * It should be noted that the cache is not used for file datablocks, these
23 * are decompressed and cached in the page-cache in the normal way. The
24 * cache is only used to temporarily cache fragment and metadata blocks
25 * which have been read as as a result of a metadata (i.e. inode or
26 * directory) or fragment access. Because metadata and fragments are packed
27 * together into blocks (to gain greater compression) the read of a particular
28 * piece of metadata or fragment will retrieve other metadata/fragments which
29 * have been packed with it, these because of locality-of-reference may be read
30 * in the near future. Temporarily caching them ensures they are available for
31 * 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 * Waiters on cache->wait_queue are keyed by the block they want, so a wakeup
50 * can name who it is for. A NULL key is a capacity wakeup: one entry became
51 * free, so wake one waiter. A block key is a publication wakeup: that block
52 * now has an entry, so wake every waiter which can share it.
53 */
54struct squashfs_cache_wait {
55 wait_queue_entry_t wait;
56 u64 block;
57 bool capacity_wake;
58};
59
60static int squashfs_cache_wake_function(wait_queue_entry_t *wait,
61 unsigned int mode, int sync, void *key)
62{
63 struct squashfs_cache_wait *cache_wait =
64 container_of(wait, struct squashfs_cache_wait, wait);
65 u64 *block = key;
66
67 if (block && cache_wait->block != *block)
68 return 0;
69
70 WRITE_ONCE(cache_wait->capacity_wake, !block);
71
72 /*
73 * Wake and unlink unconditionally instead of using
74 * autoremove_wake_function(), which unlinks only when it changed the
75 * task state. A waiter can be made runnable by something which does
76 * not go through this queue: wake_up_process() takes TASK_NORMAL, and
77 * a cgroup v2 thaw calls it on every task in the cgroup, as do
78 * free_pid() on a pid namespace init and a late rcuwait_wake_up().
79 * try_to_wake_up() then fails. Leaving such a waiter queued with a
80 * reason already recorded would let it act on a freed entry it was not
81 * given, and the failure would not consume the exclusive budget, so a
82 * second waiter would be woken for the same entry.
83 *
84 * list_del_init_careful() must be the last access to @cache_wait: it
85 * releases the waiter, whose wait structure lives on its stack, and it
86 * pairs with list_empty_careful() in finish_wait() to publish the
87 * store above. __wake_up_common() samples ->flags and the next entry
88 * before calling here, so it does not touch @wait afterwards either.
89 */
90 default_wake_function(wait, mode, sync, key);
91 list_del_init_careful(&wait->entry);
92
93 return 1;
94}
95
96static void squashfs_cache_wake_block(struct squashfs_cache *cache, u64 block)
97{
98 /* nr_exclusive == 0: wake every waiter which matches the key. */
99 __wake_up(&cache->wait_queue, TASK_NORMAL, 0, &block);
100}
101
102/*
103 * Look-up block in cache, and increment usage count. If not in cache, read
104 * and decompress it from disk.
105 *
106 * A caller which finds no free entry sleeps on cache->wait_queue as an
107 * exclusive waiter, so squashfs_cache_put() releasing one entry wakes exactly
108 * one task. Because a wakee may find its block published in the meantime and
109 * share that entry rather than claim the free one, a wakee which shares hands
110 * its wakeup on to the next waiter.
111 */
112struct squashfs_cache_entry *squashfs_cache_get(struct super_block *sb,
113 struct squashfs_cache *cache, u64 block, int length)
114{
115 int i, n;
116 struct squashfs_cache_entry *entry;
117 bool capacity_wake = false;
118
119 spin_lock(&cache->lock);
120
121 while (1) {
122 bool pending, wake_next, wake_block;
123
124 for (i = cache->curr_blk, n = 0; n < cache->entries; n++) {
125 if (cache->entry[i].block == block) {
126 cache->curr_blk = i;
127 break;
128 }
129 i = (i + 1) % cache->entries;
130 }
131
132 if (n == cache->entries) {
133 /*
134 * Block not in cache, if all cache entries are used
135 * go to sleep waiting for one to become available.
136 */
137 if (cache->unused == 0) {
138 struct squashfs_cache_wait wait = {
139 .block = block,
140 .capacity_wake = false,
141 };
142
143 init_wait_func(&wait.wait,
144 squashfs_cache_wake_function);
145 cache->num_waiters++;
146 /*
147 * Enqueue while still holding cache->lock, so
148 * that a concurrent lookup either sees us
149 * queued or we see the block it publishes.
150 */
151 prepare_to_wait_exclusive(&cache->wait_queue,
152 &wait.wait, TASK_UNINTERRUPTIBLE);
153 spin_unlock(&cache->lock);
154 schedule();
155 finish_wait(&cache->wait_queue, &wait.wait);
156 capacity_wake = READ_ONCE(wait.capacity_wake);
157 spin_lock(&cache->lock);
158 cache->num_waiters--;
159 continue;
160 }
161
162 /*
163 * At least one unused cache entry. A simple
164 * round-robin strategy is used to choose the entry to
165 * be evicted from the cache.
166 */
167 i = cache->next_blk;
168 for (n = 0; n < cache->entries; n++) {
169 if (cache->entry[i].refcount == 0)
170 break;
171 i = (i + 1) % cache->entries;
172 }
173
174 cache->next_blk = (i + 1) % cache->entries;
175 entry = &cache->entry[i];
176
177 /*
178 * Initialise chosen cache entry, and fill it in from
179 * disk.
180 */
181 cache->unused--;
182 entry->block = block;
183 entry->refcount = 1;
184 entry->pending = 1;
185 entry->num_waiters = 0;
186 entry->error = 0;
187 wake_block = cache->num_waiters > 0;
188 spin_unlock(&cache->lock);
189
190 /*
191 * The entry is now findable, so release everybody
192 * queued for this block to share it rather than each
193 * waiting for an entry of their own. They will block
194 * on entry->wait_queue below until the read completes.
195 */
196 if (wake_block)
197 squashfs_cache_wake_block(cache, block);
198
199 entry->length = squashfs_read_data(sb, block, length,
200 &entry->next_index, entry->actor);
201
202 spin_lock(&cache->lock);
203
204 if (entry->length < 0)
205 entry->error = entry->length;
206
207 entry->pending = 0;
208
209 /*
210 * While filling this entry one or more other processes
211 * have looked it up in the cache, and have slept
212 * waiting for it to become available.
213 */
214 if (entry->num_waiters) {
215 spin_unlock(&cache->lock);
216 wake_up_all(&entry->wait_queue);
217 } else
218 spin_unlock(&cache->lock);
219
220 goto out;
221 }
222
223 /*
224 * Block already in cache. Increment refcount so it doesn't
225 * get reused until we're finished with it, if it was
226 * previously unused there's one less cache entry available
227 * for reuse.
228 */
229 entry = &cache->entry[i];
230 if (entry->refcount == 0) {
231 cache->unused--;
232 /* This claims the capacity we were woken for. */
233 capacity_wake = false;
234 }
235 entry->refcount++;
236
237 /*
238 * If the entry is currently being filled in by another process
239 * go to sleep waiting for it to become available.
240 */
241 pending = entry->pending;
242 if (pending)
243 entry->num_waiters++;
244
245 /*
246 * We were woken because an entry became free, but shared a
247 * block instead of claiming it. Hand the wakeup on, otherwise
248 * the free entry sits unclaimed while others sleep.
249 */
250 wake_next = capacity_wake && cache->unused && cache->num_waiters;
251 spin_unlock(&cache->lock);
252
253 if (wake_next)
254 wake_up(&cache->wait_queue);
255 if (pending)
256 wait_event(entry->wait_queue, !entry->pending);
257
258 goto out;
259 }
260
261out:
262 TRACE("Got %s %d, start block %lld, refcount %d, error %d\n",
263 cache->name, i, entry->block, entry->refcount, entry->error);
264
265 if (entry->error)
266 ERROR("Unable to read %s cache entry [%llx]\n", cache->name,
267 block);
268 return entry;
269}
270
271
272/*
273 * Release cache entry, once usage count is zero it can be reused.
274 */
275void squashfs_cache_put(struct squashfs_cache_entry *entry)
276{
277 struct squashfs_cache *cache = entry->cache;
278
279 spin_lock(&cache->lock);
280 entry->refcount--;
281 if (entry->refcount == 0) {
282 cache->unused++;
283 /*
284 * If there's any processes waiting for a block to become
285 * available, wake one up.
286 */
287 if (cache->num_waiters) {
288 spin_unlock(&cache->lock);
289 wake_up(&cache->wait_queue);
290 return;
291 }
292 }
293 spin_unlock(&cache->lock);
294}
295
296/*
297 * Delete cache reclaiming all kmalloced buffers.
298 */
299void squashfs_cache_delete(struct squashfs_cache *cache)
300{
301 int i, j;
302
303 if (IS_ERR(cache) || cache == NULL)
304 return;
305
306 for (i = 0; i < cache->entries; i++) {
307 if (cache->entry[i].data) {
308 for (j = 0; j < cache->pages; j++)
309 kfree(cache->entry[i].data[j]);
310 kfree(cache->entry[i].data);
311 }
312 kfree(cache->entry[i].actor);
313 }
314
315 kfree(cache->entry);
316 kfree(cache);
317}
318
319
320/*
321 * Initialise cache allocating the specified number of entries, each of
322 * size block_size. To avoid vmalloc fragmentation issues each entry
323 * is allocated as a sequence of kmalloced PAGE_SIZE buffers.
324 */
325struct squashfs_cache *squashfs_cache_init(char *name, int entries,
326 int block_size)
327{
328 int i, j;
329 struct squashfs_cache *cache;
330
331 if (entries == 0)
332 return NULL;
333
334 cache = kzalloc_obj(*cache);
335 if (cache == NULL) {
336 ERROR("Failed to allocate %s cache\n", name);
337 return ERR_PTR(-ENOMEM);
338 }
339
340 cache->entry = kzalloc_objs(*(cache->entry), entries);
341 if (cache->entry == NULL) {
342 ERROR("Failed to allocate %s cache\n", name);
343 goto cleanup;
344 }
345
346 cache->curr_blk = 0;
347 cache->next_blk = 0;
348 cache->unused = entries;
349 cache->entries = entries;
350 cache->block_size = block_size;
351 cache->pages = block_size >> PAGE_SHIFT;
352 cache->pages = cache->pages ? cache->pages : 1;
353 cache->name = name;
354 cache->num_waiters = 0;
355 spin_lock_init(&cache->lock);
356 init_waitqueue_head(&cache->wait_queue);
357
358 for (i = 0; i < entries; i++) {
359 struct squashfs_cache_entry *entry = &cache->entry[i];
360
361 init_waitqueue_head(&cache->entry[i].wait_queue);
362 entry->cache = cache;
363 entry->block = SQUASHFS_INVALID_BLK;
364 entry->data = kcalloc(cache->pages, sizeof(void *), GFP_KERNEL);
365 if (entry->data == NULL) {
366 ERROR("Failed to allocate %s cache entry\n", name);
367 goto cleanup;
368 }
369
370 for (j = 0; j < cache->pages; j++) {
371 entry->data[j] = kmalloc(PAGE_SIZE, GFP_KERNEL);
372 if (entry->data[j] == NULL) {
373 ERROR("Failed to allocate %s buffer\n", name);
374 goto cleanup;
375 }
376 }
377
378 entry->actor = squashfs_page_actor_init(entry->data,
379 cache->pages, 0);
380 if (entry->actor == NULL) {
381 ERROR("Failed to allocate %s cache entry\n", name);
382 goto cleanup;
383 }
384 }
385
386 return cache;
387
388cleanup:
389 squashfs_cache_delete(cache);
390 return ERR_PTR(-ENOMEM);
391}
392
393
394/*
395 * Copy up to length bytes from cache entry to buffer starting at offset bytes
396 * into the cache entry. If there's not length bytes then copy the number of
397 * bytes available. In all cases return the number of bytes copied.
398 */
399int squashfs_copy_data(void *buffer, struct squashfs_cache_entry *entry,
400 int offset, int length)
401{
402 int remaining = length;
403
404 if (length == 0 || offset < 0)
405 return 0;
406 else if (buffer == NULL)
407 return min(length, entry->length - offset);
408
409 while (offset < entry->length) {
410 void *buff = entry->data[offset / PAGE_SIZE]
411 + (offset % PAGE_SIZE);
412 int bytes = min_t(int, entry->length - offset,
413 PAGE_SIZE - (offset % PAGE_SIZE));
414
415 if (bytes >= remaining) {
416 memcpy(buffer, buff, remaining);
417 remaining = 0;
418 break;
419 }
420
421 memcpy(buffer, buff, bytes);
422 buffer += bytes;
423 remaining -= bytes;
424 offset += bytes;
425 }
426
427 return length - remaining;
428}
429
430
431/*
432 * Read length bytes from metadata position <block, offset> (block is the
433 * start of the compressed block on disk, and offset is the offset into
434 * the block once decompressed). Data is packed into consecutive blocks,
435 * and length bytes may require reading more than one block.
436 */
437int squashfs_read_metadata(struct super_block *sb, void *buffer,
438 u64 *block, int *offset, int length)
439{
440 struct squashfs_sb_info *msblk = sb->s_fs_info;
441 int bytes, res = length;
442 struct squashfs_cache_entry *entry;
443
444 TRACE("Entered squashfs_read_metadata [%llx:%x]\n", *block, *offset);
445
446 if (unlikely(length < 0))
447 return -EIO;
448
449 if (unlikely(*offset < 0 || *offset >= SQUASHFS_METADATA_SIZE))
450 return -EIO;
451
452 while (length) {
453 entry = squashfs_cache_get(sb, msblk->block_cache, *block, 0);
454 if (entry->error) {
455 res = entry->error;
456 goto error;
457 } else if (*offset >= entry->length) {
458 res = -EIO;
459 goto error;
460 }
461
462 bytes = squashfs_copy_data(buffer, entry, *offset, length);
463 if (buffer)
464 buffer += bytes;
465 length -= bytes;
466 *offset += bytes;
467
468 if (*offset == entry->length) {
469 *block = entry->next_index;
470 *offset = 0;
471 }
472
473 squashfs_cache_put(entry);
474 }
475
476 return res;
477
478error:
479 squashfs_cache_put(entry);
480 return res;
481}
482
483
484/*
485 * Look-up in the fragmment cache the fragment located at <start_block> in the
486 * filesystem. If necessary read and decompress it from disk.
487 */
488struct squashfs_cache_entry *squashfs_get_fragment(struct super_block *sb,
489 u64 start_block, int length)
490{
491 struct squashfs_sb_info *msblk = sb->s_fs_info;
492
493 return squashfs_cache_get(sb, msblk->fragment_cache, start_block,
494 length);
495}
496
497
498/*
499 * Read and decompress the datablock located at <start_block> in the
500 * filesystem. The cache is used here to avoid duplicating locking and
501 * read/decompress code.
502 */
503struct squashfs_cache_entry *squashfs_get_datablock(struct super_block *sb,
504 u64 start_block, int length)
505{
506 struct squashfs_sb_info *msblk = sb->s_fs_info;
507
508 return squashfs_cache_get(sb, msblk->read_page, start_block, length);
509}
510
511
512/*
513 * Read a filesystem table (uncompressed sequence of bytes) from disk
514 */
515void *squashfs_read_table(struct super_block *sb, u64 block, int length)
516{
517 int pages = (length + PAGE_SIZE - 1) >> PAGE_SHIFT;
518 int i, res;
519 void *table, *buffer, **data;
520 struct squashfs_page_actor *actor;
521
522 table = buffer = kmalloc(length, GFP_KERNEL);
523 if (table == NULL)
524 return ERR_PTR(-ENOMEM);
525
526 data = kcalloc(pages, sizeof(void *), GFP_KERNEL);
527 if (data == NULL) {
528 res = -ENOMEM;
529 goto failed;
530 }
531
532 actor = squashfs_page_actor_init(data, pages, length);
533 if (actor == NULL) {
534 res = -ENOMEM;
535 goto failed2;
536 }
537
538 for (i = 0; i < pages; i++, buffer += PAGE_SIZE)
539 data[i] = buffer;
540
541 res = squashfs_read_data(sb, block, length |
542 SQUASHFS_COMPRESSED_BIT_BLOCK, NULL, actor);
543
544 kfree(data);
545 kfree(actor);
546
547 if (res < 0)
548 goto failed;
549
550 return table;
551
552failed2:
553 kfree(data);
554failed:
555 kfree(table);
556 return ERR_PTR(res);
557}