diff options
Diffstat (limited to 'ufs/dir.c')
| -rw-r--r-- | ufs/dir.c | 861 |
1 files changed, 861 insertions, 0 deletions
diff --git a/ufs/dir.c b/ufs/dir.c new file mode 100644 index 00000000..d088778e --- /dev/null +++ b/ufs/dir.c @@ -0,0 +1,861 @@ +/* Directory management routines + Copyright (C) 1994 Free Software Foundation + + This program is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2, or (at + your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ + +#include "ufs.h" +#include "dir.h" + +#include <string.h> +#include <stdio.h> + +enum slot_status +{ + /* This means we haven't yet found room for a new entry. */ + LOOKING, + + /* This means that the specified entry is free and should be used. */ + TAKE, + + /* This means that the specified entry has enough room at the end + to hold the new entry. */ + SHRINK, + + /* This means that there is enough space in the block, but not in + any one single entry, so they all have to be shifted to make + room. */ + COMPRESS, + + /* This means that the directory will have to be grown to hold the + entry. */ + EXTEND, + + /* For removal and rename, this means that this is the location + of the entry found. */ + HERE_TIS, +}; + +struct dirstat +{ + /* Type of followp operation expected */ + enum lookup_type type; + + /* One of the statuses above */ + enum slot_status stat; + + /* Mapped address and length of directory */ + vm_address_t mapbuf; + vm_size_t mapextent; + + /* Index of this directory block. */ + int idx; + + /* For stat COMPRESS, this is the address (inside mapbuf) + of the first direct in the directory block to be compressed. */ + /* For stat HERE_TIS, SHRINK, and TAKE, this is the entry referenced. */ + struct direct *entry; + + /* For stat HERE_TIS, type REMOVE, this is the address of the immediately + previous direct in this directory block, or zero if this is the first. */ + struct direct *preventry; +}; + +size_t diskfs_dirstat_size = sizeof (struct dirstat); + +static error_t +dirscanblock (vm_address_t blockoff, struct node *dp, int idx, char *name, + int namelen, enum lookup_type type, struct dirstat *ds, + ino_t *inum); + +/* Implement the diskfs_lookup from the diskfs library. See + <hurd/diskfs.h> for the interface specification. */ +error_t +diskfs_lookup (struct node *dp, char *name, enum lookup_type type, + struct node **npp, struct dirstat *ds, struct protid *cred) +{ + error_t err; + ino_t inum; + int namelen; + int spec_dotdot; + struct node *np = 0; + int retry_dotdot = 0; + memory_object_t memobj; + vm_address_t buf; + vm_size_t buflen; + int blockaddr; + int idx; + + if (npp) + *npp = 0; + + spec_dotdot = type & SPEC_DOTDOT; + type &= ~SPEC_DOTDOT; + + namelen = strlen (name); + + if (!S_ISDIR (dp->dn_stat.st_mode)) + return ENOTDIR; + err = diskfs_access (dp, S_IEXEC, cred); + if (err) + return err; + + try_again: + if (ds) + { + ds->type = LOOKUP; + ds->mapbuf = 0; + ds->mapextent = 0; + } + if (ds && (type == CREATE || type == RENAME)) + ds->stat = LOOKING; + + /* Map in the directory contents. */ + memobj = diskfs_get_filemap (dp); + mach_port_insert_right (mach_task_self (), memobj, memobj, + MACH_MSG_TYPE_MAKE_SEND); + buf = 0; + /* We allow extra space in case we have to do an EXTEND. */ + buflen = round_page (dp->dn_stat.st_size + DIRBLKSIZ); + if (type == LOOKUP) + /* Map read-only; we won't be writing */ + err = vm_map (mach_task_self (), &buf, buflen, 0, 1, memobj, 0, 0, + VM_PROT_READ, VM_PROT_READ, 0); + else + err = vm_map (mach_task_self (), &buf, buflen, 0, 1, memobj, 0, 0, + VM_PROT_READ|VM_PROT_WRITE, VM_PROT_READ|VM_PROT_WRITE, 0); + mach_port_deallocate (mach_task_self (), memobj); + + inum = 0; + + for (blockaddr = buf, idx = 0; + blockaddr - buf < dp->dn_stat.st_size; + blockaddr += DIRBLKSIZ, idx++) + { + err = dirscanblock (blockaddr, dp, idx, name, namelen, type, ds, &inum); + if (!err) + break; + if (err != ENOENT) + { + vm_deallocate (mach_task_self (), buf, buflen); + return err; + } + } + + /* If err is set here, it's ENOENT, and we don't want to + think about that as an error yet. */ + err = 0; + + if (inum) + { + if (namelen != 2 || name[0] != '.' || name[1] != '.') + { + if (inum == dp->dn->number) + { + np = dp; + diskfs_nref (np); + } + else + { + err = iget (inum, &np); + if (err) + goto out; + } + } + + /* We are looking up .. */ + /* Check to see if this is the root of the filesystem. */ + else if (dp->dn->number == 2) + { + err = EAGAIN; + goto out; + } + + /* We can't just do iget, because we would then deadlock. + So we do this. Ick. */ + else if (retry_dotdot) + { + /* Check to see that we got the same answer as last time. */ + if (inum != retry_dotdot) + { + /* Drop what we *thought* was .. (but isn't any more) and + try *again*. */ + diskfs_nput (np); + mutex_unlock (&dp->lock); + err = iget (inum, &np); + mutex_lock (&dp->lock); + if (err) + goto out; + retry_dotdot = inum; + goto try_again; + } + /* Otherwise, we got it fine and np is already set properly. */ + } + else if (!spec_dotdot) + { + /* Lock them in the proper order, and then + repeat the directory scan to see if this is still + right. */ + mutex_unlock (&dp->lock); + err = iget (inum, &np); + mutex_lock (&dp->lock); + if (err) + goto out; + retry_dotdot = inum; + goto try_again; + } + + /* Here below are the spec dotdot cases. */ + else if (type == RENAME || type == REMOVE) + np = ifind (inum); + + else if (type == LOOKUP) + { + diskfs_nput (dp); + err = iget (inum, &np); + if (err) + goto out; + } + else + assert (0); + } + + /* If we will be modifying the directory, make sure it's allowed. */ + if (type == RENAME + || (type == REMOVE && np) + || (type == CREATE && !np)) + { + err = diskfs_checkdirmod (dp, np, cred); + if (err) + goto out; + } + + if ((type == CREATE || type == RENAME) && !np && ds && ds->type == LOOKING) + { + /* We didn't find any room, so mark ds to extend the dir */ + ds->type = CREATE; + ds->stat = EXTEND; + ds->idx = idx; + } + + /* Return to the user; if we can't, release the reference + (and lock) we acquired above. */ + out: + /* Deallocate or save the mapping. */ + if ((err && err != ENOENT) + || !ds + || ds->type == LOOKUP) + vm_deallocate (mach_task_self (), buf, buflen); + else + { + ds->mapbuf = buf; + ds->mapextent = buflen; + } + + if (np) + { + if (err || !npp) + { + if (!spec_dotdot) + { + /* Normal case */ + if (np == dp) + diskfs_nrele (np); + else + diskfs_nput (np); + } + else if (type == RENAME || type == REMOVE) + /* We just did ifind to get np; that allocates + no new references, so we don't have anything to do */ + ; + else if (type == LOOKUP) + /* We did iget */ + diskfs_nput (np); + } + else if (npp) + *npp = np; + } + + return err ? : np ? 0 : ENOENT; +} + +/* Scan block at address BLKADDR (of node DP; block index IDX), for + name NAME of length NAMELEN. Args TYPE, DS are as for + diskfs_lookup. If found, set *INUM to the inode number, else + return ENOENT. */ +static error_t +dirscanblock (vm_address_t blockaddr, struct node *dp, int idx, char *name, + int namelen, enum lookup_type type, + struct dirstat *ds, ino_t *inum) +{ + int nfree = 0; + int needed = 0; + int countup = 0; + vm_address_t currentoff, prevoff; + struct direct *entry; + int nentries = 0; + + if (ds && ds->stat == LOOKING) + { + countup = 1; + needed = DIRSIZ (namelen); + } + + for (currentoff = blockaddr, prevoff = blockaddr; + currentoff < blockaddr + DIRBLKSIZ; + prevoff = currentoff, currentoff += entry->d_reclen) + { + entry = (struct direct *)currentoff; + + if (!entry->d_reclen + || entry->d_reclen % 4 + || entry->d_namlen > MAXNAMLEN + || currentoff + entry->d_reclen > blockaddr + DIRBLKSIZ + || entry->d_name[entry->d_namlen] + || DIRSIZ (entry->d_namlen) > entry->d_reclen + || memchr (entry->d_name, '\0', entry->d_namlen)) + { + fprintf (stderr, "Bad directory entry: inode: %ld offset: %d\n", + dp->dn->number, currentoff - blockaddr); + return ENOENT; + } + + if (countup) + { + int thisfree; + + if (entry->d_ino == 0) + thisfree = entry->d_reclen; + else + thisfree = entry->d_reclen - DIRSIZ (entry->d_namlen); + + if (thisfree >= needed) + { + ds->type = CREATE; + ds->stat = entry->d_ino == 0 ? TAKE : SHRINK; + ds->entry = entry; + ds->idx = idx; + countup = 0; + } + else + { + nfree += thisfree; + if (nfree >= needed) + { + ds->type = CREATE; + ds->stat = COMPRESS; + ds->entry = (struct direct *) blockaddr; + ds->idx = idx; + countup = 0; + } + } + } + + if (entry->d_ino) + nentries++; + + if (entry->d_namlen == namelen + && entry->d_name[0] == name[0] + && entry->d_ino + && !bcmp (entry->d_name, name, namelen)) + break; + } + + if (currentoff >= blockaddr + DIRBLKSIZ) + { + int i; + /* The name is not in this block. */ + + /* Because we scanned the entire block, we should write + down how many entries there were. */ + if (!dp->dn->dirents) + { + dp->dn->dirents = malloc ((dp->dn_stat.st_size / DIRBLKSIZ + 1) + * sizeof (int)); + for (i = 0; i < dp->dn_stat.st_size/DIRBLKSIZ; i++) + dp->dn->dirents[i] = -1; + } + /* Make sure the count is correct if there is one now. */ + assert (dp->dn->dirents[idx] == -1 + || dp->dn->dirents[idx] == nentries); + dp->dn->dirents[idx] = nentries; + + return ENOENT; + } + + /* We have found the required name. */ + + if (ds && type == CREATE) + ds->type = LOOKUP; /* it's invalid now */ + else if (ds && (type == REMOVE || type == RENAME)) + { + ds->type = type; + ds->stat = HERE_TIS; + ds->entry = entry; + ds->idx = idx; + ds->preventry = (struct direct *) prevoff; + } + + *inum = entry->d_ino; + return 0; +} + +/* Following a lookup call for CREATE, this adds a node to a directory. + DP is the directory to be modified; NAME is the name to be entered; + NP is the node being linked in; DS is the cached information returned + by lookup; CRED describes the user making the call. This call may + only be made if the directory has been held locked continuously since + the preceding lookup call, and only if that call returned ENOENT. */ +error_t +diskfs_direnter(struct node *dp, + char *name, + struct node *np, + struct dirstat *ds, + struct protid *cred) +{ + struct direct *new; + int namelen = strlen (name); + int needed = DIRSIZ (namelen); + int oldneeded; + vm_address_t fromoff, tooff; + int totfreed; + error_t err; + + assert (ds->type == CREATE); + + switch (ds->stat) + { + case TAKE: + /* We are supposed to consume this slot. */ + assert (ds->entry->d_ino == 0 && ds->entry->d_reclen >= needed); + + ds->entry->d_ino = np->dn->number; + ds->entry->d_namlen = namelen; + bcopy (name, ds->entry->d_name, namelen + 1); + + break; + + case SHRINK: + /* We are supposed to take the extra space at the end + of this slot. */ + oldneeded = DIRSIZ (ds->entry->d_namlen); + assert (ds->entry->d_reclen - oldneeded >= needed); + + new = (struct direct *) ((vm_address_t) ds->entry + oldneeded); + + new->d_ino = np->dn->number; + new->d_reclen = ds->entry->d_reclen - oldneeded; + new->d_namlen = namelen; + bcopy (name, new->d_name, namelen + 1); + + ds->entry->d_reclen = oldneeded; + + break; + + case COMPRESS: + /* We are supposed to move all the entries to the + front of the block, giving each the minimum + necessary room. This should free up enough space + for the new entry. */ + fromoff = tooff = (vm_address_t) ds->entry; + + while (fromoff < (vm_address_t) ds->entry + DIRBLKSIZ) + { + struct direct *from = (struct direct *)fromoff; + struct direct *to = (struct direct *) tooff; + int fromreclen = from->d_reclen; + + if (from->d_ino != 0) + { + assert (fromoff >= tooff); + + bcopy (from, to, fromreclen); + to->d_reclen = DIRSIZ (to->d_namlen); + + tooff += to->d_reclen; + } + fromoff += fromreclen; + } + + totfreed = (vm_address_t) ds->entry + DIRBLKSIZ - tooff; + assert (totfreed >= needed); + + new = (struct direct *) tooff; + new->d_ino = np->dn->number; + new->d_reclen = totfreed; + new->d_namlen = namelen; + bcopy (name, new->d_name, namelen + 1); + break; + + case EXTEND: + /* Extend the file. */ + while (dp->dn_stat.st_size + DIRBLKSIZ > dp->allocsize) + if (err = diskfs_grow (dp, dp->dn_stat.st_size + DIRBLKSIZ, cred)) + { + vm_deallocate (mach_task_self (), ds->mapbuf, ds->mapextent); + return err; + } + + new = (struct direct *) (ds->mapbuf + dp->dn_stat.st_size); + + dp->dn_stat.st_size += DIRBLKSIZ; + dp->dn_set_ctime = 1; + + new->d_ino = np->dn->number; + new->d_reclen = DIRBLKSIZ; + new->d_namlen = namelen; + bcopy (name, new->d_name, namelen + 1); + break; + + default: + assert (0); + } + + vm_deallocate (mach_task_self (), ds->mapbuf, ds->mapextent); + + if (ds->stat != EXTEND) + { + /* If we are keeping count of this block, then keep the count up + to date. */ + if (dp->dn->dirents && dp->dn->dirents[ds->idx] != -1) + dp->dn->dirents[ds->idx]++; + } + else + { + /* It's cheap, so start a count here even if we aren't counting + anything at all. */ + if (dp->dn->dirents) + { + dp->dn->dirents = realloc (dp->dn->dirents, + (ds->idx + 1) * sizeof (int)); + dp->dn->dirents[ds->idx] = 1; + } + else + { + int i; + dp->dn->dirents = malloc ((ds->idx + 1) * sizeof (int)); + for (i = 0; i < ds->idx; i++) + dp->dn->dirents[i] = -1; + dp->dn->dirents[ds->idx] = 1; + } + } + + diskfs_file_update (dp, 1); + + if (dp->dirmod_reqs) + diskfs_notice_dirchange (dp, DIR_CHANGED_NEW, name); + + return 0; +} + +/* Following a lookup call for REMOVE, this removes the link from the + directory. DP is the directory being changed and DS is the cached + information returned from lookup. This call is only valid if the + directory has been locked continously since the call to lookup, and + only if that call succeeded. */ +error_t +diskfs_dirremove(struct node *dp, + struct dirstat *ds) +{ + assert (ds->type == REMOVE); + assert (ds->stat == HERE_TIS); + + if (ds->preventry == 0) + ds->entry->d_ino = 0; + else + { + assert ((vm_address_t )ds->entry - (vm_address_t)ds->preventry + == ds->preventry->d_reclen); + ds->preventry->d_reclen += ds->entry->d_reclen; + } + + vm_deallocate (mach_task_self (), ds->mapbuf, ds->mapextent); + + /* If we are keeping count of this block, then keep the count up + to date. */ + if (dp->dn->dirents && dp->dn->dirents[ds->idx] != -1) + dp->dn->dirents[ds->idx]--; + + diskfs_file_update (dp, 1); + + if (dp->dirmod_reqs) + diskfs_notice_dirchange (dp, DIR_CHANGED_UNLINK, ds->entry->d_name); + + return 0; +} + + +/* Following a lookup call for RENAME, this changes the inode number + on a directory entry. DP is the directory being changed; NP is + the new node being linked in; DP is the cached information returned + by lookup. This call is only valid if the directory has been locked + continuously since the call to lookup, and only if that call + succeeded. */ +error_t +diskfs_dirrewrite(struct node *dp, + struct node *np, + struct dirstat *ds) +{ + assert (ds->type == RENAME); + assert (ds->stat == HERE_TIS); + + ds->entry->d_ino = np->dn->number; + + vm_deallocate (mach_task_self (), ds->mapbuf, ds->mapextent); + + diskfs_file_update (dp, 1); + + if (dp->dirmod_reqs) + diskfs_notice_dirchange (dp, DIR_CHANGED_RENUMBER, ds->entry->d_name); + + return 0; +} + +/* Tell if DP is an empty directory (has only "." and ".." entries). */ +/* This routine must be called from inside a catch_exception (). */ +int +diskfs_dirempty(struct node *dp, + struct protid *cred) +{ + struct direct *entry; + int curoff; + vm_address_t buf; + memory_object_t memobj; + error_t err; + + memobj = diskfs_get_filemap (dp); + mach_port_insert_right (mach_task_self (), memobj, memobj, + MACH_MSG_TYPE_MAKE_SEND); + buf = 0; + + err = vm_map (mach_task_self (), &buf, dp->dn_stat.st_size, 0, + 1, memobj, 0, 0, VM_PROT_READ, VM_PROT_READ, 0); + mach_port_deallocate (mach_task_self (), memobj); + assert (!err); + + for (curoff = buf; + curoff < buf + dp->dn_stat.st_size; + curoff += entry->d_reclen) + { + entry = (struct direct *) curoff; + + if (entry->d_ino != 0 + && (entry->d_namlen > 2 + || entry->d_name[0] != '.' + || (entry->d_name[1] != '.' + && entry->d_name[1] != '\0'))) + { + vm_deallocate (mach_task_self (), buf, dp->dn_stat.st_size); + return 0; + } + } + vm_deallocate (mach_task_self (), buf, dp->dn_stat.st_size); + return 1; +} + +/* Make DS an invalid dirstat. */ +error_t +diskfs_drop_dirstat (struct node *dp, struct dirstat *ds) +{ + if (ds->type != LOOKUP) + { + assert (ds->mapbuf); + vm_deallocate (mach_task_self (), ds->mapbuf, ds->mapextent); + ds->type = LOOKUP; + } + return 0; +} + + +/* Count the entries in directory block NB for directory DP and + write the answer down in its dirents array. As a side affect + fill BUF with the block. */ +static error_t +count_dirents (struct node *dp, int nb, char *buf) +{ + int amt; + char *offinblk; + struct direct *entry; + int count = 0; + error_t err; + + assert (dp->dn->dirents); + assert ((nb + 1) * DIRBLKSIZ <= dp->dn_stat.st_size); + + err = diskfs_node_rdwr (dp, buf, nb * DIRBLKSIZ, DIRBLKSIZ, 0, 0, &amt); + if (err) + return err; + assert (amt == DIRBLKSIZ); + + for (offinblk = buf; + offinblk < buf + DIRBLKSIZ; + offinblk += entry->d_reclen) + { + entry = (struct direct *) offinblk; + if (entry->d_ino) + count++; + } + + assert (dp->dn->dirents[nb] == -1 || dp->dn->dirents[nb] == count); + dp->dn->dirents[nb] = count; + return 0; +} + +/* Implement the disikfs_get_directs callback as described in + <hurd/diskfs.h>. */ +error_t +diskfs_get_directs (struct node *dp, + int entry, + int nentries, + char **data, + u_int *datacnt, + vm_size_t bufsiz, + int *amt) +{ + int blkno; + int nblks; + int curentry; + char buf[DIRBLKSIZ]; + char *bufp; + int bufvalid; + error_t err; + int i; + char *datap; + struct direct *entryp; + int allocsize; + int checklen; + + nblks = dp->dn_stat.st_size/DIRBLKSIZ; + + if (!dp->dn->dirents) + { + dp->dn->dirents = malloc (nblks * sizeof (int)); + for (i = 0; i < nblks; i++) + dp->dn->dirents[i] = -1; + } + + /* Allocate enough space to hold the maximum we might return */ + if (!bufsiz || bufsiz > dp->dn_stat.st_size) + allocsize = round_page (dp->dn_stat.st_size); + else + allocsize = round_page (bufsiz); + + if (allocsize > *datacnt) + vm_allocate (mach_task_self (), (vm_address_t *) data, allocsize, 1); + + /* Scan through the entries to find ENTRY. If we encounter + a -1 in the process then stop to fill it. When we run + off the end, ENTRY is too big. */ + curentry = 0; + bufvalid = 0; + for (blkno = 0; blkno < nblks; blkno++) + { + if (dp->dn->dirents[blkno] == -1) + { + err = count_dirents (dp, blkno, buf); + if (err) + return err; + bufvalid = 1; + } + + if (curentry + dp->dn->dirents[blkno] > entry) + /* ENTRY starts in this block. */ + break; + + curentry += dp->dn->dirents[blkno]; + + bufvalid = 0; + } + + if (blkno == nblks) + { + *datacnt = 0; + *amt = 0; + return 0; + } + + /* Set bufp appropriately */ + bufp = buf; + if (curentry != entry) + { + /* Look through the block to find out where to start, + setting bufp appropriately. */ + if (!bufvalid) + { + err = diskfs_node_rdwr (dp, buf, blkno * DIRBLKSIZ, DIRBLKSIZ, + 0, 0, &checklen); + if (err) + return err; + assert (checklen == DIRBLKSIZ); + bufvalid = 1; + } + for (i = 0, bufp = buf; + i < entry - curentry && bufp - buf < DIRBLKSIZ; + bufp += ((struct direct *)bufp)->d_reclen, i++) + ; + /* Make sure we didn't run off the end. */ + assert (bufp - buf < DIRBLKSIZ); + } + + i = 0; + datap = *data; + + /* Copy the entries, one at a time. */ + while (((nentries == -1) || (i < nentries)) + && (!bufsiz || (datap - *data < bufsiz) ) + && blkno < nblks) + { + if (!bufvalid) + { + err = diskfs_node_rdwr (dp, buf, blkno * DIRBLKSIZ, DIRBLKSIZ, + 0, 0, &checklen); + if (err) + return err; + assert (checklen == DIRBLKSIZ); + bufvalid = 1; + bufp = buf; + } + + entryp = (struct direct *)bufp; + + if (entryp->d_ino) + { + bcopy (bufp, datap, DIRSIZ (entryp->d_namlen)); + i++; + datap += DIRSIZ (entryp->d_namlen); + } + + bufp += entryp->d_reclen; + if (bufp - buf == DIRBLKSIZ) + { + blkno++; + bufvalid = 0; + } + } + + /* We've copied all we can. If we allocated our own array + but didn't fill all of it, then free whatever memory we didn't use. */ + if (allocsize > *datacnt) + { + if (round_page (datap - *data) < allocsize) + vm_deallocate (mach_task_self (), + (vm_address_t) (*data + round_page (datap - *data)), + allocsize - round_page (datap - *data)); + } + + /* Set variables for return */ + *datacnt = datap - *data; + *amt = i; + return 0; +} |