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