Strings em C: um erro que perdura há 50 anos

 (longtran2904.substack.com)
1 pontos por GN⁺ 4 시간 전 | 1 comentários | Compartilhar no WhatsApp
  • As strings terminadas em NUL de C não preservam a informação de comprimento, o que leva a buscas repetidas e erros de limite; hoje, strings baseadas em comprimento, que armazenam ponteiro e tamanho juntos, são uma base de projeto mais adequada
  • Sem um comprimento explícito, chamadas a strlen e varreduras byte a byte se repetem, e snprintf, sizeof e strlen diferem quanto a incluir ou não o byte terminador, o que dificulta escrever e revisar código
  • Strings baseadas em comprimento tratam a string vazia de forma consistente com size == 0 e podem aplicar as mesmas operações de busca, divisão e fatiamento a dados binários arbitrários que incluam bytes NUL
  • É possível retornar substrings que apontam para parte da memória original, evitando alocações intermediárias e cópias em operações de corte, busca e tokenização, além de parsing de CSV, Markdown, JSON e C
  • Sentinelas ainda são úteis para manter invariantes e em algumas buscas de tokens, e conversões para APIs legadas de C e do sistema operacional continuam necessárias, mas na maior parte do código é mais simples e flexível combinar strings baseadas em comprimento com a imutabilidade nas fronteiras da API

Armazenar ponteiro e comprimento em vez de terminação NUL

  • Em C, uma string é representada por um ponteiro para um fluxo de caracteres e um byte NUL final que marca o limite
    • Isso pode ter sido razoável sob as restrições de memória e desempenho dos anos 1970, mas hoje quase não há motivo para manter esse modelo
  • A alternativa adotada por linguagens modernas e frameworks importantes é uma struct que armazena ponteiro para os dados e tamanho
struct String
{
    u8* data;
    u64 size;
};
  • Literais de string podem virar String calculando o comprimento com sizeof(s) - 1, e operações como comparação e saída usam diretamente o tamanho armazenado
  • Arrays também perdem informações como o comprimento quando decaem para ponteiros, sofrendo problemas parecidos de segurança e usabilidade

O custo de descartar a informação de comprimento

  • Quando o comprimento não é armazenado, o código que usa a string precisa chamar strlen repetidamente ou percorrer os bytes um a um, aumentando o trabalho desnecessário e a complexidade
  • Também fica mais lento e trabalhoso checar e impor comprimentos em tempo de execução, e debuggers e ferramentas de análise têm dificuldade para tratar char*, char[N] e char*[N] de forma consistente
  • Há quem veja boa parte dos problemas de memória e bugs de overflow em C como consequência desse projeto, embora exista o contra-argumento de que sentinelas por si só bastam
  • Uma string cujo comprimento é desconhecido fica mais próxima de um padrão de acesso sequencial como o de uma lista ligada do que de acesso aleatório típico de arrays
  • Quem defende a terminação em NUL argumenta que o processamento sequencial favorece algoritmos de passagem única em vez de múltiplas passagens
    • Muitos programadores, inclusive iniciantes, escrevem código presumindo que é barato obter o comprimento da string
    • Rotinas comuns de string também ficam mais naturais quando o comprimento é fornecido, e chamadas repetidas a strlen fazem com que o mesmo texto seja percorrido várias vezes no código real
    • A premissa de que menos passagens é sempre mais rápido decorre de uma compreensão equivocada de como CPUs modernas funcionam

Os diferentes significados de comprimento em snprintf, sizeof e strlen

  • Os dois inteiros de snprintf parecem se referir ao mesmo “comprimento”, mas seguem regras opostas quanto à inclusão do NUL
int snprintf(char *str, size_t size, const char *format, ...);
  • O size de entrada precisa incluir o espaço para a terminação NUL no buffer de saída, mas o valor de retorno representa o comprimento da string que teria sido produzida sem contar o byte NUL
  • Sempre que se usa uma função ou API relacionada a strings, é preciso verificar separadamente se:
    • a função grava o byte NUL por conta própria
    • é preciso acrescentar espaço para o byte NUL ao tamanho de alocação
    • o argumento de tamanho e o valor de retorno incluem ou não o byte NUL
  • sizeof("some string") inclui o byte NUL, enquanto strlen("some string") o exclui
  • Ao converter código baseado em literais para código baseado em ponteiros de tempo de execução, manter o mesmo - 1 pode gerar um bug de comprimento menor em um byte
#define TEST_STRING "some string"
size_t size = sizeof(TEST_STRING) - 1;

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

Sobrescrever repetidamente bytes NUL intermediários

  • Ao concatenar strings somando retornos de snprintf ao deslocamento, cada chamada sobrescreve o byte de terminação NUL gravado pela chamada 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);
  • Gravar bytes terminadores intermediários é desnecessário, embora o impacto em desempenho possa não ser grande
  • O problema maior é que esse comportamento não é intuitivo e leva à falsa impressão de que snprintf não faz terminação NUL
  • Como resultado, aparece código que adiciona ptr[offset] = 0; no fim, mas isso também é desnecessário e reforça ainda mais o mesmo mal-entendido

O estado duplo de string vazia e string nula

  • No modelo terminado em NUL, string vazia e ponteiro nulo acabam sendo tratados como dois estados inválidos distintos, fazendo com que o código de manipulação de strings tenha de verificar ambos
  • Strings e arrays em C# também são tipos por referência, então ler Length ou iterar sobre um valor nulo gera exceção e exige tratamento separado
  • Uma resposta comum é sempre passar e retornar string vazia ou array vazio em vez de nulo
    • Regras como String.IsNullOrEmpty, “Don’t Return Null” e “Don’t Pass Null” existem justamente para lidar com essa distinção
  • Numa struct com ponteiro e comprimento, basta avaliar size == 0 para saber se a string está vazia
    • O ponteiro pode ser nulo ou pode apontar para um endereço válido
    • Ao chegar ao fim da string ou apontar para uma substring vazia dentro de uma string maior, é possível ter comprimento 0 e ainda assim um ponteiro válido
    • Se a desreferenciação só ocorre depois da checagem do comprimento, até um ponteiro para memória já liberada não será acessado quando o comprimento for 0

Usar a mesma representação para dados binários

  • Strings baseadas em comprimento não dependem de sentinela, então conseguem armazenar com segurança dados binários arbitrários com bytes NUL incluídos
  • Assim como funções ASCII podem funcionar com UTF-8, operações baseadas em comprimento como varredura, divisão, trim e slicing também podem ser aplicadas a arrays de bytes
  • Em formatos binários terminados em NUL, ainda é preciso decidir separadamente se o byte terminador será armazenado
    • Se for armazenado, o código de leitura e escrita fica mais próximo do processamento tradicional de strings
    • Se não for armazenado, reduz-se overhead de espaço e processamento, o que é uma das principais razões para usar formato binário
  • Um formato que armazena comprimento e conteúdo e ainda anexa um byte NUL reintroduz a mesma ambiguidade, porque volta a ser necessário confirmar se o comprimento armazenado inclui ou não o terminador

Substrings sem alocação nem cópia

  • Quando se exige terminação NUL, operações como trim, slicing, split, tokenização e busca precisam colocar um byte terminador também no fim dos resultados, o que leva a alocação e cópia de novas strings e buffers intermediários
  • Strings baseadas em comprimento podem simplesmente retornar um ponteiro e um comprimento que apontam para parte do original
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);
  • Lexers e parsers para CSV, Markdown, JSON e C podem guardar cada token como um slice do buffer de entrada, sem copiar os dados, usando esses slices como nomes e valores na árvore de parsing
  • O código posterior que consome a árvore também pode receber os mesmos slices e processá-los sem gerenciamento adicional de memória

Casos em que sentinelas ainda são úteis

  • Sentinelas ainda ajudam a manter invariantes de estruturas de dados e podem trazer vantagens de desempenho em alguns cenários
  • Em hardware e compiladores modernos, esses ganhos de desempenho ficaram mais fracos na maioria dos casos, exceto em situações específicas, mas o efeito de reduzir a quantidade de invariantes que o programa precisa manter continua valioso
  • Em checagem manual de tokens, o sentinela NUL permite que o loop leia o byte atual com segurança
    • Um lookahead como s[i] == 'f' && s[i+1] == 'o' && s[i+2] == 'r' pode falhar cedo aproveitando a ordem dos bytes e a avaliação de curto-circuito
    • Em strings baseadas em comprimento, é preciso distinguir quando o token termina em espaço e quando a própria entrada termina, além de exigir verificações de limite mais sistemáticas no lookahead
  • A maior parte das bibliotecas C existentes e APIs de sistema operacional exige strings terminadas em NUL, o que gera custo de conversão
    • No Windows, já é preciso converter UTF-8 para UTF-16, então o custo de adicionar um byte NUL é relativamente pequeno
    • As restrições impostas por sistemas operacionais e fornecedores podem ser superestimadas, enquanto as vantagens de strings baseadas em comprimento podem ser subestimadas

Como aplicar imutabilidade à API de strings

  • O projeto completo de API e abstrações de uma camada de strings bem acabada está fora do escopo, mas o princípio estrutural central recomendado é a imutabilidade
  • Depois de criada, a string é tratada como uma constante sem alteração de conteúdo, e funções que recebem string e retornam string também devem preservar essa propriedade
  • Basta garantir a imutabilidade nas assinaturas das funções e nas fronteiras da API
    • Dentro da função, ainda é possível usar modificação in-place ou outros procedimentos conforme necessário
    • No fluxo superior de informação, obtêm-se as vantagens da imutabilidade da programação funcional, enquanto a implementação de baixo nível mantém a flexibilidade da programação procedural
  • Essa regra pode ser aplicada como convenção de código e de API mesmo sem imposição da linguagem ou do runtime
  • Se tipos e operações de string forem claramente distinguidos, o custo de manter a regra não é alto, e a base de código pode definir por conta própria até onde ela vale e quando afrouxá-la
  • Como a linguagem também é uma API, não é necessário depender apenas das restrições fixadas por comitês de linguagem; é possível desenhar as regras com o nível de granularidade necessário

Exemplos de implementação de strings baseadas em comprimento

Limitações de outras representações de string

  • Membro de array flexível

    • Como no SDS do Redis, a parte inicial da struct armazena o comprimento atual e a capacidade máxima, e o último campo é declarado como membro de array flexível para acomodar os caracteres
    • Isso evita problemas de strings em C como a varredura O(n) de strlen e o gerenciamento manual de concatenação e limites
    • É difícil obter compatibilidade direta com literais de string e não há suporte eficiente a substrings, que é uma das principais vantagens das strings baseadas em comprimento

  • Stretch buffer

    • Um stretch buffer se parece com um array dinâmico, mas guarda o cabeçalho de comprimento e capacidade numa área separada antes do ponteiro, e não numa struct explícita
    • Além das desvantagens do membro de array flexível, isso impõe a quase todo char* uma regra de metadados praticamente invisível, e esse cabeçalho precisa virar parte do modelo da API em qualquer operação de string relevante
    • A representação por ponteiro oferece segurança de tipo e evita acessos .str ou ->str, mas esse benefício por si só dificilmente justifica regras ocultas
    • Um campo separado de capacity é natural em arrays dinâmicos, mas em strings mistura conceitos distintos no mesmo tipo e enfraquece a distinção entre categorias
    • O mesmo problema pode existir com membros de array flexível, mas nesse caso ao menos é possível usar o tamanho fixo inicial como capacidade e evitar crescimento dinâmico

  • Estilo Pascal

    • Strings curtas em estilo Pascal normalmente usam um array de caracteres de tamanho fixo de 256 bytes, reservando 1 byte para o comprimento ou recorrendo à terminação NUL
    • Isso fazia sentido sob restrições reais de memória e hardware do passado, mas hoje estratégias melhores como alocação em arena tornam essa escolha inadequada fora de casos muito específicos

Por que strings baseadas em comprimento deveriam ser o padrão

  • As vantagens das strings baseadas em comprimento são conhecidas em algumas comunidades e entre programadores experientes, mas muitos desenvolvedores ainda nunca consideraram esse tipo de implementação
  • Como o material relevante está espalhado em vários lugares, era difícil comparar de forma conjunta perda de comprimento, ambiguidade do byte terminador, processamento binário, substrings, vantagens e desvantagens de sentinelas e implementações alternativas
  • Se o tipo de string padrão for um slice formado por ponteiro e comprimento, um único projeto resolve preservação da informação de limite, simplificação de estados, compatibilidade com binários e substrings sem alocação

Leituras relacionadas

1 comentários

 
GN⁺ 4 시간 전
Opiniões no Lobste.rs

  • Para evitar bytes de padding, parece melhor trocar a ordem dos membros da struct para algo assim

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

    em vez de:

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

    • Em ambientes com ponteiros de 64 bits, os dois campos têm o mesmo tamanho, então não há padding em nenhuma das ordens; em ambientes de 32 bits, um u64 maior do que o intervalo representável por um ponteiro já é desperdício por si só
      Se usar ponteiros de 128 bits, como no CHERI, a primeira disposição cria padding de alinhamento entre data e size, e a segunda cria padding no fim da struct, então no fim sempre há algum desperdício de espaço

    • A definição correta seria usar um membro de array de tamanho variável

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

  • O padrão C não define os tipos u8 e u64; essa é uma notação ao estilo Rust
    Também não faz muito sentido usar u64 para representar comprimento em um ambiente de 32 bits, e como o tipo idiomático em C para representar tamanho de array é size_t, seria mais natural escrever assim

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

    Parece que quem escreveu o texto, ou o LLM que o gerou, não entende C direito

    • Muitos projetos em C usam typedef para definir u8 e u64, e isso é uma prática muito comum
      Muita gente acha os nomes padrão uintN_t incômodos, vários projetos grandes são mais antigos que esse padrão, e o kernel do Linux também usa aliases desse tipo
      Na verdade, essa crítica é que revela falta de familiaridade com projetos em C

  • Se você já escreveu C ou C++ por mais de alguns meses, passar ponteiro e comprimento juntos não deveria ser uma ideia já bem conhecida?
    Quase todo codebase moderno em C acaba passando um ponteiro para os dados junto com o tamanho, ou então cria sua própria biblioteca de strings

    • Armazenar o comprimento é só um dos problemas das strings em C; gerenciamento de tempo de vida também causa muita dor de cabeça
      O std::string_view do C++ moderno deixa explícito o significado de “você pode olhar para esta string, mas não deve modificá-la nem armazená-la”, o que reduz bastante os bugs
      Em APIs que recebem strings em C, esse tipo de restrição normalmente existe só como um acordo documentado

  • O verdadeiro erro não seria armazenar o comprimento ou usar terminação nula, mas sim o próprio conceito amplo demais de String, que é genérico demais para ter significado em contextos arbitrários
    Strings são usadas para todo tipo de coisa além de um simples array de caracteres, e até a palavra “caractere” aqui é uma simplificação excessiva, como naquela piada de física da vaca esférica no vácuo
    Nem está claro se “comprimento” significa número de grafemas, número de code points ou total de bytes
    Também é preciso distinguir qual é a codificação, se isso será exposto ao usuário e precisa de localização, se foi sanitizado, ou se é um valor indivisível que não faz sentido modificar, como uma chave de mapa
    Vendo por esse ângulo, você deixa de querer um tipo de string de implementação genérica

    • Às vezes reclamam que Rust tem tipos de string demais, mas parte disso existe justamente para colocar esse tipo de informação no sistema de tipos
      Não conheço nenhuma biblioteca que chame simplesmente de “comprimento” a contagem de grafemas
      Dá para resolver parte do problema adotando UTF-8 como codificação padrão e usando tipos separados para outras codificações ou arrays de bytes; o restante, em grande parte, pode ser expresso no sistema de tipos

  • Pelo que sei, C não tem um conceito de string no nível da linguagem como a maioria das linguagens modernas oferece
    Manipulação de strings é fornecida pela biblioteca padrão, não pela linguagem em si
    A 2ª edição de K&R explica que C é uma linguagem relativamente de baixo nível, mais próxima de coisas que o computador manipula diretamente, como caracteres, números e endereços, e que ela não fornece operações para manipular diretamente objetos compostos inteiros, como strings, conjuntos, listas e arrays
    Isso pode parecer uma grande deficiência, mas manter a linguagem pequena tem vantagens: ela pode ser descrita de forma breve, aprendida rapidamente, e o programador consegue entender a linguagem inteira e usá-la no dia a dia
    Para entender por que C foi projetada assim e por que faltam recursos modernos que hoje parecem óbvios, eu recomendaria fortemente ler o prefácio e a introdução da 2ª edição de K&R

    • Ainda assim, no sentido limitado de que o tipo e o layout de memória dos literais de string determinam a forma da biblioteca, strings também são parte da linguagem C
      Isso não é tão diferente da separação entre linguagem e biblioteca em linguagens de baixo nível como Rust

  • Existem propostas de serialização como https://cr.yp.to/proto/netstrings.txt, e também formatos que lidam até com structs complexas, como https://web.archive.org/web/20230305073119/…
    Mas talvez o formato seja simples demais para fazer parsing com segurança, porque os defensores fervorosos de XML, JSON, YAML, Protocol Buffers e afins continuam tendo muito trabalho