]>
git.ipfire.org Git - people/ms/u-boot.git/blob - fs/ubifs/lpt_commit.c
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 commit-related functionality of the LEB properties
19 #include <linux/crc16.h>
20 #include <linux/slab.h>
21 #include <linux/random.h>
23 #include <linux/compat.h>
24 #include <linux/err.h>
30 static int dbg_populate_lsave(struct ubifs_info
*c
);
34 * first_dirty_cnode - find first dirty cnode.
35 * @c: UBIFS file-system description object
36 * @nnode: nnode at which to start
38 * This function returns the first dirty cnode or %NULL if there is not one.
40 static struct ubifs_cnode
*first_dirty_cnode(struct ubifs_nnode
*nnode
)
46 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
47 struct ubifs_cnode
*cnode
;
49 cnode
= nnode
->nbranch
[i
].cnode
;
51 test_bit(DIRTY_CNODE
, &cnode
->flags
)) {
52 if (cnode
->level
== 0)
54 nnode
= (struct ubifs_nnode
*)cnode
;
60 return (struct ubifs_cnode
*)nnode
;
65 * next_dirty_cnode - find next dirty cnode.
66 * @cnode: cnode from which to begin searching
68 * This function returns the next dirty cnode or %NULL if there is not one.
70 static struct ubifs_cnode
*next_dirty_cnode(struct ubifs_cnode
*cnode
)
72 struct ubifs_nnode
*nnode
;
76 nnode
= cnode
->parent
;
79 for (i
= cnode
->iip
+ 1; i
< UBIFS_LPT_FANOUT
; i
++) {
80 cnode
= nnode
->nbranch
[i
].cnode
;
81 if (cnode
&& test_bit(DIRTY_CNODE
, &cnode
->flags
)) {
82 if (cnode
->level
== 0)
83 return cnode
; /* cnode is a pnode */
84 /* cnode is a nnode */
85 return first_dirty_cnode((struct ubifs_nnode
*)cnode
);
88 return (struct ubifs_cnode
*)nnode
;
92 * get_cnodes_to_commit - create list of dirty cnodes to commit.
93 * @c: UBIFS file-system description object
95 * This function returns the number of cnodes to commit.
97 static int get_cnodes_to_commit(struct ubifs_info
*c
)
99 struct ubifs_cnode
*cnode
, *cnext
;
105 if (!test_bit(DIRTY_CNODE
, &c
->nroot
->flags
))
108 c
->lpt_cnext
= first_dirty_cnode(c
->nroot
);
109 cnode
= c
->lpt_cnext
;
114 ubifs_assert(!test_bit(COW_CNODE
, &cnode
->flags
));
115 __set_bit(COW_CNODE
, &cnode
->flags
);
116 cnext
= next_dirty_cnode(cnode
);
118 cnode
->cnext
= c
->lpt_cnext
;
121 cnode
->cnext
= cnext
;
125 dbg_cmt("committing %d cnodes", cnt
);
126 dbg_lp("committing %d cnodes", cnt
);
127 ubifs_assert(cnt
== c
->dirty_nn_cnt
+ c
->dirty_pn_cnt
);
132 * upd_ltab - update LPT LEB properties.
133 * @c: UBIFS file-system description object
135 * @free: amount of free space
136 * @dirty: amount of dirty space to add
138 static void upd_ltab(struct ubifs_info
*c
, int lnum
, int free
, int dirty
)
140 dbg_lp("LEB %d free %d dirty %d to %d +%d",
141 lnum
, c
->ltab
[lnum
- c
->lpt_first
].free
,
142 c
->ltab
[lnum
- c
->lpt_first
].dirty
, free
, dirty
);
143 ubifs_assert(lnum
>= c
->lpt_first
&& lnum
<= c
->lpt_last
);
144 c
->ltab
[lnum
- c
->lpt_first
].free
= free
;
145 c
->ltab
[lnum
- c
->lpt_first
].dirty
+= dirty
;
149 * alloc_lpt_leb - allocate an LPT LEB that is empty.
150 * @c: UBIFS file-system description object
151 * @lnum: LEB number is passed and returned here
153 * This function finds the next empty LEB in the ltab starting from @lnum. If a
154 * an empty LEB is found it is returned in @lnum and the function returns %0.
155 * Otherwise the function returns -ENOSPC. Note however, that LPT is designed
156 * never to run out of space.
158 static int alloc_lpt_leb(struct ubifs_info
*c
, int *lnum
)
162 n
= *lnum
- c
->lpt_first
+ 1;
163 for (i
= n
; i
< c
->lpt_lebs
; i
++) {
164 if (c
->ltab
[i
].tgc
|| c
->ltab
[i
].cmt
)
166 if (c
->ltab
[i
].free
== c
->leb_size
) {
168 *lnum
= i
+ c
->lpt_first
;
173 for (i
= 0; i
< n
; i
++) {
174 if (c
->ltab
[i
].tgc
|| c
->ltab
[i
].cmt
)
176 if (c
->ltab
[i
].free
== c
->leb_size
) {
178 *lnum
= i
+ c
->lpt_first
;
186 * layout_cnodes - layout cnodes for commit.
187 * @c: UBIFS file-system description object
189 * This function returns %0 on success and a negative error code on failure.
191 static int layout_cnodes(struct ubifs_info
*c
)
193 int lnum
, offs
, len
, alen
, done_lsave
, done_ltab
, err
;
194 struct ubifs_cnode
*cnode
;
196 err
= dbg_chk_lpt_sz(c
, 0, 0);
199 cnode
= c
->lpt_cnext
;
202 lnum
= c
->nhead_lnum
;
203 offs
= c
->nhead_offs
;
204 /* Try to place lsave and ltab nicely */
205 done_lsave
= !c
->big_lpt
;
207 if (!done_lsave
&& offs
+ c
->lsave_sz
<= c
->leb_size
) {
209 c
->lsave_lnum
= lnum
;
210 c
->lsave_offs
= offs
;
212 dbg_chk_lpt_sz(c
, 1, c
->lsave_sz
);
215 if (offs
+ c
->ltab_sz
<= c
->leb_size
) {
220 dbg_chk_lpt_sz(c
, 1, c
->ltab_sz
);
226 c
->dirty_nn_cnt
-= 1;
229 c
->dirty_pn_cnt
-= 1;
231 while (offs
+ len
> c
->leb_size
) {
232 alen
= ALIGN(offs
, c
->min_io_size
);
233 upd_ltab(c
, lnum
, c
->leb_size
- alen
, alen
- offs
);
234 dbg_chk_lpt_sz(c
, 2, c
->leb_size
- offs
);
235 err
= alloc_lpt_leb(c
, &lnum
);
239 ubifs_assert(lnum
>= c
->lpt_first
&&
240 lnum
<= c
->lpt_last
);
241 /* Try to place lsave and ltab nicely */
244 c
->lsave_lnum
= lnum
;
245 c
->lsave_offs
= offs
;
247 dbg_chk_lpt_sz(c
, 1, c
->lsave_sz
);
255 dbg_chk_lpt_sz(c
, 1, c
->ltab_sz
);
261 cnode
->parent
->nbranch
[cnode
->iip
].lnum
= lnum
;
262 cnode
->parent
->nbranch
[cnode
->iip
].offs
= offs
;
268 dbg_chk_lpt_sz(c
, 1, len
);
269 cnode
= cnode
->cnext
;
270 } while (cnode
&& cnode
!= c
->lpt_cnext
);
272 /* Make sure to place LPT's save table */
274 if (offs
+ c
->lsave_sz
> c
->leb_size
) {
275 alen
= ALIGN(offs
, c
->min_io_size
);
276 upd_ltab(c
, lnum
, c
->leb_size
- alen
, alen
- offs
);
277 dbg_chk_lpt_sz(c
, 2, c
->leb_size
- offs
);
278 err
= alloc_lpt_leb(c
, &lnum
);
282 ubifs_assert(lnum
>= c
->lpt_first
&&
283 lnum
<= c
->lpt_last
);
286 c
->lsave_lnum
= lnum
;
287 c
->lsave_offs
= offs
;
289 dbg_chk_lpt_sz(c
, 1, c
->lsave_sz
);
292 /* Make sure to place LPT's own lprops table */
294 if (offs
+ c
->ltab_sz
> c
->leb_size
) {
295 alen
= ALIGN(offs
, c
->min_io_size
);
296 upd_ltab(c
, lnum
, c
->leb_size
- alen
, alen
- offs
);
297 dbg_chk_lpt_sz(c
, 2, c
->leb_size
- offs
);
298 err
= alloc_lpt_leb(c
, &lnum
);
302 ubifs_assert(lnum
>= c
->lpt_first
&&
303 lnum
<= c
->lpt_last
);
309 dbg_chk_lpt_sz(c
, 1, c
->ltab_sz
);
312 alen
= ALIGN(offs
, c
->min_io_size
);
313 upd_ltab(c
, lnum
, c
->leb_size
- alen
, alen
- offs
);
314 dbg_chk_lpt_sz(c
, 4, alen
- offs
);
315 err
= dbg_chk_lpt_sz(c
, 3, alen
);
321 ubifs_err("LPT out of space at LEB %d:%d needing %d, done_ltab %d, done_lsave %d",
322 lnum
, offs
, len
, done_ltab
, done_lsave
);
323 ubifs_dump_lpt_info(c
);
324 ubifs_dump_lpt_lebs(c
);
331 * realloc_lpt_leb - allocate an LPT LEB that is empty.
332 * @c: UBIFS file-system description object
333 * @lnum: LEB number is passed and returned here
335 * This function duplicates exactly the results of the function alloc_lpt_leb.
336 * It is used during end commit to reallocate the same LEB numbers that were
337 * allocated by alloc_lpt_leb during start commit.
339 * This function finds the next LEB that was allocated by the alloc_lpt_leb
340 * function starting from @lnum. If a LEB is found it is returned in @lnum and
341 * the function returns %0. Otherwise the function returns -ENOSPC.
342 * Note however, that LPT is designed never to run out of space.
344 static int realloc_lpt_leb(struct ubifs_info
*c
, int *lnum
)
348 n
= *lnum
- c
->lpt_first
+ 1;
349 for (i
= n
; i
< c
->lpt_lebs
; i
++)
350 if (c
->ltab
[i
].cmt
) {
352 *lnum
= i
+ c
->lpt_first
;
356 for (i
= 0; i
< n
; i
++)
357 if (c
->ltab
[i
].cmt
) {
359 *lnum
= i
+ c
->lpt_first
;
366 * write_cnodes - write cnodes for commit.
367 * @c: UBIFS file-system description object
369 * This function returns %0 on success and a negative error code on failure.
371 static int write_cnodes(struct ubifs_info
*c
)
373 int lnum
, offs
, len
, from
, err
, wlen
, alen
, done_ltab
, done_lsave
;
374 struct ubifs_cnode
*cnode
;
375 void *buf
= c
->lpt_buf
;
377 cnode
= c
->lpt_cnext
;
380 lnum
= c
->nhead_lnum
;
381 offs
= c
->nhead_offs
;
383 /* Ensure empty LEB is unmapped */
385 err
= ubifs_leb_unmap(c
, lnum
);
389 /* Try to place lsave and ltab nicely */
390 done_lsave
= !c
->big_lpt
;
392 if (!done_lsave
&& offs
+ c
->lsave_sz
<= c
->leb_size
) {
394 ubifs_pack_lsave(c
, buf
+ offs
, c
->lsave
);
396 dbg_chk_lpt_sz(c
, 1, c
->lsave_sz
);
399 if (offs
+ c
->ltab_sz
<= c
->leb_size
) {
401 ubifs_pack_ltab(c
, buf
+ offs
, c
->ltab_cmt
);
403 dbg_chk_lpt_sz(c
, 1, c
->ltab_sz
);
406 /* Loop for each cnode */
412 while (offs
+ len
> c
->leb_size
) {
415 alen
= ALIGN(wlen
, c
->min_io_size
);
416 memset(buf
+ offs
, 0xff, alen
- wlen
);
417 err
= ubifs_leb_write(c
, lnum
, buf
+ from
, from
,
422 dbg_chk_lpt_sz(c
, 2, c
->leb_size
- offs
);
423 err
= realloc_lpt_leb(c
, &lnum
);
427 ubifs_assert(lnum
>= c
->lpt_first
&&
428 lnum
<= c
->lpt_last
);
429 err
= ubifs_leb_unmap(c
, lnum
);
432 /* Try to place lsave and ltab nicely */
435 ubifs_pack_lsave(c
, buf
+ offs
, c
->lsave
);
437 dbg_chk_lpt_sz(c
, 1, c
->lsave_sz
);
442 ubifs_pack_ltab(c
, buf
+ offs
, c
->ltab_cmt
);
444 dbg_chk_lpt_sz(c
, 1, c
->ltab_sz
);
450 ubifs_pack_nnode(c
, buf
+ offs
,
451 (struct ubifs_nnode
*)cnode
);
453 ubifs_pack_pnode(c
, buf
+ offs
,
454 (struct ubifs_pnode
*)cnode
);
456 * The reason for the barriers is the same as in case of TNC.
457 * See comment in 'write_index()'. 'dirty_cow_nnode()' and
458 * 'dirty_cow_pnode()' are the functions for which this is
461 clear_bit(DIRTY_CNODE
, &cnode
->flags
);
462 smp_mb__before_clear_bit();
463 clear_bit(COW_CNODE
, &cnode
->flags
);
464 smp_mb__after_clear_bit();
466 dbg_chk_lpt_sz(c
, 1, len
);
467 cnode
= cnode
->cnext
;
468 } while (cnode
&& cnode
!= c
->lpt_cnext
);
470 /* Make sure to place LPT's save table */
472 if (offs
+ c
->lsave_sz
> c
->leb_size
) {
474 alen
= ALIGN(wlen
, c
->min_io_size
);
475 memset(buf
+ offs
, 0xff, alen
- wlen
);
476 err
= ubifs_leb_write(c
, lnum
, buf
+ from
, from
, alen
);
479 dbg_chk_lpt_sz(c
, 2, c
->leb_size
- offs
);
480 err
= realloc_lpt_leb(c
, &lnum
);
484 ubifs_assert(lnum
>= c
->lpt_first
&&
485 lnum
<= c
->lpt_last
);
486 err
= ubifs_leb_unmap(c
, lnum
);
491 ubifs_pack_lsave(c
, buf
+ offs
, c
->lsave
);
493 dbg_chk_lpt_sz(c
, 1, c
->lsave_sz
);
496 /* Make sure to place LPT's own lprops table */
498 if (offs
+ c
->ltab_sz
> c
->leb_size
) {
500 alen
= ALIGN(wlen
, c
->min_io_size
);
501 memset(buf
+ offs
, 0xff, alen
- wlen
);
502 err
= ubifs_leb_write(c
, lnum
, buf
+ from
, from
, alen
);
505 dbg_chk_lpt_sz(c
, 2, c
->leb_size
- offs
);
506 err
= realloc_lpt_leb(c
, &lnum
);
510 ubifs_assert(lnum
>= c
->lpt_first
&&
511 lnum
<= c
->lpt_last
);
512 err
= ubifs_leb_unmap(c
, lnum
);
517 ubifs_pack_ltab(c
, buf
+ offs
, c
->ltab_cmt
);
519 dbg_chk_lpt_sz(c
, 1, c
->ltab_sz
);
522 /* Write remaining data in buffer */
524 alen
= ALIGN(wlen
, c
->min_io_size
);
525 memset(buf
+ offs
, 0xff, alen
- wlen
);
526 err
= ubifs_leb_write(c
, lnum
, buf
+ from
, from
, alen
);
530 dbg_chk_lpt_sz(c
, 4, alen
- wlen
);
531 err
= dbg_chk_lpt_sz(c
, 3, ALIGN(offs
, c
->min_io_size
));
535 c
->nhead_lnum
= lnum
;
536 c
->nhead_offs
= ALIGN(offs
, c
->min_io_size
);
538 dbg_lp("LPT root is at %d:%d", c
->lpt_lnum
, c
->lpt_offs
);
539 dbg_lp("LPT head is at %d:%d", c
->nhead_lnum
, c
->nhead_offs
);
540 dbg_lp("LPT ltab is at %d:%d", c
->ltab_lnum
, c
->ltab_offs
);
542 dbg_lp("LPT lsave is at %d:%d", c
->lsave_lnum
, c
->lsave_offs
);
547 ubifs_err("LPT out of space mismatch at LEB %d:%d needing %d, done_ltab %d, done_lsave %d",
548 lnum
, offs
, len
, done_ltab
, done_lsave
);
549 ubifs_dump_lpt_info(c
);
550 ubifs_dump_lpt_lebs(c
);
557 * next_pnode_to_dirty - find next pnode to dirty.
558 * @c: UBIFS file-system description object
561 * This function returns the next pnode to dirty or %NULL if there are no more
562 * pnodes. Note that pnodes that have never been written (lnum == 0) are
565 static struct ubifs_pnode
*next_pnode_to_dirty(struct ubifs_info
*c
,
566 struct ubifs_pnode
*pnode
)
568 struct ubifs_nnode
*nnode
;
571 /* Try to go right */
572 nnode
= pnode
->parent
;
573 for (iip
= pnode
->iip
+ 1; iip
< UBIFS_LPT_FANOUT
; iip
++) {
574 if (nnode
->nbranch
[iip
].lnum
)
575 return ubifs_get_pnode(c
, nnode
, iip
);
578 /* Go up while can't go right */
580 iip
= nnode
->iip
+ 1;
581 nnode
= nnode
->parent
;
584 for (; iip
< UBIFS_LPT_FANOUT
; iip
++) {
585 if (nnode
->nbranch
[iip
].lnum
)
588 } while (iip
>= UBIFS_LPT_FANOUT
);
591 nnode
= ubifs_get_nnode(c
, nnode
, iip
);
593 return (void *)nnode
;
595 /* Go down to level 1 */
596 while (nnode
->level
> 1) {
597 for (iip
= 0; iip
< UBIFS_LPT_FANOUT
; iip
++) {
598 if (nnode
->nbranch
[iip
].lnum
)
601 if (iip
>= UBIFS_LPT_FANOUT
) {
603 * Should not happen, but we need to keep going
608 nnode
= ubifs_get_nnode(c
, nnode
, iip
);
610 return (void *)nnode
;
613 for (iip
= 0; iip
< UBIFS_LPT_FANOUT
; iip
++)
614 if (nnode
->nbranch
[iip
].lnum
)
616 if (iip
>= UBIFS_LPT_FANOUT
)
617 /* Should not happen, but we need to keep going if it does */
619 return ubifs_get_pnode(c
, nnode
, iip
);
623 * pnode_lookup - lookup a pnode in the LPT.
624 * @c: UBIFS file-system description object
625 * @i: pnode number (0 to main_lebs - 1)
627 * This function returns a pointer to the pnode on success or a negative
628 * error code on failure.
630 static struct ubifs_pnode
*pnode_lookup(struct ubifs_info
*c
, int i
)
632 int err
, h
, iip
, shft
;
633 struct ubifs_nnode
*nnode
;
636 err
= ubifs_read_nnode(c
, NULL
, 0);
640 i
<<= UBIFS_LPT_FANOUT_SHIFT
;
642 shft
= c
->lpt_hght
* UBIFS_LPT_FANOUT_SHIFT
;
643 for (h
= 1; h
< c
->lpt_hght
; h
++) {
644 iip
= ((i
>> shft
) & (UBIFS_LPT_FANOUT
- 1));
645 shft
-= UBIFS_LPT_FANOUT_SHIFT
;
646 nnode
= ubifs_get_nnode(c
, nnode
, iip
);
648 return ERR_CAST(nnode
);
650 iip
= ((i
>> shft
) & (UBIFS_LPT_FANOUT
- 1));
651 return ubifs_get_pnode(c
, nnode
, iip
);
655 * add_pnode_dirt - add dirty space to LPT LEB properties.
656 * @c: UBIFS file-system description object
657 * @pnode: pnode for which to add dirt
659 static void add_pnode_dirt(struct ubifs_info
*c
, struct ubifs_pnode
*pnode
)
661 ubifs_add_lpt_dirt(c
, pnode
->parent
->nbranch
[pnode
->iip
].lnum
,
666 * do_make_pnode_dirty - mark a pnode dirty.
667 * @c: UBIFS file-system description object
668 * @pnode: pnode to mark dirty
670 static void do_make_pnode_dirty(struct ubifs_info
*c
, struct ubifs_pnode
*pnode
)
672 /* Assumes cnext list is empty i.e. not called during commit */
673 if (!test_and_set_bit(DIRTY_CNODE
, &pnode
->flags
)) {
674 struct ubifs_nnode
*nnode
;
676 c
->dirty_pn_cnt
+= 1;
677 add_pnode_dirt(c
, pnode
);
678 /* Mark parent and ancestors dirty too */
679 nnode
= pnode
->parent
;
681 if (!test_and_set_bit(DIRTY_CNODE
, &nnode
->flags
)) {
682 c
->dirty_nn_cnt
+= 1;
683 ubifs_add_nnode_dirt(c
, nnode
);
684 nnode
= nnode
->parent
;
692 * make_tree_dirty - mark the entire LEB properties tree dirty.
693 * @c: UBIFS file-system description object
695 * This function is used by the "small" LPT model to cause the entire LEB
696 * properties tree to be written. The "small" LPT model does not use LPT
697 * garbage collection because it is more efficient to write the entire tree
698 * (because it is small).
700 * This function returns %0 on success and a negative error code on failure.
702 static int make_tree_dirty(struct ubifs_info
*c
)
704 struct ubifs_pnode
*pnode
;
706 pnode
= pnode_lookup(c
, 0);
708 return PTR_ERR(pnode
);
711 do_make_pnode_dirty(c
, pnode
);
712 pnode
= next_pnode_to_dirty(c
, pnode
);
714 return PTR_ERR(pnode
);
720 * need_write_all - determine if the LPT area is running out of free space.
721 * @c: UBIFS file-system description object
723 * This function returns %1 if the LPT area is running out of free space and %0
726 static int need_write_all(struct ubifs_info
*c
)
731 for (i
= 0; i
< c
->lpt_lebs
; i
++) {
732 if (i
+ c
->lpt_first
== c
->nhead_lnum
)
733 free
+= c
->leb_size
- c
->nhead_offs
;
734 else if (c
->ltab
[i
].free
== c
->leb_size
)
736 else if (c
->ltab
[i
].free
+ c
->ltab
[i
].dirty
== c
->leb_size
)
739 /* Less than twice the size left */
740 if (free
<= c
->lpt_sz
* 2)
746 * lpt_tgc_start - start trivial garbage collection of LPT LEBs.
747 * @c: UBIFS file-system description object
749 * LPT trivial garbage collection is where a LPT LEB contains only dirty and
750 * free space and so may be reused as soon as the next commit is completed.
751 * This function is called during start commit to mark LPT LEBs for trivial GC.
753 static void lpt_tgc_start(struct ubifs_info
*c
)
757 for (i
= 0; i
< c
->lpt_lebs
; i
++) {
758 if (i
+ c
->lpt_first
== c
->nhead_lnum
)
760 if (c
->ltab
[i
].dirty
> 0 &&
761 c
->ltab
[i
].free
+ c
->ltab
[i
].dirty
== c
->leb_size
) {
763 c
->ltab
[i
].free
= c
->leb_size
;
764 c
->ltab
[i
].dirty
= 0;
765 dbg_lp("LEB %d", i
+ c
->lpt_first
);
771 * lpt_tgc_end - end trivial garbage collection of LPT LEBs.
772 * @c: UBIFS file-system description object
774 * LPT trivial garbage collection is where a LPT LEB contains only dirty and
775 * free space and so may be reused as soon as the next commit is completed.
776 * This function is called after the commit is completed (master node has been
777 * written) and un-maps LPT LEBs that were marked for trivial GC.
779 static int lpt_tgc_end(struct ubifs_info
*c
)
783 for (i
= 0; i
< c
->lpt_lebs
; i
++)
784 if (c
->ltab
[i
].tgc
) {
785 err
= ubifs_leb_unmap(c
, i
+ c
->lpt_first
);
789 dbg_lp("LEB %d", i
+ c
->lpt_first
);
795 * populate_lsave - fill the lsave array with important LEB numbers.
796 * @c: the UBIFS file-system description object
798 * This function is only called for the "big" model. It records a small number
799 * of LEB numbers of important LEBs. Important LEBs are ones that are (from
800 * most important to least important): empty, freeable, freeable index, dirty
801 * index, dirty or free. Upon mount, we read this list of LEB numbers and bring
802 * their pnodes into memory. That will stop us from having to scan the LPT
803 * straight away. For the "small" model we assume that scanning the LPT is no
806 static void populate_lsave(struct ubifs_info
*c
)
808 struct ubifs_lprops
*lprops
;
809 struct ubifs_lpt_heap
*heap
;
812 ubifs_assert(c
->big_lpt
);
813 if (!(c
->lpt_drty_flgs
& LSAVE_DIRTY
)) {
814 c
->lpt_drty_flgs
|= LSAVE_DIRTY
;
815 ubifs_add_lpt_dirt(c
, c
->lsave_lnum
, c
->lsave_sz
);
819 if (dbg_populate_lsave(c
))
823 list_for_each_entry(lprops
, &c
->empty_list
, list
) {
824 c
->lsave
[cnt
++] = lprops
->lnum
;
825 if (cnt
>= c
->lsave_cnt
)
828 list_for_each_entry(lprops
, &c
->freeable_list
, list
) {
829 c
->lsave
[cnt
++] = lprops
->lnum
;
830 if (cnt
>= c
->lsave_cnt
)
833 list_for_each_entry(lprops
, &c
->frdi_idx_list
, list
) {
834 c
->lsave
[cnt
++] = lprops
->lnum
;
835 if (cnt
>= c
->lsave_cnt
)
838 heap
= &c
->lpt_heap
[LPROPS_DIRTY_IDX
- 1];
839 for (i
= 0; i
< heap
->cnt
; i
++) {
840 c
->lsave
[cnt
++] = heap
->arr
[i
]->lnum
;
841 if (cnt
>= c
->lsave_cnt
)
844 heap
= &c
->lpt_heap
[LPROPS_DIRTY
- 1];
845 for (i
= 0; i
< heap
->cnt
; i
++) {
846 c
->lsave
[cnt
++] = heap
->arr
[i
]->lnum
;
847 if (cnt
>= c
->lsave_cnt
)
850 heap
= &c
->lpt_heap
[LPROPS_FREE
- 1];
851 for (i
= 0; i
< heap
->cnt
; i
++) {
852 c
->lsave
[cnt
++] = heap
->arr
[i
]->lnum
;
853 if (cnt
>= c
->lsave_cnt
)
856 /* Fill it up completely */
857 while (cnt
< c
->lsave_cnt
)
858 c
->lsave
[cnt
++] = c
->main_first
;
862 * nnode_lookup - lookup a nnode in the LPT.
863 * @c: UBIFS file-system description object
866 * This function returns a pointer to the nnode on success or a negative
867 * error code on failure.
869 static struct ubifs_nnode
*nnode_lookup(struct ubifs_info
*c
, int i
)
872 struct ubifs_nnode
*nnode
;
875 err
= ubifs_read_nnode(c
, NULL
, 0);
881 iip
= i
& (UBIFS_LPT_FANOUT
- 1);
882 i
>>= UBIFS_LPT_FANOUT_SHIFT
;
885 nnode
= ubifs_get_nnode(c
, nnode
, iip
);
893 * make_nnode_dirty - find a nnode and, if found, make it dirty.
894 * @c: UBIFS file-system description object
895 * @node_num: nnode number of nnode to make dirty
896 * @lnum: LEB number where nnode was written
897 * @offs: offset where nnode was written
899 * This function is used by LPT garbage collection. LPT garbage collection is
900 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
901 * simply involves marking all the nodes in the LEB being garbage-collected as
902 * dirty. The dirty nodes are written next commit, after which the LEB is free
905 * This function returns %0 on success and a negative error code on failure.
907 static int make_nnode_dirty(struct ubifs_info
*c
, int node_num
, int lnum
,
910 struct ubifs_nnode
*nnode
;
912 nnode
= nnode_lookup(c
, node_num
);
914 return PTR_ERR(nnode
);
916 struct ubifs_nbranch
*branch
;
918 branch
= &nnode
->parent
->nbranch
[nnode
->iip
];
919 if (branch
->lnum
!= lnum
|| branch
->offs
!= offs
)
920 return 0; /* nnode is obsolete */
921 } else if (c
->lpt_lnum
!= lnum
|| c
->lpt_offs
!= offs
)
922 return 0; /* nnode is obsolete */
923 /* Assumes cnext list is empty i.e. not called during commit */
924 if (!test_and_set_bit(DIRTY_CNODE
, &nnode
->flags
)) {
925 c
->dirty_nn_cnt
+= 1;
926 ubifs_add_nnode_dirt(c
, nnode
);
927 /* Mark parent and ancestors dirty too */
928 nnode
= nnode
->parent
;
930 if (!test_and_set_bit(DIRTY_CNODE
, &nnode
->flags
)) {
931 c
->dirty_nn_cnt
+= 1;
932 ubifs_add_nnode_dirt(c
, nnode
);
933 nnode
= nnode
->parent
;
942 * make_pnode_dirty - find a pnode and, if found, make it dirty.
943 * @c: UBIFS file-system description object
944 * @node_num: pnode number of pnode to make dirty
945 * @lnum: LEB number where pnode was written
946 * @offs: offset where pnode was written
948 * This function is used by LPT garbage collection. LPT garbage collection is
949 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
950 * simply involves marking all the nodes in the LEB being garbage-collected as
951 * dirty. The dirty nodes are written next commit, after which the LEB is free
954 * This function returns %0 on success and a negative error code on failure.
956 static int make_pnode_dirty(struct ubifs_info
*c
, int node_num
, int lnum
,
959 struct ubifs_pnode
*pnode
;
960 struct ubifs_nbranch
*branch
;
962 pnode
= pnode_lookup(c
, node_num
);
964 return PTR_ERR(pnode
);
965 branch
= &pnode
->parent
->nbranch
[pnode
->iip
];
966 if (branch
->lnum
!= lnum
|| branch
->offs
!= offs
)
968 do_make_pnode_dirty(c
, pnode
);
973 * make_ltab_dirty - make ltab node dirty.
974 * @c: UBIFS file-system description object
975 * @lnum: LEB number where ltab was written
976 * @offs: offset where ltab was written
978 * This function is used by LPT garbage collection. LPT garbage collection is
979 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
980 * simply involves marking all the nodes in the LEB being garbage-collected as
981 * dirty. The dirty nodes are written next commit, after which the LEB is free
984 * This function returns %0 on success and a negative error code on failure.
986 static int make_ltab_dirty(struct ubifs_info
*c
, int lnum
, int offs
)
988 if (lnum
!= c
->ltab_lnum
|| offs
!= c
->ltab_offs
)
989 return 0; /* This ltab node is obsolete */
990 if (!(c
->lpt_drty_flgs
& LTAB_DIRTY
)) {
991 c
->lpt_drty_flgs
|= LTAB_DIRTY
;
992 ubifs_add_lpt_dirt(c
, c
->ltab_lnum
, c
->ltab_sz
);
998 * make_lsave_dirty - make lsave node dirty.
999 * @c: UBIFS file-system description object
1000 * @lnum: LEB number where lsave was written
1001 * @offs: offset where lsave was written
1003 * This function is used by LPT garbage collection. LPT garbage collection is
1004 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
1005 * simply involves marking all the nodes in the LEB being garbage-collected as
1006 * dirty. The dirty nodes are written next commit, after which the LEB is free
1009 * This function returns %0 on success and a negative error code on failure.
1011 static int make_lsave_dirty(struct ubifs_info
*c
, int lnum
, int offs
)
1013 if (lnum
!= c
->lsave_lnum
|| offs
!= c
->lsave_offs
)
1014 return 0; /* This lsave node is obsolete */
1015 if (!(c
->lpt_drty_flgs
& LSAVE_DIRTY
)) {
1016 c
->lpt_drty_flgs
|= LSAVE_DIRTY
;
1017 ubifs_add_lpt_dirt(c
, c
->lsave_lnum
, c
->lsave_sz
);
1023 * make_node_dirty - make node dirty.
1024 * @c: UBIFS file-system description object
1025 * @node_type: LPT node type
1026 * @node_num: node number
1027 * @lnum: LEB number where node was written
1028 * @offs: offset where node was written
1030 * This function is used by LPT garbage collection. LPT garbage collection is
1031 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
1032 * simply involves marking all the nodes in the LEB being garbage-collected as
1033 * dirty. The dirty nodes are written next commit, after which the LEB is free
1036 * This function returns %0 on success and a negative error code on failure.
1038 static int make_node_dirty(struct ubifs_info
*c
, int node_type
, int node_num
,
1041 switch (node_type
) {
1042 case UBIFS_LPT_NNODE
:
1043 return make_nnode_dirty(c
, node_num
, lnum
, offs
);
1044 case UBIFS_LPT_PNODE
:
1045 return make_pnode_dirty(c
, node_num
, lnum
, offs
);
1046 case UBIFS_LPT_LTAB
:
1047 return make_ltab_dirty(c
, lnum
, offs
);
1048 case UBIFS_LPT_LSAVE
:
1049 return make_lsave_dirty(c
, lnum
, offs
);
1055 * get_lpt_node_len - return the length of a node based on its type.
1056 * @c: UBIFS file-system description object
1057 * @node_type: LPT node type
1059 static int get_lpt_node_len(const struct ubifs_info
*c
, int node_type
)
1061 switch (node_type
) {
1062 case UBIFS_LPT_NNODE
:
1064 case UBIFS_LPT_PNODE
:
1066 case UBIFS_LPT_LTAB
:
1068 case UBIFS_LPT_LSAVE
:
1075 * get_pad_len - return the length of padding in a buffer.
1076 * @c: UBIFS file-system description object
1078 * @len: length of buffer
1080 static int get_pad_len(const struct ubifs_info
*c
, uint8_t *buf
, int len
)
1084 if (c
->min_io_size
== 1)
1086 offs
= c
->leb_size
- len
;
1087 pad_len
= ALIGN(offs
, c
->min_io_size
) - offs
;
1092 * get_lpt_node_type - return type (and node number) of a node in a buffer.
1093 * @c: UBIFS file-system description object
1095 * @node_num: node number is returned here
1097 static int get_lpt_node_type(const struct ubifs_info
*c
, uint8_t *buf
,
1100 uint8_t *addr
= buf
+ UBIFS_LPT_CRC_BYTES
;
1101 int pos
= 0, node_type
;
1103 node_type
= ubifs_unpack_bits(&addr
, &pos
, UBIFS_LPT_TYPE_BITS
);
1104 *node_num
= ubifs_unpack_bits(&addr
, &pos
, c
->pcnt_bits
);
1109 * is_a_node - determine if a buffer contains a node.
1110 * @c: UBIFS file-system description object
1112 * @len: length of buffer
1114 * This function returns %1 if the buffer contains a node or %0 if it does not.
1116 static int is_a_node(const struct ubifs_info
*c
, uint8_t *buf
, int len
)
1118 uint8_t *addr
= buf
+ UBIFS_LPT_CRC_BYTES
;
1119 int pos
= 0, node_type
, node_len
;
1120 uint16_t crc
, calc_crc
;
1122 if (len
< UBIFS_LPT_CRC_BYTES
+ (UBIFS_LPT_TYPE_BITS
+ 7) / 8)
1124 node_type
= ubifs_unpack_bits(&addr
, &pos
, UBIFS_LPT_TYPE_BITS
);
1125 if (node_type
== UBIFS_LPT_NOT_A_NODE
)
1127 node_len
= get_lpt_node_len(c
, node_type
);
1128 if (!node_len
|| node_len
> len
)
1132 crc
= ubifs_unpack_bits(&addr
, &pos
, UBIFS_LPT_CRC_BITS
);
1133 calc_crc
= crc16(-1, buf
+ UBIFS_LPT_CRC_BYTES
,
1134 node_len
- UBIFS_LPT_CRC_BYTES
);
1135 if (crc
!= calc_crc
)
1141 * lpt_gc_lnum - garbage collect a LPT LEB.
1142 * @c: UBIFS file-system description object
1143 * @lnum: LEB number to garbage collect
1145 * LPT garbage collection is used only for the "big" LPT model
1146 * (c->big_lpt == 1). Garbage collection simply involves marking all the nodes
1147 * in the LEB being garbage-collected as dirty. The dirty nodes are written
1148 * next commit, after which the LEB is free to be reused.
1150 * This function returns %0 on success and a negative error code on failure.
1152 static int lpt_gc_lnum(struct ubifs_info
*c
, int lnum
)
1154 int err
, len
= c
->leb_size
, node_type
, node_num
, node_len
, offs
;
1155 void *buf
= c
->lpt_buf
;
1157 dbg_lp("LEB %d", lnum
);
1159 err
= ubifs_leb_read(c
, lnum
, buf
, 0, c
->leb_size
, 1);
1164 if (!is_a_node(c
, buf
, len
)) {
1167 pad_len
= get_pad_len(c
, buf
, len
);
1175 node_type
= get_lpt_node_type(c
, buf
, &node_num
);
1176 node_len
= get_lpt_node_len(c
, node_type
);
1177 offs
= c
->leb_size
- len
;
1178 ubifs_assert(node_len
!= 0);
1179 mutex_lock(&c
->lp_mutex
);
1180 err
= make_node_dirty(c
, node_type
, node_num
, lnum
, offs
);
1181 mutex_unlock(&c
->lp_mutex
);
1191 * lpt_gc - LPT garbage collection.
1192 * @c: UBIFS file-system description object
1194 * Select a LPT LEB for LPT garbage collection and call 'lpt_gc_lnum()'.
1195 * Returns %0 on success and a negative error code on failure.
1197 static int lpt_gc(struct ubifs_info
*c
)
1199 int i
, lnum
= -1, dirty
= 0;
1201 mutex_lock(&c
->lp_mutex
);
1202 for (i
= 0; i
< c
->lpt_lebs
; i
++) {
1203 ubifs_assert(!c
->ltab
[i
].tgc
);
1204 if (i
+ c
->lpt_first
== c
->nhead_lnum
||
1205 c
->ltab
[i
].free
+ c
->ltab
[i
].dirty
== c
->leb_size
)
1207 if (c
->ltab
[i
].dirty
> dirty
) {
1208 dirty
= c
->ltab
[i
].dirty
;
1209 lnum
= i
+ c
->lpt_first
;
1212 mutex_unlock(&c
->lp_mutex
);
1215 return lpt_gc_lnum(c
, lnum
);
1219 * ubifs_lpt_start_commit - UBIFS commit starts.
1220 * @c: the UBIFS file-system description object
1222 * This function has to be called when UBIFS starts the commit operation.
1223 * This function "freezes" all currently dirty LEB properties and does not
1224 * change them anymore. Further changes are saved and tracked separately
1225 * because they are not part of this commit. This function returns zero in case
1226 * of success and a negative error code in case of failure.
1228 int ubifs_lpt_start_commit(struct ubifs_info
*c
)
1234 mutex_lock(&c
->lp_mutex
);
1235 err
= dbg_chk_lpt_free_spc(c
);
1238 err
= dbg_check_ltab(c
);
1242 if (c
->check_lpt_free
) {
1244 * We ensure there is enough free space in
1245 * ubifs_lpt_post_commit() by marking nodes dirty. That
1246 * information is lost when we unmount, so we also need
1247 * to check free space once after mounting also.
1249 c
->check_lpt_free
= 0;
1250 while (need_write_all(c
)) {
1251 mutex_unlock(&c
->lp_mutex
);
1255 mutex_lock(&c
->lp_mutex
);
1261 if (!c
->dirty_pn_cnt
) {
1262 dbg_cmt("no cnodes to commit");
1267 if (!c
->big_lpt
&& need_write_all(c
)) {
1268 /* If needed, write everything */
1269 err
= make_tree_dirty(c
);
1278 cnt
= get_cnodes_to_commit(c
);
1279 ubifs_assert(cnt
!= 0);
1281 err
= layout_cnodes(c
);
1285 /* Copy the LPT's own lprops for end commit to write */
1286 memcpy(c
->ltab_cmt
, c
->ltab
,
1287 sizeof(struct ubifs_lpt_lprops
) * c
->lpt_lebs
);
1288 c
->lpt_drty_flgs
&= ~(LTAB_DIRTY
| LSAVE_DIRTY
);
1291 mutex_unlock(&c
->lp_mutex
);
1296 * free_obsolete_cnodes - free obsolete cnodes for commit end.
1297 * @c: UBIFS file-system description object
1299 static void free_obsolete_cnodes(struct ubifs_info
*c
)
1301 struct ubifs_cnode
*cnode
, *cnext
;
1303 cnext
= c
->lpt_cnext
;
1308 cnext
= cnode
->cnext
;
1309 if (test_bit(OBSOLETE_CNODE
, &cnode
->flags
))
1312 cnode
->cnext
= NULL
;
1313 } while (cnext
!= c
->lpt_cnext
);
1314 c
->lpt_cnext
= NULL
;
1319 * ubifs_lpt_end_commit - finish the commit operation.
1320 * @c: the UBIFS file-system description object
1322 * This function has to be called when the commit operation finishes. It
1323 * flushes the changes which were "frozen" by 'ubifs_lprops_start_commit()' to
1324 * the media. Returns zero in case of success and a negative error code in case
1327 int ubifs_lpt_end_commit(struct ubifs_info
*c
)
1336 err
= write_cnodes(c
);
1340 mutex_lock(&c
->lp_mutex
);
1341 free_obsolete_cnodes(c
);
1342 mutex_unlock(&c
->lp_mutex
);
1349 * ubifs_lpt_post_commit - post commit LPT trivial GC and LPT GC.
1350 * @c: UBIFS file-system description object
1352 * LPT trivial GC is completed after a commit. Also LPT GC is done after a
1353 * commit for the "big" LPT model.
1355 int ubifs_lpt_post_commit(struct ubifs_info
*c
)
1359 mutex_lock(&c
->lp_mutex
);
1360 err
= lpt_tgc_end(c
);
1364 while (need_write_all(c
)) {
1365 mutex_unlock(&c
->lp_mutex
);
1369 mutex_lock(&c
->lp_mutex
);
1372 mutex_unlock(&c
->lp_mutex
);
1377 * first_nnode - find the first nnode in memory.
1378 * @c: UBIFS file-system description object
1379 * @hght: height of tree where nnode found is returned here
1381 * This function returns a pointer to the nnode found or %NULL if no nnode is
1382 * found. This function is a helper to 'ubifs_lpt_free()'.
1384 static struct ubifs_nnode
*first_nnode(struct ubifs_info
*c
, int *hght
)
1386 struct ubifs_nnode
*nnode
;
1393 for (h
= 1; h
< c
->lpt_hght
; h
++) {
1395 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
1396 if (nnode
->nbranch
[i
].nnode
) {
1398 nnode
= nnode
->nbranch
[i
].nnode
;
1410 * next_nnode - find the next nnode in memory.
1411 * @c: UBIFS file-system description object
1412 * @nnode: nnode from which to start.
1413 * @hght: height of tree where nnode is, is passed and returned here
1415 * This function returns a pointer to the nnode found or %NULL if no nnode is
1416 * found. This function is a helper to 'ubifs_lpt_free()'.
1418 static struct ubifs_nnode
*next_nnode(struct ubifs_info
*c
,
1419 struct ubifs_nnode
*nnode
, int *hght
)
1421 struct ubifs_nnode
*parent
;
1422 int iip
, h
, i
, found
;
1424 parent
= nnode
->parent
;
1427 if (nnode
->iip
== UBIFS_LPT_FANOUT
- 1) {
1431 for (iip
= nnode
->iip
+ 1; iip
< UBIFS_LPT_FANOUT
; iip
++) {
1432 nnode
= parent
->nbranch
[iip
].nnode
;
1440 for (h
= *hght
+ 1; h
< c
->lpt_hght
; h
++) {
1442 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
1443 if (nnode
->nbranch
[i
].nnode
) {
1445 nnode
= nnode
->nbranch
[i
].nnode
;
1457 * ubifs_lpt_free - free resources owned by the LPT.
1458 * @c: UBIFS file-system description object
1459 * @wr_only: free only resources used for writing
1461 void ubifs_lpt_free(struct ubifs_info
*c
, int wr_only
)
1463 struct ubifs_nnode
*nnode
;
1466 /* Free write-only things first */
1468 free_obsolete_cnodes(c
); /* Leftover from a failed commit */
1480 /* Now free the rest */
1482 nnode
= first_nnode(c
, &hght
);
1484 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++)
1485 kfree(nnode
->nbranch
[i
].nnode
);
1486 nnode
= next_nnode(c
, nnode
, &hght
);
1488 for (i
= 0; i
< LPROPS_HEAP_CNT
; i
++)
1489 kfree(c
->lpt_heap
[i
].arr
);
1490 kfree(c
->dirty_idx
.arr
);
1493 kfree(c
->lpt_nod_buf
);
1498 * Everything below is related to debugging.
1502 * dbg_is_all_ff - determine if a buffer contains only 0xFF bytes.
1504 * @len: buffer length
1506 static int dbg_is_all_ff(uint8_t *buf
, int len
)
1510 for (i
= 0; i
< len
; i
++)
1517 * dbg_is_nnode_dirty - determine if a nnode is dirty.
1518 * @c: the UBIFS file-system description object
1519 * @lnum: LEB number where nnode was written
1520 * @offs: offset where nnode was written
1522 static int dbg_is_nnode_dirty(struct ubifs_info
*c
, int lnum
, int offs
)
1524 struct ubifs_nnode
*nnode
;
1527 /* Entire tree is in memory so first_nnode / next_nnode are OK */
1528 nnode
= first_nnode(c
, &hght
);
1529 for (; nnode
; nnode
= next_nnode(c
, nnode
, &hght
)) {
1530 struct ubifs_nbranch
*branch
;
1533 if (nnode
->parent
) {
1534 branch
= &nnode
->parent
->nbranch
[nnode
->iip
];
1535 if (branch
->lnum
!= lnum
|| branch
->offs
!= offs
)
1537 if (test_bit(DIRTY_CNODE
, &nnode
->flags
))
1541 if (c
->lpt_lnum
!= lnum
|| c
->lpt_offs
!= offs
)
1543 if (test_bit(DIRTY_CNODE
, &nnode
->flags
))
1552 * dbg_is_pnode_dirty - determine if a pnode is dirty.
1553 * @c: the UBIFS file-system description object
1554 * @lnum: LEB number where pnode was written
1555 * @offs: offset where pnode was written
1557 static int dbg_is_pnode_dirty(struct ubifs_info
*c
, int lnum
, int offs
)
1561 cnt
= DIV_ROUND_UP(c
->main_lebs
, UBIFS_LPT_FANOUT
);
1562 for (i
= 0; i
< cnt
; i
++) {
1563 struct ubifs_pnode
*pnode
;
1564 struct ubifs_nbranch
*branch
;
1567 pnode
= pnode_lookup(c
, i
);
1569 return PTR_ERR(pnode
);
1570 branch
= &pnode
->parent
->nbranch
[pnode
->iip
];
1571 if (branch
->lnum
!= lnum
|| branch
->offs
!= offs
)
1573 if (test_bit(DIRTY_CNODE
, &pnode
->flags
))
1581 * dbg_is_ltab_dirty - determine if a ltab node is dirty.
1582 * @c: the UBIFS file-system description object
1583 * @lnum: LEB number where ltab node was written
1584 * @offs: offset where ltab node was written
1586 static int dbg_is_ltab_dirty(struct ubifs_info
*c
, int lnum
, int offs
)
1588 if (lnum
!= c
->ltab_lnum
|| offs
!= c
->ltab_offs
)
1590 return (c
->lpt_drty_flgs
& LTAB_DIRTY
) != 0;
1594 * dbg_is_lsave_dirty - determine if a lsave node is dirty.
1595 * @c: the UBIFS file-system description object
1596 * @lnum: LEB number where lsave node was written
1597 * @offs: offset where lsave node was written
1599 static int dbg_is_lsave_dirty(struct ubifs_info
*c
, int lnum
, int offs
)
1601 if (lnum
!= c
->lsave_lnum
|| offs
!= c
->lsave_offs
)
1603 return (c
->lpt_drty_flgs
& LSAVE_DIRTY
) != 0;
1607 * dbg_is_node_dirty - determine if a node is dirty.
1608 * @c: the UBIFS file-system description object
1609 * @node_type: node type
1610 * @lnum: LEB number where node was written
1611 * @offs: offset where node was written
1613 static int dbg_is_node_dirty(struct ubifs_info
*c
, int node_type
, int lnum
,
1616 switch (node_type
) {
1617 case UBIFS_LPT_NNODE
:
1618 return dbg_is_nnode_dirty(c
, lnum
, offs
);
1619 case UBIFS_LPT_PNODE
:
1620 return dbg_is_pnode_dirty(c
, lnum
, offs
);
1621 case UBIFS_LPT_LTAB
:
1622 return dbg_is_ltab_dirty(c
, lnum
, offs
);
1623 case UBIFS_LPT_LSAVE
:
1624 return dbg_is_lsave_dirty(c
, lnum
, offs
);
1630 * dbg_check_ltab_lnum - check the ltab for a LPT LEB number.
1631 * @c: the UBIFS file-system description object
1632 * @lnum: LEB number where node was written
1633 * @offs: offset where node was written
1635 * This function returns %0 on success and a negative error code on failure.
1637 static int dbg_check_ltab_lnum(struct ubifs_info
*c
, int lnum
)
1639 int err
, len
= c
->leb_size
, dirty
= 0, node_type
, node_num
, node_len
;
1643 if (!dbg_is_chk_lprops(c
))
1646 buf
= p
= __vmalloc(c
->leb_size
, GFP_NOFS
, PAGE_KERNEL
);
1648 ubifs_err("cannot allocate memory for ltab checking");
1652 dbg_lp("LEB %d", lnum
);
1654 err
= ubifs_leb_read(c
, lnum
, buf
, 0, c
->leb_size
, 1);
1659 if (!is_a_node(c
, p
, len
)) {
1662 pad_len
= get_pad_len(c
, p
, len
);
1669 if (!dbg_is_all_ff(p
, len
)) {
1670 ubifs_err("invalid empty space in LEB %d at %d",
1671 lnum
, c
->leb_size
- len
);
1674 i
= lnum
- c
->lpt_first
;
1675 if (len
!= c
->ltab
[i
].free
) {
1676 ubifs_err("invalid free space in LEB %d (free %d, expected %d)",
1677 lnum
, len
, c
->ltab
[i
].free
);
1680 if (dirty
!= c
->ltab
[i
].dirty
) {
1681 ubifs_err("invalid dirty space in LEB %d (dirty %d, expected %d)",
1682 lnum
, dirty
, c
->ltab
[i
].dirty
);
1687 node_type
= get_lpt_node_type(c
, p
, &node_num
);
1688 node_len
= get_lpt_node_len(c
, node_type
);
1689 ret
= dbg_is_node_dirty(c
, node_type
, lnum
, c
->leb_size
- len
);
1703 * dbg_check_ltab - check the free and dirty space in the ltab.
1704 * @c: the UBIFS file-system description object
1706 * This function returns %0 on success and a negative error code on failure.
1708 int dbg_check_ltab(struct ubifs_info
*c
)
1710 int lnum
, err
, i
, cnt
;
1712 if (!dbg_is_chk_lprops(c
))
1715 /* Bring the entire tree into memory */
1716 cnt
= DIV_ROUND_UP(c
->main_lebs
, UBIFS_LPT_FANOUT
);
1717 for (i
= 0; i
< cnt
; i
++) {
1718 struct ubifs_pnode
*pnode
;
1720 pnode
= pnode_lookup(c
, i
);
1722 return PTR_ERR(pnode
);
1727 err
= dbg_check_lpt_nodes(c
, (struct ubifs_cnode
*)c
->nroot
, 0, 0);
1731 /* Check each LEB */
1732 for (lnum
= c
->lpt_first
; lnum
<= c
->lpt_last
; lnum
++) {
1733 err
= dbg_check_ltab_lnum(c
, lnum
);
1735 ubifs_err("failed at LEB %d", lnum
);
1740 dbg_lp("succeeded");
1745 * dbg_chk_lpt_free_spc - check LPT free space is enough to write entire LPT.
1746 * @c: the UBIFS file-system description object
1748 * This function returns %0 on success and a negative error code on failure.
1750 int dbg_chk_lpt_free_spc(struct ubifs_info
*c
)
1755 if (!dbg_is_chk_lprops(c
))
1758 for (i
= 0; i
< c
->lpt_lebs
; i
++) {
1759 if (c
->ltab
[i
].tgc
|| c
->ltab
[i
].cmt
)
1761 if (i
+ c
->lpt_first
== c
->nhead_lnum
)
1762 free
+= c
->leb_size
- c
->nhead_offs
;
1763 else if (c
->ltab
[i
].free
== c
->leb_size
)
1764 free
+= c
->leb_size
;
1766 if (free
< c
->lpt_sz
) {
1767 ubifs_err("LPT space error: free %lld lpt_sz %lld",
1769 ubifs_dump_lpt_info(c
);
1770 ubifs_dump_lpt_lebs(c
);
1778 * dbg_chk_lpt_sz - check LPT does not write more than LPT size.
1779 * @c: the UBIFS file-system description object
1780 * @action: what to do
1781 * @len: length written
1783 * This function returns %0 on success and a negative error code on failure.
1784 * The @action argument may be one of:
1785 * o %0 - LPT debugging checking starts, initialize debugging variables;
1786 * o %1 - wrote an LPT node, increase LPT size by @len bytes;
1787 * o %2 - switched to a different LEB and wasted @len bytes;
1788 * o %3 - check that we've written the right number of bytes.
1789 * o %4 - wasted @len bytes;
1791 int dbg_chk_lpt_sz(struct ubifs_info
*c
, int action
, int len
)
1793 struct ubifs_debug_info
*d
= c
->dbg
;
1794 long long chk_lpt_sz
, lpt_sz
;
1797 if (!dbg_is_chk_lprops(c
))
1804 d
->chk_lpt_lebs
= 0;
1805 d
->chk_lpt_wastage
= 0;
1806 if (c
->dirty_pn_cnt
> c
->pnode_cnt
) {
1807 ubifs_err("dirty pnodes %d exceed max %d",
1808 c
->dirty_pn_cnt
, c
->pnode_cnt
);
1811 if (c
->dirty_nn_cnt
> c
->nnode_cnt
) {
1812 ubifs_err("dirty nnodes %d exceed max %d",
1813 c
->dirty_nn_cnt
, c
->nnode_cnt
);
1818 d
->chk_lpt_sz
+= len
;
1821 d
->chk_lpt_sz
+= len
;
1822 d
->chk_lpt_wastage
+= len
;
1823 d
->chk_lpt_lebs
+= 1;
1826 chk_lpt_sz
= c
->leb_size
;
1827 chk_lpt_sz
*= d
->chk_lpt_lebs
;
1828 chk_lpt_sz
+= len
- c
->nhead_offs
;
1829 if (d
->chk_lpt_sz
!= chk_lpt_sz
) {
1830 ubifs_err("LPT wrote %lld but space used was %lld",
1831 d
->chk_lpt_sz
, chk_lpt_sz
);
1834 if (d
->chk_lpt_sz
> c
->lpt_sz
) {
1835 ubifs_err("LPT wrote %lld but lpt_sz is %lld",
1836 d
->chk_lpt_sz
, c
->lpt_sz
);
1839 if (d
->chk_lpt_sz2
&& d
->chk_lpt_sz
!= d
->chk_lpt_sz2
) {
1840 ubifs_err("LPT layout size %lld but wrote %lld",
1841 d
->chk_lpt_sz
, d
->chk_lpt_sz2
);
1844 if (d
->chk_lpt_sz2
&& d
->new_nhead_offs
!= len
) {
1845 ubifs_err("LPT new nhead offs: expected %d was %d",
1846 d
->new_nhead_offs
, len
);
1849 lpt_sz
= (long long)c
->pnode_cnt
* c
->pnode_sz
;
1850 lpt_sz
+= (long long)c
->nnode_cnt
* c
->nnode_sz
;
1851 lpt_sz
+= c
->ltab_sz
;
1853 lpt_sz
+= c
->lsave_sz
;
1854 if (d
->chk_lpt_sz
- d
->chk_lpt_wastage
> lpt_sz
) {
1855 ubifs_err("LPT chk_lpt_sz %lld + waste %lld exceeds %lld",
1856 d
->chk_lpt_sz
, d
->chk_lpt_wastage
, lpt_sz
);
1860 ubifs_dump_lpt_info(c
);
1861 ubifs_dump_lpt_lebs(c
);
1864 d
->chk_lpt_sz2
= d
->chk_lpt_sz
;
1866 d
->chk_lpt_wastage
= 0;
1867 d
->chk_lpt_lebs
= 0;
1868 d
->new_nhead_offs
= len
;
1871 d
->chk_lpt_sz
+= len
;
1872 d
->chk_lpt_wastage
+= len
;
1880 * ubifs_dump_lpt_leb - dump an LPT LEB.
1881 * @c: UBIFS file-system description object
1882 * @lnum: LEB number to dump
1884 * This function dumps an LEB from LPT area. Nodes in this area are very
1885 * different to nodes in the main area (e.g., they do not have common headers,
1886 * they do not have 8-byte alignments, etc), so we have a separate function to
1887 * dump LPT area LEBs. Note, LPT has to be locked by the caller.
1889 static void dump_lpt_leb(const struct ubifs_info
*c
, int lnum
)
1891 int err
, len
= c
->leb_size
, node_type
, node_num
, node_len
, offs
;
1894 pr_err("(pid %d) start dumping LEB %d\n", current
->pid
, lnum
);
1895 buf
= p
= __vmalloc(c
->leb_size
, GFP_NOFS
, PAGE_KERNEL
);
1897 ubifs_err("cannot allocate memory to dump LPT");
1901 err
= ubifs_leb_read(c
, lnum
, buf
, 0, c
->leb_size
, 1);
1906 offs
= c
->leb_size
- len
;
1907 if (!is_a_node(c
, p
, len
)) {
1910 pad_len
= get_pad_len(c
, p
, len
);
1912 pr_err("LEB %d:%d, pad %d bytes\n",
1913 lnum
, offs
, pad_len
);
1919 pr_err("LEB %d:%d, free %d bytes\n",
1924 node_type
= get_lpt_node_type(c
, p
, &node_num
);
1925 switch (node_type
) {
1926 case UBIFS_LPT_PNODE
:
1928 node_len
= c
->pnode_sz
;
1930 pr_err("LEB %d:%d, pnode num %d\n",
1931 lnum
, offs
, node_num
);
1933 pr_err("LEB %d:%d, pnode\n", lnum
, offs
);
1936 case UBIFS_LPT_NNODE
:
1939 struct ubifs_nnode nnode
;
1941 node_len
= c
->nnode_sz
;
1943 pr_err("LEB %d:%d, nnode num %d, ",
1944 lnum
, offs
, node_num
);
1946 pr_err("LEB %d:%d, nnode, ",
1948 err
= ubifs_unpack_nnode(c
, p
, &nnode
);
1949 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
1950 pr_cont("%d:%d", nnode
.nbranch
[i
].lnum
,
1951 nnode
.nbranch
[i
].offs
);
1952 if (i
!= UBIFS_LPT_FANOUT
- 1)
1958 case UBIFS_LPT_LTAB
:
1959 node_len
= c
->ltab_sz
;
1960 pr_err("LEB %d:%d, ltab\n", lnum
, offs
);
1962 case UBIFS_LPT_LSAVE
:
1963 node_len
= c
->lsave_sz
;
1964 pr_err("LEB %d:%d, lsave len\n", lnum
, offs
);
1967 ubifs_err("LPT node type %d not recognized", node_type
);
1975 pr_err("(pid %d) finish dumping LEB %d\n", current
->pid
, lnum
);
1982 * ubifs_dump_lpt_lebs - dump LPT lebs.
1983 * @c: UBIFS file-system description object
1985 * This function dumps all LPT LEBs. The caller has to make sure the LPT is
1988 void ubifs_dump_lpt_lebs(const struct ubifs_info
*c
)
1992 pr_err("(pid %d) start dumping all LPT LEBs\n", current
->pid
);
1993 for (i
= 0; i
< c
->lpt_lebs
; i
++)
1994 dump_lpt_leb(c
, i
+ c
->lpt_first
);
1995 pr_err("(pid %d) finish dumping all LPT LEBs\n", current
->pid
);
1999 * dbg_populate_lsave - debugging version of 'populate_lsave()'
2000 * @c: UBIFS file-system description object
2002 * This is a debugging version for 'populate_lsave()' which populates lsave
2003 * with random LEBs instead of useful LEBs, which is good for test coverage.
2004 * Returns zero if lsave has not been populated (this debugging feature is
2005 * disabled) an non-zero if lsave has been populated.
2007 static int dbg_populate_lsave(struct ubifs_info
*c
)
2009 struct ubifs_lprops
*lprops
;
2010 struct ubifs_lpt_heap
*heap
;
2013 if (!dbg_is_chk_gen(c
))
2015 if (prandom_u32() & 3)
2018 for (i
= 0; i
< c
->lsave_cnt
; i
++)
2019 c
->lsave
[i
] = c
->main_first
;
2021 list_for_each_entry(lprops
, &c
->empty_list
, list
)
2022 c
->lsave
[prandom_u32() % c
->lsave_cnt
] = lprops
->lnum
;
2023 list_for_each_entry(lprops
, &c
->freeable_list
, list
)
2024 c
->lsave
[prandom_u32() % c
->lsave_cnt
] = lprops
->lnum
;
2025 list_for_each_entry(lprops
, &c
->frdi_idx_list
, list
)
2026 c
->lsave
[prandom_u32() % c
->lsave_cnt
] = lprops
->lnum
;
2028 heap
= &c
->lpt_heap
[LPROPS_DIRTY_IDX
- 1];
2029 for (i
= 0; i
< heap
->cnt
; i
++)
2030 c
->lsave
[prandom_u32() % c
->lsave_cnt
] = heap
->arr
[i
]->lnum
;
2031 heap
= &c
->lpt_heap
[LPROPS_DIRTY
- 1];
2032 for (i
= 0; i
< heap
->cnt
; i
++)
2033 c
->lsave
[prandom_u32() % c
->lsave_cnt
] = heap
->arr
[i
]->lnum
;
2034 heap
= &c
->lpt_heap
[LPROPS_FREE
- 1];
2035 for (i
= 0; i
< heap
->cnt
; i
++)
2036 c
->lsave
[prandom_u32() % c
->lsave_cnt
] = heap
->arr
[i
]->lnum
;