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:

Quote:

---

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...

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...

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?

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

And that is recommended to do everytime when using linked lists and terminating the application, correct?

Quote:

---

Originally Posted by Nazgulled

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