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