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 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 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 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 8228d9ef04Skaashoek bfree(int dev, uint b) 8328d9ef04Skaashoek { 8428d9ef04Skaashoek struct buf *bp; 85a505fd66Srsc int bi, m; 8628d9ef04Skaashoek 87a505fd66Srsc readsb(dev, &sb); 888320d61bSFrans Kaashoek bp = bread(dev, BBLOCK(b, sb)); 8928d9ef04Skaashoek bi = b % BPB; 90a505fd66Srsc m = 1 << (bi % 8); 91902b13f5Srtm if((bp->data[bi/8] & m) == 0) 92902b13f5Srtm panic("freeing free block"); 93a5fbfe41SRobert Morris bp->data[bi/8] &= ~m; 9413a96baeSFrans Kaashoek log_write(bp); 9528d9ef04Skaashoek brelse(bp); 9628d9ef04Skaashoek } 9724111398Skaashoek 986c34f97cSrsc // Inodes. 996c34f97cSrsc // 100a5fbfe41SRobert Morris // An inode describes a single unnamed file. 101a5fbfe41SRobert Morris // The inode disk structure holds metadata: the file's type, 102a5fbfe41SRobert Morris // its size, the number of links referring to it, and the 103a5fbfe41SRobert Morris // list of blocks holding the file's content. 104bcca6c6bSrsc // 1058320d61bSFrans Kaashoek // The inodes are laid out sequentially on disk at 1068320d61bSFrans Kaashoek // sb.startinode. Each inode has a number, indicating its 107a5fbfe41SRobert Morris // position on the disk. 108a5fbfe41SRobert Morris // 109a5fbfe41SRobert Morris // The kernel keeps a cache of in-use inodes in memory 110a5fbfe41SRobert Morris // to provide a place for synchronizing access 111a5fbfe41SRobert Morris // to inodes used by multiple processes. The cached 112a5fbfe41SRobert Morris // inodes include book-keeping information that is 1133375df50SRobert Morris // not stored on disk: ip->ref and ip->valid. 114bcca6c6bSrsc // 1159cec455bSRobert Morris // An inode and its in-memory representation go through a 11638eee5bcSRobert Morris // sequence of states before they can be used by the 11738eee5bcSRobert Morris // rest of the file system code. 118bcca6c6bSrsc // 11938eee5bcSRobert Morris // * Allocation: an inode is allocated if its type (on disk) 1209cec455bSRobert Morris // is non-zero. ialloc() allocates, and iput() frees if 1219cec455bSRobert Morris // the reference and link counts have fallen to zero. 122eaea18cbSrsc // 12338eee5bcSRobert Morris // * Referencing in cache: an entry in the inode cache 12438eee5bcSRobert Morris // is free if ip->ref is zero. Otherwise ip->ref tracks 12538eee5bcSRobert Morris // the number of in-memory pointers to the entry (open 1269cec455bSRobert Morris // files and current directories). iget() finds or 1279cec455bSRobert Morris // creates a cache entry and increments its ref; iput() 1289cec455bSRobert Morris // decrements ref. 129a5fbfe41SRobert Morris // 13038eee5bcSRobert Morris // * Valid: the information (type, size, &c) in an inode 1313375df50SRobert Morris // cache entry is only correct when ip->valid is 1. 1323375df50SRobert Morris // ilock() reads the inode from 1333375df50SRobert Morris // the disk and sets ip->valid, while iput() clears 1343375df50SRobert Morris // ip->valid if ip->ref has fallen to zero. 135a5fbfe41SRobert Morris // 13638eee5bcSRobert Morris // * Locked: file system code may only examine and modify 13738eee5bcSRobert Morris // the information in an inode and its content if it 138dec637bcSFrans Kaashoek // has first locked the inode. 13938eee5bcSRobert Morris // 14038eee5bcSRobert Morris // Thus a typical sequence is: 14138eee5bcSRobert Morris // ip = iget(dev, inum) 14238eee5bcSRobert Morris // ilock(ip) 14338eee5bcSRobert Morris // ... examine and modify ip->xxx ... 14438eee5bcSRobert Morris // iunlock(ip) 14538eee5bcSRobert Morris // iput(ip) 14638eee5bcSRobert Morris // 14738eee5bcSRobert Morris // ilock() is separate from iget() so that system calls can 14838eee5bcSRobert Morris // get a long-term reference to an inode (as for an open file) 14938eee5bcSRobert Morris // and only lock it for short periods (e.g., in read()). 15038eee5bcSRobert Morris // The separation also helps avoid deadlock and races during 15138eee5bcSRobert Morris // pathname lookup. iget() increments ip->ref so that the inode 15238eee5bcSRobert Morris // stays cached and pointers to it remain valid. 15338eee5bcSRobert Morris // 15438eee5bcSRobert Morris // Many internal file system functions expect the caller to 15538eee5bcSRobert Morris // have locked the inodes involved; this lets callers create 15638eee5bcSRobert Morris // multi-step atomic operations. 1571c7aa960SRobert Morris // 158*4638cabfSRobert Morris // The icache.lock spin-lock protects the allocation of icache 15970705966SRobert Morris // entries. Since ip->ref indicates whether an entry is free, 16070705966SRobert Morris // and ip->dev and ip->inum indicate which i-node an entry 16170705966SRobert Morris // holds, one must hold icache.lock while using any of those fields. 1621c7aa960SRobert Morris // 163*4638cabfSRobert Morris // An ip->lock sleep-lock protects all ip-> fields other than ref, 1641c7aa960SRobert Morris // dev, and inum. One must hold ip->lock in order to 1651c7aa960SRobert Morris // read or write that inode's ip->valid, ip->size, ip->type, &c. 166bcca6c6bSrsc 167bcca6c6bSrsc struct { 168bcca6c6bSrsc struct spinlock lock; 169bcca6c6bSrsc struct inode inode[NINODE]; 170bcca6c6bSrsc } icache; 171bcca6c6bSrsc 172bcca6c6bSrsc void 1738320d61bSFrans Kaashoek iinit(int dev) 174bcca6c6bSrsc { 175dec637bcSFrans Kaashoek int i = 0; 176dec637bcSFrans Kaashoek 17734295f46Srsc initlock(&icache.lock, "icache"); 178dec637bcSFrans Kaashoek for(i = 0; i < NINODE; i++) { 179dec637bcSFrans Kaashoek initsleeplock(&icache.inode[i].lock, "inode"); 180dec637bcSFrans Kaashoek } 181dec637bcSFrans Kaashoek 1828320d61bSFrans Kaashoek readsb(dev, &sb); 183b7fed77bSFrans Kaashoek cprintf("sb: size %d nblocks %d ninodes %d nlog %d logstart %d\ 184b7fed77bSFrans Kaashoek inodestart %d bmap start %d\n", sb.size, sb.nblocks, 185b7fed77bSFrans Kaashoek sb.ninodes, sb.nlog, sb.logstart, sb.inodestart, 186b7fed77bSFrans Kaashoek sb.bmapstart); 187bcca6c6bSrsc } 188bcca6c6bSrsc 189f9a06440SRuss Cox static struct inode* iget(uint dev, uint inum); 190f9a06440SRuss Cox 191f9a06440SRuss Cox //PAGEBREAK! 19270705966SRobert Morris // Allocate an inode on device dev. 1936389d9d4SRobert Morris // Mark it as allocated by giving it type type. 19470705966SRobert Morris // Returns an unlocked but allocated and referenced inode. 195f9a06440SRuss Cox struct inode* 196f9a06440SRuss Cox ialloc(uint dev, short type) 197f9a06440SRuss Cox { 198f9a06440SRuss Cox int inum; 199f9a06440SRuss Cox struct buf *bp; 200f9a06440SRuss Cox struct dinode *dip; 201a5fbfe41SRobert Morris 202a5fbfe41SRobert Morris for(inum = 1; inum < sb.ninodes; inum++){ 2038320d61bSFrans Kaashoek bp = bread(dev, IBLOCK(inum, sb)); 204f9a06440SRuss Cox dip = (struct dinode*)bp->data + inum%IPB; 205f9a06440SRuss Cox if(dip->type == 0){ // a free inode 206f9a06440SRuss Cox memset(dip, 0, sizeof(*dip)); 207f9a06440SRuss Cox dip->type = type; 20813a96baeSFrans Kaashoek log_write(bp); // mark it allocated on the disk 209f9a06440SRuss Cox brelse(bp); 210f9a06440SRuss Cox return iget(dev, inum); 211f9a06440SRuss Cox } 212f9a06440SRuss Cox brelse(bp); 213f9a06440SRuss Cox } 214f9a06440SRuss Cox panic("ialloc: no inodes"); 215f9a06440SRuss Cox } 216f9a06440SRuss Cox 21738eee5bcSRobert Morris // Copy a modified in-memory inode to disk. 21870705966SRobert Morris // Must be called after every change to an ip->xxx field 21970705966SRobert Morris // that lives on disk, since i-node cache is write-through. 2201c7aa960SRobert Morris // Caller must hold ip->lock. 221f9a06440SRuss Cox void 222f9a06440SRuss Cox iupdate(struct inode *ip) 223f9a06440SRuss Cox { 224f9a06440SRuss Cox struct buf *bp; 225f9a06440SRuss Cox struct dinode *dip; 226f9a06440SRuss Cox 2278320d61bSFrans Kaashoek bp = bread(ip->dev, IBLOCK(ip->inum, sb)); 228f9a06440SRuss Cox dip = (struct dinode*)bp->data + ip->inum%IPB; 229f9a06440SRuss Cox dip->type = ip->type; 230f9a06440SRuss Cox dip->major = ip->major; 231f9a06440SRuss Cox dip->minor = ip->minor; 232f9a06440SRuss Cox dip->nlink = ip->nlink; 233f9a06440SRuss Cox dip->size = ip->size; 234f9a06440SRuss Cox memmove(dip->addrs, ip->addrs, sizeof(ip->addrs)); 23513a96baeSFrans Kaashoek log_write(bp); 236f9a06440SRuss Cox brelse(bp); 237f9a06440SRuss Cox } 238f9a06440SRuss Cox 239f5527388Srsc // Find the inode with number inum on device dev 24038eee5bcSRobert Morris // and return the in-memory copy. Does not lock 24138eee5bcSRobert Morris // the inode and does not read it from disk. 24207090dd7Srsc static struct inode* 24311a9947fSrtm iget(uint dev, uint inum) 24411a9947fSrtm { 245bcca6c6bSrsc struct inode *ip, *empty; 24611a9947fSrtm 247bcca6c6bSrsc acquire(&icache.lock); 24811a9947fSrtm 24938eee5bcSRobert Morris // Is the inode already cached? 250bcca6c6bSrsc empty = 0; 251bcca6c6bSrsc for(ip = &icache.inode[0]; ip < &icache.inode[NINODE]; ip++){ 2520d6bbd31Srsc if(ip->ref > 0 && ip->dev == dev && ip->inum == inum){ 2530d6bbd31Srsc ip->ref++; 254bcca6c6bSrsc release(&icache.lock); 25507090dd7Srsc return ip; 25611a9947fSrtm } 257bcca6c6bSrsc if(empty == 0 && ip->ref == 0) // Remember empty slot. 258bcca6c6bSrsc empty = ip; 25911a9947fSrtm } 26011a9947fSrtm 26138eee5bcSRobert Morris // Recycle an inode cache entry. 262bcca6c6bSrsc if(empty == 0) 26332eea766Srsc panic("iget: no inodes"); 26411a9947fSrtm 265bcca6c6bSrsc ip = empty; 266bcca6c6bSrsc ip->dev = dev; 267bcca6c6bSrsc ip->inum = inum; 268bcca6c6bSrsc ip->ref = 1; 2693375df50SRobert Morris ip->valid = 0; 270bcca6c6bSrsc release(&icache.lock); 27111a9947fSrtm 27207090dd7Srsc return ip; 273f32f3638Srsc } 274f32f3638Srsc 275eaea18cbSrsc // Increment reference count for ip. 276eaea18cbSrsc // Returns ip to enable ip = idup(ip1) idiom. 27707090dd7Srsc struct inode* 27807090dd7Srsc idup(struct inode *ip) 279f32f3638Srsc { 280eaea18cbSrsc acquire(&icache.lock); 281eaea18cbSrsc ip->ref++; 282eaea18cbSrsc release(&icache.lock); 28307090dd7Srsc return ip; 284f32f3638Srsc } 285f32f3638Srsc 2861ddfbbb1SFrans Kaashoek // Lock the given inode. 28738eee5bcSRobert Morris // Reads the inode from disk if necessary. 28807090dd7Srsc void 28907090dd7Srsc ilock(struct inode *ip) 290f32f3638Srsc { 291f32f3638Srsc struct buf *bp; 292f32f3638Srsc struct dinode *dip; 293eaea18cbSrsc 29407090dd7Srsc if(ip == 0 || ip->ref < 1) 29507090dd7Srsc panic("ilock"); 296f32f3638Srsc 297dec637bcSFrans Kaashoek acquiresleep(&ip->lock); 298f32f3638Srsc 2993375df50SRobert Morris if(ip->valid == 0){ 3008320d61bSFrans Kaashoek bp = bread(ip->dev, IBLOCK(ip->inum, sb)); 3013341e30fSrsc dip = (struct dinode*)bp->data + ip->inum%IPB; 302bcca6c6bSrsc ip->type = dip->type; 303bcca6c6bSrsc ip->major = dip->major; 304bcca6c6bSrsc ip->minor = dip->minor; 305bcca6c6bSrsc ip->nlink = dip->nlink; 306bcca6c6bSrsc ip->size = dip->size; 307bcca6c6bSrsc memmove(ip->addrs, dip->addrs, sizeof(ip->addrs)); 30811a9947fSrtm brelse(bp); 3093375df50SRobert Morris ip->valid = 1; 310eaea18cbSrsc if(ip->type == 0) 311eaea18cbSrsc panic("ilock: no type"); 31211a9947fSrtm } 313bcca6c6bSrsc } 314bcca6c6bSrsc 315bcca6c6bSrsc // Unlock the given inode. 31607090dd7Srsc void 317bcca6c6bSrsc iunlock(struct inode *ip) 318bcca6c6bSrsc { 319dec637bcSFrans Kaashoek if(ip == 0 || !holdingsleep(&ip->lock) || ip->ref < 1) 320bcca6c6bSrsc panic("iunlock"); 321bcca6c6bSrsc 322dec637bcSFrans Kaashoek releasesleep(&ip->lock); 323bcca6c6bSrsc } 324bcca6c6bSrsc 32538eee5bcSRobert Morris // Drop a reference to an in-memory inode. 32638eee5bcSRobert Morris // If that was the last reference, the inode cache entry can 32738eee5bcSRobert Morris // be recycled. 32838eee5bcSRobert Morris // If that was the last reference and the inode has no links 32938eee5bcSRobert Morris // to it, free the inode (and its content) on disk. 3302c565472SRobert Morris // All calls to iput() must be inside a transaction in 3312c565472SRobert Morris // case it has to free the inode. 332bcca6c6bSrsc void 33307090dd7Srsc iput(struct inode *ip) 334bcca6c6bSrsc { 335aba8423cSRobert Morris acquiresleep(&ip->lock); 33670d912b3SRobert Morris if(ip->valid && ip->nlink == 0){ 337a4ee6f7dSRobert Morris acquire(&icache.lock); 338a4ee6f7dSRobert Morris int r = ip->ref; 339f32f3638Srsc release(&icache.lock); 340a4ee6f7dSRobert Morris if(r == 1){ 341a4ee6f7dSRobert Morris // inode has no links and no other references: truncate and free. 342f32f3638Srsc itrunc(ip); 343f32f3638Srsc ip->type = 0; 344f32f3638Srsc iupdate(ip); 3453375df50SRobert Morris ip->valid = 0; 346a4ee6f7dSRobert Morris } 34770d912b3SRobert Morris } 348aba8423cSRobert Morris releasesleep(&ip->lock); 349a4ee6f7dSRobert Morris 350a4ee6f7dSRobert Morris acquire(&icache.lock); 351f32f3638Srsc ip->ref--; 352f32f3638Srsc release(&icache.lock); 353bcca6c6bSrsc } 354bcca6c6bSrsc 3557895178dSrsc // Common idiom: unlock, then put. 35607090dd7Srsc void 35707090dd7Srsc iunlockput(struct inode *ip) 35807090dd7Srsc { 35907090dd7Srsc iunlock(ip); 36007090dd7Srsc iput(ip); 36107090dd7Srsc } 36207090dd7Srsc 3638d2e9a48Srsc //PAGEBREAK! 36438eee5bcSRobert Morris // Inode content 365bcca6c6bSrsc // 36638eee5bcSRobert Morris // The content (data) associated with each inode is stored 36738eee5bcSRobert Morris // in blocks on the disk. The first NDIRECT block numbers 3687895178dSrsc // are listed in ip->addrs[]. The next NINDIRECT blocks are 36938eee5bcSRobert Morris // listed in block ip->addrs[NDIRECT]. 3709d3fb671Srtm 371bb207a1dSrsc // Return the disk block address of the nth block in inode ip. 37213ae8808Srsc // If there is no such block, bmap allocates one. 373eaea18cbSrsc static uint 37413ae8808Srsc bmap(struct inode *ip, uint bn) 37522bac2cbSkaashoek { 376bcca6c6bSrsc uint addr, *a; 377bcca6c6bSrsc struct buf *bp; 37822bac2cbSkaashoek 379ea2909b6Skaashoek if(bn < NDIRECT){ 38013ae8808Srsc if((addr = ip->addrs[bn]) == 0) 381bcca6c6bSrsc ip->addrs[bn] = addr = balloc(ip->dev); 382bcca6c6bSrsc return addr; 383bcca6c6bSrsc } 384bcca6c6bSrsc bn -= NDIRECT; 385bcca6c6bSrsc 386bcca6c6bSrsc if(bn < NINDIRECT){ 387bcca6c6bSrsc // Load indirect block, allocating if necessary. 38813ae8808Srsc if((addr = ip->addrs[NDIRECT]) == 0) 389ba6cd8a6Srsc ip->addrs[NDIRECT] = addr = balloc(ip->dev); 390bcca6c6bSrsc bp = bread(ip->dev, addr); 391bcca6c6bSrsc a = (uint*)bp->data; 392bcca6c6bSrsc if((addr = a[bn]) == 0){ 393bcca6c6bSrsc a[bn] = addr = balloc(ip->dev); 39413a96baeSFrans Kaashoek log_write(bp); 395bcca6c6bSrsc } 396bcca6c6bSrsc brelse(bp); 397bcca6c6bSrsc return addr; 39822bac2cbSkaashoek } 39922bac2cbSkaashoek 400bcca6c6bSrsc panic("bmap: out of range"); 401bcca6c6bSrsc } 402bcca6c6bSrsc 403bcca6c6bSrsc // Truncate inode (discard contents). 40438eee5bcSRobert Morris // Only called when the inode has no links 40538eee5bcSRobert Morris // to it (no directory entries referring to it) 40638eee5bcSRobert Morris // and has no in-memory reference to it (is 40738eee5bcSRobert Morris // not an open file or current directory). 408fbf91039Srsc static void 4092aa4c3bcSrtm itrunc(struct inode *ip) 41022bac2cbSkaashoek { 411ea2909b6Skaashoek int i, j; 412bcca6c6bSrsc struct buf *bp; 4137d4aef6cSrsc uint *a; 41422bac2cbSkaashoek 415bcca6c6bSrsc for(i = 0; i < NDIRECT; i++){ 416bcca6c6bSrsc if(ip->addrs[i]){ 41722bac2cbSkaashoek bfree(ip->dev, ip->addrs[i]); 41822bac2cbSkaashoek ip->addrs[i] = 0; 41922bac2cbSkaashoek } 42022bac2cbSkaashoek } 421bcca6c6bSrsc 422ba6cd8a6Srsc if(ip->addrs[NDIRECT]){ 423ba6cd8a6Srsc bp = bread(ip->dev, ip->addrs[NDIRECT]); 424bcca6c6bSrsc a = (uint*)bp->data; 425bcca6c6bSrsc for(j = 0; j < NINDIRECT; j++){ 426bcca6c6bSrsc if(a[j]) 427bcca6c6bSrsc bfree(ip->dev, a[j]); 428bcca6c6bSrsc } 429bcca6c6bSrsc brelse(bp); 430ba6cd8a6Srsc bfree(ip->dev, ip->addrs[NDIRECT]); 431ba6cd8a6Srsc ip->addrs[NDIRECT] = 0; 432bcca6c6bSrsc } 433bcca6c6bSrsc 43422bac2cbSkaashoek ip->size = 0; 43522bac2cbSkaashoek iupdate(ip); 43622bac2cbSkaashoek } 43722bac2cbSkaashoek 438bb207a1dSrsc // Copy stat information from inode. 4391c7aa960SRobert Morris // Caller must hold ip->lock. 440e958c538Skaashoek void 4411f544842Skaashoek stati(struct inode *ip, struct stat *st) 4421f544842Skaashoek { 4431dca3afbSrsc st->dev = ip->dev; 4441dca3afbSrsc st->ino = ip->inum; 4451dca3afbSrsc st->type = ip->type; 4461dca3afbSrsc st->nlink = ip->nlink; 4471dca3afbSrsc st->size = ip->size; 4481f544842Skaashoek } 4491f544842Skaashoek 450eaea18cbSrsc //PAGEBREAK! 451bb207a1dSrsc // Read data from inode. 4521c7aa960SRobert Morris // Caller must hold ip->lock. 453c59361f1Srtm int 45417a85657Srtm readi(struct inode *ip, char *dst, uint off, uint n) 455c59361f1Srtm { 456bcca6c6bSrsc uint tot, m; 457c59361f1Srtm struct buf *bp; 458c59361f1Srtm 459939f9edeSkaashoek if(ip->type == T_DEV){ 4601dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].read) 461939f9edeSkaashoek return -1; 462d844f0f9Srsc return devsw[ip->major].read(ip, dst, n); 463939f9edeSkaashoek } 464939f9edeSkaashoek 4657895178dSrsc if(off > ip->size || off + n < off) 466bcca6c6bSrsc return -1; 467bcca6c6bSrsc if(off + n > ip->size) 468bcca6c6bSrsc n = ip->size - off; 469bcca6c6bSrsc 470bcca6c6bSrsc for(tot=0; tot<n; tot+=m, off+=m, dst+=m){ 47113ae8808Srsc bp = bread(ip->dev, bmap(ip, off/BSIZE)); 472bcca6c6bSrsc m = min(n - tot, BSIZE - off%BSIZE); 473bcca6c6bSrsc memmove(dst, bp->data + off%BSIZE, m); 474c59361f1Srtm brelse(bp); 475c59361f1Srtm } 476bcca6c6bSrsc return n; 477ea2909b6Skaashoek } 478ea2909b6Skaashoek 479eaea18cbSrsc // PAGEBREAK! 480bb207a1dSrsc // Write data to inode. 4811c7aa960SRobert Morris // Caller must hold ip->lock. 482ea2909b6Skaashoek int 483bcca6c6bSrsc writei(struct inode *ip, char *src, uint off, uint n) 4846fa5ffb5Skaashoek { 485bcca6c6bSrsc uint tot, m; 4867d4aef6cSrsc struct buf *bp; 4877d4aef6cSrsc 4886fa5ffb5Skaashoek if(ip->type == T_DEV){ 4891dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].write) 490939f9edeSkaashoek return -1; 491d844f0f9Srsc return devsw[ip->major].write(ip, src, n); 4927d4aef6cSrsc } 4937d4aef6cSrsc 4941ddfbbb1SFrans Kaashoek if(off > ip->size || off + n < off) 495bcca6c6bSrsc return -1; 4961ddfbbb1SFrans Kaashoek if(off + n > MAXFILE*BSIZE) 4972e590463SRobert Morris return -1; 498bcca6c6bSrsc 499bcca6c6bSrsc for(tot=0; tot<n; tot+=m, off+=m, src+=m){ 50013ae8808Srsc bp = bread(ip->dev, bmap(ip, off/BSIZE)); 501bcca6c6bSrsc m = min(n - tot, BSIZE - off%BSIZE); 502bcca6c6bSrsc memmove(bp->data + off%BSIZE, src, m); 5032e590463SRobert Morris log_write(bp); 50428d9ef04Skaashoek brelse(bp); 50528d9ef04Skaashoek } 506bcca6c6bSrsc 507bcca6c6bSrsc if(n > 0 && off > ip->size){ 50848b82470Srsc ip->size = off; 50928d9ef04Skaashoek iupdate(ip); 51028d9ef04Skaashoek } 511bcca6c6bSrsc return n; 5126fa5ffb5Skaashoek } 5136fa5ffb5Skaashoek 514eaea18cbSrsc //PAGEBREAK! 515bcca6c6bSrsc // Directories 516bcca6c6bSrsc 517eaea18cbSrsc int 518fbf91039Srsc namecmp(const char *s, const char *t) 519fbf91039Srsc { 520766ba5ccSrsc return strncmp(s, t, DIRSIZ); 521fbf91039Srsc } 522fbf91039Srsc 523bcca6c6bSrsc // Look for a directory entry in a directory. 524eaea18cbSrsc // If found, set *poff to byte offset of entry. 52507090dd7Srsc struct inode* 526fbf91039Srsc dirlookup(struct inode *dp, char *name, uint *poff) 527bcca6c6bSrsc { 528f32f3638Srsc uint off, inum; 529327cc21fSRobert Morris struct dirent de; 530bcca6c6bSrsc 531bcca6c6bSrsc if(dp->type != T_DIR) 53220365348Srtm panic("dirlookup not DIR"); 533bcca6c6bSrsc 534327cc21fSRobert Morris for(off = 0; off < dp->size; off += sizeof(de)){ 535327cc21fSRobert Morris if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 53661f26e3cSGrant Wu panic("dirlookup read"); 537327cc21fSRobert Morris if(de.inum == 0) 538bcca6c6bSrsc continue; 539327cc21fSRobert Morris if(namecmp(name, de.name) == 0){ 540bcca6c6bSrsc // entry matches path element 541e2a620daSrsc if(poff) 542327cc21fSRobert Morris *poff = off; 543327cc21fSRobert Morris inum = de.inum; 544f32f3638Srsc return iget(dp->dev, inum); 545f32f3638Srsc } 546f32f3638Srsc } 547327cc21fSRobert Morris 548bcca6c6bSrsc return 0; 549bcca6c6bSrsc } 550bcca6c6bSrsc 55113ae8808Srsc // Write a new directory entry (name, inum) into the directory dp. 552eaea18cbSrsc int 55313ae8808Srsc dirlink(struct inode *dp, char *name, uint inum) 554bcca6c6bSrsc { 555e2a620daSrsc int off; 556bcca6c6bSrsc struct dirent de; 55707090dd7Srsc struct inode *ip; 558f32f3638Srsc 559eaea18cbSrsc // Check that name is not present. 56007090dd7Srsc if((ip = dirlookup(dp, name, 0)) != 0){ 56107090dd7Srsc iput(ip); 562f32f3638Srsc return -1; 563f32f3638Srsc } 564bcca6c6bSrsc 565bcca6c6bSrsc // Look for an empty dirent. 566bcca6c6bSrsc for(off = 0; off < dp->size; off += sizeof(de)){ 567bcca6c6bSrsc if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 5687895178dSrsc panic("dirlink read"); 569bcca6c6bSrsc if(de.inum == 0) 570bcca6c6bSrsc break; 571bcca6c6bSrsc } 572bcca6c6bSrsc 573766ba5ccSrsc strncpy(de.name, name, DIRSIZ); 57413ae8808Srsc de.inum = inum; 575bcca6c6bSrsc if(writei(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 5767895178dSrsc panic("dirlink"); 577f32f3638Srsc 578f32f3638Srsc return 0; 579bcca6c6bSrsc } 580bcca6c6bSrsc 5818d2e9a48Srsc //PAGEBREAK! 582bcca6c6bSrsc // Paths 583bcca6c6bSrsc 584eaea18cbSrsc // Copy the next path element from path into name. 585eaea18cbSrsc // Return a pointer to the element following the copied one. 586eaea18cbSrsc // The returned path has no leading slashes, 587eaea18cbSrsc // so the caller can check *path=='\0' to see if the name is the last one. 588eaea18cbSrsc // If no name to remove, return 0. 589ab5c2dbbSrsc // 590ab5c2dbbSrsc // Examples: 591eaea18cbSrsc // skipelem("a/bb/c", name) = "bb/c", setting name = "a" 5927895178dSrsc // skipelem("///a//bb", name) = "bb", setting name = "a" 59313ae8808Srsc // skipelem("a", name) = "", setting name = "a" 594eaea18cbSrsc // skipelem("", name) = skipelem("////", name) = 0 595ab5c2dbbSrsc // 596ab5c2dbbSrsc static char* 597fbf91039Srsc skipelem(char *path, char *name) 598ab5c2dbbSrsc { 599fbf91039Srsc char *s; 600fbf91039Srsc int len; 601fbf91039Srsc 602ab5c2dbbSrsc while(*path == '/') 603ab5c2dbbSrsc path++; 604ab5c2dbbSrsc if(*path == 0) 605ab5c2dbbSrsc return 0; 606fbf91039Srsc s = path; 607ab5c2dbbSrsc while(*path != '/' && *path != 0) 608ab5c2dbbSrsc path++; 609fbf91039Srsc len = path - s; 610fbf91039Srsc if(len >= DIRSIZ) 611fbf91039Srsc memmove(name, s, DIRSIZ); 612fbf91039Srsc else { 613fbf91039Srsc memmove(name, s, len); 614fbf91039Srsc name[len] = 0; 615fbf91039Srsc } 616ab5c2dbbSrsc while(*path == '/') 617ab5c2dbbSrsc path++; 618ab5c2dbbSrsc return path; 619ab5c2dbbSrsc } 620ab5c2dbbSrsc 621eaea18cbSrsc // Look up and return the inode for a path name. 622bf2932a6Srsc // If parent != 0, return the inode for the parent and copy the final 623bf2932a6Srsc // path element into name, which must have room for DIRSIZ bytes. 6242c565472SRobert Morris // Must be called inside a transaction since it calls iput(). 62507090dd7Srsc static struct inode* 626f9a06440SRuss Cox namex(char *path, int nameiparent, char *name) 6279d3fb671Srtm { 62807090dd7Srsc struct inode *ip, *next; 6299d3fb671Srtm 630ab5c2dbbSrsc if(*path == '/') 6312ce40d70Srtm ip = iget(ROOTDEV, ROOTINO); 632f32f3638Srsc else 633abf847a0SFrans Kaashoek ip = idup(myproc()->cwd); 6349d3fb671Srtm 635fbf91039Srsc while((path = skipelem(path, name)) != 0){ 63607090dd7Srsc ilock(ip); 63707090dd7Srsc if(ip->type != T_DIR){ 63807090dd7Srsc iunlockput(ip); 639eaea18cbSrsc return 0; 640eaea18cbSrsc } 641f9a06440SRuss Cox if(nameiparent && *path == '\0'){ 642e2a620daSrsc // Stop one level early. 64307090dd7Srsc iunlock(ip); 64407090dd7Srsc return ip; 645ab5c2dbbSrsc } 6467895178dSrsc if((next = dirlookup(ip, name, 0)) == 0){ 64707090dd7Srsc iunlockput(ip); 648eaea18cbSrsc return 0; 649eaea18cbSrsc } 65007090dd7Srsc iunlockput(ip); 65107090dd7Srsc ip = next; 652ab5c2dbbSrsc } 653f9a06440SRuss Cox if(nameiparent){ 65407090dd7Srsc iput(ip); 6555051da6dSrtm return 0; 65620365348Srtm } 65707090dd7Srsc return ip; 6580633b971Skaashoek } 6599d3fb671Srtm 6607895178dSrsc struct inode* 6617895178dSrsc namei(char *path) 6627895178dSrsc { 6637895178dSrsc char name[DIRSIZ]; 66413ae8808Srsc return namex(path, 0, name); 6657895178dSrsc } 666bf2932a6Srsc 6677895178dSrsc struct inode* 6687895178dSrsc nameiparent(char *path, char *name) 6697895178dSrsc { 67013ae8808Srsc return namex(path, 1, name); 6717895178dSrsc } 672