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