/src/e2fsprogs/lib/ext2fs/punch.c
Line | Count | Source (jump to first uncovered line) |
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 | | */ |
29 | | static int check_zero_block(char *buf, int blocksize) |
30 | 0 | { |
31 | 0 | char *cp = buf; |
32 | 0 | int left = blocksize; |
33 | |
|
34 | 0 | while (left > 0) { |
35 | 0 | if (*cp++) |
36 | 0 | return 0; |
37 | 0 | left--; |
38 | 0 | } |
39 | 0 | return 1; |
40 | 0 | } |
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 | | blk64_t start, blk64_t count, int max) |
52 | 0 | { |
53 | 0 | errcode_t retval; |
54 | 0 | blk_t b; |
55 | 0 | int i; |
56 | 0 | blk64_t offset, incr; |
57 | 0 | 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 | 0 | incr = 1ULL << ((EXT2_BLOCK_SIZE_BITS(fs->super) - 2) * level); |
64 | 0 | for (i = 0, offset = 0; i < max; i++, p++, offset += incr) { |
65 | 0 | if (offset >= start + count) |
66 | 0 | break; |
67 | 0 | if (*p == 0 || (offset+incr) <= start) |
68 | 0 | continue; |
69 | 0 | b = *p; |
70 | 0 | if (level > 0) { |
71 | 0 | blk_t start2; |
72 | | #ifdef PUNCH_DEBUG |
73 | | printf("Reading indirect block %u\n", b); |
74 | | #endif |
75 | 0 | retval = ext2fs_read_ind_block(fs, b, block_buf); |
76 | 0 | if (retval) |
77 | 0 | return retval; |
78 | 0 | start2 = (start > offset) ? start - offset : 0; |
79 | 0 | retval = ind_punch(fs, inode, block_buf + fs->blocksize, |
80 | 0 | (blk_t *) block_buf, level - 1, |
81 | 0 | start2, count - offset, |
82 | 0 | fs->blocksize >> 2); |
83 | 0 | if (retval) |
84 | 0 | return retval; |
85 | 0 | retval = ext2fs_write_ind_block(fs, b, block_buf); |
86 | 0 | if (retval) |
87 | 0 | return retval; |
88 | 0 | if (!check_zero_block(block_buf, fs->blocksize)) |
89 | 0 | continue; |
90 | 0 | } |
91 | | #ifdef PUNCH_DEBUG |
92 | | printf("Freeing block %u (offset %llu)\n", b, offset); |
93 | | #endif |
94 | 0 | ext2fs_block_alloc_stats(fs, b, -1); |
95 | 0 | *p = 0; |
96 | 0 | freed++; |
97 | 0 | } |
98 | | #ifdef PUNCH_DEBUG |
99 | | printf("Freed %d blocks\n", freed); |
100 | | #endif |
101 | 0 | return ext2fs_iblk_sub_blocks(fs, inode, freed); |
102 | 0 | } |
103 | | |
104 | 0 | #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) |
107 | 0 | { |
108 | 0 | errcode_t retval; |
109 | 0 | char *buf = 0; |
110 | 0 | int level; |
111 | 0 | int num = EXT2_NDIR_BLOCKS; |
112 | 0 | blk_t *bp = inode->i_block; |
113 | 0 | blk_t addr_per_block; |
114 | 0 | blk64_t max = EXT2_NDIR_BLOCKS; |
115 | 0 | blk_t count; |
116 | | |
117 | | /* Check start/end don't overflow the 2^32-1 indirect block limit */ |
118 | 0 | if (start > BLK_T_MAX) |
119 | 0 | return 0; |
120 | 0 | if (end >= BLK_T_MAX || end - start + 1 >= BLK_T_MAX) |
121 | 0 | count = BLK_T_MAX - start; |
122 | 0 | else |
123 | 0 | count = end - start + 1; |
124 | |
|
125 | 0 | if (!block_buf) { |
126 | 0 | retval = ext2fs_get_array(3, fs->blocksize, &buf); |
127 | 0 | if (retval) |
128 | 0 | return retval; |
129 | 0 | block_buf = buf; |
130 | 0 | } |
131 | | |
132 | 0 | addr_per_block = (blk_t)fs->blocksize >> 2; |
133 | |
|
134 | 0 | 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 | 0 | if (start < max) { |
140 | 0 | retval = ind_punch(fs, inode, block_buf, bp, level, |
141 | 0 | start, count, num); |
142 | 0 | if (retval) |
143 | 0 | goto errout; |
144 | 0 | if (count > max) |
145 | 0 | count -= max - start; |
146 | 0 | else |
147 | 0 | break; |
148 | 0 | start = 0; |
149 | 0 | } else |
150 | 0 | start -= max; |
151 | 0 | bp += num; |
152 | 0 | if (level == 0) { |
153 | 0 | num = 1; |
154 | 0 | max = 1; |
155 | 0 | } |
156 | 0 | } |
157 | 0 | retval = 0; |
158 | 0 | errout: |
159 | 0 | if (buf) |
160 | 0 | ext2fs_free_mem(&buf); |
161 | 0 | return retval; |
162 | 0 | } |
163 | | #undef BLK_T_MAX |
164 | | |
165 | | #ifdef PUNCH_DEBUG |
166 | | |
167 | | #define dbg_printf(f, a...) printf(f, ## a) |
168 | | |
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 | 0 | #define dbg_print_extent(desc, ex) do { } while (0) |
189 | 0 | #define dbg_printf(f, a...) do { } while (0) |
190 | | #endif |
191 | | |
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) |
197 | 0 | { |
198 | 0 | blk64_t pblk; |
199 | 0 | int freed_now = 0; |
200 | 0 | __u32 cluster_freed; |
201 | 0 | errcode_t retval = 0; |
202 | |
|
203 | 0 | if (free_start < fs->super->s_first_data_block || |
204 | 0 | (free_start + free_count) >= ext2fs_blocks_count(fs->super)) |
205 | 0 | return EXT2_ET_BAD_BLOCK_NUM; |
206 | | |
207 | | /* No bigalloc? Just free each block. */ |
208 | 0 | if (EXT2FS_CLUSTER_RATIO(fs) == 1) { |
209 | 0 | *freed += free_count; |
210 | 0 | while (free_count-- > 0) |
211 | 0 | ext2fs_block_alloc_stats2(fs, free_start++, -1); |
212 | 0 | return retval; |
213 | 0 | } |
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 | 0 | if (free_start & EXT2FS_CLUSTER_MASK(fs)) { |
221 | 0 | retval = ext2fs_map_cluster_block(fs, ino, inode, |
222 | 0 | lfree_start, &pblk); |
223 | 0 | if (retval) |
224 | 0 | goto errout; |
225 | 0 | if (!pblk) { |
226 | 0 | ext2fs_block_alloc_stats2(fs, free_start, -1); |
227 | 0 | freed_now++; |
228 | 0 | } |
229 | 0 | cluster_freed = EXT2FS_CLUSTER_RATIO(fs) - |
230 | 0 | (free_start & EXT2FS_CLUSTER_MASK(fs)); |
231 | 0 | if (cluster_freed > free_count) |
232 | 0 | cluster_freed = free_count; |
233 | 0 | free_count -= cluster_freed; |
234 | 0 | free_start += cluster_freed; |
235 | 0 | lfree_start += cluster_freed; |
236 | 0 | } |
237 | | |
238 | | /* Free whole clusters from the middle of the range. */ |
239 | 0 | while (free_count > 0 && free_count >= (unsigned) EXT2FS_CLUSTER_RATIO(fs)) { |
240 | 0 | ext2fs_block_alloc_stats2(fs, free_start, -1); |
241 | 0 | freed_now++; |
242 | 0 | cluster_freed = EXT2FS_CLUSTER_RATIO(fs); |
243 | 0 | free_count -= cluster_freed; |
244 | 0 | free_start += cluster_freed; |
245 | 0 | lfree_start += cluster_freed; |
246 | 0 | } |
247 | | |
248 | | /* Try to free the last cluster. */ |
249 | 0 | if (free_count > 0) { |
250 | 0 | retval = ext2fs_map_cluster_block(fs, ino, inode, |
251 | 0 | lfree_start, &pblk); |
252 | 0 | if (retval) |
253 | 0 | goto errout; |
254 | 0 | if (!pblk) { |
255 | 0 | ext2fs_block_alloc_stats2(fs, free_start, -1); |
256 | 0 | freed_now++; |
257 | 0 | } |
258 | 0 | } |
259 | | |
260 | 0 | errout: |
261 | 0 | *freed += freed_now; |
262 | 0 | return retval; |
263 | 0 | } |
264 | | |
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 | 0 | { |
269 | 0 | ext2_extent_handle_t handle = 0; |
270 | 0 | struct ext2fs_extent extent; |
271 | 0 | errcode_t retval; |
272 | 0 | blk64_t free_start, next, lfree_start; |
273 | 0 | __u32 free_count, newlen; |
274 | 0 | int freed = 0; |
275 | 0 | int op; |
276 | |
|
277 | 0 | retval = ext2fs_extent_open2(fs, ino, inode, &handle); |
278 | 0 | if (retval) |
279 | 0 | 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 | 0 | ext2fs_extent_goto(handle, start); |
292 | 0 | retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent); |
293 | 0 | if (retval == EXT2_ET_NO_CURRENT_NODE) { |
294 | 0 | retval = 0; |
295 | 0 | goto errout; |
296 | 0 | } else if (retval) |
297 | 0 | goto errout; |
298 | 0 | while (1) { |
299 | 0 | op = EXT2_EXTENT_NEXT_LEAF; |
300 | 0 | dbg_print_extent("main loop", &extent); |
301 | 0 | next = extent.e_lblk + extent.e_len; |
302 | 0 | dbg_printf("start %llu, end %llu, next %llu\n", |
303 | 0 | (unsigned long long) start, |
304 | 0 | (unsigned long long) end, |
305 | 0 | (unsigned long long) next); |
306 | 0 | 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 | 0 | if (end < extent.e_lblk) |
312 | 0 | break; |
313 | 0 | dbg_printf("Case #%d\n", 1); |
314 | | /* Start of deleted region before extent; |
315 | | adjust beginning of extent */ |
316 | 0 | free_start = extent.e_pblk; |
317 | 0 | lfree_start = extent.e_lblk; |
318 | 0 | if (next > end) |
319 | 0 | free_count = end - extent.e_lblk + 1; |
320 | 0 | else |
321 | 0 | free_count = extent.e_len; |
322 | 0 | extent.e_len -= free_count; |
323 | 0 | extent.e_lblk += free_count; |
324 | 0 | extent.e_pblk += free_count; |
325 | 0 | } 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 | 0 | if (start >= next) |
332 | 0 | goto next_extent; |
333 | | /* End of deleted region after extent; |
334 | | adjust end of extent */ |
335 | 0 | dbg_printf("Case #%d\n", 2); |
336 | 0 | newlen = start - extent.e_lblk; |
337 | 0 | free_start = extent.e_pblk + newlen; |
338 | 0 | lfree_start = extent.e_lblk + newlen; |
339 | 0 | free_count = extent.e_len - newlen; |
340 | 0 | extent.e_len = newlen; |
341 | 0 | } else { |
342 | 0 | struct ext2fs_extent newex; |
343 | |
|
344 | 0 | dbg_printf("Case #%d\n", 3); |
345 | | /* The hard case; we need to split the extent */ |
346 | 0 | newex.e_pblk = extent.e_pblk + |
347 | 0 | (end + 1 - extent.e_lblk); |
348 | 0 | newex.e_lblk = end + 1; |
349 | 0 | newex.e_len = next - end - 1; |
350 | 0 | newex.e_flags = extent.e_flags; |
351 | |
|
352 | 0 | extent.e_len = start - extent.e_lblk; |
353 | 0 | free_start = extent.e_pblk + extent.e_len; |
354 | 0 | lfree_start = extent.e_lblk + extent.e_len; |
355 | 0 | free_count = end - start + 1; |
356 | |
|
357 | 0 | dbg_print_extent("inserting", &newex); |
358 | 0 | retval = ext2fs_extent_insert(handle, |
359 | 0 | EXT2_EXTENT_INSERT_AFTER, &newex); |
360 | 0 | if (retval) |
361 | 0 | goto errout; |
362 | 0 | retval = ext2fs_extent_fix_parents(handle); |
363 | 0 | if (retval) |
364 | 0 | 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 | 0 | retval = ext2fs_extent_goto(handle, extent.e_lblk); |
372 | 0 | if (retval) |
373 | 0 | goto errout; |
374 | 0 | } |
375 | 0 | if (extent.e_len) { |
376 | 0 | dbg_print_extent("replacing", &extent); |
377 | 0 | retval = ext2fs_extent_replace(handle, 0, &extent); |
378 | 0 | if (retval) |
379 | 0 | goto errout; |
380 | 0 | retval = ext2fs_extent_fix_parents(handle); |
381 | 0 | } else { |
382 | 0 | struct ext2fs_extent newex; |
383 | 0 | blk64_t old_lblk, next_lblk; |
384 | 0 | 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 | 0 | retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, |
391 | 0 | &newex); |
392 | 0 | if (retval) |
393 | 0 | goto errout; |
394 | 0 | old_lblk = newex.e_lblk; |
395 | |
|
396 | 0 | retval = ext2fs_extent_get(handle, |
397 | 0 | EXT2_EXTENT_NEXT_LEAF, |
398 | 0 | &newex); |
399 | 0 | if (retval == EXT2_ET_EXTENT_NO_NEXT) |
400 | 0 | next_lblk = old_lblk; |
401 | 0 | else if (retval) |
402 | 0 | goto errout; |
403 | 0 | else |
404 | 0 | next_lblk = newex.e_lblk; |
405 | | |
406 | 0 | retval = ext2fs_extent_goto(handle, old_lblk); |
407 | 0 | if (retval) |
408 | 0 | goto errout; |
409 | | |
410 | | /* Now delete the extent. */ |
411 | 0 | retval = ext2fs_extent_delete(handle, 0); |
412 | 0 | if (retval) |
413 | 0 | goto errout; |
414 | | |
415 | 0 | retval = ext2fs_extent_fix_parents(handle); |
416 | 0 | if (retval && retval != EXT2_ET_NO_CURRENT_NODE) |
417 | 0 | goto errout; |
418 | 0 | 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 | 0 | (void)ext2fs_extent_goto(handle, next_lblk); |
426 | 0 | op = EXT2_EXTENT_CURRENT; |
427 | 0 | } |
428 | 0 | if (retval) |
429 | 0 | goto errout; |
430 | 0 | dbg_printf("Free start %llu, free count = %u\n", |
431 | 0 | free_start, free_count); |
432 | 0 | retval = punch_extent_blocks(fs, ino, inode, lfree_start, |
433 | 0 | free_start, free_count, &freed); |
434 | 0 | if (retval) |
435 | 0 | goto errout; |
436 | 0 | next_extent: |
437 | 0 | retval = ext2fs_extent_get(handle, op, |
438 | 0 | &extent); |
439 | 0 | if (retval == EXT2_ET_EXTENT_NO_NEXT || |
440 | 0 | retval == EXT2_ET_NO_CURRENT_NODE) |
441 | 0 | break; |
442 | 0 | if (retval) |
443 | 0 | goto errout; |
444 | 0 | } |
445 | 0 | dbg_printf("Freed %d blocks\n", freed); |
446 | 0 | retval = ext2fs_iblk_sub_blocks(fs, inode, freed); |
447 | 0 | errout: |
448 | 0 | ext2fs_extent_free(handle); |
449 | 0 | return retval; |
450 | 0 | } |
451 | | |
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 | 0 | { |
457 | 0 | 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 | 0 | if (start > 0) |
466 | 0 | return 0; |
467 | | |
468 | 0 | memset((char *)inode->i_block, 0, EXT4_MIN_INLINE_DATA_SIZE); |
469 | 0 | inode->i_size = 0; |
470 | 0 | retval = ext2fs_write_inode(fs, ino, inode); |
471 | 0 | if (retval) |
472 | 0 | return retval; |
473 | | |
474 | 0 | return ext2fs_inline_data_ea_remove(fs, ino); |
475 | 0 | } |
476 | | |
477 | | /* |
478 | | * Deallocate all logical _blocks_ starting at start to end, inclusive. |
479 | | * If end is ~0ULL, then this is effectively truncate. |
480 | | */ |
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 | 0 | { |
486 | 0 | errcode_t retval; |
487 | 0 | struct ext2_inode inode_buf; |
488 | |
|
489 | 0 | if (start > end) |
490 | 0 | return EINVAL; |
491 | | |
492 | | /* Read inode structure if necessary */ |
493 | 0 | if (!inode) { |
494 | 0 | retval = ext2fs_read_inode(fs, ino, &inode_buf); |
495 | 0 | if (retval) |
496 | 0 | return retval; |
497 | 0 | inode = &inode_buf; |
498 | 0 | } |
499 | 0 | if (inode->i_flags & EXT4_INLINE_DATA_FL) |
500 | 0 | return ext2fs_punch_inline_data(fs, ino, inode, start, end); |
501 | 0 | else if (inode->i_flags & EXT4_EXTENTS_FL) |
502 | 0 | retval = ext2fs_punch_extent(fs, ino, inode, start, end); |
503 | 0 | else |
504 | 0 | retval = ext2fs_punch_ind(fs, inode, block_buf, start, end); |
505 | 0 | if (retval) |
506 | 0 | 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 | 0 | return ext2fs_write_inode(fs, ino, inode); |
513 | 0 | } |