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 * Author: Adrian Hunter 20 */ 21 22 #include "ubifs.h" 23 24 /* 25 * An orphan is an inode number whose inode node has been committed to the index 26 * with a link count of zero. That happens when an open file is deleted 27 * (unlinked) and then a commit is run. In the normal course of events the inode 28 * would be deleted when the file is closed. However in the case of an unclean 29 * unmount, orphans need to be accounted for. After an unclean unmount, the 30 * orphans' inodes must be deleted which means either scanning the entire index 31 * looking for them, or keeping a list on flash somewhere. This unit implements 32 * the latter approach. 33 * 34 * The orphan area is a fixed number of LEBs situated between the LPT area and 35 * the main area. The number of orphan area LEBs is specified when the file 36 * system is created. The minimum number is 1. The size of the orphan area 37 * should be so that it can hold the maximum number of orphans that are expected 38 * to ever exist at one time. 39 * 40 * The number of orphans that can fit in a LEB is: 41 * 42 * (c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64) 43 * 44 * For example: a 15872 byte LEB can fit 1980 orphans so 1 LEB may be enough. 45 * 46 * Orphans are accumulated in a rb-tree. When an inode's link count drops to 47 * zero, the inode number is added to the rb-tree. It is removed from the tree 48 * when the inode is deleted. Any new orphans that are in the orphan tree when 49 * the commit is run, are written to the orphan area in 1 or more orphan nodes. 50 * If the orphan area is full, it is consolidated to make space. There is 51 * always enough space because validation prevents the user from creating more 52 * than the maximum number of orphans allowed. 53 */ 54 55 static int dbg_check_orphans(struct ubifs_info *c); 56 57 /** 58 * ubifs_add_orphan - add an orphan. 59 * @c: UBIFS file-system description object 60 * @inum: orphan inode number 61 * 62 * Add an orphan. This function is called when an inodes link count drops to 63 * zero. 64 */ 65 int ubifs_add_orphan(struct ubifs_info *c, ino_t inum) 66 { 67 struct ubifs_orphan *orphan, *o; 68 struct rb_node **p, *parent = NULL; 69 70 orphan = kzalloc(sizeof(struct ubifs_orphan), GFP_NOFS); 71 if (!orphan) 72 return -ENOMEM; 73 orphan->inum = inum; 74 orphan->new = 1; 75 76 spin_lock(&c->orphan_lock); 77 if (c->tot_orphans >= c->max_orphans) { 78 spin_unlock(&c->orphan_lock); 79 kfree(orphan); 80 return -ENFILE; 81 } 82 p = &c->orph_tree.rb_node; 83 while (*p) { 84 parent = *p; 85 o = rb_entry(parent, struct ubifs_orphan, rb); 86 if (inum < o->inum) 87 p = &(*p)->rb_left; 88 else if (inum > o->inum) 89 p = &(*p)->rb_right; 90 else { 91 ubifs_err("orphaned twice"); 92 spin_unlock(&c->orphan_lock); 93 kfree(orphan); 94 return 0; 95 } 96 } 97 c->tot_orphans += 1; 98 c->new_orphans += 1; 99 rb_link_node(&orphan->rb, parent, p); 100 rb_insert_color(&orphan->rb, &c->orph_tree); 101 list_add_tail(&orphan->list, &c->orph_list); 102 list_add_tail(&orphan->new_list, &c->orph_new); 103 spin_unlock(&c->orphan_lock); 104 dbg_gen("ino %lu", (unsigned long)inum); 105 return 0; 106 } 107 108 /** 109 * ubifs_delete_orphan - delete an orphan. 110 * @c: UBIFS file-system description object 111 * @inum: orphan inode number 112 * 113 * Delete an orphan. This function is called when an inode is deleted. 114 */ 115 void ubifs_delete_orphan(struct ubifs_info *c, ino_t inum) 116 { 117 struct ubifs_orphan *o; 118 struct rb_node *p; 119 120 spin_lock(&c->orphan_lock); 121 p = c->orph_tree.rb_node; 122 while (p) { 123 o = rb_entry(p, struct ubifs_orphan, rb); 124 if (inum < o->inum) 125 p = p->rb_left; 126 else if (inum > o->inum) 127 p = p->rb_right; 128 else { 129 if (o->dnext) { 130 spin_unlock(&c->orphan_lock); 131 dbg_gen("deleted twice ino %lu", 132 (unsigned long)inum); 133 return; 134 } 135 if (o->cnext) { 136 o->dnext = c->orph_dnext; 137 c->orph_dnext = o; 138 spin_unlock(&c->orphan_lock); 139 dbg_gen("delete later ino %lu", 140 (unsigned long)inum); 141 return; 142 } 143 rb_erase(p, &c->orph_tree); 144 list_del(&o->list); 145 c->tot_orphans -= 1; 146 if (o->new) { 147 list_del(&o->new_list); 148 c->new_orphans -= 1; 149 } 150 spin_unlock(&c->orphan_lock); 151 kfree(o); 152 dbg_gen("inum %lu", (unsigned long)inum); 153 return; 154 } 155 } 156 spin_unlock(&c->orphan_lock); 157 ubifs_err("missing orphan ino %lu", (unsigned long)inum); 158 dump_stack(); 159 } 160 161 /** 162 * ubifs_orphan_start_commit - start commit of orphans. 163 * @c: UBIFS file-system description object 164 * 165 * Start commit of orphans. 166 */ 167 int ubifs_orphan_start_commit(struct ubifs_info *c) 168 { 169 struct ubifs_orphan *orphan, **last; 170 171 spin_lock(&c->orphan_lock); 172 last = &c->orph_cnext; 173 list_for_each_entry(orphan, &c->orph_new, new_list) { 174 ubifs_assert(orphan->new); 175 orphan->new = 0; 176 *last = orphan; 177 last = &orphan->cnext; 178 } 179 *last = orphan->cnext; 180 c->cmt_orphans = c->new_orphans; 181 c->new_orphans = 0; 182 dbg_cmt("%d orphans to commit", c->cmt_orphans); 183 INIT_LIST_HEAD(&c->orph_new); 184 if (c->tot_orphans == 0) 185 c->no_orphs = 1; 186 else 187 c->no_orphs = 0; 188 spin_unlock(&c->orphan_lock); 189 return 0; 190 } 191 192 /** 193 * avail_orphs - calculate available space. 194 * @c: UBIFS file-system description object 195 * 196 * This function returns the number of orphans that can be written in the 197 * available space. 198 */ 199 static int avail_orphs(struct ubifs_info *c) 200 { 201 int avail_lebs, avail, gap; 202 203 avail_lebs = c->orph_lebs - (c->ohead_lnum - c->orph_first) - 1; 204 avail = avail_lebs * 205 ((c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64)); 206 gap = c->leb_size - c->ohead_offs; 207 if (gap >= UBIFS_ORPH_NODE_SZ + sizeof(__le64)) 208 avail += (gap - UBIFS_ORPH_NODE_SZ) / sizeof(__le64); 209 return avail; 210 } 211 212 /** 213 * tot_avail_orphs - calculate total space. 214 * @c: UBIFS file-system description object 215 * 216 * This function returns the number of orphans that can be written in half 217 * the total space. That leaves half the space for adding new orphans. 218 */ 219 static int tot_avail_orphs(struct ubifs_info *c) 220 { 221 int avail_lebs, avail; 222 223 avail_lebs = c->orph_lebs; 224 avail = avail_lebs * 225 ((c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64)); 226 return avail / 2; 227 } 228 229 /** 230 * do_write_orph_node - write a node to the orphan head. 231 * @c: UBIFS file-system description object 232 * @len: length of node 233 * @atomic: write atomically 234 * 235 * This function writes a node to the orphan head from the orphan buffer. If 236 * %atomic is not zero, then the write is done atomically. On success, %0 is 237 * returned, otherwise a negative error code is returned. 238 */ 239 static int do_write_orph_node(struct ubifs_info *c, int len, int atomic) 240 { 241 int err = 0; 242 243 if (atomic) { 244 ubifs_assert(c->ohead_offs == 0); 245 ubifs_prepare_node(c, c->orph_buf, len, 1); 246 len = ALIGN(len, c->min_io_size); 247 err = ubifs_leb_change(c, c->ohead_lnum, c->orph_buf, len); 248 } else { 249 if (c->ohead_offs == 0) { 250 /* Ensure LEB has been unmapped */ 251 err = ubifs_leb_unmap(c, c->ohead_lnum); 252 if (err) 253 return err; 254 } 255 err = ubifs_write_node(c, c->orph_buf, len, c->ohead_lnum, 256 c->ohead_offs); 257 } 258 return err; 259 } 260 261 /** 262 * write_orph_node - write an orphan node. 263 * @c: UBIFS file-system description object 264 * @atomic: write atomically 265 * 266 * This function builds an orphan node from the cnext list and writes it to the 267 * orphan head. On success, %0 is returned, otherwise a negative error code 268 * is returned. 269 */ 270 static int write_orph_node(struct ubifs_info *c, int atomic) 271 { 272 struct ubifs_orphan *orphan, *cnext; 273 struct ubifs_orph_node *orph; 274 int gap, err, len, cnt, i; 275 276 ubifs_assert(c->cmt_orphans > 0); 277 gap = c->leb_size - c->ohead_offs; 278 if (gap < UBIFS_ORPH_NODE_SZ + sizeof(__le64)) { 279 c->ohead_lnum += 1; 280 c->ohead_offs = 0; 281 gap = c->leb_size; 282 if (c->ohead_lnum > c->orph_last) { 283 /* 284 * We limit the number of orphans so that this should 285 * never happen. 286 */ 287 ubifs_err("out of space in orphan area"); 288 return -EINVAL; 289 } 290 } 291 cnt = (gap - UBIFS_ORPH_NODE_SZ) / sizeof(__le64); 292 if (cnt > c->cmt_orphans) 293 cnt = c->cmt_orphans; 294 len = UBIFS_ORPH_NODE_SZ + cnt * sizeof(__le64); 295 ubifs_assert(c->orph_buf); 296 orph = c->orph_buf; 297 orph->ch.node_type = UBIFS_ORPH_NODE; 298 spin_lock(&c->orphan_lock); 299 cnext = c->orph_cnext; 300 for (i = 0; i < cnt; i++) { 301 orphan = cnext; 302 orph->inos[i] = cpu_to_le64(orphan->inum); 303 cnext = orphan->cnext; 304 orphan->cnext = NULL; 305 } 306 c->orph_cnext = cnext; 307 c->cmt_orphans -= cnt; 308 spin_unlock(&c->orphan_lock); 309 if (c->cmt_orphans) 310 orph->cmt_no = cpu_to_le64(c->cmt_no); 311 else 312 /* Mark the last node of the commit */ 313 orph->cmt_no = cpu_to_le64((c->cmt_no) | (1ULL << 63)); 314 ubifs_assert(c->ohead_offs + len <= c->leb_size); 315 ubifs_assert(c->ohead_lnum >= c->orph_first); 316 ubifs_assert(c->ohead_lnum <= c->orph_last); 317 err = do_write_orph_node(c, len, atomic); 318 c->ohead_offs += ALIGN(len, c->min_io_size); 319 c->ohead_offs = ALIGN(c->ohead_offs, 8); 320 return err; 321 } 322 323 /** 324 * write_orph_nodes - write orphan nodes until there are no more to commit. 325 * @c: UBIFS file-system description object 326 * @atomic: write atomically 327 * 328 * This function writes orphan nodes for all the orphans to commit. On success, 329 * %0 is returned, otherwise a negative error code is returned. 330 */ 331 static int write_orph_nodes(struct ubifs_info *c, int atomic) 332 { 333 int err; 334 335 while (c->cmt_orphans > 0) { 336 err = write_orph_node(c, atomic); 337 if (err) 338 return err; 339 } 340 if (atomic) { 341 int lnum; 342 343 /* Unmap any unused LEBs after consolidation */ 344 lnum = c->ohead_lnum + 1; 345 for (lnum = c->ohead_lnum + 1; lnum <= c->orph_last; lnum++) { 346 err = ubifs_leb_unmap(c, lnum); 347 if (err) 348 return err; 349 } 350 } 351 return 0; 352 } 353 354 /** 355 * consolidate - consolidate the orphan area. 356 * @c: UBIFS file-system description object 357 * 358 * This function enables consolidation by putting all the orphans into the list 359 * to commit. The list is in the order that the orphans were added, and the 360 * LEBs are written atomically in order, so at no time can orphans be lost by 361 * an unclean unmount. 362 * 363 * This function returns %0 on success and a negative error code on failure. 364 */ 365 static int consolidate(struct ubifs_info *c) 366 { 367 int tot_avail = tot_avail_orphs(c), err = 0; 368 369 spin_lock(&c->orphan_lock); 370 dbg_cmt("there is space for %d orphans and there are %d", 371 tot_avail, c->tot_orphans); 372 if (c->tot_orphans - c->new_orphans <= tot_avail) { 373 struct ubifs_orphan *orphan, **last; 374 int cnt = 0; 375 376 /* Change the cnext list to include all non-new orphans */ 377 last = &c->orph_cnext; 378 list_for_each_entry(orphan, &c->orph_list, list) { 379 if (orphan->new) 380 continue; 381 *last = orphan; 382 last = &orphan->cnext; 383 cnt += 1; 384 } 385 *last = orphan->cnext; 386 ubifs_assert(cnt == c->tot_orphans - c->new_orphans); 387 c->cmt_orphans = cnt; 388 c->ohead_lnum = c->orph_first; 389 c->ohead_offs = 0; 390 } else { 391 /* 392 * We limit the number of orphans so that this should 393 * never happen. 394 */ 395 ubifs_err("out of space in orphan area"); 396 err = -EINVAL; 397 } 398 spin_unlock(&c->orphan_lock); 399 return err; 400 } 401 402 /** 403 * commit_orphans - commit orphans. 404 * @c: UBIFS file-system description object 405 * 406 * This function commits orphans to flash. On success, %0 is returned, 407 * otherwise a negative error code is returned. 408 */ 409 static int commit_orphans(struct ubifs_info *c) 410 { 411 int avail, atomic = 0, err; 412 413 ubifs_assert(c->cmt_orphans > 0); 414 avail = avail_orphs(c); 415 if (avail < c->cmt_orphans) { 416 /* Not enough space to write new orphans, so consolidate */ 417 err = consolidate(c); 418 if (err) 419 return err; 420 atomic = 1; 421 } 422 err = write_orph_nodes(c, atomic); 423 return err; 424 } 425 426 /** 427 * erase_deleted - erase the orphans marked for deletion. 428 * @c: UBIFS file-system description object 429 * 430 * During commit, the orphans being committed cannot be deleted, so they are 431 * marked for deletion and deleted by this function. Also, the recovery 432 * adds killed orphans to the deletion list, and therefore they are deleted 433 * here too. 434 */ 435 static void erase_deleted(struct ubifs_info *c) 436 { 437 struct ubifs_orphan *orphan, *dnext; 438 439 spin_lock(&c->orphan_lock); 440 dnext = c->orph_dnext; 441 while (dnext) { 442 orphan = dnext; 443 dnext = orphan->dnext; 444 ubifs_assert(!orphan->new); 445 rb_erase(&orphan->rb, &c->orph_tree); 446 list_del(&orphan->list); 447 c->tot_orphans -= 1; 448 dbg_gen("deleting orphan ino %lu", (unsigned long)orphan->inum); 449 kfree(orphan); 450 } 451 c->orph_dnext = NULL; 452 spin_unlock(&c->orphan_lock); 453 } 454 455 /** 456 * ubifs_orphan_end_commit - end commit of orphans. 457 * @c: UBIFS file-system description object 458 * 459 * End commit of orphans. 460 */ 461 int ubifs_orphan_end_commit(struct ubifs_info *c) 462 { 463 int err; 464 465 if (c->cmt_orphans != 0) { 466 err = commit_orphans(c); 467 if (err) 468 return err; 469 } 470 erase_deleted(c); 471 err = dbg_check_orphans(c); 472 return err; 473 } 474 475 /** 476 * ubifs_clear_orphans - erase all LEBs used for orphans. 477 * @c: UBIFS file-system description object 478 * 479 * If recovery is not required, then the orphans from the previous session 480 * are not needed. This function locates the LEBs used to record 481 * orphans, and un-maps them. 482 */ 483 int ubifs_clear_orphans(struct ubifs_info *c) 484 { 485 int lnum, err; 486 487 for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) { 488 err = ubifs_leb_unmap(c, lnum); 489 if (err) 490 return err; 491 } 492 c->ohead_lnum = c->orph_first; 493 c->ohead_offs = 0; 494 return 0; 495 } 496 497 /** 498 * insert_dead_orphan - insert an orphan. 499 * @c: UBIFS file-system description object 500 * @inum: orphan inode number 501 * 502 * This function is a helper to the 'do_kill_orphans()' function. The orphan 503 * must be kept until the next commit, so it is added to the rb-tree and the 504 * deletion list. 505 */ 506 static int insert_dead_orphan(struct ubifs_info *c, ino_t inum) 507 { 508 struct ubifs_orphan *orphan, *o; 509 struct rb_node **p, *parent = NULL; 510 511 orphan = kzalloc(sizeof(struct ubifs_orphan), GFP_KERNEL); 512 if (!orphan) 513 return -ENOMEM; 514 orphan->inum = inum; 515 516 p = &c->orph_tree.rb_node; 517 while (*p) { 518 parent = *p; 519 o = rb_entry(parent, struct ubifs_orphan, rb); 520 if (inum < o->inum) 521 p = &(*p)->rb_left; 522 else if (inum > o->inum) 523 p = &(*p)->rb_right; 524 else { 525 /* Already added - no problem */ 526 kfree(orphan); 527 return 0; 528 } 529 } 530 c->tot_orphans += 1; 531 rb_link_node(&orphan->rb, parent, p); 532 rb_insert_color(&orphan->rb, &c->orph_tree); 533 list_add_tail(&orphan->list, &c->orph_list); 534 orphan->dnext = c->orph_dnext; 535 c->orph_dnext = orphan; 536 dbg_mnt("ino %lu, new %d, tot %d", (unsigned long)inum, 537 c->new_orphans, c->tot_orphans); 538 return 0; 539 } 540 541 /** 542 * do_kill_orphans - remove orphan inodes from the index. 543 * @c: UBIFS file-system description object 544 * @sleb: scanned LEB 545 * @last_cmt_no: cmt_no of last orphan node read is passed and returned here 546 * @outofdate: whether the LEB is out of date is returned here 547 * @last_flagged: whether the end orphan node is encountered 548 * 549 * This function is a helper to the 'kill_orphans()' function. It goes through 550 * every orphan node in a LEB and for every inode number recorded, removes 551 * all keys for that inode from the TNC. 552 */ 553 static int do_kill_orphans(struct ubifs_info *c, struct ubifs_scan_leb *sleb, 554 unsigned long long *last_cmt_no, int *outofdate, 555 int *last_flagged) 556 { 557 struct ubifs_scan_node *snod; 558 struct ubifs_orph_node *orph; 559 unsigned long long cmt_no; 560 ino_t inum; 561 int i, n, err, first = 1; 562 563 list_for_each_entry(snod, &sleb->nodes, list) { 564 if (snod->type != UBIFS_ORPH_NODE) { 565 ubifs_err("invalid node type %d in orphan area at " 566 "%d:%d", snod->type, sleb->lnum, snod->offs); 567 ubifs_dump_node(c, snod->node); 568 return -EINVAL; 569 } 570 571 orph = snod->node; 572 573 /* Check commit number */ 574 cmt_no = le64_to_cpu(orph->cmt_no) & LLONG_MAX; 575 /* 576 * The commit number on the master node may be less, because 577 * of a failed commit. If there are several failed commits in a 578 * row, the commit number written on orphan nodes will continue 579 * to increase (because the commit number is adjusted here) even 580 * though the commit number on the master node stays the same 581 * because the master node has not been re-written. 582 */ 583 if (cmt_no > c->cmt_no) 584 c->cmt_no = cmt_no; 585 if (cmt_no < *last_cmt_no && *last_flagged) { 586 /* 587 * The last orphan node had a higher commit number and 588 * was flagged as the last written for that commit 589 * number. That makes this orphan node, out of date. 590 */ 591 if (!first) { 592 ubifs_err("out of order commit number %llu in " 593 "orphan node at %d:%d", 594 cmt_no, sleb->lnum, snod->offs); 595 ubifs_dump_node(c, snod->node); 596 return -EINVAL; 597 } 598 dbg_rcvry("out of date LEB %d", sleb->lnum); 599 *outofdate = 1; 600 return 0; 601 } 602 603 if (first) 604 first = 0; 605 606 n = (le32_to_cpu(orph->ch.len) - UBIFS_ORPH_NODE_SZ) >> 3; 607 for (i = 0; i < n; i++) { 608 inum = le64_to_cpu(orph->inos[i]); 609 dbg_rcvry("deleting orphaned inode %lu", 610 (unsigned long)inum); 611 err = ubifs_tnc_remove_ino(c, inum); 612 if (err) 613 return err; 614 err = insert_dead_orphan(c, inum); 615 if (err) 616 return err; 617 } 618 619 *last_cmt_no = cmt_no; 620 if (le64_to_cpu(orph->cmt_no) & (1ULL << 63)) { 621 dbg_rcvry("last orph node for commit %llu at %d:%d", 622 cmt_no, sleb->lnum, snod->offs); 623 *last_flagged = 1; 624 } else 625 *last_flagged = 0; 626 } 627 628 return 0; 629 } 630 631 /** 632 * kill_orphans - remove all orphan inodes from the index. 633 * @c: UBIFS file-system description object 634 * 635 * If recovery is required, then orphan inodes recorded during the previous 636 * session (which ended with an unclean unmount) must be deleted from the index. 637 * This is done by updating the TNC, but since the index is not updated until 638 * the next commit, the LEBs where the orphan information is recorded are not 639 * erased until the next commit. 640 */ 641 static int kill_orphans(struct ubifs_info *c) 642 { 643 unsigned long long last_cmt_no = 0; 644 int lnum, err = 0, outofdate = 0, last_flagged = 0; 645 646 c->ohead_lnum = c->orph_first; 647 c->ohead_offs = 0; 648 /* Check no-orphans flag and skip this if no orphans */ 649 if (c->no_orphs) { 650 dbg_rcvry("no orphans"); 651 return 0; 652 } 653 /* 654 * Orph nodes always start at c->orph_first and are written to each 655 * successive LEB in turn. Generally unused LEBs will have been unmapped 656 * but may contain out of date orphan nodes if the unmap didn't go 657 * through. In addition, the last orphan node written for each commit is 658 * marked (top bit of orph->cmt_no is set to 1). It is possible that 659 * there are orphan nodes from the next commit (i.e. the commit did not 660 * complete successfully). In that case, no orphans will have been lost 661 * due to the way that orphans are written, and any orphans added will 662 * be valid orphans anyway and so can be deleted. 663 */ 664 for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) { 665 struct ubifs_scan_leb *sleb; 666 667 dbg_rcvry("LEB %d", lnum); 668 sleb = ubifs_scan(c, lnum, 0, c->sbuf, 1); 669 if (IS_ERR(sleb)) { 670 if (PTR_ERR(sleb) == -EUCLEAN) 671 sleb = ubifs_recover_leb(c, lnum, 0, 672 c->sbuf, -1); 673 if (IS_ERR(sleb)) { 674 err = PTR_ERR(sleb); 675 break; 676 } 677 } 678 err = do_kill_orphans(c, sleb, &last_cmt_no, &outofdate, 679 &last_flagged); 680 if (err || outofdate) { 681 ubifs_scan_destroy(sleb); 682 break; 683 } 684 if (sleb->endpt) { 685 c->ohead_lnum = lnum; 686 c->ohead_offs = sleb->endpt; 687 } 688 ubifs_scan_destroy(sleb); 689 } 690 return err; 691 } 692 693 /** 694 * ubifs_mount_orphans - delete orphan inodes and erase LEBs that recorded them. 695 * @c: UBIFS file-system description object 696 * @unclean: indicates recovery from unclean unmount 697 * @read_only: indicates read only mount 698 * 699 * This function is called when mounting to erase orphans from the previous 700 * session. If UBIFS was not unmounted cleanly, then the inodes recorded as 701 * orphans are deleted. 702 */ 703 int ubifs_mount_orphans(struct ubifs_info *c, int unclean, int read_only) 704 { 705 int err = 0; 706 707 c->max_orphans = tot_avail_orphs(c); 708 709 if (!read_only) { 710 c->orph_buf = vmalloc(c->leb_size); 711 if (!c->orph_buf) 712 return -ENOMEM; 713 } 714 715 if (unclean) 716 err = kill_orphans(c); 717 else if (!read_only) 718 err = ubifs_clear_orphans(c); 719 720 return err; 721 } 722 723 /* 724 * Everything below is related to debugging. 725 */ 726 727 struct check_orphan { 728 struct rb_node rb; 729 ino_t inum; 730 }; 731 732 struct check_info { 733 unsigned long last_ino; 734 unsigned long tot_inos; 735 unsigned long missing; 736 unsigned long long leaf_cnt; 737 struct ubifs_ino_node *node; 738 struct rb_root root; 739 }; 740 741 static int dbg_find_orphan(struct ubifs_info *c, ino_t inum) 742 { 743 struct ubifs_orphan *o; 744 struct rb_node *p; 745 746 spin_lock(&c->orphan_lock); 747 p = c->orph_tree.rb_node; 748 while (p) { 749 o = rb_entry(p, struct ubifs_orphan, rb); 750 if (inum < o->inum) 751 p = p->rb_left; 752 else if (inum > o->inum) 753 p = p->rb_right; 754 else { 755 spin_unlock(&c->orphan_lock); 756 return 1; 757 } 758 } 759 spin_unlock(&c->orphan_lock); 760 return 0; 761 } 762 763 static int dbg_ins_check_orphan(struct rb_root *root, ino_t inum) 764 { 765 struct check_orphan *orphan, *o; 766 struct rb_node **p, *parent = NULL; 767 768 orphan = kzalloc(sizeof(struct check_orphan), GFP_NOFS); 769 if (!orphan) 770 return -ENOMEM; 771 orphan->inum = inum; 772 773 p = &root->rb_node; 774 while (*p) { 775 parent = *p; 776 o = rb_entry(parent, struct check_orphan, rb); 777 if (inum < o->inum) 778 p = &(*p)->rb_left; 779 else if (inum > o->inum) 780 p = &(*p)->rb_right; 781 else { 782 kfree(orphan); 783 return 0; 784 } 785 } 786 rb_link_node(&orphan->rb, parent, p); 787 rb_insert_color(&orphan->rb, root); 788 return 0; 789 } 790 791 static int dbg_find_check_orphan(struct rb_root *root, ino_t inum) 792 { 793 struct check_orphan *o; 794 struct rb_node *p; 795 796 p = root->rb_node; 797 while (p) { 798 o = rb_entry(p, struct check_orphan, rb); 799 if (inum < o->inum) 800 p = p->rb_left; 801 else if (inum > o->inum) 802 p = p->rb_right; 803 else 804 return 1; 805 } 806 return 0; 807 } 808 809 static void dbg_free_check_tree(struct rb_root *root) 810 { 811 struct rb_node *this = root->rb_node; 812 struct check_orphan *o; 813 814 while (this) { 815 if (this->rb_left) { 816 this = this->rb_left; 817 continue; 818 } else if (this->rb_right) { 819 this = this->rb_right; 820 continue; 821 } 822 o = rb_entry(this, struct check_orphan, rb); 823 this = rb_parent(this); 824 if (this) { 825 if (this->rb_left == &o->rb) 826 this->rb_left = NULL; 827 else 828 this->rb_right = NULL; 829 } 830 kfree(o); 831 } 832 } 833 834 static int dbg_orphan_check(struct ubifs_info *c, struct ubifs_zbranch *zbr, 835 void *priv) 836 { 837 struct check_info *ci = priv; 838 ino_t inum; 839 int err; 840 841 inum = key_inum(c, &zbr->key); 842 if (inum != ci->last_ino) { 843 /* Lowest node type is the inode node, so it comes first */ 844 if (key_type(c, &zbr->key) != UBIFS_INO_KEY) 845 ubifs_err("found orphan node ino %lu, type %d", 846 (unsigned long)inum, key_type(c, &zbr->key)); 847 ci->last_ino = inum; 848 ci->tot_inos += 1; 849 err = ubifs_tnc_read_node(c, zbr, ci->node); 850 if (err) { 851 ubifs_err("node read failed, error %d", err); 852 return err; 853 } 854 if (ci->node->nlink == 0) 855 /* Must be recorded as an orphan */ 856 if (!dbg_find_check_orphan(&ci->root, inum) && 857 !dbg_find_orphan(c, inum)) { 858 ubifs_err("missing orphan, ino %lu", 859 (unsigned long)inum); 860 ci->missing += 1; 861 } 862 } 863 ci->leaf_cnt += 1; 864 return 0; 865 } 866 867 static int dbg_read_orphans(struct check_info *ci, struct ubifs_scan_leb *sleb) 868 { 869 struct ubifs_scan_node *snod; 870 struct ubifs_orph_node *orph; 871 ino_t inum; 872 int i, n, err; 873 874 list_for_each_entry(snod, &sleb->nodes, list) { 875 cond_resched(); 876 if (snod->type != UBIFS_ORPH_NODE) 877 continue; 878 orph = snod->node; 879 n = (le32_to_cpu(orph->ch.len) - UBIFS_ORPH_NODE_SZ) >> 3; 880 for (i = 0; i < n; i++) { 881 inum = le64_to_cpu(orph->inos[i]); 882 err = dbg_ins_check_orphan(&ci->root, inum); 883 if (err) 884 return err; 885 } 886 } 887 return 0; 888 } 889 890 static int dbg_scan_orphans(struct ubifs_info *c, struct check_info *ci) 891 { 892 int lnum, err = 0; 893 void *buf; 894 895 /* Check no-orphans flag and skip this if no orphans */ 896 if (c->no_orphs) 897 return 0; 898 899 buf = __vmalloc(c->leb_size, GFP_NOFS, PAGE_KERNEL); 900 if (!buf) { 901 ubifs_err("cannot allocate memory to check orphans"); 902 return 0; 903 } 904 905 for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) { 906 struct ubifs_scan_leb *sleb; 907 908 sleb = ubifs_scan(c, lnum, 0, buf, 0); 909 if (IS_ERR(sleb)) { 910 err = PTR_ERR(sleb); 911 break; 912 } 913 914 err = dbg_read_orphans(ci, sleb); 915 ubifs_scan_destroy(sleb); 916 if (err) 917 break; 918 } 919 920 vfree(buf); 921 return err; 922 } 923 924 static int dbg_check_orphans(struct ubifs_info *c) 925 { 926 struct check_info ci; 927 int err; 928 929 if (!dbg_is_chk_orph(c)) 930 return 0; 931 932 ci.last_ino = 0; 933 ci.tot_inos = 0; 934 ci.missing = 0; 935 ci.leaf_cnt = 0; 936 ci.root = RB_ROOT; 937 ci.node = kmalloc(UBIFS_MAX_INO_NODE_SZ, GFP_NOFS); 938 if (!ci.node) { 939 ubifs_err("out of memory"); 940 return -ENOMEM; 941 } 942 943 err = dbg_scan_orphans(c, &ci); 944 if (err) 945 goto out; 946 947 err = dbg_walk_index(c, &dbg_orphan_check, NULL, &ci); 948 if (err) { 949 ubifs_err("cannot scan TNC, error %d", err); 950 goto out; 951 } 952 953 if (ci.missing) { 954 ubifs_err("%lu missing orphan(s)", ci.missing); 955 err = -EINVAL; 956 goto out; 957 } 958 959 dbg_cmt("last inode number is %lu", ci.last_ino); 960 dbg_cmt("total number of inodes is %lu", ci.tot_inos); 961 dbg_cmt("total number of leaf nodes is %llu", ci.leaf_cnt); 962 963 out: 964 dbg_free_check_tree(&ci.root); 965 kfree(ci.node); 966 return err; 967 } 968