1a5fbfe41SRobert Morris // File system implementation. Five layers:
2bcca6c6bSrsc // + Blocks: allocator for raw disk blocks.
3a5fbfe41SRobert Morris // + Log: crash recovery for multi-step updates.
4bcca6c6bSrsc // + Files: inode allocator, reading, writing, metadata.
5bcca6c6bSrsc // + Directories: inode with special contents (list of other inodes!)
6bcca6c6bSrsc // + Names: paths like /usr/rtm/xv6/fs.c for convenient naming.
7bcca6c6bSrsc //
8eaea18cbSrsc // This file contains the low-level file system manipulation
9eaea18cbSrsc // routines. The (higher-level) system call implementations
10eaea18cbSrsc // are in sysfile.c.
11bcca6c6bSrsc
1211a9947fSrtm #include "types.h"
13558ab49fSrsc #include "defs.h"
1411a9947fSrtm #include "param.h"
15558ab49fSrsc #include "stat.h"
1611a9947fSrtm #include "mmu.h"
1711a9947fSrtm #include "proc.h"
1811a9947fSrtm #include "spinlock.h"
196670d3b5SFrans Kaashoek #include "sleeplock.h"
2011a9947fSrtm #include "fs.h"
21c24ac5d7SFrans Kaashoek #include "buf.h"
220aef8914SRuss Cox #include "file.h"
2311a9947fSrtm
24bcca6c6bSrsc #define min(a, b) ((a) < (b) ? (a) : (b))
25fbf91039Srsc static void itrunc(struct inode*);
26b7fed77bSFrans Kaashoek // there should be one superblock per disk device, but we run with
27b7fed77bSFrans Kaashoek // only one device
28b7fed77bSFrans Kaashoek struct superblock sb;
2911a9947fSrtm
30a505fd66Srsc // Read the super block.
3113a96baeSFrans Kaashoek void
readsb(int dev,struct superblock * sb)32a505fd66Srsc readsb(int dev, struct superblock *sb)
33a505fd66Srsc {
34a505fd66Srsc struct buf *bp;
35a505fd66Srsc
36a505fd66Srsc bp = bread(dev, 1);
37a505fd66Srsc memmove(sb, bp->data, sizeof(*sb));
38a505fd66Srsc brelse(bp);
39a505fd66Srsc }
40a505fd66Srsc
41a505fd66Srsc // Zero a block.
42a505fd66Srsc static void
bzero(int dev,int bno)43a505fd66Srsc bzero(int dev, int bno)
44a505fd66Srsc {
45a505fd66Srsc struct buf *bp;
46a505fd66Srsc
47a505fd66Srsc bp = bread(dev, bno);
48a505fd66Srsc memset(bp->data, 0, BSIZE);
495053dd6aSRobert Morris log_write(bp);
50a505fd66Srsc brelse(bp);
51a505fd66Srsc }
52a505fd66Srsc
53bcca6c6bSrsc // Blocks.
545be0039cSrtm
555053dd6aSRobert Morris // Allocate a zeroed disk block.
5624111398Skaashoek static uint
balloc(uint dev)5724111398Skaashoek balloc(uint dev)
5824111398Skaashoek {
59a505fd66Srsc int b, bi, m;
6024111398Skaashoek struct buf *bp;
6124111398Skaashoek
62a505fd66Srsc bp = 0;
63a505fd66Srsc for(b = 0; b < sb.size; b += BPB){
648320d61bSFrans Kaashoek bp = bread(dev, BBLOCK(b, sb));
65a5fbfe41SRobert Morris for(bi = 0; bi < BPB && b + bi < sb.size; bi++){
66a505fd66Srsc m = 1 << (bi % 8);
67a505fd66Srsc if((bp->data[bi/8] & m) == 0){ // Is block free?
68a5fbfe41SRobert Morris bp->data[bi/8] |= m; // Mark block in use.
6913a96baeSFrans Kaashoek log_write(bp);
7024111398Skaashoek brelse(bp);
715053dd6aSRobert Morris bzero(dev, b + bi);
72a505fd66Srsc return b + bi;
7324111398Skaashoek }
74a505fd66Srsc }
7528d9ef04Skaashoek brelse(bp);
767d4aef6cSrsc }
777d4aef6cSrsc panic("balloc: out of blocks");
787d4aef6cSrsc }
7924111398Skaashoek
80bb207a1dSrsc // Free a disk block.
8128d9ef04Skaashoek static void
bfree(int dev,uint b)8228d9ef04Skaashoek bfree(int dev, uint b)
8328d9ef04Skaashoek {
8428d9ef04Skaashoek struct buf *bp;
85a505fd66Srsc int bi, m;
8628d9ef04Skaashoek
878320d61bSFrans Kaashoek bp = bread(dev, BBLOCK(b, sb));
8828d9ef04Skaashoek bi = b % BPB;
89a505fd66Srsc m = 1 << (bi % 8);
90902b13f5Srtm if((bp->data[bi/8] & m) == 0)
91902b13f5Srtm panic("freeing free block");
92a5fbfe41SRobert Morris bp->data[bi/8] &= ~m;
9313a96baeSFrans Kaashoek log_write(bp);
9428d9ef04Skaashoek brelse(bp);
9528d9ef04Skaashoek }
9624111398Skaashoek
976c34f97cSrsc // Inodes.
986c34f97cSrsc //
99a5fbfe41SRobert Morris // An inode describes a single unnamed file.
100a5fbfe41SRobert Morris // The inode disk structure holds metadata: the file's type,
101a5fbfe41SRobert Morris // its size, the number of links referring to it, and the
102a5fbfe41SRobert Morris // list of blocks holding the file's content.
103bcca6c6bSrsc //
1048320d61bSFrans Kaashoek // The inodes are laid out sequentially on disk at
1058320d61bSFrans Kaashoek // sb.startinode. Each inode has a number, indicating its
106a5fbfe41SRobert Morris // position on the disk.
107a5fbfe41SRobert Morris //
108a5fbfe41SRobert Morris // The kernel keeps a cache of in-use inodes in memory
109a5fbfe41SRobert Morris // to provide a place for synchronizing access
110a5fbfe41SRobert Morris // to inodes used by multiple processes. The cached
111a5fbfe41SRobert Morris // inodes include book-keeping information that is
1123375df50SRobert Morris // not stored on disk: ip->ref and ip->valid.
113bcca6c6bSrsc //
1149cec455bSRobert Morris // An inode and its in-memory representation go through a
11538eee5bcSRobert Morris // sequence of states before they can be used by the
11638eee5bcSRobert Morris // rest of the file system code.
117bcca6c6bSrsc //
11838eee5bcSRobert Morris // * Allocation: an inode is allocated if its type (on disk)
1199cec455bSRobert Morris // is non-zero. ialloc() allocates, and iput() frees if
1209cec455bSRobert Morris // the reference and link counts have fallen to zero.
121eaea18cbSrsc //
12238eee5bcSRobert Morris // * Referencing in cache: an entry in the inode cache
12338eee5bcSRobert Morris // is free if ip->ref is zero. Otherwise ip->ref tracks
12438eee5bcSRobert Morris // the number of in-memory pointers to the entry (open
1259cec455bSRobert Morris // files and current directories). iget() finds or
1269cec455bSRobert Morris // creates a cache entry and increments its ref; iput()
1279cec455bSRobert Morris // decrements ref.
128a5fbfe41SRobert Morris //
12938eee5bcSRobert Morris // * Valid: the information (type, size, &c) in an inode
1303375df50SRobert Morris // cache entry is only correct when ip->valid is 1.
1313375df50SRobert Morris // ilock() reads the inode from
1323375df50SRobert Morris // the disk and sets ip->valid, while iput() clears
1333375df50SRobert Morris // ip->valid if ip->ref has fallen to zero.
134a5fbfe41SRobert Morris //
13538eee5bcSRobert Morris // * Locked: file system code may only examine and modify
13638eee5bcSRobert Morris // the information in an inode and its content if it
137dec637bcSFrans Kaashoek // has first locked the inode.
13838eee5bcSRobert Morris //
13938eee5bcSRobert Morris // Thus a typical sequence is:
14038eee5bcSRobert Morris // ip = iget(dev, inum)
14138eee5bcSRobert Morris // ilock(ip)
14238eee5bcSRobert Morris // ... examine and modify ip->xxx ...
14338eee5bcSRobert Morris // iunlock(ip)
14438eee5bcSRobert Morris // iput(ip)
14538eee5bcSRobert Morris //
14638eee5bcSRobert Morris // ilock() is separate from iget() so that system calls can
14738eee5bcSRobert Morris // get a long-term reference to an inode (as for an open file)
14838eee5bcSRobert Morris // and only lock it for short periods (e.g., in read()).
14938eee5bcSRobert Morris // The separation also helps avoid deadlock and races during
15038eee5bcSRobert Morris // pathname lookup. iget() increments ip->ref so that the inode
15138eee5bcSRobert Morris // stays cached and pointers to it remain valid.
15238eee5bcSRobert Morris //
15338eee5bcSRobert Morris // Many internal file system functions expect the caller to
15438eee5bcSRobert Morris // have locked the inodes involved; this lets callers create
15538eee5bcSRobert Morris // multi-step atomic operations.
1561c7aa960SRobert Morris //
157*4638cabfSRobert Morris // The icache.lock spin-lock protects the allocation of icache
15870705966SRobert Morris // entries. Since ip->ref indicates whether an entry is free,
15970705966SRobert Morris // and ip->dev and ip->inum indicate which i-node an entry
16070705966SRobert Morris // holds, one must hold icache.lock while using any of those fields.
1611c7aa960SRobert Morris //
162*4638cabfSRobert Morris // An ip->lock sleep-lock protects all ip-> fields other than ref,
1631c7aa960SRobert Morris // dev, and inum. One must hold ip->lock in order to
1641c7aa960SRobert Morris // read or write that inode's ip->valid, ip->size, ip->type, &c.
165bcca6c6bSrsc
166bcca6c6bSrsc struct {
167bcca6c6bSrsc struct spinlock lock;
168bcca6c6bSrsc struct inode inode[NINODE];
169bcca6c6bSrsc } icache;
170bcca6c6bSrsc
171bcca6c6bSrsc void
iinit(int dev)1728320d61bSFrans Kaashoek iinit(int dev)
173bcca6c6bSrsc {
174dec637bcSFrans Kaashoek int i = 0;
175dec637bcSFrans Kaashoek
17634295f46Srsc initlock(&icache.lock, "icache");
177dec637bcSFrans Kaashoek for(i = 0; i < NINODE; i++) {
178dec637bcSFrans Kaashoek initsleeplock(&icache.inode[i].lock, "inode");
179dec637bcSFrans Kaashoek }
180dec637bcSFrans Kaashoek
1818320d61bSFrans Kaashoek readsb(dev, &sb);
182b7fed77bSFrans Kaashoek cprintf("sb: size %d nblocks %d ninodes %d nlog %d logstart %d\
183b7fed77bSFrans Kaashoek inodestart %d bmap start %d\n", sb.size, sb.nblocks,
184b7fed77bSFrans Kaashoek sb.ninodes, sb.nlog, sb.logstart, sb.inodestart,
185b7fed77bSFrans Kaashoek sb.bmapstart);
186bcca6c6bSrsc }
187bcca6c6bSrsc
188f9a06440SRuss Cox static struct inode* iget(uint dev, uint inum);
189f9a06440SRuss Cox
190f9a06440SRuss Cox //PAGEBREAK!
19170705966SRobert Morris // Allocate an inode on device dev.
1926389d9d4SRobert Morris // Mark it as allocated by giving it type type.
19370705966SRobert Morris // Returns an unlocked but allocated and referenced inode.
194f9a06440SRuss Cox struct inode*
ialloc(uint dev,short type)195f9a06440SRuss Cox ialloc(uint dev, short type)
196f9a06440SRuss Cox {
197f9a06440SRuss Cox int inum;
198f9a06440SRuss Cox struct buf *bp;
199f9a06440SRuss Cox struct dinode *dip;
200a5fbfe41SRobert Morris
201a5fbfe41SRobert Morris for(inum = 1; inum < sb.ninodes; inum++){
2028320d61bSFrans Kaashoek bp = bread(dev, IBLOCK(inum, sb));
203f9a06440SRuss Cox dip = (struct dinode*)bp->data + inum%IPB;
204f9a06440SRuss Cox if(dip->type == 0){ // a free inode
205f9a06440SRuss Cox memset(dip, 0, sizeof(*dip));
206f9a06440SRuss Cox dip->type = type;
20713a96baeSFrans Kaashoek log_write(bp); // mark it allocated on the disk
208f9a06440SRuss Cox brelse(bp);
209f9a06440SRuss Cox return iget(dev, inum);
210f9a06440SRuss Cox }
211f9a06440SRuss Cox brelse(bp);
212f9a06440SRuss Cox }
213f9a06440SRuss Cox panic("ialloc: no inodes");
214f9a06440SRuss Cox }
215f9a06440SRuss Cox
21638eee5bcSRobert Morris // Copy a modified in-memory inode to disk.
21770705966SRobert Morris // Must be called after every change to an ip->xxx field
21870705966SRobert Morris // that lives on disk, since i-node cache is write-through.
2191c7aa960SRobert Morris // Caller must hold ip->lock.
220f9a06440SRuss Cox void
iupdate(struct inode * ip)221f9a06440SRuss Cox iupdate(struct inode *ip)
222f9a06440SRuss Cox {
223f9a06440SRuss Cox struct buf *bp;
224f9a06440SRuss Cox struct dinode *dip;
225f9a06440SRuss Cox
2268320d61bSFrans Kaashoek bp = bread(ip->dev, IBLOCK(ip->inum, sb));
227f9a06440SRuss Cox dip = (struct dinode*)bp->data + ip->inum%IPB;
228f9a06440SRuss Cox dip->type = ip->type;
229f9a06440SRuss Cox dip->major = ip->major;
230f9a06440SRuss Cox dip->minor = ip->minor;
231f9a06440SRuss Cox dip->nlink = ip->nlink;
232f9a06440SRuss Cox dip->size = ip->size;
233f9a06440SRuss Cox memmove(dip->addrs, ip->addrs, sizeof(ip->addrs));
23413a96baeSFrans Kaashoek log_write(bp);
235f9a06440SRuss Cox brelse(bp);
236f9a06440SRuss Cox }
237f9a06440SRuss Cox
238f5527388Srsc // Find the inode with number inum on device dev
23938eee5bcSRobert Morris // and return the in-memory copy. Does not lock
24038eee5bcSRobert Morris // the inode and does not read it from disk.
24107090dd7Srsc static struct inode*
iget(uint dev,uint inum)24211a9947fSrtm iget(uint dev, uint inum)
24311a9947fSrtm {
244bcca6c6bSrsc struct inode *ip, *empty;
24511a9947fSrtm
246bcca6c6bSrsc acquire(&icache.lock);
24711a9947fSrtm
24838eee5bcSRobert Morris // Is the inode already cached?
249bcca6c6bSrsc empty = 0;
250bcca6c6bSrsc for(ip = &icache.inode[0]; ip < &icache.inode[NINODE]; ip++){
2510d6bbd31Srsc if(ip->ref > 0 && ip->dev == dev && ip->inum == inum){
2520d6bbd31Srsc ip->ref++;
253bcca6c6bSrsc release(&icache.lock);
25407090dd7Srsc return ip;
25511a9947fSrtm }
256bcca6c6bSrsc if(empty == 0 && ip->ref == 0) // Remember empty slot.
257bcca6c6bSrsc empty = ip;
25811a9947fSrtm }
25911a9947fSrtm
26038eee5bcSRobert Morris // Recycle an inode cache entry.
261bcca6c6bSrsc if(empty == 0)
26232eea766Srsc panic("iget: no inodes");
26311a9947fSrtm
264bcca6c6bSrsc ip = empty;
265bcca6c6bSrsc ip->dev = dev;
266bcca6c6bSrsc ip->inum = inum;
267bcca6c6bSrsc ip->ref = 1;
2683375df50SRobert Morris ip->valid = 0;
269bcca6c6bSrsc release(&icache.lock);
27011a9947fSrtm
27107090dd7Srsc return ip;
272f32f3638Srsc }
273f32f3638Srsc
274eaea18cbSrsc // Increment reference count for ip.
275eaea18cbSrsc // Returns ip to enable ip = idup(ip1) idiom.
27607090dd7Srsc struct inode*
idup(struct inode * ip)27707090dd7Srsc idup(struct inode *ip)
278f32f3638Srsc {
279eaea18cbSrsc acquire(&icache.lock);
280eaea18cbSrsc ip->ref++;
281eaea18cbSrsc release(&icache.lock);
28207090dd7Srsc return ip;
283f32f3638Srsc }
284f32f3638Srsc
2851ddfbbb1SFrans Kaashoek // Lock the given inode.
28638eee5bcSRobert Morris // Reads the inode from disk if necessary.
28707090dd7Srsc void
ilock(struct inode * ip)28807090dd7Srsc ilock(struct inode *ip)
289f32f3638Srsc {
290f32f3638Srsc struct buf *bp;
291f32f3638Srsc struct dinode *dip;
292eaea18cbSrsc
29307090dd7Srsc if(ip == 0 || ip->ref < 1)
29407090dd7Srsc panic("ilock");
295f32f3638Srsc
296dec637bcSFrans Kaashoek acquiresleep(&ip->lock);
297f32f3638Srsc
2983375df50SRobert Morris if(ip->valid == 0){
2998320d61bSFrans Kaashoek bp = bread(ip->dev, IBLOCK(ip->inum, sb));
3003341e30fSrsc dip = (struct dinode*)bp->data + ip->inum%IPB;
301bcca6c6bSrsc ip->type = dip->type;
302bcca6c6bSrsc ip->major = dip->major;
303bcca6c6bSrsc ip->minor = dip->minor;
304bcca6c6bSrsc ip->nlink = dip->nlink;
305bcca6c6bSrsc ip->size = dip->size;
306bcca6c6bSrsc memmove(ip->addrs, dip->addrs, sizeof(ip->addrs));
30711a9947fSrtm brelse(bp);
3083375df50SRobert Morris ip->valid = 1;
309eaea18cbSrsc if(ip->type == 0)
310eaea18cbSrsc panic("ilock: no type");
31111a9947fSrtm }
312bcca6c6bSrsc }
313bcca6c6bSrsc
314bcca6c6bSrsc // Unlock the given inode.
31507090dd7Srsc void
iunlock(struct inode * ip)316bcca6c6bSrsc iunlock(struct inode *ip)
317bcca6c6bSrsc {
318dec637bcSFrans Kaashoek if(ip == 0 || !holdingsleep(&ip->lock) || ip->ref < 1)
319bcca6c6bSrsc panic("iunlock");
320bcca6c6bSrsc
321dec637bcSFrans Kaashoek releasesleep(&ip->lock);
322bcca6c6bSrsc }
323bcca6c6bSrsc
32438eee5bcSRobert Morris // Drop a reference to an in-memory inode.
32538eee5bcSRobert Morris // If that was the last reference, the inode cache entry can
32638eee5bcSRobert Morris // be recycled.
32738eee5bcSRobert Morris // If that was the last reference and the inode has no links
32838eee5bcSRobert Morris // to it, free the inode (and its content) on disk.
3292c565472SRobert Morris // All calls to iput() must be inside a transaction in
3302c565472SRobert Morris // case it has to free the inode.
331bcca6c6bSrsc void
iput(struct inode * ip)33207090dd7Srsc iput(struct inode *ip)
333bcca6c6bSrsc {
334aba8423cSRobert Morris acquiresleep(&ip->lock);
33570d912b3SRobert Morris if(ip->valid && ip->nlink == 0){
336a4ee6f7dSRobert Morris acquire(&icache.lock);
337a4ee6f7dSRobert Morris int r = ip->ref;
338f32f3638Srsc release(&icache.lock);
339a4ee6f7dSRobert Morris if(r == 1){
340a4ee6f7dSRobert Morris // inode has no links and no other references: truncate and free.
341f32f3638Srsc itrunc(ip);
342f32f3638Srsc ip->type = 0;
343f32f3638Srsc iupdate(ip);
3443375df50SRobert Morris ip->valid = 0;
345a4ee6f7dSRobert Morris }
34670d912b3SRobert Morris }
347aba8423cSRobert Morris releasesleep(&ip->lock);
348a4ee6f7dSRobert Morris
349a4ee6f7dSRobert Morris acquire(&icache.lock);
350f32f3638Srsc ip->ref--;
351f32f3638Srsc release(&icache.lock);
352bcca6c6bSrsc }
353bcca6c6bSrsc
3547895178dSrsc // Common idiom: unlock, then put.
35507090dd7Srsc void
iunlockput(struct inode * ip)35607090dd7Srsc iunlockput(struct inode *ip)
35707090dd7Srsc {
35807090dd7Srsc iunlock(ip);
35907090dd7Srsc iput(ip);
36007090dd7Srsc }
36107090dd7Srsc
3628d2e9a48Srsc //PAGEBREAK!
36338eee5bcSRobert Morris // Inode content
364bcca6c6bSrsc //
36538eee5bcSRobert Morris // The content (data) associated with each inode is stored
36638eee5bcSRobert Morris // in blocks on the disk. The first NDIRECT block numbers
3677895178dSrsc // are listed in ip->addrs[]. The next NINDIRECT blocks are
36838eee5bcSRobert Morris // listed in block ip->addrs[NDIRECT].
3699d3fb671Srtm
370bb207a1dSrsc // Return the disk block address of the nth block in inode ip.
37113ae8808Srsc // If there is no such block, bmap allocates one.
372eaea18cbSrsc static uint
bmap(struct inode * ip,uint bn)37313ae8808Srsc bmap(struct inode *ip, uint bn)
37422bac2cbSkaashoek {
375bcca6c6bSrsc uint addr, *a;
376bcca6c6bSrsc struct buf *bp;
37722bac2cbSkaashoek
378ea2909b6Skaashoek if(bn < NDIRECT){
37913ae8808Srsc if((addr = ip->addrs[bn]) == 0)
380bcca6c6bSrsc ip->addrs[bn] = addr = balloc(ip->dev);
381bcca6c6bSrsc return addr;
382bcca6c6bSrsc }
383bcca6c6bSrsc bn -= NDIRECT;
384bcca6c6bSrsc
385bcca6c6bSrsc if(bn < NINDIRECT){
386bcca6c6bSrsc // Load indirect block, allocating if necessary.
38713ae8808Srsc if((addr = ip->addrs[NDIRECT]) == 0)
388ba6cd8a6Srsc ip->addrs[NDIRECT] = addr = balloc(ip->dev);
389bcca6c6bSrsc bp = bread(ip->dev, addr);
390bcca6c6bSrsc a = (uint*)bp->data;
391bcca6c6bSrsc if((addr = a[bn]) == 0){
392bcca6c6bSrsc a[bn] = addr = balloc(ip->dev);
39313a96baeSFrans Kaashoek log_write(bp);
394bcca6c6bSrsc }
395bcca6c6bSrsc brelse(bp);
396bcca6c6bSrsc return addr;
39722bac2cbSkaashoek }
39822bac2cbSkaashoek
399bcca6c6bSrsc panic("bmap: out of range");
400bcca6c6bSrsc }
401bcca6c6bSrsc
402bcca6c6bSrsc // Truncate inode (discard contents).
40338eee5bcSRobert Morris // Only called when the inode has no links
40438eee5bcSRobert Morris // to it (no directory entries referring to it)
40538eee5bcSRobert Morris // and has no in-memory reference to it (is
40638eee5bcSRobert Morris // not an open file or current directory).
407fbf91039Srsc static void
itrunc(struct inode * ip)4082aa4c3bcSrtm itrunc(struct inode *ip)
40922bac2cbSkaashoek {
410ea2909b6Skaashoek int i, j;
411bcca6c6bSrsc struct buf *bp;
4127d4aef6cSrsc uint *a;
41322bac2cbSkaashoek
414bcca6c6bSrsc for(i = 0; i < NDIRECT; i++){
415bcca6c6bSrsc if(ip->addrs[i]){
41622bac2cbSkaashoek bfree(ip->dev, ip->addrs[i]);
41722bac2cbSkaashoek ip->addrs[i] = 0;
41822bac2cbSkaashoek }
41922bac2cbSkaashoek }
420bcca6c6bSrsc
421ba6cd8a6Srsc if(ip->addrs[NDIRECT]){
422ba6cd8a6Srsc bp = bread(ip->dev, ip->addrs[NDIRECT]);
423bcca6c6bSrsc a = (uint*)bp->data;
424bcca6c6bSrsc for(j = 0; j < NINDIRECT; j++){
425bcca6c6bSrsc if(a[j])
426bcca6c6bSrsc bfree(ip->dev, a[j]);
427bcca6c6bSrsc }
428bcca6c6bSrsc brelse(bp);
429ba6cd8a6Srsc bfree(ip->dev, ip->addrs[NDIRECT]);
430ba6cd8a6Srsc ip->addrs[NDIRECT] = 0;
431bcca6c6bSrsc }
432bcca6c6bSrsc
43322bac2cbSkaashoek ip->size = 0;
43422bac2cbSkaashoek iupdate(ip);
43522bac2cbSkaashoek }
43622bac2cbSkaashoek
437bb207a1dSrsc // Copy stat information from inode.
4381c7aa960SRobert Morris // Caller must hold ip->lock.
439e958c538Skaashoek void
stati(struct inode * ip,struct stat * st)4401f544842Skaashoek stati(struct inode *ip, struct stat *st)
4411f544842Skaashoek {
4421dca3afbSrsc st->dev = ip->dev;
4431dca3afbSrsc st->ino = ip->inum;
4441dca3afbSrsc st->type = ip->type;
4451dca3afbSrsc st->nlink = ip->nlink;
4461dca3afbSrsc st->size = ip->size;
4471f544842Skaashoek }
4481f544842Skaashoek
449eaea18cbSrsc //PAGEBREAK!
450bb207a1dSrsc // Read data from inode.
4511c7aa960SRobert Morris // Caller must hold ip->lock.
452c59361f1Srtm int
readi(struct inode * ip,char * dst,uint off,uint n)45317a85657Srtm readi(struct inode *ip, char *dst, uint off, uint n)
454c59361f1Srtm {
455bcca6c6bSrsc uint tot, m;
456c59361f1Srtm struct buf *bp;
457c59361f1Srtm
458939f9edeSkaashoek if(ip->type == T_DEV){
4591dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].read)
460939f9edeSkaashoek return -1;
461d844f0f9Srsc return devsw[ip->major].read(ip, dst, n);
462939f9edeSkaashoek }
463939f9edeSkaashoek
4647895178dSrsc if(off > ip->size || off + n < off)
465bcca6c6bSrsc return -1;
466bcca6c6bSrsc if(off + n > ip->size)
467bcca6c6bSrsc n = ip->size - off;
468bcca6c6bSrsc
469bcca6c6bSrsc for(tot=0; tot<n; tot+=m, off+=m, dst+=m){
47013ae8808Srsc bp = bread(ip->dev, bmap(ip, off/BSIZE));
471bcca6c6bSrsc m = min(n - tot, BSIZE - off%BSIZE);
472bcca6c6bSrsc memmove(dst, bp->data + off%BSIZE, m);
473c59361f1Srtm brelse(bp);
474c59361f1Srtm }
475bcca6c6bSrsc return n;
476ea2909b6Skaashoek }
477ea2909b6Skaashoek
478eaea18cbSrsc // PAGEBREAK!
479bb207a1dSrsc // Write data to inode.
4801c7aa960SRobert Morris // Caller must hold ip->lock.
481ea2909b6Skaashoek int
writei(struct inode * ip,char * src,uint off,uint n)482bcca6c6bSrsc writei(struct inode *ip, char *src, uint off, uint n)
4836fa5ffb5Skaashoek {
484bcca6c6bSrsc uint tot, m;
4857d4aef6cSrsc struct buf *bp;
4867d4aef6cSrsc
4876fa5ffb5Skaashoek if(ip->type == T_DEV){
4881dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].write)
489939f9edeSkaashoek return -1;
490d844f0f9Srsc return devsw[ip->major].write(ip, src, n);
4917d4aef6cSrsc }
4927d4aef6cSrsc
4931ddfbbb1SFrans Kaashoek if(off > ip->size || off + n < off)
494bcca6c6bSrsc return -1;
4951ddfbbb1SFrans Kaashoek if(off + n > MAXFILE*BSIZE)
4962e590463SRobert Morris return -1;
497bcca6c6bSrsc
498bcca6c6bSrsc for(tot=0; tot<n; tot+=m, off+=m, src+=m){
49913ae8808Srsc bp = bread(ip->dev, bmap(ip, off/BSIZE));
500bcca6c6bSrsc m = min(n - tot, BSIZE - off%BSIZE);
501bcca6c6bSrsc memmove(bp->data + off%BSIZE, src, m);
5022e590463SRobert Morris log_write(bp);
50328d9ef04Skaashoek brelse(bp);
50428d9ef04Skaashoek }
505bcca6c6bSrsc
506bcca6c6bSrsc if(n > 0 && off > ip->size){
50748b82470Srsc ip->size = off;
50828d9ef04Skaashoek iupdate(ip);
50928d9ef04Skaashoek }
510bcca6c6bSrsc return n;
5116fa5ffb5Skaashoek }
5126fa5ffb5Skaashoek
513eaea18cbSrsc //PAGEBREAK!
514bcca6c6bSrsc // Directories
515bcca6c6bSrsc
516eaea18cbSrsc int
namecmp(const char * s,const char * t)517fbf91039Srsc namecmp(const char *s, const char *t)
518fbf91039Srsc {
519766ba5ccSrsc return strncmp(s, t, DIRSIZ);
520fbf91039Srsc }
521fbf91039Srsc
522bcca6c6bSrsc // Look for a directory entry in a directory.
523eaea18cbSrsc // If found, set *poff to byte offset of entry.
52407090dd7Srsc struct inode*
dirlookup(struct inode * dp,char * name,uint * poff)525fbf91039Srsc dirlookup(struct inode *dp, char *name, uint *poff)
526bcca6c6bSrsc {
527f32f3638Srsc uint off, inum;
528327cc21fSRobert Morris struct dirent de;
529bcca6c6bSrsc
530bcca6c6bSrsc if(dp->type != T_DIR)
53120365348Srtm panic("dirlookup not DIR");
532bcca6c6bSrsc
533327cc21fSRobert Morris for(off = 0; off < dp->size; off += sizeof(de)){
534327cc21fSRobert Morris if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de))
53561f26e3cSGrant Wu panic("dirlookup read");
536327cc21fSRobert Morris if(de.inum == 0)
537bcca6c6bSrsc continue;
538327cc21fSRobert Morris if(namecmp(name, de.name) == 0){
539bcca6c6bSrsc // entry matches path element
540e2a620daSrsc if(poff)
541327cc21fSRobert Morris *poff = off;
542327cc21fSRobert Morris inum = de.inum;
543f32f3638Srsc return iget(dp->dev, inum);
544f32f3638Srsc }
545f32f3638Srsc }
546327cc21fSRobert Morris
547bcca6c6bSrsc return 0;
548bcca6c6bSrsc }
549bcca6c6bSrsc
55013ae8808Srsc // Write a new directory entry (name, inum) into the directory dp.
551eaea18cbSrsc int
dirlink(struct inode * dp,char * name,uint inum)55213ae8808Srsc dirlink(struct inode *dp, char *name, uint inum)
553bcca6c6bSrsc {
554e2a620daSrsc int off;
555bcca6c6bSrsc struct dirent de;
55607090dd7Srsc struct inode *ip;
557f32f3638Srsc
558eaea18cbSrsc // Check that name is not present.
55907090dd7Srsc if((ip = dirlookup(dp, name, 0)) != 0){
56007090dd7Srsc iput(ip);
561f32f3638Srsc return -1;
562f32f3638Srsc }
563bcca6c6bSrsc
564bcca6c6bSrsc // Look for an empty dirent.
565bcca6c6bSrsc for(off = 0; off < dp->size; off += sizeof(de)){
566bcca6c6bSrsc if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de))
5677895178dSrsc panic("dirlink read");
568bcca6c6bSrsc if(de.inum == 0)
569bcca6c6bSrsc break;
570bcca6c6bSrsc }
571bcca6c6bSrsc
572766ba5ccSrsc strncpy(de.name, name, DIRSIZ);
57313ae8808Srsc de.inum = inum;
574bcca6c6bSrsc if(writei(dp, (char*)&de, off, sizeof(de)) != sizeof(de))
5757895178dSrsc panic("dirlink");
576f32f3638Srsc
577f32f3638Srsc return 0;
578bcca6c6bSrsc }
579bcca6c6bSrsc
5808d2e9a48Srsc //PAGEBREAK!
581bcca6c6bSrsc // Paths
582bcca6c6bSrsc
583eaea18cbSrsc // Copy the next path element from path into name.
584eaea18cbSrsc // Return a pointer to the element following the copied one.
585eaea18cbSrsc // The returned path has no leading slashes,
586eaea18cbSrsc // so the caller can check *path=='\0' to see if the name is the last one.
587eaea18cbSrsc // If no name to remove, return 0.
588ab5c2dbbSrsc //
589ab5c2dbbSrsc // Examples:
590eaea18cbSrsc // skipelem("a/bb/c", name) = "bb/c", setting name = "a"
5917895178dSrsc // skipelem("///a//bb", name) = "bb", setting name = "a"
59213ae8808Srsc // skipelem("a", name) = "", setting name = "a"
593eaea18cbSrsc // skipelem("", name) = skipelem("////", name) = 0
594ab5c2dbbSrsc //
595ab5c2dbbSrsc static char*
skipelem(char * path,char * name)596fbf91039Srsc skipelem(char *path, char *name)
597ab5c2dbbSrsc {
598fbf91039Srsc char *s;
599fbf91039Srsc int len;
600fbf91039Srsc
601ab5c2dbbSrsc while(*path == '/')
602ab5c2dbbSrsc path++;
603ab5c2dbbSrsc if(*path == 0)
604ab5c2dbbSrsc return 0;
605fbf91039Srsc s = path;
606ab5c2dbbSrsc while(*path != '/' && *path != 0)
607ab5c2dbbSrsc path++;
608fbf91039Srsc len = path - s;
609fbf91039Srsc if(len >= DIRSIZ)
610fbf91039Srsc memmove(name, s, DIRSIZ);
611fbf91039Srsc else {
612fbf91039Srsc memmove(name, s, len);
613fbf91039Srsc name[len] = 0;
614fbf91039Srsc }
615ab5c2dbbSrsc while(*path == '/')
616ab5c2dbbSrsc path++;
617ab5c2dbbSrsc return path;
618ab5c2dbbSrsc }
619ab5c2dbbSrsc
620eaea18cbSrsc // Look up and return the inode for a path name.
621bf2932a6Srsc // If parent != 0, return the inode for the parent and copy the final
622bf2932a6Srsc // path element into name, which must have room for DIRSIZ bytes.
6232c565472SRobert Morris // Must be called inside a transaction since it calls iput().
62407090dd7Srsc static struct inode*
namex(char * path,int nameiparent,char * name)625f9a06440SRuss Cox namex(char *path, int nameiparent, char *name)
6269d3fb671Srtm {
62707090dd7Srsc struct inode *ip, *next;
6289d3fb671Srtm
629ab5c2dbbSrsc if(*path == '/')
6302ce40d70Srtm ip = iget(ROOTDEV, ROOTINO);
631f32f3638Srsc else
632abf847a0SFrans Kaashoek ip = idup(myproc()->cwd);
6339d3fb671Srtm
634fbf91039Srsc while((path = skipelem(path, name)) != 0){
63507090dd7Srsc ilock(ip);
63607090dd7Srsc if(ip->type != T_DIR){
63707090dd7Srsc iunlockput(ip);
638eaea18cbSrsc return 0;
639eaea18cbSrsc }
640f9a06440SRuss Cox if(nameiparent && *path == '\0'){
641e2a620daSrsc // Stop one level early.
64207090dd7Srsc iunlock(ip);
64307090dd7Srsc return ip;
644ab5c2dbbSrsc }
6457895178dSrsc if((next = dirlookup(ip, name, 0)) == 0){
64607090dd7Srsc iunlockput(ip);
647eaea18cbSrsc return 0;
648eaea18cbSrsc }
64907090dd7Srsc iunlockput(ip);
65007090dd7Srsc ip = next;
651ab5c2dbbSrsc }
652f9a06440SRuss Cox if(nameiparent){
65307090dd7Srsc iput(ip);
6545051da6dSrtm return 0;
65520365348Srtm }
65607090dd7Srsc return ip;
6570633b971Skaashoek }
6589d3fb671Srtm
6597895178dSrsc struct inode*
namei(char * path)6607895178dSrsc namei(char *path)
6617895178dSrsc {
6627895178dSrsc char name[DIRSIZ];
66313ae8808Srsc return namex(path, 0, name);
6647895178dSrsc }
665bf2932a6Srsc
6667895178dSrsc struct inode*
nameiparent(char * path,char * name)6677895178dSrsc nameiparent(char *path, char *name)
6687895178dSrsc {
66913ae8808Srsc return namex(path, 1, name);
6707895178dSrsc }
671