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