c - "free(): invalid pointer" error while freeing allocated memory of a hash table

Question

Edit:

I already ran my program through valgrind which pointed to the two functions I've included here:

==6768== Invalid free() / delete / delete[] / realloc()
==6768==    at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==6768==    by 0x42187C: free_memory (test4.c:232)
==6768==    by 0x42087E: main (test4.c:93)
==6768==  Address 0x10855f8 is 0 bytes inside data symbol "hash_table"
==6768== 
==6768== Invalid free() / delete / delete[] / realloc()
==6768==    at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==6768==    by 0x421856: free_memory (test4.c:224)
==6768==    by 0x42087E: main (test4.c:93)
==6768==  Address 0x1085708 is 272 bytes inside data symbol "hash_table"
==6768== 
==6768== 
==6768== HEAP SUMMARY:
==6768==     in use at exit: 36,504 bytes in 676 blocks
==6768==   total heap usage: 679 allocs, 679 frees, 36,666 bytes allocated
==6768== 
==6768== 36,504 bytes in 676 blocks are definitely lost in loss record 1 of 1
==6768==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==6768==    by 0x4208C9: init_table (test4.c:105)
==6768==    by 0x42073D: main (test4.c:44)
==6768== 
==6768== LEAK SUMMARY:
==6768==    definitely lost: 36,504 bytes in 676 blocks
==6768==    indirectly lost: 0 bytes in 0 blocks
==6768==      possibly lost: 0 bytes in 0 blocks
==6768==    still reachable: 0 bytes in 0 blocks
==6768==         suppressed: 0 bytes in 0 blocks
==6768== 
==6768== For counts of detected and suppressed errors, rerun with: -v
==6768== ERROR SUMMARY: 677 errors from 3 contexts (suppressed: 0 from 0)

---

Good day everyone. I have an interesting problem if you have some time. I keep running into an error with free() function from stdlib.h for days. My code is somewhat large, so I tested it to get the same error in a minified version. I know where the problem occurs but I can't formulate a solution for it. All help is much appreciated. Full error text:

*** Error in `./sample': free(): invalid pointer: 0x0000000001084078 ***
Aborted

The code includes a data structure to index words with their first and second letters' alphabetical indexes as key values, and stores the word itself in a linked list pointed by a node-head living in the corresponding indexed location. It's a very simple idea. As a great man once said; talk is cheap, show me code. Start reading the data structure definitions from (1) to (3), it will make more sense:

#include <stdlib.h>


// (3) Node (of a linked list), represents a single word indexed first letter of-
// column[i] and second letter of row[i]. Think of the z axis of a table

typedef struct _node
{
    char *value;
    struct _node *next;
}
node;


// (2) Row, represents the second letter of a word. Think of the y axis of a table

typedef struct _row
{
    node rows[26];
}
row;


// (1) Column, represents the first letter of a word. Think of the x axis of a table

typedef struct _column
{
    row columns[26];
}
column;


// These are detailed below

void init_table(column *table);
void free_memory(column *table);

column hash_table;


int main(void)
{

    init_table(&hash_table);
    free_memory(&hash_table);

    return 0;
}


// Initialize node-heads. If I don't do this, I get a 'runtime error: null-
// pointer passed as argument' when I want to access and store something in 
// "node->next" or "node->value" for the first time

void init_table(column *table)
{
    for (int i = 0; i < 26; i++)  // For each column
    {
        for (int j = 0; j < 26; j++)  // For each row
        {
            // Allocate space for a new node, as the head of a linked list.
            // Max word length will be 45 letters, allocate that much space
            node *first_node = malloc(sizeof(char) * 46 + sizeof(node *));

            // Assign new node with value of "none", and "next" (pointer) of NULL
            *first_node = (node) { .value = "none", .next = NULL };

            // Store this node in the current table cell
            table->columns[i].rows[j] = *first_node;
        }
    }
}


// Free all the memory on the heap, allocated previously
void free_memory(column *table)
{
    node *ptr;  // To guide the "del_node"
    node *del_node;  // To delete guided memory locations
    for (int i = 0; i < 26; i++)  // columns
    {
        for (int j = 0; j < 26; j++)  // rows
        {
            // Address of the first node of the current linked list
            ptr = &table->columns[i].rows[j];

            while(1)
            {
                if(ptr->next)  // If node does not point to "NULL"
                {
                    del_node = ptr;  // Guide the "del_node"
                    ptr = ptr->next;  // Advance "ptr" to the next node
                    free(del_node);  // Free the memory pointed by "del_node"
                }
                else {
                    break;
                }
            }

            // Free "ptr" in case there was no next node but "ptr" 
            // was pointing to a node

            if (ptr) free(ptr);
        }
    }
}

标签： c

Answer 1

该代码中有很多问题。

您的错误可能来自这篇文章：

    for (int j = 0; j < 26; j++)  // rows
    {
        // Address of the first node of the current linked list
        ptr = &table->columns[i].rows[j];

请记住：该表是一个非动态分配的全局变量。 ptr指向此静态变量的数组元素。

        while(1)
        {
            if(ptr->next)  // If node does not point to "NULL"
            {
                del_node = ptr;  // Guide the "del_node"
                ptr = ptr->next;  // Advance "ptr" to the next node
                free(del_node);  // Free the memory pointed by "del_node"
            }

在这里，您尝试释放数组中的节点。不是动态分配的内存位置。那不会飞

查看您初始化表的方式，我们发现了更多问题：

    for (int j = 0; j < 26; j++)  // For each row
    {
        // Allocate space for a new node, as the head of a linked list.
        // Max word length will be 45 letters, allocate that much space
        node *first_node = malloc(sizeof(char) * 46 + sizeof(node *));

您有 46 字节的内存无法使用该node类型访问。

        // Assign new node with value of "none", and "next" (pointer) of NULL
        *first_node = (node) { .value = "none", .next = NULL };

虽然value是指向 char 的指针，但这可能有效。但是，如果您打算为其他节点使用动态分配的内存，则需要在之后释放它。这不适用于字符串文字。

        // Store this node in the current table cell
        table->columns[i].rows[j] = *first_node;

你复制了分配内存的内容（当然没有额外的 46 个字节），然后你就忘记了分配的内存。你不能再释放它了。

如果这些节点都是列表的头部，则根本不应该为它们分配内存，因为它们是静态的。