2 * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com)
6 * Copyright (c) 2012 Martin Sucha
7 * Copyright (c) 2012 Frantisek Princ
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
14 * - Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * - Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 * - The name of the author may not be used to endorse or promote products
20 * derived from this software without specific prior written permission.
22 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
23 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
24 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
25 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
27 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
31 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 /** @addtogroup lwext4
39 * @brief More complex filesystem functions.
42 #include "ext4_config.h"
43 #include "ext4_extent.h"
44 #include "ext4_inode.h"
45 #include "ext4_super.h"
46 #include "ext4_crc32c.h"
47 #include "ext4_blockdev.h"
48 #include "ext4_balloc.h"
54 #if !CONFIG_EXTENT_FULL
56 static struct ext4_extent_header *ext_inode_hdr(struct ext4_inode *inode)
58 return (struct ext4_extent_header *)inode->blocks;
61 static uint16_t ext_depth(struct ext4_inode *inode)
63 return to_le16(ext_inode_hdr(inode)->depth);
66 static struct ext4_extent_tail *
67 find_ext4_extent_tail(struct ext4_extent_header *eh)
69 return (struct ext4_extent_tail *)(((char *)eh) +
70 EXT4_EXTENT_TAIL_OFFSET(eh));
73 #if CONFIG_META_CSUM_ENABLE
74 static uint32_t ext4_ext_block_csum(struct ext4_inode_ref *inode_ref,
75 struct ext4_extent_header *eh)
77 uint32_t checksum = 0;
78 struct ext4_sblock *sb = &inode_ref->fs->sb;
80 if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {
81 uint32_t ino_index = to_le32(inode_ref->index);
83 to_le32(ext4_inode_get_generation(inode_ref->inode));
84 /* First calculate crc32 checksum against fs uuid */
85 checksum = ext4_crc32c(EXT4_CRC32_INIT, sb->uuid,
87 /* Then calculate crc32 checksum against inode number
88 * and inode generation */
89 checksum = ext4_crc32c(checksum, &ino_index,
91 checksum = ext4_crc32c(checksum, &ino_gen,
93 /* Finally calculate crc32 checksum against
94 * the entire extent block up to the checksum field */
95 checksum = ext4_crc32c(checksum, eh,
96 EXT4_EXTENT_TAIL_OFFSET(eh));
101 #define ext4_ext_block_csum(...) 0
104 static void ext4_extent_block_csum_set(struct ext4_inode_ref *inode_ref,
105 struct ext4_extent_header *eh)
107 struct ext4_extent_tail *tail;
108 if (!ext4_sb_feature_ro_com(&inode_ref->fs->sb,
109 EXT4_FRO_COM_METADATA_CSUM))
112 if (to_le16(eh->depth) < ext_depth(inode_ref->inode)) {
113 tail = find_ext4_extent_tail(eh);
114 tail->et_checksum = to_le32(ext4_ext_block_csum(inode_ref, eh));
118 #if CONFIG_META_CSUM_ENABLE
120 ext4_extent_verify_block_csum(struct ext4_inode_ref *inode_ref,
121 struct ext4_block *block)
123 struct ext4_extent_header *eh;
124 struct ext4_extent_tail *tail;
125 eh = (struct ext4_extent_header *)block->data;
126 if (!ext4_sb_feature_ro_com(&inode_ref->fs->sb,
127 EXT4_FRO_COM_METADATA_CSUM))
130 if (to_le16(eh->depth) < ext_depth(inode_ref->inode)) {
131 tail = find_ext4_extent_tail(eh);
132 return tail->et_checksum ==
133 to_le32(ext4_ext_block_csum(inode_ref, eh));
139 #define ext4_extent_verify_block_csum(...) true
142 /**@brief Binary search in extent index node.
143 * @param header Extent header of index node
144 * @param index Output value - found index will be set here
145 * @param iblock Logical block number to find in index node */
146 static void ext4_extent_binsearch_idx(struct ext4_extent_header *header,
147 struct ext4_extent_index **index,
150 struct ext4_extent_index *r;
151 struct ext4_extent_index *l;
152 struct ext4_extent_index *m;
154 uint16_t entries_count = ext4_extent_header_get_entries_count(header);
156 /* Initialize bounds */
157 l = EXT4_EXTENT_FIRST_INDEX(header) + 1;
158 r = EXT4_EXTENT_FIRST_INDEX(header) + entries_count - 1;
160 /* Do binary search */
163 uint32_t first_block = ext4_extent_index_get_first_block(m);
165 if (iblock < first_block)
171 /* Set output value */
175 /**@brief Binary search in extent leaf node.
176 * @param header Extent header of leaf node
177 * @param extent Output value - found extent will be set here,
178 * or NULL if node is empty
179 * @param iblock Logical block number to find in leaf node */
180 static void ext4_extent_binsearch(struct ext4_extent_header *header,
181 struct ext4_extent **extent, uint32_t iblock)
183 struct ext4_extent *r;
184 struct ext4_extent *l;
185 struct ext4_extent *m;
187 uint16_t entries_count = ext4_extent_header_get_entries_count(header);
189 if (entries_count == 0) {
190 /* this leaf is empty */
195 /* Initialize bounds */
196 l = EXT4_EXTENT_FIRST(header) + 1;
197 r = EXT4_EXTENT_FIRST(header) + entries_count - 1;
199 /* Do binary search */
202 uint32_t first_block = ext4_extent_get_first_block(m);
204 if (iblock < first_block)
210 /* Set output value */
214 /**@brief Get physical block in the extent tree by logical block number.
215 * There is no need to save path in the tree during this algorithm.
216 * @param inode_ref I-node to load block from
217 * @param iblock Logical block number to find
218 * @param fblock Output value for physical block number
219 * @return Error code*/
221 ext4_extent_find_block(struct ext4_inode_ref *inode_ref, uint32_t iblock,
222 ext4_fsblk_t *fblock)
225 /* Compute bound defined by i-node size */
226 uint64_t inode_size =
227 ext4_inode_get_size(&inode_ref->fs->sb, inode_ref->inode);
229 uint32_t block_size = ext4_sb_get_block_size(&inode_ref->fs->sb);
231 uint32_t last_idx = (inode_size - 1) / block_size;
233 /* Check if requested iblock is not over size of i-node */
234 if (iblock > last_idx) {
239 struct ext4_block block;
242 /* Walk through extent tree */
243 struct ext4_extent_header *header =
244 ext4_inode_get_extent_header(inode_ref->inode);
246 while (ext4_extent_header_get_depth(header) != 0) {
247 /* Search index in node */
248 struct ext4_extent_index *index;
249 ext4_extent_binsearch_idx(header, &index, iblock);
251 /* Load child node and set values for the next iteration */
252 uint64_t child = ext4_extent_index_get_leaf(index);
255 rc = ext4_block_set(inode_ref->fs->bdev, &block);
260 int rc = ext4_block_get(inode_ref->fs->bdev, &block, child);
263 if (!ext4_extent_verify_block_csum(inode_ref,
265 ext4_dbg(DEBUG_EXTENT,
266 DBG_WARN "Extent block checksum failed."
267 "Blocknr: %" PRIu64"\n",
271 header = (struct ext4_extent_header *)block.data;
274 /* Search extent in the leaf block */
275 struct ext4_extent *extent = NULL;
276 ext4_extent_binsearch(header, &extent, iblock);
278 /* Prevent empty leaf */
279 if (extent == NULL) {
282 /* Compute requested physical block address */
283 ext4_fsblk_t phys_block;
284 uint32_t first = ext4_extent_get_first_block(extent);
285 phys_block = ext4_extent_get_start(extent) + iblock - first;
287 *fblock = phys_block;
292 rc = ext4_block_set(inode_ref->fs->bdev, &block);
300 /**@brief Find extent for specified iblock.
301 * This function is used for finding block in the extent tree with
302 * saving the path through the tree for possible future modifications.
303 * @param inode_ref I-node to read extent tree from
304 * @param iblock Iblock to find extent for
305 * @param ret_path Output value for loaded path from extent tree
306 * @return Error code */
307 static int ext4_extent_find_extent(struct ext4_inode_ref *inode_ref,
309 struct ext4_extent_path **ret_path)
311 struct ext4_extent_header *eh =
312 ext4_inode_get_extent_header(inode_ref->inode);
314 uint16_t depth = ext4_extent_header_get_depth(eh);
316 struct ext4_extent_path *tmp_path;
318 /* Added 2 for possible tree growing */
319 tmp_path = malloc(sizeof(struct ext4_extent_path) * (depth + 2));
320 if (tmp_path == NULL)
323 /* Initialize structure for algorithm start */
324 tmp_path[0].block = inode_ref->block;
325 tmp_path[0].header = eh;
327 /* Walk through the extent tree */
330 while (ext4_extent_header_get_depth(eh) != 0) {
331 /* Search index in index node by iblock */
332 ext4_extent_binsearch_idx(tmp_path[pos].header,
333 &tmp_path[pos].index, iblock);
335 tmp_path[pos].depth = depth;
336 tmp_path[pos].extent = NULL;
338 ext4_assert(tmp_path[pos].index != 0);
340 /* Load information for the next iteration */
342 ext4_extent_index_get_leaf(tmp_path[pos].index);
344 struct ext4_block block;
345 rc = ext4_block_get(inode_ref->fs->bdev, &block, fblock);
349 if (!ext4_extent_verify_block_csum(inode_ref,
351 ext4_dbg(DEBUG_EXTENT,
352 DBG_WARN "Extent block checksum failed."
353 "Blocknr: %" PRIu64"\n",
359 eh = (struct ext4_extent_header *)block.data;
360 tmp_path[pos].block = block;
361 tmp_path[pos].header = eh;
364 tmp_path[pos].depth = 0;
365 tmp_path[pos].extent = NULL;
366 tmp_path[pos].index = NULL;
368 /* Find extent in the leaf node */
369 ext4_extent_binsearch(tmp_path[pos].header, &tmp_path[pos].extent,
371 *ret_path = tmp_path;
378 * From 1: 0 is a block with inode data
380 for (i = 1; i < tmp_path->depth; ++i) {
381 if (tmp_path[i].block.lb_id) {
382 int r = ext4_block_set(inode_ref->fs->bdev,
389 /* Destroy temporary data structure */
395 /**@brief Release extent and all data blocks covered by the extent.
396 * @param inode_ref I-node to release extent and block from
397 * @param extent Extent to release
398 * @return Error code */
399 static int ext4_extent_release(struct ext4_inode_ref *inode_ref,
400 struct ext4_extent *extent)
402 /* Compute number of the first physical block to release */
403 uint64_t start = ext4_extent_get_start(extent);
404 uint16_t block_count = ext4_extent_get_block_count(extent);
406 return ext4_balloc_free_blocks(inode_ref, start, block_count);
409 /** Recursively release the whole branch of the extent tree.
410 * For each entry of the node release the subbranch and finally release
411 * the node. In the leaf node all extents will be released.
412 * @param inode_ref I-node where the branch is released
413 * @param index Index in the non-leaf node to be released
414 * with the whole subtree
415 * @return Error code */
416 static int ext4_extent_release_branch(struct ext4_inode_ref *inode_ref,
417 struct ext4_extent_index *index)
419 ext4_fsblk_t fblock = ext4_extent_index_get_leaf(index);
421 struct ext4_block block;
422 int rc = ext4_block_get(inode_ref->fs->bdev, &block, fblock);
426 if (!ext4_extent_verify_block_csum(inode_ref,
428 ext4_dbg(DEBUG_EXTENT,
429 DBG_WARN "Extent block checksum failed."
430 "Blocknr: %" PRIu64"\n",
434 struct ext4_extent_header *header = (void *)block.data;
436 if (ext4_extent_header_get_depth(header)) {
437 /* The node is non-leaf, do recursion */
438 struct ext4_extent_index *idx = EXT4_EXTENT_FIRST_INDEX(header);
440 /* Release all subbranches */
441 for (i = 0; i < ext4_extent_header_get_entries_count(header);
443 rc = ext4_extent_release_branch(inode_ref, idx);
448 /* Leaf node reached */
449 struct ext4_extent *ext = EXT4_EXTENT_FIRST(header);
451 /* Release all extents and stop recursion */
452 for (i = 0; i < ext4_extent_header_get_entries_count(header);
454 rc = ext4_extent_release(inode_ref, ext);
460 /* Release data block where the node was stored */
462 rc = ext4_block_set(inode_ref->fs->bdev, &block);
466 return ext4_balloc_free_block(inode_ref, fblock);
469 int ext4_extent_remove_space(struct ext4_inode_ref *inode_ref, ext4_lblk_t from,
472 if (to != EXT_MAX_BLOCKS)
475 /* Find the first extent to modify */
476 struct ext4_extent_path *path;
478 int rc = ext4_extent_find_extent(inode_ref, from, &path);
482 /* Jump to last item of the path (extent) */
483 struct ext4_extent_path *path_ptr = path;
484 while (path_ptr->depth != 0)
487 ext4_assert(path_ptr->extent != NULL);
489 /* First extent maybe released partially */
490 uint32_t first_iblock = ext4_extent_get_first_block(path_ptr->extent);
491 ext4_fsblk_t first_fblock = ext4_extent_get_start(path_ptr->extent) +
494 uint16_t block_count = ext4_extent_get_block_count(path_ptr->extent);
496 uint16_t delete_count =
498 (ext4_extent_get_start(path_ptr->extent) - first_fblock);
500 /* Release all blocks */
501 rc = ext4_balloc_free_blocks(inode_ref, first_fblock, delete_count);
505 /* Correct counter */
506 block_count -= delete_count;
507 ext4_extent_set_block_count(path_ptr->extent, block_count,
508 EXT4_EXT_IS_UNWRITTEN(path_ptr->extent));
510 /* Initialize the following loop */
512 ext4_extent_header_get_entries_count(path_ptr->header);
513 struct ext4_extent *tmp_ext = path_ptr->extent + 1;
514 struct ext4_extent *stop_ext =
515 EXT4_EXTENT_FIRST(path_ptr->header) + entries;
517 /* If first extent empty, release it */
518 if (block_count == 0)
521 /* Release all successors of the first extent in the same node */
522 while (tmp_ext < stop_ext) {
523 first_fblock = ext4_extent_get_start(tmp_ext);
524 delete_count = ext4_extent_get_block_count(tmp_ext);
526 rc = ext4_balloc_free_blocks(inode_ref, first_fblock,
535 ext4_extent_header_set_entries_count(path_ptr->header, entries);
536 ext4_extent_block_csum_set(inode_ref, path_ptr->header);
537 ext4_bcache_set_dirty(path_ptr->block.buf);
539 /* If leaf node is empty, parent entry must be modified */
540 bool remove_parent_record = false;
542 /* Don't release root block (including inode data) !!! */
543 if ((path_ptr != path) && (entries == 0)) {
544 rc = ext4_balloc_free_block(inode_ref, path_ptr->block.lb_id);
548 remove_parent_record = true;
551 /* Jump to the parent */
554 /* Release all successors in all tree levels */
555 while (path_ptr >= path) {
557 ext4_extent_header_get_entries_count(path_ptr->header);
558 struct ext4_extent_index *index = path_ptr->index + 1;
559 struct ext4_extent_index *stop =
560 EXT4_EXTENT_FIRST_INDEX(path_ptr->header) + entries;
562 /* Correct entries count because of changes in the previous
564 if (remove_parent_record)
567 /* Iterate over all entries and release the whole subtrees */
568 while (index < stop) {
569 rc = ext4_extent_release_branch(inode_ref, index);
577 ext4_extent_header_set_entries_count(path_ptr->header, entries);
578 ext4_extent_block_csum_set(inode_ref, path_ptr->header);
579 ext4_bcache_set_dirty(path_ptr->block.buf);
581 /* Free the node if it is empty */
582 if ((entries == 0) && (path_ptr != path)) {
583 rc = ext4_balloc_free_block(inode_ref,
584 path_ptr->block.lb_id);
588 /* Mark parent to be checked */
589 remove_parent_record = true;
591 remove_parent_record = false;
597 ext4_extent_header_set_depth(path->header, 0);
602 * starting from 1: 0 is a block with inode data
604 for (i = 1; i <= path->depth; ++i) {
605 if (path[i].block.lb_id) {
607 ext4_block_set(inode_ref->fs->bdev, &path[i].block);
613 /* Destroy temporary data structure */
619 /**@brief Append new extent to the i-node and do some splitting if necessary.
620 * @param inode_ref I-node to append extent to
621 * @param path Path in the extent tree for possible splitting
622 * @param last_path_item Input/output parameter for pointer to the last
623 * valid item in the extent tree path
624 * @param iblock Logical index of block to append extent for
625 * @return Error code */
626 static int ext4_extent_append_extent(struct ext4_inode_ref *inode_ref,
627 struct ext4_extent_path *path,
630 struct ext4_extent_path *path_ptr = path + path->depth;
632 uint32_t block_size = ext4_sb_get_block_size(&inode_ref->fs->sb);
634 /* Start splitting */
635 while (path_ptr > path) {
637 ext4_extent_header_get_entries_count(path_ptr->header);
639 ext4_extent_header_get_max_entries_count(path_ptr->header);
641 if (entries == limit) {
642 /* Full node - allocate block for new one */
643 ext4_fsblk_t goal, fblock;
644 int rc = ext4_fs_indirect_find_goal(inode_ref, &goal);
648 rc = ext4_balloc_alloc_block(inode_ref, goal, &fblock);
652 struct ext4_block block;
654 ext4_block_get_noread(inode_ref->fs->bdev, &block, fblock);
656 ext4_balloc_free_block(inode_ref, fblock);
660 /* Put back not modified old block */
661 rc = ext4_block_set(inode_ref->fs->bdev,
664 ext4_balloc_free_block(inode_ref, fblock);
668 /* Initialize newly allocated block and remember it */
669 memset(block.data, 0, block_size);
670 path_ptr->block = block;
672 /* Update pointers in extent path structure */
673 path_ptr->header = (void *)block.data;
674 if (path_ptr->depth) {
676 EXT4_EXTENT_FIRST_INDEX(path_ptr->header);
677 ext4_extent_index_set_first_block(
678 path_ptr->index, iblock);
679 ext4_extent_index_set_leaf(
681 (path_ptr + 1)->block.lb_id);
682 limit = (block_size -
683 sizeof(struct ext4_extent_header)) /
684 sizeof(struct ext4_extent_index);
687 EXT4_EXTENT_FIRST(path_ptr->header);
688 ext4_extent_set_first_block(path_ptr->extent,
690 limit = (block_size -
691 sizeof(struct ext4_extent_header)) /
692 sizeof(struct ext4_extent);
695 /* Initialize on-disk structure (header) */
696 ext4_extent_header_set_entries_count(path_ptr->header,
698 ext4_extent_header_set_max_entries_count(
699 path_ptr->header, limit);
700 ext4_extent_header_set_magic(path_ptr->header,
702 ext4_extent_header_set_depth(path_ptr->header,
704 ext4_extent_header_set_generation(path_ptr->header, 0);
706 ext4_extent_block_csum_set(inode_ref, path_ptr->header);
707 ext4_bcache_set_dirty(path_ptr->block.buf);
709 /* Jump to the preceding item */
712 /* Node with free space */
713 if (path_ptr->depth) {
715 EXT4_EXTENT_FIRST_INDEX(path_ptr->header) +
717 ext4_extent_index_set_first_block(
718 path_ptr->index, iblock);
719 ext4_extent_index_set_leaf(
721 (path_ptr + 1)->block.lb_id);
724 EXT4_EXTENT_FIRST(path_ptr->header) +
726 ext4_extent_set_first_block(path_ptr->extent,
730 ext4_extent_header_set_entries_count(path_ptr->header,
732 ext4_extent_block_csum_set(inode_ref, path_ptr->header);
733 ext4_bcache_set_dirty(path_ptr->block.buf);
735 /* No more splitting needed */
740 ext4_assert(path_ptr == path);
742 /* Should be the root split too? */
744 uint16_t entries = ext4_extent_header_get_entries_count(path->header);
745 uint16_t limit = ext4_extent_header_get_max_entries_count(path->header);
747 if (entries == limit) {
748 ext4_fsblk_t goal, new_fblock;
749 int rc = ext4_fs_indirect_find_goal(inode_ref, &goal);
753 rc = ext4_balloc_alloc_block(inode_ref, goal, &new_fblock);
757 struct ext4_block block;
758 rc = ext4_block_get_noread(inode_ref->fs->bdev, &block, new_fblock);
762 /* Initialize newly allocated block */
763 memset(block.data, 0, block_size);
765 /* Move data from root to the new block */
766 memcpy(block.data, inode_ref->inode->blocks,
767 EXT4_INODE_BLOCKS * sizeof(uint32_t));
769 /* Data block is initialized */
771 struct ext4_block *root_block = &path->block;
772 uint16_t root_depth = path->depth;
773 struct ext4_extent_header *root_header = path->header;
775 /* Make space for tree growing */
776 struct ext4_extent_path *new_root = path;
777 struct ext4_extent_path *old_root = path + 1;
780 sizeof(struct ext4_extent_path) * (path->depth + 1);
781 memmove(old_root, new_root, nbytes);
782 memset(new_root, 0, sizeof(struct ext4_extent_path));
784 /* Update old root structure */
785 old_root->block = block;
786 old_root->header = (struct ext4_extent_header *)block.data;
788 /* Add new entry and update limit for entries */
789 if (old_root->depth) {
791 (block_size - sizeof(struct ext4_extent_header)) /
792 sizeof(struct ext4_extent_index);
794 EXT4_EXTENT_FIRST_INDEX(old_root->header) + entries;
795 ext4_extent_index_set_first_block(old_root->index,
797 ext4_extent_index_set_leaf(old_root->index,
798 (old_root + 1)->block.lb_id);
799 old_root->extent = NULL;
802 (block_size - sizeof(struct ext4_extent_header)) /
803 sizeof(struct ext4_extent);
805 EXT4_EXTENT_FIRST(old_root->header) + entries;
806 ext4_extent_set_first_block(old_root->extent, iblock);
807 old_root->index = NULL;
810 ext4_extent_header_set_entries_count(old_root->header,
812 ext4_extent_header_set_max_entries_count(old_root->header,
815 ext4_extent_block_csum_set(inode_ref, old_root->header);
816 ext4_bcache_set_dirty(old_root->block.buf);
818 /* Re-initialize new root metadata */
819 new_root->depth = root_depth + 1;
820 new_root->block = *root_block;
821 new_root->header = root_header;
822 new_root->extent = NULL;
823 new_root->index = EXT4_EXTENT_FIRST_INDEX(new_root->header);
825 ext4_extent_header_set_depth(new_root->header, new_root->depth);
827 /* Create new entry in root */
828 ext4_extent_header_set_entries_count(new_root->header, 1);
829 ext4_extent_index_set_first_block(new_root->index, 0);
830 ext4_extent_index_set_leaf(new_root->index, new_fblock);
832 /* Since new_root belongs to on-disk inode,
833 * we don't do checksum here */
834 ext4_bcache_set_dirty(new_root->block.buf);
838 EXT4_EXTENT_FIRST_INDEX(path->header) + entries;
839 ext4_extent_index_set_first_block(path->index, iblock);
840 ext4_extent_index_set_leaf(path->index,
841 (path + 1)->block.lb_id);
844 EXT4_EXTENT_FIRST(path->header) + entries;
845 ext4_extent_set_first_block(path->extent, iblock);
848 ext4_extent_header_set_entries_count(path->header, entries + 1);
849 /* Since new_root belongs to on-disk inode,
850 * we don't do checksum here */
851 ext4_bcache_set_dirty(path->block.buf);
857 /**@brief Append data block to the i-node.
858 * This function allocates data block, tries to append it
859 * to some existing extent or creates new extents.
860 * It includes possible extent tree modifications (splitting).
861 * @param inode_ref I-node to append block to
862 * @param iblock Output logical number of newly allocated block
863 * @param fblock Output physical block address of newly allocated block
865 * @return Error code*/
867 ext4_extent_append_block(struct ext4_inode_ref *inode_ref, uint32_t *iblock,
868 ext4_fsblk_t *fblock, bool update_size)
872 struct ext4_sblock *sb = &inode_ref->fs->sb;
873 uint64_t inode_size = ext4_inode_get_size(sb, inode_ref->inode);
874 uint32_t block_size = ext4_sb_get_block_size(sb);
876 /* Calculate number of new logical block */
877 uint32_t new_block_idx = 0;
878 if (inode_size > 0) {
879 if ((inode_size % block_size) != 0)
880 inode_size += block_size - (inode_size % block_size);
882 new_block_idx = inode_size / block_size;
885 /* Load the nearest leaf (with extent) */
886 struct ext4_extent_path *path;
887 int rc = ext4_extent_find_extent(inode_ref, new_block_idx, &path);
891 /* Jump to last item of the path (extent) */
892 struct ext4_extent_path *path_ptr = path;
893 while (path_ptr->depth != 0)
896 /* Add new extent to the node if not present */
897 if (path_ptr->extent == NULL)
900 uint16_t block_count = ext4_extent_get_block_count(path_ptr->extent);
901 uint16_t block_limit = (1 << 15);
903 ext4_fsblk_t phys_block = 0;
904 if (block_count < block_limit) {
905 /* There is space for new block in the extent */
906 if (block_count == 0) {
907 int rc = ext4_fs_indirect_find_goal(inode_ref, &goal);
911 /* Existing extent is empty */
912 rc = ext4_balloc_alloc_block(inode_ref, goal, &phys_block);
916 /* Initialize extent */
917 ext4_extent_set_first_block(path_ptr->extent,
919 ext4_extent_set_start(path_ptr->extent, phys_block);
920 ext4_extent_set_block_count(path_ptr->extent, 1,
925 ext4_inode_set_size(inode_ref->inode,
926 inode_size + block_size);
927 inode_ref->dirty = true;
930 ext4_extent_block_csum_set(inode_ref, path_ptr->header);
931 ext4_bcache_set_dirty(path_ptr->block.buf);
936 int rc = ext4_fs_indirect_find_goal(inode_ref, &goal);
940 /* Existing extent contains some blocks */
941 phys_block = ext4_extent_get_start(path_ptr->extent);
943 ext4_extent_get_block_count(path_ptr->extent);
945 /* Check if the following block is free for allocation
948 rc = ext4_balloc_try_alloc_block(inode_ref, phys_block,
954 /* Target is not free, new block must be
955 * appended to new extent
961 ext4_extent_set_block_count(path_ptr->extent,
967 ext4_inode_set_size(inode_ref->inode,
968 inode_size + block_size);
969 inode_ref->dirty = true;
972 ext4_extent_block_csum_set(inode_ref, path_ptr->header);
973 ext4_bcache_set_dirty(path_ptr->block.buf);
980 /* Append new extent to the tree */
983 rc = ext4_fs_indirect_find_goal(inode_ref, &goal);
987 /* Allocate new data block */
988 rc = ext4_balloc_alloc_block(inode_ref, goal, &phys_block);
992 /* Append extent for new block (includes tree splitting if needed) */
993 rc = ext4_extent_append_extent(inode_ref, path, new_block_idx);
995 ext4_balloc_free_block(inode_ref, phys_block);
999 uint32_t tree_depth = ext4_extent_header_get_depth(path->header);
1000 path_ptr = path + tree_depth;
1002 /* Initialize newly created extent */
1003 ext4_extent_set_block_count(path_ptr->extent, 1, false);
1004 ext4_extent_set_first_block(path_ptr->extent, new_block_idx);
1005 ext4_extent_set_start(path_ptr->extent, phys_block);
1009 ext4_inode_set_size(inode_ref->inode, inode_size + block_size);
1010 inode_ref->dirty = true;
1013 ext4_extent_block_csum_set(inode_ref, path_ptr->header);
1014 ext4_bcache_set_dirty(path_ptr->block.buf);
1017 /* Set return values */
1018 *iblock = new_block_idx;
1019 *fblock = phys_block;
1023 * starting from 1: 0 is a block with inode data
1025 for (i = 1; i <= path->depth; ++i) {
1026 if (path[i].block.lb_id) {
1028 ext4_block_set(inode_ref->fs->bdev, &path[i].block);
1034 /* Destroy temporary data structure */
1040 int ext4_extent_get_blocks(struct ext4_inode_ref *inode_ref, ext4_fsblk_t iblock,
1041 ext4_lblk_t max_blocks, ext4_fsblk_t *result, bool create,
1042 ext4_lblk_t *blocks_count)
1044 uint32_t iblk = iblock;
1045 ext4_fsblk_t fblk = 0;
1050 if (max_blocks != 1)
1054 r = ext4_extent_find_block(inode_ref, iblk, &fblk);
1056 r = ext4_extent_append_block(inode_ref, &iblk, &fblk, false);