2 * This file is part of UBIFS.
4 * Copyright (C) 2006-2008 Nokia Corporation.
6 * This program is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License version 2 as published by
8 * the Free Software Foundation.
10 * This program is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
15 * You should have received a copy of the GNU General Public License along with
16 * this program; if not, write to the Free Software Foundation, Inc., 51
17 * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 * Authors: Adrian Hunter
20 * Artem Bityutskiy (Битюцкий Артём)
24 * This file implements the LEB properties tree (LPT) area. The LPT area
25 * contains the LEB properties tree, a table of LPT area eraseblocks (ltab), and
26 * (for the "big" model) a table of saved LEB numbers (lsave). The LPT area sits
27 * between the log and the orphan area.
29 * The LPT area is like a miniature self-contained file system. It is required
30 * that it never runs out of space, is fast to access and update, and scales
31 * logarithmically. The LEB properties tree is implemented as a wandering tree
32 * much like the TNC, and the LPT area has its own garbage collection.
34 * The LPT has two slightly different forms called the "small model" and the
35 * "big model". The small model is used when the entire LEB properties table
36 * can be written into a single eraseblock. In that case, garbage collection
37 * consists of just writing the whole table, which therefore makes all other
38 * eraseblocks reusable. In the case of the big model, dirty eraseblocks are
39 * selected for garbage collection, which consists are marking the nodes in
40 * that LEB as dirty, and then only the dirty nodes are written out. Also, in
41 * the case of the big model, a table of LEB numbers is saved so that the entire
42 * LPT does not to be scanned looking for empty eraseblocks when UBIFS is first
46 #include <linux/crc16.h>
50 * do_calc_lpt_geom - calculate sizes for the LPT area.
51 * @c: the UBIFS file-system description object
53 * Calculate the sizes of LPT bit fields, nodes, and tree, based on the
54 * properties of the flash and whether LPT is "big" (c->big_lpt).
56 static void do_calc_lpt_geom(struct ubifs_info
*c
)
58 int i
, n
, bits
, per_leb_wastage
, max_pnode_cnt
;
59 long long sz
, tot_wastage
;
61 n
= c
->main_lebs
+ c
->max_leb_cnt
- c
->leb_cnt
;
62 max_pnode_cnt
= DIV_ROUND_UP(n
, UBIFS_LPT_FANOUT
);
66 while (n
< max_pnode_cnt
) {
68 n
<<= UBIFS_LPT_FANOUT_SHIFT
;
71 c
->pnode_cnt
= DIV_ROUND_UP(c
->main_lebs
, UBIFS_LPT_FANOUT
);
73 n
= DIV_ROUND_UP(c
->pnode_cnt
, UBIFS_LPT_FANOUT
);
75 for (i
= 1; i
< c
->lpt_hght
; i
++) {
76 n
= DIV_ROUND_UP(n
, UBIFS_LPT_FANOUT
);
80 c
->space_bits
= fls(c
->leb_size
) - 3;
81 c
->lpt_lnum_bits
= fls(c
->lpt_lebs
);
82 c
->lpt_offs_bits
= fls(c
->leb_size
- 1);
83 c
->lpt_spc_bits
= fls(c
->leb_size
);
85 n
= DIV_ROUND_UP(c
->max_leb_cnt
, UBIFS_LPT_FANOUT
);
86 c
->pcnt_bits
= fls(n
- 1);
88 c
->lnum_bits
= fls(c
->max_leb_cnt
- 1);
90 bits
= UBIFS_LPT_CRC_BITS
+ UBIFS_LPT_TYPE_BITS
+
91 (c
->big_lpt
? c
->pcnt_bits
: 0) +
92 (c
->space_bits
* 2 + 1) * UBIFS_LPT_FANOUT
;
93 c
->pnode_sz
= (bits
+ 7) / 8;
95 bits
= UBIFS_LPT_CRC_BITS
+ UBIFS_LPT_TYPE_BITS
+
96 (c
->big_lpt
? c
->pcnt_bits
: 0) +
97 (c
->lpt_lnum_bits
+ c
->lpt_offs_bits
) * UBIFS_LPT_FANOUT
;
98 c
->nnode_sz
= (bits
+ 7) / 8;
100 bits
= UBIFS_LPT_CRC_BITS
+ UBIFS_LPT_TYPE_BITS
+
101 c
->lpt_lebs
* c
->lpt_spc_bits
* 2;
102 c
->ltab_sz
= (bits
+ 7) / 8;
104 bits
= UBIFS_LPT_CRC_BITS
+ UBIFS_LPT_TYPE_BITS
+
105 c
->lnum_bits
* c
->lsave_cnt
;
106 c
->lsave_sz
= (bits
+ 7) / 8;
108 /* Calculate the minimum LPT size */
109 c
->lpt_sz
= (long long)c
->pnode_cnt
* c
->pnode_sz
;
110 c
->lpt_sz
+= (long long)c
->nnode_cnt
* c
->nnode_sz
;
111 c
->lpt_sz
+= c
->ltab_sz
;
113 c
->lpt_sz
+= c
->lsave_sz
;
117 per_leb_wastage
= max_t(int, c
->pnode_sz
, c
->nnode_sz
);
118 sz
+= per_leb_wastage
;
119 tot_wastage
= per_leb_wastage
;
120 while (sz
> c
->leb_size
) {
121 sz
+= per_leb_wastage
;
123 tot_wastage
+= per_leb_wastage
;
125 tot_wastage
+= ALIGN(sz
, c
->min_io_size
) - sz
;
126 c
->lpt_sz
+= tot_wastage
;
130 * ubifs_calc_lpt_geom - calculate and check sizes for the LPT area.
131 * @c: the UBIFS file-system description object
133 * This function returns %0 on success and a negative error code on failure.
135 int ubifs_calc_lpt_geom(struct ubifs_info
*c
)
142 /* Verify that lpt_lebs is big enough */
143 sz
= c
->lpt_sz
* 2; /* Must have at least 2 times the size */
144 sz
+= c
->leb_size
- 1;
145 do_div(sz
, c
->leb_size
);
147 if (lebs_needed
> c
->lpt_lebs
) {
148 ubifs_err("too few LPT LEBs");
152 /* Verify that ltab fits in a single LEB (since ltab is a single node */
153 if (c
->ltab_sz
> c
->leb_size
) {
154 ubifs_err("LPT ltab too big");
158 c
->check_lpt_free
= c
->big_lpt
;
164 * calc_dflt_lpt_geom - calculate default LPT geometry.
165 * @c: the UBIFS file-system description object
166 * @main_lebs: number of main area LEBs is passed and returned here
167 * @big_lpt: whether the LPT area is "big" is returned here
169 * The size of the LPT area depends on parameters that themselves are dependent
170 * on the size of the LPT area. This function, successively recalculates the LPT
171 * area geometry until the parameters and resultant geometry are consistent.
173 * This function returns %0 on success and a negative error code on failure.
175 static int calc_dflt_lpt_geom(struct ubifs_info
*c
, int *main_lebs
,
181 /* Start by assuming the minimum number of LPT LEBs */
182 c
->lpt_lebs
= UBIFS_MIN_LPT_LEBS
;
183 c
->main_lebs
= *main_lebs
- c
->lpt_lebs
;
184 if (c
->main_lebs
<= 0)
187 /* And assume we will use the small LPT model */
191 * Calculate the geometry based on assumptions above and then see if it
196 /* Small LPT model must have lpt_sz < leb_size */
197 if (c
->lpt_sz
> c
->leb_size
) {
198 /* Nope, so try again using big LPT model */
203 /* Now check there are enough LPT LEBs */
204 for (i
= 0; i
< 64 ; i
++) {
205 sz
= c
->lpt_sz
* 4; /* Allow 4 times the size */
206 sz
+= c
->leb_size
- 1;
207 do_div(sz
, c
->leb_size
);
209 if (lebs_needed
> c
->lpt_lebs
) {
210 /* Not enough LPT LEBs so try again with more */
211 c
->lpt_lebs
= lebs_needed
;
212 c
->main_lebs
= *main_lebs
- c
->lpt_lebs
;
213 if (c
->main_lebs
<= 0)
218 if (c
->ltab_sz
> c
->leb_size
) {
219 ubifs_err("LPT ltab too big");
222 *main_lebs
= c
->main_lebs
;
223 *big_lpt
= c
->big_lpt
;
230 * pack_bits - pack bit fields end-to-end.
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)
236 static void pack_bits(uint8_t **addr
, int *pos
, uint32_t val
, int nrbits
)
241 ubifs_assert(nrbits
> 0);
242 ubifs_assert(nrbits
<= 32);
243 ubifs_assert(*pos
>= 0);
244 ubifs_assert(*pos
< 8);
245 ubifs_assert((val
>> nrbits
) == 0 || nrbits
== 32);
247 *p
|= ((uint8_t)val
) << b
;
250 *++p
= (uint8_t)(val
>>= (8 - b
));
252 *++p
= (uint8_t)(val
>>= 8);
254 *++p
= (uint8_t)(val
>>= 8);
256 *++p
= (uint8_t)(val
>>= 8);
263 *++p
= (uint8_t)(val
>>= 8);
265 *++p
= (uint8_t)(val
>>= 8);
267 *++p
= (uint8_t)(val
>>= 8);
279 * ubifs_unpack_bits - unpack bit fields.
280 * @addr: address at which to unpack (passed and next address returned)
281 * @pos: bit position at which to unpack (passed and next position returned)
282 * @nrbits: number of bits of value to unpack (1-32)
284 * This functions returns the value unpacked.
286 uint32_t ubifs_unpack_bits(uint8_t **addr
, int *pos
, int nrbits
)
288 const int k
= 32 - nrbits
;
291 uint32_t uninitialized_var(val
);
292 const int bytes
= (nrbits
+ b
+ 7) >> 3;
294 ubifs_assert(nrbits
> 0);
295 ubifs_assert(nrbits
<= 32);
296 ubifs_assert(*pos
>= 0);
297 ubifs_assert(*pos
< 8);
304 val
= p
[1] | ((uint32_t)p
[2] << 8);
307 val
= p
[1] | ((uint32_t)p
[2] << 8) |
308 ((uint32_t)p
[3] << 16);
311 val
= p
[1] | ((uint32_t)p
[2] << 8) |
312 ((uint32_t)p
[3] << 16) |
313 ((uint32_t)p
[4] << 24);
324 val
= p
[0] | ((uint32_t)p
[1] << 8);
327 val
= p
[0] | ((uint32_t)p
[1] << 8) |
328 ((uint32_t)p
[2] << 16);
331 val
= p
[0] | ((uint32_t)p
[1] << 8) |
332 ((uint32_t)p
[2] << 16) |
333 ((uint32_t)p
[3] << 24);
343 ubifs_assert((val
>> nrbits
) == 0 || nrbits
- b
== 32);
348 * ubifs_pack_pnode - pack all the bit fields of a pnode.
349 * @c: UBIFS file-system description object
350 * @buf: buffer into which to pack
351 * @pnode: pnode to pack
353 void ubifs_pack_pnode(struct ubifs_info
*c
, void *buf
,
354 struct ubifs_pnode
*pnode
)
356 uint8_t *addr
= buf
+ UBIFS_LPT_CRC_BYTES
;
360 pack_bits(&addr
, &pos
, UBIFS_LPT_PNODE
, UBIFS_LPT_TYPE_BITS
);
362 pack_bits(&addr
, &pos
, pnode
->num
, c
->pcnt_bits
);
363 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
364 pack_bits(&addr
, &pos
, pnode
->lprops
[i
].free
>> 3,
366 pack_bits(&addr
, &pos
, pnode
->lprops
[i
].dirty
>> 3,
368 if (pnode
->lprops
[i
].flags
& LPROPS_INDEX
)
369 pack_bits(&addr
, &pos
, 1, 1);
371 pack_bits(&addr
, &pos
, 0, 1);
373 crc
= crc16(-1, buf
+ UBIFS_LPT_CRC_BYTES
,
374 c
->pnode_sz
- UBIFS_LPT_CRC_BYTES
);
377 pack_bits(&addr
, &pos
, crc
, UBIFS_LPT_CRC_BITS
);
381 * ubifs_pack_nnode - pack all the bit fields of a nnode.
382 * @c: UBIFS file-system description object
383 * @buf: buffer into which to pack
384 * @nnode: nnode to pack
386 void ubifs_pack_nnode(struct ubifs_info
*c
, void *buf
,
387 struct ubifs_nnode
*nnode
)
389 uint8_t *addr
= buf
+ UBIFS_LPT_CRC_BYTES
;
393 pack_bits(&addr
, &pos
, UBIFS_LPT_NNODE
, UBIFS_LPT_TYPE_BITS
);
395 pack_bits(&addr
, &pos
, nnode
->num
, c
->pcnt_bits
);
396 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
397 int lnum
= nnode
->nbranch
[i
].lnum
;
400 lnum
= c
->lpt_last
+ 1;
401 pack_bits(&addr
, &pos
, lnum
- c
->lpt_first
, c
->lpt_lnum_bits
);
402 pack_bits(&addr
, &pos
, nnode
->nbranch
[i
].offs
,
405 crc
= crc16(-1, buf
+ UBIFS_LPT_CRC_BYTES
,
406 c
->nnode_sz
- UBIFS_LPT_CRC_BYTES
);
409 pack_bits(&addr
, &pos
, crc
, UBIFS_LPT_CRC_BITS
);
413 * ubifs_pack_ltab - pack the LPT's own lprops table.
414 * @c: UBIFS file-system description object
415 * @buf: buffer into which to pack
416 * @ltab: LPT's own lprops table to pack
418 void ubifs_pack_ltab(struct ubifs_info
*c
, void *buf
,
419 struct ubifs_lpt_lprops
*ltab
)
421 uint8_t *addr
= buf
+ UBIFS_LPT_CRC_BYTES
;
425 pack_bits(&addr
, &pos
, UBIFS_LPT_LTAB
, UBIFS_LPT_TYPE_BITS
);
426 for (i
= 0; i
< c
->lpt_lebs
; i
++) {
427 pack_bits(&addr
, &pos
, ltab
[i
].free
, c
->lpt_spc_bits
);
428 pack_bits(&addr
, &pos
, ltab
[i
].dirty
, c
->lpt_spc_bits
);
430 crc
= crc16(-1, buf
+ UBIFS_LPT_CRC_BYTES
,
431 c
->ltab_sz
- UBIFS_LPT_CRC_BYTES
);
434 pack_bits(&addr
, &pos
, crc
, UBIFS_LPT_CRC_BITS
);
438 * ubifs_pack_lsave - pack the LPT's save table.
439 * @c: UBIFS file-system description object
440 * @buf: buffer into which to pack
441 * @lsave: LPT's save table to pack
443 void ubifs_pack_lsave(struct ubifs_info
*c
, void *buf
, int *lsave
)
445 uint8_t *addr
= buf
+ UBIFS_LPT_CRC_BYTES
;
449 pack_bits(&addr
, &pos
, UBIFS_LPT_LSAVE
, UBIFS_LPT_TYPE_BITS
);
450 for (i
= 0; i
< c
->lsave_cnt
; i
++)
451 pack_bits(&addr
, &pos
, lsave
[i
], c
->lnum_bits
);
452 crc
= crc16(-1, buf
+ UBIFS_LPT_CRC_BYTES
,
453 c
->lsave_sz
- UBIFS_LPT_CRC_BYTES
);
456 pack_bits(&addr
, &pos
, crc
, UBIFS_LPT_CRC_BITS
);
460 * ubifs_add_lpt_dirt - add dirty space to LPT LEB properties.
461 * @c: UBIFS file-system description object
462 * @lnum: LEB number to which to add dirty space
463 * @dirty: amount of dirty space to add
465 void ubifs_add_lpt_dirt(struct ubifs_info
*c
, int lnum
, int dirty
)
469 dbg_lp("LEB %d add %d to %d",
470 lnum
, dirty
, c
->ltab
[lnum
- c
->lpt_first
].dirty
);
471 ubifs_assert(lnum
>= c
->lpt_first
&& lnum
<= c
->lpt_last
);
472 c
->ltab
[lnum
- c
->lpt_first
].dirty
+= dirty
;
476 * set_ltab - set LPT LEB properties.
477 * @c: UBIFS file-system description object
479 * @free: amount of free space
480 * @dirty: amount of dirty space
482 static void set_ltab(struct ubifs_info
*c
, int lnum
, int free
, int dirty
)
484 dbg_lp("LEB %d free %d dirty %d to %d %d",
485 lnum
, c
->ltab
[lnum
- c
->lpt_first
].free
,
486 c
->ltab
[lnum
- c
->lpt_first
].dirty
, free
, dirty
);
487 ubifs_assert(lnum
>= c
->lpt_first
&& lnum
<= c
->lpt_last
);
488 c
->ltab
[lnum
- c
->lpt_first
].free
= free
;
489 c
->ltab
[lnum
- c
->lpt_first
].dirty
= dirty
;
493 * ubifs_add_nnode_dirt - add dirty space to LPT LEB properties.
494 * @c: UBIFS file-system description object
495 * @nnode: nnode for which to add dirt
497 void ubifs_add_nnode_dirt(struct ubifs_info
*c
, struct ubifs_nnode
*nnode
)
499 struct ubifs_nnode
*np
= nnode
->parent
;
502 ubifs_add_lpt_dirt(c
, np
->nbranch
[nnode
->iip
].lnum
,
505 ubifs_add_lpt_dirt(c
, c
->lpt_lnum
, c
->nnode_sz
);
506 if (!(c
->lpt_drty_flgs
& LTAB_DIRTY
)) {
507 c
->lpt_drty_flgs
|= LTAB_DIRTY
;
508 ubifs_add_lpt_dirt(c
, c
->ltab_lnum
, c
->ltab_sz
);
514 * add_pnode_dirt - add dirty space to LPT LEB properties.
515 * @c: UBIFS file-system description object
516 * @pnode: pnode for which to add dirt
518 static void add_pnode_dirt(struct ubifs_info
*c
, struct ubifs_pnode
*pnode
)
520 ubifs_add_lpt_dirt(c
, pnode
->parent
->nbranch
[pnode
->iip
].lnum
,
525 * calc_nnode_num - calculate nnode number.
526 * @row: the row in the tree (root is zero)
527 * @col: the column in the row (leftmost is zero)
529 * The nnode number is a number that uniquely identifies a nnode and can be used
530 * easily to traverse the tree from the root to that nnode.
532 * This function calculates and returns the nnode number for the nnode at @row
535 static int calc_nnode_num(int row
, int col
)
541 bits
= (col
& (UBIFS_LPT_FANOUT
- 1));
542 col
>>= UBIFS_LPT_FANOUT_SHIFT
;
543 num
<<= UBIFS_LPT_FANOUT_SHIFT
;
550 * calc_nnode_num_from_parent - calculate nnode number.
551 * @c: UBIFS file-system description object
552 * @parent: parent nnode
553 * @iip: index in parent
555 * The nnode number is a number that uniquely identifies a nnode and can be used
556 * easily to traverse the tree from the root to that nnode.
558 * This function calculates and returns the nnode number based on the parent's
559 * nnode number and the index in parent.
561 static int calc_nnode_num_from_parent(struct ubifs_info
*c
,
562 struct ubifs_nnode
*parent
, int iip
)
568 shft
= (c
->lpt_hght
- parent
->level
) * UBIFS_LPT_FANOUT_SHIFT
;
569 num
= parent
->num
^ (1 << shft
);
570 num
|= (UBIFS_LPT_FANOUT
+ iip
) << shft
;
575 * calc_pnode_num_from_parent - calculate pnode number.
576 * @c: UBIFS file-system description object
577 * @parent: parent nnode
578 * @iip: index in parent
580 * The pnode number is a number that uniquely identifies a pnode and can be used
581 * easily to traverse the tree from the root to that pnode.
583 * This function calculates and returns the pnode number based on the parent's
584 * nnode number and the index in parent.
586 static int calc_pnode_num_from_parent(struct ubifs_info
*c
,
587 struct ubifs_nnode
*parent
, int iip
)
589 int i
, n
= c
->lpt_hght
- 1, pnum
= parent
->num
, num
= 0;
591 for (i
= 0; i
< n
; i
++) {
592 num
<<= UBIFS_LPT_FANOUT_SHIFT
;
593 num
|= pnum
& (UBIFS_LPT_FANOUT
- 1);
594 pnum
>>= UBIFS_LPT_FANOUT_SHIFT
;
596 num
<<= UBIFS_LPT_FANOUT_SHIFT
;
602 * ubifs_create_dflt_lpt - create default LPT.
603 * @c: UBIFS file-system description object
604 * @main_lebs: number of main area LEBs is passed and returned here
605 * @lpt_first: LEB number of first LPT LEB
606 * @lpt_lebs: number of LEBs for LPT is passed and returned here
607 * @big_lpt: use big LPT model is passed and returned here
609 * This function returns %0 on success and a negative error code on failure.
611 int ubifs_create_dflt_lpt(struct ubifs_info
*c
, int *main_lebs
, int lpt_first
,
612 int *lpt_lebs
, int *big_lpt
)
614 int lnum
, err
= 0, node_sz
, iopos
, i
, j
, cnt
, len
, alen
, row
;
615 int blnum
, boffs
, bsz
, bcnt
;
616 struct ubifs_pnode
*pnode
= NULL
;
617 struct ubifs_nnode
*nnode
= NULL
;
618 void *buf
= NULL
, *p
;
619 struct ubifs_lpt_lprops
*ltab
= NULL
;
622 err
= calc_dflt_lpt_geom(c
, main_lebs
, big_lpt
);
625 *lpt_lebs
= c
->lpt_lebs
;
627 /* Needed by 'ubifs_pack_nnode()' and 'set_ltab()' */
628 c
->lpt_first
= lpt_first
;
629 /* Needed by 'set_ltab()' */
630 c
->lpt_last
= lpt_first
+ c
->lpt_lebs
- 1;
631 /* Needed by 'ubifs_pack_lsave()' */
632 c
->main_first
= c
->leb_cnt
- *main_lebs
;
634 lsave
= kmalloc(sizeof(int) * c
->lsave_cnt
, GFP_KERNEL
);
635 pnode
= kzalloc(sizeof(struct ubifs_pnode
), GFP_KERNEL
);
636 nnode
= kzalloc(sizeof(struct ubifs_nnode
), GFP_KERNEL
);
637 buf
= vmalloc(c
->leb_size
);
638 ltab
= vmalloc(sizeof(struct ubifs_lpt_lprops
) * c
->lpt_lebs
);
639 if (!pnode
|| !nnode
|| !buf
|| !ltab
|| !lsave
) {
644 ubifs_assert(!c
->ltab
);
645 c
->ltab
= ltab
; /* Needed by set_ltab */
647 /* Initialize LPT's own lprops */
648 for (i
= 0; i
< c
->lpt_lebs
; i
++) {
649 ltab
[i
].free
= c
->leb_size
;
657 /* Number of leaf nodes (pnodes) */
661 * The first pnode contains the LEB properties for the LEBs that contain
662 * the root inode node and the root index node of the index tree.
664 node_sz
= ALIGN(ubifs_idx_node_sz(c
, 1), 8);
665 iopos
= ALIGN(node_sz
, c
->min_io_size
);
666 pnode
->lprops
[0].free
= c
->leb_size
- iopos
;
667 pnode
->lprops
[0].dirty
= iopos
- node_sz
;
668 pnode
->lprops
[0].flags
= LPROPS_INDEX
;
670 node_sz
= UBIFS_INO_NODE_SZ
;
671 iopos
= ALIGN(node_sz
, c
->min_io_size
);
672 pnode
->lprops
[1].free
= c
->leb_size
- iopos
;
673 pnode
->lprops
[1].dirty
= iopos
- node_sz
;
675 for (i
= 2; i
< UBIFS_LPT_FANOUT
; i
++)
676 pnode
->lprops
[i
].free
= c
->leb_size
;
678 /* Add first pnode */
679 ubifs_pack_pnode(c
, p
, pnode
);
684 /* Reset pnode values for remaining pnodes */
685 pnode
->lprops
[0].free
= c
->leb_size
;
686 pnode
->lprops
[0].dirty
= 0;
687 pnode
->lprops
[0].flags
= 0;
689 pnode
->lprops
[1].free
= c
->leb_size
;
690 pnode
->lprops
[1].dirty
= 0;
693 * To calculate the internal node branches, we keep information about
696 blnum
= lnum
; /* LEB number of level below */
697 boffs
= 0; /* Offset of level below */
698 bcnt
= cnt
; /* Number of nodes in level below */
699 bsz
= c
->pnode_sz
; /* Size of nodes in level below */
701 /* Add all remaining pnodes */
702 for (i
= 1; i
< cnt
; i
++) {
703 if (len
+ c
->pnode_sz
> c
->leb_size
) {
704 alen
= ALIGN(len
, c
->min_io_size
);
705 set_ltab(c
, lnum
, c
->leb_size
- alen
, alen
- len
);
706 memset(p
, 0xff, alen
- len
);
707 err
= ubi_leb_change(c
->ubi
, lnum
++, buf
, alen
,
714 ubifs_pack_pnode(c
, p
, pnode
);
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.
726 for (i
= UBIFS_LPT_FANOUT
; cnt
> i
; i
<<= UBIFS_LPT_FANOUT_SHIFT
)
728 /* Add all nnodes, one level at a time */
730 /* Number of internal nodes (nnodes) at next level */
731 cnt
= DIV_ROUND_UP(cnt
, UBIFS_LPT_FANOUT
);
732 for (i
= 0; i
< cnt
; i
++) {
733 if (len
+ c
->nnode_sz
> c
->leb_size
) {
734 alen
= ALIGN(len
, c
->min_io_size
);
735 set_ltab(c
, lnum
, c
->leb_size
- alen
,
737 memset(p
, 0xff, alen
- len
);
738 err
= ubi_leb_change(c
->ubi
, lnum
++, buf
, alen
,
745 /* Only 1 nnode at this level, so it is the root */
750 /* Set branches to the level below */
751 for (j
= 0; j
< UBIFS_LPT_FANOUT
; j
++) {
753 if (boffs
+ bsz
> c
->leb_size
) {
757 nnode
->nbranch
[j
].lnum
= blnum
;
758 nnode
->nbranch
[j
].offs
= boffs
;
762 nnode
->nbranch
[j
].lnum
= 0;
763 nnode
->nbranch
[j
].offs
= 0;
766 nnode
->num
= calc_nnode_num(row
, i
);
767 ubifs_pack_nnode(c
, p
, nnode
);
771 /* Only 1 nnode at this level, so it is the root */
774 /* Update the information about the level below */
781 /* Need to add LPT's save table */
782 if (len
+ c
->lsave_sz
> c
->leb_size
) {
783 alen
= ALIGN(len
, c
->min_io_size
);
784 set_ltab(c
, lnum
, c
->leb_size
- alen
, alen
- len
);
785 memset(p
, 0xff, alen
- len
);
786 err
= ubi_leb_change(c
->ubi
, lnum
++, buf
, alen
,
794 c
->lsave_lnum
= lnum
;
797 for (i
= 0; i
< c
->lsave_cnt
&& i
< *main_lebs
; i
++)
798 lsave
[i
] = c
->main_first
+ i
;
799 for (; i
< c
->lsave_cnt
; i
++)
800 lsave
[i
] = c
->main_first
;
802 ubifs_pack_lsave(c
, p
, lsave
);
807 /* Need to add LPT's own LEB properties table */
808 if (len
+ c
->ltab_sz
> c
->leb_size
) {
809 alen
= ALIGN(len
, c
->min_io_size
);
810 set_ltab(c
, lnum
, c
->leb_size
- alen
, alen
- len
);
811 memset(p
, 0xff, alen
- len
);
812 err
= ubi_leb_change(c
->ubi
, lnum
++, buf
, alen
, UBI_SHORTTERM
);
822 /* Update ltab before packing it */
824 alen
= ALIGN(len
, c
->min_io_size
);
825 set_ltab(c
, lnum
, c
->leb_size
- alen
, alen
- len
);
827 ubifs_pack_ltab(c
, p
, ltab
);
830 /* Write remaining buffer */
831 memset(p
, 0xff, alen
- len
);
832 err
= ubi_leb_change(c
->ubi
, lnum
, buf
, alen
, UBI_SHORTTERM
);
836 c
->nhead_lnum
= lnum
;
837 c
->nhead_offs
= ALIGN(len
, c
->min_io_size
);
839 dbg_lp("space_bits %d", c
->space_bits
);
840 dbg_lp("lpt_lnum_bits %d", c
->lpt_lnum_bits
);
841 dbg_lp("lpt_offs_bits %d", c
->lpt_offs_bits
);
842 dbg_lp("lpt_spc_bits %d", c
->lpt_spc_bits
);
843 dbg_lp("pcnt_bits %d", c
->pcnt_bits
);
844 dbg_lp("lnum_bits %d", c
->lnum_bits
);
845 dbg_lp("pnode_sz %d", c
->pnode_sz
);
846 dbg_lp("nnode_sz %d", c
->nnode_sz
);
847 dbg_lp("ltab_sz %d", c
->ltab_sz
);
848 dbg_lp("lsave_sz %d", c
->lsave_sz
);
849 dbg_lp("lsave_cnt %d", c
->lsave_cnt
);
850 dbg_lp("lpt_hght %d", c
->lpt_hght
);
851 dbg_lp("big_lpt %d", c
->big_lpt
);
852 dbg_lp("LPT root is at %d:%d", c
->lpt_lnum
, c
->lpt_offs
);
853 dbg_lp("LPT head is at %d:%d", c
->nhead_lnum
, c
->nhead_offs
);
854 dbg_lp("LPT ltab is at %d:%d", c
->ltab_lnum
, c
->ltab_offs
);
856 dbg_lp("LPT lsave is at %d:%d", c
->lsave_lnum
, c
->lsave_offs
);
868 * update_cats - add LEB properties of a pnode to LEB category lists and heaps.
869 * @c: UBIFS file-system description object
872 * When a pnode is loaded into memory, the LEB properties it contains are added,
873 * by this function, to the LEB category lists and heaps.
875 static void update_cats(struct ubifs_info
*c
, struct ubifs_pnode
*pnode
)
879 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
880 int cat
= pnode
->lprops
[i
].flags
& LPROPS_CAT_MASK
;
881 int lnum
= pnode
->lprops
[i
].lnum
;
885 ubifs_add_to_cat(c
, &pnode
->lprops
[i
], cat
);
890 * replace_cats - add LEB properties of a pnode to LEB category lists and heaps.
891 * @c: UBIFS file-system description object
892 * @old_pnode: pnode copied
893 * @new_pnode: pnode copy
895 * During commit it is sometimes necessary to copy a pnode
896 * (see dirty_cow_pnode). When that happens, references in
897 * category lists and heaps must be replaced. This function does that.
899 static void replace_cats(struct ubifs_info
*c
, struct ubifs_pnode
*old_pnode
,
900 struct ubifs_pnode
*new_pnode
)
904 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
905 if (!new_pnode
->lprops
[i
].lnum
)
907 ubifs_replace_cat(c
, &old_pnode
->lprops
[i
],
908 &new_pnode
->lprops
[i
]);
913 * check_lpt_crc - check LPT node crc is correct.
914 * @c: UBIFS file-system description object
915 * @buf: buffer containing node
916 * @len: length of node
918 * This function returns %0 on success and a negative error code on failure.
920 static int check_lpt_crc(void *buf
, int len
)
924 uint16_t crc
, calc_crc
;
926 crc
= ubifs_unpack_bits(&addr
, &pos
, UBIFS_LPT_CRC_BITS
);
927 calc_crc
= crc16(-1, buf
+ UBIFS_LPT_CRC_BYTES
,
928 len
- UBIFS_LPT_CRC_BYTES
);
929 if (crc
!= calc_crc
) {
930 ubifs_err("invalid crc in LPT node: crc %hx calc %hx", crc
,
939 * check_lpt_type - check LPT node type is correct.
940 * @c: UBIFS file-system description object
941 * @addr: address of type bit field is passed and returned updated here
942 * @pos: position of type bit field is passed and returned updated here
943 * @type: expected type
945 * This function returns %0 on success and a negative error code on failure.
947 static int check_lpt_type(uint8_t **addr
, int *pos
, int type
)
951 node_type
= ubifs_unpack_bits(addr
, pos
, UBIFS_LPT_TYPE_BITS
);
952 if (node_type
!= type
) {
953 ubifs_err("invalid type (%d) in LPT node type %d", node_type
,
962 * unpack_pnode - unpack a pnode.
963 * @c: UBIFS file-system description object
964 * @buf: buffer containing packed pnode to unpack
965 * @pnode: pnode structure to fill
967 * This function returns %0 on success and a negative error code on failure.
969 static int unpack_pnode(struct ubifs_info
*c
, void *buf
,
970 struct ubifs_pnode
*pnode
)
972 uint8_t *addr
= buf
+ UBIFS_LPT_CRC_BYTES
;
975 err
= check_lpt_type(&addr
, &pos
, UBIFS_LPT_PNODE
);
979 pnode
->num
= ubifs_unpack_bits(&addr
, &pos
, c
->pcnt_bits
);
980 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
981 struct ubifs_lprops
* const lprops
= &pnode
->lprops
[i
];
983 lprops
->free
= ubifs_unpack_bits(&addr
, &pos
, c
->space_bits
);
985 lprops
->dirty
= ubifs_unpack_bits(&addr
, &pos
, c
->space_bits
);
988 if (ubifs_unpack_bits(&addr
, &pos
, 1))
989 lprops
->flags
= LPROPS_INDEX
;
992 lprops
->flags
|= ubifs_categorize_lprops(c
, lprops
);
994 err
= check_lpt_crc(buf
, c
->pnode_sz
);
999 * unpack_nnode - unpack a nnode.
1000 * @c: UBIFS file-system description object
1001 * @buf: buffer containing packed nnode to unpack
1002 * @nnode: nnode structure to fill
1004 * This function returns %0 on success and a negative error code on failure.
1006 static int unpack_nnode(struct ubifs_info
*c
, void *buf
,
1007 struct ubifs_nnode
*nnode
)
1009 uint8_t *addr
= buf
+ UBIFS_LPT_CRC_BYTES
;
1010 int i
, pos
= 0, err
;
1012 err
= check_lpt_type(&addr
, &pos
, UBIFS_LPT_NNODE
);
1016 nnode
->num
= ubifs_unpack_bits(&addr
, &pos
, c
->pcnt_bits
);
1017 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
1020 lnum
= ubifs_unpack_bits(&addr
, &pos
, c
->lpt_lnum_bits
) +
1022 if (lnum
== c
->lpt_last
+ 1)
1024 nnode
->nbranch
[i
].lnum
= lnum
;
1025 nnode
->nbranch
[i
].offs
= ubifs_unpack_bits(&addr
, &pos
,
1028 err
= check_lpt_crc(buf
, c
->nnode_sz
);
1033 * unpack_ltab - unpack the LPT's own lprops table.
1034 * @c: UBIFS file-system description object
1035 * @buf: buffer from which to unpack
1037 * This function returns %0 on success and a negative error code on failure.
1039 static int unpack_ltab(struct ubifs_info
*c
, void *buf
)
1041 uint8_t *addr
= buf
+ UBIFS_LPT_CRC_BYTES
;
1042 int i
, pos
= 0, err
;
1044 err
= check_lpt_type(&addr
, &pos
, UBIFS_LPT_LTAB
);
1047 for (i
= 0; i
< c
->lpt_lebs
; i
++) {
1048 int free
= ubifs_unpack_bits(&addr
, &pos
, c
->lpt_spc_bits
);
1049 int dirty
= ubifs_unpack_bits(&addr
, &pos
, c
->lpt_spc_bits
);
1051 if (free
< 0 || free
> c
->leb_size
|| dirty
< 0 ||
1052 dirty
> c
->leb_size
|| free
+ dirty
> c
->leb_size
)
1055 c
->ltab
[i
].free
= free
;
1056 c
->ltab
[i
].dirty
= dirty
;
1060 err
= check_lpt_crc(buf
, c
->ltab_sz
);
1065 * unpack_lsave - unpack the LPT's save table.
1066 * @c: UBIFS file-system description object
1067 * @buf: buffer from which to unpack
1069 * This function returns %0 on success and a negative error code on failure.
1071 static int unpack_lsave(struct ubifs_info
*c
, void *buf
)
1073 uint8_t *addr
= buf
+ UBIFS_LPT_CRC_BYTES
;
1074 int i
, pos
= 0, err
;
1076 err
= check_lpt_type(&addr
, &pos
, UBIFS_LPT_LSAVE
);
1079 for (i
= 0; i
< c
->lsave_cnt
; i
++) {
1080 int lnum
= ubifs_unpack_bits(&addr
, &pos
, c
->lnum_bits
);
1082 if (lnum
< c
->main_first
|| lnum
>= c
->leb_cnt
)
1086 err
= check_lpt_crc(buf
, c
->lsave_sz
);
1091 * validate_nnode - validate a nnode.
1092 * @c: UBIFS file-system description object
1093 * @nnode: nnode to validate
1094 * @parent: parent nnode (or NULL for the root nnode)
1095 * @iip: index in parent
1097 * This function returns %0 on success and a negative error code on failure.
1099 static int validate_nnode(struct ubifs_info
*c
, struct ubifs_nnode
*nnode
,
1100 struct ubifs_nnode
*parent
, int iip
)
1102 int i
, lvl
, max_offs
;
1105 int num
= calc_nnode_num_from_parent(c
, parent
, iip
);
1107 if (nnode
->num
!= num
)
1110 lvl
= parent
? parent
->level
- 1 : c
->lpt_hght
;
1114 max_offs
= c
->leb_size
- c
->pnode_sz
;
1116 max_offs
= c
->leb_size
- c
->nnode_sz
;
1117 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
1118 int lnum
= nnode
->nbranch
[i
].lnum
;
1119 int offs
= nnode
->nbranch
[i
].offs
;
1126 if (lnum
< c
->lpt_first
|| lnum
> c
->lpt_last
)
1128 if (offs
< 0 || offs
> max_offs
)
1135 * validate_pnode - validate a pnode.
1136 * @c: UBIFS file-system description object
1137 * @pnode: pnode to validate
1138 * @parent: parent nnode
1139 * @iip: index in parent
1141 * This function returns %0 on success and a negative error code on failure.
1143 static int validate_pnode(struct ubifs_info
*c
, struct ubifs_pnode
*pnode
,
1144 struct ubifs_nnode
*parent
, int iip
)
1149 int num
= calc_pnode_num_from_parent(c
, parent
, iip
);
1151 if (pnode
->num
!= num
)
1154 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
1155 int free
= pnode
->lprops
[i
].free
;
1156 int dirty
= pnode
->lprops
[i
].dirty
;
1158 if (free
< 0 || free
> c
->leb_size
|| free
% c
->min_io_size
||
1161 if (dirty
< 0 || dirty
> c
->leb_size
|| (dirty
& 7))
1163 if (dirty
+ free
> c
->leb_size
)
1170 * set_pnode_lnum - set LEB numbers on a pnode.
1171 * @c: UBIFS file-system description object
1172 * @pnode: pnode to update
1174 * This function calculates the LEB numbers for the LEB properties it contains
1175 * based on the pnode number.
1177 static void set_pnode_lnum(struct ubifs_info
*c
, struct ubifs_pnode
*pnode
)
1181 lnum
= (pnode
->num
<< UBIFS_LPT_FANOUT_SHIFT
) + c
->main_first
;
1182 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
1183 if (lnum
>= c
->leb_cnt
)
1185 pnode
->lprops
[i
].lnum
= lnum
++;
1190 * ubifs_read_nnode - read a nnode from flash and link it to the tree in memory.
1191 * @c: UBIFS file-system description object
1192 * @parent: parent nnode (or NULL for the root)
1193 * @iip: index in parent
1195 * This function returns %0 on success and a negative error code on failure.
1197 int ubifs_read_nnode(struct ubifs_info
*c
, struct ubifs_nnode
*parent
, int iip
)
1199 struct ubifs_nbranch
*branch
= NULL
;
1200 struct ubifs_nnode
*nnode
= NULL
;
1201 void *buf
= c
->lpt_nod_buf
;
1202 int err
, lnum
, offs
;
1205 branch
= &parent
->nbranch
[iip
];
1206 lnum
= branch
->lnum
;
1207 offs
= branch
->offs
;
1212 nnode
= kzalloc(sizeof(struct ubifs_nnode
), GFP_NOFS
);
1219 * This nnode was not written which just means that the LEB
1220 * properties in the subtree below it describe empty LEBs. We
1221 * make the nnode as though we had read it, which in fact means
1222 * doing almost nothing.
1225 nnode
->num
= calc_nnode_num_from_parent(c
, parent
, iip
);
1227 err
= ubi_read(c
->ubi
, lnum
, buf
, offs
, c
->nnode_sz
);
1230 err
= unpack_nnode(c
, buf
, nnode
);
1234 err
= validate_nnode(c
, nnode
, parent
, iip
);
1238 nnode
->num
= calc_nnode_num_from_parent(c
, parent
, iip
);
1240 branch
->nnode
= nnode
;
1241 nnode
->level
= parent
->level
- 1;
1244 nnode
->level
= c
->lpt_hght
;
1246 nnode
->parent
= parent
;
1251 ubifs_err("error %d reading nnode at %d:%d", err
, lnum
, offs
);
1257 * read_pnode - read a pnode from flash and link it to the tree in memory.
1258 * @c: UBIFS file-system description object
1259 * @parent: parent nnode
1260 * @iip: index in parent
1262 * This function returns %0 on success and a negative error code on failure.
1264 static int read_pnode(struct ubifs_info
*c
, struct ubifs_nnode
*parent
, int iip
)
1266 struct ubifs_nbranch
*branch
;
1267 struct ubifs_pnode
*pnode
= NULL
;
1268 void *buf
= c
->lpt_nod_buf
;
1269 int err
, lnum
, offs
;
1271 branch
= &parent
->nbranch
[iip
];
1272 lnum
= branch
->lnum
;
1273 offs
= branch
->offs
;
1274 pnode
= kzalloc(sizeof(struct ubifs_pnode
), GFP_NOFS
);
1281 * This pnode was not written which just means that the LEB
1282 * properties in it describe empty LEBs. We make the pnode as
1283 * though we had read it.
1288 pnode
->num
= calc_pnode_num_from_parent(c
, parent
, iip
);
1289 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
1290 struct ubifs_lprops
* const lprops
= &pnode
->lprops
[i
];
1292 lprops
->free
= c
->leb_size
;
1293 lprops
->flags
= ubifs_categorize_lprops(c
, lprops
);
1296 err
= ubi_read(c
->ubi
, lnum
, buf
, offs
, c
->pnode_sz
);
1299 err
= unpack_pnode(c
, buf
, pnode
);
1303 err
= validate_pnode(c
, pnode
, parent
, iip
);
1307 pnode
->num
= calc_pnode_num_from_parent(c
, parent
, iip
);
1308 branch
->pnode
= pnode
;
1309 pnode
->parent
= parent
;
1311 set_pnode_lnum(c
, pnode
);
1312 c
->pnodes_have
+= 1;
1316 ubifs_err("error %d reading pnode at %d:%d", err
, lnum
, offs
);
1317 dbg_dump_pnode(c
, pnode
, parent
, iip
);
1318 dbg_msg("calc num: %d", calc_pnode_num_from_parent(c
, parent
, iip
));
1324 * read_ltab - read LPT's own lprops table.
1325 * @c: UBIFS file-system description object
1327 * This function returns %0 on success and a negative error code on failure.
1329 static int read_ltab(struct ubifs_info
*c
)
1334 buf
= vmalloc(c
->ltab_sz
);
1337 err
= ubi_read(c
->ubi
, c
->ltab_lnum
, buf
, c
->ltab_offs
, c
->ltab_sz
);
1340 err
= unpack_ltab(c
, buf
);
1347 * read_lsave - read LPT's save table.
1348 * @c: UBIFS file-system description object
1350 * This function returns %0 on success and a negative error code on failure.
1352 static int read_lsave(struct ubifs_info
*c
)
1357 buf
= vmalloc(c
->lsave_sz
);
1360 err
= ubi_read(c
->ubi
, c
->lsave_lnum
, buf
, c
->lsave_offs
, c
->lsave_sz
);
1363 err
= unpack_lsave(c
, buf
);
1366 for (i
= 0; i
< c
->lsave_cnt
; i
++) {
1367 int lnum
= c
->lsave
[i
];
1370 * Due to automatic resizing, the values in the lsave table
1371 * could be beyond the volume size - just ignore them.
1373 if (lnum
>= c
->leb_cnt
)
1375 ubifs_lpt_lookup(c
, lnum
);
1383 * ubifs_get_nnode - get a nnode.
1384 * @c: UBIFS file-system description object
1385 * @parent: parent nnode (or NULL for the root)
1386 * @iip: index in parent
1388 * This function returns a pointer to the nnode on success or a negative error
1391 struct ubifs_nnode
*ubifs_get_nnode(struct ubifs_info
*c
,
1392 struct ubifs_nnode
*parent
, int iip
)
1394 struct ubifs_nbranch
*branch
;
1395 struct ubifs_nnode
*nnode
;
1398 branch
= &parent
->nbranch
[iip
];
1399 nnode
= branch
->nnode
;
1402 err
= ubifs_read_nnode(c
, parent
, iip
);
1404 return ERR_PTR(err
);
1405 return branch
->nnode
;
1409 * ubifs_get_pnode - get a pnode.
1410 * @c: UBIFS file-system description object
1411 * @parent: parent nnode
1412 * @iip: index in parent
1414 * This function returns a pointer to the pnode on success or a negative error
1417 struct ubifs_pnode
*ubifs_get_pnode(struct ubifs_info
*c
,
1418 struct ubifs_nnode
*parent
, int iip
)
1420 struct ubifs_nbranch
*branch
;
1421 struct ubifs_pnode
*pnode
;
1424 branch
= &parent
->nbranch
[iip
];
1425 pnode
= branch
->pnode
;
1428 err
= read_pnode(c
, parent
, iip
);
1430 return ERR_PTR(err
);
1431 update_cats(c
, branch
->pnode
);
1432 return branch
->pnode
;
1436 * ubifs_lpt_lookup - lookup LEB properties in the LPT.
1437 * @c: UBIFS file-system description object
1438 * @lnum: LEB number to lookup
1440 * This function returns a pointer to the LEB properties on success or a
1441 * negative error code on failure.
1443 struct ubifs_lprops
*ubifs_lpt_lookup(struct ubifs_info
*c
, int lnum
)
1445 int err
, i
, h
, iip
, shft
;
1446 struct ubifs_nnode
*nnode
;
1447 struct ubifs_pnode
*pnode
;
1450 err
= ubifs_read_nnode(c
, NULL
, 0);
1452 return ERR_PTR(err
);
1455 i
= lnum
- c
->main_first
;
1456 shft
= c
->lpt_hght
* UBIFS_LPT_FANOUT_SHIFT
;
1457 for (h
= 1; h
< c
->lpt_hght
; h
++) {
1458 iip
= ((i
>> shft
) & (UBIFS_LPT_FANOUT
- 1));
1459 shft
-= UBIFS_LPT_FANOUT_SHIFT
;
1460 nnode
= ubifs_get_nnode(c
, nnode
, iip
);
1462 return ERR_PTR(PTR_ERR(nnode
));
1464 iip
= ((i
>> shft
) & (UBIFS_LPT_FANOUT
- 1));
1465 shft
-= UBIFS_LPT_FANOUT_SHIFT
;
1466 pnode
= ubifs_get_pnode(c
, nnode
, iip
);
1468 return ERR_PTR(PTR_ERR(pnode
));
1469 iip
= (i
& (UBIFS_LPT_FANOUT
- 1));
1470 dbg_lp("LEB %d, free %d, dirty %d, flags %d", lnum
,
1471 pnode
->lprops
[iip
].free
, pnode
->lprops
[iip
].dirty
,
1472 pnode
->lprops
[iip
].flags
);
1473 return &pnode
->lprops
[iip
];
1477 * dirty_cow_nnode - ensure a nnode is not being committed.
1478 * @c: UBIFS file-system description object
1479 * @nnode: nnode to check
1481 * Returns dirtied nnode on success or negative error code on failure.
1483 static struct ubifs_nnode
*dirty_cow_nnode(struct ubifs_info
*c
,
1484 struct ubifs_nnode
*nnode
)
1486 struct ubifs_nnode
*n
;
1489 if (!test_bit(COW_CNODE
, &nnode
->flags
)) {
1490 /* nnode is not being committed */
1491 if (!test_and_set_bit(DIRTY_CNODE
, &nnode
->flags
)) {
1492 c
->dirty_nn_cnt
+= 1;
1493 ubifs_add_nnode_dirt(c
, nnode
);
1498 /* nnode is being committed, so copy it */
1499 n
= kmalloc(sizeof(struct ubifs_nnode
), GFP_NOFS
);
1501 return ERR_PTR(-ENOMEM
);
1503 memcpy(n
, nnode
, sizeof(struct ubifs_nnode
));
1505 __set_bit(DIRTY_CNODE
, &n
->flags
);
1506 __clear_bit(COW_CNODE
, &n
->flags
);
1508 /* The children now have new parent */
1509 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
1510 struct ubifs_nbranch
*branch
= &n
->nbranch
[i
];
1513 branch
->cnode
->parent
= n
;
1516 ubifs_assert(!test_bit(OBSOLETE_CNODE
, &nnode
->flags
));
1517 __set_bit(OBSOLETE_CNODE
, &nnode
->flags
);
1519 c
->dirty_nn_cnt
+= 1;
1520 ubifs_add_nnode_dirt(c
, nnode
);
1522 nnode
->parent
->nbranch
[n
->iip
].nnode
= n
;
1529 * dirty_cow_pnode - ensure a pnode is not being committed.
1530 * @c: UBIFS file-system description object
1531 * @pnode: pnode to check
1533 * Returns dirtied pnode on success or negative error code on failure.
1535 static struct ubifs_pnode
*dirty_cow_pnode(struct ubifs_info
*c
,
1536 struct ubifs_pnode
*pnode
)
1538 struct ubifs_pnode
*p
;
1540 if (!test_bit(COW_CNODE
, &pnode
->flags
)) {
1541 /* pnode is not being committed */
1542 if (!test_and_set_bit(DIRTY_CNODE
, &pnode
->flags
)) {
1543 c
->dirty_pn_cnt
+= 1;
1544 add_pnode_dirt(c
, pnode
);
1549 /* pnode is being committed, so copy it */
1550 p
= kmalloc(sizeof(struct ubifs_pnode
), GFP_NOFS
);
1552 return ERR_PTR(-ENOMEM
);
1554 memcpy(p
, pnode
, sizeof(struct ubifs_pnode
));
1556 __set_bit(DIRTY_CNODE
, &p
->flags
);
1557 __clear_bit(COW_CNODE
, &p
->flags
);
1558 replace_cats(c
, pnode
, p
);
1560 ubifs_assert(!test_bit(OBSOLETE_CNODE
, &pnode
->flags
));
1561 __set_bit(OBSOLETE_CNODE
, &pnode
->flags
);
1563 c
->dirty_pn_cnt
+= 1;
1564 add_pnode_dirt(c
, pnode
);
1565 pnode
->parent
->nbranch
[p
->iip
].pnode
= p
;
1570 * ubifs_lpt_lookup_dirty - lookup LEB properties in the LPT.
1571 * @c: UBIFS file-system description object
1572 * @lnum: LEB number to lookup
1574 * This function returns a pointer to the LEB properties on success or a
1575 * negative error code on failure.
1577 struct ubifs_lprops
*ubifs_lpt_lookup_dirty(struct ubifs_info
*c
, int lnum
)
1579 int err
, i
, h
, iip
, shft
;
1580 struct ubifs_nnode
*nnode
;
1581 struct ubifs_pnode
*pnode
;
1584 err
= ubifs_read_nnode(c
, NULL
, 0);
1586 return ERR_PTR(err
);
1589 nnode
= dirty_cow_nnode(c
, nnode
);
1591 return ERR_PTR(PTR_ERR(nnode
));
1592 i
= lnum
- c
->main_first
;
1593 shft
= c
->lpt_hght
* UBIFS_LPT_FANOUT_SHIFT
;
1594 for (h
= 1; h
< c
->lpt_hght
; h
++) {
1595 iip
= ((i
>> shft
) & (UBIFS_LPT_FANOUT
- 1));
1596 shft
-= UBIFS_LPT_FANOUT_SHIFT
;
1597 nnode
= ubifs_get_nnode(c
, nnode
, iip
);
1599 return ERR_PTR(PTR_ERR(nnode
));
1600 nnode
= dirty_cow_nnode(c
, nnode
);
1602 return ERR_PTR(PTR_ERR(nnode
));
1604 iip
= ((i
>> shft
) & (UBIFS_LPT_FANOUT
- 1));
1605 shft
-= UBIFS_LPT_FANOUT_SHIFT
;
1606 pnode
= ubifs_get_pnode(c
, nnode
, iip
);
1608 return ERR_PTR(PTR_ERR(pnode
));
1609 pnode
= dirty_cow_pnode(c
, pnode
);
1611 return ERR_PTR(PTR_ERR(pnode
));
1612 iip
= (i
& (UBIFS_LPT_FANOUT
- 1));
1613 dbg_lp("LEB %d, free %d, dirty %d, flags %d", lnum
,
1614 pnode
->lprops
[iip
].free
, pnode
->lprops
[iip
].dirty
,
1615 pnode
->lprops
[iip
].flags
);
1616 ubifs_assert(test_bit(DIRTY_CNODE
, &pnode
->flags
));
1617 return &pnode
->lprops
[iip
];
1621 * lpt_init_rd - initialize the LPT for reading.
1622 * @c: UBIFS file-system description object
1624 * This function returns %0 on success and a negative error code on failure.
1626 static int lpt_init_rd(struct ubifs_info
*c
)
1630 c
->ltab
= vmalloc(sizeof(struct ubifs_lpt_lprops
) * c
->lpt_lebs
);
1634 i
= max_t(int, c
->nnode_sz
, c
->pnode_sz
);
1635 c
->lpt_nod_buf
= kmalloc(i
, GFP_KERNEL
);
1636 if (!c
->lpt_nod_buf
)
1639 for (i
= 0; i
< LPROPS_HEAP_CNT
; i
++) {
1640 c
->lpt_heap
[i
].arr
= kmalloc(sizeof(void *) * LPT_HEAP_SZ
,
1642 if (!c
->lpt_heap
[i
].arr
)
1644 c
->lpt_heap
[i
].cnt
= 0;
1645 c
->lpt_heap
[i
].max_cnt
= LPT_HEAP_SZ
;
1648 c
->dirty_idx
.arr
= kmalloc(sizeof(void *) * LPT_HEAP_SZ
, GFP_KERNEL
);
1649 if (!c
->dirty_idx
.arr
)
1651 c
->dirty_idx
.cnt
= 0;
1652 c
->dirty_idx
.max_cnt
= LPT_HEAP_SZ
;
1658 dbg_lp("space_bits %d", c
->space_bits
);
1659 dbg_lp("lpt_lnum_bits %d", c
->lpt_lnum_bits
);
1660 dbg_lp("lpt_offs_bits %d", c
->lpt_offs_bits
);
1661 dbg_lp("lpt_spc_bits %d", c
->lpt_spc_bits
);
1662 dbg_lp("pcnt_bits %d", c
->pcnt_bits
);
1663 dbg_lp("lnum_bits %d", c
->lnum_bits
);
1664 dbg_lp("pnode_sz %d", c
->pnode_sz
);
1665 dbg_lp("nnode_sz %d", c
->nnode_sz
);
1666 dbg_lp("ltab_sz %d", c
->ltab_sz
);
1667 dbg_lp("lsave_sz %d", c
->lsave_sz
);
1668 dbg_lp("lsave_cnt %d", c
->lsave_cnt
);
1669 dbg_lp("lpt_hght %d", c
->lpt_hght
);
1670 dbg_lp("big_lpt %d", c
->big_lpt
);
1671 dbg_lp("LPT root is at %d:%d", c
->lpt_lnum
, c
->lpt_offs
);
1672 dbg_lp("LPT head is at %d:%d", c
->nhead_lnum
, c
->nhead_offs
);
1673 dbg_lp("LPT ltab is at %d:%d", c
->ltab_lnum
, c
->ltab_offs
);
1675 dbg_lp("LPT lsave is at %d:%d", c
->lsave_lnum
, c
->lsave_offs
);
1681 * lpt_init_wr - initialize the LPT for writing.
1682 * @c: UBIFS file-system description object
1684 * 'lpt_init_rd()' must have been called already.
1686 * This function returns %0 on success and a negative error code on failure.
1688 static int lpt_init_wr(struct ubifs_info
*c
)
1692 c
->ltab_cmt
= vmalloc(sizeof(struct ubifs_lpt_lprops
) * c
->lpt_lebs
);
1696 c
->lpt_buf
= vmalloc(c
->leb_size
);
1701 c
->lsave
= kmalloc(sizeof(int) * c
->lsave_cnt
, GFP_NOFS
);
1704 err
= read_lsave(c
);
1709 for (i
= 0; i
< c
->lpt_lebs
; i
++)
1710 if (c
->ltab
[i
].free
== c
->leb_size
) {
1711 err
= ubifs_leb_unmap(c
, i
+ c
->lpt_first
);
1720 * ubifs_lpt_init - initialize the LPT.
1721 * @c: UBIFS file-system description object
1722 * @rd: whether to initialize lpt for reading
1723 * @wr: whether to initialize lpt for writing
1725 * For mounting 'rw', @rd and @wr are both true. For mounting 'ro', @rd is true
1726 * and @wr is false. For mounting from 'ro' to 'rw', @rd is false and @wr is
1729 * This function returns %0 on success and a negative error code on failure.
1731 int ubifs_lpt_init(struct ubifs_info
*c
, int rd
, int wr
)
1736 err
= lpt_init_rd(c
);
1742 err
= lpt_init_wr(c
);
1751 * struct lpt_scan_node - somewhere to put nodes while we scan LPT.
1752 * @nnode: where to keep a nnode
1753 * @pnode: where to keep a pnode
1754 * @cnode: where to keep a cnode
1755 * @in_tree: is the node in the tree in memory
1756 * @ptr.nnode: pointer to the nnode (if it is an nnode) which may be here or in
1758 * @ptr.pnode: ditto for pnode
1759 * @ptr.cnode: ditto for cnode
1761 struct lpt_scan_node
{
1763 struct ubifs_nnode nnode
;
1764 struct ubifs_pnode pnode
;
1765 struct ubifs_cnode cnode
;
1769 struct ubifs_nnode
*nnode
;
1770 struct ubifs_pnode
*pnode
;
1771 struct ubifs_cnode
*cnode
;
1776 * scan_get_nnode - for the scan, get a nnode from either the tree or flash.
1777 * @c: the UBIFS file-system description object
1778 * @path: where to put the nnode
1779 * @parent: parent of the nnode
1780 * @iip: index in parent of the nnode
1782 * This function returns a pointer to the nnode on success or a negative error
1785 static struct ubifs_nnode
*scan_get_nnode(struct ubifs_info
*c
,
1786 struct lpt_scan_node
*path
,
1787 struct ubifs_nnode
*parent
, int iip
)
1789 struct ubifs_nbranch
*branch
;
1790 struct ubifs_nnode
*nnode
;
1791 void *buf
= c
->lpt_nod_buf
;
1794 branch
= &parent
->nbranch
[iip
];
1795 nnode
= branch
->nnode
;
1798 path
->ptr
.nnode
= nnode
;
1801 nnode
= &path
->nnode
;
1803 path
->ptr
.nnode
= nnode
;
1804 memset(nnode
, 0, sizeof(struct ubifs_nnode
));
1805 if (branch
->lnum
== 0) {
1807 * This nnode was not written which just means that the LEB
1808 * properties in the subtree below it describe empty LEBs. We
1809 * make the nnode as though we had read it, which in fact means
1810 * doing almost nothing.
1813 nnode
->num
= calc_nnode_num_from_parent(c
, parent
, iip
);
1815 err
= ubi_read(c
->ubi
, branch
->lnum
, buf
, branch
->offs
,
1818 return ERR_PTR(err
);
1819 err
= unpack_nnode(c
, buf
, nnode
);
1821 return ERR_PTR(err
);
1823 err
= validate_nnode(c
, nnode
, parent
, iip
);
1825 return ERR_PTR(err
);
1827 nnode
->num
= calc_nnode_num_from_parent(c
, parent
, iip
);
1828 nnode
->level
= parent
->level
- 1;
1829 nnode
->parent
= parent
;
1835 * scan_get_pnode - for the scan, get a pnode from either the tree or flash.
1836 * @c: the UBIFS file-system description object
1837 * @path: where to put the pnode
1838 * @parent: parent of the pnode
1839 * @iip: index in parent of the pnode
1841 * This function returns a pointer to the pnode on success or a negative error
1844 static struct ubifs_pnode
*scan_get_pnode(struct ubifs_info
*c
,
1845 struct lpt_scan_node
*path
,
1846 struct ubifs_nnode
*parent
, int iip
)
1848 struct ubifs_nbranch
*branch
;
1849 struct ubifs_pnode
*pnode
;
1850 void *buf
= c
->lpt_nod_buf
;
1853 branch
= &parent
->nbranch
[iip
];
1854 pnode
= branch
->pnode
;
1857 path
->ptr
.pnode
= pnode
;
1860 pnode
= &path
->pnode
;
1862 path
->ptr
.pnode
= pnode
;
1863 memset(pnode
, 0, sizeof(struct ubifs_pnode
));
1864 if (branch
->lnum
== 0) {
1866 * This pnode was not written which just means that the LEB
1867 * properties in it describe empty LEBs. We make the pnode as
1868 * though we had read it.
1873 pnode
->num
= calc_pnode_num_from_parent(c
, parent
, iip
);
1874 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
1875 struct ubifs_lprops
* const lprops
= &pnode
->lprops
[i
];
1877 lprops
->free
= c
->leb_size
;
1878 lprops
->flags
= ubifs_categorize_lprops(c
, lprops
);
1881 ubifs_assert(branch
->lnum
>= c
->lpt_first
&&
1882 branch
->lnum
<= c
->lpt_last
);
1883 ubifs_assert(branch
->offs
>= 0 && branch
->offs
< c
->leb_size
);
1884 err
= ubi_read(c
->ubi
, branch
->lnum
, buf
, branch
->offs
,
1887 return ERR_PTR(err
);
1888 err
= unpack_pnode(c
, buf
, pnode
);
1890 return ERR_PTR(err
);
1892 err
= validate_pnode(c
, pnode
, parent
, iip
);
1894 return ERR_PTR(err
);
1896 pnode
->num
= calc_pnode_num_from_parent(c
, parent
, iip
);
1897 pnode
->parent
= parent
;
1899 set_pnode_lnum(c
, pnode
);
1904 * ubifs_lpt_scan_nolock - scan the LPT.
1905 * @c: the UBIFS file-system description object
1906 * @start_lnum: LEB number from which to start scanning
1907 * @end_lnum: LEB number at which to stop scanning
1908 * @scan_cb: callback function called for each lprops
1909 * @data: data to be passed to the callback function
1911 * This function returns %0 on success and a negative error code on failure.
1913 int ubifs_lpt_scan_nolock(struct ubifs_info
*c
, int start_lnum
, int end_lnum
,
1914 ubifs_lpt_scan_callback scan_cb
, void *data
)
1916 int err
= 0, i
, h
, iip
, shft
;
1917 struct ubifs_nnode
*nnode
;
1918 struct ubifs_pnode
*pnode
;
1919 struct lpt_scan_node
*path
;
1921 if (start_lnum
== -1) {
1922 start_lnum
= end_lnum
+ 1;
1923 if (start_lnum
>= c
->leb_cnt
)
1924 start_lnum
= c
->main_first
;
1927 ubifs_assert(start_lnum
>= c
->main_first
&& start_lnum
< c
->leb_cnt
);
1928 ubifs_assert(end_lnum
>= c
->main_first
&& end_lnum
< c
->leb_cnt
);
1931 err
= ubifs_read_nnode(c
, NULL
, 0);
1936 path
= kmalloc(sizeof(struct lpt_scan_node
) * (c
->lpt_hght
+ 1),
1941 path
[0].ptr
.nnode
= c
->nroot
;
1942 path
[0].in_tree
= 1;
1944 /* Descend to the pnode containing start_lnum */
1946 i
= start_lnum
- c
->main_first
;
1947 shft
= c
->lpt_hght
* UBIFS_LPT_FANOUT_SHIFT
;
1948 for (h
= 1; h
< c
->lpt_hght
; h
++) {
1949 iip
= ((i
>> shft
) & (UBIFS_LPT_FANOUT
- 1));
1950 shft
-= UBIFS_LPT_FANOUT_SHIFT
;
1951 nnode
= scan_get_nnode(c
, path
+ h
, nnode
, iip
);
1952 if (IS_ERR(nnode
)) {
1953 err
= PTR_ERR(nnode
);
1957 iip
= ((i
>> shft
) & (UBIFS_LPT_FANOUT
- 1));
1958 shft
-= UBIFS_LPT_FANOUT_SHIFT
;
1959 pnode
= scan_get_pnode(c
, path
+ h
, nnode
, iip
);
1960 if (IS_ERR(pnode
)) {
1961 err
= PTR_ERR(pnode
);
1964 iip
= (i
& (UBIFS_LPT_FANOUT
- 1));
1966 /* Loop for each lprops */
1968 struct ubifs_lprops
*lprops
= &pnode
->lprops
[iip
];
1969 int ret
, lnum
= lprops
->lnum
;
1971 ret
= scan_cb(c
, lprops
, path
[h
].in_tree
, data
);
1976 if (ret
& LPT_SCAN_ADD
) {
1977 /* Add all the nodes in path to the tree in memory */
1978 for (h
= 1; h
< c
->lpt_hght
; h
++) {
1979 const size_t sz
= sizeof(struct ubifs_nnode
);
1980 struct ubifs_nnode
*parent
;
1982 if (path
[h
].in_tree
)
1984 nnode
= kmalloc(sz
, GFP_NOFS
);
1989 memcpy(nnode
, &path
[h
].nnode
, sz
);
1990 parent
= nnode
->parent
;
1991 parent
->nbranch
[nnode
->iip
].nnode
= nnode
;
1992 path
[h
].ptr
.nnode
= nnode
;
1993 path
[h
].in_tree
= 1;
1994 path
[h
+ 1].cnode
.parent
= nnode
;
1996 if (path
[h
].in_tree
)
1997 ubifs_ensure_cat(c
, lprops
);
1999 const size_t sz
= sizeof(struct ubifs_pnode
);
2000 struct ubifs_nnode
*parent
;
2002 pnode
= kmalloc(sz
, GFP_NOFS
);
2007 memcpy(pnode
, &path
[h
].pnode
, sz
);
2008 parent
= pnode
->parent
;
2009 parent
->nbranch
[pnode
->iip
].pnode
= pnode
;
2010 path
[h
].ptr
.pnode
= pnode
;
2011 path
[h
].in_tree
= 1;
2012 update_cats(c
, pnode
);
2013 c
->pnodes_have
+= 1;
2015 err
= dbg_check_lpt_nodes(c
, (struct ubifs_cnode
*)
2019 err
= dbg_check_cats(c
);
2023 if (ret
& LPT_SCAN_STOP
) {
2027 /* Get the next lprops */
2028 if (lnum
== end_lnum
) {
2030 * We got to the end without finding what we were
2036 if (lnum
+ 1 >= c
->leb_cnt
) {
2037 /* Wrap-around to the beginning */
2038 start_lnum
= c
->main_first
;
2041 if (iip
+ 1 < UBIFS_LPT_FANOUT
) {
2042 /* Next lprops is in the same pnode */
2046 /* We need to get the next pnode. Go up until we can go right */
2050 ubifs_assert(h
>= 0);
2051 nnode
= path
[h
].ptr
.nnode
;
2052 if (iip
+ 1 < UBIFS_LPT_FANOUT
)
2058 /* Descend to the pnode */
2060 for (; h
< c
->lpt_hght
; h
++) {
2061 nnode
= scan_get_nnode(c
, path
+ h
, nnode
, iip
);
2062 if (IS_ERR(nnode
)) {
2063 err
= PTR_ERR(nnode
);
2068 pnode
= scan_get_pnode(c
, path
+ h
, nnode
, iip
);
2069 if (IS_ERR(pnode
)) {
2070 err
= PTR_ERR(pnode
);
2080 #ifdef CONFIG_UBIFS_FS_DEBUG
2083 * dbg_chk_pnode - check a pnode.
2084 * @c: the UBIFS file-system description object
2085 * @pnode: pnode to check
2086 * @col: pnode column
2088 * This function returns %0 on success and a negative error code on failure.
2090 static int dbg_chk_pnode(struct ubifs_info
*c
, struct ubifs_pnode
*pnode
,
2095 if (pnode
->num
!= col
) {
2096 dbg_err("pnode num %d expected %d parent num %d iip %d",
2097 pnode
->num
, col
, pnode
->parent
->num
, pnode
->iip
);
2100 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
2101 struct ubifs_lprops
*lp
, *lprops
= &pnode
->lprops
[i
];
2102 int lnum
= (pnode
->num
<< UBIFS_LPT_FANOUT_SHIFT
) + i
+
2104 int found
, cat
= lprops
->flags
& LPROPS_CAT_MASK
;
2105 struct ubifs_lpt_heap
*heap
;
2106 struct list_head
*list
= NULL
;
2108 if (lnum
>= c
->leb_cnt
)
2110 if (lprops
->lnum
!= lnum
) {
2111 dbg_err("bad LEB number %d expected %d",
2112 lprops
->lnum
, lnum
);
2115 if (lprops
->flags
& LPROPS_TAKEN
) {
2116 if (cat
!= LPROPS_UNCAT
) {
2117 dbg_err("LEB %d taken but not uncat %d",
2123 if (lprops
->flags
& LPROPS_INDEX
) {
2126 case LPROPS_DIRTY_IDX
:
2127 case LPROPS_FRDI_IDX
:
2130 dbg_err("LEB %d index but cat %d",
2140 case LPROPS_FREEABLE
:
2143 dbg_err("LEB %d not index but cat %d",
2150 list
= &c
->uncat_list
;
2153 list
= &c
->empty_list
;
2155 case LPROPS_FREEABLE
:
2156 list
= &c
->freeable_list
;
2158 case LPROPS_FRDI_IDX
:
2159 list
= &c
->frdi_idx_list
;
2165 case LPROPS_DIRTY_IDX
:
2167 heap
= &c
->lpt_heap
[cat
- 1];
2168 if (lprops
->hpos
< heap
->cnt
&&
2169 heap
->arr
[lprops
->hpos
] == lprops
)
2174 case LPROPS_FREEABLE
:
2175 case LPROPS_FRDI_IDX
:
2176 list_for_each_entry(lp
, list
, list
)
2184 dbg_err("LEB %d cat %d not found in cat heap/list",
2190 if (lprops
->free
!= c
->leb_size
) {
2191 dbg_err("LEB %d cat %d free %d dirty %d",
2192 lprops
->lnum
, cat
, lprops
->free
,
2196 case LPROPS_FREEABLE
:
2197 case LPROPS_FRDI_IDX
:
2198 if (lprops
->free
+ lprops
->dirty
!= c
->leb_size
) {
2199 dbg_err("LEB %d cat %d free %d dirty %d",
2200 lprops
->lnum
, cat
, lprops
->free
,
2210 * dbg_check_lpt_nodes - check nnodes and pnodes.
2211 * @c: the UBIFS file-system description object
2212 * @cnode: next cnode (nnode or pnode) to check
2213 * @row: row of cnode (root is zero)
2214 * @col: column of cnode (leftmost is zero)
2216 * This function returns %0 on success and a negative error code on failure.
2218 int dbg_check_lpt_nodes(struct ubifs_info
*c
, struct ubifs_cnode
*cnode
,
2221 struct ubifs_nnode
*nnode
, *nn
;
2222 struct ubifs_cnode
*cn
;
2223 int num
, iip
= 0, err
;
2225 if (!(ubifs_chk_flags
& UBIFS_CHK_LPROPS
))
2229 ubifs_assert(row
>= 0);
2230 nnode
= cnode
->parent
;
2232 /* cnode is a nnode */
2233 num
= calc_nnode_num(row
, col
);
2234 if (cnode
->num
!= num
) {
2235 dbg_err("nnode num %d expected %d "
2236 "parent num %d iip %d", cnode
->num
, num
,
2237 (nnode
? nnode
->num
: 0), cnode
->iip
);
2240 nn
= (struct ubifs_nnode
*)cnode
;
2241 while (iip
< UBIFS_LPT_FANOUT
) {
2242 cn
= nn
->nbranch
[iip
].cnode
;
2246 col
<<= UBIFS_LPT_FANOUT_SHIFT
;
2255 if (iip
< UBIFS_LPT_FANOUT
)
2258 struct ubifs_pnode
*pnode
;
2260 /* cnode is a pnode */
2261 pnode
= (struct ubifs_pnode
*)cnode
;
2262 err
= dbg_chk_pnode(c
, pnode
, col
);
2266 /* Go up and to the right */
2268 col
>>= UBIFS_LPT_FANOUT_SHIFT
;
2269 iip
= cnode
->iip
+ 1;
2270 cnode
= (struct ubifs_cnode
*)nnode
;
2275 #endif /* CONFIG_UBIFS_FS_DEBUG */