为什么在trie中释放字符串会导致malloc错误？

Question

我需要帮助理解我从中得到的调试消息malloc.我编写了一个函数,通过在trie上递归遍历该字符串并释放其他字符串未使用的所有内容,从trie中删除指定的字符串.这包括转到最后一个节点并释放它,然后返回堆栈并检查每个级别以查看该级别是否也被其他字符串未使用,如果是,则释放它们.一旦它到达第一个被其他东西使用的东西,它就会停止.

当我只删除一个字符串时,该函数似乎工作正常,但当我删除第二个字符串时,我开始遇到问题.到目前为止,这是我的程序的整个代码(请注意,有些行是用于测试/调试目的而不是程序的组成部分):

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct node {
    char chr;
    bool end;
    struct node *children[128];
};

void add( struct node *, char * );
void del( struct node *, char * );
bool isMember( struct node *, char * );

bool recursiveDel( struct node *, char * );
// del is really just a dummy function that calls recursiveDel.

int main( int argc, char **argv ){
    struct node *trie = (struct node *) malloc( sizeof( struct node ) );
    for( int i = 1; i < argc; i++ ){
        add( trie, argv[i] );
    }
    del( trie, argv[1] );
    del( trie, argv[2] );
    for( int i = 1; i < argc; i++ ){
        printf( "%d\n", isMember( trie, argv[i] ) );
    }
    return 0;
}

void add( struct node *trie, char *str ){
    int i = 0;
    while( str[i] ){
        // Check/goto next node
        // If NULL, create next node
        if( trie->children[str[i]] == NULL )
            trie->children[str[i]] = (struct node *) malloc( sizeof( struct node ) );
        trie = trie->children[str[i++]];
    }
    trie->end = true;
}

void del( struct node *trie, char *str ){
    if( isMember( trie, str ) ){
        recursiveDel( trie, str );
    }
}

bool isMember( struct node *trie, char *str ){
    int i = 0;
    struct node *cur = trie;
    while( str[i] ){
        if( trie->children[str[i]] == NULL ) return false;
        else trie = trie->children[str[i++]];
    }
    return trie->end;
}

// Features of this function:
// When it gets to the leaf, it deletes that node and then starts going back up the call stack
// Each call passes a Boolean value back up the call stack.
// This boolean value indicates whether or not the node was deleted.
// If the value returned from the lower node is true, then that means check the next node up to see if it should be deleted.
// If false do nothing, because there are other strings using this node.
bool recursiveDel( struct node *trie, char *str ){
    printf( "%p, %d, %s\n", trie, trie->end, str );
    if( trie->end ){
        free( trie );
        return true;
    }
    bool deleted = recursiveDel( trie->children[str[0]], str+1 );
    if( deleted ){
        int used = 0;
        // Loop checks to see if the node
        // is used by any other strings.
        for( int i = 0; i < 128; i++ ){
            if( trie->children[i] ){
                used++;
                break;
            }
        }
        if( used <= 1 ){
            free( trie );
            return true;
        }
    }
    return false;
}

问题似乎发生在这个块中,我尝试释放字符串的终止节点:

    if( trie->end ){
        free( trie );
        return true;
    }

我收到一条消息,说该节点因为不存在而无法释放...

bash-3.2$ ./trie hello world
0x7fd370802000, 0, hello
0x7fd370800600, 0, ello
0x7fd370802600, 0, llo
0x7fd370802c00, 0, lo
0x7fd370803200, 0, o
0x7fd370803800, 1,
0x7fd370802000, 0, world
0x7fd370803e00, 0, orld
0x7fd370804400, 0, rld
0x7fd370804a00, 0, ld
0x7fd370805000, 0, d
0x7fd370805600, 1,
trie(43216,0x7fff7818e000) malloc: *** error for object 0x7fd370802000: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
Abort trap: 6
bash-3.2$

似乎是这样的情况,当我尝试删除第二个字符串时,它按预期进入最后一个节点,但是然后不是回到堆栈,它继续前进并尝试在此之后释放下一个节点,这显然它无法做到,因为这是一个叶子节点.

看起来它可能是未定义的行为,但同时,程序以一种非常可预测的方式失败 - 第一次删除字符串总是成功,而第二次删除字符串总是不成功.我无法做出这样的正面或反面.

此外,malloc失败时给出的地址似乎有点偏.最后几个地址都有所不同0x600,但这个地址与上一个地址不同0xa00.我知道堆内存分配是不可预测的,但我只是想我会指出这一点.

更奇怪的是malloc,尽管事实上失败的free操作紧跟在最后一个之后,但是给出的地址与最后打印的地址不同printf.这几乎似乎表明编译器正在插入printf行和if( trie->end ) free( trie )部件之间的指针前进操作.常识表明这很荒谬,但我不知道任何其他解释.

Answer 1

代码的相关部分:

int main( int argc, char **argv ){
    struct node *trie = (struct node *) malloc( sizeof( struct node ) );
    for( int i = 1; i < argc; i++ ){
        add( trie, argv[i] );
    }
    …
}

void add( struct node *trie, char *str ){
    int i = 0;
    while( str[i] ){
        if( trie->children[str[i]] == NULL )
//          ^^^^^^^^^^^^^^^^^^^^^^

您正在分配a struct node,然后在.children[...]不初始化的情况下访问其指针.未定义的行为.

您需要node在分配它们之后初始化它们.