Форум разработчиков электроники ELECTRONIX.ru > FreeRTOS Heap

FormatCft

Oct 7 2008, 07:08

Доброго времени суток!
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1. Есть ли у кого своя реализация Heap_x.c? А то, что то не хочется использовать реализации которые есть (то без чистки памяти, то без объединения свободных блоков).
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2. Еще вопрос по heap_3.c. Этот хип использует стандартный Си-шный хип или просто есть возможность его использовать?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

zltigo

Oct 7 2008, 07:36

Цитата(FormatCft @ Oct 7 2008, 09:08)

Есть ли у кого своя реализация Heap_x.c?

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

Цитата

Еще вопрос по heap_3.c. Этот хип использует стандартный Си-шный хип или просто есть возможность его использовать?

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

FormatCft

Oct 7 2008, 07:54

Цитата(zltigo @ Oct 7 2008, 13:36)

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

Ого! Значительные навороты! ! !
Можно у Вас попросить поделиться результатами Ваших трудов? Был бы очень благодарен!
Или хотябы подсказать в каком направлении двигаться.

Цитата(zltigo @ Oct 7 2008, 13:36)

К делу не относится, но еще были объединены блоки памяти под TCB и Stack.

Мне кажется, что относится

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

Цитата(zltigo @ Oct 7 2008, 13:36)

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

Понял. Т.е. есть смысл найти открытый нормально написанный или попыхтеть "немножко" и написать своё

sergeeff

Oct 7 2008, 07:55

В этом плане можно воспользоваться TLSF: Memory Allocator for Real-Time - http://rtportal.upv.es/rtmalloc/node/8. Испанская разработка. Компактная и быстрая.

FormatCft

Oct 7 2008, 08:08

Цитата(sergeeff @ Oct 7 2008, 13:55)

В этом плане можно воспользоваться TLSF: Memory Allocator for Real-Time - http://rtportal.upv.es/rtmalloc/node/8. Испанская разработка. Компактная и быстрая.

Спасибо за ссылку! ! !
Т.е. вы её как я понял используйте? Если используйте, то нет ли каких-нибудь багов или малопреятных мелочей?

Version 2.4.3 тестили?

zltigo

Oct 7 2008, 08:26

Цитата(FormatCft @ Oct 7 2008, 09:54)

Можно у Вас попросить поделиться результатами Ваших трудов? Был бы очень благодарен!

Я подумаю. Основная проблема не в "секретности" а некоторой заточенности под несколько отличающееся от стандартного окружение и желательную чистку и комментирование перед раздачей

Цитата

Мне кажется, что относится

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

Нет, прежде всего прямое сокращение TCB на указатель и косвенное на один MCB.

Цитата

Понял. Т.е. есть смысл найти открытый нормально написанный или попыхтеть "немножко" и написать своё

Да, так.

Цитата(sergeeff @ Oct 7 2008, 09:55)

Компактная и быстрая.

Ну несколько монументальна

. Но в качестве объекта для изучения безусловно годится.

FormatCft

Oct 7 2008, 08:38

Цитата(zltigo @ Oct 7 2008, 14:26)

Я подумаю. Основная проблема не в "секретности" а некоторой заточенности под несколько отличающееся от стандартного окружение и желательную чистку и комментирование перед раздачей

Спасибо! Буду с нетерпением ждать

Цитата(zltigo @ Oct 7 2008, 14:26)

Нет, прежде всего прямое сокращение TCB на указатель и косвенное на один MCB.

Ясно. Небольшая экономия места.

Цитата(zltigo @ Oct 7 2008, 14:26)

Ну несколько монументальна

. Но в качестве объекта для изучения безусловно годится.

Т.е. я так понял, что для МК-го применения не подходит из-за того, что слишком много времени кушает?

sergeeff

Oct 7 2008, 10:18

Цитата(FormatCft @ Oct 7 2008, 12:08)

Спасибо за ссылку! ! !
Т.е. вы её как я понял используйте? Если используйте, то нет ли каких-нибудь багов или малопреятных мелочей?

Version 2.4.3 тестили?

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

zltigo

Oct 7 2008, 10:31

Цитата(FormatCft @ Oct 7 2008, 10:38)

Т.е. я так понял, что для МК-го применения не подходит из-за того, что слишком много времени кушает?

Подходит. Время дело второе. Просто излишества есть, типа сервисных наворотов, realloc(),....

Terminator

Oct 7 2008, 10:58

Запустил в своём проекте heap_3
arm-elf-gcc + newlib небольшие правки syscalls.c, вообщем получилось как костыль. Пока работает.

FormatCft

Oct 7 2008, 13:45

Цитата(zltigo @ Oct 7 2008, 16:31)

Подходит. Время дело второе. Просто излишества есть, типа сервисных наворотов, realloc(),....

Понял. Сейчас только жду вашей версии!

Цитата(Terminator @ Oct 7 2008, 16:58)

Запустил в своём проекте heap_3
arm-elf-gcc + newlib небольшие правки syscalls.c, вообщем получилось как костыль. Пока работает.

Спасибо! Костыли мне еще рано )) Я думаю, что буду использовать что-то из 2х предложенных вариантов (скорее всего вариант ЗлтИго)

sergeeff

Oct 7 2008, 15:31

To zltigo:

А в чем уважаемый гуру вы усмотрели "монументальность" TLSF аллокатора? По моему ничего особо навороченного там нет, а блоки выделяются достаточно шустро, и довольно изящно частично решена задача дефрагментации освобождаемой памяти. Да и с самого начала разрабатывалась для embedded применений.
Я не агент команды, написавшей TLSF, просто интересно уяснить для себя про монументальность.

zltigo

Oct 7 2008, 15:46

Цитата(sergeeff @ Oct 7 2008, 17:31)

А в чем уважаемый гуру вы усмотрели "монументальность" TLSF аллокатора? По моему ничего особо навороченного там нет...

Ничего особо, естественно, нет, но некоторые излишества универсальности присутствуют.

FormatCft

Oct 7 2008, 16:12

опсотв ))

sergeeff

Oct 7 2008, 16:46

Цитата(zltigo @ Oct 7 2008, 19:46)

Ничего особо, естественно, нет, но некоторые излишества универсальности присутствуют.

Сразу пришла на ум легендарная фразы Вицина из "Кавказской пленницы" : "И излишества всякие, нехорошие ..."

FormatCft

Oct 17 2008, 19:14

Цитата(sergeeff @ Oct 7 2008, 16:18)

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

Подключил я этот алокатор. Вылетает в dabort_hamdler при входе в макрос EXTRACT_BLOCK_HDR(b, tlsf, fl, sl);
Использую CW.
Может уже разбирались с этой проблемой?

zltigo

Oct 17 2008, 21:29

Цитата(sergeeff @ Oct 7 2008, 18:46)

И излишества всякие, нехорошие ...

Думал просто oткомментировать немного и выложить heap manager для FreeRTOS, но получается, что сначала нужно описывать почему он сделан именно так

. Попробую:
1. Хотелось иметь возможность получения списков свободных и занятых блоков памяти во время консольной отладки.
2. Хотелось иметь признак для чего блок памяти используется системой (TCB/Stack, Очередь,...)
3. Хотелось иметь возможность знать какая задача породила тот или иной блок - самое простое, при запросе блока сохранять адрес TCB.
4. Обязательна возможность использовать с менеджером разрозненные блоки памяти в едином списке. И наоборот - использовать несколько независимо управляемых блоков памяти (например, если эти блоки памяти имеют разное назначение/свойства, или для ручной борьбы с дефрагментацией )
5. Особые навороты с для ускорения поиска свободных блоков типа "испанского варианта" не нужны, поскольку
- основная масса блоков памяти под задачи, очереди и прочее выделяется "навсегда" и естественно выделение начинается с них;
- относительно родной реализации FreeRTOS под задачу и очередь у меня выделяется по одному блоку памяти TCB+Stack и QCB+Queue вместо отдельных.
- в результате в реальности занимаются/освобождаются обычно 2-3-5-ну чуть больше блоков и найти подходящий по размеру проще и быстрее простым перебором из свободных.
6. Борьба с дефрагментацией:
- склеивание соседних свободных блоков в один;
- прежде всего поиск свободного блока равного размеру запрашиваемого - на самом деле достаточно не редкий вариант, особенно, если чуть приложить к этому усилия.

Как строим:
1. Один общий связанный список, или отдельные для свободных и занятых. Использую один общий. Решающая причина - простой механизм склейки свободных блоков. При этом недостатки такого подхода нивелирутся тем, что ввиду (п.5) дефрагментация только в хвосте списка и длинна списка для поиска свободного эффективно сокращается использованием всего одного дополнительного указателя на первый свободный блок в общем списке.
2. На MCB выделено достаточно много памяти - 16 байт. Для максимально кастрированного варианта типа родных heap_*.с и с ограничением на размеры выделяемого блока можно было и в 4 байта уложиться, но см. "хотелки". Без особого напряга можно было в 12 байт уложиться, но тем неменее исходя из того, что например, для ARM стека выравнивание на 8 байт надо.... Пусть будет на данный момент 16 байт.

Код

typedef union type_size {
    unsigned long size;
    struct {
    unsigned long xlen:24;
    unsigned long type:8;
    };
}type_size;

// Memory Control Block (MCB)
typedef struct heap_mcb
{
    struct heap_mcb *next;       // Указатель на следующий MCB
                                  // mcb.next  последнего MCM всегда указывает на
                                  // первый MCB.
    struct heap_mcb *prev;       // Указатель на предыдущий MCB.
                                // Для первого MCB этот указатель указывает
                                // сам на себя.
    union type_size ts;          // Размер блока памяти и тип блока

    void  *ow;        // ТСВ Владельца блока памяти
                                // Собственно контролируемый блок памяти расположен сразу за MCB
} heap_mcb;

// Структура-описатель HEAP (тип-структура t_heap)
typedef struct heap_t
{     // Указатель на начало heap (первый MCB)
    struct heap_mcb *start;
    // Указатель на первый свободный MCB
    struct heap_mcb *freem;
    // RAW размер HEAP
    unsigned long hsize;
} heap_t;

Осталось откомментировать и выложить исходники. Завтра...

zltigo

Oct 18 2008, 19:47

Оптимально-простой в соответствии с ранее изложенными принципами менеджер памяти.
Подгибать, немного по месту, естественно, надо.
Инициализация у меня, например, в одном из применений выглядит примерно так:

Код

#pragma segment="HEAP_RTOS"
#pragma segment="XXX_STACK"
void init_system_heap( int add_ram_id )
{
    system_heap.start = (heap_mcb *)(__segment_begin( "HEAP_RTOS"));
    system_heap.freem = (heap_mcb *)(__segment_begin( "HEAP_RTOS"));
    system_heap.hsize = (ulong)(__segment_begin( "XXX_STACK")) - (ulong)(__segment_begin( "HEAP_RTOS")) + 1;

    heapinit( &system_heap );
    if( add_ram_id == 2148 )              // LPC2148  USB Memory as General prupose RAM
              heapadd( &system_heap, (void *)0x7FD00000, 0x2000 );

}

Для стандартной FreeRTOS можно для начала обертки сделать

Код

#define pvPortMalloc( size ) malloc_z( &system_heap, (size), MARK_SYSTEM, NULL )
#define vPortFree( ptr ) free_z( &system_heap, (ptr) )

FormatCft

Oct 18 2008, 20:04

Спасибо! ! ! Щас будем прикручивать

Terminator

Nov 12 2008, 04:26

Прикрутил к FreeRTOS TLSF
~3kB RAM уходит на таблицу.
Не нашёл описания на кучу дефайнов в tlsf.c, походу минимальный выделяемый блок 128 байт.

Нажмите для просмотра прикрепленного файла

zltigo

Apr 17 2010, 13:06

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

Dron_Gus

Apr 21 2010, 07:41

Спасибо за исходники. Пошел подтачивать под ansi.

Alex B._

Apr 22 2010, 11:05

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

Код

    xptr = tptr->prev;
    if( ( xptr->next != tptr )||( mem_ptr < heap->start ) )
    {   xTaskResumeScheduler();
         return;
    }

на

Код

    xptr = tptr->prev;
    if ( ((xptr != tptr) && ( xptr->next != tptr )) || ( mem_ptr < (void*)heap->start ) )
    {
        xTaskResumeScheduler();
        return;
    }

zltigo

Apr 22 2010, 11:10

Цитата(Alex B._ @ Apr 22 2010, 13:20)

Первый выделенный блок не освобождается.

Типа да, это тоже были особенности использования в системе, которая имеет как минимум одну idle задачу, которая занимает минимум один блок.
Если это не так, то добавить этот код надо.

Alex B._

Apr 22 2010, 11:16

Цитата(zltigo @ Apr 22 2010, 15:25)

Типа да, это тоже были особенности использования в системе, которая имеет как минимум одну idle задачу, которая занимает минимум один блок.

Да это понятно. Спасибо за исходники.

wave48

Jul 15 2013, 07:06

Исходники аллокатора от zltigo оказались очень полезными. Их, правда, пришлось почти полностью переписать, но идея, положенная в основу самая правильная. В результате получилась heap, которая при размере в 15 килобайт устойчиво держится в системе FreeRTOS, lwip (полный) и FatFS.
Нажмите для просмотра прикрепленного файла

esaulenka

Jul 16 2013, 19:38

Раз уж подняли тему.
Модулей диагностики (хотя б печать занятых/свободных блоков) для штатных heap2/heap4 никто не делал? Вроде б очень нужная вещь для отладки, но найти я не смог.

Или все внешние прикручивают? Странно это...

wave48

Jul 17 2013, 06:29

Вот это и было одной из причин использовать собственный аллокатор. На моей плате хеапы из дистрибутива FReeRTOS увеличивали размер кучи после просмотра двух-трех страниц lwipa и чтения пары килобайт из конфигурационных файлов. Оказалось что они почти не следят за освободившимися блоками, не умеют их объединять. Системный malloc приводил к таким же результатам - ему требовался большой стек.

MiG-3

Dec 4 2014, 13:13

Добрый день, коллеги!
Хочется более точно понять как и откуда выделяется память во FreeRTOS и особенности функционирования отдельных выделяльщиков.
Проект в IARe, в конфигурации линковщика есть параметр "heap".
Так ли я понимаю, что при использовании heap_1.c, heap_2.c, heap_4.c для оси выделяется динамическая память размером "configTOTAL_HEAP_SIZE".

Вопрос 1. Откуда она выделяется? Т.е. "configTOTAL_HEAP_SIZE" это часть "heap" или "configTOTAL_HEAP_SIZE" - это память, забираемая плюсом к "heap"? Т.е. сколько мне остается на переменные проекта :-)

Вопрос 2. Для heap_3.c размер кучи - это "heap" линковщика?

Вопрос 3. В последних версиях FreeRTOS heap_4.c (heap_5.c) имеет все равно проблемы с фрагментацией?

Вопрос 4. Если память выделяется динамически на этапе старта - инита оси, стеков и пр., а в дальнейшем изменения задач, мутексов и динамически выделяемых данных не предвидится, то есть ли смысл париться альтернативным кодом аллокаторов?

Непомнящий Евгений

Dec 8 2014, 13:11

Цитата(MiG-3 @ Dec 4 2014, 17:13)

Так ли я понимаю, что при использовании heap_1.c, heap_2.c, heap_4.c для оси выделяется динамическая память размером "configTOTAL_HEAP_SIZE".

Не понял что значит "для оси выделяется динамическая память"? configTOTAL_HEAP_SIZE задает объем памяти, доступный через pvPortMalloc. Память с его помощью выделяет сама ОС, и он же может использоваться в пользовательском коде...

Цитата

Вопрос 1. Откуда она выделяется? Т.е. "configTOTAL_HEAP_SIZE" это часть "heap" или "configTOTAL_HEAP_SIZE" - это память, забираемая плюсом к "heap"? Т.е. сколько мне остается на переменные проекта :-)

Есть массив размера configTOTAL_HEAP_SIZE, из него память и выделяется.

Цитата

Вопрос 2. Для heap_3.c размер кучи - это "heap" линковщика?

Код

void *pvPortMalloc( size_t xWantedSize )
{
void *pvReturn;

    vTaskSuspendAll();
    {
        pvReturn = malloc( xWantedSize );
    }
    xTaskResumeAll();
    return pvReturn;
}

КО подсказывает, что да

Цитата

Вопрос 3. В последних версиях FreeRTOS heap_4.c (heap_5.c) имеет все равно проблемы с фрагментацией?

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

Цитата

Вопрос 4. Если память выделяется динамически на этапе старта - инита оси, стеков и пр., а в дальнейшем изменения задач, мутексов и динамически выделяемых данных не предвидится, то есть ли смысл париться альтернативным кодом аллокаторов?

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

MiG-3

Dec 10 2014, 10:29

Спасибо за ответ!

Цитата(Непомнящий Евгений @ Dec 8 2014, 16:11)

Не понял что значит "для оси выделяется динамическая память"? configTOTAL_HEAP_SIZE задает объем памяти, доступный через pvPortMalloc. Память с его помощью выделяет сама ОС, и он же может использоваться в пользовательском коде...

Есть массив размера configTOTAL_HEAP_SIZE, из него память и выделяется.

Да это-то понятно. Но вот откуда выделяется память вопрос был. Меня интересивало, где выделяется этот массив, размером configTOTAL_HEAP_SIZE. Он входит в размер heap, который указан в настройках линковщика или за пределами этого размера. Ну грубо говоря, если heap = 20000 байт, а configTOTAL_HEAP_SIZE = 10000 байт. Я занимаю в ОЗУ 20000байт или 30000байт.

Я тут попробовал - вроде получается, что куча ОСИ выделяется в общей куче.

Остальное ясно - спасибо.

Непомнящий Евгений

Dec 15 2014, 09:52

Цитата(MiG-3 @ Dec 10 2014, 13:29)

Да это-то понятно. Но вот откуда выделяется память вопрос был. Меня интересивало, где выделяется этот массив, размером configTOTAL_HEAP_SIZE. Он входит в размер heap, который указан в настройках линковщика или за пределами этого размера. Ну грубо говоря, если heap = 20000 байт, а configTOTAL_HEAP_SIZE = 10000 байт. Я занимаю в ОЗУ 20000байт или 30000байт.

Что такое heap? Сишная куча? Она к фриртос никакого отношения не имеет. Массив - обычный глобальный объект, память для него резервируется при линковке