2 * Copyright (c) 2008 The DragonFly Project. All rights reserved.
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>
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
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
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.
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
37 * This file is being used by boot2 and libstand (loader).
38 * Compile with -DTESTING to obtain a binary.
42 #if !defined(BOOT2) && !defined(TESTING)
49 #include <sys/param.h>
55 #include <sys/fcntl.h>
70 #include <vfs/hammer/hammer_disk.h>
94 u_int8_t last_dir_cap_flags;
96 struct blockentry cache[NUMCACHE];
100 hread(struct hfs *hfs, hammer_off_t off)
102 hammer_off_t boff = off & ~HAMMER_BUFMASK64;
104 boff &= HAMMER_OFF_LONG_MASK;
106 if (HAMMER_ZONE_DECODE(off) != HAMMER_ZONE_RAW_VOLUME_INDEX)
107 boff += hfs->buf_beg;
109 struct blockentry *be = NULL;
110 for (int i = 0; i < NUMCACHE; i++) {
111 if (be == NULL || be->use > hfs->cache[i].use)
113 if (hfs->cache[i].off == boff) {
118 if (be->off != boff) {
119 // Didn't find any match
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);
128 int rv = hfs->f->f_dev->dv_strategy(hfs->f->f_devdata, F_READ,
129 boff >> DEV_BSHIFT, HAMMER_BUFSIZE,
131 if (rv || rlen != HAMMER_BUFSIZE)
136 be->use = ++hfs->lru;
137 return &be->data[off & HAMMER_BUFMASK];
142 struct hammer_dmadat {
143 struct boot2_dmadat boot2;
144 char buf[HAMMER_BUFSIZE];
147 #define fsdmadat ((struct hammer_dmadat *)boot2_dmadat)
151 int64_t last_dir_ino;
152 u_int8_t last_dir_cap_flags;
157 hread(struct hfs *hfs, hammer_off_t off)
159 char *buf = fsdmadat->buf;
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;
167 if (dskread(buf, boff, HAMMER_BUFSIZE >> DEV_BSHIFT))
169 return (&buf[off & HAMMER_BUFMASK]);
173 bzero(void *buf, size_t size)
175 for (size_t i = 0; i < size; i++)
176 ((char *)buf)[i] = 0;
180 bcopy(void *src, void *dst, size_t size)
182 memcpy(dst, src, size);
186 strlen(const char *s)
195 memcmp(const void *a, const void *b, size_t len)
197 for (size_t p = 0; p < len; p++) {
198 int r = ((const char *)a)[p] - ((const char *)b)[p];
209 * (from hammer_btree.c)
211 * Compare two B-Tree elements, return -N, 0, or +N (e.g. similar to strcmp).
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.
217 * See also hammer_rec_rb_compare() and hammer_rec_cmp() in hammer_object.c.
220 hammer_btree_cmp(hammer_base_elm_t key1, hammer_base_elm_t key2)
222 if (key1->localization < key2->localization)
224 if (key1->localization > key2->localization)
227 if (key1->obj_id < key2->obj_id)
229 if (key1->obj_id > key2->obj_id)
232 if (key1->rec_type < key2->rec_type)
234 if (key1->rec_type > key2->rec_type)
237 if (key1->key < key2->key)
239 if (key1->key > key2->key)
243 * A create_tid of zero indicates a record which is undeletable
244 * and must be considered to have a value of positive infinity.
246 if (key1->create_tid == 0) {
247 if (key2->create_tid == 0)
251 if (key2->create_tid == 0)
253 if (key1->create_tid < key2->create_tid)
255 if (key1->create_tid > key2->create_tid)
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.
266 hammer_btree_search_node(hammer_base_elm_t elm, hammer_node_ondisk_t node)
274 * Don't bother if the node does not have very many elements
280 r = hammer_btree_cmp(elm, &node->elms[i].leaf.base);
292 * (from hammer_subs.c)
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.
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.
302 * This function can never return 0. We use the MSB-0 space to synthesize
303 * artificial directory entries such as "." and "..".
306 hammer_directory_namekey(const void *name, int len)
310 key = (int64_t)(crc32(name, len) & 0x7FFFFFFF) << 32;
312 key |= 0x100000000LL;
317 hammer_directory_namekey(const void *name __unused, int len __unused)
329 hammer_to_unix_xid(uuid_t *uuid)
331 return(*(u_int32_t *)&uuid->node[2]);
335 hammer_get_dtype(u_int8_t obj_type)
338 case HAMMER_OBJTYPE_DIRECTORY:
340 case HAMMER_OBJTYPE_REGFILE:
342 case HAMMER_OBJTYPE_DBFILE:
344 case HAMMER_OBJTYPE_FIFO:
346 case HAMMER_OBJTYPE_SOCKET:
348 case HAMMER_OBJTYPE_CDEV:
350 case HAMMER_OBJTYPE_BDEV:
352 case HAMMER_OBJTYPE_SOFTLINK:
361 hammer_get_mode(u_int8_t obj_type)
364 case HAMMER_OBJTYPE_DIRECTORY:
366 case HAMMER_OBJTYPE_REGFILE:
368 case HAMMER_OBJTYPE_DBFILE:
370 case HAMMER_OBJTYPE_FIFO:
372 case HAMMER_OBJTYPE_SOCKET:
374 case HAMMER_OBJTYPE_CDEV:
376 case HAMMER_OBJTYPE_BDEV:
378 case HAMMER_OBJTYPE_SOFTLINK:
388 hprintb(hammer_base_elm_t e)
390 printf("%d/", e->localization);
391 if (e->obj_id >> 32 != 0)
393 (long)(e->obj_id >> 32),
394 (long)(e->obj_id & 0xffffffff));
396 printf("%lx", (long)e->obj_id);
397 printf("/%d/", e->rec_type);
398 if (e->key >> 32 != 0)
400 (long)(e->key >> 32),
401 (long)(e->key & 0xffffffff));
403 printf("%lx", (long)e->key);
405 printf("/%llx/%llx", e->create_tid, e->delete_tid);
408 #endif /* DEBUG > 1 */
411 static hammer_btree_leaf_elm_t
412 hfind(struct hfs *hfs, hammer_base_elm_t key, hammer_base_elm_t end)
415 printf("searching for ");
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;
432 node = hread(hfs, nodeoff);
435 internal = node->type == HAMMER_BTREE_TYPE_INTERNAL;
438 for (int i = 0; i < node->count; i++) {
440 hprintb(&node->elms[i].base);
445 hprintb(&node->elms[node->count].base);
450 n = hammer_btree_search_node(&search, node);
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++) {
456 r = hammer_btree_cmp(&search, &e->base);
462 // unless we stopped right on the left side, we need to back off a bit
464 e = &node->elms[--n];
473 // If we hit the right boundary, backtrack to
474 // the next higher level.
475 if (n == node->count)
477 nodeoff = e->internal.subtree_offset;
478 backtrack = (e+1)->base;
482 r = hammer_btree_cmp(key, &e->base);
483 // If we're more off than the createtid, take the next elem
489 // Skip deleted elements
490 while (n < node->count && e->base.delete_tid != 0) {
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) {
504 printf("hit right boundary (%d), resetting search to ",
519 if (hammer_btree_cmp(end, &e->base) < -1)
532 * Returns the directory entry localization field based on the directory
533 * inode's capabilities.
536 hdirlocalization(struct hfs *hfs, ino_t ino)
538 struct hammer_base_elm key;
540 if (ino != hfs->last_dir_ino) {
541 bzero(&key, sizeof(key));
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;
548 e = hfind(hfs, &key, &key);
550 ed = hread(hfs, e->data_offset);
552 hfs->last_dir_ino = ino;
553 hfs->last_dir_cap_flags = ed->inode.cap_flags;
555 printf("hdirlocal: no inode data for %llx\n",
559 printf("hdirlocal: no inode entry for %llx\n",
563 if (hfs->last_dir_cap_flags & HAMMER_INODE_CAP_DIR_LOCAL_INO)
564 return(HAMMER_LOCALIZE_INODE);
566 return(HAMMER_LOCALIZE_MISC);
571 hreaddir(struct hfs *hfs, ino_t ino, int64_t *off, struct dirent *de)
573 struct hammer_base_elm key, end;
576 printf("%s(%llx, %lld)\n", __func__, (long long)ino, *off);
579 bzero(&key, sizeof(key));
581 key.localization = hdirlocalization(hfs, ino);
582 key.rec_type = HAMMER_RECTYPE_DIRENTRY;
586 end.key = HAMMER_MAX_KEY;
588 hammer_btree_leaf_elm_t e;
590 e = hfind(hfs, &key, &end);
596 *off = e->base.key + 1; // remember next pos
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);
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;
612 hresolve(struct hfs *hfs, ino_t dirino, const char *name)
614 struct hammer_base_elm key, end;
615 size_t namel = strlen(name);
618 printf("%s(%llx, %s)\n", __func__, (long long)dirino, name);
621 bzero(&key, sizeof(key));
623 key.localization = hdirlocalization(hfs, dirino);
624 key.key = hammer_directory_namekey(name, namel);
625 key.rec_type = HAMMER_RECTYPE_DIRENTRY;
627 end.key = HAMMER_MAX_KEY;
629 hammer_btree_leaf_elm_t e;
630 while ((e = hfind(hfs, &key, &end)) != NULL) {
631 key.key = e->base.key + 1;
633 size_t elen = e->data_len - HAMMER_ENTRY_NAME_OFF;
634 hammer_data_ondisk_t ed = hread(hfs, e->data_offset);
639 for (int i = 0; i < elen; i++)
640 putchar(ed->entry.name[i]);
646 if (elen == namel && memcmp(ed->entry.name, name, MIN(elen, namel)) == 0)
647 return (ed->entry.obj_id);
659 hlookup(struct hfs *hfs, const char *path)
662 printf("%s(%s)\n", __func__, path);
670 char name[MAXPATHLEN + 1];
675 for (char *n = name; *path != 0 && *path != '/'; path++, n++) {
681 // A single ? means "list"
682 if (name[0] == '?' && name[1] == 0)
686 ino = hresolve(hfs, ino, name);
687 } while (ino != (ino_t)-1 && *path != 0);
695 hstat(struct hfs *hfs, ino_t ino, struct stat* st)
697 struct hammer_base_elm key;
700 printf("%s(%llx)\n", __func__, (long long)ino);
703 bzero(&key, sizeof(key));
705 key.localization = HAMMER_LOCALIZE_INODE;
706 key.rec_type = HAMMER_RECTYPE_INODE;
708 hammer_btree_leaf_elm_t e = hfind(hfs, &key, &key);
716 hammer_data_ondisk_t ed = hread(hfs, e->data_offset);
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;
730 hreadf(struct hfs *hfs, ino_t ino, int64_t off, int64_t len, char *buf)
732 int64_t startoff = off;
733 struct hammer_base_elm key, end;
735 bzero(&key, sizeof(key));
737 key.localization = HAMMER_LOCALIZE_MISC;
738 key.rec_type = HAMMER_RECTYPE_DATA;
740 end.key = HAMMER_MAX_KEY;
744 hammer_btree_leaf_elm_t e = hfind(hfs, &key, &end);
747 if (e == NULL || off > e->base.key) {
754 int64_t doff = e->base.key - e->data_len;
756 // sparse file, beginning
758 dlen = MIN(dlen, len);
761 int64_t boff = off - doff;
762 hammer_off_t roff = e->data_offset;
766 dlen = MIN(dlen, len);
768 while (boff >= HAMMER_BUFSIZE) {
769 boff -= HAMMER_BUFSIZE;
770 roff += HAMMER_BUFSIZE;
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
778 * hread only reads 16K aligned buffers, check for
779 * a length overflow and truncate dlen appropriately.
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);
786 bcopy(data + boff, buf, dlen);
794 return (off - startoff);
801 boot2_hammer_init(void)
803 hammer_volume_ondisk_t volhead;
805 volhead = hread(&hfs, HAMMER_ZONE_ENCODE(1, 0));
808 if (volhead->vol_signature != HAMMER_FSBUF_VOLUME)
810 hfs.root = volhead->vol0_btree_root;
811 hfs.buf_beg = volhead->vol_buf_beg;
816 boot2_hammer_lookup(const char *path)
818 ino_t ino = hlookup(&hfs, path);
829 boot2_hammer_read(boot2_ino_t ino, void *buf, size_t len)
831 ssize_t rlen = hreadf(&hfs, ino, fs_off, len, buf);
837 const struct boot2_fsapi boot2_hammer_api = {
838 .fsinit = boot2_hammer_init,
839 .fslookup = boot2_hammer_lookup,
840 .fsread = boot2_hammer_read
847 hinit(struct hfs *hfs)
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;
858 if (hfs->cache[i].data == NULL)
859 printf("malloc failed\n");
863 hfs->last_dir_ino = -1;
865 hammer_volume_ondisk_t volhead = hread(hfs, HAMMER_ZONE_ENCODE(1, 0));
869 printf("signature: %svalid\n",
870 volhead->vol_signature != HAMMER_FSBUF_VOLUME ?
873 printf("name: %s\n", volhead->vol_name);
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;
886 hfs->root = volhead->vol0_btree_root;
887 hfs->buf_beg = volhead->vol_buf_beg;
893 hclose(struct hfs *hfs)
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;
915 hammer_open(const char *path, struct open_file *f)
917 struct hfile *hf = malloc(sizeof(*hf));
919 bzero(hf, sizeof(*hf));
924 int rv = hinit(&hf->hfs);
932 printf("hammer_open %s %p %ld\n", path, f);
935 hf->ino = hlookup(&hf->hfs, path);
940 if (hstat(&hf->hfs, hf->ino, &st) == -1)
942 hf->fsize = st.st_size;
945 printf(" %ld\n", (long)hf->fsize);
952 printf("hammer_open fail\n");
961 hammer_close(struct open_file *f)
963 struct hfile *hf = f->f_fsdata;
974 hammer_read(struct open_file *f, void *buf, size_t len, size_t *resid)
976 struct hfile *hf = f->f_fsdata;
979 printf("hammer_read %p %ld %ld\n", f, f->f_offset, len);
982 if (f->f_offset >= hf->fsize)
986 if (f->f_offset + len > hf->fsize)
987 maxlen = hf->fsize - f->f_offset;
989 ssize_t rlen = hreadf(&hf->hfs, hf->ino, f->f_offset, maxlen, buf);
1000 hammer_seek(struct open_file *f, off_t offset, int whence)
1002 struct hfile *hf = f->f_fsdata;
1006 f->f_offset = offset;
1009 f->f_offset += offset;
1012 f->f_offset = hf->fsize - offset;
1017 return (f->f_offset);
1021 hammer_stat(struct open_file *f, struct stat *st)
1023 struct hfile *hf = f->f_fsdata;
1025 return (hstat(&hf->hfs, hf->ino, st));
1029 hammer_readdir(struct open_file *f, struct dirent *d)
1031 struct hfile *hf = f->f_fsdata;
1033 int64_t off = f->f_offset;
1034 int rv = hreaddir(&hf->hfs, hf->ino, &off, d);
1040 struct fs_ops hammer_fsops = {
1054 main(int argc, char **argv)
1057 fprintf(stderr, "usage: hammerread <dev>\n");
1062 hfs.fd = open(argv[1], O_RDONLY);
1064 err(1, "unable to open %s", argv[1]);
1066 if (hinit(&hfs) == -1)
1067 err(1, "invalid hammerfs");
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]);
1077 if (hstat(&hfs, ino, &st)) {
1078 warn("hstat %s", argv[i]);
1082 printf("%s %d/%d %o %lld\n",
1084 st.st_uid, st.st_gid,
1085 st.st_mode, st.st_size);
1087 if (S_ISDIR(st.st_mode)) {
1090 while (hreaddir(&hfs, ino, &off, &de) == 0) {
1091 printf("%s %d %llx\n",
1092 de.d_name, de.d_type, de.d_ino);
1094 } else if (S_ISREG(st.st_mode)) {
1095 char *buf = malloc(100000);
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);