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.h"
  30 #include "file.h"
  31 #include "filehdr.h"
  32 #include "directory.h"
  33 #include "devices/disk.h"
  34 #include "lib/bitmap.h"
  35 #include "lib/debug.h"
  36 #include "lib/lib.h"
  37
  38 /* Filesystem.
  39
  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.
  45
  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.
  53
  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.
  59
  60    The filesystem implemented here has the following limitations:
  61
  62      - No synchronization.  Concurrent accesses will interfere
  63        with one another.
  64
  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.
  68
  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.
  73
  74      - No nested subdirectories.
  75
  76      - Filenames limited to 14 characters.
  77
  78      - A system crash mid-operation may corrupt the disk in a way
  79        that cannot be repaired automatically.  No `fsck' tool is
  80        provided in any case.
  81
  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
  86    suffices. */
  87
  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. */
  91
  92 /* Root directory. */
  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)
  96
  97 /* The disk that contains the filesystem. */
  98 struct disk *filesys_disk;
  99
 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;
 103
 104 static void do_format (void);
 105
 106 /* Initializes the filesystem module.
 107    If FORMAT is true, reformats the filesystem. */
 108 void
 109 filesys_init (bool format)
 110 {
 111   filesys_disk = disk_get (0, 1);
 112   if (filesys_disk == NULL)
 113     PANIC ("hd0:1 (hdb) not present, filesystem initialization failed");
 114
 115   if (format)
 116     do_format ();
 117
 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");
 122 }
 123
 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. */
 128 bool
 129 filesys_create (const char *name, off_t initial_size)
 130 {
 131   struct dir dir;
 132   struct bitmap free_map;
 133   disk_sector_t hdr_sector;
 134   struct filehdr *filehdr;
 135   bool success = false;
 136
 137   /* Read the root directory. */
 138   if (!dir_init (&dir, NUM_DIR_ENTRIES))
 139     return false;
 140   dir_read (&dir, &root_dir_file);
 141   if (dir_lookup (&dir, name, NULL))
 142     goto exit1;
 143
 144   /* Allocate a block for the file header. */
 145   if (!bitmap_init (&free_map, disk_size (filesys_disk)))
 146     goto exit1;
 147   bitmap_read (&free_map, &free_map_file);
 148   hdr_sector = bitmap_find_and_set (&free_map);
 149   if (hdr_sector == BITMAP_ERROR)
 150     goto exit2;
 151
 152   /* Add the file to the directory. */
 153   if (!dir_add (&dir, name, hdr_sector))
 154     goto exit2;
 155
 156   /* Allocate space for the file. */
 157   filehdr = filehdr_allocate (&free_map, initial_size);
 158   if (filehdr == NULL)
 159     goto exit2;
 160
 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);
 165
 166   success = true;
 167
 168   /* Clean up. */
 169   filehdr_destroy (filehdr);
 170  exit2:
 171   bitmap_destroy (&free_map);
 172  exit1:
 173   dir_destroy (&dir);
 174
 175   return success;
 176 }
 177
 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. */
 183 bool
 184 filesys_open (const char *name, struct file *file)
 185 {
 186   struct dir dir;
 187   disk_sector_t hdr_sector;
 188   bool success = false;
 189
 190   if (!dir_init (&dir, NUM_DIR_ENTRIES))
 191     return false;
 192   dir_read (&dir, &root_dir_file);
 193   if (dir_lookup (&dir, name, &hdr_sector))
 194     success = file_open (file, hdr_sector);
 195
 196   dir_destroy (&dir);
 197   return success;
 198 }
 199
 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. */
 204 bool
 205 filesys_remove (const char *name)
 206 {
 207   struct dir dir;
 208   disk_sector_t hdr_sector;
 209   struct filehdr *filehdr;
 210   struct bitmap free_map;
 211   bool success = false;
 212
 213   /* Read the root directory. */
 214   if (!dir_init (&dir, NUM_DIR_ENTRIES))
 215     return false;
 216   dir_read (&dir, &root_dir_file);
 217   if (!dir_lookup (&dir, name, &hdr_sector))
 218     goto exit1;
 219
 220   /* Read the file header. */
 221   filehdr = filehdr_read (hdr_sector);
 222   if (filehdr == NULL)
 223     goto exit1;
 224
 225   /* Allocate a block for the file header. */
 226   if (!bitmap_init (&free_map, disk_size (filesys_disk)))
 227     goto exit2;
 228   bitmap_read (&free_map, &free_map_file);
 229
 230   /* Deallocate. */
 231   filehdr_deallocate (filehdr, &free_map);
 232   bitmap_reset (&free_map, hdr_sector);
 233   dir_remove (&dir, name);
 234
 235   /* Write everything back. */
 236   bitmap_write (&free_map, &free_map_file);
 237   dir_write (&dir, &root_dir_file);
 238
 239   success = true;
 240
 241   /* Clean up. */
 242   bitmap_destroy (&free_map);
 243  exit2:
 244   filehdr_destroy (filehdr);
 245  exit1:
 246   dir_destroy (&dir);
 247
 248   return success;
 249 }
 250
 251 /* Prints a list of files in the filesystem to the system
 252    console.
 253    Returns true if successful, false on failure,
 254    which occurs only if an internal memory allocation fails. */
 255 bool
 256 filesys_list (void)
 257 {
 258   struct dir dir;
 259
 260   if (!dir_init (&dir, NUM_DIR_ENTRIES))
 261     return false;
 262   dir_read (&dir, &root_dir_file);
 263   dir_list (&dir);
 264   dir_destroy (&dir);
 265
 266   return true;
 267 }
 268
 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. */
 273 bool
 274 filesys_dump (void)
 275 {
 276   struct bitmap free_map;
 277   struct dir dir;
 278
 279   printk ("Free map:\n");
 280   if (!bitmap_init (&free_map, disk_size (filesys_disk)))
 281     return false;
 282   bitmap_read (&free_map, &free_map_file);
 283   bitmap_dump (&free_map);
 284   bitmap_destroy (&free_map);
 285   printk ("\n");
 286
 287   if (!dir_init (&dir, NUM_DIR_ENTRIES))
 288     return false;
 289   dir_read (&dir, &root_dir_file);
 290   dir_dump (&dir);
 291   dir_destroy (&dir);
 292
 293   return true;
 294 }
 295
 296 static void must_succeed_function (int, bool) NO_INLINE;
 297 #define MUST_SUCCEED(EXPR) must_succeed_function (__LINE__, EXPR)
 298
 299 /* Performs basic sanity checks on the filesystem.
 300    The filesystem should not contain a file named `foo' when
 301    called. */
 302 void
 303 filesys_self_test (void)
 304 {
 305   static const char s[] = "This is a test string.";
 306   struct file file;
 307   char s2[sizeof s];
 308
 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);
 314   file_close (&file);
 315
 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);
 321   file_close (&file);
 322
 323   MUST_SUCCEED (filesys_remove ("foo"));
 324
 325   printk ("filesys: self test ok\n");
 326 }
 327 \f
 328 /* Formats the filesystem. */
 329 static void
 330 do_format (void)
 331 {
 332   struct bitmap free_map;
 333   struct filehdr *map_hdr, *dir_hdr;
 334   struct dir dir;
 335
 336   printk ("Formatting filesystem...");
 337
 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);
 344
 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));
 348   if (map_hdr == NULL)
 349     PANIC ("free map creation failed--disk is too large");
 350   filehdr_write (map_hdr, FREE_MAP_SECTOR);
 351   filehdr_destroy (map_hdr);
 352
 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);
 356   if (dir_hdr == NULL)
 357     PANIC ("root directory creation failed");
 358   filehdr_write (dir_hdr, ROOT_DIR_SECTOR);
 359   filehdr_destroy (dir_hdr);
 360
 361   /* Write out the free map now that we have space reserved
 362      for it. */
 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);
 368
 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);
 375   dir_destroy (&dir);
 376   file_close (&free_map_file);
 377
 378   printk ("done.\n");
 379 }
 380
 381 /* If SUCCESS is false, panics with an error complaining about
 382    LINE_NO. */
 383 static void
 384 must_succeed_function (int line_no, bool success)
 385 {
 386   if (!success)
 387     PANIC ("filesys_self_test: operation failed on line %d", line_no);
 388 }