8cd384c51dd36a7f2ba622f75f0214bdf93fd268
[dump.git] / restore / symtab.c
1 /*
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
7 */
8
9 /*
10 * Copyright (c) 1983, 1993
11 * The Regents of the University of California. All rights reserved.
12 *
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions
15 * are met:
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.
24 *
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
35 * SUCH DAMAGE.
36 */
37
38 #ifndef lint
39 static const char rcsid[] =
40 "$Id: symtab.c,v 1.23 2004/12/14 14:07:58 stelian Exp $";
41 #endif /* not lint */
42
43 /*
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".
50 */
51
52 #include <config.h>
53 #include <sys/param.h>
54 #include <sys/stat.h>
55
56 #ifdef __linux__
57 #include <sys/time.h>
58 #include <time.h>
59 #ifdef HAVE_EXT2FS_EXT2_FS_H
60 #include <ext2fs/ext2_fs.h>
61 #else
62 #include <linux/ext2_fs.h>
63 #endif
64 #include <bsdcompat.h>
65 #else /* __linux__ */
66 #ifdef sunos
67 #include <sys/fcntl.h>
68 #include <bsdcompat.h>
69 #else
70 #include <ufs/ufs/dinode.h>
71 #endif
72 #endif /* __linux__ */
73
74 #include <errno.h>
75 #include <compaterr.h>
76 #include <fcntl.h>
77 #include <stdio.h>
78 #include <stdlib.h>
79 #include <string.h>
80 #include <unistd.h>
81
82 #ifdef __linux__
83 #include <ext2fs/ext2fs.h>
84 #endif
85
86 #include "restore.h"
87 #include "extern.h"
88
89 /*
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).
95 */
96 #define HASHFACTOR 5
97 static struct entry **entry;
98 static long entrytblsize;
99
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 *));
104
105 /*
106 * Returns a hash given a file name
107 */
108 static int
109 dir_hash(char *name)
110 {
111 unsigned long hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
112 int len = strlen(name);
113
114 while (len--) {
115 unsigned long hash = hash1 + (hash0 ^ (*name++ * 7152373));
116 if (hash & 0x80000000) hash -= 0x7fffffff;
117 hash1 = hash0;
118 hash0 = hash;
119 }
120 return hash0 % DIRHASH_SIZE;
121 }
122
123 /*
124 * Look up an entry by inode number
125 */
126 struct entry *
127 lookupino(dump_ino_t inum)
128 {
129 struct entry *ep;
130
131 if (inum < WINO || inum >= maxino)
132 return (NULL);
133 for (ep = entry[inum % entrytblsize]; ep != NULL; ep = ep->e_next)
134 if (ep->e_ino == inum)
135 return (ep);
136 return (NULL);
137 }
138
139 /*
140 * Add an entry into the entry table
141 */
142 static void
143 addino(dump_ino_t inum, struct entry *np)
144 {
145 struct entry **epp;
146
147 if (inum < WINO || inum >= maxino)
148 panic("addino: out of range %d\n", inum);
149 epp = &entry[inum % entrytblsize];
150 np->e_ino = inum;
151 np->e_next = *epp;
152 *epp = np;
153 if (dflag)
154 for (np = np->e_next; np != NULL; np = np->e_next)
155 if (np->e_ino == inum)
156 badentry(np, "duplicate inum");
157 }
158
159 /*
160 * Delete an entry from the entry table
161 */
162 void
163 deleteino(dump_ino_t inum)
164 {
165 struct entry *next;
166 struct entry **prev;
167
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) {
173 next->e_ino = 0;
174 *prev = next->e_next;
175 return;
176 }
177 prev = &next->e_next;
178 }
179 panic("deleteino: %d not found\n", inum);
180 }
181
182 /*
183 * Look up an entry by name
184 */
185 struct entry *
186 lookupname(char *name)
187 {
188 struct entry *ep, *oldep;
189 char *np, *cp;
190 char buf[MAXPATHLEN];
191
192 cp = name;
193
194 ep = lookupino(ROOTINO);
195 while (ep != NULL) {
196 for (np = buf; *cp != '/' && *cp != '\0' &&
197 np < &buf[sizeof(buf)]; )
198 *np++ = *cp++;
199 if (np == &buf[sizeof(buf)])
200 break;
201 *np = '\0';
202
203 oldep = ep;
204
205 if (strcmp(ep->e_name, buf) != 0 &&
206 ep->e_entries != NULL) {
207
208 ep = ep->e_entries[dir_hash(buf)];
209 for ( ; ep != NULL; ep = ep->e_sibling)
210 if (strcmp(ep->e_name, buf) == 0)
211 break;
212
213 /* search all hash lists for renamed inodes */
214 if (ep == NULL) {
215 int j;
216 for (j = 0; j < DIRHASH_SIZE; j++) {
217 ep = oldep->e_entries[j];
218 for ( ; ep != NULL; ep = ep->e_sibling)
219 if (strcmp(ep->e_name, buf) == 0)
220 break;
221 if (ep != NULL)
222 break;
223 }
224 }
225 }
226
227 if (ep == NULL)
228 break;
229 if (*cp++ == '\0')
230 return (ep);
231 }
232 return (NULL);
233 }
234
235 /*
236 * Look up the parent of a pathname
237 */
238 static struct entry *
239 lookupparent(char *name)
240 {
241 struct entry *ep;
242 char *tailindex;
243
244 tailindex = strrchr(name, '/');
245 if (tailindex == NULL)
246 return (NULL);
247 *tailindex = '\0';
248 ep = lookupname(name);
249 *tailindex = '/';
250 if (ep == NULL)
251 return (NULL);
252 if (ep->e_type != NODE)
253 panic("%s is not a directory\n", name);
254 return (ep);
255 }
256
257 /*
258 * Determine the current pathname of a node or leaf
259 */
260 char *
261 myname(struct entry *ep)
262 {
263 char *cp;
264 static char namebuf[MAXPATHLEN];
265
266 for (cp = &namebuf[MAXPATHLEN - 2]; cp > &namebuf[ep->e_namlen]; ) {
267 cp -= ep->e_namlen;
268 memmove(cp, ep->e_name, (size_t)ep->e_namlen);
269 if (ep == lookupino(ROOTINO))
270 return (cp);
271 *(--cp) = '/';
272 ep = ep->e_parent;
273 }
274 panic("%s: pathname too long\n", cp);
275 return(cp);
276 }
277
278 /*
279 * Unused symbol table entries are linked together on a free list
280 * headed by the following pointer.
281 */
282 static struct entry *freelist = NULL;
283
284 /*
285 * add an entry to the symbol table
286 */
287 struct entry *
288 addentry(char *name, dump_ino_t inum, int type)
289 {
290 struct entry *np, *ep;
291
292 if (freelist != NULL) {
293 np = freelist;
294 freelist = np->e_next;
295 memset(np, 0, sizeof(struct entry));
296 } else {
297 np = (struct entry *)calloc(1, sizeof(struct entry));
298 if (np == NULL)
299 errx(1, "no memory to extend symbol table");
300 }
301 np->e_type = type & ~LINK;
302 if (type & NODE) {
303 np->e_entries = calloc(1, DIRHASH_SIZE * sizeof(struct entry *));
304 if (np->e_entries == NULL)
305 panic("unable to allocate directory entries\n");
306 }
307 ep = lookupparent(name);
308 if (ep == NULL) {
309 if (inum != ROOTINO || lookupino(ROOTINO) != NULL)
310 panic("bad name to addentry %s\n", name);
311 np->e_name = savename(name);
312 np->e_namlen = strlen(name);
313 np->e_parent = np;
314 addino(ROOTINO, np);
315 return (np);
316 }
317 np->e_name = savename(strrchr(name, '/') + 1);
318 np->e_namlen = strlen(np->e_name);
319 np->e_parent = ep;
320 np->e_sibling = ep->e_entries[dir_hash(np->e_name)];
321 ep->e_entries[dir_hash(np->e_name)] = np;
322 if (type & LINK) {
323 ep = lookupino(inum);
324 if (ep == NULL)
325 panic("link to non-existent name\n");
326 np->e_ino = inum;
327 np->e_links = ep->e_links;
328 ep->e_links = np;
329 } else if (inum != 0) {
330 if (lookupino(inum) != NULL)
331 panic("duplicate entry\n");
332 addino(inum, np);
333 }
334 return (np);
335 }
336
337 /*
338 * delete an entry from the symbol table
339 */
340 void
341 freeentry(struct entry *ep)
342 {
343 struct entry *np;
344 dump_ino_t inum;
345
346 if (ep->e_flags != REMOVED)
347 badentry(ep, "not marked REMOVED");
348 if (ep->e_type == NODE) {
349 if (ep->e_links != NULL)
350 badentry(ep, "freeing referenced directory");
351 if (ep->e_entries != NULL) {
352 int i;
353 for (i = 0; i < DIRHASH_SIZE; i++) {
354 if (ep->e_entries[i] != NULL)
355 badentry(ep, "freeing non-empty directory");
356 }
357 }
358 }
359 if (ep->e_ino != 0) {
360 np = lookupino(ep->e_ino);
361 if (np == NULL)
362 badentry(ep, "lookupino failed");
363 if (np == ep) {
364 inum = ep->e_ino;
365 deleteino(inum);
366 if (ep->e_links != NULL)
367 addino(inum, ep->e_links);
368 } else {
369 for (; np != NULL; np = np->e_links) {
370 if (np->e_links == ep) {
371 np->e_links = ep->e_links;
372 break;
373 }
374 }
375 if (np == NULL)
376 badentry(ep, "link not found");
377 }
378 }
379 removeentry(ep);
380 freename(ep->e_name);
381 ep->e_next = freelist;
382 freelist = ep;
383 }
384
385 /*
386 * Relocate an entry in the tree structure
387 */
388 void
389 moveentry(struct entry *ep, char *newname)
390 {
391 struct entry *np;
392 char *cp;
393
394 np = lookupparent(newname);
395 if (np == NULL)
396 badentry(ep, "cannot move ROOT");
397 if (np != ep->e_parent) {
398 removeentry(ep);
399 ep->e_parent = np;
400 ep->e_sibling = np->e_entries[dir_hash(ep->e_name)];
401 np->e_entries[dir_hash(ep->e_name)] = ep;
402 }
403 cp = strrchr(newname, '/') + 1;
404 freename(ep->e_name);
405 ep->e_name = savename(cp);
406 ep->e_namlen = strlen(cp);
407 if (strcmp(gentempname(ep), ep->e_name) == 0)
408 ep->e_flags |= TMPNAME;
409 else
410 ep->e_flags &= ~TMPNAME;
411 }
412
413 /*
414 * Remove an entry in the tree structure
415 */
416 static void
417 removeentry(struct entry *ep)
418 {
419 struct entry *np = ep->e_parent;
420 struct entry *entry = np->e_entries[dir_hash(ep->e_name)];
421
422 if (entry == ep) {
423 np->e_entries[dir_hash(ep->e_name)] = ep->e_sibling;
424 } else {
425 for (np = entry; np != NULL; np = np->e_sibling) {
426 if (np->e_sibling == ep) {
427 np->e_sibling = ep->e_sibling;
428 break;
429 }
430 }
431 if (np == NULL) {
432
433 /* search all hash lists for renamed inodes */
434 int j;
435 for (j = 0; j < DIRHASH_SIZE; j++) {
436 np = ep->e_parent;
437 entry = np->e_entries[j];
438 if (entry == ep) {
439 np->e_entries[j] = ep->e_sibling;
440 return;
441 }
442 else {
443 for (np = entry; np != NULL; np = np->e_sibling) {
444 if (np->e_sibling == ep) {
445 np->e_sibling = ep->e_sibling;
446 return;
447 }
448 }
449 }
450 }
451 badentry(ep, "cannot find entry in parent list");
452 }
453 }
454 }
455
456 /*
457 * Table of unused string entries, sorted by length.
458 *
459 * Entries are allocated in STRTBLINCR sized pieces so that names
460 * of similar lengths can use the same entry. The value of STRTBLINCR
461 * is chosen so that every entry has at least enough space to hold
462 * a "struct strtbl" header. Thus every entry can be linked onto an
463 * appropriate free list.
464 *
465 * NB. The macro "allocsize" below assumes that "struct strhdr"
466 * has a size that is a power of two.
467 */
468 struct strhdr {
469 struct strhdr *next;
470 };
471
472 #define STRTBLINCR (sizeof(struct strhdr))
473 #define allocsize(size) (((size) + 1 + STRTBLINCR - 1) & ~(STRTBLINCR - 1))
474
475 static struct strhdr strtblhdr[allocsize(MAXNAMLEN) / STRTBLINCR];
476
477 /*
478 * Allocate space for a name. It first looks to see if it already
479 * has an appropriate sized entry, and if not allocates a new one.
480 */
481 char *
482 savename(char *name)
483 {
484 struct strhdr *np;
485 long len;
486 char *cp;
487
488 if (name == NULL)
489 panic("bad name\n");
490 len = strlen(name);
491 np = strtblhdr[len / STRTBLINCR].next;
492 if (np != NULL) {
493 strtblhdr[len / STRTBLINCR].next = np->next;
494 cp = (char *)np;
495 } else {
496 cp = malloc((unsigned)allocsize(len));
497 if (cp == NULL)
498 errx(1, "no space for string table");
499 }
500 (void) strcpy(cp, name);
501 return (cp);
502 }
503
504 /*
505 * Free space for a name. The resulting entry is linked onto the
506 * appropriate free list.
507 */
508 void
509 freename(char *name)
510 {
511 struct strhdr *tp, *np;
512
513 tp = &strtblhdr[strlen(name) / STRTBLINCR];
514 np = (struct strhdr *)name;
515 np->next = tp->next;
516 tp->next = np;
517 }
518
519 /*
520 * Useful quantities placed at the end of a dumped symbol table.
521 */
522 struct symtableheader {
523 int32_t volno;
524 int32_t stringsize;
525 int32_t hashsize;
526 int32_t entrytblsize;
527 time_t dumptime;
528 time_t dumpdate;
529 dump_ino_t maxino;
530 int32_t ntrec;
531 int32_t zflag;
532 };
533
534 /*
535 * dump a snapshot of the symbol table
536 */
537 void
538 dumpsymtable(char *filename, long checkpt)
539 {
540 struct entry *ep, *tep;
541 dump_ino_t i;
542 struct entry temp, *tentry;
543 long mynum = 1, stroff = 0, hashoff = 0;
544 FILE *fd;
545 struct symtableheader hdr;
546 struct entry *temphash[DIRHASH_SIZE];
547
548 Vprintf(stdout, "Check pointing the restore\n");
549 if (Nflag)
550 return;
551 if ((fd = fopen(filename, "w")) == NULL) {
552 warn("fopen");
553 panic("cannot create save file %s for symbol table\n",
554 filename);
555 }
556 clearerr(fd);
557 /*
558 * Assign indices to each entry
559 * Write out the string entries
560 */
561 for (i = WINO; i <= maxino; i++) {
562 for (ep = lookupino(i); ep != NULL; ep = ep->e_links) {
563 ep->e_index = mynum++;
564 (void) fwrite(ep->e_name, sizeof(char),
565 (int)allocsize(ep->e_namlen), fd);
566 }
567 }
568 /*
569 * Write out e_entries tables
570 */
571 for (i = WINO; i <= maxino; i++) {
572 for (ep = lookupino(i); ep != NULL; ep = ep->e_links) {
573 if (ep->e_entries != NULL) {
574 int j;
575 memcpy(temphash, ep->e_entries, DIRHASH_SIZE * sizeof(struct entry *));
576 for (j = 0; j < DIRHASH_SIZE; j++) {
577 if (temphash[j])
578 temphash[j] = (struct entry *)ep->e_entries[j]->e_index;
579 }
580 fwrite(temphash, DIRHASH_SIZE, sizeof(struct entry *), fd);
581 }
582 }
583 }
584 /*
585 * Convert pointers to indexes, and output
586 */
587 tep = &temp;
588 stroff = 0;
589 hashoff = 0;
590 for (i = WINO; i <= maxino; i++) {
591 for (ep = lookupino(i); ep != NULL; ep = ep->e_links) {
592 memmove(tep, ep, sizeof(struct entry));
593 tep->e_name = (char *)stroff;
594 stroff += allocsize(ep->e_namlen);
595 tep->e_parent = (struct entry *)ep->e_parent->e_index;
596 if (ep->e_links != NULL)
597 tep->e_links =
598 (struct entry *)ep->e_links->e_index;
599 if (ep->e_sibling != NULL)
600 tep->e_sibling =
601 (struct entry *)ep->e_sibling->e_index;
602 if (ep->e_entries != NULL) {
603 tep->e_entries = (struct entry **)hashoff;
604 hashoff += DIRHASH_SIZE * sizeof(struct entry *);
605 }
606 if (ep->e_next != NULL)
607 tep->e_next =
608 (struct entry *)ep->e_next->e_index;
609 (void) fwrite((char *)tep, sizeof(struct entry), 1, fd);
610 }
611 }
612 /*
613 * Convert entry pointers to indexes, and output
614 */
615 for (i = 0; (long)i < entrytblsize; i++) {
616 if (entry[i] == NULL)
617 tentry = NULL;
618 else
619 tentry = (struct entry *)entry[i]->e_index;
620 (void) fwrite((char *)&tentry, sizeof(struct entry *), 1, fd);
621 }
622 hdr.volno = checkpt;
623 hdr.maxino = maxino;
624 hdr.entrytblsize = entrytblsize;
625 hdr.stringsize = stroff;
626 hdr.hashsize = hashoff;
627 hdr.dumptime = dumptime;
628 hdr.dumpdate = dumpdate;
629 hdr.ntrec = ntrec;
630 hdr.zflag = zflag;
631 (void) fwrite((char *)&hdr, sizeof(struct symtableheader), 1, fd);
632 if (ferror(fd)) {
633 warn("fwrite");
634 panic("output error to file %s writing symbol table\n",
635 filename);
636 }
637 (void) fclose(fd);
638 }
639
640 /*
641 * Initialize a symbol table from a file
642 */
643 void
644 initsymtable(char *filename)
645 {
646 char *base;
647 long tblsize;
648 struct entry *ep;
649 struct entry *baseep, *lep;
650 struct symtableheader hdr;
651 struct stat stbuf;
652 long i;
653 int fd;
654
655 Vprintf(stdout, "Initialize symbol table.\n");
656 if (filename == NULL) {
657 entrytblsize = maxino / HASHFACTOR;
658 entry = (struct entry **)
659 calloc((unsigned)entrytblsize, sizeof(struct entry *));
660 if (entry == (struct entry **)NULL)
661 errx(1, "no memory for entry table");
662 ep = addentry(".", ROOTINO, NODE);
663 ep->e_flags |= NEW;
664 return;
665 }
666 if ((fd = open(filename, O_RDONLY, 0)) < 0) {
667 warn("open");
668 errx(1, "cannot open symbol table file %s", filename);
669 }
670 if (fstat(fd, &stbuf) < 0) {
671 warn("stat");
672 errx(1, "cannot stat symbol table file %s", filename);
673 }
674 tblsize = stbuf.st_size - sizeof(struct symtableheader);
675 base = calloc(sizeof(char), (unsigned)tblsize);
676 if (base == NULL)
677 errx(1, "cannot allocate space for symbol table");
678 if (read(fd, base, (int)tblsize) < 0 ||
679 read(fd, (char *)&hdr, sizeof(struct symtableheader)) < 0) {
680 warn("read");
681 errx(1, "cannot read symbol table file %s", filename);
682 }
683 switch (command) {
684 case 'r':
685 /*
686 * For normal continuation, insure that we are using
687 * the next incremental tape
688 */
689 if (hdr.dumpdate != dumptime)
690 errx(1, "Incremental tape too %s",
691 (hdr.dumpdate < dumptime) ? "low" : "high");
692 break;
693 case 'R':
694 /*
695 * For restart, insure that we are using the same tape
696 */
697 curfile.action = SKIP;
698 dumptime = hdr.dumptime;
699 dumpdate = hdr.dumpdate;
700 zflag = hdr.zflag;
701 if (!bflag)
702 newtapebuf(hdr.ntrec);
703 getvol(hdr.volno);
704 break;
705 default:
706 panic("initsymtable called from command %c\n", command);
707 break;
708 }
709 resizemaps(maxino, hdr.maxino);
710 maxino = hdr.maxino;
711 entrytblsize = hdr.entrytblsize;
712 entry = (struct entry **)
713 (base + tblsize - (entrytblsize * sizeof(struct entry *)));
714 baseep = (struct entry *)(base + hdr.stringsize + hdr.hashsize - sizeof(struct entry));
715 lep = (struct entry *)entry;
716 for (i = 0; i < entrytblsize; i++) {
717 if (entry[i] == NULL)
718 continue;
719 entry[i] = &baseep[(long)entry[i]];
720 }
721 for (ep = &baseep[1]; ep < lep; ep++) {
722 ep->e_name = base + (long)ep->e_name;
723 ep->e_parent = &baseep[(long)ep->e_parent];
724 if (ep->e_sibling != NULL)
725 ep->e_sibling = &baseep[(long)ep->e_sibling];
726 if (ep->e_links != NULL)
727 ep->e_links = &baseep[(long)ep->e_links];
728 if (ep->e_type == NODE) {
729 int i;
730 ep->e_entries = (struct entry **)(base + hdr.stringsize + (long)ep->e_entries);
731 for (i = 0; i < DIRHASH_SIZE; i++) {
732 if (ep->e_entries[i])
733 ep->e_entries[i] = &baseep[(long)ep->e_entries[i]];
734 }
735 }
736 else
737 ep->e_entries = NULL;
738 if (ep->e_next != NULL)
739 ep->e_next = &baseep[(long)ep->e_next];
740 }
741 }