1bcca6c6bSrsc // File system implementation. 2bcca6c6bSrsc // 3bcca6c6bSrsc // Four layers: 4bcca6c6bSrsc // + Blocks: allocator for raw disk blocks. 5bcca6c6bSrsc // + Files: inode allocator, reading, writing, metadata. 6bcca6c6bSrsc // + Directories: inode with special contents (list of other inodes!) 7bcca6c6bSrsc // + Names: paths like /usr/rtm/xv6/fs.c for convenient naming. 8bcca6c6bSrsc // 9bcca6c6bSrsc // Disk layout is: superblock, inodes, disk bitmap, data blocks. 10eaea18cbSrsc // 11eaea18cbSrsc // This file contains the low-level file system manipulation 12eaea18cbSrsc // routines. The (higher-level) system call implementations 13eaea18cbSrsc // are in sysfile.c. 14bcca6c6bSrsc 1511a9947fSrtm #include "types.h" 161f544842Skaashoek #include "stat.h" 1711a9947fSrtm #include "param.h" 1811a9947fSrtm #include "x86.h" 1911a9947fSrtm #include "mmu.h" 2011a9947fSrtm #include "proc.h" 2111a9947fSrtm #include "defs.h" 2211a9947fSrtm #include "spinlock.h" 2311a9947fSrtm #include "buf.h" 2411a9947fSrtm #include "fs.h" 2511a9947fSrtm #include "fsvar.h" 266fa5ffb5Skaashoek #include "dev.h" 2711a9947fSrtm 28bcca6c6bSrsc #define min(a, b) ((a) < (b) ? (a) : (b)) 29fbf91039Srsc static void itrunc(struct inode*); 3011a9947fSrtm 31bcca6c6bSrsc // Blocks. 325be0039cSrtm 33f5527388Srsc // Allocate a disk block. 3424111398Skaashoek static uint 3524111398Skaashoek balloc(uint dev) 3624111398Skaashoek { 377d4aef6cSrsc int b, bi, m, ninodes, size; 3824111398Skaashoek struct buf *bp; 3924111398Skaashoek struct superblock *sb; 4024111398Skaashoek 4124111398Skaashoek bp = bread(dev, 1); 4224111398Skaashoek sb = (struct superblock*) bp->data; 4324111398Skaashoek size = sb->size; 4424111398Skaashoek ninodes = sb->ninodes; 4524111398Skaashoek 4624111398Skaashoek for(b = 0; b < size; b++) { 4724111398Skaashoek if(b % BPB == 0) { 4824111398Skaashoek brelse(bp); 4924111398Skaashoek bp = bread(dev, BBLOCK(b, ninodes)); 5024111398Skaashoek } 5124111398Skaashoek bi = b % BPB; 5224111398Skaashoek m = 0x1 << (bi % 8); 5324111398Skaashoek if((bp->data[bi/8] & m) == 0) { // is block free? 5424111398Skaashoek bp->data[bi/8] |= 0x1 << (bi % 8); 55eaea18cbSrsc bwrite(bp); // mark it allocated on disk 5628d9ef04Skaashoek brelse(bp); 5724111398Skaashoek return b; 5824111398Skaashoek } 597d4aef6cSrsc } 607d4aef6cSrsc panic("balloc: out of blocks"); 617d4aef6cSrsc } 6224111398Skaashoek 63bb207a1dSrsc // Free a disk block. 6428d9ef04Skaashoek static void 6528d9ef04Skaashoek bfree(int dev, uint b) 6628d9ef04Skaashoek { 6728d9ef04Skaashoek struct buf *bp; 6828d9ef04Skaashoek struct superblock *sb; 697d4aef6cSrsc int bi, m, ninodes; 7028d9ef04Skaashoek 7128d9ef04Skaashoek bp = bread(dev, 1); 7228d9ef04Skaashoek sb = (struct superblock*) bp->data; 7328d9ef04Skaashoek ninodes = sb->ninodes; 7428d9ef04Skaashoek brelse(bp); 7528d9ef04Skaashoek 76c372e8dcSkaashoek bp = bread(dev, b); 77c372e8dcSkaashoek memset(bp->data, 0, BSIZE); 78eaea18cbSrsc bwrite(bp); 79c372e8dcSkaashoek brelse(bp); 80c372e8dcSkaashoek 8128d9ef04Skaashoek bp = bread(dev, BBLOCK(b, ninodes)); 8228d9ef04Skaashoek bi = b % BPB; 837d4aef6cSrsc m = 0x1 << (bi % 8); 847d4aef6cSrsc bp->data[bi/8] &= ~m; 85eaea18cbSrsc bwrite(bp); // mark it free on disk 8628d9ef04Skaashoek brelse(bp); 8728d9ef04Skaashoek } 8824111398Skaashoek 89bcca6c6bSrsc // Inodes 90bcca6c6bSrsc // 91bcca6c6bSrsc // The inodes are laid out sequentially on disk immediately after 92bcca6c6bSrsc // the superblock. The kernel keeps a cache of the in-use 93bcca6c6bSrsc // on-disk structures to provide a place for synchronizing access 94bcca6c6bSrsc // to inodes shared between multiple processes. 95bcca6c6bSrsc // 96bcca6c6bSrsc // ip->ref counts the number of references to this 97bcca6c6bSrsc // inode; references are typically kept in struct file and in cp->cwd. 98bcca6c6bSrsc // When ip->ref falls to zero, the inode is no longer cached. 99bcca6c6bSrsc // It is an error to use an inode without holding a reference to it. 100bcca6c6bSrsc // 101bcca6c6bSrsc // Inodes can be marked busy, just like bufs, meaning 102eaea18cbSrsc // that some process has exclusive use of the inode. 103eaea18cbSrsc // Processes are only allowed to read and write inode 104eaea18cbSrsc // metadata and contents when holding the inode's lock. 105eaea18cbSrsc // Because inodes locks are held during disk accesses, 106eaea18cbSrsc // they are implemented using a flag, as in the buffer cache, 107eaea18cbSrsc // not using spin locks. Callers are responsible for locking 108eaea18cbSrsc // inodes before passing them to routines in this file; leaving 109eaea18cbSrsc // this responsibility with the caller makes it possible for them 110eaea18cbSrsc // to create arbitrarily-sized atomic operations. 111eaea18cbSrsc // 112eaea18cbSrsc // To give maximum control over locking to the callers, 113eaea18cbSrsc // the routines in this file that return inode pointers 114eaea18cbSrsc // return pointers to *unlocked* inodes. It is the callers' 115eaea18cbSrsc // responsibility to lock them before using them. 116bcca6c6bSrsc 117bcca6c6bSrsc struct { 118bcca6c6bSrsc struct spinlock lock; 119bcca6c6bSrsc struct inode inode[NINODE]; 120bcca6c6bSrsc } icache; 121bcca6c6bSrsc 122bcca6c6bSrsc void 123bcca6c6bSrsc iinit(void) 124bcca6c6bSrsc { 125bcca6c6bSrsc initlock(&icache.lock, "icache.lock"); 126bcca6c6bSrsc } 127bcca6c6bSrsc 128f5527388Srsc // Find the inode with number inum on device dev 129eaea18cbSrsc // and return the in-memory copy. h 130eaea18cbSrsc static struct uinode* 13111a9947fSrtm iget(uint dev, uint inum) 13211a9947fSrtm { 133bcca6c6bSrsc struct inode *ip, *empty; 13411a9947fSrtm 135bcca6c6bSrsc acquire(&icache.lock); 13611a9947fSrtm 137bcca6c6bSrsc // Try for cached inode. 138bcca6c6bSrsc empty = 0; 139bcca6c6bSrsc for(ip = &icache.inode[0]; ip < &icache.inode[NINODE]; ip++){ 1400d6bbd31Srsc if(ip->ref > 0 && ip->dev == dev && ip->inum == inum){ 1410d6bbd31Srsc ip->ref++; 142bcca6c6bSrsc release(&icache.lock); 143eaea18cbSrsc return (struct uinode*)ip; 14411a9947fSrtm } 145bcca6c6bSrsc if(empty == 0 && ip->ref == 0) // Remember empty slot. 146bcca6c6bSrsc empty = ip; 14711a9947fSrtm } 14811a9947fSrtm 149bcca6c6bSrsc // Allocate fresh inode. 150bcca6c6bSrsc if(empty == 0) 15132eea766Srsc panic("iget: no inodes"); 15211a9947fSrtm 153bcca6c6bSrsc ip = empty; 154bcca6c6bSrsc ip->dev = dev; 155bcca6c6bSrsc ip->inum = inum; 156bcca6c6bSrsc ip->ref = 1; 157f32f3638Srsc ip->flags = 0; 158bcca6c6bSrsc release(&icache.lock); 15911a9947fSrtm 160eaea18cbSrsc return (struct uinode*)ip; 161f32f3638Srsc } 162f32f3638Srsc 163eaea18cbSrsc // Increment reference count for ip. 164eaea18cbSrsc // Returns ip to enable ip = idup(ip1) idiom. 165eaea18cbSrsc struct uinode* 166eaea18cbSrsc idup(struct uinode *uip) 167f32f3638Srsc { 168f32f3638Srsc struct inode *ip; 169eaea18cbSrsc 170eaea18cbSrsc ip = (struct inode*)uip; 171eaea18cbSrsc acquire(&icache.lock); 172eaea18cbSrsc ip->ref++; 173eaea18cbSrsc release(&icache.lock); 174eaea18cbSrsc return uip; 175f32f3638Srsc } 176f32f3638Srsc 177f32f3638Srsc // Lock the given inode. 178eaea18cbSrsc struct inode* 179eaea18cbSrsc ilock(struct uinode *uip) 180f32f3638Srsc { 181f32f3638Srsc struct buf *bp; 182f32f3638Srsc struct dinode *dip; 183eaea18cbSrsc struct inode *ip; 184eaea18cbSrsc 185eaea18cbSrsc ip = (struct inode*)uip; 186eaea18cbSrsc if(ip == 0) 187eaea18cbSrsc return 0; 188f32f3638Srsc 189f32f3638Srsc if(ip->ref < 1) 190eaea18cbSrsc panic("ilock: no refs"); 191f32f3638Srsc 192f32f3638Srsc acquire(&icache.lock); 193f32f3638Srsc while(ip->flags & I_BUSY) 194f32f3638Srsc sleep(ip, &icache.lock); 195f32f3638Srsc ip->flags |= I_BUSY; 196f32f3638Srsc release(&icache.lock); 197f32f3638Srsc 198f32f3638Srsc if(!(ip->flags & I_VALID)){ 199f32f3638Srsc bp = bread(ip->dev, IBLOCK(ip->inum)); 200f32f3638Srsc dip = &((struct dinode*)(bp->data))[ip->inum % IPB]; 201bcca6c6bSrsc ip->type = dip->type; 202bcca6c6bSrsc ip->major = dip->major; 203bcca6c6bSrsc ip->minor = dip->minor; 204bcca6c6bSrsc ip->nlink = dip->nlink; 205bcca6c6bSrsc ip->size = dip->size; 206bcca6c6bSrsc memmove(ip->addrs, dip->addrs, sizeof(ip->addrs)); 20711a9947fSrtm brelse(bp); 208f32f3638Srsc ip->flags |= I_VALID; 209eaea18cbSrsc if(ip->type == 0) 210eaea18cbSrsc panic("ilock: no type"); 21111a9947fSrtm } 212eaea18cbSrsc return ip; 213bcca6c6bSrsc } 214bcca6c6bSrsc 215bcca6c6bSrsc // Unlock the given inode. 216eaea18cbSrsc struct uinode* 217bcca6c6bSrsc iunlock(struct inode *ip) 218bcca6c6bSrsc { 219eaea18cbSrsc if(ip == 0) 220eaea18cbSrsc return 0; 221eaea18cbSrsc 222f32f3638Srsc if(!(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); 229eaea18cbSrsc return (struct uinode*)ip; 230bcca6c6bSrsc } 231bcca6c6bSrsc 232f32f3638Srsc // Caller holds reference to unlocked ip. Drop reference. 233bcca6c6bSrsc void 234eaea18cbSrsc iput(struct uinode *uip) 235bcca6c6bSrsc { 236eaea18cbSrsc struct inode *ip; 237eaea18cbSrsc 238eaea18cbSrsc ip = (struct inode*)uip; 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 // XXX convince rsc that no one will come find this inode. 247f32f3638Srsc itrunc(ip); 248f32f3638Srsc ip->type = 0; 249f32f3638Srsc iupdate(ip); 250f32f3638Srsc acquire(&icache.lock); 251f32f3638Srsc ip->flags &= ~I_BUSY; 252f32f3638Srsc } 253f32f3638Srsc ip->ref--; 254f32f3638Srsc release(&icache.lock); 255bcca6c6bSrsc } 256bcca6c6bSrsc 257bcca6c6bSrsc // Allocate a new inode with the given type on device dev. 258eaea18cbSrsc struct uinode* 259e8d11c2eSkaashoek ialloc(uint dev, short type) 260e8d11c2eSkaashoek { 261f32f3638Srsc int inum, ninodes; 262f32f3638Srsc struct buf *bp; 2637d4aef6cSrsc struct dinode *dip; 264e8d11c2eSkaashoek struct superblock *sb; 265e8d11c2eSkaashoek 266e8d11c2eSkaashoek bp = bread(dev, 1); 26724111398Skaashoek sb = (struct superblock*)bp->data; 268e8d11c2eSkaashoek ninodes = sb->ninodes; 269e8d11c2eSkaashoek brelse(bp); 270e8d11c2eSkaashoek 271e8d11c2eSkaashoek for(inum = 1; inum < 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 305bcca6c6bSrsc // Inode contents 306bcca6c6bSrsc // 307bcca6c6bSrsc // The contents (data) associated with each inode is stored 308bcca6c6bSrsc // in a sequence of blocks on the disk. The first NDIRECT blocks 309bcca6c6bSrsc // are stored in ip->addrs[]. The next NINDIRECT blocks are 310bcca6c6bSrsc // listed in the block ip->addrs[INDIRECT]. 3119d3fb671Srtm 312bb207a1dSrsc // Return the disk block address of the nth block in inode ip. 313eaea18cbSrsc // If there is no such block, alloc controls whether one is allocated. 314eaea18cbSrsc static uint 315bcca6c6bSrsc bmap(struct inode *ip, uint bn, int alloc) 31622bac2cbSkaashoek { 317bcca6c6bSrsc uint addr, *a; 318bcca6c6bSrsc struct buf *bp; 31922bac2cbSkaashoek 320ea2909b6Skaashoek if(bn < NDIRECT) { 321bcca6c6bSrsc if((addr = ip->addrs[bn]) == 0) { 322bcca6c6bSrsc if(!alloc) 323bcca6c6bSrsc return -1; 324bcca6c6bSrsc ip->addrs[bn] = addr = balloc(ip->dev); 325ea2909b6Skaashoek } 326bcca6c6bSrsc return addr; 327bcca6c6bSrsc } 328bcca6c6bSrsc bn -= NDIRECT; 329bcca6c6bSrsc 330bcca6c6bSrsc if(bn < NINDIRECT) { 331bcca6c6bSrsc // Load indirect block, allocating if necessary. 332bcca6c6bSrsc if((addr = ip->addrs[INDIRECT]) == 0) { 333bcca6c6bSrsc if(!alloc) 334bcca6c6bSrsc return -1; 335bcca6c6bSrsc ip->addrs[INDIRECT] = addr = balloc(ip->dev); 336bcca6c6bSrsc } 337bcca6c6bSrsc bp = bread(ip->dev, addr); 338bcca6c6bSrsc a = (uint*)bp->data; 339bcca6c6bSrsc 340bcca6c6bSrsc if((addr = a[bn]) == 0) { 341bcca6c6bSrsc if(!alloc) { 342bcca6c6bSrsc brelse(bp); 343bcca6c6bSrsc return -1; 344bcca6c6bSrsc } 345bcca6c6bSrsc a[bn] = addr = balloc(ip->dev); 346eaea18cbSrsc bwrite(bp); 347bcca6c6bSrsc } 348bcca6c6bSrsc brelse(bp); 349bcca6c6bSrsc return addr; 35022bac2cbSkaashoek } 35122bac2cbSkaashoek 352bcca6c6bSrsc panic("bmap: out of range"); 353bcca6c6bSrsc } 354bcca6c6bSrsc 355eaea18cbSrsc // PAGEBREAK: 30 356bcca6c6bSrsc // Truncate inode (discard contents). 357fbf91039Srsc static void 3582aa4c3bcSrtm itrunc(struct inode *ip) 35922bac2cbSkaashoek { 360ea2909b6Skaashoek int i, j; 361bcca6c6bSrsc struct buf *bp; 3627d4aef6cSrsc uint *a; 36322bac2cbSkaashoek 364bcca6c6bSrsc for(i = 0; i < NDIRECT; i++) { 365bcca6c6bSrsc if(ip->addrs[i]) { 36622bac2cbSkaashoek bfree(ip->dev, ip->addrs[i]); 36722bac2cbSkaashoek ip->addrs[i] = 0; 36822bac2cbSkaashoek } 36922bac2cbSkaashoek } 370bcca6c6bSrsc 371bcca6c6bSrsc if(ip->addrs[INDIRECT]) { 372bcca6c6bSrsc bp = bread(ip->dev, ip->addrs[INDIRECT]); 373bcca6c6bSrsc a = (uint*)bp->data; 374bcca6c6bSrsc for(j = 0; j < NINDIRECT; j++) { 375bcca6c6bSrsc if(a[j]) 376bcca6c6bSrsc bfree(ip->dev, a[j]); 377bcca6c6bSrsc } 378bcca6c6bSrsc brelse(bp); 379bcca6c6bSrsc ip->addrs[INDIRECT] = 0; 380bcca6c6bSrsc } 381bcca6c6bSrsc 38222bac2cbSkaashoek ip->size = 0; 38322bac2cbSkaashoek iupdate(ip); 38422bac2cbSkaashoek } 38522bac2cbSkaashoek 386bb207a1dSrsc // Copy stat information from inode. 387e958c538Skaashoek void 3881f544842Skaashoek stati(struct inode *ip, struct stat *st) 3891f544842Skaashoek { 3901dca3afbSrsc st->dev = ip->dev; 3911dca3afbSrsc st->ino = ip->inum; 3921dca3afbSrsc st->type = ip->type; 3931dca3afbSrsc st->nlink = ip->nlink; 3941dca3afbSrsc st->size = ip->size; 3951f544842Skaashoek } 3961f544842Skaashoek 397eaea18cbSrsc //PAGEBREAK! 398bb207a1dSrsc // Read data from inode. 399c59361f1Srtm int 40017a85657Srtm readi(struct inode *ip, char *dst, uint off, uint n) 401c59361f1Srtm { 402bcca6c6bSrsc uint tot, m; 403c59361f1Srtm struct buf *bp; 404c59361f1Srtm 405939f9edeSkaashoek if(ip->type == T_DEV) { 4061dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].read) 407939f9edeSkaashoek return -1; 4081dca3afbSrsc return devsw[ip->major].read(ip->minor, dst, n); 409939f9edeSkaashoek } 410939f9edeSkaashoek 411bcca6c6bSrsc if(off + n < off) 412bcca6c6bSrsc return -1; 413bcca6c6bSrsc if(off + n > ip->size) 414bcca6c6bSrsc n = ip->size - off; 415bcca6c6bSrsc 416bcca6c6bSrsc for(tot=0; tot<n; tot+=m, off+=m, dst+=m) { 417bcca6c6bSrsc bp = bread(ip->dev, bmap(ip, off/BSIZE, 0)); 418bcca6c6bSrsc m = min(n - tot, BSIZE - off%BSIZE); 419bcca6c6bSrsc memmove(dst, bp->data + off%BSIZE, m); 420c59361f1Srtm brelse(bp); 421c59361f1Srtm } 422bcca6c6bSrsc return n; 423ea2909b6Skaashoek } 424ea2909b6Skaashoek 425eaea18cbSrsc // PAGEBREAK! 426bb207a1dSrsc // Write data to inode. 427ea2909b6Skaashoek int 428bcca6c6bSrsc writei(struct inode *ip, char *src, uint off, uint n) 4296fa5ffb5Skaashoek { 430bcca6c6bSrsc uint tot, m; 4317d4aef6cSrsc struct buf *bp; 4327d4aef6cSrsc 4336fa5ffb5Skaashoek if(ip->type == T_DEV) { 4341dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].write) 435939f9edeSkaashoek return -1; 436bcca6c6bSrsc return devsw[ip->major].write(ip->minor, src, n); 4377d4aef6cSrsc } 4387d4aef6cSrsc 439bcca6c6bSrsc if(off + n < off) 440bcca6c6bSrsc return -1; 441bcca6c6bSrsc if(off + n > MAXFILE*BSIZE) 442bcca6c6bSrsc n = MAXFILE*BSIZE - off; 443bcca6c6bSrsc 444bcca6c6bSrsc for(tot=0; tot<n; tot+=m, off+=m, src+=m) { 445bcca6c6bSrsc bp = bread(ip->dev, bmap(ip, off/BSIZE, 1)); 446bcca6c6bSrsc m = min(n - tot, BSIZE - off%BSIZE); 447bcca6c6bSrsc memmove(bp->data + off%BSIZE, src, m); 448eaea18cbSrsc bwrite(bp); 44928d9ef04Skaashoek brelse(bp); 45028d9ef04Skaashoek } 451bcca6c6bSrsc 452bcca6c6bSrsc if(n > 0 && off > ip->size) { 45348b82470Srsc ip->size = off; 45428d9ef04Skaashoek iupdate(ip); 45528d9ef04Skaashoek } 456bcca6c6bSrsc return n; 4576fa5ffb5Skaashoek } 4586fa5ffb5Skaashoek 459eaea18cbSrsc //PAGEBREAK! 460bcca6c6bSrsc // Directories 461bcca6c6bSrsc 462eaea18cbSrsc int 463fbf91039Srsc namecmp(const char *s, const char *t) 464fbf91039Srsc { 465fbf91039Srsc int i; 466fbf91039Srsc 467fbf91039Srsc for(i=0; i<DIRSIZ; i++){ 468fbf91039Srsc if(s[i] != t[i]) 469fbf91039Srsc return s[i] - t[i]; 470fbf91039Srsc if(s[i] == 0) 471fbf91039Srsc break; 472fbf91039Srsc } 473fbf91039Srsc return 0; 474fbf91039Srsc } 475fbf91039Srsc 476bcca6c6bSrsc // Look for a directory entry in a directory. 477eaea18cbSrsc // If found, set *poff to byte offset of entry. 478*20365348Srtm // Caller must have already locked dp. 479eaea18cbSrsc struct uinode* 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) 487*20365348Srtm 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 510eaea18cbSrsc // Copy one name to another. 511eaea18cbSrsc static void 512eaea18cbSrsc namecpy(char *s, const char *t) 513eaea18cbSrsc { 514eaea18cbSrsc int i; 515eaea18cbSrsc 516eaea18cbSrsc for(i=0; i<DIRSIZ && t[i]; i++) 517eaea18cbSrsc s[i] = t[i]; 518eaea18cbSrsc for(; i<DIRSIZ; i++) 519eaea18cbSrsc s[i] = 0; 520eaea18cbSrsc } 521eaea18cbSrsc 522bcca6c6bSrsc // Write a new directory entry (name, ino) into the directory dp. 523eaea18cbSrsc int 524fbf91039Srsc dirlink(struct inode *dp, char *name, uint ino) 525bcca6c6bSrsc { 526e2a620daSrsc int off; 527bcca6c6bSrsc struct dirent de; 528f0721f1bSrsc struct uinode *ipu; 529f32f3638Srsc 530eaea18cbSrsc // Check that name is not present. 531f0721f1bSrsc if((ipu = dirlookup(dp, name, 0)) != 0){ 532f0721f1bSrsc iput(ipu); 533f32f3638Srsc return -1; 534f32f3638Srsc } 535bcca6c6bSrsc 536bcca6c6bSrsc // Look for an empty dirent. 537bcca6c6bSrsc for(off = 0; off < dp->size; off += sizeof(de)){ 538bcca6c6bSrsc if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 539bcca6c6bSrsc panic("dirwrite read"); 540bcca6c6bSrsc if(de.inum == 0) 541bcca6c6bSrsc break; 542bcca6c6bSrsc } 543bcca6c6bSrsc 544fbf91039Srsc namecpy(de.name, name); 545bcca6c6bSrsc de.inum = ino; 546bcca6c6bSrsc if(writei(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 547bcca6c6bSrsc panic("dirwrite"); 548f32f3638Srsc 549f32f3638Srsc return 0; 550bcca6c6bSrsc } 551bcca6c6bSrsc 552bcca6c6bSrsc // Paths 553bcca6c6bSrsc 554eaea18cbSrsc // Copy the next path element from path into name. 555eaea18cbSrsc // Return a pointer to the element following the copied one. 556eaea18cbSrsc // The returned path has no leading slashes, 557eaea18cbSrsc // so the caller can check *path=='\0' to see if the name is the last one. 558eaea18cbSrsc // If no name to remove, return 0. 559ab5c2dbbSrsc // 560ab5c2dbbSrsc // Examples: 561eaea18cbSrsc // skipelem("a/bb/c", name) = "bb/c", setting name = "a" 562*20365348Srtm // skipelem("///a/bb", name) = "bb", setting name="a" 563eaea18cbSrsc // skipelem("", name) = skipelem("////", name) = 0 564ab5c2dbbSrsc // 565ab5c2dbbSrsc static char* 566fbf91039Srsc skipelem(char *path, char *name) 567ab5c2dbbSrsc { 568fbf91039Srsc char *s; 569fbf91039Srsc int len; 570fbf91039Srsc 571ab5c2dbbSrsc while(*path == '/') 572ab5c2dbbSrsc path++; 573ab5c2dbbSrsc if(*path == 0) 574ab5c2dbbSrsc return 0; 575fbf91039Srsc s = path; 576ab5c2dbbSrsc while(*path != '/' && *path != 0) 577ab5c2dbbSrsc path++; 578fbf91039Srsc len = path - s; 579fbf91039Srsc if(len >= DIRSIZ) 580fbf91039Srsc memmove(name, s, DIRSIZ); 581fbf91039Srsc else{ 582fbf91039Srsc memmove(name, s, len); 583fbf91039Srsc name[len] = 0; 584fbf91039Srsc } 585ab5c2dbbSrsc while(*path == '/') 586ab5c2dbbSrsc path++; 587ab5c2dbbSrsc return path; 588ab5c2dbbSrsc } 589ab5c2dbbSrsc 590eaea18cbSrsc // Look up and return the inode for a path name. 591eaea18cbSrsc // If parent is set, return the inode for the parent 592eaea18cbSrsc // and write the final path element to name, which 593eaea18cbSrsc // should have room for DIRSIZ bytes. 594eaea18cbSrsc static struct uinode* 595fbf91039Srsc _namei(char *path, int parent, char *name) 5969d3fb671Srtm { 597f0721f1bSrsc struct uinode *dpu, *ipu; 598f0721f1bSrsc struct inode *dp; 599f32f3638Srsc uint off; 6009d3fb671Srtm 601ab5c2dbbSrsc if(*path == '/') 602f0721f1bSrsc dpu = iget(ROOTDEV, 1); 603f32f3638Srsc else 604f0721f1bSrsc dpu = idup(cp->cwd); 6059d3fb671Srtm 606fbf91039Srsc while((path = skipelem(path, name)) != 0){ 607f0721f1bSrsc dp = ilock(dpu); 608f0721f1bSrsc if(dp->type != T_DIR){ 609f0721f1bSrsc iput(iunlock(dp)); 610eaea18cbSrsc return 0; 611eaea18cbSrsc } 612ab5c2dbbSrsc 613e2a620daSrsc if(parent && *path == '\0'){ 614e2a620daSrsc // Stop one level early. 615f0721f1bSrsc iunlock(dp); 616f0721f1bSrsc return dpu; 617ab5c2dbbSrsc } 618ab5c2dbbSrsc 619f0721f1bSrsc if((ipu = dirlookup(dp, name, &off)) == 0){ 620f0721f1bSrsc iput(iunlock(dp)); 621eaea18cbSrsc return 0; 622eaea18cbSrsc } 623f0721f1bSrsc iput(iunlock(dp)); 624f0721f1bSrsc dpu = ipu; 625ab5c2dbbSrsc } 626*20365348Srtm if(parent){ 627*20365348Srtm iput(dpu); 6285051da6dSrtm return 0; 629*20365348Srtm } 630f0721f1bSrsc return dpu; 6310633b971Skaashoek } 6329d3fb671Srtm 633eaea18cbSrsc struct uinode* 634e2a620daSrsc namei(char *path) 635e2a620daSrsc { 636fbf91039Srsc char name[DIRSIZ]; 637fbf91039Srsc return _namei(path, 0, name); 638e2a620daSrsc } 639e2a620daSrsc 640eaea18cbSrsc struct uinode* 641fbf91039Srsc nameiparent(char *path, char *name) 642e2a620daSrsc { 643fbf91039Srsc return _namei(path, 1, name); 644e2a620daSrsc } 645