UB o no UB: elemento duplicado std::vector / Habr

En este artículo descubriremos si, desde el punto de vista del estándar del lenguaje C++, es posible duplicar un elemento std::vector con una llamada push_back trivial. Respondiendo a una pregunta sencilla, nos enfrentaremos a otras más interesantes: cuál es el mundo interno de un vector, cómo se “desvanecen” los iteradores durante la reasignación, qué restricciones añaden garantías de seguridad respecto a las excepciones…

Quizás el contenedor más común de la biblioteca estándar de C++ sea std::vector. La disposición lineal de los datos en la memoria nos brinda agradables ventajas: acceso a un elemento arbitrario en tiempo constante, paso secuencial rápido gracias al uso eficiente de la caché. La otra cara de la moneda es la costosa inserción en un lugar arbitrario (en tiempo lineal) y la invalidación de iteradores durante las reasignaciones y más. Esto último “agrada” especialmente a los principiantes, quienes se benefician de funciones aparentemente inofensivas como add y erase Los demonios comienzan a saltar debajo. UB (Comportamiento indefinido: comportamiento impredecible del programa como resultado de una violación del acuerdo fijado en el estándar del idioma).

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
}

Si los problemas en el código anterior no son obvios, simplemente vaya a cppreference en la documentación para vector::push_back() o cualquier otro método cuya llamada potencialmente resulte en una reasignación. Después de eso, mire debajo del spoiler a continuación, donde se ilustra el proceso de inserción con una animación visual.

El problema de la discapacidad en los dedos.

Esta es una situación buena y normal cuando la comprensión del error (y su causa) se vuelve obvia después de unos minutos de leer la documentación. Y como ejemplo opuesto, esperando que los problemas anteriores sean comprensibles y no causen interés, propongo considerar conjuntamente la siguiente pregunta: ¿es correcto dicho código?

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

Una entrada similar me llamó la atención cuando buscaba un error en el código de otra persona, que ocasionalmente fallaba por falta de desinfectantes. Sonó el timbre interno: “para, ¿no es la UB”? Sobrecarga usada push_back(const T& v) acepta un argumento v por referencia, lo que significa que la implementación del vector tendrá que crear un nuevo elemento a partir de otro ubicado en su propio buffer. ¿Qué pasa si cuando se construye la copia, el búfer interno ya se ha implementado? La intuición sugiere que código similar en varias versiones ya se ha escrito muchas veces y todo debería funcionar, pero ¿quién en el mundo C++ confía en la intuición…

Como punto de partida, veamos descripción métodos para cambiar el vector, vemos lo que se espera:

Observaciones: Provoca reasignación si el nuevo tamaño es mayor que la capacidad anterior. La reasignación invalida todas las referencias, punteros e iteradores que hacen referencia a los elementos de la secuencia, así como el iterador más allá del final.

Y a primera vista, esto es suficiente para afirmar con confianza: el código anterior conducirá a UB si en el momento de la llamada push_back afirmación en progreso size() == capacity(). Todo desarrollador sabe que las bicicletas suelen ser improductivas, pero educativas y divertidas. Para estudiar el problema desde adentro, comencemos intentando escribir una implementación mínima que cumpla con el estándar. push_back, en el que se reproducirá el problema. En este caso, llegaremos a la respuesta a la pregunta, y la respuesta en sí estará en la siguiente sección.

Implementación rota

Por ejemplo, una operación de inserción tan ingenua al final hará que el resultado de todo el programa sea indefinido:

 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 }

Aquí, si el buffer se agota, terminamos en push_back_realloc_v1, donde primero asignamos uno nuevo, de algún tamaño mayor garantizado. Luego movemos todos los elementos del anterior y liberamos el antiguo búfer interno. _buf desafío deallocate (Asumiremos que al implementar esto último no solo le pedimos al asignador que se haga cargo de la memoria que se ha vuelto innecesaria, sino que tampoco nos olvidemos de revisar todos size() elementos y llamar a sus destructores). A continuación intentamos crear una copia. value y colóquelo después del último elemento en el nuevo buffer y… Houston, tenemos un problema. Si value estaba almacenado en nuestro vector original, luego en este momento accedemos a la memoria que ya ha sido liberada. El programa está roto. Antes de actualizar nuestro vector con un puntero al búfer interno y _capacity ya no llegaremos allí.

Listo, ¿ha escrito una implementación correcta que conduzca a UB en el caso de interés? No, todavía hay bastantes errores garrafales: si T no hay ningún constructor en movimiento, el código simplemente no se construye. Si lo hay y arroja una excepción en la línea 4, la memoria se perderá. Pero desde el punto de vista de nuestro experimento, es mucho más grave que se hayan olvidado de requisito Estándar estricto de garantía de seguridad con respecto a las excepciones:

Observaciones: Si se lanza una excepción al insertar un solo elemento al final y t es Cpp17CopiaInsertable o is_nothrow_move_constructible_v es cierto, no hay efectos. De lo contrario, si el constructor de movimientos de un objeto que noCpp17CopiaInsertable tlos efectos no se especifican.

Descargo de responsabilidad para casos no relacionados con nuestra sobrecarga push_back (cuando el constructor de copia no está disponible y el constructor de movimiento genera una excepción) no es muy interesante. Pero el primer requisito se viola fatalmente. ¿Quizás la seguridad del ejemplo original se desprende implícitamente de esta afirmación? Intentemos proporcionar fuerte garantía de excepción. ¿Qué podría salir mal ahora? Si no asignamos memoria (línea 3), todo está bien: no tuvimos tiempo de estropear los datos vectoriales. En la línea 4 la situación es más interesante: si uno de los constructores en movimiento lanza una excepción, no se puede restaurar el estado original del vector. Las llamadas a destructores y la desasignación (5) no garantizan excepciones (a menos que tenga objetos extraños con no-noexcept destructores, no tienen cabida en contenedores estándar). Finalmente, la línea (6) puede generar un constructor de copia, en cuyo caso el usuario del contenedor tampoco debería notar ningún efecto secundario. De corrección:

 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 }

Esta opción es un poco más complicada y mucho mejor. Usando un contenedor RAII sobre un bloque de memoria next_buffer (para no inflar, se toma el código de ejemplo final_action de GSL). Un objeto _ al final de su vida (saliendo del área 3-14) garantiza una llamada al transferido a gsl::finally lambdas. Ahora llenar el nuevo búfer se basa en una función estándar. move_if_noexcept: si T constructor de movimientos que no lanza, obtenga una referencia de rvalue y llame al constructor de movimientos; de lo contrario, copie desde la referencia de lvalue. Aún se puede generar una excepción al llamar al constructor de copia (líneas 8 y 10), en cuyo caso nuestra guardia sin nombre se generará antes de que salga la función. _ mediante el uso deallocate asegurará que los destructores de todos los objetos ya copiados sean llamados out - next_buffer piezas y liberando el buffer temporal. Si todos los constructores han funcionado y la ejecución ha pasado la línea 10, no habrá más excepciones, es hora de cambiar los punteros del buffer temporal y principal. En la línea 13 recordamos que la existencia _ está llegando a su fin y está a punto de ser llamado deallocate. Tratando de calcular out - next_buffer ahora conducirá a la UB, porque next_buffer ahora un puntero al antiguo buffer, y out – todavía como nuevo. Por lo tanto, como venganza por el azúcar sintáctico final_actionnecesitamos actualizar el valor out únicamente para la determinación correcta del número de elementos en el buffer liberado.

Genial, podemos decir con más o menos confianza que lo implementamos para la clase experimental. bad_vector método push_back, que tuvo en cuenta todos los requisitos para ello, claramente enumerados en la página cppreference.com correspondiente (y en el estándar). Ahora reproduzcamos la situación en la que push_back rompe nuestro ejemplo. Supongamos que

en la clase T hay un constructor de movimientos sin tiro
llegó el momento en que vec.size()==vec.capacity()
quería duplicar tu elemento vec.push_back(vec.back())

En estas condiciones, al arrastrar elementos del buffer antiguo al nuevo, se llamará a los constructores de movimiento. Es importante que, en general, cada uno de ellos tenga derecho a sacar el interior del objeto. En el momento del movimiento, encendemos la mecha y ~~explosión~~ Se produce un efecto interesante en la línea 10 cuando intentamos construir una copia. value del objeto movido. La norma impone un requisito bastante vago, en mi opinión, validez a objetos es estándar en estado posterior al movimiento y aclaraque se deben conservar las invariantes declaradas por el contenedor/algoritmo:

Cpp17MoveConstructible requisitos: <...> Nota 1:rv aún debe cumplir con los requisitos del componente de la biblioteca que lo está utilizando. Las operaciones enumeradas en esos requisitos deben funcionar según lo especificado, ya sea que la casa rodante se haya movido o no..

Mientras un objeto de un tipo definido por el usuario no toque la biblioteca estándar, desde el punto de vista del documento del idioma principal, el constructor/operador de asignación en movimiento tiene derecho a hacer cualquier cosa indecente con él (no requerido incluso la capacidad de llamar a un destructor sobre un objeto en movimiento). Cuando colocamos este objeto en un contenedor estándar (más precisamente, comenzamos a usar algunos métodos), llegan los mismos requisitos. Cpp17MoveInsertable y Cpp17MoveAsignable y similares. Sin embargo, los requisitos son relativamente débiles: por ejemplo, para un vector es suficiente garantizar cierto comportamiento correcto de los constructores de copiar y mover y algunas otras funciones.

De esto se desprende que UB inmediatamente en el momento de la convocatoria push_back No lo conseguiremos, pero el contenido del vector generalmente se volverá inadecuado y las invariantes del usuario pueden fallar. Por ejemplo, como resultado de ejecutar el código siguiente, obtenemos un vector de dos elementos, el primero de los cuales es un puntero a uno y el segundo es nullptr, porque construido a partir de desplazados shared_ptr.

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

Por cierto, se puede romper por completo.bad_vector::push_back, manejando por separado el caso en el que el constructor en movimiento genera una excepción pero el constructor que copia no. En este hilo pasamos a push_back_realloc_v1en el que en lugar de mover usamos copiar (std::uninitialized_copy) y obtenga una UB completa al acceder a la memoria liberada en pleno cumplimiento de la sólida garantía de excepción:

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 o no UB

Pudimos escribir con éxito una mala implementación. Veamos ahora cómo funcionan los buenos a priori: miremos debajo del capó push_back realizado sonido metálico, gcc y msvc. Aquí nos espera una sorpresa: el patrón de acceso a los datos no corresponde al nuestro y se repite estrictamente en cada biblioteca: asignación de un nuevo búfer, construcción del último elemento (insertado), copia o movimiento de elementos del antiguo búfer y su desasignación. La conclusión obvia es que bad_vector A diferencia de sus homólogos adultos, todavía no cumple con el estándar: le falta algo. Una vez más, repasamos detenidamente el apartado de contenedores de la norma:

garantía estricta la seguridad de excepción no prohíbe la posibilidad de una “implementación rota” de push_back en sí misma, aunque la hace inconveniente;
para vec.emplace(pos, args) declarado explícitamenteque los argumentos pueden ser referencias a valores de vec. Para push_back (y emplace_back) no existe ninguna marca similar;
para vec.insert(pos, begin, end) no se indica menos claramente que la gama que debe insertarse no debe pertenecen al mismo contenedor;
comentarios a vec.push_back