xref: /xv6-public/fs.c (revision db8fb62e) 
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 // Allocate a disk block.
28 static uint
29 balloc(uint dev)
30 {
31   int b;
32   struct buf *bp;
33   struct superblock *sb;
34   int bi = 0;
35   int size;
36   int ninodes;
37   uchar m;
38 
39   bp = bread(dev, 1);
40   sb = (struct superblock*) bp->data;
41   size = sb->size;
42   ninodes = sb->ninodes;
43 
44   for(b = 0; b < size; b++) {
45     if(b % BPB == 0) {
46       brelse(bp);
47       bp = bread(dev, BBLOCK(b, ninodes));
48     }
49     bi = b % BPB;
50     m = 0x1 << (bi % 8);
51     if((bp->data[bi/8] & m) == 0) {  // is block free?
52       break;
53     }
54   }
55   if(b >= size)
56     panic("balloc: out of blocks");
57 
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   bp = bread(dev, 1);
74   sb = (struct superblock*) bp->data;
75   ninodes = sb->ninodes;
76   brelse(bp);
77 
78   bp = bread(dev, b);
79   memset(bp->data, 0, BSIZE);
80   bwrite(bp, b);
81   brelse(bp);
82 
83   bp = bread(dev, BBLOCK(b, ninodes));
84   bi = b % BPB;
85   m = ~(0x1 << (bi %8));
86   bp->data[bi/8] &= m;
87   bwrite(bp, BBLOCK(b, ninodes));  // mark it free on disk
88   brelse(bp);
89 }
90 
91 // Find the inode with number inum on device dev
92 // and return an in-memory copy.  Loads the inode
93 // from disk into the in-core table if necessary.
94 // The returned inode has busy set and has its ref count incremented.
95 // Caller must iput the return value when done with it.
96 struct inode*
97 iget(uint dev, uint inum)
98 {
99   struct inode *ip, *nip;
100   struct dinode *dip;
101   struct buf *bp;
102 
103   acquire(&inode_table_lock);
104 
105  loop:
106   nip = 0;
107   for(ip = &inode[0]; ip < &inode[NINODE]; ip++){
108     if(ip->count > 0 && ip->dev == dev && ip->inum == inum){
109       if(ip->busy){
110         sleep(ip, &inode_table_lock);
111         goto loop;
112       }
113       ip->count++;
114       ip->busy = 1;
115       release(&inode_table_lock);
116       return ip;
117     }
118     if(nip == 0 && ip->count == 0)
119       nip = ip;
120   }
121 
122   if(nip == 0)
123     panic("out of inodes");
124 
125   nip->dev = dev;
126   nip->inum = inum;
127   nip->count = 1;
128   nip->busy = 1;
129 
130   release(&inode_table_lock);
131 
132   bp = bread(dev, IBLOCK(inum));
133   dip = &((struct dinode*)(bp->data))[inum % IPB];
134   nip->type = dip->type;
135   nip->major = dip->major;
136   nip->minor = dip->minor;
137   nip->nlink = dip->nlink;
138   nip->size = dip->size;
139   memmove(nip->addrs, dip->addrs, sizeof(nip->addrs));
140   brelse(bp);
141 
142   return nip;
143 }
144 
145 void
146 iupdate(struct inode *ip)
147 {
148   struct buf *bp;
149   struct dinode *dip;
150 
151   bp = bread(ip->dev, IBLOCK(ip->inum));
152   dip = &((struct dinode*)(bp->data))[ip->inum % IPB];
153   dip->type = ip->type;
154   dip->major = ip->major;
155   dip->minor = ip->minor;
156   dip->nlink = ip->nlink;
157   dip->size = ip->size;
158   memmove(dip->addrs, ip->addrs, sizeof(ip->addrs));
159   bwrite(bp, IBLOCK(ip->inum));   // mark it allocated on the disk
160   brelse(bp);
161 }
162 
163 struct inode*
164 ialloc(uint dev, short type)
165 {
166   struct inode *ip;
167   struct dinode *dip = 0;
168   struct superblock *sb;
169   int ninodes;
170   int inum;
171   struct buf *bp;
172 
173   bp = bread(dev, 1);
174   sb = (struct superblock*) bp->data;
175   ninodes = sb->ninodes;
176   brelse(bp);
177 
178   for(inum = 1; inum < ninodes; inum++) {  // loop over inode blocks
179     bp = bread(dev, IBLOCK(inum));
180     dip = &((struct dinode*)(bp->data))[inum % IPB];
181     if(dip->type == 0) {  // a free inode
182       break;
183     }
184     brelse(bp);
185   }
186 
187   if(inum >= ninodes)
188     panic("ialloc: no inodes left");
189 
190   memset(dip, 0, sizeof(*dip));
191   dip->type = type;
192   bwrite(bp, IBLOCK(inum));   // mark it allocated on the disk
193   brelse(bp);
194   ip = iget(dev, inum);
195   return ip;
196 }
197 
198 static void
199 ifree(struct inode *ip)
200 {
201   ip->type = 0;
202   iupdate(ip);
203 }
204 
205 void
206 ilock(struct inode *ip)
207 {
208   if(ip->count < 1)
209     panic("ilock");
210 
211   acquire(&inode_table_lock);
212 
213   while(ip->busy)
214     sleep(ip, &inode_table_lock);
215   ip->busy = 1;
216 
217   release(&inode_table_lock);
218 }
219 
220 // caller is holding onto a reference to this inode, but no
221 // longer needs to examine or change it, so clear ip->busy.
222 void
223 iunlock(struct inode *ip)
224 {
225   if(ip->busy != 1 || ip->count < 1)
226     panic("iunlock");
227 
228   acquire(&inode_table_lock);
229 
230   ip->busy = 0;
231   wakeup(ip);
232 
233   release(&inode_table_lock);
234 }
235 
236 uint
237 bmap(struct inode *ip, uint bn)
238 {
239   unsigned x;
240   uint *a;
241   struct buf *inbp;
242 
243   if(bn >= MAXFILE)
244     panic("bmap 1");
245   if(bn < NDIRECT) {
246     x = ip->addrs[bn];
247     if(x == 0)
248       panic("bmap 2");
249   } else {
250     if(ip->addrs[INDIRECT] == 0)
251       panic("bmap 3");
252     inbp = bread(ip->dev, ip->addrs[INDIRECT]);
253     a = (uint*) inbp->data;
254     x = a[bn - NDIRECT];
255     brelse(inbp);
256     if(x == 0)
257       panic("bmap 4");
258   }
259   return x;
260 }
261 
262 void
263 itrunc(struct inode *ip)
264 {
265   int i, j;
266   struct buf *inbp;
267 
268   for(i = 0; i < NADDRS; i++) {
269     if(ip->addrs[i] != 0) {
270       if(i == INDIRECT) {
271         inbp = bread(ip->dev, ip->addrs[INDIRECT]);
272         uint *a = (uint*) inbp->data;
273         for(j = 0; j < NINDIRECT; j++) {
274           if(a[j] != 0) {
275             bfree(ip->dev, a[j]);
276             a[j] = 0;
277           }
278         }
279         brelse(inbp);
280       }
281       bfree(ip->dev, ip->addrs[i]);
282       ip->addrs[i] = 0;
283     }
284   }
285   ip->size = 0;
286   iupdate(ip);
287 }
288 
289 // caller is releasing a reference to this inode.
290 // you must have the inode lock.
291 void
292 iput(struct inode *ip)
293 {
294   if(ip->count < 1 || ip->busy != 1)
295     panic("iput");
296 
297   if((ip->count == 1) && (ip->nlink == 0)) {
298     itrunc(ip);
299     ifree(ip);
300   }
301 
302   acquire(&inode_table_lock);
303 
304   ip->count -= 1;
305   ip->busy = 0;
306   wakeup(ip);
307 
308   release(&inode_table_lock);
309 }
310 
311 void
312 idecref(struct inode *ip)
313 {
314   ilock(ip);
315   iput(ip);
316 }
317 
318 void
319 iincref(struct inode *ip)
320 {
321   ilock(ip);
322   ip->count++;
323   iunlock(ip);
324 }
325 
326 void
327 stati(struct inode *ip, struct stat *st)
328 {
329   st->st_dev = ip->dev;
330   st->st_ino = ip->inum;
331   st->st_type = ip->type;
332   st->st_nlink = ip->nlink;
333   st->st_size = ip->size;
334 }
335 
336 #define min(a, b) ((a) < (b) ? (a) : (b))
337 
338 int
339 readi(struct inode *ip, char *dst, uint off, uint n)
340 {
341   uint target = n, n1;
342   struct buf *bp;
343 
344   if(ip->type == T_DEV) {
345     if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].d_read)
346       return -1;
347     return devsw[ip->major].d_read(ip->minor, dst, n);
348   }
349 
350   while(n > 0 && off < ip->size){
351     bp = bread(ip->dev, bmap(ip, off / BSIZE));
352     n1 = min(n, ip->size - off);
353     n1 = min(n1, BSIZE - (off % BSIZE));
354     memmove(dst, bp->data + (off % BSIZE), n1);
355     n -= n1;
356     off += n1;
357     dst += n1;
358     brelse(bp);
359   }
360 
361   return target - n;
362 }
363 
364 static int
365 newblock(struct inode *ip, uint lbn)
366 {
367   struct buf *inbp;
368   uint *inaddrs;
369   uint b;
370 
371   if(lbn < NDIRECT) {
372     if(ip->addrs[lbn] == 0) {
373       b = balloc(ip->dev);
374       if(b <= 0)
375         return -1;
376       ip->addrs[lbn] = b;
377     }
378   } else {
379     if(ip->addrs[INDIRECT] == 0) {
380       b = balloc(ip->dev);
381       if(b <= 0)
382         return -1;
383       ip->addrs[INDIRECT] = b;
384     }
385     inbp = bread(ip->dev, ip->addrs[INDIRECT]);
386     inaddrs = (uint*) inbp->data;
387     if(inaddrs[lbn - NDIRECT] == 0) {
388       b = balloc(ip->dev);
389       if(b <= 0)
390         return -1;
391       inaddrs[lbn - NDIRECT] = b;
392       bwrite(inbp, ip->addrs[INDIRECT]);
393     }
394     brelse(inbp);
395   }
396   return 0;
397 }
398 
399 int
400 writei(struct inode *ip, char *addr, uint off, uint n)
401 {
402   if(ip->type == T_DEV) {
403     if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].d_write)
404       return -1;
405     return devsw[ip->major].d_write(ip->minor, addr, n);
406   } else if(ip->type == T_FILE || ip->type == T_DIR) {
407     struct buf *bp;
408     int r = 0;
409     int m;
410     int lbn;
411     while(r < n) {
412       lbn = off / BSIZE;
413       if(lbn >= MAXFILE)
414         return r;
415       if(newblock(ip, lbn) < 0) {
416         cprintf("newblock failed\n");
417         return r;
418       }
419       m = min(BSIZE - off % BSIZE, n-r);
420       bp = bread(ip->dev, bmap(ip, lbn));
421       memmove(bp->data + off % BSIZE, addr, m);
422       bwrite(bp, bmap(ip, lbn));
423       brelse(bp);
424       r += m;
425       off += m;
426     }
427     if(r > 0) {
428       if(off > ip->size) {
429         if(ip->type == T_DIR)
430           ip->size = ((off / BSIZE) + 1) * BSIZE;
431         else
432           ip->size = off;
433       }
434       iupdate(ip);
435     }
436     return r;
437   } else {
438     panic("writei: unknown type");
439     return 0;
440   }
441 }
442 
443 // look up a path name, in one of three modes.
444 // NAMEI_LOOKUP: return locked target inode.
445 // NAMEI_CREATE: return locked parent inode.
446 //   return 0 if name does exist.
447 //   *ret_last points to last path component (i.e. new file name).
448 //   *ret_ip points to the the name that did exist, if it did.
449 //   *ret_ip and *ret_last may be zero even if return value is zero.
450 // NAMEI_DELETE: return locked parent inode, offset of dirent in *ret_off.
451 //   return 0 if name doesn't exist.
452 struct inode*
453 namei(char *path, int mode, uint *ret_off, char **ret_last, struct inode **ret_ip)
454 {
455   struct inode *dp;
456   struct proc *p = curproc[cpu()];
457   char *cp = path, *cp1;
458   uint off, dev;
459   struct buf *bp;
460   struct dirent *ep;
461   int i, atend;
462   unsigned ninum;
463 
464   if(ret_off)
465     *ret_off = 0xffffffff;
466   if(ret_last)
467     *ret_last = 0;
468   if(ret_ip)
469     *ret_ip = 0;
470 
471   if(*cp == '/')
472     dp = iget(rootdev, 1);
473   else {
474     dp = p->cwd;
475     iincref(dp);
476     ilock(dp);
477   }
478 
479   while(*cp == '/')
480     cp++;
481 
482   for(;;){
483     if(*cp == '\0'){
484       if(mode == NAMEI_LOOKUP)
485         return dp;
486       if(mode == NAMEI_CREATE && ret_ip){
487         *ret_ip = dp;
488         return 0;
489       }
490       iput(dp);
491       return 0;
492     }
493 
494     if(dp->type != T_DIR){
495       iput(dp);
496       return 0;
497     }
498 
499     for(off = 0; off < dp->size; off += BSIZE){
500       bp = bread(dp->dev, bmap(dp, off / BSIZE));
501       for(ep = (struct dirent*) bp->data;
502           ep < (struct dirent*) (bp->data + BSIZE);
503           ep++){
504         if(ep->inum == 0)
505           continue;
506         for(i = 0; i < DIRSIZ && cp[i] != '/' && cp[i]; i++)
507           if(cp[i] != ep->name[i])
508             break;
509         if((cp[i] == '\0' || cp[i] == '/' || i >= DIRSIZ) &&
510            (i >= DIRSIZ || ep->name[i] == '\0')){
511           while(cp[i] != '\0' && cp[i] != '/')
512             i++;
513           off += (uchar*)ep - bp->data;
514           ninum = ep->inum;
515           brelse(bp);
516           cp += i;
517           goto found;
518         }
519       }
520       brelse(bp);
521     }
522     atend = 1;
523     for(cp1 = cp; *cp1; cp1++)
524       if(*cp1 == '/')
525         atend = 0;
526     if(mode == NAMEI_CREATE && atend){
527       if(*cp == '\0'){
528         iput(dp);
529         return 0;
530       }
531       *ret_last = cp;
532       return dp;
533     }
534 
535     iput(dp);
536     return 0;
537 
538   found:
539     if(mode == NAMEI_DELETE && *cp == '\0'){
540       *ret_off = off;
541       return dp;
542     }
543     dev = dp->dev;
544     iput(dp);
545     dp = iget(dev, ninum);
546     if(dp->type == 0 || dp->nlink < 1)
547       panic("namei");
548     while(*cp == '/')
549       cp++;
550   }
551 }
552 
553 void
554 wdir(struct inode *dp, char *name, uint ino)
555 {
556   uint off;
557   struct dirent de;
558   int i;
559 
560   for(off = 0; off < dp->size; off += sizeof(de)){
561     if(readi(dp, (char*) &de, off, sizeof(de)) != sizeof(de))
562       panic("wdir read");
563     if(de.inum == 0)
564       break;
565   }
566 
567   de.inum = ino;
568   for(i = 0; i < DIRSIZ && name[i]; i++)
569     de.name[i] = name[i];
570   for( ; i < DIRSIZ; i++)
571     de.name[i] = '\0';
572 
573   if(writei(dp, (char*) &de, off, sizeof(de)) != sizeof(de))
574     panic("wdir write");
575 }
576 
577 struct inode*
578 mknod(char *cp, short type, short major, short minor)
579 {
580   struct inode *ip, *dp;
581   char *last;
582 
583   if((dp = namei(cp, NAMEI_CREATE, 0, &last, 0)) == 0)
584     return 0;
585 
586   ip = mknod1(dp, last, type, major, minor);
587 
588   iput(dp);
589 
590   return ip;
591 }
592 
593 struct inode*
594 mknod1(struct inode *dp, char *name, short type, short major, short minor)
595 {
596   struct inode *ip;
597 
598   ip = ialloc(dp->dev, type);
599   if(ip == 0)
600     return 0;
601   ip->major = major;
602   ip->minor = minor;
603   ip->size = 0;
604   ip->nlink = 1;
605 
606   iupdate(ip);  // write new inode to disk
607 
608   wdir(dp, name, ip->inum);
609 
610   return ip;
611 }
612 
613 int
614 unlink(char *cp)
615 {
616   struct inode *ip, *dp;
617   struct dirent de;
618   uint off, inum, dev;
619 
620   dp = namei(cp, NAMEI_DELETE, &off, 0, 0);
621   if(dp == 0)
622     return -1;
623 
624   dev = dp->dev;
625 
626   if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de) || de.inum == 0)
627     panic("unlink no entry");
628 
629   inum = de.inum;
630 
631   memset(&de, 0, sizeof(de));
632   if(writei(dp, (char*)&de, off, sizeof(de)) != sizeof(de))
633     panic("unlink dir write");
634 
635   iupdate(dp);
636   iput(dp);
637 
638   ip = iget(dev, inum);
639 
640   if(ip->nlink < 1)
641     panic("unlink nlink < 1");
642 
643   ip->nlink--;
644 
645   iupdate(ip);
646   iput(ip);
647 
648   return 0;
649 }
650 
651 int
652 link(char *name1, char *name2)
653 {
654   struct inode *ip, *dp;
655   char *last;
656 
657   if((ip = namei(name1, NAMEI_LOOKUP, 0, 0, 0)) == 0)
658     return -1;
659   if(ip->type == T_DIR){
660     iput(ip);
661     return -1;
662   }
663 
664   iunlock(ip);
665 
666   if((dp = namei(name2, NAMEI_CREATE, 0, &last, 0)) == 0) {
667     idecref(ip);
668     return -1;
669   }
670   if(dp->dev != ip->dev){
671     idecref(ip);
672     iput(dp);
673     return -1;
674   }
675 
676   ilock(ip);
677   ip->nlink += 1;
678   iupdate(ip);
679 
680   wdir(dp, last, ip->inum);
681   iput(dp);
682   iput(ip);
683 
684   return 0;
685 }
686