src/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_misc.h"
  41 #include "ext4_errno.h"
  42 #include "ext4_debug.h"
  43
  44 #include "ext4_fs.h"
  45 #include "ext4_super.h"
  46 #include "ext4_journal.h"
  47 #include "ext4_blockdev.h"
  48 #include "ext4_crc32.h"
  49 #include "ext4_journal.h"
  50
  51 #include <string.h>
  52 #include <stdlib.h>
  53
  54 /**@brief  Revoke entry during journal replay.*/
  55 struct revoke_entry {
  56         /**@brief  Block number not to be replayed.*/
  57         ext4_fsblk_t block;
  58
  59         /**@brief  For any transaction id smaller
  60          *         than trans_id, records of @block
  61          *         in those transactions should not
  62          *         be replayed.*/
  63         uint32_t trans_id;
  64
  65         /**@brief  Revoke tree node.*/
  66         RB_ENTRY(revoke_entry) revoke_node;
  67 };
  68
  69 /**@brief  Valid journal replay information.*/
  70 struct recover_info {
  71         /**@brief  Starting transaction id.*/
  72         uint32_t start_trans_id;
  73
  74         /**@brief  Ending transaction id.*/
  75         uint32_t last_trans_id;
  76
  77         /**@brief  Used as internal argument.*/
  78         uint32_t this_trans_id;
  79
  80         /**@brief  No of transactions went through.*/
  81         uint32_t trans_cnt;
  82
  83         /**@brief  RB-Tree storing revoke entries.*/
  84         RB_HEAD(jbd_revoke, revoke_entry) revoke_root;
  85 };
  86
  87 /**@brief  Journal replay internal arguments.*/
  88 struct replay_arg {
  89         /**@brief  Journal replay information.*/
  90         struct recover_info *info;
  91
  92         /**@brief  Current block we are on.*/
  93         uint32_t *this_block;
  94
  95         /**@brief  Current trans_id we are on.*/
  96         uint32_t this_trans_id;
  97 };
  98
  99 /* Make sure we wrap around the log correctly! */
 100 #define wrap(sb, var)                                           \
 101 do {                                                                    \
 102         if (var >= jbd_get32((sb), maxlen))                                     \
 103                 var -= (jbd_get32((sb), maxlen) - jbd_get32((sb), first));      \
 104 } while (0)
 105
 106 static inline int32_t
 107 trans_id_diff(uint32_t x, uint32_t y)
 108 {
 109         int32_t diff = x - y;
 110         return diff;
 111 }
 112
 113 static int
 114 jbd_revoke_entry_cmp(struct revoke_entry *a, struct revoke_entry *b)
 115 {
 116         if (a->block > b->block)
 117                 return 1;
 118         else if (a->block < b->block)
 119                 return -1;
 120         return 0;
 121 }
 122
 123 static int
 124 jbd_block_rec_cmp(struct jbd_block_rec *a, struct jbd_block_rec *b)
 125 {
 126         if (a->lba > b->lba)
 127                 return 1;
 128         else if (a->lba < b->lba)
 129                 return -1;
 130         return 0;
 131 }
 132
 133 static int
 134 jbd_revoke_rec_cmp(struct jbd_revoke_rec *a, struct jbd_revoke_rec *b)
 135 {
 136         if (a->lba > b->lba)
 137                 return 1;
 138         else if (a->lba < b->lba)
 139                 return -1;
 140         return 0;
 141 }
 142
 143 RB_GENERATE_INTERNAL(jbd_revoke, revoke_entry, revoke_node,
 144                      jbd_revoke_entry_cmp, static inline)
 145 RB_GENERATE_INTERNAL(jbd_block, jbd_block_rec, block_rec_node,
 146                      jbd_block_rec_cmp, static inline)
 147 RB_GENERATE_INTERNAL(jbd_revoke_tree, jbd_revoke_rec, revoke_node,
 148                      jbd_revoke_rec_cmp, static inline)
 149
 150 #define jbd_alloc_revoke_entry() calloc(1, sizeof(struct revoke_entry))
 151 #define jbd_free_revoke_entry(addr) free(addr)
 152
 153 static int jbd_has_csum(struct jbd_sb *jbd_sb)
 154 {
 155         if (JBD_HAS_INCOMPAT_FEATURE(jbd_sb, JBD_FEATURE_INCOMPAT_CSUM_V2))
 156                 return 2;
 157
 158         if (JBD_HAS_INCOMPAT_FEATURE(jbd_sb, JBD_FEATURE_INCOMPAT_CSUM_V3))
 159                 return 3;
 160
 161         return 0;
 162 }
 163
 164 #if CONFIG_META_CSUM_ENABLE
 165 static uint32_t jbd_sb_csum(struct jbd_sb *jbd_sb)
 166 {
 167         uint32_t checksum = 0;
 168
 169         if (jbd_has_csum(jbd_sb)) {
 170                 uint32_t orig_checksum = jbd_sb->checksum;
 171                 jbd_set32(jbd_sb, checksum, 0);
 172                 /* Calculate crc32c checksum against tho whole superblock */
 173                 checksum = ext4_crc32c(EXT4_CRC32_INIT, jbd_sb,
 174                                 JBD_SUPERBLOCK_SIZE);
 175                 jbd_sb->checksum = orig_checksum;
 176         }
 177         return checksum;
 178 }
 179 #else
 180 #define jbd_sb_csum(...) 0
 181 #endif
 182
 183 static void jbd_sb_csum_set(struct jbd_sb *jbd_sb)
 184 {
 185         if (!jbd_has_csum(jbd_sb))
 186                 return;
 187
 188         jbd_set32(jbd_sb, checksum, jbd_sb_csum(jbd_sb));
 189 }
 190
 191 #if CONFIG_META_CSUM_ENABLE
 192 static bool
 193 jbd_verify_sb_csum(struct jbd_sb *jbd_sb)
 194 {
 195         if (!jbd_has_csum(jbd_sb))
 196                 return true;
 197
 198         return jbd_sb_csum(jbd_sb) == jbd_get32(jbd_sb, checksum);
 199 }
 200 #else
 201 #define jbd_verify_sb_csum(...) true
 202 #endif
 203
 204 #if CONFIG_META_CSUM_ENABLE
 205 static uint32_t jbd_meta_csum(struct jbd_fs *jbd_fs,
 206                               struct jbd_bhdr *bhdr)
 207 {
 208         uint32_t checksum = 0;
 209
 210         if (jbd_has_csum(&jbd_fs->sb)) {
 211                 uint32_t block_size = jbd_get32(&jbd_fs->sb, blocksize);
 212                 struct jbd_block_tail *tail =
 213                         (struct jbd_block_tail *)((char *)bhdr + block_size -
 214                                 sizeof(struct jbd_block_tail));
 215                 uint32_t orig_checksum = tail->checksum;
 216                 tail->checksum = 0;
 217
 218                 /* First calculate crc32c checksum against fs uuid */
 219                 checksum = ext4_crc32c(EXT4_CRC32_INIT, jbd_fs->sb.uuid,
 220                                        sizeof(jbd_fs->sb.uuid));
 221                 /* Calculate crc32c checksum against tho whole block */
 222                 checksum = ext4_crc32c(checksum, bhdr,
 223                                 block_size);
 224                 tail->checksum = orig_checksum;
 225         }
 226         return checksum;
 227 }
 228 #else
 229 #define jbd_meta_csum(...) 0
 230 #endif
 231
 232 static void jbd_meta_csum_set(struct jbd_fs *jbd_fs,
 233                               struct jbd_bhdr *bhdr)
 234 {
 235         uint32_t block_size = jbd_get32(&jbd_fs->sb, blocksize);
 236         struct jbd_block_tail *tail = (struct jbd_block_tail *)
 237                                 ((char *)bhdr + block_size -
 238                                 sizeof(struct jbd_block_tail));
 239         if (!jbd_has_csum(&jbd_fs->sb))
 240                 return;
 241
 242         tail->checksum = to_be32(jbd_meta_csum(jbd_fs, bhdr));
 243 }
 244
 245 #if CONFIG_META_CSUM_ENABLE
 246 static bool
 247 jbd_verify_meta_csum(struct jbd_fs *jbd_fs,
 248                      struct jbd_bhdr *bhdr)
 249 {
 250         uint32_t block_size = jbd_get32(&jbd_fs->sb, blocksize);
 251         struct jbd_block_tail *tail = (struct jbd_block_tail *)
 252                                 ((char *)bhdr + block_size -
 253                                 sizeof(struct jbd_block_tail));
 254         if (!jbd_has_csum(&jbd_fs->sb))
 255                 return true;
 256
 257         return jbd_meta_csum(jbd_fs, bhdr) == to_be32(tail->checksum);
 258 }
 259 #else
 260 #define jbd_verify_meta_csum(...) true
 261 #endif
 262
 263 #if CONFIG_META_CSUM_ENABLE
 264 static uint32_t jbd_commit_csum(struct jbd_fs *jbd_fs,
 265                               struct jbd_commit_header *header)
 266 {
 267         uint32_t checksum = 0;
 268
 269         if (jbd_has_csum(&jbd_fs->sb)) {
 270                 uint32_t orig_checksum_type = header->chksum_type,
 271                          orig_checksum_size = header->chksum_size,
 272                          orig_checksum = header->chksum[0];
 273                 uint32_t block_size = jbd_get32(&jbd_fs->sb, blocksize);
 274                 header->chksum_type = 0;
 275                 header->chksum_size = 0;
 276                 header->chksum[0] = 0;
 277
 278                 /* First calculate crc32c checksum against fs uuid */
 279                 checksum = ext4_crc32c(EXT4_CRC32_INIT, jbd_fs->sb.uuid,
 280                                        sizeof(jbd_fs->sb.uuid));
 281                 /* Calculate crc32c checksum against tho whole block */
 282                 checksum = ext4_crc32c(checksum, header,
 283                                 block_size);
 284
 285                 header->chksum_type = orig_checksum_type;
 286                 header->chksum_size = orig_checksum_size;
 287                 header->chksum[0] = orig_checksum;
 288         }
 289         return checksum;
 290 }
 291 #else
 292 #define jbd_commit_csum(...) 0
 293 #endif
 294
 295 static void jbd_commit_csum_set(struct jbd_fs *jbd_fs,
 296                               struct jbd_commit_header *header)
 297 {
 298         if (!jbd_has_csum(&jbd_fs->sb))
 299                 return;
 300
 301         header->chksum_type = 0;
 302         header->chksum_size = 0;
 303         header->chksum[0] = jbd_commit_csum(jbd_fs, header);
 304 }
 305
 306 #if CONFIG_META_CSUM_ENABLE
 307 static bool jbd_verify_commit_csum(struct jbd_fs *jbd_fs,
 308                                    struct jbd_commit_header *header)
 309 {
 310         if (!jbd_has_csum(&jbd_fs->sb))
 311                 return true;
 312
 313         return header->chksum[0] == to_be32(jbd_commit_csum(jbd_fs,
 314                                             header));
 315 }
 316 #else
 317 #define jbd_verify_commit_csum(...) true
 318 #endif
 319
 320 #if CONFIG_META_CSUM_ENABLE
 321 /*
 322  * NOTE: We only make use of @csum parameter when
 323  *       JBD_FEATURE_COMPAT_CHECKSUM is enabled.
 324  */
 325 static uint32_t jbd_block_csum(struct jbd_fs *jbd_fs, const void *buf,
 326                                uint32_t csum,
 327                                uint32_t sequence)
 328 {
 329         uint32_t checksum = 0;
 330
 331         if (jbd_has_csum(&jbd_fs->sb)) {
 332                 uint32_t block_size = jbd_get32(&jbd_fs->sb, blocksize);
 333                 /* First calculate crc32c checksum against fs uuid */
 334                 checksum = ext4_crc32c(EXT4_CRC32_INIT, jbd_fs->sb.uuid,
 335                                        sizeof(jbd_fs->sb.uuid));
 336                 /* Then calculate crc32c checksum against sequence no. */
 337                 checksum = ext4_crc32c(checksum, &sequence,
 338                                 sizeof(uint32_t));
 339                 /* Calculate crc32c checksum against tho whole block */
 340                 checksum = ext4_crc32c(checksum, buf,
 341                                 block_size);
 342         } else if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 343                                      JBD_FEATURE_COMPAT_CHECKSUM)) {
 344                 uint32_t block_size = jbd_get32(&jbd_fs->sb, blocksize);
 345                 /* Calculate crc32c checksum against tho whole block */
 346                 checksum = ext4_crc32(csum, buf,
 347                                 block_size);
 348         }
 349         return checksum;
 350 }
 351 #else
 352 #define jbd_block_csum(...) 0
 353 #endif
 354
 355 static void jbd_block_tag_csum_set(struct jbd_fs *jbd_fs, void *__tag,
 356                                    uint32_t checksum)
 357 {
 358         int ver = jbd_has_csum(&jbd_fs->sb);
 359         if (!ver)
 360                 return;
 361
 362         if (ver == 2) {
 363                 struct jbd_block_tag *tag = __tag;
 364                 tag->checksum = (uint16_t)to_be32(checksum);
 365         } else {
 366                 struct jbd_block_tag3 *tag = __tag;
 367                 tag->checksum = to_be32(checksum);
 368         }
 369 }
 370
 371 /**@brief  Write jbd superblock to disk.
 372  * @param  jbd_fs jbd filesystem
 373  * @param  s jbd superblock
 374  * @return standard error code*/
 375 static int jbd_sb_write(struct jbd_fs *jbd_fs, struct jbd_sb *s)
 376 {
 377         int rc;
 378         struct ext4_fs *fs = jbd_fs->inode_ref.fs;
 379         uint64_t offset;
 380         ext4_fsblk_t fblock;
 381         rc = jbd_inode_bmap(jbd_fs, 0, &fblock);
 382         if (rc != EOK)
 383                 return rc;
 384
 385         jbd_sb_csum_set(s);
 386         offset = fblock * ext4_sb_get_block_size(&fs->sb);
 387         return ext4_block_writebytes(fs->bdev, offset, s,
 388                                      EXT4_SUPERBLOCK_SIZE);
 389 }
 390
 391 /**@brief  Read jbd superblock from disk.
 392  * @param  jbd_fs jbd filesystem
 393  * @param  s jbd superblock
 394  * @return standard error code*/
 395 static int jbd_sb_read(struct jbd_fs *jbd_fs, struct jbd_sb *s)
 396 {
 397         int rc;
 398         struct ext4_fs *fs = jbd_fs->inode_ref.fs;
 399         uint64_t offset;
 400         ext4_fsblk_t fblock;
 401         rc = jbd_inode_bmap(jbd_fs, 0, &fblock);
 402         if (rc != EOK)
 403                 return rc;
 404
 405         offset = fblock * ext4_sb_get_block_size(&fs->sb);
 406         return ext4_block_readbytes(fs->bdev, offset, s,
 407                                     EXT4_SUPERBLOCK_SIZE);
 408 }
 409
 410 /**@brief  Verify jbd superblock.
 411  * @param  sb jbd superblock
 412  * @return true if jbd superblock is valid */
 413 static bool jbd_verify_sb(struct jbd_sb *sb)
 414 {
 415         struct jbd_bhdr *header = &sb->header;
 416         if (jbd_get32(header, magic) != JBD_MAGIC_NUMBER)
 417                 return false;
 418
 419         if (jbd_get32(header, blocktype) != JBD_SUPERBLOCK &&
 420             jbd_get32(header, blocktype) != JBD_SUPERBLOCK_V2)
 421                 return false;
 422
 423         return jbd_verify_sb_csum(sb);
 424 }
 425
 426 /**@brief  Write back dirty jbd superblock to disk.
 427  * @param  jbd_fs jbd filesystem
 428  * @return standard error code*/
 429 static int jbd_write_sb(struct jbd_fs *jbd_fs)
 430 {
 431         int rc = EOK;
 432         if (jbd_fs->dirty) {
 433                 rc = jbd_sb_write(jbd_fs, &jbd_fs->sb);
 434                 if (rc != EOK)
 435                         return rc;
 436
 437                 jbd_fs->dirty = false;
 438         }
 439         return rc;
 440 }
 441
 442 /**@brief  Get reference to jbd filesystem.
 443  * @param  fs Filesystem to load journal of
 444  * @param  jbd_fs jbd filesystem
 445  * @return standard error code*/
 446 int jbd_get_fs(struct ext4_fs *fs,
 447                struct jbd_fs *jbd_fs)
 448 {
 449         int rc;
 450         uint32_t journal_ino;
 451
 452         memset(jbd_fs, 0, sizeof(struct jbd_fs));
 453         /* See if there is journal inode on this filesystem.*/
 454         /* FIXME: detection on existance ofbkejournal bdev is
 455          *        missing.*/
 456         journal_ino = ext4_get32(&fs->sb, journal_inode_number);
 457
 458         rc = ext4_fs_get_inode_ref(fs,
 459                                    journal_ino,
 460                                    &jbd_fs->inode_ref);
 461         if (rc != EOK) {
 462                 memset(jbd_fs, 0, sizeof(struct jbd_fs));
 463                 return rc;
 464         }
 465         rc = jbd_sb_read(jbd_fs, &jbd_fs->sb);
 466         if (rc != EOK) {
 467                 memset(jbd_fs, 0, sizeof(struct jbd_fs));
 468                 ext4_fs_put_inode_ref(&jbd_fs->inode_ref);
 469                 return rc;
 470         }
 471         if (!jbd_verify_sb(&jbd_fs->sb)) {
 472                 memset(jbd_fs, 0, sizeof(struct jbd_fs));
 473                 ext4_fs_put_inode_ref(&jbd_fs->inode_ref);
 474                 rc = EIO;
 475         }
 476
 477         if (rc == EOK)
 478                 jbd_fs->bdev = fs->bdev;
 479
 480         return rc;
 481 }
 482
 483 /**@brief  Put reference of jbd filesystem.
 484  * @param  jbd_fs jbd filesystem
 485  * @return standard error code*/
 486 int jbd_put_fs(struct jbd_fs *jbd_fs)
 487 {
 488         int rc = EOK;
 489         rc = jbd_write_sb(jbd_fs);
 490
 491         ext4_fs_put_inode_ref(&jbd_fs->inode_ref);
 492         return rc;
 493 }
 494
 495 /**@brief  Data block lookup helper.
 496  * @param  jbd_fs jbd filesystem
 497  * @param  iblock block index
 498  * @param  fblock logical block address
 499  * @return standard error code*/
 500 int jbd_inode_bmap(struct jbd_fs *jbd_fs,
 501                    ext4_lblk_t iblock,
 502                    ext4_fsblk_t *fblock)
 503 {
 504         int rc = ext4_fs_get_inode_dblk_idx(
 505                         &jbd_fs->inode_ref,
 506                         iblock,
 507                         fblock,
 508                         false);
 509         return rc;
 510 }
 511
 512 /**@brief   jbd block get function (through cache).
 513  * @param   jbd_fs jbd filesystem
 514  * @param   block block descriptor
 515  * @param   fblock jbd logical block address
 516  * @return  standard error code*/
 517 static int jbd_block_get(struct jbd_fs *jbd_fs,
 518                   struct ext4_block *block,
 519                   ext4_fsblk_t fblock)
 520 {
 521         /* TODO: journal device. */
 522         int rc;
 523         struct ext4_blockdev *bdev = jbd_fs->bdev;
 524         ext4_lblk_t iblock = (ext4_lblk_t)fblock;
 525
 526         /* Lookup the logical block address of
 527          * fblock.*/
 528         rc = jbd_inode_bmap(jbd_fs, iblock,
 529                             &fblock);
 530         if (rc != EOK)
 531                 return rc;
 532
 533         rc = ext4_block_get(bdev, block, fblock);
 534
 535         /* If succeeded, mark buffer as BC_FLUSH to indicate
 536          * that data should be written to disk immediately.*/
 537         if (rc == EOK) {
 538                 ext4_bcache_set_flag(block->buf, BC_FLUSH);
 539                 /* As we don't want to occupy too much space
 540                  * in block cache, we set this buffer BC_TMP.*/
 541                 ext4_bcache_set_flag(block->buf, BC_TMP);
 542         }
 543
 544         return rc;
 545 }
 546
 547 /**@brief   jbd block get function (through cache, don't read).
 548  * @param   jbd_fs jbd filesystem
 549  * @param   block block descriptor
 550  * @param   fblock jbd logical block address
 551  * @return  standard error code*/
 552 static int jbd_block_get_noread(struct jbd_fs *jbd_fs,
 553                          struct ext4_block *block,
 554                          ext4_fsblk_t fblock)
 555 {
 556         /* TODO: journal device. */
 557         int rc;
 558         struct ext4_blockdev *bdev = jbd_fs->bdev;
 559         ext4_lblk_t iblock = (ext4_lblk_t)fblock;
 560         rc = jbd_inode_bmap(jbd_fs, iblock,
 561                             &fblock);
 562         if (rc != EOK)
 563                 return rc;
 564
 565         rc = ext4_block_get_noread(bdev, block, fblock);
 566         if (rc == EOK)
 567                 ext4_bcache_set_flag(block->buf, BC_FLUSH);
 568
 569         return rc;
 570 }
 571
 572 /**@brief   jbd block set procedure (through cache).
 573  * @param   jbd_fs jbd filesystem
 574  * @param   block block descriptor
 575  * @return  standard error code*/
 576 static int jbd_block_set(struct jbd_fs *jbd_fs,
 577                   struct ext4_block *block)
 578 {
 579         struct ext4_blockdev *bdev = jbd_fs->bdev;
 580         return ext4_block_set(bdev, block);
 581 }
 582
 583 /**@brief  helper functions to calculate
 584  *         block tag size, not including UUID part.
 585  * @param  jbd_fs jbd filesystem
 586  * @return tag size in bytes*/
 587 static int jbd_tag_bytes(struct jbd_fs *jbd_fs)
 588 {
 589         int size;
 590
 591         /* It is very easy to deal with the case which
 592          * JBD_FEATURE_INCOMPAT_CSUM_V3 is enabled.*/
 593         if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 594                                      JBD_FEATURE_INCOMPAT_CSUM_V3))
 595                 return sizeof(struct jbd_block_tag3);
 596
 597         size = sizeof(struct jbd_block_tag);
 598
 599         /* If JBD_FEATURE_INCOMPAT_CSUM_V2 is enabled,
 600          * add 2 bytes to size.*/
 601         if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 602                                      JBD_FEATURE_INCOMPAT_CSUM_V2))
 603                 size += sizeof(uint16_t);
 604
 605         if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 606                                      JBD_FEATURE_INCOMPAT_64BIT))
 607                 return size;
 608
 609         /* If block number is 4 bytes in size,
 610          * minus 4 bytes from size */
 611         return size - sizeof(uint32_t);
 612 }
 613
 614 /**@brief  Tag information. */
 615 struct tag_info {
 616         /**@brief  Tag size in bytes, including UUID part.*/
 617         int tag_bytes;
 618
 619         /**@brief  block number stored in this tag.*/
 620         ext4_fsblk_t block;
 621
 622         /**@brief  whether UUID part exists or not.*/
 623         bool uuid_exist;
 624
 625         /**@brief  UUID content if UUID part exists.*/
 626         uint8_t uuid[UUID_SIZE];
 627
 628         /**@brief  Is this the last tag? */
 629         bool last_tag;
 630
 631         /**@brief  crc32c checksum. */
 632         uint32_t checksum;
 633 };
 634
 635 /**@brief  Extract information from a block tag.
 636  * @param  __tag pointer to the block tag
 637  * @param  tag_bytes block tag size of this jbd filesystem
 638  * @param  remaining size in buffer containing the block tag
 639  * @param  tag_info information of this tag.
 640  * @return  EOK when succeed, otherwise return EINVAL.*/
 641 static int
 642 jbd_extract_block_tag(struct jbd_fs *jbd_fs,
 643                       void *__tag,
 644                       int tag_bytes,
 645                       int32_t remain_buf_size,
 646                       struct tag_info *tag_info)
 647 {
 648         char *uuid_start;
 649         tag_info->tag_bytes = tag_bytes;
 650         tag_info->uuid_exist = false;
 651         tag_info->last_tag = false;
 652
 653         /* See whether it is possible to hold a valid block tag.*/
 654         if (remain_buf_size - tag_bytes < 0)
 655                 return EINVAL;
 656
 657         if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 658                                      JBD_FEATURE_INCOMPAT_CSUM_V3)) {
 659                 struct jbd_block_tag3 *tag = __tag;
 660                 tag_info->block = jbd_get32(tag, blocknr);
 661                 if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 662                                              JBD_FEATURE_INCOMPAT_64BIT))
 663                          tag_info->block |=
 664                                  (uint64_t)jbd_get32(tag, blocknr_high) << 32;
 665
 666                 if (jbd_get32(tag, flags) & JBD_FLAG_ESCAPE)
 667                         tag_info->block = 0;
 668
 669                 if (!(jbd_get32(tag, flags) & JBD_FLAG_SAME_UUID)) {
 670                         /* See whether it is possible to hold UUID part.*/
 671                         if (remain_buf_size - tag_bytes < UUID_SIZE)
 672                                 return EINVAL;
 673
 674                         uuid_start = (char *)tag + tag_bytes;
 675                         tag_info->uuid_exist = true;
 676                         tag_info->tag_bytes += UUID_SIZE;
 677                         memcpy(tag_info->uuid, uuid_start, UUID_SIZE);
 678                 }
 679
 680                 if (jbd_get32(tag, flags) & JBD_FLAG_LAST_TAG)
 681                         tag_info->last_tag = true;
 682
 683         } else {
 684                 struct jbd_block_tag *tag = __tag;
 685                 tag_info->block = jbd_get32(tag, blocknr);
 686                 if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 687                                              JBD_FEATURE_INCOMPAT_64BIT))
 688                          tag_info->block |=
 689                                  (uint64_t)jbd_get32(tag, blocknr_high) << 32;
 690
 691                 if (jbd_get16(tag, flags) & JBD_FLAG_ESCAPE)
 692                         tag_info->block = 0;
 693
 694                 if (!(jbd_get16(tag, flags) & JBD_FLAG_SAME_UUID)) {
 695                         /* See whether it is possible to hold UUID part.*/
 696                         if (remain_buf_size - tag_bytes < UUID_SIZE)
 697                                 return EINVAL;
 698
 699                         uuid_start = (char *)tag + tag_bytes;
 700                         tag_info->uuid_exist = true;
 701                         tag_info->tag_bytes += UUID_SIZE;
 702                         memcpy(tag_info->uuid, uuid_start, UUID_SIZE);
 703                 }
 704
 705                 if (jbd_get16(tag, flags) & JBD_FLAG_LAST_TAG)
 706                         tag_info->last_tag = true;
 707
 708         }
 709         return EOK;
 710 }
 711
 712 /**@brief  Write information to a block tag.
 713  * @param  __tag pointer to the block tag
 714  * @param  remaining size in buffer containing the block tag
 715  * @param  tag_info information of this tag.
 716  * @return  EOK when succeed, otherwise return EINVAL.*/
 717 static int
 718 jbd_write_block_tag(struct jbd_fs *jbd_fs,
 719                     void *__tag,
 720                     int32_t remain_buf_size,
 721                     struct tag_info *tag_info)
 722 {
 723         char *uuid_start;
 724         int tag_bytes = jbd_tag_bytes(jbd_fs);
 725
 726         tag_info->tag_bytes = tag_bytes;
 727
 728         /* See whether it is possible to hold a valid block tag.*/
 729         if (remain_buf_size - tag_bytes < 0)
 730                 return EINVAL;
 731
 732         if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 733                                      JBD_FEATURE_INCOMPAT_CSUM_V3)) {
 734                 struct jbd_block_tag3 *tag = __tag;
 735                 memset(tag, 0, sizeof(struct jbd_block_tag3));
 736                 jbd_set32(tag, blocknr, (uint32_t)tag_info->block);
 737                 if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 738                                              JBD_FEATURE_INCOMPAT_64BIT))
 739                         jbd_set32(tag, blocknr_high, tag_info->block >> 32);
 740
 741                 if (tag_info->uuid_exist) {
 742                         /* See whether it is possible to hold UUID part.*/
 743                         if (remain_buf_size - tag_bytes < UUID_SIZE)
 744                                 return EINVAL;
 745
 746                         uuid_start = (char *)tag + tag_bytes;
 747                         tag_info->tag_bytes += UUID_SIZE;
 748                         memcpy(uuid_start, tag_info->uuid, UUID_SIZE);
 749                 } else
 750                         jbd_set32(tag, flags,
 751                                   jbd_get32(tag, flags) | JBD_FLAG_SAME_UUID);
 752
 753                 jbd_block_tag_csum_set(jbd_fs, __tag, tag_info->checksum);
 754
 755                 if (tag_info->last_tag)
 756                         jbd_set32(tag, flags,
 757                                   jbd_get32(tag, flags) | JBD_FLAG_LAST_TAG);
 758
 759         } else {
 760                 struct jbd_block_tag *tag = __tag;
 761                 memset(tag, 0, sizeof(struct jbd_block_tag));
 762                 jbd_set32(tag, blocknr, (uint32_t)tag_info->block);
 763                 if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 764                                              JBD_FEATURE_INCOMPAT_64BIT))
 765                         jbd_set32(tag, blocknr_high, tag_info->block >> 32);
 766
 767                 if (tag_info->uuid_exist) {
 768                         /* See whether it is possible to hold UUID part.*/
 769                         if (remain_buf_size - tag_bytes < UUID_SIZE)
 770                                 return EINVAL;
 771
 772                         uuid_start = (char *)tag + tag_bytes;
 773                         tag_info->tag_bytes += UUID_SIZE;
 774                         memcpy(uuid_start, tag_info->uuid, UUID_SIZE);
 775                 } else
 776                         jbd_set16(tag, flags,
 777                                   jbd_get16(tag, flags) | JBD_FLAG_SAME_UUID);
 778
 779                 jbd_block_tag_csum_set(jbd_fs, __tag, tag_info->checksum);
 780
 781                 if (tag_info->last_tag)
 782                         jbd_set16(tag, flags,
 783                                   jbd_get16(tag, flags) | JBD_FLAG_LAST_TAG);
 784
 785         }
 786         return EOK;
 787 }
 788
 789 /**@brief  Iterate all block tags in a block.
 790  * @param  jbd_fs jbd filesystem
 791  * @param  __tag_start pointer to the block
 792  * @param  tag_tbl_size size of the block
 793  * @param  func callback routine to indicate that
 794  *         a block tag is found
 795  * @param  arg additional argument to be passed to func */
 796 static void
 797 jbd_iterate_block_table(struct jbd_fs *jbd_fs,
 798                         void *__tag_start,
 799                         int32_t tag_tbl_size,
 800                         void (*func)(struct jbd_fs * jbd_fs,
 801                                         ext4_fsblk_t block,
 802                                         uint8_t *uuid,
 803                                         void *arg),
 804                         void *arg)
 805 {
 806         char *tag_start, *tag_ptr;
 807         int tag_bytes = jbd_tag_bytes(jbd_fs);
 808         tag_start = __tag_start;
 809         tag_ptr = tag_start;
 810
 811         /* Cut off the size of block tail storing checksum. */
 812         if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 813                                      JBD_FEATURE_INCOMPAT_CSUM_V2) ||
 814             JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 815                                      JBD_FEATURE_INCOMPAT_CSUM_V3))
 816                 tag_tbl_size -= sizeof(struct jbd_block_tail);
 817
 818         while (tag_tbl_size) {
 819                 struct tag_info tag_info;
 820                 int rc = jbd_extract_block_tag(jbd_fs,
 821                                       tag_ptr,
 822                                       tag_bytes,
 823                                       tag_tbl_size,
 824                                       &tag_info);
 825                 if (rc != EOK)
 826                         break;
 827
 828                 if (func)
 829                         func(jbd_fs, tag_info.block, tag_info.uuid, arg);
 830
 831                 /* Stop the iteration when we reach the last tag. */
 832                 if (tag_info.last_tag)
 833                         break;
 834
 835                 tag_ptr += tag_info.tag_bytes;
 836                 tag_tbl_size -= tag_info.tag_bytes;
 837         }
 838 }
 839
 840 static void jbd_display_block_tags(struct jbd_fs *jbd_fs,
 841                                    ext4_fsblk_t block,
 842                                    uint8_t *uuid,
 843                                    void *arg)
 844 {
 845         uint32_t *iblock = arg;
 846         ext4_dbg(DEBUG_JBD, "Block in block_tag: %" PRIu64 "\n", block);
 847         (*iblock)++;
 848         wrap(&jbd_fs->sb, *iblock);
 849         (void)jbd_fs;
 850         (void)uuid;
 851         return;
 852 }
 853
 854 static struct revoke_entry *
 855 jbd_revoke_entry_lookup(struct recover_info *info, ext4_fsblk_t block)
 856 {
 857         struct revoke_entry tmp = {
 858                 .block = block
 859         };
 860
 861         return RB_FIND(jbd_revoke, &info->revoke_root, &tmp);
 862 }
 863
 864 /**@brief  Replay a block in a transaction.
 865  * @param  jbd_fs jbd filesystem
 866  * @param  block  block address to be replayed.*/
 867 static void jbd_replay_block_tags(struct jbd_fs *jbd_fs,
 868                                   ext4_fsblk_t block,
 869                                   uint8_t *uuid __unused,
 870                                   void *__arg)
 871 {
 872         int r;
 873         struct replay_arg *arg = __arg;
 874         struct recover_info *info = arg->info;
 875         uint32_t *this_block = arg->this_block;
 876         struct revoke_entry *revoke_entry;
 877         struct ext4_block journal_block, ext4_block;
 878         struct ext4_fs *fs = jbd_fs->inode_ref.fs;
 879
 880         (*this_block)++;
 881         wrap(&jbd_fs->sb, *this_block);
 882
 883         /* We replay this block only if the current transaction id
 884          * is equal or greater than that in revoke entry.*/
 885         revoke_entry = jbd_revoke_entry_lookup(info, block);
 886         if (revoke_entry &&
 887             trans_id_diff(arg->this_trans_id, revoke_entry->trans_id) < 0)
 888                 return;
 889
 890         ext4_dbg(DEBUG_JBD,
 891                  "Replaying block in block_tag: %" PRIu64 "\n",
 892                  block);
 893
 894         r = jbd_block_get(jbd_fs, &journal_block, *this_block);
 895         if (r != EOK)
 896                 return;
 897
 898         /* We need special treatment for ext4 superblock. */
 899         if (block) {
 900                 r = ext4_block_get_noread(fs->bdev, &ext4_block, block);
 901                 if (r != EOK) {
 902                         jbd_block_set(jbd_fs, &journal_block);
 903                         return;
 904                 }
 905
 906                 memcpy(ext4_block.data,
 907                         journal_block.data,
 908                         jbd_get32(&jbd_fs->sb, blocksize));
 909
 910                 ext4_bcache_set_dirty(ext4_block.buf);
 911                 ext4_block_set(fs->bdev, &ext4_block);
 912         } else {
 913                 uint16_t mount_count, state;
 914                 mount_count = ext4_get16(&fs->sb, mount_count);
 915                 state = ext4_get16(&fs->sb, state);
 916
 917                 memcpy(&fs->sb,
 918                         journal_block.data + EXT4_SUPERBLOCK_OFFSET,
 919                         EXT4_SUPERBLOCK_SIZE);
 920
 921                 /* Mark system as mounted */
 922                 ext4_set16(&fs->sb, state, state);
 923                 r = ext4_sb_write(fs->bdev, &fs->sb);
 924                 if (r != EOK)
 925                         return;
 926
 927                 /*Update mount count*/
 928                 ext4_set16(&fs->sb, mount_count, mount_count);
 929         }
 930
 931         jbd_block_set(jbd_fs, &journal_block);
 932
 933         return;
 934 }
 935
 936 /**@brief  Add block address to revoke tree, along with
 937  *         its transaction id.
 938  * @param  info  journal replay info
 939  * @param  block  block address to be replayed.*/
 940 static void jbd_add_revoke_block_tags(struct recover_info *info,
 941                                       ext4_fsblk_t block)
 942 {
 943         struct revoke_entry *revoke_entry;
 944
 945         ext4_dbg(DEBUG_JBD, "Add block %" PRIu64 " to revoke tree\n", block);
 946         /* If the revoke entry with respect to the block address
 947          * exists already, update its transaction id.*/
 948         revoke_entry = jbd_revoke_entry_lookup(info, block);
 949         if (revoke_entry) {
 950                 revoke_entry->trans_id = info->this_trans_id;
 951                 return;
 952         }
 953
 954         revoke_entry = jbd_alloc_revoke_entry();
 955         ext4_assert(revoke_entry);
 956         revoke_entry->block = block;
 957         revoke_entry->trans_id = info->this_trans_id;
 958         RB_INSERT(jbd_revoke, &info->revoke_root, revoke_entry);
 959
 960         return;
 961 }
 962
 963 static void jbd_destroy_revoke_tree(struct recover_info *info)
 964 {
 965         while (!RB_EMPTY(&info->revoke_root)) {
 966                 struct revoke_entry *revoke_entry =
 967                         RB_MIN(jbd_revoke, &info->revoke_root);
 968                 ext4_assert(revoke_entry);
 969                 RB_REMOVE(jbd_revoke, &info->revoke_root, revoke_entry);
 970                 jbd_free_revoke_entry(revoke_entry);
 971         }
 972 }
 973
 974
 975 #define ACTION_SCAN 0
 976 #define ACTION_REVOKE 1
 977 #define ACTION_RECOVER 2
 978
 979 /**@brief  Add entries in a revoke block to revoke tree.
 980  * @param  jbd_fs jbd filesystem
 981  * @param  header revoke block header
 982  * @param  recover_info  journal replay info*/
 983 static void jbd_build_revoke_tree(struct jbd_fs *jbd_fs,
 984                                   struct jbd_bhdr *header,
 985                                   struct recover_info *info)
 986 {
 987         char *blocks_entry;
 988         struct jbd_revoke_header *revoke_hdr =
 989                 (struct jbd_revoke_header *)header;
 990         uint32_t i, nr_entries, record_len = 4;
 991
 992         /* If we are working on a 64bit jbd filesystem, */
 993         if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 994                                      JBD_FEATURE_INCOMPAT_64BIT))
 995                 record_len = 8;
 996
 997         nr_entries = (jbd_get32(revoke_hdr, count) -
 998                         sizeof(struct jbd_revoke_header)) /
 999                         record_len;
1000
1001         blocks_entry = (char *)(revoke_hdr + 1);
1002
1003         for (i = 0;i < nr_entries;i++) {
1004                 if (record_len == 8) {
1005                         uint64_t *blocks =
1006                                 (uint64_t *)blocks_entry;
1007                         jbd_add_revoke_block_tags(info, to_be64(*blocks));
1008                 } else {
1009                         uint32_t *blocks =
1010                                 (uint32_t *)blocks_entry;
1011                         jbd_add_revoke_block_tags(info, to_be32(*blocks));
1012                 }
1013                 blocks_entry += record_len;
1014         }
1015 }
1016
1017 static void jbd_debug_descriptor_block(struct jbd_fs *jbd_fs,
1018                                        struct jbd_bhdr *header,
1019                                        uint32_t *iblock)
1020 {
1021         jbd_iterate_block_table(jbd_fs,
1022                                 header + 1,
1023                                 jbd_get32(&jbd_fs->sb, blocksize) -
1024                                         sizeof(struct jbd_bhdr),
1025                                 jbd_display_block_tags,
1026                                 iblock);
1027 }
1028
1029 static void jbd_replay_descriptor_block(struct jbd_fs *jbd_fs,
1030                                         struct jbd_bhdr *header,
1031                                         struct replay_arg *arg)
1032 {
1033         jbd_iterate_block_table(jbd_fs,
1034                                 header + 1,
1035                                 jbd_get32(&jbd_fs->sb, blocksize) -
1036                                         sizeof(struct jbd_bhdr),
1037                                 jbd_replay_block_tags,
1038                                 arg);
1039 }
1040
1041 /**@brief  The core routine of journal replay.
1042  * @param  jbd_fs jbd filesystem
1043  * @param  recover_info  journal replay info
1044  * @param  action action needed to be taken
1045  * @return standard error code*/
1046 static int jbd_iterate_log(struct jbd_fs *jbd_fs,
1047                            struct recover_info *info,
1048                            int action)
1049 {
1050         int r = EOK;
1051         bool log_end = false;
1052         struct jbd_sb *sb = &jbd_fs->sb;
1053         uint32_t start_trans_id, this_trans_id;
1054         uint32_t start_block, this_block;
1055
1056         /* We start iterating valid blocks in the whole journal.*/
1057         start_trans_id = this_trans_id = jbd_get32(sb, sequence);
1058         start_block = this_block = jbd_get32(sb, start);
1059         if (action == ACTION_SCAN)
1060                 info->trans_cnt = 0;
1061         else if (!info->trans_cnt)
1062                 log_end = true;
1063
1064         ext4_dbg(DEBUG_JBD, "Start of journal at trans id: %" PRIu32 "\n",
1065                             start_trans_id);
1066
1067         while (!log_end) {
1068                 struct ext4_block block;
1069                 struct jbd_bhdr *header;
1070                 /* If we are not scanning for the last
1071                  * valid transaction in the journal,
1072                  * we will stop when we reach the end of
1073                  * the journal.*/
1074                 if (action != ACTION_SCAN)
1075                         if (trans_id_diff(this_trans_id, info->last_trans_id) > 0) {
1076                                 log_end = true;
1077                                 continue;
1078                         }
1079
1080                 r = jbd_block_get(jbd_fs, &block, this_block);
1081                 if (r != EOK)
1082                         break;
1083
1084                 header = (struct jbd_bhdr *)block.data;
1085                 /* This block does not have a valid magic number,
1086                  * so we have reached the end of the journal.*/
1087                 if (jbd_get32(header, magic) != JBD_MAGIC_NUMBER) {
1088                         jbd_block_set(jbd_fs, &block);
1089                         log_end = true;
1090                         continue;
1091                 }
1092
1093                 /* If the transaction id we found is not expected,
1094                  * we may have reached the end of the journal.
1095                  *
1096                  * If we are not scanning the journal, something
1097                  * bad might have taken place. :-( */
1098                 if (jbd_get32(header, sequence) != this_trans_id) {
1099                         if (action != ACTION_SCAN)
1100                                 r = EIO;
1101
1102                         jbd_block_set(jbd_fs, &block);
1103                         log_end = true;
1104                         continue;
1105                 }
1106
1107                 switch (jbd_get32(header, blocktype)) {
1108                 case JBD_DESCRIPTOR_BLOCK:
1109                         if (!jbd_verify_meta_csum(jbd_fs, header)) {
1110                                 ext4_dbg(DEBUG_JBD,
1111                                         DBG_WARN "Descriptor block checksum failed."
1112                                                 "Journal block: %" PRIu32"\n",
1113                                                 this_block);
1114                                 log_end = true;
1115                                 break;
1116                         }
1117                         ext4_dbg(DEBUG_JBD, "Descriptor block: %" PRIu32", "
1118                                             "trans_id: %" PRIu32"\n",
1119                                             this_block, this_trans_id);
1120                         if (action == ACTION_RECOVER) {
1121                                 struct replay_arg replay_arg;
1122                                 replay_arg.info = info;
1123                                 replay_arg.this_block = &this_block;
1124                                 replay_arg.this_trans_id = this_trans_id;
1125
1126                                 jbd_replay_descriptor_block(jbd_fs,
1127                                                 header, &replay_arg);
1128                         } else
1129                                 jbd_debug_descriptor_block(jbd_fs,
1130                                                 header, &this_block);
1131
1132                         break;
1133                 case JBD_COMMIT_BLOCK:
1134                         if (!jbd_verify_commit_csum(jbd_fs,
1135                                         (struct jbd_commit_header *)header)) {
1136                                 ext4_dbg(DEBUG_JBD,
1137                                         DBG_WARN "Commit block checksum failed."
1138                                                 "Journal block: %" PRIu32"\n",
1139                                                 this_block);
1140                                 log_end = true;
1141                                 break;
1142                         }
1143                         ext4_dbg(DEBUG_JBD, "Commit block: %" PRIu32", "
1144                                             "trans_id: %" PRIu32"\n",
1145                                             this_block, this_trans_id);
1146                         /* This is the end of a transaction,
1147                          * we may now proceed to the next transaction.
1148                          */
1149                         this_trans_id++;
1150                         info->trans_cnt++;
1151                         break;
1152                 case JBD_REVOKE_BLOCK:
1153                         if (!jbd_verify_meta_csum(jbd_fs, header)) {
1154                                 ext4_dbg(DEBUG_JBD,
1155                                         DBG_WARN "Revoke block checksum failed."
1156                                                 "Journal block: %" PRIu32"\n",
1157                                                 this_block);
1158                                 log_end = true;
1159                                 break;
1160                         }
1161                         ext4_dbg(DEBUG_JBD, "Revoke block: %" PRIu32", "
1162                                             "trans_id: %" PRIu32"\n",
1163                                             this_block, this_trans_id);
1164                         if (action == ACTION_REVOKE) {
1165                                 info->this_trans_id = this_trans_id;
1166                                 jbd_build_revoke_tree(jbd_fs,
1167                                                 header, info);
1168                         }
1169                         break;
1170                 default:
1171                         log_end = true;
1172                         break;
1173                 }
1174                 jbd_block_set(jbd_fs, &block);
1175                 this_block++;
1176                 wrap(sb, this_block);
1177                 if (this_block == start_block)
1178                         log_end = true;
1179
1180         }
1181         ext4_dbg(DEBUG_JBD, "End of journal.\n");
1182         if (r == EOK && action == ACTION_SCAN) {
1183                 /* We have finished scanning the journal. */
1184                 info->start_trans_id = start_trans_id;
1185                 if (trans_id_diff(this_trans_id, start_trans_id) > 0)
1186                         info->last_trans_id = this_trans_id - 1;
1187                 else
1188                         info->last_trans_id = this_trans_id;
1189         }
1190
1191         return r;
1192 }
1193
1194 /**@brief  Replay journal.
1195  * @param  jbd_fs jbd filesystem
1196  * @return standard error code*/
1197 int jbd_recover(struct jbd_fs *jbd_fs)
1198 {
1199         int r;
1200         struct recover_info info;
1201         struct jbd_sb *sb = &jbd_fs->sb;
1202         if (!sb->start)
1203                 return EOK;
1204
1205         RB_INIT(&info.revoke_root);
1206
1207         r = jbd_iterate_log(jbd_fs, &info, ACTION_SCAN);
1208         if (r != EOK)
1209                 return r;
1210
1211         r = jbd_iterate_log(jbd_fs, &info, ACTION_REVOKE);
1212         if (r != EOK)
1213                 return r;
1214
1215         r = jbd_iterate_log(jbd_fs, &info, ACTION_RECOVER);
1216         if (r == EOK) {
1217                 /* If we successfully replay the journal,
1218                  * clear EXT4_FINCOM_RECOVER flag on the
1219                  * ext4 superblock, and set the start of
1220                  * journal to 0.*/
1221                 uint32_t features_incompatible =
1222                         ext4_get32(&jbd_fs->inode_ref.fs->sb,
1223                                    features_incompatible);
1224                 jbd_set32(&jbd_fs->sb, start, 0);
1225                 features_incompatible &= ~EXT4_FINCOM_RECOVER;
1226                 ext4_set32(&jbd_fs->inode_ref.fs->sb,
1227                            features_incompatible,
1228                            features_incompatible);
1229                 jbd_fs->dirty = true;
1230                 r = ext4_sb_write(jbd_fs->bdev,
1231                                   &jbd_fs->inode_ref.fs->sb);
1232         }
1233         jbd_destroy_revoke_tree(&info);
1234         return r;
1235 }
1236
1237 static void jbd_journal_write_sb(struct jbd_journal *journal)
1238 {
1239         struct jbd_fs *jbd_fs = journal->jbd_fs;
1240         jbd_set32(&jbd_fs->sb, start, journal->start);
1241         jbd_set32(&jbd_fs->sb, sequence, journal->trans_id);
1242         jbd_fs->dirty = true;
1243 }
1244
1245 /**@brief  Start accessing the journal.
1246  * @param  jbd_fs jbd filesystem
1247  * @param  journal current journal session
1248  * @return standard error code*/
1249 int jbd_journal_start(struct jbd_fs *jbd_fs,
1250                       struct jbd_journal *journal)
1251 {
1252         int r;
1253         uint32_t features_incompatible =
1254                         ext4_get32(&jbd_fs->inode_ref.fs->sb,
1255                                    features_incompatible);
1256         struct ext4_block block = EXT4_BLOCK_ZERO();
1257         features_incompatible |= EXT4_FINCOM_RECOVER;
1258         ext4_set32(&jbd_fs->inode_ref.fs->sb,
1259                         features_incompatible,
1260                         features_incompatible);
1261         r = ext4_sb_write(jbd_fs->bdev,
1262                         &jbd_fs->inode_ref.fs->sb);
1263         if (r != EOK)
1264                 return r;
1265
1266         journal->first = jbd_get32(&jbd_fs->sb, first);
1267         journal->start = journal->first;
1268         journal->last = journal->first;
1269         journal->trans_id = 1;
1270         journal->alloc_trans_id = 1;
1271
1272         journal->block_size = jbd_get32(&jbd_fs->sb, blocksize);
1273
1274         r = jbd_block_get_noread(jbd_fs,
1275                          &block,
1276                          journal->start);
1277         if (r != EOK) {
1278                 memset(journal, 0, sizeof(struct jbd_journal));
1279                 return r;
1280         }
1281         memset(block.data, 0, journal->block_size);
1282         ext4_bcache_set_dirty(block.buf);
1283         r = jbd_block_set(jbd_fs, &block);
1284         if (r != EOK) {
1285                 memset(journal, 0, sizeof(struct jbd_journal));
1286                 return r;
1287         }
1288
1289         TAILQ_INIT(&journal->cp_queue);
1290         RB_INIT(&journal->block_rec_root);
1291         journal->jbd_fs = jbd_fs;
1292         jbd_journal_write_sb(journal);
1293         r = jbd_write_sb(jbd_fs);
1294         if (r != EOK)
1295                 return r;
1296
1297         jbd_fs->bdev->journal = journal;
1298         return EOK;
1299 }
1300
1301 static void jbd_trans_end_write(struct ext4_bcache *bc __unused,
1302                           struct ext4_buf *buf __unused,
1303                           int res,
1304                           void *arg);
1305
1306 /*
1307  * This routine is only suitable to committed transactions. */
1308 static void jbd_journal_flush_trans(struct jbd_trans *trans)
1309 {
1310         struct jbd_buf *jbd_buf, *tmp;
1311         struct jbd_journal *journal = trans->journal;
1312         struct ext4_fs *fs = journal->jbd_fs->inode_ref.fs;
1313         void *tmp_data = malloc(journal->block_size);
1314         ext4_assert(tmp_data);
1315
1316         TAILQ_FOREACH_SAFE(jbd_buf, &trans->buf_queue, buf_node,
1317                         tmp) {
1318                 struct ext4_buf *buf;
1319                 struct ext4_block block;
1320                 /* The buffer is not yet flushed. */
1321                 buf = ext4_bcache_find_get(fs->bdev->bc, &block,
1322                                            jbd_buf->block_rec->lba);
1323                 if (!(buf && ext4_bcache_test_flag(buf, BC_UPTODATE) &&
1324                       jbd_buf->block_rec->trans == trans)) {
1325                         int r;
1326                         struct ext4_block jbd_block = EXT4_BLOCK_ZERO();
1327                         ext4_assert(jbd_block_get(journal->jbd_fs,
1328                                                 &jbd_block,
1329                                                 jbd_buf->jbd_lba) == EOK);
1330                         memcpy(tmp_data, jbd_block.data,
1331                                         journal->block_size);
1332                         ext4_block_set(fs->bdev, &jbd_block);
1333                         r = ext4_blocks_set_direct(fs->bdev, tmp_data,
1334                                         jbd_buf->block_rec->lba, 1);
1335                         jbd_trans_end_write(fs->bdev->bc, buf, r, jbd_buf);
1336                 } else
1337                         ext4_block_flush_buf(fs->bdev, buf);
1338
1339                 if (buf)
1340                         ext4_block_set(fs->bdev, &block);
1341         }
1342
1343         free(tmp_data);
1344 }
1345
1346 static void
1347 jbd_journal_skip_pure_revoke(struct jbd_journal *journal,
1348                              struct jbd_trans *trans)
1349 {
1350         journal->start = trans->start_iblock +
1351                 trans->alloc_blocks;
1352         wrap(&journal->jbd_fs->sb, journal->start);
1353         journal->trans_id = trans->trans_id + 1;
1354         jbd_journal_free_trans(journal,
1355                         trans, false);
1356         jbd_journal_write_sb(journal);
1357 }
1358
1359 void
1360 jbd_journal_purge_cp_trans(struct jbd_journal *journal,
1361                            bool flush,
1362                            bool once)
1363 {
1364         struct jbd_trans *trans;
1365         while ((trans = TAILQ_FIRST(&journal->cp_queue))) {
1366                 if (!trans->data_cnt) {
1367                         TAILQ_REMOVE(&journal->cp_queue,
1368                                         trans,
1369                                         trans_node);
1370                         jbd_journal_skip_pure_revoke(journal, trans);
1371                 } else {
1372                         if (trans->data_cnt ==
1373                                         trans->written_cnt) {
1374                                 journal->start =
1375                                         trans->start_iblock +
1376                                         trans->alloc_blocks;
1377                                 wrap(&journal->jbd_fs->sb,
1378                                                 journal->start);
1379                                 journal->trans_id =
1380                                         trans->trans_id + 1;
1381                                 TAILQ_REMOVE(&journal->cp_queue,
1382                                                 trans,
1383                                                 trans_node);
1384                                 jbd_journal_free_trans(journal,
1385                                                 trans,
1386                                                 false);
1387                                 jbd_journal_write_sb(journal);
1388                         } else if (!flush) {
1389                                 journal->start =
1390                                         trans->start_iblock;
1391                                 wrap(&journal->jbd_fs->sb,
1392                                                 journal->start);
1393                                 journal->trans_id =
1394                                         trans->trans_id;
1395                                 jbd_journal_write_sb(journal);
1396                                 break;
1397                         } else
1398                                 jbd_journal_flush_trans(trans);
1399                 }
1400                 if (once)
1401                         break;
1402         }
1403 }
1404
1405 /**@brief  Stop accessing the journal.
1406  * @param  journal current journal session
1407  * @return standard error code*/
1408 int jbd_journal_stop(struct jbd_journal *journal)
1409 {
1410         int r;
1411         struct jbd_fs *jbd_fs = journal->jbd_fs;
1412         uint32_t features_incompatible;
1413
1414         /* Make sure that journalled content have reached
1415          * the disk.*/
1416         jbd_journal_purge_cp_trans(journal, true, false);
1417
1418         /* There should be no block record in this journal
1419          * session. */
1420         if (!RB_EMPTY(&journal->block_rec_root))
1421                 ext4_dbg(DEBUG_JBD,
1422                          DBG_WARN "There are still block records "
1423                                   "in this journal session!\n");
1424
1425         features_incompatible =
1426                 ext4_get32(&jbd_fs->inode_ref.fs->sb,
1427                            features_incompatible);
1428         features_incompatible &= ~EXT4_FINCOM_RECOVER;
1429         ext4_set32(&jbd_fs->inode_ref.fs->sb,
1430                         features_incompatible,
1431                         features_incompatible);
1432         r = ext4_sb_write(jbd_fs->bdev,
1433                         &jbd_fs->inode_ref.fs->sb);
1434         if (r != EOK)
1435                 return r;
1436
1437         journal->start = 0;
1438         journal->trans_id = 0;
1439         jbd_journal_write_sb(journal);
1440         return jbd_write_sb(journal->jbd_fs);
1441 }
1442
1443 /**@brief  Allocate a block in the journal.
1444  * @param  journal current journal session
1445  * @param  trans transaction
1446  * @return allocated block address*/
1447 static uint32_t jbd_journal_alloc_block(struct jbd_journal *journal,
1448                                         struct jbd_trans *trans)
1449 {
1450         uint32_t start_block;
1451
1452         start_block = journal->last++;
1453         trans->alloc_blocks++;
1454         wrap(&journal->jbd_fs->sb, journal->last);
1455
1456         /* If there is no space left, flush all journalled
1457          * blocks to disk first.*/
1458         if (journal->last == journal->start)
1459                 jbd_journal_purge_cp_trans(journal, true, false);
1460
1461         return start_block;
1462 }
1463
1464 static struct jbd_block_rec *
1465 jbd_trans_block_rec_lookup(struct jbd_journal *journal,
1466                            ext4_fsblk_t lba)
1467 {
1468         struct jbd_block_rec tmp = {
1469                 .lba = lba
1470         };
1471
1472         return RB_FIND(jbd_block,
1473                        &journal->block_rec_root,
1474                        &tmp);
1475 }
1476
1477 static void
1478 jbd_trans_change_ownership(struct jbd_block_rec *block_rec,
1479                            struct jbd_trans *new_trans)
1480 {
1481         LIST_REMOVE(block_rec, tbrec_node);
1482         if (new_trans) {
1483                 /* Now this block record belongs to this transaction. */
1484                 LIST_INSERT_HEAD(&new_trans->tbrec_list, block_rec, tbrec_node);
1485         }
1486         block_rec->trans = new_trans;
1487 }
1488
1489 static inline struct jbd_block_rec *
1490 jbd_trans_insert_block_rec(struct jbd_trans *trans,
1491                            ext4_fsblk_t lba)
1492 {
1493         struct jbd_block_rec *block_rec;
1494         block_rec = jbd_trans_block_rec_lookup(trans->journal, lba);
1495         if (block_rec) {
1496                 jbd_trans_change_ownership(block_rec, trans);
1497                 return block_rec;
1498         }
1499         block_rec = calloc(1, sizeof(struct jbd_block_rec));
1500         if (!block_rec)
1501                 return NULL;
1502
1503         block_rec->lba = lba;
1504         block_rec->trans = trans;
1505         TAILQ_INIT(&block_rec->dirty_buf_queue);
1506         LIST_INSERT_HEAD(&trans->tbrec_list, block_rec, tbrec_node);
1507         RB_INSERT(jbd_block, &trans->journal->block_rec_root, block_rec);
1508         return block_rec;
1509 }
1510
1511 /*
1512  * This routine will do the dirty works.
1513  */
1514 static void
1515 jbd_trans_finish_callback(struct jbd_journal *journal,
1516                           const struct jbd_trans *trans,
1517                           struct jbd_block_rec *block_rec,
1518                           bool abort,
1519                           bool revoke)
1520 {
1521         struct ext4_fs *fs = journal->jbd_fs->inode_ref.fs;
1522         if (block_rec->trans != trans)
1523                 return;
1524
1525         if (!abort) {
1526                 struct jbd_buf *jbd_buf, *tmp;
1527                 TAILQ_FOREACH_SAFE(jbd_buf,
1528                                 &block_rec->dirty_buf_queue,
1529                                 dirty_buf_node,
1530                                 tmp) {
1531                         jbd_trans_end_write(fs->bdev->bc,
1532                                         NULL,
1533                                         EOK,
1534                                         jbd_buf);
1535                 }
1536         } else {
1537                 /*
1538                  * We have to roll back data if the block is going to be
1539                  * aborted.
1540                  */
1541                 struct jbd_buf *jbd_buf;
1542                 struct ext4_block jbd_block = EXT4_BLOCK_ZERO(),
1543                                   block = EXT4_BLOCK_ZERO();
1544                 jbd_buf = TAILQ_LAST(&block_rec->dirty_buf_queue,
1545                                 jbd_buf_dirty);
1546                 if (jbd_buf) {
1547                         if (!revoke) {
1548                                 ext4_assert(ext4_block_get_noread(fs->bdev,
1549                                                         &block,
1550                                                         block_rec->lba) == EOK);
1551                                 ext4_assert(jbd_block_get(journal->jbd_fs,
1552                                                         &jbd_block,
1553                                                         jbd_buf->jbd_lba) == EOK);
1554                                 memcpy(block.data, jbd_block.data,
1555                                                 journal->block_size);
1556
1557                                 jbd_trans_change_ownership(block_rec,
1558                                                 jbd_buf->trans);
1559
1560                                 block.buf->end_write = jbd_trans_end_write;
1561                                 block.buf->end_write_arg = jbd_buf;
1562
1563                                 ext4_bcache_set_flag(jbd_block.buf, BC_TMP);
1564                                 ext4_bcache_set_dirty(block.buf);
1565
1566                                 ext4_block_set(fs->bdev, &jbd_block);
1567                                 ext4_block_set(fs->bdev, &block);
1568                                 return;
1569                         } else {
1570                                 /* The revoked buffer is yet written. */
1571                                 jbd_trans_change_ownership(block_rec,
1572                                                 jbd_buf->trans);
1573                         }
1574                 }
1575         }
1576 }
1577
1578 static inline void
1579 jbd_trans_remove_block_rec(struct jbd_journal *journal,
1580                            struct jbd_block_rec *block_rec,
1581                            struct jbd_trans *trans)
1582 {
1583         /* If this block record doesn't belong to this transaction,
1584          * give up.*/
1585         if (block_rec->trans == trans) {
1586                 LIST_REMOVE(block_rec, tbrec_node);
1587                 RB_REMOVE(jbd_block,
1588                                 &journal->block_rec_root,
1589                                 block_rec);
1590                 free(block_rec);
1591         }
1592 }
1593
1594 /**@brief  Add block to a transaction and mark it dirty.
1595  * @param  trans transaction
1596  * @param  block block descriptor
1597  * @return standard error code*/
1598 int jbd_trans_set_block_dirty(struct jbd_trans *trans,
1599                               struct ext4_block *block)
1600 {
1601         struct jbd_buf *jbd_buf;
1602         struct jbd_revoke_rec *rec, tmp_rec = {
1603                 .lba = block->lb_id
1604         };
1605         struct jbd_block_rec *block_rec;
1606
1607         if (block->buf->end_write == jbd_trans_end_write) {
1608                 jbd_buf = block->buf->end_write_arg;
1609                 if (jbd_buf && jbd_buf->trans == trans)
1610                         return EOK;
1611         }
1612         jbd_buf = calloc(1, sizeof(struct jbd_buf));
1613         if (!jbd_buf)
1614                 return ENOMEM;
1615
1616         if ((block_rec = jbd_trans_insert_block_rec(trans,
1617                                         block->lb_id)) == NULL) {
1618                 free(jbd_buf);
1619                 return ENOMEM;
1620         }
1621
1622         TAILQ_INSERT_TAIL(&block_rec->dirty_buf_queue,
1623                         jbd_buf,
1624                         dirty_buf_node);
1625
1626         jbd_buf->block_rec = block_rec;
1627         jbd_buf->trans = trans;
1628         jbd_buf->block = *block;
1629         ext4_bcache_inc_ref(block->buf);
1630
1631         /* If the content reach the disk, notify us
1632          * so that we may do a checkpoint. */
1633         block->buf->end_write = jbd_trans_end_write;
1634         block->buf->end_write_arg = jbd_buf;
1635
1636         trans->data_cnt++;
1637         TAILQ_INSERT_HEAD(&trans->buf_queue, jbd_buf, buf_node);
1638
1639         ext4_bcache_set_dirty(block->buf);
1640         rec = RB_FIND(jbd_revoke_tree,
1641                         &trans->revoke_root,
1642                         &tmp_rec);
1643         if (rec) {
1644                 RB_REMOVE(jbd_revoke_tree, &trans->revoke_root,
1645                           rec);
1646                 free(rec);
1647         }
1648
1649         return EOK;
1650 }
1651
1652 /**@brief  Add block to be revoked to a transaction
1653  * @param  trans transaction
1654  * @param  lba logical block address
1655  * @return standard error code*/
1656 int jbd_trans_revoke_block(struct jbd_trans *trans,
1657                            ext4_fsblk_t lba)
1658 {
1659         struct jbd_revoke_rec tmp_rec = {
1660                 .lba = lba
1661         }, *rec;
1662         rec = RB_FIND(jbd_revoke_tree,
1663                       &trans->revoke_root,
1664                       &tmp_rec);
1665         if (rec)
1666                 return EOK;
1667
1668         rec = calloc(1, sizeof(struct jbd_revoke_rec));
1669         if (!rec)
1670                 return ENOMEM;
1671
1672         rec->lba = lba;
1673         RB_INSERT(jbd_revoke_tree, &trans->revoke_root, rec);
1674         return EOK;
1675 }
1676
1677 /**@brief  Try to add block to be revoked to a transaction.
1678  *         If @lba still remains in an transaction on checkpoint
1679  *         queue, add @lba as a revoked block to the transaction.
1680  * @param  trans transaction
1681  * @param  lba logical block address
1682  * @return standard error code*/
1683 int jbd_trans_try_revoke_block(struct jbd_trans *trans,
1684                                ext4_fsblk_t lba)
1685 {
1686         struct jbd_journal *journal = trans->journal;
1687         struct jbd_block_rec *block_rec =
1688                 jbd_trans_block_rec_lookup(journal, lba);
1689
1690         if (block_rec) {
1691                 if (block_rec->trans == trans) {
1692                         struct jbd_buf *jbd_buf =
1693                                 TAILQ_LAST(&block_rec->dirty_buf_queue,
1694                                         jbd_buf_dirty);
1695                         /* If there are still unwritten buffers. */
1696                         if (TAILQ_FIRST(&block_rec->dirty_buf_queue) !=
1697                             jbd_buf)
1698                                 jbd_trans_revoke_block(trans, lba);
1699
1700                 } else
1701                         jbd_trans_revoke_block(trans, lba);
1702         }
1703
1704         return EOK;
1705 }
1706
1707 /**@brief  Free a transaction
1708  * @param  journal current journal session
1709  * @param  trans transaction
1710  * @param  abort discard all the modifications on the block?
1711  * @return standard error code*/
1712 void jbd_journal_free_trans(struct jbd_journal *journal,
1713                             struct jbd_trans *trans,
1714                             bool abort)
1715 {
1716         struct jbd_buf *jbd_buf, *tmp;
1717         struct jbd_revoke_rec *rec, *tmp2;
1718         struct jbd_block_rec *block_rec, *tmp3;
1719         struct ext4_fs *fs = journal->jbd_fs->inode_ref.fs;
1720         TAILQ_FOREACH_SAFE(jbd_buf, &trans->buf_queue, buf_node,
1721                           tmp) {
1722                 block_rec = jbd_buf->block_rec;
1723                 if (abort) {
1724                         jbd_buf->block.buf->end_write = NULL;
1725                         jbd_buf->block.buf->end_write_arg = NULL;
1726                         ext4_bcache_clear_dirty(jbd_buf->block.buf);
1727                         ext4_block_set(fs->bdev, &jbd_buf->block);
1728                 }
1729
1730                 TAILQ_REMOVE(&jbd_buf->block_rec->dirty_buf_queue,
1731                         jbd_buf,
1732                         dirty_buf_node);
1733                 jbd_trans_finish_callback(journal,
1734                                 trans,
1735                                 block_rec,
1736                                 abort,
1737                                 false);
1738                 TAILQ_REMOVE(&trans->buf_queue, jbd_buf, buf_node);
1739                 free(jbd_buf);
1740         }
1741         RB_FOREACH_SAFE(rec, jbd_revoke_tree, &trans->revoke_root,
1742                           tmp2) {
1743                 RB_REMOVE(jbd_revoke_tree, &trans->revoke_root, rec);
1744                 free(rec);
1745         }
1746         LIST_FOREACH_SAFE(block_rec, &trans->tbrec_list, tbrec_node,
1747                           tmp3) {
1748                 jbd_trans_remove_block_rec(journal, block_rec, trans);
1749         }
1750
1751         free(trans);
1752 }
1753
1754 /**@brief  Write commit block for a transaction
1755  * @param  trans transaction
1756  * @return standard error code*/
1757 static int jbd_trans_write_commit_block(struct jbd_trans *trans)
1758 {
1759         int rc;
1760         struct ext4_block block;
1761         struct jbd_commit_header *header;
1762         uint32_t commit_iblock, orig_commit_iblock;
1763         struct jbd_journal *journal = trans->journal;
1764
1765         commit_iblock = jbd_journal_alloc_block(journal, trans);
1766         orig_commit_iblock = commit_iblock;
1767         commit_iblock++;
1768         wrap(&journal->jbd_fs->sb, commit_iblock);
1769
1770         /* To prevent accidental reference to stale journalling metadata. */
1771         if (orig_commit_iblock < commit_iblock) {
1772                 rc = jbd_block_get_noread(journal->jbd_fs, &block, commit_iblock);
1773                 if (rc != EOK)
1774                         return rc;
1775
1776                 memset(block.data, 0, journal->block_size);
1777                 ext4_bcache_set_dirty(block.buf);
1778                 ext4_bcache_set_flag(block.buf, BC_TMP);
1779                 rc = jbd_block_set(journal->jbd_fs, &block);
1780                 if (rc != EOK)
1781                         return rc;
1782         }
1783
1784         rc = jbd_block_get_noread(journal->jbd_fs, &block, orig_commit_iblock);
1785         if (rc != EOK)
1786                 return rc;
1787
1788         header = (struct jbd_commit_header *)block.data;
1789         jbd_set32(&header->header, magic, JBD_MAGIC_NUMBER);
1790         jbd_set32(&header->header, blocktype, JBD_COMMIT_BLOCK);
1791         jbd_set32(&header->header, sequence, trans->trans_id);
1792
1793         if (JBD_HAS_INCOMPAT_FEATURE(&journal->jbd_fs->sb,
1794                                 JBD_FEATURE_COMPAT_CHECKSUM)) {
1795                 jbd_set32(header, chksum_type, JBD_CRC32_CHKSUM);
1796                 jbd_set32(header, chksum_size, JBD_CRC32_CHKSUM_SIZE);
1797                 jbd_set32(header, chksum[0], trans->data_csum);
1798         }
1799         jbd_commit_csum_set(journal->jbd_fs, header);
1800         ext4_bcache_set_dirty(block.buf);
1801         ext4_bcache_set_flag(block.buf, BC_TMP);
1802         rc = jbd_block_set(journal->jbd_fs, &block);
1803         return rc;
1804 }
1805
1806 /**@brief  Write descriptor block for a transaction
1807  * @param  journal current journal session
1808  * @param  trans transaction
1809  * @return standard error code*/
1810 static int jbd_journal_prepare(struct jbd_journal *journal,
1811                                struct jbd_trans *trans)
1812 {
1813         int rc = EOK, i = 0;
1814         struct ext4_block desc_block = EXT4_BLOCK_ZERO(),
1815                           data_block = EXT4_BLOCK_ZERO();
1816         int32_t tag_tbl_size = 0;
1817         uint32_t desc_iblock = 0;
1818         uint32_t data_iblock = 0;
1819         char *tag_start = NULL, *tag_ptr = NULL;
1820         struct jbd_buf *jbd_buf, *tmp;
1821         struct ext4_fs *fs = journal->jbd_fs->inode_ref.fs;
1822         uint32_t checksum = EXT4_CRC32_INIT;
1823         struct jbd_bhdr *bhdr = NULL;
1824         void *data;
1825
1826         /* Try to remove any non-dirty buffers from the tail of
1827          * buf_queue. */
1828         TAILQ_FOREACH_REVERSE_SAFE(jbd_buf, &trans->buf_queue,
1829                         jbd_trans_buf, buf_node, tmp) {
1830                 struct jbd_revoke_rec tmp_rec = {
1831                         .lba = jbd_buf->block_rec->lba
1832                 };
1833                 /* We stop the iteration when we find a dirty buffer. */
1834                 if (ext4_bcache_test_flag(jbd_buf->block.buf,
1835                                         BC_DIRTY))
1836                         break;
1837
1838                 TAILQ_REMOVE(&jbd_buf->block_rec->dirty_buf_queue,
1839                         jbd_buf,
1840                         dirty_buf_node);
1841
1842                 jbd_buf->block.buf->end_write = NULL;
1843                 jbd_buf->block.buf->end_write_arg = NULL;
1844                 jbd_trans_finish_callback(journal,
1845                                 trans,
1846                                 jbd_buf->block_rec,
1847                                 true,
1848                                 RB_FIND(jbd_revoke_tree,
1849                                         &trans->revoke_root,
1850                                         &tmp_rec));
1851                 jbd_trans_remove_block_rec(journal,
1852                                         jbd_buf->block_rec, trans);
1853                 trans->data_cnt--;
1854
1855                 ext4_block_set(fs->bdev, &jbd_buf->block);
1856                 TAILQ_REMOVE(&trans->buf_queue, jbd_buf, buf_node);
1857                 free(jbd_buf);
1858         }
1859
1860         TAILQ_FOREACH_SAFE(jbd_buf, &trans->buf_queue, buf_node, tmp) {
1861                 struct tag_info tag_info;
1862                 bool uuid_exist = false;
1863                 struct jbd_revoke_rec tmp_rec = {
1864                         .lba = jbd_buf->block_rec->lba
1865                 };
1866                 if (!ext4_bcache_test_flag(jbd_buf->block.buf,
1867                                            BC_DIRTY)) {
1868                         TAILQ_REMOVE(&jbd_buf->block_rec->dirty_buf_queue,
1869                                         jbd_buf,
1870                                         dirty_buf_node);
1871
1872                         jbd_buf->block.buf->end_write = NULL;
1873                         jbd_buf->block.buf->end_write_arg = NULL;
1874
1875                         /* The buffer has not been modified, just release
1876                          * that jbd_buf. */
1877                         jbd_trans_finish_callback(journal,
1878                                         trans,
1879                                         jbd_buf->block_rec,
1880                                         true,
1881                                         RB_FIND(jbd_revoke_tree,
1882                                                 &trans->revoke_root,
1883                                                 &tmp_rec));
1884                         jbd_trans_remove_block_rec(journal,
1885                                         jbd_buf->block_rec, trans);
1886                         trans->data_cnt--;
1887
1888                         ext4_block_set(fs->bdev, &jbd_buf->block);
1889                         TAILQ_REMOVE(&trans->buf_queue, jbd_buf, buf_node);
1890                         free(jbd_buf);
1891                         continue;
1892                 }
1893                 checksum = jbd_block_csum(journal->jbd_fs,
1894                                           jbd_buf->block.data,
1895                                           checksum,
1896                                           trans->trans_id);
1897 again:
1898                 if (!desc_iblock) {
1899                         desc_iblock = jbd_journal_alloc_block(journal, trans);
1900                         rc = jbd_block_get_noread(journal->jbd_fs, &desc_block, desc_iblock);
1901                         if (rc != EOK)
1902                                 break;
1903
1904                         bhdr = (struct jbd_bhdr *)desc_block.data;
1905                         jbd_set32(bhdr, magic, JBD_MAGIC_NUMBER);
1906                         jbd_set32(bhdr, blocktype, JBD_DESCRIPTOR_BLOCK);
1907                         jbd_set32(bhdr, sequence, trans->trans_id);
1908
1909                         tag_start = (char *)(bhdr + 1);
1910                         tag_ptr = tag_start;
1911                         uuid_exist = true;
1912                         tag_tbl_size = journal->block_size -
1913                                 sizeof(struct jbd_bhdr);
1914
1915                         if (jbd_has_csum(&journal->jbd_fs->sb))
1916                                 tag_tbl_size -= sizeof(struct jbd_block_tail);
1917
1918                         if (!trans->start_iblock)
1919                                 trans->start_iblock = desc_iblock;
1920
1921                         ext4_bcache_set_dirty(desc_block.buf);
1922                         ext4_bcache_set_flag(desc_block.buf, BC_TMP);
1923                 }
1924                 tag_info.block = jbd_buf->block.lb_id;
1925                 tag_info.uuid_exist = uuid_exist;
1926                 if (i == trans->data_cnt - 1)
1927                         tag_info.last_tag = true;
1928                 else
1929                         tag_info.last_tag = false;
1930
1931                 tag_info.checksum = checksum;
1932
1933                 if (uuid_exist)
1934                         memcpy(tag_info.uuid, journal->jbd_fs->sb.uuid,
1935                                         UUID_SIZE);
1936
1937                 rc = jbd_write_block_tag(journal->jbd_fs,
1938                                 tag_ptr,
1939                                 tag_tbl_size,
1940                                 &tag_info);
1941                 if (rc != EOK) {
1942                         jbd_meta_csum_set(journal->jbd_fs, bhdr);
1943                         desc_iblock = 0;
1944                         rc = jbd_block_set(journal->jbd_fs, &desc_block);
1945                         if (rc != EOK)
1946                                 break;
1947
1948                         goto again;
1949                 }
1950
1951                 data_iblock = jbd_journal_alloc_block(journal, trans);
1952                 rc = jbd_block_get_noread(journal->jbd_fs, &data_block, data_iblock);
1953                 if (rc != EOK) {
1954                         desc_iblock = 0;
1955                         ext4_bcache_clear_dirty(desc_block.buf);
1956                         jbd_block_set(journal->jbd_fs, &desc_block);
1957                         break;
1958                 }
1959
1960                 data = data_block.data;
1961                 memcpy(data, jbd_buf->block.data,
1962                         journal->block_size);
1963                 ext4_bcache_set_dirty(data_block.buf);
1964                 ext4_bcache_set_flag(data_block.buf, BC_TMP);
1965                 rc = jbd_block_set(journal->jbd_fs, &data_block);
1966                 if (rc != EOK) {
1967                         desc_iblock = 0;
1968                         ext4_bcache_clear_dirty(desc_block.buf);
1969                         jbd_block_set(journal->jbd_fs, &desc_block);
1970                         break;
1971                 }
1972                 jbd_buf->jbd_lba = data_iblock;
1973
1974                 tag_ptr += tag_info.tag_bytes;
1975                 tag_tbl_size -= tag_info.tag_bytes;
1976
1977                 i++;
1978         }
1979         if (rc == EOK && desc_iblock) {
1980                 jbd_meta_csum_set(journal->jbd_fs,
1981                                 (struct jbd_bhdr *)bhdr);
1982                 trans->data_csum = checksum;
1983                 rc = jbd_block_set(journal->jbd_fs, &desc_block);
1984         }
1985
1986         return rc;
1987 }
1988
1989 /**@brief  Write revoke block for a transaction
1990  * @param  journal current journal session
1991  * @param  trans transaction
1992  * @return standard error code*/
1993 static int
1994 jbd_journal_prepare_revoke(struct jbd_journal *journal,
1995                            struct jbd_trans *trans)
1996 {
1997         int rc = EOK, i = 0;
1998         struct ext4_block desc_block = EXT4_BLOCK_ZERO();
1999         int32_t tag_tbl_size = 0;
2000         uint32_t desc_iblock = 0;
2001         char *blocks_entry = NULL;
2002         struct jbd_revoke_rec *rec, *tmp;
2003         struct jbd_revoke_header *header = NULL;
2004         int32_t record_len = 4;
2005         struct jbd_bhdr *bhdr = NULL;
2006
2007         if (JBD_HAS_INCOMPAT_FEATURE(&journal->jbd_fs->sb,
2008                                      JBD_FEATURE_INCOMPAT_64BIT))
2009                 record_len = 8;
2010
2011         RB_FOREACH_SAFE(rec, jbd_revoke_tree, &trans->revoke_root,
2012                           tmp) {
2013 again:
2014                 if (!desc_iblock) {
2015                         desc_iblock = jbd_journal_alloc_block(journal, trans);
2016                         rc = jbd_block_get_noread(journal->jbd_fs, &desc_block,
2017                                                   desc_iblock);
2018                         if (rc != EOK)
2019                                 break;
2020
2021                         bhdr = (struct jbd_bhdr *)desc_block.data;
2022                         jbd_set32(bhdr, magic, JBD_MAGIC_NUMBER);
2023                         jbd_set32(bhdr, blocktype, JBD_REVOKE_BLOCK);
2024                         jbd_set32(bhdr, sequence, trans->trans_id);
2025
2026                         header = (struct jbd_revoke_header *)bhdr;
2027                         blocks_entry = (char *)(header + 1);
2028                         tag_tbl_size = journal->block_size -
2029                                 sizeof(struct jbd_revoke_header);
2030
2031                         if (jbd_has_csum(&journal->jbd_fs->sb))
2032                                 tag_tbl_size -= sizeof(struct jbd_block_tail);
2033
2034                         if (!trans->start_iblock)
2035                                 trans->start_iblock = desc_iblock;
2036
2037                         ext4_bcache_set_dirty(desc_block.buf);
2038                         ext4_bcache_set_flag(desc_block.buf, BC_TMP);
2039                 }
2040
2041                 if (tag_tbl_size < record_len) {
2042                         jbd_set32(header, count,
2043                                   journal->block_size - tag_tbl_size);
2044                         jbd_meta_csum_set(journal->jbd_fs, bhdr);
2045                         bhdr = NULL;
2046                         desc_iblock = 0;
2047                         header = NULL;
2048                         rc = jbd_block_set(journal->jbd_fs, &desc_block);
2049                         if (rc != EOK)
2050                                 break;
2051
2052                         goto again;
2053                 }
2054                 if (record_len == 8) {
2055                         uint64_t *blocks =
2056                                 (uint64_t *)blocks_entry;
2057                         *blocks = to_be64(rec->lba);
2058                 } else {
2059                         uint32_t *blocks =
2060                                 (uint32_t *)blocks_entry;
2061                         *blocks = to_be32((uint32_t)rec->lba);
2062                 }
2063                 blocks_entry += record_len;
2064                 tag_tbl_size -= record_len;
2065
2066                 i++;
2067         }
2068         if (rc == EOK && desc_iblock) {
2069                 if (header != NULL)
2070                         jbd_set32(header, count,
2071                                   journal->block_size - tag_tbl_size);
2072
2073                 jbd_meta_csum_set(journal->jbd_fs, bhdr);
2074                 rc = jbd_block_set(journal->jbd_fs, &desc_block);
2075         }
2076
2077         return rc;
2078 }
2079
2080 /**@brief  Put references of block descriptors in a transaction.
2081  * @param  journal current journal session
2082  * @param  trans transaction*/
2083 void jbd_journal_cp_trans(struct jbd_journal *journal, struct jbd_trans *trans)
2084 {
2085         struct jbd_buf *jbd_buf, *tmp;
2086         struct ext4_fs *fs = journal->jbd_fs->inode_ref.fs;
2087         TAILQ_FOREACH_SAFE(jbd_buf, &trans->buf_queue, buf_node,
2088                         tmp) {
2089                 struct ext4_block block = jbd_buf->block;
2090                 ext4_block_set(fs->bdev, &block);
2091         }
2092 }
2093
2094 /**@brief  Update the start block of the journal when
2095  *         all the contents in a transaction reach the disk.*/
2096 static void jbd_trans_end_write(struct ext4_bcache *bc __unused,
2097                           struct ext4_buf *buf,
2098                           int res,
2099                           void *arg)
2100 {
2101         struct jbd_buf *jbd_buf = arg;
2102         struct jbd_trans *trans = jbd_buf->trans;
2103         struct jbd_block_rec *block_rec = jbd_buf->block_rec;
2104         struct jbd_journal *journal = trans->journal;
2105         bool first_in_queue =
2106                 trans == TAILQ_FIRST(&journal->cp_queue);
2107         if (res != EOK)
2108                 trans->error = res;
2109
2110         TAILQ_REMOVE(&trans->buf_queue, jbd_buf, buf_node);
2111         TAILQ_REMOVE(&block_rec->dirty_buf_queue,
2112                         jbd_buf,
2113                         dirty_buf_node);
2114
2115         jbd_trans_finish_callback(journal,
2116                         trans,
2117                         jbd_buf->block_rec,
2118                         false,
2119                         false);
2120         if (block_rec->trans == trans && buf) {
2121                 /* Clear the end_write and end_write_arg fields. */
2122                 buf->end_write = NULL;
2123                 buf->end_write_arg = NULL;
2124         }
2125
2126         free(jbd_buf);
2127
2128         trans->written_cnt++;
2129         if (trans->written_cnt == trans->data_cnt) {
2130                 /* If it is the first transaction on checkpoint queue,
2131                  * we will shift the start of the journal to the next
2132                  * transaction, and remove subsequent written
2133                  * transactions from checkpoint queue until we find
2134                  * an unwritten one. */
2135                 if (first_in_queue) {
2136                         journal->start = trans->start_iblock +
2137                                 trans->alloc_blocks;
2138                         wrap(&journal->jbd_fs->sb, journal->start);
2139                         journal->trans_id = trans->trans_id + 1;
2140                         TAILQ_REMOVE(&journal->cp_queue, trans, trans_node);
2141                         jbd_journal_free_trans(journal, trans, false);
2142
2143                         jbd_journal_purge_cp_trans(journal, false, true);
2144                         jbd_journal_write_sb(journal);
2145                         jbd_write_sb(journal->jbd_fs);
2146                 }
2147         }
2148 }
2149
2150 /**@brief  Commit a transaction to the journal immediately.
2151  * @param  journal current journal session
2152  * @param  trans transaction
2153  * @return standard error code*/
2154 static int __jbd_journal_commit_trans(struct jbd_journal *journal,
2155                                       struct jbd_trans *trans)
2156 {
2157         int rc = EOK;
2158         uint32_t last = journal->last;
2159         struct jbd_revoke_rec *rec, *tmp;
2160
2161         trans->trans_id = journal->alloc_trans_id;
2162         rc = jbd_journal_prepare(journal, trans);
2163         if (rc != EOK)
2164                 goto Finish;
2165
2166         rc = jbd_journal_prepare_revoke(journal, trans);
2167         if (rc != EOK)
2168                 goto Finish;
2169
2170         if (TAILQ_EMPTY(&trans->buf_queue) &&
2171             RB_EMPTY(&trans->revoke_root)) {
2172                 /* Since there are no entries in both buffer list
2173                  * and revoke entry list, we do not consider trans as
2174                  * complete transaction and just return EOK.*/
2175                 jbd_journal_free_trans(journal, trans, false);
2176                 goto Finish;
2177         }
2178
2179         rc = jbd_trans_write_commit_block(trans);
2180         if (rc != EOK)
2181                 goto Finish;
2182
2183         journal->alloc_trans_id++;
2184
2185         /* Complete the checkpoint of buffers which are revoked. */
2186         RB_FOREACH_SAFE(rec, jbd_revoke_tree, &trans->revoke_root,
2187                         tmp) {
2188                 struct jbd_block_rec *block_rec =
2189                         jbd_trans_block_rec_lookup(journal, rec->lba);
2190                 struct jbd_buf *jbd_buf = NULL;
2191                 if (block_rec)
2192                         jbd_buf = TAILQ_LAST(&block_rec->dirty_buf_queue,
2193                                         jbd_buf_dirty);
2194                 if (jbd_buf) {
2195                         struct ext4_buf *buf;
2196                         struct ext4_block block = EXT4_BLOCK_ZERO();
2197                         /*
2198                          * We do this to reset the ext4_buf::end_write and
2199                          * ext4_buf::end_write_arg fields so that the checkpoint
2200                          * callback won't be triggered again.
2201                          */
2202                         buf = ext4_bcache_find_get(journal->jbd_fs->bdev->bc,
2203                                         &block,
2204                                         jbd_buf->block_rec->lba);
2205                         jbd_trans_end_write(journal->jbd_fs->bdev->bc,
2206                                         buf,
2207                                         EOK,
2208                                         jbd_buf);
2209                         if (buf)
2210                                 ext4_block_set(journal->jbd_fs->bdev, &block);
2211                 }
2212         }
2213
2214         if (TAILQ_EMPTY(&journal->cp_queue)) {
2215                 /*
2216                  * This transaction is going to be the first object in the
2217                  * checkpoint queue.
2218                  * When the first transaction in checkpoint queue is completely
2219                  * written to disk, we shift the tail of the log to right.
2220                  */
2221                 if (trans->data_cnt) {
2222                         journal->start = trans->start_iblock;
2223                         wrap(&journal->jbd_fs->sb, journal->start);
2224                         journal->trans_id = trans->trans_id;
2225                         jbd_journal_write_sb(journal);
2226                         jbd_write_sb(journal->jbd_fs);
2227                         TAILQ_INSERT_TAIL(&journal->cp_queue, trans,
2228                                         trans_node);
2229                         jbd_journal_cp_trans(journal, trans);
2230                 } else {
2231                         journal->start = trans->start_iblock +
2232                                 trans->alloc_blocks;
2233                         wrap(&journal->jbd_fs->sb, journal->start);
2234                         journal->trans_id = trans->trans_id + 1;
2235                         jbd_journal_write_sb(journal);
2236                         jbd_journal_free_trans(journal, trans, false);
2237                 }
2238         } else {
2239                 /* No need to do anything to the JBD superblock. */
2240                 TAILQ_INSERT_TAIL(&journal->cp_queue, trans,
2241                                 trans_node);
2242                 if (trans->data_cnt)
2243                         jbd_journal_cp_trans(journal, trans);
2244         }
2245 Finish:
2246         if (rc != EOK && rc != ENOSPC) {
2247                 journal->last = last;
2248                 jbd_journal_free_trans(journal, trans, true);
2249         }
2250         return rc;
2251 }
2252
2253 /**@brief  Allocate a new transaction
2254  * @param  journal current journal session
2255  * @return transaction allocated*/
2256 struct jbd_trans *
2257 jbd_journal_new_trans(struct jbd_journal *journal)
2258 {
2259         struct jbd_trans *trans = NULL;
2260         trans = calloc(1, sizeof(struct jbd_trans));
2261         if (!trans)
2262                 return NULL;
2263
2264         /* We will assign a trans_id to this transaction,
2265          * once it has been committed.*/
2266         trans->journal = journal;
2267         trans->data_csum = EXT4_CRC32_INIT;
2268         trans->error = EOK;
2269         TAILQ_INIT(&trans->buf_queue);
2270         return trans;
2271 }
2272
2273 /**@brief  Commit a transaction to the journal immediately.
2274  * @param  journal current journal session
2275  * @param  trans transaction
2276  * @return standard error code*/
2277 int jbd_journal_commit_trans(struct jbd_journal *journal,
2278                              struct jbd_trans *trans)
2279 {
2280         int r = EOK;
2281         r = __jbd_journal_commit_trans(journal, trans);
2282         return r;
2283 }
2284
2285 /**
2286  * @}
2287  */