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. 10bcca6c6bSrsc 11bcca6c6bSrsc // TODO: Check locking! 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)) 27*fbf91039Srsc static void itrunc(struct inode*); 28*fbf91039Srsc static void iupdate(struct inode*); 2911a9947fSrtm 30bcca6c6bSrsc // Blocks. 315be0039cSrtm 32f5527388Srsc // Allocate a disk block. 3324111398Skaashoek static uint 3424111398Skaashoek balloc(uint dev) 3524111398Skaashoek { 367d4aef6cSrsc int b, bi, m, ninodes, size; 3724111398Skaashoek struct buf *bp; 3824111398Skaashoek struct superblock *sb; 3924111398Skaashoek 4024111398Skaashoek bp = bread(dev, 1); 4124111398Skaashoek sb = (struct superblock*) bp->data; 4224111398Skaashoek size = sb->size; 4324111398Skaashoek ninodes = sb->ninodes; 4424111398Skaashoek 4524111398Skaashoek for(b = 0; b < size; b++) { 4624111398Skaashoek if(b % BPB == 0) { 4724111398Skaashoek brelse(bp); 4824111398Skaashoek bp = bread(dev, BBLOCK(b, ninodes)); 4924111398Skaashoek } 5024111398Skaashoek bi = b % BPB; 5124111398Skaashoek m = 0x1 << (bi % 8); 5224111398Skaashoek if((bp->data[bi/8] & m) == 0) { // is block free? 5324111398Skaashoek bp->data[bi/8] |= 0x1 << (bi % 8); 5405e97551Srtm bwrite(bp, BBLOCK(b, ninodes)); // mark it allocated on disk 5528d9ef04Skaashoek brelse(bp); 5624111398Skaashoek return b; 5724111398Skaashoek } 587d4aef6cSrsc } 597d4aef6cSrsc panic("balloc: out of blocks"); 607d4aef6cSrsc } 6124111398Skaashoek 62bb207a1dSrsc // Free a disk block. 6328d9ef04Skaashoek static void 6428d9ef04Skaashoek bfree(int dev, uint b) 6528d9ef04Skaashoek { 6628d9ef04Skaashoek struct buf *bp; 6728d9ef04Skaashoek struct superblock *sb; 687d4aef6cSrsc int bi, m, ninodes; 6928d9ef04Skaashoek 7028d9ef04Skaashoek bp = bread(dev, 1); 7128d9ef04Skaashoek sb = (struct superblock*) bp->data; 7228d9ef04Skaashoek ninodes = sb->ninodes; 7328d9ef04Skaashoek brelse(bp); 7428d9ef04Skaashoek 75c372e8dcSkaashoek bp = bread(dev, b); 76c372e8dcSkaashoek memset(bp->data, 0, BSIZE); 77c372e8dcSkaashoek bwrite(bp, b); 78c372e8dcSkaashoek brelse(bp); 79c372e8dcSkaashoek 8028d9ef04Skaashoek bp = bread(dev, BBLOCK(b, ninodes)); 8128d9ef04Skaashoek bi = b % BPB; 827d4aef6cSrsc m = 0x1 << (bi % 8); 837d4aef6cSrsc bp->data[bi/8] &= ~m; 8405e97551Srtm bwrite(bp, BBLOCK(b, ninodes)); // mark it free on disk 8528d9ef04Skaashoek brelse(bp); 8628d9ef04Skaashoek } 8724111398Skaashoek 88bcca6c6bSrsc // Inodes 89bcca6c6bSrsc // 90bcca6c6bSrsc // The inodes are laid out sequentially on disk immediately after 91bcca6c6bSrsc // the superblock. The kernel keeps a cache of the in-use 92bcca6c6bSrsc // on-disk structures to provide a place for synchronizing access 93bcca6c6bSrsc // to inodes shared between multiple processes. 94bcca6c6bSrsc // 95bcca6c6bSrsc // ip->ref counts the number of references to this 96bcca6c6bSrsc // inode; references are typically kept in struct file and in cp->cwd. 97bcca6c6bSrsc // When ip->ref falls to zero, the inode is no longer cached. 98bcca6c6bSrsc // It is an error to use an inode without holding a reference to it. 99bcca6c6bSrsc // 100bcca6c6bSrsc // Inodes can be marked busy, just like bufs, meaning 101bcca6c6bSrsc // that some process has logically locked the inode, and other processes 102bcca6c6bSrsc // are not allowed to look at it. Because the locking can last for 103bcca6c6bSrsc // a long time (for example, during a disk access), we use a flag 104bcca6c6bSrsc // like in buffer cache, not spin locks. The inode should always be 105bcca6c6bSrsc // locked during modifications to it. 106bcca6c6bSrsc 107bcca6c6bSrsc struct { 108bcca6c6bSrsc struct spinlock lock; 109bcca6c6bSrsc struct inode inode[NINODE]; 110bcca6c6bSrsc } icache; 111bcca6c6bSrsc 112bcca6c6bSrsc void 113bcca6c6bSrsc iinit(void) 114bcca6c6bSrsc { 115bcca6c6bSrsc initlock(&icache.lock, "icache.lock"); 116bcca6c6bSrsc } 117bcca6c6bSrsc 118f5527388Srsc // Find the inode with number inum on device dev 119f32f3638Srsc // and return the in-memory copy. The returned inode 120f32f3638Srsc // has its reference count incremented (and thus must be 121f32f3638Srsc // idecref'ed), but is *unlocked*, meaning that none of the fields 122f32f3638Srsc // except dev and inum are guaranteed to be initialized. 123f32f3638Srsc // This convention gives the caller maximum control over blocking; 124f32f3638Srsc // it also guarantees that iget will not sleep, which is useful in 125f32f3638Srsc // the early igetroot and when holding other locked inodes. 12611a9947fSrtm struct inode* 12711a9947fSrtm iget(uint dev, uint inum) 12811a9947fSrtm { 129bcca6c6bSrsc struct inode *ip, *empty; 13011a9947fSrtm 131bcca6c6bSrsc acquire(&icache.lock); 13211a9947fSrtm 133bcca6c6bSrsc // Try for cached inode. 134bcca6c6bSrsc empty = 0; 135bcca6c6bSrsc for(ip = &icache.inode[0]; ip < &icache.inode[NINODE]; ip++){ 1360d6bbd31Srsc if(ip->ref > 0 && ip->dev == dev && ip->inum == inum){ 1370d6bbd31Srsc ip->ref++; 138bcca6c6bSrsc release(&icache.lock); 13911a9947fSrtm return ip; 14011a9947fSrtm } 141bcca6c6bSrsc if(empty == 0 && ip->ref == 0) // Remember empty slot. 142bcca6c6bSrsc empty = ip; 14311a9947fSrtm } 14411a9947fSrtm 145bcca6c6bSrsc // Allocate fresh inode. 146bcca6c6bSrsc if(empty == 0) 14732eea766Srsc panic("iget: no inodes"); 14811a9947fSrtm 149bcca6c6bSrsc ip = empty; 150bcca6c6bSrsc ip->dev = dev; 151bcca6c6bSrsc ip->inum = inum; 152bcca6c6bSrsc ip->ref = 1; 153f32f3638Srsc ip->flags = 0; 154bcca6c6bSrsc release(&icache.lock); 15511a9947fSrtm 156f32f3638Srsc return ip; 157f32f3638Srsc } 158f32f3638Srsc 159f32f3638Srsc // Iget the inode for the file system root (/). 160f32f3638Srsc // This gets called before there is a current process: it cannot sleep! 161f32f3638Srsc struct inode* 162f32f3638Srsc igetroot(void) 163f32f3638Srsc { 164f32f3638Srsc struct inode *ip; 165f32f3638Srsc ip = iget(ROOTDEV, 1); 166f32f3638Srsc return ip; 167f32f3638Srsc } 168f32f3638Srsc 169f32f3638Srsc // Lock the given inode. 170f32f3638Srsc void 171f32f3638Srsc ilock(struct inode *ip) 172f32f3638Srsc { 173f32f3638Srsc struct buf *bp; 174f32f3638Srsc struct dinode *dip; 175f32f3638Srsc 176f32f3638Srsc if(ip->ref < 1) 177f32f3638Srsc panic("ilock"); 178f32f3638Srsc 179f32f3638Srsc acquire(&icache.lock); 180f32f3638Srsc while(ip->flags & I_BUSY) 181f32f3638Srsc sleep(ip, &icache.lock); 182f32f3638Srsc ip->flags |= I_BUSY; 183f32f3638Srsc release(&icache.lock); 184f32f3638Srsc 185f32f3638Srsc if(!(ip->flags & I_VALID)){ 186f32f3638Srsc bp = bread(ip->dev, IBLOCK(ip->inum)); 187f32f3638Srsc dip = &((struct dinode*)(bp->data))[ip->inum % IPB]; 188bcca6c6bSrsc ip->type = dip->type; 189bcca6c6bSrsc ip->major = dip->major; 190bcca6c6bSrsc ip->minor = dip->minor; 191bcca6c6bSrsc ip->nlink = dip->nlink; 192bcca6c6bSrsc ip->size = dip->size; 193bcca6c6bSrsc memmove(ip->addrs, dip->addrs, sizeof(ip->addrs)); 19411a9947fSrtm brelse(bp); 195f32f3638Srsc ip->flags |= I_VALID; 19611a9947fSrtm } 197bcca6c6bSrsc } 198bcca6c6bSrsc 199bcca6c6bSrsc // Unlock the given inode. 200bcca6c6bSrsc void 201bcca6c6bSrsc iunlock(struct inode *ip) 202bcca6c6bSrsc { 203f32f3638Srsc if(!(ip->flags & I_BUSY) || ip->ref < 1) 204bcca6c6bSrsc panic("iunlock"); 205bcca6c6bSrsc 206bcca6c6bSrsc acquire(&icache.lock); 207f32f3638Srsc ip->flags &= ~I_BUSY; 208bcca6c6bSrsc wakeup(ip); 209bcca6c6bSrsc release(&icache.lock); 210bcca6c6bSrsc } 211bcca6c6bSrsc 212bcca6c6bSrsc // Unlock inode and drop reference. 213bcca6c6bSrsc void 214bcca6c6bSrsc iput(struct inode *ip) 215bcca6c6bSrsc { 216f32f3638Srsc iunlock(ip); 217f32f3638Srsc idecref(ip); 218bcca6c6bSrsc } 219bcca6c6bSrsc 220bcca6c6bSrsc // Increment reference count for ip. 221bcca6c6bSrsc // Returns ip to enable ip = iincref(ip1) idiom. 222bcca6c6bSrsc struct inode* 223bcca6c6bSrsc iincref(struct inode *ip) 224bcca6c6bSrsc { 225f32f3638Srsc acquire(&icache.lock); 226bcca6c6bSrsc ip->ref++; 227f32f3638Srsc release(&icache.lock); 228bcca6c6bSrsc return ip; 229bcca6c6bSrsc } 230bcca6c6bSrsc 231f32f3638Srsc // Caller holds reference to unlocked ip. Drop reference. 232bcca6c6bSrsc void 233bcca6c6bSrsc idecref(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) 239f32f3638Srsc panic("idecref 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 253bcca6c6bSrsc // Allocate a new inode with the given type on device dev. 254e8d11c2eSkaashoek struct inode* 255e8d11c2eSkaashoek ialloc(uint dev, short type) 256e8d11c2eSkaashoek { 257f32f3638Srsc int inum, ninodes; 258f32f3638Srsc struct buf *bp; 2597d4aef6cSrsc struct dinode *dip; 260e8d11c2eSkaashoek struct superblock *sb; 261e8d11c2eSkaashoek 262e8d11c2eSkaashoek bp = bread(dev, 1); 26324111398Skaashoek sb = (struct superblock*)bp->data; 264e8d11c2eSkaashoek ninodes = sb->ninodes; 265e8d11c2eSkaashoek brelse(bp); 266e8d11c2eSkaashoek 267e8d11c2eSkaashoek for(inum = 1; inum < ninodes; inum++) { // loop over inode blocks 26824111398Skaashoek bp = bread(dev, IBLOCK(inum)); 269e8d11c2eSkaashoek dip = &((struct dinode*)(bp->data))[inum % IPB]; 270e8d11c2eSkaashoek if(dip->type == 0) { // a free inode 2712aa4c3bcSrtm memset(dip, 0, sizeof(*dip)); 272e8d11c2eSkaashoek dip->type = type; 27305e97551Srtm bwrite(bp, IBLOCK(inum)); // mark it allocated on the disk 274e8d11c2eSkaashoek brelse(bp); 275f32f3638Srsc return iget(dev, inum); 276e8d11c2eSkaashoek } 27795c07f82Srsc brelse(bp); 27895c07f82Srsc } 27995c07f82Srsc panic("ialloc: no inodes"); 28095c07f82Srsc } 281e8d11c2eSkaashoek 282bcca6c6bSrsc // Copy inode, which has changed, from memory to disk. 283*fbf91039Srsc static void 284bcca6c6bSrsc iupdate(struct inode *ip) 285bcca6c6bSrsc { 286bcca6c6bSrsc struct buf *bp; 287bcca6c6bSrsc struct dinode *dip; 288bcca6c6bSrsc 289bcca6c6bSrsc bp = bread(ip->dev, IBLOCK(ip->inum)); 290bcca6c6bSrsc dip = &((struct dinode*)(bp->data))[ip->inum % IPB]; 291bcca6c6bSrsc dip->type = ip->type; 292bcca6c6bSrsc dip->major = ip->major; 293bcca6c6bSrsc dip->minor = ip->minor; 294bcca6c6bSrsc dip->nlink = ip->nlink; 295bcca6c6bSrsc dip->size = ip->size; 296bcca6c6bSrsc memmove(dip->addrs, ip->addrs, sizeof(ip->addrs)); 297bcca6c6bSrsc bwrite(bp, IBLOCK(ip->inum)); 298bcca6c6bSrsc brelse(bp); 299bcca6c6bSrsc } 300bcca6c6bSrsc 301bcca6c6bSrsc // Inode contents 302bcca6c6bSrsc // 303bcca6c6bSrsc // The contents (data) associated with each inode is stored 304bcca6c6bSrsc // in a sequence of blocks on the disk. The first NDIRECT blocks 305bcca6c6bSrsc // are stored in ip->addrs[]. The next NINDIRECT blocks are 306bcca6c6bSrsc // listed in the block ip->addrs[INDIRECT]. 3079d3fb671Srtm 308bb207a1dSrsc // Return the disk block address of the nth block in inode ip. 309bcca6c6bSrsc // If there is no such block: if alloc is set, allocate one, else return -1. 31022bac2cbSkaashoek uint 311bcca6c6bSrsc bmap(struct inode *ip, uint bn, int alloc) 31222bac2cbSkaashoek { 313bcca6c6bSrsc uint addr, *a; 314bcca6c6bSrsc struct buf *bp; 31522bac2cbSkaashoek 316ea2909b6Skaashoek if(bn < NDIRECT) { 317bcca6c6bSrsc if((addr = ip->addrs[bn]) == 0) { 318bcca6c6bSrsc if(!alloc) 319bcca6c6bSrsc return -1; 320bcca6c6bSrsc ip->addrs[bn] = addr = balloc(ip->dev); 321ea2909b6Skaashoek } 322bcca6c6bSrsc return addr; 323bcca6c6bSrsc } 324bcca6c6bSrsc bn -= NDIRECT; 325bcca6c6bSrsc 326bcca6c6bSrsc if(bn < NINDIRECT) { 327bcca6c6bSrsc // Load indirect block, allocating if necessary. 328bcca6c6bSrsc if((addr = ip->addrs[INDIRECT]) == 0) { 329bcca6c6bSrsc if(!alloc) 330bcca6c6bSrsc return -1; 331bcca6c6bSrsc ip->addrs[INDIRECT] = addr = balloc(ip->dev); 332bcca6c6bSrsc } 333bcca6c6bSrsc bp = bread(ip->dev, addr); 334bcca6c6bSrsc a = (uint*)bp->data; 335bcca6c6bSrsc 336bcca6c6bSrsc if((addr = a[bn]) == 0) { 337bcca6c6bSrsc if(!alloc) { 338bcca6c6bSrsc brelse(bp); 339bcca6c6bSrsc return -1; 340bcca6c6bSrsc } 341bcca6c6bSrsc a[bn] = addr = balloc(ip->dev); 342bcca6c6bSrsc bwrite(bp, ip->addrs[INDIRECT]); 343bcca6c6bSrsc } 344bcca6c6bSrsc brelse(bp); 345bcca6c6bSrsc return addr; 34622bac2cbSkaashoek } 34722bac2cbSkaashoek 348bcca6c6bSrsc panic("bmap: out of range"); 349bcca6c6bSrsc } 350bcca6c6bSrsc 351bcca6c6bSrsc // Truncate inode (discard contents). 352*fbf91039Srsc static void 3532aa4c3bcSrtm itrunc(struct inode *ip) 35422bac2cbSkaashoek { 355ea2909b6Skaashoek int i, j; 356bcca6c6bSrsc struct buf *bp; 3577d4aef6cSrsc uint *a; 35822bac2cbSkaashoek 359bcca6c6bSrsc for(i = 0; i < NDIRECT; i++) { 360bcca6c6bSrsc if(ip->addrs[i]) { 36122bac2cbSkaashoek bfree(ip->dev, ip->addrs[i]); 36222bac2cbSkaashoek ip->addrs[i] = 0; 36322bac2cbSkaashoek } 36422bac2cbSkaashoek } 365bcca6c6bSrsc 366bcca6c6bSrsc if(ip->addrs[INDIRECT]) { 367bcca6c6bSrsc bp = bread(ip->dev, ip->addrs[INDIRECT]); 368bcca6c6bSrsc a = (uint*)bp->data; 369bcca6c6bSrsc for(j = 0; j < NINDIRECT; j++) { 370bcca6c6bSrsc if(a[j]) 371bcca6c6bSrsc bfree(ip->dev, a[j]); 372bcca6c6bSrsc } 373bcca6c6bSrsc brelse(bp); 374bcca6c6bSrsc ip->addrs[INDIRECT] = 0; 375bcca6c6bSrsc } 376bcca6c6bSrsc 37722bac2cbSkaashoek ip->size = 0; 37822bac2cbSkaashoek iupdate(ip); 37922bac2cbSkaashoek } 38022bac2cbSkaashoek 381bb207a1dSrsc // Copy stat information from inode. 382e958c538Skaashoek void 3831f544842Skaashoek stati(struct inode *ip, struct stat *st) 3841f544842Skaashoek { 3851dca3afbSrsc st->dev = ip->dev; 3861dca3afbSrsc st->ino = ip->inum; 3871dca3afbSrsc st->type = ip->type; 3881dca3afbSrsc st->nlink = ip->nlink; 3891dca3afbSrsc st->size = ip->size; 3901f544842Skaashoek } 3911f544842Skaashoek 392bb207a1dSrsc // Read data from inode. 393c59361f1Srtm int 39417a85657Srtm readi(struct inode *ip, char *dst, uint off, uint n) 395c59361f1Srtm { 396bcca6c6bSrsc uint tot, m; 397c59361f1Srtm struct buf *bp; 398c59361f1Srtm 399939f9edeSkaashoek if(ip->type == T_DEV) { 4001dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].read) 401939f9edeSkaashoek return -1; 4021dca3afbSrsc return devsw[ip->major].read(ip->minor, dst, n); 403939f9edeSkaashoek } 404939f9edeSkaashoek 405bcca6c6bSrsc if(off + n < off) 406bcca6c6bSrsc return -1; 407bcca6c6bSrsc if(off + n > ip->size) 408bcca6c6bSrsc n = ip->size - off; 409bcca6c6bSrsc 410bcca6c6bSrsc for(tot=0; tot<n; tot+=m, off+=m, dst+=m) { 411bcca6c6bSrsc bp = bread(ip->dev, bmap(ip, off/BSIZE, 0)); 412bcca6c6bSrsc m = min(n - tot, BSIZE - off%BSIZE); 413bcca6c6bSrsc memmove(dst, bp->data + off%BSIZE, m); 414c59361f1Srtm brelse(bp); 415c59361f1Srtm } 416bcca6c6bSrsc return n; 417ea2909b6Skaashoek } 418ea2909b6Skaashoek 419bb207a1dSrsc // Write data to inode. 420ea2909b6Skaashoek int 421bcca6c6bSrsc writei(struct inode *ip, char *src, uint off, uint n) 4226fa5ffb5Skaashoek { 423bcca6c6bSrsc uint tot, m; 4247d4aef6cSrsc struct buf *bp; 4257d4aef6cSrsc 4266fa5ffb5Skaashoek if(ip->type == T_DEV) { 4271dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].write) 428939f9edeSkaashoek return -1; 429bcca6c6bSrsc return devsw[ip->major].write(ip->minor, src, n); 4307d4aef6cSrsc } 4317d4aef6cSrsc 432bcca6c6bSrsc if(off + n < off) 433bcca6c6bSrsc return -1; 434bcca6c6bSrsc if(off + n > MAXFILE*BSIZE) 435bcca6c6bSrsc n = MAXFILE*BSIZE - off; 436bcca6c6bSrsc 437bcca6c6bSrsc for(tot=0; tot<n; tot+=m, off+=m, src+=m) { 438bcca6c6bSrsc bp = bread(ip->dev, bmap(ip, off/BSIZE, 1)); 439bcca6c6bSrsc m = min(n - tot, BSIZE - off%BSIZE); 440bcca6c6bSrsc memmove(bp->data + off%BSIZE, src, m); 441bcca6c6bSrsc bwrite(bp, bmap(ip, off/BSIZE, 0)); 44228d9ef04Skaashoek brelse(bp); 44328d9ef04Skaashoek } 444bcca6c6bSrsc 445bcca6c6bSrsc if(n > 0 && off > ip->size) { 44648b82470Srsc ip->size = off; 44728d9ef04Skaashoek iupdate(ip); 44828d9ef04Skaashoek } 449bcca6c6bSrsc return n; 4506fa5ffb5Skaashoek } 4516fa5ffb5Skaashoek 452bcca6c6bSrsc // Directories 453bcca6c6bSrsc // 454bcca6c6bSrsc // Directories are just inodes (files) filled with dirent structures. 455bcca6c6bSrsc 456*fbf91039Srsc // Compare two names, which are strings with a max length of DIRSIZ. 457*fbf91039Srsc static int 458*fbf91039Srsc namecmp(const char *s, const char *t) 459*fbf91039Srsc { 460*fbf91039Srsc int i; 461*fbf91039Srsc 462*fbf91039Srsc for(i=0; i<DIRSIZ; i++){ 463*fbf91039Srsc if(s[i] != t[i]) 464*fbf91039Srsc return s[i] - t[i]; 465*fbf91039Srsc if(s[i] == 0) 466*fbf91039Srsc break; 467*fbf91039Srsc } 468*fbf91039Srsc return 0; 469*fbf91039Srsc } 470*fbf91039Srsc 471*fbf91039Srsc // Copy one name to another. 472*fbf91039Srsc static void 473*fbf91039Srsc namecpy(char *s, const char *t) 474*fbf91039Srsc { 475*fbf91039Srsc int i; 476*fbf91039Srsc 477*fbf91039Srsc for(i=0; i<DIRSIZ && t[i]; i++) 478*fbf91039Srsc s[i] = t[i]; 479*fbf91039Srsc for(; i<DIRSIZ; i++) 480*fbf91039Srsc s[i] = 0; 481*fbf91039Srsc } 482*fbf91039Srsc 483bcca6c6bSrsc // Look for a directory entry in a directory. 484bcca6c6bSrsc // If not found, return -1. 485bcca6c6bSrsc // If found: 486bcca6c6bSrsc // set *poff to the byte offset of the directory entry 487bcca6c6bSrsc // set *pinum to the inode number 488bcca6c6bSrsc // return 0. 489*fbf91039Srsc static struct inode* 490*fbf91039Srsc dirlookup(struct inode *dp, char *name, uint *poff) 491bcca6c6bSrsc { 492f32f3638Srsc uint off, inum; 493bcca6c6bSrsc struct buf *bp; 494bcca6c6bSrsc struct dirent *de; 495bcca6c6bSrsc 496bcca6c6bSrsc if(dp->type != T_DIR) 497f32f3638Srsc return 0; 498bcca6c6bSrsc 499bcca6c6bSrsc for(off = 0; off < dp->size; off += BSIZE){ 500bcca6c6bSrsc bp = bread(dp->dev, bmap(dp, off / BSIZE, 0)); 501bcca6c6bSrsc for(de = (struct dirent*) bp->data; 502bcca6c6bSrsc de < (struct dirent*) (bp->data + BSIZE); 503bcca6c6bSrsc de++){ 504bcca6c6bSrsc if(de->inum == 0) 505bcca6c6bSrsc continue; 506*fbf91039Srsc if(namecmp(name, de->name) == 0){ 507bcca6c6bSrsc // entry matches path element 508e2a620daSrsc if(poff) 509bcca6c6bSrsc *poff = off + (uchar*)de - bp->data; 510f32f3638Srsc inum = de->inum; 511bcca6c6bSrsc brelse(bp); 512f32f3638Srsc return iget(dp->dev, inum); 513f32f3638Srsc } 514f32f3638Srsc } 515f32f3638Srsc brelse(bp); 516f32f3638Srsc } 517bcca6c6bSrsc return 0; 518bcca6c6bSrsc } 519bcca6c6bSrsc 520bcca6c6bSrsc // Write a new directory entry (name, ino) into the directory dp. 521bcca6c6bSrsc // Caller must have locked dp. 522*fbf91039Srsc static int 523*fbf91039Srsc dirlink(struct inode *dp, char *name, uint ino) 524bcca6c6bSrsc { 525e2a620daSrsc int off; 526bcca6c6bSrsc struct dirent de; 527f32f3638Srsc struct inode *ip; 528f32f3638Srsc 529f32f3638Srsc // Double-check that name is not present. 530*fbf91039Srsc if((ip = dirlookup(dp, name, 0)) != 0){ 531f32f3638Srsc idecref(ip); 532f32f3638Srsc return -1; 533f32f3638Srsc } 534bcca6c6bSrsc 535bcca6c6bSrsc // Look for an empty dirent. 536bcca6c6bSrsc for(off = 0; off < dp->size; off += sizeof(de)){ 537bcca6c6bSrsc if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 538bcca6c6bSrsc panic("dirwrite read"); 539bcca6c6bSrsc if(de.inum == 0) 540bcca6c6bSrsc break; 541bcca6c6bSrsc } 542bcca6c6bSrsc 543*fbf91039Srsc namecpy(de.name, name); 544bcca6c6bSrsc de.inum = ino; 545bcca6c6bSrsc if(writei(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 546bcca6c6bSrsc panic("dirwrite"); 547f32f3638Srsc 548f32f3638Srsc return 0; 549bcca6c6bSrsc } 550bcca6c6bSrsc 551e2a620daSrsc // Create a new inode named name inside dp 552e2a620daSrsc // and return its locked inode structure. 553e2a620daSrsc // If name already exists, return 0. 554*fbf91039Srsc static struct inode* 555*fbf91039Srsc dircreat(struct inode *dp, char *name, short type, short major, short minor) 556e2a620daSrsc { 557e2a620daSrsc struct inode *ip; 558e2a620daSrsc 559e2a620daSrsc ip = ialloc(dp->dev, type); 560e2a620daSrsc if(ip == 0) 561e2a620daSrsc return 0; 562f32f3638Srsc ilock(ip); 563e2a620daSrsc ip->major = major; 564e2a620daSrsc ip->minor = minor; 565e2a620daSrsc ip->size = 0; 566e2a620daSrsc ip->nlink = 1; 567e2a620daSrsc iupdate(ip); 568e2a620daSrsc 569*fbf91039Srsc if(dirlink(dp, name, ip->inum) < 0){ 570f32f3638Srsc ip->nlink = 0; 571f32f3638Srsc iupdate(ip); 572f32f3638Srsc iput(ip); 573f32f3638Srsc return 0; 574f32f3638Srsc } 575e2a620daSrsc 576e2a620daSrsc return ip; 577e2a620daSrsc } 578e2a620daSrsc 579bcca6c6bSrsc // Paths 580bcca6c6bSrsc 581ab5c2dbbSrsc // Skip over the next path element in path, 582ab5c2dbbSrsc // saving it in *name and its length in *len. 583ab5c2dbbSrsc // Return a pointer to the element after that 584ab5c2dbbSrsc // (after any trailing slashes). 585ab5c2dbbSrsc // Thus the caller can check whether *path=='\0' 586ab5c2dbbSrsc // to see whether the name just removed was 587ab5c2dbbSrsc // the last one. 588ab5c2dbbSrsc // If there is no name to remove, return 0. 589ab5c2dbbSrsc // 590ab5c2dbbSrsc // Examples: 591ab5c2dbbSrsc // skipelem("a/bb/c") = "bb/c", with *name = "a/bb/c", len=1 592ab5c2dbbSrsc // skipelem("///a/bb") = "b", with *name="a/bb", len=1 593ab5c2dbbSrsc // skipelem("") = skipelem("////") = 0 594ab5c2dbbSrsc // 595ab5c2dbbSrsc static char* 596*fbf91039Srsc skipelem(char *path, char *name) 597ab5c2dbbSrsc { 598*fbf91039Srsc char *s; 599*fbf91039Srsc int len; 600*fbf91039Srsc 601ab5c2dbbSrsc while(*path == '/') 602ab5c2dbbSrsc path++; 603ab5c2dbbSrsc if(*path == 0) 604ab5c2dbbSrsc return 0; 605*fbf91039Srsc s = path; 606ab5c2dbbSrsc while(*path != '/' && *path != 0) 607ab5c2dbbSrsc path++; 608*fbf91039Srsc len = path - s; 609*fbf91039Srsc if(len >= DIRSIZ) 610*fbf91039Srsc memmove(name, s, DIRSIZ); 611*fbf91039Srsc else{ 612*fbf91039Srsc memmove(name, s, len); 613*fbf91039Srsc name[len] = 0; 614*fbf91039Srsc } 615ab5c2dbbSrsc while(*path == '/') 616ab5c2dbbSrsc path++; 617ab5c2dbbSrsc return path; 618ab5c2dbbSrsc } 619ab5c2dbbSrsc 620211ff0c6Srtm // look up a path name, in one of three modes. 621211ff0c6Srtm // NAMEI_LOOKUP: return locked target inode. 622211ff0c6Srtm // NAMEI_CREATE: return locked parent inode. 6235051da6dSrtm // return 0 if name does exist. 6245051da6dSrtm // *ret_last points to last path component (i.e. new file name). 6255051da6dSrtm // *ret_ip points to the the name that did exist, if it did. 6265051da6dSrtm // *ret_ip and *ret_last may be zero even if return value is zero. 627211ff0c6Srtm // NAMEI_DELETE: return locked parent inode, offset of dirent in *ret_off. 628211ff0c6Srtm // return 0 if name doesn't exist. 6299d3fb671Srtm struct inode* 630*fbf91039Srsc _namei(char *path, int parent, char *name) 6319d3fb671Srtm { 632f32f3638Srsc struct inode *dp, *ip; 633f32f3638Srsc uint off; 6349d3fb671Srtm 635ab5c2dbbSrsc if(*path == '/') 636bcca6c6bSrsc dp = igetroot(); 637f32f3638Srsc else 638bc011703Srsc dp = iincref(cp->cwd); 6398787cd01Skaashoek ilock(dp); 6409d3fb671Srtm 641*fbf91039Srsc while((path = skipelem(path, name)) != 0){ 642ab5c2dbbSrsc if(dp->type != T_DIR) 643ab5c2dbbSrsc goto fail; 644ab5c2dbbSrsc 645e2a620daSrsc if(parent && *path == '\0'){ 646e2a620daSrsc // Stop one level early. 647ab5c2dbbSrsc return dp; 648ab5c2dbbSrsc } 649ab5c2dbbSrsc 650*fbf91039Srsc if((ip = dirlookup(dp, name, &off)) == 0) 651ab5c2dbbSrsc goto fail; 652ab5c2dbbSrsc 653ab5c2dbbSrsc iput(dp); 654f32f3638Srsc ilock(ip); 655f32f3638Srsc dp = ip; 656ab5c2dbbSrsc if(dp->type == 0 || dp->nlink < 1) 657ab5c2dbbSrsc panic("namei"); 658ab5c2dbbSrsc } 659e2a620daSrsc if(parent) 6605051da6dSrtm return 0; 661e2a620daSrsc return dp; 662ab5c2dbbSrsc 663ab5c2dbbSrsc fail: 664211ff0c6Srtm iput(dp); 665211ff0c6Srtm return 0; 6660633b971Skaashoek } 6679d3fb671Srtm 668e2a620daSrsc struct inode* 669e2a620daSrsc namei(char *path) 670e2a620daSrsc { 671*fbf91039Srsc char name[DIRSIZ]; 672*fbf91039Srsc return _namei(path, 0, name); 673e2a620daSrsc } 674e2a620daSrsc 675*fbf91039Srsc static struct inode* 676*fbf91039Srsc nameiparent(char *path, char *name) 677e2a620daSrsc { 678*fbf91039Srsc return _namei(path, 1, name); 679e2a620daSrsc } 680e2a620daSrsc 681b6095304Srsc // Create the path and return its locked inode structure. 682bb207a1dSrsc // If cp already exists, return 0. 683e8d11c2eSkaashoek struct inode* 684b6095304Srsc mknod(char *path, short type, short major, short minor) 685e8d11c2eSkaashoek { 6860633b971Skaashoek struct inode *ip, *dp; 687*fbf91039Srsc char name[DIRSIZ]; 688e8d11c2eSkaashoek 689*fbf91039Srsc if((dp = nameiparent(path, name)) == 0) 6900633b971Skaashoek return 0; 691*fbf91039Srsc ip = dircreat(dp, name, type, major, minor); 692e2a620daSrsc iput(dp); 693e8d11c2eSkaashoek return ip; 694e8d11c2eSkaashoek } 69524437cd5Skaashoek 696bb207a1dSrsc // Unlink the inode named cp. 69724437cd5Skaashoek int 698b6095304Srsc unlink(char *path) 69924437cd5Skaashoek { 700211ff0c6Srtm struct inode *ip, *dp; 701211ff0c6Srtm struct dirent de; 702f32f3638Srsc uint off; 703*fbf91039Srsc char name[DIRSIZ]; 70424437cd5Skaashoek 705*fbf91039Srsc if((dp = nameiparent(path, name)) == 0) 70624437cd5Skaashoek return -1; 707*fbf91039Srsc 708*fbf91039Srsc // Cannot unlink "." or "..". 709*fbf91039Srsc if(namecmp(name, ".") == 0 || namecmp(name, "..") == 0){ 710e2a620daSrsc iput(dp); 711e2a620daSrsc return -1; 712e2a620daSrsc } 71317e3cf15Srtm 714*fbf91039Srsc if((ip = dirlookup(dp, name, &off)) == 0){ 715ab5c2dbbSrsc iput(dp); 716ab5c2dbbSrsc return -1; 717ab5c2dbbSrsc } 718211ff0c6Srtm memset(&de, 0, sizeof(de)); 719211ff0c6Srtm if(writei(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 720211ff0c6Srtm panic("unlink dir write"); 72124437cd5Skaashoek iput(dp); 722211ff0c6Srtm 723f32f3638Srsc ilock(ip); 724bcfb84b6Srtm if(ip->nlink < 1) 725bcfb84b6Srtm panic("unlink nlink < 1"); 726211ff0c6Srtm ip->nlink--; 727211ff0c6Srtm iupdate(ip); 72822bac2cbSkaashoek iput(ip); 729211ff0c6Srtm 73024437cd5Skaashoek return 0; 73124437cd5Skaashoek } 7329e5970d5Srtm 733bb207a1dSrsc // Create the path new as a link to the same inode as old. 7349e5970d5Srtm int 735e2a620daSrsc link(char *old, char *new) 7369e5970d5Srtm { 737211ff0c6Srtm struct inode *ip, *dp; 738*fbf91039Srsc char name[DIRSIZ]; 7399e5970d5Srtm 740e2a620daSrsc if((ip = namei(old)) == 0) 7419e5970d5Srtm return -1; 742211ff0c6Srtm if(ip->type == T_DIR){ 743211ff0c6Srtm iput(ip); 744211ff0c6Srtm return -1; 745211ff0c6Srtm } 746211ff0c6Srtm iunlock(ip); 747211ff0c6Srtm 748*fbf91039Srsc if((dp = nameiparent(new, name)) == 0){ 749e2a620daSrsc idecref(ip); 750e2a620daSrsc return -1; 751e2a620daSrsc } 752*fbf91039Srsc if(dp->dev != ip->dev || dirlink(dp, name, ip->inum) < 0){ 753211ff0c6Srtm idecref(ip); 754211ff0c6Srtm iput(dp); 755211ff0c6Srtm return -1; 756211ff0c6Srtm } 757f32f3638Srsc iput(dp); 758211ff0c6Srtm 759f32f3638Srsc // XXX write ordering wrong here too. 760211ff0c6Srtm ilock(ip); 761be29b8e2Srsc ip->nlink++; 7629e5970d5Srtm iupdate(ip); 763f32f3638Srsc iput(ip); 764f32f3638Srsc return 0; 765f32f3638Srsc } 7669e5970d5Srtm 767f32f3638Srsc int 768f32f3638Srsc mkdir(char *path) 769f32f3638Srsc { 770f32f3638Srsc struct inode *dp, *ip; 771*fbf91039Srsc char name[DIRSIZ]; 772f32f3638Srsc 773f32f3638Srsc // XXX write ordering is screwy here- do we care? 774*fbf91039Srsc if((dp = nameiparent(path, name)) == 0) 775f32f3638Srsc return -1; 776f32f3638Srsc 777*fbf91039Srsc if((ip = dircreat(dp, name, T_DIR, 0, 0)) == 0){ 778f32f3638Srsc iput(dp); 779f32f3638Srsc return -1; 780f32f3638Srsc } 781f32f3638Srsc dp->nlink++; 782f32f3638Srsc iupdate(dp); 783f32f3638Srsc 784*fbf91039Srsc if(dirlink(ip, ".", ip->inum) < 0 || dirlink(ip, "..", dp->inum) < 0) 785f32f3638Srsc panic("mkdir"); 7869e5970d5Srtm iput(dp); 7879e5970d5Srtm iput(ip); 7889e5970d5Srtm 7899e5970d5Srtm return 0; 7909e5970d5Srtm } 791f32f3638Srsc 792f32f3638Srsc struct inode* 793f32f3638Srsc create(char *path) 794f32f3638Srsc { 795f32f3638Srsc struct inode *dp, *ip; 796*fbf91039Srsc char name[DIRSIZ]; 797f32f3638Srsc 798*fbf91039Srsc if((dp = nameiparent(path, name)) == 0) 799f32f3638Srsc return 0; 800f32f3638Srsc 801*fbf91039Srsc if((ip = dirlookup(dp, name, 0)) != 0){ 802f32f3638Srsc iput(dp); 803f32f3638Srsc ilock(ip); 804f32f3638Srsc if(ip->type == T_DIR){ 805f32f3638Srsc iput(ip); 806f32f3638Srsc return 0; 807f32f3638Srsc } 808f32f3638Srsc return ip; 809f32f3638Srsc } 810*fbf91039Srsc if((ip = dircreat(dp, name, T_FILE, 0, 0)) == 0){ 811f32f3638Srsc iput(dp); 812f32f3638Srsc return 0; 813f32f3638Srsc } 814f32f3638Srsc iput(dp); 815f32f3638Srsc return ip; 816f32f3638Srsc } 817f32f3638Srsc 818