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 * 4. 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.
16 *
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
27 * SUCH DAMAGE.
28 */
29
30#ifndef lint
31#if 0
32static char sccsid[] = "@(#)symtab.c	8.3 (Berkeley) 4/28/95";
33#endif
34static const char rcsid[] =
35  "$FreeBSD$";
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 <limits.h>
55#include <stdio.h>
56#include <stdlib.h>
57#include <string.h>
58#include <unistd.h>
59
60#include "restore.h"
61#include "extern.h"
62
63/*
64 * The following variables define the inode symbol table.
65 * The primary hash table is dynamically allocated based on
66 * the number of inodes in the file system (maxino), scaled by
67 * HASHFACTOR. The variable "entry" points to the hash table;
68 * the variable "entrytblsize" indicates its size (in entries).
69 */
70#define HASHFACTOR 5
71static struct entry **entry;
72static long entrytblsize;
73
74static void		 addino(ino_t, struct entry *);
75static struct entry	*lookupparent(char *);
76static void		 removeentry(struct entry *);
77
78/*
79 * Look up an entry by inode number
80 */
81struct entry *
82lookupino(ino_t inum)
83{
84	struct entry *ep;
85
86	if (inum < WINO || 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 */
97static void
98addino(ino_t inum, struct entry *np)
99{
100	struct entry **epp;
101
102	if (inum < WINO || inum >= maxino)
103		panic("addino: out of range %d\n", inum);
104	epp = &entry[inum % entrytblsize];
105	np->e_ino = inum;
106	np->e_next = *epp;
107	*epp = np;
108	if (dflag)
109		for (np = np->e_next; np != NULL; np = np->e_next)
110			if (np->e_ino == inum)
111				badentry(np, "duplicate inum");
112}
113
114/*
115 * Delete an entry from the entry table
116 */
117void
118deleteino(ino_t inum)
119{
120	struct entry *next;
121	struct entry **prev;
122
123	if (inum < WINO || inum >= maxino)
124		panic("deleteino: out of range %d\n", inum);
125	prev = &entry[inum % entrytblsize];
126	for (next = *prev; next != NULL; next = next->e_next) {
127		if (next->e_ino == inum) {
128			next->e_ino = 0;
129			*prev = next->e_next;
130			return;
131		}
132		prev = &next->e_next;
133	}
134	panic("deleteino: %d not found\n", inum);
135}
136
137/*
138 * Look up an entry by name
139 */
140struct entry *
141lookupname(char *name)
142{
143	struct entry *ep;
144	char *np, *cp;
145	char buf[MAXPATHLEN];
146
147	cp = name;
148	for (ep = lookupino(ROOTINO); ep != NULL; ep = ep->e_entries) {
149		for (np = buf; *cp != '/' && *cp != '\0' &&
150				np < &buf[sizeof(buf)]; )
151			*np++ = *cp++;
152		if (np == &buf[sizeof(buf)])
153			break;
154		*np = '\0';
155		for ( ; ep != NULL; ep = ep->e_sibling)
156			if (strcmp(ep->e_name, buf) == 0)
157				break;
158		if (ep == NULL)
159			break;
160		if (*cp++ == '\0')
161			return (ep);
162	}
163	return (NULL);
164}
165
166/*
167 * Look up the parent of a pathname
168 */
169static struct entry *
170lookupparent(char *name)
171{
172	struct entry *ep;
173	char *tailindex;
174
175	tailindex = strrchr(name, '/');
176	if (tailindex == NULL)
177		return (NULL);
178	*tailindex = '\0';
179	ep = lookupname(name);
180	*tailindex = '/';
181	if (ep == NULL)
182		return (NULL);
183	if (ep->e_type != NODE)
184		panic("%s is not a directory\n", name);
185	return (ep);
186}
187
188/*
189 * Determine the current pathname of a node or leaf
190 */
191char *
192myname(struct entry *ep)
193{
194	char *cp;
195	static char namebuf[MAXPATHLEN];
196
197	for (cp = &namebuf[MAXPATHLEN - 2]; cp > &namebuf[ep->e_namlen]; ) {
198		cp -= ep->e_namlen;
199		memmove(cp, ep->e_name, (long)ep->e_namlen);
200		if (ep == lookupino(ROOTINO))
201			return (cp);
202		*(--cp) = '/';
203		ep = ep->e_parent;
204	}
205	panic("%s: pathname too long\n", cp);
206	return(cp);
207}
208
209/*
210 * Unused symbol table entries are linked together on a free list
211 * headed by the following pointer.
212 */
213static struct entry *freelist = NULL;
214
215/*
216 * add an entry to the symbol table
217 */
218struct entry *
219addentry(char *name, ino_t inum, int type)
220{
221	struct entry *np, *ep;
222
223	if (freelist != NULL) {
224		np = freelist;
225		freelist = np->e_next;
226		memset(np, 0, (long)sizeof(struct entry));
227	} else {
228		np = (struct entry *)calloc(1, sizeof(struct entry));
229		if (np == NULL)
230			panic("no memory to extend symbol table\n");
231	}
232	np->e_type = type & ~LINK;
233	ep = lookupparent(name);
234	if (ep == NULL) {
235		if (inum != ROOTINO || lookupino(ROOTINO) != NULL)
236			panic("bad name to addentry %s\n", name);
237		np->e_name = savename(name);
238		np->e_namlen = strlen(name);
239		np->e_parent = np;
240		addino(ROOTINO, np);
241		return (np);
242	}
243	np->e_name = savename(strrchr(name, '/') + 1);
244	np->e_namlen = strlen(np->e_name);
245	np->e_parent = ep;
246	np->e_sibling = ep->e_entries;
247	ep->e_entries = np;
248	if (type & LINK) {
249		ep = lookupino(inum);
250		if (ep == NULL)
251			panic("link to non-existent name\n");
252		np->e_ino = inum;
253		np->e_links = ep->e_links;
254		ep->e_links = np;
255	} else if (inum != 0) {
256		if (lookupino(inum) != NULL)
257			panic("duplicate entry\n");
258		addino(inum, np);
259	}
260	return (np);
261}
262
263/*
264 * delete an entry from the symbol table
265 */
266void
267freeentry(struct entry *ep)
268{
269	struct entry *np;
270	ino_t inum;
271
272	if (ep->e_flags != REMOVED)
273		badentry(ep, "not marked REMOVED");
274	if (ep->e_type == NODE) {
275		if (ep->e_links != NULL)
276			badentry(ep, "freeing referenced directory");
277		if (ep->e_entries != NULL)
278			badentry(ep, "freeing non-empty directory");
279	}
280	if (ep->e_ino != 0) {
281		np = lookupino(ep->e_ino);
282		if (np == NULL)
283			badentry(ep, "lookupino failed");
284		if (np == ep) {
285			inum = ep->e_ino;
286			deleteino(inum);
287			if (ep->e_links != NULL)
288				addino(inum, ep->e_links);
289		} else {
290			for (; np != NULL; np = np->e_links) {
291				if (np->e_links == ep) {
292					np->e_links = ep->e_links;
293					break;
294				}
295			}
296			if (np == NULL)
297				badentry(ep, "link not found");
298		}
299	}
300	removeentry(ep);
301	freename(ep->e_name);
302	ep->e_next = freelist;
303	freelist = ep;
304}
305
306/*
307 * Relocate an entry in the tree structure
308 */
309void
310moveentry(struct entry *ep, char *newname)
311{
312	struct entry *np;
313	char *cp;
314
315	np = lookupparent(newname);
316	if (np == NULL)
317		badentry(ep, "cannot move ROOT");
318	if (np != ep->e_parent) {
319		removeentry(ep);
320		ep->e_parent = np;
321		ep->e_sibling = np->e_entries;
322		np->e_entries = ep;
323	}
324	cp = strrchr(newname, '/') + 1;
325	freename(ep->e_name);
326	ep->e_name = savename(cp);
327	ep->e_namlen = strlen(cp);
328	if (strcmp(gentempname(ep), ep->e_name) == 0)
329		ep->e_flags |= TMPNAME;
330	else
331		ep->e_flags &= ~TMPNAME;
332}
333
334/*
335 * Remove an entry in the tree structure
336 */
337static void
338removeentry(struct entry *ep)
339{
340	struct entry *np;
341
342	np = ep->e_parent;
343	if (np->e_entries == ep) {
344		np->e_entries = ep->e_sibling;
345	} else {
346		for (np = np->e_entries; np != NULL; np = np->e_sibling) {
347			if (np->e_sibling == ep) {
348				np->e_sibling = ep->e_sibling;
349				break;
350			}
351		}
352		if (np == NULL)
353			badentry(ep, "cannot find entry in parent list");
354	}
355}
356
357/*
358 * Table of unused string entries, sorted by length.
359 *
360 * Entries are allocated in STRTBLINCR sized pieces so that names
361 * of similar lengths can use the same entry. The value of STRTBLINCR
362 * is chosen so that every entry has at least enough space to hold
363 * a "struct strtbl" header. Thus every entry can be linked onto an
364 * appropriate free list.
365 *
366 * NB. The macro "allocsize" below assumes that "struct strhdr"
367 *     has a size that is a power of two.
368 */
369struct strhdr {
370	struct strhdr *next;
371};
372
373#define STRTBLINCR	(sizeof(struct strhdr))
374#define allocsize(size)	(((size) + 1 + STRTBLINCR - 1) & ~(STRTBLINCR - 1))
375
376static struct strhdr strtblhdr[allocsize(NAME_MAX) / STRTBLINCR];
377
378/*
379 * Allocate space for a name. It first looks to see if it already
380 * has an appropriate sized entry, and if not allocates a new one.
381 */
382char *
383savename(char *name)
384{
385	struct strhdr *np;
386	long len;
387	char *cp;
388
389	if (name == NULL)
390		panic("bad name\n");
391	len = strlen(name);
392	np = strtblhdr[len / STRTBLINCR].next;
393	if (np != NULL) {
394		strtblhdr[len / STRTBLINCR].next = np->next;
395		cp = (char *)np;
396	} else {
397		cp = malloc((unsigned)allocsize(len));
398		if (cp == NULL)
399			panic("no space for string table\n");
400	}
401	(void) strcpy(cp, name);
402	return (cp);
403}
404
405/*
406 * Free space for a name. The resulting entry is linked onto the
407 * appropriate free list.
408 */
409void
410freename(char *name)
411{
412	struct strhdr *tp, *np;
413
414	tp = &strtblhdr[strlen(name) / STRTBLINCR];
415	np = (struct strhdr *)name;
416	np->next = tp->next;
417	tp->next = np;
418}
419
420/*
421 * Useful quantities placed at the end of a dumped symbol table.
422 */
423struct symtableheader {
424	int32_t	volno;
425	int32_t	stringsize;
426	int32_t	entrytblsize;
427	time_t	dumptime;
428	time_t	dumpdate;
429	ino_t	maxino;
430	int32_t	ntrec;
431};
432
433/*
434 * dump a snapshot of the symbol table
435 */
436void
437dumpsymtable(char *filename, long checkpt)
438{
439	struct entry *ep, *tep;
440	ino_t i;
441	struct entry temp, *tentry;
442	long mynum = 1, stroff = 0;
443	FILE *fd;
444	struct symtableheader hdr;
445
446	vprintf(stdout, "Checkpointing the restore\n");
447	if (Nflag)
448		return;
449	if ((fd = fopen(filename, "w")) == NULL) {
450		fprintf(stderr, "fopen: %s\n", strerror(errno));
451		panic("cannot create save file %s for symbol table\n",
452			filename);
453		done(1);
454	}
455	clearerr(fd);
456	/*
457	 * Assign indices to each entry
458	 * Write out the string entries
459	 */
460	for (i = WINO; i <= maxino; i++) {
461		for (ep = lookupino(i); ep != NULL; ep = ep->e_links) {
462			ep->e_index = mynum++;
463			(void) fwrite(ep->e_name, sizeof(char),
464			       (int)allocsize(ep->e_namlen), fd);
465		}
466	}
467	/*
468	 * Convert pointers to indexes, and output
469	 */
470	tep = &temp;
471	stroff = 0;
472	for (i = WINO; i <= maxino; i++) {
473		for (ep = lookupino(i); ep != NULL; ep = ep->e_links) {
474			memmove(tep, ep, (long)sizeof(struct entry));
475			tep->e_name = (char *)stroff;
476			stroff += allocsize(ep->e_namlen);
477			tep->e_parent = (struct entry *)ep->e_parent->e_index;
478			if (ep->e_links != NULL)
479				tep->e_links =
480					(struct entry *)ep->e_links->e_index;
481			if (ep->e_sibling != NULL)
482				tep->e_sibling =
483					(struct entry *)ep->e_sibling->e_index;
484			if (ep->e_entries != NULL)
485				tep->e_entries =
486					(struct entry *)ep->e_entries->e_index;
487			if (ep->e_next != NULL)
488				tep->e_next =
489					(struct entry *)ep->e_next->e_index;
490			(void) fwrite((char *)tep, sizeof(struct entry), 1, fd);
491		}
492	}
493	/*
494	 * Convert entry pointers to indexes, and output
495	 */
496	for (i = 0; i < entrytblsize; i++) {
497		if (entry[i] == NULL)
498			tentry = NULL;
499		else
500			tentry = (struct entry *)entry[i]->e_index;
501		(void) fwrite((char *)&tentry, sizeof(struct entry *), 1, fd);
502	}
503	hdr.volno = checkpt;
504	hdr.maxino = maxino;
505	hdr.entrytblsize = entrytblsize;
506	hdr.stringsize = stroff;
507	hdr.dumptime = dumptime;
508	hdr.dumpdate = dumpdate;
509	hdr.ntrec = ntrec;
510	(void) fwrite((char *)&hdr, sizeof(struct symtableheader), 1, fd);
511	if (ferror(fd)) {
512		fprintf(stderr, "fwrite: %s\n", strerror(errno));
513		panic("output error to file %s writing symbol table\n",
514			filename);
515	}
516	(void) fclose(fd);
517}
518
519/*
520 * Initialize a symbol table from a file
521 */
522void
523initsymtable(char *filename)
524{
525	char *base;
526	long tblsize;
527	struct entry *ep;
528	struct entry *baseep, *lep;
529	struct symtableheader hdr;
530	struct stat stbuf;
531	long i;
532	int fd;
533
534	vprintf(stdout, "Initialize symbol table.\n");
535	if (filename == NULL) {
536		entrytblsize = maxino / HASHFACTOR;
537		entry = (struct entry **)
538			calloc((unsigned)entrytblsize, sizeof(struct entry *));
539		if (entry == (struct entry **)NULL)
540			panic("no memory for entry table\n");
541		ep = addentry(".", ROOTINO, NODE);
542		ep->e_flags |= NEW;
543		return;
544	}
545	if ((fd = open(filename, O_RDONLY, 0)) < 0) {
546		fprintf(stderr, "open: %s\n", strerror(errno));
547		panic("cannot open symbol table file %s\n", filename);
548	}
549	if (fstat(fd, &stbuf) < 0) {
550		fprintf(stderr, "stat: %s\n", strerror(errno));
551		panic("cannot stat symbol table file %s\n", filename);
552	}
553	tblsize = stbuf.st_size - sizeof(struct symtableheader);
554	base = calloc(sizeof(char), (unsigned)tblsize);
555	if (base == NULL)
556		panic("cannot allocate space for symbol table\n");
557	if (read(fd, base, (int)tblsize) < 0 ||
558	    read(fd, (char *)&hdr, sizeof(struct symtableheader)) < 0) {
559		fprintf(stderr, "read: %s\n", strerror(errno));
560		panic("cannot read symbol table file %s\n", filename);
561	}
562	switch (command) {
563	case 'r':
564		/*
565		 * For normal continuation, insure that we are using
566		 * the next incremental tape
567		 */
568		if (hdr.dumpdate != dumptime) {
569			if (hdr.dumpdate < dumptime)
570				fprintf(stderr, "Incremental tape too low\n");
571			else
572				fprintf(stderr, "Incremental tape too high\n");
573			done(1);
574		}
575		break;
576	case 'R':
577		/*
578		 * For restart, insure that we are using the same tape
579		 */
580		curfile.action = SKIP;
581		dumptime = hdr.dumptime;
582		dumpdate = hdr.dumpdate;
583		if (!bflag)
584			newtapebuf(hdr.ntrec);
585		getvol(hdr.volno);
586		break;
587	default:
588		panic("initsymtable called from command %c\n", command);
589		break;
590	}
591	maxino = hdr.maxino;
592	entrytblsize = hdr.entrytblsize;
593	entry = (struct entry **)
594		(base + tblsize - (entrytblsize * sizeof(struct entry *)));
595	baseep = (struct entry *)(base + hdr.stringsize - sizeof(struct entry));
596	lep = (struct entry *)entry;
597	for (i = 0; i < entrytblsize; i++) {
598		if (entry[i] == NULL)
599			continue;
600		entry[i] = &baseep[(long)entry[i]];
601	}
602	for (ep = &baseep[1]; ep < lep; ep++) {
603		ep->e_name = base + (long)ep->e_name;
604		ep->e_parent = &baseep[(long)ep->e_parent];
605		if (ep->e_sibling != NULL)
606			ep->e_sibling = &baseep[(long)ep->e_sibling];
607		if (ep->e_links != NULL)
608			ep->e_links = &baseep[(long)ep->e_links];
609		if (ep->e_entries != NULL)
610			ep->e_entries = &baseep[(long)ep->e_entries];
611		if (ep->e_next != NULL)
612			ep->e_next = &baseep[(long)ep->e_next];
613	}
614}
615