1 | // SPDX-License-Identifier: GPL-2.0-only |
2 | /* |
3 | * This file is part of UBIFS. |
4 | * |
5 | * Copyright (C) 2006-2008 Nokia Corporation. |
6 | * |
7 | * Authors: Adrian Hunter |
8 | * Artem Bityutskiy (Битюцкий Артём) |
9 | */ |
10 | |
11 | /* |
12 | * This file implements the LEB properties tree (LPT) area. The LPT area |
13 | * contains the LEB properties tree, a table of LPT area eraseblocks (ltab), and |
14 | * (for the "big" model) a table of saved LEB numbers (lsave). The LPT area sits |
15 | * between the log and the orphan area. |
16 | * |
17 | * The LPT area is like a miniature self-contained file system. It is required |
18 | * that it never runs out of space, is fast to access and update, and scales |
19 | * logarithmically. The LEB properties tree is implemented as a wandering tree |
20 | * much like the TNC, and the LPT area has its own garbage collection. |
21 | * |
22 | * The LPT has two slightly different forms called the "small model" and the |
23 | * "big model". The small model is used when the entire LEB properties table |
24 | * can be written into a single eraseblock. In that case, garbage collection |
25 | * consists of just writing the whole table, which therefore makes all other |
26 | * eraseblocks reusable. In the case of the big model, dirty eraseblocks are |
27 | * selected for garbage collection, which consists of marking the clean nodes in |
28 | * that LEB as dirty, and then only the dirty nodes are written out. Also, in |
29 | * the case of the big model, a table of LEB numbers is saved so that the entire |
30 | * LPT does not to be scanned looking for empty eraseblocks when UBIFS is first |
31 | * mounted. |
32 | */ |
33 | |
34 | #include "ubifs.h" |
35 | #include <linux/crc16.h> |
36 | #include <linux/math64.h> |
37 | #include <linux/slab.h> |
38 | |
39 | /** |
40 | * do_calc_lpt_geom - calculate sizes for the LPT area. |
41 | * @c: the UBIFS file-system description object |
42 | * |
43 | * Calculate the sizes of LPT bit fields, nodes, and tree, based on the |
44 | * properties of the flash and whether LPT is "big" (c->big_lpt). |
45 | */ |
46 | static void do_calc_lpt_geom(struct ubifs_info *c) |
47 | { |
48 | int i, n, bits, per_leb_wastage, max_pnode_cnt; |
49 | long long sz, tot_wastage; |
50 | |
51 | n = c->main_lebs + c->max_leb_cnt - c->leb_cnt; |
52 | max_pnode_cnt = DIV_ROUND_UP(n, UBIFS_LPT_FANOUT); |
53 | |
54 | c->lpt_hght = 1; |
55 | n = UBIFS_LPT_FANOUT; |
56 | while (n < max_pnode_cnt) { |
57 | c->lpt_hght += 1; |
58 | n <<= UBIFS_LPT_FANOUT_SHIFT; |
59 | } |
60 | |
61 | c->pnode_cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT); |
62 | |
63 | n = DIV_ROUND_UP(c->pnode_cnt, UBIFS_LPT_FANOUT); |
64 | c->nnode_cnt = n; |
65 | for (i = 1; i < c->lpt_hght; i++) { |
66 | n = DIV_ROUND_UP(n, UBIFS_LPT_FANOUT); |
67 | c->nnode_cnt += n; |
68 | } |
69 | |
70 | c->space_bits = fls(x: c->leb_size) - 3; |
71 | c->lpt_lnum_bits = fls(x: c->lpt_lebs); |
72 | c->lpt_offs_bits = fls(x: c->leb_size - 1); |
73 | c->lpt_spc_bits = fls(x: c->leb_size); |
74 | |
75 | n = DIV_ROUND_UP(c->max_leb_cnt, UBIFS_LPT_FANOUT); |
76 | c->pcnt_bits = fls(x: n - 1); |
77 | |
78 | c->lnum_bits = fls(x: c->max_leb_cnt - 1); |
79 | |
80 | bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS + |
81 | (c->big_lpt ? c->pcnt_bits : 0) + |
82 | (c->space_bits * 2 + 1) * UBIFS_LPT_FANOUT; |
83 | c->pnode_sz = (bits + 7) / 8; |
84 | |
85 | bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS + |
86 | (c->big_lpt ? c->pcnt_bits : 0) + |
87 | (c->lpt_lnum_bits + c->lpt_offs_bits) * UBIFS_LPT_FANOUT; |
88 | c->nnode_sz = (bits + 7) / 8; |
89 | |
90 | bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS + |
91 | c->lpt_lebs * c->lpt_spc_bits * 2; |
92 | c->ltab_sz = (bits + 7) / 8; |
93 | |
94 | bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS + |
95 | c->lnum_bits * c->lsave_cnt; |
96 | c->lsave_sz = (bits + 7) / 8; |
97 | |
98 | /* Calculate the minimum LPT size */ |
99 | c->lpt_sz = (long long)c->pnode_cnt * c->pnode_sz; |
100 | c->lpt_sz += (long long)c->nnode_cnt * c->nnode_sz; |
101 | c->lpt_sz += c->ltab_sz; |
102 | if (c->big_lpt) |
103 | c->lpt_sz += c->lsave_sz; |
104 | |
105 | /* Add wastage */ |
106 | sz = c->lpt_sz; |
107 | per_leb_wastage = max_t(int, c->pnode_sz, c->nnode_sz); |
108 | sz += per_leb_wastage; |
109 | tot_wastage = per_leb_wastage; |
110 | while (sz > c->leb_size) { |
111 | sz += per_leb_wastage; |
112 | sz -= c->leb_size; |
113 | tot_wastage += per_leb_wastage; |
114 | } |
115 | tot_wastage += ALIGN(sz, c->min_io_size) - sz; |
116 | c->lpt_sz += tot_wastage; |
117 | } |
118 | |
119 | /** |
120 | * ubifs_calc_lpt_geom - calculate and check sizes for the LPT area. |
121 | * @c: the UBIFS file-system description object |
122 | * |
123 | * This function returns %0 on success and a negative error code on failure. |
124 | */ |
125 | int ubifs_calc_lpt_geom(struct ubifs_info *c) |
126 | { |
127 | int lebs_needed; |
128 | long long sz; |
129 | |
130 | do_calc_lpt_geom(c); |
131 | |
132 | /* Verify that lpt_lebs is big enough */ |
133 | sz = c->lpt_sz * 2; /* Must have at least 2 times the size */ |
134 | lebs_needed = div_u64(dividend: sz + c->leb_size - 1, divisor: c->leb_size); |
135 | if (lebs_needed > c->lpt_lebs) { |
136 | ubifs_err(c, fmt: "too few LPT LEBs" ); |
137 | return -EINVAL; |
138 | } |
139 | |
140 | /* Verify that ltab fits in a single LEB (since ltab is a single node */ |
141 | if (c->ltab_sz > c->leb_size) { |
142 | ubifs_err(c, fmt: "LPT ltab too big" ); |
143 | return -EINVAL; |
144 | } |
145 | |
146 | c->check_lpt_free = c->big_lpt; |
147 | return 0; |
148 | } |
149 | |
150 | /** |
151 | * calc_dflt_lpt_geom - calculate default LPT geometry. |
152 | * @c: the UBIFS file-system description object |
153 | * @main_lebs: number of main area LEBs is passed and returned here |
154 | * @big_lpt: whether the LPT area is "big" is returned here |
155 | * |
156 | * The size of the LPT area depends on parameters that themselves are dependent |
157 | * on the size of the LPT area. This function, successively recalculates the LPT |
158 | * area geometry until the parameters and resultant geometry are consistent. |
159 | * |
160 | * This function returns %0 on success and a negative error code on failure. |
161 | */ |
162 | static int calc_dflt_lpt_geom(struct ubifs_info *c, int *main_lebs, |
163 | int *big_lpt) |
164 | { |
165 | int i, lebs_needed; |
166 | long long sz; |
167 | |
168 | /* Start by assuming the minimum number of LPT LEBs */ |
169 | c->lpt_lebs = UBIFS_MIN_LPT_LEBS; |
170 | c->main_lebs = *main_lebs - c->lpt_lebs; |
171 | if (c->main_lebs <= 0) |
172 | return -EINVAL; |
173 | |
174 | /* And assume we will use the small LPT model */ |
175 | c->big_lpt = 0; |
176 | |
177 | /* |
178 | * Calculate the geometry based on assumptions above and then see if it |
179 | * makes sense |
180 | */ |
181 | do_calc_lpt_geom(c); |
182 | |
183 | /* Small LPT model must have lpt_sz < leb_size */ |
184 | if (c->lpt_sz > c->leb_size) { |
185 | /* Nope, so try again using big LPT model */ |
186 | c->big_lpt = 1; |
187 | do_calc_lpt_geom(c); |
188 | } |
189 | |
190 | /* Now check there are enough LPT LEBs */ |
191 | for (i = 0; i < 64 ; i++) { |
192 | sz = c->lpt_sz * 4; /* Allow 4 times the size */ |
193 | lebs_needed = div_u64(dividend: sz + c->leb_size - 1, divisor: c->leb_size); |
194 | if (lebs_needed > c->lpt_lebs) { |
195 | /* Not enough LPT LEBs so try again with more */ |
196 | c->lpt_lebs = lebs_needed; |
197 | c->main_lebs = *main_lebs - c->lpt_lebs; |
198 | if (c->main_lebs <= 0) |
199 | return -EINVAL; |
200 | do_calc_lpt_geom(c); |
201 | continue; |
202 | } |
203 | if (c->ltab_sz > c->leb_size) { |
204 | ubifs_err(c, fmt: "LPT ltab too big" ); |
205 | return -EINVAL; |
206 | } |
207 | *main_lebs = c->main_lebs; |
208 | *big_lpt = c->big_lpt; |
209 | return 0; |
210 | } |
211 | return -EINVAL; |
212 | } |
213 | |
214 | /** |
215 | * pack_bits - pack bit fields end-to-end. |
216 | * @c: UBIFS file-system description object |
217 | * @addr: address at which to pack (passed and next address returned) |
218 | * @pos: bit position at which to pack (passed and next position returned) |
219 | * @val: value to pack |
220 | * @nrbits: number of bits of value to pack (1-32) |
221 | */ |
222 | static void pack_bits(const struct ubifs_info *c, uint8_t **addr, int *pos, uint32_t val, int nrbits) |
223 | { |
224 | uint8_t *p = *addr; |
225 | int b = *pos; |
226 | |
227 | ubifs_assert(c, nrbits > 0); |
228 | ubifs_assert(c, nrbits <= 32); |
229 | ubifs_assert(c, *pos >= 0); |
230 | ubifs_assert(c, *pos < 8); |
231 | ubifs_assert(c, (val >> nrbits) == 0 || nrbits == 32); |
232 | if (b) { |
233 | *p |= ((uint8_t)val) << b; |
234 | nrbits += b; |
235 | if (nrbits > 8) { |
236 | *++p = (uint8_t)(val >>= (8 - b)); |
237 | if (nrbits > 16) { |
238 | *++p = (uint8_t)(val >>= 8); |
239 | if (nrbits > 24) { |
240 | *++p = (uint8_t)(val >>= 8); |
241 | if (nrbits > 32) |
242 | *++p = (uint8_t)(val >>= 8); |
243 | } |
244 | } |
245 | } |
246 | } else { |
247 | *p = (uint8_t)val; |
248 | if (nrbits > 8) { |
249 | *++p = (uint8_t)(val >>= 8); |
250 | if (nrbits > 16) { |
251 | *++p = (uint8_t)(val >>= 8); |
252 | if (nrbits > 24) |
253 | *++p = (uint8_t)(val >>= 8); |
254 | } |
255 | } |
256 | } |
257 | b = nrbits & 7; |
258 | if (b == 0) |
259 | p++; |
260 | *addr = p; |
261 | *pos = b; |
262 | } |
263 | |
264 | /** |
265 | * ubifs_unpack_bits - unpack bit fields. |
266 | * @c: UBIFS file-system description object |
267 | * @addr: address at which to unpack (passed and next address returned) |
268 | * @pos: bit position at which to unpack (passed and next position returned) |
269 | * @nrbits: number of bits of value to unpack (1-32) |
270 | * |
271 | * This functions returns the value unpacked. |
272 | */ |
273 | uint32_t ubifs_unpack_bits(const struct ubifs_info *c, uint8_t **addr, int *pos, int nrbits) |
274 | { |
275 | const int k = 32 - nrbits; |
276 | uint8_t *p = *addr; |
277 | int b = *pos; |
278 | uint32_t val; |
279 | const int bytes = (nrbits + b + 7) >> 3; |
280 | |
281 | ubifs_assert(c, nrbits > 0); |
282 | ubifs_assert(c, nrbits <= 32); |
283 | ubifs_assert(c, *pos >= 0); |
284 | ubifs_assert(c, *pos < 8); |
285 | if (b) { |
286 | switch (bytes) { |
287 | case 2: |
288 | val = p[1]; |
289 | break; |
290 | case 3: |
291 | val = p[1] | ((uint32_t)p[2] << 8); |
292 | break; |
293 | case 4: |
294 | val = p[1] | ((uint32_t)p[2] << 8) | |
295 | ((uint32_t)p[3] << 16); |
296 | break; |
297 | case 5: |
298 | val = p[1] | ((uint32_t)p[2] << 8) | |
299 | ((uint32_t)p[3] << 16) | |
300 | ((uint32_t)p[4] << 24); |
301 | } |
302 | val <<= (8 - b); |
303 | val |= *p >> b; |
304 | nrbits += b; |
305 | } else { |
306 | switch (bytes) { |
307 | case 1: |
308 | val = p[0]; |
309 | break; |
310 | case 2: |
311 | val = p[0] | ((uint32_t)p[1] << 8); |
312 | break; |
313 | case 3: |
314 | val = p[0] | ((uint32_t)p[1] << 8) | |
315 | ((uint32_t)p[2] << 16); |
316 | break; |
317 | case 4: |
318 | val = p[0] | ((uint32_t)p[1] << 8) | |
319 | ((uint32_t)p[2] << 16) | |
320 | ((uint32_t)p[3] << 24); |
321 | break; |
322 | } |
323 | } |
324 | val <<= k; |
325 | val >>= k; |
326 | b = nrbits & 7; |
327 | p += nrbits >> 3; |
328 | *addr = p; |
329 | *pos = b; |
330 | ubifs_assert(c, (val >> nrbits) == 0 || nrbits - b == 32); |
331 | return val; |
332 | } |
333 | |
334 | /** |
335 | * ubifs_pack_pnode - pack all the bit fields of a pnode. |
336 | * @c: UBIFS file-system description object |
337 | * @buf: buffer into which to pack |
338 | * @pnode: pnode to pack |
339 | */ |
340 | void ubifs_pack_pnode(struct ubifs_info *c, void *buf, |
341 | struct ubifs_pnode *pnode) |
342 | { |
343 | uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; |
344 | int i, pos = 0; |
345 | uint16_t crc; |
346 | |
347 | pack_bits(c, addr: &addr, pos: &pos, val: UBIFS_LPT_PNODE, UBIFS_LPT_TYPE_BITS); |
348 | if (c->big_lpt) |
349 | pack_bits(c, addr: &addr, pos: &pos, val: pnode->num, nrbits: c->pcnt_bits); |
350 | for (i = 0; i < UBIFS_LPT_FANOUT; i++) { |
351 | pack_bits(c, addr: &addr, pos: &pos, val: pnode->lprops[i].free >> 3, |
352 | nrbits: c->space_bits); |
353 | pack_bits(c, addr: &addr, pos: &pos, val: pnode->lprops[i].dirty >> 3, |
354 | nrbits: c->space_bits); |
355 | if (pnode->lprops[i].flags & LPROPS_INDEX) |
356 | pack_bits(c, addr: &addr, pos: &pos, val: 1, nrbits: 1); |
357 | else |
358 | pack_bits(c, addr: &addr, pos: &pos, val: 0, nrbits: 1); |
359 | } |
360 | crc = crc16(crc: -1, buffer: buf + UBIFS_LPT_CRC_BYTES, |
361 | len: c->pnode_sz - UBIFS_LPT_CRC_BYTES); |
362 | addr = buf; |
363 | pos = 0; |
364 | pack_bits(c, addr: &addr, pos: &pos, val: crc, UBIFS_LPT_CRC_BITS); |
365 | } |
366 | |
367 | /** |
368 | * ubifs_pack_nnode - pack all the bit fields of a nnode. |
369 | * @c: UBIFS file-system description object |
370 | * @buf: buffer into which to pack |
371 | * @nnode: nnode to pack |
372 | */ |
373 | void ubifs_pack_nnode(struct ubifs_info *c, void *buf, |
374 | struct ubifs_nnode *nnode) |
375 | { |
376 | uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; |
377 | int i, pos = 0; |
378 | uint16_t crc; |
379 | |
380 | pack_bits(c, addr: &addr, pos: &pos, val: UBIFS_LPT_NNODE, UBIFS_LPT_TYPE_BITS); |
381 | if (c->big_lpt) |
382 | pack_bits(c, addr: &addr, pos: &pos, val: nnode->num, nrbits: c->pcnt_bits); |
383 | for (i = 0; i < UBIFS_LPT_FANOUT; i++) { |
384 | int lnum = nnode->nbranch[i].lnum; |
385 | |
386 | if (lnum == 0) |
387 | lnum = c->lpt_last + 1; |
388 | pack_bits(c, addr: &addr, pos: &pos, val: lnum - c->lpt_first, nrbits: c->lpt_lnum_bits); |
389 | pack_bits(c, addr: &addr, pos: &pos, val: nnode->nbranch[i].offs, |
390 | nrbits: c->lpt_offs_bits); |
391 | } |
392 | crc = crc16(crc: -1, buffer: buf + UBIFS_LPT_CRC_BYTES, |
393 | len: c->nnode_sz - UBIFS_LPT_CRC_BYTES); |
394 | addr = buf; |
395 | pos = 0; |
396 | pack_bits(c, addr: &addr, pos: &pos, val: crc, UBIFS_LPT_CRC_BITS); |
397 | } |
398 | |
399 | /** |
400 | * ubifs_pack_ltab - pack the LPT's own lprops table. |
401 | * @c: UBIFS file-system description object |
402 | * @buf: buffer into which to pack |
403 | * @ltab: LPT's own lprops table to pack |
404 | */ |
405 | void ubifs_pack_ltab(struct ubifs_info *c, void *buf, |
406 | struct ubifs_lpt_lprops *ltab) |
407 | { |
408 | uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; |
409 | int i, pos = 0; |
410 | uint16_t crc; |
411 | |
412 | pack_bits(c, addr: &addr, pos: &pos, val: UBIFS_LPT_LTAB, UBIFS_LPT_TYPE_BITS); |
413 | for (i = 0; i < c->lpt_lebs; i++) { |
414 | pack_bits(c, addr: &addr, pos: &pos, val: ltab[i].free, nrbits: c->lpt_spc_bits); |
415 | pack_bits(c, addr: &addr, pos: &pos, val: ltab[i].dirty, nrbits: c->lpt_spc_bits); |
416 | } |
417 | crc = crc16(crc: -1, buffer: buf + UBIFS_LPT_CRC_BYTES, |
418 | len: c->ltab_sz - UBIFS_LPT_CRC_BYTES); |
419 | addr = buf; |
420 | pos = 0; |
421 | pack_bits(c, addr: &addr, pos: &pos, val: crc, UBIFS_LPT_CRC_BITS); |
422 | } |
423 | |
424 | /** |
425 | * ubifs_pack_lsave - pack the LPT's save table. |
426 | * @c: UBIFS file-system description object |
427 | * @buf: buffer into which to pack |
428 | * @lsave: LPT's save table to pack |
429 | */ |
430 | void ubifs_pack_lsave(struct ubifs_info *c, void *buf, int *lsave) |
431 | { |
432 | uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; |
433 | int i, pos = 0; |
434 | uint16_t crc; |
435 | |
436 | pack_bits(c, addr: &addr, pos: &pos, val: UBIFS_LPT_LSAVE, UBIFS_LPT_TYPE_BITS); |
437 | for (i = 0; i < c->lsave_cnt; i++) |
438 | pack_bits(c, addr: &addr, pos: &pos, val: lsave[i], nrbits: c->lnum_bits); |
439 | crc = crc16(crc: -1, buffer: buf + UBIFS_LPT_CRC_BYTES, |
440 | len: c->lsave_sz - UBIFS_LPT_CRC_BYTES); |
441 | addr = buf; |
442 | pos = 0; |
443 | pack_bits(c, addr: &addr, pos: &pos, val: crc, UBIFS_LPT_CRC_BITS); |
444 | } |
445 | |
446 | /** |
447 | * ubifs_add_lpt_dirt - add dirty space to LPT LEB properties. |
448 | * @c: UBIFS file-system description object |
449 | * @lnum: LEB number to which to add dirty space |
450 | * @dirty: amount of dirty space to add |
451 | */ |
452 | void ubifs_add_lpt_dirt(struct ubifs_info *c, int lnum, int dirty) |
453 | { |
454 | if (!dirty || !lnum) |
455 | return; |
456 | dbg_lp("LEB %d add %d to %d" , |
457 | lnum, dirty, c->ltab[lnum - c->lpt_first].dirty); |
458 | ubifs_assert(c, lnum >= c->lpt_first && lnum <= c->lpt_last); |
459 | c->ltab[lnum - c->lpt_first].dirty += dirty; |
460 | } |
461 | |
462 | /** |
463 | * set_ltab - set LPT LEB properties. |
464 | * @c: UBIFS file-system description object |
465 | * @lnum: LEB number |
466 | * @free: amount of free space |
467 | * @dirty: amount of dirty space |
468 | */ |
469 | static void set_ltab(struct ubifs_info *c, int lnum, int free, int dirty) |
470 | { |
471 | dbg_lp("LEB %d free %d dirty %d to %d %d" , |
472 | lnum, c->ltab[lnum - c->lpt_first].free, |
473 | c->ltab[lnum - c->lpt_first].dirty, free, dirty); |
474 | ubifs_assert(c, lnum >= c->lpt_first && lnum <= c->lpt_last); |
475 | c->ltab[lnum - c->lpt_first].free = free; |
476 | c->ltab[lnum - c->lpt_first].dirty = dirty; |
477 | } |
478 | |
479 | /** |
480 | * ubifs_add_nnode_dirt - add dirty space to LPT LEB properties. |
481 | * @c: UBIFS file-system description object |
482 | * @nnode: nnode for which to add dirt |
483 | */ |
484 | void ubifs_add_nnode_dirt(struct ubifs_info *c, struct ubifs_nnode *nnode) |
485 | { |
486 | struct ubifs_nnode *np = nnode->parent; |
487 | |
488 | if (np) |
489 | ubifs_add_lpt_dirt(c, lnum: np->nbranch[nnode->iip].lnum, |
490 | dirty: c->nnode_sz); |
491 | else { |
492 | ubifs_add_lpt_dirt(c, lnum: c->lpt_lnum, dirty: c->nnode_sz); |
493 | if (!(c->lpt_drty_flgs & LTAB_DIRTY)) { |
494 | c->lpt_drty_flgs |= LTAB_DIRTY; |
495 | ubifs_add_lpt_dirt(c, lnum: c->ltab_lnum, dirty: c->ltab_sz); |
496 | } |
497 | } |
498 | } |
499 | |
500 | /** |
501 | * add_pnode_dirt - add dirty space to LPT LEB properties. |
502 | * @c: UBIFS file-system description object |
503 | * @pnode: pnode for which to add dirt |
504 | */ |
505 | static void add_pnode_dirt(struct ubifs_info *c, struct ubifs_pnode *pnode) |
506 | { |
507 | ubifs_add_lpt_dirt(c, lnum: pnode->parent->nbranch[pnode->iip].lnum, |
508 | dirty: c->pnode_sz); |
509 | } |
510 | |
511 | /** |
512 | * calc_nnode_num - calculate nnode number. |
513 | * @row: the row in the tree (root is zero) |
514 | * @col: the column in the row (leftmost is zero) |
515 | * |
516 | * The nnode number is a number that uniquely identifies a nnode and can be used |
517 | * easily to traverse the tree from the root to that nnode. |
518 | * |
519 | * This function calculates and returns the nnode number for the nnode at @row |
520 | * and @col. |
521 | */ |
522 | static int calc_nnode_num(int row, int col) |
523 | { |
524 | int num, bits; |
525 | |
526 | num = 1; |
527 | while (row--) { |
528 | bits = (col & (UBIFS_LPT_FANOUT - 1)); |
529 | col >>= UBIFS_LPT_FANOUT_SHIFT; |
530 | num <<= UBIFS_LPT_FANOUT_SHIFT; |
531 | num |= bits; |
532 | } |
533 | return num; |
534 | } |
535 | |
536 | /** |
537 | * calc_nnode_num_from_parent - calculate nnode number. |
538 | * @c: UBIFS file-system description object |
539 | * @parent: parent nnode |
540 | * @iip: index in parent |
541 | * |
542 | * The nnode number is a number that uniquely identifies a nnode and can be used |
543 | * easily to traverse the tree from the root to that nnode. |
544 | * |
545 | * This function calculates and returns the nnode number based on the parent's |
546 | * nnode number and the index in parent. |
547 | */ |
548 | static int calc_nnode_num_from_parent(const struct ubifs_info *c, |
549 | struct ubifs_nnode *parent, int iip) |
550 | { |
551 | int num, shft; |
552 | |
553 | if (!parent) |
554 | return 1; |
555 | shft = (c->lpt_hght - parent->level) * UBIFS_LPT_FANOUT_SHIFT; |
556 | num = parent->num ^ (1 << shft); |
557 | num |= (UBIFS_LPT_FANOUT + iip) << shft; |
558 | return num; |
559 | } |
560 | |
561 | /** |
562 | * calc_pnode_num_from_parent - calculate pnode number. |
563 | * @c: UBIFS file-system description object |
564 | * @parent: parent nnode |
565 | * @iip: index in parent |
566 | * |
567 | * The pnode number is a number that uniquely identifies a pnode and can be used |
568 | * easily to traverse the tree from the root to that pnode. |
569 | * |
570 | * This function calculates and returns the pnode number based on the parent's |
571 | * nnode number and the index in parent. |
572 | */ |
573 | static int calc_pnode_num_from_parent(const struct ubifs_info *c, |
574 | struct ubifs_nnode *parent, int iip) |
575 | { |
576 | int i, n = c->lpt_hght - 1, pnum = parent->num, num = 0; |
577 | |
578 | for (i = 0; i < n; i++) { |
579 | num <<= UBIFS_LPT_FANOUT_SHIFT; |
580 | num |= pnum & (UBIFS_LPT_FANOUT - 1); |
581 | pnum >>= UBIFS_LPT_FANOUT_SHIFT; |
582 | } |
583 | num <<= UBIFS_LPT_FANOUT_SHIFT; |
584 | num |= iip; |
585 | return num; |
586 | } |
587 | |
588 | /** |
589 | * ubifs_create_dflt_lpt - create default LPT. |
590 | * @c: UBIFS file-system description object |
591 | * @main_lebs: number of main area LEBs is passed and returned here |
592 | * @lpt_first: LEB number of first LPT LEB |
593 | * @lpt_lebs: number of LEBs for LPT is passed and returned here |
594 | * @big_lpt: use big LPT model is passed and returned here |
595 | * @hash: hash of the LPT is returned here |
596 | * |
597 | * This function returns %0 on success and a negative error code on failure. |
598 | */ |
599 | int ubifs_create_dflt_lpt(struct ubifs_info *c, int *main_lebs, int lpt_first, |
600 | int *lpt_lebs, int *big_lpt, u8 *hash) |
601 | { |
602 | int lnum, err = 0, node_sz, iopos, i, j, cnt, len, alen, row; |
603 | int blnum, boffs, bsz, bcnt; |
604 | struct ubifs_pnode *pnode = NULL; |
605 | struct ubifs_nnode *nnode = NULL; |
606 | void *buf = NULL, *p; |
607 | struct ubifs_lpt_lprops *ltab = NULL; |
608 | int *lsave = NULL; |
609 | struct shash_desc *desc; |
610 | |
611 | err = calc_dflt_lpt_geom(c, main_lebs, big_lpt); |
612 | if (err) |
613 | return err; |
614 | *lpt_lebs = c->lpt_lebs; |
615 | |
616 | /* Needed by 'ubifs_pack_nnode()' and 'set_ltab()' */ |
617 | c->lpt_first = lpt_first; |
618 | /* Needed by 'set_ltab()' */ |
619 | c->lpt_last = lpt_first + c->lpt_lebs - 1; |
620 | /* Needed by 'ubifs_pack_lsave()' */ |
621 | c->main_first = c->leb_cnt - *main_lebs; |
622 | |
623 | desc = ubifs_hash_get_desc(c); |
624 | if (IS_ERR(ptr: desc)) |
625 | return PTR_ERR(ptr: desc); |
626 | |
627 | lsave = kmalloc_array(n: c->lsave_cnt, size: sizeof(int), GFP_KERNEL); |
628 | pnode = kzalloc(size: sizeof(struct ubifs_pnode), GFP_KERNEL); |
629 | nnode = kzalloc(size: sizeof(struct ubifs_nnode), GFP_KERNEL); |
630 | buf = vmalloc(size: c->leb_size); |
631 | ltab = vmalloc(array_size(sizeof(struct ubifs_lpt_lprops), |
632 | c->lpt_lebs)); |
633 | if (!pnode || !nnode || !buf || !ltab || !lsave) { |
634 | err = -ENOMEM; |
635 | goto out; |
636 | } |
637 | |
638 | ubifs_assert(c, !c->ltab); |
639 | c->ltab = ltab; /* Needed by set_ltab */ |
640 | |
641 | /* Initialize LPT's own lprops */ |
642 | for (i = 0; i < c->lpt_lebs; i++) { |
643 | ltab[i].free = c->leb_size; |
644 | ltab[i].dirty = 0; |
645 | ltab[i].tgc = 0; |
646 | ltab[i].cmt = 0; |
647 | } |
648 | |
649 | lnum = lpt_first; |
650 | p = buf; |
651 | /* Number of leaf nodes (pnodes) */ |
652 | cnt = c->pnode_cnt; |
653 | |
654 | /* |
655 | * The first pnode contains the LEB properties for the LEBs that contain |
656 | * the root inode node and the root index node of the index tree. |
657 | */ |
658 | node_sz = ALIGN(ubifs_idx_node_sz(c, 1), 8); |
659 | iopos = ALIGN(node_sz, c->min_io_size); |
660 | pnode->lprops[0].free = c->leb_size - iopos; |
661 | pnode->lprops[0].dirty = iopos - node_sz; |
662 | pnode->lprops[0].flags = LPROPS_INDEX; |
663 | |
664 | node_sz = UBIFS_INO_NODE_SZ; |
665 | iopos = ALIGN(node_sz, c->min_io_size); |
666 | pnode->lprops[1].free = c->leb_size - iopos; |
667 | pnode->lprops[1].dirty = iopos - node_sz; |
668 | |
669 | for (i = 2; i < UBIFS_LPT_FANOUT; i++) |
670 | pnode->lprops[i].free = c->leb_size; |
671 | |
672 | /* Add first pnode */ |
673 | ubifs_pack_pnode(c, buf: p, pnode); |
674 | err = ubifs_shash_update(c, desc, buf: p, len: c->pnode_sz); |
675 | if (err) |
676 | goto out; |
677 | |
678 | p += c->pnode_sz; |
679 | len = c->pnode_sz; |
680 | pnode->num += 1; |
681 | |
682 | /* Reset pnode values for remaining pnodes */ |
683 | pnode->lprops[0].free = c->leb_size; |
684 | pnode->lprops[0].dirty = 0; |
685 | pnode->lprops[0].flags = 0; |
686 | |
687 | pnode->lprops[1].free = c->leb_size; |
688 | pnode->lprops[1].dirty = 0; |
689 | |
690 | /* |
691 | * To calculate the internal node branches, we keep information about |
692 | * the level below. |
693 | */ |
694 | blnum = lnum; /* LEB number of level below */ |
695 | boffs = 0; /* Offset of level below */ |
696 | bcnt = cnt; /* Number of nodes in level below */ |
697 | bsz = c->pnode_sz; /* Size of nodes in level below */ |
698 | |
699 | /* Add all remaining pnodes */ |
700 | for (i = 1; i < cnt; i++) { |
701 | if (len + c->pnode_sz > c->leb_size) { |
702 | alen = ALIGN(len, c->min_io_size); |
703 | set_ltab(c, lnum, free: c->leb_size - alen, dirty: alen - len); |
704 | memset(p, 0xff, alen - len); |
705 | err = ubifs_leb_change(c, lnum: lnum++, buf, len: alen); |
706 | if (err) |
707 | goto out; |
708 | p = buf; |
709 | len = 0; |
710 | } |
711 | ubifs_pack_pnode(c, buf: p, pnode); |
712 | err = ubifs_shash_update(c, desc, buf: p, len: c->pnode_sz); |
713 | if (err) |
714 | goto out; |
715 | |
716 | p += c->pnode_sz; |
717 | len += c->pnode_sz; |
718 | /* |
719 | * pnodes are simply numbered left to right starting at zero, |
720 | * which means the pnode number can be used easily to traverse |
721 | * down the tree to the corresponding pnode. |
722 | */ |
723 | pnode->num += 1; |
724 | } |
725 | |
726 | row = 0; |
727 | for (i = UBIFS_LPT_FANOUT; cnt > i; i <<= UBIFS_LPT_FANOUT_SHIFT) |
728 | row += 1; |
729 | /* Add all nnodes, one level at a time */ |
730 | while (1) { |
731 | /* Number of internal nodes (nnodes) at next level */ |
732 | cnt = DIV_ROUND_UP(cnt, UBIFS_LPT_FANOUT); |
733 | for (i = 0; i < cnt; i++) { |
734 | if (len + c->nnode_sz > c->leb_size) { |
735 | alen = ALIGN(len, c->min_io_size); |
736 | set_ltab(c, lnum, free: c->leb_size - alen, |
737 | dirty: alen - len); |
738 | memset(p, 0xff, alen - len); |
739 | err = ubifs_leb_change(c, lnum: lnum++, buf, len: alen); |
740 | if (err) |
741 | goto out; |
742 | p = buf; |
743 | len = 0; |
744 | } |
745 | /* Only 1 nnode at this level, so it is the root */ |
746 | if (cnt == 1) { |
747 | c->lpt_lnum = lnum; |
748 | c->lpt_offs = len; |
749 | } |
750 | /* Set branches to the level below */ |
751 | for (j = 0; j < UBIFS_LPT_FANOUT; j++) { |
752 | if (bcnt) { |
753 | if (boffs + bsz > c->leb_size) { |
754 | blnum += 1; |
755 | boffs = 0; |
756 | } |
757 | nnode->nbranch[j].lnum = blnum; |
758 | nnode->nbranch[j].offs = boffs; |
759 | boffs += bsz; |
760 | bcnt--; |
761 | } else { |
762 | nnode->nbranch[j].lnum = 0; |
763 | nnode->nbranch[j].offs = 0; |
764 | } |
765 | } |
766 | nnode->num = calc_nnode_num(row, col: i); |
767 | ubifs_pack_nnode(c, buf: p, nnode); |
768 | p += c->nnode_sz; |
769 | len += c->nnode_sz; |
770 | } |
771 | /* Only 1 nnode at this level, so it is the root */ |
772 | if (cnt == 1) |
773 | break; |
774 | /* Update the information about the level below */ |
775 | bcnt = cnt; |
776 | bsz = c->nnode_sz; |
777 | row -= 1; |
778 | } |
779 | |
780 | if (*big_lpt) { |
781 | /* Need to add LPT's save table */ |
782 | if (len + c->lsave_sz > c->leb_size) { |
783 | alen = ALIGN(len, c->min_io_size); |
784 | set_ltab(c, lnum, free: c->leb_size - alen, dirty: alen - len); |
785 | memset(p, 0xff, alen - len); |
786 | err = ubifs_leb_change(c, lnum: lnum++, buf, len: alen); |
787 | if (err) |
788 | goto out; |
789 | p = buf; |
790 | len = 0; |
791 | } |
792 | |
793 | c->lsave_lnum = lnum; |
794 | c->lsave_offs = len; |
795 | |
796 | for (i = 0; i < c->lsave_cnt && i < *main_lebs; i++) |
797 | lsave[i] = c->main_first + i; |
798 | for (; i < c->lsave_cnt; i++) |
799 | lsave[i] = c->main_first; |
800 | |
801 | ubifs_pack_lsave(c, buf: p, lsave); |
802 | p += c->lsave_sz; |
803 | len += c->lsave_sz; |
804 | } |
805 | |
806 | /* Need to add LPT's own LEB properties table */ |
807 | if (len + c->ltab_sz > c->leb_size) { |
808 | alen = ALIGN(len, c->min_io_size); |
809 | set_ltab(c, lnum, free: c->leb_size - alen, dirty: alen - len); |
810 | memset(p, 0xff, alen - len); |
811 | err = ubifs_leb_change(c, lnum: lnum++, buf, len: alen); |
812 | if (err) |
813 | goto out; |
814 | p = buf; |
815 | len = 0; |
816 | } |
817 | |
818 | c->ltab_lnum = lnum; |
819 | c->ltab_offs = len; |
820 | |
821 | /* Update ltab before packing it */ |
822 | len += c->ltab_sz; |
823 | alen = ALIGN(len, c->min_io_size); |
824 | set_ltab(c, lnum, free: c->leb_size - alen, dirty: alen - len); |
825 | |
826 | ubifs_pack_ltab(c, buf: p, ltab); |
827 | p += c->ltab_sz; |
828 | |
829 | /* Write remaining buffer */ |
830 | memset(p, 0xff, alen - len); |
831 | err = ubifs_leb_change(c, lnum, buf, len: alen); |
832 | if (err) |
833 | goto out; |
834 | |
835 | err = ubifs_shash_final(c, desc, out: hash); |
836 | if (err) |
837 | goto out; |
838 | |
839 | c->nhead_lnum = lnum; |
840 | c->nhead_offs = ALIGN(len, c->min_io_size); |
841 | |
842 | dbg_lp("space_bits %d" , c->space_bits); |
843 | dbg_lp("lpt_lnum_bits %d" , c->lpt_lnum_bits); |
844 | dbg_lp("lpt_offs_bits %d" , c->lpt_offs_bits); |
845 | dbg_lp("lpt_spc_bits %d" , c->lpt_spc_bits); |
846 | dbg_lp("pcnt_bits %d" , c->pcnt_bits); |
847 | dbg_lp("lnum_bits %d" , c->lnum_bits); |
848 | dbg_lp("pnode_sz %d" , c->pnode_sz); |
849 | dbg_lp("nnode_sz %d" , c->nnode_sz); |
850 | dbg_lp("ltab_sz %d" , c->ltab_sz); |
851 | dbg_lp("lsave_sz %d" , c->lsave_sz); |
852 | dbg_lp("lsave_cnt %d" , c->lsave_cnt); |
853 | dbg_lp("lpt_hght %d" , c->lpt_hght); |
854 | dbg_lp("big_lpt %u" , c->big_lpt); |
855 | dbg_lp("LPT root is at %d:%d" , c->lpt_lnum, c->lpt_offs); |
856 | dbg_lp("LPT head is at %d:%d" , c->nhead_lnum, c->nhead_offs); |
857 | dbg_lp("LPT ltab is at %d:%d" , c->ltab_lnum, c->ltab_offs); |
858 | if (c->big_lpt) |
859 | dbg_lp("LPT lsave is at %d:%d" , c->lsave_lnum, c->lsave_offs); |
860 | out: |
861 | c->ltab = NULL; |
862 | kfree(objp: desc); |
863 | kfree(objp: lsave); |
864 | vfree(addr: ltab); |
865 | vfree(addr: buf); |
866 | kfree(objp: nnode); |
867 | kfree(objp: pnode); |
868 | return err; |
869 | } |
870 | |
871 | /** |
872 | * update_cats - add LEB properties of a pnode to LEB category lists and heaps. |
873 | * @c: UBIFS file-system description object |
874 | * @pnode: pnode |
875 | * |
876 | * When a pnode is loaded into memory, the LEB properties it contains are added, |
877 | * by this function, to the LEB category lists and heaps. |
878 | */ |
879 | static void update_cats(struct ubifs_info *c, struct ubifs_pnode *pnode) |
880 | { |
881 | int i; |
882 | |
883 | for (i = 0; i < UBIFS_LPT_FANOUT; i++) { |
884 | int cat = pnode->lprops[i].flags & LPROPS_CAT_MASK; |
885 | int lnum = pnode->lprops[i].lnum; |
886 | |
887 | if (!lnum) |
888 | return; |
889 | ubifs_add_to_cat(c, lprops: &pnode->lprops[i], cat); |
890 | } |
891 | } |
892 | |
893 | /** |
894 | * replace_cats - add LEB properties of a pnode to LEB category lists and heaps. |
895 | * @c: UBIFS file-system description object |
896 | * @old_pnode: pnode copied |
897 | * @new_pnode: pnode copy |
898 | * |
899 | * During commit it is sometimes necessary to copy a pnode |
900 | * (see dirty_cow_pnode). When that happens, references in |
901 | * category lists and heaps must be replaced. This function does that. |
902 | */ |
903 | static void replace_cats(struct ubifs_info *c, struct ubifs_pnode *old_pnode, |
904 | struct ubifs_pnode *new_pnode) |
905 | { |
906 | int i; |
907 | |
908 | for (i = 0; i < UBIFS_LPT_FANOUT; i++) { |
909 | if (!new_pnode->lprops[i].lnum) |
910 | return; |
911 | ubifs_replace_cat(c, old_lprops: &old_pnode->lprops[i], |
912 | new_lprops: &new_pnode->lprops[i]); |
913 | } |
914 | } |
915 | |
916 | /** |
917 | * check_lpt_crc - check LPT node crc is correct. |
918 | * @c: UBIFS file-system description object |
919 | * @buf: buffer containing node |
920 | * @len: length of node |
921 | * |
922 | * This function returns %0 on success and a negative error code on failure. |
923 | */ |
924 | static int check_lpt_crc(const struct ubifs_info *c, void *buf, int len) |
925 | { |
926 | int pos = 0; |
927 | uint8_t *addr = buf; |
928 | uint16_t crc, calc_crc; |
929 | |
930 | crc = ubifs_unpack_bits(c, addr: &addr, pos: &pos, UBIFS_LPT_CRC_BITS); |
931 | calc_crc = crc16(crc: -1, buffer: buf + UBIFS_LPT_CRC_BYTES, |
932 | len: len - UBIFS_LPT_CRC_BYTES); |
933 | if (crc != calc_crc) { |
934 | ubifs_err(c, fmt: "invalid crc in LPT node: crc %hx calc %hx" , |
935 | crc, calc_crc); |
936 | dump_stack(); |
937 | return -EINVAL; |
938 | } |
939 | return 0; |
940 | } |
941 | |
942 | /** |
943 | * check_lpt_type - check LPT node type is correct. |
944 | * @c: UBIFS file-system description object |
945 | * @addr: address of type bit field is passed and returned updated here |
946 | * @pos: position of type bit field is passed and returned updated here |
947 | * @type: expected type |
948 | * |
949 | * This function returns %0 on success and a negative error code on failure. |
950 | */ |
951 | static int check_lpt_type(const struct ubifs_info *c, uint8_t **addr, |
952 | int *pos, int type) |
953 | { |
954 | int node_type; |
955 | |
956 | node_type = ubifs_unpack_bits(c, addr, pos, UBIFS_LPT_TYPE_BITS); |
957 | if (node_type != type) { |
958 | ubifs_err(c, fmt: "invalid type (%d) in LPT node type %d" , |
959 | node_type, type); |
960 | dump_stack(); |
961 | return -EINVAL; |
962 | } |
963 | return 0; |
964 | } |
965 | |
966 | /** |
967 | * unpack_pnode - unpack a pnode. |
968 | * @c: UBIFS file-system description object |
969 | * @buf: buffer containing packed pnode to unpack |
970 | * @pnode: pnode structure to fill |
971 | * |
972 | * This function returns %0 on success and a negative error code on failure. |
973 | */ |
974 | static int unpack_pnode(const struct ubifs_info *c, void *buf, |
975 | struct ubifs_pnode *pnode) |
976 | { |
977 | uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; |
978 | int i, pos = 0, err; |
979 | |
980 | err = check_lpt_type(c, addr: &addr, pos: &pos, type: UBIFS_LPT_PNODE); |
981 | if (err) |
982 | return err; |
983 | if (c->big_lpt) |
984 | pnode->num = ubifs_unpack_bits(c, addr: &addr, pos: &pos, nrbits: c->pcnt_bits); |
985 | for (i = 0; i < UBIFS_LPT_FANOUT; i++) { |
986 | struct ubifs_lprops * const lprops = &pnode->lprops[i]; |
987 | |
988 | lprops->free = ubifs_unpack_bits(c, addr: &addr, pos: &pos, nrbits: c->space_bits); |
989 | lprops->free <<= 3; |
990 | lprops->dirty = ubifs_unpack_bits(c, addr: &addr, pos: &pos, nrbits: c->space_bits); |
991 | lprops->dirty <<= 3; |
992 | |
993 | if (ubifs_unpack_bits(c, addr: &addr, pos: &pos, nrbits: 1)) |
994 | lprops->flags = LPROPS_INDEX; |
995 | else |
996 | lprops->flags = 0; |
997 | lprops->flags |= ubifs_categorize_lprops(c, lprops); |
998 | } |
999 | err = check_lpt_crc(c, buf, len: c->pnode_sz); |
1000 | return err; |
1001 | } |
1002 | |
1003 | /** |
1004 | * ubifs_unpack_nnode - unpack a nnode. |
1005 | * @c: UBIFS file-system description object |
1006 | * @buf: buffer containing packed nnode to unpack |
1007 | * @nnode: nnode structure to fill |
1008 | * |
1009 | * This function returns %0 on success and a negative error code on failure. |
1010 | */ |
1011 | int ubifs_unpack_nnode(const struct ubifs_info *c, void *buf, |
1012 | struct ubifs_nnode *nnode) |
1013 | { |
1014 | uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; |
1015 | int i, pos = 0, err; |
1016 | |
1017 | err = check_lpt_type(c, addr: &addr, pos: &pos, type: UBIFS_LPT_NNODE); |
1018 | if (err) |
1019 | return err; |
1020 | if (c->big_lpt) |
1021 | nnode->num = ubifs_unpack_bits(c, addr: &addr, pos: &pos, nrbits: c->pcnt_bits); |
1022 | for (i = 0; i < UBIFS_LPT_FANOUT; i++) { |
1023 | int lnum; |
1024 | |
1025 | lnum = ubifs_unpack_bits(c, addr: &addr, pos: &pos, nrbits: c->lpt_lnum_bits) + |
1026 | c->lpt_first; |
1027 | if (lnum == c->lpt_last + 1) |
1028 | lnum = 0; |
1029 | nnode->nbranch[i].lnum = lnum; |
1030 | nnode->nbranch[i].offs = ubifs_unpack_bits(c, addr: &addr, pos: &pos, |
1031 | nrbits: c->lpt_offs_bits); |
1032 | } |
1033 | err = check_lpt_crc(c, buf, len: c->nnode_sz); |
1034 | return err; |
1035 | } |
1036 | |
1037 | /** |
1038 | * unpack_ltab - unpack the LPT's own lprops table. |
1039 | * @c: UBIFS file-system description object |
1040 | * @buf: buffer from which to unpack |
1041 | * |
1042 | * This function returns %0 on success and a negative error code on failure. |
1043 | */ |
1044 | static int unpack_ltab(const struct ubifs_info *c, void *buf) |
1045 | { |
1046 | uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; |
1047 | int i, pos = 0, err; |
1048 | |
1049 | err = check_lpt_type(c, addr: &addr, pos: &pos, type: UBIFS_LPT_LTAB); |
1050 | if (err) |
1051 | return err; |
1052 | for (i = 0; i < c->lpt_lebs; i++) { |
1053 | int free = ubifs_unpack_bits(c, addr: &addr, pos: &pos, nrbits: c->lpt_spc_bits); |
1054 | int dirty = ubifs_unpack_bits(c, addr: &addr, pos: &pos, nrbits: c->lpt_spc_bits); |
1055 | |
1056 | if (free < 0 || free > c->leb_size || dirty < 0 || |
1057 | dirty > c->leb_size || free + dirty > c->leb_size) |
1058 | return -EINVAL; |
1059 | |
1060 | c->ltab[i].free = free; |
1061 | c->ltab[i].dirty = dirty; |
1062 | c->ltab[i].tgc = 0; |
1063 | c->ltab[i].cmt = 0; |
1064 | } |
1065 | err = check_lpt_crc(c, buf, len: c->ltab_sz); |
1066 | return err; |
1067 | } |
1068 | |
1069 | /** |
1070 | * unpack_lsave - unpack the LPT's save table. |
1071 | * @c: UBIFS file-system description object |
1072 | * @buf: buffer from which to unpack |
1073 | * |
1074 | * This function returns %0 on success and a negative error code on failure. |
1075 | */ |
1076 | static int unpack_lsave(const struct ubifs_info *c, void *buf) |
1077 | { |
1078 | uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; |
1079 | int i, pos = 0, err; |
1080 | |
1081 | err = check_lpt_type(c, addr: &addr, pos: &pos, type: UBIFS_LPT_LSAVE); |
1082 | if (err) |
1083 | return err; |
1084 | for (i = 0; i < c->lsave_cnt; i++) { |
1085 | int lnum = ubifs_unpack_bits(c, addr: &addr, pos: &pos, nrbits: c->lnum_bits); |
1086 | |
1087 | if (lnum < c->main_first || lnum >= c->leb_cnt) |
1088 | return -EINVAL; |
1089 | c->lsave[i] = lnum; |
1090 | } |
1091 | err = check_lpt_crc(c, buf, len: c->lsave_sz); |
1092 | return err; |
1093 | } |
1094 | |
1095 | /** |
1096 | * validate_nnode - validate a nnode. |
1097 | * @c: UBIFS file-system description object |
1098 | * @nnode: nnode to validate |
1099 | * @parent: parent nnode (or NULL for the root nnode) |
1100 | * @iip: index in parent |
1101 | * |
1102 | * This function returns %0 on success and a negative error code on failure. |
1103 | */ |
1104 | static int validate_nnode(const struct ubifs_info *c, struct ubifs_nnode *nnode, |
1105 | struct ubifs_nnode *parent, int iip) |
1106 | { |
1107 | int i, lvl, max_offs; |
1108 | |
1109 | if (c->big_lpt) { |
1110 | int num = calc_nnode_num_from_parent(c, parent, iip); |
1111 | |
1112 | if (nnode->num != num) |
1113 | return -EINVAL; |
1114 | } |
1115 | lvl = parent ? parent->level - 1 : c->lpt_hght; |
1116 | if (lvl < 1) |
1117 | return -EINVAL; |
1118 | if (lvl == 1) |
1119 | max_offs = c->leb_size - c->pnode_sz; |
1120 | else |
1121 | max_offs = c->leb_size - c->nnode_sz; |
1122 | for (i = 0; i < UBIFS_LPT_FANOUT; i++) { |
1123 | int lnum = nnode->nbranch[i].lnum; |
1124 | int offs = nnode->nbranch[i].offs; |
1125 | |
1126 | if (lnum == 0) { |
1127 | if (offs != 0) |
1128 | return -EINVAL; |
1129 | continue; |
1130 | } |
1131 | if (lnum < c->lpt_first || lnum > c->lpt_last) |
1132 | return -EINVAL; |
1133 | if (offs < 0 || offs > max_offs) |
1134 | return -EINVAL; |
1135 | } |
1136 | return 0; |
1137 | } |
1138 | |
1139 | /** |
1140 | * validate_pnode - validate a pnode. |
1141 | * @c: UBIFS file-system description object |
1142 | * @pnode: pnode to validate |
1143 | * @parent: parent nnode |
1144 | * @iip: index in parent |
1145 | * |
1146 | * This function returns %0 on success and a negative error code on failure. |
1147 | */ |
1148 | static int validate_pnode(const struct ubifs_info *c, struct ubifs_pnode *pnode, |
1149 | struct ubifs_nnode *parent, int iip) |
1150 | { |
1151 | int i; |
1152 | |
1153 | if (c->big_lpt) { |
1154 | int num = calc_pnode_num_from_parent(c, parent, iip); |
1155 | |
1156 | if (pnode->num != num) |
1157 | return -EINVAL; |
1158 | } |
1159 | for (i = 0; i < UBIFS_LPT_FANOUT; i++) { |
1160 | int free = pnode->lprops[i].free; |
1161 | int dirty = pnode->lprops[i].dirty; |
1162 | |
1163 | if (free < 0 || free > c->leb_size || free % c->min_io_size || |
1164 | (free & 7)) |
1165 | return -EINVAL; |
1166 | if (dirty < 0 || dirty > c->leb_size || (dirty & 7)) |
1167 | return -EINVAL; |
1168 | if (dirty + free > c->leb_size) |
1169 | return -EINVAL; |
1170 | } |
1171 | return 0; |
1172 | } |
1173 | |
1174 | /** |
1175 | * set_pnode_lnum - set LEB numbers on a pnode. |
1176 | * @c: UBIFS file-system description object |
1177 | * @pnode: pnode to update |
1178 | * |
1179 | * This function calculates the LEB numbers for the LEB properties it contains |
1180 | * based on the pnode number. |
1181 | */ |
1182 | static void set_pnode_lnum(const struct ubifs_info *c, |
1183 | struct ubifs_pnode *pnode) |
1184 | { |
1185 | int i, lnum; |
1186 | |
1187 | lnum = (pnode->num << UBIFS_LPT_FANOUT_SHIFT) + c->main_first; |
1188 | for (i = 0; i < UBIFS_LPT_FANOUT; i++) { |
1189 | if (lnum >= c->leb_cnt) |
1190 | return; |
1191 | pnode->lprops[i].lnum = lnum++; |
1192 | } |
1193 | } |
1194 | |
1195 | /** |
1196 | * ubifs_read_nnode - read a nnode from flash and link it to the tree in memory. |
1197 | * @c: UBIFS file-system description object |
1198 | * @parent: parent nnode (or NULL for the root) |
1199 | * @iip: index in parent |
1200 | * |
1201 | * This function returns %0 on success and a negative error code on failure. |
1202 | */ |
1203 | int ubifs_read_nnode(struct ubifs_info *c, struct ubifs_nnode *parent, int iip) |
1204 | { |
1205 | struct ubifs_nbranch *branch = NULL; |
1206 | struct ubifs_nnode *nnode = NULL; |
1207 | void *buf = c->lpt_nod_buf; |
1208 | int err, lnum, offs; |
1209 | |
1210 | if (parent) { |
1211 | branch = &parent->nbranch[iip]; |
1212 | lnum = branch->lnum; |
1213 | offs = branch->offs; |
1214 | } else { |
1215 | lnum = c->lpt_lnum; |
1216 | offs = c->lpt_offs; |
1217 | } |
1218 | nnode = kzalloc(size: sizeof(struct ubifs_nnode), GFP_NOFS); |
1219 | if (!nnode) { |
1220 | err = -ENOMEM; |
1221 | goto out; |
1222 | } |
1223 | if (lnum == 0) { |
1224 | /* |
1225 | * This nnode was not written which just means that the LEB |
1226 | * properties in the subtree below it describe empty LEBs. We |
1227 | * make the nnode as though we had read it, which in fact means |
1228 | * doing almost nothing. |
1229 | */ |
1230 | if (c->big_lpt) |
1231 | nnode->num = calc_nnode_num_from_parent(c, parent, iip); |
1232 | } else { |
1233 | err = ubifs_leb_read(c, lnum, buf, offs, len: c->nnode_sz, even_ebadmsg: 1); |
1234 | if (err) |
1235 | goto out; |
1236 | err = ubifs_unpack_nnode(c, buf, nnode); |
1237 | if (err) |
1238 | goto out; |
1239 | } |
1240 | err = validate_nnode(c, nnode, parent, iip); |
1241 | if (err) |
1242 | goto out; |
1243 | if (!c->big_lpt) |
1244 | nnode->num = calc_nnode_num_from_parent(c, parent, iip); |
1245 | if (parent) { |
1246 | branch->nnode = nnode; |
1247 | nnode->level = parent->level - 1; |
1248 | } else { |
1249 | c->nroot = nnode; |
1250 | nnode->level = c->lpt_hght; |
1251 | } |
1252 | nnode->parent = parent; |
1253 | nnode->iip = iip; |
1254 | return 0; |
1255 | |
1256 | out: |
1257 | ubifs_err(c, fmt: "error %d reading nnode at %d:%d" , err, lnum, offs); |
1258 | dump_stack(); |
1259 | kfree(objp: nnode); |
1260 | return err; |
1261 | } |
1262 | |
1263 | /** |
1264 | * read_pnode - read a pnode from flash and link it to the tree in memory. |
1265 | * @c: UBIFS file-system description object |
1266 | * @parent: parent nnode |
1267 | * @iip: index in parent |
1268 | * |
1269 | * This function returns %0 on success and a negative error code on failure. |
1270 | */ |
1271 | static int read_pnode(struct ubifs_info *c, struct ubifs_nnode *parent, int iip) |
1272 | { |
1273 | struct ubifs_nbranch *branch; |
1274 | struct ubifs_pnode *pnode = NULL; |
1275 | void *buf = c->lpt_nod_buf; |
1276 | int err, lnum, offs; |
1277 | |
1278 | branch = &parent->nbranch[iip]; |
1279 | lnum = branch->lnum; |
1280 | offs = branch->offs; |
1281 | pnode = kzalloc(size: sizeof(struct ubifs_pnode), GFP_NOFS); |
1282 | if (!pnode) |
1283 | return -ENOMEM; |
1284 | |
1285 | if (lnum == 0) { |
1286 | /* |
1287 | * This pnode was not written which just means that the LEB |
1288 | * properties in it describe empty LEBs. We make the pnode as |
1289 | * though we had read it. |
1290 | */ |
1291 | int i; |
1292 | |
1293 | if (c->big_lpt) |
1294 | pnode->num = calc_pnode_num_from_parent(c, parent, iip); |
1295 | for (i = 0; i < UBIFS_LPT_FANOUT; i++) { |
1296 | struct ubifs_lprops * const lprops = &pnode->lprops[i]; |
1297 | |
1298 | lprops->free = c->leb_size; |
1299 | lprops->flags = ubifs_categorize_lprops(c, lprops); |
1300 | } |
1301 | } else { |
1302 | err = ubifs_leb_read(c, lnum, buf, offs, len: c->pnode_sz, even_ebadmsg: 1); |
1303 | if (err) |
1304 | goto out; |
1305 | err = unpack_pnode(c, buf, pnode); |
1306 | if (err) |
1307 | goto out; |
1308 | } |
1309 | err = validate_pnode(c, pnode, parent, iip); |
1310 | if (err) |
1311 | goto out; |
1312 | if (!c->big_lpt) |
1313 | pnode->num = calc_pnode_num_from_parent(c, parent, iip); |
1314 | branch->pnode = pnode; |
1315 | pnode->parent = parent; |
1316 | pnode->iip = iip; |
1317 | set_pnode_lnum(c, pnode); |
1318 | c->pnodes_have += 1; |
1319 | return 0; |
1320 | |
1321 | out: |
1322 | ubifs_err(c, fmt: "error %d reading pnode at %d:%d" , err, lnum, offs); |
1323 | ubifs_dump_pnode(c, pnode, parent, iip); |
1324 | dump_stack(); |
1325 | ubifs_err(c, fmt: "calc num: %d" , calc_pnode_num_from_parent(c, parent, iip)); |
1326 | kfree(objp: pnode); |
1327 | return err; |
1328 | } |
1329 | |
1330 | /** |
1331 | * read_ltab - read LPT's own lprops table. |
1332 | * @c: UBIFS file-system description object |
1333 | * |
1334 | * This function returns %0 on success and a negative error code on failure. |
1335 | */ |
1336 | static int read_ltab(struct ubifs_info *c) |
1337 | { |
1338 | int err; |
1339 | void *buf; |
1340 | |
1341 | buf = vmalloc(size: c->ltab_sz); |
1342 | if (!buf) |
1343 | return -ENOMEM; |
1344 | err = ubifs_leb_read(c, lnum: c->ltab_lnum, buf, offs: c->ltab_offs, len: c->ltab_sz, even_ebadmsg: 1); |
1345 | if (err) |
1346 | goto out; |
1347 | err = unpack_ltab(c, buf); |
1348 | out: |
1349 | vfree(addr: buf); |
1350 | return err; |
1351 | } |
1352 | |
1353 | /** |
1354 | * read_lsave - read LPT's save table. |
1355 | * @c: UBIFS file-system description object |
1356 | * |
1357 | * This function returns %0 on success and a negative error code on failure. |
1358 | */ |
1359 | static int read_lsave(struct ubifs_info *c) |
1360 | { |
1361 | int err, i; |
1362 | void *buf; |
1363 | |
1364 | buf = vmalloc(size: c->lsave_sz); |
1365 | if (!buf) |
1366 | return -ENOMEM; |
1367 | err = ubifs_leb_read(c, lnum: c->lsave_lnum, buf, offs: c->lsave_offs, |
1368 | len: c->lsave_sz, even_ebadmsg: 1); |
1369 | if (err) |
1370 | goto out; |
1371 | err = unpack_lsave(c, buf); |
1372 | if (err) |
1373 | goto out; |
1374 | for (i = 0; i < c->lsave_cnt; i++) { |
1375 | int lnum = c->lsave[i]; |
1376 | struct ubifs_lprops *lprops; |
1377 | |
1378 | /* |
1379 | * Due to automatic resizing, the values in the lsave table |
1380 | * could be beyond the volume size - just ignore them. |
1381 | */ |
1382 | if (lnum >= c->leb_cnt) |
1383 | continue; |
1384 | lprops = ubifs_lpt_lookup(c, lnum); |
1385 | if (IS_ERR(ptr: lprops)) { |
1386 | err = PTR_ERR(ptr: lprops); |
1387 | goto out; |
1388 | } |
1389 | } |
1390 | out: |
1391 | vfree(addr: buf); |
1392 | return err; |
1393 | } |
1394 | |
1395 | /** |
1396 | * ubifs_get_nnode - get a nnode. |
1397 | * @c: UBIFS file-system description object |
1398 | * @parent: parent nnode (or NULL for the root) |
1399 | * @iip: index in parent |
1400 | * |
1401 | * This function returns a pointer to the nnode on success or a negative error |
1402 | * code on failure. |
1403 | */ |
1404 | struct ubifs_nnode *ubifs_get_nnode(struct ubifs_info *c, |
1405 | struct ubifs_nnode *parent, int iip) |
1406 | { |
1407 | struct ubifs_nbranch *branch; |
1408 | struct ubifs_nnode *nnode; |
1409 | int err; |
1410 | |
1411 | branch = &parent->nbranch[iip]; |
1412 | nnode = branch->nnode; |
1413 | if (nnode) |
1414 | return nnode; |
1415 | err = ubifs_read_nnode(c, parent, iip); |
1416 | if (err) |
1417 | return ERR_PTR(error: err); |
1418 | return branch->nnode; |
1419 | } |
1420 | |
1421 | /** |
1422 | * ubifs_get_pnode - get a pnode. |
1423 | * @c: UBIFS file-system description object |
1424 | * @parent: parent nnode |
1425 | * @iip: index in parent |
1426 | * |
1427 | * This function returns a pointer to the pnode on success or a negative error |
1428 | * code on failure. |
1429 | */ |
1430 | struct ubifs_pnode *ubifs_get_pnode(struct ubifs_info *c, |
1431 | struct ubifs_nnode *parent, int iip) |
1432 | { |
1433 | struct ubifs_nbranch *branch; |
1434 | struct ubifs_pnode *pnode; |
1435 | int err; |
1436 | |
1437 | branch = &parent->nbranch[iip]; |
1438 | pnode = branch->pnode; |
1439 | if (pnode) |
1440 | return pnode; |
1441 | err = read_pnode(c, parent, iip); |
1442 | if (err) |
1443 | return ERR_PTR(error: err); |
1444 | update_cats(c, pnode: branch->pnode); |
1445 | return branch->pnode; |
1446 | } |
1447 | |
1448 | /** |
1449 | * ubifs_pnode_lookup - lookup a pnode in the LPT. |
1450 | * @c: UBIFS file-system description object |
1451 | * @i: pnode number (0 to (main_lebs - 1) / UBIFS_LPT_FANOUT) |
1452 | * |
1453 | * This function returns a pointer to the pnode on success or a negative |
1454 | * error code on failure. |
1455 | */ |
1456 | struct ubifs_pnode *ubifs_pnode_lookup(struct ubifs_info *c, int i) |
1457 | { |
1458 | int err, h, iip, shft; |
1459 | struct ubifs_nnode *nnode; |
1460 | |
1461 | if (!c->nroot) { |
1462 | err = ubifs_read_nnode(c, NULL, iip: 0); |
1463 | if (err) |
1464 | return ERR_PTR(error: err); |
1465 | } |
1466 | i <<= UBIFS_LPT_FANOUT_SHIFT; |
1467 | nnode = c->nroot; |
1468 | shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT; |
1469 | for (h = 1; h < c->lpt_hght; h++) { |
1470 | iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1)); |
1471 | shft -= UBIFS_LPT_FANOUT_SHIFT; |
1472 | nnode = ubifs_get_nnode(c, parent: nnode, iip); |
1473 | if (IS_ERR(ptr: nnode)) |
1474 | return ERR_CAST(ptr: nnode); |
1475 | } |
1476 | iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1)); |
1477 | return ubifs_get_pnode(c, parent: nnode, iip); |
1478 | } |
1479 | |
1480 | /** |
1481 | * ubifs_lpt_lookup - lookup LEB properties in the LPT. |
1482 | * @c: UBIFS file-system description object |
1483 | * @lnum: LEB number to lookup |
1484 | * |
1485 | * This function returns a pointer to the LEB properties on success or a |
1486 | * negative error code on failure. |
1487 | */ |
1488 | struct ubifs_lprops *ubifs_lpt_lookup(struct ubifs_info *c, int lnum) |
1489 | { |
1490 | int i, iip; |
1491 | struct ubifs_pnode *pnode; |
1492 | |
1493 | i = lnum - c->main_first; |
1494 | pnode = ubifs_pnode_lookup(c, i: i >> UBIFS_LPT_FANOUT_SHIFT); |
1495 | if (IS_ERR(ptr: pnode)) |
1496 | return ERR_CAST(ptr: pnode); |
1497 | iip = (i & (UBIFS_LPT_FANOUT - 1)); |
1498 | dbg_lp("LEB %d, free %d, dirty %d, flags %d" , lnum, |
1499 | pnode->lprops[iip].free, pnode->lprops[iip].dirty, |
1500 | pnode->lprops[iip].flags); |
1501 | return &pnode->lprops[iip]; |
1502 | } |
1503 | |
1504 | /** |
1505 | * dirty_cow_nnode - ensure a nnode is not being committed. |
1506 | * @c: UBIFS file-system description object |
1507 | * @nnode: nnode to check |
1508 | * |
1509 | * Returns dirtied nnode on success or negative error code on failure. |
1510 | */ |
1511 | static struct ubifs_nnode *dirty_cow_nnode(struct ubifs_info *c, |
1512 | struct ubifs_nnode *nnode) |
1513 | { |
1514 | struct ubifs_nnode *n; |
1515 | int i; |
1516 | |
1517 | if (!test_bit(COW_CNODE, &nnode->flags)) { |
1518 | /* nnode is not being committed */ |
1519 | if (!test_and_set_bit(nr: DIRTY_CNODE, addr: &nnode->flags)) { |
1520 | c->dirty_nn_cnt += 1; |
1521 | ubifs_add_nnode_dirt(c, nnode); |
1522 | } |
1523 | return nnode; |
1524 | } |
1525 | |
1526 | /* nnode is being committed, so copy it */ |
1527 | n = kmemdup(p: nnode, size: sizeof(struct ubifs_nnode), GFP_NOFS); |
1528 | if (unlikely(!n)) |
1529 | return ERR_PTR(error: -ENOMEM); |
1530 | |
1531 | n->cnext = NULL; |
1532 | __set_bit(DIRTY_CNODE, &n->flags); |
1533 | __clear_bit(COW_CNODE, &n->flags); |
1534 | |
1535 | /* The children now have new parent */ |
1536 | for (i = 0; i < UBIFS_LPT_FANOUT; i++) { |
1537 | struct ubifs_nbranch *branch = &n->nbranch[i]; |
1538 | |
1539 | if (branch->cnode) |
1540 | branch->cnode->parent = n; |
1541 | } |
1542 | |
1543 | ubifs_assert(c, !test_bit(OBSOLETE_CNODE, &nnode->flags)); |
1544 | __set_bit(OBSOLETE_CNODE, &nnode->flags); |
1545 | |
1546 | c->dirty_nn_cnt += 1; |
1547 | ubifs_add_nnode_dirt(c, nnode); |
1548 | if (nnode->parent) |
1549 | nnode->parent->nbranch[n->iip].nnode = n; |
1550 | else |
1551 | c->nroot = n; |
1552 | return n; |
1553 | } |
1554 | |
1555 | /** |
1556 | * dirty_cow_pnode - ensure a pnode is not being committed. |
1557 | * @c: UBIFS file-system description object |
1558 | * @pnode: pnode to check |
1559 | * |
1560 | * Returns dirtied pnode on success or negative error code on failure. |
1561 | */ |
1562 | static struct ubifs_pnode *dirty_cow_pnode(struct ubifs_info *c, |
1563 | struct ubifs_pnode *pnode) |
1564 | { |
1565 | struct ubifs_pnode *p; |
1566 | |
1567 | if (!test_bit(COW_CNODE, &pnode->flags)) { |
1568 | /* pnode is not being committed */ |
1569 | if (!test_and_set_bit(nr: DIRTY_CNODE, addr: &pnode->flags)) { |
1570 | c->dirty_pn_cnt += 1; |
1571 | add_pnode_dirt(c, pnode); |
1572 | } |
1573 | return pnode; |
1574 | } |
1575 | |
1576 | /* pnode is being committed, so copy it */ |
1577 | p = kmemdup(p: pnode, size: sizeof(struct ubifs_pnode), GFP_NOFS); |
1578 | if (unlikely(!p)) |
1579 | return ERR_PTR(error: -ENOMEM); |
1580 | |
1581 | p->cnext = NULL; |
1582 | __set_bit(DIRTY_CNODE, &p->flags); |
1583 | __clear_bit(COW_CNODE, &p->flags); |
1584 | replace_cats(c, old_pnode: pnode, new_pnode: p); |
1585 | |
1586 | ubifs_assert(c, !test_bit(OBSOLETE_CNODE, &pnode->flags)); |
1587 | __set_bit(OBSOLETE_CNODE, &pnode->flags); |
1588 | |
1589 | c->dirty_pn_cnt += 1; |
1590 | add_pnode_dirt(c, pnode); |
1591 | pnode->parent->nbranch[p->iip].pnode = p; |
1592 | return p; |
1593 | } |
1594 | |
1595 | /** |
1596 | * ubifs_lpt_lookup_dirty - lookup LEB properties in the LPT. |
1597 | * @c: UBIFS file-system description object |
1598 | * @lnum: LEB number to lookup |
1599 | * |
1600 | * This function returns a pointer to the LEB properties on success or a |
1601 | * negative error code on failure. |
1602 | */ |
1603 | struct ubifs_lprops *ubifs_lpt_lookup_dirty(struct ubifs_info *c, int lnum) |
1604 | { |
1605 | int err, i, h, iip, shft; |
1606 | struct ubifs_nnode *nnode; |
1607 | struct ubifs_pnode *pnode; |
1608 | |
1609 | if (!c->nroot) { |
1610 | err = ubifs_read_nnode(c, NULL, iip: 0); |
1611 | if (err) |
1612 | return ERR_PTR(error: err); |
1613 | } |
1614 | nnode = c->nroot; |
1615 | nnode = dirty_cow_nnode(c, nnode); |
1616 | if (IS_ERR(ptr: nnode)) |
1617 | return ERR_CAST(ptr: nnode); |
1618 | i = lnum - c->main_first; |
1619 | shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT; |
1620 | for (h = 1; h < c->lpt_hght; h++) { |
1621 | iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1)); |
1622 | shft -= UBIFS_LPT_FANOUT_SHIFT; |
1623 | nnode = ubifs_get_nnode(c, parent: nnode, iip); |
1624 | if (IS_ERR(ptr: nnode)) |
1625 | return ERR_CAST(ptr: nnode); |
1626 | nnode = dirty_cow_nnode(c, nnode); |
1627 | if (IS_ERR(ptr: nnode)) |
1628 | return ERR_CAST(ptr: nnode); |
1629 | } |
1630 | iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1)); |
1631 | pnode = ubifs_get_pnode(c, parent: nnode, iip); |
1632 | if (IS_ERR(ptr: pnode)) |
1633 | return ERR_CAST(ptr: pnode); |
1634 | pnode = dirty_cow_pnode(c, pnode); |
1635 | if (IS_ERR(ptr: pnode)) |
1636 | return ERR_CAST(ptr: pnode); |
1637 | iip = (i & (UBIFS_LPT_FANOUT - 1)); |
1638 | dbg_lp("LEB %d, free %d, dirty %d, flags %d" , lnum, |
1639 | pnode->lprops[iip].free, pnode->lprops[iip].dirty, |
1640 | pnode->lprops[iip].flags); |
1641 | ubifs_assert(c, test_bit(DIRTY_CNODE, &pnode->flags)); |
1642 | return &pnode->lprops[iip]; |
1643 | } |
1644 | |
1645 | /** |
1646 | * ubifs_lpt_calc_hash - Calculate hash of the LPT pnodes |
1647 | * @c: UBIFS file-system description object |
1648 | * @hash: the returned hash of the LPT pnodes |
1649 | * |
1650 | * This function iterates over the LPT pnodes and creates a hash over them. |
1651 | * Returns 0 for success or a negative error code otherwise. |
1652 | */ |
1653 | int ubifs_lpt_calc_hash(struct ubifs_info *c, u8 *hash) |
1654 | { |
1655 | struct ubifs_nnode *nnode, *nn; |
1656 | struct ubifs_cnode *cnode; |
1657 | struct shash_desc *desc; |
1658 | int iip = 0, i; |
1659 | int bufsiz = max_t(int, c->nnode_sz, c->pnode_sz); |
1660 | void *buf; |
1661 | int err; |
1662 | |
1663 | if (!ubifs_authenticated(c)) |
1664 | return 0; |
1665 | |
1666 | if (!c->nroot) { |
1667 | err = ubifs_read_nnode(c, NULL, iip: 0); |
1668 | if (err) |
1669 | return err; |
1670 | } |
1671 | |
1672 | desc = ubifs_hash_get_desc(c); |
1673 | if (IS_ERR(ptr: desc)) |
1674 | return PTR_ERR(ptr: desc); |
1675 | |
1676 | buf = kmalloc(size: bufsiz, GFP_NOFS); |
1677 | if (!buf) { |
1678 | err = -ENOMEM; |
1679 | goto out; |
1680 | } |
1681 | |
1682 | cnode = (struct ubifs_cnode *)c->nroot; |
1683 | |
1684 | while (cnode) { |
1685 | nnode = cnode->parent; |
1686 | nn = (struct ubifs_nnode *)cnode; |
1687 | if (cnode->level > 1) { |
1688 | while (iip < UBIFS_LPT_FANOUT) { |
1689 | if (nn->nbranch[iip].lnum == 0) { |
1690 | /* Go right */ |
1691 | iip++; |
1692 | continue; |
1693 | } |
1694 | |
1695 | nnode = ubifs_get_nnode(c, parent: nn, iip); |
1696 | if (IS_ERR(ptr: nnode)) { |
1697 | err = PTR_ERR(ptr: nnode); |
1698 | goto out; |
1699 | } |
1700 | |
1701 | /* Go down */ |
1702 | iip = 0; |
1703 | cnode = (struct ubifs_cnode *)nnode; |
1704 | break; |
1705 | } |
1706 | if (iip < UBIFS_LPT_FANOUT) |
1707 | continue; |
1708 | } else { |
1709 | struct ubifs_pnode *pnode; |
1710 | |
1711 | for (i = 0; i < UBIFS_LPT_FANOUT; i++) { |
1712 | if (nn->nbranch[i].lnum == 0) |
1713 | continue; |
1714 | pnode = ubifs_get_pnode(c, parent: nn, iip: i); |
1715 | if (IS_ERR(ptr: pnode)) { |
1716 | err = PTR_ERR(ptr: pnode); |
1717 | goto out; |
1718 | } |
1719 | |
1720 | ubifs_pack_pnode(c, buf, pnode); |
1721 | err = ubifs_shash_update(c, desc, buf, |
1722 | len: c->pnode_sz); |
1723 | if (err) |
1724 | goto out; |
1725 | } |
1726 | } |
1727 | /* Go up and to the right */ |
1728 | iip = cnode->iip + 1; |
1729 | cnode = (struct ubifs_cnode *)nnode; |
1730 | } |
1731 | |
1732 | err = ubifs_shash_final(c, desc, out: hash); |
1733 | out: |
1734 | kfree(objp: desc); |
1735 | kfree(objp: buf); |
1736 | |
1737 | return err; |
1738 | } |
1739 | |
1740 | /** |
1741 | * lpt_check_hash - check the hash of the LPT. |
1742 | * @c: UBIFS file-system description object |
1743 | * |
1744 | * This function calculates a hash over all pnodes in the LPT and compares it with |
1745 | * the hash stored in the master node. Returns %0 on success and a negative error |
1746 | * code on failure. |
1747 | */ |
1748 | static int lpt_check_hash(struct ubifs_info *c) |
1749 | { |
1750 | int err; |
1751 | u8 hash[UBIFS_HASH_ARR_SZ]; |
1752 | |
1753 | if (!ubifs_authenticated(c)) |
1754 | return 0; |
1755 | |
1756 | err = ubifs_lpt_calc_hash(c, hash); |
1757 | if (err) |
1758 | return err; |
1759 | |
1760 | if (ubifs_check_hash(c, expected: c->mst_node->hash_lpt, got: hash)) { |
1761 | err = -EPERM; |
1762 | ubifs_err(c, fmt: "Failed to authenticate LPT" ); |
1763 | } else { |
1764 | err = 0; |
1765 | } |
1766 | |
1767 | return err; |
1768 | } |
1769 | |
1770 | /** |
1771 | * lpt_init_rd - initialize the LPT for reading. |
1772 | * @c: UBIFS file-system description object |
1773 | * |
1774 | * This function returns %0 on success and a negative error code on failure. |
1775 | */ |
1776 | static int lpt_init_rd(struct ubifs_info *c) |
1777 | { |
1778 | int err, i; |
1779 | |
1780 | c->ltab = vmalloc(array_size(sizeof(struct ubifs_lpt_lprops), |
1781 | c->lpt_lebs)); |
1782 | if (!c->ltab) |
1783 | return -ENOMEM; |
1784 | |
1785 | i = max_t(int, c->nnode_sz, c->pnode_sz); |
1786 | c->lpt_nod_buf = kmalloc(size: i, GFP_KERNEL); |
1787 | if (!c->lpt_nod_buf) |
1788 | return -ENOMEM; |
1789 | |
1790 | for (i = 0; i < LPROPS_HEAP_CNT; i++) { |
1791 | c->lpt_heap[i].arr = kmalloc_array(LPT_HEAP_SZ, |
1792 | size: sizeof(void *), |
1793 | GFP_KERNEL); |
1794 | if (!c->lpt_heap[i].arr) |
1795 | return -ENOMEM; |
1796 | c->lpt_heap[i].cnt = 0; |
1797 | c->lpt_heap[i].max_cnt = LPT_HEAP_SZ; |
1798 | } |
1799 | |
1800 | c->dirty_idx.arr = kmalloc_array(LPT_HEAP_SZ, size: sizeof(void *), |
1801 | GFP_KERNEL); |
1802 | if (!c->dirty_idx.arr) |
1803 | return -ENOMEM; |
1804 | c->dirty_idx.cnt = 0; |
1805 | c->dirty_idx.max_cnt = LPT_HEAP_SZ; |
1806 | |
1807 | err = read_ltab(c); |
1808 | if (err) |
1809 | return err; |
1810 | |
1811 | err = lpt_check_hash(c); |
1812 | if (err) |
1813 | return err; |
1814 | |
1815 | dbg_lp("space_bits %d" , c->space_bits); |
1816 | dbg_lp("lpt_lnum_bits %d" , c->lpt_lnum_bits); |
1817 | dbg_lp("lpt_offs_bits %d" , c->lpt_offs_bits); |
1818 | dbg_lp("lpt_spc_bits %d" , c->lpt_spc_bits); |
1819 | dbg_lp("pcnt_bits %d" , c->pcnt_bits); |
1820 | dbg_lp("lnum_bits %d" , c->lnum_bits); |
1821 | dbg_lp("pnode_sz %d" , c->pnode_sz); |
1822 | dbg_lp("nnode_sz %d" , c->nnode_sz); |
1823 | dbg_lp("ltab_sz %d" , c->ltab_sz); |
1824 | dbg_lp("lsave_sz %d" , c->lsave_sz); |
1825 | dbg_lp("lsave_cnt %d" , c->lsave_cnt); |
1826 | dbg_lp("lpt_hght %d" , c->lpt_hght); |
1827 | dbg_lp("big_lpt %u" , c->big_lpt); |
1828 | dbg_lp("LPT root is at %d:%d" , c->lpt_lnum, c->lpt_offs); |
1829 | dbg_lp("LPT head is at %d:%d" , c->nhead_lnum, c->nhead_offs); |
1830 | dbg_lp("LPT ltab is at %d:%d" , c->ltab_lnum, c->ltab_offs); |
1831 | if (c->big_lpt) |
1832 | dbg_lp("LPT lsave is at %d:%d" , c->lsave_lnum, c->lsave_offs); |
1833 | |
1834 | return 0; |
1835 | } |
1836 | |
1837 | /** |
1838 | * lpt_init_wr - initialize the LPT for writing. |
1839 | * @c: UBIFS file-system description object |
1840 | * |
1841 | * 'lpt_init_rd()' must have been called already. |
1842 | * |
1843 | * This function returns %0 on success and a negative error code on failure. |
1844 | */ |
1845 | static int lpt_init_wr(struct ubifs_info *c) |
1846 | { |
1847 | int err, i; |
1848 | |
1849 | c->ltab_cmt = vmalloc(array_size(sizeof(struct ubifs_lpt_lprops), |
1850 | c->lpt_lebs)); |
1851 | if (!c->ltab_cmt) |
1852 | return -ENOMEM; |
1853 | |
1854 | c->lpt_buf = vmalloc(size: c->leb_size); |
1855 | if (!c->lpt_buf) |
1856 | return -ENOMEM; |
1857 | |
1858 | if (c->big_lpt) { |
1859 | c->lsave = kmalloc_array(n: c->lsave_cnt, size: sizeof(int), GFP_NOFS); |
1860 | if (!c->lsave) |
1861 | return -ENOMEM; |
1862 | err = read_lsave(c); |
1863 | if (err) |
1864 | return err; |
1865 | } |
1866 | |
1867 | for (i = 0; i < c->lpt_lebs; i++) |
1868 | if (c->ltab[i].free == c->leb_size) { |
1869 | err = ubifs_leb_unmap(c, lnum: i + c->lpt_first); |
1870 | if (err) |
1871 | return err; |
1872 | } |
1873 | |
1874 | return 0; |
1875 | } |
1876 | |
1877 | /** |
1878 | * ubifs_lpt_init - initialize the LPT. |
1879 | * @c: UBIFS file-system description object |
1880 | * @rd: whether to initialize lpt for reading |
1881 | * @wr: whether to initialize lpt for writing |
1882 | * |
1883 | * For mounting 'rw', @rd and @wr are both true. For mounting 'ro', @rd is true |
1884 | * and @wr is false. For mounting from 'ro' to 'rw', @rd is false and @wr is |
1885 | * true. |
1886 | * |
1887 | * This function returns %0 on success and a negative error code on failure. |
1888 | */ |
1889 | int ubifs_lpt_init(struct ubifs_info *c, int rd, int wr) |
1890 | { |
1891 | int err; |
1892 | |
1893 | if (rd) { |
1894 | err = lpt_init_rd(c); |
1895 | if (err) |
1896 | goto out_err; |
1897 | } |
1898 | |
1899 | if (wr) { |
1900 | err = lpt_init_wr(c); |
1901 | if (err) |
1902 | goto out_err; |
1903 | } |
1904 | |
1905 | return 0; |
1906 | |
1907 | out_err: |
1908 | if (wr) |
1909 | ubifs_lpt_free(c, wr_only: 1); |
1910 | if (rd) |
1911 | ubifs_lpt_free(c, wr_only: 0); |
1912 | return err; |
1913 | } |
1914 | |
1915 | /** |
1916 | * struct lpt_scan_node - somewhere to put nodes while we scan LPT. |
1917 | * @nnode: where to keep a nnode |
1918 | * @pnode: where to keep a pnode |
1919 | * @cnode: where to keep a cnode |
1920 | * @in_tree: is the node in the tree in memory |
1921 | * @ptr.nnode: pointer to the nnode (if it is an nnode) which may be here or in |
1922 | * the tree |
1923 | * @ptr.pnode: ditto for pnode |
1924 | * @ptr.cnode: ditto for cnode |
1925 | */ |
1926 | struct lpt_scan_node { |
1927 | union { |
1928 | struct ubifs_nnode nnode; |
1929 | struct ubifs_pnode pnode; |
1930 | struct ubifs_cnode cnode; |
1931 | }; |
1932 | int in_tree; |
1933 | union { |
1934 | struct ubifs_nnode *nnode; |
1935 | struct ubifs_pnode *pnode; |
1936 | struct ubifs_cnode *cnode; |
1937 | } ptr; |
1938 | }; |
1939 | |
1940 | /** |
1941 | * scan_get_nnode - for the scan, get a nnode from either the tree or flash. |
1942 | * @c: the UBIFS file-system description object |
1943 | * @path: where to put the nnode |
1944 | * @parent: parent of the nnode |
1945 | * @iip: index in parent of the nnode |
1946 | * |
1947 | * This function returns a pointer to the nnode on success or a negative error |
1948 | * code on failure. |
1949 | */ |
1950 | static struct ubifs_nnode *scan_get_nnode(struct ubifs_info *c, |
1951 | struct lpt_scan_node *path, |
1952 | struct ubifs_nnode *parent, int iip) |
1953 | { |
1954 | struct ubifs_nbranch *branch; |
1955 | struct ubifs_nnode *nnode; |
1956 | void *buf = c->lpt_nod_buf; |
1957 | int err; |
1958 | |
1959 | branch = &parent->nbranch[iip]; |
1960 | nnode = branch->nnode; |
1961 | if (nnode) { |
1962 | path->in_tree = 1; |
1963 | path->ptr.nnode = nnode; |
1964 | return nnode; |
1965 | } |
1966 | nnode = &path->nnode; |
1967 | path->in_tree = 0; |
1968 | path->ptr.nnode = nnode; |
1969 | memset(nnode, 0, sizeof(struct ubifs_nnode)); |
1970 | if (branch->lnum == 0) { |
1971 | /* |
1972 | * This nnode was not written which just means that the LEB |
1973 | * properties in the subtree below it describe empty LEBs. We |
1974 | * make the nnode as though we had read it, which in fact means |
1975 | * doing almost nothing. |
1976 | */ |
1977 | if (c->big_lpt) |
1978 | nnode->num = calc_nnode_num_from_parent(c, parent, iip); |
1979 | } else { |
1980 | err = ubifs_leb_read(c, lnum: branch->lnum, buf, offs: branch->offs, |
1981 | len: c->nnode_sz, even_ebadmsg: 1); |
1982 | if (err) |
1983 | return ERR_PTR(error: err); |
1984 | err = ubifs_unpack_nnode(c, buf, nnode); |
1985 | if (err) |
1986 | return ERR_PTR(error: err); |
1987 | } |
1988 | err = validate_nnode(c, nnode, parent, iip); |
1989 | if (err) |
1990 | return ERR_PTR(error: err); |
1991 | if (!c->big_lpt) |
1992 | nnode->num = calc_nnode_num_from_parent(c, parent, iip); |
1993 | nnode->level = parent->level - 1; |
1994 | nnode->parent = parent; |
1995 | nnode->iip = iip; |
1996 | return nnode; |
1997 | } |
1998 | |
1999 | /** |
2000 | * scan_get_pnode - for the scan, get a pnode from either the tree or flash. |
2001 | * @c: the UBIFS file-system description object |
2002 | * @path: where to put the pnode |
2003 | * @parent: parent of the pnode |
2004 | * @iip: index in parent of the pnode |
2005 | * |
2006 | * This function returns a pointer to the pnode on success or a negative error |
2007 | * code on failure. |
2008 | */ |
2009 | static struct ubifs_pnode *scan_get_pnode(struct ubifs_info *c, |
2010 | struct lpt_scan_node *path, |
2011 | struct ubifs_nnode *parent, int iip) |
2012 | { |
2013 | struct ubifs_nbranch *branch; |
2014 | struct ubifs_pnode *pnode; |
2015 | void *buf = c->lpt_nod_buf; |
2016 | int err; |
2017 | |
2018 | branch = &parent->nbranch[iip]; |
2019 | pnode = branch->pnode; |
2020 | if (pnode) { |
2021 | path->in_tree = 1; |
2022 | path->ptr.pnode = pnode; |
2023 | return pnode; |
2024 | } |
2025 | pnode = &path->pnode; |
2026 | path->in_tree = 0; |
2027 | path->ptr.pnode = pnode; |
2028 | memset(pnode, 0, sizeof(struct ubifs_pnode)); |
2029 | if (branch->lnum == 0) { |
2030 | /* |
2031 | * This pnode was not written which just means that the LEB |
2032 | * properties in it describe empty LEBs. We make the pnode as |
2033 | * though we had read it. |
2034 | */ |
2035 | int i; |
2036 | |
2037 | if (c->big_lpt) |
2038 | pnode->num = calc_pnode_num_from_parent(c, parent, iip); |
2039 | for (i = 0; i < UBIFS_LPT_FANOUT; i++) { |
2040 | struct ubifs_lprops * const lprops = &pnode->lprops[i]; |
2041 | |
2042 | lprops->free = c->leb_size; |
2043 | lprops->flags = ubifs_categorize_lprops(c, lprops); |
2044 | } |
2045 | } else { |
2046 | ubifs_assert(c, branch->lnum >= c->lpt_first && |
2047 | branch->lnum <= c->lpt_last); |
2048 | ubifs_assert(c, branch->offs >= 0 && branch->offs < c->leb_size); |
2049 | err = ubifs_leb_read(c, lnum: branch->lnum, buf, offs: branch->offs, |
2050 | len: c->pnode_sz, even_ebadmsg: 1); |
2051 | if (err) |
2052 | return ERR_PTR(error: err); |
2053 | err = unpack_pnode(c, buf, pnode); |
2054 | if (err) |
2055 | return ERR_PTR(error: err); |
2056 | } |
2057 | err = validate_pnode(c, pnode, parent, iip); |
2058 | if (err) |
2059 | return ERR_PTR(error: err); |
2060 | if (!c->big_lpt) |
2061 | pnode->num = calc_pnode_num_from_parent(c, parent, iip); |
2062 | pnode->parent = parent; |
2063 | pnode->iip = iip; |
2064 | set_pnode_lnum(c, pnode); |
2065 | return pnode; |
2066 | } |
2067 | |
2068 | /** |
2069 | * ubifs_lpt_scan_nolock - scan the LPT. |
2070 | * @c: the UBIFS file-system description object |
2071 | * @start_lnum: LEB number from which to start scanning |
2072 | * @end_lnum: LEB number at which to stop scanning |
2073 | * @scan_cb: callback function called for each lprops |
2074 | * @data: data to be passed to the callback function |
2075 | * |
2076 | * This function returns %0 on success and a negative error code on failure. |
2077 | */ |
2078 | int ubifs_lpt_scan_nolock(struct ubifs_info *c, int start_lnum, int end_lnum, |
2079 | ubifs_lpt_scan_callback scan_cb, void *data) |
2080 | { |
2081 | int err = 0, i, h, iip, shft; |
2082 | struct ubifs_nnode *nnode; |
2083 | struct ubifs_pnode *pnode; |
2084 | struct lpt_scan_node *path; |
2085 | |
2086 | if (start_lnum == -1) { |
2087 | start_lnum = end_lnum + 1; |
2088 | if (start_lnum >= c->leb_cnt) |
2089 | start_lnum = c->main_first; |
2090 | } |
2091 | |
2092 | ubifs_assert(c, start_lnum >= c->main_first && start_lnum < c->leb_cnt); |
2093 | ubifs_assert(c, end_lnum >= c->main_first && end_lnum < c->leb_cnt); |
2094 | |
2095 | if (!c->nroot) { |
2096 | err = ubifs_read_nnode(c, NULL, iip: 0); |
2097 | if (err) |
2098 | return err; |
2099 | } |
2100 | |
2101 | path = kmalloc_array(n: c->lpt_hght + 1, size: sizeof(struct lpt_scan_node), |
2102 | GFP_NOFS); |
2103 | if (!path) |
2104 | return -ENOMEM; |
2105 | |
2106 | path[0].ptr.nnode = c->nroot; |
2107 | path[0].in_tree = 1; |
2108 | again: |
2109 | /* Descend to the pnode containing start_lnum */ |
2110 | nnode = c->nroot; |
2111 | i = start_lnum - c->main_first; |
2112 | shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT; |
2113 | for (h = 1; h < c->lpt_hght; h++) { |
2114 | iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1)); |
2115 | shft -= UBIFS_LPT_FANOUT_SHIFT; |
2116 | nnode = scan_get_nnode(c, path: path + h, parent: nnode, iip); |
2117 | if (IS_ERR(ptr: nnode)) { |
2118 | err = PTR_ERR(ptr: nnode); |
2119 | goto out; |
2120 | } |
2121 | } |
2122 | iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1)); |
2123 | pnode = scan_get_pnode(c, path: path + h, parent: nnode, iip); |
2124 | if (IS_ERR(ptr: pnode)) { |
2125 | err = PTR_ERR(ptr: pnode); |
2126 | goto out; |
2127 | } |
2128 | iip = (i & (UBIFS_LPT_FANOUT - 1)); |
2129 | |
2130 | /* Loop for each lprops */ |
2131 | while (1) { |
2132 | struct ubifs_lprops *lprops = &pnode->lprops[iip]; |
2133 | int ret, lnum = lprops->lnum; |
2134 | |
2135 | ret = scan_cb(c, lprops, path[h].in_tree, data); |
2136 | if (ret < 0) { |
2137 | err = ret; |
2138 | goto out; |
2139 | } |
2140 | if (ret & LPT_SCAN_ADD) { |
2141 | /* Add all the nodes in path to the tree in memory */ |
2142 | for (h = 1; h < c->lpt_hght; h++) { |
2143 | const size_t sz = sizeof(struct ubifs_nnode); |
2144 | struct ubifs_nnode *parent; |
2145 | |
2146 | if (path[h].in_tree) |
2147 | continue; |
2148 | nnode = kmemdup(p: &path[h].nnode, size: sz, GFP_NOFS); |
2149 | if (!nnode) { |
2150 | err = -ENOMEM; |
2151 | goto out; |
2152 | } |
2153 | parent = nnode->parent; |
2154 | parent->nbranch[nnode->iip].nnode = nnode; |
2155 | path[h].ptr.nnode = nnode; |
2156 | path[h].in_tree = 1; |
2157 | path[h + 1].cnode.parent = nnode; |
2158 | } |
2159 | if (path[h].in_tree) |
2160 | ubifs_ensure_cat(c, lprops); |
2161 | else { |
2162 | const size_t sz = sizeof(struct ubifs_pnode); |
2163 | struct ubifs_nnode *parent; |
2164 | |
2165 | pnode = kmemdup(p: &path[h].pnode, size: sz, GFP_NOFS); |
2166 | if (!pnode) { |
2167 | err = -ENOMEM; |
2168 | goto out; |
2169 | } |
2170 | parent = pnode->parent; |
2171 | parent->nbranch[pnode->iip].pnode = pnode; |
2172 | path[h].ptr.pnode = pnode; |
2173 | path[h].in_tree = 1; |
2174 | update_cats(c, pnode); |
2175 | c->pnodes_have += 1; |
2176 | } |
2177 | err = dbg_check_lpt_nodes(c, cnode: (struct ubifs_cnode *) |
2178 | c->nroot, row: 0, col: 0); |
2179 | if (err) |
2180 | goto out; |
2181 | err = dbg_check_cats(c); |
2182 | if (err) |
2183 | goto out; |
2184 | } |
2185 | if (ret & LPT_SCAN_STOP) { |
2186 | err = 0; |
2187 | break; |
2188 | } |
2189 | /* Get the next lprops */ |
2190 | if (lnum == end_lnum) { |
2191 | /* |
2192 | * We got to the end without finding what we were |
2193 | * looking for |
2194 | */ |
2195 | err = -ENOSPC; |
2196 | goto out; |
2197 | } |
2198 | if (lnum + 1 >= c->leb_cnt) { |
2199 | /* Wrap-around to the beginning */ |
2200 | start_lnum = c->main_first; |
2201 | goto again; |
2202 | } |
2203 | if (iip + 1 < UBIFS_LPT_FANOUT) { |
2204 | /* Next lprops is in the same pnode */ |
2205 | iip += 1; |
2206 | continue; |
2207 | } |
2208 | /* We need to get the next pnode. Go up until we can go right */ |
2209 | iip = pnode->iip; |
2210 | while (1) { |
2211 | h -= 1; |
2212 | ubifs_assert(c, h >= 0); |
2213 | nnode = path[h].ptr.nnode; |
2214 | if (iip + 1 < UBIFS_LPT_FANOUT) |
2215 | break; |
2216 | iip = nnode->iip; |
2217 | } |
2218 | /* Go right */ |
2219 | iip += 1; |
2220 | /* Descend to the pnode */ |
2221 | h += 1; |
2222 | for (; h < c->lpt_hght; h++) { |
2223 | nnode = scan_get_nnode(c, path: path + h, parent: nnode, iip); |
2224 | if (IS_ERR(ptr: nnode)) { |
2225 | err = PTR_ERR(ptr: nnode); |
2226 | goto out; |
2227 | } |
2228 | iip = 0; |
2229 | } |
2230 | pnode = scan_get_pnode(c, path: path + h, parent: nnode, iip); |
2231 | if (IS_ERR(ptr: pnode)) { |
2232 | err = PTR_ERR(ptr: pnode); |
2233 | goto out; |
2234 | } |
2235 | iip = 0; |
2236 | } |
2237 | out: |
2238 | kfree(objp: path); |
2239 | return err; |
2240 | } |
2241 | |
2242 | /** |
2243 | * dbg_chk_pnode - check a pnode. |
2244 | * @c: the UBIFS file-system description object |
2245 | * @pnode: pnode to check |
2246 | * @col: pnode column |
2247 | * |
2248 | * This function returns %0 on success and a negative error code on failure. |
2249 | */ |
2250 | static int dbg_chk_pnode(struct ubifs_info *c, struct ubifs_pnode *pnode, |
2251 | int col) |
2252 | { |
2253 | int i; |
2254 | |
2255 | if (pnode->num != col) { |
2256 | ubifs_err(c, fmt: "pnode num %d expected %d parent num %d iip %d" , |
2257 | pnode->num, col, pnode->parent->num, pnode->iip); |
2258 | return -EINVAL; |
2259 | } |
2260 | for (i = 0; i < UBIFS_LPT_FANOUT; i++) { |
2261 | struct ubifs_lprops *lp, *lprops = &pnode->lprops[i]; |
2262 | int lnum = (pnode->num << UBIFS_LPT_FANOUT_SHIFT) + i + |
2263 | c->main_first; |
2264 | int found, cat = lprops->flags & LPROPS_CAT_MASK; |
2265 | struct ubifs_lpt_heap *heap; |
2266 | struct list_head *list = NULL; |
2267 | |
2268 | if (lnum >= c->leb_cnt) |
2269 | continue; |
2270 | if (lprops->lnum != lnum) { |
2271 | ubifs_err(c, fmt: "bad LEB number %d expected %d" , |
2272 | lprops->lnum, lnum); |
2273 | return -EINVAL; |
2274 | } |
2275 | if (lprops->flags & LPROPS_TAKEN) { |
2276 | if (cat != LPROPS_UNCAT) { |
2277 | ubifs_err(c, fmt: "LEB %d taken but not uncat %d" , |
2278 | lprops->lnum, cat); |
2279 | return -EINVAL; |
2280 | } |
2281 | continue; |
2282 | } |
2283 | if (lprops->flags & LPROPS_INDEX) { |
2284 | switch (cat) { |
2285 | case LPROPS_UNCAT: |
2286 | case LPROPS_DIRTY_IDX: |
2287 | case LPROPS_FRDI_IDX: |
2288 | break; |
2289 | default: |
2290 | ubifs_err(c, fmt: "LEB %d index but cat %d" , |
2291 | lprops->lnum, cat); |
2292 | return -EINVAL; |
2293 | } |
2294 | } else { |
2295 | switch (cat) { |
2296 | case LPROPS_UNCAT: |
2297 | case LPROPS_DIRTY: |
2298 | case LPROPS_FREE: |
2299 | case LPROPS_EMPTY: |
2300 | case LPROPS_FREEABLE: |
2301 | break; |
2302 | default: |
2303 | ubifs_err(c, fmt: "LEB %d not index but cat %d" , |
2304 | lprops->lnum, cat); |
2305 | return -EINVAL; |
2306 | } |
2307 | } |
2308 | switch (cat) { |
2309 | case LPROPS_UNCAT: |
2310 | list = &c->uncat_list; |
2311 | break; |
2312 | case LPROPS_EMPTY: |
2313 | list = &c->empty_list; |
2314 | break; |
2315 | case LPROPS_FREEABLE: |
2316 | list = &c->freeable_list; |
2317 | break; |
2318 | case LPROPS_FRDI_IDX: |
2319 | list = &c->frdi_idx_list; |
2320 | break; |
2321 | } |
2322 | found = 0; |
2323 | switch (cat) { |
2324 | case LPROPS_DIRTY: |
2325 | case LPROPS_DIRTY_IDX: |
2326 | case LPROPS_FREE: |
2327 | heap = &c->lpt_heap[cat - 1]; |
2328 | if (lprops->hpos < heap->cnt && |
2329 | heap->arr[lprops->hpos] == lprops) |
2330 | found = 1; |
2331 | break; |
2332 | case LPROPS_UNCAT: |
2333 | case LPROPS_EMPTY: |
2334 | case LPROPS_FREEABLE: |
2335 | case LPROPS_FRDI_IDX: |
2336 | list_for_each_entry(lp, list, list) |
2337 | if (lprops == lp) { |
2338 | found = 1; |
2339 | break; |
2340 | } |
2341 | break; |
2342 | } |
2343 | if (!found) { |
2344 | ubifs_err(c, fmt: "LEB %d cat %d not found in cat heap/list" , |
2345 | lprops->lnum, cat); |
2346 | return -EINVAL; |
2347 | } |
2348 | switch (cat) { |
2349 | case LPROPS_EMPTY: |
2350 | if (lprops->free != c->leb_size) { |
2351 | ubifs_err(c, fmt: "LEB %d cat %d free %d dirty %d" , |
2352 | lprops->lnum, cat, lprops->free, |
2353 | lprops->dirty); |
2354 | return -EINVAL; |
2355 | } |
2356 | break; |
2357 | case LPROPS_FREEABLE: |
2358 | case LPROPS_FRDI_IDX: |
2359 | if (lprops->free + lprops->dirty != c->leb_size) { |
2360 | ubifs_err(c, fmt: "LEB %d cat %d free %d dirty %d" , |
2361 | lprops->lnum, cat, lprops->free, |
2362 | lprops->dirty); |
2363 | return -EINVAL; |
2364 | } |
2365 | break; |
2366 | } |
2367 | } |
2368 | return 0; |
2369 | } |
2370 | |
2371 | /** |
2372 | * dbg_check_lpt_nodes - check nnodes and pnodes. |
2373 | * @c: the UBIFS file-system description object |
2374 | * @cnode: next cnode (nnode or pnode) to check |
2375 | * @row: row of cnode (root is zero) |
2376 | * @col: column of cnode (leftmost is zero) |
2377 | * |
2378 | * This function returns %0 on success and a negative error code on failure. |
2379 | */ |
2380 | int dbg_check_lpt_nodes(struct ubifs_info *c, struct ubifs_cnode *cnode, |
2381 | int row, int col) |
2382 | { |
2383 | struct ubifs_nnode *nnode, *nn; |
2384 | struct ubifs_cnode *cn; |
2385 | int num, iip = 0, err; |
2386 | |
2387 | if (!dbg_is_chk_lprops(c)) |
2388 | return 0; |
2389 | |
2390 | while (cnode) { |
2391 | ubifs_assert(c, row >= 0); |
2392 | nnode = cnode->parent; |
2393 | if (cnode->level) { |
2394 | /* cnode is a nnode */ |
2395 | num = calc_nnode_num(row, col); |
2396 | if (cnode->num != num) { |
2397 | ubifs_err(c, fmt: "nnode num %d expected %d parent num %d iip %d" , |
2398 | cnode->num, num, |
2399 | (nnode ? nnode->num : 0), cnode->iip); |
2400 | return -EINVAL; |
2401 | } |
2402 | nn = (struct ubifs_nnode *)cnode; |
2403 | while (iip < UBIFS_LPT_FANOUT) { |
2404 | cn = nn->nbranch[iip].cnode; |
2405 | if (cn) { |
2406 | /* Go down */ |
2407 | row += 1; |
2408 | col <<= UBIFS_LPT_FANOUT_SHIFT; |
2409 | col += iip; |
2410 | iip = 0; |
2411 | cnode = cn; |
2412 | break; |
2413 | } |
2414 | /* Go right */ |
2415 | iip += 1; |
2416 | } |
2417 | if (iip < UBIFS_LPT_FANOUT) |
2418 | continue; |
2419 | } else { |
2420 | struct ubifs_pnode *pnode; |
2421 | |
2422 | /* cnode is a pnode */ |
2423 | pnode = (struct ubifs_pnode *)cnode; |
2424 | err = dbg_chk_pnode(c, pnode, col); |
2425 | if (err) |
2426 | return err; |
2427 | } |
2428 | /* Go up and to the right */ |
2429 | row -= 1; |
2430 | col >>= UBIFS_LPT_FANOUT_SHIFT; |
2431 | iip = cnode->iip + 1; |
2432 | cnode = (struct ubifs_cnode *)nnode; |
2433 | } |
2434 | return 0; |
2435 | } |
2436 | |