2022-06-01 How fast are Linux pipes anyway?

In this post, we will explore how Unix pipes are implemented in Linux by iteratively optimizing a test program that writes and reads data through a pipe.¹

We will begin with a simple program with a throughput of around 3.5GiB/s, and improve its performance twentyfold. The improvements will be informed by profiling the program using Linux’s perf tooling.² The code is available on GitHub.

The post was inspired by reading a highly optimized FizzBuzz program, which pushes output to a pipe at a rate of ~35GiB/s on my laptop.³ Our first goal will be to match that speed, explaining every step as we go along. We’ll also add an additional performance-improving measure, which is not needed in FizzBuzz since the bottleneck is actually computing the output, not IO, at least on my machine.

We will proceed as follows:

1. A first slow version of our pipe test bench;
2. How pipes are implemented internally, and why writing and reading from them is slow;
3. How the vmsplice and splice syscalls let us get around some (but not all!) of the slowness;
4. A description of Linux paging, leading up to a faster version using huge pages;
5. The final optimization, replacing polling with busy looping;
6. Some closing thoughts.

Section 4 is the heaviest on Linux kernel internals, so it might be interesting even if you’re familiar with the other topics treated in the post. For readers not familiar with the topics treated, only basic knowledge of C is assumed.

Let’s begin!

First of all, let’s start with measuring the performance of the fabled FizzBuzz program, following the rules laid down by the StackOverflow post:

% ./fizzbuzz | pv >/dev/null
 422GiB 0:00:16 [36.2GiB/s]

pv is “pipe viewer”, a handy utility to measure the throughput of data flowing through a pipe. So fizzbuzz is producing output at a rate of 36GiB/s.

fizzbuzz writes the output in blocks as big as the L2 cache, to strike a good balance between cheap access to memory and minimizing IO overhead.

On my machine, the L2 cache is 256KiB. Throughout this post, we’ll also output blocks of 256KiB, but without “computing” anything. Essentially, we’ll try to measure the upper bound for programs writing to a pipe with a reasonable buffer size.⁴

While fizzbuzz uses pv to measure speed, our setup will be slightly different: we’ll implement the programs on both ends of the pipe. This is so that we fully control the code involved in pushing and pulling data from the pipe.

The code is available in my pipes-speed-test repo. write.cpp implements the writing, and read.cpp the reading. write repeatedly writes the same 256KiB forever. read reads through 10GiB of data and terminates, printing the throughput in GiB/s. Both executables accept a variety of command line options to change their behavior.

The first attempt at reading and writing from pipes will be using the write and read syscalls, using the same buffer size as fizzbuzz. Here’s a view of the writing end:

This snippet and following ones omit all error checking for brevity.⁵ The memset ensures that the output will be printable, but also plays another role, as we’ll discuss later.

The work is all done by the write call, the rest is making sure that the whole buffer is written. The read end is very similar, but reading data into buf, and terminating when enough has been read.

After building, the code from the repo can be run as follows:

To find out what our program is spending time on, we can use perf:^{6 7}

% perf record -g sh -c './write | ./read'
3.2GiB/s, 256KiB buffer, 40960 iterations (10GiB piped)
[ perf record: Woken up 6 times to write data ]
[ perf record: Captured and wrote 2.851 MB perf.data (21201 samples) ]

The -g instructs perf to record call graphs: this will allow us to take a top-down look at where time is being spent.

We can take a look at where time is spent using perf report. Here is a lightly redacted excerpt, breaking down where write spends its time:⁸

% perf report -g --symbol-filter=write
-   48.05%     0.05%  write    libc-2.33.so       [.] __GI___libc_write
   - 48.04% __GI___libc_write
      - 47.69% entry_SYSCALL_64_after_hwframe
         - do_syscall_64
            - 47.54% ksys_write
               - 47.40% vfs_write
                  - 47.23% new_sync_write
                     - pipe_write
                        + 24.08% copy_page_from_iter
                        + 11.76% __alloc_pages
                        + 4.32% schedule
                        + 2.98% __wake_up_common_lock
                          0.95% _raw_spin_lock_irq
                          0.74% alloc_pages
                          0.66% prepare_to_wait_event

47% of the time is spent in pipe_write, which is what write resolves to if we’re writing to a pipe. This is not surprising — we’re spending roughly half of the time writing, and the other half reading.

Within pipe_write, 3/4 of the time is spent copying or allocating pages (copy_page_from_iter and __alloc_pages). If we already have an idea of how communication between the kernel and userspace works this might make some sense. Regardless, to fully understand what’s happening we must first understand how pipes work.

The operations described above are protected by a lock, which pipe_write acquires and releases as necessary.

pipe_read is the mirror image of pipe_write, except that we consume pages, free them when we’ve fully read them, and update tail.⁹

So, we now have a quite unpleasant picture of what is going on:

• We copy each page twice, once from user memory to the kernel, and back again from the kernel to user memory;
• The copying is done one 4KiB page at a time, interspersed with other activity, such as the synchronization between read and write, and page allocation and freeing;
• We are working with memory that might not be contiguous, since we’re constantly allocating new pages;
• We’re acquiring and releasing the pipe lock.

On this machine, sequential RAM reading clocks at around 16GiB/s:

Luckily, Linux includes system calls to speed things up when we want to move data to and from pipes, without copying. Specifically:

• splice moves data from a pipe to a file descriptor, and vice-versa.
• vmsplice moves data from user memory into a pipe.¹⁰

Crucially, both operations work without copying anything.

Now that we know how pipes work, we can already vaguely imagine how the two operations function: they just “grab” an existing buffer from somewhere and put it into the pipe ring buffer, or the reverse, rather than allocating new pages as needed:

fd is the target pipe, struct iovec *iov is an array of buffers we’ll be moving to the pipe. Note that vmsplice returns how much was “spliced” into the pipe, which might not be the full amount, much like how write returns how much was written. Remember that pipes are bounded by how many slots they have in the ring buffer, and vmsplice is not exempt from this restriction.

We also need to be a bit careful when using vmsplice. Since the user memory is moved to the pipe without copying, we must ensure that the read-end consumes it before we can reuse the spliced buffer.

For this reason fizzbuzz uses a double buffering scheme, which works as follows:

1. Split the 256KiB buffer in two;
2. Set the pipe size to 128KiB, this will have the effect of setting the pipe ring buffer to have 128KiB/4KiB = 32 slots;
3. Alternate between writing to the first half-buffer and using vmsplice to move it to the pipe and doing the same with the other half.

The fact that the pipe size is set to 128KiB, and that we wait for vmsplice to fully output one 128KiB buffer, ensures that by the time we’re done with one iteration of vmsplice we know that the the previous buffer has been fully read — otherwise we would not have been able to fully vmsplice the new 128KiB buffer into the 128KiB pipe.

Now, we’re not actually writing anything to the buffers, but we’ll keep the double buffering scheme since a similar scheme would be required for any program actually writing content.¹¹

Our write loop now looks something like this:

The lion’s share of the time is taken by locking the pipe for writing (__mutex_lock.constprop.0), and by moving the pages into the pipe (iov_iter_get_pages). There isn’t so much we can do about the locking, but we can improve the performance of iov_iter_get_pages.

As the name suggests, iov_iter_get_pages turns the struct iovecs we feed into vmsplice into struct pages to put into the pipe. To understand what this function actually does, and how to speed it up, we must first take a detour into how the CPU and Linux organize pages.

As you might be aware of, processes do not refer to locations in RAM directly: instead, the are assigned virtual memory addresses, which get resolved to physical addresses. This abstraction is known as virtual memory, and has all sorts of advantages we won’t cover here — the most obvious being that it significantly simplifies running multiple processes competing for the same physical memory.

In any case, whenever we execute a program and we load/store from/to memory, the CPU needs to convert our virtual address to a physical address. Storing a mapping from every virtual address to every corresponding physical address would be impratical. Therefore memory is split up in uniformly sized chunks, called pages, and virtual pages are mapped to physical pages:¹²

There’s nothing special about 4KiB: each architecture picks a size, based on various tradeoffs — some of which we’ll soon explore.

To make this a bit more precise, let’s imagine allocating 10000 bytes using malloc:

void* buf = malloc(10000);
printf("%p\n", buf);          // 0x6f42430

As we use them, our 10k bytes will look contiguous in virtual memory, but will be mapped to 3 not necessarily contiguous physical pages:¹³

One of the tasks of the kernel is to manage this mapping, which is embodied in a data structure called the page table. The CPU specifies how the page table looks (since it needs to understand it), and the kernel manipulates it as needed. On x86-64 the page table is a 4-level, 512-way tree, which itself lives in memory.¹⁴ Each node of this tree is (you guessed it!) 4KiB wide, with each entry within the node leading to the next level being 8 bytes (4KiB/8bytes = 512). The entries contain the address of the next node, along with other metadata.

We have one page table per process — or in other words, each process has a reserved virtual address space. When the kernel context-switches to a process, it sets the special register CR3 to the physical address of the root of this tree.¹⁵ Then whenever a virtual address needs to be converted to a physical address, the CPU splits up the address in sections, and uses them to walk this tree and compute the physical address.

To make these concepts less abstract, here’s a visual depiction of how the virtual address 0x0000f2705af953c0 might be resolved to a physical address:

The search starts from the first level, called the “page global directory”, or PGD, the physical location of which is stored in CR3. The first 16 bits of the address are unused.¹⁶ We use the next 9 bits the PGD entry, and traverse down to the second level, “page upper directory”, or PUD. The next 9 bits are used to select an entry from the PUD. The process repeats for the next two levels, PMD (“page middle directory”), and PTE (“page table entry”). The PTE tells where the actual physical page we’re looking for is, and then we use the last 12 bits to find the offset inside the page.

The sparse structure of the page table allows the mapping to be gradually built up as new pages are needed. Whenever a process needs memory, the page table will be updated with a new entry by the kernel.

The struct page data structure is a key piece of this machinery: it is what the kernel uses to refer to a single physical page, storing its physical address and all sorts of other metadata about it.¹⁷ For instance we can get a struct page from the information contained in the PTE (the last level of the page table described above). In general it is used pervasively in all code handling page-related matters.

In the case of pipes, struct page is used to hold their data in the ring buffer, as we’re already seen:

struct pipe_inode_info {
  unsigned int head;
  unsigned int tail;
  struct pipe_buffer *bufs;
};

struct pipe_buffer {
  struct page *page;
  unsigned int offset, len;
};

The time spent in iov_iter_get_pages is really entirely spent in another function, get_user_pages_fast:

% perf report -g --symbol-filter=iov_iter_get_pages
-   17.08%     0.17%  write    [kernel.kallsyms]  [k] iov_iter_get_pages
   - 16.91% iov_iter_get_pages
      - 16.88% internal_get_user_pages_fast
           11.22% try_grab_compound_head

get_user_pages_fast is a more bare-bones version of iov_iter_get_pages:

int get_user_pages_fast(
  // virtual address, page aligned
  unsigned long start,
  // number of pages to retrieve
  int nr_pages,
  // flags, the meaning of which we won't get into
  unsigned int gup_flags,
  // output physical pages
  struct page **pages
)

Here “user” (as opposed to “kernel”) refers to the fact that we’re turning virtual pages into references to physical pages.

To get our struct pages, get_user_pages_fast does exactly what the CPU would do, but in software: it walks the page table to collect all the physical pages, storing the results in struct pages. In our case, we have a 128KiB buffer, and 4KiB pages, so we’ll have nr_pages = 32.¹⁸ get_user_pages_fast will need to walk the page table tree collecting 32 leaves, and storing the result in 32 struct pages.

get_user_pages_fast also needs to make sure that the physical page is not repurposed until the caller doesn’t need it anymore. This is achieved in the kernel using a reference count stored in struct page, which is used to know when a physical page can be released and repurposed in the future. The caller of get_user_pages_fast must, at some point, release the pages again with put_page, which will decrease the reference count.

Finally, get_user_pages_fast behaves differently depending on whether virtual addresses are already in the page table. This is where the _fast suffix comes from: the kernel will first try to get an already existing page table entry and corresponding struct page by just walking the page table, which is relatively cheap, and fall back to producing a struct page by other, more expensive means otherwise. The fact that we memset the memory at the beginning will ensure that we never end up in the “slow” path of get_user_pages_fast, since the page table entries will be created as our buffer is filled with 'X's.¹⁹

Note that the get_user_pages family of functions is not only useful for pipes — in fact, it is central in many drivers. A typical use is related to the kernel bypass we mentioned: a driver for a network card might use it to turn some user memory region into a physical page, then communicate the physical page location to the network card, and have the network card interact directly with that memory region without kernel involvement.

Up to now we’ve presented pages as always being of the same size — 4KiB on x86-64. However, many CPU architectures, including x86-64, include larger page sizes. In the case of x86-64, we not only have 4KiB pages (the “standard” size), but also 2MiB and even 1GiB pages (“huge” pages). In the rest of the post we’ll only deal with 2MiB huge pages, since 1GiB pages are fairly uncommon, and overkill for our task anyway.

The main advantage of huge pages is that bookkeeping is cheaper, since there’s fewer of them needed to cover the same amount of memory. Moreover other operations are cheaper too, such as resolving a virtual address to a physical address, since one level less of page table is needed: instead of having a 12-bit offset into the page, we’ll have a 21-bit offset, and one less page table level.

This relieves pressure on the parts of the CPUs that handle this conversion, leading to performance improvements in many circumstances.²¹ However, in our case, the pressure is not on the hardware that walks the page table, but on its software counterpart which runs in the kernel.

On Linux, we can allocate a 2MiB huge page in a variety of ways, such as by allocating memory aligned to 2MiB and then using madvise to tell the kernel to use huge pages for the provided buffer:

void* buf = aligned_alloc(1 << 21, size);
madvise(buf, size, MADV_HUGEPAGE)

Switching to huge pages in our program yields another ~50% improvement:

% ./write --write_with_vmsplice --huge_page | ./read --read_with_splice
51.0GiB/s, 256KiB buffer, 40960 iterations (10GiB piped)

However, the reason for the improvements is not totally obvious. Naively, we might think that by using huge pages struct page will just refer to a 2MiB page, rather than 4KiB.

Sadly this is not the case: the kernel code assumes everywhere that a struct page refers to a page of the “standard” size for the current architecture. The way this works for huge pages (and in general for what Linux calls “compound pages”) is that a “head” struct page contains the actual information about the backing physical page, with successive “tail” pages just containing a pointer to the head page.

So to represent 2MiB huge page we’ll have 1 “head” struct page, and up to 511 “tail” struct pages. Or in the case of our 128KiB buffer, 31 tail struct pages:²²

Even if we need all these struct pages, the code generating it ends up significantly faster. Instead of traversing the page table multiple times, once the first entry is found, the following struct pages can be generated in a simple loop. Hence the performance improvement!