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
19  * larger), the code implements an index cache that caches the mapping from
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
44  * Locate cache slot in range [offset, index] for specified inode.  If
51 	struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info;  in locate_meta_index()
52 	int i;  in locate_meta_index()  local
54 	mutex_lock(&msblk->meta_index_mutex);  in locate_meta_index()
58 	if (msblk->meta_index == NULL)  in locate_meta_index()
61 	for (i = 0; i < SQUASHFS_META_SLOTS; i++) {  in locate_meta_index()
62 		if (msblk->meta_index[i].inode_number == inode->i_ino &&  in locate_meta_index()
63 				msblk->meta_index[i].offset >= offset &&  in locate_meta_index()
64 				msblk->meta_index[i].offset <= index &&  in locate_meta_index()
65 				msblk->meta_index[i].locked == 0) {  in locate_meta_index()
66 			TRACE("locate_meta_index: entry %d, offset %d\n", i,  in locate_meta_index()
67 					msblk->meta_index[i].offset);  in locate_meta_index()
68 			meta = &msblk->meta_index[i];  in locate_meta_index()
69 			offset = meta->offset;  in locate_meta_index()
74 		meta->locked = 1;  in locate_meta_index()
77 	mutex_unlock(&msblk->meta_index_mutex);  in locate_meta_index()
84  * Find and initialise an empty cache slot for index offset.
89 	struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info;  in empty_meta_index()
91 	int i;  in empty_meta_index()  local
93 	mutex_lock(&msblk->meta_index_mutex);  in empty_meta_index()
97 	if (msblk->meta_index == NULL) {  in empty_meta_index()
99 		 * First time cache index has been used, allocate and  in empty_meta_index()
100 		 * initialise.  The cache index could be allocated at  in empty_meta_index()
104 		msblk->meta_index = kcalloc(SQUASHFS_META_SLOTS,  in empty_meta_index()
105 			sizeof(*(msblk->meta_index)), GFP_KERNEL);  in empty_meta_index()
106 		if (msblk->meta_index == NULL) {  in empty_meta_index()
110 		for (i = 0; i < SQUASHFS_META_SLOTS; i++) {  in empty_meta_index()
111 			msblk->meta_index[i].inode_number = 0;  in empty_meta_index()
112 			msblk->meta_index[i].locked = 0;  in empty_meta_index()
114 		msblk->next_meta_index = 0;  in empty_meta_index()
117 	for (i = SQUASHFS_META_SLOTS; i &&  in empty_meta_index()
118 			msblk->meta_index[msblk->next_meta_index].locked; i--)  in empty_meta_index()
119 		msblk->next_meta_index = (msblk->next_meta_index + 1) %  in empty_meta_index()
122 	if (i == 0) {  in empty_meta_index()
128 			msblk->next_meta_index,  in empty_meta_index()
129 			&msblk->meta_index[msblk->next_meta_index]);  in empty_meta_index()
131 	meta = &msblk->meta_index[msblk->next_meta_index];  in empty_meta_index()
132 	msblk->next_meta_index = (msblk->next_meta_index + 1) %  in empty_meta_index()
135 	meta->inode_number = inode->i_ino;  in empty_meta_index()
136 	meta->offset = offset;  in empty_meta_index()
137 	meta->skip = skip;  in empty_meta_index()
138 	meta->entries = 0;  in empty_meta_index()
139 	meta->locked = 1;  in empty_meta_index()
142 	mutex_unlock(&msblk->meta_index_mutex);  in empty_meta_index()
149 	struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info;  in release_meta_index()
150 	mutex_lock(&msblk->meta_index_mutex);  in release_meta_index()
151 	meta->locked = 0;  in release_meta_index()
152 	mutex_unlock(&msblk->meta_index_mutex);  in release_meta_index()
163 	int err, i;  in read_indexes()  local
169 		return -ENOMEM;  in read_indexes()
183 		for (i = 0; i < blocks; i++) {  in read_indexes()
184 			int size = squashfs_block_size(blist[i]);  in read_indexes()  local
185 			if (size < 0) {  in read_indexes()
186 				err = size;  in read_indexes()
189 			block += SQUASHFS_COMPRESSED_SIZE_BLOCK(size);  in read_indexes()
191 		n -= blocks;  in read_indexes()
204  * Each cache index slot has SQUASHFS_META_ENTRIES, each of which
205  * can cache one index -> datablock/blocklist-block mapping.  We wish
209  * limited to the size of the metadata cache (SQUASHFS_CACHED_BLKS) to ensure
210  * the number of metadata blocks that need to be read fits into the cache.
218 	return min(SQUASHFS_CACHED_BLKS - 1, skip + 1);  in calculate_skip()
223  * Search and grow the index cache for the specified inode, returning the
224  * on-disk locations of the datablock and block list metadata block
225  * <index_block, index_offset> for index (scaled to nearest cache index).
230 	struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info;  in fill_meta_index()
231 	int skip = calculate_skip(i_size_read(inode) >> msblk->block_log);  in fill_meta_index()
235 	u64 cur_index_block = squashfs_i(inode)->block_list_start;  in fill_meta_index()
236 	int cur_offset = squashfs_i(inode)->offset;  in fill_meta_index()
237 	u64 cur_data_block = squashfs_i(inode)->start;  in fill_meta_index()
238 	int err, i;  in fill_meta_index()  local
241 	 * Scale index to cache index (cache slot entry)  in fill_meta_index()
253 			offset = index < meta->offset + meta->entries ? index :  in fill_meta_index()
254 				meta->offset + meta->entries - 1;  in fill_meta_index()
255 			meta_entry = &meta->meta_entry[offset - meta->offset];  in fill_meta_index()
256 			cur_index_block = meta_entry->index_block +  in fill_meta_index()
257 				msblk->inode_table;  in fill_meta_index()
258 			cur_offset = meta_entry->offset;  in fill_meta_index()
259 			cur_data_block = meta_entry->data_block;  in fill_meta_index()
260 			TRACE("get_meta_index: offset %d, meta->offset %d, "  in fill_meta_index()
261 				"meta->entries %d\n", offset, meta->offset,  in fill_meta_index()
262 				meta->entries);  in fill_meta_index()
269 		 * If necessary grow cache slot by reading block list.  Cache  in fill_meta_index()
273 		for (i = meta->offset + meta->entries; i <= index &&  in fill_meta_index()
274 				i < meta->offset + SQUASHFS_META_ENTRIES; i++) {  in fill_meta_index()
276 			long long res = read_indexes(inode->i_sb, blocks,  in fill_meta_index()
280 				if (meta->entries == 0)  in fill_meta_index()
285 					meta->inode_number = 0;  in fill_meta_index()
291 			meta_entry = &meta->meta_entry[i - meta->offset];  in fill_meta_index()
292 			meta_entry->index_block = cur_index_block -  in fill_meta_index()
293 				msblk->inode_table;  in fill_meta_index()
294 			meta_entry->offset = cur_offset;  in fill_meta_index()
295 			meta_entry->data_block = cur_data_block;  in fill_meta_index()
296 			meta->entries++;  in fill_meta_index()
300 		TRACE("get_meta_index: meta->offset %d, meta->entries %d\n",  in fill_meta_index()
301 				meta->offset, meta->entries);  in fill_meta_index()
312 	 * Scale cache index (cache slot entry) to index  in fill_meta_index()
323  * Get the on-disk location and compressed size of the datablock
331 	__le32 size;  in read_blocklist()  local
344 	 * meta_index cache works at a higher granularity).  Read any  in read_blocklist()
348 		blks = read_indexes(inode->i_sb, index - res, &start, &offset);  in read_blocklist()
357 	res = squashfs_read_metadata(inode->i_sb, &size, &start, &offset,  in read_blocklist()
358 			sizeof(size));  in read_blocklist()
361 	return squashfs_block_size(size);  in read_blocklist()
371 	memset(pageaddr + copied, 0, PAGE_SIZE - copied);  in squashfs_fill_page()
381 /* Copy data into page cache  */
385 	struct inode *inode = page->mapping->host;  in squashfs_copy_cache()
386 	struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info;  in squashfs_copy_cache()
387 	int i, mask = (1 << (msblk->block_log - PAGE_SHIFT)) - 1;  in squashfs_copy_cache()  local
388 	int start_index = page->index & ~mask, end_index = start_index | mask;  in squashfs_copy_cache()
392 	 * many PAGE_SIZE pages (default block size is 128 KiB) explicitly  in squashfs_copy_cache()
393 	 * grab the pages from the page cache, except for the page that we've  in squashfs_copy_cache()
396 	for (i = start_index; i <= end_index && bytes > 0; i++,  in squashfs_copy_cache()
397 			bytes -= PAGE_SIZE, offset += PAGE_SIZE) {  in squashfs_copy_cache()
401 		TRACE("bytes %d, i %d, available_bytes %d\n", bytes, i, avail);  in squashfs_copy_cache()
403 		push_page = (i == page->index) ? page :  in squashfs_copy_cache()
404 			grab_cache_page_nowait(page->mapping, i);  in squashfs_copy_cache()
415 		if (i != page->index)  in squashfs_copy_cache()
420 /* Read datablock stored packed inside a fragment (tail-end packed block) */
423 	struct inode *inode = page->mapping->host;  in squashfs_readpage_fragment()
424 	struct squashfs_cache_entry *buffer = squashfs_get_fragment(inode->i_sb,  in squashfs_readpage_fragment()
425 		squashfs_i(inode)->fragment_block,  in squashfs_readpage_fragment()
426 		squashfs_i(inode)->fragment_size);  in squashfs_readpage_fragment()
427 	int res = buffer->error;  in squashfs_readpage_fragment()
430 		ERROR("Unable to read page, block %llx, size %x\n",  in squashfs_readpage_fragment()
431 			squashfs_i(inode)->fragment_block,  in squashfs_readpage_fragment()
432 			squashfs_i(inode)->fragment_size);  in squashfs_readpage_fragment()
435 			squashfs_i(inode)->fragment_offset);  in squashfs_readpage_fragment()
449 	struct inode *inode = page->mapping->host;  in squashfs_readpage()
450 	struct squashfs_sb_info *msblk = inode->i_sb->s_fs_info;  in squashfs_readpage()
451 	int index = page->index >> (msblk->block_log - PAGE_SHIFT);  in squashfs_readpage()
452 	int file_end = i_size_read(inode) >> msblk->block_log;  in squashfs_readpage()
454 			(i_size_read(inode) & (msblk->block_size - 1)) :  in squashfs_readpage()
455 			 msblk->block_size;  in squashfs_readpage()
460 				page->index, squashfs_i(inode)->start);  in squashfs_readpage()
462 	if (page->index >= ((i_size_read(inode) + PAGE_SIZE - 1) >>  in squashfs_readpage()
466 	if (index < file_end || squashfs_i(inode)->fragment_block ==  in squashfs_readpage()