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 bitmap) 44 { 45 ext2fs_ba_private bp; 46 errcode_t retval; 47 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 retval = ext2fs_get_mem(sizeof (ext2fs_ba_private), &bp); 56 if (retval) 57 return retval; 58 59 size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1); 60 61 retval = ext2fs_get_mem(size, &bp->bitarray); 62 if (retval) { 63 ext2fs_free_mem(&bp); 64 bp = 0; 65 return retval; 66 } 67 bitmap->private = (void *) bp; 68 return 0; 69 } 70 71 static errcode_t ba_new_bmap(ext2_filsys fs EXT2FS_ATTR((unused)), 72 ext2fs_generic_bitmap bitmap) 73 { 74 ext2fs_ba_private bp; 75 errcode_t retval; 76 size_t size; 77 78 retval = ba_alloc_private_data (bitmap); 79 if (retval) 80 return retval; 81 82 bp = (ext2fs_ba_private) bitmap->private; 83 size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1); 84 memset(bp->bitarray, 0, size); 85 86 return 0; 87 } 88 89 static void ba_free_bmap(ext2fs_generic_bitmap bitmap) 90 { 91 ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; 92 93 if (!bp) 94 return; 95 96 if (bp->bitarray) { 97 ext2fs_free_mem (&bp->bitarray); 98 bp->bitarray = 0; 99 } 100 ext2fs_free_mem (&bp); 101 bp = 0; 102 } 103 104 static errcode_t ba_copy_bmap(ext2fs_generic_bitmap src, 105 ext2fs_generic_bitmap dest) 106 { 107 ext2fs_ba_private src_bp = (ext2fs_ba_private) src->private; 108 ext2fs_ba_private dest_bp; 109 errcode_t retval; 110 size_t size; 111 112 retval = ba_alloc_private_data (dest); 113 if (retval) 114 return retval; 115 116 dest_bp = (ext2fs_ba_private) dest->private; 117 118 size = (size_t) (((src->real_end - src->start) / 8) + 1); 119 memcpy (dest_bp->bitarray, src_bp->bitarray, size); 120 121 return 0; 122 } 123 124 static errcode_t ba_resize_bmap(ext2fs_generic_bitmap bmap, 125 __u64 new_end, __u64 new_real_end) 126 { 127 ext2fs_ba_private bp = (ext2fs_ba_private) bmap->private; 128 errcode_t retval; 129 size_t size, new_size; 130 __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 if (new_end > bmap->end) { 137 bitno = bmap->real_end; 138 if (bitno > new_end) 139 bitno = new_end; 140 for (; bitno > bmap->end; bitno--) 141 ext2fs_clear_bit64(bitno - bmap->start, bp->bitarray); 142 } 143 if (new_real_end == bmap->real_end) { 144 bmap->end = new_end; 145 return 0; 146 } 147 148 size = ((bmap->real_end - bmap->start) / 8) + 1; 149 new_size = ((new_real_end - bmap->start) / 8) + 1; 150 151 if (size != new_size) { 152 retval = ext2fs_resize_mem(size, new_size, &bp->bitarray); 153 if (retval) 154 return retval; 155 } 156 if (new_size > size) 157 memset(bp->bitarray + size, 0, new_size - size); 158 159 bmap->end = new_end; 160 bmap->real_end = new_real_end; 161 return 0; 162 163 } 164 165 static int ba_mark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg) 166 { 167 ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; 168 blk64_t bitno = (blk64_t) arg; 169 170 return ext2fs_set_bit64(bitno - bitmap->start, bp->bitarray); 171 } 172 173 static int ba_unmark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg) 174 { 175 ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; 176 blk64_t bitno = (blk64_t) arg; 177 178 return ext2fs_clear_bit64(bitno - bitmap->start, bp->bitarray); 179 } 180 181 static int ba_test_bmap(ext2fs_generic_bitmap bitmap, __u64 arg) 182 { 183 ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; 184 blk64_t bitno = (blk64_t) arg; 185 186 return ext2fs_test_bit64(bitno - bitmap->start, bp->bitarray); 187 } 188 189 static void ba_mark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg, 190 unsigned int num) 191 { 192 ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; 193 blk64_t bitno = (blk64_t) arg; 194 unsigned int i; 195 196 for (i = 0; i < num; i++) 197 ext2fs_fast_set_bit64(bitno + i - bitmap->start, bp->bitarray); 198 } 199 200 static void ba_unmark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg, 201 unsigned int num) 202 { 203 ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; 204 blk64_t bitno = (blk64_t) arg; 205 unsigned int i; 206 207 for (i = 0; i < num; i++) 208 ext2fs_fast_clear_bit64(bitno + i - bitmap->start, bp->bitarray); 209 } 210 211 static int ba_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap, 212 __u64 start, unsigned int len) 213 { 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; 219 int mark_count = 0; 220 int mark_bit = 0; 221 int i; 222 const char *ADDR; 223 224 ADDR = bp->bitarray; 225 start -= bitmap->start; 226 start_byte = start >> 3; 227 start_bit = start % 8; 228 229 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 mark_count = 8 - start_bit; 235 if (len < 8 - start_bit) { 236 mark_count = (int)len; 237 mark_bit = len + start_bit - 1; 238 } else 239 mark_bit = 7; 240 241 for (i = mark_count; i > 0; i--, mark_bit--) 242 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 if (first_bit & ADDR[start_byte]) 249 return 0; 250 else if (len <= 8 - start_bit) 251 return 1; 252 253 start_byte++; 254 len_bit = (len - mark_count) % 8; 255 len_byte = (len - mark_count) >> 3; 256 } 257 258 /* 259 * The compared start block number or start inode number is 260 * the first bit in a byte. 261 */ 262 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 for (mark_bit = len_bit - 1; mark_bit >= 0; mark_bit--) 268 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 if (last_bit & ADDR[start_byte + len_byte]) 275 return 0; 276 else if (len_byte == 0) 277 return 1; 278 } 279 280 /* Check whether all bytes are 0 */ 281 return ext2fs_mem_is_zero(ADDR + start_byte, len_byte); 282 } 283 284 285 static errcode_t ba_set_bmap_range(ext2fs_generic_bitmap bitmap, 286 __u64 start, size_t num, void *in) 287 { 288 ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; 289 290 memcpy (bp->bitarray + (start >> 3), in, (num + 7) >> 3); 291 292 return 0; 293 } 294 295 static errcode_t ba_get_bmap_range(ext2fs_generic_bitmap bitmap, 296 __u64 start, size_t num, void *out) 297 { 298 ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; 299 300 memcpy (out, bp->bitarray + (start >> 3), (num + 7) >> 3); 301 302 return 0; 303 } 304 305 static void ba_clear_bmap(ext2fs_generic_bitmap bitmap) 306 { 307 ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; 308 309 memset(bp->bitarray, 0, 310 (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1)); 311 } 312 313 #ifdef ENABLE_BMAP_STATS 314 static void ba_print_stats(ext2fs_generic_bitmap bitmap) 315 { 316 fprintf(stderr, "%16llu Bytes used by bitarray\n", 317 ((bitmap->real_end - bitmap->start) >> 3) + 1 + 318 sizeof(struct ext2fs_ba_private_struct)); 319 } 320 #else 321 static void ba_print_stats(ext2fs_generic_bitmap 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 bitmap, 328 __u64 start, __u64 end, __u64 *out) 329 { 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; 336 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; 341 return 0; 342 } 343 bitpos++; 344 count--; 345 } 346 347 if (!count) 348 return ENOENT; 349 350 pos = ((unsigned char *)bp->bitarray) + (bitpos >> 3); 351 /* scan bytes until 8-byte (64-bit) aligned */ 352 while (count >= 8 && (((uintptr_t)pos) & 0x07)) { 353 if (*pos != 0xff) { 354 byte_found = 1; 355 break; 356 } 357 pos++; 358 count -= 8; 359 bitpos += 8; 360 } 361 362 if (!byte_found) { 363 max_loop_count = count >> 6; /* 8-byte blocks */ 364 i = max_loop_count; 365 while (i) { 366 if (*((const __u64 *)pos) != ((__u64)-1)) 367 break; 368 pos += 8; 369 i--; 370 } 371 count -= 64 * (max_loop_count - i); 372 bitpos += 64 * (max_loop_count - i); 373 374 max_loop_count = count >> 3; 375 i = max_loop_count; 376 while (i) { 377 if (*pos != 0xff) { 378 byte_found = 1; 379 break; 380 } 381 pos++; 382 i--; 383 } 384 count -= 8 * (max_loop_count - i); 385 bitpos += 8 * (max_loop_count - i); 386 } 387 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; 392 return 0; 393 } 394 bitpos++; 395 } 396 397 return ENOENT; 398 } 399 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) 403 { 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; 410 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; 415 return 0; 416 } 417 bitpos++; 418 count--; 419 } 420 421 if (!count) 422 return ENOENT; 423 424 pos = ((unsigned char *)bp->bitarray) + (bitpos >> 3); 425 /* scan bytes until 8-byte (64-bit) aligned */ 426 while (count >= 8 && (((uintptr_t)pos) & 0x07)) { 427 if (*pos != 0) { 428 byte_found = 1; 429 break; 430 } 431 pos++; 432 count -= 8; 433 bitpos += 8; 434 } 435 436 if (!byte_found) { 437 max_loop_count = count >> 6; /* 8-byte blocks */ 438 i = max_loop_count; 439 while (i) { 440 if (*((const __u64 *)pos) != 0) 441 break; 442 pos += 8; 443 i--; 444 } 445 count -= 64 * (max_loop_count - i); 446 bitpos += 64 * (max_loop_count - i); 447 448 max_loop_count = count >> 3; 449 i = max_loop_count; 450 while (i) { 451 if (*pos != 0) { 452 byte_found = 1; 453 break; 454 } 455 pos++; 456 i--; 457 } 458 count -= 8 * (max_loop_count - i); 459 bitpos += 8 * (max_loop_count - i); 460 } 461 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; 466 return 0; 467 } 468 bitpos++; 469 } 470 471 return ENOENT; 472 } 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 }; 493
