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