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