symtab.c revision 1.1.1.2 1 /*
2 * Copyright (c) 1983, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. All advertising materials mentioning features or use of this software
14 * must display the following acknowledgement:
15 * This product includes software developed by the University of
16 * California, Berkeley and its contributors.
17 * 4. Neither the name of the University nor the names of its contributors
18 * may be used to endorse or promote products derived from this software
19 * without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 */
33
34 #ifndef lint
35 static char sccsid[] = "@(#)symtab.c 8.1 (Berkeley) 6/5/93";
36 #endif /* not lint */
37
38 /*
39 * These routines maintain the symbol table which tracks the state
40 * of the file system being restored. They provide lookup by either
41 * name or inode number. They also provide for creation, deletion,
42 * and renaming of entries. Because of the dynamic nature of pathnames,
43 * names should not be saved, but always constructed just before they
44 * are needed, by calling "myname".
45 */
46
47 #include <sys/param.h>
48 #include <sys/stat.h>
49
50 #include <ufs/ufs/dinode.h>
51
52 #include <errno.h>
53 #include <fcntl.h>
54 #include <stdio.h>
55 #include <stdlib.h>
56 #include <string.h>
57 #include <unistd.h>
58
59 #include "restore.h"
60 #include "extern.h"
61
62 /*
63 * The following variables define the inode symbol table.
64 * The primary hash table is dynamically allocated based on
65 * the number of inodes in the file system (maxino), scaled by
66 * HASHFACTOR. The variable "entry" points to the hash table;
67 * the variable "entrytblsize" indicates its size (in entries).
68 */
69 #define HASHFACTOR 5
70 static struct entry **entry;
71 static long entrytblsize;
72
73 static void addino __P((ino_t, struct entry *));
74 static struct entry *lookupparent __P((char *));
75 static void removeentry __P((struct entry *));
76
77 /*
78 * Look up an entry by inode number
79 */
80 struct entry *
81 lookupino(inum)
82 ino_t inum;
83 {
84 register struct entry *ep;
85
86 if (inum < ROOTINO || inum >= maxino)
87 return (NULL);
88 for (ep = entry[inum % entrytblsize]; ep != NULL; ep = ep->e_next)
89 if (ep->e_ino == inum)
90 return (ep);
91 return (NULL);
92 }
93
94 /*
95 * Add an entry into the entry table
96 */
97 static void
98 addino(inum, np)
99 ino_t inum;
100 struct entry *np;
101 {
102 struct entry **epp;
103
104 if (inum < ROOTINO || inum >= maxino)
105 panic("addino: out of range %d\n", 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
120 deleteino(inum)
121 ino_t inum;
122 {
123 register struct entry *next;
124 struct entry **prev;
125
126 if (inum < ROOTINO || inum >= maxino)
127 panic("deleteino: out of range %d\n", 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: %d not found\n", inum);
138 }
139
140 /*
141 * Look up an entry by name
142 */
143 struct entry *
144 lookupname(name)
145 char *name;
146 {
147 register struct entry *ep;
148 register char *np, *cp;
149 char buf[MAXPATHLEN];
150
151 cp = name;
152 for (ep = lookupino(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 *
171 lookupparent(name)
172 char *name;
173 {
174 struct entry *ep;
175 char *tailindex;
176
177 tailindex = rindex(name, '/');
178 if (tailindex == NULL)
179 return (NULL);
180 *tailindex = '\0';
181 ep = lookupname(name);
182 *tailindex = '/';
183 if (ep == NULL)
184 return (NULL);
185 if (ep->e_type != NODE)
186 panic("%s is not a directory\n", name);
187 return (ep);
188 }
189
190 /*
191 * Determine the current pathname of a node or leaf
192 */
193 char *
194 myname(ep)
195 register struct entry *ep;
196 {
197 register 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 bcopy(ep->e_name, cp, (long)ep->e_namlen);
203 if (ep == lookupino(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 freelist
214 * headed by the following pointer.
215 */
216 static struct entry *freelist = NULL;
217
218 /*
219 * add an entry to the symbol table
220 */
221 struct entry *
222 addentry(name, inum, type)
223 char *name;
224 ino_t inum;
225 int type;
226 {
227 register struct entry *np, *ep;
228
229 if (freelist != NULL) {
230 np = freelist;
231 freelist = np->e_next;
232 bzero((char *)np, (long)sizeof(struct entry));
233 } else {
234 np = (struct entry *)calloc(1, sizeof(struct entry));
235 if (np == NULL)
236 panic("no memory to extend symbol table\n");
237 }
238 np->e_type = type & ~LINK;
239 ep = lookupparent(name);
240 if (ep == NULL) {
241 if (inum != ROOTINO || lookupino(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(ROOTINO, np);
247 return (np);
248 }
249 np->e_name = savename(rindex(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-existant 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
273 freeentry(ep)
274 register struct entry *ep;
275 {
276 register struct entry *np;
277 ino_t inum;
278
279 if (ep->e_flags != REMOVED)
280 badentry(ep, "not marked REMOVED");
281 if (ep->e_type == NODE) {
282 if (ep->e_links != NULL)
283 badentry(ep, "freeing referenced directory");
284 if (ep->e_entries != NULL)
285 badentry(ep, "freeing non-empty directory");
286 }
287 if (ep->e_ino != 0) {
288 np = lookupino(ep->e_ino);
289 if (np == NULL)
290 badentry(ep, "lookupino failed");
291 if (np == ep) {
292 inum = ep->e_ino;
293 deleteino(inum);
294 if (ep->e_links != NULL)
295 addino(inum, ep->e_links);
296 } else {
297 for (; np != NULL; np = np->e_links) {
298 if (np->e_links == ep) {
299 np->e_links = ep->e_links;
300 break;
301 }
302 }
303 if (np == NULL)
304 badentry(ep, "link not found");
305 }
306 }
307 removeentry(ep);
308 freename(ep->e_name);
309 ep->e_next = freelist;
310 freelist = ep;
311 }
312
313 /*
314 * Relocate an entry in the tree structure
315 */
316 void
317 moveentry(ep, newname)
318 register struct entry *ep;
319 char *newname;
320 {
321 struct entry *np;
322 char *cp;
323
324 np = lookupparent(newname);
325 if (np == NULL)
326 badentry(ep, "cannot move ROOT");
327 if (np != ep->e_parent) {
328 removeentry(ep);
329 ep->e_parent = np;
330 ep->e_sibling = np->e_entries;
331 np->e_entries = ep;
332 }
333 cp = rindex(newname, '/') + 1;
334 freename(ep->e_name);
335 ep->e_name = savename(cp);
336 ep->e_namlen = strlen(cp);
337 if (strcmp(gentempname(ep), ep->e_name) == 0)
338 ep->e_flags |= TMPNAME;
339 else
340 ep->e_flags &= ~TMPNAME;
341 }
342
343 /*
344 * Remove an entry in the tree structure
345 */
346 static void
347 removeentry(ep)
348 register struct entry *ep;
349 {
350 register struct entry *np;
351
352 np = ep->e_parent;
353 if (np->e_entries == ep) {
354 np->e_entries = ep->e_sibling;
355 } else {
356 for (np = np->e_entries; np != NULL; np = np->e_sibling) {
357 if (np->e_sibling == ep) {
358 np->e_sibling = ep->e_sibling;
359 break;
360 }
361 }
362 if (np == NULL)
363 badentry(ep, "cannot find entry in parent list");
364 }
365 }
366
367 /*
368 * Table of unused string entries, sorted by length.
369 *
370 * Entries are allocated in STRTBLINCR sized pieces so that names
371 * of similar lengths can use the same entry. The value of STRTBLINCR
372 * is chosen so that every entry has at least enough space to hold
373 * a "struct strtbl" header. Thus every entry can be linked onto an
374 * apprpriate free list.
375 *
376 * NB. The macro "allocsize" below assumes that "struct strhdr"
377 * has a size that is a power of two.
378 */
379 struct strhdr {
380 struct strhdr *next;
381 };
382
383 #define STRTBLINCR (sizeof(struct strhdr))
384 #define allocsize(size) (((size) + 1 + STRTBLINCR - 1) & ~(STRTBLINCR - 1))
385
386 static struct strhdr strtblhdr[allocsize(NAME_MAX) / STRTBLINCR];
387
388 /*
389 * Allocate space for a name. It first looks to see if it already
390 * has an appropriate sized entry, and if not allocates a new one.
391 */
392 char *
393 savename(name)
394 char *name;
395 {
396 struct strhdr *np;
397 long len;
398 char *cp;
399
400 if (name == NULL)
401 panic("bad name\n");
402 len = strlen(name);
403 np = strtblhdr[len / STRTBLINCR].next;
404 if (np != NULL) {
405 strtblhdr[len / STRTBLINCR].next = np->next;
406 cp = (char *)np;
407 } else {
408 cp = malloc((unsigned)allocsize(len));
409 if (cp == NULL)
410 panic("no space for string table\n");
411 }
412 (void) strcpy(cp, name);
413 return (cp);
414 }
415
416 /*
417 * Free space for a name. The resulting entry is linked onto the
418 * appropriate free list.
419 */
420 void
421 freename(name)
422 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 long volno;
437 long stringsize;
438 long entrytblsize;
439 time_t dumptime;
440 time_t dumpdate;
441 ino_t maxino;
442 long ntrec;
443 };
444
445 /*
446 * dump a snapshot of the symbol table
447 */
448 void
449 dumpsymtable(filename, checkpt)
450 char *filename;
451 long checkpt;
452 {
453 register struct entry *ep, *tep;
454 register ino_t i;
455 struct entry temp, *tentry;
456 long mynum = 1, stroff = 0;
457 FILE *fd;
458 struct symtableheader hdr;
459
460 vprintf(stdout, "Check pointing the restore\n");
461 if (Nflag)
462 return;
463 if ((fd = fopen(filename, "w")) == NULL) {
464 fprintf(stderr, "fopen: %s\n", strerror(errno));
465 panic("cannot create save file %s for symbol table\n",
466 filename);
467 }
468 clearerr(fd);
469 /*
470 * Assign indicies to each entry
471 * Write out the string entries
472 */
473 for (i = ROOTINO; i < maxino; i++) {
474 for (ep = lookupino(i); ep != NULL; ep = ep->e_links) {
475 ep->e_index = mynum++;
476 (void) fwrite(ep->e_name, sizeof(char),
477 (int)allocsize(ep->e_namlen), fd);
478 }
479 }
480 /*
481 * Convert pointers to indexes, and output
482 */
483 tep = &temp;
484 stroff = 0;
485 for (i = ROOTINO; i < maxino; i++) {
486 for (ep = lookupino(i); ep != NULL; ep = ep->e_links) {
487 bcopy((char *)ep, (char *)tep,
488 (long)sizeof(struct entry));
489 tep->e_name = (char *)stroff;
490 stroff += allocsize(ep->e_namlen);
491 tep->e_parent = (struct entry *)ep->e_parent->e_index;
492 if (ep->e_links != NULL)
493 tep->e_links =
494 (struct entry *)ep->e_links->e_index;
495 if (ep->e_sibling != NULL)
496 tep->e_sibling =
497 (struct entry *)ep->e_sibling->e_index;
498 if (ep->e_entries != NULL)
499 tep->e_entries =
500 (struct entry *)ep->e_entries->e_index;
501 if (ep->e_next != NULL)
502 tep->e_next =
503 (struct entry *)ep->e_next->e_index;
504 (void) fwrite((char *)tep, sizeof(struct entry), 1, fd);
505 }
506 }
507 /*
508 * Convert entry pointers to indexes, and output
509 */
510 for (i = 0; i < entrytblsize; i++) {
511 if (entry[i] == NULL)
512 tentry = NULL;
513 else
514 tentry = (struct entry *)entry[i]->e_index;
515 (void) fwrite((char *)&tentry, sizeof(struct entry *), 1, fd);
516 }
517 hdr.volno = checkpt;
518 hdr.maxino = maxino;
519 hdr.entrytblsize = entrytblsize;
520 hdr.stringsize = stroff;
521 hdr.dumptime = dumptime;
522 hdr.dumpdate = dumpdate;
523 hdr.ntrec = ntrec;
524 (void) fwrite((char *)&hdr, sizeof(struct symtableheader), 1, fd);
525 if (ferror(fd)) {
526 fprintf(stderr, "fwrite: %s\n", strerror(errno));
527 panic("output error to file %s writing symbol table\n",
528 filename);
529 }
530 (void) fclose(fd);
531 }
532
533 /*
534 * Initialize a symbol table from a file
535 */
536 void
537 initsymtable(filename)
538 char *filename;
539 {
540 char *base;
541 long tblsize;
542 register struct entry *ep;
543 struct entry *baseep, *lep;
544 struct symtableheader hdr;
545 struct stat stbuf;
546 register long i;
547 int fd;
548
549 vprintf(stdout, "Initialize symbol table.\n");
550 if (filename == NULL) {
551 entrytblsize = maxino / HASHFACTOR;
552 entry = (struct entry **)
553 calloc((unsigned)entrytblsize, sizeof(struct entry *));
554 if (entry == (struct entry **)NULL)
555 panic("no memory for entry table\n");
556 ep = addentry(".", ROOTINO, NODE);
557 ep->e_flags |= NEW;
558 return;
559 }
560 if ((fd = open(filename, O_RDONLY, 0)) < 0) {
561 fprintf(stderr, "open: %s\n", strerror(errno));
562 panic("cannot open symbol table file %s\n", filename);
563 }
564 if (fstat(fd, &stbuf) < 0) {
565 fprintf(stderr, "stat: %s\n", strerror(errno));
566 panic("cannot stat symbol table file %s\n", filename);
567 }
568 tblsize = stbuf.st_size - sizeof(struct symtableheader);
569 base = calloc(sizeof(char), (unsigned)tblsize);
570 if (base == NULL)
571 panic("cannot allocate space for symbol table\n");
572 if (read(fd, base, (int)tblsize) < 0 ||
573 read(fd, (char *)&hdr, sizeof(struct symtableheader)) < 0) {
574 fprintf(stderr, "read: %s\n", strerror(errno));
575 panic("cannot read symbol table file %s\n", filename);
576 }
577 switch (command) {
578 case 'r':
579 /*
580 * For normal continuation, insure that we are using
581 * the next incremental tape
582 */
583 if (hdr.dumpdate != dumptime) {
584 if (hdr.dumpdate < dumptime)
585 fprintf(stderr, "Incremental tape too low\n");
586 else
587 fprintf(stderr, "Incremental tape too high\n");
588 done(1);
589 }
590 break;
591 case 'R':
592 /*
593 * For restart, insure that we are using the same tape
594 */
595 curfile.action = SKIP;
596 dumptime = hdr.dumptime;
597 dumpdate = hdr.dumpdate;
598 if (!bflag)
599 newtapebuf(hdr.ntrec);
600 getvol(hdr.volno);
601 break;
602 default:
603 panic("initsymtable called from command %c\n", command);
604 break;
605 }
606 maxino = hdr.maxino;
607 entrytblsize = hdr.entrytblsize;
608 entry = (struct entry **)
609 (base + tblsize - (entrytblsize * sizeof(struct entry *)));
610 baseep = (struct entry *)(base + hdr.stringsize - sizeof(struct entry));
611 lep = (struct entry *)entry;
612 for (i = 0; i < entrytblsize; i++) {
613 if (entry[i] == NULL)
614 continue;
615 entry[i] = &baseep[(long)entry[i]];
616 }
617 for (ep = &baseep[1]; ep < lep; ep++) {
618 ep->e_name = base + (long)ep->e_name;
619 ep->e_parent = &baseep[(long)ep->e_parent];
620 if (ep->e_sibling != NULL)
621 ep->e_sibling = &baseep[(long)ep->e_sibling];
622 if (ep->e_links != NULL)
623 ep->e_links = &baseep[(long)ep->e_links];
624 if (ep->e_entries != NULL)
625 ep->e_entries = &baseep[(long)ep->e_entries];
626 if (ep->e_next != NULL)
627 ep->e_next = &baseep[(long)ep->e_next];
628 }
629 }
630