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