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

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

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

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

Ответ 1

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

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

Ответ 2

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

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

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

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

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

Ответ 3

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

Ответ 4

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

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

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

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

Но на этот раз мне повезло: я нашел это: http://hempeldesigngroup.com/embedded/stories/memorymanager/

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

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

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

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

Ответ 5

Поскольку версия 5.1, Lua разрешил a настраиваемый распределитель, который будет установлен, когда создает новые состояния.

Ответ 6

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

Ответ 7

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

Ответ 8

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

https://github.com/vitiral/tinymem

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

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

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