Ancient CS 61 Content Warning!!!!!1!!!
This is not the current version of the class.
This site was automatically translated from a wiki. The translation may have introduced mistakes (and the content might have been wrong to begin with).

Caching, Copying, and Consistency

Cache Semantics

Generally, when we build a cache, we aim for a transparent cache. This means that the cache has the same semantics as the underlying slow storage. This is not always achievable (incoherent cache). Altering the cache semantics to be different from the semantics of the underlying storage may also come with performance gains at the risk of less robust code. We have studied several system calls in the file API.

Based on this interface, what can we conclude about the semantics of the Linux file system API?

 ssize_t read(int fd, void *buf, size_t count)
 // read() attempts to read up to count bytes from file descriptor 
 // fd into the buffer starting at buf

Referring to the manual page for read, we can see that the read system call's semantics are defined as moving into the file buffer by some valid offset from current file pointer. The semantics also define the expected behavior of multiple processes reading and writing to the same file. In Linux, each thread behaves as if it is the only thread accessing a file.

Man page for read

Atomic Effect

Behavior is atomic if it is as if the executing system call is the only system call that is running. The kernel guarantees that system calls are atomic. Note that there is no guarantee about the atomicity of multiple system calls.

For example, if a user wants to read 4 bytes when the file pointer is two bytes from the end, two calls to read are needed (once to read the last two bytes and another time to read the first two bytes of the file). This loses guarantees of atomicity. This means that the second call to read may return data that is has been written by another thread.

Linux File System API

An interesting feature of the Linux and other UNIX operating systems is that everything is a file (or a stream of bytes). The /dev directory, is used to tell users what hardware devices are accessible to their machine. However, each object in the /dev directory is a file. Operations on each of these files translates to operations on the underlying hardware. The /dev directory also contains three special files.

Think about stdin and stdout. Your keyboard input becomes stdin in the computer. We have learned that stdin is mapped to file descriptor 0 and stdout is mapped to file descriptor 2. These interfaces are fundamentally tied to the Linux file system.

However, it is more accurate to think of a file as a stream of bytes. stdout does not behave as if data from your program is being written to a file, and then read from the file to display the final output of your program. Rather, stdout behaves as if output from your program is immediately transferred to your terminal. stdout behaves like a stream of data.

The phrase everything is a file more specifically refers to the idea that everything is a stream of bytes. Each of the three files in the /dev directory mentioned above behave as if they were portals to data streams. Opening the file gives you access to the data stream.

Memory Mapping

The cache hierarchy is structured so that the stdio cache speeds up access to the buffer cache. A user program would conceivably experience performance benefits if they could access the buffer cache directly. This performance gain is the purpose of memory mapped I/O.

Memory mapped I/O allows a user program to have direct shared access to the buffer cache via the same memory. As the name would suggest, memory mapping maps one byte of a file to another byte in faster storage.

 void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset)

mmap will return either MAP_FAILED or a pointer to the successfully mapped area. Successfully mapping memory will save you system calls. For example, if a piece of memory has been mapped, you can access it with memcpy rather than executing a read syscall.

Memory mapping is primarily used with large files. This is because mapped regions are aligned to 4kb. If a file is too small, the cost of mapping more data than necessary may outweigh the benefits of faster access.

Strided Access Patterns

Memory mapping is especially useful for strided access patterns. A strided access pattern is when a program requests B bytes and the file pointer is incremented by a constant, nonzero value between each request. In section, we will study strided access patterns in the context of matrix multiplication.