Отладка вашей ОС: урок по выделению памяти

Всё началось, как и многие другие расследования, с баг-репорта.

Название отчёта было довольно простым: «При HTTP-подключении iter_content медленно работает с чанками большого размера». Подобное название немедленно включило у меня в голове сирену по двум причинам. Во-первых, довольно сложно определить, что здесь означает «медленно»? Насколько медленно? Насколько велик «большой размер»? Во-вторых, если бы описанное проявлялось действительно серьёзно, то мы бы об этом уже знали. Метод iter_content используется давно, и если бы он существенно притормаживал в распространённом пользовательском режиме, то мимо нас такая информация не прошла бы.

Я быстро просмотрел отчёт. Автор предоставил мало подробностей, но написал вот что: «Это приводит к 100%-й загрузке процессора и снижает пропускную способность сети ниже 1 Мб/с». Я ухватился за эту фразу, потому что такого быть не может. Простое скачивание с минимальной обработкой не бывает настолько медленным!

Однако все сообщения о багах до опровержения заслуживают расследования. Пообщавшись с автором отчёта, удалось восстановить сценарий проявления бага: если использовать Requests с PyOpenSSL и запустить следующий код, то процессор будет полностью загружен, а пропускная способность сети упадёт до минимума:

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

Это просто замечательный воспроизводимый сценарий, потому что он совершенно чётко указывает на стек Requests. Здесь не выполняется пользовательский (user-supplied) код: это часть библиотеки Requests или одной из его зависимостей; нет вероятности, что это пользователь написал дурацкий низкопроизводительный код. Настоящая фантастика. Ещё более фантастично использование публичного URL. Я мог выполнить сценарий! И, сделав это, я столкнулся с багом. При каждом выполнении.

Здесь была ещё одна прелестная подробность:

При 10 Мб не отмечается какого-то роста нагрузки на процессор и влияния на пропускную способность. При 1 Гб процессор загружается на 100 %, как и при 100 Мб, но пропускная способность падает ниже 100 Кб/с, в отличие от 1 Мб/с при 100 Мб.

Это очень интересный момент: он намекает на то, что литеральное значение (literal value) размера чанка влияет на рабочую нагрузку. Если учесть, что это происходит только при использовании PyOpenSSL, а также что большую часть времени стек обслуживает вышеприведённый код, проблема становится ясна:

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

Расследование показало, что стандартное поведение CFFI относительно FFI.new заключается в возвращении обнулённой памяти. Это означало линейное увеличение избыточности в зависимости от размера выделяемой памяти: более крупные объёмы приходилось обнулять дольше. Следовательно, плохое поведение связано с выделением больших объёмов. Мы воспользовались возможностью CFFI отключить обнуление этих буферов, и проблема ушла¹. Так она решена, верно?

Неверно.

Настоящий баг

Шутки в сторону: это действительно позволило решить проблему. Но несколько дней спустя мне задали очень глубокомысленный вопрос: зачем вообще память активно обнулялась? Чтобы понять суть вопроса, давайте отвлечёмся и поговорим о выделении памяти в POSIX-системах.

malloc и calloc и vmalloc, ох ты ж!

Многим программистам известен стандартный способ запроса памяти у оперативной системы. В этом механизме задействована функция malloc из стандартной библиотеки С (можете почитать документацию о ней для вашей ОС, введя в мануале в поиск man 3 malloc). Эта функция берёт один аргумент — количество байтов памяти, которое нужно выделить. Стандартная библиотека С выделяет память по одной из нескольких разных методик, но так или иначе она возвращает указатель на бит памяти, по крайней мере такой же большой, как и запрошенный вами объём.

По умолчанию malloc возвращает неинициализированную память. То есть стандартная библиотека С выделяет какой-то объём и немедленно передаёт его вашей программе, без изменения данных, которые уже там находятся. То есть при использовании malloc вашей программе будет возвращаться буфер, в который она уже записывала данные. Это распространённая причина багов в не безопасных по памяти (memory-unsafe) языках, например С. В целом читать из неинициализированной памяти очень рискованно.

Однако у malloc есть друг, задокументированный на той же странице мануала: calloc. Его главное отличие заключается в том, что он принимает два аргумента — счётчик и размер. Используя malloc, вы просите стандартную библиотеку С: «Пожалуйста, выдели мне не менее n байтов». А при вызове calloc вы просите её: «Пожалуйста, выдели достаточно памяти для n объектов размером m байтов». Очевидно, что первичная идея вызова calloc заключалась в безопасном выделении кучи для массивов объектов².

Но у calloc есть побочный эффект, связанный с его исходным предназначением для размещения массивов в памяти. О нём очень скромно упоминается в мануале.

Выделенная память заполнена нулевыми байтами.

Это идёт рука об руку с предназначением calloc. К примеру, если вы размещаете в памяти массив значений, то зачастую будет очень полезно, чтобы он изначально имел состояние по умолчанию. В некоторых современных безопасных по памяти языках это уже стало стандартным поведением при создании массивов и структур. Скажем, когда в Go инициализируешь структуру, то все её члены по умолчанию приведены к своим так называемым «нулевым» значениям, эквивалентным «таким значениям, которые были бы, если бы всё сбросили в ноль». Это можно считать обещанием, что все Go-структуры размещаются в памяти с помощью calloc³.

Такое поведение означает, что malloc возвращает неинициализированную память, а calloc — инициализированную. А раз так, да ещё и в свете вышеупомянутых строгих обещаний, то операционная система может оптимизировать выделяемую память. И действительно, многие современные ОС так делают.

Воспользуемся calloc

Конечно, простейший способ внедрить calloc — это написать что-то вроде:

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;
}

Стоимость подобной функции изменяется примерно линейно по отношению к размеру выделяемой памяти: чем больше байтов, тем дороже их все обнулить. Сегодня большинство ОС по факту содержат стандартные библиотеки С, в которых прописаны оптимизированные пути для memset (обычно используются специализированные процессорные векторные инструкции, позволяющие одной инструкцией обнулять сразу большое количество байтов). Тем не менее стоимость этой процедуры меняется линейно.

Для выделения больших объёмов в ОС используется ещё один трюк, имеющий отношение к виртуальной памяти.

Виртуальная память

Здесь мы не будем разбирать всю структуру и работу виртуальной памяти, но я очень рекомендую об этом почитать (тема крайне интересная!). Вкратце: виртуальная память — это ложь ядра ОС процессам о доступной памяти. У каждого выполняемого процесса есть своё представление о памяти, принадлежащей ему и только ему. Это представление косвенно «отображается» (mapped) на физическую память.

В результате ОС может прокручивать всевозможные хитрые трюки. Чаще всего она выдаёт за память специальные файлы, отображаемые в неё (memory-mapped file). Они используются для выгрузки содержимого памяти на диск, а также для отображения в них памяти. В последнем случае программа просит ОС: «Пожалуйста, выдели мне n байтов памяти и сохрани их в файле на диске, так, чтобы, когда я буду писать в память, все записи выполнялись бы в этот файл, а когда считываю из памяти, то данные считывались бы из него же».

На уровне ядра это работает так: когда процесс пытается считать из такой памяти, процессор уведомляет, что память не существует, ставит процесс на паузу и бросает «ошибку страницы» (page fault). Ядро помещает в память актуальные данные, чтобы приложение могло их считать. Затем процесс снимается с паузы и находит в соответствующем месте волшебным образом появившиеся данные. С точки зрения процесса всё произошло мгновенно, без паузы.

Этот механизм можно использовать для выполнения других тонких трюков. Один из них заключается в «бесплатности» выделения очень больших объёмов памяти. Или, точнее, в том, чтобы сделать их стоимость пропорциональной степени использования этой памяти, а не выделяемому размеру.

Исторически сложилось так, что многие программы, которым во время выполнения нужны порядочные куски памяти, при запуске создают большой буфер, который потом может распределяться внутри программы в ходе её жизненного цикла. Так делалось потому, что программы писались для окружений, не использовавших виртуальную память; программам приходилось сразу занимать какие-то объёмы памяти, чтобы потом не испытывать в ней недостатка. Но после внедрения виртуальной памяти такое поведение стало ненужным: каждая программа может выделить себе столько памяти, сколько надо, не вырывая у других кусок изо рта⁴.

Чтобы избежать очень больших затрат при запуске приложений, операционные системы начали врать приложениям. В большинстве ОС, если вы попытаетесь выделить более 128 Кб в рамках одного вызова, стандартная библиотека С напрямую попросит у ОС совершенно новые страницы виртуальной памяти, которые покроют запрошенные объёмы. Но главное: такое выделение почти ничего не стоит. Ведь на самом деле ОС ничего не делает: она лишь перенастраивает схему виртуальной памяти. Так что при использовании malloc расходы получаются мизерными.

Память не была «приписана» к процессу, и, как только приложение пытается использовать её на самом деле, возникает ошибка страницы памяти. Здесь вмешивается ОС, находит нужную страницу и помещает её туда, куда обращается процесс, так же, как и в случае с ошибкой памяти и файлом отображаемой памяти. Только разница в том, что виртуальная память обеспечивается памятью физической, а не файлом.

В результате, если вызвать malloc(1024 * 1024 * 1024) для выделения 1 Гб памяти, это произойдёт почти мгновенно, потому что на самом деле процессу память не выделяется. Зато программы могут моментально «выделять» для себя многие гигабайты, хотя в реальности это происходило бы далеко не быстро.

Но ещё удивительнее то, что такая же оптимизация доступна и для calloc. ОС может отображать совершенно новую страницу на так называемую «нулевую страницу»: это страница памяти, доступная только для чтения, причём считываются из неё одни лишь нули. Изначально такое отображение представляет собой копирование при записи (copy-on-write): когда ваш процесс пытается записать данные в эту новую память — вмешивается ядро, копирует все нули в новую страницу, а затем разрешает вам выполнить запись.

Благодаря такому ухищрению со стороны ОС calloc может при выделении больших объёмов делать то же самое, что и malloc, запрашивая новые страницы виртуальной памяти. Это будет происходить бесплатно до тех пор, пока память не начнёт использоваться. Подобная оптимизация означает, что стоимость calloc(1024 * 1024 * 1024, 1) будет равна вызову malloc для такого же объёма памяти, несмотря на то что calloc ещё и обещает заполнять память нулями. Умно!

Вернёмся к нашему багу

Итак: если CFFI использовал calloc, то почему память обнулялась?

Для начала: calloc использовался не всегда. Но я подозревал, что в данном случае могу воспроизвести замедление напрямую с помощью calloc, поэтому снова накидал программу:

#include <stdlib.h>

#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;
}

Очень простая программа на C, выделяющая и освобождающая 100 Мб посредством вызова calloc десять тысяч раз. Затем выполняется выход. Далее — два варианта⁵:

1. calloc может использовать вышеописанную хитрость с виртуальной памятью. В таком случае программа должна работать быстро: выделяемая память на самом деле не используется, не разбивается на страницы, а страницы не становятся «грязными» (dirty). ОС врёт нам насчёт выделения, а мы не ловим её за руку, так что всё работает прекрасно.
2. calloc может привлечь malloc и вручную обнулить память с помощью memset. Это должно делаться очень-очень медленно: в сумме нам надо обнулить терабайт памяти (десять тысяч циклов по 100 Мб), что очень непросто.

Это сильно превышает стандартный порог ОС для использования первого варианта, так что можно ожидать именно такого поведения. Действительно, Linux так и поступает: если скомпилировать код с помощью GCC и запустить, то он выполнится крайне быстро, сгенерирует несколько ошибок страницы и почти не приведёт к нагрузке на память. Но если ту же программу запустить на MacOS, то она будет выполняться крайне долго: у меня это заняло почти восемь минут.

Более того, если увеличить ALLOCATION_SIZE (например, 1000 * 1024 * 1024), то на MacOS эта программа станет работать почти мгновенно! Что за чертовщина?

Что тут вообще происходит?

Углублённый разбор

В MacOS есть утилита sample (см. man 1 sample), которая может многое рассказать о выполняемом процессе, регистрируя его состояние. Для нашего кода sample выдаёт такое:

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

Здесь мы ясно видим, что куча времени тратится на метод _platform_bzero$VARIANT$Haswell. Он используется для обнуления буферов. То есть MacOS их обнуляет. Почему?

Спустя какое-то время после релиза Apple делает открытым большую часть основного кода своей ОС. И можно увидеть, что эта программа тратит немало времени в libsystem_malloc. Я отправился на opensource.apple.com, скачал архив libmalloc-116 с нужным мне исходным кодом и принялся исследовать.

Похоже, вся магия происходит в large_malloc. Эта ветка нужна для выделения памяти крупнее 127 Кб, она использует трюк с виртуальной памятью. Так почему у нас всё медленно работает?

Похоже, дело в том, что Apple слишком перемудрила. В large_malloc за константой #define спрятана куча кода, CONFIG_LARGE_CACHE. В основном весь этот код сводится к «списку свободных» (free-list) страниц больших объёмов памяти, выделенных для программы. Если MacOS выделяет смежный буфер размером от 127 Кб до LARGE_CACHE_SIZE_ENTRY_LIMIT (примерно 125 Мб), тогда libsystem_malloc попытается снова пустить в ход эти страницы, если ими может воспользоваться другой процесс выделения памяти. Благодаря этому ему не приходится просить страницы у ядра Darwin, что экономит переключение контекста и системный вызов: в принципе, нетривиальная экономия.

Однако это тот случай для calloc, когда нужно обнулить байты. И если MacOS находит страницу, которую можно использовать повторно и которая была вызвана из calloc, то память обнулится. Вся. И так каждый раз.

В этом есть свой резон: обнулённые страницы — ограниченный ресурс, особенно в условиях скромного железа (смотрю на Apple Watch). Так что если страницу можно использовать повторно, то это может дать хорошую экономию.

Однако кеш страницы полностью лишает нас преимуществ использования calloc для предоставления обнулённых страниц памяти. Это было бы не так уж плохо, если бы делалось только для «грязных» страниц. Если приложение записывает в обнуляемую страницу, то та, вероятно, не будет обнулена. Но MacOS выполняет это безоговорочно. Это значит, что даже если вызвать alloc, free и calloc, вообще не трогая память, то при втором вызове calloc будут взяты страницы, выделенные во время первого вызова и ни разу не поддержанные физической памятью. Поэтому ОС приходится загрузить (page-in) всю эту память, чтобы обнулить её, хотя она уже была обнулена. Этого мы и хотим избежать с помощью средства распределения на базе виртуальной памяти, когда доходит до выделения больших объёмов: ни разу не использовавшаяся память становится использованной «списком свободных» страниц.

В результате на MacOS стоимость calloc линейно возрастает в зависимости от размера выделяемой памяти вплоть до 125 Мб, несмотря на то что другие ОС демонстрируют поведение O(1) начиная со 127 Кб. После 125 Мб MacOS перестаёт кешировать страницы, так что скорость волшебным образом взлетает.

Я не ожидал найти такой баг из программы на Python, и у меня возник ряд вопросов. Например, сколько процессорных циклов теряется на обнуление памяти, которая уже обнулена? Сколько переключений контекста уходит на то, чтобы заставлять приложения загружать (page-in) память, которую они не использовали (и не собираются), чтобы ОС могла бессмысленно её обнулить?

Мне кажется, всё это подтверждает верность старой поговорки: утечки есть во всех абстракциях (all abstractions are leaky). Вы не можете забывать об этом лишь потому, что программируете на Python. Ваша программа выполняется на машине, использующей память и всякие трюки для её управления. Однажды, совершенно неожиданно, написанный вами код станет работать очень медленно. И разобраться с этим удастся, лишь разобравшись во внутренностях ОС.

Этот баг был описан как Radar 29508271. Один из самых странных багов, что мне встречались.

Выводы

1. Многие из вас спросят, безопасно ли так делать? Конечно, CFFI не просто обнуляет буферы: гораздо лучше использовать инициализированную память, чем неинициализированную, особенно при взаимодействии с памятью напрямую из языка программирования, поэтому с обнулением получается гораздо безопаснее. Но в данном случае создаваемый нами массив char немедленно передаётся в OpenSSL, который может писать данные в буфер, и мы сообщаем OpenSSL длину буфера. Это значит, что OpenSSL немедленно перезаписывает поверх наших свежеобнулённых байтов максимальный размер буфера. И когда мы получаем буфер обратно, OpenSSL сообщает нам, сколько байтов он записал. Мы просто копируем эти байты из буфера и выкидываем их. То есть каждый байт в буфере а) мы заполнили нулями, затем его перезаписал OpenSSL, затем мы его выкопировали, или б) мы заполнили нулями и больше никогда не трогали. В любом случае первый шаг (заполнение нулями) необязателен: либо OpenSSL потом сам обнулит, либо мы вообще не будем касаться этих байтов, вне зависимости от хранимых в них значений. Так что в целом используемые подобным образом буферы не нуждаются в обнулении.
2. Нужно пояснить насчёт «безопасного». Огромное количество C-кода, желающего выделить кучу для массивов, делает вызовы наподобие такого: type *array = malloc(number_of_elements * size_of_element). Это опасный шаблон, поскольку умножение может привести к переполнению: если результат умножения number_of_elements на size_of_element не поместится в отведённое количество битов, программа может запросить слишком мало данных. calloc предотвращает это с помощью кода, который при умножении проверяет на переполнение. И если результат оказывается слишком большим, то возвращается соответствующая ошибка.
3. Должен подчеркнуть, что «можно считать» — не синоним «гарантирует». Я не анализировал runtime Go и не проверял этот момент.
4. Конечно, они могут морить друг друга голодом с точки зрения физической памяти, но это уже другая проблема.
5. Всё это предполагает, что вы компилируете с выключенными оптимизациями: ведь оптимизатор может просто оптимизировать всю программу!

Автор: Mail.Ru Group

Источник