Building get_next_line: Uma função de 93 linhas que explica file descriptors, buffers e a fronteira das syscalls

1.000.000 de chamadas read() de 1 byte custam 100 segundos só de latência. Minha implementação lê de BUFFER_SIZE 1 a 10.000.000 sem vazar um byte. Esta é a história de como uma única função me forçou a entender file descriptors, buffers do kernel e a fronteira entre user space e kernel.

O problema

Escreva uma função que retorna uma linha por vez de um file descriptor. Compile com -D BUFFER_SIZE=n, onde n pode ser qualquer valor de 1 a 10.000.000. Sem leaks, sem UB, sem crash, em qualquer tamanho de buffer. Uma linha pode ser tão curta quanto "\n" ou o arquivo inteiro sem uma única quebra de linha.

As restrições são o ponto. Você não pode conhecer a entrada antecipadamente, e o chamador não libera o que você não alocou corretamente. Isto é streaming na sua forma mais crua em C.

O que read() realmente custa

Antes de desenhar qualquer coisa, eu fiz as contas do primitivo. read() é uma system call: o processo para, a CPU troca do ring 3 para o ring 0, o kernel valida o fd, vai até o disco ou page cache, e copia os bytes de volta para o user space. Cada travessia custa centenas a milhares de ciclos de CPU, um pedágio fixo, quer você peça 1 byte ou 4096.

Se o disco tem latência de ~0.1ms (SSD) e você faz 1.000.000 de reads de 1 byte, são 100 segundos de latência pura de syscall antes de um único byte ser processado. Ler 4096 bytes de uma vez custa quase o mesmo que ler 1. É por isso que a libc bufferiza o printf, 100 chamadas de printf não viram 100 system calls. Todo sistema real é cheio de buffers exatamente por isso.

Por que BUFFER_SIZE é um pedido, não um tamanho de linha

BUFFER_SIZE é quantos bytes seu programa pede ao kernel por chamada. O kernel não garante a quantidade. Ele devolve o que leu, e esse retorno é a única verdade. O design mais ingênuo, char buffer[BUFFER_SIZE] na stack, dá segfault com 10.000.000: a stack do Linux tem ~8MB por padrão. A correção tem uma palavra: heap. buffer = malloc(BUFFER_SIZE + 1) move 10MB para onde memória é só memória, e o +1 existe porque strings em C terminam em '\0', o invariante que separa uma string de lixo.

O único estado que a função pode manter

get_next_line(fd) tem assinatura fixa e globais são proibidos, mas ela precisa lembrar bytes que já consumiu do kernel. A resposta é static: um local static vive em .bss, zerado pelo SO antes do main, enquanto a visibilidade continua dentro da função. A mesma palavra, dois significados em C: storage duration vs linkage. Um contador prova: um local imprime 1, 1, 1 entre chamadas; um static imprime 1, 2, 3.

O remainder existe por causa de um fato duro dos file descriptors: o kernel mantém o offset de leitura, e ele só anda para frente. Se você leu 42 bytes e o \n estava no byte 5, os outros 37 bytes já foram consumidos, não existe "desler". O fd é um int que indexa a tabela do kernel de arquivos abertos (é por isso que o primeiro open() retorna 3: 0, 1 e 2 são stdin, stdout, stderr). Seu programa nunca vê esse estado avançar; o remainder é como você o espelha no user space.

O tipo de retorno é parte do contrato

read() retorna ssize_t, não size_t, porque precisa caber tanto "bytes lidos" quanto -1 (erro). Com size_t, -1 vira SIZE_MAX, cerca de 18 quintilhões em 64 bits, e a comparação bytes == -1 nunca é verdadeira. Meu loop interno de leitura espelha o read() com um protocolo de três estados: -1 erro, 0 EOF, 1 linha obtida. O tipo de um retorno é parte da API.

Resultados

A implementação tem 93 linhas: ler e acumular até uma quebra de linha ou EOF, extrair a linha, guardar o excedente. O buffer é alocado no heap com espaço para o terminador, e após cada leitura o byte no índice bytes recebe '\0', terminação exatamente um byte após o último dado válido. Testado na suíte completa: 128 casos com BUFFER_SIZE 1, 42, 9999 e 10.000.000, zero falhas, zero leaks. Lê de stdin e de arquivos, devolve a última linha sem \n final no EOF, e retorna NULL para sempre depois disso (read() no EOF retorna 0 instantaneamente; sem loop infinito).

Trade-offs

A parte honesta. Cada leitura faz append via strjoin, que copia o remainder acumulado inteiro, O(n²) numa linha longa patológica lida através de um buffer pequeno. Passou em todos os testers, e continua quadrático onde um design de tail-copy seria linear. A variável static única também significa um fd por vez: intercalar dois fds corrompe os dois remainders (o bonus da 42, um único static gerenciando vários fds via linked list, existe exatamente para isso). E o chamador é dono de cada linha retornada: a função garante alocação e liberação do próprio estado interno, e nada mais. Simples, correto e sabidamente subótimo nos cantos.

Lições

  • Performance em I/O é uma história sobre a fronteira user/kernel, não sobre código esperto. Conte as travessias, depois bufferize.
  • Memória do malloc vem suja. O '\0' é uma convenção que só o programador restaura.
  • O tipo de retorno é um contrato. size_t transforma -1 em 18 quintilhões de falsidades silenciosas.
  • Complexidade se esconde em detalhes de API: um strjoin O(n) dentro de um loop vira O(n²) sem mudar a forma de uma única linha.
  • Newline no EOF não é erro; a string vazia não é EOF; NULL não é linha. Streaming é 90% convenções.

Uma nota sobre ferramentas

Man pages de read(2) e malloc(3); valgrind para a disciplina de leaks; a Norma da 42 (25 linhas por função, 80 colunas) como função forçadora; e um tester de 128 casos com tamanhos extremos de buffer como único juiz honesto.

Código: github.com/matheus896/GNL_42