fs/ubifs/recovery.c

   1 /*
   2  * This file is part of UBIFS.
   3  *
   4  * Copyright (C) 2006-2008 Nokia Corporation
   5  *
   6  * SPDX-License-Identifier:     GPL-2.0+
   7  *
   8  * Authors: Adrian Hunter
   9  *          Artem Bityutskiy (Битюцкий Артём)
  10  */
  11
  12 /*
  13  * This file implements functions needed to recover from unclean un-mounts.
  14  * When UBIFS is mounted, it checks a flag on the master node to determine if
  15  * an un-mount was completed successfully. If not, the process of mounting
  16  * incorporates additional checking and fixing of on-flash data structures.
  17  * UBIFS always cleans away all remnants of an unclean un-mount, so that
  18  * errors do not accumulate. However UBIFS defers recovery if it is mounted
  19  * read-only, and the flash is not modified in that case.
  20  *
  21  * The general UBIFS approach to the recovery is that it recovers from
  22  * corruptions which could be caused by power cuts, but it refuses to recover
  23  * from corruption caused by other reasons. And UBIFS tries to distinguish
  24  * between these 2 reasons of corruptions and silently recover in the former
  25  * case and loudly complain in the latter case.
  26  *
  27  * UBIFS writes only to erased LEBs, so it writes only to the flash space
  28  * containing only 0xFFs. UBIFS also always writes strictly from the beginning
  29  * of the LEB to the end. And UBIFS assumes that the underlying flash media
  30  * writes in @c->max_write_size bytes at a time.
  31  *
  32  * Hence, if UBIFS finds a corrupted node at offset X, it expects only the min.
  33  * I/O unit corresponding to offset X to contain corrupted data, all the
  34  * following min. I/O units have to contain empty space (all 0xFFs). If this is
  35  * not true, the corruption cannot be the result of a power cut, and UBIFS
  36  * refuses to mount.
  37  */
  38
  39 #ifndef __UBOOT__
  40 #include <linux/crc32.h>
  41 #include <linux/slab.h>
  42 #else
  43 #include <linux/err.h>
  44 #endif
  45 #include "ubifs.h"
  46
  47 /**
  48  * is_empty - determine whether a buffer is empty (contains all 0xff).
  49  * @buf: buffer to clean
  50  * @len: length of buffer
  51  *
  52  * This function returns %1 if the buffer is empty (contains all 0xff) otherwise
  53  * %0 is returned.
  54  */
  55 static int is_empty(void *buf, int len)
  56 {
  57         uint8_t *p = buf;
  58         int i;
  59
  60         for (i = 0; i < len; i++)
  61                 if (*p++ != 0xff)
  62                         return 0;
  63         return 1;
  64 }
  65
  66 /**
  67  * first_non_ff - find offset of the first non-0xff byte.
  68  * @buf: buffer to search in
  69  * @len: length of buffer
  70  *
  71  * This function returns offset of the first non-0xff byte in @buf or %-1 if
  72  * the buffer contains only 0xff bytes.
  73  */
  74 static int first_non_ff(void *buf, int len)
  75 {
  76         uint8_t *p = buf;
  77         int i;
  78
  79         for (i = 0; i < len; i++)
  80                 if (*p++ != 0xff)
  81                         return i;
  82         return -1;
  83 }
  84
  85 /**
  86  * get_master_node - get the last valid master node allowing for corruption.
  87  * @c: UBIFS file-system description object
  88  * @lnum: LEB number
  89  * @pbuf: buffer containing the LEB read, is returned here
  90  * @mst: master node, if found, is returned here
  91  * @cor: corruption, if found, is returned here
  92  *
  93  * This function allocates a buffer, reads the LEB into it, and finds and
  94  * returns the last valid master node allowing for one area of corruption.
  95  * The corrupt area, if there is one, must be consistent with the assumption
  96  * that it is the result of an unclean unmount while the master node was being
  97  * written. Under those circumstances, it is valid to use the previously written
  98  * master node.
  99  *
 100  * This function returns %0 on success and a negative error code on failure.
 101  */
 102 static int get_master_node(const struct ubifs_info *c, int lnum, void **pbuf,
 103                            struct ubifs_mst_node **mst, void **cor)
 104 {
 105         const int sz = c->mst_node_alsz;
 106         int err, offs, len;
 107         void *sbuf, *buf;
 108
 109         sbuf = vmalloc(c->leb_size);
 110         if (!sbuf)
 111                 return -ENOMEM;
 112
 113         err = ubifs_leb_read(c, lnum, sbuf, 0, c->leb_size, 0);
 114         if (err && err != -EBADMSG)
 115                 goto out_free;
 116
 117         /* Find the first position that is definitely not a node */
 118         offs = 0;
 119         buf = sbuf;
 120         len = c->leb_size;
 121         while (offs + UBIFS_MST_NODE_SZ <= c->leb_size) {
 122                 struct ubifs_ch *ch = buf;
 123
 124                 if (le32_to_cpu(ch->magic) != UBIFS_NODE_MAGIC)
 125                         break;
 126                 offs += sz;
 127                 buf  += sz;
 128                 len  -= sz;
 129         }
 130         /* See if there was a valid master node before that */
 131         if (offs) {
 132                 int ret;
 133
 134                 offs -= sz;
 135                 buf  -= sz;
 136                 len  += sz;
 137                 ret = ubifs_scan_a_node(c, buf, len, lnum, offs, 1);
 138                 if (ret != SCANNED_A_NODE && offs) {
 139                         /* Could have been corruption so check one place back */
 140                         offs -= sz;
 141                         buf  -= sz;
 142                         len  += sz;
 143                         ret = ubifs_scan_a_node(c, buf, len, lnum, offs, 1);
 144                         if (ret != SCANNED_A_NODE)
 145                                 /*
 146                                  * We accept only one area of corruption because
 147                                  * we are assuming that it was caused while
 148                                  * trying to write a master node.
 149                                  */
 150                                 goto out_err;
 151                 }
 152                 if (ret == SCANNED_A_NODE) {
 153                         struct ubifs_ch *ch = buf;
 154
 155                         if (ch->node_type != UBIFS_MST_NODE)
 156                                 goto out_err;
 157                         dbg_rcvry("found a master node at %d:%d", lnum, offs);
 158                         *mst = buf;
 159                         offs += sz;
 160                         buf  += sz;
 161                         len  -= sz;
 162                 }
 163         }
 164         /* Check for corruption */
 165         if (offs < c->leb_size) {
 166                 if (!is_empty(buf, min_t(int, len, sz))) {
 167                         *cor = buf;
 168                         dbg_rcvry("found corruption at %d:%d", lnum, offs);
 169                 }
 170                 offs += sz;
 171                 buf  += sz;
 172                 len  -= sz;
 173         }
 174         /* Check remaining empty space */
 175         if (offs < c->leb_size)
 176                 if (!is_empty(buf, len))
 177                         goto out_err;
 178         *pbuf = sbuf;
 179         return 0;
 180
 181 out_err:
 182         err = -EINVAL;
 183 out_free:
 184         vfree(sbuf);
 185         *mst = NULL;
 186         *cor = NULL;
 187         return err;
 188 }
 189
 190 /**
 191  * write_rcvrd_mst_node - write recovered master node.
 192  * @c: UBIFS file-system description object
 193  * @mst: master node
 194  *
 195  * This function returns %0 on success and a negative error code on failure.
 196  */
 197 static int write_rcvrd_mst_node(struct ubifs_info *c,
 198                                 struct ubifs_mst_node *mst)
 199 {
 200         int err = 0, lnum = UBIFS_MST_LNUM, sz = c->mst_node_alsz;
 201         __le32 save_flags;
 202
 203         dbg_rcvry("recovery");
 204
 205         save_flags = mst->flags;
 206         mst->flags |= cpu_to_le32(UBIFS_MST_RCVRY);
 207
 208         ubifs_prepare_node(c, mst, UBIFS_MST_NODE_SZ, 1);
 209         err = ubifs_leb_change(c, lnum, mst, sz);
 210         if (err)
 211                 goto out;
 212         err = ubifs_leb_change(c, lnum + 1, mst, sz);
 213         if (err)
 214                 goto out;
 215 out:
 216         mst->flags = save_flags;
 217         return err;
 218 }
 219
 220 /**
 221  * ubifs_recover_master_node - recover the master node.
 222  * @c: UBIFS file-system description object
 223  *
 224  * This function recovers the master node from corruption that may occur due to
 225  * an unclean unmount.
 226  *
 227  * This function returns %0 on success and a negative error code on failure.
 228  */
 229 int ubifs_recover_master_node(struct ubifs_info *c)
 230 {
 231         void *buf1 = NULL, *buf2 = NULL, *cor1 = NULL, *cor2 = NULL;
 232         struct ubifs_mst_node *mst1 = NULL, *mst2 = NULL, *mst;
 233         const int sz = c->mst_node_alsz;
 234         int err, offs1, offs2;
 235
 236         dbg_rcvry("recovery");
 237
 238         err = get_master_node(c, UBIFS_MST_LNUM, &buf1, &mst1, &cor1);
 239         if (err)
 240                 goto out_free;
 241
 242         err = get_master_node(c, UBIFS_MST_LNUM + 1, &buf2, &mst2, &cor2);
 243         if (err)
 244                 goto out_free;
 245
 246         if (mst1) {
 247                 offs1 = (void *)mst1 - buf1;
 248                 if ((le32_to_cpu(mst1->flags) & UBIFS_MST_RCVRY) &&
 249                     (offs1 == 0 && !cor1)) {
 250                         /*
 251                          * mst1 was written by recovery at offset 0 with no
 252                          * corruption.
 253                          */
 254                         dbg_rcvry("recovery recovery");
 255                         mst = mst1;
 256                 } else if (mst2) {
 257                         offs2 = (void *)mst2 - buf2;
 258                         if (offs1 == offs2) {
 259                                 /* Same offset, so must be the same */
 260                                 if (memcmp((void *)mst1 + UBIFS_CH_SZ,
 261                                            (void *)mst2 + UBIFS_CH_SZ,
 262                                            UBIFS_MST_NODE_SZ - UBIFS_CH_SZ))
 263                                         goto out_err;
 264                                 mst = mst1;
 265                         } else if (offs2 + sz == offs1) {
 266                                 /* 1st LEB was written, 2nd was not */
 267                                 if (cor1)
 268                                         goto out_err;
 269                                 mst = mst1;
 270                         } else if (offs1 == 0 &&
 271                                    c->leb_size - offs2 - sz < sz) {
 272                                 /* 1st LEB was unmapped and written, 2nd not */
 273                                 if (cor1)
 274                                         goto out_err;
 275                                 mst = mst1;
 276                         } else
 277                                 goto out_err;
 278                 } else {
 279                         /*
 280                          * 2nd LEB was unmapped and about to be written, so
 281                          * there must be only one master node in the first LEB
 282                          * and no corruption.
 283                          */
 284                         if (offs1 != 0 || cor1)
 285                                 goto out_err;
 286                         mst = mst1;
 287                 }
 288         } else {
 289                 if (!mst2)
 290                         goto out_err;
 291                 /*
 292                  * 1st LEB was unmapped and about to be written, so there must
 293                  * be no room left in 2nd LEB.
 294                  */
 295                 offs2 = (void *)mst2 - buf2;
 296                 if (offs2 + sz + sz <= c->leb_size)
 297                         goto out_err;
 298                 mst = mst2;
 299         }
 300
 301         ubifs_msg(c, "recovered master node from LEB %d",
 302                   (mst == mst1 ? UBIFS_MST_LNUM : UBIFS_MST_LNUM + 1));
 303
 304         memcpy(c->mst_node, mst, UBIFS_MST_NODE_SZ);
 305
 306         if (c->ro_mount) {
 307                 /* Read-only mode. Keep a copy for switching to rw mode */
 308                 c->rcvrd_mst_node = kmalloc(sz, GFP_KERNEL);
 309                 if (!c->rcvrd_mst_node) {
 310                         err = -ENOMEM;
 311                         goto out_free;
 312                 }
 313                 memcpy(c->rcvrd_mst_node, c->mst_node, UBIFS_MST_NODE_SZ);
 314
 315                 /*
 316                  * We had to recover the master node, which means there was an
 317                  * unclean reboot. However, it is possible that the master node
 318                  * is clean at this point, i.e., %UBIFS_MST_DIRTY is not set.
 319                  * E.g., consider the following chain of events:
 320                  *
 321                  * 1. UBIFS was cleanly unmounted, so the master node is clean
 322                  * 2. UBIFS is being mounted R/W and starts changing the master
 323                  *    node in the first (%UBIFS_MST_LNUM). A power cut happens,
 324                  *    so this LEB ends up with some amount of garbage at the
 325                  *    end.
 326                  * 3. UBIFS is being mounted R/O. We reach this place and
 327                  *    recover the master node from the second LEB
 328                  *    (%UBIFS_MST_LNUM + 1). But we cannot update the media
 329                  *    because we are being mounted R/O. We have to defer the
 330                  *    operation.
 331                  * 4. However, this master node (@c->mst_node) is marked as
 332                  *    clean (since the step 1). And if we just return, the
 333                  *    mount code will be confused and won't recover the master
 334                  *    node when it is re-mounter R/W later.
 335                  *
 336                  *    Thus, to force the recovery by marking the master node as
 337                  *    dirty.
 338                  */
 339                 c->mst_node->flags |= cpu_to_le32(UBIFS_MST_DIRTY);
 340 #ifndef __UBOOT__
 341         } else {
 342                 /* Write the recovered master node */
 343                 c->max_sqnum = le64_to_cpu(mst->ch.sqnum) - 1;
 344                 err = write_rcvrd_mst_node(c, c->mst_node);
 345                 if (err)
 346                         goto out_free;
 347 #endif
 348         }
 349
 350         vfree(buf2);
 351         vfree(buf1);
 352
 353         return 0;
 354
 355 out_err:
 356         err = -EINVAL;
 357 out_free:
 358         ubifs_err(c, "failed to recover master node");
 359         if (mst1) {
 360                 ubifs_err(c, "dumping first master node");
 361                 ubifs_dump_node(c, mst1);
 362         }
 363         if (mst2) {
 364                 ubifs_err(c, "dumping second master node");
 365                 ubifs_dump_node(c, mst2);
 366         }
 367         vfree(buf2);
 368         vfree(buf1);
 369         return err;
 370 }
 371
 372 /**
 373  * ubifs_write_rcvrd_mst_node - write the recovered master node.
 374  * @c: UBIFS file-system description object
 375  *
 376  * This function writes the master node that was recovered during mounting in
 377  * read-only mode and must now be written because we are remounting rw.
 378  *
 379  * This function returns %0 on success and a negative error code on failure.
 380  */
 381 int ubifs_write_rcvrd_mst_node(struct ubifs_info *c)
 382 {
 383         int err;
 384
 385         if (!c->rcvrd_mst_node)
 386                 return 0;
 387         c->rcvrd_mst_node->flags |= cpu_to_le32(UBIFS_MST_DIRTY);
 388         c->mst_node->flags |= cpu_to_le32(UBIFS_MST_DIRTY);
 389         err = write_rcvrd_mst_node(c, c->rcvrd_mst_node);
 390         if (err)
 391                 return err;
 392         kfree(c->rcvrd_mst_node);
 393         c->rcvrd_mst_node = NULL;
 394         return 0;
 395 }
 396
 397 /**
 398  * is_last_write - determine if an offset was in the last write to a LEB.
 399  * @c: UBIFS file-system description object
 400  * @buf: buffer to check
 401  * @offs: offset to check
 402  *
 403  * This function returns %1 if @offs was in the last write to the LEB whose data
 404  * is in @buf, otherwise %0 is returned. The determination is made by checking
 405  * for subsequent empty space starting from the next @c->max_write_size
 406  * boundary.
 407  */
 408 static int is_last_write(const struct ubifs_info *c, void *buf, int offs)
 409 {
 410         int empty_offs, check_len;
 411         uint8_t *p;
 412
 413         /*
 414          * Round up to the next @c->max_write_size boundary i.e. @offs is in
 415          * the last wbuf written. After that should be empty space.
 416          */
 417         empty_offs = ALIGN(offs + 1, c->max_write_size);
 418         check_len = c->leb_size - empty_offs;
 419         p = buf + empty_offs - offs;
 420         return is_empty(p, check_len);
 421 }
 422
 423 /**
 424  * clean_buf - clean the data from an LEB sitting in a buffer.
 425  * @c: UBIFS file-system description object
 426  * @buf: buffer to clean
 427  * @lnum: LEB number to clean
 428  * @offs: offset from which to clean
 429  * @len: length of buffer
 430  *
 431  * This function pads up to the next min_io_size boundary (if there is one) and
 432  * sets empty space to all 0xff. @buf, @offs and @len are updated to the next
 433  * @c->min_io_size boundary.
 434  */
 435 static void clean_buf(const struct ubifs_info *c, void **buf, int lnum,
 436                       int *offs, int *len)
 437 {
 438         int empty_offs, pad_len;
 439
 440         lnum = lnum;
 441         dbg_rcvry("cleaning corruption at %d:%d", lnum, *offs);
 442
 443         ubifs_assert(!(*offs & 7));
 444         empty_offs = ALIGN(*offs, c->min_io_size);
 445         pad_len = empty_offs - *offs;
 446         ubifs_pad(c, *buf, pad_len);
 447         *offs += pad_len;
 448         *buf += pad_len;
 449         *len -= pad_len;
 450         memset(*buf, 0xff, c->leb_size - empty_offs);
 451 }
 452
 453 /**
 454  * no_more_nodes - determine if there are no more nodes in a buffer.
 455  * @c: UBIFS file-system description object
 456  * @buf: buffer to check
 457  * @len: length of buffer
 458  * @lnum: LEB number of the LEB from which @buf was read
 459  * @offs: offset from which @buf was read
 460  *
 461  * This function ensures that the corrupted node at @offs is the last thing
 462  * written to a LEB. This function returns %1 if more data is not found and
 463  * %0 if more data is found.
 464  */
 465 static int no_more_nodes(const struct ubifs_info *c, void *buf, int len,
 466                         int lnum, int offs)
 467 {
 468         struct ubifs_ch *ch = buf;
 469         int skip, dlen = le32_to_cpu(ch->len);
 470
 471         /* Check for empty space after the corrupt node's common header */
 472         skip = ALIGN(offs + UBIFS_CH_SZ, c->max_write_size) - offs;
 473         if (is_empty(buf + skip, len - skip))
 474                 return 1;
 475         /*
 476          * The area after the common header size is not empty, so the common
 477          * header must be intact. Check it.
 478          */
 479         if (ubifs_check_node(c, buf, lnum, offs, 1, 0) != -EUCLEAN) {
 480                 dbg_rcvry("unexpected bad common header at %d:%d", lnum, offs);
 481                 return 0;
 482         }
 483         /* Now we know the corrupt node's length we can skip over it */
 484         skip = ALIGN(offs + dlen, c->max_write_size) - offs;
 485         /* After which there should be empty space */
 486         if (is_empty(buf + skip, len - skip))
 487                 return 1;
 488         dbg_rcvry("unexpected data at %d:%d", lnum, offs + skip);
 489         return 0;
 490 }
 491
 492 /**
 493  * fix_unclean_leb - fix an unclean LEB.
 494  * @c: UBIFS file-system description object
 495  * @sleb: scanned LEB information
 496  * @start: offset where scan started
 497  */
 498 static int fix_unclean_leb(struct ubifs_info *c, struct ubifs_scan_leb *sleb,
 499                            int start)
 500 {
 501         int lnum = sleb->lnum, endpt = start;
 502
 503         /* Get the end offset of the last node we are keeping */
 504         if (!list_empty(&sleb->nodes)) {
 505                 struct ubifs_scan_node *snod;
 506
 507                 snod = list_entry(sleb->nodes.prev,
 508                                   struct ubifs_scan_node, list);
 509                 endpt = snod->offs + snod->len;
 510         }
 511
 512         if (c->ro_mount && !c->remounting_rw) {
 513                 /* Add to recovery list */
 514                 struct ubifs_unclean_leb *ucleb;
 515
 516                 dbg_rcvry("need to fix LEB %d start %d endpt %d",
 517                           lnum, start, sleb->endpt);
 518                 ucleb = kzalloc(sizeof(struct ubifs_unclean_leb), GFP_NOFS);
 519                 if (!ucleb)
 520                         return -ENOMEM;
 521                 ucleb->lnum = lnum;
 522                 ucleb->endpt = endpt;
 523                 list_add_tail(&ucleb->list, &c->unclean_leb_list);
 524 #ifndef __UBOOT__
 525         } else {
 526                 /* Write the fixed LEB back to flash */
 527                 int err;
 528
 529                 dbg_rcvry("fixing LEB %d start %d endpt %d",
 530                           lnum, start, sleb->endpt);
 531                 if (endpt == 0) {
 532                         err = ubifs_leb_unmap(c, lnum);
 533                         if (err)
 534                                 return err;
 535                 } else {
 536                         int len = ALIGN(endpt, c->min_io_size);
 537
 538                         if (start) {
 539                                 err = ubifs_leb_read(c, lnum, sleb->buf, 0,
 540                                                      start, 1);
 541                                 if (err)
 542                                         return err;
 543                         }
 544                         /* Pad to min_io_size */
 545                         if (len > endpt) {
 546                                 int pad_len = len - ALIGN(endpt, 8);
 547
 548                                 if (pad_len > 0) {
 549                                         void *buf = sleb->buf + len - pad_len;
 550
 551                                         ubifs_pad(c, buf, pad_len);
 552                                 }
 553                         }
 554                         err = ubifs_leb_change(c, lnum, sleb->buf, len);
 555                         if (err)
 556                                 return err;
 557                 }
 558 #endif
 559         }
 560         return 0;
 561 }
 562
 563 /**
 564  * drop_last_group - drop the last group of nodes.
 565  * @sleb: scanned LEB information
 566  * @offs: offset of dropped nodes is returned here
 567  *
 568  * This is a helper function for 'ubifs_recover_leb()' which drops the last
 569  * group of nodes of the scanned LEB.
 570  */
 571 static void drop_last_group(struct ubifs_scan_leb *sleb, int *offs)
 572 {
 573         while (!list_empty(&sleb->nodes)) {
 574                 struct ubifs_scan_node *snod;
 575                 struct ubifs_ch *ch;
 576
 577                 snod = list_entry(sleb->nodes.prev, struct ubifs_scan_node,
 578                                   list);
 579                 ch = snod->node;
 580                 if (ch->group_type != UBIFS_IN_NODE_GROUP)
 581                         break;
 582
 583                 dbg_rcvry("dropping grouped node at %d:%d",
 584                           sleb->lnum, snod->offs);
 585                 *offs = snod->offs;
 586                 list_del(&snod->list);
 587                 kfree(snod);
 588                 sleb->nodes_cnt -= 1;
 589         }
 590 }
 591
 592 /**
 593  * drop_last_node - drop the last node.
 594  * @sleb: scanned LEB information
 595  * @offs: offset of dropped nodes is returned here
 596  *
 597  * This is a helper function for 'ubifs_recover_leb()' which drops the last
 598  * node of the scanned LEB.
 599  */
 600 static void drop_last_node(struct ubifs_scan_leb *sleb, int *offs)
 601 {
 602         struct ubifs_scan_node *snod;
 603
 604         if (!list_empty(&sleb->nodes)) {
 605                 snod = list_entry(sleb->nodes.prev, struct ubifs_scan_node,
 606                                   list);
 607
 608                 dbg_rcvry("dropping last node at %d:%d",
 609                           sleb->lnum, snod->offs);
 610                 *offs = snod->offs;
 611                 list_del(&snod->list);
 612                 kfree(snod);
 613                 sleb->nodes_cnt -= 1;
 614         }
 615 }
 616
 617 /**
 618  * ubifs_recover_leb - scan and recover a LEB.
 619  * @c: UBIFS file-system description object
 620  * @lnum: LEB number
 621  * @offs: offset
 622  * @sbuf: LEB-sized buffer to use
 623  * @jhead: journal head number this LEB belongs to (%-1 if the LEB does not
 624  *         belong to any journal head)
 625  *
 626  * This function does a scan of a LEB, but caters for errors that might have
 627  * been caused by the unclean unmount from which we are attempting to recover.
 628  * Returns the scanned information on success and a negative error code on
 629  * failure.
 630  */
 631 struct ubifs_scan_leb *ubifs_recover_leb(struct ubifs_info *c, int lnum,
 632                                          int offs, void *sbuf, int jhead)
 633 {
 634         int ret = 0, err, len = c->leb_size - offs, start = offs, min_io_unit;
 635         int grouped = jhead == -1 ? 0 : c->jheads[jhead].grouped;
 636         struct ubifs_scan_leb *sleb;
 637         void *buf = sbuf + offs;
 638
 639         dbg_rcvry("%d:%d, jhead %d, grouped %d", lnum, offs, jhead, grouped);
 640
 641         sleb = ubifs_start_scan(c, lnum, offs, sbuf);
 642         if (IS_ERR(sleb))
 643                 return sleb;
 644
 645         ubifs_assert(len >= 8);
 646         while (len >= 8) {
 647                 dbg_scan("look at LEB %d:%d (%d bytes left)",
 648                          lnum, offs, len);
 649
 650                 cond_resched();
 651
 652                 /*
 653                  * Scan quietly until there is an error from which we cannot
 654                  * recover
 655                  */
 656                 ret = ubifs_scan_a_node(c, buf, len, lnum, offs, 1);
 657                 if (ret == SCANNED_A_NODE) {
 658                         /* A valid node, and not a padding node */
 659                         struct ubifs_ch *ch = buf;
 660                         int node_len;
 661
 662                         err = ubifs_add_snod(c, sleb, buf, offs);
 663                         if (err)
 664                                 goto error;
 665                         node_len = ALIGN(le32_to_cpu(ch->len), 8);
 666                         offs += node_len;
 667                         buf += node_len;
 668                         len -= node_len;
 669                 } else if (ret > 0) {
 670                         /* Padding bytes or a valid padding node */
 671                         offs += ret;
 672                         buf += ret;
 673                         len -= ret;
 674                 } else if (ret == SCANNED_EMPTY_SPACE ||
 675                            ret == SCANNED_GARBAGE     ||
 676                            ret == SCANNED_A_BAD_PAD_NODE ||
 677                            ret == SCANNED_A_CORRUPT_NODE) {
 678                         dbg_rcvry("found corruption (%d) at %d:%d",
 679                                   ret, lnum, offs);
 680                         break;
 681                 } else {
 682                         ubifs_err(c, "unexpected return value %d", ret);
 683                         err = -EINVAL;
 684                         goto error;
 685                 }
 686         }
 687
 688         if (ret == SCANNED_GARBAGE || ret == SCANNED_A_BAD_PAD_NODE) {
 689                 if (!is_last_write(c, buf, offs))
 690                         goto corrupted_rescan;
 691         } else if (ret == SCANNED_A_CORRUPT_NODE) {
 692                 if (!no_more_nodes(c, buf, len, lnum, offs))
 693                         goto corrupted_rescan;
 694         } else if (!is_empty(buf, len)) {
 695                 if (!is_last_write(c, buf, offs)) {
 696                         int corruption = first_non_ff(buf, len);
 697
 698                         /*
 699                          * See header comment for this file for more
 700                          * explanations about the reasons we have this check.
 701                          */
 702                         ubifs_err(c, "corrupt empty space LEB %d:%d, corruption starts at %d",
 703                                   lnum, offs, corruption);
 704                         /* Make sure we dump interesting non-0xFF data */
 705                         offs += corruption;
 706                         buf += corruption;
 707                         goto corrupted;
 708                 }
 709         }
 710
 711         min_io_unit = round_down(offs, c->min_io_size);
 712         if (grouped)
 713                 /*
 714                  * If nodes are grouped, always drop the incomplete group at
 715                  * the end.
 716                  */
 717                 drop_last_group(sleb, &offs);
 718
 719         if (jhead == GCHD) {
 720                 /*
 721                  * If this LEB belongs to the GC head then while we are in the
 722                  * middle of the same min. I/O unit keep dropping nodes. So
 723                  * basically, what we want is to make sure that the last min.
 724                  * I/O unit where we saw the corruption is dropped completely
 725                  * with all the uncorrupted nodes which may possibly sit there.
 726                  *
 727                  * In other words, let's name the min. I/O unit where the
 728                  * corruption starts B, and the previous min. I/O unit A. The
 729                  * below code tries to deal with a situation when half of B
 730                  * contains valid nodes or the end of a valid node, and the
 731                  * second half of B contains corrupted data or garbage. This
 732                  * means that UBIFS had been writing to B just before the power
 733                  * cut happened. I do not know how realistic is this scenario
 734                  * that half of the min. I/O unit had been written successfully
 735                  * and the other half not, but this is possible in our 'failure
 736                  * mode emulation' infrastructure at least.
 737                  *
 738                  * So what is the problem, why we need to drop those nodes? Why
 739                  * can't we just clean-up the second half of B by putting a
 740                  * padding node there? We can, and this works fine with one
 741                  * exception which was reproduced with power cut emulation
 742                  * testing and happens extremely rarely.
 743                  *
 744                  * Imagine the file-system is full, we run GC which starts
 745                  * moving valid nodes from LEB X to LEB Y (obviously, LEB Y is
 746                  * the current GC head LEB). The @c->gc_lnum is -1, which means
 747                  * that GC will retain LEB X and will try to continue. Imagine
 748                  * that LEB X is currently the dirtiest LEB, and the amount of
 749                  * used space in LEB Y is exactly the same as amount of free
 750                  * space in LEB X.
 751                  *
 752                  * And a power cut happens when nodes are moved from LEB X to
 753                  * LEB Y. We are here trying to recover LEB Y which is the GC
 754                  * head LEB. We find the min. I/O unit B as described above.
 755                  * Then we clean-up LEB Y by padding min. I/O unit. And later
 756                  * 'ubifs_rcvry_gc_commit()' function fails, because it cannot
 757                  * find a dirty LEB which could be GC'd into LEB Y! Even LEB X
 758                  * does not match because the amount of valid nodes there does
 759                  * not fit the free space in LEB Y any more! And this is
 760                  * because of the padding node which we added to LEB Y. The
 761                  * user-visible effect of this which I once observed and
 762                  * analysed is that we cannot mount the file-system with
 763                  * -ENOSPC error.
 764                  *
 765                  * So obviously, to make sure that situation does not happen we
 766                  * should free min. I/O unit B in LEB Y completely and the last
 767                  * used min. I/O unit in LEB Y should be A. This is basically
 768                  * what the below code tries to do.
 769                  */
 770                 while (offs > min_io_unit)
 771                         drop_last_node(sleb, &offs);
 772         }
 773
 774         buf = sbuf + offs;
 775         len = c->leb_size - offs;
 776
 777         clean_buf(c, &buf, lnum, &offs, &len);
 778         ubifs_end_scan(c, sleb, lnum, offs);
 779
 780         err = fix_unclean_leb(c, sleb, start);
 781         if (err)
 782                 goto error;
 783
 784         return sleb;
 785
 786 corrupted_rescan:
 787         /* Re-scan the corrupted data with verbose messages */
 788         ubifs_err(c, "corruption %d", ret);
 789         ubifs_scan_a_node(c, buf, len, lnum, offs, 1);
 790 corrupted:
 791         ubifs_scanned_corruption(c, lnum, offs, buf);
 792         err = -EUCLEAN;
 793 error:
 794         ubifs_err(c, "LEB %d scanning failed", lnum);
 795         ubifs_scan_destroy(sleb);
 796         return ERR_PTR(err);
 797 }
 798
 799 /**
 800  * get_cs_sqnum - get commit start sequence number.
 801  * @c: UBIFS file-system description object
 802  * @lnum: LEB number of commit start node
 803  * @offs: offset of commit start node
 804  * @cs_sqnum: commit start sequence number is returned here
 805  *
 806  * This function returns %0 on success and a negative error code on failure.
 807  */
 808 static int get_cs_sqnum(struct ubifs_info *c, int lnum, int offs,
 809                         unsigned long long *cs_sqnum)
 810 {
 811         struct ubifs_cs_node *cs_node = NULL;
 812         int err, ret;
 813
 814         dbg_rcvry("at %d:%d", lnum, offs);
 815         cs_node = kmalloc(UBIFS_CS_NODE_SZ, GFP_KERNEL);
 816         if (!cs_node)
 817                 return -ENOMEM;
 818         if (c->leb_size - offs < UBIFS_CS_NODE_SZ)
 819                 goto out_err;
 820         err = ubifs_leb_read(c, lnum, (void *)cs_node, offs,
 821                              UBIFS_CS_NODE_SZ, 0);
 822         if (err && err != -EBADMSG)
 823                 goto out_free;
 824         ret = ubifs_scan_a_node(c, cs_node, UBIFS_CS_NODE_SZ, lnum, offs, 0);
 825         if (ret != SCANNED_A_NODE) {
 826                 ubifs_err(c, "Not a valid node");
 827                 goto out_err;
 828         }
 829         if (cs_node->ch.node_type != UBIFS_CS_NODE) {
 830                 ubifs_err(c, "Node a CS node, type is %d", cs_node->ch.node_type);
 831                 goto out_err;
 832         }
 833         if (le64_to_cpu(cs_node->cmt_no) != c->cmt_no) {
 834                 ubifs_err(c, "CS node cmt_no %llu != current cmt_no %llu",
 835                           (unsigned long long)le64_to_cpu(cs_node->cmt_no),
 836                           c->cmt_no);
 837                 goto out_err;
 838         }
 839         *cs_sqnum = le64_to_cpu(cs_node->ch.sqnum);
 840         dbg_rcvry("commit start sqnum %llu", *cs_sqnum);
 841         kfree(cs_node);
 842         return 0;
 843
 844 out_err:
 845         err = -EINVAL;
 846 out_free:
 847         ubifs_err(c, "failed to get CS sqnum");
 848         kfree(cs_node);
 849         return err;
 850 }
 851
 852 /**
 853  * ubifs_recover_log_leb - scan and recover a log LEB.
 854  * @c: UBIFS file-system description object
 855  * @lnum: LEB number
 856  * @offs: offset
 857  * @sbuf: LEB-sized buffer to use
 858  *
 859  * This function does a scan of a LEB, but caters for errors that might have
 860  * been caused by unclean reboots from which we are attempting to recover
 861  * (assume that only the last log LEB can be corrupted by an unclean reboot).
 862  *
 863  * This function returns %0 on success and a negative error code on failure.
 864  */
 865 struct ubifs_scan_leb *ubifs_recover_log_leb(struct ubifs_info *c, int lnum,
 866                                              int offs, void *sbuf)
 867 {
 868         struct ubifs_scan_leb *sleb;
 869         int next_lnum;
 870
 871         dbg_rcvry("LEB %d", lnum);
 872         next_lnum = lnum + 1;
 873         if (next_lnum >= UBIFS_LOG_LNUM + c->log_lebs)
 874                 next_lnum = UBIFS_LOG_LNUM;
 875         if (next_lnum != c->ltail_lnum) {
 876                 /*
 877                  * We can only recover at the end of the log, so check that the
 878                  * next log LEB is empty or out of date.
 879                  */
 880                 sleb = ubifs_scan(c, next_lnum, 0, sbuf, 0);
 881                 if (IS_ERR(sleb))
 882                         return sleb;
 883                 if (sleb->nodes_cnt) {
 884                         struct ubifs_scan_node *snod;
 885                         unsigned long long cs_sqnum = c->cs_sqnum;
 886
 887                         snod = list_entry(sleb->nodes.next,
 888                                           struct ubifs_scan_node, list);
 889                         if (cs_sqnum == 0) {
 890                                 int err;
 891
 892                                 err = get_cs_sqnum(c, lnum, offs, &cs_sqnum);
 893                                 if (err) {
 894                                         ubifs_scan_destroy(sleb);
 895                                         return ERR_PTR(err);
 896                                 }
 897                         }
 898                         if (snod->sqnum > cs_sqnum) {
 899                                 ubifs_err(c, "unrecoverable log corruption in LEB %d",
 900                                           lnum);
 901                                 ubifs_scan_destroy(sleb);
 902                                 return ERR_PTR(-EUCLEAN);
 903                         }
 904                 }
 905                 ubifs_scan_destroy(sleb);
 906         }
 907         return ubifs_recover_leb(c, lnum, offs, sbuf, -1);
 908 }
 909
 910 /**
 911  * recover_head - recover a head.
 912  * @c: UBIFS file-system description object
 913  * @lnum: LEB number of head to recover
 914  * @offs: offset of head to recover
 915  * @sbuf: LEB-sized buffer to use
 916  *
 917  * This function ensures that there is no data on the flash at a head location.
 918  *
 919  * This function returns %0 on success and a negative error code on failure.
 920  */
 921 static int recover_head(struct ubifs_info *c, int lnum, int offs, void *sbuf)
 922 {
 923         int len = c->max_write_size, err;
 924
 925         if (offs + len > c->leb_size)
 926                 len = c->leb_size - offs;
 927
 928         if (!len)
 929                 return 0;
 930
 931         /* Read at the head location and check it is empty flash */
 932         err = ubifs_leb_read(c, lnum, sbuf, offs, len, 1);
 933         if (err || !is_empty(sbuf, len)) {
 934                 dbg_rcvry("cleaning head at %d:%d", lnum, offs);
 935                 if (offs == 0)
 936                         return ubifs_leb_unmap(c, lnum);
 937                 err = ubifs_leb_read(c, lnum, sbuf, 0, offs, 1);
 938                 if (err)
 939                         return err;
 940                 return ubifs_leb_change(c, lnum, sbuf, offs);
 941         }
 942
 943         return 0;
 944 }
 945
 946 /**
 947  * ubifs_recover_inl_heads - recover index and LPT heads.
 948  * @c: UBIFS file-system description object
 949  * @sbuf: LEB-sized buffer to use
 950  *
 951  * This function ensures that there is no data on the flash at the index and
 952  * LPT head locations.
 953  *
 954  * This deals with the recovery of a half-completed journal commit. UBIFS is
 955  * careful never to overwrite the last version of the index or the LPT. Because
 956  * the index and LPT are wandering trees, data from a half-completed commit will
 957  * not be referenced anywhere in UBIFS. The data will be either in LEBs that are
 958  * assumed to be empty and will be unmapped anyway before use, or in the index
 959  * and LPT heads.
 960  *
 961  * This function returns %0 on success and a negative error code on failure.
 962  */
 963 int ubifs_recover_inl_heads(struct ubifs_info *c, void *sbuf)
 964 {
 965         int err;
 966
 967         ubifs_assert(!c->ro_mount || c->remounting_rw);
 968
 969         dbg_rcvry("checking index head at %d:%d", c->ihead_lnum, c->ihead_offs);
 970         err = recover_head(c, c->ihead_lnum, c->ihead_offs, sbuf);
 971         if (err)
 972                 return err;
 973
 974         dbg_rcvry("checking LPT head at %d:%d", c->nhead_lnum, c->nhead_offs);
 975
 976         return recover_head(c, c->nhead_lnum, c->nhead_offs, sbuf);
 977 }
 978
 979 /**
 980  * clean_an_unclean_leb - read and write a LEB to remove corruption.
 981  * @c: UBIFS file-system description object
 982  * @ucleb: unclean LEB information
 983  * @sbuf: LEB-sized buffer to use
 984  *
 985  * This function reads a LEB up to a point pre-determined by the mount recovery,
 986  * checks the nodes, and writes the result back to the flash, thereby cleaning
 987  * off any following corruption, or non-fatal ECC errors.
 988  *
 989  * This function returns %0 on success and a negative error code on failure.
 990  */
 991 static int clean_an_unclean_leb(struct ubifs_info *c,
 992                                 struct ubifs_unclean_leb *ucleb, void *sbuf)
 993 {
 994         int err, lnum = ucleb->lnum, offs = 0, len = ucleb->endpt, quiet = 1;
 995         void *buf = sbuf;
 996
 997         dbg_rcvry("LEB %d len %d", lnum, len);
 998
 999         if (len == 0) {
1000                 /* Nothing to read, just unmap it */
1001                 return ubifs_leb_unmap(c, lnum);
1002         }
1003
1004         err = ubifs_leb_read(c, lnum, buf, offs, len, 0);
1005         if (err && err != -EBADMSG)
1006                 return err;
1007
1008         while (len >= 8) {
1009                 int ret;
1010
1011                 cond_resched();
1012
1013                 /* Scan quietly until there is an error */
1014                 ret = ubifs_scan_a_node(c, buf, len, lnum, offs, quiet);
1015
1016                 if (ret == SCANNED_A_NODE) {
1017                         /* A valid node, and not a padding node */
1018                         struct ubifs_ch *ch = buf;
1019                         int node_len;
1020
1021                         node_len = ALIGN(le32_to_cpu(ch->len), 8);
1022                         offs += node_len;
1023                         buf += node_len;
1024                         len -= node_len;
1025                         continue;
1026                 }
1027
1028                 if (ret > 0) {
1029                         /* Padding bytes or a valid padding node */
1030                         offs += ret;
1031                         buf += ret;
1032                         len -= ret;
1033                         continue;
1034                 }
1035
1036                 if (ret == SCANNED_EMPTY_SPACE) {
1037                         ubifs_err(c, "unexpected empty space at %d:%d",
1038                                   lnum, offs);
1039                         return -EUCLEAN;
1040                 }
1041
1042                 if (quiet) {
1043                         /* Redo the last scan but noisily */
1044                         quiet = 0;
1045                         continue;
1046                 }
1047
1048                 ubifs_scanned_corruption(c, lnum, offs, buf);
1049                 return -EUCLEAN;
1050         }
1051
1052         /* Pad to min_io_size */
1053         len = ALIGN(ucleb->endpt, c->min_io_size);
1054         if (len > ucleb->endpt) {
1055                 int pad_len = len - ALIGN(ucleb->endpt, 8);
1056
1057                 if (pad_len > 0) {
1058                         buf = c->sbuf + len - pad_len;
1059                         ubifs_pad(c, buf, pad_len);
1060                 }
1061         }
1062
1063         /* Write back the LEB atomically */
1064         err = ubifs_leb_change(c, lnum, sbuf, len);
1065         if (err)
1066                 return err;
1067
1068         dbg_rcvry("cleaned LEB %d", lnum);
1069
1070         return 0;
1071 }
1072
1073 /**
1074  * ubifs_clean_lebs - clean LEBs recovered during read-only mount.
1075  * @c: UBIFS file-system description object
1076  * @sbuf: LEB-sized buffer to use
1077  *
1078  * This function cleans a LEB identified during recovery that needs to be
1079  * written but was not because UBIFS was mounted read-only. This happens when
1080  * remounting to read-write mode.
1081  *
1082  * This function returns %0 on success and a negative error code on failure.
1083  */
1084 int ubifs_clean_lebs(struct ubifs_info *c, void *sbuf)
1085 {
1086         dbg_rcvry("recovery");
1087         while (!list_empty(&c->unclean_leb_list)) {
1088                 struct ubifs_unclean_leb *ucleb;
1089                 int err;
1090
1091                 ucleb = list_entry(c->unclean_leb_list.next,
1092                                    struct ubifs_unclean_leb, list);
1093                 err = clean_an_unclean_leb(c, ucleb, sbuf);
1094                 if (err)
1095                         return err;
1096                 list_del(&ucleb->list);
1097                 kfree(ucleb);
1098         }
1099         return 0;
1100 }
1101
1102 #ifndef __UBOOT__
1103 /**
1104  * grab_empty_leb - grab an empty LEB to use as GC LEB and run commit.
1105  * @c: UBIFS file-system description object
1106  *
1107  * This is a helper function for 'ubifs_rcvry_gc_commit()' which grabs an empty
1108  * LEB to be used as GC LEB (@c->gc_lnum), and then runs the commit. Returns
1109  * zero in case of success and a negative error code in case of failure.
1110  */
1111 static int grab_empty_leb(struct ubifs_info *c)
1112 {
1113         int lnum, err;
1114
1115         /*
1116          * Note, it is very important to first search for an empty LEB and then
1117          * run the commit, not vice-versa. The reason is that there might be
1118          * only one empty LEB at the moment, the one which has been the
1119          * @c->gc_lnum just before the power cut happened. During the regular
1120          * UBIFS operation (not now) @c->gc_lnum is marked as "taken", so no
1121          * one but GC can grab it. But at this moment this single empty LEB is
1122          * not marked as taken, so if we run commit - what happens? Right, the
1123          * commit will grab it and write the index there. Remember that the
1124          * index always expands as long as there is free space, and it only
1125          * starts consolidating when we run out of space.
1126          *
1127          * IOW, if we run commit now, we might not be able to find a free LEB
1128          * after this.
1129          */
1130         lnum = ubifs_find_free_leb_for_idx(c);
1131         if (lnum < 0) {
1132                 ubifs_err(c, "could not find an empty LEB");
1133                 ubifs_dump_lprops(c);
1134                 ubifs_dump_budg(c, &c->bi);
1135                 return lnum;
1136         }
1137
1138         /* Reset the index flag */
1139         err = ubifs_change_one_lp(c, lnum, LPROPS_NC, LPROPS_NC, 0,
1140                                   LPROPS_INDEX, 0);
1141         if (err)
1142                 return err;
1143
1144         c->gc_lnum = lnum;
1145         dbg_rcvry("found empty LEB %d, run commit", lnum);
1146
1147         return ubifs_run_commit(c);
1148 }
1149
1150 /**
1151  * ubifs_rcvry_gc_commit - recover the GC LEB number and run the commit.
1152  * @c: UBIFS file-system description object
1153  *
1154  * Out-of-place garbage collection requires always one empty LEB with which to
1155  * start garbage collection. The LEB number is recorded in c->gc_lnum and is
1156  * written to the master node on unmounting. In the case of an unclean unmount
1157  * the value of gc_lnum recorded in the master node is out of date and cannot
1158  * be used. Instead, recovery must allocate an empty LEB for this purpose.
1159  * However, there may not be enough empty space, in which case it must be
1160  * possible to GC the dirtiest LEB into the GC head LEB.
1161  *
1162  * This function also runs the commit which causes the TNC updates from
1163  * size-recovery and orphans to be written to the flash. That is important to
1164  * ensure correct replay order for subsequent mounts.
1165  *
1166  * This function returns %0 on success and a negative error code on failure.
1167  */
1168 int ubifs_rcvry_gc_commit(struct ubifs_info *c)
1169 {
1170         struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
1171         struct ubifs_lprops lp;
1172         int err;
1173
1174         dbg_rcvry("GC head LEB %d, offs %d", wbuf->lnum, wbuf->offs);
1175
1176         c->gc_lnum = -1;
1177         if (wbuf->lnum == -1 || wbuf->offs == c->leb_size)
1178                 return grab_empty_leb(c);
1179
1180         err = ubifs_find_dirty_leb(c, &lp, wbuf->offs, 2);
1181         if (err) {
1182                 if (err != -ENOSPC)
1183                         return err;
1184
1185                 dbg_rcvry("could not find a dirty LEB");
1186                 return grab_empty_leb(c);
1187         }
1188
1189         ubifs_assert(!(lp.flags & LPROPS_INDEX));
1190         ubifs_assert(lp.free + lp.dirty >= wbuf->offs);
1191
1192         /*
1193          * We run the commit before garbage collection otherwise subsequent
1194          * mounts will see the GC and orphan deletion in a different order.
1195          */
1196         dbg_rcvry("committing");
1197         err = ubifs_run_commit(c);
1198         if (err)
1199                 return err;
1200
1201         dbg_rcvry("GC'ing LEB %d", lp.lnum);
1202         mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead);
1203         err = ubifs_garbage_collect_leb(c, &lp);
1204         if (err >= 0) {
1205                 int err2 = ubifs_wbuf_sync_nolock(wbuf);
1206
1207                 if (err2)
1208                         err = err2;
1209         }
1210         mutex_unlock(&wbuf->io_mutex);
1211         if (err < 0) {
1212                 ubifs_err(c, "GC failed, error %d", err);
1213                 if (err == -EAGAIN)
1214                         err = -EINVAL;
1215                 return err;
1216         }
1217
1218         ubifs_assert(err == LEB_RETAINED);
1219         if (err != LEB_RETAINED)
1220                 return -EINVAL;
1221
1222         err = ubifs_leb_unmap(c, c->gc_lnum);
1223         if (err)
1224                 return err;
1225
1226         dbg_rcvry("allocated LEB %d for GC", lp.lnum);
1227         return 0;
1228 }
1229 #else
1230 int ubifs_rcvry_gc_commit(struct ubifs_info *c)
1231 {
1232         return 0;
1233 }
1234 #endif
1235
1236 /**
1237  * struct size_entry - inode size information for recovery.
1238  * @rb: link in the RB-tree of sizes
1239  * @inum: inode number
1240  * @i_size: size on inode
1241  * @d_size: maximum size based on data nodes
1242  * @exists: indicates whether the inode exists
1243  * @inode: inode if pinned in memory awaiting rw mode to fix it
1244  */
1245 struct size_entry {
1246         struct rb_node rb;
1247         ino_t inum;
1248         loff_t i_size;
1249         loff_t d_size;
1250         int exists;
1251         struct inode *inode;
1252 };
1253
1254 /**
1255  * add_ino - add an entry to the size tree.
1256  * @c: UBIFS file-system description object
1257  * @inum: inode number
1258  * @i_size: size on inode
1259  * @d_size: maximum size based on data nodes
1260  * @exists: indicates whether the inode exists
1261  */
1262 static int add_ino(struct ubifs_info *c, ino_t inum, loff_t i_size,
1263                    loff_t d_size, int exists)
1264 {
1265         struct rb_node **p = &c->size_tree.rb_node, *parent = NULL;
1266         struct size_entry *e;
1267
1268         while (*p) {
1269                 parent = *p;
1270                 e = rb_entry(parent, struct size_entry, rb);
1271                 if (inum < e->inum)
1272                         p = &(*p)->rb_left;
1273                 else
1274                         p = &(*p)->rb_right;
1275         }
1276
1277         e = kzalloc(sizeof(struct size_entry), GFP_KERNEL);
1278         if (!e)
1279                 return -ENOMEM;
1280
1281         e->inum = inum;
1282         e->i_size = i_size;
1283         e->d_size = d_size;
1284         e->exists = exists;
1285
1286         rb_link_node(&e->rb, parent, p);
1287         rb_insert_color(&e->rb, &c->size_tree);
1288
1289         return 0;
1290 }
1291
1292 /**
1293  * find_ino - find an entry on the size tree.
1294  * @c: UBIFS file-system description object
1295  * @inum: inode number
1296  */
1297 static struct size_entry *find_ino(struct ubifs_info *c, ino_t inum)
1298 {
1299         struct rb_node *p = c->size_tree.rb_node;
1300         struct size_entry *e;
1301
1302         while (p) {
1303                 e = rb_entry(p, struct size_entry, rb);
1304                 if (inum < e->inum)
1305                         p = p->rb_left;
1306                 else if (inum > e->inum)
1307                         p = p->rb_right;
1308                 else
1309                         return e;
1310         }
1311         return NULL;
1312 }
1313
1314 /**
1315  * remove_ino - remove an entry from the size tree.
1316  * @c: UBIFS file-system description object
1317  * @inum: inode number
1318  */
1319 static void remove_ino(struct ubifs_info *c, ino_t inum)
1320 {
1321         struct size_entry *e = find_ino(c, inum);
1322
1323         if (!e)
1324                 return;
1325         rb_erase(&e->rb, &c->size_tree);
1326         kfree(e);
1327 }
1328
1329 /**
1330  * ubifs_destroy_size_tree - free resources related to the size tree.
1331  * @c: UBIFS file-system description object
1332  */
1333 void ubifs_destroy_size_tree(struct ubifs_info *c)
1334 {
1335         struct size_entry *e, *n;
1336
1337         rbtree_postorder_for_each_entry_safe(e, n, &c->size_tree, rb) {
1338                 if (e->inode)
1339                         iput(e->inode);
1340                 kfree(e);
1341         }
1342
1343         c->size_tree = RB_ROOT;
1344 }
1345
1346 /**
1347  * ubifs_recover_size_accum - accumulate inode sizes for recovery.
1348  * @c: UBIFS file-system description object
1349  * @key: node key
1350  * @deletion: node is for a deletion
1351  * @new_size: inode size
1352  *
1353  * This function has two purposes:
1354  *     1) to ensure there are no data nodes that fall outside the inode size
1355  *     2) to ensure there are no data nodes for inodes that do not exist
1356  * To accomplish those purposes, a rb-tree is constructed containing an entry
1357  * for each inode number in the journal that has not been deleted, and recording
1358  * the size from the inode node, the maximum size of any data node (also altered
1359  * by truncations) and a flag indicating a inode number for which no inode node
1360  * was present in the journal.
1361  *
1362  * Note that there is still the possibility that there are data nodes that have
1363  * been committed that are beyond the inode size, however the only way to find
1364  * them would be to scan the entire index. Alternatively, some provision could
1365  * be made to record the size of inodes at the start of commit, which would seem
1366  * very cumbersome for a scenario that is quite unlikely and the only negative
1367  * consequence of which is wasted space.
1368  *
1369  * This functions returns %0 on success and a negative error code on failure.
1370  */
1371 int ubifs_recover_size_accum(struct ubifs_info *c, union ubifs_key *key,
1372                              int deletion, loff_t new_size)
1373 {
1374         ino_t inum = key_inum(c, key);
1375         struct size_entry *e;
1376         int err;
1377
1378         switch (key_type(c, key)) {
1379         case UBIFS_INO_KEY:
1380                 if (deletion)
1381                         remove_ino(c, inum);
1382                 else {
1383                         e = find_ino(c, inum);
1384                         if (e) {
1385                                 e->i_size = new_size;
1386                                 e->exists = 1;
1387                         } else {
1388                                 err = add_ino(c, inum, new_size, 0, 1);
1389                                 if (err)
1390                                         return err;
1391                         }
1392                 }
1393                 break;
1394         case UBIFS_DATA_KEY:
1395                 e = find_ino(c, inum);
1396                 if (e) {
1397                         if (new_size > e->d_size)
1398                                 e->d_size = new_size;
1399                 } else {
1400                         err = add_ino(c, inum, 0, new_size, 0);
1401                         if (err)
1402                                 return err;
1403                 }
1404                 break;
1405         case UBIFS_TRUN_KEY:
1406                 e = find_ino(c, inum);
1407                 if (e)
1408                         e->d_size = new_size;
1409                 break;
1410         }
1411         return 0;
1412 }
1413
1414 #ifndef __UBOOT__
1415 /**
1416  * fix_size_in_place - fix inode size in place on flash.
1417  * @c: UBIFS file-system description object
1418  * @e: inode size information for recovery
1419  */
1420 static int fix_size_in_place(struct ubifs_info *c, struct size_entry *e)
1421 {
1422         struct ubifs_ino_node *ino = c->sbuf;
1423         unsigned char *p;
1424         union ubifs_key key;
1425         int err, lnum, offs, len;
1426         loff_t i_size;
1427         uint32_t crc;
1428
1429         /* Locate the inode node LEB number and offset */
1430         ino_key_init(c, &key, e->inum);
1431         err = ubifs_tnc_locate(c, &key, ino, &lnum, &offs);
1432         if (err)
1433                 goto out;
1434         /*
1435          * If the size recorded on the inode node is greater than the size that
1436          * was calculated from nodes in the journal then don't change the inode.
1437          */
1438         i_size = le64_to_cpu(ino->size);
1439         if (i_size >= e->d_size)
1440                 return 0;
1441         /* Read the LEB */
1442         err = ubifs_leb_read(c, lnum, c->sbuf, 0, c->leb_size, 1);
1443         if (err)
1444                 goto out;
1445         /* Change the size field and recalculate the CRC */
1446         ino = c->sbuf + offs;
1447         ino->size = cpu_to_le64(e->d_size);
1448         len = le32_to_cpu(ino->ch.len);
1449         crc = crc32(UBIFS_CRC32_INIT, (void *)ino + 8, len - 8);
1450         ino->ch.crc = cpu_to_le32(crc);
1451         /* Work out where data in the LEB ends and free space begins */
1452         p = c->sbuf;
1453         len = c->leb_size - 1;
1454         while (p[len] == 0xff)
1455                 len -= 1;
1456         len = ALIGN(len + 1, c->min_io_size);
1457         /* Atomically write the fixed LEB back again */
1458         err = ubifs_leb_change(c, lnum, c->sbuf, len);
1459         if (err)
1460                 goto out;
1461         dbg_rcvry("inode %lu at %d:%d size %lld -> %lld",
1462                   (unsigned long)e->inum, lnum, offs, i_size, e->d_size);
1463         return 0;
1464
1465 out:
1466         ubifs_warn(c, "inode %lu failed to fix size %lld -> %lld error %d",
1467                    (unsigned long)e->inum, e->i_size, e->d_size, err);
1468         return err;
1469 }
1470 #endif
1471
1472 /**
1473  * ubifs_recover_size - recover inode size.
1474  * @c: UBIFS file-system description object
1475  *
1476  * This function attempts to fix inode size discrepancies identified by the
1477  * 'ubifs_recover_size_accum()' function.
1478  *
1479  * This functions returns %0 on success and a negative error code on failure.
1480  */
1481 int ubifs_recover_size(struct ubifs_info *c)
1482 {
1483         struct rb_node *this = rb_first(&c->size_tree);
1484
1485         while (this) {
1486                 struct size_entry *e;
1487                 int err;
1488
1489                 e = rb_entry(this, struct size_entry, rb);
1490                 if (!e->exists) {
1491                         union ubifs_key key;
1492
1493                         ino_key_init(c, &key, e->inum);
1494                         err = ubifs_tnc_lookup(c, &key, c->sbuf);
1495                         if (err && err != -ENOENT)
1496                                 return err;
1497                         if (err == -ENOENT) {
1498                                 /* Remove data nodes that have no inode */
1499                                 dbg_rcvry("removing ino %lu",
1500                                           (unsigned long)e->inum);
1501                                 err = ubifs_tnc_remove_ino(c, e->inum);
1502                                 if (err)
1503                                         return err;
1504                         } else {
1505                                 struct ubifs_ino_node *ino = c->sbuf;
1506
1507                                 e->exists = 1;
1508                                 e->i_size = le64_to_cpu(ino->size);
1509                         }
1510                 }
1511
1512                 if (e->exists && e->i_size < e->d_size) {
1513                         if (c->ro_mount) {
1514                                 /* Fix the inode size and pin it in memory */
1515                                 struct inode *inode;
1516                                 struct ubifs_inode *ui;
1517
1518                                 ubifs_assert(!e->inode);
1519
1520                                 inode = ubifs_iget(c->vfs_sb, e->inum);
1521                                 if (IS_ERR(inode))
1522                                         return PTR_ERR(inode);
1523
1524                                 ui = ubifs_inode(inode);
1525                                 if (inode->i_size < e->d_size) {
1526                                         dbg_rcvry("ino %lu size %lld -> %lld",
1527                                                   (unsigned long)e->inum,
1528                                                   inode->i_size, e->d_size);
1529                                         inode->i_size = e->d_size;
1530                                         ui->ui_size = e->d_size;
1531                                         ui->synced_i_size = e->d_size;
1532                                         e->inode = inode;
1533                                         this = rb_next(this);
1534                                         continue;
1535                                 }
1536                                 iput(inode);
1537 #ifndef __UBOOT__
1538                         } else {
1539                                 /* Fix the size in place */
1540                                 err = fix_size_in_place(c, e);
1541                                 if (err)
1542                                         return err;
1543                                 if (e->inode)
1544                                         iput(e->inode);
1545 #endif
1546                         }
1547                 }
1548
1549                 this = rb_next(this);
1550                 rb_erase(&e->rb, &c->size_tree);
1551                 kfree(e);
1552         }
1553
1554         return 0;
1555 }