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                            blk_t start, blk_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 %u, count %u, "
  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 static errcode_t ext2fs_punch_ind(ext2_filsys fs, struct ext2_inode *inode,
 105                                   char *block_buf, blk_t start, blk_t count)
 106 {
 107         errcode_t               retval;
 108         char                    *buf = 0;
 109         int                     level;
 110         int                     num = EXT2_NDIR_BLOCKS;
 111         blk_t                   *bp = inode->i_block;
 112         blk_t                   addr_per_block;
 113         blk64_t                 max = EXT2_NDIR_BLOCKS;
 114
 115         if (!block_buf) {
 116                 retval = ext2fs_get_array(3, fs->blocksize, &buf);
 117                 if (retval)
 118                         return retval;
 119                 block_buf = buf;
 120         }
 121
 122         addr_per_block = (blk_t) fs->blocksize >> 2;
 123
 124         for (level = 0; level < 4; level++, max *= (blk64_t)addr_per_block) {
 125 #ifdef PUNCH_DEBUG
 126                 printf("Main loop level %d, start %u count %u "
 127                        "max %llu num %d\n", level, start, count, max, num);
 128 #endif
 129                 if (start < max) {
 130                         retval = ind_punch(fs, inode, block_buf, bp, level,
 131                                            start, count, num);
 132                         if (retval)
 133                                 goto errout;
 134                         if (count > max)
 135                                 count -= max - start;
 136                         else
 137                                 break;
 138                         start = 0;
 139                 } else
 140                         start -= max;
 141                 bp += num;
 142                 if (level == 0) {
 143                         num = 1;
 144                         max = 1;
 145                 }
 146         }
 147         retval = 0;
 148 errout:
 149         if (buf)
 150                 ext2fs_free_mem(&buf);
 151         return retval;
 152 }
 153
 154 #ifdef PUNCH_DEBUG
 155
 156 #define dbg_printf(f, a...)  printf(f, ## a)
 157
 158 static void dbg_print_extent(char *desc, struct ext2fs_extent *extent)
 159 {
 160         if (desc)
 161                 printf("%s: ", desc);
 162         printf("extent: lblk %llu--%llu, len %u, pblk %llu, flags: ",
 163                extent->e_lblk, extent->e_lblk + extent->e_len - 1,
 164                extent->e_len, extent->e_pblk);
 165         if (extent->e_flags & EXT2_EXTENT_FLAGS_LEAF)
 166                 fputs("LEAF ", stdout);
 167         if (extent->e_flags & EXT2_EXTENT_FLAGS_UNINIT)
 168                 fputs("UNINIT ", stdout);
 169         if (extent->e_flags & EXT2_EXTENT_FLAGS_SECOND_VISIT)
 170                 fputs("2ND_VISIT ", stdout);
 171         if (!extent->e_flags)
 172                 fputs("(none)", stdout);
 173         fputc('\n', stdout);
 174
 175 }
 176 #else
 177 #define dbg_print_extent(desc, ex)      do { } while (0)
 178 #define dbg_printf(f, a...)             do { } while (0)
 179 #endif
 180
 181 /* Free a range of blocks, respecting cluster boundaries */
 182 static errcode_t punch_extent_blocks(ext2_filsys fs, ext2_ino_t ino,
 183                                      struct ext2_inode *inode,
 184                                      blk64_t lfree_start, blk64_t free_start,
 185                                      __u32 free_count, int *freed)
 186 {
 187         blk64_t         pblk;
 188         int             freed_now = 0;
 189         __u32           cluster_freed;
 190         errcode_t       retval = 0;
 191
 192         /* No bigalloc?  Just free each block. */
 193         if (EXT2FS_CLUSTER_RATIO(fs) == 1) {
 194                 *freed += free_count;
 195                 while (free_count-- > 0)
 196                         ext2fs_block_alloc_stats2(fs, free_start++, -1);
 197                 return retval;
 198         }
 199
 200         /*
 201          * Try to free up to the next cluster boundary.  We assume that all
 202          * blocks in a logical cluster map to blocks from the same physical
 203          * cluster, and that the offsets within the [pl]clusters match.
 204          */
 205         if (free_start & EXT2FS_CLUSTER_MASK(fs)) {
 206                 retval = ext2fs_map_cluster_block(fs, ino, inode,
 207                                                   lfree_start, &pblk);
 208                 if (retval)
 209                         goto errout;
 210                 if (!pblk) {
 211                         ext2fs_block_alloc_stats2(fs, free_start, -1);
 212                         freed_now++;
 213                 }
 214                 cluster_freed = EXT2FS_CLUSTER_RATIO(fs) -
 215                         (free_start & EXT2FS_CLUSTER_MASK(fs));
 216                 if (cluster_freed > free_count)
 217                         cluster_freed = free_count;
 218                 free_count -= cluster_freed;
 219                 free_start += cluster_freed;
 220                 lfree_start += cluster_freed;
 221         }
 222
 223         /* Free whole clusters from the middle of the range. */
 224         while (free_count > 0 && free_count >= EXT2FS_CLUSTER_RATIO(fs)) {
 225                 ext2fs_block_alloc_stats2(fs, free_start, -1);
 226                 freed_now++;
 227                 cluster_freed = EXT2FS_CLUSTER_RATIO(fs);
 228                 free_count -= cluster_freed;
 229                 free_start += cluster_freed;
 230                 lfree_start += cluster_freed;
 231         }
 232
 233         /* Try to free the last cluster. */
 234         if (free_count > 0) {
 235                 retval = ext2fs_map_cluster_block(fs, ino, inode,
 236                                                   lfree_start, &pblk);
 237                 if (retval)
 238                         goto errout;
 239                 if (!pblk) {
 240                         ext2fs_block_alloc_stats2(fs, free_start, -1);
 241                         freed_now++;
 242                 }
 243         }
 244
 245 errout:
 246         *freed += freed_now;
 247         return retval;
 248 }
 249
 250 static errcode_t ext2fs_punch_extent(ext2_filsys fs, ext2_ino_t ino,
 251                                      struct ext2_inode *inode,
 252                                      blk64_t start, blk64_t end)
 253 {
 254         ext2_extent_handle_t    handle = 0;
 255         struct ext2fs_extent    extent;
 256         errcode_t               retval;
 257         blk64_t                 free_start, next, lfree_start;
 258         __u32                   free_count, newlen;
 259         int                     freed = 0;
 260         int                     op;
 261
 262         retval = ext2fs_extent_open2(fs, ino, inode, &handle);
 263         if (retval)
 264                 return retval;
 265         /*
 266          * Find the extent closest to the start of the punch range.  We don't
 267          * check the return value because _goto() sets the current node to the
 268          * next-lowest extent if 'start' is in a hole, and doesn't set a
 269          * current node if there was a real error reading the extent tree.
 270          * In that case, _get() will error out.
 271          *
 272          * Note: If _get() returns 'no current node', that simply means that
 273          * there aren't any blocks mapped past this point in the file, so we're
 274          * done.
 275          */
 276         ext2fs_extent_goto(handle, start);
 277         retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
 278         if (retval == EXT2_ET_NO_CURRENT_NODE) {
 279                 retval = 0;
 280                 goto errout;
 281         } else if (retval)
 282                 goto errout;
 283         while (1) {
 284                 op = EXT2_EXTENT_NEXT_LEAF;
 285                 dbg_print_extent("main loop", &extent);
 286                 next = extent.e_lblk + extent.e_len;
 287                 dbg_printf("start %llu, end %llu, next %llu\n",
 288                            (unsigned long long) start,
 289                            (unsigned long long) end,
 290                            (unsigned long long) next);
 291                 if (start <= extent.e_lblk) {
 292                         /*
 293                          * Have we iterated past the end of the punch region?
 294                          * If so, we can stop.
 295                          */
 296                         if (end < extent.e_lblk)
 297                                 break;
 298                         dbg_printf("Case #%d\n", 1);
 299                         /* Start of deleted region before extent;
 300                            adjust beginning of extent */
 301                         free_start = extent.e_pblk;
 302                         lfree_start = extent.e_lblk;
 303                         if (next > end)
 304                                 free_count = end - extent.e_lblk + 1;
 305                         else
 306                                 free_count = extent.e_len;
 307                         extent.e_len -= free_count;
 308                         extent.e_lblk += free_count;
 309                         extent.e_pblk += free_count;
 310                 } else if (end >= next-1) {
 311                         /*
 312                          * Is the punch region beyond this extent?  This can
 313                          * happen if start is already inside a hole.  Try to
 314                          * advance to the next extent if this is the case.
 315                          */
 316                         if (start >= next)
 317                                 goto next_extent;
 318                         /* End of deleted region after extent;
 319                            adjust end of extent */
 320                         dbg_printf("Case #%d\n", 2);
 321                         newlen = start - extent.e_lblk;
 322                         free_start = extent.e_pblk + newlen;
 323                         lfree_start = extent.e_lblk + newlen;
 324                         free_count = extent.e_len - newlen;
 325                         extent.e_len = newlen;
 326                 } else {
 327                         struct ext2fs_extent    newex;
 328
 329                         dbg_printf("Case #%d\n", 3);
 330                         /* The hard case; we need to split the extent */
 331                         newex.e_pblk = extent.e_pblk +
 332                                 (end + 1 - extent.e_lblk);
 333                         newex.e_lblk = end + 1;
 334                         newex.e_len = next - end - 1;
 335                         newex.e_flags = extent.e_flags;
 336
 337                         extent.e_len = start - extent.e_lblk;
 338                         free_start = extent.e_pblk + extent.e_len;
 339                         lfree_start = extent.e_lblk + extent.e_len;
 340                         free_count = end - start + 1;
 341
 342                         dbg_print_extent("inserting", &newex);
 343                         retval = ext2fs_extent_insert(handle,
 344                                         EXT2_EXTENT_INSERT_AFTER, &newex);
 345                         if (retval)
 346                                 goto errout;
 347                         retval = ext2fs_extent_fix_parents(handle);
 348                         if (retval)
 349                                 goto errout;
 350                         /*
 351                          * Now pointing at inserted extent; so go back.
 352                          *
 353                          * We cannot use EXT2_EXTENT_PREV to go back; note the
 354                          * subtlety in the comment for fix_parents().
 355                          */
 356                         retval = ext2fs_extent_goto(handle, extent.e_lblk);
 357                         if (retval)
 358                                 goto errout;
 359                 }
 360                 if (extent.e_len) {
 361                         dbg_print_extent("replacing", &extent);
 362                         retval = ext2fs_extent_replace(handle, 0, &extent);
 363                         if (retval)
 364                                 goto errout;
 365                         retval = ext2fs_extent_fix_parents(handle);
 366                 } else {
 367                         struct ext2fs_extent    newex;
 368                         blk64_t                 old_lblk, next_lblk;
 369                         dbg_printf("deleting current extent%s\n", "");
 370
 371                         /*
 372                          * Save the location of the next leaf, then slip
 373                          * back to the current extent.
 374                          */
 375                         retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT,
 376                                                    &newex);
 377                         if (retval)
 378                                 goto errout;
 379                         old_lblk = newex.e_lblk;
 380
 381                         retval = ext2fs_extent_get(handle,
 382                                                    EXT2_EXTENT_NEXT_LEAF,
 383                                                    &newex);
 384                         if (retval == EXT2_ET_EXTENT_NO_NEXT)
 385                                 next_lblk = old_lblk;
 386                         else if (retval)
 387                                 goto errout;
 388                         else
 389                                 next_lblk = newex.e_lblk;
 390
 391                         retval = ext2fs_extent_goto(handle, old_lblk);
 392                         if (retval)
 393                                 goto errout;
 394
 395                         /* Now delete the extent. */
 396                         retval = ext2fs_extent_delete(handle, 0);
 397                         if (retval)
 398                                 goto errout;
 399
 400                         retval = ext2fs_extent_fix_parents(handle);
 401                         if (retval && retval != EXT2_ET_NO_CURRENT_NODE)
 402                                 goto errout;
 403                         retval = 0;
 404
 405                         /* Jump forward to the next extent. */
 406                         ext2fs_extent_goto(handle, next_lblk);
 407                         op = EXT2_EXTENT_CURRENT;
 408                 }
 409                 if (retval)
 410                         goto errout;
 411                 dbg_printf("Free start %llu, free count = %u\n",
 412                        free_start, free_count);
 413                 retval = punch_extent_blocks(fs, ino, inode, lfree_start,
 414                                              free_start, free_count, &freed);
 415                 if (retval)
 416                         goto errout;
 417         next_extent:
 418                 retval = ext2fs_extent_get(handle, op,
 419                                            &extent);
 420                 if (retval == EXT2_ET_EXTENT_NO_NEXT ||
 421                     retval == EXT2_ET_NO_CURRENT_NODE)
 422                         break;
 423                 if (retval)
 424                         goto errout;
 425         }
 426         dbg_printf("Freed %d blocks\n", freed);
 427         retval = ext2fs_iblk_sub_blocks(fs, inode, freed);
 428 errout:
 429         ext2fs_extent_free(handle);
 430         return retval;
 431 }
 432
 433 static errcode_t ext2fs_punch_inline_data(ext2_filsys fs, ext2_ino_t ino,
 434                                           struct ext2_inode *inode,
 435                                           blk64_t start, blk64_t end)
 436 {
 437         errcode_t retval;
 438
 439         /*
 440          * In libext2fs ext2fs_punch is based on block unit.  So that
 441          * means that if start > 0 we don't need to do nothing.  Due
 442          * to this we will remove all inline data in ext2fs_punch()
 443          * now.
 444          */
 445         if (start > 0)
 446                 return 0;
 447
 448         memset((char *)inode->i_block, 0, EXT4_MIN_INLINE_DATA_SIZE);
 449         inode->i_size = 0;
 450         retval = ext2fs_write_inode(fs, ino, inode);
 451         if (retval)
 452                 return retval;
 453
 454         return ext2fs_inline_data_ea_remove(fs, ino);
 455 }
 456
 457 /*
 458  * Deallocate all logical blocks starting at start to end, inclusive.
 459  * If end is ~0, then this is effectively truncate.
 460  */
 461 errcode_t ext2fs_punch(ext2_filsys fs, ext2_ino_t ino,
 462                        struct ext2_inode *inode,
 463                        char *block_buf, blk64_t start,
 464                        blk64_t end)
 465 {
 466         errcode_t               retval;
 467         struct ext2_inode       inode_buf;
 468
 469         if (start > end)
 470                 return EINVAL;
 471
 472         /* Read inode structure if necessary */
 473         if (!inode) {
 474                 retval = ext2fs_read_inode(fs, ino, &inode_buf);
 475                 if (retval)
 476                         return retval;
 477                 inode = &inode_buf;
 478         }
 479         if (inode->i_flags & EXT4_INLINE_DATA_FL)
 480                 return ext2fs_punch_inline_data(fs, ino, inode, start, end);
 481         else if (inode->i_flags & EXT4_EXTENTS_FL)
 482                 retval = ext2fs_punch_extent(fs, ino, inode, start, end);
 483         else {
 484                 blk_t   count;
 485
 486                 if (start > ~0U)
 487                         return 0;
 488                 if (end > ~0U)
 489                         end = ~0U;
 490                 count = ((end - start + 1) < ~0U) ? (end - start + 1) : ~0U;
 491                 retval = ext2fs_punch_ind(fs, inode, block_buf,
 492                                           (blk_t) start, count);
 493         }
 494         if (retval)
 495                 return retval;
 496
 497         return ext2fs_write_inode(fs, ino, inode);
 498 }