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