2 * Copyright (c) 2019 Tomohiro Kusumi <tkusumi@netbsd.org>
3 * Copyright (c) 2019 The DragonFly Project
6 * This code is derived from software contributed to The DragonFly Project
7 * by Matthew Dillon <dillon@dragonflybsd.org>
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in
17 * the documentation and/or other materials provided with the
19 * 3. Neither the name of The DragonFly Project nor the names of its
20 * contributors may be used to endorse or promote products derived
21 * from this software without specific, prior written permission.
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
26 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
27 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
28 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
29 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
30 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
31 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
32 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
33 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
37 #include <sys/types.h>
40 #include <sys/queue.h>
41 #include <sys/ttycom.h>
51 #include <openssl/sha.h>
53 #include <vfs/hammer2/hammer2_disk.h>
54 #include <vfs/hammer2/hammer2_xxhash.h>
56 #include "fsck_hammer2.h"
59 TAILQ_ENTRY(blockref_msg) entry;
63 struct blockref_entry {
64 RB_ENTRY(blockref_entry) entry;
65 hammer2_off_t data_off;
66 TAILQ_HEAD(, blockref_msg) head;
70 blockref_cmp(struct blockref_entry *b1, struct blockref_entry *b2)
72 if (b1->data_off < b2->data_off)
74 if (b1->data_off > b2->data_off)
79 RB_HEAD(blockref_tree, blockref_entry);
80 RB_PROTOTYPE2(blockref_tree, blockref_entry, entry, blockref_cmp,
82 RB_GENERATE2(blockref_tree, blockref_entry, entry, blockref_cmp, hammer2_off_t,
86 struct blockref_tree root;
87 uint8_t type; /* HAMMER2_BREF_TYPE_VOLUME or FREEMAP */
88 uint64_t total_blockref;
90 uint64_t total_invalid;
93 /* use volume or freemap depending on type value */
96 uint64_t total_indirect;
98 uint64_t total_dirent;
101 uint64_t total_freemap_node;
102 uint64_t total_freemap_leaf;
107 static void init_blockref_stats(blockref_stats_t *, uint8_t);
108 static void cleanup_blockref_stats(blockref_stats_t *);
109 static void print_blockref_stats(const blockref_stats_t *, bool);
110 static int verify_volume_header(const hammer2_volume_data_t *);
111 static int verify_blockref(int, const hammer2_volume_data_t *,
112 const hammer2_blockref_t *, bool, blockref_stats_t *);
114 static int best_zone = -1;
119 tfprintf(FILE *fp, int tab, const char *ctl, ...)
124 fprintf(fp, "%*s", tab, "");
128 vfprintf(fp, ctl, va);
133 find_best_zone(int fd)
135 hammer2_blockref_t best;
138 memset(&best, 0, sizeof(best));
140 for (i = 0; i < HAMMER2_NUM_VOLHDRS; ++i) {
141 hammer2_volume_data_t voldata;
142 hammer2_blockref_t broot;
145 memset(&broot, 0, sizeof(broot));
146 broot.data_off = (i * HAMMER2_ZONE_BYTES64) | HAMMER2_PBUFRADIX;
147 lseek(fd, broot.data_off & ~HAMMER2_OFF_MASK_RADIX, SEEK_SET);
149 ret = read(fd, &voldata, HAMMER2_PBUFSIZE);
150 if (ret == HAMMER2_PBUFSIZE) {
151 if ((voldata.magic != HAMMER2_VOLUME_ID_HBO) &&
152 (voldata.magic != HAMMER2_VOLUME_ID_ABO))
154 broot.mirror_tid = voldata.mirror_tid;
155 if (best_i < 0 || best.mirror_tid < broot.mirror_tid) {
159 } else if (ret == -1) {
163 tfprintf(stderr, 1, "Failed to read volume header\n");
172 test_volume_header(int fd)
177 for (i = 0; i < HAMMER2_NUM_VOLHDRS; ++i) {
178 hammer2_volume_data_t voldata;
179 hammer2_blockref_t broot;
182 memset(&broot, 0, sizeof(broot));
183 broot.data_off = (i * HAMMER2_ZONE_BYTES64) | HAMMER2_PBUFRADIX;
184 lseek(fd, broot.data_off & ~HAMMER2_OFF_MASK_RADIX, SEEK_SET);
186 ret = read(fd, &voldata, HAMMER2_PBUFSIZE);
187 if (ret == HAMMER2_PBUFSIZE) {
188 broot.mirror_tid = voldata.mirror_tid;
190 printf("zone.%d %016lX%s\n", i, broot.data_off,
191 (i == best_zone) ? " (best)" : "");
192 if (verify_volume_header(&voldata) == -1)
194 } else if (ret == -1) {
198 tfprintf(stderr, 1, "Failed to read volume header\n");
203 return failed ? -1 : 0;
207 test_blockref(int fd, uint8_t type)
212 for (i = 0; i < HAMMER2_NUM_VOLHDRS; ++i) {
213 hammer2_volume_data_t voldata;
214 hammer2_blockref_t broot;
217 memset(&broot, 0, sizeof(broot));
219 broot.data_off = (i * HAMMER2_ZONE_BYTES64) | HAMMER2_PBUFRADIX;
220 lseek(fd, broot.data_off & ~HAMMER2_OFF_MASK_RADIX, SEEK_SET);
222 ret = read(fd, &voldata, HAMMER2_PBUFSIZE);
223 if (ret == HAMMER2_PBUFSIZE) {
224 blockref_stats_t bstats;
225 struct blockref_entry *e;
226 broot.mirror_tid = voldata.mirror_tid;
227 init_blockref_stats(&bstats, type);
229 printf("zone.%d %016lX%s\n", i, broot.data_off,
230 (i == best_zone) ? " (best)" : "");
231 if (verify_blockref(fd, &voldata, &broot, false,
234 print_blockref_stats(&bstats, true);
236 RB_FOREACH(e, blockref_tree, &bstats.root) {
237 struct blockref_msg *m;
238 TAILQ_FOREACH(m, &e->head, entry) {
239 tfprintf(stderr, 1, "%016lX %s\n",
240 e->data_off, m->msg);
243 cleanup_blockref_stats(&bstats);
244 } else if (ret == -1) {
248 tfprintf(stderr, 1, "Failed to read volume header\n");
253 return failed ? -1 : 0;
264 if (ioctl(0, TIOCGWINSZ, &ws) != -1)
266 if (columns == 0 && (cp = getenv("COLUMNS")))
269 columns = 80; /* last resort */
275 add_blockref_entry(blockref_stats_t *bstats, hammer2_off_t data_off,
278 struct blockref_entry *e;
279 struct blockref_msg *m;
281 e = RB_LOOKUP(blockref_tree, &bstats->root, data_off);
283 e = calloc(1, sizeof(*e));
285 TAILQ_INIT(&e->head);
288 m = calloc(1, sizeof(*m));
290 m->msg = strdup(msg);
292 e->data_off = data_off;
293 TAILQ_INSERT_TAIL(&e->head, m, entry);
294 RB_INSERT(blockref_tree, &bstats->root, e);
298 init_blockref_stats(blockref_stats_t *bstats, uint8_t type)
300 memset(bstats, 0, sizeof(*bstats));
302 RB_INIT(&bstats->root);
306 cleanup_blockref_stats(blockref_stats_t *bstats)
308 struct blockref_entry *e;
310 while ((e = RB_ROOT(&bstats->root)) != NULL) {
311 struct blockref_msg *m;
312 RB_REMOVE(blockref_tree, &bstats->root, e);
313 while ((m = TAILQ_FIRST(&e->head)) != NULL) {
314 TAILQ_REMOVE(&e->head, m, entry);
318 assert(TAILQ_EMPTY(&e->head));
321 assert(RB_EMPTY(&bstats->root));
325 print_blockref_stats(const blockref_stats_t *bstats, bool newline)
327 size_t siz = charsperline();
328 char *buf = calloc(1, siz);
332 switch (bstats->type) {
333 case HAMMER2_BREF_TYPE_VOLUME:
334 snprintf(buf, siz, "%*s%ju blockref (%ju inode, %ju indirect, "
335 "%ju data, %ju dirent, %ju empty), %s",
337 (uintmax_t)bstats->total_blockref,
338 (uintmax_t)bstats->volume.total_inode,
339 (uintmax_t)bstats->volume.total_indirect,
340 (uintmax_t)bstats->volume.total_data,
341 (uintmax_t)bstats->volume.total_dirent,
342 (uintmax_t)bstats->total_empty,
343 sizetostr(bstats->total_bytes));
345 case HAMMER2_BREF_TYPE_FREEMAP:
346 snprintf(buf, siz, "%*s%ju blockref (%ju node, %ju leaf, "
349 (uintmax_t)bstats->total_blockref,
350 (uintmax_t)bstats->freemap.total_freemap_node,
351 (uintmax_t)bstats->freemap.total_freemap_leaf,
352 (uintmax_t)bstats->total_empty,
353 sizetostr(bstats->total_bytes));
370 verify_volume_header(const hammer2_volume_data_t *voldata)
372 hammer2_crc32_t crc0, crc, bcrc0, bcrc;
373 const char *p = (const char*)voldata;
375 if ((voldata->magic != HAMMER2_VOLUME_ID_HBO) &&
376 (voldata->magic != HAMMER2_VOLUME_ID_ABO)) {
377 tfprintf(stderr, 1, "Bad magic %jX\n", voldata->magic);
381 if (voldata->magic == HAMMER2_VOLUME_ID_ABO)
382 tfprintf(stderr, 1, "Reverse endian\n");
384 crc = voldata->icrc_sects[HAMMER2_VOL_ICRC_SECT0];
385 crc0 = hammer2_icrc32(p + HAMMER2_VOLUME_ICRC0_OFF,
386 HAMMER2_VOLUME_ICRC0_SIZE);
388 tfprintf(stderr, 1, "Bad HAMMER2_VOL_ICRC_SECT0 CRC\n");
392 bcrc = voldata->icrc_sects[HAMMER2_VOL_ICRC_SECT1];
393 bcrc0 = hammer2_icrc32(p + HAMMER2_VOLUME_ICRC1_OFF,
394 HAMMER2_VOLUME_ICRC1_SIZE);
396 tfprintf(stderr, 1, "Bad HAMMER2_VOL_ICRC_SECT1 CRC\n");
404 verify_blockref(int fd, const hammer2_volume_data_t *voldata,
405 const hammer2_blockref_t *bref, bool norecurse, blockref_stats_t *bstats)
407 hammer2_media_data_t media;
408 hammer2_blockref_t *bscan;
418 uint8_t digest[SHA256_DIGEST_LENGTH];
419 uint64_t digest64[SHA256_DIGEST_LENGTH/8];
422 bstats->total_blockref++;
424 switch (bref->type) {
425 case HAMMER2_BREF_TYPE_EMPTY:
426 bstats->total_empty++;
428 case HAMMER2_BREF_TYPE_INODE:
429 bstats->volume.total_inode++;
431 case HAMMER2_BREF_TYPE_INDIRECT:
432 bstats->volume.total_indirect++;
434 case HAMMER2_BREF_TYPE_DATA:
435 bstats->volume.total_data++;
437 case HAMMER2_BREF_TYPE_DIRENT:
438 bstats->volume.total_dirent++;
440 case HAMMER2_BREF_TYPE_FREEMAP_NODE:
441 bstats->freemap.total_freemap_node++;
443 case HAMMER2_BREF_TYPE_FREEMAP_LEAF:
444 bstats->freemap.total_freemap_leaf++;
446 case HAMMER2_BREF_TYPE_VOLUME:
447 bstats->total_blockref--;
449 case HAMMER2_BREF_TYPE_FREEMAP:
450 bstats->total_blockref--;
453 bstats->total_invalid++;
454 snprintf(msg, sizeof(msg),
455 "Invalid blockref type %d", bref->type);
456 add_blockref_entry(bstats, bref->data_off, msg);
461 bytes = (bref->data_off & HAMMER2_OFF_MASK_RADIX);
463 bytes = (size_t)1 << bytes;
464 if (bref->type != HAMMER2_BREF_TYPE_VOLUME &&
465 bref->type != HAMMER2_BREF_TYPE_FREEMAP)
466 bstats->total_bytes += bytes;
468 if ((bstats->total_blockref % 100) == 0)
469 print_blockref_stats(bstats, false);
472 hammer2_off_t io_off;
473 hammer2_off_t io_base;
477 io_off = bref->data_off & ~HAMMER2_OFF_MASK_RADIX;
478 io_base = io_off & ~(hammer2_off_t)(HAMMER2_MINIOSIZE - 1);
479 boff = io_off - io_base;
481 io_bytes = HAMMER2_MINIOSIZE;
482 while (io_bytes + boff < bytes)
485 if (io_bytes > sizeof(media)) {
486 snprintf(msg, sizeof(msg),
487 "Bad I/O bytes %ju", io_bytes);
488 add_blockref_entry(bstats, bref->data_off, msg);
491 lseek(fd, io_base, SEEK_SET);
492 if (read(fd, &media, io_bytes) != (ssize_t)io_bytes) {
493 add_blockref_entry(bstats, bref->data_off,
494 "Failed to read media");
498 memcpy(&media, (char *)&media + boff, bytes);
500 switch (HAMMER2_DEC_CHECK(bref->methods)) {
501 case HAMMER2_CHECK_ISCSI32:
502 cv = hammer2_icrc32(&media, bytes);
503 if (bref->check.iscsi32.value != cv) {
504 add_blockref_entry(bstats, bref->data_off,
505 "Bad HAMMER2_CHECK_ISCSI32");
509 case HAMMER2_CHECK_XXHASH64:
510 cv64 = XXH64(&media, bytes, XXH_HAMMER2_SEED);
511 if (bref->check.xxhash64.value != cv64) {
512 add_blockref_entry(bstats, bref->data_off,
513 "Bad HAMMER2_CHECK_XXHASH64");
517 case HAMMER2_CHECK_SHA192:
518 SHA256_Init(&hash_ctx);
519 SHA256_Update(&hash_ctx, &media, bytes);
520 SHA256_Final(u.digest, &hash_ctx);
521 u.digest64[2] ^= u.digest64[3];
522 if (memcmp(u.digest, bref->check.sha192.data,
523 sizeof(bref->check.sha192.data))) {
524 add_blockref_entry(bstats, bref->data_off,
525 "Bad HAMMER2_CHECK_SHA192");
529 case HAMMER2_CHECK_FREEMAP:
530 cv = hammer2_icrc32(&media, bytes);
531 if (bref->check.freemap.icrc32 != cv) {
532 add_blockref_entry(bstats, bref->data_off,
533 "Bad HAMMER2_CHECK_FREEMAP");
540 switch (bref->type) {
541 case HAMMER2_BREF_TYPE_INODE:
542 if (!(media.ipdata.meta.op_flags & HAMMER2_OPFLAG_DIRECTDATA)) {
543 bscan = &media.ipdata.u.blockset.blockref[0];
544 bcount = HAMMER2_SET_COUNT;
550 case HAMMER2_BREF_TYPE_INDIRECT:
551 bscan = &media.npdata[0];
552 bcount = bytes / sizeof(hammer2_blockref_t);
554 case HAMMER2_BREF_TYPE_FREEMAP_NODE:
555 bscan = &media.npdata[0];
556 bcount = bytes / sizeof(hammer2_blockref_t);
558 case HAMMER2_BREF_TYPE_VOLUME:
559 bscan = &media.voldata.sroot_blockset.blockref[0];
560 bcount = HAMMER2_SET_COUNT;
562 case HAMMER2_BREF_TYPE_FREEMAP:
563 bscan = &media.voldata.freemap_blockset.blockref[0];
564 bcount = HAMMER2_SET_COUNT;
575 * If failed, no recurse, but still verify its direct children.
576 * Beyond that is probably garbage.
578 for (i = 0; norecurse == 0 && i < bcount; ++i)
579 if (bscan[i].type != HAMMER2_BREF_TYPE_EMPTY)
580 if (verify_blockref(fd, voldata, &bscan[i], failed,
583 return failed ? -1 : 0;
587 test_hammer2(const char *devpath)
592 fd = open(devpath, O_RDONLY);
598 if (fstat(fd, &st) == -1) {
603 if (!S_ISCHR(st.st_mode)) {
604 fprintf(stderr, "%s is not a block device\n", devpath);
609 best_zone = find_best_zone(fd);
611 fprintf(stderr, "Failed to find best zone\n");
613 printf("volume header\n");
614 if (test_volume_header(fd) == -1) {
622 if (test_blockref(fd, HAMMER2_BREF_TYPE_FREEMAP) == -1) {
629 if (test_blockref(fd, HAMMER2_BREF_TYPE_VOLUME) == -1) {