Coverage Report

Created: 2023-12-08 06:55

/src/e2fsprogs/lib/ext2fs/blkmap64_ba.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * blkmap64_ba.c --- Simple bitarray implementation for bitmaps
3
 *
4
 * Copyright (C) 2008 Theodore Ts'o.
5
 *
6
 * %Begin-Header%
7
 * This file may be redistributed under the terms of the GNU Public
8
 * License.
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 <fcntl.h>
19
#include <time.h>
20
#if HAVE_SYS_STAT_H
21
#include <sys/stat.h>
22
#endif
23
#if HAVE_SYS_TYPES_H
24
#include <sys/types.h>
25
#endif
26
27
#include "ext2_fs.h"
28
#include "ext2fsP.h"
29
#include "bmap64.h"
30
31
/*
32
 * Private data for bit array implementation of bitmap ops.
33
 * Currently, this is just a pointer to our big flat hunk of memory,
34
 * exactly equivalent to the old-skool char * bitmap member.
35
 */
36
37
struct ext2fs_ba_private_struct {
38
  char *bitarray;
39
};
40
41
typedef struct ext2fs_ba_private_struct *ext2fs_ba_private;
42
43
static errcode_t ba_alloc_private_data (ext2fs_generic_bitmap_64 bitmap)
44
0
{
45
0
  ext2fs_ba_private bp;
46
0
  errcode_t retval;
47
0
  size_t    size;
48
49
  /*
50
   * Since we only have the one pointer, we could just shove our
51
   * private data in the void *private field itself, but then
52
   * we'd have to do a fair bit of rewriting if we ever added a
53
   * field.  I'm agnostic.
54
   */
55
0
  retval = ext2fs_get_mem(sizeof (ext2fs_ba_private), &bp);
56
0
  if (retval)
57
0
    return retval;
58
59
0
  size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1);
60
61
0
  retval = ext2fs_get_mem(size, &bp->bitarray);
62
0
  if (retval) {
63
0
    ext2fs_free_mem(&bp);
64
0
    bp = 0;
65
0
    return retval;
66
0
  }
67
0
  bitmap->private = (void *) bp;
68
0
  return 0;
69
0
}
70
71
static errcode_t ba_new_bmap(ext2_filsys fs EXT2FS_ATTR((unused)),
72
           ext2fs_generic_bitmap_64 bitmap)
73
0
{
74
0
  ext2fs_ba_private bp;
75
0
  errcode_t retval;
76
0
  size_t    size;
77
78
0
  retval = ba_alloc_private_data (bitmap);
79
0
  if (retval)
80
0
    return retval;
81
82
0
  bp = (ext2fs_ba_private) bitmap->private;
83
0
  size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1);
84
0
  memset(bp->bitarray, 0, size);
85
86
0
  return 0;
87
0
}
88
89
static void ba_free_bmap(ext2fs_generic_bitmap_64 bitmap)
90
0
{
91
0
  ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
92
93
0
  if (!bp)
94
0
    return;
95
96
0
  if (bp->bitarray) {
97
0
    ext2fs_free_mem (&bp->bitarray);
98
0
    bp->bitarray = 0;
99
0
  }
100
0
  ext2fs_free_mem (&bp);
101
0
  bp = 0;
102
0
}
103
104
static errcode_t ba_copy_bmap(ext2fs_generic_bitmap_64 src,
105
            ext2fs_generic_bitmap_64 dest)
106
0
{
107
0
  ext2fs_ba_private src_bp = (ext2fs_ba_private) src->private;
108
0
  ext2fs_ba_private dest_bp;
109
0
  errcode_t retval;
110
0
  size_t size;
111
112
0
  retval = ba_alloc_private_data (dest);
113
0
  if (retval)
114
0
    return retval;
115
116
0
  dest_bp = (ext2fs_ba_private) dest->private;
117
118
0
  size = (size_t) (((src->real_end - src->start) / 8) + 1);
119
0
  memcpy (dest_bp->bitarray, src_bp->bitarray, size);
120
121
0
  return 0;
122
0
}
123
124
static errcode_t ba_resize_bmap(ext2fs_generic_bitmap_64 bmap,
125
        __u64 new_end, __u64 new_real_end)
126
0
{
127
0
  ext2fs_ba_private bp = (ext2fs_ba_private) bmap->private;
128
0
  errcode_t retval;
129
0
  size_t    size, new_size;
130
0
  __u64   bitno;
131
132
  /*
133
   * If we're expanding the bitmap, make sure all of the new
134
   * parts of the bitmap are zero.
135
   */
136
0
  if (new_end > bmap->end) {
137
0
    bitno = bmap->real_end;
138
0
    if (bitno > new_end)
139
0
      bitno = new_end;
140
0
    for (; bitno > bmap->end; bitno--)
141
0
      ext2fs_clear_bit64(bitno - bmap->start, bp->bitarray);
142
0
  }
143
0
  if (new_real_end == bmap->real_end) {
144
0
    bmap->end = new_end;
145
0
    return 0;
146
0
  }
147
148
0
  size = ((bmap->real_end - bmap->start) / 8) + 1;
149
0
  new_size = ((new_real_end - bmap->start) / 8) + 1;
150
151
0
  if (size != new_size) {
152
0
    retval = ext2fs_resize_mem(size, new_size, &bp->bitarray);
153
0
    if (retval)
154
0
      return retval;
155
0
  }
156
0
  if (new_size > size)
157
0
    memset(bp->bitarray + size, 0, new_size - size);
158
159
0
  bmap->end = new_end;
160
0
  bmap->real_end = new_real_end;
161
0
  return 0;
162
163
0
}
164
165
static int ba_mark_bmap(ext2fs_generic_bitmap_64 bitmap, __u64 arg)
166
0
{
167
0
  ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
168
0
  blk64_t bitno = (blk64_t) arg;
169
170
0
  return ext2fs_set_bit64(bitno - bitmap->start, bp->bitarray);
171
0
}
172
173
static int ba_unmark_bmap(ext2fs_generic_bitmap_64 bitmap, __u64 arg)
174
0
{
175
0
  ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
176
0
  blk64_t bitno = (blk64_t) arg;
177
178
0
  return ext2fs_clear_bit64(bitno - bitmap->start, bp->bitarray);
179
0
}
180
181
static int ba_test_bmap(ext2fs_generic_bitmap_64 bitmap, __u64 arg)
182
0
{
183
0
  ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
184
0
  blk64_t bitno = (blk64_t) arg;
185
186
0
  return ext2fs_test_bit64(bitno - bitmap->start, bp->bitarray);
187
0
}
188
189
static void ba_mark_bmap_extent(ext2fs_generic_bitmap_64 bitmap, __u64 arg,
190
        unsigned int num)
191
0
{
192
0
  ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
193
0
  blk64_t bitno = (blk64_t) arg;
194
0
  unsigned int i;
195
196
0
  for (i = 0; i < num; i++)
197
0
    ext2fs_fast_set_bit64(bitno + i - bitmap->start, bp->bitarray);
198
0
}
199
200
static void ba_unmark_bmap_extent(ext2fs_generic_bitmap_64 bitmap, __u64 arg,
201
          unsigned int num)
202
0
{
203
0
  ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
204
0
  blk64_t bitno = (blk64_t) arg;
205
0
  unsigned int i;
206
207
0
  for (i = 0; i < num; i++)
208
0
    ext2fs_fast_clear_bit64(bitno + i - bitmap->start, bp->bitarray);
209
0
}
210
211
static int ba_test_clear_bmap_extent(ext2fs_generic_bitmap_64 bitmap,
212
             __u64 start, unsigned int len)
213
0
{
214
0
  ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
215
0
  __u64 start_byte, len_byte = len >> 3;
216
0
  unsigned int start_bit, len_bit = len % 8;
217
0
  unsigned int first_bit = 0;
218
0
  unsigned int last_bit  = 0;
219
0
  int mark_count = 0;
220
0
  int mark_bit = 0;
221
0
  int i;
222
0
  const char *ADDR;
223
224
0
  ADDR = bp->bitarray;
225
0
  start -= bitmap->start;
226
0
  start_byte = start >> 3;
227
0
  start_bit = start % 8;
228
229
0
  if (start_bit != 0) {
230
    /*
231
     * The compared start block number or start inode number
232
     * is not the first bit in a byte.
233
     */
234
0
    mark_count = 8 - start_bit;
235
0
    if (len < 8 - start_bit) {
236
0
      mark_count = (int)len;
237
0
      mark_bit = len + start_bit - 1;
238
0
    } else
239
0
      mark_bit = 7;
240
241
0
    for (i = mark_count; i > 0; i--, mark_bit--)
242
0
      first_bit |= 1 << mark_bit;
243
244
    /*
245
     * Compare blocks or inodes in the first byte.
246
     * If there is any marked bit, this function returns 0.
247
     */
248
0
    if (first_bit & ADDR[start_byte])
249
0
      return 0;
250
0
    else if (len <= 8 - start_bit)
251
0
      return 1;
252
253
0
    start_byte++;
254
0
    len_bit = (len - mark_count) % 8;
255
0
    len_byte = (len - mark_count) >> 3;
256
0
  }
257
258
  /*
259
   * The compared start block number or start inode number is
260
   * the first bit in a byte.
261
   */
262
0
  if (len_bit != 0) {
263
    /*
264
     * The compared end block number or end inode number is
265
     * not the last bit in a byte.
266
     */
267
0
    for (mark_bit = len_bit - 1; mark_bit >= 0; mark_bit--)
268
0
      last_bit |= 1 << mark_bit;
269
270
    /*
271
     * Compare blocks or inodes in the last byte.
272
     * If there is any marked bit, this function returns 0.
273
     */
274
0
    if (last_bit & ADDR[start_byte + len_byte])
275
0
      return 0;
276
0
    else if (len_byte == 0)
277
0
      return 1;
278
0
  }
279
280
  /* Check whether all bytes are 0 */
281
0
  return ext2fs_mem_is_zero(ADDR + start_byte, len_byte);
282
0
}
283
284
285
static errcode_t ba_set_bmap_range(ext2fs_generic_bitmap_64 bitmap,
286
             __u64 start, size_t num, void *in)
287
0
{
288
0
  ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
289
290
0
  memcpy (bp->bitarray + (start >> 3), in, (num + 7) >> 3);
291
292
0
  return 0;
293
0
}
294
295
static errcode_t ba_get_bmap_range(ext2fs_generic_bitmap_64 bitmap,
296
             __u64 start, size_t num, void *out)
297
0
{
298
0
  ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
299
300
0
  memcpy (out, bp->bitarray + (start >> 3), (num + 7) >> 3);
301
302
0
  return 0;
303
0
}
304
305
static void ba_clear_bmap(ext2fs_generic_bitmap_64 bitmap)
306
0
{
307
0
  ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
308
309
0
  memset(bp->bitarray, 0,
310
0
         (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1));
311
0
}
312
313
#ifdef ENABLE_BMAP_STATS
314
static void ba_print_stats(ext2fs_generic_bitmap_64 bitmap)
315
0
{
316
0
  fprintf(stderr, "%16llu Bytes used by bitarray\n", (unsigned long long)
317
0
    ((bitmap->real_end - bitmap->start) >> 3) + 1 +
318
0
    sizeof(struct ext2fs_ba_private_struct));
319
0
}
320
#else
321
static void ba_print_stats(ext2fs_generic_bitmap_64 bitmap EXT2FS_ATTR((unused)))
322
{
323
}
324
#endif
325
326
/* Find the first zero bit between start and end, inclusive. */
327
static errcode_t ba_find_first_zero(ext2fs_generic_bitmap_64 bitmap,
328
            __u64 start, __u64 end, __u64 *out)
329
0
{
330
0
  ext2fs_ba_private bp = (ext2fs_ba_private)bitmap->private;
331
0
  unsigned long bitpos = start - bitmap->start;
332
0
  unsigned long count = end - start + 1;
333
0
  int byte_found = 0; /* whether a != 0xff byte has been found */
334
0
  const unsigned char *pos;
335
0
  unsigned long max_loop_count, i;
336
337
  /* scan bits until we hit a byte boundary */
338
0
  while ((bitpos & 0x7) != 0 && count > 0) {
339
0
    if (!ext2fs_test_bit64(bitpos, bp->bitarray)) {
340
0
      *out = bitpos + bitmap->start;
341
0
      return 0;
342
0
    }
343
0
    bitpos++;
344
0
    count--;
345
0
  }
346
347
0
  if (!count)
348
0
    return ENOENT;
349
350
0
  pos = ((unsigned char *)bp->bitarray) + (bitpos >> 3);
351
  /* scan bytes until 8-byte (64-bit) aligned */
352
0
  while (count >= 8 && (((uintptr_t)pos) & 0x07)) {
353
0
    if (*pos != 0xff) {
354
0
      byte_found = 1;
355
0
      break;
356
0
    }
357
0
    pos++;
358
0
    count -= 8;
359
0
    bitpos += 8;
360
0
  }
361
362
0
  if (!byte_found) {
363
0
    max_loop_count = count >> 6; /* 8-byte blocks */
364
0
    i = max_loop_count;
365
0
    while (i) {
366
0
      if (*((const __u64 *)pos) != ((__u64)-1))
367
0
        break;
368
0
      pos += 8;
369
0
      i--;
370
0
    }
371
0
    count -= 64 * (max_loop_count - i);
372
0
    bitpos += 64 * (max_loop_count - i);
373
374
0
    max_loop_count = count >> 3;
375
0
    i = max_loop_count;
376
0
    while (i) {
377
0
      if (*pos != 0xff) {
378
0
        byte_found = 1;
379
0
        break;
380
0
      }
381
0
      pos++;
382
0
      i--;
383
0
    }
384
0
    count -= 8 * (max_loop_count - i);
385
0
    bitpos += 8 * (max_loop_count - i);
386
0
  }
387
388
  /* Here either count < 8 or byte_found == 1. */
389
0
  while (count-- > 0) {
390
0
    if (!ext2fs_test_bit64(bitpos, bp->bitarray)) {
391
0
      *out = bitpos + bitmap->start;
392
0
      return 0;
393
0
    }
394
0
    bitpos++;
395
0
  }
396
397
0
  return ENOENT;
398
0
}
399
400
/* Find the first one bit between start and end, inclusive. */
401
static errcode_t ba_find_first_set(ext2fs_generic_bitmap_64 bitmap,
402
            __u64 start, __u64 end, __u64 *out)
403
0
{
404
0
  ext2fs_ba_private bp = (ext2fs_ba_private)bitmap->private;
405
0
  unsigned long bitpos = start - bitmap->start;
406
0
  unsigned long count = end - start + 1;
407
0
  int byte_found = 0; /* whether a != 0xff byte has been found */
408
0
  const unsigned char *pos;
409
0
  unsigned long max_loop_count, i;
410
411
  /* scan bits until we hit a byte boundary */
412
0
  while ((bitpos & 0x7) != 0 && count > 0) {
413
0
    if (ext2fs_test_bit64(bitpos, bp->bitarray)) {
414
0
      *out = bitpos + bitmap->start;
415
0
      return 0;
416
0
    }
417
0
    bitpos++;
418
0
    count--;
419
0
  }
420
421
0
  if (!count)
422
0
    return ENOENT;
423
424
0
  pos = ((unsigned char *)bp->bitarray) + (bitpos >> 3);
425
  /* scan bytes until 8-byte (64-bit) aligned */
426
0
  while (count >= 8 && (((uintptr_t)pos) & 0x07)) {
427
0
    if (*pos != 0) {
428
0
      byte_found = 1;
429
0
      break;
430
0
    }
431
0
    pos++;
432
0
    count -= 8;
433
0
    bitpos += 8;
434
0
  }
435
436
0
  if (!byte_found) {
437
0
    max_loop_count = count >> 6; /* 8-byte blocks */
438
0
    i = max_loop_count;
439
0
    while (i) {
440
0
      if (*((const __u64 *)pos) != 0)
441
0
        break;
442
0
      pos += 8;
443
0
      i--;
444
0
    }
445
0
    count -= 64 * (max_loop_count - i);
446
0
    bitpos += 64 * (max_loop_count - i);
447
448
0
    max_loop_count = count >> 3;
449
0
    i = max_loop_count;
450
0
    while (i) {
451
0
      if (*pos != 0) {
452
0
        byte_found = 1;
453
0
        break;
454
0
      }
455
0
      pos++;
456
0
      i--;
457
0
    }
458
0
    count -= 8 * (max_loop_count - i);
459
0
    bitpos += 8 * (max_loop_count - i);
460
0
  }
461
462
  /* Here either count < 8 or byte_found == 1. */
463
0
  while (count-- > 0) {
464
0
    if (ext2fs_test_bit64(bitpos, bp->bitarray)) {
465
0
      *out = bitpos + bitmap->start;
466
0
      return 0;
467
0
    }
468
0
    bitpos++;
469
0
  }
470
471
0
  return ENOENT;
472
0
}
473
474
struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = {
475
  .type = EXT2FS_BMAP64_BITARRAY,
476
  .new_bmap = ba_new_bmap,
477
  .free_bmap = ba_free_bmap,
478
  .copy_bmap = ba_copy_bmap,
479
  .resize_bmap = ba_resize_bmap,
480
  .mark_bmap = ba_mark_bmap,
481
  .unmark_bmap = ba_unmark_bmap,
482
  .test_bmap = ba_test_bmap,
483
  .test_clear_bmap_extent = ba_test_clear_bmap_extent,
484
  .mark_bmap_extent = ba_mark_bmap_extent,
485
  .unmark_bmap_extent = ba_unmark_bmap_extent,
486
  .set_bmap_range = ba_set_bmap_range,
487
  .get_bmap_range = ba_get_bmap_range,
488
  .clear_bmap = ba_clear_bmap,
489
  .print_stats = ba_print_stats,
490
  .find_first_zero = ba_find_first_zero,
491
  .find_first_set = ba_find_first_set
492
};