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 <phillip@squashfs.org.uk>
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 * Look-up block in cache, and increment usage count.  If not in cache, read
50 * 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 used
72			 * 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 simple
85			 * round-robin strategy is used to choose the entry to
86			 * 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 from
100			 * 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 processes
122			 * have looked it up in the cache, and have slept
123			 * 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			} else
129				spin_unlock(&cache->lock);
130
131			goto out;
132		}
133
134		/*
135		 * Block already in cache.  Increment refcount so it doesn't
136		 * get reused until we're finished with it, if it was
137		 * previously unused there's one less cache entry available
138		 * 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 process
147		 * 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		} else
154			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 become
183		 * 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 of
220 * size block_size.  To avoid vmalloc fragmentation issues each entry
221 * 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 bytes
290 * into the cache entry.  If there's not length bytes then copy the number of
291 * 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 the
327 * start of the compressed block on disk, and offset is the offset into
328 * 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 the
377 * 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 the
391 * filesystem.  The cache is used here to avoid duplicating locking and
392 * 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 disk
405 */
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