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_crc32c.h"
  48 #include "ext4_debug.h"
  49 #include "ext4_block_group.h"
  50 #include "ext4_balloc.h"
  51 #include "ext4_bitmap.h"
  52 #include "ext4_inode.h"
  53 #include "ext4_ialloc.h"
  54 #include "ext4_extent.h"
  55
  56 #include <string.h>
  57
  58 int ext4_fs_init(struct ext4_fs *fs, struct ext4_blockdev *bdev)
  59 {
  60         int r, i;
  61         uint16_t tmp;
  62         uint32_t bsize;
  63         bool read_only = false;
  64
  65         ext4_assert(fs && bdev);
  66
  67         fs->bdev = bdev;
  68
  69         r = ext4_sb_read(fs->bdev, &fs->sb);
  70         if (r != EOK)
  71                 return r;
  72
  73         if (!ext4_sb_check(&fs->sb))
  74                 return ENOTSUP;
  75
  76         bsize = ext4_sb_get_block_size(&fs->sb);
  77         if (bsize > EXT4_MAX_BLOCK_SIZE)
  78                 return ENXIO;
  79
  80         r = ext4_fs_check_features(fs, &read_only);
  81         if (r != EOK)
  82                 return r;
  83
  84         if (read_only)
  85                 return ENOTSUP;
  86
  87         /* Compute limits for indirect block levels */
  88         uint32_t blocks_id = bsize / sizeof(uint32_t);
  89
  90         fs->inode_block_limits[0] = EXT4_INODE_DIRECT_BLOCK_COUNT;
  91         fs->inode_blocks_per_level[0] = 1;
  92
  93         for (i = 1; i < 4; i++) {
  94                 fs->inode_blocks_per_level[i] =
  95                     fs->inode_blocks_per_level[i - 1] * blocks_id;
  96                 fs->inode_block_limits[i] = fs->inode_block_limits[i - 1] +
  97                                             fs->inode_blocks_per_level[i];
  98         }
  99
 100         /*Validate FS*/
 101         tmp = ext4_get16(&fs->sb, state);
 102         if (tmp & EXT4_SUPERBLOCK_STATE_ERROR_FS)
 103                 ext4_dbg(DEBUG_FS, DBG_WARN
 104                                 "last umount error: superblock fs_error flag\n");
 105
 106
 107         /* Mark system as mounted */
 108         ext4_set16(&fs->sb, state, EXT4_SUPERBLOCK_STATE_ERROR_FS);
 109         r = ext4_sb_write(fs->bdev, &fs->sb);
 110         if (r != EOK)
 111                 return r;
 112
 113         /*Update mount count*/
 114         ext4_set16(&fs->sb, mount_count, ext4_get16(&fs->sb, mount_count) + 1);
 115
 116         return r;
 117 }
 118
 119 int ext4_fs_fini(struct ext4_fs *fs)
 120 {
 121         ext4_assert(fs);
 122
 123         /*Set superblock state*/
 124         ext4_set16(&fs->sb, state, EXT4_SUPERBLOCK_STATE_VALID_FS);
 125
 126         return ext4_sb_write(fs->bdev, &fs->sb);
 127 }
 128
 129 static void ext4_fs_debug_features_inc(uint32_t features_incompatible)
 130 {
 131         if (features_incompatible & EXT4_FINCOM_COMPRESSION)
 132                 ext4_dbg(DEBUG_FS, DBG_NONE "compression\n");
 133         if (features_incompatible & EXT4_FINCOM_FILETYPE)
 134                 ext4_dbg(DEBUG_FS, DBG_NONE "filetype\n");
 135         if (features_incompatible & EXT4_FINCOM_RECOVER)
 136                 ext4_dbg(DEBUG_FS, DBG_NONE "recover\n");
 137         if (features_incompatible & EXT4_FINCOM_JOURNAL_DEV)
 138                 ext4_dbg(DEBUG_FS, DBG_NONE "journal_dev\n");
 139         if (features_incompatible & EXT4_FINCOM_META_BG)
 140                 ext4_dbg(DEBUG_FS, DBG_NONE "meta_bg\n");
 141         if (features_incompatible & EXT4_FINCOM_EXTENTS)
 142                 ext4_dbg(DEBUG_FS, DBG_NONE "extents\n");
 143         if (features_incompatible & EXT4_FINCOM_64BIT)
 144                 ext4_dbg(DEBUG_FS, DBG_NONE "64bit\n");
 145         if (features_incompatible & EXT4_FINCOM_MMP)
 146                 ext4_dbg(DEBUG_FS, DBG_NONE "mnp\n");
 147         if (features_incompatible & EXT4_FINCOM_FLEX_BG)
 148                 ext4_dbg(DEBUG_FS, DBG_NONE "flex_bg\n");
 149         if (features_incompatible & EXT4_FINCOM_EA_INODE)
 150                 ext4_dbg(DEBUG_FS, DBG_NONE "ea_inode\n");
 151         if (features_incompatible & EXT4_FINCOM_DIRDATA)
 152                 ext4_dbg(DEBUG_FS, DBG_NONE "dirdata\n");
 153         if (features_incompatible & EXT4_FINCOM_BG_USE_META_CSUM)
 154                 ext4_dbg(DEBUG_FS, DBG_NONE "meta_csum\n");
 155         if (features_incompatible & EXT4_FINCOM_LARGEDIR)
 156                 ext4_dbg(DEBUG_FS, DBG_NONE "largedir\n");
 157         if (features_incompatible & EXT4_FINCOM_INLINE_DATA)
 158                 ext4_dbg(DEBUG_FS, DBG_NONE "inline_data\n");
 159 }
 160 static void ext4_fs_debug_features_comp(uint32_t features_compatible)
 161 {
 162         if (features_compatible & EXT4_FCOM_DIR_PREALLOC)
 163                 ext4_dbg(DEBUG_FS, DBG_NONE "dir_prealloc\n");
 164         if (features_compatible & EXT4_FCOM_IMAGIC_INODES)
 165                 ext4_dbg(DEBUG_FS, DBG_NONE "imagic_inodes\n");
 166         if (features_compatible & EXT4_FCOM_HAS_JOURNAL)
 167                 ext4_dbg(DEBUG_FS, DBG_NONE "has_journal\n");
 168         if (features_compatible & EXT4_FCOM_EXT_ATTR)
 169                 ext4_dbg(DEBUG_FS, DBG_NONE "ext_attr\n");
 170         if (features_compatible & EXT4_FCOM_RESIZE_INODE)
 171                 ext4_dbg(DEBUG_FS, DBG_NONE "resize_inode\n");
 172         if (features_compatible & EXT4_FCOM_DIR_INDEX)
 173                 ext4_dbg(DEBUG_FS, DBG_NONE "dir_index\n");
 174 }
 175
 176 static void ext4_fs_debug_features_ro(uint32_t features_ro)
 177 {
 178         if (features_ro & EXT4_FRO_COM_SPARSE_SUPER)
 179                 ext4_dbg(DEBUG_FS, DBG_NONE "sparse_super\n");
 180         if (features_ro & EXT4_FRO_COM_LARGE_FILE)
 181                 ext4_dbg(DEBUG_FS, DBG_NONE "large_file\n");
 182         if (features_ro & EXT4_FRO_COM_BTREE_DIR)
 183                 ext4_dbg(DEBUG_FS, DBG_NONE "btree_dir\n");
 184         if (features_ro & EXT4_FRO_COM_HUGE_FILE)
 185                 ext4_dbg(DEBUG_FS, DBG_NONE "huge_file\n");
 186         if (features_ro & EXT4_FRO_COM_GDT_CSUM)
 187                 ext4_dbg(DEBUG_FS, DBG_NONE "gtd_csum\n");
 188         if (features_ro & EXT4_FRO_COM_DIR_NLINK)
 189                 ext4_dbg(DEBUG_FS, DBG_NONE "dir_nlink\n");
 190         if (features_ro & EXT4_FRO_COM_EXTRA_ISIZE)
 191                 ext4_dbg(DEBUG_FS, DBG_NONE "extra_isize\n");
 192         if (features_ro & EXT4_FRO_COM_QUOTA)
 193                 ext4_dbg(DEBUG_FS, DBG_NONE "quota\n");
 194         if (features_ro & EXT4_FRO_COM_BIGALLOC)
 195                 ext4_dbg(DEBUG_FS, DBG_NONE "bigalloc\n");
 196         if (features_ro & EXT4_FRO_COM_METADATA_CSUM)
 197                 ext4_dbg(DEBUG_FS, DBG_NONE "metadata_csum\n");
 198 }
 199
 200 int ext4_fs_check_features(struct ext4_fs *fs, bool *read_only)
 201 {
 202         ext4_assert(fs && read_only);
 203         uint32_t v;
 204         if (ext4_get32(&fs->sb, rev_level) == 0) {
 205                 *read_only = false;
 206                 return EOK;
 207         }
 208
 209         ext4_dbg(DEBUG_FS, DBG_INFO "sblock features_incompatible:\n");
 210         ext4_fs_debug_features_inc(ext4_get32(&fs->sb, features_incompatible));
 211
 212         ext4_dbg(DEBUG_FS, DBG_INFO "sblock features_compatible:\n");
 213         ext4_fs_debug_features_comp(ext4_get32(&fs->sb, features_compatible));
 214
 215         ext4_dbg(DEBUG_FS, DBG_INFO "sblock features_read_only:\n");
 216         ext4_fs_debug_features_ro(ext4_get32(&fs->sb, features_read_only));
 217
 218         /*Check features_incompatible*/
 219         v = (ext4_get32(&fs->sb, features_incompatible) &
 220              (~CONFIG_SUPPORTED_FINCOM));
 221         if (v) {
 222                 ext4_dbg(DEBUG_FS, DBG_ERROR
 223                                 "sblock has unsupported features incompatible:\n");
 224                 ext4_fs_debug_features_inc(v);
 225                 return ENOTSUP;
 226         }
 227
 228         /*Check features_read_only*/
 229         v = ext4_get32(&fs->sb, features_read_only);
 230         v &= ~CONFIG_SUPPORTED_FRO_COM;
 231         if (v) {
 232                 ext4_dbg(DEBUG_FS, DBG_WARN
 233                         "sblock has unsupported features read only:\n");
 234                 ext4_fs_debug_features_ro(v);
 235                 *read_only = true;
 236                 return EOK;
 237         }
 238         *read_only = false;
 239
 240         return EOK;
 241 }
 242
 243 /**@brief Determine whether the block is inside the group.
 244  * @param baddr   block address
 245  * @param bgid    block group id
 246  * @return Error code
 247  */
 248 static bool ext4_block_in_group(struct ext4_sblock *s, ext4_fsblk_t baddr,
 249                                 uint32_t bgid)
 250 {
 251         uint32_t actual_bgid;
 252         actual_bgid = ext4_balloc_get_bgid_of_block(s, baddr);
 253         if (actual_bgid == bgid)
 254                 return true;
 255         return false;
 256 }
 257
 258 /**@brief   To avoid calling the atomic setbit hundreds or thousands of times, we only
 259  *          need to use it within a single byte (to ensure we get endianness right).
 260  *          We can use memset for the rest of the bitmap as there are no other users.
 261  */
 262 static void ext4_fs_mark_bitmap_end(int start_bit, int end_bit, void *bitmap)
 263 {
 264         int i;
 265
 266         if (start_bit >= end_bit)
 267                 return;
 268
 269         for (i = start_bit; (unsigned)i < ((start_bit + 7) & ~7UL); i++)
 270                 ext4_bmap_bit_set(bitmap, i);
 271
 272         if (i < end_bit)
 273                 memset((char *)bitmap + (i >> 3), 0xff, (end_bit - i) >> 3);
 274 }
 275
 276 /**@brief Initialize block bitmap in block group.
 277  * @param bg_ref Reference to block group
 278  * @return Error code
 279  */
 280 static int ext4_fs_init_block_bitmap(struct ext4_block_group_ref *bg_ref)
 281 {
 282         struct ext4_sblock *sb = &bg_ref->fs->sb;
 283         struct ext4_bgroup *bg = bg_ref->block_group;
 284         int rc;
 285
 286         uint32_t i, bit, bit_max;
 287         uint32_t group_blocks;
 288         uint16_t inode_size = ext4_get16(sb, inode_size);
 289         uint32_t block_size = ext4_sb_get_block_size(sb);
 290         uint32_t inodes_per_group = ext4_get32(sb, inodes_per_group);
 291
 292         ext4_fsblk_t bmp_blk = ext4_bg_get_block_bitmap(bg, sb);
 293         ext4_fsblk_t bmp_inode = ext4_bg_get_inode_bitmap(bg, sb);
 294         ext4_fsblk_t inode_table = ext4_bg_get_inode_table_first_block(bg, sb);
 295         ext4_fsblk_t first_bg = ext4_balloc_get_block_of_bgid(sb, bg_ref->index);
 296
 297         uint32_t dsc_per_block =  block_size / ext4_sb_get_desc_size(sb);
 298
 299         bool flex_bg = ext4_sb_feature_incom(sb, EXT4_FINCOM_FLEX_BG);
 300         bool meta_bg = ext4_sb_feature_incom(sb, EXT4_FINCOM_META_BG);
 301
 302         uint32_t inode_table_bcnt = inodes_per_group * inode_size / block_size;
 303
 304         struct ext4_block block_bitmap;
 305         rc = ext4_block_get_noread(bg_ref->fs->bdev, &block_bitmap, bmp_blk);
 306         if (rc != EOK)
 307                 return rc;
 308
 309         memset(block_bitmap.data, 0, block_size);
 310         bit_max = ext4_sb_is_super_in_bg(sb, bg_ref->index);
 311
 312         uint32_t count = ext4_sb_first_meta_bg(sb) * dsc_per_block;
 313         if (!meta_bg || bg_ref->index < count) {
 314                 if (bit_max) {
 315                         bit_max += ext4_bg_num_gdb(sb, bg_ref->index);
 316                         bit_max += ext4_get16(sb, s_reserved_gdt_blocks);
 317                 }
 318         } else { /* For META_BG_BLOCK_GROUPS */
 319                 bit_max += ext4_bg_num_gdb(sb, bg_ref->index);
 320         }
 321         for (bit = 0; bit < bit_max; bit++)
 322                 ext4_bmap_bit_set(block_bitmap.data, bit);
 323
 324         if (bg_ref->index == ext4_block_group_cnt(sb) - 1) {
 325                 /*
 326                  * Even though mke2fs always initialize first and last group
 327                  * if some other tool enabled the EXT4_BG_BLOCK_UNINIT we need
 328                  * to make sure we calculate the right free blocks
 329                  */
 330
 331                 group_blocks = ext4_sb_get_blocks_cnt(sb);
 332                 group_blocks -= ext4_get32(sb, first_data_block);
 333                 group_blocks -= ext4_get32(sb, blocks_per_group) *
 334                                 (ext4_block_group_cnt(sb) - 1);
 335         } else {
 336                 group_blocks = ext4_get32(sb, blocks_per_group);
 337         }
 338
 339         bool in_bg;
 340         in_bg = ext4_block_in_group(sb, bmp_blk, bg_ref->index);
 341         if (!flex_bg || in_bg)
 342                 ext4_bmap_bit_set(block_bitmap.data, bmp_blk - first_bg);
 343
 344         in_bg = ext4_block_in_group(sb, bmp_inode, bg_ref->index);
 345         if (!flex_bg || in_bg)
 346                 ext4_bmap_bit_set(block_bitmap.data, bmp_inode - first_bg);
 347
 348         for (i = inode_table; i < inode_table + inode_table_bcnt; i++) {
 349                 in_bg = ext4_block_in_group(sb, i, bg_ref->index);
 350                 if (!flex_bg || in_bg)
 351                         ext4_bmap_bit_set(block_bitmap.data, i - first_bg);
 352         }
 353         /*
 354          * Also if the number of blocks within the group is
 355          * less than the blocksize * 8 ( which is the size
 356          * of bitmap ), set rest of the block bitmap to 1
 357          */
 358         ext4_fs_mark_bitmap_end(group_blocks, block_size * 8, block_bitmap.data);
 359         block_bitmap.dirty = true;
 360
 361         ext4_balloc_set_bitmap_csum(sb, bg_ref->block_group, block_bitmap.data);
 362         bg_ref->dirty = true;
 363
 364         /* Save bitmap */
 365         return ext4_block_set(bg_ref->fs->bdev, &block_bitmap);
 366 }
 367
 368 /**@brief Initialize i-node bitmap in block group.
 369  * @param bg_ref Reference to block group
 370  * @return Error code
 371  */
 372 static int ext4_fs_init_inode_bitmap(struct ext4_block_group_ref *bg_ref)
 373 {
 374         int rc;
 375         struct ext4_sblock *sb = &bg_ref->fs->sb;
 376         struct ext4_bgroup *bg = bg_ref->block_group;
 377
 378         /* Load bitmap */
 379         ext4_fsblk_t bitmap_block_addr = ext4_bg_get_inode_bitmap(bg, sb);
 380
 381         struct ext4_block b;
 382         rc = ext4_block_get_noread(bg_ref->fs->bdev, &b, bitmap_block_addr);
 383         if (rc != EOK)
 384                 return rc;
 385
 386         /* Initialize all bitmap bits to zero */
 387         uint32_t block_size = ext4_sb_get_block_size(sb);
 388         uint32_t inodes_per_group = ext4_get32(sb, inodes_per_group);
 389
 390         memset(b.data, 0, (inodes_per_group + 7) / 8);
 391
 392         uint32_t start_bit = inodes_per_group;
 393         uint32_t end_bit = block_size * 8;
 394
 395         uint32_t i;
 396         for (i = start_bit; i < ((start_bit + 7) & ~7UL); i++)
 397                 ext4_bmap_bit_set(b.data, i);
 398
 399         if (i < end_bit)
 400                 memset(b.data + (i >> 3), 0xff, (end_bit - i) >> 3);
 401
 402         b.dirty = true;
 403
 404         ext4_ialloc_set_bitmap_csum(sb, bg, b.data);
 405         bg_ref->dirty = true;
 406
 407         /* Save bitmap */
 408         return ext4_block_set(bg_ref->fs->bdev, &b);
 409 }
 410
 411 /**@brief Initialize i-node table in block group.
 412  * @param bg_ref Reference to block group
 413  * @return Error code
 414  */
 415 static int ext4_fs_init_inode_table(struct ext4_block_group_ref *bg_ref)
 416 {
 417         struct ext4_sblock *sb = &bg_ref->fs->sb;
 418         struct ext4_bgroup *bg = bg_ref->block_group;
 419
 420         uint32_t inode_size = ext4_get32(sb, inode_size);
 421         uint32_t block_size = ext4_sb_get_block_size(sb);
 422         uint32_t inodes_per_block = block_size / inode_size;
 423         uint32_t inodes_in_group = ext4_inodes_in_group_cnt(sb, bg_ref->index);
 424         uint32_t table_blocks = inodes_in_group / inodes_per_block;
 425         ext4_fsblk_t fblock;
 426
 427         if (inodes_in_group % inodes_per_block)
 428                 table_blocks++;
 429
 430         /* Compute initialization bounds */
 431         ext4_fsblk_t first_block = ext4_bg_get_inode_table_first_block(bg, sb);
 432
 433         ext4_fsblk_t last_block = first_block + table_blocks - 1;
 434
 435         /* Initialization of all itable blocks */
 436         for (fblock = first_block; fblock <= last_block; ++fblock) {
 437                 struct ext4_block b;
 438                 int rc = ext4_block_get_noread(bg_ref->fs->bdev, &b, fblock);
 439                 if (rc != EOK)
 440                         return rc;
 441
 442                 memset(b.data, 0, block_size);
 443                 b.dirty = true;
 444
 445                 ext4_block_set(bg_ref->fs->bdev, &b);
 446                 if (rc != EOK)
 447                         return rc;
 448         }
 449
 450         return EOK;
 451 }
 452
 453 static ext4_fsblk_t ext4_fs_get_descriptor_block(struct ext4_sblock *s,
 454                                              uint32_t bgid,
 455                                              uint32_t dsc_per_block)
 456 {
 457         uint32_t first_meta_bg, dsc_id;
 458         int has_super = 0;
 459         dsc_id = bgid / dsc_per_block;
 460         first_meta_bg = ext4_sb_first_meta_bg(s);
 461
 462         bool meta_bg = ext4_sb_feature_incom(s, EXT4_FINCOM_META_BG);
 463
 464         if (!meta_bg || dsc_id < first_meta_bg)
 465                 return ext4_get32(s, first_data_block) + dsc_id + 1;
 466
 467         if (ext4_sb_is_super_in_bg(s, bgid))
 468                 has_super = 1;
 469
 470         return (has_super + ext4_fs_first_bg_block_no(s, bgid));
 471 }
 472
 473 /**@brief  Compute checksum of block group descriptor.
 474  * @param sb   Superblock
 475  * @param bgid Index of block group in the filesystem
 476  * @param bg   Block group to compute checksum for
 477  * @return Checksum value
 478  */
 479 static uint16_t ext4_fs_bg_checksum(struct ext4_sblock *sb, uint32_t bgid,
 480                                     struct ext4_bgroup *bg)
 481 {
 482         /* If checksum not supported, 0 will be returned */
 483         uint16_t crc = 0;
 484 #if CONFIG_META_CSUM_ENABLE
 485         /* Compute the checksum only if the filesystem supports it */
 486         if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {
 487                 /* Use metadata_csum algorithm instead */
 488                 uint32_t le32_bgid = to_le32(bgid);
 489                 uint32_t orig_checksum, checksum;
 490
 491                 /* Preparation: temporarily set bg checksum to 0 */
 492                 orig_checksum = bg->checksum;
 493                 bg->checksum = 0;
 494
 495                 /* First calculate crc32 checksum against fs uuid */
 496                 checksum = ext4_crc32c(EXT4_CRC32_INIT, sb->uuid,
 497                                 sizeof(sb->uuid));
 498                 /* Then calculate crc32 checksum against bgid */
 499                 checksum = ext4_crc32c(checksum, &le32_bgid, sizeof(bgid));
 500                 /* Finally calculate crc32 checksum against block_group_desc */
 501                 checksum = ext4_crc32c(checksum, bg, ext4_sb_get_desc_size(sb));
 502                 bg->checksum = orig_checksum;
 503
 504                 crc = checksum & 0xFFFF;
 505                 return crc;
 506         }
 507 #endif
 508         if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_GDT_CSUM)) {
 509                 uint8_t *base = (uint8_t *)bg;
 510                 uint8_t *checksum = (uint8_t *)&bg->checksum;
 511
 512                 uint32_t offset = (uint32_t)(checksum - base);
 513
 514                 /* Convert block group index to little endian */
 515                 uint32_t le_group = to_le32(bgid);
 516
 517                 /* Initialization */
 518                 crc = ext4_bg_crc16(~0, sb->uuid, sizeof(sb->uuid));
 519
 520                 /* Include index of block group */
 521                 crc =
 522                     ext4_bg_crc16(crc, (uint8_t *)&le_group, sizeof(le_group));
 523
 524                 /* Compute crc from the first part (stop before checksum field)
 525                  */
 526                 crc = ext4_bg_crc16(crc, (uint8_t *)bg, offset);
 527
 528                 /* Skip checksum */
 529                 offset += sizeof(bg->checksum);
 530
 531                 /* Checksum of the rest of block group descriptor */
 532                 if ((ext4_sb_feature_incom(sb, EXT4_FINCOM_64BIT)) &&
 533                     (offset < ext4_sb_get_desc_size(sb))) {
 534
 535                         const uint8_t *start = ((uint8_t *)bg) + offset;
 536                         size_t len = ext4_sb_get_desc_size(sb) - offset;
 537                         crc = ext4_bg_crc16(crc, start, len);
 538                 }
 539         }
 540         return crc;
 541 }
 542
 543 #if CONFIG_META_CSUM_ENABLE
 544 static bool ext4_fs_verify_bg_csum(struct ext4_sblock *sb,
 545                                    uint32_t bgid,
 546                                    struct ext4_bgroup *bg)
 547 {
 548         if (!ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM))
 549                 return true;
 550
 551         return ext4_fs_bg_checksum(sb, bgid, bg) == to_le16(bg->checksum);
 552 }
 553 #else
 554 #define ext4_fs_verify_bg_csum(...) true
 555 #endif
 556
 557 int ext4_fs_get_block_group_ref(struct ext4_fs *fs, uint32_t bgid,
 558                                 struct ext4_block_group_ref *ref)
 559 {
 560         /* Compute number of descriptors, that fits in one data block */
 561         uint32_t block_size = ext4_sb_get_block_size(&fs->sb);
 562         uint32_t dsc_cnt = block_size / ext4_sb_get_desc_size(&fs->sb);
 563
 564         /* Block group descriptor table starts at the next block after
 565          * superblock */
 566         uint64_t block_id = ext4_fs_get_descriptor_block(&fs->sb, bgid, dsc_cnt);
 567
 568         uint32_t offset = (bgid % dsc_cnt) * ext4_sb_get_desc_size(&fs->sb);
 569
 570         int rc = ext4_block_get(fs->bdev, &ref->block, block_id);
 571         if (rc != EOK)
 572                 return rc;
 573
 574         ref->block_group = (void *)(ref->block.data + offset);
 575         ref->fs = fs;
 576         ref->index = bgid;
 577         ref->dirty = false;
 578         struct ext4_bgroup *bg = ref->block_group;
 579
 580         if (!ext4_fs_verify_bg_csum(&fs->sb, bgid, bg)) {
 581                 ext4_dbg(DEBUG_FS,
 582                          DBG_WARN "Block group descriptor checksum failed."
 583                          "Block group index: %" PRIu32"\n",
 584                          bgid);
 585         }
 586
 587         if (ext4_bg_has_flag(bg, EXT4_BLOCK_GROUP_BLOCK_UNINIT)) {
 588                 rc = ext4_fs_init_block_bitmap(ref);
 589                 if (rc != EOK) {
 590                         ext4_block_set(fs->bdev, &ref->block);
 591                         return rc;
 592                 }
 593                 ext4_bg_clear_flag(bg, EXT4_BLOCK_GROUP_BLOCK_UNINIT);
 594                 ref->dirty = true;
 595         }
 596
 597         if (ext4_bg_has_flag(bg, EXT4_BLOCK_GROUP_INODE_UNINIT)) {
 598                 rc = ext4_fs_init_inode_bitmap(ref);
 599                 if (rc != EOK) {
 600                         ext4_block_set(ref->fs->bdev, &ref->block);
 601                         return rc;
 602                 }
 603
 604                 ext4_bg_clear_flag(bg, EXT4_BLOCK_GROUP_INODE_UNINIT);
 605
 606                 if (!ext4_bg_has_flag(bg, EXT4_BLOCK_GROUP_ITABLE_ZEROED)) {
 607                         rc = ext4_fs_init_inode_table(ref);
 608                         if (rc != EOK) {
 609                                 ext4_block_set(fs->bdev, &ref->block);
 610                                 return rc;
 611                         }
 612
 613                         ext4_bg_set_flag(bg, EXT4_BLOCK_GROUP_ITABLE_ZEROED);
 614                 }
 615
 616                 ref->dirty = true;
 617         }
 618
 619         return EOK;
 620 }
 621
 622 int ext4_fs_put_block_group_ref(struct ext4_block_group_ref *ref)
 623 {
 624         /* Check if reference modified */
 625         if (ref->dirty) {
 626                 /* Compute new checksum of block group */
 627                 uint16_t cs;
 628                 cs = ext4_fs_bg_checksum(&ref->fs->sb, ref->index,
 629                                          ref->block_group);
 630                 ref->block_group->checksum = to_le16(cs);
 631
 632                 /* Mark block dirty for writing changes to physical device */
 633                 ref->block.dirty = true;
 634         }
 635
 636         /* Put back block, that contains block group descriptor */
 637         return ext4_block_set(ref->fs->bdev, &ref->block);
 638 }
 639
 640 #if CONFIG_META_CSUM_ENABLE
 641 static uint32_t ext4_fs_inode_checksum(struct ext4_inode_ref *inode_ref)
 642 {
 643         uint32_t checksum = 0;
 644         struct ext4_sblock *sb = &inode_ref->fs->sb;
 645         uint16_t inode_size = ext4_get16(sb, inode_size);
 646
 647         if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {
 648                 uint32_t orig_checksum;
 649
 650                 uint32_t ino_index = to_le32(inode_ref->index);
 651                 uint32_t ino_gen =
 652                         to_le32(ext4_inode_get_generation(inode_ref->inode));
 653
 654                 /* Preparation: temporarily set bg checksum to 0 */
 655                 orig_checksum = ext4_inode_get_csum(sb, inode_ref->inode);
 656                 ext4_inode_set_csum(sb, inode_ref->inode, 0);
 657
 658                 /* First calculate crc32 checksum against fs uuid */
 659                 checksum = ext4_crc32c(EXT4_CRC32_INIT, sb->uuid,
 660                                        sizeof(sb->uuid));
 661                 /* Then calculate crc32 checksum against inode number
 662                  * and inode generation */
 663                 checksum = ext4_crc32c(checksum, &ino_index, sizeof(ino_index));
 664                 checksum = ext4_crc32c(checksum, &ino_gen, sizeof(ino_gen));
 665                 /* Finally calculate crc32 checksum against
 666                  * the entire inode */
 667                 checksum = ext4_crc32c(checksum, inode_ref->inode, inode_size);
 668                 ext4_inode_set_csum(sb, inode_ref->inode, orig_checksum);
 669
 670                 /* If inode size is not large enough to hold the
 671                  * upper 16bit of the checksum */
 672                 if (inode_size == EXT4_GOOD_OLD_INODE_SIZE)
 673                         checksum &= 0xFFFF;
 674
 675         }
 676         return checksum;
 677 }
 678 #else
 679 #define ext4_fs_inode_checksum(...) 0
 680 #endif
 681
 682 static void ext4_fs_set_inode_checksum(struct ext4_inode_ref *inode_ref)
 683 {
 684         struct ext4_sblock *sb = &inode_ref->fs->sb;
 685         if (!ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM))
 686                 return;
 687
 688         uint32_t csum = ext4_fs_inode_checksum(inode_ref);
 689         ext4_inode_set_csum(sb, inode_ref->inode, csum);
 690 }
 691
 692 #if CONFIG_META_CSUM_ENABLE
 693 static bool ext4_fs_verify_inode_csum(struct ext4_inode_ref *inode_ref)
 694 {
 695         struct ext4_sblock *sb = &inode_ref->fs->sb;
 696         if (!ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM))
 697                 return true;
 698
 699         return ext4_inode_get_csum(sb, inode_ref->inode) ==
 700                 ext4_fs_inode_checksum(inode_ref);
 701 }
 702 #else
 703 #define ext4_fs_verify_inode_csum(...) true
 704 #endif
 705
 706 static int
 707 __ext4_fs_get_inode_ref(struct ext4_fs *fs, uint32_t index,
 708                         struct ext4_inode_ref *ref,
 709                         bool initialized)
 710 {
 711         /* Compute number of i-nodes, that fits in one data block */
 712         uint32_t inodes_per_group = ext4_get32(&fs->sb, inodes_per_group);
 713
 714         /*
 715          * Inode numbers are 1-based, but it is simpler to work with 0-based
 716          * when computing indices
 717          */
 718         index -= 1;
 719         uint32_t block_group = index / inodes_per_group;
 720         uint32_t offset_in_group = index % inodes_per_group;
 721
 722         /* Load block group, where i-node is located */
 723         struct ext4_block_group_ref bg_ref;
 724
 725         int rc = ext4_fs_get_block_group_ref(fs, block_group, &bg_ref);
 726         if (rc != EOK) {
 727                 return rc;
 728         }
 729
 730         /* Load block address, where i-node table is located */
 731         uint32_t inode_table_start =
 732             ext4_bg_get_inode_table_first_block(bg_ref.block_group, &fs->sb);
 733
 734         /* Put back block group reference (not needed more) */
 735         rc = ext4_fs_put_block_group_ref(&bg_ref);
 736         if (rc != EOK) {
 737                 return rc;
 738         }
 739
 740         /* Compute position of i-node in the block group */
 741         uint16_t inode_size = ext4_get16(&fs->sb, inode_size);
 742         uint32_t block_size = ext4_sb_get_block_size(&fs->sb);
 743         uint32_t byte_offset_in_group = offset_in_group * inode_size;
 744
 745         /* Compute block address */
 746         ext4_fsblk_t block_id =
 747             inode_table_start + (byte_offset_in_group / block_size);
 748
 749         rc = ext4_block_get(fs->bdev, &ref->block, block_id);
 750         if (rc != EOK) {
 751                 return rc;
 752         }
 753
 754         /* Compute position of i-node in the data block */
 755         uint32_t offset_in_block = byte_offset_in_group % block_size;
 756         ref->inode = (struct ext4_inode *)(ref->block.data + offset_in_block);
 757
 758         /* We need to store the original value of index in the reference */
 759         ref->index = index + 1;
 760         ref->fs = fs;
 761         ref->dirty = false;
 762
 763         if (initialized && !ext4_fs_verify_inode_csum(ref)) {
 764                 ext4_dbg(DEBUG_FS,
 765                         DBG_WARN "Inode checksum failed."
 766                         "Inode: %" PRIu32"\n",
 767                         ref->index);
 768         }
 769
 770         return EOK;
 771 }
 772
 773 int ext4_fs_get_inode_ref(struct ext4_fs *fs, uint32_t index,
 774                           struct ext4_inode_ref *ref)
 775 {
 776         return __ext4_fs_get_inode_ref(fs, index, ref, true);
 777 }
 778
 779 int ext4_fs_put_inode_ref(struct ext4_inode_ref *ref)
 780 {
 781         /* Check if reference modified */
 782         if (ref->dirty) {
 783                 /* Mark block dirty for writing changes to physical device */
 784                 ext4_fs_set_inode_checksum(ref);
 785                 ref->block.dirty = true;
 786         }
 787
 788         /* Put back block, that contains i-node */
 789         return ext4_block_set(ref->fs->bdev, &ref->block);
 790 }
 791
 792 void ext4_fs_inode_blocks_init(struct ext4_fs *fs,
 793                                struct ext4_inode_ref *inode_ref)
 794 {
 795         int i;
 796         struct ext4_inode *inode = inode_ref->inode;
 797
 798         for (i = 0; i < EXT4_INODE_BLOCKS; i++)
 799                 inode->blocks[i] = 0;
 800
 801         (void)fs;
 802 #if CONFIG_EXTENT_ENABLE
 803         /* Initialize extents if needed */
 804         if (ext4_sb_feature_incom(&fs->sb, EXT4_FINCOM_EXTENTS)) {
 805                 ext4_inode_set_flag(inode, EXT4_INODE_FLAG_EXTENTS);
 806
 807                 /* Initialize extent root header */
 808                 ext4_extent_tree_init(inode_ref);
 809         }
 810 #endif
 811 }
 812
 813 uint32_t ext4_fs_correspond_inode_mode(int filetype)
 814 {
 815         switch (filetype) {
 816         case EXT4_DIRENTRY_DIR:
 817                 return EXT4_INODE_MODE_DIRECTORY;
 818         case EXT4_DIRENTRY_REG_FILE:
 819                 return EXT4_INODE_MODE_FILE;
 820         case EXT4_DIRENTRY_SYMLINK:
 821                 return EXT4_INODE_MODE_SOFTLINK;
 822         default:
 823                 /* FIXME: right now we only support 3 file type. */
 824                 ext4_assert(0);
 825         }
 826         return 0;
 827 }
 828
 829 int ext4_fs_alloc_inode(struct ext4_fs *fs, struct ext4_inode_ref *inode_ref,
 830                         int filetype)
 831 {
 832         /* Check if newly allocated i-node will be a directory */
 833         bool is_dir;
 834         uint16_t inode_size = ext4_get16(&fs->sb, inode_size);
 835
 836         is_dir = (filetype == EXT4_DIRENTRY_DIR);
 837
 838         /* Allocate inode by allocation algorithm */
 839         uint32_t index;
 840         int rc = ext4_ialloc_alloc_inode(fs, &index, is_dir);
 841         if (rc != EOK)
 842                 return rc;
 843
 844         /* Load i-node from on-disk i-node table */
 845         rc = __ext4_fs_get_inode_ref(fs, index, inode_ref, false);
 846         if (rc != EOK) {
 847                 ext4_ialloc_free_inode(fs, index, is_dir);
 848                 return rc;
 849         }
 850
 851         /* Initialize i-node */
 852         struct ext4_inode *inode = inode_ref->inode;
 853
 854         uint32_t mode;
 855         if (is_dir) {
 856                 /*
 857                  * Default directory permissions to be compatible with other
 858                  * systems
 859                  * 0777 (octal) == rwxrwxrwx
 860                  */
 861
 862                 mode = 0777;
 863                 mode |= EXT4_INODE_MODE_DIRECTORY;
 864         } else {
 865                 /*
 866                  * Default file permissions to be compatible with other systems
 867                  * 0666 (octal) == rw-rw-rw-
 868                  */
 869
 870                 mode = 0666;
 871                 mode |= ext4_fs_correspond_inode_mode(filetype);
 872         }
 873         ext4_inode_set_mode(&fs->sb, inode, mode);
 874
 875         ext4_inode_set_links_count(inode, 0);
 876         ext4_inode_set_uid(inode, 0);
 877         ext4_inode_set_gid(inode, 0);
 878         ext4_inode_set_size(inode, 0);
 879         ext4_inode_set_access_time(inode, 0);
 880         ext4_inode_set_change_inode_time(inode, 0);
 881         ext4_inode_set_modification_time(inode, 0);
 882         ext4_inode_set_deletion_time(inode, 0);
 883         ext4_inode_set_blocks_count(&fs->sb, inode, 0);
 884         ext4_inode_set_flags(inode, 0);
 885         ext4_inode_set_generation(inode, 0);
 886         if (inode_size > EXT4_GOOD_OLD_INODE_SIZE) {
 887                 uint16_t off = offsetof(struct ext4_inode, extra_isize);
 888                 uint16_t size = sizeof(struct ext4_inode) - off;
 889                 ext4_inode_set_extra_isize(inode, size);
 890         }
 891
 892         /* Reset blocks array. For symbolic link inode, just
 893          * fill in blocks with 0 */
 894         if (ext4_inode_is_type(&fs->sb, inode, EXT4_INODE_MODE_SOFTLINK)) {
 895                 for (int i = 0; i < EXT4_INODE_BLOCKS; i++)
 896                         inode->blocks[i] = 0;
 897
 898         } else {
 899                 ext4_fs_inode_blocks_init(fs, inode_ref);
 900         }
 901
 902         inode_ref->dirty = true;
 903
 904         return EOK;
 905 }
 906
 907 int ext4_fs_free_inode(struct ext4_inode_ref *inode_ref)
 908 {
 909         struct ext4_fs *fs = inode_ref->fs;
 910         uint32_t offset;
 911         uint32_t suboff;
 912         int rc;
 913 #if CONFIG_EXTENT_ENABLE
 914         /* For extents must be data block destroyed by other way */
 915         if ((ext4_sb_feature_incom(&fs->sb, EXT4_FINCOM_EXTENTS)) &&
 916             (ext4_inode_has_flag(inode_ref->inode, EXT4_INODE_FLAG_EXTENTS))) {
 917                 /* Data structures are released during truncate operation... */
 918                 goto finish;
 919         }
 920 #endif
 921         /* Release all indirect (no data) blocks */
 922
 923         /* 1) Single indirect */
 924         ext4_fsblk_t fblock = ext4_inode_get_indirect_block(inode_ref->inode, 0);
 925         if (fblock != 0) {
 926                 int rc = ext4_balloc_free_block(inode_ref, fblock);
 927                 if (rc != EOK)
 928                         return rc;
 929
 930                 ext4_inode_set_indirect_block(inode_ref->inode, 0, 0);
 931         }
 932
 933         uint32_t block_size = ext4_sb_get_block_size(&fs->sb);
 934         uint32_t count = block_size / sizeof(uint32_t);
 935
 936         struct ext4_block block;
 937
 938         /* 2) Double indirect */
 939         fblock = ext4_inode_get_indirect_block(inode_ref->inode, 1);
 940         if (fblock != 0) {
 941                 int rc = ext4_block_get(fs->bdev, &block, fblock);
 942                 if (rc != EOK)
 943                         return rc;
 944
 945                 ext4_fsblk_t ind_block;
 946                 for (offset = 0; offset < count; ++offset) {
 947                         ind_block = to_le32(((uint32_t *)block.data)[offset]);
 948
 949                         if (ind_block == 0)
 950                                 continue;
 951                         rc = ext4_balloc_free_block(inode_ref, ind_block);
 952                         if (rc != EOK) {
 953                                 ext4_block_set(fs->bdev, &block);
 954                                 return rc;
 955                         }
 956
 957                 }
 958
 959                 ext4_block_set(fs->bdev, &block);
 960                 rc = ext4_balloc_free_block(inode_ref, fblock);
 961                 if (rc != EOK)
 962                         return rc;
 963
 964                 ext4_inode_set_indirect_block(inode_ref->inode, 1, 0);
 965         }
 966
 967         /* 3) Tripple indirect */
 968         struct ext4_block subblock;
 969         fblock = ext4_inode_get_indirect_block(inode_ref->inode, 2);
 970         if (fblock == 0)
 971                 goto finish;
 972         rc = ext4_block_get(fs->bdev, &block, fblock);
 973         if (rc != EOK)
 974                 return rc;
 975
 976         ext4_fsblk_t ind_block;
 977         for (offset = 0; offset < count; ++offset) {
 978                 ind_block = to_le32(((uint32_t *)block.data)[offset]);
 979
 980                 if (ind_block == 0)
 981                         continue;
 982                 rc = ext4_block_get(fs->bdev, &subblock,
 983                                 ind_block);
 984                 if (rc != EOK) {
 985                         ext4_block_set(fs->bdev, &block);
 986                         return rc;
 987                 }
 988
 989                 ext4_fsblk_t ind_subblk;
 990                 for (suboff = 0; suboff < count; ++suboff) {
 991                         ind_subblk = to_le32(((uint32_t *)subblock.data)[suboff]);
 992
 993                         if (ind_subblk == 0)
 994                                 continue;
 995                         rc = ext4_balloc_free_block(inode_ref, ind_subblk);
 996                         if (rc != EOK) {
 997                                 ext4_block_set(fs->bdev, &subblock);
 998                                 ext4_block_set(fs->bdev, &block);
 999                                 return rc;
1000                         }
1001
1002                 }
1003
1004                 ext4_block_set(fs->bdev, &subblock);
1005
1006                 rc = ext4_balloc_free_block(inode_ref,
1007                                 ind_block);
1008                 if (rc != EOK) {
1009                         ext4_block_set(fs->bdev, &block);
1010                         return rc;
1011                 }
1012
1013         }
1014
1015         ext4_block_set(fs->bdev, &block);
1016         rc = ext4_balloc_free_block(inode_ref, fblock);
1017         if (rc != EOK)
1018                 return rc;
1019
1020         ext4_inode_set_indirect_block(inode_ref->inode, 2, 0);
1021 finish:
1022         /* Mark inode dirty for writing to the physical device */
1023         inode_ref->dirty = true;
1024
1025         /* Free block with extended attributes if present */
1026         ext4_fsblk_t xattr_block =
1027             ext4_inode_get_file_acl(inode_ref->inode, &fs->sb);
1028         if (xattr_block) {
1029                 int rc = ext4_balloc_free_block(inode_ref, xattr_block);
1030                 if (rc != EOK)
1031                         return rc;
1032
1033                 ext4_inode_set_file_acl(inode_ref->inode, &fs->sb, 0);
1034         }
1035
1036         /* Free inode by allocator */
1037         if (ext4_inode_is_type(&fs->sb, inode_ref->inode,
1038                                EXT4_INODE_MODE_DIRECTORY))
1039                 rc = ext4_ialloc_free_inode(fs, inode_ref->index, true);
1040         else
1041                 rc = ext4_ialloc_free_inode(fs, inode_ref->index, false);
1042
1043         return rc;
1044 }
1045
1046
1047 /**@brief Release data block from i-node
1048  * @param inode_ref I-node to release block from
1049  * @param iblock    Logical block to be released
1050  * @return Error code
1051  */
1052 static int ext4_fs_release_inode_block(struct ext4_inode_ref *inode_ref,
1053                                 uint32_t iblock)
1054 {
1055         ext4_fsblk_t fblock;
1056
1057         struct ext4_fs *fs = inode_ref->fs;
1058
1059         /* Extents are handled otherwise = there is not support in this function
1060          */
1061         ext4_assert(!(
1062             ext4_sb_feature_incom(&fs->sb, EXT4_FINCOM_EXTENTS) &&
1063             (ext4_inode_has_flag(inode_ref->inode, EXT4_INODE_FLAG_EXTENTS))));
1064
1065         struct ext4_inode *inode = inode_ref->inode;
1066
1067         /* Handle simple case when we are dealing with direct reference */
1068         if (iblock < EXT4_INODE_DIRECT_BLOCK_COUNT) {
1069                 fblock = ext4_inode_get_direct_block(inode, iblock);
1070
1071                 /* Sparse file */
1072                 if (fblock == 0)
1073                         return EOK;
1074
1075                 ext4_inode_set_direct_block(inode, iblock, 0);
1076                 return ext4_balloc_free_block(inode_ref, fblock);
1077         }
1078
1079         /* Determine the indirection level needed to get the desired block */
1080         unsigned int level = 0;
1081         unsigned int i;
1082         for (i = 1; i < 4; i++) {
1083                 if (iblock < fs->inode_block_limits[i]) {
1084                         level = i;
1085                         break;
1086                 }
1087         }
1088
1089         if (level == 0)
1090                 return EIO;
1091
1092         /* Compute offsets for the topmost level */
1093         uint64_t block_offset_in_level =
1094             iblock - fs->inode_block_limits[level - 1];
1095         ext4_fsblk_t current_block =
1096             ext4_inode_get_indirect_block(inode, level - 1);
1097         uint32_t offset_in_block =
1098             block_offset_in_level / fs->inode_blocks_per_level[level - 1];
1099
1100         /*
1101          * Navigate through other levels, until we find the block number
1102          * or find null reference meaning we are dealing with sparse file
1103          */
1104         struct ext4_block block;
1105
1106         while (level > 0) {
1107
1108                 /* Sparse check */
1109                 if (current_block == 0)
1110                         return EOK;
1111
1112                 int rc = ext4_block_get(fs->bdev, &block, current_block);
1113                 if (rc != EOK)
1114                         return rc;
1115
1116                 current_block =
1117                     to_le32(((uint32_t *)block.data)[offset_in_block]);
1118
1119                 /* Set zero if physical data block address found */
1120                 if (level == 1) {
1121                         ((uint32_t *)block.data)[offset_in_block] = to_le32(0);
1122                         block.dirty = true;
1123                 }
1124
1125                 rc = ext4_block_set(fs->bdev, &block);
1126                 if (rc != EOK)
1127                         return rc;
1128
1129                 level--;
1130
1131                 /*
1132                  * If we are on the last level, break here as
1133                  * there is no next level to visit
1134                  */
1135                 if (level == 0)
1136                         break;
1137
1138                 /* Visit the next level */
1139                 block_offset_in_level %= fs->inode_blocks_per_level[level];
1140                 offset_in_block = block_offset_in_level /
1141                                   fs->inode_blocks_per_level[level - 1];
1142         }
1143
1144         fblock = current_block;
1145         if (fblock == 0)
1146                 return EOK;
1147
1148         /* Physical block is not referenced, it can be released */
1149         return ext4_balloc_free_block(inode_ref, fblock);
1150 }
1151
1152 int ext4_fs_truncate_inode(struct ext4_inode_ref *inode_ref, uint64_t new_size)
1153 {
1154         struct ext4_sblock *sb = &inode_ref->fs->sb;
1155         uint32_t i;
1156         int r;
1157
1158         /* Check flags, if i-node can be truncated */
1159         if (!ext4_inode_can_truncate(sb, inode_ref->inode))
1160                 return EINVAL;
1161
1162         /* If sizes are equal, nothing has to be done. */
1163         uint64_t old_size = ext4_inode_get_size(sb, inode_ref->inode);
1164         if (old_size == new_size)
1165                 return EOK;
1166
1167         /* It's not supported to make the larger file by truncate operation */
1168         if (old_size < new_size)
1169                 return EINVAL;
1170
1171         bool v;
1172         v = ext4_inode_is_type(sb, inode_ref->inode, EXT4_INODE_MODE_SOFTLINK);
1173         if (v && old_size < sizeof(inode_ref->inode->blocks) &&
1174             !ext4_inode_get_blocks_count(sb, inode_ref->inode)) {
1175                 char *content = (char *)inode_ref->inode->blocks + new_size;
1176                 memset(content , 0, sizeof(inode_ref->inode->blocks) - new_size);
1177                 ext4_inode_set_size(inode_ref->inode, new_size);
1178                 inode_ref->dirty = true;
1179
1180                 return EOK;
1181         }
1182
1183         /* Compute how many blocks will be released */
1184         uint32_t block_size = ext4_sb_get_block_size(sb);
1185         uint32_t new_blocks_cnt = (new_size + block_size - 1) / block_size;
1186         uint32_t old_blocks_cnt = (old_size + block_size - 1) / block_size;
1187         uint32_t diff_blocks_cnt = old_blocks_cnt - new_blocks_cnt;
1188 #if CONFIG_EXTENT_ENABLE
1189         if ((ext4_sb_feature_incom(sb, EXT4_FINCOM_EXTENTS)) &&
1190             (ext4_inode_has_flag(inode_ref->inode, EXT4_INODE_FLAG_EXTENTS))) {
1191
1192                 /* Extents require special operation */
1193                 if (diff_blocks_cnt) {
1194                         r = ext4_extent_remove_space(inode_ref, new_blocks_cnt,
1195                                                      EXT_MAX_BLOCKS);
1196                         if (r != EOK)
1197                                 return r;
1198
1199                 }
1200         } else
1201 #endif
1202         {
1203                 /* Release data blocks from the end of file */
1204
1205                 /* Starting from 1 because of logical blocks are numbered from 0
1206                  */
1207                 for (i = 0; i < diff_blocks_cnt; ++i) {
1208                         r = ext4_fs_release_inode_block(inode_ref,
1209                                                         new_blocks_cnt + i);
1210                         if (r != EOK)
1211                                 return r;
1212                 }
1213         }
1214
1215         /* Update i-node */
1216         ext4_inode_set_size(inode_ref->inode, new_size);
1217         inode_ref->dirty = true;
1218
1219         return EOK;
1220 }
1221
1222 /**@brief Compute 'goal' for inode index
1223  * @param inode_ref Reference to inode, to allocate block for
1224  * @return goal
1225  */
1226 ext4_fsblk_t ext4_fs_inode_to_goal_block(struct ext4_inode_ref *inode_ref)
1227 {
1228         uint32_t grp_inodes = ext4_get32(&inode_ref->fs->sb, inodes_per_group);
1229         return (inode_ref->index - 1) / grp_inodes;
1230 }
1231
1232 /**@brief Compute 'goal' for allocation algorithm (For blockmap).
1233  * @param inode_ref Reference to inode, to allocate block for
1234  * @param goal
1235  * @return error code
1236  */
1237 int ext4_fs_indirect_find_goal(struct ext4_inode_ref *inode_ref,
1238                                ext4_fsblk_t *goal)
1239 {
1240         int r;
1241         struct ext4_sblock *sb = &inode_ref->fs->sb;
1242         *goal = 0;
1243
1244         uint64_t inode_size = ext4_inode_get_size(sb, inode_ref->inode);
1245         uint32_t block_size = ext4_sb_get_block_size(sb);
1246         uint32_t iblock_cnt = inode_size / block_size;
1247
1248         if (inode_size % block_size != 0)
1249                 iblock_cnt++;
1250
1251         /* If inode has some blocks, get last block address + 1 */
1252         if (iblock_cnt > 0) {
1253                 r = ext4_fs_get_inode_data_block_index(inode_ref, iblock_cnt - 1,
1254                                                        goal, false);
1255                 if (r != EOK)
1256                         return r;
1257
1258                 if (*goal != 0) {
1259                         (*goal)++;
1260                         return r;
1261                 }
1262
1263                 /* If goal == 0, sparse file -> continue */
1264         }
1265
1266         /* Identify block group of inode */
1267
1268         uint32_t inodes_per_bg = ext4_get32(sb, inodes_per_group);
1269         uint32_t block_group = (inode_ref->index - 1) / inodes_per_bg;
1270         block_size = ext4_sb_get_block_size(sb);
1271
1272         /* Load block group reference */
1273         struct ext4_block_group_ref bg_ref;
1274         r = ext4_fs_get_block_group_ref(inode_ref->fs, block_group, &bg_ref);
1275         if (r != EOK)
1276                 return r;
1277
1278         struct ext4_bgroup *bg = bg_ref.block_group;
1279
1280         /* Compute indexes */
1281         uint32_t bg_count = ext4_block_group_cnt(sb);
1282         ext4_fsblk_t itab_first_block = ext4_bg_get_inode_table_first_block(bg, sb);
1283         uint16_t itab_item_size = ext4_get16(sb, inode_size);
1284         uint32_t itab_bytes;
1285
1286         /* Check for last block group */
1287         if (block_group < bg_count - 1) {
1288                 itab_bytes = inodes_per_bg * itab_item_size;
1289         } else {
1290                 /* Last block group could be smaller */
1291                 uint32_t inodes_cnt = ext4_get32(sb, inodes_count);
1292
1293                 itab_bytes = (inodes_cnt - ((bg_count - 1) * inodes_per_bg));
1294                 itab_bytes *= itab_item_size;
1295         }
1296
1297         ext4_fsblk_t inode_table_blocks = itab_bytes / block_size;
1298
1299         if (itab_bytes % block_size)
1300                 inode_table_blocks++;
1301
1302         *goal = itab_first_block + inode_table_blocks;
1303
1304         return ext4_fs_put_block_group_ref(&bg_ref);
1305 }
1306
1307 static int ext4_fs_get_inode_data_block_idx(struct ext4_inode_ref *inode_ref,
1308                                        uint64_t iblock, ext4_fsblk_t *fblock,
1309                                        bool extent_create,
1310                                        bool support_unwritten __unused)
1311 {
1312         struct ext4_fs *fs = inode_ref->fs;
1313
1314         /* For empty file is situation simple */
1315         if (ext4_inode_get_size(&fs->sb, inode_ref->inode) == 0) {
1316                 *fblock = 0;
1317                 return EOK;
1318         }
1319
1320         ext4_fsblk_t current_block;
1321
1322         (void)extent_create;
1323 #if CONFIG_EXTENT_ENABLE
1324         /* Handle i-node using extents */
1325         if ((ext4_sb_feature_incom(&fs->sb, EXT4_FINCOM_EXTENTS)) &&
1326             (ext4_inode_has_flag(inode_ref->inode, EXT4_INODE_FLAG_EXTENTS))) {
1327
1328                 ext4_fsblk_t current_fsblk;
1329                 int rc = ext4_extent_get_blocks(inode_ref, iblock, 1,
1330                                 &current_fsblk, extent_create, NULL);
1331                 if (rc != EOK)
1332                         return rc;
1333
1334                 current_block = current_fsblk;
1335                 *fblock = current_block;
1336
1337                 ext4_assert(*fblock || support_unwritten);
1338                 return EOK;
1339         }
1340 #endif
1341
1342         struct ext4_inode *inode = inode_ref->inode;
1343
1344         /* Direct block are read directly from array in i-node structure */
1345         if (iblock < EXT4_INODE_DIRECT_BLOCK_COUNT) {
1346                 current_block =
1347                     ext4_inode_get_direct_block(inode, (uint32_t)iblock);
1348                 *fblock = current_block;
1349                 return EOK;
1350         }
1351
1352         /* Determine indirection level of the target block */
1353         unsigned int l = 0;
1354         unsigned int i;
1355         for (i = 1; i < 4; i++) {
1356                 if (iblock < fs->inode_block_limits[i]) {
1357                         l = i;
1358                         break;
1359                 }
1360         }
1361
1362         if (l == 0)
1363                 return EIO;
1364
1365         /* Compute offsets for the topmost level */
1366         uint64_t blk_off_in_lvl =  iblock - fs->inode_block_limits[l - 1];
1367         current_block = ext4_inode_get_indirect_block(inode, l - 1);
1368         uint32_t off_in_blk = blk_off_in_lvl / fs->inode_blocks_per_level[l - 1];
1369
1370         /* Sparse file */
1371         if (current_block == 0) {
1372                 *fblock = 0;
1373                 return EOK;
1374         }
1375
1376         struct ext4_block block;
1377
1378         /*
1379          * Navigate through other levels, until we find the block number
1380          * or find null reference meaning we are dealing with sparse file
1381          */
1382         while (l > 0) {
1383                 /* Load indirect block */
1384                 int rc = ext4_block_get(fs->bdev, &block, current_block);
1385                 if (rc != EOK)
1386                         return rc;
1387
1388                 /* Read block address from indirect block */
1389                 current_block =
1390                     to_le32(((uint32_t *)block.data)[off_in_blk]);
1391
1392                 /* Put back indirect block untouched */
1393                 rc = ext4_block_set(fs->bdev, &block);
1394                 if (rc != EOK)
1395                         return rc;
1396
1397                 /* Check for sparse file */
1398                 if (current_block == 0) {
1399                         *fblock = 0;
1400                         return EOK;
1401                 }
1402
1403                 /* Jump to the next level */
1404                 l--;
1405
1406                 /* Termination condition - we have address of data block loaded
1407                  */
1408                 if (l == 0)
1409                         break;
1410
1411                 /* Visit the next level */
1412                 blk_off_in_lvl %= fs->inode_blocks_per_level[l];
1413                 off_in_blk = blk_off_in_lvl / fs->inode_blocks_per_level[l - 1];
1414         }
1415
1416         *fblock = current_block;
1417
1418         return EOK;
1419 }
1420
1421
1422 int ext4_fs_get_inode_data_block_index(struct ext4_inode_ref *inode_ref,
1423                                        uint64_t iblock, ext4_fsblk_t *fblock,
1424                                        bool support_unwritten)
1425 {
1426         return ext4_fs_get_inode_data_block_idx(inode_ref, iblock, fblock,
1427                         false, support_unwritten);
1428 }
1429
1430 int ext4_fs_init_inode_data_block_index(struct ext4_inode_ref *inode_ref,
1431                                        uint64_t iblock, ext4_fsblk_t *fblock)
1432 {
1433         return ext4_fs_get_inode_data_block_idx(inode_ref, iblock, fblock,
1434                         true, true);
1435 }
1436
1437 static int ext4_fs_set_inode_data_block_index(struct ext4_inode_ref *inode_ref,
1438                                        uint64_t iblock, ext4_fsblk_t fblock)
1439 {
1440         struct ext4_fs *fs = inode_ref->fs;
1441
1442 #if CONFIG_EXTENT_ENABLE
1443         /* Handle inode using extents */
1444         if ((ext4_sb_feature_incom(&fs->sb, EXT4_FINCOM_EXTENTS)) &&
1445             (ext4_inode_has_flag(inode_ref->inode, EXT4_INODE_FLAG_EXTENTS))) {
1446                 /* Not reachable */
1447                 return ENOTSUP;
1448         }
1449 #endif
1450
1451         /* Handle simple case when we are dealing with direct reference */
1452         if (iblock < EXT4_INODE_DIRECT_BLOCK_COUNT) {
1453                 ext4_inode_set_direct_block(inode_ref->inode, (uint32_t)iblock,
1454                                             (uint32_t)fblock);
1455                 inode_ref->dirty = true;
1456
1457                 return EOK;
1458         }
1459
1460         /* Determine the indirection level needed to get the desired block */
1461         unsigned int l = 0;
1462         unsigned int i;
1463         for (i = 1; i < 4; i++) {
1464                 if (iblock < fs->inode_block_limits[i]) {
1465                         l = i;
1466                         break;
1467                 }
1468         }
1469
1470         if (l == 0)
1471                 return EIO;
1472
1473         uint32_t block_size = ext4_sb_get_block_size(&fs->sb);
1474
1475         /* Compute offsets for the topmost level */
1476         uint64_t blk_off_in_lvl =  iblock - fs->inode_block_limits[l - 1];
1477         ext4_fsblk_t current_block =
1478                         ext4_inode_get_indirect_block(inode_ref->inode, l - 1);
1479         uint32_t off_in_blk = blk_off_in_lvl / fs->inode_blocks_per_level[l - 1];
1480
1481         ext4_fsblk_t new_blk;
1482
1483         struct ext4_block block;
1484         struct ext4_block new_block;
1485
1486         /* Is needed to allocate indirect block on the i-node level */
1487         if (current_block == 0) {
1488                 /* Allocate new indirect block */
1489                 ext4_fsblk_t goal;
1490                 int rc = ext4_fs_indirect_find_goal(inode_ref, &goal);
1491                 if (rc != EOK)
1492                         return rc;
1493
1494                 rc = ext4_balloc_alloc_block(inode_ref, goal, &new_blk);
1495                 if (rc != EOK)
1496                         return rc;
1497
1498                 /* Update i-node */
1499                 ext4_inode_set_indirect_block(inode_ref->inode, l - 1, new_blk);
1500                 inode_ref->dirty = true;
1501
1502                 /* Load newly allocated block */
1503                 rc = ext4_block_get_noread(fs->bdev, &new_block, new_blk);
1504                 if (rc != EOK) {
1505                         ext4_balloc_free_block(inode_ref, new_blk);
1506                         return rc;
1507                 }
1508
1509                 /* Initialize new block */
1510                 memset(new_block.data, 0, block_size);
1511                 new_block.dirty = true;
1512
1513                 /* Put back the allocated block */
1514                 rc = ext4_block_set(fs->bdev, &new_block);
1515                 if (rc != EOK)
1516                         return rc;
1517
1518                 current_block = new_blk;
1519         }
1520
1521         /*
1522          * Navigate through other levels, until we find the block number
1523          * or find null reference meaning we are dealing with sparse file
1524          */
1525         while (l > 0) {
1526                 int rc = ext4_block_get(fs->bdev, &block, current_block);
1527                 if (rc != EOK)
1528                         return rc;
1529
1530                 current_block = to_le32(((uint32_t *)block.data)[off_in_blk]);
1531                 if ((l > 1) && (current_block == 0)) {
1532                         ext4_fsblk_t goal;
1533                         rc = ext4_fs_indirect_find_goal(inode_ref, &goal);
1534                         if (rc != EOK) {
1535                                 ext4_block_set(fs->bdev, &block);
1536                                 return rc;
1537                         }
1538
1539                         /* Allocate new block */
1540                         rc =
1541                             ext4_balloc_alloc_block(inode_ref, goal, &new_blk);
1542                         if (rc != EOK) {
1543                                 ext4_block_set(fs->bdev, &block);
1544                                 return rc;
1545                         }
1546
1547                         /* Load newly allocated block */
1548                         rc = ext4_block_get_noread(fs->bdev, &new_block,
1549                                             new_blk);
1550
1551                         if (rc != EOK) {
1552                                 ext4_block_set(fs->bdev, &block);
1553                                 return rc;
1554                         }
1555
1556                         /* Initialize allocated block */
1557                         memset(new_block.data, 0, block_size);
1558                         new_block.dirty = true;
1559
1560                         rc = ext4_block_set(fs->bdev, &new_block);
1561                         if (rc != EOK) {
1562                                 ext4_block_set(fs->bdev, &block);
1563                                 return rc;
1564                         }
1565
1566                         /* Write block address to the parent */
1567                         uint32_t * p = (uint32_t * )block.data;
1568                         p[off_in_blk] = to_le32((uint32_t)new_blk);
1569                         block.dirty = true;
1570                         current_block = new_blk;
1571                 }
1572
1573                 /* Will be finished, write the fblock address */
1574                 if (l == 1) {
1575                         uint32_t * p = (uint32_t * )block.data;
1576                         p[off_in_blk] = to_le32((uint32_t)fblock);
1577                         block.dirty = true;
1578                 }
1579
1580                 rc = ext4_block_set(fs->bdev, &block);
1581                 if (rc != EOK)
1582                         return rc;
1583
1584                 l--;
1585
1586                 /*
1587                  * If we are on the last level, break here as
1588                  * there is no next level to visit
1589                  */
1590                 if (l == 0)
1591                         break;
1592
1593                 /* Visit the next level */
1594                 blk_off_in_lvl %= fs->inode_blocks_per_level[l];
1595                 off_in_blk = blk_off_in_lvl / fs->inode_blocks_per_level[l - 1];
1596         }
1597
1598         return EOK;
1599 }
1600
1601
1602 int ext4_fs_append_inode_block(struct ext4_inode_ref *inode_ref,
1603                                ext4_fsblk_t *fblock, uint32_t *iblock)
1604 {
1605 #if CONFIG_EXTENT_ENABLE
1606         /* Handle extents separately */
1607         if ((ext4_sb_feature_incom(&inode_ref->fs->sb, EXT4_FINCOM_EXTENTS)) &&
1608             (ext4_inode_has_flag(inode_ref->inode, EXT4_INODE_FLAG_EXTENTS))) {
1609                 int rc;
1610                 ext4_fsblk_t current_fsblk;
1611                 struct ext4_sblock *sb = &inode_ref->fs->sb;
1612                 uint64_t inode_size = ext4_inode_get_size(sb, inode_ref->inode);
1613                 uint32_t block_size = ext4_sb_get_block_size(sb);
1614                 *iblock = (inode_size + block_size - 1) / block_size;
1615
1616                 rc = ext4_extent_get_blocks(inode_ref, *iblock, 1,
1617                                                 &current_fsblk, true, NULL);
1618
1619
1620                 *fblock = current_fsblk;
1621                 ext4_assert(*fblock);
1622
1623                 ext4_inode_set_size(inode_ref->inode, inode_size + block_size);
1624                 inode_ref->dirty = true;
1625
1626
1627                 return rc;
1628         }
1629 #endif
1630         struct ext4_sblock *sb = &inode_ref->fs->sb;
1631
1632         /* Compute next block index and allocate data block */
1633         uint64_t inode_size = ext4_inode_get_size(sb, inode_ref->inode);
1634         uint32_t block_size = ext4_sb_get_block_size(sb);
1635
1636         /* Align size i-node size */
1637         if ((inode_size % block_size) != 0)
1638                 inode_size += block_size - (inode_size % block_size);
1639
1640         /* Logical blocks are numbered from 0 */
1641         uint32_t new_block_idx = inode_size / block_size;
1642
1643         /* Allocate new physical block */
1644         ext4_fsblk_t goal, phys_block;
1645         int rc = ext4_fs_indirect_find_goal(inode_ref, &goal);
1646         if (rc != EOK)
1647                 return rc;
1648
1649         rc = ext4_balloc_alloc_block(inode_ref, goal, &phys_block);
1650         if (rc != EOK)
1651                 return rc;
1652
1653         /* Add physical block address to the i-node */
1654         rc = ext4_fs_set_inode_data_block_index(inode_ref, new_block_idx,
1655                                                 phys_block);
1656         if (rc != EOK) {
1657                 ext4_balloc_free_block(inode_ref, phys_block);
1658                 return rc;
1659         }
1660
1661         /* Update i-node */
1662         ext4_inode_set_size(inode_ref->inode, inode_size + block_size);
1663         inode_ref->dirty = true;
1664
1665         *fblock = phys_block;
1666         *iblock = new_block_idx;
1667
1668         return EOK;
1669 }
1670
1671 void ext4_fs_inode_links_count_inc(struct ext4_inode_ref *inode_ref)
1672 {
1673         uint16_t link;
1674         bool is_dx;
1675         link = ext4_inode_get_links_count(inode_ref->inode);
1676         link++;
1677         ext4_inode_set_links_count(inode_ref->inode, link);
1678
1679         is_dx = ext4_sb_feature_com(&inode_ref->fs->sb, EXT4_FCOM_DIR_INDEX) &&
1680                 ext4_inode_has_flag(inode_ref->inode, EXT4_INODE_FLAG_INDEX);
1681
1682         if (is_dx && link > 1) {
1683                 if (link >= EXT4_LINK_MAX || link == 2) {
1684                         ext4_inode_set_links_count(inode_ref->inode, 1);
1685
1686                         uint32_t v;
1687                         v = ext4_get32(&inode_ref->fs->sb, features_read_only);
1688                         v |= EXT4_FRO_COM_DIR_NLINK;
1689                         ext4_set32(&inode_ref->fs->sb, features_read_only, v);
1690                 }
1691         }
1692 }
1693
1694 void ext4_fs_inode_links_count_dec(struct ext4_inode_ref *inode_ref)
1695 {
1696         uint16_t links = ext4_inode_get_links_count(inode_ref->inode);
1697         if (!ext4_inode_is_type(&inode_ref->fs->sb, inode_ref->inode,
1698                                 EXT4_INODE_MODE_DIRECTORY)) {
1699                 if (links > 0)
1700                         ext4_inode_set_links_count(inode_ref->inode, links - 1);
1701                 return;
1702         }
1703
1704         if (links > 2)
1705                 ext4_inode_set_links_count(inode_ref->inode, links - 1);
1706 }
1707
1708 /**
1709  * @}
1710  */