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 - No indirect blocks. This limits maximum file size to the
78 number of sector pointers that fit in a single inode
79 times the size of a sector, or 126 * 512 == 63 kB given
80 32-bit sizes and 512-byte sectors.
84 - Filenames limited to 14 characters.
86 - A system crash mid-operation may corrupt the disk in a way
87 that cannot be repaired automatically. No `fsck' tool is
90 However one important feature is included:
92 - Unix-like semantics for filesys_remove() are implemented.
93 That is, if a file is open when it is removed, its blocks
94 are not deallocated and it may still be accessed by the
95 threads that have it open until the last one closes it. */
97 /* Sectors of system file inodes. */
98 #define FREE_MAP_SECTOR 0 /* Free map file inode sector. */
99 #define ROOT_DIR_SECTOR 1 /* Root directory file inode sector. */
101 /* Root directory. */
102 #define NUM_DIR_ENTRIES 10 /* Maximum number of directory entries. */
104 /* The disk that contains the filesystem. */
105 struct disk *filesys_disk;
107 /* The free map and root directory files.
108 These files are opened by filesys_init() and never closed. */
109 struct file *free_map_file, *root_dir_file;
111 static void do_format (void);
113 /* Initializes the filesystem module.
114 If FORMAT is true, reformats the filesystem. */
116 filesys_init (bool format)
120 filesys_disk = disk_get (0, 1);
121 if (filesys_disk == NULL)
122 PANIC ("hd0:1 (hdb) not present, filesystem initialization failed");
127 free_map_file = file_open (FREE_MAP_SECTOR);
128 if (free_map_file == NULL)
129 PANIC ("can't open free map file");
130 root_dir_file = file_open (ROOT_DIR_SECTOR);
131 if (root_dir_file == NULL)
132 PANIC ("can't open root dir file");
135 /* Shuts down the filesystem module, writing any unwritten data
137 Currently there's nothing to do. You'll need to add code here
138 when you implement write-behind caching. */
144 /* Creates a file named NAME with the given INITIAL_SIZE.
145 Returns true if successful, false otherwise.
146 Fails if a file named NAME already exists,
147 or if internal memory allocation fails. */
149 filesys_create (const char *name, off_t initial_size)
151 struct dir *dir = NULL;
152 struct bitmap *free_map = NULL;
153 struct inode *inode = NULL;
154 disk_sector_t inode_sector;
155 bool success = false;
157 /* Read the root directory. */
158 dir = dir_create (NUM_DIR_ENTRIES);
161 dir_read (dir, root_dir_file);
162 if (dir_lookup (dir, name, NULL))
165 /* Allocate a block for the inode. */
166 free_map = bitmap_create (disk_size (filesys_disk));
167 if (free_map == NULL)
169 bitmap_read (free_map, free_map_file);
170 inode_sector = bitmap_scan_and_flip (free_map, 0, 1, false);
171 if (inode_sector == BITMAP_ERROR)
174 /* Add the file to the directory. */
175 if (!dir_add (dir, name, inode_sector))
178 /* Allocate space for the file. */
179 inode = inode_create (free_map, inode_sector, initial_size);
183 /* Write everything back. */
184 inode_commit (inode);
185 dir_write (dir, root_dir_file);
186 bitmap_write (free_map, free_map_file);
193 bitmap_destroy (free_map);
199 /* Opens a file named NAME and initializes FILE for usage with
200 the file_*() functions declared in file.h.
201 Returns the new file if successful or a null pointer
203 Fails if no file named NAME exists,
204 or if an internal memory allocation fails. */
206 filesys_open (const char *name)
208 struct dir *dir = NULL;
209 struct file *file = NULL;
210 disk_sector_t inode_sector;
212 dir = dir_create (NUM_DIR_ENTRIES);
216 dir_read (dir, root_dir_file);
217 if (dir_lookup (dir, name, &inode_sector))
218 file = file_open (inode_sector);
226 /* Deletes the file named NAME.
227 Returns true if successful, false on failure.
228 Fails if no file named NAME exists,
229 or if an internal memory allocation fails. */
231 filesys_remove (const char *name)
233 struct dir *dir = NULL;
235 disk_sector_t inode_sector;
236 bool success = false;
238 /* Read the root directory. */
239 dir = dir_create (NUM_DIR_ENTRIES);
242 dir_read (dir, root_dir_file);
243 if (!dir_lookup (dir, name, &inode_sector))
246 /* Open the inode and delete it. */
247 inode = inode_open (inode_sector);
250 inode_remove (inode);
253 /* Remove file from root directory and write directory back to
255 dir_remove (dir, name);
256 dir_write (dir, root_dir_file);
267 /* Prints a list of files in the filesystem to the system
269 Returns true if successful, false on failure,
270 which occurs only if an internal memory allocation fails. */
274 struct dir *dir = dir_create (NUM_DIR_ENTRIES);
277 dir_read (dir, root_dir_file);
284 /* Dumps the filesystem state to the system console,
285 including the free map, the list of files, and file contents.
286 Returns true if successful, false on failure,
287 which occurs only if an internal memory allocation fails. */
291 struct bitmap *free_map;
294 printf ("Free map:\n");
295 free_map = bitmap_create (disk_size (filesys_disk));
296 if (free_map == NULL)
298 bitmap_read (free_map, free_map_file);
299 bitmap_dump (free_map);
300 bitmap_destroy (free_map);
303 dir = dir_create (NUM_DIR_ENTRIES);
306 dir_read (dir, root_dir_file);
313 static void must_succeed_function (int, bool) NO_INLINE;
314 #define MUST_SUCCEED(EXPR) must_succeed_function (__LINE__, EXPR)
316 /* Performs basic sanity checks on the filesystem.
317 The filesystem should not contain a file named `foo' when
320 filesys_self_test (void)
322 static const char s[] = "This is a test string.";
323 static const char zeros[sizeof s] = {0};
328 filesys_remove ("foo");
329 for (i = 0; i < 2; i++)
331 /* Create file and check that it contains zeros
332 throughout the created length. */
333 MUST_SUCCEED (filesys_create ("foo", sizeof s));
334 MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
335 MUST_SUCCEED (file_read (file, s2, sizeof s2) == sizeof s2);
336 MUST_SUCCEED (memcmp (s2, zeros, sizeof s) == 0);
337 MUST_SUCCEED (file_tell (file) == sizeof s);
338 MUST_SUCCEED (file_length (file) == sizeof s);
341 /* Reopen file and write to it. */
342 MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
343 MUST_SUCCEED (file_write (file, s, sizeof s) == sizeof s);
344 MUST_SUCCEED (file_tell (file) == sizeof s);
345 MUST_SUCCEED (file_length (file) == sizeof s);
348 /* Reopen file and verify that it reads back correctly.
349 Delete file while open to check proper semantics. */
350 MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
351 MUST_SUCCEED (filesys_remove ("foo"));
352 MUST_SUCCEED (file_read (file, s2, sizeof s) == sizeof s);
353 MUST_SUCCEED (memcmp (s, s2, sizeof s) == 0);
354 MUST_SUCCEED (file_tell (file) == sizeof s);
355 MUST_SUCCEED (file_length (file) == sizeof s);
358 /* Make sure file is deleted. */
359 MUST_SUCCEED ((file = filesys_open ("foo")) == NULL);
362 printf ("filesys: self test ok\n");
365 /* Formats the filesystem. */
369 struct bitmap *free_map;
370 struct inode *map_inode, *dir_inode;
373 printf ("Formatting filesystem...");
375 /* Create the initial bitmap and reserve sectors for the
376 free map and root directory inodes. */
377 free_map = bitmap_create (disk_size (filesys_disk));
378 if (free_map == NULL)
379 PANIC ("bitmap creation failed--disk is too large");
380 bitmap_mark (free_map, FREE_MAP_SECTOR);
381 bitmap_mark (free_map, ROOT_DIR_SECTOR);
383 /* Allocate data sector(s) for the free map file
384 and write its inode to disk. */
385 map_inode = inode_create (free_map, FREE_MAP_SECTOR,
386 bitmap_file_size (free_map));
387 if (map_inode == NULL)
388 PANIC ("free map creation failed--disk is too large");
389 inode_commit (map_inode);
390 inode_close (map_inode);
392 /* Allocate data sector(s) for the root directory file
393 and write its inodes to disk. */
394 dir_inode = inode_create (free_map, ROOT_DIR_SECTOR,
395 dir_size (NUM_DIR_ENTRIES));
396 if (dir_inode == NULL)
397 PANIC ("root directory creation failed");
398 inode_commit (dir_inode);
399 inode_close (dir_inode);
401 /* Write out the free map now that we have space reserved
403 free_map_file = file_open (FREE_MAP_SECTOR);
404 if (free_map_file == NULL)
405 PANIC ("can't open free map file");
406 bitmap_write (free_map, free_map_file);
407 bitmap_destroy (free_map);
408 file_close (free_map_file);
410 /* Write out the root directory in the same way. */
411 root_dir_file = file_open (ROOT_DIR_SECTOR);
412 if (root_dir_file == NULL)
413 PANIC ("can't open root directory");
414 dir = dir_create (NUM_DIR_ENTRIES);
416 PANIC ("can't initialize root directory");
417 dir_write (dir, root_dir_file);
419 file_close (root_dir_file);
424 /* If SUCCESS is false, panics with an error complaining about
427 must_succeed_function (int line_no, bool success)
430 PANIC ("filesys_self_test: operation failed on line %d", line_no);