[thirdparty/e2fsprogs.git] / lib / ext2fs / punch.c

/*
 * punch.c --- deallocate blocks allocated to an inode
 *
 * Copyright (C) 2010 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
#include <errno.h>

#include "ext2_fs.h"
#include "ext2fs.h"
#include "ext2fsP.h"

#undef PUNCH_DEBUG

/*
 * This function returns 1 if the specified block is all zeros
 */
static int check_zero_block(char *buf, int blocksize)
{
	char	*cp = buf;
	int	left = blocksize;

	while (left > 0) {
		if (*cp++)
			return 0;
		left--;
	}
	return 1;
}

/*
 * This clever recursive function handles i_blocks[] as well as
 * indirect, double indirect, and triple indirect blocks.  It iterates
 * over the entries in the i_blocks array or indirect blocks, and for
 * each one, will recursively handle any indirect blocks and then
 * frees and deallocates the blocks.
 */
static errcode_t ind_punch(ext2_filsys fs, struct ext2_inode *inode,
			   char *block_buf, blk_t *p, int level,
			   blk_t start, blk_t count, int max)
{
	errcode_t	retval;
	blk_t		b;
	int		i;
	blk64_t		offset, incr;
	int		freed = 0;

#ifdef PUNCH_DEBUG
	printf("Entering ind_punch, level %d, start %u, count %u, "
	       "max %d\n", level, start, count, max);
#endif
	incr = 1ULL << ((EXT2_BLOCK_SIZE_BITS(fs->super)-2)*level);
	for (i=0, offset=0; i < max; i++, p++, offset += incr) {
		if (offset >= start + count)
			break;
		if (*p == 0 || (offset+incr) <= start)
			continue;
		b = *p;
		if (level > 0) {
			blk_t start2;
#ifdef PUNCH_DEBUG
			printf("Reading indirect block %u\n", b);
#endif
			retval = ext2fs_read_ind_block(fs, b, block_buf);
			if (retval)
				return retval;
			start2 = (start > offset) ? start - offset : 0;
			retval = ind_punch(fs, inode, block_buf + fs->blocksize,
					   (blk_t *) block_buf, level - 1,
					   start2, count - offset,
					   fs->blocksize >> 2);
			if (retval)
				return retval;
			retval = ext2fs_write_ind_block(fs, b, block_buf);
			if (retval)
				return retval;
			if (!check_zero_block(block_buf, fs->blocksize))
				continue;
		}
#ifdef PUNCH_DEBUG
		printf("Freeing block %u (offset %llu)\n", b, offset);
#endif
		ext2fs_block_alloc_stats(fs, b, -1);
		*p = 0;
		freed++;
	}
#ifdef PUNCH_DEBUG
	printf("Freed %d blocks\n", freed);
#endif
	return ext2fs_iblk_sub_blocks(fs, inode, freed);
}

static errcode_t ext2fs_punch_ind(ext2_filsys fs, struct ext2_inode *inode,
				  char *block_buf, blk_t start, blk_t count)
{
	errcode_t		retval;
	char			*buf = 0;
	int			level;
	int			num = EXT2_NDIR_BLOCKS;
	blk_t			*bp = inode->i_block;
	blk_t			addr_per_block;
	blk64_t			max = EXT2_NDIR_BLOCKS;

	if (!block_buf) {
		retval = ext2fs_get_array(3, fs->blocksize, &buf);
		if (retval)
			return retval;
		block_buf = buf;
	}

	addr_per_block = (blk_t) fs->blocksize >> 2;

	for (level = 0; level < 4; level++, max *= (blk64_t)addr_per_block) {
#ifdef PUNCH_DEBUG
		printf("Main loop level %d, start %u count %u "
		       "max %llu num %d\n", level, start, count, max, num);
#endif
		if (start < max) {
			retval = ind_punch(fs, inode, block_buf, bp, level,
					   start, count, num);
			if (retval)
				goto errout;
			if (count > max)
				count -= max - start;
			else
				break;
			start = 0;
		} else
			start -= max;
		bp += num;
		if (level == 0) {
			num = 1;
			max = 1;
		}
	}
	retval = 0;
errout:
	if (buf)
		ext2fs_free_mem(&buf);
	return retval;
}

#ifdef PUNCH_DEBUG

#define dbg_printf(f, a...)  printf(f, ## a)

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);

}
#else
#define dbg_print_extent(desc, ex)	do { } while (0)
#define dbg_printf(f, a...)		do { } while (0)
#endif

/* Free a range of blocks, respecting cluster boundaries */
static errcode_t punch_extent_blocks(ext2_filsys fs, ext2_ino_t ino,
				     struct ext2_inode *inode,
				     blk64_t lfree_start, blk64_t free_start,
				     __u32 free_count, int *freed)
{
	blk64_t		pblk;
	int		freed_now = 0;
	__u32		cluster_freed;
	errcode_t	retval = 0;

	/* No bigalloc?  Just free each block. */
	if (EXT2FS_CLUSTER_RATIO(fs) == 1) {
		*freed += free_count;
		while (free_count-- > 0)
			ext2fs_block_alloc_stats2(fs, free_start++, -1);
		return retval;
	}

	/*
	 * Try to free up to the next cluster boundary.  We assume that all
	 * blocks in a logical cluster map to blocks from the same physical
	 * cluster, and that the offsets within the [pl]clusters match.
	 */
	if (free_start & EXT2FS_CLUSTER_MASK(fs)) {
		retval = ext2fs_map_cluster_block(fs, ino, inode,
						  lfree_start, &pblk);
		if (retval)
			goto errout;
		if (!pblk) {
			ext2fs_block_alloc_stats2(fs, free_start, -1);
			freed_now++;
		}
		cluster_freed = EXT2FS_CLUSTER_RATIO(fs) -
			(free_start & EXT2FS_CLUSTER_MASK(fs));
		if (cluster_freed > free_count)
			cluster_freed = free_count;
		free_count -= cluster_freed;
		free_start += cluster_freed;
		lfree_start += cluster_freed;
	}

	/* Free whole clusters from the middle of the range. */
	while (free_count > 0 && free_count >= EXT2FS_CLUSTER_RATIO(fs)) {
		ext2fs_block_alloc_stats2(fs, free_start, -1);
		freed_now++;
		cluster_freed = EXT2FS_CLUSTER_RATIO(fs);
		free_count -= cluster_freed;
		free_start += cluster_freed;
		lfree_start += cluster_freed;
	}

	/* Try to free the last cluster. */
	if (free_count > 0) {
		retval = ext2fs_map_cluster_block(fs, ino, inode,
						  lfree_start, &pblk);
		if (retval)
			goto errout;
		if (!pblk) {
			ext2fs_block_alloc_stats2(fs, free_start, -1);
			freed_now++;
		}
	}

errout:
	*freed += freed_now;
	return retval;
}

static errcode_t ext2fs_punch_extent(ext2_filsys fs, ext2_ino_t ino,
				     struct ext2_inode *inode,
				     blk64_t start, blk64_t end)
{
	ext2_extent_handle_t	handle = 0;
	struct ext2fs_extent	extent;
	errcode_t		retval;
	blk64_t			free_start, next, lfree_start;
	__u32			free_count, newlen;
	int			freed = 0;
	int			op;

	retval = ext2fs_extent_open2(fs, ino, inode, &handle);
	if (retval)
		return retval;
	/*
	 * Find the extent closest to the start of the punch range.  We don't
	 * check the return value because _goto() sets the current node to the
	 * next-lowest extent if 'start' is in a hole, and doesn't set a
	 * current node if there was a real error reading the extent tree.
	 * In that case, _get() will error out.
	 *
	 * Note: If _get() returns 'no current node', that simply means that
	 * there aren't any blocks mapped past this point in the file, so we're
	 * done.
	 */
	ext2fs_extent_goto(handle, start);
	retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
	if (retval == EXT2_ET_NO_CURRENT_NODE) {
		retval = 0;
		goto errout;
	} else if (retval)
		goto errout;
	while (1) {
		op = EXT2_EXTENT_NEXT_LEAF;
		dbg_print_extent("main loop", &extent);
		next = extent.e_lblk + extent.e_len;
		dbg_printf("start %llu, end %llu, next %llu\n",
			   (unsigned long long) start,
			   (unsigned long long) end,
			   (unsigned long long) next);
		if (start <= extent.e_lblk) {
			/*
			 * Have we iterated past the end of the punch region?
			 * If so, we can stop.
			 */
			if (end < extent.e_lblk)
				break;
			dbg_printf("Case #%d\n", 1);
			/* Start of deleted region before extent; 
			   adjust beginning of extent */
			free_start = extent.e_pblk;
			lfree_start = extent.e_lblk;
			if (next > end)
				free_count = end - extent.e_lblk + 1;
			else
				free_count = extent.e_len;
			extent.e_len -= free_count;
			extent.e_lblk += free_count;
			extent.e_pblk += free_count;
		} else if (end >= next-1) {
			/*
			 * Is the punch region beyond this extent?  This can
			 * happen if start is already inside a hole.  Try to
			 * advance to the next extent if this is the case.
			 */
			if (start >= next)
				goto next_extent;
			/* End of deleted region after extent;
			   adjust end of extent */
			dbg_printf("Case #%d\n", 2);
			newlen = start - extent.e_lblk;
			free_start = extent.e_pblk + newlen;
			lfree_start = extent.e_lblk + newlen;
			free_count = extent.e_len - newlen;
			extent.e_len = newlen;
		} else {
			struct ext2fs_extent	newex;

			dbg_printf("Case #%d\n", 3);
			/* The hard case; we need to split the extent */
			newex.e_pblk = extent.e_pblk +
				(end + 1 - extent.e_lblk);
			newex.e_lblk = end + 1;
			newex.e_len = next - end - 1;
			newex.e_flags = extent.e_flags;

			extent.e_len = start - extent.e_lblk;
			free_start = extent.e_pblk + extent.e_len;
			lfree_start = extent.e_lblk + extent.e_len;
			free_count = end - start + 1;

			dbg_print_extent("inserting", &newex);
			retval = ext2fs_extent_insert(handle,
					EXT2_EXTENT_INSERT_AFTER, &newex);
			if (retval)
				goto errout;
			retval = ext2fs_extent_fix_parents(handle);
			if (retval)
				goto errout;
			/*
			 * Now pointing at inserted extent; so go back.
			 *
			 * We cannot use EXT2_EXTENT_PREV to go back; note the
			 * subtlety in the comment for fix_parents().
			 */
			retval = ext2fs_extent_goto(handle, extent.e_lblk);
			if (retval)
				goto errout;
		} 
		if (extent.e_len) {
			dbg_print_extent("replacing", &extent);
			retval = ext2fs_extent_replace(handle, 0, &extent);
			if (retval)
				goto errout;
			retval = ext2fs_extent_fix_parents(handle);
		} else {
			struct ext2fs_extent	newex;
			blk64_t			old_lblk, next_lblk;
			dbg_printf("deleting current extent%s\n", "");

			/*
			 * Save the location of the next leaf, then slip
			 * back to the current extent.
			 */
			retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT,
						   &newex);
			if (retval)
				goto errout;
			old_lblk = newex.e_lblk;

			retval = ext2fs_extent_get(handle,
						   EXT2_EXTENT_NEXT_LEAF,
						   &newex);
			if (retval == EXT2_ET_EXTENT_NO_NEXT)
				next_lblk = old_lblk;
			else if (retval)
				goto errout;
			else
				next_lblk = newex.e_lblk;

			retval = ext2fs_extent_goto(handle, old_lblk);
			if (retval)
				goto errout;

			/* Now delete the extent. */
			retval = ext2fs_extent_delete(handle, 0);
			if (retval)
				goto errout;

			retval = ext2fs_extent_fix_parents(handle);
			if (retval && retval != EXT2_ET_NO_CURRENT_NODE)
				goto errout;
			retval = 0;

			/*
			 * Jump forward to the next extent.  If there are
			 * errors, the ext2fs_extent_get down below will
			 * capture them for us.
			 */
			(void)ext2fs_extent_goto(handle, next_lblk);
			op = EXT2_EXTENT_CURRENT;
		}
		if (retval)
			goto errout;
		dbg_printf("Free start %llu, free count = %u\n",
		       free_start, free_count);
		retval = punch_extent_blocks(fs, ino, inode, lfree_start,
					     free_start, free_count, &freed);
		if (retval)
			goto errout;
	next_extent:
		retval = ext2fs_extent_get(handle, op,
					   &extent);
		if (retval == EXT2_ET_EXTENT_NO_NEXT ||
		    retval == EXT2_ET_NO_CURRENT_NODE)
			break;
		if (retval)
			goto errout;
	}
	dbg_printf("Freed %d blocks\n", freed);
	retval = ext2fs_iblk_sub_blocks(fs, inode, freed);
errout:
	ext2fs_extent_free(handle);
	return retval;
}
	
static errcode_t ext2fs_punch_inline_data(ext2_filsys fs, ext2_ino_t ino,
					  struct ext2_inode *inode,
					  blk64_t start,
					  blk64_t end EXT2FS_ATTR((unused)))
{
	errcode_t retval;

	/*
	 * In libext2fs ext2fs_punch is based on block unit.  So that
	 * means that if start > 0 we don't need to do nothing.  Due
	 * to this we will remove all inline data in ext2fs_punch()
	 * now.
	 */
	if (start > 0)
		return 0;

	memset((char *)inode->i_block, 0, EXT4_MIN_INLINE_DATA_SIZE);
	inode->i_size = 0;
	retval = ext2fs_write_inode(fs, ino, inode);
	if (retval)
		return retval;

	return ext2fs_inline_data_ea_remove(fs, ino);
}

/*
 * Deallocate all logical blocks starting at start to end, inclusive.
 * If end is ~0, then this is effectively truncate.
 */
errcode_t ext2fs_punch(ext2_filsys fs, ext2_ino_t ino,
		       struct ext2_inode *inode,
		       char *block_buf, blk64_t start,
		       blk64_t end)
{
	errcode_t		retval;
	struct ext2_inode	inode_buf;

	if (start > end)
		return EINVAL;

	/* Read inode structure if necessary */
	if (!inode) {
		retval = ext2fs_read_inode(fs, ino, &inode_buf);
		if (retval)
			return retval;
		inode = &inode_buf;
	}
	if (inode->i_flags & EXT4_INLINE_DATA_FL)
		return ext2fs_punch_inline_data(fs, ino, inode, start, end);
	else if (inode->i_flags & EXT4_EXTENTS_FL)
		retval = ext2fs_punch_extent(fs, ino, inode, start, end);
	else {
		blk_t	count;

		if (start > ~0U)
			return 0;
		if (end > ~0U)
			end = ~0U;
		count = ((end - start + 1) < ~0U) ? (end - start + 1) : ~0U;
		retval = ext2fs_punch_ind(fs, inode, block_buf, 
					  (blk_t) start, count);
	}
	if (retval)
		return retval;

	return ext2fs_write_inode(fs, ino, inode);
}
Commit	Line	Data
3adb9374 TT	1	/*
	2	* punch.c --- deallocate blocks allocated to an inode
	3	*
	4	* Copyright (C) 2010 Theodore Ts'o.
	5	*
	6	* %Begin-Header%
	7	* This file may be redistributed under the terms of the GNU Library
	8	* General Public License, version 2.
	9	* %End-Header%
	10	*/
	11
d1154eb4	12	#include "config.h"
3adb9374 TT	13	#include <stdio.h>
	14	#include <string.h>
	15	#if HAVE_UNISTD_H
	16	#include <unistd.h>
	17	#endif
	18	#include <errno.h>
	19
	20	#include "ext2_fs.h"
	21	#include "ext2fs.h"
24997f1c	22	#include "ext2fsP.h"
3adb9374 TT	23
	24	#undef PUNCH_DEBUG
	25
	26	/*
	27	* This function returns 1 if the specified block is all zeros
	28	*/
	29	static int check_zero_block(char *buf, int blocksize)
	30	{
	31	char *cp = buf;
	32	int left = blocksize;
	33
	34	while (left > 0) {
	35	if (*cp++)
	36	return 0;
	37	left--;
	38	}
	39	return 1;
	40	}
	41
	42	/*
	43	* This clever recursive function handles i_blocks[] as well as
	44	* indirect, double indirect, and triple indirect blocks. It iterates
	45	* over the entries in the i_blocks array or indirect blocks, and for
	46	* each one, will recursively handle any indirect blocks and then
	47	* frees and deallocates the blocks.
	48	*/
	49	static errcode_t ind_punch(ext2_filsys fs, struct ext2_inode *inode,
	50	char block_buf, blk_t p, int level,
	51	blk_t start, blk_t count, int max)
	52	{
	53	errcode_t retval;
341bc5e3 DW	54	blk_t b;
	55	int i;
	56	blk64_t offset, incr;
3adb9374 TT	57	int freed = 0;
	58
	59	#ifdef PUNCH_DEBUG
	60	printf("Entering ind_punch, level %d, start %u, count %u, "
	61	"max %d\n", level, start, count, max);
	62	#endif
341bc5e3	63	incr = 1ULL << ((EXT2_BLOCK_SIZE_BITS(fs->super)-2)*level);
3adb9374	64	for (i=0, offset=0; i < max; i++, p++, offset += incr) {
581646b9	65	if (offset >= start + count)
3adb9374 TT	66	break;
	67	if (*p == 0 \|\| (offset+incr) <= start)
	68	continue;
	69	b = *p;
	70	if (level > 0) {
	71	blk_t start2;
	72	#ifdef PUNCH_DEBUG
	73	printf("Reading indirect block %u\n", b);
	74	#endif
	75	retval = ext2fs_read_ind_block(fs, b, block_buf);
	76	if (retval)
	77	return retval;
	78	start2 = (start > offset) ? start - offset : 0;
	79	retval = ind_punch(fs, inode, block_buf + fs->blocksize,
	80	(blk_t *) block_buf, level - 1,
	81	start2, count - offset,
	82	fs->blocksize >> 2);
	83	if (retval)
	84	return retval;
	85	retval = ext2fs_write_ind_block(fs, b, block_buf);
	86	if (retval)
	87	return retval;
	88	if (!check_zero_block(block_buf, fs->blocksize))
	89	continue;
	90	}
	91	#ifdef PUNCH_DEBUG
341bc5e3	92	printf("Freeing block %u (offset %llu)\n", b, offset);
3adb9374 TT	93	#endif
	94	ext2fs_block_alloc_stats(fs, b, -1);
	95	*p = 0;
	96	freed++;
	97	}
	98	#ifdef PUNCH_DEBUG
	99	printf("Freed %d blocks\n", freed);
	100	#endif
	101	return ext2fs_iblk_sub_blocks(fs, inode, freed);
	102	}
	103
	104	static errcode_t ext2fs_punch_ind(ext2_filsys fs, struct ext2_inode *inode,
	105	char *block_buf, blk_t start, blk_t count)
	106	{
	107	errcode_t retval;
	108	char *buf = 0;
	109	int level;
	110	int num = EXT2_NDIR_BLOCKS;
	111	blk_t *bp = inode->i_block;
	112	blk_t addr_per_block;
341bc5e3	113	blk64_t max = EXT2_NDIR_BLOCKS;
3adb9374 TT	114
	115	if (!block_buf) {
	116	retval = ext2fs_get_array(3, fs->blocksize, &buf);
	117	if (retval)
	118	return retval;
	119	block_buf = buf;
	120	}
	121
	122	addr_per_block = (blk_t) fs->blocksize >> 2;
	123
341bc5e3	124	for (level = 0; level < 4; level++, max *= (blk64_t)addr_per_block) {
3adb9374 TT	125	#ifdef PUNCH_DEBUG
3adb9374 TT	126	printf("Main loop level %d, start %u count %u "
341bc5e3	127	"max %llu num %d\n", level, start, count, max, num);
3adb9374 TT	128	#endif
	129	if (start < max) {
	130	retval = ind_punch(fs, inode, block_buf, bp, level,
	131	start, count, num);
	132	if (retval)
	133	goto errout;
	134	if (count > max)
	135	count -= max - start;
	136	else
	137	break;
	138	start = 0;
	139	} else
	140	start -= max;
	141	bp += num;
	142	if (level == 0) {
	143	num = 1;
	144	max = 1;
	145	}
	146	}
	147	retval = 0;
	148	errout:
	149	if (buf)
	150	ext2fs_free_mem(&buf);
	151	return retval;
	152	}
	153
	154	#ifdef PUNCH_DEBUG
	155
	156	#define dbg_printf(f, a...) printf(f, ## a)
	157
	158	static void dbg_print_extent(char desc, struct ext2fs_extent extent)
	159	{
	160	if (desc)
	161	printf("%s: ", desc);
	162	printf("extent: lblk %llu--%llu, len %u, pblk %llu, flags: ",
	163	extent->e_lblk, extent->e_lblk + extent->e_len - 1,
	164	extent->e_len, extent->e_pblk);
	165	if (extent->e_flags & EXT2_EXTENT_FLAGS_LEAF)
	166	fputs("LEAF ", stdout);
	167	if (extent->e_flags & EXT2_EXTENT_FLAGS_UNINIT)
	168	fputs("UNINIT ", stdout);
	169	if (extent->e_flags & EXT2_EXTENT_FLAGS_SECOND_VISIT)
	170	fputs("2ND_VISIT ", stdout);
	171	if (!extent->e_flags)
	172	fputs("(none)", stdout);
	173	fputc('\n', stdout);
	174
	175	}
	176	#else
	177	#define dbg_print_extent(desc, ex) do { } while (0)
	178	#define dbg_printf(f, a...) do { } while (0)
	179	#endif
	180
84397754 DW	181	/* Free a range of blocks, respecting cluster boundaries */
	182	static errcode_t punch_extent_blocks(ext2_filsys fs, ext2_ino_t ino,
	183	struct ext2_inode *inode,
	184	blk64_t lfree_start, blk64_t free_start,
	185	__u32 free_count, int *freed)
	186	{
	187	blk64_t pblk;
	188	int freed_now = 0;
	189	__u32 cluster_freed;
	190	errcode_t retval = 0;
	191
	192	/* No bigalloc? Just free each block. */
	193	if (EXT2FS_CLUSTER_RATIO(fs) == 1) {
	194	*freed += free_count;
	195	while (free_count-- > 0)
	196	ext2fs_block_alloc_stats2(fs, free_start++, -1);
	197	return retval;
	198	}
	199
	200	/*
	201	* Try to free up to the next cluster boundary. We assume that all
	202	* blocks in a logical cluster map to blocks from the same physical
	203	* cluster, and that the offsets within the [pl]clusters match.
	204	*/
	205	if (free_start & EXT2FS_CLUSTER_MASK(fs)) {
	206	retval = ext2fs_map_cluster_block(fs, ino, inode,
	207	lfree_start, &pblk);
	208	if (retval)
	209	goto errout;
	210	if (!pblk) {
	211	ext2fs_block_alloc_stats2(fs, free_start, -1);
	212	freed_now++;
	213	}
	214	cluster_freed = EXT2FS_CLUSTER_RATIO(fs) -
	215	(free_start & EXT2FS_CLUSTER_MASK(fs));
	216	if (cluster_freed > free_count)
	217	cluster_freed = free_count;
	218	free_count -= cluster_freed;
	219	free_start += cluster_freed;
	220	lfree_start += cluster_freed;
	221	}
	222
	223	/* Free whole clusters from the middle of the range. */
	224	while (free_count > 0 && free_count >= EXT2FS_CLUSTER_RATIO(fs)) {
	225	ext2fs_block_alloc_stats2(fs, free_start, -1);
	226	freed_now++;
	227	cluster_freed = EXT2FS_CLUSTER_RATIO(fs);
	228	free_count -= cluster_freed;
	229	free_start += cluster_freed;
	230	lfree_start += cluster_freed;
	231	}
	232
	233	/* Try to free the last cluster. */
	234	if (free_count > 0) {
	235	retval = ext2fs_map_cluster_block(fs, ino, inode,
	236	lfree_start, &pblk);
	237	if (retval)
	238	goto errout;
	239	if (!pblk) {
	240	ext2fs_block_alloc_stats2(fs, free_start, -1);
	241	freed_now++;
	242	}
	243	}
	244
245	errout:
246	*freed += freed_now;
247	return retval;
248	}
249
3adb9374 TT	250	static errcode_t ext2fs_punch_extent(ext2_filsys fs, ext2_ino_t ino,
	251	struct ext2_inode *inode,
	252	blk64_t start, blk64_t end)
	253	{
	254	ext2_extent_handle_t handle = 0;
	255	struct ext2fs_extent extent;
	256	errcode_t retval;
84397754	257	blk64_t free_start, next, lfree_start;
3adb9374 TT	258	__u32 free_count, newlen;
3adb9374 TT	259	int freed = 0;
5d494038	260	int op;
3adb9374 TT	261
	262	retval = ext2fs_extent_open2(fs, ino, inode, &handle);
	263	if (retval)
	264	return retval;
8d74ab76 DW	265	/*
	266	* Find the extent closest to the start of the punch range. We don't
	267	* check the return value because _goto() sets the current node to the
	268	* next-lowest extent if 'start' is in a hole, and doesn't set a
	269	* current node if there was a real error reading the extent tree.
	270	* In that case, _get() will error out.
042a0f52 DW	271	*
	272	* Note: If _get() returns 'no current node', that simply means that
	273	* there aren't any blocks mapped past this point in the file, so we're
	274	* done.
8d74ab76	275	*/
3adb9374 TT	276	ext2fs_extent_goto(handle, start);
3adb9374 TT	277	retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
042a0f52 DW	278	if (retval == EXT2_ET_NO_CURRENT_NODE) {
	279	retval = 0;
	280	goto errout;
	281	} else if (retval)
3adb9374 TT	282	goto errout;
3adb9374 TT	283	while (1) {
5d494038	284	op = EXT2_EXTENT_NEXT_LEAF;
3adb9374 TT	285	dbg_print_extent("main loop", &extent);
	286	next = extent.e_lblk + extent.e_len;
	287	dbg_printf("start %llu, end %llu, next %llu\n",
	288	(unsigned long long) start,
	289	(unsigned long long) end,
	290	(unsigned long long) next);
	291	if (start <= extent.e_lblk) {
80dec4cb DW	292	/*
	293	* Have we iterated past the end of the punch region?
	294	* If so, we can stop.
	295	*/
3adb9374	296	if (end < extent.e_lblk)
80dec4cb	297	break;
d32c915a	298	dbg_printf("Case #%d\n", 1);
3adb9374 TT	299	/* Start of deleted region before extent;
	300	adjust beginning of extent */
	301	free_start = extent.e_pblk;
84397754	302	lfree_start = extent.e_lblk;
3adb9374 TT	303	if (next > end)
	304	free_count = end - extent.e_lblk + 1;
	305	else
	306	free_count = extent.e_len;
	307	extent.e_len -= free_count;
	308	extent.e_lblk += free_count;
	309	extent.e_pblk += free_count;
	310	} else if (end >= next-1) {
80dec4cb DW	311	/*
	312	* Is the punch region beyond this extent? This can
	313	* happen if start is already inside a hole. Try to
	314	* advance to the next extent if this is the case.
	315	*/
3adb9374	316	if (start >= next)
80dec4cb	317	goto next_extent;
3adb9374 TT	318	/* End of deleted region after extent;
3adb9374 TT	319	adjust end of extent */
d32c915a	320	dbg_printf("Case #%d\n", 2);
3adb9374 TT	321	newlen = start - extent.e_lblk;
3adb9374 TT	322	free_start = extent.e_pblk + newlen;
84397754	323	lfree_start = extent.e_lblk + newlen;
3adb9374 TT	324	free_count = extent.e_len - newlen;
	325	extent.e_len = newlen;
	326	} else {
	327	struct ext2fs_extent newex;
	328
d32c915a	329	dbg_printf("Case #%d\n", 3);
3adb9374 TT	330	/* The hard case; we need to split the extent */
	331	newex.e_pblk = extent.e_pblk +
	332	(end + 1 - extent.e_lblk);
	333	newex.e_lblk = end + 1;
	334	newex.e_len = next - end - 1;
	335	newex.e_flags = extent.e_flags;
	336
	337	extent.e_len = start - extent.e_lblk;
	338	free_start = extent.e_pblk + extent.e_len;
84397754	339	lfree_start = extent.e_lblk + extent.e_len;
3adb9374 TT	340	free_count = end - start + 1;
	341
	342	dbg_print_extent("inserting", &newex);
	343	retval = ext2fs_extent_insert(handle,
	344	EXT2_EXTENT_INSERT_AFTER, &newex);
	345	if (retval)
	346	goto errout;
acbca26e DW	347	retval = ext2fs_extent_fix_parents(handle);
	348	if (retval)
	349	goto errout;
	350	/*
	351	* Now pointing at inserted extent; so go back.
	352	*
	353	* We cannot use EXT2_EXTENT_PREV to go back; note the
	354	* subtlety in the comment for fix_parents().
	355	*/
	356	retval = ext2fs_extent_goto(handle, extent.e_lblk);
3adb9374 TT	357	if (retval)
	358	goto errout;
	359	}
	360	if (extent.e_len) {
	361	dbg_print_extent("replacing", &extent);
	362	retval = ext2fs_extent_replace(handle, 0, &extent);
3c890ee9 DW	363	if (retval)
	364	goto errout;
	365	retval = ext2fs_extent_fix_parents(handle);
3adb9374	366	} else {
5d494038	367	struct ext2fs_extent newex;
dc9673ab	368	blk64_t old_lblk, next_lblk;
d32c915a	369	dbg_printf("deleting current extent%s\n", "");
dc9673ab	370
5d494038	371	/*
dc9673ab DW	372	* Save the location of the next leaf, then slip
dc9673ab DW	373	* back to the current extent.
5d494038	374	*/
dc9673ab DW	375	retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT,
	376	&newex);
	377	if (retval)
	378	goto errout;
	379	old_lblk = newex.e_lblk;
	380
5d494038	381	retval = ext2fs_extent_get(handle,
dc9673ab	382	EXT2_EXTENT_NEXT_LEAF,
5d494038	383	&newex);
dc9673ab DW	384	if (retval == EXT2_ET_EXTENT_NO_NEXT)
	385	next_lblk = old_lblk;
	386	else if (retval)
	387	goto errout;
	388	else
	389	next_lblk = newex.e_lblk;
	390
	391	retval = ext2fs_extent_goto(handle, old_lblk);
	392	if (retval)
	393	goto errout;
	394
	395	/* Now delete the extent. */
	396	retval = ext2fs_extent_delete(handle, 0);
	397	if (retval)
	398	goto errout;
	399
3c890ee9 DW	400	retval = ext2fs_extent_fix_parents(handle);
	401	if (retval && retval != EXT2_ET_NO_CURRENT_NODE)
	402	goto errout;
	403	retval = 0;
	404
ec3a42b1 DW	405	/*
	406	* Jump forward to the next extent. If there are
	407	* errors, the ext2fs_extent_get down below will
	408	* capture them for us.
	409	*/
	410	(void)ext2fs_extent_goto(handle, next_lblk);
dc9673ab	411	op = EXT2_EXTENT_CURRENT;
3adb9374 TT	412	}
	413	if (retval)
	414	goto errout;
	415	dbg_printf("Free start %llu, free count = %u\n",
	416	free_start, free_count);
84397754 DW	417	retval = punch_extent_blocks(fs, ino, inode, lfree_start,
	418	free_start, free_count, &freed);
	419	if (retval)
	420	goto errout;
3adb9374	421	next_extent:
5d494038	422	retval = ext2fs_extent_get(handle, op,
3adb9374	423	&extent);
5d494038 DW	424	if (retval == EXT2_ET_EXTENT_NO_NEXT \|\|
5d494038 DW	425	retval == EXT2_ET_NO_CURRENT_NODE)
3adb9374 TT	426	break;
	427	if (retval)
	428	goto errout;
	429	}
	430	dbg_printf("Freed %d blocks\n", freed);
	431	retval = ext2fs_iblk_sub_blocks(fs, inode, freed);
	432	errout:
	433	ext2fs_extent_free(handle);
	434	return retval;
	435	}
	436
97581d44 ZL	437	static errcode_t ext2fs_punch_inline_data(ext2_filsys fs, ext2_ino_t ino,
97581d44 ZL	438	struct ext2_inode *inode,
25f291c9 TT	439	blk64_t start,
25f291c9 TT	440	blk64_t end EXT2FS_ATTR((unused)))
97581d44 ZL	441	{
	442	errcode_t retval;
	443
	444	/*
	445	* In libext2fs ext2fs_punch is based on block unit. So that
	446	* means that if start > 0 we don't need to do nothing. Due
	447	* to this we will remove all inline data in ext2fs_punch()
	448	* now.
	449	*/
	450	if (start > 0)
	451	return 0;
	452
	453	memset((char *)inode->i_block, 0, EXT4_MIN_INLINE_DATA_SIZE);
	454	inode->i_size = 0;
	455	retval = ext2fs_write_inode(fs, ino, inode);
	456	if (retval)
	457	return retval;
	458
	459	return ext2fs_inline_data_ea_remove(fs, ino);
	460	}
	461
3adb9374 TT	462	/*
	463	* Deallocate all logical blocks starting at start to end, inclusive.
	464	* If end is ~0, then this is effectively truncate.
	465	*/
f404167d TT	466	errcode_t ext2fs_punch(ext2_filsys fs, ext2_ino_t ino,
	467	struct ext2_inode *inode,
	468	char *block_buf, blk64_t start,
	469	blk64_t end)
3adb9374 TT	470	{
	471	errcode_t retval;
	472	struct ext2_inode inode_buf;
	473
	474	if (start > end)
	475	return EINVAL;
	476
3adb9374 TT	477	/* Read inode structure if necessary */
	478	if (!inode) {
	479	retval = ext2fs_read_inode(fs, ino, &inode_buf);
	480	if (retval)
	481	return retval;
	482	inode = &inode_buf;
	483	}
97581d44 ZL	484	if (inode->i_flags & EXT4_INLINE_DATA_FL)
	485	return ext2fs_punch_inline_data(fs, ino, inode, start, end);
	486	else if (inode->i_flags & EXT4_EXTENTS_FL)
3adb9374 TT	487	retval = ext2fs_punch_extent(fs, ino, inode, start, end);
	488	else {
	489	blk_t count;
	490
	491	if (start > ~0U)
	492	return 0;
4c6fd9c2 DW	493	if (end > ~0U)
4c6fd9c2 DW	494	end = ~0U;
4ee4ad80	495	count = ((end - start + 1) < ~0U) ? (end - start + 1) : ~0U;
3adb9374 TT	496	retval = ext2fs_punch_ind(fs, inode, block_buf,
	497	(blk_t) start, count);
	498	}
	499	if (retval)
	500	return retval;
	501
	502	return ext2fs_write_inode(fs, ino, inode);
	503	}