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, offs %d", lnum, jhead, offs);
 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         dbg_mnt("bud LEB %d replied: dirty %d, free %d", lnum, *dirty, *free);
 640
 641 out:
 642         ubifs_scan_destroy(sleb);
 643         return err;
 644
 645 out_dump:
 646         ubifs_err("bad node is at LEB %d:%d", lnum, snod->offs);
 647         dbg_dump_node(c, snod->node);
 648         ubifs_scan_destroy(sleb);
 649         return -EINVAL;
 650 }
 651
 652 /**
 653  * insert_ref_node - insert a reference node to the replay tree.
 654  * @c: UBIFS file-system description object
 655  * @lnum: node logical eraseblock number
 656  * @offs: node offset
 657  * @sqnum: sequence number
 658  * @free: amount of free space in bud
 659  * @dirty: amount of dirty space from padding and deletion nodes
 660  * @jhead: journal head number for the bud
 661  *
 662  * This function inserts a reference node to the replay tree and returns zero
 663  * in case of success or a negative error code in case of failure.
 664  */
 665 static int insert_ref_node(struct ubifs_info *c, int lnum, int offs,
 666                            unsigned long long sqnum, int free, int dirty,
 667                            int jhead)
 668 {
 669         struct rb_node **p = &c->replay_tree.rb_node, *parent = NULL;
 670         struct replay_entry *r;
 671
 672         dbg_mnt("add ref LEB %d:%d", lnum, offs);
 673         while (*p) {
 674                 parent = *p;
 675                 r = rb_entry(parent, struct replay_entry, rb);
 676                 if (sqnum < r->sqnum) {
 677                         p = &(*p)->rb_left;
 678                         continue;
 679                 } else if (sqnum > r->sqnum) {
 680                         p = &(*p)->rb_right;
 681                         continue;
 682                 }
 683                 ubifs_err("duplicate sqnum in replay tree");
 684                 return -EINVAL;
 685         }
 686
 687         r = kzalloc(sizeof(struct replay_entry), GFP_KERNEL);
 688         if (!r)
 689                 return -ENOMEM;
 690
 691         r->lnum = lnum;
 692         r->offs = offs;
 693         r->sqnum = sqnum;
 694         r->flags = REPLAY_REF;
 695         r->free = free;
 696         r->dirty = dirty;
 697         r->jhead = jhead;
 698
 699         rb_link_node(&r->rb, parent, p);
 700         rb_insert_color(&r->rb, &c->replay_tree);
 701         return 0;
 702 }
 703
 704 /**
 705  * replay_buds - replay all buds.
 706  * @c: UBIFS file-system description object
 707  *
 708  * This function returns zero in case of success and a negative error code in
 709  * case of failure.
 710  */
 711 static int replay_buds(struct ubifs_info *c)
 712 {
 713         struct bud_entry *b;
 714         int err, uninitialized_var(free), uninitialized_var(dirty);
 715
 716         list_for_each_entry(b, &c->replay_buds, list) {
 717                 err = replay_bud(c, b->bud->lnum, b->bud->start, b->bud->jhead,
 718                                  &free, &dirty);
 719                 if (err)
 720                         return err;
 721                 err = insert_ref_node(c, b->bud->lnum, b->bud->start, b->sqnum,
 722                                       free, dirty, b->bud->jhead);
 723                 if (err)
 724                         return err;
 725         }
 726
 727         return 0;
 728 }
 729
 730 /**
 731  * destroy_bud_list - destroy the list of buds to replay.
 732  * @c: UBIFS file-system description object
 733  */
 734 static void destroy_bud_list(struct ubifs_info *c)
 735 {
 736         struct bud_entry *b;
 737
 738         while (!list_empty(&c->replay_buds)) {
 739                 b = list_entry(c->replay_buds.next, struct bud_entry, list);
 740                 list_del(&b->list);
 741                 kfree(b);
 742         }
 743 }
 744
 745 /**
 746  * add_replay_bud - add a bud to the list of buds to replay.
 747  * @c: UBIFS file-system description object
 748  * @lnum: bud logical eraseblock number to replay
 749  * @offs: bud start offset
 750  * @jhead: journal head to which this bud belongs
 751  * @sqnum: reference node sequence number
 752  *
 753  * This function returns zero in case of success and a negative error code in
 754  * case of failure.
 755  */
 756 static int add_replay_bud(struct ubifs_info *c, int lnum, int offs, int jhead,
 757                           unsigned long long sqnum)
 758 {
 759         struct ubifs_bud *bud;
 760         struct bud_entry *b;
 761
 762         dbg_mnt("add replay bud LEB %d:%d, head %d", lnum, offs, jhead);
 763
 764         bud = kmalloc(sizeof(struct ubifs_bud), GFP_KERNEL);
 765         if (!bud)
 766                 return -ENOMEM;
 767
 768         b = kmalloc(sizeof(struct bud_entry), GFP_KERNEL);
 769         if (!b) {
 770                 kfree(bud);
 771                 return -ENOMEM;
 772         }
 773
 774         bud->lnum = lnum;
 775         bud->start = offs;
 776         bud->jhead = jhead;
 777         ubifs_add_bud(c, bud);
 778
 779         b->bud = bud;
 780         b->sqnum = sqnum;
 781         list_add_tail(&b->list, &c->replay_buds);
 782
 783         return 0;
 784 }
 785
 786 /**
 787  * validate_ref - validate a reference node.
 788  * @c: UBIFS file-system description object
 789  * @ref: the reference node to validate
 790  * @ref_lnum: LEB number of the reference node
 791  * @ref_offs: reference node offset
 792  *
 793  * This function returns %1 if a bud reference already exists for the LEB. %0 is
 794  * returned if the reference node is new, otherwise %-EINVAL is returned if
 795  * validation failed.
 796  */
 797 static int validate_ref(struct ubifs_info *c, const struct ubifs_ref_node *ref)
 798 {
 799         struct ubifs_bud *bud;
 800         int lnum = le32_to_cpu(ref->lnum);
 801         unsigned int offs = le32_to_cpu(ref->offs);
 802         unsigned int jhead = le32_to_cpu(ref->jhead);
 803
 804         /*
 805          * ref->offs may point to the end of LEB when the journal head points
 806          * to the end of LEB and we write reference node for it during commit.
 807          * So this is why we require 'offs > c->leb_size'.
 808          */
 809         if (jhead >= c->jhead_cnt || lnum >= c->leb_cnt ||
 810             lnum < c->main_first || offs > c->leb_size ||
 811             offs & (c->min_io_size - 1))
 812                 return -EINVAL;
 813
 814         /* Make sure we have not already looked at this bud */
 815         bud = ubifs_search_bud(c, lnum);
 816         if (bud) {
 817                 if (bud->jhead == jhead && bud->start <= offs)
 818                         return 1;
 819                 ubifs_err("bud at LEB %d:%d was already referred", lnum, offs);
 820                 return -EINVAL;
 821         }
 822
 823         return 0;
 824 }
 825
 826 /**
 827  * replay_log_leb - replay a log logical eraseblock.
 828  * @c: UBIFS file-system description object
 829  * @lnum: log logical eraseblock to replay
 830  * @offs: offset to start replaying from
 831  * @sbuf: scan buffer
 832  *
 833  * This function replays a log LEB and returns zero in case of success, %1 if
 834  * this is the last LEB in the log, and a negative error code in case of
 835  * failure.
 836  */
 837 static int replay_log_leb(struct ubifs_info *c, int lnum, int offs, void *sbuf)
 838 {
 839         int err;
 840         struct ubifs_scan_leb *sleb;
 841         struct ubifs_scan_node *snod;
 842         const struct ubifs_cs_node *node;
 843
 844         dbg_mnt("replay log LEB %d:%d", lnum, offs);
 845         sleb = ubifs_scan(c, lnum, offs, sbuf, c->need_recovery);
 846         if (IS_ERR(sleb)) {
 847                 if (PTR_ERR(sleb) != -EUCLEAN || !c->need_recovery)
 848                         return PTR_ERR(sleb);
 849                 /*
 850                  * Note, the below function will recover this log LEB only if
 851                  * it is the last, because unclean reboots can possibly corrupt
 852                  * only the tail of the log.
 853                  */
 854                 sleb = ubifs_recover_log_leb(c, lnum, offs, sbuf);
 855                 if (IS_ERR(sleb))
 856                         return PTR_ERR(sleb);
 857         }
 858
 859         if (sleb->nodes_cnt == 0) {
 860                 err = 1;
 861                 goto out;
 862         }
 863
 864         node = sleb->buf;
 865         snod = list_entry(sleb->nodes.next, struct ubifs_scan_node, list);
 866         if (c->cs_sqnum == 0) {
 867                 /*
 868                  * This is the first log LEB we are looking at, make sure that
 869                  * the first node is a commit start node. Also record its
 870                  * sequence number so that UBIFS can determine where the log
 871                  * ends, because all nodes which were have higher sequence
 872                  * numbers.
 873                  */
 874                 if (snod->type != UBIFS_CS_NODE) {
 875                         dbg_err("first log node at LEB %d:%d is not CS node",
 876                                 lnum, offs);
 877                         goto out_dump;
 878                 }
 879                 if (le64_to_cpu(node->cmt_no) != c->cmt_no) {
 880                         dbg_err("first CS node at LEB %d:%d has wrong "
 881                                 "commit number %llu expected %llu",
 882                                 lnum, offs,
 883                                 (unsigned long long)le64_to_cpu(node->cmt_no),
 884                                 c->cmt_no);
 885                         goto out_dump;
 886                 }
 887
 888                 c->cs_sqnum = le64_to_cpu(node->ch.sqnum);
 889                 dbg_mnt("commit start sqnum %llu", c->cs_sqnum);
 890         }
 891
 892         if (snod->sqnum < c->cs_sqnum) {
 893                 /*
 894                  * This means that we reached end of log and now
 895                  * look to the older log data, which was already
 896                  * committed but the eraseblock was not erased (UBIFS
 897                  * only un-maps it). So this basically means we have to
 898                  * exit with "end of log" code.
 899                  */
 900                 err = 1;
 901                 goto out;
 902         }
 903
 904         /* Make sure the first node sits at offset zero of the LEB */
 905         if (snod->offs != 0) {
 906                 dbg_err("first node is not at zero offset");
 907                 goto out_dump;
 908         }
 909
 910         list_for_each_entry(snod, &sleb->nodes, list) {
 911                 cond_resched();
 912
 913                 if (snod->sqnum >= SQNUM_WATERMARK) {
 914                         ubifs_err("file system's life ended");
 915                         goto out_dump;
 916                 }
 917
 918                 if (snod->sqnum < c->cs_sqnum) {
 919                         dbg_err("bad sqnum %llu, commit sqnum %llu",
 920                                 snod->sqnum, c->cs_sqnum);
 921                         goto out_dump;
 922                 }
 923
 924                 if (snod->sqnum > c->max_sqnum)
 925                         c->max_sqnum = snod->sqnum;
 926
 927                 switch (snod->type) {
 928                 case UBIFS_REF_NODE: {
 929                         const struct ubifs_ref_node *ref = snod->node;
 930
 931                         err = validate_ref(c, ref);
 932                         if (err == 1)
 933                                 break; /* Already have this bud */
 934                         if (err)
 935                                 goto out_dump;
 936
 937                         err = add_replay_bud(c, le32_to_cpu(ref->lnum),
 938                                              le32_to_cpu(ref->offs),
 939                                              le32_to_cpu(ref->jhead),
 940                                              snod->sqnum);
 941                         if (err)
 942                                 goto out;
 943
 944                         break;
 945                 }
 946                 case UBIFS_CS_NODE:
 947                         /* Make sure it sits at the beginning of LEB */
 948                         if (snod->offs != 0) {
 949                                 ubifs_err("unexpected node in log");
 950                                 goto out_dump;
 951                         }
 952                         break;
 953                 default:
 954                         ubifs_err("unexpected node in log");
 955                         goto out_dump;
 956                 }
 957         }
 958
 959         if (sleb->endpt || c->lhead_offs >= c->leb_size) {
 960                 c->lhead_lnum = lnum;
 961                 c->lhead_offs = sleb->endpt;
 962         }
 963
 964         err = !sleb->endpt;
 965 out:
 966         ubifs_scan_destroy(sleb);
 967         return err;
 968
 969 out_dump:
 970         ubifs_err("log error detected while replaying the log at LEB %d:%d",
 971                   lnum, offs + snod->offs);
 972         dbg_dump_node(c, snod->node);
 973         ubifs_scan_destroy(sleb);
 974         return -EINVAL;
 975 }
 976
 977 /**
 978  * take_ihead - update the status of the index head in lprops to 'taken'.
 979  * @c: UBIFS file-system description object
 980  *
 981  * This function returns the amount of free space in the index head LEB or a
 982  * negative error code.
 983  */
 984 static int take_ihead(struct ubifs_info *c)
 985 {
 986         const struct ubifs_lprops *lp;
 987         int err, free;
 988
 989         ubifs_get_lprops(c);
 990
 991         lp = ubifs_lpt_lookup_dirty(c, c->ihead_lnum);
 992         if (IS_ERR(lp)) {
 993                 err = PTR_ERR(lp);
 994                 goto out;
 995         }
 996
 997         free = lp->free;
 998
 999         lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC,
1000                              lp->flags | LPROPS_TAKEN, 0);
1001         if (IS_ERR(lp)) {
1002                 err = PTR_ERR(lp);
1003                 goto out;
1004         }
1005
1006         err = free;
1007 out:
1008         ubifs_release_lprops(c);
1009         return err;
1010 }
1011
1012 /**
1013  * ubifs_replay_journal - replay journal.
1014  * @c: UBIFS file-system description object
1015  *
1016  * This function scans the journal, replays and cleans it up. It makes sure all
1017  * memory data structures related to uncommitted journal are built (dirty TNC
1018  * tree, tree of buds, modified lprops, etc).
1019  */
1020 int ubifs_replay_journal(struct ubifs_info *c)
1021 {
1022         int err, i, lnum, offs, free;
1023
1024         BUILD_BUG_ON(UBIFS_TRUN_KEY > 5);
1025
1026         /* Update the status of the index head in lprops to 'taken' */
1027         free = take_ihead(c);
1028         if (free < 0)
1029                 return free; /* Error code */
1030
1031         if (c->ihead_offs != c->leb_size - free) {
1032                 ubifs_err("bad index head LEB %d:%d", c->ihead_lnum,
1033                           c->ihead_offs);
1034                 return -EINVAL;
1035         }
1036
1037         dbg_mnt("start replaying the journal");
1038         c->replaying = 1;
1039         lnum = c->ltail_lnum = c->lhead_lnum;
1040         offs = c->lhead_offs;
1041
1042         for (i = 0; i < c->log_lebs; i++, lnum++) {
1043                 if (lnum >= UBIFS_LOG_LNUM + c->log_lebs) {
1044                         /*
1045                          * The log is logically circular, we reached the last
1046                          * LEB, switch to the first one.
1047                          */
1048                         lnum = UBIFS_LOG_LNUM;
1049                         offs = 0;
1050                 }
1051                 err = replay_log_leb(c, lnum, offs, c->sbuf);
1052                 if (err == 1)
1053                         /* We hit the end of the log */
1054                         break;
1055                 if (err)
1056                         goto out;
1057                 offs = 0;
1058         }
1059
1060         err = replay_buds(c);
1061         if (err)
1062                 goto out;
1063
1064         err = apply_replay_tree(c);
1065         if (err)
1066                 goto out;
1067
1068         /*
1069          * UBIFS budgeting calculations use @c->bi.uncommitted_idx variable
1070          * to roughly estimate index growth. Things like @c->bi.min_idx_lebs
1071          * depend on it. This means we have to initialize it to make sure
1072          * budgeting works properly.
1073          */
1074         c->bi.uncommitted_idx = atomic_long_read(&c->dirty_zn_cnt);
1075         c->bi.uncommitted_idx *= c->max_idx_node_sz;
1076
1077         ubifs_assert(c->bud_bytes <= c->max_bud_bytes || c->need_recovery);
1078         dbg_mnt("finished, log head LEB %d:%d, max_sqnum %llu, "
1079                 "highest_inum %lu", c->lhead_lnum, c->lhead_offs, c->max_sqnum,
1080                 (unsigned long)c->highest_inum);
1081 out:
1082         destroy_replay_tree(c);
1083         destroy_bud_list(c);
1084         c->replaying = 0;
1085         return err;
1086 }