Home | History | Annotate | Line # | Download | only in restore
symtab.c revision 1.1.1.2
      1 /*
      2  * Copyright (c) 1983, 1993
      3  *	The Regents of the University of California.  All rights reserved.
      4  *
      5  * Redistribution and use in source and binary forms, with or without
      6  * modification, are permitted provided that the following conditions
      7  * are met:
      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. All advertising materials mentioning features or use of this software
     14  *    must display the following acknowledgement:
     15  *	This product includes software developed by the University of
     16  *	California, Berkeley and its contributors.
     17  * 4. Neither the name of the University nor the names of its contributors
     18  *    may be used to endorse or promote products derived from this software
     19  *    without specific prior written permission.
     20  *
     21  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     31  * SUCH DAMAGE.
     32  */
     33 
     34 #ifndef lint
     35 static char sccsid[] = "@(#)symtab.c	8.1 (Berkeley) 6/5/93";
     36 #endif /* not lint */
     37 
     38 /*
     39  * These routines maintain the symbol table which tracks the state
     40  * of the file system being restored. They provide lookup by either
     41  * name or inode number. They also provide for creation, deletion,
     42  * and renaming of entries. Because of the dynamic nature of pathnames,
     43  * names should not be saved, but always constructed just before they
     44  * are needed, by calling "myname".
     45  */
     46 
     47 #include <sys/param.h>
     48 #include <sys/stat.h>
     49 
     50 #include <ufs/ufs/dinode.h>
     51 
     52 #include <errno.h>
     53 #include <fcntl.h>
     54 #include <stdio.h>
     55 #include <stdlib.h>
     56 #include <string.h>
     57 #include <unistd.h>
     58 
     59 #include "restore.h"
     60 #include "extern.h"
     61 
     62 /*
     63  * The following variables define the inode symbol table.
     64  * The primary hash table is dynamically allocated based on
     65  * the number of inodes in the file system (maxino), scaled by
     66  * HASHFACTOR. The variable "entry" points to the hash table;
     67  * the variable "entrytblsize" indicates its size (in entries).
     68  */
     69 #define HASHFACTOR 5
     70 static struct entry **entry;
     71 static long entrytblsize;
     72 
     73 static void		 addino __P((ino_t, struct entry *));
     74 static struct entry	*lookupparent __P((char *));
     75 static void		 removeentry __P((struct entry *));
     76 
     77 /*
     78  * Look up an entry by inode number
     79  */
     80 struct entry *
     81 lookupino(inum)
     82 	ino_t inum;
     83 {
     84 	register struct entry *ep;
     85 
     86 	if (inum < ROOTINO || inum >= maxino)
     87 		return (NULL);
     88 	for (ep = entry[inum % entrytblsize]; ep != NULL; ep = ep->e_next)
     89 		if (ep->e_ino == inum)
     90 			return (ep);
     91 	return (NULL);
     92 }
     93 
     94 /*
     95  * Add an entry into the entry table
     96  */
     97 static void
     98 addino(inum, np)
     99 	ino_t inum;
    100 	struct entry *np;
    101 {
    102 	struct entry **epp;
    103 
    104 	if (inum < ROOTINO || inum >= maxino)
    105 		panic("addino: out of range %d\n", inum);
    106 	epp = &entry[inum % entrytblsize];
    107 	np->e_ino = inum;
    108 	np->e_next = *epp;
    109 	*epp = np;
    110 	if (dflag)
    111 		for (np = np->e_next; np != NULL; np = np->e_next)
    112 			if (np->e_ino == inum)
    113 				badentry(np, "duplicate inum");
    114 }
    115 
    116 /*
    117  * Delete an entry from the entry table
    118  */
    119 void
    120 deleteino(inum)
    121 	ino_t inum;
    122 {
    123 	register struct entry *next;
    124 	struct entry **prev;
    125 
    126 	if (inum < ROOTINO || inum >= maxino)
    127 		panic("deleteino: out of range %d\n", inum);
    128 	prev = &entry[inum % entrytblsize];
    129 	for (next = *prev; next != NULL; next = next->e_next) {
    130 		if (next->e_ino == inum) {
    131 			next->e_ino = 0;
    132 			*prev = next->e_next;
    133 			return;
    134 		}
    135 		prev = &next->e_next;
    136 	}
    137 	panic("deleteino: %d not found\n", inum);
    138 }
    139 
    140 /*
    141  * Look up an entry by name
    142  */
    143 struct entry *
    144 lookupname(name)
    145 	char *name;
    146 {
    147 	register struct entry *ep;
    148 	register char *np, *cp;
    149 	char buf[MAXPATHLEN];
    150 
    151 	cp = name;
    152 	for (ep = lookupino(ROOTINO); ep != NULL; ep = ep->e_entries) {
    153 		for (np = buf; *cp != '/' && *cp != '\0'; )
    154 			*np++ = *cp++;
    155 		*np = '\0';
    156 		for ( ; ep != NULL; ep = ep->e_sibling)
    157 			if (strcmp(ep->e_name, buf) == 0)
    158 				break;
    159 		if (ep == NULL)
    160 			break;
    161 		if (*cp++ == '\0')
    162 			return (ep);
    163 	}
    164 	return (NULL);
    165 }
    166 
    167 /*
    168  * Look up the parent of a pathname
    169  */
    170 static struct entry *
    171 lookupparent(name)
    172 	char *name;
    173 {
    174 	struct entry *ep;
    175 	char *tailindex;
    176 
    177 	tailindex = rindex(name, '/');
    178 	if (tailindex == NULL)
    179 		return (NULL);
    180 	*tailindex = '\0';
    181 	ep = lookupname(name);
    182 	*tailindex = '/';
    183 	if (ep == NULL)
    184 		return (NULL);
    185 	if (ep->e_type != NODE)
    186 		panic("%s is not a directory\n", name);
    187 	return (ep);
    188 }
    189 
    190 /*
    191  * Determine the current pathname of a node or leaf
    192  */
    193 char *
    194 myname(ep)
    195 	register struct entry *ep;
    196 {
    197 	register char *cp;
    198 	static char namebuf[MAXPATHLEN];
    199 
    200 	for (cp = &namebuf[MAXPATHLEN - 2]; cp > &namebuf[ep->e_namlen]; ) {
    201 		cp -= ep->e_namlen;
    202 		bcopy(ep->e_name, cp, (long)ep->e_namlen);
    203 		if (ep == lookupino(ROOTINO))
    204 			return (cp);
    205 		*(--cp) = '/';
    206 		ep = ep->e_parent;
    207 	}
    208 	panic("%s: pathname too long\n", cp);
    209 	return(cp);
    210 }
    211 
    212 /*
    213  * Unused symbol table entries are linked together on a freelist
    214  * headed by the following pointer.
    215  */
    216 static struct entry *freelist = NULL;
    217 
    218 /*
    219  * add an entry to the symbol table
    220  */
    221 struct entry *
    222 addentry(name, inum, type)
    223 	char *name;
    224 	ino_t inum;
    225 	int type;
    226 {
    227 	register struct entry *np, *ep;
    228 
    229 	if (freelist != NULL) {
    230 		np = freelist;
    231 		freelist = np->e_next;
    232 		bzero((char *)np, (long)sizeof(struct entry));
    233 	} else {
    234 		np = (struct entry *)calloc(1, sizeof(struct entry));
    235 		if (np == NULL)
    236 			panic("no memory to extend symbol table\n");
    237 	}
    238 	np->e_type = type & ~LINK;
    239 	ep = lookupparent(name);
    240 	if (ep == NULL) {
    241 		if (inum != ROOTINO || lookupino(ROOTINO) != NULL)
    242 			panic("bad name to addentry %s\n", name);
    243 		np->e_name = savename(name);
    244 		np->e_namlen = strlen(name);
    245 		np->e_parent = np;
    246 		addino(ROOTINO, np);
    247 		return (np);
    248 	}
    249 	np->e_name = savename(rindex(name, '/') + 1);
    250 	np->e_namlen = strlen(np->e_name);
    251 	np->e_parent = ep;
    252 	np->e_sibling = ep->e_entries;
    253 	ep->e_entries = np;
    254 	if (type & LINK) {
    255 		ep = lookupino(inum);
    256 		if (ep == NULL)
    257 			panic("link to non-existant name\n");
    258 		np->e_ino = inum;
    259 		np->e_links = ep->e_links;
    260 		ep->e_links = np;
    261 	} else if (inum != 0) {
    262 		if (lookupino(inum) != NULL)
    263 			panic("duplicate entry\n");
    264 		addino(inum, np);
    265 	}
    266 	return (np);
    267 }
    268 
    269 /*
    270  * delete an entry from the symbol table
    271  */
    272 void
    273 freeentry(ep)
    274 	register struct entry *ep;
    275 {
    276 	register struct entry *np;
    277 	ino_t inum;
    278 
    279 	if (ep->e_flags != REMOVED)
    280 		badentry(ep, "not marked REMOVED");
    281 	if (ep->e_type == NODE) {
    282 		if (ep->e_links != NULL)
    283 			badentry(ep, "freeing referenced directory");
    284 		if (ep->e_entries != NULL)
    285 			badentry(ep, "freeing non-empty directory");
    286 	}
    287 	if (ep->e_ino != 0) {
    288 		np = lookupino(ep->e_ino);
    289 		if (np == NULL)
    290 			badentry(ep, "lookupino failed");
    291 		if (np == ep) {
    292 			inum = ep->e_ino;
    293 			deleteino(inum);
    294 			if (ep->e_links != NULL)
    295 				addino(inum, ep->e_links);
    296 		} else {
    297 			for (; np != NULL; np = np->e_links) {
    298 				if (np->e_links == ep) {
    299 					np->e_links = ep->e_links;
    300 					break;
    301 				}
    302 			}
    303 			if (np == NULL)
    304 				badentry(ep, "link not found");
    305 		}
    306 	}
    307 	removeentry(ep);
    308 	freename(ep->e_name);
    309 	ep->e_next = freelist;
    310 	freelist = ep;
    311 }
    312 
    313 /*
    314  * Relocate an entry in the tree structure
    315  */
    316 void
    317 moveentry(ep, newname)
    318 	register struct entry *ep;
    319 	char *newname;
    320 {
    321 	struct entry *np;
    322 	char *cp;
    323 
    324 	np = lookupparent(newname);
    325 	if (np == NULL)
    326 		badentry(ep, "cannot move ROOT");
    327 	if (np != ep->e_parent) {
    328 		removeentry(ep);
    329 		ep->e_parent = np;
    330 		ep->e_sibling = np->e_entries;
    331 		np->e_entries = ep;
    332 	}
    333 	cp = rindex(newname, '/') + 1;
    334 	freename(ep->e_name);
    335 	ep->e_name = savename(cp);
    336 	ep->e_namlen = strlen(cp);
    337 	if (strcmp(gentempname(ep), ep->e_name) == 0)
    338 		ep->e_flags |= TMPNAME;
    339 	else
    340 		ep->e_flags &= ~TMPNAME;
    341 }
    342 
    343 /*
    344  * Remove an entry in the tree structure
    345  */
    346 static void
    347 removeentry(ep)
    348 	register struct entry *ep;
    349 {
    350 	register struct entry *np;
    351 
    352 	np = ep->e_parent;
    353 	if (np->e_entries == ep) {
    354 		np->e_entries = ep->e_sibling;
    355 	} else {
    356 		for (np = np->e_entries; np != NULL; np = np->e_sibling) {
    357 			if (np->e_sibling == ep) {
    358 				np->e_sibling = ep->e_sibling;
    359 				break;
    360 			}
    361 		}
    362 		if (np == NULL)
    363 			badentry(ep, "cannot find entry in parent list");
    364 	}
    365 }
    366 
    367 /*
    368  * Table of unused string entries, sorted by length.
    369  *
    370  * Entries are allocated in STRTBLINCR sized pieces so that names
    371  * of similar lengths can use the same entry. The value of STRTBLINCR
    372  * is chosen so that every entry has at least enough space to hold
    373  * a "struct strtbl" header. Thus every entry can be linked onto an
    374  * apprpriate free list.
    375  *
    376  * NB. The macro "allocsize" below assumes that "struct strhdr"
    377  *     has a size that is a power of two.
    378  */
    379 struct strhdr {
    380 	struct strhdr *next;
    381 };
    382 
    383 #define STRTBLINCR	(sizeof(struct strhdr))
    384 #define allocsize(size)	(((size) + 1 + STRTBLINCR - 1) & ~(STRTBLINCR - 1))
    385 
    386 static struct strhdr strtblhdr[allocsize(NAME_MAX) / STRTBLINCR];
    387 
    388 /*
    389  * Allocate space for a name. It first looks to see if it already
    390  * has an appropriate sized entry, and if not allocates a new one.
    391  */
    392 char *
    393 savename(name)
    394 	char *name;
    395 {
    396 	struct strhdr *np;
    397 	long len;
    398 	char *cp;
    399 
    400 	if (name == NULL)
    401 		panic("bad name\n");
    402 	len = strlen(name);
    403 	np = strtblhdr[len / STRTBLINCR].next;
    404 	if (np != NULL) {
    405 		strtblhdr[len / STRTBLINCR].next = np->next;
    406 		cp = (char *)np;
    407 	} else {
    408 		cp = malloc((unsigned)allocsize(len));
    409 		if (cp == NULL)
    410 			panic("no space for string table\n");
    411 	}
    412 	(void) strcpy(cp, name);
    413 	return (cp);
    414 }
    415 
    416 /*
    417  * Free space for a name. The resulting entry is linked onto the
    418  * appropriate free list.
    419  */
    420 void
    421 freename(name)
    422 	char *name;
    423 {
    424 	struct strhdr *tp, *np;
    425 
    426 	tp = &strtblhdr[strlen(name) / STRTBLINCR];
    427 	np = (struct strhdr *)name;
    428 	np->next = tp->next;
    429 	tp->next = np;
    430 }
    431 
    432 /*
    433  * Useful quantities placed at the end of a dumped symbol table.
    434  */
    435 struct symtableheader {
    436 	long	volno;
    437 	long	stringsize;
    438 	long	entrytblsize;
    439 	time_t	dumptime;
    440 	time_t	dumpdate;
    441 	ino_t	maxino;
    442 	long	ntrec;
    443 };
    444 
    445 /*
    446  * dump a snapshot of the symbol table
    447  */
    448 void
    449 dumpsymtable(filename, checkpt)
    450 	char *filename;
    451 	long checkpt;
    452 {
    453 	register struct entry *ep, *tep;
    454 	register ino_t i;
    455 	struct entry temp, *tentry;
    456 	long mynum = 1, stroff = 0;
    457 	FILE *fd;
    458 	struct symtableheader hdr;
    459 
    460 	vprintf(stdout, "Check pointing the restore\n");
    461 	if (Nflag)
    462 		return;
    463 	if ((fd = fopen(filename, "w")) == NULL) {
    464 		fprintf(stderr, "fopen: %s\n", strerror(errno));
    465 		panic("cannot create save file %s for symbol table\n",
    466 			filename);
    467 	}
    468 	clearerr(fd);
    469 	/*
    470 	 * Assign indicies to each entry
    471 	 * Write out the string entries
    472 	 */
    473 	for (i = ROOTINO; i < maxino; i++) {
    474 		for (ep = lookupino(i); ep != NULL; ep = ep->e_links) {
    475 			ep->e_index = mynum++;
    476 			(void) fwrite(ep->e_name, sizeof(char),
    477 			       (int)allocsize(ep->e_namlen), fd);
    478 		}
    479 	}
    480 	/*
    481 	 * Convert pointers to indexes, and output
    482 	 */
    483 	tep = &temp;
    484 	stroff = 0;
    485 	for (i = ROOTINO; i < maxino; i++) {
    486 		for (ep = lookupino(i); ep != NULL; ep = ep->e_links) {
    487 			bcopy((char *)ep, (char *)tep,
    488 				(long)sizeof(struct entry));
    489 			tep->e_name = (char *)stroff;
    490 			stroff += allocsize(ep->e_namlen);
    491 			tep->e_parent = (struct entry *)ep->e_parent->e_index;
    492 			if (ep->e_links != NULL)
    493 				tep->e_links =
    494 					(struct entry *)ep->e_links->e_index;
    495 			if (ep->e_sibling != NULL)
    496 				tep->e_sibling =
    497 					(struct entry *)ep->e_sibling->e_index;
    498 			if (ep->e_entries != NULL)
    499 				tep->e_entries =
    500 					(struct entry *)ep->e_entries->e_index;
    501 			if (ep->e_next != NULL)
    502 				tep->e_next =
    503 					(struct entry *)ep->e_next->e_index;
    504 			(void) fwrite((char *)tep, sizeof(struct entry), 1, fd);
    505 		}
    506 	}
    507 	/*
    508 	 * Convert entry pointers to indexes, and output
    509 	 */
    510 	for (i = 0; i < entrytblsize; i++) {
    511 		if (entry[i] == NULL)
    512 			tentry = NULL;
    513 		else
    514 			tentry = (struct entry *)entry[i]->e_index;
    515 		(void) fwrite((char *)&tentry, sizeof(struct entry *), 1, fd);
    516 	}
    517 	hdr.volno = checkpt;
    518 	hdr.maxino = maxino;
    519 	hdr.entrytblsize = entrytblsize;
    520 	hdr.stringsize = stroff;
    521 	hdr.dumptime = dumptime;
    522 	hdr.dumpdate = dumpdate;
    523 	hdr.ntrec = ntrec;
    524 	(void) fwrite((char *)&hdr, sizeof(struct symtableheader), 1, fd);
    525 	if (ferror(fd)) {
    526 		fprintf(stderr, "fwrite: %s\n", strerror(errno));
    527 		panic("output error to file %s writing symbol table\n",
    528 			filename);
    529 	}
    530 	(void) fclose(fd);
    531 }
    532 
    533 /*
    534  * Initialize a symbol table from a file
    535  */
    536 void
    537 initsymtable(filename)
    538 	char *filename;
    539 {
    540 	char *base;
    541 	long tblsize;
    542 	register struct entry *ep;
    543 	struct entry *baseep, *lep;
    544 	struct symtableheader hdr;
    545 	struct stat stbuf;
    546 	register long i;
    547 	int fd;
    548 
    549 	vprintf(stdout, "Initialize symbol table.\n");
    550 	if (filename == NULL) {
    551 		entrytblsize = maxino / HASHFACTOR;
    552 		entry = (struct entry **)
    553 			calloc((unsigned)entrytblsize, sizeof(struct entry *));
    554 		if (entry == (struct entry **)NULL)
    555 			panic("no memory for entry table\n");
    556 		ep = addentry(".", ROOTINO, NODE);
    557 		ep->e_flags |= NEW;
    558 		return;
    559 	}
    560 	if ((fd = open(filename, O_RDONLY, 0)) < 0) {
    561 		fprintf(stderr, "open: %s\n", strerror(errno));
    562 		panic("cannot open symbol table file %s\n", filename);
    563 	}
    564 	if (fstat(fd, &stbuf) < 0) {
    565 		fprintf(stderr, "stat: %s\n", strerror(errno));
    566 		panic("cannot stat symbol table file %s\n", filename);
    567 	}
    568 	tblsize = stbuf.st_size - sizeof(struct symtableheader);
    569 	base = calloc(sizeof(char), (unsigned)tblsize);
    570 	if (base == NULL)
    571 		panic("cannot allocate space for symbol table\n");
    572 	if (read(fd, base, (int)tblsize) < 0 ||
    573 	    read(fd, (char *)&hdr, sizeof(struct symtableheader)) < 0) {
    574 		fprintf(stderr, "read: %s\n", strerror(errno));
    575 		panic("cannot read symbol table file %s\n", filename);
    576 	}
    577 	switch (command) {
    578 	case 'r':
    579 		/*
    580 		 * For normal continuation, insure that we are using
    581 		 * the next incremental tape
    582 		 */
    583 		if (hdr.dumpdate != dumptime) {
    584 			if (hdr.dumpdate < dumptime)
    585 				fprintf(stderr, "Incremental tape too low\n");
    586 			else
    587 				fprintf(stderr, "Incremental tape too high\n");
    588 			done(1);
    589 		}
    590 		break;
    591 	case 'R':
    592 		/*
    593 		 * For restart, insure that we are using the same tape
    594 		 */
    595 		curfile.action = SKIP;
    596 		dumptime = hdr.dumptime;
    597 		dumpdate = hdr.dumpdate;
    598 		if (!bflag)
    599 			newtapebuf(hdr.ntrec);
    600 		getvol(hdr.volno);
    601 		break;
    602 	default:
    603 		panic("initsymtable called from command %c\n", command);
    604 		break;
    605 	}
    606 	maxino = hdr.maxino;
    607 	entrytblsize = hdr.entrytblsize;
    608 	entry = (struct entry **)
    609 		(base + tblsize - (entrytblsize * sizeof(struct entry *)));
    610 	baseep = (struct entry *)(base + hdr.stringsize - sizeof(struct entry));
    611 	lep = (struct entry *)entry;
    612 	for (i = 0; i < entrytblsize; i++) {
    613 		if (entry[i] == NULL)
    614 			continue;
    615 		entry[i] = &baseep[(long)entry[i]];
    616 	}
    617 	for (ep = &baseep[1]; ep < lep; ep++) {
    618 		ep->e_name = base + (long)ep->e_name;
    619 		ep->e_parent = &baseep[(long)ep->e_parent];
    620 		if (ep->e_sibling != NULL)
    621 			ep->e_sibling = &baseep[(long)ep->e_sibling];
    622 		if (ep->e_links != NULL)
    623 			ep->e_links = &baseep[(long)ep->e_links];
    624 		if (ep->e_entries != NULL)
    625 			ep->e_entries = &baseep[(long)ep->e_entries];
    626 		if (ep->e_next != NULL)
    627 			ep->e_next = &baseep[(long)ep->e_next];
    628 	}
    629 }
    630