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 * $DragonFly: src/sbin/hammer/cmd_blockmap.c,v 1.4 2008/07/19 18:48:14 dillon Exp $ 35 */ 36 37 #include "hammer.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 struct hammer_blockmap_layer2 *track2; /* track of layer2 entries */ 47 struct hammer_blockmap_layer2 *layer2; /* 1<<19 x 16 bytes entries */ 48 int error; /* # of inconsistencies */ 49 } *collect_t; 50 51 static int 52 collect_compare(struct collect *c1, struct collect *c2) 53 { 54 if (c1->phys_offset < c2->phys_offset) 55 return(-1); 56 if (c1->phys_offset > c2->phys_offset) 57 return(1); 58 return(0); 59 } 60 61 RB_HEAD(collect_rb_tree, collect) CollectTree = RB_INITIALIZER(&CollectTree); 62 RB_PROTOTYPE2(collect_rb_tree, collect, entry, collect_compare, hammer_off_t); 63 RB_GENERATE2(collect_rb_tree, collect, entry, collect_compare, hammer_off_t, 64 phys_offset); 65 66 static void dump_blockmap(const char *label, int zone); 67 static void check_btree_node(hammer_off_t node_offset, int depth); 68 static void check_undo(hammer_blockmap_t rootmap); 69 static __inline void collect_btree_root(hammer_off_t node_offset); 70 static __inline void collect_btree_internal(hammer_btree_elm_t elm); 71 static __inline void collect_btree_leaf(hammer_btree_elm_t elm); 72 static __inline void collect_undo(hammer_off_t scan_offset, 73 hammer_fifo_head_t head); 74 static void collect_blockmap(hammer_off_t offset, int32_t length, int zone); 75 static struct hammer_blockmap_layer2 *collect_get_track( 76 collect_t collect, hammer_off_t offset, int zone, 77 struct hammer_blockmap_layer2 *layer2); 78 static collect_t collect_get(hammer_off_t phys_offset); 79 static void dump_collect_table(void); 80 static void dump_collect(collect_t collect, int *stats); 81 82 void 83 hammer_cmd_blockmap(void) 84 { 85 dump_blockmap("freemap", HAMMER_ZONE_FREEMAP_INDEX); 86 } 87 88 static 89 void 90 dump_blockmap(const char *label, int zone) 91 { 92 struct volume_info *root_volume; 93 hammer_blockmap_t rootmap; 94 struct hammer_blockmap_layer1 *layer1; 95 struct hammer_blockmap_layer2 *layer2; 96 struct buffer_info *buffer1 = NULL; 97 struct buffer_info *buffer2 = NULL; 98 hammer_off_t layer1_offset; 99 hammer_off_t layer2_offset; 100 hammer_off_t scan1; 101 hammer_off_t scan2; 102 int xerr; 103 104 assert(RootVolNo >= 0); 105 root_volume = get_volume(RootVolNo); 106 rootmap = &root_volume->ondisk->vol0_blockmap[zone]; 107 assert(rootmap->phys_offset != 0); 108 109 printf("zone %-16s next %016jx alloc %016jx\n", 110 label, 111 (uintmax_t)rootmap->next_offset, 112 (uintmax_t)rootmap->alloc_offset); 113 114 for (scan1 = HAMMER_ZONE_ENCODE(zone, 0); 115 scan1 < HAMMER_ZONE_ENCODE(zone, HAMMER_OFF_LONG_MASK); 116 scan1 += HAMMER_BLOCKMAP_LAYER2) { 117 /* 118 * Dive layer 1. 119 */ 120 layer1_offset = rootmap->phys_offset + 121 HAMMER_BLOCKMAP_LAYER1_OFFSET(scan1); 122 layer1 = get_buffer_data(layer1_offset, &buffer1, 0); 123 xerr = ' '; 124 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) 125 xerr = 'B'; 126 if (xerr == ' ' && 127 layer1->phys_offset == HAMMER_BLOCKMAP_UNAVAIL) { 128 continue; 129 } 130 printf("%c layer1 %016jx @%016jx blocks-free %jd\n", 131 xerr, 132 (uintmax_t)scan1, 133 (uintmax_t)layer1->phys_offset, 134 (intmax_t)layer1->blocks_free); 135 if (layer1->phys_offset == HAMMER_BLOCKMAP_FREE) 136 continue; 137 for (scan2 = scan1; 138 scan2 < scan1 + HAMMER_BLOCKMAP_LAYER2; 139 scan2 += HAMMER_BIGBLOCK_SIZE 140 ) { 141 /* 142 * Dive layer 2, each entry represents a big-block. 143 */ 144 layer2_offset = layer1->phys_offset + 145 HAMMER_BLOCKMAP_LAYER2_OFFSET(scan2); 146 layer2 = get_buffer_data(layer2_offset, &buffer2, 0); 147 xerr = ' '; 148 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) 149 xerr = 'B'; 150 printf("%c %016jx zone=%d app=%-7d free=%-7d\n", 151 xerr, 152 (uintmax_t)scan2, 153 layer2->zone, 154 layer2->append_off, 155 layer2->bytes_free); 156 } 157 } 158 rel_buffer(buffer1); 159 rel_buffer(buffer2); 160 rel_volume(root_volume); 161 } 162 163 void 164 hammer_cmd_checkmap(void) 165 { 166 struct volume_info *volume; 167 hammer_blockmap_t rootmap; 168 hammer_off_t node_offset; 169 170 volume = get_volume(RootVolNo); 171 node_offset = volume->ondisk->vol0_btree_root; 172 rootmap = &volume->ondisk->vol0_blockmap[HAMMER_ZONE_UNDO_INDEX]; 173 174 if (QuietOpt < 3) { 175 printf("Volume header\trecords=%jd next_tid=%016jx\n", 176 (intmax_t)volume->ondisk->vol0_stat_records, 177 (uintmax_t)volume->ondisk->vol0_next_tid); 178 printf("\t\tbufoffset=%016jx\n", 179 (uintmax_t)volume->ondisk->vol_buf_beg); 180 printf("\t\tundosize=%jdMB\n", 181 (intmax_t)((rootmap->alloc_offset & HAMMER_OFF_LONG_MASK) 182 / (1024 * 1024))); 183 } 184 rel_volume(volume); 185 186 assert(HAMMER_ZONE_UNDO_INDEX < HAMMER_ZONE2_MAPPED_INDEX); 187 assert(HAMMER_ZONE2_MAPPED_INDEX < HAMMER_MAX_ZONES); 188 AssertOnFailure = 0; 189 190 printf("Collecting allocation info from B-Tree: "); 191 fflush(stdout); 192 collect_btree_root(node_offset); 193 check_btree_node(node_offset, 0); 194 printf("done\n"); 195 196 printf("Collecting allocation info from UNDO: "); 197 fflush(stdout); 198 check_undo(rootmap); 199 printf("done\n"); 200 201 dump_collect_table(); 202 AssertOnFailure = 1; 203 } 204 205 static void 206 check_btree_node(hammer_off_t node_offset, int depth) 207 { 208 struct buffer_info *buffer = NULL; 209 hammer_node_ondisk_t node; 210 hammer_btree_elm_t elm; 211 int i; 212 char badc; 213 214 node = get_node(node_offset, &buffer); 215 216 if (crc32(&node->crc + 1, HAMMER_BTREE_CRCSIZE) == node->crc) 217 badc = ' '; 218 else 219 badc = 'B'; 220 221 if (badc != ' ') { 222 printf("%c NODE %016jx cnt=%02d p=%016jx " 223 "type=%c depth=%d", 224 badc, 225 (uintmax_t)node_offset, node->count, 226 (uintmax_t)node->parent, 227 (node->type ? node->type : '?'), depth); 228 printf(" mirror %016jx\n", (uintmax_t)node->mirror_tid); 229 } 230 231 for (i = 0; i < node->count; ++i) { 232 elm = &node->elms[i]; 233 234 switch(node->type) { 235 case HAMMER_BTREE_TYPE_INTERNAL: 236 if (elm->internal.subtree_offset) { 237 collect_btree_internal(elm); 238 check_btree_node(elm->internal.subtree_offset, 239 depth + 1); 240 } 241 break; 242 case HAMMER_BTREE_TYPE_LEAF: 243 if (elm->leaf.data_offset) 244 collect_btree_leaf(elm); 245 break; 246 default: 247 if (AssertOnFailure) 248 assert(0); 249 break; 250 } 251 } 252 rel_buffer(buffer); 253 } 254 255 static void 256 check_undo(hammer_blockmap_t rootmap) 257 { 258 struct buffer_info *buffer = NULL; 259 hammer_off_t scan_offset; 260 hammer_fifo_head_t head; 261 262 scan_offset = HAMMER_ZONE_ENCODE(HAMMER_ZONE_UNDO_INDEX, 0); 263 while (scan_offset < rootmap->alloc_offset) { 264 head = get_buffer_data(scan_offset, &buffer, 0); 265 switch (head->hdr_type) { 266 case HAMMER_HEAD_TYPE_PAD: 267 case HAMMER_HEAD_TYPE_DUMMY: 268 case HAMMER_HEAD_TYPE_UNDO: 269 case HAMMER_HEAD_TYPE_REDO: 270 collect_undo(scan_offset, head); 271 break; 272 default: 273 if (AssertOnFailure) 274 assert(0); 275 break; 276 } 277 if ((head->hdr_size & HAMMER_HEAD_ALIGN_MASK) || 278 head->hdr_size == 0 || 279 head->hdr_size > HAMMER_UNDO_ALIGN - 280 ((u_int)scan_offset & HAMMER_UNDO_MASK)) { 281 printf("Illegal size, skipping to next boundary\n"); 282 scan_offset = (scan_offset + HAMMER_UNDO_MASK) & 283 ~HAMMER_UNDO_MASK64; 284 } else { 285 scan_offset += head->hdr_size; 286 } 287 } 288 rel_buffer(buffer); 289 } 290 291 static __inline 292 void 293 collect_btree_root(hammer_off_t node_offset) 294 { 295 collect_blockmap(node_offset, 296 sizeof(struct hammer_node_ondisk), /* 4KB */ 297 HAMMER_ZONE_BTREE_INDEX); 298 } 299 300 static __inline 301 void 302 collect_btree_internal(hammer_btree_elm_t elm) 303 { 304 collect_blockmap(elm->internal.subtree_offset, 305 sizeof(struct hammer_node_ondisk), /* 4KB */ 306 HAMMER_ZONE_BTREE_INDEX); 307 } 308 309 static __inline 310 void 311 collect_btree_leaf(hammer_btree_elm_t elm) 312 { 313 int zone; 314 315 switch (elm->base.rec_type) { 316 case HAMMER_RECTYPE_INODE: 317 case HAMMER_RECTYPE_DIRENTRY: 318 case HAMMER_RECTYPE_EXT: 319 case HAMMER_RECTYPE_FIX: 320 case HAMMER_RECTYPE_PFS: 321 case HAMMER_RECTYPE_SNAPSHOT: 322 case HAMMER_RECTYPE_CONFIG: 323 zone = HAMMER_ZONE_META_INDEX; 324 break; 325 case HAMMER_RECTYPE_DATA: 326 case HAMMER_RECTYPE_DB: 327 /* 328 * There is an exceptional case where HAMMER uses 329 * HAMMER_ZONE_LARGE_DATA when the data length is 330 * >HAMMER_BUFSIZE/2 (not >=HAMMER_BUFSIZE). 331 * This exceptional case is currently being used 332 * by mirror write code, however the following code 333 * can ignore that and simply use the normal way 334 * of selecting a zone using >=HAMMER_BUFSIZE. 335 * See hammer_alloc_data() for details. 336 */ 337 zone = elm->leaf.data_len >= HAMMER_BUFSIZE ? 338 HAMMER_ZONE_LARGE_DATA_INDEX : 339 HAMMER_ZONE_SMALL_DATA_INDEX; 340 break; 341 default: 342 zone = HAMMER_ZONE_UNAVAIL_INDEX; 343 break; 344 } 345 collect_blockmap(elm->leaf.data_offset, 346 (elm->leaf.data_len + 15) & ~15, zone); 347 } 348 349 static __inline 350 void 351 collect_undo(hammer_off_t scan_offset, hammer_fifo_head_t head) 352 { 353 collect_blockmap(scan_offset, head->hdr_size, 354 HAMMER_ZONE_UNDO_INDEX); 355 } 356 357 static 358 void 359 collect_blockmap(hammer_off_t offset, int32_t length, int zone) 360 { 361 struct hammer_blockmap_layer1 layer1; 362 struct hammer_blockmap_layer2 layer2; 363 struct hammer_blockmap_layer2 *track2; 364 hammer_off_t result_offset; 365 collect_t collect; 366 int error; 367 368 result_offset = blockmap_lookup(offset, &layer1, &layer2, &error); 369 if (AssertOnFailure) { 370 assert(HAMMER_ZONE_DECODE(offset) == zone); 371 assert(HAMMER_ZONE_DECODE(result_offset) == 372 HAMMER_ZONE_RAW_BUFFER_INDEX); 373 assert(error == 0); 374 } 375 collect = collect_get(layer1.phys_offset); /* layer2 address */ 376 track2 = collect_get_track(collect, offset, zone, &layer2); 377 track2->bytes_free -= length; 378 } 379 380 static 381 collect_t 382 collect_get(hammer_off_t phys_offset) 383 { 384 collect_t collect; 385 386 collect = RB_LOOKUP(collect_rb_tree, &CollectTree, phys_offset); 387 if (collect) 388 return(collect); 389 390 collect = calloc(sizeof(*collect), 1); 391 collect->track2 = malloc(HAMMER_BIGBLOCK_SIZE); /* 1<<23 bytes */ 392 collect->layer2 = malloc(HAMMER_BIGBLOCK_SIZE); /* 1<<23 bytes */ 393 collect->phys_offset = phys_offset; 394 RB_INSERT(collect_rb_tree, &CollectTree, collect); 395 bzero(collect->track2, HAMMER_BIGBLOCK_SIZE); 396 bzero(collect->layer2, HAMMER_BIGBLOCK_SIZE); 397 398 return (collect); 399 } 400 401 static 402 void 403 collect_rel(collect_t collect) 404 { 405 free(collect->layer2); 406 free(collect->track2); 407 free(collect); 408 } 409 410 static 411 struct hammer_blockmap_layer2 * 412 collect_get_track(collect_t collect, hammer_off_t offset, int zone, 413 struct hammer_blockmap_layer2 *layer2) 414 { 415 struct hammer_blockmap_layer2 *track2; 416 size_t i; 417 418 i = HAMMER_BLOCKMAP_LAYER2_OFFSET(offset) / sizeof(*track2); 419 track2 = &collect->track2[i]; 420 if (track2->entry_crc == 0) { 421 collect->layer2[i] = *layer2; 422 track2->zone = zone; 423 track2->bytes_free = HAMMER_BIGBLOCK_SIZE; 424 track2->entry_crc = 1; /* steal field to tag track load */ 425 } 426 return (track2); 427 } 428 429 static 430 void 431 dump_collect_table(void) 432 { 433 collect_t collect; 434 int i; 435 int error = 0; 436 int total = 0; 437 int stats[HAMMER_MAX_ZONES]; 438 bzero(stats, sizeof(stats)); 439 440 RB_FOREACH(collect, collect_rb_tree, &CollectTree) { 441 dump_collect(collect, stats); 442 error += collect->error; 443 } 444 445 while ((collect = RB_ROOT(&CollectTree)) != NULL) { 446 RB_REMOVE(collect_rb_tree, &CollectTree, collect); 447 collect_rel(collect); 448 } 449 assert(RB_EMPTY(&CollectTree)); 450 451 if (VerboseOpt) { 452 printf("Statistics\n"); 453 printf("\tzone #\tbig-blocks\n"); 454 for (i = 0; i < HAMMER_MAX_ZONES; i++) { 455 printf("\tzone %d\t%d\n", i, stats[i]); 456 total += stats[i]; 457 } 458 printf("\t---------------\n"); 459 printf("\ttotal\t%d\n", total); 460 } 461 462 if (error || VerboseOpt) 463 printf("%d errors\n", error); 464 } 465 466 static 467 void 468 dump_collect(collect_t collect, int *stats) 469 { 470 struct hammer_blockmap_layer2 *track2; 471 struct hammer_blockmap_layer2 *layer2; 472 hammer_off_t offset; 473 size_t i; 474 int zone; 475 476 for (i = 0; i < HAMMER_BLOCKMAP_RADIX2; ++i) { 477 track2 = &collect->track2[i]; 478 layer2 = &collect->layer2[i]; 479 offset = collect->phys_offset + i * HAMMER_BIGBLOCK_SIZE; 480 481 /* 482 * Check big-blocks referenced by data, B-Tree nodes 483 * and UNDO fifo. 484 */ 485 if (track2->entry_crc == 0) 486 continue; 487 488 zone = layer2->zone; 489 if (AssertOnFailure) { 490 assert((zone == HAMMER_ZONE_UNDO_INDEX) || 491 (zone >= HAMMER_ZONE2_MAPPED_INDEX && 492 zone < HAMMER_MAX_ZONES)); 493 } 494 stats[zone]++; 495 496 if (track2->zone != layer2->zone) { 497 printf("BZ\tblock=%016jx calc zone=%2d, got zone=%2d\n", 498 (intmax_t)offset, 499 track2->zone, 500 layer2->zone); 501 collect->error++; 502 } else if (track2->bytes_free != layer2->bytes_free) { 503 printf("BM\tblock=%016jx zone=%2d calc %d free, got %d\n", 504 (intmax_t)offset, 505 layer2->zone, 506 track2->bytes_free, 507 layer2->bytes_free); 508 collect->error++; 509 } else if (VerboseOpt) { 510 printf("\tblock=%016jx zone=%2d %d free (correct)\n", 511 (intmax_t)offset, 512 layer2->zone, 513 track2->bytes_free); 514 } 515 } 516 } 517