168252eb5SThomas Gleixner // SPDX-License-Identifier: GPL-2.0-or-later 2e2780ab1SPhillip Lougher /* 3e2780ab1SPhillip Lougher * Squashfs - a compressed read only filesystem for Linux 4e2780ab1SPhillip Lougher * 5e2780ab1SPhillip Lougher * Copyright (c) 2002, 2003, 2004, 2005, 2006, 2007, 2008 6d7f2ff67SPhillip Lougher * Phillip Lougher <phillip@squashfs.org.uk> 7e2780ab1SPhillip Lougher * 8e2780ab1SPhillip Lougher * block.c 9e2780ab1SPhillip Lougher */ 10e2780ab1SPhillip Lougher 11e2780ab1SPhillip Lougher /* 12e2780ab1SPhillip Lougher * This file implements the low-level routines to read and decompress 13e2780ab1SPhillip Lougher * datablocks and metadata blocks. 14e2780ab1SPhillip Lougher */ 15e2780ab1SPhillip Lougher 1693e72b3cSPhilippe Liard #include <linux/blkdev.h> 17e2780ab1SPhillip Lougher #include <linux/fs.h> 18e2780ab1SPhillip Lougher #include <linux/vfs.h> 19e2780ab1SPhillip Lougher #include <linux/slab.h> 20*e994f5b6SVincent Whitchurch #include <linux/pagemap.h> 21e2780ab1SPhillip Lougher #include <linux/string.h> 222f8b5444SChristoph Hellwig #include <linux/bio.h> 23e2780ab1SPhillip Lougher 24e2780ab1SPhillip Lougher #include "squashfs_fs.h" 25e2780ab1SPhillip Lougher #include "squashfs_fs_sb.h" 26e2780ab1SPhillip Lougher #include "squashfs.h" 274c0f0bb2SPhillip Lougher #include "decompressor.h" 28846b730eSPhillip Lougher #include "page_actor.h" 29e2780ab1SPhillip Lougher 30e2780ab1SPhillip Lougher /* 3193e72b3cSPhilippe Liard * Returns the amount of bytes copied to the page actor. 32e2780ab1SPhillip Lougher */ 3393e72b3cSPhilippe Liard static int copy_bio_to_actor(struct bio *bio, 3493e72b3cSPhilippe Liard struct squashfs_page_actor *actor, 3593e72b3cSPhilippe Liard int offset, int req_length) 3693e72b3cSPhilippe Liard { 37f268eeddSPhillip Lougher void *actor_addr; 3893e72b3cSPhilippe Liard struct bvec_iter_all iter_all = {}; 3993e72b3cSPhilippe Liard struct bio_vec *bvec = bvec_init_iter_all(&iter_all); 4093e72b3cSPhilippe Liard int copied_bytes = 0; 4193e72b3cSPhilippe Liard int actor_offset = 0; 4293e72b3cSPhilippe Liard 43f268eeddSPhillip Lougher squashfs_actor_nobuff(actor); 44f268eeddSPhillip Lougher actor_addr = squashfs_first_page(actor); 45f268eeddSPhillip Lougher 4693e72b3cSPhilippe Liard if (WARN_ON_ONCE(!bio_next_segment(bio, &iter_all))) 4793e72b3cSPhilippe Liard return 0; 4893e72b3cSPhilippe Liard 4993e72b3cSPhilippe Liard while (copied_bytes < req_length) { 5093e72b3cSPhilippe Liard int bytes_to_copy = min_t(int, bvec->bv_len - offset, 5193e72b3cSPhilippe Liard PAGE_SIZE - actor_offset); 5293e72b3cSPhilippe Liard 5393e72b3cSPhilippe Liard bytes_to_copy = min_t(int, bytes_to_copy, 5493e72b3cSPhilippe Liard req_length - copied_bytes); 55f268eeddSPhillip Lougher if (!IS_ERR(actor_addr)) 56f268eeddSPhillip Lougher memcpy(actor_addr + actor_offset, bvec_virt(bvec) + 57f268eeddSPhillip Lougher offset, bytes_to_copy); 5893e72b3cSPhilippe Liard 5993e72b3cSPhilippe Liard actor_offset += bytes_to_copy; 6093e72b3cSPhilippe Liard copied_bytes += bytes_to_copy; 6193e72b3cSPhilippe Liard offset += bytes_to_copy; 6293e72b3cSPhilippe Liard 6393e72b3cSPhilippe Liard if (actor_offset >= PAGE_SIZE) { 6493e72b3cSPhilippe Liard actor_addr = squashfs_next_page(actor); 6593e72b3cSPhilippe Liard if (!actor_addr) 6693e72b3cSPhilippe Liard break; 6793e72b3cSPhilippe Liard actor_offset = 0; 6893e72b3cSPhilippe Liard } 6993e72b3cSPhilippe Liard if (offset >= bvec->bv_len) { 7093e72b3cSPhilippe Liard if (!bio_next_segment(bio, &iter_all)) 7193e72b3cSPhilippe Liard break; 7293e72b3cSPhilippe Liard offset = 0; 7393e72b3cSPhilippe Liard } 7493e72b3cSPhilippe Liard } 7593e72b3cSPhilippe Liard squashfs_finish_page(actor); 7693e72b3cSPhilippe Liard return copied_bytes; 7793e72b3cSPhilippe Liard } 7893e72b3cSPhilippe Liard 79*e994f5b6SVincent Whitchurch static int squashfs_bio_read_cached(struct bio *fullbio, 80*e994f5b6SVincent Whitchurch struct address_space *cache_mapping, u64 index, int length, 81*e994f5b6SVincent Whitchurch u64 read_start, u64 read_end, int page_count) 82*e994f5b6SVincent Whitchurch { 83*e994f5b6SVincent Whitchurch struct page *head_to_cache = NULL, *tail_to_cache = NULL; 84*e994f5b6SVincent Whitchurch struct block_device *bdev = fullbio->bi_bdev; 85*e994f5b6SVincent Whitchurch int start_idx = 0, end_idx = 0; 86*e994f5b6SVincent Whitchurch struct bvec_iter_all iter_all; 87*e994f5b6SVincent Whitchurch struct bio *bio = NULL; 88*e994f5b6SVincent Whitchurch struct bio_vec *bv; 89*e994f5b6SVincent Whitchurch int idx = 0; 90*e994f5b6SVincent Whitchurch int err = 0; 91*e994f5b6SVincent Whitchurch 92*e994f5b6SVincent Whitchurch bio_for_each_segment_all(bv, fullbio, iter_all) { 93*e994f5b6SVincent Whitchurch struct page *page = bv->bv_page; 94*e994f5b6SVincent Whitchurch 95*e994f5b6SVincent Whitchurch if (page->mapping == cache_mapping) { 96*e994f5b6SVincent Whitchurch idx++; 97*e994f5b6SVincent Whitchurch continue; 98*e994f5b6SVincent Whitchurch } 99*e994f5b6SVincent Whitchurch 100*e994f5b6SVincent Whitchurch /* 101*e994f5b6SVincent Whitchurch * We only use this when the device block size is the same as 102*e994f5b6SVincent Whitchurch * the page size, so read_start and read_end cover full pages. 103*e994f5b6SVincent Whitchurch * 104*e994f5b6SVincent Whitchurch * Compare these to the original required index and length to 105*e994f5b6SVincent Whitchurch * only cache pages which were requested partially, since these 106*e994f5b6SVincent Whitchurch * are the ones which are likely to be needed when reading 107*e994f5b6SVincent Whitchurch * adjacent blocks. 108*e994f5b6SVincent Whitchurch */ 109*e994f5b6SVincent Whitchurch if (idx == 0 && index != read_start) 110*e994f5b6SVincent Whitchurch head_to_cache = page; 111*e994f5b6SVincent Whitchurch else if (idx == page_count - 1 && index + length != read_end) 112*e994f5b6SVincent Whitchurch tail_to_cache = page; 113*e994f5b6SVincent Whitchurch 114*e994f5b6SVincent Whitchurch if (!bio || idx != end_idx) { 115*e994f5b6SVincent Whitchurch struct bio *new = bio_alloc_clone(bdev, fullbio, 116*e994f5b6SVincent Whitchurch GFP_NOIO, &fs_bio_set); 117*e994f5b6SVincent Whitchurch 118*e994f5b6SVincent Whitchurch if (bio) { 119*e994f5b6SVincent Whitchurch bio_trim(bio, start_idx * PAGE_SECTORS, 120*e994f5b6SVincent Whitchurch (end_idx - start_idx) * PAGE_SECTORS); 121*e994f5b6SVincent Whitchurch bio_chain(bio, new); 122*e994f5b6SVincent Whitchurch submit_bio(bio); 123*e994f5b6SVincent Whitchurch } 124*e994f5b6SVincent Whitchurch 125*e994f5b6SVincent Whitchurch bio = new; 126*e994f5b6SVincent Whitchurch start_idx = idx; 127*e994f5b6SVincent Whitchurch } 128*e994f5b6SVincent Whitchurch 129*e994f5b6SVincent Whitchurch idx++; 130*e994f5b6SVincent Whitchurch end_idx = idx; 131*e994f5b6SVincent Whitchurch } 132*e994f5b6SVincent Whitchurch 133*e994f5b6SVincent Whitchurch if (bio) { 134*e994f5b6SVincent Whitchurch bio_trim(bio, start_idx * PAGE_SECTORS, 135*e994f5b6SVincent Whitchurch (end_idx - start_idx) * PAGE_SECTORS); 136*e994f5b6SVincent Whitchurch err = submit_bio_wait(bio); 137*e994f5b6SVincent Whitchurch bio_put(bio); 138*e994f5b6SVincent Whitchurch } 139*e994f5b6SVincent Whitchurch 140*e994f5b6SVincent Whitchurch if (err) 141*e994f5b6SVincent Whitchurch return err; 142*e994f5b6SVincent Whitchurch 143*e994f5b6SVincent Whitchurch if (head_to_cache) { 144*e994f5b6SVincent Whitchurch int ret = add_to_page_cache_lru(head_to_cache, cache_mapping, 145*e994f5b6SVincent Whitchurch read_start >> PAGE_SHIFT, 146*e994f5b6SVincent Whitchurch GFP_NOIO); 147*e994f5b6SVincent Whitchurch 148*e994f5b6SVincent Whitchurch if (!ret) { 149*e994f5b6SVincent Whitchurch SetPageUptodate(head_to_cache); 150*e994f5b6SVincent Whitchurch unlock_page(head_to_cache); 151*e994f5b6SVincent Whitchurch } 152*e994f5b6SVincent Whitchurch 153*e994f5b6SVincent Whitchurch } 154*e994f5b6SVincent Whitchurch 155*e994f5b6SVincent Whitchurch if (tail_to_cache) { 156*e994f5b6SVincent Whitchurch int ret = add_to_page_cache_lru(tail_to_cache, cache_mapping, 157*e994f5b6SVincent Whitchurch (read_end >> PAGE_SHIFT) - 1, 158*e994f5b6SVincent Whitchurch GFP_NOIO); 159*e994f5b6SVincent Whitchurch 160*e994f5b6SVincent Whitchurch if (!ret) { 161*e994f5b6SVincent Whitchurch SetPageUptodate(tail_to_cache); 162*e994f5b6SVincent Whitchurch unlock_page(tail_to_cache); 163*e994f5b6SVincent Whitchurch } 164*e994f5b6SVincent Whitchurch } 165*e994f5b6SVincent Whitchurch 166*e994f5b6SVincent Whitchurch return 0; 167*e994f5b6SVincent Whitchurch } 168*e994f5b6SVincent Whitchurch 16993e72b3cSPhilippe Liard static int squashfs_bio_read(struct super_block *sb, u64 index, int length, 17093e72b3cSPhilippe Liard struct bio **biop, int *block_offset) 171e2780ab1SPhillip Lougher { 172e2780ab1SPhillip Lougher struct squashfs_sb_info *msblk = sb->s_fs_info; 173*e994f5b6SVincent Whitchurch struct address_space *cache_mapping = msblk->cache_mapping; 17493e72b3cSPhilippe Liard const u64 read_start = round_down(index, msblk->devblksize); 17593e72b3cSPhilippe Liard const sector_t block = read_start >> msblk->devblksize_log2; 17693e72b3cSPhilippe Liard const u64 read_end = round_up(index + length, msblk->devblksize); 17793e72b3cSPhilippe Liard const sector_t block_end = read_end >> msblk->devblksize_log2; 17893e72b3cSPhilippe Liard int offset = read_start - round_down(index, PAGE_SIZE); 17993e72b3cSPhilippe Liard int total_len = (block_end - block) << msblk->devblksize_log2; 18093e72b3cSPhilippe Liard const int page_count = DIV_ROUND_UP(total_len + offset, PAGE_SIZE); 18193e72b3cSPhilippe Liard int error, i; 18293e72b3cSPhilippe Liard struct bio *bio; 183e2780ab1SPhillip Lougher 184066ff571SChristoph Hellwig bio = bio_kmalloc(page_count, GFP_NOIO); 18593e72b3cSPhilippe Liard if (!bio) 18693e72b3cSPhilippe Liard return -ENOMEM; 187066ff571SChristoph Hellwig bio_init(bio, sb->s_bdev, bio->bi_inline_vecs, page_count, REQ_OP_READ); 18893e72b3cSPhilippe Liard bio->bi_iter.bi_sector = block * (msblk->devblksize >> SECTOR_SHIFT); 1893689456bSPhillip Lougher 19093e72b3cSPhilippe Liard for (i = 0; i < page_count; ++i) { 19193e72b3cSPhilippe Liard unsigned int len = 19293e72b3cSPhilippe Liard min_t(unsigned int, PAGE_SIZE - offset, total_len); 193*e994f5b6SVincent Whitchurch struct page *page = NULL; 194*e994f5b6SVincent Whitchurch 195*e994f5b6SVincent Whitchurch if (cache_mapping) 196*e994f5b6SVincent Whitchurch page = find_get_page(cache_mapping, 197*e994f5b6SVincent Whitchurch (read_start >> PAGE_SHIFT) + i); 198*e994f5b6SVincent Whitchurch if (!page) 199*e994f5b6SVincent Whitchurch page = alloc_page(GFP_NOIO); 20093e72b3cSPhilippe Liard 20193e72b3cSPhilippe Liard if (!page) { 20293e72b3cSPhilippe Liard error = -ENOMEM; 20393e72b3cSPhilippe Liard goto out_free_bio; 2043689456bSPhillip Lougher } 205*e994f5b6SVincent Whitchurch 206*e994f5b6SVincent Whitchurch /* 207*e994f5b6SVincent Whitchurch * Use the __ version to avoid merging since we need each page 208*e994f5b6SVincent Whitchurch * to be separate when we check for and avoid cached pages. 209*e994f5b6SVincent Whitchurch */ 210*e994f5b6SVincent Whitchurch __bio_add_page(bio, page, len, offset); 21193e72b3cSPhilippe Liard offset = 0; 21293e72b3cSPhilippe Liard total_len -= len; 213e2780ab1SPhillip Lougher } 214e2780ab1SPhillip Lougher 215*e994f5b6SVincent Whitchurch if (cache_mapping) 216*e994f5b6SVincent Whitchurch error = squashfs_bio_read_cached(bio, cache_mapping, index, 217*e994f5b6SVincent Whitchurch length, read_start, read_end, 218*e994f5b6SVincent Whitchurch page_count); 219*e994f5b6SVincent Whitchurch else 22093e72b3cSPhilippe Liard error = submit_bio_wait(bio); 22193e72b3cSPhilippe Liard if (error) 22293e72b3cSPhilippe Liard goto out_free_bio; 223e2780ab1SPhillip Lougher 22493e72b3cSPhilippe Liard *biop = bio; 22593e72b3cSPhilippe Liard *block_offset = index & ((1 << msblk->devblksize_log2) - 1); 22693e72b3cSPhilippe Liard return 0; 22793e72b3cSPhilippe Liard 22893e72b3cSPhilippe Liard out_free_bio: 22993e72b3cSPhilippe Liard bio_free_pages(bio); 230066ff571SChristoph Hellwig bio_uninit(bio); 231066ff571SChristoph Hellwig kfree(bio); 23293e72b3cSPhilippe Liard return error; 23393e72b3cSPhilippe Liard } 234e2780ab1SPhillip Lougher 235e2780ab1SPhillip Lougher /* 236e2780ab1SPhillip Lougher * Read and decompress a metadata block or datablock. Length is non-zero 237e2780ab1SPhillip Lougher * if a datablock is being read (the size is stored elsewhere in the 238e2780ab1SPhillip Lougher * filesystem), otherwise the length is obtained from the first two bytes of 239e2780ab1SPhillip Lougher * the metadata block. A bit in the length field indicates if the block 240e2780ab1SPhillip Lougher * is stored uncompressed in the filesystem (usually because compression 241ec9267b6SPhillip Lougher * generated a larger block - this does occasionally happen with compression 242ec9267b6SPhillip Lougher * algorithms). 243e2780ab1SPhillip Lougher */ 244846b730eSPhillip Lougher int squashfs_read_data(struct super_block *sb, u64 index, int length, 245846b730eSPhillip Lougher u64 *next_index, struct squashfs_page_actor *output) 246e2780ab1SPhillip Lougher { 247e2780ab1SPhillip Lougher struct squashfs_sb_info *msblk = sb->s_fs_info; 24893e72b3cSPhilippe Liard struct bio *bio = NULL; 24993e72b3cSPhilippe Liard int compressed; 25093e72b3cSPhilippe Liard int res; 25193e72b3cSPhilippe Liard int offset; 252e2780ab1SPhillip Lougher 253e2780ab1SPhillip Lougher if (length) { 254e2780ab1SPhillip Lougher /* 255e2780ab1SPhillip Lougher * Datablock. 256e2780ab1SPhillip Lougher */ 257e2780ab1SPhillip Lougher compressed = SQUASHFS_COMPRESSED_BLOCK(length); 258e2780ab1SPhillip Lougher length = SQUASHFS_COMPRESSED_SIZE_BLOCK(length); 259e2780ab1SPhillip Lougher TRACE("Block @ 0x%llx, %scompressed size %d, src size %d\n", 260846b730eSPhillip Lougher index, compressed ? "" : "un", length, output->length); 261e2780ab1SPhillip Lougher } else { 262e2780ab1SPhillip Lougher /* 263e2780ab1SPhillip Lougher * Metadata block. 264e2780ab1SPhillip Lougher */ 26593e72b3cSPhilippe Liard const u8 *data; 26693e72b3cSPhilippe Liard struct bvec_iter_all iter_all = {}; 26793e72b3cSPhilippe Liard struct bio_vec *bvec = bvec_init_iter_all(&iter_all); 268e2780ab1SPhillip Lougher 26993e72b3cSPhilippe Liard if (index + 2 > msblk->bytes_used) { 27093e72b3cSPhilippe Liard res = -EIO; 27193e72b3cSPhilippe Liard goto out; 27293e72b3cSPhilippe Liard } 27393e72b3cSPhilippe Liard res = squashfs_bio_read(sb, index, 2, &bio, &offset); 27493e72b3cSPhilippe Liard if (res) 27593e72b3cSPhilippe Liard goto out; 276e2780ab1SPhillip Lougher 27793e72b3cSPhilippe Liard if (WARN_ON_ONCE(!bio_next_segment(bio, &iter_all))) { 27893e72b3cSPhilippe Liard res = -EIO; 27993e72b3cSPhilippe Liard goto out_free_bio; 28093e72b3cSPhilippe Liard } 28193e72b3cSPhilippe Liard /* Extract the length of the metadata block */ 282fbc27241SChristoph Hellwig data = bvec_virt(bvec); 28393e72b3cSPhilippe Liard length = data[offset]; 2842910c59fSPhillip Lougher if (offset < bvec->bv_len - 1) { 28593e72b3cSPhilippe Liard length |= data[offset + 1] << 8; 28693e72b3cSPhilippe Liard } else { 28793e72b3cSPhilippe Liard if (WARN_ON_ONCE(!bio_next_segment(bio, &iter_all))) { 28893e72b3cSPhilippe Liard res = -EIO; 28993e72b3cSPhilippe Liard goto out_free_bio; 29093e72b3cSPhilippe Liard } 291fbc27241SChristoph Hellwig data = bvec_virt(bvec); 29293e72b3cSPhilippe Liard length |= data[0] << 8; 29393e72b3cSPhilippe Liard } 29493e72b3cSPhilippe Liard bio_free_pages(bio); 295066ff571SChristoph Hellwig bio_uninit(bio); 296066ff571SChristoph Hellwig kfree(bio); 29793e72b3cSPhilippe Liard 298e2780ab1SPhillip Lougher compressed = SQUASHFS_COMPRESSED(length); 299e2780ab1SPhillip Lougher length = SQUASHFS_COMPRESSED_SIZE(length); 30093e72b3cSPhilippe Liard index += 2; 301e2780ab1SPhillip Lougher 302e812cbbbSPhillip Lougher TRACE("Block @ 0x%llx, %scompressed size %d\n", index - 2, 303e2780ab1SPhillip Lougher compressed ? "" : "un", length); 304e2780ab1SPhillip Lougher } 305e812cbbbSPhillip Lougher if (length < 0 || length > output->length || 306e812cbbbSPhillip Lougher (index + length) > msblk->bytes_used) { 307e812cbbbSPhillip Lougher res = -EIO; 308e812cbbbSPhillip Lougher goto out; 309e812cbbbSPhillip Lougher } 310e812cbbbSPhillip Lougher 31193e72b3cSPhilippe Liard if (next_index) 31293e72b3cSPhilippe Liard *next_index = index + length; 313e2780ab1SPhillip Lougher 31493e72b3cSPhilippe Liard res = squashfs_bio_read(sb, index, length, &bio, &offset); 31593e72b3cSPhilippe Liard if (res) 31693e72b3cSPhilippe Liard goto out; 3179508c6b9SPhillip Lougher 318e2780ab1SPhillip Lougher if (compressed) { 31993e72b3cSPhilippe Liard if (!msblk->stream) { 32093e72b3cSPhilippe Liard res = -EIO; 32193e72b3cSPhilippe Liard goto out_free_bio; 32293e72b3cSPhilippe Liard } 32380f78409SXiaoming Ni res = msblk->thread_ops->decompress(msblk, bio, offset, length, output); 324e2780ab1SPhillip Lougher } else { 32593e72b3cSPhilippe Liard res = copy_bio_to_actor(bio, output, offset, length); 326e2780ab1SPhillip Lougher } 327e2780ab1SPhillip Lougher 32893e72b3cSPhilippe Liard out_free_bio: 32993e72b3cSPhilippe Liard bio_free_pages(bio); 330066ff571SChristoph Hellwig bio_uninit(bio); 331066ff571SChristoph Hellwig kfree(bio); 33293e72b3cSPhilippe Liard out: 33310dde05bSVincent Whitchurch if (res < 0) { 33493e72b3cSPhilippe Liard ERROR("Failed to read block 0x%llx: %d\n", index, res); 33510dde05bSVincent Whitchurch if (msblk->panic_on_errors) 33610dde05bSVincent Whitchurch panic("squashfs read failed"); 33710dde05bSVincent Whitchurch } 338e2780ab1SPhillip Lougher 33993e72b3cSPhilippe Liard return res; 340e2780ab1SPhillip Lougher } 341