Implementing malloc and free
Jun 14, 2017 · 5 min read
Chapter 7 of “The Linux Programming Interface” is about memory allocation. One of the exercises, marked as advanced, asks the reader to implement malloc. I’ve decided to give it a shot. My full implementation is available on Github; I will try to break down some of my reasoning on the next sections and include some snippets from the code.
Memory layout of a Process
The memory allocated to each process is composed of multiple segments, as can be seen on the following image:
We are particularly in t erested on the heap (also known as the data segment), an area from which memory can be dynamically allocated at run time. The top end of the heap is called the program break.
Adjusting the program break
We can move the program break on our C program by using sbrk() and brk().
The first, moves the program break to the address pointed by addr, while the latter increments the program break by increment bytes. Their man pages can give more information about their implementation on Linux and other systems, but those are the basic building blocks that our malloc implementation will rely on. On Linux, sbrk relies on brk.
The implementation
The entire code for the implementation is available at github. Beware that this implementation is full of bugs (some are discussed below, some are obvious from reading the real malloc implementation). The following code is the malloc function implementation.
Our implementation keeps a doubly linked listed of free memory blocks and every time _malloc gets called, we traverse the linked list looking for a block with at least the size requested by the user (lines 8–25). If a block with the exact requested size exists, we remove it from the list and return its address to the user (lines 11–16); if the block is larger, we split it into two blocks, return the one with the requested size to the user and adds the newly created block to the list (lines 19–21).
If we are unable to find a block on the list, we must “ask” the OS for more memory, by using the sbrk function (lines 31–35). To reduce the number of calls to sbrk, we alloc a fixed number of bytes that is a multiple of the memory page size, defined as:
After the call to sbrk (where our program break changes value) we create a new block with the allocated size. The metadata on this block contains the size, next and previous blocks and is allocated on the first 24 bytes of the block (this is our overhead) (lines 36–38). Since we may have allocated much more memory then the user requested, we split this new block and return the one with the exact same size as requested (lines 39–43).
The BLOCK_MEM macro, defined as:
returns skips the metadata at given ptr and returns the address of the memory area that is available for the user.
The _free function is quite straightforward, given a pointer that was previously “malloced” to the user, we must find its metadata (by using the BLOCK_HEADER macro) and add it to our free linked list. After that, the function scan_merge() is called to do some cleaning:
scan_merge() first traverses the linked list looking for continuous blocks (two different memory blocks that are free and correspond to continuous addresses). We keep the blocks sorted by address to make this step easier. For every two continuous blocks found, we merge both blocks to reduce our total overhead (less metadata to keep) (lines 18–33).
After finding the last block on our free list, we check if this blocks ends on the program break (line 39). If that is true, and the block is big enough (where “big” is defined as MIN_DEALLOC, also a multiple of the page size), we remove the block from our list and move the program break to the beginning of the block, by calling brk.
How is malloc actually implemented?
Before diving into the real malloc code, I decided to write a simple test program and trace it’s execution using strace. I used the following code:
I decided to trace the executing testing different sizes.
The first thing I noticed between executions is that when asking for a large size, malloc actually used mmap instead of brk to allocate the memory. I wasn’t sure why, since I have yet to study mmap. But checking the code for glibc’s malloc I’ve found a pretty nice writeup made by the authors explaining their implementation. I highly recommend reading it. Regarding the use of mmap, from the source code comments:
The documentation also explains their design goals, motivations, how the blocks are organized (by using bins for the different sizes, instead of keeping a linked list sorted by address, as I did) and lots of other details. I learned a lot reading it.
Adding a call to free on my test program does not change the syscalls made by at, as the memory is not released to the OS (some people rely on this behavior “mallocing” a large chunk of memory and freeing it on the start of a program to reserve the memory). One can control this behavior by defining M_TRIM_THREASHOLD:
This blog post is part of a series of posts that I intent to write while reading “The Linux Programming Interface” to make sure I’m actually learning something, as a way to practice and to share knowledge.
Источник
Эксперименты с malloc
Как известно, в современных архитектурах x86(_64) и ARM виртуальная память процесса линейна и непрерывна, ибо, к счастью, прошли времена char near* и int huge* . Виртуальная память поделена на страницы, типичный размер которых 4 KiB, и по умолчанию они не отображены на физическую память (mapping), так что работать с ними не получится. Чтобы посмотреть текущие отображённые интервалы адресов у процесса, в Linux смотрим /proc/
/maps, в OS X vmmap
. У каждого интервала адресов есть три вида защиты: от исполнения, от записи и от чтения. Как видно, самый первый интервал, начинающийся с load address (соответствующий сегменту .text у ELF в Linux, __TEXT у Mach-O в OS X), доступен на чтение и исполнение — очень логично. Ещё можно увидеть, что стек по сути ничем не отличается от других интервалов, и можно быстро вычислить его размер, вычтя из конечного адреса начальный. Отображение страниц выполняется с помощью mmap/munmap, а защита меняется с помощью mprotect. Ещё существуют brk/sbrk, deprecated древние пережитки прошлого, которые изменяют размер одного-единственного интервала «данных» и в современных системах эмулируются mmap’ом.
Все POSIX-реализации malloc так или иначе упираются в перечисленные выше функции. По сравнению с наивным выделением и освобождением страниц, округляя необходимый размер в большую сторону, malloc имеет много преимуществ:
- оптимально управляет уже выделенной памятью;
- значительно уменьшает количество обращений к ядру (ведь mmap / sbrk — это syscall);
- вообще абстрагирует программиста от виртуальной памяти, так что многие пользуются malloc’ом, вообще не подозревая о существовании страниц, таблиц трансляции и т. п.
Довольно теории! Будем щупать malloc на практике. Проведём три эксперимента. Работа будет возможна на POSIX-совместимых операционках, в частности была проверена работа на Linux и на OS X.
NULL из malloc
Начнём с банального. Если переопределить функцию из libc (равно как и любой другой библиотеки) у себя в коде, то linker не будет против, если libc подключается динамически (а по умолчанию именно так), и не будет ругаться на двойное определение. К примеру, такой код:
Он будет печатать «malloc» и иметь нулевой код возврата ( echo $? ). Однако давайте проверим, что будет, если вызвать какую-нибудь функцию, в недрах которой вызывается malloc, например asprintf.
И тут будет сильно зависеть от linker’а. Если это ld/Linux, то напечатается
Ибо malloc вызовется наш, переопределённый, а glibc-реализация printf не использует malloc. Переопределение получилось, потому что malloc в glibc объявлен слабым символом (__attribute__((weak))), а наше определение по-умолчанию сильное (специфично для ELF). Но при dyld / OS X поведение другое:
На самом деле malloc на маке не переопределился! Дело должно быть в многоуровневых пространствах имён dyld. Ну-ка, ну-ка…
Хрясь БАБАХ бдыжь! Дело, по всей видимости, даже не дошло до int main(). В чём причина?
Какой-какой фрейм? 130952-й? Да у нас, оказывается, Stack Overflow! А ещё мы узнали несколько любопытных вещей: dyld написан на C++, а puts зачем-то выделяет память тем самым malloc’ом, создавая рекурсию. Хочется верить, что он так поступает всего один раз при инициализации stdout-буфера. Ну а мы вынуждены его заменить:
Запускаем и видим:
Итак, видно, что в отличие от GNU/Linux, ld которого сделан на статической аллокации, при запуске приложения в OS X интенсивно используется куча. Также видно, что выброс исключения про неудавшееся выделение памяти оператором new вызывает calloc, который, как мы помним, есть комбинация malloc + заполнение нулями (bzero). Реализация calloc попалась бажная и не проверила нулевой указатель. С этим знанием мне теперь не даст покоя мысль, что будет, если в OS X по-настоящему закончится память, «до последнего байта». Очевидно, что правильным и логичным решением было бы заранее выделять память для std::bad_alloc.
Ок, Гугл, как нам всё-таки переопределить malloc под OS X так, чтобы ничего не падало? Придётся погрузиться в детали реализации. Malloc на маке выделяет память в зонах. Изначально зона всего одна, по умолчанию, и именно её покажет vmmap в конце вывода. У каждой зоны хранятся указатели на malloc, free и realloc, что позволяет гибко настраивать управление памятью. Можно взять дефолтную зону и заменить в ней указатель на malloc:
Обратите внимание на mprotect. Изначально malloc_default_zone возвращает указатель на область памяти, которая защищена от записи. В этом легко убедиться, запустив программу без mprotect и исследовав падение в отладчике и vmmap’е. Такая защита получается от шаловливых рук… Обратно на PROT_READ, строго говоря, защиту можно было и не менять, добавлено ради порядка. Что напечатается:
Видим, что printf использовал malloc, но потом нашёл в себе силы обойтись без динамической памяти и всё равно распечатал нулевой указатель.
К слову, о зонах. Malloc в glibc использует похожий поход, который назвали obstacks. С одной стороны, для работы с ними существует много функций, с другой стороны, отсутствует возможность применять в разных obstack’ах разные алгоритмы выделения памяти.
Вывод: dyld, загрузчик OS X, написан на C++ и работа с кучей в программах на этой системе начинается задолго до int main(). C ld на Linux такого не происходит и обращений к куче нет.
Неэффективный malloc
Поставим теперь себе новую цель: создадим динамическую библиотеку, в которой реализуем свою версию malloc.
Здесь реализуется простейший подход, когда мы выделяем память страницами. Приходится хранить в начале страницы размер, чтобы было что передать в unmap. MAP_ANONYMOUS в флагах mmap означает, что мы отображаем в память не реальный файл, а физическую память (обычно mmap’ом отображают в память именно файлы, это даёт ускорение в некоторых операциях). MAP_PRIVATE в случае файлов создавал бы индивидуальную копию при записи (copy-on-write), но для нас, по сути, ничего не делает, просто документация требует присутствия либо MAP_PRIVATE, либо MAP_SHARED. Кстати, с MAP_SHARED этот код тоже прекрасно работает.
Проверять будем на примере:
Собирать будем так:
При запуске увидим:
Вывод для OS X и Linux идентичный. В случае OS X вспоминаем про пространства имён dyld и делаем их плоскими, как интерфейс Windows 10.
Программа отработала, и уже хорошо. Что удивительно — явное несоответствие между количеством вызовов malloc и free перед int main(). Также free много раз завершался неудачно. Интересующиеся могут запустить test в отладчике, поставить бряку на free и узнать про тёмную жизнь dyld много нового, а мы будем двигаться дальше.
Вывод: вполне реально написать реализацию malloc «в лоб» в 30 строк.
Шпионим за malloc
Попробуем использовать технику DLL injection, чтобы внедрять свой malloc в чужие программы. Писать собственную эффективную реализацию кучи не хочется, хотя существует множество интересных алгоритмов, например Buddy. Можно было бы взять любую из готовых реализаций, но мы применим трюк с RTLD_NEXT и сошлёмся на системный malloc. Рассмотрим такой код:
Ссылка на полную версию кода будет дана в конце статьи. Его половину съела кросс-платформенная реализация clock_gettime, а вторую — обращение к clock_gettime, так что я был вынужден немного сократить. Вся прелесть в одной-единственной строчке:
В ней мы подгружаем «предыдущий» malloc. Обычно dlsym используют для вытаскивания функций из загруженных динамических библиотек, но у нас в качестве дескриптора библиотеки использован магический RTLD_NEXT. Строго говоря, в POSIX его нет, но по факту его поддерживают многие linker’ы. Итак, мы получаем указатель на истинный malloc, сохраняем его и впоследствии вызываем, возвращая его результат. Попутно логируем все вызовы.
Собираем так же, как и hack_malloc.c, используем на Linux так:
Путь обязательно должен быть абсолютным, иначе магия не случится. LD_PRELOAD — специальная переменная окружения, насильно подгружающая указанные библиотеки перед основными, с которыми собрана программа. Таким образом можно переопределять произвольные функции или решать временные проблемы с запуском неправильно скомпонованных программ (то самое сообщение lib*.so: not found).
Ls, к примеру, создаёт около 2 KB лога. А whoami упадёт с сообщением undefined symbol: dlsym, потому что dlsym определён в libdl.so, который некоторые подгружают, а некоторые нет. И нет смысла собирать libtracemalloc с -ldl, так как LD_PRELOAD не будет подгружать зависимости инжектируемых библиотек. Придётся делать как-то так:
И мы увидим килобайт лога выделений памяти даже в случае такой элементарной утилиты.
Ок, а что там с OS X? Dyld поддерживает переменную окружения DYLD_INSERT_LIBRARIES, которая делает аналогичные вещи. Пробуем:
… не получается, вспоминаем про пространства имён:
… и снова облом. Уже интересно! Оказывается, дело в защите системных программ System Integrity Protection. Этот механизм с помощью расширенных файловых атрибутов не даёт изменять файлы, инжектить код, дебажить по путям вроде /System, /usr и т. д. К счастью, /usr/local помиловали.
SIP можно отключить, но мы поступим проще — будем копировать интересующие нас программы в свою директорию:
Так уже работает. В заключение докажем известный тезис о двух типах выделения памяти. Соберем лог malloc’а и построим гистограмму распределения размеров с помощью элементарного кода на IPython:
На гистограмме размеров будет видна типичная картина (Y — количество вызовов, X — размер, программа — clang):
Я специально обрезал хвост на 100 байтах, так как аллокации большего размера настолько редки, что становятся не видны на гистограмме. Итак, 98% всех выделений памяти в куче меньше, чем 100 байт, а значит, хороший malloc должен обслуживать минимум два отдельных домена: для больших объектов и для всех остальных.
Заметим, что для того, чтобы проанализировать вашу программу, можно не возиться с самосборной библиотекой вроде описанной выше, а взять уже готовую. Например, tcmalloc позволяет профилировать кучу и делать много другого полезного.
Код из статьи доступен на гитхабе. В следующий раз мы возьмём настоящую, большую программу, соберём лог выделений памяти во время её работы и попробуем делать предсказания на основе LSTM-модели рекурсивной нейронной сети.
Источник
