On Monday 19 June 2006 7:55 am, Verdi March wrote:

Hi,

Valgrind detected memleak on one of my test case, which is a standard, textbook insertion sort. However, I don't see any problem with the testcase. I'm wondering if this is a false alarm, and should submit a bug report.

I'm using SuSE 10.1, and valgrind-3.2.0-11.1 from opensuse build service.

The followings are the test case and the output of valgrind. I've marked the offending line (line 36) in the testcase.

/************************** Test Case ************************/ #include #include

typedef struct _int_struct { int i; struct _int_struct *next; } IntStruct;

typedef struct _int_list { IntStruct *head; } IntList;

int insert(IntList *ilist, int i); int insertion_sort(IntList *ilist, IntStruct *is);

int main() { IntStruct *is; IntList ilist;

ilist.head = NULL;

insert(&ilist, 500); insert(&ilist, 100);

printf("ilist: "); for (is = ilist.head; is; is = is->next) printf("%d ", is->i); printf("\n");

return 0; }

int insert(IntList *ilist, int i) { IntStruct *is = (IntStruct *) calloc(1, sizeof(IntStruct)); /* line 36 */ is->i = i; return insertion_sort(ilist, is); }

int insertion_sort(IntList *ilist, IntStruct *is) { IntStruct **isp; for (isp = &ilist->head; *isp; isp = &((*isp)->next)) { if (is->i < (*isp)->i) { is->next = *isp; break; } else if (is->i == (*isp)->i) { /* return FALSE; */ return 0; } }

*isp = is;

/* return TRUE; */ return 1; } You very definitely have a memory leak. You create your list using calloc(3), but you fail to free that list.

-- Jerry Feldman Boston Linux and Unix user group http://www.blu.org PGP key id:C5061EA9 PGP Key fingerprint:053C 73EC 3AC1 5C44 3E14 9245 FB00 3ED5 C506 1EA9

On Monday 19 June 2006 9:40 am, Verdi March wrote:

Hi,

Jerry Feldman wrote:

...

You very definitely have a memory leak. You create your list using calloc(3), but you fail to free that list.

Shouldn't that be regarded as "reachable" instead of "definite lost"? I can still refer to the allocated instances, otherwise I'd not be able to print-out the list's content.

$ ./a.out ilist: 100 500 No. That is because the pointer is available in main. If you allocate memory inside of a function, and return from that function without freeing that memory or without providing a pointer to that memory, that is unreachable. -- Jerry Feldman Boston Linux and Unix user group http://www.blu.org PGP key id:C5061EA9 PGP Key fingerprint:053C 73EC 3AC1 5C44 3E14 9245 FB00 3ED5 C506 1EA9

On Monday 19 June 2006 22:56, Verdi March wrote:

On Monday 19 June 2006 22:09, Jerry Feldman wrote:

...

No. That is because the pointer is available in main. If you allocate memory inside of a function, and return from that function without freeing that memory or without providing a pointer to that memory, that is unreachable.

I tried the above with a simpler testcase:

int main() { int *iptr iptr (int *) malloc(sizeof(int));

This should be: iptr = (int *) malloc(sizeof(int));

return 0; }

and valgrind still detect a memory leak. Obviously I hold a pointer (iptr) to the allocated memory, or do I misunderstand your explanation?

Hi, On Monday 19 June 2006 23:34, Jerry Feldman wrote:

...

I tried the above with a simpler testcase:

int main() { int *iptr iptr (int *) malloc(sizeof(int)); return 0; }

and valgrind still detect a memory leak. Obviously I hold a pointer (iptr) to the allocated memory, or do I misunderstand your explanation?

This is a memory leak because you return from main() without freeing memory. The following code is NOT a memory leak: int main() { int *iptr iptr (int *) malloc(sizeof(int)); free(iptr); return 0; }

I see. I was expecting that my testcase would be considered as "not freed but still reachable", whereas "definite lost" would be something like: int main() { int *iptr = malloc(...); iptr = NULL; return 0; } Often I dynamically allocate memory that I know it is going to be used until a program terminates. Though I'll keep pointers to these memory (thus, reachable from main()), I don't bother to explicitly free() these pointers when the program is about to terminate. Afterall, after the program terminates, its address space will be reclaimed by the system. -- Regards, Verdi

On Monday 19 June 2006 19:20, Anders Johansson wrote:

On Monday 19 June 2006 13:55, Verdi March wrote:

...

int insertion_sort(IntList *ilist, IntStruct *is) { IntStruct **isp; for (isp = &ilist->head; *isp; isp = &((*isp)->next)) { if (is->i < (*isp)->i) { is->next = *isp; break; } else if (is->i == (*isp)->i) { /* return FALSE; */ return 0; } }

*isp = is;

/* return TRUE; */ return 1; }

What on earth is going on here.

insert 500 insert 100 insert 600

What is the result?

600 < 100? No, next 600 < 500? No, next end of list

*isp = is, goodbye list

My mistake. Actually, it's "*isp = is -> segmentation fault because *isp == NULL"

That's no way to do an insertion sort.

This is still true

On Monday 19 June 2006 13:55, Verdi March wrote:

int insertion_sort(IntList *ilist, IntStruct *is) { IntStruct **isp; for (isp = &ilist->head; *isp; isp = &((*isp)->next)) { if (is->i < (*isp)->i) { is->next = *isp; break; } else if (is->i == (*isp)->i) { /* return FALSE; */ return 0; } }

*isp = is;

OK, I was wrong, it works. The layers of double indirection threw me. I think it's a very poor way of programming, I don't like it at all Here's how I would do it, which I think is much easier to read #include #include typedef struct _int_struct { int i; struct _int_struct *next; } IntStruct; typedef struct _int_list { IntStruct *head; } IntList; void insert(IntList *ilist, int i); void insertion_sort(IntList *ilist, IntStruct *is); int main() { IntStruct *is; IntList ilist; ilist.head = NULL; insert(&ilist, 500); insert(&ilist, 100); insert(&ilist, 600); printf("ilist: "); for (is = ilist.head; is != NULL; is = is->next) printf("%d ", is->i); printf("\n"); return 0; } void insert(IntList *ilist, int i) { IntStruct *is = (IntStruct *) calloc(1, sizeof(IntStruct)); /* line 36 */ is->i = i; is->next = NULL; insertion_sort(ilist, is); return; } void insertion_sort(IntList *ilist, IntStruct *is) { IntStruct *isp; if(ilist->head == NULL){ ilist->head = is; return; } if(is->i <= ilist->head->i){ is->next = ilist->head; ilist->head = is; return; } for (isp = ilist->head; isp->next != NULL; isp = isp->next) if (is->i <= isp->next->i) { is->next = isp->next; isp->next = is; return; } isp->next = is; }

On Monday 19 June 2006 21:21, Jerry Feldman wrote:

On Monday 19 June 2006 2:16 pm, Anders Johansson wrote:

...

OK, I was wrong, it works. The layers of double indirection threw me. I think it's a very poor way of programming, I don't like it at all

Here's how I would do it, which I think is much easier to read

IntStruct *is = (IntStruct *) calloc(1, sizeof(IntStruct)); /* line 36 */ is->i = i; is->next = NULL;

This is a segfault waiting to happen. What happens if calloc(3) returns NULL? Always test the return values of malloc(3) and derivatives for NULL, otherwise there will be a point where the program will blow up.

Very true. I wasn't really looking at that, I was more concerned with the unseemly use of pointer indirection elsewhere. If I was to really rewrite it I would do a lot more

On Tuesday 20 June 2006 03:38, Jerry Feldman wrote:

On Monday 19 June 2006 12:01 pm, Verdi March wrote:

...

Often I dynamically allocate memory that I know it is going to be used until a program terminates. Though I'll keep pointers to these memory (thus, reachable from main()), I don't bother to explicitly free() these pointers when the program is about to terminate. Afterall, after the program terminates, its address space will be reclaimed by the system.

This is a poor programming practice. One should always release allocated memory after it is no longer needed.

The C language standard does not guarantee that allocated memory will be reclaimed by the system. However, nearly all Unix and Linux systems do this for you. But, I once worked on an IBM mainframe system where this was not the case, and we had a memory leak that prevented the application from being reloaded without a logout. -- Jerry Feldman

I would just like to agree with Jerry: I worked with a company where C++ programmers didn't keep tight tabs on memory and the system just chewed up memory until it crashed. Customers were forced to regularly re-boot Windows to clear memory. As Jerry said: poor programming. Colin

I agree, The example does not test the return value of calloc, as I didn't expect this small example to fail. No prob here. many times when we write small reproducers we forget some of

On Monday 19 June 2006 9:14 pm, Verdi March wrote: the details, but it is important to get into the practice of doing things the 'correct' way, even for examples like this. I guess I am kind of a stickler as I once worked for a company that had a methodology of provably correct code. -- Jerry Feldman Boston Linux and Unix user group http://www.blu.org PGP key id:C5061EA9 PGP Key fingerprint:053C 73EC 3AC1 5C44 3E14 9245 FB00 3ED5 C506 1EA9

On Sun, 09 Jul 2006 16:17:59 +0100 peter burden wrote:

Jerry Feldman wrote:

...

On Monday 19 June 2006 10:56 am, Verdi March wrote:

...

Hi,

On Monday 19 June 2006 22:09, Jerry Feldman wrote:

...

No. That is because the pointer is available in main. If you allocate memory inside of a function, and return from that function without freeing that memory or without providing a pointer to that memory, that is unreachable.

I tried the above with a simpler testcase:

int main() { int *iptr iptr (int *) malloc(sizeof(int)); return 0; }

and valgrind still detect a memory leak. Obviously I hold a pointer (iptr) to the allocated memory, or do I misunderstand your explanation?

This is a memory leak because you return from main() without freeing memory. The following code is NOT a memory leak: int main() { int *iptr iptr (int *) malloc(sizeof(int)); free(iptr); return 0;

However the following reports the block as "still reachable"

#include static int *iptr; int main() { iptr = (int *)malloc(sizeof (int)); return 0; }

As commented by Phil Betts, valgrind checks the state of memory AFTER main() exits. Yes, it is reachable because iptr is a static variable. But, it is still a memory leak.

-- Jerry Feldman Boston Linux and Unix user group http://www.blu.org PGP key id:C5061EA9 PGP Key fingerprint:053C 73EC 3AC1 5C44 3E14 9245 FB00 3ED5 C506 1EA9