lwext4/ext4_extent.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
  34 /** @addtogroup lwext4
  35  * @{
  36  */
  37 /**
  38  * @file  ext4_extent.c
  39  * @brief More complex filesystem functions.
  40  */
  41
  42 #include "ext4_config.h"
  43 #include "ext4_extent.h"
  44 #include "ext4_inode.h"
  45 #include "ext4_super.h"
  46 #include "ext4_blockdev.h"
  47 #include "ext4_balloc.h"
  48 #include "ext4_fs.h"
  49
  50 #include <string.h>
  51 #include <stdlib.h>
  52
  53 #if !CONFIG_EXTENT_FULL
  54
  55 /**@brief Binary search in extent index node.
  56  * @param header Extent header of index node
  57  * @param index  Output value - found index will be set here
  58  * @param iblock Logical block number to find in index node */
  59 static void ext4_extent_binsearch_idx(struct ext4_extent_header *header,
  60                                       struct ext4_extent_index **index,
  61                                       uint32_t iblock)
  62 {
  63         struct ext4_extent_index *r;
  64         struct ext4_extent_index *l;
  65         struct ext4_extent_index *m;
  66
  67         uint16_t entries_count = ext4_extent_header_get_entries_count(header);
  68
  69         /* Initialize bounds */
  70         l = EXT4_EXTENT_FIRST_INDEX(header) + 1;
  71         r = EXT4_EXTENT_FIRST_INDEX(header) + entries_count - 1;
  72
  73         /* Do binary search */
  74         while (l <= r) {
  75                 m = l + (r - l) / 2;
  76                 uint32_t first_block = ext4_extent_index_get_first_block(m);
  77
  78                 if (iblock < first_block)
  79                         r = m - 1;
  80                 else
  81                         l = m + 1;
  82         }
  83
  84         /* Set output value */
  85         *index = l - 1;
  86 }
  87
  88 /**@brief Binary search in extent leaf node.
  89  * @param header Extent header of leaf node
  90  * @param extent Output value - found extent will be set here,
  91  *               or NULL if node is empty
  92  * @param iblock Logical block number to find in leaf node */
  93 static void ext4_extent_binsearch(struct ext4_extent_header *header,
  94                                   struct ext4_extent **extent, uint32_t iblock)
  95 {
  96         struct ext4_extent *r;
  97         struct ext4_extent *l;
  98         struct ext4_extent *m;
  99
 100         uint16_t entries_count = ext4_extent_header_get_entries_count(header);
 101
 102         if (entries_count == 0) {
 103                 /* this leaf is empty */
 104                 *extent = NULL;
 105                 return;
 106         }
 107
 108         /* Initialize bounds */
 109         l = EXT4_EXTENT_FIRST(header) + 1;
 110         r = EXT4_EXTENT_FIRST(header) + entries_count - 1;
 111
 112         /* Do binary search */
 113         while (l <= r) {
 114                 m = l + (r - l) / 2;
 115                 uint32_t first_block = ext4_extent_get_first_block(m);
 116
 117                 if (iblock < first_block)
 118                         r = m - 1;
 119                 else
 120                         l = m + 1;
 121         }
 122
 123         /* Set output value */
 124         *extent = l - 1;
 125 }
 126
 127 /**@brief Get physical block in the extent tree by logical block number.
 128  * There is no need to save path in the tree during this algorithm.
 129  * @param inode_ref I-node to load block from
 130  * @param iblock    Logical block number to find
 131  * @param fblock    Output value for physical block number
 132  * @return Error code*/
 133 static int
 134 ext4_extent_find_block(struct ext4_inode_ref *inode_ref, uint32_t iblock,
 135                            ext4_fsblk_t *fblock)
 136 {
 137         int rc;
 138         /* Compute bound defined by i-node size */
 139         uint64_t inode_size =
 140             ext4_inode_get_size(&inode_ref->fs->sb, inode_ref->inode);
 141
 142         uint32_t block_size = ext4_sb_get_block_size(&inode_ref->fs->sb);
 143
 144         uint32_t last_idx = (inode_size - 1) / block_size;
 145
 146         /* Check if requested iblock is not over size of i-node */
 147         if (iblock > last_idx) {
 148                 *fblock = 0;
 149                 return EOK;
 150         }
 151
 152         struct ext4_block block;
 153         block.lb_id = 0;
 154
 155         /* Walk through extent tree */
 156         struct ext4_extent_header *header =
 157             ext4_inode_get_extent_header(inode_ref->inode);
 158
 159         while (ext4_extent_header_get_depth(header) != 0) {
 160                 /* Search index in node */
 161                 struct ext4_extent_index *index;
 162                 ext4_extent_binsearch_idx(header, &index, iblock);
 163
 164                 /* Load child node and set values for the next iteration */
 165                 uint64_t child = ext4_extent_index_get_leaf(index);
 166
 167                 if (block.lb_id) {
 168                         rc = ext4_block_set(inode_ref->fs->bdev, &block);
 169                         if (rc != EOK)
 170                                 return rc;
 171                 }
 172
 173                 int rc = ext4_block_get(inode_ref->fs->bdev, &block, child);
 174                 if (rc != EOK)
 175                         return rc;
 176
 177                 header = (struct ext4_extent_header *)block.data;
 178         }
 179
 180         /* Search extent in the leaf block */
 181         struct ext4_extent *extent = NULL;
 182         ext4_extent_binsearch(header, &extent, iblock);
 183
 184         /* Prevent empty leaf */
 185         if (extent == NULL) {
 186                 *fblock = 0;
 187         } else {
 188                 /* Compute requested physical block address */
 189                 ext4_fsblk_t phys_block;
 190                 uint32_t first = ext4_extent_get_first_block(extent);
 191                 phys_block = ext4_extent_get_start(extent) + iblock - first;
 192
 193                 *fblock = phys_block;
 194         }
 195
 196         /* Cleanup */
 197         if (block.lb_id) {
 198                 rc = ext4_block_set(inode_ref->fs->bdev, &block);
 199                 if (rc != EOK)
 200                         return rc;
 201         }
 202
 203         return EOK;
 204 }
 205
 206 /**@brief Find extent for specified iblock.
 207  * This function is used for finding block in the extent tree with
 208  * saving the path through the tree for possible future modifications.
 209  * @param inode_ref I-node to read extent tree from
 210  * @param iblock    Iblock to find extent for
 211  * @param ret_path  Output value for loaded path from extent tree
 212  * @return Error code */
 213 static int ext4_extent_find_extent(struct ext4_inode_ref *inode_ref,
 214                                    uint32_t iblock,
 215                                    struct ext4_extent_path **ret_path)
 216 {
 217         struct ext4_extent_header *eh =
 218             ext4_inode_get_extent_header(inode_ref->inode);
 219
 220         uint16_t depth = ext4_extent_header_get_depth(eh);
 221         uint16_t i;
 222         struct ext4_extent_path *tmp_path;
 223
 224         /* Added 2 for possible tree growing */
 225         tmp_path = malloc(sizeof(struct ext4_extent_path) * (depth + 2));
 226         if (tmp_path == NULL)
 227                 return ENOMEM;
 228
 229         /* Initialize structure for algorithm start */
 230         tmp_path[0].block = inode_ref->block;
 231         tmp_path[0].header = eh;
 232
 233         /* Walk through the extent tree */
 234         uint16_t pos = 0;
 235         int rc;
 236         while (ext4_extent_header_get_depth(eh) != 0) {
 237                 /* Search index in index node by iblock */
 238                 ext4_extent_binsearch_idx(tmp_path[pos].header,
 239                                           &tmp_path[pos].index, iblock);
 240
 241                 tmp_path[pos].depth = depth;
 242                 tmp_path[pos].extent = NULL;
 243
 244                 ext4_assert(tmp_path[pos].index != 0);
 245
 246                 /* Load information for the next iteration */
 247                 uint64_t fblock =
 248                     ext4_extent_index_get_leaf(tmp_path[pos].index);
 249
 250                 struct ext4_block block;
 251                 rc = ext4_block_get(inode_ref->fs->bdev, &block, fblock);
 252                 if (rc != EOK)
 253                         goto cleanup;
 254
 255                 pos++;
 256
 257                 eh = (struct ext4_extent_header *)block.data;
 258                 tmp_path[pos].block = block;
 259                 tmp_path[pos].header = eh;
 260         }
 261
 262         tmp_path[pos].depth = 0;
 263         tmp_path[pos].extent = NULL;
 264         tmp_path[pos].index = NULL;
 265
 266         /* Find extent in the leaf node */
 267         ext4_extent_binsearch(tmp_path[pos].header, &tmp_path[pos].extent,
 268                               iblock);
 269         *ret_path = tmp_path;
 270
 271         return EOK;
 272
 273 cleanup:
 274         /*
 275          * Put loaded blocks
 276          * From 1: 0 is a block with inode data
 277          */
 278         for (i = 1; i < tmp_path->depth; ++i) {
 279                 if (tmp_path[i].block.lb_id) {
 280                         int r = ext4_block_set(inode_ref->fs->bdev,
 281                                                &tmp_path[i].block);
 282                         if (r != EOK)
 283                                 rc = r;
 284                 }
 285         }
 286
 287         /* Destroy temporary data structure */
 288         free(tmp_path);
 289
 290         return rc;
 291 }
 292
 293 /**@brief Release extent and all data blocks covered by the extent.
 294  * @param inode_ref I-node to release extent and block from
 295  * @param extent    Extent to release
 296  * @return Error code */
 297 static int ext4_extent_release(struct ext4_inode_ref *inode_ref,
 298                                struct ext4_extent *extent)
 299 {
 300         /* Compute number of the first physical block to release */
 301         uint64_t start = ext4_extent_get_start(extent);
 302         uint16_t block_count = ext4_extent_get_block_count(extent);
 303
 304         return ext4_balloc_free_blocks(inode_ref, start, block_count);
 305 }
 306
 307 /** Recursively release the whole branch of the extent tree.
 308  * For each entry of the node release the subbranch and finally release
 309  * the node. In the leaf node all extents will be released.
 310  * @param inode_ref I-node where the branch is released
 311  * @param index     Index in the non-leaf node to be released
 312  *                  with the whole subtree
 313  * @return Error code */
 314 static int ext4_extent_release_branch(struct ext4_inode_ref *inode_ref,
 315                                       struct ext4_extent_index *index)
 316 {
 317         ext4_fsblk_t fblock = ext4_extent_index_get_leaf(index);
 318         uint32_t i;
 319         struct ext4_block block;
 320         int rc = ext4_block_get(inode_ref->fs->bdev, &block, fblock);
 321         if (rc != EOK)
 322                 return rc;
 323
 324         struct ext4_extent_header *header = (void *)block.data;
 325
 326         if (ext4_extent_header_get_depth(header)) {
 327                 /* The node is non-leaf, do recursion */
 328                 struct ext4_extent_index *idx = EXT4_EXTENT_FIRST_INDEX(header);
 329
 330                 /* Release all subbranches */
 331                 for (i = 0; i < ext4_extent_header_get_entries_count(header);
 332                      ++i, ++idx) {
 333                         rc = ext4_extent_release_branch(inode_ref, idx);
 334                         if (rc != EOK)
 335                                 return rc;
 336                 }
 337         } else {
 338                 /* Leaf node reached */
 339                 struct ext4_extent *ext = EXT4_EXTENT_FIRST(header);
 340
 341                 /* Release all extents and stop recursion */
 342                 for (i = 0; i < ext4_extent_header_get_entries_count(header);
 343                      ++i, ++ext) {
 344                         rc = ext4_extent_release(inode_ref, ext);
 345                         if (rc != EOK)
 346                                 return rc;
 347                 }
 348         }
 349
 350         /* Release data block where the node was stored */
 351
 352         rc = ext4_block_set(inode_ref->fs->bdev, &block);
 353         if (rc != EOK)
 354                 return rc;
 355
 356         return ext4_balloc_free_block(inode_ref, fblock);
 357 }
 358
 359 int ext4_extent_remove_space(struct ext4_inode_ref *inode_ref, ext4_lblk_t from,
 360                              ext4_lblk_t to)
 361 {
 362         if (to != EXT_MAX_BLOCKS)
 363                 return ENOTSUP;
 364
 365         /* Find the first extent to modify */
 366         struct ext4_extent_path *path;
 367         uint16_t i;
 368         int rc = ext4_extent_find_extent(inode_ref, from, &path);
 369         if (rc != EOK)
 370                 return rc;
 371
 372         /* Jump to last item of the path (extent) */
 373         struct ext4_extent_path *path_ptr = path;
 374         while (path_ptr->depth != 0)
 375                 path_ptr++;
 376
 377         ext4_assert(path_ptr->extent != NULL);
 378
 379         /* First extent maybe released partially */
 380         uint32_t first_iblock = ext4_extent_get_first_block(path_ptr->extent);
 381         ext4_fsblk_t first_fblock = ext4_extent_get_start(path_ptr->extent) +
 382                                 from - first_iblock;
 383
 384         uint16_t block_count = ext4_extent_get_block_count(path_ptr->extent);
 385
 386         uint16_t delete_count =
 387             block_count -
 388             (ext4_extent_get_start(path_ptr->extent) - first_fblock);
 389
 390         /* Release all blocks */
 391         rc = ext4_balloc_free_blocks(inode_ref, first_fblock, delete_count);
 392         if (rc != EOK)
 393                 goto cleanup;
 394
 395         /* Correct counter */
 396         block_count -= delete_count;
 397         ext4_extent_set_block_count(path_ptr->extent, block_count,
 398                                 EXT4_EXT_IS_UNWRITTEN(path_ptr->extent));
 399
 400         /* Initialize the following loop */
 401         uint16_t entries =
 402             ext4_extent_header_get_entries_count(path_ptr->header);
 403         struct ext4_extent *tmp_ext = path_ptr->extent + 1;
 404         struct ext4_extent *stop_ext =
 405             EXT4_EXTENT_FIRST(path_ptr->header) + entries;
 406
 407         /* If first extent empty, release it */
 408         if (block_count == 0)
 409                 entries--;
 410
 411         /* Release all successors of the first extent in the same node */
 412         while (tmp_ext < stop_ext) {
 413                 first_fblock = ext4_extent_get_start(tmp_ext);
 414                 delete_count = ext4_extent_get_block_count(tmp_ext);
 415
 416                 rc = ext4_balloc_free_blocks(inode_ref, first_fblock,
 417                                              delete_count);
 418                 if (rc != EOK)
 419                         goto cleanup;
 420
 421                 entries--;
 422                 tmp_ext++;
 423         }
 424
 425         ext4_extent_header_set_entries_count(path_ptr->header, entries);
 426         path_ptr->block.dirty = true;
 427
 428         /* If leaf node is empty, parent entry must be modified */
 429         bool remove_parent_record = false;
 430
 431         /* Don't release root block (including inode data) !!! */
 432         if ((path_ptr != path) && (entries == 0)) {
 433                 rc = ext4_balloc_free_block(inode_ref, path_ptr->block.lb_id);
 434                 if (rc != EOK)
 435                         goto cleanup;
 436
 437                 remove_parent_record = true;
 438         }
 439
 440         /* Jump to the parent */
 441         --path_ptr;
 442
 443         /* Release all successors in all tree levels */
 444         while (path_ptr >= path) {
 445                 entries =
 446                     ext4_extent_header_get_entries_count(path_ptr->header);
 447                 struct ext4_extent_index *index = path_ptr->index + 1;
 448                 struct ext4_extent_index *stop =
 449                     EXT4_EXTENT_FIRST_INDEX(path_ptr->header) + entries;
 450
 451                 /* Correct entries count because of changes in the previous
 452                  * iteration */
 453                 if (remove_parent_record)
 454                         entries--;
 455
 456                 /* Iterate over all entries and release the whole subtrees */
 457                 while (index < stop) {
 458                         rc = ext4_extent_release_branch(inode_ref, index);
 459                         if (rc != EOK)
 460                                 goto cleanup;
 461
 462                         ++index;
 463                         --entries;
 464                 }
 465
 466                 ext4_extent_header_set_entries_count(path_ptr->header, entries);
 467                 path_ptr->block.dirty = true;
 468
 469                 /* Free the node if it is empty */
 470                 if ((entries == 0) && (path_ptr != path)) {
 471                         rc = ext4_balloc_free_block(inode_ref,
 472                                                     path_ptr->block.lb_id);
 473                         if (rc != EOK)
 474                                 goto cleanup;
 475
 476                         /* Mark parent to be checked */
 477                         remove_parent_record = true;
 478                 } else
 479                         remove_parent_record = false;
 480
 481                 --path_ptr;
 482         }
 483
 484         if (!entries)
 485                 ext4_extent_header_set_depth(path->header, 0);
 486
 487 cleanup:
 488         /*
 489          * Put loaded blocks
 490          * starting from 1: 0 is a block with inode data
 491          */
 492         for (i = 1; i <= path->depth; ++i) {
 493                 if (path[i].block.lb_id) {
 494                         int r =
 495                             ext4_block_set(inode_ref->fs->bdev, &path[i].block);
 496                         if (r != EOK)
 497                                 rc = r;
 498                 }
 499         }
 500
 501         /* Destroy temporary data structure */
 502         free(path);
 503
 504         return rc;
 505 }
 506
 507 /**@brief Append new extent to the i-node and do some splitting if necessary.
 508  * @param inode_ref      I-node to append extent to
 509  * @param path           Path in the extent tree for possible splitting
 510  * @param last_path_item Input/output parameter for pointer to the last
 511  *                       valid item in the extent tree path
 512  * @param iblock         Logical index of block to append extent for
 513  * @return Error code */
 514 static int ext4_extent_append_extent(struct ext4_inode_ref *inode_ref,
 515                                      struct ext4_extent_path *path,
 516                                      uint32_t iblock)
 517 {
 518         struct ext4_extent_path *path_ptr = path + path->depth;
 519
 520         uint32_t block_size = ext4_sb_get_block_size(&inode_ref->fs->sb);
 521
 522         /* Start splitting */
 523         while (path_ptr > path) {
 524                 uint16_t entries =
 525                     ext4_extent_header_get_entries_count(path_ptr->header);
 526                 uint16_t limit =
 527                     ext4_extent_header_get_max_entries_count(path_ptr->header);
 528
 529                 if (entries == limit) {
 530                         /* Full node - allocate block for new one */
 531                         ext4_fsblk_t goal, fblock;
 532                         int rc = ext4_fs_indirect_find_goal(inode_ref, &goal);
 533                         if (rc != EOK)
 534                                 return rc;
 535
 536                         rc = ext4_balloc_alloc_block(inode_ref, goal, &fblock);
 537                         if (rc != EOK)
 538                                 return rc;
 539
 540                         struct ext4_block block;
 541                         rc =
 542                             ext4_block_get(inode_ref->fs->bdev, &block, fblock);
 543                         if (rc != EOK) {
 544                                 ext4_balloc_free_block(inode_ref, fblock);
 545                                 return rc;
 546                         }
 547
 548                         /* Put back not modified old block */
 549                         rc = ext4_block_set(inode_ref->fs->bdev,
 550                                             &path_ptr->block);
 551                         if (rc != EOK) {
 552                                 ext4_balloc_free_block(inode_ref, fblock);
 553                                 return rc;
 554                         }
 555
 556                         /* Initialize newly allocated block and remember it */
 557                         memset(block.data, 0, block_size);
 558                         path_ptr->block = block;
 559
 560                         /* Update pointers in extent path structure */
 561                         path_ptr->header = (void *)block.data;
 562                         if (path_ptr->depth) {
 563                                 path_ptr->index =
 564                                     EXT4_EXTENT_FIRST_INDEX(path_ptr->header);
 565                                 ext4_extent_index_set_first_block(
 566                                     path_ptr->index, iblock);
 567                                 ext4_extent_index_set_leaf(
 568                                     path_ptr->index,
 569                                     (path_ptr + 1)->block.lb_id);
 570                                 limit = (block_size -
 571                                          sizeof(struct ext4_extent_header)) /
 572                                         sizeof(struct ext4_extent_index);
 573                         } else {
 574                                 path_ptr->extent =
 575                                     EXT4_EXTENT_FIRST(path_ptr->header);
 576                                 ext4_extent_set_first_block(path_ptr->extent,
 577                                                             iblock);
 578                                 limit = (block_size -
 579                                          sizeof(struct ext4_extent_header)) /
 580                                         sizeof(struct ext4_extent);
 581                         }
 582
 583                         /* Initialize on-disk structure (header) */
 584                         ext4_extent_header_set_entries_count(path_ptr->header,
 585                                                              1);
 586                         ext4_extent_header_set_max_entries_count(
 587                             path_ptr->header, limit);
 588                         ext4_extent_header_set_magic(path_ptr->header,
 589                                                      EXT4_EXTENT_MAGIC);
 590                         ext4_extent_header_set_depth(path_ptr->header,
 591                                                      path_ptr->depth);
 592                         ext4_extent_header_set_generation(path_ptr->header, 0);
 593
 594                         path_ptr->block.dirty = true;
 595
 596                         /* Jump to the preceding item */
 597                         path_ptr--;
 598                 } else {
 599                         /* Node with free space */
 600                         if (path_ptr->depth) {
 601                                 path_ptr->index =
 602                                     EXT4_EXTENT_FIRST_INDEX(path_ptr->header) +
 603                                     entries;
 604                                 ext4_extent_index_set_first_block(
 605                                     path_ptr->index, iblock);
 606                                 ext4_extent_index_set_leaf(
 607                                     path_ptr->index,
 608                                     (path_ptr + 1)->block.lb_id);
 609                         } else {
 610                                 path_ptr->extent =
 611                                     EXT4_EXTENT_FIRST(path_ptr->header) +
 612                                     entries;
 613                                 ext4_extent_set_first_block(path_ptr->extent,
 614                                                             iblock);
 615                         }
 616
 617                         ext4_extent_header_set_entries_count(path_ptr->header,
 618                                                              entries + 1);
 619                         path_ptr->block.dirty = true;
 620
 621                         /* No more splitting needed */
 622                         return EOK;
 623                 }
 624         }
 625
 626         ext4_assert(path_ptr == path);
 627
 628         /* Should be the root split too? */
 629
 630         uint16_t entries = ext4_extent_header_get_entries_count(path->header);
 631         uint16_t limit = ext4_extent_header_get_max_entries_count(path->header);
 632
 633         if (entries == limit) {
 634                 ext4_fsblk_t goal, new_fblock;
 635                 int rc = ext4_fs_indirect_find_goal(inode_ref, &goal);
 636                 if (rc != EOK)
 637                         return rc;
 638
 639                 rc = ext4_balloc_alloc_block(inode_ref, goal, &new_fblock);
 640                 if (rc != EOK)
 641                         return rc;
 642
 643                 struct ext4_block block;
 644                 rc = ext4_block_get(inode_ref->fs->bdev, &block, new_fblock);
 645                 if (rc != EOK)
 646                         return rc;
 647
 648                 /* Initialize newly allocated block */
 649                 memset(block.data, 0, block_size);
 650
 651                 /* Move data from root to the new block */
 652                 memcpy(block.data, inode_ref->inode->blocks,
 653                        EXT4_INODE_BLOCKS * sizeof(uint32_t));
 654
 655                 /* Data block is initialized */
 656
 657                 struct ext4_block *root_block = &path->block;
 658                 uint16_t root_depth = path->depth;
 659                 struct ext4_extent_header *root_header = path->header;
 660
 661                 /* Make space for tree growing */
 662                 struct ext4_extent_path *new_root = path;
 663                 struct ext4_extent_path *old_root = path + 1;
 664
 665                 size_t nbytes =
 666                     sizeof(struct ext4_extent_path) * (path->depth + 1);
 667                 memmove(old_root, new_root, nbytes);
 668                 memset(new_root, 0, sizeof(struct ext4_extent_path));
 669
 670                 /* Update old root structure */
 671                 old_root->block = block;
 672                 old_root->header = (struct ext4_extent_header *)block.data;
 673
 674                 /* Add new entry and update limit for entries */
 675                 if (old_root->depth) {
 676                         limit =
 677                             (block_size - sizeof(struct ext4_extent_header)) /
 678                             sizeof(struct ext4_extent_index);
 679                         old_root->index =
 680                             EXT4_EXTENT_FIRST_INDEX(old_root->header) + entries;
 681                         ext4_extent_index_set_first_block(old_root->index,
 682                                                           iblock);
 683                         ext4_extent_index_set_leaf(old_root->index,
 684                                                    (old_root + 1)->block.lb_id);
 685                         old_root->extent = NULL;
 686                 } else {
 687                         limit =
 688                             (block_size - sizeof(struct ext4_extent_header)) /
 689                             sizeof(struct ext4_extent);
 690                         old_root->extent =
 691                             EXT4_EXTENT_FIRST(old_root->header) + entries;
 692                         ext4_extent_set_first_block(old_root->extent, iblock);
 693                         old_root->index = NULL;
 694                 }
 695
 696                 ext4_extent_header_set_entries_count(old_root->header,
 697                                                      entries + 1);
 698                 ext4_extent_header_set_max_entries_count(old_root->header,
 699                                                          limit);
 700
 701                 old_root->block.dirty = true;
 702
 703                 /* Re-initialize new root metadata */
 704                 new_root->depth = root_depth + 1;
 705                 new_root->block = *root_block;
 706                 new_root->header = root_header;
 707                 new_root->extent = NULL;
 708                 new_root->index = EXT4_EXTENT_FIRST_INDEX(new_root->header);
 709
 710                 ext4_extent_header_set_depth(new_root->header, new_root->depth);
 711
 712                 /* Create new entry in root */
 713                 ext4_extent_header_set_entries_count(new_root->header, 1);
 714                 ext4_extent_index_set_first_block(new_root->index, 0);
 715                 ext4_extent_index_set_leaf(new_root->index, new_fblock);
 716
 717                 new_root->block.dirty = true;
 718         } else {
 719                 if (path->depth) {
 720                         path->index =
 721                             EXT4_EXTENT_FIRST_INDEX(path->header) + entries;
 722                         ext4_extent_index_set_first_block(path->index, iblock);
 723                         ext4_extent_index_set_leaf(path->index,
 724                                                    (path + 1)->block.lb_id);
 725                 } else {
 726                         path->extent =
 727                             EXT4_EXTENT_FIRST(path->header) + entries;
 728                         ext4_extent_set_first_block(path->extent, iblock);
 729                 }
 730
 731                 ext4_extent_header_set_entries_count(path->header, entries + 1);
 732                 path->block.dirty = true;
 733         }
 734
 735         return EOK;
 736 }
 737
 738 /**@brief Append data block to the i-node.
 739  * This function allocates data block, tries to append it
 740  * to some existing extent or creates new extents.
 741  * It includes possible extent tree modifications (splitting).
 742  * @param inode_ref I-node to append block to
 743  * @param iblock    Output logical number of newly allocated block
 744  * @param fblock    Output physical block address of newly allocated block
 745  *
 746  * @return Error code*/
 747 static int
 748 ext4_extent_append_block(struct ext4_inode_ref *inode_ref, uint32_t *iblock,
 749                              ext4_fsblk_t *fblock, bool update_size)
 750 {
 751         uint16_t i;
 752         ext4_fsblk_t goal;
 753         struct ext4_sblock *sb = &inode_ref->fs->sb;
 754         uint64_t inode_size = ext4_inode_get_size(sb, inode_ref->inode);
 755         uint32_t block_size = ext4_sb_get_block_size(sb);
 756
 757         /* Calculate number of new logical block */
 758         uint32_t new_block_idx = 0;
 759         if (inode_size > 0) {
 760                 if ((inode_size % block_size) != 0)
 761                         inode_size += block_size - (inode_size % block_size);
 762
 763                 new_block_idx = inode_size / block_size;
 764         }
 765
 766         /* Load the nearest leaf (with extent) */
 767         struct ext4_extent_path *path;
 768         int rc = ext4_extent_find_extent(inode_ref, new_block_idx, &path);
 769         if (rc != EOK)
 770                 return rc;
 771
 772         /* Jump to last item of the path (extent) */
 773         struct ext4_extent_path *path_ptr = path;
 774         while (path_ptr->depth != 0)
 775                 path_ptr++;
 776
 777         /* Add new extent to the node if not present */
 778         if (path_ptr->extent == NULL)
 779                 goto append_extent;
 780
 781         uint16_t block_count = ext4_extent_get_block_count(path_ptr->extent);
 782         uint16_t block_limit = (1 << 15);
 783
 784         ext4_fsblk_t phys_block = 0;
 785         if (block_count < block_limit) {
 786                 /* There is space for new block in the extent */
 787                 if (block_count == 0) {
 788                         int rc = ext4_fs_indirect_find_goal(inode_ref, &goal);
 789                         if (rc != EOK)
 790                                 goto finish;
 791
 792                         /* Existing extent is empty */
 793                         rc = ext4_balloc_alloc_block(inode_ref, goal, &phys_block);
 794                         if (rc != EOK)
 795                                 goto finish;
 796
 797                         /* Initialize extent */
 798                         ext4_extent_set_first_block(path_ptr->extent,
 799                                                     new_block_idx);
 800                         ext4_extent_set_start(path_ptr->extent, phys_block);
 801                         ext4_extent_set_block_count(path_ptr->extent, 1,
 802                                                 false);
 803
 804                         /* Update i-node */
 805                         if (update_size) {
 806                                 ext4_inode_set_size(inode_ref->inode,
 807                                                     inode_size + block_size);
 808                                 inode_ref->dirty = true;
 809                         }
 810
 811                         path_ptr->block.dirty = true;
 812
 813                         goto finish;
 814                 } else {
 815                         ext4_fsblk_t goal;
 816                         int rc = ext4_fs_indirect_find_goal(inode_ref, &goal);
 817                         if (rc != EOK)
 818                                 goto finish;
 819
 820                         /* Existing extent contains some blocks */
 821                         phys_block = ext4_extent_get_start(path_ptr->extent);
 822                         phys_block +=
 823                             ext4_extent_get_block_count(path_ptr->extent);
 824
 825                         /* Check if the following block is free for allocation
 826                          */
 827                         bool free;
 828                         rc = ext4_balloc_try_alloc_block(inode_ref, phys_block,
 829                                                          &free);
 830                         if (rc != EOK)
 831                                 goto finish;
 832
 833                         if (!free) {
 834                                 /* Target is not free, new block must be
 835                                  * appended to new extent
 836                                  */
 837                                 goto append_extent;
 838                         }
 839
 840                         /* Update extent */
 841                         ext4_extent_set_block_count(path_ptr->extent,
 842                                                     block_count + 1,
 843                                                     false);
 844
 845                         /* Update i-node */
 846                         if (update_size) {
 847                                 ext4_inode_set_size(inode_ref->inode,
 848                                                     inode_size + block_size);
 849                                 inode_ref->dirty = true;
 850                         }
 851
 852                         path_ptr->block.dirty = true;
 853
 854                         goto finish;
 855                 }
 856         }
 857
 858 append_extent:
 859         /* Append new extent to the tree */
 860         phys_block = 0;
 861
 862         rc = ext4_fs_indirect_find_goal(inode_ref, &goal);
 863         if (rc != EOK)
 864                 goto finish;
 865
 866         /* Allocate new data block */
 867         rc = ext4_balloc_alloc_block(inode_ref, goal, &phys_block);
 868         if (rc != EOK)
 869                 goto finish;
 870
 871         /* Append extent for new block (includes tree splitting if needed) */
 872         rc = ext4_extent_append_extent(inode_ref, path, new_block_idx);
 873         if (rc != EOK) {
 874                 ext4_balloc_free_block(inode_ref, phys_block);
 875                 goto finish;
 876         }
 877
 878         uint32_t tree_depth = ext4_extent_header_get_depth(path->header);
 879         path_ptr = path + tree_depth;
 880
 881         /* Initialize newly created extent */
 882         ext4_extent_set_block_count(path_ptr->extent, 1, false);
 883         ext4_extent_set_first_block(path_ptr->extent, new_block_idx);
 884         ext4_extent_set_start(path_ptr->extent, phys_block);
 885
 886         /* Update i-node */
 887         if (update_size) {
 888                 ext4_inode_set_size(inode_ref->inode, inode_size + block_size);
 889                 inode_ref->dirty = true;
 890         }
 891
 892         path_ptr->block.dirty = true;
 893
 894 finish:
 895         /* Set return values */
 896         *iblock = new_block_idx;
 897         *fblock = phys_block;
 898
 899         /*
 900          * Put loaded blocks
 901          * starting from 1: 0 is a block with inode data
 902          */
 903         for (i = 1; i <= path->depth; ++i) {
 904                 if (path[i].block.lb_id) {
 905                         int r =
 906                             ext4_block_set(inode_ref->fs->bdev, &path[i].block);
 907                         if (r != EOK)
 908                                 rc = r;
 909                 }
 910         }
 911
 912         /* Destroy temporary data structure */
 913         free(path);
 914
 915         return rc;
 916 }
 917
 918 int ext4_extent_get_blocks(struct ext4_inode_ref *inode_ref, ext4_fsblk_t iblock,
 919                            ext4_lblk_t max_blocks, ext4_fsblk_t *result, bool create,
 920                            ext4_lblk_t *blocks_count)
 921 {
 922         uint32_t iblk = iblock;
 923         ext4_fsblk_t fblk = 0;
 924         int r;
 925
 926         if (blocks_count)
 927                 return ENOTSUP;
 928         if (max_blocks != 1)
 929                 return ENOTSUP;
 930
 931         if (!create)
 932                 r = ext4_extent_find_block(inode_ref, iblk, &fblk);
 933         else
 934                 r = ext4_extent_append_block(inode_ref, &iblk, &fblk, false);
 935
 936         *result = fblk;
 937         return r;
 938 }
 939
 940 #endif
 941 /**
 942  * @}
 943  */