1 #include "types.h" 2 #include "stat.h" 3 #include "param.h" 4 #include "x86.h" 5 #include "mmu.h" 6 #include "proc.h" 7 #include "defs.h" 8 #include "spinlock.h" 9 #include "buf.h" 10 #include "fs.h" 11 #include "fsvar.h" 12 #include "dev.h" 13 14 // these are inodes currently in use 15 // an entry is free if count == 0 16 struct inode inode[NINODE]; 17 struct spinlock inode_table_lock; 18 19 uint rootdev = 1; 20 21 void 22 iinit(void) 23 { 24 initlock(&inode_table_lock, "inode_table"); 25 } 26 27 static uint 28 balloc(uint dev) 29 { 30 int b; 31 struct buf *bp; 32 struct superblock *sb; 33 int bi = 0; 34 int size; 35 int ninodes; 36 uchar m; 37 38 bp = bread(dev, 1); 39 sb = (struct superblock *) bp->data; 40 size = sb->size; 41 ninodes = sb->ninodes; 42 43 for (b = 0; b < size; b++) { 44 if (b % BPB == 0) { 45 brelse(bp); 46 bp = bread(dev, BBLOCK(b, ninodes)); 47 } 48 bi = b % BPB; 49 m = 0x1 << (bi % 8); 50 if ((bp->data[bi/8] & m) == 0) { // is block free? 51 break; 52 } 53 } 54 if (b >= size) 55 panic("balloc: out of blocks\n"); 56 57 cprintf ("balloc: allocate block %d\n", b); 58 bp->data[bi/8] |= 0x1 << (bi % 8); 59 bwrite (bp, BBLOCK(b, ninodes)); // mark it allocated on disk 60 brelse(bp); 61 return b; 62 } 63 64 static void 65 bfree(int dev, uint b) 66 { 67 struct buf *bp; 68 struct superblock *sb; 69 int bi; 70 int ninodes; 71 uchar m; 72 73 cprintf ("bfree: free block %d\n", b); 74 bp = bread(dev, 1); 75 sb = (struct superblock *) bp->data; 76 ninodes = sb->ninodes; 77 brelse(bp); 78 79 bp = bread(dev, BBLOCK(b, ninodes)); 80 bi = b % BPB; 81 m = ~(0x1 << (bi %8)); 82 bp->data[bi/8] &= m; 83 bwrite (bp, BBLOCK(b, ninodes)); // mark it free on disk 84 brelse(bp); 85 } 86 87 // returns an inode with busy set and incremented reference count. 88 struct inode * 89 iget(uint dev, uint inum) 90 { 91 struct inode *ip, *nip = 0; 92 struct dinode *dip; 93 struct buf *bp; 94 95 acquire(&inode_table_lock); 96 97 loop: 98 for(ip = &inode[0]; ip < &inode[NINODE]; ip++){ 99 if(ip->count > 0 && ip->dev == dev && ip->inum == inum){ 100 if(ip->busy){ 101 sleep(ip, &inode_table_lock); 102 goto loop; 103 } 104 ip->count++; 105 ip->busy = 1; 106 release(&inode_table_lock); 107 return ip; 108 } 109 if(nip == 0 && ip->count == 0) 110 nip = ip; 111 } 112 113 if(nip == 0) 114 panic("out of inodes"); 115 116 nip->dev = dev; 117 nip->inum = inum; 118 nip->count = 1; 119 nip->busy = 1; 120 121 release(&inode_table_lock); 122 123 bp = bread(dev, IBLOCK(inum)); 124 dip = &((struct dinode *)(bp->data))[inum % IPB]; 125 nip->type = dip->type; 126 nip->major = dip->major; 127 nip->minor = dip->minor; 128 nip->nlink = dip->nlink; 129 nip->size = dip->size; 130 memmove(nip->addrs, dip->addrs, sizeof(nip->addrs)); 131 brelse(bp); 132 133 return nip; 134 } 135 136 void 137 iupdate (struct inode *ip) 138 { 139 struct buf *bp; 140 struct dinode *dip; 141 142 bp = bread(ip->dev, IBLOCK(ip->inum)); 143 dip = &((struct dinode *)(bp->data))[ip->inum % IPB]; 144 dip->type = ip->type; 145 dip->major = ip->major; 146 dip->minor = ip->minor; 147 dip->nlink = ip->nlink; 148 dip->size = ip->size; 149 memmove(dip->addrs, ip->addrs, sizeof(ip->addrs)); 150 bwrite (bp, IBLOCK(ip->inum)); // mark it allocated on the disk 151 brelse(bp); 152 } 153 154 struct inode * 155 ialloc(uint dev, short type) 156 { 157 struct inode *ip; 158 struct dinode *dip = 0; 159 struct superblock *sb; 160 int ninodes; 161 int inum; 162 struct buf *bp; 163 164 bp = bread(dev, 1); 165 sb = (struct superblock *) bp->data; 166 ninodes = sb->ninodes; 167 brelse(bp); 168 169 for (inum = 1; inum < ninodes; inum++) { // loop over inode blocks 170 bp = bread(dev, IBLOCK(inum)); 171 dip = &((struct dinode *)(bp->data))[inum % IPB]; 172 if (dip->type == 0) { // a free inode 173 break; 174 } 175 brelse(bp); 176 } 177 178 if (inum >= ninodes) { 179 panic ("ialloc: no inodes left\n"); 180 } 181 182 cprintf ("ialloc: %d\n", inum); 183 dip->type = type; 184 bwrite (bp, IBLOCK(inum)); // mark it allocated on the disk 185 brelse(bp); 186 ip = iget (dev, inum); 187 return ip; 188 } 189 190 static void 191 ifree(struct inode *ip) 192 { 193 cprintf("ifree: %d\n", ip->inum); 194 ip->type = 0; 195 iupdate(ip); 196 } 197 198 void 199 ilock(struct inode *ip) 200 { 201 if(ip->count < 1) 202 panic("ilock"); 203 204 acquire(&inode_table_lock); 205 206 while(ip->busy) 207 sleep(ip, &inode_table_lock); 208 ip->busy = 1; 209 210 release(&inode_table_lock); 211 } 212 213 // caller is holding onto a reference to this inode, but no 214 // longer needs to examine or change it, so clear ip->busy. 215 void 216 iunlock(struct inode *ip) 217 { 218 if(ip->busy != 1) 219 panic("iunlock"); 220 221 acquire(&inode_table_lock); 222 223 ip->busy = 0; 224 wakeup(ip); 225 226 release(&inode_table_lock); 227 } 228 229 uint 230 bmap(struct inode *ip, uint bn) 231 { 232 unsigned x; 233 234 if(bn >= NDIRECT) 235 panic("bmap 1"); 236 x = ip->addrs[bn]; 237 if(x == 0) 238 panic("bmap 2"); 239 return x; 240 } 241 242 void 243 iunlink(struct inode *ip) 244 { 245 int i; 246 247 // free inode, its blocks, and remove dir entry 248 for (i = 0; i < NDIRECT; i++) { 249 if (ip->addrs[i] != 0) { 250 bfree(ip->dev, ip->addrs[i]); 251 ip->addrs[i] = 0; 252 } 253 } 254 ip->size = 0; 255 ip->major = 0; 256 ip->minor = 0; 257 iupdate(ip); 258 ifree(ip); // is this the right order? 259 } 260 261 // caller is releasing a reference to this inode. 262 // you must have the inode lock. 263 void 264 iput(struct inode *ip) 265 { 266 if(ip->count < 1 || ip->busy != 1) 267 panic("iput"); 268 269 if ((ip->count <= 1) && (ip->nlink <= 0)) 270 iunlink(ip); 271 272 acquire(&inode_table_lock); 273 274 ip->count -= 1; 275 ip->busy = 0; 276 wakeup(ip); 277 278 release(&inode_table_lock); 279 } 280 281 void 282 idecref(struct inode *ip) 283 { 284 acquire(&inode_table_lock); 285 286 if(ip->count < 1) 287 panic("idecref"); 288 289 ip->count -= 1; 290 291 release(&inode_table_lock); 292 } 293 294 void 295 stati(struct inode *ip, struct stat *st) 296 { 297 st->st_dev = ip->dev; 298 st->st_ino = ip->inum; 299 st->st_type = ip->type; 300 st->st_nlink = ip->nlink; 301 st->st_size = ip->size; 302 } 303 304 #define min(a, b) ((a) < (b) ? (a) : (b)) 305 306 int 307 readi(struct inode *ip, char *dst, uint off, uint n) 308 { 309 uint target = n, n1; 310 struct buf *bp; 311 312 if (ip->type == T_DEV) { 313 if (ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].d_read) 314 return -1; 315 return devsw[ip->major].d_read (ip->minor, dst, n); 316 } 317 318 while(n > 0 && off < ip->size){ 319 bp = bread(ip->dev, bmap(ip, off / BSIZE)); 320 n1 = min(n, ip->size - off); 321 n1 = min(n1, BSIZE - (off % BSIZE)); 322 memmove(dst, bp->data + (off % BSIZE), n1); 323 n -= n1; 324 off += n1; 325 dst += n1; 326 brelse(bp); 327 } 328 329 return target - n; 330 } 331 332 int 333 writei(struct inode *ip, char *addr, uint off, uint n) 334 { 335 if (ip->type == T_DEV) { 336 if (ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].d_write) 337 return -1; 338 return devsw[ip->major].d_write (ip->minor, addr, n); 339 } else if (ip->type == T_FILE || ip->type == T_DIR) { // XXX dir here too? 340 struct buf *bp; 341 int r = 0; 342 int m; 343 int lbn; 344 uint b; 345 while (r < n) { 346 lbn = off / BSIZE; 347 if (lbn >= NDIRECT) return r; 348 if (ip->addrs[lbn] == 0) { 349 b = balloc(ip->dev); 350 if (b <= 0) return r; 351 ip->addrs[lbn] = b; 352 } 353 m = min(BSIZE - off % BSIZE, n-r); 354 bp = bread(ip->dev, bmap(ip, off / BSIZE)); 355 memmove (bp->data + off % BSIZE, addr, m); 356 bwrite (bp, bmap(ip, off/BSIZE)); 357 brelse (bp); 358 r += m; 359 off += m; 360 } 361 if (r > 0) { 362 if (off > ip->size) { 363 ip->size = off; 364 } 365 iupdate(ip); 366 } 367 return r; 368 } else { 369 panic ("writei: unknown type\n"); 370 return 0; 371 } 372 } 373 374 struct inode * 375 namei(char *path, uint *ret_pinum) 376 { 377 struct inode *dp; 378 char *cp = path; 379 uint off, dev; 380 struct buf *bp; 381 struct dirent *ep; 382 int i; 383 unsigned ninum; 384 unsigned pinum; 385 386 dp = iget(rootdev, 1); 387 pinum = dp->inum; 388 389 while(*cp == '/') 390 cp++; 391 392 while(1){ 393 if(*cp == '\0') { 394 if (ret_pinum) 395 *ret_pinum = pinum; 396 return dp; 397 } 398 399 if(dp->type != T_DIR){ 400 if (ret_pinum) 401 *ret_pinum = pinum; 402 iput(dp); 403 return 0; 404 } 405 406 for(off = 0; off < dp->size; off += BSIZE){ 407 bp = bread(dp->dev, bmap(dp, off / BSIZE)); 408 for(ep = (struct dirent *) bp->data; 409 ep < (struct dirent *) (bp->data + BSIZE); 410 ep++){ 411 if(ep->inum == 0) 412 continue; 413 for(i = 0; i < DIRSIZ && cp[i] != '/' && cp[i]; i++) 414 if(cp[i] != ep->name[i]) 415 break; 416 if((cp[i] == '\0' || cp[i] == '/') && (i >= DIRSIZ || ep->name[i] == '\0')){ 417 ninum = ep->inum; 418 brelse(bp); 419 cp += i; 420 goto found; 421 } 422 } 423 brelse(bp); 424 } 425 iput(dp); 426 if (ret_pinum) 427 *ret_pinum = pinum; 428 return 0; 429 430 found: 431 dev = dp->dev; 432 pinum = dp->inum; 433 iput(dp); 434 dp = iget(dev, ninum); 435 if(dp->type == 0 || dp->nlink < 1) 436 panic("namei"); 437 while(*cp == '/') 438 cp++; 439 } 440 } 441 442 struct inode * 443 mknod(char *cp, short type, short major, short minor) 444 { 445 struct inode *ip, *dp; 446 struct dirent *ep = 0; 447 int off; 448 int i; 449 struct buf *bp = 0; 450 uint pinum = 0; 451 452 cprintf("mknod: %s %d %d %d\n", cp, type, major, minor); 453 454 if ((ip = namei(cp, &pinum)) != 0) { 455 iput(ip); 456 return 0; 457 } 458 cprintf("mknod: pinum = %d\n", pinum); 459 dp = iget(rootdev, pinum); 460 ip = ialloc(dp->dev, type); 461 if (ip == 0) { 462 iput(dp); 463 return 0; 464 } 465 ip->major = major; 466 ip->minor = minor; 467 ip->size = 0; 468 ip->nlink = 1; 469 470 iupdate (ip); // write new inode to disk 471 472 for(off = 0; off < dp->size; off += BSIZE) { 473 bp = bread(dp->dev, bmap(dp, off / BSIZE)); 474 for(ep = (struct dirent *) bp->data; 475 ep < (struct dirent *) (bp->data + BSIZE); 476 ep++){ 477 if(ep->inum == 0) { 478 goto found; 479 } 480 } 481 brelse(bp); 482 } 483 panic("mknod: XXXX no dir entry free\n"); 484 485 found: 486 ep->inum = ip->inum; 487 for(i = 0; i < DIRSIZ && cp[i]; i++) 488 ep->name[i] = cp[i]; 489 for( ; i < DIRSIZ; i++) 490 ep->name[i] = '\0'; 491 bwrite (bp, bmap(dp, off/BSIZE)); // write directory block 492 brelse(bp); 493 494 iput(dp); 495 496 return ip; 497 } 498 499 int 500 unlink(char *cp) 501 { 502 struct inode *ip; 503 struct inode *dp; 504 struct dirent *ep = 0; 505 int off; 506 struct buf *bp = 0; 507 uint pinum; 508 509 510 if ((ip = namei(cp, &pinum)) == 0) { 511 cprintf("unlink(%s) it doesn't exist\n", cp); 512 return -1; 513 } 514 515 ip->nlink--; 516 if (ip->nlink > 0) { 517 iput(ip); 518 return 0; 519 } 520 521 dp = iget(rootdev, pinum); 522 for(off = 0; off < dp->size; off += BSIZE) { 523 bp = bread(dp->dev, bmap(dp, off / BSIZE)); 524 for(ep = (struct dirent *) bp->data; 525 ep < (struct dirent *) (bp->data + BSIZE); 526 ep++){ 527 if(ep->inum == ip->inum) { 528 goto found; 529 } 530 } 531 brelse(bp); 532 } 533 panic("mknod: XXXX no dir entry free\n"); 534 535 found: 536 ep->inum = 0; 537 bwrite (bp, bmap(dp, off/BSIZE)); // write directory block 538 brelse(bp); 539 iupdate (dp); 540 iput(dp); 541 iput(ip); 542 return 0; 543 } 544