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 { 44*7d4aef6cSrsc int b, bi, m, ninodes, size; 4524111398Skaashoek struct buf *bp; 4624111398Skaashoek struct superblock *sb; 4724111398Skaashoek 4824111398Skaashoek bp = bread(dev, 1); 4924111398Skaashoek sb = (struct superblock*) bp->data; 5024111398Skaashoek size = sb->size; 5124111398Skaashoek ninodes = sb->ninodes; 5224111398Skaashoek 5324111398Skaashoek for(b = 0; b < size; b++) { 5424111398Skaashoek if(b % BPB == 0) { 5524111398Skaashoek brelse(bp); 5624111398Skaashoek bp = bread(dev, BBLOCK(b, ninodes)); 5724111398Skaashoek } 5824111398Skaashoek bi = b % BPB; 5924111398Skaashoek m = 0x1 << (bi % 8); 6024111398Skaashoek if((bp->data[bi/8] & m) == 0) { // is block free? 6124111398Skaashoek bp->data[bi/8] |= 0x1 << (bi % 8); 6205e97551Srtm bwrite(bp, BBLOCK(b, ninodes)); // mark it allocated on disk 6328d9ef04Skaashoek brelse(bp); 6424111398Skaashoek return b; 6524111398Skaashoek } 66*7d4aef6cSrsc } 67*7d4aef6cSrsc panic("balloc: out of blocks"); 68*7d4aef6cSrsc } 6924111398Skaashoek 70bb207a1dSrsc // Free a disk block. 7128d9ef04Skaashoek static void 7228d9ef04Skaashoek bfree(int dev, uint b) 7328d9ef04Skaashoek { 7428d9ef04Skaashoek struct buf *bp; 7528d9ef04Skaashoek struct superblock *sb; 76*7d4aef6cSrsc int bi, m, ninodes; 7728d9ef04Skaashoek 7828d9ef04Skaashoek bp = bread(dev, 1); 7928d9ef04Skaashoek sb = (struct superblock*) bp->data; 8028d9ef04Skaashoek ninodes = sb->ninodes; 8128d9ef04Skaashoek brelse(bp); 8228d9ef04Skaashoek 83c372e8dcSkaashoek bp = bread(dev, b); 84c372e8dcSkaashoek memset(bp->data, 0, BSIZE); 85c372e8dcSkaashoek bwrite(bp, b); 86c372e8dcSkaashoek brelse(bp); 87c372e8dcSkaashoek 8828d9ef04Skaashoek bp = bread(dev, BBLOCK(b, ninodes)); 8928d9ef04Skaashoek bi = b % BPB; 90*7d4aef6cSrsc m = 0x1 << (bi % 8); 91*7d4aef6cSrsc bp->data[bi/8] &= ~m; 9205e97551Srtm bwrite(bp, BBLOCK(b, ninodes)); // mark it free on disk 9328d9ef04Skaashoek brelse(bp); 9428d9ef04Skaashoek } 9524111398Skaashoek 96f5527388Srsc // Find the inode with number inum on device dev 97f5527388Srsc // and return an in-memory copy. Loads the inode 98f5527388Srsc // from disk into the in-core table if necessary. 99f5527388Srsc // The returned inode has busy set and has its ref count incremented. 100f5527388Srsc // Caller must iput the return value when done with it. 10111a9947fSrtm struct inode* 10211a9947fSrtm iget(uint dev, uint inum) 10311a9947fSrtm { 10417e3cf15Srtm struct inode *ip, *nip; 10511a9947fSrtm struct dinode *dip; 10611a9947fSrtm struct buf *bp; 10711a9947fSrtm 10811a9947fSrtm acquire(&inode_table_lock); 10911a9947fSrtm 11011a9947fSrtm loop: 11117e3cf15Srtm nip = 0; 11211a9947fSrtm for(ip = &inode[0]; ip < &inode[NINODE]; ip++){ 1130d6bbd31Srsc if(ip->ref > 0 && ip->dev == dev && ip->inum == inum){ 11411a9947fSrtm if(ip->busy){ 11511a9947fSrtm sleep(ip, &inode_table_lock); 116bb207a1dSrsc // Since we droped inode_table_lock, ip might have been reused 117bb207a1dSrsc // for some other inode entirely. Must start the scan over, 118bb207a1dSrsc // and hopefully this time we will find the inode we want 119bb207a1dSrsc // and it will not be busy. 12011a9947fSrtm goto loop; 12111a9947fSrtm } 1220d6bbd31Srsc ip->ref++; 12317a85657Srtm ip->busy = 1; 12411a9947fSrtm release(&inode_table_lock); 12511a9947fSrtm return ip; 12611a9947fSrtm } 1270d6bbd31Srsc if(nip == 0 && ip->ref == 0) 12811a9947fSrtm nip = ip; 12911a9947fSrtm } 13011a9947fSrtm 13111a9947fSrtm if(nip == 0) 13232eea766Srsc panic("iget: no inodes"); 13311a9947fSrtm 13411a9947fSrtm nip->dev = dev; 13511a9947fSrtm nip->inum = inum; 1360d6bbd31Srsc nip->ref = 1; 13711a9947fSrtm nip->busy = 1; 13811a9947fSrtm 13911a9947fSrtm release(&inode_table_lock); 14011a9947fSrtm 14124111398Skaashoek bp = bread(dev, IBLOCK(inum)); 14211a9947fSrtm dip = &((struct dinode*)(bp->data))[inum % IPB]; 14311a9947fSrtm nip->type = dip->type; 144e8d11c2eSkaashoek nip->major = dip->major; 145e8d11c2eSkaashoek nip->minor = dip->minor; 14611a9947fSrtm nip->nlink = dip->nlink; 14711a9947fSrtm nip->size = dip->size; 14811a9947fSrtm memmove(nip->addrs, dip->addrs, sizeof(nip->addrs)); 14911a9947fSrtm brelse(bp); 15011a9947fSrtm 15111a9947fSrtm return nip; 15211a9947fSrtm } 15311a9947fSrtm 1548e1d1ec9Skaashoek // Copy inode in memory, which has changed, to disk. 155bb207a1dSrsc // Caller must have locked ip. 15628d9ef04Skaashoek void 15728d9ef04Skaashoek iupdate(struct inode *ip) 15828d9ef04Skaashoek { 15928d9ef04Skaashoek struct buf *bp; 16028d9ef04Skaashoek struct dinode *dip; 16128d9ef04Skaashoek 16228d9ef04Skaashoek bp = bread(ip->dev, IBLOCK(ip->inum)); 16328d9ef04Skaashoek dip = &((struct dinode*)(bp->data))[ip->inum % IPB]; 16428d9ef04Skaashoek dip->type = ip->type; 16528d9ef04Skaashoek dip->major = ip->major; 16628d9ef04Skaashoek dip->minor = ip->minor; 16728d9ef04Skaashoek dip->nlink = ip->nlink; 16828d9ef04Skaashoek dip->size = ip->size; 16928d9ef04Skaashoek memmove(dip->addrs, ip->addrs, sizeof(ip->addrs)); 170*7d4aef6cSrsc bwrite(bp, IBLOCK(ip->inum)); 17128d9ef04Skaashoek brelse(bp); 17228d9ef04Skaashoek } 17328d9ef04Skaashoek 174bb207a1dSrsc // Allocate a new inode with the given type 175bb207a1dSrsc // from the file system on device dev. 176e8d11c2eSkaashoek struct inode* 177e8d11c2eSkaashoek ialloc(uint dev, short type) 178e8d11c2eSkaashoek { 179e8d11c2eSkaashoek struct inode *ip; 180*7d4aef6cSrsc struct dinode *dip; 181e8d11c2eSkaashoek struct superblock *sb; 182e8d11c2eSkaashoek int ninodes; 183e8d11c2eSkaashoek int inum; 184e8d11c2eSkaashoek struct buf *bp; 185e8d11c2eSkaashoek 186e8d11c2eSkaashoek bp = bread(dev, 1); 18724111398Skaashoek sb = (struct superblock*) bp->data; 188e8d11c2eSkaashoek ninodes = sb->ninodes; 189e8d11c2eSkaashoek brelse(bp); 190e8d11c2eSkaashoek 191e8d11c2eSkaashoek for(inum = 1; inum < ninodes; inum++) { // loop over inode blocks 19224111398Skaashoek bp = bread(dev, IBLOCK(inum)); 193e8d11c2eSkaashoek dip = &((struct dinode*)(bp->data))[inum % IPB]; 194e8d11c2eSkaashoek if(dip->type == 0) { // a free inode 1952aa4c3bcSrtm memset(dip, 0, sizeof(*dip)); 196e8d11c2eSkaashoek dip->type = type; 19705e97551Srtm bwrite(bp, IBLOCK(inum)); // mark it allocated on the disk 198e8d11c2eSkaashoek brelse(bp); 199e8d11c2eSkaashoek ip = iget(dev, inum); 200e8d11c2eSkaashoek return ip; 201e8d11c2eSkaashoek } 20295c07f82Srsc brelse(bp); 20395c07f82Srsc } 20495c07f82Srsc panic("ialloc: no inodes"); 20595c07f82Srsc } 206e8d11c2eSkaashoek 207bb207a1dSrsc // Free the given inode from its file system. 20828d9ef04Skaashoek static void 20924437cd5Skaashoek ifree(struct inode *ip) 210e8d11c2eSkaashoek { 21128d9ef04Skaashoek ip->type = 0; 21228d9ef04Skaashoek iupdate(ip); 213e8d11c2eSkaashoek } 214e8d11c2eSkaashoek 215bb207a1dSrsc // Lock the given inode (wait for it to be not busy, 216bb207a1dSrsc // and then ip->busy). 217bb207a1dSrsc // Caller must already hold a reference to ip. 218bb207a1dSrsc // Otherwise, if all the references to ip go away, 219bb207a1dSrsc // it might be reused underfoot. 22011a9947fSrtm void 2219d3fb671Srtm ilock(struct inode *ip) 2229d3fb671Srtm { 2230d6bbd31Srsc if(ip->ref < 1) 2249d3fb671Srtm panic("ilock"); 2259d3fb671Srtm 2269d3fb671Srtm acquire(&inode_table_lock); 2279d3fb671Srtm 2289d3fb671Srtm while(ip->busy) 2299d3fb671Srtm sleep(ip, &inode_table_lock); 2309d3fb671Srtm ip->busy = 1; 2319d3fb671Srtm 2329d3fb671Srtm release(&inode_table_lock); 2339d3fb671Srtm } 2349d3fb671Srtm 235bb207a1dSrsc // Caller holds reference to ip and has locked it. 236bb207a1dSrsc // Caller no longer needs to examine / change it. 237bb207a1dSrsc // Unlock it, but keep the reference. 2389d3fb671Srtm void 2399d3fb671Srtm iunlock(struct inode *ip) 2409d3fb671Srtm { 2410d6bbd31Srsc if(ip->busy != 1 || ip->ref < 1) 2429d3fb671Srtm panic("iunlock"); 2439d3fb671Srtm 2449d3fb671Srtm acquire(&inode_table_lock); 2459d3fb671Srtm 2469d3fb671Srtm ip->busy = 0; 2479d3fb671Srtm wakeup(ip); 2489d3fb671Srtm 2499d3fb671Srtm release(&inode_table_lock); 2509d3fb671Srtm } 2519d3fb671Srtm 252bb207a1dSrsc // Return the disk block address of the nth block in inode ip. 25322bac2cbSkaashoek uint 25422bac2cbSkaashoek bmap(struct inode *ip, uint bn) 25522bac2cbSkaashoek { 256d80b06a1Srsc uint *a, x; 257ea2909b6Skaashoek struct buf *inbp; 25822bac2cbSkaashoek 259ea2909b6Skaashoek if(bn >= MAXFILE) 26022bac2cbSkaashoek panic("bmap 1"); 261ea2909b6Skaashoek if(bn < NDIRECT) { 26222bac2cbSkaashoek x = ip->addrs[bn]; 26322bac2cbSkaashoek if(x == 0) 26422bac2cbSkaashoek panic("bmap 2"); 265ea2909b6Skaashoek } else { 2665051da6dSrtm if(ip->addrs[INDIRECT] == 0) 2675051da6dSrtm panic("bmap 3"); 2681be76685Skaashoek inbp = bread(ip->dev, ip->addrs[INDIRECT]); 269ea2909b6Skaashoek a = (uint*) inbp->data; 270ea2909b6Skaashoek x = a[bn - NDIRECT]; 271ea2909b6Skaashoek brelse(inbp); 272ea2909b6Skaashoek if(x == 0) 2735051da6dSrtm panic("bmap 4"); 274ea2909b6Skaashoek } 27522bac2cbSkaashoek return x; 27622bac2cbSkaashoek } 27722bac2cbSkaashoek 278bb207a1dSrsc // Truncate the inode ip, discarding all its data blocks. 27922bac2cbSkaashoek void 2802aa4c3bcSrtm itrunc(struct inode *ip) 28122bac2cbSkaashoek { 282ea2909b6Skaashoek int i, j; 2831be76685Skaashoek struct buf *inbp; 284*7d4aef6cSrsc uint *a; 28522bac2cbSkaashoek 286ea2909b6Skaashoek for(i = 0; i < NADDRS; i++) { 28722bac2cbSkaashoek if(ip->addrs[i] != 0) { 288ea2909b6Skaashoek if(i == INDIRECT) { 2891be76685Skaashoek inbp = bread(ip->dev, ip->addrs[INDIRECT]); 290*7d4aef6cSrsc a = (uint*)inbp->data; 291bcfb84b6Srtm for(j = 0; j < NINDIRECT; j++) { 292ea2909b6Skaashoek if(a[j] != 0) { 293ea2909b6Skaashoek bfree(ip->dev, a[j]); 294ea2909b6Skaashoek a[j] = 0; 295ea2909b6Skaashoek } 296ea2909b6Skaashoek } 2971be76685Skaashoek brelse(inbp); 298ea2909b6Skaashoek } 29922bac2cbSkaashoek bfree(ip->dev, ip->addrs[i]); 30022bac2cbSkaashoek ip->addrs[i] = 0; 30122bac2cbSkaashoek } 30222bac2cbSkaashoek } 30322bac2cbSkaashoek ip->size = 0; 30422bac2cbSkaashoek iupdate(ip); 30522bac2cbSkaashoek } 30622bac2cbSkaashoek 307bb207a1dSrsc // Caller holds reference to ip and has locked it, 308bb207a1dSrsc // possibly editing it. 309bb207a1dSrsc // Release lock and drop the reference. 3109d3fb671Srtm void 31111a9947fSrtm iput(struct inode *ip) 31211a9947fSrtm { 3130d6bbd31Srsc if(ip->ref < 1 || ip->busy != 1) 3149d3fb671Srtm panic("iput"); 3159d3fb671Srtm 3160d6bbd31Srsc if((ip->ref == 1) && (ip->nlink == 0)) { 3172aa4c3bcSrtm itrunc(ip); 3182aa4c3bcSrtm ifree(ip); 3192aa4c3bcSrtm } 32022bac2cbSkaashoek 32111a9947fSrtm acquire(&inode_table_lock); 32211a9947fSrtm 3230d6bbd31Srsc ip->ref -= 1; 32411a9947fSrtm ip->busy = 0; 32511a9947fSrtm wakeup(ip); 32611a9947fSrtm 32711a9947fSrtm release(&inode_table_lock); 32811a9947fSrtm } 3299d3fb671Srtm 330bb207a1dSrsc // Caller holds reference to ip but not lock. 331bb207a1dSrsc // Drop reference. 3329d3fb671Srtm void 33332630628Srtm idecref(struct inode *ip) 3349d3fb671Srtm { 335211ff0c6Srtm ilock(ip); 336211ff0c6Srtm iput(ip); 3379d3fb671Srtm } 3389d3fb671Srtm 339bb207a1dSrsc // Increment reference count for ip. 340d80b06a1Srsc // Returns ip to enable ip = iincref(ip1) idiom. 341d80b06a1Srsc struct inode* 342e958c538Skaashoek iincref(struct inode *ip) 343e958c538Skaashoek { 344e958c538Skaashoek ilock(ip); 3450d6bbd31Srsc ip->ref++; 346e958c538Skaashoek iunlock(ip); 347d80b06a1Srsc return ip; 348e958c538Skaashoek } 349e958c538Skaashoek 350bb207a1dSrsc // Copy stat information from inode. 351e958c538Skaashoek void 3521f544842Skaashoek stati(struct inode *ip, struct stat *st) 3531f544842Skaashoek { 3541dca3afbSrsc st->dev = ip->dev; 3551dca3afbSrsc st->ino = ip->inum; 3561dca3afbSrsc st->type = ip->type; 3571dca3afbSrsc st->nlink = ip->nlink; 3581dca3afbSrsc st->size = ip->size; 3591f544842Skaashoek } 3601f544842Skaashoek 36122bac2cbSkaashoek #define min(a, b) ((a) < (b) ? (a) : (b)) 36222bac2cbSkaashoek 363bb207a1dSrsc // Read data from inode. 364c59361f1Srtm int 36517a85657Srtm readi(struct inode *ip, char *dst, uint off, uint n) 366c59361f1Srtm { 367*7d4aef6cSrsc uint target, n1; 368c59361f1Srtm struct buf *bp; 369c59361f1Srtm 370939f9edeSkaashoek if(ip->type == T_DEV) { 3711dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].read) 372939f9edeSkaashoek return -1; 3731dca3afbSrsc return devsw[ip->major].read(ip->minor, dst, n); 374939f9edeSkaashoek } 375939f9edeSkaashoek 376*7d4aef6cSrsc target = n; 377c59361f1Srtm while(n > 0 && off < ip->size){ 37824111398Skaashoek bp = bread(ip->dev, bmap(ip, off / BSIZE)); 379c59361f1Srtm n1 = min(n, ip->size - off); 38024111398Skaashoek n1 = min(n1, BSIZE - (off % BSIZE)); 38124111398Skaashoek memmove(dst, bp->data + (off % BSIZE), n1); 382c59361f1Srtm n -= n1; 383c59361f1Srtm off += n1; 384c59361f1Srtm dst += n1; 385c59361f1Srtm brelse(bp); 386c59361f1Srtm } 387c59361f1Srtm 388c59361f1Srtm return target - n; 389c59361f1Srtm } 390c59361f1Srtm 391bb207a1dSrsc // Allocate the nth block in inode ip if necessary. 3921be76685Skaashoek static int 393ea2909b6Skaashoek newblock(struct inode *ip, uint lbn) 394ea2909b6Skaashoek { 395ea2909b6Skaashoek struct buf *inbp; 396ea2909b6Skaashoek uint *inaddrs; 397ea2909b6Skaashoek uint b; 398ea2909b6Skaashoek 399ea2909b6Skaashoek if(lbn < NDIRECT) { 400ea2909b6Skaashoek if(ip->addrs[lbn] == 0) { 401ea2909b6Skaashoek b = balloc(ip->dev); 40248b82470Srsc if(b <= 0) 40348b82470Srsc return -1; 404ea2909b6Skaashoek ip->addrs[lbn] = b; 405ea2909b6Skaashoek } 406ea2909b6Skaashoek } else { 407ea2909b6Skaashoek if(ip->addrs[INDIRECT] == 0) { 408ea2909b6Skaashoek b = balloc(ip->dev); 40948b82470Srsc if(b <= 0) 41048b82470Srsc return -1; 411ea2909b6Skaashoek ip->addrs[INDIRECT] = b; 412ea2909b6Skaashoek } 4131be76685Skaashoek inbp = bread(ip->dev, ip->addrs[INDIRECT]); 414ea2909b6Skaashoek inaddrs = (uint*) inbp->data; 415ea2909b6Skaashoek if(inaddrs[lbn - NDIRECT] == 0) { 416ea2909b6Skaashoek b = balloc(ip->dev); 41748b82470Srsc if(b <= 0) 41848b82470Srsc return -1; 419ea2909b6Skaashoek inaddrs[lbn - NDIRECT] = b; 4201be76685Skaashoek bwrite(inbp, ip->addrs[INDIRECT]); 421ea2909b6Skaashoek } 422ea2909b6Skaashoek brelse(inbp); 423ea2909b6Skaashoek } 424ea2909b6Skaashoek return 0; 425ea2909b6Skaashoek } 426ea2909b6Skaashoek 427bb207a1dSrsc // Write data to inode. 428ea2909b6Skaashoek int 42917a85657Srtm writei(struct inode *ip, char *addr, uint off, uint n) 4306fa5ffb5Skaashoek { 431*7d4aef6cSrsc struct buf *bp; 432*7d4aef6cSrsc int r, m, lbn; 433*7d4aef6cSrsc 4346fa5ffb5Skaashoek if(ip->type == T_DEV) { 4351dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].write) 436939f9edeSkaashoek return -1; 4371dca3afbSrsc return devsw[ip->major].write(ip->minor, addr, n); 438*7d4aef6cSrsc } 439*7d4aef6cSrsc 440*7d4aef6cSrsc for(r=0; r<n; ) { 44128d9ef04Skaashoek lbn = off / BSIZE; 44248b82470Srsc if(lbn >= MAXFILE) 44348b82470Srsc return r; 444ea2909b6Skaashoek if(newblock(ip, lbn) < 0) { 445ea2909b6Skaashoek cprintf("newblock failed\n"); 446ea2909b6Skaashoek return r; 44728d9ef04Skaashoek } 44822bac2cbSkaashoek m = min(BSIZE - off % BSIZE, n-r); 449ea2909b6Skaashoek bp = bread(ip->dev, bmap(ip, lbn)); 45028d9ef04Skaashoek memmove(bp->data + off % BSIZE, addr, m); 451ea2909b6Skaashoek bwrite(bp, bmap(ip, lbn)); 45228d9ef04Skaashoek brelse(bp); 45328d9ef04Skaashoek r += m; 45428d9ef04Skaashoek off += m; 45528d9ef04Skaashoek } 456*7d4aef6cSrsc if(r > 0 && off > ip->size) { 45748b82470Srsc if(ip->type == T_DIR) 45848b82470Srsc ip->size = ((off / BSIZE) + 1) * BSIZE; 45948b82470Srsc else 46048b82470Srsc ip->size = off; 46128d9ef04Skaashoek iupdate(ip); 46228d9ef04Skaashoek } 46328d9ef04Skaashoek return r; 4646fa5ffb5Skaashoek } 4656fa5ffb5Skaashoek 466ab5c2dbbSrsc // Skip over the next path element in path, 467ab5c2dbbSrsc // saving it in *name and its length in *len. 468ab5c2dbbSrsc // Return a pointer to the element after that 469ab5c2dbbSrsc // (after any trailing slashes). 470ab5c2dbbSrsc // Thus the caller can check whether *path=='\0' 471ab5c2dbbSrsc // to see whether the name just removed was 472ab5c2dbbSrsc // the last one. 473ab5c2dbbSrsc // If there is no name to remove, return 0. 474ab5c2dbbSrsc // 475ab5c2dbbSrsc // Examples: 476ab5c2dbbSrsc // skipelem("a/bb/c") = "bb/c", with *name = "a/bb/c", len=1 477ab5c2dbbSrsc // skipelem("///a/bb") = "b", with *name="a/bb", len=1 478ab5c2dbbSrsc // skipelem("") = skipelem("////") = 0 479ab5c2dbbSrsc // 480ab5c2dbbSrsc static char* 481ab5c2dbbSrsc skipelem(char *path, char **name, int *len) 482ab5c2dbbSrsc { 483ab5c2dbbSrsc while(*path == '/') 484ab5c2dbbSrsc path++; 485ab5c2dbbSrsc if(*path == 0) 486ab5c2dbbSrsc return 0; 487ab5c2dbbSrsc *name = path; 488ab5c2dbbSrsc while(*path != '/' && *path != 0) 489ab5c2dbbSrsc path++; 490ab5c2dbbSrsc *len = path - *name; 491ab5c2dbbSrsc while(*path == '/') 492ab5c2dbbSrsc path++; 493ab5c2dbbSrsc return path; 494ab5c2dbbSrsc } 495ab5c2dbbSrsc 496ab5c2dbbSrsc // Look for a directory entry in a directory. 497ab5c2dbbSrsc // If not found, return -1. 498ab5c2dbbSrsc // If found: 499ab5c2dbbSrsc // set *poff to the byte offset of the directory entry 500ab5c2dbbSrsc // set *pinum to the inode number 501ab5c2dbbSrsc // return 0. 502ab5c2dbbSrsc static int 503ab5c2dbbSrsc lookup(struct inode *dp, char *name, int namelen, uint *poff, uint *pinum) 504ab5c2dbbSrsc { 505ab5c2dbbSrsc uint off; 506ab5c2dbbSrsc struct buf *bp; 507ab5c2dbbSrsc struct dirent *de; 508ab5c2dbbSrsc 509ab5c2dbbSrsc if(dp->type != T_DIR) 510ab5c2dbbSrsc return -1; 511ab5c2dbbSrsc 512ab5c2dbbSrsc for(off = 0; off < dp->size; off += BSIZE){ 513ab5c2dbbSrsc bp = bread(dp->dev, bmap(dp, off / BSIZE)); 514ab5c2dbbSrsc for(de = (struct dirent*) bp->data; 515ab5c2dbbSrsc de < (struct dirent*) (bp->data + BSIZE); 516ab5c2dbbSrsc de++){ 517ab5c2dbbSrsc if(de->inum == 0) 518ab5c2dbbSrsc continue; 519ab5c2dbbSrsc if(memcmp(name, de->name, namelen) == 0 && 520ab5c2dbbSrsc (namelen == DIRSIZ || de->name[namelen]== 0)){ 521ab5c2dbbSrsc // entry matches path element 522ab5c2dbbSrsc *poff = off + (uchar*)de - bp->data; 523ab5c2dbbSrsc *pinum = de->inum; 524ab5c2dbbSrsc brelse(bp); 525ab5c2dbbSrsc return 0; 526ab5c2dbbSrsc } 527ab5c2dbbSrsc } 528ab5c2dbbSrsc brelse(bp); 529ab5c2dbbSrsc } 530ab5c2dbbSrsc return -1; 531ab5c2dbbSrsc } 532ab5c2dbbSrsc 533211ff0c6Srtm // look up a path name, in one of three modes. 534211ff0c6Srtm // NAMEI_LOOKUP: return locked target inode. 535211ff0c6Srtm // NAMEI_CREATE: return locked parent inode. 5365051da6dSrtm // return 0 if name does exist. 5375051da6dSrtm // *ret_last points to last path component (i.e. new file name). 5385051da6dSrtm // *ret_ip points to the the name that did exist, if it did. 5395051da6dSrtm // *ret_ip and *ret_last may be zero even if return value is zero. 540211ff0c6Srtm // NAMEI_DELETE: return locked parent inode, offset of dirent in *ret_off. 541211ff0c6Srtm // return 0 if name doesn't exist. 5429d3fb671Srtm struct inode* 5430cfc7290Srsc namei(char *path, int mode, uint *ret_off, 5440cfc7290Srsc char **ret_last, struct inode **ret_ip) 5459d3fb671Srtm { 5469d3fb671Srtm struct inode *dp; 547ab5c2dbbSrsc char *name; 548ab5c2dbbSrsc int namelen; 549bc011703Srsc uint off, dev, inum; 5509d3fb671Srtm 5515051da6dSrtm if(ret_off) 5525051da6dSrtm *ret_off = 0xffffffff; 5535051da6dSrtm if(ret_last) 5545051da6dSrtm *ret_last = 0; 5555051da6dSrtm if(ret_ip) 5565051da6dSrtm *ret_ip = 0; 5575051da6dSrtm 558ab5c2dbbSrsc if(*path == '/') 55948b82470Srsc dp = iget(rootdev, 1); 5608787cd01Skaashoek else { 561bc011703Srsc dp = iincref(cp->cwd); 5628787cd01Skaashoek ilock(dp); 5638787cd01Skaashoek } 5649d3fb671Srtm 565ab5c2dbbSrsc while((path = skipelem(path, &name, &namelen)) != 0){ 566ab5c2dbbSrsc // Truncate names in path to DIRSIZ chars. 567ab5c2dbbSrsc if(namelen > DIRSIZ) 568ab5c2dbbSrsc namelen = DIRSIZ; 5699d3fb671Srtm 570ab5c2dbbSrsc if(dp->type != T_DIR) 571ab5c2dbbSrsc goto fail; 572ab5c2dbbSrsc 573ab5c2dbbSrsc if(lookup(dp, name, namelen, &off, &inum) < 0){ 574ab5c2dbbSrsc if(mode == NAMEI_CREATE && *path == '\0'){ 575ab5c2dbbSrsc *ret_last = name; 576ab5c2dbbSrsc return dp; 577ab5c2dbbSrsc } 578ab5c2dbbSrsc goto fail; 579ab5c2dbbSrsc } 580ab5c2dbbSrsc 581ab5c2dbbSrsc if(mode == NAMEI_DELETE && *path == '\0'){ 582ab5c2dbbSrsc // can't unlink . and .. 583ab5c2dbbSrsc if((namelen == 1 && memcmp(name, ".", 1) == 0) || 584ab5c2dbbSrsc (namelen == 2 && memcmp(name, "..", 2) == 0)){ 585ab5c2dbbSrsc goto fail; 586ab5c2dbbSrsc } 587ab5c2dbbSrsc *ret_off = off; 588ab5c2dbbSrsc return dp; 589ab5c2dbbSrsc } 590ab5c2dbbSrsc 591ab5c2dbbSrsc dev = dp->dev; 592ab5c2dbbSrsc iput(dp); 593ab5c2dbbSrsc dp = iget(dev, inum); 594ab5c2dbbSrsc if(dp->type == 0 || dp->nlink < 1) 595ab5c2dbbSrsc panic("namei"); 596ab5c2dbbSrsc } 597ab5c2dbbSrsc 598211ff0c6Srtm if(mode == NAMEI_LOOKUP) 5999d3fb671Srtm return dp; 6005051da6dSrtm if(mode == NAMEI_CREATE && ret_ip){ 6015051da6dSrtm *ret_ip = dp; 6025051da6dSrtm return 0; 6035051da6dSrtm } 604ab5c2dbbSrsc goto fail; 605ab5c2dbbSrsc 606ab5c2dbbSrsc fail: 607211ff0c6Srtm iput(dp); 608211ff0c6Srtm return 0; 6090633b971Skaashoek } 6109d3fb671Srtm 611bb207a1dSrsc // Write a new directory entry (name, ino) into the directory dp. 612bb207a1dSrsc // Caller must have locked dp. 6139e5970d5Srtm void 6149e5970d5Srtm wdir(struct inode *dp, char *name, uint ino) 6159e5970d5Srtm { 6169e5970d5Srtm uint off; 617e4bcd2a3Srtm struct dirent de; 6189e5970d5Srtm int i; 6199e5970d5Srtm 620e4bcd2a3Srtm for(off = 0; off < dp->size; off += sizeof(de)){ 621e4bcd2a3Srtm if(readi(dp, (char*) &de, off, sizeof(de)) != sizeof(de)) 622e4bcd2a3Srtm panic("wdir read"); 623e4bcd2a3Srtm if(de.inum == 0) 624e4bcd2a3Srtm break; 625e4bcd2a3Srtm } 626211ff0c6Srtm 627e4bcd2a3Srtm de.inum = ino; 6282aa4c3bcSrtm for(i = 0; i < DIRSIZ && name[i]; i++) 629e4bcd2a3Srtm de.name[i] = name[i]; 6309e5970d5Srtm for( ; i < DIRSIZ; i++) 631e4bcd2a3Srtm de.name[i] = '\0'; 632e4bcd2a3Srtm 633e4bcd2a3Srtm if(writei(dp, (char*) &de, off, sizeof(de)) != sizeof(de)) 634e4bcd2a3Srtm panic("wdir write"); 6359e5970d5Srtm } 6369e5970d5Srtm 637b6095304Srsc // Create the path and return its locked inode structure. 638bb207a1dSrsc // If cp already exists, return 0. 639e8d11c2eSkaashoek struct inode* 640b6095304Srsc mknod(char *path, short type, short major, short minor) 641e8d11c2eSkaashoek { 6420633b971Skaashoek struct inode *ip, *dp; 6435051da6dSrtm char *last; 644e8d11c2eSkaashoek 645b6095304Srsc if((dp = namei(path, NAMEI_CREATE, 0, &last, 0)) == 0) 6460633b971Skaashoek return 0; 647211ff0c6Srtm 6485051da6dSrtm ip = mknod1(dp, last, type, major, minor); 6495051da6dSrtm 6505051da6dSrtm iput(dp); 6515051da6dSrtm 6525051da6dSrtm return ip; 6535051da6dSrtm } 6545051da6dSrtm 655bb207a1dSrsc // Create a new inode named name inside dp 656bb207a1dSrsc // and return its locked inode structure. 657bb207a1dSrsc // If name already exists, return 0. 6585051da6dSrtm struct inode* 6595051da6dSrtm mknod1(struct inode *dp, char *name, short type, short major, short minor) 6605051da6dSrtm { 6615051da6dSrtm struct inode *ip; 6625051da6dSrtm 663e8d11c2eSkaashoek ip = ialloc(dp->dev, type); 6642aa4c3bcSrtm if(ip == 0) 6650633b971Skaashoek return 0; 666e8d11c2eSkaashoek ip->major = major; 667e8d11c2eSkaashoek ip->minor = minor; 6686c0e444fSkaashoek ip->size = 0; 6697ce01cf9Srtm ip->nlink = 1; 6706c0e444fSkaashoek 6716c0e444fSkaashoek iupdate(ip); // write new inode to disk 672e8d11c2eSkaashoek 6735051da6dSrtm wdir(dp, name, ip->inum); 6745051da6dSrtm 675e8d11c2eSkaashoek return ip; 676e8d11c2eSkaashoek } 67724437cd5Skaashoek 678bb207a1dSrsc // Unlink the inode named cp. 67924437cd5Skaashoek int 680b6095304Srsc unlink(char *path) 68124437cd5Skaashoek { 682211ff0c6Srtm struct inode *ip, *dp; 683211ff0c6Srtm struct dirent de; 68417e3cf15Srtm uint off, inum, dev; 68524437cd5Skaashoek 686b6095304Srsc dp = namei(path, NAMEI_DELETE, &off, 0, 0); 6875051da6dSrtm if(dp == 0) 68824437cd5Skaashoek return -1; 68924437cd5Skaashoek 69017e3cf15Srtm dev = dp->dev; 69117e3cf15Srtm 69217e3cf15Srtm if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de) || de.inum == 0) 693211ff0c6Srtm panic("unlink no entry"); 69417e3cf15Srtm 695ab5c2dbbSrsc // Cannot remove "." or ".." - the 2 and 3 count the trailing NUL. 696ab5c2dbbSrsc if(memcmp(de.name, ".", 2) == 0 || memcmp(de.name, "..", 3) == 0){ 697ab5c2dbbSrsc iput(dp); 698ab5c2dbbSrsc return -1; 699ab5c2dbbSrsc } 700ab5c2dbbSrsc 701211ff0c6Srtm inum = de.inum; 70224437cd5Skaashoek 703211ff0c6Srtm memset(&de, 0, sizeof(de)); 704211ff0c6Srtm if(writei(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 705211ff0c6Srtm panic("unlink dir write"); 70624437cd5Skaashoek 70724437cd5Skaashoek iupdate(dp); 70824437cd5Skaashoek iput(dp); 709211ff0c6Srtm 71017e3cf15Srtm ip = iget(dev, inum); 711211ff0c6Srtm 712bcfb84b6Srtm if(ip->nlink < 1) 713bcfb84b6Srtm panic("unlink nlink < 1"); 714bcfb84b6Srtm 715211ff0c6Srtm ip->nlink--; 716211ff0c6Srtm 717211ff0c6Srtm iupdate(ip); 71822bac2cbSkaashoek iput(ip); 719211ff0c6Srtm 72024437cd5Skaashoek return 0; 72124437cd5Skaashoek } 7229e5970d5Srtm 723bb207a1dSrsc // Create the path new as a link to the same inode as old. 7249e5970d5Srtm int 7259e5970d5Srtm link(char *name1, char *name2) 7269e5970d5Srtm { 727211ff0c6Srtm struct inode *ip, *dp; 7285051da6dSrtm char *last; 7299e5970d5Srtm 7305051da6dSrtm if((ip = namei(name1, NAMEI_LOOKUP, 0, 0, 0)) == 0) 7319e5970d5Srtm return -1; 732211ff0c6Srtm if(ip->type == T_DIR){ 733211ff0c6Srtm iput(ip); 734211ff0c6Srtm return -1; 735211ff0c6Srtm } 7369e5970d5Srtm 737211ff0c6Srtm iunlock(ip); 738211ff0c6Srtm 7395051da6dSrtm if((dp = namei(name2, NAMEI_CREATE, 0, &last, 0)) == 0) { 740211ff0c6Srtm idecref(ip); 741211ff0c6Srtm return -1; 742211ff0c6Srtm } 743211ff0c6Srtm if(dp->dev != ip->dev){ 744211ff0c6Srtm idecref(ip); 745211ff0c6Srtm iput(dp); 746211ff0c6Srtm return -1; 747211ff0c6Srtm } 748211ff0c6Srtm 749211ff0c6Srtm ilock(ip); 750be29b8e2Srsc ip->nlink++; 7519e5970d5Srtm iupdate(ip); 7529e5970d5Srtm 7535051da6dSrtm wdir(dp, last, ip->inum); 7549e5970d5Srtm iput(dp); 7559e5970d5Srtm iput(ip); 7569e5970d5Srtm 7579e5970d5Srtm return 0; 7589e5970d5Srtm } 759