В библиотеке кода реального времени выполнения Blackfin (Blackfin C/C++ run-time library) встроены 4 стандартные функции для управления кучей (heap): calloc, free, malloc и realloc. По умолчанию в приложении определена одна куча, так называемая куча по умолчанию (default heap), которая обслуживает все запросы на динамическое выделение блоков памяти, где не указана явно какая-то альтернативная куча. Куча по умолчанию определена в стандартном файле описания настроек линкера (linker description file, *.ldf) и заголовке реального времени выполнения (run-time header).

Если достаточно одной кучи по умолчанию, то для начала использования динамического выделения памяти не требуется никаких дополнительных действий - т. е. функции calloc, free, malloc и realloc доступны сразу после запуска приложения. Возможно потребуется только изменить параметры (например размер) системной кучи. Это делается в настройках проекта, раздел LDF Settings -> System Heap.

Может быть также определено любое количество дополнительных куч. Эти кучи будут обслуживать те запросы на выделение памяти, которые явно будут указывать конкретную кучу. К этим дополнительным кучам можно общаться через расширенные функции выделения памяти heap_calloc, heap_free, heap_malloc и heap_realloc. Также имеется дополнительная функция heap_space_unused, подробнее см. далее.

Использование нескольких куч позволяют программисту выбирать между памятью для блоков - либо использовать быструю, но дорогую память (SRAM, L1), либо использовать память помедленнее, но которой имеется достаточное количество (SDRAM, L3). Это особенно актуально для проектов VDK, активно где API активно используют системную кучу для создания потоков.

Ниже будет показано, как определять кучу, как работать с кучами, как использовать интерфейс кучи и как освобождать место в куче.

[Определение кучи]

Куча может быть определена либо на этапе сборки проекта приложения (link-time), либо во время его выполнения (runtime). В обоих случаях у кучи имеется 3 атрибута:

• Start (base) address. Базовый адрес кучи. Это самый малый из адресов памяти, который можно использовать для выделения блоков, т. е. начало кучи в адресном пространстве.
• Length. Размер кучи в байтах.
• User identifier (userid). Идентификатор пользователя: число >= 1.

Системная куча по умолчанию (default system heap), определенная link-time, всегда имеет userid 0.

В дополнение кучи снабжаются индексами. Это что-то типа userid, но отличие в том, что индекс назначается не пользователем, а системой. Все выделения (allocation) и освобождения (deallocation) блоков памяти используют именно индексы кучи, но не userid кучи. Значение userid кучи может быть преобразовано в её индекс путем вызова функции using _heap_lookup() (см. "Определение куч во время сборки (Link-Time)"). Будьте внимательны, чтобы гарантировать передать корректный идентификатор в каждую функцию.

[Определение куч во время сборки (Link-Time)]

Кучи, определяемые во время сборки (link-time), задаются в библиотечном файле heaptab.s (это файл имяпроекта_heaptab.s, который находится в папке Generated Files -> User Heap), и параметры начала кучи, размера и userid хранятся в нем как три 32-битных слова. Параметры куч находятся в таблице, которая называется _heap_table. Эта таблица должна содержать первой кучу по умолчанию (запись описания кучи с userid 0), и должна завершаться записью, в которой базовый адрес равен 0. Дополнительные кучи и их параметры редактируются в свойствах проекта, раздел LDF Settings -> User Heap.

Адреса, которые находятся в этой таблице, могут быть литеральными (указанными явно как числа), или они могут быть символами, которые распознаются линкером. Куча по умолчанию (default heap) использует символы, генерируемые линкером с помощью файла .ldf.

Таблица _heap_table должна быть размещена в памяти констант. Она используется для инициализации run-time структуры кучи ___heaps, когда осуществляется первый запрос к куче. Когда происходит выделение памяти из любой кучи, библиотека инициализирует структуру ___heaps, используя данные, находящиеся в таблице _heap_table, и устанавливает ___nheaps в количество доступных куч.

Поскольку функции выделения памяти используют индексы кучи вместо их userid, то кучи, настроенные таким образом, должны иметь userid, привязанные к индексам, перед их явным использованием:

int _heap_lookup(int userid);    // функция вернет индекс кучи

[Определение куч во время выполнения (Runtime)]

Кучи могут быть определены и инсталлированы во время выполнения кода программы (runtime) с помощью функции _heap_install():

int _heap_install(void *base, size_t length, int userid);

Эта функция может взять любую секцию памяти и начать использовать её как кучу. Функция вернет индекс кучи, которая была выделена как новая установленная куча, либо вернет отрицательное значение, если были обнаружены проблемы выделения кучи (см. "Советы для работы с кучами").

Причины, по которым _heap_install() может завершиться с ошибкой, следующие (но могут быть и другие, не перечисленные здесь причины):

• Уже существует куча, у которой задан указанный userid.
• Новая куча слишком мала для использования (указанный параметр длины length слишком мал).

[Советы для работы с кучами]

Кучи не могут начинаться с нулевого адреса (0x0000 0000). Этот адрес соответствует зарезервированному значению для указателя, и он означает "память не может быть выделена". Это так называемый null-указатель на платформе Blackfin (как впрочем, почти на всех других известных платформах).

Не вся память в куче доступна для пользователей. Для обслуживания кучи (heap housekeeping) в ней тратится 32 байта на кучу, и еще 12 байт на каждое выделение блока в куче (значения округлены, чтобы выделяемые блоки памяти были выровнены на 8 байт по начальному адресу). Таким образом, куча из 256 байт не может обслужить 4 выделения блока по 64 байта.

Память, затрачиваемая на обслуживание кучи, предшествует выделяемым блокам. Таким образом, если куча начинается с адреса 0x0800 0000, то этот адрес никогда не будет возвращен в программу пользователя как адрес начала запрошенного на выделение блока; первый запрос на выделение блока вернет некий адрес, который будет находиться внутри кучи, но он будет больше 0x0800 0000.

Базовый адрес кучи должен быть соответствующим образом выровнен так, чтобы он нацело делился на 8 (выравнивание на 8 байт). Это гарантирует возможность использования выделенных блоков для векторных операций [2].

Размеры куч (параметр length) должен нацело делиться на число, являющееся степенью двойки, чтобы использование памяти было более эффективным. Аллокатор кучи работает с такими размерами блоков, как 256, 512 или 1024 bytes.

Для совместимости C++ вызовы malloc и calloc с размером блока 0 выделят блок размером 1.

[Стандартный интерфейс кучи]

Стандартные функции calloc и malloc выделят новый объект (блок памяти) из кучи по умолчанию (default heap). Если realloc был вызван с null-указателем, то в результате также будет выделен новый объект из кучи по умолчанию.

Ранее выделенные объекты могут быть освобождены функциями free или realloc. Когда ранее выделенный объект меняет свой размер вызовом realloc, то возвращенный объект будет находиться в той же куче, что и исходный объект.

Функция space_unused вернет количество не выделенных блоков в куче с индексом 0. Имейте в виду, что Вы не сможете выделить все это пространство по той причине, что имеются потери на фрагментацию кучи и на обслуживание выделения блоков (heap housekeeping).

[Выделение STL-объектов C++ из кучи, не являющейся кучей по умолчанию]

Объекты C++ STL могут быть помещены в кучу не по умолчанию с использованием пользовательского аллокатора (custom allocator). Чтобы осуществить такое выделение, Вам сначала необходимо создать custom allocator. Ниже показан пример custom allocator, который Вы можете использовать как базу для своего собственного. Самая важная часть customalloc.h в большинстве случаев это функция выделения памяти, где память выделяется для STL-объекта. В настоящий момент подходящая строка кода назначает кучу по умолчанию (0):

Ty* ty = (Ty*) heap_malloc(0, n * sizeof(Ty));

Если просто поменяете первый параметр heap_malloc(), то Вы сможете выделять память из другой кучи:

• 0 соответствует default heap (куча по умолчанию).
• 1 это первая пользовательская куча.
• 2 это вторая пользовательская куча.
• ... и так далее.

Как только создали свой custom allocator, Вы должны проинформировать об этом используемый объект STL, чтобы он его использовал. Вот пример для стандартного определения списка ("list"):

list < int > a;

То же самое произойдет, если написать:

list < int, allocator < int > > a; 

Здесь "allocator" это аллокатор по умолчанию (default allocator). Таким образом, мы можем сказать списку "a" использовать пользовательский аллокатор следующим образом:

list < int, customallocator < int > > a;

Будучи созданным, список "a" может использоваться точно также, как и созданный обычным способом. Ниже во врезке показан пример использования пользовательского аллокатора (код example.cpp).

template < class Ty >
class customallocator {

public:
   typedef Ty value_type;
   typedef Ty* pointer;
   typedef Ty& reference;
   typedef const Ty* const_pointer;
   typedef const Ty& const_reference;
   
   typedef size_t size_type;
   typedef ptrdiff_t difference_type;
   
   template < class Other >
   struct rebind { typedef customallocator< Other > other; };
   pointer address(reference val) const { return &val; }
   const_pointer address(const_reference val)
      const { return &val; }
   customallocator(){}
   customallocator(const customallocator< Ty >&){}
   template < class Other >
   customallocator(const customallocator< Other >&) {}
   template < class Other >
   customallocator< Ty >& operator=(const customallocator&)
      { return (*this); }
   pointer allocate(size_type n, const void * = 0) {
      Ty* ty = (Ty*) heap_malloc(0, n * sizeof(Ty));
      cout << "Allocating 0x" << ty << endl;
      return ty;
   }
   void deallocate(void* p, size_type) {
      cout << "Deallocating 0x" << p << endl;
      if (p) free(p);
   }
   void construct(pointer p, const Ty& val)
      { new((void*)p)Ty(val); }
   void destroy(pointer p) { p->~Ty(); }
   size_type max_size() const { return size_t(-1); }
};

#include < iostream >

#include < list >

#include < customalloc.h > // подключение Вашего пользовательского аллокатора

using namespace std;

main(){
   cout << "creating list" << endl;
   // Создание списка с помощью custom allocator:
   list < int, customallocator< int > > a;
   cout.setf(ios_base::hex,ios_base::basefield);
   cout << "pushing some items on the back" << endl;
   a.push_back(0xaaaaaaaa); // проталкивание записи в список, как обычно
   a.push_back(0xbbbbbbbb);
   while(!a.empty()){
      // Чтение записи из списка обычным образом:
      cout << "popping:0x" << a.front() << endl;
      // Выталкивание записи из списка обычным образом:
      a.pop_front();
   }
   cout << "finished." << endl;
}

[Использование альтернативного интерфейса к куче]

Как уже упоминалось, библиотека C реального времени выполнения предоставляет несколько альтернативных функций для доступа к куче: heap_calloc, heap_free, heap_malloc и heap_realloc. Эти функции работают точно так же, как и традиционные стандартные, за исключением дополнительного аргумента, в котором указывается индекс используемой кучи.

Вот прототипы этих функций:

void *_heap_calloc(int idx, size_t nelem, size_t elsize);

void *_heap_free(int idx, void *);

void *_heap_malloc(int idx, size_t length);

void *_heap_realloc(int idx, void *, size_t length);

Имена реальных функций получили начальное подчеркивание перед именем функции, но заголовочный файл stdlib.h определяет макросы, которые задают имена для функций без этого подчеркивания.

Обратите внимание, что вызов

heap_realloc(idx, NULL, length);

эквивалентен

heap_realloc(idx, length);

Однако для вызова

heap_realloc(idx, ptr, length);

где ptr!=NULL, предоставленный параметр idx игнорируется; перераспределение памяти всегда осуществится в куче, в которой был выделен блок, на который указывает ptr, даже если для перемещения данных для кучи понадобится вызов memcpy.

Подобным образом, вызов

heap_free(idx, ptr);

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

Функция heap_space_unused (int idx) возвратит количество байт, которые остались не выделенными в куче с индексом idx. Если эта функция вернет -1, то куча с таким индексом не существует.

[Поддержка C++ для альтернативного интерфейса кучи]

Библиотека реального времени выполнения C++ (C++ run-time library) предоставляет поддержку для выделения и освобождения памяти из альтернативных куч через операторы new и delete.

Кучи должны быть инициализированы функциями C run-time, как это было описано ранее. Эти кучи могут затем использоваться через традиционный механизм new и delete путем простой передачи индекса кучи оператору new. Для оператора delete не нужно передавать индекс кучи, потому что для освобождения памяти эта информация не требуется.

Ниже показан пример, как это работает.

#include < heapnew >

char *alloc_string(int size, int heapidx)
{
   char *retVal = new(heapidx) char[size];
   return retVal;
}

void free_string(char *aString)
{
   delete aString;
}

[Освобождение места в памяти]

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

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

int _heap_init(int index);

В случае успеха функция _heap_init вернет 0, и если вызов потерпел неудачу, то будет возвращено ненулевое значение. Однако имейте в виду, что вызов все равно сделает недействительными все записи в куче, поэтому _heap_init использовать нельзя, если в куче имеются в наличии действующие выделения памяти.

[Как используется куча в приложениях VDK]

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

Традиционные функции для работы с кучами (calloc, free, malloc, realloc, heap_calloc, heap_free, heap_malloc, heap_realloc, new, delete) в приложениях VDK так же доступны. Однако необходимо помнить о том, что библиотеки API-функций VDK активно используют кучу по умолчанию для обслуживания потоков (system_heap). Когда поток создается, то память выделяется из системной кучи, поэтому при создании большого количества потоков системная куча может быстро переполниться (функции CreateThread, CreateThreadEx будут возвращать ошибку kThreadCreationFailure). Однако для экономии памяти системной кучи есть возможность настроить дополнительные, альтернативные кучи для потоков VDK.

Примечание: библиотечные функции VisualDSP могут занимать память системной кучи, и в документации нет информации по этому поводу. Например, функция стандартного ввода/вывода printf при первом использовании выделяет в системной куче область памяти размером 552 байта. Эта память не освобождается до завершения работы приложения, но последующие вызовы printf больше не выделяют дополнительную память.

Создание новой кучи VDK. Вы можете создать новую кучу в интерфейсе настройки ядра проекта VDK (закладка Kernel -> Heaps -> выберите в контекстном меню New Heap). После этого укажите для созданной кучи идентификатор пользователя - произвольное число, которое потом может использоваться для вызовов функций heap_calloc, heap_free, heap_malloc, heap_realloc и операторов new.

После того, как куча создана, она может быть использована для потока любого типа - в свойствах типа потока можно выбрать кучу из выпадающих списков Thread Structure Heap и Stack Heap. Однако имейте в виду, что новая куча будет работать только после того, как она была инициализирована должным образом.

Когда Вы настраиваете кучу для VDK, то этим не заменяете кучу, которую используют традиционные вызовы malloc. Вы просто создаете идентификатор для кучи, и эту кучу потом можно указать как кучу для структуры стека потока (Thread Structure Heap) и самого стека (Stack Heap), см. скриншоты ниже.

[Ссылки]

1. VisualDSP++ 5.0 C/C++ Compiler and Library Manual for Blackfin® Processors site:analog.com.
2. Blackfin: система команд (ассемблер) - часть 2.
3. VDK: пулы памяти.
4. VisualDSP: поиск утечки памяти в приложении.
5. Как устроена куча Blackfin.