1*bcca6c6bSrsc // File system implementation. 2*bcca6c6bSrsc // 3*bcca6c6bSrsc // Four layers: 4*bcca6c6bSrsc // + Blocks: allocator for raw disk blocks. 5*bcca6c6bSrsc // + Files: inode allocator, reading, writing, metadata. 6*bcca6c6bSrsc // + Directories: inode with special contents (list of other inodes!) 7*bcca6c6bSrsc // + Names: paths like /usr/rtm/xv6/fs.c for convenient naming. 8*bcca6c6bSrsc // 9*bcca6c6bSrsc // Disk layout is: superblock, inodes, disk bitmap, data blocks. 10*bcca6c6bSrsc 11*bcca6c6bSrsc // TODO: Check locking! 12*bcca6c6bSrsc 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 26*bcca6c6bSrsc #define min(a, b) ((a) < (b) ? (a) : (b)) 2711a9947fSrtm 28*bcca6c6bSrsc static void ifree(struct inode*); 299d3fb671Srtm 30*bcca6c6bSrsc // 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 88*bcca6c6bSrsc // Inodes 89*bcca6c6bSrsc // 90*bcca6c6bSrsc // The inodes are laid out sequentially on disk immediately after 91*bcca6c6bSrsc // the superblock. The kernel keeps a cache of the in-use 92*bcca6c6bSrsc // on-disk structures to provide a place for synchronizing access 93*bcca6c6bSrsc // to inodes shared between multiple processes. 94*bcca6c6bSrsc // 95*bcca6c6bSrsc // ip->ref counts the number of references to this 96*bcca6c6bSrsc // inode; references are typically kept in struct file and in cp->cwd. 97*bcca6c6bSrsc // When ip->ref falls to zero, the inode is no longer cached. 98*bcca6c6bSrsc // It is an error to use an inode without holding a reference to it. 99*bcca6c6bSrsc // 100*bcca6c6bSrsc // Inodes can be marked busy, just like bufs, meaning 101*bcca6c6bSrsc // that some process has logically locked the inode, and other processes 102*bcca6c6bSrsc // are not allowed to look at it. Because the locking can last for 103*bcca6c6bSrsc // a long time (for example, during a disk access), we use a flag 104*bcca6c6bSrsc // like in buffer cache, not spin locks. The inode should always be 105*bcca6c6bSrsc // locked during modifications to it. 106*bcca6c6bSrsc 107*bcca6c6bSrsc struct { 108*bcca6c6bSrsc struct spinlock lock; 109*bcca6c6bSrsc struct inode inode[NINODE]; 110*bcca6c6bSrsc } icache; 111*bcca6c6bSrsc 112*bcca6c6bSrsc void 113*bcca6c6bSrsc iinit(void) 114*bcca6c6bSrsc { 115*bcca6c6bSrsc initlock(&icache.lock, "icache.lock"); 116*bcca6c6bSrsc } 117*bcca6c6bSrsc 118f5527388Srsc // Find the inode with number inum on device dev 119f5527388Srsc // and return an in-memory copy. Loads the inode 120f5527388Srsc // from disk into the in-core table if necessary. 121*bcca6c6bSrsc // The returned inode is locked and has its ref count incremented. 122f5527388Srsc // Caller must iput the return value when done with it. 12311a9947fSrtm struct inode* 12411a9947fSrtm iget(uint dev, uint inum) 12511a9947fSrtm { 126*bcca6c6bSrsc struct inode *ip, *empty; 12711a9947fSrtm struct dinode *dip; 12811a9947fSrtm struct buf *bp; 12911a9947fSrtm 130*bcca6c6bSrsc acquire(&icache.lock); 13111a9947fSrtm 13211a9947fSrtm loop: 133*bcca6c6bSrsc // Try for cached inode. 134*bcca6c6bSrsc empty = 0; 135*bcca6c6bSrsc for(ip = &icache.inode[0]; ip < &icache.inode[NINODE]; ip++){ 1360d6bbd31Srsc if(ip->ref > 0 && ip->dev == dev && ip->inum == inum){ 13711a9947fSrtm if(ip->busy){ 138*bcca6c6bSrsc sleep(ip, &icache.lock); 13911a9947fSrtm goto loop; 14011a9947fSrtm } 1410d6bbd31Srsc ip->ref++; 14217a85657Srtm ip->busy = 1; 143*bcca6c6bSrsc release(&icache.lock); 14411a9947fSrtm return ip; 14511a9947fSrtm } 146*bcca6c6bSrsc if(empty == 0 && ip->ref == 0) // Remember empty slot. 147*bcca6c6bSrsc empty = ip; 14811a9947fSrtm } 14911a9947fSrtm 150*bcca6c6bSrsc // Allocate fresh inode. 151*bcca6c6bSrsc if(empty == 0) 15232eea766Srsc panic("iget: no inodes"); 15311a9947fSrtm 154*bcca6c6bSrsc ip = empty; 155*bcca6c6bSrsc ip->dev = dev; 156*bcca6c6bSrsc ip->inum = inum; 157*bcca6c6bSrsc ip->ref = 1; 158*bcca6c6bSrsc ip->busy = 1; 159*bcca6c6bSrsc release(&icache.lock); 16011a9947fSrtm 16124111398Skaashoek bp = bread(dev, IBLOCK(inum)); 16211a9947fSrtm dip = &((struct dinode*)(bp->data))[inum % IPB]; 163*bcca6c6bSrsc ip->type = dip->type; 164*bcca6c6bSrsc ip->major = dip->major; 165*bcca6c6bSrsc ip->minor = dip->minor; 166*bcca6c6bSrsc ip->nlink = dip->nlink; 167*bcca6c6bSrsc ip->size = dip->size; 168*bcca6c6bSrsc memmove(ip->addrs, dip->addrs, sizeof(ip->addrs)); 16911a9947fSrtm brelse(bp); 17011a9947fSrtm 171*bcca6c6bSrsc return ip; 17211a9947fSrtm } 17311a9947fSrtm 174*bcca6c6bSrsc // Iget the inode for the file system root (/). 175*bcca6c6bSrsc struct inode* 176*bcca6c6bSrsc igetroot(void) 17728d9ef04Skaashoek { 178*bcca6c6bSrsc return iget(ROOTDEV, 1); 17928d9ef04Skaashoek } 18028d9ef04Skaashoek 181*bcca6c6bSrsc // Lock the given inode. 182*bcca6c6bSrsc void 183*bcca6c6bSrsc ilock(struct inode *ip) 184*bcca6c6bSrsc { 185*bcca6c6bSrsc if(ip->ref < 1) 186*bcca6c6bSrsc panic("ilock"); 187*bcca6c6bSrsc 188*bcca6c6bSrsc acquire(&icache.lock); 189*bcca6c6bSrsc while(ip->busy) 190*bcca6c6bSrsc sleep(ip, &icache.lock); 191*bcca6c6bSrsc ip->busy = 1; 192*bcca6c6bSrsc release(&icache.lock); 193*bcca6c6bSrsc } 194*bcca6c6bSrsc 195*bcca6c6bSrsc // Unlock the given inode. 196*bcca6c6bSrsc void 197*bcca6c6bSrsc iunlock(struct inode *ip) 198*bcca6c6bSrsc { 199*bcca6c6bSrsc if(ip->busy != 1 || ip->ref < 1) 200*bcca6c6bSrsc panic("iunlock"); 201*bcca6c6bSrsc 202*bcca6c6bSrsc acquire(&icache.lock); 203*bcca6c6bSrsc ip->busy = 0; 204*bcca6c6bSrsc wakeup(ip); 205*bcca6c6bSrsc release(&icache.lock); 206*bcca6c6bSrsc } 207*bcca6c6bSrsc 208*bcca6c6bSrsc // Unlock inode and drop reference. 209*bcca6c6bSrsc void 210*bcca6c6bSrsc iput(struct inode *ip) 211*bcca6c6bSrsc { 212*bcca6c6bSrsc if(ip->ref < 1 || ip->busy != 1) 213*bcca6c6bSrsc panic("iput"); 214*bcca6c6bSrsc 215*bcca6c6bSrsc if((ip->ref == 1) && (ip->nlink == 0)) { 216*bcca6c6bSrsc itrunc(ip); 217*bcca6c6bSrsc ifree(ip); 218*bcca6c6bSrsc } 219*bcca6c6bSrsc 220*bcca6c6bSrsc acquire(&icache.lock); 221*bcca6c6bSrsc ip->ref -= 1; 222*bcca6c6bSrsc ip->busy = 0; 223*bcca6c6bSrsc wakeup(ip); 224*bcca6c6bSrsc release(&icache.lock); 225*bcca6c6bSrsc } 226*bcca6c6bSrsc 227*bcca6c6bSrsc // Increment reference count for ip. 228*bcca6c6bSrsc // Returns ip to enable ip = iincref(ip1) idiom. 229*bcca6c6bSrsc struct inode* 230*bcca6c6bSrsc iincref(struct inode *ip) 231*bcca6c6bSrsc { 232*bcca6c6bSrsc ilock(ip); 233*bcca6c6bSrsc ip->ref++; 234*bcca6c6bSrsc iunlock(ip); 235*bcca6c6bSrsc return ip; 236*bcca6c6bSrsc } 237*bcca6c6bSrsc 238*bcca6c6bSrsc // Caller holds reference to unlocked ip. 239*bcca6c6bSrsc // Drop reference. 240*bcca6c6bSrsc void 241*bcca6c6bSrsc idecref(struct inode *ip) 242*bcca6c6bSrsc { 243*bcca6c6bSrsc ilock(ip); 244*bcca6c6bSrsc iput(ip); 245*bcca6c6bSrsc } 246*bcca6c6bSrsc 247*bcca6c6bSrsc // Allocate a new inode with the given type on device dev. 248e8d11c2eSkaashoek struct inode* 249e8d11c2eSkaashoek ialloc(uint dev, short type) 250e8d11c2eSkaashoek { 251e8d11c2eSkaashoek struct inode *ip; 2527d4aef6cSrsc struct dinode *dip; 253e8d11c2eSkaashoek struct superblock *sb; 254e8d11c2eSkaashoek int ninodes; 255e8d11c2eSkaashoek int inum; 256e8d11c2eSkaashoek struct buf *bp; 257e8d11c2eSkaashoek 258e8d11c2eSkaashoek bp = bread(dev, 1); 25924111398Skaashoek sb = (struct superblock*)bp->data; 260e8d11c2eSkaashoek ninodes = sb->ninodes; 261e8d11c2eSkaashoek brelse(bp); 262e8d11c2eSkaashoek 263e8d11c2eSkaashoek for(inum = 1; inum < ninodes; inum++) { // loop over inode blocks 26424111398Skaashoek bp = bread(dev, IBLOCK(inum)); 265e8d11c2eSkaashoek dip = &((struct dinode*)(bp->data))[inum % IPB]; 266e8d11c2eSkaashoek if(dip->type == 0) { // a free inode 2672aa4c3bcSrtm memset(dip, 0, sizeof(*dip)); 268e8d11c2eSkaashoek dip->type = type; 26905e97551Srtm bwrite(bp, IBLOCK(inum)); // mark it allocated on the disk 270e8d11c2eSkaashoek brelse(bp); 271e8d11c2eSkaashoek ip = iget(dev, inum); 272e8d11c2eSkaashoek return ip; 273e8d11c2eSkaashoek } 27495c07f82Srsc brelse(bp); 27595c07f82Srsc } 27695c07f82Srsc panic("ialloc: no inodes"); 27795c07f82Srsc } 278e8d11c2eSkaashoek 279*bcca6c6bSrsc // Copy inode, which has changed, from memory to disk. 280*bcca6c6bSrsc void 281*bcca6c6bSrsc iupdate(struct inode *ip) 282*bcca6c6bSrsc { 283*bcca6c6bSrsc struct buf *bp; 284*bcca6c6bSrsc struct dinode *dip; 285*bcca6c6bSrsc 286*bcca6c6bSrsc bp = bread(ip->dev, IBLOCK(ip->inum)); 287*bcca6c6bSrsc dip = &((struct dinode*)(bp->data))[ip->inum % IPB]; 288*bcca6c6bSrsc dip->type = ip->type; 289*bcca6c6bSrsc dip->major = ip->major; 290*bcca6c6bSrsc dip->minor = ip->minor; 291*bcca6c6bSrsc dip->nlink = ip->nlink; 292*bcca6c6bSrsc dip->size = ip->size; 293*bcca6c6bSrsc memmove(dip->addrs, ip->addrs, sizeof(ip->addrs)); 294*bcca6c6bSrsc bwrite(bp, IBLOCK(ip->inum)); 295*bcca6c6bSrsc brelse(bp); 296*bcca6c6bSrsc } 297*bcca6c6bSrsc 298*bcca6c6bSrsc // Free (delete) the given inode. 299*bcca6c6bSrsc // Caller must have ip locked. 30028d9ef04Skaashoek static void 30124437cd5Skaashoek ifree(struct inode *ip) 302e8d11c2eSkaashoek { 30328d9ef04Skaashoek ip->type = 0; 30428d9ef04Skaashoek iupdate(ip); 305e8d11c2eSkaashoek } 306e8d11c2eSkaashoek 307*bcca6c6bSrsc // Inode contents 308*bcca6c6bSrsc // 309*bcca6c6bSrsc // The contents (data) associated with each inode is stored 310*bcca6c6bSrsc // in a sequence of blocks on the disk. The first NDIRECT blocks 311*bcca6c6bSrsc // are stored in ip->addrs[]. The next NINDIRECT blocks are 312*bcca6c6bSrsc // listed in the block ip->addrs[INDIRECT]. 3139d3fb671Srtm 314bb207a1dSrsc // Return the disk block address of the nth block in inode ip. 315*bcca6c6bSrsc // If there is no such block: if alloc is set, allocate one, else return -1. 31622bac2cbSkaashoek uint 317*bcca6c6bSrsc bmap(struct inode *ip, uint bn, int alloc) 31822bac2cbSkaashoek { 319*bcca6c6bSrsc uint addr, *a; 320*bcca6c6bSrsc struct buf *bp; 32122bac2cbSkaashoek 322ea2909b6Skaashoek if(bn < NDIRECT) { 323*bcca6c6bSrsc if((addr = ip->addrs[bn]) == 0) { 324*bcca6c6bSrsc if(!alloc) 325*bcca6c6bSrsc return -1; 326*bcca6c6bSrsc ip->addrs[bn] = addr = balloc(ip->dev); 327ea2909b6Skaashoek } 328*bcca6c6bSrsc return addr; 329*bcca6c6bSrsc } 330*bcca6c6bSrsc bn -= NDIRECT; 331*bcca6c6bSrsc 332*bcca6c6bSrsc if(bn < NINDIRECT) { 333*bcca6c6bSrsc // Load indirect block, allocating if necessary. 334*bcca6c6bSrsc if((addr = ip->addrs[INDIRECT]) == 0) { 335*bcca6c6bSrsc if(!alloc) 336*bcca6c6bSrsc return -1; 337*bcca6c6bSrsc ip->addrs[INDIRECT] = addr = balloc(ip->dev); 338*bcca6c6bSrsc } 339*bcca6c6bSrsc bp = bread(ip->dev, addr); 340*bcca6c6bSrsc a = (uint*)bp->data; 341*bcca6c6bSrsc 342*bcca6c6bSrsc if((addr = a[bn]) == 0) { 343*bcca6c6bSrsc if(!alloc) { 344*bcca6c6bSrsc brelse(bp); 345*bcca6c6bSrsc return -1; 346*bcca6c6bSrsc } 347*bcca6c6bSrsc a[bn] = addr = balloc(ip->dev); 348*bcca6c6bSrsc bwrite(bp, ip->addrs[INDIRECT]); 349*bcca6c6bSrsc } 350*bcca6c6bSrsc brelse(bp); 351*bcca6c6bSrsc return addr; 35222bac2cbSkaashoek } 35322bac2cbSkaashoek 354*bcca6c6bSrsc panic("bmap: out of range"); 355*bcca6c6bSrsc } 356*bcca6c6bSrsc 357*bcca6c6bSrsc // Truncate inode (discard contents). 35822bac2cbSkaashoek void 3592aa4c3bcSrtm itrunc(struct inode *ip) 36022bac2cbSkaashoek { 361ea2909b6Skaashoek int i, j; 362*bcca6c6bSrsc struct buf *bp; 3637d4aef6cSrsc uint *a; 36422bac2cbSkaashoek 365*bcca6c6bSrsc for(i = 0; i < NDIRECT; i++) { 366*bcca6c6bSrsc if(ip->addrs[i]) { 36722bac2cbSkaashoek bfree(ip->dev, ip->addrs[i]); 36822bac2cbSkaashoek ip->addrs[i] = 0; 36922bac2cbSkaashoek } 37022bac2cbSkaashoek } 371*bcca6c6bSrsc 372*bcca6c6bSrsc if(ip->addrs[INDIRECT]) { 373*bcca6c6bSrsc bp = bread(ip->dev, ip->addrs[INDIRECT]); 374*bcca6c6bSrsc a = (uint*)bp->data; 375*bcca6c6bSrsc for(j = 0; j < NINDIRECT; j++) { 376*bcca6c6bSrsc if(a[j]) 377*bcca6c6bSrsc bfree(ip->dev, a[j]); 378*bcca6c6bSrsc } 379*bcca6c6bSrsc brelse(bp); 380*bcca6c6bSrsc ip->addrs[INDIRECT] = 0; 381*bcca6c6bSrsc } 382*bcca6c6bSrsc 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 398bb207a1dSrsc // Read data from inode. 399c59361f1Srtm int 40017a85657Srtm readi(struct inode *ip, char *dst, uint off, uint n) 401c59361f1Srtm { 402*bcca6c6bSrsc 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 411*bcca6c6bSrsc if(off + n < off) 412*bcca6c6bSrsc return -1; 413*bcca6c6bSrsc if(off + n > ip->size) 414*bcca6c6bSrsc n = ip->size - off; 415*bcca6c6bSrsc 416*bcca6c6bSrsc for(tot=0; tot<n; tot+=m, off+=m, dst+=m) { 417*bcca6c6bSrsc bp = bread(ip->dev, bmap(ip, off/BSIZE, 0)); 418*bcca6c6bSrsc m = min(n - tot, BSIZE - off%BSIZE); 419*bcca6c6bSrsc memmove(dst, bp->data + off%BSIZE, m); 420c59361f1Srtm brelse(bp); 421c59361f1Srtm } 422*bcca6c6bSrsc return n; 423ea2909b6Skaashoek } 424ea2909b6Skaashoek 425bb207a1dSrsc // Write data to inode. 426ea2909b6Skaashoek int 427*bcca6c6bSrsc writei(struct inode *ip, char *src, uint off, uint n) 4286fa5ffb5Skaashoek { 429*bcca6c6bSrsc uint tot, m; 4307d4aef6cSrsc struct buf *bp; 4317d4aef6cSrsc 4326fa5ffb5Skaashoek if(ip->type == T_DEV) { 4331dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].write) 434939f9edeSkaashoek return -1; 435*bcca6c6bSrsc return devsw[ip->major].write(ip->minor, src, n); 4367d4aef6cSrsc } 4377d4aef6cSrsc 438*bcca6c6bSrsc if(off + n < off) 439*bcca6c6bSrsc return -1; 440*bcca6c6bSrsc if(off + n > MAXFILE*BSIZE) 441*bcca6c6bSrsc n = MAXFILE*BSIZE - off; 442*bcca6c6bSrsc 443*bcca6c6bSrsc for(tot=0; tot<n; tot+=m, off+=m, src+=m) { 444*bcca6c6bSrsc bp = bread(ip->dev, bmap(ip, off/BSIZE, 1)); 445*bcca6c6bSrsc m = min(n - tot, BSIZE - off%BSIZE); 446*bcca6c6bSrsc memmove(bp->data + off%BSIZE, src, m); 447*bcca6c6bSrsc bwrite(bp, bmap(ip, off/BSIZE, 0)); 44828d9ef04Skaashoek brelse(bp); 44928d9ef04Skaashoek } 450*bcca6c6bSrsc 451*bcca6c6bSrsc if(n > 0 && off > ip->size) { 45248b82470Srsc ip->size = off; 45328d9ef04Skaashoek iupdate(ip); 45428d9ef04Skaashoek } 455*bcca6c6bSrsc return n; 4566fa5ffb5Skaashoek } 4576fa5ffb5Skaashoek 458*bcca6c6bSrsc // Directories 459*bcca6c6bSrsc // 460*bcca6c6bSrsc // Directories are just inodes (files) filled with dirent structures. 461*bcca6c6bSrsc 462*bcca6c6bSrsc // Look for a directory entry in a directory. 463*bcca6c6bSrsc // If not found, return -1. 464*bcca6c6bSrsc // If found: 465*bcca6c6bSrsc // set *poff to the byte offset of the directory entry 466*bcca6c6bSrsc // set *pinum to the inode number 467*bcca6c6bSrsc // return 0. 468*bcca6c6bSrsc static int 469*bcca6c6bSrsc dirlookup(struct inode *dp, char *name, int namelen, uint *poff, uint *pinum) 470*bcca6c6bSrsc { 471*bcca6c6bSrsc uint off; 472*bcca6c6bSrsc struct buf *bp; 473*bcca6c6bSrsc struct dirent *de; 474*bcca6c6bSrsc 475*bcca6c6bSrsc if(dp->type != T_DIR) 476*bcca6c6bSrsc return -1; 477*bcca6c6bSrsc 478*bcca6c6bSrsc for(off = 0; off < dp->size; off += BSIZE){ 479*bcca6c6bSrsc bp = bread(dp->dev, bmap(dp, off / BSIZE, 0)); 480*bcca6c6bSrsc for(de = (struct dirent*) bp->data; 481*bcca6c6bSrsc de < (struct dirent*) (bp->data + BSIZE); 482*bcca6c6bSrsc de++){ 483*bcca6c6bSrsc if(de->inum == 0) 484*bcca6c6bSrsc continue; 485*bcca6c6bSrsc if(memcmp(name, de->name, namelen) == 0 && 486*bcca6c6bSrsc (namelen == DIRSIZ || de->name[namelen]== 0)){ 487*bcca6c6bSrsc // entry matches path element 488*bcca6c6bSrsc *poff = off + (uchar*)de - bp->data; 489*bcca6c6bSrsc *pinum = de->inum; 490*bcca6c6bSrsc brelse(bp); 491*bcca6c6bSrsc return 0; 492*bcca6c6bSrsc } 493*bcca6c6bSrsc } 494*bcca6c6bSrsc brelse(bp); 495*bcca6c6bSrsc } 496*bcca6c6bSrsc return -1; 497*bcca6c6bSrsc } 498*bcca6c6bSrsc 499*bcca6c6bSrsc // Write a new directory entry (name, ino) into the directory dp. 500*bcca6c6bSrsc // Caller must have locked dp. 501*bcca6c6bSrsc void 502*bcca6c6bSrsc dirwrite(struct inode *dp, char *name, uint ino) 503*bcca6c6bSrsc { 504*bcca6c6bSrsc int i, off; 505*bcca6c6bSrsc struct dirent de; 506*bcca6c6bSrsc 507*bcca6c6bSrsc // Look for an empty dirent. 508*bcca6c6bSrsc for(off = 0; off < dp->size; off += sizeof(de)){ 509*bcca6c6bSrsc if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 510*bcca6c6bSrsc panic("dirwrite read"); 511*bcca6c6bSrsc if(de.inum == 0) 512*bcca6c6bSrsc break; 513*bcca6c6bSrsc } 514*bcca6c6bSrsc 515*bcca6c6bSrsc de.inum = ino; 516*bcca6c6bSrsc for(i = 0; i < DIRSIZ && name[i]; i++) 517*bcca6c6bSrsc de.name[i] = name[i]; 518*bcca6c6bSrsc for(; i < DIRSIZ; i++) 519*bcca6c6bSrsc de.name[i] = '\0'; 520*bcca6c6bSrsc 521*bcca6c6bSrsc if(writei(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 522*bcca6c6bSrsc panic("dirwrite"); 523*bcca6c6bSrsc } 524*bcca6c6bSrsc 525*bcca6c6bSrsc // Paths 526*bcca6c6bSrsc 527ab5c2dbbSrsc // Skip over the next path element in path, 528ab5c2dbbSrsc // saving it in *name and its length in *len. 529ab5c2dbbSrsc // Return a pointer to the element after that 530ab5c2dbbSrsc // (after any trailing slashes). 531ab5c2dbbSrsc // Thus the caller can check whether *path=='\0' 532ab5c2dbbSrsc // to see whether the name just removed was 533ab5c2dbbSrsc // the last one. 534ab5c2dbbSrsc // If there is no name to remove, return 0. 535ab5c2dbbSrsc // 536ab5c2dbbSrsc // Examples: 537ab5c2dbbSrsc // skipelem("a/bb/c") = "bb/c", with *name = "a/bb/c", len=1 538ab5c2dbbSrsc // skipelem("///a/bb") = "b", with *name="a/bb", len=1 539ab5c2dbbSrsc // skipelem("") = skipelem("////") = 0 540ab5c2dbbSrsc // 541ab5c2dbbSrsc static char* 542ab5c2dbbSrsc skipelem(char *path, char **name, int *len) 543ab5c2dbbSrsc { 544ab5c2dbbSrsc while(*path == '/') 545ab5c2dbbSrsc path++; 546ab5c2dbbSrsc if(*path == 0) 547ab5c2dbbSrsc return 0; 548ab5c2dbbSrsc *name = path; 549ab5c2dbbSrsc while(*path != '/' && *path != 0) 550ab5c2dbbSrsc path++; 551ab5c2dbbSrsc *len = path - *name; 552ab5c2dbbSrsc while(*path == '/') 553ab5c2dbbSrsc path++; 554ab5c2dbbSrsc return path; 555ab5c2dbbSrsc } 556ab5c2dbbSrsc 557211ff0c6Srtm // look up a path name, in one of three modes. 558211ff0c6Srtm // NAMEI_LOOKUP: return locked target inode. 559211ff0c6Srtm // NAMEI_CREATE: return locked parent inode. 5605051da6dSrtm // return 0 if name does exist. 5615051da6dSrtm // *ret_last points to last path component (i.e. new file name). 5625051da6dSrtm // *ret_ip points to the the name that did exist, if it did. 5635051da6dSrtm // *ret_ip and *ret_last may be zero even if return value is zero. 564211ff0c6Srtm // NAMEI_DELETE: return locked parent inode, offset of dirent in *ret_off. 565211ff0c6Srtm // return 0 if name doesn't exist. 5669d3fb671Srtm struct inode* 5670cfc7290Srsc namei(char *path, int mode, uint *ret_off, 5680cfc7290Srsc char **ret_last, struct inode **ret_ip) 5699d3fb671Srtm { 5709d3fb671Srtm struct inode *dp; 571ab5c2dbbSrsc char *name; 572ab5c2dbbSrsc int namelen; 573bc011703Srsc uint off, dev, inum; 5749d3fb671Srtm 5755051da6dSrtm if(ret_off) 5765051da6dSrtm *ret_off = 0xffffffff; 5775051da6dSrtm if(ret_last) 5785051da6dSrtm *ret_last = 0; 5795051da6dSrtm if(ret_ip) 5805051da6dSrtm *ret_ip = 0; 5815051da6dSrtm 582ab5c2dbbSrsc if(*path == '/') 583*bcca6c6bSrsc dp = igetroot(); 5848787cd01Skaashoek else { 585bc011703Srsc dp = iincref(cp->cwd); 5868787cd01Skaashoek ilock(dp); 5878787cd01Skaashoek } 5889d3fb671Srtm 589ab5c2dbbSrsc while((path = skipelem(path, &name, &namelen)) != 0){ 590ab5c2dbbSrsc // Truncate names in path to DIRSIZ chars. 591ab5c2dbbSrsc if(namelen > DIRSIZ) 592ab5c2dbbSrsc namelen = DIRSIZ; 5939d3fb671Srtm 594ab5c2dbbSrsc if(dp->type != T_DIR) 595ab5c2dbbSrsc goto fail; 596ab5c2dbbSrsc 597*bcca6c6bSrsc if(dirlookup(dp, name, namelen, &off, &inum) < 0){ 598ab5c2dbbSrsc if(mode == NAMEI_CREATE && *path == '\0'){ 599ab5c2dbbSrsc *ret_last = name; 600ab5c2dbbSrsc return dp; 601ab5c2dbbSrsc } 602ab5c2dbbSrsc goto fail; 603ab5c2dbbSrsc } 604ab5c2dbbSrsc 605ab5c2dbbSrsc if(mode == NAMEI_DELETE && *path == '\0'){ 606ab5c2dbbSrsc // can't unlink . and .. 607ab5c2dbbSrsc if((namelen == 1 && memcmp(name, ".", 1) == 0) || 608ab5c2dbbSrsc (namelen == 2 && memcmp(name, "..", 2) == 0)){ 609ab5c2dbbSrsc goto fail; 610ab5c2dbbSrsc } 611ab5c2dbbSrsc *ret_off = off; 612ab5c2dbbSrsc return dp; 613ab5c2dbbSrsc } 614ab5c2dbbSrsc 615ab5c2dbbSrsc dev = dp->dev; 616ab5c2dbbSrsc iput(dp); 617ab5c2dbbSrsc dp = iget(dev, inum); 618ab5c2dbbSrsc if(dp->type == 0 || dp->nlink < 1) 619ab5c2dbbSrsc panic("namei"); 620ab5c2dbbSrsc } 621ab5c2dbbSrsc 622211ff0c6Srtm if(mode == NAMEI_LOOKUP) 6239d3fb671Srtm return dp; 6245051da6dSrtm if(mode == NAMEI_CREATE && ret_ip){ 6255051da6dSrtm *ret_ip = dp; 6265051da6dSrtm return 0; 6275051da6dSrtm } 628ab5c2dbbSrsc goto fail; 629ab5c2dbbSrsc 630ab5c2dbbSrsc fail: 631211ff0c6Srtm iput(dp); 632211ff0c6Srtm return 0; 6330633b971Skaashoek } 6349d3fb671Srtm 635b6095304Srsc // Create the path and return its locked inode structure. 636bb207a1dSrsc // If cp already exists, return 0. 637e8d11c2eSkaashoek struct inode* 638b6095304Srsc mknod(char *path, short type, short major, short minor) 639e8d11c2eSkaashoek { 6400633b971Skaashoek struct inode *ip, *dp; 6415051da6dSrtm char *last; 642e8d11c2eSkaashoek 643b6095304Srsc if((dp = namei(path, NAMEI_CREATE, 0, &last, 0)) == 0) 6440633b971Skaashoek return 0; 645211ff0c6Srtm 6465051da6dSrtm ip = mknod1(dp, last, type, major, minor); 6475051da6dSrtm 6485051da6dSrtm iput(dp); 6495051da6dSrtm 6505051da6dSrtm return ip; 6515051da6dSrtm } 6525051da6dSrtm 653bb207a1dSrsc // Create a new inode named name inside dp 654bb207a1dSrsc // and return its locked inode structure. 655bb207a1dSrsc // If name already exists, return 0. 6565051da6dSrtm struct inode* 6575051da6dSrtm mknod1(struct inode *dp, char *name, short type, short major, short minor) 6585051da6dSrtm { 6595051da6dSrtm struct inode *ip; 6605051da6dSrtm 661e8d11c2eSkaashoek ip = ialloc(dp->dev, type); 6622aa4c3bcSrtm if(ip == 0) 6630633b971Skaashoek return 0; 664e8d11c2eSkaashoek ip->major = major; 665e8d11c2eSkaashoek ip->minor = minor; 6666c0e444fSkaashoek ip->size = 0; 6677ce01cf9Srtm ip->nlink = 1; 6686c0e444fSkaashoek 6696c0e444fSkaashoek iupdate(ip); // write new inode to disk 670e8d11c2eSkaashoek 671*bcca6c6bSrsc dirwrite(dp, name, ip->inum); 6725051da6dSrtm 673e8d11c2eSkaashoek return ip; 674e8d11c2eSkaashoek } 67524437cd5Skaashoek 676bb207a1dSrsc // Unlink the inode named cp. 67724437cd5Skaashoek int 678b6095304Srsc unlink(char *path) 67924437cd5Skaashoek { 680211ff0c6Srtm struct inode *ip, *dp; 681211ff0c6Srtm struct dirent de; 68217e3cf15Srtm uint off, inum, dev; 68324437cd5Skaashoek 684b6095304Srsc dp = namei(path, NAMEI_DELETE, &off, 0, 0); 6855051da6dSrtm if(dp == 0) 68624437cd5Skaashoek return -1; 68724437cd5Skaashoek 68817e3cf15Srtm dev = dp->dev; 68917e3cf15Srtm 69017e3cf15Srtm if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de) || de.inum == 0) 691211ff0c6Srtm panic("unlink no entry"); 69217e3cf15Srtm 693ab5c2dbbSrsc // Cannot remove "." or ".." - the 2 and 3 count the trailing NUL. 694ab5c2dbbSrsc if(memcmp(de.name, ".", 2) == 0 || memcmp(de.name, "..", 3) == 0){ 695ab5c2dbbSrsc iput(dp); 696ab5c2dbbSrsc return -1; 697ab5c2dbbSrsc } 698ab5c2dbbSrsc 699211ff0c6Srtm inum = de.inum; 70024437cd5Skaashoek 701211ff0c6Srtm memset(&de, 0, sizeof(de)); 702211ff0c6Srtm if(writei(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 703211ff0c6Srtm panic("unlink dir write"); 70424437cd5Skaashoek 70524437cd5Skaashoek iupdate(dp); 70624437cd5Skaashoek iput(dp); 707211ff0c6Srtm 70817e3cf15Srtm ip = iget(dev, inum); 709211ff0c6Srtm 710bcfb84b6Srtm if(ip->nlink < 1) 711bcfb84b6Srtm panic("unlink nlink < 1"); 712bcfb84b6Srtm 713211ff0c6Srtm ip->nlink--; 714211ff0c6Srtm 715211ff0c6Srtm iupdate(ip); 71622bac2cbSkaashoek iput(ip); 717211ff0c6Srtm 71824437cd5Skaashoek return 0; 71924437cd5Skaashoek } 7209e5970d5Srtm 721bb207a1dSrsc // Create the path new as a link to the same inode as old. 7229e5970d5Srtm int 7239e5970d5Srtm link(char *name1, char *name2) 7249e5970d5Srtm { 725211ff0c6Srtm struct inode *ip, *dp; 7265051da6dSrtm char *last; 7279e5970d5Srtm 7285051da6dSrtm if((ip = namei(name1, NAMEI_LOOKUP, 0, 0, 0)) == 0) 7299e5970d5Srtm return -1; 730211ff0c6Srtm if(ip->type == T_DIR){ 731211ff0c6Srtm iput(ip); 732211ff0c6Srtm return -1; 733211ff0c6Srtm } 7349e5970d5Srtm 735211ff0c6Srtm iunlock(ip); 736211ff0c6Srtm 7375051da6dSrtm if((dp = namei(name2, NAMEI_CREATE, 0, &last, 0)) == 0) { 738211ff0c6Srtm idecref(ip); 739211ff0c6Srtm return -1; 740211ff0c6Srtm } 741211ff0c6Srtm if(dp->dev != ip->dev){ 742211ff0c6Srtm idecref(ip); 743211ff0c6Srtm iput(dp); 744211ff0c6Srtm return -1; 745211ff0c6Srtm } 746211ff0c6Srtm 747211ff0c6Srtm ilock(ip); 748be29b8e2Srsc ip->nlink++; 7499e5970d5Srtm iupdate(ip); 7509e5970d5Srtm 751*bcca6c6bSrsc dirwrite(dp, last, ip->inum); 7529e5970d5Srtm iput(dp); 7539e5970d5Srtm iput(ip); 7549e5970d5Srtm 7559e5970d5Srtm return 0; 7569e5970d5Srtm } 757