1 /* $NetBSD: symtab.c,v 1.31 2024/02/10 08:24:50 andvar 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
35 static char sccsid[] = "@(#)symtab.c 8.3 (Berkeley) 4/28/95";
36 #else
37 __RCSID("$NetBSD: symtab.c,v 1.31 2024/02/10 08:24:50 andvar 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
73 static struct entry **entry;
74 static long entrytblsize;
75
76 static void addino(ino_t, struct entry *);
77 static struct entry *lookupparent(const char *);
78 static void removeentry(struct entry *);
79
80 /*
81 * Look up an entry by inode number
82 */
83 struct entry *
lookupino(ino_t inum)84 lookupino(ino_t inum)
85 {
86 struct entry *ep;
87
88 if (inum < UFS_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 */
99 static void
addino(ino_t inum,struct entry * np)100 addino(ino_t inum, struct entry *np)
101 {
102 struct entry **epp;
103
104 if (inum < UFS_WINO || inum >= maxino)
105 panic("addino: out of range %ju\n", (uintmax_t)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 */
119 void
deleteino(ino_t inum)120 deleteino(ino_t inum)
121 {
122 struct entry *next;
123 struct entry **prev;
124
125 if (inum < UFS_WINO || inum >= maxino)
126 panic("deleteino: out of range %ju\n",
127 (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 */
143 struct entry *
lookupname(const char * name)144 lookupname(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(UFS_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 */
170 static struct entry *
lookupparent(const char * name)171 lookupparent(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 */
192 char *
myname(struct entry * ep)193 myname(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(UFS_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 */
214 static struct entry *freelist = NULL;
215
216 /*
217 * add an entry to the symbol table
218 */
219 struct entry *
addentry(const char * name,ino_t inum,int type)220 addentry(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 != UFS_ROOTINO || lookupino(UFS_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(UFS_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 */
272 void
freeentry(struct entry * ep)273 freeentry(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 */
315 void
moveentry(struct entry * ep,const char * newname)316 moveentry(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 */
343 static void
removeentry(struct entry * ep)344 removeentry(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 */
375 struct strhdr {
376 struct strhdr *next;
377 };
378
379 #define STRTBLINCR (sizeof(struct strhdr))
380 #define allocsize(size) (((size) + 1 + STRTBLINCR - 1) & ~(STRTBLINCR - 1))
381
382 static 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 */
388 char *
savename(const char * name)389 savename(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 */
421 void
freename(char * name)422 freename(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 */
435 struct 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 */
448 void
dumpsymtable(const char * filename,int32_t checkpt)449 dumpsymtable(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 indices to each entry
470 * Write out the string entries
471 */
472 for (i = UFS_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 = UFS_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 */
535 void
initsymtable(const char * filename)536 initsymtable(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(".", UFS_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