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:
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!
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!
Postar um comentário