111a9947fSrtm #include "types.h" 211a9947fSrtm #include "param.h" 311a9947fSrtm #include "x86.h" 411a9947fSrtm #include "mmu.h" 511a9947fSrtm #include "proc.h" 611a9947fSrtm #include "defs.h" 711a9947fSrtm #include "spinlock.h" 811a9947fSrtm #include "buf.h" 911a9947fSrtm #include "fs.h" 1011a9947fSrtm #include "fsvar.h" 116fa5ffb5Skaashoek #include "dev.h" 1211a9947fSrtm 1311a9947fSrtm // these are inodes currently in use 1411a9947fSrtm // an entry is free if count == 0 1511a9947fSrtm struct inode inode[NINODE]; 1632630628Srtm struct spinlock inode_table_lock = { "inode_table" }; 1711a9947fSrtm 189d3fb671Srtm uint rootdev = 1; 199d3fb671Srtm 2024111398Skaashoek static uint 2124111398Skaashoek balloc(uint dev) 2224111398Skaashoek { 2324111398Skaashoek int b; 2424111398Skaashoek struct buf *bp; 2524111398Skaashoek struct superblock *sb; 26*28d9ef04Skaashoek int bi = 0; 2724111398Skaashoek int size; 2824111398Skaashoek int ninodes; 2924111398Skaashoek uchar m; 3024111398Skaashoek 3124111398Skaashoek bp = bread(dev, 1); 3224111398Skaashoek sb = (struct superblock *) bp->data; 3324111398Skaashoek size = sb->size; 3424111398Skaashoek ninodes = sb->ninodes; 3524111398Skaashoek 3624111398Skaashoek for (b = 0; b < size; b++) { 3724111398Skaashoek if (b % BPB == 0) { 3824111398Skaashoek brelse(bp); 3924111398Skaashoek bp = bread(dev, BBLOCK(b, ninodes)); 4024111398Skaashoek } 4124111398Skaashoek bi = b % BPB; 4224111398Skaashoek m = 0x1 << (bi % 8); 4324111398Skaashoek if ((bp->data[bi/8] & m) == 0) { // is block free? 4424111398Skaashoek break; 4524111398Skaashoek } 4624111398Skaashoek } 4724111398Skaashoek if (b >= size) 4824111398Skaashoek panic("balloc: out of blocks\n"); 4924111398Skaashoek 5024111398Skaashoek cprintf ("balloc: allocate block %d\n", b); 5124111398Skaashoek bp->data[bi/8] |= 0x1 << (bi % 8); 5224111398Skaashoek bwrite (dev, bp, BBLOCK(b, ninodes)); // mark it allocated on disk 53*28d9ef04Skaashoek brelse(bp); 5424111398Skaashoek return b; 5524111398Skaashoek } 5624111398Skaashoek 57*28d9ef04Skaashoek static void 58*28d9ef04Skaashoek bfree(int dev, uint b) 59*28d9ef04Skaashoek { 60*28d9ef04Skaashoek struct buf *bp; 61*28d9ef04Skaashoek struct superblock *sb; 62*28d9ef04Skaashoek int bi; 63*28d9ef04Skaashoek int ninodes; 64*28d9ef04Skaashoek uchar m; 65*28d9ef04Skaashoek 66*28d9ef04Skaashoek cprintf ("bfree: free block %d\n", b); 67*28d9ef04Skaashoek bp = bread(dev, 1); 68*28d9ef04Skaashoek sb = (struct superblock *) bp->data; 69*28d9ef04Skaashoek ninodes = sb->ninodes; 70*28d9ef04Skaashoek brelse(bp); 71*28d9ef04Skaashoek 72*28d9ef04Skaashoek bp = bread(dev, BBLOCK(b, ninodes)); 73*28d9ef04Skaashoek bi = b % BPB; 74*28d9ef04Skaashoek m = ~(0x1 << (bi %8)); 75*28d9ef04Skaashoek bp->data[bi/8] &= m; 76*28d9ef04Skaashoek bwrite (dev, bp, BBLOCK(b, ninodes)); // mark it free on disk 77*28d9ef04Skaashoek brelse(bp); 78*28d9ef04Skaashoek } 7924111398Skaashoek 809d3fb671Srtm // returns an inode with busy set and incremented reference count. 8111a9947fSrtm struct inode * 8211a9947fSrtm iget(uint dev, uint inum) 8311a9947fSrtm { 8411a9947fSrtm struct inode *ip, *nip = 0; 8511a9947fSrtm struct dinode *dip; 8611a9947fSrtm struct buf *bp; 8711a9947fSrtm 8811a9947fSrtm acquire(&inode_table_lock); 8911a9947fSrtm 9011a9947fSrtm loop: 9111a9947fSrtm for(ip = &inode[0]; ip < &inode[NINODE]; ip++){ 9211a9947fSrtm if(ip->count > 0 && ip->dev == dev && ip->inum == inum){ 9311a9947fSrtm if(ip->busy){ 9411a9947fSrtm sleep(ip, &inode_table_lock); 9511a9947fSrtm goto loop; 9611a9947fSrtm } 9711a9947fSrtm ip->count++; 9811a9947fSrtm release(&inode_table_lock); 9911a9947fSrtm return ip; 10011a9947fSrtm } 10111a9947fSrtm if(nip == 0 && ip->count == 0) 10211a9947fSrtm nip = ip; 10311a9947fSrtm } 10411a9947fSrtm 10511a9947fSrtm if(nip == 0) 10611a9947fSrtm panic("out of inodes"); 10711a9947fSrtm 10811a9947fSrtm nip->dev = dev; 10911a9947fSrtm nip->inum = inum; 11011a9947fSrtm nip->count = 1; 11111a9947fSrtm nip->busy = 1; 11211a9947fSrtm 11311a9947fSrtm release(&inode_table_lock); 11411a9947fSrtm 11524111398Skaashoek bp = bread(dev, IBLOCK(inum)); 11611a9947fSrtm dip = &((struct dinode *)(bp->data))[inum % IPB]; 11711a9947fSrtm nip->type = dip->type; 118e8d11c2eSkaashoek nip->major = dip->major; 119e8d11c2eSkaashoek nip->minor = dip->minor; 12011a9947fSrtm nip->nlink = dip->nlink; 12111a9947fSrtm nip->size = dip->size; 12211a9947fSrtm memmove(nip->addrs, dip->addrs, sizeof(nip->addrs)); 12311a9947fSrtm brelse(bp); 12411a9947fSrtm 12511a9947fSrtm return nip; 12611a9947fSrtm } 12711a9947fSrtm 128*28d9ef04Skaashoek void 129*28d9ef04Skaashoek iupdate (struct inode *ip) 130*28d9ef04Skaashoek { 131*28d9ef04Skaashoek struct buf *bp; 132*28d9ef04Skaashoek struct dinode *dip; 133*28d9ef04Skaashoek 134*28d9ef04Skaashoek bp = bread(ip->dev, IBLOCK(ip->inum)); 135*28d9ef04Skaashoek dip = &((struct dinode *)(bp->data))[ip->inum % IPB]; 136*28d9ef04Skaashoek dip->type = ip->type; 137*28d9ef04Skaashoek dip->major = ip->major; 138*28d9ef04Skaashoek dip->minor = ip->minor; 139*28d9ef04Skaashoek dip->nlink = ip->nlink; 140*28d9ef04Skaashoek dip->size = ip->size; 141*28d9ef04Skaashoek memmove(dip->addrs, ip->addrs, sizeof(ip->addrs)); 142*28d9ef04Skaashoek bwrite (ip->dev, bp, IBLOCK(ip->inum)); // mark it allocated on the disk 143*28d9ef04Skaashoek brelse(bp); 144*28d9ef04Skaashoek } 145*28d9ef04Skaashoek 146e8d11c2eSkaashoek struct inode * 147e8d11c2eSkaashoek ialloc(uint dev, short type) 148e8d11c2eSkaashoek { 149e8d11c2eSkaashoek struct inode *ip; 150e8d11c2eSkaashoek struct dinode *dip = 0; 151e8d11c2eSkaashoek struct superblock *sb; 152e8d11c2eSkaashoek int ninodes; 153e8d11c2eSkaashoek int inum; 154e8d11c2eSkaashoek struct buf *bp; 155e8d11c2eSkaashoek 156e8d11c2eSkaashoek bp = bread(dev, 1); 15724111398Skaashoek sb = (struct superblock *) bp->data; 158e8d11c2eSkaashoek ninodes = sb->ninodes; 159e8d11c2eSkaashoek brelse(bp); 160e8d11c2eSkaashoek 161e8d11c2eSkaashoek for (inum = 1; inum < ninodes; inum++) { // loop over inode blocks 16224111398Skaashoek bp = bread(dev, IBLOCK(inum)); 163e8d11c2eSkaashoek dip = &((struct dinode *)(bp->data))[inum % IPB]; 164e8d11c2eSkaashoek if (dip->type == 0) { // a free inode 165e8d11c2eSkaashoek break; 166e8d11c2eSkaashoek } 167e8d11c2eSkaashoek brelse(bp); 168e8d11c2eSkaashoek } 169e8d11c2eSkaashoek 170e8d11c2eSkaashoek if (inum >= ninodes) { 17124111398Skaashoek panic ("ialloc: no inodes left\n"); 172e8d11c2eSkaashoek } 173e8d11c2eSkaashoek 174e8d11c2eSkaashoek cprintf ("ialloc: %d\n", inum); 175e8d11c2eSkaashoek dip->type = type; 17624111398Skaashoek bwrite (dev, bp, IBLOCK(inum)); // mark it allocated on the disk 177e8d11c2eSkaashoek brelse(bp); 178e8d11c2eSkaashoek ip = iget (dev, inum); 179e8d11c2eSkaashoek return ip; 180e8d11c2eSkaashoek } 181e8d11c2eSkaashoek 182*28d9ef04Skaashoek static void 183*28d9ef04Skaashoek ifree(uint dev, struct inode *ip) 184e8d11c2eSkaashoek { 185*28d9ef04Skaashoek ip->type = 0; 186*28d9ef04Skaashoek iupdate(ip); 187e8d11c2eSkaashoek } 188e8d11c2eSkaashoek 18911a9947fSrtm void 1909d3fb671Srtm ilock(struct inode *ip) 1919d3fb671Srtm { 1929d3fb671Srtm if(ip->count < 1) 1939d3fb671Srtm panic("ilock"); 1949d3fb671Srtm 1959d3fb671Srtm acquire(&inode_table_lock); 1969d3fb671Srtm 1979d3fb671Srtm while(ip->busy) 1989d3fb671Srtm sleep(ip, &inode_table_lock); 1999d3fb671Srtm ip->busy = 1; 2009d3fb671Srtm 2019d3fb671Srtm release(&inode_table_lock); 2029d3fb671Srtm } 2039d3fb671Srtm 2049d3fb671Srtm // caller is holding onto a reference to this inode, but no 2059d3fb671Srtm // longer needs to examine or change it, so clear ip->busy. 2069d3fb671Srtm void 2079d3fb671Srtm iunlock(struct inode *ip) 2089d3fb671Srtm { 2099d3fb671Srtm if(ip->busy != 1) 2109d3fb671Srtm panic("iunlock"); 2119d3fb671Srtm 2129d3fb671Srtm acquire(&inode_table_lock); 2139d3fb671Srtm 2149d3fb671Srtm ip->busy = 0; 2159d3fb671Srtm wakeup(ip); 2169d3fb671Srtm 2179d3fb671Srtm release(&inode_table_lock); 2189d3fb671Srtm } 2199d3fb671Srtm 2209d3fb671Srtm // caller is releasing a reference to this inode. 2219d3fb671Srtm // you must have the inode lock. 2229d3fb671Srtm void 22311a9947fSrtm iput(struct inode *ip) 22411a9947fSrtm { 2259d3fb671Srtm if(ip->count < 1 || ip->busy != 1) 2269d3fb671Srtm panic("iput"); 2279d3fb671Srtm 22811a9947fSrtm acquire(&inode_table_lock); 22911a9947fSrtm 23011a9947fSrtm ip->count -= 1; 23111a9947fSrtm ip->busy = 0; 23211a9947fSrtm wakeup(ip); 23311a9947fSrtm 23411a9947fSrtm release(&inode_table_lock); 23511a9947fSrtm } 2369d3fb671Srtm 2379d3fb671Srtm void 23832630628Srtm idecref(struct inode *ip) 2399d3fb671Srtm { 2409d3fb671Srtm acquire(&inode_table_lock); 2419d3fb671Srtm 24232630628Srtm if(ip->count < 1) 24332630628Srtm panic("idecref"); 24432630628Srtm 24532630628Srtm ip->count -= 1; 2469d3fb671Srtm 2479d3fb671Srtm release(&inode_table_lock); 2489d3fb671Srtm } 2499d3fb671Srtm 2509d3fb671Srtm uint 2519d3fb671Srtm bmap(struct inode *ip, uint bn) 2529d3fb671Srtm { 2539d3fb671Srtm unsigned x; 2549d3fb671Srtm 2559d3fb671Srtm if(bn >= NDIRECT) 2569d3fb671Srtm panic("bmap 1"); 2579d3fb671Srtm x = ip->addrs[bn]; 2589d3fb671Srtm if(x == 0) 2599d3fb671Srtm panic("bmap 2"); 2609d3fb671Srtm return x; 2619d3fb671Srtm } 2629d3fb671Srtm 263c59361f1Srtm #define min(a, b) ((a) < (b) ? (a) : (b)) 264c59361f1Srtm 265c59361f1Srtm int 266c59361f1Srtm readi(struct inode *ip, void *xdst, uint off, uint n) 267c59361f1Srtm { 268c59361f1Srtm char *dst = (char *) xdst; 269c59361f1Srtm uint target = n, n1; 270c59361f1Srtm struct buf *bp; 271c59361f1Srtm 272939f9edeSkaashoek if (ip->type == T_DEV) { 273939f9edeSkaashoek if (ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].d_read) 274939f9edeSkaashoek return -1; 275939f9edeSkaashoek return devsw[ip->major].d_read (ip->minor, xdst, n); 276939f9edeSkaashoek } 277939f9edeSkaashoek 278c59361f1Srtm while(n > 0 && off < ip->size){ 27924111398Skaashoek bp = bread(ip->dev, bmap(ip, off / BSIZE)); 280c59361f1Srtm n1 = min(n, ip->size - off); 28124111398Skaashoek n1 = min(n1, BSIZE - (off % BSIZE)); 28224111398Skaashoek memmove(dst, bp->data + (off % BSIZE), n1); 283c59361f1Srtm n -= n1; 284c59361f1Srtm off += n1; 285c59361f1Srtm dst += n1; 286c59361f1Srtm brelse(bp); 287c59361f1Srtm } 288c59361f1Srtm 289c59361f1Srtm return target - n; 290c59361f1Srtm } 291c59361f1Srtm 292*28d9ef04Skaashoek #define MIN(a, b) ((a < b) ? a : b) 293*28d9ef04Skaashoek 2946fa5ffb5Skaashoek int 295*28d9ef04Skaashoek writei(struct inode *ip, void *addr, uint off, uint n) 2966fa5ffb5Skaashoek { 2976fa5ffb5Skaashoek if (ip->type == T_DEV) { 298939f9edeSkaashoek if (ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].d_write) 299939f9edeSkaashoek return -1; 3006fa5ffb5Skaashoek return devsw[ip->major].d_write (ip->minor, addr, n); 301*28d9ef04Skaashoek } else if (ip->type == T_FILE || ip->type == T_DIR) { // XXX dir here too? 302*28d9ef04Skaashoek struct buf *bp; 303*28d9ef04Skaashoek int r = 0; 304*28d9ef04Skaashoek int m; 305*28d9ef04Skaashoek int lbn; 306*28d9ef04Skaashoek uint b; 307*28d9ef04Skaashoek while (r < n) { 308*28d9ef04Skaashoek lbn = off / BSIZE; 309*28d9ef04Skaashoek if (lbn >= NDIRECT) return r; 310*28d9ef04Skaashoek if (ip->addrs[lbn] == 0) { 311*28d9ef04Skaashoek b = balloc(ip->dev); 312*28d9ef04Skaashoek if (b <= 0) return r; 313*28d9ef04Skaashoek ip->addrs[lbn] = b; 314*28d9ef04Skaashoek } 315*28d9ef04Skaashoek m = MIN(BSIZE - off % BSIZE, n-r); 316*28d9ef04Skaashoek bp = bread(ip->dev, bmap(ip, off / BSIZE)); 317*28d9ef04Skaashoek memmove (bp->data + off % BSIZE, addr, m); 318*28d9ef04Skaashoek bwrite (ip->dev, bp, bmap(ip, off/BSIZE)); 319*28d9ef04Skaashoek brelse (bp); 320*28d9ef04Skaashoek r += m; 321*28d9ef04Skaashoek off += m; 322*28d9ef04Skaashoek } 323*28d9ef04Skaashoek if (r > 0) { 324*28d9ef04Skaashoek if (off > ip->size) { 325*28d9ef04Skaashoek ip->size = off; 326*28d9ef04Skaashoek } 327*28d9ef04Skaashoek iupdate(ip); 328*28d9ef04Skaashoek } 329*28d9ef04Skaashoek return r; 3306fa5ffb5Skaashoek } else { 3316fa5ffb5Skaashoek panic ("writei: unknown type\n"); 3326fa5ffb5Skaashoek } 3336fa5ffb5Skaashoek } 3346fa5ffb5Skaashoek 3359d3fb671Srtm struct inode * 3369d3fb671Srtm namei(char *path) 3379d3fb671Srtm { 3389d3fb671Srtm struct inode *dp; 3399d3fb671Srtm char *cp = path; 3409d3fb671Srtm uint off, dev; 3419d3fb671Srtm struct buf *bp; 3429d3fb671Srtm struct dirent *ep; 3439d3fb671Srtm int i; 3449d3fb671Srtm unsigned ninum; 3459d3fb671Srtm 3469d3fb671Srtm dp = iget(rootdev, 1); 3479d3fb671Srtm 3489d3fb671Srtm while(*cp == '/') 3499d3fb671Srtm cp++; 3509d3fb671Srtm 3519d3fb671Srtm while(1){ 3529d3fb671Srtm if(*cp == '\0') 3539d3fb671Srtm return dp; 3549d3fb671Srtm 3559d3fb671Srtm if(dp->type != T_DIR){ 3569d3fb671Srtm iput(dp); 3579d3fb671Srtm return 0; 3589d3fb671Srtm } 3599d3fb671Srtm 36024111398Skaashoek for(off = 0; off < dp->size; off += BSIZE){ 36124111398Skaashoek bp = bread(dp->dev, bmap(dp, off / BSIZE)); 3629d3fb671Srtm for(ep = (struct dirent *) bp->data; 36324111398Skaashoek ep < (struct dirent *) (bp->data + BSIZE); 3649d3fb671Srtm ep++){ 3659d3fb671Srtm if(ep->inum == 0) 3669d3fb671Srtm continue; 3679d3fb671Srtm for(i = 0; i < DIRSIZ && cp[i] != '/' && cp[i]; i++) 3689d3fb671Srtm if(cp[i] != ep->name[i]) 3699d3fb671Srtm break; 3709d3fb671Srtm if((cp[i] == '\0' || cp[i] == '/') && (i >= DIRSIZ || ep->name[i] == '\0')){ 3719d3fb671Srtm ninum = ep->inum; 3729d3fb671Srtm brelse(bp); 3739d3fb671Srtm cp += i; 3749d3fb671Srtm goto found; 3759d3fb671Srtm } 3769d3fb671Srtm } 3779d3fb671Srtm brelse(bp); 3789d3fb671Srtm } 3799d3fb671Srtm iput(dp); 3809d3fb671Srtm return 0; 3819d3fb671Srtm 3829d3fb671Srtm found: 3839d3fb671Srtm dev = dp->dev; 3849d3fb671Srtm iput(dp); 3859d3fb671Srtm dp = iget(dev, ninum); 3869d3fb671Srtm while(*cp == '/') 3879d3fb671Srtm cp++; 3889d3fb671Srtm } 3899d3fb671Srtm } 390e8d11c2eSkaashoek 391e8d11c2eSkaashoek struct inode * 392e8d11c2eSkaashoek mknod(struct inode *dp, char *cp, short type, short major, short minor) 393e8d11c2eSkaashoek { 394e8d11c2eSkaashoek struct inode *ip; 395e8d11c2eSkaashoek struct dirent *ep = 0; 396e8d11c2eSkaashoek int off; 397e8d11c2eSkaashoek int i; 398e8d11c2eSkaashoek struct buf *bp = 0; 399e8d11c2eSkaashoek 400e8d11c2eSkaashoek cprintf("mknod: %s %d %d %d\n", cp, type, major, minor); 401e8d11c2eSkaashoek 402e8d11c2eSkaashoek ip = ialloc(dp->dev, type); 403e8d11c2eSkaashoek if (ip == 0) return 0; 404e8d11c2eSkaashoek ip->major = major; 405e8d11c2eSkaashoek ip->minor = minor; 4066c0e444fSkaashoek ip->size = 0; 4076c0e444fSkaashoek ip->nlink = 0; 4086c0e444fSkaashoek 4096c0e444fSkaashoek iupdate (ip); // write new inode to disk 410e8d11c2eSkaashoek 41124111398Skaashoek for(off = 0; off < dp->size; off += BSIZE) { 41224111398Skaashoek bp = bread(dp->dev, bmap(dp, off / BSIZE)); 413e8d11c2eSkaashoek for(ep = (struct dirent *) bp->data; 41424111398Skaashoek ep < (struct dirent *) (bp->data + BSIZE); 415e8d11c2eSkaashoek ep++){ 416e8d11c2eSkaashoek if(ep->inum == 0) { 417e8d11c2eSkaashoek goto found; 418e8d11c2eSkaashoek } 419e8d11c2eSkaashoek } 420e8d11c2eSkaashoek brelse(bp); 421e8d11c2eSkaashoek } 422*28d9ef04Skaashoek panic("mknod: XXXX no dir entry free\n"); 423e8d11c2eSkaashoek 424e8d11c2eSkaashoek found: 425e8d11c2eSkaashoek ep->inum = ip->inum; 426e8d11c2eSkaashoek for(i = 0; i < DIRSIZ && cp[i]; i++) ep->name[i] = cp[i]; 4276c0e444fSkaashoek bwrite (dp->dev, bp, bmap(dp, off/BSIZE)); // write directory block 428e8d11c2eSkaashoek brelse(bp); 4296c0e444fSkaashoek 4306c0e444fSkaashoek dp->size += sizeof(struct dirent); // update directory inode 4316c0e444fSkaashoek iupdate (dp); 4326c0e444fSkaashoek 433e8d11c2eSkaashoek return ip; 434e8d11c2eSkaashoek } 435