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 // 9*902b13f5Srtm // Disk layout is: superblock, inodes, block not-free 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? 54*902b13f5Srtm bp->data[bi/8] |= m; 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); 84*902b13f5Srtm if((bp->data[bi/8] & m) == 0) 85*902b13f5Srtm panic("freeing free block"); 867d4aef6cSrsc bp->data[bi/8] &= ~m; 87eaea18cbSrsc bwrite(bp); // mark it free on disk 8828d9ef04Skaashoek brelse(bp); 8928d9ef04Skaashoek } 9024111398Skaashoek 91bcca6c6bSrsc // Inodes 92bcca6c6bSrsc // 93bcca6c6bSrsc // The inodes are laid out sequentially on disk immediately after 94bcca6c6bSrsc // the superblock. The kernel keeps a cache of the in-use 95bcca6c6bSrsc // on-disk structures to provide a place for synchronizing access 96bcca6c6bSrsc // to inodes shared between multiple processes. 97bcca6c6bSrsc // 98*902b13f5Srtm // ip->ref counts the number of pointer references to this cached 99bcca6c6bSrsc // inode; references are typically kept in struct file and in cp->cwd. 100bcca6c6bSrsc // When ip->ref falls to zero, the inode is no longer cached. 101bcca6c6bSrsc // It is an error to use an inode without holding a reference to it. 102bcca6c6bSrsc // 103*902b13f5Srtm // Inodes can be locked with I_BUSY (like bufs and B_BUSY). 104eaea18cbSrsc // Processes are only allowed to read and write inode 105eaea18cbSrsc // metadata and contents when holding the inode's lock. 106*902b13f5Srtm // Because inode locks are held during disk accesses, 107*902b13f5Srtm // they are implemented using a flag rather than with 108*902b13f5Srtm // spin locks. Callers are responsible for locking 109eaea18cbSrsc // inodes before passing them to routines in this file; leaving 110eaea18cbSrsc // this responsibility with the caller makes it possible for them 111eaea18cbSrsc // to create arbitrarily-sized atomic operations. 112eaea18cbSrsc // 113eaea18cbSrsc // To give maximum control over locking to the callers, 114eaea18cbSrsc // the routines in this file that return inode pointers 115eaea18cbSrsc // return pointers to *unlocked* inodes. It is the callers' 116*902b13f5Srtm // responsibility to lock them before using them. A non-zero 117*902b13f5Srtm // ip->ref keeps these unlocked inodes in the cache. 118bcca6c6bSrsc 119bcca6c6bSrsc struct { 120bcca6c6bSrsc struct spinlock lock; 121bcca6c6bSrsc struct inode inode[NINODE]; 122bcca6c6bSrsc } icache; 123bcca6c6bSrsc 124bcca6c6bSrsc void 125bcca6c6bSrsc iinit(void) 126bcca6c6bSrsc { 127bcca6c6bSrsc initlock(&icache.lock, "icache.lock"); 128bcca6c6bSrsc } 129bcca6c6bSrsc 130f5527388Srsc // Find the inode with number inum on device dev 131eaea18cbSrsc // and return the in-memory copy. h 132eaea18cbSrsc static struct uinode* 13311a9947fSrtm iget(uint dev, uint inum) 13411a9947fSrtm { 135bcca6c6bSrsc struct inode *ip, *empty; 13611a9947fSrtm 137bcca6c6bSrsc acquire(&icache.lock); 13811a9947fSrtm 139bcca6c6bSrsc // Try for cached inode. 140bcca6c6bSrsc empty = 0; 141bcca6c6bSrsc for(ip = &icache.inode[0]; ip < &icache.inode[NINODE]; ip++){ 1420d6bbd31Srsc if(ip->ref > 0 && ip->dev == dev && ip->inum == inum){ 1430d6bbd31Srsc ip->ref++; 144bcca6c6bSrsc release(&icache.lock); 145eaea18cbSrsc return (struct uinode*)ip; 14611a9947fSrtm } 147bcca6c6bSrsc if(empty == 0 && ip->ref == 0) // Remember empty slot. 148bcca6c6bSrsc empty = ip; 14911a9947fSrtm } 15011a9947fSrtm 151bcca6c6bSrsc // Allocate fresh inode. 152bcca6c6bSrsc if(empty == 0) 15332eea766Srsc panic("iget: no inodes"); 15411a9947fSrtm 155bcca6c6bSrsc ip = empty; 156bcca6c6bSrsc ip->dev = dev; 157bcca6c6bSrsc ip->inum = inum; 158bcca6c6bSrsc ip->ref = 1; 159f32f3638Srsc ip->flags = 0; 160bcca6c6bSrsc release(&icache.lock); 16111a9947fSrtm 162eaea18cbSrsc return (struct uinode*)ip; 163f32f3638Srsc } 164f32f3638Srsc 165eaea18cbSrsc // Increment reference count for ip. 166eaea18cbSrsc // Returns ip to enable ip = idup(ip1) idiom. 167eaea18cbSrsc struct uinode* 168eaea18cbSrsc idup(struct uinode *uip) 169f32f3638Srsc { 170f32f3638Srsc struct inode *ip; 171eaea18cbSrsc 172eaea18cbSrsc ip = (struct inode*)uip; 173eaea18cbSrsc acquire(&icache.lock); 174eaea18cbSrsc ip->ref++; 175eaea18cbSrsc release(&icache.lock); 176eaea18cbSrsc return uip; 177f32f3638Srsc } 178f32f3638Srsc 179f32f3638Srsc // Lock the given inode. 180eaea18cbSrsc struct inode* 181eaea18cbSrsc ilock(struct uinode *uip) 182f32f3638Srsc { 183f32f3638Srsc struct buf *bp; 184f32f3638Srsc struct dinode *dip; 185eaea18cbSrsc struct inode *ip; 186eaea18cbSrsc 187eaea18cbSrsc ip = (struct inode*)uip; 188eaea18cbSrsc if(ip == 0) 189eaea18cbSrsc return 0; 190f32f3638Srsc 191f32f3638Srsc if(ip->ref < 1) 192eaea18cbSrsc panic("ilock: no refs"); 193f32f3638Srsc 194f32f3638Srsc acquire(&icache.lock); 195f32f3638Srsc while(ip->flags & I_BUSY) 196f32f3638Srsc sleep(ip, &icache.lock); 197f32f3638Srsc ip->flags |= I_BUSY; 198f32f3638Srsc release(&icache.lock); 199f32f3638Srsc 200f32f3638Srsc if(!(ip->flags & I_VALID)){ 201f32f3638Srsc bp = bread(ip->dev, IBLOCK(ip->inum)); 202f32f3638Srsc dip = &((struct dinode*)(bp->data))[ip->inum % IPB]; 203bcca6c6bSrsc ip->type = dip->type; 204bcca6c6bSrsc ip->major = dip->major; 205bcca6c6bSrsc ip->minor = dip->minor; 206bcca6c6bSrsc ip->nlink = dip->nlink; 207bcca6c6bSrsc ip->size = dip->size; 208bcca6c6bSrsc memmove(ip->addrs, dip->addrs, sizeof(ip->addrs)); 20911a9947fSrtm brelse(bp); 210f32f3638Srsc ip->flags |= I_VALID; 211eaea18cbSrsc if(ip->type == 0) 212eaea18cbSrsc panic("ilock: no type"); 21311a9947fSrtm } 214eaea18cbSrsc return ip; 215bcca6c6bSrsc } 216bcca6c6bSrsc 217bcca6c6bSrsc // Unlock the given inode. 218eaea18cbSrsc struct uinode* 219bcca6c6bSrsc iunlock(struct inode *ip) 220bcca6c6bSrsc { 221eaea18cbSrsc if(ip == 0) 222eaea18cbSrsc return 0; 223eaea18cbSrsc 224f32f3638Srsc if(!(ip->flags & I_BUSY) || ip->ref < 1) 225bcca6c6bSrsc panic("iunlock"); 226bcca6c6bSrsc 227bcca6c6bSrsc acquire(&icache.lock); 228f32f3638Srsc ip->flags &= ~I_BUSY; 229bcca6c6bSrsc wakeup(ip); 230bcca6c6bSrsc release(&icache.lock); 231eaea18cbSrsc return (struct uinode*)ip; 232bcca6c6bSrsc } 233bcca6c6bSrsc 234f32f3638Srsc // Caller holds reference to unlocked ip. Drop reference. 235bcca6c6bSrsc void 236eaea18cbSrsc iput(struct uinode *uip) 237bcca6c6bSrsc { 238eaea18cbSrsc struct inode *ip; 239eaea18cbSrsc 240eaea18cbSrsc ip = (struct inode*)uip; 241f32f3638Srsc acquire(&icache.lock); 242f32f3638Srsc if(ip->ref == 1 && (ip->flags & I_VALID) && ip->nlink == 0) { 243f32f3638Srsc // inode is no longer used: truncate and free inode. 244f32f3638Srsc if(ip->flags & I_BUSY) 245eaea18cbSrsc panic("iput busy"); 246f32f3638Srsc ip->flags |= I_BUSY; 247f32f3638Srsc release(&icache.lock); 248f32f3638Srsc // XXX convince rsc that no one will come find this inode. 249f32f3638Srsc itrunc(ip); 250f32f3638Srsc ip->type = 0; 251f32f3638Srsc iupdate(ip); 252f32f3638Srsc acquire(&icache.lock); 253f32f3638Srsc ip->flags &= ~I_BUSY; 254f32f3638Srsc } 255f32f3638Srsc ip->ref--; 256f32f3638Srsc release(&icache.lock); 257bcca6c6bSrsc } 258bcca6c6bSrsc 259bcca6c6bSrsc // Allocate a new inode with the given type on device dev. 260eaea18cbSrsc struct uinode* 261e8d11c2eSkaashoek ialloc(uint dev, short type) 262e8d11c2eSkaashoek { 263f32f3638Srsc int inum, ninodes; 264f32f3638Srsc struct buf *bp; 2657d4aef6cSrsc struct dinode *dip; 266e8d11c2eSkaashoek struct superblock *sb; 267e8d11c2eSkaashoek 268e8d11c2eSkaashoek bp = bread(dev, 1); 26924111398Skaashoek sb = (struct superblock*)bp->data; 270e8d11c2eSkaashoek ninodes = sb->ninodes; 271e8d11c2eSkaashoek brelse(bp); 272e8d11c2eSkaashoek 273e8d11c2eSkaashoek for(inum = 1; inum < ninodes; inum++) { // loop over inode blocks 27424111398Skaashoek bp = bread(dev, IBLOCK(inum)); 275e8d11c2eSkaashoek dip = &((struct dinode*)(bp->data))[inum % IPB]; 276e8d11c2eSkaashoek if(dip->type == 0) { // a free inode 2772aa4c3bcSrtm memset(dip, 0, sizeof(*dip)); 278e8d11c2eSkaashoek dip->type = type; 279eaea18cbSrsc bwrite(bp); // mark it allocated on the disk 280e8d11c2eSkaashoek brelse(bp); 281f32f3638Srsc return iget(dev, inum); 282e8d11c2eSkaashoek } 28395c07f82Srsc brelse(bp); 28495c07f82Srsc } 28595c07f82Srsc panic("ialloc: no inodes"); 28695c07f82Srsc } 287e8d11c2eSkaashoek 288bcca6c6bSrsc // Copy inode, which has changed, from memory to disk. 289eaea18cbSrsc void 290bcca6c6bSrsc iupdate(struct inode *ip) 291bcca6c6bSrsc { 292bcca6c6bSrsc struct buf *bp; 293bcca6c6bSrsc struct dinode *dip; 294bcca6c6bSrsc 295bcca6c6bSrsc bp = bread(ip->dev, IBLOCK(ip->inum)); 296bcca6c6bSrsc dip = &((struct dinode*)(bp->data))[ip->inum % IPB]; 297bcca6c6bSrsc dip->type = ip->type; 298bcca6c6bSrsc dip->major = ip->major; 299bcca6c6bSrsc dip->minor = ip->minor; 300bcca6c6bSrsc dip->nlink = ip->nlink; 301bcca6c6bSrsc dip->size = ip->size; 302bcca6c6bSrsc memmove(dip->addrs, ip->addrs, sizeof(ip->addrs)); 303eaea18cbSrsc bwrite(bp); 304bcca6c6bSrsc brelse(bp); 305bcca6c6bSrsc } 306bcca6c6bSrsc 307bcca6c6bSrsc // Inode contents 308bcca6c6bSrsc // 309bcca6c6bSrsc // The contents (data) associated with each inode is stored 310bcca6c6bSrsc // in a sequence of blocks on the disk. The first NDIRECT blocks 311bcca6c6bSrsc // are stored in ip->addrs[]. The next NINDIRECT blocks are 312bcca6c6bSrsc // listed in the block ip->addrs[INDIRECT]. 3139d3fb671Srtm 314bb207a1dSrsc // Return the disk block address of the nth block in inode ip. 315eaea18cbSrsc // If there is no such block, alloc controls whether one is allocated. 316eaea18cbSrsc static uint 317bcca6c6bSrsc bmap(struct inode *ip, uint bn, int alloc) 31822bac2cbSkaashoek { 319bcca6c6bSrsc uint addr, *a; 320bcca6c6bSrsc struct buf *bp; 32122bac2cbSkaashoek 322ea2909b6Skaashoek if(bn < NDIRECT) { 323bcca6c6bSrsc if((addr = ip->addrs[bn]) == 0) { 324bcca6c6bSrsc if(!alloc) 325bcca6c6bSrsc return -1; 326bcca6c6bSrsc ip->addrs[bn] = addr = balloc(ip->dev); 327ea2909b6Skaashoek } 328bcca6c6bSrsc return addr; 329bcca6c6bSrsc } 330bcca6c6bSrsc bn -= NDIRECT; 331bcca6c6bSrsc 332bcca6c6bSrsc if(bn < NINDIRECT) { 333bcca6c6bSrsc // Load indirect block, allocating if necessary. 334bcca6c6bSrsc if((addr = ip->addrs[INDIRECT]) == 0) { 335bcca6c6bSrsc if(!alloc) 336bcca6c6bSrsc return -1; 337bcca6c6bSrsc ip->addrs[INDIRECT] = addr = balloc(ip->dev); 338bcca6c6bSrsc } 339bcca6c6bSrsc bp = bread(ip->dev, addr); 340bcca6c6bSrsc a = (uint*)bp->data; 341bcca6c6bSrsc 342bcca6c6bSrsc if((addr = a[bn]) == 0) { 343bcca6c6bSrsc if(!alloc) { 344bcca6c6bSrsc brelse(bp); 345bcca6c6bSrsc return -1; 346bcca6c6bSrsc } 347bcca6c6bSrsc a[bn] = addr = balloc(ip->dev); 348eaea18cbSrsc bwrite(bp); 349bcca6c6bSrsc } 350bcca6c6bSrsc brelse(bp); 351bcca6c6bSrsc return addr; 35222bac2cbSkaashoek } 35322bac2cbSkaashoek 354bcca6c6bSrsc panic("bmap: out of range"); 355bcca6c6bSrsc } 356bcca6c6bSrsc 357eaea18cbSrsc // PAGEBREAK: 30 358bcca6c6bSrsc // Truncate inode (discard contents). 359fbf91039Srsc static void 3602aa4c3bcSrtm itrunc(struct inode *ip) 36122bac2cbSkaashoek { 362ea2909b6Skaashoek int i, j; 363bcca6c6bSrsc struct buf *bp; 3647d4aef6cSrsc uint *a; 36522bac2cbSkaashoek 366bcca6c6bSrsc for(i = 0; i < NDIRECT; i++) { 367bcca6c6bSrsc if(ip->addrs[i]) { 36822bac2cbSkaashoek bfree(ip->dev, ip->addrs[i]); 36922bac2cbSkaashoek ip->addrs[i] = 0; 37022bac2cbSkaashoek } 37122bac2cbSkaashoek } 372bcca6c6bSrsc 373bcca6c6bSrsc if(ip->addrs[INDIRECT]) { 374bcca6c6bSrsc bp = bread(ip->dev, ip->addrs[INDIRECT]); 375bcca6c6bSrsc a = (uint*)bp->data; 376bcca6c6bSrsc for(j = 0; j < NINDIRECT; j++) { 377bcca6c6bSrsc if(a[j]) 378bcca6c6bSrsc bfree(ip->dev, a[j]); 379bcca6c6bSrsc } 380bcca6c6bSrsc brelse(bp); 381bcca6c6bSrsc ip->addrs[INDIRECT] = 0; 382bcca6c6bSrsc } 383bcca6c6bSrsc 38422bac2cbSkaashoek ip->size = 0; 38522bac2cbSkaashoek iupdate(ip); 38622bac2cbSkaashoek } 38722bac2cbSkaashoek 388bb207a1dSrsc // Copy stat information from inode. 389e958c538Skaashoek void 3901f544842Skaashoek stati(struct inode *ip, struct stat *st) 3911f544842Skaashoek { 3921dca3afbSrsc st->dev = ip->dev; 3931dca3afbSrsc st->ino = ip->inum; 3941dca3afbSrsc st->type = ip->type; 3951dca3afbSrsc st->nlink = ip->nlink; 3961dca3afbSrsc st->size = ip->size; 3971f544842Skaashoek } 3981f544842Skaashoek 399eaea18cbSrsc //PAGEBREAK! 400bb207a1dSrsc // Read data from inode. 401c59361f1Srtm int 40217a85657Srtm readi(struct inode *ip, char *dst, uint off, uint n) 403c59361f1Srtm { 404bcca6c6bSrsc uint tot, m; 405c59361f1Srtm struct buf *bp; 406c59361f1Srtm 407939f9edeSkaashoek if(ip->type == T_DEV) { 4081dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].read) 409939f9edeSkaashoek return -1; 4101dca3afbSrsc return devsw[ip->major].read(ip->minor, dst, n); 411939f9edeSkaashoek } 412939f9edeSkaashoek 413bcca6c6bSrsc if(off + n < off) 414bcca6c6bSrsc return -1; 415bcca6c6bSrsc if(off + n > ip->size) 416bcca6c6bSrsc n = ip->size - off; 417bcca6c6bSrsc 418bcca6c6bSrsc for(tot=0; tot<n; tot+=m, off+=m, dst+=m) { 419bcca6c6bSrsc bp = bread(ip->dev, bmap(ip, off/BSIZE, 0)); 420bcca6c6bSrsc m = min(n - tot, BSIZE - off%BSIZE); 421bcca6c6bSrsc memmove(dst, bp->data + off%BSIZE, m); 422c59361f1Srtm brelse(bp); 423c59361f1Srtm } 424bcca6c6bSrsc return n; 425ea2909b6Skaashoek } 426ea2909b6Skaashoek 427eaea18cbSrsc // PAGEBREAK! 428bb207a1dSrsc // Write data to inode. 429ea2909b6Skaashoek int 430bcca6c6bSrsc writei(struct inode *ip, char *src, uint off, uint n) 4316fa5ffb5Skaashoek { 432bcca6c6bSrsc uint tot, m; 4337d4aef6cSrsc struct buf *bp; 4347d4aef6cSrsc 4356fa5ffb5Skaashoek if(ip->type == T_DEV) { 4361dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].write) 437939f9edeSkaashoek return -1; 438bcca6c6bSrsc return devsw[ip->major].write(ip->minor, src, n); 4397d4aef6cSrsc } 4407d4aef6cSrsc 441bcca6c6bSrsc if(off + n < off) 442bcca6c6bSrsc return -1; 443bcca6c6bSrsc if(off + n > MAXFILE*BSIZE) 444bcca6c6bSrsc n = MAXFILE*BSIZE - off; 445bcca6c6bSrsc 446bcca6c6bSrsc for(tot=0; tot<n; tot+=m, off+=m, src+=m) { 447bcca6c6bSrsc bp = bread(ip->dev, bmap(ip, off/BSIZE, 1)); 448bcca6c6bSrsc m = min(n - tot, BSIZE - off%BSIZE); 449bcca6c6bSrsc memmove(bp->data + off%BSIZE, src, m); 450eaea18cbSrsc bwrite(bp); 45128d9ef04Skaashoek brelse(bp); 45228d9ef04Skaashoek } 453bcca6c6bSrsc 454bcca6c6bSrsc if(n > 0 && off > ip->size) { 45548b82470Srsc ip->size = off; 45628d9ef04Skaashoek iupdate(ip); 45728d9ef04Skaashoek } 458bcca6c6bSrsc return n; 4596fa5ffb5Skaashoek } 4606fa5ffb5Skaashoek 461eaea18cbSrsc //PAGEBREAK! 462bcca6c6bSrsc // Directories 463bcca6c6bSrsc 464eaea18cbSrsc int 465fbf91039Srsc namecmp(const char *s, const char *t) 466fbf91039Srsc { 467fbf91039Srsc int i; 468fbf91039Srsc 469fbf91039Srsc for(i=0; i<DIRSIZ; i++){ 470fbf91039Srsc if(s[i] != t[i]) 471fbf91039Srsc return s[i] - t[i]; 472fbf91039Srsc if(s[i] == 0) 473fbf91039Srsc break; 474fbf91039Srsc } 475fbf91039Srsc return 0; 476fbf91039Srsc } 477fbf91039Srsc 478bcca6c6bSrsc // Look for a directory entry in a directory. 479eaea18cbSrsc // If found, set *poff to byte offset of entry. 48020365348Srtm // Caller must have already locked dp. 481eaea18cbSrsc struct uinode* 482fbf91039Srsc dirlookup(struct inode *dp, char *name, uint *poff) 483bcca6c6bSrsc { 484f32f3638Srsc uint off, inum; 485bcca6c6bSrsc struct buf *bp; 486bcca6c6bSrsc struct dirent *de; 487bcca6c6bSrsc 488bcca6c6bSrsc if(dp->type != T_DIR) 48920365348Srtm panic("dirlookup not DIR"); 490bcca6c6bSrsc 491bcca6c6bSrsc for(off = 0; off < dp->size; off += BSIZE){ 492bcca6c6bSrsc bp = bread(dp->dev, bmap(dp, off / BSIZE, 0)); 493bcca6c6bSrsc for(de = (struct dirent*) bp->data; 494bcca6c6bSrsc de < (struct dirent*) (bp->data + BSIZE); 495bcca6c6bSrsc de++){ 496bcca6c6bSrsc if(de->inum == 0) 497bcca6c6bSrsc continue; 498fbf91039Srsc if(namecmp(name, de->name) == 0){ 499bcca6c6bSrsc // entry matches path element 500e2a620daSrsc if(poff) 501bcca6c6bSrsc *poff = off + (uchar*)de - bp->data; 502f32f3638Srsc inum = de->inum; 503bcca6c6bSrsc brelse(bp); 504f32f3638Srsc return iget(dp->dev, inum); 505f32f3638Srsc } 506f32f3638Srsc } 507f32f3638Srsc brelse(bp); 508f32f3638Srsc } 509bcca6c6bSrsc return 0; 510bcca6c6bSrsc } 511bcca6c6bSrsc 512eaea18cbSrsc // Copy one name to another. 513eaea18cbSrsc static void 514eaea18cbSrsc namecpy(char *s, const char *t) 515eaea18cbSrsc { 516eaea18cbSrsc int i; 517eaea18cbSrsc 518eaea18cbSrsc for(i=0; i<DIRSIZ && t[i]; i++) 519eaea18cbSrsc s[i] = t[i]; 520eaea18cbSrsc for(; i<DIRSIZ; i++) 521eaea18cbSrsc s[i] = 0; 522eaea18cbSrsc } 523eaea18cbSrsc 524bcca6c6bSrsc // Write a new directory entry (name, ino) into the directory dp. 525eaea18cbSrsc int 526fbf91039Srsc dirlink(struct inode *dp, char *name, uint ino) 527bcca6c6bSrsc { 528e2a620daSrsc int off; 529bcca6c6bSrsc struct dirent de; 530f0721f1bSrsc struct uinode *ipu; 531f32f3638Srsc 532eaea18cbSrsc // Check that name is not present. 533f0721f1bSrsc if((ipu = dirlookup(dp, name, 0)) != 0){ 534f0721f1bSrsc iput(ipu); 535f32f3638Srsc return -1; 536f32f3638Srsc } 537bcca6c6bSrsc 538bcca6c6bSrsc // Look for an empty dirent. 539bcca6c6bSrsc for(off = 0; off < dp->size; off += sizeof(de)){ 540bcca6c6bSrsc if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 541bcca6c6bSrsc panic("dirwrite read"); 542bcca6c6bSrsc if(de.inum == 0) 543bcca6c6bSrsc break; 544bcca6c6bSrsc } 545bcca6c6bSrsc 546fbf91039Srsc namecpy(de.name, name); 547bcca6c6bSrsc de.inum = ino; 548bcca6c6bSrsc if(writei(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 549bcca6c6bSrsc panic("dirwrite"); 550f32f3638Srsc 551f32f3638Srsc return 0; 552bcca6c6bSrsc } 553bcca6c6bSrsc 554bcca6c6bSrsc // Paths 555bcca6c6bSrsc 556eaea18cbSrsc // Copy the next path element from path into name. 557eaea18cbSrsc // Return a pointer to the element following the copied one. 558eaea18cbSrsc // The returned path has no leading slashes, 559eaea18cbSrsc // so the caller can check *path=='\0' to see if the name is the last one. 560eaea18cbSrsc // If no name to remove, return 0. 561ab5c2dbbSrsc // 562ab5c2dbbSrsc // Examples: 563eaea18cbSrsc // skipelem("a/bb/c", name) = "bb/c", setting name = "a" 56420365348Srtm // skipelem("///a/bb", name) = "bb", setting name="a" 565eaea18cbSrsc // skipelem("", name) = skipelem("////", name) = 0 566ab5c2dbbSrsc // 567ab5c2dbbSrsc static char* 568fbf91039Srsc skipelem(char *path, char *name) 569ab5c2dbbSrsc { 570fbf91039Srsc char *s; 571fbf91039Srsc int len; 572fbf91039Srsc 573ab5c2dbbSrsc while(*path == '/') 574ab5c2dbbSrsc path++; 575ab5c2dbbSrsc if(*path == 0) 576ab5c2dbbSrsc return 0; 577fbf91039Srsc s = path; 578ab5c2dbbSrsc while(*path != '/' && *path != 0) 579ab5c2dbbSrsc path++; 580fbf91039Srsc len = path - s; 581fbf91039Srsc if(len >= DIRSIZ) 582fbf91039Srsc memmove(name, s, DIRSIZ); 583fbf91039Srsc else{ 584fbf91039Srsc memmove(name, s, len); 585fbf91039Srsc name[len] = 0; 586fbf91039Srsc } 587ab5c2dbbSrsc while(*path == '/') 588ab5c2dbbSrsc path++; 589ab5c2dbbSrsc return path; 590ab5c2dbbSrsc } 591ab5c2dbbSrsc 592eaea18cbSrsc // Look up and return the inode for a path name. 593eaea18cbSrsc // If parent is set, return the inode for the parent 594eaea18cbSrsc // and write the final path element to name, which 595eaea18cbSrsc // should have room for DIRSIZ bytes. 596eaea18cbSrsc static struct uinode* 597fbf91039Srsc _namei(char *path, int parent, char *name) 5989d3fb671Srtm { 599f0721f1bSrsc struct uinode *dpu, *ipu; 600f0721f1bSrsc struct inode *dp; 601f32f3638Srsc uint off; 6029d3fb671Srtm 603ab5c2dbbSrsc if(*path == '/') 604f0721f1bSrsc dpu = iget(ROOTDEV, 1); 605f32f3638Srsc else 606f0721f1bSrsc dpu = idup(cp->cwd); 6079d3fb671Srtm 608fbf91039Srsc while((path = skipelem(path, name)) != 0){ 609f0721f1bSrsc dp = ilock(dpu); 610f0721f1bSrsc if(dp->type != T_DIR){ 611f0721f1bSrsc iput(iunlock(dp)); 612eaea18cbSrsc return 0; 613eaea18cbSrsc } 614ab5c2dbbSrsc 615e2a620daSrsc if(parent && *path == '\0'){ 616e2a620daSrsc // Stop one level early. 617f0721f1bSrsc iunlock(dp); 618f0721f1bSrsc return dpu; 619ab5c2dbbSrsc } 620ab5c2dbbSrsc 621f0721f1bSrsc if((ipu = dirlookup(dp, name, &off)) == 0){ 622f0721f1bSrsc iput(iunlock(dp)); 623eaea18cbSrsc return 0; 624eaea18cbSrsc } 625f0721f1bSrsc iput(iunlock(dp)); 626f0721f1bSrsc dpu = ipu; 627ab5c2dbbSrsc } 62820365348Srtm if(parent){ 62920365348Srtm iput(dpu); 6305051da6dSrtm return 0; 63120365348Srtm } 632f0721f1bSrsc return dpu; 6330633b971Skaashoek } 6349d3fb671Srtm 635eaea18cbSrsc struct uinode* 636e2a620daSrsc namei(char *path) 637e2a620daSrsc { 638fbf91039Srsc char name[DIRSIZ]; 639fbf91039Srsc return _namei(path, 0, name); 640e2a620daSrsc } 641e2a620daSrsc 642eaea18cbSrsc struct uinode* 643fbf91039Srsc nameiparent(char *path, char *name) 644e2a620daSrsc { 645fbf91039Srsc return _namei(path, 1, name); 646e2a620daSrsc } 647