2 * extent.c --- routines to implement extents support
4 * Copyright (C) 2007 Theodore Ts'o.
7 * This file may be redistributed under the terms of the GNU Library
8 * General Public License, version 2.
25 #include <sys/types.h>
35 * Definitions to be dropped in lib/ext2fs/ext2fs.h
55 struct ext2_extent_handle {
59 struct ext2_inode *inode;
60 struct ext2_inode inodebuf;
65 struct extent_path *path;
68 struct ext2_extent_path {
75 * Useful Debugging stuff
79 static void dbg_show_header(struct ext3_extent_header *eh)
81 printf("header: magic=%x entries=%u max=%u depth=%u generation=%u\n",
82 ext2fs_le16_to_cpu(eh->eh_magic),
83 ext2fs_le16_to_cpu(eh->eh_entries),
84 ext2fs_le16_to_cpu(eh->eh_max),
85 ext2fs_le16_to_cpu(eh->eh_depth),
86 ext2fs_le32_to_cpu(eh->eh_generation));
89 static void dbg_show_index(struct ext3_extent_idx *ix)
91 printf("index: block=%u leaf=%u leaf_hi=%u unused=%u\n",
92 ext2fs_le32_to_cpu(ix->ei_block),
93 ext2fs_le32_to_cpu(ix->ei_leaf),
94 ext2fs_le16_to_cpu(ix->ei_leaf_hi),
95 ext2fs_le16_to_cpu(ix->ei_unused));
98 static void dbg_show_extent(struct ext3_extent *ex)
100 printf("extent: block=%u-%u len=%u start=%u start_hi=%u\n",
101 ext2fs_le32_to_cpu(ex->ee_block),
102 ext2fs_le32_to_cpu(ex->ee_block) +
103 ext2fs_le16_to_cpu(ex->ee_len) - 1,
104 ext2fs_le16_to_cpu(ex->ee_len),
105 ext2fs_le32_to_cpu(ex->ee_start),
106 ext2fs_le16_to_cpu(ex->ee_start_hi));
109 static void dbg_print_extent(char *desc, struct ext2fs_extent *extent)
112 printf("%s: ", desc);
113 printf("extent: lblk %llu--%llu, len %u, pblk %llu, flags: ",
114 extent->e_lblk, extent->e_lblk + extent->e_len - 1,
115 extent->e_len, extent->e_pblk);
116 if (extent->e_flags & EXT2_EXTENT_FLAGS_LEAF)
117 fputs("LEAF ", stdout);
118 if (extent->e_flags & EXT2_EXTENT_FLAGS_UNINIT)
119 fputs("UNINIT ", stdout);
120 if (extent->e_flags & EXT2_EXTENT_FLAGS_SECOND_VISIT)
121 fputs("2ND_VISIT ", stdout);
122 if (!extent->e_flags)
123 fputs("(none)", stdout);
128 static void dump_path(const char *tag, struct ext2_extent_handle *handle,
129 struct extent_path *path)
131 struct extent_path *ppp = path;
132 printf("%s: level=%d\n", tag, handle->level);
135 printf("%s: path=%ld buf=%p entries=%d max_entries=%d left=%d "
136 "visit_num=%d flags=0x%x end_blk=%llu curr=%p(%ld)\n",
137 tag, (ppp - handle->path), ppp->buf, ppp->entries,
138 ppp->max_entries, ppp->left, ppp->visit_num, ppp->flags,
139 ppp->end_blk, ppp->curr, ppp->curr - (void *)ppp->buf);
141 dbg_show_header((struct ext3_extent_header *)ppp->buf);
144 dbg_show_index(ppp->curr);
146 dbg_show_extent(ppp->curr);
149 } while (ppp >= handle->path);
156 #define dbg_show_header(eh) do { } while (0)
157 #define dbg_show_index(ix) do { } while (0)
158 #define dbg_show_extent(ex) do { } while (0)
159 #define dbg_print_extent(desc, ex) do { } while (0)
160 #define dump_path(tag, handle, path) do { } while (0)
164 * Verify the extent header as being sane
166 errcode_t ext2fs_extent_header_verify(void *ptr, int size)
168 int eh_max, entry_size;
169 struct ext3_extent_header *eh = ptr;
172 if (ext2fs_le16_to_cpu(eh->eh_magic) != EXT3_EXT_MAGIC)
173 return EXT2_ET_EXTENT_HEADER_BAD;
174 if (ext2fs_le16_to_cpu(eh->eh_entries) > ext2fs_le16_to_cpu(eh->eh_max))
175 return EXT2_ET_EXTENT_HEADER_BAD;
176 if (eh->eh_depth == 0)
177 entry_size = sizeof(struct ext3_extent);
179 entry_size = sizeof(struct ext3_extent_idx);
181 eh_max = (size - sizeof(*eh)) / entry_size;
182 /* Allow two extent-sized items at the end of the block, for
183 * ext4_extent_tail with checksum in the future. */
184 if ((ext2fs_le16_to_cpu(eh->eh_max) > eh_max) ||
185 (ext2fs_le16_to_cpu(eh->eh_max) < (eh_max - 2)))
186 return EXT2_ET_EXTENT_HEADER_BAD;
193 * Begin functions to handle an inode's extent information
195 void ext2fs_extent_free(ext2_extent_handle_t handle)
203 for (i = 1; i < handle->max_paths; i++) {
204 if (handle->path[i].buf)
205 ext2fs_free_mem(&handle->path[i].buf);
207 ext2fs_free_mem(&handle->path);
209 ext2fs_free_mem(&handle);
212 errcode_t ext2fs_extent_open(ext2_filsys fs, ext2_ino_t ino,
213 ext2_extent_handle_t *ret_handle)
215 return ext2fs_extent_open2(fs, ino, NULL, ret_handle);
218 errcode_t ext2fs_extent_open2(ext2_filsys fs, ext2_ino_t ino,
219 struct ext2_inode *inode,
220 ext2_extent_handle_t *ret_handle)
222 struct ext2_extent_handle *handle;
225 struct ext3_extent_header *eh;
227 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
230 if ((ino == 0) || (ino > fs->super->s_inodes_count))
231 return EXT2_ET_BAD_INODE_NUM;
233 retval = ext2fs_get_mem(sizeof(struct ext2_extent_handle), &handle);
236 memset(handle, 0, sizeof(struct ext2_extent_handle));
242 handle->inode = inode;
244 handle->inode = &handle->inodebuf;
245 retval = ext2fs_read_inode(fs, ino, handle->inode);
250 eh = (struct ext3_extent_header *) &handle->inode->i_block[0];
252 for (i=0; i < EXT2_N_BLOCKS; i++)
253 if (handle->inode->i_block[i])
255 if (i >= EXT2_N_BLOCKS) {
256 eh->eh_magic = ext2fs_cpu_to_le16(EXT3_EXT_MAGIC);
259 i = (sizeof(handle->inode->i_block) - sizeof(*eh)) /
260 sizeof(struct ext3_extent);
261 eh->eh_max = ext2fs_cpu_to_le16(i);
262 handle->inode->i_flags |= EXT4_EXTENTS_FL;
265 if (!(handle->inode->i_flags & EXT4_EXTENTS_FL)) {
266 retval = EXT2_ET_INODE_NOT_EXTENT;
270 retval = ext2fs_extent_header_verify(eh, sizeof(handle->inode->i_block));
274 handle->max_depth = ext2fs_le16_to_cpu(eh->eh_depth);
275 handle->type = ext2fs_le16_to_cpu(eh->eh_magic);
277 handle->max_paths = handle->max_depth + 1;
278 retval = ext2fs_get_memzero(handle->max_paths *
279 sizeof(struct extent_path),
281 handle->path[0].buf = (char *) handle->inode->i_block;
283 handle->path[0].left = handle->path[0].entries =
284 ext2fs_le16_to_cpu(eh->eh_entries);
285 handle->path[0].max_entries = ext2fs_le16_to_cpu(eh->eh_max);
286 handle->path[0].curr = 0;
287 handle->path[0].end_blk =
288 (EXT2_I_SIZE(handle->inode) + fs->blocksize - 1) >>
289 EXT2_BLOCK_SIZE_BITS(fs->super);
290 handle->path[0].blk = 0;
291 handle->path[0].visit_num = 1;
293 handle->magic = EXT2_ET_MAGIC_EXTENT_HANDLE;
295 *ret_handle = handle;
299 ext2fs_extent_free(handle);
304 * This function is responsible for (optionally) moving through the
305 * extent tree and then returning the current extent
307 errcode_t ext2fs_extent_get(ext2_extent_handle_t handle,
308 int flags, struct ext2fs_extent *extent)
310 struct extent_path *path, *newpath, *tp;
311 struct ext3_extent_header *eh;
312 struct ext3_extent_idx *ix = 0;
313 struct ext3_extent *ex;
320 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
323 return EXT2_ET_NO_CURRENT_NODE;
325 orig_op = op = flags & EXT2_EXTENT_MOVE_MASK;
328 path = handle->path + handle->level;
329 if ((orig_op == EXT2_EXTENT_NEXT) ||
330 (orig_op == EXT2_EXTENT_NEXT_LEAF)) {
331 if (handle->level < handle->max_depth) {
333 if (path->visit_num == 0) {
335 op = EXT2_EXTENT_DOWN;
336 } else if (path->left > 0)
337 op = EXT2_EXTENT_NEXT_SIB;
338 else if (handle->level > 0)
341 return EXT2_ET_EXTENT_NO_NEXT;
345 op = EXT2_EXTENT_NEXT_SIB;
346 else if (handle->level > 0)
349 return EXT2_ET_EXTENT_NO_NEXT;
351 if (op != EXT2_EXTENT_NEXT_SIB) {
352 #ifdef DEBUG_GET_EXTENT
353 printf("<<<< OP = %s\n",
354 (op == EXT2_EXTENT_DOWN) ? "down" :
355 ((op == EXT2_EXTENT_UP) ? "up" : "unknown"));
360 if ((orig_op == EXT2_EXTENT_PREV) ||
361 (orig_op == EXT2_EXTENT_PREV_LEAF)) {
362 if (handle->level < handle->max_depth) {
364 if (path->visit_num > 0 ) {
365 /* path->visit_num = 0; */
366 op = EXT2_EXTENT_DOWN_AND_LAST;
367 } else if (path->left < path->entries-1)
368 op = EXT2_EXTENT_PREV_SIB;
369 else if (handle->level > 0)
372 return EXT2_ET_EXTENT_NO_PREV;
375 if (path->left < path->entries-1)
376 op = EXT2_EXTENT_PREV_SIB;
377 else if (handle->level > 0)
380 return EXT2_ET_EXTENT_NO_PREV;
382 if (op != EXT2_EXTENT_PREV_SIB) {
383 #ifdef DEBUG_GET_EXTENT
384 printf("<<<< OP = %s\n",
385 (op == EXT2_EXTENT_DOWN_AND_LAST) ? "down/last" :
386 ((op == EXT2_EXTENT_UP) ? "up" : "unknown"));
391 if (orig_op == EXT2_EXTENT_LAST_LEAF) {
392 if ((handle->level < handle->max_depth) &&
394 op = EXT2_EXTENT_DOWN;
396 op = EXT2_EXTENT_LAST_SIB;
397 #ifdef DEBUG_GET_EXTENT
398 printf("<<<< OP = %s\n",
399 (op == EXT2_EXTENT_DOWN) ? "down" : "last_sib");
404 case EXT2_EXTENT_CURRENT:
407 case EXT2_EXTENT_ROOT:
409 path = handle->path + handle->level;
411 case EXT2_EXTENT_FIRST_SIB:
412 path->left = path->entries;
415 case EXT2_EXTENT_NEXT_SIB:
417 return EXT2_ET_EXTENT_NO_NEXT;
422 eh = (struct ext3_extent_header *) path->buf;
423 ix = EXT_FIRST_INDEX(eh);
429 case EXT2_EXTENT_PREV_SIB:
431 path->left+1 >= path->entries)
432 return EXT2_ET_EXTENT_NO_PREV;
437 if (handle->level < handle->max_depth)
440 case EXT2_EXTENT_LAST_SIB:
441 eh = (struct ext3_extent_header *) path->buf;
442 path->curr = EXT_LAST_EXTENT(eh);
448 if (handle->level <= 0)
449 return EXT2_ET_EXTENT_NO_UP;
453 if ((orig_op == EXT2_EXTENT_PREV) ||
454 (orig_op == EXT2_EXTENT_PREV_LEAF))
457 case EXT2_EXTENT_DOWN:
458 case EXT2_EXTENT_DOWN_AND_LAST:
459 if (!path->curr ||(handle->level >= handle->max_depth))
460 return EXT2_ET_EXTENT_NO_DOWN;
465 retval = ext2fs_get_mem(handle->fs->blocksize,
470 blk = ext2fs_le32_to_cpu(ix->ei_leaf) +
471 ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32);
472 for (l = handle->level, tp = path; l > 0; l--, tp--) {
474 return EXT2_ET_EXTENT_CYCLE;
477 if ((handle->fs->flags & EXT2_FLAG_IMAGE_FILE) &&
478 (handle->fs->io != handle->fs->image_io))
479 memset(newpath->buf, 0, handle->fs->blocksize);
481 retval = io_channel_read_blk64(handle->fs->io,
482 blk, 1, newpath->buf);
488 eh = (struct ext3_extent_header *) newpath->buf;
490 retval = ext2fs_extent_header_verify(eh, handle->fs->blocksize);
496 if (!(handle->fs->flags & EXT2_FLAG_IGNORE_CSUM_ERRORS) &&
497 !ext2fs_extent_block_csum_verify(handle->fs, handle->ino,
501 newpath->left = newpath->entries =
502 ext2fs_le16_to_cpu(eh->eh_entries);
503 newpath->max_entries = ext2fs_le16_to_cpu(eh->eh_max);
505 /* Make sure there is at least one extent present */
506 if (newpath->left <= 0)
507 return EXT2_ET_EXTENT_NO_DOWN;
509 if (path->left > 0) {
511 newpath->end_blk = ext2fs_le32_to_cpu(ix->ei_block);
513 newpath->end_blk = path->end_blk;
516 if (op == EXT2_EXTENT_DOWN) {
517 ix = EXT_FIRST_INDEX((struct ext3_extent_header *) eh);
519 path->left = path->entries - 1;
522 ix = EXT_LAST_INDEX((struct ext3_extent_header *) eh);
525 if (handle->level < handle->max_depth)
528 #ifdef DEBUG_GET_EXTENT
529 printf("Down to level %d/%d, end_blk=%llu\n",
530 handle->level, handle->max_depth,
535 return EXT2_ET_OP_NOT_SUPPORTED;
539 return EXT2_ET_NO_CURRENT_NODE;
542 #ifdef DEBUG_GET_EXTENT
543 printf("(Left %d)\n", path->left);
546 if (handle->level == handle->max_depth) {
547 ex = (struct ext3_extent *) ix;
549 extent->e_pblk = ext2fs_le32_to_cpu(ex->ee_start) +
550 ((__u64) ext2fs_le16_to_cpu(ex->ee_start_hi) << 32);
551 extent->e_lblk = ext2fs_le32_to_cpu(ex->ee_block);
552 extent->e_len = ext2fs_le16_to_cpu(ex->ee_len);
553 extent->e_flags |= EXT2_EXTENT_FLAGS_LEAF;
554 if (extent->e_len > EXT_INIT_MAX_LEN) {
555 extent->e_len -= EXT_INIT_MAX_LEN;
556 extent->e_flags |= EXT2_EXTENT_FLAGS_UNINIT;
559 extent->e_pblk = ext2fs_le32_to_cpu(ix->ei_leaf) +
560 ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32);
561 extent->e_lblk = ext2fs_le32_to_cpu(ix->ei_block);
562 if (path->left > 0) {
564 end_blk = ext2fs_le32_to_cpu(ix->ei_block);
566 end_blk = path->end_blk;
568 extent->e_len = end_blk - extent->e_lblk;
571 extent->e_flags |= EXT2_EXTENT_FLAGS_SECOND_VISIT;
573 if (((orig_op == EXT2_EXTENT_NEXT_LEAF) ||
574 (orig_op == EXT2_EXTENT_PREV_LEAF)) &&
575 (handle->level != handle->max_depth))
578 if ((orig_op == EXT2_EXTENT_LAST_LEAF) &&
579 ((handle->level != handle->max_depth) ||
584 return EXT2_ET_EXTENT_CSUM_INVALID;
589 static errcode_t update_path(ext2_extent_handle_t handle)
593 struct ext3_extent_idx *ix;
594 struct ext3_extent_header *eh;
596 if (handle->level == 0) {
597 retval = ext2fs_write_inode(handle->fs, handle->ino,
600 ix = handle->path[handle->level - 1].curr;
601 blk = ext2fs_le32_to_cpu(ix->ei_leaf) +
602 ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32);
604 /* then update the checksum */
605 eh = (struct ext3_extent_header *)
606 handle->path[handle->level].buf;
607 retval = ext2fs_extent_block_csum_set(handle->fs, handle->ino,
612 retval = io_channel_write_blk64(handle->fs->io,
613 blk, 1, handle->path[handle->level].buf);
619 errcode_t ext2fs_extent_save_path(ext2_extent_handle_t handle,
620 ext2_extent_path_t *ret_path)
622 ext2_extent_path_t save_path;
623 struct ext2fs_extent extent;
624 struct ext2_extent_info info;
627 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
631 retval = ext2fs_extent_get_info(handle, &info);
635 retval = ext2fs_get_mem(sizeof(struct ext2_extent_path), &save_path);
638 memset(save_path, 0, sizeof(struct ext2_extent_path));
640 save_path->magic = EXT2_ET_MAGIC_EXTENT_PATH;
641 save_path->leaf_height = info.max_depth - info.curr_level - 1;
642 save_path->lblk = extent.e_lblk;
644 *ret_path = save_path;
648 errcode_t ext2fs_extent_free_path(ext2_extent_path_t path)
650 EXT2_CHECK_MAGIC(path, EXT2_ET_MAGIC_EXTENT_PATH);
652 ext2fs_free_mem(&path);
658 * Go to the node at leaf_level which contains logical block blk.
660 * leaf_level is height from the leaf node level, i.e.
661 * leaf_level 0 is at leaf node, leaf_level 1 is 1 above etc.
663 * If "blk" has no mapping (hole) then handle is left at last
666 errcode_t ext2fs_extent_goto2(ext2_extent_handle_t handle,
667 int leaf_level, blk64_t blk)
669 struct ext2fs_extent extent;
672 retval = ext2fs_extent_get(handle, EXT2_EXTENT_ROOT, &extent);
674 if (retval == EXT2_ET_EXTENT_NO_NEXT)
675 retval = EXT2_ET_EXTENT_NOT_FOUND;
679 if (leaf_level > handle->max_depth) {
681 printf("leaf level %d greater than tree depth %d\n",
682 leaf_level, handle->max_depth);
684 return EXT2_ET_OP_NOT_SUPPORTED;
688 printf("goto extent ino %u, level %d, %llu\n", handle->ino,
692 #ifdef DEBUG_GOTO_EXTENTS
693 dbg_print_extent("root", &extent);
696 if (handle->max_depth - handle->level == leaf_level) {
697 /* block is in this &extent */
698 if ((blk >= extent.e_lblk) &&
699 (blk < extent.e_lblk + extent.e_len))
701 if (blk < extent.e_lblk) {
702 retval = ext2fs_extent_get(handle,
703 EXT2_EXTENT_PREV_SIB,
705 return EXT2_ET_EXTENT_NOT_FOUND;
707 retval = ext2fs_extent_get(handle,
708 EXT2_EXTENT_NEXT_SIB,
710 if (retval == EXT2_ET_EXTENT_NO_NEXT)
711 return EXT2_ET_EXTENT_NOT_FOUND;
717 retval = ext2fs_extent_get(handle, EXT2_EXTENT_NEXT_SIB,
719 if (retval == EXT2_ET_EXTENT_NO_NEXT)
724 #ifdef DEBUG_GOTO_EXTENTS
725 dbg_print_extent("next", &extent);
727 if (blk == extent.e_lblk)
729 if (blk > extent.e_lblk)
732 retval = ext2fs_extent_get(handle, EXT2_EXTENT_PREV_SIB,
737 #ifdef DEBUG_GOTO_EXTENTS
738 dbg_print_extent("prev", &extent);
742 retval = ext2fs_extent_get(handle, EXT2_EXTENT_DOWN,
747 #ifdef DEBUG_GOTO_EXTENTS
748 dbg_print_extent("down", &extent);
753 errcode_t ext2fs_extent_goto(ext2_extent_handle_t handle,
756 return ext2fs_extent_goto2(handle, 0, blk);
760 * Traverse back up to root fixing parents of current node as needed.
762 * If we changed start of first entry in a node, fix parent index start
765 * Safe to call for any position in node; if not at the first entry,
766 * it will simply return.
768 * Note a subtlety of this function -- if there happen to be two extents
769 * mapping the same lblk and someone calls fix_parents on the second of the two
770 * extents, the position of the extent handle after the call will be the second
771 * extent if nothing happened, or the first extent if something did. A caller
772 * in this situation must use ext2fs_extent_goto() after calling this function.
773 * Or simply don't map the same lblk with two extents, ever.
775 errcode_t ext2fs_extent_fix_parents(ext2_extent_handle_t handle)
780 struct extent_path *path;
781 struct ext2fs_extent extent;
782 struct ext2_extent_info info;
784 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
786 if (!(handle->fs->flags & EXT2_FLAG_RW))
787 return EXT2_ET_RO_FILSYS;
790 return EXT2_ET_NO_CURRENT_NODE;
792 path = handle->path + handle->level;
794 return EXT2_ET_NO_CURRENT_NODE;
796 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
800 /* modified node's start block */
801 start = extent.e_lblk;
803 if ((retval = ext2fs_extent_get_info(handle, &info)))
805 orig_height = info.max_depth - info.curr_level;
807 /* traverse up until index not first, or startblk matches, or top */
808 while (handle->level > 0 &&
809 (path->left == path->entries - 1)) {
810 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent);
813 if (extent.e_lblk == start)
815 path = handle->path + handle->level;
816 extent.e_len += (extent.e_lblk - start);
817 extent.e_lblk = start;
818 retval = ext2fs_extent_replace(handle, 0, &extent);
824 /* put handle back to where we started */
825 retval = ext2fs_extent_goto2(handle, orig_height, start);
830 errcode_t ext2fs_extent_replace(ext2_extent_handle_t handle,
831 int flags EXT2FS_ATTR((unused)),
832 struct ext2fs_extent *extent)
834 struct extent_path *path;
835 struct ext3_extent_idx *ix;
836 struct ext3_extent *ex;
838 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
840 if (!(handle->fs->flags & EXT2_FLAG_RW))
841 return EXT2_ET_RO_FILSYS;
844 return EXT2_ET_NO_CURRENT_NODE;
846 path = handle->path + handle->level;
848 return EXT2_ET_NO_CURRENT_NODE;
851 printf("extent replace: %u ", handle->ino);
852 dbg_print_extent(0, extent);
855 if (handle->level == handle->max_depth) {
858 ex->ee_block = ext2fs_cpu_to_le32(extent->e_lblk);
859 ex->ee_start = ext2fs_cpu_to_le32(extent->e_pblk & 0xFFFFFFFF);
860 ex->ee_start_hi = ext2fs_cpu_to_le16(extent->e_pblk >> 32);
861 if (extent->e_flags & EXT2_EXTENT_FLAGS_UNINIT) {
862 if (extent->e_len > EXT_UNINIT_MAX_LEN)
863 return EXT2_ET_EXTENT_INVALID_LENGTH;
864 ex->ee_len = ext2fs_cpu_to_le16(extent->e_len +
867 if (extent->e_len > EXT_INIT_MAX_LEN)
868 return EXT2_ET_EXTENT_INVALID_LENGTH;
869 ex->ee_len = ext2fs_cpu_to_le16(extent->e_len);
874 ix->ei_leaf = ext2fs_cpu_to_le32(extent->e_pblk & 0xFFFFFFFF);
875 ix->ei_leaf_hi = ext2fs_cpu_to_le16(extent->e_pblk >> 32);
876 ix->ei_block = ext2fs_cpu_to_le32(extent->e_lblk);
883 static int splitting_at_eof(struct ext2_extent_handle *handle,
884 struct extent_path *path)
886 struct extent_path *ppp = path;
887 dump_path(__func__, handle, path);
889 if (handle->level == 0)
896 } while (ppp >= handle->path);
902 * allocate a new block, move half the current node to it, and update parent
904 * handle will be left pointing at original record.
906 static errcode_t extent_node_split(ext2_extent_handle_t handle,
909 errcode_t retval = 0;
910 blk64_t new_node_pblk;
911 blk64_t new_node_start;
913 blk64_t goal_blk = 0;
915 char *block_buf = NULL;
916 struct ext2fs_extent extent;
917 struct extent_path *path, *newpath = 0;
918 struct ext3_extent_header *eh, *neweh;
921 struct ext2_extent_info info;
925 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
927 if (!(handle->fs->flags & EXT2_FLAG_RW))
928 return EXT2_ET_RO_FILSYS;
931 return EXT2_ET_NO_CURRENT_NODE;
934 printf("splitting node at level %d\n", handle->level);
936 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
940 retval = ext2fs_extent_get_info(handle, &info);
944 /* save the position we were originally splitting... */
945 orig_height = info.max_depth - info.curr_level;
946 orig_lblk = extent.e_lblk;
948 /* Try to put the index block before the first extent */
949 path = handle->path + handle->level;
950 eh = (struct ext3_extent_header *) path->buf;
951 if (handle->level == handle->max_depth) {
952 struct ext3_extent *ex;
954 ex = EXT_FIRST_EXTENT(eh);
955 goal_blk = ext2fs_le32_to_cpu(ex->ee_start) +
956 ((__u64) ext2fs_le16_to_cpu(ex->ee_start_hi) << 32);
958 struct ext3_extent_idx *ix;
960 ix = EXT_FIRST_INDEX(eh);
961 goal_blk = ext2fs_le32_to_cpu(ix->ei_leaf) +
962 ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32);
964 goal_blk -= EXT2FS_CLUSTER_RATIO(handle->fs);
965 goal_blk &= ~EXT2FS_CLUSTER_MASK(handle->fs);
967 /* Is there room in the parent for a new entry? */
969 (handle->path[handle->level - 1].entries >=
970 handle->path[handle->level - 1].max_entries)) {
973 printf("parent level %d full; splitting it too\n",
976 /* split the parent */
977 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent);
981 retval = extent_node_split(handle, expand_allowed);
985 /* get handle back to our original split position */
986 retval = ext2fs_extent_goto2(handle, orig_height, orig_lblk);
991 /* At this point, parent should have room for this split */
992 path = handle->path + handle->level;
994 return EXT2_ET_NO_CURRENT_NODE;
997 * Normally, we try to split a full node in half. This doesn't turn
998 * out so well if we're tacking extents on the end of the file because
999 * then we're stuck with a tree of half-full extent blocks. This of
1000 * course doesn't apply to the root level.
1002 no_balance = expand_allowed ? splitting_at_eof(handle, path) : 0;
1004 /* extent header of the current node we'll split */
1005 eh = (struct ext3_extent_header *)path->buf;
1007 /* splitting root level means moving them all out */
1008 if (handle->level == 0) {
1010 tocopy = ext2fs_le16_to_cpu(eh->eh_entries);
1011 retval = ext2fs_get_memzero((handle->max_paths + 1) *
1012 sizeof(struct extent_path),
1020 tocopy = ext2fs_le16_to_cpu(eh->eh_entries) / 2;
1024 printf("will copy out %d of %d entries at level %d\n",
1025 tocopy, ext2fs_le16_to_cpu(eh->eh_entries),
1029 if (!tocopy && !no_balance) {
1031 printf("Nothing to copy to new block!\n");
1033 retval = EXT2_ET_CANT_SPLIT_EXTENT;
1037 /* first we need a new block, or can do nothing. */
1038 block_buf = malloc(handle->fs->blocksize);
1045 goal_blk = ext2fs_find_inode_goal(handle->fs, handle->ino,
1047 retval = ext2fs_alloc_block2(handle->fs, goal_blk, block_buf,
1053 printf("will copy to new node at block %lu\n",
1054 (unsigned long) new_node_pblk);
1057 /* Copy data into new block buffer */
1058 /* First the header for the new block... */
1059 neweh = (struct ext3_extent_header *) block_buf;
1060 memcpy(neweh, eh, sizeof(struct ext3_extent_header));
1061 neweh->eh_entries = ext2fs_cpu_to_le16(tocopy);
1062 neweh->eh_max = ext2fs_cpu_to_le16((handle->fs->blocksize -
1063 sizeof(struct ext3_extent_header)) /
1064 sizeof(struct ext3_extent));
1066 /* then the entries for the new block... */
1067 memcpy(EXT_FIRST_INDEX(neweh),
1068 EXT_FIRST_INDEX(eh) +
1069 (ext2fs_le16_to_cpu(eh->eh_entries) - tocopy),
1070 sizeof(struct ext3_extent_idx) * tocopy);
1072 new_node_start = ext2fs_le32_to_cpu(EXT_FIRST_INDEX(neweh)->ei_block);
1074 /* then update the checksum */
1075 retval = ext2fs_extent_block_csum_set(handle->fs, handle->ino, neweh);
1079 /* ...and write the new node block out to disk. */
1080 retval = io_channel_write_blk64(handle->fs->io, new_node_pblk, 1,
1086 /* OK! we've created the new node; now adjust the tree */
1088 /* current path now has fewer active entries, we copied some out */
1089 if (handle->level == 0) {
1090 memcpy(newpath, path,
1091 sizeof(struct extent_path) * handle->max_paths);
1092 handle->path = newpath;
1094 path = handle->path;
1096 path->left = path->max_entries - 1;
1097 handle->max_depth++;
1098 handle->max_paths++;
1099 eh->eh_depth = ext2fs_cpu_to_le16(handle->max_depth);
1101 path->entries -= tocopy;
1102 path->left -= tocopy;
1105 eh->eh_entries = ext2fs_cpu_to_le16(path->entries);
1106 /* this writes out the node, incl. the modified header */
1107 retval = update_path(handle);
1111 /* now go up and insert/replace index for new node we created */
1113 retval = ext2fs_extent_get(handle, EXT2_EXTENT_FIRST_SIB, &extent);
1117 extent.e_lblk = new_node_start;
1118 extent.e_pblk = new_node_pblk;
1119 extent.e_len = handle->path[0].end_blk - extent.e_lblk;
1120 retval = ext2fs_extent_replace(handle, 0, &extent);
1124 __u32 new_node_length;
1126 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent);
1127 /* will insert after this one; it's length is shorter now */
1128 new_node_length = new_node_start - extent.e_lblk;
1129 extent.e_len -= new_node_length;
1130 retval = ext2fs_extent_replace(handle, 0, &extent);
1134 /* now set up the new extent and insert it */
1135 extent.e_lblk = new_node_start;
1136 extent.e_pblk = new_node_pblk;
1137 extent.e_len = new_node_length;
1138 retval = ext2fs_extent_insert(handle, EXT2_EXTENT_INSERT_AFTER, &extent);
1143 /* get handle back to our original position */
1144 retval = ext2fs_extent_goto2(handle, orig_height, orig_lblk);
1148 /* new node hooked in, so update inode block count (do this here?) */
1149 ext2fs_iblk_add_blocks(handle->fs, handle->inode, 1);
1150 retval = ext2fs_write_inode(handle->fs, handle->ino,
1157 ext2fs_free_mem(&newpath);
1163 errcode_t ext2fs_extent_node_split(ext2_extent_handle_t handle)
1165 return extent_node_split(handle, 0);
1168 errcode_t ext2fs_extent_insert(ext2_extent_handle_t handle, int flags,
1169 struct ext2fs_extent *extent)
1171 struct extent_path *path;
1172 struct ext3_extent_idx *ix;
1173 struct ext3_extent_header *eh;
1176 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
1178 if (!(handle->fs->flags & EXT2_FLAG_RW))
1179 return EXT2_ET_RO_FILSYS;
1182 return EXT2_ET_NO_CURRENT_NODE;
1185 printf("extent insert: %u ", handle->ino);
1186 dbg_print_extent(0, extent);
1189 path = handle->path + handle->level;
1191 if (path->entries >= path->max_entries) {
1192 if (flags & EXT2_EXTENT_INSERT_NOSPLIT) {
1193 return EXT2_ET_CANT_INSERT_EXTENT;
1196 printf("node full (level %d) - splitting\n",
1199 retval = extent_node_split(handle, 1);
1202 path = handle->path + handle->level;
1206 eh = (struct ext3_extent_header *) path->buf;
1209 if (flags & EXT2_EXTENT_INSERT_AFTER) {
1214 ix = EXT_FIRST_INDEX(eh);
1220 if (path->left >= 0)
1222 (path->left+1) * sizeof(struct ext3_extent_idx));
1226 eh = (struct ext3_extent_header *) path->buf;
1227 eh->eh_entries = ext2fs_cpu_to_le16(path->entries);
1229 retval = ext2fs_extent_replace(handle, 0, extent);
1233 retval = update_path(handle);
1240 ext2fs_extent_delete(handle, 0);
1245 * Sets the physical block for a logical file block in the extent tree.
1247 * May: map unmapped, unmap mapped, or remap mapped blocks.
1249 * Mapping an unmapped block adds a single-block extent.
1251 * Unmapping first or last block modifies extent in-place
1252 * - But may need to fix parent's starts too in first-block case
1254 * Mapping any unmapped block requires adding a (single-block) extent
1255 * and inserting into proper point in tree.
1257 * Modifying (unmapping or remapping) a block in the middle
1258 * of an extent requires splitting the extent.
1259 * - Remapping case requires new single-block extent.
1261 * Remapping first or last block adds an extent.
1263 * We really need extent adding to be smart about merging.
1266 errcode_t ext2fs_extent_set_bmap(ext2_extent_handle_t handle,
1267 blk64_t logical, blk64_t physical, int flags)
1269 errcode_t ec, retval = 0;
1270 int mapped = 1; /* logical is mapped? */
1272 int extent_uninit = 0;
1273 int prev_uninit = 0;
1274 int next_uninit = 0;
1276 int max_len = EXT_INIT_MAX_LEN;
1277 int has_prev, has_next;
1279 struct extent_path *path;
1280 struct ext2fs_extent extent, next_extent, prev_extent;
1281 struct ext2fs_extent newextent;
1282 struct ext2_extent_info info;
1284 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
1287 printf("set_bmap ino %u log %lld phys %lld flags %d\n",
1288 handle->ino, logical, physical, flags);
1291 if (!(handle->fs->flags & EXT2_FLAG_RW))
1292 return EXT2_ET_RO_FILSYS;
1295 return EXT2_ET_NO_CURRENT_NODE;
1297 path = handle->path + handle->level;
1299 if (flags & EXT2_EXTENT_SET_BMAP_UNINIT) {
1301 max_len = EXT_UNINIT_MAX_LEN;
1304 /* if (re)mapping, set up new extent to insert */
1306 newextent.e_len = 1;
1307 newextent.e_pblk = physical;
1308 newextent.e_lblk = logical;
1309 newextent.e_flags = EXT2_EXTENT_FLAGS_LEAF;
1311 newextent.e_flags |= EXT2_EXTENT_FLAGS_UNINIT;
1314 /* special case if the extent tree is completely empty */
1315 if ((handle->max_depth == 0) && (path->entries == 0)) {
1316 retval = ext2fs_extent_insert(handle, 0, &newextent);
1320 /* save our original location in the extent tree */
1321 if ((retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT,
1323 if (retval != EXT2_ET_NO_CURRENT_NODE)
1325 memset(&extent, 0, sizeof(extent));
1327 if ((retval = ext2fs_extent_get_info(handle, &info)))
1329 orig_height = info.max_depth - info.curr_level;
1330 orig_lblk = extent.e_lblk;
1332 /* go to the logical spot we want to (re/un)map */
1333 retval = ext2fs_extent_goto(handle, logical);
1335 if (retval == EXT2_ET_EXTENT_NOT_FOUND) {
1340 printf("block %llu already unmapped\n",
1350 * This may be the extent *before* the requested logical,
1351 * if it's currently unmapped.
1353 * Get the previous and next leaf extents, if they are present.
1355 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
1358 if (extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT)
1360 retval = ext2fs_extent_get(handle, EXT2_EXTENT_NEXT_LEAF, &next_extent);
1363 if (retval != EXT2_ET_EXTENT_NO_NEXT)
1366 dbg_print_extent("set_bmap: next_extent",
1369 if (next_extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT)
1372 retval = ext2fs_extent_goto(handle, logical);
1373 if (retval && retval != EXT2_ET_EXTENT_NOT_FOUND)
1375 retval = ext2fs_extent_get(handle, EXT2_EXTENT_PREV_LEAF, &prev_extent);
1378 if (retval != EXT2_ET_EXTENT_NO_PREV)
1382 dbg_print_extent("set_bmap: prev_extent",
1384 if (prev_extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT)
1387 retval = ext2fs_extent_goto(handle, logical);
1388 if (retval && retval != EXT2_ET_EXTENT_NOT_FOUND)
1391 /* check if already pointing to the requested physical */
1392 if (mapped && (new_uninit == extent_uninit) &&
1393 (extent.e_pblk + (logical - extent.e_lblk) == physical)) {
1395 printf("physical block (at %llu) unchanged\n", logical);
1402 printf("mapping unmapped logical block %llu\n", logical);
1404 if ((logical == extent.e_lblk + extent.e_len) &&
1405 (physical == extent.e_pblk + extent.e_len) &&
1406 (new_uninit == extent_uninit) &&
1407 ((int) extent.e_len < max_len-1)) {
1409 retval = ext2fs_extent_replace(handle, 0, &extent);
1410 } else if ((logical == extent.e_lblk - 1) &&
1411 (physical == extent.e_pblk - 1) &&
1412 (new_uninit == extent_uninit) &&
1413 ((int) extent.e_len < max_len - 1)) {
1417 retval = ext2fs_extent_replace(handle, 0, &extent);
1418 } else if (has_next &&
1419 (logical == next_extent.e_lblk - 1) &&
1420 (physical == next_extent.e_pblk - 1) &&
1421 (new_uninit == next_uninit) &&
1422 ((int) next_extent.e_len < max_len - 1)) {
1423 retval = ext2fs_extent_get(handle,
1424 EXT2_EXTENT_NEXT_LEAF,
1428 next_extent.e_len++;
1429 next_extent.e_lblk--;
1430 next_extent.e_pblk--;
1431 retval = ext2fs_extent_replace(handle, 0, &next_extent);
1432 } else if (logical < extent.e_lblk)
1433 retval = ext2fs_extent_insert(handle, 0, &newextent);
1435 retval = ext2fs_extent_insert(handle,
1436 EXT2_EXTENT_INSERT_AFTER, &newextent);
1439 retval = ext2fs_extent_fix_parents(handle);
1442 } else if ((logical == extent.e_lblk) && (extent.e_len == 1)) {
1444 printf("(re/un)mapping only block in extent\n");
1447 retval = ext2fs_extent_replace(handle, 0, &newextent);
1449 retval = ext2fs_extent_delete(handle, 0);
1452 ec = ext2fs_extent_fix_parents(handle);
1453 if (ec != EXT2_ET_NO_CURRENT_NODE)
1459 } else if (logical == extent.e_lblk + extent.e_len - 1) {
1461 printf("(re/un)mapping last block in extent\n");
1465 (logical == (next_extent.e_lblk - 1)) &&
1466 (physical == (next_extent.e_pblk - 1)) &&
1467 (new_uninit == next_uninit) &&
1468 ((int) next_extent.e_len < max_len - 1)) {
1469 retval = ext2fs_extent_get(handle,
1470 EXT2_EXTENT_NEXT_LEAF, &next_extent);
1473 next_extent.e_len++;
1474 next_extent.e_lblk--;
1475 next_extent.e_pblk--;
1476 retval = ext2fs_extent_replace(handle, 0,
1481 retval = ext2fs_extent_insert(handle,
1482 EXT2_EXTENT_INSERT_AFTER, &newextent);
1485 retval = ext2fs_extent_fix_parents(handle);
1489 * Now pointing at inserted extent; move back to prev.
1491 * We cannot use EXT2_EXTENT_PREV to go back; note the
1492 * subtlety in the comment for fix_parents().
1494 retval = ext2fs_extent_goto(handle, logical);
1497 retval = ext2fs_extent_get(handle,
1498 EXT2_EXTENT_CURRENT,
1504 retval = ext2fs_extent_replace(handle, 0, &extent);
1507 } else if (logical == extent.e_lblk) {
1509 printf("(re/un)mapping first block in extent\n");
1513 (logical == (prev_extent.e_lblk +
1514 prev_extent.e_len)) &&
1515 (physical == (prev_extent.e_pblk +
1516 prev_extent.e_len)) &&
1517 (new_uninit == prev_uninit) &&
1518 ((int) prev_extent.e_len < max_len-1)) {
1519 retval = ext2fs_extent_get(handle,
1520 EXT2_EXTENT_PREV_LEAF, &prev_extent);
1523 prev_extent.e_len++;
1524 retval = ext2fs_extent_replace(handle, 0,
1527 retval = ext2fs_extent_insert(handle,
1531 retval = ext2fs_extent_fix_parents(handle);
1534 retval = ext2fs_extent_get(handle,
1535 EXT2_EXTENT_NEXT_LEAF,
1543 retval = ext2fs_extent_replace(handle, 0, &extent);
1546 retval = ext2fs_extent_fix_parents(handle);
1552 struct ext2fs_extent save_extent;
1556 printf("(re/un)mapping in middle of extent\n");
1558 /* need to split this extent; later */
1559 save_lblk = extent.e_lblk;
1560 save_length = extent.e_len;
1561 save_extent = extent;
1563 /* shorten pre-split extent */
1564 extent.e_len = (logical - extent.e_lblk);
1565 retval = ext2fs_extent_replace(handle, 0, &extent);
1568 /* insert our new extent, if any */
1570 /* insert new extent after current */
1571 retval = ext2fs_extent_insert(handle,
1572 EXT2_EXTENT_INSERT_AFTER, &newextent);
1574 r2 = ext2fs_extent_goto(handle, save_lblk);
1576 (void)ext2fs_extent_replace(handle, 0,
1581 /* add post-split extent */
1582 extent.e_pblk += extent.e_len + 1;
1583 extent.e_lblk += extent.e_len + 1;
1584 extent.e_len = save_length - extent.e_len - 1;
1585 retval = ext2fs_extent_insert(handle,
1586 EXT2_EXTENT_INSERT_AFTER, &extent);
1589 r2 = ext2fs_extent_goto(handle,
1592 (void)ext2fs_extent_delete(handle, 0);
1594 r2 = ext2fs_extent_goto(handle, save_lblk);
1596 (void)ext2fs_extent_replace(handle, 0,
1603 /* get handle back to its position */
1604 if (orig_height > handle->max_depth)
1605 orig_height = handle->max_depth; /* In case we shortened the tree */
1606 ext2fs_extent_goto2(handle, orig_height, orig_lblk);
1610 errcode_t ext2fs_extent_delete(ext2_extent_handle_t handle, int flags)
1612 struct extent_path *path;
1614 struct ext3_extent_header *eh;
1615 errcode_t retval = 0;
1617 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
1619 if (!(handle->fs->flags & EXT2_FLAG_RW))
1620 return EXT2_ET_RO_FILSYS;
1623 return EXT2_ET_NO_CURRENT_NODE;
1627 struct ext2fs_extent extent;
1629 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT,
1632 printf("extent delete %u ", handle->ino);
1633 dbg_print_extent(0, &extent);
1638 path = handle->path + handle->level;
1640 return EXT2_ET_NO_CURRENT_NODE;
1644 /* Sanity check before memmove() */
1646 return EXT2_ET_EXTENT_LEAF_BAD;
1649 memmove(cp, cp + sizeof(struct ext3_extent_idx),
1650 path->left * sizeof(struct ext3_extent_idx));
1653 struct ext3_extent_idx *ix = path->curr;
1657 if (--path->entries == 0)
1660 /* if non-root node has no entries left, remove it & parent ptr to it */
1661 if (path->entries == 0 && handle->level) {
1662 if (!(flags & EXT2_EXTENT_DELETE_KEEP_EMPTY)) {
1663 struct ext2fs_extent extent;
1665 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP,
1670 retval = ext2fs_extent_delete(handle, flags);
1671 handle->inode->i_blocks -=
1672 (handle->fs->blocksize *
1673 EXT2FS_CLUSTER_RATIO(handle->fs)) / 512;
1674 retval = ext2fs_write_inode(handle->fs, handle->ino,
1676 ext2fs_block_alloc_stats2(handle->fs,
1680 eh = (struct ext3_extent_header *) path->buf;
1681 eh->eh_entries = ext2fs_cpu_to_le16(path->entries);
1682 if ((path->entries == 0) && (handle->level == 0)) {
1684 handle->max_depth = 0;
1686 retval = update_path(handle);
1691 errcode_t ext2fs_extent_get_info(ext2_extent_handle_t handle,
1692 struct ext2_extent_info *info)
1694 struct extent_path *path;
1696 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
1698 memset(info, 0, sizeof(struct ext2_extent_info));
1700 path = handle->path + handle->level;
1703 info->curr_entry = ((char *) path->curr - path->buf) /
1704 sizeof(struct ext3_extent_idx);
1706 info->curr_entry = 0;
1707 info->num_entries = path->entries;
1708 info->max_entries = path->max_entries;
1709 info->bytes_avail = (path->max_entries - path->entries) *
1710 sizeof(struct ext3_extent);
1713 info->curr_level = handle->level;
1714 info->max_depth = handle->max_depth;
1715 info->max_lblk = EXT_MAX_EXTENT_LBLK;
1716 info->max_pblk = EXT_MAX_EXTENT_PBLK;
1717 info->max_len = EXT_INIT_MAX_LEN;
1718 info->max_uninit_len = EXT_UNINIT_MAX_LEN;
1723 static int ul_log2(unsigned long arg)
1735 size_t ext2fs_max_extent_depth(ext2_extent_handle_t handle)
1737 size_t iblock_sz = sizeof(((struct ext2_inode *)NULL)->i_block);
1738 size_t iblock_extents = (iblock_sz - sizeof(struct ext3_extent_header)) /
1739 sizeof(struct ext3_extent);
1740 size_t extents_per_block = (handle->fs->blocksize -
1741 sizeof(struct ext3_extent_header)) /
1742 sizeof(struct ext3_extent);
1743 static unsigned int last_blocksize = 0;
1744 static size_t last_result = 0;
1746 if (last_blocksize && last_blocksize == handle->fs->blocksize)
1749 last_result = 1 + ((ul_log2(EXT_MAX_EXTENT_LBLK) - ul_log2(iblock_extents)) /
1750 ul_log2(extents_per_block));
1751 last_blocksize = handle->fs->blocksize;
1755 errcode_t ext2fs_fix_extents_checksums(ext2_filsys fs, ext2_ino_t ino,
1756 struct ext2_inode *inode)
1758 ext2_extent_handle_t handle;
1759 struct ext2fs_extent extent;
1761 int save_flags = fs->flags;
1763 if (!ext2fs_has_feature_metadata_csum(fs->super) ||
1764 (inode && !(inode->i_flags & EXT4_EXTENTS_FL)))
1767 errcode = ext2fs_extent_open2(fs, ino, inode, &handle);
1769 if (errcode == EXT2_ET_INODE_NOT_EXTENT)
1774 fs->flags &= ~EXT2_FLAG_IGNORE_CSUM_ERRORS;
1775 errcode = ext2fs_extent_get(handle, EXT2_EXTENT_ROOT, &extent);
1780 /* Skip to the end of a block of leaf nodes */
1781 if (extent.e_flags & EXT2_EXTENT_FLAGS_LEAF) {
1782 errcode = ext2fs_extent_get(handle,
1783 EXT2_EXTENT_LAST_SIB,
1789 errcode = ext2fs_extent_get(handle, EXT2_EXTENT_NEXT, &extent);
1790 if (errcode == EXT2_ET_EXTENT_CSUM_INVALID)
1791 errcode = update_path(handle);
1792 } while (errcode == 0);
1795 /* Ok if we run off the end */
1796 if (errcode == EXT2_ET_EXTENT_NO_NEXT)
1798 ext2fs_extent_free(handle);
1799 fs->flags = save_flags;
1803 errcode_t ext2fs_decode_extent(struct ext2fs_extent *to, void *addr, int len)
1805 struct ext3_extent *from = (struct ext3_extent *)addr;
1807 if (len != sizeof(struct ext3_extent))
1808 return EXT2_ET_INVALID_ARGUMENT;
1810 to->e_pblk = ext2fs_le32_to_cpu(from->ee_start) +
1811 ((__u64) ext2fs_le16_to_cpu(from->ee_start_hi)
1813 to->e_lblk = ext2fs_le32_to_cpu(from->ee_block);
1814 to->e_len = ext2fs_le16_to_cpu(from->ee_len);
1815 to->e_flags = EXT2_EXTENT_FLAGS_LEAF;
1816 if (to->e_len > EXT_INIT_MAX_LEN) {
1817 to->e_len -= EXT_INIT_MAX_LEN;
1818 to->e_flags |= EXT2_EXTENT_FLAGS_UNINIT;
1824 errcode_t ext2fs_count_blocks(ext2_filsys fs, ext2_ino_t ino,
1825 struct ext2_inode *inode, blk64_t *ret_count)
1827 ext2_extent_handle_t handle = NULL;
1828 struct ext2fs_extent extent;
1831 blk64_t blkcount = 0;
1832 blk64_t *intermediate_nodes;
1834 errcode = ext2fs_extent_open2(fs, ino, inode, &handle);
1838 errcode = ext2fs_extent_get(handle, EXT2_EXTENT_ROOT, &extent);
1842 errcode = ext2fs_get_array(handle->max_depth, sizeof(blk64_t),
1843 &intermediate_nodes);
1847 blkcount = handle->level;
1849 if (extent.e_flags & EXT2_EXTENT_FLAGS_LEAF) {
1850 blkcount += extent.e_len;
1851 for (i = 0; i < handle->level; i++) {
1852 if (intermediate_nodes[i] !=
1853 handle->path[i].end_blk) {
1855 intermediate_nodes[i] =
1856 handle->path[i].end_blk;
1860 errcode = ext2fs_extent_get(handle, EXT2_EXTENT_NEXT, &extent);
1862 ext2fs_free_mem(&intermediate_nodes);
1864 *ret_count = blkcount;
1865 ext2fs_extent_free(handle);
1872 * Override debugfs's prompt
1874 const char *debug_prog_name = "tst_extents";