Кто какую реализацию использует для распределения памяти на cortex? Опции

[Beginning]

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

[shmur]

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

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

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

[Beginning]

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

[IgorKossak]

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

[brag]

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

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

[Beginning]

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

[scifi]

Есть ли простой способ, без костылей, дефрагментировать кучу?

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

[Beginning]

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

[jcxz]

Картина собственно ясна. А теперь вопрос. Стоит ли ради дефрагментации накладывать на программу кучу обязательств

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

[brag]

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

[_Pasha]

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

[Beginning]

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

[maksimp]

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

[Beginning]

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

[aaarrr]

Пока все не разлочат кучу, её не дефрагментируешь.

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

[Beginning]

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

[_Pasha]

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

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

[Beginning]

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

[maksimp]

Зарезервировал память. Хочеш попользоваться -получай поинт, пользуйся. Не пользуешся разлочивай. .... Ну и как эта система, себя оправдала?

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

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

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

[_Pasha]

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

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

[Beginning]

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

[_Pasha]

Программа должна быть максимально естественна (проста) с точки зрения кода.

А вот пример:

Применяется для хранения сообщений для передачи между потоками...
Типа в одном потоке создаем обьект в куче, кидаем указатель на него в FIFO, другие потоки выгребают эти обьекты, выполняют соответствующие методы, возможно передают их дальше другим потокам(в том числе и родителю обратно) и подостижении состояния "final" обьект удаляется(это может произойти в любом потоке). Размер обьектов разный, тип разный. FIFO один. Лучшей реализации,чем использовать кучу пока не придумал.

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

Сообщение отредактировал _Pasha - Jun 21 2012, 07:41

[Beginning]

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

[_Pasha]

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

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

[Beginning]

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

[brag]

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

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

GlobalUnlock. Ранее полученный указатель стал недействительным. Когда блок отпущен он можен быть сдвинут. Чтобы ещё раз добраться до блока нужно ещё раз вызвать GlobalLock.

Ну да, было дело Вероятность схватить 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 байт(+ оверхед на заголовки):

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

[maksimp]

GlobalUnlock. Ранее полученный указатель стал недействительным. Когда блок отпущен он можен быть сдвинут. Чтобы ещё раз добраться до блока нужно ещё раз вызвать GlobalLock.

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

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

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

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

[brag]

Deadlock - вряд ли.

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

[jcxz]

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

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

[brag]

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

[Axel]

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

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

[brag]

несколькими альтернативными режимами

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

[Axel]

...и placement new.

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

[brag]

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

[Axel]

...размер пула определяется на этапе компиляции...

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

[ReAl]

А как Вы это делаете?

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

Код

#define SIZE_IN(class, type)  ((sizeof(class)+sizeof(type)-1)/sizeof(type))

#define POOL_PLACE(class) uint8_t place_for_##class [ sizeof(class) ]

#include "A.h"

#ifdef MODE_B_USED
#   include "B.h"
#endif

#include "C.h"

union pool1_member_sizes
{
    POOL_PLACE(A);
#ifdef MODE_B_USED
    POOL_PLACE(B);
#endif
    POOL_PLACE(C);
};

// автоматически получаем MAX всех размеров
uint32_t pool1[ SIZE_IN(pool1_member_sizes,uint32_t) ];

[Axel]

Можно и как-то так...

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

[brag]

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

Код

#define SIZE_IN(class, type)  (sizeof(class)/sizeof(type))

#include "A.h"

#ifdef MODE_B_USED
#   include "B.h"
#endif

#include "C.h"

union pool1_member_sizes{
    А а;
#ifdef MODE_B_USED
    B b;
#endif
    C c;
};

// автоматически получаем MAX всех размеров
uint32_t pool1[ SIZE_IN(pool1_member_sizes,uint32_t) ];

[ReAl]

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

Код

#define POOL_PLACE(class) class a_##class

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

Код

pn.cpp:31: error: member ‘A pool1_member_sizes::a_A’ with constructor not allowed in union

И ручное выравнивание можно убрать и на 8-/16битных юзать вместо uint32_t соответствующій тип.

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