Assignment 1: Disks

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

Overview

• ReadBlock(int blocknum, void *buffer)
• WriteBlock(int blocknum, void *buffer)

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

Getting started

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:

% cvs import -m "YFS" yfs yfs start

7. Leave the yfs directory you created and remove it. For example:

unix % cd ..
unix % rm -rf yfs

8. Check out your yfs project from CVS as follows:

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.

A Disk Interface

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);

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

/* 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;
}

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

% cvs add ydisk.c ydisk_impl.h

Disk Implementation

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

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);

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 ...

#include "ydisk_impl.h"

YDISK *CreateRamDisk(void *buffer, int blocksize, int blocks, int flags) {
  /* You need to fill this in */
}

% cvs add ramdisk.c

Disk Images

int    CreateDiskImage(const char *filename, int blocksize, int nblocks);
YDISK *OpenDiskImage(const char *filename, int blocksize, int flags);

/* 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 ...

#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 */
}

% cvs add diskimage.c

Commentary

Pre-launch check

% ls
Makefile
README
diskimage.c
ramdisk.c
ydisk_impl.h
ydisk.c

Your challenge

• No modifications may be made to the header files in /yfs/include. These headers include ydisk.h, yramdisk.h, and ydiskimage.h.

• The file ydisk.c may not contain ANY code that refers to features of RAM disks or disk images. In other words, it is not allowed to directly use any of the functions contained in either ramdisk.c or diskimage.c.

• The file ydisk_impl.h may not contain ANY code related to RAM disks or disk images.

• The files ramdisk.c and diskimage.c must be completely independent of each other (i.e., no shared code and no references to each other).

• Your code must be extensible. For example, if I wanted to add support for SCSI disks, I should be able to add a single file "scsi.c" and have it work without making any modifications to any of your other files.

How to do it

• ReadBlock()
• WriteBlock()
• GetBlockSize()
• GetNumBlocks()
• SyncDisk()
• ReleaseDisk()

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

• The files ramdisk.c and diskimage.c will define the same set of 6 functions for the shared disk operations. Only the low-level implementation details will differ.

• For the disk image device, use the low-level Unix I/O interface to work with files. You should be able to implement the device using nothing more than the following:

  open()
  close()
  read()
  write()
  lseek()
  

• The ramdisk device can be easily implemented using nothing more than the memmove() function that's part of the C library.

• The high-level functions in ydisk.c (i.e., ReadBlock()) are examples of what are known as "polymorphic" functions). That is, whenever you call this function on a disk, its behavior will depend on what kind of disk it is. To implement this, consider defining a structure of function pointers. Perhaps something like this:

  struct DiskMethods {
     int (*read_block)(YDISK *, int, void *);
     int (*write_block)(YDISK *, int, void *);
     int (*blocksize)(YDISK *);
     int (*numblocks)(YDISK *);
     int (*sync)(YDISK *);
     int (*release)(YDISK *);
  };
  

  Then, use this structure to coordinate the interaction between ydisk.c, ramdisk.c, diskimage.c. Hint: this would be part of the YDISK structure that is shared by all three files.

• If you are stuck, post a message on the class mailing list.

Testing and debugging

% /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)
...

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

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

unix % cvs checkout yfs
unix % cd yfs
unix % make
unix % /yfs/test/testdisk

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 grade will consist of the following:

• Correctness. 60%
• Programming style and efficiency. 40%.