2 * Copyright (c) 1983 Regents of the University of California.
3 * All rights reserved. The Berkeley software License Agreement
4 * specifies the terms and conditions for redistribution.
7 /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
8 /* All Rights Reserved */
11 * Copyright (c) 1996,1998,2001 by Sun Microsystems, Inc.
12 * All rights reserved.
16 * These routines maintain the symbol table which tracks the state
17 * of the file system being restored. They provide lookup by either
18 * name or inode number. They also provide for creation, deletion,
19 * and renaming of entries. Because of the dynamic nature of pathnames,
20 * names should not be saved, but always constructed just before they
21 * are needed, by calling "myname".
28 * The following variables define the inode symbol table.
29 * The primary hash table is dynamically allocated based on
30 * the number of inodes in the file system (maxino), scaled by
31 * HASHFACTOR. The variable "entry" points to the hash table;
32 * the variable "entrytblsize" indicates its size (in entries).
35 static struct entry
**entry
;
36 static uint_t entrytblsize
;
39 static void addino(ino_t
, struct entry
*);
40 static struct entry
*lookupparent(char *);
41 static void removeentry(struct entry
*);
44 static struct entry
*lookupparent();
45 static void removeentry();
49 * Look up an entry by inode number
57 if (inum
< ROOTINO
|| inum
>= maxino
)
59 for (ep
= entry
[inum
% entrytblsize
]; ep
!= NIL
; ep
= ep
->e_next
)
60 if (ep
->e_ino
== inum
)
66 * We now ignore inodes that are out of range. This
67 * allows us to attempt to proceed in the face of
68 * a corrupted archive, albeit with future complaints
69 * about failed inode lookups. We only complain once
70 * about range problems, to avoid irritating the user
71 * without providing any useful information. Failed
72 * lookups have the bogus name, which is useful, so
75 static int complained_about_range
= 0;
78 * Add an entry into the entry table
87 if (inum
< ROOTINO
|| inum
>= maxino
) {
88 if (!complained_about_range
) {
89 panic(gettext("%s: out of range %d\n"),
91 complained_about_range
= 1;
95 epp
= &entry
[inum
% entrytblsize
];
100 for (np
= np
->e_next
; np
!= NIL
; np
= np
->e_next
)
101 if (np
->e_ino
== inum
)
102 badentry(np
, gettext("duplicate inum"));
106 * Delete an entry from the entry table. We assume our caller
107 * arranges for the necessary memory reclamation, if needed.
116 if (inum
< ROOTINO
|| inum
>= maxino
) {
117 if (!complained_about_range
) {
118 panic(gettext("%s: out of range %d\n"),
120 complained_about_range
= 1;
125 prev
= &entry
[inum
% entrytblsize
];
126 for (next
= *prev
; next
!= NIL
; next
= next
->e_next
) {
127 if (next
->e_ino
== inum
) {
129 *prev
= next
->e_next
;
132 prev
= &next
->e_next
;
137 * Look up an entry by name.
138 * NOTE: this function handles "complex" pathnames (as returned
139 * by myname()) for extended file attributes. The name string
140 * provided to this function should be terminated with *two*
149 char buf
[MAXPATHLEN
];
151 if (strlen(name
) > (sizeof (buf
) - 1)) {
152 (void) fprintf(stderr
, gettext("%s: ignoring too-long name\n"),
158 for (ep
= lookupino(ROOTINO
); ep
!= NIL
; ep
= ep
->e_entries
) {
160 while (*cp
!= '/' && *cp
!= '\0')
163 for (; ep
!= NIL
; ep
= ep
->e_sibling
)
164 if (strcmp(ep
->e_name
, buf
) == 0)
170 * skip over the "./" prefix on all
171 * extended attribute paths
185 * Look up the parent of a pathname. This routine accepts complex
186 * names so the provided name argument must terminate with two NULLs.
188 static struct entry
*
193 char *tailindex
, savechar
, *lastpart
;
196 /* find the last component of the complex name */
199 tailindex
= strrchr(lastpart
, '/');
200 if (tailindex
== 0) {
201 if (lastpart
== name
)
204 * tailindex normaly points to the '/' character
205 * dividing the path, but in the case of an extended
206 * attribute transition it will point to the NULL
207 * separator in front of the attribute path.
209 tailindex
= lastpart
- 1;
214 savechar
= *(tailindex
+1);
215 *(tailindex
+1) = '\0';
216 ep
= lookupname(name
);
217 if (ep
!= NIL
&& !xattrparent
&& ep
->e_type
!= NODE
)
218 panic(gettext("%s is not a directory\n"), name
);
219 if (!xattrparent
) *tailindex
= '/';
220 *(tailindex
+1) = savechar
;
225 * Determine the current pathname of a node or leaf.
226 * The returned pathname will be multiple strings with NULL separators:
228 * ./<path>/entry\0<path>/attrentry\0<path>/...\0\0
230 * return pntr entry attr recursive attr terminator
232 * Guaranteed to return a name that fits within MAXCOMPLEXLEN and is
233 * terminated with two NULLs.
240 struct entry
*root
= lookupino(ROOTINO
);
241 static char namebuf
[MAXCOMPLEXLEN
];
243 cp
= &namebuf
[MAXCOMPLEXLEN
- 3];
246 while (cp
> &namebuf
[ep
->e_namlen
]) {
248 bcopy(ep
->e_name
, cp
, (size_t)ep
->e_namlen
);
251 if (ep
->e_flags
& XATTRROOT
)
257 panic(gettext("%s%s: pathname too long\n"), "...", cp
);
262 * Unused symbol table entries are linked together on a freelist
263 * headed by the following pointer.
265 static struct entry
*freelist
= NIL
;
268 * add an entry to the symbol table
271 addentry(name
, inum
, type
)
276 struct entry
*np
, *ep
;
279 if (freelist
!= NIL
) {
281 freelist
= np
->e_next
;
282 (void) bzero((char *)np
, (size_t)sizeof (*np
));
284 np
= (struct entry
*)calloc(1, sizeof (*np
));
286 (void) fprintf(stderr
,
287 gettext("no memory to extend symbol table\n"));
291 np
->e_type
= type
& ~(LINK
|ROOT
);
293 np
->e_flags
|= XATTR
;
294 ep
= lookupparent(name
);
296 if (inum
!= ROOTINO
|| lookupino(ROOTINO
) != NIL
) {
297 (void) fprintf(stderr
, gettext(
298 "%s: bad name %s\n"), "addentry", name
);
302 np
->e_name
= savename(name
);
303 /* LINTED: savename guarantees that strlen fits in e_namlen */
304 np
->e_namlen
= strlen(name
);
310 if (np
->e_flags
& XATTR
) {
312 * skip to the last part of the complex string: it
313 * containes the extended attribute file name.
317 cp
= strrchr(name
, '/');
323 np
->e_name
= savename(cp
);
324 /* LINTED: savename guarantees that strlen will fit */
325 np
->e_namlen
= strlen(np
->e_name
);
328 * Extended attribute root directories must be linked to their
329 * "parents" via the e_xattrs field. Other entries are simply
330 * added to their parent directories e_entries list.
332 if ((type
& ROOT
) && (np
->e_flags
& XATTR
)) {
333 /* link this extended attribute root dir to its "parent" */
336 /* add this entry to the entry list of the parent dir */
337 np
->e_sibling
= ep
->e_entries
;
341 ep
= lookupino(inum
);
343 /* XXX just bail on this one and continue? */
344 (void) fprintf(stderr
,
345 gettext("link to non-existent name\n"));
349 np
->e_links
= ep
->e_links
;
351 } else if (inum
!= 0) {
352 ep
= lookupino(inum
);
354 panic(gettext("duplicate entry\n"));
362 * delete an entry from the symbol table
371 if ((ep
->e_flags
& REMOVED
) == 0)
372 badentry(ep
, gettext("not marked REMOVED"));
373 if (ep
->e_type
== NODE
) {
374 if (ep
->e_links
!= NIL
)
375 badentry(ep
, gettext("freeing referenced directory"));
376 if (ep
->e_entries
!= NIL
)
377 badentry(ep
, gettext("freeing non-empty directory"));
379 if (ep
->e_ino
!= 0) {
380 np
= lookupino(ep
->e_ino
);
382 badentry(ep
, gettext("lookupino failed"));
386 if (ep
->e_links
!= NIL
)
387 addino(inum
, ep
->e_links
);
389 for (; np
!= NIL
; np
= np
->e_links
) {
390 if (np
->e_links
== ep
) {
391 np
->e_links
= ep
->e_links
;
396 badentry(ep
, gettext("link not found"));
400 freename(ep
->e_name
);
401 ep
->e_next
= freelist
;
406 * Relocate an entry in the tree structure
409 moveentry(ep
, newname
)
416 np
= lookupparent(newname
);
418 badentry(ep
, gettext("cannot move ROOT"));
419 if (np
!= ep
->e_parent
) {
422 ep
->e_sibling
= np
->e_entries
;
425 /* find the last component of the complex name */
427 cp
= strrchr(newname
, '/') + 1;
430 freename(ep
->e_name
);
431 ep
->e_name
= savename(cp
);
432 /* LINTED: savename guarantees that strlen will fit */
433 ep
->e_namlen
= strlen(cp
);
434 if (strcmp(gentempname(ep
), ep
->e_name
) == 0) {
435 /* LINTED: result fits in a short */
436 ep
->e_flags
|= TMPNAME
;
438 /* LINTED: result fits in a short */
439 ep
->e_flags
&= ~TMPNAME
;
444 * Remove an entry in the tree structure
453 if (ep
->e_flags
& XATTRROOT
) {
454 if (np
->e_xattrs
== ep
)
457 badentry(ep
, gettext(
458 "parent does not reference this xattr tree"));
459 } else if (np
->e_entries
== ep
) {
460 np
->e_entries
= ep
->e_sibling
;
462 for (np
= np
->e_entries
; np
!= NIL
; np
= np
->e_sibling
) {
463 if (np
->e_sibling
== ep
) {
464 np
->e_sibling
= ep
->e_sibling
;
469 badentry(ep
, gettext(
470 "cannot find entry in parent list"));
475 * Table of unused string entries, sorted by length.
477 * Entries are allocated in STRTBLINCR sized pieces so that names
478 * of similar lengths can use the same entry. The value of STRTBLINCR
479 * is chosen so that every entry has at least enough space to hold
480 * a "struct strtbl" header. Thus every entry can be linked onto an
481 * apprpriate free list.
483 * NB. The macro "allocsize" below assumes that "struct strhdr"
484 * has a size that is a power of two. Also, an extra byte is
485 * allocated for the string to provide space for the two NULL
486 * string terminator required for extended attribute paths.
492 #define STRTBLINCR ((size_t)sizeof (struct strhdr))
493 #define allocsize(size) (((size) + 2 + STRTBLINCR - 1) & ~(STRTBLINCR - 1))
495 static struct strhdr strtblhdr
[allocsize(MAXCOMPLEXLEN
) / STRTBLINCR
];
498 * Allocate space for a name. It first looks to see if it already
499 * has an appropriate sized entry, and if not allocates a new one.
510 (void) fprintf(stderr
, gettext("bad name\n"));
514 if (len
> MAXPATHLEN
) {
515 (void) fprintf(stderr
, gettext("name too long\n"));
519 np
= strtblhdr
[as
/ STRTBLINCR
].next
;
521 strtblhdr
[as
/ STRTBLINCR
].next
= np
->next
;
524 /* Note that allocsize() adds 2 for the trailing \0s */
527 (void) fprintf(stderr
,
528 gettext("no space for string table\n"));
532 (void) strcpy(cp
, name
);
533 /* add an extra null for complex (attribute) name support */
539 * Free space for a name. The resulting entry is linked onto the
540 * appropriate free list.
546 struct strhdr
*tp
, *np
;
548 /* NULL case should never happen, but might as well be careful */
550 tp
= &strtblhdr
[allocsize(strlen(name
)) / STRTBLINCR
];
551 /*LINTED [name points to at least sizeof (struct strhdr)]*/
552 np
= (struct strhdr
*)name
;
559 * Useful quantities placed at the end of a dumped symbol table.
561 struct symtableheader
{
572 * dump a snapshot of the symbol table
575 dumpsymtable(filename
, checkpt
)
579 struct entry
*ep
, *tep
;
581 struct entry temp
, *tentry
;
585 struct symtableheader hdr
;
587 vprintf(stdout
, gettext("Check pointing the restore\n"));
588 if ((fp
= safe_fopen(filename
, "w", 0600)) == NULL
) {
590 (void) fprintf(stderr
,
591 gettext("cannot create save file %s for symbol table\n"),
597 * Assign an index to each entry
598 * Write out the string entries
600 for (i
= ROOTINO
; i
< maxino
; i
++) {
601 for (ep
= lookupino(i
); ep
!= NIL
; ep
= ep
->e_links
) {
602 ep
->e_index
= mynum
++;
603 (void) fwrite(ep
->e_name
, sizeof (ep
->e_name
[0]),
604 (size_t)allocsize(ep
->e_namlen
), fp
);
608 * Convert e_name pointers to offsets, other pointers
609 * to indices, and output
613 for (i
= ROOTINO
; !ferror(fp
) && i
< maxino
; i
++) {
614 for (ep
= lookupino(i
);
615 !ferror(fp
) && ep
!= NIL
;
617 bcopy((char *)ep
, (char *)tep
, sizeof (*tep
));
618 /* LINTED: type pun ok */
619 tep
->e_name
= (char *)stroff
;
620 stroff
+= allocsize(ep
->e_namlen
);
621 tep
->e_parent
= (struct entry
*)ep
->e_parent
->e_index
;
622 if (ep
->e_links
!= NIL
)
624 (struct entry
*)ep
->e_links
->e_index
;
625 if (ep
->e_sibling
!= NIL
)
627 (struct entry
*)ep
->e_sibling
->e_index
;
628 if (ep
->e_entries
!= NIL
)
630 (struct entry
*)ep
->e_entries
->e_index
;
631 if (ep
->e_xattrs
!= NIL
)
633 (struct entry
*)ep
->e_xattrs
->e_index
;
634 if (ep
->e_next
!= NIL
)
636 (struct entry
*)ep
->e_next
->e_index
;
637 (void) fwrite((char *)tep
, sizeof (*tep
), 1, fp
);
641 * Convert entry pointers to indices, and output
643 for (i
= 0; !ferror(fp
) && i
< (ino_t
)entrytblsize
; i
++) {
647 tentry
= (struct entry
*)entry
[i
]->e_index
;
648 (void) fwrite((char *)&tentry
, sizeof (tentry
), 1, fp
);
652 /* Ought to have a checksum or magic number */
655 hdr
.entrytblsize
= entrytblsize
;
656 hdr
.stringsize
= stroff
;
657 hdr
.dumptime
= dumptime
;
658 hdr
.dumpdate
= dumpdate
;
660 (void) fwrite((char *)&hdr
, sizeof (hdr
), 1, fp
);
665 panic(gettext("output error to file %s writing symbol table\n"),
672 * Initialize a symbol table from a file
675 initsymtable(filename
)
681 struct entry
*baseep
, *lep
;
682 struct symtableheader hdr
;
687 vprintf(stdout
, gettext("Initialize symbol table.\n"));
688 if (filename
== NULL
) {
689 if ((maxino
/ HASHFACTOR
) > UINT_MAX
) {
690 (void) fprintf(stderr
,
691 gettext("file system too large\n"));
694 /* LINTED: result fits in entrytblsize */
695 entrytblsize
= maxino
/ HASHFACTOR
;
696 entry
= (struct entry
**)
697 /* LINTED entrytblsize fits in a size_t */
698 calloc((size_t)entrytblsize
, sizeof (*entry
));
699 if (entry
== (struct entry
**)NULL
) {
700 (void) fprintf(stderr
,
701 gettext("no memory for entry table\n"));
704 ep
= addentry(".", ROOTINO
, NODE
);
705 /* LINTED: result fits in a short */
709 if ((fd
= open(filename
, O_RDONLY
)) < 0) {
711 (void) fprintf(stderr
,
712 gettext("cannot open symbol table file %s\n"), filename
);
715 if (fstat64(fd
, &stbuf
) < 0) {
717 (void) fprintf(stderr
,
718 gettext("cannot stat symbol table file %s\n"), filename
);
723 * The symbol table file is too small so say we can't read it.
725 if (stbuf
.st_size
< sizeof (hdr
)) {
726 (void) fprintf(stderr
,
727 gettext("cannot read symbol table file %s\n"), filename
);
731 tblsize
= stbuf
.st_size
- sizeof (hdr
);
732 if (tblsize
> ULONG_MAX
) {
733 (void) fprintf(stderr
,
734 gettext("symbol table file too large\n"));
738 /* LINTED tblsize fits in a size_t */
739 base
= calloc((size_t)sizeof (char), (size_t)tblsize
);
741 (void) fprintf(stderr
,
742 gettext("cannot allocate space for symbol table\n"));
746 /* LINTED tblsize fits in a size_t */
747 if (read(fd
, base
, (size_t)tblsize
) < 0 ||
748 read(fd
, (char *)&hdr
, sizeof (hdr
)) < 0) {
750 (void) fprintf(stderr
,
751 gettext("cannot read symbol table file %s\n"), filename
);
760 * For normal continuation, insure that we are using
761 * the next incremental tape
763 if (hdr
.dumpdate
!= dumptime
) {
764 if (hdr
.dumpdate
< dumptime
)
765 (void) fprintf(stderr
, gettext(
766 "Incremental volume too low\n"));
768 (void) fprintf(stderr
, gettext(
769 "Incremental volume too high\n"));
775 * For restart, insure that we are using the same tape
777 curfile
.action
= SKIP
;
778 dumptime
= hdr
.dumptime
;
779 dumpdate
= hdr
.dumpdate
;
781 newtapebuf(hdr
.ntrec
);
785 (void) fprintf(stderr
,
786 gettext("initsymtable called from command %c\n"),
792 entrytblsize
= hdr
.entrytblsize
;
793 /*LINTED [pointer cast alignment]*/
794 entry
= (struct entry
**)
795 (base
+ tblsize
- (entrytblsize
* sizeof (*entry
)));
796 if (((ulong_t
)entry
% 4) != 0) {
797 (void) fprintf(stderr
,
798 gettext("Symbol table file corrupted\n"));
801 /*LINTED [rvalue % 4 == 0] */
802 baseep
= (struct entry
*)
803 (base
+ hdr
.stringsize
- sizeof (*baseep
));
804 if (((ulong_t
)baseep
% 4) != 0) {
805 (void) fprintf(stderr
,
806 gettext("Symbol table file corrupted\n"));
809 lep
= (struct entry
*)entry
;
810 for (i
= 0; i
< entrytblsize
; i
++) {
813 entry
[i
] = &baseep
[(long)entry
[i
]];
815 for (ep
= &baseep
[1]; ep
< lep
; ep
++) {
816 ep
->e_name
= base
+ (long)ep
->e_name
;
817 ep
->e_parent
= &baseep
[(long)ep
->e_parent
];
818 if (ep
->e_sibling
!= NIL
)
819 ep
->e_sibling
= &baseep
[(long)ep
->e_sibling
];
820 if (ep
->e_links
!= NIL
)
821 ep
->e_links
= &baseep
[(long)ep
->e_links
];
822 if (ep
->e_entries
!= NIL
)
823 ep
->e_entries
= &baseep
[(long)ep
->e_entries
];
824 if (ep
->e_xattrs
!= NIL
)
825 ep
->e_xattrs
= &baseep
[(long)ep
->e_xattrs
];
826 if (ep
->e_next
!= NIL
)
827 ep
->e_next
= &baseep
[(long)ep
->e_next
];