punch.c revision 5d494038eede1bb538441dedf4207529629154b3
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 23#undef PUNCH_DEBUG 24 25/* 26 * This function returns 1 if the specified block is all zeros 27 */ 28static int check_zero_block(char *buf, int blocksize) 29{ 30 char *cp = buf; 31 int left = blocksize; 32 33 while (left > 0) { 34 if (*cp++) 35 return 0; 36 left--; 37 } 38 return 1; 39} 40 41/* 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. 47 */ 48static 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) 51{ 52 errcode_t retval; 53 blk_t b, offset; 54 int i, incr; 55 int freed = 0; 56 57#ifdef PUNCH_DEBUG 58 printf("Entering ind_punch, level %d, start %u, count %u, " 59 "max %d\n", level, start, count, max); 60#endif 61 incr = 1 << ((EXT2_BLOCK_SIZE_BITS(fs->super)-2)*level); 62 for (i=0, offset=0; i < max; i++, p++, offset += incr) { 63 if (offset > count) 64 break; 65 if (*p == 0 || (offset+incr) <= start) 66 continue; 67 b = *p; 68 if (level > 0) { 69 blk_t start2; 70#ifdef PUNCH_DEBUG 71 printf("Reading indirect block %u\n", b); 72#endif 73 retval = ext2fs_read_ind_block(fs, b, block_buf); 74 if (retval) 75 return retval; 76 start2 = (start > offset) ? start - offset : 0; 77 retval = ind_punch(fs, inode, block_buf + fs->blocksize, 78 (blk_t *) block_buf, level - 1, 79 start2, count - offset, 80 fs->blocksize >> 2); 81 if (retval) 82 return retval; 83 retval = ext2fs_write_ind_block(fs, b, block_buf); 84 if (retval) 85 return retval; 86 if (!check_zero_block(block_buf, fs->blocksize)) 87 continue; 88 } 89#ifdef PUNCH_DEBUG 90 printf("Freeing block %u (offset %d)\n", b, offset); 91#endif 92 ext2fs_block_alloc_stats(fs, b, -1); 93 *p = 0; 94 freed++; 95 } 96#ifdef PUNCH_DEBUG 97 printf("Freed %d blocks\n", freed); 98#endif 99 return ext2fs_iblk_sub_blocks(fs, inode, freed); 100} 101 102static errcode_t ext2fs_punch_ind(ext2_filsys fs, struct ext2_inode *inode, 103 char *block_buf, blk_t start, blk_t count) 104{ 105 errcode_t retval; 106 char *buf = 0; 107 int level; 108 int num = EXT2_NDIR_BLOCKS; 109 blk_t *bp = inode->i_block; 110 blk_t addr_per_block; 111 blk_t max = EXT2_NDIR_BLOCKS; 112 113 if (!block_buf) { 114 retval = ext2fs_get_array(3, fs->blocksize, &buf); 115 if (retval) 116 return retval; 117 block_buf = buf; 118 } 119 120 addr_per_block = (blk_t) fs->blocksize >> 2; 121 122 for (level=0; level < 4; level++, max *= addr_per_block) { 123#ifdef PUNCH_DEBUG 124 printf("Main loop level %d, start %u count %u " 125 "max %d num %d\n", level, start, count, max, num); 126#endif 127 if (start < max) { 128 retval = ind_punch(fs, inode, block_buf, bp, level, 129 start, count, num); 130 if (retval) 131 goto errout; 132 if (count > max) 133 count -= max - start; 134 else 135 break; 136 start = 0; 137 } else 138 start -= max; 139 bp += num; 140 if (level == 0) { 141 num = 1; 142 max = 1; 143 } 144 } 145 retval = 0; 146errout: 147 if (buf) 148 ext2fs_free_mem(&buf); 149 return retval; 150} 151 152#ifdef PUNCH_DEBUG 153 154#define dbg_printf(f, a...) printf(f, ## a) 155 156static void dbg_print_extent(char *desc, struct ext2fs_extent *extent) 157{ 158 if (desc) 159 printf("%s: ", desc); 160 printf("extent: lblk %llu--%llu, len %u, pblk %llu, flags: ", 161 extent->e_lblk, extent->e_lblk + extent->e_len - 1, 162 extent->e_len, extent->e_pblk); 163 if (extent->e_flags & EXT2_EXTENT_FLAGS_LEAF) 164 fputs("LEAF ", stdout); 165 if (extent->e_flags & EXT2_EXTENT_FLAGS_UNINIT) 166 fputs("UNINIT ", stdout); 167 if (extent->e_flags & EXT2_EXTENT_FLAGS_SECOND_VISIT) 168 fputs("2ND_VISIT ", stdout); 169 if (!extent->e_flags) 170 fputs("(none)", stdout); 171 fputc('\n', stdout); 172 173} 174#else 175#define dbg_print_extent(desc, ex) do { } while (0) 176#define dbg_printf(f, a...) do { } while (0) 177#endif 178 179static errcode_t ext2fs_punch_extent(ext2_filsys fs, ext2_ino_t ino, 180 struct ext2_inode *inode, 181 blk64_t start, blk64_t end) 182{ 183 ext2_extent_handle_t handle = 0; 184 struct ext2fs_extent extent; 185 errcode_t retval; 186 blk64_t free_start, next; 187 __u32 free_count, newlen; 188 int freed = 0; 189 int op; 190 191 retval = ext2fs_extent_open2(fs, ino, inode, &handle); 192 if (retval) 193 return retval; 194 ext2fs_extent_goto(handle, start); 195 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent); 196 if (retval) 197 goto errout; 198 while (1) { 199 op = EXT2_EXTENT_NEXT_LEAF; 200 dbg_print_extent("main loop", &extent); 201 next = extent.e_lblk + extent.e_len; 202 dbg_printf("start %llu, end %llu, next %llu\n", 203 (unsigned long long) start, 204 (unsigned long long) end, 205 (unsigned long long) next); 206 if (start <= extent.e_lblk) { 207 if (end < extent.e_lblk) 208 goto next_extent; 209 dbg_printf("Case #%d\n", 1); 210 /* Start of deleted region before extent; 211 adjust beginning of extent */ 212 free_start = extent.e_pblk; 213 if (next > end) 214 free_count = end - extent.e_lblk + 1; 215 else 216 free_count = extent.e_len; 217 extent.e_len -= free_count; 218 extent.e_lblk += free_count; 219 extent.e_pblk += free_count; 220 } else if (end >= next-1) { 221 if (start >= next) 222 break; 223 /* End of deleted region after extent; 224 adjust end of extent */ 225 dbg_printf("Case #%d\n", 2); 226 newlen = start - extent.e_lblk; 227 free_start = extent.e_pblk + newlen; 228 free_count = extent.e_len - newlen; 229 extent.e_len = newlen; 230 } else { 231 struct ext2fs_extent newex; 232 233 dbg_printf("Case #%d\n", 3); 234 /* The hard case; we need to split the extent */ 235 newex.e_pblk = extent.e_pblk + 236 (end + 1 - extent.e_lblk); 237 newex.e_lblk = end + 1; 238 newex.e_len = next - end - 1; 239 newex.e_flags = extent.e_flags; 240 241 extent.e_len = start - extent.e_lblk; 242 free_start = extent.e_pblk + extent.e_len; 243 free_count = end - start + 1; 244 245 dbg_print_extent("inserting", &newex); 246 retval = ext2fs_extent_insert(handle, 247 EXT2_EXTENT_INSERT_AFTER, &newex); 248 if (retval) 249 goto errout; 250 /* Now pointing at inserted extent; so go back */ 251 retval = ext2fs_extent_get(handle, 252 EXT2_EXTENT_PREV_LEAF, 253 &newex); 254 if (retval) 255 goto errout; 256 } 257 if (extent.e_len) { 258 dbg_print_extent("replacing", &extent); 259 retval = ext2fs_extent_replace(handle, 0, &extent); 260 } else { 261 struct ext2fs_extent newex; 262 dbg_printf("deleting current extent%s\n", ""); 263 retval = ext2fs_extent_delete(handle, 0); 264 if (retval) 265 goto errout; 266 /* 267 * We just moved the next extent into the current 268 * extent's position, so re-read the extent next time. 269 */ 270 retval = ext2fs_extent_get(handle, 271 EXT2_EXTENT_PREV_LEAF, 272 &newex); 273 /* Can't go back? Just reread current. */ 274 if (retval == EXT2_ET_EXTENT_NO_PREV) { 275 retval = 0; 276 op = EXT2_EXTENT_CURRENT; 277 } 278 } 279 if (retval) 280 goto errout; 281 dbg_printf("Free start %llu, free count = %u\n", 282 free_start, free_count); 283 while (free_count-- > 0) { 284 ext2fs_block_alloc_stats(fs, free_start++, -1); 285 freed++; 286 } 287 next_extent: 288 retval = ext2fs_extent_get(handle, op, 289 &extent); 290 if (retval == EXT2_ET_EXTENT_NO_NEXT || 291 retval == EXT2_ET_NO_CURRENT_NODE) 292 break; 293 if (retval) 294 goto errout; 295 } 296 dbg_printf("Freed %d blocks\n", freed); 297 retval = ext2fs_iblk_sub_blocks(fs, inode, freed); 298errout: 299 ext2fs_extent_free(handle); 300 return retval; 301} 302 303/* 304 * Deallocate all logical blocks starting at start to end, inclusive. 305 * If end is ~0, then this is effectively truncate. 306 */ 307extern errcode_t ext2fs_punch(ext2_filsys fs, ext2_ino_t ino, 308 struct ext2_inode *inode, 309 char *block_buf, blk64_t start, 310 blk64_t end) 311{ 312 errcode_t retval; 313 struct ext2_inode inode_buf; 314 315 if (start > end) 316 return EINVAL; 317 318 if (start == end) 319 return 0; 320 321 /* Read inode structure if necessary */ 322 if (!inode) { 323 retval = ext2fs_read_inode(fs, ino, &inode_buf); 324 if (retval) 325 return retval; 326 inode = &inode_buf; 327 } 328 if (inode->i_flags & EXT4_EXTENTS_FL) 329 retval = ext2fs_punch_extent(fs, ino, inode, start, end); 330 else { 331 blk_t count; 332 333 if (start > ~0U) 334 return 0; 335 count = ((end - start) < ~0U) ? (end - start) : ~0U; 336 retval = ext2fs_punch_ind(fs, inode, block_buf, 337 (blk_t) start, count); 338 } 339 if (retval) 340 return retval; 341 342 return ext2fs_write_inode(fs, ino, inode); 343} 344