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
12 #include "config.h"
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"
22 #include "ext2fsP.h"
23
24 #undef PUNCH_DEBUG
25
26 /*
27 * This function returns 1 if the specified block is all zeros
28 */
check_zero_block(char * buf,int blocksize)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 */
ind_punch(ext2_filsys fs,struct ext2_inode * inode,char * block_buf,blk_t * p,int level,blk64_t start,blk64_t count,int max)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)
52 {
53 errcode_t retval;
54 blk_t b;
55 int i;
56 blk64_t offset, incr;
57 int freed = 0;
58
59 #ifdef PUNCH_DEBUG
60 printf("Entering ind_punch, level %d, start %llu, count %llu, "
61 "max %d\n", level, start, count, max);
62 #endif
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)
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
92 printf("Freeing block %u (offset %llu)\n", b, offset);
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 #define BLK_T_MAX ((blk_t)~0ULL)
ext2fs_punch_ind(ext2_filsys fs,struct ext2_inode * inode,char * block_buf,blk64_t start,blk64_t end)105 static errcode_t ext2fs_punch_ind(ext2_filsys fs, struct ext2_inode *inode,
106 char *block_buf, blk64_t start, blk64_t end)
107 {
108 errcode_t retval;
109 char *buf = 0;
110 int level;
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;
115 blk_t count;
116
117 /* Check start/end don't overflow the 2^32-1 indirect block limit */
118 if (start > BLK_T_MAX)
119 return 0;
120 if (end >= BLK_T_MAX || end - start + 1 >= BLK_T_MAX)
121 count = BLK_T_MAX - start;
122 else
123 count = end - start + 1;
124
125 if (!block_buf) {
126 retval = ext2fs_get_array(3, fs->blocksize, &buf);
127 if (retval)
128 return retval;
129 block_buf = buf;
130 }
131
132 addr_per_block = (blk_t)fs->blocksize >> 2;
133
134 for (level = 0; level < 4; level++, max *= (blk64_t)addr_per_block) {
135 #ifdef PUNCH_DEBUG
136 printf("Main loop level %d, start %llu count %u "
137 "max %llu num %d\n", level, start, count, max, num);
138 #endif
139 if (start < max) {
140 retval = ind_punch(fs, inode, block_buf, bp, level,
141 start, count, num);
142 if (retval)
143 goto errout;
144 if (count > max)
145 count -= max - start;
146 else
147 break;
148 start = 0;
149 } else
150 start -= max;
151 bp += num;
152 if (level == 0) {
153 num = 1;
154 max = 1;
155 }
156 }
157 retval = 0;
158 errout:
159 if (buf)
160 ext2fs_free_mem(&buf);
161 return retval;
162 }
163 #undef BLK_T_MAX
164
165 #ifdef PUNCH_DEBUG
166
167 #define dbg_printf(f, a...) printf(f, ## a)
168
dbg_print_extent(char * desc,struct ext2fs_extent * extent)169 static void dbg_print_extent(char *desc, struct ext2fs_extent *extent)
170 {
171 if (desc)
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);
184 fputc('\n', stdout);
185
186 }
187 #else
188 #define dbg_print_extent(desc, ex) do { } while (0)
189 #define dbg_printf(f, a...) do { } while (0)
190 #endif
191
192 /* Free a range of blocks, respecting cluster boundaries */
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)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)
197 {
198 blk64_t pblk;
199 int freed_now = 0;
200 __u32 cluster_freed;
201 errcode_t retval = 0;
202
203 if (free_start < fs->super->s_first_data_block ||
204 (free_start + free_count) >= ext2fs_blocks_count(fs->super))
205 return EXT2_ET_BAD_BLOCK_NUM;
206
207 /* No bigalloc? Just free each block. */
208 if (EXT2FS_CLUSTER_RATIO(fs) == 1) {
209 *freed += free_count;
210 while (free_count-- > 0)
211 ext2fs_block_alloc_stats2(fs, free_start++, -1);
212 return retval;
213 }
214
215 /*
216 * Try to free up to the next cluster boundary. We assume that all
217 * blocks in a logical cluster map to blocks from the same physical
218 * cluster, and that the offsets within the [pl]clusters match.
219 */
220 if (free_start & EXT2FS_CLUSTER_MASK(fs)) {
221 retval = ext2fs_map_cluster_block(fs, ino, inode,
222 lfree_start, &pblk);
223 if (retval)
224 goto errout;
225 if (!pblk) {
226 ext2fs_block_alloc_stats2(fs, free_start, -1);
227 freed_now++;
228 }
229 cluster_freed = EXT2FS_CLUSTER_RATIO(fs) -
230 (free_start & EXT2FS_CLUSTER_MASK(fs));
231 if (cluster_freed > free_count)
232 cluster_freed = free_count;
233 free_count -= cluster_freed;
234 free_start += cluster_freed;
235 lfree_start += cluster_freed;
236 }
237
238 /* Free whole clusters from the middle of the range. */
239 while (free_count > 0 && free_count >= (unsigned) EXT2FS_CLUSTER_RATIO(fs)) {
240 ext2fs_block_alloc_stats2(fs, free_start, -1);
241 freed_now++;
242 cluster_freed = EXT2FS_CLUSTER_RATIO(fs);
243 free_count -= cluster_freed;
244 free_start += cluster_freed;
245 lfree_start += cluster_freed;
246 }
247
248 /* Try to free the last cluster. */
249 if (free_count > 0) {
250 retval = ext2fs_map_cluster_block(fs, ino, inode,
251 lfree_start, &pblk);
252 if (retval)
253 goto errout;
254 if (!pblk) {
255 ext2fs_block_alloc_stats2(fs, free_start, -1);
256 freed_now++;
257 }
258 }
259
260 errout:
261 *freed += freed_now;
262 return retval;
263 }
264
ext2fs_punch_extent(ext2_filsys fs,ext2_ino_t ino,struct ext2_inode * inode,blk64_t start,blk64_t end)265 static errcode_t ext2fs_punch_extent(ext2_filsys fs, ext2_ino_t ino,
266 struct ext2_inode *inode,
267 blk64_t start, blk64_t end)
268 {
269 ext2_extent_handle_t handle = 0;
270 struct ext2fs_extent extent;
271 errcode_t retval;
272 blk64_t free_start, next, lfree_start;
273 __u32 free_count, newlen;
274 int freed = 0;
275 int op;
276
277 retval = ext2fs_extent_open2(fs, ino, inode, &handle);
278 if (retval)
279 return retval;
280 /*
281 * Find the extent closest to the start of the punch range. We don't
282 * check the return value because _goto() sets the current node to the
283 * next-lowest extent if 'start' is in a hole, and doesn't set a
284 * current node if there was a real error reading the extent tree.
285 * In that case, _get() will error out.
286 *
287 * Note: If _get() returns 'no current node', that simply means that
288 * there aren't any blocks mapped past this point in the file, so we're
289 * done.
290 */
291 ext2fs_extent_goto(handle, start);
292 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
293 if (retval == EXT2_ET_NO_CURRENT_NODE) {
294 retval = 0;
295 goto errout;
296 } else if (retval)
297 goto errout;
298 while (1) {
299 op = EXT2_EXTENT_NEXT_LEAF;
300 dbg_print_extent("main loop", &extent);
301 next = extent.e_lblk + extent.e_len;
302 dbg_printf("start %llu, end %llu, next %llu\n",
303 (unsigned long long) start,
304 (unsigned long long) end,
305 (unsigned long long) next);
306 if (start <= extent.e_lblk) {
307 /*
308 * Have we iterated past the end of the punch region?
309 * If so, we can stop.
310 */
311 if (end < extent.e_lblk)
312 break;
313 dbg_printf("Case #%d\n", 1);
314 /* Start of deleted region before extent;
315 adjust beginning of extent */
316 free_start = extent.e_pblk;
317 lfree_start = extent.e_lblk;
318 if (next > end)
319 free_count = end - extent.e_lblk + 1;
320 else
321 free_count = extent.e_len;
322 extent.e_len -= free_count;
323 extent.e_lblk += free_count;
324 extent.e_pblk += free_count;
325 } else if (end >= next-1) {
326 /*
327 * Is the punch region beyond this extent? This can
328 * happen if start is already inside a hole. Try to
329 * advance to the next extent if this is the case.
330 */
331 if (start >= next)
332 goto next_extent;
333 /* End of deleted region after extent;
334 adjust end of extent */
335 dbg_printf("Case #%d\n", 2);
336 newlen = start - extent.e_lblk;
337 free_start = extent.e_pblk + newlen;
338 lfree_start = extent.e_lblk + newlen;
339 free_count = extent.e_len - newlen;
340 extent.e_len = newlen;
341 } else {
342 struct ext2fs_extent newex;
343
344 dbg_printf("Case #%d\n", 3);
345 /* The hard case; we need to split the extent */
346 newex.e_pblk = extent.e_pblk +
347 (end + 1 - extent.e_lblk);
348 newex.e_lblk = end + 1;
349 newex.e_len = next - end - 1;
350 newex.e_flags = extent.e_flags;
351
352 extent.e_len = start - extent.e_lblk;
353 free_start = extent.e_pblk + extent.e_len;
354 lfree_start = extent.e_lblk + extent.e_len;
355 free_count = end - start + 1;
356
357 dbg_print_extent("inserting", &newex);
358 retval = ext2fs_extent_insert(handle,
359 EXT2_EXTENT_INSERT_AFTER, &newex);
360 if (retval)
361 goto errout;
362 retval = ext2fs_extent_fix_parents(handle);
363 if (retval)
364 goto errout;
365 /*
366 * Now pointing at inserted extent; so go back.
367 *
368 * We cannot use EXT2_EXTENT_PREV to go back; note the
369 * subtlety in the comment for fix_parents().
370 */
371 retval = ext2fs_extent_goto(handle, extent.e_lblk);
372 if (retval)
373 goto errout;
374 }
375 if (extent.e_len) {
376 dbg_print_extent("replacing", &extent);
377 retval = ext2fs_extent_replace(handle, 0, &extent);
378 if (retval)
379 goto errout;
380 retval = ext2fs_extent_fix_parents(handle);
381 } else {
382 struct ext2fs_extent newex;
383 blk64_t old_lblk, next_lblk;
384 dbg_printf("deleting current extent%s\n", "");
385
386 /*
387 * Save the location of the next leaf, then slip
388 * back to the current extent.
389 */
390 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT,
391 &newex);
392 if (retval)
393 goto errout;
394 old_lblk = newex.e_lblk;
395
396 retval = ext2fs_extent_get(handle,
397 EXT2_EXTENT_NEXT_LEAF,
398 &newex);
399 if (retval == EXT2_ET_EXTENT_NO_NEXT)
400 next_lblk = old_lblk;
401 else if (retval)
402 goto errout;
403 else
404 next_lblk = newex.e_lblk;
405
406 retval = ext2fs_extent_goto(handle, old_lblk);
407 if (retval)
408 goto errout;
409
410 /* Now delete the extent. */
411 retval = ext2fs_extent_delete(handle, 0);
412 if (retval)
413 goto errout;
414
415 retval = ext2fs_extent_fix_parents(handle);
416 if (retval && retval != EXT2_ET_NO_CURRENT_NODE)
417 goto errout;
418 retval = 0;
419
420 /*
421 * Jump forward to the next extent. If there are
422 * errors, the ext2fs_extent_get down below will
423 * capture them for us.
424 */
425 (void)ext2fs_extent_goto(handle, next_lblk);
426 op = EXT2_EXTENT_CURRENT;
427 }
428 if (retval)
429 goto errout;
430 dbg_printf("Free start %llu, free count = %u\n",
431 free_start, free_count);
432 retval = punch_extent_blocks(fs, ino, inode, lfree_start,
433 free_start, free_count, &freed);
434 if (retval)
435 goto errout;
436 next_extent:
437 retval = ext2fs_extent_get(handle, op,
438 &extent);
439 if (retval == EXT2_ET_EXTENT_NO_NEXT ||
440 retval == EXT2_ET_NO_CURRENT_NODE)
441 break;
442 if (retval)
443 goto errout;
444 }
445 dbg_printf("Freed %d blocks\n", freed);
446 retval = ext2fs_iblk_sub_blocks(fs, inode, freed);
447 errout:
448 ext2fs_extent_free(handle);
449 return retval;
450 }
451
ext2fs_punch_inline_data(ext2_filsys fs,ext2_ino_t ino,struct ext2_inode * inode,blk64_t start,blk64_t end EXT2FS_ATTR ((unused)))452 static errcode_t ext2fs_punch_inline_data(ext2_filsys fs, ext2_ino_t ino,
453 struct ext2_inode *inode,
454 blk64_t start,
455 blk64_t end EXT2FS_ATTR((unused)))
456 {
457 errcode_t retval;
458
459 /*
460 * In libext2fs ext2fs_punch is based on block unit. So that
461 * means that if start > 0 we don't need to do nothing. Due
462 * to this we will remove all inline data in ext2fs_punch()
463 * now.
464 */
465 if (start > 0)
466 return 0;
467
468 memset((char *)inode->i_block, 0, EXT4_MIN_INLINE_DATA_SIZE);
469 inode->i_size = 0;
470 retval = ext2fs_write_inode(fs, ino, inode);
471 if (retval)
472 return retval;
473
474 return ext2fs_inline_data_ea_remove(fs, ino);
475 }
476
477 /*
478 * Deallocate all logical _blocks_ starting at start to end, inclusive.
479 * If end is ~0ULL, then this is effectively truncate.
480 */
ext2fs_punch(ext2_filsys fs,ext2_ino_t ino,struct ext2_inode * inode,char * block_buf,blk64_t start,blk64_t end)481 errcode_t ext2fs_punch(ext2_filsys fs, ext2_ino_t ino,
482 struct ext2_inode *inode,
483 char *block_buf, blk64_t start,
484 blk64_t end)
485 {
486 errcode_t retval;
487 struct ext2_inode inode_buf;
488
489 if (start > end)
490 return EINVAL;
491
492 /* Read inode structure if necessary */
493 if (!inode) {
494 retval = ext2fs_read_inode(fs, ino, &inode_buf);
495 if (retval)
496 return retval;
497 inode = &inode_buf;
498 }
499 if (inode->i_flags & EXT4_INLINE_DATA_FL)
500 return ext2fs_punch_inline_data(fs, ino, inode, start, end);
501 else if (inode->i_flags & EXT4_EXTENTS_FL)
502 retval = ext2fs_punch_extent(fs, ino, inode, start, end);
503 else
504 retval = ext2fs_punch_ind(fs, inode, block_buf, start, end);
505 if (retval)
506 return retval;
507
508 #ifdef PUNCH_DEBUG
509 printf("%u: write inode size now %lu blocks %u\n",
510 ino, EXT2_I_SIZE(inode), inode->i_blocks);
511 #endif
512 return ext2fs_write_inode(fs, ino, inode);
513 }
514