LinuxQuestions.org
Help answer threads with 0 replies.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
Search this Thread
Old 08-27-2013, 02:14 PM   #1
ayush.suhane
LQ Newbie
 
Registered: Aug 2013
Posts: 5

Rep: Reputation: Disabled
Corrupted double-linked list


Hi,

I have a code which uses a linked list initially, but after its use presently I am not freeing memory allocated to it. The code compiles without any error, but while running gives a error : glibc detected, corrupted double-linked list.
I was wondering if freeing memory is necessary condition. and if yes how to free memory for struct linked list withh parameters as x,y,z and a pointer *next.

Using fuctions like push and pop , I have already freed memory allocated for new nodes. Only head pointer memory is allocated at the end of the code. Please tell me the problem and suggest some probable solutions.

Code is pretty complex so it would be difficult to post it here.
Thanks in advance.
 
Old 08-27-2013, 02:22 PM   #2
TB0ne
Guru
 
Registered: Jul 2003
Location: Birmingham, Alabama
Distribution: SuSE, RedHat, Slack,CentOS
Posts: 14,244

Rep: Reputation: 2475Reputation: 2475Reputation: 2475Reputation: 2475Reputation: 2475Reputation: 2475Reputation: 2475Reputation: 2475Reputation: 2475Reputation: 2475Reputation: 2475
Quote:
Originally Posted by ayush.suhane View Post
Hi,

I have a code which uses a linked list initially, but after its use presently I am not freeing memory allocated to it. The code compiles without any error, but while running gives a error : glibc detected, corrupted double-linked list.
I was wondering if freeing memory is necessary condition. and if yes how to free memory for struct linked list withh parameters as x,y,z and a pointer *next.

Using fuctions like push and pop , I have already freed memory allocated for new nodes. Only head pointer memory is allocated at the end of the code. Please tell me the problem and suggest some probable solutions.

Code is pretty complex so it would be difficult to post it here.
Thanks in advance.
Well, without seeing any code at all, and just going by an error message, the best we can tell you is "There's a problem in your code". You don't even say which version/distro of Linux you're using, or what language you wrote your code in, so there's not much anyone can tell you.
 
Old 08-27-2013, 03:28 PM   #3
ayush.suhane
LQ Newbie
 
Registered: Aug 2013
Posts: 5

Original Poster
Rep: Reputation: Disabled
Sorry this is my first post in this forum.

I am using Linux mint and a gcc compiler.I have written my code in C.

this is a .c file with all the functions involved are already included. I have defined a struct in a Global .h file to access from multiple files.Struct is then typedefined as node in all files.

typedef struct linked_list node;
31
32
33 int Function(){
34

36 int i=0,j=0,count;
37 double point_x,point_y,point_z;
41
42 double cellsize=0;
43 int x_numcell=0,y_numcell=0,z_numcell=0,total_numcells=0;
44
45 cellsize = ((Mindist)/(R3));
46 printf("Cellsize: %lf\n",cellsize);
47 x_numcell = (ceil)(Lx/cellsize);
48 y_numcell = (ceil)(Ly/cellsize);
49 z_numcell = (ceil)(Lz/cellsize);
51 total_numcells = x_numcell * y_numcell * z_numcell;
52
56
57 Grid = (double **)malloc(total_numcells * sizeof(double*));
58 for(i=0;i<total_numcells;i++)
59 Grid[i] = (double *)malloc(3 * sizeof(double));
60
61
62 for(i=0;i<total_numcells;i++)
63 {
64 for(j=0;j<3;j++) Grid[i][j] = 0;
65 }
66
67 /*
68 First point selection and insertion in lists
*/
70 point_x = ((int)(gsl_rng_uniform(URN) * Nx))* CLx;
71 point_y = ((int)(gsl_rng_uniform(URN) * Ny))* CLy;
72 point_z = ((int)(gsl_rng_uniform(URN) * Nz))* CLz;
73
76 //Updating lists

78
79 Grid[0][0] = point_x;
80 Grid[0][1] = point_y;
81 Grid[0][2] = point_z;
82
83 node *head,*t;
84
85 head = (node *)malloc(sizeof(node));
86 t=head;
87 t -> x = point_x;
88 t -> y = point_y;
89 t -> z = point_z;
90 t -> next = NULL;
91
92
93 printf("First point pushed : x: %lf , y : %lf , z: %lf\n",t->x,t->y,t->z);
94 count = CountSize(head) ;
95 printf("Count after first point : %d\n",count);
96 /*
97 Check and pop every element in activelist While it is not empty
98 */
99 //count = 1;
100 int grid_counter=0;
101 while(count != 0)
102 {
106 head = Pop(head); //Pops a head element from the list
107 count = CountSize(head); // Counts the number of elements in present list
108 printf("Count after popping : %d\n",count);
109 for(i=0;i<Constant;i++)
117 {
119 RandomPointPDS(); //Obtains a random point (finite distance away)from a selected point
120
121 if(CheckPDS(grid_counter)==1)
122 {
123 head = Push(head); //Pushes the head element
124 count = CountSize(head);
126 grid_counter=grid_counter+1;
127 Grid[grid_counter][0] = New_x;
128 Grid[grid_counter][1] = New_y;
129 Grid[grid_counter][2] = New_z;
132 }
133 }
135 count=CountSize(head);
136 printf("End Count: %d\n",count);
137 }



So finally only head element would be stored in list. I have also given NULL value to head pointer at the end of the program.
If only this code is compiled and run, it doesnot give any error. But since it is just a part of code, when it is linked with another part of code, it gives glibc error. Is it specifically a memory allocation error or is it related to something else.
 
Old 08-27-2013, 07:16 PM   #4
johnsfine
Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,055

Rep: Reputation: 1104Reputation: 1104Reputation: 1104Reputation: 1104Reputation: 1104Reputation: 1104Reputation: 1104Reputation: 1104Reputation: 1104
Quote:
Originally Posted by ayush.suhane View Post
I was wondering if freeing memory is necessary condition.
No. Freeing memory is not necessary and failing to free memory is not causing the problem you reported.

A very large amount of failing to free memory might cause a 32-bit program to exhaust its virtual address limit or a 64 bit program to exhaust the available swap space. That would be a serious problem and under those conditions freeing memory would be necessary. But those symptoms don't fit your description.


Quote:
Using fuctions like push and pop , I have already freed memory allocated for new nodes. Only head pointer memory is allocated at the end of the code. Please tell me the problem and suggest some probable solutions.
Something in the program is writing to some memory that is used for something else by some other part of the program. That could be caused by continuing to use a struct after freeing it. But that is just a wild guess. Many other bugs could have the same symptom.

Last edited by johnsfine; 08-27-2013 at 07:19 PM.
 
Old 08-27-2013, 11:29 PM   #5
ntubski
Senior Member
 
Registered: Nov 2005
Distribution: Debian
Posts: 2,397

Rep: Reputation: 814Reputation: 814Reputation: 814Reputation: 814Reputation: 814Reputation: 814Reputation: 814
Running the code with valgrind can help discover the source of memory corrupting bugs.

PS please put [code][/code] tags around your code. And leave out the line numbers, they're just distracting.
 
Old 08-27-2013, 11:57 PM   #6
psionl0
Member
 
Registered: Jan 2011
Distribution: slackware_64 14.0
Posts: 510
Blog Entries: 2

Rep: Reputation: 68
Quote:
Originally Posted by ayush.suhane View Post
83 node *head,*t;
84
85 head = (node *)malloc(sizeof(node));
86 t=head;
87 t -> x = point_x;
88 t -> y = point_y;
89 t -> z = point_z;
90 t -> next = NULL;
91
You talk about a double-linked list but you haven't assigned a value to t -> prev.

Do you really mean "double-linked" or do you mean "single-linked"?
 
Old 08-28-2013, 03:00 AM   #7
ayush.suhane
LQ Newbie
 
Registered: Aug 2013
Posts: 5

Original Poster
Rep: Reputation: Disabled
Thanks old.
I had made a single linked list but the error is showing otherwise.
Structure i had defined is given as
strict linked
{
double x;
double y;
double z;
strict linked *next;
};
 
Old 08-28-2013, 06:51 AM   #8
johnsfine
Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,055

Rep: Reputation: 1104Reputation: 1104Reputation: 1104Reputation: 1104Reputation: 1104Reputation: 1104Reputation: 1104Reputation: 1104Reputation: 1104
Why did you select that specific chunk of code to post? It seems pretty clear the symptom is in a different section of code and fairly likely the cause is in yet another section of code.

If the cause is in the section you posted, then the most likely problem would be grid_counter is getting too large. You might want to follow the statement

Code:
grid_counter=grid_counter+1;
with something like
Code:
if ( grid_counter >= total_numcells ) {
   printf("Bug in program:  grid_counter is too large.\n");
   exit(-1); }
With the appropriate headers included, you could do something like that more concisely with an assert macro (which then is active only in a debug build).

Last edited by johnsfine; 08-28-2013 at 06:54 AM.
 
1 members found this post helpful.
Old 08-28-2013, 11:48 AM   #9
ayush.suhane
LQ Newbie
 
Registered: Aug 2013
Posts: 5

Original Poster
Rep: Reputation: Disabled
Thanks.

Why I have written only this code is because when I run the other part of the code by predefining the values obtained from this code, it runs perfectly fine. But only after the introduction of this part creates error.
However , if I run only this part of code , it also runs fine without crashing. Error occurs when both are linked.

Regarding grain_counter, I had already printed value of grain counter during the run, and it doesnot get to values higher than total_numcells.
 
Old 08-28-2013, 01:33 PM   #10
PTrenholme
Senior Member
 
Registered: Dec 2004
Location: Olympia, WA, USA
Distribution: Fedora, (K)Ubuntu
Posts: 4,147

Rep: Reputation: 330Reputation: 330Reputation: 330Reputation: 330
You have no check after you do the maloc call to see of you've got a non-null return. Perhaps your system memory is unlimited, but, if not, such checks are strongly advised.
 
Old 08-28-2013, 02:06 PM   #11
johnsfine
Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,055

Rep: Reputation: 1104Reputation: 1104Reputation: 1104Reputation: 1104Reputation: 1104Reputation: 1104Reputation: 1104Reputation: 1104Reputation: 1104
Quote:
Originally Posted by ayush.suhane View Post
Why I have written only this code is because when I run the other part of the code by predefining the values obtained from this code, it runs perfectly fine. But only after the introduction of this part creates error.
However , if I run only this part of code , it also runs fine without crashing. Error occurs when both are linked.
The previous things you said pretty much established this is the kind of bug usually called a "memory clobber".

It is typical for a memory clobber that the bug is in one section of the code, but the symptom is in another section of code and making some unrelated change in a third section of code can make the symptom appear or disappear.

Beginning programmers often go bogged down in investigating some section of code where changes make the symptoms appear or disappear. In a memory clobber bug that is a total waste of time.

In a small enough project, a competent program could desk check the whole thing and spot the bug. Is this project really so big you can't post the whole source?

In a big enough project, you need skilled use of a debugger to track it down systematically.

First you need to "break" at the symptom and look around for the proximate cause (what clobbered memory location directly caused the symptom).

Then you need to restart the program, usually break on the storage of the correct value in that location and set a data breakpoint to catch the clobber.

Sometimes you find the correct data wasn't stored, and the "clobbered" location wasn't actually clobbered. Instead some correct code copied wrong data from some earlier memory clobber into the location that seemed to have been clobbered. Then you need to start over again tracking that earlier apparent clobber.

I do that a lot, because I work on two different teams and no other engineer on either team has the skills to backtrack a memory clobber competently, so I end up diagnosing any memory clobber anyone has on either project.

In theory, tools like Valgrind can catch a lot of these bugs, so you don't need the skill (nor the large amount of time) needed to backtrack them. In practice I find those tools fail far more often than they work. But I still wouldn't recommend against trying them.

Still, this sounds like a beginner project and in a beginner project, desk checking the whole source code is typically easier than debugging a memory clobber.

Quote:
Originally Posted by PTrenholme View Post
You have no check after you do the maloc call to see of you've got a non-null return. Perhaps your system memory is unlimited, but, if not, such checks are strongly advised.
I would disagree anyway. I think there is little value in changing a non graceful crash into a slightly less non graceful crash for an obscure situation that is quite unlikely to occur.

But I especially disagree in the middle of diagnosing a memory clobber bug that could not possibly be the result of failing to check for a null return from malloc.

Any change made to the code could hide or disguise a memory clobber bug. Now is not the time for general improvements in style.

Last edited by johnsfine; 08-28-2013 at 02:18 PM.
 
1 members found this post helpful.
Old 08-29-2013, 12:04 PM   #12
PTrenholme
Senior Member
 
Registered: Dec 2004
Location: Olympia, WA, USA
Distribution: Fedora, (K)Ubuntu
Posts: 4,147

Rep: Reputation: 330Reputation: 330Reputation: 330Reputation: 330
Quote:
Originally Posted by johnsfine View Post
[...]Now is not the time for general improvements in style.
I somewhat disagree: I believe that a good, consistent, style ts the basis of good programs. If the OP is new to programming, establishing a good habits now is a better choice than constant failure from the lack thereof.

My point was that obvious failure conditions should, as a matter of style, always be checked. Not having seen the rest of the code, I was trying to suggest that the OP review his code and add those obvious checks.

I should remark that, when I first learned to code (more than half a century ago), memory was quite limited, and not checking after any memory allocation (attempt) was a VERY common point of failure.

The cost of copious use of ASSERT macros, etc., is, in my mind, much less that failure to do so. But, hey, I'm really somewhat "old school."
 
Old 08-29-2013, 12:34 PM   #13
johnsfine
Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,055

Rep: Reputation: 1104Reputation: 1104Reputation: 1104Reputation: 1104Reputation: 1104Reputation: 1104Reputation: 1104Reputation: 1104Reputation: 1104
Quote:
Originally Posted by PTrenholme View Post
The cost of copious use of ASSERT macros, etc., is, in my mind, much less that failure to do so. But, hey, I'm really somewhat "old school."
I generally agree. But the reason ASSERTs are low cost (they are compiled into only debug and not release builds) is sometimes a reason they are less valuable.

I'm not sure how much my recent experience is a distortion due to the type of mathematicians (vs. real software engineers) I work with and the type of mathematics they work on. But my experience has been that ASSERTing in range for the non obvious computed indexes is more useful than all other ASSERTs combined.

Most of the time a software engineer uses an index, the fact that it is in range will be locally obvious from the structure of the code. The mathematicians I work with are much more likely to write constructs like what I commented on earlier in the OP's posted code: An index is computed in a way that gives no local reason why one would trust that the index is in range. Elsewhere, deep in the theory underlying the algorithm, there is usually some effect limiting the range of the computed index. But there is usually some corner case the mathematician hasn't thought through in which the computed index isn't limited quite enough.
Over years of helping them debug things, as many bugs have been due to such corner cases producing out of range indexes as were due to all other bugs combined. Each time we finish a struggle with one of those bugs, I remind them it is easier to write a hundred ASSERTs that non obvious indexes are in range than it is to debug a single instance of such a corner case without those ASSERTs.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
[SOLVED] What's the difference between Segfault and corrupted double-linked list r3pl4y Programming 12 02-18-2013 02:35 AM
smallbin double linked list corrupted thirumalesh Programming 2 06-27-2011 03:40 AM
glibc detected *** corrupted double-linked list rubadub Programming 11 09-21-2008 01:21 PM
*** glibc detected *** corrupted double-linked list: 0x084a25c0 *** Looooooka Slackware 2 03-06-2006 08:41 AM
What the heck is a corrupted double linked list??? The_Nerd Programming 18 02-10-2006 03:17 PM


All times are GMT -5. The time now is 10:51 PM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration