2 * This file is part of UBIFS.
4 * Copyright (C) 2006-2008 Nokia Corporation.
6 * SPDX-License-Identifier: GPL-2.0+
8 * Authors: Adrian Hunter
9 * Artem Bityutskiy (Битюцкий Артём)
13 * This file implements the LEB properties tree (LPT) area. The LPT area
14 * contains the LEB properties tree, a table of LPT area eraseblocks (ltab), and
15 * (for the "big" model) a table of saved LEB numbers (lsave). The LPT area sits
16 * between the log and the orphan area.
18 * The LPT area is like a miniature self-contained file system. It is required
19 * that it never runs out of space, is fast to access and update, and scales
20 * logarithmically. The LEB properties tree is implemented as a wandering tree
21 * much like the TNC, and the LPT area has its own garbage collection.
23 * The LPT has two slightly different forms called the "small model" and the
24 * "big model". The small model is used when the entire LEB properties table
25 * can be written into a single eraseblock. In that case, garbage collection
26 * consists of just writing the whole table, which therefore makes all other
27 * eraseblocks reusable. In the case of the big model, dirty eraseblocks are
28 * selected for garbage collection, which consists of marking the clean nodes in
29 * that LEB as dirty, and then only the dirty nodes are written out. Also, in
30 * the case of the big model, a table of LEB numbers is saved so that the entire
31 * LPT does not to be scanned looking for empty eraseblocks when UBIFS is first
37 #include <linux/crc16.h>
38 #include <linux/math64.h>
39 #include <linux/slab.h>
41 #include <linux/compat.h>
42 #include <linux/err.h>
43 #include <ubi_uboot.h>
48 * do_calc_lpt_geom - calculate sizes for the LPT area.
49 * @c: the UBIFS file-system description object
51 * Calculate the sizes of LPT bit fields, nodes, and tree, based on the
52 * properties of the flash and whether LPT is "big" (c->big_lpt).
54 static void do_calc_lpt_geom(struct ubifs_info
*c
)
56 int i
, n
, bits
, per_leb_wastage
, max_pnode_cnt
;
57 long long sz
, tot_wastage
;
59 n
= c
->main_lebs
+ c
->max_leb_cnt
- c
->leb_cnt
;
60 max_pnode_cnt
= DIV_ROUND_UP(n
, UBIFS_LPT_FANOUT
);
64 while (n
< max_pnode_cnt
) {
66 n
<<= UBIFS_LPT_FANOUT_SHIFT
;
69 c
->pnode_cnt
= DIV_ROUND_UP(c
->main_lebs
, UBIFS_LPT_FANOUT
);
71 n
= DIV_ROUND_UP(c
->pnode_cnt
, UBIFS_LPT_FANOUT
);
73 for (i
= 1; i
< c
->lpt_hght
; i
++) {
74 n
= DIV_ROUND_UP(n
, UBIFS_LPT_FANOUT
);
78 c
->space_bits
= fls(c
->leb_size
) - 3;
79 c
->lpt_lnum_bits
= fls(c
->lpt_lebs
);
80 c
->lpt_offs_bits
= fls(c
->leb_size
- 1);
81 c
->lpt_spc_bits
= fls(c
->leb_size
);
83 n
= DIV_ROUND_UP(c
->max_leb_cnt
, UBIFS_LPT_FANOUT
);
84 c
->pcnt_bits
= fls(n
- 1);
86 c
->lnum_bits
= fls(c
->max_leb_cnt
- 1);
88 bits
= UBIFS_LPT_CRC_BITS
+ UBIFS_LPT_TYPE_BITS
+
89 (c
->big_lpt
? c
->pcnt_bits
: 0) +
90 (c
->space_bits
* 2 + 1) * UBIFS_LPT_FANOUT
;
91 c
->pnode_sz
= (bits
+ 7) / 8;
93 bits
= UBIFS_LPT_CRC_BITS
+ UBIFS_LPT_TYPE_BITS
+
94 (c
->big_lpt
? c
->pcnt_bits
: 0) +
95 (c
->lpt_lnum_bits
+ c
->lpt_offs_bits
) * UBIFS_LPT_FANOUT
;
96 c
->nnode_sz
= (bits
+ 7) / 8;
98 bits
= UBIFS_LPT_CRC_BITS
+ UBIFS_LPT_TYPE_BITS
+
99 c
->lpt_lebs
* c
->lpt_spc_bits
* 2;
100 c
->ltab_sz
= (bits
+ 7) / 8;
102 bits
= UBIFS_LPT_CRC_BITS
+ UBIFS_LPT_TYPE_BITS
+
103 c
->lnum_bits
* c
->lsave_cnt
;
104 c
->lsave_sz
= (bits
+ 7) / 8;
106 /* Calculate the minimum LPT size */
107 c
->lpt_sz
= (long long)c
->pnode_cnt
* c
->pnode_sz
;
108 c
->lpt_sz
+= (long long)c
->nnode_cnt
* c
->nnode_sz
;
109 c
->lpt_sz
+= c
->ltab_sz
;
111 c
->lpt_sz
+= c
->lsave_sz
;
115 per_leb_wastage
= max_t(int, c
->pnode_sz
, c
->nnode_sz
);
116 sz
+= per_leb_wastage
;
117 tot_wastage
= per_leb_wastage
;
118 while (sz
> c
->leb_size
) {
119 sz
+= per_leb_wastage
;
121 tot_wastage
+= per_leb_wastage
;
123 tot_wastage
+= ALIGN(sz
, c
->min_io_size
) - sz
;
124 c
->lpt_sz
+= tot_wastage
;
128 * ubifs_calc_lpt_geom - calculate and check sizes for the LPT area.
129 * @c: the UBIFS file-system description object
131 * This function returns %0 on success and a negative error code on failure.
133 int ubifs_calc_lpt_geom(struct ubifs_info
*c
)
140 /* Verify that lpt_lebs is big enough */
141 sz
= c
->lpt_sz
* 2; /* Must have at least 2 times the size */
142 lebs_needed
= div_u64(sz
+ c
->leb_size
- 1, c
->leb_size
);
143 if (lebs_needed
> c
->lpt_lebs
) {
144 ubifs_err(c
, "too few LPT LEBs");
148 /* Verify that ltab fits in a single LEB (since ltab is a single node */
149 if (c
->ltab_sz
> c
->leb_size
) {
150 ubifs_err(c
, "LPT ltab too big");
154 c
->check_lpt_free
= c
->big_lpt
;
159 * calc_dflt_lpt_geom - calculate default LPT geometry.
160 * @c: the UBIFS file-system description object
161 * @main_lebs: number of main area LEBs is passed and returned here
162 * @big_lpt: whether the LPT area is "big" is returned here
164 * The size of the LPT area depends on parameters that themselves are dependent
165 * on the size of the LPT area. This function, successively recalculates the LPT
166 * area geometry until the parameters and resultant geometry are consistent.
168 * This function returns %0 on success and a negative error code on failure.
170 static int calc_dflt_lpt_geom(struct ubifs_info
*c
, int *main_lebs
,
176 /* Start by assuming the minimum number of LPT LEBs */
177 c
->lpt_lebs
= UBIFS_MIN_LPT_LEBS
;
178 c
->main_lebs
= *main_lebs
- c
->lpt_lebs
;
179 if (c
->main_lebs
<= 0)
182 /* And assume we will use the small LPT model */
186 * Calculate the geometry based on assumptions above and then see if it
191 /* Small LPT model must have lpt_sz < leb_size */
192 if (c
->lpt_sz
> c
->leb_size
) {
193 /* Nope, so try again using big LPT model */
198 /* Now check there are enough LPT LEBs */
199 for (i
= 0; i
< 64 ; i
++) {
200 sz
= c
->lpt_sz
* 4; /* Allow 4 times the size */
201 lebs_needed
= div_u64(sz
+ c
->leb_size
- 1, c
->leb_size
);
202 if (lebs_needed
> c
->lpt_lebs
) {
203 /* Not enough LPT LEBs so try again with more */
204 c
->lpt_lebs
= lebs_needed
;
205 c
->main_lebs
= *main_lebs
- c
->lpt_lebs
;
206 if (c
->main_lebs
<= 0)
211 if (c
->ltab_sz
> c
->leb_size
) {
212 ubifs_err(c
, "LPT ltab too big");
215 *main_lebs
= c
->main_lebs
;
216 *big_lpt
= c
->big_lpt
;
223 * pack_bits - pack bit fields end-to-end.
224 * @addr: address at which to pack (passed and next address returned)
225 * @pos: bit position at which to pack (passed and next position returned)
226 * @val: value to pack
227 * @nrbits: number of bits of value to pack (1-32)
229 static void pack_bits(uint8_t **addr
, int *pos
, uint32_t val
, int nrbits
)
234 ubifs_assert(nrbits
> 0);
235 ubifs_assert(nrbits
<= 32);
236 ubifs_assert(*pos
>= 0);
237 ubifs_assert(*pos
< 8);
238 ubifs_assert((val
>> nrbits
) == 0 || nrbits
== 32);
240 *p
|= ((uint8_t)val
) << b
;
243 *++p
= (uint8_t)(val
>>= (8 - b
));
245 *++p
= (uint8_t)(val
>>= 8);
247 *++p
= (uint8_t)(val
>>= 8);
249 *++p
= (uint8_t)(val
>>= 8);
256 *++p
= (uint8_t)(val
>>= 8);
258 *++p
= (uint8_t)(val
>>= 8);
260 *++p
= (uint8_t)(val
>>= 8);
272 * ubifs_unpack_bits - unpack bit fields.
273 * @addr: address at which to unpack (passed and next address returned)
274 * @pos: bit position at which to unpack (passed and next position returned)
275 * @nrbits: number of bits of value to unpack (1-32)
277 * This functions returns the value unpacked.
279 uint32_t ubifs_unpack_bits(uint8_t **addr
, int *pos
, int nrbits
)
281 const int k
= 32 - nrbits
;
284 uint32_t uninitialized_var(val
);
285 const int bytes
= (nrbits
+ b
+ 7) >> 3;
287 ubifs_assert(nrbits
> 0);
288 ubifs_assert(nrbits
<= 32);
289 ubifs_assert(*pos
>= 0);
290 ubifs_assert(*pos
< 8);
297 val
= p
[1] | ((uint32_t)p
[2] << 8);
300 val
= p
[1] | ((uint32_t)p
[2] << 8) |
301 ((uint32_t)p
[3] << 16);
304 val
= p
[1] | ((uint32_t)p
[2] << 8) |
305 ((uint32_t)p
[3] << 16) |
306 ((uint32_t)p
[4] << 24);
317 val
= p
[0] | ((uint32_t)p
[1] << 8);
320 val
= p
[0] | ((uint32_t)p
[1] << 8) |
321 ((uint32_t)p
[2] << 16);
324 val
= p
[0] | ((uint32_t)p
[1] << 8) |
325 ((uint32_t)p
[2] << 16) |
326 ((uint32_t)p
[3] << 24);
336 ubifs_assert((val
>> nrbits
) == 0 || nrbits
- b
== 32);
341 * ubifs_pack_pnode - pack all the bit fields of a pnode.
342 * @c: UBIFS file-system description object
343 * @buf: buffer into which to pack
344 * @pnode: pnode to pack
346 void ubifs_pack_pnode(struct ubifs_info
*c
, void *buf
,
347 struct ubifs_pnode
*pnode
)
349 uint8_t *addr
= buf
+ UBIFS_LPT_CRC_BYTES
;
353 pack_bits(&addr
, &pos
, UBIFS_LPT_PNODE
, UBIFS_LPT_TYPE_BITS
);
355 pack_bits(&addr
, &pos
, pnode
->num
, c
->pcnt_bits
);
356 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
357 pack_bits(&addr
, &pos
, pnode
->lprops
[i
].free
>> 3,
359 pack_bits(&addr
, &pos
, pnode
->lprops
[i
].dirty
>> 3,
361 if (pnode
->lprops
[i
].flags
& LPROPS_INDEX
)
362 pack_bits(&addr
, &pos
, 1, 1);
364 pack_bits(&addr
, &pos
, 0, 1);
366 crc
= crc16(-1, buf
+ UBIFS_LPT_CRC_BYTES
,
367 c
->pnode_sz
- UBIFS_LPT_CRC_BYTES
);
370 pack_bits(&addr
, &pos
, crc
, UBIFS_LPT_CRC_BITS
);
374 * ubifs_pack_nnode - pack all the bit fields of a nnode.
375 * @c: UBIFS file-system description object
376 * @buf: buffer into which to pack
377 * @nnode: nnode to pack
379 void ubifs_pack_nnode(struct ubifs_info
*c
, void *buf
,
380 struct ubifs_nnode
*nnode
)
382 uint8_t *addr
= buf
+ UBIFS_LPT_CRC_BYTES
;
386 pack_bits(&addr
, &pos
, UBIFS_LPT_NNODE
, UBIFS_LPT_TYPE_BITS
);
388 pack_bits(&addr
, &pos
, nnode
->num
, c
->pcnt_bits
);
389 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
390 int lnum
= nnode
->nbranch
[i
].lnum
;
393 lnum
= c
->lpt_last
+ 1;
394 pack_bits(&addr
, &pos
, lnum
- c
->lpt_first
, c
->lpt_lnum_bits
);
395 pack_bits(&addr
, &pos
, nnode
->nbranch
[i
].offs
,
398 crc
= crc16(-1, buf
+ UBIFS_LPT_CRC_BYTES
,
399 c
->nnode_sz
- UBIFS_LPT_CRC_BYTES
);
402 pack_bits(&addr
, &pos
, crc
, UBIFS_LPT_CRC_BITS
);
406 * ubifs_pack_ltab - pack the LPT's own lprops table.
407 * @c: UBIFS file-system description object
408 * @buf: buffer into which to pack
409 * @ltab: LPT's own lprops table to pack
411 void ubifs_pack_ltab(struct ubifs_info
*c
, void *buf
,
412 struct ubifs_lpt_lprops
*ltab
)
414 uint8_t *addr
= buf
+ UBIFS_LPT_CRC_BYTES
;
418 pack_bits(&addr
, &pos
, UBIFS_LPT_LTAB
, UBIFS_LPT_TYPE_BITS
);
419 for (i
= 0; i
< c
->lpt_lebs
; i
++) {
420 pack_bits(&addr
, &pos
, ltab
[i
].free
, c
->lpt_spc_bits
);
421 pack_bits(&addr
, &pos
, ltab
[i
].dirty
, c
->lpt_spc_bits
);
423 crc
= crc16(-1, buf
+ UBIFS_LPT_CRC_BYTES
,
424 c
->ltab_sz
- UBIFS_LPT_CRC_BYTES
);
427 pack_bits(&addr
, &pos
, crc
, UBIFS_LPT_CRC_BITS
);
431 * ubifs_pack_lsave - pack the LPT's save table.
432 * @c: UBIFS file-system description object
433 * @buf: buffer into which to pack
434 * @lsave: LPT's save table to pack
436 void ubifs_pack_lsave(struct ubifs_info
*c
, void *buf
, int *lsave
)
438 uint8_t *addr
= buf
+ UBIFS_LPT_CRC_BYTES
;
442 pack_bits(&addr
, &pos
, UBIFS_LPT_LSAVE
, UBIFS_LPT_TYPE_BITS
);
443 for (i
= 0; i
< c
->lsave_cnt
; i
++)
444 pack_bits(&addr
, &pos
, lsave
[i
], c
->lnum_bits
);
445 crc
= crc16(-1, buf
+ UBIFS_LPT_CRC_BYTES
,
446 c
->lsave_sz
- UBIFS_LPT_CRC_BYTES
);
449 pack_bits(&addr
, &pos
, crc
, UBIFS_LPT_CRC_BITS
);
453 * ubifs_add_lpt_dirt - add dirty space to LPT LEB properties.
454 * @c: UBIFS file-system description object
455 * @lnum: LEB number to which to add dirty space
456 * @dirty: amount of dirty space to add
458 void ubifs_add_lpt_dirt(struct ubifs_info
*c
, int lnum
, int dirty
)
462 dbg_lp("LEB %d add %d to %d",
463 lnum
, dirty
, c
->ltab
[lnum
- c
->lpt_first
].dirty
);
464 ubifs_assert(lnum
>= c
->lpt_first
&& lnum
<= c
->lpt_last
);
465 c
->ltab
[lnum
- c
->lpt_first
].dirty
+= dirty
;
469 * set_ltab - set LPT LEB properties.
470 * @c: UBIFS file-system description object
472 * @free: amount of free space
473 * @dirty: amount of dirty space
475 static void set_ltab(struct ubifs_info
*c
, int lnum
, int free
, int dirty
)
477 dbg_lp("LEB %d free %d dirty %d to %d %d",
478 lnum
, c
->ltab
[lnum
- c
->lpt_first
].free
,
479 c
->ltab
[lnum
- c
->lpt_first
].dirty
, free
, dirty
);
480 ubifs_assert(lnum
>= c
->lpt_first
&& lnum
<= c
->lpt_last
);
481 c
->ltab
[lnum
- c
->lpt_first
].free
= free
;
482 c
->ltab
[lnum
- c
->lpt_first
].dirty
= dirty
;
486 * ubifs_add_nnode_dirt - add dirty space to LPT LEB properties.
487 * @c: UBIFS file-system description object
488 * @nnode: nnode for which to add dirt
490 void ubifs_add_nnode_dirt(struct ubifs_info
*c
, struct ubifs_nnode
*nnode
)
492 struct ubifs_nnode
*np
= nnode
->parent
;
495 ubifs_add_lpt_dirt(c
, np
->nbranch
[nnode
->iip
].lnum
,
498 ubifs_add_lpt_dirt(c
, c
->lpt_lnum
, c
->nnode_sz
);
499 if (!(c
->lpt_drty_flgs
& LTAB_DIRTY
)) {
500 c
->lpt_drty_flgs
|= LTAB_DIRTY
;
501 ubifs_add_lpt_dirt(c
, c
->ltab_lnum
, c
->ltab_sz
);
507 * add_pnode_dirt - add dirty space to LPT LEB properties.
508 * @c: UBIFS file-system description object
509 * @pnode: pnode for which to add dirt
511 static void add_pnode_dirt(struct ubifs_info
*c
, struct ubifs_pnode
*pnode
)
513 ubifs_add_lpt_dirt(c
, pnode
->parent
->nbranch
[pnode
->iip
].lnum
,
518 * calc_nnode_num - calculate nnode number.
519 * @row: the row in the tree (root is zero)
520 * @col: the column in the row (leftmost is zero)
522 * The nnode number is a number that uniquely identifies a nnode and can be used
523 * easily to traverse the tree from the root to that nnode.
525 * This function calculates and returns the nnode number for the nnode at @row
528 static int calc_nnode_num(int row
, int col
)
534 bits
= (col
& (UBIFS_LPT_FANOUT
- 1));
535 col
>>= UBIFS_LPT_FANOUT_SHIFT
;
536 num
<<= UBIFS_LPT_FANOUT_SHIFT
;
543 * calc_nnode_num_from_parent - calculate nnode number.
544 * @c: UBIFS file-system description object
545 * @parent: parent nnode
546 * @iip: index in parent
548 * The nnode number is a number that uniquely identifies a nnode and can be used
549 * easily to traverse the tree from the root to that nnode.
551 * This function calculates and returns the nnode number based on the parent's
552 * nnode number and the index in parent.
554 static int calc_nnode_num_from_parent(const struct ubifs_info
*c
,
555 struct ubifs_nnode
*parent
, int iip
)
561 shft
= (c
->lpt_hght
- parent
->level
) * UBIFS_LPT_FANOUT_SHIFT
;
562 num
= parent
->num
^ (1 << shft
);
563 num
|= (UBIFS_LPT_FANOUT
+ iip
) << shft
;
568 * calc_pnode_num_from_parent - calculate pnode number.
569 * @c: UBIFS file-system description object
570 * @parent: parent nnode
571 * @iip: index in parent
573 * The pnode number is a number that uniquely identifies a pnode and can be used
574 * easily to traverse the tree from the root to that pnode.
576 * This function calculates and returns the pnode number based on the parent's
577 * nnode number and the index in parent.
579 static int calc_pnode_num_from_parent(const struct ubifs_info
*c
,
580 struct ubifs_nnode
*parent
, int iip
)
582 int i
, n
= c
->lpt_hght
- 1, pnum
= parent
->num
, num
= 0;
584 for (i
= 0; i
< n
; i
++) {
585 num
<<= UBIFS_LPT_FANOUT_SHIFT
;
586 num
|= pnum
& (UBIFS_LPT_FANOUT
- 1);
587 pnum
>>= UBIFS_LPT_FANOUT_SHIFT
;
589 num
<<= UBIFS_LPT_FANOUT_SHIFT
;
595 * ubifs_create_dflt_lpt - create default LPT.
596 * @c: UBIFS file-system description object
597 * @main_lebs: number of main area LEBs is passed and returned here
598 * @lpt_first: LEB number of first LPT LEB
599 * @lpt_lebs: number of LEBs for LPT is passed and returned here
600 * @big_lpt: use big LPT model is passed and returned here
602 * This function returns %0 on success and a negative error code on failure.
604 int ubifs_create_dflt_lpt(struct ubifs_info
*c
, int *main_lebs
, int lpt_first
,
605 int *lpt_lebs
, int *big_lpt
)
607 int lnum
, err
= 0, node_sz
, iopos
, i
, j
, cnt
, len
, alen
, row
;
608 int blnum
, boffs
, bsz
, bcnt
;
609 struct ubifs_pnode
*pnode
= NULL
;
610 struct ubifs_nnode
*nnode
= NULL
;
611 void *buf
= NULL
, *p
;
612 struct ubifs_lpt_lprops
*ltab
= NULL
;
615 err
= calc_dflt_lpt_geom(c
, main_lebs
, big_lpt
);
618 *lpt_lebs
= c
->lpt_lebs
;
620 /* Needed by 'ubifs_pack_nnode()' and 'set_ltab()' */
621 c
->lpt_first
= lpt_first
;
622 /* Needed by 'set_ltab()' */
623 c
->lpt_last
= lpt_first
+ c
->lpt_lebs
- 1;
624 /* Needed by 'ubifs_pack_lsave()' */
625 c
->main_first
= c
->leb_cnt
- *main_lebs
;
627 lsave
= kmalloc(sizeof(int) * c
->lsave_cnt
, GFP_KERNEL
);
628 pnode
= kzalloc(sizeof(struct ubifs_pnode
), GFP_KERNEL
);
629 nnode
= kzalloc(sizeof(struct ubifs_nnode
), GFP_KERNEL
);
630 buf
= vmalloc(c
->leb_size
);
631 ltab
= vmalloc(sizeof(struct ubifs_lpt_lprops
) * c
->lpt_lebs
);
632 if (!pnode
|| !nnode
|| !buf
|| !ltab
|| !lsave
) {
637 ubifs_assert(!c
->ltab
);
638 c
->ltab
= ltab
; /* Needed by set_ltab */
640 /* Initialize LPT's own lprops */
641 for (i
= 0; i
< c
->lpt_lebs
; i
++) {
642 ltab
[i
].free
= c
->leb_size
;
650 /* Number of leaf nodes (pnodes) */
654 * The first pnode contains the LEB properties for the LEBs that contain
655 * the root inode node and the root index node of the index tree.
657 node_sz
= ALIGN(ubifs_idx_node_sz(c
, 1), 8);
658 iopos
= ALIGN(node_sz
, c
->min_io_size
);
659 pnode
->lprops
[0].free
= c
->leb_size
- iopos
;
660 pnode
->lprops
[0].dirty
= iopos
- node_sz
;
661 pnode
->lprops
[0].flags
= LPROPS_INDEX
;
663 node_sz
= UBIFS_INO_NODE_SZ
;
664 iopos
= ALIGN(node_sz
, c
->min_io_size
);
665 pnode
->lprops
[1].free
= c
->leb_size
- iopos
;
666 pnode
->lprops
[1].dirty
= iopos
- node_sz
;
668 for (i
= 2; i
< UBIFS_LPT_FANOUT
; i
++)
669 pnode
->lprops
[i
].free
= c
->leb_size
;
671 /* Add first pnode */
672 ubifs_pack_pnode(c
, p
, pnode
);
677 /* Reset pnode values for remaining pnodes */
678 pnode
->lprops
[0].free
= c
->leb_size
;
679 pnode
->lprops
[0].dirty
= 0;
680 pnode
->lprops
[0].flags
= 0;
682 pnode
->lprops
[1].free
= c
->leb_size
;
683 pnode
->lprops
[1].dirty
= 0;
686 * To calculate the internal node branches, we keep information about
689 blnum
= lnum
; /* LEB number of level below */
690 boffs
= 0; /* Offset of level below */
691 bcnt
= cnt
; /* Number of nodes in level below */
692 bsz
= c
->pnode_sz
; /* Size of nodes in level below */
694 /* Add all remaining pnodes */
695 for (i
= 1; i
< cnt
; i
++) {
696 if (len
+ c
->pnode_sz
> c
->leb_size
) {
697 alen
= ALIGN(len
, c
->min_io_size
);
698 set_ltab(c
, lnum
, c
->leb_size
- alen
, alen
- len
);
699 memset(p
, 0xff, alen
- len
);
700 err
= ubifs_leb_change(c
, lnum
++, buf
, alen
);
706 ubifs_pack_pnode(c
, p
, pnode
);
710 * pnodes are simply numbered left to right starting at zero,
711 * which means the pnode number can be used easily to traverse
712 * down the tree to the corresponding pnode.
718 for (i
= UBIFS_LPT_FANOUT
; cnt
> i
; i
<<= UBIFS_LPT_FANOUT_SHIFT
)
720 /* Add all nnodes, one level at a time */
722 /* Number of internal nodes (nnodes) at next level */
723 cnt
= DIV_ROUND_UP(cnt
, UBIFS_LPT_FANOUT
);
724 for (i
= 0; i
< cnt
; i
++) {
725 if (len
+ c
->nnode_sz
> c
->leb_size
) {
726 alen
= ALIGN(len
, c
->min_io_size
);
727 set_ltab(c
, lnum
, c
->leb_size
- alen
,
729 memset(p
, 0xff, alen
- len
);
730 err
= ubifs_leb_change(c
, lnum
++, buf
, alen
);
736 /* Only 1 nnode at this level, so it is the root */
741 /* Set branches to the level below */
742 for (j
= 0; j
< UBIFS_LPT_FANOUT
; j
++) {
744 if (boffs
+ bsz
> c
->leb_size
) {
748 nnode
->nbranch
[j
].lnum
= blnum
;
749 nnode
->nbranch
[j
].offs
= boffs
;
753 nnode
->nbranch
[j
].lnum
= 0;
754 nnode
->nbranch
[j
].offs
= 0;
757 nnode
->num
= calc_nnode_num(row
, i
);
758 ubifs_pack_nnode(c
, p
, nnode
);
762 /* Only 1 nnode at this level, so it is the root */
765 /* Update the information about the level below */
772 /* Need to add LPT's save table */
773 if (len
+ c
->lsave_sz
> c
->leb_size
) {
774 alen
= ALIGN(len
, c
->min_io_size
);
775 set_ltab(c
, lnum
, c
->leb_size
- alen
, alen
- len
);
776 memset(p
, 0xff, alen
- len
);
777 err
= ubifs_leb_change(c
, lnum
++, buf
, alen
);
784 c
->lsave_lnum
= lnum
;
787 for (i
= 0; i
< c
->lsave_cnt
&& i
< *main_lebs
; i
++)
788 lsave
[i
] = c
->main_first
+ i
;
789 for (; i
< c
->lsave_cnt
; i
++)
790 lsave
[i
] = c
->main_first
;
792 ubifs_pack_lsave(c
, p
, lsave
);
797 /* Need to add LPT's own LEB properties table */
798 if (len
+ c
->ltab_sz
> c
->leb_size
) {
799 alen
= ALIGN(len
, c
->min_io_size
);
800 set_ltab(c
, lnum
, c
->leb_size
- alen
, alen
- len
);
801 memset(p
, 0xff, alen
- len
);
802 err
= ubifs_leb_change(c
, lnum
++, buf
, alen
);
812 /* Update ltab before packing it */
814 alen
= ALIGN(len
, c
->min_io_size
);
815 set_ltab(c
, lnum
, c
->leb_size
- alen
, alen
- len
);
817 ubifs_pack_ltab(c
, p
, ltab
);
820 /* Write remaining buffer */
821 memset(p
, 0xff, alen
- len
);
822 err
= ubifs_leb_change(c
, lnum
, buf
, alen
);
826 c
->nhead_lnum
= lnum
;
827 c
->nhead_offs
= ALIGN(len
, c
->min_io_size
);
829 dbg_lp("space_bits %d", c
->space_bits
);
830 dbg_lp("lpt_lnum_bits %d", c
->lpt_lnum_bits
);
831 dbg_lp("lpt_offs_bits %d", c
->lpt_offs_bits
);
832 dbg_lp("lpt_spc_bits %d", c
->lpt_spc_bits
);
833 dbg_lp("pcnt_bits %d", c
->pcnt_bits
);
834 dbg_lp("lnum_bits %d", c
->lnum_bits
);
835 dbg_lp("pnode_sz %d", c
->pnode_sz
);
836 dbg_lp("nnode_sz %d", c
->nnode_sz
);
837 dbg_lp("ltab_sz %d", c
->ltab_sz
);
838 dbg_lp("lsave_sz %d", c
->lsave_sz
);
839 dbg_lp("lsave_cnt %d", c
->lsave_cnt
);
840 dbg_lp("lpt_hght %d", c
->lpt_hght
);
841 dbg_lp("big_lpt %d", c
->big_lpt
);
842 dbg_lp("LPT root is at %d:%d", c
->lpt_lnum
, c
->lpt_offs
);
843 dbg_lp("LPT head is at %d:%d", c
->nhead_lnum
, c
->nhead_offs
);
844 dbg_lp("LPT ltab is at %d:%d", c
->ltab_lnum
, c
->ltab_offs
);
846 dbg_lp("LPT lsave is at %d:%d", c
->lsave_lnum
, c
->lsave_offs
);
858 * update_cats - add LEB properties of a pnode to LEB category lists and heaps.
859 * @c: UBIFS file-system description object
862 * When a pnode is loaded into memory, the LEB properties it contains are added,
863 * by this function, to the LEB category lists and heaps.
865 static void update_cats(struct ubifs_info
*c
, struct ubifs_pnode
*pnode
)
869 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
870 int cat
= pnode
->lprops
[i
].flags
& LPROPS_CAT_MASK
;
871 int lnum
= pnode
->lprops
[i
].lnum
;
875 ubifs_add_to_cat(c
, &pnode
->lprops
[i
], cat
);
880 * replace_cats - add LEB properties of a pnode to LEB category lists and heaps.
881 * @c: UBIFS file-system description object
882 * @old_pnode: pnode copied
883 * @new_pnode: pnode copy
885 * During commit it is sometimes necessary to copy a pnode
886 * (see dirty_cow_pnode). When that happens, references in
887 * category lists and heaps must be replaced. This function does that.
889 static void replace_cats(struct ubifs_info
*c
, struct ubifs_pnode
*old_pnode
,
890 struct ubifs_pnode
*new_pnode
)
894 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
895 if (!new_pnode
->lprops
[i
].lnum
)
897 ubifs_replace_cat(c
, &old_pnode
->lprops
[i
],
898 &new_pnode
->lprops
[i
]);
903 * check_lpt_crc - check LPT node crc is correct.
904 * @c: UBIFS file-system description object
905 * @buf: buffer containing node
906 * @len: length of node
908 * This function returns %0 on success and a negative error code on failure.
910 static int check_lpt_crc(const struct ubifs_info
*c
, void *buf
, int len
)
914 uint16_t crc
, calc_crc
;
916 crc
= ubifs_unpack_bits(&addr
, &pos
, UBIFS_LPT_CRC_BITS
);
917 calc_crc
= crc16(-1, buf
+ UBIFS_LPT_CRC_BYTES
,
918 len
- UBIFS_LPT_CRC_BYTES
);
919 if (crc
!= calc_crc
) {
920 ubifs_err(c
, "invalid crc in LPT node: crc %hx calc %hx",
929 * check_lpt_type - check LPT node type is correct.
930 * @c: UBIFS file-system description object
931 * @addr: address of type bit field is passed and returned updated here
932 * @pos: position of type bit field is passed and returned updated here
933 * @type: expected type
935 * This function returns %0 on success and a negative error code on failure.
937 static int check_lpt_type(const struct ubifs_info
*c
, uint8_t **addr
,
942 node_type
= ubifs_unpack_bits(addr
, pos
, UBIFS_LPT_TYPE_BITS
);
943 if (node_type
!= type
) {
944 ubifs_err(c
, "invalid type (%d) in LPT node type %d",
953 * unpack_pnode - unpack a pnode.
954 * @c: UBIFS file-system description object
955 * @buf: buffer containing packed pnode to unpack
956 * @pnode: pnode structure to fill
958 * This function returns %0 on success and a negative error code on failure.
960 static int unpack_pnode(const struct ubifs_info
*c
, void *buf
,
961 struct ubifs_pnode
*pnode
)
963 uint8_t *addr
= buf
+ UBIFS_LPT_CRC_BYTES
;
966 err
= check_lpt_type(c
, &addr
, &pos
, UBIFS_LPT_PNODE
);
970 pnode
->num
= ubifs_unpack_bits(&addr
, &pos
, c
->pcnt_bits
);
971 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
972 struct ubifs_lprops
* const lprops
= &pnode
->lprops
[i
];
974 lprops
->free
= ubifs_unpack_bits(&addr
, &pos
, c
->space_bits
);
976 lprops
->dirty
= ubifs_unpack_bits(&addr
, &pos
, c
->space_bits
);
979 if (ubifs_unpack_bits(&addr
, &pos
, 1))
980 lprops
->flags
= LPROPS_INDEX
;
983 lprops
->flags
|= ubifs_categorize_lprops(c
, lprops
);
985 err
= check_lpt_crc(c
, buf
, c
->pnode_sz
);
990 * ubifs_unpack_nnode - unpack a nnode.
991 * @c: UBIFS file-system description object
992 * @buf: buffer containing packed nnode to unpack
993 * @nnode: nnode structure to fill
995 * This function returns %0 on success and a negative error code on failure.
997 int ubifs_unpack_nnode(const struct ubifs_info
*c
, void *buf
,
998 struct ubifs_nnode
*nnode
)
1000 uint8_t *addr
= buf
+ UBIFS_LPT_CRC_BYTES
;
1001 int i
, pos
= 0, err
;
1003 err
= check_lpt_type(c
, &addr
, &pos
, UBIFS_LPT_NNODE
);
1007 nnode
->num
= ubifs_unpack_bits(&addr
, &pos
, c
->pcnt_bits
);
1008 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
1011 lnum
= ubifs_unpack_bits(&addr
, &pos
, c
->lpt_lnum_bits
) +
1013 if (lnum
== c
->lpt_last
+ 1)
1015 nnode
->nbranch
[i
].lnum
= lnum
;
1016 nnode
->nbranch
[i
].offs
= ubifs_unpack_bits(&addr
, &pos
,
1019 err
= check_lpt_crc(c
, buf
, c
->nnode_sz
);
1024 * unpack_ltab - unpack the LPT's own lprops table.
1025 * @c: UBIFS file-system description object
1026 * @buf: buffer from which to unpack
1028 * This function returns %0 on success and a negative error code on failure.
1030 static int unpack_ltab(const struct ubifs_info
*c
, void *buf
)
1032 uint8_t *addr
= buf
+ UBIFS_LPT_CRC_BYTES
;
1033 int i
, pos
= 0, err
;
1035 err
= check_lpt_type(c
, &addr
, &pos
, UBIFS_LPT_LTAB
);
1038 for (i
= 0; i
< c
->lpt_lebs
; i
++) {
1039 int free
= ubifs_unpack_bits(&addr
, &pos
, c
->lpt_spc_bits
);
1040 int dirty
= ubifs_unpack_bits(&addr
, &pos
, c
->lpt_spc_bits
);
1042 if (free
< 0 || free
> c
->leb_size
|| dirty
< 0 ||
1043 dirty
> c
->leb_size
|| free
+ dirty
> c
->leb_size
)
1046 c
->ltab
[i
].free
= free
;
1047 c
->ltab
[i
].dirty
= dirty
;
1051 err
= check_lpt_crc(c
, buf
, c
->ltab_sz
);
1057 * unpack_lsave - unpack the LPT's save table.
1058 * @c: UBIFS file-system description object
1059 * @buf: buffer from which to unpack
1061 * This function returns %0 on success and a negative error code on failure.
1063 static int unpack_lsave(const struct ubifs_info
*c
, void *buf
)
1065 uint8_t *addr
= buf
+ UBIFS_LPT_CRC_BYTES
;
1066 int i
, pos
= 0, err
;
1068 err
= check_lpt_type(c
, &addr
, &pos
, UBIFS_LPT_LSAVE
);
1071 for (i
= 0; i
< c
->lsave_cnt
; i
++) {
1072 int lnum
= ubifs_unpack_bits(&addr
, &pos
, c
->lnum_bits
);
1074 if (lnum
< c
->main_first
|| lnum
>= c
->leb_cnt
)
1078 err
= check_lpt_crc(c
, buf
, c
->lsave_sz
);
1084 * validate_nnode - validate a nnode.
1085 * @c: UBIFS file-system description object
1086 * @nnode: nnode to validate
1087 * @parent: parent nnode (or NULL for the root nnode)
1088 * @iip: index in parent
1090 * This function returns %0 on success and a negative error code on failure.
1092 static int validate_nnode(const struct ubifs_info
*c
, struct ubifs_nnode
*nnode
,
1093 struct ubifs_nnode
*parent
, int iip
)
1095 int i
, lvl
, max_offs
;
1098 int num
= calc_nnode_num_from_parent(c
, parent
, iip
);
1100 if (nnode
->num
!= num
)
1103 lvl
= parent
? parent
->level
- 1 : c
->lpt_hght
;
1107 max_offs
= c
->leb_size
- c
->pnode_sz
;
1109 max_offs
= c
->leb_size
- c
->nnode_sz
;
1110 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
1111 int lnum
= nnode
->nbranch
[i
].lnum
;
1112 int offs
= nnode
->nbranch
[i
].offs
;
1119 if (lnum
< c
->lpt_first
|| lnum
> c
->lpt_last
)
1121 if (offs
< 0 || offs
> max_offs
)
1128 * validate_pnode - validate a pnode.
1129 * @c: UBIFS file-system description object
1130 * @pnode: pnode to validate
1131 * @parent: parent nnode
1132 * @iip: index in parent
1134 * This function returns %0 on success and a negative error code on failure.
1136 static int validate_pnode(const struct ubifs_info
*c
, struct ubifs_pnode
*pnode
,
1137 struct ubifs_nnode
*parent
, int iip
)
1142 int num
= calc_pnode_num_from_parent(c
, parent
, iip
);
1144 if (pnode
->num
!= num
)
1147 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
1148 int free
= pnode
->lprops
[i
].free
;
1149 int dirty
= pnode
->lprops
[i
].dirty
;
1151 if (free
< 0 || free
> c
->leb_size
|| free
% c
->min_io_size
||
1154 if (dirty
< 0 || dirty
> c
->leb_size
|| (dirty
& 7))
1156 if (dirty
+ free
> c
->leb_size
)
1163 * set_pnode_lnum - set LEB numbers on a pnode.
1164 * @c: UBIFS file-system description object
1165 * @pnode: pnode to update
1167 * This function calculates the LEB numbers for the LEB properties it contains
1168 * based on the pnode number.
1170 static void set_pnode_lnum(const struct ubifs_info
*c
,
1171 struct ubifs_pnode
*pnode
)
1175 lnum
= (pnode
->num
<< UBIFS_LPT_FANOUT_SHIFT
) + c
->main_first
;
1176 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
1177 if (lnum
>= c
->leb_cnt
)
1179 pnode
->lprops
[i
].lnum
= lnum
++;
1184 * ubifs_read_nnode - read a nnode from flash and link it to the tree in memory.
1185 * @c: UBIFS file-system description object
1186 * @parent: parent nnode (or NULL for the root)
1187 * @iip: index in parent
1189 * This function returns %0 on success and a negative error code on failure.
1191 int ubifs_read_nnode(struct ubifs_info
*c
, struct ubifs_nnode
*parent
, int iip
)
1193 struct ubifs_nbranch
*branch
= NULL
;
1194 struct ubifs_nnode
*nnode
= NULL
;
1195 void *buf
= c
->lpt_nod_buf
;
1196 int err
, lnum
, offs
;
1199 branch
= &parent
->nbranch
[iip
];
1200 lnum
= branch
->lnum
;
1201 offs
= branch
->offs
;
1206 nnode
= kzalloc(sizeof(struct ubifs_nnode
), GFP_NOFS
);
1213 * This nnode was not written which just means that the LEB
1214 * properties in the subtree below it describe empty LEBs. We
1215 * make the nnode as though we had read it, which in fact means
1216 * doing almost nothing.
1219 nnode
->num
= calc_nnode_num_from_parent(c
, parent
, iip
);
1221 err
= ubifs_leb_read(c
, lnum
, buf
, offs
, c
->nnode_sz
, 1);
1224 err
= ubifs_unpack_nnode(c
, buf
, nnode
);
1228 err
= validate_nnode(c
, nnode
, parent
, iip
);
1232 nnode
->num
= calc_nnode_num_from_parent(c
, parent
, iip
);
1234 branch
->nnode
= nnode
;
1235 nnode
->level
= parent
->level
- 1;
1238 nnode
->level
= c
->lpt_hght
;
1240 nnode
->parent
= parent
;
1245 ubifs_err(c
, "error %d reading nnode at %d:%d", err
, lnum
, offs
);
1252 * read_pnode - read a pnode from flash and link it to the tree in memory.
1253 * @c: UBIFS file-system description object
1254 * @parent: parent nnode
1255 * @iip: index in parent
1257 * This function returns %0 on success and a negative error code on failure.
1259 static int read_pnode(struct ubifs_info
*c
, struct ubifs_nnode
*parent
, int iip
)
1261 struct ubifs_nbranch
*branch
;
1262 struct ubifs_pnode
*pnode
= NULL
;
1263 void *buf
= c
->lpt_nod_buf
;
1264 int err
, lnum
, offs
;
1266 branch
= &parent
->nbranch
[iip
];
1267 lnum
= branch
->lnum
;
1268 offs
= branch
->offs
;
1269 pnode
= kzalloc(sizeof(struct ubifs_pnode
), GFP_NOFS
);
1275 * This pnode was not written which just means that the LEB
1276 * properties in it describe empty LEBs. We make the pnode as
1277 * though we had read it.
1282 pnode
->num
= calc_pnode_num_from_parent(c
, parent
, iip
);
1283 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
1284 struct ubifs_lprops
* const lprops
= &pnode
->lprops
[i
];
1286 lprops
->free
= c
->leb_size
;
1287 lprops
->flags
= ubifs_categorize_lprops(c
, lprops
);
1290 err
= ubifs_leb_read(c
, lnum
, buf
, offs
, c
->pnode_sz
, 1);
1293 err
= unpack_pnode(c
, buf
, pnode
);
1297 err
= validate_pnode(c
, pnode
, parent
, iip
);
1301 pnode
->num
= calc_pnode_num_from_parent(c
, parent
, iip
);
1302 branch
->pnode
= pnode
;
1303 pnode
->parent
= parent
;
1305 set_pnode_lnum(c
, pnode
);
1306 c
->pnodes_have
+= 1;
1310 ubifs_err(c
, "error %d reading pnode at %d:%d", err
, lnum
, offs
);
1311 ubifs_dump_pnode(c
, pnode
, parent
, iip
);
1313 ubifs_err(c
, "calc num: %d", calc_pnode_num_from_parent(c
, parent
, iip
));
1319 * read_ltab - read LPT's own lprops table.
1320 * @c: UBIFS file-system description object
1322 * This function returns %0 on success and a negative error code on failure.
1324 static int read_ltab(struct ubifs_info
*c
)
1329 buf
= vmalloc(c
->ltab_sz
);
1332 err
= ubifs_leb_read(c
, c
->ltab_lnum
, buf
, c
->ltab_offs
, c
->ltab_sz
, 1);
1335 err
= unpack_ltab(c
, buf
);
1343 * read_lsave - read LPT's save table.
1344 * @c: UBIFS file-system description object
1346 * This function returns %0 on success and a negative error code on failure.
1348 static int read_lsave(struct ubifs_info
*c
)
1353 buf
= vmalloc(c
->lsave_sz
);
1356 err
= ubifs_leb_read(c
, c
->lsave_lnum
, buf
, c
->lsave_offs
,
1360 err
= unpack_lsave(c
, buf
);
1363 for (i
= 0; i
< c
->lsave_cnt
; i
++) {
1364 int lnum
= c
->lsave
[i
];
1365 struct ubifs_lprops
*lprops
;
1368 * Due to automatic resizing, the values in the lsave table
1369 * could be beyond the volume size - just ignore them.
1371 if (lnum
>= c
->leb_cnt
)
1373 lprops
= ubifs_lpt_lookup(c
, lnum
);
1374 if (IS_ERR(lprops
)) {
1375 err
= PTR_ERR(lprops
);
1386 * ubifs_get_nnode - get a nnode.
1387 * @c: UBIFS file-system description object
1388 * @parent: parent nnode (or NULL for the root)
1389 * @iip: index in parent
1391 * This function returns a pointer to the nnode on success or a negative error
1394 struct ubifs_nnode
*ubifs_get_nnode(struct ubifs_info
*c
,
1395 struct ubifs_nnode
*parent
, int iip
)
1397 struct ubifs_nbranch
*branch
;
1398 struct ubifs_nnode
*nnode
;
1401 branch
= &parent
->nbranch
[iip
];
1402 nnode
= branch
->nnode
;
1405 err
= ubifs_read_nnode(c
, parent
, iip
);
1407 return ERR_PTR(err
);
1408 return branch
->nnode
;
1412 * ubifs_get_pnode - get a pnode.
1413 * @c: UBIFS file-system description object
1414 * @parent: parent nnode
1415 * @iip: index in parent
1417 * This function returns a pointer to the pnode on success or a negative error
1420 struct ubifs_pnode
*ubifs_get_pnode(struct ubifs_info
*c
,
1421 struct ubifs_nnode
*parent
, int iip
)
1423 struct ubifs_nbranch
*branch
;
1424 struct ubifs_pnode
*pnode
;
1427 branch
= &parent
->nbranch
[iip
];
1428 pnode
= branch
->pnode
;
1431 err
= read_pnode(c
, parent
, iip
);
1433 return ERR_PTR(err
);
1434 update_cats(c
, branch
->pnode
);
1435 return branch
->pnode
;
1439 * ubifs_lpt_lookup - lookup LEB properties in the LPT.
1440 * @c: UBIFS file-system description object
1441 * @lnum: LEB number to lookup
1443 * This function returns a pointer to the LEB properties on success or a
1444 * negative error code on failure.
1446 struct ubifs_lprops
*ubifs_lpt_lookup(struct ubifs_info
*c
, int lnum
)
1448 int err
, i
, h
, iip
, shft
;
1449 struct ubifs_nnode
*nnode
;
1450 struct ubifs_pnode
*pnode
;
1453 err
= ubifs_read_nnode(c
, NULL
, 0);
1455 return ERR_PTR(err
);
1458 i
= lnum
- c
->main_first
;
1459 shft
= c
->lpt_hght
* UBIFS_LPT_FANOUT_SHIFT
;
1460 for (h
= 1; h
< c
->lpt_hght
; h
++) {
1461 iip
= ((i
>> shft
) & (UBIFS_LPT_FANOUT
- 1));
1462 shft
-= UBIFS_LPT_FANOUT_SHIFT
;
1463 nnode
= ubifs_get_nnode(c
, nnode
, iip
);
1465 return ERR_CAST(nnode
);
1467 iip
= ((i
>> shft
) & (UBIFS_LPT_FANOUT
- 1));
1468 pnode
= ubifs_get_pnode(c
, nnode
, iip
);
1470 return ERR_CAST(pnode
);
1471 iip
= (i
& (UBIFS_LPT_FANOUT
- 1));
1472 dbg_lp("LEB %d, free %d, dirty %d, flags %d", lnum
,
1473 pnode
->lprops
[iip
].free
, pnode
->lprops
[iip
].dirty
,
1474 pnode
->lprops
[iip
].flags
);
1475 return &pnode
->lprops
[iip
];
1479 * dirty_cow_nnode - ensure a nnode is not being committed.
1480 * @c: UBIFS file-system description object
1481 * @nnode: nnode to check
1483 * Returns dirtied nnode on success or negative error code on failure.
1485 static struct ubifs_nnode
*dirty_cow_nnode(struct ubifs_info
*c
,
1486 struct ubifs_nnode
*nnode
)
1488 struct ubifs_nnode
*n
;
1491 if (!test_bit(COW_CNODE
, &nnode
->flags
)) {
1492 /* nnode is not being committed */
1493 if (!test_and_set_bit(DIRTY_CNODE
, &nnode
->flags
)) {
1494 c
->dirty_nn_cnt
+= 1;
1495 ubifs_add_nnode_dirt(c
, nnode
);
1500 /* nnode is being committed, so copy it */
1501 n
= kmalloc(sizeof(struct ubifs_nnode
), GFP_NOFS
);
1503 return ERR_PTR(-ENOMEM
);
1505 memcpy(n
, nnode
, sizeof(struct ubifs_nnode
));
1507 __set_bit(DIRTY_CNODE
, &n
->flags
);
1508 __clear_bit(COW_CNODE
, &n
->flags
);
1510 /* The children now have new parent */
1511 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
1512 struct ubifs_nbranch
*branch
= &n
->nbranch
[i
];
1515 branch
->cnode
->parent
= n
;
1518 ubifs_assert(!test_bit(OBSOLETE_CNODE
, &nnode
->flags
));
1519 __set_bit(OBSOLETE_CNODE
, &nnode
->flags
);
1521 c
->dirty_nn_cnt
+= 1;
1522 ubifs_add_nnode_dirt(c
, nnode
);
1524 nnode
->parent
->nbranch
[n
->iip
].nnode
= n
;
1531 * dirty_cow_pnode - ensure a pnode is not being committed.
1532 * @c: UBIFS file-system description object
1533 * @pnode: pnode to check
1535 * Returns dirtied pnode on success or negative error code on failure.
1537 static struct ubifs_pnode
*dirty_cow_pnode(struct ubifs_info
*c
,
1538 struct ubifs_pnode
*pnode
)
1540 struct ubifs_pnode
*p
;
1542 if (!test_bit(COW_CNODE
, &pnode
->flags
)) {
1543 /* pnode is not being committed */
1544 if (!test_and_set_bit(DIRTY_CNODE
, &pnode
->flags
)) {
1545 c
->dirty_pn_cnt
+= 1;
1546 add_pnode_dirt(c
, pnode
);
1551 /* pnode is being committed, so copy it */
1552 p
= kmalloc(sizeof(struct ubifs_pnode
), GFP_NOFS
);
1554 return ERR_PTR(-ENOMEM
);
1556 memcpy(p
, pnode
, sizeof(struct ubifs_pnode
));
1558 __set_bit(DIRTY_CNODE
, &p
->flags
);
1559 __clear_bit(COW_CNODE
, &p
->flags
);
1560 replace_cats(c
, pnode
, p
);
1562 ubifs_assert(!test_bit(OBSOLETE_CNODE
, &pnode
->flags
));
1563 __set_bit(OBSOLETE_CNODE
, &pnode
->flags
);
1565 c
->dirty_pn_cnt
+= 1;
1566 add_pnode_dirt(c
, pnode
);
1567 pnode
->parent
->nbranch
[p
->iip
].pnode
= p
;
1572 * ubifs_lpt_lookup_dirty - lookup LEB properties in the LPT.
1573 * @c: UBIFS file-system description object
1574 * @lnum: LEB number to lookup
1576 * This function returns a pointer to the LEB properties on success or a
1577 * negative error code on failure.
1579 struct ubifs_lprops
*ubifs_lpt_lookup_dirty(struct ubifs_info
*c
, int lnum
)
1581 int err
, i
, h
, iip
, shft
;
1582 struct ubifs_nnode
*nnode
;
1583 struct ubifs_pnode
*pnode
;
1586 err
= ubifs_read_nnode(c
, NULL
, 0);
1588 return ERR_PTR(err
);
1591 nnode
= dirty_cow_nnode(c
, nnode
);
1593 return ERR_CAST(nnode
);
1594 i
= lnum
- c
->main_first
;
1595 shft
= c
->lpt_hght
* UBIFS_LPT_FANOUT_SHIFT
;
1596 for (h
= 1; h
< c
->lpt_hght
; h
++) {
1597 iip
= ((i
>> shft
) & (UBIFS_LPT_FANOUT
- 1));
1598 shft
-= UBIFS_LPT_FANOUT_SHIFT
;
1599 nnode
= ubifs_get_nnode(c
, nnode
, iip
);
1601 return ERR_CAST(nnode
);
1602 nnode
= dirty_cow_nnode(c
, nnode
);
1604 return ERR_CAST(nnode
);
1606 iip
= ((i
>> shft
) & (UBIFS_LPT_FANOUT
- 1));
1607 pnode
= ubifs_get_pnode(c
, nnode
, iip
);
1609 return ERR_CAST(pnode
);
1610 pnode
= dirty_cow_pnode(c
, pnode
);
1612 return ERR_CAST(pnode
);
1613 iip
= (i
& (UBIFS_LPT_FANOUT
- 1));
1614 dbg_lp("LEB %d, free %d, dirty %d, flags %d", lnum
,
1615 pnode
->lprops
[iip
].free
, pnode
->lprops
[iip
].dirty
,
1616 pnode
->lprops
[iip
].flags
);
1617 ubifs_assert(test_bit(DIRTY_CNODE
, &pnode
->flags
));
1618 return &pnode
->lprops
[iip
];
1622 * lpt_init_rd - initialize the LPT for reading.
1623 * @c: UBIFS file-system description object
1625 * This function returns %0 on success and a negative error code on failure.
1627 static int lpt_init_rd(struct ubifs_info
*c
)
1631 c
->ltab
= vmalloc(sizeof(struct ubifs_lpt_lprops
) * c
->lpt_lebs
);
1635 i
= max_t(int, c
->nnode_sz
, c
->pnode_sz
);
1636 c
->lpt_nod_buf
= kmalloc(i
, GFP_KERNEL
);
1637 if (!c
->lpt_nod_buf
)
1640 for (i
= 0; i
< LPROPS_HEAP_CNT
; i
++) {
1641 c
->lpt_heap
[i
].arr
= kmalloc(sizeof(void *) * LPT_HEAP_SZ
,
1643 if (!c
->lpt_heap
[i
].arr
)
1645 c
->lpt_heap
[i
].cnt
= 0;
1646 c
->lpt_heap
[i
].max_cnt
= LPT_HEAP_SZ
;
1649 c
->dirty_idx
.arr
= kmalloc(sizeof(void *) * LPT_HEAP_SZ
, GFP_KERNEL
);
1650 if (!c
->dirty_idx
.arr
)
1652 c
->dirty_idx
.cnt
= 0;
1653 c
->dirty_idx
.max_cnt
= LPT_HEAP_SZ
;
1659 dbg_lp("space_bits %d", c
->space_bits
);
1660 dbg_lp("lpt_lnum_bits %d", c
->lpt_lnum_bits
);
1661 dbg_lp("lpt_offs_bits %d", c
->lpt_offs_bits
);
1662 dbg_lp("lpt_spc_bits %d", c
->lpt_spc_bits
);
1663 dbg_lp("pcnt_bits %d", c
->pcnt_bits
);
1664 dbg_lp("lnum_bits %d", c
->lnum_bits
);
1665 dbg_lp("pnode_sz %d", c
->pnode_sz
);
1666 dbg_lp("nnode_sz %d", c
->nnode_sz
);
1667 dbg_lp("ltab_sz %d", c
->ltab_sz
);
1668 dbg_lp("lsave_sz %d", c
->lsave_sz
);
1669 dbg_lp("lsave_cnt %d", c
->lsave_cnt
);
1670 dbg_lp("lpt_hght %d", c
->lpt_hght
);
1671 dbg_lp("big_lpt %d", c
->big_lpt
);
1672 dbg_lp("LPT root is at %d:%d", c
->lpt_lnum
, c
->lpt_offs
);
1673 dbg_lp("LPT head is at %d:%d", c
->nhead_lnum
, c
->nhead_offs
);
1674 dbg_lp("LPT ltab is at %d:%d", c
->ltab_lnum
, c
->ltab_offs
);
1676 dbg_lp("LPT lsave is at %d:%d", c
->lsave_lnum
, c
->lsave_offs
);
1683 * lpt_init_wr - initialize the LPT for writing.
1684 * @c: UBIFS file-system description object
1686 * 'lpt_init_rd()' must have been called already.
1688 * This function returns %0 on success and a negative error code on failure.
1690 static int lpt_init_wr(struct ubifs_info
*c
)
1694 c
->ltab_cmt
= vmalloc(sizeof(struct ubifs_lpt_lprops
) * c
->lpt_lebs
);
1698 c
->lpt_buf
= vmalloc(c
->leb_size
);
1703 c
->lsave
= kmalloc(sizeof(int) * c
->lsave_cnt
, GFP_NOFS
);
1706 err
= read_lsave(c
);
1711 for (i
= 0; i
< c
->lpt_lebs
; i
++)
1712 if (c
->ltab
[i
].free
== c
->leb_size
) {
1713 err
= ubifs_leb_unmap(c
, i
+ c
->lpt_first
);
1723 * ubifs_lpt_init - initialize the LPT.
1724 * @c: UBIFS file-system description object
1725 * @rd: whether to initialize lpt for reading
1726 * @wr: whether to initialize lpt for writing
1728 * For mounting 'rw', @rd and @wr are both true. For mounting 'ro', @rd is true
1729 * and @wr is false. For mounting from 'ro' to 'rw', @rd is false and @wr is
1732 * This function returns %0 on success and a negative error code on failure.
1734 int ubifs_lpt_init(struct ubifs_info
*c
, int rd
, int wr
)
1739 err
= lpt_init_rd(c
);
1746 err
= lpt_init_wr(c
);
1757 ubifs_lpt_free(c
, 1);
1760 ubifs_lpt_free(c
, 0);
1765 * struct lpt_scan_node - somewhere to put nodes while we scan LPT.
1766 * @nnode: where to keep a nnode
1767 * @pnode: where to keep a pnode
1768 * @cnode: where to keep a cnode
1769 * @in_tree: is the node in the tree in memory
1770 * @ptr.nnode: pointer to the nnode (if it is an nnode) which may be here or in
1772 * @ptr.pnode: ditto for pnode
1773 * @ptr.cnode: ditto for cnode
1775 struct lpt_scan_node
{
1777 struct ubifs_nnode nnode
;
1778 struct ubifs_pnode pnode
;
1779 struct ubifs_cnode cnode
;
1783 struct ubifs_nnode
*nnode
;
1784 struct ubifs_pnode
*pnode
;
1785 struct ubifs_cnode
*cnode
;
1790 * scan_get_nnode - for the scan, get a nnode from either the tree or flash.
1791 * @c: the UBIFS file-system description object
1792 * @path: where to put the nnode
1793 * @parent: parent of the nnode
1794 * @iip: index in parent of the nnode
1796 * This function returns a pointer to the nnode on success or a negative error
1799 static struct ubifs_nnode
*scan_get_nnode(struct ubifs_info
*c
,
1800 struct lpt_scan_node
*path
,
1801 struct ubifs_nnode
*parent
, int iip
)
1803 struct ubifs_nbranch
*branch
;
1804 struct ubifs_nnode
*nnode
;
1805 void *buf
= c
->lpt_nod_buf
;
1808 branch
= &parent
->nbranch
[iip
];
1809 nnode
= branch
->nnode
;
1812 path
->ptr
.nnode
= nnode
;
1815 nnode
= &path
->nnode
;
1817 path
->ptr
.nnode
= nnode
;
1818 memset(nnode
, 0, sizeof(struct ubifs_nnode
));
1819 if (branch
->lnum
== 0) {
1821 * This nnode was not written which just means that the LEB
1822 * properties in the subtree below it describe empty LEBs. We
1823 * make the nnode as though we had read it, which in fact means
1824 * doing almost nothing.
1827 nnode
->num
= calc_nnode_num_from_parent(c
, parent
, iip
);
1829 err
= ubifs_leb_read(c
, branch
->lnum
, buf
, branch
->offs
,
1832 return ERR_PTR(err
);
1833 err
= ubifs_unpack_nnode(c
, buf
, nnode
);
1835 return ERR_PTR(err
);
1837 err
= validate_nnode(c
, nnode
, parent
, iip
);
1839 return ERR_PTR(err
);
1841 nnode
->num
= calc_nnode_num_from_parent(c
, parent
, iip
);
1842 nnode
->level
= parent
->level
- 1;
1843 nnode
->parent
= parent
;
1849 * scan_get_pnode - for the scan, get a pnode from either the tree or flash.
1850 * @c: the UBIFS file-system description object
1851 * @path: where to put the pnode
1852 * @parent: parent of the pnode
1853 * @iip: index in parent of the pnode
1855 * This function returns a pointer to the pnode on success or a negative error
1858 static struct ubifs_pnode
*scan_get_pnode(struct ubifs_info
*c
,
1859 struct lpt_scan_node
*path
,
1860 struct ubifs_nnode
*parent
, int iip
)
1862 struct ubifs_nbranch
*branch
;
1863 struct ubifs_pnode
*pnode
;
1864 void *buf
= c
->lpt_nod_buf
;
1867 branch
= &parent
->nbranch
[iip
];
1868 pnode
= branch
->pnode
;
1871 path
->ptr
.pnode
= pnode
;
1874 pnode
= &path
->pnode
;
1876 path
->ptr
.pnode
= pnode
;
1877 memset(pnode
, 0, sizeof(struct ubifs_pnode
));
1878 if (branch
->lnum
== 0) {
1880 * This pnode was not written which just means that the LEB
1881 * properties in it describe empty LEBs. We make the pnode as
1882 * though we had read it.
1887 pnode
->num
= calc_pnode_num_from_parent(c
, parent
, iip
);
1888 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
1889 struct ubifs_lprops
* const lprops
= &pnode
->lprops
[i
];
1891 lprops
->free
= c
->leb_size
;
1892 lprops
->flags
= ubifs_categorize_lprops(c
, lprops
);
1895 ubifs_assert(branch
->lnum
>= c
->lpt_first
&&
1896 branch
->lnum
<= c
->lpt_last
);
1897 ubifs_assert(branch
->offs
>= 0 && branch
->offs
< c
->leb_size
);
1898 err
= ubifs_leb_read(c
, branch
->lnum
, buf
, branch
->offs
,
1901 return ERR_PTR(err
);
1902 err
= unpack_pnode(c
, buf
, pnode
);
1904 return ERR_PTR(err
);
1906 err
= validate_pnode(c
, pnode
, parent
, iip
);
1908 return ERR_PTR(err
);
1910 pnode
->num
= calc_pnode_num_from_parent(c
, parent
, iip
);
1911 pnode
->parent
= parent
;
1913 set_pnode_lnum(c
, pnode
);
1918 * ubifs_lpt_scan_nolock - scan the LPT.
1919 * @c: the UBIFS file-system description object
1920 * @start_lnum: LEB number from which to start scanning
1921 * @end_lnum: LEB number at which to stop scanning
1922 * @scan_cb: callback function called for each lprops
1923 * @data: data to be passed to the callback function
1925 * This function returns %0 on success and a negative error code on failure.
1927 int ubifs_lpt_scan_nolock(struct ubifs_info
*c
, int start_lnum
, int end_lnum
,
1928 ubifs_lpt_scan_callback scan_cb
, void *data
)
1930 int err
= 0, i
, h
, iip
, shft
;
1931 struct ubifs_nnode
*nnode
;
1932 struct ubifs_pnode
*pnode
;
1933 struct lpt_scan_node
*path
;
1935 if (start_lnum
== -1) {
1936 start_lnum
= end_lnum
+ 1;
1937 if (start_lnum
>= c
->leb_cnt
)
1938 start_lnum
= c
->main_first
;
1941 ubifs_assert(start_lnum
>= c
->main_first
&& start_lnum
< c
->leb_cnt
);
1942 ubifs_assert(end_lnum
>= c
->main_first
&& end_lnum
< c
->leb_cnt
);
1945 err
= ubifs_read_nnode(c
, NULL
, 0);
1950 path
= kmalloc(sizeof(struct lpt_scan_node
) * (c
->lpt_hght
+ 1),
1955 path
[0].ptr
.nnode
= c
->nroot
;
1956 path
[0].in_tree
= 1;
1958 /* Descend to the pnode containing start_lnum */
1960 i
= start_lnum
- c
->main_first
;
1961 shft
= c
->lpt_hght
* UBIFS_LPT_FANOUT_SHIFT
;
1962 for (h
= 1; h
< c
->lpt_hght
; h
++) {
1963 iip
= ((i
>> shft
) & (UBIFS_LPT_FANOUT
- 1));
1964 shft
-= UBIFS_LPT_FANOUT_SHIFT
;
1965 nnode
= scan_get_nnode(c
, path
+ h
, nnode
, iip
);
1966 if (IS_ERR(nnode
)) {
1967 err
= PTR_ERR(nnode
);
1971 iip
= ((i
>> shft
) & (UBIFS_LPT_FANOUT
- 1));
1972 pnode
= scan_get_pnode(c
, path
+ h
, nnode
, iip
);
1973 if (IS_ERR(pnode
)) {
1974 err
= PTR_ERR(pnode
);
1977 iip
= (i
& (UBIFS_LPT_FANOUT
- 1));
1979 /* Loop for each lprops */
1981 struct ubifs_lprops
*lprops
= &pnode
->lprops
[iip
];
1982 int ret
, lnum
= lprops
->lnum
;
1984 ret
= scan_cb(c
, lprops
, path
[h
].in_tree
, data
);
1989 if (ret
& LPT_SCAN_ADD
) {
1990 /* Add all the nodes in path to the tree in memory */
1991 for (h
= 1; h
< c
->lpt_hght
; h
++) {
1992 const size_t sz
= sizeof(struct ubifs_nnode
);
1993 struct ubifs_nnode
*parent
;
1995 if (path
[h
].in_tree
)
1997 nnode
= kmemdup(&path
[h
].nnode
, sz
, GFP_NOFS
);
2002 parent
= nnode
->parent
;
2003 parent
->nbranch
[nnode
->iip
].nnode
= nnode
;
2004 path
[h
].ptr
.nnode
= nnode
;
2005 path
[h
].in_tree
= 1;
2006 path
[h
+ 1].cnode
.parent
= nnode
;
2008 if (path
[h
].in_tree
)
2009 ubifs_ensure_cat(c
, lprops
);
2011 const size_t sz
= sizeof(struct ubifs_pnode
);
2012 struct ubifs_nnode
*parent
;
2014 pnode
= kmemdup(&path
[h
].pnode
, sz
, GFP_NOFS
);
2019 parent
= pnode
->parent
;
2020 parent
->nbranch
[pnode
->iip
].pnode
= pnode
;
2021 path
[h
].ptr
.pnode
= pnode
;
2022 path
[h
].in_tree
= 1;
2023 update_cats(c
, pnode
);
2024 c
->pnodes_have
+= 1;
2026 err
= dbg_check_lpt_nodes(c
, (struct ubifs_cnode
*)
2030 err
= dbg_check_cats(c
);
2034 if (ret
& LPT_SCAN_STOP
) {
2038 /* Get the next lprops */
2039 if (lnum
== end_lnum
) {
2041 * We got to the end without finding what we were
2047 if (lnum
+ 1 >= c
->leb_cnt
) {
2048 /* Wrap-around to the beginning */
2049 start_lnum
= c
->main_first
;
2052 if (iip
+ 1 < UBIFS_LPT_FANOUT
) {
2053 /* Next lprops is in the same pnode */
2057 /* We need to get the next pnode. Go up until we can go right */
2061 ubifs_assert(h
>= 0);
2062 nnode
= path
[h
].ptr
.nnode
;
2063 if (iip
+ 1 < UBIFS_LPT_FANOUT
)
2069 /* Descend to the pnode */
2071 for (; h
< c
->lpt_hght
; h
++) {
2072 nnode
= scan_get_nnode(c
, path
+ h
, nnode
, iip
);
2073 if (IS_ERR(nnode
)) {
2074 err
= PTR_ERR(nnode
);
2079 pnode
= scan_get_pnode(c
, path
+ h
, nnode
, iip
);
2080 if (IS_ERR(pnode
)) {
2081 err
= PTR_ERR(pnode
);
2092 * dbg_chk_pnode - check a pnode.
2093 * @c: the UBIFS file-system description object
2094 * @pnode: pnode to check
2095 * @col: pnode column
2097 * This function returns %0 on success and a negative error code on failure.
2099 static int dbg_chk_pnode(struct ubifs_info
*c
, struct ubifs_pnode
*pnode
,
2104 if (pnode
->num
!= col
) {
2105 ubifs_err(c
, "pnode num %d expected %d parent num %d iip %d",
2106 pnode
->num
, col
, pnode
->parent
->num
, pnode
->iip
);
2109 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
2110 struct ubifs_lprops
*lp
, *lprops
= &pnode
->lprops
[i
];
2111 int lnum
= (pnode
->num
<< UBIFS_LPT_FANOUT_SHIFT
) + i
+
2113 int found
, cat
= lprops
->flags
& LPROPS_CAT_MASK
;
2114 struct ubifs_lpt_heap
*heap
;
2115 struct list_head
*list
= NULL
;
2117 if (lnum
>= c
->leb_cnt
)
2119 if (lprops
->lnum
!= lnum
) {
2120 ubifs_err(c
, "bad LEB number %d expected %d",
2121 lprops
->lnum
, lnum
);
2124 if (lprops
->flags
& LPROPS_TAKEN
) {
2125 if (cat
!= LPROPS_UNCAT
) {
2126 ubifs_err(c
, "LEB %d taken but not uncat %d",
2132 if (lprops
->flags
& LPROPS_INDEX
) {
2135 case LPROPS_DIRTY_IDX
:
2136 case LPROPS_FRDI_IDX
:
2139 ubifs_err(c
, "LEB %d index but cat %d",
2149 case LPROPS_FREEABLE
:
2152 ubifs_err(c
, "LEB %d not index but cat %d",
2159 list
= &c
->uncat_list
;
2162 list
= &c
->empty_list
;
2164 case LPROPS_FREEABLE
:
2165 list
= &c
->freeable_list
;
2167 case LPROPS_FRDI_IDX
:
2168 list
= &c
->frdi_idx_list
;
2174 case LPROPS_DIRTY_IDX
:
2176 heap
= &c
->lpt_heap
[cat
- 1];
2177 if (lprops
->hpos
< heap
->cnt
&&
2178 heap
->arr
[lprops
->hpos
] == lprops
)
2183 case LPROPS_FREEABLE
:
2184 case LPROPS_FRDI_IDX
:
2185 list_for_each_entry(lp
, list
, list
)
2193 ubifs_err(c
, "LEB %d cat %d not found in cat heap/list",
2199 if (lprops
->free
!= c
->leb_size
) {
2200 ubifs_err(c
, "LEB %d cat %d free %d dirty %d",
2201 lprops
->lnum
, cat
, lprops
->free
,
2206 case LPROPS_FREEABLE
:
2207 case LPROPS_FRDI_IDX
:
2208 if (lprops
->free
+ lprops
->dirty
!= c
->leb_size
) {
2209 ubifs_err(c
, "LEB %d cat %d free %d dirty %d",
2210 lprops
->lnum
, cat
, lprops
->free
,
2221 * dbg_check_lpt_nodes - check nnodes and pnodes.
2222 * @c: the UBIFS file-system description object
2223 * @cnode: next cnode (nnode or pnode) to check
2224 * @row: row of cnode (root is zero)
2225 * @col: column of cnode (leftmost is zero)
2227 * This function returns %0 on success and a negative error code on failure.
2229 int dbg_check_lpt_nodes(struct ubifs_info
*c
, struct ubifs_cnode
*cnode
,
2232 struct ubifs_nnode
*nnode
, *nn
;
2233 struct ubifs_cnode
*cn
;
2234 int num
, iip
= 0, err
;
2236 if (!dbg_is_chk_lprops(c
))
2240 ubifs_assert(row
>= 0);
2241 nnode
= cnode
->parent
;
2243 /* cnode is a nnode */
2244 num
= calc_nnode_num(row
, col
);
2245 if (cnode
->num
!= num
) {
2246 ubifs_err(c
, "nnode num %d expected %d parent num %d iip %d",
2248 (nnode
? nnode
->num
: 0), cnode
->iip
);
2251 nn
= (struct ubifs_nnode
*)cnode
;
2252 while (iip
< UBIFS_LPT_FANOUT
) {
2253 cn
= nn
->nbranch
[iip
].cnode
;
2257 col
<<= UBIFS_LPT_FANOUT_SHIFT
;
2266 if (iip
< UBIFS_LPT_FANOUT
)
2269 struct ubifs_pnode
*pnode
;
2271 /* cnode is a pnode */
2272 pnode
= (struct ubifs_pnode
*)cnode
;
2273 err
= dbg_chk_pnode(c
, pnode
, col
);
2277 /* Go up and to the right */
2279 col
>>= UBIFS_LPT_FANOUT_SHIFT
;
2280 iip
= cnode
->iip
+ 1;
2281 cnode
= (struct ubifs_cnode
*)nnode
;