]>
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, 1995, 1996
9 * Copyright (c) 1983, 1993
10 * The Regents of the University of California. All rights reserved.
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions
15 * 1. Redistributions of source code must retain the above copyright
16 * notice, this list of conditions and the following disclaimer.
17 * 2. Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in the
19 * documentation and/or other materials provided with the distribution.
20 * 3. All advertising materials mentioning features or use of this software
21 * must display the following acknowledgement:
22 * This product includes software developed by the University of
23 * California, Berkeley and its contributors.
24 * 4. Neither the name of the University nor the names of its contributors
25 * may be used to endorse or promote products derived from this software
26 * without specific prior written permission.
28 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
29 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
30 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
31 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
32 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
33 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
34 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
35 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
36 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
37 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
42 static char sccsid
[] = "@(#)symtab.c 8.3 (Berkeley) 4/28/95";
46 * These routines maintain the symbol table which tracks the state
47 * of the file system being restored. They provide lookup by either
48 * name or inode number. They also provide for creation, deletion,
49 * and renaming of entries. Because of the dynamic nature of pathnames,
50 * names should not be saved, but always constructed just before they
51 * are needed, by calling "myname".
54 #include <sys/param.h>
59 #include <linux/ext2_fs.h>
60 #include <bsdcompat.h>
62 #include <ufs/ufs/dinode.h>
63 #endif /* __linux__ */
73 #include <ext2fs/ext2fs.h>
80 * The following variables define the inode symbol table.
81 * The primary hash table is dynamically allocated based on
82 * the number of inodes in the file system (maxino), scaled by
83 * HASHFACTOR. The variable "entry" points to the hash table;
84 * the variable "entrytblsize" indicates its size (in entries).
87 static struct entry
**entry
;
88 static long entrytblsize
;
90 static void addino
__P((ino_t
, struct entry
*));
91 static struct entry
*lookupparent
__P((char *));
92 static void removeentry
__P((struct entry
*));
95 * Look up an entry by inode number
101 register struct entry
*ep
;
103 if (inum
< WINO
|| inum
>= maxino
)
105 for (ep
= entry
[inum
% entrytblsize
]; ep
!= NULL
; ep
= ep
->e_next
)
106 if (ep
->e_ino
== inum
)
112 * Add an entry into the entry table
121 if (inum
< WINO
|| inum
>= maxino
)
122 panic("addino: out of range %d\n", inum
);
123 epp
= &entry
[inum
% entrytblsize
];
128 for (np
= np
->e_next
; np
!= NULL
; np
= np
->e_next
)
129 if (np
->e_ino
== inum
)
130 badentry(np
, "duplicate inum");
134 * Delete an entry from the entry table
140 register struct entry
*next
;
143 if (inum
< WINO
|| inum
>= maxino
)
144 panic("deleteino: out of range %d\n", inum
);
145 prev
= &entry
[inum
% entrytblsize
];
146 for (next
= *prev
; next
!= NULL
; next
= next
->e_next
) {
147 if (next
->e_ino
== inum
) {
149 *prev
= next
->e_next
;
152 prev
= &next
->e_next
;
154 panic("deleteino: %d not found\n", inum
);
158 * Look up an entry by name
164 register struct entry
*ep
;
165 register char *np
, *cp
;
166 char buf
[MAXPATHLEN
];
169 for (ep
= lookupino(ROOTINO
); ep
!= NULL
; ep
= ep
->e_entries
) {
170 for (np
= buf
; *cp
!= '/' && *cp
!= '\0'; )
173 for ( ; ep
!= NULL
; ep
= ep
->e_sibling
)
174 if (strcmp(ep
->e_name
, buf
) == 0)
185 * Look up the parent of a pathname
187 static struct entry
*
194 tailindex
= strrchr(name
, '/');
195 if (tailindex
== NULL
)
198 ep
= lookupname(name
);
202 if (ep
->e_type
!= NODE
)
203 panic("%s is not a directory\n", name
);
208 * Determine the current pathname of a node or leaf
212 register struct entry
*ep
;
215 static char namebuf
[MAXPATHLEN
];
217 for (cp
= &namebuf
[MAXPATHLEN
- 2]; cp
> &namebuf
[ep
->e_namlen
]; ) {
219 memmove(cp
, ep
->e_name
, (long)ep
->e_namlen
);
220 if (ep
== lookupino(ROOTINO
))
225 panic("%s: pathname too long\n", cp
);
230 * Unused symbol table entries are linked together on a freelist
231 * headed by the following pointer.
233 static struct entry
*freelist
= NULL
;
236 * add an entry to the symbol table
239 addentry(name
, inum
, type
)
244 register struct entry
*np
, *ep
;
246 if (freelist
!= NULL
) {
248 freelist
= np
->e_next
;
249 memset(np
, 0, (long)sizeof(struct entry
));
251 np
= (struct entry
*)calloc(1, sizeof(struct entry
));
253 panic("no memory to extend symbol table\n");
255 np
->e_type
= type
& ~LINK
;
256 ep
= lookupparent(name
);
258 if (inum
!= ROOTINO
|| lookupino(ROOTINO
) != NULL
)
259 panic("bad name to addentry %s\n", name
);
260 np
->e_name
= savename(name
);
261 np
->e_namlen
= strlen(name
);
266 np
->e_name
= savename(strrchr(name
, '/') + 1);
267 np
->e_namlen
= strlen(np
->e_name
);
269 np
->e_sibling
= ep
->e_entries
;
272 ep
= lookupino(inum
);
274 panic("link to non-existant name\n");
276 np
->e_links
= ep
->e_links
;
278 } else if (inum
!= 0) {
279 if (lookupino(inum
) != NULL
)
280 panic("duplicate entry\n");
287 * delete an entry from the symbol table
291 register struct entry
*ep
;
293 register struct entry
*np
;
296 if (ep
->e_flags
!= REMOVED
)
297 badentry(ep
, "not marked REMOVED");
298 if (ep
->e_type
== NODE
) {
299 if (ep
->e_links
!= NULL
)
300 badentry(ep
, "freeing referenced directory");
301 if (ep
->e_entries
!= NULL
)
302 badentry(ep
, "freeing non-empty directory");
304 if (ep
->e_ino
!= 0) {
305 np
= lookupino(ep
->e_ino
);
307 badentry(ep
, "lookupino failed");
311 if (ep
->e_links
!= NULL
)
312 addino(inum
, ep
->e_links
);
314 for (; np
!= NULL
; np
= np
->e_links
) {
315 if (np
->e_links
== ep
) {
316 np
->e_links
= ep
->e_links
;
321 badentry(ep
, "link not found");
325 freename(ep
->e_name
);
326 ep
->e_next
= freelist
;
331 * Relocate an entry in the tree structure
334 moveentry(ep
, newname
)
335 register struct entry
*ep
;
341 np
= lookupparent(newname
);
343 badentry(ep
, "cannot move ROOT");
344 if (np
!= ep
->e_parent
) {
347 ep
->e_sibling
= np
->e_entries
;
350 cp
= strrchr(newname
, '/') + 1;
351 freename(ep
->e_name
);
352 ep
->e_name
= savename(cp
);
353 ep
->e_namlen
= strlen(cp
);
354 if (strcmp(gentempname(ep
), ep
->e_name
) == 0)
355 ep
->e_flags
|= TMPNAME
;
357 ep
->e_flags
&= ~TMPNAME
;
361 * Remove an entry in the tree structure
365 register struct entry
*ep
;
367 register struct entry
*np
;
370 if (np
->e_entries
== ep
) {
371 np
->e_entries
= ep
->e_sibling
;
373 for (np
= np
->e_entries
; np
!= NULL
; np
= np
->e_sibling
) {
374 if (np
->e_sibling
== ep
) {
375 np
->e_sibling
= ep
->e_sibling
;
380 badentry(ep
, "cannot find entry in parent list");
385 * Table of unused string entries, sorted by length.
387 * Entries are allocated in STRTBLINCR sized pieces so that names
388 * of similar lengths can use the same entry. The value of STRTBLINCR
389 * is chosen so that every entry has at least enough space to hold
390 * a "struct strtbl" header. Thus every entry can be linked onto an
391 * apprpriate free list.
393 * NB. The macro "allocsize" below assumes that "struct strhdr"
394 * has a size that is a power of two.
400 #define STRTBLINCR (sizeof(struct strhdr))
401 #define allocsize(size) (((size) + 1 + STRTBLINCR - 1) & ~(STRTBLINCR - 1))
403 static struct strhdr strtblhdr
[allocsize(NAME_MAX
) / STRTBLINCR
];
406 * Allocate space for a name. It first looks to see if it already
407 * has an appropriate sized entry, and if not allocates a new one.
420 np
= strtblhdr
[len
/ STRTBLINCR
].next
;
422 strtblhdr
[len
/ STRTBLINCR
].next
= np
->next
;
425 cp
= malloc((unsigned)allocsize(len
));
427 panic("no space for string table\n");
429 (void) strcpy(cp
, name
);
434 * Free space for a name. The resulting entry is linked onto the
435 * appropriate free list.
441 struct strhdr
*tp
, *np
;
443 tp
= &strtblhdr
[strlen(name
) / STRTBLINCR
];
444 np
= (struct strhdr
*)name
;
450 * Useful quantities placed at the end of a dumped symbol table.
452 struct symtableheader
{
463 * dump a snapshot of the symbol table
466 dumpsymtable(filename
, checkpt
)
470 register struct entry
*ep
, *tep
;
472 struct entry temp
, *tentry
;
473 long mynum
= 1, stroff
= 0;
475 struct symtableheader hdr
;
477 vprintf(stdout
, "Check pointing the restore\n");
480 if ((fd
= fopen(filename
, "w")) == NULL
) {
481 fprintf(stderr
, "fopen: %s\n", strerror(errno
));
482 panic("cannot create save file %s for symbol table\n",
487 * Assign indicies to each entry
488 * Write out the string entries
490 for (i
= WINO
; i
< maxino
; i
++) {
491 for (ep
= lookupino(i
); ep
!= NULL
; ep
= ep
->e_links
) {
492 ep
->e_index
= mynum
++;
493 (void) fwrite(ep
->e_name
, sizeof(char),
494 (int)allocsize(ep
->e_namlen
), fd
);
498 * Convert pointers to indexes, and output
502 for (i
= WINO
; i
< maxino
; i
++) {
503 for (ep
= lookupino(i
); ep
!= NULL
; ep
= ep
->e_links
) {
504 memmove(tep
, ep
, (long)sizeof(struct entry
));
505 tep
->e_name
= (char *)stroff
;
506 stroff
+= allocsize(ep
->e_namlen
);
507 tep
->e_parent
= (struct entry
*)ep
->e_parent
->e_index
;
508 if (ep
->e_links
!= NULL
)
510 (struct entry
*)ep
->e_links
->e_index
;
511 if (ep
->e_sibling
!= NULL
)
513 (struct entry
*)ep
->e_sibling
->e_index
;
514 if (ep
->e_entries
!= NULL
)
516 (struct entry
*)ep
->e_entries
->e_index
;
517 if (ep
->e_next
!= NULL
)
519 (struct entry
*)ep
->e_next
->e_index
;
520 (void) fwrite((char *)tep
, sizeof(struct entry
), 1, fd
);
524 * Convert entry pointers to indexes, and output
526 for (i
= 0; i
< entrytblsize
; i
++) {
527 if (entry
[i
] == NULL
)
530 tentry
= (struct entry
*)entry
[i
]->e_index
;
531 (void) fwrite((char *)&tentry
, sizeof(struct entry
*), 1, fd
);
535 hdr
.entrytblsize
= entrytblsize
;
536 hdr
.stringsize
= stroff
;
537 hdr
.dumptime
= dumptime
;
538 hdr
.dumpdate
= dumpdate
;
540 (void) fwrite((char *)&hdr
, sizeof(struct symtableheader
), 1, fd
);
542 fprintf(stderr
, "fwrite: %s\n", strerror(errno
));
543 panic("output error to file %s writing symbol table\n",
550 * Initialize a symbol table from a file
553 initsymtable(filename
)
558 register struct entry
*ep
;
559 struct entry
*baseep
, *lep
;
560 struct symtableheader hdr
;
565 vprintf(stdout
, "Initialize symbol table.\n");
566 if (filename
== NULL
) {
567 entrytblsize
= maxino
/ HASHFACTOR
;
568 entry
= (struct entry
**)
569 calloc((unsigned)entrytblsize
, sizeof(struct entry
*));
570 if (entry
== (struct entry
**)NULL
)
571 panic("no memory for entry table\n");
572 ep
= addentry(".", ROOTINO
, NODE
);
576 if ((fd
= open(filename
, O_RDONLY
, 0)) < 0) {
577 fprintf(stderr
, "open: %s\n", strerror(errno
));
578 panic("cannot open symbol table file %s\n", filename
);
580 if (fstat(fd
, &stbuf
) < 0) {
581 fprintf(stderr
, "stat: %s\n", strerror(errno
));
582 panic("cannot stat symbol table file %s\n", filename
);
584 tblsize
= stbuf
.st_size
- sizeof(struct symtableheader
);
585 base
= calloc(sizeof(char), (unsigned)tblsize
);
587 panic("cannot allocate space for symbol table\n");
588 if (read(fd
, base
, (int)tblsize
) < 0 ||
589 read(fd
, (char *)&hdr
, sizeof(struct symtableheader
)) < 0) {
590 fprintf(stderr
, "read: %s\n", strerror(errno
));
591 panic("cannot read symbol table file %s\n", filename
);
596 * For normal continuation, insure that we are using
597 * the next incremental tape
599 if (hdr
.dumpdate
!= dumptime
) {
600 if (hdr
.dumpdate
< dumptime
)
601 fprintf(stderr
, "Incremental tape too low\n");
603 fprintf(stderr
, "Incremental tape too high\n");
609 * For restart, insure that we are using the same tape
611 curfile
.action
= SKIP
;
612 dumptime
= hdr
.dumptime
;
613 dumpdate
= hdr
.dumpdate
;
615 newtapebuf(hdr
.ntrec
);
619 panic("initsymtable called from command %c\n", command
);
623 entrytblsize
= hdr
.entrytblsize
;
624 entry
= (struct entry
**)
625 (base
+ tblsize
- (entrytblsize
* sizeof(struct entry
*)));
626 baseep
= (struct entry
*)(base
+ hdr
.stringsize
- sizeof(struct entry
));
627 lep
= (struct entry
*)entry
;
628 for (i
= 0; i
< entrytblsize
; i
++) {
629 if (entry
[i
] == NULL
)
631 entry
[i
] = &baseep
[(long)entry
[i
]];
633 for (ep
= &baseep
[1]; ep
< lep
; ep
++) {
634 ep
->e_name
= base
+ (long)ep
->e_name
;
635 ep
->e_parent
= &baseep
[(long)ep
->e_parent
];
636 if (ep
->e_sibling
!= NULL
)
637 ep
->e_sibling
= &baseep
[(long)ep
->e_sibling
];
638 if (ep
->e_links
!= NULL
)
639 ep
->e_links
= &baseep
[(long)ep
->e_links
];
640 if (ep
->e_entries
!= NULL
)
641 ep
->e_entries
= &baseep
[(long)ep
->e_entries
];
642 if (ep
->e_next
!= NULL
)
643 ep
->e_next
= &baseep
[(long)ep
->e_next
];