Что такое хороший распределитель памяти C для встроенных систем? [закрыто]

Question

У меня есть однопоточное встроенное приложение, которое выделяет и освобождает множество маленьких блоков (32-64b). Идеальный сценарий для распределителя на основе кэша. И хотя я мог бы ПОПРОБОВАТЬ, чтобы написать один, это, вероятно, будет пустой тратой времени, и не так хорошо проверено и настроено, как какое-то решение, которое уже было на переднем крае.

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

Примечание: я использую виртуальную машину Lua в системе (которая является виновником 80 +% выделений), поэтому я не могу легко реорганизовать мой код для использования выделений стека для увеличения производительности выделения.

Answer 1

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

В вашем случае это кажется оправданным; при условии, что вы не можете починить ВМ, эти крошечные выделения очень расточительны. Я не знаю, какова вся ваша среда, но вы могли бы рассмотреть упаковку вызовов malloc / realloc / free только на виртуальной машине, чтобы вы могли передать ее обработчику, предназначенному для небольших пулов.

Answer 2

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

Базовая реализация включала набор подпрограмм, которые управляли буферами заданного размера. Подпрограммы использовались в качестве оберток вокруг malloc () и free (). Мы использовали эти подпрограммы для управления размещением часто используемых структур, а также для управления общими буферами заданных размеров. Структура использовалась для описания каждого типа управляемого буфера. Когда был выделен буфер определенного типа, мы выполняли malloc () память в блоках (если список свободных буферов был пуст). То есть, если бы мы управляли 10-байтовыми буферами, мы могли бы создать один malloc (), который содержал бы место для 100 из этих буферов, чтобы уменьшить фрагментацию и количество необходимых базовых malloc.

В начале каждого буфера будет указатель, который будет использоваться для связывания буферов в свободном списке. Когда 100 буферов были выделены, каждый буфер был бы объединен в свободный список. Когда буфер использовался, указатель был бы установлен в нуль. Мы также вели список «блоков». буферов, чтобы мы могли выполнить простую очистку, вызвав free () для каждого из существующих буферов malloc'd.

Для управления динамическими размерами буфера мы также добавили переменную size_t в начале каждого буфера, сообщающую размер буфера. Затем он использовался для определения того, в какой блок буфера помещать буфер, когда он был освобожден. У нас были подпрограммы замены для malloc () и free (), которые делали арифметику указателей, чтобы получить размер буфера и затем поместить буфер в свободный список. У нас также было ограничение на размер буферов, которыми мы управляли. Буферы, превышающие этот предел, были просто malloc'd и переданы пользователю. Для структур, которыми мы управляли, мы создали процедуры-оболочки для выделения и освобождения определенных структур.

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

Answer 3

Я немного опоздал на вечеринку, но я просто хочу поделиться очень эффективным распределителем памяти для встраиваемых систем, которые я недавно обнаружил и протестировал: https://github.com/dimonomid/umm_malloc

Это библиотека управления памятью, специально разработанная для работы с ARM7, лично я использую ее на устройстве PIC32, но она должна работать на любом 16- и 8-разрядном устройстве (у меня есть планы на тестирование на 16-разрядном PIC24 , но я еще не проверял)

Я был серьезно побежден фрагментацией с распределителем по умолчанию: мой проект часто выделял блоки различного размера, от нескольких байтов до нескольких сотен байтов, и иногда я сталкивался с ошибкой «нехватка памяти». Мое устройство PIC32 имеет 32 КБ ОЗУ, а для кучи используется 8192 байта. В данный момент доступно более 5 КБ свободной памяти, но из-за фрагментации распределитель по умолчанию имеет максимальный нефрагментированный блок памяти всего около 700 байт. Это очень плохо, поэтому я решил поискать более эффективное решение.

Я уже знал о некоторых распределителях, но у всех них есть некоторые ограничения (например, размер блока должен быть степенью или 2, начиная не с 2, а, скажем, с 128 байтов), или был просто глючный. Каждый раз мне приходилось возвращаться к распределителю по умолчанию.

Но на этот раз мне повезло: я нашел этот: http: // hempeldesigngroup .com / встроенный / рассказы / MemoryManager /

Когда я попробовал этот распределитель памяти, в точно такой же ситуации с 5K свободной памяти, он имеет блок более 3800 байт! Это было так невероятно для меня (по сравнению с 700 байтами), и я провел жесткий тест: устройство работало более 30 часов. Нет утечек памяти, все работает как надо. Я также нашел этот распределитель в репозитории FreeRTOS: http://svnmios.midibox.org/listing.php?repname=svn.mios32&path=%2Ftrunk%2FFreeRTOS%2FSource%2Fportable%2FMemMang%2F&rev=1041&revg= 1041 # , и этот факт является дополнительным доказательством стабильности umm_malloc. Поэтому я полностью переключился на umm_malloc, и я вполне доволен этим.

Мне просто пришлось немного его изменить: конфигурация была немного ошибочной, когда макрос UMM_TEST_MAIN не определен, поэтому я создал репозиторий github (ссылка вверху этого поста). Теперь зависящая от пользователя конфигурация хранится в отдельном файле umm_malloc_cfg.h

Я еще глубоко не разбираюсь в алгоритмах, применяемых в этом распределителе, но он имеет очень подробное объяснение алгоритмов, поэтому любой желающий может заглянуть в начало файла umm_malloc.c. По меньшей мере, «биннинг» подход должен дать огромную выгоду в меньшей фрагментации: http://g.oswego.edu/dl /html/malloc.html

Я считаю, что любой, кому нужен эффективный распределитель памяти для микроконтроллеров, должен хотя бы попробовать этот.

Answer 4

Хотя прошло уже некоторое время с тех пор, как я спросил об этом, мое окончательное решение заключалось в том, чтобы использовать SmallObjectAllocator от LoKi, но он прекрасно работает. Избавился от всех вызовов ОС и улучшил производительность моего движка Lua для встроенных устройств. Очень красиво и просто, всего за 5 минут работы!

Answer 5

Начиная с версии 5.1 , Lua разрешил пользовательский распределитель , который нужно установить при создании новых состояний .

Answer 6

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

Answer 7

Я использовал систему «бинарного приятеля» для хорошего эффекта в vxworks. По сути, вы разделяете свою кучу, разрезая блоки пополам, чтобы получить наименьшую мощность двухразмерного блока для удержания вашего запроса, а когда блоки освобождаются, вы можете сделать проход по дереву, чтобы объединить блоки обратно, чтобы уменьшить фрагментацию. Поиск в Google должен найти всю необходимую информацию.

Answer 8

Я пишу распределитель памяти C с именем tinymem, который предназначен для возможности дефрагментации кучи и повторного использования памяти. Проверьте это:

https://github.com/vitiral/tinymem

Примечание: этот проект был прекращен для работы над реализацией ржавчины:

https://github.com/vitiral/defrag-rs

Кроме того, я не слышал о umm_malloc раньше. К сожалению, он не в состоянии справиться с фрагментацией, но он определенно выглядит полезным. Я должен буду проверить это.