Valgrind 错误：条件跳转或移动取决于未初始化的值

Question

这是我在这里发表的第一篇文章，因此对任何违反规范的行为表示歉意...... 我正在完成哈佛大学 Cs50 的拼写问题。任务是将字典文件加载到哈希映射中，然后检查文本文件中是否存在拼写错误的单词。 我的程序运行良好并通过了除 valgrind 测试之外的所有测试。 这是我的问题代码，还有另一个哈佛编写的文件，其中包含程序的主文件并调用我编写的所有函数：

// Implements a dictionary's functionality

#include <ctype.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
#include <strings.h>
#include <stdio.h>
#include "dictionary.h"

// Represents a node in a hash table

typedef struct node
{
    char word[LENGTH + 1];
    struct node* next;
}
node;

void deleteList(node* n);
bool checkList(node* n, const char* checkword);


// TODO: Choose number of buckets in hash table
const unsigned int N = 21952;

// Hash table
node* table[N];

// Returns true if word is in dictionary, else false
bool check(const char* word)
{
    int code = hash(word);
    return checkList(table[code], word);
}

int dictSize = 0;
bool dictLoaded = false;

// Hashes word to a number
unsigned int hash(const char* word)
{
    int index = 0;
    //char* wordCopy = malloc((sizeof(char) * strlen(word))); //VALGRIND ERROR Conditional jump or move depends on uninitialised value
    char* wordCopy = calloc(strlen(word), sizeof(char));
    strncpy(wordCopy, word, strlen(word)); //this line


    int sum = 0;
    //iterate thru the word until it ends or we get to our requisite 3 characters
    //must accomodate any capitalization or apostraphes
    while (word[index] != '\0' && index < 3) // this line is still an an error, just like when word was wordcopy
    {
        //change chars to int vals so that null is 0, a is 1, z is 26, and ' is 27
        int ascii = 0; // this remains unchanged if the current char is null
        if (isalpha(wordCopy[index]) != 0)
        {
            wordCopy[index] = tolower(wordCopy[index]);
            ascii = wordCopy[index] - 96;
        }
        else if (wordCopy[index] == '\'')
        {
            ascii = 27;
        }

// add the current chars val to the sum of the word's first three vals
// the math here ensures that "null null null" will be 0, and ''' will be 21,951 or the last index of our hash map
    if (index == 0)
        sum += ascii * 784;

    if (index == 1)
        sum += ascii * 28;

    if (index == 2)
        sum += ascii;

    index++;
    }


    free(wordCopy);

    return sum;
}

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

    FILE* dict = fopen(dictionary, "r");



   int wordLen = 0;
   char* tmpWord = malloc((sizeof(char) * 45) + 1);

   //hard code the first word

   // this first word would screw our loop bc the loop compares the null at the end of a word to a previous null
   //this first word has no previous null to compare to
    int index = 0;

    char c;
    while (fread(&c, sizeof(char), 1, dict))
    {

        if (c != '\n')
        {
            tmpWord[index] = c;
            index++;
        }
        else
        {
            break;
        }
    }


    if (index < 1)
    {
        printf("first word broke load function\n");
        return false;
    }
//find some memory for our word
    node* firstNode = malloc(sizeof(node));

    //copy over the word into the node
    strncpy(firstNode->word, tmpWord, index);

    int code = hash(firstNode->word);

    firstNode->next = table[code];
    table[code] = firstNode;
    dictSize++;


    int lastNull = index - 1;
    int tmpWordIndex = 0;

    //now we can loop thru that ish!
    while (fread(&c, sizeof(char), 1, dict))
    {


        if (c != '\n' && c != '\0')
        {
            tmpWord[tmpWordIndex] = c; //this starts copying into the tmp word at 0
            tmpWordIndex++;
        }
        else // we have reached the end of a string, dictionary[i] == \0
        {
            wordLen = index - lastNull - 1; // -1 for the new line characters

            //create a new node to store this new word
            node* newNode = malloc(sizeof(node));

            // then we actually copy the word over from tmpWord
            strncpy(newNode->word, tmpWord, wordLen);

            code = hash(newNode->word);

            //insert node at the beginning of our list by changing pointer to current first item
            //then change the head node at table[code] to point to our new node
            newNode->next = table[code];
            table[code] = newNode;
            dictSize++;

            //reset the word index so that the next word will copy into the start of tmp word
            //reset the last null encountered to our current char, a null
            tmpWordIndex = 0;
            lastNull = index;

        }


        index++;
    }
        //do it all once more outside loop to grab the last character
            wordLen = index - lastNull - 1; 
            node* newNode = malloc(sizeof(node));
            strncpy(newNode->word, tmpWord, wordLen);
            code = hash(newNode->word);
            newNode->next = table[code];
            table[code] = newNode;


    
    free(tmpWord);
    dictLoaded = true;


    fclose(dict);
    return true;

}

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

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    bool unloaded = false;
    for (int n = 0; n < N; n++)
    {
        node* tmp;
        while(table[n] != NULL)
        {
            tmp = table[n];
            table[n] = table[n]->next;
            free(tmp);
        }
        if(n == N-1)
        {
            unloaded = true;
        }
    }

    return unloaded;
}

void deleteList(node* n) 
{
    // base case is if next pointer is null
    if (n->next == NULL)
    {
        free(n);
        return;
    }

    deleteList(n->next);
}

bool checkList(node* n, const char* checkword)//recursion brah
{
    if (n == NULL)
    {
        return false;
    }
    if (strcasecmp(n->word, checkword) == 0) //error here, see below


// VALGRIND ERROR Conditional jump or move depends on uninitialised value(s): (file: dictionary.c, line: 258)
//Use of uninitialised value of size 8: (file: dictionary.c, line: 258)


    {
        return true;
    }
    else
    {
        return checkList(n->next, checkword); 
    }

}

哈佛的检查测试给了我这些行的错误，特别是： 在 hash(const char* word) 函数中，

char* wordCopy = calloc(strlen(word), sizeof(char));
strncpy(wordCopy, word, strlen(word));
...
while (word[index] != '\0' && index < 3)

我尝试将 malloc 更改为 calloc。我尝试增加和减少我要求 malloc/calloc 的内存大小 1 ie malloc((strlen(word) +/- 1) * sizeof(char))。 原始代码在 while 循环中比较了 wordCopy[index]，但 word[index] 仍然给出相同的错误。 我尝试在 valgrind 上运行 --track-origins=yes arg （见下文），但这并没有给我任何东西，只有哈佛的测试实际上向我显示了错误。

speller/ $ valgrind -s --track-origins=yes ./speller
==7117== Memcheck, a memory error detector
==7117== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==7117== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==7117== Command: ./speller
==7117== 
Usage: ./speller [DICTIONARY] text
==7117== 
==7117== HEAP SUMMARY:
==7117==     in use at exit: 0 bytes in 0 blocks
==7117==   total heap usage: 1 allocs, 1 frees, 1,024 bytes allocated
==7117== 
==7117== All heap blocks were freed -- no leaks are possible
==7117== 
==7117== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

哈佛的测试显示如下：

running valgrind --show-leak-kinds=all --xml=yes --xml-file=/tmp/tmpqjc7357q -- ./speller substring/dict substring/text...
checking for output "MISSPELLED WORDS\n\nca\ncats\ncaterpill\ncaterpillars\n\nWORDS MISSPELLED: 4\nWORDS IN DICTIONARY: 2\nWORDS IN TEXT: 6\n"...
checking that program exited with status 0...
checking for valgrind errors...
Conditional jump or move depends on uninitialised value(s): (file: dictionary.c, line: 45)
Conditional jump or move depends on uninitialised value(s): (file: dictionary.c, line: 46)
Conditional jump or move depends on uninitialised value(s): (file: dictionary.c, line: 57)
Conditional jump or move depends on uninitialised value(s): (file: dictionary.c, line: 267)
Use of uninitialised value of size 8: (file: dictionary.c, line: 267) 

45、46 和 57 是上面提到的哈希函数中的行。第 267 行如下，可在代码底部的 checkList 函数中找到。

if (strcasecmp(n->word, checkword) == 0) 

这是我的第一堂编码课，这个特殊问题完全阻碍了我的进步。如果代码不太好看，我深表歉意。感谢您阅读我的帖子！

编辑：下面是dictionary.h和speller.c，都是我预先编写的......

// Declares a dictionary's functionality

#ifndef DICTIONARY_H
#define DICTIONARY_H

#include <stdbool.h>

// Maximum length for a word
// (e.g., pneumonoultramicroscopicsilicovolcanoconiosis)
#define LENGTH 45

// Prototypes
bool check(const char* word);
unsigned int hash(const char* word);
bool load(const char* dictionary);
unsigned int size(void);
bool unload(void);

#endif // DICTIONARY_H

// Implements a spell-checker

#include <ctype.h>
#include <stdio.h>
#include <sys/resource.h>
#include <sys/time.h>

#include "dictionary.h"

// Undefine any definitions
#undef calculate
#undef getrusage

// Default dictionary
#define DICTIONARY "dictionaries/large"

// Prototype
double calculate(const struct rusage *b, const struct rusage *a);

int main(int argc, char *argv[])
{
    // Check for correct number of args
    if (argc != 2 && argc != 3)
    {
        printf("Usage: ./speller [DICTIONARY] text\n");
        return 1;
    }

    // Structures for timing data
    struct rusage before, after;

    // Benchmarks
    double time_load = 0.0, time_check = 0.0, time_size = 0.0, time_unload = 0.0;

    // Determine dictionary to use
    char *dictionary = (argc == 3) ? argv[1] : DICTIONARY;

    // Load dictionary
    getrusage(RUSAGE_SELF, &before);
    bool loaded = load(dictionary);
    getrusage(RUSAGE_SELF, &after);

    // Exit if dictionary not loaded
    if (!loaded)
    {
        printf("Could not load %s.\n", dictionary);
        return 1;
    }

    // Calculate time to load dictionary
    time_load = calculate(&before, &after);

    // Try to open text
    char *text = (argc == 3) ? argv[2] : argv[1];
    FILE *file = fopen(text, "r");
    if (file == NULL)
    {
        printf("Could not open %s.\n", text);
        unload();
        return 1;
    }

    // Prepare to report misspellings
    printf("\nMISSPELLED WORDS\n\n");

    // Prepare to spell-check
    int index = 0, misspellings = 0, words = 0;
    char word[LENGTH + 1];

    // Spell-check each word in text
    char c;
    while (fread(&c, sizeof(char), 1, file))
    {
        // Allow only alphabetical characters and apostrophes
        if (isalpha(c) || (c == '\'' && index > 0))
        {
            // Append character to word
            word[index] = c;
            index++;

            // Ignore alphabetical strings too long to be words
            if (index > LENGTH)
            {
                // Consume remainder of alphabetical string
                while (fread(&c, sizeof(char), 1, file) && isalpha(c));

                // Prepare for new word
                index = 0;
            }
        }

        // Ignore words with numbers (like MS Word can)
        else if (isdigit(c))
        {
            // Consume remainder of alphanumeric string
            while (fread(&c, sizeof(char), 1, file) && isalnum(c));

            // Prepare for new word
            index = 0;
        }

        // We must have found a whole word
        else if (index > 0)
        {
            // Terminate current word
            word[index] = '\0';

            // Update counter
            words++;

            // Check word's spelling
            getrusage(RUSAGE_SELF, &before);
            bool misspelled = !check(word);
            getrusage(RUSAGE_SELF, &after);

            // Update benchmark
            time_check += calculate(&before, &after);

            // Print word if misspelled
            if (misspelled)
            {
                printf("%s\n", word);
                misspellings++;
            }

            // Prepare for next word
            index = 0;
        }
    }

    // Check whether there was an error
    if (ferror(file))
    {
        fclose(file);
        printf("Error reading %s.\n", text);
        unload();
        return 1;
    }

    // Close text
    fclose(file);


    // Determine dictionary's size
    getrusage(RUSAGE_SELF, &before);
    unsigned int n = size();
    getrusage(RUSAGE_SELF, &after);

    // Calculate time to determine dictionary's size
    time_size = calculate(&before, &after);

    // Unload dictionary
    // causing core dump!!
    getrusage(RUSAGE_SELF, &before);
    bool unloaded = unload();
    getrusage(RUSAGE_SELF, &after);

    // Abort if dictionary not unloaded
    if (!unloaded)
    {
        printf("Could not unload %s.\n", dictionary);
        return 1;
    }

    // Calculate time to unload dictionary
    time_unload = calculate(&before, &after);

    // Report benchmarks
    printf("\nWORDS MISSPELLED:     %d\n", misspellings);
    printf("WORDS IN DICTIONARY:  %d\n", n);
    printf("WORDS IN TEXT:        %d\n", words);
    printf("TIME IN load:         %.2f\n", time_load);
    printf("TIME IN check:        %.2f\n", time_check);
    printf("TIME IN size:         %.2f\n", time_size);
    printf("TIME IN unload:       %.2f\n", time_unload);
    printf("TIME IN TOTAL:        %.2f\n\n",
           time_load + time_check + time_size + time_unload);

    // Success
    return 0;
}

// Returns number of seconds between b and a
double calculate(const struct rusage *b, const struct rusage *a)
{
    if (b == NULL || a == NULL)
    {
        return 0.0;
    }
    else
    {
        return ((((a->ru_utime.tv_sec * 1000000 + a->ru_utime.tv_usec) -
                  (b->ru_utime.tv_sec * 1000000 + b->ru_utime.tv_usec)) +
                 ((a->ru_stime.tv_sec * 1000000 + a->ru_stime.tv_usec) -
                  (b->ru_stime.tv_sec * 1000000 + b->ru_stime.tv_usec)))
                / 1000000.0);
    }
}

编辑： pm100 的答案帮助缓解了除了我的哈希函数中的 while 循环检查之外的所有问题。我认为我传递给哈希的所有单词都应该在适当的索引中以空结尾。我将保留我的旧代码作为参考。 以下是我当前相关功能的代码。我在加载函数中添加了空值，因为该函数将混乱的字符串传递给给出错误的哈希函数。 为了消除哈希中的 malloc 错误，我想我可以只复制当前索引处的字符，而不是引用传递到函数中的整个单词的副本。这很有帮助。但由于某种原因，在 while 循环条件中将 d 字符与 null 进行比较是不好的。

// Hashes word to a number
unsigned int hash(const char* word)
{
    int index = 0;

    int sum = 0;
    //iterate thru the word until it ends or we get to our requisite 3 characters
    //must accomodate any capitalization or apostraphes
    char d = word[0];
    while (d != '\0' && index < 3) // this line is still an an error, just like when it word was wordcopy
    {

        //change chars to int vals so that null is 0, a is 1, z is 26, and ' is 27
        int ascii = 0; // this remains unchanged if the current char is null
        if (isalpha(d) != 0)
        {
            d = tolower(d);
            ascii = d - 96;
        }
        else if (d == '\'')
        {
            ascii = 27;
        }

// add the current chars val to the sum of the word's first three vals
// the math here ensures that "null null null" will be 0, and ''' will be 21,951 or the last index of our hash map
    if (index == 0)
        sum += ascii * 784;

    if (index == 1)
        sum += ascii * 28;

    if (index == 2)
        sum += ascii;

    index++;
    d = word[index];

    }



    return sum;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char* dictionary)
{
    FILE* dict = fopen(dictionary, "r");



   int wordLen = 0;
   char* tmpWord = malloc((sizeof(char) * 45) + 1);

   //hard code the first word

   // this first word would screw our loop bc the loop compares the null at the end of a word to a previous null
   //this first word has no previous null to compare to
    int index = 0;

    char c;
    while (fread(&c, sizeof(char), 1, dict))
    {
        //printf("%c\n", c);
        if (c != '\n')
        {
            tmpWord[index] = c;
            index++;
        }
        else
        {
            break;
        }
    }
    tmpWord[index] = '\0';

    if (index < 1)
    {
        printf("first word broke load function\n");
        return false;
    }
//find some memory for our word
    node* firstNode = malloc(sizeof(node));

    //copy over the word into the node
    strncpy(firstNode->word, tmpWord, index + 1);

    int code = hash(tmpWord);


    firstNode->next = table[code];
    table[code] = firstNode;
    dictSize++;


    int lastNull = index - 1;
    int tmpWordIndex = 0;

    //now we can loop thru that!
    while (fread(&c, sizeof(char), 1, dict))
    {

        if (c != '\n' && c != '\0')
        {
            tmpWord[tmpWordIndex] = c; //this starts copying into the tmp word at 0
            tmpWordIndex++;
        }
        else // we have reached the end of a string, dictionary[i] == \n
        {
            wordLen = index - lastNull - 1; // -2 for the null and new line characters

            //create a new node to store this new word
            node* newNode = malloc(sizeof(node));
            tmpWord[tmpWordIndex] = '\0';
            // then we actually copy the word over from tmpWord
            strncpy(newNode->word, tmpWord, wordLen + 1);
            //insert node at the beginning of our list by changing pointer to current first item
            //then change the head node at table[code] to point to our new node
            newNode->next = table[code];
            table[code] = newNode;
            dictSize++;

            //reset the word index so that the next word will copy into the start of tmp word
            //reset the last null encountered to our current char, a null
            tmpWordIndex = 0;
            lastNull = index;

        }


        index++;
    }

            wordLen = index - lastNull - 1;
            node* newNode = malloc(sizeof(node));
            tmpWord[tmpWordIndex] = '\0';
            strncpy(newNode->word, tmpWord, wordLen);
            code = hash(newNode->word);
            newNode->next = table[code];
            table[code] = newNode;



    free(tmpWord);
    dictLoaded = true;

    fclose(dict);
    return true;

}

哈希函数内的这一行 while (d != '\0' && index < 3) 仍然返回条件跳转 valgrind 错误。

Answer 1

好吧，你的主要问题是空终止符，我不明白你的很多逻辑，我只是​​用一个简单的 4 字文件调用加载。

您必须确保为空值留出足够的空间，并且必须确保有空值。

所以

我找到的那些，你必须修复其他的

char c;
while (fread(&c, sizeof(char), 1, dict))
{

    if (c != '\n')
    {
        tmpWord[index] = c;
        index++;
    }
    else
    {
        break;
    }
}
tmpWord[index] = 0; <<<<===== add the null at the end

，

   //copy over the word into the node
   // +1 for the null
    strncpy(firstNode->word, tmpWord, index + 1);

现在在散列

char* wordCopy = calloc(strlen(word)+1, sizeof(char));
strncpy(wordCopy, word, strlen(word)+1); 

+1，+1

中还有其他我确信的。

valgrind 抱怨的原因是因为没有像 strlen 这样的尾随 null 函数，它会一直读入内存，直到找到随机 null，valgrind 会看到您从复制的内容末尾读取 waaaay 中的字符。

为了确保您有 null，请放置一个printf 或只是在调试器中暂停并查看字符串。如果你看到

 "cat"

事情是好的，但如果你看到了

 "cat!!@*foodle!....ll"

，你就知道你错过了空