In this blog we are going to discuss “How to find memory leak using valgrind memory debugging tool”. In previous blog http://wikistack.com/how-to-write-c-program-for-trie-data-structure/  we have implemented trie data structure with insert and search operation. This implementation has some memory leak. Let us find memory leak using valgrind tool. Let us see below code.

#include<stdio.h>
#include<malloc.h>
#include<string.h>

#define true 1
#define false 0

struct trie {
	struct trie *children[26];
	int isEndOfString;
};

struct trie *makeNode() {
	struct trie *p = (struct trie*) malloc(sizeof(struct trie));
	if (p) {
		p->isEndOfString = false;
		int i = 0;
		for (i; i < 26; i++) {
			p->children[i] = NULL;
		}
	}
	return p;
}

int getIndex(char ch) {
	return ch - 'a';
}

void insert(struct trie * root, char *str, int str_len) {
	struct trie *tmp = root;
	int i = 0;
	for (i; i < str_len; i++) {
		int index_of_char = getIndex(str[i]);
		if (tmp->children[index_of_char] == NULL) {
			tmp->children[index_of_char] = makeNode();
		}
		tmp = tmp->children[index_of_char];
	}
	// after traversing all char of str,mark
	// last trie node's flag isEndOfString true
	tmp->isEndOfString = true;
}
int search(struct trie *root, char* str, int len) {

	int i = 0;
	struct trie *tmp = root;

	for (i; i < len; i++) {
		int index = getIndex(str[i]);

		if (!tmp->children[index])
			return false;

		tmp = tmp->children[index];
	}

	return (tmp != NULL && tmp->isEndOfString);
}
int main() {
	// make root Node
	struct trie *root = makeNode();
	char *str = "als";
	int len = strlen(str);
	insert(root, str, len);

	if (search(root, str, len))
		printf("string is present in trie\n");
	else
		printf("string is not present in trie\n");

	char *strr = "wiki";
	if (search(root, strr, len))
		printf("string is present in trie\n");
	else
		printf("string is not present in trie\n");

	return 0;
}

How to find memory leak using valgrind memory debugging tool

  • compile above code using gcc -g  trie.c -o trie
  • And run using valgrind –tool=memcheck –leak-check=full ./trie , we will see output as
==3863== Memcheck, a memory error detector
==3863== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==3863== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info
==3863== Command: ./trie
==3863== 
string is present in trie
string is not present in trie
==3863== 
==3863== HEAP SUMMARY:
==3863==     in use at exit: 864 bytes in 4 blocks
==3863==   total heap usage: 4 allocs, 0 frees, 864 bytes allocated
==3863== 
==3863== 864 (216 direct, 648 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2
==3863==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3863==    by 0x4005CE: makeNode (trie.c:14)
==3863==    by 0x40076C: main (trie.c:61)
==3863== 
==3863== LEAK SUMMARY:
==3863==    definitely lost: 216 bytes in 1 blocks
==3863==    indirectly lost: 648 bytes in 3 blocks
==3863==      possibly lost: 0 bytes in 0 blocks
==3863==    still reachable: 0 bytes in 0 blocks
==3863==         suppressed: 0 bytes in 0 blocks
==3863== 
==3863== For counts of detected and suppressed errors, rerun with: -v
==3863== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

observation on valgrind output

  • From the above valgrind messages we can see that our program has memory leak.

==3863== LEAK SUMMARY:
==3863==    definitely lost: 216 bytes in 1 blocks
==3863==    indirectly lost: 648 bytes in 3 blocks

  • The stack trace tells where the leaked memory was allocated.Memcheck tool cannot tell why does memory leaks.

==3863==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3863==    by 0x4005CE: makeNode (trie.c:14)
==3863==    by 0x40076C: main (trie.c:61)

  • Whenever a programmer allocate memory using malloc, it is programmer to delete memory using library function free().
  • So to delete memory allocated in our trie implementation we need to traverse entire trie and delete allocated memory.
void delete(struct trie *root)
{
    struct trie *tmp=root;
    int i;
    if (tmp != NULL && tmp->isEndOfString == false){
      for (i=0;i<26;i++){
         if (tmp->children[i] != NULL){
            delete(tmp->children[i]);
            tmp->children[i] = NULL; 
         }
      }
    }

    if (tmp != NULL){ 
      free(tmp);
   }
}

Ref:

https://stackoverflow.com/questions/40324818/freeing-a-trie-tree



Related Contents to follow