]>
git.proxmox.com Git - mirror_ubuntu-eoan-kernel.git/blob - fs/ubifs/lpt_commit.c
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(const struct ubifs_info
*c
, struct ubifs_nnode
*nnode
)
44 ubifs_assert(c
, 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 * @c: UBIFS file-system description object
69 * @cnode: cnode from which to begin searching
71 * This function returns the next dirty cnode or %NULL if there is not one.
73 static struct ubifs_cnode
*next_dirty_cnode(const struct ubifs_info
*c
, struct ubifs_cnode
*cnode
)
75 struct ubifs_nnode
*nnode
;
78 ubifs_assert(c
, cnode
);
79 nnode
= cnode
->parent
;
82 for (i
= cnode
->iip
+ 1; i
< UBIFS_LPT_FANOUT
; i
++) {
83 cnode
= nnode
->nbranch
[i
].cnode
;
84 if (cnode
&& test_bit(DIRTY_CNODE
, &cnode
->flags
)) {
85 if (cnode
->level
== 0)
86 return cnode
; /* cnode is a pnode */
87 /* cnode is a nnode */
88 return first_dirty_cnode(c
, (struct ubifs_nnode
*)cnode
);
91 return (struct ubifs_cnode
*)nnode
;
95 * get_cnodes_to_commit - create list of dirty cnodes to commit.
96 * @c: UBIFS file-system description object
98 * This function returns the number of cnodes to commit.
100 static int get_cnodes_to_commit(struct ubifs_info
*c
)
102 struct ubifs_cnode
*cnode
, *cnext
;
108 if (!test_bit(DIRTY_CNODE
, &c
->nroot
->flags
))
111 c
->lpt_cnext
= first_dirty_cnode(c
, c
->nroot
);
112 cnode
= c
->lpt_cnext
;
117 ubifs_assert(c
, !test_bit(COW_CNODE
, &cnode
->flags
));
118 __set_bit(COW_CNODE
, &cnode
->flags
);
119 cnext
= next_dirty_cnode(c
, cnode
);
121 cnode
->cnext
= c
->lpt_cnext
;
124 cnode
->cnext
= cnext
;
128 dbg_cmt("committing %d cnodes", cnt
);
129 dbg_lp("committing %d cnodes", cnt
);
130 ubifs_assert(c
, cnt
== c
->dirty_nn_cnt
+ c
->dirty_pn_cnt
);
135 * upd_ltab - update LPT LEB properties.
136 * @c: UBIFS file-system description object
138 * @free: amount of free space
139 * @dirty: amount of dirty space to add
141 static void upd_ltab(struct ubifs_info
*c
, int lnum
, int free
, int dirty
)
143 dbg_lp("LEB %d free %d dirty %d to %d +%d",
144 lnum
, c
->ltab
[lnum
- c
->lpt_first
].free
,
145 c
->ltab
[lnum
- c
->lpt_first
].dirty
, free
, dirty
);
146 ubifs_assert(c
, lnum
>= c
->lpt_first
&& lnum
<= c
->lpt_last
);
147 c
->ltab
[lnum
- c
->lpt_first
].free
= free
;
148 c
->ltab
[lnum
- c
->lpt_first
].dirty
+= dirty
;
152 * alloc_lpt_leb - allocate an LPT LEB that is empty.
153 * @c: UBIFS file-system description object
154 * @lnum: LEB number is passed and returned here
156 * This function finds the next empty LEB in the ltab starting from @lnum. If a
157 * an empty LEB is found it is returned in @lnum and the function returns %0.
158 * Otherwise the function returns -ENOSPC. Note however, that LPT is designed
159 * never to run out of space.
161 static int alloc_lpt_leb(struct ubifs_info
*c
, int *lnum
)
165 n
= *lnum
- c
->lpt_first
+ 1;
166 for (i
= n
; i
< c
->lpt_lebs
; i
++) {
167 if (c
->ltab
[i
].tgc
|| c
->ltab
[i
].cmt
)
169 if (c
->ltab
[i
].free
== c
->leb_size
) {
171 *lnum
= i
+ c
->lpt_first
;
176 for (i
= 0; i
< n
; i
++) {
177 if (c
->ltab
[i
].tgc
|| c
->ltab
[i
].cmt
)
179 if (c
->ltab
[i
].free
== c
->leb_size
) {
181 *lnum
= i
+ c
->lpt_first
;
189 * layout_cnodes - layout cnodes for commit.
190 * @c: UBIFS file-system description object
192 * This function returns %0 on success and a negative error code on failure.
194 static int layout_cnodes(struct ubifs_info
*c
)
196 int lnum
, offs
, len
, alen
, done_lsave
, done_ltab
, err
;
197 struct ubifs_cnode
*cnode
;
199 err
= dbg_chk_lpt_sz(c
, 0, 0);
202 cnode
= c
->lpt_cnext
;
205 lnum
= c
->nhead_lnum
;
206 offs
= c
->nhead_offs
;
207 /* Try to place lsave and ltab nicely */
208 done_lsave
= !c
->big_lpt
;
210 if (!done_lsave
&& offs
+ c
->lsave_sz
<= c
->leb_size
) {
212 c
->lsave_lnum
= lnum
;
213 c
->lsave_offs
= offs
;
215 dbg_chk_lpt_sz(c
, 1, c
->lsave_sz
);
218 if (offs
+ c
->ltab_sz
<= c
->leb_size
) {
223 dbg_chk_lpt_sz(c
, 1, c
->ltab_sz
);
229 c
->dirty_nn_cnt
-= 1;
232 c
->dirty_pn_cnt
-= 1;
234 while (offs
+ len
> c
->leb_size
) {
235 alen
= ALIGN(offs
, c
->min_io_size
);
236 upd_ltab(c
, lnum
, c
->leb_size
- alen
, alen
- offs
);
237 dbg_chk_lpt_sz(c
, 2, c
->leb_size
- offs
);
238 err
= alloc_lpt_leb(c
, &lnum
);
242 ubifs_assert(c
, lnum
>= c
->lpt_first
&&
243 lnum
<= c
->lpt_last
);
244 /* Try to place lsave and ltab nicely */
247 c
->lsave_lnum
= lnum
;
248 c
->lsave_offs
= offs
;
250 dbg_chk_lpt_sz(c
, 1, c
->lsave_sz
);
258 dbg_chk_lpt_sz(c
, 1, c
->ltab_sz
);
264 cnode
->parent
->nbranch
[cnode
->iip
].lnum
= lnum
;
265 cnode
->parent
->nbranch
[cnode
->iip
].offs
= offs
;
271 dbg_chk_lpt_sz(c
, 1, len
);
272 cnode
= cnode
->cnext
;
273 } while (cnode
&& cnode
!= c
->lpt_cnext
);
275 /* Make sure to place LPT's save table */
277 if (offs
+ c
->lsave_sz
> c
->leb_size
) {
278 alen
= ALIGN(offs
, c
->min_io_size
);
279 upd_ltab(c
, lnum
, c
->leb_size
- alen
, alen
- offs
);
280 dbg_chk_lpt_sz(c
, 2, c
->leb_size
- offs
);
281 err
= alloc_lpt_leb(c
, &lnum
);
285 ubifs_assert(c
, lnum
>= c
->lpt_first
&&
286 lnum
<= c
->lpt_last
);
289 c
->lsave_lnum
= lnum
;
290 c
->lsave_offs
= offs
;
292 dbg_chk_lpt_sz(c
, 1, c
->lsave_sz
);
295 /* Make sure to place LPT's own lprops table */
297 if (offs
+ c
->ltab_sz
> c
->leb_size
) {
298 alen
= ALIGN(offs
, c
->min_io_size
);
299 upd_ltab(c
, lnum
, c
->leb_size
- alen
, alen
- offs
);
300 dbg_chk_lpt_sz(c
, 2, c
->leb_size
- offs
);
301 err
= alloc_lpt_leb(c
, &lnum
);
305 ubifs_assert(c
, lnum
>= c
->lpt_first
&&
306 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(c
, "LPT out of space at LEB %d:%d needing %d, done_ltab %d, done_lsave %d",
324 lnum
, offs
, len
, done_ltab
, done_lsave
);
325 ubifs_dump_lpt_info(c
);
326 ubifs_dump_lpt_lebs(c
);
332 * realloc_lpt_leb - allocate an LPT LEB that is empty.
333 * @c: UBIFS file-system description object
334 * @lnum: LEB number is passed and returned here
336 * This function duplicates exactly the results of the function alloc_lpt_leb.
337 * It is used during end commit to reallocate the same LEB numbers that were
338 * allocated by alloc_lpt_leb during start commit.
340 * This function finds the next LEB that was allocated by the alloc_lpt_leb
341 * function starting from @lnum. If a LEB is found it is returned in @lnum and
342 * the function returns %0. Otherwise the function returns -ENOSPC.
343 * Note however, that LPT is designed never to run out of space.
345 static int realloc_lpt_leb(struct ubifs_info
*c
, int *lnum
)
349 n
= *lnum
- c
->lpt_first
+ 1;
350 for (i
= n
; i
< c
->lpt_lebs
; i
++)
351 if (c
->ltab
[i
].cmt
) {
353 *lnum
= i
+ c
->lpt_first
;
357 for (i
= 0; i
< n
; i
++)
358 if (c
->ltab
[i
].cmt
) {
360 *lnum
= i
+ c
->lpt_first
;
367 * write_cnodes - write cnodes for commit.
368 * @c: UBIFS file-system description object
370 * This function returns %0 on success and a negative error code on failure.
372 static int write_cnodes(struct ubifs_info
*c
)
374 int lnum
, offs
, len
, from
, err
, wlen
, alen
, done_ltab
, done_lsave
;
375 struct ubifs_cnode
*cnode
;
376 void *buf
= c
->lpt_buf
;
378 cnode
= c
->lpt_cnext
;
381 lnum
= c
->nhead_lnum
;
382 offs
= c
->nhead_offs
;
384 /* Ensure empty LEB is unmapped */
386 err
= ubifs_leb_unmap(c
, lnum
);
390 /* Try to place lsave and ltab nicely */
391 done_lsave
= !c
->big_lpt
;
393 if (!done_lsave
&& offs
+ c
->lsave_sz
<= c
->leb_size
) {
395 ubifs_pack_lsave(c
, buf
+ offs
, c
->lsave
);
397 dbg_chk_lpt_sz(c
, 1, c
->lsave_sz
);
400 if (offs
+ c
->ltab_sz
<= c
->leb_size
) {
402 ubifs_pack_ltab(c
, buf
+ offs
, c
->ltab_cmt
);
404 dbg_chk_lpt_sz(c
, 1, c
->ltab_sz
);
407 /* Loop for each cnode */
413 while (offs
+ len
> c
->leb_size
) {
416 alen
= ALIGN(wlen
, c
->min_io_size
);
417 memset(buf
+ offs
, 0xff, alen
- wlen
);
418 err
= ubifs_leb_write(c
, lnum
, buf
+ from
, from
,
423 dbg_chk_lpt_sz(c
, 2, c
->leb_size
- offs
);
424 err
= realloc_lpt_leb(c
, &lnum
);
428 ubifs_assert(c
, lnum
>= c
->lpt_first
&&
429 lnum
<= c
->lpt_last
);
430 err
= ubifs_leb_unmap(c
, lnum
);
433 /* Try to place lsave and ltab nicely */
436 ubifs_pack_lsave(c
, buf
+ offs
, c
->lsave
);
438 dbg_chk_lpt_sz(c
, 1, c
->lsave_sz
);
443 ubifs_pack_ltab(c
, buf
+ offs
, c
->ltab_cmt
);
445 dbg_chk_lpt_sz(c
, 1, c
->ltab_sz
);
451 ubifs_pack_nnode(c
, buf
+ offs
,
452 (struct ubifs_nnode
*)cnode
);
454 ubifs_pack_pnode(c
, buf
+ offs
,
455 (struct ubifs_pnode
*)cnode
);
457 * The reason for the barriers is the same as in case of TNC.
458 * See comment in 'write_index()'. 'dirty_cow_nnode()' and
459 * 'dirty_cow_pnode()' are the functions for which this is
462 clear_bit(DIRTY_CNODE
, &cnode
->flags
);
463 smp_mb__before_atomic();
464 clear_bit(COW_CNODE
, &cnode
->flags
);
465 smp_mb__after_atomic();
467 dbg_chk_lpt_sz(c
, 1, len
);
468 cnode
= cnode
->cnext
;
469 } while (cnode
&& cnode
!= c
->lpt_cnext
);
471 /* Make sure to place LPT's save table */
473 if (offs
+ c
->lsave_sz
> c
->leb_size
) {
475 alen
= ALIGN(wlen
, c
->min_io_size
);
476 memset(buf
+ offs
, 0xff, alen
- wlen
);
477 err
= ubifs_leb_write(c
, lnum
, buf
+ from
, from
, alen
);
480 dbg_chk_lpt_sz(c
, 2, c
->leb_size
- offs
);
481 err
= realloc_lpt_leb(c
, &lnum
);
485 ubifs_assert(c
, lnum
>= c
->lpt_first
&&
486 lnum
<= c
->lpt_last
);
487 err
= ubifs_leb_unmap(c
, lnum
);
492 ubifs_pack_lsave(c
, buf
+ offs
, c
->lsave
);
494 dbg_chk_lpt_sz(c
, 1, c
->lsave_sz
);
497 /* Make sure to place LPT's own lprops table */
499 if (offs
+ c
->ltab_sz
> c
->leb_size
) {
501 alen
= ALIGN(wlen
, c
->min_io_size
);
502 memset(buf
+ offs
, 0xff, alen
- wlen
);
503 err
= ubifs_leb_write(c
, lnum
, buf
+ from
, from
, alen
);
506 dbg_chk_lpt_sz(c
, 2, c
->leb_size
- offs
);
507 err
= realloc_lpt_leb(c
, &lnum
);
511 ubifs_assert(c
, lnum
>= c
->lpt_first
&&
512 lnum
<= c
->lpt_last
);
513 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(c
, "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
);
556 * next_pnode_to_dirty - find next pnode to dirty.
557 * @c: UBIFS file-system description object
560 * This function returns the next pnode to dirty or %NULL if there are no more
561 * pnodes. Note that pnodes that have never been written (lnum == 0) are
564 static struct ubifs_pnode
*next_pnode_to_dirty(struct ubifs_info
*c
,
565 struct ubifs_pnode
*pnode
)
567 struct ubifs_nnode
*nnode
;
570 /* Try to go right */
571 nnode
= pnode
->parent
;
572 for (iip
= pnode
->iip
+ 1; iip
< UBIFS_LPT_FANOUT
; iip
++) {
573 if (nnode
->nbranch
[iip
].lnum
)
574 return ubifs_get_pnode(c
, nnode
, iip
);
577 /* Go up while can't go right */
579 iip
= nnode
->iip
+ 1;
580 nnode
= nnode
->parent
;
583 for (; iip
< UBIFS_LPT_FANOUT
; iip
++) {
584 if (nnode
->nbranch
[iip
].lnum
)
587 } while (iip
>= UBIFS_LPT_FANOUT
);
590 nnode
= ubifs_get_nnode(c
, nnode
, iip
);
592 return (void *)nnode
;
594 /* Go down to level 1 */
595 while (nnode
->level
> 1) {
596 for (iip
= 0; iip
< UBIFS_LPT_FANOUT
; iip
++) {
597 if (nnode
->nbranch
[iip
].lnum
)
600 if (iip
>= UBIFS_LPT_FANOUT
) {
602 * Should not happen, but we need to keep going
607 nnode
= ubifs_get_nnode(c
, nnode
, iip
);
609 return (void *)nnode
;
612 for (iip
= 0; iip
< UBIFS_LPT_FANOUT
; iip
++)
613 if (nnode
->nbranch
[iip
].lnum
)
615 if (iip
>= UBIFS_LPT_FANOUT
)
616 /* Should not happen, but we need to keep going if it does */
618 return ubifs_get_pnode(c
, nnode
, iip
);
622 * add_pnode_dirt - add dirty space to LPT LEB properties.
623 * @c: UBIFS file-system description object
624 * @pnode: pnode for which to add dirt
626 static void add_pnode_dirt(struct ubifs_info
*c
, struct ubifs_pnode
*pnode
)
628 ubifs_add_lpt_dirt(c
, pnode
->parent
->nbranch
[pnode
->iip
].lnum
,
633 * do_make_pnode_dirty - mark a pnode dirty.
634 * @c: UBIFS file-system description object
635 * @pnode: pnode to mark dirty
637 static void do_make_pnode_dirty(struct ubifs_info
*c
, struct ubifs_pnode
*pnode
)
639 /* Assumes cnext list is empty i.e. not called during commit */
640 if (!test_and_set_bit(DIRTY_CNODE
, &pnode
->flags
)) {
641 struct ubifs_nnode
*nnode
;
643 c
->dirty_pn_cnt
+= 1;
644 add_pnode_dirt(c
, pnode
);
645 /* Mark parent and ancestors dirty too */
646 nnode
= pnode
->parent
;
648 if (!test_and_set_bit(DIRTY_CNODE
, &nnode
->flags
)) {
649 c
->dirty_nn_cnt
+= 1;
650 ubifs_add_nnode_dirt(c
, nnode
);
651 nnode
= nnode
->parent
;
659 * make_tree_dirty - mark the entire LEB properties tree dirty.
660 * @c: UBIFS file-system description object
662 * This function is used by the "small" LPT model to cause the entire LEB
663 * properties tree to be written. The "small" LPT model does not use LPT
664 * garbage collection because it is more efficient to write the entire tree
665 * (because it is small).
667 * This function returns %0 on success and a negative error code on failure.
669 static int make_tree_dirty(struct ubifs_info
*c
)
671 struct ubifs_pnode
*pnode
;
673 pnode
= ubifs_pnode_lookup(c
, 0);
675 return PTR_ERR(pnode
);
678 do_make_pnode_dirty(c
, pnode
);
679 pnode
= next_pnode_to_dirty(c
, pnode
);
681 return PTR_ERR(pnode
);
687 * need_write_all - determine if the LPT area is running out of free space.
688 * @c: UBIFS file-system description object
690 * This function returns %1 if the LPT area is running out of free space and %0
693 static int need_write_all(struct ubifs_info
*c
)
698 for (i
= 0; i
< c
->lpt_lebs
; i
++) {
699 if (i
+ c
->lpt_first
== c
->nhead_lnum
)
700 free
+= c
->leb_size
- c
->nhead_offs
;
701 else if (c
->ltab
[i
].free
== c
->leb_size
)
703 else if (c
->ltab
[i
].free
+ c
->ltab
[i
].dirty
== c
->leb_size
)
706 /* Less than twice the size left */
707 if (free
<= c
->lpt_sz
* 2)
713 * lpt_tgc_start - start trivial garbage collection of LPT LEBs.
714 * @c: UBIFS file-system description object
716 * LPT trivial garbage collection is where a LPT LEB contains only dirty and
717 * free space and so may be reused as soon as the next commit is completed.
718 * This function is called during start commit to mark LPT LEBs for trivial GC.
720 static void lpt_tgc_start(struct ubifs_info
*c
)
724 for (i
= 0; i
< c
->lpt_lebs
; i
++) {
725 if (i
+ c
->lpt_first
== c
->nhead_lnum
)
727 if (c
->ltab
[i
].dirty
> 0 &&
728 c
->ltab
[i
].free
+ c
->ltab
[i
].dirty
== c
->leb_size
) {
730 c
->ltab
[i
].free
= c
->leb_size
;
731 c
->ltab
[i
].dirty
= 0;
732 dbg_lp("LEB %d", i
+ c
->lpt_first
);
738 * lpt_tgc_end - end trivial garbage collection of LPT LEBs.
739 * @c: UBIFS file-system description object
741 * LPT trivial garbage collection is where a LPT LEB contains only dirty and
742 * free space and so may be reused as soon as the next commit is completed.
743 * This function is called after the commit is completed (master node has been
744 * written) and un-maps LPT LEBs that were marked for trivial GC.
746 static int lpt_tgc_end(struct ubifs_info
*c
)
750 for (i
= 0; i
< c
->lpt_lebs
; i
++)
751 if (c
->ltab
[i
].tgc
) {
752 err
= ubifs_leb_unmap(c
, i
+ c
->lpt_first
);
756 dbg_lp("LEB %d", i
+ c
->lpt_first
);
762 * populate_lsave - fill the lsave array with important LEB numbers.
763 * @c: the UBIFS file-system description object
765 * This function is only called for the "big" model. It records a small number
766 * of LEB numbers of important LEBs. Important LEBs are ones that are (from
767 * most important to least important): empty, freeable, freeable index, dirty
768 * index, dirty or free. Upon mount, we read this list of LEB numbers and bring
769 * their pnodes into memory. That will stop us from having to scan the LPT
770 * straight away. For the "small" model we assume that scanning the LPT is no
773 static void populate_lsave(struct ubifs_info
*c
)
775 struct ubifs_lprops
*lprops
;
776 struct ubifs_lpt_heap
*heap
;
779 ubifs_assert(c
, c
->big_lpt
);
780 if (!(c
->lpt_drty_flgs
& LSAVE_DIRTY
)) {
781 c
->lpt_drty_flgs
|= LSAVE_DIRTY
;
782 ubifs_add_lpt_dirt(c
, c
->lsave_lnum
, c
->lsave_sz
);
785 if (dbg_populate_lsave(c
))
788 list_for_each_entry(lprops
, &c
->empty_list
, list
) {
789 c
->lsave
[cnt
++] = lprops
->lnum
;
790 if (cnt
>= c
->lsave_cnt
)
793 list_for_each_entry(lprops
, &c
->freeable_list
, list
) {
794 c
->lsave
[cnt
++] = lprops
->lnum
;
795 if (cnt
>= c
->lsave_cnt
)
798 list_for_each_entry(lprops
, &c
->frdi_idx_list
, list
) {
799 c
->lsave
[cnt
++] = lprops
->lnum
;
800 if (cnt
>= c
->lsave_cnt
)
803 heap
= &c
->lpt_heap
[LPROPS_DIRTY_IDX
- 1];
804 for (i
= 0; i
< heap
->cnt
; i
++) {
805 c
->lsave
[cnt
++] = heap
->arr
[i
]->lnum
;
806 if (cnt
>= c
->lsave_cnt
)
809 heap
= &c
->lpt_heap
[LPROPS_DIRTY
- 1];
810 for (i
= 0; i
< heap
->cnt
; i
++) {
811 c
->lsave
[cnt
++] = heap
->arr
[i
]->lnum
;
812 if (cnt
>= c
->lsave_cnt
)
815 heap
= &c
->lpt_heap
[LPROPS_FREE
- 1];
816 for (i
= 0; i
< heap
->cnt
; i
++) {
817 c
->lsave
[cnt
++] = heap
->arr
[i
]->lnum
;
818 if (cnt
>= c
->lsave_cnt
)
821 /* Fill it up completely */
822 while (cnt
< c
->lsave_cnt
)
823 c
->lsave
[cnt
++] = c
->main_first
;
827 * nnode_lookup - lookup a nnode in the LPT.
828 * @c: UBIFS file-system description object
831 * This function returns a pointer to the nnode on success or a negative
832 * error code on failure.
834 static struct ubifs_nnode
*nnode_lookup(struct ubifs_info
*c
, int i
)
837 struct ubifs_nnode
*nnode
;
840 err
= ubifs_read_nnode(c
, NULL
, 0);
846 iip
= i
& (UBIFS_LPT_FANOUT
- 1);
847 i
>>= UBIFS_LPT_FANOUT_SHIFT
;
850 nnode
= ubifs_get_nnode(c
, nnode
, iip
);
858 * make_nnode_dirty - find a nnode and, if found, make it dirty.
859 * @c: UBIFS file-system description object
860 * @node_num: nnode number of nnode to make dirty
861 * @lnum: LEB number where nnode was written
862 * @offs: offset where nnode was written
864 * This function is used by LPT garbage collection. LPT garbage collection is
865 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
866 * simply involves marking all the nodes in the LEB being garbage-collected as
867 * dirty. The dirty nodes are written next commit, after which the LEB is free
870 * This function returns %0 on success and a negative error code on failure.
872 static int make_nnode_dirty(struct ubifs_info
*c
, int node_num
, int lnum
,
875 struct ubifs_nnode
*nnode
;
877 nnode
= nnode_lookup(c
, node_num
);
879 return PTR_ERR(nnode
);
881 struct ubifs_nbranch
*branch
;
883 branch
= &nnode
->parent
->nbranch
[nnode
->iip
];
884 if (branch
->lnum
!= lnum
|| branch
->offs
!= offs
)
885 return 0; /* nnode is obsolete */
886 } else if (c
->lpt_lnum
!= lnum
|| c
->lpt_offs
!= offs
)
887 return 0; /* nnode is obsolete */
888 /* Assumes cnext list is empty i.e. not called during commit */
889 if (!test_and_set_bit(DIRTY_CNODE
, &nnode
->flags
)) {
890 c
->dirty_nn_cnt
+= 1;
891 ubifs_add_nnode_dirt(c
, nnode
);
892 /* Mark parent and ancestors dirty too */
893 nnode
= nnode
->parent
;
895 if (!test_and_set_bit(DIRTY_CNODE
, &nnode
->flags
)) {
896 c
->dirty_nn_cnt
+= 1;
897 ubifs_add_nnode_dirt(c
, nnode
);
898 nnode
= nnode
->parent
;
907 * make_pnode_dirty - find a pnode and, if found, make it dirty.
908 * @c: UBIFS file-system description object
909 * @node_num: pnode number of pnode to make dirty
910 * @lnum: LEB number where pnode was written
911 * @offs: offset where pnode was written
913 * This function is used by LPT garbage collection. LPT garbage collection is
914 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
915 * simply involves marking all the nodes in the LEB being garbage-collected as
916 * dirty. The dirty nodes are written next commit, after which the LEB is free
919 * This function returns %0 on success and a negative error code on failure.
921 static int make_pnode_dirty(struct ubifs_info
*c
, int node_num
, int lnum
,
924 struct ubifs_pnode
*pnode
;
925 struct ubifs_nbranch
*branch
;
927 pnode
= ubifs_pnode_lookup(c
, node_num
);
929 return PTR_ERR(pnode
);
930 branch
= &pnode
->parent
->nbranch
[pnode
->iip
];
931 if (branch
->lnum
!= lnum
|| branch
->offs
!= offs
)
933 do_make_pnode_dirty(c
, pnode
);
938 * make_ltab_dirty - make ltab node dirty.
939 * @c: UBIFS file-system description object
940 * @lnum: LEB number where ltab was written
941 * @offs: offset where ltab was written
943 * This function is used by LPT garbage collection. LPT garbage collection is
944 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
945 * simply involves marking all the nodes in the LEB being garbage-collected as
946 * dirty. The dirty nodes are written next commit, after which the LEB is free
949 * This function returns %0 on success and a negative error code on failure.
951 static int make_ltab_dirty(struct ubifs_info
*c
, int lnum
, int offs
)
953 if (lnum
!= c
->ltab_lnum
|| offs
!= c
->ltab_offs
)
954 return 0; /* This ltab node is obsolete */
955 if (!(c
->lpt_drty_flgs
& LTAB_DIRTY
)) {
956 c
->lpt_drty_flgs
|= LTAB_DIRTY
;
957 ubifs_add_lpt_dirt(c
, c
->ltab_lnum
, c
->ltab_sz
);
963 * make_lsave_dirty - make lsave node dirty.
964 * @c: UBIFS file-system description object
965 * @lnum: LEB number where lsave was written
966 * @offs: offset where lsave was written
968 * This function is used by LPT garbage collection. LPT garbage collection is
969 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
970 * simply involves marking all the nodes in the LEB being garbage-collected as
971 * dirty. The dirty nodes are written next commit, after which the LEB is free
974 * This function returns %0 on success and a negative error code on failure.
976 static int make_lsave_dirty(struct ubifs_info
*c
, int lnum
, int offs
)
978 if (lnum
!= c
->lsave_lnum
|| offs
!= c
->lsave_offs
)
979 return 0; /* This lsave node is obsolete */
980 if (!(c
->lpt_drty_flgs
& LSAVE_DIRTY
)) {
981 c
->lpt_drty_flgs
|= LSAVE_DIRTY
;
982 ubifs_add_lpt_dirt(c
, c
->lsave_lnum
, c
->lsave_sz
);
988 * make_node_dirty - make node dirty.
989 * @c: UBIFS file-system description object
990 * @node_type: LPT node type
991 * @node_num: node number
992 * @lnum: LEB number where node was written
993 * @offs: offset where node was written
995 * This function is used by LPT garbage collection. LPT garbage collection is
996 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection
997 * simply involves marking all the nodes in the LEB being garbage-collected as
998 * dirty. The dirty nodes are written next commit, after which the LEB is free
1001 * This function returns %0 on success and a negative error code on failure.
1003 static int make_node_dirty(struct ubifs_info
*c
, int node_type
, int node_num
,
1006 switch (node_type
) {
1007 case UBIFS_LPT_NNODE
:
1008 return make_nnode_dirty(c
, node_num
, lnum
, offs
);
1009 case UBIFS_LPT_PNODE
:
1010 return make_pnode_dirty(c
, node_num
, lnum
, offs
);
1011 case UBIFS_LPT_LTAB
:
1012 return make_ltab_dirty(c
, lnum
, offs
);
1013 case UBIFS_LPT_LSAVE
:
1014 return make_lsave_dirty(c
, lnum
, offs
);
1020 * get_lpt_node_len - return the length of a node based on its type.
1021 * @c: UBIFS file-system description object
1022 * @node_type: LPT node type
1024 static int get_lpt_node_len(const struct ubifs_info
*c
, int node_type
)
1026 switch (node_type
) {
1027 case UBIFS_LPT_NNODE
:
1029 case UBIFS_LPT_PNODE
:
1031 case UBIFS_LPT_LTAB
:
1033 case UBIFS_LPT_LSAVE
:
1040 * get_pad_len - return the length of padding in a buffer.
1041 * @c: UBIFS file-system description object
1043 * @len: length of buffer
1045 static int get_pad_len(const struct ubifs_info
*c
, uint8_t *buf
, int len
)
1049 if (c
->min_io_size
== 1)
1051 offs
= c
->leb_size
- len
;
1052 pad_len
= ALIGN(offs
, c
->min_io_size
) - offs
;
1057 * get_lpt_node_type - return type (and node number) of a node in a buffer.
1058 * @c: UBIFS file-system description object
1060 * @node_num: node number is returned here
1062 static int get_lpt_node_type(const struct ubifs_info
*c
, uint8_t *buf
,
1065 uint8_t *addr
= buf
+ UBIFS_LPT_CRC_BYTES
;
1066 int pos
= 0, node_type
;
1068 node_type
= ubifs_unpack_bits(c
, &addr
, &pos
, UBIFS_LPT_TYPE_BITS
);
1069 *node_num
= ubifs_unpack_bits(c
, &addr
, &pos
, c
->pcnt_bits
);
1074 * is_a_node - determine if a buffer contains a node.
1075 * @c: UBIFS file-system description object
1077 * @len: length of buffer
1079 * This function returns %1 if the buffer contains a node or %0 if it does not.
1081 static int is_a_node(const struct ubifs_info
*c
, uint8_t *buf
, int len
)
1083 uint8_t *addr
= buf
+ UBIFS_LPT_CRC_BYTES
;
1084 int pos
= 0, node_type
, node_len
;
1085 uint16_t crc
, calc_crc
;
1087 if (len
< UBIFS_LPT_CRC_BYTES
+ (UBIFS_LPT_TYPE_BITS
+ 7) / 8)
1089 node_type
= ubifs_unpack_bits(c
, &addr
, &pos
, UBIFS_LPT_TYPE_BITS
);
1090 if (node_type
== UBIFS_LPT_NOT_A_NODE
)
1092 node_len
= get_lpt_node_len(c
, node_type
);
1093 if (!node_len
|| node_len
> len
)
1097 crc
= ubifs_unpack_bits(c
, &addr
, &pos
, UBIFS_LPT_CRC_BITS
);
1098 calc_crc
= crc16(-1, buf
+ UBIFS_LPT_CRC_BYTES
,
1099 node_len
- UBIFS_LPT_CRC_BYTES
);
1100 if (crc
!= calc_crc
)
1106 * lpt_gc_lnum - garbage collect a LPT LEB.
1107 * @c: UBIFS file-system description object
1108 * @lnum: LEB number to garbage collect
1110 * LPT garbage collection is used only for the "big" LPT model
1111 * (c->big_lpt == 1). Garbage collection simply involves marking all the nodes
1112 * in the LEB being garbage-collected as dirty. The dirty nodes are written
1113 * next commit, after which the LEB is free to be reused.
1115 * This function returns %0 on success and a negative error code on failure.
1117 static int lpt_gc_lnum(struct ubifs_info
*c
, int lnum
)
1119 int err
, len
= c
->leb_size
, node_type
, node_num
, node_len
, offs
;
1120 void *buf
= c
->lpt_buf
;
1122 dbg_lp("LEB %d", lnum
);
1124 err
= ubifs_leb_read(c
, lnum
, buf
, 0, c
->leb_size
, 1);
1129 if (!is_a_node(c
, buf
, len
)) {
1132 pad_len
= get_pad_len(c
, buf
, len
);
1140 node_type
= get_lpt_node_type(c
, buf
, &node_num
);
1141 node_len
= get_lpt_node_len(c
, node_type
);
1142 offs
= c
->leb_size
- len
;
1143 ubifs_assert(c
, node_len
!= 0);
1144 mutex_lock(&c
->lp_mutex
);
1145 err
= make_node_dirty(c
, node_type
, node_num
, lnum
, offs
);
1146 mutex_unlock(&c
->lp_mutex
);
1156 * lpt_gc - LPT garbage collection.
1157 * @c: UBIFS file-system description object
1159 * Select a LPT LEB for LPT garbage collection and call 'lpt_gc_lnum()'.
1160 * Returns %0 on success and a negative error code on failure.
1162 static int lpt_gc(struct ubifs_info
*c
)
1164 int i
, lnum
= -1, dirty
= 0;
1166 mutex_lock(&c
->lp_mutex
);
1167 for (i
= 0; i
< c
->lpt_lebs
; i
++) {
1168 ubifs_assert(c
, !c
->ltab
[i
].tgc
);
1169 if (i
+ c
->lpt_first
== c
->nhead_lnum
||
1170 c
->ltab
[i
].free
+ c
->ltab
[i
].dirty
== c
->leb_size
)
1172 if (c
->ltab
[i
].dirty
> dirty
) {
1173 dirty
= c
->ltab
[i
].dirty
;
1174 lnum
= i
+ c
->lpt_first
;
1177 mutex_unlock(&c
->lp_mutex
);
1180 return lpt_gc_lnum(c
, lnum
);
1184 * ubifs_lpt_start_commit - UBIFS commit starts.
1185 * @c: the UBIFS file-system description object
1187 * This function has to be called when UBIFS starts the commit operation.
1188 * This function "freezes" all currently dirty LEB properties and does not
1189 * change them anymore. Further changes are saved and tracked separately
1190 * because they are not part of this commit. This function returns zero in case
1191 * of success and a negative error code in case of failure.
1193 int ubifs_lpt_start_commit(struct ubifs_info
*c
)
1199 mutex_lock(&c
->lp_mutex
);
1200 err
= dbg_chk_lpt_free_spc(c
);
1203 err
= dbg_check_ltab(c
);
1207 if (c
->check_lpt_free
) {
1209 * We ensure there is enough free space in
1210 * ubifs_lpt_post_commit() by marking nodes dirty. That
1211 * information is lost when we unmount, so we also need
1212 * to check free space once after mounting also.
1214 c
->check_lpt_free
= 0;
1215 while (need_write_all(c
)) {
1216 mutex_unlock(&c
->lp_mutex
);
1220 mutex_lock(&c
->lp_mutex
);
1226 if (!c
->dirty_pn_cnt
) {
1227 dbg_cmt("no cnodes to commit");
1232 if (!c
->big_lpt
&& need_write_all(c
)) {
1233 /* If needed, write everything */
1234 err
= make_tree_dirty(c
);
1243 cnt
= get_cnodes_to_commit(c
);
1244 ubifs_assert(c
, cnt
!= 0);
1246 err
= layout_cnodes(c
);
1250 err
= ubifs_lpt_calc_hash(c
, c
->mst_node
->hash_lpt
);
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
);
1464 * Everything below is related to debugging.
1468 * dbg_is_all_ff - determine if a buffer contains only 0xFF bytes.
1470 * @len: buffer length
1472 static int dbg_is_all_ff(uint8_t *buf
, int len
)
1476 for (i
= 0; i
< len
; i
++)
1483 * dbg_is_nnode_dirty - determine if a nnode is dirty.
1484 * @c: the UBIFS file-system description object
1485 * @lnum: LEB number where nnode was written
1486 * @offs: offset where nnode was written
1488 static int dbg_is_nnode_dirty(struct ubifs_info
*c
, int lnum
, int offs
)
1490 struct ubifs_nnode
*nnode
;
1493 /* Entire tree is in memory so first_nnode / next_nnode are OK */
1494 nnode
= first_nnode(c
, &hght
);
1495 for (; nnode
; nnode
= next_nnode(c
, nnode
, &hght
)) {
1496 struct ubifs_nbranch
*branch
;
1499 if (nnode
->parent
) {
1500 branch
= &nnode
->parent
->nbranch
[nnode
->iip
];
1501 if (branch
->lnum
!= lnum
|| branch
->offs
!= offs
)
1503 if (test_bit(DIRTY_CNODE
, &nnode
->flags
))
1507 if (c
->lpt_lnum
!= lnum
|| c
->lpt_offs
!= offs
)
1509 if (test_bit(DIRTY_CNODE
, &nnode
->flags
))
1518 * dbg_is_pnode_dirty - determine if a pnode is dirty.
1519 * @c: the UBIFS file-system description object
1520 * @lnum: LEB number where pnode was written
1521 * @offs: offset where pnode was written
1523 static int dbg_is_pnode_dirty(struct ubifs_info
*c
, int lnum
, int offs
)
1527 cnt
= DIV_ROUND_UP(c
->main_lebs
, UBIFS_LPT_FANOUT
);
1528 for (i
= 0; i
< cnt
; i
++) {
1529 struct ubifs_pnode
*pnode
;
1530 struct ubifs_nbranch
*branch
;
1533 pnode
= ubifs_pnode_lookup(c
, i
);
1535 return PTR_ERR(pnode
);
1536 branch
= &pnode
->parent
->nbranch
[pnode
->iip
];
1537 if (branch
->lnum
!= lnum
|| branch
->offs
!= offs
)
1539 if (test_bit(DIRTY_CNODE
, &pnode
->flags
))
1547 * dbg_is_ltab_dirty - determine if a ltab node is dirty.
1548 * @c: the UBIFS file-system description object
1549 * @lnum: LEB number where ltab node was written
1550 * @offs: offset where ltab node was written
1552 static int dbg_is_ltab_dirty(struct ubifs_info
*c
, int lnum
, int offs
)
1554 if (lnum
!= c
->ltab_lnum
|| offs
!= c
->ltab_offs
)
1556 return (c
->lpt_drty_flgs
& LTAB_DIRTY
) != 0;
1560 * dbg_is_lsave_dirty - determine if a lsave node is dirty.
1561 * @c: the UBIFS file-system description object
1562 * @lnum: LEB number where lsave node was written
1563 * @offs: offset where lsave node was written
1565 static int dbg_is_lsave_dirty(struct ubifs_info
*c
, int lnum
, int offs
)
1567 if (lnum
!= c
->lsave_lnum
|| offs
!= c
->lsave_offs
)
1569 return (c
->lpt_drty_flgs
& LSAVE_DIRTY
) != 0;
1573 * dbg_is_node_dirty - determine if a node is dirty.
1574 * @c: the UBIFS file-system description object
1575 * @node_type: node type
1576 * @lnum: LEB number where node was written
1577 * @offs: offset where node was written
1579 static int dbg_is_node_dirty(struct ubifs_info
*c
, int node_type
, int lnum
,
1582 switch (node_type
) {
1583 case UBIFS_LPT_NNODE
:
1584 return dbg_is_nnode_dirty(c
, lnum
, offs
);
1585 case UBIFS_LPT_PNODE
:
1586 return dbg_is_pnode_dirty(c
, lnum
, offs
);
1587 case UBIFS_LPT_LTAB
:
1588 return dbg_is_ltab_dirty(c
, lnum
, offs
);
1589 case UBIFS_LPT_LSAVE
:
1590 return dbg_is_lsave_dirty(c
, lnum
, offs
);
1596 * dbg_check_ltab_lnum - check the ltab for a LPT LEB number.
1597 * @c: the UBIFS file-system description object
1598 * @lnum: LEB number where node was written
1600 * This function returns %0 on success and a negative error code on failure.
1602 static int dbg_check_ltab_lnum(struct ubifs_info
*c
, int lnum
)
1604 int err
, len
= c
->leb_size
, dirty
= 0, node_type
, node_num
, node_len
;
1608 if (!dbg_is_chk_lprops(c
))
1611 buf
= p
= __vmalloc(c
->leb_size
, GFP_NOFS
, PAGE_KERNEL
);
1613 ubifs_err(c
, "cannot allocate memory for ltab checking");
1617 dbg_lp("LEB %d", lnum
);
1619 err
= ubifs_leb_read(c
, lnum
, buf
, 0, c
->leb_size
, 1);
1624 if (!is_a_node(c
, p
, len
)) {
1627 pad_len
= get_pad_len(c
, p
, len
);
1634 if (!dbg_is_all_ff(p
, len
)) {
1635 ubifs_err(c
, "invalid empty space in LEB %d at %d",
1636 lnum
, c
->leb_size
- len
);
1639 i
= lnum
- c
->lpt_first
;
1640 if (len
!= c
->ltab
[i
].free
) {
1641 ubifs_err(c
, "invalid free space in LEB %d (free %d, expected %d)",
1642 lnum
, len
, c
->ltab
[i
].free
);
1645 if (dirty
!= c
->ltab
[i
].dirty
) {
1646 ubifs_err(c
, "invalid dirty space in LEB %d (dirty %d, expected %d)",
1647 lnum
, dirty
, c
->ltab
[i
].dirty
);
1652 node_type
= get_lpt_node_type(c
, p
, &node_num
);
1653 node_len
= get_lpt_node_len(c
, node_type
);
1654 ret
= dbg_is_node_dirty(c
, node_type
, lnum
, c
->leb_size
- len
);
1668 * dbg_check_ltab - check the free and dirty space in the ltab.
1669 * @c: the UBIFS file-system description object
1671 * This function returns %0 on success and a negative error code on failure.
1673 int dbg_check_ltab(struct ubifs_info
*c
)
1675 int lnum
, err
, i
, cnt
;
1677 if (!dbg_is_chk_lprops(c
))
1680 /* Bring the entire tree into memory */
1681 cnt
= DIV_ROUND_UP(c
->main_lebs
, UBIFS_LPT_FANOUT
);
1682 for (i
= 0; i
< cnt
; i
++) {
1683 struct ubifs_pnode
*pnode
;
1685 pnode
= ubifs_pnode_lookup(c
, i
);
1687 return PTR_ERR(pnode
);
1692 err
= dbg_check_lpt_nodes(c
, (struct ubifs_cnode
*)c
->nroot
, 0, 0);
1696 /* Check each LEB */
1697 for (lnum
= c
->lpt_first
; lnum
<= c
->lpt_last
; lnum
++) {
1698 err
= dbg_check_ltab_lnum(c
, lnum
);
1700 ubifs_err(c
, "failed at LEB %d", lnum
);
1705 dbg_lp("succeeded");
1710 * dbg_chk_lpt_free_spc - check LPT free space is enough to write entire LPT.
1711 * @c: the UBIFS file-system description object
1713 * This function returns %0 on success and a negative error code on failure.
1715 int dbg_chk_lpt_free_spc(struct ubifs_info
*c
)
1720 if (!dbg_is_chk_lprops(c
))
1723 for (i
= 0; i
< c
->lpt_lebs
; i
++) {
1724 if (c
->ltab
[i
].tgc
|| c
->ltab
[i
].cmt
)
1726 if (i
+ c
->lpt_first
== c
->nhead_lnum
)
1727 free
+= c
->leb_size
- c
->nhead_offs
;
1728 else if (c
->ltab
[i
].free
== c
->leb_size
)
1729 free
+= c
->leb_size
;
1731 if (free
< c
->lpt_sz
) {
1732 ubifs_err(c
, "LPT space error: free %lld lpt_sz %lld",
1734 ubifs_dump_lpt_info(c
);
1735 ubifs_dump_lpt_lebs(c
);
1743 * dbg_chk_lpt_sz - check LPT does not write more than LPT size.
1744 * @c: the UBIFS file-system description object
1745 * @action: what to do
1746 * @len: length written
1748 * This function returns %0 on success and a negative error code on failure.
1749 * The @action argument may be one of:
1750 * o %0 - LPT debugging checking starts, initialize debugging variables;
1751 * o %1 - wrote an LPT node, increase LPT size by @len bytes;
1752 * o %2 - switched to a different LEB and wasted @len bytes;
1753 * o %3 - check that we've written the right number of bytes.
1754 * o %4 - wasted @len bytes;
1756 int dbg_chk_lpt_sz(struct ubifs_info
*c
, int action
, int len
)
1758 struct ubifs_debug_info
*d
= c
->dbg
;
1759 long long chk_lpt_sz
, lpt_sz
;
1762 if (!dbg_is_chk_lprops(c
))
1769 d
->chk_lpt_lebs
= 0;
1770 d
->chk_lpt_wastage
= 0;
1771 if (c
->dirty_pn_cnt
> c
->pnode_cnt
) {
1772 ubifs_err(c
, "dirty pnodes %d exceed max %d",
1773 c
->dirty_pn_cnt
, c
->pnode_cnt
);
1776 if (c
->dirty_nn_cnt
> c
->nnode_cnt
) {
1777 ubifs_err(c
, "dirty nnodes %d exceed max %d",
1778 c
->dirty_nn_cnt
, c
->nnode_cnt
);
1783 d
->chk_lpt_sz
+= len
;
1786 d
->chk_lpt_sz
+= len
;
1787 d
->chk_lpt_wastage
+= len
;
1788 d
->chk_lpt_lebs
+= 1;
1791 chk_lpt_sz
= c
->leb_size
;
1792 chk_lpt_sz
*= d
->chk_lpt_lebs
;
1793 chk_lpt_sz
+= len
- c
->nhead_offs
;
1794 if (d
->chk_lpt_sz
!= chk_lpt_sz
) {
1795 ubifs_err(c
, "LPT wrote %lld but space used was %lld",
1796 d
->chk_lpt_sz
, chk_lpt_sz
);
1799 if (d
->chk_lpt_sz
> c
->lpt_sz
) {
1800 ubifs_err(c
, "LPT wrote %lld but lpt_sz is %lld",
1801 d
->chk_lpt_sz
, c
->lpt_sz
);
1804 if (d
->chk_lpt_sz2
&& d
->chk_lpt_sz
!= d
->chk_lpt_sz2
) {
1805 ubifs_err(c
, "LPT layout size %lld but wrote %lld",
1806 d
->chk_lpt_sz
, d
->chk_lpt_sz2
);
1809 if (d
->chk_lpt_sz2
&& d
->new_nhead_offs
!= len
) {
1810 ubifs_err(c
, "LPT new nhead offs: expected %d was %d",
1811 d
->new_nhead_offs
, len
);
1814 lpt_sz
= (long long)c
->pnode_cnt
* c
->pnode_sz
;
1815 lpt_sz
+= (long long)c
->nnode_cnt
* c
->nnode_sz
;
1816 lpt_sz
+= c
->ltab_sz
;
1818 lpt_sz
+= c
->lsave_sz
;
1819 if (d
->chk_lpt_sz
- d
->chk_lpt_wastage
> lpt_sz
) {
1820 ubifs_err(c
, "LPT chk_lpt_sz %lld + waste %lld exceeds %lld",
1821 d
->chk_lpt_sz
, d
->chk_lpt_wastage
, lpt_sz
);
1825 ubifs_dump_lpt_info(c
);
1826 ubifs_dump_lpt_lebs(c
);
1829 d
->chk_lpt_sz2
= d
->chk_lpt_sz
;
1831 d
->chk_lpt_wastage
= 0;
1832 d
->chk_lpt_lebs
= 0;
1833 d
->new_nhead_offs
= len
;
1836 d
->chk_lpt_sz
+= len
;
1837 d
->chk_lpt_wastage
+= len
;
1845 * dump_lpt_leb - dump an LPT LEB.
1846 * @c: UBIFS file-system description object
1847 * @lnum: LEB number to dump
1849 * This function dumps an LEB from LPT area. Nodes in this area are very
1850 * different to nodes in the main area (e.g., they do not have common headers,
1851 * they do not have 8-byte alignments, etc), so we have a separate function to
1852 * dump LPT area LEBs. Note, LPT has to be locked by the caller.
1854 static void dump_lpt_leb(const struct ubifs_info
*c
, int lnum
)
1856 int err
, len
= c
->leb_size
, node_type
, node_num
, node_len
, offs
;
1859 pr_err("(pid %d) start dumping LEB %d\n", current
->pid
, lnum
);
1860 buf
= p
= __vmalloc(c
->leb_size
, GFP_NOFS
, PAGE_KERNEL
);
1862 ubifs_err(c
, "cannot allocate memory to dump LPT");
1866 err
= ubifs_leb_read(c
, lnum
, buf
, 0, c
->leb_size
, 1);
1871 offs
= c
->leb_size
- len
;
1872 if (!is_a_node(c
, p
, len
)) {
1875 pad_len
= get_pad_len(c
, p
, len
);
1877 pr_err("LEB %d:%d, pad %d bytes\n",
1878 lnum
, offs
, pad_len
);
1884 pr_err("LEB %d:%d, free %d bytes\n",
1889 node_type
= get_lpt_node_type(c
, p
, &node_num
);
1890 switch (node_type
) {
1891 case UBIFS_LPT_PNODE
:
1893 node_len
= c
->pnode_sz
;
1895 pr_err("LEB %d:%d, pnode num %d\n",
1896 lnum
, offs
, node_num
);
1898 pr_err("LEB %d:%d, pnode\n", lnum
, offs
);
1901 case UBIFS_LPT_NNODE
:
1904 struct ubifs_nnode nnode
;
1906 node_len
= c
->nnode_sz
;
1908 pr_err("LEB %d:%d, nnode num %d, ",
1909 lnum
, offs
, node_num
);
1911 pr_err("LEB %d:%d, nnode, ",
1913 err
= ubifs_unpack_nnode(c
, p
, &nnode
);
1915 pr_err("failed to unpack_node, error %d\n",
1919 for (i
= 0; i
< UBIFS_LPT_FANOUT
; i
++) {
1920 pr_cont("%d:%d", nnode
.nbranch
[i
].lnum
,
1921 nnode
.nbranch
[i
].offs
);
1922 if (i
!= UBIFS_LPT_FANOUT
- 1)
1928 case UBIFS_LPT_LTAB
:
1929 node_len
= c
->ltab_sz
;
1930 pr_err("LEB %d:%d, ltab\n", lnum
, offs
);
1932 case UBIFS_LPT_LSAVE
:
1933 node_len
= c
->lsave_sz
;
1934 pr_err("LEB %d:%d, lsave len\n", lnum
, offs
);
1937 ubifs_err(c
, "LPT node type %d not recognized", node_type
);
1945 pr_err("(pid %d) finish dumping LEB %d\n", current
->pid
, lnum
);
1952 * ubifs_dump_lpt_lebs - dump LPT lebs.
1953 * @c: UBIFS file-system description object
1955 * This function dumps all LPT LEBs. The caller has to make sure the LPT is
1958 void ubifs_dump_lpt_lebs(const struct ubifs_info
*c
)
1962 pr_err("(pid %d) start dumping all LPT LEBs\n", current
->pid
);
1963 for (i
= 0; i
< c
->lpt_lebs
; i
++)
1964 dump_lpt_leb(c
, i
+ c
->lpt_first
);
1965 pr_err("(pid %d) finish dumping all LPT LEBs\n", current
->pid
);
1969 * dbg_populate_lsave - debugging version of 'populate_lsave()'
1970 * @c: UBIFS file-system description object
1972 * This is a debugging version for 'populate_lsave()' which populates lsave
1973 * with random LEBs instead of useful LEBs, which is good for test coverage.
1974 * Returns zero if lsave has not been populated (this debugging feature is
1975 * disabled) an non-zero if lsave has been populated.
1977 static int dbg_populate_lsave(struct ubifs_info
*c
)
1979 struct ubifs_lprops
*lprops
;
1980 struct ubifs_lpt_heap
*heap
;
1983 if (!dbg_is_chk_gen(c
))
1985 if (prandom_u32() & 3)
1988 for (i
= 0; i
< c
->lsave_cnt
; i
++)
1989 c
->lsave
[i
] = c
->main_first
;
1991 list_for_each_entry(lprops
, &c
->empty_list
, list
)
1992 c
->lsave
[prandom_u32() % c
->lsave_cnt
] = lprops
->lnum
;
1993 list_for_each_entry(lprops
, &c
->freeable_list
, list
)
1994 c
->lsave
[prandom_u32() % c
->lsave_cnt
] = lprops
->lnum
;
1995 list_for_each_entry(lprops
, &c
->frdi_idx_list
, list
)
1996 c
->lsave
[prandom_u32() % c
->lsave_cnt
] = lprops
->lnum
;
1998 heap
= &c
->lpt_heap
[LPROPS_DIRTY_IDX
- 1];
1999 for (i
= 0; i
< heap
->cnt
; i
++)
2000 c
->lsave
[prandom_u32() % c
->lsave_cnt
] = heap
->arr
[i
]->lnum
;
2001 heap
= &c
->lpt_heap
[LPROPS_DIRTY
- 1];
2002 for (i
= 0; i
< heap
->cnt
; i
++)
2003 c
->lsave
[prandom_u32() % c
->lsave_cnt
] = heap
->arr
[i
]->lnum
;
2004 heap
= &c
->lpt_heap
[LPROPS_FREE
- 1];
2005 for (i
= 0; i
< heap
->cnt
; i
++)
2006 c
->lsave
[prandom_u32() % c
->lsave_cnt
] = heap
->arr
[i
]->lnum
;