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" 1911a9947fSrtm #include "fs.h" 20c24ac5d7SFrans Kaashoek #include "buf.h" 210aef8914SRuss Cox #include "file.h" 2211a9947fSrtm 23bcca6c6bSrsc #define min(a, b) ((a) < (b) ? (a) : (b)) 24fbf91039Srsc static void itrunc(struct inode*); 25*8320d61bSFrans Kaashoek struct superblock sb; // there should be one per dev, but we run with one dev 2611a9947fSrtm 27a505fd66Srsc // Read the super block. 2813a96baeSFrans Kaashoek void 29a505fd66Srsc readsb(int dev, struct superblock *sb) 30a505fd66Srsc { 31a505fd66Srsc struct buf *bp; 32a505fd66Srsc 33a505fd66Srsc bp = bread(dev, 1); 34a505fd66Srsc memmove(sb, bp->data, sizeof(*sb)); 35a505fd66Srsc brelse(bp); 36a505fd66Srsc } 37a505fd66Srsc 38a505fd66Srsc // Zero a block. 39a505fd66Srsc static void 40a505fd66Srsc bzero(int dev, int bno) 41a505fd66Srsc { 42a505fd66Srsc struct buf *bp; 43a505fd66Srsc 44a505fd66Srsc bp = bread(dev, bno); 45a505fd66Srsc memset(bp->data, 0, BSIZE); 465053dd6aSRobert Morris log_write(bp); 47a505fd66Srsc brelse(bp); 48a505fd66Srsc } 49a505fd66Srsc 50bcca6c6bSrsc // Blocks. 515be0039cSrtm 525053dd6aSRobert Morris // Allocate a zeroed disk block. 5324111398Skaashoek static uint 5424111398Skaashoek balloc(uint dev) 5524111398Skaashoek { 56a505fd66Srsc int b, bi, m; 5724111398Skaashoek struct buf *bp; 5824111398Skaashoek 59a505fd66Srsc bp = 0; 60a505fd66Srsc for(b = 0; b < sb.size; b += BPB){ 61*8320d61bSFrans Kaashoek bp = bread(dev, BBLOCK(b, sb)); 62a5fbfe41SRobert Morris for(bi = 0; bi < BPB && b + bi < sb.size; bi++){ 63a505fd66Srsc m = 1 << (bi % 8); 64a505fd66Srsc if((bp->data[bi/8] & m) == 0){ // Is block free? 65a5fbfe41SRobert Morris bp->data[bi/8] |= m; // Mark block in use. 6613a96baeSFrans Kaashoek log_write(bp); 6724111398Skaashoek brelse(bp); 685053dd6aSRobert Morris bzero(dev, b + bi); 69a505fd66Srsc return b + bi; 7024111398Skaashoek } 71a505fd66Srsc } 7228d9ef04Skaashoek brelse(bp); 737d4aef6cSrsc } 747d4aef6cSrsc panic("balloc: out of blocks"); 757d4aef6cSrsc } 7624111398Skaashoek 77bb207a1dSrsc // Free a disk block. 7828d9ef04Skaashoek static void 7928d9ef04Skaashoek bfree(int dev, uint b) 8028d9ef04Skaashoek { 8128d9ef04Skaashoek struct buf *bp; 82a505fd66Srsc int bi, m; 8328d9ef04Skaashoek 84a505fd66Srsc readsb(dev, &sb); 85*8320d61bSFrans Kaashoek bp = bread(dev, BBLOCK(b, sb)); 8628d9ef04Skaashoek bi = b % BPB; 87a505fd66Srsc m = 1 << (bi % 8); 88902b13f5Srtm if((bp->data[bi/8] & m) == 0) 89902b13f5Srtm panic("freeing free block"); 90a5fbfe41SRobert Morris bp->data[bi/8] &= ~m; 9113a96baeSFrans Kaashoek log_write(bp); 9228d9ef04Skaashoek brelse(bp); 9328d9ef04Skaashoek } 9424111398Skaashoek 956c34f97cSrsc // Inodes. 966c34f97cSrsc // 97a5fbfe41SRobert Morris // An inode describes a single unnamed file. 98a5fbfe41SRobert Morris // The inode disk structure holds metadata: the file's type, 99a5fbfe41SRobert Morris // its size, the number of links referring to it, and the 100a5fbfe41SRobert Morris // list of blocks holding the file's content. 101bcca6c6bSrsc // 102*8320d61bSFrans Kaashoek // The inodes are laid out sequentially on disk at 103*8320d61bSFrans Kaashoek // sb.startinode. Each inode has a number, indicating its 104a5fbfe41SRobert Morris // position on the disk. 105a5fbfe41SRobert Morris // 106a5fbfe41SRobert Morris // The kernel keeps a cache of in-use inodes in memory 107a5fbfe41SRobert Morris // to provide a place for synchronizing access 108a5fbfe41SRobert Morris // to inodes used by multiple processes. The cached 109a5fbfe41SRobert Morris // inodes include book-keeping information that is 110a5fbfe41SRobert Morris // not stored on disk: ip->ref and ip->flags. 111bcca6c6bSrsc // 11238eee5bcSRobert Morris // An inode and its in-memory represtative go through a 11338eee5bcSRobert Morris // sequence of states before they can be used by the 11438eee5bcSRobert Morris // rest of the file system code. 115bcca6c6bSrsc // 11638eee5bcSRobert Morris // * Allocation: an inode is allocated if its type (on disk) 11738eee5bcSRobert Morris // is non-zero. ialloc() allocates, iput() frees if 11838eee5bcSRobert Morris // the link count has fallen to zero. 119eaea18cbSrsc // 12038eee5bcSRobert Morris // * Referencing in cache: an entry in the inode cache 12138eee5bcSRobert Morris // is free if ip->ref is zero. Otherwise ip->ref tracks 12238eee5bcSRobert Morris // the number of in-memory pointers to the entry (open 12338eee5bcSRobert Morris // files and current directories). iget() to find or 12438eee5bcSRobert Morris // create a cache entry and increment its ref, iput() 12538eee5bcSRobert Morris // to decrement ref. 126a5fbfe41SRobert Morris // 12738eee5bcSRobert Morris // * Valid: the information (type, size, &c) in an inode 12838eee5bcSRobert Morris // cache entry is only correct when the I_VALID bit 12938eee5bcSRobert Morris // is set in ip->flags. ilock() reads the inode from 13038eee5bcSRobert Morris // the disk and sets I_VALID, while iput() clears 13138eee5bcSRobert Morris // I_VALID if ip->ref has fallen to zero. 132a5fbfe41SRobert Morris // 13338eee5bcSRobert Morris // * Locked: file system code may only examine and modify 13438eee5bcSRobert Morris // the information in an inode and its content if it 13538eee5bcSRobert Morris // has first locked the inode. The I_BUSY flag indicates 13638eee5bcSRobert Morris // that the inode is locked. ilock() sets I_BUSY, 13738eee5bcSRobert Morris // while iunlock clears it. 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. 156bcca6c6bSrsc 157bcca6c6bSrsc struct { 158bcca6c6bSrsc struct spinlock lock; 159bcca6c6bSrsc struct inode inode[NINODE]; 160bcca6c6bSrsc } icache; 161bcca6c6bSrsc 162bcca6c6bSrsc void 163*8320d61bSFrans Kaashoek iinit(int dev) 164bcca6c6bSrsc { 16534295f46Srsc initlock(&icache.lock, "icache"); 166*8320d61bSFrans Kaashoek readsb(dev, &sb); 167*8320d61bSFrans Kaashoek cprintf("sb: size %d nblocks %d ninodes %d nlog %d logstart %d inodestart %d bmap start %d\n", sb.size, 168*8320d61bSFrans Kaashoek sb.nblocks, sb.ninodes, sb.nlog, sb.logstart, sb.inodestart, sb.bmapstart); 169bcca6c6bSrsc } 170bcca6c6bSrsc 171f9a06440SRuss Cox static struct inode* iget(uint dev, uint inum); 172f9a06440SRuss Cox 173f9a06440SRuss Cox //PAGEBREAK! 174f9a06440SRuss Cox // Allocate a new inode with the given type on device dev. 175a5fbfe41SRobert Morris // A free inode has a type of zero. 176f9a06440SRuss Cox struct inode* 177f9a06440SRuss Cox ialloc(uint dev, short type) 178f9a06440SRuss Cox { 179f9a06440SRuss Cox int inum; 180f9a06440SRuss Cox struct buf *bp; 181f9a06440SRuss Cox struct dinode *dip; 182a5fbfe41SRobert Morris 183a5fbfe41SRobert Morris for(inum = 1; inum < sb.ninodes; inum++){ 184*8320d61bSFrans Kaashoek bp = bread(dev, IBLOCK(inum, sb)); 185f9a06440SRuss Cox dip = (struct dinode*)bp->data + inum%IPB; 186f9a06440SRuss Cox if(dip->type == 0){ // a free inode 187f9a06440SRuss Cox memset(dip, 0, sizeof(*dip)); 188f9a06440SRuss Cox dip->type = type; 18913a96baeSFrans Kaashoek log_write(bp); // mark it allocated on the disk 190f9a06440SRuss Cox brelse(bp); 191f9a06440SRuss Cox return iget(dev, inum); 192f9a06440SRuss Cox } 193f9a06440SRuss Cox brelse(bp); 194f9a06440SRuss Cox } 195f9a06440SRuss Cox panic("ialloc: no inodes"); 196f9a06440SRuss Cox } 197f9a06440SRuss Cox 19838eee5bcSRobert Morris // Copy a modified in-memory inode to disk. 199f9a06440SRuss Cox void 200f9a06440SRuss Cox iupdate(struct inode *ip) 201f9a06440SRuss Cox { 202f9a06440SRuss Cox struct buf *bp; 203f9a06440SRuss Cox struct dinode *dip; 204f9a06440SRuss Cox 205*8320d61bSFrans Kaashoek bp = bread(ip->dev, IBLOCK(ip->inum, sb)); 206f9a06440SRuss Cox dip = (struct dinode*)bp->data + ip->inum%IPB; 207f9a06440SRuss Cox dip->type = ip->type; 208f9a06440SRuss Cox dip->major = ip->major; 209f9a06440SRuss Cox dip->minor = ip->minor; 210f9a06440SRuss Cox dip->nlink = ip->nlink; 211f9a06440SRuss Cox dip->size = ip->size; 212f9a06440SRuss Cox memmove(dip->addrs, ip->addrs, sizeof(ip->addrs)); 21313a96baeSFrans Kaashoek log_write(bp); 214f9a06440SRuss Cox brelse(bp); 215f9a06440SRuss Cox } 216f9a06440SRuss Cox 217f5527388Srsc // Find the inode with number inum on device dev 21838eee5bcSRobert Morris // and return the in-memory copy. Does not lock 21938eee5bcSRobert Morris // the inode and does not read it from disk. 22007090dd7Srsc static struct inode* 22111a9947fSrtm iget(uint dev, uint inum) 22211a9947fSrtm { 223bcca6c6bSrsc struct inode *ip, *empty; 22411a9947fSrtm 225bcca6c6bSrsc acquire(&icache.lock); 22611a9947fSrtm 22738eee5bcSRobert Morris // Is the inode already cached? 228bcca6c6bSrsc empty = 0; 229bcca6c6bSrsc for(ip = &icache.inode[0]; ip < &icache.inode[NINODE]; ip++){ 2300d6bbd31Srsc if(ip->ref > 0 && ip->dev == dev && ip->inum == inum){ 2310d6bbd31Srsc ip->ref++; 232bcca6c6bSrsc release(&icache.lock); 23307090dd7Srsc return ip; 23411a9947fSrtm } 235bcca6c6bSrsc if(empty == 0 && ip->ref == 0) // Remember empty slot. 236bcca6c6bSrsc empty = ip; 23711a9947fSrtm } 23811a9947fSrtm 23938eee5bcSRobert Morris // Recycle an inode cache entry. 240bcca6c6bSrsc if(empty == 0) 24132eea766Srsc panic("iget: no inodes"); 24211a9947fSrtm 243bcca6c6bSrsc ip = empty; 244bcca6c6bSrsc ip->dev = dev; 245bcca6c6bSrsc ip->inum = inum; 246bcca6c6bSrsc ip->ref = 1; 247f32f3638Srsc ip->flags = 0; 248bcca6c6bSrsc release(&icache.lock); 24911a9947fSrtm 25007090dd7Srsc return ip; 251f32f3638Srsc } 252f32f3638Srsc 253eaea18cbSrsc // Increment reference count for ip. 254eaea18cbSrsc // Returns ip to enable ip = idup(ip1) idiom. 25507090dd7Srsc struct inode* 25607090dd7Srsc idup(struct inode *ip) 257f32f3638Srsc { 258eaea18cbSrsc acquire(&icache.lock); 259eaea18cbSrsc ip->ref++; 260eaea18cbSrsc release(&icache.lock); 26107090dd7Srsc return ip; 262f32f3638Srsc } 263f32f3638Srsc 2641ddfbbb1SFrans Kaashoek // Lock the given inode. 26538eee5bcSRobert Morris // Reads the inode from disk if necessary. 26607090dd7Srsc void 26707090dd7Srsc ilock(struct inode *ip) 268f32f3638Srsc { 269f32f3638Srsc struct buf *bp; 270f32f3638Srsc struct dinode *dip; 271eaea18cbSrsc 27207090dd7Srsc if(ip == 0 || ip->ref < 1) 27307090dd7Srsc panic("ilock"); 274f32f3638Srsc 275f32f3638Srsc acquire(&icache.lock); 2761ddfbbb1SFrans Kaashoek while(ip->flags & I_BUSY) 2771ddfbbb1SFrans Kaashoek sleep(ip, &icache.lock); 2781ddfbbb1SFrans Kaashoek ip->flags |= I_BUSY; 279f32f3638Srsc release(&icache.lock); 280f32f3638Srsc 281f32f3638Srsc if(!(ip->flags & I_VALID)){ 282*8320d61bSFrans Kaashoek bp = bread(ip->dev, IBLOCK(ip->inum, sb)); 2833341e30fSrsc dip = (struct dinode*)bp->data + ip->inum%IPB; 284bcca6c6bSrsc ip->type = dip->type; 285bcca6c6bSrsc ip->major = dip->major; 286bcca6c6bSrsc ip->minor = dip->minor; 287bcca6c6bSrsc ip->nlink = dip->nlink; 288bcca6c6bSrsc ip->size = dip->size; 289bcca6c6bSrsc memmove(ip->addrs, dip->addrs, sizeof(ip->addrs)); 29011a9947fSrtm brelse(bp); 291f32f3638Srsc ip->flags |= I_VALID; 292eaea18cbSrsc if(ip->type == 0) 293eaea18cbSrsc panic("ilock: no type"); 29411a9947fSrtm } 295bcca6c6bSrsc } 296bcca6c6bSrsc 297bcca6c6bSrsc // Unlock the given inode. 29807090dd7Srsc void 299bcca6c6bSrsc iunlock(struct inode *ip) 300bcca6c6bSrsc { 3011ddfbbb1SFrans Kaashoek if(ip == 0 || !(ip->flags & I_BUSY) || ip->ref < 1) 302bcca6c6bSrsc panic("iunlock"); 303bcca6c6bSrsc 304bcca6c6bSrsc acquire(&icache.lock); 3051ddfbbb1SFrans Kaashoek ip->flags &= ~I_BUSY; 3061ddfbbb1SFrans Kaashoek wakeup(ip); 307bcca6c6bSrsc release(&icache.lock); 308bcca6c6bSrsc } 309bcca6c6bSrsc 31038eee5bcSRobert Morris // Drop a reference to an in-memory inode. 31138eee5bcSRobert Morris // If that was the last reference, the inode cache entry can 31238eee5bcSRobert Morris // be recycled. 31338eee5bcSRobert Morris // If that was the last reference and the inode has no links 31438eee5bcSRobert Morris // to it, free the inode (and its content) on disk. 3152c565472SRobert Morris // All calls to iput() must be inside a transaction in 3162c565472SRobert Morris // case it has to free the inode. 317bcca6c6bSrsc void 31807090dd7Srsc iput(struct inode *ip) 319bcca6c6bSrsc { 320f32f3638Srsc acquire(&icache.lock); 321f32f3638Srsc if(ip->ref == 1 && (ip->flags & I_VALID) && ip->nlink == 0){ 322e2b4583dSRobert Morris // inode has no links and no other references: truncate and free. 3231ddfbbb1SFrans Kaashoek if(ip->flags & I_BUSY) 324eaea18cbSrsc panic("iput busy"); 3251ddfbbb1SFrans Kaashoek ip->flags |= I_BUSY; 326f32f3638Srsc release(&icache.lock); 327f32f3638Srsc itrunc(ip); 328f32f3638Srsc ip->type = 0; 329f32f3638Srsc iupdate(ip); 330f32f3638Srsc acquire(&icache.lock); 331ce72cadbSrsc ip->flags = 0; 3328970df0cSrsc wakeup(ip); 333f32f3638Srsc } 334f32f3638Srsc ip->ref--; 335f32f3638Srsc release(&icache.lock); 336bcca6c6bSrsc } 337bcca6c6bSrsc 3387895178dSrsc // Common idiom: unlock, then put. 33907090dd7Srsc void 34007090dd7Srsc iunlockput(struct inode *ip) 34107090dd7Srsc { 34207090dd7Srsc iunlock(ip); 34307090dd7Srsc iput(ip); 34407090dd7Srsc } 34507090dd7Srsc 3468d2e9a48Srsc //PAGEBREAK! 34738eee5bcSRobert Morris // Inode content 348bcca6c6bSrsc // 34938eee5bcSRobert Morris // The content (data) associated with each inode is stored 35038eee5bcSRobert Morris // in blocks on the disk. The first NDIRECT block numbers 3517895178dSrsc // are listed in ip->addrs[]. The next NINDIRECT blocks are 35238eee5bcSRobert Morris // listed in block ip->addrs[NDIRECT]. 3539d3fb671Srtm 354bb207a1dSrsc // Return the disk block address of the nth block in inode ip. 35513ae8808Srsc // If there is no such block, bmap allocates one. 356eaea18cbSrsc static uint 35713ae8808Srsc bmap(struct inode *ip, uint bn) 35822bac2cbSkaashoek { 359bcca6c6bSrsc uint addr, *a; 360bcca6c6bSrsc struct buf *bp; 36122bac2cbSkaashoek 362ea2909b6Skaashoek if(bn < NDIRECT){ 36313ae8808Srsc if((addr = ip->addrs[bn]) == 0) 364bcca6c6bSrsc ip->addrs[bn] = addr = balloc(ip->dev); 365bcca6c6bSrsc return addr; 366bcca6c6bSrsc } 367bcca6c6bSrsc bn -= NDIRECT; 368bcca6c6bSrsc 369bcca6c6bSrsc if(bn < NINDIRECT){ 370bcca6c6bSrsc // Load indirect block, allocating if necessary. 37113ae8808Srsc if((addr = ip->addrs[NDIRECT]) == 0) 372ba6cd8a6Srsc ip->addrs[NDIRECT] = addr = balloc(ip->dev); 373bcca6c6bSrsc bp = bread(ip->dev, addr); 374bcca6c6bSrsc a = (uint*)bp->data; 375bcca6c6bSrsc if((addr = a[bn]) == 0){ 376bcca6c6bSrsc a[bn] = addr = balloc(ip->dev); 37713a96baeSFrans Kaashoek log_write(bp); 378bcca6c6bSrsc } 379bcca6c6bSrsc brelse(bp); 380bcca6c6bSrsc return addr; 38122bac2cbSkaashoek } 38222bac2cbSkaashoek 383bcca6c6bSrsc panic("bmap: out of range"); 384bcca6c6bSrsc } 385bcca6c6bSrsc 386bcca6c6bSrsc // Truncate inode (discard contents). 38738eee5bcSRobert Morris // Only called when the inode has no links 38838eee5bcSRobert Morris // to it (no directory entries referring to it) 38938eee5bcSRobert Morris // and has no in-memory reference to it (is 39038eee5bcSRobert Morris // not an open file or current directory). 391fbf91039Srsc static void 3922aa4c3bcSrtm itrunc(struct inode *ip) 39322bac2cbSkaashoek { 394ea2909b6Skaashoek int i, j; 395bcca6c6bSrsc struct buf *bp; 3967d4aef6cSrsc uint *a; 39722bac2cbSkaashoek 398bcca6c6bSrsc for(i = 0; i < NDIRECT; i++){ 399bcca6c6bSrsc if(ip->addrs[i]){ 40022bac2cbSkaashoek bfree(ip->dev, ip->addrs[i]); 40122bac2cbSkaashoek ip->addrs[i] = 0; 40222bac2cbSkaashoek } 40322bac2cbSkaashoek } 404bcca6c6bSrsc 405ba6cd8a6Srsc if(ip->addrs[NDIRECT]){ 406ba6cd8a6Srsc bp = bread(ip->dev, ip->addrs[NDIRECT]); 407bcca6c6bSrsc a = (uint*)bp->data; 408bcca6c6bSrsc for(j = 0; j < NINDIRECT; j++){ 409bcca6c6bSrsc if(a[j]) 410bcca6c6bSrsc bfree(ip->dev, a[j]); 411bcca6c6bSrsc } 412bcca6c6bSrsc brelse(bp); 413ba6cd8a6Srsc bfree(ip->dev, ip->addrs[NDIRECT]); 414ba6cd8a6Srsc ip->addrs[NDIRECT] = 0; 415bcca6c6bSrsc } 416bcca6c6bSrsc 41722bac2cbSkaashoek ip->size = 0; 41822bac2cbSkaashoek iupdate(ip); 41922bac2cbSkaashoek } 42022bac2cbSkaashoek 421bb207a1dSrsc // Copy stat information from inode. 422e958c538Skaashoek void 4231f544842Skaashoek stati(struct inode *ip, struct stat *st) 4241f544842Skaashoek { 4251dca3afbSrsc st->dev = ip->dev; 4261dca3afbSrsc st->ino = ip->inum; 4271dca3afbSrsc st->type = ip->type; 4281dca3afbSrsc st->nlink = ip->nlink; 4291dca3afbSrsc st->size = ip->size; 4301f544842Skaashoek } 4311f544842Skaashoek 432eaea18cbSrsc //PAGEBREAK! 433bb207a1dSrsc // Read data from inode. 434c59361f1Srtm int 43517a85657Srtm readi(struct inode *ip, char *dst, uint off, uint n) 436c59361f1Srtm { 437bcca6c6bSrsc uint tot, m; 438c59361f1Srtm struct buf *bp; 439c59361f1Srtm 440939f9edeSkaashoek if(ip->type == T_DEV){ 4411dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].read) 442939f9edeSkaashoek return -1; 443d844f0f9Srsc return devsw[ip->major].read(ip, dst, n); 444939f9edeSkaashoek } 445939f9edeSkaashoek 4467895178dSrsc if(off > ip->size || off + n < off) 447bcca6c6bSrsc return -1; 448bcca6c6bSrsc if(off + n > ip->size) 449bcca6c6bSrsc n = ip->size - off; 450bcca6c6bSrsc 451bcca6c6bSrsc for(tot=0; tot<n; tot+=m, off+=m, dst+=m){ 45213ae8808Srsc bp = bread(ip->dev, bmap(ip, off/BSIZE)); 453bcca6c6bSrsc m = min(n - tot, BSIZE - off%BSIZE); 454bcca6c6bSrsc memmove(dst, bp->data + off%BSIZE, m); 455c59361f1Srtm brelse(bp); 456c59361f1Srtm } 457bcca6c6bSrsc return n; 458ea2909b6Skaashoek } 459ea2909b6Skaashoek 460eaea18cbSrsc // PAGEBREAK! 461bb207a1dSrsc // Write data to inode. 462ea2909b6Skaashoek int 463bcca6c6bSrsc writei(struct inode *ip, char *src, uint off, uint n) 4646fa5ffb5Skaashoek { 465bcca6c6bSrsc uint tot, m; 4667d4aef6cSrsc struct buf *bp; 4677d4aef6cSrsc 4686fa5ffb5Skaashoek if(ip->type == T_DEV){ 4691dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].write) 470939f9edeSkaashoek return -1; 471d844f0f9Srsc return devsw[ip->major].write(ip, src, n); 4727d4aef6cSrsc } 4737d4aef6cSrsc 4741ddfbbb1SFrans Kaashoek if(off > ip->size || off + n < off) 475bcca6c6bSrsc return -1; 4761ddfbbb1SFrans Kaashoek if(off + n > MAXFILE*BSIZE) 4772e590463SRobert Morris return -1; 478bcca6c6bSrsc 479bcca6c6bSrsc for(tot=0; tot<n; tot+=m, off+=m, src+=m){ 48013ae8808Srsc bp = bread(ip->dev, bmap(ip, off/BSIZE)); 481bcca6c6bSrsc m = min(n - tot, BSIZE - off%BSIZE); 482bcca6c6bSrsc memmove(bp->data + off%BSIZE, src, m); 4832e590463SRobert Morris log_write(bp); 48428d9ef04Skaashoek brelse(bp); 48528d9ef04Skaashoek } 486bcca6c6bSrsc 487bcca6c6bSrsc if(n > 0 && off > ip->size){ 48848b82470Srsc ip->size = off; 48928d9ef04Skaashoek iupdate(ip); 49028d9ef04Skaashoek } 491bcca6c6bSrsc return n; 4926fa5ffb5Skaashoek } 4936fa5ffb5Skaashoek 494eaea18cbSrsc //PAGEBREAK! 495bcca6c6bSrsc // Directories 496bcca6c6bSrsc 497eaea18cbSrsc int 498fbf91039Srsc namecmp(const char *s, const char *t) 499fbf91039Srsc { 500766ba5ccSrsc return strncmp(s, t, DIRSIZ); 501fbf91039Srsc } 502fbf91039Srsc 503bcca6c6bSrsc // Look for a directory entry in a directory. 504eaea18cbSrsc // If found, set *poff to byte offset of entry. 50507090dd7Srsc struct inode* 506fbf91039Srsc dirlookup(struct inode *dp, char *name, uint *poff) 507bcca6c6bSrsc { 508f32f3638Srsc uint off, inum; 509327cc21fSRobert Morris struct dirent de; 510bcca6c6bSrsc 511bcca6c6bSrsc if(dp->type != T_DIR) 51220365348Srtm panic("dirlookup not DIR"); 513bcca6c6bSrsc 514327cc21fSRobert Morris for(off = 0; off < dp->size; off += sizeof(de)){ 515327cc21fSRobert Morris if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 516327cc21fSRobert Morris panic("dirlink read"); 517327cc21fSRobert Morris if(de.inum == 0) 518bcca6c6bSrsc continue; 519327cc21fSRobert Morris if(namecmp(name, de.name) == 0){ 520bcca6c6bSrsc // entry matches path element 521e2a620daSrsc if(poff) 522327cc21fSRobert Morris *poff = off; 523327cc21fSRobert Morris inum = de.inum; 524f32f3638Srsc return iget(dp->dev, inum); 525f32f3638Srsc } 526f32f3638Srsc } 527327cc21fSRobert Morris 528bcca6c6bSrsc return 0; 529bcca6c6bSrsc } 530bcca6c6bSrsc 53113ae8808Srsc // Write a new directory entry (name, inum) into the directory dp. 532eaea18cbSrsc int 53313ae8808Srsc dirlink(struct inode *dp, char *name, uint inum) 534bcca6c6bSrsc { 535e2a620daSrsc int off; 536bcca6c6bSrsc struct dirent de; 53707090dd7Srsc struct inode *ip; 538f32f3638Srsc 539eaea18cbSrsc // Check that name is not present. 54007090dd7Srsc if((ip = dirlookup(dp, name, 0)) != 0){ 54107090dd7Srsc iput(ip); 542f32f3638Srsc return -1; 543f32f3638Srsc } 544bcca6c6bSrsc 545bcca6c6bSrsc // Look for an empty dirent. 546bcca6c6bSrsc for(off = 0; off < dp->size; off += sizeof(de)){ 547bcca6c6bSrsc if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 5487895178dSrsc panic("dirlink read"); 549bcca6c6bSrsc if(de.inum == 0) 550bcca6c6bSrsc break; 551bcca6c6bSrsc } 552bcca6c6bSrsc 553766ba5ccSrsc strncpy(de.name, name, DIRSIZ); 55413ae8808Srsc de.inum = inum; 555bcca6c6bSrsc if(writei(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 5567895178dSrsc panic("dirlink"); 557f32f3638Srsc 558f32f3638Srsc return 0; 559bcca6c6bSrsc } 560bcca6c6bSrsc 5618d2e9a48Srsc //PAGEBREAK! 562bcca6c6bSrsc // Paths 563bcca6c6bSrsc 564eaea18cbSrsc // Copy the next path element from path into name. 565eaea18cbSrsc // Return a pointer to the element following the copied one. 566eaea18cbSrsc // The returned path has no leading slashes, 567eaea18cbSrsc // so the caller can check *path=='\0' to see if the name is the last one. 568eaea18cbSrsc // If no name to remove, return 0. 569ab5c2dbbSrsc // 570ab5c2dbbSrsc // Examples: 571eaea18cbSrsc // skipelem("a/bb/c", name) = "bb/c", setting name = "a" 5727895178dSrsc // skipelem("///a//bb", name) = "bb", setting name = "a" 57313ae8808Srsc // skipelem("a", name) = "", setting name = "a" 574eaea18cbSrsc // skipelem("", name) = skipelem("////", name) = 0 575ab5c2dbbSrsc // 576ab5c2dbbSrsc static char* 577fbf91039Srsc skipelem(char *path, char *name) 578ab5c2dbbSrsc { 579fbf91039Srsc char *s; 580fbf91039Srsc int len; 581fbf91039Srsc 582ab5c2dbbSrsc while(*path == '/') 583ab5c2dbbSrsc path++; 584ab5c2dbbSrsc if(*path == 0) 585ab5c2dbbSrsc return 0; 586fbf91039Srsc s = path; 587ab5c2dbbSrsc while(*path != '/' && *path != 0) 588ab5c2dbbSrsc path++; 589fbf91039Srsc len = path - s; 590fbf91039Srsc if(len >= DIRSIZ) 591fbf91039Srsc memmove(name, s, DIRSIZ); 592fbf91039Srsc else { 593fbf91039Srsc memmove(name, s, len); 594fbf91039Srsc name[len] = 0; 595fbf91039Srsc } 596ab5c2dbbSrsc while(*path == '/') 597ab5c2dbbSrsc path++; 598ab5c2dbbSrsc return path; 599ab5c2dbbSrsc } 600ab5c2dbbSrsc 601eaea18cbSrsc // Look up and return the inode for a path name. 602bf2932a6Srsc // If parent != 0, return the inode for the parent and copy the final 603bf2932a6Srsc // path element into name, which must have room for DIRSIZ bytes. 6042c565472SRobert Morris // Must be called inside a transaction since it calls iput(). 60507090dd7Srsc static struct inode* 606f9a06440SRuss Cox namex(char *path, int nameiparent, char *name) 6079d3fb671Srtm { 60807090dd7Srsc struct inode *ip, *next; 6099d3fb671Srtm 610ab5c2dbbSrsc if(*path == '/') 6112ce40d70Srtm ip = iget(ROOTDEV, ROOTINO); 612f32f3638Srsc else 61348755214SRuss Cox ip = idup(proc->cwd); 6149d3fb671Srtm 615fbf91039Srsc while((path = skipelem(path, name)) != 0){ 61607090dd7Srsc ilock(ip); 61707090dd7Srsc if(ip->type != T_DIR){ 61807090dd7Srsc iunlockput(ip); 619eaea18cbSrsc return 0; 620eaea18cbSrsc } 621f9a06440SRuss Cox if(nameiparent && *path == '\0'){ 622e2a620daSrsc // Stop one level early. 62307090dd7Srsc iunlock(ip); 62407090dd7Srsc return ip; 625ab5c2dbbSrsc } 6267895178dSrsc if((next = dirlookup(ip, name, 0)) == 0){ 62707090dd7Srsc iunlockput(ip); 628eaea18cbSrsc return 0; 629eaea18cbSrsc } 63007090dd7Srsc iunlockput(ip); 63107090dd7Srsc ip = next; 632ab5c2dbbSrsc } 633f9a06440SRuss Cox if(nameiparent){ 63407090dd7Srsc iput(ip); 6355051da6dSrtm return 0; 63620365348Srtm } 63707090dd7Srsc return ip; 6380633b971Skaashoek } 6399d3fb671Srtm 6407895178dSrsc struct inode* 6417895178dSrsc namei(char *path) 6427895178dSrsc { 6437895178dSrsc char name[DIRSIZ]; 64413ae8808Srsc return namex(path, 0, name); 6457895178dSrsc } 646bf2932a6Srsc 6477895178dSrsc struct inode* 6487895178dSrsc nameiparent(char *path, char *name) 6497895178dSrsc { 65013ae8808Srsc return namex(path, 1, name); 6517895178dSrsc } 652