Динамическое распределение памяти C

Динамическое распределение памяти C означает выполнение ручного управления памятью для динамического распределения памяти на языке программирования C с помощью группы функций стандартной библиотеки C , а именно: маллок , перераспределить , каллок , выровненный_аллок и бесплатно .

Язык программирования C++ включает в себя эти функции; однако операторы новый и delete предоставляют аналогичную функциональность и рекомендуются авторами этого языка. Тем не менее, есть несколько ситуаций, в которых использование new/ delete неприменим, например код сборки мусора или код, чувствительный к производительности, а также комбинация malloc и размещение 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++).

Функция	Описание
malloc	выделяет указанное количество байтов
aligned_alloc	выделяет указанное количество байтов с указанным выравниванием
realloc	увеличивает или уменьшает размер указанного блока памяти, перемещая его при необходимости
calloc	выделяет указанное количество байтов и инициализирует их нулем
free	освобождает указанный блок памяти обратно в систему

Различия между malloc() и calloc()

• malloc() принимает один аргумент (объем выделяемой памяти в байтах), а calloc() принимает два аргумента — количество элементов и размер каждого элемента.
• malloc() только выделяет память, в то время как calloc() выделяет и устанавливает байты в выделенной области в ноль.

Пример использования

Создать массив из десяти целых чисел с автоматической областью действия на языке C очень просто:

int array[10];

Однако размер массива фиксируется во время компиляции. Если кто-то желает динамически выделить аналогичный массив без использования массива переменной длины , поддержка которого не гарантируется во всех реализациях C11 , можно использовать следующий код:

int *array = malloc(10 * sizeof(int));

При этом вычисляется количество байтов, которые десять целых чисел занимают в памяти, а затем запрашивается столько же байтов из malloc и присваивает результат указателю с именем array (из-за синтаксиса C указатели и массивы в некоторых ситуациях могут использоваться как взаимозаменяемые).

Потому что malloc может быть не в состоянии обслужить запрос, он может вернуть нулевой указатель , и хорошей практикой программирования является проверка на это:

int *array = malloc(10 * sizeof(int));
if (array == NULL) {
  fprintf(stderr, "malloc failed\n");
  return -1;
}

Когда программе больше не нужен динамический массив , она должна в конечном итоге вызвать free чтобы вернуть занимаемую им память в свободное хранилище:

free(array);

Память, оставленная malloc не инициализирован и может содержать мусор : остатки ранее использованных и отброшенных данных. После распределения с mallocэлементы массива являются неинициализированными переменными . Команда calloc вернет выделение, которое уже было очищено:

int *array = calloc(10, sizeof(int));

С помощью Realloc мы можем изменить размер памяти, на которую указывает указатель. Например, если у нас есть указатель, действующий как массив размером $n$ и мы хотим изменить его на массив размером $m$, мы можем использовать realloc.

int *arr = malloc(2 * sizeof(int));
arr[0] = 1;
arr[1] = 2;
arr = realloc(arr, 3 * sizeof(int));
arr[2] = 3;

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

Тип безопасности

malloc возвращает пустой указатель ( void *), что указывает на то, что это указатель на область неизвестного типа данных. Использование приведения требуется в C++ из-за строгой системы типов, тогда как в C это не так. Можно «привести» (см. преобразование типов ) этот указатель к определенному типу:

int *ptr, *ptr2;
ptr = malloc(10 * sizeof(*ptr)); /* without a cast */
ptr2 = (int *)malloc(10 * sizeof(*ptr)); /* with a cast */

У такого гипса есть свои преимущества и недостатки.

Преимущества кастинга

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

Недостатки кастинга

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

Распространенные ошибки

Неправильное использование динамического выделения памяти часто может быть источником ошибок. К ним могут относиться ошибки безопасности или сбои программы, чаще всего из-за ошибок сегментации .

Наиболее распространенные ошибки следующие:

Не проверять ошибки выделения

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

Утечки памяти

Невозможно освободить память с помощью free приводит к накоплению одноразовой памяти, которая больше не используется программой. Это приводит к пустой трате ресурсов памяти и может привести к сбоям распределения, когда эти ресурсы исчерпаны.

Логические ошибки

Все распределения должны следовать одной и той же схеме: распределение с использованием malloc, использование для хранения данных, освобождение с помощью free. Несоблюдение этого шаблона, например использование памяти после вызова free ( висячий указатель ) или перед вызовом malloc ( дикий указатель ), вызов free дважды («двойное освобождение») и т. д. обычно вызывает ошибку сегментации и приводит к сбою программы. Эти ошибки могут быть временными и трудными для отладки — например, освобожденная память обычно не сразу освобождается операционной системой, и поэтому висячие указатели могут сохраняться некоторое время и выглядеть работоспособными.

Кроме того, как интерфейс, предшествующий стандартизации ANSI C, malloc и связанные с ним функции имеют поведение, которое намеренно было оставлено на усмотрение реализации, чтобы она могла определить ее самостоятельно. Одним из них является распределение нулевой длины, что представляет собой большую проблему для realloc поскольку чаще всего размер изменяется до нуля. Хотя и POSIX , и Единая спецификация Unix требуют правильной обработки выделений нулевого размера путем возврата NULL или что-то еще, что можно безопасно освободить, не все платформы обязаны соблюдать эти правила. Среди множества ошибок, к которым это привело, WhatsApp RCE 2019 года. особенно выделялась Чтобы сделать эти функции более безопасными, можно обернуть их, просто проверив выделение нулевого размера и превратив его в размер 1. (Возврат NULL имеет свои проблемы: в противном случае это указывает на нехватку памяти. В случае realloc это означало бы, что исходная память не была перемещена и освобождена, что опять-таки не относится к размеру 0, что приводит к двойному освобождению.)

Реализации

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

На основе кучи

Смотрите также: сбрк

Реализация устаревших распределителей обычно выполнялась с использованием сегмента кучи . Распределитель обычно расширяет и сжимает кучу для выполнения запросов на выделение.

Метод кучи имеет несколько присущих ему недостатков:

• Линейный распределитель может сжиматься только в том случае, если освобождается последнее выделение. Даже если куча практически не используется, она может «застрять» на очень большом размере из-за небольшого, но долгоживущего выделения на ее вершине, которое может привести к потере любого объема адресного пространства, хотя некоторые распределители в некоторых системах могут освободить его полностью. пустые промежуточные страницы в ОС.
• Линейный распределитель чувствителен к фрагментации , в то время как хороший распределитель будет пытаться отслеживать и повторно использовать свободные слоты по всей куче, поскольку размеры выделения и время жизни смешиваются, и может быть сложно и дорого найти или объединить свободные сегменты, достаточно большие для размещения нового распределения. запросы.
• Линейный распределитель имеет чрезвычайно плохие характеристики параллелизма, поскольку сегмент кучи предназначен для каждого процесса, каждый поток должен синхронизироваться при выделении, а одновременное выделение из потоков, которые могут иметь очень разные рабочие нагрузки, усугубляет две предыдущие проблемы.

dlmalloc и ptmalloc

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

dlmalloc — распределитель граничных тегов. Память в куче выделяется в виде «кусков» — 8-байтовой выровненной структуры данных , которая содержит заголовок и полезную память. Выделенная память содержит 8- или 16-байтовые служебные данные для размера фрагмента и флагов использования (аналогично вектору допинга ). Нераспределенные фрагменты также хранят указатели на другие свободные фрагменты в полезной области пространства, в результате чего минимальный размер фрагмента составляет 16 байт в 32-битных системах и 24/32 (в зависимости от выравнивания) байт в 64-битных системах.

Нераспределенная память группируется в « корзины » одинакового размера, реализованные с помощью двусвязного списка фрагментов (с указателями, хранящимися в нераспределенном пространстве внутри фрагмента). Контейнеры сортируются по размеру на три класса:

• Для запросов размером менее 256 байт (запрос «малого контейнера») используется простой двухстепенный распределитель наилучшего соответствия. Если в этой ячейке нет свободных блоков, блок из следующей по величине ячейки делится на две части.
• Для запросов размером 256 байт или выше, но ниже порога mmap , dlmalloc, начиная с версии 2.8.0, использует на месте поиска побитовый алгоритм («treebin»). Если для удовлетворения запроса не осталось свободного места, dlmalloc пытается увеличить размер кучи, обычно с помощью системного вызова brk . Эта функция была введена после создания ptmalloc (начиная с версии 2.7.x), и в результате она не является частью glibc, который унаследовал старый распределитель наилучшего соответствия.
• Для запросов, превышающих пороговое значение mmap (запрос «большого контейнера»), память всегда выделяется с помощью системного вызова mmap . Порог обычно составляет 128 КБ. Метод mmap предотвращает проблемы с огромными буферами, захватывающими небольшое выделение в конце после истечения их срока действия, но всегда выделяет целую страницу памяти, размер которой на многих архитектурах составляет 4096 байт.

Разработчик игры Адриан Стоун утверждает, что dlmalloc, как распределитель граничных тегов, недружелюбен для консольных систем, которые имеют виртуальную память, но не имеют подкачки по запросу . Это связано с тем, что его обратные вызовы сокращаются и растут ( sysmalloc/ systrim) нельзя использовать для выделения и фиксации отдельных страниц виртуальной памяти. В отсутствие пейджинговой связи по запросу фрагментация становится более серьезной проблемой.

Jemalloc для FreeBSD и NetBSD

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

Malloc OpenBSD

OpenBSD Реализация malloc функция использует mmap . Для запросов размером более одной страницы все выделение извлекается с помощью mmap; меньшие размеры назначаются из пулов памяти, поддерживаемых malloc в пределах нескольких «страниц корзины», также выделенных mmap. При звонке в free, память освобождается и не отображается из адресного пространства процесса с помощью munmap. Эта система предназначена для повышения безопасности за счет использования преимуществ рандомизации структуры адресного пространства и функций пробелов в страницах, реализованных как часть OpenBSD. mmap системного вызова и для обнаружения ошибок использования после освобождения — поскольку большой объем памяти полностью не отображается после его освобождения, дальнейшее использование вызывает ошибку сегментации и завершение работы программы.

Проект GrapheneOS изначально начался с переноса распределителя памяти OpenBSD в библиотеку Android Bionic C.

Накопить маллок

Основная статья: Распределитель памяти

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

мималлок

Основная статья: мималлок

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

Кэширование потоков malloc (tcmalloc)

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

В ядре

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

Переопределение malloc

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

Наиболее распространенной формой в POSIX-подобных системах является установка переменной среды LD_PRELOAD с путем к распределителю, чтобы динамический компоновщик использовал эту версию malloc/calloc/free вместо реализации libc.

Ограничения размера выделения

Максимально возможный блок памяти malloc которые можно выделить, зависит от хост-системы, в частности от размера физической памяти и реализации операционной системы.

Теоретически наибольшее число должно быть максимальным значением, которое может храниться в size_t тип, который представляет собой зависящее от реализации целое число без знака, представляющее размер области памяти. В стандарте C99 и более поздних версиях он доступен как SIZE_MAX постоянная от <stdint.h>. Хотя это и не гарантируется ISO C , обычно это 2^(CHAR_BIT * sizeof(size_t)) - 1.

В системах glibc максимально возможный блок памяти malloc можно выделить только половину этого размера, а именно 2^(CHAR_BIT * sizeof(ptrdiff_t) - 1) - 1.

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

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

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

См. также

• Переполнение буфера
• Отладчик памяти
• Защита памяти
• Размер страницы
• Массив переменной длины

Внешние ссылки

• Определение malloc в стандарте IEEE Std 1003.1
• Леа, Дуг ; Проектирование основы аллокатора glibc
• Глогер, Вольфрам; Домашняя страница ptmalloc
• Бергер, Эмери; Домашняя страница клада
• Дуглас, Найл; Домашняя страница nedmalloc
• Эванс, Джейсон; Домашняя страница джемаллока
• Google; Домашняя страница tcmalloc
• Простые алгоритмы распределения памяти в сообществе OSDEV
• Майкл, Магед М.; Масштабируемое динамическое распределение памяти без блокировки
• Бартлетт, Джонатан; Внутреннее управление памятью . Выбор, компромиссы и реализации динамического распределения.
• Вики-страница Memory Reduction (GNOME) с большим количеством информации об исправлении malloc.
• Стандартный проект C99, включая TC1/TC2/TC3
• Некоторые полезные ссылки о C
• ISO/IEC 9899 – Языки программирования – C
• Понимание glibc malloc