Lines Matching +full:index +full:- +full:page
2 * Squashfs - a compressed read only filesystem for Linux
19 * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
27 * compressed fragment block (tail-end packed block). The compressed size
32 * larger), the code implements an index cache that caches the mapping from
33 * block index to datablock location on disk.
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
39 * The index cache is designed to be memory efficient, and by default uses
58 * Locate cache slot in range [offset, index] for specified inode. If
59 * there's more than one return the slot closest to index.
62 int index) in locate_meta_index() argument
65 struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info; in locate_meta_index()
68 mutex_lock(&msblk->meta_index_mutex); in locate_meta_index()
70 TRACE("locate_meta_index: index %d, offset %d\n", index, offset); in locate_meta_index()
72 if (msblk->meta_index == NULL) in locate_meta_index()
76 if (msblk->meta_index[i].inode_number == inode->i_ino && in locate_meta_index()
77 msblk->meta_index[i].offset >= offset && in locate_meta_index()
78 msblk->meta_index[i].offset <= index && in locate_meta_index()
79 msblk->meta_index[i].locked == 0) { in locate_meta_index()
81 msblk->meta_index[i].offset); in locate_meta_index()
82 meta = &msblk->meta_index[i]; in locate_meta_index()
83 offset = meta->offset; in locate_meta_index()
88 meta->locked = 1; in locate_meta_index()
91 mutex_unlock(&msblk->meta_index_mutex); in locate_meta_index()
98 * Find and initialise an empty cache slot for index offset.
103 struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info; in empty_meta_index()
107 mutex_lock(&msblk->meta_index_mutex); in empty_meta_index()
111 if (msblk->meta_index == NULL) { in empty_meta_index()
113 * First time cache index has been used, allocate and in empty_meta_index()
114 * initialise. The cache index could be allocated at in empty_meta_index()
118 msblk->meta_index = kcalloc(SQUASHFS_META_SLOTS, in empty_meta_index()
119 sizeof(*(msblk->meta_index)), GFP_KERNEL); in empty_meta_index()
120 if (msblk->meta_index == NULL) { in empty_meta_index()
125 msblk->meta_index[i].inode_number = 0; in empty_meta_index()
126 msblk->meta_index[i].locked = 0; in empty_meta_index()
128 msblk->next_meta_index = 0; in empty_meta_index()
132 msblk->meta_index[msblk->next_meta_index].locked; i--) in empty_meta_index()
133 msblk->next_meta_index = (msblk->next_meta_index + 1) % in empty_meta_index()
142 msblk->next_meta_index, in empty_meta_index()
143 &msblk->meta_index[msblk->next_meta_index]); in empty_meta_index()
145 meta = &msblk->meta_index[msblk->next_meta_index]; in empty_meta_index()
146 msblk->next_meta_index = (msblk->next_meta_index + 1) % in empty_meta_index()
149 meta->inode_number = inode->i_ino; in empty_meta_index()
150 meta->offset = offset; in empty_meta_index()
151 meta->skip = skip; in empty_meta_index()
152 meta->entries = 0; in empty_meta_index()
153 meta->locked = 1; in empty_meta_index()
156 mutex_unlock(&msblk->meta_index_mutex); in empty_meta_index()
163 struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info; in release_meta_index()
164 mutex_lock(&msblk->meta_index_mutex); in release_meta_index()
165 meta->locked = 0; in release_meta_index()
166 mutex_unlock(&msblk->meta_index_mutex); in release_meta_index()
183 return -ENOMEM; in read_indexes()
201 n -= blocks; in read_indexes()
214 * Each cache index slot has SQUASHFS_META_ENTRIES, each of which
215 * can cache one index -> datablock/blocklist-block mapping. We wish
216 * to distribute these over the length of the file, entry[0] maps index x,
217 * entry[1] maps index x + skip, entry[2] maps index x + 2 * skip, and so on.
228 return min(SQUASHFS_CACHED_BLKS - 1, skip + 1); in calculate_skip()
233 * Search and grow the index cache for the specified inode, returning the
234 * on-disk locations of the datablock and block list metadata block
235 * <index_block, index_offset> for index (scaled to nearest cache index).
237 static int fill_meta_index(struct inode *inode, int index, in fill_meta_index() argument
240 struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info; in fill_meta_index()
241 int skip = calculate_skip(i_size_read(inode) >> msblk->block_log); in fill_meta_index()
245 u64 cur_index_block = squashfs_i(inode)->block_list_start; in fill_meta_index()
246 int cur_offset = squashfs_i(inode)->offset; in fill_meta_index()
247 u64 cur_data_block = squashfs_i(inode)->start; in fill_meta_index()
251 * Scale index to cache index (cache slot entry) in fill_meta_index()
253 index /= SQUASHFS_META_INDEXES * skip; in fill_meta_index()
255 while (offset < index) { in fill_meta_index()
256 meta = locate_meta_index(inode, offset + 1, index); in fill_meta_index()
263 offset = index < meta->offset + meta->entries ? index : in fill_meta_index()
264 meta->offset + meta->entries - 1; in fill_meta_index()
265 meta_entry = &meta->meta_entry[offset - meta->offset]; in fill_meta_index()
266 cur_index_block = meta_entry->index_block + in fill_meta_index()
267 msblk->inode_table; in fill_meta_index()
268 cur_offset = meta_entry->offset; in fill_meta_index()
269 cur_data_block = meta_entry->data_block; in fill_meta_index()
270 TRACE("get_meta_index: offset %d, meta->offset %d, " in fill_meta_index()
271 "meta->entries %d\n", offset, meta->offset, in fill_meta_index()
272 meta->entries); in fill_meta_index()
280 * slot is extended up to index or to the end of the slot, in in fill_meta_index()
283 for (i = meta->offset + meta->entries; i <= index && in fill_meta_index()
284 i < meta->offset + SQUASHFS_META_ENTRIES; i++) { in fill_meta_index()
286 long long res = read_indexes(inode->i_sb, blocks, in fill_meta_index()
290 if (meta->entries == 0) in fill_meta_index()
295 meta->inode_number = 0; in fill_meta_index()
301 meta_entry = &meta->meta_entry[i - meta->offset]; in fill_meta_index()
302 meta_entry->index_block = cur_index_block - in fill_meta_index()
303 msblk->inode_table; in fill_meta_index()
304 meta_entry->offset = cur_offset; in fill_meta_index()
305 meta_entry->data_block = cur_data_block; in fill_meta_index()
306 meta->entries++; in fill_meta_index()
310 TRACE("get_meta_index: meta->offset %d, meta->entries %d\n", in fill_meta_index()
311 meta->offset, meta->entries); in fill_meta_index()
322 * Scale cache index (cache slot entry) to index in fill_meta_index()
333 * Get the on-disk location and compressed size of the datablock
334 * specified by index. Fill_meta_index() does most of the work.
336 static int read_blocklist(struct inode *inode, int index, u64 *block) in read_blocklist() argument
342 int res = fill_meta_index(inode, index, &start, &offset, block); in read_blocklist()
344 TRACE("read_blocklist: res %d, index %d, start 0x%llx, offset" in read_blocklist()
345 " 0x%x, block 0x%llx\n", res, index, start, offset, in read_blocklist()
352 * res contains the index of the mapping returned by fill_meta_index(), in read_blocklist()
353 * this will likely be less than the desired index (because the in read_blocklist()
357 if (res < index) { in read_blocklist()
358 blks = read_indexes(inode->i_sb, index - res, &start, &offset); in read_blocklist()
365 * Read length of block specified by index. in read_blocklist()
367 res = squashfs_read_metadata(inode->i_sb, &size, &start, &offset, in read_blocklist()
375 static int squashfs_readpage(struct file *file, struct page *page) in squashfs_readpage() argument
377 struct inode *inode = page->mapping->host; in squashfs_readpage()
378 struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info; in squashfs_readpage()
383 int mask = (1 << (msblk->block_log - PAGE_CACHE_SHIFT)) - 1; in squashfs_readpage()
384 int index = page->index >> (msblk->block_log - PAGE_CACHE_SHIFT); in squashfs_readpage() local
385 int start_index = page->index & ~mask; in squashfs_readpage()
387 int file_end = i_size_read(inode) >> msblk->block_log; in squashfs_readpage()
389 TRACE("Entered squashfs_readpage, page index %lx, start block %llx\n", in squashfs_readpage()
390 page->index, squashfs_i(inode)->start); in squashfs_readpage()
392 if (page->index >= ((i_size_read(inode) + PAGE_CACHE_SIZE - 1) >> in squashfs_readpage()
396 if (index < file_end || squashfs_i(inode)->fragment_block == in squashfs_readpage()
403 int bsize = read_blocklist(inode, index, &block); in squashfs_readpage()
408 bytes = index == file_end ? in squashfs_readpage()
409 (i_size_read(inode) & (msblk->block_size - 1)) : in squashfs_readpage()
410 msblk->block_size; in squashfs_readpage()
416 buffer = squashfs_get_datablock(inode->i_sb, in squashfs_readpage()
418 if (buffer->error) { in squashfs_readpage()
419 ERROR("Unable to read page, block %llx, size %x" in squashfs_readpage()
424 bytes = buffer->length; in squashfs_readpage()
428 * Datablock is stored inside a fragment (tail-end packed in squashfs_readpage()
431 buffer = squashfs_get_fragment(inode->i_sb, in squashfs_readpage()
432 squashfs_i(inode)->fragment_block, in squashfs_readpage()
433 squashfs_i(inode)->fragment_size); in squashfs_readpage()
435 if (buffer->error) { in squashfs_readpage()
436 ERROR("Unable to read page, block %llx, size %x\n", in squashfs_readpage()
437 squashfs_i(inode)->fragment_block, in squashfs_readpage()
438 squashfs_i(inode)->fragment_size); in squashfs_readpage()
442 bytes = i_size_read(inode) & (msblk->block_size - 1); in squashfs_readpage()
443 offset = squashfs_i(inode)->fragment_offset; in squashfs_readpage()
449 * grab the pages from the page cache, except for the page that we've in squashfs_readpage()
453 bytes -= PAGE_CACHE_SIZE, offset += PAGE_CACHE_SIZE) { in squashfs_readpage()
454 struct page *push_page; in squashfs_readpage()
459 push_page = (i == page->index) ? page : in squashfs_readpage()
460 grab_cache_page_nowait(page->mapping, i); in squashfs_readpage()
470 memset(pageaddr + avail, 0, PAGE_CACHE_SIZE - avail); in squashfs_readpage()
476 if (i != page->index) in squashfs_readpage()
486 SetPageError(page); in squashfs_readpage()
488 pageaddr = kmap_atomic(page, KM_USER0); in squashfs_readpage()
491 flush_dcache_page(page); in squashfs_readpage()
492 if (!PageError(page)) in squashfs_readpage()
493 SetPageUptodate(page); in squashfs_readpage()
494 unlock_page(page); in squashfs_readpage()