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   disk_sector_t inode_sector;
 153   bool success = false;
 154
 155   /* Read the root directory. */
 156   dir = dir_create (NUM_DIR_ENTRIES);
 157   if (dir == NULL)
 158     goto done;
 159   dir_read (dir, root_dir_file);
 160   if (dir_lookup (dir, name, NULL))
 161     goto done;
 162
 163   /* Allocate a block for the inode. */
 164   free_map = bitmap_create (disk_size (filesys_disk));
 165   if (free_map == NULL)
 166     goto done;
 167   bitmap_read (free_map, free_map_file);
 168   inode_sector = bitmap_scan_and_flip (free_map, 0, 1, false);
 169   if (inode_sector == BITMAP_ERROR)
 170     goto done;
 171
 172   /* Add the file to the directory. */
 173   if (!dir_add (dir, name, inode_sector))
 174     goto done;
 175
 176   /* Allocate space for the file. */
 177   if (!inode_create (free_map, inode_sector, initial_size))
 178     goto done;
 179
 180   /* Write everything back. */
 181   dir_write (dir, root_dir_file);
 182   bitmap_write (free_map, free_map_file);
 183
 184   success = true;
 185
 186   /* Clean up. */
 187  done:
 188   bitmap_destroy (free_map);
 189   dir_destroy (dir);
 190
 191   return success;
 192 }
 193
 194 /* Opens a file named NAME and initializes FILE for usage with
 195    the file_*() functions declared in file.h.
 196    Returns the new file if successful or a null pointer
 197    otherwise.
 198    Fails if no file named NAME exists,
 199    or if an internal memory allocation fails. */
 200 struct file *
 201 filesys_open (const char *name)
 202 {
 203   struct dir *dir = NULL;
 204   struct file *file = NULL;
 205   disk_sector_t inode_sector;
 206
 207   dir = dir_create (NUM_DIR_ENTRIES);
 208   if (dir == NULL)
 209     goto done;
 210
 211   dir_read (dir, root_dir_file);
 212   if (dir_lookup (dir, name, &inode_sector))
 213     file = file_open (inode_sector);
 214
 215  done:
 216   dir_destroy (dir);
 217
 218   return file;
 219 }
 220
 221 /* Deletes the file named NAME.
 222    Returns true if successful, false on failure.
 223    Fails if no file named NAME exists,
 224    or if an internal memory allocation fails. */
 225 bool
 226 filesys_remove (const char *name)
 227 {
 228   struct dir *dir = NULL;
 229   struct inode *inode;
 230   disk_sector_t inode_sector;
 231   bool success = false;
 232
 233   /* Read the root directory. */
 234   dir = dir_create (NUM_DIR_ENTRIES);
 235   if (dir == NULL)
 236     goto done;
 237   dir_read (dir, root_dir_file);
 238   if (!dir_lookup (dir, name, &inode_sector))
 239     goto done;
 240
 241   /* Open the inode and delete it. */
 242   inode = inode_open (inode_sector);
 243   if (inode == NULL)
 244     goto done;
 245   inode_remove (inode);
 246   inode_close (inode);
 247
 248   /* Remove file from root directory and write directory back to
 249      disk. */
 250   dir_remove (dir, name);
 251   dir_write (dir, root_dir_file);
 252
 253   success = true;
 254
 255   /* Clean up. */
 256  done:
 257   dir_destroy (dir);
 258
 259   return success;
 260 }
 261
 262 /* Prints a list of files in the filesystem to the system
 263    console.
 264    Returns true if successful, false on failure,
 265    which occurs only if an internal memory allocation fails. */
 266 bool
 267 filesys_list (void)
 268 {
 269   struct dir *dir = dir_create (NUM_DIR_ENTRIES);
 270   if (dir == NULL)
 271     return false;
 272   dir_read (dir, root_dir_file);
 273   dir_list (dir);
 274   dir_destroy (dir);
 275
 276   return true;
 277 }
 278
 279 static void must_succeed_function (int, bool) NO_INLINE;
 280 #define MUST_SUCCEED(EXPR) must_succeed_function (__LINE__, EXPR)
 281
 282 /* Performs basic sanity checks on the filesystem.
 283    The filesystem should not contain a file named `foo' when
 284    called. */
 285 void
 286 filesys_self_test (void)
 287 {
 288   static const char s[] = "This is a test string.";
 289   static const char zeros[sizeof s] = {0};
 290   struct file *file;
 291   char s2[sizeof s];
 292   int i;
 293
 294   filesys_remove ("foo");
 295   for (i = 0; i < 2; i++)
 296     {
 297       /* Create file and check that it contains zeros
 298          throughout the created length. */
 299       MUST_SUCCEED (filesys_create ("foo", sizeof s));
 300       MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
 301       MUST_SUCCEED (file_read (file, s2, sizeof s2) == sizeof s2);
 302       MUST_SUCCEED (memcmp (s2, zeros, sizeof s) == 0);
 303       MUST_SUCCEED (file_tell (file) == sizeof s);
 304       MUST_SUCCEED (file_length (file) == sizeof s);
 305       file_close (file);
 306
 307       /* Reopen file and write to it. */
 308       MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
 309       MUST_SUCCEED (file_write (file, s, sizeof s) == sizeof s);
 310       MUST_SUCCEED (file_tell (file) == sizeof s);
 311       MUST_SUCCEED (file_length (file) == sizeof s);
 312       file_close (file);
 313
 314       /* Reopen file and verify that it reads back correctly.
 315          Delete file while open to check proper semantics. */
 316       MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
 317       MUST_SUCCEED (filesys_remove ("foo"));
 318       MUST_SUCCEED (filesys_open ("foo") == NULL);
 319       MUST_SUCCEED (file_read (file, s2, sizeof s) == sizeof s);
 320       MUST_SUCCEED (memcmp (s, s2, sizeof s) == 0);
 321       MUST_SUCCEED (file_tell (file) == sizeof s);
 322       MUST_SUCCEED (file_length (file) == sizeof s);
 323       file_close (file);
 324     }
 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 dir *dir;
 335
 336   printf ("Formatting filesystem...");
 337
 338   /* Create the initial bitmap and reserve sectors for the
 339      free map and root directory inodes. */
 340   free_map = bitmap_create (disk_size (filesys_disk));
 341   if (free_map == NULL)
 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 free map and root dir files. */
 347   if (!inode_create (free_map, FREE_MAP_SECTOR, bitmap_file_size (free_map)))
 348     PANIC ("free map creation failed--disk is too large");
 349   if (!inode_create (free_map, ROOT_DIR_SECTOR, dir_size (NUM_DIR_ENTRIES)))
 350     PANIC ("root directory creation failed");
 351
 352   /* Write out the free map now that we have space reserved
 353      for it. */
 354   free_map_file = file_open (FREE_MAP_SECTOR);
 355   if (free_map_file == NULL)
 356     PANIC ("can't open free map file");
 357   bitmap_write (free_map, free_map_file);
 358   bitmap_destroy (free_map);
 359   file_close (free_map_file);
 360
 361   /* Write out the root directory in the same way. */
 362   root_dir_file = file_open (ROOT_DIR_SECTOR);
 363   if (root_dir_file == NULL)
 364     PANIC ("can't open root directory");
 365   dir = dir_create (NUM_DIR_ENTRIES);
 366   if (dir == NULL)
 367     PANIC ("can't initialize root directory");
 368   dir_write (dir, root_dir_file);
 369   dir_destroy (dir);
 370   file_close (root_dir_file);
 371
 372   printf ("done.\n");
 373 }
 374
 375 /* If SUCCESS is false, panics with an error complaining about
 376    LINE_NO. */
 377 static void
 378 must_succeed_function (int line_no, bool success)
 379 {
 380   if (!success)
 381     PANIC ("filesys_self_test: operation failed on line %d", line_no);
 382 }