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,\r
 341                                           &tmp_path[pos].index, 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 =\r
 350                     ext4_extent_index_get_leaf(tmp_path[pos].index);\r
 351 \r
 352                 struct ext4_block block;\r
 353                 rc = ext4_block_get(inode_ref->fs->bdev, &block, fblock);\r
 354                 if (rc != EOK)\r
 355                         goto cleanup;\r
 356 \r
 357                 pos++;\r
 358 \r
 359                 eh = (struct ext4_extent_header *)block.data;\r
 360                 tmp_path[pos].block = block;\r
 361                 tmp_path[pos].header = eh;\r
 362         }\r
 363 \r
 364         tmp_path[pos].depth = 0;\r
 365         tmp_path[pos].extent = NULL;\r
 366         tmp_path[pos].index = NULL;\r
 367 \r
 368         /* Find extent in the leaf node */\r
 369         ext4_extent_binsearch(tmp_path[pos].header, &tmp_path[pos].extent,\r
 370                               iblock);\r
 371         *ret_path = tmp_path;\r
 372 \r
 373         return EOK;\r
 374 \r
 375 cleanup:\r
 376         /*\r
 377          * Put loaded blocks\r
 378          * From 1: 0 is a block with inode data\r
 379          */\r
 380         for (i = 1; i < tmp_path->depth; ++i) {\r
 381                 if (tmp_path[i].block.lb_id) {\r
 382                         int r = ext4_block_set(inode_ref->fs->bdev,\r
 383                                                &tmp_path[i].block);\r
 384                         if (r != EOK)\r
 385                                 rc = r;\r
 386                 }\r
 387         }\r
 388 \r
 389         /* Destroy temporary data structure */\r
 390         free(tmp_path);\r
 391 \r
 392         return rc;\r
 393 }\r
 394 \r
 395 /**@brief Release extent and all data blocks covered by the extent.\r
 396  * @param inode_ref I-node to release extent and block from\r
 397  * @param extent    Extent to release\r
 398  * @return Error code */\r
 399 static int ext4_extent_release(struct ext4_inode_ref *inode_ref,\r
 400                                struct ext4_extent *extent)\r
 401 {\r
 402         /* Compute number of the first physical block to release */\r
 403         uint64_t start = ext4_extent_get_start(extent);\r
 404         uint16_t block_count = ext4_extent_get_block_count(extent);\r
 405 \r
 406         return ext4_balloc_free_blocks(inode_ref, start, block_count);\r
 407 }\r
 408 \r
 409 /** Recursively release the whole branch of the extent tree.\r
 410  * For each entry of the node release the subbranch and finally release\r
 411  * the node. In the leaf node all extents will be released.\r
 412  * @param inode_ref I-node where the branch is released\r
 413  * @param index     Index in the non-leaf node to be released\r
 414  *                  with the whole subtree\r
 415  * @return Error code */\r
 416 static int ext4_extent_release_branch(struct ext4_inode_ref *inode_ref,\r
 417                                       struct ext4_extent_index *index)\r
 418 {\r
 419         uint32_t fblock = ext4_extent_index_get_leaf(index);\r
 420         uint32_t i;\r
 421         struct ext4_block block;\r
 422         int rc = ext4_block_get(inode_ref->fs->bdev, &block, fblock);\r
 423         if (rc != EOK)\r
 424                 return rc;\r
 425 \r
 426         struct ext4_extent_header *header = (void *)block.data;\r
 427 \r
 428         if (ext4_extent_header_get_depth(header)) {\r
 429                 /* The node is non-leaf, do recursion */\r
 430                 struct ext4_extent_index *idx = EXT4_EXTENT_FIRST_INDEX(header);\r
 431 \r
 432                 /* Release all subbranches */\r
 433                 for (i = 0; i < ext4_extent_header_get_entries_count(header);\r
 434                      ++i, ++idx) {\r
 435                         rc = ext4_extent_release_branch(inode_ref, idx);\r
 436                         if (rc != EOK)\r
 437                                 return rc;\r
 438                 }\r
 439         } else {\r
 440                 /* Leaf node reached */\r
 441                 struct ext4_extent *ext = EXT4_EXTENT_FIRST(header);\r
 442 \r
 443                 /* Release all extents and stop recursion */\r
 444                 for (i = 0; i < ext4_extent_header_get_entries_count(header);\r
 445                      ++i, ++ext) {\r
 446                         rc = ext4_extent_release(inode_ref, ext);\r
 447                         if (rc != EOK)\r
 448                                 return rc;\r
 449                 }\r
 450         }\r
 451 \r
 452         /* Release data block where the node was stored */\r
 453 \r
 454         rc = ext4_block_set(inode_ref->fs->bdev, &block);\r
 455         if (rc != EOK)\r
 456                 return rc;\r
 457 \r
 458         return ext4_balloc_free_block(inode_ref, fblock);\r
 459 }\r
 460 \r
 461 int ext4_extent_release_blocks_from(struct ext4_inode_ref *inode_ref,\r
 462                                     uint32_t iblock_from)\r
 463 {\r
 464         /* Find the first extent to modify */\r
 465         struct ext4_extent_path *path;\r
 466         uint16_t i;\r
 467         int rc = ext4_extent_find_extent(inode_ref, iblock_from, &path);\r
 468         if (rc != EOK)\r
 469                 return rc;\r
 470 \r
 471         /* Jump to last item of the path (extent) */\r
 472         struct ext4_extent_path *path_ptr = path;\r
 473         while (path_ptr->depth != 0)\r
 474                 path_ptr++;\r
 475 \r
 476         ext4_assert(path_ptr->extent != NULL);\r
 477 \r
 478         /* First extent maybe released partially */\r
 479         uint32_t first_iblock = ext4_extent_get_first_block(path_ptr->extent);\r
 480         uint32_t first_fblock = ext4_extent_get_start(path_ptr->extent) +\r
 481                                 iblock_from - first_iblock;\r
 482 \r
 483         uint16_t block_count = ext4_extent_get_block_count(path_ptr->extent);\r
 484 \r
 485         uint16_t delete_count =\r
 486             block_count -\r
 487             (ext4_extent_get_start(path_ptr->extent) - first_fblock);\r
 488 \r
 489         /* Release all blocks */\r
 490         rc = ext4_balloc_free_blocks(inode_ref, first_fblock, delete_count);\r
 491         if (rc != EOK)\r
 492                 goto cleanup;\r
 493 \r
 494         /* Correct counter */\r
 495         block_count -= delete_count;\r
 496         ext4_extent_set_block_count(path_ptr->extent, block_count);\r
 497 \r
 498         /* Initialize the following loop */\r
 499         uint16_t entries =\r
 500             ext4_extent_header_get_entries_count(path_ptr->header);\r
 501         struct ext4_extent *tmp_ext = path_ptr->extent + 1;\r
 502         struct ext4_extent *stop_ext =\r
 503             EXT4_EXTENT_FIRST(path_ptr->header) + entries;\r
 504 \r
 505         /* If first extent empty, release it */\r
 506         if (block_count == 0)\r
 507                 entries--;\r
 508 \r
 509         /* Release all successors of the first extent in the same node */\r
 510         while (tmp_ext < stop_ext) {\r
 511                 first_fblock = ext4_extent_get_start(tmp_ext);\r
 512                 delete_count = ext4_extent_get_block_count(tmp_ext);\r
 513 \r
 514                 rc = ext4_balloc_free_blocks(inode_ref, first_fblock,\r
 515                                              delete_count);\r
 516                 if (rc != EOK)\r
 517                         goto cleanup;\r
 518 \r
 519                 entries--;\r
 520                 tmp_ext++;\r
 521         }\r
 522 \r
 523         ext4_extent_header_set_entries_count(path_ptr->header, entries);\r
 524         path_ptr->block.dirty = true;\r
 525 \r
 526         /* If leaf node is empty, parent entry must be modified */\r
 527         bool remove_parent_record = false;\r
 528 \r
 529         /* Don't release root block (including inode data) !!! */\r
 530         if ((path_ptr != path) && (entries == 0)) {\r
 531                 rc = ext4_balloc_free_block(inode_ref, path_ptr->block.lb_id);\r
 532                 if (rc != EOK)\r
 533                         goto cleanup;\r
 534 \r
 535                 remove_parent_record = true;\r
 536         }\r
 537 \r
 538         /* Jump to the parent */\r
 539         --path_ptr;\r
 540 \r
 541         /* Release all successors in all tree levels */\r
 542         while (path_ptr >= path) {\r
 543                 entries =\r
 544                     ext4_extent_header_get_entries_count(path_ptr->header);\r
 545                 struct ext4_extent_index *index = path_ptr->index + 1;\r
 546                 struct ext4_extent_index *stop =\r
 547                     EXT4_EXTENT_FIRST_INDEX(path_ptr->header) + entries;\r
 548 \r
 549                 /* Correct entries count because of changes in the previous\r
 550                  * iteration */\r
 551                 if (remove_parent_record)\r
 552                         entries--;\r
 553 \r
 554                 /* Iterate over all entries and release the whole subtrees */\r
 555                 while (index < stop) {\r
 556                         rc = ext4_extent_release_branch(inode_ref, index);\r
 557                         if (rc != EOK)\r
 558                                 goto cleanup;\r
 559 \r
 560                         ++index;\r
 561                         --entries;\r
 562                 }\r
 563 \r
 564                 ext4_extent_header_set_entries_count(path_ptr->header, entries);\r
 565                 path_ptr->block.dirty = true;\r
 566 \r
 567                 /* Free the node if it is empty */\r
 568                 if ((entries == 0) && (path_ptr != path)) {\r
 569                         rc = ext4_balloc_free_block(inode_ref,\r
 570                                                     path_ptr->block.lb_id);\r
 571                         if (rc != EOK)\r
 572                                 goto cleanup;\r
 573 \r
 574                         /* Mark parent to be checked */\r
 575                         remove_parent_record = true;\r
 576                 } else\r
 577                         remove_parent_record = false;\r
 578 \r
 579                 --path_ptr;\r
 580         }\r
 581 \r
 582         if (!entries)\r
 583                 ext4_extent_header_set_depth(path->header, 0);\r
 584 \r
 585 cleanup:\r
 586         /*\r
 587          * Put loaded blocks\r
 588          * starting from 1: 0 is a block with inode data\r
 589          */\r
 590         for (i = 1; i <= path->depth; ++i) {\r
 591                 if (path[i].block.lb_id) {\r
 592                         int r =\r
 593                             ext4_block_set(inode_ref->fs->bdev, &path[i].block);\r
 594                         if (r != EOK)\r
 595                                 rc = r;\r
 596                 }\r
 597         }\r
 598 \r
 599         /* Destroy temporary data structure */\r
 600         free(path);\r
 601 \r
 602         return rc;\r
 603 }\r
 604 \r
 605 /**@brief Append new extent to the i-node and do some splitting if necessary.\r
 606  * @param inode_ref      I-node to append extent to\r
 607  * @param path           Path in the extent tree for possible splitting\r
 608  * @param last_path_item Input/output parameter for pointer to the last\r
 609  *                       valid item in the extent tree path\r
 610  * @param iblock         Logical index of block to append extent for\r
 611  * @return Error code */\r
 612 static int ext4_extent_append_extent(struct ext4_inode_ref *inode_ref,\r
 613                                      struct ext4_extent_path *path,\r
 614                                      uint32_t iblock)\r
 615 {\r
 616         struct ext4_extent_path *path_ptr = path + path->depth;\r
 617 \r
 618         uint32_t block_size = ext4_sb_get_block_size(&inode_ref->fs->sb);\r
 619 \r
 620         /* Start splitting */\r
 621         while (path_ptr > path) {\r
 622                 uint16_t entries =\r
 623                     ext4_extent_header_get_entries_count(path_ptr->header);\r
 624                 uint16_t limit =\r
 625                     ext4_extent_header_get_max_entries_count(path_ptr->header);\r
 626 \r
 627                 if (entries == limit) {\r
 628                         /* Full node - allocate block for new one */\r
 629                         uint32_t fblock;\r
 630                         int rc = ext4_balloc_alloc_block(inode_ref, &fblock);\r
 631                         if (rc != EOK)\r
 632                                 return rc;\r
 633 \r
 634                         struct ext4_block block;\r
 635                         rc =\r
 636                             ext4_block_get(inode_ref->fs->bdev, &block, fblock);\r
 637                         if (rc != EOK) {\r
 638                                 ext4_balloc_free_block(inode_ref, fblock);\r
 639                                 return rc;\r
 640                         }\r
 641 \r
 642                         /* Put back not modified old block */\r
 643                         rc = ext4_block_set(inode_ref->fs->bdev,\r
 644                                             &path_ptr->block);\r
 645                         if (rc != EOK) {\r
 646                                 ext4_balloc_free_block(inode_ref, fblock);\r
 647                                 return rc;\r
 648                         }\r
 649 \r
 650                         /* Initialize newly allocated block and remember it */\r
 651                         memset(block.data, 0, block_size);\r
 652                         path_ptr->block = block;\r
 653 \r
 654                         /* Update pointers in extent path structure */\r
 655                         path_ptr->header = (void *)block.data;\r
 656                         if (path_ptr->depth) {\r
 657                                 path_ptr->index =\r
 658                                     EXT4_EXTENT_FIRST_INDEX(path_ptr->header);\r
 659                                 ext4_extent_index_set_first_block(\r
 660                                     path_ptr->index, iblock);\r
 661                                 ext4_extent_index_set_leaf(\r
 662                                     path_ptr->index,\r
 663                                     (path_ptr + 1)->block.lb_id);\r
 664                                 limit = (block_size -\r
 665                                          sizeof(struct ext4_extent_header)) /\r
 666                                         sizeof(struct ext4_extent_index);\r
 667                         } else {\r
 668                                 path_ptr->extent =\r
 669                                     EXT4_EXTENT_FIRST(path_ptr->header);\r
 670                                 ext4_extent_set_first_block(path_ptr->extent,\r
 671                                                             iblock);\r
 672                                 limit = (block_size -\r
 673                                          sizeof(struct ext4_extent_header)) /\r
 674                                         sizeof(struct ext4_extent);\r
 675                         }\r
 676 \r
 677                         /* Initialize on-disk structure (header) */\r
 678                         ext4_extent_header_set_entries_count(path_ptr->header,\r
 679                                                              1);\r
 680                         ext4_extent_header_set_max_entries_count(\r
 681                             path_ptr->header, limit);\r
 682                         ext4_extent_header_set_magic(path_ptr->header,\r
 683                                                      EXT4_EXTENT_MAGIC);\r
 684                         ext4_extent_header_set_depth(path_ptr->header,\r
 685                                                      path_ptr->depth);\r
 686                         ext4_extent_header_set_generation(path_ptr->header, 0);\r
 687 \r
 688                         path_ptr->block.dirty = true;\r
 689 \r
 690                         /* Jump to the preceding item */\r
 691                         path_ptr--;\r
 692                 } else {\r
 693                         /* Node with free space */\r
 694                         if (path_ptr->depth) {\r
 695                                 path_ptr->index =\r
 696                                     EXT4_EXTENT_FIRST_INDEX(path_ptr->header) +\r
 697                                     entries;\r
 698                                 ext4_extent_index_set_first_block(\r
 699                                     path_ptr->index, iblock);\r
 700                                 ext4_extent_index_set_leaf(\r
 701                                     path_ptr->index,\r
 702                                     (path_ptr + 1)->block.lb_id);\r
 703                         } else {\r
 704                                 path_ptr->extent =\r
 705                                     EXT4_EXTENT_FIRST(path_ptr->header) +\r
 706                                     entries;\r
 707                                 ext4_extent_set_first_block(path_ptr->extent,\r
 708                                                             iblock);\r
 709                         }\r
 710 \r
 711                         ext4_extent_header_set_entries_count(path_ptr->header,\r
 712                                                              entries + 1);\r
 713                         path_ptr->block.dirty = true;\r
 714 \r
 715                         /* No more splitting needed */\r
 716                         return EOK;\r
 717                 }\r
 718         }\r
 719 \r
 720         ext4_assert(path_ptr == path);\r
 721 \r
 722         /* Should be the root split too? */\r
 723 \r
 724         uint16_t entries = ext4_extent_header_get_entries_count(path->header);\r
 725         uint16_t limit = ext4_extent_header_get_max_entries_count(path->header);\r
 726 \r
 727         if (entries == limit) {\r
 728                 uint32_t new_fblock;\r
 729                 int rc = ext4_balloc_alloc_block(inode_ref, &new_fblock);\r
 730                 if (rc != EOK)\r
 731                         return rc;\r
 732 \r
 733                 struct ext4_block block;\r
 734                 rc = ext4_block_get(inode_ref->fs->bdev, &block, new_fblock);\r
 735                 if (rc != EOK)\r
 736                         return rc;\r
 737 \r
 738                 /* Initialize newly allocated block */\r
 739                 memset(block.data, 0, block_size);\r
 740 \r
 741                 /* Move data from root to the new block */\r
 742                 memcpy(block.data, inode_ref->inode->blocks,\r
 743                        EXT4_INODE_BLOCKS * sizeof(uint32_t));\r
 744 \r
 745                 /* Data block is initialized */\r
 746 \r
 747                 struct ext4_block *root_block = &path->block;\r
 748                 uint16_t root_depth = path->depth;\r
 749                 struct ext4_extent_header *root_header = path->header;\r
 750 \r
 751                 /* Make space for tree growing */\r
 752                 struct ext4_extent_path *new_root = path;\r
 753                 struct ext4_extent_path *old_root = path + 1;\r
 754 \r
 755                 size_t nbytes =\r
 756                     sizeof(struct ext4_extent_path) * (path->depth + 1);\r
 757                 memmove(old_root, new_root, nbytes);\r
 758                 memset(new_root, 0, sizeof(struct ext4_extent_path));\r
 759 \r
 760                 /* Update old root structure */\r
 761                 old_root->block = block;\r
 762                 old_root->header = (struct ext4_extent_header *)block.data;\r
 763 \r
 764                 /* Add new entry and update limit for entries */\r
 765                 if (old_root->depth) {\r
 766                         limit =\r
 767                             (block_size - sizeof(struct ext4_extent_header)) /\r
 768                             sizeof(struct ext4_extent_index);\r
 769                         old_root->index =\r
 770                             EXT4_EXTENT_FIRST_INDEX(old_root->header) + entries;\r
 771                         ext4_extent_index_set_first_block(old_root->index,\r
 772                                                           iblock);\r
 773                         ext4_extent_index_set_leaf(old_root->index,\r
 774                                                    (old_root + 1)->block.lb_id);\r
 775                         old_root->extent = NULL;\r
 776                 } else {\r
 777                         limit =\r
 778                             (block_size - sizeof(struct ext4_extent_header)) /\r
 779                             sizeof(struct ext4_extent);\r
 780                         old_root->extent =\r
 781                             EXT4_EXTENT_FIRST(old_root->header) + entries;\r
 782                         ext4_extent_set_first_block(old_root->extent, iblock);\r
 783                         old_root->index = NULL;\r
 784                 }\r
 785 \r
 786                 ext4_extent_header_set_entries_count(old_root->header,\r
 787                                                      entries + 1);\r
 788                 ext4_extent_header_set_max_entries_count(old_root->header,\r
 789                                                          limit);\r
 790 \r
 791                 old_root->block.dirty = true;\r
 792 \r
 793                 /* Re-initialize new root metadata */\r
 794                 new_root->depth = root_depth + 1;\r
 795                 new_root->block = *root_block;\r
 796                 new_root->header = root_header;\r
 797                 new_root->extent = NULL;\r
 798                 new_root->index = EXT4_EXTENT_FIRST_INDEX(new_root->header);\r
 799 \r
 800                 ext4_extent_header_set_depth(new_root->header, new_root->depth);\r
 801 \r
 802                 /* Create new entry in root */\r
 803                 ext4_extent_header_set_entries_count(new_root->header, 1);\r
 804                 ext4_extent_index_set_first_block(new_root->index, 0);\r
 805                 ext4_extent_index_set_leaf(new_root->index, new_fblock);\r
 806 \r
 807                 new_root->block.dirty = true;\r
 808         } else {\r
 809                 if (path->depth) {\r
 810                         path->index =\r
 811                             EXT4_EXTENT_FIRST_INDEX(path->header) + entries;\r
 812                         ext4_extent_index_set_first_block(path->index, iblock);\r
 813                         ext4_extent_index_set_leaf(path->index,\r
 814                                                    (path + 1)->block.lb_id);\r
 815                 } else {\r
 816                         path->extent =\r
 817                             EXT4_EXTENT_FIRST(path->header) + entries;\r
 818                         ext4_extent_set_first_block(path->extent, iblock);\r
 819                 }\r
 820 \r
 821                 ext4_extent_header_set_entries_count(path->header, entries + 1);\r
 822                 path->block.dirty = true;\r
 823         }\r
 824 \r
 825         return EOK;\r
 826 }\r
 827 \r
 828 int ext4_extent_append_block(struct ext4_inode_ref *inode_ref, uint32_t *iblock,\r
 829                              uint32_t *fblock, bool update_size)\r
 830 {\r
 831         uint16_t i;\r
 832         struct ext4_sblock *sb = &inode_ref->fs->sb;\r
 833         uint64_t inode_size = ext4_inode_get_size(sb, inode_ref->inode);\r
 834         uint32_t block_size = ext4_sb_get_block_size(sb);\r
 835 \r
 836         /* Calculate number of new logical block */\r
 837         uint32_t new_block_idx = 0;\r
 838         if (inode_size > 0) {\r
 839                 if ((inode_size % block_size) != 0)\r
 840                         inode_size += block_size - (inode_size % block_size);\r
 841 \r
 842                 new_block_idx = inode_size / block_size;\r
 843         }\r
 844 \r
 845         /* Load the nearest leaf (with extent) */\r
 846         struct ext4_extent_path *path;\r
 847         int rc = ext4_extent_find_extent(inode_ref, new_block_idx, &path);\r
 848         if (rc != EOK)\r
 849                 return rc;\r
 850 \r
 851         /* Jump to last item of the path (extent) */\r
 852         struct ext4_extent_path *path_ptr = path;\r
 853         while (path_ptr->depth != 0)\r
 854                 path_ptr++;\r
 855 \r
 856         /* Add new extent to the node if not present */\r
 857         if (path_ptr->extent == NULL)\r
 858                 goto append_extent;\r
 859 \r
 860         uint16_t block_count = ext4_extent_get_block_count(path_ptr->extent);\r
 861         uint16_t block_limit = (1 << 15);\r
 862 \r
 863         uint32_t phys_block = 0;\r
 864         if (block_count < block_limit) {\r
 865                 /* There is space for new block in the extent */\r
 866                 if (block_count == 0) {\r
 867                         /* Existing extent is empty */\r
 868                         rc = ext4_balloc_alloc_block(inode_ref, &phys_block);\r
 869                         if (rc != EOK)\r
 870                                 goto finish;\r
 871 \r
 872                         /* Initialize extent */\r
 873                         ext4_extent_set_first_block(path_ptr->extent,\r
 874                                                     new_block_idx);\r
 875                         ext4_extent_set_start(path_ptr->extent, phys_block);\r
 876                         ext4_extent_set_block_count(path_ptr->extent, 1);\r
 877 \r
 878                         /* Update i-node */\r
 879                         if (update_size) {\r
 880                                 ext4_inode_set_size(inode_ref->inode,\r
 881                                                     inode_size + block_size);\r
 882                                 inode_ref->dirty = true;\r
 883                         }\r
 884 \r
 885                         path_ptr->block.dirty = true;\r
 886 \r
 887                         goto finish;\r
 888                 } else {\r
 889                         /* Existing extent contains some blocks */\r
 890                         phys_block = ext4_extent_get_start(path_ptr->extent);\r
 891                         phys_block +=\r
 892                             ext4_extent_get_block_count(path_ptr->extent);\r
 893 \r
 894                         /* Check if the following block is free for allocation\r
 895                          */\r
 896                         bool free;\r
 897                         rc = ext4_balloc_try_alloc_block(inode_ref, phys_block,\r
 898                                                          &free);\r
 899                         if (rc != EOK)\r
 900                                 goto finish;\r
 901 \r
 902                         if (!free) {\r
 903                                 /* Target is not free, new block must be\r
 904                                  * appended to new extent\r
 905                                  */\r
 906                                 goto append_extent;\r
 907                         }\r
 908 \r
 909                         /* Update extent */\r
 910                         ext4_extent_set_block_count(path_ptr->extent,\r
 911                                                     block_count + 1);\r
 912 \r
 913                         /* Update i-node */\r
 914                         if (update_size) {\r
 915                                 ext4_inode_set_size(inode_ref->inode,\r
 916                                                     inode_size + block_size);\r
 917                                 inode_ref->dirty = true;\r
 918                         }\r
 919 \r
 920                         path_ptr->block.dirty = true;\r
 921 \r
 922                         goto finish;\r
 923                 }\r
 924         }\r
 925 \r
 926 append_extent:\r
 927         /* Append new extent to the tree */\r
 928         phys_block = 0;\r
 929 \r
 930         /* Allocate new data block */\r
 931         rc = ext4_balloc_alloc_block(inode_ref, &phys_block);\r
 932         if (rc != EOK)\r
 933                 goto finish;\r
 934 \r
 935         /* Append extent for new block (includes tree splitting if needed) */\r
 936         rc = ext4_extent_append_extent(inode_ref, path, new_block_idx);\r
 937         if (rc != EOK) {\r
 938                 ext4_balloc_free_block(inode_ref, phys_block);\r
 939                 goto finish;\r
 940         }\r
 941 \r
 942         uint32_t tree_depth = ext4_extent_header_get_depth(path->header);\r
 943         path_ptr = path + tree_depth;\r
 944 \r
 945         /* Initialize newly created extent */\r
 946         ext4_extent_set_block_count(path_ptr->extent, 1);\r
 947         ext4_extent_set_first_block(path_ptr->extent, new_block_idx);\r
 948         ext4_extent_set_start(path_ptr->extent, phys_block);\r
 949 \r
 950         /* Update i-node */\r
 951         if (update_size) {\r
 952                 ext4_inode_set_size(inode_ref->inode, inode_size + block_size);\r
 953                 inode_ref->dirty = true;\r
 954         }\r
 955 \r
 956         path_ptr->block.dirty = true;\r
 957 \r
 958 finish:\r
 959         /* Set return values */\r
 960         *iblock = new_block_idx;\r
 961         *fblock = phys_block;\r
 962 \r
 963         /*\r
 964          * Put loaded blocks\r
 965          * starting from 1: 0 is a block with inode data\r
 966          */\r
 967         for (i = 1; i <= path->depth; ++i) {\r
 968                 if (path[i].block.lb_id) {\r
 969                         int r =\r
 970                             ext4_block_set(inode_ref->fs->bdev, &path[i].block);\r
 971                         if (r != EOK)\r
 972                                 rc = r;\r
 973                 }\r
 974         }\r
 975 \r
 976         /* Destroy temporary data structure */\r
 977         free(path);\r
 978 \r
 979         return rc;\r
 980 }\r
 981 \r
 982 /**\r
 983  * @}\r
 984  */\r