GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: sbin/restore/symtab.c Lines: 0 262 0.0 %
Date: 2016-12-06 Branches: 0 183 0.0 %

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