Thread: Singly-linked lists and memory loss (valgrind report)

  1. #1
    Registered User
    Join Date
    Mar 2006
    Posts
    158

    Singly-linked lists and memory loss (valgrind report)

    Hi,

    I was having a class the past Friday where we were doing some simple singly-linked lists and using valgrind to minimize the memory loss but I had to leave early and I didn't catch everything. So, the teacher talked about but he said, if we did the delete node function correctly we would lose X of memory, but I believe I'm losing X+Y. I can't tell you the exact numbers cause I can't remember, it's a vague idea that I have...

    And valgrind is also reporting errors, something I believe it should happen. >nyway, my code is as follows:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <errno.h>
    
    typedef struct node {
    	int key;
    	char *val;
    	struct node *next;
    } Dict;
    
    Dict *put(Dict *d, int key, char *val) {
    	Dict *x = (Dict*)malloc(sizeof(Dict));
    	
    	if(!x) {
    		perror("Malloc: ");
    		return NULL;
    	}
    	
    	x->key = key;
    	x->val = val;
    	
    	x->next = d;
    	
    	return x;
    }
    
    Dict *del(Dict *d, int key) {
    	if(!d) return NULL;
    	
    	Dict *ptr = d, *prev = ptr;
    	
    	while(ptr) {
    		if(ptr->key == key) {
    			prev->next = ptr->next;
    			free(ptr);
    		}
    		
    		prev = ptr;
    		ptr = ptr->next;
    	}
    	
    	return d;
    }
    
    int main(void) {
    	Dict *d = NULL;
    	
    	d = put(d, 1, "abc");
    	d = put(d, 2, "def");
    	d = put(d, 3, "tri");
    	d = put(d, 4, "def");
    	d = put(d, 5, "abc");
    	d = put(d, 6, "def");
    	d = put(d, 7, "abc");
    	d = put(d, 8, "def");
    	
    	d = del(d, 5);
    	
    	return 0;
    }
    And the valgrind output is this:

    nazgulled@nazbox ~/University/Sistemas Operativos/Aulas $ valgrind -v ./dictionary
    ==6043== Memcheck, a memory error detector.
    ==6043== Copyright (C) 2002-2007, and GNU GPL'd, by Julian Seward et al.
    ==6043== Using LibVEX rev 1732, a library for dynamic binary translation.
    ==6043== Copyright (C) 2004-2007, and GNU GPL'd, by OpenWorks LLP.
    ==6043== Using valgrind-3.2.3, a dynamic binary instrumentation framework.
    ==6043== Copyright (C) 2000-2007, and GNU GPL'd, by Julian Seward et al.
    ==6043==
    --6043-- Command line
    --6043-- ./dictionary
    --6043-- Startup, with flags:
    --6043-- -v
    --6043-- Contents of /proc/version:
    --6043-- Linux version 2.6.22-gentoo-r5 (root@nazbox) (gcc version 4.1.2 (Gentoo 4.1.2 p1.0.1)) #7 SMP Thu Sep 27 02:47:20 WEST 2007
    --6043-- Arch and hwcaps: X86, x86-sse1-sse2
    --6043-- Page sizes: currently 4096, max supported 4096
    --6043-- Valgrind library directory: /usr/lib/valgrind
    --6043-- Reading syms from /lib/ld-2.6.1.so (0x4000000)
    --6043-- object doesn't have a symbol table
    --6043-- Reading syms from /home/nazgulled/University/Sistemas Operativos/Aulas/dictionary (0x8048000)
    --6043-- Reading syms from /usr/lib/valgrind/x86-linux/memcheck (0x38000000)
    --6043-- object doesn't have a symbol table
    --6043-- object doesn't have a dynamic symbol table
    --6043-- Reading suppressions file: /usr/lib/valgrind/default.supp
    --6043-- Reading syms from /usr/lib/valgrind/x86-linux/vgpreload_core.so (0x401D000)
    --6043-- object doesn't have a symbol table
    --6043-- Reading syms from /usr/lib/valgrind/x86-linux/vgpreload_memcheck.so (0x4020000)
    --6043-- object doesn't have a symbol table
    --6043-- Reading syms from /lib/libc-2.6.1.so (0x4035000)
    --6043-- object doesn't have a symbol table
    --6043-- REDIR: 0x40A1930 (rindex) redirected to 0x4023610 (rindex)
    --6043-- REDIR: 0x409E290 (malloc) redirected to 0x4022930 (malloc)
    --6043-- REDIR: 0x409C670 (free) redirected to 0x40224D0 (free)
    ==6043== Invalid read of size 4
    ==6043== at 0x80484C6: del (in /home/nazgulled/University/Sistemas Operativos/Aulas/dictionary)
    ==6043== by 0x80485F7: main (in /home/nazgulled/University/Sistemas Operativos/Aulas/dictionary)
    ==6043== Address 0x4166130 is 8 bytes inside a block of size 12 free'd
    ==6043== at 0x402253C: free (in /usr/lib/valgrind/x86-linux/vgpreload_memcheck.so)
    ==6043== by 0x80484BC: del (in /home/nazgulled/University/Sistemas Operativos/Aulas/dictionary)
    ==6043== by 0x80485F7: main (in /home/nazgulled/University/Sistemas Operativos/Aulas/dictionary)
    --6043-- REDIR: 0x40A2800 (memset) redirected to 0x4023B10 (memset)
    ==6043==
    ==6043== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 7 from 1)
    ==6043==
    ==6043== 1 errors in context 1 of 1:
    ==6043== Invalid read of size 4
    ==6043== at 0x80484C6: del (in /home/nazgulled/University/Sistemas Operativos/Aulas/dictionary)
    ==6043== by 0x80485F7: main (in /home/nazgulled/University/Sistemas Operativos/Aulas/dictionary)
    ==6043== Address 0x4166130 is 8 bytes inside a block of size 12 free'd
    ==6043== at 0x402253C: free (in /usr/lib/valgrind/x86-linux/vgpreload_memcheck.so)
    ==6043== by 0x80484BC: del (in /home/nazgulled/University/Sistemas Operativos/Aulas/dictionary)
    ==6043== by 0x80485F7: main (in /home/nazgulled/University/Sistemas Operativos/Aulas/dictionary)
    --6043--
    --6043-- supp: 7 dl-hack3
    ==6043==
    ==6043== IN SUMMARY: 1 errors from 1 contexts (suppressed: 7 from 1)
    ==6043==
    ==6043== malloc/free: in use at exit: 84 bytes in 7 blocks.
    ==6043== malloc/free: 8 allocs, 1 frees, 96 bytes allocated.
    ==6043==
    ==6043== searching for pointers to 7 not-freed blocks.
    ==6043== checked 48,796 bytes.
    ==6043==
    ==6043== LEAK SUMMARY:
    ==6043== definitely lost: 84 bytes in 7 blocks.
    ==6043== possibly lost: 0 bytes in 0 blocks.
    ==6043== still reachable: 0 bytes in 0 blocks.
    ==6043== suppressed: 0 bytes in 0 blocks.
    ==6043== Rerun with --leak-check=full to see details of leaked memory.
    --6043-- memcheck: sanity checks: 0 cheap, 1 expensive
    --6043-- memcheck: auxmaps: 0 auxmap entries (0k, 0M) in use
    --6043-- memcheck: auxmaps: 0 searches, 0 comparisons
    --6043-- memcheck: SMs: n_issued = 7 (112k, 0M)
    --6043-- memcheck: SMs: n_deissued = 0 (0k, 0M)
    --6043-- memcheck: SMs: max_noaccess = 65535 (1048560k, 1023M)
    --6043-- memcheck: SMs: max_undefined = 0 (0k, 0M)
    --6043-- memcheck: SMs: max_defined = 19 (304k, 0M)
    --6043-- memcheck: SMs: max_non_DSM = 7 (112k, 0M)
    --6043-- memcheck: max sec V bit nodes: 0 (0k, 0M)
    --6043-- memcheck: set_sec_vbits8 calls: 0 (new: 0, updates: 0)
    --6043-- memcheck: max shadow mem size: 416k, 0M
    --6043-- translate: fast SP updates identified: 1,499 ( 89.7%)
    --6043-- translate: generic_known SP updates identified: 88 ( 5.2%)
    --6043-- translate: generic_unknown SP updates identified: 83 ( 4.9%)
    --6043-- tt/tc: 3,231 tt lookups requiring 3,252 probes
    --6043-- tt/tc: 3,231 fast-cache updates, 2 flushes
    --6043-- transtab: new 1,614 (33,918 -> 559,093; ratio 164:10) [0 scs]
    --6043-- transtab: dumped 0 (0 -> ??)
    --6043-- transtab: discarded 0 (0 -> ??)
    --6043-- scheduler: 22,398 jumps (bb entries).
    --6043-- scheduler: 0/1,665 major/minor sched events.
    --6043-- sanity: 1 cheap, 1 expensive checks.
    --6043-- exectx: 30,011 lists, 17 contexts (avg 0 per list)
    --6043-- exectx: 17 searches, 0 full compares (0 per 1000)
    --6043-- exectx: 0 cmp2, 21 cmp4, 0 cmpAll
    Now, I need your help for the following:

    1) Nothing is reported about the put function. Does this mean that this function is done the way it should and this is as good as it gets? For this simply singly linked lists of course...

    2) What must be done to fix the memory loss problems with the del function? I can't see what I'm doing wrong...

  2. #2
    uint64_t...think positive xuftugulus's Avatar
    Join Date
    Feb 2008
    Location
    Pacem
    Posts
    355
    I don't think you are doing anything wrong. valgrind reports 84 bytes lost, and your del function is only called for a specific entry. d = del(d, 5) you wrote.
    But you haven't called any function to release the entire list before exiting the program, so from the 8 allocations of 12 bytes you performed, the remaining 7 are still allocated. Noticing that 7 * 12 = 84, i see a connection...
    Code:
    ...
        goto johny_walker_red_label;
    johny_walker_blue_label: exit(-149$);
    johny_walker_red_label : exit( -22$);
    A typical example of ...cheap programming practices.

  3. #3
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    I see...

    So, if one wanted to release the entire list when leaving the program what did one had to do?

    Cycle through the list like the del function but instead of freeing just one element, free them all or is there a better/simple way?

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Yes, you'd have to run through the entire list. Something like this:
    Code:
      struct node p, q;
       
      for(p = d; p; p = q)
      {
         q = p->next;
         free(p);
      }
    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    And that is recommended to do everytime when using linked lists and terminating the application, correct?

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Nazgulled View Post
    And that is recommended to do everytime when using linked lists and terminating the application, correct?
    Yes, or rather, whenever you no longer need the linked list - this may happen before you're ready to terminate the application [e.g. a linked list is created as a temporary measure to do some part of the work, and then the linked list is no longer needed, and so should be deleted].

    In theory, you can leave all allocations floating about [assuming the OS cleans up after you], but it's bad style, and if you have MANY and LARGE allocations floating about, it will increase the amount of memory used by the application, which is generally a bad thing.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help! -Linked Lists, Memory Allocation, Time Steps, Debugg
    By MetallicaX in forum C Programming
    Replies: 2
    Last Post: 03-14-2009, 08:50 PM
  2. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  3. Linked Lists and Memory
    By John_L in forum C Programming
    Replies: 1
    Last Post: 10-27-2007, 12:27 PM
  4. Memory allocation in linked lists
    By Panserbjorn in forum C Programming
    Replies: 6
    Last Post: 10-26-2007, 11:02 PM
  5. dynamic memory + linked lists
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 02-10-2002, 04:50 PM