UB or not UB: дублируем элемент std::vector

В статье выясним, можно ли с точки зрения стандарта языка C++ тривиальным вызовом push_back продублировать элемент std::vector. Отвечая на простой вопрос, столкнемся с более интересными: что собой представляет внутренний мир вектора, как "протухают" итераторы при реаллокации, какие ограничения добавляют гарантии безопасности относительно исключений...

Пожалуй самый распространенный контейнер из стандартной библиотеки C++ это std::vector. Линейное расположение данных в памяти дает нам приятные бонусы: доступ к произвольному элементу за константное время, быстрый последовательный проход за счет эффективного использования кэша. Обратная сторона медали - дорогая вставка в произвольное место (за линейное время) и инвалидация итераторов при реаллокациях и не только. Последнее особенно "радует" новичков, на которых из безобидно выглядящих функций вроде add и erase ниже начинают выпрыгивать демоны UB (Undefined Behavior - непредсказуемое поведение программы в результате нарушения зафиксированного в стандарте языка соглашения).

void add(std::vector<int> vec) {
  for (int v: vec) { // UB
    if (/*некоторое условие*/)
      vec.push_back(42);
  }
}

void erase() {
  std::vector vec = {1, 2, 3};
  auto two = std::next(vec.begin());
  std::erase(vec, 1);
  std::cout << *two; // UB
}

Если проблемы в коде выше неочевидны, достаточно сходить на cppreference в документацию к vector::push_back() или любому другому методу, вызов которого потенциально приводит к реаллокации. После этого заглядывайте под спойлер ниже, где процесс вставки проиллюстрирован наглядной анимацией.

Проблема инвалидации на пальцах

Это хорошая, штатная ситуация, когда понимание ошибки (и ее причины) становится очевидно после нескольких минут чтения документации. А в качестве противоположного примера, рассчитывая, что проблемы выше понятны и не вызывают интереса, предлагаю совместно рассмотреть такой вопрос: корректен ли подобный код:

void duplicateLatest(std::vector<int>& vec) {
  assert(!vec.empty());
  vec.push_back(vec.back());
}

Похожая запись попалась на глаза, когда искал ошибку в чужом, изредка падающем в отсутствие санитайзеров коде. Зазвонил внутренний колокольчик: "стоп, а не UB ли это"? Используемая перегрузка push_back(const T& v) принимает аргумент v по ссылке, а значит реализации вектора придется создавать новый элемент из другого, расположенного в его же собственном буфере. Что если к моменту конструирования копии внутренний буфер будет уже реаллоцирован? Интуиция подсказывает, что подобный код в различных вариантах уже написан многократно и все должно работать, но кто в мире C++ полагается на интуицию...

В качестве отправной точки заглядываем в описание методов изменения вектора, видим ожидаемое:

Remarks: Causes reallocation if the new size is greater than the old capacity. Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence, as well as the past-the-end iterator.

И на первый взгляд этого достаточно, чтобы уверенно заявить: код выше приведет к UB, если к моменту вызова push_back выполняется утверждение size() == capacity(). Каждый разработчик знает, что велосипеды - это чаще всего непродуктивно, но познавательно и весело. Чтобы изучить вопрос изнутри, начнем с попытки написать минимальную удовлетворяющую стандарту реализацию push_back, в которой проблема воспроизведется. При этом подойдем к ответу на вопрос, а сам ответ будет в следующем разделе.

Сломанная реализация

Например, такая наивная операция вставки в конец сделает результат выполнения всей программы неопределенным:

 1 //_buf - сырой указатель на внутренний буфер, _capacity - его вместимость
 2 void push_back_realloc_v1(const T& value, size_t next_capacity) {
 3   T* next_buffer = allocate(next_capacity);
 4   T* place_for_value = std::uninitialized_move(begin(), end(), next_buffer);
 5   deallocate(_buf, size());
 6   new (place_for_value) T(value); // потенциальное use-after-free
 7   std::swap(_buf, next_buffer);
 8   std::swap(_capacity, next_capacity);
 9 }
10
11 void push_back(const T& value) {
12   if (size() == capacity()) {
13     size_t next_capacity = size() * growth_rate + 1;
14     push_back_realloc_v1(value, next_capacity);
15   } else {/*тривиальное добавление в существующий буфер*/}
16   // увеличение счетчика длины или указателя на конец данных
17 }

Здесь в случае исчерпания буфера попадаем в push_back_realloc_v1, где первым делом аллоцируем новый, некоторого гарантированно большего размера. Потом перемещаем в него все элементы из старого и освобождаем старый внутренний буфер _buf вызовом deallocate (будем считать, что в реализации последнего мы не только просим аллокатор прибрать к рукам ставшую ненужной память, но и не забываем перед этим пройти по всем size() элементам и вызвать их деструкторы). Далее пытаемся создать копию value и поместить ее после последнего элемента в новом буфере и ... Houston, we have a problem. Если value хранился в нашем исходном векторе, то в этот момент обращаемся к памяти, которая уже освобождена. Программа сломана. До обновления в нашем векторе указателя на внутренний буфер и _capacity мы уже не доберемся.

Готово, написали корректную реализацию, которая приводит к UB в интересующем случае? Нет, здесь пока хватает ляпов: если у T нет перемещающего конструктора, код просто не соберется. Если есть и он кинет исключение в строке 4 - утечет память. Но с точки зрения нашего эксперимента гораздо серьезнее, что забыли про требование стандарта строгой гарантии безопасности относительно исключений:

Remarks: If an exception is thrown while inserting a single element at the end and T is Cpp17CopyInsertable or is_nothrow_move_constructible_v is true, there are no effects. Otherwise, if an exception is thrown by the move constructor of a non-Cpp17CopyInsertable T, the effects are unspecified.

Оговорка для случая, не относящегося к нашей перегрузке push_back (когда копирующий конструктор недоступен, а перемещающий выбрасывает исключение), не очень интересна. А вот первое требование фатально нарушено. Возможно безопасность исходного примера неявно следует из этого утверждение? Давайте попробуем обеспечить strong exception guarantee. Что сейчас может пойти не так? Если не удастся выделить память (строка 3), все в порядке: данные вектора мы попортить не успели. В строке 4 ситуация интереснее: если один из перемещающих конструкторов кинет исключение, исходное состояние вектора уже не восстановить. Вызовы деструкторов и деаллокация (5) гарантируют отсутствие исключений (если вдруг у вас есть странные объекты с не-noexcept деструкторами, им не место в стандартных контейнерах). Наконец, в строке (6) может бросить копирующий конструктор, и в этом случае пользователь контейнера тоже не должен заметить никаких побочных эффектов. Исправляем:

 1 void push_back_realloc_v2(const T& value, size_t next_capacity) {
 2   T* next_buffer = allocate(next_capacity);
 3   {
 4     T* out = next_buffer;
 5     auto _ = gsl::finally([&]{ deallocate(next_buffer, out - next_buffer); });
 6 
 7     for (auto in = begin(); in != end(); ++in, ++out) {
 8       new (out) T(std::move_if_noexcept(*in));
 9     }
10     new (out) T(value); // потенциальное use-after-move
11     std::swap(_buf, next_buffer);
12     std::swap(_capacity, next_capacity);
13     out = next_buffer + size();
14   }
15 }

Этот вариант немного сложнее и гораздо лучше. Используем RAII-обертку над блоком памяти next_buffer (чтобы не раздувать код примера взят final_action из GSL). Объект _ при завершении своей жизни (выход из области 3-14) гарантирует вызов переданной в gsl::finally лямбды. Теперь заполнение нового буфера основано на стандартной функции move_if_noexcept: если у T небросающий конструктор перемещения, получаем rvalue ссылку и зовем конструктор перемещения, иначе копируем из lvalue ссылки. При вызове конструктора копирования (строки 8 и 10) все еще может вылететь исключение, в этом случае перед выходом из функции наш безымянный страж _ с помощью deallocate обеспечит вызов деструкторов всех уже скопированных объектов в количестве out - next_buffer штук и освобождение временного буфера. Если все конструкторы отработали и выполнение миновало строку 10 - исключений больше не будет, самое время поменять указатели временного и основного буфера. В строке 13 вспоминаем, что существование _ подходит к концу и вот-вот будет вызван deallocate. Попытка вычислить out - next_buffer теперь приведет к UB, т.к. next_buffer теперь указатель на старый буфер, а out - все еще на новый. Поэтому в качестве расплаты за синтаксический сахар final_actionнам необходимо обновить значение out исключительно для корректного определения числа элементов в освобождаемом буфере.

Отлично, можем более-менее уверенно заявить, что реализовали для подопытного класса bad_vector метод push_back, в котором учли все требования к нему, явно перечисленные на соответстующей странице cppreference.com (и в стандарте). Теперь воспроизводим ситуацию, когда push_back сломает наш пример. Положим, что

• у класса T есть nothrow move-конструктор

• наступил момент, когда vec.size()==vec.capacity()

• захотели продублировать свой элемент vec.push_back(vec.back())

В этих условиях при перетаскивании элементов из старого буфера в новый будут вызываться перемещающие конструкторы. Важно, что каждый из них в общем случае имеет право вытаскивать внутренности из объекта. В момент перемещения мы поджигаем фитиль, а взрыв интересный эффект происходит в строке 10, когда пытаемся сконструировать копию value из перемещенного объекта. Стандарт накладывает довольно размытое, на мой взгляд, требование валидности на объекты из std в состоянии after move и уточняет, что заявленные контейнером/алгоритмом инварианты должны сохраняться:

Cpp17MoveConstructible requirements: <...> Note 1: rv must still meet the requirements of the library component that is using it. The operations listed in those requirements must work as specified whether rv has been moved from or not.

Пока объект пользовательского типа не касается стандартной библиотеки, с точки зрения главного документа языка перемещающий конструктор/оператор присваивания имеют права творить с ним любые непотребства (не обязательна даже возможность вызова деструктора у перемещенного объекта). Когда мы помещаем этот объект в стандартный контейнер (точнее, начинаем использовать некоторые методы), прилетают те самые требования Cpp17MoveInsertable and Cpp17MoveAssignable и им подобные. Однако требования сравнительно слабые: например, для вектора достаточно обеспечить некоторое корректное поведение копирующих и перемещающих конструкторов и нескольких других функций.

Из этого следует, что UB непосредственно в момент вызова push_back не получим, но содержимое вектора в общем случае станет неадекватным и пользовательские инварианты могут сломаться. Например, в результате выполнения такого кода ниже получим вектор из двух элементов, первый из которых - указатель на единичку, а второй - nullptr, т.к. конструируется из перемещенного shared_ptr.

bad_vector<std::shared_ptr<int>> vec;
vec.push_back(std::make_shared<int>(1));
vec.push_back(vec.back());

К слову, можно и окончательно разломатьbad_vector::push_back, отдельно обрабатывая случай, когда перемещающий конструктор бросает исключение, а копирующий - нет. В этой ветке переключаемся на push_back_realloc_v1, в котором вместо перемещения пользуемся копированием (std::uninitialized_copy) и получаем полноценное UB при обращении к освобожденной памяти при полном соблюдении strong exception guarantee:

constexpr bool copy_ctor_noexcept = noexcept(T(*std::declval<T*>()));
constexpr bool move_ctor_noexcept = noexcept(T(std::declval<T>()));
if constexpr (copy_ctor_noexcept && !move_ctor_noexcept) {
  /*привет, use-after-free*/
}

UB или не UB

Мы успешно смогли написать плохую реализацию. Давайте теперь посмотрим, как устроены априори хорошие: заглянем под капот push_back в исполнении clang, gcc и msvc. Здесь ждет сюрприз: паттерн доступа к данным не соответствует нашему и строго повторяется в каждой библиотеке: аллокация нового буфера, конструирование последнего (вставляемого) элемента, копирование или перемещение элементов из старого буфера и его деаллокация. Напрашивается очевидный вывод, что bad_vector в отличие от его взрослых собратьев все еще не соответствует стандарту: что-то упустили. Еще раз внимательно идем по разделу контейнеров в стандарте:

• строгая гарантия безопасности относительно исключений не запрещает возможность "сломанной реализации" push_back сама по себе, хотя и делает ее неудобной;

• для vec.emplace(pos, args) явно указано, что аргументы могут быть ссылками на значения из vec. Для push_back (и emplace_back) аналогичной пометки нет;

• для vec.insert(pos, begin, end) не менее явно сказано, что вставляемый диапазон не должен принадлежать тому же контейнеру;

• комментарии к vec.push_back(t) лаконичны: метод добавляет в конец вектора копию t;

• в реализации libstdc++ есть комментарий: порядок операций диктуется необходимостью избежать use-after-move. К сожалению, ссылка на пункт стандарта в конце комментария, относится уже к другой перегрузке push_back и не поясняет, почему эта ситуация обязана быть учтена (а не сброшена со счетов как UB из-за инвалидации итераторов).

Авторитетный ответ на такой же по сути вопрос про вставку в вектор его же элемента v.insert(v.begin(), v[2]) я нашел среди issue к Library Working Group. Однако его лаконичность несколько обескураживает:

vector::insert(iter, value) is required to work because the standard doesn't give permission for it not to work.

Более подробен развернутый комментарий одного из мейнтейнеров реализации STL от Microsoft. Ниже вольный перевод фрагмента:

Стандарт требует, чтобы этот пример работал (что может быть головной болью для мейнтейнеров STL). Это требование определено наиболее неприятным, на мой взгляд, образом: "ничем не запрещено". В действительности инвалидация итераторов здесь не замешена: в момент вызова push_back() ссылка валидна, поэтому реализация обязана гарантировать, что потенциальная реаллокация не сломает ее до тех пор, пока она необходима. (VC сейчас обеспечивает это с помощью явной проверки, которую я хотел бы удалить в будущем)

Таким образом, безопасность вставки в вектор ссылки на его собственные элементы следует в первую очередь из базового описания операции вставки. Если заявлено, что метод добавляет в конец вектора копию t, то он делает это для любого t, а инвалидация итераторов с точки зрения внешнего кода наступает строго после возврата управления из метода. Подобная логика справедлива до тех пор, пока в стандарте явно не указано иное. В исходном примере поведение строго определено и соответствует ожиданиям.

Отлично, что полученное положение согласуется с интуитивным ощущением при написании подобного кода. Еще лучше, что UB в исходном примере нет: чем UB меньше, тем проще писать надежные программы. Однако для того, чтобы в точности убедиться в этом, пришлось довольно глубоко погрузиться в стандарт и... его не хватило, помог лишь ответ от LWG. В частности, мне неочевиден приоритет общего описания операции над частной проблемой инвалидации. Если у вас есть понимание, из какого пункта стандарта можно это вывести (и другие идеи и дополнения), буду рад обсудить в комментариях. Самым обескураживающим моментом путешествия в документацию оказалось наличие явного указания, что аргументы emplace могут быть ссылками на элементы того же вектора, и отсутствие подобных примечаний для push_back, insert...

Интересно, что читать и имплементировать стандарт тяжело не только тем, кто заглядывает в него редко: в VS до ~2010 года исходный пример приводил к падению. В 2017 году был еще один багфикс по тому же вопросу: оказалось, что ранее реализованная простая проверка "является ли t элементом вектора" не работает: вставляемый элемент может не входить в вектор непосредственно, в лишь косвенно зависеть от времени жизни его элементов.

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