10.3.1 Куча

Выделение памяти

Библиотечными вызовами, использующимися для выделения/освобождения памяти в "куче", являются malloc, realloc, calloc и free. Основной функцией является malloc, и нам необходимо понять, как работает malloc на стандартном Linux, и почему она не может быть использована в uClinux.

malloc обеспечивает динамическое выделение памяти в "куче" в процессе работы. По существу, чтобы управлять размером адресного пространства процесса, она использует низкоуровневые системные вызовы sbrk() / brk(). sbrk() добавляет память в конец адресного пространства процесса, увеличивая тем самым размер. brk(), с другой стороны, можно задать произвольный размер в пространстве процесса. Они эффективно используются библиотечными вызовами malloc / free для выделения/освобождения памяти для приложений, соответственно. Пространство процесса в стандартном Linux является виртуальным адресным пространством и, следовательно, добавление большей памяти выполняется простой настройкой структур виртуальной памяти в ядре, которое обеспечивает необходимую связь с физическими адресами. Так что malloc просто увеличивает размер виртуальной памяти, а free уменьшает размер виртуальной памяти по мере необходимости. Например, рассмотрим приложение размером 64 K (включая размер bss) с начальным размером "кучи" равным 0. При этом используется от 0 до 64 К в виртуальной памяти (общий размер виртуальной памяти = 64 K + размер стека), как показано на Рисунке 10.6.

Рисунок 10.6 Выделение памяти в "куче".

Теперь предположим, что приложение делает вызов malloc(4096). Это увеличит размер виртуальной памяти до 68 K, как показано на Рисунке 10.6. Фактическая физическая память выделяется только на фактическое время использования в обработчике ошибки отсутствия страницы в памяти.

В uClinux нет виртуальной памяти, так что добавлять или изменять границы адресного пространства процесса невозможно. Поэтому пришлось обеспечивать альтернативные решения. Такое альтернативное решение должно позволить обходиться очень небольшими изменениями или вообще их отсутствием при переносе приложений на uClinux. Такие простые решения, как отсутствие в uClinux "кучи", предварительное выделение всей необходимой памяти с использованием статических массивов, предоставление "кучи" фиксированного размера, и так далее, исключены. Это потребует огромных усилий по переносу и даже реорганизацию большинства приложений, что не желательно.

В uClinux такое решение обеспечивается использованием общесистемного пула свободной памяти для выделения памяти в "куче" всеми процессами. Поскольку все процессы выделяют память в одном пуле, один процесс может забрать всю доступную память и в результате случится нехватка общесистемной памяти. Это системный недостаток любой конструкции без MMU.

Простейшая реализация malloc использует прямые вызовы mmap() / munmap(). Весь требуемый объём памяти  запрашивается непосредственно с помощью распределителя памяти ядра. Реализация приводится ниже.

▪Делаем системный вызов mmap(), чтобы получить память из пула памяти ядра
 
void * malloc(size_t size) {
 …
 result = mmap((void *) 0, size, PROT_READ | PROT_WRITE,
                MAP_SHARED | MAP_ANONYMOUS, 0, 0);
 if (result == MAP_FAILED)
   return 0;
 return(result);
}
 

▪Чтобы вернуть использованную память, вызываем munmap()

Проблемы такого подхода становятся очевидными из его реализации, показанной в Распечатке 10.3, поскольку вызов mmap связан с распределителем памяти ядра, kmalloc, чтобы получить свободную память. Возвращённая память сохраняется в  связном списке указателей для учёта. Учёт необходим для того, чтобы система могла отслеживать память, выделенную каждому процессу и, следовательно, они связаны с структурой процесса, так что она может быть освобождена, когда процесс заканчивает работу. Накладные расходы для структур данных tblock и rblock составляют 56 байт на одно выделение. Приложения, требующие небольших кусков через malloc, очевидно, зря потратят память.

Также, kmalloc возвращает куски памяти размером с округлением до степени 2, ограниченные максимальным размером 1 Мб. Например, запрос на выделение 1.5 К (1536) приведёт к потере 0.5 К (512), так как ближайшая доступная степень 2 только 2 К (2048). Таким образом, распределитель очень неэффективен и ограничен.

56-ти байтовые накладные расходы могут быть уменьшены, если сделать API malloc умнее. Например, можно либо делать групповые выделения, либо выделять большие куски, а затем управлять этими кусками с помощью меньших структур данных. Эта проблема была также решена в ядре 2.6 и структуры rblock и tblock были удалены. Вторая проблема требует переписать схему выделения памяти ядра. В ядре uClinux имеется модифицированный метод распределения памяти в ядре. Это помогает уменьшить накладные расходы при выделении памяти. Новая функция kmalloc использует степень 2-ки для запросов памяти размером до размера 1-ой страницы (например, 4 КБ или 4096 байт), а для размеров более 1-ой страницы он округляется до границы ближайшей страницы. Например, рассмотрим выделение 100 К с использованием стандартной kmalloc. Это приведёт к выделению 128 К и потере 28 К. Однако, используя новую kmalloc можно выделить точно 100 К.

uClibc предоставляет три различные реализации malloc. Перечислим преимущества и недостатки каждой из их.

▪malloc-simple [uClinux-dist/uClibc/libc/stdlib/malloc-simple]
 
malloc(size_t size) {
 …
 …
 result = mmap((void *) 0, size, PROT_READ | PROT_WRITE,
                MAP_SHARED | MAP_ANONYMOUS, -1, 0);
 
 if (result == MAP_FAILED)
   return 0;
 return(result);
}
 
Это простейшая форма malloc, используемая в uClinux. Это простая реализация в одну строчку с быстрыми и прямыми  выделениями. Недостатком является 56-ти байтовые накладные расходы, которая проявляются при использовании приложений, которые требуют большого числа выделений памяти малого размера.
 

▪malloc [uClinux-dist/uClibc/libc/stdlib/malloc]:
 
В этой реализации malloc имеет внутреннюю "кучу", выделенную в статической области. Функция malloc_from_heap(), основываясь на требуемом размере, принимает решение о выделении памяти из этой статической области или прибегает к mmap. В этом подходе запросы малого размера не имеют при распределении проблемы накладных расходов, так как выделение памяти происходит из внутренней "кучи". Реализация приведена в Распечатке 10.4.

▪malloc-standard [uClinux-dist/uClibc/libc/stdlib/malloc-standard]:
 
Это самая сложная из всех реализаций malloc и используемая в стандартном вызове libc. По существу, библиотека malloc поддерживает выделения памяти малого размера внутри себя с помощью кусочков разного размера. Если запрос на выделение укладывается в кусочек определённого размера, то кусочек удаляется из списка свободных и маркируется как использованный (пока он не будет освобождён или приложение не завершится). Если запрашиваемый размер выделения больше, чем имеющийся размер кусочка, или если все уже использованы, библиотека вызывает mmap, предоставляющий размер выделения больший, чем пороговый размер. Этот пороговый размер регулируется таким образом, чтобы минимизировать накладные расходы при выделении памяти через mmap. В противном случае для увеличения размера "кучи" процесса используется brk, и в случае неудачи он в конечном счёте возвращается к mmap. При таком подходе очень эффективно управляемые кусочки сокращают накладные расходы при выделении памяти, добавляемые mmap, но это решение доступно только на системах с MMU.

Фрагментация памяти

Количество доступной свободной памяти не гарантирует такое же количество выделенной памяти. Например, если система имеет 100 К свободной памяти, это не обязательно означает, что malloc(100K) будет успешным. Это происходит из-за проблемы, называемой фрагментацией памяти. Доступная память может быть не непрерывной и, следовательно, запрос на выделение может быть не выполнен. Выделение памяти в системе начинается только на границе страницы. Свободная страница запрашивается из списка доступной свободной памяти и добавляется в список используемой. Любой последующий запрос памяти, который помещается внутри оставшегося пространства, выполняет выделение памяти из той же страницы. И как только страница помечена как использованная, она может быть возвращена в системный список свободной памяти только тогда, когда все выделения памяти, использующие эту страницу, освободили память.

Например, предположим, что программа выполнила 16 256-ти байтовых выделений памяти. Предполагая накладные расходы в схеме выделения памяти равными нулю, это соответствует размеру одной страницы, в нашем случае 4 К = 16*256. Теперь до тех пор, пока приложение не освободит все 16 указателей, используемая страница не может быть освобождена. Таким образом, может быть ситуация, когда в системе есть достаточно памяти, но всё же её недостаточно для обслуживания текущего запроса на выделение.

Дефрагментация памяти

В стандартном Linux все приложения пользовательского пространства используют виртуальные адреса. Дефрагментация памяти проста, в том смысле, что необходимо изменить виртуальное отображения процесса, чтобы указать на новые места физического расположения. Даже если изменилось физическое местонахождение памяти, программы всё ещё используют виртуальный адрес и в состоянии нормально работать даже после перемещения. Без виртуальной памяти это становится невозможным.

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