2 * blkmap64_ba.c --- Simple bitarray implementation for bitmaps
4 * Copyright (C) 2008 Theodore Ts'o.
7 * This file may be redistributed under the terms of the GNU Public
24 #include <sys/types.h>
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.
37 struct ext2fs_ba_private_struct {
41 typedef struct ext2fs_ba_private_struct *ext2fs_ba_private;
43 static errcode_t ba_alloc_private_data (ext2fs_generic_bitmap bitmap)
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.
55 retval = ext2fs_get_mem(sizeof (ext2fs_ba_private), &bp);
59 size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1);
61 retval = ext2fs_get_mem(size, &bp->bitarray);
67 bitmap->private = (void *) bp;
71 static errcode_t ba_new_bmap(ext2_filsys fs EXT2FS_ATTR((unused)),
72 ext2fs_generic_bitmap bitmap)
78 retval = ba_alloc_private_data (bitmap);
82 bp = (ext2fs_ba_private) bitmap->private;
83 size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1);
84 memset(bp->bitarray, 0, size);
89 static void ba_free_bmap(ext2fs_generic_bitmap bitmap)
91 ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
97 ext2fs_free_mem (&bp->bitarray);
100 ext2fs_free_mem (&bp);
104 static errcode_t ba_copy_bmap(ext2fs_generic_bitmap src,
105 ext2fs_generic_bitmap dest)
107 ext2fs_ba_private src_bp = (ext2fs_ba_private) src->private;
108 ext2fs_ba_private dest_bp;
112 retval = ba_alloc_private_data (dest);
116 dest_bp = (ext2fs_ba_private) dest->private;
118 size = (size_t) (((src->real_end - src->start) / 8) + 1);
119 memcpy (dest_bp->bitarray, src_bp->bitarray, size);
124 static errcode_t ba_resize_bmap(ext2fs_generic_bitmap bmap,
125 __u64 new_end, __u64 new_real_end)
127 ext2fs_ba_private bp = (ext2fs_ba_private) bmap->private;
129 size_t size, new_size;
133 * If we're expanding the bitmap, make sure all of the new
134 * parts of the bitmap are zero.
136 if (new_end > bmap->end) {
137 bitno = bmap->real_end;
140 for (; bitno > bmap->end; bitno--)
141 ext2fs_clear_bit64(bitno - bmap->start, bp->bitarray);
143 if (new_real_end == bmap->real_end) {
148 size = ((bmap->real_end - bmap->start) / 8) + 1;
149 new_size = ((new_real_end - bmap->start) / 8) + 1;
151 if (size != new_size) {
152 retval = ext2fs_resize_mem(size, new_size, &bp->bitarray);
157 memset(bp->bitarray + size, 0, new_size - size);
160 bmap->real_end = new_real_end;
165 static int ba_mark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
167 ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
168 blk64_t bitno = (blk64_t) arg;
170 return ext2fs_set_bit64(bitno - bitmap->start, bp->bitarray);
173 static int ba_unmark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
175 ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
176 blk64_t bitno = (blk64_t) arg;
178 return ext2fs_clear_bit64(bitno - bitmap->start, bp->bitarray);
181 static int ba_test_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
183 ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
184 blk64_t bitno = (blk64_t) arg;
186 return ext2fs_test_bit64(bitno - bitmap->start, bp->bitarray);
189 static void ba_mark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
192 ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
193 blk64_t bitno = (blk64_t) arg;
196 for (i = 0; i < num; i++)
197 ext2fs_fast_set_bit64(bitno + i - bitmap->start, bp->bitarray);
200 static void ba_unmark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
203 ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
204 blk64_t bitno = (blk64_t) arg;
207 for (i = 0; i < num; i++)
208 ext2fs_fast_clear_bit64(bitno + i - bitmap->start, bp->bitarray);
211 static int ba_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap,
212 __u64 start, unsigned int len)
214 ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
215 __u64 start_byte, len_byte = len >> 3;
216 unsigned int start_bit, len_bit = len % 8;
217 unsigned int first_bit = 0;
218 unsigned int last_bit = 0;
225 start -= bitmap->start;
226 start_byte = start >> 3;
227 start_bit = start % 8;
229 if (start_bit != 0) {
231 * The compared start block number or start inode number
232 * is not the first bit in a byte.
234 mark_count = 8 - start_bit;
235 if (len < 8 - start_bit) {
236 mark_count = (int)len;
237 mark_bit = len + start_bit - 1;
241 for (i = mark_count; i > 0; i--, mark_bit--)
242 first_bit |= 1 << mark_bit;
245 * Compare blocks or inodes in the first byte.
246 * If there is any marked bit, this function returns 0.
248 if (first_bit & ADDR[start_byte])
250 else if (len <= 8 - start_bit)
254 len_bit = (len - mark_count) % 8;
255 len_byte = (len - mark_count) >> 3;
259 * The compared start block number or start inode number is
260 * the first bit in a byte.
264 * The compared end block number or end inode number is
265 * not the last bit in a byte.
267 for (mark_bit = len_bit - 1; mark_bit >= 0; mark_bit--)
268 last_bit |= 1 << mark_bit;
271 * Compare blocks or inodes in the last byte.
272 * If there is any marked bit, this function returns 0.
274 if (last_bit & ADDR[start_byte + len_byte])
276 else if (len_byte == 0)
280 /* Check whether all bytes are 0 */
281 return ext2fs_mem_is_zero(ADDR + start_byte, len_byte);
285 static errcode_t ba_set_bmap_range(ext2fs_generic_bitmap bitmap,
286 __u64 start, size_t num, void *in)
288 ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
290 memcpy (bp->bitarray + (start >> 3), in, (num + 7) >> 3);
295 static errcode_t ba_get_bmap_range(ext2fs_generic_bitmap bitmap,
296 __u64 start, size_t num, void *out)
298 ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
300 memcpy (out, bp->bitarray + (start >> 3), (num + 7) >> 3);
305 static void ba_clear_bmap(ext2fs_generic_bitmap bitmap)
307 ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
309 memset(bp->bitarray, 0,
310 (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1));
313 #ifdef ENABLE_BMAP_STATS
314 static void ba_print_stats(ext2fs_generic_bitmap bitmap)
316 fprintf(stderr, "%16llu Bytes used by bitarray\n",
317 ((bitmap->real_end - bitmap->start) >> 3) + 1 +
318 sizeof(struct ext2fs_ba_private_struct));
321 static void ba_print_stats(ext2fs_generic_bitmap bitmap EXT2FS_ATTR((unused)))
326 /* Find the first zero bit between start and end, inclusive. */
327 static errcode_t ba_find_first_zero(ext2fs_generic_bitmap bitmap,
328 __u64 start, __u64 end, __u64 *out)
330 ext2fs_ba_private bp = (ext2fs_ba_private)bitmap->private;
331 unsigned long bitpos = start - bitmap->start;
332 unsigned long count = end - start + 1;
333 int byte_found = 0; /* whether a != 0xff byte has been found */
334 const unsigned char *pos;
335 unsigned long max_loop_count, i;
337 /* scan bits until we hit a byte boundary */
338 while ((bitpos & 0x7) != 0 && count > 0) {
339 if (!ext2fs_test_bit64(bitpos, bp->bitarray)) {
340 *out = bitpos + bitmap->start;
350 pos = ((unsigned char *)bp->bitarray) + (bitpos >> 3);
351 /* scan bytes until 8-byte (64-bit) aligned */
352 while (count >= 8 && (((unsigned long)pos) & 0x07)) {
363 max_loop_count = count >> 6; /* 8-byte blocks */
366 if (*((const __u64 *)pos) != ((__u64)-1))
371 count -= 64 * (max_loop_count - i);
372 bitpos += 64 * (max_loop_count - i);
374 max_loop_count = count >> 3;
384 count -= 8 * (max_loop_count - i);
385 bitpos += 8 * (max_loop_count - i);
388 /* Here either count < 8 or byte_found == 1. */
389 while (count-- > 0) {
390 if (!ext2fs_test_bit64(bitpos, bp->bitarray)) {
391 *out = bitpos + bitmap->start;
400 /* Find the first one bit between start and end, inclusive. */
401 static errcode_t ba_find_first_set(ext2fs_generic_bitmap bitmap,
402 __u64 start, __u64 end, __u64 *out)
404 ext2fs_ba_private bp = (ext2fs_ba_private)bitmap->private;
405 unsigned long bitpos = start - bitmap->start;
406 unsigned long count = end - start + 1;
407 int byte_found = 0; /* whether a != 0xff byte has been found */
408 const unsigned char *pos;
409 unsigned long max_loop_count, i;
411 /* scan bits until we hit a byte boundary */
412 while ((bitpos & 0x7) != 0 && count > 0) {
413 if (ext2fs_test_bit64(bitpos, bp->bitarray)) {
414 *out = bitpos + bitmap->start;
424 pos = ((unsigned char *)bp->bitarray) + (bitpos >> 3);
425 /* scan bytes until 8-byte (64-bit) aligned */
426 while (count >= 8 && (((unsigned long)pos) & 0x07)) {
437 max_loop_count = count >> 6; /* 8-byte blocks */
440 if (*((const __u64 *)pos) != 0)
445 count -= 64 * (max_loop_count - i);
446 bitpos += 64 * (max_loop_count - i);
448 max_loop_count = count >> 3;
458 count -= 8 * (max_loop_count - i);
459 bitpos += 8 * (max_loop_count - i);
462 /* Here either count < 8 or byte_found == 1. */
463 while (count-- > 0) {
464 if (ext2fs_test_bit64(bitpos, bp->bitarray)) {
465 *out = bitpos + bitmap->start;
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