1 /* This file is derived from source code for the Nachos
2 instructional operating system. The Nachos copyright notice
3 is reproduced in full below. */
5 /* Copyright (c) 1992-1996 The Regents of the University of California.
8 Permission to use, copy, modify, and distribute this software
9 and its documentation for any purpose, without fee, and
10 without written agreement is hereby granted, provided that the
11 above copyright notice and the following two paragraphs appear
12 in all copies of this software.
14 IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO
15 ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR
16 CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE
17 AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA
18 HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
20 THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY
21 WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
22 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
23 PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS"
24 BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
25 PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
29 #include "filesys/filesys.h"
34 #include "filesys/file.h"
35 #include "filesys/inode.h"
36 #include "filesys/directory.h"
37 #include "devices/disk.h"
41 For the purposes of the "user processes" assignment (project
42 2), please treat all the code in the filesys directory as a
43 black box. No changes should be needed. For that project, a
44 single lock external to the filesystem code suffices.
46 The filesystem consists of a set of files. Each file has a
47 header called an `index node' or `inode', represented by
48 struct inode, that is stored by itself in a single sector (see
49 inode.h). The header contains the file's length in bytes and
50 an array that lists the sector numbers for the file's
53 Two files are special. The first special file is the free
54 map, whose inode is always stored in sector 0
55 (FREE_MAP_SECTOR). The free map stores a bitmap (see
56 lib/bitmap.h) that contains one bit for each sector on the
57 disk. Each bit that corresponds to a sector within a file is
58 set to true, and the other bits, which are not part of any
59 file, are set to false.
61 The second special file is the root directory, whose inode is
62 always stored in sector 1 (ROOT_DIR_SECTOR). The root
63 directory file stores an array of `struct dir_entry' (see
64 directory.h), each of which, if it is in use, associates a
65 filename with the sector of the file's inode.
67 The filesystem implemented here has the following limitations:
69 - No synchronization. Concurrent accesses will interfere
70 with one another, so external synchronization is needed.
72 - File size is fixed at creation time. Because the root
73 directory is represented as a file, the number of files
74 that may be created is also limited.
76 - No indirect blocks. This limits maximum file size to the
77 number of sector pointers that fit in a single inode
78 times the size of a sector, or 126 * 512 == 63 kB given
79 32-bit sizes and 512-byte sectors.
83 - Filenames limited to 14 characters.
85 - A system crash mid-operation may corrupt the disk in a way
86 that cannot be repaired automatically. No `fsck' tool is
89 However one important feature is included:
91 - Unix-like semantics for filesys_remove() are implemented.
92 That is, if a file is open when it is removed, its blocks
93 are not deallocated and it may still be accessed by the
94 threads that have it open until the last one closes it. */
96 /* Sectors of system file inodes. */
97 #define FREE_MAP_SECTOR 0 /* Free map file inode sector. */
98 #define ROOT_DIR_SECTOR 1 /* Root directory file inode sector. */
100 /* Root directory. */
101 #define NUM_DIR_ENTRIES 10 /* Maximum number of directory entries. */
103 /* The disk that contains the filesystem. */
104 struct disk *filesys_disk;
106 /* The free map and root directory files.
107 These files are opened by filesys_init() and never closed. */
108 struct file *free_map_file, *root_dir_file;
110 static void do_format (void);
112 /* Initializes the filesystem module.
113 If FORMAT is true, reformats the filesystem. */
115 filesys_init (bool format)
119 filesys_disk = disk_get (0, 1);
120 if (filesys_disk == NULL)
121 PANIC ("hd0:1 (hdb) not present, filesystem initialization failed");
126 free_map_file = file_open (FREE_MAP_SECTOR);
127 if (free_map_file == NULL)
128 PANIC ("can't open free map file");
129 root_dir_file = file_open (ROOT_DIR_SECTOR);
130 if (root_dir_file == NULL)
131 PANIC ("can't open root dir file");
134 /* Creates a file named NAME with the given INITIAL_SIZE.
135 Returns true if successful, false otherwise.
136 Fails if a file named NAME already exists,
137 or if internal memory allocation fails. */
139 filesys_create (const char *name, off_t initial_size)
141 struct dir *dir = NULL;
142 struct bitmap *free_map = NULL;
143 struct inode *inode = NULL;
144 disk_sector_t inode_sector;
145 bool success = false;
147 /* Read the root directory. */
148 dir = dir_create (NUM_DIR_ENTRIES);
151 dir_read (dir, root_dir_file);
152 if (dir_lookup (dir, name, NULL))
155 /* Allocate a block for the inode. */
156 free_map = bitmap_create (disk_size (filesys_disk));
157 if (free_map == NULL)
159 bitmap_read (free_map, free_map_file);
160 inode_sector = bitmap_find_and_set (free_map);
161 if (inode_sector == BITMAP_ERROR)
164 /* Add the file to the directory. */
165 if (!dir_add (dir, name, inode_sector))
168 /* Allocate space for the file. */
169 inode = inode_create (free_map, inode_sector, initial_size);
173 /* Write everything back. */
174 inode_commit (inode);
175 dir_write (dir, root_dir_file);
176 bitmap_write (free_map, free_map_file);
183 bitmap_destroy (free_map);
189 /* Opens a file named NAME and initializes FILE for usage with
190 the file_*() functions declared in file.h.
191 Returns true if successful, false on failure.
192 Fails if no file named NAME exists,
193 or if an internal memory allocation fails. */
195 filesys_open (const char *name)
197 struct dir *dir = NULL;
198 struct file *file = NULL;
199 disk_sector_t inode_sector;
201 dir = dir_create (NUM_DIR_ENTRIES);
205 dir_read (dir, root_dir_file);
206 if (dir_lookup (dir, name, &inode_sector))
207 file = file_open (inode_sector);
215 /* Deletes the file named NAME.
216 Returns true if successful, false on failure.
217 Fails if no file named NAME exists,
218 or if an internal memory allocation fails. */
220 filesys_remove (const char *name)
222 struct dir *dir = NULL;
224 disk_sector_t inode_sector;
225 bool success = false;
227 /* Read the root directory. */
228 dir = dir_create (NUM_DIR_ENTRIES);
231 dir_read (dir, root_dir_file);
232 if (!dir_lookup (dir, name, &inode_sector))
235 /* Open the inode and delete it it. */
236 inode = inode_open (inode_sector);
239 inode_remove (inode);
242 /* Remove file from root directory and write directory back to
244 dir_remove (dir, name);
245 dir_write (dir, root_dir_file);
256 /* Prints a list of files in the filesystem to the system
258 Returns true if successful, false on failure,
259 which occurs only if an internal memory allocation fails. */
263 struct dir *dir = dir_create (NUM_DIR_ENTRIES);
266 dir_read (dir, root_dir_file);
273 /* Dumps the filesystem state to the system console,
274 including the free map, the list of files, and file contents.
275 Returns true if successful, false on failure,
276 which occurs only if an internal memory allocation fails. */
280 struct bitmap *free_map;
283 printf ("Free map:\n");
284 free_map = bitmap_create (disk_size (filesys_disk));
285 if (free_map == NULL)
287 bitmap_read (free_map, free_map_file);
288 bitmap_dump (free_map);
289 bitmap_destroy (free_map);
292 dir = dir_create (NUM_DIR_ENTRIES);
295 dir_read (dir, root_dir_file);
302 static void must_succeed_function (int, bool) NO_INLINE;
303 #define MUST_SUCCEED(EXPR) must_succeed_function (__LINE__, EXPR)
305 /* Performs basic sanity checks on the filesystem.
306 The filesystem should not contain a file named `foo' when
309 filesys_self_test (void)
311 static const char s[] = "This is a test string.";
312 static const char zeros[sizeof s] = {0};
317 filesys_remove ("foo");
318 for (i = 0; i < 2; i++)
320 /* Create file and check that it contains zeros
321 throughout the created length. */
322 MUST_SUCCEED (filesys_create ("foo", sizeof s));
323 MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
324 MUST_SUCCEED (file_read (file, s2, sizeof s2) == sizeof s2);
325 MUST_SUCCEED (memcmp (s2, zeros, sizeof s) == 0);
326 MUST_SUCCEED (file_tell (file) == sizeof s);
327 MUST_SUCCEED (file_length (file) == sizeof s);
330 /* Reopen file and write to it. */
331 MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
332 MUST_SUCCEED (file_write (file, s, sizeof s) == sizeof s);
333 MUST_SUCCEED (file_tell (file) == sizeof s);
334 MUST_SUCCEED (file_length (file) == sizeof s);
337 /* Reopen file and verify that it reads back correctly.
338 Delete file while open to check proper semantics. */
339 MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
340 MUST_SUCCEED (filesys_remove ("foo"));
341 MUST_SUCCEED (file_read (file, s2, sizeof s) == sizeof s);
342 MUST_SUCCEED (memcmp (s, s2, sizeof s) == 0);
343 MUST_SUCCEED (file_tell (file) == sizeof s);
344 MUST_SUCCEED (file_length (file) == sizeof s);
347 /* Make sure file is deleted. */
348 MUST_SUCCEED ((file = filesys_open ("foo")) == NULL);
351 printf ("filesys: self test ok\n");
354 /* Formats the filesystem. */
358 struct bitmap *free_map;
359 struct inode *map_inode, *dir_inode;
362 printf ("Formatting filesystem...");
364 /* Create the initial bitmap and reserve sectors for the
365 free map and root directory inodes. */
366 free_map = bitmap_create (disk_size (filesys_disk));
367 if (free_map == NULL)
368 PANIC ("bitmap creation failed--disk is too large");
369 bitmap_mark (free_map, FREE_MAP_SECTOR);
370 bitmap_mark (free_map, ROOT_DIR_SECTOR);
372 /* Allocate data sector(s) for the free map file
373 and write its inode to disk. */
374 map_inode = inode_create (free_map, FREE_MAP_SECTOR,
375 bitmap_file_size (free_map));
376 if (map_inode == NULL)
377 PANIC ("free map creation failed--disk is too large");
378 inode_commit (map_inode);
379 inode_close (map_inode);
381 /* Allocate data sector(s) for the root directory file
382 and write its inodes to disk. */
383 dir_inode = inode_create (free_map, ROOT_DIR_SECTOR,
384 dir_size (NUM_DIR_ENTRIES));
385 if (dir_inode == NULL)
386 PANIC ("root directory creation failed");
387 inode_commit (dir_inode);
388 inode_close (dir_inode);
390 /* Write out the free map now that we have space reserved
392 free_map_file = file_open (FREE_MAP_SECTOR);
393 if (free_map_file == NULL)
394 PANIC ("can't open free map file");
395 bitmap_write (free_map, free_map_file);
396 bitmap_destroy (free_map);
397 file_close (free_map_file);
399 /* Write out the root directory in the same way. */
400 root_dir_file = file_open (ROOT_DIR_SECTOR);
401 if (root_dir_file == NULL)
402 PANIC ("can't open root directory");
403 dir = dir_create (NUM_DIR_ENTRIES);
405 PANIC ("can't initialize root directory");
406 dir_write (dir, root_dir_file);
408 file_close (root_dir_file);
413 /* If SUCCESS is false, panics with an error complaining about
416 must_succeed_function (int line_no, bool success)
419 PANIC ("filesys_self_test: operation failed on line %d", line_no);