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