summaryrefslogtreecommitdiff
path: root/fs.c
diff options
context:
space:
mode:
authorrsc <rsc>2007-08-22 06:01:32 +0000
committerrsc <rsc>2007-08-22 06:01:32 +0000
commiteaea18cb9cbb86018dae8f1decfa217ecbe85fa5 (patch)
tree98c4a9b852ad9b6aaf16016417cf5eeee0b3857e /fs.c
parent3dcf889c1b5c2c5ddf5b4756f2a731c344f6f08e (diff)
downloadxv6-labs-eaea18cb9cbb86018dae8f1decfa217ecbe85fa5.tar.gz
xv6-labs-eaea18cb9cbb86018dae8f1decfa217ecbe85fa5.tar.bz2
xv6-labs-eaea18cb9cbb86018dae8f1decfa217ecbe85fa5.zip
PDF at http://am.lcs.mit.edu/~rsc/xv6.pdf
Various changes made while offline. + bwrite sector argument is redundant; use b->sector. + reformatting of files for nicer PDF page breaks + distinguish between locked, unlocked inodes in type signatures + change FD_FILE to FD_INODE + move userinit (nee proc0init) to proc.c + move ROOTDEV to param.h + always parenthesize sizeof argument
Diffstat (limited to 'fs.c')
-rw-r--r--fs.c411
1 files changed, 120 insertions, 291 deletions
diff --git a/fs.c b/fs.c
index 8c65f35..69bfd8f 100644
--- a/fs.c
+++ b/fs.c
@@ -7,8 +7,10 @@
// + Names: paths like /usr/rtm/xv6/fs.c for convenient naming.
//
// Disk layout is: superblock, inodes, disk bitmap, data blocks.
-
-// TODO: Check locking!
+//
+// This file contains the low-level file system manipulation
+// routines. The (higher-level) system call implementations
+// are in sysfile.c.
#include "types.h"
#include "stat.h"
@@ -25,7 +27,6 @@
#define min(a, b) ((a) < (b) ? (a) : (b))
static void itrunc(struct inode*);
-static void iupdate(struct inode*);
// Blocks.
@@ -51,7 +52,7 @@ balloc(uint dev)
m = 0x1 << (bi % 8);
if((bp->data[bi/8] & m) == 0) { // is block free?
bp->data[bi/8] |= 0x1 << (bi % 8);
- bwrite(bp, BBLOCK(b, ninodes)); // mark it allocated on disk
+ bwrite(bp); // mark it allocated on disk
brelse(bp);
return b;
}
@@ -74,14 +75,14 @@ bfree(int dev, uint b)
bp = bread(dev, b);
memset(bp->data, 0, BSIZE);
- bwrite(bp, b);
+ bwrite(bp);
brelse(bp);
bp = bread(dev, BBLOCK(b, ninodes));
bi = b % BPB;
m = 0x1 << (bi % 8);
bp->data[bi/8] &= ~m;
- bwrite(bp, BBLOCK(b, ninodes)); // mark it free on disk
+ bwrite(bp); // mark it free on disk
brelse(bp);
}
@@ -98,11 +99,20 @@ bfree(int dev, uint b)
// It is an error to use an inode without holding a reference to it.
//
// Inodes can be marked busy, just like bufs, meaning
-// that some process has logically locked the inode, and other processes
-// are not allowed to look at it. Because the locking can last for
-// a long time (for example, during a disk access), we use a flag
-// like in buffer cache, not spin locks. The inode should always be
-// locked during modifications to it.
+// that some process has exclusive use of the inode.
+// Processes are only allowed to read and write inode
+// metadata and contents when holding the inode's lock.
+// Because inodes locks are held during disk accesses,
+// they are implemented using a flag, as in the buffer cache,
+// not using spin locks. Callers are responsible for locking
+// inodes before passing them to routines in this file; leaving
+// this responsibility with the caller makes it possible for them
+// to create arbitrarily-sized atomic operations.
+//
+// To give maximum control over locking to the callers,
+// the routines in this file that return inode pointers
+// return pointers to *unlocked* inodes. It is the callers'
+// responsibility to lock them before using them.
struct {
struct spinlock lock;
@@ -116,14 +126,8 @@ iinit(void)
}
// Find the inode with number inum on device dev
-// and return the in-memory copy. The returned inode
-// has its reference count incremented (and thus must be
-// idecref'ed), but is *unlocked*, meaning that none of the fields
-// except dev and inum are guaranteed to be initialized.
-// This convention gives the caller maximum control over blocking;
-// it also guarantees that iget will not sleep, which is useful in
-// the early igetroot and when holding other locked inodes.
-struct inode*
+// and return the in-memory copy. h
+static struct uinode*
iget(uint dev, uint inum)
{
struct inode *ip, *empty;
@@ -136,7 +140,7 @@ iget(uint dev, uint inum)
if(ip->ref > 0 && ip->dev == dev && ip->inum == inum){
ip->ref++;
release(&icache.lock);
- return ip;
+ return (struct uinode*)ip;
}
if(empty == 0 && ip->ref == 0) // Remember empty slot.
empty = ip;
@@ -153,28 +157,37 @@ iget(uint dev, uint inum)
ip->flags = 0;
release(&icache.lock);
- return ip;
+ return (struct uinode*)ip;
}
-// Iget the inode for the file system root (/).
-// This gets called before there is a current process: it cannot sleep!
-struct inode*
-igetroot(void)
+// Increment reference count for ip.
+// Returns ip to enable ip = idup(ip1) idiom.
+struct uinode*
+idup(struct uinode *uip)
{
struct inode *ip;
- ip = iget(ROOTDEV, 1);
- return ip;
+
+ ip = (struct inode*)uip;
+ acquire(&icache.lock);
+ ip->ref++;
+ release(&icache.lock);
+ return uip;
}
// Lock the given inode.
-void
-ilock(struct inode *ip)
+struct inode*
+ilock(struct uinode *uip)
{
struct buf *bp;
struct dinode *dip;
+ struct inode *ip;
+
+ ip = (struct inode*)uip;
+ if(ip == 0)
+ return 0;
if(ip->ref < 1)
- panic("ilock");
+ panic("ilock: no refs");
acquire(&icache.lock);
while(ip->flags & I_BUSY)
@@ -193,13 +206,19 @@ ilock(struct inode *ip)
memmove(ip->addrs, dip->addrs, sizeof(ip->addrs));
brelse(bp);
ip->flags |= I_VALID;
+ if(ip->type == 0)
+ panic("ilock: no type");
}
+ return ip;
}
// Unlock the given inode.
-void
+struct uinode*
iunlock(struct inode *ip)
{
+ if(ip == 0)
+ return 0;
+
if(!(ip->flags & I_BUSY) || ip->ref < 1)
panic("iunlock");
@@ -207,36 +226,21 @@ iunlock(struct inode *ip)
ip->flags &= ~I_BUSY;
wakeup(ip);
release(&icache.lock);
-}
-
-// Unlock inode and drop reference.
-void
-iput(struct inode *ip)
-{
- iunlock(ip);
- idecref(ip);
-}
-
-// Increment reference count for ip.
-// Returns ip to enable ip = iincref(ip1) idiom.
-struct inode*
-iincref(struct inode *ip)
-{
- acquire(&icache.lock);
- ip->ref++;
- release(&icache.lock);
- return ip;
+ return (struct uinode*)ip;
}
// Caller holds reference to unlocked ip. Drop reference.
void
-idecref(struct inode *ip)
+iput(struct uinode *uip)
{
+ struct inode *ip;
+
+ ip = (struct inode*)uip;
acquire(&icache.lock);
if(ip->ref == 1 && (ip->flags & I_VALID) && ip->nlink == 0) {
// inode is no longer used: truncate and free inode.
if(ip->flags & I_BUSY)
- panic("idecref busy");
+ panic("iput busy");
ip->flags |= I_BUSY;
release(&icache.lock);
// XXX convince rsc that no one will come find this inode.
@@ -251,7 +255,7 @@ idecref(struct inode *ip)
}
// Allocate a new inode with the given type on device dev.
-struct inode*
+struct uinode*
ialloc(uint dev, short type)
{
int inum, ninodes;
@@ -270,7 +274,7 @@ ialloc(uint dev, short type)
if(dip->type == 0) { // a free inode
memset(dip, 0, sizeof(*dip));
dip->type = type;
- bwrite(bp, IBLOCK(inum)); // mark it allocated on the disk
+ bwrite(bp); // mark it allocated on the disk
brelse(bp);
return iget(dev, inum);
}
@@ -280,7 +284,7 @@ ialloc(uint dev, short type)
}
// Copy inode, which has changed, from memory to disk.
-static void
+void
iupdate(struct inode *ip)
{
struct buf *bp;
@@ -294,7 +298,7 @@ iupdate(struct inode *ip)
dip->nlink = ip->nlink;
dip->size = ip->size;
memmove(dip->addrs, ip->addrs, sizeof(ip->addrs));
- bwrite(bp, IBLOCK(ip->inum));
+ bwrite(bp);
brelse(bp);
}
@@ -306,8 +310,8 @@ iupdate(struct inode *ip)
// listed in the block ip->addrs[INDIRECT].
// Return the disk block address of the nth block in inode ip.
-// If there is no such block: if alloc is set, allocate one, else return -1.
-uint
+// If there is no such block, alloc controls whether one is allocated.
+static uint
bmap(struct inode *ip, uint bn, int alloc)
{
uint addr, *a;
@@ -339,7 +343,7 @@ bmap(struct inode *ip, uint bn, int alloc)
return -1;
}
a[bn] = addr = balloc(ip->dev);
- bwrite(bp, ip->addrs[INDIRECT]);
+ bwrite(bp);
}
brelse(bp);
return addr;
@@ -348,6 +352,7 @@ bmap(struct inode *ip, uint bn, int alloc)
panic("bmap: out of range");
}
+// PAGEBREAK: 30
// Truncate inode (discard contents).
static void
itrunc(struct inode *ip)
@@ -389,6 +394,7 @@ stati(struct inode *ip, struct stat *st)
st->size = ip->size;
}
+//PAGEBREAK!
// Read data from inode.
int
readi(struct inode *ip, char *dst, uint off, uint n)
@@ -416,6 +422,7 @@ readi(struct inode *ip, char *dst, uint off, uint n)
return n;
}
+// PAGEBREAK!
// Write data to inode.
int
writei(struct inode *ip, char *src, uint off, uint n)
@@ -438,7 +445,7 @@ writei(struct inode *ip, char *src, uint off, uint n)
bp = bread(ip->dev, bmap(ip, off/BSIZE, 1));
m = min(n - tot, BSIZE - off%BSIZE);
memmove(bp->data + off%BSIZE, src, m);
- bwrite(bp, bmap(ip, off/BSIZE, 0));
+ bwrite(bp);
brelse(bp);
}
@@ -449,12 +456,10 @@ writei(struct inode *ip, char *src, uint off, uint n)
return n;
}
+//PAGEBREAK!
// Directories
-//
-// Directories are just inodes (files) filled with dirent structures.
-// Compare two names, which are strings with a max length of DIRSIZ.
-static int
+int
namecmp(const char *s, const char *t)
{
int i;
@@ -468,25 +473,9 @@ namecmp(const char *s, const char *t)
return 0;
}
-// Copy one name to another.
-static void
-namecpy(char *s, const char *t)
-{
- int i;
-
- for(i=0; i<DIRSIZ && t[i]; i++)
- s[i] = t[i];
- for(; i<DIRSIZ; i++)
- s[i] = 0;
-}
-
// Look for a directory entry in a directory.
-// If not found, return -1.
-// If found:
-// set *poff to the byte offset of the directory entry
-// set *pinum to the inode number
-// return 0.
-static struct inode*
+// If found, set *poff to byte offset of entry.
+struct uinode*
dirlookup(struct inode *dp, char *name, uint *poff)
{
uint off, inum;
@@ -517,18 +506,29 @@ dirlookup(struct inode *dp, char *name, uint *poff)
return 0;
}
+// Copy one name to another.
+static void
+namecpy(char *s, const char *t)
+{
+ int i;
+
+ for(i=0; i<DIRSIZ && t[i]; i++)
+ s[i] = t[i];
+ for(; i<DIRSIZ; i++)
+ s[i] = 0;
+}
+
// Write a new directory entry (name, ino) into the directory dp.
-// Caller must have locked dp.
-static int
+int
dirlink(struct inode *dp, char *name, uint ino)
{
int off;
struct dirent de;
- struct inode *ip;
+ struct uinode *ip;
- // Double-check that name is not present.
+ // Check that name is not present.
if((ip = dirlookup(dp, name, 0)) != 0){
- idecref(ip);
+ iput(ip);
return -1;
}
@@ -548,49 +548,18 @@ dirlink(struct inode *dp, char *name, uint ino)
return 0;
}
-// Create a new inode named name inside dp
-// and return its locked inode structure.
-// If name already exists, return 0.
-static struct inode*
-dircreat(struct inode *dp, char *name, short type, short major, short minor)
-{
- struct inode *ip;
-
- ip = ialloc(dp->dev, type);
- if(ip == 0)
- return 0;
- ilock(ip);
- ip->major = major;
- ip->minor = minor;
- ip->size = 0;
- ip->nlink = 1;
- iupdate(ip);
-
- if(dirlink(dp, name, ip->inum) < 0){
- ip->nlink = 0;
- iupdate(ip);
- iput(ip);
- return 0;
- }
-
- return ip;
-}
-
// Paths
-// Skip over the next path element in path,
-// saving it in *name and its length in *len.
-// Return a pointer to the element after that
-// (after any trailing slashes).
-// Thus the caller can check whether *path=='\0'
-// to see whether the name just removed was
-// the last one.
-// If there is no name to remove, return 0.
+// Copy the next path element from path into name.
+// Return a pointer to the element following the copied one.
+// The returned path has no leading slashes,
+// so the caller can check *path=='\0' to see if the name is the last one.
+// If no name to remove, return 0.
//
// Examples:
-// skipelem("a/bb/c") = "bb/c", with *name = "a/bb/c", len=1
-// skipelem("///a/bb") = "b", with *name="a/bb", len=1
-// skipelem("") = skipelem("////") = 0
+// skipelem("a/bb/c", name) = "bb/c", setting name = "a"
+// skipelem("///a/bb", name) = "b", setting name="a"
+// skipelem("", name) = skipelem("////", name) = 0
//
static char*
skipelem(char *path, char *name)
@@ -617,201 +586,61 @@ skipelem(char *path, char *name)
return path;
}
-// look up a path name, in one of three modes.
-// NAMEI_LOOKUP: return locked target inode.
-// NAMEI_CREATE: return locked parent inode.
-// return 0 if name does exist.
-// *ret_last points to last path component (i.e. new file name).
-// *ret_ip points to the the name that did exist, if it did.
-// *ret_ip and *ret_last may be zero even if return value is zero.
-// NAMEI_DELETE: return locked parent inode, offset of dirent in *ret_off.
-// return 0 if name doesn't exist.
-struct inode*
+// Look up and return the inode for a path name.
+// If parent is set, return the inode for the parent
+// and write the final path element to name, which
+// should have room for DIRSIZ bytes.
+static struct uinode*
_namei(char *path, int parent, char *name)
{
- struct inode *dp, *ip;
+ struct uinode *dp, *ip;
+ struct inode *dpl;
uint off;
if(*path == '/')
- dp = igetroot();
+ dp = iget(ROOTDEV, 1);
else
- dp = iincref(cp->cwd);
- ilock(dp);
+ dp = idup(cp->cwd);
while((path = skipelem(path, name)) != 0){
- if(dp->type != T_DIR)
- goto fail;
+ dpl = ilock(dp);
+ if(dpl->type != T_DIR){
+ iunlock(dpl);
+ iput(dp);
+ return 0;
+ }
if(parent && *path == '\0'){
// Stop one level early.
+ iunlock(dpl);
return dp;
}
- if((ip = dirlookup(dp, name, &off)) == 0)
- goto fail;
+ if((ip = dirlookup(dpl, name, &off)) == 0){
+ iunlock(dpl);
+ iput(dp);
+ iput(ip);
+ return 0;
+ }
+ iunlock(dpl);
iput(dp);
- ilock(ip);
dp = ip;
- if(dp->type == 0 || dp->nlink < 1)
- panic("namei");
}
if(parent)
return 0;
return dp;
-
-fail:
- iput(dp);
- return 0;
}
-struct inode*
+struct uinode*
namei(char *path)
{
char name[DIRSIZ];
return _namei(path, 0, name);
}
-static struct inode*
+struct uinode*
nameiparent(char *path, char *name)
{
return _namei(path, 1, name);
}
-
-// Create the path and return its locked inode structure.
-// If cp already exists, return 0.
-struct inode*
-mknod(char *path, short type, short major, short minor)
-{
- struct inode *ip, *dp;
- char name[DIRSIZ];
-
- if((dp = nameiparent(path, name)) == 0)
- return 0;
- ip = dircreat(dp, name, type, major, minor);
- iput(dp);
- return ip;
-}
-
-// Unlink the inode named cp.
-int
-unlink(char *path)
-{
- struct inode *ip, *dp;
- struct dirent de;
- uint off;
- char name[DIRSIZ];
-
- if((dp = nameiparent(path, name)) == 0)
- return -1;
-
- // Cannot unlink "." or "..".
- if(namecmp(name, ".") == 0 || namecmp(name, "..") == 0){
- iput(dp);
- return -1;
- }
-
- if((ip = dirlookup(dp, name, &off)) == 0){
- iput(dp);
- return -1;
- }
- memset(&de, 0, sizeof(de));
- if(writei(dp, (char*)&de, off, sizeof(de)) != sizeof(de))
- panic("unlink dir write");
- iput(dp);
-
- ilock(ip);
- if(ip->nlink < 1)
- panic("unlink nlink < 1");
- ip->nlink--;
- iupdate(ip);
- iput(ip);
-
- return 0;
-}
-
-// Create the path new as a link to the same inode as old.
-int
-link(char *old, char *new)
-{
- struct inode *ip, *dp;
- char name[DIRSIZ];
-
- if((ip = namei(old)) == 0)
- return -1;
- if(ip->type == T_DIR){
- iput(ip);
- return -1;
- }
- iunlock(ip);
-
- if((dp = nameiparent(new, name)) == 0){
- idecref(ip);
- return -1;
- }
- if(dp->dev != ip->dev || dirlink(dp, name, ip->inum) < 0){
- idecref(ip);
- iput(dp);
- return -1;
- }
- iput(dp);
-
- // XXX write ordering wrong here too.
- ilock(ip);
- ip->nlink++;
- iupdate(ip);
- iput(ip);
- return 0;
-}
-
-int
-mkdir(char *path)
-{
- struct inode *dp, *ip;
- char name[DIRSIZ];
-
- // XXX write ordering is screwy here- do we care?
- if((dp = nameiparent(path, name)) == 0)
- return -1;
-
- if((ip = dircreat(dp, name, T_DIR, 0, 0)) == 0){
- iput(dp);
- return -1;
- }
- dp->nlink++;
- iupdate(dp);
-
- if(dirlink(ip, ".", ip->inum) < 0 || dirlink(ip, "..", dp->inum) < 0)
- panic("mkdir");
- iput(dp);
- iput(ip);
-
- return 0;
-}
-
-struct inode*
-create(char *path)
-{
- struct inode *dp, *ip;
- char name[DIRSIZ];
-
- if((dp = nameiparent(path, name)) == 0)
- return 0;
-
- if((ip = dirlookup(dp, name, 0)) != 0){
- iput(dp);
- ilock(ip);
- if(ip->type == T_DIR){
- iput(ip);
- return 0;
- }
- return ip;
- }
- if((ip = dircreat(dp, name, T_FILE, 0, 0)) == 0){
- iput(dp);
- return 0;
- }
- iput(dp);
- return ip;
-}
-