* Copyright (c) 1983 Regents of the University of California.
* All rights reserved. The Berkeley software License Agreement
* specifies the terms and conditions for redistribution.
static char sccsid
[] = "@(#)symtab.c 5.1 (Berkeley) %G%";
* These routines maintain the symbol table which tracks the state
* of the file system being restored. They provide lookup by either
* name or inode number. They also provide for creation, deletion,
* and renaming of entries. Because of the dynamic nature of pathnames,
* names should not be saved, but always constructed just before they
* are needed, by calling "myname".
* The following variables define the inode symbol table.
* The primary hash table is dynamically allocated based on
* the number of inodes in the file system (maxino), scaled by
* HASHFACTOR. The variable "entry" points to the hash table;
* the variable "entrytblsize" indicates its size (in entries).
static struct entry
**entry
;
static long entrytblsize
;
* Look up an entry by inode number
register struct entry
*ep
;
if (inum
< ROOTINO
|| inum
>= maxino
)
for (ep
= entry
[inum
% entrytblsize
]; ep
!= NIL
; ep
= ep
->e_next
)
* Add an entry into the entry table
if (inum
< ROOTINO
|| inum
>= maxino
)
panic("addino: out of range %d\n", inum
);
epp
= &entry
[inum
% entrytblsize
];
for (np
= np
->e_next
; np
!= NIL
; np
= np
->e_next
)
badentry(np
, "duplicate inum");
* Delete an entry from the entry table
register struct entry
*next
;
if (inum
< ROOTINO
|| inum
>= maxino
)
panic("deleteino: out of range %d\n", inum
);
prev
= &entry
[inum
% entrytblsize
];
for (next
= *prev
; next
!= NIL
; next
= next
->e_next
) {
if (next
->e_ino
== inum
) {
panic("deleteino: %d not found\n", inum
);
* Look up an entry by name
register struct entry
*ep
;
for (ep
= lookupino(ROOTINO
); ep
!= NIL
; ep
= ep
->e_entries
) {
for (np
= buf
; *cp
!= '/' && *cp
!= '\0'; )
for ( ; ep
!= NIL
; ep
= ep
->e_sibling
)
if (strcmp(ep
->e_name
, buf
) == 0)
* Look up the parent of a pathname
tailindex
= rindex(name
, '/');
panic("%s is not a directory\n", name
);
* Determine the current pathname of a node or leaf
register struct entry
*ep
;
static char namebuf
[MAXPATHLEN
];
for (cp
= &namebuf
[MAXPATHLEN
- 2]; cp
> &namebuf
[ep
->e_namlen
]; ) {
bcopy(ep
->e_name
, cp
, (long)ep
->e_namlen
);
if (ep
== lookupino(ROOTINO
))
panic("%s: pathname too long\n", cp
);
* Unused symbol table entries are linked together on a freelist
* headed by the following pointer.
static struct entry
*freelist
= NIL
;
* add an entry to the symbol table
addentry(name
, inum
, type
)
register struct entry
*np
, *ep
;
bzero((char *)np
, (long)sizeof(struct entry
));
np
= (struct entry
*)calloc(1, sizeof(struct entry
));
panic("no memory to extend symbol table\n");
np
->e_type
= type
& ~LINK
;
if (inum
!= ROOTINO
|| lookupino(ROOTINO
) != NIL
)
panic("bad name to addentry %s\n", name
);
np
->e_name
= savename(name
);
np
->e_namlen
= strlen(name
);
np
->e_name
= savename(rindex(name
, '/') + 1);
np
->e_namlen
= strlen(np
->e_name
);
np
->e_sibling
= ep
->e_entries
;
panic("link to non-existant name\n");
np
->e_links
= ep
->e_links
;
if (lookupino(inum
) != NIL
)
panic("duplicate entry\n");
* delete an entry from the symbol table
register struct entry
*ep
;
register struct entry
*np
;
if (ep
->e_flags
!= REMOVED
)
badentry(ep
, "not marked REMOVED");
if (ep
->e_type
== NODE
) {
badentry(ep
, "freeing referenced directory");
if (ep
->e_entries
!= NIL
)
badentry(ep
, "freeing non-empty directory");
np
= lookupino(ep
->e_ino
);
badentry(ep
, "lookupino failed");
addino(inum
, ep
->e_links
);
for (; np
!= NIL
; np
= np
->e_links
) {
np
->e_links
= ep
->e_links
;
badentry(ep
, "link not found");
* Relocate an entry in the tree structure
register struct entry
*ep
;
np
= lookupparent(newname
);
badentry(ep
, "cannot move ROOT");
if (np
!= ep
->e_parent
) {
ep
->e_sibling
= np
->e_entries
;
cp
= rindex(newname
, '/') + 1;
ep
->e_name
= savename(cp
);
ep
->e_namlen
= strlen(cp
);
if (strcmp(gentempname(ep
), ep
->e_name
) == 0)
* Remove an entry in the tree structure
register struct entry
*ep
;
register struct entry
*np
;
if (np
->e_entries
== ep
) {
np
->e_entries
= ep
->e_sibling
;
for (np
= np
->e_entries
; np
!= NIL
; np
= np
->e_sibling
) {
if (np
->e_sibling
== ep
) {
np
->e_sibling
= ep
->e_sibling
;
badentry(ep
, "cannot find entry in parent list");
* Table of unused string entries, sorted by length.
* Entries are allocated in STRTBLINCR sized pieces so that names
* of similar lengths can use the same entry. The value of STRTBLINCR
* is chosen so that every entry has at least enough space to hold
* a "struct strtbl" header. Thus every entry can be linked onto an
* NB. The macro "allocsize" below assumes that "struct strhdr"
* has a size that is a power of two.
#define STRTBLINCR (sizeof(struct strhdr))
#define allocsize(size) (((size) + 1 + STRTBLINCR - 1) & ~(STRTBLINCR - 1))
static struct strhdr strtblhdr
[allocsize(MAXNAMLEN
) / STRTBLINCR
];
* Allocate space for a name. It first looks to see if it already
* has an appropriate sized entry, and if not allocates a new one.
np
= strtblhdr
[len
/ STRTBLINCR
].next
;
strtblhdr
[len
/ STRTBLINCR
].next
= np
->next
;
cp
= malloc((unsigned)allocsize(len
));
panic("no space for string table\n");
* Free space for a name. The resulting entry is linked onto the
tp
= &strtblhdr
[strlen(name
) / STRTBLINCR
];
np
= (struct strhdr
*)name
;
* Useful quantities placed at the end of a dumped symbol table.
* dump a snapshot of the symbol table
dumpsymtable(filename
, checkpt
)
register struct entry
*ep
, *tep
;
struct entry temp
, *tentry
;
long mynum
= 1, stroff
= 0;
struct symtableheader hdr
;
vprintf(stdout
, "Check pointing the restore\n");
if ((fd
= fopen(filename
, "w")) == NULL
) {
panic("cannot create save file %s for symbol table\n",
* Assign indicies to each entry
* Write out the string entries
for (i
= ROOTINO
; i
< maxino
; i
++) {
for (ep
= lookupino(i
); ep
!= NIL
; ep
= ep
->e_links
) {
(void) fwrite(ep
->e_name
, sizeof(char),
(int)allocsize(ep
->e_namlen
), fd
);
* Convert pointers to indexes, and output
for (i
= ROOTINO
; i
< maxino
; i
++) {
for (ep
= lookupino(i
); ep
!= NIL
; ep
= ep
->e_links
) {
bcopy((char *)ep
, (char *)tep
,
(long)sizeof(struct entry
));
tep
->e_name
= (char *)stroff
;
stroff
+= allocsize(ep
->e_namlen
);
tep
->e_parent
= (struct entry
*)ep
->e_parent
->e_index
;
(struct entry
*)ep
->e_links
->e_index
;
if (ep
->e_sibling
!= NIL
)
(struct entry
*)ep
->e_sibling
->e_index
;
if (ep
->e_entries
!= NIL
)
(struct entry
*)ep
->e_entries
->e_index
;
(struct entry
*)ep
->e_next
->e_index
;
(void) fwrite((char *)tep
, sizeof(struct entry
), 1, fd
);
* Convert entry pointers to indexes, and output
for (i
= 0; i
< entrytblsize
; i
++) {
tentry
= (struct entry
*)entry
[i
]->e_index
;
(void) fwrite((char *)&tentry
, sizeof(struct entry
*), 1, fd
);
hdr
.entrytblsize
= entrytblsize
;
(void) fwrite((char *)&hdr
, sizeof(struct symtableheader
), 1, fd
);
panic("output error to file %s writing symbol table\n",
* Initialize a symbol table from a file
register struct entry
*ep
;
struct entry
*baseep
, *lep
;
struct symtableheader hdr
;
vprintf(stdout
, "Initialize symbol table.\n");
entrytblsize
= maxino
/ HASHFACTOR
;
entry
= (struct entry
**)
calloc((unsigned)entrytblsize
, sizeof(struct entry
*));
if (entry
== (struct entry
**)NIL
)
panic("no memory for entry table\n");
ep
= addentry(".", ROOTINO
, NODE
);
if ((fd
= open(filename
, 0)) < 0) {
panic("cannot open symbol table file %s\n", filename
);
if (fstat(fd
, &stbuf
) < 0) {
panic("cannot stat symbol table file %s\n", filename
);
tblsize
= stbuf
.st_size
- sizeof(struct symtableheader
);
base
= calloc(sizeof(char), (unsigned)tblsize
);
panic("cannot allocate space for symbol table\n");
if (read(fd
, base
, (int)tblsize
) < 0 ||
read(fd
, (char *)&hdr
, sizeof(struct symtableheader
)) < 0) {
panic("cannot read symbol table file %s\n", filename
);
* For normal continuation, insure that we are using
* the next incremental tape
if (hdr
.dumpdate
!= dumptime
) {
if (hdr
.dumpdate
< dumptime
)
fprintf(stderr
, "Incremental tape too low\n");
fprintf(stderr
, "Incremental tape too high\n");
* For restart, insure that we are using the same tape
panic("initsymtable called from command %c\n", command
);
entrytblsize
= hdr
.entrytblsize
;
entry
= (struct entry
**)
(base
+ tblsize
- (entrytblsize
* sizeof(struct entry
*)));
baseep
= (struct entry
*)(base
+ hdr
.stringsize
- sizeof(struct entry
));
lep
= (struct entry
*)entry
;
for (i
= 0; i
< entrytblsize
; i
++) {
entry
[i
] = &baseep
[(long)entry
[i
]];
for (ep
= &baseep
[1]; ep
< lep
; ep
++) {
ep
->e_name
= base
+ (long)ep
->e_name
;
ep
->e_parent
= &baseep
[(long)ep
->e_parent
];
if (ep
->e_sibling
!= NIL
)
ep
->e_sibling
= &baseep
[(long)ep
->e_sibling
];
ep
->e_links
= &baseep
[(long)ep
->e_links
];
if (ep
->e_entries
!= NIL
)
ep
->e_entries
= &baseep
[(long)ep
->e_entries
];
ep
->e_next
= &baseep
[(long)ep
->e_next
];