06.5 Размещение типов в памяти

План лекции
Про модель памяти программы
Размещение в стековом кадре
Выравнивание
Связь выравниваний производного типа и его элементов
Выравнивающие байты
Динамическое распределение памяти
Стандартные функции языка Си malloc, free и др.
Doug Lea’s malloc
Накладные расходы, фрагментация
Виды ошибок и address sanitizer

Модель памяти программы

Модель памяти программы
Память программы
Куча
Стек вызовов потока T - 2
Стек вызовов потока T - 1
Стек вызовов потока 0
Цветные блоки – значения
Стрелки – «ссылки»

Модель памяти программы
Языки без указателей
Java, Python, C#, Haskel, Ocaml, etc.
Работа с памятью 100% автоматическая
Сборка мусора, безопасность – бесплатно
Скорость работы ▼
Расход памяти ▲
Языки с указателями
Pascal, C, C++, golang, etc.
Работа с памятью полуавтоматическая
Сами уничтожаем ненужные значения и правильно работаем с указателями
Скорость работы ▲
Расход памяти ▼

Модель памяти программы
Языки без указателей
Java, Python, C#, Haskel, Ocaml, etc.
Работа с памятью 100% автоматическая
Сборка мусора, безопасность – бесплатно
Скорость работы ▼
Расход памяти ▲
Языки с указателями
Pascal, C, C++, golang, etc.
Работа с памятью полуавтоматическая
Сами уничтожаем ненужные значения и правильно работаем с указателями
Скорость работы ▲
Расход памяти ▼

Модель памяти программы
Языки без указателей
Java, Python, C#, Haskel, Ocaml, etc.
Работа с памятью 100% автоматическая
Сборка мусора, безопасность – бесплатно
Скорость работы ▼
Расход памяти ▲
Языки с указателями
Pascal, C, C++, golang, etc.
Работа с памятью полуавтоматическая
Сами уничтожаем ненужные значения и правильно работаем с указателями
Скорость работы ▲
Расход памяти ▼

Модель памяти программы
Языки без указателей
Java, Python, C#, Haskel, Ocaml, etc.
Работа с памятью 100% автоматическая
Сборка мусора, безопасность – бесплатно
Скорость работы ▼
Расход памяти ▲
Языки с указателями
Pascal, C, C++, golang, etc.
Работа с памятью полуавтоматическая
Сами уничтожаем ненужные значения и правильно работаем с указателями
Скорость работы ▲
Расход памяти ▼

Модель памяти программы
Языки без указателей
Java, Python, C#, Haskel, Ocaml, etc.
Работа с памятью 100% автоматическая
Сборка мусора, безопасность – бесплатно
Скорость работы ▼
Расход памяти ▲
Языки с указателями
Pascal, C, C++, golang, etc.
Работа с памятью полуавтоматическая
Сами уничтожаем ненужные значения и правильно работаем с указателями
Скорость работы ▲
Расход памяти ▼

Модель памяти программы
Языки без указателей
Java, Python, C#, Haskel, Ocaml, etc.
Работа с памятью 100% автоматическая
Сборка мусора, безопасность – бесплатно
Скорость работы ▼
Расход памяти ▲
Языки с указателями
Pascal, C, C++, golang, etc.
Работа с памятью полуавтоматическая
Сами уничтожаем ненужные значения и правильно работаем с указателями
Скорость работы ▲
Расход памяти ▼

Модель памяти программы
Языки без указателей
Java, Python, C#, Haskel, Ocaml, etc.
Работа с памятью 100% автоматическая
Сборка мусора, безопасность – бесплатно
Скорость работы ▼
Расход памяти ▲
Языки с указателями
Pascal, C, C++, golang, etc.
Работа с памятью полуавтоматическая
Сами уничтожаем ненужные значения и правильно работаем с указателями
Скорость работы ▲
Расход памяти ▼

Размещение данных в стековом кадре
Компилятор размещает значения переменных в стековом кадре в соответствии со стандартом языка Си
Назначает переменным адреса для хранения
Генерирует код для доступа
Переменные располагаются в стековом кадре в порядке описания
Если описаны без static/extern
Возможно присутствие неиспользуемых байтов между значениями последовательно описанных переменных

Размещение данных в стековом кадре
Компилятор размещает значения переменных в стековом кадре в соответствии со стандартом языка Си
Назначает переменным адреса для хранения
Генерирует код для доступа
Переменные располагаются в стековом кадре в порядке описания
Если описаны без static/extern
Возможно присутствие неиспользуемых байтов между значениями последовательно описанных переменных

Размещение данных в стековом кадре
Компилятор размещает значения переменных в стековом кадре в соответствии со стандартом языка Си
Назначает переменным адреса для хранения
Переменные располагаются в стековом кадре в порядке описания
Если описаны без static/extern
Возможно присутствие неиспользуемых байтов между значениями последовательно описанных переменных

Размещение данных в стековом кадре
Компилятор размещает значения переменных в стековом кадре в соответствии со стандартом языка Си
Назначает переменным адреса для хранения
Переменные располагаются в стековом кадре в порядке описания
Если описаны без static/extern
Возможно присутствие неиспользуемых байтов между значениями последовательно описанных переменных

Размещение данных в стековом кадре
Компилятор размещает значения переменных в стековом кадре в соответствии со стандартом языка Си
Назначает переменным адреса для хранения
Переменные располагаются в стековом кадре в порядке описания
Если описаны без static/extern
Возможно присутствие неиспользуемых байтов между последовательно описанными переменными

Выравнивание
Значения типа Т должны храниться по адресам, кратным alignof(T) – выравниванию типа T
Оператор alignof появился в C99
У всех популярных компиляторов alignof(T) -- это небольшая степень 2
Доступ к значению типа T, хранящемуся по адресу, некратному alignof(T), – это undefined behavior
char array[4] = {0};
// undefined behavior,
// if alignof(char) %
// alignof(int) != 0
if (*(int*)array == 0) {
// ...
}

Выравнивание
Значения типа Т должны храниться по адресам, кратным alignof(T) – выравниванию типа T
Оператор alignof появился в C99
У всех популярных компиляторов alignof(T) -- это небольшая степень 2
Зависящая от Т
Доступ к значению типа T, хранящемуся по адресу, некратному alignof(T), – это undefined behavior
char array[4] = {0};
// undefined behavior,
// if alignof(char) %
// alignof(int) != 0
if (*(int*)array == 0) {
// ...
}

Выравнивание
Значения типа Т должны храниться по адресам, кратным alignof(T) – выравниванию типа T
Оператор alignof появился в C99
У всех популярных компиляторов alignof(T) -- это небольшая степень 2
Зависящая от Т
Доступ к значению типа T, хранящемуся по адресу, некратному alignof(T), – это undefined behavior
char array[4] = {0};
// undefined behavior,
// if alignof(char) %
// alignof(int) != 0
if (*(int*)array == 0) {
// ...
}

Выравнивание
Значения типа Т должны храниться по адресам, кратным alignof(T) – выравниванию типа T
Оператор alignof появился в C99
У всех популярных компиляторов alignof(T) -- это небольшая степень 2
Зависящая от Т
Доступ к значению типа T, хранящемуся по адресу, некратному alignof(T), – это undefined behavior
char array[4] = {0};
// undefined behavior,
// if alignof(char) %
// alignof(int) != 0
if (*(int*)array == 0) {
// ...
}

Выравнивание
Значения типа Т должны храниться по адресам, кратным alignof(T) – выравниванию типа T
Оператор alignof появился в C99
У всех популярных компиляторов alignof(T) -- это небольшая степень 2
Зависящая от Т
Доступ к значению типа T, хранящемуся по адресу, некратному alignof(T), – это undefined behavior
char array[4] = {0};
// undefined behavior,
// if alignof(char) %
// alignof(int) != 0
if (*(int*)array == 0) {
// ...
}

Выравнивание простых типов и указателей
Зависит от используемого компилятора (implementation specific)
До C99 alignof(T) можно узнать в документации по компилятору
alignof(T) определяется требованиями, которые предъявляются к адресам инструкциями процессора для чтения и записи в память данных размера sizeof(T)

Выравнивание простых типов и указателей
Зависит от используемого компилятора (implementation defined)
До C99 alignof(T) можно узнать в документации по компилятору
alignof(T) определяется требованиями, которые предъявляются к адресам инструкциями процессора для чтения и записи в память данных размера sizeof(T)

Выравнивание простых типов и указателей
Зависит от используемого компилятора (implementation defined)
До C99 alignof(T) можно узнать в документации по компилятору
alignof(T) определяется требованиями, которые предъявляют к адресам инструкции процессора для чтения и записи в память данных размера sizeof(T)

Как компилятор выравнивает производный тип

Как компилятор выравнивает производный тип
Пусть T – производный тип
Пусть T1, …, Tn – типы элементов T
Необходимо, чтобы alignof(T) было кратно наибольшему общему кратному всех alignof(Ti)
alignof(T) % НОК(alignof(T1), …, alignof(Tn)) == 0
Иначе некоторые элементы Т будут выровнены неправильно
Все популярные компиляторы используют max вместо НОК, т.к. у них все alignof(Ti) – это степени 2

Как компилятор выравнивает производный тип
Пусть T – производный тип
Пусть T1, …, Tn – типы элементов T
Необходимо, чтобы alignof(T) было кратно наибольшему общему кратному всех alignof(Ti)
alignof(T) % НОК(alignof(T1), …, alignof(Tn)) == 0
Иначе некоторые элементы Т будут выровнены неправильно
Все популярные компиляторы используют max вместо НОК, т.к. у них все alignof(Ti) – это степени 2

Как компилятор выравнивает производный тип
Пусть T – производный тип
Пусть T1, …, Tn – типы элементов T
Необходимо, чтобы alignof(T) было кратно наибольшему общему кратному всех alignof(Ti)
alignof(T) % НОК(alignof(T1), …, alignof(Tn)) == 0
Иначе некоторые элементы Т будут выровнены неправильно
Все популярные компиляторы используют max вместо НОК, т.к. у них все alignof(Ti) – это степени 2

Как компилятор выравнивает производный тип
Пусть T – производный тип
Пусть T1, …, Tn – типы элементов T
Необходимо, чтобы alignof(T) было кратно наибольшему общему кратному всех alignof(Ti)
alignof(T) % НОК(alignof(T1), …, alignof(Tn)) == 0
Иначе некоторые элементы Т могут быть выровнены неправильно
Все популярные компиляторы используют max вместо НОК, т.к. у них все alignof(Ti) – это степени 2

Как компилятор выравнивает производный тип
Пусть T – производный тип
Пусть T1, …, Tn – типы элементов T
Необходимо, чтобы alignof(T) было кратно наибольшему общему кратному всех alignof(Ti)
alignof(T) % НОК(alignof(T1), …, alignof(Tn)) == 0
Иначе некоторые элементы Т могут быть выровнены неправильно
Все популярные компиляторы используют max вместо НОК, т.к. у них все alignof(Ti) – это степени 2

Пример про выравнивание массива
T = int (*)[4] – массив из 4 int
Т1 = Т2 = Т3 = Т4 = int – типы элементов Т
Пусть alignof(int) == 4, но alignof(T) == 1 или 2
т.е. нарушена кратность выравниванию элемента
Тогда разрешалось бы разместить массив int a[4] так, что
(size_t)&a % 4 == 2
И доступ к элементам a[0] и a[2] приводил бы к undefined behavior

Пример про выравнивание массива
T = int (*)[4] – массив из 4 int
Т1 = Т2 = Т3 = Т4 = int – типы элементов Т
Пусть alignof(int) == 4, но alignof(T) == 1 или 2
т.е. нарушена кратность НОК(выравнивания элементов)
Тогда разрешалось бы разместить массив int a[4] так, что
(size_t)&a % 4 == 2
И доступ к элементам a[0] и a[2] приводил бы к undefined behavior

Пример про выравнивание массива
T = int (*)[4] – массив из 4 int
Т1 = Т2 = Т3 = Т4 = int – типы элементов Т
Пусть alignof(int) == 4, но alignof(T) == 1 или 2
т.е. нарушена кратность НОК(выравнивания элементов)
Тогда разрешалось бы разместить массив int a[4] так, что
(size_t)&a % 4 == 2
И доступ к элементам a[0] и a[2] приводил бы к undefined behavior

Пример про выравнивание массива
T = int (*)[4] – массив из 4 int
Т1 = Т2 = Т3 = Т4 = int – типы элементов Т
Пусть alignof(int) == 4, но alignof(T) == 1 или 2
т.е. нарушена кратность НОК(выравнивания элементов)
Тогда разрешалось бы разместить массив int a[4] так, что
(size_t)&a % 4 == 2
И доступ к элементам a[0] и a[2] приводил бы к undefined behavior

Пример с выравниванием struct
T = struct XY { int X; double Y; }
T1 = int, T2 = double
Пусть alignof(int) ≤ alignof(double) == 8, но alignof(T) == 1, 2 или 4
т.е. нарушена кратность НОК(выравнивания элементов)
Пусть a и b – переменные типа struct XY
При alignof(T) < 8 возможно (size_t)&a % 8 == A > 0, (size_t)&b % 8 == 0
При доступе к a.Y должно быть 0 == (size_t)&a.Y % 8 == ((size_t)&a + N) % 8 == (A + N) % 8
Иначе – undefined behavior
При доступе к b.Y должно быть 0 == (size_t)&b.Y % 8 == ((size_t)&b + N) % 8 == N % 8
Иначе – undefined behavior
Требование N % 8 == 0 противоречит (A + N) % 8 == 0, т.к. A > 0

Пример с выравниванием struct
T = struct XY { int X; double Y; }
T1 = int, T2 = double
Пусть alignof(int) ≤ alignof(double) == 8, но alignof(T) == 1, 2 или 4
т.е. нарушена кратность НОК(выравнивания элементов)
Пусть a и b – переменные типа struct XY
При alignof(T) < 8 возможно (size_t)&a % 8 == A > 0, (size_t)&b % 8 == 0
При доступе к a.Y должно быть 0 == (size_t)&a.Y % 8 == ((size_t)&a + N) % 8 == (A + N) % 8
Иначе – undefined behavior
При доступе к b.Y должно быть 0 == (size_t)&b.Y % 8 == ((size_t)&b + N) % 8 == N % 8
Иначе – undefined behavior
Требование N % 8 == 0 противоречит (A + N) % 8 == 0, т.к. A > 0

Пример с выравниванием struct
T = struct XY { int X; double Y; }
T1 = int, T2 = double
Пусть alignof(int) ≤ alignof(double) == 8, но alignof(T) == 1, 2 или 4
т.е. нарушена кратность НОК(выравнивания элементов)
Пусть a и b – переменные типа struct XY
При alignof(T) < 8 возможно (size_t)&a % 8 == A > 0, (size_t)&b % 8 == 0
При доступе к a.Y должно быть 0 == (size_t)&a.Y % 8 == ((size_t)&a + N) % 8 == (A + N) % 8
Иначе – undefined behavior
При доступе к b.Y должно быть 0 == (size_t)&b.Y % 8 == ((size_t)&b + N) % 8 == N % 8
Иначе – undefined behavior
Требование N % 8 == 0 противоречит (A + N) % 8 == 0, т.к. A > 0

Пример с выравниванием struct
T = struct XY { int X; double Y; }
T1 = int, T2 = double
Пусть alignof(int) ≤ alignof(double) == 8, но alignof(T) == 1, 2 или 4
т.е. нарушена кратность НОК(выравнивания элементов)
Пусть a и b – переменные типа struct XY
При alignof(T) < 8 возможно (size_t)&a % 8 == A > 0, (size_t)&b % 8 == 0
При доступе к a.Y должно быть 0 == (size_t)&a.Y % 8 == ((size_t)&a + N) % 8 == (A + N) % 8
Иначе – undefined behavior
При доступе к b.Y должно быть 0 == (size_t)&b.Y % 8 == ((size_t)&b + N) % 8 == N % 8
Иначе – undefined behavior
Требование N % 8 == 0 противоречит (A + N) % 8 == 0, т.к. A > 0

Пример с выравниванием struct
T = struct XY { int X; double Y; }
T1 = int, T2 = double
Пусть alignof(int) ≤ alignof(double) == 8, но alignof(T) == 1, 2 или 4
т.е. нарушена кратность НОК(выравнивания элементов)
Пусть a и b – переменные типа struct XY
При alignof(T) < 8 возможно (size_t)&a % 8 == A > 0, (size_t)&b % 8 == 0
При доступе к a.Y должно быть 0 == (size_t)&a.Y % 8 == ((size_t)&a + N) % 8 == (A + N) % 8
Иначе – undefined behavior
При доступе к b.Y должно быть 0 == (size_t)&b.Y % 8 == ((size_t)&b + N) % 8 == N % 8
Иначе – undefined behavior
Требование N % 8 == 0 противоречит (A + N) % 8 == 0, т.к. A > 0

Пример с выравниванием struct
T = struct XY { int X; double Y; }
T1 = int, T2 = double
Пусть alignof(int) ≤ alignof(double) == 8, но alignof(T) == 1, 2 или 4
т.е. нарушена кратность НОК(выравнивания элементов)
Пусть a и b – переменные типа struct XY
При alignof(T) < 8 возможно (size_t)&a % 8 == A > 0, (size_t)&b % 8 == 0
При доступе к a.Y должно быть 0 == (size_t)&a.Y % 8 == ((size_t)&a + N) % 8 == (A + N) % 8
Иначе – undefined behavior
При доступе к b.Y должно быть 0 == (size_t)&b.Y % 8 == ((size_t)&b + N) % 8 == N % 8
Иначе – undefined behavior
Требование N % 8 == 0 противоречит (A + N) % 8 == 0, т.к. A > 0

Пример с выравниванием struct
T = struct XY { int X; double Y; }
T1 = int, T2 = double
Пусть alignof(int) ≤ alignof(double) == 8, но alignof(T) == 1, 2 или 4
т.е. нарушена кратность НОК(выравнивания элементов)
Пусть a и b – переменные типа struct XY
При alignof(T) < 8 возможно (size_t)&a % 8 == A > 0, (size_t)&b % 8 == 0
При доступе к a.Y должно быть 0 == (size_t)&a.Y % 8 == ((size_t)&a + N) % 8 == (A + N) % 8
Иначе – undefined behavior
При доступе к b.Y должно быть 0 == (size_t)&b.Y % 8 == ((size_t)&b + N) % 8 == N % 8
Иначе – undefined behavior
Требование N % 8 == 0 противоречит (A + N) % 8 == 0, т.к. A > 0

Пример с выравниванием struct
T = struct XY { int X; double Y; }
T1 = int, T2 = double
Пусть alignof(int) ≤ alignof(double) == 8, но alignof(T) == 1, 2 или 4
т.е. нарушена кратность НОК(выравнивания элементов)
Пусть a и b – переменные типа struct XY
При alignof(T) < 8 возможно (size_t)&a % 8 == A > 0, (size_t)&b % 8 == 0
При доступе к a.Y должно быть 0 == (size_t)&a.Y % 8 == ((size_t)&a + N) % 8 == (A + N) % 8
Иначе – undefined behavior
При доступе к b.Y должно быть 0 == (size_t)&b.Y % 8 == ((size_t)&b + N) % 8 == N % 8
Иначе – undefined behavior
Требование N % 8 == 0 противоречит (A + N) % 8 == 0, т.к. A > 0

Пример с выравниванием struct
T = struct XY { int X; double Y; }
T1 = int, T2 = double
Пусть alignof(int) ≤ alignof(double) == 8, но alignof(T) == 1, 2 или 4
т.е. нарушена кратность НОК(выравнивания элементов)
Пусть a и b – переменные типа struct XY
При alignof(T) < 8 возможно (size_t)&a % 8 == A > 0, (size_t)&b % 8 == 0
При доступе к a.Y должно быть 0 == (size_t)&a.Y % 8 == ((size_t)&a + N) % 8 == (A + N) % 8
Иначе – undefined behavior
При доступе к b.Y должно быть 0 == (size_t)&b.Y % 8 == ((size_t)&b + N) % 8 == N % 8
Иначе – undefined behavior
Требование N % 8 == 0 противоречит (A + N) % 8 == 0, т.к. A > 0

Выравнивающие байты в конце struct/union
Для правильного выравнивания элементов массива T требуется, чтобы sizeof(T) был кратен alignof(T)
Поэтому компилятор может добавлять выравнивающие байты в конце структур и объединений
см. пример про кратность выравниванию элементу структуры
struct XY {
double X;
char Y;
};
// В зависимости от
// alignof(double),
// sizeof(struct XY) == 16
// или 12

Выравнивающие байты в конце struct/union
Для правильного выравнивания элементов массива T требуется, чтобы sizeof(T) был кратен alignof(T)
Поэтому компилятор может добавлять выравнивающие байты в конце структур и объединений
см. пример про кратность
struct XY {
double X;
char Y;
};
// В зависимости от
// alignof(double),
// sizeof(struct XY) == 16
// или 12

Выравнивающие байты в конце struct/union
Для правильного выравнивания элементов массива T требуется, чтобы sizeof(T) был кратен alignof(T)
Поэтому компилятор может добавлять выравнивающие байты в конце структур и объединений
struct XY {
double X;
char Y;
};
// В зависимости от
// alignof(double),
// sizeof(struct XY) == 16
// или 12

Выравнивающие байты в конце struct/union
Для правильного выравнивания элементов массива T требуется, чтобы sizeof(T) был кратен alignof(T)
Поэтому компилятор может добавлять выравнивающие байты в конце структур и объединений
struct XY {
double X;
char Y;
};
// В зависимости от
// alignof(double),
// sizeof(struct XY) == 16
// или 12

Выравнивающие байты внутри struct
Компилятор может добавлять выравнивающие байты между элементами структуры для правильного выравнивания ее элементов
см. N в примере про кратность выравниванию элементу структуры
struct YX {
char Y;
double X;
};
// В зависимости от
// alignof(double),
// sizeof(struct YX) == 16
// или 12

Выравнивающие байты внутри struct
Компилятор может добавлять выравнивающие байты между элементами структуры для правильного выравнивания ее элементов
см. N в примере про кратность выравниванию элементу структуры
struct YX {
char Y;
double X;
};
// В зависимости от
// alignof(double),
// sizeof(struct YX) == 16
// или 12

Выравнивающие байты внутри struct
Компилятор может добавлять выравнивающие байты между элементами структуры для правильного выравнивания ее элементов
см. N в примере про кратность выравниванию элементу структуры
struct YX {
char Y;
double X;
};
// В зависимости от
// alignof(double),
// sizeof(struct YX) == 16
// или 12

Динамическое распределение памяти
Программа в процессе работы сама резервирует и освобождает участки памяти для хранения необходимых ей данных – использует динамическое распределение памяти
Для резервирования и освобождения участка памяти используются стандартные функции языка Си
Участки памяти резервируются в специальной области памяти «куче» (heap)
Динамическое распределение памяти используется, если во время компиляции неизвестна «разумная» верхняя граница на максимальный размер обрабатываемых данных

Динамическое распределение памяти
Программа в процессе работы сама резервирует и освобождает блоки памяти для хранения необходимых ей данных – использует динамическое распределение памяти
Для резервирования и освобождения участка памяти используются стандартные функции языка Си
Участки памяти резервируются в специальной области памяти «куче» (heap)
Динамическое распределение памяти используется, если во время компиляции неизвестна «разумная» верхняя граница на максимальный размер обрабатываемых данных

Динамическое распределение памяти
Программа в процессе работы сама резервирует и освобождает блоки памяти для хранения необходимых ей данных – использует динамическое распределение памяти
Для резервирования и освобождения блока памяти используются стандартные функции языка Си
Участки памяти резервируются в специальной области памяти «куче» (heap)
Динамическое распределение памяти используется, если во время компиляции неизвестна «разумная» верхняя граница на максимальный размер обрабатываемых данных

Динамическое распределение памяти
Программа в процессе работы сама резервирует и освобождает блоки памяти для хранения необходимых ей данных – использует динамическое распределение памяти
Для резервирования и освобождения блока памяти используются стандартные функции языка Си
Блоки памяти резервируются в специальной области памяти «куче» (heap)
Динамическое распределение памяти используется, если во время компиляции неизвестна «разумная» верхняя граница на максимальный размер обрабатываемых данных

Динамическое распределение памяти
Программа в процессе работы сама резервирует и освобождает блоки памяти для хранения необходимых ей данных – использует динамическое распределение памяти
Для резервирования и освобождения блока памяти используются стандартные функции языка Си
Блоки памяти резервируются в специальной области памяти «куче» (heap)
Динамическое распределение памяти используется, если во время компиляции неизвестна «разумная» верхняя граница на максимальный размер обрабатываемых данных

Стандартные функции malloc, free и др.
void* malloc(size_t size)
резервирует непрерывный блок из size байтов и возвращает указатель на него
возвращает NULL, если резервирование невозможно
void* calloc(size_t count, size_t size)
резервирует непрерывный блок из count ∙ size байтов, заполняет нулями и возвращает указатель на него
возвращает NULL, если резервирование невозможно
void* realloc(void* ptr , size_t size)
резервирует непрерывный блок из size байтов и возвращает указатель на него
переносит в новый блок min(size, размер блока по адресу ptr) байтов из блока по адресу ptr и освобождает его
возвращает NULL, если изменение размера невозможно
при этом блок по адресу ptr не освобождается, данные в нем сохраняются
void free(void* ptr)
освобождает ранее зарезервированный блок по адресу ptr

Стандартные функции malloc, free и др.
void* malloc(size_t size)
резервирует непрерывный блок из size байтов и возвращает указатель на него
возвращает NULL, если резервирование невозможно
void* calloc(size_t count, size_t size)
резервирует непрерывный блок из count ∙ size байтов, заполняет нулями и возвращает указатель на него
возвращает NULL, если резервирование невозможно
void* realloc(void* ptr , size_t size)
резервирует непрерывный блок из size байтов и возвращает указатель на него
переносит в новый блок min(size, размер блока по адресу ptr) байтов из блока по адресу ptr и освобождает его
возвращает NULL, если изменение размера невозможно
при этом блок по адресу ptr не освобождается, данные в нем сохраняются
void free(void* ptr)
освобождает ранее зарезервированный блок по адресу ptr

Стандартные функции malloc, free и др.
void* malloc(size_t size)
резервирует непрерывный блок из size байтов и возвращает указатель на него
возвращает NULL, если резервирование невозможно
void* calloc(size_t count, size_t size)
резервирует непрерывный блок из count ∙ size байтов, заполняет нулями и возвращает указатель на него
возвращает NULL, если резервирование невозможно
void* realloc(void* ptr , size_t size)
резервирует непрерывный блок из size байтов и возвращает указатель на него
переносит в новый блок min(size, размер блока по адресу ptr) байтов из блока по адресу ptr и освобождает его
возвращает NULL, если изменение размера невозможно
при этом блок по адресу ptr не освобождается, данные в нем сохраняются
void free(void* ptr)
освобождает ранее зарезервированный блок по адресу ptr

Стандартные функции malloc, free и др.
void* malloc(size_t size)
резервирует непрерывный блок из size байтов и возвращает указатель на него
возвращает NULL, если резервирование невозможно
void* calloc(size_t count, size_t size)
резервирует непрерывный блок из count ∙ size байтов, заполняет нулями и возвращает указатель на него
возвращает NULL, если резервирование невозможно
void* realloc(void* ptr , size_t size)
резервирует непрерывный блок из size байтов и возвращает указатель на него
переносит в новый блок min(size, размер блока по адресу ptr) байтов из блока по адресу ptr и освобождает его
возвращает NULL, если изменение размера невозможно
при этом блок по адресу ptr не освобождается, данные в нем сохраняются
void free(void* ptr)
освобождает ранее зарезервированный блок по адресу ptr

Стандартные функции malloc, free и др.
void* malloc(size_t size)
резервирует непрерывный блок из size байтов и возвращает указатель на него
возвращает NULL, если резервирование невозможно
void* calloc(size_t count, size_t size)
резервирует непрерывный блок из count ∙ size байтов, заполняет нулями и возвращает указатель на него
возвращает NULL, если резервирование невозможно
void* realloc(void* ptr , size_t size)
резервирует непрерывный блок из size байтов и возвращает указатель на него
переносит в новый блок min(size, размер блока по адресу ptr) байтов из блока по адресу ptr и освобождает его
возвращает NULL, если изменение размера невозможно
при этом блок по адресу ptr не освобождается, данные в нем сохраняются
void free(void* ptr)
освобождает ранее зарезервированный блок по адресу ptr

Стандартные функции malloc, free и др.
void* malloc(size_t size)
резервирует непрерывный блок из size байтов и возвращает указатель на него
возвращает NULL, если резервирование невозможно
void* calloc(size_t count, size_t size)
резервирует непрерывный блок из count ∙ size байтов, заполняет нулями и возвращает указатель на него
возвращает NULL, если резервирование невозможно
void* realloc(void* ptr , size_t size)
резервирует непрерывный блок из size байтов и возвращает указатель на него
переносит в новый блок min(size, размер блока по адресу ptr) байтов из блока по адресу ptr и освобождает его
возвращает NULL, если изменение размера невозможно
при этом блок по адресу ptr не освобождается, данные в нем сохраняются
void free(void* ptr)
освобождает ранее зарезервированный блок по адресу ptr

Стандартные функции malloc, free и др.
void* malloc(size_t size)
резервирует непрерывный блок из size байтов и возвращает указатель на него
возвращает NULL, если резервирование невозможно
void* calloc(size_t count, size_t size)
резервирует непрерывный блок из count ∙ size байтов, заполняет нулями и возвращает указатель на него
возвращает NULL, если резервирование невозможно
void* realloc(void* ptr , size_t size)
резервирует непрерывный блок из size байтов и возвращает указатель на него
переносит в новый блок min(size, размер блока по адресу ptr) байтов из блока по адресу ptr и освобождает его
возвращает NULL, если изменение размера невозможно
при этом блок по адресу ptr не освобождается, данные в нем сохраняются
void free(void* ptr)
освобождает ранее зарезервированный блок по адресу ptr

Стандартные функции malloc, free и др.
void* malloc(size_t size)
резервирует непрерывный блок из size байтов и возвращает указатель на него
возвращает NULL, если резервирование невозможно
void* calloc(size_t count, size_t size)
резервирует непрерывный блок из count ∙ size байтов, заполняет нулями и возвращает указатель на него
возвращает NULL, если резервирование невозможно
void* realloc(void* ptr , size_t size)
резервирует непрерывный блок из size байтов и возвращает указатель на него
переносит в новый блок min(size, размер блока по адресу ptr) байтов из блока по адресу ptr и освобождает его
возвращает NULL, если изменение размера невозможно
при этом блок по адресу ptr не освобождается, данные в нем сохраняются
void free(void* ptr)
освобождает ранее зарезервированный блок по адресу ptr

Стандартные функции malloc, free и др.
void* malloc(size_t size)
резервирует непрерывный блок из size байтов и возвращает указатель на него
возвращает NULL, если резервирование невозможно
void* calloc(size_t count, size_t size)
резервирует непрерывный блок из count ∙ size байтов, заполняет нулями и возвращает указатель на него
возвращает NULL, если резервирование невозможно
void* realloc(void* ptr , size_t size)
резервирует непрерывный блок из size байтов и возвращает указатель на него
переносит в новый блок min(size, размер блока по адресу ptr) байтов из блока по адресу ptr и освобождает его
возвращает NULL, если изменение размера невозможно
при этом блок по адресу ptr не освобождается, данные в нем сохраняются
void free(void* ptr)
освобождает ранее зарезервированный блок по адресу ptr

Стандартные функции malloc, free и др.
void* malloc(size_t size)
резервирует непрерывный блок из size байтов и возвращает указатель на него
возвращает NULL, если резервирование невозможно
void* calloc(size_t count, size_t size)
резервирует непрерывный блок из count ∙ size байтов, заполняет нулями и возвращает указатель на него
возвращает NULL, если резервирование невозможно
void* realloc(void* ptr , size_t size)
резервирует непрерывный блок из size байтов и возвращает указатель на него
переносит в новый блок min(size, размер блока по адресу ptr) байтов из блока по адресу ptr и освобождает его
возвращает NULL, если изменение размера невозможно
при этом блок по адресу ptr не освобождается, данные в нем сохраняются
void free(void* ptr)
освобождает ранее зарезервированный блок по адресу ptr

Doug Lea’s malloc (dlmalloc)
Основа malloc в библиотеке GNU C (libc) для большинства версий Linux
http://gee.cs.oswego.edu/dl/html/malloc.html
Douglas (Doug) Lea, JVM Language Summit, 2010

Doug Lea’s malloc (dlmalloc)
Основа malloc в библиотеке GNU C (libc) для большинства версий Linux
http://gee.cs.oswego.edu/dl/html/malloc.html
Douglas (Doug) Lea, JVM Language Summit, 2010

Doug Lea’s malloc (dlmalloc)
Основа malloc в библиотеке GNU C (libc) для большинства версий Linux
http://gee.cs.oswego.edu/dl/html/malloc.html
Douglas (Doug) Lea, JVM Language Summit, 2010

Doug Lea’s malloc (dlmalloc)
Основа malloc в библиотеке GNU C (libc) для большинства версий Linux
http://gee.cs.oswego.edu/dl/html/malloc.html
Douglas (Doug) Lea, JVM Language Summit, 2010

Устройство «кучи»

Устройство «кучи»

Устройство «кучи»

Устройство «кучи»

Устройство «кучи»

Резервирование malloc(size)
block = свободный блок min размера ≥ size
Если block не найден, то возвращаем NULL
Если размер(block) ≈ size, то возвращаем block + sizeof(size_t)
Иначе режем block на userBlock и freeBlock, чтобы размер(userBlock ) ≈ size
Добавляем freeBlock в список свободных блоков размера размер(freeBlock)
Возвращаем userBlock + sizeof(size_t)
malloc(size)

Резервирование malloc(size)
block = свободный блок min размера ≥ size
Если block не найден, то возвращаем NULL
Если размер(block) ≈ size, то возвращаем block + sizeof(size_t)
Иначе режем block на userBlock и freeBlock, чтобы размер(userBlock ) ≈ size
Добавляем freeBlock в список свободных блоков размера размер(freeBlock)
Возвращаем userBlock + sizeof(size_t)
malloc(size)

Резервирование malloc(size)
block = свободный блок min размера ≥ size
Если block не найден, то возвращаем NULL
Если размер(block) ≈ size, то возвращаем block + sizeof(size_t)
Иначе режем block на userBlock и freeBlock, чтобы размер(userBlock ) ≈ size
Добавляем freeBlock в список свободных блоков размера размер(freeBlock)
Возвращаем userBlock + sizeof(size_t)
malloc(size)

Резервирование malloc(size)
block = свободный блок min размера ≥ size
Если block не найден, то возвращаем NULL
Если размер(block) ≈ size, то возвращаем block + sizeof(size_t)
Иначе режем block на userBlock и freeBlock, чтобы размер(userBlock ) ≈ size
Добавляем freeBlock в список свободных блоков размера размер(freeBlock)
Возвращаем userBlock + sizeof(size_t)
malloc(size)

Резервирование malloc(size)
block = свободный блок min размера ≥ size
Если block не найден, то возвращаем NULL
Если размер(block) ≈ size, то возвращаем block + sizeof(size_t)
Иначе режем block на userBlock и freeBlock, чтобы размер(userBlock ) ≈ size
Добавляем freeBlock в список свободных блоков размера размер(freeBlock)
Возвращаем userBlock + sizeof(size_t)
malloc(size)

Резервирование malloc(size)
block = свободный блок min размера ≥ size
Если block не найден, то возвращаем NULL
Если размер(block) ≈ size, то возвращаем block + sizeof(size_t)
Иначе режем block на userBlock и freeBlock, чтобы размер(userBlock ) ≈ size
Добавляем freeBlock в список свободных блоков размера размер(freeBlock)
Возвращаем userBlock + sizeof(size_t)
malloc(size)

Резервирование malloc(size)
block = свободный блок min размера ≥ size
Если block не найден, то возвращаем NULL
Если размер(block) ≈ size, то возвращаем block + sizeof(size_t)
Иначе режем block на userBlock и freeBlock, чтобы размер(userBlock ) ≈ size
Добавляем freeBlock в список свободных блоков размера размер(freeBlock)
Возвращаем userBlock + sizeof(size_t)
malloc(size)

Освобождение free(ptr)
Объединяем с блоком по адресу ptr блок слева (если свободен) и блок справа (если свободен)
«слева» и «справа» по адресу в памяти, а не по связям в списке
Добавляем получившийся блок в список свободных блоков соотв. размера
free(ptr)

Освобождение free(ptr)
Объединяем с блоком по адресу ptr блок слева (если свободен) и блок справа (если свободен)
«слева» и «справа» по адресу в памяти, а не по связям в списке
Добавляем получившийся блок в список свободных блоков соотв. размера
free(ptr)

Освобождение free(ptr)
Объединяем с блоком по адресу ptr блок слева (если свободен) и блок справа (если свободен)
«слева» и «справа» по адресу в памяти, а не по связям в списке
Добавляем получившийся блок в список свободных блоков соотв. размера
free(ptr)

Накладные расходы при работе с кучей
Поиск min свободного блока в malloc
malloc размера > 512 байтов и много свободных блоков в соотв. списке – большой накладной расход времени на просмотр
Дополнительные 2 ∙ sizeof(size_t) байтов на каждый блок
Много malloc небольшого размера – большой накладной расход памяти

Накладные расходы при работе с кучей
Поиск min свободного блока в malloc
malloc размера > 512 байтов и много свободных блоков в соотв. списке – большой накладной расход времени на просмотр списка свободных блоков
Дополнительные 2 ∙ sizeof(size_t) байтов на каждый блок
Много malloc небольшого размера – большой накладной расход памяти

Накладные расходы при работе с кучей
Поиск min свободного блока в malloc
malloc размера > 512 байтов и много свободных блоков в соотв. списке – большой накладной расход времени на просмотр списка свободных блоков
Дополнительные 2 ∙ sizeof(size_t) байтов на каждый блок
Много malloc небольшого размера – большой накладной расход памяти

Фрагментация кучи
Резервирование и освобождение блоков разного размера приводит к фрагментации
for (int i = 0; i < count; ++i) {
void* small = malloc(8);
bigger[i] = malloc(32);
free(small);
}

Фрагментация кучи
Резервирование и освобождение блоков разного размера приводит к фрагментации
for (int i = 0; i < count; ++i) {
void* small = malloc(8);
bigger[i] = malloc(32);
free(small);
}

Фрагментация кучи
Резервирование и освобождение блоков разного размера приводит к фрагментации
for (int i = 0; i < count; ++i) {
void* small = malloc(8);
bigger[i] = malloc(32);
free(small);
}

Фрагментация кучи
Резервирование и освобождение блоков разного размера приводит к фрагментации
for (int i = 0; i < count; ++i) {
void* small = malloc(8);
bigger[i] = malloc(32);
free(small);
}

Фрагментация кучи
Резервирование и освобождение блоков разного размера приводит к фрагментации
Свободная память разбита на большое число мелких блоков и нет возможности зарезервировать блоки большего размера
for (int i = 0; i < count; ++i) {
void* small = malloc(8);
bigger[i] = malloc(32);
free(small);
}

Виды ошибок при работе с кучей
// missing NULL pointer check
int* ptr = malloc(4);
*ptr = 0; // <--
free(ptr);
*ptr = 0; // use after free
free(ptr); // double free
// freeing invalid pointer
ptr = malloc(8);
free(ptr + 4); // <--
// memory leak
ptr = malloc(8);
ptr = malloc(8); // <--
// freeing invalid pointer
free(&ptr);
ptr = malloc(4);
for (int i = 0; i < 10; ++i) {
// heap corruption
ptr[i-1] = 0; // <--
}

Виды ошибок при работе с кучей
// missing NULL pointer check
int* ptr = malloc(4);
*ptr = 0; // <--
free(ptr);
*ptr = 0; // use after free
free(ptr); // double free
// freeing invalid pointer
ptr = malloc(8);
free(ptr + 4); // <--
free(&ptr); // <--
// memory leak
ptr = malloc(8);
ptr = malloc(8); // <--
// memory leak
ptr = realloc(ptr, 32); // <-- if OOM
// heap corruption
ptr = malloc(4);
for (int i = 0; i < 10; ++i) {
ptr[i - 1] = 0; // <-- if i = 0
}

Виды ошибок при работе с кучей
// missing NULL pointer check
int* ptr = malloc(4);
*ptr = 0; // <--
free(ptr);
*ptr = 0; // use after free
free(ptr); // double free
// freeing invalid pointer
ptr = malloc(8);
free(ptr + 4); // <--
free(&ptr); // <--
// memory leak
ptr = malloc(8);
ptr = malloc(8); // <--
// memory leak
ptr = realloc(ptr, 32); // <-- if OOM
// heap corruption
ptr = malloc(4);
for (int i = 0; i < 10; ++i) {
ptr[i - 1] = 0; // <-- if i = 0
}

Виды ошибок при работе с кучей
// missing NULL pointer check
int* ptr = malloc(4);
*ptr = 0; // <--
free(ptr);
*ptr = 0; // use after free
free(ptr); // double free
// freeing invalid pointer
ptr = malloc(8);
free(ptr + 4); // <--
free(&ptr); // <--
// memory leak
ptr = malloc(8);
ptr = malloc(8); // <--
// memory leak
ptr = realloc(ptr, 32); // <-- if OOM
// heap corruption
ptr = malloc(4);
for (int i = 0; i < 10; ++i) {
ptr[i - 1] = 0; // <-- if i = 0
}

Виды ошибок при работе с кучей
// missing NULL pointer check
int* ptr = malloc(4);
*ptr = 0; // <--
free(ptr);
*ptr = 0; // use after free
free(ptr); // double free
// freeing invalid pointer
ptr = malloc(8);
free(ptr + 4); // <--
free(&ptr); // <--
// memory leak
ptr = malloc(8);
ptr = malloc(8); // <--
// memory leak
ptr = realloc(ptr, 32); // <-- if OOM
// heap corruption
ptr = malloc(4);
for (int i = 0; i < 10; ++i) {
ptr[i - 1] = 0; // <-- if i = 0
}

Виды ошибок при работе с кучей
// missing NULL pointer check
int* ptr = malloc(4);
*ptr = 0; // <--
free(ptr);
*ptr = 0; // use after free
free(ptr); // double free
// freeing invalid pointer
ptr = malloc(8);
free(ptr + 4); // <--
free(&ptr); // <--
// memory leak
ptr = malloc(8);
ptr = malloc(8); // <--
// memory leak
ptr = realloc(ptr, 32); // <-- if OOM
// heap corruption
ptr = malloc(4);
for (int i = 0; i < 10; ++i) {
ptr[i - 1] = 0; // <-- if i = 0
}

Виды ошибок при работе с кучей
// missing NULL pointer check
int* ptr = malloc(4);
*ptr = 0; // <--
free(ptr);
*ptr = 0; // use after free
free(ptr); // double free
// freeing invalid pointer
ptr = malloc(8);
free(ptr + 4); // <--
free(&ptr); // <--
// memory leak
ptr = malloc(8);
ptr = malloc(8); // <--
// memory leak
ptr = realloc(ptr, 32); // <-- if OOM
// heap corruption
ptr = malloc(4);
for (int i = 0; i < 10; ++i) {
ptr[i - 1] = 0; // <-- if i = 0
}

Виды ошибок при работе с кучей
// missing NULL pointer check
int* ptr = malloc(4);
*ptr = 0; // <--
free(ptr);
*ptr = 0; // use after free
free(ptr); // double free
// freeing invalid pointer
ptr = malloc(8);
free(ptr + 4); // <--
free(&ptr); // <--
// memory leak
ptr = malloc(8);
ptr = malloc(8); // <--
// memory leak
ptr = realloc(ptr, 32); // <-- if OOM
// heap corruption
ptr = malloc(4);
for (int i = 0; i < 10; ++i) {
ptr[i - 1] = 0; // <-- if i = 0
}

Виды ошибок при работе с кучей
// missing NULL pointer check
int* ptr = malloc(4);
*ptr = 0; // <--
free(ptr);
*ptr = 0; // use after free
free(ptr); // double free
// freeing invalid pointer
ptr = malloc(8);
free(ptr + 4); // <--
free(&ptr); // <--
// memory leak
ptr = malloc(8);
ptr = malloc(8); // <--
// memory leak
ptr = realloc(ptr, 32); // <-- if OOM
// heap corruption
ptr = malloc(4);
for (int i = 0; i < 10; ++i) {
ptr[i - 1] = 0; // <-- if i = 0
}

Address sanitizer
Константин Серебряный1
Derek Bruening2
Александр Потапенко3
Дмитрий Вьюков4
AddressSanitizer: A Fast Address Sanity Checker
https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37752.pdf
1
2
3
4

Address sanitizer
Константин Серебряный1
Derek Bruening2
Александр Потапенко3
Дмитрий Вьюков4
AddressSanitizer: A Fast Address Sanity Checker
https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37752.pdf

Address sanitizer
Константин Серебряный1
Derek Bruening2
Александр Потапенко3
Дмитрий Вьюков4
AddressSanitizer: A Fast Address Sanity Checker
https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37752.pdf
1
2
3
4

Address sanitizer
Константин Серебряный1
Derek Bruening2
Александр Потапенко3
Дмитрий Вьюков4
AddressSanitizer: A Fast Address Sanity Checker, 2012
https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37752.pdf
1
2
3
4

Use after free

Buffer overflow (heap corruption)