Здесь тоже живут драконы: синтаксис vs семантика
Опытным разработчикам известно, что между исходным кодом и сгенерированным ассемблером, на уровнях оптимизации начиная с O1, нет ничего общего.
Скомпилированный код обязан лишь иметь видимое поведение (в соответствие со стандартами), соответствующее синтаксису. Однако чем выше уровень оптимизации, тем агрессивнее оптимизация и семантика ассемблера все больше и больше отличается от исходного кода. При выполнении оптимизаций компилятор может сделать практически что угодно. Выкинуть блокировку, если считает, что она не нужна в конкретном месте. Переупорядочить блоки инструкций. Выкинуть код, который, как ему кажется, не влияет на видимое поведение. Здравствуй, UB.
Однако речь сейчас не об UB, а о производительности vs читаемости кода.
Как уже было сказано, распространенное мнение об интеллектуальности компиляторов ошибочно. Соответственно, расхожее мнение, будто бы компилятор сам разберется, как сгенерировать наиболее эффективный код, ошибочно тоже.
Рассмотрим простенький пример.
Он же на Godbolt. Можно с интересом поиграться с уровнями оптимизации и типами данных и посмотреть, что генерируется для двух идентичных операций целочисленного деления.
На SO бытует стойкое ошибочное мнение, будто бы арифметика всегда оптимизируется до быстрых аппаратно поддерживаемых bitwise операций. Это не во всех случаях верно.
В данном конкретном примере, разница существенная. Битовый сдвиг генерирует одну инструкцию. Деление - пять инструкций. Разумеется, читаемость выше у деления. На SO утверждают, будто бы на O1-O3 будет одно и то же.
Самые внимательные заметили, что x знаковый. Если сделать его беззнаковым - компилятор резко умнеет и оба случая компилируются в битовый сдвиг.
Самые продвинутые заметят, что если в вычислении y кастануть x в беззнаковый тип, произойдет то же самое.
Умудренные опытом скажут, что каст опасен - смешивание знаковых и беззнаковых в арифметике - прямая дорога к UB. Быстро, но опасно.
Кстати, антипример - tcmalloc переполнен int'ами и выражениями где смешаны
Возвращаясь к нашему примеру. В общем-то, нет ничего сложного привести типы в соответствие, если уж вы настаиваете на чистом коде, понятном даже начинающим программистам. Приводить в любом случае придется, потому что UB не дремлет.
Но нет никаких трудностей использовать bitwise - напомним, они поддерживаются процессорами аппаратно и очень быстры - для той же целочисленной арифметики. А для умеющих читать рядом написать комментарий, где перевести битовое выражение на понятный даже им язык. Битовый сдвиг не только выполняется аппаратно - его использование гарантирует неизменность генерируемого компилятором кода в данном конкретном случае.
Все вышесказанное лишь один крошечный пример того, что синтаксис не равнозначен семантике. Интересоваться при программировании стоит не только фичами и их быстрой реализацией. Но и тем, как они воплощаются на нижнем уровне.
Там, под капотом, живут не только агрессивная оптимизация, видимое поведение и UB, но и значимые изменения производительности, причем синтаксис прямо или косвенно определяет семантику.
И все, в конечном итоге, исключительно в руках программиста. Это ему решать - к умным или к красивым.
Опытным разработчикам известно, что между исходным кодом и сгенерированным ассемблером, на уровнях оптимизации начиная с O1, нет ничего общего.
Скомпилированный код обязан лишь иметь видимое поведение (в соответствие со стандартами), соответствующее синтаксису. Однако чем выше уровень оптимизации, тем агрессивнее оптимизация и семантика ассемблера все больше и больше отличается от исходного кода. При выполнении оптимизаций компилятор может сделать практически что угодно. Выкинуть блокировку, если считает, что она не нужна в конкретном месте. Переупорядочить блоки инструкций. Выкинуть код, который, как ему кажется, не влияет на видимое поведение. Здравствуй, UB.
Однако речь сейчас не об UB, а о производительности vs читаемости кода.
Как уже было сказано, распространенное мнение об интеллектуальности компиляторов ошибочно. Соответственно, расхожее мнение, будто бы компилятор сам разберется, как сгенерировать наиболее эффективный код, ошибочно тоже.
Рассмотрим простенький пример.
#include <cstddef>
ptrdiff_t x { 1024 };
int main()
{
size_t y, z;
y = x / 2;
z = x >> 1;
return y + z;
}
Он же на Godbolt. Можно с интересом поиграться с уровнями оптимизации и типами данных и посмотреть, что генерируется для двух идентичных операций целочисленного деления.
На SO бытует стойкое ошибочное мнение, будто бы арифметика всегда оптимизируется до быстрых аппаратно поддерживаемых bitwise операций. Это не во всех случаях верно.
В данном конкретном примере, разница существенная. Битовый сдвиг генерирует одну инструкцию. Деление - пять инструкций. Разумеется, читаемость выше у деления. На SO утверждают, будто бы на O1-O3 будет одно и то же.
Самые внимательные заметили, что x знаковый. Если сделать его беззнаковым - компилятор резко умнеет и оба случая компилируются в битовый сдвиг.
Самые продвинутые заметят, что если в вычислении y кастануть x в беззнаковый тип, произойдет то же самое.
Умудренные опытом скажут, что каст опасен - смешивание знаковых и беззнаковых в арифметике - прямая дорога к UB. Быстро, но опасно.
Кстати, антипример - tcmalloc переполнен int'ами и выражениями где смешаны
int и size_t. Можно догадаться, чем пахнут спелые фиги и применение такого щедрого подарка в продакшене. Стоит, в общем, читать исходники опенсурсной халявы, прежде, чем тащить в прод.Возвращаясь к нашему примеру. В общем-то, нет ничего сложного привести типы в соответствие, если уж вы настаиваете на чистом коде, понятном даже начинающим программистам. Приводить в любом случае придется, потому что UB не дремлет.
Но нет никаких трудностей использовать bitwise - напомним, они поддерживаются процессорами аппаратно и очень быстры - для той же целочисленной арифметики. А для умеющих читать рядом написать комментарий, где перевести битовое выражение на понятный даже им язык. Битовый сдвиг не только выполняется аппаратно - его использование гарантирует неизменность генерируемого компилятором кода в данном конкретном случае.
Все вышесказанное лишь один крошечный пример того, что синтаксис не равнозначен семантике. Интересоваться при программировании стоит не только фичами и их быстрой реализацией. Но и тем, как они воплощаются на нижнем уровне.
Там, под капотом, живут не только агрессивная оптимизация, видимое поведение и UB, но и значимые изменения производительности, причем синтаксис прямо или косвенно определяет семантику.
И все, в конечном итоге, исключительно в руках программиста. Это ему решать - к умным или к красивым.
TheCacheWorks pinned «Не надо хотеть невозможного Если вы имеете хоть какое-то отношение к IT, возможно, вам известна фундаментальная системная закономерность - временная и пространственная сложности алгоритмов противоположны. Простыми словами - либо вы экономите память, либо…»
Драконье логово: обертки оберток
Любителям оберток и оберток оберток посвящается.
Рассмотрим снова простенький пример.
Два, казалось бы, с виду идентичных функционально, вызова. По логике, первое - кроссплатформенное - должно транслироваться один-в-один во второе.
Если посмотреть на ассемблерный код, на любых уровнях оптимизации, первый вызов дополнительно порождает две ассемблерных команды (на уровне оптимизации -O3) - вызов конструктора типа
Казалось бы, какая мелочь. Что там конструировать, знаковое целое, INT_MAX, о чем там волноваться?
Если бы. В горячем пути эта разница дает 2,5% потери производительности (для кроссплатформенного и типобезопасного
О чем беспокоиться? Вот о чем - эти 2,5% - при единственном вызове в горячем пути. Да, всего один вызов и один запуск конструктора типа. Ничего особенного.
Это совсем простенький, тривиальный пример, как один уровень абстракции всего в одной функции просаживает производительность.
Как известно, в оптимизации производительности мелочей нет. Микрооптимизации, пренебрежительно игнорируемые, в массе суммируются вполне себе в макрооптимизации.
Процессорные циклы. Наносекунды складываются в секунды, а секунды в боль.
Чем больше вы наворачиваете уровней абстракции - даже если вам дуют в уши, что это совершенно бесплатно, то есть даром - тем больше вы впустую тратите процессорных циклов. Хотите вы этого или нет.
Абстракции не бесплатны. Бесчисленные обертки, обертки оберток, фреймворки, фреймворки фреймворков - любознательные инженеры уже давно выяснили, что прямой, как палка, тупой в лоб написанный JS - много быстрее фреймворков.
Закон Мура подошел к своим теоретическим пределам, тактовые частоты выше 4 ГГц не могут подняться уже свыше 10 лет, размеры техпроцесса не могут быть меньше размера атома - а квантовые эффекты начнутся сильно раньше.
Время задуматься об оптимизации. И игнорировать даже микрооптимизации больше не получится.
Любителям оберток и оберток оберток посвящается.
Рассмотрим снова простенький пример.
#include <thread>
std::thread::id thread_id = std::this_thread::get_id();
#include <pthread.h>
pthread_t thread_id = pthread_self();
Два, казалось бы, с виду идентичных функционально, вызова. По логике, первое - кроссплатформенное - должно транслироваться один-в-один во второе.
Если посмотреть на ассемблерный код, на любых уровнях оптимизации, первый вызов дополнительно порождает две ассемблерных команды (на уровне оптимизации -O3) - вызов конструктора типа
std::thread::id. Для типобезопасности.Казалось бы, какая мелочь. Что там конструировать, знаковое целое, INT_MAX, о чем там волноваться?
Если бы. В горячем пути эта разница дает 2,5% потери производительности (для кроссплатформенного и типобезопасного
get_id()).О чем беспокоиться? Вот о чем - эти 2,5% - при единственном вызове в горячем пути. Да, всего один вызов и один запуск конструктора типа. Ничего особенного.
Это совсем простенький, тривиальный пример, как один уровень абстракции всего в одной функции просаживает производительность.
Как известно, в оптимизации производительности мелочей нет. Микрооптимизации, пренебрежительно игнорируемые, в массе суммируются вполне себе в макрооптимизации.
Процессорные циклы. Наносекунды складываются в секунды, а секунды в боль.
Чем больше вы наворачиваете уровней абстракции - даже если вам дуют в уши, что это совершенно бесплатно, то есть даром - тем больше вы впустую тратите процессорных циклов. Хотите вы этого или нет.
Абстракции не бесплатны. Бесчисленные обертки, обертки оберток, фреймворки, фреймворки фреймворков - любознательные инженеры уже давно выяснили, что прямой, как палка, тупой в лоб написанный JS - много быстрее фреймворков.
Закон Мура подошел к своим теоретическим пределам, тактовые частоты выше 4 ГГц не могут подняться уже свыше 10 лет, размеры техпроцесса не могут быть меньше размера атома - а квантовые эффекты начнутся сильно раньше.
Время задуматься об оптимизации. И игнорировать даже микрооптимизации больше не получится.
Федорино core
В glibC 2.42 (Федора 43 и другие роллинги) сделали защиту от DF. Причем сделали так, что лучше бы не делали.
Как всегда, напишем простенький тест:
Скомпилируем и запустим:
Посмотрим на стектрейс (на КДПВ). Вам он хоть что-нибудь говорит? Нам не говорит тоже. Сегфолт прилетает из глубин glibC, ни единого намека на четкий и ясный код, вызвавший DF - как, вообще говоря, должно быть. Что такое tcache 2? Должно быть, некая структура метаданных бэкэнда системного аллокатора, не так ли? А какая именно? И как она связана с DF в нашем коде?
Как программист должен догадаться, где произошел DF - в сколько-нибудь сложном коде, если в стектрейсе ничего вообще на это не указывает?
Телепаты загорают на Бали.
От аллокатора хотят - нет, требуют! - чтобы он ловил DF/UAF и при сегфолте четко указывал, где именно произошло двойное освобождение.
Однако, для этого требуется одна мелочь - аллокатор должен полностью в юзерспейсе выполняться. Иначе защита будет срабатывать в неизведанных глубинах ядра и пользы от такой защиты - ровно тот факт, что где-то в приложении есть double-free.
UPD. Помимо полной неясности, где именно произошел double-free, есть еще один, гораздо более серьезный, недостаток. Простейшие и самоочевидные DF эта защита ловит. Но уже чуть менее тривиальные случаи она не отлавливает и просто заметает под ковер без всяких сегфолтов. Что значительно хуже. Неполноценная защита едва ли лучше ее полного отсутствия.
В glibC 2.42 (Федора 43 и другие роллинги) сделали защиту от DF. Причем сделали так, что лучше бы не делали.
Как всегда, напишем простенький тест:
#include <iostream>
#include <vector>
#include <functional>
#include <cstdlib>
int main() {
void* dangling_ptr = nullptr;
// Queue of callbacks
std::vector<std::function<void()>> callbacks;
// Callback #1: allocate block and save dangling pointer
callbacks.push_back([&dangling_ptr]() {
void* block = malloc(128);
dangling_ptr = block; // save dangling pointer
free(block); // block goes back to thread cache
});
// Callback #2: allocate new block of same size
callbacks.push_back([]() {
void* new_block = malloc(128);
(void)new_block; // pretend to use
});
// Callback #3: free using old dangling pointer
callbacks.push_back([&dangling_ptr]() {
std::cout << "dangling_ptr=" << dangling_ptr << std::endl;
std::cout << "calling free(dangling_ptr)..." << std::endl;
free(dangling_ptr); // crash on allocator
});
// Execute callbacks in order
for (auto& cb : callbacks) {
cb();
}
}
Скомпилируем и запустим:
BIT=-m64
g++ -O3 $BIT -std=c++11 -c -o test1.o test1.cc
g++ $BIT -s -o test1 test1.o
./test1
dangling_ptr=0x2d235430
calling free(dangling_ptr)...
free(): double free detected in tcache 2
./test1.sh: line 7: 2749 Aborted (core dumped) ./test1
Посмотрим на стектрейс (на КДПВ). Вам он хоть что-нибудь говорит? Нам не говорит тоже. Сегфолт прилетает из глубин glibC, ни единого намека на четкий и ясный код, вызвавший DF - как, вообще говоря, должно быть. Что такое tcache 2? Должно быть, некая структура метаданных бэкэнда системного аллокатора, не так ли? А какая именно? И как она связана с DF в нашем коде?
Как программист должен догадаться, где произошел DF - в сколько-нибудь сложном коде, если в стектрейсе ничего вообще на это не указывает?
Телепаты загорают на Бали.
От аллокатора хотят - нет, требуют! - чтобы он ловил DF/UAF и при сегфолте четко указывал, где именно произошло двойное освобождение.
Однако, для этого требуется одна мелочь - аллокатор должен полностью в юзерспейсе выполняться. Иначе защита будет срабатывать в неизведанных глубинах ядра и пользы от такой защиты - ровно тот факт, что где-то в приложении есть double-free.
UPD. Помимо полной неясности, где именно произошел double-free, есть еще один, гораздо более серьезный, недостаток. Простейшие и самоочевидные DF эта защита ловит. Но уже чуть менее тривиальные случаи она не отлавливает и просто заметает под ковер без всяких сегфолтов. Что значительно хуже. Неполноценная защита едва ли лучше ее полного отсутствия.
Где находится double-free
По следам предыдущей публикации, небольшой технический разбор.
А как вообще можно на уровне аллокатора или его бэкэнда отловить double-free в прикладном коде?
Собственно, это в значительной степени зависит от архитектуры аллокатора.
Допустим, что аллокатор (или его бэкэнд) построен на основе односвязных списков - фрилистов. При выполнении вызова free(), указатель на блок добавляется в список, и затем, спустя какое-то время, фрилист уходит на утилизацию ОС либо в некое центральное хранилище (кэш).
То есть, существует некоторый гистерезис между формальным освобождением и фактическим. В этот промежуток и проскальзывает double-free, если кодирование приложения осуществлялось небрежно и на блок есть либо висящие указатели, либо кто-то просто забыл, что после освобождения памяти по указателю сам указатель надо в обязательном порядке занулить.
Этот гистерезис делается намеренно, чтобы не тратить лишние циклы на жонглирование указателями и фрилистами туда-сюда. В случае бэкэнда ОС, это в особенности важно, так как ядру и так есть чем заняться.
Если немного подумать, простейшая и наивная защита от DF - при освобождении указателя перед его помещением во фрилист, проитерироваться по фрилисту с проверкой указателя - а не находится ли он уже в списке свободных? Всё бы ничего, но это O(n) прямо в горячем пути. Падение производительности аллокатора будет не драматическим - а астрономическим, на пару десятичных порядков примерно.
Вариант продвинутый - использовать дополнительную память, поверх фрилиста выстроить хэш-таблицу и проверять вхождение по хэшу. И все вариации на эту тему. O(n) уже по памяти. Плюс расчет хэшей.
Вариант хрупкий - манипуляции со старшими битами указателей, чтобы помечать, что блок уже освобожден. Минус масштабирование - что, если нужны все биты указателя? Ну, к примеру - сервер с кучей терабайт и эти терабайты задействованы полностью? Риск случайного затирания весьма велик.
Определив, что указатель уже был недавно освобожден, возможны два варианта поведения. Первый - замести под ковер. Просто молча сглотнуть указатель и больше его во фрилист не добавлять. Плохо, потому что это скрытый 0-day. Который неизбежно найдут и используют, а вы даже знать об этом не будете. Второй - плюнуть сегфолтом в приложение. Вариант неплох, вы сразу получите стектрейс с указанием, где примерно в коде приложения был DF.
Однако накладные расходы на защиту будут ужасные. Все это происходит в горячих путях и жрет - с учетом интенсивности malloc/free - процессорные циклы как не в себя.
Нативная защита на уровне аллокатора возможна. Ну, что считать защитой - проглатывать повторные освобождения опасно для здоровья, кидаться сегфолтами можно и нужно - и только так должен вести себя православный аллокатор. Мы лишь хотим, чтобы стектрейс нам прямо указывал на место в коде, где затаился double-free.
Что это означает на практике? На практике это означает, что нам всего-то навсего архитектурно нужна очень жесткая reuse policy. То есть, free() должно означать "немедленный free, блок сразу же, через наносекунду, попадает во фрилист и будет переиспользован". В этом случае молниеносно происходит смена владения и аллокатор, обнаружив, что кто-то уже трогает память, которая была освобождена и переиспользована, незамедлительно кинет сегфолт. Что, по цепочке, приведет к образованию внятного стектрейса приложения (не бэкэнда, не компонентов ядра ОС), с free() на вершине стека.
Одна маленькая проблемка. Ни один из существующих аллокаторов так не реализован.
То есть - нативной защиты не существует. И, вообще говоря, это означает, что все ходят по краю пропасти.
Нет, Rust не спасёт и не сохранит. Нет, статический анализ не обязан видеть DF.
Единственная, по сути, защита - это строгая дисциплина программирования - всегда зануляйте указатели после освобождения памяти - и жесткая reuse policy аллокаторов. Которая - единственная - при обнаружении DF немедленно уронит приложение, а не закопает ошибку владения под ковер.
По следам предыдущей публикации, небольшой технический разбор.
А как вообще можно на уровне аллокатора или его бэкэнда отловить double-free в прикладном коде?
Собственно, это в значительной степени зависит от архитектуры аллокатора.
Допустим, что аллокатор (или его бэкэнд) построен на основе односвязных списков - фрилистов. При выполнении вызова free(), указатель на блок добавляется в список, и затем, спустя какое-то время, фрилист уходит на утилизацию ОС либо в некое центральное хранилище (кэш).
То есть, существует некоторый гистерезис между формальным освобождением и фактическим. В этот промежуток и проскальзывает double-free, если кодирование приложения осуществлялось небрежно и на блок есть либо висящие указатели, либо кто-то просто забыл, что после освобождения памяти по указателю сам указатель надо в обязательном порядке занулить.
Этот гистерезис делается намеренно, чтобы не тратить лишние циклы на жонглирование указателями и фрилистами туда-сюда. В случае бэкэнда ОС, это в особенности важно, так как ядру и так есть чем заняться.
Если немного подумать, простейшая и наивная защита от DF - при освобождении указателя перед его помещением во фрилист, проитерироваться по фрилисту с проверкой указателя - а не находится ли он уже в списке свободных? Всё бы ничего, но это O(n) прямо в горячем пути. Падение производительности аллокатора будет не драматическим - а астрономическим, на пару десятичных порядков примерно.
Вариант продвинутый - использовать дополнительную память, поверх фрилиста выстроить хэш-таблицу и проверять вхождение по хэшу. И все вариации на эту тему. O(n) уже по памяти. Плюс расчет хэшей.
Вариант хрупкий - манипуляции со старшими битами указателей, чтобы помечать, что блок уже освобожден. Минус масштабирование - что, если нужны все биты указателя? Ну, к примеру - сервер с кучей терабайт и эти терабайты задействованы полностью? Риск случайного затирания весьма велик.
Определив, что указатель уже был недавно освобожден, возможны два варианта поведения. Первый - замести под ковер. Просто молча сглотнуть указатель и больше его во фрилист не добавлять. Плохо, потому что это скрытый 0-day. Который неизбежно найдут и используют, а вы даже знать об этом не будете. Второй - плюнуть сегфолтом в приложение. Вариант неплох, вы сразу получите стектрейс с указанием, где примерно в коде приложения был DF.
Однако накладные расходы на защиту будут ужасные. Все это происходит в горячих путях и жрет - с учетом интенсивности malloc/free - процессорные циклы как не в себя.
Нативная защита на уровне аллокатора возможна. Ну, что считать защитой - проглатывать повторные освобождения опасно для здоровья, кидаться сегфолтами можно и нужно - и только так должен вести себя православный аллокатор. Мы лишь хотим, чтобы стектрейс нам прямо указывал на место в коде, где затаился double-free.
Что это означает на практике? На практике это означает, что нам всего-то навсего архитектурно нужна очень жесткая reuse policy. То есть, free() должно означать "немедленный free, блок сразу же, через наносекунду, попадает во фрилист и будет переиспользован". В этом случае молниеносно происходит смена владения и аллокатор, обнаружив, что кто-то уже трогает память, которая была освобождена и переиспользована, незамедлительно кинет сегфолт. Что, по цепочке, приведет к образованию внятного стектрейса приложения (не бэкэнда, не компонентов ядра ОС), с free() на вершине стека.
Одна маленькая проблемка. Ни один из существующих аллокаторов так не реализован.
То есть - нативной защиты не существует. И, вообще говоря, это означает, что все ходят по краю пропасти.
Нет, Rust не спасёт и не сохранит. Нет, статический анализ не обязан видеть DF.
Единственная, по сути, защита - это строгая дисциплина программирования - всегда зануляйте указатели после освобождения памяти - и жесткая reuse policy аллокаторов. Которая - единственная - при обнаружении DF немедленно уронит приложение, а не закопает ошибку владения под ковер.
Corner cases и стандарты
О бедном reallocarray() замолвите слово.
Спустя 30 лет, неожиданно оказалось, что произведения elems * size (двух беззнаковых целых типа size_t) недостаточно и нужно проверять на переполнение еще и экзотический вариант realloc, в котором тоже может быть переполнение произведения беззнаковых целых.
Вообще говоря, wrap around беззнаковых целых не редкость при безалаберном программировании.
Но давайте говорить честно - если у вас в вызов функции аллокации прилетели слишком большие сомножители, приводящие прямо к этому самому wrap around - то проблемы у вас посерьезнее, чем проверка входящих данных непосредственно в этой самой функции аллокации.
Это определенно не тот слой, где следует выполнять тяжеловесные проверки на переполнение в горячем пути (а там тяжелое деление неконстантных значений).
Собственно, это одна из причин, по которой POSIX неохотно согласились включить такую проверку в calloc() (calloc при переполнении warp around, до выполнения аллокации, возвращает NULL) и отказались включать reallocarray() в стандарт.
Мотивация появления reallocarray() вообще в высшей степени мутная. "Если внезапно понадобится резко выполнить сверхкрупную реаллокацию...". Что значит "Внезапно?" Внезапно захотели из килобайта получить терабайт? Из-под камня вылез wrap around и закорраптил кучу? Вы не проверяете входящие значения?
Не то, чтобы size_t было достаточно для любого. Но сам по себе корнер кейс исчезающе редкий. Да и не должен быть аллокатор нянькой для программиста.
Еще раз: аллокатор не нянька. Он не должен быть обложен подушками со всех без исключения сторон и охватывать все мыслимые и немыслимые корнер кейсы.
Если программист не знает, что может произойти при переполнении выражения с двумя беззнаковыми целыми - а это аппаратное поведение процессоров - может, ему стоит подумать о смене профессии?
То же самое относится к классическому realloc. Стандартное поведение: если size = 0, то память по указателю освобождается и указатель зануляется. Если программист не подумал о таком корнер кейсе и просто написал
realloc() штука небезопасная, такое поведение описано в стандарте, это, по сути, контракт. Обвязка для проверок входных данных на корректность и для сохранения данных по указателю в корнер кейсах, если необходимо продолжить обработку в такой ситуации - это прерогатива программиста. Аллокатор не нянька, он работает в соответствие со стандартом. Передал нулевой размер - получил free(p) и p = NULL.
Между тем таким случаям просто несть числа.
NB: статические анализаторы могут поймать realloc(p, 0). А могут и не поймать.
Anyway, границы слоев проверок и защит от дурака постепенно размываются. И незаметно плывут в сторону рукосуев. Как слово "кофе" плавно стало среднего рода. Ценой - разумеется - увеличения накладных расходов. А что такого-то, процессор железный, он все перемолотит.
Это неправильный подход. Не случайно POSIX послали reallocarray() в сад, а рукосуи правдами и неправдами пытаются его зафиксировать как стандарт де-факто, пропихивая в libC/glibC изо всех сил.
Хотите вручную управлять памятью - пожалуйста, но перечитайте, пожалуйста, стандарт и не делайте допущений, что в implementation details будут подложены все и всякие подушки и подушечки на случай дефективной прокладки между сиденьем и клавиатурой.
PS. Если что-то ходит, как костыль, бегает, как костыль, крякает как костыль и выглядит, как костыль - то это и есть костыль.
О бедном reallocarray() замолвите слово.
Спустя 30 лет, неожиданно оказалось, что произведения elems * size (двух беззнаковых целых типа size_t) недостаточно и нужно проверять на переполнение еще и экзотический вариант realloc, в котором тоже может быть переполнение произведения беззнаковых целых.
Вообще говоря, wrap around беззнаковых целых не редкость при безалаберном программировании.
Но давайте говорить честно - если у вас в вызов функции аллокации прилетели слишком большие сомножители, приводящие прямо к этому самому wrap around - то проблемы у вас посерьезнее, чем проверка входящих данных непосредственно в этой самой функции аллокации.
Это определенно не тот слой, где следует выполнять тяжеловесные проверки на переполнение в горячем пути (а там тяжелое деление неконстантных значений).
Собственно, это одна из причин, по которой POSIX неохотно согласились включить такую проверку в calloc() (calloc при переполнении warp around, до выполнения аллокации, возвращает NULL) и отказались включать reallocarray() в стандарт.
Мотивация появления reallocarray() вообще в высшей степени мутная. "Если внезапно понадобится резко выполнить сверхкрупную реаллокацию...". Что значит "Внезапно?" Внезапно захотели из килобайта получить терабайт? Из-под камня вылез wrap around и закорраптил кучу? Вы не проверяете входящие значения?
Не то, чтобы size_t было достаточно для любого. Но сам по себе корнер кейс исчезающе редкий. Да и не должен быть аллокатор нянькой для программиста.
Еще раз: аллокатор не нянька. Он не должен быть обложен подушками со всех без исключения сторон и охватывать все мыслимые и немыслимые корнер кейсы.
Если программист не знает, что может произойти при переполнении выражения с двумя беззнаковыми целыми - а это аппаратное поведение процессоров - может, ему стоит подумать о смене профессии?
То же самое относится к классическому realloc. Стандартное поведение: если size = 0, то память по указателю освобождается и указатель зануляется. Если программист не подумал о таком корнер кейсе и просто написал
ptr = realloc(ptr, size) и в результате потерял данные после ошибочного поступления нулевого size - то это, вообще-то говоря, его проблема.realloc() штука небезопасная, такое поведение описано в стандарте, это, по сути, контракт. Обвязка для проверок входных данных на корректность и для сохранения данных по указателю в корнер кейсах, если необходимо продолжить обработку в такой ситуации - это прерогатива программиста. Аллокатор не нянька, он работает в соответствие со стандартом. Передал нулевой размер - получил free(p) и p = NULL.
Между тем таким случаям просто несть числа.
NB: статические анализаторы могут поймать realloc(p, 0). А могут и не поймать.
Anyway, границы слоев проверок и защит от дурака постепенно размываются. И незаметно плывут в сторону рукосуев. Как слово "кофе" плавно стало среднего рода. Ценой - разумеется - увеличения накладных расходов. А что такого-то, процессор железный, он все перемолотит.
Это неправильный подход. Не случайно POSIX послали reallocarray() в сад, а рукосуи правдами и неправдами пытаются его зафиксировать как стандарт де-факто, пропихивая в libC/glibC изо всех сил.
Хотите вручную управлять памятью - пожалуйста, но перечитайте, пожалуйста, стандарт и не делайте допущений, что в implementation details будут подложены все и всякие подушки и подушечки на случай дефективной прокладки между сиденьем и клавиатурой.
PS. Если что-то ходит, как костыль, бегает, как костыль, крякает как костыль и выглядит, как костыль - то это и есть костыль.
Диагностика и оптимизация производительности
В оптимизации производительности диагностика - экзистенциальная и крайне плохо формализуемая проблема.
Та причина, по которой за 30 с лишним лет никому - а усилия были достойны всяческого уважения - так и не удалось не то, что автоматизировать тюнинг - а хотя бы добиться получения надежной и однозначной диагностики.
Если начать от частного к общему, то в двух словах проблема звучит так - top это не тот инструмент, который сходу определит бутылочное горлышко (bottleneck).
Мало того, что ботлнек часто вовсе не там, где его показывают мониторинги, а сплошные логи терабайтами не только не позволяют годами (!) определить проблему и хотя бы понять, что происходит под капотом сложной системы, а лишь создают ненужный шум и тратят уйму ресурсов.
Ботлнек либо невозможно четко определить, либо невозможно легко - либо хоть как-то - исправить.
При этом простое понимание факта, что в системе присутствует проблема, связанная с производительностью, требует одновременно двух взаимоисключающих вещей: глобального видения, начиная от глобальной же архитектуры - и внимания к деталям, к тем мелочам, которые, как правило, просто игнорируются как незначимые.
Никакая автоматизированная система этими свойствами не обладает и обладать не может. Именно это объясняет гомерические провалы, в частности, попыток Oracle создать автотюнер. Ни решение на базе экспертной системы (Oracle Expert; на минуточку, 1998 год) с базой данных и базой правил, ни последующие поползновения Diagnostics/Tuning Pack, ни любые другие шаблонные и формализованные решения к успеху не привели и маловероятно, что приведут. А ведь здесь речь идет о достаточно простой, в общем-то, вещи - реляционной базе данных, всего-то навсего. У которой, как оказалось, существует окружение - ОС, железо, сбалансированные и не очень конфигурации, многочисленные ошибки архитекторов, программистов и сисадминов... Тот огромный и, как оказывается, значимый контекст, который невозможно описать на двух страничках А4 языком популярных телепередач.
Проблема осложняется тем, что действительно полезные диагностические инструменты либо неизвестны широкой публике, либо их применение на продах осложнено необходимостью установки кучи вспомогательного софта и данных, что, как правило, категорически неприемлемо.
Нативно встроенные в систему инструменты - как и сами такие системы - находятся вне тренда, по целому ряду причин нетехнического характера, и даже в лучшие времена использовались в единичных случаях. Попытки повторить dtrace провалились просто в силу монструозности и крайнего неудобства вновь созданных инструментов. Системы, которые смогли - предельно маргинализированы и не применяются в видимой части рынка.
Простой пример - обнаружение lock contention в современных системах это задача уровня сложности "Неразрешимая". То, что играючи выполняется средствами lockstat или dtrace, практически нереально выполнить без кучи подготовительных плясок с трудновоспроизводимым результатом.
Рынок, однако, сделал свой выбор. Верхнеуровневые средства + интуиция - вот то, что осталось. Техношаманство как система.
Глубокая диагностика подменена совершенно неэквивалентным понятием обсервабилити. В тщетной надежде, будто бы избыточный мониторинг в состоянии точно указать проблемные места, которые можно исправить и устранить на бегу, в рамках девопс-методологии.
Между тем, аксиома "Оптимизация производительности - требует прежде всего глубокого понимания архитектуры" никуда не делась. И диагностика - это фундамент любой оптимизации. Которая в начале разработки преждевременная, а потом невозможная.
В оптимизации производительности диагностика - экзистенциальная и крайне плохо формализуемая проблема.
Та причина, по которой за 30 с лишним лет никому - а усилия были достойны всяческого уважения - так и не удалось не то, что автоматизировать тюнинг - а хотя бы добиться получения надежной и однозначной диагностики.
Если начать от частного к общему, то в двух словах проблема звучит так - top это не тот инструмент, который сходу определит бутылочное горлышко (bottleneck).
Мало того, что ботлнек часто вовсе не там, где его показывают мониторинги, а сплошные логи терабайтами не только не позволяют годами (!) определить проблему и хотя бы понять, что происходит под капотом сложной системы, а лишь создают ненужный шум и тратят уйму ресурсов.
Ботлнек либо невозможно четко определить, либо невозможно легко - либо хоть как-то - исправить.
При этом простое понимание факта, что в системе присутствует проблема, связанная с производительностью, требует одновременно двух взаимоисключающих вещей: глобального видения, начиная от глобальной же архитектуры - и внимания к деталям, к тем мелочам, которые, как правило, просто игнорируются как незначимые.
Никакая автоматизированная система этими свойствами не обладает и обладать не может. Именно это объясняет гомерические провалы, в частности, попыток Oracle создать автотюнер. Ни решение на базе экспертной системы (Oracle Expert; на минуточку, 1998 год) с базой данных и базой правил, ни последующие поползновения Diagnostics/Tuning Pack, ни любые другие шаблонные и формализованные решения к успеху не привели и маловероятно, что приведут. А ведь здесь речь идет о достаточно простой, в общем-то, вещи - реляционной базе данных, всего-то навсего. У которой, как оказалось, существует окружение - ОС, железо, сбалансированные и не очень конфигурации, многочисленные ошибки архитекторов, программистов и сисадминов... Тот огромный и, как оказывается, значимый контекст, который невозможно описать на двух страничках А4 языком популярных телепередач.
Проблема осложняется тем, что действительно полезные диагностические инструменты либо неизвестны широкой публике, либо их применение на продах осложнено необходимостью установки кучи вспомогательного софта и данных, что, как правило, категорически неприемлемо.
Нативно встроенные в систему инструменты - как и сами такие системы - находятся вне тренда, по целому ряду причин нетехнического характера, и даже в лучшие времена использовались в единичных случаях. Попытки повторить dtrace провалились просто в силу монструозности и крайнего неудобства вновь созданных инструментов. Системы, которые смогли - предельно маргинализированы и не применяются в видимой части рынка.
Простой пример - обнаружение lock contention в современных системах это задача уровня сложности "Неразрешимая". То, что играючи выполняется средствами lockstat или dtrace, практически нереально выполнить без кучи подготовительных плясок с трудновоспроизводимым результатом.
Рынок, однако, сделал свой выбор. Верхнеуровневые средства + интуиция - вот то, что осталось. Техношаманство как система.
Глубокая диагностика подменена совершенно неэквивалентным понятием обсервабилити. В тщетной надежде, будто бы избыточный мониторинг в состоянии точно указать проблемные места, которые можно исправить и устранить на бегу, в рамках девопс-методологии.
Между тем, аксиома "Оптимизация производительности - требует прежде всего глубокого понимания архитектуры" никуда не делась. И диагностика - это фундамент любой оптимизации. Которая в начале разработки преждевременная, а потом невозможная.
RDBMS != InMemory database
Эта прописная истина не доходит до DBA с тех самых пор, как реляционные БД пихают где надо и где не надо, во все места и при этом скорость хоть сколько-нибудь критична.
Реляционные БД - это не InMemory БД. Это аксиома. Для RDBMS нормально иметь постоянный IO со сториджем, и, следовательно, 99% cache hit ratio это абсолютно нездоровая метрика.
Почему?
По очевидным причинам.
OLTP это постоянно идущие транзакции. Записи на диск - в блоки данных и логи и чекпойнты. Такие данные, которые движутся в одну сторону, кэшировать бессмысленно - это просто впустую занимать оперативную память. Изменили - записали - выполнили чекпойнт - покинули кэш. Лишь в случаях повторного чтения кэш уменьшит лейтенси; причем, с учетом того факта, что мы говорим об OLTP - объем записей маленький, чтение со сториджа, который не сатурирован, происходит быстро. Нет, это не рандомное чтение - слой кэша файловой системы плюс упреждающая выборка на уровне ОС - они существуют - скомпенсируют сторидж (разумеется, грамотно построенный и сконфигурированный). Запись при OLTP преимущественно последовательная.
DWH/OLAP - тоже выполняют IO. И тоже в одну сторону. Чтение фактовых таблиц большого размера в ad hoc запросах - это дорога в одну сторону, загрузили, обработали, освободили кэш.
Это ожидаемое поведение.
Попытки целиком закэшировать реляционную БД в надежде достичь 99% cache hit на практике приводят к чрезмерному раздуванию кэша с последующей дикой внутренней фрагментацией и падению скорости. Приходилось видеть совершенно копеечные реляционные БД с кэшем размером 1 Тб (!) и непонятным замедлением и рандомными скачками лейтенси.
Нормальными показателями cache hit ratio для подавляющего большинства активных реляционных БД любого типа является величина 80-90%. Максимум.
При условии, что время отклика запросов находится в пределах бейслайна (baseline).
Стремление загнать все таблицы и индексы в кэш для реляционных баз порочно по определению и никогда не приводит к ожидаемому результату.
Почему этот миф оказался настолько живучим?
Если не вникать во внутреннюю архитектуру и происходящие в реляционных базах процессы, то существует распространенное заблуждение, проистекающее из насаждаемых вендорами оценок capacity, будто бы больше памяти = всегда лучше. Памятью базу не испортишь.
Так вот, это не более, чем заблуждение.
Чем скорее вы от него сумеете избавиться - тем больше оперативной памяти не будет израсходовано впустую и тем меньше ненужных усилий потратит DBA в ошибочных попытках оптимизации производительности.
PS. Игнорирование нижележащих абстракций всегда ведет к заблуждениям при тюнинге. В оптимизации дьявол в деталях и необходимо учитывать их все. К слову, случаи direct mount относительно редки, но даже там попытки кэшировать базу целиком добром не заканчиваются. Базы тоже выполняют read ahead и write behind. Отнюдь не по одному блоку.
Эта прописная истина не доходит до DBA с тех самых пор, как реляционные БД пихают где надо и где не надо, во все места и при этом скорость хоть сколько-нибудь критична.
Реляционные БД - это не InMemory БД. Это аксиома. Для RDBMS нормально иметь постоянный IO со сториджем, и, следовательно, 99% cache hit ratio это абсолютно нездоровая метрика.
Почему?
По очевидным причинам.
OLTP это постоянно идущие транзакции. Записи на диск - в блоки данных и логи и чекпойнты. Такие данные, которые движутся в одну сторону, кэшировать бессмысленно - это просто впустую занимать оперативную память. Изменили - записали - выполнили чекпойнт - покинули кэш. Лишь в случаях повторного чтения кэш уменьшит лейтенси; причем, с учетом того факта, что мы говорим об OLTP - объем записей маленький, чтение со сториджа, который не сатурирован, происходит быстро. Нет, это не рандомное чтение - слой кэша файловой системы плюс упреждающая выборка на уровне ОС - они существуют - скомпенсируют сторидж (разумеется, грамотно построенный и сконфигурированный). Запись при OLTP преимущественно последовательная.
DWH/OLAP - тоже выполняют IO. И тоже в одну сторону. Чтение фактовых таблиц большого размера в ad hoc запросах - это дорога в одну сторону, загрузили, обработали, освободили кэш.
Это ожидаемое поведение.
Попытки целиком закэшировать реляционную БД в надежде достичь 99% cache hit на практике приводят к чрезмерному раздуванию кэша с последующей дикой внутренней фрагментацией и падению скорости. Приходилось видеть совершенно копеечные реляционные БД с кэшем размером 1 Тб (!) и непонятным замедлением и рандомными скачками лейтенси.
Нормальными показателями cache hit ratio для подавляющего большинства активных реляционных БД любого типа является величина 80-90%. Максимум.
При условии, что время отклика запросов находится в пределах бейслайна (baseline).
Стремление загнать все таблицы и индексы в кэш для реляционных баз порочно по определению и никогда не приводит к ожидаемому результату.
Почему этот миф оказался настолько живучим?
Если не вникать во внутреннюю архитектуру и происходящие в реляционных базах процессы, то существует распространенное заблуждение, проистекающее из насаждаемых вендорами оценок capacity, будто бы больше памяти = всегда лучше. Памятью базу не испортишь.
Так вот, это не более, чем заблуждение.
Чем скорее вы от него сумеете избавиться - тем больше оперативной памяти не будет израсходовано впустую и тем меньше ненужных усилий потратит DBA в ошибочных попытках оптимизации производительности.
PS. Игнорирование нижележащих абстракций всегда ведет к заблуждениям при тюнинге. В оптимизации дьявол в деталях и необходимо учитывать их все. К слову, случаи direct mount относительно редки, но даже там попытки кэшировать базу целиком добром не заканчиваются. Базы тоже выполняют read ahead и write behind. Отнюдь не по одному блоку.
Кэш и Большое О
Каким боком вообще связаны кэши (любые) и асимптотика алгоритмов, если две самые большие проблемы в ИТ - это нейминг переменных и инвалидация кэшей?
Самым прямым образом.
Инвалидация и TTL кэша не самые значимые факторы, влияющие на cache hit ratio.
Фактор, который упускается из виду всеми без исключения капаситорами, и который впрямую влияет на невозможность линейного масштабирования кэша через его безграничное наращивание - это лукапы (lookups).
Сюрприз.
Кэш, оказывается, имеет структуры, посредством которых осуществляется поиск и извлечение данных.
Ассоциативные массивы, деревья всех цветов - кстати, хэши не в воздухе висят, а тоже собраны в деревья как правило, да просто обычные плоские массивы, наконец. Да, с асимптотикой O(n). Алгоритмов поиска с честным O(1) - не амортизированным, а честным - среди них, в общем-то, не 100%. Нет, обходы деревьев не бесплатны. Нет, там не O(1) в поиске.
Именно этот факт, помимо фрагментации памяти, является причиной, что кривая зависимости hit ratio и - в особенности - скорости доступа к данным в кэше - является кривой с перегибом, а вовсе не прямой линией с коэффициентом.
Реляционные БД - которые довольно часто используют в качестве кэшей, кстати говоря - имеют одну структуру с поиском амортизированное O(1). Это сбалансированные B-деревья. Используемые в индексах. Имеющие конечное число уровней и до определенных - весьма больших - пределов выполняют лукапы с константной скоростью.
Внимание, вопрос.
Какие кэши, из существующих в природе, используют эту структуру для доступа?
Вопрос риторический. "Мы не вникали".
Если говорить глобально, практически все и любые кэши имеют стеклянный потолок, выше которого данные проще подтащить извне, даже с HDD, нежели разыскать в гигантском кэше в оперативной памяти.
Не обязательно, кстати говоря, в оперативной. К процессорным кэшам это относится в равной степени. Которые, в числе прочих факторов, напрямую влияют на скорости доступа к кэшам в оперативной памяти.
Метаданные растут вместе с данными. Этой памяти надо коснуться, ее надо прокачать - частично или полностью - через процессоры. Инвалидировать при этом процессорные кэши. Совершить массу других движений. А память кэша фрагментируется, причем чем она больше - тем быстрее идет фрагментация. Плюс cache replacement. Плюс разный TTL. Чем кэш крупнее и чем больше данных оттуда одновременно извлекается - тем весь этот оверхэд выше. Тем дольше идут эти процессы - физику не обманешь.
Все вышесказанное означает инженерные компромиссы, которые приходится учитывать при вертикальном масштабировании.
К слову, горизонтальное масштабирование тут не является волшебной пулей, по очевидным причинам, подобным закону Амдаля-Уэра. Оно отягощено экспоненциальным ростом накладных расходов на координацию и обслуживание распределенных структур. Помимо того, что для хилых узлов тоже действуют вышеописанные ограничения и процессы.
Таким образом, реальный мир довольно сильно отличается от представлений капаситоров об этом самом реальном мире.
И оптимизация производительности, подобно ИБ, является не продуктом, а процессом.
Что это означает на практике?
Данные растут, как снежный ком, кэши безгранично наращивать бессмысленно, cache hit ratio не ключевая метрика, масштабирование - нетривиальная задача и ее нужно решать в комплексе, начиная с архитектуры и, самое главное - с понимания того, как функционируют системы на всех уровнях.
PS. Кстати, как вы думаете - зачем в статистике Redis метрики фрагментации памяти?
Каким боком вообще связаны кэши (любые) и асимптотика алгоритмов, если две самые большие проблемы в ИТ - это нейминг переменных и инвалидация кэшей?
Самым прямым образом.
Инвалидация и TTL кэша не самые значимые факторы, влияющие на cache hit ratio.
Фактор, который упускается из виду всеми без исключения капаситорами, и который впрямую влияет на невозможность линейного масштабирования кэша через его безграничное наращивание - это лукапы (lookups).
Сюрприз.
Кэш, оказывается, имеет структуры, посредством которых осуществляется поиск и извлечение данных.
Ассоциативные массивы, деревья всех цветов - кстати, хэши не в воздухе висят, а тоже собраны в деревья как правило, да просто обычные плоские массивы, наконец. Да, с асимптотикой O(n). Алгоритмов поиска с честным O(1) - не амортизированным, а честным - среди них, в общем-то, не 100%. Нет, обходы деревьев не бесплатны. Нет, там не O(1) в поиске.
Именно этот факт, помимо фрагментации памяти, является причиной, что кривая зависимости hit ratio и - в особенности - скорости доступа к данным в кэше - является кривой с перегибом, а вовсе не прямой линией с коэффициентом.
Реляционные БД - которые довольно часто используют в качестве кэшей, кстати говоря - имеют одну структуру с поиском амортизированное O(1). Это сбалансированные B-деревья. Используемые в индексах. Имеющие конечное число уровней и до определенных - весьма больших - пределов выполняют лукапы с константной скоростью.
Внимание, вопрос.
Какие кэши, из существующих в природе, используют эту структуру для доступа?
Вопрос риторический. "Мы не вникали".
Если говорить глобально, практически все и любые кэши имеют стеклянный потолок, выше которого данные проще подтащить извне, даже с HDD, нежели разыскать в гигантском кэше в оперативной памяти.
Не обязательно, кстати говоря, в оперативной. К процессорным кэшам это относится в равной степени. Которые, в числе прочих факторов, напрямую влияют на скорости доступа к кэшам в оперативной памяти.
Метаданные растут вместе с данными. Этой памяти надо коснуться, ее надо прокачать - частично или полностью - через процессоры. Инвалидировать при этом процессорные кэши. Совершить массу других движений. А память кэша фрагментируется, причем чем она больше - тем быстрее идет фрагментация. Плюс cache replacement. Плюс разный TTL. Чем кэш крупнее и чем больше данных оттуда одновременно извлекается - тем весь этот оверхэд выше. Тем дольше идут эти процессы - физику не обманешь.
Все вышесказанное означает инженерные компромиссы, которые приходится учитывать при вертикальном масштабировании.
К слову, горизонтальное масштабирование тут не является волшебной пулей, по очевидным причинам, подобным закону Амдаля-Уэра. Оно отягощено экспоненциальным ростом накладных расходов на координацию и обслуживание распределенных структур. Помимо того, что для хилых узлов тоже действуют вышеописанные ограничения и процессы.
Таким образом, реальный мир довольно сильно отличается от представлений капаситоров об этом самом реальном мире.
И оптимизация производительности, подобно ИБ, является не продуктом, а процессом.
Что это означает на практике?
Данные растут, как снежный ком, кэши безгранично наращивать бессмысленно, cache hit ratio не ключевая метрика, масштабирование - нетривиальная задача и ее нужно решать в комплексе, начиная с архитектуры и, самое главное - с понимания того, как функционируют системы на всех уровнях.
PS. Кстати, как вы думаете - зачем в статистике Redis метрики фрагментации памяти?
allocator_frag_ratio, allocator_frag_bytes, mem_fragmentation_ratio, mem_fragmentation_bytes)) Ну и стоит всегда помнить, что кэш может быть большим, а процессор маленький. Поэтому маэстро следует урезать осетра.Линия жизни
Проблема DF (double free)/UAF (use-after-free) в действительности глубже, чем может показаться.
Причем эта кроличья нора мало того, что бездонная - она тщательно замаскирована и угодить в нее можно буквально где угодно и почти на каждом шагу.
Она не очень точно называется владением памятью, более точно назвать ее проблемой висящих указателей (dangling pointers), что, в свою очередь, тоже не совсем точно.
Если объяснять совсем на пальцах, в языках с ручным управлением памятью, память - разумеется - не может знать, сколько на нее смотрит указателей из разных мест кода. Сырые указатели штука тупая и циничная. Это просто адрес ячейки или блока.
Считать указатели в обертках (
Проблема усугубляется тем фактом, что в том же C++ на сырых указателях под капотом много чего строится - наследование, полиморфизм, vtable - и заменить всё это на умные указатели (которые тоже вовсе не панацея) или на ссылки не получится по определению, совместимость и гигатонны работающего кода. Что касается Си, то там указатели буквально фундамент всей и всяческой алгоритмики.
Суть проблемы, однако же, даже не в этом. А в том, что нижележащий слой - libC, системные и мажорные аллокаторы - проблему прячут и прячут глубоко в своем бэкэнде.
Теоретически аллокатор должен предоставлять один железный контракт - после free() память считается не твоей, всё, забудь о ней. Сразу же, незамедлительно, как только произошел возврат из free(). И правильно занулить указатель, потому что повторный free(NULL) - по POSIX - не бросит исключения или сегфолта и просто молча ничего не выполнит. Это не абсолютная защита, но хотя бы кое-что.
На практике освобожденный блок может достаточно долго болтаться в бэкэнде аллокатора и любые другие указатели (о которых никто, кроме приложения, не знает и знать не может) позволяют видеть эту память. Кардинально менять архитектуру аллокаторов никто не станет, и плевать на контракты - тут так принято. Исторически сложилось.
Так DF плавно превращается в UAF, что уже значительно хуже. Представили, да, извлечение приватных данных из памяти?
Так что АНБ напрасно мутит воду с безопасными языками программирования. Во-первых, никто не станет переписывать эти самые гигатонны работающего кода. Во-вторых, кто посмеет хоть пальцем тронуть системные аллокаторы?
Снова и снова - никакие костыльные защиты не спасают. Они либо чрезвычайно дороги в плане оверхеда, либо фрагментарны, либо бесполезны.
Архитектуру приложений переделывать очень дорого по времени, деньгам и когнитивной сложности. Обнаружить висящие указатели непросто даже бригаде сеньоров с микроскопами, по коду надо буквально ползать, выверяя владение, указатели, логику освобождения.
Статический анализ малоэффективен. Санитайзеры очень тяжеловесны (а чего вы ожидали?) и нацелены, в общем, на другое.
В целом, резюме очень малоутешительное. Нужно либо дьявольски тщательно и качественно код писать (что на практике является ненаучной фантастикой), либо заменять системные и иже с ними аллокаторы на архитектурно другие, с жесточайшим соблюдением контракта освобождения.
С тем, чтобы приложение, в случае DF/UAF, немедленно грохнулось в дамп, и чтобы в дампе на стеке было то самое место, где DF/UAF произошел.
Помимо того, что разработка аллокатора общего назначения сама по себе чрезвычайно нетривиальная задача, нужно еще принять волевое решение о внедрении, с тем, что отныне ошибки памяти такого класса не закапываются под ковер, а вытаскиваются на свет божий с целью незамедлительного исправления.
По очевидной причине, которую все понимают - такие ошибки это буквально приглашение к RCE. Ведь понимают? Ведь правда?
Проблема DF (double free)/UAF (use-after-free) в действительности глубже, чем может показаться.
Причем эта кроличья нора мало того, что бездонная - она тщательно замаскирована и угодить в нее можно буквально где угодно и почти на каждом шагу.
Она не очень точно называется владением памятью, более точно назвать ее проблемой висящих указателей (dangling pointers), что, в свою очередь, тоже не совсем точно.
Если объяснять совсем на пальцах, в языках с ручным управлением памятью, память - разумеется - не может знать, сколько на нее смотрит указателей из разных мест кода. Сырые указатели штука тупая и циничная. Это просто адрес ячейки или блока.
Считать указатели в обертках (
shared_ptr) накладно и в горячих путях дорого. Счетчики, блокировки. Наворачивать слои безопасности при работе с памятью - чрезвычайно дорого.Проблема усугубляется тем фактом, что в том же C++ на сырых указателях под капотом много чего строится - наследование, полиморфизм, vtable - и заменить всё это на умные указатели (которые тоже вовсе не панацея) или на ссылки не получится по определению, совместимость и гигатонны работающего кода. Что касается Си, то там указатели буквально фундамент всей и всяческой алгоритмики.
Суть проблемы, однако же, даже не в этом. А в том, что нижележащий слой - libC, системные и мажорные аллокаторы - проблему прячут и прячут глубоко в своем бэкэнде.
Теоретически аллокатор должен предоставлять один железный контракт - после free() память считается не твоей, всё, забудь о ней. Сразу же, незамедлительно, как только произошел возврат из free(). И правильно занулить указатель, потому что повторный free(NULL) - по POSIX - не бросит исключения или сегфолта и просто молча ничего не выполнит. Это не абсолютная защита, но хотя бы кое-что.
На практике освобожденный блок может достаточно долго болтаться в бэкэнде аллокатора и любые другие указатели (о которых никто, кроме приложения, не знает и знать не может) позволяют видеть эту память. Кардинально менять архитектуру аллокаторов никто не станет, и плевать на контракты - тут так принято. Исторически сложилось.
Так DF плавно превращается в UAF, что уже значительно хуже. Представили, да, извлечение приватных данных из памяти?
Так что АНБ напрасно мутит воду с безопасными языками программирования. Во-первых, никто не станет переписывать эти самые гигатонны работающего кода. Во-вторых, кто посмеет хоть пальцем тронуть системные аллокаторы?
Снова и снова - никакие костыльные защиты не спасают. Они либо чрезвычайно дороги в плане оверхеда, либо фрагментарны, либо бесполезны.
Архитектуру приложений переделывать очень дорого по времени, деньгам и когнитивной сложности. Обнаружить висящие указатели непросто даже бригаде сеньоров с микроскопами, по коду надо буквально ползать, выверяя владение, указатели, логику освобождения.
Статический анализ малоэффективен. Санитайзеры очень тяжеловесны (а чего вы ожидали?) и нацелены, в общем, на другое.
В целом, резюме очень малоутешительное. Нужно либо дьявольски тщательно и качественно код писать (что на практике является ненаучной фантастикой), либо заменять системные и иже с ними аллокаторы на архитектурно другие, с жесточайшим соблюдением контракта освобождения.
С тем, чтобы приложение, в случае DF/UAF, немедленно грохнулось в дамп, и чтобы в дампе на стеке было то самое место, где DF/UAF произошел.
Помимо того, что разработка аллокатора общего назначения сама по себе чрезвычайно нетривиальная задача, нужно еще принять волевое решение о внедрении, с тем, что отныне ошибки памяти такого класса не закапываются под ковер, а вытаскиваются на свет божий с целью незамедлительного исправления.
По очевидной причине, которую все понимают - такие ошибки это буквально приглашение к RCE. Ведь понимают? Ведь правда?
Самая Быстрая Рука на Диком Западе
Кошмар любого перфоманс инженера - приложение, зависящее от таймингов.
Например, щедро усеянное внутри вызовами nanosleep() и ему подобными. Есть и гораздо худшие варианты. Популярные ныне асинхронные приложения на коллбэках. Которые в той или иной степени при выполнении логики ориентируются не на события, а на время. Или содержащие логические ошибки - от которых никто не застрахован.
Неприятное во всем этом то, что никакие тестирования в контролируемых условиях найти такие места не способны физически. К вящему огорчению команд тестировщиков всех видов. Ни юнит-тесты, ни регрессионные, ни даже нагрузочные тесты найти все подобные места не могут.
"У меня всё работает!" - знакомая фраза.
По факту, чтобы выловить подобные проблемы - нужно многолетнее тестирование на продакшенах. Причем любое изменение - даже не оптимизация производительности, которая, ко всему, имеет разное влияние на разные части алгоритмов - а даже простая замена процессора на более быстрый или просто имеющий другую внутреннюю архитектуру - может вызвать к жизни все, что угодно, вплоть до UB. Изменились тайминги - разные участки кода стали завершаться в разные моменты времени.
Формально корректный алгоритм, проходящий все и любые статические анализаторы, в чуть изменившихся условиях начинает бабахать сегфолтами.
Как реагирует бизнес и разработка на такие события?
Либо костыльный патч, либо воркэраунд с частичным или полным откатом условий к стабильному поведению.
Третьего по факту не дано.
В чем вообще проблема? Обычно она архитектурная, причем зачастую размазана тонким слоем по куче мест. Чрезвычайно трудно локализуемая. Очень трудная к реальному исправлению.
Нужно перелопатить кучу кода, изменить архитектуру - точечно или площадями, найти и пофиксить.
Это та самая категория гейзенбагов, которая вынуждает откатывать самые лучшие решения в пользу сильно менее лучших.
Зачастую подобные проблемы вылезают именно тогда, когда их никто не ожидает. Алгоритм годами работал прекрасно, но вдруг, в какой-то момент, после изменения какой-либо части окружения - начинает ломаться.
Что можно сделать в данном случае перфоманс инженеру, который сталкивается с подобным?
А ничего. Откатить изменения и отойти в сторону.
Задача в рамках существующих начальных условий практически нерешаема. Доказать наличие архитектурных проблем разработчикам невозможно. Исправление может обойтись страшно дорого и ужасно больно. И сломать совместимость.
Альтернативы много хуже. Нужно вести длительное полнофункциональное тестирование в рамках различных внешних условий. Разумеется, охватить все варианты невозможно. Разумеется, никто не будет тратить на это время, фактически проводя тестовые развертывания и статистические методы оценки результата. Сломалось у 1%? Ну и ладно, не больно-то и хотелось.
Тоже очень узнаваемо, да? Обновления Windows. Здесь работает, здесь не работает, а здесь рыбу заворачивали.
Finally. Непопулярный ныне инженерный подход к вдумчивому и тщательному проектированию и реализации. Как и всегда. Другого пути - не победить, а хотя бы снизить вероятность - просто не существует.
Кошмар любого перфоманс инженера - приложение, зависящее от таймингов.
Например, щедро усеянное внутри вызовами nanosleep() и ему подобными. Есть и гораздо худшие варианты. Популярные ныне асинхронные приложения на коллбэках. Которые в той или иной степени при выполнении логики ориентируются не на события, а на время. Или содержащие логические ошибки - от которых никто не застрахован.
Неприятное во всем этом то, что никакие тестирования в контролируемых условиях найти такие места не способны физически. К вящему огорчению команд тестировщиков всех видов. Ни юнит-тесты, ни регрессионные, ни даже нагрузочные тесты найти все подобные места не могут.
"У меня всё работает!" - знакомая фраза.
По факту, чтобы выловить подобные проблемы - нужно многолетнее тестирование на продакшенах. Причем любое изменение - даже не оптимизация производительности, которая, ко всему, имеет разное влияние на разные части алгоритмов - а даже простая замена процессора на более быстрый или просто имеющий другую внутреннюю архитектуру - может вызвать к жизни все, что угодно, вплоть до UB. Изменились тайминги - разные участки кода стали завершаться в разные моменты времени.
Формально корректный алгоритм, проходящий все и любые статические анализаторы, в чуть изменившихся условиях начинает бабахать сегфолтами.
Как реагирует бизнес и разработка на такие события?
Либо костыльный патч, либо воркэраунд с частичным или полным откатом условий к стабильному поведению.
Третьего по факту не дано.
В чем вообще проблема? Обычно она архитектурная, причем зачастую размазана тонким слоем по куче мест. Чрезвычайно трудно локализуемая. Очень трудная к реальному исправлению.
Нужно перелопатить кучу кода, изменить архитектуру - точечно или площадями, найти и пофиксить.
Это та самая категория гейзенбагов, которая вынуждает откатывать самые лучшие решения в пользу сильно менее лучших.
Зачастую подобные проблемы вылезают именно тогда, когда их никто не ожидает. Алгоритм годами работал прекрасно, но вдруг, в какой-то момент, после изменения какой-либо части окружения - начинает ломаться.
Что можно сделать в данном случае перфоманс инженеру, который сталкивается с подобным?
А ничего. Откатить изменения и отойти в сторону.
Задача в рамках существующих начальных условий практически нерешаема. Доказать наличие архитектурных проблем разработчикам невозможно. Исправление может обойтись страшно дорого и ужасно больно. И сломать совместимость.
Альтернативы много хуже. Нужно вести длительное полнофункциональное тестирование в рамках различных внешних условий. Разумеется, охватить все варианты невозможно. Разумеется, никто не будет тратить на это время, фактически проводя тестовые развертывания и статистические методы оценки результата. Сломалось у 1%? Ну и ладно, не больно-то и хотелось.
Тоже очень узнаваемо, да? Обновления Windows. Здесь работает, здесь не работает, а здесь рыбу заворачивали.
Finally. Непопулярный ныне инженерный подход к вдумчивому и тщательному проектированию и реализации. Как и всегда. Другого пути - не победить, а хотя бы снизить вероятность - просто не существует.
Пир во время UB
Проблема UB в том, что это именно UB - поведение абсолютно не определено, не гарантировано и вообще всё сломалось.
Нет,
Причем вторая проблема заключается в том, что при UB ломается содержимое регистров процессора и поток управления улетает в неизвестном направлении, на кого бог пошлет.
Приземлиться он может абсолютно где угодно в пределах памяти программы - а иногда и хорошо за ее пределами - и сегфолт, а, точнее, стектрейс покажет вам погоду - точку приземления, но совсем не точку возникновения.
Здравствуй, многомесячная отладка и Valgrind.
Адмиральше Грейс было много проще. Вот жук, вот провода, вот проблема.
Проблема UB значительно сложнее и даже обширный инструментарий поможет лишь отчасти.
Особенно неприятная разновидность UB - это спящий UAF, причем, следует заметить - UAF бывают очень незаурядными и разновидностей просто очень много. Он может спать годами и десятилетиями, а потом выскочить внезапно, показать страшную морду и заорать "Бу!"
Хотите вы этого или нет, почти никакие из существующих инструментов неспособны со 100% гарантией отловить UAF. В том числе спящий. Особенно спящий.
Как страшно жить, да.
Это означает все тот же унылый и печальный вывод - "Тщательней надо программировать! Тщательней!"
Увы. Королевских путей в индустрии не существует. Долгие бессонные ночи, кропотливое продумывание, скрупулезное программирование.
PS. Бабушка Грейс смотрит свирепо, грустно, и в то же время с недоумением.
Проблема UB в том, что это именно UB - поведение абсолютно не определено, не гарантировано и вообще всё сломалось.
Нет,
format c: /u, конечно, не происходит - это страшилка бородатых сисадминов, вы даже до кернел паник в большинстве случаев не долетите, вас SIGSEGV нагонит и подстрелит значительно раньше. По опыту, вы останетесь в пределах программы и ее депендентов и получите сегфолт прямо в (клюв), короче, куда вы там смотрите.Причем вторая проблема заключается в том, что при UB ломается содержимое регистров процессора и поток управления улетает в неизвестном направлении, на кого бог пошлет.
Приземлиться он может абсолютно где угодно в пределах памяти программы - а иногда и хорошо за ее пределами - и сегфолт, а, точнее, стектрейс покажет вам погоду - точку приземления, но совсем не точку возникновения.
Здравствуй, многомесячная отладка и Valgrind.
Адмиральше Грейс было много проще. Вот жук, вот провода, вот проблема.
Проблема UB значительно сложнее и даже обширный инструментарий поможет лишь отчасти.
Особенно неприятная разновидность UB - это спящий UAF, причем, следует заметить - UAF бывают очень незаурядными и разновидностей просто очень много. Он может спать годами и десятилетиями, а потом выскочить внезапно, показать страшную морду и заорать "Бу!"
Хотите вы этого или нет, почти никакие из существующих инструментов неспособны со 100% гарантией отловить UAF. В том числе спящий. Особенно спящий.
Как страшно жить, да.
Это означает все тот же унылый и печальный вывод - "Тщательней надо программировать! Тщательней!"
Увы. Королевских путей в индустрии не существует. Долгие бессонные ночи, кропотливое продумывание, скрупулезное программирование.
PS. Бабушка Грейс смотрит свирепо, грустно, и в то же время с недоумением.
Охота за Double Free
Поймать DF на самом деле очень просто. Это частный случай UAF и надо просто нарушения владения памятью замечать.
Нужно отслеживать жизненный цикл адресов аллоцированных блоков и в рантайме проверять парность malloc-free, как скобок. Если по одному адресу прилетело больше одного free до завершения жизненного цикла блока - здравствуйте! Контролировать пошагово весь поток выполнения - здравствуй, Valgrind! - для этого, в общем, совершенно не обязательно.
Дьявол, большой и страшный, разумеется, в деталях и это только на словах просто, да чтобы еще и почти без оверхэда. И надо еще постараться не упасть в сегфолт, чтобы хотя бы мявкнуть успеть. Но, тем не менее, теоретически это вполне возможно сделать относительно просто. Теоретически.
С полноценным UAF все значительно сложнее. Это не обязательно разновидность именно DF, чаще всего это просто тычок в чужую память после того, как она сменила владельца. Если на уровне слоя аллокации нет защиты или контроля в каком угодно виде - здравствуй, динамический анализ, здравствуй, Valgrind, и вы, Heartbleed, тоже здравствуйте!
Хороший аллокатор уровня userspace, конечно, UAF не просто обгавкает - а швырнет приложение в дамп с указанием места тычка в чужую память - он так и должен себя вести, но много ли вы видели хороших аллокаторов уровня userspace?
Возвращаясь к DF, от первого случая ущерб немного смягчает обязательная нуллификация адреса блока после освобождения. Второй и последующие free, по стандарту, на нулевой адрес просто сделают no-op. Хотя бы UB не произойдет. Ошибка в коде, конечно же, останется. Но положа руку на сердце - многие ли держат в голове, что после освобождения памяти указатель на нее нужно нуллифицировать в обязательном порядке? Статические анализаторы не Капитан Очевидность и не мамка, тыкать пальцем в такое нарушение не будут, они на другое нацелены - может, программист так и задумал, э?
Что до UAF - тут конкретно не повезло. Без динамического анализа с огромным оверхедом - на порядок-два замедление выполнения, не фунт изюма - поймать UAF может, в основном, лишь вышеупомянутый хороший аллокатор уровня userspace. При этом, что характерно, обвинят в сегфолтах именно хороший аллокатор, тут так принято.
Спор о виновнике падения может элементарно разрешить Valgrind, но, положа руку на кровоточащее сердце - кто будет так заморачиваться, или, упаси боже! - встраивать Valgrind в крысиные бега CI/CD? Виноват аллокатор и точка!
Гораздо спокойнее жить с широко закрытыми глазами. Глаз DF/UAF не видит - желудок, разумеется, не страдает.
Конечно, как говорят англоязычные, "Absence of evidence is not evidence of absence". Отсутствие доказательств не есть доказательство отсутствия.
Но заморачиваться еще и такими проблемами мы не будем. Не хотим.
Поймать DF на самом деле очень просто. Это частный случай UAF и надо просто нарушения владения памятью замечать.
Нужно отслеживать жизненный цикл адресов аллоцированных блоков и в рантайме проверять парность malloc-free, как скобок. Если по одному адресу прилетело больше одного free до завершения жизненного цикла блока - здравствуйте! Контролировать пошагово весь поток выполнения - здравствуй, Valgrind! - для этого, в общем, совершенно не обязательно.
Дьявол, большой и страшный, разумеется, в деталях и это только на словах просто, да чтобы еще и почти без оверхэда. И надо еще постараться не упасть в сегфолт, чтобы хотя бы мявкнуть успеть. Но, тем не менее, теоретически это вполне возможно сделать относительно просто. Теоретически.
С полноценным UAF все значительно сложнее. Это не обязательно разновидность именно DF, чаще всего это просто тычок в чужую память после того, как она сменила владельца. Если на уровне слоя аллокации нет защиты или контроля в каком угодно виде - здравствуй, динамический анализ, здравствуй, Valgrind, и вы, Heartbleed, тоже здравствуйте!
Хороший аллокатор уровня userspace, конечно, UAF не просто обгавкает - а швырнет приложение в дамп с указанием места тычка в чужую память - он так и должен себя вести, но много ли вы видели хороших аллокаторов уровня userspace?
Возвращаясь к DF, от первого случая ущерб немного смягчает обязательная нуллификация адреса блока после освобождения. Второй и последующие free, по стандарту, на нулевой адрес просто сделают no-op. Хотя бы UB не произойдет. Ошибка в коде, конечно же, останется. Но положа руку на сердце - многие ли держат в голове, что после освобождения памяти указатель на нее нужно нуллифицировать в обязательном порядке? Статические анализаторы не Капитан Очевидность и не мамка, тыкать пальцем в такое нарушение не будут, они на другое нацелены - может, программист так и задумал, э?
Что до UAF - тут конкретно не повезло. Без динамического анализа с огромным оверхедом - на порядок-два замедление выполнения, не фунт изюма - поймать UAF может, в основном, лишь вышеупомянутый хороший аллокатор уровня userspace. При этом, что характерно, обвинят в сегфолтах именно хороший аллокатор, тут так принято.
Спор о виновнике падения может элементарно разрешить Valgrind, но, положа руку на кровоточащее сердце - кто будет так заморачиваться, или, упаси боже! - встраивать Valgrind в крысиные бега CI/CD? Виноват аллокатор и точка!
Гораздо спокойнее жить с широко закрытыми глазами. Глаз DF/UAF не видит - желудок, разумеется, не страдает.
Конечно, как говорят англоязычные, "Absence of evidence is not evidence of absence". Отсутствие доказательств не есть доказательство отсутствия.
Но заморачиваться еще и такими проблемами мы не будем. Не хотим.
Не уверен - не используй
В этом паноптикуме ошибок жизненного цикла блоков памяти UAF по справедливости занимает почетное первое место среди противных и опасных.
Что особенно печально, он умеет добротно прятаться. Настолько добротно, что без полноценного динамического анализа потока выполнения с причитающимся оверхедом выловить его крайне сложно в сколько-нибудь сложных софтах.
Как было описано в предыдущем посте, если умудриться встать где-то посредине между ОС и приложением, то теоретически поймать UAF с высокой вероятностью в принципе можно.
Очень помогла бы в этом архитектурная заточка жесткой reuse policy. Когда - и если - она не противоречит основным функциям системного аллокатора.
Суть проблемы, однако же, в том, что такую задачу в разработке аллокаторов никто никогда не ставил. Не те приоритеты.
Используйте динамический анализ.
Задача осложняется тем, что UAF часто оказывается связан с таймингами, с нагрузкой, с разными путями выполнения. В силу чего написать однозначные красные тесты для ловли этого класса ошибок оказывается почти неразрешимой задачей.
Настолько неразрешимой, что даже команда Тео использует термин "потенциальный UAF": "ssh(1): avoid potential realloc use-after-free in the client if a remote forwarding is added via the local session multiplexing socket while a remote forwarding open request is pending with the server.". Кстати, в последнее время релизы OpenSSH/LibreSSL с такими багфиксами что-то как-то кучно пошли.
Что в переводе на простой язык означает "Мы в точности не уверены, мы не анализировали динамикой".
Как мы все прекрасно понимаем, UAF настолько опасен, что даже просто повышенная вероятность его возникновения должна поднимать прически дыбом.
Как факт, что с этим делать?
Тут просто тщательным и вдумчивым проектированием и кодированием, говоря откровенно, не отделаться.
Динамический анализ либо врожденная стойкость аллокатора к нарушению инвариантов владения памятью становится насущной необходимостью.
Да, это в принципе противоречит концепции TTM. Да, это требует изменения процессов разработки и технической поддержки ПО.
Однако быстро поедешь - медленно понесут. Возможно, что и с музыкой.
В этом паноптикуме ошибок жизненного цикла блоков памяти UAF по справедливости занимает почетное первое место среди противных и опасных.
Что особенно печально, он умеет добротно прятаться. Настолько добротно, что без полноценного динамического анализа потока выполнения с причитающимся оверхедом выловить его крайне сложно в сколько-нибудь сложных софтах.
Как было описано в предыдущем посте, если умудриться встать где-то посредине между ОС и приложением, то теоретически поймать UAF с высокой вероятностью в принципе можно.
Очень помогла бы в этом архитектурная заточка жесткой reuse policy. Когда - и если - она не противоречит основным функциям системного аллокатора.
Суть проблемы, однако же, в том, что такую задачу в разработке аллокаторов никто никогда не ставил. Не те приоритеты.
Используйте динамический анализ.
Задача осложняется тем, что UAF часто оказывается связан с таймингами, с нагрузкой, с разными путями выполнения. В силу чего написать однозначные красные тесты для ловли этого класса ошибок оказывается почти неразрешимой задачей.
Настолько неразрешимой, что даже команда Тео использует термин "потенциальный UAF": "ssh(1): avoid potential realloc use-after-free in the client if a remote forwarding is added via the local session multiplexing socket while a remote forwarding open request is pending with the server.". Кстати, в последнее время релизы OpenSSH/LibreSSL с такими багфиксами что-то как-то кучно пошли.
Что в переводе на простой язык означает "Мы в точности не уверены, мы не анализировали динамикой".
Как мы все прекрасно понимаем, UAF настолько опасен, что даже просто повышенная вероятность его возникновения должна поднимать прически дыбом.
Как факт, что с этим делать?
Тут просто тщательным и вдумчивым проектированием и кодированием, говоря откровенно, не отделаться.
Динамический анализ либо врожденная стойкость аллокатора к нарушению инвариантов владения памятью становится насущной необходимостью.
Да, это в принципе противоречит концепции TTM. Да, это требует изменения процессов разработки и технической поддержки ПО.
Однако быстро поедешь - медленно понесут. Возможно, что и с музыкой.
Вертикальный предел
Проблема диагностики UAF (частным случаем которого является DF) в коде ограничена информацией о происхождении (provenance) указателей на блоки.
В общем случае, находясь на уровне рантайма - libC/glibC/аллокатора мы знаем об указателе (здесь - адресе блока) лишь сам указатель, размер блока и адрес вызвавшей функции (последнее не всегда в точности, нужно находиться как можно ближе к исполняемому коду приложения).
Мы ничего не знаем ни о потоке выполнения пользовательской программы, ни о владении этим указателем, ни об изменениях этого владения.
На уровне рантайма libC/glibC, таким образом, мы знаем лишь о факте возникновения нарушения владения где-то в программе. И всё. Доказано Федорой.
Технически, на этом уровне мы можем достоверно отследить только три инварианта - разрешенные изменения состояния allocated -> freed (нормальный переход), freed -> allocated (переиспользование) и freed -> freed (double free, запрещенный переход).
Последний переход мы c гарантией можем отследить только до момента его возникновения, потому что дальше происходит UB и мы можем либо упасть, либо нет.
Если говорить о более общем случае UAF, мы в рантайме просто не имеем достаточно информации, чтобы определить даже не приблизительное место - а сам факт возникновения нарушения владения. Лишь по косвенным признаком - "Я упал!!!111"
Хорошо, если аллокатор работает в юзерспейсе. Тогда он в стектрейсе хотя бы укажет адрес и стек вокруг него, куда приземлился тычок в чужую память. Плохо, если это не так. Тогда точность будет "Где-то там, вон в той программе".
Для того, чтобы с определенной степенью уверенности утверждать о наличии UAF, нужно находиться на уровень-два выше.
Либо в самой программе - ASan, либо над ней - Valgrind.
Иначе необходимую недостающую информацию просто неоткуда получить.
И понятно, что и то и другое будет работать медленно, печально и это та самая причина, по которой мало кто пользуется динамическим анализом.
"Мне повезет!"
Вывод из всего этого неутешительный.
Чтобы обскакать Valgrind - без оверхеда в реальном времени находить UAF хоть сколько-нибудь достоверно - надо переизобрести Valgrind. И без серьезного оверхеда уже не получится - недостающую информацию надо как-то добыть.
Говоря простым языком, DF мы можем, ценой определенных усилий и с относительно небольшим оверхедом, распознать практически со 100% точностью, а вот UAF - уже нет.
Усилий потребуется в разы, если не на порядок, больше и точность не гарантируется.
Проблема диагностики UAF (частным случаем которого является DF) в коде ограничена информацией о происхождении (provenance) указателей на блоки.
В общем случае, находясь на уровне рантайма - libC/glibC/аллокатора мы знаем об указателе (здесь - адресе блока) лишь сам указатель, размер блока и адрес вызвавшей функции (последнее не всегда в точности, нужно находиться как можно ближе к исполняемому коду приложения).
Мы ничего не знаем ни о потоке выполнения пользовательской программы, ни о владении этим указателем, ни об изменениях этого владения.
На уровне рантайма libC/glibC, таким образом, мы знаем лишь о факте возникновения нарушения владения где-то в программе. И всё. Доказано Федорой.
Технически, на этом уровне мы можем достоверно отследить только три инварианта - разрешенные изменения состояния allocated -> freed (нормальный переход), freed -> allocated (переиспользование) и freed -> freed (double free, запрещенный переход).
Последний переход мы c гарантией можем отследить только до момента его возникновения, потому что дальше происходит UB и мы можем либо упасть, либо нет.
Если говорить о более общем случае UAF, мы в рантайме просто не имеем достаточно информации, чтобы определить даже не приблизительное место - а сам факт возникновения нарушения владения. Лишь по косвенным признаком - "Я упал!!!111"
Хорошо, если аллокатор работает в юзерспейсе. Тогда он в стектрейсе хотя бы укажет адрес и стек вокруг него, куда приземлился тычок в чужую память. Плохо, если это не так. Тогда точность будет "Где-то там, вон в той программе".
Для того, чтобы с определенной степенью уверенности утверждать о наличии UAF, нужно находиться на уровень-два выше.
Либо в самой программе - ASan, либо над ней - Valgrind.
Иначе необходимую недостающую информацию просто неоткуда получить.
И понятно, что и то и другое будет работать медленно, печально и это та самая причина, по которой мало кто пользуется динамическим анализом.
"Мне повезет!"
Вывод из всего этого неутешительный.
Чтобы обскакать Valgrind - без оверхеда в реальном времени находить UAF хоть сколько-нибудь достоверно - надо переизобрести Valgrind. И без серьезного оверхеда уже не получится - недостающую информацию надо как-то добыть.
Говоря простым языком, DF мы можем, ценой определенных усилий и с относительно небольшим оверхедом, распознать практически со 100% точностью, а вот UAF - уже нет.
Усилий потребуется в разы, если не на порядок, больше и точность не гарантируется.
Ceterum autem censeo Bengalurium esse delendam
Кажущееся изобилие вычислительных ресурсов приводит к отвратительным практикам программирования. Первое место по справедливости занимает Бангалор-style.
Пока теоретики рассуждают о преимуществе массивов над списками и кэшах L1, многочисленные смуглокожие детишки капитана Немо (и это не национальность а состояние души) наваливают в код километровые последовательности if (и это за счастье, если догадаются хотя бы написать case), сбивая с толку предсказатели процессоров. Хэш-мапы там, где достаточно RADIX Trie. Структуры, где на выравнивание забили болт - ну, а что такого, архитектура же позволяет невыровненный доступ. Про false sharing можно даже не заикаться - в эпоху многоядерных процессоров и тредов. Железо и AVX порешают все проблемы. И так далее.
Как результат, миллисекунды превращаются в секунды, а секунды в боль.
Оправдания и отмазки при этом самые благовидные.
"Бизнес требует быстро! Если фича не будет готова вчера, где-то умрет котенок!"
"Код должен понимать и поддерживать даже выпускник интерната для слабоумных!"
Таков путь.
Бангалорцы. Планете кирдык.
Дедушка Дональд пробил себе лицо фейспалмом, видя, как его цитатой про оптимизацию - имеющей совершенно иной смысл - прикрываются эвересты бангалорского кода.
На предлагающих выполнить оптимизацию кода смотрят как на юродивых.
Как результат, навык и рефлекс оптимизации при кодировании почти безвозвратно и повсеместно утерян.
При этом бангалорцы очень любят, сидя за кружкой пива, поливать ругательствами своих сородичей из Майкрософт за тормозящий при открытии папки Explorer.
Суть проблемы заключается, как ни странно, в том, что бангалорцы, по сути, и есть последняя линия обороны между "Хочу быстро, плевать на качество!" и конечными пользователями.
Если не вы - то уже никто.
Пачка из сотни if весьма часто элегантным движением пальцев рук превращается в бинарный поиск. Выравнивание структур выполняется простым эмпирическим правилом убывания размера полей. False sharing даже профилировать не нужно - его невооруженным глазом видно. Если, конечно, код не усложнять сверх всяких разумных пределов по принципу "Мама, мама, смотри, как я еще могу!"
Для базовых оптимизаций даже не нужно каких-то особенных сверхусилий.
Просто выполнение сравнительно небольшой кучки хороших практик прямо при программировании - ведь многие вещи уже хорошо известны поколениям программистов.
И - да, микроархитектура важна. Как бы ни хаяли ассемблер, на нижнем уровне процессор выполняет не абстракции, а вполне конкретный машинный код. На него придется смотреть, и его придется понимать. Завязаны шнурки или нет.
Есть отличная поговорка.
Если ты что-то сделал быстро, но плохо - все очень скоро забудут о том, что ты сделал быстро, но будут долго помнить, что ты сделал плохо. И наоборот - если ты сделал медленно и хорошо, все очень скоро забудут, что ты сделал медленно. Но будут долго помнить, что ты сделал хорошо.
Волшебства не существует.
Бангалор в головах должен быть разрушен.
Кажущееся изобилие вычислительных ресурсов приводит к отвратительным практикам программирования. Первое место по справедливости занимает Бангалор-style.
Пока теоретики рассуждают о преимуществе массивов над списками и кэшах L1, многочисленные смуглокожие детишки капитана Немо (и это не национальность а состояние души) наваливают в код километровые последовательности if (и это за счастье, если догадаются хотя бы написать case), сбивая с толку предсказатели процессоров. Хэш-мапы там, где достаточно RADIX Trie. Структуры, где на выравнивание забили болт - ну, а что такого, архитектура же позволяет невыровненный доступ. Про false sharing можно даже не заикаться - в эпоху многоядерных процессоров и тредов. Железо и AVX порешают все проблемы. И так далее.
Как результат, миллисекунды превращаются в секунды, а секунды в боль.
Оправдания и отмазки при этом самые благовидные.
"Бизнес требует быстро! Если фича не будет готова вчера, где-то умрет котенок!"
"Код должен понимать и поддерживать даже выпускник интерната для слабоумных!"
Таков путь.
Бангалорцы. Планете кирдык.
Дедушка Дональд пробил себе лицо фейспалмом, видя, как его цитатой про оптимизацию - имеющей совершенно иной смысл - прикрываются эвересты бангалорского кода.
На предлагающих выполнить оптимизацию кода смотрят как на юродивых.
Как результат, навык и рефлекс оптимизации при кодировании почти безвозвратно и повсеместно утерян.
При этом бангалорцы очень любят, сидя за кружкой пива, поливать ругательствами своих сородичей из Майкрософт за тормозящий при открытии папки Explorer.
Суть проблемы заключается, как ни странно, в том, что бангалорцы, по сути, и есть последняя линия обороны между "Хочу быстро, плевать на качество!" и конечными пользователями.
Если не вы - то уже никто.
Пачка из сотни if весьма часто элегантным движением пальцев рук превращается в бинарный поиск. Выравнивание структур выполняется простым эмпирическим правилом убывания размера полей. False sharing даже профилировать не нужно - его невооруженным глазом видно. Если, конечно, код не усложнять сверх всяких разумных пределов по принципу "Мама, мама, смотри, как я еще могу!"
Для базовых оптимизаций даже не нужно каких-то особенных сверхусилий.
Просто выполнение сравнительно небольшой кучки хороших практик прямо при программировании - ведь многие вещи уже хорошо известны поколениям программистов.
И - да, микроархитектура важна. Как бы ни хаяли ассемблер, на нижнем уровне процессор выполняет не абстракции, а вполне конкретный машинный код. На него придется смотреть, и его придется понимать. Завязаны шнурки или нет.
Есть отличная поговорка.
Если ты что-то сделал быстро, но плохо - все очень скоро забудут о том, что ты сделал быстро, но будут долго помнить, что ты сделал плохо. И наоборот - если ты сделал медленно и хорошо, все очень скоро забудут, что ты сделал медленно. Но будут долго помнить, что ты сделал хорошо.
Волшебства не существует.
Бангалор в головах должен быть разрушен.
Пески Марса
Как часто вы обслуживаете ваши сервера?
Вот это самое - остановили, обесточили, вскрыли, вынули-вставили память, продули пыль, собрали, закрыли, включили?
Сыну маминой подруги на днях пески Марса неприятно напомнили о своем существовании.
Начала рандомно падать одна ВМка. Одна и та же. С SIGSEGV. И повторяющимся ни о чем не говорящем характерным стектрейсом, начинающимся с main(), и заканчивающимся на вершине на malloc или free. Эффект появился внезапно, после обновления и плановой перезагрузки.
Что? Вдруг сломался аллокатор? Всегда аллокатор виноват? Или бозон Хиггса посетил?
Что характерно, memtest показал полную и абсолютную исправность всех банков памяти.
Особенно неприятно, что происходило это не на каком-то Синолоджике, а на брендовом сервере, с памятью ECC - а как же иначе! - причем Advanced ECC не спас и не сохранил.
Спас лишь пеший поход к серверу с баллоном Воздуха Свободы и вот это самое - остановили, обесточили, вскрыли, вынули-вставили память, продули память и материнку Воздухом Свободы, собрали, закрыли, включили.
После чего проблема сгинула, будто бы ее никогда и не было.
Пыль - токопроводящая. Двуокись кремния. Полупроводник. Даже в самых чистых серверных пыль была, есть и будет. На частотах RAM много пыли не нужно, чтобы организовать утечку. Даже DDR2 уже реагирует на пыль, покрывающую DIMMы. Забудем на минуточку про биметалл в контактах, это происходит сильно реже.
Очень сомнительно, что сервера у всех стоят в обеспыленных гермозонах, как у TSMC.
Еще более сомнительно, что тысячи серверов кто-то будет подобным образом обслуживать на регулярной основе. В лучшем случае - влажная уборка в апокалиптических по площади ДЦ.
Вспоминается старый анекдот про нового русского, который приехал заменить купленный три дня назад Мерседес-600, потому что "У него пепельница переполнилась".
Забудем на минутку, что тысячи серверов вместо десятков это неразумно, нерационально и невозможно нормально обслужить.
Вспомним о том, что здесь и сейчас относиться к оборудованию как к расходнику - непозволительная роскошь.
Плохо даже не то, что такой фактор в принципе не рассматривается, не анализируется, сохранение кордампов не включается по умолчанию, и никто не вникает. Упало и упало, перезапустили, стало падать часто - заменили сервер. Три года проживет, а там, как пепельница переполнится - заменим.
Плохо то, что проблема проявляется не всегда и не сразу. Чаще всего происходит тихое повреждение кучи. Внезапные и необъяснимые фатальные ошибки. Типа ORA-600. Неожиданные UB там, где их сроду не было.
И первый обвиняемый - всегда софт.
Между тем, траблшутинг нужно начинать именно с харда.
И - да, сервера можно просто заменить. 😂😂😂
Как часто вы обслуживаете ваши сервера?
Вот это самое - остановили, обесточили, вскрыли, вынули-вставили память, продули пыль, собрали, закрыли, включили?
Сыну маминой подруги на днях пески Марса неприятно напомнили о своем существовании.
Начала рандомно падать одна ВМка. Одна и та же. С SIGSEGV. И повторяющимся ни о чем не говорящем характерным стектрейсом, начинающимся с main(), и заканчивающимся на вершине на malloc или free. Эффект появился внезапно, после обновления и плановой перезагрузки.
Что? Вдруг сломался аллокатор? Всегда аллокатор виноват? Или бозон Хиггса посетил?
Что характерно, memtest показал полную и абсолютную исправность всех банков памяти.
Особенно неприятно, что происходило это не на каком-то Синолоджике, а на брендовом сервере, с памятью ECC - а как же иначе! - причем Advanced ECC не спас и не сохранил.
Спас лишь пеший поход к серверу с баллоном Воздуха Свободы и вот это самое - остановили, обесточили, вскрыли, вынули-вставили память, продули память и материнку Воздухом Свободы, собрали, закрыли, включили.
После чего проблема сгинула, будто бы ее никогда и не было.
Пыль - токопроводящая. Двуокись кремния. Полупроводник. Даже в самых чистых серверных пыль была, есть и будет. На частотах RAM много пыли не нужно, чтобы организовать утечку. Даже DDR2 уже реагирует на пыль, покрывающую DIMMы. Забудем на минуточку про биметалл в контактах, это происходит сильно реже.
Очень сомнительно, что сервера у всех стоят в обеспыленных гермозонах, как у TSMC.
Еще более сомнительно, что тысячи серверов кто-то будет подобным образом обслуживать на регулярной основе. В лучшем случае - влажная уборка в апокалиптических по площади ДЦ.
Вспоминается старый анекдот про нового русского, который приехал заменить купленный три дня назад Мерседес-600, потому что "У него пепельница переполнилась".
Забудем на минутку, что тысячи серверов вместо десятков это неразумно, нерационально и невозможно нормально обслужить.
Вспомним о том, что здесь и сейчас относиться к оборудованию как к расходнику - непозволительная роскошь.
Плохо даже не то, что такой фактор в принципе не рассматривается, не анализируется, сохранение кордампов не включается по умолчанию, и никто не вникает. Упало и упало, перезапустили, стало падать часто - заменили сервер. Три года проживет, а там, как пепельница переполнится - заменим.
Плохо то, что проблема проявляется не всегда и не сразу. Чаще всего происходит тихое повреждение кучи. Внезапные и необъяснимые фатальные ошибки. Типа ORA-600. Неожиданные UB там, где их сроду не было.
И первый обвиняемый - всегда софт.
Между тем, траблшутинг нужно начинать именно с харда.
И - да, сервера можно просто заменить. 😂😂😂