- Выделяем память под структуры
- Что происходит с указателями при malloc
- Выделится ли память, если сделать malloc(0)
- Бинарное дерево. Динамическая память. Указатели на функции.
[yt]
[vk]
man 3 malloc
// Выделить size байт
void *malloc(size_t size);
// Освободить выделенную память
void free(void *ptr);
// Выделить память под nmemb элементов размером size байт.
// Память будет занулена
void *calloc(size_t nmemb, size_t size);
// Изменить размер памяти по указателю ptr. Можно уменьшить или увеличить. Возвращает новый указатель, так как данные могут быть перенесены в другую ячейку памяти.
void *realloc(void *ptr, size_t size);
// Изменить размер памяти по указателю ptr. Работает аналогично realloc,
// только принимает в себя новое количество элементов и размер одного элемента
// Безопаснее с точки зрения переполнения, потому что в случае переполнения nmemb*size вернет null
void *reallocarray(void *ptr, size_t nmemb, size_t size);
Во всех приведенных выше функциях нужно проверять, что возвращаемых указатель не NULL и что память действительно удалось выделить. В realloc нужно избегать конструкций вида
ptr = realloc(ptr, n);
Так как если память выделить не удалось, то в ptr будет лежать NULL и доступ к старой памяти мы потеряем.
Вольный перевод главы 7.1.3 книги The Linux Programming Interface Book by Michael Kerrisk
Обратите внимание, что в деталях имплементация malloc может отличаться, но идеи остаются те же
malloc() устроен достаточно просто. Внутри себя он поддерживает двусвязный список свободных блоков памяти.
При вызове malloc он проходится по этому списку и ищет блок, размер которого больше или равен запрошенному (при поиске могут использоваться разные стратегии, в зависимости от реализации, например, "первый найденный" или "наилучшее совпадение").
Если удалось найти блок нужного размера, то он возвращается вызывающей стороне. Если найденный блок больше, то он разбивается на две части, и вызывающей стороне возвращается блок нужного размера, а в спискок свободных блоков добавляется оставшийся кусок.
Если подходящий блок не удалось найти, то mallo делает системный вызов sbrk (man 2 sbrk). Однако, чтобы уменьшить общее количество системных вызовов, malloc запрашивает больше памяти у системы, чем просила вызывающая сторона. Лишнюю запрошенную память malloc также добавляет в список свободных блоков.
Как же тогда работает free? При вызове free ожидается, что он вернет соответствующий блок памяти обратно в список свободных блоков. Но как он узнает, какой размер блока? Для этого используется хитрость. Когда malloc выделяет блок, он дополнительно выделяет память под несколько байт, хранящих размер блока. Число с размером лежит в самом начале блока. Поэтому, когда malloc возвращает указатель, то он указывает на следующий элемент после размера блока.
+--------------+--------------------------+
| размер блока | память для использования |
+--------------+--------------------------+
^
|________ адрес, который возвращает malloc
Когда блок помещается в двусвязный список свободных блоков, то часть блока опять же используется для хранения дополнительной информации: указателя на следующий элемент списка и указатель на предыдущий.
+--------------+--------------------------+------------------------+-----------+
| размер блока | указатель на предыдущий | указатель на следующий | свободная |
| | свободный блок | свободный блок | память |
+--------------+--------------------------+------------------------+-----------+
| |
<----------------------+ +------------->
При этом в памяти аллоцированные блоки и свободоные могут быть перемешаны.
+--------------------------------------------+ +------------------------------------------...
| | |
| v |
+------------+------+--+---+-----------+----------+-----------+------------+------+--+---+-----------+----------+-----------+--...
| размер | | | | | размер |xxxxxxxxxxx| размер | | | | | размер |xxxxxxxxxxx| ...
| свободного | NULL | x | | занятого |xxxxxxxxxxx| свободного | x | x | | занятого |xxxxxxxxxxx| ...
| блока | | | | блока |xxxxxxxxxxx| блока | | | | | блока |xxxxxxxxxxx| ...
+------------+------+------+-----------+----------+-----------+------------+--+---+------+-----------+----------+-----------+--...
^ ^ ^ |
| | | |
| +-------------------------------------------------------------+---------+
+----- начало списка |
+----------------------------------------------------------...
- Нельзя 2 раза делать
free- это UB. - Можно делать
free(NULL). freeне меняет значение указателя наNULL. Нет способа проверить, освобождена ли память по указателю. Поэтому для удобства можно послеfree(ptr)делатьptr = NULL.- Между
mallocиcallocлучше выбиратьcalloc. Во-первых, есть шанс, что зануленная память нам достанется бесплатно (возьмутся оболасти памяти, которые уже занулены) и не надо будет делатьmemset. Во-вторых, при умноженииsize * amountвmallocможет произойти переполонение и мы об этом не узнаем. Тогда какcallocпринимает 2 аргумента и сам их перемножает и в случае переполнения не выделит память и мы об этом узнаем через возвращаемое значение. - При вызове *alloc функций для получения размера лучше делать
MyStruct* p = calloc(1, sizeof(*p))вместоMyStruct* p = calloc(1, sizeof(MyStruct))иMyStruct* p = calloc(1, 12). Потому что при изменении размера структуры или типа указателя, при таком подходе нужно будет менять меньше мест и труднее ошибиться.
Утечка памяти это серьезная проблема, которая может быть не сильно заметна во время занятий. Но в жизни, если программа работает долго, отвечает на много запросов и в ней есть утечка памяти, то рано или поздно память закончится и процесс умрет (например, его убьет OOM-killer).
Для того чтобы проверить программу на утечки памяти, можно воспользоваться утилитой valgrind.
Он покажет, сколько памяти было аллоцировано и сколько освобождено. А если скомпилировать бинарь
с отладочными символами (с флагом -g), то valgrind покажет еще и строчку, где была выделена память,
которую потом не освободили.
valgrind --leak-check=full ./a.out
Мы уже знаем, что системные вызовы делать долго, поэтому существует множество механизмов, которые позволяют миинимизировать количество вызовов. Динамическая память выделяется операционной системой, поэтому, чтобы ее получить, необходимо сделать системный вызов.
Какой?
man 3 malloc говорит следующее:
Normally, malloc() allocates memory from the heap, and adjusts the size of the heap as required, using sbrk(2). When allocating blocks of memory larger than
MMAP_THRESHOLD bytes, the glibc malloc() implementation allocates the memory as a private anonymous mapping using mmap(2). MMAP_THRESHOLD is 128 kB by default, but is
adjustable using mallopt(3).
Значит для небольших аллокаций используется sbrk, а для больших mmap. Посмотрим, как часто и какие аллокации будет делать наше дерево.
Если грубо, то у нас должно быть по 3 небольшие аллокации на каждую ноду: строка и 2 ребенка.
Посмотреть, как работает brk/sbrk можно в man 2 brk.
Посмотрим, сколько раз вызовется brk в дереве. Положим 100 случайных чисел в
дерево и в strace посмотрим, сколько раз был сделан системный вызов brk.
for i in `seq 100`; do echo $RANDOM; done | strace ./a.out 2>&1 | grep brk
Результат:
brk(NULL) = 0x5584a3c4d000
brk(NULL) = 0x5584a3c4d000
brk(0x5584a3c6e000) = 0x5584a3c6e000
При этом 2 раза вызывается с аргументом NULL (это делается для того, чтобы
узнать адрес начала кучи (системный вызов brk в отличие от обертки из glibc
возвращает адрес конца кучи после увеличения), поэтому передавая в него NULL можно узнать адрес начала.
Заметим, что количество вызовов отличается от грубой оценки 3 * 100.
Таким образом как раз malloc и минимизирует количество системных вызовов:
сразу запрашивает больше памяти, чем нужно, чтобы при следующих аллокациях
не обращаться к операционной системе, а использовать уже выделенную память.
Попробуем увеличить количество элементов в дереве:
for i in `seq 10000`; do echo $RANDOM; done | strace ./a.out 2>&1 | grep brk
Результат:
brk(NULL) = 0x55a81e0cf000
brk(NULL) = 0x55a81e0cf000
brk(0x55a81e0f0000) = 0x55a81e0f0000
brk(0x55a81e111000) = 0x55a81e111000
brk(0x55a81e132000) = 0x55a81e132000
Увеличим еще:
for i in `seq 10000`; do echo $RANDOM; done | strace ./a.out 2>&1 | grep brk
Результат:
brk(NULL) = 0x55d519fdf000
brk(NULL) = 0x55d519fdf000
brk(0x55d51a000000) = 0x55d51a000000
brk(0x55d51a021000) = 0x55d51a021000
brk(0x55d51a042000) = 0x55d51a042000
brk(0x55d51a063000) = 0x55d51a063000
brk(0x55d51a084000) = 0x55d51a084000
brk(0x55d51a0a5000) = 0x55d51a0a5000
brk(0x55d51a0c6000) = 0x55d51a0c6000
brk(0x55d51a0e7000) = 0x55d51a0e7000
brk(0x55d51a108000) = 0x55d51a108000
brk(0x55d51a129000) = 0x55d51a129000
brk(0x55d51a14a000) = 0x55d51a14a000
brk(0x55d51a16b000) = 0x55d51a16b000
brk(0x55d51a18c000) = 0x55d51a18c000
brk(0x55d51a1ad000) = 0x55d51a1ad000
brk(0x55d51a1ce000) = 0x55d51a1ce000
brk(0x55d51a1ef000) = 0x55d51a1ef000
brk(0x55d51a210000) = 0x55d51a210000
brk(0x55d51a231000) = 0x55d51a231000
brk(0x55d51a252000) = 0x55d51a252000
brk(0x55d51a273000) = 0x55d51a273000
brk(0x55d51a294000) = 0x55d51a294000
brk(0x55d51a2b5000) = 0x55d51a2b5000
brk(0x55d51a2d6000) = 0x55d51a2d6000
brk(0x55d51a2f7000) = 0x55d51a2f7000
Попробуем теперь сделать следующее. Будем создавать не одно большое дерево, а много маленьких. Для этого добавим в код удаление дерева при достижении им размера 1000.
Добавим к код:
if (counter % 1000 == 0) {
delete(tree);
tree = NULL;
}
В таком случае количество вызовов уже куда меньше:
brk(NULL) = 0x55b28d901000
brk(NULL) = 0x55b28d901000
brk(0x55b28d922000) = 0x55b28d922000
brk(0x55b28d943000) = 0x55b28d943000
brk(0x55b28d964000) = 0x55b28d964000
Таким образом мы можем видеть еще одну особенность работы malloc: он может
переиспользовать память, которая уже была освобождена. Как мы видим,
адреса, с которыми вызывался brk не уменьшались, а значит память при удалении
дерева не возвращалась операциоонной системе, и malloc мог ее переиспользоовать
для построения других деревьев.
В файлике malloc_zero есть код, который запускает malloc(0) в бесконечном цикле.
Что может произойти?
Вообще есть 2 варианта:
- malloc может просто вернуть
NULL, при этом мы даже безопасно сможем сделатьfree(null)после этого - malloc выделит все-таки 0 байт памяти, при этом создат для себя блок памяти размером 0, но содержащий служебную информацию, к примеру размер блока.
Результат зависит от имплементации, но вероятнее всего будет 2 вариант.
В таком случае память для пользователя не выделится, но в реальности она выделится под служебную секцию. И если запустить код из примера, то рано или поздно на компьютере просто закончится память.
При этом приведенный код можно относительно безопасно запустить. Потому что в случае, когда память кончается, то процесс, агрессивно потребляющий память, просто убивают.
Но кто?
Специальный процесс, который для каждого процесса ведет счетчик, называемый oom_score.
Этот score считается достаточно сложно, но идея его в том, что чем больше значение, тем более агрессивно соответствующий процесс потребляет память и тем выше шанс, что при нехватке памяти убьют именно этот процесс.
Чтобы посмотреть oom_score для заданного процесса с заданным pid надо выполнить cat /proc/<pid>/oom_score.
Чтобы постоянно следить за oom_score можно выполнить
watch -n1 cat /proc/<pid>/oom_score
В таком случае команда будет выполняться раз в секунду и ее результат будет выводиться.
Как только памяти станет слишком мало, то OOM killer остановит процесс с наибольшим oom_score.
Узнать, был ли процесс убит в результате работы OOM killer можно, посмотрев в лог: dmesg -T и поискав там pid процесса.