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