pintos-os.org Git - pintos-anon/blob - src/filesys/filesys.c

   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. */
   4
   5 /* Copyright (c) 1992-1996 The Regents of the University of California.
   6    All rights reserved.
   7
   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.
  13
  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.
  19
  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
  26    MODIFICATIONS.
  27 */
  28
  29 #include "filesys/filesys.h"
  30 #include <bitmap.h>
  31 #include <debug.h>
  32 #include <stdio.h>
  33 #include <string.h>
  34 #include "filesys/file.h"
  35 #include "filesys/filehdr.h"
  36 #include "filesys/directory.h"
  37 #include "devices/disk.h"
  38
  39 /* Filesystem.
  40
  41    The filesystem consists of a set of files.  Each file has a
  42    header, represented by struct filehdr, that is stored by
  43    itself in a single sector (see filehdr.h).  The header
  44    contains the file's length in bytes and an array that lists
  45    the sector numbers for the file's contents.
  46
  47    Two files are special.  The first special file is the free
  48    map, whose header is always stored in sector 0
  49    (FREE_MAP_SECTOR).  The free map stores a bitmap (see
  50    lib/bitmap.h) that contains one bit for each sector on the
  51    disk.  Each bit that corresponds to a sector within a file is
  52    set to true, and the other bits, which are not part of any
  53    file, are set to false.
  54
  55    The second special file is the root directory, whose header is
  56    always stored in sector 1 (ROOT_DIR_SECTOR).  The root
  57    directory file stores an array of `struct dir_entry' (see
  58    directory.h), each of which, if it is in use, associates a
  59    filename with the sector of the file's header.
  60
  61    The filesystem implemented here has the following limitations:
  62
  63      - No synchronization.  Concurrent accesses will interfere
  64        with one another.
  65
  66      - File size is fixed at creation time.  Because the root
  67        directory is represented as a file, the number of files
  68        that may be created is also limited.
  69
  70      - No indirect blocks.  This limits maximum file size to the
  71        number of sector pointers that fit in a single sector
  72        times the size of a sector, or 126 * 512 == 63 kB given
  73        32-bit sizes and 512-byte sectors.
  74
  75      - No nested subdirectories.
  76
  77      - Filenames limited to 14 characters.
  78
  79      - A system crash mid-operation may corrupt the disk in a way
  80        that cannot be repaired automatically.  No `fsck' tool is
  81        provided in any case.
  82
  83    Note: for the purposes of the "user processes" assignment
  84    (project 2), please treat all the code in the filesys
  85    directory as a black box.  No changes should be needed.  For
  86    that project, a single lock external to the filesystem code
  87    suffices. */
  88
  89 /* File header sectors for system files. */
  90 #define FREE_MAP_SECTOR 0       /* Free map file header sector. */
  91 #define ROOT_DIR_SECTOR 1       /* Root directory file header sector. */
  92
  93 /* Root directory. */
  94 #define NUM_DIR_ENTRIES 10      /* Maximum number of directory entries. */
  95 #define ROOT_DIR_FILE_SIZE      /* Root directory file size in bytes. */ \
  96          (sizeof (struct dir_entry) * NUM_DIR_ENTRIES)
  97
  98 /* The disk that contains the filesystem. */
  99 struct disk *filesys_disk;
 100
 101 /* The free map and root directory files.
 102    These files are opened by filesys_init() and never closed. */
 103 static struct file free_map_file, root_dir_file;
 104
 105 static void do_format (void);
 106
 107 /* Initializes the filesystem module.
 108    If FORMAT is true, reformats the filesystem. */
 109 void
 110 filesys_init (bool format)
 111 {
 112   filesys_disk = disk_get (0, 1);
 113   if (filesys_disk == NULL)
 114     PANIC ("hd0:1 (hdb) not present, filesystem initialization failed");
 115
 116   if (format)
 117     do_format ();
 118
 119   if (!file_open (&free_map_file, FREE_MAP_SECTOR))
 120     PANIC ("can't open free map file");
 121   if (!file_open (&root_dir_file, ROOT_DIR_SECTOR))
 122     PANIC ("can't open root dir file");
 123 }
 124
 125 /* Creates a file named NAME with the given INITIAL_SIZE.
 126    Returns true if successful, false otherwise.
 127    Fails if a file named NAME already exists,
 128    or if internal memory allocation fails. */
 129 bool
 130 filesys_create (const char *name, off_t initial_size)
 131 {
 132   struct dir dir;
 133   struct bitmap free_map;
 134   disk_sector_t hdr_sector;
 135   struct filehdr *filehdr;
 136   bool success = false;
 137
 138   /* Read the root directory. */
 139   if (!dir_init (&dir, NUM_DIR_ENTRIES))
 140     return false;
 141   dir_read (&dir, &root_dir_file);
 142   if (dir_lookup (&dir, name, NULL))
 143     goto exit1;
 144
 145   /* Allocate a block for the file header. */
 146   if (!bitmap_init (&free_map, disk_size (filesys_disk)))
 147     goto exit1;
 148   bitmap_read (&free_map, &free_map_file);
 149   hdr_sector = bitmap_find_and_set (&free_map);
 150   if (hdr_sector == BITMAP_ERROR)
 151     goto exit2;
 152
 153   /* Add the file to the directory. */
 154   if (!dir_add (&dir, name, hdr_sector))
 155     goto exit2;
 156
 157   /* Allocate space for the file. */
 158   filehdr = filehdr_allocate (&free_map, initial_size);
 159   if (filehdr == NULL)
 160     goto exit2;
 161
 162   /* Write everything back. */
 163   filehdr_write (filehdr, hdr_sector);
 164   dir_write (&dir, &root_dir_file);
 165   bitmap_write (&free_map, &free_map_file);
 166
 167   success = true;
 168
 169   /* Clean up. */
 170   filehdr_destroy (filehdr);
 171  exit2:
 172   bitmap_destroy (&free_map);
 173  exit1:
 174   dir_destroy (&dir);
 175
 176   return success;
 177 }
 178
 179 /* Opens a file named NAME and initializes FILE for usage with
 180    the file_*() functions declared in file.h.
 181    Returns true if successful, false on failure.
 182    Fails if no file named NAME exists,
 183    or if an internal memory allocation fails. */
 184 bool
 185 filesys_open (const char *name, struct file *file)
 186 {
 187   struct dir dir;
 188   disk_sector_t hdr_sector;
 189   bool success = false;
 190
 191   if (!dir_init (&dir, NUM_DIR_ENTRIES))
 192     return false;
 193   dir_read (&dir, &root_dir_file);
 194   if (dir_lookup (&dir, name, &hdr_sector))
 195     success = file_open (file, hdr_sector);
 196
 197   dir_destroy (&dir);
 198   return success;
 199 }
 200
 201 /* Deletes the file named NAME.
 202    Returns true if successful, false on failure.
 203    Fails if no file named NAME exists,
 204    or if an internal memory allocation fails. */
 205 bool
 206 filesys_remove (const char *name)
 207 {
 208   struct dir dir;
 209   disk_sector_t hdr_sector;
 210   struct filehdr *filehdr;
 211   struct bitmap free_map;
 212   bool success = false;
 213
 214   /* Read the root directory. */
 215   if (!dir_init (&dir, NUM_DIR_ENTRIES))
 216     return false;
 217   dir_read (&dir, &root_dir_file);
 218   if (!dir_lookup (&dir, name, &hdr_sector))
 219     goto exit1;
 220
 221   /* Read the file header. */
 222   filehdr = filehdr_read (hdr_sector);
 223   if (filehdr == NULL)
 224     goto exit1;
 225
 226   /* Allocate a block for the file header. */
 227   if (!bitmap_init (&free_map, disk_size (filesys_disk)))
 228     goto exit2;
 229   bitmap_read (&free_map, &free_map_file);
 230
 231   /* Deallocate. */
 232   filehdr_deallocate (filehdr, &free_map);
 233   bitmap_reset (&free_map, hdr_sector);
 234   dir_remove (&dir, name);
 235
 236   /* Write everything back. */
 237   bitmap_write (&free_map, &free_map_file);
 238   dir_write (&dir, &root_dir_file);
 239
 240   success = true;
 241
 242   /* Clean up. */
 243   bitmap_destroy (&free_map);
 244  exit2:
 245   filehdr_destroy (filehdr);
 246  exit1:
 247   dir_destroy (&dir);
 248
 249   return success;
 250 }
 251
 252 /* Prints a list of files in the filesystem to the system
 253    console.
 254    Returns true if successful, false on failure,
 255    which occurs only if an internal memory allocation fails. */
 256 bool
 257 filesys_list (void)
 258 {
 259   struct dir dir;
 260
 261   if (!dir_init (&dir, NUM_DIR_ENTRIES))
 262     return false;
 263   dir_read (&dir, &root_dir_file);
 264   dir_list (&dir);
 265   dir_destroy (&dir);
 266
 267   return true;
 268 }
 269
 270 /* Dumps the filesystem state to the system console,
 271    including the free map, the list of files, and file contents.
 272    Returns true if successful, false on failure,
 273    which occurs only if an internal memory allocation fails. */
 274 bool
 275 filesys_dump (void)
 276 {
 277   struct bitmap free_map;
 278   struct dir dir;
 279
 280   printf ("Free map:\n");
 281   if (!bitmap_init (&free_map, disk_size (filesys_disk)))
 282     return false;
 283   bitmap_read (&free_map, &free_map_file);
 284   bitmap_dump (&free_map);
 285   bitmap_destroy (&free_map);
 286   printf ("\n");
 287
 288   if (!dir_init (&dir, NUM_DIR_ENTRIES))
 289     return false;
 290   dir_read (&dir, &root_dir_file);
 291   dir_dump (&dir);
 292   dir_destroy (&dir);
 293
 294   return true;
 295 }
 296
 297 static void must_succeed_function (int, bool) NO_INLINE;
 298 #define MUST_SUCCEED(EXPR) must_succeed_function (__LINE__, EXPR)
 299
 300 /* Performs basic sanity checks on the filesystem.
 301    The filesystem should not contain a file named `foo' when
 302    called. */
 303 void
 304 filesys_self_test (void)
 305 {
 306   static const char s[] = "This is a test string.";
 307   struct file file;
 308   char s2[sizeof s];
 309
 310   MUST_SUCCEED (filesys_create ("foo", sizeof s));
 311   MUST_SUCCEED (filesys_open ("foo", &file));
 312   MUST_SUCCEED (file_write (&file, s, sizeof s) == sizeof s);
 313   MUST_SUCCEED (file_tell (&file) == sizeof s);
 314   MUST_SUCCEED (file_length (&file) == sizeof s);
 315   file_close (&file);
 316
 317   MUST_SUCCEED (filesys_open ("foo", &file));
 318   MUST_SUCCEED (file_read (&file, s2, sizeof s2) == sizeof s2);
 319   MUST_SUCCEED (memcmp (s, s2, sizeof s) == 0);
 320   MUST_SUCCEED (file_tell (&file) == sizeof s2);
 321   MUST_SUCCEED (file_length (&file) == sizeof s2);
 322   file_close (&file);
 323
 324   MUST_SUCCEED (filesys_remove ("foo"));
 325
 326   printf ("filesys: self test ok\n");
 327 }
 328 \f
 329 /* Formats the filesystem. */
 330 static void
 331 do_format (void)
 332 {
 333   struct bitmap free_map;
 334   struct filehdr *map_hdr, *dir_hdr;
 335   struct dir dir;
 336
 337   printf ("Formatting filesystem...");
 338
 339   /* Create the initial bitmap and reserve sectors for the
 340      free map and root directory file headers. */
 341   if (!bitmap_init (&free_map, disk_size (filesys_disk)))
 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);
 345
 346   /* Allocate data sector(s) for the free map file
 347      and write its file header to disk. */
 348   map_hdr = filehdr_allocate (&free_map, bitmap_file_size (&free_map));
 349   if (map_hdr == NULL)
 350     PANIC ("free map creation failed--disk is too large");
 351   filehdr_write (map_hdr, FREE_MAP_SECTOR);
 352   filehdr_destroy (map_hdr);
 353
 354   /* Allocate data sector(s) for the root directory file
 355      and write its file header to disk. */
 356   dir_hdr = filehdr_allocate (&free_map, ROOT_DIR_FILE_SIZE);
 357   if (dir_hdr == NULL)
 358     PANIC ("root directory creation failed");
 359   filehdr_write (dir_hdr, ROOT_DIR_SECTOR);
 360   filehdr_destroy (dir_hdr);
 361
 362   /* Write out the free map now that we have space reserved
 363      for it. */
 364   if (!file_open (&free_map_file, FREE_MAP_SECTOR))
 365     PANIC ("can't open free map file");
 366   bitmap_write (&free_map, &free_map_file);
 367   bitmap_destroy (&free_map);
 368   file_close (&free_map_file);
 369
 370   /* Write out the root directory in the same way. */
 371   if (!file_open (&root_dir_file, ROOT_DIR_SECTOR))
 372     PANIC ("can't open root directory");
 373   if (!dir_init (&dir, NUM_DIR_ENTRIES))
 374     PANIC ("can't initialize root directory");
 375   dir_write (&dir, &root_dir_file);
 376   dir_destroy (&dir);
 377   file_close (&free_map_file);
 378
 379   printf ("done.\n");
 380 }
 381
 382 /* If SUCCESS is false, panics with an error complaining about
 383    LINE_NO. */
 384 static void
 385 must_succeed_function (int line_no, bool success)
 386 {
 387   if (!success)
 388     PANIC ("filesys_self_test: operation failed on line %d", line_no);
 389 }