xref: /xv6-public/fs.c (revision f5527388) 
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) return -1;
375       ip->addrs[lbn] = b;
376     }
377   } else {
378     if(ip->addrs[INDIRECT] == 0) {
379       b = balloc(ip->dev);
380       if(b <= 0) return -1;
381       ip->addrs[INDIRECT] = b;
382     }
383     inbp = bread(ip->dev, ip->addrs[INDIRECT]);
384     inaddrs = (uint*) inbp->data;
385     if(inaddrs[lbn - NDIRECT] == 0) {
386       b = balloc(ip->dev);
387       if(b <= 0) return -1;
388       inaddrs[lbn - NDIRECT] = b;
389       bwrite(inbp, ip->addrs[INDIRECT]);
390     }
391     brelse(inbp);
392   }
393   return 0;
394 }
395 
396 int
397 writei(struct inode *ip, char *addr, uint off, uint n)
398 {
399   if(ip->type == T_DEV) {
400     if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].d_write)
401       return -1;
402     return devsw[ip->major].d_write(ip->minor, addr, n);
403   } else if(ip->type == T_FILE || ip->type == T_DIR) {
404     struct buf *bp;
405     int r = 0;
406     int m;
407     int lbn;
408     while(r < n) {
409       lbn = off / BSIZE;
410       if(lbn >= MAXFILE) return r;
411       if(newblock(ip, lbn) < 0) {
412         cprintf("newblock failed\n");
413         return r;
414       }
415       m = min(BSIZE - off % BSIZE, n-r);
416       bp = bread(ip->dev, bmap(ip, lbn));
417       memmove(bp->data + off % BSIZE, addr, m);
418       bwrite(bp, bmap(ip, lbn));
419       brelse(bp);
420       r += m;
421       off += m;
422     }
423     if(r > 0) {
424       if(off > ip->size) {
425         if(ip->type == T_DIR) ip->size = ((off / BSIZE) + 1) * BSIZE;
426         else ip->size = off;
427       }
428       iupdate(ip);
429     }
430     return r;
431   } else {
432     panic("writei: unknown type");
433     return 0;
434   }
435 }
436 
437 // look up a path name, in one of three modes.
438 // NAMEI_LOOKUP: return locked target inode.
439 // NAMEI_CREATE: return locked parent inode.
440 //   return 0 if name does exist.
441 //   *ret_last points to last path component (i.e. new file name).
442 //   *ret_ip points to the the name that did exist, if it did.
443 //   *ret_ip and *ret_last may be zero even if return value is zero.
444 // NAMEI_DELETE: return locked parent inode, offset of dirent in *ret_off.
445 //   return 0 if name doesn't exist.
446 struct inode*
447 namei(char *path, int mode, uint *ret_off, char **ret_last, struct inode **ret_ip)
448 {
449   struct inode *dp;
450   struct proc *p = curproc[cpu()];
451   char *cp = path, *cp1;
452   uint off, dev;
453   struct buf *bp;
454   struct dirent *ep;
455   int i, atend;
456   unsigned ninum;
457 
458   if(ret_off)
459     *ret_off = 0xffffffff;
460   if(ret_last)
461     *ret_last = 0;
462   if(ret_ip)
463     *ret_ip = 0;
464 
465   if(*cp == '/') dp = iget(rootdev, 1);
466   else {
467     dp = p->cwd;
468     iincref(dp);
469     ilock(dp);
470   }
471 
472   while(*cp == '/')
473     cp++;
474 
475   while(1){
476     if(*cp == '\0'){
477       if(mode == NAMEI_LOOKUP)
478         return dp;
479       if(mode == NAMEI_CREATE && ret_ip){
480         *ret_ip = dp;
481         return 0;
482       }
483       iput(dp);
484       return 0;
485     }
486 
487     if(dp->type != T_DIR){
488       iput(dp);
489       return 0;
490     }
491 
492     for(off = 0; off < dp->size; off += BSIZE){
493       bp = bread(dp->dev, bmap(dp, off / BSIZE));
494       for(ep = (struct dirent*) bp->data;
495           ep < (struct dirent*) (bp->data + BSIZE);
496           ep++){
497         if(ep->inum == 0)
498           continue;
499         for(i = 0; i < DIRSIZ && cp[i] != '/' && cp[i]; i++)
500           if(cp[i] != ep->name[i])
501             break;
502         if((cp[i] == '\0' || cp[i] == '/' || i >= DIRSIZ) &&
503            (i >= DIRSIZ || ep->name[i] == '\0')){
504           while(cp[i] != '\0' && cp[i] != '/')
505             i++;
506           off += (uchar*)ep - bp->data;
507           ninum = ep->inum;
508           brelse(bp);
509           cp += i;
510           goto found;
511         }
512       }
513       brelse(bp);
514     }
515     atend = 1;
516     for(cp1 = cp; *cp1; cp1++)
517       if(*cp1 == '/')
518         atend = 0;
519     if(mode == NAMEI_CREATE && atend){
520       if(*cp == '\0'){
521         iput(dp);
522         return 0;
523       }
524       *ret_last = cp;
525       return dp;
526     }
527 
528     iput(dp);
529     return 0;
530 
531   found:
532     if(mode == NAMEI_DELETE && *cp == '\0'){
533       *ret_off = off;
534       return dp;
535     }
536     dev = dp->dev;
537     iput(dp);
538     dp = iget(dev, ninum);
539     if(dp->type == 0 || dp->nlink < 1)
540       panic("namei");
541     while(*cp == '/')
542       cp++;
543   }
544 }
545 
546 void
547 wdir(struct inode *dp, char *name, uint ino)
548 {
549   uint off;
550   struct dirent de;
551   int i;
552 
553   for(off = 0; off < dp->size; off += sizeof(de)){
554     if(readi(dp, (char*) &de, off, sizeof(de)) != sizeof(de))
555       panic("wdir read");
556     if(de.inum == 0)
557       break;
558   }
559 
560   de.inum = ino;
561   for(i = 0; i < DIRSIZ && name[i]; i++)
562     de.name[i] = name[i];
563   for( ; i < DIRSIZ; i++)
564     de.name[i] = '\0';
565 
566   if(writei(dp, (char*) &de, off, sizeof(de)) != sizeof(de))
567     panic("wdir write");
568 }
569 
570 struct inode*
571 mknod(char *cp, short type, short major, short minor)
572 {
573   struct inode *ip, *dp;
574   char *last;
575 
576   if((dp = namei(cp, NAMEI_CREATE, 0, &last, 0)) == 0)
577     return 0;
578 
579   ip = mknod1(dp, last, type, major, minor);
580 
581   iput(dp);
582 
583   return ip;
584 }
585 
586 struct inode*
587 mknod1(struct inode *dp, char *name, short type, short major, short minor)
588 {
589   struct inode *ip;
590 
591   ip = ialloc(dp->dev, type);
592   if(ip == 0)
593     return 0;
594   ip->major = major;
595   ip->minor = minor;
596   ip->size = 0;
597   ip->nlink = 1;
598 
599   iupdate(ip);  // write new inode to disk
600 
601   wdir(dp, name, ip->inum);
602 
603   return ip;
604 }
605 
606 int
607 unlink(char *cp)
608 {
609   struct inode *ip, *dp;
610   struct dirent de;
611   uint off, inum, dev;
612 
613   dp = namei(cp, NAMEI_DELETE, &off, 0, 0);
614   if(dp == 0)
615     return -1;
616 
617   dev = dp->dev;
618 
619   if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de) || de.inum == 0)
620     panic("unlink no entry");
621 
622   inum = de.inum;
623 
624   memset(&de, 0, sizeof(de));
625   if(writei(dp, (char*)&de, off, sizeof(de)) != sizeof(de))
626     panic("unlink dir write");
627 
628   iupdate(dp);
629   iput(dp);
630 
631   ip = iget(dev, inum);
632 
633   if(ip->nlink < 1)
634     panic("unlink nlink < 1");
635 
636   ip->nlink--;
637 
638   iupdate(ip);
639   iput(ip);
640 
641   return 0;
642 }
643 
644 int
645 link(char *name1, char *name2)
646 {
647   struct inode *ip, *dp;
648   char *last;
649 
650   if((ip = namei(name1, NAMEI_LOOKUP, 0, 0, 0)) == 0)
651     return -1;
652   if(ip->type == T_DIR){
653     iput(ip);
654     return -1;
655   }
656 
657   iunlock(ip);
658 
659   if((dp = namei(name2, NAMEI_CREATE, 0, &last, 0)) == 0) {
660     idecref(ip);
661     return -1;
662   }
663   if(dp->dev != ip->dev){
664     idecref(ip);
665     iput(dp);
666     return -1;
667   }
668 
669   ilock(ip);
670   ip->nlink += 1;
671   iupdate(ip);
672 
673   wdir(dp, last, ip->inum);
674   iput(dp);
675   iput(ip);
676 
677   return 0;
678 }
679