gen_bitmap64.c revision d1154eb460efe588eaed3d439c1caaca149fa362
1/* 2 * gen_bitmap64.c --- routines to read, write, and manipulate the new qinode and 3 * block bitmaps. 4 * 5 * Copyright (C) 2007, 2008 Theodore Ts'o. 6 * 7 * %Begin-Header% 8 * This file may be redistributed under the terms of the GNU Public 9 * License. 10 * %End-Header% 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#include <errno.h> 22#if HAVE_SYS_STAT_H 23#include <sys/stat.h> 24#endif 25#if HAVE_SYS_TYPES_H 26#include <sys/types.h> 27#endif 28 29#include "ext2_fs.h" 30#include "ext2fsP.h" 31#include "bmap64.h" 32 33/* 34 * Design of 64-bit bitmaps 35 * 36 * In order maintain ABI compatibility with programs that don't 37 * understand about 64-bit blocks/inodes, 38 * ext2fs_allocate_inode_bitmap() and ext2fs_allocate_block_bitmap() 39 * will create old-style bitmaps unless the application passes the 40 * flag EXT2_FLAG_64BITS to ext2fs_open(). If this flag is 41 * passed, then we know the application has been recompiled, so we can 42 * use the new-style bitmaps. If it is not passed, we have to return 43 * an error if trying to open a filesystem which needs 64-bit bitmaps. 44 * 45 * The new bitmaps use a new set of structure magic numbers, so that 46 * both the old-style and new-style interfaces can identify which 47 * version of the data structure was used. Both the old-style and 48 * new-style interfaces will support either type of bitmap, although 49 * of course 64-bit operation will only be possible when both the 50 * new-style interface and the new-style bitmap are used. 51 * 52 * For example, the new bitmap interfaces will check the structure 53 * magic numbers and so will be able to detect old-stype bitmap. If 54 * they see an old-style bitmap, they will pass it to the gen_bitmap.c 55 * functions for handling. The same will be true for the old 56 * interfaces as well. 57 * 58 * The new-style interfaces will have several different back-end 59 * implementations, so we can support different encodings that are 60 * appropriate for different applications. In general the default 61 * should be whatever makes sense, and what the application/library 62 * will use. However, e2fsck may need specialized implementations for 63 * its own uses. For example, when doing parent directory pointer 64 * loop detections in pass 3, the bitmap will *always* be sparse, so 65 * e2fsck can request an encoding which is optimized for that. 66 */ 67 68static void warn_bitmap(ext2fs_generic_bitmap bitmap, 69 int code, __u64 arg) 70{ 71#ifndef OMIT_COM_ERR 72 if (bitmap->description) 73 com_err(0, bitmap->base_error_code+code, 74 "#%llu for %s", arg, bitmap->description); 75 else 76 com_err(0, bitmap->base_error_code + code, "#%llu", arg); 77#endif 78} 79 80 81errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic, 82 int type, __u64 start, __u64 end, 83 __u64 real_end, 84 const char *descr, 85 ext2fs_generic_bitmap *ret) 86{ 87 ext2fs_generic_bitmap bitmap; 88 struct ext2_bitmap_ops *ops; 89 errcode_t retval; 90 91 switch (type) { 92 case EXT2FS_BMAP64_BITARRAY: 93 ops = &ext2fs_blkmap64_bitarray; 94 break; 95 default: 96 return EINVAL; 97 } 98 99 retval = ext2fs_get_mem(sizeof(struct ext2fs_struct_generic_bitmap), 100 &bitmap); 101 if (retval) 102 return retval; 103 104 /* XXX factor out, repeated in copy_bmap */ 105 bitmap->magic = magic; 106 bitmap->fs = fs; 107 bitmap->start = start; 108 bitmap->end = end; 109 bitmap->real_end = real_end; 110 bitmap->bitmap_ops = ops; 111 bitmap->cluster_bits = 0; 112 switch (magic) { 113 case EXT2_ET_MAGIC_INODE_BITMAP64: 114 bitmap->base_error_code = EXT2_ET_BAD_INODE_MARK; 115 break; 116 case EXT2_ET_MAGIC_BLOCK_BITMAP64: 117 bitmap->base_error_code = EXT2_ET_BAD_BLOCK_MARK; 118 bitmap->cluster_bits = fs->cluster_ratio_bits; 119 break; 120 default: 121 bitmap->base_error_code = EXT2_ET_BAD_GENERIC_MARK; 122 } 123 if (descr) { 124 retval = ext2fs_get_mem(strlen(descr)+1, &bitmap->description); 125 if (retval) { 126 ext2fs_free_mem(&bitmap); 127 return retval; 128 } 129 strcpy(bitmap->description, descr); 130 } else 131 bitmap->description = 0; 132 133 retval = bitmap->bitmap_ops->new_bmap(fs, bitmap); 134 if (retval) { 135 ext2fs_free_mem(&bitmap->description); 136 ext2fs_free_mem(&bitmap); 137 return retval; 138 } 139 140 *ret = bitmap; 141 return 0; 142} 143 144void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap) 145{ 146 if (!bmap) 147 return; 148 149 if (EXT2FS_IS_32_BITMAP(bmap)) { 150 ext2fs_free_generic_bitmap(bmap); 151 return; 152 } 153 154 if (!EXT2FS_IS_64_BITMAP(bmap)) 155 return; 156 157 bmap->bitmap_ops->free_bmap(bmap); 158 159 if (bmap->description) { 160 ext2fs_free_mem(&bmap->description); 161 bmap->description = 0; 162 } 163 bmap->magic = 0; 164 ext2fs_free_mem(&bmap); 165} 166 167errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap src, 168 ext2fs_generic_bitmap *dest) 169{ 170 char *descr, *new_descr; 171 ext2fs_generic_bitmap new_bmap; 172 errcode_t retval; 173 174 if (!src) 175 return EINVAL; 176 177 if (EXT2FS_IS_32_BITMAP(src)) 178 return ext2fs_copy_generic_bitmap(src, dest); 179 180 if (!EXT2FS_IS_64_BITMAP(src)) 181 return EINVAL; 182 183 /* Allocate a new bitmap struct */ 184 retval = ext2fs_get_mem(sizeof(struct ext2fs_struct_generic_bitmap), 185 &new_bmap); 186 if (retval) 187 return retval; 188 189 /* Copy all the high-level parts over */ 190 new_bmap->magic = src->magic; 191 new_bmap->fs = src->fs; 192 new_bmap->start = src->start; 193 new_bmap->end = src->end; 194 new_bmap->real_end = src->real_end; 195 new_bmap->bitmap_ops = src->bitmap_ops; 196 new_bmap->base_error_code = src->base_error_code; 197 new_bmap->cluster_bits = src->cluster_bits; 198 199 descr = src->description; 200 if (descr) { 201 retval = ext2fs_get_mem(strlen(descr)+1, &new_descr); 202 if (retval) { 203 ext2fs_free_mem(&new_bmap); 204 return retval; 205 } 206 strcpy(new_descr, descr); 207 new_bmap->description = new_descr; 208 } 209 210 retval = src->bitmap_ops->copy_bmap(src, new_bmap); 211 if (retval) { 212 ext2fs_free_mem(&new_bmap->description); 213 ext2fs_free_mem(&new_bmap); 214 return retval; 215 } 216 217 *dest = new_bmap; 218 219 return 0; 220} 221 222errcode_t ext2fs_resize_generic_bmap(ext2fs_generic_bitmap bmap, 223 __u64 new_end, 224 __u64 new_real_end) 225{ 226 if (!bmap) 227 return EINVAL; 228 229 if (EXT2FS_IS_32_BITMAP(bmap)) 230 return ext2fs_resize_generic_bitmap(bmap->magic, new_end, 231 new_real_end, bmap); 232 233 if (!EXT2FS_IS_64_BITMAP(bmap)) 234 return EINVAL; 235 236 return bmap->bitmap_ops->resize_bmap(bmap, new_end, new_real_end); 237} 238 239errcode_t ext2fs_fudge_generic_bmap_end(ext2fs_generic_bitmap bitmap, 240 errcode_t neq, 241 __u64 end, __u64 *oend) 242{ 243 if (!bitmap) 244 return EINVAL; 245 246 if (EXT2FS_IS_32_BITMAP(bitmap)) { 247 ext2_ino_t tmp_oend; 248 int retval; 249 250 retval = ext2fs_fudge_generic_bitmap_end(bitmap, bitmap->magic, 251 neq, end, &tmp_oend); 252 if (oend) 253 *oend = tmp_oend; 254 return retval; 255 } 256 257 if (!EXT2FS_IS_64_BITMAP(bitmap)) 258 return EINVAL; 259 260 if (end > bitmap->real_end) 261 return neq; 262 if (oend) 263 *oend = bitmap->end; 264 bitmap->end = end; 265 return 0; 266} 267 268__u64 ext2fs_get_generic_bmap_start(ext2fs_generic_bitmap bitmap) 269{ 270 if (!bitmap) 271 return EINVAL; 272 273 if (EXT2FS_IS_32_BITMAP(bitmap)) 274 return ext2fs_get_generic_bitmap_start(bitmap); 275 276 if (!EXT2FS_IS_64_BITMAP(bitmap)) 277 return EINVAL; 278 279 return bitmap->start; 280} 281 282__u64 ext2fs_get_generic_bmap_end(ext2fs_generic_bitmap bitmap) 283{ 284 if (!bitmap) 285 return EINVAL; 286 287 if (EXT2FS_IS_32_BITMAP(bitmap)) 288 return ext2fs_get_generic_bitmap_end(bitmap); 289 290 if (!EXT2FS_IS_64_BITMAP(bitmap)) 291 return EINVAL; 292 293 return bitmap->end; 294} 295 296void ext2fs_clear_generic_bmap(ext2fs_generic_bitmap bitmap) 297{ 298 if (EXT2FS_IS_32_BITMAP(bitmap)) 299 ext2fs_clear_generic_bitmap(bitmap); 300 301 bitmap->bitmap_ops->clear_bmap (bitmap); 302} 303 304int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap bitmap, 305 __u64 arg) 306{ 307 if (!bitmap) 308 return 0; 309 310 if (EXT2FS_IS_32_BITMAP(bitmap)) { 311 if (arg & ~0xffffffffULL) { 312 ext2fs_warn_bitmap2(bitmap, 313 EXT2FS_MARK_ERROR, 0xffffffff); 314 return 0; 315 } 316 return ext2fs_mark_generic_bitmap(bitmap, arg); 317 } 318 319 if (!EXT2FS_IS_64_BITMAP(bitmap)) 320 return 0; 321 322 arg >>= bitmap->cluster_bits; 323 324 if ((arg < bitmap->start) || (arg > bitmap->end)) { 325 warn_bitmap(bitmap, EXT2FS_MARK_ERROR, arg); 326 return 0; 327 } 328 329 return bitmap->bitmap_ops->mark_bmap(bitmap, arg); 330} 331 332int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap bitmap, 333 __u64 arg) 334{ 335 if (!bitmap) 336 return 0; 337 338 if (EXT2FS_IS_32_BITMAP(bitmap)) { 339 if (arg & ~0xffffffffULL) { 340 ext2fs_warn_bitmap2(bitmap, EXT2FS_UNMARK_ERROR, 341 0xffffffff); 342 return 0; 343 } 344 return ext2fs_unmark_generic_bitmap(bitmap, arg); 345 } 346 347 if (!EXT2FS_IS_64_BITMAP(bitmap)) 348 return 0; 349 350 arg >>= bitmap->cluster_bits; 351 352 if ((arg < bitmap->start) || (arg > bitmap->end)) { 353 warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg); 354 return 0; 355 } 356 357 return bitmap->bitmap_ops->unmark_bmap(bitmap, arg); 358} 359 360int ext2fs_test_generic_bmap(ext2fs_generic_bitmap bitmap, 361 __u64 arg) 362{ 363 if (!bitmap) 364 return 0; 365 366 if (EXT2FS_IS_32_BITMAP(bitmap)) { 367 if (arg & ~0xffffffffULL) { 368 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, 369 0xffffffff); 370 return 0; 371 } 372 return ext2fs_test_generic_bitmap(bitmap, arg); 373 } 374 375 if (!EXT2FS_IS_64_BITMAP(bitmap)) 376 return 0; 377 378 arg >>= bitmap->cluster_bits; 379 380 if ((arg < bitmap->start) || (arg > bitmap->end)) { 381 warn_bitmap(bitmap, EXT2FS_TEST_ERROR, arg); 382 return 0; 383 } 384 385 return bitmap->bitmap_ops->test_bmap(bitmap, arg); 386} 387 388errcode_t ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap bmap, 389 __u64 start, unsigned int num, 390 void *in) 391{ 392 if (!bmap) 393 return EINVAL; 394 395 if (EXT2FS_IS_32_BITMAP(bmap)) { 396 if ((start+num-1) & ~0xffffffffULL) { 397 ext2fs_warn_bitmap2(bmap, EXT2FS_UNMARK_ERROR, 398 0xffffffff); 399 return EINVAL; 400 } 401 return ext2fs_set_generic_bitmap_range(bmap, bmap->magic, 402 start, num, in); 403 } 404 405 if (!EXT2FS_IS_64_BITMAP(bmap)) 406 return EINVAL; 407 408 return bmap->bitmap_ops->set_bmap_range(bmap, start, num, in); 409} 410 411errcode_t ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap bmap, 412 __u64 start, unsigned int num, 413 void *out) 414{ 415 if (!bmap) 416 return EINVAL; 417 418 if (EXT2FS_IS_32_BITMAP(bmap)) { 419 if ((start+num-1) & ~0xffffffffULL) { 420 ext2fs_warn_bitmap2(bmap, 421 EXT2FS_UNMARK_ERROR, 0xffffffff); 422 return EINVAL; 423 } 424 return ext2fs_get_generic_bitmap_range(bmap, bmap->magic, 425 start, num, out); 426 } 427 428 if (!EXT2FS_IS_64_BITMAP(bmap)) 429 return EINVAL; 430 431 return bmap->bitmap_ops->get_bmap_range(bmap, start, num, out); 432} 433 434errcode_t ext2fs_compare_generic_bmap(errcode_t neq, 435 ext2fs_generic_bitmap bm1, 436 ext2fs_generic_bitmap bm2) 437{ 438 blk64_t i; 439 440 if (!bm1 || !bm2) 441 return EINVAL; 442 if (bm1->magic != bm2->magic) 443 return EINVAL; 444 445 /* Now we know both bitmaps have the same magic */ 446 if (EXT2FS_IS_32_BITMAP(bm1)) 447 return ext2fs_compare_generic_bitmap(bm1->magic, neq, bm1, bm2); 448 449 if (!EXT2FS_IS_64_BITMAP(bm1)) 450 return EINVAL; 451 452 if ((bm1->start != bm2->start) || 453 (bm1->end != bm2->end)) 454 return neq; 455 456 for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++) 457 if (ext2fs_test_generic_bmap(bm1, i) != 458 ext2fs_test_generic_bmap(bm2, i)) 459 return neq; 460 461 return 0; 462} 463 464void ext2fs_set_generic_bmap_padding(ext2fs_generic_bitmap bmap) 465{ 466 __u64 start, num; 467 468 if (EXT2FS_IS_32_BITMAP(bmap)) { 469 ext2fs_set_generic_bitmap_padding(bmap); 470 return; 471 } 472 473 start = bmap->end + 1; 474 num = bmap->real_end - bmap->end; 475 bmap->bitmap_ops->mark_bmap_extent(bmap, start, num); 476 /* XXX ought to warn on error */ 477} 478 479int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap bmap, 480 blk64_t block, unsigned int num) 481{ 482 if (!bmap) 483 return EINVAL; 484 485 if (num == 1) 486 return !ext2fs_test_generic_bmap((ext2fs_generic_bitmap) 487 bmap, block); 488 489 if (EXT2FS_IS_32_BITMAP(bmap)) { 490 if ((block+num-1) & ~0xffffffffULL) { 491 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap, 492 EXT2FS_UNMARK_ERROR, 0xffffffff); 493 return EINVAL; 494 } 495 return ext2fs_test_block_bitmap_range( 496 (ext2fs_generic_bitmap) bmap, block, num); 497 } 498 499 if (!EXT2FS_IS_64_BITMAP(bmap)) 500 return EINVAL; 501 502 return bmap->bitmap_ops->test_clear_bmap_extent(bmap, block, num); 503} 504 505void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap bmap, 506 blk64_t block, unsigned int num) 507{ 508 if (!bmap) 509 return; 510 511 if (EXT2FS_IS_32_BITMAP(bmap)) { 512 if ((block+num-1) & ~0xffffffffULL) { 513 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap, 514 EXT2FS_UNMARK_ERROR, 0xffffffff); 515 return; 516 } 517 ext2fs_mark_block_bitmap_range((ext2fs_generic_bitmap) bmap, 518 block, num); 519 } 520 521 if (!EXT2FS_IS_64_BITMAP(bmap)) 522 return; 523 524 if ((block < bmap->start) || (block+num-1 > bmap->end)) { 525 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block, 526 bmap->description); 527 return; 528 } 529 530 bmap->bitmap_ops->mark_bmap_extent(bmap, block, num); 531} 532 533void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap bmap, 534 blk64_t block, unsigned int num) 535{ 536 if (!bmap) 537 return; 538 539 if (EXT2FS_IS_32_BITMAP(bmap)) { 540 if ((block+num-1) & ~0xffffffffULL) { 541 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap, 542 EXT2FS_UNMARK_ERROR, 0xffffffff); 543 return; 544 } 545 ext2fs_unmark_block_bitmap_range((ext2fs_generic_bitmap) bmap, 546 block, num); 547 } 548 549 if (!EXT2FS_IS_64_BITMAP(bmap)) 550 return; 551 552 if ((block < bmap->start) || (block+num-1 > bmap->end)) { 553 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block, 554 bmap->description); 555 return; 556 } 557 558 bmap->bitmap_ops->unmark_bmap_extent(bmap, block, num); 559} 560 561void ext2fs_warn_bitmap32(ext2fs_generic_bitmap bitmap, const char *func) 562{ 563#ifndef OMIT_COM_ERR 564 if (bitmap && bitmap->description) 565 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP, 566 "called %s with 64-bit bitmap for %s", func, 567 bitmap->description); 568 else 569 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP, 570 "called %s with 64-bit bitmap", func); 571#endif 572} 573 574errcode_t ext2fs_convert_subcluster_bitmap(ext2_filsys fs, 575 ext2fs_block_bitmap *bitmap) 576{ 577 ext2fs_block_bitmap cmap, bmap; 578 errcode_t retval; 579 blk64_t i, b_end, c_end; 580 int n, ratio; 581 582 bmap = *bitmap; 583 584 if (fs->cluster_ratio_bits == ext2fs_get_bitmap_granularity(bmap)) 585 return 0; /* Nothing to do */ 586 587 retval = ext2fs_allocate_block_bitmap(fs, "converted cluster bitmap", 588 &cmap); 589 if (retval) 590 return retval; 591 592 i = bmap->start; 593 b_end = bmap->end; 594 bmap->end = bmap->real_end; 595 c_end = cmap->end; 596 cmap->end = cmap->real_end; 597 n = 0; 598 ratio = 1 << fs->cluster_ratio_bits; 599 while (i < bmap->real_end) { 600 if (ext2fs_test_block_bitmap2(bmap, i)) { 601 ext2fs_mark_block_bitmap2(cmap, i); 602 i += ratio - n; 603 n = 0; 604 continue; 605 } 606 i++; n++; 607 if (n >= ratio) 608 n = 0; 609 } 610 bmap->end = b_end; 611 cmap->end = c_end; 612 ext2fs_free_block_bitmap(bmap); 613 *bitmap = cmap; 614 return 0; 615} 616