1*a505fd66Srsc // 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" 141f544842Skaashoek #include "stat.h" 1511a9947fSrtm #include "param.h" 1611a9947fSrtm #include "x86.h" 1711a9947fSrtm #include "mmu.h" 1811a9947fSrtm #include "proc.h" 1911a9947fSrtm #include "defs.h" 2011a9947fSrtm #include "spinlock.h" 2111a9947fSrtm #include "buf.h" 2211a9947fSrtm #include "fs.h" 2311a9947fSrtm #include "fsvar.h" 246fa5ffb5Skaashoek #include "dev.h" 2511a9947fSrtm 26bcca6c6bSrsc #define min(a, b) ((a) < (b) ? (a) : (b)) 27fbf91039Srsc static void itrunc(struct inode*); 2811a9947fSrtm 29*a505fd66Srsc // Read the super block. 30*a505fd66Srsc static void 31*a505fd66Srsc readsb(int dev, struct superblock *sb) 32*a505fd66Srsc { 33*a505fd66Srsc struct buf *bp; 34*a505fd66Srsc 35*a505fd66Srsc bp = bread(dev, 1); 36*a505fd66Srsc memmove(sb, bp->data, sizeof(*sb)); 37*a505fd66Srsc brelse(bp); 38*a505fd66Srsc } 39*a505fd66Srsc 40*a505fd66Srsc // Zero a block. 41*a505fd66Srsc static void 42*a505fd66Srsc bzero(int dev, int bno) 43*a505fd66Srsc { 44*a505fd66Srsc struct buf *bp; 45*a505fd66Srsc 46*a505fd66Srsc bp = bread(dev, bno); 47*a505fd66Srsc memset(bp->data, 0, BSIZE); 48*a505fd66Srsc bwrite(bp); 49*a505fd66Srsc brelse(bp); 50*a505fd66Srsc } 51*a505fd66Srsc 52bcca6c6bSrsc // Blocks. 535be0039cSrtm 54f5527388Srsc // Allocate a disk block. 5524111398Skaashoek static uint 5624111398Skaashoek balloc(uint dev) 5724111398Skaashoek { 58*a505fd66Srsc int b, bi, m; 5924111398Skaashoek struct buf *bp; 60*a505fd66Srsc struct superblock sb; 6124111398Skaashoek 62*a505fd66Srsc bp = 0; 63*a505fd66Srsc readsb(dev, &sb); 64*a505fd66Srsc for(b = 0; b < sb.size; b += BPB){ 65*a505fd66Srsc bp = bread(dev, BBLOCK(b, sb.ninodes)); 66*a505fd66Srsc for(bi = 0; bi < BPB; bi++){ 67*a505fd66Srsc m = 1 << (bi % 8); 68*a505fd66Srsc if((bp->data[bi/8] & m) == 0){ // Is block free? 69*a505fd66Srsc bp->data[bi/8] |= m; // Mark block in use on disk. 70*a505fd66Srsc bwrite(bp); 7124111398Skaashoek brelse(bp); 72*a505fd66Srsc return b + bi; 7324111398Skaashoek } 74*a505fd66Srsc } 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; 85*a505fd66Srsc struct superblock sb; 86*a505fd66Srsc int bi, m; 8728d9ef04Skaashoek 88*a505fd66Srsc bzero(dev, b); 8928d9ef04Skaashoek 90*a505fd66Srsc readsb(dev, &sb); 91*a505fd66Srsc bp = bread(dev, BBLOCK(b, sb.ninodes)); 9228d9ef04Skaashoek bi = b % BPB; 93*a505fd66Srsc m = 1 << (bi % 8); 94902b13f5Srtm if((bp->data[bi/8] & m) == 0) 95902b13f5Srtm panic("freeing free block"); 96*a505fd66Srsc bp->data[bi/8] &= ~m; // Mark block free on disk. 97*a505fd66Srsc bwrite(bp); 9828d9ef04Skaashoek brelse(bp); 9928d9ef04Skaashoek } 10024111398Skaashoek 101bcca6c6bSrsc // Inodes 102bcca6c6bSrsc // 103bcca6c6bSrsc // The inodes are laid out sequentially on disk immediately after 104bcca6c6bSrsc // the superblock. The kernel keeps a cache of the in-use 105bcca6c6bSrsc // on-disk structures to provide a place for synchronizing access 106bcca6c6bSrsc // to inodes shared between multiple processes. 107bcca6c6bSrsc // 108902b13f5Srtm // ip->ref counts the number of pointer references to this cached 109bcca6c6bSrsc // inode; references are typically kept in struct file and in cp->cwd. 110bcca6c6bSrsc // When ip->ref falls to zero, the inode is no longer cached. 111bcca6c6bSrsc // It is an error to use an inode without holding a reference to it. 112bcca6c6bSrsc // 113902b13f5Srtm // Inodes can be locked with I_BUSY (like bufs and B_BUSY). 114eaea18cbSrsc // Processes are only allowed to read and write inode 115eaea18cbSrsc // metadata and contents when holding the inode's lock. 116902b13f5Srtm // Because inode locks are held during disk accesses, 117902b13f5Srtm // they are implemented using a flag rather than with 118902b13f5Srtm // spin locks. Callers are responsible for locking 119eaea18cbSrsc // inodes before passing them to routines in this file; leaving 120eaea18cbSrsc // this responsibility with the caller makes it possible for them 121eaea18cbSrsc // to create arbitrarily-sized atomic operations. 122eaea18cbSrsc // 123eaea18cbSrsc // To give maximum control over locking to the callers, 124eaea18cbSrsc // the routines in this file that return inode pointers 125eaea18cbSrsc // return pointers to *unlocked* inodes. It is the callers' 126902b13f5Srtm // responsibility to lock them before using them. A non-zero 127902b13f5Srtm // ip->ref keeps these unlocked inodes in the cache. 128bcca6c6bSrsc 129bcca6c6bSrsc struct { 130bcca6c6bSrsc struct spinlock lock; 131bcca6c6bSrsc struct inode inode[NINODE]; 132bcca6c6bSrsc } icache; 133bcca6c6bSrsc 134bcca6c6bSrsc void 135bcca6c6bSrsc iinit(void) 136bcca6c6bSrsc { 137bcca6c6bSrsc initlock(&icache.lock, "icache.lock"); 138bcca6c6bSrsc } 139bcca6c6bSrsc 140f5527388Srsc // Find the inode with number inum on device dev 141eaea18cbSrsc // and return the in-memory copy. h 14207090dd7Srsc static struct inode* 14311a9947fSrtm iget(uint dev, uint inum) 14411a9947fSrtm { 145bcca6c6bSrsc struct inode *ip, *empty; 14611a9947fSrtm 147bcca6c6bSrsc acquire(&icache.lock); 14811a9947fSrtm 149bcca6c6bSrsc // Try for cached inode. 150bcca6c6bSrsc empty = 0; 151bcca6c6bSrsc for(ip = &icache.inode[0]; ip < &icache.inode[NINODE]; ip++){ 1520d6bbd31Srsc if(ip->ref > 0 && ip->dev == dev && ip->inum == inum){ 1530d6bbd31Srsc ip->ref++; 154bcca6c6bSrsc release(&icache.lock); 15507090dd7Srsc return ip; 15611a9947fSrtm } 157bcca6c6bSrsc if(empty == 0 && ip->ref == 0) // Remember empty slot. 158bcca6c6bSrsc empty = ip; 15911a9947fSrtm } 16011a9947fSrtm 161bcca6c6bSrsc // Allocate fresh inode. 162bcca6c6bSrsc if(empty == 0) 16332eea766Srsc panic("iget: no inodes"); 16411a9947fSrtm 165bcca6c6bSrsc ip = empty; 166bcca6c6bSrsc ip->dev = dev; 167bcca6c6bSrsc ip->inum = inum; 168bcca6c6bSrsc ip->ref = 1; 169f32f3638Srsc ip->flags = 0; 170bcca6c6bSrsc release(&icache.lock); 17111a9947fSrtm 17207090dd7Srsc return ip; 173f32f3638Srsc } 174f32f3638Srsc 175eaea18cbSrsc // Increment reference count for ip. 176eaea18cbSrsc // Returns ip to enable ip = idup(ip1) idiom. 17707090dd7Srsc struct inode* 17807090dd7Srsc idup(struct inode *ip) 179f32f3638Srsc { 180eaea18cbSrsc acquire(&icache.lock); 181eaea18cbSrsc ip->ref++; 182eaea18cbSrsc release(&icache.lock); 18307090dd7Srsc return ip; 184f32f3638Srsc } 185f32f3638Srsc 186f32f3638Srsc // Lock the given inode. 18707090dd7Srsc void 18807090dd7Srsc ilock(struct inode *ip) 189f32f3638Srsc { 190f32f3638Srsc struct buf *bp; 191f32f3638Srsc struct dinode *dip; 192eaea18cbSrsc 19307090dd7Srsc if(ip == 0 || ip->ref < 1) 19407090dd7Srsc panic("ilock"); 195f32f3638Srsc 196f32f3638Srsc acquire(&icache.lock); 197f32f3638Srsc while(ip->flags & I_BUSY) 198f32f3638Srsc sleep(ip, &icache.lock); 199f32f3638Srsc ip->flags |= I_BUSY; 200f32f3638Srsc release(&icache.lock); 201f32f3638Srsc 202f32f3638Srsc if(!(ip->flags & I_VALID)){ 203f32f3638Srsc bp = bread(ip->dev, IBLOCK(ip->inum)); 204f32f3638Srsc dip = &((struct dinode*)(bp->data))[ip->inum % IPB]; 205bcca6c6bSrsc ip->type = dip->type; 206bcca6c6bSrsc ip->major = dip->major; 207bcca6c6bSrsc ip->minor = dip->minor; 208bcca6c6bSrsc ip->nlink = dip->nlink; 209bcca6c6bSrsc ip->size = dip->size; 210bcca6c6bSrsc memmove(ip->addrs, dip->addrs, sizeof(ip->addrs)); 21111a9947fSrtm brelse(bp); 212f32f3638Srsc ip->flags |= I_VALID; 213eaea18cbSrsc if(ip->type == 0) 214eaea18cbSrsc panic("ilock: no type"); 21511a9947fSrtm } 216bcca6c6bSrsc } 217bcca6c6bSrsc 218bcca6c6bSrsc // Unlock the given inode. 21907090dd7Srsc void 220bcca6c6bSrsc iunlock(struct inode *ip) 221bcca6c6bSrsc { 22207090dd7Srsc if(ip == 0 || !(ip->flags & I_BUSY) || ip->ref < 1) 223bcca6c6bSrsc panic("iunlock"); 224bcca6c6bSrsc 225bcca6c6bSrsc acquire(&icache.lock); 226f32f3638Srsc ip->flags &= ~I_BUSY; 227bcca6c6bSrsc wakeup(ip); 228bcca6c6bSrsc release(&icache.lock); 229bcca6c6bSrsc } 230bcca6c6bSrsc 231f32f3638Srsc // Caller holds reference to unlocked ip. Drop reference. 232bcca6c6bSrsc void 23307090dd7Srsc iput(struct inode *ip) 234bcca6c6bSrsc { 235f32f3638Srsc acquire(&icache.lock); 236f32f3638Srsc if(ip->ref == 1 && (ip->flags & I_VALID) && ip->nlink == 0) { 237f32f3638Srsc // inode is no longer used: truncate and free inode. 238f32f3638Srsc if(ip->flags & I_BUSY) 239eaea18cbSrsc panic("iput busy"); 240f32f3638Srsc ip->flags |= I_BUSY; 241f32f3638Srsc release(&icache.lock); 242f32f3638Srsc // XXX convince rsc that no one will come find this inode. 243f32f3638Srsc itrunc(ip); 244f32f3638Srsc ip->type = 0; 245f32f3638Srsc iupdate(ip); 246f32f3638Srsc acquire(&icache.lock); 247f32f3638Srsc ip->flags &= ~I_BUSY; 248f32f3638Srsc } 249f32f3638Srsc ip->ref--; 250f32f3638Srsc release(&icache.lock); 251bcca6c6bSrsc } 252bcca6c6bSrsc 25307090dd7Srsc void 25407090dd7Srsc iunlockput(struct inode *ip) 25507090dd7Srsc { 25607090dd7Srsc iunlock(ip); 25707090dd7Srsc iput(ip); 25807090dd7Srsc } 25907090dd7Srsc 2608d2e9a48Srsc //PAGEBREAK! 261bcca6c6bSrsc // Allocate a new inode with the given type on device dev. 26207090dd7Srsc struct inode* 263e8d11c2eSkaashoek ialloc(uint dev, short type) 264e8d11c2eSkaashoek { 265*a505fd66Srsc int inum; 266f32f3638Srsc struct buf *bp; 2677d4aef6cSrsc struct dinode *dip; 268*a505fd66Srsc struct superblock sb; 269e8d11c2eSkaashoek 270*a505fd66Srsc readsb(dev, &sb); 271*a505fd66Srsc for(inum = 1; inum < sb.ninodes; inum++) { // loop over inode blocks 27224111398Skaashoek bp = bread(dev, IBLOCK(inum)); 273e8d11c2eSkaashoek dip = &((struct dinode*)(bp->data))[inum % IPB]; 274e8d11c2eSkaashoek if(dip->type == 0) { // a free inode 2752aa4c3bcSrtm memset(dip, 0, sizeof(*dip)); 276e8d11c2eSkaashoek dip->type = type; 277eaea18cbSrsc bwrite(bp); // mark it allocated on the disk 278e8d11c2eSkaashoek brelse(bp); 279f32f3638Srsc return iget(dev, inum); 280e8d11c2eSkaashoek } 28195c07f82Srsc brelse(bp); 28295c07f82Srsc } 28395c07f82Srsc panic("ialloc: no inodes"); 28495c07f82Srsc } 285e8d11c2eSkaashoek 286bcca6c6bSrsc // Copy inode, which has changed, from memory to disk. 287eaea18cbSrsc void 288bcca6c6bSrsc iupdate(struct inode *ip) 289bcca6c6bSrsc { 290bcca6c6bSrsc struct buf *bp; 291bcca6c6bSrsc struct dinode *dip; 292bcca6c6bSrsc 293bcca6c6bSrsc bp = bread(ip->dev, IBLOCK(ip->inum)); 294bcca6c6bSrsc dip = &((struct dinode*)(bp->data))[ip->inum % IPB]; 295bcca6c6bSrsc dip->type = ip->type; 296bcca6c6bSrsc dip->major = ip->major; 297bcca6c6bSrsc dip->minor = ip->minor; 298bcca6c6bSrsc dip->nlink = ip->nlink; 299bcca6c6bSrsc dip->size = ip->size; 300bcca6c6bSrsc memmove(dip->addrs, ip->addrs, sizeof(ip->addrs)); 301eaea18cbSrsc bwrite(bp); 302bcca6c6bSrsc brelse(bp); 303bcca6c6bSrsc } 304bcca6c6bSrsc 3058d2e9a48Srsc //PAGEBREAK! 306bcca6c6bSrsc // Inode contents 307bcca6c6bSrsc // 308bcca6c6bSrsc // The contents (data) associated with each inode is stored 309bcca6c6bSrsc // in a sequence of blocks on the disk. The first NDIRECT blocks 310bcca6c6bSrsc // are stored in ip->addrs[]. The next NINDIRECT blocks are 311bcca6c6bSrsc // listed in the block ip->addrs[INDIRECT]. 3129d3fb671Srtm 313bb207a1dSrsc // Return the disk block address of the nth block in inode ip. 314eaea18cbSrsc // If there is no such block, alloc controls whether one is allocated. 315eaea18cbSrsc static uint 316bcca6c6bSrsc bmap(struct inode *ip, uint bn, int alloc) 31722bac2cbSkaashoek { 318bcca6c6bSrsc uint addr, *a; 319bcca6c6bSrsc struct buf *bp; 32022bac2cbSkaashoek 321ea2909b6Skaashoek if(bn < NDIRECT) { 322bcca6c6bSrsc if((addr = ip->addrs[bn]) == 0) { 323bcca6c6bSrsc if(!alloc) 324bcca6c6bSrsc return -1; 325bcca6c6bSrsc ip->addrs[bn] = addr = balloc(ip->dev); 326ea2909b6Skaashoek } 327bcca6c6bSrsc return addr; 328bcca6c6bSrsc } 329bcca6c6bSrsc bn -= NDIRECT; 330bcca6c6bSrsc 331bcca6c6bSrsc if(bn < NINDIRECT) { 332bcca6c6bSrsc // Load indirect block, allocating if necessary. 333bcca6c6bSrsc if((addr = ip->addrs[INDIRECT]) == 0) { 334bcca6c6bSrsc if(!alloc) 335bcca6c6bSrsc return -1; 336bcca6c6bSrsc ip->addrs[INDIRECT] = addr = balloc(ip->dev); 337bcca6c6bSrsc } 338bcca6c6bSrsc bp = bread(ip->dev, addr); 339bcca6c6bSrsc a = (uint*)bp->data; 340bcca6c6bSrsc 341bcca6c6bSrsc if((addr = a[bn]) == 0) { 342bcca6c6bSrsc if(!alloc) { 343bcca6c6bSrsc brelse(bp); 344bcca6c6bSrsc return -1; 345bcca6c6bSrsc } 346bcca6c6bSrsc a[bn] = addr = balloc(ip->dev); 347eaea18cbSrsc bwrite(bp); 348bcca6c6bSrsc } 349bcca6c6bSrsc brelse(bp); 350bcca6c6bSrsc return addr; 35122bac2cbSkaashoek } 35222bac2cbSkaashoek 353bcca6c6bSrsc panic("bmap: out of range"); 354bcca6c6bSrsc } 355bcca6c6bSrsc 356eaea18cbSrsc // PAGEBREAK: 30 357bcca6c6bSrsc // Truncate inode (discard contents). 358fbf91039Srsc static void 3592aa4c3bcSrtm itrunc(struct inode *ip) 36022bac2cbSkaashoek { 361ea2909b6Skaashoek int i, j; 362bcca6c6bSrsc struct buf *bp; 3637d4aef6cSrsc uint *a; 36422bac2cbSkaashoek 365bcca6c6bSrsc for(i = 0; i < NDIRECT; i++) { 366bcca6c6bSrsc if(ip->addrs[i]) { 36722bac2cbSkaashoek bfree(ip->dev, ip->addrs[i]); 36822bac2cbSkaashoek ip->addrs[i] = 0; 36922bac2cbSkaashoek } 37022bac2cbSkaashoek } 371bcca6c6bSrsc 372bcca6c6bSrsc if(ip->addrs[INDIRECT]) { 373bcca6c6bSrsc bp = bread(ip->dev, ip->addrs[INDIRECT]); 374bcca6c6bSrsc a = (uint*)bp->data; 375bcca6c6bSrsc for(j = 0; j < NINDIRECT; j++) { 376bcca6c6bSrsc if(a[j]) 377bcca6c6bSrsc bfree(ip->dev, a[j]); 378bcca6c6bSrsc } 379bcca6c6bSrsc brelse(bp); 380bcca6c6bSrsc ip->addrs[INDIRECT] = 0; 381bcca6c6bSrsc } 382bcca6c6bSrsc 38322bac2cbSkaashoek ip->size = 0; 38422bac2cbSkaashoek iupdate(ip); 38522bac2cbSkaashoek } 38622bac2cbSkaashoek 387bb207a1dSrsc // Copy stat information from inode. 388e958c538Skaashoek void 3891f544842Skaashoek stati(struct inode *ip, struct stat *st) 3901f544842Skaashoek { 3911dca3afbSrsc st->dev = ip->dev; 3921dca3afbSrsc st->ino = ip->inum; 3931dca3afbSrsc st->type = ip->type; 3941dca3afbSrsc st->nlink = ip->nlink; 3951dca3afbSrsc st->size = ip->size; 3961f544842Skaashoek } 3971f544842Skaashoek 398eaea18cbSrsc //PAGEBREAK! 399bb207a1dSrsc // Read data from inode. 400c59361f1Srtm int 40117a85657Srtm readi(struct inode *ip, char *dst, uint off, uint n) 402c59361f1Srtm { 403bcca6c6bSrsc uint tot, m; 404c59361f1Srtm struct buf *bp; 405c59361f1Srtm 406939f9edeSkaashoek if(ip->type == T_DEV) { 4071dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].read) 408939f9edeSkaashoek return -1; 4091dca3afbSrsc return devsw[ip->major].read(ip->minor, dst, n); 410939f9edeSkaashoek } 411939f9edeSkaashoek 412bcca6c6bSrsc if(off + n < off) 413bcca6c6bSrsc return -1; 414bcca6c6bSrsc if(off + n > ip->size) 415bcca6c6bSrsc n = ip->size - off; 416bcca6c6bSrsc 417bcca6c6bSrsc for(tot=0; tot<n; tot+=m, off+=m, dst+=m) { 418bcca6c6bSrsc bp = bread(ip->dev, bmap(ip, off/BSIZE, 0)); 419bcca6c6bSrsc m = min(n - tot, BSIZE - off%BSIZE); 420bcca6c6bSrsc memmove(dst, bp->data + off%BSIZE, m); 421c59361f1Srtm brelse(bp); 422c59361f1Srtm } 423bcca6c6bSrsc return n; 424ea2909b6Skaashoek } 425ea2909b6Skaashoek 426eaea18cbSrsc // PAGEBREAK! 427bb207a1dSrsc // Write data to inode. 428ea2909b6Skaashoek int 429bcca6c6bSrsc writei(struct inode *ip, char *src, uint off, uint n) 4306fa5ffb5Skaashoek { 431bcca6c6bSrsc uint tot, m; 4327d4aef6cSrsc struct buf *bp; 4337d4aef6cSrsc 4346fa5ffb5Skaashoek if(ip->type == T_DEV) { 4351dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].write) 436939f9edeSkaashoek return -1; 437bcca6c6bSrsc return devsw[ip->major].write(ip->minor, src, n); 4387d4aef6cSrsc } 4397d4aef6cSrsc 440bcca6c6bSrsc if(off + n < off) 441bcca6c6bSrsc return -1; 442bcca6c6bSrsc if(off + n > MAXFILE*BSIZE) 443bcca6c6bSrsc n = MAXFILE*BSIZE - off; 444bcca6c6bSrsc 445bcca6c6bSrsc for(tot=0; tot<n; tot+=m, off+=m, src+=m) { 446bcca6c6bSrsc bp = bread(ip->dev, bmap(ip, off/BSIZE, 1)); 447bcca6c6bSrsc m = min(n - tot, BSIZE - off%BSIZE); 448bcca6c6bSrsc memmove(bp->data + off%BSIZE, src, m); 449eaea18cbSrsc bwrite(bp); 45028d9ef04Skaashoek brelse(bp); 45128d9ef04Skaashoek } 452bcca6c6bSrsc 453bcca6c6bSrsc if(n > 0 && off > ip->size) { 45448b82470Srsc ip->size = off; 45528d9ef04Skaashoek iupdate(ip); 45628d9ef04Skaashoek } 457bcca6c6bSrsc return n; 4586fa5ffb5Skaashoek } 4596fa5ffb5Skaashoek 460eaea18cbSrsc //PAGEBREAK! 461bcca6c6bSrsc // Directories 462bcca6c6bSrsc 463eaea18cbSrsc int 464fbf91039Srsc namecmp(const char *s, const char *t) 465fbf91039Srsc { 466766ba5ccSrsc return strncmp(s, t, DIRSIZ); 467fbf91039Srsc } 468fbf91039Srsc 469bcca6c6bSrsc // Look for a directory entry in a directory. 470eaea18cbSrsc // If found, set *poff to byte offset of entry. 47120365348Srtm // Caller must have already locked dp. 47207090dd7Srsc struct inode* 473fbf91039Srsc dirlookup(struct inode *dp, char *name, uint *poff) 474bcca6c6bSrsc { 475f32f3638Srsc uint off, inum; 476bcca6c6bSrsc struct buf *bp; 477bcca6c6bSrsc struct dirent *de; 478bcca6c6bSrsc 479bcca6c6bSrsc if(dp->type != T_DIR) 48020365348Srtm panic("dirlookup not DIR"); 481bcca6c6bSrsc 482bcca6c6bSrsc for(off = 0; off < dp->size; off += BSIZE){ 483bcca6c6bSrsc bp = bread(dp->dev, bmap(dp, off / BSIZE, 0)); 484bcca6c6bSrsc for(de = (struct dirent*) bp->data; 485bcca6c6bSrsc de < (struct dirent*) (bp->data + BSIZE); 486bcca6c6bSrsc de++){ 487bcca6c6bSrsc if(de->inum == 0) 488bcca6c6bSrsc continue; 489fbf91039Srsc if(namecmp(name, de->name) == 0){ 490bcca6c6bSrsc // entry matches path element 491e2a620daSrsc if(poff) 492bcca6c6bSrsc *poff = off + (uchar*)de - bp->data; 493f32f3638Srsc inum = de->inum; 494bcca6c6bSrsc brelse(bp); 495f32f3638Srsc return iget(dp->dev, inum); 496f32f3638Srsc } 497f32f3638Srsc } 498f32f3638Srsc brelse(bp); 499f32f3638Srsc } 500bcca6c6bSrsc return 0; 501bcca6c6bSrsc } 502bcca6c6bSrsc 503bcca6c6bSrsc // Write a new directory entry (name, ino) into the directory dp. 504eaea18cbSrsc int 505fbf91039Srsc dirlink(struct inode *dp, char *name, uint ino) 506bcca6c6bSrsc { 507e2a620daSrsc int off; 508bcca6c6bSrsc struct dirent de; 50907090dd7Srsc struct inode *ip; 510f32f3638Srsc 511eaea18cbSrsc // Check that name is not present. 51207090dd7Srsc if((ip = dirlookup(dp, name, 0)) != 0){ 51307090dd7Srsc iput(ip); 514f32f3638Srsc return -1; 515f32f3638Srsc } 516bcca6c6bSrsc 517bcca6c6bSrsc // Look for an empty dirent. 518bcca6c6bSrsc for(off = 0; off < dp->size; off += sizeof(de)){ 519bcca6c6bSrsc if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 520bcca6c6bSrsc panic("dirwrite read"); 521bcca6c6bSrsc if(de.inum == 0) 522bcca6c6bSrsc break; 523bcca6c6bSrsc } 524bcca6c6bSrsc 525766ba5ccSrsc strncpy(de.name, name, DIRSIZ); 526bcca6c6bSrsc de.inum = ino; 527bcca6c6bSrsc if(writei(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 528bcca6c6bSrsc panic("dirwrite"); 529f32f3638Srsc 530f32f3638Srsc return 0; 531bcca6c6bSrsc } 532bcca6c6bSrsc 5338d2e9a48Srsc //PAGEBREAK! 534bcca6c6bSrsc // Paths 535bcca6c6bSrsc 536eaea18cbSrsc // Copy the next path element from path into name. 537eaea18cbSrsc // Return a pointer to the element following the copied one. 538eaea18cbSrsc // The returned path has no leading slashes, 539eaea18cbSrsc // so the caller can check *path=='\0' to see if the name is the last one. 540eaea18cbSrsc // If no name to remove, return 0. 541ab5c2dbbSrsc // 542ab5c2dbbSrsc // Examples: 543eaea18cbSrsc // skipelem("a/bb/c", name) = "bb/c", setting name = "a" 54420365348Srtm // skipelem("///a/bb", name) = "bb", setting name="a" 545eaea18cbSrsc // skipelem("", name) = skipelem("////", name) = 0 546ab5c2dbbSrsc // 547ab5c2dbbSrsc static char* 548fbf91039Srsc skipelem(char *path, char *name) 549ab5c2dbbSrsc { 550fbf91039Srsc char *s; 551fbf91039Srsc int len; 552fbf91039Srsc 553ab5c2dbbSrsc while(*path == '/') 554ab5c2dbbSrsc path++; 555ab5c2dbbSrsc if(*path == 0) 556ab5c2dbbSrsc return 0; 557fbf91039Srsc s = path; 558ab5c2dbbSrsc while(*path != '/' && *path != 0) 559ab5c2dbbSrsc path++; 560fbf91039Srsc len = path - s; 561fbf91039Srsc if(len >= DIRSIZ) 562fbf91039Srsc memmove(name, s, DIRSIZ); 563fbf91039Srsc else{ 564fbf91039Srsc memmove(name, s, len); 565fbf91039Srsc name[len] = 0; 566fbf91039Srsc } 567ab5c2dbbSrsc while(*path == '/') 568ab5c2dbbSrsc path++; 569ab5c2dbbSrsc return path; 570ab5c2dbbSrsc } 571ab5c2dbbSrsc 5728d2e9a48Srsc static struct inode* _namei(char*, int, char*); 5738d2e9a48Srsc 5748d2e9a48Srsc struct inode* 5758d2e9a48Srsc namei(char *path) 5768d2e9a48Srsc { 5778d2e9a48Srsc char name[DIRSIZ]; 5788d2e9a48Srsc return _namei(path, 0, name); 5798d2e9a48Srsc } 5808d2e9a48Srsc 5818d2e9a48Srsc struct inode* 5828d2e9a48Srsc nameiparent(char *path, char *name) 5838d2e9a48Srsc { 5848d2e9a48Srsc return _namei(path, 1, name); 5858d2e9a48Srsc } 5868d2e9a48Srsc 587eaea18cbSrsc // Look up and return the inode for a path name. 588eaea18cbSrsc // If parent is set, return the inode for the parent 589eaea18cbSrsc // and write the final path element to name, which 590eaea18cbSrsc // should have room for DIRSIZ bytes. 59107090dd7Srsc static struct inode* 592fbf91039Srsc _namei(char *path, int parent, char *name) 5939d3fb671Srtm { 59407090dd7Srsc struct inode *ip, *next; 595f32f3638Srsc uint off; 5969d3fb671Srtm 597ab5c2dbbSrsc if(*path == '/') 59807090dd7Srsc ip = iget(ROOTDEV, 1); 599f32f3638Srsc else 60007090dd7Srsc ip = idup(cp->cwd); 6019d3fb671Srtm 602fbf91039Srsc while((path = skipelem(path, name)) != 0){ 60307090dd7Srsc ilock(ip); 60407090dd7Srsc if(ip->type != T_DIR){ 60507090dd7Srsc iunlockput(ip); 606eaea18cbSrsc return 0; 607eaea18cbSrsc } 608ab5c2dbbSrsc 609e2a620daSrsc if(parent && *path == '\0'){ 610e2a620daSrsc // Stop one level early. 61107090dd7Srsc iunlock(ip); 61207090dd7Srsc return ip; 613ab5c2dbbSrsc } 614ab5c2dbbSrsc 61507090dd7Srsc if((next = dirlookup(ip, name, &off)) == 0){ 61607090dd7Srsc iunlockput(ip); 617eaea18cbSrsc return 0; 618eaea18cbSrsc } 61907090dd7Srsc iunlockput(ip); 62007090dd7Srsc ip = next; 621ab5c2dbbSrsc } 62220365348Srtm if(parent){ 62307090dd7Srsc iput(ip); 6245051da6dSrtm return 0; 62520365348Srtm } 62607090dd7Srsc return ip; 6270633b971Skaashoek } 6289d3fb671Srtm 629