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
66 static struct entry **entry;
67 static long entrytblsize;
68
69 static void addino(ino_t, struct entry *);
70 static struct entry *lookupparent(char *);
71 static void removeentry(struct entry *);
72
73 /*
74 * Look up an entry by inode number
75 */
76 struct entry *
lookupino(ino_t inum)77 lookupino(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 */
92 static void
addino(ino_t inum,struct entry * np)93 addino(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 */
112 void
deleteino(ino_t inum)113 deleteino(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 */
135 struct entry *
lookupname(char * name)136 lookupname(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 */
164 static struct entry *
lookupparent(char * name)165 lookupparent(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 */
186 char *
myname(struct entry * ep)187 myname(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 */
208 static struct entry *freelist = NULL;
209
210 /*
211 * add an entry to the symbol table
212 */
213 struct entry *
addentry(char * name,ino_t inum,int type)214 addentry(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 */
261 void
freeentry(struct entry * ep)262 freeentry(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 */
304 void
moveentry(struct entry * ep,char * newname)305 moveentry(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 */
332 static void
removeentry(struct entry * ep)333 removeentry(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 */
364 struct strhdr {
365 struct strhdr *next;
366 };
367
368 #define STRTBLINCR (sizeof(struct strhdr))
369 #define allocsize(size) roundup2((size) + 1, STRTBLINCR)
370
371 static 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 */
377 char *
savename(char * name)378 savename(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 */
404 void
freename(char * name)405 freename(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 */
418 struct 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 */
431 void
dumpsymtable(char * filename,long checkpt)432 dumpsymtable(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 */
517 void
initsymtable(char * filename)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((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