Debugging your OS: a lesson on memory allocation / Mail.ru Group Blog

It all started, like many other investigations, with a bug report .

The title of the report was quite simple: "When connecting to HTTP, iter_content slowly works with large chunks." A similar name immediately included a siren in my head for two reasons. Firstly, it’s rather difficult to determine what “slow” means here. How slow How big is the “big size”? Secondly, if the described was manifested really seriously, then we would already know about it. The method iter_contenthas been used for a long time, and if it had slowed down significantly in the common user mode, then such information would not have passed by us.

I quickly looked through the report. The author provided few details, but wrote this: "This leads to a 100% processor load and reduces network bandwidth below 1 Mb / s." I grabbed this phrase because it cannot be. Easy downloads with minimal processing are never so slow!

However, all reports of bugs prior to denial deserve investigation. Having talked with the author of the report, I was able to restore the scenario of the manifestation of the bug: if you use Requests with PyOpenSSL and run the following code, the processor will be fully loaded, and network bandwidth will drop to a minimum:

import requests
https = requests.get("https://az792536.vo.msecnd.net/vms/VMBuild_20161102/VirtualBox/MSEdge/MSEdge.Win10_preview.VirtualBox.zip", stream=True)
for content in https.iter_content(100 * 2 ** 20): # 100MB
    pass

This is just a great reproducible script because it clearly points to the Requests stack. The user-supplied code is not executed here: it is part of the Requests library or one of its dependencies; it’s unlikely that this user wrote stupid low-performance code. Real fiction. Using the public URL is even more fantastic. I could execute the script ! And having done this, I ran into a bug. At each execution.

Here was another lovely detail:

At 10 MB, there is no slight increase in processor load and impact on throughput. At 1 GB, the processor is 100% loaded, as at 100 MB, but the throughput drops below 100 Kb / s, in contrast to 1 Mb / s at 100 MB.

This is a very interesting point: it hints that the literal value of the size of the chunk affects the workload. Considering that this only happens when using PyOpenSSL, and also that most of the time the stack serves the above code, the problem becomes clear:

File "/home/user/.local/lib/python2.7/site-packages/OpenSSL/SSL.py", line 1299, in recv
  buf = _ffi.new("char[]", bufsiz)

The investigation showed that the standard behavior of CFFI with respect FFI.newto the return of zeroed memory. This meant a linear increase in redundancy depending on the size of the allocated memory: larger volumes had to be reset to zero longer. Therefore, poor behavior is associated with the allocation of large volumes. We took advantage of CFFI's ability to disable the zeroing of these buffers, and the problem went away ¹ . So it's solved, right?

Wrong.

Real bug

Jokes aside: this really solved the problem. But a few days later I was asked a very thoughtful question: why was memory actively reset at all ? To understand the essence of the issue, let's digress and talk about memory allocation in POSIX systems.

malloc and calloc and vmalloc, oh you!

Many programmers know the standard way to request memory from the operating system. This mechanism uses a function mallocfrom the standard C library (you can read the documentation about it for your OS by typing in the manual in the search man 3 malloc). This function takes one argument - the number of bytes of memory to allocate. The C standard library allocates memory using one of several different methods, but one way or another it returns a pointer to a section of memory that is at least as large as the amount you requested.

By default mallocreturns uninitialized memory . That is, the standard C library allocates some volume and immediately passes it to your program, without changing the data that is already there. That is, when using mallocyour program, the buffer will be returned to which it already wrote data. This is a common cause of bugs in memory-unsafe languages, such as C. Generally speaking, reading from uninitialized memory is very risky.

However, mallocthere is one, document on the same page manual: calloc. Its main difference is that it takes two arguments - counter and size. Using malloc, you ask the standard C library: "Please allocate at least nbytes to me ." And when callocyou call, you ask her: "Please allocate enough memory for nobjects of size mbytes." Obviously, the primary idea of callingcallocconsisted in safely allocating heaps for arrays of objects ² .

But callocthere is a side effect associated with its original purpose for placing arrays in memory. It is very modestly mentioned in the manual.

The allocated memory is filled with zero bytes.

It goes hand in hand with the destination calloc. For example, if you place an array of values ​​in memory, it will often be very useful for it to initially have a default state. In some modern memory-safe languages, this has already become standard behavior when creating arrays and structures. Say, when you initialize a structure in Go, then all its members are reduced by default to their so-called “zero” values, equivalent to “those values ​​that would be if everything were reset to zero”. This can be considered a promise that all Go structures are allocated in memory using calloc³ .

This behavior means that it mallocreturns uninitialized memory, and calloc- initialized. And if so, and even in the light of the above strict promises, the operating system can optimize the allocated memory. Indeed, many modern operating systems do this.

We use calloc

Of course, the easiest way to implement callocis to write something like:

void *calloc(size_t count, size_t size) {
    assert(!multiplication_would_overflow(count, size));
    size_t allocation_size = count * size;
    void *allocation = malloc(allocation_size);
    memset(allocation, 0, allocation_size);
    return allocation;
}

The cost of such a function varies approximately linearly with respect to the size of the allocated memory: the more bytes, the more expensive it is to reset them all. Today, most OSs in fact contain standard C libraries in which optimized paths are written for memset(usually specialized processor vector instructions are used that allow a single instruction to reset a large number of bytes at once). However, the cost of this procedure varies linearly.

To allocate large volumes, the OS uses another trick related to virtual memory.

Virtual memory

Here we will not analyze the entire structure and operation of virtual memory, but I highly recommend reading about it (the topic is extremely interesting!). In short: virtual memory is a lie of the OS kernel to processes about available memory. Each executed process has its own idea of ​​the memory belonging to him and only to him. This representation is indirectly “mapped” onto physical memory.

As a result, the OS can scroll through all sorts of tricky tricks. Most often, it gives out for memory special files displayed in it (memory-mapped file). They are used to download the contents of memory to disk, as well as to display memory in them. In the latter case, the program asks the OS: “Please allocate me n bytes of memory and save them in a file on disk, so that when I write to memory, all writes are made to this file, and when I read from memory, then the data would be read from it. ”

At the kernel level, this works: when a process tries to read from such memory, the processor notifies that the memory does not exist, pauses the process and throws a “page fault”. The kernel putsactual data in memory so that the application can read it. Then the process is paused and finds in the appropriate place the data that has magically appeared. From the point of view of the process, everything happened instantly, without a pause.

This mechanism can be used to perform other subtle tricks. One of them is the “free” allocation of very large amounts of memory. Or, more precisely, to make their value proportional to the degree of use of this memory, and not to the allocated size.

Historically, many programs that need decent chunks of memory at runtime create a largea buffer, which can then be distributed within the program during its life cycle. This was because programs were written for environments that did not use virtual memory; programs had to immediately take up some amount of memory, so that later they would not lack it. But after the introduction of virtual memory, this behavior became unnecessary: ​​each program can allocate as much memory as it needs, without tearing a piece out of its mouth ⁴ from others .

To avoid very high costs when launching applications, operating systems began to lie to applications. In most operating systems, if you try to allocate more than 128 KB in a single call, the standard C library will directly ask the OS for completely new virtual memory pages that will cover the requested volumes. But the main thing: thisHighlighting costs almost nothing . After all, in fact, the OS does nothing: it only reconfigures the virtual memory scheme. So when used, the malloccosts are miserable.

The memory was not “assigned” to the process, and as soon as the application tries to actually use it, an error occurs on the memory page. Here, the OS intervenes, finds the desired page and places it where the process is accessing, just like in the case of a memory error and a mapped memory file. The only difference is that virtual memory is provided by physical memory, not by file.

As a result, if you callmalloc(1024 * 1024 * 1024)to allocate 1 GB of memory, this will happen almost instantly, because in fact the memory is not allocated to the process. But programs can instantly “allocate” many gigabytes for themselves, although in reality this would not happen quickly.

But even more surprising is that the same optimization is available for calloc. The OS can display a completely new page on the so-called “zero page”: this is a read-only memory page, and only zeros are read from it. Initially, this mapping is a copy-on-write: when your process tries to write data to this new memory, the kernel intervenes, copies all zeros to a new page, and then allows you to write.

Thanks to such OS trickscallocwhen allocating large volumes, it can do the same as mallocrequesting new pages of virtual memory. This will happen for free until the memory starts to be used. Such optimization means that the cost calloc(1024 * 1024 * 1024, 1)will be equal to the call mallocfor the same amount of memory, despite the fact that callocit also promises to fill the memory with zeros. Clever!

Back to our bug

So: if CFFI used calloc, then why was the memory reset?

To start: callocnot always used. But I suspected that in this case I could reproduce the slowdown directly with the help calloc, so I again threw the program:

#include 
#define ALLOCATION_SIZE (100 * 1024 * 1024)
int main (int argc, char *argv[]) {
    for (int i = 0; i < 10000; i++) {
        void *temp = calloc(ALLOCATION_SIZE, 1);
        free(temp);
    }
    return 0;
}

A very simple C program that allocates and frees up 100 MB by calling callocten thousand times. Then the exit is performed. Next, there are two options ⁵ :

1. calloccan use the above trick with virtual memory. In this case, the program should work quickly: the allocated memory is not actually used, it does not break into pages, and the pages do not become dirty. The OS is lying to us about the allocation, but we do not catch it by the hand, so everything works fine.
2. calloccan attract mallocand manually reset the memory with memset. This should be done very, very slowly: in total, we need to reset the terabyte of memory (ten thousand cycles of 100 MB each), which is very difficult.

This greatly exceeds the standard OS threshold for using the first option, so you can expect just this behavior. Indeed, Linux does just that: if you compile the code using GCC and run it, it will execute extremely quickly, generate a few page errors, and hardly lead to memory load. But if you run the same program on MacOS, then it will run extremely long: it took me almost eight minutes .

Moreover, if you increase ALLOCATION_SIZE(for example 1000 * 1024 * 1024), then on MacOS this program will work almost instantly! What the hell is this?

What is going on here?

In-depth analysis

In MacOS there is a utility sample(see man 1 sample), which can tell a lot about the process being performed, recording its status. For our code it sampleproduces this:

Sampling process 57844 for 10 seconds with 1 millisecond of run time between samples
Sampling completed, processing symbols...
Sample analysis of process 57844 written to file /tmp/a.out_2016-12-05_153352_8Lp9.sample.txt
Analysis of sampling a.out (pid 57844) every 1 millisecond
Process:         a.out [57844]
Path:            /Users/cory/tmp/a.out
Load Address:    0x10a279000
Identifier:      a.out
Version:         0
Code Type:       X86-64
Parent Process:  zsh [1021]
Date/Time:       2016-12-05 15:33:52.123 +0000
Launch Time:     2016-12-05 15:33:42.352 +0000
OS Version:      Mac OS X 10.12.2 (16C53a)
Report Version:  7
Analysis Tool:   /usr/bin/sample
----
Call graph:
    3668 Thread_7796221   DispatchQueue_1: com.apple.main-thread  (serial)
      3668 start  (in libdyld.dylib) + 1  [0x7fffca829255]
        3444 main  (in a.out) + 61  [0x10a279f5d]
        + 3444 calloc  (in libsystem_malloc.dylib) + 30  [0x7fffca9addd7]
        +   3444 malloc_zone_calloc  (in libsystem_malloc.dylib) + 87  [0x7fffca9ad496]
        +     3444 szone_malloc_should_clear  (in libsystem_malloc.dylib) + 365  [0x7fffca9ab4a7]
        +       3227 large_malloc  (in libsystem_malloc.dylib) + 989  [0x7fffca9afe47]
        +       ! 3227 _platform_bzero$VARIANT$Haswel  (in libsystem_platform.dylib) + 41  [0x7fffcaa3abc9]
        +       217 large_malloc  (in libsystem_malloc.dylib) + 961  [0x7fffca9afe2b]
        +         217 madvise  (in libsystem_kernel.dylib) + 10  [0x7fffca958f32]
        221 main  (in a.out) + 74  [0x10a279f6a]
        + 217 free_large  (in libsystem_malloc.dylib) + 538  [0x7fffca9b0481]
        + ! 217 madvise  (in libsystem_kernel.dylib) + 10  [0x7fffca958f32]
        + 4 free_large  (in libsystem_malloc.dylib) + 119  [0x7fffca9b02de]
        +   4 madvise  (in libsystem_kernel.dylib) + 10  [0x7fffca958f32]
        3 main  (in a.out) + 61  [0x10a279f5d]
Total number in stack (recursive counted multiple, when >=5):
Sort by top of stack, same collapsed (when >= 5):
        _platform_bzero$VARIANT$Haswell  (in libsystem_platform.dylib)        3227
        madvise  (in libsystem_kernel.dylib)        438

Here we clearly see that a lot of time is wasted on the method _platform_bzero$VARIANT$Haswell. It is used to zero buffers. That is, MacOS resets them. Why?

Some time after the release, Apple makes most of the core code of its OS open. And you can see that this program spends a lot of time in libsystem_malloc. I went to opensource.apple.com , downloaded the libmalloc-116 archive with the source code I needed, and began to research.

It seems like all the magic happens in large_malloc . This branch is needed to allocate memory larger than 127 Kb, it uses a trick with virtual memory. So why does everything work slowly for us?

It seems that the fact is that Apple is too sophisticated. A bunch of code is hidden large_mallocbehind a constant #define,CONFIG_LARGE_CACHE. Basically, all this code comes down to a “free-list” of pages of large amounts of memory allocated for the program. If MacOS allocates an adjacent buffer from 127 KB to LARGE_CACHE_SIZE_ENTRY_LIMIT(approximately 125 MB) in size , then it libsystem_mallocwill try to use these pages again if another memory allocation process can use them. Thanks to this, he does not have to ask pages from the Darwin kernel, which saves context switching and system call: in principle, non-trivial savings.

However, this is the case for callocwhen you need to reset the bytes. And if MacOS finds a page that can be reused and that was called from calloc, then the memory will be reset . All. And so every time.

This has its own reason: zeroed pages are a limited resource, especially in modest iron (I look at the Apple Watch). So if the page can be reused, then this can give good savings.

However, the page cache completely deprives us of the advantages of using it callocto provide zero pages of memory. This would not be so bad if it was done only for dirty pages. If an application writes to a nullable page, then it probably will not be nullified. But MacOS does this unconditionally . This means that even if you call alloc, freeand callocwithout touching the memory at all, then with the second callcallocpages selected during the first call and never supported by physical memory will be taken. Therefore, the OS has to load (page-in) all this memory in order to reset it, although it has already been reset . This is what we want to avoid with the help of a distribution tool based on virtual memory when it comes to allocating large volumes: never-used memory becomes a used “list of free” pages.

As a result, on MacOS, the cost callocincreases linearly depending on the size of the allocated memory up to 125 MB, despite the fact that other OSs show O (1) behavior starting from 127 Kb. After 125 MB, MacOS stops caching pages, so that speed magically takes off.

I did not expect to find such a bug from a Python program, and I had a number of questions. For example, how many processor cycles are lost on resetting memory that has already been reset? How many context switches does it take to force applications to load (page-in) memory that they have not used (and are not going to) so that the OS can nullify it pointlessly?

It seems to me that all this confirms the truth of the old saying: there are leaks in all abstractions ( all abstractions are leaky ). You cannot forget about it just because you are programming in Python. Your program runs on a machine that uses memory and all sorts of tricks to control it. Once, quite unexpectedly, the code you wrote will start to work very slowly. And you will be able to deal with this only by understanding the OS internals.

This bug has been described as Radar 29508271 . One of the strangest bugs that I have encountered.

conclusions

1. Many of you will ask if it is safe to do so. Of course, CFFI does not just zero out buffers: it is much better to use initialized memory than uninitialized, especially when interacting with memory directly from a programming language, so it is much safer to reset it. But in this case, the array we create is charimmediately passed to OpenSSL, which can write data to the buffer, and we tell OpenSSL the length of the buffer. This means that OpenSSL immediately overwrites the maximum buffer size on top of our freshly cleared bytes. And when we get the buffer back, OpenSSL tells us how many bytes it wrote. We simply copy these bytes from the buffer and throw them away. That is, each byte in the buffer a) we filled it with zeros, then it was overwritten by OpenSSL, then we copied it, or b) we filled it with zeros and never touched it again. In any case, the first step (filling with zeros) is optional: either OpenSSL will then zero itself out, or we will not touch these bytes at all, regardless of the values ​​stored in them. So, in general, buffers used in this way do not need to be reset.
2. Need to clarify about the "safe." A huge number of C-code, wants to highlight a bunch of arrays, making calls like this: type *array = malloc(number_of_elements * size_of_element). This is a dangerous pattern, because multiplication can lead to overflow : if the result of the multiplication number_of_elements на size_of_elementdoes not fit in the allotted number of bits, the program may request too little data . callocprevents this by using code that checks for overflow when multiplying. And if the result is too large, then the corresponding error is returned.
3. I must emphasize that “can be considered” is not a synonym for “guarantees”. I did not analyze runtime Go and did not check this point.
4. Of course, they can starve each other in terms of physical memory, but this is another problem.
5. All this assumes that you are compiling with optimizations turned off: after all, the optimizer can simply optimize the entire program!