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 #include "devices/partition.h"
  39
  40 /* Filesystem.
  41
  42    For the purposes of the "user processes" and "virtual memory"
  43    assignments (projects 2 and 3), please treat all the code in
  44    the filesys directory as a black box.  No changes should be
  45    needed.  For those projects, a single lock external to the
  46    file system code suffices.
  47
  48    The file system consists of a set of files.  Each file has a
  49    header called an `index node' or `inode', represented by
  50    struct inode, that is stored by itself in a single sector (see
  51    inode.h).  The header contains the file's length in bytes and
  52    an array that lists the sector numbers for the file's
  53    contents.
  54
  55    Two files are special.  The first special file is the free
  56    map, whose inode is always stored in sector 0
  57    (FREE_MAP_SECTOR).  The free map stores a bitmap (see
  58    lib/bitmap.h) that contains one bit for each sector on the
  59    disk.  Each bit that corresponds to a sector within a file is
  60    set to true, and the other bits, which are not part of any
  61    file, are set to false.
  62
  63    The second special file is the root directory, whose inode is
  64    always stored in sector 1 (ROOT_DIR_SECTOR).  The root
  65    directory file stores an array of `struct dir_entry' (see
  66    directory.h), each of which, if it is in use, associates a
  67    filename with the sector of the file's inode.
  68
  69    The file system implemented here has the following limitations:
  70
  71      - No synchronization.  Concurrent accesses will interfere
  72        with one another, so external synchronization is needed.
  73
  74      - File size is fixed at creation time.  Because the root
  75        directory is represented as a file, the number of files
  76        that may be created is also limited.
  77
  78      - File data is allocated as a single extent, so that
  79        external fragmentation can become a serious problem as a
  80        file system is used over time.
  81
  82      - No subdirectories.
  83
  84      - Filenames limited to 14 characters.
  85
  86      - A system crash mid-operation may corrupt the disk in a way
  87        that cannot be repaired automatically.  No `fsck' tool is
  88        provided in any case.
  89
  90    However one important feature is included:
  91
  92      - Unix-like semantics for filesys_remove() are implemented.
  93        That is, if a file is open when it is removed, its blocks
  94        are not deallocated and it may still be accessed by the
  95        threads that have it open until the last one closes it. */
  96
  97 /* Sectors of system file inodes. */
  98 #define FREE_MAP_SECTOR 0       /* Free map file inode sector. */
  99 #define ROOT_DIR_SECTOR 1       /* Root directory file inode sector. */
 100
 101 /* Root directory. */
 102 #define NUM_DIR_ENTRIES 10      /* Maximum number of directory entries. */
 103
 104 /* The partition that contains the file system. */
 105 struct partition *filesys_partition;
 106
 107 /* The free map and root directory files.
 108    These files are opened by filesys_init() and never closed. */
 109 struct file *free_map_file, *root_dir_file;
 110
 111 static void do_format (void);
 112
 113 /* Initializes the file system module.
 114    If FORMAT is true, reformats the file system. */
 115 void
 116 filesys_init (bool format)
 117 {
 118   inode_init ();
 119
 120   filesys_partition = partition_get (PARTITION_FILESYS);
 121   if (filesys_partition == NULL)
 122     PANIC ("missing file system partition");
 123
 124   if (format)
 125     do_format ();
 126
 127   free_map_file = file_open (FREE_MAP_SECTOR);
 128   if (free_map_file == NULL)
 129     PANIC ("can't open free map file");
 130   root_dir_file = file_open (ROOT_DIR_SECTOR);
 131   if (root_dir_file == NULL)
 132     PANIC ("can't open root dir file");
 133 }
 134
 135 /* Shuts down the file system module, writing any unwritten data
 136    to disk.
 137    Currently there's nothing to do.  You'll need to add code here
 138    when you implement write-behind caching. */
 139 void
 140 filesys_done (void)
 141 {
 142 }
 143
 144 /* Creates a file named NAME with the given INITIAL_SIZE.
 145    Returns true if successful, false otherwise.
 146    Fails if a file named NAME already exists,
 147    or if internal memory allocation fails. */
 148 bool
 149 filesys_create (const char *name, off_t initial_size)
 150 {
 151   struct dir *dir = NULL;
 152   struct bitmap *free_map = 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 (partition_size (filesys_partition));
 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   if (!inode_create (free_map, inode_sector, initial_size))
 179     goto done;
 180
 181   /* Write everything back. */
 182   dir_write (dir, root_dir_file);
 183   bitmap_write (free_map, free_map_file);
 184
 185   success = true;
 186
 187   /* Clean up. */
 188  done:
 189   bitmap_destroy (free_map);
 190   dir_destroy (dir);
 191
 192   return success;
 193 }
 194
 195 /* Opens a file named NAME and initializes FILE for usage with
 196    the file_*() functions declared in file.h.
 197    Returns the new file if successful or a null pointer
 198    otherwise.
 199    Fails if no file named NAME exists,
 200    or if an internal memory allocation fails. */
 201 struct file *
 202 filesys_open (const char *name)
 203 {
 204   struct dir *dir = NULL;
 205   struct file *file = NULL;
 206   disk_sector_t inode_sector;
 207
 208   dir = dir_create (NUM_DIR_ENTRIES);
 209   if (dir == NULL)
 210     goto done;
 211
 212   dir_read (dir, root_dir_file);
 213   if (dir_lookup (dir, name, &inode_sector))
 214     file = file_open (inode_sector);
 215
 216  done:
 217   dir_destroy (dir);
 218
 219   return file;
 220 }
 221
 222 /* Deletes the file named NAME.
 223    Returns true if successful, false on failure.
 224    Fails if no file named NAME exists,
 225    or if an internal memory allocation fails. */
 226 bool
 227 filesys_remove (const char *name)
 228 {
 229   struct dir *dir = NULL;
 230   struct inode *inode;
 231   disk_sector_t inode_sector;
 232   bool success = false;
 233
 234   /* Read the root directory. */
 235   dir = dir_create (NUM_DIR_ENTRIES);
 236   if (dir == NULL)
 237     goto done;
 238   dir_read (dir, root_dir_file);
 239   if (!dir_lookup (dir, name, &inode_sector))
 240     goto done;
 241
 242   /* Open the inode and delete it. */
 243   inode = inode_open (inode_sector);
 244   if (inode == NULL)
 245     goto done;
 246   inode_remove (inode);
 247   inode_close (inode);
 248
 249   /* Remove file from root directory and write directory back to
 250      disk. */
 251   dir_remove (dir, name);
 252   dir_write (dir, root_dir_file);
 253
 254   success = true;
 255
 256   /* Clean up. */
 257  done:
 258   dir_destroy (dir);
 259
 260   return success;
 261 }
 262
 263 /* Prints a list of files in the file system to the system
 264    console.
 265    Returns true if successful, false on failure,
 266    which occurs only if an internal memory allocation fails. */
 267 bool
 268 filesys_list (void)
 269 {
 270   struct dir *dir = dir_create (NUM_DIR_ENTRIES);
 271   if (dir == NULL)
 272     return false;
 273   dir_read (dir, root_dir_file);
 274   dir_list (dir);
 275   dir_destroy (dir);
 276
 277   return true;
 278 }
 279
 280 /* Dumps the file system state to the system console,
 281    including the free map, the list of files, and file contents.
 282    Returns true if successful, false on failure,
 283    which occurs only if an internal memory allocation fails. */
 284 bool
 285 filesys_dump (void)
 286 {
 287   struct bitmap *free_map;
 288   struct dir *dir;
 289
 290   printf ("Free map:\n");
 291   free_map = bitmap_create (partition_size (filesys_partition));
 292   if (free_map == NULL)
 293     return false;
 294   bitmap_read (free_map, free_map_file);
 295   bitmap_dump (free_map);
 296   bitmap_destroy (free_map);
 297   printf ("\n");
 298
 299   dir = dir_create (NUM_DIR_ENTRIES);
 300   if (dir == NULL)
 301     return false;
 302   dir_read (dir, root_dir_file);
 303   dir_dump (dir);
 304   dir_destroy (dir);
 305
 306   return true;
 307 }
 308
 309 static void must_succeed_function (int, bool) NO_INLINE;
 310 #define MUST_SUCCEED(EXPR) must_succeed_function (__LINE__, EXPR)
 311
 312 /* Performs basic sanity checks on the file system.
 313    The file system should not contain a file named `foo' when
 314    called. */
 315 void
 316 filesys_self_test (void)
 317 {
 318   static const char s[] = "This is a test string.";
 319   static const char zeros[sizeof s] = {0};
 320   struct file *file;
 321   char s2[sizeof s];
 322   int i;
 323
 324   filesys_remove ("foo");
 325   for (i = 0; i < 2; i++)
 326     {
 327       /* Create file and check that it contains zeros
 328          throughout the created length. */
 329       MUST_SUCCEED (filesys_create ("foo", sizeof s));
 330       MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
 331       MUST_SUCCEED (file_read (file, s2, sizeof s2) == sizeof s2);
 332       MUST_SUCCEED (memcmp (s2, zeros, sizeof s) == 0);
 333       MUST_SUCCEED (file_tell (file) == sizeof s);
 334       MUST_SUCCEED (file_length (file) == sizeof s);
 335       file_close (file);
 336
 337       /* Reopen file and write to it. */
 338       MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
 339       MUST_SUCCEED (file_write (file, s, sizeof s) == sizeof s);
 340       MUST_SUCCEED (file_tell (file) == sizeof s);
 341       MUST_SUCCEED (file_length (file) == sizeof s);
 342       file_close (file);
 343
 344       /* Reopen file and verify that it reads back correctly.
 345          Delete file while open to check proper semantics. */
 346       MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
 347       MUST_SUCCEED (filesys_remove ("foo"));
 348       MUST_SUCCEED (filesys_open ("foo") == NULL);
 349       MUST_SUCCEED (file_read (file, s2, sizeof s) == sizeof s);
 350       MUST_SUCCEED (memcmp (s, s2, sizeof s) == 0);
 351       MUST_SUCCEED (file_tell (file) == sizeof s);
 352       MUST_SUCCEED (file_length (file) == sizeof s);
 353       file_close (file);
 354     }
 355
 356   printf ("filesys: self test ok\n");
 357 }
 358 \f
 359 /* Formats the file system. */
 360 static void
 361 do_format (void)
 362 {
 363   struct bitmap *free_map;
 364   struct dir *dir;
 365
 366   printf ("Formatting file system...");
 367
 368   /* Create the initial bitmap and reserve sectors for the
 369      free map and root directory inodes. */
 370   free_map = bitmap_create (partition_size (filesys_partition));
 371   if (free_map == NULL)
 372     PANIC ("bitmap creation failed--file system partition is too large");
 373   bitmap_mark (free_map, FREE_MAP_SECTOR);
 374   bitmap_mark (free_map, ROOT_DIR_SECTOR);
 375
 376   /* Allocate free map and root dir files. */
 377   if (!inode_create (free_map, FREE_MAP_SECTOR, bitmap_file_size (free_map)))
 378     PANIC ("free map creation failed--file system partition is too large");
 379   if (!inode_create (free_map, ROOT_DIR_SECTOR, dir_size (NUM_DIR_ENTRIES)))
 380     PANIC ("root directory creation failed");
 381
 382   /* Write out the free map now that we have space reserved
 383      for it. */
 384   free_map_file = file_open (FREE_MAP_SECTOR);
 385   if (free_map_file == NULL)
 386     PANIC ("can't open free map file");
 387   bitmap_write (free_map, free_map_file);
 388   bitmap_destroy (free_map);
 389   file_close (free_map_file);
 390
 391   /* Write out the root directory in the same way. */
 392   root_dir_file = file_open (ROOT_DIR_SECTOR);
 393   if (root_dir_file == NULL)
 394     PANIC ("can't open root directory");
 395   dir = dir_create (NUM_DIR_ENTRIES);
 396   if (dir == NULL)
 397     PANIC ("can't initialize root directory");
 398   dir_write (dir, root_dir_file);
 399   dir_destroy (dir);
 400   file_close (root_dir_file);
 401
 402   printf ("done.\n");
 403 }
 404
 405 /* If SUCCESS is false, panics with an error complaining about
 406    LINE_NO. */
 407 static void
 408 must_succeed_function (int line_no, bool success)
 409 {
 410   if (!success)
 411     PANIC ("filesys_self_test: operation failed on line %d", line_no);
 412 }