Root/
1 | /* |
2 | * Squashfs - a compressed read only filesystem for Linux |
3 | * |
4 | * Copyright (c) 2002, 2003, 2004, 2005, 2006, 2007, 2008 |
5 | * Phillip Lougher <phillip@squashfs.org.uk> |
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 | * file.c |
22 | */ |
23 | |
24 | /* |
25 | * This file contains code for handling regular files. A regular file |
26 | * consists of a sequence of contiguous compressed blocks, and/or a |
27 | * compressed fragment block (tail-end packed block). The compressed size |
28 | * of each datablock is stored in a block list contained within the |
29 | * file inode (itself stored in one or more compressed metadata blocks). |
30 | * |
31 | * To speed up access to datablocks when reading 'large' files (256 Mbytes or |
32 | * larger), the code implements an index cache that caches the mapping from |
33 | * block index to datablock location on disk. |
34 | * |
35 | * The index cache allows Squashfs to handle large files (up to 1.75 TiB) while |
36 | * retaining a simple and space-efficient block list on disk. The cache |
37 | * is split into slots, caching up to eight 224 GiB files (128 KiB blocks). |
38 | * Larger files use multiple slots, with 1.75 TiB files using all 8 slots. |
39 | * The index cache is designed to be memory efficient, and by default uses |
40 | * 16 KiB. |
41 | */ |
42 | |
43 | #include <linux/fs.h> |
44 | #include <linux/vfs.h> |
45 | #include <linux/kernel.h> |
46 | #include <linux/slab.h> |
47 | #include <linux/string.h> |
48 | #include <linux/pagemap.h> |
49 | #include <linux/mutex.h> |
50 | |
51 | #include "squashfs_fs.h" |
52 | #include "squashfs_fs_sb.h" |
53 | #include "squashfs_fs_i.h" |
54 | #include "squashfs.h" |
55 | |
56 | /* |
57 | * Locate cache slot in range [offset, index] for specified inode. If |
58 | * there's more than one return the slot closest to index. |
59 | */ |
60 | static struct meta_index *locate_meta_index(struct inode *inode, int offset, |
61 | int index) |
62 | { |
63 | struct meta_index *meta = NULL; |
64 | struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info; |
65 | int i; |
66 | |
67 | mutex_lock(&msblk->meta_index_mutex); |
68 | |
69 | TRACE("locate_meta_index: index %d, offset %d\n", index, offset); |
70 | |
71 | if (msblk->meta_index == NULL) |
72 | goto not_allocated; |
73 | |
74 | for (i = 0; i < SQUASHFS_META_SLOTS; i++) { |
75 | if (msblk->meta_index[i].inode_number == inode->i_ino && |
76 | msblk->meta_index[i].offset >= offset && |
77 | msblk->meta_index[i].offset <= index && |
78 | msblk->meta_index[i].locked == 0) { |
79 | TRACE("locate_meta_index: entry %d, offset %d\n", i, |
80 | msblk->meta_index[i].offset); |
81 | meta = &msblk->meta_index[i]; |
82 | offset = meta->offset; |
83 | } |
84 | } |
85 | |
86 | if (meta) |
87 | meta->locked = 1; |
88 | |
89 | not_allocated: |
90 | mutex_unlock(&msblk->meta_index_mutex); |
91 | |
92 | return meta; |
93 | } |
94 | |
95 | |
96 | /* |
97 | * Find and initialise an empty cache slot for index offset. |
98 | */ |
99 | static struct meta_index *empty_meta_index(struct inode *inode, int offset, |
100 | int skip) |
101 | { |
102 | struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info; |
103 | struct meta_index *meta = NULL; |
104 | int i; |
105 | |
106 | mutex_lock(&msblk->meta_index_mutex); |
107 | |
108 | TRACE("empty_meta_index: offset %d, skip %d\n", offset, skip); |
109 | |
110 | if (msblk->meta_index == NULL) { |
111 | /* |
112 | * First time cache index has been used, allocate and |
113 | * initialise. The cache index could be allocated at |
114 | * mount time but doing it here means it is allocated only |
115 | * if a 'large' file is read. |
116 | */ |
117 | msblk->meta_index = kcalloc(SQUASHFS_META_SLOTS, |
118 | sizeof(*(msblk->meta_index)), GFP_KERNEL); |
119 | if (msblk->meta_index == NULL) { |
120 | ERROR("Failed to allocate meta_index\n"); |
121 | goto failed; |
122 | } |
123 | for (i = 0; i < SQUASHFS_META_SLOTS; i++) { |
124 | msblk->meta_index[i].inode_number = 0; |
125 | msblk->meta_index[i].locked = 0; |
126 | } |
127 | msblk->next_meta_index = 0; |
128 | } |
129 | |
130 | for (i = SQUASHFS_META_SLOTS; i && |
131 | msblk->meta_index[msblk->next_meta_index].locked; i--) |
132 | msblk->next_meta_index = (msblk->next_meta_index + 1) % |
133 | SQUASHFS_META_SLOTS; |
134 | |
135 | if (i == 0) { |
136 | TRACE("empty_meta_index: failed!\n"); |
137 | goto failed; |
138 | } |
139 | |
140 | TRACE("empty_meta_index: returned meta entry %d, %p\n", |
141 | msblk->next_meta_index, |
142 | &msblk->meta_index[msblk->next_meta_index]); |
143 | |
144 | meta = &msblk->meta_index[msblk->next_meta_index]; |
145 | msblk->next_meta_index = (msblk->next_meta_index + 1) % |
146 | SQUASHFS_META_SLOTS; |
147 | |
148 | meta->inode_number = inode->i_ino; |
149 | meta->offset = offset; |
150 | meta->skip = skip; |
151 | meta->entries = 0; |
152 | meta->locked = 1; |
153 | |
154 | failed: |
155 | mutex_unlock(&msblk->meta_index_mutex); |
156 | return meta; |
157 | } |
158 | |
159 | |
160 | static void release_meta_index(struct inode *inode, struct meta_index *meta) |
161 | { |
162 | struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info; |
163 | mutex_lock(&msblk->meta_index_mutex); |
164 | meta->locked = 0; |
165 | mutex_unlock(&msblk->meta_index_mutex); |
166 | } |
167 | |
168 | |
169 | /* |
170 | * Read the next n blocks from the block list, starting from |
171 | * metadata block <start_block, offset>. |
172 | */ |
173 | static long long read_indexes(struct super_block *sb, int n, |
174 | u64 *start_block, int *offset) |
175 | { |
176 | int err, i; |
177 | long long block = 0; |
178 | __le32 *blist = kmalloc(PAGE_CACHE_SIZE, GFP_KERNEL); |
179 | |
180 | if (blist == NULL) { |
181 | ERROR("read_indexes: Failed to allocate block_list\n"); |
182 | return -ENOMEM; |
183 | } |
184 | |
185 | while (n) { |
186 | int blocks = min_t(int, n, PAGE_CACHE_SIZE >> 2); |
187 | |
188 | err = squashfs_read_metadata(sb, blist, start_block, |
189 | offset, blocks << 2); |
190 | if (err < 0) { |
191 | ERROR("read_indexes: reading block [%llx:%x]\n", |
192 | *start_block, *offset); |
193 | goto failure; |
194 | } |
195 | |
196 | for (i = 0; i < blocks; i++) { |
197 | int size = le32_to_cpu(blist[i]); |
198 | block += SQUASHFS_COMPRESSED_SIZE_BLOCK(size); |
199 | } |
200 | n -= blocks; |
201 | } |
202 | |
203 | kfree(blist); |
204 | return block; |
205 | |
206 | failure: |
207 | kfree(blist); |
208 | return err; |
209 | } |
210 | |
211 | |
212 | /* |
213 | * Each cache index slot has SQUASHFS_META_ENTRIES, each of which |
214 | * can cache one index -> datablock/blocklist-block mapping. We wish |
215 | * to distribute these over the length of the file, entry[0] maps index x, |
216 | * entry[1] maps index x + skip, entry[2] maps index x + 2 * skip, and so on. |
217 | * The larger the file, the greater the skip factor. The skip factor is |
218 | * limited to the size of the metadata cache (SQUASHFS_CACHED_BLKS) to ensure |
219 | * the number of metadata blocks that need to be read fits into the cache. |
220 | * If the skip factor is limited in this way then the file will use multiple |
221 | * slots. |
222 | */ |
223 | static inline int calculate_skip(int blocks) |
224 | { |
225 | int skip = blocks / ((SQUASHFS_META_ENTRIES + 1) |
226 | * SQUASHFS_META_INDEXES); |
227 | return min(SQUASHFS_CACHED_BLKS - 1, skip + 1); |
228 | } |
229 | |
230 | |
231 | /* |
232 | * Search and grow the index cache for the specified inode, returning the |
233 | * on-disk locations of the datablock and block list metadata block |
234 | * <index_block, index_offset> for index (scaled to nearest cache index). |
235 | */ |
236 | static int fill_meta_index(struct inode *inode, int index, |
237 | u64 *index_block, int *index_offset, u64 *data_block) |
238 | { |
239 | struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info; |
240 | int skip = calculate_skip(i_size_read(inode) >> msblk->block_log); |
241 | int offset = 0; |
242 | struct meta_index *meta; |
243 | struct meta_entry *meta_entry; |
244 | u64 cur_index_block = squashfs_i(inode)->block_list_start; |
245 | int cur_offset = squashfs_i(inode)->offset; |
246 | u64 cur_data_block = squashfs_i(inode)->start; |
247 | int err, i; |
248 | |
249 | /* |
250 | * Scale index to cache index (cache slot entry) |
251 | */ |
252 | index /= SQUASHFS_META_INDEXES * skip; |
253 | |
254 | while (offset < index) { |
255 | meta = locate_meta_index(inode, offset + 1, index); |
256 | |
257 | if (meta == NULL) { |
258 | meta = empty_meta_index(inode, offset + 1, skip); |
259 | if (meta == NULL) |
260 | goto all_done; |
261 | } else { |
262 | offset = index < meta->offset + meta->entries ? index : |
263 | meta->offset + meta->entries - 1; |
264 | meta_entry = &meta->meta_entry[offset - meta->offset]; |
265 | cur_index_block = meta_entry->index_block + |
266 | msblk->inode_table; |
267 | cur_offset = meta_entry->offset; |
268 | cur_data_block = meta_entry->data_block; |
269 | TRACE("get_meta_index: offset %d, meta->offset %d, " |
270 | "meta->entries %d\n", offset, meta->offset, |
271 | meta->entries); |
272 | TRACE("get_meta_index: index_block 0x%llx, offset 0x%x" |
273 | " data_block 0x%llx\n", cur_index_block, |
274 | cur_offset, cur_data_block); |
275 | } |
276 | |
277 | /* |
278 | * If necessary grow cache slot by reading block list. Cache |
279 | * slot is extended up to index or to the end of the slot, in |
280 | * which case further slots will be used. |
281 | */ |
282 | for (i = meta->offset + meta->entries; i <= index && |
283 | i < meta->offset + SQUASHFS_META_ENTRIES; i++) { |
284 | int blocks = skip * SQUASHFS_META_INDEXES; |
285 | long long res = read_indexes(inode->i_sb, blocks, |
286 | &cur_index_block, &cur_offset); |
287 | |
288 | if (res < 0) { |
289 | if (meta->entries == 0) |
290 | /* |
291 | * Don't leave an empty slot on read |
292 | * error allocated to this inode... |
293 | */ |
294 | meta->inode_number = 0; |
295 | err = res; |
296 | goto failed; |
297 | } |
298 | |
299 | cur_data_block += res; |
300 | meta_entry = &meta->meta_entry[i - meta->offset]; |
301 | meta_entry->index_block = cur_index_block - |
302 | msblk->inode_table; |
303 | meta_entry->offset = cur_offset; |
304 | meta_entry->data_block = cur_data_block; |
305 | meta->entries++; |
306 | offset++; |
307 | } |
308 | |
309 | TRACE("get_meta_index: meta->offset %d, meta->entries %d\n", |
310 | meta->offset, meta->entries); |
311 | |
312 | release_meta_index(inode, meta); |
313 | } |
314 | |
315 | all_done: |
316 | *index_block = cur_index_block; |
317 | *index_offset = cur_offset; |
318 | *data_block = cur_data_block; |
319 | |
320 | /* |
321 | * Scale cache index (cache slot entry) to index |
322 | */ |
323 | return offset * SQUASHFS_META_INDEXES * skip; |
324 | |
325 | failed: |
326 | release_meta_index(inode, meta); |
327 | return err; |
328 | } |
329 | |
330 | |
331 | /* |
332 | * Get the on-disk location and compressed size of the datablock |
333 | * specified by index. Fill_meta_index() does most of the work. |
334 | */ |
335 | static int read_blocklist(struct inode *inode, int index, u64 *block) |
336 | { |
337 | u64 start; |
338 | long long blks; |
339 | int offset; |
340 | __le32 size; |
341 | int res = fill_meta_index(inode, index, &start, &offset, block); |
342 | |
343 | TRACE("read_blocklist: res %d, index %d, start 0x%llx, offset" |
344 | " 0x%x, block 0x%llx\n", res, index, start, offset, |
345 | *block); |
346 | |
347 | if (res < 0) |
348 | return res; |
349 | |
350 | /* |
351 | * res contains the index of the mapping returned by fill_meta_index(), |
352 | * this will likely be less than the desired index (because the |
353 | * meta_index cache works at a higher granularity). Read any |
354 | * extra block indexes needed. |
355 | */ |
356 | if (res < index) { |
357 | blks = read_indexes(inode->i_sb, index - res, &start, &offset); |
358 | if (blks < 0) |
359 | return (int) blks; |
360 | *block += blks; |
361 | } |
362 | |
363 | /* |
364 | * Read length of block specified by index. |
365 | */ |
366 | res = squashfs_read_metadata(inode->i_sb, &size, &start, &offset, |
367 | sizeof(size)); |
368 | if (res < 0) |
369 | return res; |
370 | return le32_to_cpu(size); |
371 | } |
372 | |
373 | |
374 | static int squashfs_readpage(struct file *file, struct page *page) |
375 | { |
376 | struct inode *inode = page->mapping->host; |
377 | struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info; |
378 | int bytes, i, offset = 0, sparse = 0; |
379 | struct squashfs_cache_entry *buffer = NULL; |
380 | void *pageaddr; |
381 | |
382 | int mask = (1 << (msblk->block_log - PAGE_CACHE_SHIFT)) - 1; |
383 | int index = page->index >> (msblk->block_log - PAGE_CACHE_SHIFT); |
384 | int start_index = page->index & ~mask; |
385 | int end_index = start_index | mask; |
386 | int file_end = i_size_read(inode) >> msblk->block_log; |
387 | |
388 | TRACE("Entered squashfs_readpage, page index %lx, start block %llx\n", |
389 | page->index, squashfs_i(inode)->start); |
390 | |
391 | if (page->index >= ((i_size_read(inode) + PAGE_CACHE_SIZE - 1) >> |
392 | PAGE_CACHE_SHIFT)) |
393 | goto out; |
394 | |
395 | if (index < file_end || squashfs_i(inode)->fragment_block == |
396 | SQUASHFS_INVALID_BLK) { |
397 | /* |
398 | * Reading a datablock from disk. Need to read block list |
399 | * to get location and block size. |
400 | */ |
401 | u64 block = 0; |
402 | int bsize = read_blocklist(inode, index, &block); |
403 | if (bsize < 0) |
404 | goto error_out; |
405 | |
406 | if (bsize == 0) { /* hole */ |
407 | bytes = index == file_end ? |
408 | (i_size_read(inode) & (msblk->block_size - 1)) : |
409 | msblk->block_size; |
410 | sparse = 1; |
411 | } else { |
412 | /* |
413 | * Read and decompress datablock. |
414 | */ |
415 | buffer = squashfs_get_datablock(inode->i_sb, |
416 | block, bsize); |
417 | if (buffer->error) { |
418 | ERROR("Unable to read page, block %llx, size %x" |
419 | "\n", block, bsize); |
420 | squashfs_cache_put(buffer); |
421 | goto error_out; |
422 | } |
423 | bytes = buffer->length; |
424 | } |
425 | } else { |
426 | /* |
427 | * Datablock is stored inside a fragment (tail-end packed |
428 | * block). |
429 | */ |
430 | buffer = squashfs_get_fragment(inode->i_sb, |
431 | squashfs_i(inode)->fragment_block, |
432 | squashfs_i(inode)->fragment_size); |
433 | |
434 | if (buffer->error) { |
435 | ERROR("Unable to read page, block %llx, size %x\n", |
436 | squashfs_i(inode)->fragment_block, |
437 | squashfs_i(inode)->fragment_size); |
438 | squashfs_cache_put(buffer); |
439 | goto error_out; |
440 | } |
441 | bytes = i_size_read(inode) & (msblk->block_size - 1); |
442 | offset = squashfs_i(inode)->fragment_offset; |
443 | } |
444 | |
445 | /* |
446 | * Loop copying datablock into pages. As the datablock likely covers |
447 | * many PAGE_CACHE_SIZE pages (default block size is 128 KiB) explicitly |
448 | * grab the pages from the page cache, except for the page that we've |
449 | * been called to fill. |
450 | */ |
451 | for (i = start_index; i <= end_index && bytes > 0; i++, |
452 | bytes -= PAGE_CACHE_SIZE, offset += PAGE_CACHE_SIZE) { |
453 | struct page *push_page; |
454 | int avail = sparse ? 0 : min_t(int, bytes, PAGE_CACHE_SIZE); |
455 | |
456 | TRACE("bytes %d, i %d, available_bytes %d\n", bytes, i, avail); |
457 | |
458 | push_page = (i == page->index) ? page : |
459 | grab_cache_page_nowait(page->mapping, i); |
460 | |
461 | if (!push_page) |
462 | continue; |
463 | |
464 | if (PageUptodate(push_page)) |
465 | goto skip_page; |
466 | |
467 | pageaddr = kmap_atomic(push_page, KM_USER0); |
468 | squashfs_copy_data(pageaddr, buffer, offset, avail); |
469 | memset(pageaddr + avail, 0, PAGE_CACHE_SIZE - avail); |
470 | kunmap_atomic(pageaddr, KM_USER0); |
471 | flush_dcache_page(push_page); |
472 | SetPageUptodate(push_page); |
473 | skip_page: |
474 | unlock_page(push_page); |
475 | if (i != page->index) |
476 | page_cache_release(push_page); |
477 | } |
478 | |
479 | if (!sparse) |
480 | squashfs_cache_put(buffer); |
481 | |
482 | return 0; |
483 | |
484 | error_out: |
485 | SetPageError(page); |
486 | out: |
487 | pageaddr = kmap_atomic(page, KM_USER0); |
488 | memset(pageaddr, 0, PAGE_CACHE_SIZE); |
489 | kunmap_atomic(pageaddr, KM_USER0); |
490 | flush_dcache_page(page); |
491 | if (!PageError(page)) |
492 | SetPageUptodate(page); |
493 | unlock_page(page); |
494 | |
495 | return 0; |
496 | } |
497 | |
498 | |
499 | const struct address_space_operations squashfs_aops = { |
500 | .readpage = squashfs_readpage |
501 | }; |
502 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9