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