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