lib/libstand/hammer1.c

   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 Simon Schubert <corecode@fs.ei.tum.de>
   6  * and Matthew Dillon <dillon@backplane.com>
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  *
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in
  16  *    the documentation and/or other materials provided with the
  17  *    distribution.
  18  * 3. Neither the name of The DragonFly Project nor the names of its
  19  *    contributors may be used to endorse or promote products derived
  20  *    from this software without specific, prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  23  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  24  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  25  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  26  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  27  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  28  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  29  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  30  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  31  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  32  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  33  * SUCH DAMAGE.
  34  */
  35
  36 /*
  37  * This file is being used by boot2 and libstand (loader).
  38  * Compile with -DTESTING to obtain a binary.
  39  */
  40
  41
  42 #if !defined(BOOT2) && !defined(TESTING)
  43 #define LIBSTAND        1
  44 #endif
  45
  46 #ifdef BOOT2
  47 #include "boot2.h"
  48 #else
  49 #include <sys/param.h>
  50 #include <stddef.h>
  51 #include <stdint.h>
  52 #endif
  53
  54 #ifdef TESTING
  55 #include <sys/fcntl.h>
  56 #include <sys/stat.h>
  57 #include <unistd.h>
  58 #include <err.h>
  59 #include <stdio.h>
  60 #include <stdlib.h>
  61 #include <string.h>
  62 #include <errno.h>
  63 #include <dirent.h>
  64 #endif
  65
  66 #ifdef LIBSTAND
  67 #include "stand.h"
  68 #endif
  69
  70 #include <vfs/hammer/hammer_disk.h>
  71
  72 #ifndef BOOT2
  73 struct blockentry {
  74         hammer_off_t    off;
  75         int             use;
  76         char            *data;
  77 };
  78
  79 #ifdef TESTING
  80 #define NUMCACHE        16
  81 #else
  82 #define NUMCACHE        6
  83 #endif
  84
  85 struct hfs {
  86 #ifdef TESTING
  87         int             fd;
  88 #else   // libstand
  89         struct open_file *f;
  90 #endif
  91         hammer_off_t    root;
  92         int64_t         buf_beg;
  93         int64_t         last_dir_ino;
  94         u_int8_t        last_dir_cap_flags;
  95         int             lru;
  96         struct blockentry cache[NUMCACHE];
  97 };
  98
  99 static void *
 100 hread(struct hfs *hfs, hammer_off_t off)
 101 {
 102         hammer_off_t boff = off & ~HAMMER_BUFMASK64;
 103
 104         boff &= HAMMER_OFF_LONG_MASK;
 105
 106         if (HAMMER_ZONE_DECODE(off) != HAMMER_ZONE_RAW_VOLUME_INDEX)
 107                 boff += hfs->buf_beg;
 108
 109         struct blockentry *be = NULL;
 110         for (int i = 0; i < NUMCACHE; i++) {
 111                 if (be == NULL || be->use > hfs->cache[i].use)
 112                         be = &hfs->cache[i];
 113                 if (hfs->cache[i].off == boff) {
 114                         be = &hfs->cache[i];
 115                         break;
 116                 }
 117         }
 118         if (be->off != boff) {
 119                 // Didn't find any match
 120                 be->off = boff;
 121 #ifdef TESTING
 122                 ssize_t res = pread(hfs->fd, be->data, HAMMER_BUFSIZE,
 123                                     boff & HAMMER_OFF_SHORT_MASK);
 124                 if (res != HAMMER_BUFSIZE)
 125                         err(1, "short read on off %llx", boff);
 126 #else   // libstand
 127                 size_t rlen;
 128                 int rv = hfs->f->f_dev->dv_strategy(hfs->f->f_devdata, F_READ,
 129                         boff >> DEV_BSHIFT, HAMMER_BUFSIZE,
 130                         be->data, &rlen);
 131                 if (rv || rlen != HAMMER_BUFSIZE)
 132                         return (NULL);
 133 #endif
 134         }
 135
 136         be->use = ++hfs->lru;
 137         return &be->data[off & HAMMER_BUFMASK];
 138 }
 139
 140 #else   /* BOOT2 */
 141
 142 struct hammer_dmadat {
 143         struct boot2_dmadat boot2;
 144         char            buf[HAMMER_BUFSIZE];
 145 };
 146
 147 #define fsdmadat        ((struct hammer_dmadat *)boot2_dmadat)
 148
 149 struct hfs {
 150         hammer_off_t    root;
 151         int64_t         last_dir_ino;
 152         u_int8_t        last_dir_cap_flags;
 153         int64_t         buf_beg;
 154 };
 155
 156 static void *
 157 hread(struct hfs *hfs, hammer_off_t off)
 158 {
 159         char *buf = fsdmadat->buf;
 160
 161         hammer_off_t boff = off & ~HAMMER_BUFMASK64;
 162         boff &= HAMMER_OFF_LONG_MASK;
 163         if (HAMMER_ZONE_DECODE(off) != HAMMER_ZONE_RAW_VOLUME_INDEX)
 164                 boff += hfs->buf_beg;
 165         boff &= HAMMER_OFF_SHORT_MASK;
 166         boff >>= DEV_BSHIFT;
 167         if (dskread(buf, boff, HAMMER_BUFSIZE >> DEV_BSHIFT))
 168                 return (NULL);
 169         return (&buf[off & HAMMER_BUFMASK]);
 170 }
 171
 172 static void
 173 bzero(void *buf, size_t size)
 174 {
 175         for (size_t i = 0; i < size; i++)
 176                 ((char *)buf)[i] = 0;
 177 }
 178
 179 static void
 180 bcopy(void *src, void *dst, size_t size)
 181 {
 182         memcpy(dst, src, size);
 183 }
 184
 185 static size_t
 186 strlen(const char *s)
 187 {
 188         size_t l = 0;
 189         for (; *s != 0; s++)
 190                 l++;
 191         return (l);
 192 }
 193
 194 static int
 195 memcmp(const void *a, const void *b, size_t len)
 196 {
 197         for (size_t p = 0; p < len; p++) {
 198                 int r = ((const char *)a)[p] - ((const char *)b)[p];
 199                 if (r != 0)
 200                         return (r);
 201         }
 202
 203         return (0);
 204 }
 205
 206 #endif
 207
 208 /*
 209  * (from hammer_btree.c)
 210  *
 211  * Compare two B-Tree elements, return -N, 0, or +N (e.g. similar to strcmp).
 212  *
 213  * Note that for this particular function a return value of -1, 0, or +1
 214  * can denote a match if create_tid is otherwise discounted.  A create_tid
 215  * of zero is considered to be 'infinity' in comparisons.
 216  *
 217  * See also hammer_rec_rb_compare() and hammer_rec_cmp() in hammer_object.c.
 218  */
 219 static int
 220 hammer_btree_cmp(hammer_base_elm_t key1, hammer_base_elm_t key2)
 221 {
 222         if (key1->localization < key2->localization)
 223                 return(-5);
 224         if (key1->localization > key2->localization)
 225                 return(5);
 226
 227         if (key1->obj_id < key2->obj_id)
 228                 return(-4);
 229         if (key1->obj_id > key2->obj_id)
 230                 return(4);
 231
 232         if (key1->rec_type < key2->rec_type)
 233                 return(-3);
 234         if (key1->rec_type > key2->rec_type)
 235                 return(3);
 236
 237         if (key1->key < key2->key)
 238                 return(-2);
 239         if (key1->key > key2->key)
 240                 return(2);
 241
 242         /*
 243          * A create_tid of zero indicates a record which is undeletable
 244          * and must be considered to have a value of positive infinity.
 245          */
 246         if (key1->create_tid == 0) {
 247                 if (key2->create_tid == 0)
 248                         return(0);
 249                 return(1);
 250         }
 251         if (key2->create_tid == 0)
 252                 return(-1);
 253         if (key1->create_tid < key2->create_tid)
 254                 return(-1);
 255         if (key1->create_tid > key2->create_tid)
 256                 return(1);
 257         return(0);
 258 }
 259
 260 /*
 261  * Heuristical search for the first element whos comparison is <= 1.  May
 262  * return an index whos compare result is > 1 but may only return an index
 263  * whos compare result is <= 1 if it is the first element with that result.
 264  */
 265 static int
 266 hammer_btree_search_node(hammer_base_elm_t elm, hammer_node_ondisk_t node)
 267 {
 268         int b;
 269         int s;
 270         int i;
 271         int r;
 272
 273         /*
 274          * Don't bother if the node does not have very many elements
 275          */
 276         b = 0;
 277         s = node->count;
 278         while (s - b > 4) {
 279                 i = b + (s - b) / 2;
 280                 r = hammer_btree_cmp(elm, &node->elms[i].leaf.base);
 281                 if (r <= 1) {
 282                         s = i;
 283                 } else {
 284                         b = i;
 285                 }
 286         }
 287         return(b);
 288 }
 289
 290 #if 0
 291 /*
 292  * (from hammer_subs.c)
 293  *
 294  * Return a namekey hash.   The 64 bit namekey hash consists of a 32 bit
 295  * crc in the MSB and 0 in the LSB.  The caller will use the low bits to
 296  * generate a unique key and will scan all entries with the same upper
 297  * 32 bits when issuing a lookup.
 298  *
 299  * We strip bit 63 in order to provide a positive key, this way a seek
 300  * offset of 0 will represent the base of the directory.
 301  *
 302  * This function can never return 0.  We use the MSB-0 space to synthesize
 303  * artificial directory entries such as "." and "..".
 304  */
 305 static int64_t
 306 hammer_directory_namekey(const void *name, int len)
 307 {
 308         int64_t key;
 309
 310         key = (int64_t)(crc32(name, len) & 0x7FFFFFFF) << 32;
 311         if (key == 0)
 312                 key |= 0x100000000LL;
 313         return(key);
 314 }
 315 #else
 316 static int64_t
 317 hammer_directory_namekey(const void *name __unused, int len __unused)
 318 {
 319         return (0);
 320 }
 321 #endif
 322
 323
 324 #ifndef BOOT2
 325 /*
 326  * Misc
 327  */
 328 static u_int32_t
 329 hammer_to_unix_xid(uuid_t *uuid)
 330 {
 331         return(*(u_int32_t *)&uuid->node[2]);
 332 }
 333
 334 static int
 335 hammer_get_dtype(u_int8_t obj_type)
 336 {
 337         switch(obj_type) {
 338         case HAMMER_OBJTYPE_DIRECTORY:
 339                 return(DT_DIR);
 340         case HAMMER_OBJTYPE_REGFILE:
 341                 return(DT_REG);
 342         case HAMMER_OBJTYPE_DBFILE:
 343                 return(DT_DBF);
 344         case HAMMER_OBJTYPE_FIFO:
 345                 return(DT_FIFO);
 346         case HAMMER_OBJTYPE_SOCKET:
 347                 return(DT_SOCK);
 348         case HAMMER_OBJTYPE_CDEV:
 349                 return(DT_CHR);
 350         case HAMMER_OBJTYPE_BDEV:
 351                 return(DT_BLK);
 352         case HAMMER_OBJTYPE_SOFTLINK:
 353                 return(DT_LNK);
 354         default:
 355                 return(DT_UNKNOWN);
 356         }
 357         /* not reached */
 358 }
 359
 360 static int
 361 hammer_get_mode(u_int8_t obj_type)
 362 {
 363         switch(obj_type) {
 364         case HAMMER_OBJTYPE_DIRECTORY:
 365                 return(S_IFDIR);
 366         case HAMMER_OBJTYPE_REGFILE:
 367                 return(S_IFREG);
 368         case HAMMER_OBJTYPE_DBFILE:
 369                 return(S_IFDB);
 370         case HAMMER_OBJTYPE_FIFO:
 371                 return(S_IFIFO);
 372         case HAMMER_OBJTYPE_SOCKET:
 373                 return(S_IFSOCK);
 374         case HAMMER_OBJTYPE_CDEV:
 375                 return(S_IFCHR);
 376         case HAMMER_OBJTYPE_BDEV:
 377                 return(S_IFBLK);
 378         case HAMMER_OBJTYPE_SOFTLINK:
 379                 return(S_IFLNK);
 380         default:
 381                 return(0);
 382         }
 383         /* not reached */
 384 }
 385
 386 #if DEBUG > 1
 387 static void
 388 hprintb(hammer_base_elm_t e)
 389 {
 390         printf("%d/", e->localization);
 391         if (e->obj_id >> 32 != 0)
 392                 printf("%lx%08lx",
 393                        (long)(e->obj_id >> 32),
 394                        (long)(e->obj_id & 0xffffffff));
 395         else
 396                 printf("%lx", (long)e->obj_id);
 397         printf("/%d/", e->rec_type);
 398         if (e->key >> 32 != 0)
 399                 printf("%lx%08lx",
 400                        (long)(e->key >> 32),
 401                        (long)(e->key & 0xffffffff));
 402         else
 403                 printf("%lx", (long)e->key);
 404 #ifdef TESTING
 405         printf("/%llx/%llx", e->create_tid, e->delete_tid);
 406 #endif
 407 }
 408 #endif /* DEBUG > 1 */
 409 #endif /* !BOOT2 */
 410
 411 static hammer_btree_leaf_elm_t
 412 hfind(struct hfs *hfs, hammer_base_elm_t key, hammer_base_elm_t end)
 413 {
 414 #if DEBUG > 1
 415         printf("searching for ");
 416         hprintb(key);
 417         printf(" end ");
 418         hprintb(end);
 419         printf("\n");
 420 #endif
 421
 422         int n;
 423         int r;
 424         struct hammer_base_elm search = *key;
 425         struct hammer_base_elm backtrack;
 426         hammer_off_t nodeoff = hfs->root;
 427         hammer_node_ondisk_t node;
 428         hammer_btree_elm_t e = NULL;
 429         int internal;
 430
 431 loop:
 432         node = hread(hfs, nodeoff);
 433         if (node == NULL)
 434                 return (NULL);
 435         internal = node->type == HAMMER_BTREE_TYPE_INTERNAL;
 436
 437 #if DEBUG > 3
 438         for (int i = 0; i < node->count; i++) {
 439                 printf("E: ");
 440                 hprintb(&node->elms[i].base);
 441                 printf("\n");
 442         }
 443         if (internal) {
 444                 printf("B: ");
 445                 hprintb(&node->elms[node->count].base);
 446                 printf("\n");
 447         }
 448 #endif
 449
 450         n = hammer_btree_search_node(&search, node);
 451
 452         // In internal nodes, we cover the right boundary as well.
 453         // If we hit it, we'll backtrack.
 454         for (; n < node->count + internal; n++) {
 455                 e = &node->elms[n];
 456                 r = hammer_btree_cmp(&search, &e->base);
 457
 458                 if (r < 0)
 459                         break;
 460         }
 461
 462         // unless we stopped right on the left side, we need to back off a bit
 463         if (n > 0)
 464                 e = &node->elms[--n];
 465
 466 #if DEBUG > 2
 467         printf("  found: ");
 468         hprintb(&e->base);
 469         printf("\n");
 470 #endif
 471
 472         if (internal) {
 473                 // If we hit the right boundary, backtrack to
 474                 // the next higher level.
 475                 if (n == node->count)
 476                         goto backtrack;
 477                 nodeoff = e->internal.subtree_offset;
 478                 backtrack = (e+1)->base;
 479                 goto loop;
 480         }
 481
 482         r = hammer_btree_cmp(key, &e->base);
 483         // If we're more off than the createtid, take the next elem
 484         if (r > 1) {
 485                 e++;
 486                 n++;
 487         }
 488
 489         // Skip deleted elements
 490         while (n < node->count && e->base.delete_tid != 0) {
 491                 e++;
 492                 n++;
 493         }
 494
 495         // In the unfortunate event when there is no next
 496         // element in this node, we repeat the search with
 497         // a key beyond the right boundary
 498         if (n == node->count) {
 499 backtrack:
 500                 search = backtrack;
 501                 nodeoff = hfs->root;
 502
 503 #if DEBUG > 2
 504                 printf("hit right boundary (%d), resetting search to ",
 505                        node->count);
 506                 hprintb(&search);
 507                 printf("\n");
 508 #endif
 509                 goto loop;
 510         }
 511
 512 #if DEBUG > 1
 513         printf("  result: ");
 514         hprintb(&e->base);
 515         printf("\n");
 516 #endif
 517
 518         if (end != NULL)
 519                 if (hammer_btree_cmp(end, &e->base) < -1)
 520                         goto fail;
 521
 522         return (&e->leaf);
 523
 524 fail:
 525 #if DEBUG > 1
 526         printf("  fail.\n");
 527 #endif
 528         return (NULL);
 529 }
 530
 531 /*
 532  * Returns the directory entry localization field based on the directory
 533  * inode's capabilities.
 534  */
 535 static u_int32_t
 536 hdirlocalization(struct hfs *hfs, ino_t ino)
 537 {
 538         struct hammer_base_elm key;
 539
 540         if (ino != hfs->last_dir_ino) {
 541                 bzero(&key, sizeof(key));
 542                 key.obj_id = ino;
 543                 key.localization = HAMMER_LOCALIZE_INODE;
 544                 key.rec_type = HAMMER_RECTYPE_INODE;
 545                 hammer_btree_leaf_elm_t e;
 546                 hammer_data_ondisk_t ed;
 547
 548                 e = hfind(hfs, &key, &key);
 549                 if (e) {
 550                         ed = hread(hfs, e->data_offset);
 551                         if (ed) {
 552                                 hfs->last_dir_ino = ino;
 553                                 hfs->last_dir_cap_flags = ed->inode.cap_flags;
 554                         } else {
 555                                 printf("hdirlocal: no inode data for %llx\n",
 556                                         (long long)ino);
 557                         }
 558                 } else {
 559                         printf("hdirlocal: no inode entry for %llx\n",
 560                                 (long long)ino);
 561                 }
 562         }
 563         if (hfs->last_dir_cap_flags & HAMMER_INODE_CAP_DIR_LOCAL_INO)
 564                 return(HAMMER_LOCALIZE_INODE);
 565         else
 566                 return(HAMMER_LOCALIZE_MISC);
 567 }
 568
 569 #ifndef BOOT2
 570 static int
 571 hreaddir(struct hfs *hfs, ino_t ino, int64_t *off, struct dirent *de)
 572 {
 573         struct hammer_base_elm key, end;
 574
 575 #if DEBUG > 2
 576         printf("%s(%llx, %lld)\n", __func__, (long long)ino, *off);
 577 #endif
 578
 579         bzero(&key, sizeof(key));
 580         key.obj_id = ino;
 581         key.localization = hdirlocalization(hfs, ino);
 582         key.rec_type = HAMMER_RECTYPE_DIRENTRY;
 583         key.key = *off;
 584
 585         end = key;
 586         end.key = HAMMER_MAX_KEY;
 587
 588         hammer_btree_leaf_elm_t e;
 589
 590         e = hfind(hfs, &key, &end);
 591         if (e == NULL) {
 592                 errno = ENOENT;
 593                 return (-1);
 594         }
 595
 596         *off = e->base.key + 1;         // remember next pos
 597
 598         de->d_namlen = e->data_len - HAMMER_ENTRY_NAME_OFF;
 599         de->d_type = hammer_get_dtype(e->base.obj_type);
 600         hammer_data_ondisk_t ed = hread(hfs, e->data_offset);
 601         if (ed == NULL)
 602                 return (-1);
 603         de->d_ino = ed->entry.obj_id;
 604         bcopy(ed->entry.name, de->d_name, de->d_namlen);
 605         de->d_name[de->d_namlen] = 0;
 606
 607         return (0);
 608 }
 609 #endif
 610
 611 static ino_t
 612 hresolve(struct hfs *hfs, ino_t dirino, const char *name)
 613 {
 614         struct hammer_base_elm key, end;
 615         size_t namel = strlen(name);
 616
 617 #if DEBUG > 2
 618         printf("%s(%llx, %s)\n", __func__, (long long)dirino, name);
 619 #endif
 620
 621         bzero(&key, sizeof(key));
 622         key.obj_id = dirino;
 623         key.localization = hdirlocalization(hfs, dirino);
 624         key.key = hammer_directory_namekey(name, namel);
 625         key.rec_type = HAMMER_RECTYPE_DIRENTRY;
 626         end = key;
 627         end.key = HAMMER_MAX_KEY;
 628
 629         hammer_btree_leaf_elm_t e;
 630         while ((e = hfind(hfs, &key, &end)) != NULL) {
 631                 key.key = e->base.key + 1;
 632
 633                 size_t elen = e->data_len - HAMMER_ENTRY_NAME_OFF;
 634                 hammer_data_ondisk_t ed = hread(hfs, e->data_offset);
 635                 if (ed == NULL)
 636                         return (-1);
 637 #ifdef BOOT2
 638                 if (ls) {
 639                         for (int i = 0; i < elen; i++)
 640                                 putchar(ed->entry.name[i]);
 641                         putchar(' ');
 642                         ls = 2;
 643                         continue;
 644                 }
 645 #endif
 646                 if (elen == namel && memcmp(ed->entry.name, name, MIN(elen, namel)) == 0)
 647                         return (ed->entry.obj_id);
 648         }
 649
 650 #if BOOT2
 651         if (ls == 2)
 652                 printf("\n");
 653 #endif
 654
 655         return -1;
 656 }
 657
 658 static ino_t
 659 hlookup(struct hfs *hfs, const char *path)
 660 {
 661 #if DEBUG > 2
 662         printf("%s(%s)\n", __func__, path);
 663 #endif
 664
 665 #ifdef BOOT2
 666         ls = 0;
 667 #endif
 668         ino_t ino = 1;
 669         do {
 670                 char name[MAXPATHLEN + 1];
 671                 while (*path == '/')
 672                         path++;
 673                 if (*path == 0)
 674                         break;
 675                 for (char *n = name; *path != 0 && *path != '/'; path++, n++) {
 676                         n[0] = *path;
 677                         n[1] = 0;
 678                 }
 679
 680 #ifdef BOOT2
 681                 // A single ? means "list"
 682                 if (name[0] == '?' && name[1] == 0)
 683                         ls = 1;
 684 #endif
 685
 686                 ino = hresolve(hfs, ino, name);
 687         } while (ino != (ino_t)-1 && *path != 0);
 688
 689         return (ino);
 690 }
 691
 692
 693 #ifndef BOOT2
 694 static int
 695 hstat(struct hfs *hfs, ino_t ino, struct stat* st)
 696 {
 697         struct hammer_base_elm key;
 698
 699 #if DEBUG > 2
 700         printf("%s(%llx)\n", __func__, (long long)ino);
 701 #endif
 702
 703         bzero(&key, sizeof(key));
 704         key.obj_id = ino;
 705         key.localization = HAMMER_LOCALIZE_INODE;
 706         key.rec_type = HAMMER_RECTYPE_INODE;
 707
 708         hammer_btree_leaf_elm_t e = hfind(hfs, &key, &key);
 709         if (e == NULL) {
 710 #ifndef BOOT2
 711                 errno = ENOENT;
 712 #endif
 713                 return -1;
 714         }
 715
 716         hammer_data_ondisk_t ed = hread(hfs, e->data_offset);
 717         if (ed == NULL)
 718                 return (-1);
 719
 720         st->st_mode = ed->inode.mode | hammer_get_mode(ed->inode.obj_type);
 721         st->st_uid = hammer_to_unix_xid(&ed->inode.uid);
 722         st->st_gid = hammer_to_unix_xid(&ed->inode.gid);
 723         st->st_size = ed->inode.size;
 724
 725         return (0);
 726 }
 727 #endif
 728
 729 static ssize_t
 730 hreadf(struct hfs *hfs, ino_t ino, int64_t off, int64_t len, char *buf)
 731 {
 732         int64_t startoff = off;
 733         struct hammer_base_elm key, end;
 734
 735         bzero(&key, sizeof(key));
 736         key.obj_id = ino;
 737         key.localization = HAMMER_LOCALIZE_MISC;
 738         key.rec_type = HAMMER_RECTYPE_DATA;
 739         end = key;
 740         end.key = HAMMER_MAX_KEY;
 741
 742         while (len > 0) {
 743                 key.key = off + 1;
 744                 hammer_btree_leaf_elm_t e = hfind(hfs, &key, &end);
 745                 int64_t dlen;
 746
 747                 if (e == NULL || off > e->base.key) {
 748                         bzero(buf, len);
 749                         off += len;
 750                         len = 0;
 751                         break;
 752                 }
 753
 754                 int64_t doff = e->base.key - e->data_len;
 755                 if (off < doff) {
 756                         // sparse file, beginning
 757                         dlen = doff - off;
 758                         dlen = MIN(dlen, len);
 759                         bzero(buf, dlen);
 760                 } else {
 761                         int64_t boff = off - doff;
 762                         hammer_off_t roff = e->data_offset;
 763
 764                         dlen = e->data_len;
 765                         dlen -= boff;
 766                         dlen = MIN(dlen, len);
 767
 768                         while (boff >= HAMMER_BUFSIZE) {
 769                                 boff -= HAMMER_BUFSIZE;
 770                                 roff += HAMMER_BUFSIZE;
 771                         }
 772
 773                         /*
 774                          * boff - relative offset in disk buffer (not aligned)
 775                          * roff - base offset of disk buffer     (not aligned)
 776                          * dlen - amount of data we think we can copy
 777                          *
 778                          * hread only reads 16K aligned buffers, check for
 779                          * a length overflow and truncate dlen appropriately.
 780                          */
 781                         if ((roff & ~HAMMER_BUFMASK64) != ((roff + boff + dlen - 1) & ~HAMMER_BUFMASK64))
 782                                 dlen = HAMMER_BUFSIZE - ((boff + roff) & HAMMER_BUFMASK);
 783                         char *data = hread(hfs, roff);
 784                         if (data == NULL)
 785                                 return (-1);
 786                         bcopy(data + boff, buf, dlen);
 787                 }
 788
 789                 buf += dlen;
 790                 off += dlen;
 791                 len -= dlen;
 792         }
 793
 794         return (off - startoff);
 795 }
 796
 797 #ifdef BOOT2
 798 struct hfs hfs;
 799
 800 static int
 801 boot2_hammer_init(void)
 802 {
 803         hammer_volume_ondisk_t volhead;
 804
 805         volhead = hread(&hfs, HAMMER_ZONE_ENCODE(1, 0));
 806         if (volhead == NULL)
 807                 return (-1);
 808         if (volhead->vol_signature != HAMMER_FSBUF_VOLUME)
 809                 return (-1);
 810         hfs.root = volhead->vol0_btree_root;
 811         hfs.buf_beg = volhead->vol_buf_beg;
 812         return (0);
 813 }
 814
 815 static boot2_ino_t
 816 boot2_hammer_lookup(const char *path)
 817 {
 818         ino_t ino = hlookup(&hfs, path);
 819
 820         if (ino == -1)
 821                 ino = 0;
 822
 823         fs_off = 0;
 824
 825         return (ino);
 826 }
 827
 828 static ssize_t
 829 boot2_hammer_read(boot2_ino_t ino, void *buf, size_t len)
 830 {
 831         ssize_t rlen = hreadf(&hfs, ino, fs_off, len, buf);
 832         if (rlen != -1)
 833                 fs_off += rlen;
 834         return (rlen);
 835 }
 836
 837 const struct boot2_fsapi boot2_hammer_api = {
 838         .fsinit = boot2_hammer_init,
 839         .fslookup = boot2_hammer_lookup,
 840         .fsread = boot2_hammer_read
 841 };
 842
 843 #endif
 844
 845 #ifndef BOOT2
 846 static int
 847 hinit(struct hfs *hfs)
 848 {
 849 #if DEBUG
 850         printf("hinit\n");
 851 #endif
 852         for (int i = 0; i < NUMCACHE; i++) {
 853                 hfs->cache[i].data = malloc(HAMMER_BUFSIZE);
 854                 hfs->cache[i].off = -1; // invalid
 855                 hfs->cache[i].use = 0;
 856
 857 #if DEBUG
 858                 if (hfs->cache[i].data == NULL)
 859                         printf("malloc failed\n");
 860 #endif
 861         }
 862         hfs->lru = 0;
 863         hfs->last_dir_ino = -1;
 864
 865         hammer_volume_ondisk_t volhead = hread(hfs, HAMMER_ZONE_ENCODE(1, 0));
 866
 867 #ifdef TESTING
 868         if (volhead) {
 869                 printf("signature: %svalid\n",
 870                        volhead->vol_signature != HAMMER_FSBUF_VOLUME ?
 871                                 "in" :
 872                                 "");
 873                 printf("name: %s\n", volhead->vol_name);
 874         }
 875 #endif
 876
 877         if (volhead == NULL || volhead->vol_signature != HAMMER_FSBUF_VOLUME) {
 878                 for (int i = 0; i < NUMCACHE; i++) {
 879                         free(hfs->cache[i].data);
 880                         hfs->cache[i].data = NULL;
 881                 }
 882                 errno = ENODEV;
 883                 return (-1);
 884         }
 885
 886         hfs->root = volhead->vol0_btree_root;
 887         hfs->buf_beg = volhead->vol_buf_beg;
 888
 889         return (0);
 890 }
 891
 892 static void
 893 hclose(struct hfs *hfs)
 894 {
 895 #if DEBUG
 896         printf("hclose\n");
 897 #endif
 898         for (int i = 0; i < NUMCACHE; i++) {
 899                 if (hfs->cache[i].data) {
 900                         free(hfs->cache[i].data);
 901                         hfs->cache[i].data = NULL;
 902                 }
 903         }
 904 }
 905 #endif
 906
 907 #ifdef LIBSTAND
 908 struct hfile {
 909         struct hfs      hfs;
 910         ino_t           ino;
 911         int64_t         fsize;
 912 };
 913
 914 static int
 915 hammer_open(const char *path, struct open_file *f)
 916 {
 917         struct hfile *hf = malloc(sizeof(*hf));
 918
 919         bzero(hf, sizeof(*hf));
 920         f->f_fsdata = hf;
 921         hf->hfs.f = f;
 922         f->f_offset = 0;
 923
 924         int rv = hinit(&hf->hfs);
 925         if (rv) {
 926                 f->f_fsdata = NULL;
 927                 free(hf);
 928                 return (rv);
 929         }
 930
 931 #if DEBUG
 932         printf("hammer_open %s %p\n", path, f);
 933 #endif
 934
 935         hf->ino = hlookup(&hf->hfs, path);
 936         if (hf->ino == -1)
 937                 goto fail;
 938
 939         struct stat st;
 940         if (hstat(&hf->hfs, hf->ino, &st) == -1)
 941                 goto fail;
 942         hf->fsize = st.st_size;
 943
 944 #if DEBUG
 945         printf("        %ld\n", (long)hf->fsize);
 946 #endif
 947
 948         return (0);
 949
 950 fail:
 951 #if DEBUG
 952         printf("hammer_open fail\n");
 953 #endif
 954         f->f_fsdata = NULL;
 955         hclose(&hf->hfs);
 956         free(hf);
 957         return (ENOENT);
 958 }
 959
 960 static int
 961 hammer_close(struct open_file *f)
 962 {
 963         struct hfile *hf = f->f_fsdata;
 964
 965         f->f_fsdata = NULL;
 966         if (hf) {
 967             hclose(&hf->hfs);
 968             free(hf);
 969         }
 970         return (0);
 971 }
 972
 973 static int
 974 hammer_read(struct open_file *f, void *buf, size_t len, size_t *resid)
 975 {
 976         struct hfile *hf = f->f_fsdata;
 977
 978 #if DEBUG
 979         printf("hammer_read %p %ld %ld\n", f, f->f_offset, len);
 980 #endif
 981
 982         if (f->f_offset >= hf->fsize)
 983                 return (EINVAL);
 984
 985         size_t maxlen = len;
 986         if (f->f_offset + len > hf->fsize)
 987                 maxlen = hf->fsize - f->f_offset;
 988
 989         ssize_t rlen = hreadf(&hf->hfs, hf->ino, f->f_offset, maxlen, buf);
 990         if (rlen == -1)
 991                 return (EINVAL);
 992
 993         f->f_offset += rlen;
 994
 995         *resid = len - rlen;
 996         return (0);
 997 }
 998
 999 static off_t
1000 hammer_seek(struct open_file *f, off_t offset, int whence)
1001 {
1002         struct hfile *hf = f->f_fsdata;
1003
1004         switch (whence) {
1005         case SEEK_SET:
1006                 f->f_offset = offset;
1007                 break;
1008         case SEEK_CUR:
1009                 f->f_offset += offset;
1010                 break;
1011         case SEEK_END:
1012                 f->f_offset = hf->fsize - offset;
1013                 break;
1014         default:
1015                 return (-1);
1016         }
1017         return (f->f_offset);
1018 }
1019
1020 static int
1021 hammer_stat(struct open_file *f, struct stat *st)
1022 {
1023         struct hfile *hf = f->f_fsdata;
1024
1025         return (hstat(&hf->hfs, hf->ino, st));
1026 }
1027
1028 static int
1029 hammer_readdir(struct open_file *f, struct dirent *d)
1030 {
1031         struct hfile *hf = f->f_fsdata;
1032
1033         int64_t off = f->f_offset;
1034         int rv = hreaddir(&hf->hfs, hf->ino, &off, d);
1035         f->f_offset = off;
1036         return (rv);
1037 }
1038
1039 // libstand
1040 struct fs_ops hammer_fsops = {
1041         "hammer",
1042         hammer_open,
1043         hammer_close,
1044         hammer_read,
1045         null_write,
1046         hammer_seek,
1047         hammer_stat,
1048         hammer_readdir
1049 };
1050 #endif  // LIBSTAND
1051
1052 #ifdef TESTING
1053 int
1054 main(int argc, char **argv)
1055 {
1056         if (argc < 2) {
1057                 fprintf(stderr, "usage: hammerread <dev>\n");
1058                 return (1);
1059         }
1060
1061         struct hfs hfs;
1062         hfs.fd = open(argv[1], O_RDONLY);
1063         if (hfs.fd == -1)
1064                 err(1, "unable to open %s", argv[1]);
1065
1066         if (hinit(&hfs) == -1)
1067                 err(1, "invalid hammerfs");
1068
1069         for (int i = 2; i < argc; i++) {
1070                 ino_t ino = hlookup(&hfs, argv[i]);
1071                 if (ino == (ino_t)-1) {
1072                         warn("hlookup %s", argv[i]);
1073                         continue;
1074                 }
1075
1076                 struct stat st;
1077                 if (hstat(&hfs, ino, &st)) {
1078                         warn("hstat %s", argv[i]);
1079                         continue;
1080                 }
1081
1082                 printf("%s %d/%d %o %lld\n",
1083                        argv[i],
1084                        st.st_uid, st.st_gid,
1085                        st.st_mode, st.st_size);
1086
1087                 if (S_ISDIR(st.st_mode)) {
1088                         int64_t off = 0;
1089                         struct dirent de;
1090                         while (hreaddir(&hfs, ino, &off, &de) == 0) {
1091                                 printf("%s %d %llx\n",
1092                                        de.d_name, de.d_type, de.d_ino);
1093                         }
1094                 } else if (S_ISREG(st.st_mode)) {
1095                         char *buf = malloc(100000);
1096                         int64_t off = 0;
1097                         while (off < st.st_size) {
1098                                 int64_t len = MIN(100000, st.st_size - off);
1099                                 int64_t rl = hreadf(&hfs, ino, off, len, buf);
1100                                 fwrite(buf, rl, 1, stdout);
1101                                 off += rl;
1102                         }
1103                         free(buf);
1104                 }
1105         }
1106
1107         return 0;
1108 }
1109 #endif