2 * Copyright (c) 2010 The DragonFly Project. All rights reserved.
4 * This code is derived from software contributed to The DragonFly Project
5 * by Matthew Dillon <dillon@backplane.com>
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * 3. Neither the name of The DragonFly Project nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific, prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
31 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
38 struct recover_dict
*next
;
39 struct recover_dict
*parent
;
48 #define DICTF_MADEDIR 0x01
49 #define DICTF_MADEFILE 0x02
50 #define DICTF_PARENT 0x04 /* parent attached for real */
51 #define DICTF_TRAVERSED 0x80
53 static void recover_top(char *ptr
, hammer_off_t offset
);
54 static void recover_elm(hammer_btree_leaf_elm_t leaf
);
55 static struct recover_dict
*get_dict(int64_t obj_id
, uint16_t pfs_id
);
56 static char *recover_path(struct recover_dict
*dict
);
57 static void sanitize_string(char *str
);
59 static const char *TargetDir
;
60 static int CachedFd
= -1;
61 static char *CachedPath
;
64 * XXX There is a hidden bug here while iterating zone-2 offset as
65 * shown in an example below.
67 * If a volume was once used as HAMMER filesystem which consists of
68 * multiple volumes whose usage has reached beyond the first volume,
69 * and then later re-formatted only using 1 volume, hammer recover is
70 * likely to hit assertion in get_buffer() due to having access to
71 * invalid volume (vol1,2,...) from old filesystem data.
73 * |-----vol0-----|-----vol1-----|-----vol2-----| old filesystem
74 * <-----------------------> used by old filesystem
76 * |-----vol0-----| new filesystem
77 * <-----> used by new filesystem
78 * <-------> unused, invalid data from old filesystem
79 * <-> B-Tree nodes likely to point to vol1
83 hammer_cmd_recover(const char *target_dir
)
85 struct buffer_info
*data_buffer
;
86 struct volume_info
*volume
;
92 TargetDir
= target_dir
;
94 if (mkdir(TargetDir
, 0777) == -1) {
95 if (errno
!= EEXIST
) {
101 printf("Running raw scan of HAMMER image, recovering to %s\n",
105 for (i
= 0; i
< HAMMER_MAX_VOLUMES
; i
++) {
106 volume
= get_volume(i
);
109 printf("Scanning volume %d size %s\n",
110 volume
->vol_no
, sizetostr(volume
->size
));
111 off
= HAMMER_ENCODE_RAW_BUFFER(volume
->vol_no
, 0);
112 off_end
= off
+ HAMMER_VOL_BUF_SIZE(volume
->ondisk
);
115 * It should somehow implement reverse mapping from
116 * zone-2 to zone-X, so the command doesn't just try
117 * every zone-2 offset assuming it's a B-Tree node.
118 * Since we know most big-blocks are not for zone-8,
119 * we don't want to spend extra I/O for other zones
120 * as well as possible misinterpretation of nodes.
122 while (off
< off_end
) {
123 ptr
= get_buffer_data(off
, &data_buffer
, 0);
125 recover_top(ptr
, off
);
126 off
+= HAMMER_BUFSIZE
;
129 rel_buffer(data_buffer
);
140 * Top level recovery processor. Assume the data is a B-Tree node.
141 * If the CRC is good we attempt to process the node, building the
142 * object space and creating the dictionary as we go.
145 recover_top(char *ptr
, hammer_off_t offset
)
147 hammer_node_ondisk_t node
;
148 hammer_btree_elm_t elm
;
152 char buf
[HAMMER_BTREE_LEAF_ELMS
+ 1];
154 for (node
= (void *)ptr
; (char *)node
< ptr
+ HAMMER_BUFSIZE
; ++node
) {
155 isnode
= hammer_crc_test_btree(node
);
156 maxcount
= hammer_node_max_elements(node
->type
);
159 for (i
= 0; i
< node
->count
&& i
< maxcount
; ++i
)
160 buf
[i
] = hammer_elm_btype(&node
->elms
[i
]);
162 if (!isnode
&& DebugOpt
> 1)
163 printf("%016jx -\n", offset
);
165 printf("%016jx %c %d %s\n",
166 offset
, node
->type
, node
->count
, buf
);
168 offset
+= sizeof(*node
);
170 if (isnode
&& node
->type
== HAMMER_BTREE_TYPE_LEAF
) {
171 for (i
= 0; i
< node
->count
&& i
< maxcount
; ++i
) {
172 elm
= &node
->elms
[i
];
173 if (elm
->base
.btype
== HAMMER_BTREE_TYPE_RECORD
)
174 recover_elm(&elm
->leaf
);
181 recover_elm(hammer_btree_leaf_elm_t leaf
)
183 struct buffer_info
*data_buffer
= NULL
;
184 struct recover_dict
*dict
;
185 struct recover_dict
*dict2
;
186 hammer_data_ondisk_t ondisk
;
187 hammer_off_t data_offset
;
201 * Ignore deleted records
205 if ((data_offset
= leaf
->data_offset
) != 0)
206 ondisk
= get_buffer_data(data_offset
, &data_buffer
, 0);
212 len
= leaf
->data_len
;
213 chunk
= HAMMER_BUFSIZE
- ((int)data_offset
& HAMMER_BUFMASK
);
217 if (len
< 0 || len
> HAMMER_XBUFSIZE
|| len
> chunk
)
220 pfs_id
= lo_to_pfs(leaf
->base
.localization
);
223 * Note that meaning of leaf->base.obj_id differs depending
224 * on record type. For a direntry, leaf->base.obj_id points
225 * to its parent inode that this entry is a part of, but not
226 * its corresponding inode.
228 dict
= get_dict(leaf
->base
.obj_id
, pfs_id
);
230 switch(leaf
->base
.rec_type
) {
231 case HAMMER_RECTYPE_INODE
:
233 * We found an inode which also tells us where the file
234 * or directory is in the directory hierarchy.
237 printf("inode %016jx:%05d found\n",
238 (uintmax_t)leaf
->base
.obj_id
, pfs_id
);
240 path1
= recover_path(dict
);
243 * Attach the inode to its parent. This isn't strictly
244 * necessary because the information is also in the
245 * directory entries, but if we do not find the directory
246 * entry this ensures that the files will still be
247 * reasonably well organized in their proper directories.
249 if ((dict
->flags
& DICTF_PARENT
) == 0 &&
250 dict
->obj_id
!= HAMMER_OBJID_ROOT
&&
251 ondisk
->inode
.parent_obj_id
!= 0) {
252 dict
->flags
|= DICTF_PARENT
;
253 dict
->parent
= get_dict(ondisk
->inode
.parent_obj_id
,
256 (dict
->parent
->flags
& DICTF_MADEDIR
) == 0) {
257 dict
->parent
->flags
|= DICTF_MADEDIR
;
258 path2
= recover_path(dict
->parent
);
259 printf("mkdir %s\n", path2
);
265 if (dict
->obj_type
== 0)
266 dict
->obj_type
= ondisk
->inode
.obj_type
;
267 dict
->size
= ondisk
->inode
.size
;
268 path2
= recover_path(dict
);
270 if (lstat(path1
, &st
) == 0) {
271 if (ondisk
->inode
.obj_type
== HAMMER_OBJTYPE_REGFILE
) {
272 truncate(path1
, dict
->size
);
273 /* chmod(path1, 0666); */
275 if (strcmp(path1
, path2
)) {
276 printf("Rename %s -> %s\n", path1
, path2
);
277 rename(path1
, path2
);
279 } else if (ondisk
->inode
.obj_type
== HAMMER_OBJTYPE_REGFILE
) {
280 printf("mkinode (file) %s\n", path2
);
281 fd
= open(path2
, O_RDWR
|O_CREAT
, 0666);
284 } else if (ondisk
->inode
.obj_type
== HAMMER_OBJTYPE_DIRECTORY
) {
285 printf("mkinode (dir) %s\n", path2
);
287 dict
->flags
|= DICTF_MADEDIR
;
292 case HAMMER_RECTYPE_DATA
:
296 if (leaf
->base
.obj_id
== 0)
299 printf("inode %016jx:%05d data %016jx,%d\n",
300 (uintmax_t)leaf
->base
.obj_id
,
302 (uintmax_t)leaf
->base
.key
- len
,
307 * Update the dictionary entry
309 if (dict
->obj_type
== 0)
310 dict
->obj_type
= HAMMER_OBJTYPE_REGFILE
;
313 * If the parent directory has not been created we
314 * have to create it (typically a PFS%05d)
317 (dict
->parent
->flags
& DICTF_MADEDIR
) == 0) {
318 dict
->parent
->flags
|= DICTF_MADEDIR
;
319 path2
= recover_path(dict
->parent
);
320 printf("mkdir %s\n", path2
);
327 * Create the file if necessary, report file creations
329 path1
= recover_path(dict
);
330 if (CachedPath
&& strcmp(CachedPath
, path1
) == 0) {
333 fd
= open(path1
, O_CREAT
|O_RDWR
, 0666);
336 printf("Unable to create %s: %s\n",
337 path1
, strerror(errno
));
341 if ((dict
->flags
& DICTF_MADEFILE
) == 0) {
342 dict
->flags
|= DICTF_MADEFILE
;
343 printf("mkfile %s\n", path1
);
347 * And write the record. A HAMMER data block is aligned
348 * and may contain trailing zeros after the file EOF. The
349 * inode record is required to get the actual file size.
351 * However, when the inode record is not available
352 * we can do a sparse write and that will get it right
353 * most of the time even if the inode record is never
356 file_offset
= (int64_t)leaf
->base
.key
- len
;
357 lseek(fd
, (off_t
)file_offset
, SEEK_SET
);
359 if (dict
->size
== -1) {
360 for (zfill
= chunk
- 1; zfill
>= 0; --zfill
) {
361 if (((char *)ondisk
)[zfill
])
370 write(fd
, ondisk
, zfill
);
372 lseek(fd
, chunk
- zfill
, SEEK_CUR
);
375 data_offset
+= chunk
;
376 file_offset
+= chunk
;
377 ondisk
= get_buffer_data(data_offset
, &data_buffer
, 0);
380 chunk
= HAMMER_BUFSIZE
-
381 ((int)data_offset
& HAMMER_BUFMASK
);
385 if (dict
->size
>= 0 && file_offset
> dict
->size
) {
386 ftruncate(fd
, dict
->size
);
387 /* fchmod(fd, 0666); */
390 if (fd
== CachedFd
) {
392 } else if (CachedPath
) {
402 case HAMMER_RECTYPE_DIRENTRY
:
403 nlen
= len
- HAMMER_ENTRY_NAME_OFF
;
404 if ((int)nlen
< 0) /* illegal length */
406 if (ondisk
->entry
.obj_id
== 0 ||
407 ondisk
->entry
.obj_id
== HAMMER_OBJID_ROOT
)
409 name
= malloc(nlen
+ 1);
410 bcopy(ondisk
->entry
.name
, name
, nlen
);
412 sanitize_string(name
);
415 printf("dir %016jx:%05d entry %016jx \"%s\"\n",
416 (uintmax_t)leaf
->base
.obj_id
,
418 (uintmax_t)ondisk
->entry
.obj_id
,
423 * We can't deal with hardlinks so if the object already
424 * has a name assigned to it we just keep using that name.
426 dict2
= get_dict(ondisk
->entry
.obj_id
, pfs_id
);
427 path1
= recover_path(dict2
);
429 if (dict2
->name
== NULL
)
435 * Attach dict2 to its directory (dict), create the
436 * directory (dict) if necessary. We must ensure
437 * that the directory entry exists in order to be
438 * able to properly rename() the file without creating
439 * a namespace conflict.
441 if ((dict2
->flags
& DICTF_PARENT
) == 0) {
442 dict2
->flags
|= DICTF_PARENT
;
443 dict2
->parent
= dict
;
444 if ((dict
->flags
& DICTF_MADEDIR
) == 0) {
445 dict
->flags
|= DICTF_MADEDIR
;
446 path2
= recover_path(dict
);
447 printf("mkdir %s\n", path2
);
453 path2
= recover_path(dict2
);
454 if (strcmp(path1
, path2
) != 0 && lstat(path1
, &st
) == 0) {
455 printf("Rename %s -> %s\n", path1
, path2
);
456 rename(path1
, path2
);
463 * Ignore any other record types
468 rel_buffer(data_buffer
);
471 #define RD_HSIZE 32768
472 #define RD_HMASK (RD_HSIZE - 1)
474 struct recover_dict
*RDHash
[RD_HSIZE
];
477 struct recover_dict
*
478 get_dict(int64_t obj_id
, uint16_t pfs_id
)
480 struct recover_dict
*dict
;
486 i
= crc32(&obj_id
, sizeof(obj_id
)) & RD_HMASK
;
487 for (dict
= RDHash
[i
]; dict
; dict
= dict
->next
) {
488 if (dict
->obj_id
== obj_id
&&
489 dict
->pfs_id
== pfs_id
) {
494 dict
= malloc(sizeof(*dict
));
495 bzero(dict
, sizeof(*dict
));
496 dict
->obj_id
= obj_id
;
497 dict
->pfs_id
= pfs_id
;
498 dict
->next
= RDHash
[i
];
503 * Always connect dangling dictionary entries to object 1
504 * (the root of the PFS).
506 * DICTF_PARENT will not be set until we know what the
507 * real parent directory object is.
509 if (dict
->obj_id
!= HAMMER_OBJID_ROOT
)
510 dict
->parent
= get_dict(HAMMER_OBJID_ROOT
, pfs_id
);
516 enum { PI_FIGURE
, PI_LOAD
} state
;
523 static void recover_path_helper(struct recover_dict
*, struct path_info
*);
527 recover_path(struct recover_dict
*dict
)
529 struct path_info info
;
531 /* Find info.len first */
532 bzero(&info
, sizeof(info
));
533 info
.state
= PI_FIGURE
;
534 recover_path_helper(dict
, &info
);
536 /* Fill in the path */
537 info
.pfs_id
= dict
->pfs_id
;
538 info
.base
= malloc(info
.len
);
539 info
.next
= info
.base
;
540 info
.state
= PI_LOAD
;
541 recover_path_helper(dict
, &info
);
543 /* Return the path */
547 #define STRLEN_OBJID 22 /* "obj_0x%016jx" */
548 #define STRLEN_PFSID 8 /* "PFS%05d" */
552 recover_path_helper(struct recover_dict
*dict
, struct path_info
*info
)
555 * Calculate path element length
557 dict
->flags
|= DICTF_TRAVERSED
;
559 switch(info
->state
) {
561 if (dict
->obj_id
== HAMMER_OBJID_ROOT
)
562 info
->len
+= STRLEN_PFSID
;
564 info
->len
+= strlen(dict
->name
);
566 info
->len
+= STRLEN_OBJID
;
570 (dict
->parent
->flags
& DICTF_TRAVERSED
) == 0) {
571 recover_path_helper(dict
->parent
, info
);
573 info
->len
+= strlen(TargetDir
) + 1;
578 (dict
->parent
->flags
& DICTF_TRAVERSED
) == 0) {
579 recover_path_helper(dict
->parent
, info
);
581 strcpy(info
->next
, TargetDir
);
582 info
->next
+= strlen(info
->next
);
586 if (dict
->obj_id
== HAMMER_OBJID_ROOT
) {
587 snprintf(info
->next
, STRLEN_PFSID
+ 1,
588 "PFS%05d", info
->pfs_id
);
589 } else if (dict
->name
) {
590 strcpy(info
->next
, dict
->name
);
592 snprintf(info
->next
, STRLEN_OBJID
+ 1,
593 "obj_0x%016jx", (uintmax_t)dict
->obj_id
);
595 info
->next
+= strlen(info
->next
);
598 dict
->flags
&= ~DICTF_TRAVERSED
;
603 sanitize_string(char *str
)