lwext4/ext4_journal.c

   1 /**
   2  * @file  ext4_journal.c
   3  * @brief Journalling
   4  */
   5
   6 #include "ext4_config.h"
   7 #include "ext4_types.h"
   8 #include "ext4_fs.h"
   9 #include "ext4_super.h"
  10 #include "ext4_errno.h"
  11 #include "ext4_blockdev.h"
  12 #include "ext4_crc32c.h"
  13 #include "ext4_debug.h"
  14 #include "tree.h"
  15
  16 #include <string.h>
  17 #include <stdlib.h>
  18
  19 struct revoke_entry {
  20         ext4_fsblk_t block;
  21         uint32_t trans_id;
  22         RB_ENTRY(revoke_entry) revoke_node;
  23 };
  24
  25 struct recover_info {
  26         uint32_t start_trans_id;
  27         uint32_t last_trans_id;
  28         uint32_t this_trans_id;
  29         RB_HEAD(jbd_revoke, revoke_entry) revoke_root;
  30 };
  31
  32 struct replay_arg {
  33         struct recover_info *info;
  34         uint32_t *this_block;
  35         uint32_t this_trans_id;
  36 };
  37
  38 static int
  39 jbd_revoke_entry_cmp(struct revoke_entry *a, struct revoke_entry *b)
  40 {
  41         if (a->block > b->block)
  42                 return 1;
  43         else if (a->block < b->block)
  44                 return -1;
  45         return 0;
  46 }
  47
  48 RB_GENERATE_INTERNAL(jbd_revoke, revoke_entry, revoke_node,
  49                      jbd_revoke_entry_cmp, static inline)
  50
  51 #define jbd_alloc_revoke_entry() calloc(1, sizeof(struct revoke_entry))
  52 #define jbd_free_revoke_entry(addr) free(addr)
  53
  54 int jbd_inode_bmap(struct jbd_fs *jbd_fs,
  55                    ext4_lblk_t iblock,
  56                    ext4_fsblk_t *fblock);
  57
  58 int jbd_sb_write(struct jbd_fs *jbd_fs, struct jbd_sb *s)
  59 {
  60         int rc;
  61         struct ext4_fs *fs = jbd_fs->inode_ref.fs;
  62         uint64_t offset;
  63         ext4_fsblk_t fblock;
  64         rc = jbd_inode_bmap(jbd_fs, 0, &fblock);
  65         if (rc != EOK)
  66                 return rc;
  67
  68         offset = fblock * ext4_sb_get_block_size(&fs->sb);
  69         return ext4_block_writebytes(fs->bdev, offset, s,
  70                                      EXT4_SUPERBLOCK_SIZE);
  71 }
  72
  73 int jbd_sb_read(struct jbd_fs *jbd_fs, struct jbd_sb *s)
  74 {
  75         int rc;
  76         struct ext4_fs *fs = jbd_fs->inode_ref.fs;
  77         uint64_t offset;
  78         ext4_fsblk_t fblock;
  79         rc = jbd_inode_bmap(jbd_fs, 0, &fblock);
  80         if (rc != EOK)
  81                 return rc;
  82
  83         offset = fblock * ext4_sb_get_block_size(&fs->sb);
  84         return ext4_block_readbytes(fs->bdev, offset, s,
  85                                     EXT4_SUPERBLOCK_SIZE);
  86 }
  87
  88 static bool jbd_verify_sb(struct jbd_sb *sb)
  89 {
  90         struct jbd_bhdr *header = &sb->header;
  91         if (jbd_get32(header, magic) != JBD_MAGIC_NUMBER)
  92                 return false;
  93
  94         if (jbd_get32(header, blocktype) != JBD_SUPERBLOCK &&
  95             jbd_get32(header, blocktype) != JBD_SUPERBLOCK_V2)
  96                 return false;
  97
  98         return true;
  99 }
 100
 101 int jbd_get_fs(struct ext4_fs *fs,
 102                struct jbd_fs *jbd_fs)
 103 {
 104         int rc;
 105         uint32_t journal_ino;
 106
 107         memset(jbd_fs, 0, sizeof(struct jbd_fs));
 108         journal_ino = ext4_get32(&fs->sb, journal_inode_number);
 109
 110         rc = ext4_fs_get_inode_ref(fs,
 111                                    journal_ino,
 112                                    &jbd_fs->inode_ref);
 113         if (rc != EOK) {
 114                 memset(jbd_fs, 0, sizeof(struct jbd_fs));
 115                 return rc;
 116         }
 117         rc = jbd_sb_read(jbd_fs, &jbd_fs->sb);
 118         if (rc != EOK) {
 119                 memset(jbd_fs, 0, sizeof(struct jbd_fs));
 120                 ext4_fs_put_inode_ref(&jbd_fs->inode_ref);
 121         }
 122
 123         return rc;
 124 }
 125
 126 int jbd_put_fs(struct jbd_fs *jbd_fs)
 127 {
 128         int rc;
 129         if (jbd_fs->dirty)
 130                 jbd_sb_write(jbd_fs, &jbd_fs->sb);
 131
 132         rc = ext4_fs_put_inode_ref(&jbd_fs->inode_ref);
 133         return rc;
 134 }
 135
 136 int jbd_inode_bmap(struct jbd_fs *jbd_fs,
 137                    ext4_lblk_t iblock,
 138                    ext4_fsblk_t *fblock)
 139 {
 140         int rc = ext4_fs_get_inode_data_block_index(
 141                         &jbd_fs->inode_ref,
 142                         iblock,
 143                         fblock,
 144                         false);
 145         return rc;
 146 }
 147
 148 int jbd_block_get(struct jbd_fs *jbd_fs,
 149                   struct ext4_block *block,
 150                   ext4_fsblk_t fblock)
 151 {
 152         /* TODO: journal device. */
 153         int rc;
 154         ext4_lblk_t iblock = (ext4_lblk_t)fblock;
 155         rc = jbd_inode_bmap(jbd_fs, iblock,
 156                             &fblock);
 157         if (rc != EOK)
 158                 return rc;
 159
 160         struct ext4_blockdev *bdev = jbd_fs->inode_ref.fs->bdev;
 161         rc = ext4_block_get(bdev, block, fblock);
 162         return rc;
 163 }
 164
 165 int jbd_block_get_noread(struct jbd_fs *jbd_fs,
 166                          struct ext4_block *block,
 167                          ext4_fsblk_t fblock)
 168 {
 169         /* TODO: journal device. */
 170         int rc;
 171         ext4_lblk_t iblock = (ext4_lblk_t)fblock;
 172         rc = jbd_inode_bmap(jbd_fs, iblock,
 173                             &fblock);
 174         if (rc != EOK)
 175                 return rc;
 176
 177         struct ext4_blockdev *bdev = jbd_fs->inode_ref.fs->bdev;
 178         rc = ext4_block_get_noread(bdev, block, fblock);
 179         return rc;
 180 }
 181
 182 int jbd_block_set(struct jbd_fs *jbd_fs,
 183                   struct ext4_block *block)
 184 {
 185         return ext4_block_set(jbd_fs->inode_ref.fs->bdev,
 186                               block);
 187 }
 188
 189 /*
 190  * helper functions to deal with 32 or 64bit block numbers.
 191  */
 192 int jbd_tag_bytes(struct jbd_fs *jbd_fs)
 193 {
 194         int size;
 195
 196         if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 197                                      JBD_FEATURE_INCOMPAT_CSUM_V3))
 198                 return sizeof(struct jbd_block_tag3);
 199
 200         size = sizeof(struct jbd_block_tag);
 201
 202         if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 203                                      JBD_FEATURE_INCOMPAT_CSUM_V2))
 204                 size += sizeof(uint16_t);
 205
 206         if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 207                                      JBD_FEATURE_INCOMPAT_64BIT))
 208                 return size;
 209
 210         return size - sizeof(uint32_t);
 211 }
 212
 213 static void
 214 jbd_extract_block_tag(struct jbd_fs *jbd_fs,
 215                       uint32_t tag_bytes,
 216                       void *__tag,
 217                       ext4_fsblk_t *block,
 218                       bool *uuid_exist,
 219                       uint8_t *uuid,
 220                       bool *last_tag)
 221 {
 222         char *uuid_start;
 223         *uuid_exist = false;
 224         *last_tag = false;
 225         if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 226                                      JBD_FEATURE_INCOMPAT_CSUM_V3)) {
 227                 struct jbd_block_tag3 *tag = __tag;
 228                 *block = jbd_get32(tag, blocknr);
 229                 if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 230                                              JBD_FEATURE_INCOMPAT_64BIT))
 231                          *block |= (uint64_t)jbd_get32(tag, blocknr_high) << 32;
 232
 233                 if (jbd_get32(tag, flags) & JBD_FLAG_ESCAPE)
 234                         *block = 0;
 235
 236                 if (!(jbd_get32(tag, flags) & JBD_FLAG_SAME_UUID)) {
 237                         uuid_start = (char *)tag + tag_bytes;
 238                         *uuid_exist = true;
 239                         memcpy(uuid, uuid_start, UUID_SIZE);
 240                 }
 241
 242                 if (jbd_get32(tag, flags) & JBD_FLAG_LAST_TAG)
 243                         *last_tag = true;
 244
 245         } else {
 246                 struct jbd_block_tag *tag = __tag;
 247                 *block = jbd_get32(tag, blocknr);
 248                 if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 249                                              JBD_FEATURE_INCOMPAT_64BIT))
 250                          *block |= (uint64_t)jbd_get32(tag, blocknr_high) << 32;
 251
 252                 if (jbd_get16(tag, flags) & JBD_FLAG_ESCAPE)
 253                         *block = 0;
 254
 255                 if (!(jbd_get16(tag, flags) & JBD_FLAG_SAME_UUID)) {
 256                         uuid_start = (char *)tag + tag_bytes;
 257                         *uuid_exist = true;
 258                         memcpy(uuid, uuid_start, UUID_SIZE);
 259                 }
 260
 261                 if (jbd_get16(tag, flags) & JBD_FLAG_LAST_TAG)
 262                         *last_tag = true;
 263
 264         }
 265 }
 266
 267 static void
 268 jbd_iterate_block_table(struct jbd_fs *jbd_fs,
 269                         void *__tag_start,
 270                         uint32_t tag_tbl_size,
 271                         void (*func)(struct jbd_fs * jbd_fs,
 272                                         ext4_fsblk_t block,
 273                                         uint8_t *uuid,
 274                                         void *arg),
 275                         void *arg)
 276 {
 277         ext4_fsblk_t block = 0;
 278         uint8_t uuid[UUID_SIZE];
 279         char *tag_start, *tag_ptr;
 280         uint32_t tag_bytes = jbd_tag_bytes(jbd_fs);
 281         tag_start = __tag_start;
 282         tag_ptr = tag_start;
 283
 284         if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 285                                      JBD_FEATURE_INCOMPAT_CSUM_V2) ||
 286             JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 287                                      JBD_FEATURE_INCOMPAT_CSUM_V3))
 288                 tag_tbl_size -= sizeof(struct jbd_block_tail);
 289
 290         while (tag_ptr - tag_start + tag_bytes <= tag_tbl_size) {
 291                 bool uuid_exist;
 292                 bool last_tag;
 293                 jbd_extract_block_tag(jbd_fs,
 294                                       tag_bytes,
 295                                       tag_ptr,
 296                                       &block,
 297                                       &uuid_exist,
 298                                       uuid,
 299                                       &last_tag);
 300                 if (func)
 301                         func(jbd_fs, block, uuid, arg);
 302
 303                 if (last_tag)
 304                         break;
 305
 306                 tag_ptr += tag_bytes;
 307                 if (uuid_exist)
 308                         tag_ptr += UUID_SIZE;
 309
 310         }
 311 }
 312
 313 static void jbd_display_block_tags(struct jbd_fs *jbd_fs,
 314                                    ext4_fsblk_t block,
 315                                    uint8_t *uuid,
 316                                    void *arg)
 317 {
 318         uint32_t *iblock = arg;
 319         ext4_dbg(DEBUG_JBD, "Block in block_tag: %" PRIu64 "\n", block);
 320         (*iblock)++;
 321         (void)jbd_fs;
 322         (void)uuid;
 323         return;
 324 }
 325
 326 static struct revoke_entry *
 327 jbd_revoke_entry_lookup(struct recover_info *info, ext4_fsblk_t block)
 328 {
 329         struct revoke_entry tmp = {
 330                 .block = block
 331         };
 332
 333         return RB_FIND(jbd_revoke, &info->revoke_root, &tmp);
 334 }
 335
 336 static void jbd_replay_block_tags(struct jbd_fs *jbd_fs,
 337                                   ext4_fsblk_t block,
 338                                   uint8_t *uuid __unused,
 339                                   void *__arg)
 340 {
 341         int r;
 342         struct replay_arg *arg = __arg;
 343         struct recover_info *info = arg->info;
 344         uint32_t *this_block = arg->this_block;
 345         struct revoke_entry *revoke_entry;
 346         struct ext4_block journal_block, ext4_block;
 347         struct ext4_fs *fs = jbd_fs->inode_ref.fs;
 348
 349         ext4_dbg(DEBUG_JBD,
 350                  "Replaying block in block_tag: %" PRIu64 "\n",
 351                  block);
 352         (*this_block)++;
 353
 354         revoke_entry = jbd_revoke_entry_lookup(info, block);
 355         if (revoke_entry &&
 356             arg->this_trans_id < revoke_entry->trans_id)
 357                 return;
 358
 359         r = jbd_block_get(jbd_fs, &journal_block, *this_block);
 360         if (r != EOK)
 361                 return;
 362
 363         if (block) {
 364                 r = ext4_block_get_noread(fs->bdev, &ext4_block, block);
 365                 if (r != EOK) {
 366                         jbd_block_set(jbd_fs, &journal_block);
 367                         return;
 368                 }
 369
 370                 memcpy(ext4_block.data,
 371                         journal_block.data,
 372                         jbd_get32(&jbd_fs->sb, blocksize));
 373
 374                 ext4_block.dirty = true;
 375                 ext4_block_set(fs->bdev, &ext4_block);
 376         } else {
 377                 uint16_t mount_count, state;
 378                 mount_count = ext4_get16(&fs->sb, mount_count);
 379                 state = ext4_get16(&fs->sb, state);
 380
 381                 memcpy(&fs->sb,
 382                         journal_block.data + EXT4_SUPERBLOCK_OFFSET,
 383                         EXT4_SUPERBLOCK_SIZE);
 384
 385                 /* Mark system as mounted */
 386                 ext4_set16(&fs->sb, state, state);
 387                 r = ext4_sb_write(fs->bdev, &fs->sb);
 388                 if (r != EOK)
 389                         return;
 390
 391                 /*Update mount count*/
 392                 ext4_set16(&fs->sb, mount_count, mount_count);
 393         }
 394
 395         jbd_block_set(jbd_fs, &journal_block);
 396
 397         return;
 398 }
 399
 400 static void jbd_add_revoke_block_tags(struct recover_info *info,
 401                                       ext4_fsblk_t block)
 402 {
 403         struct revoke_entry *revoke_entry;
 404
 405         ext4_dbg(DEBUG_JBD, "Add block %" PRIu64 " to revoke tree\n", block);
 406         revoke_entry = jbd_revoke_entry_lookup(info, block);
 407         if (revoke_entry) {
 408                 revoke_entry->trans_id = info->this_trans_id;
 409                 return;
 410         }
 411
 412         revoke_entry = jbd_alloc_revoke_entry();
 413         ext4_assert(revoke_entry);
 414         revoke_entry->block = block;
 415         revoke_entry->trans_id = info->this_trans_id;
 416         RB_INSERT(jbd_revoke, &info->revoke_root, revoke_entry);
 417
 418         return;
 419 }
 420
 421 static void jbd_destroy_revoke_tree(struct recover_info *info)
 422 {
 423         while (!RB_EMPTY(&info->revoke_root)) {
 424                 struct revoke_entry *revoke_entry =
 425                         RB_MIN(jbd_revoke, &info->revoke_root);
 426                 ext4_assert(revoke_entry);
 427                 RB_REMOVE(jbd_revoke, &info->revoke_root, revoke_entry);
 428                 jbd_free_revoke_entry(revoke_entry);
 429         }
 430 }
 431
 432 /* Make sure we wrap around the log correctly! */
 433 #define wrap(sb, var)                                           \
 434 do {                                                                    \
 435         if (var >= jbd_get32((sb), maxlen))                                     \
 436                 var -= (jbd_get32((sb), maxlen) - jbd_get32((sb), first));      \
 437 } while (0)
 438
 439 #define ACTION_SCAN 0
 440 #define ACTION_REVOKE 1
 441 #define ACTION_RECOVER 2
 442
 443
 444 static void jbd_build_revoke_tree(struct jbd_fs *jbd_fs,
 445                                   struct jbd_bhdr *header,
 446                                   struct recover_info *info)
 447 {
 448         char *blocks_entry;
 449         struct jbd_revoke_header *revoke_hdr =
 450                 (struct jbd_revoke_header *)header;
 451         uint32_t i, nr_entries, record_len = 4;
 452         if (JBD_HAS_INCOMPAT_FEATURE(&jbd_fs->sb,
 453                                      JBD_FEATURE_INCOMPAT_64BIT))
 454                 record_len = 8;
 455
 456         nr_entries = (revoke_hdr->count -
 457                         sizeof(struct jbd_revoke_header)) /
 458                         record_len;
 459
 460         blocks_entry = (char *)(revoke_hdr + 1);
 461
 462         for (i = 0;i < nr_entries;i++) {
 463                 if (record_len == 8) {
 464                         uint64_t *blocks =
 465                                 (uint64_t *)blocks_entry;
 466                         jbd_add_revoke_block_tags(info, *blocks);
 467                 } else {
 468                         uint32_t *blocks =
 469                                 (uint32_t *)blocks_entry;
 470                         jbd_add_revoke_block_tags(info, *blocks);
 471                 }
 472                 blocks_entry += record_len;
 473         }
 474 }
 475
 476 static void jbd_debug_descriptor_block(struct jbd_fs *jbd_fs,
 477                                        struct jbd_bhdr *header,
 478                                        uint32_t *iblock)
 479 {
 480         jbd_iterate_block_table(jbd_fs,
 481                                 header + 1,
 482                                 jbd_get32(&jbd_fs->sb, blocksize) -
 483                                         sizeof(struct jbd_bhdr),
 484                                 jbd_display_block_tags,
 485                                 iblock);
 486 }
 487
 488 static void jbd_replay_descriptor_block(struct jbd_fs *jbd_fs,
 489                                         struct jbd_bhdr *header,
 490                                         struct replay_arg *arg)
 491 {
 492         jbd_iterate_block_table(jbd_fs,
 493                                 header + 1,
 494                                 jbd_get32(&jbd_fs->sb, blocksize) -
 495                                         sizeof(struct jbd_bhdr),
 496                                 jbd_replay_block_tags,
 497                                 arg);
 498 }
 499
 500 int jbd_iterate_log(struct jbd_fs *jbd_fs,
 501                     struct recover_info *info,
 502                     int action)
 503 {
 504         int r = EOK;
 505         bool log_end = false;
 506         struct jbd_sb *sb = &jbd_fs->sb;
 507         uint32_t start_trans_id, this_trans_id;
 508         uint32_t start_block, this_block;
 509
 510         start_trans_id = this_trans_id = jbd_get32(sb, sequence);
 511         start_block = this_block = jbd_get32(sb, start);
 512
 513         ext4_dbg(DEBUG_JBD, "Start of journal at trans id: %" PRIu32 "\n",
 514                             start_trans_id);
 515
 516         while (!log_end) {
 517                 struct ext4_block block;
 518                 struct jbd_bhdr *header;
 519                 if (action != ACTION_SCAN)
 520                         if (this_trans_id > info->last_trans_id) {
 521                                 log_end = true;
 522                                 continue;
 523                         }
 524
 525                 r = jbd_block_get(jbd_fs, &block, this_block);
 526                 if (r != EOK)
 527                         break;
 528
 529                 header = (struct jbd_bhdr *)block.data;
 530                 if (jbd_get32(header, magic) != JBD_MAGIC_NUMBER) {
 531                         jbd_block_set(jbd_fs, &block);
 532                         log_end = true;
 533                         continue;
 534                 }
 535
 536                 if (jbd_get32(header, sequence) != this_trans_id) {
 537                         if (action != ACTION_SCAN)
 538                                 r = EIO;
 539
 540                         jbd_block_set(jbd_fs, &block);
 541                         log_end = true;
 542                         continue;
 543                 }
 544
 545                 switch (jbd_get32(header, blocktype)) {
 546                 case JBD_DESCRIPTOR_BLOCK:
 547                         ext4_dbg(DEBUG_JBD, "Descriptor block: %" PRIu32", "
 548                                             "trans_id: %" PRIu32"\n",
 549                                             this_block, this_trans_id);
 550                         if (action == ACTION_SCAN)
 551                                 jbd_debug_descriptor_block(jbd_fs,
 552                                                 header, &this_block);
 553                         else if (action == ACTION_RECOVER) {
 554                                 struct replay_arg replay_arg;
 555                                 replay_arg.info = info;
 556                                 replay_arg.this_block = &this_block;
 557                                 replay_arg.this_trans_id = this_trans_id;
 558
 559                                 jbd_replay_descriptor_block(jbd_fs,
 560                                                 header, &replay_arg);
 561                         }
 562
 563                         break;
 564                 case JBD_COMMIT_BLOCK:
 565                         ext4_dbg(DEBUG_JBD, "Commit block: %" PRIu32", "
 566                                             "trans_id: %" PRIu32"\n",
 567                                             this_block, this_trans_id);
 568                         this_trans_id++;
 569                         break;
 570                 case JBD_REVOKE_BLOCK:
 571                         ext4_dbg(DEBUG_JBD, "Revoke block: %" PRIu32", "
 572                                             "trans_id: %" PRIu32"\n",
 573                                             this_block, this_trans_id);
 574                         if (action == ACTION_REVOKE) {
 575                                 info->this_trans_id = this_trans_id;
 576                                 jbd_build_revoke_tree(jbd_fs,
 577                                                 header, info);
 578                         }
 579                         break;
 580                 default:
 581                         log_end = true;
 582                         break;
 583                 }
 584                 jbd_block_set(jbd_fs, &block);
 585                 this_block++;
 586                 wrap(sb, this_block);
 587                 if (this_block == start_block)
 588                         log_end = true;
 589
 590         }
 591         ext4_dbg(DEBUG_JBD, "End of journal.\n");
 592         if (r == EOK && action == ACTION_SCAN) {
 593                 info->start_trans_id = start_trans_id;
 594                 if (this_trans_id > start_trans_id)
 595                         info->last_trans_id = this_trans_id - 1;
 596                 else
 597                         info->last_trans_id = this_trans_id;
 598         }
 599
 600         return r;
 601 }
 602
 603 int jbd_recover(struct jbd_fs *jbd_fs)
 604 {
 605         int r;
 606         struct recover_info info;
 607         struct jbd_sb *sb = &jbd_fs->sb;
 608         if (!sb->start)
 609                 return EOK;
 610
 611         RB_INIT(&info.revoke_root);
 612
 613         r = jbd_iterate_log(jbd_fs, &info, ACTION_SCAN);
 614         if (r != EOK)
 615                 return r;
 616
 617         r = jbd_iterate_log(jbd_fs, &info, ACTION_REVOKE);
 618         if (r != EOK)
 619                 return r;
 620
 621         r = jbd_iterate_log(jbd_fs, &info, ACTION_RECOVER);
 622         if (r == EOK) {
 623                 jbd_set32(&jbd_fs->sb, start, 0);
 624                 jbd_fs->dirty = true;
 625         }
 626         jbd_destroy_revoke_tree(&info);
 627         return r;
 628 }