Lines Matching +full:cache +full:- +full:block
1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * Squashfs - a compressed read only filesystem for Linux
14 * compressed fragment block (tail-end packed block). The compressed size
15 * of each datablock is stored in a block list contained within the
19 * larger), the code implements an index cache that caches the mapping from
20 * block index to datablock location on disk.
22 * The index cache allows Squashfs to handle large files (up to 1.75 TiB) while
23 * retaining a simple and space-efficient block list on disk. The cache
26 * The index cache is designed to be memory efficient, and by default uses
45 * Locate cache slot in range [offset, index] for specified inode. If
52 struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info; in locate_meta_index()
55 mutex_lock(&msblk->meta_index_mutex); in locate_meta_index()
59 if (msblk->meta_index == NULL) in locate_meta_index()
63 if (msblk->meta_index[i].inode_number == inode->i_ino && in locate_meta_index()
64 msblk->meta_index[i].offset >= offset && in locate_meta_index()
65 msblk->meta_index[i].offset <= index && in locate_meta_index()
66 msblk->meta_index[i].locked == 0) { in locate_meta_index()
68 msblk->meta_index[i].offset); in locate_meta_index()
69 meta = &msblk->meta_index[i]; in locate_meta_index()
70 offset = meta->offset; in locate_meta_index()
75 meta->locked = 1; in locate_meta_index()
78 mutex_unlock(&msblk->meta_index_mutex); in locate_meta_index()
85 * Find and initialise an empty cache slot for index offset.
90 struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info; in empty_meta_index()
94 mutex_lock(&msblk->meta_index_mutex); in empty_meta_index()
98 if (msblk->meta_index == NULL) { in empty_meta_index()
100 * First time cache index has been used, allocate and in empty_meta_index()
101 * initialise. The cache index could be allocated at in empty_meta_index()
105 msblk->meta_index = kcalloc(SQUASHFS_META_SLOTS, in empty_meta_index()
106 sizeof(*(msblk->meta_index)), GFP_KERNEL); in empty_meta_index()
107 if (msblk->meta_index == NULL) { in empty_meta_index()
112 msblk->meta_index[i].inode_number = 0; in empty_meta_index()
113 msblk->meta_index[i].locked = 0; in empty_meta_index()
115 msblk->next_meta_index = 0; in empty_meta_index()
119 msblk->meta_index[msblk->next_meta_index].locked; i--) in empty_meta_index()
120 msblk->next_meta_index = (msblk->next_meta_index + 1) % in empty_meta_index()
129 msblk->next_meta_index, in empty_meta_index()
130 &msblk->meta_index[msblk->next_meta_index]); in empty_meta_index()
132 meta = &msblk->meta_index[msblk->next_meta_index]; in empty_meta_index()
133 msblk->next_meta_index = (msblk->next_meta_index + 1) % in empty_meta_index()
136 meta->inode_number = inode->i_ino; in empty_meta_index()
137 meta->offset = offset; in empty_meta_index()
138 meta->skip = skip; in empty_meta_index()
139 meta->entries = 0; in empty_meta_index()
140 meta->locked = 1; in empty_meta_index()
143 mutex_unlock(&msblk->meta_index_mutex); in empty_meta_index()
150 struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info; in release_meta_index()
151 mutex_lock(&msblk->meta_index_mutex); in release_meta_index()
152 meta->locked = 0; in release_meta_index()
153 mutex_unlock(&msblk->meta_index_mutex); in release_meta_index()
158 * Read the next n blocks from the block list, starting from
159 * metadata block <start_block, offset>.
165 long long block = 0; in read_indexes() local
170 return -ENOMEM; in read_indexes()
179 ERROR("read_indexes: reading block [%llx:%x]\n", in read_indexes()
190 block += SQUASHFS_COMPRESSED_SIZE_BLOCK(size); in read_indexes()
192 n -= blocks; in read_indexes()
196 return block; in read_indexes()
205 * Each cache index slot has SQUASHFS_META_ENTRIES, each of which
206 * can cache one index -> datablock/blocklist-block mapping. We wish
210 * limited to the size of the metadata cache (SQUASHFS_CACHED_BLKS) to ensure
211 * the number of metadata blocks that need to be read fits into the cache.
219 return min((u64) SQUASHFS_CACHED_BLKS - 1, skip + 1); in calculate_skip()
224 * Search and grow the index cache for the specified inode, returning the
225 * on-disk locations of the datablock and block list metadata block
226 * <index_block, index_offset> for index (scaled to nearest cache index).
231 struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info; in fill_meta_index()
232 int skip = calculate_skip(i_size_read(inode) >> msblk->block_log); in fill_meta_index()
236 u64 cur_index_block = squashfs_i(inode)->block_list_start; in fill_meta_index()
237 int cur_offset = squashfs_i(inode)->offset; in fill_meta_index()
238 u64 cur_data_block = squashfs_i(inode)->start; in fill_meta_index()
242 * Scale index to cache index (cache slot entry) in fill_meta_index()
254 offset = index < meta->offset + meta->entries ? index : in fill_meta_index()
255 meta->offset + meta->entries - 1; in fill_meta_index()
256 meta_entry = &meta->meta_entry[offset - meta->offset]; in fill_meta_index()
257 cur_index_block = meta_entry->index_block + in fill_meta_index()
258 msblk->inode_table; in fill_meta_index()
259 cur_offset = meta_entry->offset; in fill_meta_index()
260 cur_data_block = meta_entry->data_block; in fill_meta_index()
261 TRACE("get_meta_index: offset %d, meta->offset %d, " in fill_meta_index()
262 "meta->entries %d\n", offset, meta->offset, in fill_meta_index()
263 meta->entries); in fill_meta_index()
270 * If necessary grow cache slot by reading block list. Cache in fill_meta_index()
274 for (i = meta->offset + meta->entries; i <= index && in fill_meta_index()
275 i < meta->offset + SQUASHFS_META_ENTRIES; i++) { in fill_meta_index()
277 long long res = read_indexes(inode->i_sb, blocks, in fill_meta_index()
281 if (meta->entries == 0) in fill_meta_index()
286 meta->inode_number = 0; in fill_meta_index()
292 meta_entry = &meta->meta_entry[i - meta->offset]; in fill_meta_index()
293 meta_entry->index_block = cur_index_block - in fill_meta_index()
294 msblk->inode_table; in fill_meta_index()
295 meta_entry->offset = cur_offset; in fill_meta_index()
296 meta_entry->data_block = cur_data_block; in fill_meta_index()
297 meta->entries++; in fill_meta_index()
301 TRACE("get_meta_index: meta->offset %d, meta->entries %d\n", in fill_meta_index()
302 meta->offset, meta->entries); in fill_meta_index()
313 * Scale cache index (cache slot entry) to index in fill_meta_index()
324 * Get the on-disk location and compressed size of the datablock
327 static int read_blocklist(struct inode *inode, int index, u64 *block) in read_blocklist() argument
333 int res = fill_meta_index(inode, index, &start, &offset, block); in read_blocklist()
336 " 0x%x, block 0x%llx\n", res, index, start, offset, in read_blocklist()
337 *block); in read_blocklist()
345 * meta_index cache works at a higher granularity). Read any in read_blocklist()
346 * extra block indexes needed. in read_blocklist()
349 blks = read_indexes(inode->i_sb, index - res, &start, &offset); in read_blocklist()
352 *block += blks; in read_blocklist()
356 * Read length of block specified by index. in read_blocklist()
358 res = squashfs_read_metadata(inode->i_sb, &size, &start, &offset, in read_blocklist()
374 memset(pageaddr + copied, 0, PAGE_SIZE - copied); in squashfs_fill_page()
382 /* Copy data into page cache */
387 struct address_space *mapping = folio->mapping; in squashfs_copy_cache()
388 struct inode *inode = mapping->host; in squashfs_copy_cache()
389 struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info; in squashfs_copy_cache()
390 int i, mask = (1 << (msblk->block_log - PAGE_SHIFT)) - 1; in squashfs_copy_cache()
391 int start_index = folio->index & ~mask, end_index = start_index | mask; in squashfs_copy_cache()
395 * many PAGE_SIZE pages (default block size is 128 KiB) explicitly in squashfs_copy_cache()
396 * grab the pages from the page cache, except for the page that we've in squashfs_copy_cache()
400 bytes -= PAGE_SIZE, offset += PAGE_SIZE) { in squashfs_copy_cache()
407 push_folio = (i == folio->index) ? folio : in squashfs_copy_cache()
421 if (i != folio->index) in squashfs_copy_cache()
426 /* Read datablock stored packed inside a fragment (tail-end packed block) */
429 struct inode *inode = folio->mapping->host; in squashfs_readpage_fragment()
430 struct squashfs_cache_entry *buffer = squashfs_get_fragment(inode->i_sb, in squashfs_readpage_fragment()
431 squashfs_i(inode)->fragment_block, in squashfs_readpage_fragment()
432 squashfs_i(inode)->fragment_size); in squashfs_readpage_fragment()
433 int res = buffer->error; in squashfs_readpage_fragment()
436 ERROR("Unable to read page, block %llx, size %x\n", in squashfs_readpage_fragment()
437 squashfs_i(inode)->fragment_block, in squashfs_readpage_fragment()
438 squashfs_i(inode)->fragment_size); in squashfs_readpage_fragment()
441 squashfs_i(inode)->fragment_offset); in squashfs_readpage_fragment()
455 struct inode *inode = folio->mapping->host; in squashfs_read_folio()
456 struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info; in squashfs_read_folio()
457 int index = folio->index >> (msblk->block_log - PAGE_SHIFT); in squashfs_read_folio()
458 int file_end = i_size_read(inode) >> msblk->block_log; in squashfs_read_folio()
460 (i_size_read(inode) & (msblk->block_size - 1)) : in squashfs_read_folio()
461 msblk->block_size; in squashfs_read_folio()
464 TRACE("Entered squashfs_readpage, page index %lx, start block %llx\n", in squashfs_read_folio()
465 folio->index, squashfs_i(inode)->start); in squashfs_read_folio()
467 if (folio->index >= ((i_size_read(inode) + PAGE_SIZE - 1) >> in squashfs_read_folio()
471 if (index < file_end || squashfs_i(inode)->fragment_block == in squashfs_read_folio()
473 u64 block = 0; in squashfs_read_folio() local
475 res = read_blocklist(inode, index, &block); in squashfs_read_folio()
482 res = squashfs_readpage_block(folio, block, res, expected); in squashfs_read_folio()
499 struct inode *inode = page[0]->mapping->host; in squashfs_readahead_fragment()
500 struct squashfs_cache_entry *buffer = squashfs_get_fragment(inode->i_sb, in squashfs_readahead_fragment()
501 squashfs_i(inode)->fragment_block, in squashfs_readahead_fragment()
502 squashfs_i(inode)->fragment_size); in squashfs_readahead_fragment()
503 struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info; in squashfs_readahead_fragment()
510 if (buffer->error) in squashfs_readahead_fragment()
522 int avail = min_t(int, expected - offset, PAGE_SIZE); in squashfs_readahead_fragment()
526 squashfs_i(inode)->fragment_offset, avail); in squashfs_readahead_fragment()
542 memzero_page(last_page, bytes, PAGE_SIZE - bytes); in squashfs_readahead_fragment()
568 struct inode *inode = ractl->mapping->host; in squashfs_readahead()
569 struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info; in squashfs_readahead()
570 size_t mask = (1UL << msblk->block_log) - 1; in squashfs_readahead()
571 unsigned short shift = msblk->block_log - PAGE_SHIFT; in squashfs_readahead()
573 size_t len = readahead_length(ractl) + readahead_pos(ractl) - start; in squashfs_readahead()
578 loff_t file_end = i_size_read(inode) >> msblk->block_log; in squashfs_readahead()
589 u64 block = 0; in squashfs_readahead() local
593 expected = start >> msblk->block_log == file_end ? in squashfs_readahead()
594 (i_size_read(inode) & (msblk->block_size - 1)) : in squashfs_readahead()
595 msblk->block_size; in squashfs_readahead()
597 max_pages = (expected + PAGE_SIZE - 1) >> PAGE_SHIFT; in squashfs_readahead()
606 if (start >> msblk->block_log == file_end && in squashfs_readahead()
607 squashfs_i(inode)->fragment_block != SQUASHFS_INVALID_BLK) { in squashfs_readahead()
615 bsize = read_blocklist(inode, start >> msblk->block_log, &block); in squashfs_readahead()
624 res = squashfs_read_data(inode->i_sb, block, bsize, NULL, actor); in squashfs_readahead()
633 if (start >> msblk->block_log == file_end && bytes && last_page) in squashfs_readahead()
635 PAGE_SIZE - bytes); in squashfs_readahead()