lib/ext2fs/punch.c

   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  */
  28 static 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  */
  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)
  51 {
  52         errcode_t       retval;
  53         blk_t           b;
  54         int             i;
  55         blk64_t         offset, incr;
  56         int             freed = 0;
  57
  58 #ifdef PUNCH_DEBUG
  59         printf("Entering ind_punch, level %d, start %u, count %u, "
  60                "max %d\n", level, start, count, max);
  61 #endif
  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)
  65                         break;
  66                 if (*p == 0 || (offset+incr) <= start)
  67                         continue;
  68                 b = *p;
  69                 if (level > 0) {
  70                         blk_t start2;
  71 #ifdef PUNCH_DEBUG
  72                         printf("Reading indirect block %u\n", b);
  73 #endif
  74                         retval = ext2fs_read_ind_block(fs, b, block_buf);
  75                         if (retval)
  76                                 return retval;
  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,
  81                                            fs->blocksize >> 2);
  82                         if (retval)
  83                                 return retval;
  84                         retval = ext2fs_write_ind_block(fs, b, block_buf);
  85                         if (retval)
  86                                 return retval;
  87                         if (!check_zero_block(block_buf, fs->blocksize))
  88                                 continue;
  89                 }
  90 #ifdef PUNCH_DEBUG
  91                 printf("Freeing block %u (offset %llu)\n", b, offset);
  92 #endif
  93                 ext2fs_block_alloc_stats(fs, b, -1);
  94                 *p = 0;
  95                 freed++;
  96         }
  97 #ifdef PUNCH_DEBUG
  98         printf("Freed %d blocks\n", freed);
  99 #endif
 100         return ext2fs_iblk_sub_blocks(fs, inode, freed);
 101 }
 102
 103 static errcode_t ext2fs_punch_ind(ext2_filsys fs, struct ext2_inode *inode,
 104                                   char *block_buf, blk_t start, blk_t count)
 105 {
 106         errcode_t               retval;
 107         char                    *buf = 0;
 108         int                     level;
 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;
 113
 114         if (!block_buf) {
 115                 retval = ext2fs_get_array(3, fs->blocksize, &buf);
 116                 if (retval)
 117                         return retval;
 118                 block_buf = buf;
 119         }
 120
 121         addr_per_block = (blk_t) fs->blocksize >> 2;
 122
 123         for (level = 0; level < 4; level++, max *= (blk64_t)addr_per_block) {
 124 #ifdef PUNCH_DEBUG
 125                 printf("Main loop level %d, start %u count %u "
 126                        "max %llu num %d\n", level, start, count, max, num);
 127 #endif
 128                 if (start < max) {
 129                         retval = ind_punch(fs, inode, block_buf, bp, level,
 130                                            start, count, num);
 131                         if (retval)
 132                                 goto errout;
 133                         if (count > max)
 134                                 count -= max - start;
 135                         else
 136                                 break;
 137                         start = 0;
 138                 } else
 139                         start -= max;
 140                 bp += num;
 141                 if (level == 0) {
 142                         num = 1;
 143                         max = 1;
 144                 }
 145         }
 146         retval = 0;
 147 errout:
 148         if (buf)
 149                 ext2fs_free_mem(&buf);
 150         return retval;
 151 }
 152
 153 #ifdef PUNCH_DEBUG
 154
 155 #define dbg_printf(f, a...)  printf(f, ## a)
 156
 157 static void dbg_print_extent(char *desc, struct ext2fs_extent *extent)
 158 {
 159         if (desc)
 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);
 172         fputc('\n', stdout);
 173
 174 }
 175 #else
 176 #define dbg_print_extent(desc, ex)      do { } while (0)
 177 #define dbg_printf(f, a...)             do { } while (0)
 178 #endif
 179
 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)
 185 {
 186         blk64_t         pblk;
 187         int             freed_now = 0;
 188         __u32           cluster_freed;
 189         errcode_t       retval = 0;
 190
 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);
 196                 return retval;
 197         }
 198
 199         /*
 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.
 203          */
 204         if (free_start & EXT2FS_CLUSTER_MASK(fs)) {
 205                 retval = ext2fs_map_cluster_block(fs, ino, inode,
 206                                                   lfree_start, &pblk);
 207                 if (retval)
 208                         goto errout;
 209                 if (!pblk) {
 210                         ext2fs_block_alloc_stats2(fs, free_start, -1);
 211                         freed_now++;
 212                 }
 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;
 220         }
 221
 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);
 225                 freed_now++;
 226                 cluster_freed = EXT2FS_CLUSTER_RATIO(fs);
 227                 free_count -= cluster_freed;
 228                 free_start += cluster_freed;
 229                 lfree_start += cluster_freed;
 230         }
 231
 232         /* Try to free the last cluster. */
 233         if (free_count > 0) {
 234                 retval = ext2fs_map_cluster_block(fs, ino, inode,
 235                                                   lfree_start, &pblk);
 236                 if (retval)
 237                         goto errout;
 238                 if (!pblk) {
 239                         ext2fs_block_alloc_stats2(fs, free_start, -1);
 240                         freed_now++;
 241                 }
 242         }
 243
 244 errout:
 245         *freed += freed_now;
 246         return retval;
 247 }
 248
 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)
 252 {
 253         ext2_extent_handle_t    handle = 0;
 254         struct ext2fs_extent    extent;
 255         errcode_t               retval;
 256         blk64_t                 free_start, next, lfree_start;
 257         __u32                   free_count, newlen;
 258         int                     freed = 0;
 259         int                     op;
 260
 261         retval = ext2fs_extent_open2(fs, ino, inode, &handle);
 262         if (retval)
 263                 return retval;
 264         /*
 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.
 270          *
 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
 273          * done.
 274          */
 275         ext2fs_extent_goto(handle, start);
 276         retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
 277         if (retval == EXT2_ET_NO_CURRENT_NODE) {
 278                 retval = 0;
 279                 goto errout;
 280         } else if (retval)
 281                 goto errout;
 282         while (1) {
 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) {
 291                         /*
 292                          * Have we iterated past the end of the punch region?
 293                          * If so, we can stop.
 294                          */
 295                         if (end < extent.e_lblk)
 296                                 break;
 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;
 302                         if (next > end)
 303                                 free_count = end - extent.e_lblk + 1;
 304                         else
 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) {
 310                         /*
 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.
 314                          */
 315                         if (start >= next)
 316                                 goto next_extent;
 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;
 325                 } else {
 326                         struct ext2fs_extent    newex;
 327
 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;
 335
 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;
 340
 341                         dbg_print_extent("inserting", &newex);
 342                         retval = ext2fs_extent_insert(handle,
 343                                         EXT2_EXTENT_INSERT_AFTER, &newex);
 344                         if (retval)
 345                                 goto errout;
 346                         retval = ext2fs_extent_fix_parents(handle);
 347                         if (retval)
 348                                 goto errout;
 349                         /*
 350                          * Now pointing at inserted extent; so go back.
 351                          *
 352                          * We cannot use EXT2_EXTENT_PREV to go back; note the
 353                          * subtlety in the comment for fix_parents().
 354                          */
 355                         retval = ext2fs_extent_goto(handle, extent.e_lblk);
 356                         if (retval)
 357                                 goto errout;
 358                 }
 359                 if (extent.e_len) {
 360                         dbg_print_extent("replacing", &extent);
 361                         retval = ext2fs_extent_replace(handle, 0, &extent);
 362                         if (retval)
 363                                 goto errout;
 364                         retval = ext2fs_extent_fix_parents(handle);
 365                 } else {
 366                         struct ext2fs_extent    newex;
 367                         blk64_t                 old_lblk, next_lblk;
 368                         dbg_printf("deleting current extent%s\n", "");
 369
 370                         /*
 371                          * Save the location of the next leaf, then slip
 372                          * back to the current extent.
 373                          */
 374                         retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT,
 375                                                    &newex);
 376                         if (retval)
 377                                 goto errout;
 378                         old_lblk = newex.e_lblk;
 379
 380                         retval = ext2fs_extent_get(handle,
 381                                                    EXT2_EXTENT_NEXT_LEAF,
 382                                                    &newex);
 383                         if (retval == EXT2_ET_EXTENT_NO_NEXT)
 384                                 next_lblk = old_lblk;
 385                         else if (retval)
 386                                 goto errout;
 387                         else
 388                                 next_lblk = newex.e_lblk;
 389
 390                         retval = ext2fs_extent_goto(handle, old_lblk);
 391                         if (retval)
 392                                 goto errout;
 393
 394                         /* Now delete the extent. */
 395                         retval = ext2fs_extent_delete(handle, 0);
 396                         if (retval)
 397                                 goto errout;
 398
 399                         retval = ext2fs_extent_fix_parents(handle);
 400                         if (retval && retval != EXT2_ET_NO_CURRENT_NODE)
 401                                 goto errout;
 402                         retval = 0;
 403
 404                         /* Jump forward to the next extent. */
 405                         ext2fs_extent_goto(handle, next_lblk);
 406                         op = EXT2_EXTENT_CURRENT;
 407                 }
 408                 if (retval)
 409                         goto errout;
 410                 dbg_printf("Free start %llu, free count = %u\n",
 411                        free_start, free_count);
 412                 retval = punch_extent_blocks(fs, ino, inode, lfree_start,
 413                                              free_start, free_count, &freed);
 414                 if (retval)
 415                         goto errout;
 416         next_extent:
 417                 retval = ext2fs_extent_get(handle, op,
 418                                            &extent);
 419                 if (retval == EXT2_ET_EXTENT_NO_NEXT ||
 420                     retval == EXT2_ET_NO_CURRENT_NODE)
 421                         break;
 422                 if (retval)
 423                         goto errout;
 424         }
 425         dbg_printf("Freed %d blocks\n", freed);
 426         retval = ext2fs_iblk_sub_blocks(fs, inode, freed);
 427 errout:
 428         ext2fs_extent_free(handle);
 429         return retval;
 430 }
 431
 432 /*
 433  * Deallocate all logical blocks starting at start to end, inclusive.
 434  * If end is ~0, then this is effectively truncate.
 435  */
 436 errcode_t ext2fs_punch(ext2_filsys fs, ext2_ino_t ino,
 437                        struct ext2_inode *inode,
 438                        char *block_buf, blk64_t start,
 439                        blk64_t end)
 440 {
 441         errcode_t               retval;
 442         struct ext2_inode       inode_buf;
 443
 444         if (start > end)
 445                 return EINVAL;
 446
 447         /* Read inode structure if necessary */
 448         if (!inode) {
 449                 retval = ext2fs_read_inode(fs, ino, &inode_buf);
 450                 if (retval)
 451                         return retval;
 452                 inode = &inode_buf;
 453         }
 454         if (inode->i_flags & EXT4_EXTENTS_FL)
 455                 retval = ext2fs_punch_extent(fs, ino, inode, start, end);
 456         else {
 457                 blk_t   count;
 458
 459                 if (start > ~0U)
 460                         return 0;
 461                 if (end > ~0U)
 462                         end = ~0U;
 463                 count = ((end - start + 1) < ~0U) ? (end - start + 1) : ~0U;
 464                 retval = ext2fs_punch_ind(fs, inode, block_buf,
 465                                           (blk_t) start, count);
 466         }
 467         if (retval)
 468                 return retval;
 469
 470         return ext2fs_write_inode(fs, ino, inode);
 471 }