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 #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 {
  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  */
  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)
 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
 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 */
 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         /* No bigalloc?  Just free each block. */
 204         if (EXT2FS_CLUSTER_RATIO(fs) == 1) {
 205                 *freed += free_count;
 206                 while (free_count-- > 0)
 207                         ext2fs_block_alloc_stats2(fs, free_start++, -1);
 208                 return retval;
 209         }
 210
 211         /*
 212          * Try to free up to the next cluster boundary.  We assume that all
 213          * blocks in a logical cluster map to blocks from the same physical
 214          * cluster, and that the offsets within the [pl]clusters match.
 215          */
 216         if (free_start & EXT2FS_CLUSTER_MASK(fs)) {
 217                 retval = ext2fs_map_cluster_block(fs, ino, inode,
 218                                                   lfree_start, &pblk);
 219                 if (retval)
 220                         goto errout;
 221                 if (!pblk) {
 222                         ext2fs_block_alloc_stats2(fs, free_start, -1);
 223                         freed_now++;
 224                 }
 225                 cluster_freed = EXT2FS_CLUSTER_RATIO(fs) -
 226                         (free_start & EXT2FS_CLUSTER_MASK(fs));
 227                 if (cluster_freed > free_count)
 228                         cluster_freed = free_count;
 229                 free_count -= cluster_freed;
 230                 free_start += cluster_freed;
 231                 lfree_start += cluster_freed;
 232         }
 233
 234         /* Free whole clusters from the middle of the range. */
 235         while (free_count > 0 && free_count >= (unsigned) EXT2FS_CLUSTER_RATIO(fs)) {
 236                 ext2fs_block_alloc_stats2(fs, free_start, -1);
 237                 freed_now++;
 238                 cluster_freed = EXT2FS_CLUSTER_RATIO(fs);
 239                 free_count -= cluster_freed;
 240                 free_start += cluster_freed;
 241                 lfree_start += cluster_freed;
 242         }
 243
 244         /* Try to free the last cluster. */
 245         if (free_count > 0) {
 246                 retval = ext2fs_map_cluster_block(fs, ino, inode,
 247                                                   lfree_start, &pblk);
 248                 if (retval)
 249                         goto errout;
 250                 if (!pblk) {
 251                         ext2fs_block_alloc_stats2(fs, free_start, -1);
 252                         freed_now++;
 253                 }
 254         }
 255
 256 errout:
 257         *freed += freed_now;
 258         return retval;
 259 }
 260
 261 static errcode_t ext2fs_punch_extent(ext2_filsys fs, ext2_ino_t ino,
 262                                      struct ext2_inode *inode,
 263                                      blk64_t start, blk64_t end)
 264 {
 265         ext2_extent_handle_t    handle = 0;
 266         struct ext2fs_extent    extent;
 267         errcode_t               retval;
 268         blk64_t                 free_start, next, lfree_start;
 269         __u32                   free_count, newlen;
 270         int                     freed = 0;
 271         int                     op;
 272
 273         retval = ext2fs_extent_open2(fs, ino, inode, &handle);
 274         if (retval)
 275                 return retval;
 276         /*
 277          * Find the extent closest to the start of the punch range.  We don't
 278          * check the return value because _goto() sets the current node to the
 279          * next-lowest extent if 'start' is in a hole, and doesn't set a
 280          * current node if there was a real error reading the extent tree.
 281          * In that case, _get() will error out.
 282          *
 283          * Note: If _get() returns 'no current node', that simply means that
 284          * there aren't any blocks mapped past this point in the file, so we're
 285          * done.
 286          */
 287         ext2fs_extent_goto(handle, start);
 288         retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
 289         if (retval == EXT2_ET_NO_CURRENT_NODE) {
 290                 retval = 0;
 291                 goto errout;
 292         } else if (retval)
 293                 goto errout;
 294         while (1) {
 295                 op = EXT2_EXTENT_NEXT_LEAF;
 296                 dbg_print_extent("main loop", &extent);
 297                 next = extent.e_lblk + extent.e_len;
 298                 dbg_printf("start %llu, end %llu, next %llu\n",
 299                            (unsigned long long) start,
 300                            (unsigned long long) end,
 301                            (unsigned long long) next);
 302                 if (start <= extent.e_lblk) {
 303                         /*
 304                          * Have we iterated past the end of the punch region?
 305                          * If so, we can stop.
 306                          */
 307                         if (end < extent.e_lblk)
 308                                 break;
 309                         dbg_printf("Case #%d\n", 1);
 310                         /* Start of deleted region before extent;
 311                            adjust beginning of extent */
 312                         free_start = extent.e_pblk;
 313                         lfree_start = extent.e_lblk;
 314                         if (next > end)
 315                                 free_count = end - extent.e_lblk + 1;
 316                         else
 317                                 free_count = extent.e_len;
 318                         extent.e_len -= free_count;
 319                         extent.e_lblk += free_count;
 320                         extent.e_pblk += free_count;
 321                 } else if (end >= next-1) {
 322                         /*
 323                          * Is the punch region beyond this extent?  This can
 324                          * happen if start is already inside a hole.  Try to
 325                          * advance to the next extent if this is the case.
 326                          */
 327                         if (start >= next)
 328                                 goto next_extent;
 329                         /* End of deleted region after extent;
 330                            adjust end of extent */
 331                         dbg_printf("Case #%d\n", 2);
 332                         newlen = start - extent.e_lblk;
 333                         free_start = extent.e_pblk + newlen;
 334                         lfree_start = extent.e_lblk + newlen;
 335                         free_count = extent.e_len - newlen;
 336                         extent.e_len = newlen;
 337                 } else {
 338                         struct ext2fs_extent    newex;
 339
 340                         dbg_printf("Case #%d\n", 3);
 341                         /* The hard case; we need to split the extent */
 342                         newex.e_pblk = extent.e_pblk +
 343                                 (end + 1 - extent.e_lblk);
 344                         newex.e_lblk = end + 1;
 345                         newex.e_len = next - end - 1;
 346                         newex.e_flags = extent.e_flags;
 347
 348                         extent.e_len = start - extent.e_lblk;
 349                         free_start = extent.e_pblk + extent.e_len;
 350                         lfree_start = extent.e_lblk + extent.e_len;
 351                         free_count = end - start + 1;
 352
 353                         dbg_print_extent("inserting", &newex);
 354                         retval = ext2fs_extent_insert(handle,
 355                                         EXT2_EXTENT_INSERT_AFTER, &newex);
 356                         if (retval)
 357                                 goto errout;
 358                         retval = ext2fs_extent_fix_parents(handle);
 359                         if (retval)
 360                                 goto errout;
 361                         /*
 362                          * Now pointing at inserted extent; so go back.
 363                          *
 364                          * We cannot use EXT2_EXTENT_PREV to go back; note the
 365                          * subtlety in the comment for fix_parents().
 366                          */
 367                         retval = ext2fs_extent_goto(handle, extent.e_lblk);
 368                         if (retval)
 369                                 goto errout;
 370                 }
 371                 if (extent.e_len) {
 372                         dbg_print_extent("replacing", &extent);
 373                         retval = ext2fs_extent_replace(handle, 0, &extent);
 374                         if (retval)
 375                                 goto errout;
 376                         retval = ext2fs_extent_fix_parents(handle);
 377                 } else {
 378                         struct ext2fs_extent    newex;
 379                         blk64_t                 old_lblk, next_lblk;
 380                         dbg_printf("deleting current extent%s\n", "");
 381
 382                         /*
 383                          * Save the location of the next leaf, then slip
 384                          * back to the current extent.
 385                          */
 386                         retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT,
 387                                                    &newex);
 388                         if (retval)
 389                                 goto errout;
 390                         old_lblk = newex.e_lblk;
 391
 392                         retval = ext2fs_extent_get(handle,
 393                                                    EXT2_EXTENT_NEXT_LEAF,
 394                                                    &newex);
 395                         if (retval == EXT2_ET_EXTENT_NO_NEXT)
 396                                 next_lblk = old_lblk;
 397                         else if (retval)
 398                                 goto errout;
 399                         else
 400                                 next_lblk = newex.e_lblk;
 401
 402                         retval = ext2fs_extent_goto(handle, old_lblk);
 403                         if (retval)
 404                                 goto errout;
 405
 406                         /* Now delete the extent. */
 407                         retval = ext2fs_extent_delete(handle, 0);
 408                         if (retval)
 409                                 goto errout;
 410
 411                         retval = ext2fs_extent_fix_parents(handle);
 412                         if (retval && retval != EXT2_ET_NO_CURRENT_NODE)
 413                                 goto errout;
 414                         retval = 0;
 415
 416                         /*
 417                          * Jump forward to the next extent.  If there are
 418                          * errors, the ext2fs_extent_get down below will
 419                          * capture them for us.
 420                          */
 421                         (void)ext2fs_extent_goto(handle, next_lblk);
 422                         op = EXT2_EXTENT_CURRENT;
 423                 }
 424                 if (retval)
 425                         goto errout;
 426                 dbg_printf("Free start %llu, free count = %u\n",
 427                        free_start, free_count);
 428                 retval = punch_extent_blocks(fs, ino, inode, lfree_start,
 429                                              free_start, free_count, &freed);
 430                 if (retval)
 431                         goto errout;
 432         next_extent:
 433                 retval = ext2fs_extent_get(handle, op,
 434                                            &extent);
 435                 if (retval == EXT2_ET_EXTENT_NO_NEXT ||
 436                     retval == EXT2_ET_NO_CURRENT_NODE)
 437                         break;
 438                 if (retval)
 439                         goto errout;
 440         }
 441         dbg_printf("Freed %d blocks\n", freed);
 442         retval = ext2fs_iblk_sub_blocks(fs, inode, freed);
 443 errout:
 444         ext2fs_extent_free(handle);
 445         return retval;
 446 }
 447
 448 static errcode_t ext2fs_punch_inline_data(ext2_filsys fs, ext2_ino_t ino,
 449                                           struct ext2_inode *inode,
 450                                           blk64_t start,
 451                                           blk64_t end EXT2FS_ATTR((unused)))
 452 {
 453         errcode_t retval;
 454
 455         /*
 456          * In libext2fs ext2fs_punch is based on block unit.  So that
 457          * means that if start > 0 we don't need to do nothing.  Due
 458          * to this we will remove all inline data in ext2fs_punch()
 459          * now.
 460          */
 461         if (start > 0)
 462                 return 0;
 463
 464         memset((char *)inode->i_block, 0, EXT4_MIN_INLINE_DATA_SIZE);
 465         inode->i_size = 0;
 466         retval = ext2fs_write_inode(fs, ino, inode);
 467         if (retval)
 468                 return retval;
 469
 470         return ext2fs_inline_data_ea_remove(fs, ino);
 471 }
 472
 473 /*
 474  * Deallocate all logical _blocks_ starting at start to end, inclusive.
 475  * If end is ~0ULL, then this is effectively truncate.
 476  */
 477 errcode_t ext2fs_punch(ext2_filsys fs, ext2_ino_t ino,
 478                        struct ext2_inode *inode,
 479                        char *block_buf, blk64_t start,
 480                        blk64_t end)
 481 {
 482         errcode_t               retval;
 483         struct ext2_inode       inode_buf;
 484
 485         if (start > end)
 486                 return EINVAL;
 487
 488         /* Read inode structure if necessary */
 489         if (!inode) {
 490                 retval = ext2fs_read_inode(fs, ino, &inode_buf);
 491                 if (retval)
 492                         return retval;
 493                 inode = &inode_buf;
 494         }
 495         if (inode->i_flags & EXT4_INLINE_DATA_FL)
 496                 return ext2fs_punch_inline_data(fs, ino, inode, start, end);
 497         else if (inode->i_flags & EXT4_EXTENTS_FL)
 498                 retval = ext2fs_punch_extent(fs, ino, inode, start, end);
 499         else
 500                 retval = ext2fs_punch_ind(fs, inode, block_buf, start, end);
 501         if (retval)
 502                 return retval;
 503
 504 #ifdef PUNCH_DEBUG
 505         printf("%u: write inode size now %lu blocks %u\n",
 506                 ino, EXT2_I_SIZE(inode), inode->i_blocks);
 507 #endif
 508         return ext2fs_write_inode(fs, ino, inode);
 509 }