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)
53 #include <sys/param.h>
59 #include <sys/fcntl.h>
74 #include <vfs/hammer/hammer_disk.h>
98 u_int8_t last_dir_cap_flags
;
100 struct blockentry cache
[NUMCACHE
];
104 hread(struct hfs
*hfs
, hammer_off_t off
)
106 hammer_off_t boff
= off
& ~HAMMER_BUFMASK64
;
108 boff
&= HAMMER_OFF_LONG_MASK
;
110 if (HAMMER_ZONE_DECODE(off
) != HAMMER_ZONE_RAW_VOLUME_INDEX
)
111 boff
+= hfs
->buf_beg
;
113 struct blockentry
*be
= NULL
;
114 for (int i
= 0; i
< NUMCACHE
; i
++) {
115 if (be
== NULL
|| be
->use
> hfs
->cache
[i
].use
)
117 if (hfs
->cache
[i
].off
== boff
) {
122 if (be
->off
!= boff
) {
123 // Didn't find any match
126 ssize_t res
= pread(hfs
->fd
, be
->data
, HAMMER_BUFSIZE
,
127 boff
& HAMMER_OFF_SHORT_MASK
);
128 if (res
!= HAMMER_BUFSIZE
)
129 err(1, "short read on off %llx", boff
);
132 int rv
= hfs
->f
->f_dev
->dv_strategy(hfs
->f
->f_devdata
, F_READ
,
133 boff
>> DEV_BSHIFT
, HAMMER_BUFSIZE
,
135 if (rv
|| rlen
!= HAMMER_BUFSIZE
)
140 be
->use
= ++hfs
->lru
;
141 return &be
->data
[off
& HAMMER_BUFMASK
];
146 struct hammer_dmadat
{
147 struct boot2_dmadat boot2
;
148 char buf
[HAMMER_BUFSIZE
];
151 #define fsdmadat ((struct hammer_dmadat *)boot2_dmadat)
155 int64_t last_dir_ino
;
156 u_int8_t last_dir_cap_flags
;
161 hread(struct hfs
*hfs
, hammer_off_t off
)
163 char *buf
= fsdmadat
->buf
;
165 hammer_off_t boff
= off
& ~HAMMER_BUFMASK64
;
166 boff
&= HAMMER_OFF_LONG_MASK
;
167 if (HAMMER_ZONE_DECODE(off
) != HAMMER_ZONE_RAW_VOLUME_INDEX
)
168 boff
+= hfs
->buf_beg
;
169 boff
&= HAMMER_OFF_SHORT_MASK
;
171 if (dskread(buf
, boff
, HAMMER_BUFSIZE
>> DEV_BSHIFT
))
173 return (&buf
[off
& HAMMER_BUFMASK
]);
177 bzero(void *buf
, size_t size
)
179 for (size_t i
= 0; i
< size
; i
++)
180 ((char *)buf
)[i
] = 0;
184 bcopy(void *src
, void *dst
, size_t size
)
186 memcpy(dst
, src
, size
);
190 strlen(const char *s
)
199 memcmp(const void *a
, const void *b
, size_t len
)
201 for (size_t p
= 0; p
< len
; p
++) {
202 int r
= ((const char *)a
)[p
] - ((const char *)b
)[p
];
213 * (from hammer_btree.c)
215 * Compare two B-Tree elements, return -N, 0, or +N (e.g. similar to strcmp).
217 * Note that for this particular function a return value of -1, 0, or +1
218 * can denote a match if create_tid is otherwise discounted. A create_tid
219 * of zero is considered to be 'infinity' in comparisons.
221 * See also hammer_rec_rb_compare() and hammer_rec_cmp() in hammer_object.c.
224 hammer_btree_cmp(hammer_base_elm_t key1
, hammer_base_elm_t key2
)
226 if (key1
->localization
< key2
->localization
)
228 if (key1
->localization
> key2
->localization
)
231 if (key1
->obj_id
< key2
->obj_id
)
233 if (key1
->obj_id
> key2
->obj_id
)
236 if (key1
->rec_type
< key2
->rec_type
)
238 if (key1
->rec_type
> key2
->rec_type
)
241 if (key1
->key
< key2
->key
)
243 if (key1
->key
> key2
->key
)
247 * A create_tid of zero indicates a record which is undeletable
248 * and must be considered to have a value of positive infinity.
250 if (key1
->create_tid
== 0) {
251 if (key2
->create_tid
== 0)
255 if (key2
->create_tid
== 0)
257 if (key1
->create_tid
< key2
->create_tid
)
259 if (key1
->create_tid
> key2
->create_tid
)
265 * Heuristical search for the first element whos comparison is <= 1. May
266 * return an index whos compare result is > 1 but may only return an index
267 * whos compare result is <= 1 if it is the first element with that result.
270 hammer_btree_search_node(hammer_base_elm_t elm
, hammer_node_ondisk_t node
)
278 * Don't bother if the node does not have very many elements
284 r
= hammer_btree_cmp(elm
, &node
->elms
[i
].leaf
.base
);
296 * (from hammer_subs.c)
298 * Return a namekey hash. The 64 bit namekey hash consists of a 32 bit
299 * crc in the MSB and 0 in the LSB. The caller will use the low bits to
300 * generate a unique key and will scan all entries with the same upper
301 * 32 bits when issuing a lookup.
303 * We strip bit 63 in order to provide a positive key, this way a seek
304 * offset of 0 will represent the base of the directory.
306 * This function can never return 0. We use the MSB-0 space to synthesize
307 * artificial directory entries such as "." and "..".
310 hammer_directory_namekey(const void *name
, int len
)
314 key
= (int64_t)(crc32(name
, len
) & 0x7FFFFFFF) << 32;
316 key
|= 0x100000000LL
;
321 hammer_directory_namekey(const void *name __unused
, int len __unused
)
333 hammer_to_unix_xid(hammer_uuid_t
*uuid
)
335 return(*(u_int32_t
*)&uuid
->node
[2]);
339 hammer_get_dtype(u_int8_t obj_type
)
342 case HAMMER_OBJTYPE_DIRECTORY
:
344 case HAMMER_OBJTYPE_REGFILE
:
346 case HAMMER_OBJTYPE_DBFILE
:
348 case HAMMER_OBJTYPE_FIFO
:
350 case HAMMER_OBJTYPE_SOCKET
:
352 case HAMMER_OBJTYPE_CDEV
:
354 case HAMMER_OBJTYPE_BDEV
:
356 case HAMMER_OBJTYPE_SOFTLINK
:
365 hammer_get_mode(u_int8_t obj_type
)
368 case HAMMER_OBJTYPE_DIRECTORY
:
370 case HAMMER_OBJTYPE_REGFILE
:
372 case HAMMER_OBJTYPE_DBFILE
:
374 case HAMMER_OBJTYPE_FIFO
:
376 case HAMMER_OBJTYPE_SOCKET
:
378 case HAMMER_OBJTYPE_CDEV
:
380 case HAMMER_OBJTYPE_BDEV
:
382 case HAMMER_OBJTYPE_SOFTLINK
:
392 hprintb(hammer_base_elm_t e
)
394 printf("%d/", e
->localization
);
395 if (e
->obj_id
>> 32 != 0)
397 (long)(e
->obj_id
>> 32),
398 (long)(e
->obj_id
& 0xffffffff));
400 printf("%lx", (long)e
->obj_id
);
401 printf("/%d/", e
->rec_type
);
402 if (e
->key
>> 32 != 0)
404 (long)(e
->key
>> 32),
405 (long)(e
->key
& 0xffffffff));
407 printf("%lx", (long)e
->key
);
409 printf("/%llx/%llx", e
->create_tid
, e
->delete_tid
);
412 #endif /* DEBUG > 1 */
415 static hammer_btree_leaf_elm_t
416 hfind(struct hfs
*hfs
, hammer_base_elm_t key
, hammer_base_elm_t end
)
419 printf("searching for ");
428 struct hammer_base_elm search
= *key
;
429 struct hammer_base_elm backtrack
;
430 hammer_off_t nodeoff
= hfs
->root
;
431 hammer_node_ondisk_t node
;
432 hammer_btree_elm_t e
= NULL
;
436 node
= hread(hfs
, nodeoff
);
439 internal
= node
->type
== HAMMER_BTREE_TYPE_INTERNAL
;
442 for (int i
= 0; i
< node
->count
; i
++) {
444 hprintb(&node
->elms
[i
].base
);
449 hprintb(&node
->elms
[node
->count
].base
);
454 n
= hammer_btree_search_node(&search
, node
);
456 // In internal nodes, we cover the right boundary as well.
457 // If we hit it, we'll backtrack.
458 for (; n
< node
->count
+ internal
; n
++) {
460 r
= hammer_btree_cmp(&search
, &e
->base
);
466 // unless we stopped right on the left side, we need to back off a bit
468 e
= &node
->elms
[--n
];
477 // If we hit the right boundary, backtrack to
478 // the next higher level.
479 if (n
== node
->count
)
481 nodeoff
= e
->internal
.subtree_offset
;
482 backtrack
= (e
+1)->base
;
486 r
= hammer_btree_cmp(key
, &e
->base
);
487 // If we're more off than the createtid, take the next elem
493 // Skip deleted elements
494 while (n
< node
->count
&& e
->base
.delete_tid
!= 0) {
499 // In the unfortunate event when there is no next
500 // element in this node, we repeat the search with
501 // a key beyond the right boundary
502 if (n
== node
->count
) {
508 printf("hit right boundary (%d), resetting search to ",
523 if (hammer_btree_cmp(end
, &e
->base
) < -1)
536 * Returns the directory entry localization field based on the directory
537 * inode's capabilities.
540 hdirlocalization(struct hfs
*hfs
, ino_t ino
)
542 struct hammer_base_elm key
;
544 if (ino
!= hfs
->last_dir_ino
) {
545 bzero(&key
, sizeof(key
));
547 key
.localization
= HAMMER_LOCALIZE_INODE
;
548 key
.rec_type
= HAMMER_RECTYPE_INODE
;
549 hammer_btree_leaf_elm_t e
;
550 hammer_data_ondisk_t ed
;
552 e
= hfind(hfs
, &key
, &key
);
554 ed
= hread(hfs
, e
->data_offset
);
556 hfs
->last_dir_ino
= ino
;
557 hfs
->last_dir_cap_flags
= ed
->inode
.cap_flags
;
559 printf("hdirlocal: no inode data for %llx\n",
563 printf("hdirlocal: no inode entry for %llx\n",
567 if (hfs
->last_dir_cap_flags
& HAMMER_INODE_CAP_DIR_LOCAL_INO
)
568 return(HAMMER_LOCALIZE_INODE
);
570 return(HAMMER_LOCALIZE_MISC
);
575 hreaddir(struct hfs
*hfs
, ino_t ino
, int64_t *off
, struct dirent
*de
)
577 struct hammer_base_elm key
, end
;
580 printf("%s(%llx, %lld)\n", __func__
, (long long)ino
, *off
);
583 bzero(&key
, sizeof(key
));
585 key
.localization
= hdirlocalization(hfs
, ino
);
586 key
.rec_type
= HAMMER_RECTYPE_DIRENTRY
;
590 end
.key
= HAMMER_MAX_KEY
;
592 hammer_btree_leaf_elm_t e
;
594 e
= hfind(hfs
, &key
, &end
);
600 *off
= e
->base
.key
+ 1; // remember next pos
602 de
->d_namlen
= e
->data_len
- HAMMER_ENTRY_NAME_OFF
;
603 de
->d_type
= hammer_get_dtype(e
->base
.obj_type
);
604 hammer_data_ondisk_t ed
= hread(hfs
, e
->data_offset
);
607 de
->d_ino
= ed
->entry
.obj_id
;
608 bcopy(ed
->entry
.name
, de
->d_name
, de
->d_namlen
);
609 de
->d_name
[de
->d_namlen
] = 0;
616 hresolve(struct hfs
*hfs
, ino_t dirino
, const char *name
)
618 struct hammer_base_elm key
, end
;
619 size_t namel
= strlen(name
);
622 printf("%s(%llx, %s)\n", __func__
, (long long)dirino
, name
);
625 bzero(&key
, sizeof(key
));
627 key
.localization
= hdirlocalization(hfs
, dirino
);
628 key
.key
= hammer_directory_namekey(name
, namel
);
629 key
.rec_type
= HAMMER_RECTYPE_DIRENTRY
;
631 end
.key
= HAMMER_MAX_KEY
;
633 hammer_btree_leaf_elm_t e
;
634 while ((e
= hfind(hfs
, &key
, &end
)) != NULL
) {
635 key
.key
= e
->base
.key
+ 1;
637 size_t elen
= e
->data_len
- HAMMER_ENTRY_NAME_OFF
;
638 hammer_data_ondisk_t ed
= hread(hfs
, e
->data_offset
);
643 for (int i
= 0; i
< elen
; i
++)
644 putchar(ed
->entry
.name
[i
]);
650 if (elen
== namel
&& memcmp(ed
->entry
.name
, name
, MIN(elen
, namel
)) == 0)
651 return (ed
->entry
.obj_id
);
663 hlookup(struct hfs
*hfs
, const char *path
)
666 printf("%s(%s)\n", __func__
, path
);
674 char name
[MAXPATHLEN
+ 1];
679 for (char *n
= name
; *path
!= 0 && *path
!= '/'; path
++, n
++) {
685 // A single ? means "list"
686 if (name
[0] == '?' && name
[1] == 0)
690 ino
= hresolve(hfs
, ino
, name
);
691 } while (ino
!= (ino_t
)-1 && *path
!= 0);
699 hstat(struct hfs
*hfs
, ino_t ino
, struct stat
* st
)
701 struct hammer_base_elm key
;
704 printf("%s(%llx)\n", __func__
, (long long)ino
);
707 bzero(&key
, sizeof(key
));
709 key
.localization
= HAMMER_LOCALIZE_INODE
;
710 key
.rec_type
= HAMMER_RECTYPE_INODE
;
712 hammer_btree_leaf_elm_t e
= hfind(hfs
, &key
, &key
);
720 hammer_data_ondisk_t ed
= hread(hfs
, e
->data_offset
);
724 st
->st_mode
= ed
->inode
.mode
| hammer_get_mode(ed
->inode
.obj_type
);
725 st
->st_uid
= hammer_to_unix_xid(&ed
->inode
.uid
);
726 st
->st_gid
= hammer_to_unix_xid(&ed
->inode
.gid
);
727 st
->st_size
= ed
->inode
.size
;
734 hreadf(struct hfs
*hfs
, ino_t ino
, int64_t off
, int64_t len
, char *buf
)
736 int64_t startoff
= off
;
737 struct hammer_base_elm key
, end
;
739 bzero(&key
, sizeof(key
));
741 key
.localization
= HAMMER_LOCALIZE_MISC
;
742 key
.rec_type
= HAMMER_RECTYPE_DATA
;
744 end
.key
= HAMMER_MAX_KEY
;
748 hammer_btree_leaf_elm_t e
= hfind(hfs
, &key
, &end
);
751 if (e
== NULL
|| off
> e
->base
.key
) {
758 int64_t doff
= e
->base
.key
- e
->data_len
;
760 // sparse file, beginning
762 dlen
= MIN(dlen
, len
);
765 int64_t boff
= off
- doff
;
766 hammer_off_t roff
= e
->data_offset
;
770 dlen
= MIN(dlen
, len
);
772 while (boff
>= HAMMER_BUFSIZE
) {
773 boff
-= HAMMER_BUFSIZE
;
774 roff
+= HAMMER_BUFSIZE
;
778 * boff - relative offset in disk buffer (not aligned)
779 * roff - base offset of disk buffer (not aligned)
780 * dlen - amount of data we think we can copy
782 * hread only reads 16K aligned buffers, check for
783 * a length overflow and truncate dlen appropriately.
785 if ((roff
& ~HAMMER_BUFMASK64
) != ((roff
+ boff
+ dlen
- 1) & ~HAMMER_BUFMASK64
))
786 dlen
= HAMMER_BUFSIZE
- ((boff
+ roff
) & HAMMER_BUFMASK
);
787 char *data
= hread(hfs
, roff
);
790 bcopy(data
+ boff
, buf
, dlen
);
798 return (off
- startoff
);
805 boot2_hammer_init(void)
807 hammer_volume_ondisk_t volhead
;
809 volhead
= hread(&hfs
, HAMMER_ZONE_ENCODE(1, 0));
812 if (volhead
->vol_signature
!= HAMMER_FSBUF_VOLUME
)
814 hfs
.root
= volhead
->vol0_btree_root
;
815 hfs
.buf_beg
= volhead
->vol_buf_beg
;
820 boot2_hammer_lookup(const char *path
)
822 ino_t ino
= hlookup(&hfs
, path
);
833 boot2_hammer_read(boot2_ino_t ino
, void *buf
, size_t len
)
835 ssize_t rlen
= hreadf(&hfs
, ino
, fs_off
, len
, buf
);
841 const struct boot2_fsapi boot2_hammer_api
= {
842 .fsinit
= boot2_hammer_init
,
843 .fslookup
= boot2_hammer_lookup
,
844 .fsread
= boot2_hammer_read
851 hinit(struct hfs
*hfs
)
856 for (int i
= 0; i
< NUMCACHE
; i
++) {
857 hfs
->cache
[i
].data
= malloc(HAMMER_BUFSIZE
);
858 hfs
->cache
[i
].off
= -1; // invalid
859 hfs
->cache
[i
].use
= 0;
862 if (hfs
->cache
[i
].data
== NULL
)
863 printf("malloc failed\n");
867 hfs
->last_dir_ino
= -1;
869 hammer_volume_ondisk_t volhead
= hread(hfs
, HAMMER_ZONE_ENCODE(1, 0));
873 printf("signature: %svalid\n",
874 volhead
->vol_signature
!= HAMMER_FSBUF_VOLUME
?
877 printf("name: %s\n", volhead
->vol_label
);
881 if (volhead
== NULL
|| volhead
->vol_signature
!= HAMMER_FSBUF_VOLUME
) {
882 for (int i
= 0; i
< NUMCACHE
; i
++) {
883 free(hfs
->cache
[i
].data
);
884 hfs
->cache
[i
].data
= NULL
;
890 hfs
->root
= volhead
->vol0_btree_root
;
891 hfs
->buf_beg
= volhead
->vol_buf_beg
;
897 hclose(struct hfs
*hfs
)
902 for (int i
= 0; i
< NUMCACHE
; i
++) {
903 if (hfs
->cache
[i
].data
) {
904 free(hfs
->cache
[i
].data
);
905 hfs
->cache
[i
].data
= NULL
;
919 hammer_open(const char *path
, struct open_file
*f
)
921 struct hfile
*hf
= malloc(sizeof(*hf
));
923 bzero(hf
, sizeof(*hf
));
928 int rv
= hinit(&hf
->hfs
);
936 printf("hammer_open %s %p\n", path
, f
);
939 hf
->ino
= hlookup(&hf
->hfs
, path
);
944 if (hstat(&hf
->hfs
, hf
->ino
, &st
) == -1)
946 hf
->fsize
= st
.st_size
;
949 printf(" %ld\n", (long)hf
->fsize
);
956 printf("hammer_open fail\n");
965 hammer_close(struct open_file
*f
)
967 struct hfile
*hf
= f
->f_fsdata
;
978 hammer_read(struct open_file
*f
, void *buf
, size_t len
, size_t *resid
)
980 struct hfile
*hf
= f
->f_fsdata
;
983 printf("hammer_read %p %ld %ld\n", f
, f
->f_offset
, len
);
986 if (f
->f_offset
>= hf
->fsize
)
990 if (f
->f_offset
+ len
> hf
->fsize
)
991 maxlen
= hf
->fsize
- f
->f_offset
;
993 ssize_t rlen
= hreadf(&hf
->hfs
, hf
->ino
, f
->f_offset
, maxlen
, buf
);
1004 hammer_seek(struct open_file
*f
, off_t offset
, int whence
)
1006 struct hfile
*hf
= f
->f_fsdata
;
1010 f
->f_offset
= offset
;
1013 f
->f_offset
+= offset
;
1016 f
->f_offset
= hf
->fsize
- offset
;
1021 return (f
->f_offset
);
1025 hammer_stat(struct open_file
*f
, struct stat
*st
)
1027 struct hfile
*hf
= f
->f_fsdata
;
1029 return (hstat(&hf
->hfs
, hf
->ino
, st
));
1033 hammer_readdir(struct open_file
*f
, struct dirent
*d
)
1035 struct hfile
*hf
= f
->f_fsdata
;
1037 int64_t off
= f
->f_offset
;
1038 int rv
= hreaddir(&hf
->hfs
, hf
->ino
, &off
, d
);
1044 struct fs_ops hammer1_fsops
= {
1058 main(int argc
, char **argv
)
1061 fprintf(stderr
, "usage: hammerread <dev>\n");
1066 hfs
.fd
= open(argv
[1], O_RDONLY
);
1068 err(1, "unable to open %s", argv
[1]);
1070 if (hinit(&hfs
) == -1)
1071 err(1, "invalid hammerfs");
1073 for (int i
= 2; i
< argc
; i
++) {
1074 ino_t ino
= hlookup(&hfs
, argv
[i
]);
1075 if (ino
== (ino_t
)-1) {
1076 warn("hlookup %s", argv
[i
]);
1081 if (hstat(&hfs
, ino
, &st
)) {
1082 warn("hstat %s", argv
[i
]);
1086 printf("%s %d/%d %o %lld\n",
1088 st
.st_uid
, st
.st_gid
,
1089 st
.st_mode
, st
.st_size
);
1091 if (S_ISDIR(st
.st_mode
)) {
1094 while (hreaddir(&hfs
, ino
, &off
, &de
) == 0) {
1095 printf("%s %d %llx\n",
1096 de
.d_name
, de
.d_type
, de
.d_ino
);
1098 } else if (S_ISREG(st
.st_mode
)) {
1099 char *buf
= malloc(100000);
1101 while (off
< st
.st_size
) {
1102 int64_t len
= MIN(100000, st
.st_size
- off
);
1103 int64_t rl
= hreadf(&hfs
, ino
, off
, len
, buf
);
1104 fwrite(buf
, rl
, 1, stdout
);