Проще говоря вы используете malloc и т.п. из библиотеки или свои? Я вот FreeRTOS изучаю. Решил досконально изучить исходники (heap_2). Честно говоря это треш какой то. Конечно как кому, но для меня такой стиль писания... Все эти x,px и и т.д. километровые имена. Принцип бритвы Оккамы походу не известен разработчикам. Пока всю эту дибилистику не убрал постоянно терялся на середине алгоритма. Как там, мозг не может запомнить одновременно более 7 переменных величин. Но да ладно не об этом. Вобщем мне не понравилась такая реализация - нету дефрагментации кучи. Взял стандартные библиотечные (KEIL RVDS). Но их тоже оказывается 2 реализации http://www.keil.com/support/man/docs/armli...ib_Cihfiabf.htm
Как они толком работают, не поймешь - исходников я не нашёл.
Вобщем кто какой реализацией пользуется? Может кто исходниками поделится. Камень Cortex.

Пользуемся tlsf, пока всем устраивает.

Имени zltigo. И на Cortex и на ARM7

Блин, нашёл тему близнец тыц Можно склеить.

Склеил бы, да руки не достают. Тем более, что здесь часто возникают такие вопросы. Пусть остаётся.

Вот и моя близняшка http://electronix.ru/forum/index.php?showtopic=103157
Юзаю простой best-fit аллокатор с ограничением на минимальный свободный блок, правда не в тех задачах, что в той теме описаны.
Применяется для хранения сообщений для передачи между потоками...
Типа в одном потоке создаем обьект в куче, кидаем указатель на него в FIFO, другие потоки выгребают эти обьекты, выполняют соответствующие методы, возможно передают их дальше другим потокам(в том числе и родителю обратно) и подостижении состояния "final" обьект удаляется(это может произойти в любом потоке). Размер обьектов разный, тип разный. FIFO один. Лучшей реализации,чем использовать кучу пока не придумал.

shmur, про tlsf можно по подробнее, мож где-то толковое описание метода есть или алго? где-то краем глаза читал про него в брошюрке, но так и не понял,инфы мало было.

Я тут немного поразмыслил и пришел к выводу что дефрагментация кучи это практически невыполнимая задача без костылей. Вначале я быстро прикинул алгоритм примерно такой. При выделении памяти в начале кучи выделяется собственно память а с конца (например, можно и в начале) выделяется указатели на понтеры, которые собственно и "получат память". Тогда выделение памяти будет выглядеть не так:
byte *p = alloc(100);
а так
byte *p;
alloc(&p,100);
if(p!=NULL)...
Делается это для того, что бы сохранить адрес понтера, и при дефрагментации кучи мы могли бы занести туда новое значение адреса.
Но поразмыслив я понял что это накладывает кучу ограничений.
Нельзя использовать:
byte *pp,*p = alloc(100);
pp = p;
или
p += x; т.е. изменять адрес
Придётся использовать функции которые грамотно копировали бы поинтеры.
Использовать **p тоже не хочется, усложнение на пустом месте.
Есть ли простой способ, без костылей, дефрагментировать кучу?

Простых способов нет.
Дефрагментация неизбежно требует, чтобы программа была готова к тому, что выделенные куски памяти могут переместиться (то есть после перемещения должны обновиться указатели). Кроме того, должен быть некий механизм запирания, чтобы дефрагментатор не стал двигать кусок памяти, с которым ещё не закончена работа (есть активный указатель).

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

Проще наложить одно единственное обязательство - не использовать кучу.

Забудьте про дефраг. Дефрагментация уместна только, если есть страничная адресация(у кортексов-м3 нету), и то не нужна она там обычно.
Если уж других вариантов решить задачу нету - купите проц с внешней шиной и нацепите срам сверху. такие делает STm, на пример.

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

Я уже писал про **p. Придётся везде лепить. А потом начнётся ***p и т. д.

Практическая реализация дефрагментации без аппаратной поддержки вполне возможна. Это использовалось в Windows старых версий, в том числе на процессоре 8086.
См. функцию GlobalAlloc с флагом GMEM_MOVEABLE. А также функции GlobalLock, GlobalUnlock, GlobalFree, GlobalReAlloc.
Идея такая. Выделил с помощью GlobalAlloc с флагом GMEM_MOVEABLE кусок памяти - и получил не указатель а дескритор, значение типа HGLOBAL.
Нужно попользоваться - закрепил по дескриптору блок с помощью GlobalLock и получил при этом указатель, залез в блок, и отпустил его GlobalUnlock. Ранее полученный указатель стал недействительным. Когда блок отпущен он можен быть сдвинут. Чтобы ещё раз добраться до блока нужно ещё раз вызвать GlobalLock.

Я так понимаю это компромис. Зарезервировал память. Хочеш попользоваться -получай поинт, пользуйся. Не пользуешся разлочивай. Данные при этом не пропадают, но могут переместится. Отсюда два минуса - надо постоянно получать поинты и лочить/разлочить. Пока все не разлочат кучу, её не дефрагментируешь. Как по мне костыль номер один достаточно геморойный. Ну и как эта система, себя оправдала?

Все ее могут и никогда не разлочить. Нужно пользоваться моментом.

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

Если дефрагментация выполняется в потоке с самым низким приоритетом (как и должно быть) - то откуда грабли?

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

В старых книгах по Windows писали что о-го-го. Но когда появились процессоры с аппаратной поддержкой страниц памяти (80386) то эту систему отменили.


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

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

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

А вот пример:


Если после генерации сообщения поток блокируется, (у меня лично таких случаев 100%) вплоть до момента обработки, вообще кучу использовать не надо. А всё, что не успевает обрабатываться продюсер/консюмером - вообще выносится за ось, поскольку ставит под сомнение перфоманс этой оси. Я имею ввиду - пытаюсь обходиться одним тредом.

Я не очень понимаю выражения "не использовать кучу". Тут 2 варианта, либо ты резервируешь память раз и навсегда, либо динамически выдаёш, забираеш. В первом варианти торетически память в большинстве случаев будет простаивать.

Забыли по вариант 3: объект, например, контент сообщения, создается как локальный, т.е. в стеке, а в очередь записывается указатель на него. Затем отправитель сообщения блокируется до обработки, по окончании обработки работа возобновляется, тело сообщения удаляется из стека при выходе из блока кода.

Ну тут я вижу потенциальную проблему. Допустим памяти 100 байт. Есть две задачи. Сообщение занимает 100 байт. Какой стек вы выделите каждой задаче? Правильно по 100 байт и того получается 200, уже не влазим. Если есть куча, то система работоспособна. Разумеется память используется по очереди.
Т.е. я хочу сказать что при использовании стека в качестве хранилища данных, мы должны зарезервировать его максимальный размер при старте. Т.е. это первый вариант.

к тому же перегруженные, а возможно и volatile - защищать это все дело надо будет в многопоточном приложении...


Ну да, было дело Вероятность схватить Deadlock резко возрастает и тормоза в том числе. в 21 веке никто так не делает...


а как себя оправдала Windows 3.1 16-bit? :D


Это убивает прелесть многопоточности и "естетственности" программы. весь смысл прогонки обьекта по нескольким потокам - избавится от гемора, избавится от локов, упростить программу. попишу немного букавок в качестве примера.
Есть GSM модуль, протокол CMUX - 2 канала GSM & GPRS. Каждий канал обрабатывается только своим потоком.
Допустим GSM опрашівает состояние модуля, что-то там куда-то логирует и принимает и отправляет SMS. В SMS приходят команды. Допустим, пришла команда загрузить какой-то файл s ftp://ftp.murzilka.ru/01.zip. GSM формирует обьект-сообщение и кидает в очередь. GPRS по мере готовности выгребает сообщение и выполняет. в конце кидает его обратно в очередь(вернее само сообщение себя кидает и меняет состояние, эт уже детали реализации иерархии классов) и занимается дальше своими делами.
GSM по мере готовности выгребает сообщение и выполняет(отправляет SMS с отчетом о загрузке файла).
Конечно, можно было лочить каналы(довольно медленные) и делать все действия на месте(не отходя от кассы), но в сложном приложении(в том,которое есть на самом деле, все гораздо сложнее) запаритесь потом и система будет простаивать.на пример, чтобы прочитать следующую смс(вообще не относящуюся к командам связанным с GPRS) или снять следующее состояние модема надо будет ждать, пока тормознутый GPRS что-то там обработает минут так 10-15:))


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

Deadlock - вряд ли. Так как GlobalLock не предоставляет блок в исключительное пользование одному процессу. Много процессов могут вызвать GlobalLock для одного и того же блока одновременно - и получат успешно в ответ один и тот же указатель. GlobalLock блокирует только перемещение блока при дефрагментации.

Вещь! была для своего времени. Впрочем эта система выделения памяти была действительно актуальна только до Windows 3.0 включительно, на процессоре 8086. Windows 3.1 на таком процессоре уже не могла работать.

легко: Поток 1 занял взял GlobalLock, ожидает сообщение от потока 2. Поток 2 готов давать сообщение, для этого ему надо выделить блок памяти. куча фрагментирована, блока памяти нужного размера нету,другие блоки тоже двигать нельзя. дедлок готов. Такое может произойти,если приложение выделяет память в "peaks"-режиме. допустим wait и GlobalLock в потоке 1 поменять нельзя просто так.

Во-втором случае будет простаивать как минимум в 2 раза большее кол-во памяти.
Все кучефилы почему-то забывают об элементарной вещи, которая сводит на нет все +-ы кучи в embedded:
если к примеру 2 потока используют периодически каких-то 2 блока памяти и зависимость во времени этих использований невозможно детерминировать и возможны моменты одновременного использования (т.е. - невозможно поместить эти 2 блока в union static), то они совершенно забывают, что если выделять эти блоки на куче, то тоже будут моменты одновременного использования, соответственно - объём памяти в куче должен быть равен не менее чем сумме размеров блоков (а в реальности - более из-за заголовков).
Поэтому в типичном эмбеддед-приложении где нет запускаемых пользователем задач (которым при нехватке памяти можно отказать в запуске) или если нет таких потоков, выполнение которых можно остановить без ущерба функционированию системе при нехватке памяти, использование кучи не приводит к уменьшению требований по памяти, а наоборот - увеличивает требования к памяти + приводит к проблемам фрагментации.
Поэтому обычное static-размещение + union для использований неперекрывающихся по времени, однозначно рулит.
Поймите-же эту простую мысль, кучефилы, и творения ваши станут чуть менее глючными!!!

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

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

в моей практике тоже такое часто, обычно весь рижим в итоге упакован в 1 класс(а внутри уже может быть куча обьектов, втч классов общих для разных режимов) и placement new.

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

практически да. только в моем случаи размер пула определяется на этапе компиляции U32 pool[MAX(sizeof(class1),sizeof(class2),...)/4];
И ни одно слово не простаивает. В случаи с кучей надо иметь запас

А как Вы это делаете? Я, поскольку так не умею, делаю это как часть инициализации: определяю макс. размер класса, выделяю пул из кучи, и уже его потом использую для placement new... Кривовато выглядит

Ну выше ж написано - pool[ MAX( ) ]
Т.е. цепочака макросов MAX с sizeof() классов, на этом форуме вроде уже не раз placement new обсуждался..
Можно и как-то так, чтобы длинные MAX не писать и условной компиляцией включать/выключать применение (не помню, писал ли раньше):

Спасибо, технично, уже включил в код.

Тогда уж красивее так вроде, зачем лишний макро?
И ручное выравнивание можно убрать и на 8-/16битных юзать вместо uint32_t соответствующій тип. Хотя, без разницы

Ага, щас.
Заменяем (так быстрее, чем union редактировать):

Получаем кучу в духе:

Да кто его знает...
Вот вдруг «захочется» на CM3 ровнять такие пулы на двойное слово, uint64_t.
А sizeof даст в байтах округлённое вверх до uint32_t.
И у какого-то класса будет их (uint32_t) нечётное количество.
И даст sizeof(отой_union)/sizeof(uint64_t) отбрасывание «лишнего» uint32_t и нехватку места в буфере.
Мне проще каждый раз вместо A/B написать (A+B-1)/B чем думать, где отсутствие округления вверх может вілезти боком.
Лишней памяти такая запись точно никогда не запросит, нехватки тоже гарантированно не будет, в отличие от A/B.