Caching, Copying, and Consistency
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.
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.
/dev/null: Reading from this file will get you nothing and sending data to this file is the same as throwing it away.
/dev/random: Produces a stream of random numbers. This file is very important in cryptography research.
/dev/zero: Produces a stream of zeroes.
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.
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
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.