1 /* 2 * Copyright (c) 2008 The DragonFly Project. All rights reserved. 3 * 4 * This code is derived from software contributed to The DragonFly Project 5 * by Matthew Dillon <dillon@backplane.com> 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in 15 * the documentation and/or other materials provided with the 16 * distribution. 17 * 3. Neither the name of The DragonFly Project nor the names of its 18 * contributors may be used to endorse or promote products derived 19 * from this software without specific, prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 25 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 26 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, 27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 29 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 30 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 31 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32 * SUCH DAMAGE. 33 */ 34 35 #include "hammer.h" 36 37 #include <sys/tree.h> 38 39 /* 40 * Each collect covers 1<<(19+23) bytes address space of layer 1. 41 * (plus a copy of 1<<23 bytes that holds layer2 entries in layer 1). 42 */ 43 typedef struct collect { 44 RB_ENTRY(collect) entry; 45 hammer_off_t phys_offset; /* layer2 address pointed by layer1 */ 46 hammer_off_t *offsets; /* big-block offset for layer2[i] */ 47 hammer_blockmap_layer2_t track2; /* track of layer2 entries */ 48 hammer_blockmap_layer2_t layer2; /* 1<<19 x 16 bytes entries */ 49 int error; /* # of inconsistencies */ 50 } *collect_t; 51 52 static int 53 collect_compare(struct collect *c1, struct collect *c2) 54 { 55 if (c1->phys_offset < c2->phys_offset) 56 return(-1); 57 if (c1->phys_offset > c2->phys_offset) 58 return(1); 59 return(0); 60 } 61 62 RB_HEAD(collect_rb_tree, collect) CollectTree = RB_INITIALIZER(&CollectTree); 63 RB_PROTOTYPE2(collect_rb_tree, collect, entry, collect_compare, hammer_off_t); 64 RB_GENERATE2(collect_rb_tree, collect, entry, collect_compare, hammer_off_t, 65 phys_offset); 66 67 static void dump_blockmap(int zone); 68 static void check_freemap(hammer_blockmap_t freemap); 69 static void check_btree_node(hammer_off_t node_offset, int depth); 70 static void check_undo(hammer_blockmap_t undomap); 71 static __inline void collect_btree_root(hammer_off_t node_offset); 72 static __inline void collect_btree_internal(hammer_btree_elm_t elm); 73 static __inline void collect_btree_leaf(hammer_btree_elm_t elm); 74 static __inline void collect_freemap_layer1(hammer_blockmap_t freemap); 75 static __inline void collect_freemap_layer2(hammer_blockmap_layer1_t layer1); 76 static __inline void collect_undo(hammer_off_t scan_offset, 77 hammer_fifo_head_t head); 78 static void collect_blockmap(hammer_off_t offset, int32_t length, int zone); 79 static hammer_blockmap_layer2_t collect_get_track( 80 collect_t collect, hammer_off_t offset, int zone, 81 hammer_blockmap_layer2_t layer2); 82 static collect_t collect_get(hammer_off_t phys_offset); 83 static void dump_collect_table(void); 84 static void dump_collect(collect_t collect, zone_stat_t stats); 85 86 static int num_bad_layer1 = 0; 87 static int num_bad_layer2 = 0; 88 static int num_bad_node = 0; 89 90 void 91 hammer_cmd_blockmap(void) 92 { 93 dump_blockmap(HAMMER_ZONE_FREEMAP_INDEX); 94 } 95 96 static 97 void 98 dump_blockmap(int zone) 99 { 100 volume_info_t root_volume; 101 hammer_blockmap_t rootmap; 102 hammer_blockmap_layer1_t layer1; 103 hammer_blockmap_layer2_t layer2; 104 buffer_info_t buffer1 = NULL; 105 buffer_info_t buffer2 = NULL; 106 hammer_off_t layer1_offset; 107 hammer_off_t layer2_offset; 108 hammer_off_t phys_offset; 109 hammer_off_t block_offset; 110 zone_stat_t stats = NULL; 111 int xerr, aerr, ferr; 112 113 root_volume = get_root_volume(); 114 rootmap = &root_volume->ondisk->vol0_blockmap[zone]; 115 assert(rootmap->phys_offset != 0); 116 117 print_blockmap(root_volume); 118 119 if (VerboseOpt) 120 stats = hammer_init_zone_stat(); 121 122 for (phys_offset = HAMMER_ZONE_ENCODE(zone, 0); 123 phys_offset < HAMMER_ZONE_ENCODE(zone, HAMMER_OFF_LONG_MASK); 124 phys_offset += HAMMER_BLOCKMAP_LAYER2) { 125 /* 126 * Dive layer 1. 127 */ 128 layer1_offset = rootmap->phys_offset + 129 HAMMER_BLOCKMAP_LAYER1_OFFSET(phys_offset); 130 layer1 = get_buffer_data(layer1_offset, &buffer1, 0); 131 132 xerr = ' '; /* good */ 133 if (!hammer_crc_test_layer1(HammerVersion, layer1)) { 134 xerr = 'B'; 135 ++num_bad_layer1; 136 } 137 if (xerr == ' ' && 138 layer1->phys_offset == HAMMER_BLOCKMAP_UNAVAIL) { 139 continue; 140 } 141 printf("%c layer1 %016jx @%016jx blocks-free %jd\n", 142 xerr, 143 (uintmax_t)phys_offset, 144 (uintmax_t)layer1->phys_offset, 145 (intmax_t)layer1->blocks_free); 146 147 for (block_offset = 0; 148 block_offset < HAMMER_BLOCKMAP_LAYER2; 149 block_offset += HAMMER_BIGBLOCK_SIZE) { 150 hammer_off_t zone_offset = phys_offset + block_offset; 151 /* 152 * Dive layer 2, each entry represents a big-block. 153 */ 154 layer2_offset = layer1->phys_offset + 155 HAMMER_BLOCKMAP_LAYER2_OFFSET(block_offset); 156 layer2 = get_buffer_data(layer2_offset, &buffer2, 0); 157 158 xerr = aerr = ferr = ' '; /* good */ 159 if (!hammer_crc_test_layer2(HammerVersion, layer2)) { 160 xerr = 'B'; 161 ++num_bad_layer2; 162 } 163 if (layer2->append_off > HAMMER_BIGBLOCK_SIZE) { 164 aerr = 'A'; 165 ++num_bad_layer2; 166 } 167 if (layer2->bytes_free < 0 || 168 layer2->bytes_free > HAMMER_BIGBLOCK_SIZE) { 169 ferr = 'F'; 170 ++num_bad_layer2; 171 } 172 173 if (VerboseOpt < 2 && 174 xerr == ' ' && aerr == ' ' && ferr == ' ' && 175 layer2->zone == HAMMER_ZONE_UNAVAIL_INDEX) { 176 break; 177 } 178 printf("%c%c%c %016jx zone=%-2d ", 179 xerr, aerr, ferr, (uintmax_t)zone_offset, layer2->zone); 180 if (VerboseOpt) { 181 printf("vol=%-3d L1#=%-6d L2#=%-6d L1=%-7lu L2=%-7lu ", 182 HAMMER_VOL_DECODE(zone_offset), 183 HAMMER_BLOCKMAP_LAYER1_INDEX(zone_offset), 184 HAMMER_BLOCKMAP_LAYER2_INDEX(zone_offset), 185 HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset), 186 HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset)); 187 } 188 printf("app=%-7d free=%-7d", 189 layer2->append_off, 190 layer2->bytes_free); 191 if (VerboseOpt) { 192 double bytes_used = HAMMER_BIGBLOCK_SIZE - 193 layer2->bytes_free; 194 printf(" fill=%-5.1lf crc=%08x-%08x\n", 195 bytes_used * 100 / HAMMER_BIGBLOCK_SIZE, 196 layer1->layer1_crc, 197 layer2->entry_crc); 198 } else { 199 printf("\n"); 200 } 201 202 if (stats) 203 hammer_add_zone_stat_layer2(stats, layer2); 204 } 205 } 206 rel_buffer(buffer1); 207 rel_buffer(buffer2); 208 209 if (stats) { 210 hammer_print_zone_stat(stats); 211 hammer_cleanup_zone_stat(stats); 212 } 213 214 if (num_bad_layer1 || VerboseOpt) 215 printf("%d bad layer1\n", num_bad_layer1); 216 if (num_bad_layer2 || VerboseOpt) 217 printf("%d bad layer2\n", num_bad_layer1); 218 } 219 220 void 221 hammer_cmd_checkmap(void) 222 { 223 volume_info_t volume; 224 hammer_blockmap_t freemap; 225 hammer_blockmap_t undomap; 226 hammer_off_t node_offset; 227 228 volume = get_root_volume(); 229 node_offset = volume->ondisk->vol0_btree_root; 230 freemap = &volume->ondisk->vol0_blockmap[HAMMER_ZONE_FREEMAP_INDEX]; 231 undomap = &volume->ondisk->vol0_blockmap[HAMMER_ZONE_UNDO_INDEX]; 232 233 print_blockmap(volume); 234 235 printf("Collecting allocation info from freemap: "); 236 fflush(stdout); 237 check_freemap(freemap); 238 printf("done\n"); 239 240 printf("Collecting allocation info from B-Tree: "); 241 fflush(stdout); 242 check_btree_node(node_offset, 0); 243 printf("done\n"); 244 245 printf("Collecting allocation info from UNDO: "); 246 fflush(stdout); 247 check_undo(undomap); 248 printf("done\n"); 249 250 dump_collect_table(); 251 } 252 253 static 254 void 255 check_freemap(hammer_blockmap_t freemap) 256 { 257 hammer_off_t offset; 258 buffer_info_t buffer1 = NULL; 259 hammer_blockmap_layer1_t layer1; 260 int i; 261 262 collect_freemap_layer1(freemap); 263 264 for (i = 0; i < HAMMER_BLOCKMAP_RADIX1; ++i) { 265 offset = freemap->phys_offset + i * sizeof(*layer1); 266 layer1 = get_buffer_data(offset, &buffer1, 0); 267 if (layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL) 268 collect_freemap_layer2(layer1); 269 } 270 rel_buffer(buffer1); 271 } 272 273 static 274 void 275 check_btree_node(hammer_off_t node_offset, int depth) 276 { 277 buffer_info_t buffer = NULL; 278 hammer_node_ondisk_t node; 279 hammer_btree_elm_t elm; 280 int i; 281 char badc = ' '; /* good */ 282 char badm = ' '; /* good */ 283 284 if (depth == 0) 285 collect_btree_root(node_offset); 286 node = get_buffer_data(node_offset, &buffer, 0); 287 288 if (node == NULL) { 289 badc = 'B'; 290 badm = 'I'; 291 } else if (!hammer_crc_test_btree(HammerVersion, node)) { 292 badc = 'B'; 293 } 294 295 if (badm != ' ' || badc != ' ') { /* not good */ 296 ++num_bad_node; 297 printf("%c%c NODE %016jx ", 298 badc, badm, (uintmax_t)node_offset); 299 if (node == NULL) { 300 printf("(IO ERROR)\n"); 301 rel_buffer(buffer); 302 return; 303 } else { 304 printf("cnt=%02d p=%016jx type=%c depth=%d mirror=%016jx\n", 305 node->count, 306 (uintmax_t)node->parent, 307 (node->type ? node->type : '?'), 308 depth, 309 (uintmax_t)node->mirror_tid); 310 } 311 } 312 313 for (i = 0; i < node->count; ++i) { 314 elm = &node->elms[i]; 315 316 switch(node->type) { 317 case HAMMER_BTREE_TYPE_INTERNAL: 318 if (elm->internal.subtree_offset) { 319 collect_btree_internal(elm); 320 check_btree_node(elm->internal.subtree_offset, 321 depth + 1); 322 } 323 break; 324 case HAMMER_BTREE_TYPE_LEAF: 325 if (elm->leaf.data_offset) 326 collect_btree_leaf(elm); 327 break; 328 default: 329 assert(!DebugOpt); 330 break; 331 } 332 } 333 rel_buffer(buffer); 334 } 335 336 static 337 void 338 check_undo(hammer_blockmap_t undomap) 339 { 340 buffer_info_t buffer = NULL; 341 hammer_off_t scan_offset; 342 hammer_fifo_head_t head; 343 344 scan_offset = HAMMER_ENCODE_UNDO(0); 345 while (scan_offset < undomap->alloc_offset) { 346 head = get_buffer_data(scan_offset, &buffer, 0); 347 switch (head->hdr_type) { 348 case HAMMER_HEAD_TYPE_PAD: 349 case HAMMER_HEAD_TYPE_DUMMY: 350 case HAMMER_HEAD_TYPE_UNDO: 351 case HAMMER_HEAD_TYPE_REDO: 352 collect_undo(scan_offset, head); 353 break; 354 default: 355 assert(!DebugOpt); 356 break; 357 } 358 if ((head->hdr_size & HAMMER_HEAD_ALIGN_MASK) || 359 head->hdr_size == 0 || 360 head->hdr_size > HAMMER_UNDO_ALIGN - 361 ((u_int)scan_offset & HAMMER_UNDO_MASK)) { 362 printf("Illegal size, skipping to next boundary\n"); 363 scan_offset = HAMMER_UNDO_DOALIGN(scan_offset); 364 } else { 365 scan_offset += head->hdr_size; 366 } 367 } 368 rel_buffer(buffer); 369 } 370 371 static __inline 372 void 373 collect_freemap_layer1(hammer_blockmap_t freemap) 374 { 375 /* 376 * This translation is necessary to do checkmap properly 377 * as zone4 is really just zone2 address space. 378 */ 379 hammer_off_t zone4_offset = hammer_xlate_to_zoneX( 380 HAMMER_ZONE_FREEMAP_INDEX, freemap->phys_offset); 381 collect_blockmap(zone4_offset, HAMMER_BIGBLOCK_SIZE, 382 HAMMER_ZONE_FREEMAP_INDEX); 383 } 384 385 static __inline 386 void 387 collect_freemap_layer2(hammer_blockmap_layer1_t layer1) 388 { 389 /* 390 * This translation is necessary to do checkmap properly 391 * as zone4 is really just zone2 address space. 392 */ 393 hammer_off_t zone4_offset = hammer_xlate_to_zoneX( 394 HAMMER_ZONE_FREEMAP_INDEX, layer1->phys_offset); 395 collect_blockmap(zone4_offset, HAMMER_BIGBLOCK_SIZE, 396 HAMMER_ZONE_FREEMAP_INDEX); 397 } 398 399 static __inline 400 void 401 collect_btree_root(hammer_off_t node_offset) 402 { 403 collect_blockmap(node_offset, 404 sizeof(struct hammer_node_ondisk), /* 4KB */ 405 HAMMER_ZONE_BTREE_INDEX); 406 } 407 408 static __inline 409 void 410 collect_btree_internal(hammer_btree_elm_t elm) 411 { 412 collect_blockmap(elm->internal.subtree_offset, 413 sizeof(struct hammer_node_ondisk), /* 4KB */ 414 HAMMER_ZONE_BTREE_INDEX); 415 } 416 417 static __inline 418 void 419 collect_btree_leaf(hammer_btree_elm_t elm) 420 { 421 int zone; 422 423 switch (elm->base.rec_type) { 424 case HAMMER_RECTYPE_INODE: 425 case HAMMER_RECTYPE_DIRENTRY: 426 case HAMMER_RECTYPE_EXT: 427 case HAMMER_RECTYPE_FIX: 428 case HAMMER_RECTYPE_PFS: 429 case HAMMER_RECTYPE_SNAPSHOT: 430 case HAMMER_RECTYPE_CONFIG: 431 zone = HAMMER_ZONE_META_INDEX; 432 break; 433 case HAMMER_RECTYPE_DATA: 434 case HAMMER_RECTYPE_DB: 435 zone = hammer_data_zone_index(elm->leaf.data_len); 436 break; 437 default: 438 zone = HAMMER_ZONE_UNAVAIL_INDEX; 439 break; 440 } 441 collect_blockmap(elm->leaf.data_offset, 442 HAMMER_DATA_DOALIGN(elm->leaf.data_len), zone); 443 } 444 445 static __inline 446 void 447 collect_undo(hammer_off_t scan_offset, hammer_fifo_head_t head) 448 { 449 collect_blockmap(scan_offset, head->hdr_size, 450 HAMMER_ZONE_UNDO_INDEX); 451 } 452 453 static 454 void 455 collect_blockmap(hammer_off_t offset, int32_t length, int zone) 456 { 457 struct hammer_blockmap_layer1 layer1; 458 struct hammer_blockmap_layer2 layer2; 459 hammer_blockmap_layer2_t track2; 460 hammer_off_t result_offset; 461 collect_t collect; 462 int error; 463 464 result_offset = blockmap_lookup_save(offset, &layer1, &layer2, &error); 465 if (DebugOpt) { 466 assert(HAMMER_ZONE_DECODE(offset) == zone); 467 assert(hammer_is_zone_raw_buffer(result_offset)); 468 assert(error == 0); 469 } 470 collect = collect_get(layer1.phys_offset); /* layer2 address */ 471 track2 = collect_get_track(collect, result_offset, zone, &layer2); 472 track2->bytes_free -= length; 473 } 474 475 static 476 collect_t 477 collect_get(hammer_off_t phys_offset) 478 { 479 collect_t collect; 480 481 collect = RB_LOOKUP(collect_rb_tree, &CollectTree, phys_offset); 482 if (collect) 483 return(collect); 484 485 collect = calloc(1, sizeof(*collect)); 486 collect->track2 = calloc(1, HAMMER_BIGBLOCK_SIZE); /* 1<<23 bytes */ 487 collect->layer2 = calloc(1, HAMMER_BIGBLOCK_SIZE); /* 1<<23 bytes */ 488 collect->offsets = calloc(HAMMER_BLOCKMAP_RADIX2, sizeof(hammer_off_t)); 489 collect->phys_offset = phys_offset; 490 RB_INSERT(collect_rb_tree, &CollectTree, collect); 491 492 return (collect); 493 } 494 495 static 496 void 497 collect_rel(collect_t collect) 498 { 499 free(collect->offsets); 500 free(collect->layer2); 501 free(collect->track2); 502 free(collect); 503 } 504 505 static 506 hammer_blockmap_layer2_t 507 collect_get_track(collect_t collect, hammer_off_t offset, int zone, 508 hammer_blockmap_layer2_t layer2) 509 { 510 hammer_blockmap_layer2_t track2; 511 size_t i; 512 513 i = HAMMER_BLOCKMAP_LAYER2_INDEX(offset); 514 track2 = &collect->track2[i]; 515 if (track2->entry_crc == 0) { 516 collect->layer2[i] = *layer2; 517 collect->offsets[i] = offset & ~HAMMER_BIGBLOCK_MASK64; 518 track2->zone = zone; 519 track2->bytes_free = HAMMER_BIGBLOCK_SIZE; 520 track2->entry_crc = 1; /* steal field to tag track load */ 521 } 522 return (track2); 523 } 524 525 static 526 void 527 dump_collect_table(void) 528 { 529 collect_t collect; 530 int error = 0; 531 zone_stat_t stats = NULL; 532 533 if (VerboseOpt) 534 stats = hammer_init_zone_stat(); 535 536 RB_FOREACH(collect, collect_rb_tree, &CollectTree) { 537 dump_collect(collect, stats); 538 error += collect->error; 539 } 540 541 while ((collect = RB_ROOT(&CollectTree)) != NULL) { 542 RB_REMOVE(collect_rb_tree, &CollectTree, collect); 543 collect_rel(collect); 544 } 545 assert(RB_EMPTY(&CollectTree)); 546 547 if (stats) { 548 hammer_print_zone_stat(stats); 549 hammer_cleanup_zone_stat(stats); 550 } 551 552 if (num_bad_node || VerboseOpt) 553 printf("%d bad nodes\n", num_bad_node); 554 if (error || VerboseOpt) 555 printf("%d errors\n", error); 556 } 557 558 static 559 void 560 dump_collect(collect_t collect, zone_stat_t stats) 561 { 562 hammer_blockmap_layer2_t track2; 563 hammer_blockmap_layer2_t layer2; 564 hammer_off_t offset; 565 int i; 566 567 for (i = 0; i < HAMMER_BLOCKMAP_RADIX2; ++i) { 568 track2 = &collect->track2[i]; 569 layer2 = &collect->layer2[i]; 570 offset = collect->offsets[i]; 571 572 /* 573 * Check big-blocks referenced by freemap, data, 574 * B-Tree nodes and UNDO fifo. 575 */ 576 if (track2->entry_crc == 0) 577 continue; 578 579 if (DebugOpt) { 580 assert((layer2->zone == HAMMER_ZONE_UNDO_INDEX) || 581 (layer2->zone == HAMMER_ZONE_FREEMAP_INDEX) || 582 hammer_is_index_record(layer2->zone)); 583 } 584 if (stats) 585 hammer_add_zone_stat_layer2(stats, layer2); 586 587 if (track2->zone != layer2->zone) { 588 printf("BZ\tblock=%016jx calc zone=%-2d, got zone=%-2d\n", 589 (uintmax_t)offset, 590 track2->zone, 591 layer2->zone); 592 collect->error++; 593 } else if (track2->bytes_free != layer2->bytes_free) { 594 printf("BM\tblock=%016jx zone=%-2d calc %d free, got %d\n", 595 (uintmax_t)offset, 596 layer2->zone, 597 track2->bytes_free, 598 layer2->bytes_free); 599 collect->error++; 600 } else if (VerboseOpt) { 601 printf("\tblock=%016jx zone=%-2d %d free (correct)\n", 602 (uintmax_t)offset, 603 layer2->zone, 604 track2->bytes_free); 605 } 606 } 607 } 608