quinta-feira, novembro 24, 2011

Um Bug Curioso Com Mais de 20 Anos de Idade

Uma das coisas mais úteis na minha "caixa de ferramentas" é um conjunto de rotinas para manipulação de B-trees. Venho usando este código, com alterações mínimas, desde que ele foi publicado na revista Dr Dobb's em 1990. Imaginem a minha surpresa ao descobrirmos um bug no código que, em um equipamento específico, simplesmente travava a execução!

B-trees

Para quem não seguiu o link acima, uma b-tree é uma estrutura de dados que armazena chaves em uma árvore e é manipulada de forma a manter a árvore balanceada (isto é, com ramos do mesmo tamanho), de forma a garantir que buscas, inserções e supressões sejam feitas em "tempo logarítmico" (isto é, à medida que o número de chaves armazenadas aumenta, o tempo para as operações aumenta com o logaritmo do número de chaves). B-trees são costumeiramente usadas para implementação de índices em sistemas de banco de dados.

No meu caso, uso b-trees quando preciso fazer consultas rápidas a dados coletados durante a operação e não faz sentido ter um gerenciador de banco de dados tradicional.

O Código

O código publicado na Dr Dobb's é de autoria de Al Stevens. É um código em C "bruto", com algumas práticas que hoje não são mais recomendadas. O próprio Al reescreveu posteriormente o código em C++ e publicou um livro a respeito.

Eu venho utilizando o código original em C. Inicialmente isto se devia ao pouco suporte a C++ nos ambientes que eu usava, posteriormente virou uma questão de não mexer em time que estava ganhando.

O Bug

Seguem abaixo as linhas de código envolvidas com o problema:

#define NODE      512         // length of a B-tree node
#define MXKEYLEN   32         // maximum key length for indexes

typedef long BT_RPTR;
#define ADR     sizeof(BT_RPTR)

/* --------- the btree node structure -------------- */
typedef struct treenode    {
   int     nonleaf;     /* 0 if leaf, 1 if non-leaf           */
   BT_RPTR prntnode;    /* parent node                        */
   BT_RPTR lfsib;       /* left sibling node                  */
   BT_RPTR rtsib;       /* right sibling node                 */
   int     keyct;       /* number of keys                     */
   BT_RPTR key0;        /* node # of keys < 1st key this node */
   BYTE    keyspace [NODE - ((sizeof(int) * 2) + (ADR * 4))];
   BYTE    spil     [MXKEYLEN];  /* for insertion excess */
} BTREE;

static BTREE trnode;

/* -------------- Delete a key  ------------- */
int btree_deletekey(int tree, BYTE *x, BT_RPTR ad)
{
   BTREE *qp;

   //...

   qp = (BTREE *) malloc (NODE);

   //...

   trnode = *qp;

   //...

}

O problema acontece na linha "trnode = *qp". Esta é uma construção incomum em C: uma atribuição de estruturas. O compilador C irá fazer uma cópia binária dos dados da origem para o destino. Ocorre que a área apontada por qp é menor que o tamanho da estrutura BTREE (para quem estiver curioso, isto se deve ao acréscimo do campo "spil" que usado pela rotina de inserção mas não é gravado em disco).

Trata-se, portanto, de um primo do buffer overflow, exceto que aqui estamos fazendo a leitura de dados não alocados. Na maioria dos casos isto acaba sendo inócuo, o que explica o funcionamento durante duas décadas em dezenas de aplicações.  Infelizmente, a sorte da gente acaba algum dia. Em um determinado equipamento o acesso a estes bytes adicionais causa o travamento do programa (sem nenhuma mensagem de erro, é claro).

A solução foi simples: substituir a atribuição por um velho memcpy (&trnode, qp, NODE).

2 comentários:

wmoecke disse...

Penso estar mui possivelmente equivocado, mas postarei meu palpite assim mesmo - na esperança de que você me corrija (e eu entenda):
- Você diz que o ponteiro qp foi definido com espaço de memória insuficiente para conter a estrutura do tipo BTREE, certo? Na linha anterior, vc define qp com o espaço de memória definido na constante NODE. Penso que esse valor seja para conter uma estrutura de nó inteira, se isso não acontece, então por que o valor da constante não pode ser alterado para que a atribuição permaneça válida?

Na instrução memcpy vc garante que será feita a cópia binária de um valor ao seu destino, mas novamente, você especificou o tamanho da constante NODE.

Eu acho que perdi alguma coisa no meio do caminho, por isso aceito a sua correção. Não sou nativo em C (prefiro nem dizer o que eu faço), mas gosto de acompanhar o código.


Abraços e um Feliz Natal a você e toda a sua família!

Daniel Quadros disse...

Realmente faltou um pouco mais de detalhes sobre o código.

No disco a btree é armazenada em blocos (nós) com o tamanho NODE (512). A estrutura destes nós é a descrita por BTREE, retirando o campo spil.

A conta na definição de keyspace (NODE - ((sizeof(int) * 2) + (ADR * 4))) garante que o tamanho do nó é exatamente NODE. Para facilitar a rotina de inserção, a estrutura BTREE possui espaço para mais uma chave (o campo spil), que não será gravada em disco.

Aumentar o valor de NODE não resolve, pois keyspace aumentará também. Uma outra solução seria trocar o malloc(NODE) por malloc (sizeof BTREE). Entretanto isto alocaria alguns bytes desnecessários.

Espero que tenha dado para entender melhor.

Feliz Natal para você e família também!