Как `free()` в C узнаёт, сколько памяти освобождать, если мы не передаём размер?
Когда вызываем
Откуда
В glibc malloc перед возвращаемым указателем обычно находится скрытый заголовок блока памяти (`malloc_chunk`). В нём хранится размер блока и служебные флаги аллокатора.
Три младших бита поля размера используются для флагов, поскольку размеры блоков выровнены.
Когда вызывается
Проверить доступный размер можно через GNU-специфичную функцию
Иногда
При этом функция показывает доступный размер блока, а не обязательно размер, который изначально запросила программа.
Интересный нюанс: стандарт C не определяет, как именно
И ещё:
Когда вызываем
malloc(1024), получаем указатель на выделенную память. Но при освобождении передаём только адрес:
void *ptr = malloc(1024);
free(ptr);
Откуда
free() знает, сколько байт нужно освободить?В glibc malloc перед возвращаемым указателем обычно находится скрытый заголовок блока памяти (`malloc_chunk`). В нём хранится размер блока и служебные флаги аллокатора.
Три младших бита поля размера используются для флагов, поскольку размеры блоков выровнены.
Когда вызывается
free(ptr), glibc по адресу указателя находит метаданные и определяет размер выделенного блока.Проверить доступный размер можно через GNU-специфичную функцию
malloc_usable_size():
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
int main(void) {
void *ptr = malloc(1024);
if (!ptr) return 1;
printf("Requested: 1024\n");
printf("Usable: %zu\n",
malloc_usable_size(ptr));
free(ptr);
return 0;
}
Иногда
malloc_usable_size() возвращает больше запрошенных 1024 байт. Это связано с выравниванием и внутренней организацией памяти.При этом функция показывает доступный размер блока, а не обязательно размер, который изначально запросила программа.
Интересный нюанс: стандарт C не определяет, как именно
malloc хранит размеры блоков. Другие аллокаторы могут использовать совершенно иную организацию метаданных.И ещё:
free() не обязательно сразу возвращает память операционной системе. Часто она остаётся у аллокатора для повторного использования.👍3🥰2❤🔥1
В ядре Linux есть поиск строки, который ускоряется за счёт пропуска символов
В
Допустим, ищем
Первое сравнение: последняя
Можно сдвинуть шаблон сразу на пять позиций. При меньшем сдвиге
Реализация ядра заранее строит две таблицы: для сдвига по несовпавшему символу и по уже совпавшему суффиксу. Затем выбирает больший из допустимых сдвигов.
Но у этой реализации есть ограничение: она может пропустить совпадение на границе двух блоков данных. Например, если один блок заканчивается на
Поэтому прямо в комментарии к исходнику для фильтрации и обнаружения вторжений рекомендуют KMP, который умеет находить такие совпадения.
Выбор алгоритма здесь зависит и от скорости, и от того, как данные поступают на обработку.
В
lib/ts_bm.c реализован алгоритм Бойера - Мура. Он сравнивает шаблон с текстом справа налево и при несовпадении может перескочить сразу через несколько позиций.Допустим, ищем
ERROR:
Текст: ABCDXERROR
Шаблон: ERROR
↑
Первое сравнение: последняя
R шаблона против X в тексте. Символа X в ERROR вообще нет.Можно сдвинуть шаблон сразу на пять позиций. При меньшем сдвиге
X всё ещё находился бы внутри проверяемого участка, поэтому совпадение невозможно.Реализация ядра заранее строит две таблицы: для сдвига по несовпавшему символу и по уже совпавшему суффиксу. Затем выбирает больший из допустимых сдвигов.
Но у этой реализации есть ограничение: она может пропустить совпадение на границе двух блоков данных. Например, если один блок заканчивается на
ERR, а следующий начинается с OR.Поэтому прямо в комментарии к исходнику для фильтрации и обнаружения вторжений рекомендуют KMP, который умеет находить такие совпадения.
Выбор алгоритма здесь зависит и от скорости, и от того, как данные поступают на обработку.
❤1👍1