CMSC 412 Project 5

GOSFS Filesystem

Due Friday, December 13, 11:59pm

Notes and Updates

Previous versions of this project have had intermediate deadlines. We're using a single deadline at the end, but there is a lot of code to write. Please start early.

1. Introduction

GeekOS currently has a filesystem of type PFAT residing in IDE disk 0 (disk image diskc.img). PFAT is extremely limited: all files are stored in a single directory, file names are limited to twelve characters, and it does not allow writing to disk. The goal of this project is to develop a new filesystem type, called GOSFS, and to create an instance of it in IDE disk 1 (disk image diskd.img). User programs will remain on the original PFAT filesystem while you develop your GOSFS filesystem implementation.

Here, we use the term filesystem type to mean a set of rules for laying out directories and files in a disk and for adding, modifying and deleting them. We use the term filesystem to mean an instance of a filesystem type. For example, PFAT is a filesystem type (whose rules are implemented in pfat.c); diskc.img is a PFAT filesystem. GOSFS is another filesystem type (whose rules you will implement in gosfs.c); your diskd.img will be a GOSFS filesystem.

References in the text (depending on your edition, chapter numbers may differ): File-system interface (chapter 11), File-system implementation (chapter 12).

2. Context: VFS and blockdev

GeekOS has a virtual filesystem (VFS) that acts as a wrapper for different types of files. VFS provides a uniform set of system calls that abstract away the details of the filesystem's implementation. It is not limited to files on disk: you used VFS at the beginning of the semester to provide access to pipes.

Initially VFS consists of just an empty root directory ("/"). After the OS has been initialized, the PFAT filesystem in IDE 0 is mounted onto VFS at position "/c", after which user programs can access the PFAT filesystem as the VFS subdirectory "/c". Similarly, your GOSFS filesystem can be mounted at another point (say "/d") and accessed.

In addition to VFS, GeekOS has a virtual block device into which any block-structured storage device (e.g., IDE, floppy) can be registered. You used the block device layer to access your paging file in Project 4, and you will use it here to read and write the actual data in your filesystem. The block device acts as a wrapper to the registered storage devices, allowing them to be accessed in a uniform manner. In GeekOS, only the kernel has direct access to block devices.

The figure below illustrates the context. User programs invoke system calls, which invoke functions in vfs.c, which invoke functions in pfat.c or gosfs.c, which invoke functions in blockdev.c, which in turn invoke functions in ide.c. You have to implement the functions in in gosfs.c and the entry points to the system calls in syscall.c. The other layers are already implemented. You will need to understand how vfs.c and pfat.c work and how to use blockdev.c.

VFS uses a set of common data structures to provide uniform access across the filesystem types below it. Each user context has an array of ten File structures. The user refers to files by the index in the array; this index is called a file descriptor. Each element of the array is a pointer to a struct File. You used file descriptors and the File struct to refer to pipes in Project 0. As you may recall, the File struct contains some generic information such as the current position in the file, a pointer to a group of operations (function pointers) that VFS will use to act on the file, and a pointer called fsData that is available for the filesystem's use. The file operations and fsData pointer are what VFS uses to invoke filesystem-specific code. When you open a file, you will set the file operations to point to GOSFS functions. You will also create a struct with whatever information you need to manage a GOSFS file, and use the fsData pointer to associate your data with each File struct. Again, this is how you implemented pipes in Project 0.

The File struct lets you perform operations such as reads and writes on files that are already open. However, you need something more to create and open files, and to support other filesystem actions that are not assocated with a single file. VFS uses struct Mount_Point for this purpose. Each mounted filesystem has an associated Mount_Point struct. Like struct File, it has some generic data such as the prefix where the disk is mounted and the associated block device, a pointer to a group of filesystem operations, and a pointer to filesystem-specific data. You will again define the struct that holds whatever data you need to manage a GOSFS filesystem.

VFS also provides some utility functions to the filesystem types below it. For instance, it provides functions that register a filesystem type (Register_Filesystem) and that allocate a File struct (Allocate_File). You may use these VFS functions as you wish. The baseline version of main.c includes a call to Init_GOSFS(), which uses Register_Filesystem to tell VFS how to format or mount a GOSFS filesystem.

By convention, the pfat functions that are called by vfs have names of the form PFAT_<function> (see pfat.c). Similarly, the baseline GeekOS distribution has GOSFS functions with names of the form GOSFS_<function> (see gosfs.c). Note, however, that these names have no special significance to VFS. It accesses the functions through the function pointers described above. These function pointers are set at run time (when a filesystem type is registered, when a filesystem is mounted, and when a file is opened).

3. GOSFS

GOSFS provides a much richer interface than PFAT. The directories of a GOSFS filesystem form a tree. A directory can hold up to 36 entries, each of which may represent a file or a directory. A directory entry has a name of up to 64 characters (bytes), including the null at the end. A full path to a file is at most 1024 characters. Directories and files can be created and deleted. Existing files can opened for reading and writing. A raw disk can be formatted to hold a GOSFS filesystem. (In contrast, PFAT is read-only, has only one directory, its file names are at most 12 characters, and there is no format capability.)

Internally, GOSFS uses a block size of 4KB. Recall that an IDE disk in GeekOS has a block (or sector) size of 512 bytes. Thus in an IDE disk with a GOSFS filesystem, each GOSFS block is stored in 8 successive disk blocks. Gosfs block 0 (stored in disk blocks 0-7) is called the superblock; it holds info about this particular filesystem, such as the disk size, locations of free blocks, and the root directory's location. Gosfs blocks 1 and higher contain files and directories or are free.

You must keep track of free GOSFS blocks using a bitvector. A module called bitset is provided (see bitset.h and bitset.c) that manages a bitvector and find bits that are 0 (i.e. corresponding to free GOSFS blocks). Note that one bit in the bitvector corresponds to a GOSFS (4KB) block (i.e., 8 disk blocks). So a bitvector of is 8192 bits (1024 bytes) can keep track of a disk of size 8192 * 4KB = 32 MB.

3.1 Caching

When a file is read, the data from the disk is stored in a cache. If the user reads the same blocks again, the data may be returned from the cache without waiting for the disk again. Likewise, when data is written to a file, it is first saved in the cache. The write can then return without forcing the caller to wait for the disk, and the data can be read back from the cache before it is written to disk. (Of course, the data must eventually be written from the cache to disk. This may happen when the file is closed or when a later operation needs space in the cache, but in any case, the Sync system call makes sure that all cached changes are written to disk.) You must implement block-level caching in GOSFS. The automated tests will not detect whether or not you are caching blocks, but we will check your code by hand to make sure. Most of the work has already been done in a module called bufcache.c, which we suggest you use. If you use some other approach for caching, please email Jon to let him know and make sure your solution meets the requirements.

3.2. GOSFS functions

Here is a quick summary of the functions you must implement in gosfs.c. Except for Init_GOSFS, all the functions below are called by VFS. Note that there are some functions in gosfs.c that relate to access control and file ownership. You may ignore those.
Init_GOSFS()
Register the GOSFS filesystem type with vfs. (Sets pointers in vfs to some GOSFS_ functions.)
GOSFS_Mount(...)
Mount a GOSFS filesystem. The call identifies a block device (expected to have a GOSFS filesystem) and the place in vfs where it is to be mounted (for instance, "/d").
GOSFS_Format(...)
Format a block device with an empty GOSFS filesystem, i.e., creates superblock and empty root directory. The call identifies the block device (which should have been previously registered with blockdev).
GOSFS_Open(...)
Returns a File struct corresponding to a file in a mounted GOSFS filesystem. The call identifies the mounted filesystem and the path to the file in the filesystem. The file is now open: it can be read and written. This call is also used to create a file.
GOSFS_Open_Directory(...)
Return a File struct for an existing directory. (Note that, in contrast to Open, this function will not create a new directory.) The directory will be closed with GOSFS_Close.
GOSFS_Create_Directory(...)
Create a new directory and return a File struct for it.
GOSFS_Close(...)
Close an open file.
GOSFS_Delete(...)
Delete a file (mark its directory entry unused and mark its blocks as free).
GOSFS_Read(...)
Read a specified part of an open file.
GOSFS_Read_Entry(...)
Read an entry from a directory.
GOSFS_Write(...)
Write a specified part of an open file.
GOSFS_FStat(...) and GOSFS_Stat(...)
Retrieve information about a file.
GOSFS_Seek(...)
Set the position within a file.
GOSFS_Sync(...)
Write all buffered changes to a file onto the disk.

3.3. Filenodes and Directory structure

The internal structure of a GOSFS directory is defined in gosfs.h. Each directory in GOSFS takes up a single GOSFS block. It is an array of 36 GOSFS filenodes (GOSFSfileNode), one for every possible entry (file or subdirectory). (The limit of 36 ensures that the array fits in a single 4KB block.) A filenode has the following fields: name of the entry; size of the entry's data; whether the entry is active; whether the entry is a directory; and an array of pointers to GOSFS blocks containing the entry's data. Each "pointer" is simply a 4-byte block number. (There are also some fields (isSetUid, acls) not relevant for project 5.)

The array of pointers is called blocks. It is used as follows.

The superblock and root directory have no associated GOSFSfileNode. Every other directory and every file has an associated GOSFSfileNode in its parent directory.

3.4. Disk Layout

Superblock (4 KB)
Rest of the Disk (32 MB – 4 KB)
Magic
(4 bytes) 		Root Dir Ptr
(4 bytes) 		Disk Size
(4 bytes) 		Free Block Bitmap
(1024 bytes) 		Unused
(3060 bytes) 		Data (unallocated blocks, indirect blocks, and blocks allocated to files and directories)

An example disk layout is provided above. The diagram shows a 32 MB disk, but GOSFS disks may be larger or smaller than this size. Gosfs block 0 is called SUPERBLOCK, and contains filesystem housekeeping data. Gosfs blocks ≥ 1 may be:

The superblock is structured as follows:

When you do a Format(), you make a raw disk usable with GOSFS. That is:

Keep in mind that the superblock and root directory have no associated GOSFSfileNode.

4. VFS System Calls

Here are the system calls concerning the virtual filesystem (VFS). As you see, the semantics of these calls is very similar to that in UNIX. Keep in mind that each call vectors through the VFS layer before invoking a corresponding GOSFS_ or PFAT_ function. You have to implement the initial system call code (i.e., Sys_*) and the GOSFS_ functions. The PFAT_ functions are already implemented in pfat.c. It may be useful to look at PFAT as you implement GOSFS.

Several of the system calls use structures that are defined in fileio.h and vfs.h, both in include/geekos.

There are several errors that can arise in the system calls below. This is a list (not exhaustive) of these common error conditions. They are listed here to avoid repetition in the descriptions of the system calls.

int Mount(char *dev, char *prefix, char *fstype)
  • Entry point in syscall.c: Sys_Mount
  • Parameters:
    • dev: the name of the device, such as ide1
    • prefix: the VFS prefix, such as d (note that the leading slash is omitted from the call)
    • fstype: the name of the FS type; for GOSFS this is gosfs
  • Return 0 on success, or an error code on failure:
    • a filesystem is already mounted under prefix.
    • a parameter in the superblock has an illegal value (in GOSFS, this means that the magic number is wrong; there are other errors possible, such as the root directory pointer being zero, but we will not test these).
  • Typically, the user-side code for a system call calls strlen() on each string argument, and passes the string pointer and the string length as two separate arguments to the kernel code. (Recall that the "arguments" to the kernel code are stored in the x86 general-purpose registers ebx, ecx, edx, edi, and esi; eax is used to hold the system call number.) With three string arguments, this approach would require six separate arguments, but we only have five registers available. Therefore, the user code for Mount() stores the three strings in a struct VFS_Mount_Request (see fileio.h), and the only argument to the kernel code is a pointer to the struct.

int Open(char *path, int permissions)
  • Entry point in syscall.c: Sys_Open
  • Parameters:
    • path: the full path name of the file to open, such as /d/foo/bar/baz.txt
    • permissions: an integer assembled by OR'ing together the flags O_CREATE, O_READ, and O_WRITE, defined in fileio.h
  • Return a newly assigned file descriptor (from 0 to 9) on success, or an error code on failure (see common errors):
    • the final name in the path does not exist, and permissions do not include O_CREATE
    • the final name in the path is a directory (use OpenDirectory instead)
  • Comments
    • There's no system call to create a plain file. Setting O_CREATE tells Open to create a plain file (not a directory) if it does not exist. O_CREATE has no effect if the file already exists: the function should act just as if O_CREATE had not been set.
    • Do not create directories recursively. For instance, if /d/d1 is an empty directory, Open("/d/d1/d2/xFile", O_CREATE) will fail.
    • You don't have to worry about the case where a process opens a file twice without closing it, or about two processes having a file open at the same time.
    • Each open file has a current position, stored in struct File. When the file is opened, set the position to zero.

int Open_Directory(char *path)
  • Entry point in syscall.c: Sys_OpenDirectory
  • Parameters:
    • path: the full pathname of the directory to open
  • Return a newly assigned file descriptor (from 0 to 9) on success, or an error code on failure (see common errors)
  • Comments
    • Unlike Open, this function will not create a new directory. Use CreateDirectory instead.

int CreateDirectory(char *path)
  • Entry point in syscall.c: Sys_CreateDirectory
  • Parameters:
    • path: the full pathname of the directory (or directory chain) to create
  • Return 0 on success, or an error code on failure (see common errors):
    • a directory or regular file with the given name already exists
  • Comments
    • CreateDirectory creates a directory chain recursively if needed. For instance, if /d/d1 is an empty directory, CreateDirectory("/d/d1/d2/d3") will create d2 inside d1, and d3 inside d2. This operation is atomic: either all directories in the chain are created, or none are.
    • If the intermediate directories in the path do not exist, CreateDirectory may, at your option, return an error or recursively create them. That is, if /d/d1 is an empty directory,
      • CreateDirectory("/d/d1/d2") will create d2 within d1.
      • We will not test CreateDirectory("/d/d1/d2/d3"). It may either return an error, or create d2 within d1 and d3 within d2.
    • CreateDirectory does not open the new directory, since there would be no entries to read.

int Close(int fd)
  • Entry point in syscall.c: Sys_Close
  • Parameters:
    • fd: descriptor of the file to close
  • You may choose to write all buffered changes to disk when a file is closed.
  • Return 0 on success, or an error code on failure (see common errors)

int Delete(char *path)
  • Entry point in syscall.c: Sys_Delete
  • Parameters:
    • path: full path of the file or directory to be deleted
  • Return 0 on success, or an error code on failure (see common errors):
    • The path supplied ends in a directory, and the directory is not empty.
  • Comments
    • If Delete is called and the file is still open in some process, all subsequent operations on that file except Close() should fail. (The file could be open in the same process that called Delete, or in another process.)

int Read(int fd, char *buffer, int length)
  • Entry point in syscall.c: Sys_READ
  • Parameters:
    • fd: descriptor of the file to be read. It must be a plain file; use ReadEntry to read from a directory.
    • buffer: pointer to a buffer in user space where data will be stored
    • length: the number of bytes of data to be read
  • The read starts from the current file position. After reading, increment the file position by the number of bytes read.
  • On success, return the number of bytes read. This may be less than the number requested; if the starting position was at the end of the file, it may be zero. On failure, return an error code (see common errors):
    • the file was not opened with the O_READ flag
    • the descriptor is for a directory rather than a plain file
    • the buffer pointer is null

int Read_Entry(int fd, struct VFS_Dir_Entry *dirEntry)
  • Entry point in syscall.c: Sys_ReadEntry
  • Parameters:
    • fd: descriptor of the file to be read. It must be a directory; use Read to read from a plain file.
    • dirEntry: pointer to a VFS_Dir_Entry structure
  • On success, return 1, populate the VFS_Dir_Entry struct with the information for the next directory entry after the current file position. Note that, as files are added to and deleted from a directory, there may be empty nodes in the middle of the directory. You should return the contents of the next non-empty node. At end of file (that is, if there are no nodes in use between the file position and the end of the directory), return zero. On failure, return an error code (see common errors):
    • the descriptor was for a plain file rather than a directory
    • the buffer pointer is null

int Write(int fd, char *buffer, int length)
  • Entry point in syscall.c: Sys_Write
  • Parameters:
    • fd: descriptor of the file to be read. It must be a plain file; there is no way to write directly to a directory.
    • buffer: pointer to a buffer in user space that holds the data to be written
    • length: the number of bytes of data to be written
  • On success, return the number of bytes written and increase the file position. If the write goes past the end of the file, make the file grow: allocate blocks as necessary, and increase the file size in the GOSFSfileNode in the directory. On failure, return an error code (see common errors):
    • the file was not opened with the O_WRITE flag
    • the descriptor is for a directory rather than a plain file
    • the buffer pointer is null
    • the write would increase the number of blocks in the file, but there are no more free blocks on the disk

int Stat(char *path, VFS_File_Stat *stat)
  • Entry point in syscall.c: Sys_Stat
  • Parameters:
    • path: full path of the file or directory to be examined
    • stat: pointer to a VFS_File_Stat struct that will be populated with information about the file or directory
  • On success, return 0 and populate the stat struct. On failure, return an error code (see common errors).
  • Stat is useful for testing whether a file exists without incurring the overhead of opening it (or iterating through directory entries on the user side).
  • You can ignore the isSetuid and acl elements of struct VFS_File_Stat. To keep the output of ls.c clean, however, we recommend filling them with zeroes.
  • Set the size field of struct VFS_File_Stat to the number of bytes found when the file is read. That is, you should include 4K for each unused block in a sparse file.
  • Set the numBlocks field of struct VFS_File_Stat to the number of blocks used to store the file on disk. This number includes indirect blocks, but does not include the unused blocks in a sparse file.

int FStat(int fd, VFS_File_Stat *stat)
  • Entry point in syscall.c: Sys_FStat
  • Parameters:
    • fd: descriptor for the (open) file or directory to be examined
    • stat: pointer to a VFS_File_Stat struct that will be populated with information about the file or directory
  • On success, return 0 and populate the stat struct. On failure, return an error code (see common errors).
  • In GOSFS, FStat is useful mainly to check the size of an open file or directory. In more fully-featured filesystems, stat and fstat provide considerably more information about a file.
  • Regarding the contents of the VFS_File_Stat struct, see the description of Stat().

int Seek(int fd, int offset)
  • Entry point in syscall.c: Sys_Seek
  • Parameters:
    • fd: descriptor of the file (plain file or directory) to operate on
    • offset: position to set in the file
  • offset is an absolute position in the file. For a plain file, interpret it as a byte position; for a directory, interpret it as the position of a file node. Position 0 refers to the beginning of the file.
  • Return 0 on success, or an error code on failure (see common errors):
    • offset is less than zero
  • Comments
    • It is legal to set the offset past the end of the file. In this case, reads should return end of file, and writes should take place at the specified position. You should treat the file as being filled with zeroes up to the written position. For instance, after the code 
          int fd = Open("/d/test.txt", O_READ | O_WRITE | O_CREATE);
    Write(fd, "test0", 5);
    Seek(fd, 10000);
    Write(fd, "test10000", 9);
    Close(fd);

    char buf[50];
    fd = Open("/d/test.txt", O_READ);
    Seek(fd, 9995);
    Read(fd, buf, 10);
    Close(fd);
      the Read should return 10, and the buffer should contain five zero bytes followed by the characters "test1".
    • You do not have to allocate the GOSFS blocks that Seek() skipped over in the above example.

int Format(int device, char *filesystem_type)
  • Entry point in syscall.c: Sys_Format
  • Parameters:
    • device: the device name (such as ide1) to be formatted
    • filesystem_type: the type of filesystem that will be placed on the device. You only need to handle the string gosfs for this parameter.
  • Return 0 on success, or an error code on failure:
    • the device contains a mounted filesystem
    • the device is not available
  • Don't call Format() unless the user actually runs the format program (in format.c). This way data on the disk will persist across sessions.

int Sync(void)
  • Entry point in syscall.c: Sys_Sync
  • Parameters: none
  • Return 0 on success, or an error code on failure (see common errors)
  • Sync writes all buffered filesystem data to disk. As implemented in the VFS layer, it operates on all filesystems. The VFS Sync function will call GOSFS_Sync for each mounted GOSFS filesystem. GOSFS_Sync must write all buffered file changes to disk. After a Sync, it must be possible to reboot the machine without losing any changes.

5. Notes

You do not need to consider situations where two processes have the same file open.

Make sure your Mount() works well, so that we can test your project. If we cannot Mount() a GOSFS filesystem, we cannot grade your project.

You might also want to mount /d automatically in Main() to speed up your testing, but the code you submit should not mount /d automatically. However, /c should be mounted automatically in Main(), as usual. (So the code that you submit should have no changes in Main()).

We will test your filesystem with disk sizes up to 32 MB and file sizes up to 5 MB (which is enough to require double-indirect blocks). The discussion slides will describe how to create an arbitrary size diskd.img which will be available as device ide1.

This project does not depend on previous ones. You may work on top of your code from previous projects, or start from the baseline.

6. Testing

In src/user we will provide some programs that can be used to test your file management syscalls. The tentative list as of November 19 is:

We will also provide one or two premade disk images that you can mount. These will be available by November 26 in the subversion repository (run svn update or check out a new version of the repository), and we will update the spec with the final list of test programs at that time.