fs/ubifs/replay.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 contains journal replay code. It runs when the file-system is being
  25  * mounted and requires no locking.
  26  *
  27  * The larger is the journal, the longer it takes to scan it, so the longer it
  28  * takes to mount UBIFS. This is why the journal has limited size which may be
  29  * changed depending on the system requirements. But a larger journal gives
  30  * faster I/O speed because it writes the index less frequently. So this is a
  31  * trade-off. Also, the journal is indexed by the in-memory index (TNC), so the
  32  * larger is the journal, the more memory its index may consume.
  33  */
  34
  35 #include "ubifs.h"
  36
  37 /*
  38  * Replay flags.
  39  *
  40  * REPLAY_DELETION: node was deleted
  41  * REPLAY_REF: node is a reference node
  42  */
  43 enum {
  44         REPLAY_DELETION = 1,
  45         REPLAY_REF = 2,
  46 };
  47
  48 /**
  49  * struct replay_entry - replay tree entry.
  50  * @lnum: logical eraseblock number of the node
  51  * @offs: node offset
  52  * @len: node length
  53  * @sqnum: node sequence number
  54  * @flags: replay flags
  55  * @rb: links the replay tree
  56  * @key: node key
  57  * @nm: directory entry name
  58  * @old_size: truncation old size
  59  * @new_size: truncation new size
  60  * @free: amount of free space in a bud
  61  * @dirty: amount of dirty space in a bud from padding and deletion nodes
  62  * @jhead: journal head number of the bud
  63  *
  64  * UBIFS journal replay must compare node sequence numbers, which means it must
  65  * build a tree of node information to insert into the TNC.
  66  */
  67 struct replay_entry {
  68         int lnum;
  69         int offs;
  70         int len;
  71         unsigned long long sqnum;
  72         int flags;
  73         struct rb_node rb;
  74         union ubifs_key key;
  75         union {
  76                 struct qstr nm;
  77                 struct {
  78                         loff_t old_size;
  79                         loff_t new_size;
  80                 };
  81                 struct {
  82                         int free;
  83                         int dirty;
  84                         int jhead;
  85                 };
  86         };
  87 };
  88
  89 /**
  90  * struct bud_entry - entry in the list of buds to replay.
  91  * @list: next bud in the list
  92  * @bud: bud description object
  93  * @free: free bytes in the bud
  94  * @sqnum: reference node sequence number
  95  */
  96 struct bud_entry {
  97         struct list_head list;
  98         struct ubifs_bud *bud;
  99         int free;
 100         unsigned long long sqnum;
 101 };
 102
 103 /**
 104  * set_bud_lprops - set free and dirty space used by a bud.
 105  * @c: UBIFS file-system description object
 106  * @r: replay entry of bud
 107  */
 108 static int set_bud_lprops(struct ubifs_info *c, struct replay_entry *r)
 109 {
 110         const struct ubifs_lprops *lp;
 111         int err = 0, dirty;
 112
 113         ubifs_get_lprops(c);
 114
 115         lp = ubifs_lpt_lookup_dirty(c, r->lnum);
 116         if (IS_ERR(lp)) {
 117                 err = PTR_ERR(lp);
 118                 goto out;
 119         }
 120
 121         dirty = lp->dirty;
 122         if (r->offs == 0 && (lp->free != c->leb_size || lp->dirty != 0)) {
 123                 /*
 124                  * The LEB was added to the journal with a starting offset of
 125                  * zero which means the LEB must have been empty. The LEB
 126                  * property values should be lp->free == c->leb_size and
 127                  * lp->dirty == 0, but that is not the case. The reason is that
 128                  * the LEB was garbage collected. The garbage collector resets
 129                  * the free and dirty space without recording it anywhere except
 130                  * lprops, so if there is not a commit then lprops does not have
 131                  * that information next time the file system is mounted.
 132                  *
 133                  * We do not need to adjust free space because the scan has told
 134                  * us the exact value which is recorded in the replay entry as
 135                  * r->free.
 136                  *
 137                  * However we do need to subtract from the dirty space the
 138                  * amount of space that the garbage collector reclaimed, which
 139                  * is the whole LEB minus the amount of space that was free.
 140                  */
 141                 dbg_mnt("bud LEB %d was GC'd (%d free, %d dirty)", r->lnum,
 142                         lp->free, lp->dirty);
 143                 dbg_gc("bud LEB %d was GC'd (%d free, %d dirty)", r->lnum,
 144                         lp->free, lp->dirty);
 145                 dirty -= c->leb_size - lp->free;
 146                 /*
 147                  * If the replay order was perfect the dirty space would now be
 148                  * zero. The order is not perfect because the journal heads
 149                  * race with each other. This is not a problem but is does mean
 150                  * that the dirty space may temporarily exceed c->leb_size
 151                  * during the replay.
 152                  */
 153                 if (dirty != 0)
 154                         dbg_msg("LEB %d lp: %d free %d dirty "
 155                                 "replay: %d free %d dirty", r->lnum, lp->free,
 156                                 lp->dirty, r->free, r->dirty);
 157         }
 158         lp = ubifs_change_lp(c, lp, r->free, dirty + r->dirty,
 159                              lp->flags | LPROPS_TAKEN, 0);
 160         if (IS_ERR(lp)) {
 161                 err = PTR_ERR(lp);
 162                 goto out;
 163         }
 164
 165         /* Make sure the journal head points to the latest bud */
 166         err = ubifs_wbuf_seek_nolock(&c->jheads[r->jhead].wbuf, r->lnum,
 167                                      c->leb_size - r->free, UBI_SHORTTERM);
 168
 169 out:
 170         ubifs_release_lprops(c);
 171         return err;
 172 }
 173
 174 /**
 175  * trun_remove_range - apply a replay entry for a truncation to the TNC.
 176  * @c: UBIFS file-system description object
 177  * @r: replay entry of truncation
 178  */
 179 static int trun_remove_range(struct ubifs_info *c, struct replay_entry *r)
 180 {
 181         unsigned min_blk, max_blk;
 182         union ubifs_key min_key, max_key;
 183         ino_t ino;
 184
 185         min_blk = r->new_size / UBIFS_BLOCK_SIZE;
 186         if (r->new_size & (UBIFS_BLOCK_SIZE - 1))
 187                 min_blk += 1;
 188
 189         max_blk = r->old_size / UBIFS_BLOCK_SIZE;
 190         if ((r->old_size & (UBIFS_BLOCK_SIZE - 1)) == 0)
 191                 max_blk -= 1;
 192
 193         ino = key_inum(c, &r->key);
 194
 195         data_key_init(c, &min_key, ino, min_blk);
 196         data_key_init(c, &max_key, ino, max_blk);
 197
 198         return ubifs_tnc_remove_range(c, &min_key, &max_key);
 199 }
 200
 201 /**
 202  * apply_replay_entry - apply a replay entry to the TNC.
 203  * @c: UBIFS file-system description object
 204  * @r: replay entry to apply
 205  *
 206  * Apply a replay entry to the TNC.
 207  */
 208 static int apply_replay_entry(struct ubifs_info *c, struct replay_entry *r)
 209 {
 210         int err, deletion = ((r->flags & REPLAY_DELETION) != 0);
 211
 212         dbg_mnt("LEB %d:%d len %d flgs %d sqnum %llu %s", r->lnum,
 213                 r->offs, r->len, r->flags, r->sqnum, DBGKEY(&r->key));
 214
 215         /* Set c->replay_sqnum to help deal with dangling branches. */
 216         c->replay_sqnum = r->sqnum;
 217
 218         if (r->flags & REPLAY_REF)
 219                 err = set_bud_lprops(c, r);
 220         else if (is_hash_key(c, &r->key)) {
 221                 if (deletion)
 222                         err = ubifs_tnc_remove_nm(c, &r->key, &r->nm);
 223                 else
 224                         err = ubifs_tnc_add_nm(c, &r->key, r->lnum, r->offs,
 225                                                r->len, &r->nm);
 226         } else {
 227                 if (deletion)
 228                         switch (key_type(c, &r->key)) {
 229                         case UBIFS_INO_KEY:
 230                         {
 231                                 ino_t inum = key_inum(c, &r->key);
 232
 233                                 err = ubifs_tnc_remove_ino(c, inum);
 234                                 break;
 235                         }
 236                         case UBIFS_TRUN_KEY:
 237                                 err = trun_remove_range(c, r);
 238                                 break;
 239                         default:
 240                                 err = ubifs_tnc_remove(c, &r->key);
 241                                 break;
 242                         }
 243                 else
 244                         err = ubifs_tnc_add(c, &r->key, r->lnum, r->offs,
 245                                             r->len);
 246                 if (err)
 247                         return err;
 248
 249                 if (c->need_recovery)
 250                         err = ubifs_recover_size_accum(c, &r->key, deletion,
 251                                                        r->new_size);
 252         }
 253
 254         return err;
 255 }
 256
 257 /**
 258  * destroy_replay_tree - destroy the replay.
 259  * @c: UBIFS file-system description object
 260  *
 261  * Destroy the replay tree.
 262  */
 263 static void destroy_replay_tree(struct ubifs_info *c)
 264 {
 265         struct rb_node *this = c->replay_tree.rb_node;
 266         struct replay_entry *r;
 267
 268         while (this) {
 269                 if (this->rb_left) {
 270                         this = this->rb_left;
 271                         continue;
 272                 } else if (this->rb_right) {
 273                         this = this->rb_right;
 274                         continue;
 275                 }
 276                 r = rb_entry(this, struct replay_entry, rb);
 277                 this = rb_parent(this);
 278                 if (this) {
 279                         if (this->rb_left == &r->rb)
 280                                 this->rb_left = NULL;
 281                         else
 282                                 this->rb_right = NULL;
 283                 }
 284                 if (is_hash_key(c, &r->key))
 285                         kfree(r->nm.name);
 286                 kfree(r);
 287         }
 288         c->replay_tree = RB_ROOT;
 289 }
 290
 291 /**
 292  * apply_replay_tree - apply the replay tree to the TNC.
 293  * @c: UBIFS file-system description object
 294  *
 295  * Apply the replay tree.
 296  * Returns zero in case of success and a negative error code in case of
 297  * failure.
 298  */
 299 static int apply_replay_tree(struct ubifs_info *c)
 300 {
 301         struct rb_node *this = rb_first(&c->replay_tree);
 302
 303         while (this) {
 304                 struct replay_entry *r;
 305                 int err;
 306
 307                 cond_resched();
 308
 309                 r = rb_entry(this, struct replay_entry, rb);
 310                 err = apply_replay_entry(c, r);
 311                 if (err)
 312                         return err;
 313                 this = rb_next(this);
 314         }
 315         return 0;
 316 }
 317
 318 /**
 319  * insert_node - insert a node to the replay tree.
 320  * @c: UBIFS file-system description object
 321  * @lnum: node logical eraseblock number
 322  * @offs: node offset
 323  * @len: node length
 324  * @key: node key
 325  * @sqnum: sequence number
 326  * @deletion: non-zero if this is a deletion
 327  * @used: number of bytes in use in a LEB
 328  * @old_size: truncation old size
 329  * @new_size: truncation new size
 330  *
 331  * This function inserts a scanned non-direntry node to the replay tree. The
 332  * replay tree is an RB-tree containing @struct replay_entry elements which are
 333  * indexed by the sequence number. The replay tree is applied at the very end
 334  * of the replay process. Since the tree is sorted in sequence number order,
 335  * the older modifications are applied first. This function returns zero in
 336  * case of success and a negative error code in case of failure.
 337  */
 338 static int insert_node(struct ubifs_info *c, int lnum, int offs, int len,
 339                        union ubifs_key *key, unsigned long long sqnum,
 340                        int deletion, int *used, loff_t old_size,
 341                        loff_t new_size)
 342 {
 343         struct rb_node **p = &c->replay_tree.rb_node, *parent = NULL;
 344         struct replay_entry *r;
 345
 346         if (key_inum(c, key) >= c->highest_inum)
 347                 c->highest_inum = key_inum(c, key);
 348
 349         dbg_mnt("add LEB %d:%d, key %s", lnum, offs, DBGKEY(key));
 350         while (*p) {
 351                 parent = *p;
 352                 r = rb_entry(parent, struct replay_entry, rb);
 353                 if (sqnum < r->sqnum) {
 354                         p = &(*p)->rb_left;
 355                         continue;
 356                 } else if (sqnum > r->sqnum) {
 357                         p = &(*p)->rb_right;
 358                         continue;
 359                 }
 360                 ubifs_err("duplicate sqnum in replay");
 361                 return -EINVAL;
 362         }
 363
 364         r = kzalloc(sizeof(struct replay_entry), GFP_KERNEL);
 365         if (!r)
 366                 return -ENOMEM;
 367
 368         if (!deletion)
 369                 *used += ALIGN(len, 8);
 370         r->lnum = lnum;
 371         r->offs = offs;
 372         r->len = len;
 373         r->sqnum = sqnum;
 374         r->flags = (deletion ? REPLAY_DELETION : 0);
 375         r->old_size = old_size;
 376         r->new_size = new_size;
 377         key_copy(c, key, &r->key);
 378
 379         rb_link_node(&r->rb, parent, p);
 380         rb_insert_color(&r->rb, &c->replay_tree);
 381         return 0;
 382 }
 383
 384 /**
 385  * insert_dent - insert a directory entry node into the replay tree.
 386  * @c: UBIFS file-system description object
 387  * @lnum: node logical eraseblock number
 388  * @offs: node offset
 389  * @len: node length
 390  * @key: node key
 391  * @name: directory entry name
 392  * @nlen: directory entry name length
 393  * @sqnum: sequence number
 394  * @deletion: non-zero if this is a deletion
 395  * @used: number of bytes in use in a LEB
 396  *
 397  * This function inserts a scanned directory entry node to the replay tree.
 398  * Returns zero in case of success and a negative error code in case of
 399  * failure.
 400  *
 401  * This function is also used for extended attribute entries because they are
 402  * implemented as directory entry nodes.
 403  */
 404 static int insert_dent(struct ubifs_info *c, int lnum, int offs, int len,
 405                        union ubifs_key *key, const char *name, int nlen,
 406                        unsigned long long sqnum, int deletion, int *used)
 407 {
 408         struct rb_node **p = &c->replay_tree.rb_node, *parent = NULL;
 409         struct replay_entry *r;
 410         char *nbuf;
 411
 412         if (key_inum(c, key) >= c->highest_inum)
 413                 c->highest_inum = key_inum(c, key);
 414
 415         dbg_mnt("add LEB %d:%d, key %s", lnum, offs, DBGKEY(key));
 416         while (*p) {
 417                 parent = *p;
 418                 r = rb_entry(parent, struct replay_entry, rb);
 419                 if (sqnum < r->sqnum) {
 420                         p = &(*p)->rb_left;
 421                         continue;
 422                 }
 423                 if (sqnum > r->sqnum) {
 424                         p = &(*p)->rb_right;
 425                         continue;
 426                 }
 427                 ubifs_err("duplicate sqnum in replay");
 428                 return -EINVAL;
 429         }
 430
 431         r = kzalloc(sizeof(struct replay_entry), GFP_KERNEL);
 432         if (!r)
 433                 return -ENOMEM;
 434         nbuf = kmalloc(nlen + 1, GFP_KERNEL);
 435         if (!nbuf) {
 436                 kfree(r);
 437                 return -ENOMEM;
 438         }
 439
 440         if (!deletion)
 441                 *used += ALIGN(len, 8);
 442         r->lnum = lnum;
 443         r->offs = offs;
 444         r->len = len;
 445         r->sqnum = sqnum;
 446         r->nm.len = nlen;
 447         memcpy(nbuf, name, nlen);
 448         nbuf[nlen] = '\0';
 449         r->nm.name = nbuf;
 450         r->flags = (deletion ? REPLAY_DELETION : 0);
 451         key_copy(c, key, &r->key);
 452
 453         ubifs_assert(!*p);
 454         rb_link_node(&r->rb, parent, p);
 455         rb_insert_color(&r->rb, &c->replay_tree);
 456         return 0;
 457 }
 458
 459 /**
 460  * ubifs_validate_entry - validate directory or extended attribute entry node.
 461  * @c: UBIFS file-system description object
 462  * @dent: the node to validate
 463  *
 464  * This function validates directory or extended attribute entry node @dent.
 465  * Returns zero if the node is all right and a %-EINVAL if not.
 466  */
 467 int ubifs_validate_entry(struct ubifs_info *c,
 468                          const struct ubifs_dent_node *dent)
 469 {
 470         int key_type = key_type_flash(c, dent->key);
 471         int nlen = le16_to_cpu(dent->nlen);
 472
 473         if (le32_to_cpu(dent->ch.len) != nlen + UBIFS_DENT_NODE_SZ + 1 ||
 474             dent->type >= UBIFS_ITYPES_CNT ||
 475             nlen > UBIFS_MAX_NLEN || dent->name[nlen] != 0 ||
 476             strnlen(dent->name, nlen) != nlen ||
 477             le64_to_cpu(dent->inum) > MAX_INUM) {
 478                 ubifs_err("bad %s node", key_type == UBIFS_DENT_KEY ?
 479                           "directory entry" : "extended attribute entry");
 480                 return -EINVAL;
 481         }
 482
 483         if (key_type != UBIFS_DENT_KEY && key_type != UBIFS_XENT_KEY) {
 484                 ubifs_err("bad key type %d", key_type);
 485                 return -EINVAL;
 486         }
 487
 488         return 0;
 489 }
 490
 491 /**
 492  * replay_bud - replay a bud logical eraseblock.
 493  * @c: UBIFS file-system description object
 494  * @lnum: bud logical eraseblock number to replay
 495  * @offs: bud start offset
 496  * @jhead: journal head to which this bud belongs
 497  * @free: amount of free space in the bud is returned here
 498  * @dirty: amount of dirty space from padding and deletion nodes is returned
 499  * here
 500  *
 501  * This function returns zero in case of success and a negative error code in
 502  * case of failure.
 503  */
 504 static int replay_bud(struct ubifs_info *c, int lnum, int offs, int jhead,
 505                       int *free, int *dirty)
 506 {
 507         int err = 0, used = 0;
 508         struct ubifs_scan_leb *sleb;
 509         struct ubifs_scan_node *snod;
 510         struct ubifs_bud *bud;
 511
 512         dbg_mnt("replay bud LEB %d, head %d", lnum, jhead);
 513         if (c->need_recovery)
 514                 sleb = ubifs_recover_leb(c, lnum, offs, c->sbuf, jhead != GCHD);
 515         else
 516                 sleb = ubifs_scan(c, lnum, offs, c->sbuf, 0);
 517         if (IS_ERR(sleb))
 518                 return PTR_ERR(sleb);
 519
 520         /*
 521          * The bud does not have to start from offset zero - the beginning of
 522          * the 'lnum' LEB may contain previously committed data. One of the
 523          * things we have to do in replay is to correctly update lprops with
 524          * newer information about this LEB.
 525          *
 526          * At this point lprops thinks that this LEB has 'c->leb_size - offs'
 527          * bytes of free space because it only contain information about
 528          * committed data.
 529          *
 530          * But we know that real amount of free space is 'c->leb_size -
 531          * sleb->endpt', and the space in the 'lnum' LEB between 'offs' and
 532          * 'sleb->endpt' is used by bud data. We have to correctly calculate
 533          * how much of these data are dirty and update lprops with this
 534          * information.
 535          *
 536          * The dirt in that LEB region is comprised of padding nodes, deletion
 537          * nodes, truncation nodes and nodes which are obsoleted by subsequent
 538          * nodes in this LEB. So instead of calculating clean space, we
 539          * calculate used space ('used' variable).
 540          */
 541
 542         list_for_each_entry(snod, &sleb->nodes, list) {
 543                 int deletion = 0;
 544
 545                 cond_resched();
 546
 547                 if (snod->sqnum >= SQNUM_WATERMARK) {
 548                         ubifs_err("file system's life ended");
 549                         goto out_dump;
 550                 }
 551
 552                 if (snod->sqnum > c->max_sqnum)
 553                         c->max_sqnum = snod->sqnum;
 554
 555                 switch (snod->type) {
 556                 case UBIFS_INO_NODE:
 557                 {
 558                         struct ubifs_ino_node *ino = snod->node;
 559                         loff_t new_size = le64_to_cpu(ino->size);
 560
 561                         if (le32_to_cpu(ino->nlink) == 0)
 562                                 deletion = 1;
 563                         err = insert_node(c, lnum, snod->offs, snod->len,
 564                                           &snod->key, snod->sqnum, deletion,
 565                                           &used, 0, new_size);
 566                         break;
 567                 }
 568                 case UBIFS_DATA_NODE:
 569                 {
 570                         struct ubifs_data_node *dn = snod->node;
 571                         loff_t new_size = le32_to_cpu(dn->size) +
 572                                           key_block(c, &snod->key) *
 573                                           UBIFS_BLOCK_SIZE;
 574
 575                         err = insert_node(c, lnum, snod->offs, snod->len,
 576                                           &snod->key, snod->sqnum, deletion,
 577                                           &used, 0, new_size);
 578                         break;
 579                 }
 580                 case UBIFS_DENT_NODE:
 581                 case UBIFS_XENT_NODE:
 582                 {
 583                         struct ubifs_dent_node *dent = snod->node;
 584
 585                         err = ubifs_validate_entry(c, dent);
 586                         if (err)
 587                                 goto out_dump;
 588
 589                         err = insert_dent(c, lnum, snod->offs, snod->len,
 590                                           &snod->key, dent->name,
 591                                           le16_to_cpu(dent->nlen), snod->sqnum,
 592                                           !le64_to_cpu(dent->inum), &used);
 593                         break;
 594                 }
 595                 case UBIFS_TRUN_NODE:
 596                 {
 597                         struct ubifs_trun_node *trun = snod->node;
 598                         loff_t old_size = le64_to_cpu(trun->old_size);
 599                         loff_t new_size = le64_to_cpu(trun->new_size);
 600                         union ubifs_key key;
 601
 602                         /* Validate truncation node */
 603                         if (old_size < 0 || old_size > c->max_inode_sz ||
 604                             new_size < 0 || new_size > c->max_inode_sz ||
 605                             old_size <= new_size) {
 606                                 ubifs_err("bad truncation node");
 607                                 goto out_dump;
 608                         }
 609
 610                         /*
 611                          * Create a fake truncation key just to use the same
 612                          * functions which expect nodes to have keys.
 613                          */
 614                         trun_key_init(c, &key, le32_to_cpu(trun->inum));
 615                         err = insert_node(c, lnum, snod->offs, snod->len,
 616                                           &key, snod->sqnum, 1, &used,
 617                                           old_size, new_size);
 618                         break;
 619                 }
 620                 default:
 621                         ubifs_err("unexpected node type %d in bud LEB %d:%d",
 622                                   snod->type, lnum, snod->offs);
 623                         err = -EINVAL;
 624                         goto out_dump;
 625                 }
 626                 if (err)
 627                         goto out;
 628         }
 629
 630         bud = ubifs_search_bud(c, lnum);
 631         if (!bud)
 632                 BUG();
 633
 634         ubifs_assert(sleb->endpt - offs >= used);
 635         ubifs_assert(sleb->endpt % c->min_io_size == 0);
 636
 637         *dirty = sleb->endpt - offs - used;
 638         *free = c->leb_size - sleb->endpt;
 639
 640 out:
 641         ubifs_scan_destroy(sleb);
 642         return err;
 643
 644 out_dump:
 645         ubifs_err("bad node is at LEB %d:%d", lnum, snod->offs);
 646         dbg_dump_node(c, snod->node);
 647         ubifs_scan_destroy(sleb);
 648         return -EINVAL;
 649 }
 650
 651 /**
 652  * insert_ref_node - insert a reference node to the replay tree.
 653  * @c: UBIFS file-system description object
 654  * @lnum: node logical eraseblock number
 655  * @offs: node offset
 656  * @sqnum: sequence number
 657  * @free: amount of free space in bud
 658  * @dirty: amount of dirty space from padding and deletion nodes
 659  * @jhead: journal head number for the bud
 660  *
 661  * This function inserts a reference node to the replay tree and returns zero
 662  * in case of success or a negative error code in case of failure.
 663  */
 664 static int insert_ref_node(struct ubifs_info *c, int lnum, int offs,
 665                            unsigned long long sqnum, int free, int dirty,
 666                            int jhead)
 667 {
 668         struct rb_node **p = &c->replay_tree.rb_node, *parent = NULL;
 669         struct replay_entry *r;
 670
 671         dbg_mnt("add ref LEB %d:%d", lnum, offs);
 672         while (*p) {
 673                 parent = *p;
 674                 r = rb_entry(parent, struct replay_entry, rb);
 675                 if (sqnum < r->sqnum) {
 676                         p = &(*p)->rb_left;
 677                         continue;
 678                 } else if (sqnum > r->sqnum) {
 679                         p = &(*p)->rb_right;
 680                         continue;
 681                 }
 682                 ubifs_err("duplicate sqnum in replay tree");
 683                 return -EINVAL;
 684         }
 685
 686         r = kzalloc(sizeof(struct replay_entry), GFP_KERNEL);
 687         if (!r)
 688                 return -ENOMEM;
 689
 690         r->lnum = lnum;
 691         r->offs = offs;
 692         r->sqnum = sqnum;
 693         r->flags = REPLAY_REF;
 694         r->free = free;
 695         r->dirty = dirty;
 696         r->jhead = jhead;
 697
 698         rb_link_node(&r->rb, parent, p);
 699         rb_insert_color(&r->rb, &c->replay_tree);
 700         return 0;
 701 }
 702
 703 /**
 704  * replay_buds - replay all buds.
 705  * @c: UBIFS file-system description object
 706  *
 707  * This function returns zero in case of success and a negative error code in
 708  * case of failure.
 709  */
 710 static int replay_buds(struct ubifs_info *c)
 711 {
 712         struct bud_entry *b;
 713         int err, uninitialized_var(free), uninitialized_var(dirty);
 714
 715         list_for_each_entry(b, &c->replay_buds, list) {
 716                 err = replay_bud(c, b->bud->lnum, b->bud->start, b->bud->jhead,
 717                                  &free, &dirty);
 718                 if (err)
 719                         return err;
 720                 err = insert_ref_node(c, b->bud->lnum, b->bud->start, b->sqnum,
 721                                       free, dirty, b->bud->jhead);
 722                 if (err)
 723                         return err;
 724         }
 725
 726         return 0;
 727 }
 728
 729 /**
 730  * destroy_bud_list - destroy the list of buds to replay.
 731  * @c: UBIFS file-system description object
 732  */
 733 static void destroy_bud_list(struct ubifs_info *c)
 734 {
 735         struct bud_entry *b;
 736
 737         while (!list_empty(&c->replay_buds)) {
 738                 b = list_entry(c->replay_buds.next, struct bud_entry, list);
 739                 list_del(&b->list);
 740                 kfree(b);
 741         }
 742 }
 743
 744 /**
 745  * add_replay_bud - add a bud to the list of buds to replay.
 746  * @c: UBIFS file-system description object
 747  * @lnum: bud logical eraseblock number to replay
 748  * @offs: bud start offset
 749  * @jhead: journal head to which this bud belongs
 750  * @sqnum: reference node sequence number
 751  *
 752  * This function returns zero in case of success and a negative error code in
 753  * case of failure.
 754  */
 755 static int add_replay_bud(struct ubifs_info *c, int lnum, int offs, int jhead,
 756                           unsigned long long sqnum)
 757 {
 758         struct ubifs_bud *bud;
 759         struct bud_entry *b;
 760
 761         dbg_mnt("add replay bud LEB %d:%d, head %d", lnum, offs, jhead);
 762
 763         bud = kmalloc(sizeof(struct ubifs_bud), GFP_KERNEL);
 764         if (!bud)
 765                 return -ENOMEM;
 766
 767         b = kmalloc(sizeof(struct bud_entry), GFP_KERNEL);
 768         if (!b) {
 769                 kfree(bud);
 770                 return -ENOMEM;
 771         }
 772
 773         bud->lnum = lnum;
 774         bud->start = offs;
 775         bud->jhead = jhead;
 776         ubifs_add_bud(c, bud);
 777
 778         b->bud = bud;
 779         b->sqnum = sqnum;
 780         list_add_tail(&b->list, &c->replay_buds);
 781
 782         return 0;
 783 }
 784
 785 /**
 786  * validate_ref - validate a reference node.
 787  * @c: UBIFS file-system description object
 788  * @ref: the reference node to validate
 789  * @ref_lnum: LEB number of the reference node
 790  * @ref_offs: reference node offset
 791  *
 792  * This function returns %1 if a bud reference already exists for the LEB. %0 is
 793  * returned if the reference node is new, otherwise %-EINVAL is returned if
 794  * validation failed.
 795  */
 796 static int validate_ref(struct ubifs_info *c, const struct ubifs_ref_node *ref)
 797 {
 798         struct ubifs_bud *bud;
 799         int lnum = le32_to_cpu(ref->lnum);
 800         unsigned int offs = le32_to_cpu(ref->offs);
 801         unsigned int jhead = le32_to_cpu(ref->jhead);
 802
 803         /*
 804          * ref->offs may point to the end of LEB when the journal head points
 805          * to the end of LEB and we write reference node for it during commit.
 806          * So this is why we require 'offs > c->leb_size'.
 807          */
 808         if (jhead >= c->jhead_cnt || lnum >= c->leb_cnt ||
 809             lnum < c->main_first || offs > c->leb_size ||
 810             offs & (c->min_io_size - 1))
 811                 return -EINVAL;
 812
 813         /* Make sure we have not already looked at this bud */
 814         bud = ubifs_search_bud(c, lnum);
 815         if (bud) {
 816                 if (bud->jhead == jhead && bud->start <= offs)
 817                         return 1;
 818                 ubifs_err("bud at LEB %d:%d was already referred", lnum, offs);
 819                 return -EINVAL;
 820         }
 821
 822         return 0;
 823 }
 824
 825 /**
 826  * replay_log_leb - replay a log logical eraseblock.
 827  * @c: UBIFS file-system description object
 828  * @lnum: log logical eraseblock to replay
 829  * @offs: offset to start replaying from
 830  * @sbuf: scan buffer
 831  *
 832  * This function replays a log LEB and returns zero in case of success, %1 if
 833  * this is the last LEB in the log, and a negative error code in case of
 834  * failure.
 835  */
 836 static int replay_log_leb(struct ubifs_info *c, int lnum, int offs, void *sbuf)
 837 {
 838         int err;
 839         struct ubifs_scan_leb *sleb;
 840         struct ubifs_scan_node *snod;
 841         const struct ubifs_cs_node *node;
 842
 843         dbg_mnt("replay log LEB %d:%d", lnum, offs);
 844         sleb = ubifs_scan(c, lnum, offs, sbuf, c->need_recovery);
 845         if (IS_ERR(sleb)) {
 846                 if (PTR_ERR(sleb) != -EUCLEAN || !c->need_recovery)
 847                         return PTR_ERR(sleb);
 848                 /*
 849                  * Note, the below function will recover this log LEB only if
 850                  * it is the last, because unclean reboots can possibly corrupt
 851                  * only the tail of the log.
 852                  */
 853                 sleb = ubifs_recover_log_leb(c, lnum, offs, sbuf);
 854                 if (IS_ERR(sleb))
 855                         return PTR_ERR(sleb);
 856         }
 857
 858         if (sleb->nodes_cnt == 0) {
 859                 err = 1;
 860                 goto out;
 861         }
 862
 863         node = sleb->buf;
 864         snod = list_entry(sleb->nodes.next, struct ubifs_scan_node, list);
 865         if (c->cs_sqnum == 0) {
 866                 /*
 867                  * This is the first log LEB we are looking at, make sure that
 868                  * the first node is a commit start node. Also record its
 869                  * sequence number so that UBIFS can determine where the log
 870                  * ends, because all nodes which were have higher sequence
 871                  * numbers.
 872                  */
 873                 if (snod->type != UBIFS_CS_NODE) {
 874                         dbg_err("first log node at LEB %d:%d is not CS node",
 875                                 lnum, offs);
 876                         goto out_dump;
 877                 }
 878                 if (le64_to_cpu(node->cmt_no) != c->cmt_no) {
 879                         dbg_err("first CS node at LEB %d:%d has wrong "
 880                                 "commit number %llu expected %llu",
 881                                 lnum, offs,
 882                                 (unsigned long long)le64_to_cpu(node->cmt_no),
 883                                 c->cmt_no);
 884                         goto out_dump;
 885                 }
 886
 887                 c->cs_sqnum = le64_to_cpu(node->ch.sqnum);
 888                 dbg_mnt("commit start sqnum %llu", c->cs_sqnum);
 889         }
 890
 891         if (snod->sqnum < c->cs_sqnum) {
 892                 /*
 893                  * This means that we reached end of log and now
 894                  * look to the older log data, which was already
 895                  * committed but the eraseblock was not erased (UBIFS
 896                  * only un-maps it). So this basically means we have to
 897                  * exit with "end of log" code.
 898                  */
 899                 err = 1;
 900                 goto out;
 901         }
 902
 903         /* Make sure the first node sits at offset zero of the LEB */
 904         if (snod->offs != 0) {
 905                 dbg_err("first node is not at zero offset");
 906                 goto out_dump;
 907         }
 908
 909         list_for_each_entry(snod, &sleb->nodes, list) {
 910                 cond_resched();
 911
 912                 if (snod->sqnum >= SQNUM_WATERMARK) {
 913                         ubifs_err("file system's life ended");
 914                         goto out_dump;
 915                 }
 916
 917                 if (snod->sqnum < c->cs_sqnum) {
 918                         dbg_err("bad sqnum %llu, commit sqnum %llu",
 919                                 snod->sqnum, c->cs_sqnum);
 920                         goto out_dump;
 921                 }
 922
 923                 if (snod->sqnum > c->max_sqnum)
 924                         c->max_sqnum = snod->sqnum;
 925
 926                 switch (snod->type) {
 927                 case UBIFS_REF_NODE: {
 928                         const struct ubifs_ref_node *ref = snod->node;
 929
 930                         err = validate_ref(c, ref);
 931                         if (err == 1)
 932                                 break; /* Already have this bud */
 933                         if (err)
 934                                 goto out_dump;
 935
 936                         err = add_replay_bud(c, le32_to_cpu(ref->lnum),
 937                                              le32_to_cpu(ref->offs),
 938                                              le32_to_cpu(ref->jhead),
 939                                              snod->sqnum);
 940                         if (err)
 941                                 goto out;
 942
 943                         break;
 944                 }
 945                 case UBIFS_CS_NODE:
 946                         /* Make sure it sits at the beginning of LEB */
 947                         if (snod->offs != 0) {
 948                                 ubifs_err("unexpected node in log");
 949                                 goto out_dump;
 950                         }
 951                         break;
 952                 default:
 953                         ubifs_err("unexpected node in log");
 954                         goto out_dump;
 955                 }
 956         }
 957
 958         if (sleb->endpt || c->lhead_offs >= c->leb_size) {
 959                 c->lhead_lnum = lnum;
 960                 c->lhead_offs = sleb->endpt;
 961         }
 962
 963         err = !sleb->endpt;
 964 out:
 965         ubifs_scan_destroy(sleb);
 966         return err;
 967
 968 out_dump:
 969         ubifs_err("log error detected while replaying the log at LEB %d:%d",
 970                   lnum, offs + snod->offs);
 971         dbg_dump_node(c, snod->node);
 972         ubifs_scan_destroy(sleb);
 973         return -EINVAL;
 974 }
 975
 976 /**
 977  * take_ihead - update the status of the index head in lprops to 'taken'.
 978  * @c: UBIFS file-system description object
 979  *
 980  * This function returns the amount of free space in the index head LEB or a
 981  * negative error code.
 982  */
 983 static int take_ihead(struct ubifs_info *c)
 984 {
 985         const struct ubifs_lprops *lp;
 986         int err, free;
 987
 988         ubifs_get_lprops(c);
 989
 990         lp = ubifs_lpt_lookup_dirty(c, c->ihead_lnum);
 991         if (IS_ERR(lp)) {
 992                 err = PTR_ERR(lp);
 993                 goto out;
 994         }
 995
 996         free = lp->free;
 997
 998         lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC,
 999                              lp->flags | LPROPS_TAKEN, 0);
1000         if (IS_ERR(lp)) {
1001                 err = PTR_ERR(lp);
1002                 goto out;
1003         }
1004
1005         err = free;
1006 out:
1007         ubifs_release_lprops(c);
1008         return err;
1009 }
1010
1011 /**
1012  * ubifs_replay_journal - replay journal.
1013  * @c: UBIFS file-system description object
1014  *
1015  * This function scans the journal, replays and cleans it up. It makes sure all
1016  * memory data structures related to uncommitted journal are built (dirty TNC
1017  * tree, tree of buds, modified lprops, etc).
1018  */
1019 int ubifs_replay_journal(struct ubifs_info *c)
1020 {
1021         int err, i, lnum, offs, free;
1022
1023         BUILD_BUG_ON(UBIFS_TRUN_KEY > 5);
1024
1025         /* Update the status of the index head in lprops to 'taken' */
1026         free = take_ihead(c);
1027         if (free < 0)
1028                 return free; /* Error code */
1029
1030         if (c->ihead_offs != c->leb_size - free) {
1031                 ubifs_err("bad index head LEB %d:%d", c->ihead_lnum,
1032                           c->ihead_offs);
1033                 return -EINVAL;
1034         }
1035
1036         dbg_mnt("start replaying the journal");
1037         c->replaying = 1;
1038         lnum = c->ltail_lnum = c->lhead_lnum;
1039         offs = c->lhead_offs;
1040
1041         for (i = 0; i < c->log_lebs; i++, lnum++) {
1042                 if (lnum >= UBIFS_LOG_LNUM + c->log_lebs) {
1043                         /*
1044                          * The log is logically circular, we reached the last
1045                          * LEB, switch to the first one.
1046                          */
1047                         lnum = UBIFS_LOG_LNUM;
1048                         offs = 0;
1049                 }
1050                 err = replay_log_leb(c, lnum, offs, c->sbuf);
1051                 if (err == 1)
1052                         /* We hit the end of the log */
1053                         break;
1054                 if (err)
1055                         goto out;
1056                 offs = 0;
1057         }
1058
1059         err = replay_buds(c);
1060         if (err)
1061                 goto out;
1062
1063         err = apply_replay_tree(c);
1064         if (err)
1065                 goto out;
1066
1067         /*
1068          * UBIFS budgeting calculations use @c->budg_uncommitted_idx variable
1069          * to roughly estimate index growth. Things like @c->min_idx_lebs
1070          * depend on it. This means we have to initialize it to make sure
1071          * budgeting works properly.
1072          */
1073         c->budg_uncommitted_idx = atomic_long_read(&c->dirty_zn_cnt);
1074         c->budg_uncommitted_idx *= c->max_idx_node_sz;
1075
1076         ubifs_assert(c->bud_bytes <= c->max_bud_bytes || c->need_recovery);
1077         dbg_mnt("finished, log head LEB %d:%d, max_sqnum %llu, "
1078                 "highest_inum %lu", c->lhead_lnum, c->lhead_offs, c->max_sqnum,
1079                 (unsigned long)c->highest_inum);
1080 out:
1081         destroy_replay_tree(c);
1082         destroy_bud_list(c);
1083         c->replaying = 0;
1084         return err;
1085 }