]>
git.wh0rd.org - dump.git/blob - restore/symtab.c
2 * Ported to Linux's Second Extended File System as part of the
3 * dump and restore backup suit
4 * Remy Card <card@Linux.EU.Org>, 1994-1997
5 * Stelian Pop <stelian@popies.net>, 1999-2000
6 * Stelian Pop <stelian@popies.net> - AlcĂ´ve <www.alcove.com>, 2000-2002
10 * Copyright (c) 1983, 1993
11 * The Regents of the University of California. All rights reserved.
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions
16 * 1. Redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer.
18 * 2. Redistributions in binary form must reproduce the above copyright
19 * notice, this list of conditions and the following disclaimer in the
20 * documentation and/or other materials provided with the distribution.
21 * 3. Neither the name of the University nor the names of its contributors
22 * may be used to endorse or promote products derived from this software
23 * without specific prior written permission.
25 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
39 static const char rcsid
[] =
40 "$Id: symtab.c,v 1.27 2005/07/07 09:16:08 stelian Exp $";
44 * These routines maintain the symbol table which tracks the state
45 * of the file system being restored. They provide lookup by either
46 * name or inode number. They also provide for creation, deletion,
47 * and renaming of entries. Because of the dynamic nature of pathnames,
48 * names should not be saved, but always constructed just before they
49 * are needed, by calling "myname".
53 #include <compatlfs.h>
54 #include <sys/param.h>
60 #ifdef HAVE_EXT2FS_EXT2_FS_H
61 #include <ext2fs/ext2_fs.h>
63 #include <linux/ext2_fs.h>
65 #include <bsdcompat.h>
68 #include <sys/fcntl.h>
69 #include <bsdcompat.h>
71 #include <ufs/ufs/dinode.h>
73 #endif /* __linux__ */
76 #include <compaterr.h>
84 #include <ext2fs/ext2fs.h>
91 * The following variables define the inode symbol table.
92 * The primary hash table is dynamically allocated based on
93 * the number of inodes in the file system (maxino), scaled by
94 * HASHFACTOR. The variable "entry" points to the hash table;
95 * the variable "entrytblsize" indicates its size (in entries).
98 static struct entry
**entry
;
99 static long entrytblsize
;
101 static void addino
__P((dump_ino_t
, struct entry
*));
102 static struct entry
*lookupparent
__P((char *));
103 static void removeentry
__P((struct entry
*));
104 static int dir_hash
__P((char *));
107 * Returns a hash given a file name
112 unsigned long hash0
= 0x12a3fe2d, hash1
= 0x37abe8f9;
113 int len
= strlen(name
);
116 unsigned long hash
= hash1
+ (hash0
^ (*name
++ * 7152373));
117 if (hash
& 0x80000000) hash
-= 0x7fffffff;
121 return hash0
% dirhash_size
;
125 * Look up an entry by inode number
128 lookupino(dump_ino_t inum
)
132 if (inum
< WINO
|| inum
>= maxino
)
134 for (ep
= entry
[inum
% entrytblsize
]; ep
!= NULL
; ep
= ep
->e_next
)
135 if (ep
->e_ino
== inum
)
141 * Add an entry into the entry table
144 addino(dump_ino_t inum
, struct entry
*np
)
148 if (inum
< WINO
|| inum
>= maxino
)
149 panic("addino: out of range %d\n", inum
);
150 epp
= &entry
[inum
% entrytblsize
];
155 for (np
= np
->e_next
; np
!= NULL
; np
= np
->e_next
)
156 if (np
->e_ino
== inum
)
157 badentry(np
, "duplicate inum");
161 * Delete an entry from the entry table
164 deleteino(dump_ino_t inum
)
169 if (inum
< WINO
|| inum
>= maxino
)
170 panic("deleteino: out of range %d\n", inum
);
171 prev
= &entry
[inum
% entrytblsize
];
172 for (next
= *prev
; next
!= NULL
; next
= next
->e_next
) {
173 if (next
->e_ino
== inum
) {
175 *prev
= next
->e_next
;
178 prev
= &next
->e_next
;
180 panic("deleteino: %d not found\n", inum
);
184 * Look up an entry by name
187 lookupname(char *name
)
189 struct entry
*ep
, *oldep
;
191 char buf
[MAXPATHLEN
];
193 ep
= lookupino(ROOTINO
);
204 for (np
= buf
; *cp
!= '/' && *cp
!= '\0' &&
205 np
< &buf
[sizeof(buf
)]; )
207 if (np
== &buf
[sizeof(buf
)])
213 if (ep
->e_entries
!= NULL
) {
215 ep
= ep
->e_entries
[dir_hash(buf
)];
216 for ( ; ep
!= NULL
; ep
= ep
->e_sibling
)
217 if (strcmp(ep
->e_name
, buf
) == 0)
220 /* search all hash lists for renamed inodes */
223 for (j
= 0; j
< dirhash_size
; j
++) {
224 ep
= oldep
->e_entries
[j
];
225 for ( ; ep
!= NULL
; ep
= ep
->e_sibling
)
226 if (strcmp(ep
->e_name
, buf
) == 0)
243 * Look up the parent of a pathname
245 static struct entry
*
246 lookupparent(char *name
)
251 tailindex
= strrchr(name
, '/');
252 if (tailindex
== NULL
)
255 ep
= lookupname(name
);
259 if (ep
->e_type
!= NODE
)
260 panic("%s is not a directory\n", name
);
265 * Determine the current pathname of a node or leaf
268 myname(struct entry
*ep
)
271 static char namebuf
[MAXPATHLEN
];
273 for (cp
= &namebuf
[MAXPATHLEN
- 2]; cp
> &namebuf
[ep
->e_namlen
]; ) {
275 memmove(cp
, ep
->e_name
, (size_t)ep
->e_namlen
);
276 if (ep
== lookupino(ROOTINO
))
281 panic("%s: pathname too long\n", cp
);
286 * Unused symbol table entries are linked together on a free list
287 * headed by the following pointer.
289 static struct entry
*freelist
= NULL
;
292 * add an entry to the symbol table
295 addentry(char *name
, dump_ino_t inum
, int type
)
297 struct entry
*np
, *ep
;
299 if (freelist
!= NULL
) {
301 freelist
= np
->e_next
;
302 memset(np
, 0, sizeof(struct entry
));
304 np
= (struct entry
*)calloc(1, sizeof(struct entry
));
306 errx(1, "no memory to extend symbol table");
308 np
->e_type
= type
& ~LINK
;
310 np
->e_entries
= calloc(1, dirhash_size
* sizeof(struct entry
*));
311 if (np
->e_entries
== NULL
)
312 panic("unable to allocate directory entries\n");
314 ep
= lookupparent(name
);
316 if (inum
!= ROOTINO
|| lookupino(ROOTINO
) != NULL
)
317 panic("bad name to addentry %s\n", name
);
318 np
->e_name
= savename(name
);
319 np
->e_namlen
= strlen(name
);
324 np
->e_name
= savename(strrchr(name
, '/') + 1);
325 np
->e_namlen
= strlen(np
->e_name
);
327 np
->e_sibling
= ep
->e_entries
[dir_hash(np
->e_name
)];
328 ep
->e_entries
[dir_hash(np
->e_name
)] = np
;
330 ep
= lookupino(inum
);
332 panic("link to non-existent name\n");
334 np
->e_links
= ep
->e_links
;
336 } else if (inum
!= 0) {
337 if (lookupino(inum
) != NULL
)
338 panic("duplicate entry\n");
345 * delete an entry from the symbol table
348 freeentry(struct entry
*ep
)
353 if (ep
->e_flags
!= REMOVED
)
354 badentry(ep
, "not marked REMOVED");
355 if (ep
->e_type
== NODE
) {
356 if (ep
->e_links
!= NULL
)
357 badentry(ep
, "freeing referenced directory");
358 if (ep
->e_entries
!= NULL
) {
360 for (i
= 0; i
< dirhash_size
; i
++) {
361 if (ep
->e_entries
[i
] != NULL
)
362 badentry(ep
, "freeing non-empty directory");
366 if (ep
->e_ino
!= 0) {
367 np
= lookupino(ep
->e_ino
);
369 badentry(ep
, "lookupino failed");
373 if (ep
->e_links
!= NULL
)
374 addino(inum
, ep
->e_links
);
376 for (; np
!= NULL
; np
= np
->e_links
) {
377 if (np
->e_links
== ep
) {
378 np
->e_links
= ep
->e_links
;
383 badentry(ep
, "link not found");
387 freename(ep
->e_name
);
388 ep
->e_next
= freelist
;
393 * Relocate an entry in the tree structure
396 moveentry(struct entry
*ep
, char *newname
)
401 np
= lookupparent(newname
);
403 badentry(ep
, "cannot move ROOT");
404 if (np
!= ep
->e_parent
) {
407 ep
->e_sibling
= np
->e_entries
[dir_hash(ep
->e_name
)];
408 np
->e_entries
[dir_hash(ep
->e_name
)] = ep
;
410 cp
= strrchr(newname
, '/') + 1;
411 freename(ep
->e_name
);
412 ep
->e_name
= savename(cp
);
413 ep
->e_namlen
= strlen(cp
);
414 if (strcmp(gentempname(ep
), ep
->e_name
) == 0)
415 ep
->e_flags
|= TMPNAME
;
417 ep
->e_flags
&= ~TMPNAME
;
421 * Remove an entry in the tree structure
424 removeentry(struct entry
*ep
)
426 struct entry
*np
= ep
->e_parent
;
427 struct entry
*entry
= np
->e_entries
[dir_hash(ep
->e_name
)];
430 np
->e_entries
[dir_hash(ep
->e_name
)] = ep
->e_sibling
;
432 for (np
= entry
; np
!= NULL
; np
= np
->e_sibling
) {
433 if (np
->e_sibling
== ep
) {
434 np
->e_sibling
= ep
->e_sibling
;
440 /* search all hash lists for renamed inodes */
442 for (j
= 0; j
< dirhash_size
; j
++) {
444 entry
= np
->e_entries
[j
];
446 np
->e_entries
[j
] = ep
->e_sibling
;
450 for (np
= entry
; np
!= NULL
; np
= np
->e_sibling
) {
451 if (np
->e_sibling
== ep
) {
452 np
->e_sibling
= ep
->e_sibling
;
458 badentry(ep
, "cannot find entry in parent list");
464 * Table of unused string entries, sorted by length.
466 * Entries are allocated in STRTBLINCR sized pieces so that names
467 * of similar lengths can use the same entry. The value of STRTBLINCR
468 * is chosen so that every entry has at least enough space to hold
469 * a "struct strtbl" header. Thus every entry can be linked onto an
470 * appropriate free list.
472 * NB. The macro "allocsize" below assumes that "struct strhdr"
473 * has a size that is a power of two.
479 #define STRTBLINCR (sizeof(struct strhdr))
480 #define allocsize(size) (((size) + 1 + STRTBLINCR - 1) & ~(STRTBLINCR - 1))
482 static struct strhdr strtblhdr
[allocsize(MAXNAMLEN
) / STRTBLINCR
];
485 * Allocate space for a name. It first looks to see if it already
486 * has an appropriate sized entry, and if not allocates a new one.
498 np
= strtblhdr
[len
/ STRTBLINCR
].next
;
500 strtblhdr
[len
/ STRTBLINCR
].next
= np
->next
;
503 cp
= malloc((unsigned)allocsize(len
));
505 errx(1, "no space for string table");
507 (void) strcpy(cp
, name
);
512 * Free space for a name. The resulting entry is linked onto the
513 * appropriate free list.
518 struct strhdr
*tp
, *np
;
520 tp
= &strtblhdr
[strlen(name
) / STRTBLINCR
];
521 np
= (struct strhdr
*)name
;
527 * Useful quantities placed at the end of a dumped symbol table.
529 struct symtableheader
{
533 int32_t entrytblsize
;
542 * dump a snapshot of the symbol table
545 dumpsymtable(char *filename
, long checkpt
)
547 struct entry
*ep
, *tep
;
549 struct entry temp
, *tentry
;
550 long mynum
= 1, stroff
= 0, hashoff
= 0;
552 struct symtableheader hdr
;
553 struct entry
**temphash
;
555 Vprintf(stdout
, "Check pointing the restore\n");
558 if ((fd
= FOPEN(filename
, "w")) == NULL
) {
560 panic("cannot create save file %s for symbol table\n",
565 * Assign indices to each entry
566 * Write out the string entries
568 for (i
= WINO
; i
<= maxino
; i
++) {
569 for (ep
= lookupino(i
); ep
!= NULL
; ep
= ep
->e_links
) {
570 ep
->e_index
= mynum
++;
571 (void) fwrite(ep
->e_name
, sizeof(char),
572 (int)allocsize(ep
->e_namlen
), fd
);
576 * Write out e_entries tables
578 temphash
= calloc(1, dirhash_size
* sizeof(struct entry
*));
579 if (temphash
== NULL
)
580 errx(1, "no memory for saving hashtable");
581 for (i
= WINO
; i
<= maxino
; i
++) {
582 for (ep
= lookupino(i
); ep
!= NULL
; ep
= ep
->e_links
) {
583 if (ep
->e_entries
!= NULL
) {
585 memcpy(temphash
, ep
->e_entries
, dirhash_size
* sizeof(struct entry
*));
586 for (j
= 0; j
< dirhash_size
; j
++) {
588 temphash
[j
] = (struct entry
*)ep
->e_entries
[j
]->e_index
;
590 fwrite(temphash
, dirhash_size
, sizeof(struct entry
*), fd
);
597 * Convert pointers to indexes, and output
602 for (i
= WINO
; i
<= maxino
; i
++) {
603 for (ep
= lookupino(i
); ep
!= NULL
; ep
= ep
->e_links
) {
604 memmove(tep
, ep
, sizeof(struct entry
));
605 tep
->e_name
= (char *)stroff
;
606 stroff
+= allocsize(ep
->e_namlen
);
607 tep
->e_parent
= (struct entry
*)ep
->e_parent
->e_index
;
608 if (ep
->e_links
!= NULL
)
610 (struct entry
*)ep
->e_links
->e_index
;
611 if (ep
->e_sibling
!= NULL
)
613 (struct entry
*)ep
->e_sibling
->e_index
;
614 if (ep
->e_entries
!= NULL
) {
615 tep
->e_entries
= (struct entry
**)hashoff
;
616 hashoff
+= dirhash_size
* sizeof(struct entry
*);
618 if (ep
->e_next
!= NULL
)
620 (struct entry
*)ep
->e_next
->e_index
;
621 (void) fwrite((char *)tep
, sizeof(struct entry
), 1, fd
);
625 * Convert entry pointers to indexes, and output
627 for (i
= 0; (long)i
< entrytblsize
; i
++) {
628 if (entry
[i
] == NULL
)
631 tentry
= (struct entry
*)entry
[i
]->e_index
;
632 (void) fwrite((char *)&tentry
, sizeof(struct entry
*), 1, fd
);
636 hdr
.entrytblsize
= entrytblsize
;
637 hdr
.stringsize
= stroff
;
638 hdr
.hashsize
= hashoff
;
639 hdr
.dumptime
= dumptime
;
640 hdr
.dumpdate
= dumpdate
;
643 (void) fwrite((char *)&hdr
, sizeof(struct symtableheader
), 1, fd
);
646 panic("output error to file %s writing symbol table\n",
653 * Initialize a symbol table from a file
656 initsymtable(char *filename
)
661 struct entry
*baseep
, *lep
;
662 struct symtableheader hdr
;
667 Vprintf(stdout
, "Initialize symbol table.\n");
668 if (filename
== NULL
) {
669 entrytblsize
= maxino
/ HASHFACTOR
;
670 entry
= (struct entry
**)
671 calloc((unsigned)entrytblsize
, sizeof(struct entry
*));
672 if (entry
== (struct entry
**)NULL
)
673 errx(1, "no memory for entry table");
674 ep
= addentry(".", ROOTINO
, NODE
);
678 if ((fd
= OPEN(filename
, O_RDONLY
, 0)) < 0) {
680 errx(1, "cannot open symbol table file %s", filename
);
682 if (FSTAT(fd
, &stbuf
) < 0) {
684 errx(1, "cannot stat symbol table file %s", filename
);
686 tblsize
= stbuf
.st_size
- sizeof(struct symtableheader
);
687 base
= calloc(sizeof(char), (unsigned)tblsize
);
689 errx(1, "cannot allocate space for symbol table");
690 if (read(fd
, base
, (int)tblsize
) < 0 ||
691 read(fd
, (char *)&hdr
, sizeof(struct symtableheader
)) < 0) {
693 errx(1, "cannot read symbol table file %s", filename
);
698 * For normal continuation, insure that we are using
699 * the next incremental tape
701 if (hdr
.dumpdate
!= dumptime
)
702 errx(1, "Incremental tape too %s",
703 (hdr
.dumpdate
< dumptime
) ? "low" : "high");
707 * For restart, insure that we are using the same tape
709 curfile
.action
= SKIP
;
710 dumptime
= hdr
.dumptime
;
711 dumpdate
= hdr
.dumpdate
;
714 newtapebuf(hdr
.ntrec
);
718 panic("initsymtable called from command %c\n", command
);
721 if (hdr
.maxino
> maxino
) {
722 resizemaps(maxino
, hdr
.maxino
);
725 entrytblsize
= hdr
.entrytblsize
;
726 entry
= (struct entry
**)
727 (base
+ tblsize
- (entrytblsize
* sizeof(struct entry
*)));
728 baseep
= (struct entry
*)(base
+ hdr
.stringsize
+ hdr
.hashsize
- sizeof(struct entry
));
729 lep
= (struct entry
*)entry
;
730 for (i
= 0; i
< entrytblsize
; i
++) {
731 if (entry
[i
] == NULL
)
733 entry
[i
] = &baseep
[(long)entry
[i
]];
735 for (ep
= &baseep
[1]; ep
< lep
; ep
++) {
736 ep
->e_name
= base
+ (long)ep
->e_name
;
737 ep
->e_parent
= &baseep
[(long)ep
->e_parent
];
738 if (ep
->e_sibling
!= NULL
)
739 ep
->e_sibling
= &baseep
[(long)ep
->e_sibling
];
740 if (ep
->e_links
!= NULL
)
741 ep
->e_links
= &baseep
[(long)ep
->e_links
];
742 if (ep
->e_type
== NODE
) {
744 ep
->e_entries
= (struct entry
**)(base
+ hdr
.stringsize
+ (long)ep
->e_entries
);
745 for (i
= 0; i
< dirhash_size
; i
++) {
746 if (ep
->e_entries
[i
])
747 ep
->e_entries
[i
] = &baseep
[(long)ep
->e_entries
[i
]];
751 ep
->e_entries
= NULL
;
752 if (ep
->e_next
!= NULL
)
753 ep
->e_next
= &baseep
[(long)ep
->e_next
];