OS161 Assignment 4

Assignment4

In this assignment you will implement a few system calls that allow user programs to use files. This assignment will further train you how to navigate and understand a large and complex source base, and will teach you how to implement system calls and transfer control between the user mode and the kernel. You will implement part of the process management subsystem, which will be the subject of the next assignment.

Code reading exercises

1. What are the ELF magic numbers?

The ELF (Executable and Linkable Format) magic numbers are a sequence of bytes (0x7f, 'E', 'L', 'F') at the beginning of an ELF file that identify it as an ELF file and provide some basic information about its format.

These magic numbers help operating systems and other tools quickly identify ELF files and determine their basic characteristics without having to parse the entire file structure.

2. What is the difference between UIO_USERISPACE and UIO_USERSPACE? When should one use UIO_SYSSPACE instead?

The enum uio_seg is typically used in Unix-like operating systems to specify the memory segment for I/O operations.

/* Source/destination. */
enum uio_seg {
        UIO_USERISPACE,			/* User process code. */
        UIO_USERSPACE,			/* User process data. */
        UIO_SYSSPACE,			/* Kernel. */
};

UIO_USERISPACE(User process instruction space) refers to the memory segment where the user process's executable code (instructions) resides.

UIO_USERSPACE(User process data space) refers to the memory segment where the user process's data resides.

UIO_SYSSPACE is used when the memory being accessed is in kernel space rather than user space. It is typically used within kernel code or drivers when performing I/O operations on kernel-owned memory.

3. Why can the struct uio that is used to read in a segment be allocated on the stack in load_segment() (i.e., where does the memory read actually go)?

The uio structure describes an I/O operation that will read data from the file (vnode v) into the user's address space at vaddr.

The struct uio is allocated on the stack in the load_segment() function. This is fine because the structure is just used to describe the I/O operation, not to hold the actual data being read. The actual read operation (VOP_READ) will use this information to copy the data directly into the user's address space.

The key is in this line:

iov.iov_ubase = (userptr_t)vaddr;

Here, vaddr is the virtual address in the user's address space where the segment should be loaded.

4. In runprogram(), why is it important to call vfs_close() before going to user mode?

Once the program is loaded, there's no need for the kernel to maintain access to the executable file. Closing the file before going to user mode ensures that the new user process doesn't have unnecessary open file handles.

5. What function forces the processor to switch into user mode? Is this function machine dependent?

The function that forces the processor to switch into user mode is: mips_usermode(), which calls asm_usermode().

This function is machine dependent. Specifically, it's designed for the MIPS architecture.

6. In what file are copyin and copyout defined? memmove? Why can't copyin and copyout be implemented as simply as memmove?

copyin and copyout are defined in ~/src/kern/vm/copyinout.c

memmove is defined in ~/src/common/libc/string/memmove.c

The copyin and copyout functions cannot be implemented as simply as memmove because they involve copying data between user space and kernel space, which introduces security and reliability concerns that memmove doesn't have to deal with.

There's a copycheck function call at the beginning of both copyin and copyout because the kernel must verify that the user-provided addresses are valid and within the user's accessible memory range.

The complexity in copyin and copyout comes from setting up safeguards (like tm_badfaultfunc and setjmp) to catch and handle potential faults, performing necessary checks, and ensuring the operation is secure and doesn't compromise the system's integrity.

In contrast, memmove operates entirely within a single memory space (either all kernel or all user space) and can assume that all addresses it's working with are valid and accessible, which allows for a much simpler implementation.

7. What (briefly) is the purpose of userptr_t?

The purpose of userptr_t is to create a distinct pointer type for user-space addresses that cannot be accidentally confused or mixed with kernel-space pointers. It serves as a safeguard in the kernel code to clearly differentiate and safely handle pointers to user-space memory.

8. What is the numerical value of the exception code for a MIPS system call?

The exception code for a MIPS system call is 8.

9. How many bytes is an instruction in MIPS?

By examining the syscall(struct trapframe *tf) function, we can determine that each MIPS instruction is 4 bytes. This is evident from the following code snippet:

/*
 * Now, advance the program counter, to avoid restarting
 * the syscall over and over again.
 */
tf->tf_epc += 4;

The line tf->tf_epc += 4; increments the program counter by 4, indicating that each instruction in MIPS occupies 4 bytes.

10. Why do you "probably want to change" the implementation of kill_curthread()?

Since this function handles fatal faults in user-level code by calling panic(), which will crash the entire system. For a single user-level fault, we don't need to crash the entire kernel or system. We can simply signal the parent and clean up the process.

11. What would be required to implement a system call that took more than 4 arguments?

To implement a system call with more than 4 arguments, the following steps would be necessary:

1. Pass the first 4 arguments in registers a0-a3.

2. Fetch the remaining arguments from the user stack: For arguments beyond the 4th, we need to get them from the user stack, in detail, fetching from sp+16 to skip over the space reserved for the first 4 registerized arguments. (We need use the copyin() function to safely retrieve these arguments from the user space into the kernel space. )

12. What is the purpose of the SYSCALL macro?

The main purpose of the SYSCALL macro is to simplify the definition and handling of system calls, ensuring that each system call is properly numbered and recognized by the kernel.

1. Generate Assembly Code for System Calls: It generates the necessary assembly code to load the system call number into the appropriate register and call the generic __syscall handler.

2. Simplify the Registration Process: By using the SYSCALL macro, developers don't have to manually write the assembly code for each system call. The script ( gensyscalls.sh) parses this file and generates the required assembly stubs, making the system calls automatically recognizable and executable by the kernel.

13. What is the MIPS instruction that actually triggers a system call?

The instruction that actually triggers a system call is: syscall

14. After reading syscalls-mips.S and syscall.c, you should be prepared to answer the following question:

    OS/161 supports 64-bit values; lseek() takes and returns a 64-bit offset value. Thus, lseek() takes a 32-bit file handle (arg0), a 64-bit offset (arg1), a 32-bit whence (arg2), and needs to return a 64-bit offset value. In void syscall(struct trapframe *tf) where will you find each of the three arguments (in which registers) and how will you return the 64-bit offset?

• arg0 (file handle, 32-bit) is found in the a0 register.
• arg1 (offset, 64-bit):
  • Lower 32 bits are stored in a2.
  • Upper 32 bits are stored in a3.
  • If registers are insufficient, additional arguments can be fetched from the user stack, starting at sp+16 for the lower 32 bits and sp+20 for the upper 32 bits.
• arg2 (whence, 32-bit) is found on the user stack at sp+16.

To return the 64-bit offset value:

• v0 holds the lower 32 bits of the return value.
• v1 holds the upper 32 bits of the return value.

15. As you were reading the code in runprogram.c and loadelf.c, you probably noticed how the kernel manipulates the files. Which kernel function is called to open a file? Which macro is called to read the file? What about to write a file? Which data structure is used in the kernel to represent an open file?

Kernel function to open a file: The kernel function to open a file is vfs_open(). In runprogram(), the file is opened with the call vfs_open(progname, O_RDONLY, 0, &v);, where O_RDONLY specifies read-only mode.

Macro to read a file: The macro to read a file is VOP_READ(). In loadelf.c, it is used in load_segment() with the call VOP_READ(v, &u); to read data from the file.

Macro to write a file: Although not explicitly used in the provided code, the macro to write a file is VOP_WRITE(), which functions similarly to VOP_READ() but for writing.

Data structure representing an open file in the kernel: The kernel uses the struct vnode data structure to represent an open file. In runprogram.c, a vnode represents the opened program file, stored in the variable v.

16. What is the purpose of VOP_INCREF and VOP_DECREF?

VOP_INCREF: Increases the reference count of a file (or vnode) to indicate that it is in use. This prevents the file from being released while it is still being accessed.

VOP_DECREF: Decreases the reference count of a file. When the count reaches zero, it indicates that the file is no longer in use, allowing the kernel to safely release its resources.

Design and implementation

The system calls you need to implement in this assignment are:

open(), read(), write(), lseek(), close(), dup2(), chdir(), and __getcwd()

How to begin:

1. Take a look at kern/test/fstest.c to learn about the functions available in the kernel for manipulating files. Another place to look for useful function is in the kern/vfs directory. These functions will be very helpful to you when implementing the solution to this assignment.
2. Carefully study kern/arch/mips/syscall/syscall.c. Look at the existing system calls as well as the comments at the top of this file. They will tell you exactly how to pass the arguments in and out of the system calls.

Things become even more complicated in Assignment 5, where you'll need to implement fork(), which dictates that the file objects be shared between the parent and child processes; since these can run concurrently, you will need some careful synchronization! Though you don't need to worry about this for the current assignment, designing your file-tracking system with Assignment 5 in mind might make your life easier later.

That is to say, different processes that run concurrently may share the same file handle. Besides, although in this assignment we assume each process only has one thread, it is strongly recommended that we take multi-threaded processes into account in order to make our code more robust.

Important: Before sitting down to write code, get together with your partner and write down the following for every system call:

• the arguments it takes
• the return values it might return
• the errors it must check for
• the information it needs to access and update inside the file table
• the functions and macros available in os161 that you can use for its implementation
• the potential race conditions and how they must be prevented (assume no user-level threads for this assignment).

For now, make the menu thread go away by having it block on some semaphore or run an infinite while loop after it launches the user program.

My Solution

Task: Implement open(), read(), write(), lseek(), close(), dup2(), chdir(), and __getcwd() system calls.

Kernel structure for open files

All the system calls that we implemented here are interact with files. So we first need to implement the OS/161 kernel structure for managing open files, including the file descriptor table and file handles.

Details of OS/161 kernel structure for open files are shown below:

Kernel three-table data structure for open files:

• Table1: Process table

Each process entry in the process table contains a file description table(a table of open file descriptors).

• Table2: Open file table

The file descriptors index the entries in the file description table. Each entry contains a pointer to an entry in the open files table(a table that the kernel maintains for all open files).

Each entry in this open files table contains the file status flags (read, write, append, etc.), the current file offset, and a pointer to the entry for this file in the so-called v-node table.

• Table3: V-node table

The v-node table (or part of it) is stored on the physical device. For now, you can think of its entries as the "real'' file contents on a disk, with associated informations like file location on disk, size, name, owner, etc.

What if two processes want to independently open the same physical file, i.e. with each process maintaining its own access mode (read, write or append) and file offset as well?

Here the open files table has two independent entries for the same file, each associated to one of the processes.

What if we need to have in one process two file descriptors opened for the same file?

Duplication of file descriptors:

How we achieve this?

The dup() and dup2() system calls do this job.

/* duplicate the passed file descriptor, returning the smallest available one. */
int dup(int fildes);
/* specify in what file descriptor you want the copy */
int dup2(int fildes, int fildes2);

Why we need the duplication of file descriptors?

Example:

...
    if (fork()==0)
    {
        close(STDIN_FILENO); 
        dup(datafd); /* datafd duplicated in stdin */
        execlp("sed", "sed", (char *)0);
        perror("sed");
    }

By duplicating datafd to stdin, we ensure sed can read from our desired file.

What is the problem of dup()? How we solve this?

The close-and-duplicate sequence above is not atomic. We can fix this with dup2:

...
if (fork()==0)
{
    /* atomic operation */
    dup2(datafd, STDIN_FILENO);
    execlp("sed", "sed", (char *)0);
    perror("sed");
}

Take time to fully understand the contents above before implementing your file descriptor table and file handle structures.

/* File handle structure */
struct filehandle {
    struct vnode *vn;       // Pointer to the v-node
    off_t offset;           // Current file offset
    unsigned int refcount;  // Reference count
    int flags;              // file status flags
    struct lock *fh_lock;   // Lock for the file handle
};

/* Per-process file descriptor table */
struct filetable {
    struct filehandle *file_handles[OPEN_MAX];
    struct lock *ft_lock;  // Lock for the file descriptor table
};

Notice that although in this lab we assume each process only has one thread, adding a lock to the file descriptor table makes our code more robust.

Besides implementing the actual file table and file handle structure, we also need to implement some functions with which the system calls can perform operations on the file system.

Think about what those functions are needed? Also within those functions, what kinds of synchronization do we need?

You can first write some functions that come to mind after you finish implementing the file table and file handle structure, and gradually add more functions while trying to implement the file-related system calls.

Here I show all the functions I need to operate on the file tables and file handles:

/* File descriptor table functions */
struct filetable *filetable_create(void);
void filetable_stdio_init(struct filetable *ft);
void filetable_destroy(struct filetable *ft);
int filetable_add(struct filetable *ft, struct filehandle *fh);
int filetable_remove(struct filetable *ft, int fd);
struct filetable *filetable_copy(struct filetable *old_ft);

/* File handle functions */
struct filehandle *create_stdio_handle(const char *device, int flags);
struct filehandle *filehandle_create(struct vnode *vn, int flags);
void filehandle_destroy(struct filehandle *fh);
void filehandle_incref(struct filehandle *fh);
void filehandle_decref(struct filehandle *fh);

//////////////////////////////////////////////////
//
// File descriptor table functions

/**
 * @brief Create a new file descriptor table.
 *
 * This function allocates memory for a new file descriptor table and initializes it by creating a lock
 * for synchronization. It also initializes the file handles array with standard I/O.
 *
 * @return A pointer to the newly created file descriptor table, 
 * or NULL if memory allocation fails or if the lock creation fails.
 */
struct filetable *
filetable_create(void)
{
    struct filetable *ft = kmalloc(sizeof(struct filetable));
    if (ft == NULL)
    {
        return NULL;
    }

    ft->ft_lock = lock_create("filetable_lock");
    if (ft->ft_lock == NULL)
    {
        kfree(ft);
        return NULL;
    }

    for (int i = 0; i < OPEN_MAX; i++)
    {
        ft->file_handles[i] = NULL;
    }

    return ft;
}

void filetable_stdio_init(struct filetable *ft) {
    // Initialize standard I/O
    struct filehandle *stdin_handle = create_stdio_handle("con:", O_RDONLY);
    struct filehandle *stdout_handle = create_stdio_handle("con:", O_WRONLY);
    struct filehandle *stderr_handle = create_stdio_handle("con:", O_WRONLY);

    KASSERT(stdin_handle != NULL);
    KASSERT(stdout_handle != NULL);
    KASSERT(stderr_handle != NULL);

    int fd0 = filetable_add(ft, stdin_handle);
    int fd1 = filetable_add(ft, stdout_handle);
    int fd2 = filetable_add(ft, stderr_handle);

    KASSERT(fd0 == 0);
    KASSERT(fd1 == 1);
    KASSERT(fd2 == 2);
}

/**
 * @brief Destroy the file descriptor table.
 * 
 * This function releases all file handles in the file descriptor table by decrementing their reference counts
 * and setting them to NULL. It also destroys the lock associated with the file descriptor table and frees the memory.
 * 
 * @param ft The file descriptor table to be destroyed.
 */
void filetable_destroy(struct filetable *ft)
{
    KASSERT(ft != NULL);

    lock_acquire(ft->ft_lock);
    for (int i = 0; i < OPEN_MAX; i++)
    {
        if (ft->file_handles[i] != NULL)
        {
            filehandle_decref(ft->file_handles[i]);
            ft->file_handles[i] = NULL;
        }
    }
    lock_release(ft->ft_lock);

    lock_destroy(ft->ft_lock);
    kfree(ft);
}

/**
 * @brief Add an entry to the process's file descriptor table that 
 * maps a new file descriptor to this file handle.
 *
 * @param ft The file descriptor table to add the file handle to.
 * @param fh The file handle to add.
 *
 * @return The assigned file descriptor for the file handle, 
 * or -1 if the file descriptor table is full.
 */
int filetable_add(struct filetable *ft, struct filehandle *fh)
{
    int fd = -1;
    lock_acquire(ft->ft_lock);

    // Find the first available file descriptor
    for (int i = 0; i < OPEN_MAX; i++)
    {
        if (ft->file_handles[i] == NULL)
        {
            ft->file_handles[i] = fh;
            filehandle_incref(fh);
            fd = i;
            break;
        }
    }

    lock_release(ft->ft_lock);
    return fd;
}

/**
 * @brief Remove a file handle from the file descriptor table.
 *
 * This function removes the file handle associated with the specified
 * file descriptor from the file descriptor table by decrementing its
 * reference count and setting the entry to NULL. The operation is
 * protected by a lock to ensure thread safety.
 *
 * @param ft The file descriptor table to remove the file handle from.
 * @param fd The file descriptor whose associated file handle is to be removed.
 * @return 0 on success, or EBADF if the file descriptor is not valid.
 */
int filetable_remove(struct filetable *ft, int fd)
{
    if (fd < 0 || fd >= OPEN_MAX)
    {
        return EBADF;
    }

    lock_acquire(ft->ft_lock);
    if (ft->file_handles[fd] != NULL)
    {
        filehandle_decref(ft->file_handles[fd]);
        ft->file_handles[fd] = NULL;
    }
    else {
        lock_release(ft->ft_lock);
        return EBADF;
    }
    lock_release(ft->ft_lock);
    
    return 0;
}

/**
 * Creates a copy of an existing file table.
 *
 * This function is typically used during process forking. It allocates
 * memory for a new file table structure, copies all entries from the old
 * file table to the new one, increments the reference count for each file
 * handle in the new table, and creates new synchronization primitives for
 * the new table.
 *
 * @param old_ft Pointer to the file table to be copied.
 *
 * @return A pointer to the newly created copy of the file table on success,
 *         or NULL if memory allocation fails.
 *
 * @note This function creates a shallow copy of the file handles, meaning
 *       the actual file state is shared between the original and the copy.
 */
struct filetable *
filetable_copy(struct filetable *old_ft)
{
    KASSERT(old_ft != NULL);

    struct filetable *new_ft = filetable_create();
    if (new_ft == NULL) {
        return NULL;
    }

    lock_acquire(old_ft->ft_lock);
    lock_acquire(new_ft->ft_lock);

    for (int i = 0; i < OPEN_MAX; i++) {
        if (old_ft->file_handles[i] != NULL) {
            new_ft->file_handles[i] = old_ft->file_handles[i];
            new_ft->file_handles[i]->refcount++;
        }
    }

    lock_release(new_ft->ft_lock);
    lock_release(old_ft->ft_lock);

    return new_ft;
}


//////////////////////////////////////////////////
//
// File handle functions

/**
 * @brief Create a file handle for standard I/O.
 * 
 * @param device The device name (e.g., "con:")
 * @param flags The flags for opening the device
 * @return The newly-create file handle
 */
struct filehandle *
create_stdio_handle(const char *device, int flags)
{
    struct vnode *vn;
    int result = vfs_open(kstrdup(device), flags, 0, &vn);
    KASSERT(result == 0);
    
    struct filehandle *fh = kmalloc(sizeof(struct filehandle));
    KASSERT(fh != NULL);
    
    fh->vn = vn;
    fh->offset = 0;
    fh->refcount = 0;
    fh->flags = flags;
    fh->fh_lock = lock_create("file_handle_lock");
    KASSERT(fh->fh_lock != NULL);
    
    return fh;
}

/**
 * @brief Create a new file handle.
 *
 * This function allocates memory for a new file handle and initializes it with the provided vnode
 * and flags. It also initializes the file handle's offset, reference count, and file status flags. 
 * Additionally, it creates a lock for the file handle for synchronization purposes.
 * 
 * @param vn The vnode associated with the file handle.
 * @param flags The file status flags for the file handle.
 * @return A pointer to the newly created file handle.
 */
struct filehandle *
filehandle_create(struct vnode *vn, int flags)
{
    struct filehandle *fh = kmalloc(sizeof(struct filehandle));
    KASSERT(fh != NULL);

    fh->vn = vn;
    fh->offset = 0;
    fh->refcount = 0;
    fh->flags = flags;
    fh->fh_lock = lock_create("file_handle_lock");
    KASSERT(fh->fh_lock != NULL);

    return fh;
}

/**
 * @brief Destroy a file handle.
 *
 * This function closes the vnode associated with the file handle, destroys the lock associated with the file handle, and
 * frees the memory allocated for the file handle.
 * It is called when the reference count of a file handle reaches 0 and the lock for the file handle is locked.
 *
 * @param fh The file handle to be destroyed.
 */
void filehandle_destroy(struct filehandle *fh)
{
    KASSERT(fh != NULL);
    KASSERT(lock_do_i_hold(fh->fh_lock));

    vfs_close(fh->vn);
    lock_release(fh->fh_lock);
    lock_destroy(fh->fh_lock);
    kfree(fh);
}

/**
 * @brief Increment the reference count of a file handle.
 *
 * This function increments the reference count of a file handle, which is used to determine when a file handle can be
 * safely destroyed. The reference count is incremented atomically to ensure the integrity of the file handle.
 *
 * @param fh The file handle whose reference count to increment.
 */
void filehandle_incref(struct filehandle *fh)
{
    KASSERT(fh != NULL);

    lock_acquire(fh->fh_lock);
    fh->refcount++;
    lock_release(fh->fh_lock);
}

/**
 * @brief Decrement the reference count of a file handle.
 *
 * This function decreases the reference count of the provided file handle.
 * If the reference count reaches zero, the file handle is destroyed, 
 * releasing any resources associated with it. The function is protected
 * by a lock to ensure thread safety during the operation.
 * 
 * @param fh The file handle whose reference count is to be decremented.
 */
void filehandle_decref(struct filehandle *fh)
{
    KASSERT(fh != NULL);

    lock_acquire(fh->fh_lock);
    fh->refcount--;
    if (fh->refcount == 0)
    {
        filehandle_destroy(fh);
        return;
    }
    lock_release(fh->fh_lock);
}

After implementing the file descriptor table and functions to operate on it, we need to add the filetable to the proc structure, create the file descriptor table during process creation and clean the file descriptor table during process destruction.

Notice that in OS/161, there are two ways to create a process:

1. By fork system call

   we will implement the proc_create_fork function in the next assignment. Since the child process share the same file descriptor table with the parent process, we just need to copy the entire filetable to the new process. That is why we need a filetable_copy function.

2. By proc_create_runprogram

   This function is used to create the first user process for the new program to run in. Since this is the first user process created, we need to initialize the standard I/O in its file descriptor table. Therefore, we need to call filetable_stdio_init in proc_create_runprogram.

Notice that in either way, we first need to call the proc_create function to create a initial proc structure.

System calls (From system call API to Disk)

Have the kernel structure for managing open files at hand, now it's time to write some file-related system calls!

Things to think about before coding:

What functions can we use to help us implementing those system calls?

Focus on functions that are responsible for VOP operations(operate on vnode) and VFS layer operations(translate operations on abstract on-disk files to operations on specific filesystems).

What kind of synchronizations do we need to implement in the kernel for those system calls?

Notice that for this assignment, we assume each process has only one thread. However, different processes may share the same file handle and can run concurrently.

What kinds of errors should each system call return?

Read the OS/161 system calls man page carefully and look up the error types in errno.h.

sys_open

How to copy the filename string from user space into kernel space.

Use the copyinstr function to copy the filename from user space to kernel space.

What function is used to actually open the file?

We need to use the vfs functions to interact with vnode. Once we have the vnode, we can create the file handle that points to the vnode and add the file handle to the current process's file descriptor table.

int sys_open(const_userptr_t filename, int flags, mode_t mode, int32_t *retval)
{
    char kfilename[PATH_MAX];
    size_t actual_len;
    int result;

    /* Copy the filename from user space to kernel space */
    result = copyinstr(filename, kfilename, PATH_MAX, &actual_len);
    if (result)
    {
        return result;      // Indicate failure
    }

    /* Open the file */
    struct vnode *vn;
    result = vfs_open(kfilename, flags, mode, &vn);
    if (result)
    {
        return result;      // Indicate failure
    }

    /* Create the file handle */
    struct filehandle *fh;
    fh = filehandle_create(vn, flags);
    KASSERT(fh != NULL);

    /* Add the file handle to the file descriptor table */
    int fd = filetable_add(curproc->p_ft, fh);
    if (fd == -1)
    {
        filehandle_decref(fh);
        return EMFILE;      // Indicate failure
    }

    *retval = fd;
    return 0;
}

sys_close

What functions in filetable can we use to close a file? How can we implement that function in filetable?

We need to use the vfs_close to decrement the refcount in vnode.

We also need to decrease the refcount of filehandle and remove filehandle from filetable.

int
sys_close(int fd)
{   
    /* Check if the file descriptor is valid */
    if (fd < 0 || fd >= OPEN_MAX) {
        return EBADF;       // Indicate failure
    }
    
    /* Get the current process's file descriptor table */
    struct filetable *ft = curproc->p_ft;
    KASSERT(ft != NULL);

    /* Remove the file handle from the file descriptor table */
    int result = filetable_remove(ft, fd);
    if (result) {
        return result;      // Indicate failure
    }
    
    return 0;
}

sys_read and sys_write

Those two system calls' implementations are very similar.

What synchronization problems can we face in the read/write system calls?

Imagine two processes using the same file handle reading/writing from/to the same file concurrently. Therefore, we need to lock the file handle while reading as well as writing.

To mention it again, although in this lab we assume each process only has one thread, it is strongly recommended that we lock the file descriptor table while we are trying to get the file handle to make our code more robust.

What structures and functions should we use to actually read/write from/to a file.

We read/write from/to a vnode, so we should use VOP operation to read/write from/to a vnode.

Since vnode is the abstract representation of the file on disk, we also need some kind of I/O structure to describe the I/O operation(read/write).

That is the uio structure! Just to clarify, the uio structure is used just to describe the I/O operation, not to hold the actual data to be transferred. The VOP I/O operation use this information to transfer data directly from/to the disk.

int sys_read(int fd, userptr_t buf_ptr, size_t nbytes, int32_t *retval)
{
    struct filetable *ft;
    struct filehandle *fh;
    struct iovec iov;
    struct uio u;
    int result;

    // Check if file descriptor is valid
    if (fd < 0 || fd >= OPEN_MAX)
    {
        return EBADF;
    }

    // Get the file descriptor table of the current process
    ft = curproc->p_ft;
    KASSERT(ft != NULL);

    // Get the file handle from the file descriptor table
    lock_acquire(ft->ft_lock);
    fh = ft->file_handles[fd];
    if (fh == NULL)
    {
        lock_release(ft->ft_lock);
        return EBADF;
    }

    // Acquire the lock for the file handle
    lock_acquire(fh->fh_lock);
    lock_release(ft->ft_lock);

    // Check if the file is opened for reading
    if ((fh->flags & O_ACCMODE) == O_WRONLY)
    {
        lock_release(fh->fh_lock);
        return EBADF;
    }

    // Set up the uio structure
    uio_kinit(&iov, &u, (void *)buf_ptr, nbytes, fh->offset, UIO_READ);
    u.uio_segflg = UIO_USERSPACE;
    u.uio_space = curproc->p_addrspace;

    // Perform the read operation
    result = VOP_READ(fh->vn, &u);

    if (result)
    {
        lock_release(fh->fh_lock);
        return result;
    }

    // Update the file offset
    fh->offset = u.uio_offset;

    // Calculate the number of bytes actually read
    *retval = nbytes - u.uio_resid;

    // Release the lock for the file handle
    lock_release(fh->fh_lock);

    return 0;
}

int sys_write(int fd, const_userptr_t buf_ptr, size_t nbytes, int32_t *retval)
{
    struct filetable *ft;
    struct filehandle *fh;
    struct iovec iov;
    struct uio u;
    int result;

    // Check if file descriptor is valid
    if (fd < 0 || fd >= OPEN_MAX)
    {
        return EBADF;
    }

    // Get the file descriptor table of the current process
    ft = curproc->p_ft;
    KASSERT(ft != NULL);

    // Get the file handle from the file descriptor table
    lock_acquire(ft->ft_lock);
    fh = ft->file_handles[fd];
    if (fh == NULL)
    {
        lock_release(ft->ft_lock);
        return EBADF;
    }

    // lock the file handle
    lock_acquire(fh->fh_lock);
    lock_release(ft->ft_lock);

    // Check if the file is opened for writing
    if ((fh->flags & O_ACCMODE) == O_RDONLY)
    {
        lock_release(fh->fh_lock);
        return EBADF;
    }

    // Set up the uio structure
    uio_kinit(&iov, &u, (void *)buf_ptr, nbytes, fh->offset, UIO_WRITE);
    u.uio_segflg = UIO_USERSPACE;
    u.uio_space = curproc->p_addrspace;

    // Perform the write operation
    result = VOP_WRITE(fh->vn, &u);

    if (result)
    {
        lock_release(fh->fh_lock);
        return result;
    }

    // Update the file offset
    fh->offset = u.uio_offset;
    *retval = nbytes - u.uio_resid;

    // Release the lock for the file handle
    lock_release(fh->fh_lock);

    return 0;
}

sys_lseek

Check the man page to understand how to calculate the new file offset given the parameter whence.

What synchronization problems can we face in the lseek system call?

Like read/write, imagine two processes using the same file handle seeking to different locations. We need to lock the file handle while seeking. Like mentioned before, it is strongly recommended that we also lock the file descriptor table while trying to get the file handle to support multi-threaded processes, making our code more robust.

How to check if the file supports seeking and how to know the size of the file?

Those all interact with vnode, so we need to use VOP operations.

When implementing sys_lseek, pay close attention to where you can find its parameters and how to pass its return value. If you are confused, review the coding reading exercises Q14.

int
sys_lseek(int fd, off_t pos, int whence, off_t *retval)
{
    struct filetable *ft;
    struct filehandle *fh;
    struct stat st;
    off_t new_pos;
    int result;

    // Check if file descriptor is valid
    if (fd < 0 || fd >= OPEN_MAX) {
        return EBADF;
    }

    // Get the file descriptor table of the current process
    ft = curproc->p_ft;
    KASSERT(ft != NULL);

    // Get the file handle from the file descriptor table
    lock_acquire(ft->ft_lock);
    fh = ft->file_handles[fd];
    if (fh == NULL) {
        lock_release(ft->ft_lock);
        return EBADF;
    }

    // Acquire the lock for the file handle
    lock_acquire(fh->fh_lock);
    lock_release(ft->ft_lock);

    // Check if the file supports seeking
    if (!VOP_ISSEEKABLE(fh->vn)) {
        lock_release(fh->fh_lock);
        return ESPIPE;
    }

    // Calculate the new position based on whence
    switch (whence) {
        case SEEK_SET:
            new_pos = pos;
            break;
        case SEEK_CUR:
            new_pos = fh->offset + pos;
            break;
        case SEEK_END:
            // Get the file size
            result = VOP_STAT(fh->vn, &st);
            if (result) {
                lock_release(fh->fh_lock);
                return result;
            }
            new_pos = st.st_size + pos;
            break;
        default:
            lock_release(fh->fh_lock);
            return EINVAL;
    }

    // Check if the new position is valid
    if (new_pos < 0) {
        lock_release(fh->fh_lock);
        return EINVAL;
    }

    // Update the file offset
    fh->offset = new_pos;

    // Release the lock for the file handle
    lock_release(fh->fh_lock);

    // Set the return value
    *retval = new_pos;

    return 0;
}

sys_dup2

The dup process is really simple. We just make the newfd point to the same file handle as the oldfd and increase the filehandle refcount.

What synchronization problems can we face in the dup2 system call?

dup2 operates on file descriptors. Since each process has its own file descriptor table, we won't need to worry about synchronization problems between processes. However, to make our code more robust, it is strongly recommended that we take multi-threaded processes into account.

Imagine two threads within the same process use dup2 to operate on the same file descriptor at the same time. We need to lock the file descriptor table during the dup process.

int sys_dup2(int oldfd, int newfd, int32_t *retval)
{
    struct filetable *ft;
    struct filehandle *old_fh, *new_fh;

    // Check validity of file descriptors
    if (oldfd < 0 || oldfd >= OPEN_MAX || newfd < 0 || newfd >= OPEN_MAX)
    {
        return EBADF;
    }

    // Get the current process's file descriptor table
    ft = curproc->p_ft;
    KASSERT(ft != NULL);

    // If oldfd and newfd are the same, return success immediately
    if (oldfd == newfd)
    {
        *retval = newfd;
        return 0;
    }

    // Acquire the lock for the file descriptor table
    lock_acquire(ft->ft_lock);

    // Get the file handle for oldfd
    old_fh = ft->file_handles[oldfd];
    if (old_fh == NULL)
    {
        lock_release(ft->ft_lock);
        return EBADF;
    }

    // Get the file handle for newfd
    new_fh = ft->file_handles[newfd];

    // Check if newfd is already open, if so, close it
    if (new_fh != NULL)
    {
        filehandle_decref(new_fh);
        ft->file_handles[newfd] = NULL;
    }

    // Add old_fh to newfd
    ft->file_handles[newfd] = old_fh;
    filehandle_incref(old_fh);

    // Release the lock for the file decriptor table
    lock_release(ft->ft_lock);

    // Set the return value
    *retval = newfd;

    return 0;
}

sys___getcwd and sys_chdir

What function should we use to get the current working directory?

Getting the current working directory is like reading from a file. Changing the working directory is like writing to a file. Therefore, we still need the uio structure describe the I/O operation. The working directory of the process is associated with specific file systems. Therefore, we need to use vfs layer functions to interact with the file system.

To get the current working directory(cwd):

Take a look at uio_kinit, the uio structure is initiated with a kernel buffer. Therefore, we need to first read the cwd into a kernel buffer and then use copyout to copy the data to user buffer.

To change the current working directory(cwd):

We first need to use copyinstr to copy the pathname into a kernel buffer kpath and use kpath to do the work.

int
sys___getcwd(userptr_t buf, size_t buflen, int32_t *retval)
{
    struct iovec iov;
    struct uio u;
    void *kbuf;
    int result;

    // Handle zero-length buffer
    if (buflen == 0) {
        *retval = 0;
        return 0;
    }

    // Allocate kernel buffer
    kbuf = kmalloc(buflen);
    KASSERT(kbuf != NULL);

    // Set up the uio structure
    uio_kinit(&iov, &u, kbuf, buflen, 0, UIO_READ);

    // Perform the getcwd operation
    result = vfs_getcwd(&u);
    if (result) {
        kfree(kbuf);
        return result;
    }

    // Calculate the number of bytes actually read
    *retval = buflen - u.uio_resid;

    // Copy data from kernel space to user space
    result = copyout(kbuf, buf, *retval);

    // Free the kernel buffer
    kfree(kbuf);

    if (result) {
        return result;
    }

    return 0;
}

int
sys_chdir(const_userptr_t pathname)
{
    int result;
    char *kpath;

    // Allocate kernel buffer for the pathname
    kpath = kmalloc(PATH_MAX);
    KASSERT(kpath != NULL);

    // Copy the pathname from user space to kernel space
    result = copyinstr(pathname, kpath, PATH_MAX, NULL);
    if (result) {
        kfree(kpath);
        return result;
    }

    // Do the actual directory change
    result = vfs_chdir(kpath);

    // Free the kernel buffer
    kfree(kpath);

    if (result) {
        return result;
    }

    return 0;
}

syscall.c

The parameters for those system calls lie mainly in the trapframe. The special case is lseek, whose last parameter lies on user stack.

// In `syscall` function
...
	case SYS_open:
		err = sys_open((const_userptr_t)tf->tf_a0, tf->tf_a1, tf->tf_a2, &retval);
		break;

	case SYS_close:
		err = sys_close(tf->tf_a0);
		break;

	case SYS_write:
		err = sys_write(tf->tf_a0, (const_userptr_t)tf->tf_a1, tf->tf_a2, &retval);
		break;

	case SYS_read:
		err = sys_read(tf->tf_a0, (userptr_t)tf->tf_a1, tf->tf_a2, &retval);
		break;

	case SYS_lseek:
	{
		int whence;
		err = copyin((const_userptr_t)(tf->tf_sp + 16), &whence, sizeof(int));
		if (err)
		{
			break;
		}
		err = sys_lseek(tf->tf_a0, ((off_t)tf->tf_a2 << 32) | (off_t)tf->tf_a3, whence, &retval64);
		break;
	}

	case SYS_dup2:
		err = sys_dup2(tf->tf_a0, tf->tf_a1, &retval);
		break;

	case SYS_chdir:
		err = sys_chdir((const_userptr_t)tf->tf_a0);
		break;

	case SYS___getcwd:
		err = sys___getcwd((userptr_t)tf->tf_a0, tf->tf_a1, &retval);
		break;

The return values of those system calls are 32 bits long, with the exception of lseek, whose return value is 64 bits long.

// In `syscall` function
...
if (err)
	{
		/*
		 * Return the error code. This gets converted at
		 * userlevel to a return value of -1 and the error
		 * code in errno.
		 */
		tf->tf_v0 = err;
		tf->tf_a3 = 1; /* signal an error */
	}
	else
	{
		/* Success. */
		tf->tf_v0 = retval;
		tf->tf_a3 = 0; /* signal no error */
		if (callno == SYS_lseek)
		{
			tf->tf_v0 = retval64 >> 32;
			tf->tf_v1 = retval64;
		}
	}

To sum up, we need to carefully pass the parameters to sys_* functions from the trapframe and pass the return values of those system calls to the trapframe where the user process can get them from when going back to user mode.

conf.kern

~/src/kern/conf/conf.kern:

Whenever creating a new file, include it in conf.kern and recompile the kernel.

Finish!

Those are the files I have modified/created. Do not get here unless you are stuck in coding!

We have passed all tests in Assignment4!

OS/161 kernel [? for menu]: p /testbin/badcall
Operation took 0.002373840 seconds
[a-|, 1-4, *, ?=menu, !=quit]
[a] execv                   [b] waitpid                 
[c] open                    [d] read                    
[e] write                   [f] close                   
[g] reboot                  [h] sbrk                    
[i] ioctl                   [j] lseek                   
[k] fsync                   [l] ftruncate               
[m] fstat                   [n] remove                  
[o] rename                  [p] link                    
[q] mkdir                   [r] rmdir                   
[s] chdir                   [t] getdirentry             
[u] symlink                 [v] readlink                
[w] dup2                    [x] pipe                    
[y] __time                  [z] __getcwd                
[{] stat                    [|] lstat                   
[1] asst1                   [2] asst2                   
[3] asst3                   [4] asst4                   
[*] all                     [!] quit                    
Choose: c
(program name unknown): passed: open with NULL path
(program name unknown): passed: open with invalid-pointer path
(program name unknown): passed: open with kernel-pointer path
(program name unknown): passed: open null: with bad flags
(program name unknown): passed: open empty string
Choose: d
(program name unknown): passed: read using fd -1
(program name unknown): passed: read using fd -5
(program name unknown): passed: read using closed fd
(program name unknown): passed: read using impossible fd
(program name unknown): passed: read using fd OPEN_MAX
(program name unknown): passed: read using fd opened write-only
(program name unknown): passed: read with NULL buffer
Unknown syscall 68
(program name unknown): passed: read with invalid buffer
Unknown syscall 68
(program name unknown): passed: read with kernel-space buffer
Unknown syscall 68
Choose: e
(program name unknown): passed: write using fd -1
(program name unknown): passed: write using fd -5
(program name unknown): passed: write using closed fd
(program name unknown): passed: write using impossible fd
(program name unknown): passed: write using fd OPEN_MAX
(program name unknown): passed: write using fd opened read-only
(program name unknown): passed: write with NULL buffer
Unknown syscall 68
(program name unknown): passed: write with invalid buffer
Unknown syscall 68
(program name unknown): passed: write with kernel-space buffer
Unknown syscall 68
Choose: f
(program name unknown): passed: close using fd -1
(program name unknown): passed: close using fd -5
(program name unknown): passed: close using closed fd
(program name unknown): passed: close using impossible fd
(program name unknown): passed: close using fd OPEN_MAX
Choose: s
(program name unknown): passed: chdir with NULL path
(program name unknown): passed: chdir with invalid-pointer path
(program name unknown): passed: chdir with kernel-pointer path
(program name unknown): passed: chdir to empty string
Choose: w
(program name unknown): passed: dup2 using fd -1
(program name unknown): passed: dup2 using fd -5
(program name unknown): passed: dup2 using closed fd
(program name unknown): passed: dup2 using impossible fd
(program name unknown): passed: dup2 using fd OPEN_MAX
(program name unknown): passed: dup2 to -1
(program name unknown): passed: dup2 to -5
(program name unknown): passed: dup2 to impossible fd
(program name unknown): passed: dup2 to OPEN_MAX
(program name unknown): passed: dup2 to same fd
Unknown syscall 82
(program name unknown): passed: lseek fd after dup2 to itself
Choose: z
(program name unknown): passed: getcwd with NULL buffer
(program name unknown): passed: getcwd with invalid buffer
(program name unknown): passed: getcwd with kernel-space buffer
Choose: j
(program name unknown): passed: lseek using fd -1
(program name unknown): passed: lseek using fd -5
(program name unknown): passed: lseek using closed fd
(program name unknown): passed: lseek using impossible fd
(program name unknown): passed: lseek using fd OPEN_MAX
(program name unknown): passed: lseek on device
Unknown syscall 0
(program name unknown): UH-OH: fork failed: Function not implemented
(program name unknown): passed: lseek to negative offset
Unknown syscall 68
(program name unknown): passed: seek past/to EOF
Unknown syscall 68
(program name unknown): passed: lseek with invalid whence code
Unknown syscall 68

We have finished Assignment4!😊