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
54 struct ext2_extent_handle
{
58 struct ext2_inode
*inode
;
59 struct ext2_inode inodebuf
;
64 struct extent_path
*path
;
67 struct ext2_extent_path
{
74 * Useful Debugging stuff
78 static void dbg_show_header(struct ext3_extent_header
*eh
)
80 printf("header: magic=%x entries=%u max=%u depth=%u generation=%u\n",
81 ext2fs_le16_to_cpu(eh
->eh_magic
),
82 ext2fs_le16_to_cpu(eh
->eh_entries
),
83 ext2fs_le16_to_cpu(eh
->eh_max
),
84 ext2fs_le16_to_cpu(eh
->eh_depth
),
85 ext2fs_le32_to_cpu(eh
->eh_generation
));
88 static void dbg_show_index(struct ext3_extent_idx
*ix
)
90 printf("index: block=%u leaf=%u leaf_hi=%u unused=%u\n",
91 ext2fs_le32_to_cpu(ix
->ei_block
),
92 ext2fs_le32_to_cpu(ix
->ei_leaf
),
93 ext2fs_le16_to_cpu(ix
->ei_leaf_hi
),
94 ext2fs_le16_to_cpu(ix
->ei_unused
));
97 static void dbg_show_extent(struct ext3_extent
*ex
)
99 printf("extent: block=%u-%u len=%u start=%u start_hi=%u\n",
100 ext2fs_le32_to_cpu(ex
->ee_block
),
101 ext2fs_le32_to_cpu(ex
->ee_block
) +
102 ext2fs_le16_to_cpu(ex
->ee_len
) - 1,
103 ext2fs_le16_to_cpu(ex
->ee_len
),
104 ext2fs_le32_to_cpu(ex
->ee_start
),
105 ext2fs_le16_to_cpu(ex
->ee_start_hi
));
108 static void dbg_print_extent(char *desc
, struct ext2fs_extent
*extent
)
111 printf("%s: ", desc
);
112 printf("extent: lblk %llu--%llu, len %u, pblk %llu, flags: ",
113 extent
->e_lblk
, extent
->e_lblk
+ extent
->e_len
- 1,
114 extent
->e_len
, extent
->e_pblk
);
115 if (extent
->e_flags
& EXT2_EXTENT_FLAGS_LEAF
)
116 fputs("LEAF ", stdout
);
117 if (extent
->e_flags
& EXT2_EXTENT_FLAGS_UNINIT
)
118 fputs("UNINIT ", stdout
);
119 if (extent
->e_flags
& EXT2_EXTENT_FLAGS_SECOND_VISIT
)
120 fputs("2ND_VISIT ", stdout
);
121 if (!extent
->e_flags
)
122 fputs("(none)", stdout
);
127 static void dump_path(const char *tag
, struct ext2_extent_handle
*handle
,
128 struct extent_path
*path
)
130 struct extent_path
*ppp
= path
;
131 printf("%s: level=%d\n", tag
, handle
->level
);
134 printf("%s: path=%ld buf=%p entries=%d max_entries=%d left=%d "
135 "visit_num=%d flags=0x%x end_blk=%llu curr=%p(%ld)\n",
136 tag
, (ppp
- handle
->path
), ppp
->buf
, ppp
->entries
,
137 ppp
->max_entries
, ppp
->left
, ppp
->visit_num
, ppp
->flags
,
138 ppp
->end_blk
, ppp
->curr
, ppp
->curr
- (void *)ppp
->buf
);
140 dbg_show_header((struct ext3_extent_header
*)ppp
->buf
);
143 dbg_show_index(ppp
->curr
);
145 dbg_show_extent(ppp
->curr
);
148 } while (ppp
>= handle
->path
);
155 #define dbg_show_header(eh) do { } while (0)
156 #define dbg_show_index(ix) do { } while (0)
157 #define dbg_show_extent(ex) do { } while (0)
158 #define dbg_print_extent(desc, ex) do { } while (0)
159 #define dump_path(tag, handle, path) do { } while (0)
163 * Verify the extent header as being sane
165 errcode_t
ext2fs_extent_header_verify(void *ptr
, int size
)
167 int eh_max
, entry_size
;
168 struct ext3_extent_header
*eh
= ptr
;
171 if (ext2fs_le16_to_cpu(eh
->eh_magic
) != EXT3_EXT_MAGIC
)
172 return EXT2_ET_EXTENT_HEADER_BAD
;
173 if (ext2fs_le16_to_cpu(eh
->eh_entries
) > ext2fs_le16_to_cpu(eh
->eh_max
))
174 return EXT2_ET_EXTENT_HEADER_BAD
;
175 if (eh
->eh_depth
== 0)
176 entry_size
= sizeof(struct ext3_extent
);
178 entry_size
= sizeof(struct ext3_extent_idx
);
180 eh_max
= (size
- sizeof(*eh
)) / entry_size
;
181 /* Allow two extent-sized items at the end of the block, for
182 * ext4_extent_tail with checksum in the future. */
183 if ((ext2fs_le16_to_cpu(eh
->eh_max
) > eh_max
) ||
184 (ext2fs_le16_to_cpu(eh
->eh_max
) < (eh_max
- 2)))
185 return EXT2_ET_EXTENT_HEADER_BAD
;
192 * Begin functions to handle an inode's extent information
194 void ext2fs_extent_free(ext2_extent_handle_t handle
)
202 for (i
= 1; i
< handle
->max_paths
; i
++) {
203 if (handle
->path
[i
].buf
)
204 ext2fs_free_mem(&handle
->path
[i
].buf
);
206 ext2fs_free_mem(&handle
->path
);
208 ext2fs_free_mem(&handle
);
211 errcode_t
ext2fs_extent_open(ext2_filsys fs
, ext2_ino_t ino
,
212 ext2_extent_handle_t
*ret_handle
)
214 return ext2fs_extent_open2(fs
, ino
, NULL
, ret_handle
);
217 errcode_t
ext2fs_extent_open2(ext2_filsys fs
, ext2_ino_t ino
,
218 struct ext2_inode
*inode
,
219 ext2_extent_handle_t
*ret_handle
)
221 struct ext2_extent_handle
*handle
;
224 struct ext3_extent_header
*eh
;
226 EXT2_CHECK_MAGIC(fs
, EXT2_ET_MAGIC_EXT2FS_FILSYS
);
229 if ((ino
== 0) || (ino
> fs
->super
->s_inodes_count
))
230 return EXT2_ET_BAD_INODE_NUM
;
232 retval
= ext2fs_get_mem(sizeof(struct ext2_extent_handle
), &handle
);
235 memset(handle
, 0, sizeof(struct ext2_extent_handle
));
241 handle
->inode
= inode
;
243 handle
->inode
= &handle
->inodebuf
;
244 retval
= ext2fs_read_inode(fs
, ino
, handle
->inode
);
249 eh
= (struct ext3_extent_header
*) &handle
->inode
->i_block
[0];
251 for (i
=0; i
< EXT2_N_BLOCKS
; i
++)
252 if (handle
->inode
->i_block
[i
])
254 if (i
>= EXT2_N_BLOCKS
) {
255 eh
->eh_magic
= ext2fs_cpu_to_le16(EXT3_EXT_MAGIC
);
258 i
= (sizeof(handle
->inode
->i_block
) - sizeof(*eh
)) /
259 sizeof(struct ext3_extent
);
260 eh
->eh_max
= ext2fs_cpu_to_le16(i
);
261 handle
->inode
->i_flags
|= EXT4_EXTENTS_FL
;
264 if (!(handle
->inode
->i_flags
& EXT4_EXTENTS_FL
)) {
265 retval
= EXT2_ET_INODE_NOT_EXTENT
;
269 retval
= ext2fs_extent_header_verify(eh
, sizeof(handle
->inode
->i_block
));
273 handle
->max_depth
= ext2fs_le16_to_cpu(eh
->eh_depth
);
274 handle
->type
= ext2fs_le16_to_cpu(eh
->eh_magic
);
276 handle
->max_paths
= handle
->max_depth
+ 1;
277 retval
= ext2fs_get_memzero(handle
->max_paths
*
278 sizeof(struct extent_path
),
280 handle
->path
[0].buf
= (char *) handle
->inode
->i_block
;
282 handle
->path
[0].left
= handle
->path
[0].entries
=
283 ext2fs_le16_to_cpu(eh
->eh_entries
);
284 handle
->path
[0].max_entries
= ext2fs_le16_to_cpu(eh
->eh_max
);
285 handle
->path
[0].curr
= 0;
286 handle
->path
[0].end_blk
=
287 (EXT2_I_SIZE(handle
->inode
) + fs
->blocksize
- 1) >>
288 EXT2_BLOCK_SIZE_BITS(fs
->super
);
289 handle
->path
[0].visit_num
= 1;
291 handle
->magic
= EXT2_ET_MAGIC_EXTENT_HANDLE
;
293 *ret_handle
= handle
;
297 ext2fs_extent_free(handle
);
302 * This function is responsible for (optionally) moving through the
303 * extent tree and then returning the current extent
305 errcode_t
ext2fs_extent_get(ext2_extent_handle_t handle
,
306 int flags
, struct ext2fs_extent
*extent
)
308 struct extent_path
*path
, *newpath
;
309 struct ext3_extent_header
*eh
;
310 struct ext3_extent_idx
*ix
= 0;
311 struct ext3_extent
*ex
;
318 EXT2_CHECK_MAGIC(handle
, EXT2_ET_MAGIC_EXTENT_HANDLE
);
321 return EXT2_ET_NO_CURRENT_NODE
;
323 orig_op
= op
= flags
& EXT2_EXTENT_MOVE_MASK
;
326 path
= handle
->path
+ handle
->level
;
327 if ((orig_op
== EXT2_EXTENT_NEXT
) ||
328 (orig_op
== EXT2_EXTENT_NEXT_LEAF
)) {
329 if (handle
->level
< handle
->max_depth
) {
331 if (path
->visit_num
== 0) {
333 op
= EXT2_EXTENT_DOWN
;
334 } else if (path
->left
> 0)
335 op
= EXT2_EXTENT_NEXT_SIB
;
336 else if (handle
->level
> 0)
339 return EXT2_ET_EXTENT_NO_NEXT
;
343 op
= EXT2_EXTENT_NEXT_SIB
;
344 else if (handle
->level
> 0)
347 return EXT2_ET_EXTENT_NO_NEXT
;
349 if (op
!= EXT2_EXTENT_NEXT_SIB
) {
350 #ifdef DEBUG_GET_EXTENT
351 printf("<<<< OP = %s\n",
352 (op
== EXT2_EXTENT_DOWN
) ? "down" :
353 ((op
== EXT2_EXTENT_UP
) ? "up" : "unknown"));
358 if ((orig_op
== EXT2_EXTENT_PREV
) ||
359 (orig_op
== EXT2_EXTENT_PREV_LEAF
)) {
360 if (handle
->level
< handle
->max_depth
) {
362 if (path
->visit_num
> 0 ) {
363 /* path->visit_num = 0; */
364 op
= EXT2_EXTENT_DOWN_AND_LAST
;
365 } else if (path
->left
< path
->entries
-1)
366 op
= EXT2_EXTENT_PREV_SIB
;
367 else if (handle
->level
> 0)
370 return EXT2_ET_EXTENT_NO_PREV
;
373 if (path
->left
< path
->entries
-1)
374 op
= EXT2_EXTENT_PREV_SIB
;
375 else if (handle
->level
> 0)
378 return EXT2_ET_EXTENT_NO_PREV
;
380 if (op
!= EXT2_EXTENT_PREV_SIB
) {
381 #ifdef DEBUG_GET_EXTENT
382 printf("<<<< OP = %s\n",
383 (op
== EXT2_EXTENT_DOWN_AND_LAST
) ? "down/last" :
384 ((op
== EXT2_EXTENT_UP
) ? "up" : "unknown"));
389 if (orig_op
== EXT2_EXTENT_LAST_LEAF
) {
390 if ((handle
->level
< handle
->max_depth
) &&
392 op
= EXT2_EXTENT_DOWN
;
394 op
= EXT2_EXTENT_LAST_SIB
;
395 #ifdef DEBUG_GET_EXTENT
396 printf("<<<< OP = %s\n",
397 (op
== EXT2_EXTENT_DOWN
) ? "down" : "last_sib");
402 case EXT2_EXTENT_CURRENT
:
405 case EXT2_EXTENT_ROOT
:
407 path
= handle
->path
+ handle
->level
;
409 case EXT2_EXTENT_FIRST_SIB
:
410 path
->left
= path
->entries
;
413 case EXT2_EXTENT_NEXT_SIB
:
415 return EXT2_ET_EXTENT_NO_NEXT
;
420 eh
= (struct ext3_extent_header
*) path
->buf
;
421 ix
= EXT_FIRST_INDEX(eh
);
427 case EXT2_EXTENT_PREV_SIB
:
429 path
->left
+1 >= path
->entries
)
430 return EXT2_ET_EXTENT_NO_PREV
;
435 if (handle
->level
< handle
->max_depth
)
438 case EXT2_EXTENT_LAST_SIB
:
439 eh
= (struct ext3_extent_header
*) path
->buf
;
440 path
->curr
= EXT_LAST_EXTENT(eh
);
446 if (handle
->level
<= 0)
447 return EXT2_ET_EXTENT_NO_UP
;
451 if ((orig_op
== EXT2_EXTENT_PREV
) ||
452 (orig_op
== EXT2_EXTENT_PREV_LEAF
))
455 case EXT2_EXTENT_DOWN
:
456 case EXT2_EXTENT_DOWN_AND_LAST
:
457 if (!path
->curr
||(handle
->level
>= handle
->max_depth
))
458 return EXT2_ET_EXTENT_NO_DOWN
;
463 retval
= ext2fs_get_mem(handle
->fs
->blocksize
,
468 blk
= ext2fs_le32_to_cpu(ix
->ei_leaf
) +
469 ((__u64
) ext2fs_le16_to_cpu(ix
->ei_leaf_hi
) << 32);
470 if ((handle
->fs
->flags
& EXT2_FLAG_IMAGE_FILE
) &&
471 (handle
->fs
->io
!= handle
->fs
->image_io
))
472 memset(newpath
->buf
, 0, handle
->fs
->blocksize
);
474 retval
= io_channel_read_blk64(handle
->fs
->io
,
475 blk
, 1, newpath
->buf
);
481 eh
= (struct ext3_extent_header
*) newpath
->buf
;
483 retval
= ext2fs_extent_header_verify(eh
, handle
->fs
->blocksize
);
489 if (!(handle
->fs
->flags
& EXT2_FLAG_IGNORE_CSUM_ERRORS
) &&
490 !ext2fs_extent_block_csum_verify(handle
->fs
, handle
->ino
,
494 newpath
->left
= newpath
->entries
=
495 ext2fs_le16_to_cpu(eh
->eh_entries
);
496 newpath
->max_entries
= ext2fs_le16_to_cpu(eh
->eh_max
);
498 if (path
->left
> 0) {
500 newpath
->end_blk
= ext2fs_le32_to_cpu(ix
->ei_block
);
502 newpath
->end_blk
= path
->end_blk
;
505 if (op
== EXT2_EXTENT_DOWN
) {
506 ix
= EXT_FIRST_INDEX((struct ext3_extent_header
*) eh
);
508 path
->left
= path
->entries
- 1;
511 ix
= EXT_LAST_INDEX((struct ext3_extent_header
*) eh
);
514 if (handle
->level
< handle
->max_depth
)
517 #ifdef DEBUG_GET_EXTENT
518 printf("Down to level %d/%d, end_blk=%llu\n",
519 handle
->level
, handle
->max_depth
,
524 return EXT2_ET_OP_NOT_SUPPORTED
;
528 return EXT2_ET_NO_CURRENT_NODE
;
531 #ifdef DEBUG_GET_EXTENT
532 printf("(Left %d)\n", path
->left
);
535 if (handle
->level
== handle
->max_depth
) {
536 ex
= (struct ext3_extent
*) ix
;
538 extent
->e_pblk
= ext2fs_le32_to_cpu(ex
->ee_start
) +
539 ((__u64
) ext2fs_le16_to_cpu(ex
->ee_start_hi
) << 32);
540 extent
->e_lblk
= ext2fs_le32_to_cpu(ex
->ee_block
);
541 extent
->e_len
= ext2fs_le16_to_cpu(ex
->ee_len
);
542 extent
->e_flags
|= EXT2_EXTENT_FLAGS_LEAF
;
543 if (extent
->e_len
> EXT_INIT_MAX_LEN
) {
544 extent
->e_len
-= EXT_INIT_MAX_LEN
;
545 extent
->e_flags
|= EXT2_EXTENT_FLAGS_UNINIT
;
548 extent
->e_pblk
= ext2fs_le32_to_cpu(ix
->ei_leaf
) +
549 ((__u64
) ext2fs_le16_to_cpu(ix
->ei_leaf_hi
) << 32);
550 extent
->e_lblk
= ext2fs_le32_to_cpu(ix
->ei_block
);
551 if (path
->left
> 0) {
553 end_blk
= ext2fs_le32_to_cpu(ix
->ei_block
);
555 end_blk
= path
->end_blk
;
557 extent
->e_len
= end_blk
- extent
->e_lblk
;
560 extent
->e_flags
|= EXT2_EXTENT_FLAGS_SECOND_VISIT
;
562 if (((orig_op
== EXT2_EXTENT_NEXT_LEAF
) ||
563 (orig_op
== EXT2_EXTENT_PREV_LEAF
)) &&
564 (handle
->level
!= handle
->max_depth
))
567 if ((orig_op
== EXT2_EXTENT_LAST_LEAF
) &&
568 ((handle
->level
!= handle
->max_depth
) ||
573 return EXT2_ET_EXTENT_CSUM_INVALID
;
578 static errcode_t
update_path(ext2_extent_handle_t handle
)
582 struct ext3_extent_idx
*ix
;
583 struct ext3_extent_header
*eh
;
585 if (handle
->level
== 0) {
586 retval
= ext2fs_write_inode(handle
->fs
, handle
->ino
,
589 ix
= handle
->path
[handle
->level
- 1].curr
;
590 blk
= ext2fs_le32_to_cpu(ix
->ei_leaf
) +
591 ((__u64
) ext2fs_le16_to_cpu(ix
->ei_leaf_hi
) << 32);
593 /* then update the checksum */
594 eh
= (struct ext3_extent_header
*)
595 handle
->path
[handle
->level
].buf
;
596 retval
= ext2fs_extent_block_csum_set(handle
->fs
, handle
->ino
,
601 retval
= io_channel_write_blk64(handle
->fs
->io
,
602 blk
, 1, handle
->path
[handle
->level
].buf
);
608 errcode_t
ext2fs_extent_save_path(ext2_extent_handle_t handle
,
609 ext2_extent_path_t
*ret_path
)
611 ext2_extent_path_t save_path
;
612 struct ext2fs_extent extent
;
613 struct ext2_extent_info info
;
616 retval
= ext2fs_extent_get(handle
, EXT2_EXTENT_CURRENT
, &extent
);
620 retval
= ext2fs_extent_get_info(handle
, &info
);
624 retval
= ext2fs_get_mem(sizeof(struct ext2_extent_path
), &save_path
);
627 memset(save_path
, 0, sizeof(struct ext2_extent_path
));
629 save_path
->magic
= EXT2_ET_MAGIC_EXTENT_PATH
;
630 save_path
->leaf_height
= info
.max_depth
- info
.curr_level
- 1;
631 save_path
->lblk
= extent
.e_lblk
;
633 *ret_path
= save_path
;
637 errcode_t
ext2fs_extent_free_path(ext2_extent_path_t path
)
639 EXT2_CHECK_MAGIC(path
, EXT2_ET_MAGIC_EXTENT_PATH
);
641 ext2fs_free_mem(&path
);
647 * Go to the node at leaf_level which contains logical block blk.
649 * leaf_level is height from the leaf node level, i.e.
650 * leaf_level 0 is at leaf node, leaf_level 1 is 1 above etc.
652 * If "blk" has no mapping (hole) then handle is left at last
655 errcode_t
ext2fs_extent_goto2(ext2_extent_handle_t handle
,
656 int leaf_level
, blk64_t blk
)
658 struct ext2fs_extent extent
;
661 retval
= ext2fs_extent_get(handle
, EXT2_EXTENT_ROOT
, &extent
);
663 if (retval
== EXT2_ET_EXTENT_NO_NEXT
)
664 retval
= EXT2_ET_EXTENT_NOT_FOUND
;
668 if (leaf_level
> handle
->max_depth
) {
670 printf("leaf level %d greater than tree depth %d\n",
671 leaf_level
, handle
->max_depth
);
673 return EXT2_ET_OP_NOT_SUPPORTED
;
677 printf("goto extent ino %u, level %d, %llu\n", handle
->ino
,
681 #ifdef DEBUG_GOTO_EXTENTS
682 dbg_print_extent("root", &extent
);
685 if (handle
->max_depth
- handle
->level
== leaf_level
) {
686 /* block is in this &extent */
687 if ((blk
>= extent
.e_lblk
) &&
688 (blk
< extent
.e_lblk
+ extent
.e_len
))
690 if (blk
< extent
.e_lblk
) {
691 retval
= ext2fs_extent_get(handle
,
692 EXT2_EXTENT_PREV_SIB
,
694 return EXT2_ET_EXTENT_NOT_FOUND
;
696 retval
= ext2fs_extent_get(handle
,
697 EXT2_EXTENT_NEXT_SIB
,
699 if (retval
== EXT2_ET_EXTENT_NO_NEXT
)
700 return EXT2_ET_EXTENT_NOT_FOUND
;
706 retval
= ext2fs_extent_get(handle
, EXT2_EXTENT_NEXT_SIB
,
708 if (retval
== EXT2_ET_EXTENT_NO_NEXT
)
713 #ifdef DEBUG_GOTO_EXTENTS
714 dbg_print_extent("next", &extent
);
716 if (blk
== extent
.e_lblk
)
718 if (blk
> extent
.e_lblk
)
721 retval
= ext2fs_extent_get(handle
, EXT2_EXTENT_PREV_SIB
,
726 #ifdef DEBUG_GOTO_EXTENTS
727 dbg_print_extent("prev", &extent
);
731 retval
= ext2fs_extent_get(handle
, EXT2_EXTENT_DOWN
,
736 #ifdef DEBUG_GOTO_EXTENTS
737 dbg_print_extent("down", &extent
);
742 errcode_t
ext2fs_extent_goto(ext2_extent_handle_t handle
,
745 return ext2fs_extent_goto2(handle
, 0, blk
);
749 * Traverse back up to root fixing parents of current node as needed.
751 * If we changed start of first entry in a node, fix parent index start
754 * Safe to call for any position in node; if not at the first entry,
755 * it will simply return.
757 * Note a subtlety of this function -- if there happen to be two extents
758 * mapping the same lblk and someone calls fix_parents on the second of the two
759 * extents, the position of the extent handle after the call will be the second
760 * extent if nothing happened, or the first extent if something did. A caller
761 * in this situation must use ext2fs_extent_goto() after calling this function.
762 * Or simply don't map the same lblk with two extents, ever.
764 errcode_t
ext2fs_extent_fix_parents(ext2_extent_handle_t handle
)
769 struct extent_path
*path
;
770 struct ext2fs_extent extent
;
771 struct ext2_extent_info info
;
773 EXT2_CHECK_MAGIC(handle
, EXT2_ET_MAGIC_EXTENT_HANDLE
);
775 if (!(handle
->fs
->flags
& EXT2_FLAG_RW
))
776 return EXT2_ET_RO_FILSYS
;
779 return EXT2_ET_NO_CURRENT_NODE
;
781 path
= handle
->path
+ handle
->level
;
783 return EXT2_ET_NO_CURRENT_NODE
;
785 retval
= ext2fs_extent_get(handle
, EXT2_EXTENT_CURRENT
, &extent
);
789 /* modified node's start block */
790 start
= extent
.e_lblk
;
792 if ((retval
= ext2fs_extent_get_info(handle
, &info
)))
794 orig_height
= info
.max_depth
- info
.curr_level
;
796 /* traverse up until index not first, or startblk matches, or top */
797 while (handle
->level
> 0 &&
798 (path
->left
== path
->entries
- 1)) {
799 retval
= ext2fs_extent_get(handle
, EXT2_EXTENT_UP
, &extent
);
802 if (extent
.e_lblk
== start
)
804 path
= handle
->path
+ handle
->level
;
805 extent
.e_len
+= (extent
.e_lblk
- start
);
806 extent
.e_lblk
= start
;
807 retval
= ext2fs_extent_replace(handle
, 0, &extent
);
813 /* put handle back to where we started */
814 retval
= ext2fs_extent_goto2(handle
, orig_height
, start
);
819 errcode_t
ext2fs_extent_replace(ext2_extent_handle_t handle
,
820 int flags
EXT2FS_ATTR((unused
)),
821 struct ext2fs_extent
*extent
)
823 struct extent_path
*path
;
824 struct ext3_extent_idx
*ix
;
825 struct ext3_extent
*ex
;
827 EXT2_CHECK_MAGIC(handle
, EXT2_ET_MAGIC_EXTENT_HANDLE
);
829 if (!(handle
->fs
->flags
& EXT2_FLAG_RW
))
830 return EXT2_ET_RO_FILSYS
;
833 return EXT2_ET_NO_CURRENT_NODE
;
835 path
= handle
->path
+ handle
->level
;
837 return EXT2_ET_NO_CURRENT_NODE
;
840 printf("extent replace: %u ", handle
->ino
);
841 dbg_print_extent(0, extent
);
844 if (handle
->level
== handle
->max_depth
) {
847 ex
->ee_block
= ext2fs_cpu_to_le32(extent
->e_lblk
);
848 ex
->ee_start
= ext2fs_cpu_to_le32(extent
->e_pblk
& 0xFFFFFFFF);
849 ex
->ee_start_hi
= ext2fs_cpu_to_le16(extent
->e_pblk
>> 32);
850 if (extent
->e_flags
& EXT2_EXTENT_FLAGS_UNINIT
) {
851 if (extent
->e_len
> EXT_UNINIT_MAX_LEN
)
852 return EXT2_ET_EXTENT_INVALID_LENGTH
;
853 ex
->ee_len
= ext2fs_cpu_to_le16(extent
->e_len
+
856 if (extent
->e_len
> EXT_INIT_MAX_LEN
)
857 return EXT2_ET_EXTENT_INVALID_LENGTH
;
858 ex
->ee_len
= ext2fs_cpu_to_le16(extent
->e_len
);
863 ix
->ei_leaf
= ext2fs_cpu_to_le32(extent
->e_pblk
& 0xFFFFFFFF);
864 ix
->ei_leaf_hi
= ext2fs_cpu_to_le16(extent
->e_pblk
>> 32);
865 ix
->ei_block
= ext2fs_cpu_to_le32(extent
->e_lblk
);
872 static int splitting_at_eof(struct ext2_extent_handle
*handle
,
873 struct extent_path
*path
)
875 struct extent_path
*ppp
= path
;
876 dump_path(__func__
, handle
, path
);
878 if (handle
->level
== 0)
885 } while (ppp
>= handle
->path
);
891 * allocate a new block, move half the current node to it, and update parent
893 * handle will be left pointing at original record.
895 static errcode_t
extent_node_split(ext2_extent_handle_t handle
,
898 errcode_t retval
= 0;
899 blk64_t new_node_pblk
;
900 blk64_t new_node_start
;
902 blk64_t goal_blk
= 0;
904 char *block_buf
= NULL
;
905 struct ext2fs_extent extent
;
906 struct extent_path
*path
, *newpath
= 0;
907 struct ext3_extent_header
*eh
, *neweh
;
910 struct ext2_extent_info info
;
914 EXT2_CHECK_MAGIC(handle
, EXT2_ET_MAGIC_EXTENT_HANDLE
);
916 if (!(handle
->fs
->flags
& EXT2_FLAG_RW
))
917 return EXT2_ET_RO_FILSYS
;
920 return EXT2_ET_NO_CURRENT_NODE
;
923 printf("splitting node at level %d\n", handle
->level
);
925 retval
= ext2fs_extent_get(handle
, EXT2_EXTENT_CURRENT
, &extent
);
929 retval
= ext2fs_extent_get_info(handle
, &info
);
933 /* save the position we were originally splitting... */
934 orig_height
= info
.max_depth
- info
.curr_level
;
935 orig_lblk
= extent
.e_lblk
;
937 /* Try to put the index block before the first extent */
938 path
= handle
->path
+ handle
->level
;
939 eh
= (struct ext3_extent_header
*) path
->buf
;
940 if (handle
->level
== handle
->max_depth
) {
941 struct ext3_extent
*ex
;
943 ex
= EXT_FIRST_EXTENT(eh
);
944 goal_blk
= ext2fs_le32_to_cpu(ex
->ee_start
) +
945 ((__u64
) ext2fs_le16_to_cpu(ex
->ee_start_hi
) << 32);
947 struct ext3_extent_idx
*ix
;
949 ix
= EXT_FIRST_INDEX(eh
);
950 goal_blk
= ext2fs_le32_to_cpu(ix
->ei_leaf
) +
951 ((__u64
) ext2fs_le16_to_cpu(ix
->ei_leaf_hi
) << 32);
953 goal_blk
-= EXT2FS_CLUSTER_RATIO(handle
->fs
);
954 goal_blk
&= ~EXT2FS_CLUSTER_MASK(handle
->fs
);
956 /* Is there room in the parent for a new entry? */
958 (handle
->path
[handle
->level
- 1].entries
>=
959 handle
->path
[handle
->level
- 1].max_entries
)) {
962 printf("parent level %d full; splitting it too\n",
965 /* split the parent */
966 retval
= ext2fs_extent_get(handle
, EXT2_EXTENT_UP
, &extent
);
970 retval
= extent_node_split(handle
, expand_allowed
);
974 /* get handle back to our original split position */
975 retval
= ext2fs_extent_goto2(handle
, orig_height
, orig_lblk
);
980 /* At this point, parent should have room for this split */
981 path
= handle
->path
+ handle
->level
;
983 return EXT2_ET_NO_CURRENT_NODE
;
986 * Normally, we try to split a full node in half. This doesn't turn
987 * out so well if we're tacking extents on the end of the file because
988 * then we're stuck with a tree of half-full extent blocks. This of
989 * course doesn't apply to the root level.
991 no_balance
= expand_allowed
? splitting_at_eof(handle
, path
) : 0;
993 /* extent header of the current node we'll split */
994 eh
= (struct ext3_extent_header
*)path
->buf
;
996 /* splitting root level means moving them all out */
997 if (handle
->level
== 0) {
999 tocopy
= ext2fs_le16_to_cpu(eh
->eh_entries
);
1000 retval
= ext2fs_get_memzero((handle
->max_paths
+ 1) *
1001 sizeof(struct extent_path
),
1009 tocopy
= ext2fs_le16_to_cpu(eh
->eh_entries
) / 2;
1013 printf("will copy out %d of %d entries at level %d\n",
1014 tocopy
, ext2fs_le16_to_cpu(eh
->eh_entries
),
1018 if (!tocopy
&& !no_balance
) {
1020 printf("Nothing to copy to new block!\n");
1022 retval
= EXT2_ET_CANT_SPLIT_EXTENT
;
1026 /* first we need a new block, or can do nothing. */
1027 block_buf
= malloc(handle
->fs
->blocksize
);
1034 goal_blk
= ext2fs_find_inode_goal(handle
->fs
, handle
->ino
,
1036 retval
= ext2fs_alloc_block2(handle
->fs
, goal_blk
, block_buf
,
1042 printf("will copy to new node at block %lu\n",
1043 (unsigned long) new_node_pblk
);
1046 /* Copy data into new block buffer */
1047 /* First the header for the new block... */
1048 neweh
= (struct ext3_extent_header
*) block_buf
;
1049 memcpy(neweh
, eh
, sizeof(struct ext3_extent_header
));
1050 neweh
->eh_entries
= ext2fs_cpu_to_le16(tocopy
);
1051 neweh
->eh_max
= ext2fs_cpu_to_le16((handle
->fs
->blocksize
-
1052 sizeof(struct ext3_extent_header
)) /
1053 sizeof(struct ext3_extent
));
1055 /* then the entries for the new block... */
1056 memcpy(EXT_FIRST_INDEX(neweh
),
1057 EXT_FIRST_INDEX(eh
) +
1058 (ext2fs_le16_to_cpu(eh
->eh_entries
) - tocopy
),
1059 sizeof(struct ext3_extent_idx
) * tocopy
);
1061 new_node_start
= ext2fs_le32_to_cpu(EXT_FIRST_INDEX(neweh
)->ei_block
);
1063 /* then update the checksum */
1064 retval
= ext2fs_extent_block_csum_set(handle
->fs
, handle
->ino
, neweh
);
1068 /* ...and write the new node block out to disk. */
1069 retval
= io_channel_write_blk64(handle
->fs
->io
, new_node_pblk
, 1,
1075 /* OK! we've created the new node; now adjust the tree */
1077 /* current path now has fewer active entries, we copied some out */
1078 if (handle
->level
== 0) {
1079 memcpy(newpath
, path
,
1080 sizeof(struct extent_path
) * handle
->max_paths
);
1081 handle
->path
= newpath
;
1083 path
= handle
->path
;
1085 path
->left
= path
->max_entries
- 1;
1086 handle
->max_depth
++;
1087 handle
->max_paths
++;
1088 eh
->eh_depth
= ext2fs_cpu_to_le16(handle
->max_depth
);
1090 path
->entries
-= tocopy
;
1091 path
->left
-= tocopy
;
1094 eh
->eh_entries
= ext2fs_cpu_to_le16(path
->entries
);
1095 /* this writes out the node, incl. the modified header */
1096 retval
= update_path(handle
);
1100 /* now go up and insert/replace index for new node we created */
1102 retval
= ext2fs_extent_get(handle
, EXT2_EXTENT_FIRST_SIB
, &extent
);
1106 extent
.e_lblk
= new_node_start
;
1107 extent
.e_pblk
= new_node_pblk
;
1108 extent
.e_len
= handle
->path
[0].end_blk
- extent
.e_lblk
;
1109 retval
= ext2fs_extent_replace(handle
, 0, &extent
);
1113 __u32 new_node_length
;
1115 retval
= ext2fs_extent_get(handle
, EXT2_EXTENT_UP
, &extent
);
1116 /* will insert after this one; it's length is shorter now */
1117 new_node_length
= new_node_start
- extent
.e_lblk
;
1118 extent
.e_len
-= new_node_length
;
1119 retval
= ext2fs_extent_replace(handle
, 0, &extent
);
1123 /* now set up the new extent and insert it */
1124 extent
.e_lblk
= new_node_start
;
1125 extent
.e_pblk
= new_node_pblk
;
1126 extent
.e_len
= new_node_length
;
1127 retval
= ext2fs_extent_insert(handle
, EXT2_EXTENT_INSERT_AFTER
, &extent
);
1132 /* get handle back to our original position */
1133 retval
= ext2fs_extent_goto2(handle
, orig_height
, orig_lblk
);
1137 /* new node hooked in, so update inode block count (do this here?) */
1138 ext2fs_iblk_add_blocks(handle
->fs
, handle
->inode
, 1);
1139 retval
= ext2fs_write_inode(handle
->fs
, handle
->ino
,
1146 ext2fs_free_mem(&newpath
);
1152 errcode_t
ext2fs_extent_node_split(ext2_extent_handle_t handle
)
1154 return extent_node_split(handle
, 0);
1157 errcode_t
ext2fs_extent_insert(ext2_extent_handle_t handle
, int flags
,
1158 struct ext2fs_extent
*extent
)
1160 struct extent_path
*path
;
1161 struct ext3_extent_idx
*ix
;
1162 struct ext3_extent_header
*eh
;
1165 EXT2_CHECK_MAGIC(handle
, EXT2_ET_MAGIC_EXTENT_HANDLE
);
1167 if (!(handle
->fs
->flags
& EXT2_FLAG_RW
))
1168 return EXT2_ET_RO_FILSYS
;
1171 return EXT2_ET_NO_CURRENT_NODE
;
1174 printf("extent insert: %u ", handle
->ino
);
1175 dbg_print_extent(0, extent
);
1178 path
= handle
->path
+ handle
->level
;
1180 if (path
->entries
>= path
->max_entries
) {
1181 if (flags
& EXT2_EXTENT_INSERT_NOSPLIT
) {
1182 return EXT2_ET_CANT_INSERT_EXTENT
;
1185 printf("node full (level %d) - splitting\n",
1188 retval
= extent_node_split(handle
, 1);
1191 path
= handle
->path
+ handle
->level
;
1195 eh
= (struct ext3_extent_header
*) path
->buf
;
1198 if (flags
& EXT2_EXTENT_INSERT_AFTER
) {
1203 ix
= EXT_FIRST_INDEX(eh
);
1209 if (path
->left
>= 0)
1211 (path
->left
+1) * sizeof(struct ext3_extent_idx
));
1215 eh
= (struct ext3_extent_header
*) path
->buf
;
1216 eh
->eh_entries
= ext2fs_cpu_to_le16(path
->entries
);
1218 retval
= ext2fs_extent_replace(handle
, 0, extent
);
1222 retval
= update_path(handle
);
1229 ext2fs_extent_delete(handle
, 0);
1234 * Sets the physical block for a logical file block in the extent tree.
1236 * May: map unmapped, unmap mapped, or remap mapped blocks.
1238 * Mapping an unmapped block adds a single-block extent.
1240 * Unmapping first or last block modifies extent in-place
1241 * - But may need to fix parent's starts too in first-block case
1243 * Mapping any unmapped block requires adding a (single-block) extent
1244 * and inserting into proper point in tree.
1246 * Modifying (unmapping or remapping) a block in the middle
1247 * of an extent requires splitting the extent.
1248 * - Remapping case requires new single-block extent.
1250 * Remapping first or last block adds an extent.
1252 * We really need extent adding to be smart about merging.
1255 errcode_t
ext2fs_extent_set_bmap(ext2_extent_handle_t handle
,
1256 blk64_t logical
, blk64_t physical
, int flags
)
1258 errcode_t ec
, retval
= 0;
1259 int mapped
= 1; /* logical is mapped? */
1261 int extent_uninit
= 0;
1262 int prev_uninit
= 0;
1263 int next_uninit
= 0;
1265 int max_len
= EXT_INIT_MAX_LEN
;
1266 int has_prev
, has_next
;
1268 struct extent_path
*path
;
1269 struct ext2fs_extent extent
, next_extent
, prev_extent
;
1270 struct ext2fs_extent newextent
;
1271 struct ext2_extent_info info
;
1273 EXT2_CHECK_MAGIC(handle
, EXT2_ET_MAGIC_EXTENT_HANDLE
);
1276 printf("set_bmap ino %u log %lld phys %lld flags %d\n",
1277 handle
->ino
, logical
, physical
, flags
);
1280 if (!(handle
->fs
->flags
& EXT2_FLAG_RW
))
1281 return EXT2_ET_RO_FILSYS
;
1284 return EXT2_ET_NO_CURRENT_NODE
;
1286 path
= handle
->path
+ handle
->level
;
1288 if (flags
& EXT2_EXTENT_SET_BMAP_UNINIT
) {
1290 max_len
= EXT_UNINIT_MAX_LEN
;
1293 /* if (re)mapping, set up new extent to insert */
1295 newextent
.e_len
= 1;
1296 newextent
.e_pblk
= physical
;
1297 newextent
.e_lblk
= logical
;
1298 newextent
.e_flags
= EXT2_EXTENT_FLAGS_LEAF
;
1300 newextent
.e_flags
|= EXT2_EXTENT_FLAGS_UNINIT
;
1303 /* special case if the extent tree is completely empty */
1304 if ((handle
->max_depth
== 0) && (path
->entries
== 0)) {
1305 retval
= ext2fs_extent_insert(handle
, 0, &newextent
);
1309 /* save our original location in the extent tree */
1310 if ((retval
= ext2fs_extent_get(handle
, EXT2_EXTENT_CURRENT
,
1312 if (retval
!= EXT2_ET_NO_CURRENT_NODE
)
1314 memset(&extent
, 0, sizeof(extent
));
1316 if ((retval
= ext2fs_extent_get_info(handle
, &info
)))
1318 orig_height
= info
.max_depth
- info
.curr_level
;
1319 orig_lblk
= extent
.e_lblk
;
1321 /* go to the logical spot we want to (re/un)map */
1322 retval
= ext2fs_extent_goto(handle
, logical
);
1324 if (retval
== EXT2_ET_EXTENT_NOT_FOUND
) {
1329 printf("block %llu already unmapped\n",
1339 * This may be the extent *before* the requested logical,
1340 * if it's currently unmapped.
1342 * Get the previous and next leaf extents, if they are present.
1344 retval
= ext2fs_extent_get(handle
, EXT2_EXTENT_CURRENT
, &extent
);
1347 if (extent
.e_flags
& EXT2_EXTENT_FLAGS_UNINIT
)
1349 retval
= ext2fs_extent_get(handle
, EXT2_EXTENT_NEXT_LEAF
, &next_extent
);
1352 if (retval
!= EXT2_ET_EXTENT_NO_NEXT
)
1355 dbg_print_extent("set_bmap: next_extent",
1358 if (next_extent
.e_flags
& EXT2_EXTENT_FLAGS_UNINIT
)
1361 retval
= ext2fs_extent_goto(handle
, logical
);
1362 if (retval
&& retval
!= EXT2_ET_EXTENT_NOT_FOUND
)
1364 retval
= ext2fs_extent_get(handle
, EXT2_EXTENT_PREV_LEAF
, &prev_extent
);
1367 if (retval
!= EXT2_ET_EXTENT_NO_PREV
)
1371 dbg_print_extent("set_bmap: prev_extent",
1373 if (prev_extent
.e_flags
& EXT2_EXTENT_FLAGS_UNINIT
)
1376 retval
= ext2fs_extent_goto(handle
, logical
);
1377 if (retval
&& retval
!= EXT2_ET_EXTENT_NOT_FOUND
)
1380 /* check if already pointing to the requested physical */
1381 if (mapped
&& (new_uninit
== extent_uninit
) &&
1382 (extent
.e_pblk
+ (logical
- extent
.e_lblk
) == physical
)) {
1384 printf("physical block (at %llu) unchanged\n", logical
);
1391 printf("mapping unmapped logical block %llu\n", logical
);
1393 if ((logical
== extent
.e_lblk
+ extent
.e_len
) &&
1394 (physical
== extent
.e_pblk
+ extent
.e_len
) &&
1395 (new_uninit
== extent_uninit
) &&
1396 ((int) extent
.e_len
< max_len
-1)) {
1398 retval
= ext2fs_extent_replace(handle
, 0, &extent
);
1399 } else if ((logical
== extent
.e_lblk
- 1) &&
1400 (physical
== extent
.e_pblk
- 1) &&
1401 (new_uninit
== extent_uninit
) &&
1402 ((int) extent
.e_len
< max_len
- 1)) {
1406 retval
= ext2fs_extent_replace(handle
, 0, &extent
);
1407 } else if (has_next
&&
1408 (logical
== next_extent
.e_lblk
- 1) &&
1409 (physical
== next_extent
.e_pblk
- 1) &&
1410 (new_uninit
== next_uninit
) &&
1411 ((int) next_extent
.e_len
< max_len
- 1)) {
1412 retval
= ext2fs_extent_get(handle
,
1413 EXT2_EXTENT_NEXT_LEAF
,
1417 next_extent
.e_len
++;
1418 next_extent
.e_lblk
--;
1419 next_extent
.e_pblk
--;
1420 retval
= ext2fs_extent_replace(handle
, 0, &next_extent
);
1421 } else if (logical
< extent
.e_lblk
)
1422 retval
= ext2fs_extent_insert(handle
, 0, &newextent
);
1424 retval
= ext2fs_extent_insert(handle
,
1425 EXT2_EXTENT_INSERT_AFTER
, &newextent
);
1428 retval
= ext2fs_extent_fix_parents(handle
);
1431 } else if ((logical
== extent
.e_lblk
) && (extent
.e_len
== 1)) {
1433 printf("(re/un)mapping only block in extent\n");
1436 retval
= ext2fs_extent_replace(handle
, 0, &newextent
);
1438 retval
= ext2fs_extent_delete(handle
, 0);
1441 ec
= ext2fs_extent_fix_parents(handle
);
1442 if (ec
!= EXT2_ET_NO_CURRENT_NODE
)
1448 } else if (logical
== extent
.e_lblk
+ extent
.e_len
- 1) {
1450 printf("(re/un)mapping last block in extent\n");
1454 (logical
== (next_extent
.e_lblk
- 1)) &&
1455 (physical
== (next_extent
.e_pblk
- 1)) &&
1456 (new_uninit
== next_uninit
) &&
1457 ((int) next_extent
.e_len
< max_len
- 1)) {
1458 retval
= ext2fs_extent_get(handle
,
1459 EXT2_EXTENT_NEXT_LEAF
, &next_extent
);
1462 next_extent
.e_len
++;
1463 next_extent
.e_lblk
--;
1464 next_extent
.e_pblk
--;
1465 retval
= ext2fs_extent_replace(handle
, 0,
1470 retval
= ext2fs_extent_insert(handle
,
1471 EXT2_EXTENT_INSERT_AFTER
, &newextent
);
1474 retval
= ext2fs_extent_fix_parents(handle
);
1478 * Now pointing at inserted extent; move back to prev.
1480 * We cannot use EXT2_EXTENT_PREV to go back; note the
1481 * subtlety in the comment for fix_parents().
1483 retval
= ext2fs_extent_goto(handle
, logical
);
1486 retval
= ext2fs_extent_get(handle
,
1487 EXT2_EXTENT_CURRENT
,
1493 retval
= ext2fs_extent_replace(handle
, 0, &extent
);
1496 } else if (logical
== extent
.e_lblk
) {
1498 printf("(re/un)mapping first block in extent\n");
1502 (logical
== (prev_extent
.e_lblk
+
1503 prev_extent
.e_len
)) &&
1504 (physical
== (prev_extent
.e_pblk
+
1505 prev_extent
.e_len
)) &&
1506 (new_uninit
== prev_uninit
) &&
1507 ((int) prev_extent
.e_len
< max_len
-1)) {
1508 retval
= ext2fs_extent_get(handle
,
1509 EXT2_EXTENT_PREV_LEAF
, &prev_extent
);
1512 prev_extent
.e_len
++;
1513 retval
= ext2fs_extent_replace(handle
, 0,
1516 retval
= ext2fs_extent_insert(handle
,
1520 retval
= ext2fs_extent_fix_parents(handle
);
1523 retval
= ext2fs_extent_get(handle
,
1524 EXT2_EXTENT_NEXT_LEAF
,
1532 retval
= ext2fs_extent_replace(handle
, 0, &extent
);
1535 retval
= ext2fs_extent_fix_parents(handle
);
1541 struct ext2fs_extent save_extent
;
1545 printf("(re/un)mapping in middle of extent\n");
1547 /* need to split this extent; later */
1548 save_lblk
= extent
.e_lblk
;
1549 save_length
= extent
.e_len
;
1550 save_extent
= extent
;
1552 /* shorten pre-split extent */
1553 extent
.e_len
= (logical
- extent
.e_lblk
);
1554 retval
= ext2fs_extent_replace(handle
, 0, &extent
);
1557 /* insert our new extent, if any */
1559 /* insert new extent after current */
1560 retval
= ext2fs_extent_insert(handle
,
1561 EXT2_EXTENT_INSERT_AFTER
, &newextent
);
1563 r2
= ext2fs_extent_goto(handle
, save_lblk
);
1565 (void)ext2fs_extent_replace(handle
, 0,
1570 /* add post-split extent */
1571 extent
.e_pblk
+= extent
.e_len
+ 1;
1572 extent
.e_lblk
+= extent
.e_len
+ 1;
1573 extent
.e_len
= save_length
- extent
.e_len
- 1;
1574 retval
= ext2fs_extent_insert(handle
,
1575 EXT2_EXTENT_INSERT_AFTER
, &extent
);
1578 r2
= ext2fs_extent_goto(handle
,
1581 (void)ext2fs_extent_delete(handle
, 0);
1583 r2
= ext2fs_extent_goto(handle
, save_lblk
);
1585 (void)ext2fs_extent_replace(handle
, 0,
1592 /* get handle back to its position */
1593 if (orig_height
> handle
->max_depth
)
1594 orig_height
= handle
->max_depth
; /* In case we shortened the tree */
1595 ext2fs_extent_goto2(handle
, orig_height
, orig_lblk
);
1599 errcode_t
ext2fs_extent_delete(ext2_extent_handle_t handle
, int flags
)
1601 struct extent_path
*path
;
1603 struct ext3_extent_header
*eh
;
1604 errcode_t retval
= 0;
1606 EXT2_CHECK_MAGIC(handle
, EXT2_ET_MAGIC_EXTENT_HANDLE
);
1608 if (!(handle
->fs
->flags
& EXT2_FLAG_RW
))
1609 return EXT2_ET_RO_FILSYS
;
1612 return EXT2_ET_NO_CURRENT_NODE
;
1616 struct ext2fs_extent extent
;
1618 retval
= ext2fs_extent_get(handle
, EXT2_EXTENT_CURRENT
,
1621 printf("extent delete %u ", handle
->ino
);
1622 dbg_print_extent(0, &extent
);
1627 path
= handle
->path
+ handle
->level
;
1629 return EXT2_ET_NO_CURRENT_NODE
;
1634 memmove(cp
, cp
+ sizeof(struct ext3_extent_idx
),
1635 path
->left
* sizeof(struct ext3_extent_idx
));
1638 struct ext3_extent_idx
*ix
= path
->curr
;
1642 if (--path
->entries
== 0)
1645 /* if non-root node has no entries left, remove it & parent ptr to it */
1646 if (path
->entries
== 0 && handle
->level
) {
1647 if (!(flags
& EXT2_EXTENT_DELETE_KEEP_EMPTY
)) {
1648 struct ext2fs_extent extent
;
1650 retval
= ext2fs_extent_get(handle
, EXT2_EXTENT_UP
,
1655 retval
= ext2fs_extent_delete(handle
, flags
);
1656 handle
->inode
->i_blocks
-=
1657 (handle
->fs
->blocksize
*
1658 EXT2FS_CLUSTER_RATIO(handle
->fs
)) / 512;
1659 retval
= ext2fs_write_inode(handle
->fs
, handle
->ino
,
1661 ext2fs_block_alloc_stats2(handle
->fs
,
1665 eh
= (struct ext3_extent_header
*) path
->buf
;
1666 eh
->eh_entries
= ext2fs_cpu_to_le16(path
->entries
);
1667 if ((path
->entries
== 0) && (handle
->level
== 0)) {
1669 handle
->max_depth
= 0;
1671 retval
= update_path(handle
);
1676 errcode_t
ext2fs_extent_get_info(ext2_extent_handle_t handle
,
1677 struct ext2_extent_info
*info
)
1679 struct extent_path
*path
;
1681 EXT2_CHECK_MAGIC(handle
, EXT2_ET_MAGIC_EXTENT_HANDLE
);
1683 memset(info
, 0, sizeof(struct ext2_extent_info
));
1685 path
= handle
->path
+ handle
->level
;
1688 info
->curr_entry
= ((char *) path
->curr
- path
->buf
) /
1689 sizeof(struct ext3_extent_idx
);
1691 info
->curr_entry
= 0;
1692 info
->num_entries
= path
->entries
;
1693 info
->max_entries
= path
->max_entries
;
1694 info
->bytes_avail
= (path
->max_entries
- path
->entries
) *
1695 sizeof(struct ext3_extent
);
1698 info
->curr_level
= handle
->level
;
1699 info
->max_depth
= handle
->max_depth
;
1700 info
->max_lblk
= EXT_MAX_EXTENT_LBLK
;
1701 info
->max_pblk
= EXT_MAX_EXTENT_PBLK
;
1702 info
->max_len
= EXT_INIT_MAX_LEN
;
1703 info
->max_uninit_len
= EXT_UNINIT_MAX_LEN
;
1708 static int ul_log2(unsigned long arg
)
1720 size_t ext2fs_max_extent_depth(ext2_extent_handle_t handle
)
1722 size_t iblock_sz
= sizeof(((struct ext2_inode
*)NULL
)->i_block
);
1723 size_t iblock_extents
= (iblock_sz
- sizeof(struct ext3_extent_header
)) /
1724 sizeof(struct ext3_extent
);
1725 size_t extents_per_block
= (handle
->fs
->blocksize
-
1726 sizeof(struct ext3_extent_header
)) /
1727 sizeof(struct ext3_extent
);
1728 static unsigned int last_blocksize
= 0;
1729 static size_t last_result
= 0;
1731 if (last_blocksize
&& last_blocksize
== handle
->fs
->blocksize
)
1734 last_result
= 1 + ((ul_log2(EXT_MAX_EXTENT_LBLK
) - ul_log2(iblock_extents
)) /
1735 ul_log2(extents_per_block
));
1736 last_blocksize
= handle
->fs
->blocksize
;
1740 errcode_t
ext2fs_fix_extents_checksums(ext2_filsys fs
, ext2_ino_t ino
,
1741 struct ext2_inode
*inode
)
1743 ext2_extent_handle_t handle
;
1744 struct ext2fs_extent extent
;
1746 int save_flags
= fs
->flags
;
1748 if (!ext2fs_has_feature_metadata_csum(fs
->super
) ||
1749 (inode
&& !(inode
->i_flags
& EXT4_EXTENTS_FL
)))
1752 errcode
= ext2fs_extent_open2(fs
, ino
, inode
, &handle
);
1754 if (errcode
== EXT2_ET_INODE_NOT_EXTENT
)
1759 fs
->flags
&= ~EXT2_FLAG_IGNORE_CSUM_ERRORS
;
1760 errcode
= ext2fs_extent_get(handle
, EXT2_EXTENT_ROOT
, &extent
);
1765 /* Skip to the end of a block of leaf nodes */
1766 if (extent
.e_flags
& EXT2_EXTENT_FLAGS_LEAF
) {
1767 errcode
= ext2fs_extent_get(handle
,
1768 EXT2_EXTENT_LAST_SIB
,
1774 errcode
= ext2fs_extent_get(handle
, EXT2_EXTENT_NEXT
, &extent
);
1775 if (errcode
== EXT2_ET_EXTENT_CSUM_INVALID
)
1776 errcode
= update_path(handle
);
1777 } while (errcode
== 0);
1780 /* Ok if we run off the end */
1781 if (errcode
== EXT2_ET_EXTENT_NO_NEXT
)
1783 ext2fs_extent_free(handle
);
1784 fs
->flags
= save_flags
;
1790 * Override debugfs's prompt
1792 const char *debug_prog_name
= "tst_extents";