c - 内存泄漏和无效读/写

Question

在我因为没有看这里过多的 Valgrind 问题而崩溃之前:我看了。我花了很多时间寻找，但我发现的都是没有 malloc() 正确字节数的人。如果我不正确并且这是重复的，我很乐意接受您的引用。

在这个程序中，我使用树来创建拼写检查器。我的代码中有很多问题需要修复，但内存泄漏是我真正需要帮助解决的唯一问题。 (很多代码都是临时的，所以它会编译，以便我可以修复内存泄漏。)

问题是我相当确定我正在为我的节点分配正确的空间量，我认为 Valgrind 证实了这一点，因为我只有 2 个未释放的 block (在 365,371 个分配中)。

无论如何，我会发布完整的代码(以防有人需要完整的上下文)，但我认为相关部分是加载函数和清除函数，我分别在其中分配和释放内存。

/**
* Implements a dictionary's functionality.
*/
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "dictionary.h"

// number of characters we are using (a-z and ')
#define LETTERS 27

// max guaranteed number of nonnegative char values that exist
#define CHARVALUES 128

// create node structure for trie
typedef struct node
{
    struct node *children[LETTERS];
    bool is_word;
}
node;

// create root node for trie
node *root;

// stores the size of our dictionary
unsigned int dict_size = 0;

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char *word)
{
    // keeps track of where we are; starts with root for each new word
    node *current_node = root;

    while (*word != '\0')
    {

        // indices: 'a' -> 0, ..., 'z' -> 25, '\' -> 26
        int index = (tolower(*word) - 'a') % CHARVALUES;
        if (index >= LETTERS - 1)
        {
            // by assumption, the char must be '\'' if not '\n' or a letter
            index = LETTERS - 1;
        }

        // if the node we need to go to is NULL, the word is not here
        if (current_node->children[index] == NULL)
        {
            return false;
        }

        // go to the next logical node, and look at the next letter of the word
        current_node = current_node->children[index];
        word++;
        }
    }
    return current_node->is_word;
}

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

    FILE *inptr = fopen(dictionary, "r");
    if (inptr == NULL)
    {
        return false;
    }

    // allocate memory for the root node
    root = malloc(sizeof(node));

    // store first letter (by assumption, it must be a lowercase letter)
    char letter = fgetc(inptr);

    // stores indices corresponding to letters
    int index = 0;

    /**
     * we can assume that there is at least one word; we will execute the loop
     * and assign letter a new value at the end. at the end of each loop, due
     * to the inside loop, letter will be a newline; we know the EOF in the
     * dictionary follows a newline, so the loop will terminate appropriately
     */
    do
    {
        // keeps track of where we are; starts with root for each new word
        node *current_node = root; 

        // this loop will only execute if our character is a letter or '\''
        while (letter != '\n')
        {
            // indices: 'a' -> 0, ..., 'z' -> 25, '\' -> 26
            index = (letter - 'a') % CHARVALUES;
            if (index >= LETTERS - 1)
            {
                // by assumption, the char must be '\'' if not '\n' or a letter
                index = LETTERS - 1;
            }

            // allocate memory for a node if we have not done so already
            if (current_node->children[index] == NULL)
            {
                current_node->children[index] = malloc(sizeof(node));

                // if we cannot allocate the memory, unload and return false
                if (current_node->children[index] == NULL)
                {
                    unload();
                    return false;
                }

            }

            // go to the appropriate node for the next letter in our word
            current_node = current_node->children[index];

            // get the next letter
            letter = fgetc(inptr);
        }

        // after each linefeed, our current node represents a dictionary word
        current_node->is_word = true;
        dict_size++;

        // get the next letter
        letter = fgetc(inptr);
    }
    while (letter != EOF);

    fclose(inptr);

    // if we haven't returned false yet, then loading the trie must have worked
    return true;
}

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

void clear(node *head)
{
    for (int i = 0; i < LETTERS; i++)
    {
        if (head->children[i] != NULL)
        {
            clear(head->children[i]);
        }
    }
    free(head);
}

/**
 * Unloads dictionary from memory. Returns true if successful else false.
 */
bool unload(void)
{
    clear(root);
    return true;
}

相关的 valgrind 输出如下:

==18981== HEAP SUMMARY:
==18981==     in use at exit: 448 bytes in 2 blocks
==18981==   total heap usage: 365,371 allocs, 365,369 frees, 81,843,792 bytes allocated
==18981== 
==18981== 448 (224 direct, 224 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2
==18981==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==18981==    by 0x4011B0: load (dictionary.c:111)
==18981==    by 0x4008CD: main (speller.c:40)
==18981== 
==18981== LEAK SUMMARY:
==18981==    definitely lost: 224 bytes in 1 blocks
==18981==    indirectly lost: 224 bytes in 1 blocks
==18981==      possibly lost: 0 bytes in 0 blocks
==18981==    still reachable: 0 bytes in 0 blocks
==18981==         suppressed: 0 bytes in 0 blocks

因此，我对此输出的解释是，在以下代码块中:

            if (current_node->children[index] == NULL)
            {
                current_node->children[index] = malloc(sizeof(node));

                // if we cannot allocate the memory, unload and return false
                if (current_node->children[index] == NULL)
                {
                    unload();
                    return false;
                }

            }

malloc 语句(确实是 dictionary.c:111 行)被执行两次，因此分配的内存永远不会被释放。 (这是正确的吗？)现在，这让我认为真正的问题在于我的 clear 函数，即它写得不好并且没有清除我的 trie 的每个节点。

但是，我盯着代码看了好几个小时，我几乎看不出它有什么问题。 (我敢肯定很多是；我只是不太擅长这个。)

如有任何帮助，我们将不胜感激。

Answer 1

对于初学者:

代码未将成员数组 children 初始化为每个节点 malloc() 的所有 NULL。 malloc() 不对分配的内存执行任何初始化。它只是包含“垃圾”。

所以这里

       if (current_node->children[index] == NULL)
       {

成为一个“随机”决定，如果它本身没有引发未定义的行为的话。

(顺便说一句，您的问题标题中提到的“无效读/写”，但您没有向我们展示，很可能也恰好提到了上面的这一行代码...)

要解决此问题，您可以使用如下内容:

#include <stdlib.h> (/* for malloc() */
#include <errno.h> (/* for errno */


/* Allocate and initialises a new node. */
/* Returns 0 on success and -1 on failure. */

int node_create(node ** pn)
{
  int result = 0; /* Be optimistic. */

  if (NULL == pn)
  {
    errno = EINVAL;
    result = -1;
  }
  else
  {
    node * n = malloc(sizeof *n);
    if (NULL == n)
    {
      result = -1;
    }
    else
    {
      for (size_t i = 0; i < LETTERS; ++i)
      {
        n -> children[i] = NULL;
      }

      n -> is_word = 0;
      (*pn) = n;
    }
  }

  return result;
}

然后像这样使用它:

  ...

  if (-1 == node_create(&root))
  {
    perror("node_create() failed");
    return false;
  }