src/lwext4/ext4_fs.c

   1 /*
   2  * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com)
   3  *
   4  *
   5  * HelenOS:
   6  * Copyright (c) 2012 Martin Sucha
   7  * Copyright (c) 2012 Frantisek Princ
   8  * All rights reserved.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  *
  14  * - Redistributions of source code must retain the above copyright
  15  *   notice, this list of conditions and the following disclaimer.
  16  * - Redistributions in binary form must reproduce the above copyright
  17  *   notice, this list of conditions and the following disclaimer in the
  18  *   documentation and/or other materials provided with the distribution.
  19  * - The name of the author may not be used to endorse or promote products
  20  *   derived from this software without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  23  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  24  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  25  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  27  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  28  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  29  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  30  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  31  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32  */
  33 /** @addtogroup lwext4
  34  * @{
  35  */
  36 /**
  37  * @file  ext4_fs.c
  38  * @brief More complex filesystem functions.
  39  */
  40
  41 #include <ext4_config.h>
  42 #include <ext4_types.h>
  43 #include <ext4_fs.h>
  44 #include <ext4_errno.h>
  45 #include <ext4_blockdev.h>
  46 #include <ext4_super.h>
  47 #include <ext4_debug.h>
  48 #include <ext4_block_group.h>
  49 #include <ext4_balloc.h>
  50 #include <ext4_bitmap.h>
  51 #include <ext4_inode.h>
  52 #include <ext4_ialloc.h>
  53 #include <string.h>
  54
  55 int ext4_fs_init(struct ext4_fs *fs, struct ext4_blockdev *bdev)
  56 {
  57     int r, i;
  58     uint16_t tmp;
  59     uint32_t bsize;
  60     bool read_only = false;
  61
  62     ext4_assert(fs && bdev);
  63
  64     fs->bdev = bdev;
  65
  66     r = ext4_sb_read(fs->bdev, &fs->sb);
  67     if(r != EOK)
  68         return r;
  69
  70     if(!ext4_sb_check(&fs->sb))
  71         return ENOTSUP;
  72
  73     bsize = ext4_sb_get_block_size(&fs->sb);
  74     if (bsize > EXT4_MAX_BLOCK_SIZE)
  75         return ENXIO;
  76
  77     r = ext4_fs_check_features(fs, &read_only);
  78     if(r != EOK)
  79         return r;
  80
  81     if(read_only)
  82         return ENOTSUP;
  83
  84     /* Compute limits for indirect block levels */
  85     uint32_t blocks_id = bsize / sizeof(uint32_t);
  86
  87     fs->inode_block_limits[0] = EXT4_INODE_DIRECT_BLOCK_COUNT;
  88     fs->inode_blocks_per_level[0] = 1;
  89
  90     for (i = 1; i < 4; i++) {
  91         fs->inode_blocks_per_level[i] = fs->inode_blocks_per_level[i - 1] *
  92                 blocks_id;
  93         fs->inode_block_limits[i] = fs->inode_block_limits[i - 1] +
  94                 fs->inode_blocks_per_level[i];
  95     }
  96
  97     /*Validate FS*/
  98     tmp = ext4_get16(&fs->sb, state);
  99     if (tmp & EXT4_SUPERBLOCK_STATE_ERROR_FS) {
 100         ext4_dprintf(EXT4_DEBUG_FS, "Filesystem was not cleanly unmounted before \n");
 101     }
 102
 103     /* Mark system as mounted */
 104     ext4_set16(&fs->sb, state, EXT4_SUPERBLOCK_STATE_ERROR_FS);
 105     r = ext4_sb_write(fs->bdev, &fs->sb);
 106     if (r != EOK)
 107         return r;
 108
 109
 110     /*Update mount count*/
 111     ext4_set16(&fs->sb, mount_count, ext4_get16(&fs->sb, mount_count) + 1);
 112
 113     return r;
 114 }
 115
 116
 117 int ext4_fs_fini(struct ext4_fs *fs)
 118 {
 119     ext4_assert(fs);
 120
 121     /*Set superblock state*/
 122     ext4_set16(&fs->sb, state, EXT4_SUPERBLOCK_STATE_VALID_FS);
 123
 124     return ext4_sb_write(fs->bdev, &fs->sb);
 125 }
 126
 127 int ext4_fs_check_features(struct ext4_fs *fs, bool *read_only)
 128 {
 129     ext4_assert(fs && read_only);
 130
 131     if(ext4_get32(&fs->sb, rev_level) == 0){
 132         *read_only = false;
 133         return EOK;
 134     }
 135
 136     /*Check features_incompatible*/
 137     if ((ext4_get32(&fs->sb, features_incompatible) & (~EXT4_FEATURE_INCOMPAT_SUPP)) )
 138         return ENOTSUP;
 139
 140
 141     /*Check features_read_only*/
 142     if ((ext4_get32(&fs->sb, features_read_only) & (~EXT4_FEATURE_RO_COMPAT_SUPP))){
 143         *read_only = true;
 144         return EOK;
 145     }
 146
 147     *read_only = false;
 148
 149     return EOK;
 150 }
 151
 152 uint32_t ext4_fs_baddr2_index_in_group(struct ext4_sblock *s, uint32_t baddr)
 153 {
 154     ext4_assert(baddr);
 155     if(ext4_get32(s, first_data_block))
 156         baddr--;
 157
 158     return  baddr % ext4_get32(s, blocks_per_group);
 159 }
 160
 161
 162
 163 uint32_t ext4_fs_index_in_group2_baddr(struct ext4_sblock *s, uint32_t index, uint32_t bgid)
 164 {
 165     if(ext4_get32(s, first_data_block))
 166         index++;
 167
 168     return ext4_get32(s, blocks_per_group) * bgid + index;
 169 }
 170
 171
 172
 173
 174 static int ext4_fs_init_block_bitmap(struct ext4_block_group_ref *bg_ref)
 175 {
 176     uint32_t i;
 177     uint32_t bitmap_block_addr = ext4_bg_get_block_bitmap(
 178             bg_ref->block_group, &bg_ref->fs->sb);
 179
 180     struct ext4_block block_bitmap;
 181     int rc = ext4_block_get(bg_ref->fs->bdev, &block_bitmap, bitmap_block_addr);
 182     if (rc != EOK)
 183         return rc;
 184
 185
 186     memset(block_bitmap.data, 0, ext4_sb_get_block_size(&bg_ref->fs->sb));
 187
 188     /* Determine first block and first data block in group */
 189     uint32_t first_idx = 0;
 190
 191     uint32_t first_data = ext4_balloc_get_first_data_block_in_group(
 192             &bg_ref->fs->sb, bg_ref);
 193     uint32_t first_data_idx = ext4_fs_baddr2_index_in_group(
 194             &bg_ref->fs->sb, first_data);
 195
 196     /* Set bits from to first block to first data block - 1 to one (allocated) */
 197     /*TODO: Optimize it*/
 198     for (i = first_idx; i < first_data_idx; ++i)
 199         ext4_bmap_bit_set(block_bitmap.data, i);
 200
 201
 202     block_bitmap.dirty = true;
 203
 204     /* Save bitmap */
 205     return ext4_block_set(bg_ref->fs->bdev, &block_bitmap);
 206 }
 207
 208 static int ext4_fs_init_inode_bitmap(struct ext4_block_group_ref *bg_ref)
 209 {
 210     /* Load bitmap */
 211     uint32_t bitmap_block_addr = ext4_bg_get_inode_bitmap(
 212             bg_ref->block_group, &bg_ref->fs->sb);
 213
 214     struct ext4_block block_bitmap;
 215     int rc = ext4_block_get(bg_ref->fs->bdev, &block_bitmap, bitmap_block_addr);
 216     if (rc != EOK)
 217         return rc;
 218
 219     /* Initialize all bitmap bits to zero */
 220     uint32_t block_size = ext4_sb_get_block_size(&bg_ref->fs->sb);
 221     uint32_t inodes_per_group = ext4_get32(&bg_ref->fs->sb, inodes_per_group);
 222
 223     memset(block_bitmap.data, 0, (inodes_per_group + 7) / 8);
 224
 225     uint32_t start_bit = inodes_per_group;
 226     uint32_t end_bit = block_size * 8;
 227
 228     uint32_t i;
 229     for (i = start_bit; i < ((start_bit + 7) & ~7UL); i++)
 230         ext4_bmap_bit_set(block_bitmap.data, i);
 231
 232     if (i < end_bit)
 233         memset(block_bitmap.data + (i >> 3), 0xff, (end_bit - i) >> 3);
 234
 235     block_bitmap.dirty = true;
 236
 237     /* Save bitmap */
 238     return ext4_block_set(bg_ref->fs->bdev, &block_bitmap);
 239 }
 240
 241 static int ext4_fs_init_inode_table(struct ext4_block_group_ref *bg_ref)
 242 {
 243     struct ext4_sblock *sb = &bg_ref->fs->sb;
 244
 245     uint32_t inode_size           = ext4_get32(sb, inode_size);
 246     uint32_t block_size           = ext4_sb_get_block_size(sb);
 247     uint32_t inodes_per_block = block_size / inode_size;
 248     uint32_t inodes_in_group  = ext4_inodes_in_group_cnt(sb, bg_ref->index);
 249     uint32_t table_blocks = inodes_in_group / inodes_per_block;
 250     uint32_t fblock;
 251
 252     if (inodes_in_group % inodes_per_block)
 253         table_blocks++;
 254
 255     /* Compute initialization bounds */
 256     uint32_t first_block = ext4_bg_get_inode_table_first_block(
 257             bg_ref->block_group, sb);
 258
 259     uint32_t last_block = first_block + table_blocks - 1;
 260
 261     /* Initialization of all itable blocks */
 262     for (fblock = first_block; fblock <= last_block; ++fblock) {
 263
 264         struct ext4_block block;
 265         int rc = ext4_block_get(bg_ref->fs->bdev, &block, fblock);
 266         if (rc != EOK)
 267             return rc;
 268
 269         memset(block.data, 0, block_size);
 270         block.dirty = true;
 271
 272         ext4_block_set(bg_ref->fs->bdev, &block);
 273         if (rc != EOK)
 274             return rc;
 275     }
 276
 277     return EOK;
 278 }
 279
 280
 281 int ext4_fs_get_block_group_ref(struct ext4_fs *fs, uint32_t bgid, struct ext4_block_group_ref *ref)
 282 {
 283     /* Compute number of descriptors, that fits in one data block */
 284     uint32_t dsc_per_block = ext4_sb_get_block_size(&fs->sb) /
 285             ext4_sb_get_desc_size(&fs->sb);
 286
 287     /* Block group descriptor table starts at the next block after superblock */
 288     uint64_t block_id = ext4_get32(&fs->sb, first_data_block) + 1;
 289
 290     /* Find the block containing the descriptor we are looking for */
 291     block_id += bgid / dsc_per_block;
 292     uint32_t offset = (bgid % dsc_per_block) *
 293             ext4_sb_get_desc_size(&fs->sb);
 294
 295
 296     int rc = ext4_block_get(fs->bdev, &ref->block, block_id);
 297     if (rc != EOK)
 298         return rc;
 299
 300     ref->block_group = (void *)(ref->block.data + offset);
 301     ref->fs = fs;
 302     ref->index = bgid;
 303     ref->dirty = false;
 304
 305     if (ext4_bg_has_flag(ref->block_group,
 306             EXT4_BLOCK_GROUP_BLOCK_UNINIT)) {
 307         rc = ext4_fs_init_block_bitmap(ref);
 308         if (rc != EOK) {
 309             ext4_block_set(fs->bdev, &ref->block);
 310             return rc;
 311         }
 312         ext4_bg_clear_flag(ref->block_group,
 313                 EXT4_BLOCK_GROUP_BLOCK_UNINIT);
 314
 315         ref->dirty = true;
 316     }
 317
 318     if (ext4_bg_has_flag(ref->block_group,
 319             EXT4_BLOCK_GROUP_INODE_UNINIT)) {
 320         rc = ext4_fs_init_inode_bitmap(ref);
 321         if (rc != EOK) {
 322             ext4_block_set(ref->fs->bdev, &ref->block);
 323             return rc;
 324         }
 325
 326         ext4_bg_clear_flag(ref->block_group,
 327                 EXT4_BLOCK_GROUP_INODE_UNINIT);
 328
 329         if (!ext4_bg_has_flag(ref->block_group,
 330                 EXT4_BLOCK_GROUP_ITABLE_ZEROED)) {
 331             rc = ext4_fs_init_inode_table(ref);
 332             if (rc != EOK){
 333                 ext4_block_set(fs->bdev, &ref->block);
 334                 return rc;
 335             }
 336
 337             ext4_bg_set_flag(ref->block_group,
 338                     EXT4_BLOCK_GROUP_ITABLE_ZEROED);
 339         }
 340
 341         ref->dirty = true;
 342     }
 343
 344     return EOK;
 345 }
 346
 347 static uint16_t ext4_fs_bg_checksum(struct ext4_sblock *sb, uint32_t bgid, struct ext4_bgroup *bg)
 348 {
 349     /* If checksum not supported, 0 will be returned */
 350     uint16_t crc = 0;
 351
 352     /* Compute the checksum only if the filesystem supports it */
 353     if (ext4_sb_check_read_only(sb,
 354             EXT4_FEATURE_RO_COMPAT_GDT_CSUM)) {
 355         void *base = bg;
 356         void *checksum = &bg->checksum;
 357
 358         uint32_t offset = (uint32_t) (checksum - base);
 359
 360         /* Convert block group index to little endian */
 361         uint32_t le_group = to_le32(bgid);
 362
 363         /* Initialization */
 364         crc = ext4_bg_crc16(~0, sb->uuid, sizeof(sb->uuid));
 365
 366         /* Include index of block group */
 367         crc = ext4_bg_crc16(crc, (uint8_t *) &le_group, sizeof(le_group));
 368
 369         /* Compute crc from the first part (stop before checksum field) */
 370         crc = ext4_bg_crc16(crc, (uint8_t *) bg, offset);
 371
 372         /* Skip checksum */
 373         offset += sizeof(bg->checksum);
 374
 375         /* Checksum of the rest of block group descriptor */
 376         if ((ext4_sb_check_feature_incompatible(sb,
 377                 EXT4_FEATURE_INCOMPAT_64BIT)) &&
 378                 (offset < ext4_sb_get_desc_size(sb)))
 379
 380             crc = ext4_bg_crc16(crc, ((uint8_t *) bg) + offset,
 381                     ext4_sb_get_desc_size(sb) - offset);
 382     }
 383     return crc;
 384 }
 385
 386 int ext4_fs_put_block_group_ref(struct ext4_block_group_ref *ref)
 387 {
 388     /* Check if reference modified */
 389     if (ref->dirty) {
 390         /* Compute new checksum of block group */
 391         uint16_t checksum =
 392                 ext4_fs_bg_checksum(&ref->fs->sb, ref->index,
 393                         ref->block_group);
 394
 395         ref->block_group->checksum = to_le16(checksum);
 396
 397         /* Mark block dirty for writing changes to physical device */
 398         ref->block.dirty = true;
 399     }
 400
 401     /* Put back block, that contains block group descriptor */
 402     return ext4_block_set(ref->fs->bdev, &ref->block);
 403 }
 404
 405 int ext4_fs_get_inode_ref(struct ext4_fs *fs, uint32_t index,  struct ext4_inode_ref *ref)
 406 {
 407     /* Compute number of i-nodes, that fits in one data block */
 408     uint32_t inodes_per_group = ext4_get32(&fs->sb, inodes_per_group);
 409
 410     /*
 411      * Inode numbers are 1-based, but it is simpler to work with 0-based
 412      * when computing indices
 413      */
 414     index -= 1;
 415     uint32_t block_group = index / inodes_per_group;
 416     uint32_t offset_in_group = index % inodes_per_group;
 417
 418     /* Load block group, where i-node is located */
 419     struct ext4_block_group_ref bg_ref;
 420
 421     int rc = ext4_fs_get_block_group_ref(fs, block_group, &bg_ref);
 422     if (rc != EOK) {
 423         return rc;
 424     }
 425
 426     /* Load block address, where i-node table is located */
 427     uint32_t inode_table_start =
 428             ext4_bg_get_inode_table_first_block(bg_ref.block_group,
 429                     &fs->sb);
 430
 431     /* Put back block group reference (not needed more) */
 432     rc = ext4_fs_put_block_group_ref(&bg_ref);
 433     if (rc != EOK) {
 434         return rc;
 435     }
 436
 437     /* Compute position of i-node in the block group */
 438     uint16_t inode_size = ext4_get16(&fs->sb, inode_size);
 439     uint32_t block_size = ext4_sb_get_block_size(&fs->sb);
 440     uint32_t byte_offset_in_group = offset_in_group * inode_size;
 441
 442     /* Compute block address */
 443     uint64_t block_id = inode_table_start + (byte_offset_in_group / block_size);
 444
 445
 446     rc = ext4_block_get(fs->bdev, &ref->block, block_id);
 447     if (rc != EOK) {
 448         return rc;
 449     }
 450
 451     /* Compute position of i-node in the data block */
 452     uint32_t offset_in_block = byte_offset_in_group % block_size;
 453     ref->inode = (struct ext4_inode *)(ref->block.data + offset_in_block);
 454
 455     /* We need to store the original value of index in the reference */
 456     ref->index = index + 1;
 457     ref->fs = fs;
 458     ref->dirty = false;
 459
 460     return EOK;
 461 }
 462
 463 int ext4_fs_put_inode_ref(struct ext4_inode_ref *ref)
 464 {
 465     /* Check if reference modified */
 466     if (ref->dirty) {
 467         /* Mark block dirty for writing changes to physical device */
 468         ref->block.dirty = true;
 469     }
 470
 471     /* Put back block, that contains i-node */
 472     return  ext4_block_set(ref->fs->bdev, &ref->block);
 473 }
 474
 475 int ext4_fs_alloc_inode(struct ext4_fs *fs, struct ext4_inode_ref *inode_ref, bool is_directory)
 476 {
 477     /* Check if newly allocated i-node will be a directory */
 478     uint32_t i;
 479     bool is_dir;
 480
 481     is_dir = is_directory;
 482
 483     /* Allocate inode by allocation algorithm */
 484     uint32_t index;
 485     int rc = ext4_ialloc_alloc_inode(fs, &index, is_dir);
 486     if (rc != EOK)
 487         return rc;
 488
 489     /* Load i-node from on-disk i-node table */
 490     rc = ext4_fs_get_inode_ref(fs, index, inode_ref);
 491     if (rc != EOK) {
 492         ext4_ialloc_free_inode(fs, index, is_dir);
 493         return rc;
 494     }
 495
 496     /* Initialize i-node */
 497     struct ext4_inode *inode = inode_ref->inode;
 498
 499     uint16_t mode;
 500     if (is_dir) {
 501         /*
 502          * Default directory permissions to be compatible with other systems
 503          * 0777 (octal) == rwxrwxrwx
 504          */
 505
 506         mode = 0777;
 507         mode |= EXT4_INODE_MODE_DIRECTORY;
 508         ext4_inode_set_mode(&fs->sb, inode, mode);
 509         ext4_inode_set_links_count(inode, 1);  /* '.' entry */
 510
 511     } else {
 512         /*
 513          * Default file permissions to be compatible with other systems
 514          * 0666 (octal) == rw-rw-rw-
 515          */
 516
 517         mode = 0666;
 518         mode |= EXT4_INODE_MODE_FILE;
 519         ext4_inode_set_mode(&fs->sb, inode, mode);
 520         ext4_inode_set_links_count(inode, 0);
 521     }
 522
 523     ext4_inode_set_uid(inode, 0);
 524     ext4_inode_set_gid(inode, 0);
 525     ext4_inode_set_size(inode, 0);
 526     ext4_inode_set_access_time(inode,           0);
 527     ext4_inode_set_change_inode_time(inode, 0);
 528     ext4_inode_set_modification_time(inode, 0);
 529     ext4_inode_set_deletion_time(inode,         0);
 530     ext4_inode_set_blocks_count(&fs->sb, inode, 0);
 531     ext4_inode_set_flags(inode, 0);
 532     ext4_inode_set_generation(inode, 0);
 533
 534     /* Reset blocks array */
 535     for (i = 0; i < EXT4_INODE_BLOCKS; i++)
 536         inode->blocks[i] = 0;
 537
 538 #if 0
 539     /* Initialize extents if needed */
 540     if (ext4_sb_check_feature_incompatible(
 541             &fs->sb, EXT4_FEATURE_INCOMPAT_EXTENTS)) {
 542         ext4_inode_set_flag(inode, EXT4_INODE_FLAG_EXTENTS);
 543
 544
 545         /* Initialize extent root header */
 546         ext4_extent_header_t *header = ext4_inode_get_extent_header(inode);
 547         ext4_extent_header_set_depth(header, 0);
 548         ext4_extent_header_set_entries_count(header, 0);
 549         ext4_extent_header_set_generation(header, 0);
 550         ext4_extent_header_set_magic(header, EXT4_EXTENT_MAGIC);
 551
 552         uint16_t max_entries = (EXT4_INODE_BLOCKS * sizeof(uint32_t) -
 553                 sizeof(ext4_extent_header_t)) / sizeof(ext4_extent_t);
 554
 555         ext4_extent_header_set_max_entries_count(header, max_entries);
 556     }
 557 #endif
 558
 559     inode_ref->dirty = true;
 560
 561     return EOK;
 562 }
 563
 564 int ext4_fs_free_inode(struct ext4_inode_ref *inode_ref)
 565 {
 566     struct ext4_fs *fs = inode_ref->fs;
 567     uint32_t offset;
 568     uint32_t suboffset;
 569     /* For extents must be data block destroyed by other way */
 570     if ((ext4_sb_check_feature_incompatible(&fs->sb,
 571             EXT4_FEATURE_INCOMPAT_EXTENTS)) &&
 572             (ext4_inode_has_flag(inode_ref->inode, EXT4_INODE_FLAG_EXTENTS))) {
 573         /* Data structures are released during truncate operation... */
 574         goto finish;
 575     }
 576
 577     /* Release all indirect (no data) blocks */
 578
 579     /* 1) Single indirect */
 580     uint32_t fblock = ext4_inode_get_indirect_block(inode_ref->inode, 0);
 581     if (fblock != 0) {
 582         int rc = ext4_balloc_free_block(inode_ref, fblock);
 583         if (rc != EOK)
 584             return rc;
 585
 586         ext4_inode_set_indirect_block(inode_ref->inode, 0, 0);
 587     }
 588
 589     uint32_t block_size = ext4_sb_get_block_size(&fs->sb);
 590     uint32_t count = block_size / sizeof(uint32_t);
 591
 592     struct      ext4_block  block;
 593
 594     /* 2) Double indirect */
 595     fblock = ext4_inode_get_indirect_block(inode_ref->inode, 1);
 596     if (fblock != 0) {
 597         int rc = ext4_block_get(fs->bdev, &block, fblock);
 598         if (rc != EOK)
 599             return rc;
 600
 601         uint32_t ind_block;
 602         for (offset = 0; offset < count; ++offset) {
 603             ind_block = to_le32(((uint32_t *) block.data)[offset]);
 604
 605             if (ind_block != 0) {
 606                 rc = ext4_balloc_free_block(inode_ref, ind_block);
 607                 if (rc != EOK) {
 608                     ext4_block_set(fs->bdev, &block);
 609                     return rc;
 610                 }
 611             }
 612         }
 613
 614         ext4_block_set(fs->bdev, &block);
 615         rc = ext4_balloc_free_block(inode_ref, fblock);
 616         if (rc != EOK)
 617             return rc;
 618
 619         ext4_inode_set_indirect_block(inode_ref->inode, 1, 0);
 620     }
 621
 622     /* 3) Tripple indirect */
 623     struct      ext4_block  subblock;
 624     fblock = ext4_inode_get_indirect_block(inode_ref->inode, 2);
 625     if (fblock != 0) {
 626         int rc = ext4_block_get(fs->bdev, &block, fblock);
 627         if (rc != EOK)
 628             return rc;
 629
 630         uint32_t ind_block;
 631         for ( offset = 0; offset < count; ++offset) {
 632             ind_block = to_le32(((uint32_t *) block.data)[offset]);
 633
 634             if (ind_block != 0) {
 635                 rc = ext4_block_get(fs->bdev, &subblock, ind_block);
 636                 if (rc != EOK) {
 637                     ext4_block_set(fs->bdev, &block);
 638                     return rc;
 639                 }
 640
 641                 uint32_t ind_subblock;
 642                 for (suboffset = 0; suboffset < count;
 643                         ++suboffset) {
 644                     ind_subblock = to_le32(((uint32_t *)
 645                             subblock.data)[suboffset]);
 646
 647                     if (ind_subblock != 0) {
 648                         rc = ext4_balloc_free_block(inode_ref, ind_subblock);
 649                         if (rc != EOK) {
 650                             ext4_block_set(fs->bdev, &subblock);
 651                             ext4_block_set(fs->bdev, &block);
 652                             return rc;
 653                         }
 654                     }
 655                 }
 656
 657                 ext4_block_set(fs->bdev, &subblock);
 658
 659
 660                 rc = ext4_balloc_free_block(inode_ref, ind_block);
 661                 if (rc != EOK) {
 662                     ext4_block_set(fs->bdev, &block);
 663                     return rc;
 664                 }
 665             }
 666         }
 667
 668         ext4_block_set(fs->bdev, &block);
 669         rc = ext4_balloc_free_block(inode_ref, fblock);
 670         if (rc != EOK)
 671             return rc;
 672
 673         ext4_inode_set_indirect_block(inode_ref->inode, 2, 0);
 674     }
 675
 676     finish:
 677     /* Mark inode dirty for writing to the physical device */
 678     inode_ref->dirty = true;
 679
 680     /* Free block with extended attributes if present */
 681     uint32_t xattr_block = ext4_inode_get_file_acl(
 682             inode_ref->inode, &fs->sb);
 683     if (xattr_block) {
 684         int rc = ext4_balloc_free_block(inode_ref, xattr_block);
 685         if (rc != EOK)
 686             return rc;
 687
 688         ext4_inode_set_file_acl(inode_ref->inode, &fs->sb, 0);
 689     }
 690
 691     /* Free inode by allocator */
 692     int rc;
 693     if (ext4_inode_is_type(&fs->sb, inode_ref->inode,
 694             EXT4_INODE_MODE_DIRECTORY))
 695         rc = ext4_ialloc_free_inode(fs, inode_ref->index, true);
 696     else
 697         rc = ext4_ialloc_free_inode(fs, inode_ref->index, false);
 698
 699     return rc;
 700 }
 701
 702 int ext4_fs_truncate_inode(struct ext4_inode_ref *inode_ref,
 703         uint64_t new_size)
 704 {
 705     struct ext4_sblock *sb = &inode_ref->fs->sb;
 706     uint32_t i;
 707
 708     /* Check flags, if i-node can be truncated */
 709     if (!ext4_inode_can_truncate(sb, inode_ref->inode))
 710         return EINVAL;
 711
 712     /* If sizes are equal, nothing has to be done. */
 713     uint64_t old_size = ext4_inode_get_size(sb, inode_ref->inode);
 714     if (old_size == new_size)
 715         return EOK;
 716
 717     /* It's not suppported to make the larger file by truncate operation */
 718     if (old_size < new_size)
 719         return EINVAL;
 720
 721     /* Compute how many blocks will be released */
 722     uint64_t size_diff = old_size - new_size;
 723     uint32_t block_size  = ext4_sb_get_block_size(sb);
 724     uint32_t diff_blocks_count = size_diff / block_size;
 725     if (size_diff % block_size != 0)
 726         diff_blocks_count++;
 727
 728     uint32_t old_blocks_count = old_size / block_size;
 729     if (old_size % block_size != 0)
 730         old_blocks_count++;
 731
 732     if ((ext4_sb_check_feature_incompatible(sb,
 733             EXT4_FEATURE_INCOMPAT_EXTENTS)) &&
 734             (ext4_inode_has_flag(inode_ref->inode, EXT4_INODE_FLAG_EXTENTS))) {
 735 #if 0
 736         /* Extents require special operation */
 737         int rc = ext4_extent_release_blocks_from(inode_ref,
 738                 old_blocks_count - diff_blocks_count);
 739         if (rc != EOK)
 740             return rc;
 741 #endif
 742     } else {
 743         /* Release data blocks from the end of file */
 744
 745         /* Starting from 1 because of logical blocks are numbered from 0 */
 746         for (i = 1; i <= diff_blocks_count; ++i) {
 747             int rc = ext4_fs_release_inode_block(inode_ref,
 748                     old_blocks_count - i);
 749             if (rc != EOK)
 750                 return rc;
 751         }
 752     }
 753
 754     /* Update i-node */
 755     ext4_inode_set_size(inode_ref->inode, new_size);
 756     inode_ref->dirty = true;
 757
 758     return EOK;
 759 }
 760
 761 int ext4_fs_get_inode_data_block_index(struct ext4_inode_ref *inode_ref,
 762         uint64_t iblock, uint32_t *fblock)
 763 {
 764     struct ext4_fs *fs = inode_ref->fs;
 765
 766     /* For empty file is situation simple */
 767     if (ext4_inode_get_size(&fs->sb, inode_ref->inode) == 0) {
 768         *fblock = 0;
 769         return EOK;
 770     }
 771
 772     uint32_t current_block;
 773
 774     /* Handle i-node using extents */
 775     if ((ext4_sb_check_feature_incompatible(&fs->sb,
 776             EXT4_FEATURE_INCOMPAT_EXTENTS)) &&
 777             (ext4_inode_has_flag(inode_ref->inode, EXT4_INODE_FLAG_EXTENTS))) {
 778
 779 #if 0
 780         int rc = ext4_extent_find_block(inode_ref, iblock, &current_block);
 781         if (rc != EOK)
 782             return rc;
 783
 784         *fblock = current_block;
 785         return EOK;
 786 #endif
 787     }
 788
 789     struct ext4_inode *inode = inode_ref->inode;
 790
 791     /* Direct block are read directly from array in i-node structure */
 792     if (iblock < EXT4_INODE_DIRECT_BLOCK_COUNT) {
 793         current_block = ext4_inode_get_direct_block(inode, (uint32_t) iblock);
 794         *fblock = current_block;
 795         return EOK;
 796     }
 797
 798     /* Determine indirection level of the target block */
 799     unsigned int level = 0;
 800     unsigned int i;
 801     for (i = 1; i < 4; i++) {
 802         if (iblock < fs->inode_block_limits[i]) {
 803             level = i;
 804             break;
 805         }
 806     }
 807
 808     if (level == 0)
 809         return EIO;
 810
 811     /* Compute offsets for the topmost level */
 812     uint64_t block_offset_in_level =
 813             iblock - fs->inode_block_limits[level - 1];
 814     current_block = ext4_inode_get_indirect_block(inode, level - 1);
 815     uint32_t offset_in_block =
 816             block_offset_in_level / fs->inode_blocks_per_level[level - 1];
 817
 818     /* Sparse file */
 819     if (current_block == 0) {
 820         *fblock = 0;
 821         return EOK;
 822     }
 823
 824     struct      ext4_block block;
 825
 826     /*
 827      * Navigate through other levels, until we find the block number
 828      * or find null reference meaning we are dealing with sparse file
 829      */
 830     while (level > 0) {
 831         /* Load indirect block */
 832         int rc = ext4_block_get(fs->bdev, &block, current_block);
 833         if (rc != EOK)
 834             return rc;
 835
 836         /* Read block address from indirect block */
 837         current_block =
 838                 to_le32(((uint32_t *) block.data)[offset_in_block]);
 839
 840         /* Put back indirect block untouched */
 841         rc = ext4_block_set(fs->bdev, &block);
 842         if (rc != EOK)
 843             return rc;
 844
 845         /* Check for sparse file */
 846         if (current_block == 0) {
 847             *fblock = 0;
 848             return EOK;
 849         }
 850
 851         /* Jump to the next level */
 852         level--;
 853
 854         /* Termination condition - we have address of data block loaded */
 855         if (level == 0)
 856             break;
 857
 858         /* Visit the next level */
 859         block_offset_in_level %= fs->inode_blocks_per_level[level];
 860         offset_in_block =
 861                 block_offset_in_level / fs->inode_blocks_per_level[level - 1];
 862     }
 863
 864     *fblock = current_block;
 865
 866     return EOK;
 867 }
 868
 869 int ext4_fs_set_inode_data_block_index(struct ext4_inode_ref *inode_ref,
 870         uint64_t iblock, uint32_t fblock)
 871 {
 872     struct ext4_fs *fs = inode_ref->fs;
 873
 874     /* Handle inode using extents */
 875     if ((ext4_sb_check_feature_incompatible(&fs->sb,
 876             EXT4_FEATURE_INCOMPAT_EXTENTS)) &&
 877             (ext4_inode_has_flag(inode_ref->inode, EXT4_INODE_FLAG_EXTENTS))) {
 878         /* Not reachable */
 879         return ENOTSUP;
 880     }
 881
 882     /* Handle simple case when we are dealing with direct reference */
 883     if (iblock < EXT4_INODE_DIRECT_BLOCK_COUNT) {
 884         ext4_inode_set_direct_block(inode_ref->inode, (uint32_t) iblock, fblock);
 885         inode_ref->dirty = true;
 886
 887         return EOK;
 888     }
 889
 890     /* Determine the indirection level needed to get the desired block */
 891     unsigned int level = 0;
 892     unsigned int i;
 893     for (i = 1; i < 4; i++) {
 894         if (iblock < fs->inode_block_limits[i]) {
 895             level = i;
 896             break;
 897         }
 898     }
 899
 900     if (level == 0)
 901         return EIO;
 902
 903     uint32_t block_size = ext4_sb_get_block_size(&fs->sb);
 904
 905     /* Compute offsets for the topmost level */
 906     uint64_t block_offset_in_level =
 907             iblock - fs->inode_block_limits[level - 1];
 908     uint32_t current_block =
 909             ext4_inode_get_indirect_block(inode_ref->inode, level - 1);
 910     uint32_t offset_in_block =
 911             block_offset_in_level / fs->inode_blocks_per_level[level - 1];
 912
 913     uint32_t new_block_addr;
 914
 915     struct      ext4_block block;
 916     struct      ext4_block new_block;
 917
 918     /* Is needed to allocate indirect block on the i-node level */
 919     if (current_block == 0) {
 920         /* Allocate new indirect block */
 921         int rc = ext4_balloc_alloc_block(inode_ref, &new_block_addr);
 922         if (rc != EOK)
 923             return rc;
 924
 925         /* Update i-node */
 926         ext4_inode_set_indirect_block(inode_ref->inode, level - 1,
 927                 new_block_addr);
 928         inode_ref->dirty = true;
 929
 930         /* Load newly allocated block */
 931         rc = ext4_block_get(fs->bdev, &new_block, new_block_addr);
 932         if (rc != EOK) {
 933             ext4_balloc_free_block(inode_ref, new_block_addr);
 934             return rc;
 935         }
 936
 937         /* Initialize new block */
 938         memset(new_block.data, 0, block_size);
 939         new_block.dirty = true;
 940
 941         /* Put back the allocated block */
 942         rc = ext4_block_set(fs->bdev, &new_block);
 943         if (rc != EOK)
 944             return rc;
 945
 946         current_block = new_block_addr;
 947     }
 948
 949     /*
 950      * Navigate through other levels, until we find the block number
 951      * or find null reference meaning we are dealing with sparse file
 952      */
 953     while (level > 0) {
 954         int rc = ext4_block_get(fs->bdev, &block, current_block);
 955         if (rc != EOK)
 956             return rc;
 957
 958         current_block =
 959                 to_le32(((uint32_t *) block.data)[offset_in_block]);
 960
 961         if ((level > 1) && (current_block == 0)) {
 962             /* Allocate new block */
 963             rc = ext4_balloc_alloc_block(inode_ref, &new_block_addr);
 964             if (rc != EOK) {
 965                 ext4_block_set(fs->bdev, &block);
 966                 return rc;
 967             }
 968
 969             /* Load newly allocated block */
 970             rc = ext4_block_get(fs->bdev, &new_block, new_block_addr);
 971
 972             if (rc != EOK) {
 973                 ext4_block_set(fs->bdev, &block);
 974                 return rc;
 975             }
 976
 977             /* Initialize allocated block */
 978             memset(new_block.data, 0, block_size);
 979             new_block.dirty = true;
 980
 981             rc = ext4_block_set(fs->bdev, &new_block);
 982             if (rc != EOK) {
 983                 ext4_block_set(fs->bdev, &block);
 984                 return rc;
 985             }
 986
 987             /* Write block address to the parent */
 988             ((uint32_t *) block.data)[offset_in_block] =
 989                     to_le32(new_block_addr);
 990             block.dirty = true;
 991             current_block = new_block_addr;
 992         }
 993
 994         /* Will be finished, write the fblock address */
 995         if (level == 1) {
 996             ((uint32_t *) block.data)[offset_in_block] =
 997                     to_le32(fblock);
 998             block.dirty = true;
 999         }
1000
1001         rc = ext4_block_set(fs->bdev, &block);
1002         if (rc != EOK)
1003             return rc;
1004
1005         level--;
1006
1007         /*
1008          * If we are on the last level, break here as
1009          * there is no next level to visit
1010          */
1011         if (level == 0)
1012             break;
1013
1014         /* Visit the next level */
1015         block_offset_in_level %= fs->inode_blocks_per_level[level];
1016         offset_in_block =
1017                 block_offset_in_level / fs->inode_blocks_per_level[level - 1];
1018     }
1019
1020     return EOK;
1021 }
1022
1023 int ext4_fs_release_inode_block(struct ext4_inode_ref *inode_ref,
1024         uint32_t iblock)
1025 {
1026     uint32_t fblock;
1027
1028     struct ext4_fs *fs = inode_ref->fs;
1029
1030     /* Extents are handled otherwise = there is not support in this function */
1031     ext4_assert(!(ext4_sb_check_feature_incompatible(&fs->sb,
1032             EXT4_FEATURE_INCOMPAT_EXTENTS) &&
1033             (ext4_inode_has_flag(inode_ref->inode, EXT4_INODE_FLAG_EXTENTS))));
1034
1035     struct ext4_inode *inode = inode_ref->inode;
1036
1037     /* Handle simple case when we are dealing with direct reference */
1038     if (iblock < EXT4_INODE_DIRECT_BLOCK_COUNT) {
1039         fblock = ext4_inode_get_direct_block(inode, iblock);
1040
1041         /* Sparse file */
1042         if (fblock == 0)
1043             return EOK;
1044
1045         ext4_inode_set_direct_block(inode, iblock, 0);
1046         return ext4_balloc_free_block(inode_ref, fblock);
1047     }
1048
1049     /* Determine the indirection level needed to get the desired block */
1050     unsigned int level = 0;
1051     unsigned int i;
1052     for (i = 1; i < 4; i++) {
1053         if (iblock < fs->inode_block_limits[i]) {
1054             level = i;
1055             break;
1056         }
1057     }
1058
1059     if (level == 0)
1060         return EIO;
1061
1062     /* Compute offsets for the topmost level */
1063     uint64_t block_offset_in_level =
1064             iblock - fs->inode_block_limits[level - 1];
1065     uint32_t current_block =
1066             ext4_inode_get_indirect_block(inode, level - 1);
1067     uint32_t offset_in_block =
1068             block_offset_in_level / fs->inode_blocks_per_level[level - 1];
1069
1070     /*
1071      * Navigate through other levels, until we find the block number
1072      * or find null reference meaning we are dealing with sparse file
1073      */
1074     struct      ext4_block block;
1075
1076     while (level > 0) {
1077
1078         /* Sparse check */
1079         if (current_block == 0)
1080             return EOK;
1081
1082         int rc = ext4_block_get(fs->bdev, &block, current_block);
1083         if (rc != EOK)
1084             return rc;
1085
1086         current_block =
1087                 to_le32(((uint32_t *) block.data)[offset_in_block]);
1088
1089         /* Set zero if physical data block address found */
1090         if (level == 1) {
1091             ((uint32_t *) block.data)[offset_in_block] =
1092                     to_le32(0);
1093             block.dirty = true;
1094         }
1095
1096         rc = ext4_block_set(fs->bdev, &block);
1097         if (rc != EOK)
1098             return rc;
1099
1100         level--;
1101
1102         /*
1103          * If we are on the last level, break here as
1104          * there is no next level to visit
1105          */
1106         if (level == 0)
1107             break;
1108
1109         /* Visit the next level */
1110         block_offset_in_level %= fs->inode_blocks_per_level[level];
1111         offset_in_block =
1112                 block_offset_in_level / fs->inode_blocks_per_level[level - 1];
1113     }
1114
1115     fblock = current_block;
1116     if (fblock == 0)
1117         return EOK;
1118
1119     /* Physical block is not referenced, it can be released */
1120     return ext4_balloc_free_block(inode_ref, fblock);
1121 }
1122
1123
1124 int ext4_fs_append_inode_block(struct ext4_inode_ref *inode_ref,
1125         uint32_t *fblock, uint32_t *iblock)
1126 {
1127     /* Handle extents separately */
1128     if ((ext4_sb_check_feature_incompatible(&inode_ref->fs->sb,
1129             EXT4_FEATURE_INCOMPAT_EXTENTS)) &&
1130             (ext4_inode_has_flag(inode_ref->inode, EXT4_INODE_FLAG_EXTENTS))){
1131
1132 #if 0
1133         return ext4_extent_append_block(inode_ref, iblock, fblock, true);
1134 #endif
1135     }
1136
1137     struct ext4_sblock *sb = &inode_ref->fs->sb;
1138
1139     /* Compute next block index and allocate data block */
1140     uint64_t inode_size = ext4_inode_get_size(sb, inode_ref->inode);
1141     uint32_t block_size = ext4_sb_get_block_size(sb);
1142
1143     /* Align size i-node size */
1144     if ((inode_size % block_size) != 0)
1145         inode_size += block_size - (inode_size % block_size);
1146
1147     /* Logical blocks are numbered from 0 */
1148     uint32_t new_block_idx = inode_size / block_size;
1149
1150     /* Allocate new physical block */
1151     uint32_t phys_block;
1152     int rc = ext4_balloc_alloc_block(inode_ref, &phys_block);
1153     if (rc != EOK)
1154         return rc;
1155
1156     /* Add physical block address to the i-node */
1157     rc = ext4_fs_set_inode_data_block_index(inode_ref,
1158             new_block_idx, phys_block);
1159     if (rc != EOK) {
1160         ext4_balloc_free_block(inode_ref, phys_block);
1161         return rc;
1162     }
1163
1164     /* Update i-node */
1165     ext4_inode_set_size(inode_ref->inode, inode_size + block_size);
1166     inode_ref->dirty = true;
1167
1168     *fblock = phys_block;
1169     *iblock = new_block_idx;
1170
1171     return EOK;
1172 }
1173
1174 /**
1175  * @}
1176  */
1177