| /* |
| * blkmap64_ba.c --- Simple bitarray implementation for bitmaps |
| * |
| * Copyright (C) 2008 Theodore Ts'o. |
| * |
| * %Begin-Header% |
| * This file may be redistributed under the terms of the GNU Public |
| * License. |
| * %End-Header% |
| */ |
| |
| #include <stdio.h> |
| #include <string.h> |
| #if HAVE_UNISTD_H |
| #include <unistd.h> |
| #endif |
| #include <fcntl.h> |
| #include <time.h> |
| #if HAVE_SYS_STAT_H |
| #include <sys/stat.h> |
| #endif |
| #if HAVE_SYS_TYPES_H |
| #include <sys/types.h> |
| #endif |
| |
| #include "ext2_fs.h" |
| #include "ext2fsP.h" |
| #include "bmap64.h" |
| |
| /* |
| * Private data for bit array implementation of bitmap ops. |
| * Currently, this is just a pointer to our big flat hunk of memory, |
| * exactly equivalent to the old-skool char * bitmap member. |
| */ |
| |
| struct ext2fs_ba_private_struct { |
| char *bitarray; |
| }; |
| |
| typedef struct ext2fs_ba_private_struct *ext2fs_ba_private; |
| |
| static errcode_t ba_alloc_private_data (ext2fs_generic_bitmap bitmap) |
| { |
| ext2fs_ba_private bp; |
| errcode_t retval; |
| size_t size; |
| |
| /* |
| * Since we only have the one pointer, we could just shove our |
| * private data in the void *private field itself, but then |
| * we'd have to do a fair bit of rewriting if we ever added a |
| * field. I'm agnostic. |
| */ |
| retval = ext2fs_get_mem(sizeof (ext2fs_ba_private), &bp); |
| if (retval) |
| return retval; |
| |
| size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1); |
| |
| retval = ext2fs_get_mem(size, &bp->bitarray); |
| if (retval) { |
| ext2fs_free_mem(&bp); |
| bp = 0; |
| return retval; |
| } |
| bitmap->private = (void *) bp; |
| return 0; |
| } |
| |
| static errcode_t ba_new_bmap(ext2_filsys fs EXT2FS_ATTR((unused)), |
| ext2fs_generic_bitmap bitmap) |
| { |
| ext2fs_ba_private bp; |
| errcode_t retval; |
| size_t size; |
| |
| retval = ba_alloc_private_data (bitmap); |
| if (retval) |
| return retval; |
| |
| bp = (ext2fs_ba_private) bitmap->private; |
| size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1); |
| memset(bp->bitarray, 0, size); |
| |
| return 0; |
| } |
| |
| static void ba_free_bmap(ext2fs_generic_bitmap bitmap) |
| { |
| ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; |
| |
| if (!bp) |
| return; |
| |
| if (bp->bitarray) { |
| ext2fs_free_mem (&bp->bitarray); |
| bp->bitarray = 0; |
| } |
| ext2fs_free_mem (&bp); |
| bp = 0; |
| } |
| |
| static errcode_t ba_copy_bmap(ext2fs_generic_bitmap src, |
| ext2fs_generic_bitmap dest) |
| { |
| ext2fs_ba_private src_bp = (ext2fs_ba_private) src->private; |
| ext2fs_ba_private dest_bp; |
| errcode_t retval; |
| size_t size; |
| |
| retval = ba_alloc_private_data (dest); |
| if (retval) |
| return retval; |
| |
| dest_bp = (ext2fs_ba_private) dest->private; |
| |
| size = (size_t) (((src->real_end - src->start) / 8) + 1); |
| memcpy (dest_bp->bitarray, src_bp->bitarray, size); |
| |
| return 0; |
| } |
| |
| static errcode_t ba_resize_bmap(ext2fs_generic_bitmap bmap, |
| __u64 new_end, __u64 new_real_end) |
| { |
| ext2fs_ba_private bp = (ext2fs_ba_private) bmap->private; |
| errcode_t retval; |
| size_t size, new_size; |
| __u64 bitno; |
| |
| /* |
| * If we're expanding the bitmap, make sure all of the new |
| * parts of the bitmap are zero. |
| */ |
| if (new_end > bmap->end) { |
| bitno = bmap->real_end; |
| if (bitno > new_end) |
| bitno = new_end; |
| for (; bitno > bmap->end; bitno--) |
| ext2fs_clear_bit64(bitno - bmap->start, bp->bitarray); |
| } |
| if (new_real_end == bmap->real_end) { |
| bmap->end = new_end; |
| return 0; |
| } |
| |
| size = ((bmap->real_end - bmap->start) / 8) + 1; |
| new_size = ((new_real_end - bmap->start) / 8) + 1; |
| |
| if (size != new_size) { |
| retval = ext2fs_resize_mem(size, new_size, &bp->bitarray); |
| if (retval) |
| return retval; |
| } |
| if (new_size > size) |
| memset(bp->bitarray + size, 0, new_size - size); |
| |
| bmap->end = new_end; |
| bmap->real_end = new_real_end; |
| return 0; |
| |
| } |
| |
| static int ba_mark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg) |
| { |
| ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; |
| blk64_t bitno = (blk64_t) arg; |
| |
| return ext2fs_set_bit64(bitno - bitmap->start, bp->bitarray); |
| } |
| |
| static int ba_unmark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg) |
| { |
| ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; |
| blk64_t bitno = (blk64_t) arg; |
| |
| return ext2fs_clear_bit64(bitno - bitmap->start, bp->bitarray); |
| } |
| |
| static int ba_test_bmap(ext2fs_generic_bitmap bitmap, __u64 arg) |
| { |
| ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; |
| blk64_t bitno = (blk64_t) arg; |
| |
| return ext2fs_test_bit64(bitno - bitmap->start, bp->bitarray); |
| } |
| |
| static void ba_mark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg, |
| unsigned int num) |
| { |
| ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; |
| blk64_t bitno = (blk64_t) arg; |
| unsigned int i; |
| |
| for (i = 0; i < num; i++) |
| ext2fs_fast_set_bit64(bitno + i - bitmap->start, bp->bitarray); |
| } |
| |
| static void ba_unmark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg, |
| unsigned int num) |
| { |
| ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; |
| blk64_t bitno = (blk64_t) arg; |
| unsigned int i; |
| |
| for (i = 0; i < num; i++) |
| ext2fs_fast_clear_bit64(bitno + i - bitmap->start, bp->bitarray); |
| } |
| |
| static int ba_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap, |
| __u64 start, unsigned int len) |
| { |
| ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; |
| __u64 start_byte, len_byte = len >> 3; |
| unsigned int start_bit, len_bit = len % 8; |
| unsigned int first_bit = 0; |
| unsigned int last_bit = 0; |
| int mark_count = 0; |
| int mark_bit = 0; |
| int i; |
| const char *ADDR; |
| |
| ADDR = bp->bitarray; |
| start -= bitmap->start; |
| start_byte = start >> 3; |
| start_bit = start % 8; |
| |
| if (start_bit != 0) { |
| /* |
| * The compared start block number or start inode number |
| * is not the first bit in a byte. |
| */ |
| mark_count = 8 - start_bit; |
| if (len < 8 - start_bit) { |
| mark_count = (int)len; |
| mark_bit = len + start_bit - 1; |
| } else |
| mark_bit = 7; |
| |
| for (i = mark_count; i > 0; i--, mark_bit--) |
| first_bit |= 1 << mark_bit; |
| |
| /* |
| * Compare blocks or inodes in the first byte. |
| * If there is any marked bit, this function returns 0. |
| */ |
| if (first_bit & ADDR[start_byte]) |
| return 0; |
| else if (len <= 8 - start_bit) |
| return 1; |
| |
| start_byte++; |
| len_bit = (len - mark_count) % 8; |
| len_byte = (len - mark_count) >> 3; |
| } |
| |
| /* |
| * The compared start block number or start inode number is |
| * the first bit in a byte. |
| */ |
| if (len_bit != 0) { |
| /* |
| * The compared end block number or end inode number is |
| * not the last bit in a byte. |
| */ |
| for (mark_bit = len_bit - 1; mark_bit >= 0; mark_bit--) |
| last_bit |= 1 << mark_bit; |
| |
| /* |
| * Compare blocks or inodes in the last byte. |
| * If there is any marked bit, this function returns 0. |
| */ |
| if (last_bit & ADDR[start_byte + len_byte]) |
| return 0; |
| else if (len_byte == 0) |
| return 1; |
| } |
| |
| /* Check whether all bytes are 0 */ |
| return ext2fs_mem_is_zero(ADDR + start_byte, len_byte); |
| } |
| |
| |
| static errcode_t ba_set_bmap_range(ext2fs_generic_bitmap bitmap, |
| __u64 start, size_t num, void *in) |
| { |
| ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; |
| |
| memcpy (bp->bitarray + (start >> 3), in, (num + 7) >> 3); |
| |
| return 0; |
| } |
| |
| static errcode_t ba_get_bmap_range(ext2fs_generic_bitmap bitmap, |
| __u64 start, size_t num, void *out) |
| { |
| ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; |
| |
| memcpy (out, bp->bitarray + (start >> 3), (num + 7) >> 3); |
| |
| return 0; |
| } |
| |
| static void ba_clear_bmap(ext2fs_generic_bitmap bitmap) |
| { |
| ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; |
| |
| memset(bp->bitarray, 0, |
| (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1)); |
| } |
| |
| static void ba_print_stats(ext2fs_generic_bitmap bitmap) |
| { |
| fprintf(stderr, "%16llu Bytes used by bitarray\n", |
| ((bitmap->real_end - bitmap->start) >> 3) + 1 + |
| sizeof(struct ext2fs_ba_private_struct)); |
| } |
| |
| /* Find the first zero bit between start and end, inclusive. */ |
| static errcode_t ba_find_first_zero(ext2fs_generic_bitmap bitmap, |
| __u64 start, __u64 end, __u64 *out) |
| { |
| ext2fs_ba_private bp = (ext2fs_ba_private)bitmap->private; |
| unsigned long bitpos = start - bitmap->start; |
| unsigned long count = end - start + 1; |
| int byte_found = 0; /* whether a != 0xff byte has been found */ |
| const unsigned char *pos; |
| unsigned long max_loop_count, i; |
| |
| if (start < bitmap->start || end > bitmap->end || start > end) |
| return EINVAL; |
| |
| if (bitmap->cluster_bits) |
| return EINVAL; |
| |
| /* scan bits until we hit a byte boundary */ |
| while ((bitpos & 0x7) != 0 && count > 0) { |
| if (!ext2fs_test_bit64(bitpos, bp->bitarray)) { |
| *out = bitpos + bitmap->start; |
| return 0; |
| } |
| bitpos++; |
| count--; |
| } |
| |
| if (!count) |
| return ENOENT; |
| |
| pos = ((unsigned char *)bp->bitarray) + (bitpos >> 3); |
| /* scan bytes until 8-byte (64-bit) aligned */ |
| while (count >= 8 && (((unsigned long)pos) & 0x07)) { |
| if (*pos != 0xff) { |
| byte_found = 1; |
| break; |
| } |
| pos++; |
| count -= 8; |
| bitpos += 8; |
| } |
| |
| if (!byte_found) { |
| max_loop_count = count >> 6; /* 8-byte blocks */ |
| i = max_loop_count; |
| while (i) { |
| if (*((const __u64 *)pos) != ((__u64)-1)) |
| break; |
| pos += 8; |
| i--; |
| } |
| count -= 64 * (max_loop_count - i); |
| bitpos += 64 * (max_loop_count - i); |
| |
| max_loop_count = count >> 3; |
| i = max_loop_count; |
| while (i) { |
| if (*pos != 0xff) { |
| byte_found = 1; |
| break; |
| } |
| pos++; |
| i--; |
| } |
| count -= 8 * (max_loop_count - i); |
| bitpos += 8 * (max_loop_count - i); |
| } |
| |
| /* Here either count < 8 or byte_found == 1. */ |
| while (count-- > 0) { |
| if (!ext2fs_test_bit64(bitpos, bp->bitarray)) { |
| *out = bitpos + bitmap->start; |
| return 0; |
| } |
| bitpos++; |
| } |
| |
| return ENOENT; |
| } |
| |
| struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = { |
| .type = EXT2FS_BMAP64_BITARRAY, |
| .new_bmap = ba_new_bmap, |
| .free_bmap = ba_free_bmap, |
| .copy_bmap = ba_copy_bmap, |
| .resize_bmap = ba_resize_bmap, |
| .mark_bmap = ba_mark_bmap, |
| .unmark_bmap = ba_unmark_bmap, |
| .test_bmap = ba_test_bmap, |
| .test_clear_bmap_extent = ba_test_clear_bmap_extent, |
| .mark_bmap_extent = ba_mark_bmap_extent, |
| .unmark_bmap_extent = ba_unmark_bmap_extent, |
| .set_bmap_range = ba_set_bmap_range, |
| .get_bmap_range = ba_get_bmap_range, |
| .clear_bmap = ba_clear_bmap, |
| .print_stats = ba_print_stats, |
| .find_first_zero = ba_find_first_zero |
| }; |