cache.c

  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 (IS_ERR(cache) || 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;
228
229	if (entries == 0)
230		return NULL;
231
232	cache = kzalloc(sizeof(*cache), GFP_KERNEL);
233	if (cache == NULL) {
234		ERROR("Failed to allocate %s cache\n", name);
235		return ERR_PTR(-ENOMEM);
236	}
237
238	cache->entry = kcalloc(entries, sizeof(*(cache->entry)), GFP_KERNEL);
239	if (cache->entry == NULL) {
240		ERROR("Failed to allocate %s cache\n", name);
241		goto cleanup;
242	}
243
244	cache->curr_blk = 0;
245	cache->next_blk = 0;
246	cache->unused = entries;
247	cache->entries = entries;
248	cache->block_size = block_size;
249	cache->pages = block_size >> PAGE_SHIFT;
250	cache->pages = cache->pages ? cache->pages : 1;
251	cache->name = name;
252	cache->num_waiters = 0;
253	spin_lock_init(&cache->lock);
254	init_waitqueue_head(&cache->wait_queue);
255
256	for (i = 0; i < entries; i++) {
257		struct squashfs_cache_entry *entry = &cache->entry[i];
258
259		init_waitqueue_head(&cache->entry[i].wait_queue);
260		entry->cache = cache;
261		entry->block = SQUASHFS_INVALID_BLK;
262		entry->data = kcalloc(cache->pages, sizeof(void *), GFP_KERNEL);
263		if (entry->data == NULL) {
264			ERROR("Failed to allocate %s cache entry\n", name);
265			goto cleanup;
266		}
267
268		for (j = 0; j < cache->pages; j++) {
269			entry->data[j] = kmalloc(PAGE_SIZE, GFP_KERNEL);
270			if (entry->data[j] == NULL) {
271				ERROR("Failed to allocate %s buffer\n", name);
272				goto cleanup;
273			}
274		}
275
276		entry->actor = squashfs_page_actor_init(entry->data,
277						cache->pages, 0);
278		if (entry->actor == NULL) {
279			ERROR("Failed to allocate %s cache entry\n", name);
280			goto cleanup;
281		}
282	}
283
284	return cache;
285
286cleanup:
287	squashfs_cache_delete(cache);
288	return ERR_PTR(-ENOMEM);
289}
290
291
292/*
293 * Copy up to length bytes from cache entry to buffer starting at offset bytes
294 * into the cache entry.  If there's not length bytes then copy the number of
295 * bytes available.  In all cases return the number of bytes copied.
296 */
297int squashfs_copy_data(void *buffer, struct squashfs_cache_entry *entry,
298		int offset, int length)
299{
300	int remaining = length;
301
302	if (length == 0)
303		return 0;
304	else if (buffer == NULL)
305		return min(length, entry->length - offset);
306
307	while (offset < entry->length) {
308		void *buff = entry->data[offset / PAGE_SIZE]
309				+ (offset % PAGE_SIZE);
310		int bytes = min_t(int, entry->length - offset,
311				PAGE_SIZE - (offset % PAGE_SIZE));
312
313		if (bytes >= remaining) {
314			memcpy(buffer, buff, remaining);
315			remaining = 0;
316			break;
317		}
318
319		memcpy(buffer, buff, bytes);
320		buffer += bytes;
321		remaining -= bytes;
322		offset += bytes;
323	}
324
325	return length - remaining;
326}
327
328
329/*
330 * Read length bytes from metadata position <block, offset> (block is the
331 * start of the compressed block on disk, and offset is the offset into
332 * the block once decompressed).  Data is packed into consecutive blocks,
333 * and length bytes may require reading more than one block.
334 */
335int squashfs_read_metadata(struct super_block *sb, void *buffer,
336		u64 *block, int *offset, int length)
337{
338	struct squashfs_sb_info *msblk = sb->s_fs_info;
339	int bytes, res = length;
340	struct squashfs_cache_entry *entry;
341
342	TRACE("Entered squashfs_read_metadata [%llx:%x]\n", *block, *offset);
343
344	if (unlikely(length < 0))
345		return -EIO;
346
347	if (unlikely(*offset < 0 || *offset >= SQUASHFS_METADATA_SIZE))
348		return -EIO;
349
350	while (length) {
351		entry = squashfs_cache_get(sb, msblk->block_cache, *block, 0);
352		if (entry->error) {
353			res = entry->error;
354			goto error;
355		} else if (*offset >= entry->length) {
356			res = -EIO;
357			goto error;
358		}
359
360		bytes = squashfs_copy_data(buffer, entry, *offset, length);
361		if (buffer)
362			buffer += bytes;
363		length -= bytes;
364		*offset += bytes;
365
366		if (*offset == entry->length) {
367			*block = entry->next_index;
368			*offset = 0;
369		}
370
371		squashfs_cache_put(entry);
372	}
373
374	return res;
375
376error:
377	squashfs_cache_put(entry);
378	return res;
379}
380
381
382/*
383 * Look-up in the fragmment cache the fragment located at <start_block> in the
384 * filesystem.  If necessary read and decompress it from disk.
385 */
386struct squashfs_cache_entry *squashfs_get_fragment(struct super_block *sb,
387				u64 start_block, int length)
388{
389	struct squashfs_sb_info *msblk = sb->s_fs_info;
390
391	return squashfs_cache_get(sb, msblk->fragment_cache, start_block,
392		length);
393}
394
395
396/*
397 * Read and decompress the datablock located at <start_block> in the
398 * filesystem.  The cache is used here to avoid duplicating locking and
399 * read/decompress code.
400 */
401struct squashfs_cache_entry *squashfs_get_datablock(struct super_block *sb,
402				u64 start_block, int length)
403{
404	struct squashfs_sb_info *msblk = sb->s_fs_info;
405
406	return squashfs_cache_get(sb, msblk->read_page, start_block, length);
407}
408
409
410/*
411 * Read a filesystem table (uncompressed sequence of bytes) from disk
412 */
413void *squashfs_read_table(struct super_block *sb, u64 block, int length)
414{
415	int pages = (length + PAGE_SIZE - 1) >> PAGE_SHIFT;
416	int i, res;
417	void *table, *buffer, **data;
418	struct squashfs_page_actor *actor;
419
420	table = buffer = kmalloc(length, GFP_KERNEL);
421	if (table == NULL)
422		return ERR_PTR(-ENOMEM);
423
424	data = kcalloc(pages, sizeof(void *), GFP_KERNEL);
425	if (data == NULL) {
426		res = -ENOMEM;
427		goto failed;
428	}
429
430	actor = squashfs_page_actor_init(data, pages, length);
431	if (actor == NULL) {
432		res = -ENOMEM;
433		goto failed2;
434	}
435
436	for (i = 0; i < pages; i++, buffer += PAGE_SIZE)
437		data[i] = buffer;
438
439	res = squashfs_read_data(sb, block, length |
440		SQUASHFS_COMPRESSED_BIT_BLOCK, NULL, actor);
441
442	kfree(data);
443	kfree(actor);
444
445	if (res < 0)
446		goto failed;
447
448	return table;
449
450failed2:
451	kfree(data);
452failed:
453	kfree(table);
454	return ERR_PTR(res);
455}