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