Sync usage with man page.
[netbsd-mini2440.git] / sbin / restore / symtab.c
blob2fec173de8c7c6b621af045e8d8ac1171a9069fe
1 /* $NetBSD: symtab.c,v 1.24 2009/02/22 15:28:43 yamt Exp $ */
3 /*
4 * Copyright (c) 1983, 1993
5 * The Regents of the University of California. All rights reserved.
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.
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.
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.24 2009/02/22 15:28:43 yamt Exp $");
38 #endif
39 #endif /* not lint */
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".
50 #include <sys/param.h>
51 #include <sys/stat.h>
53 #include <ufs/ufs/dinode.h>
55 #include <errno.h>
56 #include <fcntl.h>
57 #include <stdio.h>
58 #include <stdlib.h>
59 #include <string.h>
60 #include <unistd.h>
62 #include "restore.h"
63 #include "extern.h"
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).
72 #define HASHFACTOR 5
73 static struct entry **entry;
74 static long entrytblsize;
76 static void addino(ino_t, struct entry *);
77 static struct entry *lookupparent(const char *);
78 static void removeentry(struct entry *);
81 * Look up an entry by inode number
83 struct entry *
84 lookupino(ino_t inum)
86 struct entry *ep;
88 if (inum < 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);
97 * Add an entry into the entry table
99 static void
100 addino(ino_t inum, struct entry *np)
102 struct entry **epp;
104 if (inum < WINO || inum >= maxino)
105 panic("addino: out of range %llu\n", (unsigned long long)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");
117 * Delete an entry from the entry table
119 void
120 deleteino(ino_t inum)
122 struct entry *next;
123 struct entry **prev;
125 if (inum < WINO || inum >= maxino)
126 panic("deleteino: out of range %llu\n",
127 (unsigned long long)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;
135 prev = &next->e_next;
137 panic("deleteino: %llu not found\n", (unsigned long long)inum);
141 * Look up an entry by name
143 struct entry *
144 lookupname(const char *name)
146 struct entry *ep;
147 char *np;
148 const char *cp;
149 char buf[MAXPATHLEN];
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);
164 return (NULL);
168 * Look up the parent of a pathname
170 static struct entry *
171 lookupparent(const char *name)
173 struct entry *ep;
174 char *tailindex;
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);
190 * Determine the current pathname of a node or leaf
192 char *
193 myname(struct entry *ep)
195 char *cp;
196 static char namebuf[MAXPATHLEN];
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(ROOTINO))
202 return (cp);
203 *(--cp) = '/';
204 ep = ep->e_parent;
206 panic("%s: pathname too long\n", cp);
207 return(cp);
211 * Unused symbol table entries are linked together on a freelist
212 * headed by the following pointer.
214 static struct entry *freelist = NULL;
217 * add an entry to the symbol table
219 struct entry *
220 addentry(const char *name, ino_t inum, int type)
222 struct entry *np, *ep;
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;
234 np = freelist;
235 freelist = np->e_next;
236 memset(np, 0, sizeof(struct entry));
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);
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);
266 return (np);
270 * delete an entry from the symbol table
272 void
273 freeentry(struct entry *ep)
275 struct entry *np;
276 ino_t inum;
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");
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;
302 if (np == NULL)
303 badentry(ep, "link not found");
306 removeentry(ep);
307 freename(ep->e_name);
308 ep->e_next = freelist;
309 freelist = ep;
313 * Relocate an entry in the tree structure
315 void
316 moveentry(struct entry *ep, const char *newname)
318 struct entry *np;
319 char *cp;
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;
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;
341 * Remove an entry in the tree structure
343 static void
344 removeentry(struct entry *ep)
346 struct entry *np;
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;
358 if (np == NULL)
359 badentry(ep, "cannot find entry in parent list");
364 * Table of unused string entries, sorted by length.
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.
372 * NB. The macro "allocsize" below assumes that "struct strhdr"
373 * has a size that is a power of two.
375 struct strhdr {
376 struct strhdr *next;
379 #define STRTBLINCR (sizeof(struct strhdr))
380 #define allocsize(size) (((size) + 1 + STRTBLINCR - 1) & ~(STRTBLINCR - 1))
382 static struct strhdr strtblhdr[allocsize(NAME_MAX) / STRTBLINCR];
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.
388 char *
389 savename(const char *name)
391 struct strhdr *np, *tp;
392 long len, siz;
393 char *cp, *ep;
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;
410 np = tp->next;
411 tp->next = np->next;
412 cp = (char *)np;
413 (void) strcpy(cp, name);
414 return (cp);
418 * Free space for a name. The resulting entry is linked onto the
419 * appropriate free list.
421 void
422 freename(char *name)
424 struct strhdr *tp, *np;
426 tp = &strtblhdr[strlen(name) / STRTBLINCR];
427 np = (struct strhdr *)name;
428 np->next = tp->next;
429 tp->next = np;
433 * Useful quantities placed at the end of a dumped symbol table.
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;
446 * dump a snapshot of the symbol table
448 void
449 dumpsymtable(const char *filename, int32_t checkpt)
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;
459 vprintf(stdout, "Check pointing 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);
467 clearerr(fd);
469 * Assign indicies to each entry
470 * Write out the string entries
472 for (i = 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);
480 * Convert pointers to indexes, and output
482 tep = &temp;
483 stroff = 0;
484 for (i = 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);
507 * Convert entry pointers to indexes, and output
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);
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);
529 (void) fclose(fd);
533 * Initialize a symbol table from a file
535 void
536 initsymtable(const char *filename)
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;
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 == (struct entry **)NULL)
553 panic("no memory for entry table\n");
554 ep = addentry(".", ROOTINO, NODE);
555 ep->e_flags |= NEW;
556 return;
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);
562 if (fstat(fd, &stbuf) < 0) {
563 fprintf(stderr, "stat: %s\n", strerror(errno));
564 panic("cannot stat symbol table file %s\n", filename);
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);
575 switch (command) {
576 case 'r':
578 * For normal continuation, insure that we are using
579 * the next incremental tape
581 if (hdr.dumpdate != dumptime) {
582 if (hdr.dumpdate < dumptime)
583 fprintf(stderr, "Incremental tape too low\n");
584 else
585 fprintf(stderr, "Incremental tape too high\n");
586 exit(1);
588 break;
589 case 'R':
591 * For restart, insure that we are using the same tape
593 curfile.action = SKIP;
594 dumptime = hdr.dumptime;
595 dumpdate = hdr.dumpdate;
596 if (!bflag)
597 newtapebuf(hdr.ntrec);
598 getvol(hdr.volno);
599 break;
600 default:
601 panic("initsymtable called from command %c\n", command);
602 break;
604 maxino = hdr.maxino;
605 entrytblsize = hdr.entrytblsize;
606 entry = (struct entry **)
607 (base + tblsize - (entrytblsize * sizeof(struct entry *)));
608 baseep = (struct entry *)(base + hdr.stringsize - sizeof(struct entry));
609 lep = (struct entry *)entry;
610 for (i = 0; i < entrytblsize; i++) {
611 if (entry[i] == NULL)
612 continue;
613 entry[i] = &baseep[(long)entry[i]];
615 for (ep = &baseep[1]; ep < lep; ep++) {
616 ep->e_name = base + (long)ep->e_name;
617 ep->e_parent = &baseep[(long)ep->e_parent];
618 if (ep->e_sibling != NULL)
619 ep->e_sibling = &baseep[(long)ep->e_sibling];
620 if (ep->e_links != NULL)
621 ep->e_links = &baseep[(long)ep->e_links];
622 if (ep->e_entries != NULL)
623 ep->e_entries = &baseep[(long)ep->e_entries];
624 if (ep->e_next != NULL)
625 ep->e_next = &baseep[(long)ep->e_next];