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.

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.

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.

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.


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.

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.

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"?

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;
};

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

with something like
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).

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.

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.

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.

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.

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." ;)

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.