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