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>
32 * first_dirty_cnode - find first dirty cnode.
33 * @c: UBIFS file-system description object
34 * @nnode: nnode at which to start
36 * This function returns the first dirty cnode or %NULL if there is not one.
38 static struct ubifs_cnode
*first_dirty_cnode(struct ubifs_nnode
*nnode
)
44 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
45 struct ubifs_cnode
*cnode
;
47 cnode
= nnode
->nbranch
[i
].cnode
;
49 test_bit(DIRTY_CNODE
, &cnode
->flags
)) {
50 if (cnode
->level
== 0)
52 nnode
= (struct ubifs_nnode
*)cnode
;
58 return (struct ubifs_cnode
*)nnode
;
63 * next_dirty_cnode - find next dirty cnode.
64 * @cnode: cnode from which to begin searching
66 * This function returns the next dirty cnode or %NULL if there is not one.
68 static struct ubifs_cnode
*next_dirty_cnode(struct ubifs_cnode
*cnode
)
70 struct ubifs_nnode
*nnode
;
74 nnode
= cnode
->parent
;
77 for (i
= cnode
->iip
+ 1; i
< UBIFS_LPT_FANOUT
; i
++) {
78 cnode
= nnode
->nbranch
[i
].cnode
;
79 if (cnode
&& test_bit(DIRTY_CNODE
, &cnode
->flags
)) {
80 if (cnode
->level
== 0)
81 return cnode
; /* cnode is a pnode */
82 /* cnode is a nnode */
83 return first_dirty_cnode((struct ubifs_nnode
*)cnode
);
86 return (struct ubifs_cnode
*)nnode
;
90 * get_cnodes_to_commit - create list of dirty cnodes to commit.
91 * @c: UBIFS file-system description object
93 * This function returns the number of cnodes to commit.
95 static int get_cnodes_to_commit(struct ubifs_info
*c
)
97 struct ubifs_cnode
*cnode
, *cnext
;
103 if (!test_bit(DIRTY_CNODE
, &c
->nroot
->flags
))
106 c
->lpt_cnext
= first_dirty_cnode(c
->nroot
);
107 cnode
= c
->lpt_cnext
;
112 ubifs_assert(!test_bit(COW_ZNODE
, &cnode
->flags
));
113 __set_bit(COW_ZNODE
, &cnode
->flags
);
114 cnext
= next_dirty_cnode(cnode
);
116 cnode
->cnext
= c
->lpt_cnext
;
119 cnode
->cnext
= cnext
;
123 dbg_cmt("committing %d cnodes", cnt
);
124 dbg_lp("committing %d cnodes", cnt
);
125 ubifs_assert(cnt
== c
->dirty_nn_cnt
+ c
->dirty_pn_cnt
);
130 * upd_ltab - update LPT LEB properties.
131 * @c: UBIFS file-system description object
133 * @free: amount of free space
134 * @dirty: amount of dirty space to add
136 static void upd_ltab(struct ubifs_info
*c
, int lnum
, int free
, int dirty
)
138 dbg_lp("LEB %d free %d dirty %d to %d +%d",
139 lnum
, c
->ltab
[lnum
- c
->lpt_first
].free
,
140 c
->ltab
[lnum
- c
->lpt_first
].dirty
, free
, dirty
);
141 ubifs_assert(lnum
>= c
->lpt_first
&& lnum
<= c
->lpt_last
);
142 c
->ltab
[lnum
- c
->lpt_first
].free
= free
;
143 c
->ltab
[lnum
- c
->lpt_first
].dirty
+= dirty
;
147 * alloc_lpt_leb - allocate an LPT LEB that is empty.
148 * @c: UBIFS file-system description object
149 * @lnum: LEB number is passed and returned here
151 * This function finds the next empty LEB in the ltab starting from @lnum. If a
152 * an empty LEB is found it is returned in @lnum and the function returns %0.
153 * Otherwise the function returns -ENOSPC. Note however, that LPT is designed
154 * never to run out of space.
156 static int alloc_lpt_leb(struct ubifs_info
*c
, int *lnum
)
160 n
= *lnum
- c
->lpt_first
+ 1;
161 for (i
= n
; i
< c
->lpt_lebs
; i
++) {
162 if (c
->ltab
[i
].tgc
|| c
->ltab
[i
].cmt
)
164 if (c
->ltab
[i
].free
== c
->leb_size
) {
166 *lnum
= i
+ c
->lpt_first
;
171 for (i
= 0; i
< n
; i
++) {
172 if (c
->ltab
[i
].tgc
|| c
->ltab
[i
].cmt
)
174 if (c
->ltab
[i
].free
== c
->leb_size
) {
176 *lnum
= i
+ c
->lpt_first
;
184 * layout_cnodes - layout cnodes for commit.
185 * @c: UBIFS file-system description object
187 * This function returns %0 on success and a negative error code on failure.
189 static int layout_cnodes(struct ubifs_info
*c
)
191 int lnum
, offs
, len
, alen
, done_lsave
, done_ltab
, err
;
192 struct ubifs_cnode
*cnode
;
194 err
= dbg_chk_lpt_sz(c
, 0, 0);
197 cnode
= c
->lpt_cnext
;
200 lnum
= c
->nhead_lnum
;
201 offs
= c
->nhead_offs
;
202 /* Try to place lsave and ltab nicely */
203 done_lsave
= !c
->big_lpt
;
205 if (!done_lsave
&& offs
+ c
->lsave_sz
<= c
->leb_size
) {
207 c
->lsave_lnum
= lnum
;
208 c
->lsave_offs
= offs
;
210 dbg_chk_lpt_sz(c
, 1, c
->lsave_sz
);
213 if (offs
+ c
->ltab_sz
<= c
->leb_size
) {
218 dbg_chk_lpt_sz(c
, 1, c
->ltab_sz
);
224 c
->dirty_nn_cnt
-= 1;
227 c
->dirty_pn_cnt
-= 1;
229 while (offs
+ len
> c
->leb_size
) {
230 alen
= ALIGN(offs
, c
->min_io_size
);
231 upd_ltab(c
, lnum
, c
->leb_size
- alen
, alen
- offs
);
232 dbg_chk_lpt_sz(c
, 2, alen
- offs
);
233 err
= alloc_lpt_leb(c
, &lnum
);
237 ubifs_assert(lnum
>= c
->lpt_first
&&
238 lnum
<= c
->lpt_last
);
239 /* Try to place lsave and ltab nicely */
242 c
->lsave_lnum
= lnum
;
243 c
->lsave_offs
= offs
;
245 dbg_chk_lpt_sz(c
, 1, c
->lsave_sz
);
253 dbg_chk_lpt_sz(c
, 1, c
->ltab_sz
);
259 cnode
->parent
->nbranch
[cnode
->iip
].lnum
= lnum
;
260 cnode
->parent
->nbranch
[cnode
->iip
].offs
= offs
;
266 dbg_chk_lpt_sz(c
, 1, len
);
267 cnode
= cnode
->cnext
;
268 } while (cnode
&& cnode
!= c
->lpt_cnext
);
270 /* Make sure to place LPT's save table */
272 if (offs
+ c
->lsave_sz
> c
->leb_size
) {
273 alen
= ALIGN(offs
, c
->min_io_size
);
274 upd_ltab(c
, lnum
, c
->leb_size
- alen
, alen
- offs
);
275 dbg_chk_lpt_sz(c
, 2, alen
- offs
);
276 err
= alloc_lpt_leb(c
, &lnum
);
280 ubifs_assert(lnum
>= c
->lpt_first
&&
281 lnum
<= c
->lpt_last
);
284 c
->lsave_lnum
= lnum
;
285 c
->lsave_offs
= offs
;
287 dbg_chk_lpt_sz(c
, 1, c
->lsave_sz
);
290 /* Make sure to place LPT's own lprops table */
292 if (offs
+ c
->ltab_sz
> c
->leb_size
) {
293 alen
= ALIGN(offs
, c
->min_io_size
);
294 upd_ltab(c
, lnum
, c
->leb_size
- alen
, alen
- offs
);
295 dbg_chk_lpt_sz(c
, 2, alen
- offs
);
296 err
= alloc_lpt_leb(c
, &lnum
);
300 ubifs_assert(lnum
>= c
->lpt_first
&&
301 lnum
<= c
->lpt_last
);
307 dbg_chk_lpt_sz(c
, 1, c
->ltab_sz
);
310 alen
= ALIGN(offs
, c
->min_io_size
);
311 upd_ltab(c
, lnum
, c
->leb_size
- alen
, alen
- offs
);
312 dbg_chk_lpt_sz(c
, 4, alen
- offs
);
313 err
= dbg_chk_lpt_sz(c
, 3, alen
);
319 ubifs_err("LPT out of space");
320 dbg_err("LPT out of space at LEB %d:%d needing %d, done_ltab %d, "
321 "done_lsave %d", lnum
, offs
, len
, done_ltab
, done_lsave
);
322 dbg_dump_lpt_info(c
);
327 * realloc_lpt_leb - allocate an LPT LEB that is empty.
328 * @c: UBIFS file-system description object
329 * @lnum: LEB number is passed and returned here
331 * This function duplicates exactly the results of the function alloc_lpt_leb.
332 * It is used during end commit to reallocate the same LEB numbers that were
333 * allocated by alloc_lpt_leb during start commit.
335 * This function finds the next LEB that was allocated by the alloc_lpt_leb
336 * function starting from @lnum. If a LEB is found it is returned in @lnum and
337 * the function returns %0. Otherwise the function returns -ENOSPC.
338 * Note however, that LPT is designed never to run out of space.
340 static int realloc_lpt_leb(struct ubifs_info
*c
, int *lnum
)
344 n
= *lnum
- c
->lpt_first
+ 1;
345 for (i
= n
; i
< c
->lpt_lebs
; i
++)
346 if (c
->ltab
[i
].cmt
) {
348 *lnum
= i
+ c
->lpt_first
;
352 for (i
= 0; i
< n
; i
++)
353 if (c
->ltab
[i
].cmt
) {
355 *lnum
= i
+ c
->lpt_first
;
362 * write_cnodes - write cnodes for commit.
363 * @c: UBIFS file-system description object
365 * This function returns %0 on success and a negative error code on failure.
367 static int write_cnodes(struct ubifs_info
*c
)
369 int lnum
, offs
, len
, from
, err
, wlen
, alen
, done_ltab
, done_lsave
;
370 struct ubifs_cnode
*cnode
;
371 void *buf
= c
->lpt_buf
;
373 cnode
= c
->lpt_cnext
;
376 lnum
= c
->nhead_lnum
;
377 offs
= c
->nhead_offs
;
379 /* Ensure empty LEB is unmapped */
381 err
= ubifs_leb_unmap(c
, lnum
);
385 /* Try to place lsave and ltab nicely */
386 done_lsave
= !c
->big_lpt
;
388 if (!done_lsave
&& offs
+ c
->lsave_sz
<= c
->leb_size
) {
390 ubifs_pack_lsave(c
, buf
+ offs
, c
->lsave
);
392 dbg_chk_lpt_sz(c
, 1, c
->lsave_sz
);
395 if (offs
+ c
->ltab_sz
<= c
->leb_size
) {
397 ubifs_pack_ltab(c
, buf
+ offs
, c
->ltab_cmt
);
399 dbg_chk_lpt_sz(c
, 1, c
->ltab_sz
);
402 /* Loop for each cnode */
408 while (offs
+ len
> c
->leb_size
) {
411 alen
= ALIGN(wlen
, c
->min_io_size
);
412 memset(buf
+ offs
, 0xff, alen
- wlen
);
413 err
= ubifs_leb_write(c
, lnum
, buf
+ from
, from
,
414 alen
, UBI_SHORTTERM
);
417 dbg_chk_lpt_sz(c
, 4, alen
- wlen
);
419 dbg_chk_lpt_sz(c
, 2, 0);
420 err
= realloc_lpt_leb(c
, &lnum
);
425 ubifs_assert(lnum
>= c
->lpt_first
&&
426 lnum
<= c
->lpt_last
);
427 err
= ubifs_leb_unmap(c
, lnum
);
430 /* Try to place lsave and ltab nicely */
433 ubifs_pack_lsave(c
, buf
+ offs
, c
->lsave
);
435 dbg_chk_lpt_sz(c
, 1, c
->lsave_sz
);
440 ubifs_pack_ltab(c
, buf
+ offs
, c
->ltab_cmt
);
442 dbg_chk_lpt_sz(c
, 1, c
->ltab_sz
);
448 ubifs_pack_nnode(c
, buf
+ offs
,
449 (struct ubifs_nnode
*)cnode
);
451 ubifs_pack_pnode(c
, buf
+ offs
,
452 (struct ubifs_pnode
*)cnode
);
454 * The reason for the barriers is the same as in case of TNC.
455 * See comment in 'write_index()'. 'dirty_cow_nnode()' and
456 * 'dirty_cow_pnode()' are the functions for which this is
459 clear_bit(DIRTY_CNODE
, &cnode
->flags
);
460 smp_mb__before_clear_bit();
461 clear_bit(COW_ZNODE
, &cnode
->flags
);
462 smp_mb__after_clear_bit();
464 dbg_chk_lpt_sz(c
, 1, len
);
465 cnode
= cnode
->cnext
;
466 } while (cnode
&& cnode
!= c
->lpt_cnext
);
468 /* Make sure to place LPT's save table */
470 if (offs
+ c
->lsave_sz
> c
->leb_size
) {
472 alen
= ALIGN(wlen
, c
->min_io_size
);
473 memset(buf
+ offs
, 0xff, alen
- wlen
);
474 err
= ubifs_leb_write(c
, lnum
, buf
+ from
, from
, alen
,
478 dbg_chk_lpt_sz(c
, 2, alen
- wlen
);
479 err
= realloc_lpt_leb(c
, &lnum
);
483 ubifs_assert(lnum
>= c
->lpt_first
&&
484 lnum
<= c
->lpt_last
);
485 err
= ubifs_leb_unmap(c
, lnum
);
490 ubifs_pack_lsave(c
, buf
+ offs
, c
->lsave
);
492 dbg_chk_lpt_sz(c
, 1, c
->lsave_sz
);
495 /* Make sure to place LPT's own lprops table */
497 if (offs
+ c
->ltab_sz
> c
->leb_size
) {
499 alen
= ALIGN(wlen
, c
->min_io_size
);
500 memset(buf
+ offs
, 0xff, alen
- wlen
);
501 err
= ubifs_leb_write(c
, lnum
, buf
+ from
, from
, alen
,
505 dbg_chk_lpt_sz(c
, 2, alen
- wlen
);
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
, UBI_SHORTTERM
);
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");
548 dbg_err("LPT out of space mismatch at LEB %d:%d needing %d, done_ltab "
549 "%d, done_lsave %d", lnum
, offs
, len
, done_ltab
, done_lsave
);
550 dbg_dump_lpt_info(c
);
555 * next_pnode - find next pnode.
556 * @c: UBIFS file-system description object
559 * This function returns the next pnode or %NULL if there are no more pnodes.
561 static struct ubifs_pnode
*next_pnode(struct ubifs_info
*c
,
562 struct ubifs_pnode
*pnode
)
564 struct ubifs_nnode
*nnode
;
567 /* Try to go right */
568 nnode
= pnode
->parent
;
569 iip
= pnode
->iip
+ 1;
570 if (iip
< UBIFS_LPT_FANOUT
) {
571 /* We assume here that LEB zero is never an LPT LEB */
572 if (nnode
->nbranch
[iip
].lnum
)
573 return ubifs_get_pnode(c
, nnode
, iip
);
576 /* Go up while can't go right */
578 iip
= nnode
->iip
+ 1;
579 nnode
= nnode
->parent
;
582 /* We assume here that LEB zero is never an LPT LEB */
583 } while (iip
>= UBIFS_LPT_FANOUT
|| !nnode
->nbranch
[iip
].lnum
);
586 nnode
= ubifs_get_nnode(c
, nnode
, iip
);
588 return (void *)nnode
;
590 /* Go down to level 1 */
591 while (nnode
->level
> 1) {
592 nnode
= ubifs_get_nnode(c
, nnode
, 0);
594 return (void *)nnode
;
597 return ubifs_get_pnode(c
, nnode
, 0);
601 * pnode_lookup - lookup a pnode in the LPT.
602 * @c: UBIFS file-system description object
603 * @i: pnode number (0 to main_lebs - 1)
605 * This function returns a pointer to the pnode on success or a negative
606 * error code on failure.
608 static struct ubifs_pnode
*pnode_lookup(struct ubifs_info
*c
, int i
)
610 int err
, h
, iip
, shft
;
611 struct ubifs_nnode
*nnode
;
614 err
= ubifs_read_nnode(c
, NULL
, 0);
618 i
<<= UBIFS_LPT_FANOUT_SHIFT
;
620 shft
= c
->lpt_hght
* UBIFS_LPT_FANOUT_SHIFT
;
621 for (h
= 1; h
< c
->lpt_hght
; h
++) {
622 iip
= ((i
>> shft
) & (UBIFS_LPT_FANOUT
- 1));
623 shft
-= UBIFS_LPT_FANOUT_SHIFT
;
624 nnode
= ubifs_get_nnode(c
, nnode
, iip
);
626 return ERR_PTR(PTR_ERR(nnode
));
628 iip
= ((i
>> shft
) & (UBIFS_LPT_FANOUT
- 1));
629 return ubifs_get_pnode(c
, nnode
, iip
);
633 * add_pnode_dirt - add dirty space to LPT LEB properties.
634 * @c: UBIFS file-system description object
635 * @pnode: pnode for which to add dirt
637 static void add_pnode_dirt(struct ubifs_info
*c
, struct ubifs_pnode
*pnode
)
639 ubifs_add_lpt_dirt(c
, pnode
->parent
->nbranch
[pnode
->iip
].lnum
,
644 * do_make_pnode_dirty - mark a pnode dirty.
645 * @c: UBIFS file-system description object
646 * @pnode: pnode to mark dirty
648 static void do_make_pnode_dirty(struct ubifs_info
*c
, struct ubifs_pnode
*pnode
)
650 /* Assumes cnext list is empty i.e. not called during commit */
651 if (!test_and_set_bit(DIRTY_CNODE
, &pnode
->flags
)) {
652 struct ubifs_nnode
*nnode
;
654 c
->dirty_pn_cnt
+= 1;
655 add_pnode_dirt(c
, pnode
);
656 /* Mark parent and ancestors dirty too */
657 nnode
= pnode
->parent
;
659 if (!test_and_set_bit(DIRTY_CNODE
, &nnode
->flags
)) {
660 c
->dirty_nn_cnt
+= 1;
661 ubifs_add_nnode_dirt(c
, nnode
);
662 nnode
= nnode
->parent
;
670 * make_tree_dirty - mark the entire LEB properties tree dirty.
671 * @c: UBIFS file-system description object
673 * This function is used by the "small" LPT model to cause the entire LEB
674 * properties tree to be written. The "small" LPT model does not use LPT
675 * garbage collection because it is more efficient to write the entire tree
676 * (because it is small).
678 * This function returns %0 on success and a negative error code on failure.
680 static int make_tree_dirty(struct ubifs_info
*c
)
682 struct ubifs_pnode
*pnode
;
684 pnode
= pnode_lookup(c
, 0);
686 do_make_pnode_dirty(c
, pnode
);
687 pnode
= next_pnode(c
, pnode
);
689 return PTR_ERR(pnode
);
695 * need_write_all - determine if the LPT area is running out of free space.
696 * @c: UBIFS file-system description object
698 * This function returns %1 if the LPT area is running out of free space and %0
701 static int need_write_all(struct ubifs_info
*c
)
706 for (i
= 0; i
< c
->lpt_lebs
; i
++) {
707 if (i
+ c
->lpt_first
== c
->nhead_lnum
)
708 free
+= c
->leb_size
- c
->nhead_offs
;
709 else if (c
->ltab
[i
].free
== c
->leb_size
)
711 else if (c
->ltab
[i
].free
+ c
->ltab
[i
].dirty
== c
->leb_size
)
714 /* Less than twice the size left */
715 if (free
<= c
->lpt_sz
* 2)
721 * lpt_tgc_start - start trivial garbage collection of LPT LEBs.
722 * @c: UBIFS file-system description object
724 * LPT trivial garbage collection is where a LPT LEB contains only dirty and
725 * free space and so may be reused as soon as the next commit is completed.
726 * This function is called during start commit to mark LPT LEBs for trivial GC.
728 static void lpt_tgc_start(struct ubifs_info
*c
)
732 for (i
= 0; i
< c
->lpt_lebs
; i
++) {
733 if (i
+ c
->lpt_first
== c
->nhead_lnum
)
735 if (c
->ltab
[i
].dirty
> 0 &&
736 c
->ltab
[i
].free
+ c
->ltab
[i
].dirty
== c
->leb_size
) {
738 c
->ltab
[i
].free
= c
->leb_size
;
739 c
->ltab
[i
].dirty
= 0;
740 dbg_lp("LEB %d", i
+ c
->lpt_first
);
746 * lpt_tgc_end - end 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 after the commit is completed (master node has been
752 * written) and unmaps LPT LEBs that were marked for trivial GC.
754 static int lpt_tgc_end(struct ubifs_info
*c
)
758 for (i
= 0; i
< c
->lpt_lebs
; i
++)
759 if (c
->ltab
[i
].tgc
) {
760 err
= ubifs_leb_unmap(c
, i
+ c
->lpt_first
);
764 dbg_lp("LEB %d", i
+ c
->lpt_first
);
770 * populate_lsave - fill the lsave array with important LEB numbers.
771 * @c: the UBIFS file-system description object
773 * This function is only called for the "big" model. It records a small number
774 * of LEB numbers of important LEBs. Important LEBs are ones that are (from
775 * most important to least important): empty, freeable, freeable index, dirty
776 * index, dirty or free. Upon mount, we read this list of LEB numbers and bring
777 * their pnodes into memory. That will stop us from having to scan the LPT
778 * straight away. For the "small" model we assume that scanning the LPT is no
781 static void populate_lsave(struct ubifs_info
*c
)
783 struct ubifs_lprops
*lprops
;
784 struct ubifs_lpt_heap
*heap
;
787 ubifs_assert(c
->big_lpt
);
788 if (!(c
->lpt_drty_flgs
& LSAVE_DIRTY
)) {
789 c
->lpt_drty_flgs
|= LSAVE_DIRTY
;
790 ubifs_add_lpt_dirt(c
, c
->lsave_lnum
, c
->lsave_sz
);
792 list_for_each_entry(lprops
, &c
->empty_list
, list
) {
793 c
->lsave
[cnt
++] = lprops
->lnum
;
794 if (cnt
>= c
->lsave_cnt
)
797 list_for_each_entry(lprops
, &c
->freeable_list
, list
) {
798 c
->lsave
[cnt
++] = lprops
->lnum
;
799 if (cnt
>= c
->lsave_cnt
)
802 list_for_each_entry(lprops
, &c
->frdi_idx_list
, list
) {
803 c
->lsave
[cnt
++] = lprops
->lnum
;
804 if (cnt
>= c
->lsave_cnt
)
807 heap
= &c
->lpt_heap
[LPROPS_DIRTY_IDX
- 1];
808 for (i
= 0; i
< heap
->cnt
; i
++) {
809 c
->lsave
[cnt
++] = heap
->arr
[i
]->lnum
;
810 if (cnt
>= c
->lsave_cnt
)
813 heap
= &c
->lpt_heap
[LPROPS_DIRTY
- 1];
814 for (i
= 0; i
< heap
->cnt
; i
++) {
815 c
->lsave
[cnt
++] = heap
->arr
[i
]->lnum
;
816 if (cnt
>= c
->lsave_cnt
)
819 heap
= &c
->lpt_heap
[LPROPS_FREE
- 1];
820 for (i
= 0; i
< heap
->cnt
; i
++) {
821 c
->lsave
[cnt
++] = heap
->arr
[i
]->lnum
;
822 if (cnt
>= c
->lsave_cnt
)
825 /* Fill it up completely */
826 while (cnt
< c
->lsave_cnt
)
827 c
->lsave
[cnt
++] = c
->main_first
;
831 * nnode_lookup - lookup a nnode in the LPT.
832 * @c: UBIFS file-system description object
835 * This function returns a pointer to the nnode on success or a negative
836 * error code on failure.
838 static struct ubifs_nnode
*nnode_lookup(struct ubifs_info
*c
, int i
)
841 struct ubifs_nnode
*nnode
;
844 err
= ubifs_read_nnode(c
, NULL
, 0);
850 iip
= i
& (UBIFS_LPT_FANOUT
- 1);
851 i
>>= UBIFS_LPT_FANOUT_SHIFT
;
854 nnode
= ubifs_get_nnode(c
, nnode
, iip
);
862 * make_nnode_dirty - find a nnode and, if found, make it dirty.
863 * @c: UBIFS file-system description object
864 * @node_num: nnode number of nnode to make dirty
865 * @lnum: LEB number where nnode was written
866 * @offs: offset where nnode was written
868 * This function is used by LPT garbage collection. LPT garbage collection is
869 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
870 * simply involves marking all the nodes in the LEB being garbage-collected as
871 * dirty. The dirty nodes are written next commit, after which the LEB is free
874 * This function returns %0 on success and a negative error code on failure.
876 static int make_nnode_dirty(struct ubifs_info
*c
, int node_num
, int lnum
,
879 struct ubifs_nnode
*nnode
;
881 nnode
= nnode_lookup(c
, node_num
);
883 return PTR_ERR(nnode
);
885 struct ubifs_nbranch
*branch
;
887 branch
= &nnode
->parent
->nbranch
[nnode
->iip
];
888 if (branch
->lnum
!= lnum
|| branch
->offs
!= offs
)
889 return 0; /* nnode is obsolete */
890 } else if (c
->lpt_lnum
!= lnum
|| c
->lpt_offs
!= offs
)
891 return 0; /* nnode is obsolete */
892 /* Assumes cnext list is empty i.e. not called during commit */
893 if (!test_and_set_bit(DIRTY_CNODE
, &nnode
->flags
)) {
894 c
->dirty_nn_cnt
+= 1;
895 ubifs_add_nnode_dirt(c
, nnode
);
896 /* Mark parent and ancestors dirty too */
897 nnode
= nnode
->parent
;
899 if (!test_and_set_bit(DIRTY_CNODE
, &nnode
->flags
)) {
900 c
->dirty_nn_cnt
+= 1;
901 ubifs_add_nnode_dirt(c
, nnode
);
902 nnode
= nnode
->parent
;
911 * make_pnode_dirty - find a pnode and, if found, make it dirty.
912 * @c: UBIFS file-system description object
913 * @node_num: pnode number of pnode to make dirty
914 * @lnum: LEB number where pnode was written
915 * @offs: offset where pnode was written
917 * This function is used by LPT garbage collection. LPT garbage collection is
918 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
919 * simply involves marking all the nodes in the LEB being garbage-collected as
920 * dirty. The dirty nodes are written next commit, after which the LEB is free
923 * This function returns %0 on success and a negative error code on failure.
925 static int make_pnode_dirty(struct ubifs_info
*c
, int node_num
, int lnum
,
928 struct ubifs_pnode
*pnode
;
929 struct ubifs_nbranch
*branch
;
931 pnode
= pnode_lookup(c
, node_num
);
933 return PTR_ERR(pnode
);
934 branch
= &pnode
->parent
->nbranch
[pnode
->iip
];
935 if (branch
->lnum
!= lnum
|| branch
->offs
!= offs
)
937 do_make_pnode_dirty(c
, pnode
);
942 * make_ltab_dirty - make ltab node dirty.
943 * @c: UBIFS file-system description object
944 * @lnum: LEB number where ltab was written
945 * @offs: offset where ltab was written
947 * This function is used by LPT garbage collection. LPT garbage collection is
948 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
949 * simply involves marking all the nodes in the LEB being garbage-collected as
950 * dirty. The dirty nodes are written next commit, after which the LEB is free
953 * This function returns %0 on success and a negative error code on failure.
955 static int make_ltab_dirty(struct ubifs_info
*c
, int lnum
, int offs
)
957 if (lnum
!= c
->ltab_lnum
|| offs
!= c
->ltab_offs
)
958 return 0; /* This ltab node is obsolete */
959 if (!(c
->lpt_drty_flgs
& LTAB_DIRTY
)) {
960 c
->lpt_drty_flgs
|= LTAB_DIRTY
;
961 ubifs_add_lpt_dirt(c
, c
->ltab_lnum
, c
->ltab_sz
);
967 * make_lsave_dirty - make lsave node dirty.
968 * @c: UBIFS file-system description object
969 * @lnum: LEB number where lsave was written
970 * @offs: offset where lsave was written
972 * This function is used by LPT garbage collection. LPT garbage collection is
973 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
974 * simply involves marking all the nodes in the LEB being garbage-collected as
975 * dirty. The dirty nodes are written next commit, after which the LEB is free
978 * This function returns %0 on success and a negative error code on failure.
980 static int make_lsave_dirty(struct ubifs_info
*c
, int lnum
, int offs
)
982 if (lnum
!= c
->lsave_lnum
|| offs
!= c
->lsave_offs
)
983 return 0; /* This lsave node is obsolete */
984 if (!(c
->lpt_drty_flgs
& LSAVE_DIRTY
)) {
985 c
->lpt_drty_flgs
|= LSAVE_DIRTY
;
986 ubifs_add_lpt_dirt(c
, c
->lsave_lnum
, c
->lsave_sz
);
992 * make_node_dirty - make node dirty.
993 * @c: UBIFS file-system description object
994 * @node_type: LPT node type
995 * @node_num: node number
996 * @lnum: LEB number where node was written
997 * @offs: offset where node was written
999 * This function is used by LPT garbage collection. LPT garbage collection is
1000 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
1001 * simply involves marking all the nodes in the LEB being garbage-collected as
1002 * dirty. The dirty nodes are written next commit, after which the LEB is free
1005 * This function returns %0 on success and a negative error code on failure.
1007 static int make_node_dirty(struct ubifs_info
*c
, int node_type
, int node_num
,
1010 switch (node_type
) {
1011 case UBIFS_LPT_NNODE
:
1012 return make_nnode_dirty(c
, node_num
, lnum
, offs
);
1013 case UBIFS_LPT_PNODE
:
1014 return make_pnode_dirty(c
, node_num
, lnum
, offs
);
1015 case UBIFS_LPT_LTAB
:
1016 return make_ltab_dirty(c
, lnum
, offs
);
1017 case UBIFS_LPT_LSAVE
:
1018 return make_lsave_dirty(c
, lnum
, offs
);
1024 * get_lpt_node_len - return the length of a node based on its type.
1025 * @c: UBIFS file-system description object
1026 * @node_type: LPT node type
1028 static int get_lpt_node_len(struct ubifs_info
*c
, int node_type
)
1030 switch (node_type
) {
1031 case UBIFS_LPT_NNODE
:
1033 case UBIFS_LPT_PNODE
:
1035 case UBIFS_LPT_LTAB
:
1037 case UBIFS_LPT_LSAVE
:
1044 * get_pad_len - return the length of padding in a buffer.
1045 * @c: UBIFS file-system description object
1047 * @len: length of buffer
1049 static int get_pad_len(struct ubifs_info
*c
, uint8_t *buf
, int len
)
1053 if (c
->min_io_size
== 1)
1055 offs
= c
->leb_size
- len
;
1056 pad_len
= ALIGN(offs
, c
->min_io_size
) - offs
;
1061 * get_lpt_node_type - return type (and node number) of a node in a buffer.
1062 * @c: UBIFS file-system description object
1064 * @node_num: node number is returned here
1066 static int get_lpt_node_type(struct ubifs_info
*c
, uint8_t *buf
, int *node_num
)
1068 uint8_t *addr
= buf
+ UBIFS_LPT_CRC_BYTES
;
1069 int pos
= 0, node_type
;
1071 node_type
= ubifs_unpack_bits(&addr
, &pos
, UBIFS_LPT_TYPE_BITS
);
1072 *node_num
= ubifs_unpack_bits(&addr
, &pos
, c
->pcnt_bits
);
1077 * is_a_node - determine if a buffer contains a node.
1078 * @c: UBIFS file-system description object
1080 * @len: length of buffer
1082 * This function returns %1 if the buffer contains a node or %0 if it does not.
1084 static int is_a_node(struct ubifs_info
*c
, uint8_t *buf
, int len
)
1086 uint8_t *addr
= buf
+ UBIFS_LPT_CRC_BYTES
;
1087 int pos
= 0, node_type
, node_len
;
1088 uint16_t crc
, calc_crc
;
1090 if (len
< UBIFS_LPT_CRC_BYTES
+ (UBIFS_LPT_TYPE_BITS
+ 7) / 8)
1092 node_type
= ubifs_unpack_bits(&addr
, &pos
, UBIFS_LPT_TYPE_BITS
);
1093 if (node_type
== UBIFS_LPT_NOT_A_NODE
)
1095 node_len
= get_lpt_node_len(c
, node_type
);
1096 if (!node_len
|| node_len
> len
)
1100 crc
= ubifs_unpack_bits(&addr
, &pos
, UBIFS_LPT_CRC_BITS
);
1101 calc_crc
= crc16(-1, buf
+ UBIFS_LPT_CRC_BYTES
,
1102 node_len
- UBIFS_LPT_CRC_BYTES
);
1103 if (crc
!= calc_crc
)
1110 * lpt_gc_lnum - garbage collect a LPT LEB.
1111 * @c: UBIFS file-system description object
1112 * @lnum: LEB number to garbage collect
1114 * LPT garbage collection is used only for the "big" LPT model
1115 * (c->big_lpt == 1). Garbage collection simply involves marking all the nodes
1116 * in the LEB being garbage-collected as dirty. The dirty nodes are written
1117 * next commit, after which the LEB is free to be reused.
1119 * This function returns %0 on success and a negative error code on failure.
1121 static int lpt_gc_lnum(struct ubifs_info
*c
, int lnum
)
1123 int err
, len
= c
->leb_size
, node_type
, node_num
, node_len
, offs
;
1124 void *buf
= c
->lpt_buf
;
1126 dbg_lp("LEB %d", lnum
);
1127 err
= ubi_read(c
->ubi
, lnum
, buf
, 0, c
->leb_size
);
1129 ubifs_err("cannot read LEB %d, error %d", lnum
, err
);
1133 if (!is_a_node(c
, buf
, len
)) {
1136 pad_len
= get_pad_len(c
, buf
, len
);
1144 node_type
= get_lpt_node_type(c
, buf
, &node_num
);
1145 node_len
= get_lpt_node_len(c
, node_type
);
1146 offs
= c
->leb_size
- len
;
1147 ubifs_assert(node_len
!= 0);
1148 mutex_lock(&c
->lp_mutex
);
1149 err
= make_node_dirty(c
, node_type
, node_num
, lnum
, offs
);
1150 mutex_unlock(&c
->lp_mutex
);
1160 * lpt_gc - LPT garbage collection.
1161 * @c: UBIFS file-system description object
1163 * Select a LPT LEB for LPT garbage collection and call 'lpt_gc_lnum()'.
1164 * Returns %0 on success and a negative error code on failure.
1166 static int lpt_gc(struct ubifs_info
*c
)
1168 int i
, lnum
= -1, dirty
= 0;
1170 mutex_lock(&c
->lp_mutex
);
1171 for (i
= 0; i
< c
->lpt_lebs
; i
++) {
1172 ubifs_assert(!c
->ltab
[i
].tgc
);
1173 if (i
+ c
->lpt_first
== c
->nhead_lnum
||
1174 c
->ltab
[i
].free
+ c
->ltab
[i
].dirty
== c
->leb_size
)
1176 if (c
->ltab
[i
].dirty
> dirty
) {
1177 dirty
= c
->ltab
[i
].dirty
;
1178 lnum
= i
+ c
->lpt_first
;
1181 mutex_unlock(&c
->lp_mutex
);
1184 return lpt_gc_lnum(c
, lnum
);
1188 * ubifs_lpt_start_commit - UBIFS commit starts.
1189 * @c: the UBIFS file-system description object
1191 * This function has to be called when UBIFS starts the commit operation.
1192 * This function "freezes" all currently dirty LEB properties and does not
1193 * change them anymore. Further changes are saved and tracked separately
1194 * because they are not part of this commit. This function returns zero in case
1195 * of success and a negative error code in case of failure.
1197 int ubifs_lpt_start_commit(struct ubifs_info
*c
)
1203 mutex_lock(&c
->lp_mutex
);
1204 err
= dbg_chk_lpt_free_spc(c
);
1207 err
= dbg_check_ltab(c
);
1211 if (c
->check_lpt_free
) {
1213 * We ensure there is enough free space in
1214 * ubifs_lpt_post_commit() by marking nodes dirty. That
1215 * information is lost when we unmount, so we also need
1216 * to check free space once after mounting also.
1218 c
->check_lpt_free
= 0;
1219 while (need_write_all(c
)) {
1220 mutex_unlock(&c
->lp_mutex
);
1224 mutex_lock(&c
->lp_mutex
);
1230 if (!c
->dirty_pn_cnt
) {
1231 dbg_cmt("no cnodes to commit");
1236 if (!c
->big_lpt
&& need_write_all(c
)) {
1237 /* If needed, write everything */
1238 err
= make_tree_dirty(c
);
1247 cnt
= get_cnodes_to_commit(c
);
1248 ubifs_assert(cnt
!= 0);
1250 err
= layout_cnodes(c
);
1254 /* Copy the LPT's own lprops for end commit to write */
1255 memcpy(c
->ltab_cmt
, c
->ltab
,
1256 sizeof(struct ubifs_lpt_lprops
) * c
->lpt_lebs
);
1257 c
->lpt_drty_flgs
&= ~(LTAB_DIRTY
| LSAVE_DIRTY
);
1260 mutex_unlock(&c
->lp_mutex
);
1265 * free_obsolete_cnodes - free obsolete cnodes for commit end.
1266 * @c: UBIFS file-system description object
1268 static void free_obsolete_cnodes(struct ubifs_info
*c
)
1270 struct ubifs_cnode
*cnode
, *cnext
;
1272 cnext
= c
->lpt_cnext
;
1277 cnext
= cnode
->cnext
;
1278 if (test_bit(OBSOLETE_CNODE
, &cnode
->flags
))
1281 cnode
->cnext
= NULL
;
1282 } while (cnext
!= c
->lpt_cnext
);
1283 c
->lpt_cnext
= NULL
;
1287 * ubifs_lpt_end_commit - finish the commit operation.
1288 * @c: the UBIFS file-system description object
1290 * This function has to be called when the commit operation finishes. It
1291 * flushes the changes which were "frozen" by 'ubifs_lprops_start_commit()' to
1292 * the media. Returns zero in case of success and a negative error code in case
1295 int ubifs_lpt_end_commit(struct ubifs_info
*c
)
1304 err
= write_cnodes(c
);
1308 mutex_lock(&c
->lp_mutex
);
1309 free_obsolete_cnodes(c
);
1310 mutex_unlock(&c
->lp_mutex
);
1316 * ubifs_lpt_post_commit - post commit LPT trivial GC and LPT GC.
1317 * @c: UBIFS file-system description object
1319 * LPT trivial GC is completed after a commit. Also LPT GC is done after a
1320 * commit for the "big" LPT model.
1322 int ubifs_lpt_post_commit(struct ubifs_info
*c
)
1326 mutex_lock(&c
->lp_mutex
);
1327 err
= lpt_tgc_end(c
);
1331 while (need_write_all(c
)) {
1332 mutex_unlock(&c
->lp_mutex
);
1336 mutex_lock(&c
->lp_mutex
);
1339 mutex_unlock(&c
->lp_mutex
);
1344 * first_nnode - find the first nnode in memory.
1345 * @c: UBIFS file-system description object
1346 * @hght: height of tree where nnode found is returned here
1348 * This function returns a pointer to the nnode found or %NULL if no nnode is
1349 * found. This function is a helper to 'ubifs_lpt_free()'.
1351 static struct ubifs_nnode
*first_nnode(struct ubifs_info
*c
, int *hght
)
1353 struct ubifs_nnode
*nnode
;
1360 for (h
= 1; h
< c
->lpt_hght
; h
++) {
1362 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
1363 if (nnode
->nbranch
[i
].nnode
) {
1365 nnode
= nnode
->nbranch
[i
].nnode
;
1377 * next_nnode - find the next nnode in memory.
1378 * @c: UBIFS file-system description object
1379 * @nnode: nnode from which to start.
1380 * @hght: height of tree where nnode is, is passed and returned here
1382 * This function returns a pointer to the nnode found or %NULL if no nnode is
1383 * found. This function is a helper to 'ubifs_lpt_free()'.
1385 static struct ubifs_nnode
*next_nnode(struct ubifs_info
*c
,
1386 struct ubifs_nnode
*nnode
, int *hght
)
1388 struct ubifs_nnode
*parent
;
1389 int iip
, h
, i
, found
;
1391 parent
= nnode
->parent
;
1394 if (nnode
->iip
== UBIFS_LPT_FANOUT
- 1) {
1398 for (iip
= nnode
->iip
+ 1; iip
< UBIFS_LPT_FANOUT
; iip
++) {
1399 nnode
= parent
->nbranch
[iip
].nnode
;
1407 for (h
= *hght
+ 1; h
< c
->lpt_hght
; h
++) {
1409 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
1410 if (nnode
->nbranch
[i
].nnode
) {
1412 nnode
= nnode
->nbranch
[i
].nnode
;
1424 * ubifs_lpt_free - free resources owned by the LPT.
1425 * @c: UBIFS file-system description object
1426 * @wr_only: free only resources used for writing
1428 void ubifs_lpt_free(struct ubifs_info
*c
, int wr_only
)
1430 struct ubifs_nnode
*nnode
;
1433 /* Free write-only things first */
1435 free_obsolete_cnodes(c
); /* Leftover from a failed commit */
1447 /* Now free the rest */
1449 nnode
= first_nnode(c
, &hght
);
1451 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++)
1452 kfree(nnode
->nbranch
[i
].nnode
);
1453 nnode
= next_nnode(c
, nnode
, &hght
);
1455 for (i
= 0; i
< LPROPS_HEAP_CNT
; i
++)
1456 kfree(c
->lpt_heap
[i
].arr
);
1457 kfree(c
->dirty_idx
.arr
);
1460 kfree(c
->lpt_nod_buf
);
1463 #ifdef CONFIG_UBIFS_FS_DEBUG
1466 * dbg_is_all_ff - determine if a buffer contains only 0xff bytes.
1468 * @len: buffer length
1470 static int dbg_is_all_ff(uint8_t *buf
, int len
)
1474 for (i
= 0; i
< len
; i
++)
1481 * dbg_is_nnode_dirty - determine if a nnode is dirty.
1482 * @c: the UBIFS file-system description object
1483 * @lnum: LEB number where nnode was written
1484 * @offs: offset where nnode was written
1486 static int dbg_is_nnode_dirty(struct ubifs_info
*c
, int lnum
, int offs
)
1488 struct ubifs_nnode
*nnode
;
1491 /* Entire tree is in memory so first_nnode / next_nnode are ok */
1492 nnode
= first_nnode(c
, &hght
);
1493 for (; nnode
; nnode
= next_nnode(c
, nnode
, &hght
)) {
1494 struct ubifs_nbranch
*branch
;
1497 if (nnode
->parent
) {
1498 branch
= &nnode
->parent
->nbranch
[nnode
->iip
];
1499 if (branch
->lnum
!= lnum
|| branch
->offs
!= offs
)
1501 if (test_bit(DIRTY_CNODE
, &nnode
->flags
))
1505 if (c
->lpt_lnum
!= lnum
|| c
->lpt_offs
!= offs
)
1507 if (test_bit(DIRTY_CNODE
, &nnode
->flags
))
1516 * dbg_is_pnode_dirty - determine if a pnode is dirty.
1517 * @c: the UBIFS file-system description object
1518 * @lnum: LEB number where pnode was written
1519 * @offs: offset where pnode was written
1521 static int dbg_is_pnode_dirty(struct ubifs_info
*c
, int lnum
, int offs
)
1525 cnt
= DIV_ROUND_UP(c
->main_lebs
, UBIFS_LPT_FANOUT
);
1526 for (i
= 0; i
< cnt
; i
++) {
1527 struct ubifs_pnode
*pnode
;
1528 struct ubifs_nbranch
*branch
;
1531 pnode
= pnode_lookup(c
, i
);
1533 return PTR_ERR(pnode
);
1534 branch
= &pnode
->parent
->nbranch
[pnode
->iip
];
1535 if (branch
->lnum
!= lnum
|| branch
->offs
!= offs
)
1537 if (test_bit(DIRTY_CNODE
, &pnode
->flags
))
1545 * dbg_is_ltab_dirty - determine if a ltab node is dirty.
1546 * @c: the UBIFS file-system description object
1547 * @lnum: LEB number where ltab node was written
1548 * @offs: offset where ltab node was written
1550 static int dbg_is_ltab_dirty(struct ubifs_info
*c
, int lnum
, int offs
)
1552 if (lnum
!= c
->ltab_lnum
|| offs
!= c
->ltab_offs
)
1554 return (c
->lpt_drty_flgs
& LTAB_DIRTY
) != 0;
1558 * dbg_is_lsave_dirty - determine if a lsave node is dirty.
1559 * @c: the UBIFS file-system description object
1560 * @lnum: LEB number where lsave node was written
1561 * @offs: offset where lsave node was written
1563 static int dbg_is_lsave_dirty(struct ubifs_info
*c
, int lnum
, int offs
)
1565 if (lnum
!= c
->lsave_lnum
|| offs
!= c
->lsave_offs
)
1567 return (c
->lpt_drty_flgs
& LSAVE_DIRTY
) != 0;
1571 * dbg_is_node_dirty - determine if a node is dirty.
1572 * @c: the UBIFS file-system description object
1573 * @node_type: node type
1574 * @lnum: LEB number where node was written
1575 * @offs: offset where node was written
1577 static int dbg_is_node_dirty(struct ubifs_info
*c
, int node_type
, int lnum
,
1580 switch (node_type
) {
1581 case UBIFS_LPT_NNODE
:
1582 return dbg_is_nnode_dirty(c
, lnum
, offs
);
1583 case UBIFS_LPT_PNODE
:
1584 return dbg_is_pnode_dirty(c
, lnum
, offs
);
1585 case UBIFS_LPT_LTAB
:
1586 return dbg_is_ltab_dirty(c
, lnum
, offs
);
1587 case UBIFS_LPT_LSAVE
:
1588 return dbg_is_lsave_dirty(c
, lnum
, offs
);
1594 * dbg_check_ltab_lnum - check the ltab for a LPT LEB number.
1595 * @c: the UBIFS file-system description object
1596 * @lnum: LEB number where node was written
1597 * @offs: offset where node was written
1599 * This function returns %0 on success and a negative error code on failure.
1601 static int dbg_check_ltab_lnum(struct ubifs_info
*c
, int lnum
)
1603 int err
, len
= c
->leb_size
, dirty
= 0, node_type
, node_num
, node_len
;
1605 void *buf
= c
->dbg_buf
;
1607 dbg_lp("LEB %d", lnum
);
1608 err
= ubi_read(c
->ubi
, lnum
, buf
, 0, c
->leb_size
);
1610 dbg_msg("ubi_read failed, LEB %d, error %d", lnum
, err
);
1614 if (!is_a_node(c
, buf
, len
)) {
1617 pad_len
= get_pad_len(c
, buf
, len
);
1624 if (!dbg_is_all_ff(buf
, len
)) {
1625 dbg_msg("invalid empty space in LEB %d at %d",
1626 lnum
, c
->leb_size
- len
);
1629 i
= lnum
- c
->lpt_first
;
1630 if (len
!= c
->ltab
[i
].free
) {
1631 dbg_msg("invalid free space in LEB %d "
1632 "(free %d, expected %d)",
1633 lnum
, len
, c
->ltab
[i
].free
);
1636 if (dirty
!= c
->ltab
[i
].dirty
) {
1637 dbg_msg("invalid dirty space in LEB %d "
1638 "(dirty %d, expected %d)",
1639 lnum
, dirty
, c
->ltab
[i
].dirty
);
1644 node_type
= get_lpt_node_type(c
, buf
, &node_num
);
1645 node_len
= get_lpt_node_len(c
, node_type
);
1646 ret
= dbg_is_node_dirty(c
, node_type
, lnum
, c
->leb_size
- len
);
1655 * dbg_check_ltab - check the free and dirty space in the ltab.
1656 * @c: the UBIFS file-system description object
1658 * This function returns %0 on success and a negative error code on failure.
1660 int dbg_check_ltab(struct ubifs_info
*c
)
1662 int lnum
, err
, i
, cnt
;
1664 if (!(ubifs_chk_flags
& UBIFS_CHK_LPROPS
))
1667 /* Bring the entire tree into memory */
1668 cnt
= DIV_ROUND_UP(c
->main_lebs
, UBIFS_LPT_FANOUT
);
1669 for (i
= 0; i
< cnt
; i
++) {
1670 struct ubifs_pnode
*pnode
;
1672 pnode
= pnode_lookup(c
, i
);
1674 return PTR_ERR(pnode
);
1679 err
= dbg_check_lpt_nodes(c
, (struct ubifs_cnode
*)c
->nroot
, 0, 0);
1683 /* Check each LEB */
1684 for (lnum
= c
->lpt_first
; lnum
<= c
->lpt_last
; lnum
++) {
1685 err
= dbg_check_ltab_lnum(c
, lnum
);
1687 dbg_err("failed at LEB %d", lnum
);
1692 dbg_lp("succeeded");
1697 * dbg_chk_lpt_free_spc - check LPT free space is enough to write entire LPT.
1698 * @c: the UBIFS file-system description object
1700 * This function returns %0 on success and a negative error code on failure.
1702 int dbg_chk_lpt_free_spc(struct ubifs_info
*c
)
1707 for (i
= 0; i
< c
->lpt_lebs
; i
++) {
1708 if (c
->ltab
[i
].tgc
|| c
->ltab
[i
].cmt
)
1710 if (i
+ c
->lpt_first
== c
->nhead_lnum
)
1711 free
+= c
->leb_size
- c
->nhead_offs
;
1712 else if (c
->ltab
[i
].free
== c
->leb_size
)
1713 free
+= c
->leb_size
;
1715 if (free
< c
->lpt_sz
) {
1716 dbg_err("LPT space error: free %lld lpt_sz %lld",
1718 dbg_dump_lpt_info(c
);
1725 * dbg_chk_lpt_sz - check LPT does not write more than LPT size.
1726 * @c: the UBIFS file-system description object
1728 * @len: length written
1730 * This function returns %0 on success and a negative error code on failure.
1732 int dbg_chk_lpt_sz(struct ubifs_info
*c
, int action
, int len
)
1734 long long chk_lpt_sz
, lpt_sz
;
1741 c
->chk_lpt_lebs
= 0;
1742 c
->chk_lpt_wastage
= 0;
1743 if (c
->dirty_pn_cnt
> c
->pnode_cnt
) {
1744 dbg_err("dirty pnodes %d exceed max %d",
1745 c
->dirty_pn_cnt
, c
->pnode_cnt
);
1748 if (c
->dirty_nn_cnt
> c
->nnode_cnt
) {
1749 dbg_err("dirty nnodes %d exceed max %d",
1750 c
->dirty_nn_cnt
, c
->nnode_cnt
);
1755 c
->chk_lpt_sz
+= len
;
1758 c
->chk_lpt_sz
+= len
;
1759 c
->chk_lpt_wastage
+= len
;
1760 c
->chk_lpt_lebs
+= 1;
1763 chk_lpt_sz
= c
->leb_size
;
1764 chk_lpt_sz
*= c
->chk_lpt_lebs
;
1765 chk_lpt_sz
+= len
- c
->nhead_offs
;
1766 if (c
->chk_lpt_sz
!= chk_lpt_sz
) {
1767 dbg_err("LPT wrote %lld but space used was %lld",
1768 c
->chk_lpt_sz
, chk_lpt_sz
);
1771 if (c
->chk_lpt_sz
> c
->lpt_sz
) {
1772 dbg_err("LPT wrote %lld but lpt_sz is %lld",
1773 c
->chk_lpt_sz
, c
->lpt_sz
);
1776 if (c
->chk_lpt_sz2
&& c
->chk_lpt_sz
!= c
->chk_lpt_sz2
) {
1777 dbg_err("LPT layout size %lld but wrote %lld",
1778 c
->chk_lpt_sz
, c
->chk_lpt_sz2
);
1781 if (c
->chk_lpt_sz2
&& c
->new_nhead_offs
!= len
) {
1782 dbg_err("LPT new nhead offs: expected %d was %d",
1783 c
->new_nhead_offs
, len
);
1786 lpt_sz
= (long long)c
->pnode_cnt
* c
->pnode_sz
;
1787 lpt_sz
+= (long long)c
->nnode_cnt
* c
->nnode_sz
;
1788 lpt_sz
+= c
->ltab_sz
;
1790 lpt_sz
+= c
->lsave_sz
;
1791 if (c
->chk_lpt_sz
- c
->chk_lpt_wastage
> lpt_sz
) {
1792 dbg_err("LPT chk_lpt_sz %lld + waste %lld exceeds %lld",
1793 c
->chk_lpt_sz
, c
->chk_lpt_wastage
, lpt_sz
);
1797 dbg_dump_lpt_info(c
);
1798 c
->chk_lpt_sz2
= c
->chk_lpt_sz
;
1800 c
->chk_lpt_wastage
= 0;
1801 c
->chk_lpt_lebs
= 0;
1802 c
->new_nhead_offs
= len
;
1805 c
->chk_lpt_sz
+= len
;
1806 c
->chk_lpt_wastage
+= len
;
1813 #endif /* CONFIG_UBIFS_FS_DEBUG */