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 commit-related functionality of the LEB properties
28 #include <linux/crc16.h>
29 #include <linux/slab.h>
30 #include <linux/random.h>
33 static int dbg_populate_lsave(struct ubifs_info
*c
);
36 * first_dirty_cnode - find first dirty cnode.
37 * @c: UBIFS file-system description object
38 * @nnode: nnode at which to start
40 * This function returns the first dirty cnode or %NULL if there is not one.
42 static struct ubifs_cnode
*first_dirty_cnode(struct ubifs_nnode
*nnode
)
48 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
49 struct ubifs_cnode
*cnode
;
51 cnode
= nnode
->nbranch
[i
].cnode
;
53 test_bit(DIRTY_CNODE
, &cnode
->flags
)) {
54 if (cnode
->level
== 0)
56 nnode
= (struct ubifs_nnode
*)cnode
;
62 return (struct ubifs_cnode
*)nnode
;
67 * next_dirty_cnode - find next dirty cnode.
68 * @cnode: cnode from which to begin searching
70 * This function returns the next dirty cnode or %NULL if there is not one.
72 static struct ubifs_cnode
*next_dirty_cnode(struct ubifs_cnode
*cnode
)
74 struct ubifs_nnode
*nnode
;
78 nnode
= cnode
->parent
;
81 for (i
= cnode
->iip
+ 1; i
< UBIFS_LPT_FANOUT
; i
++) {
82 cnode
= nnode
->nbranch
[i
].cnode
;
83 if (cnode
&& test_bit(DIRTY_CNODE
, &cnode
->flags
)) {
84 if (cnode
->level
== 0)
85 return cnode
; /* cnode is a pnode */
86 /* cnode is a nnode */
87 return first_dirty_cnode((struct ubifs_nnode
*)cnode
);
90 return (struct ubifs_cnode
*)nnode
;
94 * get_cnodes_to_commit - create list of dirty cnodes to commit.
95 * @c: UBIFS file-system description object
97 * This function returns the number of cnodes to commit.
99 static int get_cnodes_to_commit(struct ubifs_info
*c
)
101 struct ubifs_cnode
*cnode
, *cnext
;
107 if (!test_bit(DIRTY_CNODE
, &c
->nroot
->flags
))
110 c
->lpt_cnext
= first_dirty_cnode(c
->nroot
);
111 cnode
= c
->lpt_cnext
;
116 ubifs_assert(!test_bit(COW_CNODE
, &cnode
->flags
));
117 __set_bit(COW_CNODE
, &cnode
->flags
);
118 cnext
= next_dirty_cnode(cnode
);
120 cnode
->cnext
= c
->lpt_cnext
;
123 cnode
->cnext
= cnext
;
127 dbg_cmt("committing %d cnodes", cnt
);
128 dbg_lp("committing %d cnodes", cnt
);
129 ubifs_assert(cnt
== c
->dirty_nn_cnt
+ c
->dirty_pn_cnt
);
134 * upd_ltab - update LPT LEB properties.
135 * @c: UBIFS file-system description object
137 * @free: amount of free space
138 * @dirty: amount of dirty space to add
140 static void upd_ltab(struct ubifs_info
*c
, int lnum
, int free
, int dirty
)
142 dbg_lp("LEB %d free %d dirty %d to %d +%d",
143 lnum
, c
->ltab
[lnum
- c
->lpt_first
].free
,
144 c
->ltab
[lnum
- c
->lpt_first
].dirty
, free
, dirty
);
145 ubifs_assert(lnum
>= c
->lpt_first
&& lnum
<= c
->lpt_last
);
146 c
->ltab
[lnum
- c
->lpt_first
].free
= free
;
147 c
->ltab
[lnum
- c
->lpt_first
].dirty
+= dirty
;
151 * alloc_lpt_leb - allocate an LPT LEB that is empty.
152 * @c: UBIFS file-system description object
153 * @lnum: LEB number is passed and returned here
155 * This function finds the next empty LEB in the ltab starting from @lnum. If a
156 * an empty LEB is found it is returned in @lnum and the function returns %0.
157 * Otherwise the function returns -ENOSPC. Note however, that LPT is designed
158 * never to run out of space.
160 static int alloc_lpt_leb(struct ubifs_info
*c
, int *lnum
)
164 n
= *lnum
- c
->lpt_first
+ 1;
165 for (i
= n
; i
< c
->lpt_lebs
; i
++) {
166 if (c
->ltab
[i
].tgc
|| c
->ltab
[i
].cmt
)
168 if (c
->ltab
[i
].free
== c
->leb_size
) {
170 *lnum
= i
+ c
->lpt_first
;
175 for (i
= 0; i
< n
; i
++) {
176 if (c
->ltab
[i
].tgc
|| c
->ltab
[i
].cmt
)
178 if (c
->ltab
[i
].free
== c
->leb_size
) {
180 *lnum
= i
+ c
->lpt_first
;
188 * layout_cnodes - layout cnodes for commit.
189 * @c: UBIFS file-system description object
191 * This function returns %0 on success and a negative error code on failure.
193 static int layout_cnodes(struct ubifs_info
*c
)
195 int lnum
, offs
, len
, alen
, done_lsave
, done_ltab
, err
;
196 struct ubifs_cnode
*cnode
;
198 err
= dbg_chk_lpt_sz(c
, 0, 0);
201 cnode
= c
->lpt_cnext
;
204 lnum
= c
->nhead_lnum
;
205 offs
= c
->nhead_offs
;
206 /* Try to place lsave and ltab nicely */
207 done_lsave
= !c
->big_lpt
;
209 if (!done_lsave
&& offs
+ c
->lsave_sz
<= c
->leb_size
) {
211 c
->lsave_lnum
= lnum
;
212 c
->lsave_offs
= offs
;
214 dbg_chk_lpt_sz(c
, 1, c
->lsave_sz
);
217 if (offs
+ c
->ltab_sz
<= c
->leb_size
) {
222 dbg_chk_lpt_sz(c
, 1, c
->ltab_sz
);
228 c
->dirty_nn_cnt
-= 1;
231 c
->dirty_pn_cnt
-= 1;
233 while (offs
+ len
> c
->leb_size
) {
234 alen
= ALIGN(offs
, c
->min_io_size
);
235 upd_ltab(c
, lnum
, c
->leb_size
- alen
, alen
- offs
);
236 dbg_chk_lpt_sz(c
, 2, c
->leb_size
- offs
);
237 err
= alloc_lpt_leb(c
, &lnum
);
241 ubifs_assert(lnum
>= c
->lpt_first
&&
242 lnum
<= c
->lpt_last
);
243 /* Try to place lsave and ltab nicely */
246 c
->lsave_lnum
= lnum
;
247 c
->lsave_offs
= offs
;
249 dbg_chk_lpt_sz(c
, 1, c
->lsave_sz
);
257 dbg_chk_lpt_sz(c
, 1, c
->ltab_sz
);
263 cnode
->parent
->nbranch
[cnode
->iip
].lnum
= lnum
;
264 cnode
->parent
->nbranch
[cnode
->iip
].offs
= offs
;
270 dbg_chk_lpt_sz(c
, 1, len
);
271 cnode
= cnode
->cnext
;
272 } while (cnode
&& cnode
!= c
->lpt_cnext
);
274 /* Make sure to place LPT's save table */
276 if (offs
+ c
->lsave_sz
> c
->leb_size
) {
277 alen
= ALIGN(offs
, c
->min_io_size
);
278 upd_ltab(c
, lnum
, c
->leb_size
- alen
, alen
- offs
);
279 dbg_chk_lpt_sz(c
, 2, c
->leb_size
- offs
);
280 err
= alloc_lpt_leb(c
, &lnum
);
284 ubifs_assert(lnum
>= c
->lpt_first
&&
285 lnum
<= c
->lpt_last
);
288 c
->lsave_lnum
= lnum
;
289 c
->lsave_offs
= offs
;
291 dbg_chk_lpt_sz(c
, 1, c
->lsave_sz
);
294 /* Make sure to place LPT's own lprops table */
296 if (offs
+ c
->ltab_sz
> c
->leb_size
) {
297 alen
= ALIGN(offs
, c
->min_io_size
);
298 upd_ltab(c
, lnum
, c
->leb_size
- alen
, alen
- offs
);
299 dbg_chk_lpt_sz(c
, 2, c
->leb_size
- offs
);
300 err
= alloc_lpt_leb(c
, &lnum
);
304 ubifs_assert(lnum
>= c
->lpt_first
&&
305 lnum
<= c
->lpt_last
);
311 dbg_chk_lpt_sz(c
, 1, c
->ltab_sz
);
314 alen
= ALIGN(offs
, c
->min_io_size
);
315 upd_ltab(c
, lnum
, c
->leb_size
- alen
, alen
- offs
);
316 dbg_chk_lpt_sz(c
, 4, alen
- offs
);
317 err
= dbg_chk_lpt_sz(c
, 3, alen
);
323 ubifs_err("LPT out of space");
324 dbg_err("LPT out of space at LEB %d:%d needing %d, done_ltab %d, "
325 "done_lsave %d", lnum
, offs
, len
, done_ltab
, done_lsave
);
326 ubifs_dump_lpt_info(c
);
327 ubifs_dump_lpt_lebs(c
);
333 * realloc_lpt_leb - allocate an LPT LEB that is empty.
334 * @c: UBIFS file-system description object
335 * @lnum: LEB number is passed and returned here
337 * This function duplicates exactly the results of the function alloc_lpt_leb.
338 * It is used during end commit to reallocate the same LEB numbers that were
339 * allocated by alloc_lpt_leb during start commit.
341 * This function finds the next LEB that was allocated by the alloc_lpt_leb
342 * function starting from @lnum. If a LEB is found it is returned in @lnum and
343 * the function returns %0. Otherwise the function returns -ENOSPC.
344 * Note however, that LPT is designed never to run out of space.
346 static int realloc_lpt_leb(struct ubifs_info
*c
, int *lnum
)
350 n
= *lnum
- c
->lpt_first
+ 1;
351 for (i
= n
; i
< c
->lpt_lebs
; i
++)
352 if (c
->ltab
[i
].cmt
) {
354 *lnum
= i
+ c
->lpt_first
;
358 for (i
= 0; i
< n
; i
++)
359 if (c
->ltab
[i
].cmt
) {
361 *lnum
= i
+ c
->lpt_first
;
368 * write_cnodes - write cnodes for commit.
369 * @c: UBIFS file-system description object
371 * This function returns %0 on success and a negative error code on failure.
373 static int write_cnodes(struct ubifs_info
*c
)
375 int lnum
, offs
, len
, from
, err
, wlen
, alen
, done_ltab
, done_lsave
;
376 struct ubifs_cnode
*cnode
;
377 void *buf
= c
->lpt_buf
;
379 cnode
= c
->lpt_cnext
;
382 lnum
= c
->nhead_lnum
;
383 offs
= c
->nhead_offs
;
385 /* Ensure empty LEB is unmapped */
387 err
= ubifs_leb_unmap(c
, lnum
);
391 /* Try to place lsave and ltab nicely */
392 done_lsave
= !c
->big_lpt
;
394 if (!done_lsave
&& offs
+ c
->lsave_sz
<= c
->leb_size
) {
396 ubifs_pack_lsave(c
, buf
+ offs
, c
->lsave
);
398 dbg_chk_lpt_sz(c
, 1, c
->lsave_sz
);
401 if (offs
+ c
->ltab_sz
<= c
->leb_size
) {
403 ubifs_pack_ltab(c
, buf
+ offs
, c
->ltab_cmt
);
405 dbg_chk_lpt_sz(c
, 1, c
->ltab_sz
);
408 /* Loop for each cnode */
414 while (offs
+ len
> c
->leb_size
) {
417 alen
= ALIGN(wlen
, c
->min_io_size
);
418 memset(buf
+ offs
, 0xff, alen
- wlen
);
419 err
= ubifs_leb_write(c
, lnum
, buf
+ from
, from
,
420 alen
, UBI_SHORTTERM
);
424 dbg_chk_lpt_sz(c
, 2, c
->leb_size
- offs
);
425 err
= realloc_lpt_leb(c
, &lnum
);
429 ubifs_assert(lnum
>= c
->lpt_first
&&
430 lnum
<= c
->lpt_last
);
431 err
= ubifs_leb_unmap(c
, lnum
);
434 /* Try to place lsave and ltab nicely */
437 ubifs_pack_lsave(c
, buf
+ offs
, c
->lsave
);
439 dbg_chk_lpt_sz(c
, 1, c
->lsave_sz
);
444 ubifs_pack_ltab(c
, buf
+ offs
, c
->ltab_cmt
);
446 dbg_chk_lpt_sz(c
, 1, c
->ltab_sz
);
452 ubifs_pack_nnode(c
, buf
+ offs
,
453 (struct ubifs_nnode
*)cnode
);
455 ubifs_pack_pnode(c
, buf
+ offs
,
456 (struct ubifs_pnode
*)cnode
);
458 * The reason for the barriers is the same as in case of TNC.
459 * See comment in 'write_index()'. 'dirty_cow_nnode()' and
460 * 'dirty_cow_pnode()' are the functions for which this is
463 clear_bit(DIRTY_CNODE
, &cnode
->flags
);
464 smp_mb__before_clear_bit();
465 clear_bit(COW_CNODE
, &cnode
->flags
);
466 smp_mb__after_clear_bit();
468 dbg_chk_lpt_sz(c
, 1, len
);
469 cnode
= cnode
->cnext
;
470 } while (cnode
&& cnode
!= c
->lpt_cnext
);
472 /* Make sure to place LPT's save table */
474 if (offs
+ c
->lsave_sz
> c
->leb_size
) {
476 alen
= ALIGN(wlen
, c
->min_io_size
);
477 memset(buf
+ offs
, 0xff, alen
- wlen
);
478 err
= ubifs_leb_write(c
, lnum
, buf
+ from
, from
, alen
,
482 dbg_chk_lpt_sz(c
, 2, c
->leb_size
- offs
);
483 err
= realloc_lpt_leb(c
, &lnum
);
487 ubifs_assert(lnum
>= c
->lpt_first
&&
488 lnum
<= c
->lpt_last
);
489 err
= ubifs_leb_unmap(c
, lnum
);
494 ubifs_pack_lsave(c
, buf
+ offs
, c
->lsave
);
496 dbg_chk_lpt_sz(c
, 1, c
->lsave_sz
);
499 /* Make sure to place LPT's own lprops table */
501 if (offs
+ c
->ltab_sz
> c
->leb_size
) {
503 alen
= ALIGN(wlen
, c
->min_io_size
);
504 memset(buf
+ offs
, 0xff, alen
- wlen
);
505 err
= ubifs_leb_write(c
, lnum
, buf
+ from
, from
, alen
,
509 dbg_chk_lpt_sz(c
, 2, c
->leb_size
- offs
);
510 err
= realloc_lpt_leb(c
, &lnum
);
514 ubifs_assert(lnum
>= c
->lpt_first
&&
515 lnum
<= c
->lpt_last
);
516 err
= ubifs_leb_unmap(c
, lnum
);
521 ubifs_pack_ltab(c
, buf
+ offs
, c
->ltab_cmt
);
523 dbg_chk_lpt_sz(c
, 1, c
->ltab_sz
);
526 /* Write remaining data in buffer */
528 alen
= ALIGN(wlen
, c
->min_io_size
);
529 memset(buf
+ offs
, 0xff, alen
- wlen
);
530 err
= ubifs_leb_write(c
, lnum
, buf
+ from
, from
, alen
, UBI_SHORTTERM
);
534 dbg_chk_lpt_sz(c
, 4, alen
- wlen
);
535 err
= dbg_chk_lpt_sz(c
, 3, ALIGN(offs
, c
->min_io_size
));
539 c
->nhead_lnum
= lnum
;
540 c
->nhead_offs
= ALIGN(offs
, c
->min_io_size
);
542 dbg_lp("LPT root is at %d:%d", c
->lpt_lnum
, c
->lpt_offs
);
543 dbg_lp("LPT head is at %d:%d", c
->nhead_lnum
, c
->nhead_offs
);
544 dbg_lp("LPT ltab is at %d:%d", c
->ltab_lnum
, c
->ltab_offs
);
546 dbg_lp("LPT lsave is at %d:%d", c
->lsave_lnum
, c
->lsave_offs
);
551 ubifs_err("LPT out of space mismatch");
552 dbg_err("LPT out of space mismatch at LEB %d:%d needing %d, done_ltab "
553 "%d, done_lsave %d", lnum
, offs
, len
, done_ltab
, done_lsave
);
554 ubifs_dump_lpt_info(c
);
555 ubifs_dump_lpt_lebs(c
);
561 * next_pnode_to_dirty - find next pnode to dirty.
562 * @c: UBIFS file-system description object
565 * This function returns the next pnode to dirty or %NULL if there are no more
566 * pnodes. Note that pnodes that have never been written (lnum == 0) are
569 static struct ubifs_pnode
*next_pnode_to_dirty(struct ubifs_info
*c
,
570 struct ubifs_pnode
*pnode
)
572 struct ubifs_nnode
*nnode
;
575 /* Try to go right */
576 nnode
= pnode
->parent
;
577 for (iip
= pnode
->iip
+ 1; iip
< UBIFS_LPT_FANOUT
; iip
++) {
578 if (nnode
->nbranch
[iip
].lnum
)
579 return ubifs_get_pnode(c
, nnode
, iip
);
582 /* Go up while can't go right */
584 iip
= nnode
->iip
+ 1;
585 nnode
= nnode
->parent
;
588 for (; iip
< UBIFS_LPT_FANOUT
; iip
++) {
589 if (nnode
->nbranch
[iip
].lnum
)
592 } while (iip
>= UBIFS_LPT_FANOUT
);
595 nnode
= ubifs_get_nnode(c
, nnode
, iip
);
597 return (void *)nnode
;
599 /* Go down to level 1 */
600 while (nnode
->level
> 1) {
601 for (iip
= 0; iip
< UBIFS_LPT_FANOUT
; iip
++) {
602 if (nnode
->nbranch
[iip
].lnum
)
605 if (iip
>= UBIFS_LPT_FANOUT
) {
607 * Should not happen, but we need to keep going
612 nnode
= ubifs_get_nnode(c
, nnode
, iip
);
614 return (void *)nnode
;
617 for (iip
= 0; iip
< UBIFS_LPT_FANOUT
; iip
++)
618 if (nnode
->nbranch
[iip
].lnum
)
620 if (iip
>= UBIFS_LPT_FANOUT
)
621 /* Should not happen, but we need to keep going if it does */
623 return ubifs_get_pnode(c
, nnode
, iip
);
627 * pnode_lookup - lookup a pnode in the LPT.
628 * @c: UBIFS file-system description object
629 * @i: pnode number (0 to main_lebs - 1)
631 * This function returns a pointer to the pnode on success or a negative
632 * error code on failure.
634 static struct ubifs_pnode
*pnode_lookup(struct ubifs_info
*c
, int i
)
636 int err
, h
, iip
, shft
;
637 struct ubifs_nnode
*nnode
;
640 err
= ubifs_read_nnode(c
, NULL
, 0);
644 i
<<= UBIFS_LPT_FANOUT_SHIFT
;
646 shft
= c
->lpt_hght
* UBIFS_LPT_FANOUT_SHIFT
;
647 for (h
= 1; h
< c
->lpt_hght
; h
++) {
648 iip
= ((i
>> shft
) & (UBIFS_LPT_FANOUT
- 1));
649 shft
-= UBIFS_LPT_FANOUT_SHIFT
;
650 nnode
= ubifs_get_nnode(c
, nnode
, iip
);
652 return ERR_CAST(nnode
);
654 iip
= ((i
>> shft
) & (UBIFS_LPT_FANOUT
- 1));
655 return ubifs_get_pnode(c
, nnode
, iip
);
659 * add_pnode_dirt - add dirty space to LPT LEB properties.
660 * @c: UBIFS file-system description object
661 * @pnode: pnode for which to add dirt
663 static void add_pnode_dirt(struct ubifs_info
*c
, struct ubifs_pnode
*pnode
)
665 ubifs_add_lpt_dirt(c
, pnode
->parent
->nbranch
[pnode
->iip
].lnum
,
670 * do_make_pnode_dirty - mark a pnode dirty.
671 * @c: UBIFS file-system description object
672 * @pnode: pnode to mark dirty
674 static void do_make_pnode_dirty(struct ubifs_info
*c
, struct ubifs_pnode
*pnode
)
676 /* Assumes cnext list is empty i.e. not called during commit */
677 if (!test_and_set_bit(DIRTY_CNODE
, &pnode
->flags
)) {
678 struct ubifs_nnode
*nnode
;
680 c
->dirty_pn_cnt
+= 1;
681 add_pnode_dirt(c
, pnode
);
682 /* Mark parent and ancestors dirty too */
683 nnode
= pnode
->parent
;
685 if (!test_and_set_bit(DIRTY_CNODE
, &nnode
->flags
)) {
686 c
->dirty_nn_cnt
+= 1;
687 ubifs_add_nnode_dirt(c
, nnode
);
688 nnode
= nnode
->parent
;
696 * make_tree_dirty - mark the entire LEB properties tree dirty.
697 * @c: UBIFS file-system description object
699 * This function is used by the "small" LPT model to cause the entire LEB
700 * properties tree to be written. The "small" LPT model does not use LPT
701 * garbage collection because it is more efficient to write the entire tree
702 * (because it is small).
704 * This function returns %0 on success and a negative error code on failure.
706 static int make_tree_dirty(struct ubifs_info
*c
)
708 struct ubifs_pnode
*pnode
;
710 pnode
= pnode_lookup(c
, 0);
712 return PTR_ERR(pnode
);
715 do_make_pnode_dirty(c
, pnode
);
716 pnode
= next_pnode_to_dirty(c
, pnode
);
718 return PTR_ERR(pnode
);
724 * need_write_all - determine if the LPT area is running out of free space.
725 * @c: UBIFS file-system description object
727 * This function returns %1 if the LPT area is running out of free space and %0
730 static int need_write_all(struct ubifs_info
*c
)
735 for (i
= 0; i
< c
->lpt_lebs
; i
++) {
736 if (i
+ c
->lpt_first
== c
->nhead_lnum
)
737 free
+= c
->leb_size
- c
->nhead_offs
;
738 else if (c
->ltab
[i
].free
== c
->leb_size
)
740 else if (c
->ltab
[i
].free
+ c
->ltab
[i
].dirty
== c
->leb_size
)
743 /* Less than twice the size left */
744 if (free
<= c
->lpt_sz
* 2)
750 * lpt_tgc_start - start trivial garbage collection of LPT LEBs.
751 * @c: UBIFS file-system description object
753 * LPT trivial garbage collection is where a LPT LEB contains only dirty and
754 * free space and so may be reused as soon as the next commit is completed.
755 * This function is called during start commit to mark LPT LEBs for trivial GC.
757 static void lpt_tgc_start(struct ubifs_info
*c
)
761 for (i
= 0; i
< c
->lpt_lebs
; i
++) {
762 if (i
+ c
->lpt_first
== c
->nhead_lnum
)
764 if (c
->ltab
[i
].dirty
> 0 &&
765 c
->ltab
[i
].free
+ c
->ltab
[i
].dirty
== c
->leb_size
) {
767 c
->ltab
[i
].free
= c
->leb_size
;
768 c
->ltab
[i
].dirty
= 0;
769 dbg_lp("LEB %d", i
+ c
->lpt_first
);
775 * lpt_tgc_end - end trivial garbage collection of LPT LEBs.
776 * @c: UBIFS file-system description object
778 * LPT trivial garbage collection is where a LPT LEB contains only dirty and
779 * free space and so may be reused as soon as the next commit is completed.
780 * This function is called after the commit is completed (master node has been
781 * written) and un-maps LPT LEBs that were marked for trivial GC.
783 static int lpt_tgc_end(struct ubifs_info
*c
)
787 for (i
= 0; i
< c
->lpt_lebs
; i
++)
788 if (c
->ltab
[i
].tgc
) {
789 err
= ubifs_leb_unmap(c
, i
+ c
->lpt_first
);
793 dbg_lp("LEB %d", i
+ c
->lpt_first
);
799 * populate_lsave - fill the lsave array with important LEB numbers.
800 * @c: the UBIFS file-system description object
802 * This function is only called for the "big" model. It records a small number
803 * of LEB numbers of important LEBs. Important LEBs are ones that are (from
804 * most important to least important): empty, freeable, freeable index, dirty
805 * index, dirty or free. Upon mount, we read this list of LEB numbers and bring
806 * their pnodes into memory. That will stop us from having to scan the LPT
807 * straight away. For the "small" model we assume that scanning the LPT is no
810 static void populate_lsave(struct ubifs_info
*c
)
812 struct ubifs_lprops
*lprops
;
813 struct ubifs_lpt_heap
*heap
;
816 ubifs_assert(c
->big_lpt
);
817 if (!(c
->lpt_drty_flgs
& LSAVE_DIRTY
)) {
818 c
->lpt_drty_flgs
|= LSAVE_DIRTY
;
819 ubifs_add_lpt_dirt(c
, c
->lsave_lnum
, c
->lsave_sz
);
822 if (dbg_populate_lsave(c
))
825 list_for_each_entry(lprops
, &c
->empty_list
, list
) {
826 c
->lsave
[cnt
++] = lprops
->lnum
;
827 if (cnt
>= c
->lsave_cnt
)
830 list_for_each_entry(lprops
, &c
->freeable_list
, list
) {
831 c
->lsave
[cnt
++] = lprops
->lnum
;
832 if (cnt
>= c
->lsave_cnt
)
835 list_for_each_entry(lprops
, &c
->frdi_idx_list
, list
) {
836 c
->lsave
[cnt
++] = lprops
->lnum
;
837 if (cnt
>= c
->lsave_cnt
)
840 heap
= &c
->lpt_heap
[LPROPS_DIRTY_IDX
- 1];
841 for (i
= 0; i
< heap
->cnt
; i
++) {
842 c
->lsave
[cnt
++] = heap
->arr
[i
]->lnum
;
843 if (cnt
>= c
->lsave_cnt
)
846 heap
= &c
->lpt_heap
[LPROPS_DIRTY
- 1];
847 for (i
= 0; i
< heap
->cnt
; i
++) {
848 c
->lsave
[cnt
++] = heap
->arr
[i
]->lnum
;
849 if (cnt
>= c
->lsave_cnt
)
852 heap
= &c
->lpt_heap
[LPROPS_FREE
- 1];
853 for (i
= 0; i
< heap
->cnt
; i
++) {
854 c
->lsave
[cnt
++] = heap
->arr
[i
]->lnum
;
855 if (cnt
>= c
->lsave_cnt
)
858 /* Fill it up completely */
859 while (cnt
< c
->lsave_cnt
)
860 c
->lsave
[cnt
++] = c
->main_first
;
864 * nnode_lookup - lookup a nnode in the LPT.
865 * @c: UBIFS file-system description object
868 * This function returns a pointer to the nnode on success or a negative
869 * error code on failure.
871 static struct ubifs_nnode
*nnode_lookup(struct ubifs_info
*c
, int i
)
874 struct ubifs_nnode
*nnode
;
877 err
= ubifs_read_nnode(c
, NULL
, 0);
883 iip
= i
& (UBIFS_LPT_FANOUT
- 1);
884 i
>>= UBIFS_LPT_FANOUT_SHIFT
;
887 nnode
= ubifs_get_nnode(c
, nnode
, iip
);
895 * make_nnode_dirty - find a nnode and, if found, make it dirty.
896 * @c: UBIFS file-system description object
897 * @node_num: nnode number of nnode to make dirty
898 * @lnum: LEB number where nnode was written
899 * @offs: offset where nnode was written
901 * This function is used by LPT garbage collection. LPT garbage collection is
902 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
903 * simply involves marking all the nodes in the LEB being garbage-collected as
904 * dirty. The dirty nodes are written next commit, after which the LEB is free
907 * This function returns %0 on success and a negative error code on failure.
909 static int make_nnode_dirty(struct ubifs_info
*c
, int node_num
, int lnum
,
912 struct ubifs_nnode
*nnode
;
914 nnode
= nnode_lookup(c
, node_num
);
916 return PTR_ERR(nnode
);
918 struct ubifs_nbranch
*branch
;
920 branch
= &nnode
->parent
->nbranch
[nnode
->iip
];
921 if (branch
->lnum
!= lnum
|| branch
->offs
!= offs
)
922 return 0; /* nnode is obsolete */
923 } else if (c
->lpt_lnum
!= lnum
|| c
->lpt_offs
!= offs
)
924 return 0; /* nnode is obsolete */
925 /* Assumes cnext list is empty i.e. not called during commit */
926 if (!test_and_set_bit(DIRTY_CNODE
, &nnode
->flags
)) {
927 c
->dirty_nn_cnt
+= 1;
928 ubifs_add_nnode_dirt(c
, nnode
);
929 /* Mark parent and ancestors dirty too */
930 nnode
= nnode
->parent
;
932 if (!test_and_set_bit(DIRTY_CNODE
, &nnode
->flags
)) {
933 c
->dirty_nn_cnt
+= 1;
934 ubifs_add_nnode_dirt(c
, nnode
);
935 nnode
= nnode
->parent
;
944 * make_pnode_dirty - find a pnode and, if found, make it dirty.
945 * @c: UBIFS file-system description object
946 * @node_num: pnode number of pnode to make dirty
947 * @lnum: LEB number where pnode was written
948 * @offs: offset where pnode was written
950 * This function is used by LPT garbage collection. LPT garbage collection is
951 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
952 * simply involves marking all the nodes in the LEB being garbage-collected as
953 * dirty. The dirty nodes are written next commit, after which the LEB is free
956 * This function returns %0 on success and a negative error code on failure.
958 static int make_pnode_dirty(struct ubifs_info
*c
, int node_num
, int lnum
,
961 struct ubifs_pnode
*pnode
;
962 struct ubifs_nbranch
*branch
;
964 pnode
= pnode_lookup(c
, node_num
);
966 return PTR_ERR(pnode
);
967 branch
= &pnode
->parent
->nbranch
[pnode
->iip
];
968 if (branch
->lnum
!= lnum
|| branch
->offs
!= offs
)
970 do_make_pnode_dirty(c
, pnode
);
975 * make_ltab_dirty - make ltab node dirty.
976 * @c: UBIFS file-system description object
977 * @lnum: LEB number where ltab was written
978 * @offs: offset where ltab was written
980 * This function is used by LPT garbage collection. LPT garbage collection is
981 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
982 * simply involves marking all the nodes in the LEB being garbage-collected as
983 * dirty. The dirty nodes are written next commit, after which the LEB is free
986 * This function returns %0 on success and a negative error code on failure.
988 static int make_ltab_dirty(struct ubifs_info
*c
, int lnum
, int offs
)
990 if (lnum
!= c
->ltab_lnum
|| offs
!= c
->ltab_offs
)
991 return 0; /* This ltab node is obsolete */
992 if (!(c
->lpt_drty_flgs
& LTAB_DIRTY
)) {
993 c
->lpt_drty_flgs
|= LTAB_DIRTY
;
994 ubifs_add_lpt_dirt(c
, c
->ltab_lnum
, c
->ltab_sz
);
1000 * make_lsave_dirty - make lsave node dirty.
1001 * @c: UBIFS file-system description object
1002 * @lnum: LEB number where lsave was written
1003 * @offs: offset where lsave was written
1005 * This function is used by LPT garbage collection. LPT garbage collection is
1006 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
1007 * simply involves marking all the nodes in the LEB being garbage-collected as
1008 * dirty. The dirty nodes are written next commit, after which the LEB is free
1011 * This function returns %0 on success and a negative error code on failure.
1013 static int make_lsave_dirty(struct ubifs_info
*c
, int lnum
, int offs
)
1015 if (lnum
!= c
->lsave_lnum
|| offs
!= c
->lsave_offs
)
1016 return 0; /* This lsave node is obsolete */
1017 if (!(c
->lpt_drty_flgs
& LSAVE_DIRTY
)) {
1018 c
->lpt_drty_flgs
|= LSAVE_DIRTY
;
1019 ubifs_add_lpt_dirt(c
, c
->lsave_lnum
, c
->lsave_sz
);
1025 * make_node_dirty - make node dirty.
1026 * @c: UBIFS file-system description object
1027 * @node_type: LPT node type
1028 * @node_num: node number
1029 * @lnum: LEB number where node was written
1030 * @offs: offset where node was written
1032 * This function is used by LPT garbage collection. LPT garbage collection is
1033 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
1034 * simply involves marking all the nodes in the LEB being garbage-collected as
1035 * dirty. The dirty nodes are written next commit, after which the LEB is free
1038 * This function returns %0 on success and a negative error code on failure.
1040 static int make_node_dirty(struct ubifs_info
*c
, int node_type
, int node_num
,
1043 switch (node_type
) {
1044 case UBIFS_LPT_NNODE
:
1045 return make_nnode_dirty(c
, node_num
, lnum
, offs
);
1046 case UBIFS_LPT_PNODE
:
1047 return make_pnode_dirty(c
, node_num
, lnum
, offs
);
1048 case UBIFS_LPT_LTAB
:
1049 return make_ltab_dirty(c
, lnum
, offs
);
1050 case UBIFS_LPT_LSAVE
:
1051 return make_lsave_dirty(c
, lnum
, offs
);
1057 * get_lpt_node_len - return the length of a node based on its type.
1058 * @c: UBIFS file-system description object
1059 * @node_type: LPT node type
1061 static int get_lpt_node_len(const struct ubifs_info
*c
, int node_type
)
1063 switch (node_type
) {
1064 case UBIFS_LPT_NNODE
:
1066 case UBIFS_LPT_PNODE
:
1068 case UBIFS_LPT_LTAB
:
1070 case UBIFS_LPT_LSAVE
:
1077 * get_pad_len - return the length of padding in a buffer.
1078 * @c: UBIFS file-system description object
1080 * @len: length of buffer
1082 static int get_pad_len(const struct ubifs_info
*c
, uint8_t *buf
, int len
)
1086 if (c
->min_io_size
== 1)
1088 offs
= c
->leb_size
- len
;
1089 pad_len
= ALIGN(offs
, c
->min_io_size
) - offs
;
1094 * get_lpt_node_type - return type (and node number) of a node in a buffer.
1095 * @c: UBIFS file-system description object
1097 * @node_num: node number is returned here
1099 static int get_lpt_node_type(const struct ubifs_info
*c
, uint8_t *buf
,
1102 uint8_t *addr
= buf
+ UBIFS_LPT_CRC_BYTES
;
1103 int pos
= 0, node_type
;
1105 node_type
= ubifs_unpack_bits(&addr
, &pos
, UBIFS_LPT_TYPE_BITS
);
1106 *node_num
= ubifs_unpack_bits(&addr
, &pos
, c
->pcnt_bits
);
1111 * is_a_node - determine if a buffer contains a node.
1112 * @c: UBIFS file-system description object
1114 * @len: length of buffer
1116 * This function returns %1 if the buffer contains a node or %0 if it does not.
1118 static int is_a_node(const struct ubifs_info
*c
, uint8_t *buf
, int len
)
1120 uint8_t *addr
= buf
+ UBIFS_LPT_CRC_BYTES
;
1121 int pos
= 0, node_type
, node_len
;
1122 uint16_t crc
, calc_crc
;
1124 if (len
< UBIFS_LPT_CRC_BYTES
+ (UBIFS_LPT_TYPE_BITS
+ 7) / 8)
1126 node_type
= ubifs_unpack_bits(&addr
, &pos
, UBIFS_LPT_TYPE_BITS
);
1127 if (node_type
== UBIFS_LPT_NOT_A_NODE
)
1129 node_len
= get_lpt_node_len(c
, node_type
);
1130 if (!node_len
|| node_len
> len
)
1134 crc
= ubifs_unpack_bits(&addr
, &pos
, UBIFS_LPT_CRC_BITS
);
1135 calc_crc
= crc16(-1, buf
+ UBIFS_LPT_CRC_BYTES
,
1136 node_len
- UBIFS_LPT_CRC_BYTES
);
1137 if (crc
!= calc_crc
)
1143 * lpt_gc_lnum - garbage collect a LPT LEB.
1144 * @c: UBIFS file-system description object
1145 * @lnum: LEB number to garbage collect
1147 * LPT garbage collection is used only for the "big" LPT model
1148 * (c->big_lpt == 1). Garbage collection simply involves marking all the nodes
1149 * in the LEB being garbage-collected as dirty. The dirty nodes are written
1150 * next commit, after which the LEB is free to be reused.
1152 * This function returns %0 on success and a negative error code on failure.
1154 static int lpt_gc_lnum(struct ubifs_info
*c
, int lnum
)
1156 int err
, len
= c
->leb_size
, node_type
, node_num
, node_len
, offs
;
1157 void *buf
= c
->lpt_buf
;
1159 dbg_lp("LEB %d", lnum
);
1161 err
= ubifs_leb_read(c
, lnum
, buf
, 0, c
->leb_size
, 1);
1166 if (!is_a_node(c
, buf
, len
)) {
1169 pad_len
= get_pad_len(c
, buf
, len
);
1177 node_type
= get_lpt_node_type(c
, buf
, &node_num
);
1178 node_len
= get_lpt_node_len(c
, node_type
);
1179 offs
= c
->leb_size
- len
;
1180 ubifs_assert(node_len
!= 0);
1181 mutex_lock(&c
->lp_mutex
);
1182 err
= make_node_dirty(c
, node_type
, node_num
, lnum
, offs
);
1183 mutex_unlock(&c
->lp_mutex
);
1193 * lpt_gc - LPT garbage collection.
1194 * @c: UBIFS file-system description object
1196 * Select a LPT LEB for LPT garbage collection and call 'lpt_gc_lnum()'.
1197 * Returns %0 on success and a negative error code on failure.
1199 static int lpt_gc(struct ubifs_info
*c
)
1201 int i
, lnum
= -1, dirty
= 0;
1203 mutex_lock(&c
->lp_mutex
);
1204 for (i
= 0; i
< c
->lpt_lebs
; i
++) {
1205 ubifs_assert(!c
->ltab
[i
].tgc
);
1206 if (i
+ c
->lpt_first
== c
->nhead_lnum
||
1207 c
->ltab
[i
].free
+ c
->ltab
[i
].dirty
== c
->leb_size
)
1209 if (c
->ltab
[i
].dirty
> dirty
) {
1210 dirty
= c
->ltab
[i
].dirty
;
1211 lnum
= i
+ c
->lpt_first
;
1214 mutex_unlock(&c
->lp_mutex
);
1217 return lpt_gc_lnum(c
, lnum
);
1221 * ubifs_lpt_start_commit - UBIFS commit starts.
1222 * @c: the UBIFS file-system description object
1224 * This function has to be called when UBIFS starts the commit operation.
1225 * This function "freezes" all currently dirty LEB properties and does not
1226 * change them anymore. Further changes are saved and tracked separately
1227 * because they are not part of this commit. This function returns zero in case
1228 * of success and a negative error code in case of failure.
1230 int ubifs_lpt_start_commit(struct ubifs_info
*c
)
1236 mutex_lock(&c
->lp_mutex
);
1237 err
= dbg_chk_lpt_free_spc(c
);
1240 err
= dbg_check_ltab(c
);
1244 if (c
->check_lpt_free
) {
1246 * We ensure there is enough free space in
1247 * ubifs_lpt_post_commit() by marking nodes dirty. That
1248 * information is lost when we unmount, so we also need
1249 * to check free space once after mounting also.
1251 c
->check_lpt_free
= 0;
1252 while (need_write_all(c
)) {
1253 mutex_unlock(&c
->lp_mutex
);
1257 mutex_lock(&c
->lp_mutex
);
1263 if (!c
->dirty_pn_cnt
) {
1264 dbg_cmt("no cnodes to commit");
1269 if (!c
->big_lpt
&& need_write_all(c
)) {
1270 /* If needed, write everything */
1271 err
= make_tree_dirty(c
);
1280 cnt
= get_cnodes_to_commit(c
);
1281 ubifs_assert(cnt
!= 0);
1283 err
= layout_cnodes(c
);
1287 /* Copy the LPT's own lprops for end commit to write */
1288 memcpy(c
->ltab_cmt
, c
->ltab
,
1289 sizeof(struct ubifs_lpt_lprops
) * c
->lpt_lebs
);
1290 c
->lpt_drty_flgs
&= ~(LTAB_DIRTY
| LSAVE_DIRTY
);
1293 mutex_unlock(&c
->lp_mutex
);
1298 * free_obsolete_cnodes - free obsolete cnodes for commit end.
1299 * @c: UBIFS file-system description object
1301 static void free_obsolete_cnodes(struct ubifs_info
*c
)
1303 struct ubifs_cnode
*cnode
, *cnext
;
1305 cnext
= c
->lpt_cnext
;
1310 cnext
= cnode
->cnext
;
1311 if (test_bit(OBSOLETE_CNODE
, &cnode
->flags
))
1314 cnode
->cnext
= NULL
;
1315 } while (cnext
!= c
->lpt_cnext
);
1316 c
->lpt_cnext
= NULL
;
1320 * ubifs_lpt_end_commit - finish the commit operation.
1321 * @c: the UBIFS file-system description object
1323 * This function has to be called when the commit operation finishes. It
1324 * flushes the changes which were "frozen" by 'ubifs_lprops_start_commit()' to
1325 * the media. Returns zero in case of success and a negative error code in case
1328 int ubifs_lpt_end_commit(struct ubifs_info
*c
)
1337 err
= write_cnodes(c
);
1341 mutex_lock(&c
->lp_mutex
);
1342 free_obsolete_cnodes(c
);
1343 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
);
1497 * Everything below is related to debugging.
1501 * dbg_is_all_ff - determine if a buffer contains only 0xFF bytes.
1503 * @len: buffer length
1505 static int dbg_is_all_ff(uint8_t *buf
, int len
)
1509 for (i
= 0; i
< len
; i
++)
1516 * dbg_is_nnode_dirty - determine if a nnode is dirty.
1517 * @c: the UBIFS file-system description object
1518 * @lnum: LEB number where nnode was written
1519 * @offs: offset where nnode was written
1521 static int dbg_is_nnode_dirty(struct ubifs_info
*c
, int lnum
, int offs
)
1523 struct ubifs_nnode
*nnode
;
1526 /* Entire tree is in memory so first_nnode / next_nnode are OK */
1527 nnode
= first_nnode(c
, &hght
);
1528 for (; nnode
; nnode
= next_nnode(c
, nnode
, &hght
)) {
1529 struct ubifs_nbranch
*branch
;
1532 if (nnode
->parent
) {
1533 branch
= &nnode
->parent
->nbranch
[nnode
->iip
];
1534 if (branch
->lnum
!= lnum
|| branch
->offs
!= offs
)
1536 if (test_bit(DIRTY_CNODE
, &nnode
->flags
))
1540 if (c
->lpt_lnum
!= lnum
|| c
->lpt_offs
!= offs
)
1542 if (test_bit(DIRTY_CNODE
, &nnode
->flags
))
1551 * dbg_is_pnode_dirty - determine if a pnode is dirty.
1552 * @c: the UBIFS file-system description object
1553 * @lnum: LEB number where pnode was written
1554 * @offs: offset where pnode was written
1556 static int dbg_is_pnode_dirty(struct ubifs_info
*c
, int lnum
, int offs
)
1560 cnt
= DIV_ROUND_UP(c
->main_lebs
, UBIFS_LPT_FANOUT
);
1561 for (i
= 0; i
< cnt
; i
++) {
1562 struct ubifs_pnode
*pnode
;
1563 struct ubifs_nbranch
*branch
;
1566 pnode
= pnode_lookup(c
, i
);
1568 return PTR_ERR(pnode
);
1569 branch
= &pnode
->parent
->nbranch
[pnode
->iip
];
1570 if (branch
->lnum
!= lnum
|| branch
->offs
!= offs
)
1572 if (test_bit(DIRTY_CNODE
, &pnode
->flags
))
1580 * dbg_is_ltab_dirty - determine if a ltab node is dirty.
1581 * @c: the UBIFS file-system description object
1582 * @lnum: LEB number where ltab node was written
1583 * @offs: offset where ltab node was written
1585 static int dbg_is_ltab_dirty(struct ubifs_info
*c
, int lnum
, int offs
)
1587 if (lnum
!= c
->ltab_lnum
|| offs
!= c
->ltab_offs
)
1589 return (c
->lpt_drty_flgs
& LTAB_DIRTY
) != 0;
1593 * dbg_is_lsave_dirty - determine if a lsave node is dirty.
1594 * @c: the UBIFS file-system description object
1595 * @lnum: LEB number where lsave node was written
1596 * @offs: offset where lsave node was written
1598 static int dbg_is_lsave_dirty(struct ubifs_info
*c
, int lnum
, int offs
)
1600 if (lnum
!= c
->lsave_lnum
|| offs
!= c
->lsave_offs
)
1602 return (c
->lpt_drty_flgs
& LSAVE_DIRTY
) != 0;
1606 * dbg_is_node_dirty - determine if a node is dirty.
1607 * @c: the UBIFS file-system description object
1608 * @node_type: node type
1609 * @lnum: LEB number where node was written
1610 * @offs: offset where node was written
1612 static int dbg_is_node_dirty(struct ubifs_info
*c
, int node_type
, int lnum
,
1615 switch (node_type
) {
1616 case UBIFS_LPT_NNODE
:
1617 return dbg_is_nnode_dirty(c
, lnum
, offs
);
1618 case UBIFS_LPT_PNODE
:
1619 return dbg_is_pnode_dirty(c
, lnum
, offs
);
1620 case UBIFS_LPT_LTAB
:
1621 return dbg_is_ltab_dirty(c
, lnum
, offs
);
1622 case UBIFS_LPT_LSAVE
:
1623 return dbg_is_lsave_dirty(c
, lnum
, offs
);
1629 * dbg_check_ltab_lnum - check the ltab for a LPT LEB number.
1630 * @c: the UBIFS file-system description object
1631 * @lnum: LEB number where node was written
1632 * @offs: offset where node was written
1634 * This function returns %0 on success and a negative error code on failure.
1636 static int dbg_check_ltab_lnum(struct ubifs_info
*c
, int lnum
)
1638 int err
, len
= c
->leb_size
, dirty
= 0, node_type
, node_num
, node_len
;
1642 if (!dbg_is_chk_lprops(c
))
1645 buf
= p
= __vmalloc(c
->leb_size
, GFP_NOFS
, PAGE_KERNEL
);
1647 ubifs_err("cannot allocate memory for ltab checking");
1651 dbg_lp("LEB %d", lnum
);
1653 err
= ubifs_leb_read(c
, lnum
, buf
, 0, c
->leb_size
, 1);
1658 if (!is_a_node(c
, p
, len
)) {
1661 pad_len
= get_pad_len(c
, p
, len
);
1668 if (!dbg_is_all_ff(p
, len
)) {
1669 dbg_msg("invalid empty space in LEB %d at %d",
1670 lnum
, c
->leb_size
- len
);
1673 i
= lnum
- c
->lpt_first
;
1674 if (len
!= c
->ltab
[i
].free
) {
1675 dbg_msg("invalid free space in LEB %d "
1676 "(free %d, expected %d)",
1677 lnum
, len
, c
->ltab
[i
].free
);
1680 if (dirty
!= c
->ltab
[i
].dirty
) {
1681 dbg_msg("invalid dirty space in LEB %d "
1682 "(dirty %d, expected %d)",
1683 lnum
, dirty
, c
->ltab
[i
].dirty
);
1688 node_type
= get_lpt_node_type(c
, p
, &node_num
);
1689 node_len
= get_lpt_node_len(c
, node_type
);
1690 ret
= dbg_is_node_dirty(c
, node_type
, lnum
, c
->leb_size
- len
);
1704 * dbg_check_ltab - check the free and dirty space in the ltab.
1705 * @c: the UBIFS file-system description object
1707 * This function returns %0 on success and a negative error code on failure.
1709 int dbg_check_ltab(struct ubifs_info
*c
)
1711 int lnum
, err
, i
, cnt
;
1713 if (!dbg_is_chk_lprops(c
))
1716 /* Bring the entire tree into memory */
1717 cnt
= DIV_ROUND_UP(c
->main_lebs
, UBIFS_LPT_FANOUT
);
1718 for (i
= 0; i
< cnt
; i
++) {
1719 struct ubifs_pnode
*pnode
;
1721 pnode
= pnode_lookup(c
, i
);
1723 return PTR_ERR(pnode
);
1728 err
= dbg_check_lpt_nodes(c
, (struct ubifs_cnode
*)c
->nroot
, 0, 0);
1732 /* Check each LEB */
1733 for (lnum
= c
->lpt_first
; lnum
<= c
->lpt_last
; lnum
++) {
1734 err
= dbg_check_ltab_lnum(c
, lnum
);
1736 dbg_err("failed at LEB %d", lnum
);
1741 dbg_lp("succeeded");
1746 * dbg_chk_lpt_free_spc - check LPT free space is enough to write entire LPT.
1747 * @c: the UBIFS file-system description object
1749 * This function returns %0 on success and a negative error code on failure.
1751 int dbg_chk_lpt_free_spc(struct ubifs_info
*c
)
1756 if (!dbg_is_chk_lprops(c
))
1759 for (i
= 0; i
< c
->lpt_lebs
; i
++) {
1760 if (c
->ltab
[i
].tgc
|| c
->ltab
[i
].cmt
)
1762 if (i
+ c
->lpt_first
== c
->nhead_lnum
)
1763 free
+= c
->leb_size
- c
->nhead_offs
;
1764 else if (c
->ltab
[i
].free
== c
->leb_size
)
1765 free
+= c
->leb_size
;
1767 if (free
< c
->lpt_sz
) {
1768 dbg_err("LPT space error: free %lld lpt_sz %lld",
1770 ubifs_dump_lpt_info(c
);
1771 ubifs_dump_lpt_lebs(c
);
1779 * dbg_chk_lpt_sz - check LPT does not write more than LPT size.
1780 * @c: the UBIFS file-system description object
1781 * @action: what to do
1782 * @len: length written
1784 * This function returns %0 on success and a negative error code on failure.
1785 * The @action argument may be one of:
1786 * o %0 - LPT debugging checking starts, initialize debugging variables;
1787 * o %1 - wrote an LPT node, increase LPT size by @len bytes;
1788 * o %2 - switched to a different LEB and wasted @len bytes;
1789 * o %3 - check that we've written the right number of bytes.
1790 * o %4 - wasted @len bytes;
1792 int dbg_chk_lpt_sz(struct ubifs_info
*c
, int action
, int len
)
1794 struct ubifs_debug_info
*d
= c
->dbg
;
1795 long long chk_lpt_sz
, lpt_sz
;
1798 if (!dbg_is_chk_lprops(c
))
1805 d
->chk_lpt_lebs
= 0;
1806 d
->chk_lpt_wastage
= 0;
1807 if (c
->dirty_pn_cnt
> c
->pnode_cnt
) {
1808 dbg_err("dirty pnodes %d exceed max %d",
1809 c
->dirty_pn_cnt
, c
->pnode_cnt
);
1812 if (c
->dirty_nn_cnt
> c
->nnode_cnt
) {
1813 dbg_err("dirty nnodes %d exceed max %d",
1814 c
->dirty_nn_cnt
, c
->nnode_cnt
);
1819 d
->chk_lpt_sz
+= len
;
1822 d
->chk_lpt_sz
+= len
;
1823 d
->chk_lpt_wastage
+= len
;
1824 d
->chk_lpt_lebs
+= 1;
1827 chk_lpt_sz
= c
->leb_size
;
1828 chk_lpt_sz
*= d
->chk_lpt_lebs
;
1829 chk_lpt_sz
+= len
- c
->nhead_offs
;
1830 if (d
->chk_lpt_sz
!= chk_lpt_sz
) {
1831 dbg_err("LPT wrote %lld but space used was %lld",
1832 d
->chk_lpt_sz
, chk_lpt_sz
);
1835 if (d
->chk_lpt_sz
> c
->lpt_sz
) {
1836 dbg_err("LPT wrote %lld but lpt_sz is %lld",
1837 d
->chk_lpt_sz
, c
->lpt_sz
);
1840 if (d
->chk_lpt_sz2
&& d
->chk_lpt_sz
!= d
->chk_lpt_sz2
) {
1841 dbg_err("LPT layout size %lld but wrote %lld",
1842 d
->chk_lpt_sz
, d
->chk_lpt_sz2
);
1845 if (d
->chk_lpt_sz2
&& d
->new_nhead_offs
!= len
) {
1846 dbg_err("LPT new nhead offs: expected %d was %d",
1847 d
->new_nhead_offs
, len
);
1850 lpt_sz
= (long long)c
->pnode_cnt
* c
->pnode_sz
;
1851 lpt_sz
+= (long long)c
->nnode_cnt
* c
->nnode_sz
;
1852 lpt_sz
+= c
->ltab_sz
;
1854 lpt_sz
+= c
->lsave_sz
;
1855 if (d
->chk_lpt_sz
- d
->chk_lpt_wastage
> lpt_sz
) {
1856 dbg_err("LPT chk_lpt_sz %lld + waste %lld exceeds %lld",
1857 d
->chk_lpt_sz
, d
->chk_lpt_wastage
, lpt_sz
);
1861 ubifs_dump_lpt_info(c
);
1862 ubifs_dump_lpt_lebs(c
);
1865 d
->chk_lpt_sz2
= d
->chk_lpt_sz
;
1867 d
->chk_lpt_wastage
= 0;
1868 d
->chk_lpt_lebs
= 0;
1869 d
->new_nhead_offs
= len
;
1872 d
->chk_lpt_sz
+= len
;
1873 d
->chk_lpt_wastage
+= len
;
1881 * ubifs_dump_lpt_leb - dump an LPT LEB.
1882 * @c: UBIFS file-system description object
1883 * @lnum: LEB number to dump
1885 * This function dumps an LEB from LPT area. Nodes in this area are very
1886 * different to nodes in the main area (e.g., they do not have common headers,
1887 * they do not have 8-byte alignments, etc), so we have a separate function to
1888 * dump LPT area LEBs. Note, LPT has to be locked by the caller.
1890 static void dump_lpt_leb(const struct ubifs_info
*c
, int lnum
)
1892 int err
, len
= c
->leb_size
, node_type
, node_num
, node_len
, offs
;
1895 printk(KERN_DEBUG
"(pid %d) start dumping LEB %d\n",
1896 current
->pid
, lnum
);
1897 buf
= p
= __vmalloc(c
->leb_size
, GFP_NOFS
, PAGE_KERNEL
);
1899 ubifs_err("cannot allocate memory to dump LPT");
1903 err
= ubifs_leb_read(c
, lnum
, buf
, 0, c
->leb_size
, 1);
1908 offs
= c
->leb_size
- len
;
1909 if (!is_a_node(c
, p
, len
)) {
1912 pad_len
= get_pad_len(c
, p
, len
);
1914 printk(KERN_DEBUG
"LEB %d:%d, pad %d bytes\n",
1915 lnum
, offs
, pad_len
);
1921 printk(KERN_DEBUG
"LEB %d:%d, free %d bytes\n",
1926 node_type
= get_lpt_node_type(c
, p
, &node_num
);
1927 switch (node_type
) {
1928 case UBIFS_LPT_PNODE
:
1930 node_len
= c
->pnode_sz
;
1932 printk(KERN_DEBUG
"LEB %d:%d, pnode num %d\n",
1933 lnum
, offs
, node_num
);
1935 printk(KERN_DEBUG
"LEB %d:%d, pnode\n",
1939 case UBIFS_LPT_NNODE
:
1942 struct ubifs_nnode nnode
;
1944 node_len
= c
->nnode_sz
;
1946 printk(KERN_DEBUG
"LEB %d:%d, nnode num %d, ",
1947 lnum
, offs
, node_num
);
1949 printk(KERN_DEBUG
"LEB %d:%d, nnode, ",
1951 err
= ubifs_unpack_nnode(c
, p
, &nnode
);
1952 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
1953 printk(KERN_CONT
"%d:%d", nnode
.nbranch
[i
].lnum
,
1954 nnode
.nbranch
[i
].offs
);
1955 if (i
!= UBIFS_LPT_FANOUT
- 1)
1956 printk(KERN_CONT
", ");
1958 printk(KERN_CONT
"\n");
1961 case UBIFS_LPT_LTAB
:
1962 node_len
= c
->ltab_sz
;
1963 printk(KERN_DEBUG
"LEB %d:%d, ltab\n",
1966 case UBIFS_LPT_LSAVE
:
1967 node_len
= c
->lsave_sz
;
1968 printk(KERN_DEBUG
"LEB %d:%d, lsave len\n", lnum
, offs
);
1971 ubifs_err("LPT node type %d not recognized", node_type
);
1979 printk(KERN_DEBUG
"(pid %d) finish dumping LEB %d\n",
1980 current
->pid
, lnum
);
1987 * ubifs_dump_lpt_lebs - dump LPT lebs.
1988 * @c: UBIFS file-system description object
1990 * This function dumps all LPT LEBs. The caller has to make sure the LPT is
1993 void ubifs_dump_lpt_lebs(const struct ubifs_info
*c
)
1997 printk(KERN_DEBUG
"(pid %d) start dumping all LPT LEBs\n",
1999 for (i
= 0; i
< c
->lpt_lebs
; i
++)
2000 dump_lpt_leb(c
, i
+ c
->lpt_first
);
2001 printk(KERN_DEBUG
"(pid %d) finish dumping all LPT LEBs\n",
2006 * dbg_populate_lsave - debugging version of 'populate_lsave()'
2007 * @c: UBIFS file-system description object
2009 * This is a debugging version for 'populate_lsave()' which populates lsave
2010 * with random LEBs instead of useful LEBs, which is good for test coverage.
2011 * Returns zero if lsave has not been populated (this debugging feature is
2012 * disabled) an non-zero if lsave has been populated.
2014 static int dbg_populate_lsave(struct ubifs_info
*c
)
2016 struct ubifs_lprops
*lprops
;
2017 struct ubifs_lpt_heap
*heap
;
2020 if (!dbg_is_chk_gen(c
))
2025 for (i
= 0; i
< c
->lsave_cnt
; i
++)
2026 c
->lsave
[i
] = c
->main_first
;
2028 list_for_each_entry(lprops
, &c
->empty_list
, list
)
2029 c
->lsave
[random32() % c
->lsave_cnt
] = lprops
->lnum
;
2030 list_for_each_entry(lprops
, &c
->freeable_list
, list
)
2031 c
->lsave
[random32() % c
->lsave_cnt
] = lprops
->lnum
;
2032 list_for_each_entry(lprops
, &c
->frdi_idx_list
, list
)
2033 c
->lsave
[random32() % c
->lsave_cnt
] = lprops
->lnum
;
2035 heap
= &c
->lpt_heap
[LPROPS_DIRTY_IDX
- 1];
2036 for (i
= 0; i
< heap
->cnt
; i
++)
2037 c
->lsave
[random32() % c
->lsave_cnt
] = heap
->arr
[i
]->lnum
;
2038 heap
= &c
->lpt_heap
[LPROPS_DIRTY
- 1];
2039 for (i
= 0; i
< heap
->cnt
; i
++)
2040 c
->lsave
[random32() % c
->lsave_cnt
] = heap
->arr
[i
]->lnum
;
2041 heap
= &c
->lpt_heap
[LPROPS_FREE
- 1];
2042 for (i
= 0; i
< heap
->cnt
; i
++)
2043 c
->lsave
[random32() % c
->lsave_cnt
] = heap
->arr
[i
]->lnum
;