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.25 2005/03/30 13:34:00 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 <sys/param.h>
59 #ifdef HAVE_EXT2FS_EXT2_FS_H
60 #include <ext2fs/ext2_fs.h>
62 #include <linux/ext2_fs.h>
64 #include <bsdcompat.h>
67 #include <sys/fcntl.h>
68 #include <bsdcompat.h>
70 #include <ufs/ufs/dinode.h>
72 #endif /* __linux__ */
75 #include <compaterr.h>
83 #include <ext2fs/ext2fs.h>
90 * The following variables define the inode symbol table.
91 * The primary hash table is dynamically allocated based on
92 * the number of inodes in the file system (maxino), scaled by
93 * HASHFACTOR. The variable "entry" points to the hash table;
94 * the variable "entrytblsize" indicates its size (in entries).
97 static struct entry **entry;
98 static long entrytblsize;
100 static void addino __P((dump_ino_t, struct entry *));
101 static struct entry *lookupparent __P((char *));
102 static void removeentry __P((struct entry *));
103 static int dir_hash __P((char *));
106 * Returns a hash given a file name
111 unsigned long hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
112 int len = strlen(name);
115 unsigned long hash = hash1 + (hash0 ^ (*name++ * 7152373));
116 if (hash & 0x80000000) hash -= 0x7fffffff;
120 return hash0 % DIRHASH_SIZE;
124 * Look up an entry by inode number
127 lookupino(dump_ino_t inum)
131 if (inum < WINO || inum >= maxino)
133 for (ep = entry[inum % entrytblsize]; ep != NULL; ep = ep->e_next)
134 if (ep->e_ino == inum)
140 * Add an entry into the entry table
143 addino(dump_ino_t inum, struct entry *np)
147 if (inum < WINO || inum >= maxino)
148 panic("addino: out of range %d\n", inum);
149 epp = &entry[inum % entrytblsize];
154 for (np = np->e_next; np != NULL; np = np->e_next)
155 if (np->e_ino == inum)
156 badentry(np, "duplicate inum");
160 * Delete an entry from the entry table
163 deleteino(dump_ino_t inum)
168 if (inum < WINO || inum >= maxino)
169 panic("deleteino: out of range %d\n", inum);
170 prev = &entry[inum % entrytblsize];
171 for (next = *prev; next != NULL; next = next->e_next) {
172 if (next->e_ino == inum) {
174 *prev = next->e_next;
177 prev = &next->e_next;
179 panic("deleteino: %d not found\n", inum);
183 * Look up an entry by name
186 lookupname(char *name)
188 struct entry *ep, *oldep;
190 char buf[MAXPATHLEN];
192 ep = lookupino(ROOTINO);
203 for (np = buf; *cp != '/' && *cp != '\0' &&
204 np < &buf[sizeof(buf)]; )
206 if (np == &buf[sizeof(buf)])
212 if (ep->e_entries != NULL) {
214 ep = ep->e_entries[dir_hash(buf)];
215 for ( ; ep != NULL; ep = ep->e_sibling)
216 if (strcmp(ep->e_name, buf) == 0)
219 /* search all hash lists for renamed inodes */
222 for (j = 0; j < DIRHASH_SIZE; j++) {
223 ep = oldep->e_entries[j];
224 for ( ; ep != NULL; ep = ep->e_sibling)
225 if (strcmp(ep->e_name, buf) == 0)
242 * Look up the parent of a pathname
244 static struct entry *
245 lookupparent(char *name)
250 tailindex = strrchr(name, '/');
251 if (tailindex == NULL)
254 ep = lookupname(name);
258 if (ep->e_type != NODE)
259 panic("%s is not a directory\n", name);
264 * Determine the current pathname of a node or leaf
267 myname(struct entry *ep)
270 static char namebuf[MAXPATHLEN];
272 for (cp = &namebuf[MAXPATHLEN - 2]; cp > &namebuf[ep->e_namlen]; ) {
274 memmove(cp, ep->e_name, (size_t)ep->e_namlen);
275 if (ep == lookupino(ROOTINO))
280 panic("%s: pathname too long\n", cp);
285 * Unused symbol table entries are linked together on a free list
286 * headed by the following pointer.
288 static struct entry *freelist = NULL;
291 * add an entry to the symbol table
294 addentry(char *name, dump_ino_t inum, int type)
296 struct entry *np, *ep;
298 if (freelist != NULL) {
300 freelist = np->e_next;
301 memset(np, 0, sizeof(struct entry));
303 np = (struct entry *)calloc(1, sizeof(struct entry));
305 errx(1, "no memory to extend symbol table");
307 np->e_type = type & ~LINK;
309 np->e_entries = calloc(1, DIRHASH_SIZE * sizeof(struct entry *));
310 if (np->e_entries == NULL)
311 panic("unable to allocate directory entries\n");
313 ep = lookupparent(name);
315 if (inum != ROOTINO || lookupino(ROOTINO) != NULL)
316 panic("bad name to addentry %s\n", name);
317 np->e_name = savename(name);
318 np->e_namlen = strlen(name);
323 np->e_name = savename(strrchr(name, '/') + 1);
324 np->e_namlen = strlen(np->e_name);
326 np->e_sibling = ep->e_entries[dir_hash(np->e_name)];
327 ep->e_entries[dir_hash(np->e_name)] = np;
329 ep = lookupino(inum);
331 panic("link to non-existent name\n");
333 np->e_links = ep->e_links;
335 } else if (inum != 0) {
336 if (lookupino(inum) != NULL)
337 panic("duplicate entry\n");
344 * delete an entry from the symbol table
347 freeentry(struct entry *ep)
352 if (ep->e_flags != REMOVED)
353 badentry(ep, "not marked REMOVED");
354 if (ep->e_type == NODE) {
355 if (ep->e_links != NULL)
356 badentry(ep, "freeing referenced directory");
357 if (ep->e_entries != NULL) {
359 for (i = 0; i < DIRHASH_SIZE; i++) {
360 if (ep->e_entries[i] != NULL)
361 badentry(ep, "freeing non-empty directory");
365 if (ep->e_ino != 0) {
366 np = lookupino(ep->e_ino);
368 badentry(ep, "lookupino failed");
372 if (ep->e_links != NULL)
373 addino(inum, ep->e_links);
375 for (; np != NULL; np = np->e_links) {
376 if (np->e_links == ep) {
377 np->e_links = ep->e_links;
382 badentry(ep, "link not found");
386 freename(ep->e_name);
387 ep->e_next = freelist;
392 * Relocate an entry in the tree structure
395 moveentry(struct entry *ep, char *newname)
400 np = lookupparent(newname);
402 badentry(ep, "cannot move ROOT");
403 if (np != ep->e_parent) {
406 ep->e_sibling = np->e_entries[dir_hash(ep->e_name)];
407 np->e_entries[dir_hash(ep->e_name)] = ep;
409 cp = strrchr(newname, '/') + 1;
410 freename(ep->e_name);
411 ep->e_name = savename(cp);
412 ep->e_namlen = strlen(cp);
413 if (strcmp(gentempname(ep), ep->e_name) == 0)
414 ep->e_flags |= TMPNAME;
416 ep->e_flags &= ~TMPNAME;
420 * Remove an entry in the tree structure
423 removeentry(struct entry *ep)
425 struct entry *np = ep->e_parent;
426 struct entry *entry = np->e_entries[dir_hash(ep->e_name)];
429 np->e_entries[dir_hash(ep->e_name)] = ep->e_sibling;
431 for (np = entry; np != NULL; np = np->e_sibling) {
432 if (np->e_sibling == ep) {
433 np->e_sibling = ep->e_sibling;
439 /* search all hash lists for renamed inodes */
441 for (j = 0; j < DIRHASH_SIZE; j++) {
443 entry = np->e_entries[j];
445 np->e_entries[j] = ep->e_sibling;
449 for (np = entry; np != NULL; np = np->e_sibling) {
450 if (np->e_sibling == ep) {
451 np->e_sibling = ep->e_sibling;
457 badentry(ep, "cannot find entry in parent list");
463 * Table of unused string entries, sorted by length.
465 * Entries are allocated in STRTBLINCR sized pieces so that names
466 * of similar lengths can use the same entry. The value of STRTBLINCR
467 * is chosen so that every entry has at least enough space to hold
468 * a "struct strtbl" header. Thus every entry can be linked onto an
469 * appropriate free list.
471 * NB. The macro "allocsize" below assumes that "struct strhdr"
472 * has a size that is a power of two.
478 #define STRTBLINCR (sizeof(struct strhdr))
479 #define allocsize(size) (((size) + 1 + STRTBLINCR - 1) & ~(STRTBLINCR - 1))
481 static struct strhdr strtblhdr[allocsize(MAXNAMLEN) / STRTBLINCR];
484 * Allocate space for a name. It first looks to see if it already
485 * has an appropriate sized entry, and if not allocates a new one.
497 np = strtblhdr[len / STRTBLINCR].next;
499 strtblhdr[len / STRTBLINCR].next = np->next;
502 cp = malloc((unsigned)allocsize(len));
504 errx(1, "no space for string table");
506 (void) strcpy(cp, name);
511 * Free space for a name. The resulting entry is linked onto the
512 * appropriate free list.
517 struct strhdr *tp, *np;
519 tp = &strtblhdr[strlen(name) / STRTBLINCR];
520 np = (struct strhdr *)name;
526 * Useful quantities placed at the end of a dumped symbol table.
528 struct symtableheader {
532 int32_t entrytblsize;
541 * dump a snapshot of the symbol table
544 dumpsymtable(char *filename, long checkpt)
546 struct entry *ep, *tep;
548 struct entry temp, *tentry;
549 long mynum = 1, stroff = 0, hashoff = 0;
551 struct symtableheader hdr;
552 struct entry *temphash[DIRHASH_SIZE];
554 Vprintf(stdout, "Check pointing the restore\n");
557 if ((fd = fopen(filename, "w")) == NULL) {
559 panic("cannot create save file %s for symbol table\n",
564 * Assign indices to each entry
565 * Write out the string entries
567 for (i = WINO; i <= maxino; i++) {
568 for (ep = lookupino(i); ep != NULL; ep = ep->e_links) {
569 ep->e_index = mynum++;
570 (void) fwrite(ep->e_name, sizeof(char),
571 (int)allocsize(ep->e_namlen), fd);
575 * Write out e_entries tables
577 for (i = WINO; i <= maxino; i++) {
578 for (ep = lookupino(i); ep != NULL; ep = ep->e_links) {
579 if (ep->e_entries != NULL) {
581 memcpy(temphash, ep->e_entries, DIRHASH_SIZE * sizeof(struct entry *));
582 for (j = 0; j < DIRHASH_SIZE; j++) {
584 temphash[j] = (struct entry *)ep->e_entries[j]->e_index;
586 fwrite(temphash, DIRHASH_SIZE, sizeof(struct entry *), fd);
591 * Convert pointers to indexes, and output
596 for (i = WINO; i <= maxino; i++) {
597 for (ep = lookupino(i); ep != NULL; ep = ep->e_links) {
598 memmove(tep, ep, sizeof(struct entry));
599 tep->e_name = (char *)stroff;
600 stroff += allocsize(ep->e_namlen);
601 tep->e_parent = (struct entry *)ep->e_parent->e_index;
602 if (ep->e_links != NULL)
604 (struct entry *)ep->e_links->e_index;
605 if (ep->e_sibling != NULL)
607 (struct entry *)ep->e_sibling->e_index;
608 if (ep->e_entries != NULL) {
609 tep->e_entries = (struct entry **)hashoff;
610 hashoff += DIRHASH_SIZE * sizeof(struct entry *);
612 if (ep->e_next != NULL)
614 (struct entry *)ep->e_next->e_index;
615 (void) fwrite((char *)tep, sizeof(struct entry), 1, fd);
619 * Convert entry pointers to indexes, and output
621 for (i = 0; (long)i < entrytblsize; i++) {
622 if (entry[i] == NULL)
625 tentry = (struct entry *)entry[i]->e_index;
626 (void) fwrite((char *)&tentry, sizeof(struct entry *), 1, fd);
630 hdr.entrytblsize = entrytblsize;
631 hdr.stringsize = stroff;
632 hdr.hashsize = hashoff;
633 hdr.dumptime = dumptime;
634 hdr.dumpdate = dumpdate;
637 (void) fwrite((char *)&hdr, sizeof(struct symtableheader), 1, fd);
640 panic("output error to file %s writing symbol table\n",
647 * Initialize a symbol table from a file
650 initsymtable(char *filename)
655 struct entry *baseep, *lep;
656 struct symtableheader hdr;
661 Vprintf(stdout, "Initialize symbol table.\n");
662 if (filename == NULL) {
663 entrytblsize = maxino / HASHFACTOR;
664 entry = (struct entry **)
665 calloc((unsigned)entrytblsize, sizeof(struct entry *));
666 if (entry == (struct entry **)NULL)
667 errx(1, "no memory for entry table");
668 ep = addentry(".", ROOTINO, NODE);
672 if ((fd = open(filename, O_RDONLY, 0)) < 0) {
674 errx(1, "cannot open symbol table file %s", filename);
676 if (fstat(fd, &stbuf) < 0) {
678 errx(1, "cannot stat symbol table file %s", filename);
680 tblsize = stbuf.st_size - sizeof(struct symtableheader);
681 base = calloc(sizeof(char), (unsigned)tblsize);
683 errx(1, "cannot allocate space for symbol table");
684 if (read(fd, base, (int)tblsize) < 0 ||
685 read(fd, (char *)&hdr, sizeof(struct symtableheader)) < 0) {
687 errx(1, "cannot read symbol table file %s", filename);
692 * For normal continuation, insure that we are using
693 * the next incremental tape
695 if (hdr.dumpdate != dumptime)
696 errx(1, "Incremental tape too %s",
697 (hdr.dumpdate < dumptime) ? "low" : "high");
701 * For restart, insure that we are using the same tape
703 curfile.action = SKIP;
704 dumptime = hdr.dumptime;
705 dumpdate = hdr.dumpdate;
708 newtapebuf(hdr.ntrec);
712 panic("initsymtable called from command %c\n", command);
715 if (hdr.maxino > maxino) {
716 resizemaps(maxino, hdr.maxino);
719 entrytblsize = hdr.entrytblsize;
720 entry = (struct entry **)
721 (base + tblsize - (entrytblsize * sizeof(struct entry *)));
722 baseep = (struct entry *)(base + hdr.stringsize + hdr.hashsize - sizeof(struct entry));
723 lep = (struct entry *)entry;
724 for (i = 0; i < entrytblsize; i++) {
725 if (entry[i] == NULL)
727 entry[i] = &baseep[(long)entry[i]];
729 for (ep = &baseep[1]; ep < lep; ep++) {
730 ep->e_name = base + (long)ep->e_name;
731 ep->e_parent = &baseep[(long)ep->e_parent];
732 if (ep->e_sibling != NULL)
733 ep->e_sibling = &baseep[(long)ep->e_sibling];
734 if (ep->e_links != NULL)
735 ep->e_links = &baseep[(long)ep->e_links];
736 if (ep->e_type == NODE) {
738 ep->e_entries = (struct entry **)(base + hdr.stringsize + (long)ep->e_entries);
739 for (i = 0; i < DIRHASH_SIZE; i++) {
740 if (ep->e_entries[i])
741 ep->e_entries[i] = &baseep[(long)ep->e_entries[i]];
745 ep->e_entries = NULL;
746 if (ep->e_next != NULL)
747 ep->e_next = &baseep[(long)ep->e_next];