1 // SPDX-License-Identifier: GPL-2.0+
4 static int z_erofs_do_map_blocks(struct erofs_inode
*vi
,
5 struct erofs_map_blocks
*map
,
8 int z_erofs_fill_inode(struct erofs_inode
*vi
)
10 if (!erofs_sb_has_big_pcluster() &&
11 !erofs_sb_has_ztailpacking() && !erofs_sb_has_fragments() &&
12 vi
->datalayout
== EROFS_INODE_COMPRESSED_FULL
) {
14 vi
->z_algorithmtype
[0] = 0;
15 vi
->z_algorithmtype
[1] = 0;
16 vi
->z_logical_clusterbits
= sbi
.blkszbits
;
18 vi
->flags
|= EROFS_I_Z_INITED
;
23 static int z_erofs_fill_inode_lazy(struct erofs_inode
*vi
)
27 struct z_erofs_map_header
*h
;
28 char buf
[sizeof(struct z_erofs_map_header
)];
30 if (vi
->flags
& EROFS_I_Z_INITED
)
33 pos
= round_up(iloc(vi
->nid
) + vi
->inode_isize
+ vi
->xattr_isize
, 8);
34 ret
= erofs_dev_read(0, buf
, pos
, sizeof(buf
));
38 h
= (struct z_erofs_map_header
*)buf
;
40 * if the highest bit of the 8-byte map header is set, the whole file
41 * is stored in the packed inode. The rest bits keeps z_fragmentoff.
43 if (h
->h_clusterbits
>> Z_EROFS_FRAGMENT_INODE_BIT
) {
44 vi
->z_advise
= Z_EROFS_ADVISE_FRAGMENT_PCLUSTER
;
45 vi
->fragmentoff
= le64_to_cpu(*(__le64
*)h
) ^ (1ULL << 63);
46 vi
->z_tailextent_headlcn
= 0;
50 vi
->z_advise
= le16_to_cpu(h
->h_advise
);
51 vi
->z_algorithmtype
[0] = h
->h_algorithmtype
& 15;
52 vi
->z_algorithmtype
[1] = h
->h_algorithmtype
>> 4;
54 if (vi
->z_algorithmtype
[0] >= Z_EROFS_COMPRESSION_MAX
) {
55 erofs_err("unknown compression format %u for nid %llu",
56 vi
->z_algorithmtype
[0], (unsigned long long)vi
->nid
);
60 vi
->z_logical_clusterbits
= sbi
.blkszbits
+ (h
->h_clusterbits
& 7);
61 if (vi
->datalayout
== EROFS_INODE_COMPRESSED_COMPACT
&&
62 !(vi
->z_advise
& Z_EROFS_ADVISE_BIG_PCLUSTER_1
) ^
63 !(vi
->z_advise
& Z_EROFS_ADVISE_BIG_PCLUSTER_2
)) {
64 erofs_err("big pcluster head1/2 of compact indexes should be consistent for nid %llu",
69 if (vi
->z_advise
& Z_EROFS_ADVISE_INLINE_PCLUSTER
) {
70 struct erofs_map_blocks map
= { .index
= UINT_MAX
};
72 vi
->idata_size
= le16_to_cpu(h
->h_idata_size
);
73 ret
= z_erofs_do_map_blocks(vi
, &map
,
74 EROFS_GET_BLOCKS_FINDTAIL
);
76 erofs_blkoff(map
.m_pa
) + map
.m_plen
> erofs_blksiz()) {
77 erofs_err("invalid tail-packing pclustersize %llu",
84 if (vi
->z_advise
& Z_EROFS_ADVISE_FRAGMENT_PCLUSTER
&&
85 !(h
->h_clusterbits
>> Z_EROFS_FRAGMENT_INODE_BIT
)) {
86 struct erofs_map_blocks map
= { .index
= UINT_MAX
};
88 vi
->fragmentoff
= le32_to_cpu(h
->h_fragmentoff
);
89 ret
= z_erofs_do_map_blocks(vi
, &map
,
90 EROFS_GET_BLOCKS_FINDTAIL
);
95 vi
->flags
|= EROFS_I_Z_INITED
;
99 struct z_erofs_maprecorder
{
100 struct erofs_inode
*inode
;
101 struct erofs_map_blocks
*map
;
105 /* compression extent information gathered */
109 erofs_blk_t pblk
, compressedblks
;
110 erofs_off_t nextpackoff
;
114 static int z_erofs_reload_indexes(struct z_erofs_maprecorder
*m
,
118 struct erofs_map_blocks
*const map
= m
->map
;
119 char *mpage
= map
->mpage
;
121 if (map
->index
== eblk
)
124 ret
= erofs_blk_read(mpage
, eblk
, 1);
133 static int legacy_load_cluster_from_disk(struct z_erofs_maprecorder
*m
,
136 struct erofs_inode
*const vi
= m
->inode
;
137 const erofs_off_t ibase
= iloc(vi
->nid
);
138 const erofs_off_t pos
= Z_EROFS_FULL_INDEX_ALIGN(ibase
+
139 vi
->inode_isize
+ vi
->xattr_isize
) +
140 lcn
* sizeof(struct z_erofs_lcluster_index
);
141 struct z_erofs_lcluster_index
*di
;
142 unsigned int advise
, type
;
145 err
= z_erofs_reload_indexes(m
, erofs_blknr(pos
));
149 m
->nextpackoff
= pos
+ sizeof(struct z_erofs_lcluster_index
);
151 di
= m
->kaddr
+ erofs_blkoff(pos
);
153 advise
= le16_to_cpu(di
->di_advise
);
154 type
= (advise
>> Z_EROFS_LI_LCLUSTER_TYPE_BIT
) &
155 ((1 << Z_EROFS_LI_LCLUSTER_TYPE_BITS
) - 1);
157 case Z_EROFS_LCLUSTER_TYPE_NONHEAD
:
158 m
->clusterofs
= 1 << vi
->z_logical_clusterbits
;
159 m
->delta
[0] = le16_to_cpu(di
->di_u
.delta
[0]);
160 if (m
->delta
[0] & Z_EROFS_LI_D0_CBLKCNT
) {
161 if (!(vi
->z_advise
& Z_EROFS_ADVISE_BIG_PCLUSTER_1
)) {
163 return -EFSCORRUPTED
;
165 m
->compressedblks
= m
->delta
[0] &
166 ~Z_EROFS_LI_D0_CBLKCNT
;
169 m
->delta
[1] = le16_to_cpu(di
->di_u
.delta
[1]);
171 case Z_EROFS_LCLUSTER_TYPE_PLAIN
:
172 case Z_EROFS_LCLUSTER_TYPE_HEAD1
:
173 if (advise
& Z_EROFS_LI_PARTIAL_REF
)
174 m
->partialref
= true;
175 m
->clusterofs
= le16_to_cpu(di
->di_clusterofs
);
176 m
->pblk
= le32_to_cpu(di
->di_u
.blkaddr
);
186 static unsigned int decode_compactedbits(unsigned int lobits
,
188 u8
*in
, unsigned int pos
, u8
*type
)
190 const unsigned int v
= get_unaligned_le32(in
+ pos
/ 8) >> (pos
& 7);
191 const unsigned int lo
= v
& lomask
;
193 *type
= (v
>> lobits
) & 3;
197 static int get_compacted_la_distance(unsigned int lclusterbits
,
198 unsigned int encodebits
,
199 unsigned int vcnt
, u8
*in
, int i
)
201 const unsigned int lomask
= (1 << lclusterbits
) - 1;
202 unsigned int lo
, d1
= 0;
205 DBG_BUGON(i
>= vcnt
);
208 lo
= decode_compactedbits(lclusterbits
, lomask
,
209 in
, encodebits
* i
, &type
);
211 if (type
!= Z_EROFS_LCLUSTER_TYPE_NONHEAD
)
214 } while (++i
< vcnt
);
216 /* vcnt - 1 (Z_EROFS_LCLUSTER_TYPE_NONHEAD) item */
217 if (!(lo
& Z_EROFS_LI_D0_CBLKCNT
))
222 static int unpack_compacted_index(struct z_erofs_maprecorder
*m
,
223 unsigned int amortizedshift
,
224 erofs_off_t pos
, bool lookahead
)
226 struct erofs_inode
*const vi
= m
->inode
;
227 const unsigned int lclusterbits
= vi
->z_logical_clusterbits
;
228 const unsigned int lomask
= (1 << lclusterbits
) - 1;
229 unsigned int vcnt
, base
, lo
, encodebits
, nblk
, eofs
;
234 if (1 << amortizedshift
== 4)
236 else if (1 << amortizedshift
== 2 && lclusterbits
== 12)
241 /* it doesn't equal to round_up(..) */
242 m
->nextpackoff
= round_down(pos
, vcnt
<< amortizedshift
) +
243 (vcnt
<< amortizedshift
);
244 big_pcluster
= vi
->z_advise
& Z_EROFS_ADVISE_BIG_PCLUSTER_1
;
245 encodebits
= ((vcnt
<< amortizedshift
) - sizeof(__le32
)) * 8 / vcnt
;
246 eofs
= erofs_blkoff(pos
);
247 base
= round_down(eofs
, vcnt
<< amortizedshift
);
248 in
= m
->kaddr
+ base
;
250 i
= (eofs
- base
) >> amortizedshift
;
252 lo
= decode_compactedbits(lclusterbits
, lomask
,
253 in
, encodebits
* i
, &type
);
255 if (type
== Z_EROFS_LCLUSTER_TYPE_NONHEAD
) {
256 m
->clusterofs
= 1 << lclusterbits
;
258 /* figure out lookahead_distance: delta[1] if needed */
260 m
->delta
[1] = get_compacted_la_distance(lclusterbits
,
261 encodebits
, vcnt
, in
, i
);
262 if (lo
& Z_EROFS_LI_D0_CBLKCNT
) {
265 return -EFSCORRUPTED
;
267 m
->compressedblks
= lo
& ~Z_EROFS_LI_D0_CBLKCNT
;
270 } else if (i
+ 1 != (int)vcnt
) {
275 * since the last lcluster in the pack is special,
276 * of which lo saves delta[1] rather than delta[0].
277 * Hence, get delta[0] by the previous lcluster indirectly.
279 lo
= decode_compactedbits(lclusterbits
, lomask
,
280 in
, encodebits
* (i
- 1), &type
);
281 if (type
!= Z_EROFS_LCLUSTER_TYPE_NONHEAD
)
283 else if (lo
& Z_EROFS_LI_D0_CBLKCNT
)
285 m
->delta
[0] = lo
+ 1;
290 /* figout out blkaddr (pblk) for HEAD lclusters */
295 lo
= decode_compactedbits(lclusterbits
, lomask
,
296 in
, encodebits
* i
, &type
);
297 if (type
== Z_EROFS_LCLUSTER_TYPE_NONHEAD
)
307 lo
= decode_compactedbits(lclusterbits
, lomask
,
308 in
, encodebits
* i
, &type
);
309 if (type
== Z_EROFS_LCLUSTER_TYPE_NONHEAD
) {
310 if (lo
& Z_EROFS_LI_D0_CBLKCNT
) {
312 nblk
+= lo
& ~Z_EROFS_LI_D0_CBLKCNT
;
317 /* --i; ++nblk; continue; */
318 return -EFSCORRUPTED
;
326 in
+= (vcnt
<< amortizedshift
) - sizeof(__le32
);
327 m
->pblk
= le32_to_cpu(*(__le32
*)in
) + nblk
;
331 static int compacted_load_cluster_from_disk(struct z_erofs_maprecorder
*m
,
332 unsigned long lcn
, bool lookahead
)
334 struct erofs_inode
*const vi
= m
->inode
;
335 const unsigned int lclusterbits
= vi
->z_logical_clusterbits
;
336 const erofs_off_t ebase
= round_up(iloc(vi
->nid
) + vi
->inode_isize
+
337 vi
->xattr_isize
, 8) +
338 sizeof(struct z_erofs_map_header
);
339 const unsigned int totalidx
= BLK_ROUND_UP(vi
->i_size
);
340 unsigned int compacted_4b_initial
, compacted_2b
;
341 unsigned int amortizedshift
;
345 if (lclusterbits
!= 12)
352 /* used to align to 32-byte (compacted_2b) alignment */
353 compacted_4b_initial
= (32 - ebase
% 32) / 4;
354 if (compacted_4b_initial
== 32 / 4)
355 compacted_4b_initial
= 0;
357 if ((vi
->z_advise
& Z_EROFS_ADVISE_COMPACTED_2B
) &&
358 compacted_4b_initial
< totalidx
)
359 compacted_2b
= rounddown(totalidx
- compacted_4b_initial
, 16);
364 if (lcn
< compacted_4b_initial
) {
368 pos
+= compacted_4b_initial
* 4;
369 lcn
-= compacted_4b_initial
;
371 if (lcn
< compacted_2b
) {
375 pos
+= compacted_2b
* 2;
379 pos
+= lcn
* (1 << amortizedshift
);
380 err
= z_erofs_reload_indexes(m
, erofs_blknr(pos
));
383 return unpack_compacted_index(m
, amortizedshift
, pos
, lookahead
);
386 static int z_erofs_load_cluster_from_disk(struct z_erofs_maprecorder
*m
,
387 unsigned int lcn
, bool lookahead
)
389 const unsigned int datamode
= m
->inode
->datalayout
;
391 if (datamode
== EROFS_INODE_COMPRESSED_FULL
)
392 return legacy_load_cluster_from_disk(m
, lcn
);
394 if (datamode
== EROFS_INODE_COMPRESSED_COMPACT
)
395 return compacted_load_cluster_from_disk(m
, lcn
, lookahead
);
400 static int z_erofs_extent_lookback(struct z_erofs_maprecorder
*m
,
401 unsigned int lookback_distance
)
403 struct erofs_inode
*const vi
= m
->inode
;
404 struct erofs_map_blocks
*const map
= m
->map
;
405 const unsigned int lclusterbits
= vi
->z_logical_clusterbits
;
406 unsigned long lcn
= m
->lcn
;
409 if (lcn
< lookback_distance
) {
410 erofs_err("bogus lookback distance @ nid %llu",
411 (unsigned long long)vi
->nid
);
413 return -EFSCORRUPTED
;
416 /* load extent head logical cluster if needed */
417 lcn
-= lookback_distance
;
418 err
= z_erofs_load_cluster_from_disk(m
, lcn
, false);
423 case Z_EROFS_LCLUSTER_TYPE_NONHEAD
:
425 erofs_err("invalid lookback distance 0 @ nid %llu",
426 (unsigned long long)vi
->nid
);
428 return -EFSCORRUPTED
;
430 return z_erofs_extent_lookback(m
, m
->delta
[0]);
431 case Z_EROFS_LCLUSTER_TYPE_PLAIN
:
432 case Z_EROFS_LCLUSTER_TYPE_HEAD1
:
433 m
->headtype
= m
->type
;
434 map
->m_la
= (lcn
<< lclusterbits
) | m
->clusterofs
;
437 erofs_err("unknown type %u @ lcn %lu of nid %llu",
438 m
->type
, lcn
, (unsigned long long)vi
->nid
);
445 static int z_erofs_get_extent_compressedlen(struct z_erofs_maprecorder
*m
,
446 unsigned int initial_lcn
)
448 struct erofs_inode
*const vi
= m
->inode
;
449 struct erofs_map_blocks
*const map
= m
->map
;
450 const unsigned int lclusterbits
= vi
->z_logical_clusterbits
;
454 DBG_BUGON(m
->type
!= Z_EROFS_LCLUSTER_TYPE_PLAIN
&&
455 m
->type
!= Z_EROFS_LCLUSTER_TYPE_HEAD1
);
457 if (m
->headtype
== Z_EROFS_LCLUSTER_TYPE_PLAIN
||
458 !(vi
->z_advise
& Z_EROFS_ADVISE_BIG_PCLUSTER_1
)) {
459 map
->m_plen
= 1 << lclusterbits
;
464 if (m
->compressedblks
)
467 err
= z_erofs_load_cluster_from_disk(m
, lcn
, false);
472 * If the 1st NONHEAD lcluster has already been handled initially w/o
473 * valid compressedblks, which means at least it mustn't be CBLKCNT, or
474 * an internal implemenatation error is detected.
476 * The following code can also handle it properly anyway, but let's
477 * BUG_ON in the debugging mode only for developers to notice that.
479 DBG_BUGON(lcn
== initial_lcn
&&
480 m
->type
== Z_EROFS_LCLUSTER_TYPE_NONHEAD
);
483 case Z_EROFS_LCLUSTER_TYPE_PLAIN
:
484 case Z_EROFS_LCLUSTER_TYPE_HEAD1
:
486 * if the 1st NONHEAD lcluster is actually PLAIN or HEAD type
487 * rather than CBLKCNT, it's a 1 lcluster-sized pcluster.
489 m
->compressedblks
= 1 << (lclusterbits
- sbi
.blkszbits
);
491 case Z_EROFS_LCLUSTER_TYPE_NONHEAD
:
492 if (m
->delta
[0] != 1)
493 goto err_bonus_cblkcnt
;
494 if (m
->compressedblks
)
498 erofs_err("cannot found CBLKCNT @ lcn %lu of nid %llu",
499 lcn
, vi
->nid
| 0ULL);
501 return -EFSCORRUPTED
;
504 map
->m_plen
= m
->compressedblks
<< sbi
.blkszbits
;
507 erofs_err("bogus CBLKCNT @ lcn %lu of nid %llu",
508 lcn
, vi
->nid
| 0ULL);
510 return -EFSCORRUPTED
;
513 static int z_erofs_get_extent_decompressedlen(struct z_erofs_maprecorder
*m
)
515 struct erofs_inode
*const vi
= m
->inode
;
516 struct erofs_map_blocks
*map
= m
->map
;
517 unsigned int lclusterbits
= vi
->z_logical_clusterbits
;
518 u64 lcn
= m
->lcn
, headlcn
= map
->m_la
>> lclusterbits
;
522 /* handle the last EOF pcluster (no next HEAD lcluster) */
523 if ((lcn
<< lclusterbits
) >= vi
->i_size
) {
524 map
->m_llen
= vi
->i_size
- map
->m_la
;
528 err
= z_erofs_load_cluster_from_disk(m
, lcn
, true);
532 if (m
->type
== Z_EROFS_LCLUSTER_TYPE_NONHEAD
) {
533 DBG_BUGON(!m
->delta
[1] &&
534 m
->clusterofs
!= 1 << lclusterbits
);
535 } else if (m
->type
== Z_EROFS_LCLUSTER_TYPE_PLAIN
||
536 m
->type
== Z_EROFS_LCLUSTER_TYPE_HEAD1
) {
537 /* go on until the next HEAD lcluster */
542 erofs_err("unknown type %u @ lcn %llu of nid %llu",
544 (unsigned long long)vi
->nid
);
549 } while (m
->delta
[1]);
551 map
->m_llen
= (lcn
<< lclusterbits
) + m
->clusterofs
- map
->m_la
;
555 static int z_erofs_do_map_blocks(struct erofs_inode
*vi
,
556 struct erofs_map_blocks
*map
,
559 bool ztailpacking
= vi
->z_advise
& Z_EROFS_ADVISE_INLINE_PCLUSTER
;
560 bool fragment
= vi
->z_advise
& Z_EROFS_ADVISE_FRAGMENT_PCLUSTER
;
561 struct z_erofs_maprecorder m
= {
567 unsigned int lclusterbits
, endoff
;
568 unsigned long initial_lcn
;
569 unsigned long long ofs
, end
;
571 lclusterbits
= vi
->z_logical_clusterbits
;
572 ofs
= flags
& EROFS_GET_BLOCKS_FINDTAIL
? vi
->i_size
- 1 : map
->m_la
;
573 initial_lcn
= ofs
>> lclusterbits
;
574 endoff
= ofs
& ((1 << lclusterbits
) - 1);
576 err
= z_erofs_load_cluster_from_disk(&m
, initial_lcn
, false);
580 if (ztailpacking
&& (flags
& EROFS_GET_BLOCKS_FINDTAIL
))
581 vi
->z_idataoff
= m
.nextpackoff
;
583 map
->m_flags
= EROFS_MAP_MAPPED
| EROFS_MAP_ENCODED
;
584 end
= (m
.lcn
+ 1ULL) << lclusterbits
;
586 case Z_EROFS_LCLUSTER_TYPE_PLAIN
:
587 case Z_EROFS_LCLUSTER_TYPE_HEAD1
:
588 if (endoff
>= m
.clusterofs
) {
590 map
->m_la
= (m
.lcn
<< lclusterbits
) | m
.clusterofs
;
593 /* m.lcn should be >= 1 if endoff < m.clusterofs */
595 erofs_err("invalid logical cluster 0 at nid %llu",
596 (unsigned long long)vi
->nid
);
600 end
= (m
.lcn
<< lclusterbits
) | m
.clusterofs
;
601 map
->m_flags
|= EROFS_MAP_FULL_MAPPED
;
604 case Z_EROFS_LCLUSTER_TYPE_NONHEAD
:
605 /* get the correspoinding first chunk */
606 err
= z_erofs_extent_lookback(&m
, m
.delta
[0]);
611 erofs_err("unknown type %u @ offset %llu of nid %llu",
612 m
.type
, ofs
, (unsigned long long)vi
->nid
);
617 map
->m_flags
|= EROFS_MAP_PARTIAL_REF
;
618 map
->m_llen
= end
- map
->m_la
;
619 if (flags
& EROFS_GET_BLOCKS_FINDTAIL
) {
620 vi
->z_tailextent_headlcn
= m
.lcn
;
621 /* for non-compact indexes, fragmentoff is 64 bits */
622 if (fragment
&& vi
->datalayout
== EROFS_INODE_COMPRESSED_FULL
)
623 vi
->fragmentoff
|= (u64
)m
.pblk
<< 32;
625 if (ztailpacking
&& m
.lcn
== vi
->z_tailextent_headlcn
) {
626 map
->m_flags
|= EROFS_MAP_META
;
627 map
->m_pa
= vi
->z_idataoff
;
628 map
->m_plen
= vi
->z_idata_size
;
629 } else if (fragment
&& m
.lcn
== vi
->z_tailextent_headlcn
) {
630 map
->m_flags
|= EROFS_MAP_FRAGMENT
;
632 map
->m_pa
= erofs_pos(m
.pblk
);
633 err
= z_erofs_get_extent_compressedlen(&m
, initial_lcn
);
638 if (m
.headtype
== Z_EROFS_LCLUSTER_TYPE_PLAIN
) {
639 if (map
->m_llen
> map
->m_plen
) {
644 if (vi
->z_advise
& Z_EROFS_ADVISE_INTERLACED_PCLUSTER
)
645 map
->m_algorithmformat
=
646 Z_EROFS_COMPRESSION_INTERLACED
;
648 map
->m_algorithmformat
=
649 Z_EROFS_COMPRESSION_SHIFTED
;
651 map
->m_algorithmformat
= vi
->z_algorithmtype
[0];
654 if (flags
& EROFS_GET_BLOCKS_FIEMAP
) {
655 err
= z_erofs_get_extent_decompressedlen(&m
);
657 map
->m_flags
|= EROFS_MAP_FULL_MAPPED
;
661 erofs_dbg("m_la %" PRIu64
" m_pa %" PRIu64
" m_llen %" PRIu64
" m_plen %" PRIu64
" m_flags 0%o",
662 map
->m_la
, map
->m_pa
,
663 map
->m_llen
, map
->m_plen
, map
->m_flags
);
667 int z_erofs_map_blocks_iter(struct erofs_inode
*vi
,
668 struct erofs_map_blocks
*map
,
673 /* when trying to read beyond EOF, leave it unmapped */
674 if (map
->m_la
>= vi
->i_size
) {
675 map
->m_llen
= map
->m_la
+ 1 - vi
->i_size
;
676 map
->m_la
= vi
->i_size
;
681 err
= z_erofs_fill_inode_lazy(vi
);
685 if ((vi
->z_advise
& Z_EROFS_ADVISE_FRAGMENT_PCLUSTER
) &&
686 !vi
->z_tailextent_headlcn
) {
688 map
->m_llen
= vi
->i_size
;
689 map
->m_flags
= EROFS_MAP_MAPPED
| EROFS_MAP_FULL_MAPPED
|
694 err
= z_erofs_do_map_blocks(vi
, map
, flags
);
696 DBG_BUGON(err
< 0 && err
!= -ENOMEM
);