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