Coverage Report

Created: 2023-12-08 06:55

/src/e2fsprogs/lib/ext2fs/punch.c
Line
Count
Source (jump to first uncovered line)
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
0
{
31
0
  char  *cp = buf;
32
0
  int left = blocksize;
33
34
0
  while (left > 0) {
35
0
    if (*cp++)
36
0
      return 0;
37
0
    left--;
38
0
  }
39
0
  return 1;
40
0
}
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
0
{
53
0
  errcode_t retval;
54
0
  blk_t   b;
55
0
  int   i;
56
0
  blk64_t   offset, incr;
57
0
  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
0
  incr = 1ULL << ((EXT2_BLOCK_SIZE_BITS(fs->super) - 2) * level);
64
0
  for (i = 0, offset = 0; i < max; i++, p++, offset += incr) {
65
0
    if (offset >= start + count)
66
0
      break;
67
0
    if (*p == 0 || (offset+incr) <= start)
68
0
      continue;
69
0
    b = *p;
70
0
    if (level > 0) {
71
0
      blk_t start2;
72
#ifdef PUNCH_DEBUG
73
      printf("Reading indirect block %u\n", b);
74
#endif
75
0
      retval = ext2fs_read_ind_block(fs, b, block_buf);
76
0
      if (retval)
77
0
        return retval;
78
0
      start2 = (start > offset) ? start - offset : 0;
79
0
      retval = ind_punch(fs, inode, block_buf + fs->blocksize,
80
0
             (blk_t *) block_buf, level - 1,
81
0
             start2, count - offset,
82
0
             fs->blocksize >> 2);
83
0
      if (retval)
84
0
        return retval;
85
0
      retval = ext2fs_write_ind_block(fs, b, block_buf);
86
0
      if (retval)
87
0
        return retval;
88
0
      if (!check_zero_block(block_buf, fs->blocksize))
89
0
        continue;
90
0
    }
91
#ifdef PUNCH_DEBUG
92
    printf("Freeing block %u (offset %llu)\n", b, offset);
93
#endif
94
0
    ext2fs_block_alloc_stats(fs, b, -1);
95
0
    *p = 0;
96
0
    freed++;
97
0
  }
98
#ifdef PUNCH_DEBUG
99
  printf("Freed %d blocks\n", freed);
100
#endif
101
0
  return ext2fs_iblk_sub_blocks(fs, inode, freed);
102
0
}
103
104
0
#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
0
{
108
0
  errcode_t   retval;
109
0
  char      *buf = 0;
110
0
  int     level;
111
0
  int     num = EXT2_NDIR_BLOCKS;
112
0
  blk_t     *bp = inode->i_block;
113
0
  blk_t     addr_per_block;
114
0
  blk64_t     max = EXT2_NDIR_BLOCKS;
115
0
  blk_t     count;
116
117
  /* Check start/end don't overflow the 2^32-1 indirect block limit */
118
0
  if (start > BLK_T_MAX)
119
0
    return 0;
120
0
  if (end >= BLK_T_MAX || end - start + 1 >= BLK_T_MAX)
121
0
    count = BLK_T_MAX - start;
122
0
  else
123
0
    count = end - start + 1;
124
125
0
  if (!block_buf) {
126
0
    retval = ext2fs_get_array(3, fs->blocksize, &buf);
127
0
    if (retval)
128
0
      return retval;
129
0
    block_buf = buf;
130
0
  }
131
132
0
  addr_per_block = (blk_t)fs->blocksize >> 2;
133
134
0
  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
0
    if (start < max) {
140
0
      retval = ind_punch(fs, inode, block_buf, bp, level,
141
0
             start, count, num);
142
0
      if (retval)
143
0
        goto errout;
144
0
      if (count > max)
145
0
        count -= max - start;
146
0
      else
147
0
        break;
148
0
      start = 0;
149
0
    } else
150
0
      start -= max;
151
0
    bp += num;
152
0
    if (level == 0) {
153
0
      num = 1;
154
0
      max = 1;
155
0
    }
156
0
  }
157
0
  retval = 0;
158
0
errout:
159
0
  if (buf)
160
0
    ext2fs_free_mem(&buf);
161
0
  return retval;
162
0
}
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
0
#define dbg_print_extent(desc, ex)  do { } while (0)
189
0
#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
0
{
198
0
  blk64_t   pblk;
199
0
  int   freed_now = 0;
200
0
  __u32   cluster_freed;
201
0
  errcode_t retval = 0;
202
203
0
  if (free_start < fs->super->s_first_data_block ||
204
0
      (free_start + free_count) >= ext2fs_blocks_count(fs->super))
205
0
    return EXT2_ET_BAD_BLOCK_NUM;
206
207
  /* No bigalloc?  Just free each block. */
208
0
  if (EXT2FS_CLUSTER_RATIO(fs) == 1) {
209
0
    *freed += free_count;
210
0
    while (free_count-- > 0)
211
0
      ext2fs_block_alloc_stats2(fs, free_start++, -1);
212
0
    return retval;
213
0
  }
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
0
  if (free_start & EXT2FS_CLUSTER_MASK(fs)) {
221
0
    retval = ext2fs_map_cluster_block(fs, ino, inode,
222
0
              lfree_start, &pblk);
223
0
    if (retval)
224
0
      goto errout;
225
0
    if (!pblk) {
226
0
      ext2fs_block_alloc_stats2(fs, free_start, -1);
227
0
      freed_now++;
228
0
    }
229
0
    cluster_freed = EXT2FS_CLUSTER_RATIO(fs) -
230
0
      (free_start & EXT2FS_CLUSTER_MASK(fs));
231
0
    if (cluster_freed > free_count)
232
0
      cluster_freed = free_count;
233
0
    free_count -= cluster_freed;
234
0
    free_start += cluster_freed;
235
0
    lfree_start += cluster_freed;
236
0
  }
237
238
  /* Free whole clusters from the middle of the range. */
239
0
  while (free_count > 0 && free_count >= (unsigned) EXT2FS_CLUSTER_RATIO(fs)) {
240
0
    ext2fs_block_alloc_stats2(fs, free_start, -1);
241
0
    freed_now++;
242
0
    cluster_freed = EXT2FS_CLUSTER_RATIO(fs);
243
0
    free_count -= cluster_freed;
244
0
    free_start += cluster_freed;
245
0
    lfree_start += cluster_freed;
246
0
  }
247
248
  /* Try to free the last cluster. */
249
0
  if (free_count > 0) {
250
0
    retval = ext2fs_map_cluster_block(fs, ino, inode,
251
0
              lfree_start, &pblk);
252
0
    if (retval)
253
0
      goto errout;
254
0
    if (!pblk) {
255
0
      ext2fs_block_alloc_stats2(fs, free_start, -1);
256
0
      freed_now++;
257
0
    }
258
0
  }
259
260
0
errout:
261
0
  *freed += freed_now;
262
0
  return retval;
263
0
}
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
0
{
269
0
  ext2_extent_handle_t  handle = 0;
270
0
  struct ext2fs_extent  extent;
271
0
  errcode_t   retval;
272
0
  blk64_t     free_start, next, lfree_start;
273
0
  __u32     free_count, newlen;
274
0
  int     freed = 0;
275
0
  int     op;
276
277
0
  retval = ext2fs_extent_open2(fs, ino, inode, &handle);
278
0
  if (retval)
279
0
    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
0
  ext2fs_extent_goto(handle, start);
292
0
  retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
293
0
  if (retval == EXT2_ET_NO_CURRENT_NODE) {
294
0
    retval = 0;
295
0
    goto errout;
296
0
  } else if (retval)
297
0
    goto errout;
298
0
  while (1) {
299
0
    op = EXT2_EXTENT_NEXT_LEAF;
300
0
    dbg_print_extent("main loop", &extent);
301
0
    next = extent.e_lblk + extent.e_len;
302
0
    dbg_printf("start %llu, end %llu, next %llu\n",
303
0
         (unsigned long long) start,
304
0
         (unsigned long long) end,
305
0
         (unsigned long long) next);
306
0
    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
0
      if (end < extent.e_lblk)
312
0
        break;
313
0
      dbg_printf("Case #%d\n", 1);
314
      /* Start of deleted region before extent; 
315
         adjust beginning of extent */
316
0
      free_start = extent.e_pblk;
317
0
      lfree_start = extent.e_lblk;
318
0
      if (next > end)
319
0
        free_count = end - extent.e_lblk + 1;
320
0
      else
321
0
        free_count = extent.e_len;
322
0
      extent.e_len -= free_count;
323
0
      extent.e_lblk += free_count;
324
0
      extent.e_pblk += free_count;
325
0
    } 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
0
      if (start >= next)
332
0
        goto next_extent;
333
      /* End of deleted region after extent;
334
         adjust end of extent */
335
0
      dbg_printf("Case #%d\n", 2);
336
0
      newlen = start - extent.e_lblk;
337
0
      free_start = extent.e_pblk + newlen;
338
0
      lfree_start = extent.e_lblk + newlen;
339
0
      free_count = extent.e_len - newlen;
340
0
      extent.e_len = newlen;
341
0
    } else {
342
0
      struct ext2fs_extent  newex;
343
344
0
      dbg_printf("Case #%d\n", 3);
345
      /* The hard case; we need to split the extent */
346
0
      newex.e_pblk = extent.e_pblk +
347
0
        (end + 1 - extent.e_lblk);
348
0
      newex.e_lblk = end + 1;
349
0
      newex.e_len = next - end - 1;
350
0
      newex.e_flags = extent.e_flags;
351
352
0
      extent.e_len = start - extent.e_lblk;
353
0
      free_start = extent.e_pblk + extent.e_len;
354
0
      lfree_start = extent.e_lblk + extent.e_len;
355
0
      free_count = end - start + 1;
356
357
0
      dbg_print_extent("inserting", &newex);
358
0
      retval = ext2fs_extent_insert(handle,
359
0
          EXT2_EXTENT_INSERT_AFTER, &newex);
360
0
      if (retval)
361
0
        goto errout;
362
0
      retval = ext2fs_extent_fix_parents(handle);
363
0
      if (retval)
364
0
        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
0
      retval = ext2fs_extent_goto(handle, extent.e_lblk);
372
0
      if (retval)
373
0
        goto errout;
374
0
    } 
375
0
    if (extent.e_len) {
376
0
      dbg_print_extent("replacing", &extent);
377
0
      retval = ext2fs_extent_replace(handle, 0, &extent);
378
0
      if (retval)
379
0
        goto errout;
380
0
      retval = ext2fs_extent_fix_parents(handle);
381
0
    } else {
382
0
      struct ext2fs_extent  newex;
383
0
      blk64_t     old_lblk, next_lblk;
384
0
      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
0
      retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT,
391
0
               &newex);
392
0
      if (retval)
393
0
        goto errout;
394
0
      old_lblk = newex.e_lblk;
395
396
0
      retval = ext2fs_extent_get(handle,
397
0
               EXT2_EXTENT_NEXT_LEAF,
398
0
               &newex);
399
0
      if (retval == EXT2_ET_EXTENT_NO_NEXT)
400
0
        next_lblk = old_lblk;
401
0
      else if (retval)
402
0
        goto errout;
403
0
      else
404
0
        next_lblk = newex.e_lblk;
405
406
0
      retval = ext2fs_extent_goto(handle, old_lblk);
407
0
      if (retval)
408
0
        goto errout;
409
410
      /* Now delete the extent. */
411
0
      retval = ext2fs_extent_delete(handle, 0);
412
0
      if (retval)
413
0
        goto errout;
414
415
0
      retval = ext2fs_extent_fix_parents(handle);
416
0
      if (retval && retval != EXT2_ET_NO_CURRENT_NODE)
417
0
        goto errout;
418
0
      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
0
      (void)ext2fs_extent_goto(handle, next_lblk);
426
0
      op = EXT2_EXTENT_CURRENT;
427
0
    }
428
0
    if (retval)
429
0
      goto errout;
430
0
    dbg_printf("Free start %llu, free count = %u\n",
431
0
           free_start, free_count);
432
0
    retval = punch_extent_blocks(fs, ino, inode, lfree_start,
433
0
               free_start, free_count, &freed);
434
0
    if (retval)
435
0
      goto errout;
436
0
  next_extent:
437
0
    retval = ext2fs_extent_get(handle, op,
438
0
             &extent);
439
0
    if (retval == EXT2_ET_EXTENT_NO_NEXT ||
440
0
        retval == EXT2_ET_NO_CURRENT_NODE)
441
0
      break;
442
0
    if (retval)
443
0
      goto errout;
444
0
  }
445
0
  dbg_printf("Freed %d blocks\n", freed);
446
0
  retval = ext2fs_iblk_sub_blocks(fs, inode, freed);
447
0
errout:
448
0
  ext2fs_extent_free(handle);
449
0
  return retval;
450
0
}
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
0
{
457
0
  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
0
  if (start > 0)
466
0
    return 0;
467
468
0
  memset((char *)inode->i_block, 0, EXT4_MIN_INLINE_DATA_SIZE);
469
0
  inode->i_size = 0;
470
0
  retval = ext2fs_write_inode(fs, ino, inode);
471
0
  if (retval)
472
0
    return retval;
473
474
0
  return ext2fs_inline_data_ea_remove(fs, ino);
475
0
}
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
0
{
486
0
  errcode_t   retval;
487
0
  struct ext2_inode inode_buf;
488
489
0
  if (start > end)
490
0
    return EINVAL;
491
492
  /* Read inode structure if necessary */
493
0
  if (!inode) {
494
0
    retval = ext2fs_read_inode(fs, ino, &inode_buf);
495
0
    if (retval)
496
0
      return retval;
497
0
    inode = &inode_buf;
498
0
  }
499
0
  if (inode->i_flags & EXT4_INLINE_DATA_FL)
500
0
    return ext2fs_punch_inline_data(fs, ino, inode, start, end);
501
0
  else if (inode->i_flags & EXT4_EXTENTS_FL)
502
0
    retval = ext2fs_punch_extent(fs, ino, inode, start, end);
503
0
  else
504
0
    retval = ext2fs_punch_ind(fs, inode, block_buf, start, end);
505
0
  if (retval)
506
0
    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
0
  return ext2fs_write_inode(fs, ino, inode);
513
0
}