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