lwext4/ext4_extent.c

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