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