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