Распределение динамической памяти C - C dynamic memory allocation

Стандартная библиотека C
Общие темы
Разные заголовки

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

Язык программирования C ++ включает эти функции; однако операторы new и delete предоставляют аналогичные функции и рекомендуются авторами этого языка. Тем не менее, есть несколько ситуаций, в которых использование new/deleteне применимо, например, код сборки мусора или код, чувствительный к производительности, и вместо оператора более высокого уровня может потребоваться комбинация mallocи . placement newnew

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

Обоснование

Язык программирования C управляет памятью статически , автоматически или динамически . Переменные статической продолжительности выделяются в основной памяти, обычно вместе с исполняемым кодом программы, и сохраняются в течение всего времени существования программы; переменные с автоматической продолжительностью выделяются в стеке и приходят и уходят, когда функции вызываются и возвращаются. Для переменных static-duration и automatic-duration размер выделения должен быть константой времени компиляции (за исключением случая автоматических массивов переменной длины). Если требуемый размер неизвестен до времени выполнения (например, если данные произвольного размера считываются от пользователя или из файла на диске), то использование объектов данных фиксированного размера неадекватно.

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

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

В исходном описании C указано, что callocи cfreeбыли в стандартной библиотеке, но нет malloc. Код для простой модели реализации диспетчера хранилища для Unix был дан вместе с функциями пользовательского интерфейса allocи freeв качестве функций пользовательского интерфейса, а также с использованием sbrkсистемного вызова для запроса памяти у операционной системы. Документация Unix 6-го издания дает allocи freeкак функции распределения памяти низкого уровня. mallocИ freeпроцедуры в их современной форме полностью описаны в руководстве 7 издание Unix.

Некоторые платформы предоставляют вызовы библиотек или встроенных функций, которые позволяют динамическое распределение во время выполнения из стека C, а не из кучи (например alloca()). Эта память автоматически освобождается, когда вызывающая функция завершается.

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

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

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

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

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

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

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

int array[10];

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

int *array = (int*)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 мы можем изменить размер памяти, на которую указывает указатель. Например, если у нас есть указатель, действующий как массив размера, и мы хотим изменить его на массив размера , мы можем использовать 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 ( void *), который указывает, что это указатель на область неизвестного типа данных. Использование приведения типов требуется в C ++ из-за сильной системы типов, тогда как в 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-битными и int32-битными) эта ошибка может фактически привести к неопределенному поведению, поскольку неявно объявленное mallocвозвращает 32-битное значение, тогда как фактически определенная функция возвращает 64-битное значение. В зависимости от соглашений о вызовах и разметки памяти это может привести к разбиению стека . Эта проблема вряд ли останется незамеченной в современных компиляторах, поскольку C99 не допускает неявных объявлений, поэтому компилятор должен произвести диагностику, даже если он предполагает intвозврат.
  • Если тип указателя изменяется при его объявлении, может также потребоваться изменить все строки, в которых mallocвызывается и выполняется приведение.

Общие ошибки

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

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

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

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

Реализации

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

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

См. Также: sbrk

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

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

dlmalloc и ptmalloc

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

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

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

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

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

Jemalloc для FreeBSD и NetBSD

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

OpenBSD malloc

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

Клад маллок

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

Hoard - это распределитель, целью которого является масштабируемая производительность выделения памяти. Подобно распределителю OpenBSD, Hoard использует mmapисключительно память, но управляет ее фрагментами по 64 килобайта, называемыми суперблоками. Куча Hoard логически разделена на одну глобальную кучу и несколько куч для каждого процессора. Кроме того, существует локальный кэш потока, который может содержать ограниченное количество суперблоков. Распределяя только из суперблоков в локальной куче для каждого потока или процессора и перемещая в основном пустые суперблоки в глобальную кучу, чтобы их можно было повторно использовать другими процессорами, 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указатели функций, которые приложение может сбросить на пользовательские функции.

Пределы размера размещения

Максимально возможный блок памяти, который 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.

Смотрите также

использованная литература

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