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 | */ |
52 | struct 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(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(lock: &cache->lock); |
77 | wait_event(cache->wait_queue, cache->unused); |
78 | spin_lock(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(lock: &cache->lock); |
109 | |
110 | entry->length = squashfs_read_data(sb, block, length, |
111 | &entry->next_index, entry->actor); |
112 | |
113 | spin_lock(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(lock: &cache->lock); |
127 | wake_up_all(&entry->wait_queue); |
128 | } else |
129 | spin_unlock(lock: &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(lock: &cache->lock); |
152 | wait_event(entry->wait_queue, !entry->pending); |
153 | } else |
154 | spin_unlock(lock: &cache->lock); |
155 | |
156 | goto out; |
157 | } |
158 | |
159 | out: |
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 | */ |
173 | void squashfs_cache_put(struct squashfs_cache_entry *entry) |
174 | { |
175 | struct squashfs_cache *cache = entry->cache; |
176 | |
177 | spin_lock(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(lock: &cache->lock); |
187 | wake_up(&cache->wait_queue); |
188 | return; |
189 | } |
190 | } |
191 | spin_unlock(lock: &cache->lock); |
192 | } |
193 | |
194 | /* |
195 | * Delete cache reclaiming all kmalloced buffers. |
196 | */ |
197 | void 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(objp: cache->entry[i].data[j]); |
208 | kfree(objp: cache->entry[i].data); |
209 | } |
210 | kfree(objp: cache->entry[i].actor); |
211 | } |
212 | |
213 | kfree(objp: cache->entry); |
214 | kfree(objp: 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 | */ |
223 | struct squashfs_cache *squashfs_cache_init(char *name, int entries, |
224 | int block_size) |
225 | { |
226 | int i, j; |
227 | struct squashfs_cache *cache = kzalloc(size: 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(n: entries, size: 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(n: cache->pages, size: 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(buffer: entry->data, |
273 | pages: cache->pages, length: 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 | |
282 | cleanup: |
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 | */ |
293 | int 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 | */ |
331 | int 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, cache: msblk->block_cache, block: *block, length: 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: *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 | |
369 | error: |
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 | */ |
379 | struct 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, cache: msblk->fragment_cache, block: 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 | */ |
394 | struct 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, cache: msblk->read_page, block: start_block, length); |
400 | } |
401 | |
402 | |
403 | /* |
404 | * Read a filesystem table (uncompressed sequence of bytes) from disk |
405 | */ |
406 | void *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(size: length, GFP_KERNEL); |
414 | if (table == NULL) |
415 | return ERR_PTR(error: -ENOMEM); |
416 | |
417 | data = kcalloc(n: pages, size: sizeof(void *), GFP_KERNEL); |
418 | if (data == NULL) { |
419 | res = -ENOMEM; |
420 | goto failed; |
421 | } |
422 | |
423 | actor = squashfs_page_actor_init(buffer: 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(objp: data); |
436 | kfree(objp: actor); |
437 | |
438 | if (res < 0) |
439 | goto failed; |
440 | |
441 | return table; |
442 | |
443 | failed2: |
444 | kfree(objp: data); |
445 | failed: |
446 | kfree(objp: table); |
447 | return ERR_PTR(error: res); |
448 | } |
449 | |