Yalnix File System

COMP 421: Advanced Operating Systems · Assignment 3

COMP 421 Lab 3: The Yalnix File System

1 Project Overview

This project asks you to implement a file system for the Yalnix kernel. Your implementation will consist of two components: a file system library and a file system server process. The file system server responds to requests from client processes through interprocess communication (IPC), while the file system library provides user-level procedures for issuing these requests.

The file system is designed to be simple but realistic. It includes several standard Unix-style features: regular files, directories, symbolic links (optional), file permissions and link counts, and a cache of recently accessed disk blocks and inodes for performance.

---

2 The Yalnix File System on Disk

2.1 Disk Organization

The Yalnix file system is stored on a single disk. The disk is partitioned into the following regions:

Boot block (sector 0): Reserved for boot code; not used by the file system.
Super block (sector 1): Contains information about the file system layout. The first INODESIZE bytes of this block hold the file system header, followed by inodes:

``c struct fs_header { int num_blocks; /* total blocks in file system */ int num_inodes; /* number of inodes in file system */ int padding[14]; /* make fs_header and inode same size */ };``

Inode region: A contiguous region containing all inodes for the file system. Inodes are packed into blocks starting immediately after the fs_header in block 1.
Data block region: A contiguous region containing all data blocks for the file system.

The file system is stored on disk as a sequence of sectors. Each sector is SECTORSIZE (512) bytes. The disk has NUMSECTORS (1426) total sectors. Constants defining the file system structure are given in the header file comp421/filesystem.h.

Inode-to-Block Mapping

There is no inode 0. The fs_header structure occupies the same 64-byte slot that inode 0 would have used. Valid inode numbers range from 1 to num_inodes. The key formulas:

INODES_PER_BLOCK = BLOCKSIZE / INODESIZE = 512 / 64 = 8

Inode N is in block:    1 + (N / INODES_PER_BLOCK)
Offset within block:    (N % INODES_PER_BLOCK) * INODESIZE

First data block:       1 + ceil((num_inodes + 1) / INODES_PER_BLOCK)

The +1 in (num_inodes + 1) accounts for the fs_header occupying slot 0. For the default 47 inodes: 1 + ceil(48 / 8) = 1 + 6 = 7, so data blocks start at block 7.

2.2 Inodes

Each file (regular file or directory) has an associated inode. An inode is a data structure that contains metadata about the file, including its size, owner, permissions, and the location of its data on disk.

The format of an inode is:

#define INODESIZE       64      /* The size in bytes of each inode */
#define NUM_DIRECT      12      /* number of direct block #s in inode */

struct inode {
    short type;                   /* file type (e.g., directory or regular) */
    short nlink;                  /* number of hard links to inode */
    int   reuse;                  /* inode reuse count */
    int   size;                   /* file size in bytes */
    int   direct[NUM_DIRECT];     /* block numbers for 1st NUM_DIRECT blocks */
    int   indirect;               /* block number of indirect block */
};

The constants NUM_DIRECT and INODESIZE are defined in comp421/filesystem.h. Note that type and nlink are short (2 bytes each), not int.

The inode type field can take one of the following values (defined in comp421/filesystem.h):

INODE_REGULAR: A regular file.
INODE_DIRECTORY: A directory file.
INODE_SYMLINK: A symbolic link (optional).

The direct array contains disk block numbers for the first several disk blocks of the file. If the file is larger than can be addressed by the direct blocks, the indirect field contains the disk block number of an indirect block, which itself contains disk block numbers for additional data blocks.

An inode is allocated from the inode region on disk. The file system manages free inodes using a free inode list. When a new file is created, the file system allocates a free inode from this list. When a file is deleted (its link count drops to zero), the inode is returned to the free inode list.

The reuse field in an inode is used to distinguish between different versions of the same inode number. When the file system is first formatted, the reuse field in each inode should be initialized to 0. Each time an inode is allocated (from being free), the reuse count in the inode must be incremented. The reuse count allows your file system to detect when a file descriptor refers to an inode that has been reused since the file was originally opened. The mkyfs formatter sets the root inode's reuse to 1 (since it was allocated once during formatting); free inodes start with reuse = 0.

Free List Management

There is no free list stored on disk. At startup, your server must: 1. Scan all inodes (1 through num_inodes) to build an in-memory free inode list -- any inode with type == INODE_FREE is free. 2. Determine which data blocks are in use by examining the direct[] and indirect block pointers of all allocated inodes, then treat all remaining data blocks as free.

2.3 Directory Entries

A directory is a special file whose contents consist of a sequence of directory entries. Each directory entry has the following format:

#define DIRNAMELEN      30      /* length in bytes of name in dir_entry */

struct dir_entry {
    short inum;                   /* inode number */
    char  name[DIRNAMELEN];       /* file name (not null-terminated) */
};

Note that inum is short (2 bytes), not int. Each struct dir_entry is 32 bytes total (2 + 30), so 16 directory entries fit in one block. A free directory entry has inum set to 0.

The file name in a directory entry may contain any characters other than a slash ('/') or the null character ('\0'). For example, even "unusual" characters such as a space, a backspace, or even a newline character are all legal in a file name; each of these characters should be treated exactly the same as any other character in a file name.

If the actual file name is shorter than DIRNAMELEN characters, the remainder of the characters in this field should be filled with the null character ('\0'). If the file name is exactly DIRNAMELEN characters long, there will be no null character at the end of the file name in the directory entry (it would waste a lot of disk space to leave room store the null character for every directory entry, and it is not needed to understand the disk format). You thus cannot correctly use the functions strlen() or strcpy() to access the file name, since the null terminating character may not be present. When looking at the file name in a directory entry, the name ends at the first null character or after DIRNAMELEN characters, whichever occurs first. Any attempt to create a file name longer than DIRNAMELEN characters should be considered as an error by your file system.

The name field of a free directory entry (with inum set to 0) need have no special value and should be ignored by your file system. However, it is best that, if the inum field is 0, then the name field is also all 0's, but this is not required.

When creating a new entry in a directory, you should "reuse" the first "free" entry in the directory (directory entry in which the inum field is set to 0). If there are no "free" entries in the directory, you should append a single new entry to the end of the directory.

2.4 Pathnames

As in Unix, each file is identified by a pathname, such as /dirname/subdirname/file. The slash character ('/') at the beginning of the pathname indicates that this is an absolute pathname, meaning that processing of that pathname begins at the inode of the root directory. A pathname such as otherdir/file (which does not have a slash character at the beginning) is a relative pathname; processing of a relative pathname begins at the inode of the current directory of the requesting user process, set by the process calling the ChDir operation (the current directory of each process when the process begins execution of a new program should be "/").

The slash character is also used to separate individual directory names along the path to the file, and to separate the last directory name from the name of the particular file in that directory. More than one slash character in a row within a pathname should be processed the same as if a single slash character had occurred there (except that those additional slash characters still do count in the total length of the pathname string). For example, the pathname such as /////dirname//subdirname///file refers to exactly the same file as does the pathname /dirname/subdirname/file. A pathname with one or more trailing slash characters at the end of the pathname (with no further characters after the last slash character) should be treated as if the pathname ended in a final component "." (described below) following that last slash character; so, for example, the pathname "/a/b/c/" should be treated as if the pathname was actually "/a/b/c/." instead. An empty pathname (a null string) should result in an error being returned for any Yalnix file system operation attempting to use such an empty pathname.

When processing a pathname, e.g., as part of an Open operation, you should process the pathname one component at a time. A component of a pathname is the name that occurs between two slash characters (or before the first slash character, or after the last slash character). As noted above, processing begins either with the root inode (for an absolute pathname) or at the inode of the current directory of the requesting process's current directory (for a relative pathname). This starting inode defines the initial "current lookup inode" for this pathname. For each next component of the pathname, beginning with the leftmost component and working component by component across the pathname, processing of that component is performed relative to the then-current lookup inode in the processing of that pathname. If that component is a directory name, for example, the current lookup inode becomes the inode for that directory (if that directory itself was found), and processing of the following component of the pathname proceeds with the inode for that directory as the current lookup inode.

A pathname, when presented as an argument to a Yalnix file system call is represented as a normal C-style string, terminated by a null character. The maximum length of the entire pathname, including the null character, is limited to MAXPATHNAMELEN characters. This limit of MAXPATHNAMELEN characters applies only to the length of the pathname string when presented as an argument to a Yalnix file system call. The fact of whether this pathname is an absolute pathname or a relative pathname, or the possible presence of symbolic links encountered while processing this pathname, do not count against that limit of MAXPATHNAMELEN characters. The limit of MAXPATHNAMELEN characters literally applies only to the argument of the call itself.

Within each directory, two special directory entries must exist (created by the MkDir call):

`"."` (dot): This directory entry has the name "." and the inode number of the directory within which it is contained.
`".."` (dot dot): This directory entry has the name ".." and the inode number of the parent directory of the directory within which it is contained. In the root directory, the ".." entry instead has the same value as "." (the inode number of the root directory, which is defined as ROOTINODE in comp421/filesystem.h).

The "." and ".." entries are created in a directory when it is created (by the MkDir request) as the first two entries in the new directory. These two directory entries subsequently cannot be explicitly deleted, but are automatically cleaned up along with the rest of the directory on a successful RmDir request. The "." and ".." entries must be included in the nlink count in the inode of the directory to which each points.

2.5 Symbolic Links

NOTE: Support for symbolic links is optional. The test suite does not require symlink support to pass. Symbolic links are defined here for completeness and to clarify how they fit into the file system design.

The Yalnix file system can support symbolic links, as in the Unix file system. A symbolic link to some other file is represented in the Yalnix file system by an inode of type INODE_SYMLINK; the format of this file is otherwise the same as an INODE_REGULAR file. However, the contents of this file (the data stored in the data blocks hanging off of this inode) is interpreted by the file system as the name of the file to which this symbolic link is linked. Note that the length of this name is the entire length of the data in the file, as given by the size field in the inode, and the name as recorded here is not terminated by a null (`'\0'`) character.

The file name to which a symbolic link points may be either an absolute pathname or a relative pathname. If a relative pathname, it is interpreted relative to the directory in which the symbolic link file itself occurs; that is, the processing of the symbolic link target begins with the current lookup inode (see Section 2.4) being the inode of the directory in which the symbolic link file itself was found. For example, consider the pathname "/a/b/c", where "b" within this pathname is a symbolic link to "d/e". Since the target of the symbolic link "b" in this example is a relative pathname, the search for the next component when, for example, attempting to Open the name "/a/b/c", begins in the same directory in which the name "b" itself was found. If, instead, "b" within the pathname "/a/b/c" is a symbolic link to the absolute pathname "/p/q", then attempting to open the file "/a/b/c" is then "equivalent" to attempting to open the name "/p/q/c" (but see the note below).

As another example, suppose that:

You are attempting to Open the pathname "/a/b/c".
In doing this Open, you find that the name "b" within this pathname is a symbolic link to "d/e".
You further find that the name "e" is a symbolic link to "f/g/h".
And you finally find that the name "c" is a symbolic link to "j".

The combined effect of attempting to Open this original pathname and encountering these symbolic links during processing is "equivalent" to attempting to Open the pathname "/f/g/h/j" (but see the note below).

Note that to process a pathname in which you might encounter one or more symbolic links, you should not attempt to build up the complete pathname that the original name is "equivalent" to. Rather, as with any pathname, you should process each component of the pathname one at a time. If you encounter a symbolic link, you should make a recursive call to your pathname lookup procedure, attempting to lookup the target of that symbolic link, before resuming processing what remains of the name you were processing when you encountered that symbolic link.

When creating a symbolic link, it is not an error if the target of the new symbolic link does not exist. Indeed, when creating a symbolic link, the target is simply recorded as-is, without any processing, except that it is an error to attempt to create a symbolic link to an empty pathname (a null string). Furthermore, if the target of an existing symbolic link is later deleted, this is not an error. In both cases, such a "dangling" symbolic link is not a problem; however, if such a dangling symbolic link is encountered while processing some other pathname (such as during an Open operation), an error would be returned upon encountering the dangling symbolic link.

Also, note that, whereas it is an error to attempt to create a hard (regular) link to a directory, creating a symbolic link to a directory is allowed; this is not an error.

Within the complete processing of a single pathname passed as an argument to any Yalnix file system operation, the maximum number of symbolic link traversals that may be performed is limited to MAXSYMLINKS symbolic link traversals (defined in comp421/filesystem.h). If in processing any single pathname that was an argument to any Yalnix file system operation, you would need to traverse more than MAXSYMLINKS symbolic links, you should terminate processing of that pathname and instead return an error as the result of that Yalnix file system operation.

Lastly, note the following special exception to handling a symbolic link when looking up a pathname, with respect to the last component of that pathname: If the last component of the pathname is the name of a symbolic link, that symbolic link must not be traversed unless the pathname is being looked up for an `Open`, `Create`, or `ChDir` file system operation (see the definition of the file system operations in Section 4.2). For example, if the last component of the pathname passed to an Unlink operation is the name of a symbolic link, then the symbolic link itself should be removed, but if the last component of the pathname passed to an Open operation is the name of a symbolic link, then the file to which the symbolic link refers should be opened, not the symbolic link itself.

2.6 Formatting the Disk

The hardware disk is initially empty. Before Yalnix can access a file system on this disk, the file system must first be formatted on the disk. Formatting a file system means to write the necessary disk data structures onto the disk to initially create a valid file system layout on the disk.

You must format a file system on your disk before your file system server process can read (and see) a valid file system on the disk.

A Unix program is provided to format an empty, validly-formatted Yalnix file system on the disk. To use this program, execute:

/clear/courses/comp421/pub/bin/mkfs

(Run this program from a Unix shell; do not run it under Yalnix.) This will create a YFS file system with 47 inodes (6 blocks worth of inodes). If you want a different number of inodes, put the number of inodes as the command line argument. The file system will contain only a root directory with "." and ".." in it. Run mkfs as a Unix command, not under Yalnix, from the same directory where you will run Yalnix.

You can modify the mkfs.c program (source at /clear/courses/comp421/pub/yfssamples-1.lab3/mkfs.c) to set up test cases. For example, before you get the MkDir file system request working correctly in your server, you can modify mkfs.c to make test directories. Run that version of mkfs before you then run your YFS server under Yalnix. Since mkfs.c runs as a Unix program, you can create anything in the Yalnix disk that you want to, and then run your server and see what your server can do with the contents that it finds on the disk.

---

3 New Yalnix Kernel Calls

A Yalnix kernel executable is provided that has been enhanced with support for reading and writing individual sectors of the disk. The disk is accessed by identifying the sector number to be read or written, and supplying the address of a sector-sized buffer. Function prototypes for these kernel calls are provided in the header file comp421/yalnix.h.

Disk I/O

**int ReadSector(int sectornum, void *buf)**

Initiate a read of disk sector number sectornum into the buffer at address buf. The buffer buf must be of size SECTORSIZE bytes. The calling process is blocked until the disk read completes. ReadSector returns the value 0 if the operation was completed successfully; however, if the indicated sector number is invalid or the indicated buffer in memory cannot be written, ReadSector returns ERROR.

**int WriteSector(int sectornum, void *buf)**

Initiate a write of disk sector number sectornum from the buffer at address buf. The buffer buf must be of length SECTORSIZE bytes. The calling process is blocked until the disk write completes. WriteSector returns the value 0 if the operation was completed successfully; however, if the indicated sector number is invalid or the indicated buffer in memory cannot be read, WriteSector returns ERROR.

These kernel calls wait for the read or write to be completed before returning. You may assume that the disk hardware is perfectly reliable, and that all read and write operations with valid arguments will eventually complete and return; you may assume that no disk hardware errors are possible during the read or write.

Interprocess Communication

The provided Yalnix kernel also includes IPC kernel calls:

`int Register(unsigned int service_id)`

Registers the calling process as providing the service service_id. After a process is registered with Register, other processes can use the Send kernel call to send messages to it by specifying the negative of this service_id value instead of the actual process ID as the destination. Returns 0 on success; returns ERROR on any error, including if another current process is already registered for that service_id. Your YFS server should register itself for the FILE_SERVER service id.

**int Send(void *msg, int pid)**

The argument msg points to a fixed-sized 32-byte buffer holding a message to be sent. The Send kernel call sends this message to the process indicated by the argument pid. The calling process is blocked until a reply message sent with Reply is received. Note that the `Send` kernel call always sends exactly 32 bytes, beginning at address `msg` as the message. Likewise, the reply message sent with Reply always overwrites exactly 32 bytes, beginning at address msg. Also note that all values in the 32-byte msg, including any pointer values, are simply sent uninterpreted, as the numerical values that they are; only those 32 bytes are sent, not anything that some pointer in the message points to.

If the value pid is positive, it is interpreted as the process ID of the process to which to send the message. If the value pid is negative, it is interpreted instead as an indication of the service to which to send the message, and the message is sent to the process currently registered with Register as providing service -pid. On success, the call returns 0; on any error, the value ERROR is returned.

If, at the time that the Send begins, the destination process identified by pid exists, but if that process later exits or is terminated before doing a Reply back to this process, then at the time that the destination process does exit or is terminated, the Send call is completed with a return value of ERROR.

**int Receive(void *msg)**

The argument msg points to a fixed-sized 32-byte buffer in the calling process's address space. The Receive kernel call receives the next message sent to this process with Send, copying that message into the buffer at msg. If no unreceived such message has been sent yet, the calling process is blocked until a suitable message is sent. Note that the `Receive` kernel call always receives (and thus overwrites) exactly 32 bytes, beginning at address `msg`. On success, the call returns the process ID of the sending process; on any error, the value `ERROR` is returned.

However, if a process is to be blocked due to its call to Receive, or if at any time while a process is already blocked due to a Receive call, it becomes the case that all other processes (other than the idle process) are also each blocked on some Receive call, the result would normally be a deadlock. Instead, to break this deadlock, the Yalnix kernel returns 0 to the calling process (and to each other process also then blocked on a Receive call). A process that has called Receive can determine that its Receive call was unblocked for this reason, since Receive always otherwise returns the process ID of the sending process (which will always be non-zero) or returns ERROR in case of any error.

**int Reply(void *msg, int pid)**

The argument msg points to a fixed-sized 32-byte buffer holding a reply message to be sent by the calling process. The Reply kernel call sends this reply message to the process with process ID pid, which must be currently blocked awaiting a reply from an earlier Send to this process. The reply message overwrites the original message sent in the address space of the sending process. Note that the `Reply` kernel call always replies with exactly 32 bytes, beginning at address `msg`. On success, the call returns 0; on any error, the value `ERROR` is returned.

**int CopyFrom(int srcpid, void *dest, void *src, int len)**

This call copies len bytes beginning at address src in the address space of process srcpid, to the calling process's address space beginning at address dest. The process srcpid must be currently blocked awaiting a reply from an earlier Send to the calling process. On success, the call returns 0; on any error, the value ERROR is returned.

**int CopyTo(int destpid, void *dest, void *src, int len)**

This call copies len bytes beginning at address src in the calling process's address space, to the address space of process destpid. The process destpid must be currently blocked awaiting a reply from an earlier Send to the calling process. On success, the call returns 0; on any error, the value ERROR is returned.

The CopyFrom and CopyTo kernel calls may be used by the receiver process with respect to a given sender process only between the receiver's Receive from and its Reply to that sender process. The src address on the CopyFrom call is interpreted by the Yalnix kernel as being a virtual address in the sending process's address space. Similarly, the dest address on the CopyTo call is interpreted as being a virtual address in the sending process's address space.

            Sender process is blocked between
            its Send and the receiver process's Reply

Sender ────────────────────────────────────────────────→ Time
        Send                                        ↑
               \                                    |
                \                                   |
                 ↘                                  |
Receiver ──────────────────────────────────────────────→
         Receive                                Reply

       Receiver process may use CopyFrom and CopyTo in order to
       read/write areas within the sender process's virtual address space

Message Sizing (CRITICAL)

WARNING: Messages are always exactly 32 bytes (`MESSAGE_SIZE`). Send, Receive, and Reply always transfer exactly 32 bytes. If your message buffer is smaller than 32 bytes, the remaining bytes sent will be whatever unknown data is in memory after your buffer, and a Reply will overwrite 32 bytes starting at msg, potentially corrupting adjacent memory.

The best (correct) way to use these calls is to define a struct of exactly 32 bytes as your message. For example:

struct my_msg {
    int data1;
    int data2;
    char data3[16];
    void *ptr;
};

The size of each int is 4 bytes (32 bits), the char array is 16 bytes, and the ptr pointer is 8 bytes (64 bits). Total: 32 bytes.

You could define a single generic struct for all messages, or a different struct for each message type. It is recommended that you put a "type" value (such as an int or short or char value) as the first thing in every message, so that the receiver can look at this value to determine the format of the rest of the message.

Be aware of struct padding. The C compiler will insert padding to keep each member aligned on a natural boundary for its size. For example, reordering the members of the struct above as:

struct my_msg {
    int data1;
    void *ptr;
    int data2;
    char data3[16];
};

results in a total size of 40 bytes (not 32), because the compiler inserts 4 bytes of padding before ptr and another 4 bytes at the end. This will not work with Yalnix message passing, since only the first 32 bytes will actually be sent.

You are strongly advised to confirm the actual size of any of your message structure definitions by using the C compiler's `sizeof` operator.

Message Design Guidance

Every request message from the library to the server should include:

A message type code (int or short) so the server knows which operation to perform.
The caller's current directory inode number (for resolving relative pathnames).
For pathname-based operations (Open, Create, MkDir, etc.): a pointer to the pathname string in the client's address space (the server will use CopyFrom to read it) and the length of the pathname.
For fd-based operations (Read, Write, Seek): the file's inode number and reuse count (from the fd table in the library), the current position, and for Read/Write: a pointer to the data buffer and the size.

The reply message should include:

The return value (int) for the operation.
For Open/Create: the inode number and reuse count of the opened file.
For Read: the number of bytes actually read (and the updated position).
For Stat: the struct Stat fields (inum, type, size, nlink).

Key insight: The server obtains the sender's PID from the return value of Receive. Use this PID as the srcpid argument to CopyFrom (to read the client's pathname or write buffer) and as the destpid argument to CopyTo (to write data into the client's read buffer or Stat result). You do NOT need to pack the client PID into the message struct.

---

4 The Yalnix File System Server

4.1 Overview

The Yalnix File System operates as a server executing as a regular user process outside the Yalnix kernel. Other processes using the file system send requests to the server and receive replies from the server, using the message-passing IPC calls provided by the Yalnix kernel.

When making a file system request such as Create or Read, a user process calls a library procedure (a stub function), which packages the appropriate parameters into a request message and sends this message to the file server. Sending this message (with the Yalnix Send kernel call) also blocks the requesting process until a reply (from Reply) from the server is received. The server executes the request and sends a reply message back when the request has completed. There is a separate copy of the library linked into each Yalnix user program that uses the file server.

The YFS server process retains no state on behalf of individual client processes or open files. Thus, the server process has no knowledge of specific file descriptor numbers that represent specific open files in specific processes. Instead, all state about a particular open file is retained within the copy of the file system library that is linked in to the client process itself; any necessary state is passed in the message to the server on each file system request. This allows the server to operate without worrying whether the client process that opened any individual file still exists, greatly simplifying the design of the file server. In the Yalnix file system, there are no reserved or otherwise special file descriptor number values, such as standard input, output, or error.

Caching

The file system server process maintains a cache in memory of recently accessed inodes and recently accessed data blocks. These caches are each of a constant size, defined by the following two constants from comp421/filesystem.h:

`BLOCK_CACHESIZE`: The cache of recently accessed disk blocks in the file server must be of constant size BLOCK_CACHESIZE blocks. Initially, all blocks in the cache are unused, but as new blocks are accessed, your server must manage the constant number of blocks in the cache using a write-back LRU policy.

`INODE_CACHESIZE`: The cache of recently accessed inodes in the file server must be of constant size INODE_CACHESIZE inodes. Initially, all inodes in the cache are unused, but as new inodes are accessed, your server must manage the constant number of inodes in the cache in a write-back LRU policy.

The block cache and the inode cache must each be a constant size. If a new item must be brought into the cache, you must decide which existing entry in the cache to replace to make room for it.

You will need to maintain a hash table to allow a block in the cache (if present) to be found quickly given the block's disk block number. Similarly, you will need a separate hash table for inodes. Given the small cache sizes (32 blocks, 16 inodes), a simple hash table with separate chaining is sufficient. For LRU, maintain a doubly-linked list; move an entry to the head on every access, and evict from the tail when the cache is full.

The cache management policy is write-back: dirty blocks (or inodes) are left in the cache (marked "dirty") until that cache slot is needed for holding a different block (or inode). At that time, the cached value is written back to disk and the new value is read into that space. When writing a cached disk block back to disk, use the WriteSector kernel call.

Important: Inode writeback goes through the block cache. When writing an inode back to disk, do NOT call WriteSector directly. Instead: (1) look up (or read in) the disk block containing that inode in the block cache, (2) copy the inode struct into the correct offset within that block, (3) mark the block as dirty. The block will be written to disk later when it is evicted from the block cache.

4.2 User Process File System Operations

A user process using the YFS file system makes file system requests by calling one of the procedures defined within your file system library. The library remembers the current directory of the process and maintains information about each file open by the process. The file system library interacts with the file server process through the Yalnix IPC facilities.

The interface to the file system library is defined in the C header file comp421/iolib.h, located at /clear/courses/comp421/pub/include/comp421/iolib.h. Do not copy this file into your own directory. Include it using:

#include <comp421/iolib.h>

When opening a file with either the Open or Create request, your library must allocate a data structure to remember information about the open file. Specifically, in your library, you will need to remember:

the file's inode number,
the file's reuse count (received from the server when the file was opened), and
the current position within the file.

The library should initialize the current directory inode number to ROOTINODE. Because the library is linked into each process, each process has its own independent fd table.

The library must support up to a maximum of MAX_OPEN_FILES open files at a time; if you run out of unused file descriptor numbers within this limit, return ERROR in response to any Open or Create that attempts to open a new file. The file descriptor number assigned for a newly opened file must be the lowest available (unused) file descriptor number.

The file descriptor numbers used by a process are assigned by and managed by the copy of your library linked into the user program running in that process. The file descriptor number is part of the procedure call interface between a user program and the library; the file descriptor number is not part of the message interface between your library and your file server process.

Your library, together with your file server process, must support the following operations:

**int Open(char *pathname)**

Opens the file named by pathname. If the file exists, returns a file descriptor number (lowest available unused fd). If the file does not exist, or if any other error occurs, returns ERROR. It is not an error to Open() a directory; the contents of the open directory can then be read using Read(), although it is an error to attempt to Write() to an open directory. If successful, the current position begins at position 0.

Each successful call to Open or Create must return a new, unique file descriptor number. Each instance has its own separate current position within the file.

`int Close(int fd)`

Closes the open file specified by file descriptor number fd. If fd is not the descriptor number of a file currently open in this process, returns ERROR; otherwise, returns 0.

**int Create(char *pathname)**

Creates and opens the new file named pathname. All directories in the named pathname must already exist; Create creates only the last file name component. If the named file already exists, truncates its size to 0 and opens the now empty file (truncation does not increase the reuse count, as it is still the same file). Truncating must free all data blocks allocated to the file (both direct blocks and any indirect block), return them to the free block list, zero out the direct[] array and indirect field in the inode, and set size = 0. However, it is an error to attempt to Create a file with the same name as an existing directory. On success, returns a file descriptor number (lowest available unused fd); otherwise, returns ERROR. Current position begins at 0.

Each successful call to Open or Create must return a new, unique file descriptor number.

**int Read(int fd, void *buf, int size)**

Reads data from an open file, beginning at the current position. fd specifies the file descriptor. buf specifies the address of the buffer from which to perform the read, and size is the number of bytes to read. Returns the number of bytes read, which will be 0 if reading at end-of-file; the number of bytes read will be the minimum of the number requested and the number remaining until end-of-file. The current position advances by the number of bytes read, and only that many bytes in buf should be modified. On any error, returns ERROR. It is not an error to Read() from a file descriptor open on a directory.

**int Write(int fd, void *buf, int size)**

Writes data to an open file, beginning at the current position. fd specifies the file descriptor. buf specifies the address of the buffer from which to write, and size is the number of bytes to write. Returns the number of bytes written, which may be less than requested (0 indicates nothing was written). The current position advances by the number of bytes written. On any error, returns ERROR. It is an error to Write() to a file descriptor open on a directory.

`int Seek(int fd, int offset, int whence)`

Changes the current file position of the open file specified by fd. The argument offset specifies a byte offset relative to the position indicated by whence:

- SEEK_SET: Set current position to offset bytes after the beginning of the file. - SEEK_CUR: Set current position to offset bytes after the current position. - SEEK_END: Set current position to offset bytes after the current end of the file.

It is an error if the Seek attempts to go before the beginning of the file. Returns the new position, or ERROR on failure. Example: Seek(fd, 0, SEEK_END) seeks to end of file and returns the file size.

Seek does allow the file offset to be set beyond the end of the file; this is not an error. This itself does not change the file size. However, if data is later written at this new offset, the file size is then set to include the gap (a "hole" in the file). Subsequent Reads of the hole return bytes of zeros ('\0') until data is actually written into it. A block number of 0 in the direct[] array or indirect block means "not allocated" (a hole); reads from such blocks return zeros. When writing to a position that requires an unallocated block, allocate a new block and zero-fill it.

Block-Level Read/Write

A file's data is stored in blocks. The first NUM_DIRECT (12) blocks are referenced by the direct[] array in the inode. For files larger than 12 blocks, the indirect field points to a data block that contains an array of int block numbers (BLOCKSIZE / sizeof(int) = 128 additional entries).

Maximum file size = (NUM_DIRECT + BLOCKSIZE/sizeof(int)) * BLOCKSIZE = (12 + 128) * 512 = 71,680 bytes.

When reading or writing a range of bytes: 1. Compute the starting block index: position / BLOCKSIZE 2. Compute the offset within that block: position % BLOCKSIZE 3. Read/write the partial first block, then full middle blocks, then partial last block 4. For block indices 0-11, use inode.direct[index] 5. For block indices >= 12, read the indirect block and use entry [index - NUM_DIRECT] 6. When writing, allocate new blocks from the free block list as needed

**int Link(char *oldname, char *newname)**

Creates a hard link from newname to the existing file oldname. The files need not be in the same directory. oldname must not be a directory. It is an error if newname already exists. Returns 0 on success; ERROR on failure.

**int Unlink(char *pathname)**

Removes the directory entry for pathname and decrements the file's nlink. If nlink reaches 0, the file must be fully freed: free all data blocks (direct and indirect), free the indirect block itself, set the inode type to INODE_FREE, and return the inode to the free inode list. (The reuse count is NOT incremented on free -- it is incremented later when the inode is next allocated.) pathname must not be a directory. Returns 0 on success; ERROR on failure.

**int SymLink(char *oldname, char *newname)**

Creates a symbolic link from newname to the file name oldname. The files need not be in the same directory. It is an error if newname already exists. oldname need not currently exist. The target is simply recorded as-is, except that it is an error to create a symbolic link to an empty pathname. Returns 0 on success; ERROR on failure.

**int ReadLink(char *pathname, char *buf, int len)**

Reads the name of the file that the symbolic link pathname is linked to; the named pathname must be that of a symbolic link. Returns the length (number of characters) of the name the symbolic link points to (or len, whichever is smaller), and places the name in buf, up to len characters. If the name is longer than len, it is truncated (not an error). The characters in buf are not terminated by a `'\0'` character. Returns ERROR on any failure.

**int MkDir(char *pathname)**

Creates a new directory named pathname, including the "." and ".." entries. The new directory's inode gets type = INODE_DIRECTORY and nlink = 2 (one for its own "." entry, one for the parent's directory entry pointing to it). The parent directory's nlink must be incremented by 1 (because the new directory's ".." points to the parent). It is an error if pathname already exists. Returns 0 on success; ERROR on failure.

**int RmDir(char *pathname)**

Deletes the existing directory named pathname. The directory must contain no entries other than "." and ".." (and possibly some free entries -- scan all entries to verify). On success: remove the directory entry from the parent, decrement the parent's nlink by 1, free the directory's data blocks and inode. Returns 0 on success; ERROR on failure. It is an error to remove the root directory or to individually remove the "." or ".." entry from a directory.

**int ChDir(char *pathname)**

Changes the current directory of the requesting process to the directory indicated by pathname. The current directory should be remembered by the inode number of that directory, within the file system library. That inode number should be passed to the file server on each request that takes file name arguments. pathname must be a directory. Returns 0 on success; ERROR on failure.

**int Stat(char *pathname, struct Stat *statbuf)**

Returns information about the file indicated by pathname in the structure at statbuf:

``c struct Stat { int inum; /* inode number of file */ int type; /* type of file (e.g., INODE_REGULAR) */ int size; /* size of file in bytes */ int nlink; /* link count of file's inode */ };``

Returns 0 on success; ERROR on failure.

`int Sync(void)`

Writes all dirty cached inodes back to their corresponding disk blocks (in the cache) and then writes all dirty cached disk blocks to the disk. Does not complete until all dirty inodes and disk blocks have been written to disk; always returns 0.

`int Shutdown(void)`

Performs an orderly shutdown of the file server process. All dirty cached inodes and disk blocks should be written back to the disk (as in a Sync request), and the file server should then call Exit to complete its shutdown. As part of a Shutdown request, the server should print an informative message indicating that it is shutting down. Always returns 0.

Inode Reuse Checking

The reuse field in each inode indicates the number of times that inode has been "reused" since the file system was originally formatted. When the file system is formatted, the reuse field in each inode should be initialized to 0. Each time an inode is allocated (from being free), the reuse count must be incremented. The reuse count allows your file system to ensure, for example after doing an Open on some file, that on later attempts to Read or Write that open file, the same file still exists and that the inode has not been reused since that `Open` for some different file. If the inode's current reuse count does not match the reuse count that the file had when it was opened, your server should return ERROR for that request.

4.3 Running Yalnix, the Server, and User Processes

The enhanced Yalnix kernel executable is located at:

/clear/courses/comp421/pub/bin/yalnix

Do not copy this program to your own directory. You may either run it using the full pathname, or put /clear/courses/comp421/pub/bin on your shell's executable search path.

The Yalnix kernel automatically starts only one process (other than the idle process) at boot time (the "init" process). Your YFS server process should be executed as the Yalnix "init" process. As part of its initialization, the YFS server should use Register to register itself as FILE_SERVER. It should then Fork and Exec a first client user process:

if (argc > 1) {
    pid = Fork();
    if (pid == 0) {
        Exec(argv[1], argv + 1);
    }
}

This uses the second argument as the name of the process to execute. For example:

yalnix yfs testprog testarg1 testarg2 testarg3 ...

The program testprog can then create additional processes itself using Fork and Exec.

After initialization and Fork/Exec, the server enters its main loop:

while (1) {
    int sender_pid = Receive(&msg);
    if (sender_pid == 0) {
        // Deadlock break: all processes are blocked on Receive.
        // No more clients running. Exit or continue.
        break;
    }
    if (sender_pid == ERROR) continue;

    // Dispatch based on msg.type
    // Use CopyFrom(sender_pid, ...) to read client data (pathnames, write buffers)
    // Use CopyTo(sender_pid, ...) to write data to client (read buffers, Stat results)
    // ... handle the request ...

    Reply(&reply, sender_pid);
}

Within your file system library, a client process sends a message to your file server using:

Send(msg, -FILE_SERVER);

Since the file server registers itself as FILE_SERVER, this message is delivered to your file server without the client needing to know its actual process ID.

TracePrintf

You can use TracePrintf for debugging:

TracePrintf(int level, char *fmt, args...)

where level is a tracing level, fmt is a printf-style format, and args are the format arguments. To set the tracing level for the YFS server, add "-ly level" to the yalnix command line:

yalnix -ly 5 yfs testprog testarg1 testarg2 testarg3 ...

You may also include "-lh level", "-lk level", and/or "-lu level" to set hardware, kernel, and/or user tracing levels.

---

5 Getting Started: Makefile Setup

Your workspace contains a Makefile template. You must customize it before anything will compile.

The template has placeholder values:

YFS_OBJS = example1.o example2.o     # <-- replace with your actual .o files
YFS_SRCS = example1.c example2.c     # <-- replace with your actual .c files
IOLIB_OBJS = example3.o example4.o   # <-- replace with your actual .o files
IOLIB_SRCS = example3.c example4.c   # <-- replace with your actual .c files

For example, if you structure your server as yfs.c + cache.c and your library as iolib.c, change these lines to:

YFS_OBJS = yfs.o cache.o
YFS_SRCS = yfs.c cache.c
IOLIB_OBJS = iolib.o
IOLIB_SRCS = iolib.c

You must set TEST = (empty) or remove the TEST line entirely, since test programs are compiled separately by the test runner. If you leave the placeholder test names, make all will fail trying to build nonexistent test programs.

CFLAGS and `-fcommon`

The template Makefile uses:

CFLAGS = -g -Wall -Wextra -Werror

If you declare global variables in a shared header file without extern (e.g., int NUM_INODES; in a .h included by multiple .c files), GCC 10+ will reject this as a multiple-definition error. You have two options:

1. (Recommended) Use proper extern declarations in headers and define globals in exactly one .c file: ```c // yfs.h extern int NUM_INODES;

// yfs.c int NUM_INODES; ```

2. Add -fcommon to CFLAGS to allow the old C behavior where tentative definitions are merged: ``makefile CFLAGS = -g -Wall -fcommon``

---

6 Building and Testing

All compilation and execution happens on CLEAR (Rice's Linux servers). The test runner handles uploading your code and running tests via SSH.

# The test runner runs these steps for each test:
# 1. Upload your source files to CLEAR
# 2. Run: make clean && make all
# 3. Compile test program with link-user-gcc
# 4. Format fresh disk: ./mkyfs
# 5. Run: yalnix yfs <test_program>
# 6. Parse TTYLOG output files for results

Each test gets a fresh disk (via mkyfs). Tests are independent.

The mkyfs formatter is provided by the test runner -- you do NOT need to create mkyfs.c. The runner automatically uploads and compiles it alongside your code. Your make all only needs to produce two things: yfs (server binary) and iolib.a (client library).

IMPORTANT: Do not use printf or fprintf in your iolib.c library code. Any printf output from your library will appear in the test program's TTYLOG output and may cause test validation to fail. Use TracePrintf in your yfs.c server code for debugging (output goes to TTYLOG.0 / TRACE, separate from test output).

---

7 Debugging Tips

TTYLOG files: Yalnix redirects each process's output to separate files.

TTYLOG.0 is the YFS server output, TTYLOG.1 is the first user process (your test program). Check TTYLOG.0 for server errors/crashes and TTYLOG.1 for test program output.

TracePrintf: Use TracePrintf(level, fmt, ...) in your YFS server

for debugging output. Set the level with yalnix -ly <level> yfs ....

Test timeouts: Most tests call Shutdown() which cleanly exits the

Yalnix simulation. One test (tcreate) does NOT call Shutdown() and will run until the timeout kills it -- this is expected behavior.

Common errors in TTYLOG output:

- TRAP -- Your server hit an exception (segfault, illegal instruction, etc.) - Segfault / BUS ERROR -- Memory access violation in your code - KILL -- Process was killed (usually timeout)

---

8 Suggested File Structure

You choose your own file organization. A typical structure:

yfs.c -- Server main loop, message dispatch, FS operation implementations
iolib.c -- Client library stubs (one function per FS operation)
cache.c -- Block and inode caching with LRU eviction
yfs.h -- Your shared header (message codes, data structures, prototypes)
Makefile -- Customized from template

This is only a suggestion. You may use fewer or more files.

---

9 Key Constants

Constant	Meaning
`SECTORSIZE`	Disk sector size in bytes (512)
`NUMSECTORS`	Total sectors on disk (1426)
`BLOCKSIZE`	Disk block size in bytes (= `SECTORSIZE` = 512)
`INODESIZE`	Size of each inode in bytes (64)
`NUM_DIRECT`	Number of direct block pointers per inode (12)
`ROOTINODE`	Inode number of root directory (1)
`DIRNAMELEN`	Max characters in a directory entry name (30)
`MAXPATHNAMELEN`	Max pathname length including null terminator (256)
`INODE_FREE`	Inode type: not in use (0)
`INODE_DIRECTORY`	Inode type: directory (1)
`INODE_REGULAR`	Inode type: regular file (2)
`INODE_SYMLINK`	Inode type: symbolic link (3)
`ERROR`	Return value for failed operations
`BLOCK_CACHESIZE`	Required block cache size (32)
`INODE_CACHESIZE`	Required inode cache size (16)
`MAX_OPEN_FILES`	Max open files per process (16)
`MAXSYMLINKS`	Max symbolic link traversals per pathname lookup (20)
`FILE_SERVER`	Service ID for YFS server registration (1)

Makefile2.8 KB

makefile

#
#   COMP 421 Lab 3
#
#	Sample Makefile for COMP 421 YFS and user programs.
#
#	The YFS server built will be named "yfs".  *ALL* Makefiles
#	for this lab must have a "yfs" rule in them, and must
#	produce a YFS server executable named "yfs" -- we will run
#	your Makefile and will grade the resulting executable
#	named "yfs".  Likewise, *ALL* Makefiles must have a rule
#	named "iolib.a" to make your YFS library.
#

#
#	Define the list of user test programs you also want to be made
#	by this Makefile.  For example, the definition below specifies
#	to make Yalnix test user programs test1, test2, and test3, all
#	of which will be linked with your library to enable them to use
#	your server.  You should modify this list to the list of your
#	own test programs.
#
#	For each user test program, the Makefile will make the
#	program out of a single correspondingly named source file.
#	In addition to this single source file for each test
#	program, each program will also be linked with your library.
#	For example, the Makefile will make test1 out of test1.c,
#	if you have a file named test1.c in this directory.
#
TEST = test1 test2 test3

#
#	Define the list of everything to be made by this Makefile.
#	The list should include "yfs" (the name of your server) and
#	"iolib.a" (the name of your library).  This should also
#	include $(TEST) so that all of your user test programs
#	(defined above) are also made by this Makefile.
#
ALL = yfs iolib.a $(TEST)

#
#	You must modify the YFS_OBJS and YFS_SRCS definitions below.
#	YFS_OBJS should be a list of the .o files that make up your
#	YFS server, and YFS_SRCS should  be a list of the corresponding
#	source files that make up your serever.
#
YFS_OBJS = example1.o example2.o
YFS_SRCS = example1.c example2.c

#
#	You must also modify the IOLIB_OBJS and IOLIB_SRCS definitions
#	below.  IOLIB_OBJS should be a list of the .o files that make up
#	your YFS library, and IOLIB_SRCS should  be a list of the
#	corresponding source files that make up your library.
#
IOLIB_OBJS = example3.o example4.o
IOLIB_SRCS = example3.c example4.c

#
#	You should not have to modify anything else in this Makefile
#	below here.  If you want to, however, you may modify things
#	such as the definition of CFLAGS, for example.
#

LANG = gcc

PUBLIC_DIR = /clear/courses/comp421/pub

CPPFLAGS = -I$(PUBLIC_DIR)/include
CFLAGS = -g -Wall -Wextra -Werror

%: %.o
	$(LINK.o) -o $@ $^ $(LOADLIBES) $(LDLIBS)

LINK.o = $(PUBLIC_DIR)/bin/link-user-$(LANG) $(LDFLAGS) $(TARGET_ARCH)

%: %.c
%: %.cc
%: %.cpp

all: $(ALL)

yfs: $(YFS_OBJS)
	$(LINK.o) -o $@ $^ $(PUBLIC_DIR)/lib/print-yfs.o $(LOADLIBES) $(LDLIBS)

iolib.a: $(IOLIB_OBJS)
	rm -f $@
	ar rv $@ $(IOLIB_OBJS)
	ranlib $@

$(TEST): iolib.a

mkyfs: mkyfs.c
	$(CC) $(CPPFLAGS) -o mkyfs mkyfs.c

clean:
	rm -f $(YFS_OBJS) $(IOLIB_OBJS) $(ALL)

depend:
	$(CC) $(CPPFLAGS) -M $(YFS_SRCS) $(IOLIB_SRCS) > .depend

#include .depend