Введение

Динамическое управление памятью в языке программирования C

Динамическое распределение памяти в C подразумевает ручное управление памятью для динамического выделения памяти в языке программирования C с использованием набора функций из стандартной библиотеки C, а именно `malloc`, `calloc`, `realloc` и `free`. Язык программирования C++ также включает эти функции, однако операторы `new` и `delete` предоставляют аналогичную функциональность и рекомендуются авторами этого языка. Тем не менее, существуют ситуации, когда использование `new`/`delete` неприменимо, например, в коде сборки мусора или в коде, критичном к производительности, и в таких случаях может потребоваться комбинация `malloc` и placement `new` вместо оператора `new` более высокого уровня. Существует множество различных реализаций механизма выделения памяти, используемого функцией `malloc`. Их производительность различается как по времени выполнения, так и по объему требуемой памяти.

Обоснование

Язык программирования C управляет памятью статически, автоматически или динамически. Переменные статической длительности выделяются в основной памяти, обычно вместе с исполняемым кодом программы, и сохраняют свое существование на протяжении всего времени работы программы; переменные автоматической длительности выделяются в стеке и создаются и уничтожаются при вызове и возврате функций. Для переменных статической и автоматической длительности размер выделяемой памяти должен быть известен во время компиляции (за исключением автоматических массивов переменной длины). Если требуемый размер неизвестен до выполнения программы (например, если данные произвольного размера считываются от пользователя или из файла на диске), то использование объектов данных фиксированного размера оказывается недостаточным. Время жизни выделенной памяти также может вызывать опасения. Ни статическая, ни автоматическая память не подходят для всех ситуаций. Автоматически выделенные данные не могут сохраняться между вызовами функций, в то время как статические данные сохраняются на протяжении всего времени работы программы, независимо от того, нужны они или нет. Во многих ситуациях программисту требуется большая гибкость в управлении временем жизни выделенной памяти. Эти ограничения устраняются с помощью динамического выделения памяти, при котором память управляется более явно (но и более гибко), как правило, путем выделения ее из специальной области памяти, предназначенной для этой цели. В C функция malloc используется для выделения блока памяти в куче. Программа получает доступ к этому блоку памяти через указатель, возвращаемый функцией malloc. Когда память больше не требуется, указатель передается функции free, которая освобождает память, чтобы ее можно было использовать для других целей. В первоначальном описании языка C указывалось, что calloc и cfree входили в стандартную библиотеку, а malloc – нет. Код простой модельной реализации менеджера хранения для Unix был представлен с функциями alloc и free в качестве функций интерфейса пользователя и с использованием системного вызова sbrk для запроса памяти у операционной системы. В документации Unix 6-го издания функции alloc и free указаны как функции выделения памяти низкого уровня. Функции malloc и free в их современном виде полностью описаны в руководстве Unix 7-го издания. Некоторые платформы предоставляют библиотечные или встроенные функции, позволяющие выполнять динамическое выделение памяти во время выполнения из стека C, а не из кучи (например, alloca). Эта память автоматически освобождается при завершении вызывающей функции.

Обзор функций

Функции динамического выделения памяти в C определены в заголовочном файле stdlib.h (заголовочном файле cstdlib в C++).

Преимущества литья

Приведение типов может позволить программе или функции на C компилироваться как C++. Это связано с тем, что старые версии функции malloc (до 1989 года) изначально возвращали указатель типа char*. Приведение типов может помочь разработчику выявить несоответствия в размерах типов, если тип целевого указателя изменится, особенно если указатель объявлен далеко от вызова malloc (хотя современные компиляторы и инструменты статического анализа могут предупреждать о подобном поведении и без явного приведения типов).

Недостатки литья

По стандарту C приведение типов избыточно. Добавление приведения типов может скрыть ошибку, связанную с отсутствием включения заголовочного файла stdlib.h, в котором содержится прототип функции malloc. В отсутствие прототипа для malloc, стандарт C90 требует, чтобы компилятор C предполагал, что malloc возвращает int. Если приведение типов отсутствует, C90 требует выдачи диагностического сообщения при присваивании этого целого числа указателю; однако, при наличии приведения типов, это сообщение не будет выдано, что скроет ошибку. На определенных архитектурах и в определенных моделях данных (например, LP64 на 64-битных системах, где long и указатели занимают 64 бита, а int – 32 бита), эта ошибка может фактически привести к неопределенному поведению, поскольку неявно объявленная функция malloc возвращает 32-битовое значение, в то время как реально определенная функция возвращает 64-битовое значение. В зависимости от соглашений о вызовах и структуры памяти, это может привести к повреждению стека. Эта проблема реже остается незамеченной в современных компиляторах, поскольку C99 не допускает неявных объявлений, поэтому компилятор должен выдавать диагностическое сообщение, даже если он предполагает возвращаемый тип int. Если тип указателя изменен при его объявлении, может потребоваться изменить все строки кода, где malloc вызывается и к которому применяется приведение типов.

Реализация

Реализация управления памятью во многом зависит от операционной системы и архитектуры. Некоторые операционные системы предоставляют распределитель для `malloc`, а другие – функции для управления определенными областями данных. Часто один и тот же динамический распределитель памяти используется для реализации как `malloc`, так и оператора `new` в C++.

dlmalloc и ptmalloc

Дуг Ли разработал dlmalloc (общественное достояние, "Doug Lea's Malloc") как универсальный распределитель памяти, начиная с 1987 года. Библиотека GNU C (glibc) является производной от ptmalloc ("pthreads malloc") Вольфрама Глогера, ответвления dlmalloc с улучшениями, связанными с многопоточностью. По состоянию на ноябрь 2023 года, последней версией dlmalloc является версия 2.8.6 от августа 2012 года.

dlmalloc – это распределитель с граничными тегами. Память в куче выделяется в виде "блоков" – 8-байтной выровненной структуры данных, содержащей заголовок и полезное пространство. Выделенная память содержит 8 или 16 байт служебной информации для хранения размера блока и флагов использования (аналогично вектору допинг-информации). Невыделенные блоки также хранят указатели на другие свободные блоки в полезном пространстве, что определяет минимальный размер блока в 16 байт для 32-битных систем и 24/32 (в зависимости от выравнивания) байта для 64-битных систем. Метод mmap позволяет избежать проблем, связанных с большими буферами, удерживающими небольшое выделение в конце их срока действия, но всегда выделяет целую страницу памяти, которая на многих архитектурах имеет размер 4096 байт. Разработчик игр Адриан Стоун утверждает, что dlmalloc, как распределитель с граничными тегами, не очень подходит для консольных систем, которые имеют виртуальную память, но не поддерживают подкачку страниц. Это связано с тем, что его механизмы сжатия и расширения пула памяти (/) нельзя использовать для выделения и фиксации отдельных страниц виртуальной памяти. При отсутствии подкачки страниц фрагментация становится более серьезной проблемой.

Джемаллок FreeBSD и NetBSD

С FreeBSD 7.0 и NetBSD 5.0 старая реализация malloc (разработанная Поулом Хеннингом Кампом) была заменена jemalloc, написанной Джейсоном Эвансом. Основной причиной этого стала недостаточная масштабируемость при многопоточной работе. Чтобы избежать взаимных блокировок, jemalloc использует отдельные "арены" для каждого процессора. Эксперименты по измерению количества выделений памяти в секунду в многопоточных приложениях показали, что это обеспечивает линейную масштабируемость с ростом числа потоков, в то время как для phkmalloc и dlmalloc производительность снижалась обратно пропорционально числу потоков.

Малокатив OpenBSD

В OpenBSD реализация функции malloc использует mmap. Для запросов размером более одной страницы вся область памяти выделяется с помощью mmap; меньшие размеры выделяются из пулов памяти, обслуживаемых malloc, в пределах нескольких "bucket pages" (страниц-ведер), которые также выделяются с помощью mmap. При вызове free память освобождается и отключается от адресного пространства процесса с помощью munmap. Эта система разработана для повышения безопасности за счет использования рандомизации адресного пространства и функций защитных страниц, реализованных в системном вызове mmap в OpenBSD, а также для обнаружения ошибок использования памяти после освобождения. Поскольку большая область памяти полностью отключается от адресного пространства после освобождения, дальнейшее использование приводит к ошибке сегментации и завершению программы. Проект GrapheneOS первоначально начал работу с портирования распределителя памяти OpenBSD в библиотеку Bionic C для Android.

Малокок

Хорд — это распределитель памяти, разработанный для обеспечения масштабируемой производительности выделения памяти. Подобно распределителю OpenBSD, Hoard использует исключительно mmap, но управляет памятью блоками по 64 килобайта, называемыми суперблоками. Куча Hoard логически разделена на единую глобальную кучу и несколько куч на процессор. Кроме того, существует кэш, локальный для каждого потока, способный хранить ограниченное количество суперблоков. Выделяя память только из суперблоков на локальной куче потока или процессора и перемещая преимущественно пустые суперблоки в глобальную кучу для повторного использования другими процессорами, Hoard поддерживает низкий уровень фрагментации и обеспечивает почти линейную масштабируемость с увеличением числа потоков.

Мималлок

Компактный универсальный распределитель памяти с открытым исходным кодом от Microsoft Research, ориентированный на производительность. Библиотека содержит около 11 000 строк кода.

Малокатор для кэширования потоков (tcmalloc)

У каждой нити есть локальное хранилище для небольших выделений памяти. Для больших выделений можно использовать mmap или sbrk. TCMalloc, malloc, разработанный компанией Google, имеет сборщик мусора для локального хранения памяти неактивных нитей. Считается, что TCMalloc более чем в два раза быстрее, чем ptmalloc из glibc для многопоточных программ.

Внутри ядра

Ядра операционных систем нуждаются в выделении памяти так же, как и прикладные программы. Однако реализация `malloc` в ядре часто существенно отличается от реализаций, используемых библиотеками C. Например, буферы памяти могут нуждаться в соответствии со специальными ограничениями, налагаемыми DMA, или функция выделения памяти может вызываться из контекста прерывания. Это требует реализации `malloc`, тесно интегрированной с подсистемой виртуальной памяти ядра операционной системы.

Превышение малок

Поскольку функции `malloc` и связанные с ними могут существенно влиять на производительность программы, часто возникает необходимость переопределять эти функции для конкретного приложения, используя специализированные реализации, оптимизированные под его шаблоны выделения памяти. Стандарт C не предоставляет для этого средств, однако операционные системы нашли различные способы реализации этой возможности, используя динамическую компоновку. Один из способов — подключение другой библиотеки для переопределения символов. Другой, применяемый в Unix System V.3, заключается в том, что `malloc` и `free` реализованы как указатели на функции, которые приложение может изменить, указав собственные реализации.

Расширения и альтернативы

Реализации библиотеки C, поставляемые с различными операционными системами и компиляторами, могут включать альтернативы и расширения стандартного интерфейса `malloc`. Одной из наиболее известных является:

`alloca`, которая выделяет запрошенное количество байтов в стеке вызовов. Отдельной функции освобождения памяти не предусмотрено, поскольку обычно память освобождается сразу после возврата вызывающей функции. `alloca` появилась в системах Unix еще в версии 32/V (1978), но её использование может быть проблематичным в некоторых (например, во встраиваемых) системах. Хотя многие компиляторы поддерживают `alloca`, она не входит в стандарт ANSI C и, следовательно, может быть непереносимой. Это также может приводить к незначительным проблемам с производительностью: она создаёт стековые фреймы переменного размера, что требует управления как указателем стека, так и указателем фрейма (при использовании стековых фреймов фиксированного размера один из этих указателей избыточен). Более крупные выделения памяти также могут повысить риск возникновения неопределённого поведения из-за переполнения стека. В C99 были предложены массивы переменной длины как альтернативный механизм выделения памяти в стеке, однако в более позднем стандарте C11 эта возможность стала необязательной. POSIX определяет функцию `posix_memalign`, которая выделяет память с выравниванием, заданным вызывающей стороной. Выделенная память освобождается функцией `free`, поэтому реализация обычно должна быть частью библиотеки `malloc`.