C strings: un error que lleva 50 años

 (longtran2904.substack.com)
1 puntos por GN⁺ 4 시간 전 | 1 comentarios | Compartir por WhatsApp
  • Las cadenas terminadas en NUL de C no conservan información de longitud, lo que provoca búsquedas repetidas y errores de límites; hoy, las cadenas basadas en longitud, que almacenan juntos el puntero y el tamaño, son más adecuadas como diseño por defecto
  • Sin una longitud explícita, se repiten las llamadas a strlen y los recorridos byte por byte, y como snprintf, sizeof y strlen difieren en si incluyen o no el byte de terminación, escribir y revisar código se vuelve difícil
  • Las cadenas basadas en longitud tratan de forma consistente la cadena vacía como size == 0, y permiten aplicar tal cual operaciones de búsqueda, división y slicing a datos binarios arbitrarios, incluidos bytes NUL
  • Pueden devolver subcadenas que apuntan a una parte de la memoria original, evitando asignaciones y copias intermedias en recortes, búsquedas, tokenización y parsing de CSV, Markdown, JSON y C
  • Los centinelas siguen siendo útiles para mantener invariantes y para algunas búsquedas de tokens, y también sigue siendo necesario convertir hacia y desde APIs existentes de C y del sistema operativo; pero en la mayoría del código, combinar cadenas basadas en longitud con inmutabilidad en los límites de la API resulta más simple y flexible

Guardar puntero y longitud en lugar de terminación NUL

  • Las cadenas de C representan sus límites con un puntero a un flujo de caracteres y un byte NUL final
    • En las restricciones de memoria y rendimiento de los años 70 pudo haber sido razonable, pero hoy casi no hay motivos para mantener este enfoque
  • La alternativa adoptada por lenguajes modernos y frameworks importantes es una estructura que almacena juntos el puntero a los datos y el tamaño
struct String
{
    u8* data;
    u64 size;
};
  • Los literales de cadena pueden convertirse en String calculando la longitud con sizeof(s) - 1, y operaciones como comparación o salida usan directamente el tamaño almacenado
  • Los arreglos también pierden información como la longitud cuando se convierten en punteros, por lo que sufren problemas de seguridad y usabilidad similares a los de las cadenas

El costo de descartar la información de longitud

  • Si no se almacena la longitud, cada código que la usa debe llamar repetidamente a strlen o recorrer los bytes uno por uno, lo que aumenta el trabajo innecesario y la complejidad
  • Inspeccionar y hacer cumplir la longitud en tiempo de ejecución también es más lento y engorroso, y a los depuradores y herramientas de análisis les cuesta tratar char*, char[N] y char*[N] de forma consistente
  • Hay quienes sostienen que muchos de los problemas de memoria y bugs de overflow de C provienen de este diseño, aunque también existe el contraargumento de que los centinelas son suficientes
  • Una cadena cuya longitud se desconoce se parece más a un patrón de acceso secuencial, como una lista enlazada, que al acceso aleatorio de un arreglo
  • Quienes defienden la terminación NUL consideran que el procesamiento secuencial induce algoritmos de una sola pasada en lugar de múltiples pasadas, y por eso es eficiente
    • Muchos programadores, incluidos principiantes, escriben código asumiendo que obtener la longitud de una cadena es barato
    • Las rutinas comunes de cadenas también se escriben con más naturalidad cuando reciben la longitud, y por las llamadas repetidas a strlen, el código real termina recorriendo la misma cadena varias veces
    • La premisa de que menos pasadas siempre significa más velocidad es resultado de malentender cómo funcionan las CPU modernas

Las distintas longitudes que significan snprintf, sizeof y strlen

  • Los dos enteros de snprintf parecen la misma “longitud”, pero sus reglas de inclusión del NUL son opuestas
int snprintf(char *str, size_t size, const char *format, ...);
  • El size de entrada debe incluir el espacio para la terminación NUL del búfer de salida, pero el valor devuelto indica la longitud de la cadena que se habría generado excluyendo el byte NUL
  • Cada vez que se usa una función o API relacionada con cadenas, hay que verificar por separado estas condiciones
    • Si la función escribe directamente el byte NUL
    • Si hay que agregar espacio para el byte NUL al tamaño de asignación
    • Si los argumentos de tamaño y los valores de retorno incluyen el byte NUL
  • sizeof("some string") incluye el byte NUL, pero strlen("some string") lo excluye
  • Si al cambiar código basado en literales por código basado en punteros en tiempo de ejecución se conserva el mismo - 1, aparece un bug de longitud uno menor
#define TEST_STRING "some string"
size_t size = sizeof(TEST_STRING) - 1;

const char *str = "some string";
size_t size = strlen(str) - 1;

Sobrescribir repetidamente bytes NUL intermedios

  • Si se suman los valores devueltos por varias llamadas a snprintf al offset para concatenar cadenas, cada llamada sobrescribe el byte de terminación NUL escrito por la llamada anterior
int offset = 0;
offset += snprintf(ptr + offset, size - offset, "%d", my_int);
offset += snprintf(ptr + offset, size - offset, "%s", my_str);
offset += snprintf(ptr + offset, size - offset, "%f", my_flt);
  • Escribir bytes de terminación intermedios es innecesario, aunque su impacto en rendimiento puede no ser grande
  • El problema mayor es que este comportamiento no es intuitivo y lleva a la idea errónea de que snprintf no termina con NUL
  • Como resultado, aparece código que agrega ptr[offset] = 0; al final, pero eso también es innecesario y refuerza aún más la misma confusión

Doble estado entre cadena vacía y cadena nula

  • En el modelo de terminación NUL, la cadena vacía y el puntero nulo se tratan como estados inválidos distintos, por lo que el código de procesamiento de cadenas debe comprobar ambos
  • Como las cadenas y arreglos de C# también son tipos por referencia, leer Length o recorrerlos en estado nulo produce una excepción y requiere manejo separado
  • Una respuesta común es pasar y devolver siempre cadenas o arreglos vacíos en lugar de nulos
    • Reglas como String.IsNullOrEmpty, “Don’t Return Null” y “Don’t Pass Null” también son formas de manejar esta distinción
  • En una estructura con puntero y longitud, si una cadena está vacía puede determinarse solo con size == 0
    • El puntero puede ser nulo o una dirección válida
    • Cuando se llegó al final de una cadena o se apunta a una subcadena vacía dentro de una cadena grande, puede haber un puntero válido incluso con longitud 0
    • Si solo se desreferencia después de comprobar la longitud, un puntero a memoria ya liberada tampoco se accede cuando la longitud es 0

Usar la misma representación para datos binarios

  • Las cadenas basadas en longitud no dependen de centinelas, por lo que pueden almacenar de forma segura datos binarios arbitrarios que contengan bytes NUL
  • Así como las funciones de cadenas ASCII también funcionan con UTF-8, las operaciones basadas en longitud como escanear, dividir, recortar y hacer slicing pueden aplicarse a arreglos de bytes
  • En formatos binarios terminados en NUL, hay que decidir por separado si se almacena el byte de terminación
    • Si se almacena, el código de lectura y escritura se parece más al procesamiento habitual de cadenas
    • Si no se almacena, se reduce el espacio y el overhead de procesamiento, lo que es una de las principales razones para usar formatos binarios
  • Un formato que guarda tanto la longitud como el contenido y además agrega un byte NUL revive la misma ambigüedad, porque obliga a comprobar otra vez si la longitud almacenada incluye el byte de terminación

Subcadenas sin asignación ni copia

  • Si se fuerza la terminación NUL, también hay que colocar un byte de terminación al final de los resultados de recorte, slicing, división, tokenización y búsqueda, lo que lleva a asignar y copiar nuevas cadenas y búferes intermedios
  • Las cadenas basadas en longitud pueden devolver solo un puntero a parte del original y una longitud
String StrPrefix(String str, u64 size);
String StrPostfix(String str, u64 size);
String StrChop(String str, u64 size);
String StrSkip(String str, u64 size);
String Substr(String a, u64 min, u64 max);

String StrFindNeedle(String str, String needle);
String StrTrim(String str);
  • Los lexers y parsers para CSV, Markdown, JSON y C pueden guardar slices del búfer de entrada como nombres y valores del árbol de parseo, sin copiar cada token
  • El código posterior que usa el árbol de parseo también puede recibir los mismos slices y procesarlos sin gestión adicional de memoria

Casos en los que los centinelas siguen siendo útiles

  • Los centinelas pueden mantener invariantes de estructuras de datos y dar ventajas de rendimiento en algunas situaciones
  • En hardware y compiladores modernos, sus ventajas de rendimiento se han debilitado en la mayoría de los casos salvo los especiales, pero se mantiene el efecto de reducir la cantidad de invariantes que debe gestionar un programa
  • En comprobaciones de tokens escritas a mano, un centinela NUL permite que el bucle lea con seguridad el byte actual
    • Un lookahead como s[i] == 'f' && s[i+1] == 'o' && s[i+2] == 'r' puede fallar pronto aprovechando el orden de los bytes y la evaluación de cortocircuito
    • Las cadenas basadas en longitud deben distinguir entre un token terminado por un espacio y el fin de la entrada en sí, y el lookahead también requiere comprobaciones de límites más sistemáticas
  • La mayoría de las bibliotecas C existentes y APIs del sistema operativo exigen cadenas terminadas en NUL, por lo que hay costo de conversión
    • En Windows, como de todos modos hay que convertir UTF-8 a UTF-16, el costo de agregar un byte NUL es relativamente pequeño
    • Las restricciones impuestas por el sistema operativo y los proveedores pueden sobreestimarse, mientras que las ventajas de las cadenas basadas en longitud pueden subestimarse

Cómo aplicar inmutabilidad a una API de cadenas

  • El diseño completo de la API y la abstracción de una capa de cadenas bien terminada queda fuera del alcance, pero se recomienda la inmutabilidad como principio estructural central
  • Una vez creadas, las cadenas deben tratarse como constantes, sin modificar su contenido; las funciones que reciben cadenas y devuelven cadenas también deben preservar esta propiedad
  • Basta con garantizar la inmutabilidad en las firmas de funciones y en los límites de la API
    • Dentro de una función se pueden usar modificaciones in-place u otros procesamientos procedimentales según sea necesario
    • En el flujo de información de alto nivel se obtienen las ventajas de inmutabilidad de la programación funcional, y en la implementación de bajo nivel se mantiene la flexibilidad de la programación procedimental
  • Esta regla puede operarse como una convención de codificación y API, aunque el lenguaje o el runtime no la impongan
  • Si los tipos de cadenas y sus operaciones se distinguen claramente, mantener la regla no es una gran carga, y el codebase puede decidir por sí mismo el alcance de aplicación y cuándo relajarla
  • Un lenguaje también es una API, así que no hay que depender solo de las restricciones fijadas por un comité del lenguaje; se pueden diseñar reglas con la granularidad necesaria

Ejemplos de implementación de cadenas basadas en longitud

Restricciones de otras representaciones de cadenas

  • Miembro de arreglo flexible

    • Como SDS de Redis, almacena la longitud actual y la capacidad máxima al inicio de la estructura, y declara el último campo como miembro de arreglo flexible para ubicar los datos de caracteres
    • Puede evitar problemas de las cadenas C como el escaneo O(n) de strlen y la concatenación y gestión manual de límites
    • Es difícil que sea directamente compatible con literales de cadena y no puede soportar subcadenas eficientes, que son una ventaja central de las cadenas basadas en longitud

  • Stretch buffer

    • Un stretch buffer se parece a un arreglo dinámico, y almacena los encabezados de longitud y capacidad en un área separada antes del puntero, no en una estructura explícita
    • Además de las desventajas del miembro de arreglo flexible, impone a todos los char* una regla de metadatos casi invisible, y cada operación de cadenas significativa debe usar este encabezado como parte del modelo de API
    • La representación con puntero ofrece seguridad de tipos y evita accesos .str o ->str, pero esa ventaja por sí sola no alcanza para justificar reglas ocultas
    • Un campo separado de capacity es natural en arreglos dinámicos, pero en cadenas mezcla conceptos distintos en un solo tipo y difumina la distinción entre tipos
    • Los miembros de arreglo flexible pueden tener el mismo problema, aunque se diferencian en que pueden usar el tamaño fijo inicial como capacidad y evitar la expansión dinámica

  • Estilo Pascal

    • Las cadenas cortas de estilo Pascal suelen usar un arreglo de caracteres de tamaño fijo de 256 bytes y reservan 1 byte para la longitud o usan terminación NUL
    • Fue válido bajo restricciones reales de memoria y hardware del pasado, pero hoy existen buenas estrategias de asignación de memoria con arenas, por lo que no es adecuado salvo en situaciones especiales

Por qué las cadenas basadas en longitud deberían ser el valor por defecto

  • Las ventajas de las cadenas basadas en longitud son conocidas en algunas comunidades y entre programadores experimentados, pero muchos desarrolladores todavía nunca han considerado este tipo de implementación
  • Los materiales relacionados están dispersos en varios lugares, lo que hacía difícil comparar en conjunto la pérdida de longitud, la ambigüedad del byte de terminación, el manejo de binarios, las subcadenas, los pros y contras de los centinelas y las implementaciones alternativas
  • Si el tipo de cadena por defecto se diseña como un slice de puntero y longitud, la preservación de la información de límites, la simplificación de estados, la compatibilidad binaria y las subcadenas sin asignación pueden resolverse con un solo diseño

Lecturas relacionadas

1 comentarios

 
GN⁺ 4 시간 전
Opiniones en Lobste.rs

  • Creo que, para evitar bytes de padding, conviene cambiar el orden de los miembros de la estructura así:

    struct String  
{  
    u8* data;  
    u64 size;  
};

    En lugar de:

    struct String  
{  
    u64 size;  
    u8* data;  
};

    • En un entorno con punteros de 64 bits, ambos campos tienen el mismo tamaño, así que no hay padding en ningún orden; y en un entorno de 32 bits, un u64 capaz de representar un rango mayor que el que puede expresar un puntero ya es un desperdicio en sí mismo.
      Si se usan punteros de 128 bits como en CHERI, la primera disposición genera padding de alineación entre data y size, y la segunda al final de la estructura, así que al final se desperdicia algo de espacio.

    • La definición correcta es una forma que usa un miembro de arreglo de longitud flexible:

      typedef struct {  
  u64 len;  
  u8 buf[];  
} String;

  • El estándar de C no define los tipos u8 y u64; esa es una notación al estilo Rust.
    Representar la longitud con u64 en un entorno de 32 bits tampoco encaja bien, y en C el tipo idiomático para expresar tamaños de arreglos es size_t, así que sería más natural escribirlo así:

    struct String  
{  
    char* data;  
    size_t size;  
};

    Parece que quien escribió el texto, o el LLM que lo generó, no conoce bien C.

    • Muchos proyectos en C definen y usan u8 y u64 mediante typedef, y es una práctica muy común.
      También hay mucha gente a la que los nombres estándar uintN_t le parecen engorrosos; algunos proyectos grandes incluso son anteriores a ese estándar, y el kernel de Linux también usa esos alias.
      Más bien, esta crítica revela falta de familiaridad con proyectos en C.

  • Si has escrito C o C++ durante más de unos meses, me parece que la forma de pasar juntos el puntero y la longitud ya es algo bastante sabido.
    Casi todas las bases de código modernas en C terminan, tarde o temprano, pasando juntos el puntero a los datos y la longitud, o teniendo su propia biblioteca de strings.

    • Guardar o no la longitud es solo uno de los problemas de los strings de C; también dan muchos dolores de cabeza en la gestión del ciclo de vida.
      std::string_view en C++ moderno explicita el significado de “puedes ver este string, pero no debes modificarlo ni conservarlo”, lo que reduce mucho los bugs.
      En una API que recibe strings de C, esa restricción no es más que una promesa en la documentación.

  • Creo que el verdadero error no es guardar la longitud ni usar terminación nula, sino el concepto mismo de String, que es demasiado amplio para tener significado en cualquier contexto arbitrario.
    Los strings se usan para todo tipo de cosas más allá de simples arreglos de caracteres, e incluso la palabra “carácter” está demasiado simplificada, como el chiste de física que asume una vaca esférica en el vacío.
    Para empezar, no está claro si la “longitud” es el número de clústeres de grafemas, el número de puntos de código o la cantidad total de bytes.
    También hay que distinguir cuál es la codificación, si se muestra al usuario y necesita localización, si está saneado, o si es un valor indivisible que no hay motivo para modificar, como una clave de mapa.
    Visto desde esta perspectiva, el tipo string de las implementaciones habituales deja de ser algo deseable.

    • A veces se quejan de que Rust tiene demasiados tipos de strings, pero algunos de ellos existen para poner esta información en el sistema de tipos.
      Que yo sepa, ninguna biblioteca llama simplemente “longitud” al número de clústeres de grafemas.
      Algunos problemas se pueden resolver con la convención de fijar UTF-8 como codificación predeterminada y usar tipos separados para otras codificaciones o para arreglos de bytes; y la mayoría se puede expresar con el sistema de tipos.

  • Por lo que sé, C no tiene un concepto de string a nivel de lenguaje como el que ofrecen la mayoría de los lenguajes modernos.
    La manipulación de strings la proporciona la biblioteca estándar, no el lenguaje en sí.
    La segunda edición de K&R explica que C es un lenguaje de nivel relativamente bajo, cercano a los objetos que la computadora maneja directamente, como caracteres, números y direcciones, y que no ofrece operaciones para manipular directamente objetos compuestos completos como strings, conjuntos, listas o arreglos.
    La ausencia de estas funciones puede parecer un defecto importante, pero mantener el lenguaje pequeño tiene la ventaja de que se puede describir brevemente y aprender rápido, y de que el programador puede entender el lenguaje completo y usarlo a diario.
    Para entender por qué C se diseñó así y por qué no tiene funciones modernas que hoy se dan por sentadas, recomiendo mucho leer el prefacio y la introducción de la segunda edición de K&R.

    • Sin embargo, en el sentido limitado de que el tipo y la disposición en memoria de los literales de string determinan la forma de la biblioteca, los strings también son parte del lenguaje C.
      Esto no es muy distinto de la separación entre lenguaje y biblioteca en lenguajes de bajo nivel como Rust.

  • Existen propuestas de serialización como https://cr.yp.to/proto/netstrings.txt, y también formas que manejan hasta estructuras complejas, como https://web.archive.org/web/20230305073119/….
    Pero quizás tienen una forma demasiado simple para parsearse de manera segura, así que los defensores entusiastas de XML, JSON, YAML, Protocol Buffers y demás pueden seguir teniendo mucho trabajo.