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()
53 	int i;  in locate_meta_index()  local
55 	mutex_lock(&msblk->meta_index_mutex);  in locate_meta_index()
59 	if (msblk->meta_index == NULL)  in locate_meta_index()
62 	for (i = 0; i < SQUASHFS_META_SLOTS; i++) {  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()
67 			TRACE("locate_meta_index: entry %d, offset %d\n", i,  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()
92 	int i;  in empty_meta_index()  local
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()
111 		for (i = 0; i < SQUASHFS_META_SLOTS; i++) {  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()
118 	for (i = SQUASHFS_META_SLOTS; i &&  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()
123 	if (i == 0) {  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>.
164 	int err, i;  in read_indexes()  local
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()
184 		for (i = 0; i < blocks; i++) {  in read_indexes()
185 			int size = squashfs_block_size(blist[i]);  in read_indexes()  local
186 			if (size < 0) {  in read_indexes()
187 				err = size;  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()
239 	int err, i;  in fill_meta_index()  local
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()
314 	 * Scale cache index (cache slot entry) to index  in fill_meta_index()
325  * Get the on-disk location and compressed size of the datablock
329 	int *offset, u64 *block)  in read_blocklist_ptrs()  argument
332 	__le32 size;  in read_blocklist_ptrs()  local
333 	int res = fill_meta_index(inode, index, start, offset, block);  in read_blocklist_ptrs()
335 	TRACE("read_blocklist: res %d, index %d, start 0x%llx, offset 0x%x, block 0x%llx\n",  in read_blocklist_ptrs()
336 				res, index, *start, *offset, block ? *block : 0);  in read_blocklist_ptrs()
344 	 * meta_index cache works at a higher granularity).  Read any  in read_blocklist_ptrs()
345 	 * extra block indexes needed.  in read_blocklist_ptrs()
348 		blks = read_indexes(inode->i_sb, index - res, start, offset);  in read_blocklist_ptrs()
351 		if (block)  in read_blocklist_ptrs()
352 			*block += blks;  in read_blocklist_ptrs()
356 	 * Read length of block specified by index.  in read_blocklist_ptrs()
358 	res = squashfs_read_metadata(inode->i_sb, &size, start, offset,  in read_blocklist_ptrs()
359 			sizeof(size));  in read_blocklist_ptrs()
362 	return squashfs_block_size(size);  in read_blocklist_ptrs()
365 static inline int read_blocklist(struct inode *inode, int index, u64 *block)  in read_blocklist()  argument
370 	return read_blocklist_ptrs(inode, index, &start, &offset, block);  in read_blocklist()
382 	memset(pageaddr + copied, 0, PAGE_SIZE - copied);  in squashfs_fill_page()
390 /* Copy data into page cache  */
395 	struct address_space *mapping = folio->mapping;  in squashfs_copy_cache()
396 	struct inode *inode = mapping->host;  in squashfs_copy_cache()
397 	struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info;  in squashfs_copy_cache()
398 	int i, mask = (1 << (msblk->block_log - PAGE_SHIFT)) - 1;  in squashfs_copy_cache()  local
399 	int start_index = folio->index & ~mask, end_index = start_index | mask;  in squashfs_copy_cache()
403 	 * many PAGE_SIZE pages (default block size is 128 KiB) explicitly  in squashfs_copy_cache()
404 	 * grab the pages from the page cache, except for the page that we've  in squashfs_copy_cache()
407 	for (i = start_index; i <= end_index && bytes > 0; i++,  in squashfs_copy_cache()
408 			bytes -= PAGE_SIZE, offset += PAGE_SIZE) {  in squashfs_copy_cache()
413 		TRACE("bytes %zu, i %d, available_bytes %zu\n", bytes, i, avail);  in squashfs_copy_cache()
415 		push_folio = (i == folio->index) ? folio :  in squashfs_copy_cache()
416 			__filemap_get_folio(mapping, i,  in squashfs_copy_cache()
429 		if (i != folio->index)  in squashfs_copy_cache()
434 /* Read datablock stored packed inside a fragment (tail-end packed block) */
437 	struct inode *inode = folio->mapping->host;  in squashfs_readpage_fragment()
438 	struct squashfs_cache_entry *buffer = squashfs_get_fragment(inode->i_sb,  in squashfs_readpage_fragment()
439 		squashfs_i(inode)->fragment_block,  in squashfs_readpage_fragment()
440 		squashfs_i(inode)->fragment_size);  in squashfs_readpage_fragment()
441 	int res = buffer->error;  in squashfs_readpage_fragment()
444 		ERROR("Unable to read page, block %llx, size %x\n",  in squashfs_readpage_fragment()
445 			squashfs_i(inode)->fragment_block,  in squashfs_readpage_fragment()
446 			squashfs_i(inode)->fragment_size);  in squashfs_readpage_fragment()
449 			squashfs_i(inode)->fragment_offset);  in squashfs_readpage_fragment()
463 	struct inode *inode = folio->mapping->host;  in squashfs_read_folio()
464 	struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info;  in squashfs_read_folio()
465 	int index = folio->index >> (msblk->block_log - PAGE_SHIFT);  in squashfs_read_folio()
466 	int file_end = i_size_read(inode) >> msblk->block_log;  in squashfs_read_folio()
468 			(i_size_read(inode) & (msblk->block_size - 1)) :  in squashfs_read_folio()
469 			 msblk->block_size;  in squashfs_read_folio()
472 	TRACE("Entered squashfs_readpage, page index %lx, start block %llx\n",  in squashfs_read_folio()
473 				folio->index, squashfs_i(inode)->start);  in squashfs_read_folio()
475 	if (folio->index >= ((i_size_read(inode) + PAGE_SIZE - 1) >>  in squashfs_read_folio()
479 	if (index < file_end || squashfs_i(inode)->fragment_block ==  in squashfs_read_folio()
481 		u64 block = 0;  in squashfs_read_folio()  local
483 		res = read_blocklist(inode, index, &block);  in squashfs_read_folio()
490 			res = squashfs_readpage_block(folio, block, res, expected);  in squashfs_read_folio()
507 	struct squashfs_cache_entry *buffer = squashfs_get_fragment(inode->i_sb,  in squashfs_readahead_fragment()
508 		squashfs_i(inode)->fragment_block,  in squashfs_readahead_fragment()
509 		squashfs_i(inode)->fragment_size);  in squashfs_readahead_fragment()
510 	struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info;  in squashfs_readahead_fragment()
511 	int i, bytes, copied;  in squashfs_readahead_fragment()  local
517 	if (buffer->error)  in squashfs_readahead_fragment()
529 		int avail = min_t(int, expected - offset, PAGE_SIZE);  in squashfs_readahead_fragment()
533 					squashfs_i(inode)->fragment_offset, avail);  in squashfs_readahead_fragment()
549 			memzero_page(last_page, bytes, PAGE_SIZE - bytes);  in squashfs_readahead_fragment()
551 		for (i = 0; i < pages; i++) {  in squashfs_readahead_fragment()
552 			flush_dcache_page(page[i]);  in squashfs_readahead_fragment()
553 			SetPageUptodate(page[i]);  in squashfs_readahead_fragment()
557 	for (i = 0; i < pages; i++) {  in squashfs_readahead_fragment()
558 		unlock_page(page[i]);  in squashfs_readahead_fragment()
559 		put_page(page[i]);  in squashfs_readahead_fragment()
575 	struct inode *inode = ractl->mapping->host;  in squashfs_readahead()
576 	struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info;  in squashfs_readahead()
577 	size_t mask = (1UL << msblk->block_log) - 1;  in squashfs_readahead()
578 	unsigned short shift = msblk->block_log - PAGE_SHIFT;  in squashfs_readahead()
580 	size_t len = readahead_length(ractl) + readahead_pos(ractl) - start;  in squashfs_readahead()
584 	int i;  in squashfs_readahead()  local
585 	loff_t file_end = i_size_read(inode) >> msblk->block_log;  in squashfs_readahead()
596 		u64 block = 0;  in squashfs_readahead()  local
600 		expected = start >> msblk->block_log == file_end ?  in squashfs_readahead()
601 			   (i_size_read(inode) & (msblk->block_size - 1)) :  in squashfs_readahead()
602 			    msblk->block_size;  in squashfs_readahead()
604 		max_pages = (expected + PAGE_SIZE - 1) >> PAGE_SHIFT;  in squashfs_readahead()
613 		if (start >> msblk->block_log == file_end &&  in squashfs_readahead()
614 				squashfs_i(inode)->fragment_block != SQUASHFS_INVALID_BLK) {  in squashfs_readahead()
622 		bsize = read_blocklist(inode, start >> msblk->block_log, &block);  in squashfs_readahead()
631 		res = squashfs_read_data(inode->i_sb, block, bsize, NULL, actor);  in squashfs_readahead()
640 			if (start >> msblk->block_log == file_end && bytes && last_page)  in squashfs_readahead()
642 					     PAGE_SIZE - bytes);  in squashfs_readahead()
644 			for (i = 0; i < nr_pages; i++) {  in squashfs_readahead()
645 				flush_dcache_page(pages[i]);  in squashfs_readahead()
646 				SetPageUptodate(pages[i]);  in squashfs_readahead()
650 		for (i = 0; i < nr_pages; i++) {  in squashfs_readahead()
651 			unlock_page(pages[i]);  in squashfs_readahead()
652 			put_page(pages[i]);  in squashfs_readahead()
662 	for (i = 0; i < nr_pages; i++) {  in squashfs_readahead()
663 		unlock_page(pages[i]);  in squashfs_readahead()
664 		put_page(pages[i]);  in squashfs_readahead()
671 	struct inode *inode = file->f_mapping->host;  in seek_hole_data()
672 	struct super_block *sb = inode->i_sb;  in seek_hole_data()
673 	struct squashfs_sb_info *msblk = sb->s_fs_info;  in seek_hole_data()
674 	u64 start, index = offset >> msblk->block_log;  in seek_hole_data()
675 	u64 file_end = (i_size_read(inode) + msblk->block_size - 1) >> msblk->block_log;  in seek_hole_data()
681 		return -ENXIO;  in seek_hole_data()
685 			squashfs_i(inode)->fragment_block != SQUASHFS_INVALID_BLK) {  in seek_hole_data()
709 		return -ENOMEM;  in seek_hole_data()
713 		int i, indexes = min(file_end - index, SQUASHFS_SCAN_INDEXES);  in seek_hole_data()  local
719 		for (i = 0; i < indexes; i++) {  in seek_hole_data()
720 			length = squashfs_block_size(blist[i]);  in seek_hole_data()
726 			/* does this block match desired whence value? */  in seek_hole_data()
729 				offset = (index + i) << msblk->block_log;  in seek_hole_data()
740 		offset = -ENXIO;  in seek_hole_data()
752 	struct inode *inode = file->f_mapping->host;  in squashfs_llseek()
766 	return vfs_setpos(file, offset, inode->i_sb->s_maxbytes);  in squashfs_llseek()