Skip to content

Latest commit

 

History

History
131 lines (90 loc) · 12.8 KB

unexpected_mutability.md

File metadata and controls

131 lines (90 loc) · 12.8 KB
Raw

Внезапная мутабельность

Был теплый весенний денек. Попивая чай, я медленно и лениво пролистывал студенческие работы. Я бы мог сказать, что ничего не предвещало беды, но, увы, работы были выполнены на C++.

Внезапно глаз зацепился за безобидную строчку, используемую для диагностического логгирования

printf("from %s -- to %s", storage[from].value.c_str(), storage[to].value.c_str());

Ничего страшного в ней нет, верно? Но в тот момент меня охватил ужас. И сейчас я поделюсь этим ужасом с вами.

В этой строке спрятана невероятная возможность для багов, неожиданных падений и неопределенных поведений!

Любая C++ строка кода очень сильно зависит от контекста, в котором она расположена. Что мы можем предположить, глядя на один лишь этот printf?

  1. storage -- это какого-то толка ассоциативный массив.
  2. В storage хранятся элементы, имеющие, по-видимому, строковое поле value. Очень вероятно, что поле имеет тип std::string
  3. Написавший этот printf, вероятно, полагает, что оба ключа from и to в массиве присутствуют

Хорошо. А теперь начинается плохо: последнее предположение в любой момент может быть случайно нарушено в дальнейшей жизни кодовой базы. И при нарушении этого предположения нас ждут самые удивительные последствия! И они будут тем более удивительными, если этот printf спрятан под макросом и существует только при конкретных опциях компиляции -- например, если максимальный уровень логгирования задается в compile time.

Такие разные контейнеры

Если from или to нет в списке ключей storage, то все зависит от того как этот самый storage обрабатывает обращение к отсутствующему ключу. Для этого надо пойти и посмотреть, какой тип имеет storage.

  • Это массив или вектор? -- привет, array overrun и неопределенное поведение
  • Это std::map или std::unordered_map? -- вам сегодня повезло, у вас вызвался default конструктор и получились пустые строчки. Хотя это, скорее всего, не то чего вы хотели и новосозданный элемент вам где-нибудь да навредит.

Все? Никого не забыли?

Мы забыли, что стандартными контейнерами из STL дело не ограничивается. Контейнеры могут быть и из других библиотек. И в случае с ассоциативными контейнерами такое встречается крайне часто. std::unordered_map в силу требования стандарта к стабильности ссылок на элементы и гарантий итерирования не может быть реализован эффективно. Он недружелюбен к кэшу и проигрывает в бенчмарках почти всегда. Поэтому в реальных приложениях часто используются альтернативные реализации, пренебрегающие теми или иными гарантиями.

Один из популярных вариантов -- семейство "плоских" хэш-таблиц с открытой адресацией. Все элементы хранятся в одном непрерывном участке памяти. Нетрудно догадаться, что если новому элементу в этом участке не найдется места, то для его вставки придется память реаллоцировать. И ни о какой стабильности ссылок на элементы речи быть не может.

А теперь снова возвращаемся к нашей строке

printf("from %s -- to %s", storage[from].value.c_str(), storage[to].value.c_str());

Если storage это хэш-таблица, имеющая схожие со стандартной, поведение и интерфейс (например, abseil::flat_hash_map ), обращение через operator[] модифицирует контейнер и нас ждут разные варианты в зависимости от заполненности таблицы и наличию ключей. Но всех их нам нужно свести к одному вопросу: при обращении к какому ключу произойдет реаллокация таблицы?

Но не спешите размышлять про from и to! Ведь порядок вычисления аргументов функции не специфицирован! Обращение к ключам может быть в ЛЮБОМ порядке! Что только добавит остроты расследованию бага, если вы столкнетесь с ним в работе.

Но я позволю себе считать, что в нашем случае сначала идет обращение к from, а затем уже к to.

Вариант отсутствия обоих ключей в принципе эквивалентен варианту отсутствия только ключа to. Поэтому им и ограничимся.

auto& from_value = storage[from].value; // 1
auto& to_value = storage[to].value // 2
  1. (1) -- вернет ссылку на поле в элементе, существующем или новосозданном, все нормально. Даже если мы возьмем c_str() тоже ничего страшного не произойдет. Контейнер управляет памятью, висячих указателей нет;
  2. (2) -- если to отсутствует, то либо контейнер реаллоцируется, либо нет. Если контейнер не реаллоцируется, баг останется незамеченным. Иначе -- ссылка from_value инвалидируется!

Короткие строки и длинные баги

Ура, победа? Мы разобрали баг до конца?

На самом деле нет. Ведь выше сознательно был опущен вызов c_str(), присутствовавший в оригинальной строке. Благодаря нему баг мог оставаться незамеченным и не валить ваши тесты! Все дело в SSO -- small string optimization.

Если storage[from].value имеет тип std::string, то на большинстве современных реализаций страшное падение произошло бы только при использовании коротких строк!

Упрощенно std::string выглядит как

class string {
    char* data;
    size_t data_size;
    size_t capacity_size;

    const char* c_str() const {return data;}
};

Здесь 3 * 8 байт на 64 битной платформе. И данные строки лежат в куче. Невиданное расточительство, если строка очень короткая -- 0-15 символов! Поэтому при достаточном желании и упорстве, используя union, можно добиться того, что для коротких строк эта структура бы воспринималась, например, так

class string {
   char data[16];
   size_t capacity_size;
   const char* c_str() const {return data;}
};

И данные строки хранятся уже в самой структуре std::string!

И снова возвращаемся

// это указатель на данные в куче или в самой структуре строки? А кто ж его знает-то!
const char* from_value = storage[from].value.c_str(); 


// если from_value указывает на кучу и контейнер эффективно использует move-семантику, то при реаллокации
// строка будет перемещена -- просто скопируется указатель и from_value останется валидным.
// Иначе строка будет скопирована и почти наверняка storage[from].value.c_str() != from_value
// Хотя, конечно, если крайне маловероятный шанс, что реаллокация реализована через realloc и вам так чудесно повезло, что reallocу
// было достаточно просто передвинуть границу блока памяти
const char* to_value = storage[to].value.c_str()

Какие выводы из этого всего нужно сделать?

  1. С++ страшный язык. Мы видим строчку на 80 символов и, когда отладчик укажет -- падение происходит на ней, чтобы разобраться в его причинах нужно учесть порядок вычисления аргументов, устройство контейнера, move-семантику и устройство элементов контейнера!
  2. Проблема была бы куда менее чудовищной, если бы operator[] не изменял контейнер.
  3. Любой рефакторинг на С++ нужно проводить крайне осторожно. Даже простую замену одной структуры данных на другую с точно таким же интерфейсом: наш баг скрыт при использовании std::map/std::unordered_map, но проявляется с другими таблицами

Как бороться?

Мне не известны настройки линтеров и статических анализаторов, которые бы тут помогли. Подобные баги может выявить только очень тщательное тестирование.

Мы можем предотвращать такие баги, изменяя подход к написанию кода. Крайне советую попрограммировать на Rust (даже если вы не будете им пользоваться в рабочем проекте), чтобы выработать привычку писать код, удовлетворяющий требованиям его borrow checkerа.

Если мы гарантируем в C++ коде, что на контейнер и данные в нем единовременно могут быть либо только const ссылки, либо не более одной мутабельной ссылки, ошибка станет почти невозможной. Но гарантировать мы этого не можем. Только ограничить, чтобы все ссылки у нас были константные:

const auto& const_storage = storage;
const auto& from_value = const_storage.at(from).value; // [] недоступен из-за const
const auto& to_value = const_storage.at(to).value  // [] недоступен из-за const
// если какой-то из ключей отсутствует -- будет выброшено исключение