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