2 * punch.c --- deallocate blocks allocated to an inode
4 * Copyright (C) 2010 Theodore Ts'o.
7 * This file may be redistributed under the terms of the GNU Library
8 * General Public License, version 2.
27 * This function returns 1 if the specified block is all zeros
29 static int check_zero_block(char *buf, int blocksize)
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.
49 static errcode_t ind_punch(ext2_filsys fs, struct ext2_inode *inode,
50 char *block_buf, blk_t *p, int level,
51 blk64_t start, blk64_t count, int max)
60 printf("Entering ind_punch, level %d, start %llu, count %llu, "
61 "max %d\n", level, start, count, max);
63 incr = 1ULL << ((EXT2_BLOCK_SIZE_BITS(fs->super) - 2) * level);
64 for (i = 0, offset = 0; i < max; i++, p++, offset += incr) {
65 if (offset >= start + count)
67 if (*p == 0 || (offset+incr) <= start)
73 printf("Reading indirect block %u\n", b);
75 retval = ext2fs_read_ind_block(fs, b, block_buf);
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,
85 retval = ext2fs_write_ind_block(fs, b, block_buf);
88 if (!check_zero_block(block_buf, fs->blocksize))
92 printf("Freeing block %u (offset %llu)\n", b, offset);
94 ext2fs_block_alloc_stats(fs, b, -1);
99 printf("Freed %d blocks\n", freed);
101 return ext2fs_iblk_sub_blocks(fs, inode, freed);
104 #define BLK_T_MAX ((blk_t)~0ULL)
105 static errcode_t ext2fs_punch_ind(ext2_filsys fs, struct ext2_inode *inode,
106 char *block_buf, blk64_t start, blk64_t end)
111 int num = EXT2_NDIR_BLOCKS;
112 blk_t *bp = inode->i_block;
113 blk_t addr_per_block;
114 blk64_t max = EXT2_NDIR_BLOCKS;
117 /* Check start/end don't overflow the 2^32-1 indirect block limit */
118 if (start > BLK_T_MAX)
120 if (end >= BLK_T_MAX || end - start + 1 >= BLK_T_MAX)
121 count = BLK_T_MAX - start;
123 count = end - start + 1;
126 retval = ext2fs_get_array(3, fs->blocksize, &buf);
132 addr_per_block = (blk_t)fs->blocksize >> 2;
134 for (level = 0; level < 4; level++, max *= (blk64_t)addr_per_block) {
136 printf("Main loop level %d, start %llu count %u "
137 "max %llu num %d\n", level, start, count, max, num);
140 retval = ind_punch(fs, inode, block_buf, bp, level,
145 count -= max - start;
160 ext2fs_free_mem(&buf);
167 #define dbg_printf(f, a...) printf(f, ## a)
169 static void dbg_print_extent(char *desc, struct ext2fs_extent *extent)
172 printf("%s: ", desc);
173 printf("extent: lblk %llu--%llu, len %u, pblk %llu, flags: ",
174 extent->e_lblk, extent->e_lblk + extent->e_len - 1,
175 extent->e_len, extent->e_pblk);
176 if (extent->e_flags & EXT2_EXTENT_FLAGS_LEAF)
177 fputs("LEAF ", stdout);
178 if (extent->e_flags & EXT2_EXTENT_FLAGS_UNINIT)
179 fputs("UNINIT ", stdout);
180 if (extent->e_flags & EXT2_EXTENT_FLAGS_SECOND_VISIT)
181 fputs("2ND_VISIT ", stdout);
182 if (!extent->e_flags)
183 fputs("(none)", stdout);
188 #define dbg_print_extent(desc, ex) do { } while (0)
189 #define dbg_printf(f, a...) do { } while (0)
192 /* Free a range of blocks, respecting cluster boundaries */
193 static errcode_t punch_extent_blocks(ext2_filsys fs, ext2_ino_t ino,
194 struct ext2_inode *inode,
195 blk64_t lfree_start, blk64_t free_start,
196 __u32 free_count, int *freed)
201 errcode_t retval = 0;
203 /* No bigalloc? Just free each block. */
204 if (EXT2FS_CLUSTER_RATIO(fs) == 1) {
205 *freed += free_count;
206 while (free_count-- > 0)
207 ext2fs_block_alloc_stats2(fs, free_start++, -1);
212 * Try to free up to the next cluster boundary. We assume that all
213 * blocks in a logical cluster map to blocks from the same physical
214 * cluster, and that the offsets within the [pl]clusters match.
216 if (free_start & EXT2FS_CLUSTER_MASK(fs)) {
217 retval = ext2fs_map_cluster_block(fs, ino, inode,
222 ext2fs_block_alloc_stats2(fs, free_start, -1);
225 cluster_freed = EXT2FS_CLUSTER_RATIO(fs) -
226 (free_start & EXT2FS_CLUSTER_MASK(fs));
227 if (cluster_freed > free_count)
228 cluster_freed = free_count;
229 free_count -= cluster_freed;
230 free_start += cluster_freed;
231 lfree_start += cluster_freed;
234 /* Free whole clusters from the middle of the range. */
235 while (free_count > 0 && free_count >= (unsigned) EXT2FS_CLUSTER_RATIO(fs)) {
236 ext2fs_block_alloc_stats2(fs, free_start, -1);
238 cluster_freed = EXT2FS_CLUSTER_RATIO(fs);
239 free_count -= cluster_freed;
240 free_start += cluster_freed;
241 lfree_start += cluster_freed;
244 /* Try to free the last cluster. */
245 if (free_count > 0) {
246 retval = ext2fs_map_cluster_block(fs, ino, inode,
251 ext2fs_block_alloc_stats2(fs, free_start, -1);
261 static errcode_t ext2fs_punch_extent(ext2_filsys fs, ext2_ino_t ino,
262 struct ext2_inode *inode,
263 blk64_t start, blk64_t end)
265 ext2_extent_handle_t handle = 0;
266 struct ext2fs_extent extent;
268 blk64_t free_start, next, lfree_start;
269 __u32 free_count, newlen;
273 retval = ext2fs_extent_open2(fs, ino, inode, &handle);
277 * Find the extent closest to the start of the punch range. We don't
278 * check the return value because _goto() sets the current node to the
279 * next-lowest extent if 'start' is in a hole, and doesn't set a
280 * current node if there was a real error reading the extent tree.
281 * In that case, _get() will error out.
283 * Note: If _get() returns 'no current node', that simply means that
284 * there aren't any blocks mapped past this point in the file, so we're
287 ext2fs_extent_goto(handle, start);
288 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
289 if (retval == EXT2_ET_NO_CURRENT_NODE) {
295 op = EXT2_EXTENT_NEXT_LEAF;
296 dbg_print_extent("main loop", &extent);
297 next = extent.e_lblk + extent.e_len;
298 dbg_printf("start %llu, end %llu, next %llu\n",
299 (unsigned long long) start,
300 (unsigned long long) end,
301 (unsigned long long) next);
302 if (start <= extent.e_lblk) {
304 * Have we iterated past the end of the punch region?
305 * If so, we can stop.
307 if (end < extent.e_lblk)
309 dbg_printf("Case #%d\n", 1);
310 /* Start of deleted region before extent;
311 adjust beginning of extent */
312 free_start = extent.e_pblk;
313 lfree_start = extent.e_lblk;
315 free_count = end - extent.e_lblk + 1;
317 free_count = extent.e_len;
318 extent.e_len -= free_count;
319 extent.e_lblk += free_count;
320 extent.e_pblk += free_count;
321 } else if (end >= next-1) {
323 * Is the punch region beyond this extent? This can
324 * happen if start is already inside a hole. Try to
325 * advance to the next extent if this is the case.
329 /* End of deleted region after extent;
330 adjust end of extent */
331 dbg_printf("Case #%d\n", 2);
332 newlen = start - extent.e_lblk;
333 free_start = extent.e_pblk + newlen;
334 lfree_start = extent.e_lblk + newlen;
335 free_count = extent.e_len - newlen;
336 extent.e_len = newlen;
338 struct ext2fs_extent newex;
340 dbg_printf("Case #%d\n", 3);
341 /* The hard case; we need to split the extent */
342 newex.e_pblk = extent.e_pblk +
343 (end + 1 - extent.e_lblk);
344 newex.e_lblk = end + 1;
345 newex.e_len = next - end - 1;
346 newex.e_flags = extent.e_flags;
348 extent.e_len = start - extent.e_lblk;
349 free_start = extent.e_pblk + extent.e_len;
350 lfree_start = extent.e_lblk + extent.e_len;
351 free_count = end - start + 1;
353 dbg_print_extent("inserting", &newex);
354 retval = ext2fs_extent_insert(handle,
355 EXT2_EXTENT_INSERT_AFTER, &newex);
358 retval = ext2fs_extent_fix_parents(handle);
362 * Now pointing at inserted extent; so go back.
364 * We cannot use EXT2_EXTENT_PREV to go back; note the
365 * subtlety in the comment for fix_parents().
367 retval = ext2fs_extent_goto(handle, extent.e_lblk);
372 dbg_print_extent("replacing", &extent);
373 retval = ext2fs_extent_replace(handle, 0, &extent);
376 retval = ext2fs_extent_fix_parents(handle);
378 struct ext2fs_extent newex;
379 blk64_t old_lblk, next_lblk;
380 dbg_printf("deleting current extent%s\n", "");
383 * Save the location of the next leaf, then slip
384 * back to the current extent.
386 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT,
390 old_lblk = newex.e_lblk;
392 retval = ext2fs_extent_get(handle,
393 EXT2_EXTENT_NEXT_LEAF,
395 if (retval == EXT2_ET_EXTENT_NO_NEXT)
396 next_lblk = old_lblk;
400 next_lblk = newex.e_lblk;
402 retval = ext2fs_extent_goto(handle, old_lblk);
406 /* Now delete the extent. */
407 retval = ext2fs_extent_delete(handle, 0);
411 retval = ext2fs_extent_fix_parents(handle);
412 if (retval && retval != EXT2_ET_NO_CURRENT_NODE)
417 * Jump forward to the next extent. If there are
418 * errors, the ext2fs_extent_get down below will
419 * capture them for us.
421 (void)ext2fs_extent_goto(handle, next_lblk);
422 op = EXT2_EXTENT_CURRENT;
426 dbg_printf("Free start %llu, free count = %u\n",
427 free_start, free_count);
428 retval = punch_extent_blocks(fs, ino, inode, lfree_start,
429 free_start, free_count, &freed);
433 retval = ext2fs_extent_get(handle, op,
435 if (retval == EXT2_ET_EXTENT_NO_NEXT ||
436 retval == EXT2_ET_NO_CURRENT_NODE)
441 dbg_printf("Freed %d blocks\n", freed);
442 retval = ext2fs_iblk_sub_blocks(fs, inode, freed);
444 ext2fs_extent_free(handle);
448 static errcode_t ext2fs_punch_inline_data(ext2_filsys fs, ext2_ino_t ino,
449 struct ext2_inode *inode,
451 blk64_t end EXT2FS_ATTR((unused)))
456 * In libext2fs ext2fs_punch is based on block unit. So that
457 * means that if start > 0 we don't need to do nothing. Due
458 * to this we will remove all inline data in ext2fs_punch()
464 memset((char *)inode->i_block, 0, EXT4_MIN_INLINE_DATA_SIZE);
466 retval = ext2fs_write_inode(fs, ino, inode);
470 return ext2fs_inline_data_ea_remove(fs, ino);
474 * Deallocate all logical _blocks_ starting at start to end, inclusive.
475 * If end is ~0ULL, then this is effectively truncate.
477 errcode_t ext2fs_punch(ext2_filsys fs, ext2_ino_t ino,
478 struct ext2_inode *inode,
479 char *block_buf, blk64_t start,
483 struct ext2_inode inode_buf;
488 /* Read inode structure if necessary */
490 retval = ext2fs_read_inode(fs, ino, &inode_buf);
495 if (inode->i_flags & EXT4_INLINE_DATA_FL)
496 return ext2fs_punch_inline_data(fs, ino, inode, start, end);
497 else if (inode->i_flags & EXT4_EXTENTS_FL)
498 retval = ext2fs_punch_extent(fs, ino, inode, start, end);
500 retval = ext2fs_punch_ind(fs, inode, block_buf, start, end);
505 printf("%u: write inode size now %u blocks %u\n",
506 ino, inode->i_size, inode->i_blocks);
508 return ext2fs_write_inode(fs, ino, inode);