1997 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2/*3 * This file is part of UBIFS.4 *5 * Copyright (C) 2006-2008 Nokia Corporation.6 *7 * Authors: Adrian Hunter8 * Artem Bityutskiy (Битюцкий Артём)9 */10 11/*12 * This file implements commit-related functionality of the LEB properties13 * subsystem.14 */15 16#include <linux/crc16.h>17#include <linux/slab.h>18#include <linux/random.h>19#include "ubifs.h"20 21static int dbg_populate_lsave(struct ubifs_info *c);22 23/**24 * first_dirty_cnode - find first dirty cnode.25 * @c: UBIFS file-system description object26 * @nnode: nnode at which to start27 *28 * This function returns the first dirty cnode or %NULL if there is not one.29 */30static struct ubifs_cnode *first_dirty_cnode(const struct ubifs_info *c, struct ubifs_nnode *nnode)31{32 ubifs_assert(c, nnode);33 while (1) {34 int i, cont = 0;35 36 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {37 struct ubifs_cnode *cnode;38 39 cnode = nnode->nbranch[i].cnode;40 if (cnode &&41 test_bit(DIRTY_CNODE, &cnode->flags)) {42 if (cnode->level == 0)43 return cnode;44 nnode = (struct ubifs_nnode *)cnode;45 cont = 1;46 break;47 }48 }49 if (!cont)50 return (struct ubifs_cnode *)nnode;51 }52}53 54/**55 * next_dirty_cnode - find next dirty cnode.56 * @c: UBIFS file-system description object57 * @cnode: cnode from which to begin searching58 *59 * This function returns the next dirty cnode or %NULL if there is not one.60 */61static struct ubifs_cnode *next_dirty_cnode(const struct ubifs_info *c, struct ubifs_cnode *cnode)62{63 struct ubifs_nnode *nnode;64 int i;65 66 ubifs_assert(c, cnode);67 nnode = cnode->parent;68 if (!nnode)69 return NULL;70 for (i = cnode->iip + 1; i < UBIFS_LPT_FANOUT; i++) {71 cnode = nnode->nbranch[i].cnode;72 if (cnode && test_bit(DIRTY_CNODE, &cnode->flags)) {73 if (cnode->level == 0)74 return cnode; /* cnode is a pnode */75 /* cnode is a nnode */76 return first_dirty_cnode(c, (struct ubifs_nnode *)cnode);77 }78 }79 return (struct ubifs_cnode *)nnode;80}81 82/**83 * get_cnodes_to_commit - create list of dirty cnodes to commit.84 * @c: UBIFS file-system description object85 *86 * This function returns the number of cnodes to commit.87 */88static int get_cnodes_to_commit(struct ubifs_info *c)89{90 struct ubifs_cnode *cnode, *cnext;91 int cnt = 0;92 93 if (!c->nroot)94 return 0;95 96 if (!test_bit(DIRTY_CNODE, &c->nroot->flags))97 return 0;98 99 c->lpt_cnext = first_dirty_cnode(c, c->nroot);100 cnode = c->lpt_cnext;101 if (!cnode)102 return 0;103 cnt += 1;104 while (1) {105 ubifs_assert(c, !test_bit(COW_CNODE, &cnode->flags));106 __set_bit(COW_CNODE, &cnode->flags);107 cnext = next_dirty_cnode(c, cnode);108 if (!cnext) {109 cnode->cnext = c->lpt_cnext;110 break;111 }112 cnode->cnext = cnext;113 cnode = cnext;114 cnt += 1;115 }116 dbg_cmt("committing %d cnodes", cnt);117 dbg_lp("committing %d cnodes", cnt);118 ubifs_assert(c, cnt == c->dirty_nn_cnt + c->dirty_pn_cnt);119 return cnt;120}121 122/**123 * upd_ltab - update LPT LEB properties.124 * @c: UBIFS file-system description object125 * @lnum: LEB number126 * @free: amount of free space127 * @dirty: amount of dirty space to add128 */129static void upd_ltab(struct ubifs_info *c, int lnum, int free, int dirty)130{131 dbg_lp("LEB %d free %d dirty %d to %d +%d",132 lnum, c->ltab[lnum - c->lpt_first].free,133 c->ltab[lnum - c->lpt_first].dirty, free, dirty);134 ubifs_assert(c, lnum >= c->lpt_first && lnum <= c->lpt_last);135 c->ltab[lnum - c->lpt_first].free = free;136 c->ltab[lnum - c->lpt_first].dirty += dirty;137}138 139/**140 * alloc_lpt_leb - allocate an LPT LEB that is empty.141 * @c: UBIFS file-system description object142 * @lnum: LEB number is passed and returned here143 *144 * This function finds the next empty LEB in the ltab starting from @lnum. If a145 * an empty LEB is found it is returned in @lnum and the function returns %0.146 * Otherwise the function returns -ENOSPC. Note however, that LPT is designed147 * never to run out of space.148 */149static int alloc_lpt_leb(struct ubifs_info *c, int *lnum)150{151 int i, n;152 153 n = *lnum - c->lpt_first + 1;154 for (i = n; i < c->lpt_lebs; i++) {155 if (c->ltab[i].tgc || c->ltab[i].cmt)156 continue;157 if (c->ltab[i].free == c->leb_size) {158 c->ltab[i].cmt = 1;159 *lnum = i + c->lpt_first;160 return 0;161 }162 }163 164 for (i = 0; i < n; i++) {165 if (c->ltab[i].tgc || c->ltab[i].cmt)166 continue;167 if (c->ltab[i].free == c->leb_size) {168 c->ltab[i].cmt = 1;169 *lnum = i + c->lpt_first;170 return 0;171 }172 }173 return -ENOSPC;174}175 176/**177 * layout_cnodes - layout cnodes for commit.178 * @c: UBIFS file-system description object179 *180 * This function returns %0 on success and a negative error code on failure.181 */182static int layout_cnodes(struct ubifs_info *c)183{184 int lnum, offs, len, alen, done_lsave, done_ltab, err;185 struct ubifs_cnode *cnode;186 187 err = dbg_chk_lpt_sz(c, 0, 0);188 if (err)189 return err;190 cnode = c->lpt_cnext;191 if (!cnode)192 return 0;193 lnum = c->nhead_lnum;194 offs = c->nhead_offs;195 /* Try to place lsave and ltab nicely */196 done_lsave = !c->big_lpt;197 done_ltab = 0;198 if (!done_lsave && offs + c->lsave_sz <= c->leb_size) {199 done_lsave = 1;200 c->lsave_lnum = lnum;201 c->lsave_offs = offs;202 offs += c->lsave_sz;203 dbg_chk_lpt_sz(c, 1, c->lsave_sz);204 }205 206 if (offs + c->ltab_sz <= c->leb_size) {207 done_ltab = 1;208 c->ltab_lnum = lnum;209 c->ltab_offs = offs;210 offs += c->ltab_sz;211 dbg_chk_lpt_sz(c, 1, c->ltab_sz);212 }213 214 do {215 if (cnode->level) {216 len = c->nnode_sz;217 c->dirty_nn_cnt -= 1;218 } else {219 len = c->pnode_sz;220 c->dirty_pn_cnt -= 1;221 }222 while (offs + len > c->leb_size) {223 alen = ALIGN(offs, c->min_io_size);224 upd_ltab(c, lnum, c->leb_size - alen, alen - offs);225 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);226 err = alloc_lpt_leb(c, &lnum);227 if (err)228 goto no_space;229 offs = 0;230 ubifs_assert(c, lnum >= c->lpt_first &&231 lnum <= c->lpt_last);232 /* Try to place lsave and ltab nicely */233 if (!done_lsave) {234 done_lsave = 1;235 c->lsave_lnum = lnum;236 c->lsave_offs = offs;237 offs += c->lsave_sz;238 dbg_chk_lpt_sz(c, 1, c->lsave_sz);239 continue;240 }241 if (!done_ltab) {242 done_ltab = 1;243 c->ltab_lnum = lnum;244 c->ltab_offs = offs;245 offs += c->ltab_sz;246 dbg_chk_lpt_sz(c, 1, c->ltab_sz);247 continue;248 }249 break;250 }251 if (cnode->parent) {252 cnode->parent->nbranch[cnode->iip].lnum = lnum;253 cnode->parent->nbranch[cnode->iip].offs = offs;254 } else {255 c->lpt_lnum = lnum;256 c->lpt_offs = offs;257 }258 offs += len;259 dbg_chk_lpt_sz(c, 1, len);260 cnode = cnode->cnext;261 } while (cnode && cnode != c->lpt_cnext);262 263 /* Make sure to place LPT's save table */264 if (!done_lsave) {265 if (offs + c->lsave_sz > c->leb_size) {266 alen = ALIGN(offs, c->min_io_size);267 upd_ltab(c, lnum, c->leb_size - alen, alen - offs);268 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);269 err = alloc_lpt_leb(c, &lnum);270 if (err)271 goto no_space;272 offs = 0;273 ubifs_assert(c, lnum >= c->lpt_first &&274 lnum <= c->lpt_last);275 }276 done_lsave = 1;277 c->lsave_lnum = lnum;278 c->lsave_offs = offs;279 offs += c->lsave_sz;280 dbg_chk_lpt_sz(c, 1, c->lsave_sz);281 }282 283 /* Make sure to place LPT's own lprops table */284 if (!done_ltab) {285 if (offs + c->ltab_sz > c->leb_size) {286 alen = ALIGN(offs, c->min_io_size);287 upd_ltab(c, lnum, c->leb_size - alen, alen - offs);288 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);289 err = alloc_lpt_leb(c, &lnum);290 if (err)291 goto no_space;292 offs = 0;293 ubifs_assert(c, lnum >= c->lpt_first &&294 lnum <= c->lpt_last);295 }296 c->ltab_lnum = lnum;297 c->ltab_offs = offs;298 offs += c->ltab_sz;299 dbg_chk_lpt_sz(c, 1, c->ltab_sz);300 }301 302 alen = ALIGN(offs, c->min_io_size);303 upd_ltab(c, lnum, c->leb_size - alen, alen - offs);304 dbg_chk_lpt_sz(c, 4, alen - offs);305 err = dbg_chk_lpt_sz(c, 3, alen);306 if (err)307 return err;308 return 0;309 310no_space:311 ubifs_err(c, "LPT out of space at LEB %d:%d needing %d, done_ltab %d, done_lsave %d",312 lnum, offs, len, done_ltab, done_lsave);313 ubifs_dump_lpt_info(c);314 ubifs_dump_lpt_lebs(c);315 dump_stack();316 return err;317}318 319/**320 * realloc_lpt_leb - allocate an LPT LEB that is empty.321 * @c: UBIFS file-system description object322 * @lnum: LEB number is passed and returned here323 *324 * This function duplicates exactly the results of the function alloc_lpt_leb.325 * It is used during end commit to reallocate the same LEB numbers that were326 * allocated by alloc_lpt_leb during start commit.327 *328 * This function finds the next LEB that was allocated by the alloc_lpt_leb329 * function starting from @lnum. If a LEB is found it is returned in @lnum and330 * the function returns %0. Otherwise the function returns -ENOSPC.331 * Note however, that LPT is designed never to run out of space.332 */333static int realloc_lpt_leb(struct ubifs_info *c, int *lnum)334{335 int i, n;336 337 n = *lnum - c->lpt_first + 1;338 for (i = n; i < c->lpt_lebs; i++)339 if (c->ltab[i].cmt) {340 c->ltab[i].cmt = 0;341 *lnum = i + c->lpt_first;342 return 0;343 }344 345 for (i = 0; i < n; i++)346 if (c->ltab[i].cmt) {347 c->ltab[i].cmt = 0;348 *lnum = i + c->lpt_first;349 return 0;350 }351 return -ENOSPC;352}353 354/**355 * write_cnodes - write cnodes for commit.356 * @c: UBIFS file-system description object357 *358 * This function returns %0 on success and a negative error code on failure.359 */360static int write_cnodes(struct ubifs_info *c)361{362 int lnum, offs, len, from, err, wlen, alen, done_ltab, done_lsave;363 struct ubifs_cnode *cnode;364 void *buf = c->lpt_buf;365 366 cnode = c->lpt_cnext;367 if (!cnode)368 return 0;369 lnum = c->nhead_lnum;370 offs = c->nhead_offs;371 from = offs;372 /* Ensure empty LEB is unmapped */373 if (offs == 0) {374 err = ubifs_leb_unmap(c, lnum);375 if (err)376 return err;377 }378 /* Try to place lsave and ltab nicely */379 done_lsave = !c->big_lpt;380 done_ltab = 0;381 if (!done_lsave && offs + c->lsave_sz <= c->leb_size) {382 done_lsave = 1;383 ubifs_pack_lsave(c, buf + offs, c->lsave);384 offs += c->lsave_sz;385 dbg_chk_lpt_sz(c, 1, c->lsave_sz);386 }387 388 if (offs + c->ltab_sz <= c->leb_size) {389 done_ltab = 1;390 ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);391 offs += c->ltab_sz;392 dbg_chk_lpt_sz(c, 1, c->ltab_sz);393 }394 395 /* Loop for each cnode */396 do {397 if (cnode->level)398 len = c->nnode_sz;399 else400 len = c->pnode_sz;401 while (offs + len > c->leb_size) {402 wlen = offs - from;403 if (wlen) {404 alen = ALIGN(wlen, c->min_io_size);405 memset(buf + offs, 0xff, alen - wlen);406 err = ubifs_leb_write(c, lnum, buf + from, from,407 alen);408 if (err)409 return err;410 }411 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);412 err = realloc_lpt_leb(c, &lnum);413 if (err)414 goto no_space;415 offs = from = 0;416 ubifs_assert(c, lnum >= c->lpt_first &&417 lnum <= c->lpt_last);418 err = ubifs_leb_unmap(c, lnum);419 if (err)420 return err;421 /* Try to place lsave and ltab nicely */422 if (!done_lsave) {423 done_lsave = 1;424 ubifs_pack_lsave(c, buf + offs, c->lsave);425 offs += c->lsave_sz;426 dbg_chk_lpt_sz(c, 1, c->lsave_sz);427 continue;428 }429 if (!done_ltab) {430 done_ltab = 1;431 ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);432 offs += c->ltab_sz;433 dbg_chk_lpt_sz(c, 1, c->ltab_sz);434 continue;435 }436 break;437 }438 if (cnode->level)439 ubifs_pack_nnode(c, buf + offs,440 (struct ubifs_nnode *)cnode);441 else442 ubifs_pack_pnode(c, buf + offs,443 (struct ubifs_pnode *)cnode);444 /*445 * The reason for the barriers is the same as in case of TNC.446 * See comment in 'write_index()'. 'dirty_cow_nnode()' and447 * 'dirty_cow_pnode()' are the functions for which this is448 * important.449 */450 clear_bit(DIRTY_CNODE, &cnode->flags);451 smp_mb__before_atomic();452 clear_bit(COW_CNODE, &cnode->flags);453 smp_mb__after_atomic();454 offs += len;455 dbg_chk_lpt_sz(c, 1, len);456 cnode = cnode->cnext;457 } while (cnode && cnode != c->lpt_cnext);458 459 /* Make sure to place LPT's save table */460 if (!done_lsave) {461 if (offs + c->lsave_sz > c->leb_size) {462 wlen = offs - from;463 alen = ALIGN(wlen, c->min_io_size);464 memset(buf + offs, 0xff, alen - wlen);465 err = ubifs_leb_write(c, lnum, buf + from, from, alen);466 if (err)467 return err;468 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);469 err = realloc_lpt_leb(c, &lnum);470 if (err)471 goto no_space;472 offs = from = 0;473 ubifs_assert(c, lnum >= c->lpt_first &&474 lnum <= c->lpt_last);475 err = ubifs_leb_unmap(c, lnum);476 if (err)477 return err;478 }479 done_lsave = 1;480 ubifs_pack_lsave(c, buf + offs, c->lsave);481 offs += c->lsave_sz;482 dbg_chk_lpt_sz(c, 1, c->lsave_sz);483 }484 485 /* Make sure to place LPT's own lprops table */486 if (!done_ltab) {487 if (offs + c->ltab_sz > c->leb_size) {488 wlen = offs - from;489 alen = ALIGN(wlen, c->min_io_size);490 memset(buf + offs, 0xff, alen - wlen);491 err = ubifs_leb_write(c, lnum, buf + from, from, alen);492 if (err)493 return err;494 dbg_chk_lpt_sz(c, 2, c->leb_size - offs);495 err = realloc_lpt_leb(c, &lnum);496 if (err)497 goto no_space;498 offs = from = 0;499 ubifs_assert(c, lnum >= c->lpt_first &&500 lnum <= c->lpt_last);501 err = ubifs_leb_unmap(c, lnum);502 if (err)503 return err;504 }505 ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);506 offs += c->ltab_sz;507 dbg_chk_lpt_sz(c, 1, c->ltab_sz);508 }509 510 /* Write remaining data in buffer */511 wlen = offs - from;512 alen = ALIGN(wlen, c->min_io_size);513 memset(buf + offs, 0xff, alen - wlen);514 err = ubifs_leb_write(c, lnum, buf + from, from, alen);515 if (err)516 return err;517 518 dbg_chk_lpt_sz(c, 4, alen - wlen);519 err = dbg_chk_lpt_sz(c, 3, ALIGN(offs, c->min_io_size));520 if (err)521 return err;522 523 c->nhead_lnum = lnum;524 c->nhead_offs = ALIGN(offs, c->min_io_size);525 526 dbg_lp("LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs);527 dbg_lp("LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs);528 dbg_lp("LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs);529 if (c->big_lpt)530 dbg_lp("LPT lsave is at %d:%d", c->lsave_lnum, c->lsave_offs);531 532 return 0;533 534no_space:535 ubifs_err(c, "LPT out of space mismatch at LEB %d:%d needing %d, done_ltab %d, done_lsave %d",536 lnum, offs, len, done_ltab, done_lsave);537 ubifs_dump_lpt_info(c);538 ubifs_dump_lpt_lebs(c);539 dump_stack();540 return err;541}542 543/**544 * next_pnode_to_dirty - find next pnode to dirty.545 * @c: UBIFS file-system description object546 * @pnode: pnode547 *548 * This function returns the next pnode to dirty or %NULL if there are no more549 * pnodes. Note that pnodes that have never been written (lnum == 0) are550 * skipped.551 */552static struct ubifs_pnode *next_pnode_to_dirty(struct ubifs_info *c,553 struct ubifs_pnode *pnode)554{555 struct ubifs_nnode *nnode;556 int iip;557 558 /* Try to go right */559 nnode = pnode->parent;560 for (iip = pnode->iip + 1; iip < UBIFS_LPT_FANOUT; iip++) {561 if (nnode->nbranch[iip].lnum)562 return ubifs_get_pnode(c, nnode, iip);563 }564 565 /* Go up while can't go right */566 do {567 iip = nnode->iip + 1;568 nnode = nnode->parent;569 if (!nnode)570 return NULL;571 for (; iip < UBIFS_LPT_FANOUT; iip++) {572 if (nnode->nbranch[iip].lnum)573 break;574 }575 } while (iip >= UBIFS_LPT_FANOUT);576 577 /* Go right */578 nnode = ubifs_get_nnode(c, nnode, iip);579 if (IS_ERR(nnode))580 return (void *)nnode;581 582 /* Go down to level 1 */583 while (nnode->level > 1) {584 for (iip = 0; iip < UBIFS_LPT_FANOUT; iip++) {585 if (nnode->nbranch[iip].lnum)586 break;587 }588 if (iip >= UBIFS_LPT_FANOUT) {589 /*590 * Should not happen, but we need to keep going591 * if it does.592 */593 iip = 0;594 }595 nnode = ubifs_get_nnode(c, nnode, iip);596 if (IS_ERR(nnode))597 return (void *)nnode;598 }599 600 for (iip = 0; iip < UBIFS_LPT_FANOUT; iip++)601 if (nnode->nbranch[iip].lnum)602 break;603 if (iip >= UBIFS_LPT_FANOUT)604 /* Should not happen, but we need to keep going if it does */605 iip = 0;606 return ubifs_get_pnode(c, nnode, iip);607}608 609/**610 * add_pnode_dirt - add dirty space to LPT LEB properties.611 * @c: UBIFS file-system description object612 * @pnode: pnode for which to add dirt613 */614static void add_pnode_dirt(struct ubifs_info *c, struct ubifs_pnode *pnode)615{616 ubifs_add_lpt_dirt(c, pnode->parent->nbranch[pnode->iip].lnum,617 c->pnode_sz);618}619 620/**621 * do_make_pnode_dirty - mark a pnode dirty.622 * @c: UBIFS file-system description object623 * @pnode: pnode to mark dirty624 */625static void do_make_pnode_dirty(struct ubifs_info *c, struct ubifs_pnode *pnode)626{627 /* Assumes cnext list is empty i.e. not called during commit */628 if (!test_and_set_bit(DIRTY_CNODE, &pnode->flags)) {629 struct ubifs_nnode *nnode;630 631 c->dirty_pn_cnt += 1;632 add_pnode_dirt(c, pnode);633 /* Mark parent and ancestors dirty too */634 nnode = pnode->parent;635 while (nnode) {636 if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {637 c->dirty_nn_cnt += 1;638 ubifs_add_nnode_dirt(c, nnode);639 nnode = nnode->parent;640 } else641 break;642 }643 }644}645 646/**647 * make_tree_dirty - mark the entire LEB properties tree dirty.648 * @c: UBIFS file-system description object649 *650 * This function is used by the "small" LPT model to cause the entire LEB651 * properties tree to be written. The "small" LPT model does not use LPT652 * garbage collection because it is more efficient to write the entire tree653 * (because it is small).654 *655 * This function returns %0 on success and a negative error code on failure.656 */657static int make_tree_dirty(struct ubifs_info *c)658{659 struct ubifs_pnode *pnode;660 661 pnode = ubifs_pnode_lookup(c, 0);662 if (IS_ERR(pnode))663 return PTR_ERR(pnode);664 665 while (pnode) {666 do_make_pnode_dirty(c, pnode);667 pnode = next_pnode_to_dirty(c, pnode);668 if (IS_ERR(pnode))669 return PTR_ERR(pnode);670 }671 return 0;672}673 674/**675 * need_write_all - determine if the LPT area is running out of free space.676 * @c: UBIFS file-system description object677 *678 * This function returns %1 if the LPT area is running out of free space and %0679 * if it is not.680 */681static int need_write_all(struct ubifs_info *c)682{683 long long free = 0;684 int i;685 686 for (i = 0; i < c->lpt_lebs; i++) {687 if (i + c->lpt_first == c->nhead_lnum)688 free += c->leb_size - c->nhead_offs;689 else if (c->ltab[i].free == c->leb_size)690 free += c->leb_size;691 else if (c->ltab[i].free + c->ltab[i].dirty == c->leb_size)692 free += c->leb_size;693 }694 /* Less than twice the size left */695 if (free <= c->lpt_sz * 2)696 return 1;697 return 0;698}699 700/**701 * lpt_tgc_start - start trivial garbage collection of LPT LEBs.702 * @c: UBIFS file-system description object703 *704 * LPT trivial garbage collection is where a LPT LEB contains only dirty and705 * free space and so may be reused as soon as the next commit is completed.706 * This function is called during start commit to mark LPT LEBs for trivial GC.707 */708static void lpt_tgc_start(struct ubifs_info *c)709{710 int i;711 712 for (i = 0; i < c->lpt_lebs; i++) {713 if (i + c->lpt_first == c->nhead_lnum)714 continue;715 if (c->ltab[i].dirty > 0 &&716 c->ltab[i].free + c->ltab[i].dirty == c->leb_size) {717 c->ltab[i].tgc = 1;718 c->ltab[i].free = c->leb_size;719 c->ltab[i].dirty = 0;720 dbg_lp("LEB %d", i + c->lpt_first);721 }722 }723}724 725/**726 * lpt_tgc_end - end trivial garbage collection of LPT LEBs.727 * @c: UBIFS file-system description object728 *729 * LPT trivial garbage collection is where a LPT LEB contains only dirty and730 * free space and so may be reused as soon as the next commit is completed.731 * This function is called after the commit is completed (master node has been732 * written) and un-maps LPT LEBs that were marked for trivial GC.733 */734static int lpt_tgc_end(struct ubifs_info *c)735{736 int i, err;737 738 for (i = 0; i < c->lpt_lebs; i++)739 if (c->ltab[i].tgc) {740 err = ubifs_leb_unmap(c, i + c->lpt_first);741 if (err)742 return err;743 c->ltab[i].tgc = 0;744 dbg_lp("LEB %d", i + c->lpt_first);745 }746 return 0;747}748 749/**750 * populate_lsave - fill the lsave array with important LEB numbers.751 * @c: the UBIFS file-system description object752 *753 * This function is only called for the "big" model. It records a small number754 * of LEB numbers of important LEBs. Important LEBs are ones that are (from755 * most important to least important): empty, freeable, freeable index, dirty756 * index, dirty or free. Upon mount, we read this list of LEB numbers and bring757 * their pnodes into memory. That will stop us from having to scan the LPT758 * straight away. For the "small" model we assume that scanning the LPT is no759 * big deal.760 */761static void populate_lsave(struct ubifs_info *c)762{763 struct ubifs_lprops *lprops;764 struct ubifs_lpt_heap *heap;765 int i, cnt = 0;766 767 ubifs_assert(c, c->big_lpt);768 if (!(c->lpt_drty_flgs & LSAVE_DIRTY)) {769 c->lpt_drty_flgs |= LSAVE_DIRTY;770 ubifs_add_lpt_dirt(c, c->lsave_lnum, c->lsave_sz);771 }772 773 if (dbg_populate_lsave(c))774 return;775 776 list_for_each_entry(lprops, &c->empty_list, list) {777 c->lsave[cnt++] = lprops->lnum;778 if (cnt >= c->lsave_cnt)779 return;780 }781 list_for_each_entry(lprops, &c->freeable_list, list) {782 c->lsave[cnt++] = lprops->lnum;783 if (cnt >= c->lsave_cnt)784 return;785 }786 list_for_each_entry(lprops, &c->frdi_idx_list, list) {787 c->lsave[cnt++] = lprops->lnum;788 if (cnt >= c->lsave_cnt)789 return;790 }791 heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];792 for (i = 0; i < heap->cnt; i++) {793 c->lsave[cnt++] = heap->arr[i]->lnum;794 if (cnt >= c->lsave_cnt)795 return;796 }797 heap = &c->lpt_heap[LPROPS_DIRTY - 1];798 for (i = 0; i < heap->cnt; i++) {799 c->lsave[cnt++] = heap->arr[i]->lnum;800 if (cnt >= c->lsave_cnt)801 return;802 }803 heap = &c->lpt_heap[LPROPS_FREE - 1];804 for (i = 0; i < heap->cnt; i++) {805 c->lsave[cnt++] = heap->arr[i]->lnum;806 if (cnt >= c->lsave_cnt)807 return;808 }809 /* Fill it up completely */810 while (cnt < c->lsave_cnt)811 c->lsave[cnt++] = c->main_first;812}813 814/**815 * nnode_lookup - lookup a nnode in the LPT.816 * @c: UBIFS file-system description object817 * @i: nnode number818 *819 * This function returns a pointer to the nnode on success or a negative820 * error code on failure.821 */822static struct ubifs_nnode *nnode_lookup(struct ubifs_info *c, int i)823{824 int err, iip;825 struct ubifs_nnode *nnode;826 827 if (!c->nroot) {828 err = ubifs_read_nnode(c, NULL, 0);829 if (err)830 return ERR_PTR(err);831 }832 nnode = c->nroot;833 while (1) {834 iip = i & (UBIFS_LPT_FANOUT - 1);835 i >>= UBIFS_LPT_FANOUT_SHIFT;836 if (!i)837 break;838 nnode = ubifs_get_nnode(c, nnode, iip);839 if (IS_ERR(nnode))840 return nnode;841 }842 return nnode;843}844 845/**846 * make_nnode_dirty - find a nnode and, if found, make it dirty.847 * @c: UBIFS file-system description object848 * @node_num: nnode number of nnode to make dirty849 * @lnum: LEB number where nnode was written850 * @offs: offset where nnode was written851 *852 * This function is used by LPT garbage collection. LPT garbage collection is853 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection854 * simply involves marking all the nodes in the LEB being garbage-collected as855 * dirty. The dirty nodes are written next commit, after which the LEB is free856 * to be reused.857 *858 * This function returns %0 on success and a negative error code on failure.859 */860static int make_nnode_dirty(struct ubifs_info *c, int node_num, int lnum,861 int offs)862{863 struct ubifs_nnode *nnode;864 865 nnode = nnode_lookup(c, node_num);866 if (IS_ERR(nnode))867 return PTR_ERR(nnode);868 if (nnode->parent) {869 struct ubifs_nbranch *branch;870 871 branch = &nnode->parent->nbranch[nnode->iip];872 if (branch->lnum != lnum || branch->offs != offs)873 return 0; /* nnode is obsolete */874 } else if (c->lpt_lnum != lnum || c->lpt_offs != offs)875 return 0; /* nnode is obsolete */876 /* Assumes cnext list is empty i.e. not called during commit */877 if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {878 c->dirty_nn_cnt += 1;879 ubifs_add_nnode_dirt(c, nnode);880 /* Mark parent and ancestors dirty too */881 nnode = nnode->parent;882 while (nnode) {883 if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {884 c->dirty_nn_cnt += 1;885 ubifs_add_nnode_dirt(c, nnode);886 nnode = nnode->parent;887 } else888 break;889 }890 }891 return 0;892}893 894/**895 * make_pnode_dirty - find a pnode and, if found, make it dirty.896 * @c: UBIFS file-system description object897 * @node_num: pnode number of pnode to make dirty898 * @lnum: LEB number where pnode was written899 * @offs: offset where pnode was written900 *901 * This function is used by LPT garbage collection. LPT garbage collection is902 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection903 * simply involves marking all the nodes in the LEB being garbage-collected as904 * dirty. The dirty nodes are written next commit, after which the LEB is free905 * to be reused.906 *907 * This function returns %0 on success and a negative error code on failure.908 */909static int make_pnode_dirty(struct ubifs_info *c, int node_num, int lnum,910 int offs)911{912 struct ubifs_pnode *pnode;913 struct ubifs_nbranch *branch;914 915 pnode = ubifs_pnode_lookup(c, node_num);916 if (IS_ERR(pnode))917 return PTR_ERR(pnode);918 branch = &pnode->parent->nbranch[pnode->iip];919 if (branch->lnum != lnum || branch->offs != offs)920 return 0;921 do_make_pnode_dirty(c, pnode);922 return 0;923}924 925/**926 * make_ltab_dirty - make ltab node dirty.927 * @c: UBIFS file-system description object928 * @lnum: LEB number where ltab was written929 * @offs: offset where ltab was written930 *931 * This function is used by LPT garbage collection. LPT garbage collection is932 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection933 * simply involves marking all the nodes in the LEB being garbage-collected as934 * dirty. The dirty nodes are written next commit, after which the LEB is free935 * to be reused.936 *937 * This function returns %0 on success and a negative error code on failure.938 */939static int make_ltab_dirty(struct ubifs_info *c, int lnum, int offs)940{941 if (lnum != c->ltab_lnum || offs != c->ltab_offs)942 return 0; /* This ltab node is obsolete */943 if (!(c->lpt_drty_flgs & LTAB_DIRTY)) {944 c->lpt_drty_flgs |= LTAB_DIRTY;945 ubifs_add_lpt_dirt(c, c->ltab_lnum, c->ltab_sz);946 }947 return 0;948}949 950/**951 * make_lsave_dirty - make lsave node dirty.952 * @c: UBIFS file-system description object953 * @lnum: LEB number where lsave was written954 * @offs: offset where lsave was written955 *956 * This function is used by LPT garbage collection. LPT garbage collection is957 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection958 * simply involves marking all the nodes in the LEB being garbage-collected as959 * dirty. The dirty nodes are written next commit, after which the LEB is free960 * to be reused.961 *962 * This function returns %0 on success and a negative error code on failure.963 */964static int make_lsave_dirty(struct ubifs_info *c, int lnum, int offs)965{966 if (lnum != c->lsave_lnum || offs != c->lsave_offs)967 return 0; /* This lsave node is obsolete */968 if (!(c->lpt_drty_flgs & LSAVE_DIRTY)) {969 c->lpt_drty_flgs |= LSAVE_DIRTY;970 ubifs_add_lpt_dirt(c, c->lsave_lnum, c->lsave_sz);971 }972 return 0;973}974 975/**976 * make_node_dirty - make node dirty.977 * @c: UBIFS file-system description object978 * @node_type: LPT node type979 * @node_num: node number980 * @lnum: LEB number where node was written981 * @offs: offset where node was written982 *983 * This function is used by LPT garbage collection. LPT garbage collection is984 * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection985 * simply involves marking all the nodes in the LEB being garbage-collected as986 * dirty. The dirty nodes are written next commit, after which the LEB is free987 * to be reused.988 *989 * This function returns %0 on success and a negative error code on failure.990 */991static int make_node_dirty(struct ubifs_info *c, int node_type, int node_num,992 int lnum, int offs)993{994 switch (node_type) {995 case UBIFS_LPT_NNODE:996 return make_nnode_dirty(c, node_num, lnum, offs);997 case UBIFS_LPT_PNODE:998 return make_pnode_dirty(c, node_num, lnum, offs);999 case UBIFS_LPT_LTAB:1000 return make_ltab_dirty(c, lnum, offs);1001 case UBIFS_LPT_LSAVE:1002 return make_lsave_dirty(c, lnum, offs);1003 }1004 return -EINVAL;1005}1006 1007/**1008 * get_lpt_node_len - return the length of a node based on its type.1009 * @c: UBIFS file-system description object1010 * @node_type: LPT node type1011 */1012static int get_lpt_node_len(const struct ubifs_info *c, int node_type)1013{1014 switch (node_type) {1015 case UBIFS_LPT_NNODE:1016 return c->nnode_sz;1017 case UBIFS_LPT_PNODE:1018 return c->pnode_sz;1019 case UBIFS_LPT_LTAB:1020 return c->ltab_sz;1021 case UBIFS_LPT_LSAVE:1022 return c->lsave_sz;1023 }1024 return 0;1025}1026 1027/**1028 * get_pad_len - return the length of padding in a buffer.1029 * @c: UBIFS file-system description object1030 * @buf: buffer1031 * @len: length of buffer1032 */1033static int get_pad_len(const struct ubifs_info *c, uint8_t *buf, int len)1034{1035 int offs, pad_len;1036 1037 if (c->min_io_size == 1)1038 return 0;1039 offs = c->leb_size - len;1040 pad_len = ALIGN(offs, c->min_io_size) - offs;1041 return pad_len;1042}1043 1044/**1045 * get_lpt_node_type - return type (and node number) of a node in a buffer.1046 * @c: UBIFS file-system description object1047 * @buf: buffer1048 * @node_num: node number is returned here1049 */1050static int get_lpt_node_type(const struct ubifs_info *c, uint8_t *buf,1051 int *node_num)1052{1053 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;1054 int pos = 0, node_type;1055 1056 node_type = ubifs_unpack_bits(c, &addr, &pos, UBIFS_LPT_TYPE_BITS);1057 *node_num = ubifs_unpack_bits(c, &addr, &pos, c->pcnt_bits);1058 return node_type;1059}1060 1061/**1062 * is_a_node - determine if a buffer contains a node.1063 * @c: UBIFS file-system description object1064 * @buf: buffer1065 * @len: length of buffer1066 *1067 * This function returns %1 if the buffer contains a node or %0 if it does not.1068 */1069static int is_a_node(const struct ubifs_info *c, uint8_t *buf, int len)1070{1071 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;1072 int pos = 0, node_type, node_len;1073 uint16_t crc, calc_crc;1074 1075 if (len < UBIFS_LPT_CRC_BYTES + (UBIFS_LPT_TYPE_BITS + 7) / 8)1076 return 0;1077 node_type = ubifs_unpack_bits(c, &addr, &pos, UBIFS_LPT_TYPE_BITS);1078 if (node_type == UBIFS_LPT_NOT_A_NODE)1079 return 0;1080 node_len = get_lpt_node_len(c, node_type);1081 if (!node_len || node_len > len)1082 return 0;1083 pos = 0;1084 addr = buf;1085 crc = ubifs_unpack_bits(c, &addr, &pos, UBIFS_LPT_CRC_BITS);1086 calc_crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,1087 node_len - UBIFS_LPT_CRC_BYTES);1088 if (crc != calc_crc)1089 return 0;1090 return 1;1091}1092 1093/**1094 * lpt_gc_lnum - garbage collect a LPT LEB.1095 * @c: UBIFS file-system description object1096 * @lnum: LEB number to garbage collect1097 *1098 * LPT garbage collection is used only for the "big" LPT model1099 * (c->big_lpt == 1). Garbage collection simply involves marking all the nodes1100 * in the LEB being garbage-collected as dirty. The dirty nodes are written1101 * next commit, after which the LEB is free to be reused.1102 *1103 * This function returns %0 on success and a negative error code on failure.1104 */1105static int lpt_gc_lnum(struct ubifs_info *c, int lnum)1106{1107 int err, len = c->leb_size, node_type, node_num, node_len, offs;1108 void *buf = c->lpt_buf;1109 1110 dbg_lp("LEB %d", lnum);1111 1112 err = ubifs_leb_read(c, lnum, buf, 0, c->leb_size, 1);1113 if (err)1114 return err;1115 1116 while (1) {1117 if (!is_a_node(c, buf, len)) {1118 int pad_len;1119 1120 pad_len = get_pad_len(c, buf, len);1121 if (pad_len) {1122 buf += pad_len;1123 len -= pad_len;1124 continue;1125 }1126 return 0;1127 }1128 node_type = get_lpt_node_type(c, buf, &node_num);1129 node_len = get_lpt_node_len(c, node_type);1130 offs = c->leb_size - len;1131 ubifs_assert(c, node_len != 0);1132 mutex_lock(&c->lp_mutex);1133 err = make_node_dirty(c, node_type, node_num, lnum, offs);1134 mutex_unlock(&c->lp_mutex);1135 if (err)1136 return err;1137 buf += node_len;1138 len -= node_len;1139 }1140 return 0;1141}1142 1143/**1144 * lpt_gc - LPT garbage collection.1145 * @c: UBIFS file-system description object1146 *1147 * Select a LPT LEB for LPT garbage collection and call 'lpt_gc_lnum()'.1148 * Returns %0 on success and a negative error code on failure.1149 */1150static int lpt_gc(struct ubifs_info *c)1151{1152 int i, lnum = -1, dirty = 0;1153 1154 mutex_lock(&c->lp_mutex);1155 for (i = 0; i < c->lpt_lebs; i++) {1156 ubifs_assert(c, !c->ltab[i].tgc);1157 if (i + c->lpt_first == c->nhead_lnum ||1158 c->ltab[i].free + c->ltab[i].dirty == c->leb_size)1159 continue;1160 if (c->ltab[i].dirty > dirty) {1161 dirty = c->ltab[i].dirty;1162 lnum = i + c->lpt_first;1163 }1164 }1165 mutex_unlock(&c->lp_mutex);1166 if (lnum == -1)1167 return -ENOSPC;1168 return lpt_gc_lnum(c, lnum);1169}1170 1171/**1172 * ubifs_lpt_start_commit - UBIFS commit starts.1173 * @c: the UBIFS file-system description object1174 *1175 * This function has to be called when UBIFS starts the commit operation.1176 * This function "freezes" all currently dirty LEB properties and does not1177 * change them anymore. Further changes are saved and tracked separately1178 * because they are not part of this commit. This function returns zero in case1179 * of success and a negative error code in case of failure.1180 */1181int ubifs_lpt_start_commit(struct ubifs_info *c)1182{1183 int err, cnt;1184 1185 dbg_lp("");1186 1187 mutex_lock(&c->lp_mutex);1188 err = dbg_chk_lpt_free_spc(c);1189 if (err)1190 goto out;1191 err = dbg_check_ltab(c);1192 if (err)1193 goto out;1194 1195 if (c->check_lpt_free) {1196 /*1197 * We ensure there is enough free space in1198 * ubifs_lpt_post_commit() by marking nodes dirty. That1199 * information is lost when we unmount, so we also need1200 * to check free space once after mounting also.1201 */1202 c->check_lpt_free = 0;1203 while (need_write_all(c)) {1204 mutex_unlock(&c->lp_mutex);1205 err = lpt_gc(c);1206 if (err)1207 return err;1208 mutex_lock(&c->lp_mutex);1209 }1210 }1211 1212 lpt_tgc_start(c);1213 1214 if (!c->dirty_pn_cnt) {1215 dbg_cmt("no cnodes to commit");1216 err = 0;1217 goto out;1218 }1219 1220 if (!c->big_lpt && need_write_all(c)) {1221 /* If needed, write everything */1222 err = make_tree_dirty(c);1223 if (err)1224 goto out;1225 lpt_tgc_start(c);1226 }1227 1228 if (c->big_lpt)1229 populate_lsave(c);1230 1231 cnt = get_cnodes_to_commit(c);1232 ubifs_assert(c, cnt != 0);1233 1234 err = layout_cnodes(c);1235 if (err)1236 goto out;1237 1238 err = ubifs_lpt_calc_hash(c, c->mst_node->hash_lpt);1239 if (err)1240 goto out;1241 1242 /* Copy the LPT's own lprops for end commit to write */1243 memcpy(c->ltab_cmt, c->ltab,1244 sizeof(struct ubifs_lpt_lprops) * c->lpt_lebs);1245 c->lpt_drty_flgs &= ~(LTAB_DIRTY | LSAVE_DIRTY);1246 1247out:1248 mutex_unlock(&c->lp_mutex);1249 return err;1250}1251 1252/**1253 * free_obsolete_cnodes - free obsolete cnodes for commit end.1254 * @c: UBIFS file-system description object1255 */1256static void free_obsolete_cnodes(struct ubifs_info *c)1257{1258 struct ubifs_cnode *cnode, *cnext;1259 1260 cnext = c->lpt_cnext;1261 if (!cnext)1262 return;1263 do {1264 cnode = cnext;1265 cnext = cnode->cnext;1266 if (test_bit(OBSOLETE_CNODE, &cnode->flags))1267 kfree(cnode);1268 else1269 cnode->cnext = NULL;1270 } while (cnext != c->lpt_cnext);1271 c->lpt_cnext = NULL;1272}1273 1274/**1275 * ubifs_lpt_end_commit - finish the commit operation.1276 * @c: the UBIFS file-system description object1277 *1278 * This function has to be called when the commit operation finishes. It1279 * flushes the changes which were "frozen" by 'ubifs_lprops_start_commit()' to1280 * the media. Returns zero in case of success and a negative error code in case1281 * of failure.1282 */1283int ubifs_lpt_end_commit(struct ubifs_info *c)1284{1285 int err;1286 1287 dbg_lp("");1288 1289 if (!c->lpt_cnext)1290 return 0;1291 1292 err = write_cnodes(c);1293 if (err)1294 return err;1295 1296 mutex_lock(&c->lp_mutex);1297 free_obsolete_cnodes(c);1298 mutex_unlock(&c->lp_mutex);1299 1300 return 0;1301}1302 1303/**1304 * ubifs_lpt_post_commit - post commit LPT trivial GC and LPT GC.1305 * @c: UBIFS file-system description object1306 *1307 * LPT trivial GC is completed after a commit. Also LPT GC is done after a1308 * commit for the "big" LPT model.1309 */1310int ubifs_lpt_post_commit(struct ubifs_info *c)1311{1312 int err;1313 1314 mutex_lock(&c->lp_mutex);1315 err = lpt_tgc_end(c);1316 if (err)1317 goto out;1318 if (c->big_lpt)1319 while (need_write_all(c)) {1320 mutex_unlock(&c->lp_mutex);1321 err = lpt_gc(c);1322 if (err)1323 return err;1324 mutex_lock(&c->lp_mutex);1325 }1326out:1327 mutex_unlock(&c->lp_mutex);1328 return err;1329}1330 1331/**1332 * first_nnode - find the first nnode in memory.1333 * @c: UBIFS file-system description object1334 * @hght: height of tree where nnode found is returned here1335 *1336 * This function returns a pointer to the nnode found or %NULL if no nnode is1337 * found. This function is a helper to 'ubifs_lpt_free()'.1338 */1339static struct ubifs_nnode *first_nnode(struct ubifs_info *c, int *hght)1340{1341 struct ubifs_nnode *nnode;1342 int h, i, found;1343 1344 nnode = c->nroot;1345 *hght = 0;1346 if (!nnode)1347 return NULL;1348 for (h = 1; h < c->lpt_hght; h++) {1349 found = 0;1350 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {1351 if (nnode->nbranch[i].nnode) {1352 found = 1;1353 nnode = nnode->nbranch[i].nnode;1354 *hght = h;1355 break;1356 }1357 }1358 if (!found)1359 break;1360 }1361 return nnode;1362}1363 1364/**1365 * next_nnode - find the next nnode in memory.1366 * @c: UBIFS file-system description object1367 * @nnode: nnode from which to start.1368 * @hght: height of tree where nnode is, is passed and returned here1369 *1370 * This function returns a pointer to the nnode found or %NULL if no nnode is1371 * found. This function is a helper to 'ubifs_lpt_free()'.1372 */1373static struct ubifs_nnode *next_nnode(struct ubifs_info *c,1374 struct ubifs_nnode *nnode, int *hght)1375{1376 struct ubifs_nnode *parent;1377 int iip, h, i, found;1378 1379 parent = nnode->parent;1380 if (!parent)1381 return NULL;1382 if (nnode->iip == UBIFS_LPT_FANOUT - 1) {1383 *hght -= 1;1384 return parent;1385 }1386 for (iip = nnode->iip + 1; iip < UBIFS_LPT_FANOUT; iip++) {1387 nnode = parent->nbranch[iip].nnode;1388 if (nnode)1389 break;1390 }1391 if (!nnode) {1392 *hght -= 1;1393 return parent;1394 }1395 for (h = *hght + 1; h < c->lpt_hght; h++) {1396 found = 0;1397 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {1398 if (nnode->nbranch[i].nnode) {1399 found = 1;1400 nnode = nnode->nbranch[i].nnode;1401 *hght = h;1402 break;1403 }1404 }1405 if (!found)1406 break;1407 }1408 return nnode;1409}1410 1411/**1412 * ubifs_lpt_free - free resources owned by the LPT.1413 * @c: UBIFS file-system description object1414 * @wr_only: free only resources used for writing1415 */1416void ubifs_lpt_free(struct ubifs_info *c, int wr_only)1417{1418 struct ubifs_nnode *nnode;1419 int i, hght;1420 1421 /* Free write-only things first */1422 1423 free_obsolete_cnodes(c); /* Leftover from a failed commit */1424 1425 vfree(c->ltab_cmt);1426 c->ltab_cmt = NULL;1427 vfree(c->lpt_buf);1428 c->lpt_buf = NULL;1429 kfree(c->lsave);1430 c->lsave = NULL;1431 1432 if (wr_only)1433 return;1434 1435 /* Now free the rest */1436 1437 nnode = first_nnode(c, &hght);1438 while (nnode) {1439 for (i = 0; i < UBIFS_LPT_FANOUT; i++)1440 kfree(nnode->nbranch[i].nnode);1441 nnode = next_nnode(c, nnode, &hght);1442 }1443 for (i = 0; i < LPROPS_HEAP_CNT; i++)1444 kfree(c->lpt_heap[i].arr);1445 kfree(c->dirty_idx.arr);1446 kfree(c->nroot);1447 vfree(c->ltab);1448 kfree(c->lpt_nod_buf);1449}1450 1451/*1452 * Everything below is related to debugging.1453 */1454 1455/**1456 * dbg_is_all_ff - determine if a buffer contains only 0xFF bytes.1457 * @buf: buffer1458 * @len: buffer length1459 */1460static int dbg_is_all_ff(uint8_t *buf, int len)1461{1462 int i;1463 1464 for (i = 0; i < len; i++)1465 if (buf[i] != 0xff)1466 return 0;1467 return 1;1468}1469 1470/**1471 * dbg_is_nnode_dirty - determine if a nnode is dirty.1472 * @c: the UBIFS file-system description object1473 * @lnum: LEB number where nnode was written1474 * @offs: offset where nnode was written1475 */1476static int dbg_is_nnode_dirty(struct ubifs_info *c, int lnum, int offs)1477{1478 struct ubifs_nnode *nnode;1479 int hght;1480 1481 /* Entire tree is in memory so first_nnode / next_nnode are OK */1482 nnode = first_nnode(c, &hght);1483 for (; nnode; nnode = next_nnode(c, nnode, &hght)) {1484 struct ubifs_nbranch *branch;1485 1486 cond_resched();1487 if (nnode->parent) {1488 branch = &nnode->parent->nbranch[nnode->iip];1489 if (branch->lnum != lnum || branch->offs != offs)1490 continue;1491 if (test_bit(DIRTY_CNODE, &nnode->flags))1492 return 1;1493 return 0;1494 } else {1495 if (c->lpt_lnum != lnum || c->lpt_offs != offs)1496 continue;1497 if (test_bit(DIRTY_CNODE, &nnode->flags))1498 return 1;1499 return 0;1500 }1501 }1502 return 1;1503}1504 1505/**1506 * dbg_is_pnode_dirty - determine if a pnode is dirty.1507 * @c: the UBIFS file-system description object1508 * @lnum: LEB number where pnode was written1509 * @offs: offset where pnode was written1510 */1511static int dbg_is_pnode_dirty(struct ubifs_info *c, int lnum, int offs)1512{1513 int i, cnt;1514 1515 cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);1516 for (i = 0; i < cnt; i++) {1517 struct ubifs_pnode *pnode;1518 struct ubifs_nbranch *branch;1519 1520 cond_resched();1521 pnode = ubifs_pnode_lookup(c, i);1522 if (IS_ERR(pnode))1523 return PTR_ERR(pnode);1524 branch = &pnode->parent->nbranch[pnode->iip];1525 if (branch->lnum != lnum || branch->offs != offs)1526 continue;1527 if (test_bit(DIRTY_CNODE, &pnode->flags))1528 return 1;1529 return 0;1530 }1531 return 1;1532}1533 1534/**1535 * dbg_is_ltab_dirty - determine if a ltab node is dirty.1536 * @c: the UBIFS file-system description object1537 * @lnum: LEB number where ltab node was written1538 * @offs: offset where ltab node was written1539 */1540static int dbg_is_ltab_dirty(struct ubifs_info *c, int lnum, int offs)1541{1542 if (lnum != c->ltab_lnum || offs != c->ltab_offs)1543 return 1;1544 return (c->lpt_drty_flgs & LTAB_DIRTY) != 0;1545}1546 1547/**1548 * dbg_is_lsave_dirty - determine if a lsave node is dirty.1549 * @c: the UBIFS file-system description object1550 * @lnum: LEB number where lsave node was written1551 * @offs: offset where lsave node was written1552 */1553static int dbg_is_lsave_dirty(struct ubifs_info *c, int lnum, int offs)1554{1555 if (lnum != c->lsave_lnum || offs != c->lsave_offs)1556 return 1;1557 return (c->lpt_drty_flgs & LSAVE_DIRTY) != 0;1558}1559 1560/**1561 * dbg_is_node_dirty - determine if a node is dirty.1562 * @c: the UBIFS file-system description object1563 * @node_type: node type1564 * @lnum: LEB number where node was written1565 * @offs: offset where node was written1566 */1567static int dbg_is_node_dirty(struct ubifs_info *c, int node_type, int lnum,1568 int offs)1569{1570 switch (node_type) {1571 case UBIFS_LPT_NNODE:1572 return dbg_is_nnode_dirty(c, lnum, offs);1573 case UBIFS_LPT_PNODE:1574 return dbg_is_pnode_dirty(c, lnum, offs);1575 case UBIFS_LPT_LTAB:1576 return dbg_is_ltab_dirty(c, lnum, offs);1577 case UBIFS_LPT_LSAVE:1578 return dbg_is_lsave_dirty(c, lnum, offs);1579 }1580 return 1;1581}1582 1583/**1584 * dbg_check_ltab_lnum - check the ltab for a LPT LEB number.1585 * @c: the UBIFS file-system description object1586 * @lnum: LEB number where node was written1587 *1588 * This function returns %0 on success and a negative error code on failure.1589 */1590static int dbg_check_ltab_lnum(struct ubifs_info *c, int lnum)1591{1592 int err, len = c->leb_size, dirty = 0, node_type, node_num, node_len;1593 int ret;1594 void *buf, *p;1595 1596 if (!dbg_is_chk_lprops(c))1597 return 0;1598 1599 buf = p = __vmalloc(c->leb_size, GFP_NOFS);1600 if (!buf) {1601 ubifs_err(c, "cannot allocate memory for ltab checking");1602 return 0;1603 }1604 1605 dbg_lp("LEB %d", lnum);1606 1607 err = ubifs_leb_read(c, lnum, buf, 0, c->leb_size, 1);1608 if (err)1609 goto out;1610 1611 while (1) {1612 if (!is_a_node(c, p, len)) {1613 int i, pad_len;1614 1615 pad_len = get_pad_len(c, p, len);1616 if (pad_len) {1617 p += pad_len;1618 len -= pad_len;1619 dirty += pad_len;1620 continue;1621 }1622 if (!dbg_is_all_ff(p, len)) {1623 ubifs_err(c, "invalid empty space in LEB %d at %d",1624 lnum, c->leb_size - len);1625 err = -EINVAL;1626 }1627 i = lnum - c->lpt_first;1628 if (len != c->ltab[i].free) {1629 ubifs_err(c, "invalid free space in LEB %d (free %d, expected %d)",1630 lnum, len, c->ltab[i].free);1631 err = -EINVAL;1632 }1633 if (dirty != c->ltab[i].dirty) {1634 ubifs_err(c, "invalid dirty space in LEB %d (dirty %d, expected %d)",1635 lnum, dirty, c->ltab[i].dirty);1636 err = -EINVAL;1637 }1638 goto out;1639 }1640 node_type = get_lpt_node_type(c, p, &node_num);1641 node_len = get_lpt_node_len(c, node_type);1642 ret = dbg_is_node_dirty(c, node_type, lnum, c->leb_size - len);1643 if (ret == 1)1644 dirty += node_len;1645 p += node_len;1646 len -= node_len;1647 }1648 1649out:1650 vfree(buf);1651 return err;1652}1653 1654/**1655 * dbg_check_ltab - check the free and dirty space in the ltab.1656 * @c: the UBIFS file-system description object1657 *1658 * This function returns %0 on success and a negative error code on failure.1659 */1660int dbg_check_ltab(struct ubifs_info *c)1661{1662 int lnum, err, i, cnt;1663 1664 if (!dbg_is_chk_lprops(c))1665 return 0;1666 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;1671 1672 pnode = ubifs_pnode_lookup(c, i);1673 if (IS_ERR(pnode))1674 return PTR_ERR(pnode);1675 cond_resched();1676 }1677 1678 /* Check nodes */1679 err = dbg_check_lpt_nodes(c, (struct ubifs_cnode *)c->nroot, 0, 0);1680 if (err)1681 return err;1682 1683 /* Check each LEB */1684 for (lnum = c->lpt_first; lnum <= c->lpt_last; lnum++) {1685 err = dbg_check_ltab_lnum(c, lnum);1686 if (err) {1687 ubifs_err(c, "failed at LEB %d", lnum);1688 return err;1689 }1690 }1691 1692 dbg_lp("succeeded");1693 return 0;1694}1695 1696/**1697 * dbg_chk_lpt_free_spc - check LPT free space is enough to write entire LPT.1698 * @c: the UBIFS file-system description object1699 *1700 * This function returns %0 on success and a negative error code on failure.1701 */1702int dbg_chk_lpt_free_spc(struct ubifs_info *c)1703{1704 long long free = 0;1705 int i;1706 1707 if (!dbg_is_chk_lprops(c))1708 return 0;1709 1710 for (i = 0; i < c->lpt_lebs; i++) {1711 if (c->ltab[i].tgc || c->ltab[i].cmt)1712 continue;1713 if (i + c->lpt_first == c->nhead_lnum)1714 free += c->leb_size - c->nhead_offs;1715 else if (c->ltab[i].free == c->leb_size)1716 free += c->leb_size;1717 }1718 if (free < c->lpt_sz) {1719 ubifs_err(c, "LPT space error: free %lld lpt_sz %lld",1720 free, c->lpt_sz);1721 ubifs_dump_lpt_info(c);1722 ubifs_dump_lpt_lebs(c);1723 dump_stack();1724 return -EINVAL;1725 }1726 return 0;1727}1728 1729/**1730 * dbg_chk_lpt_sz - check LPT does not write more than LPT size.1731 * @c: the UBIFS file-system description object1732 * @action: what to do1733 * @len: length written1734 *1735 * This function returns %0 on success and a negative error code on failure.1736 * The @action argument may be one of:1737 * o %0 - LPT debugging checking starts, initialize debugging variables;1738 * o %1 - wrote an LPT node, increase LPT size by @len bytes;1739 * o %2 - switched to a different LEB and wasted @len bytes;1740 * o %3 - check that we've written the right number of bytes.1741 * o %4 - wasted @len bytes;1742 */1743int dbg_chk_lpt_sz(struct ubifs_info *c, int action, int len)1744{1745 struct ubifs_debug_info *d = c->dbg;1746 long long chk_lpt_sz, lpt_sz;1747 int err = 0;1748 1749 if (!dbg_is_chk_lprops(c))1750 return 0;1751 1752 switch (action) {1753 case 0:1754 d->chk_lpt_sz = 0;1755 d->chk_lpt_sz2 = 0;1756 d->chk_lpt_lebs = 0;1757 d->chk_lpt_wastage = 0;1758 if (c->dirty_pn_cnt > c->pnode_cnt) {1759 ubifs_err(c, "dirty pnodes %d exceed max %d",1760 c->dirty_pn_cnt, c->pnode_cnt);1761 err = -EINVAL;1762 }1763 if (c->dirty_nn_cnt > c->nnode_cnt) {1764 ubifs_err(c, "dirty nnodes %d exceed max %d",1765 c->dirty_nn_cnt, c->nnode_cnt);1766 err = -EINVAL;1767 }1768 return err;1769 case 1:1770 d->chk_lpt_sz += len;1771 return 0;1772 case 2:1773 d->chk_lpt_sz += len;1774 d->chk_lpt_wastage += len;1775 d->chk_lpt_lebs += 1;1776 return 0;1777 case 3:1778 chk_lpt_sz = c->leb_size;1779 chk_lpt_sz *= d->chk_lpt_lebs;1780 chk_lpt_sz += len - c->nhead_offs;1781 if (d->chk_lpt_sz != chk_lpt_sz) {1782 ubifs_err(c, "LPT wrote %lld but space used was %lld",1783 d->chk_lpt_sz, chk_lpt_sz);1784 err = -EINVAL;1785 }1786 if (d->chk_lpt_sz > c->lpt_sz) {1787 ubifs_err(c, "LPT wrote %lld but lpt_sz is %lld",1788 d->chk_lpt_sz, c->lpt_sz);1789 err = -EINVAL;1790 }1791 if (d->chk_lpt_sz2 && d->chk_lpt_sz != d->chk_lpt_sz2) {1792 ubifs_err(c, "LPT layout size %lld but wrote %lld",1793 d->chk_lpt_sz, d->chk_lpt_sz2);1794 err = -EINVAL;1795 }1796 if (d->chk_lpt_sz2 && d->new_nhead_offs != len) {1797 ubifs_err(c, "LPT new nhead offs: expected %d was %d",1798 d->new_nhead_offs, len);1799 err = -EINVAL;1800 }1801 lpt_sz = (long long)c->pnode_cnt * c->pnode_sz;1802 lpt_sz += (long long)c->nnode_cnt * c->nnode_sz;1803 lpt_sz += c->ltab_sz;1804 if (c->big_lpt)1805 lpt_sz += c->lsave_sz;1806 if (d->chk_lpt_sz - d->chk_lpt_wastage > lpt_sz) {1807 ubifs_err(c, "LPT chk_lpt_sz %lld + waste %lld exceeds %lld",1808 d->chk_lpt_sz, d->chk_lpt_wastage, lpt_sz);1809 err = -EINVAL;1810 }1811 if (err) {1812 ubifs_dump_lpt_info(c);1813 ubifs_dump_lpt_lebs(c);1814 dump_stack();1815 }1816 d->chk_lpt_sz2 = d->chk_lpt_sz;1817 d->chk_lpt_sz = 0;1818 d->chk_lpt_wastage = 0;1819 d->chk_lpt_lebs = 0;1820 d->new_nhead_offs = len;1821 return err;1822 case 4:1823 d->chk_lpt_sz += len;1824 d->chk_lpt_wastage += len;1825 return 0;1826 default:1827 return -EINVAL;1828 }1829}1830 1831/**1832 * dump_lpt_leb - dump an LPT LEB.1833 * @c: UBIFS file-system description object1834 * @lnum: LEB number to dump1835 *1836 * This function dumps an LEB from LPT area. Nodes in this area are very1837 * different to nodes in the main area (e.g., they do not have common headers,1838 * they do not have 8-byte alignments, etc), so we have a separate function to1839 * dump LPT area LEBs. Note, LPT has to be locked by the caller.1840 */1841static void dump_lpt_leb(const struct ubifs_info *c, int lnum)1842{1843 int err, len = c->leb_size, node_type, node_num, node_len, offs;1844 void *buf, *p;1845 1846 pr_err("(pid %d) start dumping LEB %d\n", current->pid, lnum);1847 buf = p = __vmalloc(c->leb_size, GFP_NOFS);1848 if (!buf) {1849 ubifs_err(c, "cannot allocate memory to dump LPT");1850 return;1851 }1852 1853 err = ubifs_leb_read(c, lnum, buf, 0, c->leb_size, 1);1854 if (err)1855 goto out;1856 1857 while (1) {1858 offs = c->leb_size - len;1859 if (!is_a_node(c, p, len)) {1860 int pad_len;1861 1862 pad_len = get_pad_len(c, p, len);1863 if (pad_len) {1864 pr_err("LEB %d:%d, pad %d bytes\n",1865 lnum, offs, pad_len);1866 p += pad_len;1867 len -= pad_len;1868 continue;1869 }1870 if (len)1871 pr_err("LEB %d:%d, free %d bytes\n",1872 lnum, offs, len);1873 break;1874 }1875 1876 node_type = get_lpt_node_type(c, p, &node_num);1877 switch (node_type) {1878 case UBIFS_LPT_PNODE:1879 {1880 node_len = c->pnode_sz;1881 if (c->big_lpt)1882 pr_err("LEB %d:%d, pnode num %d\n",1883 lnum, offs, node_num);1884 else1885 pr_err("LEB %d:%d, pnode\n", lnum, offs);1886 break;1887 }1888 case UBIFS_LPT_NNODE:1889 {1890 int i;1891 struct ubifs_nnode nnode;1892 1893 node_len = c->nnode_sz;1894 if (c->big_lpt)1895 pr_err("LEB %d:%d, nnode num %d, ",1896 lnum, offs, node_num);1897 else1898 pr_err("LEB %d:%d, nnode, ",1899 lnum, offs);1900 err = ubifs_unpack_nnode(c, p, &nnode);1901 if (err) {1902 pr_err("failed to unpack_node, error %d\n",1903 err);1904 break;1905 }1906 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {1907 pr_cont("%d:%d", nnode.nbranch[i].lnum,1908 nnode.nbranch[i].offs);1909 if (i != UBIFS_LPT_FANOUT - 1)1910 pr_cont(", ");1911 }1912 pr_cont("\n");1913 break;1914 }1915 case UBIFS_LPT_LTAB:1916 node_len = c->ltab_sz;1917 pr_err("LEB %d:%d, ltab\n", lnum, offs);1918 break;1919 case UBIFS_LPT_LSAVE:1920 node_len = c->lsave_sz;1921 pr_err("LEB %d:%d, lsave len\n", lnum, offs);1922 break;1923 default:1924 ubifs_err(c, "LPT node type %d not recognized", node_type);1925 goto out;1926 }1927 1928 p += node_len;1929 len -= node_len;1930 }1931 1932 pr_err("(pid %d) finish dumping LEB %d\n", current->pid, lnum);1933out:1934 vfree(buf);1935 return;1936}1937 1938/**1939 * ubifs_dump_lpt_lebs - dump LPT lebs.1940 * @c: UBIFS file-system description object1941 *1942 * This function dumps all LPT LEBs. The caller has to make sure the LPT is1943 * locked.1944 */1945void ubifs_dump_lpt_lebs(const struct ubifs_info *c)1946{1947 int i;1948 1949 pr_err("(pid %d) start dumping all LPT LEBs\n", current->pid);1950 for (i = 0; i < c->lpt_lebs; i++)1951 dump_lpt_leb(c, i + c->lpt_first);1952 pr_err("(pid %d) finish dumping all LPT LEBs\n", current->pid);1953}1954 1955/**1956 * dbg_populate_lsave - debugging version of 'populate_lsave()'1957 * @c: UBIFS file-system description object1958 *1959 * This is a debugging version for 'populate_lsave()' which populates lsave1960 * with random LEBs instead of useful LEBs, which is good for test coverage.1961 * Returns zero if lsave has not been populated (this debugging feature is1962 * disabled) an non-zero if lsave has been populated.1963 */1964static int dbg_populate_lsave(struct ubifs_info *c)1965{1966 struct ubifs_lprops *lprops;1967 struct ubifs_lpt_heap *heap;1968 int i;1969 1970 if (!dbg_is_chk_gen(c))1971 return 0;1972 if (get_random_u32_below(4))1973 return 0;1974 1975 for (i = 0; i < c->lsave_cnt; i++)1976 c->lsave[i] = c->main_first;1977 1978 list_for_each_entry(lprops, &c->empty_list, list)1979 c->lsave[get_random_u32_below(c->lsave_cnt)] = lprops->lnum;1980 list_for_each_entry(lprops, &c->freeable_list, list)1981 c->lsave[get_random_u32_below(c->lsave_cnt)] = lprops->lnum;1982 list_for_each_entry(lprops, &c->frdi_idx_list, list)1983 c->lsave[get_random_u32_below(c->lsave_cnt)] = lprops->lnum;1984 1985 heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];1986 for (i = 0; i < heap->cnt; i++)1987 c->lsave[get_random_u32_below(c->lsave_cnt)] = heap->arr[i]->lnum;1988 heap = &c->lpt_heap[LPROPS_DIRTY - 1];1989 for (i = 0; i < heap->cnt; i++)1990 c->lsave[get_random_u32_below(c->lsave_cnt)] = heap->arr[i]->lnum;1991 heap = &c->lpt_heap[LPROPS_FREE - 1];1992 for (i = 0; i < heap->cnt; i++)1993 c->lsave[get_random_u32_below(c->lsave_cnt)] = heap->arr[i]->lnum;1994 1995 return 1;1996}1997