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         if (free_start < fs->super->s_first_data_block ||
 204             (free_start + free_count) >= ext2fs_blocks_count(fs->super))
 205                 return EXT2_ET_BAD_BLOCK_NUM;
 206
 207         /* No bigalloc?  Just free each block. */
 208         if (EXT2FS_CLUSTER_RATIO(fs) == 1) {
 209                 *freed += free_count;
 210                 while (free_count-- > 0)
 211                         ext2fs_block_alloc_stats2(fs, free_start++, -1);
 212                 return retval;
 213         }
 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         if (free_start & EXT2FS_CLUSTER_MASK(fs)) {
 221                 retval = ext2fs_map_cluster_block(fs, ino, inode,
 222                                                   lfree_start, &pblk);
 223                 if (retval)
 224                         goto errout;
 225                 if (!pblk) {
 226                         ext2fs_block_alloc_stats2(fs, free_start, -1);
 227                         freed_now++;
 228                 }
 229                 cluster_freed = EXT2FS_CLUSTER_RATIO(fs) -
 230                         (free_start & EXT2FS_CLUSTER_MASK(fs));
 231                 if (cluster_freed > free_count)
 232                         cluster_freed = free_count;
 233                 free_count -= cluster_freed;
 234                 free_start += cluster_freed;
 235                 lfree_start += cluster_freed;
 236         }
 237
 238         /* Free whole clusters from the middle of the range. */
 239         while (free_count > 0 && free_count >= (unsigned) EXT2FS_CLUSTER_RATIO(fs)) {
 240                 ext2fs_block_alloc_stats2(fs, free_start, -1);
 241                 freed_now++;
 242                 cluster_freed = EXT2FS_CLUSTER_RATIO(fs);
 243                 free_count -= cluster_freed;
 244                 free_start += cluster_freed;
 245                 lfree_start += cluster_freed;
 246         }
 247
 248         /* Try to free the last cluster. */
 249         if (free_count > 0) {
 250                 retval = ext2fs_map_cluster_block(fs, ino, inode,
 251                                                   lfree_start, &pblk);
 252                 if (retval)
 253                         goto errout;
 254                 if (!pblk) {
 255                         ext2fs_block_alloc_stats2(fs, free_start, -1);
 256                         freed_now++;
 257                 }
 258         }
 259
 260 errout:
 261         *freed += freed_now;
 262         return retval;
 263 }
 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 {
 269         ext2_extent_handle_t    handle = 0;
 270         struct ext2fs_extent    extent;
 271         errcode_t               retval;
 272         blk64_t                 free_start, next, lfree_start;
 273         __u32                   free_count, newlen;
 274         int                     freed = 0;
 275         int                     op;
 276
 277         retval = ext2fs_extent_open2(fs, ino, inode, &handle);
 278         if (retval)
 279                 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         ext2fs_extent_goto(handle, start);
 292         retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
 293         if (retval == EXT2_ET_NO_CURRENT_NODE) {
 294                 retval = 0;
 295                 goto errout;
 296         } else if (retval)
 297                 goto errout;
 298         while (1) {
 299                 op = EXT2_EXTENT_NEXT_LEAF;
 300                 dbg_print_extent("main loop", &extent);
 301                 next = extent.e_lblk + extent.e_len;
 302                 dbg_printf("start %llu, end %llu, next %llu\n",
 303                            (unsigned long long) start,
 304                            (unsigned long long) end,
 305                            (unsigned long long) next);
 306                 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                         if (end < extent.e_lblk)
 312                                 break;
 313                         dbg_printf("Case #%d\n", 1);
 314                         /* Start of deleted region before extent;
 315                            adjust beginning of extent */
 316                         free_start = extent.e_pblk;
 317                         lfree_start = extent.e_lblk;
 318                         if (next > end)
 319                                 free_count = end - extent.e_lblk + 1;
 320                         else
 321                                 free_count = extent.e_len;
 322                         extent.e_len -= free_count;
 323                         extent.e_lblk += free_count;
 324                         extent.e_pblk += free_count;
 325                 } 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                         if (start >= next)
 332                                 goto next_extent;
 333                         /* End of deleted region after extent;
 334                            adjust end of extent */
 335                         dbg_printf("Case #%d\n", 2);
 336                         newlen = start - extent.e_lblk;
 337                         free_start = extent.e_pblk + newlen;
 338                         lfree_start = extent.e_lblk + newlen;
 339                         free_count = extent.e_len - newlen;
 340                         extent.e_len = newlen;
 341                 } else {
 342                         struct ext2fs_extent    newex;
 343
 344                         dbg_printf("Case #%d\n", 3);
 345                         /* The hard case; we need to split the extent */
 346                         newex.e_pblk = extent.e_pblk +
 347                                 (end + 1 - extent.e_lblk);
 348                         newex.e_lblk = end + 1;
 349                         newex.e_len = next - end - 1;
 350                         newex.e_flags = extent.e_flags;
 351
 352                         extent.e_len = start - extent.e_lblk;
 353                         free_start = extent.e_pblk + extent.e_len;
 354                         lfree_start = extent.e_lblk + extent.e_len;
 355                         free_count = end - start + 1;
 356
 357                         dbg_print_extent("inserting", &newex);
 358                         retval = ext2fs_extent_insert(handle,
 359                                         EXT2_EXTENT_INSERT_AFTER, &newex);
 360                         if (retval)
 361                                 goto errout;
 362                         retval = ext2fs_extent_fix_parents(handle);
 363                         if (retval)
 364                                 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                         retval = ext2fs_extent_goto(handle, extent.e_lblk);
 372                         if (retval)
 373                                 goto errout;
 374                 }
 375                 if (extent.e_len) {
 376                         dbg_print_extent("replacing", &extent);
 377                         retval = ext2fs_extent_replace(handle, 0, &extent);
 378                         if (retval)
 379                                 goto errout;
 380                         retval = ext2fs_extent_fix_parents(handle);
 381                 } else {
 382                         struct ext2fs_extent    newex;
 383                         blk64_t                 old_lblk, next_lblk;
 384                         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                         retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT,
 391                                                    &newex);
 392                         if (retval)
 393                                 goto errout;
 394                         old_lblk = newex.e_lblk;
 395
 396                         retval = ext2fs_extent_get(handle,
 397                                                    EXT2_EXTENT_NEXT_LEAF,
 398                                                    &newex);
 399                         if (retval == EXT2_ET_EXTENT_NO_NEXT)
 400                                 next_lblk = old_lblk;
 401                         else if (retval)
 402                                 goto errout;
 403                         else
 404                                 next_lblk = newex.e_lblk;
 405
 406                         retval = ext2fs_extent_goto(handle, old_lblk);
 407                         if (retval)
 408                                 goto errout;
 409
 410                         /* Now delete the extent. */
 411                         retval = ext2fs_extent_delete(handle, 0);
 412                         if (retval)
 413                                 goto errout;
 414
 415                         retval = ext2fs_extent_fix_parents(handle);
 416                         if (retval && retval != EXT2_ET_NO_CURRENT_NODE)
 417                                 goto errout;
 418                         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                         (void)ext2fs_extent_goto(handle, next_lblk);
 426                         op = EXT2_EXTENT_CURRENT;
 427                 }
 428                 if (retval)
 429                         goto errout;
 430                 dbg_printf("Free start %llu, free count = %u\n",
 431                        free_start, free_count);
 432                 retval = punch_extent_blocks(fs, ino, inode, lfree_start,
 433                                              free_start, free_count, &freed);
 434                 if (retval)
 435                         goto errout;
 436         next_extent:
 437                 retval = ext2fs_extent_get(handle, op,
 438                                            &extent);
 439                 if (retval == EXT2_ET_EXTENT_NO_NEXT ||
 440                     retval == EXT2_ET_NO_CURRENT_NODE)
 441                         break;
 442                 if (retval)
 443                         goto errout;
 444         }
 445         dbg_printf("Freed %d blocks\n", freed);
 446         retval = ext2fs_iblk_sub_blocks(fs, inode, freed);
 447 errout:
 448         ext2fs_extent_free(handle);
 449         return retval;
 450 }
 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 {
 457         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         if (start > 0)
 466                 return 0;
 467
 468         memset((char *)inode->i_block, 0, EXT4_MIN_INLINE_DATA_SIZE);
 469         inode->i_size = 0;
 470         retval = ext2fs_write_inode(fs, ino, inode);
 471         if (retval)
 472                 return retval;
 473
 474         return ext2fs_inline_data_ea_remove(fs, ino);
 475 }
 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 {
 486         errcode_t               retval;
 487         struct ext2_inode       inode_buf;
 488
 489         if (start > end)
 490                 return EINVAL;
 491
 492         /* Read inode structure if necessary */
 493         if (!inode) {
 494                 retval = ext2fs_read_inode(fs, ino, &inode_buf);
 495                 if (retval)
 496                         return retval;
 497                 inode = &inode_buf;
 498         }
 499         if (inode->i_flags & EXT4_INLINE_DATA_FL)
 500                 return ext2fs_punch_inline_data(fs, ino, inode, start, end);
 501         else if (inode->i_flags & EXT4_EXTENTS_FL)
 502                 retval = ext2fs_punch_extent(fs, ino, inode, start, end);
 503         else
 504                 retval = ext2fs_punch_ind(fs, inode, block_buf, start, end);
 505         if (retval)
 506                 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         return ext2fs_write_inode(fs, ino, inode);
 513 }