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