Посоветуйте готовый менеджер памяти Опции

[pernatui]

Может быть существуют в открытом коде менеджеры памяти для ARM. Памяти 64к.

Заранее спасибо!

[HARMHARM]

Уважаемый Zltigo выкладывал здесь.

[pernatui]

большое спасибо буду изучать..нашел упоминание об эффективных менеджерах в Micro/OS
на основе этой идеи есть менеджер в Boost. Правда он на c++ и наверное может отожрать много памяти и ресурсов. Хотя при компиляции под IA-32 гораздо эффективнее malloc

[Сергей Борщ]

Правда он на c++ и наверное может отожрать много памяти и ресурсов. Хотя при компиляции под IA-32 гораздо эффективнее malloc

Какой-то набор бессмысленных фраз. Что такое malloc как не одна из функций менеджера памяти? С чего бы грамотно написанному С++ приложению жрать лишнюю память и ресурсы? Ну и наконец: в С++ операторы new и delete вызывают все те же malloc() и free().

[pernatui]

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

[sergeeff]

Я уже неоднократно призывал посмотреть форумчан в сторону достаточно нового аллокатора tlsf: http://rtportal.upv.es/rtmalloc/. Написан на С, ставится на любую систему в течение получаса и отличается высоким быстродействием и эффективностью.

[Quasar]

Я уже неоднократно призывал посмотреть форумчан в сторону достаточно нового аллокатора tlsf: http://rtportal.upv.es/rtmalloc/. Написан на С, ставится на любую систему в течение получаса и отличается высоким быстродействием и эффективностью.

Я посмотрел и даже прилепил к FreeRTOS. Пока впечатление только положительные.

[sergeeff]

Я посмотрел и даже прилепил к FreeRTOS. Пока впечатление только положительные.

Вот и я об том же. Испанцы несколько лет разрабатывали этот менеджер и сейчас он вполне работоспособен.

[Rst7]

Написан на С, ставится на любую систему в течение получаса

Если есть алгоритм, пофиг, на чем писано. Так что это не достоинства, а так, пеар

и отличается высоким быстродействием и эффективностью.

Скажем так, O(1) (а именно такое у него быстродействие) куплено ценой перерасхода ОЗУ. Велик он (перерасход) или нет - зависит от основного кода, как он работает с кучей.

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

Обычные менеджеры требуют довольно длительной блокировки кучи как ресурса - на то время, пока собственно и выполняются действия по занятию/освобождению кусочка. Это часто не позволяет применять прямую работу с кучей в различных реалтаймовых процедурах - вполне возможно, что из-за блокировки кучи как ресурса, будет занято слишком много времени. Стандартный выход - аллоцирование кусочков (обычно фиксированной длинны) для таких задач из заранее заготовленных пулов с соответствующей узкозаточенностью. Пример (хотя и аппаратный) - очереди кусочков в MAC'ах LPC, SAM7, и т.д. Но хотелось бы иметь универсальный алгоритм (и один malloc/free на весь софт).

Я сейчас большей универсальности добиваюсь следующим способом:

1. Размер аллоцируемых кусочков округляется до некоторой логарифмической сетки (этим уменьшается общее количество различных размеров, но и растет перерасход по памяти).
2. Для каждого размера заранее создается связанный список уже заготовленных кусочков (аллоцированных из большой кучи). Начальное количество в каждой цепочке выбирается исходя из тестовых прогонов софта.
3. Аллоцирование кусочка представляет из себя:
а) табличное округление желаемого размера до выбранной сетки (в большую сторону, конечно),
б) получение начального адреса связанного списка, соответствующего округленному размеру,
в) извлечение из односвязного списка первого элемента.
4. Деаллоцирование - простой возврат кусочка в необходимый список (тоже выполняется в начало списка).
5. В отдельном низкоприоритетном процессе запас кусочков в связанных списках поддерживается на каком-то выбранном уровне (задается по результатам тестовых прогонов). Естественно, это происходит возвратом кусочков из списков в большую кучу (если кусочков слишком много) и занятием новых кусочков и добавлением в список (если кусочков слишком мало).
6. В пункте 3 есть аварийный режим (ежели нужный список пуст) - большая блокировка на занятии кусочка из большой кучи. При правильно выбранных коэффициентах в пункте 5 этот пункт никогда не случается

Только пункт 3в (и аналогичный код в возврате кусочка) требует блокировки ресурсов. Причем, т.к. код, выполняемый в состоянии блокировки минимален (не в смысле О(1), а в самом прямом смысле - не более десятка команд процессора), то оказывается вполне возможным производить блокировку не поднятием больших примитивов синхронизации на уровне ОС, а банальным запрещением прерываний.

[AlexandrY]

По этой ссылке голый алгоритм хотя и работоспособный.
Это не то что обычно нужно малым embedded системам.
Там и авторы все время подчеркивают для каких сценариев использования делали алгоритм.
Он сделан для мультимедийных приложений где реально применимы статистические модели.
А для малых embedded с 64K на борту это совсем неприменимо, там запросы на память можно на пальцах пересчитать.
Тем более что алгоритм TLSF сразу отжирает около 10K на свой мапинг и реально его процедуры будут медленее выполнятся по сравнению с простейшими списочными менеджерами в пределах 64K.

Вообщем IMHO: менеджер малой системы должен главное быть многозадачным, чтоб не мудрить самому с семафорами (в TLSF этого нет), иметь фичу выделения пулов блоков фиксированной длины (в TLSF этого нет) , иметь возможность ожидания освобождения памяти (в TLSF этого нет), иметь диагностические тулсы и логи для идентификации утечек памяти(в TLSF этого нет).

Я уже неоднократно призывал посмотреть форумчан в сторону достаточно нового аллокатора tlsf: http://rtportal.upv.es/rtmalloc/. Написан на С, ставится на любую систему в течение получаса и отличается высоким быстродействием и эффективностью.

Браво, вы изобрели велосипед!
Ну точно, такую же идею я тож "изобрел" лет 6-ть назад, пока не обнаружил что это повсеместно юзают во всех серьезных коммуникационных стеках.
Но тут еще есть нюансик.
Для таких приложений как Ethernet-а не нужно выделять непрерывные области, там с успехом применяеться DMA по связным спискам.
И моя "идея" пошла лесом.

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

Я сейчас большей универсальности добиваюсь следующим способом:

[Rst7]

Браво, вы изобрели велосипед!

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

А определять тестовыми прогонами оптимальную сетку нарезки для блоков фиксированной длины это гемор почище чистых malloc-ов.

Сетка задана изначально (у меня обычно применяется шаг 1.5). Начальное количество при инициализации менеджедра - вот это да, это опытным путем. Но совсем не обязательно. На самом деле, даже задание нулевых размеров приведет в начале к тормозам системы (потому что все время будет выполняться "аварийный" режим по пункту 6), пока не устаканится некоторое среднее значение с запасом (определяется порогами в низкоприоритетном процессе).

В реальной жизни профилирование весьма несложно. Но зато дает отличные результаты.

Но тут еще есть нюансик.
Для таких приложений как Ethernet-а не нужно выделять непрерывные области, там с успехом применяеться DMA по связным спискам.

Да, это ньюанс. Но он связан с тем, что DMA уже заточен под список. А часто это еще и полностью своя отдельная область памяти, в которой он (DMA) может разгуляться. Так вот пусть там и гуляет, нефиг туда своими менеджерами лезть

[AlexandrY]

Мда, это находка, патентовать надо
Эт уже только в операционках под чипы с MMU пулами памяти управляют динамически.

Но по жизни реально не приходиться сильно напрягаться с менеджерами памяти поскольку как я сказал коммуникационные стеки имеют свои менеджеры узко заточеные, GUI тож снабжаются своими менеджерами, файловые системы так просто тупо статически себе буферы выделяют.
Что остается? Только своя самописанная часть.
Ну так поставить операционку с менеджером и закрыть тему. Я так всегда рекомендую Keil RTX Kernel. Тупая, быстрая и проблему выравниваний понимает.

Есть еще нюансы требующиеся при выделении памяти: она должна в SoC ARM-ах выделяться в большинстве случаев выровненной по границе 4, часто 8 и иногда 16 и больше байт, причина в особенностях DMA и шинной архитектуры. Этого не учитывают менеджеры пришедшие из других архитектур.

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

[Rst7]

Мда, это находка, патентовать надо Эт уже только в операционках под чипы с MMU пулами памяти управляют динамически.

Как то неуместна ирония. Я совсем не претендую на "изобретение" (так, делюсь опытом). Кроме того, мне кажется, я достаточно прозрачно объяснил смысл такого действа - минимизация нахождения в заблокированном состоянии (не в терминах "О(чегото)", а в командах или тактах) и универсальность (одна куча и один интерфейс на всех и вся). А эта универсальность приводит к тому, что чуть ли ни единственным сервисом ОС для межзадачного взаимодействия становится канал (pipe), реализуемый в виде односвязного списка сообщений. Причем, этот канал имеет минимум накладных расходов - ведь менеджер кучи очень быстр.

[sergeeff]

Если нет памяти и хочется чего по-проще, есть знаменитый BGET http://www.fourmilab.ch/bget/, который живет с 1972 в миллионах embedded приложений.

[AlexandrY]

Я вообще-то без иронии, хотел типа уважительно выразиться.

Но кто реализует по такой вашей коротенькой спецификации этот алгоритм?
А выложете, так скажем, опенсорсом?

А между тем в местном архиве пяток исходников операционок лежит с готовыми проверенными менеджерами памяти.
И тогда вопрос как всегда упирается в выбор операционки.

Как то неуместна ирония. Я совсем не претендую на "изобретение" (так, делюсь опытом). Кроме того, мне кажется, я достаточно прозрачно объяснил смысл такого действа - минимизация нахождения в заблокированном состоянии (не в терминах "О(чегото)", а в командах или тактах) и универсальность (одна куча и один интерфейс на всех и вся). А эта универсальность приводит к тому, что чуть ли ни единственным сервисом ОС для межзадачного взаимодействия становится канал (pipe), реализуемый в виде односвязного списка сообщений. Причем, этот канал имеет минимум накладных расходов - ведь менеджер кучи очень быстр.

[sergeeff]

Я вообще-то без иронии, хотел типа уважительно выразиться.

1. Вы не очень внимательно посмотрели тексты TLSF в плане многозадачности.
2. Авторы позиционируют свой TLSF как альтернативу другим менеджерам памяти для Linux.

Ваши требования к "малым" системам уметь выделять пулы блоков постоянной длины, по-моему, слишком специфические. Посмотрите, для примера, как народ сделал в LWIP - действительно написал для этого случая свой специфический аллокатор, не имеющий ничего общего со стандартной кучей.

Мораль - для специфических требований, специфический аллокатор. Автор ветки ничего специфического не требовал.

[pernatui]

спасибо за коментарии..Применение аллокатор для сетевого стека, для которого типично наличие специфичных размеров = размеров пакетов на каждом из уровне.

У boost как есть возможность программно делать пулы для одинакового размера буферов. Буду пробовать tslf...

[Rst7]

Применение аллокатор для сетевого стека, для которого типично наличие специфичных размеров = размеров пакетов на каждом из уровне.

Секундочку. Там за Вас уже разработчики камня подумали - в том смысле, что MAC DMA уже оперирует связными списками. Посмотрите, как планируемый аллокатор будет дружить с этим DMA и подумайте... Крепко подумайте...

[AlexandrY]

Ваша правда по пункту 1. Там действительно обнаружилось еще пару функций обернутых мьютексами в стиле POSIX.
Недоглядел.
Сам алгоритм TLSF, я конечно уважаю, но это полуфабрикат все таки. Под боевую платформу его еще точить и точить.

Какие требования к малым системам характерны мне кажется я знаю. Портировал uCOS на процы с 2K RAM-а.
Каких и сколько влезет задач в 64K тож как бы представляю. Не разбежишься там.
Человек неминуемо через месяцок будет помнить там все задачи на перечет и даже последовательность их выполнения.
Такое возможно в малых системах и в этом принципиальное отличие от линукса где даже гуру не знают и 10% задач крутящихся в их системе.
В линуксе можно применить статистику, а в малой системе эффективнее может оказаться ручной тюнинг собственно приложения на использование блоков фиксированной длины. (не путать с тюнингом типоразмеров самих блоков менеджера)
Менеджер с блоками фиксированной длины вообще не имеет фрагментации и таким образом гораздо лучше TLSF для малых систем.
И в системе с 64K я думаю это правило еще действует.
Недавно ворочал проект с довольно крупным стеком ZigBee от TI и они там не поленились тюнингировать все приложение и операционку под менеджер с блоками фиксированной длины.
Так что говорить о специфичности таких менеджеров не приходится.

Речь даже не о том кто какого мнения, а о том что если хотите потерять 20K (служебная инфа + неминуемая фрагментация) из 64-х - применяйте TLSF

1. Вы не очень внимательно посмотрели тексты TLSF в плане многозадачности.
2. Авторы позиционируют свой TLSF как альтернативу другим менеджерам памяти для Linux.

Ваши требования к "малым" системам уметь выделять пулы блоков постоянной длины, по-моему, слишком специфические.

[sergeeff]

Никак не могу понять, откуда вы взяли цифру 20К, которую съедает TLSF? Да, там есть накладные расходы на каждый выделяемый блок. Но именно эта дополнительная информация и позволяет минимизировать ту самую фрагментацию, о которой вы говорите. Из статически выделяемых - один массив table[]

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

[AlexandrY]

Что тут непонятного, посчитайте сколько тот массив table займет с макросами объявленными по дефолту, прикиньте размер объявленных типов, сделайте поправку на выравнивание, прикиньте средний размер выделяемого блока, рассчитайте их количество, умножьте на размер служебной структуры, опять учтите выравнивание, добавьте процент который авторы оставляют на фрагментацию и прикиньте сколько разработчик оставит резерва чтобы не упереться в потолок. 20K еще будет оптимистично.
И это в то время когда есть приемлемые методы вообще без фрагментации и более быстрые.

А я чтоль противник TLSF?
Тока уточняю особенности ее тактического применения

Никак не могу понять, откуда вы взяли цифру 20К, которую съедает TLSF? Да, там есть накладные расходы на каждый выделяемый блок. Но именно эта дополнительная информация и позволяет минимизировать ту самую фрагментацию, о которой вы говорите. Из статически выделяемых - один массив table[]

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

[MALLOY2]

Могу предложить мной писанный менагер.

Главным шагом для написания своего менагера была отладка и контроль того как приложение использует кучю, тобиш что куда и сколько кладет, какое пиковое использование кучи. После отладки эти фичи отключаются дабы не съедать ресурсы. Быстродействие быстрее чем стандартные функции IAR и уж тем более быстрее чем TSLF (с другими не измерялся). Менеджер делает примитивную фрагментацию в виде слияния свободных блоков в один.

Естественно перед написанием просмотрел много всяких менеджеров вот что могу сказать про TSLF, для таких систем где памяти десятками мегабайт измеряется и очень сложные ОС работают то он может и сыграет кой какую роль, то для контроллеров там где сотни килобайт это никуда не годится. Работает TSLF медленней библиотечной функции, у меня он на таблицу сожрал 3к памяти при куче всегото в 16к куда такое годится! Вобщем не наш это менеджер .

P.S. менеджер потоко не защищенный, используйте синхроницию вашей ос. У меня работет с FreeRTOS и LwIP. Будут вопросы пишите или в аську.

Прикрепленные файлы

 1111.ZIP ( 6.45 килобайт ) Кол-во скачиваний: 77

 

[sergeeff]

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

[MALLOY2]

Естественно, я проверял на пропускной способности стека LwIP c тем или иным менеджером, при динамичном обмене с переменным размером пакета. TLSF пролетает ... еще раз это менеджер для больших серьезных систем там где куча сотни мегабайт, BGET я не пробывал.

[sergeeff]

Мы лет 6 используем во всех разработках BGET. Когда я его пробовал использовать совместно с LWIP, то он тоже проигрывал встроенному менеджеру. На мой взгляд, подход, реализованный в LWIP очень неплох. Хочешь, используй свой менеджер, не хочешь - вот тебе наш готовый.

[dch]

в u-boot-е или арм буте есть компактный хорошо проверенный менеджер памяти