1 /* 2 * gen_bitmap.c --- Generic (32-bit) bitmap routines 3 * 4 * Copyright (C) 2001 Theodore Ts'o. 5 * 6 * %Begin-Header% 7 * This file may be redistributed under the terms of the GNU Library 8 * General Public License, version 2. 9 * %End-Header% 10 */ 11 12 13 #include "config.h" 14 #include <stdio.h> 15 #include <string.h> 16 #if HAVE_UNISTD_H 17 #include <unistd.h> 18 #endif 19 #include <fcntl.h> 20 #include <time.h> 21 #if HAVE_SYS_STAT_H 22 #include <sys/stat.h> 23 #endif 24 #if HAVE_SYS_TYPES_H 25 #include <sys/types.h> 26 #endif 27 28 #include "ext2_fs.h" 29 #include "ext2fsP.h" 30 31 struct ext2fs_struct_generic_bitmap { 32 errcode_t magic; 33 ext2_filsys fs; 34 __u32 start, end; 35 __u32 real_end; 36 char * description; 37 char * bitmap; 38 errcode_t base_error_code; 39 __u32 reserved[7]; 40 }; 41 42 #define EXT2FS_IS_32_BITMAP(bmap) \ 43 (((bmap)->magic == EXT2_ET_MAGIC_GENERIC_BITMAP) || \ 44 ((bmap)->magic == EXT2_ET_MAGIC_BLOCK_BITMAP) || \ 45 ((bmap)->magic == EXT2_ET_MAGIC_INODE_BITMAP)) 46 47 #define EXT2FS_IS_64_BITMAP(bmap) \ 48 (((bmap)->magic == EXT2_ET_MAGIC_GENERIC_BITMAP64) || \ 49 ((bmap)->magic == EXT2_ET_MAGIC_BLOCK_BITMAP64) || \ 50 ((bmap)->magic == EXT2_ET_MAGIC_INODE_BITMAP64)) 51 52 /* 53 * Used by previously inlined function, so we have to export this and 54 * not change the function signature 55 */ 56 void ext2fs_warn_bitmap2(ext2fs_generic_bitmap bitmap, 57 int code, unsigned long arg) 58 { 59 #ifndef OMIT_COM_ERR 60 if (bitmap->description) 61 com_err(0, bitmap->base_error_code+code, 62 "#%lu for %s", arg, bitmap->description); 63 else 64 com_err(0, bitmap->base_error_code + code, "#%lu", arg); 65 #endif 66 } 67 68 static errcode_t check_magic(ext2fs_generic_bitmap bitmap) 69 { 70 if (!bitmap || !((bitmap->magic == EXT2_ET_MAGIC_GENERIC_BITMAP) || 71 (bitmap->magic == EXT2_ET_MAGIC_INODE_BITMAP) || 72 (bitmap->magic == EXT2_ET_MAGIC_BLOCK_BITMAP))) 73 return EXT2_ET_MAGIC_GENERIC_BITMAP; 74 return 0; 75 } 76 77 errcode_t ext2fs_make_generic_bitmap(errcode_t magic, ext2_filsys fs, 78 __u32 start, __u32 end, __u32 real_end, 79 const char *descr, char *init_map, 80 ext2fs_generic_bitmap *ret) 81 { 82 ext2fs_generic_bitmap bitmap; 83 errcode_t retval; 84 size_t size; 85 86 retval = ext2fs_get_mem(sizeof(struct ext2fs_struct_generic_bitmap), 87 &bitmap); 88 if (retval) 89 return retval; 90 91 bitmap->magic = magic; 92 bitmap->fs = fs; 93 bitmap->start = start; 94 bitmap->end = end; 95 bitmap->real_end = real_end; 96 switch (magic) { 97 case EXT2_ET_MAGIC_INODE_BITMAP: 98 bitmap->base_error_code = EXT2_ET_BAD_INODE_MARK; 99 break; 100 case EXT2_ET_MAGIC_BLOCK_BITMAP: 101 bitmap->base_error_code = EXT2_ET_BAD_BLOCK_MARK; 102 break; 103 default: 104 bitmap->base_error_code = EXT2_ET_BAD_GENERIC_MARK; 105 } 106 if (descr) { 107 retval = ext2fs_get_mem(strlen(descr)+1, &bitmap->description); 108 if (retval) { 109 ext2fs_free_mem(&bitmap); 110 return retval; 111 } 112 strcpy(bitmap->description, descr); 113 } else 114 bitmap->description = 0; 115 116 size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1); 117 /* Round up to allow for the BT x86 instruction */ 118 size = (size + 7) & ~3; 119 retval = ext2fs_get_mem(size, &bitmap->bitmap); 120 if (retval) { 121 ext2fs_free_mem(&bitmap->description); 122 ext2fs_free_mem(&bitmap); 123 return retval; 124 } 125 126 if (init_map) 127 memcpy(bitmap->bitmap, init_map, size); 128 else 129 memset(bitmap->bitmap, 0, size); 130 *ret = bitmap; 131 return 0; 132 } 133 134 errcode_t ext2fs_allocate_generic_bitmap(__u32 start, 135 __u32 end, 136 __u32 real_end, 137 const char *descr, 138 ext2fs_generic_bitmap *ret) 139 { 140 return ext2fs_make_generic_bitmap(EXT2_ET_MAGIC_GENERIC_BITMAP, 0, 141 start, end, real_end, descr, 0, ret); 142 } 143 144 errcode_t ext2fs_copy_generic_bitmap(ext2fs_generic_bitmap src, 145 ext2fs_generic_bitmap *dest) 146 { 147 return (ext2fs_make_generic_bitmap(src->magic, src->fs, 148 src->start, src->end, 149 src->real_end, 150 src->description, src->bitmap, 151 dest)); 152 } 153 154 void ext2fs_free_generic_bitmap(ext2fs_inode_bitmap bitmap) 155 { 156 if (check_magic(bitmap)) 157 return; 158 159 bitmap->magic = 0; 160 if (bitmap->description) { 161 ext2fs_free_mem(&bitmap->description); 162 bitmap->description = 0; 163 } 164 if (bitmap->bitmap) { 165 ext2fs_free_mem(&bitmap->bitmap); 166 bitmap->bitmap = 0; 167 } 168 ext2fs_free_mem(&bitmap); 169 } 170 171 int ext2fs_test_generic_bitmap(ext2fs_generic_bitmap bitmap, 172 blk_t bitno) 173 { 174 if (!EXT2FS_IS_32_BITMAP(bitmap)) { 175 if (EXT2FS_IS_64_BITMAP(bitmap)) { 176 ext2fs_warn_bitmap32(bitmap, __func__); 177 return ext2fs_test_generic_bmap(bitmap, bitno); 178 } 179 #ifndef OMIT_COM_ERR 180 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP, 181 "test_bitmap(%lu)", (unsigned long) bitno); 182 #endif 183 return 0; 184 } 185 186 if ((bitno < bitmap->start) || (bitno > bitmap->end)) { 187 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, bitno); 188 return 0; 189 } 190 return ext2fs_test_bit(bitno - bitmap->start, bitmap->bitmap); 191 } 192 193 int ext2fs_mark_generic_bitmap(ext2fs_generic_bitmap bitmap, 194 __u32 bitno) 195 { 196 if (!EXT2FS_IS_32_BITMAP(bitmap)) { 197 if (EXT2FS_IS_64_BITMAP(bitmap)) { 198 ext2fs_warn_bitmap32(bitmap, __func__); 199 return ext2fs_mark_generic_bmap(bitmap, bitno); 200 } 201 #ifndef OMIT_COM_ERR 202 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP, 203 "mark_bitmap(%lu)", (unsigned long) bitno); 204 #endif 205 return 0; 206 } 207 208 if ((bitno < bitmap->start) || (bitno > bitmap->end)) { 209 ext2fs_warn_bitmap2(bitmap, EXT2FS_MARK_ERROR, bitno); 210 return 0; 211 } 212 return ext2fs_set_bit(bitno - bitmap->start, bitmap->bitmap); 213 } 214 215 int ext2fs_unmark_generic_bitmap(ext2fs_generic_bitmap bitmap, 216 blk_t bitno) 217 { 218 if (!EXT2FS_IS_32_BITMAP(bitmap)) { 219 if (EXT2FS_IS_64_BITMAP(bitmap)) { 220 ext2fs_warn_bitmap32(bitmap, __func__); 221 return ext2fs_unmark_generic_bmap(bitmap, bitno); 222 } 223 #ifndef OMIT_COM_ERR 224 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP, 225 "mark_bitmap(%lu)", (unsigned long) bitno); 226 #endif 227 return 0; 228 } 229 230 if ((bitno < bitmap->start) || (bitno > bitmap->end)) { 231 ext2fs_warn_bitmap2(bitmap, EXT2FS_UNMARK_ERROR, bitno); 232 return 0; 233 } 234 return ext2fs_clear_bit(bitno - bitmap->start, bitmap->bitmap); 235 } 236 237 __u32 ext2fs_get_generic_bitmap_start(ext2fs_generic_bitmap bitmap) 238 { 239 if (!EXT2FS_IS_32_BITMAP(bitmap)) { 240 if (EXT2FS_IS_64_BITMAP(bitmap)) { 241 ext2fs_warn_bitmap32(bitmap, __func__); 242 return ext2fs_get_generic_bmap_start(bitmap); 243 } 244 #ifndef OMIT_COM_ERR 245 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP, 246 "get_bitmap_start"); 247 #endif 248 return 0; 249 } 250 251 return bitmap->start; 252 } 253 254 __u32 ext2fs_get_generic_bitmap_end(ext2fs_generic_bitmap bitmap) 255 { 256 if (!EXT2FS_IS_32_BITMAP(bitmap)) { 257 if (EXT2FS_IS_64_BITMAP(bitmap)) { 258 ext2fs_warn_bitmap32(bitmap, __func__); 259 return ext2fs_get_generic_bmap_end(bitmap); 260 } 261 #ifndef OMIT_COM_ERR 262 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP, 263 "get_bitmap_end"); 264 #endif 265 return 0; 266 } 267 return bitmap->end; 268 } 269 270 void ext2fs_clear_generic_bitmap(ext2fs_generic_bitmap bitmap) 271 { 272 if (!EXT2FS_IS_32_BITMAP(bitmap)) { 273 if (EXT2FS_IS_64_BITMAP(bitmap)) { 274 ext2fs_warn_bitmap32(bitmap, __func__); 275 ext2fs_clear_generic_bmap(bitmap); 276 return; 277 } 278 #ifndef OMIT_COM_ERR 279 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP, 280 "clear_generic_bitmap"); 281 #endif 282 return; 283 } 284 285 memset(bitmap->bitmap, 0, 286 (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1)); 287 } 288 289 errcode_t ext2fs_fudge_generic_bitmap_end(ext2fs_inode_bitmap bitmap, 290 errcode_t magic, errcode_t neq, 291 ext2_ino_t end, ext2_ino_t *oend) 292 { 293 EXT2_CHECK_MAGIC(bitmap, magic); 294 295 if (end > bitmap->real_end) 296 return neq; 297 if (oend) 298 *oend = bitmap->end; 299 bitmap->end = end; 300 return 0; 301 } 302 303 errcode_t ext2fs_resize_generic_bitmap(errcode_t magic, 304 __u32 new_end, __u32 new_real_end, 305 ext2fs_generic_bitmap bmap) 306 { 307 errcode_t retval; 308 size_t size, new_size; 309 __u32 bitno; 310 311 if (!bmap || (bmap->magic != magic)) 312 return magic; 313 314 /* 315 * If we're expanding the bitmap, make sure all of the new 316 * parts of the bitmap are zero. 317 */ 318 if (new_end > bmap->end) { 319 bitno = bmap->real_end; 320 if (bitno > new_end) 321 bitno = new_end; 322 for (; bitno > bmap->end; bitno--) 323 ext2fs_clear_bit(bitno - bmap->start, bmap->bitmap); 324 } 325 if (new_real_end == bmap->real_end) { 326 bmap->end = new_end; 327 return 0; 328 } 329 330 size = ((bmap->real_end - bmap->start) / 8) + 1; 331 new_size = ((new_real_end - bmap->start) / 8) + 1; 332 333 if (size != new_size) { 334 retval = ext2fs_resize_mem(size, new_size, &bmap->bitmap); 335 if (retval) 336 return retval; 337 } 338 if (new_size > size) 339 memset(bmap->bitmap + size, 0, new_size - size); 340 341 bmap->end = new_end; 342 bmap->real_end = new_real_end; 343 return 0; 344 } 345 346 errcode_t ext2fs_compare_generic_bitmap(errcode_t magic, errcode_t neq, 347 ext2fs_generic_bitmap bm1, 348 ext2fs_generic_bitmap bm2) 349 { 350 blk_t i; 351 352 if (!bm1 || bm1->magic != magic) 353 return magic; 354 if (!bm2 || bm2->magic != magic) 355 return magic; 356 357 if ((bm1->start != bm2->start) || 358 (bm1->end != bm2->end) || 359 (memcmp(bm1->bitmap, bm2->bitmap, 360 (size_t) (bm1->end - bm1->start)/8))) 361 return neq; 362 363 for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++) 364 if (ext2fs_fast_test_block_bitmap(bm1, i) != 365 ext2fs_fast_test_block_bitmap(bm2, i)) 366 return neq; 367 368 return 0; 369 } 370 371 void ext2fs_set_generic_bitmap_padding(ext2fs_generic_bitmap map) 372 { 373 __u32 i, j; 374 375 /* Protect loop from wrap-around if map->real_end is maxed */ 376 for (i=map->end+1, j = i - map->start; 377 i <= map->real_end && i > map->end; 378 i++, j++) 379 ext2fs_set_bit(j, map->bitmap); 380 } 381 382 errcode_t ext2fs_get_generic_bitmap_range(ext2fs_generic_bitmap bmap, 383 errcode_t magic, 384 __u32 start, __u32 num, 385 void *out) 386 { 387 if (!bmap || (bmap->magic != magic)) 388 return magic; 389 390 if ((start < bmap->start) || (start+num-1 > bmap->real_end)) 391 return EXT2_ET_INVALID_ARGUMENT; 392 393 memcpy(out, bmap->bitmap + (start >> 3), (num+7) >> 3); 394 return 0; 395 } 396 397 errcode_t ext2fs_set_generic_bitmap_range(ext2fs_generic_bitmap bmap, 398 errcode_t magic, 399 __u32 start, __u32 num, 400 void *in) 401 { 402 if (!bmap || (bmap->magic != magic)) 403 return magic; 404 405 if ((start < bmap->start) || (start+num-1 > bmap->real_end)) 406 return EXT2_ET_INVALID_ARGUMENT; 407 408 memcpy(bmap->bitmap + (start >> 3), in, (num+7) >> 3); 409 return 0; 410 } 411 412 /* 413 * Compare @mem to zero buffer by 256 bytes. 414 * Return 1 if @mem is zeroed memory, otherwise return 0. 415 */ 416 int ext2fs_mem_is_zero(const char *mem, size_t len) 417 { 418 static const char zero_buf[256]; 419 420 while (len >= sizeof(zero_buf)) { 421 if (memcmp(mem, zero_buf, sizeof(zero_buf))) 422 return 0; 423 len -= sizeof(zero_buf); 424 mem += sizeof(zero_buf); 425 } 426 /* Deal with leftover bytes. */ 427 if (len) 428 return !memcmp(mem, zero_buf, len); 429 return 1; 430 } 431 432 /* 433 * Return true if all of the bits in a specified range are clear 434 */ 435 static int ext2fs_test_clear_generic_bitmap_range(ext2fs_generic_bitmap bitmap, 436 unsigned int start, 437 unsigned int len) 438 { 439 size_t start_byte, len_byte = len >> 3; 440 unsigned int start_bit, len_bit = len % 8; 441 int first_bit = 0; 442 int last_bit = 0; 443 int mark_count = 0; 444 int mark_bit = 0; 445 int i; 446 const char *ADDR = bitmap->bitmap; 447 448 start -= bitmap->start; 449 start_byte = start >> 3; 450 start_bit = start % 8; 451 452 if (start_bit != 0) { 453 /* 454 * The compared start block number or start inode number 455 * is not the first bit in a byte. 456 */ 457 mark_count = 8 - start_bit; 458 if (len < 8 - start_bit) { 459 mark_count = (int)len; 460 mark_bit = len + start_bit - 1; 461 } else 462 mark_bit = 7; 463 464 for (i = mark_count; i > 0; i--, mark_bit--) 465 first_bit |= 1 << mark_bit; 466 467 /* 468 * Compare blocks or inodes in the first byte. 469 * If there is any marked bit, this function returns 0. 470 */ 471 if (first_bit & ADDR[start_byte]) 472 return 0; 473 else if (len <= 8 - start_bit) 474 return 1; 475 476 start_byte++; 477 len_bit = (len - mark_count) % 8; 478 len_byte = (len - mark_count) >> 3; 479 } 480 481 /* 482 * The compared start block number or start inode number is 483 * the first bit in a byte. 484 */ 485 if (len_bit != 0) { 486 /* 487 * The compared end block number or end inode number is 488 * not the last bit in a byte. 489 */ 490 for (mark_bit = len_bit - 1; mark_bit >= 0; mark_bit--) 491 last_bit |= 1 << mark_bit; 492 493 /* 494 * Compare blocks or inodes in the last byte. 495 * If there is any marked bit, this function returns 0. 496 */ 497 if (last_bit & ADDR[start_byte + len_byte]) 498 return 0; 499 else if (len_byte == 0) 500 return 1; 501 } 502 503 /* Check whether all bytes are 0 */ 504 return ext2fs_mem_is_zero(ADDR + start_byte, len_byte); 505 } 506 507 errcode_t ext2fs_find_first_zero_generic_bitmap(ext2fs_generic_bitmap bitmap, 508 __u32 start, __u32 end, 509 __u32 *out) 510 { 511 blk_t b; 512 513 if (start < bitmap->start || end > bitmap->end || start > end) { 514 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start); 515 return EINVAL; 516 } 517 518 while (start <= end) { 519 b = ext2fs_test_bit(start - bitmap->start, bitmap->bitmap); 520 if (!b) { 521 *out = start; 522 return 0; 523 } 524 start++; 525 } 526 527 return ENOENT; 528 } 529 530 errcode_t ext2fs_find_first_set_generic_bitmap(ext2fs_generic_bitmap bitmap, 531 __u32 start, __u32 end, 532 __u32 *out) 533 { 534 blk_t b; 535 536 if (start < bitmap->start || end > bitmap->end || start > end) { 537 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start); 538 return EINVAL; 539 } 540 541 while (start <= end) { 542 b = ext2fs_test_bit(start - bitmap->start, bitmap->bitmap); 543 if (b) { 544 *out = start; 545 return 0; 546 } 547 start++; 548 } 549 550 return ENOENT; 551 } 552 553 int ext2fs_test_block_bitmap_range(ext2fs_block_bitmap bitmap, 554 blk_t block, int num) 555 { 556 EXT2_CHECK_MAGIC(bitmap, EXT2_ET_MAGIC_BLOCK_BITMAP); 557 if ((block < bitmap->start) || (block+num-1 > bitmap->real_end)) { 558 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST, 559 block, bitmap->description); 560 return 0; 561 } 562 return ext2fs_test_clear_generic_bitmap_range((ext2fs_generic_bitmap) 563 bitmap, block, num); 564 } 565 566 int ext2fs_test_inode_bitmap_range(ext2fs_inode_bitmap bitmap, 567 ext2_ino_t inode, int num) 568 { 569 EXT2_CHECK_MAGIC(bitmap, EXT2_ET_MAGIC_INODE_BITMAP); 570 if ((inode < bitmap->start) || (inode+num-1 > bitmap->real_end)) { 571 ext2fs_warn_bitmap(EXT2_ET_BAD_INODE_TEST, 572 inode, bitmap->description); 573 return 0; 574 } 575 return ext2fs_test_clear_generic_bitmap_range((ext2fs_generic_bitmap) 576 bitmap, inode, num); 577 } 578 579 void ext2fs_mark_block_bitmap_range(ext2fs_block_bitmap bitmap, 580 blk_t block, int num) 581 { 582 int i; 583 584 if ((block < bitmap->start) || (block+num-1 > bitmap->end)) { 585 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block, 586 bitmap->description); 587 return; 588 } 589 for (i=0; i < num; i++) 590 ext2fs_fast_set_bit(block + i - bitmap->start, bitmap->bitmap); 591 } 592 593 void ext2fs_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap, 594 blk_t block, int num) 595 { 596 int i; 597 598 if ((block < bitmap->start) || (block+num-1 > bitmap->end)) { 599 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block, 600 bitmap->description); 601 return; 602 } 603 for (i=0; i < num; i++) 604 ext2fs_fast_clear_bit(block + i - bitmap->start, 605 bitmap->bitmap); 606 } 607 608
