111a9947fSrtm #include "types.h" 21f544842Skaashoek #include "stat.h" 311a9947fSrtm #include "param.h" 411a9947fSrtm #include "x86.h" 511a9947fSrtm #include "mmu.h" 611a9947fSrtm #include "proc.h" 711a9947fSrtm #include "defs.h" 811a9947fSrtm #include "spinlock.h" 911a9947fSrtm #include "buf.h" 1011a9947fSrtm #include "fs.h" 1111a9947fSrtm #include "fsvar.h" 126fa5ffb5Skaashoek #include "dev.h" 1311a9947fSrtm 14bb207a1dSrsc // Inode table. The inode table is an in-memory cache of the 15bb207a1dSrsc // on-disk inode structures. If an inode in the table has a non-zero 16bb207a1dSrsc // reference count, then some open files refer to it and it must stay 17bb207a1dSrsc // in memory. If an inode has a zero reference count, it is only in 18bb207a1dSrsc // memory as a cache in hopes of being used again (avoiding a disk read). 19bb207a1dSrsc // Any inode with reference count zero can be evicted from the table. 20bb207a1dSrsc // 21bb207a1dSrsc // In addition to having a reference count, inodes can be marked busy 22bb207a1dSrsc // (just like bufs), meaning that some code has logically locked the 23bb207a1dSrsc // inode, and others are not allowed to look at it. 24bb207a1dSrsc // This locking can last for a long 25bb207a1dSrsc // time (for example, if the inode is busy during a disk access), 26bb207a1dSrsc // so we don't use spin locks. Instead, if a process wants to use 27bb207a1dSrsc // a particular inode, it must sleep(ip) to wait for it to be not busy. 28bb207a1dSrsc // See iget below. 2911a9947fSrtm struct inode inode[NINODE]; 305be0039cSrtm struct spinlock inode_table_lock; 3111a9947fSrtm 329d3fb671Srtm uint rootdev = 1; 339d3fb671Srtm 345be0039cSrtm void 355be0039cSrtm iinit(void) 365be0039cSrtm { 375be0039cSrtm initlock(&inode_table_lock, "inode_table"); 385be0039cSrtm } 395be0039cSrtm 40f5527388Srsc // Allocate a disk block. 4124111398Skaashoek static uint 4224111398Skaashoek balloc(uint dev) 4324111398Skaashoek { 4424111398Skaashoek int b; 4524111398Skaashoek struct buf *bp; 4624111398Skaashoek struct superblock *sb; 4728d9ef04Skaashoek int bi = 0; 4824111398Skaashoek int size; 4924111398Skaashoek int ninodes; 5024111398Skaashoek uchar m; 5124111398Skaashoek 5224111398Skaashoek bp = bread(dev, 1); 5324111398Skaashoek sb = (struct superblock*) bp->data; 5424111398Skaashoek size = sb->size; 5524111398Skaashoek ninodes = sb->ninodes; 5624111398Skaashoek 5724111398Skaashoek for(b = 0; b < size; b++) { 5824111398Skaashoek if(b % BPB == 0) { 5924111398Skaashoek brelse(bp); 6024111398Skaashoek bp = bread(dev, BBLOCK(b, ninodes)); 6124111398Skaashoek } 6224111398Skaashoek bi = b % BPB; 6324111398Skaashoek m = 0x1 << (bi % 8); 6424111398Skaashoek if((bp->data[bi/8] & m) == 0) { // is block free? 6524111398Skaashoek break; 6624111398Skaashoek } 6724111398Skaashoek } 6824111398Skaashoek if(b >= size) 692aa4c3bcSrtm panic("balloc: out of blocks"); 7024111398Skaashoek 7124111398Skaashoek bp->data[bi/8] |= 0x1 << (bi % 8); 7205e97551Srtm bwrite(bp, BBLOCK(b, ninodes)); // mark it allocated on disk 7328d9ef04Skaashoek brelse(bp); 7424111398Skaashoek return b; 7524111398Skaashoek } 7624111398Skaashoek 77bb207a1dSrsc // Free a disk block. 7828d9ef04Skaashoek static void 7928d9ef04Skaashoek bfree(int dev, uint b) 8028d9ef04Skaashoek { 8128d9ef04Skaashoek struct buf *bp; 8228d9ef04Skaashoek struct superblock *sb; 8328d9ef04Skaashoek int bi; 8428d9ef04Skaashoek int ninodes; 8528d9ef04Skaashoek uchar m; 8628d9ef04Skaashoek 8728d9ef04Skaashoek bp = bread(dev, 1); 8828d9ef04Skaashoek sb = (struct superblock*) bp->data; 8928d9ef04Skaashoek ninodes = sb->ninodes; 9028d9ef04Skaashoek brelse(bp); 9128d9ef04Skaashoek 92c372e8dcSkaashoek bp = bread(dev, b); 93c372e8dcSkaashoek memset(bp->data, 0, BSIZE); 94c372e8dcSkaashoek bwrite(bp, b); 95c372e8dcSkaashoek brelse(bp); 96c372e8dcSkaashoek 9728d9ef04Skaashoek bp = bread(dev, BBLOCK(b, ninodes)); 9828d9ef04Skaashoek bi = b % BPB; 9928d9ef04Skaashoek m = ~(0x1 << (bi %8)); 10028d9ef04Skaashoek bp->data[bi/8] &= m; 10105e97551Srtm bwrite(bp, BBLOCK(b, ninodes)); // mark it free on disk 10228d9ef04Skaashoek brelse(bp); 10328d9ef04Skaashoek } 10424111398Skaashoek 105f5527388Srsc // Find the inode with number inum on device dev 106f5527388Srsc // and return an in-memory copy. Loads the inode 107f5527388Srsc // from disk into the in-core table if necessary. 108f5527388Srsc // The returned inode has busy set and has its ref count incremented. 109f5527388Srsc // Caller must iput the return value when done with it. 11011a9947fSrtm struct inode* 11111a9947fSrtm iget(uint dev, uint inum) 11211a9947fSrtm { 11317e3cf15Srtm struct inode *ip, *nip; 11411a9947fSrtm struct dinode *dip; 11511a9947fSrtm struct buf *bp; 11611a9947fSrtm 11711a9947fSrtm acquire(&inode_table_lock); 11811a9947fSrtm 11911a9947fSrtm loop: 12017e3cf15Srtm nip = 0; 12111a9947fSrtm for(ip = &inode[0]; ip < &inode[NINODE]; ip++){ 1220d6bbd31Srsc if(ip->ref > 0 && ip->dev == dev && ip->inum == inum){ 12311a9947fSrtm if(ip->busy){ 12411a9947fSrtm sleep(ip, &inode_table_lock); 125bb207a1dSrsc // Since we droped inode_table_lock, ip might have been reused 126bb207a1dSrsc // for some other inode entirely. Must start the scan over, 127bb207a1dSrsc // and hopefully this time we will find the inode we want 128bb207a1dSrsc // and it will not be busy. 12911a9947fSrtm goto loop; 13011a9947fSrtm } 1310d6bbd31Srsc ip->ref++; 13217a85657Srtm ip->busy = 1; 13311a9947fSrtm release(&inode_table_lock); 13411a9947fSrtm return ip; 13511a9947fSrtm } 1360d6bbd31Srsc if(nip == 0 && ip->ref == 0) 13711a9947fSrtm nip = ip; 13811a9947fSrtm } 13911a9947fSrtm 14011a9947fSrtm if(nip == 0) 14132eea766Srsc panic("iget: no inodes"); 14211a9947fSrtm 14311a9947fSrtm nip->dev = dev; 14411a9947fSrtm nip->inum = inum; 1450d6bbd31Srsc nip->ref = 1; 14611a9947fSrtm nip->busy = 1; 14711a9947fSrtm 14811a9947fSrtm release(&inode_table_lock); 14911a9947fSrtm 15024111398Skaashoek bp = bread(dev, IBLOCK(inum)); 15111a9947fSrtm dip = &((struct dinode*)(bp->data))[inum % IPB]; 15211a9947fSrtm nip->type = dip->type; 153e8d11c2eSkaashoek nip->major = dip->major; 154e8d11c2eSkaashoek nip->minor = dip->minor; 15511a9947fSrtm nip->nlink = dip->nlink; 15611a9947fSrtm nip->size = dip->size; 15711a9947fSrtm memmove(nip->addrs, dip->addrs, sizeof(nip->addrs)); 15811a9947fSrtm brelse(bp); 15911a9947fSrtm 16011a9947fSrtm return nip; 16111a9947fSrtm } 16211a9947fSrtm 1638e1d1ec9Skaashoek // Copy inode in memory, which has changed, to disk. 164bb207a1dSrsc // Caller must have locked ip. 16528d9ef04Skaashoek void 16628d9ef04Skaashoek iupdate(struct inode *ip) 16728d9ef04Skaashoek { 16828d9ef04Skaashoek struct buf *bp; 16928d9ef04Skaashoek struct dinode *dip; 17028d9ef04Skaashoek 17128d9ef04Skaashoek bp = bread(ip->dev, IBLOCK(ip->inum)); 17228d9ef04Skaashoek dip = &((struct dinode*)(bp->data))[ip->inum % IPB]; 17328d9ef04Skaashoek dip->type = ip->type; 17428d9ef04Skaashoek dip->major = ip->major; 17528d9ef04Skaashoek dip->minor = ip->minor; 17628d9ef04Skaashoek dip->nlink = ip->nlink; 17728d9ef04Skaashoek dip->size = ip->size; 17828d9ef04Skaashoek memmove(dip->addrs, ip->addrs, sizeof(ip->addrs)); 17905e97551Srtm bwrite(bp, IBLOCK(ip->inum)); // mark it allocated on the disk 18028d9ef04Skaashoek brelse(bp); 18128d9ef04Skaashoek } 18228d9ef04Skaashoek 183bb207a1dSrsc // Allocate a new inode with the given type 184bb207a1dSrsc // from the file system on device dev. 185e8d11c2eSkaashoek struct inode* 186e8d11c2eSkaashoek ialloc(uint dev, short type) 187e8d11c2eSkaashoek { 188e8d11c2eSkaashoek struct inode *ip; 189e8d11c2eSkaashoek struct dinode *dip = 0; 190e8d11c2eSkaashoek struct superblock *sb; 191e8d11c2eSkaashoek int ninodes; 192e8d11c2eSkaashoek int inum; 193e8d11c2eSkaashoek struct buf *bp; 194e8d11c2eSkaashoek 195e8d11c2eSkaashoek bp = bread(dev, 1); 19624111398Skaashoek sb = (struct superblock*) bp->data; 197e8d11c2eSkaashoek ninodes = sb->ninodes; 198e8d11c2eSkaashoek brelse(bp); 199e8d11c2eSkaashoek 200e8d11c2eSkaashoek for(inum = 1; inum < ninodes; inum++) { // loop over inode blocks 20124111398Skaashoek bp = bread(dev, IBLOCK(inum)); 202e8d11c2eSkaashoek dip = &((struct dinode*)(bp->data))[inum % IPB]; 203e8d11c2eSkaashoek if(dip->type == 0) { // a free inode 2042aa4c3bcSrtm memset(dip, 0, sizeof(*dip)); 205e8d11c2eSkaashoek dip->type = type; 20605e97551Srtm bwrite(bp, IBLOCK(inum)); // mark it allocated on the disk 207e8d11c2eSkaashoek brelse(bp); 208e8d11c2eSkaashoek ip = iget(dev, inum); 209e8d11c2eSkaashoek return ip; 210e8d11c2eSkaashoek } 21195c07f82Srsc brelse(bp); 21295c07f82Srsc } 21395c07f82Srsc panic("ialloc: no inodes"); 21495c07f82Srsc } 215e8d11c2eSkaashoek 216bb207a1dSrsc // Free the given inode from its file system. 21728d9ef04Skaashoek static void 21824437cd5Skaashoek ifree(struct inode *ip) 219e8d11c2eSkaashoek { 22028d9ef04Skaashoek ip->type = 0; 22128d9ef04Skaashoek iupdate(ip); 222e8d11c2eSkaashoek } 223e8d11c2eSkaashoek 224bb207a1dSrsc // Lock the given inode (wait for it to be not busy, 225bb207a1dSrsc // and then ip->busy). 226bb207a1dSrsc // Caller must already hold a reference to ip. 227bb207a1dSrsc // Otherwise, if all the references to ip go away, 228bb207a1dSrsc // it might be reused underfoot. 22911a9947fSrtm void 2309d3fb671Srtm ilock(struct inode *ip) 2319d3fb671Srtm { 2320d6bbd31Srsc if(ip->ref < 1) 2339d3fb671Srtm panic("ilock"); 2349d3fb671Srtm 2359d3fb671Srtm acquire(&inode_table_lock); 2369d3fb671Srtm 2379d3fb671Srtm while(ip->busy) 2389d3fb671Srtm sleep(ip, &inode_table_lock); 2399d3fb671Srtm ip->busy = 1; 2409d3fb671Srtm 2419d3fb671Srtm release(&inode_table_lock); 2429d3fb671Srtm } 2439d3fb671Srtm 244bb207a1dSrsc // Caller holds reference to ip and has locked it. 245bb207a1dSrsc // Caller no longer needs to examine / change it. 246bb207a1dSrsc // Unlock it, but keep the reference. 2479d3fb671Srtm void 2489d3fb671Srtm iunlock(struct inode *ip) 2499d3fb671Srtm { 2500d6bbd31Srsc if(ip->busy != 1 || ip->ref < 1) 2519d3fb671Srtm panic("iunlock"); 2529d3fb671Srtm 2539d3fb671Srtm acquire(&inode_table_lock); 2549d3fb671Srtm 2559d3fb671Srtm ip->busy = 0; 2569d3fb671Srtm wakeup(ip); 2579d3fb671Srtm 2589d3fb671Srtm release(&inode_table_lock); 2599d3fb671Srtm } 2609d3fb671Srtm 261bb207a1dSrsc // Return the disk block address of the nth block in inode ip. 26222bac2cbSkaashoek uint 26322bac2cbSkaashoek bmap(struct inode *ip, uint bn) 26422bac2cbSkaashoek { 265d80b06a1Srsc uint *a, x; 266ea2909b6Skaashoek struct buf *inbp; 26722bac2cbSkaashoek 268ea2909b6Skaashoek if(bn >= MAXFILE) 26922bac2cbSkaashoek panic("bmap 1"); 270ea2909b6Skaashoek if(bn < NDIRECT) { 27122bac2cbSkaashoek x = ip->addrs[bn]; 27222bac2cbSkaashoek if(x == 0) 27322bac2cbSkaashoek panic("bmap 2"); 274ea2909b6Skaashoek } else { 2755051da6dSrtm if(ip->addrs[INDIRECT] == 0) 2765051da6dSrtm panic("bmap 3"); 2771be76685Skaashoek inbp = bread(ip->dev, ip->addrs[INDIRECT]); 278ea2909b6Skaashoek a = (uint*) inbp->data; 279ea2909b6Skaashoek x = a[bn - NDIRECT]; 280ea2909b6Skaashoek brelse(inbp); 281ea2909b6Skaashoek if(x == 0) 2825051da6dSrtm panic("bmap 4"); 283ea2909b6Skaashoek } 28422bac2cbSkaashoek return x; 28522bac2cbSkaashoek } 28622bac2cbSkaashoek 287bb207a1dSrsc // Truncate the inode ip, discarding all its data blocks. 28822bac2cbSkaashoek void 2892aa4c3bcSrtm itrunc(struct inode *ip) 29022bac2cbSkaashoek { 291ea2909b6Skaashoek int i, j; 2921be76685Skaashoek struct buf *inbp; 29322bac2cbSkaashoek 294ea2909b6Skaashoek for(i = 0; i < NADDRS; i++) { 29522bac2cbSkaashoek if(ip->addrs[i] != 0) { 296ea2909b6Skaashoek if(i == INDIRECT) { 2971be76685Skaashoek inbp = bread(ip->dev, ip->addrs[INDIRECT]); 2981be76685Skaashoek uint *a = (uint*) inbp->data; 299bcfb84b6Srtm for(j = 0; j < NINDIRECT; j++) { 300ea2909b6Skaashoek if(a[j] != 0) { 301ea2909b6Skaashoek bfree(ip->dev, a[j]); 302ea2909b6Skaashoek a[j] = 0; 303ea2909b6Skaashoek } 304ea2909b6Skaashoek } 3051be76685Skaashoek brelse(inbp); 306ea2909b6Skaashoek } 30722bac2cbSkaashoek bfree(ip->dev, ip->addrs[i]); 30822bac2cbSkaashoek ip->addrs[i] = 0; 30922bac2cbSkaashoek } 31022bac2cbSkaashoek } 31122bac2cbSkaashoek ip->size = 0; 31222bac2cbSkaashoek iupdate(ip); 31322bac2cbSkaashoek } 31422bac2cbSkaashoek 315bb207a1dSrsc // Caller holds reference to ip and has locked it, 316bb207a1dSrsc // possibly editing it. 317bb207a1dSrsc // Release lock and drop the reference. 3189d3fb671Srtm void 31911a9947fSrtm iput(struct inode *ip) 32011a9947fSrtm { 3210d6bbd31Srsc if(ip->ref < 1 || ip->busy != 1) 3229d3fb671Srtm panic("iput"); 3239d3fb671Srtm 3240d6bbd31Srsc if((ip->ref == 1) && (ip->nlink == 0)) { 3252aa4c3bcSrtm itrunc(ip); 3262aa4c3bcSrtm ifree(ip); 3272aa4c3bcSrtm } 32822bac2cbSkaashoek 32911a9947fSrtm acquire(&inode_table_lock); 33011a9947fSrtm 3310d6bbd31Srsc ip->ref -= 1; 33211a9947fSrtm ip->busy = 0; 33311a9947fSrtm wakeup(ip); 33411a9947fSrtm 33511a9947fSrtm release(&inode_table_lock); 33611a9947fSrtm } 3379d3fb671Srtm 338bb207a1dSrsc // Caller holds reference to ip but not lock. 339bb207a1dSrsc // Drop reference. 3409d3fb671Srtm void 34132630628Srtm idecref(struct inode *ip) 3429d3fb671Srtm { 343211ff0c6Srtm ilock(ip); 344211ff0c6Srtm iput(ip); 3459d3fb671Srtm } 3469d3fb671Srtm 347bb207a1dSrsc // Increment reference count for ip. 348d80b06a1Srsc // Returns ip to enable ip = iincref(ip1) idiom. 349d80b06a1Srsc struct inode* 350e958c538Skaashoek iincref(struct inode *ip) 351e958c538Skaashoek { 352e958c538Skaashoek ilock(ip); 3530d6bbd31Srsc ip->ref++; 354e958c538Skaashoek iunlock(ip); 355d80b06a1Srsc return ip; 356e958c538Skaashoek } 357e958c538Skaashoek 358bb207a1dSrsc // Copy stat information from inode. 359e958c538Skaashoek void 3601f544842Skaashoek stati(struct inode *ip, struct stat *st) 3611f544842Skaashoek { 3621dca3afbSrsc st->dev = ip->dev; 3631dca3afbSrsc st->ino = ip->inum; 3641dca3afbSrsc st->type = ip->type; 3651dca3afbSrsc st->nlink = ip->nlink; 3661dca3afbSrsc st->size = ip->size; 3671f544842Skaashoek } 3681f544842Skaashoek 36922bac2cbSkaashoek #define min(a, b) ((a) < (b) ? (a) : (b)) 37022bac2cbSkaashoek 371bb207a1dSrsc // Read data from inode. 372c59361f1Srtm int 37317a85657Srtm readi(struct inode *ip, char *dst, uint off, uint n) 374c59361f1Srtm { 375c59361f1Srtm uint target = n, n1; 376c59361f1Srtm struct buf *bp; 377c59361f1Srtm 378939f9edeSkaashoek if(ip->type == T_DEV) { 3791dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].read) 380939f9edeSkaashoek return -1; 3811dca3afbSrsc return devsw[ip->major].read(ip->minor, dst, n); 382939f9edeSkaashoek } 383939f9edeSkaashoek 384c59361f1Srtm while(n > 0 && off < ip->size){ 38524111398Skaashoek bp = bread(ip->dev, bmap(ip, off / BSIZE)); 386c59361f1Srtm n1 = min(n, ip->size - off); 38724111398Skaashoek n1 = min(n1, BSIZE - (off % BSIZE)); 38824111398Skaashoek memmove(dst, bp->data + (off % BSIZE), n1); 389c59361f1Srtm n -= n1; 390c59361f1Srtm off += n1; 391c59361f1Srtm dst += n1; 392c59361f1Srtm brelse(bp); 393c59361f1Srtm } 394c59361f1Srtm 395c59361f1Srtm return target - n; 396c59361f1Srtm } 397c59361f1Srtm 398bb207a1dSrsc // Allocate the nth block in inode ip if necessary. 3991be76685Skaashoek static int 400ea2909b6Skaashoek newblock(struct inode *ip, uint lbn) 401ea2909b6Skaashoek { 402ea2909b6Skaashoek struct buf *inbp; 403ea2909b6Skaashoek uint *inaddrs; 404ea2909b6Skaashoek uint b; 405ea2909b6Skaashoek 406ea2909b6Skaashoek if(lbn < NDIRECT) { 407ea2909b6Skaashoek if(ip->addrs[lbn] == 0) { 408ea2909b6Skaashoek b = balloc(ip->dev); 40948b82470Srsc if(b <= 0) 41048b82470Srsc return -1; 411ea2909b6Skaashoek ip->addrs[lbn] = b; 412ea2909b6Skaashoek } 413ea2909b6Skaashoek } else { 414ea2909b6Skaashoek if(ip->addrs[INDIRECT] == 0) { 415ea2909b6Skaashoek b = balloc(ip->dev); 41648b82470Srsc if(b <= 0) 41748b82470Srsc return -1; 418ea2909b6Skaashoek ip->addrs[INDIRECT] = b; 419ea2909b6Skaashoek } 4201be76685Skaashoek inbp = bread(ip->dev, ip->addrs[INDIRECT]); 421ea2909b6Skaashoek inaddrs = (uint*) inbp->data; 422ea2909b6Skaashoek if(inaddrs[lbn - NDIRECT] == 0) { 423ea2909b6Skaashoek b = balloc(ip->dev); 42448b82470Srsc if(b <= 0) 42548b82470Srsc return -1; 426ea2909b6Skaashoek inaddrs[lbn - NDIRECT] = b; 4271be76685Skaashoek bwrite(inbp, ip->addrs[INDIRECT]); 428ea2909b6Skaashoek } 429ea2909b6Skaashoek brelse(inbp); 430ea2909b6Skaashoek } 431ea2909b6Skaashoek return 0; 432ea2909b6Skaashoek } 433ea2909b6Skaashoek 434bb207a1dSrsc // Write data to inode. 435ea2909b6Skaashoek int 43617a85657Srtm writei(struct inode *ip, char *addr, uint off, uint n) 4376fa5ffb5Skaashoek { 4386fa5ffb5Skaashoek if(ip->type == T_DEV) { 4391dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].write) 440939f9edeSkaashoek return -1; 4411dca3afbSrsc return devsw[ip->major].write(ip->minor, addr, n); 442ea2909b6Skaashoek } else if(ip->type == T_FILE || ip->type == T_DIR) { 44328d9ef04Skaashoek struct buf *bp; 44428d9ef04Skaashoek int r = 0; 44528d9ef04Skaashoek int m; 44628d9ef04Skaashoek int lbn; 44728d9ef04Skaashoek while(r < n) { 44828d9ef04Skaashoek lbn = off / BSIZE; 44948b82470Srsc if(lbn >= MAXFILE) 45048b82470Srsc return r; 451ea2909b6Skaashoek if(newblock(ip, lbn) < 0) { 452ea2909b6Skaashoek cprintf("newblock failed\n"); 453ea2909b6Skaashoek return r; 45428d9ef04Skaashoek } 45522bac2cbSkaashoek m = min(BSIZE - off % BSIZE, n-r); 456ea2909b6Skaashoek bp = bread(ip->dev, bmap(ip, lbn)); 45728d9ef04Skaashoek memmove(bp->data + off % BSIZE, addr, m); 458ea2909b6Skaashoek bwrite(bp, bmap(ip, lbn)); 45928d9ef04Skaashoek brelse(bp); 46028d9ef04Skaashoek r += m; 46128d9ef04Skaashoek off += m; 46228d9ef04Skaashoek } 46328d9ef04Skaashoek if(r > 0) { 46428d9ef04Skaashoek if(off > ip->size) { 46548b82470Srsc if(ip->type == T_DIR) 46648b82470Srsc ip->size = ((off / BSIZE) + 1) * BSIZE; 46748b82470Srsc else 46848b82470Srsc ip->size = off; 46928d9ef04Skaashoek } 47028d9ef04Skaashoek iupdate(ip); 47128d9ef04Skaashoek } 47228d9ef04Skaashoek return r; 4736fa5ffb5Skaashoek } else { 4742aa4c3bcSrtm panic("writei: unknown type"); 4758a8be1b8Srtm return 0; 4766fa5ffb5Skaashoek } 4776fa5ffb5Skaashoek } 4786fa5ffb5Skaashoek 479*ab5c2dbbSrsc // Skip over the next path element in path, 480*ab5c2dbbSrsc // saving it in *name and its length in *len. 481*ab5c2dbbSrsc // Return a pointer to the element after that 482*ab5c2dbbSrsc // (after any trailing slashes). 483*ab5c2dbbSrsc // Thus the caller can check whether *path=='\0' 484*ab5c2dbbSrsc // to see whether the name just removed was 485*ab5c2dbbSrsc // the last one. 486*ab5c2dbbSrsc // If there is no name to remove, return 0. 487*ab5c2dbbSrsc // 488*ab5c2dbbSrsc // Examples: 489*ab5c2dbbSrsc // skipelem("a/bb/c") = "bb/c", with *name = "a/bb/c", len=1 490*ab5c2dbbSrsc // skipelem("///a/bb") = "b", with *name="a/bb", len=1 491*ab5c2dbbSrsc // skipelem("") = skipelem("////") = 0 492*ab5c2dbbSrsc // 493*ab5c2dbbSrsc static char* 494*ab5c2dbbSrsc skipelem(char *path, char **name, int *len) 495*ab5c2dbbSrsc { 496*ab5c2dbbSrsc while(*path == '/') 497*ab5c2dbbSrsc path++; 498*ab5c2dbbSrsc if(*path == 0) 499*ab5c2dbbSrsc return 0; 500*ab5c2dbbSrsc *name = path; 501*ab5c2dbbSrsc while(*path != '/' && *path != 0) 502*ab5c2dbbSrsc path++; 503*ab5c2dbbSrsc *len = path - *name; 504*ab5c2dbbSrsc while(*path == '/') 505*ab5c2dbbSrsc path++; 506*ab5c2dbbSrsc return path; 507*ab5c2dbbSrsc } 508*ab5c2dbbSrsc 509*ab5c2dbbSrsc // Look for a directory entry in a directory. 510*ab5c2dbbSrsc // If not found, return -1. 511*ab5c2dbbSrsc // If found: 512*ab5c2dbbSrsc // set *poff to the byte offset of the directory entry 513*ab5c2dbbSrsc // set *pinum to the inode number 514*ab5c2dbbSrsc // return 0. 515*ab5c2dbbSrsc static int 516*ab5c2dbbSrsc lookup(struct inode *dp, char *name, int namelen, uint *poff, uint *pinum) 517*ab5c2dbbSrsc { 518*ab5c2dbbSrsc uint off; 519*ab5c2dbbSrsc struct buf *bp; 520*ab5c2dbbSrsc struct dirent *de; 521*ab5c2dbbSrsc 522*ab5c2dbbSrsc if(dp->type != T_DIR) 523*ab5c2dbbSrsc return -1; 524*ab5c2dbbSrsc 525*ab5c2dbbSrsc for(off = 0; off < dp->size; off += BSIZE){ 526*ab5c2dbbSrsc bp = bread(dp->dev, bmap(dp, off / BSIZE)); 527*ab5c2dbbSrsc for(de = (struct dirent*) bp->data; 528*ab5c2dbbSrsc de < (struct dirent*) (bp->data + BSIZE); 529*ab5c2dbbSrsc de++){ 530*ab5c2dbbSrsc if(de->inum == 0) 531*ab5c2dbbSrsc continue; 532*ab5c2dbbSrsc if(memcmp(name, de->name, namelen) == 0 && 533*ab5c2dbbSrsc (namelen == DIRSIZ || de->name[namelen]== 0)){ 534*ab5c2dbbSrsc // entry matches path element 535*ab5c2dbbSrsc *poff = off + (uchar*)de - bp->data; 536*ab5c2dbbSrsc *pinum = de->inum; 537*ab5c2dbbSrsc brelse(bp); 538*ab5c2dbbSrsc return 0; 539*ab5c2dbbSrsc } 540*ab5c2dbbSrsc } 541*ab5c2dbbSrsc brelse(bp); 542*ab5c2dbbSrsc } 543*ab5c2dbbSrsc return -1; 544*ab5c2dbbSrsc } 545*ab5c2dbbSrsc 546211ff0c6Srtm // look up a path name, in one of three modes. 547211ff0c6Srtm // NAMEI_LOOKUP: return locked target inode. 548211ff0c6Srtm // NAMEI_CREATE: return locked parent inode. 5495051da6dSrtm // return 0 if name does exist. 5505051da6dSrtm // *ret_last points to last path component (i.e. new file name). 5515051da6dSrtm // *ret_ip points to the the name that did exist, if it did. 5525051da6dSrtm // *ret_ip and *ret_last may be zero even if return value is zero. 553211ff0c6Srtm // NAMEI_DELETE: return locked parent inode, offset of dirent in *ret_off. 554211ff0c6Srtm // return 0 if name doesn't exist. 5559d3fb671Srtm struct inode* 5560cfc7290Srsc namei(char *path, int mode, uint *ret_off, 5570cfc7290Srsc char **ret_last, struct inode **ret_ip) 5589d3fb671Srtm { 5599d3fb671Srtm struct inode *dp; 5608787cd01Skaashoek struct proc *p = curproc[cpu()]; 561*ab5c2dbbSrsc char *name; 562*ab5c2dbbSrsc int namelen; 5639d3fb671Srtm uint off, dev; 564*ab5c2dbbSrsc uint inum; 5659d3fb671Srtm 5665051da6dSrtm if(ret_off) 5675051da6dSrtm *ret_off = 0xffffffff; 5685051da6dSrtm if(ret_last) 5695051da6dSrtm *ret_last = 0; 5705051da6dSrtm if(ret_ip) 5715051da6dSrtm *ret_ip = 0; 5725051da6dSrtm 573*ab5c2dbbSrsc if(*path == '/') 57448b82470Srsc dp = iget(rootdev, 1); 5758787cd01Skaashoek else { 576d80b06a1Srsc dp = iincref(p->cwd); 5778787cd01Skaashoek ilock(dp); 5788787cd01Skaashoek } 5799d3fb671Srtm 580*ab5c2dbbSrsc while((path = skipelem(path, &name, &namelen)) != 0){ 581*ab5c2dbbSrsc // Truncate names in path to DIRSIZ chars. 582*ab5c2dbbSrsc if(namelen > DIRSIZ) 583*ab5c2dbbSrsc namelen = DIRSIZ; 5849d3fb671Srtm 585*ab5c2dbbSrsc if(dp->type != T_DIR) 586*ab5c2dbbSrsc goto fail; 587*ab5c2dbbSrsc 588*ab5c2dbbSrsc if(lookup(dp, name, namelen, &off, &inum) < 0){ 589*ab5c2dbbSrsc if(mode == NAMEI_CREATE && *path == '\0'){ 590*ab5c2dbbSrsc *ret_last = name; 591*ab5c2dbbSrsc return dp; 592*ab5c2dbbSrsc } 593*ab5c2dbbSrsc goto fail; 594*ab5c2dbbSrsc } 595*ab5c2dbbSrsc 596*ab5c2dbbSrsc if(mode == NAMEI_DELETE && *path == '\0'){ 597*ab5c2dbbSrsc // can't unlink . and .. 598*ab5c2dbbSrsc if((namelen == 1 && memcmp(name, ".", 1) == 0) || 599*ab5c2dbbSrsc (namelen == 2 && memcmp(name, "..", 2) == 0)){ 600*ab5c2dbbSrsc goto fail; 601*ab5c2dbbSrsc } 602*ab5c2dbbSrsc *ret_off = off; 603*ab5c2dbbSrsc return dp; 604*ab5c2dbbSrsc } 605*ab5c2dbbSrsc 606*ab5c2dbbSrsc dev = dp->dev; 607*ab5c2dbbSrsc iput(dp); 608*ab5c2dbbSrsc dp = iget(dev, inum); 609*ab5c2dbbSrsc if(dp->type == 0 || dp->nlink < 1) 610*ab5c2dbbSrsc panic("namei"); 611*ab5c2dbbSrsc } 612*ab5c2dbbSrsc 613211ff0c6Srtm if(mode == NAMEI_LOOKUP) 6149d3fb671Srtm return dp; 6155051da6dSrtm if(mode == NAMEI_CREATE && ret_ip){ 6165051da6dSrtm *ret_ip = dp; 6175051da6dSrtm return 0; 6185051da6dSrtm } 619*ab5c2dbbSrsc goto fail; 620*ab5c2dbbSrsc 621*ab5c2dbbSrsc fail: 622211ff0c6Srtm iput(dp); 623211ff0c6Srtm return 0; 6240633b971Skaashoek } 6259d3fb671Srtm 626bb207a1dSrsc // Write a new directory entry (name, ino) into the directory dp. 627bb207a1dSrsc // Caller must have locked dp. 6289e5970d5Srtm void 6299e5970d5Srtm wdir(struct inode *dp, char *name, uint ino) 6309e5970d5Srtm { 6319e5970d5Srtm uint off; 632e4bcd2a3Srtm struct dirent de; 6339e5970d5Srtm int i; 6349e5970d5Srtm 635e4bcd2a3Srtm for(off = 0; off < dp->size; off += sizeof(de)){ 636e4bcd2a3Srtm if(readi(dp, (char*) &de, off, sizeof(de)) != sizeof(de)) 637e4bcd2a3Srtm panic("wdir read"); 638e4bcd2a3Srtm if(de.inum == 0) 639e4bcd2a3Srtm break; 640e4bcd2a3Srtm } 641211ff0c6Srtm 642e4bcd2a3Srtm de.inum = ino; 6432aa4c3bcSrtm for(i = 0; i < DIRSIZ && name[i]; i++) 644e4bcd2a3Srtm de.name[i] = name[i]; 6459e5970d5Srtm for( ; i < DIRSIZ; i++) 646e4bcd2a3Srtm de.name[i] = '\0'; 647e4bcd2a3Srtm 648e4bcd2a3Srtm if(writei(dp, (char*) &de, off, sizeof(de)) != sizeof(de)) 649e4bcd2a3Srtm panic("wdir write"); 6509e5970d5Srtm } 6519e5970d5Srtm 652bb207a1dSrsc // Create the path cp and return its locked inode structure. 653bb207a1dSrsc // If cp already exists, return 0. 654e8d11c2eSkaashoek struct inode* 6550633b971Skaashoek mknod(char *cp, short type, short major, short minor) 656e8d11c2eSkaashoek { 6570633b971Skaashoek struct inode *ip, *dp; 6585051da6dSrtm char *last; 659e8d11c2eSkaashoek 6605051da6dSrtm if((dp = namei(cp, NAMEI_CREATE, 0, &last, 0)) == 0) 6610633b971Skaashoek return 0; 662211ff0c6Srtm 6635051da6dSrtm ip = mknod1(dp, last, type, major, minor); 6645051da6dSrtm 6655051da6dSrtm iput(dp); 6665051da6dSrtm 6675051da6dSrtm return ip; 6685051da6dSrtm } 6695051da6dSrtm 670bb207a1dSrsc // Create a new inode named name inside dp 671bb207a1dSrsc // and return its locked inode structure. 672bb207a1dSrsc // If name already exists, return 0. 6735051da6dSrtm struct inode* 6745051da6dSrtm mknod1(struct inode *dp, char *name, short type, short major, short minor) 6755051da6dSrtm { 6765051da6dSrtm struct inode *ip; 6775051da6dSrtm 678e8d11c2eSkaashoek ip = ialloc(dp->dev, type); 6792aa4c3bcSrtm if(ip == 0) 6800633b971Skaashoek return 0; 681e8d11c2eSkaashoek ip->major = major; 682e8d11c2eSkaashoek ip->minor = minor; 6836c0e444fSkaashoek ip->size = 0; 6847ce01cf9Srtm ip->nlink = 1; 6856c0e444fSkaashoek 6866c0e444fSkaashoek iupdate(ip); // write new inode to disk 687e8d11c2eSkaashoek 6885051da6dSrtm wdir(dp, name, ip->inum); 6895051da6dSrtm 690e8d11c2eSkaashoek return ip; 691e8d11c2eSkaashoek } 69224437cd5Skaashoek 693bb207a1dSrsc // Unlink the inode named cp. 69424437cd5Skaashoek int 69524437cd5Skaashoek unlink(char *cp) 69624437cd5Skaashoek { 697211ff0c6Srtm struct inode *ip, *dp; 698211ff0c6Srtm struct dirent de; 69917e3cf15Srtm uint off, inum, dev; 70024437cd5Skaashoek 7015051da6dSrtm dp = namei(cp, NAMEI_DELETE, &off, 0, 0); 7025051da6dSrtm if(dp == 0) 70324437cd5Skaashoek return -1; 70424437cd5Skaashoek 70517e3cf15Srtm dev = dp->dev; 70617e3cf15Srtm 70717e3cf15Srtm if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de) || de.inum == 0) 708211ff0c6Srtm panic("unlink no entry"); 70917e3cf15Srtm 710*ab5c2dbbSrsc // Cannot remove "." or ".." - the 2 and 3 count the trailing NUL. 711*ab5c2dbbSrsc if(memcmp(de.name, ".", 2) == 0 || memcmp(de.name, "..", 3) == 0){ 712*ab5c2dbbSrsc iput(dp); 713*ab5c2dbbSrsc return -1; 714*ab5c2dbbSrsc } 715*ab5c2dbbSrsc 716211ff0c6Srtm inum = de.inum; 71724437cd5Skaashoek 718211ff0c6Srtm memset(&de, 0, sizeof(de)); 719211ff0c6Srtm if(writei(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 720211ff0c6Srtm panic("unlink dir write"); 72124437cd5Skaashoek 72224437cd5Skaashoek iupdate(dp); 72324437cd5Skaashoek iput(dp); 724211ff0c6Srtm 72517e3cf15Srtm ip = iget(dev, inum); 726211ff0c6Srtm 727bcfb84b6Srtm if(ip->nlink < 1) 728bcfb84b6Srtm panic("unlink nlink < 1"); 729bcfb84b6Srtm 730211ff0c6Srtm ip->nlink--; 731211ff0c6Srtm 732211ff0c6Srtm iupdate(ip); 73322bac2cbSkaashoek iput(ip); 734211ff0c6Srtm 73524437cd5Skaashoek return 0; 73624437cd5Skaashoek } 7379e5970d5Srtm 738bb207a1dSrsc // Create the path new as a link to the same inode as old. 7399e5970d5Srtm int 7409e5970d5Srtm link(char *name1, char *name2) 7419e5970d5Srtm { 742211ff0c6Srtm struct inode *ip, *dp; 7435051da6dSrtm char *last; 7449e5970d5Srtm 7455051da6dSrtm if((ip = namei(name1, NAMEI_LOOKUP, 0, 0, 0)) == 0) 7469e5970d5Srtm return -1; 747211ff0c6Srtm if(ip->type == T_DIR){ 748211ff0c6Srtm iput(ip); 749211ff0c6Srtm return -1; 750211ff0c6Srtm } 7519e5970d5Srtm 752211ff0c6Srtm iunlock(ip); 753211ff0c6Srtm 7545051da6dSrtm if((dp = namei(name2, NAMEI_CREATE, 0, &last, 0)) == 0) { 755211ff0c6Srtm idecref(ip); 756211ff0c6Srtm return -1; 757211ff0c6Srtm } 758211ff0c6Srtm if(dp->dev != ip->dev){ 759211ff0c6Srtm idecref(ip); 760211ff0c6Srtm iput(dp); 761211ff0c6Srtm return -1; 762211ff0c6Srtm } 763211ff0c6Srtm 764211ff0c6Srtm ilock(ip); 765be29b8e2Srsc ip->nlink++; 7669e5970d5Srtm iupdate(ip); 7679e5970d5Srtm 7685051da6dSrtm wdir(dp, last, ip->inum); 7699e5970d5Srtm iput(dp); 7709e5970d5Srtm iput(ip); 7719e5970d5Srtm 7729e5970d5Srtm return 0; 7739e5970d5Srtm } 774