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)) 2711a9947fSrtm 28bcca6c6bSrsc // Blocks. 295be0039cSrtm 30f5527388Srsc // Allocate a disk block. 3124111398Skaashoek static uint 3224111398Skaashoek balloc(uint dev) 3324111398Skaashoek { 347d4aef6cSrsc int b, bi, m, ninodes, size; 3524111398Skaashoek struct buf *bp; 3624111398Skaashoek struct superblock *sb; 3724111398Skaashoek 3824111398Skaashoek bp = bread(dev, 1); 3924111398Skaashoek sb = (struct superblock*) bp->data; 4024111398Skaashoek size = sb->size; 4124111398Skaashoek ninodes = sb->ninodes; 4224111398Skaashoek 4324111398Skaashoek for(b = 0; b < size; b++) { 4424111398Skaashoek if(b % BPB == 0) { 4524111398Skaashoek brelse(bp); 4624111398Skaashoek bp = bread(dev, BBLOCK(b, ninodes)); 4724111398Skaashoek } 4824111398Skaashoek bi = b % BPB; 4924111398Skaashoek m = 0x1 << (bi % 8); 5024111398Skaashoek if((bp->data[bi/8] & m) == 0) { // is block free? 5124111398Skaashoek bp->data[bi/8] |= 0x1 << (bi % 8); 5205e97551Srtm bwrite(bp, BBLOCK(b, ninodes)); // mark it allocated on disk 5328d9ef04Skaashoek brelse(bp); 5424111398Skaashoek return b; 5524111398Skaashoek } 567d4aef6cSrsc } 577d4aef6cSrsc panic("balloc: out of blocks"); 587d4aef6cSrsc } 5924111398Skaashoek 60bb207a1dSrsc // Free a disk block. 6128d9ef04Skaashoek static void 6228d9ef04Skaashoek bfree(int dev, uint b) 6328d9ef04Skaashoek { 6428d9ef04Skaashoek struct buf *bp; 6528d9ef04Skaashoek struct superblock *sb; 667d4aef6cSrsc int bi, m, ninodes; 6728d9ef04Skaashoek 6828d9ef04Skaashoek bp = bread(dev, 1); 6928d9ef04Skaashoek sb = (struct superblock*) bp->data; 7028d9ef04Skaashoek ninodes = sb->ninodes; 7128d9ef04Skaashoek brelse(bp); 7228d9ef04Skaashoek 73c372e8dcSkaashoek bp = bread(dev, b); 74c372e8dcSkaashoek memset(bp->data, 0, BSIZE); 75c372e8dcSkaashoek bwrite(bp, b); 76c372e8dcSkaashoek brelse(bp); 77c372e8dcSkaashoek 7828d9ef04Skaashoek bp = bread(dev, BBLOCK(b, ninodes)); 7928d9ef04Skaashoek bi = b % BPB; 807d4aef6cSrsc m = 0x1 << (bi % 8); 817d4aef6cSrsc bp->data[bi/8] &= ~m; 8205e97551Srtm bwrite(bp, BBLOCK(b, ninodes)); // mark it free on disk 8328d9ef04Skaashoek brelse(bp); 8428d9ef04Skaashoek } 8524111398Skaashoek 86bcca6c6bSrsc // Inodes 87bcca6c6bSrsc // 88bcca6c6bSrsc // The inodes are laid out sequentially on disk immediately after 89bcca6c6bSrsc // the superblock. The kernel keeps a cache of the in-use 90bcca6c6bSrsc // on-disk structures to provide a place for synchronizing access 91bcca6c6bSrsc // to inodes shared between multiple processes. 92bcca6c6bSrsc // 93bcca6c6bSrsc // ip->ref counts the number of references to this 94bcca6c6bSrsc // inode; references are typically kept in struct file and in cp->cwd. 95bcca6c6bSrsc // When ip->ref falls to zero, the inode is no longer cached. 96bcca6c6bSrsc // It is an error to use an inode without holding a reference to it. 97bcca6c6bSrsc // 98bcca6c6bSrsc // Inodes can be marked busy, just like bufs, meaning 99bcca6c6bSrsc // that some process has logically locked the inode, and other processes 100bcca6c6bSrsc // are not allowed to look at it. Because the locking can last for 101bcca6c6bSrsc // a long time (for example, during a disk access), we use a flag 102bcca6c6bSrsc // like in buffer cache, not spin locks. The inode should always be 103bcca6c6bSrsc // locked during modifications to it. 104bcca6c6bSrsc 105bcca6c6bSrsc struct { 106bcca6c6bSrsc struct spinlock lock; 107bcca6c6bSrsc struct inode inode[NINODE]; 108bcca6c6bSrsc } icache; 109bcca6c6bSrsc 110bcca6c6bSrsc void 111bcca6c6bSrsc iinit(void) 112bcca6c6bSrsc { 113bcca6c6bSrsc initlock(&icache.lock, "icache.lock"); 114bcca6c6bSrsc } 115bcca6c6bSrsc 116f5527388Srsc // Find the inode with number inum on device dev 117*f32f3638Srsc // and return the in-memory copy. The returned inode 118*f32f3638Srsc // has its reference count incremented (and thus must be 119*f32f3638Srsc // idecref'ed), but is *unlocked*, meaning that none of the fields 120*f32f3638Srsc // except dev and inum are guaranteed to be initialized. 121*f32f3638Srsc // This convention gives the caller maximum control over blocking; 122*f32f3638Srsc // it also guarantees that iget will not sleep, which is useful in 123*f32f3638Srsc // the early igetroot and when holding other locked inodes. 12411a9947fSrtm struct inode* 12511a9947fSrtm iget(uint dev, uint inum) 12611a9947fSrtm { 127bcca6c6bSrsc struct inode *ip, *empty; 12811a9947fSrtm 129bcca6c6bSrsc acquire(&icache.lock); 13011a9947fSrtm 131bcca6c6bSrsc // Try for cached inode. 132bcca6c6bSrsc empty = 0; 133bcca6c6bSrsc for(ip = &icache.inode[0]; ip < &icache.inode[NINODE]; ip++){ 1340d6bbd31Srsc if(ip->ref > 0 && ip->dev == dev && ip->inum == inum){ 1350d6bbd31Srsc ip->ref++; 136bcca6c6bSrsc release(&icache.lock); 13711a9947fSrtm return ip; 13811a9947fSrtm } 139bcca6c6bSrsc if(empty == 0 && ip->ref == 0) // Remember empty slot. 140bcca6c6bSrsc empty = ip; 14111a9947fSrtm } 14211a9947fSrtm 143bcca6c6bSrsc // Allocate fresh inode. 144bcca6c6bSrsc if(empty == 0) 14532eea766Srsc panic("iget: no inodes"); 14611a9947fSrtm 147bcca6c6bSrsc ip = empty; 148bcca6c6bSrsc ip->dev = dev; 149bcca6c6bSrsc ip->inum = inum; 150bcca6c6bSrsc ip->ref = 1; 151*f32f3638Srsc ip->flags = 0; 152bcca6c6bSrsc release(&icache.lock); 15311a9947fSrtm 154*f32f3638Srsc return ip; 155*f32f3638Srsc } 156*f32f3638Srsc 157*f32f3638Srsc // Iget the inode for the file system root (/). 158*f32f3638Srsc // This gets called before there is a current process: it cannot sleep! 159*f32f3638Srsc struct inode* 160*f32f3638Srsc igetroot(void) 161*f32f3638Srsc { 162*f32f3638Srsc struct inode *ip; 163*f32f3638Srsc ip = iget(ROOTDEV, 1); 164*f32f3638Srsc return ip; 165*f32f3638Srsc } 166*f32f3638Srsc 167*f32f3638Srsc // Lock the given inode. 168*f32f3638Srsc void 169*f32f3638Srsc ilock(struct inode *ip) 170*f32f3638Srsc { 171*f32f3638Srsc struct buf *bp; 172*f32f3638Srsc struct dinode *dip; 173*f32f3638Srsc 174*f32f3638Srsc if(ip->ref < 1) 175*f32f3638Srsc panic("ilock"); 176*f32f3638Srsc 177*f32f3638Srsc acquire(&icache.lock); 178*f32f3638Srsc while(ip->flags & I_BUSY) 179*f32f3638Srsc sleep(ip, &icache.lock); 180*f32f3638Srsc ip->flags |= I_BUSY; 181*f32f3638Srsc release(&icache.lock); 182*f32f3638Srsc 183*f32f3638Srsc if(!(ip->flags & I_VALID)){ 184*f32f3638Srsc bp = bread(ip->dev, IBLOCK(ip->inum)); 185*f32f3638Srsc dip = &((struct dinode*)(bp->data))[ip->inum % IPB]; 186bcca6c6bSrsc ip->type = dip->type; 187bcca6c6bSrsc ip->major = dip->major; 188bcca6c6bSrsc ip->minor = dip->minor; 189bcca6c6bSrsc ip->nlink = dip->nlink; 190bcca6c6bSrsc ip->size = dip->size; 191bcca6c6bSrsc memmove(ip->addrs, dip->addrs, sizeof(ip->addrs)); 19211a9947fSrtm brelse(bp); 193*f32f3638Srsc ip->flags |= I_VALID; 19411a9947fSrtm } 195bcca6c6bSrsc } 196bcca6c6bSrsc 197bcca6c6bSrsc // Unlock the given inode. 198bcca6c6bSrsc void 199bcca6c6bSrsc iunlock(struct inode *ip) 200bcca6c6bSrsc { 201*f32f3638Srsc if(!(ip->flags & I_BUSY) || ip->ref < 1) 202bcca6c6bSrsc panic("iunlock"); 203bcca6c6bSrsc 204bcca6c6bSrsc acquire(&icache.lock); 205*f32f3638Srsc ip->flags &= ~I_BUSY; 206bcca6c6bSrsc wakeup(ip); 207bcca6c6bSrsc release(&icache.lock); 208bcca6c6bSrsc } 209bcca6c6bSrsc 210bcca6c6bSrsc // Unlock inode and drop reference. 211bcca6c6bSrsc void 212bcca6c6bSrsc iput(struct inode *ip) 213bcca6c6bSrsc { 214*f32f3638Srsc iunlock(ip); 215*f32f3638Srsc idecref(ip); 216bcca6c6bSrsc } 217bcca6c6bSrsc 218bcca6c6bSrsc // Increment reference count for ip. 219bcca6c6bSrsc // Returns ip to enable ip = iincref(ip1) idiom. 220bcca6c6bSrsc struct inode* 221bcca6c6bSrsc iincref(struct inode *ip) 222bcca6c6bSrsc { 223*f32f3638Srsc acquire(&icache.lock); 224bcca6c6bSrsc ip->ref++; 225*f32f3638Srsc release(&icache.lock); 226bcca6c6bSrsc return ip; 227bcca6c6bSrsc } 228bcca6c6bSrsc 229*f32f3638Srsc // Caller holds reference to unlocked ip. Drop reference. 230bcca6c6bSrsc void 231bcca6c6bSrsc idecref(struct inode *ip) 232bcca6c6bSrsc { 233*f32f3638Srsc acquire(&icache.lock); 234*f32f3638Srsc if(ip->ref == 1 && (ip->flags & I_VALID) && ip->nlink == 0) { 235*f32f3638Srsc // inode is no longer used: truncate and free inode. 236*f32f3638Srsc if(ip->flags & I_BUSY) 237*f32f3638Srsc panic("idecref busy"); 238*f32f3638Srsc ip->flags |= I_BUSY; 239*f32f3638Srsc release(&icache.lock); 240*f32f3638Srsc // XXX convince rsc that no one will come find this inode. 241*f32f3638Srsc itrunc(ip); 242*f32f3638Srsc ip->type = 0; 243*f32f3638Srsc iupdate(ip); 244*f32f3638Srsc acquire(&icache.lock); 245*f32f3638Srsc ip->flags &= ~I_BUSY; 246*f32f3638Srsc } 247*f32f3638Srsc ip->ref--; 248*f32f3638Srsc release(&icache.lock); 249bcca6c6bSrsc } 250bcca6c6bSrsc 251bcca6c6bSrsc // Allocate a new inode with the given type on device dev. 252e8d11c2eSkaashoek struct inode* 253e8d11c2eSkaashoek ialloc(uint dev, short type) 254e8d11c2eSkaashoek { 255*f32f3638Srsc int inum, ninodes; 256*f32f3638Srsc struct buf *bp; 2577d4aef6cSrsc struct dinode *dip; 258e8d11c2eSkaashoek struct superblock *sb; 259e8d11c2eSkaashoek 260e8d11c2eSkaashoek bp = bread(dev, 1); 26124111398Skaashoek sb = (struct superblock*)bp->data; 262e8d11c2eSkaashoek ninodes = sb->ninodes; 263e8d11c2eSkaashoek brelse(bp); 264e8d11c2eSkaashoek 265e8d11c2eSkaashoek for(inum = 1; inum < ninodes; inum++) { // loop over inode blocks 26624111398Skaashoek bp = bread(dev, IBLOCK(inum)); 267e8d11c2eSkaashoek dip = &((struct dinode*)(bp->data))[inum % IPB]; 268e8d11c2eSkaashoek if(dip->type == 0) { // a free inode 2692aa4c3bcSrtm memset(dip, 0, sizeof(*dip)); 270e8d11c2eSkaashoek dip->type = type; 27105e97551Srtm bwrite(bp, IBLOCK(inum)); // mark it allocated on the disk 272e8d11c2eSkaashoek brelse(bp); 273*f32f3638Srsc return iget(dev, inum); 274e8d11c2eSkaashoek } 27595c07f82Srsc brelse(bp); 27695c07f82Srsc } 27795c07f82Srsc panic("ialloc: no inodes"); 27895c07f82Srsc } 279e8d11c2eSkaashoek 280bcca6c6bSrsc // Copy inode, which has changed, from memory to disk. 281bcca6c6bSrsc void 282bcca6c6bSrsc iupdate(struct inode *ip) 283bcca6c6bSrsc { 284bcca6c6bSrsc struct buf *bp; 285bcca6c6bSrsc struct dinode *dip; 286bcca6c6bSrsc 287bcca6c6bSrsc bp = bread(ip->dev, IBLOCK(ip->inum)); 288bcca6c6bSrsc dip = &((struct dinode*)(bp->data))[ip->inum % IPB]; 289bcca6c6bSrsc dip->type = ip->type; 290bcca6c6bSrsc dip->major = ip->major; 291bcca6c6bSrsc dip->minor = ip->minor; 292bcca6c6bSrsc dip->nlink = ip->nlink; 293bcca6c6bSrsc dip->size = ip->size; 294bcca6c6bSrsc memmove(dip->addrs, ip->addrs, sizeof(ip->addrs)); 295bcca6c6bSrsc bwrite(bp, IBLOCK(ip->inum)); 296bcca6c6bSrsc brelse(bp); 297bcca6c6bSrsc } 298bcca6c6bSrsc 299bcca6c6bSrsc // Inode contents 300bcca6c6bSrsc // 301bcca6c6bSrsc // The contents (data) associated with each inode is stored 302bcca6c6bSrsc // in a sequence of blocks on the disk. The first NDIRECT blocks 303bcca6c6bSrsc // are stored in ip->addrs[]. The next NINDIRECT blocks are 304bcca6c6bSrsc // listed in the block ip->addrs[INDIRECT]. 3059d3fb671Srtm 306bb207a1dSrsc // Return the disk block address of the nth block in inode ip. 307bcca6c6bSrsc // If there is no such block: if alloc is set, allocate one, else return -1. 30822bac2cbSkaashoek uint 309bcca6c6bSrsc bmap(struct inode *ip, uint bn, int alloc) 31022bac2cbSkaashoek { 311bcca6c6bSrsc uint addr, *a; 312bcca6c6bSrsc struct buf *bp; 31322bac2cbSkaashoek 314ea2909b6Skaashoek if(bn < NDIRECT) { 315bcca6c6bSrsc if((addr = ip->addrs[bn]) == 0) { 316bcca6c6bSrsc if(!alloc) 317bcca6c6bSrsc return -1; 318bcca6c6bSrsc ip->addrs[bn] = addr = balloc(ip->dev); 319ea2909b6Skaashoek } 320bcca6c6bSrsc return addr; 321bcca6c6bSrsc } 322bcca6c6bSrsc bn -= NDIRECT; 323bcca6c6bSrsc 324bcca6c6bSrsc if(bn < NINDIRECT) { 325bcca6c6bSrsc // Load indirect block, allocating if necessary. 326bcca6c6bSrsc if((addr = ip->addrs[INDIRECT]) == 0) { 327bcca6c6bSrsc if(!alloc) 328bcca6c6bSrsc return -1; 329bcca6c6bSrsc ip->addrs[INDIRECT] = addr = balloc(ip->dev); 330bcca6c6bSrsc } 331bcca6c6bSrsc bp = bread(ip->dev, addr); 332bcca6c6bSrsc a = (uint*)bp->data; 333bcca6c6bSrsc 334bcca6c6bSrsc if((addr = a[bn]) == 0) { 335bcca6c6bSrsc if(!alloc) { 336bcca6c6bSrsc brelse(bp); 337bcca6c6bSrsc return -1; 338bcca6c6bSrsc } 339bcca6c6bSrsc a[bn] = addr = balloc(ip->dev); 340bcca6c6bSrsc bwrite(bp, ip->addrs[INDIRECT]); 341bcca6c6bSrsc } 342bcca6c6bSrsc brelse(bp); 343bcca6c6bSrsc return addr; 34422bac2cbSkaashoek } 34522bac2cbSkaashoek 346bcca6c6bSrsc panic("bmap: out of range"); 347bcca6c6bSrsc } 348bcca6c6bSrsc 349bcca6c6bSrsc // Truncate inode (discard contents). 35022bac2cbSkaashoek void 3512aa4c3bcSrtm itrunc(struct inode *ip) 35222bac2cbSkaashoek { 353ea2909b6Skaashoek int i, j; 354bcca6c6bSrsc struct buf *bp; 3557d4aef6cSrsc uint *a; 35622bac2cbSkaashoek 357bcca6c6bSrsc for(i = 0; i < NDIRECT; i++) { 358bcca6c6bSrsc if(ip->addrs[i]) { 35922bac2cbSkaashoek bfree(ip->dev, ip->addrs[i]); 36022bac2cbSkaashoek ip->addrs[i] = 0; 36122bac2cbSkaashoek } 36222bac2cbSkaashoek } 363bcca6c6bSrsc 364bcca6c6bSrsc if(ip->addrs[INDIRECT]) { 365bcca6c6bSrsc bp = bread(ip->dev, ip->addrs[INDIRECT]); 366bcca6c6bSrsc a = (uint*)bp->data; 367bcca6c6bSrsc for(j = 0; j < NINDIRECT; j++) { 368bcca6c6bSrsc if(a[j]) 369bcca6c6bSrsc bfree(ip->dev, a[j]); 370bcca6c6bSrsc } 371bcca6c6bSrsc brelse(bp); 372bcca6c6bSrsc ip->addrs[INDIRECT] = 0; 373bcca6c6bSrsc } 374bcca6c6bSrsc 37522bac2cbSkaashoek ip->size = 0; 37622bac2cbSkaashoek iupdate(ip); 37722bac2cbSkaashoek } 37822bac2cbSkaashoek 379bb207a1dSrsc // Copy stat information from inode. 380e958c538Skaashoek void 3811f544842Skaashoek stati(struct inode *ip, struct stat *st) 3821f544842Skaashoek { 3831dca3afbSrsc st->dev = ip->dev; 3841dca3afbSrsc st->ino = ip->inum; 3851dca3afbSrsc st->type = ip->type; 3861dca3afbSrsc st->nlink = ip->nlink; 3871dca3afbSrsc st->size = ip->size; 3881f544842Skaashoek } 3891f544842Skaashoek 390bb207a1dSrsc // Read data from inode. 391c59361f1Srtm int 39217a85657Srtm readi(struct inode *ip, char *dst, uint off, uint n) 393c59361f1Srtm { 394bcca6c6bSrsc uint tot, m; 395c59361f1Srtm struct buf *bp; 396c59361f1Srtm 397939f9edeSkaashoek if(ip->type == T_DEV) { 3981dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].read) 399939f9edeSkaashoek return -1; 4001dca3afbSrsc return devsw[ip->major].read(ip->minor, dst, n); 401939f9edeSkaashoek } 402939f9edeSkaashoek 403bcca6c6bSrsc if(off + n < off) 404bcca6c6bSrsc return -1; 405bcca6c6bSrsc if(off + n > ip->size) 406bcca6c6bSrsc n = ip->size - off; 407bcca6c6bSrsc 408bcca6c6bSrsc for(tot=0; tot<n; tot+=m, off+=m, dst+=m) { 409bcca6c6bSrsc bp = bread(ip->dev, bmap(ip, off/BSIZE, 0)); 410bcca6c6bSrsc m = min(n - tot, BSIZE - off%BSIZE); 411bcca6c6bSrsc memmove(dst, bp->data + off%BSIZE, m); 412c59361f1Srtm brelse(bp); 413c59361f1Srtm } 414bcca6c6bSrsc return n; 415ea2909b6Skaashoek } 416ea2909b6Skaashoek 417bb207a1dSrsc // Write data to inode. 418ea2909b6Skaashoek int 419bcca6c6bSrsc writei(struct inode *ip, char *src, uint off, uint n) 4206fa5ffb5Skaashoek { 421bcca6c6bSrsc uint tot, m; 4227d4aef6cSrsc struct buf *bp; 4237d4aef6cSrsc 4246fa5ffb5Skaashoek if(ip->type == T_DEV) { 4251dca3afbSrsc if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].write) 426939f9edeSkaashoek return -1; 427bcca6c6bSrsc return devsw[ip->major].write(ip->minor, src, n); 4287d4aef6cSrsc } 4297d4aef6cSrsc 430bcca6c6bSrsc if(off + n < off) 431bcca6c6bSrsc return -1; 432bcca6c6bSrsc if(off + n > MAXFILE*BSIZE) 433bcca6c6bSrsc n = MAXFILE*BSIZE - off; 434bcca6c6bSrsc 435bcca6c6bSrsc for(tot=0; tot<n; tot+=m, off+=m, src+=m) { 436bcca6c6bSrsc bp = bread(ip->dev, bmap(ip, off/BSIZE, 1)); 437bcca6c6bSrsc m = min(n - tot, BSIZE - off%BSIZE); 438bcca6c6bSrsc memmove(bp->data + off%BSIZE, src, m); 439bcca6c6bSrsc bwrite(bp, bmap(ip, off/BSIZE, 0)); 44028d9ef04Skaashoek brelse(bp); 44128d9ef04Skaashoek } 442bcca6c6bSrsc 443bcca6c6bSrsc if(n > 0 && off > ip->size) { 44448b82470Srsc ip->size = off; 44528d9ef04Skaashoek iupdate(ip); 44628d9ef04Skaashoek } 447bcca6c6bSrsc return n; 4486fa5ffb5Skaashoek } 4496fa5ffb5Skaashoek 450bcca6c6bSrsc // Directories 451bcca6c6bSrsc // 452bcca6c6bSrsc // Directories are just inodes (files) filled with dirent structures. 453bcca6c6bSrsc 454bcca6c6bSrsc // Look for a directory entry in a directory. 455bcca6c6bSrsc // If not found, return -1. 456bcca6c6bSrsc // If found: 457bcca6c6bSrsc // set *poff to the byte offset of the directory entry 458bcca6c6bSrsc // set *pinum to the inode number 459bcca6c6bSrsc // return 0. 460*f32f3638Srsc struct inode* 461*f32f3638Srsc dirlookup(struct inode *dp, char *name, int namelen, uint *poff) 462bcca6c6bSrsc { 463*f32f3638Srsc uint off, inum; 464bcca6c6bSrsc struct buf *bp; 465bcca6c6bSrsc struct dirent *de; 466bcca6c6bSrsc 467bcca6c6bSrsc if(dp->type != T_DIR) 468*f32f3638Srsc return 0; 469bcca6c6bSrsc 470bcca6c6bSrsc for(off = 0; off < dp->size; off += BSIZE){ 471bcca6c6bSrsc bp = bread(dp->dev, bmap(dp, off / BSIZE, 0)); 472bcca6c6bSrsc for(de = (struct dirent*) bp->data; 473bcca6c6bSrsc de < (struct dirent*) (bp->data + BSIZE); 474bcca6c6bSrsc de++){ 475bcca6c6bSrsc if(de->inum == 0) 476bcca6c6bSrsc continue; 477bcca6c6bSrsc if(memcmp(name, de->name, namelen) == 0 && 478bcca6c6bSrsc (namelen == DIRSIZ || de->name[namelen]== 0)){ 479bcca6c6bSrsc // entry matches path element 480e2a620daSrsc if(poff) 481bcca6c6bSrsc *poff = off + (uchar*)de - bp->data; 482*f32f3638Srsc inum = de->inum; 483bcca6c6bSrsc brelse(bp); 484*f32f3638Srsc return iget(dp->dev, inum); 485*f32f3638Srsc } 486*f32f3638Srsc } 487*f32f3638Srsc brelse(bp); 488*f32f3638Srsc } 489bcca6c6bSrsc return 0; 490bcca6c6bSrsc } 491bcca6c6bSrsc 492bcca6c6bSrsc // Write a new directory entry (name, ino) into the directory dp. 493bcca6c6bSrsc // Caller must have locked dp. 494*f32f3638Srsc int 495*f32f3638Srsc dirlink(struct inode *dp, char *name, int namelen, uint ino) 496bcca6c6bSrsc { 497e2a620daSrsc int off; 498bcca6c6bSrsc struct dirent de; 499*f32f3638Srsc struct inode *ip; 500*f32f3638Srsc 501*f32f3638Srsc // Double-check that name is not present. 502*f32f3638Srsc if((ip = dirlookup(dp, name, namelen, 0)) != 0){ 503*f32f3638Srsc idecref(ip); 504*f32f3638Srsc return -1; 505*f32f3638Srsc } 506bcca6c6bSrsc 507bcca6c6bSrsc // Look for an empty dirent. 508bcca6c6bSrsc for(off = 0; off < dp->size; off += sizeof(de)){ 509bcca6c6bSrsc if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 510bcca6c6bSrsc panic("dirwrite read"); 511bcca6c6bSrsc if(de.inum == 0) 512bcca6c6bSrsc break; 513bcca6c6bSrsc } 514bcca6c6bSrsc 515bcca6c6bSrsc de.inum = ino; 516e2a620daSrsc if(namelen > DIRSIZ) 517e2a620daSrsc namelen = DIRSIZ; 518e2a620daSrsc memmove(de.name, name, namelen); 519e2a620daSrsc memset(de.name+namelen, 0, DIRSIZ-namelen); 520bcca6c6bSrsc if(writei(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 521bcca6c6bSrsc panic("dirwrite"); 522*f32f3638Srsc 523*f32f3638Srsc return 0; 524bcca6c6bSrsc } 525bcca6c6bSrsc 526e2a620daSrsc // Create a new inode named name inside dp 527e2a620daSrsc // and return its locked inode structure. 528e2a620daSrsc // If name already exists, return 0. 529e2a620daSrsc struct inode* 530e2a620daSrsc dircreat(struct inode *dp, char *name, int namelen, short type, short major, short minor) 531e2a620daSrsc { 532e2a620daSrsc struct inode *ip; 533e2a620daSrsc 534e2a620daSrsc ip = ialloc(dp->dev, type); 535e2a620daSrsc if(ip == 0) 536e2a620daSrsc return 0; 537*f32f3638Srsc ilock(ip); 538e2a620daSrsc ip->major = major; 539e2a620daSrsc ip->minor = minor; 540e2a620daSrsc ip->size = 0; 541e2a620daSrsc ip->nlink = 1; 542e2a620daSrsc iupdate(ip); 543e2a620daSrsc 544*f32f3638Srsc if(dirlink(dp, name, namelen, ip->inum) < 0){ 545*f32f3638Srsc ip->nlink = 0; 546*f32f3638Srsc iupdate(ip); 547*f32f3638Srsc iput(ip); 548*f32f3638Srsc return 0; 549*f32f3638Srsc } 550e2a620daSrsc 551e2a620daSrsc return ip; 552e2a620daSrsc } 553e2a620daSrsc 554bcca6c6bSrsc // Paths 555bcca6c6bSrsc 556ab5c2dbbSrsc // Skip over the next path element in path, 557ab5c2dbbSrsc // saving it in *name and its length in *len. 558ab5c2dbbSrsc // Return a pointer to the element after that 559ab5c2dbbSrsc // (after any trailing slashes). 560ab5c2dbbSrsc // Thus the caller can check whether *path=='\0' 561ab5c2dbbSrsc // to see whether the name just removed was 562ab5c2dbbSrsc // the last one. 563ab5c2dbbSrsc // If there is no name to remove, return 0. 564ab5c2dbbSrsc // 565ab5c2dbbSrsc // Examples: 566ab5c2dbbSrsc // skipelem("a/bb/c") = "bb/c", with *name = "a/bb/c", len=1 567ab5c2dbbSrsc // skipelem("///a/bb") = "b", with *name="a/bb", len=1 568ab5c2dbbSrsc // skipelem("") = skipelem("////") = 0 569ab5c2dbbSrsc // 570ab5c2dbbSrsc static char* 571ab5c2dbbSrsc skipelem(char *path, char **name, int *len) 572ab5c2dbbSrsc { 573ab5c2dbbSrsc while(*path == '/') 574ab5c2dbbSrsc path++; 575ab5c2dbbSrsc if(*path == 0) 576ab5c2dbbSrsc return 0; 577ab5c2dbbSrsc *name = path; 578ab5c2dbbSrsc while(*path != '/' && *path != 0) 579ab5c2dbbSrsc path++; 580ab5c2dbbSrsc *len = path - *name; 581ab5c2dbbSrsc while(*path == '/') 582ab5c2dbbSrsc path++; 583ab5c2dbbSrsc return path; 584ab5c2dbbSrsc } 585ab5c2dbbSrsc 586211ff0c6Srtm // look up a path name, in one of three modes. 587211ff0c6Srtm // NAMEI_LOOKUP: return locked target inode. 588211ff0c6Srtm // NAMEI_CREATE: return locked parent inode. 5895051da6dSrtm // return 0 if name does exist. 5905051da6dSrtm // *ret_last points to last path component (i.e. new file name). 5915051da6dSrtm // *ret_ip points to the the name that did exist, if it did. 5925051da6dSrtm // *ret_ip and *ret_last may be zero even if return value is zero. 593211ff0c6Srtm // NAMEI_DELETE: return locked parent inode, offset of dirent in *ret_off. 594211ff0c6Srtm // return 0 if name doesn't exist. 5959d3fb671Srtm struct inode* 596e2a620daSrsc _namei(char *path, int parent, char **pname, int *pnamelen) 5979d3fb671Srtm { 598*f32f3638Srsc struct inode *dp, *ip; 599ab5c2dbbSrsc char *name; 600ab5c2dbbSrsc int namelen; 601*f32f3638Srsc uint off; 6029d3fb671Srtm 603ab5c2dbbSrsc if(*path == '/') 604bcca6c6bSrsc dp = igetroot(); 605*f32f3638Srsc else 606bc011703Srsc dp = iincref(cp->cwd); 6078787cd01Skaashoek ilock(dp); 6089d3fb671Srtm 609ab5c2dbbSrsc while((path = skipelem(path, &name, &namelen)) != 0){ 610ab5c2dbbSrsc // Truncate names in path to DIRSIZ chars. 611ab5c2dbbSrsc if(namelen > DIRSIZ) 612ab5c2dbbSrsc namelen = DIRSIZ; 6139d3fb671Srtm 614ab5c2dbbSrsc if(dp->type != T_DIR) 615ab5c2dbbSrsc goto fail; 616ab5c2dbbSrsc 617e2a620daSrsc if(parent && *path == '\0'){ 618e2a620daSrsc // Stop one level early. 619e2a620daSrsc *pname = name; 620e2a620daSrsc *pnamelen = namelen; 621ab5c2dbbSrsc return dp; 622ab5c2dbbSrsc } 623ab5c2dbbSrsc 624*f32f3638Srsc if((ip = dirlookup(dp, name, namelen, &off)) == 0) 625ab5c2dbbSrsc goto fail; 626ab5c2dbbSrsc 627ab5c2dbbSrsc iput(dp); 628*f32f3638Srsc ilock(ip); 629*f32f3638Srsc dp = ip; 630ab5c2dbbSrsc if(dp->type == 0 || dp->nlink < 1) 631ab5c2dbbSrsc panic("namei"); 632ab5c2dbbSrsc } 633e2a620daSrsc if(parent) 6345051da6dSrtm return 0; 635e2a620daSrsc return dp; 636ab5c2dbbSrsc 637ab5c2dbbSrsc fail: 638211ff0c6Srtm iput(dp); 639211ff0c6Srtm return 0; 6400633b971Skaashoek } 6419d3fb671Srtm 642e2a620daSrsc struct inode* 643e2a620daSrsc namei(char *path) 644e2a620daSrsc { 645e2a620daSrsc return _namei(path, 0, 0, 0); 646e2a620daSrsc } 647e2a620daSrsc 648e2a620daSrsc struct inode* 649e2a620daSrsc nameiparent(char *path, char **name, int *namelen) 650e2a620daSrsc { 651e2a620daSrsc return _namei(path, 1, name, namelen); 652e2a620daSrsc } 653e2a620daSrsc 654e2a620daSrsc 655e2a620daSrsc 656b6095304Srsc // Create the path and return its locked inode structure. 657bb207a1dSrsc // If cp already exists, return 0. 658e8d11c2eSkaashoek struct inode* 659b6095304Srsc mknod(char *path, short type, short major, short minor) 660e8d11c2eSkaashoek { 6610633b971Skaashoek struct inode *ip, *dp; 662e2a620daSrsc char *name; 663e2a620daSrsc int namelen; 664e8d11c2eSkaashoek 665e2a620daSrsc if((dp = nameiparent(path, &name, &namelen)) == 0) 6660633b971Skaashoek return 0; 667e2a620daSrsc ip = dircreat(dp, name, namelen, type, major, minor); 668e2a620daSrsc iput(dp); 669e8d11c2eSkaashoek return ip; 670e8d11c2eSkaashoek } 67124437cd5Skaashoek 672bb207a1dSrsc // Unlink the inode named cp. 67324437cd5Skaashoek int 674b6095304Srsc unlink(char *path) 67524437cd5Skaashoek { 676211ff0c6Srtm struct inode *ip, *dp; 677211ff0c6Srtm struct dirent de; 678*f32f3638Srsc uint off; 679e2a620daSrsc char *name; 680e2a620daSrsc int namelen; 68124437cd5Skaashoek 682e2a620daSrsc if((dp = nameiparent(path, &name, &namelen)) == 0) 68324437cd5Skaashoek return -1; 684*f32f3638Srsc if((ip = dirlookup(dp, name, namelen, &off)) == 0){ 685e2a620daSrsc iput(dp); 686e2a620daSrsc return -1; 687e2a620daSrsc } 68817e3cf15Srtm 68917e3cf15Srtm if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de) || de.inum == 0) 690211ff0c6Srtm panic("unlink no entry"); 69117e3cf15Srtm 692ab5c2dbbSrsc // Cannot remove "." or ".." - the 2 and 3 count the trailing NUL. 693ab5c2dbbSrsc if(memcmp(de.name, ".", 2) == 0 || memcmp(de.name, "..", 3) == 0){ 694*f32f3638Srsc idecref(ip); 695ab5c2dbbSrsc iput(dp); 696ab5c2dbbSrsc return -1; 697ab5c2dbbSrsc } 698ab5c2dbbSrsc 699211ff0c6Srtm memset(&de, 0, sizeof(de)); 700211ff0c6Srtm if(writei(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) 701211ff0c6Srtm panic("unlink dir write"); 70224437cd5Skaashoek iput(dp); 703211ff0c6Srtm 704*f32f3638Srsc ilock(ip); 705bcfb84b6Srtm if(ip->nlink < 1) 706bcfb84b6Srtm panic("unlink nlink < 1"); 707211ff0c6Srtm ip->nlink--; 708211ff0c6Srtm iupdate(ip); 70922bac2cbSkaashoek iput(ip); 710211ff0c6Srtm 71124437cd5Skaashoek return 0; 71224437cd5Skaashoek } 7139e5970d5Srtm 714bb207a1dSrsc // Create the path new as a link to the same inode as old. 7159e5970d5Srtm int 716e2a620daSrsc link(char *old, char *new) 7179e5970d5Srtm { 718211ff0c6Srtm struct inode *ip, *dp; 719e2a620daSrsc char *name; 720e2a620daSrsc int namelen; 7219e5970d5Srtm 722e2a620daSrsc if((ip = namei(old)) == 0) 7239e5970d5Srtm return -1; 724211ff0c6Srtm if(ip->type == T_DIR){ 725211ff0c6Srtm iput(ip); 726211ff0c6Srtm return -1; 727211ff0c6Srtm } 728211ff0c6Srtm iunlock(ip); 729211ff0c6Srtm 730e2a620daSrsc if((dp = nameiparent(new, &name, &namelen)) == 0){ 731e2a620daSrsc idecref(ip); 732e2a620daSrsc return -1; 733e2a620daSrsc } 734*f32f3638Srsc if(dp->dev != ip->dev || dirlink(dp, name, namelen, ip->inum) < 0){ 735211ff0c6Srtm idecref(ip); 736211ff0c6Srtm iput(dp); 737211ff0c6Srtm return -1; 738211ff0c6Srtm } 739*f32f3638Srsc iput(dp); 740211ff0c6Srtm 741*f32f3638Srsc // XXX write ordering wrong here too. 742211ff0c6Srtm ilock(ip); 743be29b8e2Srsc ip->nlink++; 7449e5970d5Srtm iupdate(ip); 745*f32f3638Srsc iput(ip); 746*f32f3638Srsc return 0; 747*f32f3638Srsc } 7489e5970d5Srtm 749*f32f3638Srsc int 750*f32f3638Srsc mkdir(char *path) 751*f32f3638Srsc { 752*f32f3638Srsc struct inode *dp, *ip; 753*f32f3638Srsc char *name; 754*f32f3638Srsc int namelen; 755*f32f3638Srsc 756*f32f3638Srsc // XXX write ordering is screwy here- do we care? 757*f32f3638Srsc if((dp = nameiparent(path, &name, &namelen)) == 0) 758*f32f3638Srsc return -1; 759*f32f3638Srsc 760*f32f3638Srsc if((ip = dircreat(dp, name, namelen, T_DIR, 0, 0)) == 0){ 761*f32f3638Srsc iput(dp); 762*f32f3638Srsc return -1; 763*f32f3638Srsc } 764*f32f3638Srsc dp->nlink++; 765*f32f3638Srsc iupdate(dp); 766*f32f3638Srsc 767*f32f3638Srsc if(dirlink(ip, ".", 1, ip->inum) < 0 || dirlink(ip, "..", 2, dp->inum) < 0) 768*f32f3638Srsc panic("mkdir"); 7699e5970d5Srtm iput(dp); 7709e5970d5Srtm iput(ip); 7719e5970d5Srtm 7729e5970d5Srtm return 0; 7739e5970d5Srtm } 774*f32f3638Srsc 775*f32f3638Srsc struct inode* 776*f32f3638Srsc create(char *path) 777*f32f3638Srsc { 778*f32f3638Srsc struct inode *dp, *ip; 779*f32f3638Srsc char *name; 780*f32f3638Srsc int namelen; 781*f32f3638Srsc 782*f32f3638Srsc if((dp = nameiparent(path, &name, &namelen)) == 0) 783*f32f3638Srsc return 0; 784*f32f3638Srsc 785*f32f3638Srsc if((ip = dirlookup(dp, name, namelen, 0)) != 0){ 786*f32f3638Srsc iput(dp); 787*f32f3638Srsc ilock(ip); 788*f32f3638Srsc if(ip->type == T_DIR){ 789*f32f3638Srsc iput(ip); 790*f32f3638Srsc return 0; 791*f32f3638Srsc } 792*f32f3638Srsc return ip; 793*f32f3638Srsc } 794*f32f3638Srsc if((ip = dircreat(dp, name, namelen, T_FILE, 0, 0)) == 0){ 795*f32f3638Srsc iput(dp); 796*f32f3638Srsc return 0; 797*f32f3638Srsc } 798*f32f3638Srsc iput(dp); 799*f32f3638Srsc return ip; 800*f32f3638Srsc } 801*f32f3638Srsc 802