Assignment 1: Disks

CS23000/33000, CSPP52030 - Operating Systems (Winter 2004).

MWF 10:30pm    Ry251

Due : Tuesday, January 13, 11:59 p.m.

Overview

One of the major challenges of operating system design is the problem of dealing with different types of hardware devices while providing a convenient programming interface for controlling them. In this assignment, you're going to explore this problem by looking at the problem of supporting disk drives. As you are hopefully aware, disk drives come a wide variety of flavors---hard disks, floppy disks, zip disks, CD-ROMS, DVDs, and even flash memory cards (which look like disks). At the lowest level, all disk drives are "block devices." That is, the devices only know how to operate on blocks of data that are typically 512 or 1024 bytes in size. In fact, disks really only have two primary functions: Both functions take a physical block number and a location in memory where the data is located. ReadBlock() retrieves a block of data from the disk and stores it in buffer. WriteBlock() takes the data that's stored at buffer and places it back on the disk.

Although disks are easy to describe, supporting them is more tricky. As mentioned, a wide variety of disk devices could be attached to a system. Moreover, there are a lot of other things that behave like disks, but which aren't (disk images, RAM disks, network storage devices, etc.). This is the problem you're going to look at in more detail.

Get an account

Your first step is to get a CS account. All of your work in this class must take place on a dedicated Sun Solaris machine (stonecrusher.cs.uchicago.edu) as it has been configured for the OS project and provides some additional stability when compared to other machines in the department. Access the machine using 'ssh' from any of the department machines.

Getting started

This assignment is the first stage in a larger file system project. Once you have your class account, you need to set up your project by following these steps.
  1. Log onto stonecrusher.cs.uchicago.edu

  2. Make a project directory
    % mkdir yfs
    

  3. Copy the Makefile into your directory
    % cp /yfs/assign1/Makefile yfs
    

  4. Make a README file that has your name in it.

  5. The contents of the yfs directory should now look like this:
    % ls 
    Makefile
    README
    %
    
  6. Now, in the SAME directory as your Makefile and README files, type the following to create your CVS project:
  7. % cvs import -m "YFS" yfs yfs start
  8. Leave the yfs directory you created and remove it. For example:
  9. unix % cd ..
    unix % rm -rf yfs
  10. Check out your yfs project from CVS as follows:
  11. unix % cvs checkout yfs
    This will create a directory called 'yfs' and it will include the two files you created earlier. Do all of your subsequent work on these files and in this directory.
Do not proceed to the next step until you successfully create a CVS project for your work. Contact the TAs if you are unable to create a project for some reason.

A Disk Interface

Take a look at the file /yfs/include/ydisk.h. This is a C header file that defines an interface that's going to be used to control disk devices. In this file, you'll find 6 functions:
int ReadBlock    (YDISK *disk, int blocknum, void *buffer);
int WriteBlock   (YDISK *disk, int blocknum, void *buffer);
int GetBlockSize (YDISK *disk);
int GetNumBlocks (YDISK *disk);
int SyncDisk     (YDISK *disk);
int ReleaseDisk  (YDISK *disk);
The first two functions are used to read and write blocks (as previously described). The GetBlockSize() and GetNumBlocks() functions merely query a disk to get its physical parameters. SyncDisk is a function that writes all data that hasn't been written to the disk yet (and is typically used with disk caching). ReleaseDisk() is a function that shuts down the disk and releases it. As you will notice, all of the functions take an argument of type YDISK *. This is a pointer to some kind of disk object---a data structure that contains information about the actual disk in question. We'll return to that shortly.

Within the operating system, ALL functions that want to manipulate disks are going to use these 6 functions and only these 6 functions. In this sense, the functions are shielding the rest of the code from having to know the nasty details of how a disk actually works. Of course, your task in this assignment is to implement the 6 functions.

Once you've looked at the interface, you need to create two files. First, create a private header file called ydisk_impl.h. In this header file, you're going to put the definition of the YDISK structure.

/* ydisk_impl.h
   Definition of the YDISK structure */
#ifndef _YDISK_IMPL_H
#define _YDISK_IMPL_H 1

#include "ydisk.h"

struct YDISK {
   /* You'll fill this in as needed */
};

#endif
Next, create a file ydisk.c. This file is going to contain the implementation of the 6 functions above. To start, just make 6 empty functions like this:
/* ydisk.c
   Implementation of the disk interface */

#include "ydisk_impl.h"

int ReadBlock    (YDISK *disk, int blocknum, void *buffer) {
  return Y_ENOSUPP;
}

int WriteBlock   (YDISK *disk, int blocknum, void *buffer) {
  return Y_ENOSUPP;
}

int GetBlockSize (YDISK *disk) {
  return Y_ENOSUPP;
}

int GetNumBlocks (YDISK *disk) {
  return Y_ENOSUPP;
}

int SyncDisk     (YDISK *disk) {
  return Y_ENOSUPP;
}

int ReleaseDisk  (YDISK *disk) {
  return Y_ENOSUPP;
}
Note: The return value Y_ENOSUPP is an error code that means "operation not supported." This is fair enough--since you haven't actually made anything work yet.

Once you've created these files, add them to your CVS project as follows:

% cvs add ydisk.c ydisk_impl.h

Disk Implementation

In the previous section, the "interface" to disks was given. Namely, you were given a small set of functions that were supposed to do things to disks. However, none of these functions make sense by themselves. This is because in order to do anything at all, you actually have to have a disk to work with (and not some weird figment of Dave's imagination).

In this first part of the assignment, you're going to implement two different kinds of disk devices; a RAM disk and a disk image file.

RAM Disks

A RAM disk is a disk device that's built entirely from memory. Essentially, you just take a large buffer of memory and overlay a disk structure on top of it. Most operating systems provide this support (in fact, on Unix, the /tmp directory is typically a RAM disk).

In the file /yfs/include/yramdisk.h you'll find a function definition that creates a RAM disk.

/* Open up a RAM disk */
YDISK *CreateRamDisk(void *buffer, int blocksize, int nblocks, int flags);
It might be used as follows:
void *buffer;
YDISK *d;

buffer = (void *) malloc(512*1000);
d = CreateRamDisk(buffer, 512, 1000, 0);

...
/* Some disk operations */
ReadBlock(d, 13, ...);      /* Read a block from the disk */
WriteBlock(d, 17, ...);     /* Write block 17 to the disk */
... etc ...
You're going to need to implement RAM disks. Create a file ramdisk.c that looks like this:
#include "ydisk_impl.h"

YDISK *CreateRamDisk(void *buffer, int blocksize, int blocks, int flags) {
  /* You need to fill this in */
}
Add the file ramdisk.c to CVS.
% cvs add ramdisk.c

Disk Images

A disk image is a disk device that's built on top of a normal file. For all practical purposes, if you were to take the disk image file and write it to a real disk, it would just "work." In the file /yfs/include/ydiskimage.h you'll find the definitions of two functions for dealing with disk images.
int    CreateDiskImage(const char *filename, int blocksize, int nblocks);
YDISK *OpenDiskImage(const char *filename, int blocksize, int flags);
The CreateDiskImage function is used to create a new disk image file. The OpenDiskImage function is used to open an existing disk image file and treat it as a disk. These functions work kind of like the RAM disk functions.

/* Create a disk image (only first time) */

CreateDiskImage("mydisk.img", 512, 1000);
...

/* Use a disk image file */
YDISK *d;
d = OpenDiskImage("mydisk.img",512, 0);

...
/* Perform some disk operations */
ReadBlock(d, 13, ...);      /* Read a block from the disk */
WriteBlock(d, 17, ...);     /* Write block 17 to the disk */
... etc ...
Create a file diskimage.c that looks like this:
#include "ydisk_impl.h"
#include <unistd.h>
#include <fcntl.h>

int CreateDiskImage(const char *filename, int blocksize, int nblocks) {
  /* You fill this in */
}

YDISK *OpenDiskImage(const char *filename, int blocksize, int flags) {
   /* You fill this in */
}
Add this file to CVS:
% cvs add diskimage.c

Commentary

Notice how there are different functions for creating different kinds of disks. For instance, to create a RAM disk you have to call a special function. To open a disk image, you have to call a different function. However, regardless of what kind of disk is opened, the low-level disk functions work the same. For instance, ReadBlock() just works no matter what kind of disk is being used.

Pre-launch check

Assuming you have followed all of the instructions so far, your directory should contain the following files:
% ls
Makefile
README
diskimage.c
ramdisk.c
ydisk_impl.h
ydisk.c
Type 'make' to see if they build correctly. If you get any errors, fix them. You are now ready to start the real project.

Your challenge

Your task is to provide an implementation of the RAM disk device (ramdisk.c), the disk image device (diskimage.c), and the 6 high-level disk functions (ydisk.c). Furthermore, your solution has the following constraints:

How to do it

The key to this assignment is to understand the meaning of "implementation." To implement the RAM disk and disk image device, you need to implement 6 critical functions for each device. Those 6 functions are (not surprisingly): So, in the file ramdisk.c, you're going to have 6 functions that provide these features for RAM disks. You'll also have 6 similar looking functions in the file diskimage.c.

Finally, to make everything fit together, the file ydisk.c is merely going to dispatch to the correct function depending on what kind of disk it is. Of course, this is a little tricky since the ydisk.c file is not allowed to know anything about RAM disks, disk images, or any other kind of disk for that matter.

Implementation hints

Testing and debugging

To test your disk devices, a special script is available that allows you to interactively manipulate the various functions from a Python interpreter. To do this, type the following:
% /yfs/test/testdisk

Welcome to Dave's evil ydisk tester.  

At the prompt below, you may execute any of the C functions
in ydisk.h, yramdisk.h, and ydiskimage.h

>>> m = malloc(512*1000)
>>> d = CreateRamDisk(m,512,1000,0)
>>> buffer = malloc(512)
>>> ReadBlock(d,0,buffer)
...
The testing program will have a bunch of predefined operations to test various features of your disk devices. We will use this program to test your disk device.

In the early stages of your project, you may want to device other ways to test your code. Consider defining a file 'main.c' and writing a main() function that tests various features as you go.

Handin Procedure

The disk project will be automatically collected from CVS at 11:59 p.m. on the due date. Your project must be checked into a CVS project named 'yfs'. If you made it this far and skipped step 1, shame on you! Go back and read the instructions.

Your final solution to the first assignment should be a directory of files that look like this:

yfs/
     Makefile
     README
     diskimage.c
     ramdisk.c
     ydisk_impl.h
     ydisk.c
To grade your solution, we will run various tests on your program using the /yfs/test/testdisk program.
unix % cvs checkout yfs
unix % cd yfs
unix % make
unix % /yfs/test/testdisk
If your solution fails to check out of CVS, does not build using make, or fails to run, you will receive no credit!

Make sure you test your solution by typing the above commands in some kind of junk directory---do not assume that your solution works until you have tested it yourself!

Grading

Your code will primarily be graded for correctness and style. Your solution should not deviate from the specifications described in this handout (i.e., don't change the name of the files, add additional files, or change the specification of the assignment).

Your grade will consist of the following:

No late handins are accepted!