1 // SPDX-License-Identifier: GPL-2.0+
2 /*
3 * erofs-utils/lib/zmap.c
4 *
5 * (a large amount of code was adapted from Linux kernel. )
6 *
7 * Copyright (C) 2018-2019 HUAWEI, Inc.
8 * https://www.huawei.com/
9 * Created by Gao Xiang <gaoxiang25@huawei.com>
10 * Modified by Huang Jianan <huangjianan@oppo.com>
11 */
12 #include "erofs/io.h"
13 #include "erofs/print.h"
14
z_erofs_fill_inode(struct erofs_inode * vi)15 int z_erofs_fill_inode(struct erofs_inode *vi)
16 {
17 if (vi->datalayout == EROFS_INODE_FLAT_COMPRESSION_LEGACY) {
18 vi->z_advise = 0;
19 vi->z_algorithmtype[0] = 0;
20 vi->z_algorithmtype[1] = 0;
21 vi->z_logical_clusterbits = LOG_BLOCK_SIZE;
22 vi->z_physical_clusterbits[0] = vi->z_logical_clusterbits;
23 vi->z_physical_clusterbits[1] = vi->z_logical_clusterbits;
24
25 vi->flags |= EROFS_I_Z_INITED;
26 }
27 return 0;
28 }
29
z_erofs_fill_inode_lazy(struct erofs_inode * vi)30 static int z_erofs_fill_inode_lazy(struct erofs_inode *vi)
31 {
32 int ret;
33 erofs_off_t pos;
34 struct z_erofs_map_header *h;
35 char buf[sizeof(struct z_erofs_map_header)];
36
37 if (vi->flags & EROFS_I_Z_INITED)
38 return 0;
39
40 DBG_BUGON(vi->datalayout == EROFS_INODE_FLAT_COMPRESSION_LEGACY);
41 pos = round_up(iloc(vi->nid) + vi->inode_isize + vi->xattr_isize, 8);
42
43 ret = dev_read(buf, pos, sizeof(buf));
44 if (ret < 0)
45 return -EIO;
46
47 h = (struct z_erofs_map_header *)buf;
48 vi->z_advise = le16_to_cpu(h->h_advise);
49 vi->z_algorithmtype[0] = h->h_algorithmtype & 15;
50 vi->z_algorithmtype[1] = h->h_algorithmtype >> 4;
51
52 if (vi->z_algorithmtype[0] >= Z_EROFS_COMPRESSION_MAX) {
53 erofs_err("unknown compression format %u for nid %llu",
54 vi->z_algorithmtype[0], (unsigned long long)vi->nid);
55 return -EOPNOTSUPP;
56 }
57
58 vi->z_logical_clusterbits = LOG_BLOCK_SIZE + (h->h_clusterbits & 7);
59 vi->z_physical_clusterbits[0] = vi->z_logical_clusterbits +
60 ((h->h_clusterbits >> 3) & 3);
61
62 if (vi->z_physical_clusterbits[0] != LOG_BLOCK_SIZE) {
63 erofs_err("unsupported physical clusterbits %u for nid %llu",
64 vi->z_physical_clusterbits[0], (unsigned long long)vi->nid);
65 return -EOPNOTSUPP;
66 }
67
68 vi->z_physical_clusterbits[1] = vi->z_logical_clusterbits +
69 ((h->h_clusterbits >> 5) & 7);
70 vi->flags |= EROFS_I_Z_INITED;
71 return 0;
72 }
73
74 struct z_erofs_maprecorder {
75 struct erofs_inode *inode;
76 struct erofs_map_blocks *map;
77 void *kaddr;
78
79 unsigned long lcn;
80 /* compression extent information gathered */
81 u8 type;
82 u16 clusterofs;
83 u16 delta[2];
84 erofs_blk_t pblk;
85 };
86
z_erofs_reload_indexes(struct z_erofs_maprecorder * m,erofs_blk_t eblk)87 static int z_erofs_reload_indexes(struct z_erofs_maprecorder *m,
88 erofs_blk_t eblk)
89 {
90 int ret;
91 struct erofs_map_blocks *const map = m->map;
92 char *mpage = map->mpage;
93
94 if (map->index == eblk)
95 return 0;
96
97 ret = blk_read(mpage, eblk, 1);
98 if (ret < 0)
99 return -EIO;
100
101 map->index = eblk;
102
103 return 0;
104 }
105
legacy_load_cluster_from_disk(struct z_erofs_maprecorder * m,unsigned long lcn)106 static int legacy_load_cluster_from_disk(struct z_erofs_maprecorder *m,
107 unsigned long lcn)
108 {
109 struct erofs_inode *const vi = m->inode;
110 const erofs_off_t ibase = iloc(vi->nid);
111 const erofs_off_t pos =
112 Z_EROFS_VLE_LEGACY_INDEX_ALIGN(ibase + vi->inode_isize +
113 vi->xattr_isize) +
114 lcn * sizeof(struct z_erofs_vle_decompressed_index);
115 struct z_erofs_vle_decompressed_index *di;
116 unsigned int advise, type;
117 int err;
118
119 err = z_erofs_reload_indexes(m, erofs_blknr(pos));
120 if (err)
121 return err;
122
123 m->lcn = lcn;
124 di = m->kaddr + erofs_blkoff(pos);
125
126 advise = le16_to_cpu(di->di_advise);
127 type = (advise >> Z_EROFS_VLE_DI_CLUSTER_TYPE_BIT) &
128 ((1 << Z_EROFS_VLE_DI_CLUSTER_TYPE_BITS) - 1);
129 switch (type) {
130 case Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD:
131 m->clusterofs = 1 << vi->z_logical_clusterbits;
132 m->delta[0] = le16_to_cpu(di->di_u.delta[0]);
133 m->delta[1] = le16_to_cpu(di->di_u.delta[1]);
134 break;
135 case Z_EROFS_VLE_CLUSTER_TYPE_PLAIN:
136 case Z_EROFS_VLE_CLUSTER_TYPE_HEAD:
137 m->clusterofs = le16_to_cpu(di->di_clusterofs);
138 m->pblk = le32_to_cpu(di->di_u.blkaddr);
139 break;
140 default:
141 DBG_BUGON(1);
142 return -EOPNOTSUPP;
143 }
144 m->type = type;
145 return 0;
146 }
147
decode_compactedbits(unsigned int lobits,unsigned int lomask,u8 * in,unsigned int pos,u8 * type)148 static unsigned int decode_compactedbits(unsigned int lobits,
149 unsigned int lomask,
150 u8 *in, unsigned int pos, u8 *type)
151 {
152 const unsigned int v = get_unaligned_le32(in + pos / 8) >> (pos & 7);
153 const unsigned int lo = v & lomask;
154
155 *type = (v >> lobits) & 3;
156 return lo;
157 }
158
unpack_compacted_index(struct z_erofs_maprecorder * m,unsigned int amortizedshift,unsigned int eofs)159 static int unpack_compacted_index(struct z_erofs_maprecorder *m,
160 unsigned int amortizedshift,
161 unsigned int eofs)
162 {
163 struct erofs_inode *const vi = m->inode;
164 const unsigned int lclusterbits = vi->z_logical_clusterbits;
165 const unsigned int lomask = (1 << lclusterbits) - 1;
166 unsigned int vcnt, base, lo, encodebits, nblk;
167 int i;
168 u8 *in, type;
169
170 if (1 << amortizedshift == 4)
171 vcnt = 2;
172 else if (1 << amortizedshift == 2 && lclusterbits == 12)
173 vcnt = 16;
174 else
175 return -EOPNOTSUPP;
176
177 encodebits = ((vcnt << amortizedshift) - sizeof(__le32)) * 8 / vcnt;
178 base = round_down(eofs, vcnt << amortizedshift);
179 in = m->kaddr + base;
180
181 i = (eofs - base) >> amortizedshift;
182
183 lo = decode_compactedbits(lclusterbits, lomask,
184 in, encodebits * i, &type);
185 m->type = type;
186 if (type == Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD) {
187 m->clusterofs = 1 << lclusterbits;
188 if (i + 1 != (int)vcnt) {
189 m->delta[0] = lo;
190 return 0;
191 }
192 /*
193 * since the last lcluster in the pack is special,
194 * of which lo saves delta[1] rather than delta[0].
195 * Hence, get delta[0] by the previous lcluster indirectly.
196 */
197 lo = decode_compactedbits(lclusterbits, lomask,
198 in, encodebits * (i - 1), &type);
199 if (type != Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD)
200 lo = 0;
201 m->delta[0] = lo + 1;
202 return 0;
203 }
204 m->clusterofs = lo;
205 m->delta[0] = 0;
206 /* figout out blkaddr (pblk) for HEAD lclusters */
207 nblk = 1;
208 while (i > 0) {
209 --i;
210 lo = decode_compactedbits(lclusterbits, lomask,
211 in, encodebits * i, &type);
212 if (type == Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD)
213 i -= lo;
214
215 if (i >= 0)
216 ++nblk;
217 }
218 in += (vcnt << amortizedshift) - sizeof(__le32);
219 m->pblk = le32_to_cpu(*(__le32 *)in) + nblk;
220 return 0;
221 }
222
compacted_load_cluster_from_disk(struct z_erofs_maprecorder * m,unsigned long lcn)223 static int compacted_load_cluster_from_disk(struct z_erofs_maprecorder *m,
224 unsigned long lcn)
225 {
226 struct erofs_inode *const vi = m->inode;
227 const unsigned int lclusterbits = vi->z_logical_clusterbits;
228 const erofs_off_t ebase = round_up(iloc(vi->nid) + vi->inode_isize +
229 vi->xattr_isize, 8) +
230 sizeof(struct z_erofs_map_header);
231 const unsigned int totalidx = DIV_ROUND_UP(vi->i_size, EROFS_BLKSIZ);
232 unsigned int compacted_4b_initial, compacted_2b;
233 unsigned int amortizedshift;
234 erofs_off_t pos;
235 int err;
236
237 if (lclusterbits != 12)
238 return -EOPNOTSUPP;
239
240 if (lcn >= totalidx)
241 return -EINVAL;
242
243 m->lcn = lcn;
244 /* used to align to 32-byte (compacted_2b) alignment */
245 compacted_4b_initial = (32 - ebase % 32) / 4;
246 if (compacted_4b_initial == 32 / 4)
247 compacted_4b_initial = 0;
248
249 if (vi->z_advise & Z_EROFS_ADVISE_COMPACTED_2B)
250 compacted_2b = rounddown(totalidx - compacted_4b_initial, 16);
251 else
252 compacted_2b = 0;
253
254 pos = ebase;
255 if (lcn < compacted_4b_initial) {
256 amortizedshift = 2;
257 goto out;
258 }
259 pos += compacted_4b_initial * 4;
260 lcn -= compacted_4b_initial;
261
262 if (lcn < compacted_2b) {
263 amortizedshift = 1;
264 goto out;
265 }
266 pos += compacted_2b * 2;
267 lcn -= compacted_2b;
268 amortizedshift = 2;
269 out:
270 pos += lcn * (1 << amortizedshift);
271 err = z_erofs_reload_indexes(m, erofs_blknr(pos));
272 if (err)
273 return err;
274 return unpack_compacted_index(m, amortizedshift, erofs_blkoff(pos));
275 }
276
z_erofs_load_cluster_from_disk(struct z_erofs_maprecorder * m,unsigned int lcn)277 static int z_erofs_load_cluster_from_disk(struct z_erofs_maprecorder *m,
278 unsigned int lcn)
279 {
280 const unsigned int datamode = m->inode->datalayout;
281
282 if (datamode == EROFS_INODE_FLAT_COMPRESSION_LEGACY)
283 return legacy_load_cluster_from_disk(m, lcn);
284
285 if (datamode == EROFS_INODE_FLAT_COMPRESSION)
286 return compacted_load_cluster_from_disk(m, lcn);
287
288 return -EINVAL;
289 }
290
z_erofs_extent_lookback(struct z_erofs_maprecorder * m,unsigned int lookback_distance)291 static int z_erofs_extent_lookback(struct z_erofs_maprecorder *m,
292 unsigned int lookback_distance)
293 {
294 struct erofs_inode *const vi = m->inode;
295 struct erofs_map_blocks *const map = m->map;
296 const unsigned int lclusterbits = vi->z_logical_clusterbits;
297 unsigned long lcn = m->lcn;
298 int err;
299
300 if (lcn < lookback_distance) {
301 erofs_err("bogus lookback distance @ nid %llu",
302 (unsigned long long)vi->nid);
303 DBG_BUGON(1);
304 return -EFSCORRUPTED;
305 }
306
307 /* load extent head logical cluster if needed */
308 lcn -= lookback_distance;
309 err = z_erofs_load_cluster_from_disk(m, lcn);
310 if (err)
311 return err;
312
313 switch (m->type) {
314 case Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD:
315 if (!m->delta[0]) {
316 erofs_err("invalid lookback distance 0 @ nid %llu",
317 (unsigned long long)vi->nid);
318 DBG_BUGON(1);
319 return -EFSCORRUPTED;
320 }
321 return z_erofs_extent_lookback(m, m->delta[0]);
322 case Z_EROFS_VLE_CLUSTER_TYPE_PLAIN:
323 map->m_flags &= ~EROFS_MAP_ZIPPED;
324 case Z_EROFS_VLE_CLUSTER_TYPE_HEAD:
325 map->m_la = (lcn << lclusterbits) | m->clusterofs;
326 break;
327 default:
328 erofs_err("unknown type %u @ lcn %lu of nid %llu",
329 m->type, lcn, (unsigned long long)vi->nid);
330 DBG_BUGON(1);
331 return -EOPNOTSUPP;
332 }
333 return 0;
334 }
335
z_erofs_map_blocks_iter(struct erofs_inode * vi,struct erofs_map_blocks * map)336 int z_erofs_map_blocks_iter(struct erofs_inode *vi,
337 struct erofs_map_blocks *map)
338 {
339 struct z_erofs_maprecorder m = {
340 .inode = vi,
341 .map = map,
342 .kaddr = map->mpage,
343 };
344 int err = 0;
345 unsigned int lclusterbits, endoff;
346 unsigned long long ofs, end;
347
348 /* when trying to read beyond EOF, leave it unmapped */
349 if (map->m_la >= vi->i_size) {
350 map->m_llen = map->m_la + 1 - vi->i_size;
351 map->m_la = vi->i_size;
352 map->m_flags = 0;
353 goto out;
354 }
355
356 err = z_erofs_fill_inode_lazy(vi);
357 if (err)
358 goto out;
359
360 lclusterbits = vi->z_logical_clusterbits;
361 ofs = map->m_la;
362 m.lcn = ofs >> lclusterbits;
363 endoff = ofs & ((1 << lclusterbits) - 1);
364
365 err = z_erofs_load_cluster_from_disk(&m, m.lcn);
366 if (err)
367 goto out;
368
369 map->m_flags = EROFS_MAP_ZIPPED; /* by default, compressed */
370 end = (m.lcn + 1ULL) << lclusterbits;
371 switch (m.type) {
372 case Z_EROFS_VLE_CLUSTER_TYPE_PLAIN:
373 if (endoff >= m.clusterofs)
374 map->m_flags &= ~EROFS_MAP_ZIPPED;
375 case Z_EROFS_VLE_CLUSTER_TYPE_HEAD:
376 if (endoff >= m.clusterofs) {
377 map->m_la = (m.lcn << lclusterbits) | m.clusterofs;
378 break;
379 }
380 /* m.lcn should be >= 1 if endoff < m.clusterofs */
381 if (!m.lcn) {
382 erofs_err("invalid logical cluster 0 at nid %llu",
383 (unsigned long long)vi->nid);
384 err = -EFSCORRUPTED;
385 goto out;
386 }
387 end = (m.lcn << lclusterbits) | m.clusterofs;
388 map->m_flags |= EROFS_MAP_FULL_MAPPED;
389 m.delta[0] = 1;
390 case Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD:
391 /* get the correspoinding first chunk */
392 err = z_erofs_extent_lookback(&m, m.delta[0]);
393 if (err)
394 goto out;
395 break;
396 default:
397 erofs_err("unknown type %u @ offset %llu of nid %llu",
398 m.type, ofs, (unsigned long long)vi->nid);
399 err = -EOPNOTSUPP;
400 goto out;
401 }
402
403 map->m_llen = end - map->m_la;
404 map->m_plen = 1 << lclusterbits;
405 map->m_pa = blknr_to_addr(m.pblk);
406 map->m_flags |= EROFS_MAP_MAPPED;
407
408 out:
409 erofs_dbg("m_la %" PRIu64 " m_pa %" PRIu64 " m_llen %" PRIu64 " m_plen %" PRIu64 " m_flags 0%o",
410 map->m_la, map->m_pa,
411 map->m_llen, map->m_plen, map->m_flags);
412
413 DBG_BUGON(err < 0 && err != -ENOMEM);
414 return err;
415 }
416