Memory Leaks in C Linked List

2019-06-25 12:56发布

站内文章 / C
37 0 0

问题:

I've been working on a project for school (Due tonight!), and I'm having some serious memory issues. I'm fairly new to C and am still being thrown for a loop when it comes to mallocing pointers and whatnot, so I could really use some help.

The code is as follows. The order of the files is LinkedLists.h (Header for LinkedList module), LinkedLists.c (LinkedList module), and TestList.c (Main module).

/******************************************************************************
* Base struct to contain data structure element information: deterimined by
* the application needs.
******************************************************************************/
#ifndef _LINKED_LISTS_H_
#define _LINKED_LISTS_H_

typedef struct ElementStructs
  {
        int ElementPosition;
        char* ElementValue;
  } ElementStructs;

/**************  Nothing else in the module needs to be modified *************/



/******************************************************************************
* Base struct of list nodes, contains user information and link pointers.
* The "ElementStructs" typemark must be defined based on specific needs of the
* application.
******************************************************************************/
typedef struct LinkedListNodes
  {
   /* The user information field */
   ElementStructs *ElementPtr;
   /* Link pointers */
   struct LinkedListNodes *Next;
   struct LinkedListNodes *Previous;
  } LinkedListNodes;

/******************************************************************************
* Base struct used to manage the linked list data structure.
******************************************************************************/
typedef struct LinkedLists
  {
   /* Number of elements in the list */
   int NumElements;
   /* Pointer to the front of the list of elements, possibly NULL */
   struct LinkedListNodes *FrontPtr;
   /* Pointer to the end of the list of elements, possibly NULL */
   struct LinkedListNodes *BackPtr;
  } LinkedLists;

/******************************************************************************
* Initialized the linked list data structure
******************************************************************************/
void InitLinkedList(LinkedLists *ListPtr);

/******************************************************************************
* Adds a record to the front of the list.
******************************************************************************/
void AddToFrontOfLinkedList(LinkedLists *ListPtr, ElementStructs *DataPtr);

/******************************************************************************
* Adds a record to the back of the list.
******************************************************************************/
void AddToBackOfLinkedList(LinkedLists *ListPtr, ElementStructs *DataPtr);

/******************************************************************************
* Removes (and returns) a record from the front of the list ('works' even on 
* an empty list by returning NULL).
******************************************************************************/
ElementStructs *RemoveFromFrontOfLinkedList(LinkedLists *ListPtr);

/******************************************************************************
* Removes (and returns) a record from the back of the list ('works' even on 
* an empty list by returning NULL).
******************************************************************************/
ElementStructs *RemoveFromBackOfLinkedList(LinkedLists *ListPtr);

/******************************************************************************
* De-allocates the linked list and resets the struct fields as if the
* list was empty.
******************************************************************************/
void DestroyLinkedList(LinkedLists *ListPtr);

#endif /* _LINKED_LISTS_H_ */

LinkedLists.c:

/******************************************************************************
* Extracts and prints the first and last 6 elements from the specified data 
* set and prints the total number of words in the input file. Utilizes the
* LinkedList module as specified in LinkedLists.h
* Written by xxxxxxx
******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include "LinkedLists.h"

void InitLinkedList(LinkedLists *ListPtr)
{
        ListPtr->NumElements = 0;
        ListPtr->FrontPtr = NULL;
        ListPtr->BackPtr = NULL;
}

void AddToFrontOfLinkedList(LinkedLists *ListPtr, ElementStructs
        *DataPtr)
{

        /* If there are no other elements, create new node and add it,
         * assigning it to both the front and back pointers */
        if(ListPtr->NumElements == 0)
        {
                ListPtr->FrontPtr = malloc(sizeof(LinkedListNodes));
                ListPtr->FrontPtr->ElementPtr = DataPtr;
                ListPtr->FrontPtr->Next = NULL;
                ListPtr->FrontPtr->Previous = NULL;
                ListPtr->BackPtr = ListPtr->FrontPtr;
        }

        /* If there are other elements, create new node and add it to the front
         * while retaining previous node order */
        else
        {
                /* Initialize new LinkedListNode */
                ListPtr->FrontPtr->Previous = malloc(sizeof(LinkedListNodes));
                ListPtr->FrontPtr->Previous->ElementPtr = DataPtr;
                ListPtr->FrontPtr->Previous->Next = ListPtr->FrontPtr;
                ListPtr->FrontPtr->Previous->Previous = NULL;

                /* Assign newly initialized node as front node of LinkedList */
                ListPtr->FrontPtr = ListPtr->FrontPtr->Previous;
        }

        /* List size plus one */
        (ListPtr->NumElements)++;
}

void AddToBackOfLinkedList(LinkedLists *ListPtr, ElementStructs
        *DataPtr)
{
        /* If there are no other elements, create new node and add it,
         * assigning it to both the front and back pointers */
        if(ListPtr->NumElements == 0)
        {
                ListPtr->FrontPtr = malloc(sizeof(LinkedListNodes));
                ListPtr->FrontPtr->ElementPtr = DataPtr;
                ListPtr->FrontPtr->Next = NULL;
                ListPtr->FrontPtr->Previous = NULL;
                ListPtr->BackPtr = ListPtr->FrontPtr;
                /*printf("Adding %s\n", DataPtr->ElementValue);*/
        }

        /* If there are other elements, create new node and add it to the back
         * while retaining previous node order */
        else
        {
                /* Initialize new LinkedListNode */
                ListPtr->BackPtr->Next = malloc(sizeof(LinkedListNodes));
                ListPtr->BackPtr->Next->ElementPtr = DataPtr;
                ListPtr->BackPtr->Next->Previous = ListPtr->BackPtr;
                ListPtr->BackPtr->Next->Previous = ListPtr->BackPtr;
                ListPtr->BackPtr->Next->Next = NULL;

                /* Assign newly initialized node as back node of LinkedList */
                ListPtr->BackPtr = ListPtr->BackPtr->Next;
                printf("Adding %s\n", ListPtr->BackPtr->ElementPtr->ElementValue);
        }

        /* List size plus one */
        (ListPtr->NumElements)++;
}

ElementStructs *RemoveFromFrontOfLinkedList(LinkedLists *ListPtr)
{
        if(ListPtr->NumElements > 0)
        {
                ElementStructs *removedElement = ListPtr->FrontPtr->ElementPtr;
                LinkedListNodes *removedNode = ListPtr->FrontPtr;
                 if(ListPtr->NumElements == 1)
            {
                    ListPtr->FrontPtr = NULL;
            }
            else
            {
                    ListPtr->FrontPtr = ListPtr->FrontPtr->Next;
                    ListPtr->FrontPtr->Previous = NULL;
            }
            (ListPtr->NumElements)--;
            free(removedNode);
            return removedElement;
    }
    else
    {
            ElementStructs *nullElement = NULL;
            return nullElement;
    }
}

ElementStructs *RemoveFromBackOfLinkedList(LinkedLists *ListPtr)
{
        if(ListPtr->NumElements > 1)
        {
                ElementStructs *removedElement = ListPtr->BackPtr->ElementPtr;
                LinkedListNodes *removedNode = ListPtr->BackPtr;
                if(ListPtr->NumElements == 1)
                {
                        ListPtr->BackPtr = NULL;
                }
                else
                {
                        ListPtr->BackPtr = ListPtr->BackPtr->Previous;
                        ListPtr->BackPtr->Next = NULL;     
                }
                (ListPtr->NumElements)--;
                free(removedNode);
                return removedElement;
        }
        else
        {
                ElementStructs *nullElement = NULL;
                return nullElement;
        }
}


void DestroyLinkedList(LinkedLists *ListPtr)
{
        while(ListPtr->FrontPtr != NULL)
        {
                LinkedListNodes *removedNode = ListPtr->FrontPtr;
                ListPtr->FrontPtr = ListPtr->FrontPtr->Next;

                /* Deallocate element in node */
                free(removedNode->ElementPtr->ElementValue);
                free(removedNode->ElementPtr);

                /* Deallocate node */
                free(removedNode);
        }
        free(ListPtr);
}

TestList.c:

/******************************************************************************
 * Tests the functionality of the LinkedList specified in LinkedLists.h using
 * the file "american-english-words". Reads in individual words and stores them
 * as node elements in the LinkedList.
 * Written by xxxxx
 *****************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "LinkedLists.h"

#define MAX_LENGTH 100 /* Length of longest word in any major English dictionary */

int main(int argc, char** args)
{
        if(argc == 2)
        {
                /* Initialize LinkedList */
                LinkedLists *LL;

                /* File pointer to input file */
                FILE *fp;

                /* Node to store input data from file */
                ElementStructs *NodeData;

                /* Loop completion boolean */
                int Done;

                /* Loop position counter */
                int Position;

                /* Iterator */
                ElementStructs *CurElement;

                /* Open input file and check that it is readable. If not, exit */
                fp = fopen(args[1], "r");

                if(fp == NULL)
                {
                        fprintf(stderr, "File open failed.");
                        return 2;
                }

                /* Initialize linked list and other necessary variables */
                LL = malloc(sizeof(*LL));
                InitLinkedList(LL);

                Done = 0;
                Position = 0;

                do
                {
                        if(!feof(fp))
                        {
                                /* Allocate space for new node data */
                                NodeData = malloc(sizeof(ElementStructs));

                                /* Allocate space in node element for input string */
                                NodeData->ElementValue = malloc(MAX_LENGTH * sizeof(char));

                                /* Read new node data from file */
                                fscanf(fp, "%s", NodeData->ElementValue);

                                /* Assign scanned values to node elements */
                                NodeData->ElementPosition = Position;
                                /*strcpy(NodeData->ElementValue, readString);*/

                                /* Add data node to LinkedList */
                                AddToFrontOfLinkedList(LL, NodeData);
                        }
                        else
                                Done = 1;
                        Position++;
                }while(Done == 0);

                do
                {
                        CurElement = RemoveFromFrontOfLinkedList(LL);

                        if(CurElement != NULL)
                                printf("Word #%d: %s\n", CurElement->ElementPosition,
                                CurElement->ElementValue);
                }while(CurElement != NULL);

                /* Deallocate linked list */
                DestroyLinkedList(LL);
                fclose(fp);

        }
        /* Bad command line input */
        else
        {
                fprintf(stderr, "Incorrect number of arguments");
                return 1;
        }

        return 0;
}

The program compiles fine. However, running it causes a seg fault at the end of execution, and valgrind reports multiple memory leaks (Shown below). Please, if you have any help to offer, I would be extremely grateful. The issue is mostly in the RemoveFromBackOfLinkedList and RemoveFromFrontOfLinkedList methods in the LinkedList.c module. There's a block of code in the main module (TestList.c) that calls one of these functions (I've tried both, but they have nearly identical functionality, and neither works). The block is a do/while loop shown below:

do
                {
                CurElement = RemoveFromFrontOfLinkedList(LL);

                        if(CurElement != NULL)
                                printf("Word #%d: %s\n", CurElement->ElementPosition,
                                CurElement->ElementValue);
                }while(CurElement != NULL);

Valgrind Results:

Word #225921: stoich
.
.
.
.
Word #6: Cam's
Word #5: petrochemistry's
Word #4: Tera
Word #3: benedictions
Word #2: wisted
Word #1: toxins
==4849== Invalid write of size 8
==4849==    at 0x400B5C: RemoveFromFrontOfLinkedList (in /home/amb2189/hw3/TestList)
==4849==    by 0x40085B: main (in /home/amb2189/hw3/TestList)
==4849==  Address 0x10 is not stack'd, malloc'd or (recently) free'd
==4849== 
==4849== 
==4849== Process terminating with default action of signal 11 (SIGSEGV)
==4849==  Access not within mapped region at address 0x10
==4849==    at 0x400B5C: RemoveFromFrontOfLinkedList (in /home/amb2189/hw3/TestList)
==4849==    by 0x40085B: main (in /home/amb2189/hw3/TestList)
==4849==  If you believe this happened as a result of a stack
==4849==  overflow in your program's main thread (unlikely but
==4849==  possible), you can try to increase the size of the
==4849==  main thread stack using the --main-stacksize= flag.
==4849==  The main thread stack size used in this run was 8388608.
==4849== 
==4849== HEAP SUMMARY:
==4849==     in use at exit: 23,965,172 bytes in 413,185 blocks
==4849==   total heap usage: 619,775 allocs, 206,590 frees, 28,923,332 bytes allocated
==4849== 
==4849== 16 bytes in 1 blocks are possibly lost in loss record 1 of 9
==4849==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4849==    by 0x4007E2: main (in /home/amb2189/hw3/TestList)
==4849== 
==4849== 200 bytes in 2 blocks are possibly lost in loss record 5 of 9
==4849==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4849==    by 0x4007F0: main (in /home/amb2189/hw3/TestList)
==4849== 
==4849== 23,963,992 (3,305,392 direct, 20,658,600 indirect) bytes in 206,587 blocks are definitely lost in loss record 9 of 9
==4849==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4849==    by 0x4007E2: main (in /home/amb2189/hw3/TestList)
==4849== 
==4849== LEAK SUMMARY:
==4849==    definitely lost: 3,305,392 bytes in 206,587 blocks
==4849==    indirectly lost: 20,658,600 bytes in 206,586 blocks
==4849==      possibly lost: 216 bytes in 3 blocks
==4849==    still reachable: 964 bytes in 9 blocks
==4849==         suppressed: 0 bytes in 0 blocks
==4849== Reachable blocks (those to which a pointer was found) are not shown.
==4849== To see them, rerun with: --leak-check=full --show-reachable=yes
==4849== 
==4849== For counts of detected and suppressed errors, rerun with: -v
==4849== Use --track-origins=yes to see where uninitialised values come from
==4849== ERROR SUMMARY: 5 errors from 5 contexts (suppressed: 2 from 2)
Segmentation fault (core dumped)

回答1:

Make some changes in your 2 delete functions,,

ElementStructs *RemoveFromFrontOfLinkedList(LinkedLists *ListPtr)
{
        if(ListPtr->NumElements > 0)
        {
        /*      ElementStructs *removedElement = ListPtr->FrontPtr->ElementPtr;*/
                /*LinkedListNodes *removedNode = malloc(sizeof(removedNode)); // no need allocate because you are deleting the node
                removedNode = ListPtr->FrontPtr;*/ 
                LinkedListNodes *removedNode = ListPtr->FrontPtr; // use this line
                ListPtr->FrontPtr = ListPtr->FrontPtr->Next;
                ListPtr->FrontPtr->Previous = NULL;
                free(removedNode);
                (ListPtr->NumElements)--;
                return NULL;
        }
        else
        {
                ElementStructs *nullElement = NULL;
                return nullElement;
        }
}

ElementStructs *RemoveFromBackOfLinkedList(LinkedLists *ListPtr)
{
        if(ListPtr->NumElements != 0)
        {
                ElementStructs *removedElement = ListPtr->BackPtr->ElementPtr;
                LinkedListNodes *removedNode = ListPtr->BackPtr;
                ListPtr->BackPtr = ListPtr->BackPtr->Previous;
                ListPtr->BackPtr->Next = NULL;
                free(removedNode);
                (ListPtr->NumElements)--; // add this line
                return removedElement;
        }
        else
        {
                ElementStructs *nullElement = NULL;
                return nullElement;
        }
}

EDIT 1

CurElement = malloc(sizeof(*CurElement)); this is another mem-leak in main, you don't have to use malloc for it, just remove this line.

EDIT 2: Why aren't you freeing your ELEMENT and ELEMENTVALUE...?

do
{
        CurElement = RemoveFromFrontOfLinkedList(LL);

        if(CurElement != NULL) {
                printf("Word #%d: %s\n", CurElement->ElementPosition,
                CurElement->ElementValue);
                free(CurElement->ElementValue);  //add these 2 line to free ELEMENTVALUE And ELEMENT.
                free(CurElement);
        }
}while(CurElement != NULL);


回答2:

==4769== 8 bytes in 1 blocks are definitely lost in loss record 1 of 4
==4769==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4769==    by 0x400B46: RemoveFromFrontOfLinkedList (in /home/amb2189/hw3/TestList)
==4769==    by 0x400869: main (in /home/amb2189/hw3/TestList)

This refers to the following code:

LinkedListNodes *removedNode = malloc(sizeof(removedNode));
removedNode = ListPtr->FrontPtr;

You malloc a block of memory then assign it to removedNode then immediately overwrite the pointer value. This does not assign to the contents of removedNode, but it overwrites the pointer.

The next memory leak occurs in main as pointed out by Valgrind:

CurElement = malloc(sizeof(*CurElement));

The next usage of CurElement immediately overwrites the pointer value, which means you have lost your reference to the allocated memory:

CurElement = RemoveFromFrontOfLinkedList(LL);


回答3:

I think one leak is from CurElement = malloc(sizeof(*CurElement));. The next use of CurElement over-writes this pointer.

Its also not immediately clear where NodeData->ElementValue gets freed.



回答4:

what do you want to do with:

LinkedListNodes *removedNode = malloc(sizeof(removedNode));
removedNode = ListPtr->FrontPtr;

you malloc some space and overwride the pointer



标签： c memory-leaks linked-list
举报

收藏的人(0)

Ta的文章 更多文章
登录 后发表评论
0条评论
还没有人评论过~