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
35 * $DragonFly: src/lib/libstand/hammerread.c,v 1.2 2008/10/29 22:14:25 swildner Exp $
39 * This file is being used by boot2 and libstand (loader).
40 * Compile with -DTESTING to obtain a binary.
44 #if !defined(BOOT2) && !defined(TESTING)
51 #include <sys/param.h>
57 #include <sys/fcntl.h>
72 #include <vfs/hammer/hammer_disk.h>
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)
155 hread(struct hfs
*hfs
, hammer_off_t off
)
157 char *buf
= fsdmadat
->buf
;
159 hammer_off_t boff
= off
& ~HAMMER_BUFMASK64
;
160 boff
&= HAMMER_OFF_LONG_MASK
;
161 if (HAMMER_ZONE_DECODE(off
) != HAMMER_ZONE_RAW_VOLUME_INDEX
)
162 boff
+= hfs
->buf_beg
;
163 boff
&= HAMMER_OFF_SHORT_MASK
;
165 if (dskread(buf
, boff
, HAMMER_BUFSIZE
>> DEV_BSHIFT
))
167 return (&buf
[off
& HAMMER_BUFMASK
]);
171 bzero(void *buf
, size_t size
)
173 for (size_t i
= 0; i
< size
; i
++)
174 ((char *)buf
)[i
] = 0;
178 bcopy(void *src
, void *dst
, size_t size
)
180 memcpy(dst
, src
, size
);
184 strlen(const char *s
)
193 memcmp(const void *a
, const void *b
, size_t len
)
195 for (size_t p
= 0; p
< len
; p
++) {
196 int r
= ((const char *)a
)[p
] - ((const char *)b
)[p
];
207 * (from hammer_btree.c)
209 * Compare two B-Tree elements, return -N, 0, or +N (e.g. similar to strcmp).
211 * Note that for this particular function a return value of -1, 0, or +1
212 * can denote a match if create_tid is otherwise discounted. A create_tid
213 * of zero is considered to be 'infinity' in comparisons.
215 * See also hammer_rec_rb_compare() and hammer_rec_cmp() in hammer_object.c.
218 hammer_btree_cmp(hammer_base_elm_t key1
, hammer_base_elm_t key2
)
220 if (key1
->localization
< key2
->localization
)
222 if (key1
->localization
> key2
->localization
)
225 if (key1
->obj_id
< key2
->obj_id
)
227 if (key1
->obj_id
> key2
->obj_id
)
230 if (key1
->rec_type
< key2
->rec_type
)
232 if (key1
->rec_type
> key2
->rec_type
)
235 if (key1
->key
< key2
->key
)
237 if (key1
->key
> key2
->key
)
241 * A create_tid of zero indicates a record which is undeletable
242 * and must be considered to have a value of positive infinity.
244 if (key1
->create_tid
== 0) {
245 if (key2
->create_tid
== 0)
249 if (key2
->create_tid
== 0)
251 if (key1
->create_tid
< key2
->create_tid
)
253 if (key1
->create_tid
> key2
->create_tid
)
259 * Heuristical search for the first element whos comparison is <= 1. May
260 * return an index whos compare result is > 1 but may only return an index
261 * whos compare result is <= 1 if it is the first element with that result.
264 hammer_btree_search_node(hammer_base_elm_t elm
, hammer_node_ondisk_t node
)
272 * Don't bother if the node does not have very many elements
278 r
= hammer_btree_cmp(elm
, &node
->elms
[i
].leaf
.base
);
290 * (from hammer_subs.c)
292 * Return a namekey hash. The 64 bit namekey hash consists of a 32 bit
293 * crc in the MSB and 0 in the LSB. The caller will use the low bits to
294 * generate a unique key and will scan all entries with the same upper
295 * 32 bits when issuing a lookup.
297 * We strip bit 63 in order to provide a positive key, this way a seek
298 * offset of 0 will represent the base of the directory.
300 * This function can never return 0. We use the MSB-0 space to synthesize
301 * artificial directory entries such as "." and "..".
304 hammer_directory_namekey(const void *name
, int len
)
308 key
= (int64_t)(crc32(name
, len
) & 0x7FFFFFFF) << 32;
310 key
|= 0x100000000LL
;
315 hammer_directory_namekey(const void *name __unused
, int len __unused
)
327 hammer_to_unix_xid(uuid_t
*uuid
)
329 return(*(u_int32_t
*)&uuid
->node
[2]);
333 hammer_get_dtype(u_int8_t obj_type
)
336 case HAMMER_OBJTYPE_DIRECTORY
:
338 case HAMMER_OBJTYPE_REGFILE
:
340 case HAMMER_OBJTYPE_DBFILE
:
342 case HAMMER_OBJTYPE_FIFO
:
344 case HAMMER_OBJTYPE_SOCKET
:
346 case HAMMER_OBJTYPE_CDEV
:
348 case HAMMER_OBJTYPE_BDEV
:
350 case HAMMER_OBJTYPE_SOFTLINK
:
359 hammer_get_mode(u_int8_t obj_type
)
362 case HAMMER_OBJTYPE_DIRECTORY
:
364 case HAMMER_OBJTYPE_REGFILE
:
366 case HAMMER_OBJTYPE_DBFILE
:
368 case HAMMER_OBJTYPE_FIFO
:
370 case HAMMER_OBJTYPE_SOCKET
:
372 case HAMMER_OBJTYPE_CDEV
:
374 case HAMMER_OBJTYPE_BDEV
:
376 case HAMMER_OBJTYPE_SOFTLINK
:
386 hprintb(hammer_base_elm_t e
)
388 printf("%d/", e
->localization
);
389 if (e
->obj_id
>> 32 != 0)
391 (long)(e
->obj_id
>> 32),
392 (long)(e
->obj_id
& 0xffffffff));
394 printf("%lx", (long)e
->obj_id
);
395 printf("/%d/", e
->rec_type
);
396 if (e
->key
>> 32 != 0)
398 (long)(e
->key
>> 32),
399 (long)(e
->key
& 0xffffffff));
401 printf("%lx", (long)e
->key
);
403 printf("/%llx/%llx", e
->create_tid
, e
->delete_tid
);
406 #endif /* DEBUG > 1 */
409 static hammer_btree_leaf_elm_t
410 hfind(struct hfs
*hfs
, hammer_base_elm_t key
, hammer_base_elm_t end
)
413 printf("searching for ");
422 struct hammer_base_elm search
= *key
;
423 struct hammer_base_elm backtrack
;
424 hammer_off_t nodeoff
= hfs
->root
;
425 hammer_node_ondisk_t node
;
426 hammer_btree_elm_t e
= NULL
;
430 node
= hread(hfs
, nodeoff
);
433 internal
= node
->type
== HAMMER_BTREE_TYPE_INTERNAL
;
436 for (int i
= 0; i
< node
->count
; i
++) {
438 hprintb(&node
->elms
[i
].base
);
443 hprintb(&node
->elms
[node
->count
].base
);
448 n
= hammer_btree_search_node(&search
, node
);
450 // In internal nodes, we cover the right boundary as well.
451 // If we hit it, we'll backtrack.
452 for (; n
< node
->count
+ internal
; n
++) {
454 r
= hammer_btree_cmp(&search
, &e
->base
);
460 // unless we stopped right on the left side, we need to back off a bit
462 e
= &node
->elms
[--n
];
471 // If we hit the right boundary, backtrack to
472 // the next higher level.
473 if (n
== node
->count
)
475 nodeoff
= e
->internal
.subtree_offset
;
476 backtrack
= (e
+1)->base
;
480 r
= hammer_btree_cmp(key
, &e
->base
);
481 // If we're more off than the createtid, take the next elem
487 // Skip deleted elements
488 while (n
< node
->count
&& e
->base
.delete_tid
!= 0) {
493 // In the unfortunate event when there is no next
494 // element in this node, we repeat the search with
495 // a key beyond the right boundary
496 if (n
== node
->count
) {
502 printf("hit right boundary (%d), resetting search to ",
517 if (hammer_btree_cmp(end
, &e
->base
) < -1)
531 hreaddir(struct hfs
*hfs
, ino_t ino
, int64_t *off
, struct dirent
*de
)
533 struct hammer_base_elm key
, end
;
536 printf("%s(%llx, %lld)\n", __FUNCTION__
, (long long)ino
, *off
);
539 bzero(&key
, sizeof(key
));
541 key
.localization
= HAMMER_LOCALIZE_MISC
;
542 key
.rec_type
= HAMMER_RECTYPE_DIRENTRY
;
546 end
.key
= HAMMER_MAX_KEY
;
548 hammer_btree_leaf_elm_t e
;
550 e
= hfind(hfs
, &key
, &end
);
556 *off
= e
->base
.key
+ 1; // remember next pos
558 de
->d_namlen
= e
->data_len
- HAMMER_ENTRY_NAME_OFF
;
559 de
->d_type
= hammer_get_dtype(e
->base
.obj_type
);
560 hammer_data_ondisk_t ed
= hread(hfs
, e
->data_offset
);
563 de
->d_ino
= ed
->entry
.obj_id
;
564 bcopy(ed
->entry
.name
, de
->d_name
, de
->d_namlen
);
565 de
->d_name
[de
->d_namlen
] = 0;
572 hresolve(struct hfs
*hfs
, ino_t dirino
, const char *name
)
574 struct hammer_base_elm key
, end
;
575 size_t namel
= strlen(name
);
578 printf("%s(%llx, %s)\n", __FUNCTION__
, (long long)dirino
, name
);
581 bzero(&key
, sizeof(key
));
583 key
.localization
= HAMMER_LOCALIZE_MISC
;
584 key
.key
= hammer_directory_namekey(name
, namel
);
585 key
.rec_type
= HAMMER_RECTYPE_DIRENTRY
;
587 end
.key
= HAMMER_MAX_KEY
;
589 hammer_btree_leaf_elm_t e
;
590 while ((e
= hfind(hfs
, &key
, &end
)) != NULL
) {
591 key
.key
= e
->base
.key
+ 1;
593 size_t elen
= e
->data_len
- HAMMER_ENTRY_NAME_OFF
;
594 hammer_data_ondisk_t ed
= hread(hfs
, e
->data_offset
);
599 for (int i
= 0; i
< elen
; i
++)
600 putchar(ed
->entry
.name
[i
]);
606 if (elen
== namel
&& memcmp(ed
->entry
.name
, name
, MIN(elen
, namel
)) == 0)
607 return (ed
->entry
.obj_id
);
619 hlookup(struct hfs
*hfs
, const char *path
)
622 printf("%s(%s)\n", __FUNCTION__
, path
);
630 char name
[MAXPATHLEN
+ 1];
635 for (char *n
= name
; *path
!= 0 && *path
!= '/'; path
++, n
++) {
641 // A single ? means "list"
642 if (name
[0] == '?' && name
[1] == 0)
646 ino
= hresolve(hfs
, ino
, name
);
647 } while (ino
!= (ino_t
)-1 && *path
!= 0);
655 hstat(struct hfs
*hfs
, ino_t ino
, struct stat
* st
)
657 struct hammer_base_elm key
;
660 printf("%s(%llx)\n", __FUNCTION__
, (long long)ino
);
663 bzero(&key
, sizeof(key
));
665 key
.localization
= HAMMER_LOCALIZE_INODE
;
666 key
.rec_type
= HAMMER_RECTYPE_INODE
;
668 hammer_btree_leaf_elm_t e
= hfind(hfs
, &key
, &key
);
676 hammer_data_ondisk_t ed
= hread(hfs
, e
->data_offset
);
680 st
->st_mode
= ed
->inode
.mode
| hammer_get_mode(ed
->inode
.obj_type
);
681 st
->st_uid
= hammer_to_unix_xid(&ed
->inode
.uid
);
682 st
->st_gid
= hammer_to_unix_xid(&ed
->inode
.gid
);
683 st
->st_size
= ed
->inode
.size
;
690 hreadf(struct hfs
*hfs
, ino_t ino
, int64_t off
, int64_t len
, char *buf
)
692 int64_t startoff
= off
;
693 struct hammer_base_elm key
, end
;
695 bzero(&key
, sizeof(key
));
697 key
.localization
= HAMMER_LOCALIZE_MISC
;
698 key
.rec_type
= HAMMER_RECTYPE_DATA
;
700 end
.key
= HAMMER_MAX_KEY
;
704 hammer_btree_leaf_elm_t e
= hfind(hfs
, &key
, &end
);
707 if (e
== NULL
|| off
> e
->base
.key
) {
714 int64_t doff
= e
->base
.key
- e
->data_len
;
716 // sparse file, beginning
718 dlen
= MIN(dlen
, len
);
721 int64_t boff
= off
- doff
;
722 hammer_off_t roff
= e
->data_offset
;
726 dlen
= MIN(dlen
, len
);
728 while (boff
>= HAMMER_BUFSIZE
) {
729 boff
-= HAMMER_BUFSIZE
;
730 roff
+= HAMMER_BUFSIZE
;
734 * boff - relative offset in disk buffer (not aligned)
735 * roff - base offset of disk buffer (not aligned)
736 * dlen - amount of data we think we can copy
738 * hread only reads 16K aligned buffers, check for
739 * a length overflow and truncate dlen appropriately.
741 if ((roff
& ~HAMMER_BUFMASK64
) != ((roff
+ boff
+ dlen
- 1) & ~HAMMER_BUFMASK64
))
742 dlen
= HAMMER_BUFSIZE
- ((boff
+ roff
) & HAMMER_BUFMASK
);
743 char *data
= hread(hfs
, roff
);
746 bcopy(data
+ boff
, buf
, dlen
);
754 return (off
- startoff
);
761 boot2_hammer_init(void)
763 hammer_volume_ondisk_t volhead
;
765 volhead
= hread(&hfs
, HAMMER_ZONE_ENCODE(1, 0));
768 if (volhead
->vol_signature
!= HAMMER_FSBUF_VOLUME
)
770 hfs
.root
= volhead
->vol0_btree_root
;
771 hfs
.buf_beg
= volhead
->vol_buf_beg
;
776 boot2_hammer_lookup(const char *path
)
778 ino_t ino
= hlookup(&hfs
, path
);
789 boot2_hammer_read(boot2_ino_t ino
, void *buf
, size_t len
)
791 ssize_t rlen
= hreadf(&hfs
, ino
, fs_off
, len
, buf
);
797 const struct boot2_fsapi boot2_hammer_api
= {
798 .fsinit
= boot2_hammer_init
,
799 .fslookup
= boot2_hammer_lookup
,
800 .fsread
= boot2_hammer_read
807 hinit(struct hfs
*hfs
)
812 for (int i
= 0; i
< NUMCACHE
; i
++) {
813 hfs
->cache
[i
].data
= malloc(HAMMER_BUFSIZE
);
814 hfs
->cache
[i
].off
= -1; // invalid
815 hfs
->cache
[i
].use
= 0;
818 if (hfs
->cache
[i
].data
== NULL
)
819 printf("malloc failed\n");
824 hammer_volume_ondisk_t volhead
= hread(hfs
, HAMMER_ZONE_ENCODE(1, 0));
828 printf("signature: %svalid\n",
829 volhead
->vol_signature
!= HAMMER_FSBUF_VOLUME
?
832 printf("name: %s\n", volhead
->vol_name
);
836 if (volhead
== NULL
|| volhead
->vol_signature
!= HAMMER_FSBUF_VOLUME
) {
837 for (int i
= 0; i
< NUMCACHE
; i
++) {
838 free(hfs
->cache
[i
].data
);
839 hfs
->cache
[i
].data
= NULL
;
845 hfs
->root
= volhead
->vol0_btree_root
;
846 hfs
->buf_beg
= volhead
->vol_buf_beg
;
852 hclose(struct hfs
*hfs
)
857 for (int i
= 0; i
< NUMCACHE
; i
++) {
858 if (hfs
->cache
[i
].data
) {
859 free(hfs
->cache
[i
].data
);
860 hfs
->cache
[i
].data
= NULL
;
874 hammer_open(const char *path
, struct open_file
*f
)
876 struct hfile
*hf
= malloc(sizeof(*hf
));
878 bzero(hf
, sizeof(*hf
));
883 int rv
= hinit(&hf
->hfs
);
891 printf("hammer_open %s %p %ld\n", path
, f
);
894 hf
->ino
= hlookup(&hf
->hfs
, path
);
899 if (hstat(&hf
->hfs
, hf
->ino
, &st
) == -1)
901 hf
->fsize
= st
.st_size
;
904 printf(" %ld\n", (long)hf
->fsize
);
911 printf("hammer_open fail\n");
920 hammer_close(struct open_file
*f
)
922 struct hfile
*hf
= f
->f_fsdata
;
933 hammer_read(struct open_file
*f
, void *buf
, size_t len
, size_t *resid
)
935 struct hfile
*hf
= f
->f_fsdata
;
938 printf("hammer_read %p %ld %ld\n", f
, f
->f_offset
, len
);
941 if (f
->f_offset
>= hf
->fsize
)
945 if (f
->f_offset
+ len
> hf
->fsize
)
946 maxlen
= hf
->fsize
- f
->f_offset
;
948 ssize_t rlen
= hreadf(&hf
->hfs
, hf
->ino
, f
->f_offset
, maxlen
, buf
);
959 hammer_seek(struct open_file
*f
, off_t offset
, int whence
)
961 struct hfile
*hf
= f
->f_fsdata
;
965 f
->f_offset
= offset
;
968 f
->f_offset
+= offset
;
971 f
->f_offset
= hf
->fsize
- offset
;
976 return (f
->f_offset
);
980 hammer_stat(struct open_file
*f
, struct stat
*st
)
982 struct hfile
*hf
= f
->f_fsdata
;
984 return (hstat(&hf
->hfs
, hf
->ino
, st
));
988 hammer_readdir(struct open_file
*f
, struct dirent
*d
)
990 struct hfile
*hf
= f
->f_fsdata
;
992 int64_t off
= f
->f_offset
;
993 int rv
= hreaddir(&hf
->hfs
, hf
->ino
, &off
, d
);
999 struct fs_ops hammer_fsops
= {
1013 main(int argc
, char **argv
)
1016 fprintf(stderr
, "usage: hammerread <dev>\n");
1021 hfs
.fd
= open(argv
[1], O_RDONLY
);
1023 err(1, "unable to open %s", argv
[1]);
1025 if (hinit(&hfs
) == -1)
1026 err(1, "invalid hammerfs");
1028 for (int i
= 2; i
< argc
; i
++) {
1029 ino_t ino
= hlookup(&hfs
, argv
[i
]);
1030 if (ino
== (ino_t
)-1) {
1031 warn("hlookup %s", argv
[i
]);
1036 if (hstat(&hfs
, ino
, &st
)) {
1037 warn("hstat %s", argv
[i
]);
1041 printf("%s %d/%d %o %lld\n",
1043 st
.st_uid
, st
.st_gid
,
1044 st
.st_mode
, st
.st_size
);
1046 if (S_ISDIR(st
.st_mode
)) {
1049 while (hreaddir(&hfs
, ino
, &off
, &de
) == 0) {
1050 printf("%s %d %llx\n",
1051 de
.d_name
, de
.d_type
, de
.d_ino
);
1053 } else if (S_ISREG(st
.st_mode
)) {
1054 char *buf
= malloc(100000);
1056 while (off
< st
.st_size
) {
1057 int64_t len
= MIN(100000, st
.st_size
- off
);
1058 int64_t rl
= hreadf(&hfs
, ino
, off
, len
, buf
);
1059 fwrite(buf
, rl
, 1, stdout
);