lwext4/ext4_journal.c

   1 /*
   2  * Copyright (c) 2015 Grzegorz Kostka (kostka.grzegorz@gmail.com)
   3  * Copyright (c) 2015 Kaho Ng (ngkaho1234@gmail.com)
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * - Redistributions of source code must retain the above copyright
  11  *   notice, this list of conditions and the following disclaimer.
  12  * - Redistributions in binary form must reproduce the above copyright
  13  *   notice, this list of conditions and the following disclaimer in the
  14  *   documentation and/or other materials provided with the distribution.
  15  * - The name of the author may not be used to endorse or promote products
  16  *   derived from this software without specific prior written permission.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  19  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  20  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  21  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  22  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  23  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  27  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  */
  29
  30 /** @addtogroup lwext4
  31  * @{
  32  */
  33 /**
  34  * @file  ext4_journal.c
  35  * @brief Journal handle functions
  36  */
  37
  38 #include "ext4_config.h"
  39 #include "ext4_types.h"
  40 #include "ext4_fs.h"
  41 #include "ext4_super.h"
  42 #include "ext4_journal.h"
  43 #include "ext4_errno.h"
  44 #include "ext4_blockdev.h"
  45 #include "ext4_crc32c.h"
  46 #include "ext4_debug.h"
  47
  48 #include <string.h>
  49 #include <stdlib.h>
  50
  51 /**@brief  Revoke entry during journal replay.*/
  52 struct revoke_entry {
  53         /**@brief  Block number not to be replayed.*/
  54         ext4_fsblk_t block;
  55
  56         /**@brief  For any transaction id smaller
  57          *         than trans_id, records of @block
  58          *         in those transactions should not
  59          *         be replayed.*/
  60         uint32_t trans_id;
  61
  62         /**@brief  Revoke tree node.*/
  63         RB_ENTRY(revoke_entry) revoke_node;
  64 };
  65
  66 /**@brief  Valid journal replay information.*/
  67 struct recover_info {
  68         /**@brief  Starting transaction id.*/
  69         uint32_t start_trans_id;
  70
  71         /**@brief  Ending transaction id.*/
  72         uint32_t last_trans_id;
  73
  74         /**@brief  Used as internal argument.*/
  75         uint32_t this_trans_id;
  76
  77         /**@brief  RB-Tree storing revoke entries.*/
  78         RB_HEAD(jbd_revoke, revoke_entry) revoke_root;
  79 };
  80
  81 /**@brief  Journal replay internal arguments.*/
  82 struct replay_arg {
  83         /**@brief  Journal replay information.*/
  84         struct recover_info *info;
  85
  86         /**@brief  Current block we are on.*/
  87         uint32_t *this_block;
  88
  89         /**@brief  Current trans_id we are on.*/
  90         uint32_t this_trans_id;
  91 };
  92
  93 static int
  94 jbd_revoke_entry_cmp(struct revoke_entry *a, struct revoke_entry *b)
  95 {
  96         if (a->block > b->block)
  97                 return 1;
  98         else if (a->block < b->block)
  99                 return -1;
 100         return 0;
 101 }
 102
 103 static int
 104 jbd_block_rec_cmp(struct jbd_block_rec *a, struct jbd_block_rec *b)
 105 {
 106         if (a->lba > b->lba)
 107                 return 1;
 108         else if (a->lba < b->lba)
 109                 return -1;
 110         return 0;
 111 }
 112
 113 RB_GENERATE_INTERNAL(jbd_revoke, revoke_entry, revoke_node,
 114                      jbd_revoke_entry_cmp, static inline)
 115 RB_GENERATE_INTERNAL(jbd_block, jbd_block_rec, block_rec_node,
 116                      jbd_block_rec_cmp, static inline)
 117
 118 #define jbd_alloc_revoke_entry() calloc(1, sizeof(struct revoke_entry))
 119 #define jbd_free_revoke_entry(addr) free(addr)
 120
 121 /**@brief  Write jbd superblock to disk.
 122  * @param  jbd_fs jbd filesystem
 123  * @param  s jbd superblock
 124  * @return standard error code*/
 125 static int jbd_sb_write(struct jbd_fs *jbd_fs, struct jbd_sb *s)
 126 {
 127         int rc;
 128         struct ext4_fs *fs = jbd_fs->inode_ref.fs;
 129         uint64_t offset;
 130         ext4_fsblk_t fblock;
 131         rc = jbd_inode_bmap(jbd_fs, 0, &fblock);
 132         if (rc != EOK)
 133                 return rc;
 134
 135         offset = fblock * ext4_sb_get_block_size(&fs->sb);
 136         return ext4_block_writebytes(fs->bdev, offset, s,
 137                                      EXT4_SUPERBLOCK_SIZE);
 138 }
 139
 140 /**@brief  Read jbd superblock from disk.
 141  * @param  jbd_fs jbd filesystem
 142  * @param  s jbd superblock
 143  * @return standard error code*/
 144 static int jbd_sb_read(struct jbd_fs *jbd_fs, struct jbd_sb *s)
 145 {
 146         int rc;
 147         struct ext4_fs *fs = jbd_fs->inode_ref.fs;
 148         uint64_t offset;
 149         ext4_fsblk_t fblock;
 150         rc = jbd_inode_bmap(jbd_fs, 0, &fblock);
 151         if (rc != EOK)
 152                 return rc;
 153
 154         offset = fblock * ext4_sb_get_block_size(&fs->sb);
 155         return ext4_block_readbytes(fs->bdev, offset, s,
 156                                     EXT4_SUPERBLOCK_SIZE);
 157 }
 158
 159 /**@brief  Verify jbd superblock.
 160  * @param  sb jbd superblock
 161  * @return true if jbd superblock is valid */
 162 static bool jbd_verify_sb(struct jbd_sb *sb)
 163 {
 164         struct jbd_bhdr *header = &sb->header;
 165         if (jbd_get32(header, magic) != JBD_MAGIC_NUMBER)
 166                 return false;
 167
 168         if (jbd_get32(header, blocktype) != JBD_SUPERBLOCK &&
 169             jbd_get32(header, blocktype) != JBD_SUPERBLOCK_V2)
 170                 return false;
 171
 172         return true;
 173 }
 174
 175 /**@brief  Write back dirty jbd superblock to disk.
 176  * @param  jbd_fs jbd filesystem
 177  * @return standard error code*/
 178 static int jbd_write_sb(struct jbd_fs *jbd_fs)
 179 {
 180         int rc = EOK;
 181         if (jbd_fs->dirty) {
 182                 rc = jbd_sb_write(jbd_fs, &jbd_fs->sb);
 183                 if (rc != EOK)
 184                         return rc;
 185
 186                 jbd_fs->dirty = false;
 187         }
 188         return rc;
 189 }
 190
 191 /**@brief  Get reference to jbd filesystem.
 192  * @param  fs Filesystem to load journal of
 193  * @param  jbd_fs jbd filesystem
 194  * @return standard error code*/
 195 int jbd_get_fs(struct ext4_fs *fs,
 196                struct jbd_fs *jbd_fs)
 197 {
 198         int rc;
 199         uint32_t journal_ino;
 200
 201         memset(jbd_fs, 0, sizeof(struct jbd_fs));
 202         /* See if there is journal inode on this filesystem.*/
 203         /* FIXME: detection on existance ofbkejournal bdev is
 204          *        missing.*/
 205         journal_ino = ext4_get32(&fs->sb, journal_inode_number);
 206
 207         rc = ext4_fs_get_inode_ref(fs,
 208                                    journal_ino,
 209                                    &jbd_fs->inode_ref);
 210         if (rc != EOK) {
 211                 memset(jbd_fs, 0, sizeof(struct jbd_fs));
 212                 return rc;
 213         }
 214         rc = jbd_sb_read(jbd_fs, &jbd_fs->sb);
 215         if (rc != EOK) {
 216                 memset(jbd_fs, 0, sizeof(struct jbd_fs));
 217                 ext4_fs_put_inode_ref(&jbd_fs->inode_ref);
 218                 return rc;
 219         }
 220         if (!jbd_verify_sb(&jbd_fs->sb)) {
 221                 memset(jbd_fs, 0, sizeof(struct jbd_fs));
 222                 ext4_fs_put_inode_ref(&jbd_fs->inode_ref);
 223                 rc = EIO;
 224         }
 225
 226         return rc;
 227 }
 228
 229 /**@brief  Put reference of jbd filesystem.
 230  * @param  jbd_fs jbd filesystem
 231  * @return standard error code*/
 232 int jbd_put_fs(struct jbd_fs *jbd_fs)
 233 {
 234         int rc = EOK;
 235         rc = jbd_write_sb(jbd_fs);
 236
 237         ext4_fs_put_inode_ref(&jbd_fs->inode_ref);
 238         return rc;
 239 }
 240
 241 /**@brief  Data block lookup helper.
 242  * @param  jbd_fs jbd filesystem
 243  * @param  iblock block index
 244  * @param  fblock logical block address
 245  * @return standard error code*/
 246 int jbd_inode_bmap(struct jbd_fs *jbd_fs,
 247                    ext4_lblk_t iblock,
 248                    ext4_fsblk_t *fblock)
 249 {
 250         int rc = ext4_fs_get_inode_dblk_idx(
 251                         &jbd_fs->inode_ref,
 252                         iblock,
 253                         fblock,
 254                         false);
 255         return rc;
 256 }
 257
 258 /**@brief   jbd block get function (through cache).
 259  * @param   jbd_fs jbd filesystem
 260  * @param   block block descriptor
 261  * @param   fblock jbd logical block address
 262  * @return  standard error code*/
 263 static int jbd_block_get(struct jbd_fs *jbd_fs,
 264                   struct ext4_block *block,
 265                   ext4_fsblk_t fblock)
 266 {
 267         /* TODO: journal device. */
 268         int rc;
 269         ext4_lblk_t iblock = (ext4_lblk_t)fblock;
 270
 271         /* Lookup the logical block address of
 272          * fblock.*/
 273         rc = jbd_inode_bmap(jbd_fs, iblock,
 274                             &fblock);
 275         if (rc != EOK)
 276                 return rc;
 277
 278         struct ext4_blockdev *bdev = jbd_fs->inode_ref.fs->bdev;
 279         rc = ext4_block_get(bdev, block, fblock);
 280
 281         /* If succeeded, mark buffer as BC_FLUSH to indicate
 282          * that data should be written to disk immediately.*/
 283         if (rc == EOK)
 284                 ext4_bcache_set_flag(block->buf, BC_FLUSH);
 285
 286         return rc;
 287 }
 288
 289 /**@brief   jbd block get function (through cache, don't read).
 290  * @param   jbd_fs jbd filesystem
 291  * @param   block block descriptor
 292  * @param   fblock jbd logical block address
 293  * @return  standard error code*/
 294 static int jbd_block_get_noread(struct jbd_fs *jbd_fs,
 295                          struct ext4_block *block,
 296                          ext4_fsblk_t fblock)
 297 {
 298         /* TODO: journal device. */
 299         int rc;
 300         ext4_lblk_t iblock = (ext4_lblk_t)fblock;
 301         rc = jbd_inode_bmap(jbd_fs, iblock,
 302                             &fblock);
 303         if (rc != EOK)
 304                 return rc;
 305
 306         struct ext4_blockdev *bdev = jbd_fs->inode_ref.fs->bdev;
 307         rc = ext4_block_get_noread(bdev, block, fblock);
 308         if (rc == EOK)
 309                 ext4_bcache_set_flag(block->buf, BC_FLUSH);
 310
 311         return rc;
 312 }
 313
 314 /**@brief   jbd block set procedure (through cache).
 315  * @param   jbd_fs jbd filesystem
 316  * @param   block block descriptor
 317  * @return  standard error code*/
 318 static int jbd_block_set(struct jbd_fs *jbd_fs,
 319                   struct ext4_block *block)
 320 {
 321         return ext4_block_set(jbd_fs->inode_ref.fs->bdev,
 322                               block);
 323 }
 324
 325 /**@brief  helper functions to calculate
 326  *         block tag size, not including UUID part.
 327  * @param  jbd_fs jbd filesystem
 328  * @return tag size in bytes*/
 329 static int jbd_tag_bytes(struct jbd_fs *jbd_fs)
 330 {
 331         int size;
 332
 333         /* It is very easy to deal with the case which
 334          * JBD_FEATURE_INCOMPAT_CSUM_V3 is enabled.*/
 335         if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 336                                      JBD_FEATURE_INCOMPAT_CSUM_V3))
 337                 return sizeof(struct jbd_block_tag3);
 338
 339         size = sizeof(struct jbd_block_tag);
 340
 341         /* If JBD_FEATURE_INCOMPAT_CSUM_V2 is enabled,
 342          * add 2 bytes to size.*/
 343         if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 344                                      JBD_FEATURE_INCOMPAT_CSUM_V2))
 345                 size += sizeof(uint16_t);
 346
 347         if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 348                                      JBD_FEATURE_INCOMPAT_64BIT))
 349                 return size;
 350
 351         /* If block number is 4 bytes in size,
 352          * minus 4 bytes from size */
 353         return size - sizeof(uint32_t);
 354 }
 355
 356 /**@brief  Tag information. */
 357 struct tag_info {
 358         /**@brief  Tag size in bytes, including UUID part.*/
 359         int tag_bytes;
 360
 361         /**@brief  block number stored in this tag.*/
 362         ext4_fsblk_t block;
 363
 364         /**@brief  whether UUID part exists or not.*/
 365         bool uuid_exist;
 366
 367         /**@brief  UUID content if UUID part exists.*/
 368         uint8_t uuid[UUID_SIZE];
 369
 370         /**@brief  Is this the last tag? */
 371         bool last_tag;
 372 };
 373
 374 /**@brief  Extract information from a block tag.
 375  * @param  __tag pointer to the block tag
 376  * @param  tag_bytes block tag size of this jbd filesystem
 377  * @param  remaining size in buffer containing the block tag
 378  * @param  tag_info information of this tag.
 379  * @return  EOK when succeed, otherwise return EINVAL.*/
 380 static int
 381 jbd_extract_block_tag(struct jbd_fs *jbd_fs,
 382                       void *__tag,
 383                       int tag_bytes,
 384                       int32_t remain_buf_size,
 385                       struct tag_info *tag_info)
 386 {
 387         char *uuid_start;
 388         tag_info->tag_bytes = tag_bytes;
 389         tag_info->uuid_exist = false;
 390         tag_info->last_tag = false;
 391
 392         /* See whether it is possible to hold a valid block tag.*/
 393         if (remain_buf_size - tag_bytes < 0)
 394                 return EINVAL;
 395
 396         if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 397                                      JBD_FEATURE_INCOMPAT_CSUM_V3)) {
 398                 struct jbd_block_tag3 *tag = __tag;
 399                 tag_info->block = jbd_get32(tag, blocknr);
 400                 if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 401                                              JBD_FEATURE_INCOMPAT_64BIT))
 402                          tag_info->block |=
 403                                  (uint64_t)jbd_get32(tag, blocknr_high) << 32;
 404
 405                 if (jbd_get32(tag, flags) & JBD_FLAG_ESCAPE)
 406                         tag_info->block = 0;
 407
 408                 if (!(jbd_get32(tag, flags) & JBD_FLAG_SAME_UUID)) {
 409                         /* See whether it is possible to hold UUID part.*/
 410                         if (remain_buf_size - tag_bytes < UUID_SIZE)
 411                                 return EINVAL;
 412
 413                         uuid_start = (char *)tag + tag_bytes;
 414                         tag_info->uuid_exist = true;
 415                         tag_info->tag_bytes += UUID_SIZE;
 416                         memcpy(tag_info->uuid, uuid_start, UUID_SIZE);
 417                 }
 418
 419                 if (jbd_get32(tag, flags) & JBD_FLAG_LAST_TAG)
 420                         tag_info->last_tag = true;
 421
 422         } else {
 423                 struct jbd_block_tag *tag = __tag;
 424                 tag_info->block = jbd_get32(tag, blocknr);
 425                 if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 426                                              JBD_FEATURE_INCOMPAT_64BIT))
 427                          tag_info->block |=
 428                                  (uint64_t)jbd_get32(tag, blocknr_high) << 32;
 429
 430                 if (jbd_get16(tag, flags) & JBD_FLAG_ESCAPE)
 431                         tag_info->block = 0;
 432
 433                 if (!(jbd_get16(tag, flags) & JBD_FLAG_SAME_UUID)) {
 434                         /* See whether it is possible to hold UUID part.*/
 435                         if (remain_buf_size - tag_bytes < UUID_SIZE)
 436                                 return EINVAL;
 437
 438                         uuid_start = (char *)tag + tag_bytes;
 439                         tag_info->uuid_exist = true;
 440                         tag_info->tag_bytes += UUID_SIZE;
 441                         memcpy(tag_info->uuid, uuid_start, UUID_SIZE);
 442                 }
 443
 444                 if (jbd_get16(tag, flags) & JBD_FLAG_LAST_TAG)
 445                         tag_info->last_tag = true;
 446
 447         }
 448         return EOK;
 449 }
 450
 451 /**@brief  Write information to a block tag.
 452  * @param  __tag pointer to the block tag
 453  * @param  remaining size in buffer containing the block tag
 454  * @param  tag_info information of this tag.
 455  * @return  EOK when succeed, otherwise return EINVAL.*/
 456 static int
 457 jbd_write_block_tag(struct jbd_fs *jbd_fs,
 458                     void *__tag,
 459                     int32_t remain_buf_size,
 460                     struct tag_info *tag_info)
 461 {
 462         char *uuid_start;
 463         int tag_bytes = jbd_tag_bytes(jbd_fs);
 464
 465         tag_info->tag_bytes = tag_bytes;
 466
 467         /* See whether it is possible to hold a valid block tag.*/
 468         if (remain_buf_size - tag_bytes < 0)
 469                 return EINVAL;
 470
 471         if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 472                                      JBD_FEATURE_INCOMPAT_CSUM_V3)) {
 473                 struct jbd_block_tag3 *tag = __tag;
 474                 memset(tag, 0, sizeof(struct jbd_block_tag3));
 475                 jbd_set32(tag, blocknr, tag_info->block);
 476                 if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 477                                              JBD_FEATURE_INCOMPAT_64BIT))
 478                         jbd_set32(tag, blocknr_high, tag_info->block >> 32);
 479
 480                 if (tag_info->uuid_exist) {
 481                         /* See whether it is possible to hold UUID part.*/
 482                         if (remain_buf_size - tag_bytes < UUID_SIZE)
 483                                 return EINVAL;
 484
 485                         uuid_start = (char *)tag + tag_bytes;
 486                         tag_info->tag_bytes += UUID_SIZE;
 487                         memcpy(uuid_start, tag_info->uuid, UUID_SIZE);
 488                 } else
 489                         jbd_set32(tag, flags,
 490                                   jbd_get32(tag, flags) | JBD_FLAG_SAME_UUID);
 491
 492                 if (tag_info->last_tag)
 493                         jbd_set32(tag, flags,
 494                                   jbd_get32(tag, flags) | JBD_FLAG_LAST_TAG);
 495
 496         } else {
 497                 struct jbd_block_tag *tag = __tag;
 498                 memset(tag, 0, sizeof(struct jbd_block_tag));
 499                 jbd_set32(tag, blocknr, tag_info->block);
 500                 if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 501                                              JBD_FEATURE_INCOMPAT_64BIT))
 502                         jbd_set32(tag, blocknr_high, tag_info->block >> 32);
 503
 504                 if (tag_info->uuid_exist) {
 505                         /* See whether it is possible to hold UUID part.*/
 506                         if (remain_buf_size - tag_bytes < UUID_SIZE)
 507                                 return EINVAL;
 508
 509                         uuid_start = (char *)tag + tag_bytes;
 510                         tag_info->tag_bytes += UUID_SIZE;
 511                         memcpy(uuid_start, tag_info->uuid, UUID_SIZE);
 512                 } else
 513                         jbd_set16(tag, flags,
 514                                   jbd_get16(tag, flags) | JBD_FLAG_SAME_UUID);
 515
 516                 if (tag_info->last_tag)
 517                         jbd_set16(tag, flags,
 518                                   jbd_get16(tag, flags) | JBD_FLAG_LAST_TAG);
 519
 520         }
 521         return EOK;
 522 }
 523
 524 /**@brief  Iterate all block tags in a block.
 525  * @param  jbd_fs jbd filesystem
 526  * @param  __tag_start pointer to the block
 527  * @param  tag_tbl_size size of the block
 528  * @param  func callback routine to indicate that
 529  *         a block tag is found
 530  * @param  arg additional argument to be passed to func */
 531 static void
 532 jbd_iterate_block_table(struct jbd_fs *jbd_fs,
 533                         void *__tag_start,
 534                         int32_t tag_tbl_size,
 535                         void (*func)(struct jbd_fs * jbd_fs,
 536                                         ext4_fsblk_t block,
 537                                         uint8_t *uuid,
 538                                         void *arg),
 539                         void *arg)
 540 {
 541         char *tag_start, *tag_ptr;
 542         int tag_bytes = jbd_tag_bytes(jbd_fs);
 543         tag_start = __tag_start;
 544         tag_ptr = tag_start;
 545
 546         /* Cut off the size of block tail storing checksum. */
 547         if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 548                                      JBD_FEATURE_INCOMPAT_CSUM_V2) ||
 549             JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 550                                      JBD_FEATURE_INCOMPAT_CSUM_V3))
 551                 tag_tbl_size -= sizeof(struct jbd_block_tail);
 552
 553         while (tag_tbl_size) {
 554                 struct tag_info tag_info;
 555                 int rc = jbd_extract_block_tag(jbd_fs,
 556                                       tag_ptr,
 557                                       tag_bytes,
 558                                       tag_tbl_size,
 559                                       &tag_info);
 560                 if (rc != EOK)
 561                         break;
 562
 563                 if (func)
 564                         func(jbd_fs, tag_info.block, tag_info.uuid, arg);
 565
 566                 /* Stop the iteration when we reach the last tag. */
 567                 if (tag_info.last_tag)
 568                         break;
 569
 570                 tag_ptr += tag_info.tag_bytes;
 571                 tag_tbl_size -= tag_info.tag_bytes;
 572         }
 573 }
 574
 575 static void jbd_display_block_tags(struct jbd_fs *jbd_fs,
 576                                    ext4_fsblk_t block,
 577                                    uint8_t *uuid,
 578                                    void *arg)
 579 {
 580         uint32_t *iblock = arg;
 581         ext4_dbg(DEBUG_JBD, "Block in block_tag: %" PRIu64 "\n", block);
 582         (*iblock)++;
 583         (void)jbd_fs;
 584         (void)uuid;
 585         return;
 586 }
 587
 588 static struct revoke_entry *
 589 jbd_revoke_entry_lookup(struct recover_info *info, ext4_fsblk_t block)
 590 {
 591         struct revoke_entry tmp = {
 592                 .block = block
 593         };
 594
 595         return RB_FIND(jbd_revoke, &info->revoke_root, &tmp);
 596 }
 597
 598 /**@brief  Replay a block in a transaction.
 599  * @param  jbd_fs jbd filesystem
 600  * @param  block  block address to be replayed.*/
 601 static void jbd_replay_block_tags(struct jbd_fs *jbd_fs,
 602                                   ext4_fsblk_t block,
 603                                   uint8_t *uuid __unused,
 604                                   void *__arg)
 605 {
 606         int r;
 607         struct replay_arg *arg = __arg;
 608         struct recover_info *info = arg->info;
 609         uint32_t *this_block = arg->this_block;
 610         struct revoke_entry *revoke_entry;
 611         struct ext4_block journal_block, ext4_block;
 612         struct ext4_fs *fs = jbd_fs->inode_ref.fs;
 613
 614         (*this_block)++;
 615
 616         /* We replay this block only if the current transaction id
 617          * is equal or greater than that in revoke entry.*/
 618         revoke_entry = jbd_revoke_entry_lookup(info, block);
 619         if (revoke_entry &&
 620             arg->this_trans_id < revoke_entry->trans_id)
 621                 return;
 622
 623         ext4_dbg(DEBUG_JBD,
 624                  "Replaying block in block_tag: %" PRIu64 "\n",
 625                  block);
 626
 627         r = jbd_block_get(jbd_fs, &journal_block, *this_block);
 628         if (r != EOK)
 629                 return;
 630
 631         /* We need special treatment for ext4 superblock. */
 632         if (block) {
 633                 r = ext4_block_get_noread(fs->bdev, &ext4_block, block);
 634                 if (r != EOK) {
 635                         jbd_block_set(jbd_fs, &journal_block);
 636                         return;
 637                 }
 638
 639                 memcpy(ext4_block.data,
 640                         journal_block.data,
 641                         jbd_get32(&jbd_fs->sb, blocksize));
 642
 643                 ext4_bcache_set_dirty(ext4_block.buf);
 644                 ext4_block_set(fs->bdev, &ext4_block);
 645         } else {
 646                 uint16_t mount_count, state;
 647                 mount_count = ext4_get16(&fs->sb, mount_count);
 648                 state = ext4_get16(&fs->sb, state);
 649
 650                 memcpy(&fs->sb,
 651                         journal_block.data + EXT4_SUPERBLOCK_OFFSET,
 652                         EXT4_SUPERBLOCK_SIZE);
 653
 654                 /* Mark system as mounted */
 655                 ext4_set16(&fs->sb, state, state);
 656                 r = ext4_sb_write(fs->bdev, &fs->sb);
 657                 if (r != EOK)
 658                         return;
 659
 660                 /*Update mount count*/
 661                 ext4_set16(&fs->sb, mount_count, mount_count);
 662         }
 663
 664         jbd_block_set(jbd_fs, &journal_block);
 665
 666         return;
 667 }
 668
 669 /**@brief  Add block address to revoke tree, along with
 670  *         its transaction id.
 671  * @param  info  journal replay info
 672  * @param  block  block address to be replayed.*/
 673 static void jbd_add_revoke_block_tags(struct recover_info *info,
 674                                       ext4_fsblk_t block)
 675 {
 676         struct revoke_entry *revoke_entry;
 677
 678         ext4_dbg(DEBUG_JBD, "Add block %" PRIu64 " to revoke tree\n", block);
 679         /* If the revoke entry with respect to the block address
 680          * exists already, update its transaction id.*/
 681         revoke_entry = jbd_revoke_entry_lookup(info, block);
 682         if (revoke_entry) {
 683                 revoke_entry->trans_id = info->this_trans_id;
 684                 return;
 685         }
 686
 687         revoke_entry = jbd_alloc_revoke_entry();
 688         ext4_assert(revoke_entry);
 689         revoke_entry->block = block;
 690         revoke_entry->trans_id = info->this_trans_id;
 691         RB_INSERT(jbd_revoke, &info->revoke_root, revoke_entry);
 692
 693         return;
 694 }
 695
 696 static void jbd_destroy_revoke_tree(struct recover_info *info)
 697 {
 698         while (!RB_EMPTY(&info->revoke_root)) {
 699                 struct revoke_entry *revoke_entry =
 700                         RB_MIN(jbd_revoke, &info->revoke_root);
 701                 ext4_assert(revoke_entry);
 702                 RB_REMOVE(jbd_revoke, &info->revoke_root, revoke_entry);
 703                 jbd_free_revoke_entry(revoke_entry);
 704         }
 705 }
 706
 707 /* Make sure we wrap around the log correctly! */
 708 #define wrap(sb, var)                                           \
 709 do {                                                                    \
 710         if (var >= jbd_get32((sb), maxlen))                                     \
 711                 var -= (jbd_get32((sb), maxlen) - jbd_get32((sb), first));      \
 712 } while (0)
 713
 714 #define ACTION_SCAN 0
 715 #define ACTION_REVOKE 1
 716 #define ACTION_RECOVER 2
 717
 718 /**@brief  Add entries in a revoke block to revoke tree.
 719  * @param  jbd_fs jbd filesystem
 720  * @param  header revoke block header
 721  * @param  recover_info  journal replay info*/
 722 static void jbd_build_revoke_tree(struct jbd_fs *jbd_fs,
 723                                   struct jbd_bhdr *header,
 724                                   struct recover_info *info)
 725 {
 726         char *blocks_entry;
 727         struct jbd_revoke_header *revoke_hdr =
 728                 (struct jbd_revoke_header *)header;
 729         uint32_t i, nr_entries, record_len = 4;
 730
 731         /* If we are working on a 64bit jbd filesystem, */
 732         if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 733                                      JBD_FEATURE_INCOMPAT_64BIT))
 734                 record_len = 8;
 735
 736         nr_entries = (jbd_get32(revoke_hdr, count) -
 737                         sizeof(struct jbd_revoke_header)) /
 738                         record_len;
 739
 740         blocks_entry = (char *)(revoke_hdr + 1);
 741
 742         for (i = 0;i < nr_entries;i++) {
 743                 if (record_len == 8) {
 744                         uint64_t *blocks =
 745                                 (uint64_t *)blocks_entry;
 746                         jbd_add_revoke_block_tags(info, to_be64(*blocks));
 747                 } else {
 748                         uint32_t *blocks =
 749                                 (uint32_t *)blocks_entry;
 750                         jbd_add_revoke_block_tags(info, to_be32(*blocks));
 751                 }
 752                 blocks_entry += record_len;
 753         }
 754 }
 755
 756 static void jbd_debug_descriptor_block(struct jbd_fs *jbd_fs,
 757                                        struct jbd_bhdr *header,
 758                                        uint32_t *iblock)
 759 {
 760         jbd_iterate_block_table(jbd_fs,
 761                                 header + 1,
 762                                 jbd_get32(&jbd_fs->sb, blocksize) -
 763                                         sizeof(struct jbd_bhdr),
 764                                 jbd_display_block_tags,
 765                                 iblock);
 766 }
 767
 768 static void jbd_replay_descriptor_block(struct jbd_fs *jbd_fs,
 769                                         struct jbd_bhdr *header,
 770                                         struct replay_arg *arg)
 771 {
 772         jbd_iterate_block_table(jbd_fs,
 773                                 header + 1,
 774                                 jbd_get32(&jbd_fs->sb, blocksize) -
 775                                         sizeof(struct jbd_bhdr),
 776                                 jbd_replay_block_tags,
 777                                 arg);
 778 }
 779
 780 /**@brief  The core routine of journal replay.
 781  * @param  jbd_fs jbd filesystem
 782  * @param  recover_info  journal replay info
 783  * @param  action action needed to be taken
 784  * @return standard error code*/
 785 static int jbd_iterate_log(struct jbd_fs *jbd_fs,
 786                            struct recover_info *info,
 787                            int action)
 788 {
 789         int r = EOK;
 790         bool log_end = false;
 791         struct jbd_sb *sb = &jbd_fs->sb;
 792         uint32_t start_trans_id, this_trans_id;
 793         uint32_t start_block, this_block;
 794
 795         /* We start iterating valid blocks in the whole journal.*/
 796         start_trans_id = this_trans_id = jbd_get32(sb, sequence);
 797         start_block = this_block = jbd_get32(sb, start);
 798
 799         ext4_dbg(DEBUG_JBD, "Start of journal at trans id: %" PRIu32 "\n",
 800                             start_trans_id);
 801
 802         while (!log_end) {
 803                 struct ext4_block block;
 804                 struct jbd_bhdr *header;
 805                 /* If we are not scanning for the last
 806                  * valid transaction in the journal,
 807                  * we will stop when we reach the end of
 808                  * the journal.*/
 809                 if (action != ACTION_SCAN)
 810                         if (this_trans_id > info->last_trans_id) {
 811                                 log_end = true;
 812                                 continue;
 813                         }
 814
 815                 r = jbd_block_get(jbd_fs, &block, this_block);
 816                 if (r != EOK)
 817                         break;
 818
 819                 header = (struct jbd_bhdr *)block.data;
 820                 /* This block does not have a valid magic number,
 821                  * so we have reached the end of the journal.*/
 822                 if (jbd_get32(header, magic) != JBD_MAGIC_NUMBER) {
 823                         jbd_block_set(jbd_fs, &block);
 824                         log_end = true;
 825                         continue;
 826                 }
 827
 828                 /* If the transaction id we found is not expected,
 829                  * we may have reached the end of the journal.
 830                  *
 831                  * If we are not scanning the journal, something
 832                  * bad might have taken place. :-( */
 833                 if (jbd_get32(header, sequence) != this_trans_id) {
 834                         if (action != ACTION_SCAN)
 835                                 r = EIO;
 836
 837                         jbd_block_set(jbd_fs, &block);
 838                         log_end = true;
 839                         continue;
 840                 }
 841
 842                 switch (jbd_get32(header, blocktype)) {
 843                 case JBD_DESCRIPTOR_BLOCK:
 844                         ext4_dbg(DEBUG_JBD, "Descriptor block: %" PRIu32", "
 845                                             "trans_id: %" PRIu32"\n",
 846                                             this_block, this_trans_id);
 847                         if (action == ACTION_RECOVER) {
 848                                 struct replay_arg replay_arg;
 849                                 replay_arg.info = info;
 850                                 replay_arg.this_block = &this_block;
 851                                 replay_arg.this_trans_id = this_trans_id;
 852
 853                                 jbd_replay_descriptor_block(jbd_fs,
 854                                                 header, &replay_arg);
 855                         } else
 856                                 jbd_debug_descriptor_block(jbd_fs,
 857                                                 header, &this_block);
 858
 859                         break;
 860                 case JBD_COMMIT_BLOCK:
 861                         ext4_dbg(DEBUG_JBD, "Commit block: %" PRIu32", "
 862                                             "trans_id: %" PRIu32"\n",
 863                                             this_block, this_trans_id);
 864                         /* This is the end of a transaction,
 865                          * we may now proceed to the next transaction.
 866                          */
 867                         this_trans_id++;
 868                         break;
 869                 case JBD_REVOKE_BLOCK:
 870                         ext4_dbg(DEBUG_JBD, "Revoke block: %" PRIu32", "
 871                                             "trans_id: %" PRIu32"\n",
 872                                             this_block, this_trans_id);
 873                         if (action == ACTION_REVOKE) {
 874                                 info->this_trans_id = this_trans_id;
 875                                 jbd_build_revoke_tree(jbd_fs,
 876                                                 header, info);
 877                         }
 878                         break;
 879                 default:
 880                         log_end = true;
 881                         break;
 882                 }
 883                 jbd_block_set(jbd_fs, &block);
 884                 this_block++;
 885                 wrap(sb, this_block);
 886                 if (this_block == start_block)
 887                         log_end = true;
 888
 889         }
 890         ext4_dbg(DEBUG_JBD, "End of journal.\n");
 891         if (r == EOK && action == ACTION_SCAN) {
 892                 /* We have finished scanning the journal. */
 893                 info->start_trans_id = start_trans_id;
 894                 if (this_trans_id > start_trans_id)
 895                         info->last_trans_id = this_trans_id - 1;
 896                 else
 897                         info->last_trans_id = this_trans_id;
 898         }
 899
 900         return r;
 901 }
 902
 903 /**@brief  Replay journal.
 904  * @param  jbd_fs jbd filesystem
 905  * @return standard error code*/
 906 int jbd_recover(struct jbd_fs *jbd_fs)
 907 {
 908         int r;
 909         struct recover_info info;
 910         struct jbd_sb *sb = &jbd_fs->sb;
 911         if (!sb->start)
 912                 return EOK;
 913
 914         RB_INIT(&info.revoke_root);
 915
 916         r = jbd_iterate_log(jbd_fs, &info, ACTION_SCAN);
 917         if (r != EOK)
 918                 return r;
 919
 920         r = jbd_iterate_log(jbd_fs, &info, ACTION_REVOKE);
 921         if (r != EOK)
 922                 return r;
 923
 924         r = jbd_iterate_log(jbd_fs, &info, ACTION_RECOVER);
 925         if (r == EOK) {
 926                 /* If we successfully replay the journal,
 927                  * clear EXT4_FINCOM_RECOVER flag on the
 928                  * ext4 superblock, and set the start of
 929                  * journal to 0.*/
 930                 uint32_t features_incompatible =
 931                         ext4_get32(&jbd_fs->inode_ref.fs->sb,
 932                                    features_incompatible);
 933                 jbd_set32(&jbd_fs->sb, start, 0);
 934                 features_incompatible &= ~EXT4_FINCOM_RECOVER;
 935                 ext4_set32(&jbd_fs->inode_ref.fs->sb,
 936                            features_incompatible,
 937                            features_incompatible);
 938                 jbd_fs->dirty = true;
 939                 r = ext4_sb_write(jbd_fs->inode_ref.fs->bdev,
 940                                   &jbd_fs->inode_ref.fs->sb);
 941         }
 942         jbd_destroy_revoke_tree(&info);
 943         return r;
 944 }
 945
 946 static void jbd_journal_write_sb(struct jbd_journal *journal)
 947 {
 948         struct jbd_fs *jbd_fs = journal->jbd_fs;
 949         jbd_set32(&jbd_fs->sb, start, journal->start);
 950         jbd_set32(&jbd_fs->sb, sequence, journal->trans_id);
 951         jbd_fs->dirty = true;
 952 }
 953
 954 /**@brief  Start accessing the journal.
 955  * @param  jbd_fs jbd filesystem
 956  * @param  journal current journal session
 957  * @return standard error code*/
 958 int jbd_journal_start(struct jbd_fs *jbd_fs,
 959                       struct jbd_journal *journal)
 960 {
 961         int r;
 962         uint32_t features_incompatible =
 963                         ext4_get32(&jbd_fs->inode_ref.fs->sb,
 964                                    features_incompatible);
 965         features_incompatible |= EXT4_FINCOM_RECOVER;
 966         ext4_set32(&jbd_fs->inode_ref.fs->sb,
 967                         features_incompatible,
 968                         features_incompatible);
 969         r = ext4_sb_write(jbd_fs->inode_ref.fs->bdev,
 970                         &jbd_fs->inode_ref.fs->sb);
 971         if (r != EOK)
 972                 return r;
 973
 974         journal->first = jbd_get32(&jbd_fs->sb, first);
 975         journal->start = journal->first;
 976         journal->last = journal->first;
 977         journal->trans_id = 1;
 978         journal->alloc_trans_id = 1;
 979
 980         journal->block_size = jbd_get32(&jbd_fs->sb, blocksize);
 981
 982         TAILQ_INIT(&journal->trans_queue);
 983         TAILQ_INIT(&journal->cp_queue);
 984         RB_INIT(&journal->block_rec_root);
 985         journal->jbd_fs = jbd_fs;
 986         jbd_journal_write_sb(journal);
 987         return jbd_write_sb(jbd_fs);
 988 }
 989
 990 static void jbd_journal_flush_trans(struct jbd_trans *trans)
 991 {
 992         struct jbd_buf *jbd_buf, *tmp;
 993         struct jbd_journal *journal = trans->journal;
 994         struct ext4_fs *fs = journal->jbd_fs->inode_ref.fs;
 995         TAILQ_FOREACH_SAFE(jbd_buf, &trans->buf_queue, buf_node,
 996                         tmp) {
 997                 struct ext4_block block = jbd_buf->block;
 998                 ext4_block_flush_buf(fs->bdev, block.buf);
 999         }
1000 }
1001
1002 static void
1003 jbd_journal_skip_pure_revoke(struct jbd_journal *journal,
1004                              struct jbd_trans *trans)
1005 {
1006         journal->start = trans->start_iblock +
1007                 trans->alloc_blocks;
1008         wrap(&journal->jbd_fs->sb, journal->start);
1009         journal->trans_id = trans->trans_id + 1;
1010         jbd_journal_free_trans(journal,
1011                         trans, false);
1012         jbd_journal_write_sb(journal);
1013 }
1014
1015 static void
1016 jbd_journal_purge_cp_trans(struct jbd_journal *journal,
1017                            bool flush)
1018 {
1019         struct jbd_trans *trans;
1020         while ((trans = TAILQ_FIRST(&journal->cp_queue))) {
1021                 if (!trans->data_cnt) {
1022                         TAILQ_REMOVE(&journal->cp_queue,
1023                                         trans,
1024                                         trans_node);
1025                         jbd_journal_skip_pure_revoke(journal, trans);
1026                 } else {
1027                         if (trans->data_cnt ==
1028                                         trans->written_cnt) {
1029                                 journal->start =
1030                                         trans->start_iblock +
1031                                         trans->alloc_blocks;
1032                                 wrap(&journal->jbd_fs->sb,
1033                                                 journal->start);
1034                                 journal->trans_id =
1035                                         trans->trans_id + 1;
1036                                 TAILQ_REMOVE(&journal->cp_queue,
1037                                                 trans,
1038                                                 trans_node);
1039                                 jbd_journal_free_trans(journal,
1040                                                 trans,
1041                                                 false);
1042                                 jbd_journal_write_sb(journal);
1043                         } else if (!flush) {
1044                                 journal->start =
1045                                         trans->start_iblock;
1046                                 wrap(&journal->jbd_fs->sb,
1047                                                 journal->start);
1048                                 journal->trans_id =
1049                                         trans->trans_id;
1050                                 jbd_journal_write_sb(journal);
1051                                 break;
1052                         } else
1053                                 jbd_journal_flush_trans(trans);
1054                 }
1055         }
1056 }
1057
1058 /**@brief  Stop accessing the journal.
1059  * @param  journal current journal session
1060  * @return standard error code*/
1061 int jbd_journal_stop(struct jbd_journal *journal)
1062 {
1063         int r;
1064         struct jbd_fs *jbd_fs = journal->jbd_fs;
1065         uint32_t features_incompatible;
1066
1067         /* Commit all the transactions to the journal.*/
1068         jbd_journal_commit_all(journal);
1069
1070         /* Make sure that journalled content have reached
1071          * the disk.*/
1072         jbd_journal_purge_cp_trans(journal, true);
1073
1074         /* There should be no block record in this journal
1075          * session. */
1076         if (!RB_EMPTY(&journal->block_rec_root))
1077                 ext4_dbg(DEBUG_JBD,
1078                          DBG_WARN "There are still block records "
1079                                   "in this journal session!\n");
1080
1081         features_incompatible =
1082                 ext4_get32(&jbd_fs->inode_ref.fs->sb,
1083                            features_incompatible);
1084         features_incompatible &= ~EXT4_FINCOM_RECOVER;
1085         ext4_set32(&jbd_fs->inode_ref.fs->sb,
1086                         features_incompatible,
1087                         features_incompatible);
1088         r = ext4_sb_write(jbd_fs->inode_ref.fs->bdev,
1089                         &jbd_fs->inode_ref.fs->sb);
1090         if (r != EOK)
1091                 return r;
1092
1093         journal->start = 0;
1094         journal->trans_id = 0;
1095         jbd_journal_write_sb(journal);
1096         return jbd_write_sb(journal->jbd_fs);
1097 }
1098
1099 /**@brief  Allocate a block in the journal.
1100  * @param  journal current journal session
1101  * @param  trans transaction
1102  * @return allocated block address*/
1103 static uint32_t jbd_journal_alloc_block(struct jbd_journal *journal,
1104                                         struct jbd_trans *trans)
1105 {
1106         uint32_t start_block;
1107
1108         start_block = journal->last++;
1109         trans->alloc_blocks++;
1110         wrap(&journal->jbd_fs->sb, journal->last);
1111
1112         /* If there is no space left, flush all journalled
1113          * blocks to disk first.*/
1114         if (journal->last == journal->start)
1115                 jbd_journal_purge_cp_trans(journal, true);
1116
1117         return start_block;
1118 }
1119
1120 /**@brief  Allocate a new transaction
1121  * @param  journal current journal session
1122  * @return transaction allocated*/
1123 struct jbd_trans *
1124 jbd_journal_new_trans(struct jbd_journal *journal)
1125 {
1126         struct jbd_trans *trans = calloc(1, sizeof(struct jbd_trans));
1127         if (!trans)
1128                 return NULL;
1129
1130         /* We will assign a trans_id to this transaction,
1131          * once it has been committed.*/
1132         trans->journal = journal;
1133         trans->error = EOK;
1134         TAILQ_INIT(&trans->buf_queue);
1135         return trans;
1136 }
1137
1138 static void jbd_trans_end_write(struct ext4_bcache *bc __unused,
1139                           struct ext4_buf *buf __unused,
1140                           int res,
1141                           void *arg);
1142
1143 /**@brief  gain access to it before making any modications.
1144  * @param  journal current journal session
1145  * @param  trans transaction
1146  * @param  block descriptor
1147  * @return standard error code.*/
1148 int jbd_trans_get_access(struct jbd_journal *journal,
1149                          struct jbd_trans *trans,
1150                          struct ext4_block *block)
1151 {
1152         int r = EOK;
1153         struct ext4_fs *fs = journal->jbd_fs->inode_ref.fs;
1154         struct jbd_buf *jbd_buf = block->buf->end_write_arg;
1155
1156         /* If the buffer has already been modified, we should
1157          * flush dirty data in this buffer to disk.*/
1158         if (ext4_bcache_test_flag(block->buf, BC_DIRTY) &&
1159             block->buf->end_write == jbd_trans_end_write) {
1160                 ext4_assert(jbd_buf);
1161                 if (jbd_buf->trans != trans)
1162                         r = ext4_block_flush_buf(fs->bdev, block->buf);
1163
1164         }
1165         return r;
1166 }
1167
1168 static struct jbd_block_rec *
1169 jbd_trans_block_rec_lookup(struct jbd_journal *journal,
1170                            ext4_fsblk_t lba)
1171 {
1172         struct jbd_block_rec tmp = {
1173                 .lba = lba
1174         };
1175
1176         return RB_FIND(jbd_block,
1177                        &journal->block_rec_root,
1178                        &tmp);
1179 }
1180
1181 static inline struct jbd_block_rec *
1182 jbd_trans_insert_block_rec(struct jbd_trans *trans,
1183                            ext4_fsblk_t lba,
1184                            struct ext4_buf *buf)
1185 {
1186         struct jbd_block_rec *block_rec;
1187         block_rec = jbd_trans_block_rec_lookup(trans->journal, lba);
1188         if (block_rec) {
1189                 LIST_REMOVE(block_rec, tbrec_node);
1190                 /* Data should be flushed to disk already. */
1191                 ext4_assert(!block_rec->buf);
1192                 /* Now this block record belongs to this transaction. */
1193                 LIST_INSERT_HEAD(&trans->tbrec_list, block_rec, tbrec_node);
1194                 block_rec->trans = trans;
1195                 return block_rec;
1196         }
1197         block_rec = calloc(1, sizeof(struct jbd_block_rec));
1198         if (!block_rec)
1199                 return NULL;
1200
1201         block_rec->lba = lba;
1202         block_rec->buf = buf;
1203         block_rec->trans = trans;
1204         LIST_INSERT_HEAD(&trans->tbrec_list, block_rec, tbrec_node);
1205         RB_INSERT(jbd_block, &trans->journal->block_rec_root, block_rec);
1206         return block_rec;
1207 }
1208
1209 static inline void
1210 jbd_trans_remove_block_rec(struct jbd_journal *journal,
1211                            struct jbd_block_rec *block_rec,
1212                            struct jbd_trans *trans)
1213 {
1214         /* If this block record doesn't belong to this transaction,
1215          * give up.*/
1216         if (block_rec->trans == trans) {
1217                 LIST_REMOVE(block_rec, tbrec_node);
1218                 RB_REMOVE(jbd_block,
1219                                 &journal->block_rec_root,
1220                                 block_rec);
1221                 free(block_rec);
1222         }
1223 }
1224
1225 /**@brief  Add block to a transaction and mark it dirty.
1226  * @param  trans transaction
1227  * @param  block block descriptor
1228  * @return standard error code*/
1229 int jbd_trans_set_block_dirty(struct jbd_trans *trans,
1230                               struct ext4_block *block)
1231 {
1232         struct jbd_buf *buf;
1233
1234         if (!ext4_bcache_test_flag(block->buf, BC_DIRTY) &&
1235             block->buf->end_write != jbd_trans_end_write) {
1236                 struct jbd_block_rec *block_rec;
1237                 buf = calloc(1, sizeof(struct jbd_buf));
1238                 if (!buf)
1239                         return ENOMEM;
1240
1241                 if ((block_rec = jbd_trans_insert_block_rec(trans,
1242                                         block->lb_id,
1243                                         block->buf)) == NULL) {
1244                         free(buf);
1245                         return ENOMEM;
1246                 }
1247
1248                 buf->block_rec = block_rec;
1249                 buf->trans = trans;
1250                 buf->block = *block;
1251                 ext4_bcache_inc_ref(block->buf);
1252
1253                 /* If the content reach the disk, notify us
1254                  * so that we may do a checkpoint. */
1255                 block->buf->end_write = jbd_trans_end_write;
1256                 block->buf->end_write_arg = buf;
1257
1258                 trans->data_cnt++;
1259                 TAILQ_INSERT_HEAD(&trans->buf_queue, buf, buf_node);
1260
1261                 ext4_bcache_set_dirty(block->buf);
1262         }
1263         return EOK;
1264 }
1265
1266 /**@brief  Add block to be revoked to a transaction
1267  * @param  trans transaction
1268  * @param  lba logical block address
1269  * @return standard error code*/
1270 int jbd_trans_revoke_block(struct jbd_trans *trans,
1271                            ext4_fsblk_t lba)
1272 {
1273         struct jbd_revoke_rec *rec =
1274                 calloc(1, sizeof(struct jbd_revoke_rec));
1275         if (!rec)
1276                 return ENOMEM;
1277
1278         rec->lba = lba;
1279         LIST_INSERT_HEAD(&trans->revoke_list, rec, revoke_node);
1280         return EOK;
1281 }
1282
1283 /**@brief  Try to add block to be revoked to a transaction.
1284  *         If @lba still remains in an transaction on checkpoint
1285  *         queue, add @lba as a revoked block to the transaction.
1286  * @param  trans transaction
1287  * @param  lba logical block address
1288  * @return standard error code*/
1289 int jbd_trans_try_revoke_block(struct jbd_trans *trans,
1290                                ext4_fsblk_t lba)
1291 {
1292         int r = EOK;
1293         struct jbd_journal *journal = trans->journal;
1294         struct ext4_fs *fs = journal->jbd_fs->inode_ref.fs;
1295         struct jbd_block_rec *block_rec =
1296                 jbd_trans_block_rec_lookup(journal, lba);
1297
1298         /* Make sure we don't flush any buffers belong to this transaction. */
1299         if (block_rec && block_rec->trans != trans) {
1300                 /* If the buffer has not been flushed yet, flush it now. */
1301                 if (block_rec->buf) {
1302                         r = ext4_block_flush_buf(fs->bdev, block_rec->buf);
1303                         if (r != EOK)
1304                                 return r;
1305
1306                 }
1307
1308                 jbd_trans_revoke_block(trans, lba);
1309         }
1310
1311         return EOK;
1312 }
1313
1314 /**@brief  Free a transaction
1315  * @param  journal current journal session
1316  * @param  trans transaction
1317  * @param  abort discard all the modifications on the block?
1318  * @return standard error code*/
1319 void jbd_journal_free_trans(struct jbd_journal *journal,
1320                             struct jbd_trans *trans,
1321                             bool abort)
1322 {
1323         struct jbd_buf *jbd_buf, *tmp;
1324         struct jbd_revoke_rec *rec, *tmp2;
1325         struct jbd_block_rec *block_rec, *tmp3;
1326         struct ext4_fs *fs = journal->jbd_fs->inode_ref.fs;
1327         TAILQ_FOREACH_SAFE(jbd_buf, &trans->buf_queue, buf_node,
1328                           tmp) {
1329                 if (abort) {
1330                         jbd_buf->block.buf->end_write = NULL;
1331                         jbd_buf->block.buf->end_write_arg = NULL;
1332                         ext4_bcache_clear_dirty(jbd_buf->block.buf);
1333                         ext4_block_set(fs->bdev, &jbd_buf->block);
1334                 }
1335
1336                 TAILQ_REMOVE(&trans->buf_queue, jbd_buf, buf_node);
1337                 free(jbd_buf);
1338         }
1339         LIST_FOREACH_SAFE(rec, &trans->revoke_list, revoke_node,
1340                           tmp2) {
1341                 LIST_REMOVE(rec, revoke_node);
1342                 free(rec);
1343         }
1344         LIST_FOREACH_SAFE(block_rec, &trans->tbrec_list, tbrec_node,
1345                           tmp3) {
1346                 jbd_trans_remove_block_rec(journal, block_rec, trans);
1347         }
1348
1349         free(trans);
1350 }
1351
1352 /**@brief  Write commit block for a transaction
1353  * @param  trans transaction
1354  * @return standard error code*/
1355 static int jbd_trans_write_commit_block(struct jbd_trans *trans)
1356 {
1357         int rc;
1358         struct jbd_commit_header *header;
1359         uint32_t commit_iblock = 0;
1360         struct ext4_block commit_block;
1361         struct jbd_journal *journal = trans->journal;
1362
1363         commit_iblock = jbd_journal_alloc_block(journal, trans);
1364         rc = jbd_block_get_noread(journal->jbd_fs,
1365                         &commit_block, commit_iblock);
1366         if (rc != EOK)
1367                 return rc;
1368
1369         header = (struct jbd_commit_header *)commit_block.data;
1370         jbd_set32(&header->header, magic, JBD_MAGIC_NUMBER);
1371         jbd_set32(&header->header, blocktype, JBD_COMMIT_BLOCK);
1372         jbd_set32(&header->header, sequence, trans->trans_id);
1373
1374         ext4_bcache_set_dirty(commit_block.buf);
1375         rc = jbd_block_set(journal->jbd_fs, &commit_block);
1376         if (rc != EOK)
1377                 return rc;
1378
1379         return EOK;
1380 }
1381
1382 /**@brief  Write descriptor block for a transaction
1383  * @param  journal current journal session
1384  * @param  trans transaction
1385  * @return standard error code*/
1386 static int jbd_journal_prepare(struct jbd_journal *journal,
1387                                struct jbd_trans *trans)
1388 {
1389         int rc = EOK, i = 0;
1390         int32_t tag_tbl_size;
1391         uint32_t desc_iblock = 0;
1392         uint32_t data_iblock = 0;
1393         char *tag_start = NULL, *tag_ptr = NULL;
1394         struct jbd_buf *jbd_buf, *tmp;
1395         struct ext4_block desc_block, data_block;
1396         struct ext4_fs *fs = journal->jbd_fs->inode_ref.fs;
1397
1398         /* Try to remove any non-dirty buffers from the tail of
1399          * buf_queue. */
1400         TAILQ_FOREACH_REVERSE_SAFE(jbd_buf, &trans->buf_queue,
1401                         jbd_trans_buf, buf_node, tmp) {
1402                 /* We stop the iteration when we find a dirty buffer. */
1403                 if (ext4_bcache_test_flag(jbd_buf->block.buf,
1404                                         BC_DIRTY))
1405                         break;
1406
1407                 /* The buffer has not been modified, just release
1408                  * that jbd_buf. */
1409                 jbd_trans_remove_block_rec(journal,
1410                                 jbd_buf->block_rec, trans);
1411                 trans->data_cnt--;
1412
1413                 jbd_buf->block.buf->end_write = NULL;
1414                 jbd_buf->block.buf->end_write_arg = NULL;
1415                 ext4_block_set(fs->bdev, &jbd_buf->block);
1416                 TAILQ_REMOVE(&trans->buf_queue, jbd_buf, buf_node);
1417                 free(jbd_buf);
1418         }
1419
1420         TAILQ_FOREACH_SAFE(jbd_buf, &trans->buf_queue, buf_node, tmp) {
1421                 struct tag_info tag_info;
1422                 bool uuid_exist = false;
1423                 if (!ext4_bcache_test_flag(jbd_buf->block.buf,
1424                                            BC_DIRTY)) {
1425                         /* The buffer has not been modified, just release
1426                          * that jbd_buf. */
1427                         jbd_trans_remove_block_rec(journal,
1428                                         jbd_buf->block_rec, trans);
1429                         trans->data_cnt--;
1430
1431                         jbd_buf->block.buf->end_write = NULL;
1432                         jbd_buf->block.buf->end_write_arg = NULL;
1433                         ext4_block_set(fs->bdev, &jbd_buf->block);
1434                         TAILQ_REMOVE(&trans->buf_queue, jbd_buf, buf_node);
1435                         free(jbd_buf);
1436                         continue;
1437                 }
1438 again:
1439                 if (!desc_iblock) {
1440                         struct jbd_bhdr *bhdr;
1441                         desc_iblock = jbd_journal_alloc_block(journal, trans);
1442                         rc = jbd_block_get_noread(journal->jbd_fs,
1443                                            &desc_block, desc_iblock);
1444                         if (rc != EOK)
1445                                 break;
1446
1447                         ext4_bcache_set_dirty(desc_block.buf);
1448
1449                         bhdr = (struct jbd_bhdr *)desc_block.data;
1450                         jbd_set32(bhdr, magic, JBD_MAGIC_NUMBER);
1451                         jbd_set32(bhdr, blocktype, JBD_DESCRIPTOR_BLOCK);
1452                         jbd_set32(bhdr, sequence, trans->trans_id);
1453
1454                         tag_start = (char *)(bhdr + 1);
1455                         tag_ptr = tag_start;
1456                         uuid_exist = true;
1457                         tag_tbl_size = journal->block_size -
1458                                 sizeof(struct jbd_bhdr);
1459
1460                         if (!trans->start_iblock)
1461                                 trans->start_iblock = desc_iblock;
1462
1463                 }
1464                 tag_info.block = jbd_buf->block.lb_id;
1465                 tag_info.uuid_exist = uuid_exist;
1466                 if (i == trans->data_cnt - 1)
1467                         tag_info.last_tag = true;
1468                 else
1469                         tag_info.last_tag = false;
1470
1471                 if (uuid_exist)
1472                         memcpy(tag_info.uuid, journal->jbd_fs->sb.uuid,
1473                                         UUID_SIZE);
1474
1475                 rc = jbd_write_block_tag(journal->jbd_fs,
1476                                 tag_ptr,
1477                                 tag_tbl_size,
1478                                 &tag_info);
1479                 if (rc != EOK) {
1480                         jbd_block_set(journal->jbd_fs, &desc_block);
1481                         desc_iblock = 0;
1482                         goto again;
1483                 }
1484
1485                 data_iblock = jbd_journal_alloc_block(journal, trans);
1486                 rc = jbd_block_get_noread(journal->jbd_fs,
1487                                 &data_block, data_iblock);
1488                 if (rc != EOK)
1489                         break;
1490
1491                 ext4_bcache_set_dirty(data_block.buf);
1492
1493                 memcpy(data_block.data, jbd_buf->block.data,
1494                         journal->block_size);
1495
1496                 rc = jbd_block_set(journal->jbd_fs, &data_block);
1497                 if (rc != EOK)
1498                         break;
1499
1500                 tag_ptr += tag_info.tag_bytes;
1501                 tag_tbl_size -= tag_info.tag_bytes;
1502
1503                 i++;
1504         }
1505         if (rc == EOK && desc_iblock)
1506                 jbd_block_set(journal->jbd_fs, &desc_block);
1507
1508         return rc;
1509 }
1510
1511 /**@brief  Write revoke block for a transaction
1512  * @param  journal current journal session
1513  * @param  trans transaction
1514  * @return standard error code*/
1515 static int
1516 jbd_journal_prepare_revoke(struct jbd_journal *journal,
1517                            struct jbd_trans *trans)
1518 {
1519         int rc = EOK, i = 0;
1520         int32_t tag_tbl_size;
1521         uint32_t desc_iblock = 0;
1522         char *blocks_entry = NULL;
1523         struct jbd_revoke_rec *rec, *tmp;
1524         struct ext4_block desc_block;
1525         struct jbd_revoke_header *header = NULL;
1526         int32_t record_len = 4;
1527
1528         if (JBD_HAS_INCOMPAT_FEATURE(&journal->jbd_fs->sb,
1529                                      JBD_FEATURE_INCOMPAT_64BIT))
1530                 record_len = 8;
1531
1532         LIST_FOREACH_SAFE(rec, &trans->revoke_list, revoke_node,
1533                           tmp) {
1534 again:
1535                 if (!desc_iblock) {
1536                         struct jbd_bhdr *bhdr;
1537                         desc_iblock = jbd_journal_alloc_block(journal, trans);
1538                         rc = jbd_block_get_noread(journal->jbd_fs,
1539                                            &desc_block, desc_iblock);
1540                         if (rc != EOK) {
1541                                 break;
1542                         }
1543
1544                         ext4_bcache_set_dirty(desc_block.buf);
1545
1546                         bhdr = (struct jbd_bhdr *)desc_block.data;
1547                         jbd_set32(bhdr, magic, JBD_MAGIC_NUMBER);
1548                         jbd_set32(bhdr, blocktype, JBD_REVOKE_BLOCK);
1549                         jbd_set32(bhdr, sequence, trans->trans_id);
1550
1551                         header = (struct jbd_revoke_header *)bhdr;
1552                         blocks_entry = (char *)(header + 1);
1553                         tag_tbl_size = journal->block_size -
1554                                 sizeof(struct jbd_revoke_header);
1555
1556                         if (!trans->start_iblock)
1557                                 trans->start_iblock = desc_iblock;
1558
1559                 }
1560
1561                 if (tag_tbl_size < record_len) {
1562                         jbd_set32(header, count,
1563                                   journal->block_size - tag_tbl_size);
1564                         jbd_block_set(journal->jbd_fs, &desc_block);
1565                         desc_iblock = 0;
1566                         header = NULL;
1567                         goto again;
1568                 }
1569                 if (record_len == 8) {
1570                         uint64_t *blocks =
1571                                 (uint64_t *)blocks_entry;
1572                         *blocks = to_be64(rec->lba);
1573                 } else {
1574                         uint32_t *blocks =
1575                                 (uint32_t *)blocks_entry;
1576                         *blocks = to_be32(rec->lba);
1577                 }
1578                 blocks_entry += record_len;
1579                 tag_tbl_size -= record_len;
1580
1581                 i++;
1582         }
1583         if (rc == EOK && desc_iblock) {
1584                 if (header != NULL)
1585                         jbd_set32(header, count,
1586                                   journal->block_size - tag_tbl_size);
1587
1588                 jbd_block_set(journal->jbd_fs, &desc_block);
1589         }
1590
1591         return rc;
1592 }
1593
1594 /**@brief  Submit the transaction to transaction queue.
1595  * @param  journal current journal session
1596  * @param  trans transaction*/
1597 void
1598 jbd_journal_submit_trans(struct jbd_journal *journal,
1599                          struct jbd_trans *trans)
1600 {
1601         TAILQ_INSERT_TAIL(&journal->trans_queue,
1602                           trans,
1603                           trans_node);
1604 }
1605
1606 /**@brief  Put references of block descriptors in a transaction.
1607  * @param  journal current journal session
1608  * @param  trans transaction*/
1609 void jbd_journal_cp_trans(struct jbd_journal *journal, struct jbd_trans *trans)
1610 {
1611         struct jbd_buf *jbd_buf, *tmp;
1612         struct ext4_fs *fs = journal->jbd_fs->inode_ref.fs;
1613         TAILQ_FOREACH_SAFE(jbd_buf, &trans->buf_queue, buf_node,
1614                         tmp) {
1615                 struct ext4_block block = jbd_buf->block;
1616                 ext4_block_set(fs->bdev, &block);
1617         }
1618 }
1619
1620 /**@brief  Update the start block of the journal when
1621  *         all the contents in a transaction reach the disk.*/
1622 static void jbd_trans_end_write(struct ext4_bcache *bc __unused,
1623                           struct ext4_buf *buf,
1624                           int res,
1625                           void *arg)
1626 {
1627         struct jbd_buf *jbd_buf = arg;
1628         struct jbd_trans *trans = jbd_buf->trans;
1629         struct jbd_journal *journal = trans->journal;
1630         bool first_in_queue =
1631                 trans == TAILQ_FIRST(&journal->cp_queue);
1632         if (res != EOK)
1633                 trans->error = res;
1634
1635         TAILQ_REMOVE(&trans->buf_queue, jbd_buf, buf_node);
1636         jbd_buf->block_rec->buf = NULL;
1637         free(jbd_buf);
1638
1639         /* Clear the end_write and end_write_arg fields. */
1640         buf->end_write = NULL;
1641         buf->end_write_arg = NULL;
1642
1643         trans->written_cnt++;
1644         if (trans->written_cnt == trans->data_cnt) {
1645                 /* If it is the first transaction on checkpoint queue,
1646                  * we will shift the start of the journal to the next
1647                  * transaction, and remove subsequent written
1648                  * transactions from checkpoint queue until we find
1649                  * an unwritten one. */
1650                 if (first_in_queue) {
1651                         journal->start = trans->start_iblock +
1652                                 trans->alloc_blocks;
1653                         wrap(&journal->jbd_fs->sb, journal->start);
1654                         journal->trans_id = trans->trans_id + 1;
1655                         TAILQ_REMOVE(&journal->cp_queue, trans, trans_node);
1656                         jbd_journal_free_trans(journal, trans, false);
1657
1658                         jbd_journal_purge_cp_trans(journal, false);
1659                         jbd_journal_write_sb(journal);
1660                         jbd_write_sb(journal->jbd_fs);
1661                 }
1662         }
1663 }
1664
1665 /**@brief  Commit a transaction to the journal immediately.
1666  * @param  journal current journal session
1667  * @param  trans transaction
1668  * @return standard error code*/
1669 int jbd_journal_commit_trans(struct jbd_journal *journal,
1670                              struct jbd_trans *trans)
1671 {
1672         int rc = EOK;
1673         uint32_t last = journal->last;
1674
1675         trans->trans_id = journal->alloc_trans_id;
1676         rc = jbd_journal_prepare(journal, trans);
1677         if (rc != EOK)
1678                 goto Finish;
1679
1680         rc = jbd_journal_prepare_revoke(journal, trans);
1681         if (rc != EOK)
1682                 goto Finish;
1683
1684         if (TAILQ_EMPTY(&trans->buf_queue) &&
1685             LIST_EMPTY(&trans->revoke_list)) {
1686                 /* Since there are no entries in both buffer list
1687                  * and revoke entry list, we do not consider trans as
1688                  * complete transaction and just return EOK.*/
1689                 jbd_journal_free_trans(journal, trans, false);
1690                 goto Finish;
1691         }
1692
1693         rc = jbd_trans_write_commit_block(trans);
1694         if (rc != EOK)
1695                 goto Finish;
1696
1697         journal->alloc_trans_id++;
1698         if (TAILQ_EMPTY(&journal->cp_queue)) {
1699                 if (trans->data_cnt) {
1700                         journal->start = trans->start_iblock;
1701                         wrap(&journal->jbd_fs->sb, journal->start);
1702                         journal->trans_id = trans->trans_id;
1703                         jbd_journal_write_sb(journal);
1704                         jbd_write_sb(journal->jbd_fs);
1705                         TAILQ_INSERT_TAIL(&journal->cp_queue, trans,
1706                                         trans_node);
1707                         jbd_journal_cp_trans(journal, trans);
1708                 } else {
1709                         journal->start = trans->start_iblock +
1710                                 trans->alloc_blocks;
1711                         wrap(&journal->jbd_fs->sb, journal->start);
1712                         journal->trans_id = trans->trans_id + 1;
1713                         jbd_journal_write_sb(journal);
1714                         jbd_journal_free_trans(journal, trans, false);
1715                 }
1716         } else {
1717                 TAILQ_INSERT_TAIL(&journal->cp_queue, trans,
1718                                 trans_node);
1719                 if (trans->data_cnt)
1720                         jbd_journal_cp_trans(journal, trans);
1721
1722         }
1723 Finish:
1724         if (rc != EOK) {
1725                 journal->last = last;
1726                 jbd_journal_free_trans(journal, trans, true);
1727         }
1728         return rc;
1729 }
1730
1731 /**@brief  Commit one transaction on transaction queue
1732  *         to the journal.
1733  * @param  journal current journal session.*/
1734 void jbd_journal_commit_one(struct jbd_journal *journal)
1735 {
1736         struct jbd_trans *trans;
1737
1738         if ((trans = TAILQ_FIRST(&journal->trans_queue))) {
1739                 TAILQ_REMOVE(&journal->trans_queue, trans, trans_node);
1740                 jbd_journal_commit_trans(journal, trans);
1741         }
1742 }
1743
1744 /**@brief  Commit all the transactions on transaction queue
1745  *         to the journal.
1746  * @param  journal current journal session.*/
1747 void jbd_journal_commit_all(struct jbd_journal *journal)
1748 {
1749         while (!TAILQ_EMPTY(&journal->trans_queue)) {
1750                 jbd_journal_commit_one(journal);
1751         }
1752 }
1753
1754 /**
1755  * @}
1756  */