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 u_int8_t last_dir_cap_flags
;
98 struct blockentry cache
[NUMCACHE
];
102 hread(struct hfs
*hfs
, hammer_off_t off
)
104 hammer_off_t boff
= off
& ~HAMMER_BUFMASK64
;
106 boff
&= HAMMER_OFF_LONG_MASK
;
108 if (HAMMER_ZONE_DECODE(off
) != HAMMER_ZONE_RAW_VOLUME_INDEX
)
109 boff
+= hfs
->buf_beg
;
111 struct blockentry
*be
= NULL
;
112 for (int i
= 0; i
< NUMCACHE
; i
++) {
113 if (be
== NULL
|| be
->use
> hfs
->cache
[i
].use
)
115 if (hfs
->cache
[i
].off
== boff
) {
120 if (be
->off
!= boff
) {
121 // Didn't find any match
124 ssize_t res
= pread(hfs
->fd
, be
->data
, HAMMER_BUFSIZE
,
125 boff
& HAMMER_OFF_SHORT_MASK
);
126 if (res
!= HAMMER_BUFSIZE
)
127 err(1, "short read on off %llx", boff
);
130 int rv
= hfs
->f
->f_dev
->dv_strategy(hfs
->f
->f_devdata
, F_READ
,
131 boff
>> DEV_BSHIFT
, HAMMER_BUFSIZE
,
133 if (rv
|| rlen
!= HAMMER_BUFSIZE
)
138 be
->use
= ++hfs
->lru
;
139 return &be
->data
[off
& HAMMER_BUFMASK
];
144 struct hammer_dmadat
{
145 struct boot2_dmadat boot2
;
146 char buf
[HAMMER_BUFSIZE
];
149 #define fsdmadat ((struct hammer_dmadat *)boot2_dmadat)
153 int64_t last_dir_ino
;
154 u_int8_t last_dir_cap_flags
;
159 hread(struct hfs
*hfs
, hammer_off_t off
)
161 char *buf
= fsdmadat
->buf
;
163 hammer_off_t boff
= off
& ~HAMMER_BUFMASK64
;
164 boff
&= HAMMER_OFF_LONG_MASK
;
165 if (HAMMER_ZONE_DECODE(off
) != HAMMER_ZONE_RAW_VOLUME_INDEX
)
166 boff
+= hfs
->buf_beg
;
167 boff
&= HAMMER_OFF_SHORT_MASK
;
169 if (dskread(buf
, boff
, HAMMER_BUFSIZE
>> DEV_BSHIFT
))
171 return (&buf
[off
& HAMMER_BUFMASK
]);
175 bzero(void *buf
, size_t size
)
177 for (size_t i
= 0; i
< size
; i
++)
178 ((char *)buf
)[i
] = 0;
182 bcopy(void *src
, void *dst
, size_t size
)
184 memcpy(dst
, src
, size
);
188 strlen(const char *s
)
197 memcmp(const void *a
, const void *b
, size_t len
)
199 for (size_t p
= 0; p
< len
; p
++) {
200 int r
= ((const char *)a
)[p
] - ((const char *)b
)[p
];
211 * (from hammer_btree.c)
213 * Compare two B-Tree elements, return -N, 0, or +N (e.g. similar to strcmp).
215 * Note that for this particular function a return value of -1, 0, or +1
216 * can denote a match if create_tid is otherwise discounted. A create_tid
217 * of zero is considered to be 'infinity' in comparisons.
219 * See also hammer_rec_rb_compare() and hammer_rec_cmp() in hammer_object.c.
222 hammer_btree_cmp(hammer_base_elm_t key1
, hammer_base_elm_t key2
)
224 if (key1
->localization
< key2
->localization
)
226 if (key1
->localization
> key2
->localization
)
229 if (key1
->obj_id
< key2
->obj_id
)
231 if (key1
->obj_id
> key2
->obj_id
)
234 if (key1
->rec_type
< key2
->rec_type
)
236 if (key1
->rec_type
> key2
->rec_type
)
239 if (key1
->key
< key2
->key
)
241 if (key1
->key
> key2
->key
)
245 * A create_tid of zero indicates a record which is undeletable
246 * and must be considered to have a value of positive infinity.
248 if (key1
->create_tid
== 0) {
249 if (key2
->create_tid
== 0)
253 if (key2
->create_tid
== 0)
255 if (key1
->create_tid
< key2
->create_tid
)
257 if (key1
->create_tid
> key2
->create_tid
)
263 * Heuristical search for the first element whos comparison is <= 1. May
264 * return an index whos compare result is > 1 but may only return an index
265 * whos compare result is <= 1 if it is the first element with that result.
268 hammer_btree_search_node(hammer_base_elm_t elm
, hammer_node_ondisk_t node
)
276 * Don't bother if the node does not have very many elements
282 r
= hammer_btree_cmp(elm
, &node
->elms
[i
].leaf
.base
);
294 * (from hammer_subs.c)
296 * Return a namekey hash. The 64 bit namekey hash consists of a 32 bit
297 * crc in the MSB and 0 in the LSB. The caller will use the low bits to
298 * generate a unique key and will scan all entries with the same upper
299 * 32 bits when issuing a lookup.
301 * We strip bit 63 in order to provide a positive key, this way a seek
302 * offset of 0 will represent the base of the directory.
304 * This function can never return 0. We use the MSB-0 space to synthesize
305 * artificial directory entries such as "." and "..".
308 hammer_directory_namekey(const void *name
, int len
)
312 key
= (int64_t)(crc32(name
, len
) & 0x7FFFFFFF) << 32;
314 key
|= 0x100000000LL
;
319 hammer_directory_namekey(const void *name __unused
, int len __unused
)
331 hammer_to_unix_xid(uuid_t
*uuid
)
333 return(*(u_int32_t
*)&uuid
->node
[2]);
337 hammer_get_dtype(u_int8_t obj_type
)
340 case HAMMER_OBJTYPE_DIRECTORY
:
342 case HAMMER_OBJTYPE_REGFILE
:
344 case HAMMER_OBJTYPE_DBFILE
:
346 case HAMMER_OBJTYPE_FIFO
:
348 case HAMMER_OBJTYPE_SOCKET
:
350 case HAMMER_OBJTYPE_CDEV
:
352 case HAMMER_OBJTYPE_BDEV
:
354 case HAMMER_OBJTYPE_SOFTLINK
:
363 hammer_get_mode(u_int8_t obj_type
)
366 case HAMMER_OBJTYPE_DIRECTORY
:
368 case HAMMER_OBJTYPE_REGFILE
:
370 case HAMMER_OBJTYPE_DBFILE
:
372 case HAMMER_OBJTYPE_FIFO
:
374 case HAMMER_OBJTYPE_SOCKET
:
376 case HAMMER_OBJTYPE_CDEV
:
378 case HAMMER_OBJTYPE_BDEV
:
380 case HAMMER_OBJTYPE_SOFTLINK
:
390 hprintb(hammer_base_elm_t e
)
392 printf("%d/", e
->localization
);
393 if (e
->obj_id
>> 32 != 0)
395 (long)(e
->obj_id
>> 32),
396 (long)(e
->obj_id
& 0xffffffff));
398 printf("%lx", (long)e
->obj_id
);
399 printf("/%d/", e
->rec_type
);
400 if (e
->key
>> 32 != 0)
402 (long)(e
->key
>> 32),
403 (long)(e
->key
& 0xffffffff));
405 printf("%lx", (long)e
->key
);
407 printf("/%llx/%llx", e
->create_tid
, e
->delete_tid
);
410 #endif /* DEBUG > 1 */
413 static hammer_btree_leaf_elm_t
414 hfind(struct hfs
*hfs
, hammer_base_elm_t key
, hammer_base_elm_t end
)
417 printf("searching for ");
426 struct hammer_base_elm search
= *key
;
427 struct hammer_base_elm backtrack
;
428 hammer_off_t nodeoff
= hfs
->root
;
429 hammer_node_ondisk_t node
;
430 hammer_btree_elm_t e
= NULL
;
434 node
= hread(hfs
, nodeoff
);
437 internal
= node
->type
== HAMMER_BTREE_TYPE_INTERNAL
;
440 for (int i
= 0; i
< node
->count
; i
++) {
442 hprintb(&node
->elms
[i
].base
);
447 hprintb(&node
->elms
[node
->count
].base
);
452 n
= hammer_btree_search_node(&search
, node
);
454 // In internal nodes, we cover the right boundary as well.
455 // If we hit it, we'll backtrack.
456 for (; n
< node
->count
+ internal
; n
++) {
458 r
= hammer_btree_cmp(&search
, &e
->base
);
464 // unless we stopped right on the left side, we need to back off a bit
466 e
= &node
->elms
[--n
];
475 // If we hit the right boundary, backtrack to
476 // the next higher level.
477 if (n
== node
->count
)
479 nodeoff
= e
->internal
.subtree_offset
;
480 backtrack
= (e
+1)->base
;
484 r
= hammer_btree_cmp(key
, &e
->base
);
485 // If we're more off than the createtid, take the next elem
491 // Skip deleted elements
492 while (n
< node
->count
&& e
->base
.delete_tid
!= 0) {
497 // In the unfortunate event when there is no next
498 // element in this node, we repeat the search with
499 // a key beyond the right boundary
500 if (n
== node
->count
) {
506 printf("hit right boundary (%d), resetting search to ",
521 if (hammer_btree_cmp(end
, &e
->base
) < -1)
534 * Returns the directory entry localization field based on the directory
535 * inode's capabilities.
538 hdirlocalization(struct hfs
*hfs
, ino_t ino
)
540 struct hammer_base_elm key
;
542 if (ino
!= hfs
->last_dir_ino
) {
543 bzero(&key
, sizeof(key
));
545 key
.localization
= HAMMER_LOCALIZE_INODE
;
546 key
.rec_type
= HAMMER_RECTYPE_INODE
;
547 hammer_btree_leaf_elm_t e
;
548 hammer_data_ondisk_t ed
;
550 e
= hfind(hfs
, &key
, &key
);
552 ed
= hread(hfs
, e
->data_offset
);
554 hfs
->last_dir_ino
= ino
;
555 hfs
->last_dir_cap_flags
= ed
->inode
.cap_flags
;
557 printf("hdirlocal: no inode data for %llx\n",
561 printf("hdirlocal: no inode entry for %llx\n",
565 if (hfs
->last_dir_cap_flags
& HAMMER_INODE_CAP_DIR_LOCAL_INO
)
566 return(HAMMER_LOCALIZE_INODE
);
568 return(HAMMER_LOCALIZE_MISC
);
573 hreaddir(struct hfs
*hfs
, ino_t ino
, int64_t *off
, struct dirent
*de
)
575 struct hammer_base_elm key
, end
;
578 printf("%s(%llx, %lld)\n", __FUNCTION__
, (long long)ino
, *off
);
581 bzero(&key
, sizeof(key
));
583 key
.localization
= hdirlocalization(hfs
, ino
);
584 key
.rec_type
= HAMMER_RECTYPE_DIRENTRY
;
588 end
.key
= HAMMER_MAX_KEY
;
590 hammer_btree_leaf_elm_t e
;
592 e
= hfind(hfs
, &key
, &end
);
598 *off
= e
->base
.key
+ 1; // remember next pos
600 de
->d_namlen
= e
->data_len
- HAMMER_ENTRY_NAME_OFF
;
601 de
->d_type
= hammer_get_dtype(e
->base
.obj_type
);
602 hammer_data_ondisk_t ed
= hread(hfs
, e
->data_offset
);
605 de
->d_ino
= ed
->entry
.obj_id
;
606 bcopy(ed
->entry
.name
, de
->d_name
, de
->d_namlen
);
607 de
->d_name
[de
->d_namlen
] = 0;
614 hresolve(struct hfs
*hfs
, ino_t dirino
, const char *name
)
616 struct hammer_base_elm key
, end
;
617 size_t namel
= strlen(name
);
620 printf("%s(%llx, %s)\n", __FUNCTION__
, (long long)dirino
, name
);
623 bzero(&key
, sizeof(key
));
625 key
.localization
= hdirlocalization(hfs
, dirino
);
626 key
.key
= hammer_directory_namekey(name
, namel
);
627 key
.rec_type
= HAMMER_RECTYPE_DIRENTRY
;
629 end
.key
= HAMMER_MAX_KEY
;
631 hammer_btree_leaf_elm_t e
;
632 while ((e
= hfind(hfs
, &key
, &end
)) != NULL
) {
633 key
.key
= e
->base
.key
+ 1;
635 size_t elen
= e
->data_len
- HAMMER_ENTRY_NAME_OFF
;
636 hammer_data_ondisk_t ed
= hread(hfs
, e
->data_offset
);
641 for (int i
= 0; i
< elen
; i
++)
642 putchar(ed
->entry
.name
[i
]);
648 if (elen
== namel
&& memcmp(ed
->entry
.name
, name
, MIN(elen
, namel
)) == 0)
649 return (ed
->entry
.obj_id
);
661 hlookup(struct hfs
*hfs
, const char *path
)
664 printf("%s(%s)\n", __FUNCTION__
, path
);
672 char name
[MAXPATHLEN
+ 1];
677 for (char *n
= name
; *path
!= 0 && *path
!= '/'; path
++, n
++) {
683 // A single ? means "list"
684 if (name
[0] == '?' && name
[1] == 0)
688 ino
= hresolve(hfs
, ino
, name
);
689 } while (ino
!= (ino_t
)-1 && *path
!= 0);
697 hstat(struct hfs
*hfs
, ino_t ino
, struct stat
* st
)
699 struct hammer_base_elm key
;
702 printf("%s(%llx)\n", __FUNCTION__
, (long long)ino
);
705 bzero(&key
, sizeof(key
));
707 key
.localization
= HAMMER_LOCALIZE_INODE
;
708 key
.rec_type
= HAMMER_RECTYPE_INODE
;
710 hammer_btree_leaf_elm_t e
= hfind(hfs
, &key
, &key
);
718 hammer_data_ondisk_t ed
= hread(hfs
, e
->data_offset
);
722 st
->st_mode
= ed
->inode
.mode
| hammer_get_mode(ed
->inode
.obj_type
);
723 st
->st_uid
= hammer_to_unix_xid(&ed
->inode
.uid
);
724 st
->st_gid
= hammer_to_unix_xid(&ed
->inode
.gid
);
725 st
->st_size
= ed
->inode
.size
;
732 hreadf(struct hfs
*hfs
, ino_t ino
, int64_t off
, int64_t len
, char *buf
)
734 int64_t startoff
= off
;
735 struct hammer_base_elm key
, end
;
737 bzero(&key
, sizeof(key
));
739 key
.localization
= HAMMER_LOCALIZE_MISC
;
740 key
.rec_type
= HAMMER_RECTYPE_DATA
;
742 end
.key
= HAMMER_MAX_KEY
;
746 hammer_btree_leaf_elm_t e
= hfind(hfs
, &key
, &end
);
749 if (e
== NULL
|| off
> e
->base
.key
) {
756 int64_t doff
= e
->base
.key
- e
->data_len
;
758 // sparse file, beginning
760 dlen
= MIN(dlen
, len
);
763 int64_t boff
= off
- doff
;
764 hammer_off_t roff
= e
->data_offset
;
768 dlen
= MIN(dlen
, len
);
770 while (boff
>= HAMMER_BUFSIZE
) {
771 boff
-= HAMMER_BUFSIZE
;
772 roff
+= HAMMER_BUFSIZE
;
776 * boff - relative offset in disk buffer (not aligned)
777 * roff - base offset of disk buffer (not aligned)
778 * dlen - amount of data we think we can copy
780 * hread only reads 16K aligned buffers, check for
781 * a length overflow and truncate dlen appropriately.
783 if ((roff
& ~HAMMER_BUFMASK64
) != ((roff
+ boff
+ dlen
- 1) & ~HAMMER_BUFMASK64
))
784 dlen
= HAMMER_BUFSIZE
- ((boff
+ roff
) & HAMMER_BUFMASK
);
785 char *data
= hread(hfs
, roff
);
788 bcopy(data
+ boff
, buf
, dlen
);
796 return (off
- startoff
);
803 boot2_hammer_init(void)
805 hammer_volume_ondisk_t volhead
;
807 volhead
= hread(&hfs
, HAMMER_ZONE_ENCODE(1, 0));
810 if (volhead
->vol_signature
!= HAMMER_FSBUF_VOLUME
)
812 hfs
.root
= volhead
->vol0_btree_root
;
813 hfs
.buf_beg
= volhead
->vol_buf_beg
;
818 boot2_hammer_lookup(const char *path
)
820 ino_t ino
= hlookup(&hfs
, path
);
831 boot2_hammer_read(boot2_ino_t ino
, void *buf
, size_t len
)
833 ssize_t rlen
= hreadf(&hfs
, ino
, fs_off
, len
, buf
);
839 const struct boot2_fsapi boot2_hammer_api
= {
840 .fsinit
= boot2_hammer_init
,
841 .fslookup
= boot2_hammer_lookup
,
842 .fsread
= boot2_hammer_read
849 hinit(struct hfs
*hfs
)
854 for (int i
= 0; i
< NUMCACHE
; i
++) {
855 hfs
->cache
[i
].data
= malloc(HAMMER_BUFSIZE
);
856 hfs
->cache
[i
].off
= -1; // invalid
857 hfs
->cache
[i
].use
= 0;
860 if (hfs
->cache
[i
].data
== NULL
)
861 printf("malloc failed\n");
865 hfs
->last_dir_ino
= -1;
867 hammer_volume_ondisk_t volhead
= hread(hfs
, HAMMER_ZONE_ENCODE(1, 0));
871 printf("signature: %svalid\n",
872 volhead
->vol_signature
!= HAMMER_FSBUF_VOLUME
?
875 printf("name: %s\n", volhead
->vol_name
);
879 if (volhead
== NULL
|| volhead
->vol_signature
!= HAMMER_FSBUF_VOLUME
) {
880 for (int i
= 0; i
< NUMCACHE
; i
++) {
881 free(hfs
->cache
[i
].data
);
882 hfs
->cache
[i
].data
= NULL
;
888 hfs
->root
= volhead
->vol0_btree_root
;
889 hfs
->buf_beg
= volhead
->vol_buf_beg
;
895 hclose(struct hfs
*hfs
)
900 for (int i
= 0; i
< NUMCACHE
; i
++) {
901 if (hfs
->cache
[i
].data
) {
902 free(hfs
->cache
[i
].data
);
903 hfs
->cache
[i
].data
= NULL
;
917 hammer_open(const char *path
, struct open_file
*f
)
919 struct hfile
*hf
= malloc(sizeof(*hf
));
921 bzero(hf
, sizeof(*hf
));
926 int rv
= hinit(&hf
->hfs
);
934 printf("hammer_open %s %p %ld\n", path
, f
);
937 hf
->ino
= hlookup(&hf
->hfs
, path
);
942 if (hstat(&hf
->hfs
, hf
->ino
, &st
) == -1)
944 hf
->fsize
= st
.st_size
;
947 printf(" %ld\n", (long)hf
->fsize
);
954 printf("hammer_open fail\n");
963 hammer_close(struct open_file
*f
)
965 struct hfile
*hf
= f
->f_fsdata
;
976 hammer_read(struct open_file
*f
, void *buf
, size_t len
, size_t *resid
)
978 struct hfile
*hf
= f
->f_fsdata
;
981 printf("hammer_read %p %ld %ld\n", f
, f
->f_offset
, len
);
984 if (f
->f_offset
>= hf
->fsize
)
988 if (f
->f_offset
+ len
> hf
->fsize
)
989 maxlen
= hf
->fsize
- f
->f_offset
;
991 ssize_t rlen
= hreadf(&hf
->hfs
, hf
->ino
, f
->f_offset
, maxlen
, buf
);
1002 hammer_seek(struct open_file
*f
, off_t offset
, int whence
)
1004 struct hfile
*hf
= f
->f_fsdata
;
1008 f
->f_offset
= offset
;
1011 f
->f_offset
+= offset
;
1014 f
->f_offset
= hf
->fsize
- offset
;
1019 return (f
->f_offset
);
1023 hammer_stat(struct open_file
*f
, struct stat
*st
)
1025 struct hfile
*hf
= f
->f_fsdata
;
1027 return (hstat(&hf
->hfs
, hf
->ino
, st
));
1031 hammer_readdir(struct open_file
*f
, struct dirent
*d
)
1033 struct hfile
*hf
= f
->f_fsdata
;
1035 int64_t off
= f
->f_offset
;
1036 int rv
= hreaddir(&hf
->hfs
, hf
->ino
, &off
, d
);
1042 struct fs_ops hammer_fsops
= {
1056 main(int argc
, char **argv
)
1059 fprintf(stderr
, "usage: hammerread <dev>\n");
1064 hfs
.fd
= open(argv
[1], O_RDONLY
);
1066 err(1, "unable to open %s", argv
[1]);
1068 if (hinit(&hfs
) == -1)
1069 err(1, "invalid hammerfs");
1071 for (int i
= 2; i
< argc
; i
++) {
1072 ino_t ino
= hlookup(&hfs
, argv
[i
]);
1073 if (ino
== (ino_t
)-1) {
1074 warn("hlookup %s", argv
[i
]);
1079 if (hstat(&hfs
, ino
, &st
)) {
1080 warn("hstat %s", argv
[i
]);
1084 printf("%s %d/%d %o %lld\n",
1086 st
.st_uid
, st
.st_gid
,
1087 st
.st_mode
, st
.st_size
);
1089 if (S_ISDIR(st
.st_mode
)) {
1092 while (hreaddir(&hfs
, ino
, &off
, &de
) == 0) {
1093 printf("%s %d %llx\n",
1094 de
.d_name
, de
.d_type
, de
.d_ino
);
1096 } else if (S_ISREG(st
.st_mode
)) {
1097 char *buf
= malloc(100000);
1099 while (off
< st
.st_size
) {
1100 int64_t len
= MIN(100000, st
.st_size
- off
);
1101 int64_t rl
= hreadf(&hfs
, ino
, off
, len
, buf
);
1102 fwrite(buf
, rl
, 1, stdout
);