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.
26 * This function returns 1 if the specified block is all zeros
28 static int check_zero_block(char *buf, int blocksize)
42 * This clever recursive function handles i_blocks[] as well as
43 * indirect, double indirect, and triple indirect blocks. It iterates
44 * over the entries in the i_blocks array or indirect blocks, and for
45 * each one, will recursively handle any indirect blocks and then
46 * frees and deallocates the blocks.
48 static errcode_t ind_punch(ext2_filsys fs, struct ext2_inode *inode,
49 char *block_buf, blk_t *p, int level,
50 blk_t start, blk_t count, int max)
59 printf("Entering ind_punch, level %d, start %u, count %u, "
60 "max %d\n", level, start, count, max);
62 incr = 1ULL << ((EXT2_BLOCK_SIZE_BITS(fs->super)-2)*level);
63 for (i=0, offset=0; i < max; i++, p++, offset += incr) {
64 if (offset >= start + count)
66 if (*p == 0 || (offset+incr) <= start)
72 printf("Reading indirect block %u\n", b);
74 retval = ext2fs_read_ind_block(fs, b, block_buf);
77 start2 = (start > offset) ? start - offset : 0;
78 retval = ind_punch(fs, inode, block_buf + fs->blocksize,
79 (blk_t *) block_buf, level - 1,
80 start2, count - offset,
84 retval = ext2fs_write_ind_block(fs, b, block_buf);
87 if (!check_zero_block(block_buf, fs->blocksize))
91 printf("Freeing block %u (offset %llu)\n", b, offset);
93 ext2fs_block_alloc_stats(fs, b, -1);
98 printf("Freed %d blocks\n", freed);
100 return ext2fs_iblk_sub_blocks(fs, inode, freed);
103 static errcode_t ext2fs_punch_ind(ext2_filsys fs, struct ext2_inode *inode,
104 char *block_buf, blk_t start, blk_t count)
109 int num = EXT2_NDIR_BLOCKS;
110 blk_t *bp = inode->i_block;
111 blk_t addr_per_block;
112 blk64_t max = EXT2_NDIR_BLOCKS;
115 retval = ext2fs_get_array(3, fs->blocksize, &buf);
121 addr_per_block = (blk_t) fs->blocksize >> 2;
123 for (level = 0; level < 4; level++, max *= (blk64_t)addr_per_block) {
125 printf("Main loop level %d, start %u count %u "
126 "max %llu num %d\n", level, start, count, max, num);
129 retval = ind_punch(fs, inode, block_buf, bp, level,
134 count -= max - start;
149 ext2fs_free_mem(&buf);
155 #define dbg_printf(f, a...) printf(f, ## a)
157 static void dbg_print_extent(char *desc, struct ext2fs_extent *extent)
160 printf("%s: ", desc);
161 printf("extent: lblk %llu--%llu, len %u, pblk %llu, flags: ",
162 extent->e_lblk, extent->e_lblk + extent->e_len - 1,
163 extent->e_len, extent->e_pblk);
164 if (extent->e_flags & EXT2_EXTENT_FLAGS_LEAF)
165 fputs("LEAF ", stdout);
166 if (extent->e_flags & EXT2_EXTENT_FLAGS_UNINIT)
167 fputs("UNINIT ", stdout);
168 if (extent->e_flags & EXT2_EXTENT_FLAGS_SECOND_VISIT)
169 fputs("2ND_VISIT ", stdout);
170 if (!extent->e_flags)
171 fputs("(none)", stdout);
176 #define dbg_print_extent(desc, ex) do { } while (0)
177 #define dbg_printf(f, a...) do { } while (0)
180 /* Free a range of blocks, respecting cluster boundaries */
181 static errcode_t punch_extent_blocks(ext2_filsys fs, ext2_ino_t ino,
182 struct ext2_inode *inode,
183 blk64_t lfree_start, blk64_t free_start,
184 __u32 free_count, int *freed)
189 errcode_t retval = 0;
191 /* No bigalloc? Just free each block. */
192 if (EXT2FS_CLUSTER_RATIO(fs) == 1) {
193 *freed += free_count;
194 while (free_count-- > 0)
195 ext2fs_block_alloc_stats2(fs, free_start++, -1);
200 * Try to free up to the next cluster boundary. We assume that all
201 * blocks in a logical cluster map to blocks from the same physical
202 * cluster, and that the offsets within the [pl]clusters match.
204 if (free_start & EXT2FS_CLUSTER_MASK(fs)) {
205 retval = ext2fs_map_cluster_block(fs, ino, inode,
210 ext2fs_block_alloc_stats2(fs, free_start, -1);
213 cluster_freed = EXT2FS_CLUSTER_RATIO(fs) -
214 (free_start & EXT2FS_CLUSTER_MASK(fs));
215 if (cluster_freed > free_count)
216 cluster_freed = free_count;
217 free_count -= cluster_freed;
218 free_start += cluster_freed;
219 lfree_start += cluster_freed;
222 /* Free whole clusters from the middle of the range. */
223 while (free_count > 0 && free_count >= EXT2FS_CLUSTER_RATIO(fs)) {
224 ext2fs_block_alloc_stats2(fs, free_start, -1);
226 cluster_freed = EXT2FS_CLUSTER_RATIO(fs);
227 free_count -= cluster_freed;
228 free_start += cluster_freed;
229 lfree_start += cluster_freed;
232 /* Try to free the last cluster. */
233 if (free_count > 0) {
234 retval = ext2fs_map_cluster_block(fs, ino, inode,
239 ext2fs_block_alloc_stats2(fs, free_start, -1);
249 static errcode_t ext2fs_punch_extent(ext2_filsys fs, ext2_ino_t ino,
250 struct ext2_inode *inode,
251 blk64_t start, blk64_t end)
253 ext2_extent_handle_t handle = 0;
254 struct ext2fs_extent extent;
256 blk64_t free_start, next, lfree_start;
257 __u32 free_count, newlen;
261 retval = ext2fs_extent_open2(fs, ino, inode, &handle);
265 * Find the extent closest to the start of the punch range. We don't
266 * check the return value because _goto() sets the current node to the
267 * next-lowest extent if 'start' is in a hole, and doesn't set a
268 * current node if there was a real error reading the extent tree.
269 * In that case, _get() will error out.
271 * Note: If _get() returns 'no current node', that simply means that
272 * there aren't any blocks mapped past this point in the file, so we're
275 ext2fs_extent_goto(handle, start);
276 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
277 if (retval == EXT2_ET_NO_CURRENT_NODE) {
283 op = EXT2_EXTENT_NEXT_LEAF;
284 dbg_print_extent("main loop", &extent);
285 next = extent.e_lblk + extent.e_len;
286 dbg_printf("start %llu, end %llu, next %llu\n",
287 (unsigned long long) start,
288 (unsigned long long) end,
289 (unsigned long long) next);
290 if (start <= extent.e_lblk) {
292 * Have we iterated past the end of the punch region?
293 * If so, we can stop.
295 if (end < extent.e_lblk)
297 dbg_printf("Case #%d\n", 1);
298 /* Start of deleted region before extent;
299 adjust beginning of extent */
300 free_start = extent.e_pblk;
301 lfree_start = extent.e_lblk;
303 free_count = end - extent.e_lblk + 1;
305 free_count = extent.e_len;
306 extent.e_len -= free_count;
307 extent.e_lblk += free_count;
308 extent.e_pblk += free_count;
309 } else if (end >= next-1) {
311 * Is the punch region beyond this extent? This can
312 * happen if start is already inside a hole. Try to
313 * advance to the next extent if this is the case.
317 /* End of deleted region after extent;
318 adjust end of extent */
319 dbg_printf("Case #%d\n", 2);
320 newlen = start - extent.e_lblk;
321 free_start = extent.e_pblk + newlen;
322 lfree_start = extent.e_lblk + newlen;
323 free_count = extent.e_len - newlen;
324 extent.e_len = newlen;
326 struct ext2fs_extent newex;
328 dbg_printf("Case #%d\n", 3);
329 /* The hard case; we need to split the extent */
330 newex.e_pblk = extent.e_pblk +
331 (end + 1 - extent.e_lblk);
332 newex.e_lblk = end + 1;
333 newex.e_len = next - end - 1;
334 newex.e_flags = extent.e_flags;
336 extent.e_len = start - extent.e_lblk;
337 free_start = extent.e_pblk + extent.e_len;
338 lfree_start = extent.e_lblk + extent.e_len;
339 free_count = end - start + 1;
341 dbg_print_extent("inserting", &newex);
342 retval = ext2fs_extent_insert(handle,
343 EXT2_EXTENT_INSERT_AFTER, &newex);
346 /* Now pointing at inserted extent; so go back */
347 retval = ext2fs_extent_get(handle,
348 EXT2_EXTENT_PREV_LEAF,
354 dbg_print_extent("replacing", &extent);
355 retval = ext2fs_extent_replace(handle, 0, &extent);
358 retval = ext2fs_extent_fix_parents(handle);
360 struct ext2fs_extent newex;
361 blk64_t old_lblk, next_lblk;
362 dbg_printf("deleting current extent%s\n", "");
365 * Save the location of the next leaf, then slip
366 * back to the current extent.
368 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT,
372 old_lblk = newex.e_lblk;
374 retval = ext2fs_extent_get(handle,
375 EXT2_EXTENT_NEXT_LEAF,
377 if (retval == EXT2_ET_EXTENT_NO_NEXT)
378 next_lblk = old_lblk;
382 next_lblk = newex.e_lblk;
384 retval = ext2fs_extent_goto(handle, old_lblk);
388 /* Now delete the extent. */
389 retval = ext2fs_extent_delete(handle, 0);
393 retval = ext2fs_extent_fix_parents(handle);
394 if (retval && retval != EXT2_ET_NO_CURRENT_NODE)
398 /* Jump forward to the next extent. */
399 ext2fs_extent_goto(handle, next_lblk);
400 op = EXT2_EXTENT_CURRENT;
404 dbg_printf("Free start %llu, free count = %u\n",
405 free_start, free_count);
406 retval = punch_extent_blocks(fs, ino, inode, lfree_start,
407 free_start, free_count, &freed);
411 retval = ext2fs_extent_get(handle, op,
413 if (retval == EXT2_ET_EXTENT_NO_NEXT ||
414 retval == EXT2_ET_NO_CURRENT_NODE)
419 dbg_printf("Freed %d blocks\n", freed);
420 retval = ext2fs_iblk_sub_blocks(fs, inode, freed);
422 ext2fs_extent_free(handle);
427 * Deallocate all logical blocks starting at start to end, inclusive.
428 * If end is ~0, then this is effectively truncate.
430 errcode_t ext2fs_punch(ext2_filsys fs, ext2_ino_t ino,
431 struct ext2_inode *inode,
432 char *block_buf, blk64_t start,
436 struct ext2_inode inode_buf;
441 /* Read inode structure if necessary */
443 retval = ext2fs_read_inode(fs, ino, &inode_buf);
448 if (inode->i_flags & EXT4_EXTENTS_FL)
449 retval = ext2fs_punch_extent(fs, ino, inode, start, end);
457 count = ((end - start + 1) < ~0U) ? (end - start + 1) : ~0U;
458 retval = ext2fs_punch_ind(fs, inode, block_buf,
459 (blk_t) start, count);
464 return ext2fs_write_inode(fs, ino, inode);