Test Suite Fails, Segmentation Fault

[cadaniluk]

Bug Report

I built the wallet_new branch with ./autogen.sh && ./configure --enable-debug && make check.

Running tests with ./tests:

PASSED - test_sha_256()
PASSED - test_sha_512()
PASSED - test_sha_hmac()
PASSED - test_utils()
PASSED - test_cstr()
PASSED - test_buffer()
PASSED - test_serialize()
PASSED - test_memory()
PASSED - test_random()
PASSED - test_bitcoin_hash()
PASSED - test_base58check()
PASSED - test_aes()
PASSED - test_bip32()
PASSED - test_ecc()
PASSED - test_vector()
PASSED - test_tx_serialization()
PASSED - test_invalid_tx_deser()
PASSED - test_tx_sign()
PASSED - test_tx_sighash()
PASSED - test_tx_sighash_ext()
PASSED - test_tx_negative_version()
PASSED - test_block_header()
PASSED - test_script_parse()
PASSED - test_script_op_codeseperator()
PASSED - test_eckey()
xpub: tpubDAenfwNu5GyCJWv8oqRAckdKMSUoZjgVF5p8WvQwHQeXjDhAHmGrPa4a4y2Fn7HF2nfCLefJanHV3ny1UY25MRVogizB2zRUdAo7Tr9XAjm
Segmentation fault (core dumped)

test-suite.log:

==================================
   libbtc 0.1: ./test-suite.log
==================================

# TOTAL: 1
# PASS:  0
# SKIP:  0
# XFAIL: 0
# FAIL:  1
# XPASS: 0
# ERROR: 0

.. contents:: :depth: 2

FAIL: tests
===========

FAIL tests (exit status: 139)

System Info:
OS: Fedora 27, 64-Bit
uname -r: 4.15.15-300.fc27.x86_64
gdb version: GNU gdb (GDB) Fedora 8.0.1-36.fc27
glibc 2.26

Analysis

Running the tests program with gdb (gdb ./tests) yields the following stack trace:

#0  btc_btree_tdestroy (freekey=<optimized out>, root=0xde4350)
    at ./include/btc/utils.h:74
#1  btc_wallet_free (wallet=0xde5570) at src/wallet.c:283
#2  0x00000000004093c8 in test_wallet_basics () at test/wallet_tests.c:204
#3  0x0000000000401ce6 in main () at test/unittester.c:118

After experimenting a bit, I found that after the insertion performed by tsearch, the left node pointer is 0x1, unlike the right one, which is 0x0. Breaking at src/wallet.c:537:

Breakpoint 1, btc_wallet_next_addr (wallet=wallet@entry=0xde5570)
    at src/wallet.c:537
537	    btc_wallet_addr* checknode = tsearch(waddr, &wallet->waddr_rbtree, btc_wallet_addr_compare);
(gdb) p wallet->waddr_rbtree
$1 = (void *) 0x0
(gdb) n
538	    vector_add(wallet->waddr_vector, waddr);
(gdb) p wallet->waddr_rbtree
$2 = (void *) 0xde4350
(gdb) p ((struct btc_btree_node *) wallet->waddr_rbtree)->left
$3 = (struct btc_btree_node *) 0x1
(gdb) p ((struct btc_btree_node *) wallet->waddr_rbtree)->right
$4 = (struct btc_btree_node *) 0x0
(gdb) 

This is because, as explained in a comment in misc/tsearch.c, if malloc returns aligned addresses, the lower bits of the left node's address are zero anyway and can be used to store whether the node is a red or a black one in the LSB. The definition of SETLEFT, the macro used to set the left node's value, is defined as:

#define SETLEFT(N,L) (N)->left_node = (((N)->left_node & (uintptr_t) 0x1) \
| (uintptr_t)(L))

In btc_btree_tdestroy:74 in file include/btc/utils.h the tree is destroyed recursively, but the base case is r == 0, so if the node from the red-black tree is red, but has no children, this check might fail and the function could end up destroying a pointer with value 0x1, which has undefined behavior and might result in a segmentation fault, as it does in my case.

Solution

The easy fix is to check for r == 0 || (uintptr_t) r == 1 instead of just r == 0 and clearing the LSB of r afterwards, but then you rely on the implementation of tsearch. I would not write it like that.
(r == NULL seems cleaner to me anyway.)

I just discovered your comments:

/* support substitude for GNU only tdestroy */
/* Let's hope the node struct is always compatible */

With this patch, they introduced a compile-time switch, which, if possible, includes the color bit in the left node, rendering the r == 0 insufficient. If the compiler determines that this is not possible, because malloc returns unaligned addresses, a separate struct member to indicate whether the node is red or black. Either way, the code is not well-defined: either the check fails and it ends up trying to destroy the address 0x1, which is undefined, or your struct is not compatible because of the additional red/black flag, also rendering the code undefined.
I would suggest using tdestroy anyway, which is part of the proper interface. It is a GNU extension, but you use -std=gnu99 anyway.

However, the cleanest way would be to quit using tsearch and friends and rolling your own red-black tree implementation entirely. tsearch is only supposed to be, and can, in a clean, portable way, only be used together with the other functions of the <search.h> interface and if you opt against using the other functions, it does not make sense to use tsearch either, I think.