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->min_io_unit 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->min_io_size boundary.
 384  */
 385 static int is_last_write(const struct ubifs_info *c, void *buf, int offs)
 386 {
 387         int empty_offs, check_len;
 388         uint8_t *p;
 389
 390         /*
 391          * Round up to the next @c->min_io_size boundary i.e. @offs is in the
 392          * last wbuf written. After that should be empty space.
 393          */
 394         empty_offs = ALIGN(offs + 1, c->min_io_size);
 395         check_len = c->leb_size - empty_offs;
 396         p = buf + empty_offs - offs;
 397         return is_empty(p, check_len);
 398 }
 399
 400 /**
 401  * clean_buf - clean the data from an LEB sitting in a buffer.
 402  * @c: UBIFS file-system description object
 403  * @buf: buffer to clean
 404  * @lnum: LEB number to clean
 405  * @offs: offset from which to clean
 406  * @len: length of buffer
 407  *
 408  * This function pads up to the next min_io_size boundary (if there is one) and
 409  * sets empty space to all 0xff. @buf, @offs and @len are updated to the next
 410  * @c->min_io_size boundary.
 411  */
 412 static void clean_buf(const struct ubifs_info *c, void **buf, int lnum,
 413                       int *offs, int *len)
 414 {
 415         int empty_offs, pad_len;
 416
 417         lnum = lnum;
 418         dbg_rcvry("cleaning corruption at %d:%d", lnum, *offs);
 419
 420         ubifs_assert(!(*offs & 7));
 421         empty_offs = ALIGN(*offs, c->min_io_size);
 422         pad_len = empty_offs - *offs;
 423         ubifs_pad(c, *buf, pad_len);
 424         *offs += pad_len;
 425         *buf += pad_len;
 426         *len -= pad_len;
 427         memset(*buf, 0xff, c->leb_size - empty_offs);
 428 }
 429
 430 /**
 431  * no_more_nodes - determine if there are no more nodes in a buffer.
 432  * @c: UBIFS file-system description object
 433  * @buf: buffer to check
 434  * @len: length of buffer
 435  * @lnum: LEB number of the LEB from which @buf was read
 436  * @offs: offset from which @buf was read
 437  *
 438  * This function ensures that the corrupted node at @offs is the last thing
 439  * written to a LEB. This function returns %1 if more data is not found and
 440  * %0 if more data is found.
 441  */
 442 static int no_more_nodes(const struct ubifs_info *c, void *buf, int len,
 443                         int lnum, int offs)
 444 {
 445         struct ubifs_ch *ch = buf;
 446         int skip, dlen = le32_to_cpu(ch->len);
 447
 448         /* Check for empty space after the corrupt node's common header */
 449         skip = ALIGN(offs + UBIFS_CH_SZ, c->min_io_size) - offs;
 450         if (is_empty(buf + skip, len - skip))
 451                 return 1;
 452         /*
 453          * The area after the common header size is not empty, so the common
 454          * header must be intact. Check it.
 455          */
 456         if (ubifs_check_node(c, buf, lnum, offs, 1, 0) != -EUCLEAN) {
 457                 dbg_rcvry("unexpected bad common header at %d:%d", lnum, offs);
 458                 return 0;
 459         }
 460         /* Now we know the corrupt node's length we can skip over it */
 461         skip = ALIGN(offs + dlen, c->min_io_size) - offs;
 462         /* After which there should be empty space */
 463         if (is_empty(buf + skip, len - skip))
 464                 return 1;
 465         dbg_rcvry("unexpected data at %d:%d", lnum, offs + skip);
 466         return 0;
 467 }
 468
 469 /**
 470  * fix_unclean_leb - fix an unclean LEB.
 471  * @c: UBIFS file-system description object
 472  * @sleb: scanned LEB information
 473  * @start: offset where scan started
 474  */
 475 static int fix_unclean_leb(struct ubifs_info *c, struct ubifs_scan_leb *sleb,
 476                            int start)
 477 {
 478         int lnum = sleb->lnum, endpt = start;
 479
 480         /* Get the end offset of the last node we are keeping */
 481         if (!list_empty(&sleb->nodes)) {
 482                 struct ubifs_scan_node *snod;
 483
 484                 snod = list_entry(sleb->nodes.prev,
 485                                   struct ubifs_scan_node, list);
 486                 endpt = snod->offs + snod->len;
 487         }
 488
 489         if (c->ro_mount && !c->remounting_rw) {
 490                 /* Add to recovery list */
 491                 struct ubifs_unclean_leb *ucleb;
 492
 493                 dbg_rcvry("need to fix LEB %d start %d endpt %d",
 494                           lnum, start, sleb->endpt);
 495                 ucleb = kzalloc(sizeof(struct ubifs_unclean_leb), GFP_NOFS);
 496                 if (!ucleb)
 497                         return -ENOMEM;
 498                 ucleb->lnum = lnum;
 499                 ucleb->endpt = endpt;
 500                 list_add_tail(&ucleb->list, &c->unclean_leb_list);
 501         } else {
 502                 /* Write the fixed LEB back to flash */
 503                 int err;
 504
 505                 dbg_rcvry("fixing LEB %d start %d endpt %d",
 506                           lnum, start, sleb->endpt);
 507                 if (endpt == 0) {
 508                         err = ubifs_leb_unmap(c, lnum);
 509                         if (err)
 510                                 return err;
 511                 } else {
 512                         int len = ALIGN(endpt, c->min_io_size);
 513
 514                         if (start) {
 515                                 err = ubi_read(c->ubi, lnum, sleb->buf, 0,
 516                                                start);
 517                                 if (err)
 518                                         return err;
 519                         }
 520                         /* Pad to min_io_size */
 521                         if (len > endpt) {
 522                                 int pad_len = len - ALIGN(endpt, 8);
 523
 524                                 if (pad_len > 0) {
 525                                         void *buf = sleb->buf + len - pad_len;
 526
 527                                         ubifs_pad(c, buf, pad_len);
 528                                 }
 529                         }
 530                         err = ubi_leb_change(c->ubi, lnum, sleb->buf, len,
 531                                              UBI_UNKNOWN);
 532                         if (err)
 533                                 return err;
 534                 }
 535         }
 536         return 0;
 537 }
 538
 539 /**
 540  * drop_incomplete_group - drop nodes from an incomplete group.
 541  * @sleb: scanned LEB information
 542  * @offs: offset of dropped nodes is returned here
 543  *
 544  * This function returns %1 if nodes are dropped and %0 otherwise.
 545  */
 546 static int drop_incomplete_group(struct ubifs_scan_leb *sleb, int *offs)
 547 {
 548         int dropped = 0;
 549
 550         while (!list_empty(&sleb->nodes)) {
 551                 struct ubifs_scan_node *snod;
 552                 struct ubifs_ch *ch;
 553
 554                 snod = list_entry(sleb->nodes.prev, struct ubifs_scan_node,
 555                                   list);
 556                 ch = snod->node;
 557                 if (ch->group_type != UBIFS_IN_NODE_GROUP)
 558                         return dropped;
 559                 dbg_rcvry("dropping node at %d:%d", sleb->lnum, snod->offs);
 560                 *offs = snod->offs;
 561                 list_del(&snod->list);
 562                 kfree(snod);
 563                 sleb->nodes_cnt -= 1;
 564                 dropped = 1;
 565         }
 566         return dropped;
 567 }
 568
 569 /**
 570  * ubifs_recover_leb - scan and recover a LEB.
 571  * @c: UBIFS file-system description object
 572  * @lnum: LEB number
 573  * @offs: offset
 574  * @sbuf: LEB-sized buffer to use
 575  * @grouped: nodes may be grouped for recovery
 576  *
 577  * This function does a scan of a LEB, but caters for errors that might have
 578  * been caused by the unclean unmount from which we are attempting to recover.
 579  * Returns %0 in case of success, %-EUCLEAN if an unrecoverable corruption is
 580  * found, and a negative error code in case of failure.
 581  */
 582 struct ubifs_scan_leb *ubifs_recover_leb(struct ubifs_info *c, int lnum,
 583                                          int offs, void *sbuf, int grouped)
 584 {
 585         int err, len = c->leb_size - offs, need_clean = 0, quiet = 1;
 586         int empty_chkd = 0, start = offs;
 587         struct ubifs_scan_leb *sleb;
 588         void *buf = sbuf + offs;
 589
 590         dbg_rcvry("%d:%d", lnum, offs);
 591
 592         sleb = ubifs_start_scan(c, lnum, offs, sbuf);
 593         if (IS_ERR(sleb))
 594                 return sleb;
 595
 596         if (sleb->ecc)
 597                 need_clean = 1;
 598
 599         while (len >= 8) {
 600                 int ret;
 601
 602                 dbg_scan("look at LEB %d:%d (%d bytes left)",
 603                          lnum, offs, len);
 604
 605                 cond_resched();
 606
 607                 /*
 608                  * Scan quietly until there is an error from which we cannot
 609                  * recover
 610                  */
 611                 ret = ubifs_scan_a_node(c, buf, len, lnum, offs, quiet);
 612
 613                 if (ret == SCANNED_A_NODE) {
 614                         /* A valid node, and not a padding node */
 615                         struct ubifs_ch *ch = buf;
 616                         int node_len;
 617
 618                         err = ubifs_add_snod(c, sleb, buf, offs);
 619                         if (err)
 620                                 goto error;
 621                         node_len = ALIGN(le32_to_cpu(ch->len), 8);
 622                         offs += node_len;
 623                         buf += node_len;
 624                         len -= node_len;
 625                         continue;
 626                 }
 627
 628                 if (ret > 0) {
 629                         /* Padding bytes or a valid padding node */
 630                         offs += ret;
 631                         buf += ret;
 632                         len -= ret;
 633                         continue;
 634                 }
 635
 636                 if (ret == SCANNED_EMPTY_SPACE) {
 637                         if (!is_empty(buf, len)) {
 638                                 if (!is_last_write(c, buf, offs))
 639                                         break;
 640                                 clean_buf(c, &buf, lnum, &offs, &len);
 641                                 need_clean = 1;
 642                         }
 643                         empty_chkd = 1;
 644                         break;
 645                 }
 646
 647                 if (ret == SCANNED_GARBAGE || ret == SCANNED_A_BAD_PAD_NODE)
 648                         if (is_last_write(c, buf, offs)) {
 649                                 clean_buf(c, &buf, lnum, &offs, &len);
 650                                 need_clean = 1;
 651                                 empty_chkd = 1;
 652                                 break;
 653                         }
 654
 655                 if (ret == SCANNED_A_CORRUPT_NODE)
 656                         if (no_more_nodes(c, buf, len, lnum, offs)) {
 657                                 clean_buf(c, &buf, lnum, &offs, &len);
 658                                 need_clean = 1;
 659                                 empty_chkd = 1;
 660                                 break;
 661                         }
 662
 663                 if (quiet) {
 664                         /* Redo the last scan but noisily */
 665                         quiet = 0;
 666                         continue;
 667                 }
 668
 669                 switch (ret) {
 670                 case SCANNED_GARBAGE:
 671                         dbg_err("garbage");
 672                         goto corrupted;
 673                 case SCANNED_A_CORRUPT_NODE:
 674                 case SCANNED_A_BAD_PAD_NODE:
 675                         dbg_err("bad node");
 676                         goto corrupted;
 677                 default:
 678                         dbg_err("unknown");
 679                         err = -EINVAL;
 680                         goto error;
 681                 }
 682         }
 683
 684         if (!empty_chkd && !is_empty(buf, len)) {
 685                 if (is_last_write(c, buf, offs)) {
 686                         clean_buf(c, &buf, lnum, &offs, &len);
 687                         need_clean = 1;
 688                 } else {
 689                         int corruption = first_non_ff(buf, len);
 690
 691                         /*
 692                          * See header comment for this file for more
 693                          * explanations about the reasons we have this check.
 694                          */
 695                         ubifs_err("corrupt empty space LEB %d:%d, corruption "
 696                                   "starts at %d", lnum, offs, corruption);
 697                         /* Make sure we dump interesting non-0xFF data */
 698                         offs = corruption;
 699                         buf += corruption;
 700                         goto corrupted;
 701                 }
 702         }
 703
 704         /* Drop nodes from incomplete group */
 705         if (grouped && drop_incomplete_group(sleb, &offs)) {
 706                 buf = sbuf + offs;
 707                 len = c->leb_size - offs;
 708                 clean_buf(c, &buf, lnum, &offs, &len);
 709                 need_clean = 1;
 710         }
 711
 712         if (offs % c->min_io_size) {
 713                 clean_buf(c, &buf, lnum, &offs, &len);
 714                 need_clean = 1;
 715         }
 716
 717         ubifs_end_scan(c, sleb, lnum, offs);
 718
 719         if (need_clean) {
 720                 err = fix_unclean_leb(c, sleb, start);
 721                 if (err)
 722                         goto error;
 723         }
 724
 725         return sleb;
 726
 727 corrupted:
 728         ubifs_scanned_corruption(c, lnum, offs, buf);
 729         err = -EUCLEAN;
 730 error:
 731         ubifs_err("LEB %d scanning failed", lnum);
 732         ubifs_scan_destroy(sleb);
 733         return ERR_PTR(err);
 734 }
 735
 736 /**
 737  * get_cs_sqnum - get commit start sequence number.
 738  * @c: UBIFS file-system description object
 739  * @lnum: LEB number of commit start node
 740  * @offs: offset of commit start node
 741  * @cs_sqnum: commit start sequence number is returned here
 742  *
 743  * This function returns %0 on success and a negative error code on failure.
 744  */
 745 static int get_cs_sqnum(struct ubifs_info *c, int lnum, int offs,
 746                         unsigned long long *cs_sqnum)
 747 {
 748         struct ubifs_cs_node *cs_node = NULL;
 749         int err, ret;
 750
 751         dbg_rcvry("at %d:%d", lnum, offs);
 752         cs_node = kmalloc(UBIFS_CS_NODE_SZ, GFP_KERNEL);
 753         if (!cs_node)
 754                 return -ENOMEM;
 755         if (c->leb_size - offs < UBIFS_CS_NODE_SZ)
 756                 goto out_err;
 757         err = ubi_read(c->ubi, lnum, (void *)cs_node, offs, UBIFS_CS_NODE_SZ);
 758         if (err && err != -EBADMSG)
 759                 goto out_free;
 760         ret = ubifs_scan_a_node(c, cs_node, UBIFS_CS_NODE_SZ, lnum, offs, 0);
 761         if (ret != SCANNED_A_NODE) {
 762                 dbg_err("Not a valid node");
 763                 goto out_err;
 764         }
 765         if (cs_node->ch.node_type != UBIFS_CS_NODE) {
 766                 dbg_err("Node a CS node, type is %d", cs_node->ch.node_type);
 767                 goto out_err;
 768         }
 769         if (le64_to_cpu(cs_node->cmt_no) != c->cmt_no) {
 770                 dbg_err("CS node cmt_no %llu != current cmt_no %llu",
 771                         (unsigned long long)le64_to_cpu(cs_node->cmt_no),
 772                         c->cmt_no);
 773                 goto out_err;
 774         }
 775         *cs_sqnum = le64_to_cpu(cs_node->ch.sqnum);
 776         dbg_rcvry("commit start sqnum %llu", *cs_sqnum);
 777         kfree(cs_node);
 778         return 0;
 779
 780 out_err:
 781         err = -EINVAL;
 782 out_free:
 783         ubifs_err("failed to get CS sqnum");
 784         kfree(cs_node);
 785         return err;
 786 }
 787
 788 /**
 789  * ubifs_recover_log_leb - scan and recover a log LEB.
 790  * @c: UBIFS file-system description object
 791  * @lnum: LEB number
 792  * @offs: offset
 793  * @sbuf: LEB-sized buffer to use
 794  *
 795  * This function does a scan of a LEB, but caters for errors that might have
 796  * been caused by unclean reboots from which we are attempting to recover
 797  * (assume that only the last log LEB can be corrupted by an unclean reboot).
 798  *
 799  * This function returns %0 on success and a negative error code on failure.
 800  */
 801 struct ubifs_scan_leb *ubifs_recover_log_leb(struct ubifs_info *c, int lnum,
 802                                              int offs, void *sbuf)
 803 {
 804         struct ubifs_scan_leb *sleb;
 805         int next_lnum;
 806
 807         dbg_rcvry("LEB %d", lnum);
 808         next_lnum = lnum + 1;
 809         if (next_lnum >= UBIFS_LOG_LNUM + c->log_lebs)
 810                 next_lnum = UBIFS_LOG_LNUM;
 811         if (next_lnum != c->ltail_lnum) {
 812                 /*
 813                  * We can only recover at the end of the log, so check that the
 814                  * next log LEB is empty or out of date.
 815                  */
 816                 sleb = ubifs_scan(c, next_lnum, 0, sbuf, 0);
 817                 if (IS_ERR(sleb))
 818                         return sleb;
 819                 if (sleb->nodes_cnt) {
 820                         struct ubifs_scan_node *snod;
 821                         unsigned long long cs_sqnum = c->cs_sqnum;
 822
 823                         snod = list_entry(sleb->nodes.next,
 824                                           struct ubifs_scan_node, list);
 825                         if (cs_sqnum == 0) {
 826                                 int err;
 827
 828                                 err = get_cs_sqnum(c, lnum, offs, &cs_sqnum);
 829                                 if (err) {
 830                                         ubifs_scan_destroy(sleb);
 831                                         return ERR_PTR(err);
 832                                 }
 833                         }
 834                         if (snod->sqnum > cs_sqnum) {
 835                                 ubifs_err("unrecoverable log corruption "
 836                                           "in LEB %d", lnum);
 837                                 ubifs_scan_destroy(sleb);
 838                                 return ERR_PTR(-EUCLEAN);
 839                         }
 840                 }
 841                 ubifs_scan_destroy(sleb);
 842         }
 843         return ubifs_recover_leb(c, lnum, offs, sbuf, 0);
 844 }
 845
 846 /**
 847  * recover_head - recover a head.
 848  * @c: UBIFS file-system description object
 849  * @lnum: LEB number of head to recover
 850  * @offs: offset of head to recover
 851  * @sbuf: LEB-sized buffer to use
 852  *
 853  * This function ensures that there is no data on the flash at a head location.
 854  *
 855  * This function returns %0 on success and a negative error code on failure.
 856  */
 857 static int recover_head(const struct ubifs_info *c, int lnum, int offs,
 858                         void *sbuf)
 859 {
 860         int len, err;
 861
 862         if (c->min_io_size > 1)
 863                 len = c->min_io_size;
 864         else
 865                 len = 512;
 866         if (offs + len > c->leb_size)
 867                 len = c->leb_size - offs;
 868
 869         if (!len)
 870                 return 0;
 871
 872         /* Read at the head location and check it is empty flash */
 873         err = ubi_read(c->ubi, lnum, sbuf, offs, len);
 874         if (err || !is_empty(sbuf, len)) {
 875                 dbg_rcvry("cleaning head at %d:%d", lnum, offs);
 876                 if (offs == 0)
 877                         return ubifs_leb_unmap(c, lnum);
 878                 err = ubi_read(c->ubi, lnum, sbuf, 0, offs);
 879                 if (err)
 880                         return err;
 881                 return ubi_leb_change(c->ubi, lnum, sbuf, offs, UBI_UNKNOWN);
 882         }
 883
 884         return 0;
 885 }
 886
 887 /**
 888  * ubifs_recover_inl_heads - recover index and LPT heads.
 889  * @c: UBIFS file-system description object
 890  * @sbuf: LEB-sized buffer to use
 891  *
 892  * This function ensures that there is no data on the flash at the index and
 893  * LPT head locations.
 894  *
 895  * This deals with the recovery of a half-completed journal commit. UBIFS is
 896  * careful never to overwrite the last version of the index or the LPT. Because
 897  * the index and LPT are wandering trees, data from a half-completed commit will
 898  * not be referenced anywhere in UBIFS. The data will be either in LEBs that are
 899  * assumed to be empty and will be unmapped anyway before use, or in the index
 900  * and LPT heads.
 901  *
 902  * This function returns %0 on success and a negative error code on failure.
 903  */
 904 int ubifs_recover_inl_heads(const struct ubifs_info *c, void *sbuf)
 905 {
 906         int err;
 907
 908         ubifs_assert(!c->ro_mount || c->remounting_rw);
 909
 910         dbg_rcvry("checking index head at %d:%d", c->ihead_lnum, c->ihead_offs);
 911         err = recover_head(c, c->ihead_lnum, c->ihead_offs, sbuf);
 912         if (err)
 913                 return err;
 914
 915         dbg_rcvry("checking LPT head at %d:%d", c->nhead_lnum, c->nhead_offs);
 916         err = recover_head(c, c->nhead_lnum, c->nhead_offs, sbuf);
 917         if (err)
 918                 return err;
 919
 920         return 0;
 921 }
 922
 923 /**
 924  *  clean_an_unclean_leb - read and write a LEB to remove corruption.
 925  * @c: UBIFS file-system description object
 926  * @ucleb: unclean LEB information
 927  * @sbuf: LEB-sized buffer to use
 928  *
 929  * This function reads a LEB up to a point pre-determined by the mount recovery,
 930  * checks the nodes, and writes the result back to the flash, thereby cleaning
 931  * off any following corruption, or non-fatal ECC errors.
 932  *
 933  * This function returns %0 on success and a negative error code on failure.
 934  */
 935 static int clean_an_unclean_leb(const struct ubifs_info *c,
 936                                 struct ubifs_unclean_leb *ucleb, void *sbuf)
 937 {
 938         int err, lnum = ucleb->lnum, offs = 0, len = ucleb->endpt, quiet = 1;
 939         void *buf = sbuf;
 940
 941         dbg_rcvry("LEB %d len %d", lnum, len);
 942
 943         if (len == 0) {
 944                 /* Nothing to read, just unmap it */
 945                 err = ubifs_leb_unmap(c, lnum);
 946                 if (err)
 947                         return err;
 948                 return 0;
 949         }
 950
 951         err = ubi_read(c->ubi, lnum, buf, offs, len);
 952         if (err && err != -EBADMSG)
 953                 return err;
 954
 955         while (len >= 8) {
 956                 int ret;
 957
 958                 cond_resched();
 959
 960                 /* Scan quietly until there is an error */
 961                 ret = ubifs_scan_a_node(c, buf, len, lnum, offs, quiet);
 962
 963                 if (ret == SCANNED_A_NODE) {
 964                         /* A valid node, and not a padding node */
 965                         struct ubifs_ch *ch = buf;
 966                         int node_len;
 967
 968                         node_len = ALIGN(le32_to_cpu(ch->len), 8);
 969                         offs += node_len;
 970                         buf += node_len;
 971                         len -= node_len;
 972                         continue;
 973                 }
 974
 975                 if (ret > 0) {
 976                         /* Padding bytes or a valid padding node */
 977                         offs += ret;
 978                         buf += ret;
 979                         len -= ret;
 980                         continue;
 981                 }
 982
 983                 if (ret == SCANNED_EMPTY_SPACE) {
 984                         ubifs_err("unexpected empty space at %d:%d",
 985                                   lnum, offs);
 986                         return -EUCLEAN;
 987                 }
 988
 989                 if (quiet) {
 990                         /* Redo the last scan but noisily */
 991                         quiet = 0;
 992                         continue;
 993                 }
 994
 995                 ubifs_scanned_corruption(c, lnum, offs, buf);
 996                 return -EUCLEAN;
 997         }
 998
 999         /* Pad to min_io_size */
1000         len = ALIGN(ucleb->endpt, c->min_io_size);
1001         if (len > ucleb->endpt) {
1002                 int pad_len = len - ALIGN(ucleb->endpt, 8);
1003
1004                 if (pad_len > 0) {
1005                         buf = c->sbuf + len - pad_len;
1006                         ubifs_pad(c, buf, pad_len);
1007                 }
1008         }
1009
1010         /* Write back the LEB atomically */
1011         err = ubi_leb_change(c->ubi, lnum, sbuf, len, UBI_UNKNOWN);
1012         if (err)
1013                 return err;
1014
1015         dbg_rcvry("cleaned LEB %d", lnum);
1016
1017         return 0;
1018 }
1019
1020 /**
1021  * ubifs_clean_lebs - clean LEBs recovered during read-only mount.
1022  * @c: UBIFS file-system description object
1023  * @sbuf: LEB-sized buffer to use
1024  *
1025  * This function cleans a LEB identified during recovery that needs to be
1026  * written but was not because UBIFS was mounted read-only. This happens when
1027  * remounting to read-write mode.
1028  *
1029  * This function returns %0 on success and a negative error code on failure.
1030  */
1031 int ubifs_clean_lebs(const struct ubifs_info *c, void *sbuf)
1032 {
1033         dbg_rcvry("recovery");
1034         while (!list_empty(&c->unclean_leb_list)) {
1035                 struct ubifs_unclean_leb *ucleb;
1036                 int err;
1037
1038                 ucleb = list_entry(c->unclean_leb_list.next,
1039                                    struct ubifs_unclean_leb, list);
1040                 err = clean_an_unclean_leb(c, ucleb, sbuf);
1041                 if (err)
1042                         return err;
1043                 list_del(&ucleb->list);
1044                 kfree(ucleb);
1045         }
1046         return 0;
1047 }
1048
1049 /**
1050  * ubifs_rcvry_gc_commit - recover the GC LEB number and run the commit.
1051  * @c: UBIFS file-system description object
1052  *
1053  * Out-of-place garbage collection requires always one empty LEB with which to
1054  * start garbage collection. The LEB number is recorded in c->gc_lnum and is
1055  * written to the master node on unmounting. In the case of an unclean unmount
1056  * the value of gc_lnum recorded in the master node is out of date and cannot
1057  * be used. Instead, recovery must allocate an empty LEB for this purpose.
1058  * However, there may not be enough empty space, in which case it must be
1059  * possible to GC the dirtiest LEB into the GC head LEB.
1060  *
1061  * This function also runs the commit which causes the TNC updates from
1062  * size-recovery and orphans to be written to the flash. That is important to
1063  * ensure correct replay order for subsequent mounts.
1064  *
1065  * This function returns %0 on success and a negative error code on failure.
1066  */
1067 int ubifs_rcvry_gc_commit(struct ubifs_info *c)
1068 {
1069         struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
1070         struct ubifs_lprops lp;
1071         int lnum, err;
1072
1073         c->gc_lnum = -1;
1074         if (wbuf->lnum == -1) {
1075                 dbg_rcvry("no GC head LEB");
1076                 goto find_free;
1077         }
1078         /*
1079          * See whether the used space in the dirtiest LEB fits in the GC head
1080          * LEB.
1081          */
1082         if (wbuf->offs == c->leb_size) {
1083                 dbg_rcvry("no room in GC head LEB");
1084                 goto find_free;
1085         }
1086         err = ubifs_find_dirty_leb(c, &lp, wbuf->offs, 2);
1087         if (err) {
1088                 /*
1089                  * There are no dirty or empty LEBs subject to here being
1090                  * enough for the index. Try to use
1091                  * 'ubifs_find_free_leb_for_idx()', which will return any empty
1092                  * LEBs (ignoring index requirements). If the index then
1093                  * doesn't have enough LEBs the recovery commit will fail -
1094                  * which is the  same result anyway i.e. recovery fails. So
1095                  * there is no problem ignoring index  requirements and just
1096                  * grabbing a free LEB since we have already established there
1097                  * is not a dirty LEB we could have used instead.
1098                  */
1099                 if (err == -ENOSPC) {
1100                         dbg_rcvry("could not find a dirty LEB");
1101                         goto find_free;
1102                 }
1103                 return err;
1104         }
1105         ubifs_assert(!(lp.flags & LPROPS_INDEX));
1106         lnum = lp.lnum;
1107         if (lp.free + lp.dirty == c->leb_size) {
1108                 /* An empty LEB was returned */
1109                 if (lp.free != c->leb_size) {
1110                         err = ubifs_change_one_lp(c, lnum, c->leb_size,
1111                                                   0, 0, 0, 0);
1112                         if (err)
1113                                 return err;
1114                 }
1115                 err = ubifs_leb_unmap(c, lnum);
1116                 if (err)
1117                         return err;
1118                 c->gc_lnum = lnum;
1119                 dbg_rcvry("allocated LEB %d for GC", lnum);
1120                 /* Run the commit */
1121                 dbg_rcvry("committing");
1122                 return ubifs_run_commit(c);
1123         }
1124         /*
1125          * There was no empty LEB so the used space in the dirtiest LEB must fit
1126          * in the GC head LEB.
1127          */
1128         if (lp.free + lp.dirty < wbuf->offs) {
1129                 dbg_rcvry("LEB %d doesn't fit in GC head LEB %d:%d",
1130                           lnum, wbuf->lnum, wbuf->offs);
1131                 err = ubifs_return_leb(c, lnum);
1132                 if (err)
1133                         return err;
1134                 goto find_free;
1135         }
1136         /*
1137          * We run the commit before garbage collection otherwise subsequent
1138          * mounts will see the GC and orphan deletion in a different order.
1139          */
1140         dbg_rcvry("committing");
1141         err = ubifs_run_commit(c);
1142         if (err)
1143                 return err;
1144         /*
1145          * The data in the dirtiest LEB fits in the GC head LEB, so do the GC
1146          * - use locking to keep 'ubifs_assert()' happy.
1147          */
1148         dbg_rcvry("GC'ing LEB %d", lnum);
1149         mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead);
1150         err = ubifs_garbage_collect_leb(c, &lp);
1151         if (err >= 0) {
1152                 int err2 = ubifs_wbuf_sync_nolock(wbuf);
1153
1154                 if (err2)
1155                         err = err2;
1156         }
1157         mutex_unlock(&wbuf->io_mutex);
1158         if (err < 0) {
1159                 dbg_err("GC failed, error %d", err);
1160                 if (err == -EAGAIN)
1161                         err = -EINVAL;
1162                 return err;
1163         }
1164         if (err != LEB_RETAINED) {
1165                 dbg_err("GC returned %d", err);
1166                 return -EINVAL;
1167         }
1168         err = ubifs_leb_unmap(c, c->gc_lnum);
1169         if (err)
1170                 return err;
1171         dbg_rcvry("allocated LEB %d for GC", lnum);
1172         return 0;
1173
1174 find_free:
1175         /*
1176          * There is no GC head LEB or the free space in the GC head LEB is too
1177          * small, or there are not dirty LEBs. Allocate gc_lnum by calling
1178          * 'ubifs_find_free_leb_for_idx()' so GC is not run.
1179          */
1180         lnum = ubifs_find_free_leb_for_idx(c);
1181         if (lnum < 0) {
1182                 dbg_err("could not find an empty LEB");
1183                 return lnum;
1184         }
1185         /* And reset the index flag */
1186         err = ubifs_change_one_lp(c, lnum, LPROPS_NC, LPROPS_NC, 0,
1187                                   LPROPS_INDEX, 0);
1188         if (err)
1189                 return err;
1190         c->gc_lnum = lnum;
1191         dbg_rcvry("allocated LEB %d for GC", lnum);
1192         /* Run the commit */
1193         dbg_rcvry("committing");
1194         return ubifs_run_commit(c);
1195 }
1196
1197 /**
1198  * struct size_entry - inode size information for recovery.
1199  * @rb: link in the RB-tree of sizes
1200  * @inum: inode number
1201  * @i_size: size on inode
1202  * @d_size: maximum size based on data nodes
1203  * @exists: indicates whether the inode exists
1204  * @inode: inode if pinned in memory awaiting rw mode to fix it
1205  */
1206 struct size_entry {
1207         struct rb_node rb;
1208         ino_t inum;
1209         loff_t i_size;
1210         loff_t d_size;
1211         int exists;
1212         struct inode *inode;
1213 };
1214
1215 /**
1216  * add_ino - add an entry to the size tree.
1217  * @c: UBIFS file-system description object
1218  * @inum: inode number
1219  * @i_size: size on inode
1220  * @d_size: maximum size based on data nodes
1221  * @exists: indicates whether the inode exists
1222  */
1223 static int add_ino(struct ubifs_info *c, ino_t inum, loff_t i_size,
1224                    loff_t d_size, int exists)
1225 {
1226         struct rb_node **p = &c->size_tree.rb_node, *parent = NULL;
1227         struct size_entry *e;
1228
1229         while (*p) {
1230                 parent = *p;
1231                 e = rb_entry(parent, struct size_entry, rb);
1232                 if (inum < e->inum)
1233                         p = &(*p)->rb_left;
1234                 else
1235                         p = &(*p)->rb_right;
1236         }
1237
1238         e = kzalloc(sizeof(struct size_entry), GFP_KERNEL);
1239         if (!e)
1240                 return -ENOMEM;
1241
1242         e->inum = inum;
1243         e->i_size = i_size;
1244         e->d_size = d_size;
1245         e->exists = exists;
1246
1247         rb_link_node(&e->rb, parent, p);
1248         rb_insert_color(&e->rb, &c->size_tree);
1249
1250         return 0;
1251 }
1252
1253 /**
1254  * find_ino - find an entry on the size tree.
1255  * @c: UBIFS file-system description object
1256  * @inum: inode number
1257  */
1258 static struct size_entry *find_ino(struct ubifs_info *c, ino_t inum)
1259 {
1260         struct rb_node *p = c->size_tree.rb_node;
1261         struct size_entry *e;
1262
1263         while (p) {
1264                 e = rb_entry(p, struct size_entry, rb);
1265                 if (inum < e->inum)
1266                         p = p->rb_left;
1267                 else if (inum > e->inum)
1268                         p = p->rb_right;
1269                 else
1270                         return e;
1271         }
1272         return NULL;
1273 }
1274
1275 /**
1276  * remove_ino - remove an entry from the size tree.
1277  * @c: UBIFS file-system description object
1278  * @inum: inode number
1279  */
1280 static void remove_ino(struct ubifs_info *c, ino_t inum)
1281 {
1282         struct size_entry *e = find_ino(c, inum);
1283
1284         if (!e)
1285                 return;
1286         rb_erase(&e->rb, &c->size_tree);
1287         kfree(e);
1288 }
1289
1290 /**
1291  * ubifs_destroy_size_tree - free resources related to the size tree.
1292  * @c: UBIFS file-system description object
1293  */
1294 void ubifs_destroy_size_tree(struct ubifs_info *c)
1295 {
1296         struct rb_node *this = c->size_tree.rb_node;
1297         struct size_entry *e;
1298
1299         while (this) {
1300                 if (this->rb_left) {
1301                         this = this->rb_left;
1302                         continue;
1303                 } else if (this->rb_right) {
1304                         this = this->rb_right;
1305                         continue;
1306                 }
1307                 e = rb_entry(this, struct size_entry, rb);
1308                 if (e->inode)
1309                         iput(e->inode);
1310                 this = rb_parent(this);
1311                 if (this) {
1312                         if (this->rb_left == &e->rb)
1313                                 this->rb_left = NULL;
1314                         else
1315                                 this->rb_right = NULL;
1316                 }
1317                 kfree(e);
1318         }
1319         c->size_tree = RB_ROOT;
1320 }
1321
1322 /**
1323  * ubifs_recover_size_accum - accumulate inode sizes for recovery.
1324  * @c: UBIFS file-system description object
1325  * @key: node key
1326  * @deletion: node is for a deletion
1327  * @new_size: inode size
1328  *
1329  * This function has two purposes:
1330  *     1) to ensure there are no data nodes that fall outside the inode size
1331  *     2) to ensure there are no data nodes for inodes that do not exist
1332  * To accomplish those purposes, a rb-tree is constructed containing an entry
1333  * for each inode number in the journal that has not been deleted, and recording
1334  * the size from the inode node, the maximum size of any data node (also altered
1335  * by truncations) and a flag indicating a inode number for which no inode node
1336  * was present in the journal.
1337  *
1338  * Note that there is still the possibility that there are data nodes that have
1339  * been committed that are beyond the inode size, however the only way to find
1340  * them would be to scan the entire index. Alternatively, some provision could
1341  * be made to record the size of inodes at the start of commit, which would seem
1342  * very cumbersome for a scenario that is quite unlikely and the only negative
1343  * consequence of which is wasted space.
1344  *
1345  * This functions returns %0 on success and a negative error code on failure.
1346  */
1347 int ubifs_recover_size_accum(struct ubifs_info *c, union ubifs_key *key,
1348                              int deletion, loff_t new_size)
1349 {
1350         ino_t inum = key_inum(c, key);
1351         struct size_entry *e;
1352         int err;
1353
1354         switch (key_type(c, key)) {
1355         case UBIFS_INO_KEY:
1356                 if (deletion)
1357                         remove_ino(c, inum);
1358                 else {
1359                         e = find_ino(c, inum);
1360                         if (e) {
1361                                 e->i_size = new_size;
1362                                 e->exists = 1;
1363                         } else {
1364                                 err = add_ino(c, inum, new_size, 0, 1);
1365                                 if (err)
1366                                         return err;
1367                         }
1368                 }
1369                 break;
1370         case UBIFS_DATA_KEY:
1371                 e = find_ino(c, inum);
1372                 if (e) {
1373                         if (new_size > e->d_size)
1374                                 e->d_size = new_size;
1375                 } else {
1376                         err = add_ino(c, inum, 0, new_size, 0);
1377                         if (err)
1378                                 return err;
1379                 }
1380                 break;
1381         case UBIFS_TRUN_KEY:
1382                 e = find_ino(c, inum);
1383                 if (e)
1384                         e->d_size = new_size;
1385                 break;
1386         }
1387         return 0;
1388 }
1389
1390 /**
1391  * fix_size_in_place - fix inode size in place on flash.
1392  * @c: UBIFS file-system description object
1393  * @e: inode size information for recovery
1394  */
1395 static int fix_size_in_place(struct ubifs_info *c, struct size_entry *e)
1396 {
1397         struct ubifs_ino_node *ino = c->sbuf;
1398         unsigned char *p;
1399         union ubifs_key key;
1400         int err, lnum, offs, len;
1401         loff_t i_size;
1402         uint32_t crc;
1403
1404         /* Locate the inode node LEB number and offset */
1405         ino_key_init(c, &key, e->inum);
1406         err = ubifs_tnc_locate(c, &key, ino, &lnum, &offs);
1407         if (err)
1408                 goto out;
1409         /*
1410          * If the size recorded on the inode node is greater than the size that
1411          * was calculated from nodes in the journal then don't change the inode.
1412          */
1413         i_size = le64_to_cpu(ino->size);
1414         if (i_size >= e->d_size)
1415                 return 0;
1416         /* Read the LEB */
1417         err = ubi_read(c->ubi, lnum, c->sbuf, 0, c->leb_size);
1418         if (err)
1419                 goto out;
1420         /* Change the size field and recalculate the CRC */
1421         ino = c->sbuf + offs;
1422         ino->size = cpu_to_le64(e->d_size);
1423         len = le32_to_cpu(ino->ch.len);
1424         crc = crc32(UBIFS_CRC32_INIT, (void *)ino + 8, len - 8);
1425         ino->ch.crc = cpu_to_le32(crc);
1426         /* Work out where data in the LEB ends and free space begins */
1427         p = c->sbuf;
1428         len = c->leb_size - 1;
1429         while (p[len] == 0xff)
1430                 len -= 1;
1431         len = ALIGN(len + 1, c->min_io_size);
1432         /* Atomically write the fixed LEB back again */
1433         err = ubi_leb_change(c->ubi, lnum, c->sbuf, len, UBI_UNKNOWN);
1434         if (err)
1435                 goto out;
1436         dbg_rcvry("inode %lu at %d:%d size %lld -> %lld ",
1437                   (unsigned long)e->inum, lnum, offs, i_size, e->d_size);
1438         return 0;
1439
1440 out:
1441         ubifs_warn("inode %lu failed to fix size %lld -> %lld error %d",
1442                    (unsigned long)e->inum, e->i_size, e->d_size, err);
1443         return err;
1444 }
1445
1446 /**
1447  * ubifs_recover_size - recover inode size.
1448  * @c: UBIFS file-system description object
1449  *
1450  * This function attempts to fix inode size discrepancies identified by the
1451  * 'ubifs_recover_size_accum()' function.
1452  *
1453  * This functions returns %0 on success and a negative error code on failure.
1454  */
1455 int ubifs_recover_size(struct ubifs_info *c)
1456 {
1457         struct rb_node *this = rb_first(&c->size_tree);
1458
1459         while (this) {
1460                 struct size_entry *e;
1461                 int err;
1462
1463                 e = rb_entry(this, struct size_entry, rb);
1464                 if (!e->exists) {
1465                         union ubifs_key key;
1466
1467                         ino_key_init(c, &key, e->inum);
1468                         err = ubifs_tnc_lookup(c, &key, c->sbuf);
1469                         if (err && err != -ENOENT)
1470                                 return err;
1471                         if (err == -ENOENT) {
1472                                 /* Remove data nodes that have no inode */
1473                                 dbg_rcvry("removing ino %lu",
1474                                           (unsigned long)e->inum);
1475                                 err = ubifs_tnc_remove_ino(c, e->inum);
1476                                 if (err)
1477                                         return err;
1478                         } else {
1479                                 struct ubifs_ino_node *ino = c->sbuf;
1480
1481                                 e->exists = 1;
1482                                 e->i_size = le64_to_cpu(ino->size);
1483                         }
1484                 }
1485                 if (e->exists && e->i_size < e->d_size) {
1486                         if (!e->inode && c->ro_mount) {
1487                                 /* Fix the inode size and pin it in memory */
1488                                 struct inode *inode;
1489
1490                                 inode = ubifs_iget(c->vfs_sb, e->inum);
1491                                 if (IS_ERR(inode))
1492                                         return PTR_ERR(inode);
1493                                 if (inode->i_size < e->d_size) {
1494                                         dbg_rcvry("ino %lu size %lld -> %lld",
1495                                                   (unsigned long)e->inum,
1496                                                   e->d_size, inode->i_size);
1497                                         inode->i_size = e->d_size;
1498                                         ubifs_inode(inode)->ui_size = e->d_size;
1499                                         e->inode = inode;
1500                                         this = rb_next(this);
1501                                         continue;
1502                                 }
1503                                 iput(inode);
1504                         } else {
1505                                 /* Fix the size in place */
1506                                 err = fix_size_in_place(c, e);
1507                                 if (err)
1508                                         return err;
1509                                 if (e->inode)
1510                                         iput(e->inode);
1511                         }
1512                 }
1513                 this = rb_next(this);
1514                 rb_erase(&e->rb, &c->size_tree);
1515                 kfree(e);
1516         }
1517         return 0;
1518 }