/*

 * extent.c --- routines to implement extents support

 *

 * Copyright (C) 2007 Theodore Ts'o.

 *

 * %Begin-Header%

 * This file may be redistributed under the terms of the GNU Library

 * General Public License, version 2.

 * %End-Header%

 */

#include "config.h"

#include <stdio.h>

#include <string.h>

#if HAVE_UNISTD_H

#include <unistd.h>

#endif

#if HAVE_ERRNO_H

#include <errno.h>

#endif

#if HAVE_SYS_STAT_H

#include <sys/stat.h>

#endif

#if HAVE_SYS_TYPES_H

#include <sys/types.h>

#endif

#include "ext2_fs.h"

#include "ext2fsP.h"

#include "e2image.h"

#undef DEBUG

/*

 * Definitions to be dropped in lib/ext2fs/ext2fs.h

 */

/*

 * Private definitions

 */

struct extent_path {

	char		*buf;

	int		entries;

	int		max_entries;

	int		left;

	int		visit_num;

	int		flags;

	blk64_t		end_blk;

	void		*curr;

};

struct ext2_extent_handle {

	errcode_t		magic;

	ext2_filsys		fs;

	ext2_ino_t 		ino;

	struct ext2_inode	*inode;

	struct ext2_inode	inodebuf;

	int			type;

	int			level;

	int			max_depth;

	int			max_paths;

	struct extent_path	*path;

};

struct ext2_extent_path {

	errcode_t		magic;

	int			leaf_height;

	blk64_t			lblk;

};

/*

 *  Useful Debugging stuff

 */

#ifdef DEBUG

static void dbg_show_header(struct ext3_extent_header *eh)

{

	printf("header: magic=%x entries=%u max=%u depth=%u generation=%u\n",

			ext2fs_le16_to_cpu(eh->eh_magic),

			ext2fs_le16_to_cpu(eh->eh_entries),

			ext2fs_le16_to_cpu(eh->eh_max),

			ext2fs_le16_to_cpu(eh->eh_depth),

			ext2fs_le32_to_cpu(eh->eh_generation));

}

static void dbg_show_index(struct ext3_extent_idx *ix)

{

	printf("index: block=%u leaf=%u leaf_hi=%u unused=%u\n",

			ext2fs_le32_to_cpu(ix->ei_block),

			ext2fs_le32_to_cpu(ix->ei_leaf),

			ext2fs_le16_to_cpu(ix->ei_leaf_hi),

			ext2fs_le16_to_cpu(ix->ei_unused));

}

static void dbg_show_extent(struct ext3_extent *ex)

{

	printf("extent: block=%u-%u len=%u start=%u start_hi=%u\n",

			ext2fs_le32_to_cpu(ex->ee_block),

			ext2fs_le32_to_cpu(ex->ee_block) +

			ext2fs_le16_to_cpu(ex->ee_len) - 1,

			ext2fs_le16_to_cpu(ex->ee_len),

			ext2fs_le32_to_cpu(ex->ee_start),

			ext2fs_le16_to_cpu(ex->ee_start_hi));

}

static void dbg_print_extent(char *desc, struct ext2fs_extent *extent)

{

	if (desc)

		printf("%s: ", desc);

	printf("extent: lblk %llu--%llu, len %u, pblk %llu, flags: ",

	       extent->e_lblk, extent->e_lblk + extent->e_len - 1,

	       extent->e_len, extent->e_pblk);

	if (extent->e_flags & EXT2_EXTENT_FLAGS_LEAF)

		fputs("LEAF ", stdout);

	if (extent->e_flags & EXT2_EXTENT_FLAGS_UNINIT)

		fputs("UNINIT ", stdout);

	if (extent->e_flags & EXT2_EXTENT_FLAGS_SECOND_VISIT)

		fputs("2ND_VISIT ", stdout);

	if (!extent->e_flags)

		fputs("(none)", stdout);

	fputc('\n', stdout);

}

static void dump_path(const char *tag, struct ext2_extent_handle *handle,

		      struct extent_path *path)

{

	struct extent_path *ppp = path;

	printf("%s: level=%d\n", tag, handle->level);

	do {

		printf("%s: path=%ld buf=%p entries=%d max_entries=%d left=%d "

		       "visit_num=%d flags=0x%x end_blk=%llu curr=%p(%ld)\n",

		       tag, (ppp - handle->path), ppp->buf, ppp->entries,

		       ppp->max_entries, ppp->left, ppp->visit_num, ppp->flags,

		       ppp->end_blk, ppp->curr, ppp->curr - (void *)ppp->buf);

		printf("  ");

		dbg_show_header((struct ext3_extent_header *)ppp->buf);

		if (ppp->curr) {

			printf("  ");

			dbg_show_index(ppp->curr);

			printf("  ");

			dbg_show_extent(ppp->curr);

		}

		ppp--;

	} while (ppp >= handle->path);

	fflush(stdout);

	return;

}

#else

#define dbg_show_header(eh) do { } while (0)

#define dbg_show_index(ix) do { } while (0)

#define dbg_show_extent(ex) do { } while (0)

#define dbg_print_extent(desc, ex) do { } while (0)

#define dump_path(tag, handle, path) do { } while (0)

#endif

/*

 * Verify the extent header as being sane

 */

errcode_t ext2fs_extent_header_verify(void *ptr, int size)

{

	int eh_max, entry_size;

	struct ext3_extent_header *eh = ptr;

	dbg_show_header(eh);

	if (ext2fs_le16_to_cpu(eh->eh_magic) != EXT3_EXT_MAGIC)

		return EXT2_ET_EXTENT_HEADER_BAD;

	if (ext2fs_le16_to_cpu(eh->eh_entries) > ext2fs_le16_to_cpu(eh->eh_max))

		return EXT2_ET_EXTENT_HEADER_BAD;

	if (eh->eh_depth == 0)

		entry_size = sizeof(struct ext3_extent);

	else

		entry_size = sizeof(struct ext3_extent_idx);

	eh_max = (size - sizeof(*eh)) / entry_size;

	/* Allow two extent-sized items at the end of the block, for

	 * ext4_extent_tail with checksum in the future. */

	if ((ext2fs_le16_to_cpu(eh->eh_max) > eh_max) ||

	    (ext2fs_le16_to_cpu(eh->eh_max) < (eh_max - 2)))

		return EXT2_ET_EXTENT_HEADER_BAD;

	return 0;

}

/*

 * Begin functions to handle an inode's extent information

 */

void ext2fs_extent_free(ext2_extent_handle_t handle)

{

	int			i;

	if (!handle)

		return;

	if (handle->path) {

		for (i = 1; i < handle->max_paths; i++) {

			if (handle->path[i].buf)

				ext2fs_free_mem(&handle->path[i].buf);

		}

		ext2fs_free_mem(&handle->path);

	}

	ext2fs_free_mem(&handle);

}

errcode_t ext2fs_extent_open(ext2_filsys fs, ext2_ino_t ino,

				    ext2_extent_handle_t *ret_handle)

{

	return ext2fs_extent_open2(fs, ino, NULL, ret_handle);

}

errcode_t ext2fs_extent_open2(ext2_filsys fs, ext2_ino_t ino,

				    struct ext2_inode *inode,

				    ext2_extent_handle_t *ret_handle)

{

	struct ext2_extent_handle	*handle;

	errcode_t			retval;

	int				i;

	struct ext3_extent_header	*eh;

	EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);

	if (!inode)

		if ((ino == 0) || (ino > fs->super->s_inodes_count))

			return EXT2_ET_BAD_INODE_NUM;

	retval = ext2fs_get_mem(sizeof(struct ext2_extent_handle), &handle);

	if (retval)

		return retval;

	memset(handle, 0, sizeof(struct ext2_extent_handle));

	handle->ino = ino;

	handle->fs = fs;

	if (inode) {

		handle->inode = inode;

	} else {

		handle->inode = &handle->inodebuf;

		retval = ext2fs_read_inode(fs, ino, handle->inode);

		if (retval)

			goto errout;

	}

	eh = (struct ext3_extent_header *) &handle->inode->i_block[0];

	for (i=0; i < EXT2_N_BLOCKS; i++)

		if (handle->inode->i_block[i])

			break;

	if (i >= EXT2_N_BLOCKS) {

		eh->eh_magic = ext2fs_cpu_to_le16(EXT3_EXT_MAGIC);

		eh->eh_depth = 0;

		eh->eh_entries = 0;

		i = (sizeof(handle->inode->i_block) - sizeof(*eh)) /

			sizeof(struct ext3_extent);

		eh->eh_max = ext2fs_cpu_to_le16(i);

		handle->inode->i_flags |= EXT4_EXTENTS_FL;

	}

	if (!(handle->inode->i_flags & EXT4_EXTENTS_FL)) {

		retval = EXT2_ET_INODE_NOT_EXTENT;

		goto errout;

	}

	retval = ext2fs_extent_header_verify(eh, sizeof(handle->inode->i_block));

	if (retval)

		goto errout;

	handle->max_depth = ext2fs_le16_to_cpu(eh->eh_depth);

	handle->type = ext2fs_le16_to_cpu(eh->eh_magic);

	handle->max_paths = handle->max_depth + 1;

	retval = ext2fs_get_memzero(handle->max_paths *

				    sizeof(struct extent_path),

				    &handle->path);

	handle->path[0].buf = (char *) handle->inode->i_block;

	handle->path[0].left = handle->path[0].entries =

		ext2fs_le16_to_cpu(eh->eh_entries);

	handle->path[0].max_entries = ext2fs_le16_to_cpu(eh->eh_max);

	handle->path[0].curr = 0;

	handle->path[0].end_blk =

		(EXT2_I_SIZE(handle->inode) + fs->blocksize - 1) >>

		 EXT2_BLOCK_SIZE_BITS(fs->super);

	handle->path[0].visit_num = 1;

	handle->level = 0;

	handle->magic = EXT2_ET_MAGIC_EXTENT_HANDLE;

	*ret_handle = handle;

	return 0;

errout:

	ext2fs_extent_free(handle);

	return retval;

}

/*

 * This function is responsible for (optionally) moving through the

 * extent tree and then returning the current extent

 */

errcode_t ext2fs_extent_get(ext2_extent_handle_t handle,

			    int flags, struct ext2fs_extent *extent)

{

	struct extent_path	*path, *newpath;

	struct ext3_extent_header	*eh;

	struct ext3_extent_idx		*ix = 0;

	struct ext3_extent		*ex;

	errcode_t			retval;

	blk64_t				blk;

	blk64_t				end_blk;

	int				orig_op, op;

	int				failed_csum = 0;

	EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);

	if (!handle->path)

		return EXT2_ET_NO_CURRENT_NODE;

	orig_op = op = flags & EXT2_EXTENT_MOVE_MASK;

retry:

	path = handle->path + handle->level;

	if ((orig_op == EXT2_EXTENT_NEXT) ||

	    (orig_op == EXT2_EXTENT_NEXT_LEAF)) {

		if (handle->level < handle->max_depth) {

			/* interior node */

			if (path->visit_num == 0) {

				path->visit_num++;

				op = EXT2_EXTENT_DOWN;

			} else if (path->left > 0)

				op = EXT2_EXTENT_NEXT_SIB;

			else if (handle->level > 0)

				op = EXT2_EXTENT_UP;

			else

				return EXT2_ET_EXTENT_NO_NEXT;

		} else {

			/* leaf node */

			if (path->left > 0)

				op = EXT2_EXTENT_NEXT_SIB;

			else if (handle->level > 0)

				op = EXT2_EXTENT_UP;

			else

				return EXT2_ET_EXTENT_NO_NEXT;

		}

		if (op != EXT2_EXTENT_NEXT_SIB) {

#ifdef DEBUG_GET_EXTENT

			printf("<<<< OP = %s\n",

			       (op == EXT2_EXTENT_DOWN) ? "down" :

			       ((op == EXT2_EXTENT_UP) ? "up" : "unknown"));

#endif

		}

	}

	if ((orig_op == EXT2_EXTENT_PREV) ||

	    (orig_op == EXT2_EXTENT_PREV_LEAF)) {

		if (handle->level < handle->max_depth) {

			/* interior node */

			if (path->visit_num > 0 ) {

				/* path->visit_num = 0; */

				op = EXT2_EXTENT_DOWN_AND_LAST;

			} else if (path->left < path->entries-1)

				op = EXT2_EXTENT_PREV_SIB;

			else if (handle->level > 0)

				op = EXT2_EXTENT_UP;

			else

				return EXT2_ET_EXTENT_NO_PREV;

		} else {

			/* leaf node */

			if (path->left < path->entries-1)

				op = EXT2_EXTENT_PREV_SIB;

			else if (handle->level > 0)

				op = EXT2_EXTENT_UP;

			else

				return EXT2_ET_EXTENT_NO_PREV;

		}

		if (op != EXT2_EXTENT_PREV_SIB) {

#ifdef DEBUG_GET_EXTENT

			printf("<<<< OP = %s\n",

			       (op == EXT2_EXTENT_DOWN_AND_LAST) ? "down/last" :

			       ((op == EXT2_EXTENT_UP) ? "up" : "unknown"));

#endif

		}

	}

	if (orig_op == EXT2_EXTENT_LAST_LEAF) {

		if ((handle->level < handle->max_depth) &&

		    (path->left == 0))

			op = EXT2_EXTENT_DOWN;

		else

			op = EXT2_EXTENT_LAST_SIB;

#ifdef DEBUG_GET_EXTENT

		printf("<<<< OP = %s\n",

			   (op == EXT2_EXTENT_DOWN) ? "down" : "last_sib");

#endif

	}

	switch (op) {

	case EXT2_EXTENT_CURRENT:

		ix = path->curr;

		break;

	case EXT2_EXTENT_ROOT:

		handle->level = 0;

		path = handle->path + handle->level;

		/* fallthrough */

	case EXT2_EXTENT_FIRST_SIB:

		path->left = path->entries;

		path->curr = 0;

		/* fallthrough */

	case EXT2_EXTENT_NEXT_SIB:

		if (path->left <= 0)

			return EXT2_ET_EXTENT_NO_NEXT;

		if (path->curr) {

			ix = path->curr;

			ix++;

		} else {

			eh = (struct ext3_extent_header *) path->buf;

			ix = EXT_FIRST_INDEX(eh);

		}

		path->left--;

		path->curr = ix;

		path->visit_num = 0;

		break;

	case EXT2_EXTENT_PREV_SIB:

		if (!path->curr ||

		    path->left+1 >= path->entries)

			return EXT2_ET_EXTENT_NO_PREV;

		ix = path->curr;

		ix--;

		path->curr = ix;

		path->left++;

		if (handle->level < handle->max_depth)

			path->visit_num = 1;

		break;

	case EXT2_EXTENT_LAST_SIB:

		eh = (struct ext3_extent_header *) path->buf;

		path->curr = EXT_LAST_EXTENT(eh);

		ix = path->curr;

		path->left = 0;

		path->visit_num = 0;

		break;

	case EXT2_EXTENT_UP:

		if (handle->level <= 0)

			return EXT2_ET_EXTENT_NO_UP;

		handle->level--;

		path--;

		ix = path->curr;

		if ((orig_op == EXT2_EXTENT_PREV) ||

		    (orig_op == EXT2_EXTENT_PREV_LEAF))

			path->visit_num = 0;

		break;

	case EXT2_EXTENT_DOWN:

	case EXT2_EXTENT_DOWN_AND_LAST:

		if (!path->curr ||(handle->level >= handle->max_depth))

			return EXT2_ET_EXTENT_NO_DOWN;

		ix = path->curr;

		newpath = path + 1;

		if (!newpath->buf) {

			retval = ext2fs_get_mem(handle->fs->blocksize,

						&newpath->buf);

			if (retval)

				return retval;

		}

		blk = ext2fs_le32_to_cpu(ix->ei_leaf) +

			((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32);

		if ((handle->fs->flags & EXT2_FLAG_IMAGE_FILE) &&

		    (handle->fs->io != handle->fs->image_io))

			memset(newpath->buf, 0, handle->fs->blocksize);

		else {

			retval = io_channel_read_blk64(handle->fs->io,

						     blk, 1, newpath->buf);

			if (retval)

				return retval;

		}

		handle->level++;

		eh = (struct ext3_extent_header *) newpath->buf;

		retval = ext2fs_extent_header_verify(eh, handle->fs->blocksize);

		if (retval) {

			handle->level--;

			return retval;

		}

		if (!(handle->fs->flags & EXT2_FLAG_IGNORE_CSUM_ERRORS) &&

		    !ext2fs_extent_block_csum_verify(handle->fs, handle->ino,

						     eh))

			failed_csum = 1;

		newpath->left = newpath->entries =

			ext2fs_le16_to_cpu(eh->eh_entries);

		newpath->max_entries = ext2fs_le16_to_cpu(eh->eh_max);

		if (path->left > 0) {

			ix++;

			newpath->end_blk = ext2fs_le32_to_cpu(ix->ei_block);

		} else

			newpath->end_blk = path->end_blk;

		path = newpath;

		if (op == EXT2_EXTENT_DOWN) {

			ix = EXT_FIRST_INDEX((struct ext3_extent_header *) eh);

			path->curr = ix;

			path->left = path->entries - 1;

			path->visit_num = 0;

		} else {

			ix = EXT_LAST_INDEX((struct ext3_extent_header *) eh);

			path->curr = ix;

			path->left = 0;

			if (handle->level < handle->max_depth)

				path->visit_num = 1;

		}

#ifdef DEBUG_GET_EXTENT

		printf("Down to level %d/%d, end_blk=%llu\n",

			   handle->level, handle->max_depth,

			   path->end_blk);

#endif

		break;

	default:

		return EXT2_ET_OP_NOT_SUPPORTED;

	}

	if (!ix)

		return EXT2_ET_NO_CURRENT_NODE;

	extent->e_flags = 0;

#ifdef DEBUG_GET_EXTENT

	printf("(Left %d)\n", path->left);

#endif

	if (handle->level == handle->max_depth) {

		ex = (struct ext3_extent *) ix;

		extent->e_pblk = ext2fs_le32_to_cpu(ex->ee_start) +

			((__u64) ext2fs_le16_to_cpu(ex->ee_start_hi) << 32);

		extent->e_lblk = ext2fs_le32_to_cpu(ex->ee_block);

		extent->e_len = ext2fs_le16_to_cpu(ex->ee_len);

		extent->e_flags |= EXT2_EXTENT_FLAGS_LEAF;

		if (extent->e_len > EXT_INIT_MAX_LEN) {

			extent->e_len -= EXT_INIT_MAX_LEN;

			extent->e_flags |= EXT2_EXTENT_FLAGS_UNINIT;

		}

	} else {

		extent->e_pblk = ext2fs_le32_to_cpu(ix->ei_leaf) +

			((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32);

		extent->e_lblk = ext2fs_le32_to_cpu(ix->ei_block);

		if (path->left > 0) {

			ix++;

			end_blk = ext2fs_le32_to_cpu(ix->ei_block);

		} else

			end_blk = path->end_blk;

		extent->e_len = end_blk - extent->e_lblk;

	}

	if (path->visit_num)

		extent->e_flags |= EXT2_EXTENT_FLAGS_SECOND_VISIT;

	if (((orig_op == EXT2_EXTENT_NEXT_LEAF) ||

	     (orig_op == EXT2_EXTENT_PREV_LEAF)) &&

	    (handle->level != handle->max_depth))

		goto retry;

	if ((orig_op == EXT2_EXTENT_LAST_LEAF) &&

	    ((handle->level != handle->max_depth) ||

	     (path->left != 0)))

		goto retry;

	if (failed_csum)

		return EXT2_ET_EXTENT_CSUM_INVALID;

	return 0;

}

static errcode_t update_path(ext2_extent_handle_t handle)

{

	blk64_t				blk;

	errcode_t			retval;

	struct ext3_extent_idx		*ix;

	struct ext3_extent_header	*eh;

	if (handle->level == 0) {

		retval = ext2fs_write_inode(handle->fs, handle->ino,

					    handle->inode);

	} else {

		ix = handle->path[handle->level - 1].curr;

		blk = ext2fs_le32_to_cpu(ix->ei_leaf) +

			((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32);

		/* then update the checksum */

		eh = (struct ext3_extent_header *)

				handle->path[handle->level].buf;

		retval = ext2fs_extent_block_csum_set(handle->fs, handle->ino,

						      eh);

		if (retval)

			return retval;

		retval = io_channel_write_blk64(handle->fs->io,

				      blk, 1, handle->path[handle->level].buf);

	}

	return retval;

}

#if 0

errcode_t ext2fs_extent_save_path(ext2_extent_handle_t handle,

				  ext2_extent_path_t *ret_path)

{

	ext2_extent_path_t	save_path;

	struct ext2fs_extent	extent;

	struct ext2_extent_info	info;

	errcode_t		retval;

	retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);

	if (retval)

		return retval;

	retval = ext2fs_extent_get_info(handle, &info;;

	if (retval)

		return retval;

	retval = ext2fs_get_mem(sizeof(struct ext2_extent_path), &save_path);

	if (retval)

		return retval;

	memset(save_path, 0, sizeof(struct ext2_extent_path));

	save_path->magic = EXT2_ET_MAGIC_EXTENT_PATH;

	save_path->leaf_height = info.max_depth - info.curr_level - 1;

	save_path->lblk = extent.e_lblk;

	*ret_path = save_path;

	return 0;

}

errcode_t ext2fs_extent_free_path(ext2_extent_path_t path)

{

	EXT2_CHECK_MAGIC(path, EXT2_ET_MAGIC_EXTENT_PATH);

	ext2fs_free_mem(&path);

	return 0;

}

#endif

/*

 * Go to the node at leaf_level which contains logical block blk.

 *

 * leaf_level is height from the leaf node level, i.e.

 * leaf_level 0 is at leaf node, leaf_level 1 is 1 above etc.

 *

 * If "blk" has no mapping (hole) then handle is left at last

 * extent before blk.

 */

errcode_t ext2fs_extent_goto2(ext2_extent_handle_t handle,

			      int leaf_level, blk64_t blk)

{

	struct ext2fs_extent	extent;

	errcode_t		retval;

	retval = ext2fs_extent_get(handle, EXT2_EXTENT_ROOT, &extent);

	if (retval) {

		if (retval == EXT2_ET_EXTENT_NO_NEXT)

			retval = EXT2_ET_EXTENT_NOT_FOUND;

		return retval;

	}

	if (leaf_level > handle->max_depth) {

#ifdef DEBUG

		printf("leaf level %d greater than tree depth %d\n",

			leaf_level, handle->max_depth);

#endif

		return EXT2_ET_OP_NOT_SUPPORTED;

	}

#ifdef DEBUG

	printf("goto extent ino %u, level %d, %llu\n", handle->ino,

	       leaf_level, blk);

#endif

#ifdef DEBUG_GOTO_EXTENTS

	dbg_print_extent("root", &extent);

#endif

	while (1) {

		if (handle->max_depth - handle->level == leaf_level) {

			/* block is in this &extent */

			if ((blk >= extent.e_lblk) &&

			    (blk < extent.e_lblk + extent.e_len))

				return 0;

			if (blk < extent.e_lblk) {

				retval = ext2fs_extent_get(handle,

							   EXT2_EXTENT_PREV_SIB,

							   &extent);

				return EXT2_ET_EXTENT_NOT_FOUND;

			}

			retval = ext2fs_extent_get(handle,

						   EXT2_EXTENT_NEXT_SIB,

						   &extent);

			if (retval == EXT2_ET_EXTENT_NO_NEXT)

				return EXT2_ET_EXTENT_NOT_FOUND;

			if (retval)

				return retval;

			continue;

		}

		retval = ext2fs_extent_get(handle, EXT2_EXTENT_NEXT_SIB,

					   &extent);

		if (retval == EXT2_ET_EXTENT_NO_NEXT)

			goto go_down;

		if (retval)

			return retval;

#ifdef DEBUG_GOTO_EXTENTS

		dbg_print_extent("next", &extent);

#endif

		if (blk == extent.e_lblk)

			goto go_down;

		if (blk > extent.e_lblk)

			continue;

		retval = ext2fs_extent_get(handle, EXT2_EXTENT_PREV_SIB,

					   &extent);

		if (retval)

			return retval;

#ifdef DEBUG_GOTO_EXTENTS

		dbg_print_extent("prev", &extent);

#endif

	go_down:

		retval = ext2fs_extent_get(handle, EXT2_EXTENT_DOWN,

					   &extent);

		if (retval)

			return retval;

#ifdef DEBUG_GOTO_EXTENTS

		dbg_print_extent("down", &extent);

#endif

	}

}

errcode_t ext2fs_extent_goto(ext2_extent_handle_t handle,

			     blk64_t blk)

{

	return ext2fs_extent_goto2(handle, 0, blk);

}

/*

 * Traverse back up to root fixing parents of current node as needed.

 *

 * If we changed start of first entry in a node, fix parent index start

 * and so on.

 *

 * Safe to call for any position in node; if not at the first entry,

 * it will simply return.

 *

 * Note a subtlety of this function -- if there happen to be two extents

 * mapping the same lblk and someone calls fix_parents on the second of the two

 * extents, the position of the extent handle after the call will be the second

 * extent if nothing happened, or the first extent if something did.  A caller

 * in this situation must use ext2fs_extent_goto() after calling this function.

 * Or simply don't map the same lblk with two extents, ever.

 */

errcode_t ext2fs_extent_fix_parents(ext2_extent_handle_t handle)

{

	int				retval = 0;

	int				orig_height;

	blk64_t				start;

	struct extent_path		*path;

	struct ext2fs_extent		extent;

	struct ext2_extent_info		info;

	EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);

	if (!(handle->fs->flags & EXT2_FLAG_RW))

		return EXT2_ET_RO_FILSYS;

	if (!handle->path)

		return EXT2_ET_NO_CURRENT_NODE;

	path = handle->path + handle->level;

	if (!path->curr)

		return EXT2_ET_NO_CURRENT_NODE;

	retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);

	if (retval)

		goto done;

	/* modified node's start block */

	start = extent.e_lblk;

	if ((retval = ext2fs_extent_get_info(handle, &info)))

		return retval;

	orig_height = info.max_depth - info.curr_level;

	/* traverse up until index not first, or startblk matches, or top */

	while (handle->level > 0 &&

	       (path->left == path->entries - 1)) {

		retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent);

		if (retval)

			goto done;

		if (extent.e_lblk == start)

			break;

		path = handle->path + handle->level;

		extent.e_len += (extent.e_lblk - start);

		extent.e_lblk = start;

		retval = ext2fs_extent_replace(handle, 0, &extent);

		if (retval)

			goto done;

		update_path(handle);

	}

	/* put handle back to where we started */

	retval = ext2fs_extent_goto2(handle, orig_height, start);

done:

	return retval;

}

errcode_t ext2fs_extent_replace(ext2_extent_handle_t handle,

				int flags EXT2FS_ATTR((unused)),

				struct ext2fs_extent *extent)

{

	struct extent_path		*path;

	struct ext3_extent_idx		*ix;

	struct ext3_extent		*ex;

	EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);

	if (!(handle->fs->flags & EXT2_FLAG_RW))

		return EXT2_ET_RO_FILSYS;

	if (!handle->path)

		return EXT2_ET_NO_CURRENT_NODE;

	path = handle->path + handle->level;

	if (!path->curr)

		return EXT2_ET_NO_CURRENT_NODE;

#ifdef DEBUG

	printf("extent replace: %u ", handle->ino);

	dbg_print_extent(0, extent);

#endif

	if (handle->level == handle->max_depth) {

		ex = path->curr;

		ex->ee_block = ext2fs_cpu_to_le32(extent->e_lblk);

		ex->ee_start = ext2fs_cpu_to_le32(extent->e_pblk & 0xFFFFFFFF);

		ex->ee_start_hi = ext2fs_cpu_to_le16(extent->e_pblk >> 32);

		if (extent->e_flags & EXT2_EXTENT_FLAGS_UNINIT) {

			if (extent->e_len > EXT_UNINIT_MAX_LEN)

				return EXT2_ET_EXTENT_INVALID_LENGTH;

			ex->ee_len = ext2fs_cpu_to_le16(extent->e_len +

							EXT_INIT_MAX_LEN);

		} else {

			if (extent->e_len > EXT_INIT_MAX_LEN)

				return EXT2_ET_EXTENT_INVALID_LENGTH;

			ex->ee_len = ext2fs_cpu_to_le16(extent->e_len);

		}

	} else {

		ix = path->curr;

		ix->ei_leaf = ext2fs_cpu_to_le32(extent->e_pblk & 0xFFFFFFFF);

		ix->ei_leaf_hi = ext2fs_cpu_to_le16(extent->e_pblk >> 32);

		ix->ei_block = ext2fs_cpu_to_le32(extent->e_lblk);

		ix->ei_unused = 0;

	}

	update_path(handle);

	return 0;

}

static int splitting_at_eof(struct ext2_extent_handle *handle,

			    struct extent_path *path)

{

	struct extent_path *ppp = path;

	dump_path(__func__, handle, path);

	if (handle->level == 0)

		return 0;