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