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/inode.h"
  36 #include "filesys/directory.h"
  37 #include "devices/disk.h"
  38
  39 /* Filesystem.
  40
  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.
  46
  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
  52    contents.
  53
  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.
  61
  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.
  67
  68    The filesystem implemented here has the following limitations:
  69
  70      - No synchronization.  Concurrent accesses will interfere
  71        with one another, so external synchronization is needed.
  72
  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.
  76
  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.
  80
  81      - No subdirectories.
  82
  83      - Filenames limited to 14 characters.
  84
  85      - A system crash mid-operation may corrupt the disk in a way
  86        that cannot be repaired automatically.  No `fsck' tool is
  87        provided in any case.
  88
  89    However one important feature is included:
  90
  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. */
  95
  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. */
  99
 100 /* Root directory. */
 101 #define NUM_DIR_ENTRIES 10      /* Maximum number of directory entries. */
 102
 103 /* The disk that contains the filesystem. */
 104 struct disk *filesys_disk;
 105
 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;
 109
 110 static void do_format (void);
 111
 112 /* Initializes the filesystem module.
 113    If FORMAT is true, reformats the filesystem. */
 114 void
 115 filesys_init (bool format)
 116 {
 117   inode_init ();
 118
 119   filesys_disk = disk_get (0, 1);
 120   if (filesys_disk == NULL)
 121     PANIC ("hd0:1 (hdb) not present, filesystem initialization failed");
 122
 123   if (format)
 124     do_format ();
 125
 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");
 132 }
 133
 134 /* Shuts down the filesystem module, writing any unwritten data
 135    to disk.
 136    Currently there's nothing to do.  You'll need to add code here
 137    when you implement write-behind caching. */
 138 void
 139 filesys_done (void)
 140 {
 141 }
 142
 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. */
 147 bool
 148 filesys_create (const char *name, off_t initial_size)
 149 {
 150   struct dir *dir = NULL;
 151   struct bitmap *free_map = NULL;
 152   struct inode *inode = NULL;
 153   disk_sector_t inode_sector;
 154   bool success = false;
 155
 156   /* Read the root directory. */
 157   dir = dir_create (NUM_DIR_ENTRIES);
 158   if (dir == NULL)
 159     goto done;
 160   dir_read (dir, root_dir_file);
 161   if (dir_lookup (dir, name, NULL))
 162     goto done;
 163
 164   /* Allocate a block for the inode. */
 165   free_map = bitmap_create (disk_size (filesys_disk));
 166   if (free_map == NULL)
 167     goto done;
 168   bitmap_read (free_map, free_map_file);
 169   inode_sector = bitmap_scan_and_flip (free_map, 0, 1, false);
 170   if (inode_sector == BITMAP_ERROR)
 171     goto done;
 172
 173   /* Add the file to the directory. */
 174   if (!dir_add (dir, name, inode_sector))
 175     goto done;
 176
 177   /* Allocate space for the file. */
 178   inode = inode_create (free_map, inode_sector, initial_size);
 179   if (inode == NULL)
 180     goto done;
 181
 182   /* Write everything back. */
 183   inode_commit (inode);
 184   dir_write (dir, root_dir_file);
 185   bitmap_write (free_map, free_map_file);
 186
 187   success = true;
 188
 189   /* Clean up. */
 190  done:
 191   inode_close (inode);
 192   bitmap_destroy (free_map);
 193   dir_destroy (dir);
 194
 195   return success;
 196 }
 197
 198 /* Opens a file named NAME and initializes FILE for usage with
 199    the file_*() functions declared in file.h.
 200    Returns the new file if successful or a null pointer
 201    otherwise.
 202    Fails if no file named NAME exists,
 203    or if an internal memory allocation fails. */
 204 struct file *
 205 filesys_open (const char *name)
 206 {
 207   struct dir *dir = NULL;
 208   struct file *file = NULL;
 209   disk_sector_t inode_sector;
 210
 211   dir = dir_create (NUM_DIR_ENTRIES);
 212   if (dir == NULL)
 213     goto done;
 214
 215   dir_read (dir, root_dir_file);
 216   if (dir_lookup (dir, name, &inode_sector))
 217     file = file_open (inode_sector);
 218
 219  done:
 220   dir_destroy (dir);
 221
 222   return file;
 223 }
 224
 225 /* Deletes the file named NAME.
 226    Returns true if successful, false on failure.
 227    Fails if no file named NAME exists,
 228    or if an internal memory allocation fails. */
 229 bool
 230 filesys_remove (const char *name)
 231 {
 232   struct dir *dir = NULL;
 233   struct inode *inode;
 234   disk_sector_t inode_sector;
 235   bool success = false;
 236
 237   /* Read the root directory. */
 238   dir = dir_create (NUM_DIR_ENTRIES);
 239   if (dir == NULL)
 240     goto done;
 241   dir_read (dir, root_dir_file);
 242   if (!dir_lookup (dir, name, &inode_sector))
 243     goto done;
 244
 245   /* Open the inode and delete it. */
 246   inode = inode_open (inode_sector);
 247   if (inode == NULL)
 248     goto done;
 249   inode_remove (inode);
 250   inode_close (inode);
 251
 252   /* Remove file from root directory and write directory back to
 253      disk. */
 254   dir_remove (dir, name);
 255   dir_write (dir, root_dir_file);
 256
 257   success = true;
 258
 259   /* Clean up. */
 260  done:
 261   dir_destroy (dir);
 262
 263   return success;
 264 }
 265
 266 /* Prints a list of files in the filesystem to the system
 267    console.
 268    Returns true if successful, false on failure,
 269    which occurs only if an internal memory allocation fails. */
 270 bool
 271 filesys_list (void)
 272 {
 273   struct dir *dir = dir_create (NUM_DIR_ENTRIES);
 274   if (dir == NULL)
 275     return false;
 276   dir_read (dir, root_dir_file);
 277   dir_list (dir);
 278   dir_destroy (dir);
 279
 280   return true;
 281 }
 282
 283 /* Dumps the filesystem state to the system console,
 284    including the free map, the list of files, and file contents.
 285    Returns true if successful, false on failure,
 286    which occurs only if an internal memory allocation fails. */
 287 bool
 288 filesys_dump (void)
 289 {
 290   struct bitmap *free_map;
 291   struct dir *dir;
 292
 293   printf ("Free map:\n");
 294   free_map = bitmap_create (disk_size (filesys_disk));
 295   if (free_map == NULL)
 296     return false;
 297   bitmap_read (free_map, free_map_file);
 298   bitmap_dump (free_map);
 299   bitmap_destroy (free_map);
 300   printf ("\n");
 301
 302   dir = dir_create (NUM_DIR_ENTRIES);
 303   if (dir == NULL)
 304     return false;
 305   dir_read (dir, root_dir_file);
 306   dir_dump (dir);
 307   dir_destroy (dir);
 308
 309   return true;
 310 }
 311
 312 static void must_succeed_function (int, bool) NO_INLINE;
 313 #define MUST_SUCCEED(EXPR) must_succeed_function (__LINE__, EXPR)
 314
 315 /* Performs basic sanity checks on the filesystem.
 316    The filesystem should not contain a file named `foo' when
 317    called. */
 318 void
 319 filesys_self_test (void)
 320 {
 321   static const char s[] = "This is a test string.";
 322   static const char zeros[sizeof s] = {0};
 323   struct file *file;
 324   char s2[sizeof s];
 325   int i;
 326
 327   filesys_remove ("foo");
 328   for (i = 0; i < 2; i++)
 329     {
 330       /* Create file and check that it contains zeros
 331          throughout the created length. */
 332       MUST_SUCCEED (filesys_create ("foo", sizeof s));
 333       MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
 334       MUST_SUCCEED (file_read (file, s2, sizeof s2) == sizeof s2);
 335       MUST_SUCCEED (memcmp (s2, zeros, sizeof s) == 0);
 336       MUST_SUCCEED (file_tell (file) == sizeof s);
 337       MUST_SUCCEED (file_length (file) == sizeof s);
 338       file_close (file);
 339
 340       /* Reopen file and write to it. */
 341       MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
 342       MUST_SUCCEED (file_write (file, s, sizeof s) == sizeof s);
 343       MUST_SUCCEED (file_tell (file) == sizeof s);
 344       MUST_SUCCEED (file_length (file) == sizeof s);
 345       file_close (file);
 346
 347       /* Reopen file and verify that it reads back correctly.
 348          Delete file while open to check proper semantics. */
 349       MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
 350       MUST_SUCCEED (filesys_remove ("foo"));
 351       MUST_SUCCEED (file_read (file, s2, sizeof s) == sizeof s);
 352       MUST_SUCCEED (memcmp (s, s2, sizeof s) == 0);
 353       MUST_SUCCEED (file_tell (file) == sizeof s);
 354       MUST_SUCCEED (file_length (file) == sizeof s);
 355       file_close (file);
 356
 357       /* Make sure file is deleted. */
 358       MUST_SUCCEED ((file = filesys_open ("foo")) == NULL);
 359     }
 360
 361   printf ("filesys: self test ok\n");
 362 }
 363 \f
 364 /* Formats the filesystem. */
 365 static void
 366 do_format (void)
 367 {
 368   struct bitmap *free_map;
 369   struct inode *map_inode, *dir_inode;
 370   struct dir *dir;
 371
 372   printf ("Formatting filesystem...");
 373
 374   /* Create the initial bitmap and reserve sectors for the
 375      free map and root directory inodes. */
 376   free_map = bitmap_create (disk_size (filesys_disk));
 377   if (free_map == NULL)
 378     PANIC ("bitmap creation failed--disk is too large");
 379   bitmap_mark (free_map, FREE_MAP_SECTOR);
 380   bitmap_mark (free_map, ROOT_DIR_SECTOR);
 381
 382   /* Allocate data sector(s) for the free map file
 383      and write its inode to disk. */
 384   map_inode = inode_create (free_map, FREE_MAP_SECTOR,
 385                             bitmap_file_size (free_map));
 386   if (map_inode == NULL)
 387     PANIC ("free map creation failed--disk is too large");
 388   inode_commit (map_inode);
 389   inode_close (map_inode);
 390
 391   /* Allocate data sector(s) for the root directory file
 392      and write its inodes to disk. */
 393   dir_inode = inode_create (free_map, ROOT_DIR_SECTOR,
 394                             dir_size (NUM_DIR_ENTRIES));
 395   if (dir_inode == NULL)
 396     PANIC ("root directory creation failed");
 397   inode_commit (dir_inode);
 398   inode_close (dir_inode);
 399
 400   /* Write out the free map now that we have space reserved
 401      for it. */
 402   free_map_file = file_open (FREE_MAP_SECTOR);
 403   if (free_map_file == NULL)
 404     PANIC ("can't open free map file");
 405   bitmap_write (free_map, free_map_file);
 406   bitmap_destroy (free_map);
 407   file_close (free_map_file);
 408
 409   /* Write out the root directory in the same way. */
 410   root_dir_file = file_open (ROOT_DIR_SECTOR);
 411   if (root_dir_file == NULL)
 412     PANIC ("can't open root directory");
 413   dir = dir_create (NUM_DIR_ENTRIES);
 414   if (dir == NULL)
 415     PANIC ("can't initialize root directory");
 416   dir_write (dir, root_dir_file);
 417   dir_destroy (dir);
 418   file_close (root_dir_file);
 419
 420   printf ("done.\n");
 421 }
 422
 423 /* If SUCCESS is false, panics with an error complaining about
 424    LINE_NO. */
 425 static void
 426 must_succeed_function (int line_no, bool success)
 427 {
 428   if (!success)
 429     PANIC ("filesys_self_test: operation failed on line %d", line_no);
 430 }