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
32 #include "directory.h"
40 The filesystem consists of a set of files. Each file has a
41 header, represented by struct filehdr, that is stored by
42 itself in a single sector (see filehdr.h). The header
43 contains the file's length in bytes and an array that lists
44 the sector numbers for the file's contents.
46 Two files are special. The first special file is the free
47 map, whose header is always stored in sector 0
48 (FREE_MAP_SECTOR). The free map stores a bitmap (see
49 lib/bitmap.h) that contains one bit for each sector on the
50 disk. Each bit that corresponds to a sector within a file is
51 set to true, and the other bits, which are not part of any
52 file, are set to false.
54 The second special file is the root directory, whose header is
55 always stored in sector 1 (ROOT_DIR_SECTOR). The root
56 directory file stores an array of `struct dir_entry' (see
57 directory.h), each of which, if it is in use, associates a
58 filename with the sector of the file's header.
60 The filesystem implemented here has the following limitations:
62 - No synchronization. Concurrent accesses will interfere
65 - File size is fixed at creation time. Because the root
66 directory is represented as a file, the number of files
67 that may be created is also limited.
69 - No indirect blocks. This limits maximum file size to the
70 number of sector pointers that fit in a single sector
71 times the size of a sector, or 126 * 512 == 63 kB given
72 32-bit sizes and 512-byte sectors.
74 - No nested subdirectories.
76 - Filenames limited to 14 characters.
78 - A system crash mid-operation may corrupt the disk in a way
79 that cannot be repaired automatically. No `fsck' tool is
82 Note: for the purposes of the "user processes" assignment
83 (project 2), please treat all the code in the filesys
84 directory as a black box. No changes should be needed. For
85 that project, a single lock external to the filesystem code
88 /* File header sectors for system files. */
89 #define FREE_MAP_SECTOR 0 /* Free map file header sector. */
90 #define ROOT_DIR_SECTOR 1 /* Root directory file header sector. */
93 #define NUM_DIR_ENTRIES 10 /* Maximum number of directory entries. */
94 #define ROOT_DIR_FILE_SIZE /* Root directory file size in bytes. */ \
95 (sizeof (struct dir_entry) * NUM_DIR_ENTRIES)
97 /* The disk that contains the filesystem. */
98 struct disk *filesys_disk;
100 /* The free map and root directory files.
101 These files are opened by filesys_init() and never closed. */
102 static struct file free_map_file, root_dir_file;
104 static void do_format (void);
106 /* Initializes the filesystem module.
107 If FORMAT is true, reformats the filesystem. */
109 filesys_init (bool format)
111 filesys_disk = disk_get (0, 1);
112 if (filesys_disk == NULL)
113 PANIC ("hd0:1 (hdb) not present, filesystem initialization failed");
118 if (!file_open (&free_map_file, FREE_MAP_SECTOR))
119 PANIC ("can't open free map file");
120 if (!file_open (&root_dir_file, ROOT_DIR_SECTOR))
121 PANIC ("can't open root dir file");
124 /* Creates a file named NAME with the given INITIAL_SIZE.
125 Returns true if successful, false otherwise.
126 Fails if a file named NAME already exists,
127 or if internal memory allocation fails. */
129 filesys_create (const char *name, off_t initial_size)
132 struct bitmap free_map;
133 disk_sector_t hdr_sector;
134 struct filehdr *filehdr;
135 bool success = false;
137 /* Read the root directory. */
138 if (!dir_init (&dir, NUM_DIR_ENTRIES))
140 dir_read (&dir, &root_dir_file);
141 if (dir_lookup (&dir, name, NULL))
144 /* Allocate a block for the file header. */
145 if (!bitmap_init (&free_map, disk_size (filesys_disk)))
147 bitmap_read (&free_map, &free_map_file);
148 hdr_sector = bitmap_find_and_set (&free_map);
149 if (hdr_sector == BITMAP_ERROR)
152 /* Add the file to the directory. */
153 if (!dir_add (&dir, name, hdr_sector))
156 /* Allocate space for the file. */
157 filehdr = filehdr_allocate (&free_map, initial_size);
161 /* Write everything back. */
162 filehdr_write (filehdr, hdr_sector);
163 dir_write (&dir, &root_dir_file);
164 bitmap_write (&free_map, &free_map_file);
169 filehdr_destroy (filehdr);
171 bitmap_destroy (&free_map);
178 /* Opens a file named NAME and initializes FILE for usage with
179 the file_*() functions declared in file.h.
180 Returns true if successful, false on failure.
181 Fails if no file named NAME exists,
182 or if an internal memory allocation fails. */
184 filesys_open (const char *name, struct file *file)
187 disk_sector_t hdr_sector;
188 bool success = false;
190 if (!dir_init (&dir, NUM_DIR_ENTRIES))
192 dir_read (&dir, &root_dir_file);
193 if (dir_lookup (&dir, name, &hdr_sector))
194 success = file_open (file, hdr_sector);
200 /* Deletes the file named NAME.
201 Returns true if successful, false on failure.
202 Fails if no file named NAME exists,
203 or if an internal memory allocation fails. */
205 filesys_remove (const char *name)
208 disk_sector_t hdr_sector;
209 struct filehdr *filehdr;
210 struct bitmap free_map;
211 bool success = false;
213 /* Read the root directory. */
214 if (!dir_init (&dir, NUM_DIR_ENTRIES))
216 dir_read (&dir, &root_dir_file);
217 if (!dir_lookup (&dir, name, &hdr_sector))
220 /* Read the file header. */
221 filehdr = filehdr_read (hdr_sector);
225 /* Allocate a block for the file header. */
226 if (!bitmap_init (&free_map, disk_size (filesys_disk)))
228 bitmap_read (&free_map, &free_map_file);
231 filehdr_deallocate (filehdr, &free_map);
232 bitmap_reset (&free_map, hdr_sector);
233 dir_remove (&dir, name);
235 /* Write everything back. */
236 bitmap_write (&free_map, &free_map_file);
237 dir_write (&dir, &root_dir_file);
242 bitmap_destroy (&free_map);
244 filehdr_destroy (filehdr);
251 /* Prints a list of files in the filesystem to the system
253 Returns true if successful, false on failure,
254 which occurs only if an internal memory allocation fails. */
260 if (!dir_init (&dir, NUM_DIR_ENTRIES))
262 dir_read (&dir, &root_dir_file);
269 /* Dumps the filesystem state to the system console,
270 including the free map, the list of files, and file contents.
271 Returns true if successful, false on failure,
272 which occurs only if an internal memory allocation fails. */
276 struct bitmap free_map;
279 printk ("Free map:\n");
280 if (!bitmap_init (&free_map, disk_size (filesys_disk)))
282 bitmap_read (&free_map, &free_map_file);
283 bitmap_dump (&free_map);
284 bitmap_destroy (&free_map);
287 if (!dir_init (&dir, NUM_DIR_ENTRIES))
289 dir_read (&dir, &root_dir_file);
296 static void must_succeed_function (int, bool) NO_INLINE;
297 #define MUST_SUCCEED(EXPR) must_succeed_function (__LINE__, EXPR)
299 /* Performs basic sanity checks on the filesystem.
300 The filesystem should not contain a file named `foo' when
303 filesys_self_test (void)
305 static const char s[] = "This is a test string.";
309 MUST_SUCCEED (filesys_create ("foo", sizeof s));
310 MUST_SUCCEED (filesys_open ("foo", &file));
311 MUST_SUCCEED (file_write (&file, s, sizeof s) == sizeof s);
312 MUST_SUCCEED (file_tell (&file) == sizeof s);
313 MUST_SUCCEED (file_length (&file) == sizeof s);
316 MUST_SUCCEED (filesys_open ("foo", &file));
317 MUST_SUCCEED (file_read (&file, s2, sizeof s2) == sizeof s2);
318 MUST_SUCCEED (memcmp (s, s2, sizeof s) == 0);
319 MUST_SUCCEED (file_tell (&file) == sizeof s2);
320 MUST_SUCCEED (file_length (&file) == sizeof s2);
323 MUST_SUCCEED (filesys_remove ("foo"));
325 printk ("filesys: self test ok\n");
328 /* Formats the filesystem. */
332 struct bitmap free_map;
333 struct filehdr *map_hdr, *dir_hdr;
336 printk ("Formatting filesystem...");
338 /* Create the initial bitmap and reserve sectors for the
339 free map and root directory file headers. */
340 if (!bitmap_init (&free_map, disk_size (filesys_disk)))
341 PANIC ("bitmap creation failed--disk is too large");
342 bitmap_mark (&free_map, FREE_MAP_SECTOR);
343 bitmap_mark (&free_map, ROOT_DIR_SECTOR);
345 /* Allocate data sector(s) for the free map file
346 and write its file header to disk. */
347 map_hdr = filehdr_allocate (&free_map, bitmap_file_size (&free_map));
349 PANIC ("free map creation failed--disk is too large");
350 filehdr_write (map_hdr, FREE_MAP_SECTOR);
351 filehdr_destroy (map_hdr);
353 /* Allocate data sector(s) for the root directory file
354 and write its file header to disk. */
355 dir_hdr = filehdr_allocate (&free_map, ROOT_DIR_FILE_SIZE);
357 PANIC ("root directory creation failed");
358 filehdr_write (dir_hdr, ROOT_DIR_SECTOR);
359 filehdr_destroy (dir_hdr);
361 /* Write out the free map now that we have space reserved
363 if (!file_open (&free_map_file, FREE_MAP_SECTOR))
364 PANIC ("can't open free map file");
365 bitmap_write (&free_map, &free_map_file);
366 bitmap_destroy (&free_map);
367 file_close (&free_map_file);
369 /* Write out the root directory in the same way. */
370 if (!file_open (&root_dir_file, ROOT_DIR_SECTOR))
371 PANIC ("can't open root directory");
372 if (!dir_init (&dir, NUM_DIR_ENTRIES))
373 PANIC ("can't initialize root directory");
374 dir_write (&dir, &root_dir_file);
376 file_close (&free_map_file);
381 /* If SUCCESS is false, panics with an error complaining about
384 must_succeed_function (int line_no, bool success)
387 PANIC ("filesys_self_test: operation failed on line %d", line_no);