147e4937aSGao Xiang // SPDX-License-Identifier: GPL-2.0-only 247e4937aSGao Xiang /* 347e4937aSGao Xiang * Copyright (C) 2018-2019 HUAWEI, Inc. 4592e7cd0SAlexander A. Klimov * https://www.huawei.com/ 547e4937aSGao Xiang */ 647e4937aSGao Xiang #include "internal.h" 747e4937aSGao Xiang #include <asm/unaligned.h> 847e4937aSGao Xiang #include <trace/events/erofs.h> 947e4937aSGao Xiang 1047e4937aSGao Xiang int z_erofs_fill_inode(struct inode *inode) 1147e4937aSGao Xiang { 12a5876e24SGao Xiang struct erofs_inode *const vi = EROFS_I(inode); 13cec6e93bSGao Xiang struct erofs_sb_info *sbi = EROFS_SB(inode->i_sb); 1447e4937aSGao Xiang 15cec6e93bSGao Xiang if (!erofs_sb_has_big_pcluster(sbi) && 16cec6e93bSGao Xiang vi->datalayout == EROFS_INODE_FLAT_COMPRESSION_LEGACY) { 1747e4937aSGao Xiang vi->z_advise = 0; 1847e4937aSGao Xiang vi->z_algorithmtype[0] = 0; 1947e4937aSGao Xiang vi->z_algorithmtype[1] = 0; 2047e4937aSGao Xiang vi->z_logical_clusterbits = LOG_BLOCK_SIZE; 21a5876e24SGao Xiang set_bit(EROFS_I_Z_INITED_BIT, &vi->flags); 2247e4937aSGao Xiang } 230c638f70SGao Xiang inode->i_mapping->a_ops = &z_erofs_aops; 2447e4937aSGao Xiang return 0; 2547e4937aSGao Xiang } 2647e4937aSGao Xiang 270c638f70SGao Xiang static int z_erofs_fill_inode_lazy(struct inode *inode) 2847e4937aSGao Xiang { 29a5876e24SGao Xiang struct erofs_inode *const vi = EROFS_I(inode); 3047e4937aSGao Xiang struct super_block *const sb = inode->i_sb; 3147e4937aSGao Xiang int err; 3247e4937aSGao Xiang erofs_off_t pos; 3347e4937aSGao Xiang struct page *page; 3447e4937aSGao Xiang void *kaddr; 3547e4937aSGao Xiang struct z_erofs_map_header *h; 3647e4937aSGao Xiang 37ce063129SGao Xiang if (test_bit(EROFS_I_Z_INITED_BIT, &vi->flags)) { 38ce063129SGao Xiang /* 39ce063129SGao Xiang * paired with smp_mb() at the end of the function to ensure 40ce063129SGao Xiang * fields will only be observed after the bit is set. 41ce063129SGao Xiang */ 42ce063129SGao Xiang smp_mb(); 4347e4937aSGao Xiang return 0; 44ce063129SGao Xiang } 4547e4937aSGao Xiang 46a5876e24SGao Xiang if (wait_on_bit_lock(&vi->flags, EROFS_I_BL_Z_BIT, TASK_KILLABLE)) 4747e4937aSGao Xiang return -ERESTARTSYS; 4847e4937aSGao Xiang 4947e4937aSGao Xiang err = 0; 50a5876e24SGao Xiang if (test_bit(EROFS_I_Z_INITED_BIT, &vi->flags)) 5147e4937aSGao Xiang goto out_unlock; 5247e4937aSGao Xiang 53cec6e93bSGao Xiang DBG_BUGON(!erofs_sb_has_big_pcluster(EROFS_SB(sb)) && 54cec6e93bSGao Xiang vi->datalayout == EROFS_INODE_FLAT_COMPRESSION_LEGACY); 5547e4937aSGao Xiang 5647e4937aSGao Xiang pos = ALIGN(iloc(EROFS_SB(sb), vi->nid) + vi->inode_isize + 5747e4937aSGao Xiang vi->xattr_isize, 8); 58e655b5b3SGao Xiang page = erofs_get_meta_page(sb, erofs_blknr(pos)); 5947e4937aSGao Xiang if (IS_ERR(page)) { 6047e4937aSGao Xiang err = PTR_ERR(page); 6147e4937aSGao Xiang goto out_unlock; 6247e4937aSGao Xiang } 6347e4937aSGao Xiang 6447e4937aSGao Xiang kaddr = kmap_atomic(page); 6547e4937aSGao Xiang 6647e4937aSGao Xiang h = kaddr + erofs_blkoff(pos); 6747e4937aSGao Xiang vi->z_advise = le16_to_cpu(h->h_advise); 6847e4937aSGao Xiang vi->z_algorithmtype[0] = h->h_algorithmtype & 15; 6947e4937aSGao Xiang vi->z_algorithmtype[1] = h->h_algorithmtype >> 4; 7047e4937aSGao Xiang 7147e4937aSGao Xiang if (vi->z_algorithmtype[0] >= Z_EROFS_COMPRESSION_MAX) { 724f761fa2SGao Xiang erofs_err(sb, "unknown compression format %u for nid %llu, please upgrade kernel", 7347e4937aSGao Xiang vi->z_algorithmtype[0], vi->nid); 7447e4937aSGao Xiang err = -EOPNOTSUPP; 7547e4937aSGao Xiang goto unmap_done; 7647e4937aSGao Xiang } 7747e4937aSGao Xiang 7847e4937aSGao Xiang vi->z_logical_clusterbits = LOG_BLOCK_SIZE + (h->h_clusterbits & 7); 79b86269f4SGao Xiang if (!erofs_sb_has_big_pcluster(EROFS_SB(sb)) && 80b86269f4SGao Xiang vi->z_advise & (Z_EROFS_ADVISE_BIG_PCLUSTER_1 | 81b86269f4SGao Xiang Z_EROFS_ADVISE_BIG_PCLUSTER_2)) { 82b86269f4SGao Xiang erofs_err(sb, "per-inode big pcluster without sb feature for nid %llu", 83b86269f4SGao Xiang vi->nid); 84b86269f4SGao Xiang err = -EFSCORRUPTED; 85b86269f4SGao Xiang goto unmap_done; 86b86269f4SGao Xiang } 87b86269f4SGao Xiang if (vi->datalayout == EROFS_INODE_FLAT_COMPRESSION && 88b86269f4SGao Xiang !(vi->z_advise & Z_EROFS_ADVISE_BIG_PCLUSTER_1) ^ 89b86269f4SGao Xiang !(vi->z_advise & Z_EROFS_ADVISE_BIG_PCLUSTER_2)) { 90b86269f4SGao Xiang erofs_err(sb, "big pcluster head1/2 of compact indexes should be consistent for nid %llu", 91b86269f4SGao Xiang vi->nid); 92b86269f4SGao Xiang err = -EFSCORRUPTED; 93b86269f4SGao Xiang goto unmap_done; 94b86269f4SGao Xiang } 95ce063129SGao Xiang /* paired with smp_mb() at the beginning of the function */ 96ce063129SGao Xiang smp_mb(); 97a5876e24SGao Xiang set_bit(EROFS_I_Z_INITED_BIT, &vi->flags); 9847e4937aSGao Xiang unmap_done: 9947e4937aSGao Xiang kunmap_atomic(kaddr); 10047e4937aSGao Xiang unlock_page(page); 10147e4937aSGao Xiang put_page(page); 10247e4937aSGao Xiang out_unlock: 103a5876e24SGao Xiang clear_and_wake_up_bit(EROFS_I_BL_Z_BIT, &vi->flags); 10447e4937aSGao Xiang return err; 10547e4937aSGao Xiang } 10647e4937aSGao Xiang 10747e4937aSGao Xiang struct z_erofs_maprecorder { 10847e4937aSGao Xiang struct inode *inode; 10947e4937aSGao Xiang struct erofs_map_blocks *map; 11047e4937aSGao Xiang void *kaddr; 11147e4937aSGao Xiang 11247e4937aSGao Xiang unsigned long lcn; 11347e4937aSGao Xiang /* compression extent information gathered */ 114*8f899262SGao Xiang u8 type, headtype; 11547e4937aSGao Xiang u16 clusterofs; 11647e4937aSGao Xiang u16 delta[2]; 117cec6e93bSGao Xiang erofs_blk_t pblk, compressedlcs; 11847e4937aSGao Xiang }; 11947e4937aSGao Xiang 12047e4937aSGao Xiang static int z_erofs_reload_indexes(struct z_erofs_maprecorder *m, 12147e4937aSGao Xiang erofs_blk_t eblk) 12247e4937aSGao Xiang { 12347e4937aSGao Xiang struct super_block *const sb = m->inode->i_sb; 12447e4937aSGao Xiang struct erofs_map_blocks *const map = m->map; 12547e4937aSGao Xiang struct page *mpage = map->mpage; 12647e4937aSGao Xiang 12747e4937aSGao Xiang if (mpage) { 12847e4937aSGao Xiang if (mpage->index == eblk) { 12947e4937aSGao Xiang if (!m->kaddr) 13047e4937aSGao Xiang m->kaddr = kmap_atomic(mpage); 13147e4937aSGao Xiang return 0; 13247e4937aSGao Xiang } 13347e4937aSGao Xiang 13447e4937aSGao Xiang if (m->kaddr) { 13547e4937aSGao Xiang kunmap_atomic(m->kaddr); 13647e4937aSGao Xiang m->kaddr = NULL; 13747e4937aSGao Xiang } 13847e4937aSGao Xiang put_page(mpage); 13947e4937aSGao Xiang } 14047e4937aSGao Xiang 141e655b5b3SGao Xiang mpage = erofs_get_meta_page(sb, eblk); 14247e4937aSGao Xiang if (IS_ERR(mpage)) { 14347e4937aSGao Xiang map->mpage = NULL; 14447e4937aSGao Xiang return PTR_ERR(mpage); 14547e4937aSGao Xiang } 14647e4937aSGao Xiang m->kaddr = kmap_atomic(mpage); 14747e4937aSGao Xiang unlock_page(mpage); 14847e4937aSGao Xiang map->mpage = mpage; 14947e4937aSGao Xiang return 0; 15047e4937aSGao Xiang } 15147e4937aSGao Xiang 1520c638f70SGao Xiang static int legacy_load_cluster_from_disk(struct z_erofs_maprecorder *m, 15347e4937aSGao Xiang unsigned long lcn) 15447e4937aSGao Xiang { 15547e4937aSGao Xiang struct inode *const inode = m->inode; 156a5876e24SGao Xiang struct erofs_inode *const vi = EROFS_I(inode); 15747e4937aSGao Xiang const erofs_off_t ibase = iloc(EROFS_I_SB(inode), vi->nid); 15847e4937aSGao Xiang const erofs_off_t pos = 15947e4937aSGao Xiang Z_EROFS_VLE_LEGACY_INDEX_ALIGN(ibase + vi->inode_isize + 16047e4937aSGao Xiang vi->xattr_isize) + 16147e4937aSGao Xiang lcn * sizeof(struct z_erofs_vle_decompressed_index); 16247e4937aSGao Xiang struct z_erofs_vle_decompressed_index *di; 16347e4937aSGao Xiang unsigned int advise, type; 16447e4937aSGao Xiang int err; 16547e4937aSGao Xiang 16647e4937aSGao Xiang err = z_erofs_reload_indexes(m, erofs_blknr(pos)); 16747e4937aSGao Xiang if (err) 16847e4937aSGao Xiang return err; 16947e4937aSGao Xiang 17047e4937aSGao Xiang m->lcn = lcn; 17147e4937aSGao Xiang di = m->kaddr + erofs_blkoff(pos); 17247e4937aSGao Xiang 17347e4937aSGao Xiang advise = le16_to_cpu(di->di_advise); 17447e4937aSGao Xiang type = (advise >> Z_EROFS_VLE_DI_CLUSTER_TYPE_BIT) & 17547e4937aSGao Xiang ((1 << Z_EROFS_VLE_DI_CLUSTER_TYPE_BITS) - 1); 17647e4937aSGao Xiang switch (type) { 17747e4937aSGao Xiang case Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD: 17847e4937aSGao Xiang m->clusterofs = 1 << vi->z_logical_clusterbits; 17947e4937aSGao Xiang m->delta[0] = le16_to_cpu(di->di_u.delta[0]); 180cec6e93bSGao Xiang if (m->delta[0] & Z_EROFS_VLE_DI_D0_CBLKCNT) { 181cec6e93bSGao Xiang if (!(vi->z_advise & Z_EROFS_ADVISE_BIG_PCLUSTER_1)) { 182cec6e93bSGao Xiang DBG_BUGON(1); 183cec6e93bSGao Xiang return -EFSCORRUPTED; 184cec6e93bSGao Xiang } 185cec6e93bSGao Xiang m->compressedlcs = m->delta[0] & 186cec6e93bSGao Xiang ~Z_EROFS_VLE_DI_D0_CBLKCNT; 187cec6e93bSGao Xiang m->delta[0] = 1; 188cec6e93bSGao Xiang } 18947e4937aSGao Xiang m->delta[1] = le16_to_cpu(di->di_u.delta[1]); 19047e4937aSGao Xiang break; 19147e4937aSGao Xiang case Z_EROFS_VLE_CLUSTER_TYPE_PLAIN: 19247e4937aSGao Xiang case Z_EROFS_VLE_CLUSTER_TYPE_HEAD: 19347e4937aSGao Xiang m->clusterofs = le16_to_cpu(di->di_clusterofs); 19447e4937aSGao Xiang m->pblk = le32_to_cpu(di->di_u.blkaddr); 19547e4937aSGao Xiang break; 19647e4937aSGao Xiang default: 19747e4937aSGao Xiang DBG_BUGON(1); 19847e4937aSGao Xiang return -EOPNOTSUPP; 19947e4937aSGao Xiang } 20047e4937aSGao Xiang m->type = type; 20147e4937aSGao Xiang return 0; 20247e4937aSGao Xiang } 20347e4937aSGao Xiang 20447e4937aSGao Xiang static unsigned int decode_compactedbits(unsigned int lobits, 20547e4937aSGao Xiang unsigned int lomask, 20647e4937aSGao Xiang u8 *in, unsigned int pos, u8 *type) 20747e4937aSGao Xiang { 20847e4937aSGao Xiang const unsigned int v = get_unaligned_le32(in + pos / 8) >> (pos & 7); 20947e4937aSGao Xiang const unsigned int lo = v & lomask; 21047e4937aSGao Xiang 21147e4937aSGao Xiang *type = (v >> lobits) & 3; 21247e4937aSGao Xiang return lo; 21347e4937aSGao Xiang } 21447e4937aSGao Xiang 215d95ae5e2SGao Xiang static int get_compacted_la_distance(unsigned int lclusterbits, 216d95ae5e2SGao Xiang unsigned int encodebits, 217d95ae5e2SGao Xiang unsigned int vcnt, u8 *in, int i) 218d95ae5e2SGao Xiang { 219d95ae5e2SGao Xiang const unsigned int lomask = (1 << lclusterbits) - 1; 220d95ae5e2SGao Xiang unsigned int lo, d1 = 0; 221d95ae5e2SGao Xiang u8 type; 222d95ae5e2SGao Xiang 223d95ae5e2SGao Xiang DBG_BUGON(i >= vcnt); 224d95ae5e2SGao Xiang 225d95ae5e2SGao Xiang do { 226d95ae5e2SGao Xiang lo = decode_compactedbits(lclusterbits, lomask, 227d95ae5e2SGao Xiang in, encodebits * i, &type); 228d95ae5e2SGao Xiang 229d95ae5e2SGao Xiang if (type != Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD) 230d95ae5e2SGao Xiang return d1; 231d95ae5e2SGao Xiang ++d1; 232d95ae5e2SGao Xiang } while (++i < vcnt); 233d95ae5e2SGao Xiang 234d95ae5e2SGao Xiang /* vcnt - 1 (Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD) item */ 235d95ae5e2SGao Xiang if (!(lo & Z_EROFS_VLE_DI_D0_CBLKCNT)) 236d95ae5e2SGao Xiang d1 += lo - 1; 237d95ae5e2SGao Xiang return d1; 238d95ae5e2SGao Xiang } 239d95ae5e2SGao Xiang 24047e4937aSGao Xiang static int unpack_compacted_index(struct z_erofs_maprecorder *m, 24147e4937aSGao Xiang unsigned int amortizedshift, 242d95ae5e2SGao Xiang unsigned int eofs, bool lookahead) 24347e4937aSGao Xiang { 244a5876e24SGao Xiang struct erofs_inode *const vi = EROFS_I(m->inode); 24547e4937aSGao Xiang const unsigned int lclusterbits = vi->z_logical_clusterbits; 24647e4937aSGao Xiang const unsigned int lomask = (1 << lclusterbits) - 1; 24747e4937aSGao Xiang unsigned int vcnt, base, lo, encodebits, nblk; 24847e4937aSGao Xiang int i; 24947e4937aSGao Xiang u8 *in, type; 250b86269f4SGao Xiang bool big_pcluster; 25147e4937aSGao Xiang 25247e4937aSGao Xiang if (1 << amortizedshift == 4) 25347e4937aSGao Xiang vcnt = 2; 25447e4937aSGao Xiang else if (1 << amortizedshift == 2 && lclusterbits == 12) 25547e4937aSGao Xiang vcnt = 16; 25647e4937aSGao Xiang else 25747e4937aSGao Xiang return -EOPNOTSUPP; 25847e4937aSGao Xiang 259b86269f4SGao Xiang big_pcluster = vi->z_advise & Z_EROFS_ADVISE_BIG_PCLUSTER_1; 26047e4937aSGao Xiang encodebits = ((vcnt << amortizedshift) - sizeof(__le32)) * 8 / vcnt; 26147e4937aSGao Xiang base = round_down(eofs, vcnt << amortizedshift); 26247e4937aSGao Xiang in = m->kaddr + base; 26347e4937aSGao Xiang 26447e4937aSGao Xiang i = (eofs - base) >> amortizedshift; 26547e4937aSGao Xiang 26647e4937aSGao Xiang lo = decode_compactedbits(lclusterbits, lomask, 26747e4937aSGao Xiang in, encodebits * i, &type); 26847e4937aSGao Xiang m->type = type; 26947e4937aSGao Xiang if (type == Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD) { 27047e4937aSGao Xiang m->clusterofs = 1 << lclusterbits; 271d95ae5e2SGao Xiang 272d95ae5e2SGao Xiang /* figure out lookahead_distance: delta[1] if needed */ 273d95ae5e2SGao Xiang if (lookahead) 274d95ae5e2SGao Xiang m->delta[1] = get_compacted_la_distance(lclusterbits, 275d95ae5e2SGao Xiang encodebits, vcnt, in, i); 276b86269f4SGao Xiang if (lo & Z_EROFS_VLE_DI_D0_CBLKCNT) { 277b86269f4SGao Xiang if (!big_pcluster) { 278b86269f4SGao Xiang DBG_BUGON(1); 279b86269f4SGao Xiang return -EFSCORRUPTED; 280b86269f4SGao Xiang } 281b86269f4SGao Xiang m->compressedlcs = lo & ~Z_EROFS_VLE_DI_D0_CBLKCNT; 282b86269f4SGao Xiang m->delta[0] = 1; 283b86269f4SGao Xiang return 0; 284b86269f4SGao Xiang } else if (i + 1 != (int)vcnt) { 28547e4937aSGao Xiang m->delta[0] = lo; 28647e4937aSGao Xiang return 0; 28747e4937aSGao Xiang } 28847e4937aSGao Xiang /* 28947e4937aSGao Xiang * since the last lcluster in the pack is special, 29047e4937aSGao Xiang * of which lo saves delta[1] rather than delta[0]. 29147e4937aSGao Xiang * Hence, get delta[0] by the previous lcluster indirectly. 29247e4937aSGao Xiang */ 29347e4937aSGao Xiang lo = decode_compactedbits(lclusterbits, lomask, 29447e4937aSGao Xiang in, encodebits * (i - 1), &type); 29547e4937aSGao Xiang if (type != Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD) 29647e4937aSGao Xiang lo = 0; 297b86269f4SGao Xiang else if (lo & Z_EROFS_VLE_DI_D0_CBLKCNT) 298b86269f4SGao Xiang lo = 1; 29947e4937aSGao Xiang m->delta[0] = lo + 1; 30047e4937aSGao Xiang return 0; 30147e4937aSGao Xiang } 30247e4937aSGao Xiang m->clusterofs = lo; 30347e4937aSGao Xiang m->delta[0] = 0; 30447e4937aSGao Xiang /* figout out blkaddr (pblk) for HEAD lclusters */ 305b86269f4SGao Xiang if (!big_pcluster) { 30647e4937aSGao Xiang nblk = 1; 30747e4937aSGao Xiang while (i > 0) { 30847e4937aSGao Xiang --i; 30947e4937aSGao Xiang lo = decode_compactedbits(lclusterbits, lomask, 31047e4937aSGao Xiang in, encodebits * i, &type); 31147e4937aSGao Xiang if (type == Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD) 31247e4937aSGao Xiang i -= lo; 31347e4937aSGao Xiang 31447e4937aSGao Xiang if (i >= 0) 31547e4937aSGao Xiang ++nblk; 31647e4937aSGao Xiang } 317b86269f4SGao Xiang } else { 318b86269f4SGao Xiang nblk = 0; 319b86269f4SGao Xiang while (i > 0) { 320b86269f4SGao Xiang --i; 321b86269f4SGao Xiang lo = decode_compactedbits(lclusterbits, lomask, 322b86269f4SGao Xiang in, encodebits * i, &type); 323b86269f4SGao Xiang if (type == Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD) { 324b86269f4SGao Xiang if (lo & Z_EROFS_VLE_DI_D0_CBLKCNT) { 325b86269f4SGao Xiang --i; 326b86269f4SGao Xiang nblk += lo & ~Z_EROFS_VLE_DI_D0_CBLKCNT; 327b86269f4SGao Xiang continue; 328b86269f4SGao Xiang } 329b86269f4SGao Xiang /* bigpcluster shouldn't have plain d0 == 1 */ 330b86269f4SGao Xiang if (lo <= 1) { 331b86269f4SGao Xiang DBG_BUGON(1); 332b86269f4SGao Xiang return -EFSCORRUPTED; 333b86269f4SGao Xiang } 334b86269f4SGao Xiang i -= lo - 2; 335b86269f4SGao Xiang continue; 336b86269f4SGao Xiang } 337b86269f4SGao Xiang ++nblk; 338b86269f4SGao Xiang } 339b86269f4SGao Xiang } 34047e4937aSGao Xiang in += (vcnt << amortizedshift) - sizeof(__le32); 34147e4937aSGao Xiang m->pblk = le32_to_cpu(*(__le32 *)in) + nblk; 34247e4937aSGao Xiang return 0; 34347e4937aSGao Xiang } 34447e4937aSGao Xiang 34547e4937aSGao Xiang static int compacted_load_cluster_from_disk(struct z_erofs_maprecorder *m, 346d95ae5e2SGao Xiang unsigned long lcn, bool lookahead) 34747e4937aSGao Xiang { 34847e4937aSGao Xiang struct inode *const inode = m->inode; 349a5876e24SGao Xiang struct erofs_inode *const vi = EROFS_I(inode); 35047e4937aSGao Xiang const unsigned int lclusterbits = vi->z_logical_clusterbits; 35147e4937aSGao Xiang const erofs_off_t ebase = ALIGN(iloc(EROFS_I_SB(inode), vi->nid) + 35247e4937aSGao Xiang vi->inode_isize + vi->xattr_isize, 8) + 35347e4937aSGao Xiang sizeof(struct z_erofs_map_header); 35447e4937aSGao Xiang const unsigned int totalidx = DIV_ROUND_UP(inode->i_size, EROFS_BLKSIZ); 35547e4937aSGao Xiang unsigned int compacted_4b_initial, compacted_2b; 35647e4937aSGao Xiang unsigned int amortizedshift; 35747e4937aSGao Xiang erofs_off_t pos; 35847e4937aSGao Xiang int err; 35947e4937aSGao Xiang 36047e4937aSGao Xiang if (lclusterbits != 12) 36147e4937aSGao Xiang return -EOPNOTSUPP; 36247e4937aSGao Xiang 36347e4937aSGao Xiang if (lcn >= totalidx) 36447e4937aSGao Xiang return -EINVAL; 36547e4937aSGao Xiang 36647e4937aSGao Xiang m->lcn = lcn; 36747e4937aSGao Xiang /* used to align to 32-byte (compacted_2b) alignment */ 36847e4937aSGao Xiang compacted_4b_initial = (32 - ebase % 32) / 4; 36947e4937aSGao Xiang if (compacted_4b_initial == 32 / 4) 37047e4937aSGao Xiang compacted_4b_initial = 0; 37147e4937aSGao Xiang 372c40dd3caSYue Hu if ((vi->z_advise & Z_EROFS_ADVISE_COMPACTED_2B) && 373c40dd3caSYue Hu compacted_4b_initial < totalidx) 37447e4937aSGao Xiang compacted_2b = rounddown(totalidx - compacted_4b_initial, 16); 37547e4937aSGao Xiang else 37647e4937aSGao Xiang compacted_2b = 0; 37747e4937aSGao Xiang 37847e4937aSGao Xiang pos = ebase; 37947e4937aSGao Xiang if (lcn < compacted_4b_initial) { 38047e4937aSGao Xiang amortizedshift = 2; 38147e4937aSGao Xiang goto out; 38247e4937aSGao Xiang } 38347e4937aSGao Xiang pos += compacted_4b_initial * 4; 38447e4937aSGao Xiang lcn -= compacted_4b_initial; 38547e4937aSGao Xiang 38647e4937aSGao Xiang if (lcn < compacted_2b) { 38747e4937aSGao Xiang amortizedshift = 1; 38847e4937aSGao Xiang goto out; 38947e4937aSGao Xiang } 39047e4937aSGao Xiang pos += compacted_2b * 2; 39147e4937aSGao Xiang lcn -= compacted_2b; 39247e4937aSGao Xiang amortizedshift = 2; 39347e4937aSGao Xiang out: 39447e4937aSGao Xiang pos += lcn * (1 << amortizedshift); 39547e4937aSGao Xiang err = z_erofs_reload_indexes(m, erofs_blknr(pos)); 39647e4937aSGao Xiang if (err) 39747e4937aSGao Xiang return err; 398d95ae5e2SGao Xiang return unpack_compacted_index(m, amortizedshift, erofs_blkoff(pos), 399d95ae5e2SGao Xiang lookahead); 40047e4937aSGao Xiang } 40147e4937aSGao Xiang 4020c638f70SGao Xiang static int z_erofs_load_cluster_from_disk(struct z_erofs_maprecorder *m, 403d95ae5e2SGao Xiang unsigned int lcn, bool lookahead) 40447e4937aSGao Xiang { 405a5876e24SGao Xiang const unsigned int datamode = EROFS_I(m->inode)->datalayout; 40647e4937aSGao Xiang 40747e4937aSGao Xiang if (datamode == EROFS_INODE_FLAT_COMPRESSION_LEGACY) 4080c638f70SGao Xiang return legacy_load_cluster_from_disk(m, lcn); 40947e4937aSGao Xiang 41047e4937aSGao Xiang if (datamode == EROFS_INODE_FLAT_COMPRESSION) 411d95ae5e2SGao Xiang return compacted_load_cluster_from_disk(m, lcn, lookahead); 41247e4937aSGao Xiang 41347e4937aSGao Xiang return -EINVAL; 41447e4937aSGao Xiang } 41547e4937aSGao Xiang 4160c638f70SGao Xiang static int z_erofs_extent_lookback(struct z_erofs_maprecorder *m, 41747e4937aSGao Xiang unsigned int lookback_distance) 41847e4937aSGao Xiang { 419a5876e24SGao Xiang struct erofs_inode *const vi = EROFS_I(m->inode); 42047e4937aSGao Xiang struct erofs_map_blocks *const map = m->map; 42147e4937aSGao Xiang const unsigned int lclusterbits = vi->z_logical_clusterbits; 42247e4937aSGao Xiang unsigned long lcn = m->lcn; 42347e4937aSGao Xiang int err; 42447e4937aSGao Xiang 42547e4937aSGao Xiang if (lcn < lookback_distance) { 4264f761fa2SGao Xiang erofs_err(m->inode->i_sb, 4274f761fa2SGao Xiang "bogus lookback distance @ nid %llu", vi->nid); 42847e4937aSGao Xiang DBG_BUGON(1); 42947e4937aSGao Xiang return -EFSCORRUPTED; 43047e4937aSGao Xiang } 43147e4937aSGao Xiang 43247e4937aSGao Xiang /* load extent head logical cluster if needed */ 43347e4937aSGao Xiang lcn -= lookback_distance; 434d95ae5e2SGao Xiang err = z_erofs_load_cluster_from_disk(m, lcn, false); 43547e4937aSGao Xiang if (err) 43647e4937aSGao Xiang return err; 43747e4937aSGao Xiang 43847e4937aSGao Xiang switch (m->type) { 43947e4937aSGao Xiang case Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD: 4408d8a09b0SGao Xiang if (!m->delta[0]) { 4414f761fa2SGao Xiang erofs_err(m->inode->i_sb, 4424f761fa2SGao Xiang "invalid lookback distance 0 @ nid %llu", 44347e4937aSGao Xiang vi->nid); 44447e4937aSGao Xiang DBG_BUGON(1); 44547e4937aSGao Xiang return -EFSCORRUPTED; 44647e4937aSGao Xiang } 4470c638f70SGao Xiang return z_erofs_extent_lookback(m, m->delta[0]); 44847e4937aSGao Xiang case Z_EROFS_VLE_CLUSTER_TYPE_PLAIN: 44947e4937aSGao Xiang case Z_EROFS_VLE_CLUSTER_TYPE_HEAD: 450*8f899262SGao Xiang m->headtype = m->type; 45147e4937aSGao Xiang map->m_la = (lcn << lclusterbits) | m->clusterofs; 45247e4937aSGao Xiang break; 45347e4937aSGao Xiang default: 4544f761fa2SGao Xiang erofs_err(m->inode->i_sb, 4554f761fa2SGao Xiang "unknown type %u @ lcn %lu of nid %llu", 45647e4937aSGao Xiang m->type, lcn, vi->nid); 45747e4937aSGao Xiang DBG_BUGON(1); 45847e4937aSGao Xiang return -EOPNOTSUPP; 45947e4937aSGao Xiang } 46047e4937aSGao Xiang return 0; 46147e4937aSGao Xiang } 46247e4937aSGao Xiang 463cec6e93bSGao Xiang static int z_erofs_get_extent_compressedlen(struct z_erofs_maprecorder *m, 464cec6e93bSGao Xiang unsigned int initial_lcn) 465cec6e93bSGao Xiang { 466cec6e93bSGao Xiang struct erofs_inode *const vi = EROFS_I(m->inode); 467cec6e93bSGao Xiang struct erofs_map_blocks *const map = m->map; 468cec6e93bSGao Xiang const unsigned int lclusterbits = vi->z_logical_clusterbits; 469cec6e93bSGao Xiang unsigned long lcn; 470cec6e93bSGao Xiang int err; 471cec6e93bSGao Xiang 472cec6e93bSGao Xiang DBG_BUGON(m->type != Z_EROFS_VLE_CLUSTER_TYPE_PLAIN && 473cec6e93bSGao Xiang m->type != Z_EROFS_VLE_CLUSTER_TYPE_HEAD); 474*8f899262SGao Xiang if (m->headtype == Z_EROFS_VLE_CLUSTER_TYPE_PLAIN || 475cec6e93bSGao Xiang !(vi->z_advise & Z_EROFS_ADVISE_BIG_PCLUSTER_1)) { 476cec6e93bSGao Xiang map->m_plen = 1 << lclusterbits; 477cec6e93bSGao Xiang return 0; 478cec6e93bSGao Xiang } 479cec6e93bSGao Xiang 480cec6e93bSGao Xiang lcn = m->lcn + 1; 481cec6e93bSGao Xiang if (m->compressedlcs) 482cec6e93bSGao Xiang goto out; 483cec6e93bSGao Xiang 484d95ae5e2SGao Xiang err = z_erofs_load_cluster_from_disk(m, lcn, false); 485cec6e93bSGao Xiang if (err) 486cec6e93bSGao Xiang return err; 487cec6e93bSGao Xiang 4880852b6caSGao Xiang /* 4890852b6caSGao Xiang * If the 1st NONHEAD lcluster has already been handled initially w/o 4900852b6caSGao Xiang * valid compressedlcs, which means at least it mustn't be CBLKCNT, or 4910852b6caSGao Xiang * an internal implemenatation error is detected. 4920852b6caSGao Xiang * 4930852b6caSGao Xiang * The following code can also handle it properly anyway, but let's 4940852b6caSGao Xiang * BUG_ON in the debugging mode only for developers to notice that. 4950852b6caSGao Xiang */ 4960852b6caSGao Xiang DBG_BUGON(lcn == initial_lcn && 4970852b6caSGao Xiang m->type == Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD); 4980852b6caSGao Xiang 499cec6e93bSGao Xiang switch (m->type) { 5000852b6caSGao Xiang case Z_EROFS_VLE_CLUSTER_TYPE_PLAIN: 5010852b6caSGao Xiang case Z_EROFS_VLE_CLUSTER_TYPE_HEAD: 5020852b6caSGao Xiang /* 5030852b6caSGao Xiang * if the 1st NONHEAD lcluster is actually PLAIN or HEAD type 5040852b6caSGao Xiang * rather than CBLKCNT, it's a 1 lcluster-sized pcluster. 5050852b6caSGao Xiang */ 5060852b6caSGao Xiang m->compressedlcs = 1; 5070852b6caSGao Xiang break; 508cec6e93bSGao Xiang case Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD: 509cec6e93bSGao Xiang if (m->delta[0] != 1) 510cec6e93bSGao Xiang goto err_bonus_cblkcnt; 511cec6e93bSGao Xiang if (m->compressedlcs) 512cec6e93bSGao Xiang break; 513cec6e93bSGao Xiang fallthrough; 514cec6e93bSGao Xiang default: 515cec6e93bSGao Xiang erofs_err(m->inode->i_sb, 516cec6e93bSGao Xiang "cannot found CBLKCNT @ lcn %lu of nid %llu", 517cec6e93bSGao Xiang lcn, vi->nid); 518cec6e93bSGao Xiang DBG_BUGON(1); 519cec6e93bSGao Xiang return -EFSCORRUPTED; 520cec6e93bSGao Xiang } 521cec6e93bSGao Xiang out: 522cec6e93bSGao Xiang map->m_plen = m->compressedlcs << lclusterbits; 523cec6e93bSGao Xiang return 0; 524cec6e93bSGao Xiang err_bonus_cblkcnt: 525cec6e93bSGao Xiang erofs_err(m->inode->i_sb, 526cec6e93bSGao Xiang "bogus CBLKCNT @ lcn %lu of nid %llu", 527cec6e93bSGao Xiang lcn, vi->nid); 528cec6e93bSGao Xiang DBG_BUGON(1); 529cec6e93bSGao Xiang return -EFSCORRUPTED; 530cec6e93bSGao Xiang } 531cec6e93bSGao Xiang 532d95ae5e2SGao Xiang static int z_erofs_get_extent_decompressedlen(struct z_erofs_maprecorder *m) 533d95ae5e2SGao Xiang { 534d95ae5e2SGao Xiang struct inode *inode = m->inode; 535d95ae5e2SGao Xiang struct erofs_inode *vi = EROFS_I(inode); 536d95ae5e2SGao Xiang struct erofs_map_blocks *map = m->map; 537d95ae5e2SGao Xiang unsigned int lclusterbits = vi->z_logical_clusterbits; 538d95ae5e2SGao Xiang u64 lcn = m->lcn, headlcn = map->m_la >> lclusterbits; 539d95ae5e2SGao Xiang int err; 540d95ae5e2SGao Xiang 541d95ae5e2SGao Xiang do { 542d95ae5e2SGao Xiang /* handle the last EOF pcluster (no next HEAD lcluster) */ 543d95ae5e2SGao Xiang if ((lcn << lclusterbits) >= inode->i_size) { 544d95ae5e2SGao Xiang map->m_llen = inode->i_size - map->m_la; 545d95ae5e2SGao Xiang return 0; 546d95ae5e2SGao Xiang } 547d95ae5e2SGao Xiang 548d95ae5e2SGao Xiang err = z_erofs_load_cluster_from_disk(m, lcn, true); 549d95ae5e2SGao Xiang if (err) 550d95ae5e2SGao Xiang return err; 551d95ae5e2SGao Xiang 552d95ae5e2SGao Xiang if (m->type == Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD) { 553d95ae5e2SGao Xiang DBG_BUGON(!m->delta[1] && 554d95ae5e2SGao Xiang m->clusterofs != 1 << lclusterbits); 555d95ae5e2SGao Xiang } else if (m->type == Z_EROFS_VLE_CLUSTER_TYPE_PLAIN || 556d95ae5e2SGao Xiang m->type == Z_EROFS_VLE_CLUSTER_TYPE_HEAD) { 557d95ae5e2SGao Xiang /* go on until the next HEAD lcluster */ 558d95ae5e2SGao Xiang if (lcn != headlcn) 559d95ae5e2SGao Xiang break; 560d95ae5e2SGao Xiang m->delta[1] = 1; 561d95ae5e2SGao Xiang } else { 562d95ae5e2SGao Xiang erofs_err(inode->i_sb, "unknown type %u @ lcn %llu of nid %llu", 563d95ae5e2SGao Xiang m->type, lcn, vi->nid); 564d95ae5e2SGao Xiang DBG_BUGON(1); 565d95ae5e2SGao Xiang return -EOPNOTSUPP; 566d95ae5e2SGao Xiang } 567d95ae5e2SGao Xiang lcn += m->delta[1]; 568d95ae5e2SGao Xiang } while (m->delta[1]); 569d95ae5e2SGao Xiang 570d95ae5e2SGao Xiang map->m_llen = (lcn << lclusterbits) + m->clusterofs - map->m_la; 571d95ae5e2SGao Xiang return 0; 572d95ae5e2SGao Xiang } 573d95ae5e2SGao Xiang 57447e4937aSGao Xiang int z_erofs_map_blocks_iter(struct inode *inode, 57547e4937aSGao Xiang struct erofs_map_blocks *map, 57647e4937aSGao Xiang int flags) 57747e4937aSGao Xiang { 578a5876e24SGao Xiang struct erofs_inode *const vi = EROFS_I(inode); 57947e4937aSGao Xiang struct z_erofs_maprecorder m = { 58047e4937aSGao Xiang .inode = inode, 58147e4937aSGao Xiang .map = map, 58247e4937aSGao Xiang }; 58347e4937aSGao Xiang int err = 0; 58447e4937aSGao Xiang unsigned int lclusterbits, endoff; 585cec6e93bSGao Xiang unsigned long initial_lcn; 58647e4937aSGao Xiang unsigned long long ofs, end; 58747e4937aSGao Xiang 58847e4937aSGao Xiang trace_z_erofs_map_blocks_iter_enter(inode, map, flags); 58947e4937aSGao Xiang 59047e4937aSGao Xiang /* when trying to read beyond EOF, leave it unmapped */ 5918d8a09b0SGao Xiang if (map->m_la >= inode->i_size) { 59247e4937aSGao Xiang map->m_llen = map->m_la + 1 - inode->i_size; 59347e4937aSGao Xiang map->m_la = inode->i_size; 59447e4937aSGao Xiang map->m_flags = 0; 59547e4937aSGao Xiang goto out; 59647e4937aSGao Xiang } 59747e4937aSGao Xiang 5980c638f70SGao Xiang err = z_erofs_fill_inode_lazy(inode); 59947e4937aSGao Xiang if (err) 60047e4937aSGao Xiang goto out; 60147e4937aSGao Xiang 60247e4937aSGao Xiang lclusterbits = vi->z_logical_clusterbits; 60347e4937aSGao Xiang ofs = map->m_la; 604cec6e93bSGao Xiang initial_lcn = ofs >> lclusterbits; 60547e4937aSGao Xiang endoff = ofs & ((1 << lclusterbits) - 1); 60647e4937aSGao Xiang 607d95ae5e2SGao Xiang err = z_erofs_load_cluster_from_disk(&m, initial_lcn, false); 60847e4937aSGao Xiang if (err) 60947e4937aSGao Xiang goto unmap_out; 61047e4937aSGao Xiang 611*8f899262SGao Xiang map->m_flags = EROFS_MAP_MAPPED | EROFS_MAP_ENCODED; 61247e4937aSGao Xiang end = (m.lcn + 1ULL) << lclusterbits; 61347e4937aSGao Xiang 61447e4937aSGao Xiang switch (m.type) { 61547e4937aSGao Xiang case Z_EROFS_VLE_CLUSTER_TYPE_PLAIN: 61647e4937aSGao Xiang case Z_EROFS_VLE_CLUSTER_TYPE_HEAD: 61747e4937aSGao Xiang if (endoff >= m.clusterofs) { 618*8f899262SGao Xiang m.headtype = m.type; 61947e4937aSGao Xiang map->m_la = (m.lcn << lclusterbits) | m.clusterofs; 62047e4937aSGao Xiang break; 62147e4937aSGao Xiang } 62247e4937aSGao Xiang /* m.lcn should be >= 1 if endoff < m.clusterofs */ 6238d8a09b0SGao Xiang if (!m.lcn) { 6244f761fa2SGao Xiang erofs_err(inode->i_sb, 6254f761fa2SGao Xiang "invalid logical cluster 0 at nid %llu", 62647e4937aSGao Xiang vi->nid); 62747e4937aSGao Xiang err = -EFSCORRUPTED; 62847e4937aSGao Xiang goto unmap_out; 62947e4937aSGao Xiang } 63047e4937aSGao Xiang end = (m.lcn << lclusterbits) | m.clusterofs; 63147e4937aSGao Xiang map->m_flags |= EROFS_MAP_FULL_MAPPED; 63247e4937aSGao Xiang m.delta[0] = 1; 633df561f66SGustavo A. R. Silva fallthrough; 63447e4937aSGao Xiang case Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD: 635fe6adcceSRuiqi Gong /* get the corresponding first chunk */ 6360c638f70SGao Xiang err = z_erofs_extent_lookback(&m, m.delta[0]); 6378d8a09b0SGao Xiang if (err) 63847e4937aSGao Xiang goto unmap_out; 63947e4937aSGao Xiang break; 64047e4937aSGao Xiang default: 6414f761fa2SGao Xiang erofs_err(inode->i_sb, 6424f761fa2SGao Xiang "unknown type %u @ offset %llu of nid %llu", 64347e4937aSGao Xiang m.type, ofs, vi->nid); 64447e4937aSGao Xiang err = -EOPNOTSUPP; 64547e4937aSGao Xiang goto unmap_out; 64647e4937aSGao Xiang } 64747e4937aSGao Xiang 64847e4937aSGao Xiang map->m_llen = end - map->m_la; 64947e4937aSGao Xiang map->m_pa = blknr_to_addr(m.pblk); 65047e4937aSGao Xiang 651cec6e93bSGao Xiang err = z_erofs_get_extent_compressedlen(&m, initial_lcn); 652cec6e93bSGao Xiang if (err) 653cec6e93bSGao Xiang goto out; 654d95ae5e2SGao Xiang 655*8f899262SGao Xiang if (m.headtype == Z_EROFS_VLE_CLUSTER_TYPE_PLAIN) 656*8f899262SGao Xiang map->m_algorithmformat = Z_EROFS_COMPRESSION_SHIFTED; 657*8f899262SGao Xiang else 658*8f899262SGao Xiang map->m_algorithmformat = vi->z_algorithmtype[0]; 659*8f899262SGao Xiang 660d95ae5e2SGao Xiang if (flags & EROFS_GET_BLOCKS_FIEMAP) { 661d95ae5e2SGao Xiang err = z_erofs_get_extent_decompressedlen(&m); 662d95ae5e2SGao Xiang if (!err) 663d95ae5e2SGao Xiang map->m_flags |= EROFS_MAP_FULL_MAPPED; 664d95ae5e2SGao Xiang } 66547e4937aSGao Xiang unmap_out: 66647e4937aSGao Xiang if (m.kaddr) 66747e4937aSGao Xiang kunmap_atomic(m.kaddr); 66847e4937aSGao Xiang 66947e4937aSGao Xiang out: 6704f761fa2SGao Xiang erofs_dbg("%s, m_la %llu m_pa %llu m_llen %llu m_plen %llu m_flags 0%o", 67147e4937aSGao Xiang __func__, map->m_la, map->m_pa, 67247e4937aSGao Xiang map->m_llen, map->m_plen, map->m_flags); 67347e4937aSGao Xiang 67447e4937aSGao Xiang trace_z_erofs_map_blocks_iter_exit(inode, map, flags, err); 67547e4937aSGao Xiang 67647e4937aSGao Xiang /* aggressively BUG_ON iff CONFIG_EROFS_FS_DEBUG is on */ 67747e4937aSGao Xiang DBG_BUGON(err < 0 && err != -ENOMEM); 67847e4937aSGao Xiang return err; 67947e4937aSGao Xiang } 680eadcd6b5SGao Xiang 681eadcd6b5SGao Xiang static int z_erofs_iomap_begin_report(struct inode *inode, loff_t offset, 682eadcd6b5SGao Xiang loff_t length, unsigned int flags, 683eadcd6b5SGao Xiang struct iomap *iomap, struct iomap *srcmap) 684eadcd6b5SGao Xiang { 685eadcd6b5SGao Xiang int ret; 686eadcd6b5SGao Xiang struct erofs_map_blocks map = { .m_la = offset }; 687eadcd6b5SGao Xiang 688eadcd6b5SGao Xiang ret = z_erofs_map_blocks_iter(inode, &map, EROFS_GET_BLOCKS_FIEMAP); 689eadcd6b5SGao Xiang if (map.mpage) 690eadcd6b5SGao Xiang put_page(map.mpage); 691eadcd6b5SGao Xiang if (ret < 0) 692eadcd6b5SGao Xiang return ret; 693eadcd6b5SGao Xiang 694eadcd6b5SGao Xiang iomap->bdev = inode->i_sb->s_bdev; 695eadcd6b5SGao Xiang iomap->offset = map.m_la; 696eadcd6b5SGao Xiang iomap->length = map.m_llen; 697eadcd6b5SGao Xiang if (map.m_flags & EROFS_MAP_MAPPED) { 698eadcd6b5SGao Xiang iomap->type = IOMAP_MAPPED; 699eadcd6b5SGao Xiang iomap->addr = map.m_pa; 700eadcd6b5SGao Xiang } else { 701eadcd6b5SGao Xiang iomap->type = IOMAP_HOLE; 702eadcd6b5SGao Xiang iomap->addr = IOMAP_NULL_ADDR; 703eadcd6b5SGao Xiang /* 704eadcd6b5SGao Xiang * No strict rule how to describe extents for post EOF, yet 705eadcd6b5SGao Xiang * we need do like below. Otherwise, iomap itself will get 706eadcd6b5SGao Xiang * into an endless loop on post EOF. 707eadcd6b5SGao Xiang */ 708eadcd6b5SGao Xiang if (iomap->offset >= inode->i_size) 709eadcd6b5SGao Xiang iomap->length = length + map.m_la - offset; 710eadcd6b5SGao Xiang } 711eadcd6b5SGao Xiang iomap->flags = 0; 712eadcd6b5SGao Xiang return 0; 713eadcd6b5SGao Xiang } 714eadcd6b5SGao Xiang 715eadcd6b5SGao Xiang const struct iomap_ops z_erofs_iomap_report_ops = { 716eadcd6b5SGao Xiang .iomap_begin = z_erofs_iomap_begin_report, 717eadcd6b5SGao Xiang }; 718