fs/ubifs/orphan.c

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