1a505fd66Srsc // File system implementation. Four layers: 2bcca6c6bSrsc // + Blocks: allocator for raw disk blocks. 3bcca6c6bSrsc // + Files: inode allocator, reading, writing, metadata. 4bcca6c6bSrsc // + Directories: inode with special contents (list of other inodes!) 5bcca6c6bSrsc // + Names: paths like /usr/rtm/xv6/fs.c for convenient naming. 6bcca6c6bSrsc // 74d39b633Srsc // Disk layout is: superblock, inodes, block in-use bitmap, data blocks. 8eaea18cbSrsc // 9eaea18cbSrsc // This file contains the low-level file system manipulation 10eaea18cbSrsc // routines. The (higher-level) system call implementations 11eaea18cbSrsc // are in sysfile.c. 12bcca6c6bSrsc 1311a9947fSrtm #include "types.h" 14558ab49fSrsc #include "defs.h" 1511a9947fSrtm #include "param.h" 16558ab49fSrsc #include "stat.h" 1711a9947fSrtm #include "mmu.h" 1811a9947fSrtm #include "proc.h" 1911a9947fSrtm #include "spinlock.h" 2011a9947fSrtm #include "buf.h" 2111a9947fSrtm #include "fs.h" 220aef8914SRuss Cox #include "file.h" 2311a9947fSrtm 24bcca6c6bSrsc #define min(a, b) ((a) < (b) ? (a) : (b)) 25fbf91039Srsc static void itrunc(struct inode*); 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); 46*5053dd6aSRobert Morris log_write(bp); 47a505fd66Srsc brelse(bp); 48a505fd66Srsc } 49a505fd66Srsc 50bcca6c6bSrsc // Blocks. 515be0039cSrtm 52*5053dd6aSRobert Morris // Allocate a zeroed disk block. 5324111398Skaashoek static uint 5424111398Skaashoek balloc(uint dev) 5524111398Skaashoek { 56a505fd66Srsc int b, bi, m; 5724111398Skaashoek struct buf *bp; 58a505fd66Srsc struct superblock sb; 5924111398Skaashoek 60a505fd66Srsc bp = 0; 61a505fd66Srsc readsb(dev, &sb); 62a505fd66Srsc for(b = 0; b < sb.size; b += BPB){ 63a505fd66Srsc bp = bread(dev, BBLOCK(b, sb.ninodes)); 6496b7da5fSNickolai Zeldovich for(bi = 0; bi < BPB && bi < (sb.size - b); bi++){ 65a505fd66Srsc m = 1 << (bi % 8); 66a505fd66Srsc if((bp->data[bi/8] & m) == 0){ // Is block free? 67a505fd66Srsc bp->data[bi/8] |= m; // Mark block in use on disk. 6813a96baeSFrans Kaashoek log_write(bp); 6924111398Skaashoek brelse(bp); 70*5053dd6aSRobert Morris bzero(dev, b + bi); 71a505fd66Srsc return b + bi; 7224111398Skaashoek } 73a505fd66Srsc } 7428d9ef04Skaashoek brelse(bp); 757d4aef6cSrsc } 767d4aef6cSrsc panic("balloc: out of blocks"); 777d4aef6cSrsc } 7824111398Skaashoek 79bb207a1dSrsc // Free a disk block. 8028d9ef04Skaashoek static void 8128d9ef04Skaashoek bfree(int dev, uint b) 8228d9ef04Skaashoek { 8328d9ef04Skaashoek struct buf *bp; 84a505fd66Srsc struct superblock sb; 85a505fd66Srsc int bi, m; 8628d9ef04Skaashoek 87a505fd66Srsc readsb(dev, &sb); 88a505fd66Srsc bp = bread(dev, BBLOCK(b, sb.ninodes)); 8928d9ef04Skaashoek bi = b % BPB; 90a505fd66Srsc m = 1 << (bi % 8); 91902b13f5Srtm if((bp->data[bi/8] & m) == 0) 92902b13f5Srtm panic("freeing free block"); 93a505fd66Srsc bp->data[bi/8] &= ~m; // Mark block free on disk. 9413a96baeSFrans Kaashoek log_write(bp); 9528d9ef04Skaashoek brelse(bp); 9628d9ef04Skaashoek } 9724111398Skaashoek 986c34f97cSrsc // Inodes. 996c34f97cSrsc // 1006c34f97cSrsc // An inode is a single, unnamed file in the file system. 1016c34f97cSrsc // The inode disk structure holds metadata (the type, device numbers, 1026c34f97cSrsc // and data size) along with a list of blocks where the associated 1036c34f97cSrsc // data can be found. 104bcca6c6bSrsc // 105bcca6c6bSrsc // The inodes are laid out sequentially on disk immediately after 106bcca6c6bSrsc // the superblock. The kernel keeps a cache of the in-use 107bcca6c6bSrsc // on-disk structures to provide a place for synchronizing access 108bcca6c6bSrsc // to inodes shared between multiple processes. 109bcca6c6bSrsc // 110902b13f5Srtm // ip->ref counts the number of pointer references to this cached 11148755214SRuss Cox // inode; references are typically kept in struct file and in proc->cwd. 112bcca6c6bSrsc // When ip->ref falls to zero, the inode is no longer cached. 113bcca6c6bSrsc // It is an error to use an inode without holding a reference to it. 114bcca6c6bSrsc // 115eaea18cbSrsc // Processes are only allowed to read and write inode 1166c34f97cSrsc // metadata and contents when holding the inode's lock, 1176c34f97cSrsc // represented by the I_BUSY flag in the in-memory copy. 118902b13f5Srtm // Because inode locks are held during disk accesses, 119902b13f5Srtm // they are implemented using a flag rather than with 120902b13f5Srtm // spin locks. Callers are responsible for locking 121eaea18cbSrsc // inodes before passing them to routines in this file; leaving 122eaea18cbSrsc // this responsibility with the caller makes it possible for them 123eaea18cbSrsc // to create arbitrarily-sized atomic operations. 124eaea18cbSrsc // 125eaea18cbSrsc // To give maximum control over locking to the callers, 126eaea18cbSrsc // the routines in this file that return inode pointers 127eaea18cbSrsc // return pointers to *unlocked* inodes. It is the callers' 128902b13f5Srtm // responsibility to lock them before using them. A non-zero 129902b13f5Srtm // ip->ref keeps these unlocked inodes in the cache. 130bcca6c6bSrsc 131bcca6c6bSrsc struct { 132bcca6c6bSrsc struct spinlock lock; 133bcca6c6bSrsc struct inode inode[NINODE]; 134bcca6c6bSrsc } icache; 135bcca6c6bSrsc 136bcca6c6bSrsc void 137bcca6c6bSrsc iinit(void) 138bcca6c6bSrsc { 13934295f46Srsc initlock(&icache.lock, "icache"); 140bcca6c6bSrsc } 141bcca6c6bSrsc 142f9a06440SRuss Cox static struct inode* iget(uint dev, uint inum); 143f9a06440SRuss Cox 144f9a06440SRuss Cox //PAGEBREAK! 145f9a06440SRuss Cox // Allocate a new inode with the given type on device dev. 146f9a06440SRuss Cox struct inode* 147f9a06440SRuss Cox ialloc(uint dev, short type) 148f9a06440SRuss Cox { 149f9a06440SRuss Cox int inum; 150f9a06440SRuss Cox struct buf *bp; 151f9a06440SRuss Cox struct dinode *dip; 152f9a06440SRuss Cox struct superblock sb; 153f9a06440SRuss Cox 154f9a06440SRuss Cox readsb(dev, &sb); 155f9a06440SRuss Cox for(inum = 1; inum < sb.ninodes; inum++){ // loop over inode blocks 156f9a06440SRuss Cox bp = bread(dev, IBLOCK(inum)); 157f9a06440SRuss Cox dip = (struct dinode*)bp->data + inum%IPB; 158f9a06440SRuss Cox if(dip->type == 0){ // a free inode 159f9a06440SRuss Cox memset(dip, 0, sizeof(*dip)); 160f9a06440SRuss Cox dip->type = type; 16113a96baeSFrans Kaashoek log_write(bp); // mark it allocated on the disk 162f9a06440SRuss Cox brelse(bp); 163f9a06440SRuss Cox return iget(dev, inum); 164f9a06440SRuss Cox } 165f9a06440SRuss Cox brelse(bp); 166f9a06440SRuss Cox } 167f9a06440SRuss Cox panic("ialloc: no inodes"); 168f9a06440SRuss Cox } 169f9a06440SRuss Cox 170f9a06440SRuss Cox // Copy inode, which has changed, from memory to disk. 171f9a06440SRuss Cox void 172f9a06440SRuss Cox iupdate(struct inode *ip) 173f9a06440SRuss Cox { 174f9a06440SRuss Cox struct buf *bp; 175f9a06440SRuss Cox struct dinode *dip; 176f9a06440SRuss Cox 177f9a06440SRuss Cox bp = bread(ip->dev, IBLOCK(ip->inum)); 178f9a06440SRuss Cox dip = (struct dinode*)bp->data + ip->inum%IPB; 179f9a06440SRuss Cox dip->type = ip->type; 180f9a06440SRuss Cox dip->major = ip->major; 181f9a06440SRuss Cox dip->minor = ip->minor; 182f9a06440SRuss Cox dip->nlink = ip->nlink; 183f9a06440SRuss Cox dip->size = ip->size; 184f9a06440SRuss Cox memmove(dip->addrs, ip->addrs, sizeof(ip->addrs)); 18513a96baeSFrans Kaashoek log_write(bp); 186f9a06440SRuss Cox brelse(bp); 187f9a06440SRuss Cox } 188f9a06440SRuss Cox 189f5527388Srsc // Find the inode with number inum on device dev 1907895178dSrsc // and return the in-memory copy. 19107090dd7Srsc static struct inode* 19211a9947fSrtm iget(uint dev, uint inum) 19311a9947fSrtm { 194bcca6c6bSrsc struct inode *ip, *empty; 19511a9947fSrtm 196bcca6c6bSrsc acquire(&icache.lock); 19711a9947fSrtm 198bcca6c6bSrsc // Try for cached inode. 199bcca6c6bSrsc empty = 0; 200bcca6c6bSrsc for(ip = &icache.inode[0]; ip < &icache.inode[NINODE]; ip++){ 2010d6bbd31Srsc if(ip->ref > 0 && ip->dev == dev && ip->inum == inum){ 2020d6bbd31Srsc ip->ref++; 203bcca6c6bSrsc release(&icache.lock); 20407090dd7Srsc return ip; 20511a9947fSrtm } 206bcca6c6bSrsc if(empty == 0 && ip->ref == 0) // Remember empty slot. 207bcca6c6bSrsc empty = ip; 20811a9947fSrtm } 20911a9947fSrtm 210bcca6c6bSrsc // Allocate fresh inode. 211bcca6c6bSrsc if(empty == 0) 21232eea766Srsc panic("iget: no inodes"); 21311a9947fSrtm 214bcca6c6bSrsc ip = empty; 215bcca6c6bSrsc ip->dev = dev; 216bcca6c6bSrsc ip->inum = inum; 217bcca6c6bSrsc ip->ref = 1; 218f32f3638Srsc ip->flags = 0; 219bcca6c6bSrsc release(&icache.lock); 22011a9947fSrtm 22107090dd7Srsc return ip; 222f32f3638Srsc } 223f32f3638Srsc 224eaea18cbSrsc // Increment reference count for ip. 225eaea18cbSrsc // Returns ip to enable ip = idup(ip1) idiom. 22607090dd7Srsc struct inode* 22707090dd7Srsc idup(struct inode *ip) 228f32f3638Srsc { 229eaea18cbSrsc acquire(&icache.lock); 230eaea18cbSrsc ip->ref++; 231eaea18cbSrsc release(&icache.lock); 23207090dd7Srsc return ip; 233f32f3638Srsc } 234f32f3638Srsc 235f32f3638Srsc // Lock the given inode. 23607090dd7Srsc void 23707090dd7Srsc ilock(struct inode *ip) 238f32f3638Srsc { 239f32f3638Srsc struct buf *bp; 240f32f3638Srsc struct dinode *dip; 241eaea18cbSrsc 24207090dd7Srsc if(ip == 0 || ip->ref < 1) 24307090dd7Srsc panic("ilock"); 244f32f3638Srsc 245f32f3638Srsc acquire(&icache.lock); 246f32f3638Srsc while(ip->flags & I_BUSY) 247f32f3638Srsc sleep(ip, &icache.lock); 248f32f3638Srsc ip->flags |= I_BUSY; 249f32f3638Srsc release(&icache.lock); 250f32f3638Srsc 251f32f3638Srsc if(!(ip->flags & I_VALID)){ 252f32f3638Srsc bp = bread(ip->dev, IBLOCK(ip->inum)); 2533341e30fSrsc dip = (struct dinode*)bp->data + ip->inum%IPB; 254bcca6c6bSrsc ip->type = dip->type; 255bcca6c6bSrsc ip->major = dip->major; 256bcca6c6bSrsc ip->minor = dip->minor; 257bcca6c6bSrsc ip->nlink = dip->nlink; 258bcca6c6bSrsc ip->size = dip->size; 259bcca6c6bSrsc memmove(ip->addrs, dip->addrs, sizeof(ip->addrs)); 26011a9947fSrtm brelse(bp); 261f32f3638Srsc ip->flags |= I_VALID; 262eaea18cbSrsc if(ip->type == 0) 263eaea18cbSrsc panic("ilock: no type"); 26411a9947fSrtm } 265bcca6c6bSrsc } 266bcca6c6bSrsc 267bcca6c6bSrsc // Unlock the given inode. 26807090dd7Srsc void 269bcca6c6bSrsc iunlock(struct inode *ip) 270bcca6c6bSrsc { 27107090dd7Srsc if(ip == 0 || !(ip->flags & I_BUSY) || ip->ref < 1) 272bcca6c6bSrsc panic("iunlock"); 273bcca6c6bSrsc 274bcca6c6bSrsc acquire(&icache.lock); 275ce72cadbSrsc ip->flags &= ~I_BUSY; 276bcca6c6bSrsc wakeup(ip); 277bcca6c6bSrsc release(&icache.lock); 278bcca6c6bSrsc } 279bcca6c6bSrsc 280f32f3638Srsc // Caller holds reference to unlocked ip. Drop reference. 281bcca6c6bSrsc void 28207090dd7Srsc iput(struct inode *ip) 283bcca6c6bSrsc { 284f32f3638Srsc acquire(&icache.lock); 285f32f3638Srsc if(ip->ref == 1 && (ip->flags & I_VALID) && ip->nlink == 0){ 286f32f3638Srsc // inode is no longer used: truncate and free inode. 287f32f3638Srsc if(ip->flags & I_BUSY) 288eaea18cbSrsc panic("iput busy"); 289f32f3638Srsc ip->flags |= I_BUSY; 290f32f3638Srsc release(&icache.lock); 291f32f3638Srsc itrunc(ip); 292f32f3638Srsc ip->type = 0; 293f32f3638Srsc iupdate(ip); 294f32f3638Srsc acquire(&icache.lock); 295ce72cadbSrsc ip->flags = 0; 2968970df0cSrsc wakeup(ip); 297f32f3638Srsc } 298f32f3638Srsc ip->ref--; 299f32f3638Srsc release(&icache.lock); 300bcca6c6bSrsc } 301bcca6c6bSrsc 3027895178dSrsc // Common idiom: unlock, then put. 30307090dd7Srsc void 30407090dd7Srsc iunlockput(struct inode *ip) 30507090dd7Srsc { 30607090dd7Srsc iunlock(ip); 30707090dd7Srsc iput(ip); 30807090dd7Srsc } 30907090dd7Srsc 3108d2e9a48Srsc //PAGEBREAK! 311bcca6c6bSrsc // Inode contents 312bcca6c6bSrsc // 313bcca6c6bSrsc // The contents (data) associated with each inode is stored 314bcca6c6bSrsc // in a sequence of blocks on the disk. The first NDIRECT blocks 3157895178dSrsc // are listed in ip->addrs[]. The next NINDIRECT blocks are 316745e73cdSAustin Clements // listed in the block ip->addrs[NDIRECT]. 3179d3fb671Srtm 318bb207a1dSrsc // Return the disk block address of the nth block in inode ip. 31913ae8808Srsc // If there is no such block, bmap allocates one. 320eaea18cbSrsc static uint 32113ae8808Srsc bmap(struct inode *ip, uint bn) 32222bac2cbSkaashoek { 323bcca6c6bSrsc uint addr, *a; 324bcca6c6bSrsc struct buf *bp; 32522bac2cbSkaashoek 326ea2909b6Skaashoek if(bn < NDIRECT){ 32713ae8808Srsc if((addr = ip->addrs[bn]) == 0) 328bcca6c6bSrsc ip->addrs[bn] = addr = balloc(ip->dev); 329bcca6c6bSrsc return addr; 330bcca6c6bSrsc } 331bcca6c6bSrsc bn -= NDIRECT; 332bcca6c6bSrsc 333bcca6c6bSrsc if(bn < NINDIRECT){ 334bcca6c6bSrsc // Load indirect block, allocating if necessary. 33513ae8808Srsc if((addr = ip->addrs[NDIRECT]) == 0) 336ba6cd8a6Srsc ip->addrs[NDIRECT] = addr = balloc(ip->dev); 337bcca6c6bSrsc bp = bread(ip->dev, addr); 338bcca6c6bSrsc a = (uint*)bp->data; 339bcca6c6bSrsc if((addr = a[bn]) == 0){ 340bcca6c6bSrsc a[bn] = addr = balloc(ip->dev); 34113a96baeSFrans Kaashoek log_write(bp); 342bcca6c6bSrsc } 343bcca6c6bSrsc brelse(bp); 344bcca6c6bSrsc return addr; 34522bac2cbSkaashoek } 34622bac2cbSkaashoek 347bcca6c6bSrsc panic("bmap: out of range"); 348bcca6c6bSrsc } 349bcca6c6bSrsc 350bcca6c6bSrsc // Truncate inode (discard contents). 3518eb20827Srtm // Only called after the last dirent referring 3528eb20827Srtm // to this inode has been erased on disk. 353fbf91039Srsc static void 3542aa4c3bcSrtm itrunc(struct inode *ip) 35522bac2cbSkaashoek { 356ea2909b6Skaashoek int i, j; 357bcca6c6bSrsc struct buf *bp; 3587d4aef6cSrsc uint *a; 35922bac2cbSkaashoek 360bcca6c6bSrsc for(i = 0; i < NDIRECT; i++){ 361bcca6c6bSrsc if(ip->addrs[i]){ 36222bac2cbSkaashoek bfree(ip->dev, ip->addrs[i]); 36322bac2cbSkaashoek ip->addrs[i] = 0; 36422bac2cbSkaashoek } 36522bac2cbSkaashoek } 366bcca6c6bSrsc 367ba6cd8a6Srsc if(ip->addrs[NDIRECT]){ 368ba6cd8a6Srsc bp = bread(ip->dev, ip->addrs[NDIRECT]); 369bcca6c6bSrsc a = (uint*)bp->data; 370bcca6c6bSrsc for(j = 0; j < NINDIRECT; j++){ 371bcca6c6bSrsc if(a[j]) 372bcca6c6bSrsc bfree(ip->dev, a[j]); 373bcca6c6bSrsc } 374bcca6c6bSrsc brelse(bp); 375ba6cd8a6Srsc bfree(ip->dev, ip->addrs[NDIRECT]); 376ba6cd8a6Srsc ip->addrs[NDIRECT] = 0; 377bcca6c6bSrsc } 378bcca6c6bSrsc 37922bac2cbSkaashoek ip->size = 0; 38022bac2cbSkaashoek iupdate(ip); 38122bac2cbSkaashoek } 38222bac2cbSkaashoek 383bb207a1dSrsc // Copy stat information from inode. 384e958c538Skaashoek void 3851f544842Skaashoek stati(struct inode *ip, struct stat *st) 3861f544842Skaashoek { 3871dca3afbSrsc st->dev = ip->dev; 3881dca3afbSrsc st->ino = ip->inum; 3891dca3afbSrsc st->type = ip->type; 3901dca3afbSrsc st->nlink = ip->nlink; 3911dca3afbSrsc st->size = ip->size; 3921f544842Skaashoek } 3931f544842Skaashoek 394eaea18cbSrsc //PAGEBREAK! 395bb207a1dSrsc // Read data from inode. 396c59361f1Srtm int 39717a85657Srtm readi(struct inode *ip, char *dst, uint off, uint n) 398c59361f1Srtm { 399bcca6c6bSrsc uint tot, m; 400c59361f1Srtm struct buf *bp; 401c59361f1Srtm 402939f9edeSkaashoek if(ip->type == T_DEV){ 4031dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].read) 404939f9edeSkaashoek return -1; 405d844f0f9Srsc return devsw[ip->major].read(ip, dst, n); 406939f9edeSkaashoek } 407939f9edeSkaashoek 4087895178dSrsc if(off > ip->size || off + n < off) 409bcca6c6bSrsc return -1; 410bcca6c6bSrsc if(off + n > ip->size) 411bcca6c6bSrsc n = ip->size - off; 412bcca6c6bSrsc 413bcca6c6bSrsc for(tot=0; tot<n; tot+=m, off+=m, dst+=m){ 41413ae8808Srsc bp = bread(ip->dev, bmap(ip, off/BSIZE)); 415bcca6c6bSrsc m = min(n - tot, BSIZE - off%BSIZE); 416bcca6c6bSrsc memmove(dst, bp->data + off%BSIZE, m); 417c59361f1Srtm brelse(bp); 418c59361f1Srtm } 419bcca6c6bSrsc return n; 420ea2909b6Skaashoek } 421ea2909b6Skaashoek 422eaea18cbSrsc // PAGEBREAK! 423bb207a1dSrsc // Write data to inode. 424ea2909b6Skaashoek int 425bcca6c6bSrsc writei(struct inode *ip, char *src, uint off, uint n) 4266fa5ffb5Skaashoek { 427bcca6c6bSrsc uint tot, m; 4287d4aef6cSrsc struct buf *bp; 4297d4aef6cSrsc 4306fa5ffb5Skaashoek if(ip->type == T_DEV){ 4311dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].write) 432939f9edeSkaashoek return -1; 433d844f0f9Srsc return devsw[ip->major].write(ip, src, n); 4347d4aef6cSrsc } 4357d4aef6cSrsc 43613ae8808Srsc if(off > ip->size || off + n < off) 437bcca6c6bSrsc return -1; 438bcca6c6bSrsc if(off + n > MAXFILE*BSIZE) 4392e590463SRobert Morris return -1; 440bcca6c6bSrsc 441bcca6c6bSrsc for(tot=0; tot<n; tot+=m, off+=m, src+=m){ 44213ae8808Srsc bp = bread(ip->dev, bmap(ip, off/BSIZE)); 443bcca6c6bSrsc m = min(n - tot, BSIZE - off%BSIZE); 444bcca6c6bSrsc memmove(bp->data + off%BSIZE, src, m); 4452e590463SRobert Morris log_write(bp); 44628d9ef04Skaashoek brelse(bp); 44728d9ef04Skaashoek } 448bcca6c6bSrsc 449bcca6c6bSrsc if(n > 0 && off > ip->size){ 45048b82470Srsc ip->size = off; 45128d9ef04Skaashoek iupdate(ip); 45228d9ef04Skaashoek } 453bcca6c6bSrsc return n; 4546fa5ffb5Skaashoek } 4556fa5ffb5Skaashoek 456eaea18cbSrsc //PAGEBREAK! 457bcca6c6bSrsc // Directories 458bcca6c6bSrsc 459eaea18cbSrsc int 460fbf91039Srsc namecmp(const char *s, const char *t) 461fbf91039Srsc { 462766ba5ccSrsc return strncmp(s, t, DIRSIZ); 463fbf91039Srsc } 464fbf91039Srsc 465bcca6c6bSrsc // Look for a directory entry in a directory. 466eaea18cbSrsc // If found, set *poff to byte offset of entry. 46720365348Srtm // Caller must have already locked dp. 46807090dd7Srsc struct inode* 469fbf91039Srsc dirlookup(struct inode *dp, char *name, uint *poff) 470bcca6c6bSrsc { 471f32f3638Srsc uint off, inum; 472bcca6c6bSrsc struct buf *bp; 473bcca6c6bSrsc struct dirent *de; 474bcca6c6bSrsc 475bcca6c6bSrsc if(dp->type != T_DIR) 47620365348Srtm panic("dirlookup not DIR"); 477bcca6c6bSrsc 478bcca6c6bSrsc for(off = 0; off < dp->size; off += BSIZE){ 47913ae8808Srsc bp = bread(dp->dev, bmap(dp, off / BSIZE)); 480bcca6c6bSrsc for(de = (struct dirent*)bp->data; 481bcca6c6bSrsc de < (struct dirent*)(bp->data + BSIZE); 482bcca6c6bSrsc de++){ 483bcca6c6bSrsc if(de->inum == 0) 484bcca6c6bSrsc continue; 485fbf91039Srsc if(namecmp(name, de->name) == 0){ 486bcca6c6bSrsc // entry matches path element 487e2a620daSrsc if(poff) 488bcca6c6bSrsc *poff = off + (uchar*)de - bp->data; 489f32f3638Srsc inum = de->inum; 490bcca6c6bSrsc brelse(bp); 491f32f3638Srsc return iget(dp->dev, inum); 492f32f3638Srsc } 493f32f3638Srsc } 494f32f3638Srsc brelse(bp); 495f32f3638Srsc } 496bcca6c6bSrsc return 0; 497bcca6c6bSrsc } 498bcca6c6bSrsc 49913ae8808Srsc // Write a new directory entry (name, inum) into the directory dp. 500eaea18cbSrsc int 50113ae8808Srsc dirlink(struct inode *dp, char *name, uint inum) 502bcca6c6bSrsc { 503e2a620daSrsc int off; 504bcca6c6bSrsc struct dirent de; 50507090dd7Srsc struct inode *ip; 506f32f3638Srsc 507eaea18cbSrsc // Check that name is not present. 50807090dd7Srsc if((ip = dirlookup(dp, name, 0)) != 0){ 50907090dd7Srsc iput(ip); 510f32f3638Srsc return -1; 511f32f3638Srsc } 512bcca6c6bSrsc 513bcca6c6bSrsc // Look for an empty dirent. 514bcca6c6bSrsc for(off = 0; off < dp->size; off += sizeof(de)){ 515bcca6c6bSrsc if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 5167895178dSrsc panic("dirlink read"); 517bcca6c6bSrsc if(de.inum == 0) 518bcca6c6bSrsc break; 519bcca6c6bSrsc } 520bcca6c6bSrsc 521766ba5ccSrsc strncpy(de.name, name, DIRSIZ); 52213ae8808Srsc de.inum = inum; 523bcca6c6bSrsc if(writei(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 5247895178dSrsc panic("dirlink"); 525f32f3638Srsc 526f32f3638Srsc return 0; 527bcca6c6bSrsc } 528bcca6c6bSrsc 5298d2e9a48Srsc //PAGEBREAK! 530bcca6c6bSrsc // Paths 531bcca6c6bSrsc 532eaea18cbSrsc // Copy the next path element from path into name. 533eaea18cbSrsc // Return a pointer to the element following the copied one. 534eaea18cbSrsc // The returned path has no leading slashes, 535eaea18cbSrsc // so the caller can check *path=='\0' to see if the name is the last one. 536eaea18cbSrsc // If no name to remove, return 0. 537ab5c2dbbSrsc // 538ab5c2dbbSrsc // Examples: 539eaea18cbSrsc // skipelem("a/bb/c", name) = "bb/c", setting name = "a" 5407895178dSrsc // skipelem("///a//bb", name) = "bb", setting name = "a" 54113ae8808Srsc // skipelem("a", name) = "", setting name = "a" 542eaea18cbSrsc // skipelem("", name) = skipelem("////", name) = 0 543ab5c2dbbSrsc // 544ab5c2dbbSrsc static char* 545fbf91039Srsc skipelem(char *path, char *name) 546ab5c2dbbSrsc { 547fbf91039Srsc char *s; 548fbf91039Srsc int len; 549fbf91039Srsc 550ab5c2dbbSrsc while(*path == '/') 551ab5c2dbbSrsc path++; 552ab5c2dbbSrsc if(*path == 0) 553ab5c2dbbSrsc return 0; 554fbf91039Srsc s = path; 555ab5c2dbbSrsc while(*path != '/' && *path != 0) 556ab5c2dbbSrsc path++; 557fbf91039Srsc len = path - s; 558fbf91039Srsc if(len >= DIRSIZ) 559fbf91039Srsc memmove(name, s, DIRSIZ); 560fbf91039Srsc else { 561fbf91039Srsc memmove(name, s, len); 562fbf91039Srsc name[len] = 0; 563fbf91039Srsc } 564ab5c2dbbSrsc while(*path == '/') 565ab5c2dbbSrsc path++; 566ab5c2dbbSrsc return path; 567ab5c2dbbSrsc } 568ab5c2dbbSrsc 569eaea18cbSrsc // Look up and return the inode for a path name. 570bf2932a6Srsc // If parent != 0, return the inode for the parent and copy the final 571bf2932a6Srsc // path element into name, which must have room for DIRSIZ bytes. 57207090dd7Srsc static struct inode* 573f9a06440SRuss Cox namex(char *path, int nameiparent, char *name) 5749d3fb671Srtm { 57507090dd7Srsc struct inode *ip, *next; 5769d3fb671Srtm 577ab5c2dbbSrsc if(*path == '/') 5782ce40d70Srtm ip = iget(ROOTDEV, ROOTINO); 579f32f3638Srsc else 58048755214SRuss Cox ip = idup(proc->cwd); 5819d3fb671Srtm 582fbf91039Srsc while((path = skipelem(path, name)) != 0){ 58307090dd7Srsc ilock(ip); 58407090dd7Srsc if(ip->type != T_DIR){ 58507090dd7Srsc iunlockput(ip); 586eaea18cbSrsc return 0; 587eaea18cbSrsc } 588f9a06440SRuss Cox if(nameiparent && *path == '\0'){ 589e2a620daSrsc // Stop one level early. 59007090dd7Srsc iunlock(ip); 59107090dd7Srsc return ip; 592ab5c2dbbSrsc } 5937895178dSrsc if((next = dirlookup(ip, name, 0)) == 0){ 59407090dd7Srsc iunlockput(ip); 595eaea18cbSrsc return 0; 596eaea18cbSrsc } 59707090dd7Srsc iunlockput(ip); 59807090dd7Srsc ip = next; 599ab5c2dbbSrsc } 600f9a06440SRuss Cox if(nameiparent){ 60107090dd7Srsc iput(ip); 6025051da6dSrtm return 0; 60320365348Srtm } 60407090dd7Srsc return ip; 6050633b971Skaashoek } 6069d3fb671Srtm 6077895178dSrsc struct inode* 6087895178dSrsc namei(char *path) 6097895178dSrsc { 6107895178dSrsc char name[DIRSIZ]; 61113ae8808Srsc return namex(path, 0, name); 6127895178dSrsc } 613bf2932a6Srsc 6147895178dSrsc struct inode* 6157895178dSrsc nameiparent(char *path, char *name) 6167895178dSrsc { 61713ae8808Srsc return namex(path, 1, name); 6187895178dSrsc } 619