2 * Copyright (c) 2008 The DragonFly Project. All rights reserved.
4 * This code is derived from software contributed to The DragonFly Project
5 * by Matthew Dillon <dillon@backplane.com>
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
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
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.
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
34 * $DragonFly: src/sbin/hammer/cmd_blockmap.c,v 1.4 2008/07/19 18:48:14 dillon Exp $
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).
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 */
52 collect_compare(struct collect *c1, struct collect *c2)
54 if (c1->phys_offset < c2->phys_offset)
56 if (c1->phys_offset > c2->phys_offset)
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,
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);
83 hammer_cmd_blockmap(void)
85 dump_blockmap("freemap", HAMMER_ZONE_FREEMAP_INDEX);
90 dump_blockmap(const char *label, int zone)
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;
104 assert(RootVolNo >= 0);
105 root_volume = get_volume(RootVolNo);
106 rootmap = &root_volume->ondisk->vol0_blockmap[zone];
107 assert(rootmap->phys_offset != 0);
109 printf("zone %-16s next %016jx alloc %016jx\n",
111 (uintmax_t)rootmap->next_offset,
112 (uintmax_t)rootmap->alloc_offset);
114 for (scan1 = HAMMER_ZONE_ENCODE(zone, 0);
115 scan1 < HAMMER_ZONE_ENCODE(zone, HAMMER_OFF_LONG_MASK);
116 scan1 += HAMMER_BLOCKMAP_LAYER2) {
120 layer1_offset = rootmap->phys_offset +
121 HAMMER_BLOCKMAP_LAYER1_OFFSET(scan1);
122 layer1 = get_buffer_data(layer1_offset, &buffer1, 0);
124 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE))
127 layer1->phys_offset == HAMMER_BLOCKMAP_UNAVAIL) {
130 printf("%c layer1 %016jx @%016jx blocks-free %jd\n",
133 (uintmax_t)layer1->phys_offset,
134 (intmax_t)layer1->blocks_free);
135 if (layer1->phys_offset == HAMMER_BLOCKMAP_FREE)
138 scan2 < scan1 + HAMMER_BLOCKMAP_LAYER2;
139 scan2 += HAMMER_BIGBLOCK_SIZE
142 * Dive layer 2, each entry represents a big-block.
144 layer2_offset = layer1->phys_offset +
145 HAMMER_BLOCKMAP_LAYER2_OFFSET(scan2);
146 layer2 = get_buffer_data(layer2_offset, &buffer2, 0);
148 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE))
150 printf("%c %016jx zone=%-2d app=%-7d free=%-7d\n",
160 rel_volume(root_volume);
164 hammer_cmd_checkmap(void)
166 struct volume_info *volume;
167 hammer_blockmap_t rootmap;
168 hammer_off_t node_offset;
170 volume = get_volume(RootVolNo);
171 node_offset = volume->ondisk->vol0_btree_root;
172 rootmap = &volume->ondisk->vol0_blockmap[HAMMER_ZONE_UNDO_INDEX];
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)
186 assert(HAMMER_ZONE_UNDO_INDEX < HAMMER_ZONE2_MAPPED_INDEX);
187 assert(HAMMER_ZONE2_MAPPED_INDEX < HAMMER_MAX_ZONES);
190 printf("Collecting allocation info from B-Tree: ");
192 collect_btree_root(node_offset);
193 check_btree_node(node_offset, 0);
196 printf("Collecting allocation info from UNDO: ");
201 dump_collect_table();
206 check_btree_node(hammer_off_t node_offset, int depth)
208 struct buffer_info *buffer = NULL;
209 hammer_node_ondisk_t node;
210 hammer_btree_elm_t elm;
214 node = get_node(node_offset, &buffer);
216 if (crc32(&node->crc + 1, HAMMER_BTREE_CRCSIZE) == node->crc)
222 printf("%c NODE %016jx cnt=%02d p=%016jx "
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);
231 for (i = 0; i < node->count; ++i) {
232 elm = &node->elms[i];
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,
242 case HAMMER_BTREE_TYPE_LEAF:
243 if (elm->leaf.data_offset)
244 collect_btree_leaf(elm);
256 check_undo(hammer_blockmap_t rootmap)
258 struct buffer_info *buffer = NULL;
259 hammer_off_t scan_offset;
260 hammer_fifo_head_t head;
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);
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) &
285 scan_offset += head->hdr_size;
293 collect_btree_root(hammer_off_t node_offset)
295 collect_blockmap(node_offset,
296 sizeof(struct hammer_node_ondisk), /* 4KB */
297 HAMMER_ZONE_BTREE_INDEX);
302 collect_btree_internal(hammer_btree_elm_t elm)
304 collect_blockmap(elm->internal.subtree_offset,
305 sizeof(struct hammer_node_ondisk), /* 4KB */
306 HAMMER_ZONE_BTREE_INDEX);
311 collect_btree_leaf(hammer_btree_elm_t elm)
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;
325 case HAMMER_RECTYPE_DATA:
326 case HAMMER_RECTYPE_DB:
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.
337 zone = elm->leaf.data_len >= HAMMER_BUFSIZE ?
338 HAMMER_ZONE_LARGE_DATA_INDEX :
339 HAMMER_ZONE_SMALL_DATA_INDEX;
342 zone = HAMMER_ZONE_UNAVAIL_INDEX;
345 collect_blockmap(elm->leaf.data_offset,
346 (elm->leaf.data_len + 15) & ~15, zone);
351 collect_undo(hammer_off_t scan_offset, hammer_fifo_head_t head)
353 collect_blockmap(scan_offset, head->hdr_size,
354 HAMMER_ZONE_UNDO_INDEX);
359 collect_blockmap(hammer_off_t offset, int32_t length, int zone)
361 struct hammer_blockmap_layer1 layer1;
362 struct hammer_blockmap_layer2 layer2;
363 struct hammer_blockmap_layer2 *track2;
364 hammer_off_t result_offset;
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);
375 collect = collect_get(layer1.phys_offset); /* layer2 address */
376 track2 = collect_get_track(collect, offset, zone, &layer2);
377 track2->bytes_free -= length;
382 collect_get(hammer_off_t phys_offset)
386 collect = RB_LOOKUP(collect_rb_tree, &CollectTree, phys_offset);
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);
403 collect_rel(collect_t collect)
405 free(collect->layer2);
406 free(collect->track2);
411 struct hammer_blockmap_layer2 *
412 collect_get_track(collect_t collect, hammer_off_t offset, int zone,
413 struct hammer_blockmap_layer2 *layer2)
415 struct hammer_blockmap_layer2 *track2;
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;
423 track2->bytes_free = HAMMER_BIGBLOCK_SIZE;
424 track2->entry_crc = 1; /* steal field to tag track load */
431 dump_collect_table(void)
437 int stats[HAMMER_MAX_ZONES];
438 bzero(stats, sizeof(stats));
440 RB_FOREACH(collect, collect_rb_tree, &CollectTree) {
441 dump_collect(collect, stats);
442 error += collect->error;
445 while ((collect = RB_ROOT(&CollectTree)) != NULL) {
446 RB_REMOVE(collect_rb_tree, &CollectTree, collect);
447 collect_rel(collect);
449 assert(RB_EMPTY(&CollectTree));
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]);
458 printf("\t---------------\n");
459 printf("\ttotal\t%d\n", total);
462 if (error || VerboseOpt)
463 printf("%d errors\n", error);
468 dump_collect(collect_t collect, int *stats)
470 struct hammer_blockmap_layer2 *track2;
471 struct hammer_blockmap_layer2 *layer2;
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;
482 * Check big-blocks referenced by data, B-Tree nodes
485 if (track2->entry_crc == 0)
489 if (AssertOnFailure) {
490 assert((zone == HAMMER_ZONE_UNDO_INDEX) ||
491 (zone >= HAMMER_ZONE2_MAPPED_INDEX &&
492 zone < HAMMER_MAX_ZONES));
496 if (track2->zone != layer2->zone) {
497 printf("BZ\tblock=%016jx calc zone=%-2d, got zone=%-2d\n",
502 } else if (track2->bytes_free != layer2->bytes_free) {
503 printf("BM\tblock=%016jx zone=%-2d calc %d free, got %d\n",
509 } else if (VerboseOpt) {
510 printf("\tblock=%016jx zone=%-2d %d free (correct)\n",