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" and "virtual memory"
42 assignments (projects 2 and 3), please treat all the code in
43 the filesys directory as a black box. No changes should be
44 needed. For those projects, a single lock external to the
45 filesystem code suffices.
47 The filesystem consists of a set of files. Each file has a
48 header called an `index node' or `inode', represented by
49 struct inode, that is stored by itself in a single sector (see
50 inode.h). The header contains the file's length in bytes and
51 an array that lists the sector numbers for the file's
54 Two files are special. The first special file is the free
55 map, whose inode is always stored in sector 0
56 (FREE_MAP_SECTOR). The free map stores a bitmap (see
57 lib/bitmap.h) that contains one bit for each sector on the
58 disk. Each bit that corresponds to a sector within a file is
59 set to true, and the other bits, which are not part of any
60 file, are set to false.
62 The second special file is the root directory, whose inode is
63 always stored in sector 1 (ROOT_DIR_SECTOR). The root
64 directory file stores an array of `struct dir_entry' (see
65 directory.h), each of which, if it is in use, associates a
66 filename with the sector of the file's inode.
68 The filesystem implemented here has the following limitations:
70 - No synchronization. Concurrent accesses will interfere
71 with one another, so external synchronization is needed.
73 - File size is fixed at creation time. Because the root
74 directory is represented as a file, the number of files
75 that may be created is also limited.
77 - File data is allocated as a single extent, so that
78 external fragmentation can become a serious problem as a
79 file system is used over time.
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 /* Shuts down the filesystem module, writing any unwritten data
136 Currently there's nothing to do. You'll need to add code here
137 when you implement write-behind caching. */
143 /* Creates a file named NAME with the given INITIAL_SIZE.
144 Returns true if successful, false otherwise.
145 Fails if a file named NAME already exists,
146 or if internal memory allocation fails. */
148 filesys_create (const char *name, off_t initial_size)
150 struct dir *dir = NULL;
151 struct bitmap *free_map = NULL;
152 disk_sector_t inode_sector;
153 bool success = false;
155 /* Read the root directory. */
156 dir = dir_create (NUM_DIR_ENTRIES);
159 dir_read (dir, root_dir_file);
160 if (dir_lookup (dir, name, NULL))
163 /* Allocate a block for the inode. */
164 free_map = bitmap_create (disk_size (filesys_disk));
165 if (free_map == NULL)
167 bitmap_read (free_map, free_map_file);
168 inode_sector = bitmap_scan_and_flip (free_map, 0, 1, false);
169 if (inode_sector == BITMAP_ERROR)
172 /* Add the file to the directory. */
173 if (!dir_add (dir, name, inode_sector))
176 /* Allocate space for the file. */
177 if (!inode_create (free_map, inode_sector, initial_size))
180 /* Write everything back. */
181 dir_write (dir, root_dir_file);
182 bitmap_write (free_map, free_map_file);
188 bitmap_destroy (free_map);
194 /* Opens a file named NAME and initializes FILE for usage with
195 the file_*() functions declared in file.h.
196 Returns the new file if successful or a null pointer
198 Fails if no file named NAME exists,
199 or if an internal memory allocation fails. */
201 filesys_open (const char *name)
203 struct dir *dir = NULL;
204 struct file *file = NULL;
205 disk_sector_t inode_sector;
207 dir = dir_create (NUM_DIR_ENTRIES);
211 dir_read (dir, root_dir_file);
212 if (dir_lookup (dir, name, &inode_sector))
213 file = file_open (inode_sector);
221 /* Deletes the file named NAME.
222 Returns true if successful, false on failure.
223 Fails if no file named NAME exists,
224 or if an internal memory allocation fails. */
226 filesys_remove (const char *name)
228 struct dir *dir = NULL;
230 disk_sector_t inode_sector;
231 bool success = false;
233 /* Read the root directory. */
234 dir = dir_create (NUM_DIR_ENTRIES);
237 dir_read (dir, root_dir_file);
238 if (!dir_lookup (dir, name, &inode_sector))
241 /* Open the inode and delete it. */
242 inode = inode_open (inode_sector);
245 inode_remove (inode);
248 /* Remove file from root directory and write directory back to
250 dir_remove (dir, name);
251 dir_write (dir, root_dir_file);
262 /* Prints a list of files in the filesystem to the system
264 Returns true if successful, false on failure,
265 which occurs only if an internal memory allocation fails. */
269 struct dir *dir = dir_create (NUM_DIR_ENTRIES);
272 dir_read (dir, root_dir_file);
279 static void must_succeed_function (int, bool) NO_INLINE;
280 #define MUST_SUCCEED(EXPR) must_succeed_function (__LINE__, EXPR)
282 /* Performs basic sanity checks on the filesystem.
283 The filesystem should not contain a file named `foo' when
286 filesys_self_test (void)
288 static const char s[] = "This is a test string.";
289 static const char zeros[sizeof s] = {0};
294 filesys_remove ("foo");
295 for (i = 0; i < 2; i++)
297 /* Create file and check that it contains zeros
298 throughout the created length. */
299 MUST_SUCCEED (filesys_create ("foo", sizeof s));
300 MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
301 MUST_SUCCEED (file_read (file, s2, sizeof s2) == sizeof s2);
302 MUST_SUCCEED (memcmp (s2, zeros, sizeof s) == 0);
303 MUST_SUCCEED (file_tell (file) == sizeof s);
304 MUST_SUCCEED (file_length (file) == sizeof s);
307 /* Reopen file and write to it. */
308 MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
309 MUST_SUCCEED (file_write (file, s, sizeof s) == sizeof s);
310 MUST_SUCCEED (file_tell (file) == sizeof s);
311 MUST_SUCCEED (file_length (file) == sizeof s);
314 /* Reopen file and verify that it reads back correctly.
315 Delete file while open to check proper semantics. */
316 MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
317 MUST_SUCCEED (filesys_remove ("foo"));
318 MUST_SUCCEED (filesys_open ("foo") == NULL);
319 MUST_SUCCEED (file_read (file, s2, sizeof s) == sizeof s);
320 MUST_SUCCEED (memcmp (s, s2, sizeof s) == 0);
321 MUST_SUCCEED (file_tell (file) == sizeof s);
322 MUST_SUCCEED (file_length (file) == sizeof s);
326 printf ("filesys: self test ok\n");
329 /* Formats the filesystem. */
333 struct bitmap *free_map;
336 printf ("Formatting filesystem...");
338 /* Create the initial bitmap and reserve sectors for the
339 free map and root directory inodes. */
340 free_map = bitmap_create (disk_size (filesys_disk));
341 if (free_map == NULL)
342 PANIC ("bitmap creation failed--disk is too large");
343 bitmap_mark (free_map, FREE_MAP_SECTOR);
344 bitmap_mark (free_map, ROOT_DIR_SECTOR);
346 /* Allocate free map and root dir files. */
347 if (!inode_create (free_map, FREE_MAP_SECTOR, bitmap_file_size (free_map)))
348 PANIC ("free map creation failed--disk is too large");
349 if (!inode_create (free_map, ROOT_DIR_SECTOR, dir_size (NUM_DIR_ENTRIES)))
350 PANIC ("root directory creation failed");
352 /* Write out the free map now that we have space reserved
354 free_map_file = file_open (FREE_MAP_SECTOR);
355 if (free_map_file == NULL)
356 PANIC ("can't open free map file");
357 bitmap_write (free_map, free_map_file);
358 bitmap_destroy (free_map);
359 file_close (free_map_file);
361 /* Write out the root directory in the same way. */
362 root_dir_file = file_open (ROOT_DIR_SECTOR);
363 if (root_dir_file == NULL)
364 PANIC ("can't open root directory");
365 dir = dir_create (NUM_DIR_ENTRIES);
367 PANIC ("can't initialize root directory");
368 dir_write (dir, root_dir_file);
370 file_close (root_dir_file);
375 /* If SUCCESS is false, panics with an error complaining about
378 must_succeed_function (int line_no, bool success)
381 PANIC ("filesys_self_test: operation failed on line %d", line_no);