fs/ubifs/recovery.c

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