当运行通过 valgrind 尝试来自 cs50/pset5 speller 的字典时上下文错误

Question

我正在研究哈佛的 CS50 pset5，在该课程中，您的任务是将字典上传到您选择的数据结构中，然后对给定的文本进行拼写检查。

这次我决定使用 trie，它的拼写检查正确，没有内存泄漏。

但是，运行 valgrind -v ./speller texts/lalaland.txt 似乎 return 9 个上下文错误。

鉴于没有内存泄漏，我似乎无法弄清楚这里到底是什么问题。

==5897== 
==5897== HEAP SUMMARY:
==5897==     in use at exit: 0 bytes in 0 blocks
==5897==   total heap usage: 367,084 allocs, 367,084 frees, 82,227,504 bytes allocated
==5897== 
==5897== All heap blocks were freed -- no leaks are possible
==5897== 
==5897== ERROR SUMMARY: 9913647 errors from 9 contexts (suppressed: 0 from 0)
==5897== 
==5897== 1 errors in context 1 of 9:
==5897== Conditional jump or move depends on uninitialised value(s)
==5897==    at 0x422434: unload_node (dictionary2.c:28)
==5897==    by 0x42362C: unload (dictionary2.c:170)
==5897==    by 0x421564: main (speller.c:152)
==5897==  Uninitialised value was created by a heap allocation
==5897==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5897==    by 0x422E91: load (dictionary2.c:104)
==5897==    by 0x420992: main (speller.c:40)
==5897== 
==5897== 
==5897== 216 errors in context 2 of 9:
==5897== Conditional jump or move depends on uninitialised value(s)
==5897==    at 0x422B80: check (dictionary2.c:73)
==5897==    by 0x421363: main (speller.c:112)
==5897==  Uninitialised value was created by a heap allocation
==5897==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5897==    by 0x423216: load (dictionary2.c:131)
==5897==    by 0x420992: main (speller.c:40)
==5897== 
==5897== 
==5897== 221 errors in context 3 of 9:
==5897== Conditional jump or move depends on uninitialised value(s)
==5897==    at 0x422434: unload_node (dictionary2.c:28)
==5897==    by 0x422534: unload_node (dictionary2.c:30)
==5897==    by 0x42362C: unload (dictionary2.c:170)
==5897==    by 0x421564: main (speller.c:152)
==5897==  Uninitialised value was created by a heap allocation
==5897==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5897==    by 0x423216: load (dictionary2.c:131)
==5897==    by 0x420992: main (speller.c:40)
==5897== 
==5897== 
==5897== 739 errors in context 4 of 9:
==5897== Conditional jump or move depends on uninitialised value(s)
==5897==    at 0x4213E7: main (speller.c:119)
==5897==  Uninitialised value was created by a heap allocation
==5897==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5897==    by 0x423216: load (dictionary2.c:131)
==5897==    by 0x420992: main (speller.c:40)
==5897== 
==5897== 
==5897== 739 errors in context 5 of 9:
==5897== Conditional jump or move depends on uninitialised value(s)
==5897==    at 0x4213C0: main (speller.c:119)
==5897==  Uninitialised value was created by a heap allocation
==5897==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5897==    by 0x423216: load (dictionary2.c:131)
==5897==    by 0x420992: main (speller.c:40)
==5897== 
==5897== 
==5897== 739 errors in context 6 of 9:
==5897== Conditional jump or move depends on uninitialised value(s)
==5897==    at 0x422DD5: check (dictionary2.c:83)
==5897==    by 0x421363: main (speller.c:112)
==5897==  Uninitialised value was created by a heap allocation
==5897==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5897==    by 0x423216: load (dictionary2.c:131)
==5897==    by 0x420992: main (speller.c:40)
==5897== 
==5897== 
==5897== 9185 errors in context 7 of 9:
==5897== Conditional jump or move depends on uninitialised value(s)
==5897==    at 0x422434: unload_node (dictionary2.c:28)
==5897==    by 0x422534: unload_node (dictionary2.c:30)
==5897==    by 0x422534: unload_node (dictionary2.c:30)
==5897==    by 0x42362C: unload (dictionary2.c:170)
==5897==    by 0x421564: main (speller.c:152)
==5897==  Uninitialised value was created by a heap allocation
==5897==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5897==    by 0x423216: load (dictionary2.c:131)
==5897==    by 0x420992: main (speller.c:40)
==5897== 
==5897== 
==5897== 367081 errors in context 8 of 9:
==5897== Conditional jump or move depends on uninitialised value(s)
==5897==    at 0x423205: load (dictionary2.c:127)
==5897==    by 0x420992: main (speller.c:40)
==5897==  Uninitialised value was created by a heap allocation
==5897==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5897==    by 0x422E91: load (dictionary2.c:104)
==5897==    by 0x420992: main (speller.c:40)
==5897== 
==5897== 
==5897== 9534726 errors in context 9 of 9:
==5897== Conditional jump or move depends on uninitialised value(s)
==5897==    at 0x422434: unload_node (dictionary2.c:28)
==5897==    by 0x422534: unload_node (dictionary2.c:30)
==5897==    by 0x422534: unload_node (dictionary2.c:30)
==5897==    by 0x422534: unload_node (dictionary2.c:30)
==5897==    by 0x42362C: unload (dictionary2.c:170)
==5897==    by 0x421564: main (speller.c:152)
==5897==  Uninitialised value was created by a heap allocation
==5897==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5897==    by 0x423216: load (dictionary2.c:131)
==5897==    by 0x420992: main (speller.c:40)
==5897== 
==5897== ERROR SUMMARY: 9913647 errors from 9 contexts (suppressed: 0 from 0)

dictionary2.c :

// Implements a dictionary's functionality

#include "dictionary.h"

// Define node to be used in hashtable
typedef struct node
{
    bool is_word;
    struct node *children[27];
}
node;

// Define root
node *root;

// Global variable to track word count
unsigned int word_count = 0;

// Global boolean to track whether dictionary was loaded or not
bool loaded = false;

// Helper function to unload trie nodes
void unload_node(node *firstnode)
{

    for (int i = 0; i < 27; i++)
    {
        if (firstnode->children[i] != NULL)         // line 28
        {
            unload_node(firstnode->children[i]);    // line 30
        }
    }
    free(firstnode);
    return;
}


// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // TODO
    // Copy the word as word only has read access
    int length = strlen(word);
    char word_copy[length + 1];

    // Lowercase the word
    for (int i = 0; i < length; i++)
    {
        word_copy[i] = tolower(word[i]);
    }

    // Nul terminate the string
    word_copy[length] = '[=13=]';

    // Direct traversal pointer to root
    node *trav = root;

    for (int i = 0, n = strlen(word_copy); i < n; i++)
    {
        // Find numerical value of letter
        int alphanum;

        if (word_copy[i] == 39)
        {
            // If it is apostrophe, allocate last slot in array
            alphanum = 26;
        }
        else
        {
            alphanum = word_copy[i] - 97;
        }

        if (trav->children[alphanum] != NULL)       // line 73
        {
            trav = trav->children[alphanum];
        }
        else
        {
            return false;
        }
    }

    return trav->is_word;       // line 83
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // TODO

    // Open dictionary file
    FILE *inptr = fopen(dictionary, "r");
    if (inptr == NULL)
    {
        fclose(inptr);
        fprintf(stderr, "Could not open %s.\n", dictionary);
        return 2;
    }

    // Scan through every word in dictionary and store into new node
    char wordBuffer[LENGTH + 1];

    // Malloc root node
    root = (node*) malloc(sizeof(node));        // line 104

    while (fscanf(inptr, "%s", wordBuffer) != EOF)
    {
        // Create traversal pointer to the root
        node *trav = root;

        for (int i = 0, n = strlen(wordBuffer); i < n; i++)
        {
            // Find numeric value of letter
            int alphanum;

            if (wordBuffer[i] == 39)
            {
                // If it is apostrophe, allocate last space in children's array
                alphanum = 26;
            }
            else
            {
                alphanum = wordBuffer[i] - 97;
            }


            if (trav->children[alphanum] == NULL)       // line 127
            {

                // If node does not exist in array slot, allocate memory for new node
                trav->children[alphanum] = malloc(sizeof(node));        // line 131

            }

            // Redirect trav to child
            trav = trav->children[alphanum];

        }

        trav->is_word = true;

        word_count++;
    }

    fclose(inptr);
    loaded = true;

    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    // TODO
    if (loaded)
    {
        return word_count;
    }
    else
    {
        return 0;
    }
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // TODO
    node *trav = root;
    unload_node(trav);      // line 170
    return true;
}

非常感谢任何帮助:)

Answer 1

让我们看看 9 个上下文中的第 8 个：

==5897== 367081 errors in context 8 of 9:
==5897== Conditional jump or move depends on uninitialised value(s)
==5897==    at 0x423205: load (dictionary2.c:127)
==5897==    by 0x420992: main (speller.c:40)
==5897==  Uninitialised value was created by a heap allocation
==5897==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5897==    by 0x422E91: load (dictionary2.c:104)
==5897==    by 0x420992: main (speller.c:40)
==5897==

Conditional jump or move depends on uninitialised value(s)

这意味着您正在执行 if (something)，但从未初始化 something。它在第 127 行：

if (trav->children[alphanum] == NULL)

未初始化的值必须是trav->children[alphanum]。向上看你的循环，你会发现你有

root = (node*) malloc(sizeof(node));        // line 104
...
node *trav = root;

您 malloced root 但在尝试对其进行分支之前从未在其中实际设置任何值。在使用之前，您应该将 root->children 中的条目清空。

你也可以通过查看错误的后半部分来了解这一点：

Uninitialised value was created by a heap allocation

它指向第 104 行，告诉您您在第 104 行的分配创建了一个未初始化的值，这导致了相同的结论。

Answer 2

补充一下@fennel 的回答，我的 load 函数在遇到单词的最后一个字母时似乎有问题，因为它会创建一个新节点来表示单词的结尾通过 is_word = true。该节点的 children 数组也未初始化，这是我错误的根源。

while (fscanf(inptr, "%s", wordBuffer) != EOF)
    {
        // Create traversal pointer to the root
        node *trav = root;

        for (int i = 0, n = strlen(wordBuffer); i < n; i++)
        {
            // Find numeric value of letter
            int alphanum;

            if (wordBuffer[i] == 39)
            {
                // If it is apostrophe, allocate last space in children's array
                alphanum = 26;
            }
            else
            {
                alphanum = wordBuffer[i] - 97;
            }


            if (trav->children[alphanum] == NULL)       // line 127
            {

                // If node does not exist in array slot, allocate memory for new node
                trav->children[alphanum] = malloc(1, sizeof(node));        // line 131

            }

            // Redirect trav to child
            trav = trav->children[alphanum];

        }

        trav->is_word = true;

        word_count++;
    }

一个简单的解决方法是 calloc 而不是 malloc ：

if (trav->children[alphanum] == NULL)       // line 127
                {

                    // If node does not exist in array slot, allocate memory for new node
                    trav->children[alphanum] = calloc(1, sizeof(node));        // line 131

                }

当 运行 通过 valgrind 尝试来自 cs50/pset5 speller 的字典时上下文错误

Errors from context when running trie dictionary from cs50/pset5 speller through valgrind

c

malloc

valgrind

cs50

当运行通过 valgrind 尝试来自 cs50/pset5 speller 的字典时上下文错误