2 * Copyright (c) 1983, 1993
3 * The Regents of the University of California. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of the University nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * @(#)symtab.c 8.3 (Berkeley) 4/28/95
30 * $FreeBSD: src/sbin/restore/symtab.c,v 1.7.2.1 2001/12/19 14:54:14 tobez Exp $
34 * These routines maintain the symbol table which tracks the state
35 * of the file system being restored. They provide lookup by either
36 * name or inode number. They also provide for creation, deletion,
37 * and renaming of entries. Because of the dynamic nature of pathnames,
38 * names should not be saved, but always constructed just before they
39 * are needed, by calling "myname".
42 #include <sys/param.h>
45 #include <vfs/ufs/dinode.h>
58 * The following variables define the inode symbol table.
59 * The primary hash table is dynamically allocated based on
60 * the number of inodes in the file system (maxino), scaled by
61 * HASHFACTOR. The variable "entry" points to the hash table;
62 * the variable "entrytblsize" indicates its size (in entries).
65 static struct entry
**entry
;
66 static long entrytblsize
;
68 static void addino(ufs1_ino_t
, struct entry
*);
69 static struct entry
*lookupparent(char *);
70 static void removeentry(struct entry
*);
73 * Look up an entry by inode number
76 lookupino(ufs1_ino_t inum
)
80 if (inum
< WINO
|| inum
>= maxino
)
82 for (ep
= entry
[inum
% entrytblsize
]; ep
!= NULL
; ep
= ep
->e_next
)
83 if (ep
->e_ino
== inum
)
89 * Add an entry into the entry table
92 addino(ufs1_ino_t inum
, struct entry
*np
)
96 if (inum
< WINO
|| inum
>= maxino
)
97 panic("addino: out of range %d\n", inum
);
98 epp
= &entry
[inum
% entrytblsize
];
103 for (np
= np
->e_next
; np
!= NULL
; np
= np
->e_next
)
104 if (np
->e_ino
== inum
)
105 badentry(np
, "duplicate inum");
109 * Delete an entry from the entry table
112 deleteino(ufs1_ino_t inum
)
117 if (inum
< WINO
|| inum
>= maxino
)
118 panic("deleteino: out of range %d\n", inum
);
119 prev
= &entry
[inum
% entrytblsize
];
120 for (next
= *prev
; next
!= NULL
; next
= next
->e_next
) {
121 if (next
->e_ino
== inum
) {
123 *prev
= next
->e_next
;
126 prev
= &next
->e_next
;
128 panic("deleteino: %d not found\n", inum
);
132 * Look up an entry by name
135 lookupname(char *name
)
139 char buf
[MAXPATHLEN
];
142 for (ep
= lookupino(ROOTINO
); ep
!= NULL
; ep
= ep
->e_entries
) {
143 for (np
= buf
; *cp
!= '/' && *cp
!= '\0' &&
144 np
< &buf
[sizeof(buf
)]; )
146 if (np
== &buf
[sizeof(buf
)])
149 for ( ; ep
!= NULL
; ep
= ep
->e_sibling
)
150 if (strcmp(ep
->e_name
, buf
) == 0)
161 * Look up the parent of a pathname
163 static struct entry
*
164 lookupparent(char *name
)
169 tailindex
= strrchr(name
, '/');
170 if (tailindex
== NULL
)
173 ep
= lookupname(name
);
177 if (ep
->e_type
!= NODE
)
178 panic("%s is not a directory\n", name
);
183 * Determine the current pathname of a node or leaf
186 myname(struct entry
*ep
)
189 static char namebuf
[MAXPATHLEN
];
191 for (cp
= &namebuf
[MAXPATHLEN
- 2]; cp
> &namebuf
[ep
->e_namlen
]; ) {
193 memmove(cp
, ep
->e_name
, (long)ep
->e_namlen
);
194 if (ep
== lookupino(ROOTINO
))
199 panic("%s: pathname too long\n", cp
);
204 * Unused symbol table entries are linked together on a free list
205 * headed by the following pointer.
207 static struct entry
*freelist
= NULL
;
210 * add an entry to the symbol table
213 addentry(char *name
, ufs1_ino_t inum
, int type
)
215 struct entry
*np
, *ep
;
217 if (freelist
!= NULL
) {
219 freelist
= np
->e_next
;
220 memset(np
, 0, (long)sizeof(struct entry
));
222 np
= (struct entry
*)calloc(1, sizeof(struct entry
));
224 panic("no memory to extend symbol table\n");
226 np
->e_type
= type
& ~LINK
;
227 ep
= lookupparent(name
);
229 if (inum
!= ROOTINO
|| lookupino(ROOTINO
) != NULL
)
230 panic("bad name to addentry %s\n", name
);
231 np
->e_name
= savename(name
);
232 np
->e_namlen
= strlen(name
);
237 np
->e_name
= savename(strrchr(name
, '/') + 1);
238 np
->e_namlen
= strlen(np
->e_name
);
240 np
->e_sibling
= ep
->e_entries
;
243 ep
= lookupino(inum
);
245 panic("link to non-existent name\n");
247 np
->e_links
= ep
->e_links
;
249 } else if (inum
!= 0) {
250 if (lookupino(inum
) != NULL
)
251 panic("duplicate entry\n");
258 * delete an entry from the symbol table
261 freeentry(struct entry
*ep
)
266 if (ep
->e_flags
!= REMOVED
)
267 badentry(ep
, "not marked REMOVED");
268 if (ep
->e_type
== NODE
) {
269 if (ep
->e_links
!= NULL
)
270 badentry(ep
, "freeing referenced directory");
271 if (ep
->e_entries
!= NULL
)
272 badentry(ep
, "freeing non-empty directory");
274 if (ep
->e_ino
!= 0) {
275 np
= lookupino(ep
->e_ino
);
277 badentry(ep
, "lookupino failed");
281 if (ep
->e_links
!= NULL
)
282 addino(inum
, ep
->e_links
);
284 for (; np
!= NULL
; np
= np
->e_links
) {
285 if (np
->e_links
== ep
) {
286 np
->e_links
= ep
->e_links
;
291 badentry(ep
, "link not found");
295 freename(ep
->e_name
);
296 ep
->e_next
= freelist
;
301 * Relocate an entry in the tree structure
304 moveentry(struct entry
*ep
, char *newname
)
309 np
= lookupparent(newname
);
311 badentry(ep
, "cannot move ROOT");
312 if (np
!= ep
->e_parent
) {
315 ep
->e_sibling
= np
->e_entries
;
318 cp
= strrchr(newname
, '/') + 1;
319 freename(ep
->e_name
);
320 ep
->e_name
= savename(cp
);
321 ep
->e_namlen
= strlen(cp
);
322 if (strcmp(gentempname(ep
), ep
->e_name
) == 0)
323 ep
->e_flags
|= TMPNAME
;
325 ep
->e_flags
&= ~TMPNAME
;
329 * Remove an entry in the tree structure
332 removeentry(struct entry
*ep
)
337 if (np
->e_entries
== ep
) {
338 np
->e_entries
= ep
->e_sibling
;
340 for (np
= np
->e_entries
; np
!= NULL
; np
= np
->e_sibling
) {
341 if (np
->e_sibling
== ep
) {
342 np
->e_sibling
= ep
->e_sibling
;
347 badentry(ep
, "cannot find entry in parent list");
352 * Table of unused string entries, sorted by length.
354 * Entries are allocated in STRTBLINCR sized pieces so that names
355 * of similar lengths can use the same entry. The value of STRTBLINCR
356 * is chosen so that every entry has at least enough space to hold
357 * a "struct strtbl" header. Thus every entry can be linked onto an
358 * appropriate free list.
360 * NB. The macro "allocsize" below assumes that "struct strhdr"
361 * has a size that is a power of two.
367 #define STRTBLINCR (sizeof(struct strhdr))
368 #define allocsize(size) roundup2((size) + 1, STRTBLINCR)
370 static struct strhdr strtblhdr
[allocsize(NAME_MAX
) / STRTBLINCR
];
373 * Allocate space for a name. It first looks to see if it already
374 * has an appropriate sized entry, and if not allocates a new one.
386 np
= strtblhdr
[len
/ STRTBLINCR
].next
;
388 strtblhdr
[len
/ STRTBLINCR
].next
= np
->next
;
391 cp
= malloc((unsigned)allocsize(len
));
393 panic("no space for string table\n");
400 * Free space for a name. The resulting entry is linked onto the
401 * appropriate free list.
406 struct strhdr
*tp
, *np
;
408 tp
= &strtblhdr
[strlen(name
) / STRTBLINCR
];
409 np
= (struct strhdr
*)name
;
415 * Useful quantities placed at the end of a dumped symbol table.
417 struct symtableheader
{
420 int32_t entrytblsize
;
428 * dump a snapshot of the symbol table
431 dumpsymtable(char *filename
, long checkpt
)
433 struct entry
*ep
, *tep
;
435 struct entry temp
, *tentry
;
436 long mynum
= 1, stroff
= 0;
438 struct symtableheader hdr
;
440 vprintf(stdout
, "Check pointing the restore\n");
443 if ((fd
= fopen(filename
, "w")) == NULL
) {
444 fprintf(stderr
, "fopen: %s\n", strerror(errno
));
445 panic("cannot create save file %s for symbol table\n",
451 * Assign indices to each entry
452 * Write out the string entries
454 for (i
= WINO
; i
<= maxino
; i
++) {
455 for (ep
= lookupino(i
); ep
!= NULL
; ep
= ep
->e_links
) {
456 ep
->e_index
= mynum
++;
457 fwrite(ep
->e_name
, sizeof(char),
458 (int)allocsize(ep
->e_namlen
), fd
);
462 * Convert pointers to indexes, and output
466 for (i
= WINO
; i
<= maxino
; i
++) {
467 for (ep
= lookupino(i
); ep
!= NULL
; ep
= ep
->e_links
) {
468 memmove(tep
, ep
, (long)sizeof(struct entry
));
469 tep
->e_name
= (char *)stroff
;
470 stroff
+= allocsize(ep
->e_namlen
);
471 tep
->e_parent
= (struct entry
*)ep
->e_parent
->e_index
;
472 if (ep
->e_links
!= NULL
)
474 (struct entry
*)ep
->e_links
->e_index
;
475 if (ep
->e_sibling
!= NULL
)
477 (struct entry
*)ep
->e_sibling
->e_index
;
478 if (ep
->e_entries
!= NULL
)
480 (struct entry
*)ep
->e_entries
->e_index
;
481 if (ep
->e_next
!= NULL
)
483 (struct entry
*)ep
->e_next
->e_index
;
484 fwrite((char *)tep
, sizeof(struct entry
), 1, fd
);
488 * Convert entry pointers to indexes, and output
490 for (i
= 0; i
< entrytblsize
; i
++) {
491 if (entry
[i
] == NULL
)
494 tentry
= (struct entry
*)entry
[i
]->e_index
;
495 fwrite((char *)&tentry
, sizeof(struct entry
*), 1, fd
);
499 hdr
.entrytblsize
= entrytblsize
;
500 hdr
.stringsize
= stroff
;
501 hdr
.dumptime
= dumptime
;
502 hdr
.dumpdate
= dumpdate
;
504 fwrite((char *)&hdr
, sizeof(struct symtableheader
), 1, fd
);
506 fprintf(stderr
, "fwrite: %s\n", strerror(errno
));
507 panic("output error to file %s writing symbol table\n",
514 * Initialize a symbol table from a file
517 initsymtable(char *filename
)
522 struct entry
*baseep
, *lep
;
523 struct symtableheader hdr
;
528 vprintf(stdout
, "Initialize symbol table.\n");
529 if (filename
== NULL
) {
530 entrytblsize
= maxino
/ HASHFACTOR
;
531 entry
= (struct entry
**)
532 calloc((unsigned)entrytblsize
, sizeof(struct entry
*));
534 panic("no memory for entry table\n");
535 ep
= addentry(".", ROOTINO
, NODE
);
539 if ((fd
= open(filename
, O_RDONLY
, 0)) < 0) {
540 fprintf(stderr
, "open: %s\n", strerror(errno
));
541 panic("cannot open symbol table file %s\n", filename
);
543 if (fstat(fd
, &stbuf
) < 0) {
544 fprintf(stderr
, "stat: %s\n", strerror(errno
));
545 panic("cannot stat symbol table file %s\n", filename
);
547 tblsize
= stbuf
.st_size
- sizeof(struct symtableheader
);
548 base
= calloc(sizeof(char), (unsigned)tblsize
);
550 panic("cannot allocate space for symbol table\n");
551 if (read(fd
, base
, (int)tblsize
) < 0 ||
552 read(fd
, (char *)&hdr
, sizeof(struct symtableheader
)) < 0) {
553 fprintf(stderr
, "read: %s\n", strerror(errno
));
554 panic("cannot read symbol table file %s\n", filename
);
559 * For normal continuation, insure that we are using
560 * the next incremental tape
562 if (hdr
.dumpdate
!= dumptime
) {
563 if (hdr
.dumpdate
< dumptime
)
564 fprintf(stderr
, "Incremental tape too low\n");
566 fprintf(stderr
, "Incremental tape too high\n");
572 * For restart, insure that we are using the same tape
574 curfile
.action
= SKIP
;
575 dumptime
= hdr
.dumptime
;
576 dumpdate
= hdr
.dumpdate
;
578 newtapebuf(hdr
.ntrec
);
582 panic("initsymtable called from command %c\n", command
);
586 entrytblsize
= hdr
.entrytblsize
;
587 entry
= (struct entry
**)
588 (base
+ tblsize
- (entrytblsize
* sizeof(struct entry
*)));
589 baseep
= (struct entry
*)(base
+ hdr
.stringsize
- sizeof(struct entry
));
590 lep
= (struct entry
*)entry
;
591 for (i
= 0; i
< entrytblsize
; i
++) {
592 if (entry
[i
] == NULL
)
594 entry
[i
] = &baseep
[(long)entry
[i
]];
596 for (ep
= &baseep
[1]; ep
< lep
; ep
++) {
597 ep
->e_name
= base
+ (long)ep
->e_name
;
598 ep
->e_parent
= &baseep
[(long)ep
->e_parent
];
599 if (ep
->e_sibling
!= NULL
)
600 ep
->e_sibling
= &baseep
[(long)ep
->e_sibling
];
601 if (ep
->e_links
!= NULL
)
602 ep
->e_links
= &baseep
[(long)ep
->e_links
];
603 if (ep
->e_entries
!= NULL
)
604 ep
->e_entries
= &baseep
[(long)ep
->e_entries
];
605 if (ep
->e_next
!= NULL
)
606 ep
->e_next
= &baseep
[(long)ep
->e_next
];