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