Многие чипы AVR, для которых можно скомпилировать программу с использованием avr-libc (AVR GCC, WinAVR), имеют в наличии очень малое количество RAM. Самый маленький микроконтроллер, который может поддержать окружение языка C, имеет только 128 байт RAM. Эту память нужно как-то совместно использовать для инициализированных и неинициализированных переменных (секции .data и .bss [2]), для механизма динамического выделения памяти (dynamic memory allocator, вызовы malloc) и для стека, который используется для вызова подпрограмм и хранения локальных (local, automatic) переменных. 

Кроме того, в отличие от более крупных архитектур (наподобие ARM и x86), здесь нет аппаратной поддержки управления памятью (hardware-supported memory management), которая помогла бы в разделении упомянутых регионов памяти от того, чтобы они случайно не перезаписали друг друга. 

Стандартная карта памяти ОЗУ (RAM layout) должна разместить первыми переменные секции .data, от начала внутреннего RAM, и затем переменные секции .bss. Стек начинается от верхней границы внутреннего RAM, и растет к младшим адресам. Так называемая "куча" ("heap"), доступная для динамически выделяемой памяти, будет размещена за концом секции .bss. Таким образом нет риска, что динамическая память будет мешать переменным RAM (за исключением случая ошибочной реализации dynamic memory allocator). Однако все еще есть риск, что heap и стек пересекутся и затрут друг друга, если в программе будет задействовано слишком много места под динамическую память или под стек. Такое может даже произойти, если выделения памяти были не большие, но создали со временем фрагментацию памяти, поскольку новые выделения блоков памяти перестали помещаться в "дырки" от ранее освобожденных областей. Большие требования к стеку могут происходить в функции C, которая содержит большие локальные переменные или большое количество локальных переменных, или если функции с локальными переменными вызываются рекурсивно.

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

Карта выделения памяти при использовании внутреннего RAM.

Пояснение к рисунку: здесь on-board RAM память, встроенная в ядро микроконтроллера AVR, external RAM внешнее ОЗУ.

На простом CPU наподобие микроконтроллера сложно реализовать dynamic memory allocator, который будет простым (из-за дефицита кода памяти программ), но в то же время будет достаточно мощным, чтобы избежать нежелательной фрагментации памяти, и чтобы он выполнял работу за малое количество тактов CPU. У микроконтроллеров в настоящее время часто весьма ограничена память, и они работают на гораздо меньших частотах, чем обычные компьютеры PC.

Реализованный в avr-libc memory allocator пытается справиться со всеми этими ограничениями платформы AVR, и предлагает для своей настройки некоторые опции. Они могут использоваться, если имеется больше доступных ресурсов, чем в конфигурации по умолчанию.

[Внутреннее ОЗУ по сравнению с внешним (Internal vs. external RAM)]

Очевидно, что ограничения труднее всего преодолеть в конфигурации по умолчанию, где доступно только внутреннее ОЗУ (internal RAM). Особенное внимание нужно уделить устранению коллизии stack-heap, для чего нужно убедиться, что функции не вызываются друг из друга слишком глубоко (при этом растет стек в сторону младших адресов), и что не слишком много выделяется места в стеке под локальные переменные, также как нужно быть осторожным с распределением слишком большого количества динамической памяти.

Если имеется внешнее ОЗУ (external RAM), то очень рекомендуется перенести кучу (heap) во внешнюю память RAM, независимо от того, будут или нет секции .data и .bss также расположены во внешнем RAM. Стек должен всегда быть сохранен во внутреннем RAM. Некоторые микроконтроллеры даже требуют этого, и вообще к внутренней RAM можно получить доступ гораздо быстрее, так как не требуются дополнительные циклы ожидания для обращения к internal RAM (что очень важно для сохранения высокого быстродействия программы в целом). Когда динамическое выделение памяти, стек и куча разделены по различным областям памяти, то это самый безопасный способ избежать коллизии stack-heap.

[Настройки (опции) для malloc()]

Имеется некоторое количество переменных, которое можно настроить для адаптирования поведения malloc(), чтобы оно соответствовало ожидаемым требованиям и ограничениям приложения. Любые изменения в этих настройках должны быть сделаны перед самым первым вызовом malloc(). Имейте в виду, что некоторые библиотечные функции могут также использовать динамическую память (особенно из < stdio.h >: Standard IO facilities, стандартные возможности ввода/вывода), так что убедитесь, что изменения сделаны достаточно рано во всей последовательности запуска (startup sequence, которая происходит после сброса или включения питания).

Переменные __malloc_heap_start и __malloc_heap_end могут использоваться для ограничения функции malloc(), чтобы она работала в определенной области памяти. Эти переменные статически инициализируются для указания на начало кучи __heap_start и конец кучи __heap_end соответственно, where __heap_start заполняется линкером для указания области вне .bss, и __heap_end устанавливается в 0, чем подразумевается для malloc(), что куча находится ниже стека (стек расположен в более старших адресах, чем куча).

Если куча перенесена в external RAM, то __malloc_heap_end должна быть настроена соответствующим образом. Это можно сделать либо во время выполнения кода (run-time), путем записи значения в эту переменную, или это может быть реализовано автоматически во время линковки (link-time), путем настройки значения символа __heap_end.

Следующий пример показывает команду для линкера для перемещения всех сегментов .data и .bss, и кучи по адресу 0x1100 в external RAM. Куча будет расширена вверх до адреса 0xffff.

avr-gcc ... -Wl,--section-start,.data=0x801100,--defsym=__heap_end=0x80ffff ...

Примечание: "магическое" смещение 0x800000 адреса используется для того, чтобы указать AVR GCC на память SRAM в Гарвардской архитектуре AVR. См. также руководство gcc по использованию опций -Wl. Руководство ld (linker) указывает, что использование -Tdata=x является эквивалентом использования --section-start,.data=x. Однако Вы используете --section-start как в примере выше, потому что фронтэнд GCC также устанавливает опцию -Tdata для всех типов MCU, где SRAM не начинается с 0x800060. Таким образом, линкеру предъявляются две опции -Tdata options. Начиная с binutils 2.16 линкер изменил предпочтение и выбирает в этой ситуации "неправильную" опцию.

Карта выделения памяти, когда internal RAM используется только под стек, а external RAM используется под переменные и кучу.

Пояснения к рисунку: здесь on-board RAM память, встроенная в ядро микроконтроллера AVR, external RAM внешнее ОЗУ. Область stack обозначает занятое пространство под стек, variables переменные, heap кучу. SP (Stack Pointer) обозначает текущее место в internal RAM, на которое установлен указатель стека.

Если динамическая память должна быть размещена в external RAM при сохранении переменных в internal RAM, то должна использоваться командная строка для линковки наподобие следующей. Имейте в виду, что в целях демонстрации не было сделано смежным назначение различных областей, так что имеются "дырки" ниже и выше кучи в external RAM, которые остались полностью недоступными для обычных переменных или динамических выделений памяти (дырки показаны на картинке ниже бледно-желтым цветом).

avr-gcc ... -Wl,--defsym=__heap_start=0x802000,--defsym=__heap_end=0x803fff ...

Карта выделения памяти, когда internal RAM используется под переменные и стек, а external RAM под кучу.

Если переменная __malloc_heap_end равна 0, аллокатор пытается определить нижнюю границу стека, чтобы предотвратить коллизию stack-heap, когда расширяется действительный размер кучи, чтобы выделить больше динамической памяти. Он не будет пытаться выйти за границы текущего лимита стека, уменьшенного на __malloc_margin байт. Таким образом, все возможные фреймы стека обработчиков прерываний могут прерывать выполнение текущей функции, плюс все вложенные дальнейшие вызовы функции могут не потребовать увеличения пространства под стек, или есть риск столкнуться с сегментом данных.

Значение по умолчанию для __malloc_margin равно 32.

[Подробности реализации динамического выделения памяти]

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

Реализация поддерживает простой список свободных участков памяти (freelist), который составлен из блоков памяти, которые были возвращены в кучу предыдущими вызовами free(). Имейте в виду, что вся эта память считается уже успешно добавленной к куче, так что не делается проверок на коллизии stack-heap при переработке памяти из freelist.

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

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

Если в freelist ничего не найдено, то будет сделана попытка расширения кучи. В этом случае будут проверены __malloc_margin и __malloc_heap_end, чтобы куча не конфликтовала со стеком.

Если оставшаяся часть памяти недостаточна для удовлетворения запроса, то в вызывающую функцию вернется указатель NULL.

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

Вызов realloc() сначала определяет, будет ли расти или уменьшаться текущее выделение. При уменьшении выделения все просто: существующий кусок делится, и хвост области, которая больше не используется, передается стандартной функции free(), которая добавит его в freelist. При этом сначала делается проверка, достаточно ли хвост большой, чтобы содержать в себе данные, иначе realloc() просто ничего не сделает и вернет ту же самую оригинальную область.

Когда при realloc() выделяемая область увеличивается, то сначала проверяется, может ли быть расширено имеющееся выделение. Если это так, то будет возвращен оригинальный указатель без копирования данных. Как дополнительное действие (side-effect), эта проверка также запишет размер самого большого куска в freelist.

Если область памяти не может быть расширена в том же месте, но старый кусок находится в верхней части кучи, вышеупомянутый просмотр freelist не показал достаточно большого куска, чтобы удовлетворить новый запрос, делается попытка быстро расширить этот верхний кусок (и таким образом кучу), при этом нужно сделать копирование поверх имеющихся данных. Если в куче нет больше доступного места (такая же проверка, как и в malloc()), то весь запрос потерпит неудачу.

Иначе будет вызван malloc() с новым запрошенным размером блока, существующие данные будут скопированы из старого блока в новый, и будет вызван free() на старую область памяти.

[Ссылки]

1. Memory Areas and Using malloc() site:nongnu.org.
2. AVR GCC: секции памяти (что такое .text, .data, .bss, .noinit?).
3. alloca: динамическое выделение памяти в стеке.