Commit | Line | Data |
---|---|---|
e0519353 KM |
1 | /* Copyright (c) 1983 Regents of the University of California */ |
2 | ||
3 | #ifndef lint | |
4 | static char sccsid[] = "@(#)symtab.c 3.5 (Berkeley) 83/01/16"; | |
5 | #endif | |
6 | ||
7 | #include "restore.h" | |
8 | #include <sys/stat.h> | |
9 | ||
10 | struct symtableheader { | |
11 | long volno; | |
12 | long stringsize; | |
13 | long entrytblsize; | |
14 | time_t dumptime; | |
15 | time_t dumpdate; | |
16 | ino_t maxino; | |
17 | }; | |
18 | ||
19 | static struct entry *freelist = NIL; | |
20 | static struct entry **entry; | |
21 | static long entrytblsize; | |
22 | /* used to scale maxino to get inode hash table size */ | |
23 | #define HASHFACTOR 5 | |
24 | ||
25 | /* | |
26 | * Look up an entry by inode number | |
27 | */ | |
28 | struct entry * | |
29 | lookupino(inum) | |
30 | ino_t inum; | |
31 | { | |
32 | register struct entry *ep; | |
33 | ||
34 | if (inum < ROOTINO || inum >= maxino) | |
35 | return (NIL); | |
36 | for (ep = entry[inum % entrytblsize]; ep != NIL; ep = ep->e_next) | |
37 | if (ep->e_ino == inum) | |
38 | return (ep); | |
39 | return (NIL); | |
40 | } | |
41 | ||
42 | /* | |
43 | * Add an entry into the entry table | |
44 | */ | |
45 | addino(inum, np) | |
46 | ino_t inum; | |
47 | struct entry *np; | |
48 | { | |
49 | struct entry **epp; | |
50 | ||
51 | if (inum < ROOTINO || inum >= maxino) | |
52 | panic("addino: out of range %d\n", inum); | |
53 | epp = &entry[inum % entrytblsize]; | |
54 | np->e_next = *epp; | |
55 | *epp = np; | |
56 | if (dflag) | |
57 | for (np = np->e_next; np != NIL; np = np->e_next) | |
58 | if (np->e_ino == inum) | |
59 | badentry(np, "duplicate inum"); | |
60 | } | |
61 | ||
62 | /* | |
63 | * Delete an entry from the entry table | |
64 | */ | |
65 | deleteino(inum) | |
66 | ino_t inum; | |
67 | { | |
68 | register struct entry *next; | |
69 | struct entry **prev; | |
70 | ||
71 | if (inum < ROOTINO || inum >= maxino) | |
72 | panic("deleteino: out of range %d\n", inum); | |
73 | prev = &entry[inum % entrytblsize]; | |
74 | for (next = *prev; next != NIL; next = next->e_next) { | |
75 | if (next->e_ino == inum) { | |
76 | *prev = next->e_next; | |
77 | return; | |
78 | } | |
79 | prev = &next->e_next; | |
80 | } | |
81 | panic("deleteino: %d not found\n", inum); | |
82 | } | |
83 | ||
84 | /* | |
85 | * Look up an entry by name | |
86 | */ | |
87 | struct entry * | |
88 | lookupname(name) | |
89 | char *name; | |
90 | { | |
91 | register struct entry *ep; | |
92 | register char *np, *cp; | |
93 | char buf[BUFSIZ]; | |
94 | ||
95 | cp = name; | |
96 | for (ep = lookupino(ROOTINO); ep != NIL; ep = ep->e_entries) { | |
97 | for (np = buf; *cp != '/' && *cp != '\0'; ) | |
98 | *np++ = *cp++; | |
99 | *np = '\0'; | |
100 | for ( ; ep != NIL; ep = ep->e_sibling) | |
101 | if (strcmp(ep->e_name, buf) == 0) | |
102 | break; | |
103 | if (ep == NIL) | |
104 | break; | |
105 | if (*cp++ == '\0') | |
106 | return (ep); | |
107 | } | |
108 | return (NIL); | |
109 | } | |
110 | ||
111 | /* | |
112 | * Look up the parent of a pathname | |
113 | */ | |
114 | struct entry * | |
115 | lookupparent(name) | |
116 | char *name; | |
117 | { | |
118 | struct entry *ep; | |
119 | char *tailindex; | |
120 | ||
121 | tailindex = rindex(name, '/'); | |
122 | if (tailindex == 0) | |
123 | return (NIL); | |
124 | *tailindex = '\0'; | |
125 | ep = lookupname(name); | |
126 | *tailindex = '/'; | |
127 | if (ep == NIL) | |
128 | return (NIL); | |
129 | if (ep->e_type != NODE) | |
130 | panic("%s is not a directory\n", name); | |
131 | return (ep); | |
132 | } | |
133 | ||
134 | /* | |
135 | * Determine the current pathname of a node or leaf | |
136 | */ | |
137 | char * | |
138 | myname(ep) | |
139 | register struct entry *ep; | |
140 | { | |
141 | register char *cp; | |
142 | static char namebuf[BUFSIZ]; | |
143 | ||
144 | for (cp = &namebuf[BUFSIZ - 2]; cp > &namebuf[ep->e_namlen]; ) { | |
145 | cp -= ep->e_namlen; | |
146 | bcopy(ep->e_name, cp, (long)ep->e_namlen); | |
147 | if (ep == lookupino(ROOTINO)) | |
148 | return (cp); | |
149 | *(--cp) = '/'; | |
150 | ep = ep->e_parent; | |
151 | } | |
152 | panic("%s: pathname too long\n", cp); | |
153 | return(cp); | |
154 | } | |
155 | ||
156 | /* | |
157 | * add an entry to the symbol table | |
158 | */ | |
159 | struct entry * | |
160 | addentry(name, inum, type) | |
161 | char *name; | |
162 | ino_t inum; | |
163 | int type; | |
164 | { | |
165 | register struct entry *np, *ep; | |
166 | ||
167 | if (freelist != NIL) { | |
168 | np = freelist; | |
169 | freelist = np->e_sibling; | |
170 | bzero((char *)np, (long)sizeof(struct entry)); | |
171 | } else { | |
172 | np = (struct entry *)calloc(1, sizeof(struct entry)); | |
173 | } | |
174 | np->e_ino = inum; | |
175 | np->e_type = type & ~LINK; | |
176 | ep = lookupparent(name); | |
177 | if (ep == NIL) { | |
178 | if (inum != ROOTINO || lookupino(ROOTINO) != NIL) | |
179 | panic("bad name to addentry %s\n", name); | |
180 | np->e_name = savename(name); | |
181 | np->e_namlen = strlen(name); | |
182 | np->e_parent = np; | |
183 | addino(ROOTINO, np); | |
184 | return (np); | |
185 | } | |
186 | np->e_name = savename(rindex(name, '/') + 1); | |
187 | np->e_namlen = strlen(np->e_name); | |
188 | np->e_parent = ep; | |
189 | np->e_sibling = ep->e_entries; | |
190 | ep->e_entries = np; | |
191 | if (type & LINK) { | |
192 | ep = lookupino(inum); | |
193 | if (ep == NIL) | |
194 | panic("link to non-existant name\n"); | |
195 | np->e_links = ep->e_links; | |
196 | ep->e_links = np; | |
197 | } else if (inum != 0) { | |
198 | if (lookupino(inum) != NIL) | |
199 | panic("duplicate entry\n"); | |
200 | addino(inum, np); | |
201 | } | |
202 | return (np); | |
203 | } | |
204 | ||
205 | /* | |
206 | * delete an entry from the symbol table | |
207 | */ | |
208 | freeentry(ep) | |
209 | register struct entry *ep; | |
210 | { | |
211 | register struct entry *np; | |
212 | ||
213 | np = lookupino(ep->e_ino); | |
214 | if (np == NIL) | |
215 | badentry(ep, "lookupino failed"); | |
216 | if (ep->e_flags != REMOVED) | |
217 | badentry(ep, "not marked REMOVED"); | |
218 | if (np->e_type == NODE) { | |
219 | if (np == ep && np->e_links != NIL) | |
220 | badentry(ep, "freeing referenced directory"); | |
221 | if (ep->e_entries != NIL) | |
222 | badentry(ep, "freeing non-empty directory"); | |
223 | } | |
224 | if (np == ep) { | |
225 | deleteino(ep->e_ino); | |
226 | addino(ep->e_ino, ep->e_links); | |
227 | } else { | |
228 | for (; np != NIL; np = np->e_links) { | |
229 | if (np->e_links == ep) { | |
230 | np->e_links = ep->e_links; | |
231 | break; | |
232 | } | |
233 | } | |
234 | if (np == NIL) | |
235 | badentry(ep, "link not found"); | |
236 | } | |
237 | removeentry(ep); | |
238 | free(ep->e_name); | |
239 | ep->e_sibling = freelist; | |
240 | freelist = ep; | |
241 | } | |
242 | ||
243 | /* | |
244 | * Relocate an entry in the tree structure | |
245 | */ | |
246 | moveentry(ep, newname) | |
247 | register struct entry *ep; | |
248 | char *newname; | |
249 | { | |
250 | struct entry *np; | |
251 | char *cp; | |
252 | long len; | |
253 | ||
254 | np = lookupparent(newname); | |
255 | if (np == NIL) | |
256 | badentry(ep, "cannot move ROOT"); | |
257 | if (np != ep->e_parent) { | |
258 | removeentry(ep); | |
259 | ep->e_parent = np; | |
260 | ep->e_sibling = np->e_entries; | |
261 | np->e_entries = ep; | |
262 | } | |
263 | cp = rindex(newname, '/') + 1; | |
264 | len = strlen(cp); | |
265 | if (ep->e_flags & TMPNAME) | |
266 | ep->e_namlen--; | |
267 | if (ep->e_namlen >= len) { | |
268 | strcpy(ep->e_name, cp); | |
269 | } else { | |
270 | free(ep->e_name); | |
271 | ep->e_name = savename(cp); | |
272 | } | |
273 | ep->e_namlen = len; | |
274 | if (cp[len - 1] == TMPCHAR) | |
275 | ep->e_flags |= TMPNAME; | |
276 | else | |
277 | ep->e_flags &= ~TMPNAME; | |
278 | } | |
279 | ||
280 | /* | |
281 | * Remove an entry in the tree structure | |
282 | */ | |
283 | removeentry(ep) | |
284 | register struct entry *ep; | |
285 | { | |
286 | register struct entry *np; | |
287 | ||
288 | np = ep->e_parent; | |
289 | if (np->e_entries == ep) { | |
290 | np->e_entries = ep->e_sibling; | |
291 | } else { | |
292 | for (np = np->e_entries; np != NIL; np = np->e_sibling) { | |
293 | if (np->e_sibling == ep) { | |
294 | np->e_sibling = ep->e_sibling; | |
295 | break; | |
296 | } | |
297 | } | |
298 | if (np == NIL) | |
299 | badentry(ep, "cannot find entry in parent list"); | |
300 | } | |
301 | } | |
302 | ||
303 | /* | |
304 | * allocate space for a name | |
305 | */ | |
306 | char * | |
307 | savename(name) | |
308 | char *name; | |
309 | { | |
310 | long len; | |
311 | char *cp; | |
312 | ||
313 | if (name == NULL) | |
314 | panic("bad name\n"); | |
315 | len = strlen(name) + 2; | |
316 | len = (len + 3) & ~3; | |
317 | cp = malloc((unsigned)len); | |
318 | (void) strcpy(cp, name); | |
319 | return (cp); | |
320 | } | |
321 | ||
322 | /* | |
323 | * dump a snapshot of the symbol table | |
324 | */ | |
325 | dumpsymtable(filename, checkpt) | |
326 | char *filename; | |
327 | long checkpt; | |
328 | { | |
329 | register struct entry *ep; | |
330 | register ino_t i; | |
331 | struct entry *next; | |
332 | long mynum = 0, stroff = 0; | |
333 | FILE *fd; | |
334 | struct symtableheader hdr; | |
335 | ||
336 | vprintf(stdout, "Check pointing the restore\n"); | |
337 | if ((fd = fopen(filename, "w")) == NULL) { | |
338 | perror("fopen"); | |
339 | panic("cannot create save file %s for symbol table\n", | |
340 | filename); | |
341 | } | |
342 | clearerr(fd); | |
343 | /* | |
344 | * Assign indicies to each entry | |
345 | * Write out the string entries | |
346 | */ | |
347 | for (i = ROOTINO; i < maxino; i++) { | |
348 | for (ep = lookupino(i); ep != NIL; ep = ep->e_links) { | |
349 | ep->e_index = mynum++; | |
350 | fwrite(ep->e_name, sizeof(char), (int)ep->e_namlen, fd); | |
351 | ep->e_name = (char *)stroff; | |
352 | stroff += ep->e_namlen; | |
353 | } | |
354 | } | |
355 | /* | |
356 | * Convert entry pointers to indexes, and output | |
357 | */ | |
358 | for (i = 0; i < entrytblsize; i++) { | |
359 | if (entry[i] == NIL) | |
360 | continue; | |
361 | entry[i] = (struct entry *)entry[i]->e_index; | |
362 | } | |
363 | fwrite((char *)entry, sizeof(struct entry *), (int)entrytblsize, fd); | |
364 | /* | |
365 | * Convert pointers to indexes, and output | |
366 | */ | |
367 | for (i = ROOTINO; i < maxino; i++) { | |
368 | for (ep = lookupino(i); ep != NIL; ep = next) { | |
369 | next = ep->e_links; | |
370 | ep->e_parent = (struct entry *)ep->e_parent->e_index; | |
371 | if (ep->e_links != NIL) | |
372 | ep->e_links = | |
373 | (struct entry *)ep->e_links->e_index; | |
374 | if (ep->e_sibling != NIL) | |
375 | ep->e_sibling = | |
376 | (struct entry *)ep->e_sibling->e_index; | |
377 | if (ep->e_entries != NIL) | |
378 | ep->e_entries = | |
379 | (struct entry *)ep->e_entries->e_index; | |
380 | if (ep->e_next != NIL) | |
381 | ep->e_next = | |
382 | (struct entry *)ep->e_next->e_index; | |
383 | fwrite((char *)ep, sizeof(struct entry), 1, fd); | |
384 | } | |
385 | } | |
386 | hdr.volno = checkpt; | |
387 | hdr.maxino = maxino; | |
388 | hdr.entrytblsize = entrytblsize; | |
389 | hdr.stringsize = stroff; | |
390 | hdr.dumptime = dumptime; | |
391 | hdr.dumpdate = dumpdate; | |
392 | fwrite((char *)&hdr, sizeof(struct symtableheader), 1, fd); | |
393 | if (ferror(fd)) { | |
394 | perror("fwrite"); | |
395 | panic("output error to file %s writing symbol table\n", | |
396 | filename); | |
397 | } | |
398 | fclose(fd); | |
399 | } | |
400 | ||
401 | /* | |
402 | * Initialize a symbol table from a file | |
403 | */ | |
404 | initsymtable(filename) | |
405 | char *filename; | |
406 | { | |
407 | char *base; | |
408 | long tblsize; | |
409 | register struct entry *ep; | |
410 | struct entry *baseep, *lep; | |
411 | struct symtableheader hdr; | |
412 | struct stat stbuf; | |
413 | register long i; | |
414 | int fd; | |
415 | ||
416 | vprintf(stdout, "Initialize symbol table.\n"); | |
417 | if (filename == NULL) { | |
418 | entrytblsize = maxino / HASHFACTOR; | |
419 | entry = (struct entry **) | |
420 | calloc((unsigned)entrytblsize, sizeof(struct entry *)); | |
421 | if (entry == (struct entry **)NIL) | |
422 | panic("no memory for entry table\n"); | |
423 | (void)addentry(".", ROOTINO, NODE); | |
424 | return; | |
425 | } | |
426 | if ((fd = open(filename, 0)) < 0) { | |
427 | perror("open"); | |
428 | panic("cannot open symbol table file %s\n", filename); | |
429 | } | |
430 | if (fstat(fd, &stbuf) < 0) { | |
431 | perror("stat"); | |
432 | panic("cannot stat symbol table file %s\n", filename); | |
433 | } | |
434 | tblsize = stbuf.st_size - sizeof(struct symtableheader); | |
435 | base = malloc((unsigned)tblsize); | |
436 | if (base == NULL) | |
437 | panic("cannot allocate space for symbol table\n"); | |
438 | if (read(fd, base, (int)tblsize) < 0 || | |
439 | read(fd, (char *)&hdr, sizeof(struct symtableheader)) < 0) { | |
440 | perror("read"); | |
441 | panic("cannot read symbol table file %s\n", filename); | |
442 | } | |
443 | switch (command) { | |
444 | case 'r': | |
445 | /* | |
446 | * For normal continuation, insure that we are using | |
447 | * the next incremental tape | |
448 | */ | |
449 | if (hdr.dumptime != dumpdate) { | |
450 | if (hdr.dumptime < dumpdate) | |
451 | fprintf(stderr, "Incremental tape too low\n"); | |
452 | else | |
453 | fprintf(stderr, "Incremental tape too high\n"); | |
454 | done(1); | |
455 | } | |
456 | break; | |
457 | case 'R': | |
458 | /* | |
459 | * For restart, insure that we are using the same tape | |
460 | */ | |
461 | curfile.action = SKIP; | |
462 | dumptime = hdr.dumptime; | |
463 | dumpdate = hdr.dumpdate; | |
464 | getvol(hdr.volno); | |
465 | break; | |
466 | default: | |
467 | panic("initsymtable called from command %c\n", command); | |
468 | break; | |
469 | } | |
470 | maxino = hdr.maxino; | |
471 | entrytblsize = hdr.entrytblsize; | |
472 | entry = (struct entry **)(base + hdr.stringsize); | |
473 | baseep = (struct entry *)(&entry[entrytblsize]); | |
474 | lep = (struct entry *)(base + tblsize); | |
475 | for (i = 0; i < entrytblsize; i++) { | |
476 | if (entry[i] == NIL) | |
477 | continue; | |
478 | entry[i] = &baseep[(long)entry[i]]; | |
479 | } | |
480 | for (ep = baseep; ep < lep; ep++) { | |
481 | ep->e_name = base + (long)ep->e_name; | |
482 | ep->e_parent = &baseep[(long)ep->e_parent]; | |
483 | if (ep->e_sibling != NIL) | |
484 | ep->e_sibling = &baseep[(long)ep->e_sibling]; | |
485 | if (ep->e_links != NIL) | |
486 | ep->e_links = &baseep[(long)ep->e_links]; | |
487 | if (ep->e_entries != NIL) | |
488 | ep->e_entries = &baseep[(long)ep->e_entries]; | |
489 | if (ep->e_next != NIL) | |
490 | ep->e_next = &baseep[(long)ep->e_next]; | |
491 | } | |
492 | } |