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" assignment (project
  42    2), please treat all the code in the filesys directory as a
  43    black box.  No changes should be needed.  For that project, a
  44    single lock external to the filesystem code suffices.
  45
  46    The filesystem consists of a set of files.  Each file has a
  47    header called an `index node' or `inode', represented by
  48    struct inode, that is stored by itself in a single sector (see
  49    inode.h).  The header contains the file's length in bytes and
  50    an array that lists the sector numbers for the file's
  51    contents.
  52
  53    Two files are special.  The first special file is the free
  54    map, whose inode is always stored in sector 0
  55    (FREE_MAP_SECTOR).  The free map stores a bitmap (see
  56    lib/bitmap.h) that contains one bit for each sector on the
  57    disk.  Each bit that corresponds to a sector within a file is
  58    set to true, and the other bits, which are not part of any
  59    file, are set to false.
  60
  61    The second special file is the root directory, whose inode is
  62    always stored in sector 1 (ROOT_DIR_SECTOR).  The root
  63    directory file stores an array of `struct dir_entry' (see
  64    directory.h), each of which, if it is in use, associates a
  65    filename with the sector of the file's inode.
  66
  67    The filesystem implemented here has the following limitations:
  68
  69      - No synchronization.  Concurrent accesses will interfere
  70        with one another, so external synchronization is needed.
  71
  72      - File size is fixed at creation time.  Because the root
  73        directory is represented as a file, the number of files
  74        that may be created is also limited.
  75
  76      - No indirect blocks.  This limits maximum file size to the
  77        number of sector pointers that fit in a single inode
  78        times the size of a sector, or 126 * 512 == 63 kB given
  79        32-bit sizes and 512-byte sectors.
  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_find_and_set (free_map);
 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 true if successful, false on failure.
 201    Fails if no file named NAME exists,
 202    or if an internal memory allocation fails. */
 203 struct file *
 204 filesys_open (const char *name)
 205 {
 206   struct dir *dir = NULL;
 207   struct file *file = NULL;
 208   disk_sector_t inode_sector;
 209
 210   dir = dir_create (NUM_DIR_ENTRIES);
 211   if (dir == NULL)
 212     goto done;
 213
 214   dir_read (dir, root_dir_file);
 215   if (dir_lookup (dir, name, &inode_sector))
 216     file = file_open (inode_sector);
 217
 218  done:
 219   dir_destroy (dir);
 220
 221   return file;
 222 }
 223
 224 /* Deletes the file named NAME.
 225    Returns true if successful, false on failure.
 226    Fails if no file named NAME exists,
 227    or if an internal memory allocation fails. */
 228 bool
 229 filesys_remove (const char *name)
 230 {
 231   struct dir *dir = NULL;
 232   struct inode *inode;
 233   disk_sector_t inode_sector;
 234   bool success = false;
 235
 236   /* Read the root directory. */
 237   dir = dir_create (NUM_DIR_ENTRIES);
 238   if (dir == NULL)
 239     goto done;
 240   dir_read (dir, root_dir_file);
 241   if (!dir_lookup (dir, name, &inode_sector))
 242     goto done;
 243
 244   /* Open the inode and delete it it. */
 245   inode = inode_open (inode_sector);
 246   if (inode == NULL)
 247     goto done;
 248   inode_remove (inode);
 249   inode_close (inode);
 250
 251   /* Remove file from root directory and write directory back to
 252      disk. */
 253   dir_remove (dir, name);
 254   dir_write (dir, root_dir_file);
 255
 256   success = true;
 257
 258   /* Clean up. */
 259  done:
 260   dir_destroy (dir);
 261
 262   return success;
 263 }
 264
 265 /* Prints a list of files in the filesystem to the system
 266    console.
 267    Returns true if successful, false on failure,
 268    which occurs only if an internal memory allocation fails. */
 269 bool
 270 filesys_list (void)
 271 {
 272   struct dir *dir = dir_create (NUM_DIR_ENTRIES);
 273   if (dir == NULL)
 274     return false;
 275   dir_read (dir, root_dir_file);
 276   dir_list (dir);
 277   dir_destroy (dir);
 278
 279   return true;
 280 }
 281
 282 /* Dumps the filesystem state to the system console,
 283    including the free map, the list of files, and file contents.
 284    Returns true if successful, false on failure,
 285    which occurs only if an internal memory allocation fails. */
 286 bool
 287 filesys_dump (void)
 288 {
 289   struct bitmap *free_map;
 290   struct dir *dir;
 291
 292   printf ("Free map:\n");
 293   free_map = bitmap_create (disk_size (filesys_disk));
 294   if (free_map == NULL)
 295     return false;
 296   bitmap_read (free_map, free_map_file);
 297   bitmap_dump (free_map);
 298   bitmap_destroy (free_map);
 299   printf ("\n");
 300
 301   dir = dir_create (NUM_DIR_ENTRIES);
 302   if (dir == NULL)
 303     return false;
 304   dir_read (dir, root_dir_file);
 305   dir_dump (dir);
 306   dir_destroy (dir);
 307
 308   return true;
 309 }
 310
 311 static void must_succeed_function (int, bool) NO_INLINE;
 312 #define MUST_SUCCEED(EXPR) must_succeed_function (__LINE__, EXPR)
 313
 314 /* Performs basic sanity checks on the filesystem.
 315    The filesystem should not contain a file named `foo' when
 316    called. */
 317 void
 318 filesys_self_test (void)
 319 {
 320   static const char s[] = "This is a test string.";
 321   static const char zeros[sizeof s] = {0};
 322   struct file *file;
 323   char s2[sizeof s];
 324   int i;
 325
 326   filesys_remove ("foo");
 327   for (i = 0; i < 2; i++)
 328     {
 329       /* Create file and check that it contains zeros
 330          throughout the created length. */
 331       MUST_SUCCEED (filesys_create ("foo", sizeof s));
 332       MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
 333       MUST_SUCCEED (file_read (file, s2, sizeof s2) == sizeof s2);
 334       MUST_SUCCEED (memcmp (s2, zeros, sizeof s) == 0);
 335       MUST_SUCCEED (file_tell (file) == sizeof s);
 336       MUST_SUCCEED (file_length (file) == sizeof s);
 337       file_close (file);
 338
 339       /* Reopen file and write to it. */
 340       MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
 341       MUST_SUCCEED (file_write (file, s, sizeof s) == sizeof s);
 342       MUST_SUCCEED (file_tell (file) == sizeof s);
 343       MUST_SUCCEED (file_length (file) == sizeof s);
 344       file_close (file);
 345
 346       /* Reopen file and verify that it reads back correctly.
 347          Delete file while open to check proper semantics. */
 348       MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
 349       MUST_SUCCEED (filesys_remove ("foo"));
 350       MUST_SUCCEED (file_read (file, s2, sizeof s) == sizeof s);
 351       MUST_SUCCEED (memcmp (s, s2, sizeof s) == 0);
 352       MUST_SUCCEED (file_tell (file) == sizeof s);
 353       MUST_SUCCEED (file_length (file) == sizeof s);
 354       file_close (file);
 355
 356       /* Make sure file is deleted. */
 357       MUST_SUCCEED ((file = filesys_open ("foo")) == NULL);
 358     }
 359
 360   printf ("filesys: self test ok\n");
 361 }
 362 \f
 363 /* Formats the filesystem. */
 364 static void
 365 do_format (void)
 366 {
 367   struct bitmap *free_map;
 368   struct inode *map_inode, *dir_inode;
 369   struct dir *dir;
 370
 371   printf ("Formatting filesystem...");
 372
 373   /* Create the initial bitmap and reserve sectors for the
 374      free map and root directory inodes. */
 375   free_map = bitmap_create (disk_size (filesys_disk));
 376   if (free_map == NULL)
 377     PANIC ("bitmap creation failed--disk is too large");
 378   bitmap_mark (free_map, FREE_MAP_SECTOR);
 379   bitmap_mark (free_map, ROOT_DIR_SECTOR);
 380
 381   /* Allocate data sector(s) for the free map file
 382      and write its inode to disk. */
 383   map_inode = inode_create (free_map, FREE_MAP_SECTOR,
 384                             bitmap_file_size (free_map));
 385   if (map_inode == NULL)
 386     PANIC ("free map creation failed--disk is too large");
 387   inode_commit (map_inode);
 388   inode_close (map_inode);
 389
 390   /* Allocate data sector(s) for the root directory file
 391      and write its inodes to disk. */
 392   dir_inode = inode_create (free_map, ROOT_DIR_SECTOR,
 393                             dir_size (NUM_DIR_ENTRIES));
 394   if (dir_inode == NULL)
 395     PANIC ("root directory creation failed");
 396   inode_commit (dir_inode);
 397   inode_close (dir_inode);
 398
 399   /* Write out the free map now that we have space reserved
 400      for it. */
 401   free_map_file = file_open (FREE_MAP_SECTOR);
 402   if (free_map_file == NULL)
 403     PANIC ("can't open free map file");
 404   bitmap_write (free_map, free_map_file);
 405   bitmap_destroy (free_map);
 406   file_close (free_map_file);
 407
 408   /* Write out the root directory in the same way. */
 409   root_dir_file = file_open (ROOT_DIR_SECTOR);
 410   if (root_dir_file == NULL)
 411     PANIC ("can't open root directory");
 412   dir = dir_create (NUM_DIR_ENTRIES);
 413   if (dir == NULL)
 414     PANIC ("can't initialize root directory");
 415   dir_write (dir, root_dir_file);
 416   dir_destroy (dir);
 417   file_close (root_dir_file);
 418
 419   printf ("done.\n");
 420 }
 421
 422 /* If SUCCESS is false, panics with an error complaining about
 423    LINE_NO. */
 424 static void
 425 must_succeed_function (int line_no, bool success)
 426 {
 427   if (!success)
 428     PANIC ("filesys_self_test: operation failed on line %d", line_no);
 429 }