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" 2211a9947fSrtm #include "fsvar.h" 236fa5ffb5Skaashoek #include "dev.h" 2411a9947fSrtm 25bcca6c6bSrsc #define min(a, b) ((a) < (b) ? (a) : (b)) 26fbf91039Srsc static void itrunc(struct inode*); 2711a9947fSrtm 28a505fd66Srsc // Read the super block. 29a505fd66Srsc static void 30a505fd66Srsc readsb(int dev, struct superblock *sb) 31a505fd66Srsc { 32a505fd66Srsc struct buf *bp; 33a505fd66Srsc 34a505fd66Srsc bp = bread(dev, 1); 35a505fd66Srsc memmove(sb, bp->data, sizeof(*sb)); 36a505fd66Srsc brelse(bp); 37a505fd66Srsc } 38a505fd66Srsc 39a505fd66Srsc // Zero a block. 40a505fd66Srsc static void 41a505fd66Srsc bzero(int dev, int bno) 42a505fd66Srsc { 43a505fd66Srsc struct buf *bp; 44a505fd66Srsc 45a505fd66Srsc bp = bread(dev, bno); 46a505fd66Srsc memset(bp->data, 0, BSIZE); 47a505fd66Srsc bwrite(bp); 48a505fd66Srsc brelse(bp); 49a505fd66Srsc } 50a505fd66Srsc 51bcca6c6bSrsc // Blocks. 525be0039cSrtm 53f5527388Srsc // Allocate a disk block. 5424111398Skaashoek static uint 5524111398Skaashoek balloc(uint dev) 5624111398Skaashoek { 57a505fd66Srsc int b, bi, m; 5824111398Skaashoek struct buf *bp; 59a505fd66Srsc struct superblock sb; 6024111398Skaashoek 61a505fd66Srsc bp = 0; 62a505fd66Srsc readsb(dev, &sb); 63a505fd66Srsc for(b = 0; b < sb.size; b += BPB){ 64a505fd66Srsc bp = bread(dev, BBLOCK(b, sb.ninodes)); 65a505fd66Srsc for(bi = 0; bi < BPB; bi++){ 66a505fd66Srsc m = 1 << (bi % 8); 67a505fd66Srsc if((bp->data[bi/8] & m) == 0){ // Is block free? 68a505fd66Srsc bp->data[bi/8] |= m; // Mark block in use on disk. 69a505fd66Srsc bwrite(bp); 7024111398Skaashoek brelse(bp); 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 bzero(dev, b); 8828d9ef04Skaashoek 89a505fd66Srsc readsb(dev, &sb); 90a505fd66Srsc bp = bread(dev, BBLOCK(b, sb.ninodes)); 9128d9ef04Skaashoek bi = b % BPB; 92a505fd66Srsc m = 1 << (bi % 8); 93902b13f5Srtm if((bp->data[bi/8] & m) == 0) 94902b13f5Srtm panic("freeing free block"); 95a505fd66Srsc bp->data[bi/8] &= ~m; // Mark block free on disk. 96a505fd66Srsc bwrite(bp); 9728d9ef04Skaashoek brelse(bp); 9828d9ef04Skaashoek } 9924111398Skaashoek 1006c34f97cSrsc // Inodes. 1016c34f97cSrsc // 1026c34f97cSrsc // An inode is a single, unnamed file in the file system. 1036c34f97cSrsc // The inode disk structure holds metadata (the type, device numbers, 1046c34f97cSrsc // and data size) along with a list of blocks where the associated 1056c34f97cSrsc // data can be found. 106bcca6c6bSrsc // 107bcca6c6bSrsc // The inodes are laid out sequentially on disk immediately after 108bcca6c6bSrsc // the superblock. The kernel keeps a cache of the in-use 109bcca6c6bSrsc // on-disk structures to provide a place for synchronizing access 110bcca6c6bSrsc // to inodes shared between multiple processes. 111bcca6c6bSrsc // 112902b13f5Srtm // ip->ref counts the number of pointer references to this cached 113bcca6c6bSrsc // inode; references are typically kept in struct file and in cp->cwd. 114bcca6c6bSrsc // When ip->ref falls to zero, the inode is no longer cached. 115bcca6c6bSrsc // It is an error to use an inode without holding a reference to it. 116bcca6c6bSrsc // 117eaea18cbSrsc // Processes are only allowed to read and write inode 1186c34f97cSrsc // metadata and contents when holding the inode's lock, 1196c34f97cSrsc // represented by the I_BUSY flag in the in-memory copy. 120902b13f5Srtm // Because inode locks are held during disk accesses, 121902b13f5Srtm // they are implemented using a flag rather than with 122902b13f5Srtm // spin locks. Callers are responsible for locking 123eaea18cbSrsc // inodes before passing them to routines in this file; leaving 124eaea18cbSrsc // this responsibility with the caller makes it possible for them 125eaea18cbSrsc // to create arbitrarily-sized atomic operations. 126eaea18cbSrsc // 127eaea18cbSrsc // To give maximum control over locking to the callers, 128eaea18cbSrsc // the routines in this file that return inode pointers 129eaea18cbSrsc // return pointers to *unlocked* inodes. It is the callers' 130902b13f5Srtm // responsibility to lock them before using them. A non-zero 131902b13f5Srtm // ip->ref keeps these unlocked inodes in the cache. 132bcca6c6bSrsc 133bcca6c6bSrsc struct { 134bcca6c6bSrsc struct spinlock lock; 135bcca6c6bSrsc struct inode inode[NINODE]; 136bcca6c6bSrsc } icache; 137bcca6c6bSrsc 138bcca6c6bSrsc void 139bcca6c6bSrsc iinit(void) 140bcca6c6bSrsc { 141bcca6c6bSrsc initlock(&icache.lock, "icache.lock"); 142bcca6c6bSrsc } 143bcca6c6bSrsc 144f5527388Srsc // Find the inode with number inum on device dev 1457895178dSrsc // and return the in-memory copy. 14607090dd7Srsc static struct inode* 14711a9947fSrtm iget(uint dev, uint inum) 14811a9947fSrtm { 149bcca6c6bSrsc struct inode *ip, *empty; 15011a9947fSrtm 151bcca6c6bSrsc acquire(&icache.lock); 15211a9947fSrtm 153bcca6c6bSrsc // Try for cached inode. 154bcca6c6bSrsc empty = 0; 155bcca6c6bSrsc for(ip = &icache.inode[0]; ip < &icache.inode[NINODE]; ip++){ 1560d6bbd31Srsc if(ip->ref > 0 && ip->dev == dev && ip->inum == inum){ 1570d6bbd31Srsc ip->ref++; 158bcca6c6bSrsc release(&icache.lock); 15907090dd7Srsc return ip; 16011a9947fSrtm } 161bcca6c6bSrsc if(empty == 0 && ip->ref == 0) // Remember empty slot. 162bcca6c6bSrsc empty = ip; 16311a9947fSrtm } 16411a9947fSrtm 165bcca6c6bSrsc // Allocate fresh inode. 166bcca6c6bSrsc if(empty == 0) 16732eea766Srsc panic("iget: no inodes"); 16811a9947fSrtm 169bcca6c6bSrsc ip = empty; 170bcca6c6bSrsc ip->dev = dev; 171bcca6c6bSrsc ip->inum = inum; 172bcca6c6bSrsc ip->ref = 1; 173f32f3638Srsc ip->flags = 0; 174bcca6c6bSrsc release(&icache.lock); 17511a9947fSrtm 17607090dd7Srsc return ip; 177f32f3638Srsc } 178f32f3638Srsc 179eaea18cbSrsc // Increment reference count for ip. 180eaea18cbSrsc // Returns ip to enable ip = idup(ip1) idiom. 18107090dd7Srsc struct inode* 18207090dd7Srsc idup(struct inode *ip) 183f32f3638Srsc { 184eaea18cbSrsc acquire(&icache.lock); 185eaea18cbSrsc ip->ref++; 186eaea18cbSrsc release(&icache.lock); 18707090dd7Srsc return ip; 188f32f3638Srsc } 189f32f3638Srsc 190f32f3638Srsc // Lock the given inode. 19107090dd7Srsc void 19207090dd7Srsc ilock(struct inode *ip) 193f32f3638Srsc { 194f32f3638Srsc struct buf *bp; 195f32f3638Srsc struct dinode *dip; 196eaea18cbSrsc 19707090dd7Srsc if(ip == 0 || ip->ref < 1) 19807090dd7Srsc panic("ilock"); 199f32f3638Srsc 200f32f3638Srsc acquire(&icache.lock); 201f32f3638Srsc while(ip->flags & I_BUSY) 202f32f3638Srsc sleep(ip, &icache.lock); 203f32f3638Srsc ip->flags |= I_BUSY; 204f32f3638Srsc release(&icache.lock); 205f32f3638Srsc 206f32f3638Srsc if(!(ip->flags & I_VALID)){ 207f32f3638Srsc bp = bread(ip->dev, IBLOCK(ip->inum)); 2083341e30fSrsc dip = (struct dinode*)bp->data + ip->inum%IPB; 209bcca6c6bSrsc ip->type = dip->type; 210bcca6c6bSrsc ip->major = dip->major; 211bcca6c6bSrsc ip->minor = dip->minor; 212bcca6c6bSrsc ip->nlink = dip->nlink; 213bcca6c6bSrsc ip->size = dip->size; 214bcca6c6bSrsc memmove(ip->addrs, dip->addrs, sizeof(ip->addrs)); 21511a9947fSrtm brelse(bp); 216f32f3638Srsc ip->flags |= I_VALID; 217eaea18cbSrsc if(ip->type == 0) 218eaea18cbSrsc panic("ilock: no type"); 21911a9947fSrtm } 220bcca6c6bSrsc } 221bcca6c6bSrsc 222bcca6c6bSrsc // Unlock the given inode. 22307090dd7Srsc void 224bcca6c6bSrsc iunlock(struct inode *ip) 225bcca6c6bSrsc { 22607090dd7Srsc if(ip == 0 || !(ip->flags & I_BUSY) || ip->ref < 1) 227bcca6c6bSrsc panic("iunlock"); 228bcca6c6bSrsc 229bcca6c6bSrsc acquire(&icache.lock); 230f32f3638Srsc ip->flags &= ~I_BUSY; 231bcca6c6bSrsc wakeup(ip); 232bcca6c6bSrsc release(&icache.lock); 233bcca6c6bSrsc } 234bcca6c6bSrsc 235f32f3638Srsc // Caller holds reference to unlocked ip. Drop reference. 236bcca6c6bSrsc void 23707090dd7Srsc iput(struct inode *ip) 238bcca6c6bSrsc { 239f32f3638Srsc acquire(&icache.lock); 240f32f3638Srsc if(ip->ref == 1 && (ip->flags & I_VALID) && ip->nlink == 0){ 241f32f3638Srsc // inode is no longer used: truncate and free inode. 242f32f3638Srsc if(ip->flags & I_BUSY) 243eaea18cbSrsc panic("iput busy"); 244f32f3638Srsc ip->flags |= I_BUSY; 245f32f3638Srsc release(&icache.lock); 246f32f3638Srsc itrunc(ip); 247f32f3638Srsc ip->type = 0; 248f32f3638Srsc iupdate(ip); 249f32f3638Srsc acquire(&icache.lock); 250f32f3638Srsc ip->flags &= ~I_BUSY; 2518970df0cSrsc wakeup(ip); 252f32f3638Srsc } 253f32f3638Srsc ip->ref--; 254f32f3638Srsc release(&icache.lock); 255bcca6c6bSrsc } 256bcca6c6bSrsc 2577895178dSrsc // Common idiom: unlock, then put. 25807090dd7Srsc void 25907090dd7Srsc iunlockput(struct inode *ip) 26007090dd7Srsc { 26107090dd7Srsc iunlock(ip); 26207090dd7Srsc iput(ip); 26307090dd7Srsc } 26407090dd7Srsc 2658d2e9a48Srsc //PAGEBREAK! 266bcca6c6bSrsc // Allocate a new inode with the given type on device dev. 26707090dd7Srsc struct inode* 268e8d11c2eSkaashoek ialloc(uint dev, short type) 269e8d11c2eSkaashoek { 270a505fd66Srsc int inum; 271f32f3638Srsc struct buf *bp; 2727d4aef6cSrsc struct dinode *dip; 273a505fd66Srsc struct superblock sb; 274e8d11c2eSkaashoek 275a505fd66Srsc readsb(dev, &sb); 276a505fd66Srsc for(inum = 1; inum < sb.ninodes; inum++){ // loop over inode blocks 27724111398Skaashoek bp = bread(dev, IBLOCK(inum)); 2783341e30fSrsc dip = (struct dinode*)bp->data + inum%IPB; 279e8d11c2eSkaashoek if(dip->type == 0){ // a free inode 2802aa4c3bcSrtm memset(dip, 0, sizeof(*dip)); 281e8d11c2eSkaashoek dip->type = type; 282eaea18cbSrsc bwrite(bp); // mark it allocated on the disk 283e8d11c2eSkaashoek brelse(bp); 284f32f3638Srsc return iget(dev, inum); 285e8d11c2eSkaashoek } 28695c07f82Srsc brelse(bp); 28795c07f82Srsc } 28895c07f82Srsc panic("ialloc: no inodes"); 28995c07f82Srsc } 290e8d11c2eSkaashoek 291bcca6c6bSrsc // Copy inode, which has changed, from memory to disk. 292eaea18cbSrsc void 293bcca6c6bSrsc iupdate(struct inode *ip) 294bcca6c6bSrsc { 295bcca6c6bSrsc struct buf *bp; 296bcca6c6bSrsc struct dinode *dip; 297bcca6c6bSrsc 298bcca6c6bSrsc bp = bread(ip->dev, IBLOCK(ip->inum)); 2993341e30fSrsc dip = (struct dinode*)bp->data + ip->inum%IPB; 300bcca6c6bSrsc dip->type = ip->type; 301bcca6c6bSrsc dip->major = ip->major; 302bcca6c6bSrsc dip->minor = ip->minor; 303bcca6c6bSrsc dip->nlink = ip->nlink; 304bcca6c6bSrsc dip->size = ip->size; 305bcca6c6bSrsc memmove(dip->addrs, ip->addrs, sizeof(ip->addrs)); 306eaea18cbSrsc bwrite(bp); 307bcca6c6bSrsc brelse(bp); 308bcca6c6bSrsc } 309bcca6c6bSrsc 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 316bcca6c6bSrsc // listed in the block ip->addrs[INDIRECT]. 3179d3fb671Srtm 318bb207a1dSrsc // Return the disk block address of the nth block in inode ip. 319eaea18cbSrsc // If there is no such block, alloc controls whether one is allocated. 320eaea18cbSrsc static uint 321bcca6c6bSrsc bmap(struct inode *ip, uint bn, int alloc) 32222bac2cbSkaashoek { 323bcca6c6bSrsc uint addr, *a; 324bcca6c6bSrsc struct buf *bp; 32522bac2cbSkaashoek 326ea2909b6Skaashoek if(bn < NDIRECT){ 327bcca6c6bSrsc if((addr = ip->addrs[bn]) == 0){ 328bcca6c6bSrsc if(!alloc) 329bcca6c6bSrsc return -1; 330bcca6c6bSrsc ip->addrs[bn] = addr = balloc(ip->dev); 331ea2909b6Skaashoek } 332bcca6c6bSrsc return addr; 333bcca6c6bSrsc } 334bcca6c6bSrsc bn -= NDIRECT; 335bcca6c6bSrsc 336bcca6c6bSrsc if(bn < NINDIRECT){ 337bcca6c6bSrsc // Load indirect block, allocating if necessary. 338*ba6cd8a6Srsc if((addr = ip->addrs[NDIRECT]) == 0){ 339bcca6c6bSrsc if(!alloc) 340bcca6c6bSrsc return -1; 341*ba6cd8a6Srsc ip->addrs[NDIRECT] = addr = balloc(ip->dev); 342bcca6c6bSrsc } 343bcca6c6bSrsc bp = bread(ip->dev, addr); 344bcca6c6bSrsc a = (uint*)bp->data; 345bcca6c6bSrsc 346bcca6c6bSrsc if((addr = a[bn]) == 0){ 347bcca6c6bSrsc if(!alloc){ 348bcca6c6bSrsc brelse(bp); 349bcca6c6bSrsc return -1; 350bcca6c6bSrsc } 351bcca6c6bSrsc a[bn] = addr = balloc(ip->dev); 352eaea18cbSrsc bwrite(bp); 353bcca6c6bSrsc } 354bcca6c6bSrsc brelse(bp); 355bcca6c6bSrsc return addr; 35622bac2cbSkaashoek } 35722bac2cbSkaashoek 358bcca6c6bSrsc panic("bmap: out of range"); 359bcca6c6bSrsc } 360bcca6c6bSrsc 361bcca6c6bSrsc // Truncate inode (discard contents). 3628eb20827Srtm // Only called after the last dirent referring 3638eb20827Srtm // to this inode has been erased on disk. 364fbf91039Srsc static void 3652aa4c3bcSrtm itrunc(struct inode *ip) 36622bac2cbSkaashoek { 367ea2909b6Skaashoek int i, j; 368bcca6c6bSrsc struct buf *bp; 3697d4aef6cSrsc uint *a; 37022bac2cbSkaashoek 371bcca6c6bSrsc for(i = 0; i < NDIRECT; i++){ 372bcca6c6bSrsc if(ip->addrs[i]){ 37322bac2cbSkaashoek bfree(ip->dev, ip->addrs[i]); 37422bac2cbSkaashoek ip->addrs[i] = 0; 37522bac2cbSkaashoek } 37622bac2cbSkaashoek } 377bcca6c6bSrsc 378*ba6cd8a6Srsc if(ip->addrs[NDIRECT]){ 379*ba6cd8a6Srsc bp = bread(ip->dev, ip->addrs[NDIRECT]); 380bcca6c6bSrsc a = (uint*)bp->data; 381bcca6c6bSrsc for(j = 0; j < NINDIRECT; j++){ 382bcca6c6bSrsc if(a[j]) 383bcca6c6bSrsc bfree(ip->dev, a[j]); 384bcca6c6bSrsc } 385bcca6c6bSrsc brelse(bp); 386*ba6cd8a6Srsc bfree(ip->dev, ip->addrs[NDIRECT]); 387*ba6cd8a6Srsc ip->addrs[NDIRECT] = 0; 388bcca6c6bSrsc } 389bcca6c6bSrsc 39022bac2cbSkaashoek ip->size = 0; 39122bac2cbSkaashoek iupdate(ip); 39222bac2cbSkaashoek } 39322bac2cbSkaashoek 394bb207a1dSrsc // Copy stat information from inode. 395e958c538Skaashoek void 3961f544842Skaashoek stati(struct inode *ip, struct stat *st) 3971f544842Skaashoek { 3981dca3afbSrsc st->dev = ip->dev; 3991dca3afbSrsc st->ino = ip->inum; 4001dca3afbSrsc st->type = ip->type; 4011dca3afbSrsc st->nlink = ip->nlink; 4021dca3afbSrsc st->size = ip->size; 4031f544842Skaashoek } 4041f544842Skaashoek 405eaea18cbSrsc //PAGEBREAK! 406bb207a1dSrsc // Read data from inode. 407c59361f1Srtm int 40817a85657Srtm readi(struct inode *ip, char *dst, uint off, uint n) 409c59361f1Srtm { 410bcca6c6bSrsc uint tot, m; 411c59361f1Srtm struct buf *bp; 412c59361f1Srtm 413939f9edeSkaashoek if(ip->type == T_DEV){ 4141dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].read) 415939f9edeSkaashoek return -1; 416d844f0f9Srsc return devsw[ip->major].read(ip, dst, n); 417939f9edeSkaashoek } 418939f9edeSkaashoek 4197895178dSrsc if(off > ip->size || off + n < off) 420bcca6c6bSrsc return -1; 421bcca6c6bSrsc if(off + n > ip->size) 422bcca6c6bSrsc n = ip->size - off; 423bcca6c6bSrsc 424bcca6c6bSrsc for(tot=0; tot<n; tot+=m, off+=m, dst+=m){ 425bcca6c6bSrsc bp = bread(ip->dev, bmap(ip, off/BSIZE, 0)); 426bcca6c6bSrsc m = min(n - tot, BSIZE - off%BSIZE); 427bcca6c6bSrsc memmove(dst, bp->data + off%BSIZE, m); 428c59361f1Srtm brelse(bp); 429c59361f1Srtm } 430bcca6c6bSrsc return n; 431ea2909b6Skaashoek } 432ea2909b6Skaashoek 433eaea18cbSrsc // PAGEBREAK! 434bb207a1dSrsc // Write data to inode. 435ea2909b6Skaashoek int 436bcca6c6bSrsc writei(struct inode *ip, char *src, uint off, uint n) 4376fa5ffb5Skaashoek { 438bcca6c6bSrsc uint tot, m; 4397d4aef6cSrsc struct buf *bp; 4407d4aef6cSrsc 4416fa5ffb5Skaashoek if(ip->type == T_DEV){ 4421dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].write) 443939f9edeSkaashoek return -1; 444d844f0f9Srsc return devsw[ip->major].write(ip, src, n); 4457d4aef6cSrsc } 4467d4aef6cSrsc 447bcca6c6bSrsc if(off + n < off) 448bcca6c6bSrsc return -1; 449bcca6c6bSrsc if(off + n > MAXFILE*BSIZE) 450bcca6c6bSrsc n = MAXFILE*BSIZE - off; 451bcca6c6bSrsc 452bcca6c6bSrsc for(tot=0; tot<n; tot+=m, off+=m, src+=m){ 453bcca6c6bSrsc bp = bread(ip->dev, bmap(ip, off/BSIZE, 1)); 454bcca6c6bSrsc m = min(n - tot, BSIZE - off%BSIZE); 455bcca6c6bSrsc memmove(bp->data + off%BSIZE, src, m); 456eaea18cbSrsc bwrite(bp); 45728d9ef04Skaashoek brelse(bp); 45828d9ef04Skaashoek } 459bcca6c6bSrsc 460bcca6c6bSrsc if(n > 0 && off > ip->size){ 46148b82470Srsc ip->size = off; 46228d9ef04Skaashoek iupdate(ip); 46328d9ef04Skaashoek } 464bcca6c6bSrsc return n; 4656fa5ffb5Skaashoek } 4666fa5ffb5Skaashoek 467eaea18cbSrsc //PAGEBREAK! 468bcca6c6bSrsc // Directories 469bcca6c6bSrsc 470eaea18cbSrsc int 471fbf91039Srsc namecmp(const char *s, const char *t) 472fbf91039Srsc { 473766ba5ccSrsc return strncmp(s, t, DIRSIZ); 474fbf91039Srsc } 475fbf91039Srsc 476bcca6c6bSrsc // Look for a directory entry in a directory. 477eaea18cbSrsc // If found, set *poff to byte offset of entry. 47820365348Srtm // Caller must have already locked dp. 47907090dd7Srsc struct inode* 480fbf91039Srsc dirlookup(struct inode *dp, char *name, uint *poff) 481bcca6c6bSrsc { 482f32f3638Srsc uint off, inum; 483bcca6c6bSrsc struct buf *bp; 484bcca6c6bSrsc struct dirent *de; 485bcca6c6bSrsc 486bcca6c6bSrsc if(dp->type != T_DIR) 48720365348Srtm panic("dirlookup not DIR"); 488bcca6c6bSrsc 489bcca6c6bSrsc for(off = 0; off < dp->size; off += BSIZE){ 490bcca6c6bSrsc bp = bread(dp->dev, bmap(dp, off / BSIZE, 0)); 491bcca6c6bSrsc for(de = (struct dirent*)bp->data; 492bcca6c6bSrsc de < (struct dirent*)(bp->data + BSIZE); 493bcca6c6bSrsc de++){ 494bcca6c6bSrsc if(de->inum == 0) 495bcca6c6bSrsc continue; 496fbf91039Srsc if(namecmp(name, de->name) == 0){ 497bcca6c6bSrsc // entry matches path element 498e2a620daSrsc if(poff) 499bcca6c6bSrsc *poff = off + (uchar*)de - bp->data; 500f32f3638Srsc inum = de->inum; 501bcca6c6bSrsc brelse(bp); 502f32f3638Srsc return iget(dp->dev, inum); 503f32f3638Srsc } 504f32f3638Srsc } 505f32f3638Srsc brelse(bp); 506f32f3638Srsc } 507bcca6c6bSrsc return 0; 508bcca6c6bSrsc } 509bcca6c6bSrsc 510bcca6c6bSrsc // Write a new directory entry (name, ino) into the directory dp. 511eaea18cbSrsc int 512fbf91039Srsc dirlink(struct inode *dp, char *name, uint ino) 513bcca6c6bSrsc { 514e2a620daSrsc int off; 515bcca6c6bSrsc struct dirent de; 51607090dd7Srsc struct inode *ip; 517f32f3638Srsc 518eaea18cbSrsc // Check that name is not present. 51907090dd7Srsc if((ip = dirlookup(dp, name, 0)) != 0){ 52007090dd7Srsc iput(ip); 521f32f3638Srsc return -1; 522f32f3638Srsc } 523bcca6c6bSrsc 524bcca6c6bSrsc // Look for an empty dirent. 525bcca6c6bSrsc for(off = 0; off < dp->size; off += sizeof(de)){ 526bcca6c6bSrsc if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 5277895178dSrsc panic("dirlink read"); 528bcca6c6bSrsc if(de.inum == 0) 529bcca6c6bSrsc break; 530bcca6c6bSrsc } 531bcca6c6bSrsc 532766ba5ccSrsc strncpy(de.name, name, DIRSIZ); 533bcca6c6bSrsc de.inum = ino; 534bcca6c6bSrsc if(writei(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 5357895178dSrsc panic("dirlink"); 536f32f3638Srsc 537f32f3638Srsc return 0; 538bcca6c6bSrsc } 539bcca6c6bSrsc 5408d2e9a48Srsc //PAGEBREAK! 541bcca6c6bSrsc // Paths 542bcca6c6bSrsc 543eaea18cbSrsc // Copy the next path element from path into name. 544eaea18cbSrsc // Return a pointer to the element following the copied one. 545eaea18cbSrsc // The returned path has no leading slashes, 546eaea18cbSrsc // so the caller can check *path=='\0' to see if the name is the last one. 547eaea18cbSrsc // If no name to remove, return 0. 548ab5c2dbbSrsc // 549ab5c2dbbSrsc // Examples: 550eaea18cbSrsc // skipelem("a/bb/c", name) = "bb/c", setting name = "a" 5517895178dSrsc // skipelem("///a//bb", name) = "bb", setting name = "a" 552eaea18cbSrsc // skipelem("", name) = skipelem("////", name) = 0 553ab5c2dbbSrsc // 554ab5c2dbbSrsc static char* 555fbf91039Srsc skipelem(char *path, char *name) 556ab5c2dbbSrsc { 557fbf91039Srsc char *s; 558fbf91039Srsc int len; 559fbf91039Srsc 560ab5c2dbbSrsc while(*path == '/') 561ab5c2dbbSrsc path++; 562ab5c2dbbSrsc if(*path == 0) 563ab5c2dbbSrsc return 0; 564fbf91039Srsc s = path; 565ab5c2dbbSrsc while(*path != '/' && *path != 0) 566ab5c2dbbSrsc path++; 567fbf91039Srsc len = path - s; 568fbf91039Srsc if(len >= DIRSIZ) 569fbf91039Srsc memmove(name, s, DIRSIZ); 570fbf91039Srsc else { 571fbf91039Srsc memmove(name, s, len); 572fbf91039Srsc name[len] = 0; 573fbf91039Srsc } 574ab5c2dbbSrsc while(*path == '/') 575ab5c2dbbSrsc path++; 576ab5c2dbbSrsc return path; 577ab5c2dbbSrsc } 578ab5c2dbbSrsc 579eaea18cbSrsc // Look up and return the inode for a path name. 580bf2932a6Srsc // If parent != 0, return the inode for the parent and copy the final 581bf2932a6Srsc // path element into name, which must have room for DIRSIZ bytes. 58207090dd7Srsc static struct inode* 583fbf91039Srsc _namei(char *path, int parent, char *name) 5849d3fb671Srtm { 58507090dd7Srsc struct inode *ip, *next; 5869d3fb671Srtm 587ab5c2dbbSrsc if(*path == '/') 5882ce40d70Srtm ip = iget(ROOTDEV, ROOTINO); 589f32f3638Srsc else 59007090dd7Srsc ip = idup(cp->cwd); 5919d3fb671Srtm 592fbf91039Srsc while((path = skipelem(path, name)) != 0){ 59307090dd7Srsc ilock(ip); 59407090dd7Srsc if(ip->type != T_DIR){ 59507090dd7Srsc iunlockput(ip); 596eaea18cbSrsc return 0; 597eaea18cbSrsc } 598e2a620daSrsc if(parent && *path == '\0'){ 599e2a620daSrsc // Stop one level early. 60007090dd7Srsc iunlock(ip); 60107090dd7Srsc return ip; 602ab5c2dbbSrsc } 6037895178dSrsc if((next = dirlookup(ip, name, 0)) == 0){ 60407090dd7Srsc iunlockput(ip); 605eaea18cbSrsc return 0; 606eaea18cbSrsc } 60707090dd7Srsc iunlockput(ip); 60807090dd7Srsc ip = next; 609ab5c2dbbSrsc } 61020365348Srtm if(parent){ 61107090dd7Srsc iput(ip); 6125051da6dSrtm return 0; 61320365348Srtm } 61407090dd7Srsc return ip; 6150633b971Skaashoek } 6169d3fb671Srtm 6177895178dSrsc struct inode* 6187895178dSrsc namei(char *path) 6197895178dSrsc { 6207895178dSrsc char name[DIRSIZ]; 6217895178dSrsc return _namei(path, 0, name); 6227895178dSrsc } 623bf2932a6Srsc 6247895178dSrsc struct inode* 6257895178dSrsc nameiparent(char *path, char *name) 6267895178dSrsc { 6277895178dSrsc return _namei(path, 1, name); 6287895178dSrsc } 629