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 sucessfully. If not, the process of mounting
  27  * incorparates 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
  33 #include "ubifs.h"
  34
  35 /**
  36  * is_empty - determine whether a buffer is empty (contains all 0xff).
  37  * @buf: buffer to clean
  38  * @len: length of buffer
  39  *
  40  * This function returns %1 if the buffer is empty (contains all 0xff) otherwise
  41  * %0 is returned.
  42  */
  43 static int is_empty(void *buf, int len)
  44 {
  45         uint8_t *p = buf;
  46         int i;
  47
  48         for (i = 0; i < len; i++)
  49                 if (*p++ != 0xff)
  50                         return 0;
  51         return 1;
  52 }
  53
  54 /**
  55  * get_master_node - get the last valid master node allowing for corruption.
  56  * @c: UBIFS file-system description object
  57  * @lnum: LEB number
  58  * @pbuf: buffer containing the LEB read, is returned here
  59  * @mst: master node, if found, is returned here
  60  * @cor: corruption, if found, is returned here
  61  *
  62  * This function allocates a buffer, reads the LEB into it, and finds and
  63  * returns the last valid master node allowing for one area of corruption.
  64  * The corrupt area, if there is one, must be consistent with the assumption
  65  * that it is the result of an unclean unmount while the master node was being
  66  * written. Under those circumstances, it is valid to use the previously written
  67  * master node.
  68  *
  69  * This function returns %0 on success and a negative error code on failure.
  70  */
  71 static int get_master_node(const struct ubifs_info *c, int lnum, void **pbuf,
  72                            struct ubifs_mst_node **mst, void **cor)
  73 {
  74         const int sz = c->mst_node_alsz;
  75         int err, offs, len;
  76         void *sbuf, *buf;
  77
  78         sbuf = vmalloc(c->leb_size);
  79         if (!sbuf)
  80                 return -ENOMEM;
  81
  82         err = ubi_read(c->ubi, lnum, sbuf, 0, c->leb_size);
  83         if (err && err != -EBADMSG)
  84                 goto out_free;
  85
  86         /* Find the first position that is definitely not a node */
  87         offs = 0;
  88         buf = sbuf;
  89         len = c->leb_size;
  90         while (offs + UBIFS_MST_NODE_SZ <= c->leb_size) {
  91                 struct ubifs_ch *ch = buf;
  92
  93                 if (le32_to_cpu(ch->magic) != UBIFS_NODE_MAGIC)
  94                         break;
  95                 offs += sz;
  96                 buf  += sz;
  97                 len  -= sz;
  98         }
  99         /* See if there was a valid master node before that */
 100         if (offs) {
 101                 int ret;
 102
 103                 offs -= sz;
 104                 buf  -= sz;
 105                 len  += sz;
 106                 ret = ubifs_scan_a_node(c, buf, len, lnum, offs, 1);
 107                 if (ret != SCANNED_A_NODE && offs) {
 108                         /* Could have been corruption so check one place back */
 109                         offs -= sz;
 110                         buf  -= sz;
 111                         len  += sz;
 112                         ret = ubifs_scan_a_node(c, buf, len, lnum, offs, 1);
 113                         if (ret != SCANNED_A_NODE)
 114                                 /*
 115                                  * We accept only one area of corruption because
 116                                  * we are assuming that it was caused while
 117                                  * trying to write a master node.
 118                                  */
 119                                 goto out_err;
 120                 }
 121                 if (ret == SCANNED_A_NODE) {
 122                         struct ubifs_ch *ch = buf;
 123
 124                         if (ch->node_type != UBIFS_MST_NODE)
 125                                 goto out_err;
 126                         dbg_rcvry("found a master node at %d:%d", lnum, offs);
 127                         *mst = buf;
 128                         offs += sz;
 129                         buf  += sz;
 130                         len  -= sz;
 131                 }
 132         }
 133         /* Check for corruption */
 134         if (offs < c->leb_size) {
 135                 if (!is_empty(buf, min_t(int, len, sz))) {
 136                         *cor = buf;
 137                         dbg_rcvry("found corruption at %d:%d", lnum, offs);
 138                 }
 139                 offs += sz;
 140                 buf  += sz;
 141                 len  -= sz;
 142         }
 143         /* Check remaining empty space */
 144         if (offs < c->leb_size)
 145                 if (!is_empty(buf, len))
 146                         goto out_err;
 147         *pbuf = sbuf;
 148         return 0;
 149
 150 out_err:
 151         err = -EINVAL;
 152 out_free:
 153         vfree(sbuf);
 154         *mst = NULL;
 155         *cor = NULL;
 156         return err;
 157 }
 158
 159 /**
 160  * write_rcvrd_mst_node - write recovered master node.
 161  * @c: UBIFS file-system description object
 162  * @mst: master node
 163  *
 164  * This function returns %0 on success and a negative error code on failure.
 165  */
 166 static int write_rcvrd_mst_node(struct ubifs_info *c,
 167                                 struct ubifs_mst_node *mst)
 168 {
 169         int err = 0, lnum = UBIFS_MST_LNUM, sz = c->mst_node_alsz;
 170         __le32 save_flags;
 171
 172         dbg_rcvry("recovery");
 173
 174         save_flags = mst->flags;
 175         mst->flags |= cpu_to_le32(UBIFS_MST_RCVRY);
 176
 177         ubifs_prepare_node(c, mst, UBIFS_MST_NODE_SZ, 1);
 178         err = ubi_leb_change(c->ubi, lnum, mst, sz, UBI_SHORTTERM);
 179         if (err)
 180                 goto out;
 181         err = ubi_leb_change(c->ubi, lnum + 1, mst, sz, UBI_SHORTTERM);
 182         if (err)
 183                 goto out;
 184 out:
 185         mst->flags = save_flags;
 186         return err;
 187 }
 188
 189 /**
 190  * ubifs_recover_master_node - recover the master node.
 191  * @c: UBIFS file-system description object
 192  *
 193  * This function recovers the master node from corruption that may occur due to
 194  * an unclean unmount.
 195  *
 196  * This function returns %0 on success and a negative error code on failure.
 197  */
 198 int ubifs_recover_master_node(struct ubifs_info *c)
 199 {
 200         void *buf1 = NULL, *buf2 = NULL, *cor1 = NULL, *cor2 = NULL;
 201         struct ubifs_mst_node *mst1 = NULL, *mst2 = NULL, *mst;
 202         const int sz = c->mst_node_alsz;
 203         int err, offs1, offs2;
 204
 205         dbg_rcvry("recovery");
 206
 207         err = get_master_node(c, UBIFS_MST_LNUM, &buf1, &mst1, &cor1);
 208         if (err)
 209                 goto out_free;
 210
 211         err = get_master_node(c, UBIFS_MST_LNUM + 1, &buf2, &mst2, &cor2);
 212         if (err)
 213                 goto out_free;
 214
 215         if (mst1) {
 216                 offs1 = (void *)mst1 - buf1;
 217                 if ((le32_to_cpu(mst1->flags) & UBIFS_MST_RCVRY) &&
 218                     (offs1 == 0 && !cor1)) {
 219                         /*
 220                          * mst1 was written by recovery at offset 0 with no
 221                          * corruption.
 222                          */
 223                         dbg_rcvry("recovery recovery");
 224                         mst = mst1;
 225                 } else if (mst2) {
 226                         offs2 = (void *)mst2 - buf2;
 227                         if (offs1 == offs2) {
 228                                 /* Same offset, so must be the same */
 229                                 if (memcmp((void *)mst1 + UBIFS_CH_SZ,
 230                                            (void *)mst2 + UBIFS_CH_SZ,
 231                                            UBIFS_MST_NODE_SZ - UBIFS_CH_SZ))
 232                                         goto out_err;
 233                                 mst = mst1;
 234                         } else if (offs2 + sz == offs1) {
 235                                 /* 1st LEB was written, 2nd was not */
 236                                 if (cor1)
 237                                         goto out_err;
 238                                 mst = mst1;
 239                         } else if (offs1 == 0 && offs2 + sz >= c->leb_size) {
 240                                 /* 1st LEB was unmapped and written, 2nd not */
 241                                 if (cor1)
 242                                         goto out_err;
 243                                 mst = mst1;
 244                         } else
 245                                 goto out_err;
 246                 } else {
 247                         /*
 248                          * 2nd LEB was unmapped and about to be written, so
 249                          * there must be only one master node in the first LEB
 250                          * and no corruption.
 251                          */
 252                         if (offs1 != 0 || cor1)
 253                                 goto out_err;
 254                         mst = mst1;
 255                 }
 256         } else {
 257                 if (!mst2)
 258                         goto out_err;
 259                 /*
 260                  * 1st LEB was unmapped and about to be written, so there must
 261                  * be no room left in 2nd LEB.
 262                  */
 263                 offs2 = (void *)mst2 - buf2;
 264                 if (offs2 + sz + sz <= c->leb_size)
 265                         goto out_err;
 266                 mst = mst2;
 267         }
 268
 269         dbg_rcvry("recovered master node from LEB %d",
 270                   (mst == mst1 ? UBIFS_MST_LNUM : UBIFS_MST_LNUM + 1));
 271
 272         memcpy(c->mst_node, mst, UBIFS_MST_NODE_SZ);
 273
 274         if ((c->vfs_sb->s_flags & MS_RDONLY)) {
 275                 /* Read-only mode. Keep a copy for switching to rw mode */
 276                 c->rcvrd_mst_node = kmalloc(sz, GFP_KERNEL);
 277                 if (!c->rcvrd_mst_node) {
 278                         err = -ENOMEM;
 279                         goto out_free;
 280                 }
 281                 memcpy(c->rcvrd_mst_node, c->mst_node, UBIFS_MST_NODE_SZ);
 282         }
 283
 284         vfree(buf2);
 285         vfree(buf1);
 286
 287         return 0;
 288
 289 out_err:
 290         err = -EINVAL;
 291 out_free:
 292         ubifs_err("failed to recover master node");
 293         if (mst1) {
 294                 dbg_err("dumping first master node");
 295                 dbg_dump_node(c, mst1);
 296         }
 297         if (mst2) {
 298                 dbg_err("dumping second master node");
 299                 dbg_dump_node(c, mst2);
 300         }
 301         vfree(buf2);
 302         vfree(buf1);
 303         return err;
 304 }
 305
 306 /**
 307  * ubifs_write_rcvrd_mst_node - write the recovered master node.
 308  * @c: UBIFS file-system description object
 309  *
 310  * This function writes the master node that was recovered during mounting in
 311  * read-only mode and must now be written because we are remounting rw.
 312  *
 313  * This function returns %0 on success and a negative error code on failure.
 314  */
 315 int ubifs_write_rcvrd_mst_node(struct ubifs_info *c)
 316 {
 317         int err;
 318
 319         if (!c->rcvrd_mst_node)
 320                 return 0;
 321         c->rcvrd_mst_node->flags |= cpu_to_le32(UBIFS_MST_DIRTY);
 322         c->mst_node->flags |= cpu_to_le32(UBIFS_MST_DIRTY);
 323         err = write_rcvrd_mst_node(c, c->rcvrd_mst_node);
 324         if (err)
 325                 return err;
 326         kfree(c->rcvrd_mst_node);
 327         c->rcvrd_mst_node = NULL;
 328         return 0;
 329 }
 330
 331 /**
 332  * is_last_write - determine if an offset was in the last write to a LEB.
 333  * @c: UBIFS file-system description object
 334  * @buf: buffer to check
 335  * @offs: offset to check
 336  *
 337  * This function returns %1 if @offs was in the last write to the LEB whose data
 338  * is in @buf, otherwise %0 is returned.  The determination is made by checking
 339  * for subsequent empty space starting from the next min_io_size boundary (or a
 340  * bit less than the common header size if min_io_size is one).
 341  */
 342 static int is_last_write(const struct ubifs_info *c, void *buf, int offs)
 343 {
 344         int empty_offs;
 345         int check_len;
 346         uint8_t *p;
 347
 348         if (c->min_io_size == 1) {
 349                 check_len = c->leb_size - offs;
 350                 p = buf + check_len;
 351                 for (; check_len > 0; check_len--)
 352                         if (*--p != 0xff)
 353                                 break;
 354                 /*
 355                  * 'check_len' is the size of the corruption which cannot be
 356                  * more than the size of 1 node if it was caused by an unclean
 357                  * unmount.
 358                  */
 359                 if (check_len > UBIFS_MAX_NODE_SZ)
 360                         return 0;
 361                 return 1;
 362         }
 363
 364         /*
 365          * Round up to the next c->min_io_size boundary i.e. 'offs' is in the
 366          * last wbuf written. After that should be empty space.
 367          */
 368         empty_offs = ALIGN(offs + 1, c->min_io_size);
 369         check_len = c->leb_size - empty_offs;
 370         p = buf + empty_offs - offs;
 371
 372         for (; check_len > 0; check_len--)
 373                 if (*p++ != 0xff)
 374                         return 0;
 375         return 1;
 376 }
 377
 378 /**
 379  * clean_buf - clean the data from an LEB sitting in a buffer.
 380  * @c: UBIFS file-system description object
 381  * @buf: buffer to clean
 382  * @lnum: LEB number to clean
 383  * @offs: offset from which to clean
 384  * @len: length of buffer
 385  *
 386  * This function pads up to the next min_io_size boundary (if there is one) and
 387  * sets empty space to all 0xff. @buf, @offs and @len are updated to the next
 388  * min_io_size boundary (if there is one).
 389  */
 390 static void clean_buf(const struct ubifs_info *c, void **buf, int lnum,
 391                       int *offs, int *len)
 392 {
 393         int empty_offs, pad_len;
 394
 395         lnum = lnum;
 396         dbg_rcvry("cleaning corruption at %d:%d", lnum, *offs);
 397
 398         if (c->min_io_size == 1) {
 399                 memset(*buf, 0xff, c->leb_size - *offs);
 400                 return;
 401         }
 402
 403         ubifs_assert(!(*offs & 7));
 404         empty_offs = ALIGN(*offs, c->min_io_size);
 405         pad_len = empty_offs - *offs;
 406         ubifs_pad(c, *buf, pad_len);
 407         *offs += pad_len;
 408         *buf += pad_len;
 409         *len -= pad_len;
 410         memset(*buf, 0xff, c->leb_size - empty_offs);
 411 }
 412
 413 /**
 414  * no_more_nodes - determine if there are no more nodes in a buffer.
 415  * @c: UBIFS file-system description object
 416  * @buf: buffer to check
 417  * @len: length of buffer
 418  * @lnum: LEB number of the LEB from which @buf was read
 419  * @offs: offset from which @buf was read
 420  *
 421  * This function scans @buf for more nodes and returns %0 is a node is found and
 422  * %1 if no more nodes are found.
 423  */
 424 static int no_more_nodes(const struct ubifs_info *c, void *buf, int len,
 425                         int lnum, int offs)
 426 {
 427         int skip, next_offs = 0;
 428
 429         if (len > UBIFS_DATA_NODE_SZ) {
 430                 struct ubifs_ch *ch = buf;
 431                 int dlen = le32_to_cpu(ch->len);
 432
 433                 if (ch->node_type == UBIFS_DATA_NODE && dlen >= UBIFS_CH_SZ &&
 434                     dlen <= UBIFS_MAX_DATA_NODE_SZ)
 435                         /* The corrupt node looks like a data node */
 436                         next_offs = ALIGN(offs + dlen, 8);
 437         }
 438
 439         if (c->min_io_size == 1)
 440                 skip = 8;
 441         else
 442                 skip = ALIGN(offs + 1, c->min_io_size) - offs;
 443
 444         offs += skip;
 445         buf += skip;
 446         len -= skip;
 447         while (len > 8) {
 448                 struct ubifs_ch *ch = buf;
 449                 uint32_t magic = le32_to_cpu(ch->magic);
 450                 int ret;
 451
 452                 if (magic == UBIFS_NODE_MAGIC) {
 453                         ret = ubifs_scan_a_node(c, buf, len, lnum, offs, 1);
 454                         if (ret == SCANNED_A_NODE || ret > 0) {
 455                                 /*
 456                                  * There is a small chance this is just data in
 457                                  * a data node, so check that possibility. e.g.
 458                                  * this is part of a file that itself contains
 459                                  * a UBIFS image.
 460                                  */
 461                                 if (next_offs && offs + le32_to_cpu(ch->len) <=
 462                                     next_offs)
 463                                         continue;
 464                                 dbg_rcvry("unexpected node at %d:%d", lnum,
 465                                           offs);
 466                                 return 0;
 467                         }
 468                 }
 469                 offs += 8;
 470                 buf += 8;
 471                 len -= 8;
 472         }
 473         return 1;
 474 }
 475
 476 /**
 477  * fix_unclean_leb - fix an unclean LEB.
 478  * @c: UBIFS file-system description object
 479  * @sleb: scanned LEB information
 480  * @start: offset where scan started
 481  */
 482 static int fix_unclean_leb(struct ubifs_info *c, struct ubifs_scan_leb *sleb,
 483                            int start)
 484 {
 485         int lnum = sleb->lnum, endpt = start;
 486
 487         /* Get the end offset of the last node we are keeping */
 488         if (!list_empty(&sleb->nodes)) {
 489                 struct ubifs_scan_node *snod;
 490
 491                 snod = list_entry(sleb->nodes.prev,
 492                                   struct ubifs_scan_node, list);
 493                 endpt = snod->offs + snod->len;
 494         }
 495
 496         if ((c->vfs_sb->s_flags & MS_RDONLY) && !c->remounting_rw) {
 497                 /* Add to recovery list */
 498                 struct ubifs_unclean_leb *ucleb;
 499
 500                 dbg_rcvry("need to fix LEB %d start %d endpt %d",
 501                           lnum, start, sleb->endpt);
 502                 ucleb = kzalloc(sizeof(struct ubifs_unclean_leb), GFP_NOFS);
 503                 if (!ucleb)
 504                         return -ENOMEM;
 505                 ucleb->lnum = lnum;
 506                 ucleb->endpt = endpt;
 507                 list_add_tail(&ucleb->list, &c->unclean_leb_list);
 508         }
 509         return 0;
 510 }
 511
 512 /**
 513  * drop_incomplete_group - drop nodes from an incomplete group.
 514  * @sleb: scanned LEB information
 515  * @offs: offset of dropped nodes is returned here
 516  *
 517  * This function returns %1 if nodes are dropped and %0 otherwise.
 518  */
 519 static int drop_incomplete_group(struct ubifs_scan_leb *sleb, int *offs)
 520 {
 521         int dropped = 0;
 522
 523         while (!list_empty(&sleb->nodes)) {
 524                 struct ubifs_scan_node *snod;
 525                 struct ubifs_ch *ch;
 526
 527                 snod = list_entry(sleb->nodes.prev, struct ubifs_scan_node,
 528                                   list);
 529                 ch = snod->node;
 530                 if (ch->group_type != UBIFS_IN_NODE_GROUP)
 531                         return dropped;
 532                 dbg_rcvry("dropping node at %d:%d", sleb->lnum, snod->offs);
 533                 *offs = snod->offs;
 534                 list_del(&snod->list);
 535                 kfree(snod);
 536                 sleb->nodes_cnt -= 1;
 537                 dropped = 1;
 538         }
 539         return dropped;
 540 }
 541
 542 /**
 543  * ubifs_recover_leb - scan and recover a LEB.
 544  * @c: UBIFS file-system description object
 545  * @lnum: LEB number
 546  * @offs: offset
 547  * @sbuf: LEB-sized buffer to use
 548  * @grouped: nodes may be grouped for recovery
 549  *
 550  * This function does a scan of a LEB, but caters for errors that might have
 551  * been caused by the unclean unmount from which we are attempting to recover.
 552  *
 553  * This function returns %0 on success and a negative error code on failure.
 554  */
 555 struct ubifs_scan_leb *ubifs_recover_leb(struct ubifs_info *c, int lnum,
 556                                          int offs, void *sbuf, int grouped)
 557 {
 558         int err, len = c->leb_size - offs, need_clean = 0, quiet = 1;
 559         int empty_chkd = 0, start = offs;
 560         struct ubifs_scan_leb *sleb;
 561         void *buf = sbuf + offs;
 562
 563         dbg_rcvry("%d:%d", lnum, offs);
 564
 565         sleb = ubifs_start_scan(c, lnum, offs, sbuf);
 566         if (IS_ERR(sleb))
 567                 return sleb;
 568
 569         if (sleb->ecc)
 570                 need_clean = 1;
 571
 572         while (len >= 8) {
 573                 int ret;
 574
 575                 dbg_scan("look at LEB %d:%d (%d bytes left)",
 576                          lnum, offs, len);
 577
 578                 cond_resched();
 579
 580                 /*
 581                  * Scan quietly until there is an error from which we cannot
 582                  * recover
 583                  */
 584                 ret = ubifs_scan_a_node(c, buf, len, lnum, offs, quiet);
 585
 586                 if (ret == SCANNED_A_NODE) {
 587                         /* A valid node, and not a padding node */
 588                         struct ubifs_ch *ch = buf;
 589                         int node_len;
 590
 591                         err = ubifs_add_snod(c, sleb, buf, offs);
 592                         if (err)
 593                                 goto error;
 594                         node_len = ALIGN(le32_to_cpu(ch->len), 8);
 595                         offs += node_len;
 596                         buf += node_len;
 597                         len -= node_len;
 598                         continue;
 599                 }
 600
 601                 if (ret > 0) {
 602                         /* Padding bytes or a valid padding node */
 603                         offs += ret;
 604                         buf += ret;
 605                         len -= ret;
 606                         continue;
 607                 }
 608
 609                 if (ret == SCANNED_EMPTY_SPACE) {
 610                         if (!is_empty(buf, len)) {
 611                                 if (!is_last_write(c, buf, offs))
 612                                         break;
 613                                 clean_buf(c, &buf, lnum, &offs, &len);
 614                                 need_clean = 1;
 615                         }
 616                         empty_chkd = 1;
 617                         break;
 618                 }
 619
 620                 if (ret == SCANNED_GARBAGE || ret == SCANNED_A_BAD_PAD_NODE)
 621                         if (is_last_write(c, buf, offs)) {
 622                                 clean_buf(c, &buf, lnum, &offs, &len);
 623                                 need_clean = 1;
 624                                 empty_chkd = 1;
 625                                 break;
 626                         }
 627
 628                 if (ret == SCANNED_A_CORRUPT_NODE)
 629                         if (no_more_nodes(c, buf, len, lnum, offs)) {
 630                                 clean_buf(c, &buf, lnum, &offs, &len);
 631                                 need_clean = 1;
 632                                 empty_chkd = 1;
 633                                 break;
 634                         }
 635
 636                 if (quiet) {
 637                         /* Redo the last scan but noisily */
 638                         quiet = 0;
 639                         continue;
 640                 }
 641
 642                 switch (ret) {
 643                 case SCANNED_GARBAGE:
 644                         dbg_err("garbage");
 645                         goto corrupted;
 646                 case SCANNED_A_CORRUPT_NODE:
 647                 case SCANNED_A_BAD_PAD_NODE:
 648                         dbg_err("bad node");
 649                         goto corrupted;
 650                 default:
 651                         dbg_err("unknown");
 652                         goto corrupted;
 653                 }
 654         }
 655
 656         if (!empty_chkd && !is_empty(buf, len)) {
 657                 if (is_last_write(c, buf, offs)) {
 658                         clean_buf(c, &buf, lnum, &offs, &len);
 659                         need_clean = 1;
 660                 } else {
 661                         ubifs_err("corrupt empty space at LEB %d:%d",
 662                                   lnum, offs);
 663                         goto corrupted;
 664                 }
 665         }
 666
 667         /* Drop nodes from incomplete group */
 668         if (grouped && drop_incomplete_group(sleb, &offs)) {
 669                 buf = sbuf + offs;
 670                 len = c->leb_size - offs;
 671                 clean_buf(c, &buf, lnum, &offs, &len);
 672                 need_clean = 1;
 673         }
 674
 675         if (offs % c->min_io_size) {
 676                 clean_buf(c, &buf, lnum, &offs, &len);
 677                 need_clean = 1;
 678         }
 679
 680         ubifs_end_scan(c, sleb, lnum, offs);
 681
 682         if (need_clean) {
 683                 err = fix_unclean_leb(c, sleb, start);
 684                 if (err)
 685                         goto error;
 686         }
 687
 688         return sleb;
 689
 690 corrupted:
 691         ubifs_scanned_corruption(c, lnum, offs, buf);
 692         err = -EUCLEAN;
 693 error:
 694         ubifs_err("LEB %d scanning failed", lnum);
 695         ubifs_scan_destroy(sleb);
 696         return ERR_PTR(err);
 697 }
 698
 699 /**
 700  * get_cs_sqnum - get commit start sequence number.
 701  * @c: UBIFS file-system description object
 702  * @lnum: LEB number of commit start node
 703  * @offs: offset of commit start node
 704  * @cs_sqnum: commit start sequence number is returned here
 705  *
 706  * This function returns %0 on success and a negative error code on failure.
 707  */
 708 static int get_cs_sqnum(struct ubifs_info *c, int lnum, int offs,
 709                         unsigned long long *cs_sqnum)
 710 {
 711         struct ubifs_cs_node *cs_node = NULL;
 712         int err, ret;
 713
 714         dbg_rcvry("at %d:%d", lnum, offs);
 715         cs_node = kmalloc(UBIFS_CS_NODE_SZ, GFP_KERNEL);
 716         if (!cs_node)
 717                 return -ENOMEM;
 718         if (c->leb_size - offs < UBIFS_CS_NODE_SZ)
 719                 goto out_err;
 720         err = ubi_read(c->ubi, lnum, (void *)cs_node, offs, UBIFS_CS_NODE_SZ);
 721         if (err && err != -EBADMSG)
 722                 goto out_free;
 723         ret = ubifs_scan_a_node(c, cs_node, UBIFS_CS_NODE_SZ, lnum, offs, 0);
 724         if (ret != SCANNED_A_NODE) {
 725                 dbg_err("Not a valid node");
 726                 goto out_err;
 727         }
 728         if (cs_node->ch.node_type != UBIFS_CS_NODE) {
 729                 dbg_err("Node a CS node, type is %d", cs_node->ch.node_type);
 730                 goto out_err;
 731         }
 732         if (le64_to_cpu(cs_node->cmt_no) != c->cmt_no) {
 733                 dbg_err("CS node cmt_no %llu != current cmt_no %llu",
 734                         (unsigned long long)le64_to_cpu(cs_node->cmt_no),
 735                         c->cmt_no);
 736                 goto out_err;
 737         }
 738         *cs_sqnum = le64_to_cpu(cs_node->ch.sqnum);
 739         dbg_rcvry("commit start sqnum %llu", *cs_sqnum);
 740         kfree(cs_node);
 741         return 0;
 742
 743 out_err:
 744         err = -EINVAL;
 745 out_free:
 746         ubifs_err("failed to get CS sqnum");
 747         kfree(cs_node);
 748         return err;
 749 }
 750
 751 /**
 752  * ubifs_recover_log_leb - scan and recover a log LEB.
 753  * @c: UBIFS file-system description object
 754  * @lnum: LEB number
 755  * @offs: offset
 756  * @sbuf: LEB-sized buffer to use
 757  *
 758  * This function does a scan of a LEB, but caters for errors that might have
 759  * been caused by the unclean unmount from which we are attempting to recover.
 760  *
 761  * This function returns %0 on success and a negative error code on failure.
 762  */
 763 struct ubifs_scan_leb *ubifs_recover_log_leb(struct ubifs_info *c, int lnum,
 764                                              int offs, void *sbuf)
 765 {
 766         struct ubifs_scan_leb *sleb;
 767         int next_lnum;
 768
 769         dbg_rcvry("LEB %d", lnum);
 770         next_lnum = lnum + 1;
 771         if (next_lnum >= UBIFS_LOG_LNUM + c->log_lebs)
 772                 next_lnum = UBIFS_LOG_LNUM;
 773         if (next_lnum != c->ltail_lnum) {
 774                 /*
 775                  * We can only recover at the end of the log, so check that the
 776                  * next log LEB is empty or out of date.
 777                  */
 778                 sleb = ubifs_scan(c, next_lnum, 0, sbuf);
 779                 if (IS_ERR(sleb))
 780                         return sleb;
 781                 if (sleb->nodes_cnt) {
 782                         struct ubifs_scan_node *snod;
 783                         unsigned long long cs_sqnum = c->cs_sqnum;
 784
 785                         snod = list_entry(sleb->nodes.next,
 786                                           struct ubifs_scan_node, list);
 787                         if (cs_sqnum == 0) {
 788                                 int err;
 789
 790                                 err = get_cs_sqnum(c, lnum, offs, &cs_sqnum);
 791                                 if (err) {
 792                                         ubifs_scan_destroy(sleb);
 793                                         return ERR_PTR(err);
 794                                 }
 795                         }
 796                         if (snod->sqnum > cs_sqnum) {
 797                                 ubifs_err("unrecoverable log corruption "
 798                                           "in LEB %d", lnum);
 799                                 ubifs_scan_destroy(sleb);
 800                                 return ERR_PTR(-EUCLEAN);
 801                         }
 802                 }
 803                 ubifs_scan_destroy(sleb);
 804         }
 805         return ubifs_recover_leb(c, lnum, offs, sbuf, 0);
 806 }
 807
 808 /**
 809  * recover_head - recover a head.
 810  * @c: UBIFS file-system description object
 811  * @lnum: LEB number of head to recover
 812  * @offs: offset of head to recover
 813  * @sbuf: LEB-sized buffer to use
 814  *
 815  * This function ensures that there is no data on the flash at a head location.
 816  *
 817  * This function returns %0 on success and a negative error code on failure.
 818  */
 819 static int recover_head(const struct ubifs_info *c, int lnum, int offs,
 820                         void *sbuf)
 821 {
 822         int len, err, need_clean = 0;
 823
 824         if (c->min_io_size > 1)
 825                 len = c->min_io_size;
 826         else
 827                 len = 512;
 828         if (offs + len > c->leb_size)
 829                 len = c->leb_size - offs;
 830
 831         if (!len)
 832                 return 0;
 833
 834         /* Read at the head location and check it is empty flash */
 835         err = ubi_read(c->ubi, lnum, sbuf, offs, len);
 836         if (err)
 837                 need_clean = 1;
 838         else {
 839                 uint8_t *p = sbuf;
 840
 841                 while (len--)
 842                         if (*p++ != 0xff) {
 843                                 need_clean = 1;
 844                                 break;
 845                         }
 846         }
 847
 848         if (need_clean) {
 849                 dbg_rcvry("cleaning head at %d:%d", lnum, offs);
 850                 if (offs == 0)
 851                         return ubifs_leb_unmap(c, lnum);
 852                 err = ubi_read(c->ubi, lnum, sbuf, 0, offs);
 853                 if (err)
 854                         return err;
 855                 return ubi_leb_change(c->ubi, lnum, sbuf, offs, UBI_UNKNOWN);
 856         }
 857
 858         return 0;
 859 }
 860
 861 /**
 862  * ubifs_recover_inl_heads - recover index and LPT heads.
 863  * @c: UBIFS file-system description object
 864  * @sbuf: LEB-sized buffer to use
 865  *
 866  * This function ensures that there is no data on the flash at the index and
 867  * LPT head locations.
 868  *
 869  * This deals with the recovery of a half-completed journal commit. UBIFS is
 870  * careful never to overwrite the last version of the index or the LPT. Because
 871  * the index and LPT are wandering trees, data from a half-completed commit will
 872  * not be referenced anywhere in UBIFS. The data will be either in LEBs that are
 873  * assumed to be empty and will be unmapped anyway before use, or in the index
 874  * and LPT heads.
 875  *
 876  * This function returns %0 on success and a negative error code on failure.
 877  */
 878 int ubifs_recover_inl_heads(const struct ubifs_info *c, void *sbuf)
 879 {
 880         int err;
 881
 882         ubifs_assert(!(c->vfs_sb->s_flags & MS_RDONLY) || c->remounting_rw);
 883
 884         dbg_rcvry("checking index head at %d:%d", c->ihead_lnum, c->ihead_offs);
 885         err = recover_head(c, c->ihead_lnum, c->ihead_offs, sbuf);
 886         if (err)
 887                 return err;
 888
 889         dbg_rcvry("checking LPT head at %d:%d", c->nhead_lnum, c->nhead_offs);
 890         err = recover_head(c, c->nhead_lnum, c->nhead_offs, sbuf);
 891         if (err)
 892                 return err;
 893
 894         return 0;
 895 }
 896
 897 /**
 898  *  clean_an_unclean_leb - read and write a LEB to remove corruption.
 899  * @c: UBIFS file-system description object
 900  * @ucleb: unclean LEB information
 901  * @sbuf: LEB-sized buffer to use
 902  *
 903  * This function reads a LEB up to a point pre-determined by the mount recovery,
 904  * checks the nodes, and writes the result back to the flash, thereby cleaning
 905  * off any following corruption, or non-fatal ECC errors.
 906  *
 907  * This function returns %0 on success and a negative error code on failure.
 908  */
 909 static int clean_an_unclean_leb(const struct ubifs_info *c,
 910                                 struct ubifs_unclean_leb *ucleb, void *sbuf)
 911 {
 912         int err, lnum = ucleb->lnum, offs = 0, len = ucleb->endpt, quiet = 1;
 913         void *buf = sbuf;
 914
 915         dbg_rcvry("LEB %d len %d", lnum, len);
 916
 917         if (len == 0) {
 918                 /* Nothing to read, just unmap it */
 919                 err = ubifs_leb_unmap(c, lnum);
 920                 if (err)
 921                         return err;
 922                 return 0;
 923         }
 924
 925         err = ubi_read(c->ubi, lnum, buf, offs, len);
 926         if (err && err != -EBADMSG)
 927                 return err;
 928
 929         while (len >= 8) {
 930                 int ret;
 931
 932                 cond_resched();
 933
 934                 /* Scan quietly until there is an error */
 935                 ret = ubifs_scan_a_node(c, buf, len, lnum, offs, quiet);
 936
 937                 if (ret == SCANNED_A_NODE) {
 938                         /* A valid node, and not a padding node */
 939                         struct ubifs_ch *ch = buf;
 940                         int node_len;
 941
 942                         node_len = ALIGN(le32_to_cpu(ch->len), 8);
 943                         offs += node_len;
 944                         buf += node_len;
 945                         len -= node_len;
 946                         continue;
 947                 }
 948
 949                 if (ret > 0) {
 950                         /* Padding bytes or a valid padding node */
 951                         offs += ret;
 952                         buf += ret;
 953                         len -= ret;
 954                         continue;
 955                 }
 956
 957                 if (ret == SCANNED_EMPTY_SPACE) {
 958                         ubifs_err("unexpected empty space at %d:%d",
 959                                   lnum, offs);
 960                         return -EUCLEAN;
 961                 }
 962
 963                 if (quiet) {
 964                         /* Redo the last scan but noisily */
 965                         quiet = 0;
 966                         continue;
 967                 }
 968
 969                 ubifs_scanned_corruption(c, lnum, offs, buf);
 970                 return -EUCLEAN;
 971         }
 972
 973         /* Pad to min_io_size */
 974         len = ALIGN(ucleb->endpt, c->min_io_size);
 975         if (len > ucleb->endpt) {
 976                 int pad_len = len - ALIGN(ucleb->endpt, 8);
 977
 978                 if (pad_len > 0) {
 979                         buf = c->sbuf + len - pad_len;
 980                         ubifs_pad(c, buf, pad_len);
 981                 }
 982         }
 983
 984         /* Write back the LEB atomically */
 985         err = ubi_leb_change(c->ubi, lnum, sbuf, len, UBI_UNKNOWN);
 986         if (err)
 987                 return err;
 988
 989         dbg_rcvry("cleaned LEB %d", lnum);
 990
 991         return 0;
 992 }
 993
 994 /**
 995  * ubifs_clean_lebs - clean LEBs recovered during read-only mount.
 996  * @c: UBIFS file-system description object
 997  * @sbuf: LEB-sized buffer to use
 998  *
 999  * This function cleans a LEB identified during recovery that needs to be
1000  * written but was not because UBIFS was mounted read-only. This happens when
1001  * remounting to read-write mode.
1002  *
1003  * This function returns %0 on success and a negative error code on failure.
1004  */
1005 int ubifs_clean_lebs(const struct ubifs_info *c, void *sbuf)
1006 {
1007         dbg_rcvry("recovery");
1008         while (!list_empty(&c->unclean_leb_list)) {
1009                 struct ubifs_unclean_leb *ucleb;
1010                 int err;
1011
1012                 ucleb = list_entry(c->unclean_leb_list.next,
1013                                    struct ubifs_unclean_leb, list);
1014                 err = clean_an_unclean_leb(c, ucleb, sbuf);
1015                 if (err)
1016                         return err;
1017                 list_del(&ucleb->list);
1018                 kfree(ucleb);
1019         }
1020         return 0;
1021 }
1022
1023 /**
1024  * struct size_entry - inode size information for recovery.
1025  * @rb: link in the RB-tree of sizes
1026  * @inum: inode number
1027  * @i_size: size on inode
1028  * @d_size: maximum size based on data nodes
1029  * @exists: indicates whether the inode exists
1030  * @inode: inode if pinned in memory awaiting rw mode to fix it
1031  */
1032 struct size_entry {
1033         struct rb_node rb;
1034         ino_t inum;
1035         loff_t i_size;
1036         loff_t d_size;
1037         int exists;
1038         struct inode *inode;
1039 };
1040
1041 /**
1042  * add_ino - add an entry to the size tree.
1043  * @c: UBIFS file-system description object
1044  * @inum: inode number
1045  * @i_size: size on inode
1046  * @d_size: maximum size based on data nodes
1047  * @exists: indicates whether the inode exists
1048  */
1049 static int add_ino(struct ubifs_info *c, ino_t inum, loff_t i_size,
1050                    loff_t d_size, int exists)
1051 {
1052         struct rb_node **p = &c->size_tree.rb_node, *parent = NULL;
1053         struct size_entry *e;
1054
1055         while (*p) {
1056                 parent = *p;
1057                 e = rb_entry(parent, struct size_entry, rb);
1058                 if (inum < e->inum)
1059                         p = &(*p)->rb_left;
1060                 else
1061                         p = &(*p)->rb_right;
1062         }
1063
1064         e = kzalloc(sizeof(struct size_entry), GFP_KERNEL);
1065         if (!e)
1066                 return -ENOMEM;
1067
1068         e->inum = inum;
1069         e->i_size = i_size;
1070         e->d_size = d_size;
1071         e->exists = exists;
1072
1073         rb_link_node(&e->rb, parent, p);
1074         rb_insert_color(&e->rb, &c->size_tree);
1075
1076         return 0;
1077 }
1078
1079 /**
1080  * find_ino - find an entry on the size tree.
1081  * @c: UBIFS file-system description object
1082  * @inum: inode number
1083  */
1084 static struct size_entry *find_ino(struct ubifs_info *c, ino_t inum)
1085 {
1086         struct rb_node *p = c->size_tree.rb_node;
1087         struct size_entry *e;
1088
1089         while (p) {
1090                 e = rb_entry(p, struct size_entry, rb);
1091                 if (inum < e->inum)
1092                         p = p->rb_left;
1093                 else if (inum > e->inum)
1094                         p = p->rb_right;
1095                 else
1096                         return e;
1097         }
1098         return NULL;
1099 }
1100
1101 /**
1102  * remove_ino - remove an entry from the size tree.
1103  * @c: UBIFS file-system description object
1104  * @inum: inode number
1105  */
1106 static void remove_ino(struct ubifs_info *c, ino_t inum)
1107 {
1108         struct size_entry *e = find_ino(c, inum);
1109
1110         if (!e)
1111                 return;
1112         rb_erase(&e->rb, &c->size_tree);
1113         kfree(e);
1114 }
1115
1116 /**
1117  * ubifs_recover_size_accum - accumulate inode sizes for recovery.
1118  * @c: UBIFS file-system description object
1119  * @key: node key
1120  * @deletion: node is for a deletion
1121  * @new_size: inode size
1122  *
1123  * This function has two purposes:
1124  *     1) to ensure there are no data nodes that fall outside the inode size
1125  *     2) to ensure there are no data nodes for inodes that do not exist
1126  * To accomplish those purposes, a rb-tree is constructed containing an entry
1127  * for each inode number in the journal that has not been deleted, and recording
1128  * the size from the inode node, the maximum size of any data node (also altered
1129  * by truncations) and a flag indicating a inode number for which no inode node
1130  * was present in the journal.
1131  *
1132  * Note that there is still the possibility that there are data nodes that have
1133  * been committed that are beyond the inode size, however the only way to find
1134  * them would be to scan the entire index. Alternatively, some provision could
1135  * be made to record the size of inodes at the start of commit, which would seem
1136  * very cumbersome for a scenario that is quite unlikely and the only negative
1137  * consequence of which is wasted space.
1138  *
1139  * This functions returns %0 on success and a negative error code on failure.
1140  */
1141 int ubifs_recover_size_accum(struct ubifs_info *c, union ubifs_key *key,
1142                              int deletion, loff_t new_size)
1143 {
1144         ino_t inum = key_inum(c, key);
1145         struct size_entry *e;
1146         int err;
1147
1148         switch (key_type(c, key)) {
1149         case UBIFS_INO_KEY:
1150                 if (deletion)
1151                         remove_ino(c, inum);
1152                 else {
1153                         e = find_ino(c, inum);
1154                         if (e) {
1155                                 e->i_size = new_size;
1156                                 e->exists = 1;
1157                         } else {
1158                                 err = add_ino(c, inum, new_size, 0, 1);
1159                                 if (err)
1160                                         return err;
1161                         }
1162                 }
1163                 break;
1164         case UBIFS_DATA_KEY:
1165                 e = find_ino(c, inum);
1166                 if (e) {
1167                         if (new_size > e->d_size)
1168                                 e->d_size = new_size;
1169                 } else {
1170                         err = add_ino(c, inum, 0, new_size, 0);
1171                         if (err)
1172                                 return err;
1173                 }
1174                 break;
1175         case UBIFS_TRUN_KEY:
1176                 e = find_ino(c, inum);
1177                 if (e)
1178                         e->d_size = new_size;
1179                 break;
1180         }
1181         return 0;
1182 }
1183
1184 /**
1185  * ubifs_recover_size - recover inode size.
1186  * @c: UBIFS file-system description object
1187  *
1188  * This function attempts to fix inode size discrepancies identified by the
1189  * 'ubifs_recover_size_accum()' function.
1190  *
1191  * This functions returns %0 on success and a negative error code on failure.
1192  */
1193 int ubifs_recover_size(struct ubifs_info *c)
1194 {
1195         struct rb_node *this = rb_first(&c->size_tree);
1196
1197         while (this) {
1198                 struct size_entry *e;
1199                 int err;
1200
1201                 e = rb_entry(this, struct size_entry, rb);
1202                 if (!e->exists) {
1203                         union ubifs_key key;
1204
1205                         ino_key_init(c, &key, e->inum);
1206                         err = ubifs_tnc_lookup(c, &key, c->sbuf);
1207                         if (err && err != -ENOENT)
1208                                 return err;
1209                         if (err == -ENOENT) {
1210                                 /* Remove data nodes that have no inode */
1211                                 dbg_rcvry("removing ino %lu",
1212                                           (unsigned long)e->inum);
1213                                 err = ubifs_tnc_remove_ino(c, e->inum);
1214                                 if (err)
1215                                         return err;
1216                         } else {
1217                                 struct ubifs_ino_node *ino = c->sbuf;
1218
1219                                 e->exists = 1;
1220                                 e->i_size = le64_to_cpu(ino->size);
1221                         }
1222                 }
1223                 if (e->exists && e->i_size < e->d_size) {
1224                         if (!e->inode && (c->vfs_sb->s_flags & MS_RDONLY)) {
1225                                 /* Fix the inode size and pin it in memory */
1226                                 struct inode *inode;
1227
1228                                 inode = ubifs_iget(c->vfs_sb, e->inum);
1229                                 if (IS_ERR(inode))
1230                                         return PTR_ERR(inode);
1231                                 if (inode->i_size < e->d_size) {
1232                                         dbg_rcvry("ino %lu size %lld -> %lld",
1233                                                   (unsigned long)e->inum,
1234                                                   e->d_size, inode->i_size);
1235                                         inode->i_size = e->d_size;
1236                                         ubifs_inode(inode)->ui_size = e->d_size;
1237                                         e->inode = inode;
1238                                         this = rb_next(this);
1239                                         continue;
1240                                 }
1241                                 iput(inode);
1242                         }
1243                 }
1244                 this = rb_next(this);
1245                 rb_erase(&e->rb, &c->size_tree);
1246                 kfree(e);
1247         }
1248         return 0;
1249 }