Как ни крути, а динамическая память всеравно рано или поздно становится необходимой...
Готовые реализации использовать не могу по многим причинам(необходимость иметь несколько арен, thread-safety итп).
Нужен аллокатор, который будет давать минимальную фрагментацию в реальных условиях,минимальный обьем служебной памяти, производительность не особо важна, тк размер арены от силы 32кб.

Реальные условия - одни блоки памяти живут практически forever, другие выделяются/освобождаются подобно стековым переменным - в начале/конце функции соответственно. Блоки разной длины, от 16 до 1024 байт, редко больше. Юзать стек для этого не канает, тк нужно резервировать большие стеки для каждого потока, а это память будет использована на 5-10% в 90% времени.
В основном такое поведение имеет место в GUI и всяких обменах сообщениями, где сами алгоритмы гораздо тяжелее, чем аллокатор.

Пока сделал классическую реализацию best-fit, из служебных полей только размер,бит free/used в начале и в конце блока для облегчения free() и слияния соседних пустых блоков, тобышь заголовок весит 8 байт. Работает все гуд, но хз как оно будет при длительной работе девайса(ну там месяц,2,3).
Курил всякие разные реализации, но там делается упор в основном на производительность, а про фрагментацию редко где упоминается.
По рандом-бенчмаркам best-fit типа рулит, но смущает его тенденция к накоплению кучи маленьких(малоюзабельных) блоков.
First-fit, даже на простых тестах в моих реальных условиях показал гораздо худшую фрагментацию, чем best-fit. next-fit еще хуже.

Если кто-то имел дело с использованием,разработкой аллокаторов - буду благодарен за любую информацию...

Я в свое время заморачивался, даже делал дефрагментатор, но это оказалось ненадежным, потому как в таких системах сложно добится детерменирванного времени захвата/высвобождения куска памяти.
По сему я остановился на варианте т.н. pool памяти, но таких пулов не один, а несколько - каждый имеел различный размер кусочков (slice).
Так же был диспетчер всех этих пулов, который сам выбирал при захвате пул с наиболее подходящим размером кусочка.
Т.е. в каждом пуле кусочки равного размера в пределах самого пула, но у каждого пула свой размер кусочков.
Так же этот диспетчер собирал статистику в рабочем режиме, и пре перезапуске прошивки автоматически создавал пулы с размерами кусочков и их числом на основании статистики последнего сеанса работы прошивки (статистика писалась в eeprom).
Пул-память дает четко детерменированное время захвата/освобождения кусочков.
Да и фрагментация как таковая тут полностью отсутствует.
Работало вполне эффективно.
Потом я это переписал на С++ с использованием smart pointer, стало еще удобнее работать - в коде нигде не было new/delete, куски сами освобождались, если на них уже никто не ссылался. Ориентировалось под применение RTOS, хотя можно и без нее.
А обычная куча со всеми ее недостатками, имхо, во встраиваемых приложениях - капризная и ненадежная вещь, уж лучше тогда взять проц с большим объемом памяти, чем кучу использовать. Я стараюсь избегать кучи в embedded проектах.
Ну как-то так

Спасибо.

Дефрагментатор не годится, тк мы не можем менять физический адрес, mmu в cortex-m3 нету. При наличии mmu, страничной адрессации(виртуальной памяти) фрагментация практически не страшна..

С пулами идея интересная, особенно статистика
В принципе можно модифицировать best-fit так, чтобы он не разбивал блоки малого обьема, а оставлял как есть. По идее, тогда туда будут падать те же запросы. Хотя такое ограничение уже есть - свободный блок дожнен быть такой, чтобы туда влезли заголовки и хотябы одно слово памяти (сейчас это 12байт), можно просто этот предел увеличить.
Благо, риалтайм не нужно, GUI,сеть,.. вещи довольно не риалтайм да и ОС у меня тоже не рт. Вообще рт вещи привык делать без OС на отдельных камнях, но эт уже не та тема..


Ну их больше как-бы нету 64кб практически потолок, если забить все статикой и стеками, то не хватит их, при чем процентов 80 будет реально пустовать. Тут только внешняя память решает, но это дорого. Был бы мегабайт - стека вполне хватило бы..
Согласен, кучи - зло, но динамическая память нужна

За smart pointer спасибо. подобную технику reference counter уже использую, но там aquire и forget кишит, ну да, delete нету
А про него можно по подробнее, как удалось избавится от слежения(new,delete,aquire,forget) за обьектом?

апд.

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

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

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


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

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

smart pointer пытаюсь что-то такое слепить, вроде получается обьеденить reference counter с smart pointer-ом + всякая хитрая перегрузка. не охота сильно наворачивать

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

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

Раз у вас не хватает памяти чтобы распределить её в виде static или на стеке для всех потоков, значит возможна ситуация (и даже с большей вероятностью), когда много потоков запросит больше памяти чем есть. С наличием служебных полей управления блоками в heap и фрагментации это даже более вероятно, чем при static размещении.
Что ваша система должна делать при этом? Выдать отказ потоку (но значит алгоритм всех потоков должен рассчитывать, что может быть получен отказ в памяти)? Или приостановить выполнение потока (но может случиться dead-lock)?

Я полностью согласен с Forger - делаю так же - стараюсь обходиться static. Если невозможно - использую динамическое выделение блоков фиксированной длины. Даже в довольно сложных проектах с многими потоками нигде не использую стандартный heap.
Также помогает знание алгоритма работы потоков: где-то можно использовать union если нет одновременного использования памяти, где-то можно ставить семафоры на функции использующие большие блоки статической памяти и т.п.

Как вы, интересно, определили его эффективность.
Как то не приходилось видеть движков которые бы сами эффективно могли бы создавать правильные распределения пулов фиксированного размера.
Да и сомнительно насчет сбора статистики. Сама такая статистика требует heap-а неопределенного размера.
А если все таки статистика была компактной, то какой смысл был ее собирать, анализ исходников ответил бы на все вопросы.

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

Вообще, в моих реальных проектах это нафик не было нужно: я просто закладываю больше памяти.
Так выходит быстрее, проще и надежнее А цена ОЗУ? Так в моих проектах она вообще некритична - мелкосерийные изделия, епта.


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


Мне кажется, что анализ исходников не даст полной картины в многопоточном приложении, в динамике.
Но анализ кода даст точную картину при статических объектах, да и это сам компилятор/линкер дает

При таком использовании может подойти аллокатор, который выделяет память последовательно из пула фиксированного размера и не освобождает её. Освобождается весь пул при выходе из функции. А пулы памяти можно выделять, например, с помощью bitmap allocator.

Таки ваша правда... Но работать с динамикой гораздо удобнее, чем передавать в каждую функцию указатели на буфферы, да еще и следить везде за размером.
Потом это не просто буфферы, а там классы, программа будет пестреть reinterpret_cast, что вообще не красиво и склонно к образованию разных багов.
В принципе серьезно задумываюсь над стеком, разделить тяжелые потоки и легкие отдельно. надо написать хороший анализатор стека, чтобы indirect-высовы понимал(виртуальные классы), рекурсия - фиг с ней, редко где применяется. Сейчас я сделал анализатор стека, но он понимает все, кроме индирект call...

кому надо - могу дать.


Да, вариант тоже неплох, обдумаем, спасибо

Что значит ненадёжная? Чем она более ненадёжная, чем любой другой элемент программирования.
Я делал. Только дефрагментацию делал в защищённой секции. Причём не всю дефрагментацию, а лишь её завершающую стадию. Всё работало устойчиво.
Универсально задача решается сложно. А вот под реальную задачу можно поэкспериментировать.

Понятно, что раз такой вопрос становится, то принципиально может возникнуть ситуация, когда память не может быть выделена. Значит алгоритм работы должен предусматривать такой вариант. (У меня, например приостанавливалась подкачка, пока не разгрузится память)
А задачи, где динамическое выделение памяти целесообразно есть. Сейчас я одну такую решаю. На первом этапе буду работать с статическим распределением. Потом прикручу динамическое.

А зачем? Или вы про вызов конструкторов классов для буфера?
Но что мешает явно его вызвать:
char buf[N];
new (buf) ClassName(...);
ClassName *p = (ClassName *)buf;
...

Ну так этот «С-шный каст» ничем не лучше reinterpret_cast<>

Впрочем, тут без кастов можно и нужно. Раз уж placement new используется, его надо и использовать правильно:

p.s. ещё тут

Касты с char не прокатят, char buf[ sizeof(ClassName) ]; тоже по ходу не прокатит, выравнивание должно быть до 4(а то и до 8) байт.
Ну эт такое, можно хоть long long buf[ (sizeof(ClassName)+7)/8]; втулить.


кроме placement new ничего дельного не увидел там, 10 страниц гвн
Только смысл в placement new есть только,если нужно делать отложенную инициализацию, чтобы код не пестрел всякими init()`ами.


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


Ну делать дефрагментацию кучи без MMU - это гемор жуткий: сложные указатели, сложные алгоритмы, куча багов, куча тормозов, да еще и не всегда реализуемо, тк проц может хранить адрес некоторое время у себя внутри(на пример, инструкции ldm/stm, интерруптабельные, к стати) - как мы тогда ему скажем, что адрес изменился? А если есть MMU и страничная адрессация, то и дефраг. особо не нужен, имхо