Mercurial > hg > Members > anatofuz > CbC_xv6
comparison src/fs.c @ 0:83c23a36980d
Init
author | Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 26 May 2017 23:11:05 +0900 |
parents | |
children | 36bd61f5c847 |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:83c23a36980d |
---|---|
1 // File system implementation. Five layers: | |
2 // + Blocks: allocator for raw disk blocks. | |
3 // + Log: crash recovery for multi-step updates. | |
4 // + Files: inode allocator, reading, writing, metadata. | |
5 // + Directories: inode with special contents (list of other inodes!) | |
6 // + Names: paths like /usr/rtm/xv6/fs.c for convenient naming. | |
7 // | |
8 // This file contains the low-level file system manipulation | |
9 // routines. The (higher-level) system call implementations | |
10 // are in sysfile.c. | |
11 | |
12 #include "types.h" | |
13 #include "defs.h" | |
14 #include "param.h" | |
15 #include "stat.h" | |
16 #include "mmu.h" | |
17 #include "proc.h" | |
18 #include "spinlock.h" | |
19 #include "buf.h" | |
20 #include "fs.h" | |
21 #include "file.h" | |
22 | |
23 #define min(a, b) ((a) < (b) ? (a) : (b)) | |
24 static void itrunc (struct inode*); | |
25 | |
26 // Read the super block. | |
27 void readsb (int dev, struct superblock *sb) | |
28 { | |
29 struct buf *bp; | |
30 | |
31 bp = bread(dev, 1); | |
32 memmove(sb, bp->data, sizeof(*sb)); | |
33 brelse(bp); | |
34 } | |
35 | |
36 // Zero a block. | |
37 static void bzero (int dev, int bno) | |
38 { | |
39 struct buf *bp; | |
40 | |
41 bp = bread(dev, bno); | |
42 memset(bp->data, 0, BSIZE); | |
43 log_write(bp); | |
44 brelse(bp); | |
45 } | |
46 | |
47 // Blocks. | |
48 | |
49 // Allocate a zeroed disk block. | |
50 static uint balloc (uint dev) | |
51 { | |
52 int b, bi, m; | |
53 struct buf *bp; | |
54 struct superblock sb; | |
55 | |
56 bp = 0; | |
57 readsb(dev, &sb); | |
58 | |
59 for (b = 0; b < sb.size; b += BPB) { | |
60 bp = bread(dev, BBLOCK(b, sb.ninodes)); | |
61 | |
62 for (bi = 0; bi < BPB && b + bi < sb.size; bi++) { | |
63 m = 1 << (bi % 8); | |
64 | |
65 if ((bp->data[bi / 8] & m) == 0) { // Is block free? | |
66 bp->data[bi / 8] |= m; // Mark block in use. | |
67 log_write(bp); | |
68 brelse(bp); | |
69 bzero(dev, b + bi); | |
70 return b + bi; | |
71 } | |
72 } | |
73 | |
74 brelse(bp); | |
75 } | |
76 | |
77 panic("balloc: out of blocks"); | |
78 } | |
79 | |
80 // Free a disk block. | |
81 static void bfree (int dev, uint b) | |
82 { | |
83 struct buf *bp; | |
84 struct superblock sb; | |
85 int bi, m; | |
86 | |
87 readsb(dev, &sb); | |
88 bp = bread(dev, BBLOCK(b, sb.ninodes)); | |
89 bi = b % BPB; | |
90 m = 1 << (bi % 8); | |
91 | |
92 if ((bp->data[bi / 8] & m) == 0) { | |
93 panic("freeing free block"); | |
94 } | |
95 | |
96 bp->data[bi / 8] &= ~m; | |
97 log_write(bp); | |
98 brelse(bp); | |
99 } | |
100 | |
101 // Inodes. | |
102 // | |
103 // An inode describes a single unnamed file. | |
104 // The inode disk structure holds metadata: the file's type, | |
105 // its size, the number of links referring to it, and the | |
106 // list of blocks holding the file's content. | |
107 // | |
108 // The inodes are laid out sequentially on disk immediately after | |
109 // the superblock. Each inode has a number, indicating its | |
110 // position on the disk. | |
111 // | |
112 // The kernel keeps a cache of in-use inodes in memory | |
113 // to provide a place for synchronizing access | |
114 // to inodes used by multiple processes. The cached | |
115 // inodes include book-keeping information that is | |
116 // not stored on disk: ip->ref and ip->flags. | |
117 // | |
118 // An inode and its in-memory represtative go through a | |
119 // sequence of states before they can be used by the | |
120 // rest of the file system code. | |
121 // | |
122 // * Allocation: an inode is allocated if its type (on disk) | |
123 // is non-zero. ialloc() allocates, iput() frees if | |
124 // the link count has fallen to zero. | |
125 // | |
126 // * Referencing in cache: an entry in the inode cache | |
127 // is free if ip->ref is zero. Otherwise ip->ref tracks | |
128 // the number of in-memory pointers to the entry (open | |
129 // files and current directories). iget() to find or | |
130 // create a cache entry and increment its ref, iput() | |
131 // to decrement ref. | |
132 // | |
133 // * Valid: the information (type, size, &c) in an inode | |
134 // cache entry is only correct when the I_VALID bit | |
135 // is set in ip->flags. ilock() reads the inode from | |
136 // the disk and sets I_VALID, while iput() clears | |
137 // I_VALID if ip->ref has fallen to zero. | |
138 // | |
139 // * Locked: file system code may only examine and modify | |
140 // the information in an inode and its content if it | |
141 // has first locked the inode. The I_BUSY flag indicates | |
142 // that the inode is locked. ilock() sets I_BUSY, | |
143 // while iunlock clears it. | |
144 // | |
145 // Thus a typical sequence is: | |
146 // ip = iget(dev, inum) | |
147 // ilock(ip) | |
148 // ... examine and modify ip->xxx ... | |
149 // iunlock(ip) | |
150 // iput(ip) | |
151 // | |
152 // ilock() is separate from iget() so that system calls can | |
153 // get a long-term reference to an inode (as for an open file) | |
154 // and only lock it for short periods (e.g., in read()). | |
155 // The separation also helps avoid deadlock and races during | |
156 // pathname lookup. iget() increments ip->ref so that the inode | |
157 // stays cached and pointers to it remain valid. | |
158 // | |
159 // Many internal file system functions expect the caller to | |
160 // have locked the inodes involved; this lets callers create | |
161 // multi-step atomic operations. | |
162 | |
163 struct { | |
164 struct spinlock lock; | |
165 struct inode inode[NINODE]; | |
166 } icache; | |
167 | |
168 void iinit (void) | |
169 { | |
170 initlock(&icache.lock, "icache"); | |
171 } | |
172 | |
173 static struct inode* iget (uint dev, uint inum); | |
174 | |
175 //PAGEBREAK! | |
176 // Allocate a new inode with the given type on device dev. | |
177 // A free inode has a type of zero. | |
178 struct inode* ialloc (uint dev, short type) | |
179 { | |
180 int inum; | |
181 struct buf *bp; | |
182 struct dinode *dip; | |
183 struct superblock sb; | |
184 | |
185 readsb(dev, &sb); | |
186 | |
187 for (inum = 1; inum < sb.ninodes; inum++) { | |
188 bp = bread(dev, IBLOCK(inum)); | |
189 dip = (struct dinode*) bp->data + inum % IPB; | |
190 | |
191 if (dip->type == 0) { // a free inode | |
192 memset(dip, 0, sizeof(*dip)); | |
193 dip->type = type; | |
194 log_write(bp); // mark it allocated on the disk | |
195 brelse(bp); | |
196 return iget(dev, inum); | |
197 } | |
198 | |
199 brelse(bp); | |
200 } | |
201 | |
202 panic("ialloc: no inodes"); | |
203 } | |
204 | |
205 // Copy a modified in-memory inode to disk. | |
206 void iupdate (struct inode *ip) | |
207 { | |
208 struct buf *bp; | |
209 struct dinode *dip; | |
210 | |
211 bp = bread(ip->dev, IBLOCK(ip->inum)); | |
212 | |
213 dip = (struct dinode*) bp->data + ip->inum % IPB; | |
214 dip->type = ip->type; | |
215 dip->major = ip->major; | |
216 dip->minor = ip->minor; | |
217 dip->nlink = ip->nlink; | |
218 dip->size = ip->size; | |
219 | |
220 memmove(dip->addrs, ip->addrs, sizeof(ip->addrs)); | |
221 log_write(bp); | |
222 brelse(bp); | |
223 } | |
224 | |
225 // Find the inode with number inum on device dev | |
226 // and return the in-memory copy. Does not lock | |
227 // the inode and does not read it from disk. | |
228 static struct inode* iget (uint dev, uint inum) | |
229 { | |
230 struct inode *ip, *empty; | |
231 | |
232 acquire(&icache.lock); | |
233 | |
234 // Is the inode already cached? | |
235 empty = 0; | |
236 | |
237 for (ip = &icache.inode[0]; ip < &icache.inode[NINODE]; ip++) { | |
238 if (ip->ref > 0 && ip->dev == dev && ip->inum == inum) { | |
239 ip->ref++; | |
240 release(&icache.lock); | |
241 return ip; | |
242 } | |
243 | |
244 if (empty == 0 && ip->ref == 0) { // Remember empty slot. | |
245 empty = ip; | |
246 } | |
247 } | |
248 | |
249 // Recycle an inode cache entry. | |
250 if (empty == 0) { | |
251 panic("iget: no inodes"); | |
252 } | |
253 | |
254 ip = empty; | |
255 ip->dev = dev; | |
256 ip->inum = inum; | |
257 ip->ref = 1; | |
258 ip->flags = 0; | |
259 release(&icache.lock); | |
260 | |
261 return ip; | |
262 } | |
263 | |
264 // Increment reference count for ip. | |
265 // Returns ip to enable ip = idup(ip1) idiom. | |
266 struct inode* idup (struct inode *ip) | |
267 { | |
268 acquire(&icache.lock); | |
269 ip->ref++; | |
270 release(&icache.lock); | |
271 return ip; | |
272 } | |
273 | |
274 // Lock the given inode. | |
275 // Reads the inode from disk if necessary. | |
276 void ilock (struct inode *ip) | |
277 { | |
278 struct buf *bp; | |
279 struct dinode *dip; | |
280 | |
281 if (ip == 0 || ip->ref < 1) { | |
282 panic("ilock"); | |
283 } | |
284 | |
285 acquire(&icache.lock); | |
286 while (ip->flags & I_BUSY) { | |
287 sleep(ip, &icache.lock); | |
288 } | |
289 | |
290 ip->flags |= I_BUSY; | |
291 release(&icache.lock); | |
292 | |
293 if (!(ip->flags & I_VALID)) { | |
294 bp = bread(ip->dev, IBLOCK(ip->inum)); | |
295 | |
296 dip = (struct dinode*) bp->data + ip->inum % IPB; | |
297 ip->type = dip->type; | |
298 ip->major = dip->major; | |
299 ip->minor = dip->minor; | |
300 ip->nlink = dip->nlink; | |
301 ip->size = dip->size; | |
302 | |
303 memmove(ip->addrs, dip->addrs, sizeof(ip->addrs)); | |
304 brelse(bp); | |
305 ip->flags |= I_VALID; | |
306 | |
307 if (ip->type == 0) { | |
308 panic("ilock: no type"); | |
309 } | |
310 } | |
311 } | |
312 | |
313 // Unlock the given inode. | |
314 void iunlock (struct inode *ip) | |
315 { | |
316 if (ip == 0 || !(ip->flags & I_BUSY) || ip->ref < 1) { | |
317 panic("iunlock"); | |
318 } | |
319 | |
320 acquire(&icache.lock); | |
321 ip->flags &= ~I_BUSY; | |
322 wakeup(ip); | |
323 release(&icache.lock); | |
324 } | |
325 | |
326 // Drop a reference to an in-memory inode. | |
327 // If that was the last reference, the inode cache entry can | |
328 // be recycled. | |
329 // If that was the last reference and the inode has no links | |
330 // to it, free the inode (and its content) on disk. | |
331 void iput (struct inode *ip) | |
332 { | |
333 acquire(&icache.lock); | |
334 | |
335 if (ip->ref == 1 && (ip->flags & I_VALID) && ip->nlink == 0) { | |
336 // inode has no links: truncate and free inode. | |
337 if (ip->flags & I_BUSY) { | |
338 panic("iput busy"); | |
339 } | |
340 | |
341 ip->flags |= I_BUSY; | |
342 release(&icache.lock); | |
343 itrunc(ip); | |
344 ip->type = 0; | |
345 iupdate(ip); | |
346 | |
347 acquire(&icache.lock); | |
348 ip->flags = 0; | |
349 wakeup(ip); | |
350 } | |
351 | |
352 ip->ref--; | |
353 release(&icache.lock); | |
354 } | |
355 | |
356 // Common idiom: unlock, then put. | |
357 void iunlockput (struct inode *ip) | |
358 { | |
359 iunlock(ip); | |
360 iput(ip); | |
361 } | |
362 | |
363 //PAGEBREAK! | |
364 // Inode content | |
365 // | |
366 // The content (data) associated with each inode is stored | |
367 // in blocks on the disk. The first NDIRECT block numbers | |
368 // are listed in ip->addrs[]. The next NINDIRECT blocks are | |
369 // listed in block ip->addrs[NDIRECT]. | |
370 | |
371 // Return the disk block address of the nth block in inode ip. | |
372 // If there is no such block, bmap allocates one. | |
373 static uint bmap (struct inode *ip, uint bn) | |
374 { | |
375 uint addr, *a; | |
376 struct buf *bp; | |
377 | |
378 if (bn < NDIRECT) { | |
379 if ((addr = ip->addrs[bn]) == 0) { | |
380 ip->addrs[bn] = addr = balloc(ip->dev); | |
381 } | |
382 | |
383 return addr; | |
384 } | |
385 | |
386 bn -= NDIRECT; | |
387 | |
388 if (bn < NINDIRECT) { | |
389 // Load indirect block, allocating if necessary. | |
390 if ((addr = ip->addrs[NDIRECT]) == 0) { | |
391 ip->addrs[NDIRECT] = addr = balloc(ip->dev); | |
392 } | |
393 | |
394 bp = bread(ip->dev, addr); | |
395 a = (uint*) bp->data; | |
396 | |
397 if ((addr = a[bn]) == 0) { | |
398 a[bn] = addr = balloc(ip->dev); | |
399 log_write(bp); | |
400 } | |
401 | |
402 brelse(bp); | |
403 return addr; | |
404 } | |
405 | |
406 panic("bmap: out of range"); | |
407 } | |
408 | |
409 // Truncate inode (discard contents). | |
410 // Only called when the inode has no links | |
411 // to it (no directory entries referring to it) | |
412 // and has no in-memory reference to it (is | |
413 // not an open file or current directory). | |
414 static void itrunc (struct inode *ip) | |
415 { | |
416 int i, j; | |
417 struct buf *bp; | |
418 uint *a; | |
419 | |
420 for (i = 0; i < NDIRECT; i++) { | |
421 if (ip->addrs[i]) { | |
422 bfree(ip->dev, ip->addrs[i]); | |
423 ip->addrs[i] = 0; | |
424 } | |
425 } | |
426 | |
427 if (ip->addrs[NDIRECT]) { | |
428 bp = bread(ip->dev, ip->addrs[NDIRECT]); | |
429 a = (uint*) bp->data; | |
430 | |
431 for (j = 0; j < NINDIRECT; j++) { | |
432 if (a[j]) { | |
433 bfree(ip->dev, a[j]); | |
434 } | |
435 } | |
436 | |
437 brelse(bp); | |
438 bfree(ip->dev, ip->addrs[NDIRECT]); | |
439 ip->addrs[NDIRECT] = 0; | |
440 } | |
441 | |
442 ip->size = 0; | |
443 iupdate(ip); | |
444 } | |
445 | |
446 // Copy stat information from inode. | |
447 void stati (struct inode *ip, struct stat *st) | |
448 { | |
449 st->dev = ip->dev; | |
450 st->ino = ip->inum; | |
451 st->type = ip->type; | |
452 st->nlink = ip->nlink; | |
453 st->size = ip->size; | |
454 } | |
455 | |
456 //PAGEBREAK! | |
457 // Read data from inode. | |
458 int readi (struct inode *ip, char *dst, uint off, uint n) | |
459 { | |
460 uint tot, m; | |
461 struct buf *bp; | |
462 | |
463 if (ip->type == T_DEV) { | |
464 if (ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].read) { | |
465 return -1; | |
466 } | |
467 | |
468 return devsw[ip->major].read(ip, dst, n); | |
469 } | |
470 | |
471 if (off > ip->size || off + n < off) { | |
472 return -1; | |
473 } | |
474 | |
475 if (off + n > ip->size) { | |
476 n = ip->size - off; | |
477 } | |
478 | |
479 for (tot = 0; tot < n; tot += m, off += m, dst += m) { | |
480 bp = bread(ip->dev, bmap(ip, off / BSIZE)); | |
481 m = min(n - tot, BSIZE - off%BSIZE); | |
482 memmove(dst, bp->data + off % BSIZE, m); | |
483 brelse(bp); | |
484 } | |
485 | |
486 return n; | |
487 } | |
488 | |
489 // PAGEBREAK! | |
490 // Write data to inode. | |
491 int writei (struct inode *ip, char *src, uint off, uint n) | |
492 { | |
493 uint tot, m; | |
494 struct buf *bp; | |
495 | |
496 if (ip->type == T_DEV) { | |
497 if (ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].write) { | |
498 return -1; | |
499 } | |
500 | |
501 return devsw[ip->major].write(ip, src, n); | |
502 } | |
503 | |
504 if (off > ip->size || off + n < off) { | |
505 return -1; | |
506 } | |
507 | |
508 if (off + n > MAXFILE * BSIZE) { | |
509 return -1; | |
510 } | |
511 | |
512 for (tot = 0; tot < n; tot += m, off += m, src += m) { | |
513 bp = bread(ip->dev, bmap(ip, off / BSIZE)); | |
514 m = min(n - tot, BSIZE - off%BSIZE); | |
515 memmove(bp->data + off % BSIZE, src, m); | |
516 log_write(bp); | |
517 brelse(bp); | |
518 } | |
519 | |
520 if (n > 0 && off > ip->size) { | |
521 ip->size = off; | |
522 iupdate(ip); | |
523 } | |
524 | |
525 return n; | |
526 } | |
527 | |
528 //PAGEBREAK! | |
529 // Directories | |
530 | |
531 int namecmp (const char *s, const char *t) | |
532 { | |
533 return strncmp(s, t, DIRSIZ); | |
534 } | |
535 | |
536 // Look for a directory entry in a directory. | |
537 // If found, set *poff to byte offset of entry. | |
538 struct inode* dirlookup (struct inode *dp, char *name, uint *poff) | |
539 { | |
540 uint off, inum; | |
541 struct dirent de; | |
542 | |
543 if (dp->type != T_DIR) { | |
544 panic("dirlookup not DIR"); | |
545 } | |
546 | |
547 for (off = 0; off < dp->size; off += sizeof(de)) { | |
548 if (readi(dp, (char*) &de, off, sizeof(de)) != sizeof(de)) { | |
549 panic("dirlink read"); | |
550 } | |
551 | |
552 if (de.inum == 0) { | |
553 continue; | |
554 } | |
555 | |
556 if (namecmp(name, de.name) == 0) { | |
557 // entry matches path element | |
558 if (poff) { | |
559 *poff = off; | |
560 } | |
561 | |
562 inum = de.inum; | |
563 return iget(dp->dev, inum); | |
564 } | |
565 } | |
566 | |
567 return 0; | |
568 } | |
569 | |
570 // Write a new directory entry (name, inum) into the directory dp. | |
571 int dirlink (struct inode *dp, char *name, uint inum) | |
572 { | |
573 int off; | |
574 struct dirent de; | |
575 struct inode *ip; | |
576 | |
577 // Check that name is not present. | |
578 if ((ip = dirlookup(dp, name, 0)) != 0) { | |
579 iput(ip); | |
580 return -1; | |
581 } | |
582 | |
583 // Look for an empty dirent. | |
584 for (off = 0; off < dp->size; off += sizeof(de)) { | |
585 if (readi(dp, (char*) &de, off, sizeof(de)) != sizeof(de)) { | |
586 panic("dirlink read"); | |
587 } | |
588 | |
589 if (de.inum == 0) { | |
590 break; | |
591 } | |
592 } | |
593 | |
594 strncpy(de.name, name, DIRSIZ); | |
595 de.inum = inum; | |
596 | |
597 if (writei(dp, (char*) &de, off, sizeof(de)) != sizeof(de)) { | |
598 panic("dirlink"); | |
599 } | |
600 | |
601 return 0; | |
602 } | |
603 | |
604 //PAGEBREAK! | |
605 // Paths | |
606 | |
607 // Copy the next path element from path into name. | |
608 // Return a pointer to the element following the copied one. | |
609 // The returned path has no leading slashes, | |
610 // so the caller can check *path=='\0' to see if the name is the last one. | |
611 // If no name to remove, return 0. | |
612 // | |
613 // Examples: | |
614 // skipelem("a/bb/c", name) = "bb/c", setting name = "a" | |
615 // skipelem("///a//bb", name) = "bb", setting name = "a" | |
616 // skipelem("a", name) = "", setting name = "a" | |
617 // skipelem("", name) = skipelem("////", name) = 0 | |
618 // | |
619 static char* skipelem (char *path, char *name) | |
620 { | |
621 char *s; | |
622 int len; | |
623 | |
624 while (*path == '/') { | |
625 path++; | |
626 } | |
627 | |
628 if (*path == 0) { | |
629 return 0; | |
630 } | |
631 | |
632 s = path; | |
633 | |
634 while (*path != '/' && *path != 0) { | |
635 path++; | |
636 } | |
637 | |
638 len = path - s; | |
639 | |
640 if (len >= DIRSIZ) { | |
641 memmove(name, s, DIRSIZ); | |
642 } else { | |
643 memmove(name, s, len); | |
644 name[len] = 0; | |
645 } | |
646 | |
647 while (*path == '/') { | |
648 path++; | |
649 } | |
650 | |
651 return path; | |
652 } | |
653 | |
654 // Look up and return the inode for a path name. | |
655 // If parent != 0, return the inode for the parent and copy the final | |
656 // path element into name, which must have room for DIRSIZ bytes. | |
657 static struct inode* namex (char *path, int nameiparent, char *name) | |
658 { | |
659 struct inode *ip, *next; | |
660 | |
661 if (*path == '/') { | |
662 ip = iget(ROOTDEV, ROOTINO); | |
663 } else { | |
664 ip = idup(proc->cwd); | |
665 } | |
666 | |
667 while ((path = skipelem(path, name)) != 0) { | |
668 ilock(ip); | |
669 | |
670 if (ip->type != T_DIR) { | |
671 iunlockput(ip); | |
672 return 0; | |
673 } | |
674 | |
675 if (nameiparent && *path == '\0') { | |
676 // Stop one level early. | |
677 iunlock(ip); | |
678 return ip; | |
679 } | |
680 | |
681 if ((next = dirlookup(ip, name, 0)) == 0) { | |
682 iunlockput(ip); | |
683 return 0; | |
684 } | |
685 | |
686 iunlockput(ip); | |
687 ip = next; | |
688 } | |
689 | |
690 if (nameiparent) { | |
691 iput(ip); | |
692 return 0; | |
693 } | |
694 | |
695 return ip; | |
696 } | |
697 | |
698 struct inode* namei (char *path) | |
699 { | |
700 char name[DIRSIZ]; | |
701 return namex(path, 0, name); | |
702 } | |
703 | |
704 struct inode* nameiparent (char *path, char *name) | |
705 { | |
706 return namex(path, 1, name); | |
707 } |