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