« Back to the main CS 300 website

Project 3: Caching I/O

Design Discussion due by Friday, March 8th (sign up here)
Project due Friday, March 15th at 6:00 PM EST

Introduction

Caching is the act of putting a small/fast/expensive data store (often called a cache) in front of a large/slow/cheap one. The primary purpose of caching is to increase the performance of data retrieval by storing frequently or recently accessed data within the cache. When data is requested, the system first checks the cache; if the data is found there, it can be retrieved much more quickly than if it had to be fetched from the slower data store.

Indeed, caching is at the heart of many optimizations in computing. Examples include:

1. The storage hierarchy (hard drive → SSD → DRAM → L3-L1 cache → registers), as seen in lectures.
2. Memoization (i.e., saving results of expensive computations for future reuse).
3. Your web browser's cache, which prevents redundant network requests when you access pages you've recently visited.
4. Content Delivery Networks, a technology that prevents long-distance Internet traversals by instead keeping copies of web pages close to users (this is the idea behind Akamai and Cloudflare, two billion-dollar companies!).

In this assignment, you will be speeding up a performance-critical aspect of systems programming: the reading and writing of data to and from a filesystem. To do this, you will use ✨ caching ✨. The file I/O cache you will implement in this project is similar to the CPU cache we already touched upon when we discussed alignment, and which we will discuss again in lecture, with some differences. Notably, the file I/O cache is defined in software, rather than provided by hardware (as CPU caches are). This allows the I/O cache to have variable size. Additionally, it your file I/O cache will have a single fixed-size slot (storing one contiguous segment of the file) rather than multiple slots.

Motivation

Due to the design of Hard Disk Drives (HDD, "disks"), interacting with data on disk involves waiting on several slow physical mechanisms. For example, magnetic hard disks require requests to wait for platters to spin and the metal arms to move to the right place where it can read the data off the disk. Even with modern SSDs, I/O operations on them take much longer than operations on memory. Moreover, I/O requires making system calls to the operating system, which are much slower than normal function calls (for reasons we will discuss soon).

If our programs were required to read and write their data solely from disk, they would be unacceptably slow. We saw an example of this in the form of the diskio-slow program in lecture.

Fortunately, we can do better using caching! If we are willing to sacrifice a small amount of data integrity (i.e., in the event that your computer suddenly loses power, some data is lost), we can gain 100–1,000x in performance. To do this, the computer temporarily holds the data you are using inside of its main memory (DRAM) instead of working directly with the disk. In other words, the main memory (DRAM) acts as a cache for the disk.

Project Description

You will implement an Input/Output (I/O) library that supports operations such as reading data from files (io300_readc and io300_read), writing data to files (io300_writec, io300_write), or moving to a different offset within the file (io300_seek). Your I/O library uses a cache to speed up access to data and reduce the number of disk operations required.

For example, when an application wants to read from a file, it can call your io300_read instead of the system call read. The arguments to io300_read are:

io300_read(struct io300_file* const f, char* const buff, size_t const sz)

f is the file to read from and sz is the number of bytes to read. buff is the application buffer – a region of memory (provided by the caller) where the read bytes should go. In other words, io300_read should write bytes from the data stored in a file (or the cache) into buff. That way, when the io300_read call finishes, the caller can read the bytes returned from buff.

The io300_write function has the same structure:

io300_write(struct io300_file* const f, const char* buff, size_t const sz)

In this case, the caller puts the bytes they want to write into the application buffer buff. They then call io300_write on buff, which writes the first sz bytes of buff to the file f.

Your goal when writing io300_read and io300_write is to introduce an intermediate caching layer to minimize expensive trips to the file on disk.

Here is a visualization of how the application buffer, the cache, and the file interact:

Your approach to implementing this project should be:

1. Read the entire handout as some critical information is located in later sections.
2. Attend a design discussion, where you will discuss a design for your cache data structure with a TA and with your peers. This includes the mechanics of how your cache works and all metadata required to maintain it.
3. Fill out the functions in impl/student.c to implement caching file I/O that conforms to the API specified in io300.h. In addition, you must ensure that make check reports that your implementation is correct, and make perf reports that your implementation is at most 5–10x slower than stdio (the standard library's caching I/O functions) in all cases (see grading rubric).

Project Details

Installation

Ensure that your project repository has a handout remote. Type:

$ git remote show handout

If this reports an error, run:

$ git remote add handout https://github.com/csci0300/cs300-s24-projects.git

Then run:

$ git pull
$ git pull handout main

This will merge our Project 3 (fileio) stencil code with your repository.

Once you have a local working copy of the repository that is up to date with our stencils, you are good to proceed. You'll be doing all your work for this project inside the fileio directory in the working copy of your projects repository.

Stencil/Layout

We provide you with the following files:

In this project, we provide you with a number of existing test programs that do basic file manipulation (see test_programs/*.c). These programs are written in such a way that all interaction with the filesystem is done through the io300_file interface (a series of functions whose signatures are declared in io300.h). This means that if two libraries separately implement the functions in io300.h (potentially quite differently), the test programs will work with either implementation.

We provided you with two implementations, and you will develop a third.

1. The naive implementation (impl/naive.c) reads from and writes directly to the disk without any caching. The initial project stencil is identical to this implementation.
2. The standard I/O implementation (impl/stdio.c) leverages the existing C Standard Library's "buffered" I/O, which does some clever caching.

The speed difference between these two solutions, as measured by running the test programs with each implementation, is astounding! Try it out for yourself:

$ make perf_testdata   # generates 1 MiB performance test file
$ make -B IMPL=naive   # compiles naive implementation
$ time ./byte_cat /tmp/perf_testdata /tmp/testout

real    0m18.515s
user    0m6.819s
sys     0m11.694s

$ make -B IMPL=stdio
$ time ./byte_cat /tmp/perf_testdata /tmp/testout

real    0m0.140s
user    0m0.112s
sys     0m0.028s

The numbers will differ on your computer, but the general relationship (a ~100x performance difference) will hold. (Note that real is the actual time taken (this is called "wall clock time"), while user refers to the part of that time spent in userspace, while sys is the time spent in the kernel.)

In the project, your task is to fill in the third implementation (impl/student.c) and make it perform as close to the stdio implementation as possible.

Getting Started

The core idea behind this project is the following: When a program asks the I/O library to write a byte to a file, instead of immediately going to the disk, put that byte in a cache, then write the entire cache to disk at a later point.

The first thing you should do is look at io300.h to understand the public API that each implementation offers. Next, you should run make -B IMPL=stdio check to run the tests on the implementation we provide (you can also run make -B IMPL=naive check to see how ridiculously slow it is).

The first thing you'll want to do is to work out why the stencil code (and the naive implementation) is so slow. To do so, use a handy tool called strace (for syscall trace), which prints the system calls (calls from your program into the OS) that happen when your program runs.

System calls are expensive: they require changing the processor's privilege mode, lots of safety checks, and they invoke OS code. Moreover, the read or write syscalls often go directly to disk.

Start out by investigating how the naive implementation performs on a 755 byte test file:

$ make -B IMPL=naive
$ strace -e trace=read ./byte_cat test_files/words.rot13.txt /tmp/out
read(3, "\177ELF\2\1\1\0\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\260\v\2\0\0\0\0\0"..., 832) = 832
[...]
read(3, "1", 1)                         = 1
read(3, ".", 1)                         = 1
read(3, "1", 1)                         = 1
read(3, " ", 1)                         = 1
read(3, "V", 1)                         = 1
read(3, "a", 1)                         = 1
read(3, " ", 1)                         = 1
read(3, "g", 1)                         = 1
[...]

The initial lines relate to read() system calls that happen as the OS starts up your executable (which is encoded in a format called "ELF"). You can ignore those lines. At some point, you'll see a lot of lines like read(3, "V", 1) = 1. A line like this means that the program (or, in this case, the I/O library used) invoked the system call read() with arguments 3 (a number that refers to file descriptor), "V", and 1, and that the return value was 1 (as indicated by = 1).

for (int i = 0; i < 1000; i++) {
  write(fd, 'c', 1);
}

char buff[40];
for (int i = 0; i < 1000; i++) {
  buff[i % 40] = 'c';
  if (i % 40 == 39 || i == 999) // if buffer is full
      write(fd, buff, 40);
}

Design Discussion

To succeed at this project, it is crucial that you think conceptually about your design before you write substantial amounts of code. One good way to check a design is to discuss it with someone else. Hence, we ask you to sign up for a design discussion with the course staff. During the design discussion, you will come up with a design together, and will receive feedback on your ideas.

char buffer[5];
io300_file* testFile = io300_open("testfiles/tiny.txt", "tiny!"); 
ssize_t r = io300_read(testFile, buffer, 5);
ssize_t w = io300_write(testFile, "aaa", 3); 
r = io300_read(testFile, buffer, 2);
ssize_t s = io300_seek(testFile, 12);
w = io300_write(testFile, "aaa", 3); 
r = io300_readc(testFile);
io300_close(testFile);

To help you out as you're designing your cache, we'll share what your contents of your file, cache, and return value are after two select lines of code.

Implementing Caching I/O

Now it's time to get coding! Be sure to read the rest of the handout first, however.

Making Progress

One of your early goals should be to get the byte_cat program working for a small text file.

$ touch /tmp/out.txt   # creates empty file
$ make clean all
$ ./byte_cat test_files/tiny.txt /tmp/out.txt
$ cat /tmp/out.txt 
this is a test

The byte_cat program performs no seeks and is the most simple test case you can create. Here is a list of the functions that byte_cat uses: open, close, filesize, readc, writec. We provide all of filesize, and open/close are simple, so you just have to get your reading and writing logic down!

Debugging Tips

Note that the stencil implementation passes all correctness tests, but it is very slow! Additionally, you might find that the performance tests pass locally but not on the grading server. Tests must pass on the grading server to receive credit.

As you work on the project, you will likely break the correctness tests in your quest to improve performance.

If you fail a correctness test, the first thing you will usually want to look into is whether it failed because of a crash in your code (which you can develop using familiar tools such as GDB), or whether it ran, but produced incorrect output. When you see incorrect output file contents, it makes sense to work out how they're incorrect, by looking at the actual bytes in the input and output files! Check out the Debugging section below for some helpful tools, such as xxd and diff.

Make sure your program can handle non-ASCII characters! Not all files consist of text; for example, images or videos can contain arbitrary bytes, including the NUL byte that has special meaning for text, but not in other data.

Additionally, it can also help to look at the output from strace, which lists the system calls that your caching I/O library makes, to see if anything unexpected happens during the test.

If your performance is poor, strace should be your first point of call. Poor performance in this project is almost always explained by your implementation making too many system calls. Running tests under strace will help you understand exactly what sequence of system calls happen, and how many bytes they move into and out of the cache.

Finally, you will likely want to have debug output in your library that you can disable easily when running performance tests, as printf-type functions slow down your program a lot. We provide the helper function dbg() in the stencil for this purpose: you can change the value of the DEBUG_PRINT constant to turn the debug printing code on or off in a single keystroke. dbg() works just like printf(), but if DEBUG_PRINT is set to 0, the compiler will throw away the code in the function and turn it into a no-op.

Consider also writing your own tests if you want to test specific behavior. For more information, look at Testing and Appendix II.

Finishing Up

Once you have a working implementation, test it with make check (correctness) and make perf (performance). You probably won't match stdio on all performance benchmarks yet, but you will meet the performance bar for this project if you achieve the following:

1. Your implementation is within 10x of stdio on the byte_cat benchmarks (byte_cat and reverse_byte_cat).
2. Your implementation is within 5x of stdio on the block_cat tests (block_cat, reverse_block_cat, and random_block_cat).

If you get closer to stdio (or even beat it on some tests), we will award extra credit.

Testing

Overview

make check tests your implementation for correctness. It does this by running all of the test programs with a variety of inputs on random files, and is split into two categories: (1) basic functionality tests, which test the core functionality of your implemented functions and their interactions with one another, and (2) end-to-end tests, which test your implementation with standard file operations (such as copying between files).

Basic functionality tests

The basic functionality tests use the io300_test program. The program randomly generates a single file, which it then opens and performs/tests the specified functions on. The io300_test program verifies that each io300_readc or io300_read call reads the correct bytes from the file, and verifies at the end of the test that all writes are reflected in the final file.

The name of each test specifies the functions tested – for example, readc/writec will perform a combination of io300_readc and io300_writec calls on the same generated file. You can also parse this information from the command that runs the test (io300_test with some arguments), which specifies the test's configuration. (make check prints this command with each test when running.) For instance, for seek_beyond_eof, the testing script runs:

./io300_test readc writec seek -s 0 -m 4096 -n 1000

which specifies that the program will randomly generate a file 0 bytes long (-s 0), which is allowed to grow to a size of 4096 bytes (-m 4096), on which it will then perform 1000 (-n 1000) calls to randomly either io300_readc or io300_writec, each preceded by a call to io300_seek to some location between 0 and the maximum file size. Running just ./io300_test prints a description of the values of these arguments as well.

End-to-end tests

The end-to-end tests use a combination of your io300_* functions within larger programs. Most of these programs operate on separate input and output files, so there will be two caches (one for the input file, one for the output file).

Performance tests

make perf tests your implementation for speed and compares it to stdio on the end-to-end tests.

The performance tests will run very slowly in the unmodified stencil code (e.g., on an M2 Apple MacBook Air, many of the tests take over a minute to run). You will need to make them run faster by implementing caching!

Working with tests

The end-to-end correctness and performance tests will run your implementation on each specified test program using a randomly-generated file of a certain size. For your own personal debugging use, we've provided you with the tools to easily generate these testing files.

Generating test data

If you wish to generate random testing data, use make check_testdata, which generates 80 KiB of data to test for correctness, and make perf_testdata, which generates 1 MiB of data to test for speed. These files will be located at /tmp/check_testdata and /tmp/perf_testdata, respectively.

Running a single test

You can run a single test for performance as follows:

$ make -B IMPL=student
$ make perf_testdata # generates 1 MiB performance test file
$ time ./byte_cat /tmp/perf_testdata /tmp/testout
...

The following is an example of running a simple test for correctness:

$ make check_testdata # generates 80 KiB correctness test file
$ ./byte_cat /tmp/check_testdata /tmp/testout # run test
$ diff /tmp/check_testdata /tmp/testout 
# no output expected, as the files should be the same!

Advanced testing

For a more complex test, you may need to generate intermediate output files. See correctness_tests.py for examples!

$ ./reverse_byte_cat /tmp/check_testdata /tmp/testout # reverse file
$ ./reverse_byte_cat /tmp/testout /tmp/testout2 # reverse file again
$ diff /tmp/check_testdata /tmp/testout2
# no output expected, as the files should be the same!

You may also want to write additional tests to test specific features individually of your code, particularly if you plan to implement extra credit features. For more information, see Appendix II.

Debugging

You may find the following tools (in addition to GDB and sanitizers) helpful in debugging this project.

Helpful Commands

• man displays the authoritative documentation for all functions.

man 2 open
man 2 close
man 2 read
man 2 write
man 2 lseek

• dd if=/dev/urandom ... is used in our test scripts to transfer random binary data into a file.
• wc -c <file> displays the number of bytes in a file.
• du -h <file> also displays the size of a file and is better for large files (it gives human readable byte numbers).
• head -c 40 | xxd or tail -c 40 | xxd will give you a peek at the beginning or end of a file. This is useful for inspecting large files where xxd would normally flood your screen.

Hexdump

xxd <file> allows you to view the contents of binary files. This will be helpful when you have a buggy implementation and you want to see what is going wrong, by printing out what's in your result file. The code below demonstrates an example.

$ echo 'this is ascii' > out.bytes
$ xxd out.bytes
00000000: 7468 6973 2069 7320 6173 6369 690a       this is ascii.
$ dd if=/dev/urandom of=out.bytes bs=32 count=1
1+0 records in
1+0 records out
32 bytes copied, 0.000336055 s, 95.2 kB/s
$ xxd out.bytes 
00000000: 65b7 6c53 69f3 f1ed e6d2 09eb ec66 9403  e.lSi........f..
00000010: f33c e929 d703 314f e7dd 5e6b 56a0 2d28  .<.)..1O..^kV.-(

Diff

diff <file1> <file2> will tell you if the input files differ. This may again be helpful when you have a buggy implementation and you want to figure out where in the output file you're differing from the expected content.

strace

strace, as mentioned above, is a tool that provides diagnostic information about the system calls a program is making. This may be especially helpful when you are trying to improve the performance of your implementation.

$ printf 'int main(){printf("hello world\\n");}' \
>           | gcc -w -x c - && strace ./a.out
execve("./a.out", ["./a.out"], 0x7ffe85175530 /* 26 vars */) = 0
brk(NULL)                               = 0x563c71960000
access("/etc/ld.so.nohwcap", F_OK)      = -1 ENOENT (No such file or directory)
access("/etc/ld.so.preload", R_OK)      = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
fstat(3, {st_mode=S_IFREG|0644, st_size=26696, ...}) = 0
mmap(NULL, 26696, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7f8ee6db4000
close(3)                                = 0
access("/etc/ld.so.nohwcap", F_OK)      = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libc.so.6", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1\1\3\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\20\35\2\0\0\0\0\0"..., 832) = 832
fstat(3, {st_mode=S_IFREG|0755, st_size=2030928, ...}) = 0
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f8ee6db2000
mmap(NULL, 4131552, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x7f8ee67a1000
mprotect(0x7f8ee6988000, 2097152, PROT_NONE) = 0
mmap(0x7f8ee6b88000, 24576, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x1e7000) = 0x7f8ee6b88000
mmap(0x7f8ee6b8e000, 15072, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x7f8ee6b8e000
close(3)                                = 0
arch_prctl(ARCH_SET_FS, 0x7f8ee6db34c0) = 0
mprotect(0x7f8ee6b88000, 16384, PROT_READ) = 0
mprotect(0x563c6fd55000, 4096, PROT_READ) = 0
mprotect(0x7f8ee6dbb000, 4096, PROT_READ) = 0
munmap(0x7f8ee6db4000, 26696)           = 0
fstat(1, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 0), ...}) = 0
brk(NULL)                               = 0x563c71960000
brk(0x563c71981000)                     = 0x563c71981000
write(1, "hello world\n", 12hello world
)           = 12
exit_group(0)                           = ?
+++ exited with 0 +++

$ wc -c test_files/words.rot13.txt 
755 test_files/words.rot13.txt
$ make -B IMPL=naive byte_cat
gcc -ggdb3 -Wall -Wextra -Wshadow -std=gnu11 -fsanitize=address -fsanitize=undefined -fsanitize=leak test_programs/byte_cat.c impl/naive.c -o byte_cat
$ strace ./byte_cat test_files/words.rot13.txt out.txt 2>&1 | grep read | wc -l
804
$ strace ./byte_cat test_files/words.rot13.txt out.txt 2>&1 | grep write | wc -l
758
$ make -B IMPL=stdio byte_cat
gcc -ggdb3 -Wall -Wextra -Wshadow -std=gnu11 -fsanitize=address -fsanitize=undefined -fsanitize=leak test_programs/byte_cat.c impl/stdio.c -o byte_cat
$ strace ./byte_cat test_files/words.rot13.txt out.txt 2>&1 | grep read | wc -l
50
$ strace ./byte_cat test_files/words.rot13.txt out.txt 2>&1 | grep write | wc -l
4

dbg()

Check out the function:

static void dbg(struct io300_file *f, char *fmt, ...)

in impl/student.c. Use it to debug while you are working, and then you can silence its output with one keystroke when you hand in. It acts just like printf(), but it also logs your file's metadata so you can see what is happening as your program executes. When you add fields to your file structure, be sure to include them in the format string after the TODO in dbg(). Here is an example of using it.

int io300_writec(struct io300_file *f, int ch) {
    dbg(f, "writing char: %c\n", ch);
    ...

GDB

As mentioned in previous assignments and in the debugging tips section, GDB is a very useful tool for stepping through your code. To set up gdb for a specific test, you can do the following:

• Run the command gdb [test executable] (e.g., gdb stride_cat)
• Set breakpoints using b [location] (e.g., b io300_read)
• Run r [arguments] (e.g., r test_files/tiny.txt /tmp/out.txt)
  • Note that some tests take in more parameters (for example, block_cat takes in an extra parameter of block size). You can see what parameters each test takes in by running the test executable with no parameters (e.g., ./block_cat).

You may find it helpful to print out the contents of the cache and verify that it matches the steps in your design. See the GDB guide for more useful commands.

Extra Credit

To optimize your implementation and achieve more impressive performance, you can consider some of the following extensions! If you are a graduate student taking CSCI 1310, please implement and document at least one performance optimization.

Adaptive Caching

Easy. Detect the direction of access within a file (are the reads occurring in forward or reverse) and adapting your caching strategy to pre-fetch that memory. Measure how much of an impact adaptive caching has on performance over your basic implementation by creating additional test programs in test_scripts/correctness_tests.py and test_scripts/performance_tests.py. Document how you implemented adaptive caching and its performance impact in your README file.

Diabolical byte_cat

Moderately easy. Check out the diabolical_byte_cat test program. This test program works similarly to byte_cat, but tries to throw off your cache by doing some gratuitous seeks!

Edit test_scripts/correctness_test.py and uncomment diabolical_byte_cat as part of the end-to-end tests (at the bottom of the file), and do the same in test_scripts/performance_test.py. Now optimize your code to handle the situations that this test program creates. Make sure that you still pass the correctness tests, and meet the performance bar for the diabolical_byte_cat performance test.

Detecting Strides

Moderately difficult. Have your cache detect "strides", or access patterns that jump by fixed amounts within a file. For example, reading byte 1, then byte 1001, then byte 2001, and pre-fetching appropriately. Measure how much of an impact detecting strides has on performance over your basic implementation by creating additional test programs in test_scripts/correctness_tests.py and test_scripts/performance_tests.py. Document how you implemented stride detection and its performance impact in your README file.

Memory-Mapped I/O

Difficult. Research "memory-mapped I/O" and how it works, then use it in your implementation when possible. Measure how much of an impact memory-mapped I/O has on performance over your basic implementation by creating additional test programs in test_scripts/correctness_tests.py and test_scripts/performance_tests.py. Document how you implemented memory-mapped I/O and its performance impact in your README file.

Handing In & Grading

Handin instructions

As before, you will hand in your code using Git. In the fileio/ subdirectory of your project repository, you MUST fill in the text file called README.md.

Grading breakdown

• 60% (60 points) for passing the correctness tests. If your tests pass on the grading server with sanitizers, you've probably got all these points. Each basic functionality test is worth 1.5 points, each end-to-end test is worth 3 points, and you get 1.5 points for passing all tests.
• 40% (40 points) for meeting the performance goals: your byte_cat runs must be within 10x of the stdio runtime, and your other runs (block_cat, etc.) must be within 5x of the stdio runtime. Each benchmark is worth 6.5 points, and you get 1 point for passing them all. We will award partial credit if you miss the target but improve over the naive implementation. You will not receive credit for good performance on benchmarks that fail the correctness tests; it is more important to be correct than to be fast.
• Up to 10 points of extra credit for impressive performance optimizations (e.g., matching or beating stdio).

Graduate students taking CSCI 1310 should implement and measure one performance optimization, and describe it in their README. Make sure to cover, in a few sentences, what the optimization is, why you expected it to improve performance, and whether it did or did not improve performance in your experiments.

Now head to the grading server, make sure that you have the "Caching I/O" page configured correctly with your project repository, and check that your tests pass on the grading server as expected.

Congratulations, you've completed the third CS 300 project!

Appendix I: Implementation Swapping

This section explains how our test programs can use different implementations that match the io300.h API.

Consider the following to be our test program:

#include <stdio.h>

// extern means:
//  "I'm not defining this function here, but someone
//   else (another source file) will have to define it
//   before the program is executed"
// 
extern int getRandomNumber();

int main() {
    printf("%d\n", getRandomNumber());
}

Now we want an implementation of the getRandomNumber function that we can link with the test program to produce a fully functional number printer.

// real-rand.c -- delegate to C standard library (man 3 rand)
#include <stdlib.h>

int getRandomNumber() { return rand(); }

// my-rand.c -- our own implementation (very fast)

int getRandomNumber() { return 4; }

Now when we compile the main test program, we have a choice. Since both implementations conform to the same public API (namely, they provide one function getRandomNumber :: void -> int), either can be swapped in and the main program won't know the difference.

$ gcc test-prog.c real-rand.c && ./a.out
16807
$ gcc test-prog.c my-rand.c && ./a.out
4

This is the principle behind the different implementations for this project, but instead of the public API being a single function, it is a family of IO related functions defined in io300.h

At a high level, to test your implementation, we will be doing something like this:

$ gcc our-test-program.c impl/stdio.c && time ./a.out
$ gcc our-test-program.c impl/naive.c && time ./a.out
$ gcc our-test-program.c impl/student.c && time ./a.out

to compare the speed of your implementation against the provided ones.

Appendix II: Writing Custom Tests

While you are certainly not required to design your own tests—passing the autograder tests we provide is more than enough—this assignment has a lot of moving parts! This appendix will help you write custom tests, which you may want to do for testing specific features (e.g. writing) without the requirement of everything else working.

Let's create a test program, student_test.c which opens a file, checks its filesize, and writes out an equivalent number of Zs to an output file.

To create this custom test:

1. Create a new test file, student_test.c, in the test_programs folder:

#include <stdio.h>
#include "../io300.h"

int main(int argc, char *argv[]) {
    /* our test takes 3 arguments: program, infile, and outfile 
     * if the wrong number of arguments is provided, this test fails! */
    if(argc != 3) {
        fprintf(stderr, "usage: %s <in-file> <out-file>\n", argv[0]);
        return 1;
    }
    
    // open our input file, as we need to read its contents
    struct io300_file *in = io300_open(argv[1], "student test infile");
    
    // if our input file doesn't exist, this test fails!
    if (in == NULL) {
        return 1;
    }
    
    // open our output file
    struct io300_file *out = io300_open(argv[2], "student test z-ified outfile");
    
    // if our output file couldn't be opened, this test fails!
    if (out == NULL) {
        io300_close(in);
        return 1;
    }
    
    off_t const filesize = io300_filesize(in);
    // if we can't determine the input filesize, this test fails!
    if (filesize == -1) {
        fprintf(stderr, "error: could not compute filesize\n");
        io300_close(in);
        io300_close(out);
        return 1;
    }
    
    io300_close(in);
    
    // write out our Zs!
    for (int i = 0; i < filesize; i++) {
        // if a write fails, this test fails!
        if(io300_writec(out, 'Z') == -1) {
            fprintf(stderr, "error: write should not fail.\n");
            io300_close(out);
            return 1;
        };
    }
    
    io300_close(out);
    
    // if nothing went wrong, our test passed!
    return 0;
}

2. Add your test name to the Makefile

In order to create the binary for this test, add its name (for this example, student_test) to TEST_PROGRAMS in the project Makefile. This will make sure this new test gets built along with the existing autograder tests when make is run

3. Test\(^2\) – Test your test!

A bad test can be very misleading, leading you to think that your code is failing when in actuality it may be completely correct. Try running your test manually on sample files from test_files, and triple check that everything seems to work as intended.

4. Add your test to the autograder

This project has autograders for both correctness (test_scripts/correctness_test.py) and performance (test_scripts/performance_test.py). Let's add our test to the correctness autograder, as we're testing the results of our write function

Our autograder runs each provided test, and asks two questions: did it pass (i.e. returned 0), and is the output actually correct?

Let's add a new Python function for our test:

def student_test(infile, outfile, outfile2): 
    # create an file equal in size to infile of all Zs (manually);
    # (you don't need to understand this!)
    assert shell_return(f"printf '%*s' $(cat {infile} | wc -c) | tr ' ' 'Z' > {outfile2}") == 0
    
    # check if our test passes, and if the output file is correct
    return shell_return(f'./student_test {infile} {outfile}') == 0 \
        and files_same(outfile, outfile2)

You can see the two parts of our test above. Did it pass? Well, shell_return(f'./student_test {infile} {outfile}') == 0 means an error wasn't raised. Is our output correct? If our manual and generated "Z-files" are the same, we can trust that it is: files_same(outfile, outfile2).

Finally, we can add our new test to our runtests block at the bottom of our autograder file, which handles the execution of each test:

runtests({
    #...other existing tests
    'rot13': rot13,
    #your new test!
    'student_test': student_test
})

5. Run the autograder

Huzzah: your test is complete! Running make check should provide the results of your custom test, which hopefully passes :)

======= CORRECTNESS RESULTS =======
byte_cat: PASSED
[…]
rot13: PASSED
student_test: PASSED

This test was just one sample test you could write. All of our autograder tests are available in test_scripts/, so feel free to reference them in creating your own. Further, the process for adding performance tests is very similar; reference test_scripts/performance_test.py to see the specific syntax used for its tests!

Acknowledgements: The IO project was developed for CS 300.