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