C: Segmentation fault when using free() -

  • Thread starter Werg22
  • Start date
  • Tags
    Fault
In summary, it looks like you are trying to perform a linked structure insertion sort, but you are not properly freeing any allocated structures. This may be causing your program to crash.
  • #1
Werg22
1,431
1
C: Segmentation fault when using free() - Please Help!

This is giving me a big headache. Using free() for some reason results in segmentation faults.

I'm working on making linked structures to represent polynomials modulo a prime p. For the insertion sort below: the consumed pointer (the one passed to sort()) is to be assume to have been allocated on the heap, with a previous call with malloc. I have commented out the statements that lead to errors (basically all calls of free in insert()).

I don't have much time to get this code done, so if anyone can help me out, I'd be very thankful.

Code:
/*  definition of linked structure
     fields are: coeff for coefficient
                    expon for exponent
                    next for pointer to next term structure or NUL */

struct term {

   int coeff ;

   int expon ;

   struct term *next ;

};
/* implementation of insertion sort for term structures */ struct term *insert(struct term *a, struct term *b, int p)

{

   struct term *temp = malloc(sizeof(struct term));
   
   a->coeff = addp(a->coeff, 0, p);

   if (a->coeff == 0) {
   /* free(a) ************ ERROR ************** */
      return b;
   }

   if (b == NULL) {
      a->next = NULL;
      return a;
   }

   if (a->expon == b->expon) {

      if (addp(a->coeff, b->coeff, p) == 0) {
         temp = b->next;
       /*free (a);
      	 free (b);   ************ ERROR ************** */
      	 return temp;
      }
      
      b->coeff = addp(a->coeff, b->coeff, p);
      /*free(a); ************ ERROR **************  */
      return b;
   }

   if (a->expon < b->expon) {
      a->next = b;
      return a;
   }

   temp = b->next;
   b->next = insert(a, temp, p);
   return b;
}
struct term *sort (struct term *pterms, int p)
{
   struct term *temp;
   if (pterms == NULL) return NULL;	
   
   temp = pterms->next;

   return insert(pterms, sort(temp, p),p);
}
 
Last edited:
Technology news on Phys.org
  • #2


So... it is difficult to say what needs to be changed because it is not entirely clear to me what this code is meant to be doing. But, a couple observations.

- My first guess, just from glancing at the code and your description of the problem, is that you most likely are free()ing a single pointer value more than one time.

- Every call to "insert" results in the allocation of a value for "temp", but this value is never freed or preserved.

First off, this is bad on its own terms-- you should never let a function end without either freeing, or saving a pointer somewhere to, all structures allocated during this function. Like, consider the first clause in the function, the "a->coeff == 0" clause-- in this case you delete "a" and return. But you do not delete temp. The value you just allocated for temp stays in memory after the function ends, and if you call this function and invoke this clause enough times you will run out of memory and crash (even if you fix your problems with free()...).

But second off the issue with "temp" seems to indicate some deeper problems. Basically, you do something very unusual here:

struct term *temp = malloc(sizeof(struct term));
...
temp = b->next;
return temp;

What this means is: Allocate a new term structure; store a pointer to this structure in "temp"; then overwrite this pointer with a pointer equal to b->next; then return this new value (i.e. return the value equal to b->next). The pointer to the newly-allocated "term" structure is thrown away without being used! In fact there is no path in this function where any pointer to the structure allocated as "temp" is saved for later use.

What I think happening is that you somehow got the idea that
"temp = b->next"
means "copy the fields of the structure pointed to by b->next into the structure pointed to by temp". That isn't how structures work in C. You will have to say something like
memcpy(temp, b->next, sizeof(*temp));
...to get this effect. Instead what you said was "temp = b->next", which overwrites the pointer value pointed to by temp.

With this misapprehension about what "temp = b->next" means, you think that when you return "temp" you are returning a newly allocated structure which you allocated at the beginning of the function. But you're not. You're returning a pointer to the already-existing structure pointed to by b->next. Now you have two pointers running around, both of which point to the same structure. And if you free one of these pointers, then the other, then you will have freed the same structure twice, and you will crash.

Does this help any?
 
  • #3


Thanks a lot Coin! I've corrected the mistake with temp, but I still get the same problem when freeing memory. Here's the corrected cod. I added the definition of addp() if this helps.
Code:
/*  definition of linked structure
     fields are: coeff for coefficient
                    expon for exponent
                    next for pointer to next term structure or NUL */

struct term {

   int coeff ;

   int expon ;

   struct term *next ;

};

/* addition modulo p */

int addp(int a, int b, int p) 
{
   int k = a % p;

   int i = b % p;

   int j = (i + k) % p;

   if (j < 0)
      j = j + p;   

   return j;
}

/* implementation of insertion sort for term structures */ 

struct term *insert(struct term *a, struct term *b, int p)
{
   struct term *temp;
   
   a->coeff = addp(a->coeff, 0, p);

   if (a->coeff == 0) {
   /* free(a) ************ ERROR ************** */
      return b;
   }

   if (b == NULL) {
      a->next = NULL;
      return a;
   }

   if (a->expon == b->expon) {

      if (addp(a->coeff, b->coeff, p) == 0) {
         temp = b->next;
       /*free (a);
      	 free (b);   ************ ERROR ************** */
      	 return temp;
      }
      
      b->coeff = addp(a->coeff, b->coeff, p);
      /*free(a); ************ ERROR **************  */
      return b;
   }

   if (a->expon < b->expon) {
      a->next = b;
      return a;
   }

   temp = b->next;
   b->next = insert(a, temp, p);
   return b;
}

struct term *sort (struct term *pterms, int p)
{
   struct term *temp;

   if (pterms == NULL) return NULL;	
   
   temp = pterms->next;
   return insert(pterms, sort(temp, p),p);
}

Here is a test I've included in the main function:

Code:
   struct term n = {13, 14, NULL};

   struct term m = {12, 14, &n};

   struct term *p = sort(&m,7);
This results into a segmentation fault when I use free(). I've traced it, and I can't see what's wrong. :frown:
 
Last edited:
  • #4


In this new version you are not allocating anything. Why are you using free at all?
 
  • #5


I'm allocating the input through another function. But that other function doesn't need the structures that aren't used after sorting, so that's why I'm freeing.
 
  • #6


The test doesn't do any dynamic allocation. You are freeing something that hasn't been allocated.
 
  • #7


When you have something like
Code:
struct term n = {13, 14, NULL};
the struct is placed on the stack, not in dynamically allocated memory. free()ing things on the stack is a bad idea and is pretty much guaranteed to fail.

It's probably better to have the caller of insert() be responsible for freeing memory; insert() should make no assumptions about how the pointer was made, so in particular it better not assume it was made using malloc() or similar.
 
  • #8


Okay, my test was no good. But sort() still fails when its first argument is a pointer to a location that was allocated on the heap (and all the linked structures are also on the heap).
 
  • #9


Rather than asking us to debug your program for you, it is a good idea for you to learn how to do it yourself. Some guidelines:

(1) Learn how to use your debugger. I cannot underestimate the importance of doing this. Many professional organizations require that programmers verify their code by using the debugger to step through each and every line of code.

(2) Really learn how to use your debugger. Put break points in appropriate places and add conditions to your breakpoints so you can make the code zip over the parts you know are working correctly.

(3) Learn to love your debugger. It is one of your best allies in producing correct code.

(4) Add some print statements. Sometimes the ultimate cause of an error and the manifestation of the error are so far apart that identifying the cause with the debugger can be difficult.
 
  • #10


D H said:
Add some print statements. Sometimes the ultimate cause of an error and the manifestation of the error are so far apart that identifying the cause with the debugger can be difficult.

A good thing to try in this case would be to printf("Pointer %x\n", pointer); every time you allocate or free a term structure. This will allow you to quickly see (1) is everything you free() something you did in fact malloc()? (2) Do you ever free() anything more than once? It isn't Purify, but it may be enough to find the problem...

(I am still very confused why you need free() statements at all. This is supposed to be a sorting mechanism of some kind? Why on Earth would any sort need to delete elements from the list as it goes?)
 
  • #11


Another thing that might be happening: If you allocate an array of things all at once using malloc() or similar, then you must free() the entire array at once. You can't free() individual elements of the array--if you try to free the first one, you'll end up freeing the entire array; attempting to free any other element will just segfault, since you didn't allocate them individually.
 
  • #12


D H said:
Rather than asking us to debug your program for you, it is a good idea for you to learn how to do it yourself. Some guidelines:

(1) Learn how to use your debugger. I cannot underestimate the importance of doing this. Many professional organizations require that programmers verify their code by using the debugger to step through each and every line of code.

(2) Really learn how to use your debugger. Put break points in appropriate places and add conditions to your breakpoints so you can make the code zip over the parts you know are working correctly.

(3) Learn to love your debugger. It is one of your best allies in producing correct code.

(4) Add some print statements. Sometimes the ultimate cause of an error and the manifestation of the error are so far apart that identifying the cause with the debugger can be difficult.

Thanks for the pointers (no pun intended).

Coin said:
A good thing to try in this case would be to printf("Pointer %x\n", pointer); every time you allocate or free a term structure. This will allow you to quickly see (1) is everything you free() something you did in fact malloc()? (2) Do you ever free() anything more than once? It isn't Purify, but it may be enough to find the problem...

(I am still very confused why you need free() statements at all. This is supposed to be a sorting mechanism of some kind? Why on Earth would any sort need to delete elements from the list as it goes?)

It's because the linked structures actually represent polynomials. What I'm trying to do is relink those structures so that:

1. The coefficients are reduced modulo p
2. There are only terms with non-zero coefficients
3. No two terms have the same power (no repetition of power)

So when I, for example, see that the coefficient of a term reduces to 0 modulo p, I might as well just free the memory that it occupies because I don't need it. Thanks for the suggestion though, I'll try putting printf() statements to see what I get.

adriank said:
Another thing that might be happening: If you allocate an array of things all at once using malloc() or similar, then you must free() the entire array at once. You can't free() individual elements of the array--if you try to free the first one, you'll end up freeing the entire array; attempting to free any other element will just segfault, since you didn't allocate them individually.

I see. But what I've done is this:

struct term *p = malloc(n*sizeof(struct term)).

Doing something like

free(p + 1);

doesn't change that I can still access p, p + 2, ... , p + n - 1, right?
 
  • #13


No, free(p + 1); will fail. free() can only free entire chunks of memory that were allocated; if you allocated the entire array at once, it must be freed at once too. The only thing you can do there is free(p), and that will free the entire array.

free() doesn't know about the size of the things you're trying to deallocate.
 
  • #14


Werg22 said:
But what I've done is this:

struct term *p = malloc(n*sizeof(struct term)).

Doing something like

free(p + 1);

doesn't change that I can still access p, p + 2, ... , p + n - 1, right?
Just to elaborate on what adriank said:

First, Don't ever do that! You can only call free with a pointer returned malloc. p+1 was not returned by malloc; p was.

With p = malloc(n*sizeof(struct term)) once you call free(p) you must not access p[0], p[1], ... p[n-1]. To ensure that this won't happen, it is best to reset the pointer to null after calling free: free(p); p = NULL;

adriank said:
free() doesn't know about the size of the things you're trying to deallocate.
It most certainly does. Otherwise, how could the system know that
p = malloc (10240); ... free (p);
just released 10 kilobytes of memory?

How it knows that is implementation dependent. The two most common techniques are (1) maintaining some kind of table that associates an allocated address with the number of bytes allocated at that address, or (2) storing the amount of memory allocated just before the pointer returned by malloc. In any case, one reason calling free(p+1) fails is because the system has no idea how much memory is being released.
 
  • #15


I was unclear. I meant that if you allocate an array of things and attempt to free just one of them, it doesn't know that you want it to only that one element (it doesn't observe the type of pointer you're calling free() on). If you try to get it to free just the first element of an array somehow, free() doesn't know that; it just knows that at that location the entire array was allocated. Of course it knows that the entire array was allocated at once, and calling free() with the location of the array would free the entire array, whether you thought you passed it the type of pointer to one object or not (whatever that is, since an array and a pointer to an element of the array have the same type in C).

Perhaps I'm still unclear; in that case it's probably safe to ignore that bit.
 
  • #16


Now I see what the problem was. I was trying to free part of memory allocated with malloc, whereas, as you guys tell me, I can only free the entire block of memory. Why do we have this limitation though? It seems to me we would get some gains in memory usage if it were allowed.

Edit:

I've rewrote a new version of my code. Instead of allocating all the memory at once, memory is allocated term by term. This allows insert() to use the free statements, since all the terms it visits have been independently stored in memory.

Of course this calls for an additional function that will free everything used in case of a failure to allocate memory for a single term, but it's easy to write.

Thank you for all the help.
 
Last edited:

1. What is a segmentation fault in C?

A segmentation fault, also known as a segfault, is an error that occurs when a program attempts to access memory that it is not allowed to access. This can happen when a program tries to read or write to a memory location that is outside of its allocated boundaries.

2. Why does a segmentation fault occur when using the free() function?

The free() function in C is used to deallocate memory that was previously allocated using functions such as malloc() or calloc(). A segmentation fault can occur when the program tries to free a memory address that was not previously allocated or has already been freed. This can also happen if the program tries to free the same memory address more than once.

3. How can I debug a segmentation fault in my C program?

One way to debug a segmentation fault is to use a debugger, such as GDB, to step through your code and see where the error is occurring. You can also use print statements to check the values of variables and memory addresses at different points in your code. Additionally, reviewing your code for potential memory management errors, such as not properly allocating or freeing memory, can help prevent segmentation faults.

4. Can a segmentation fault be fixed?

Yes, a segmentation fault can be fixed. As mentioned before, reviewing your code for potential memory management errors can help prevent these errors from occurring. Additionally, using debugging tools and techniques can help identify and fix the source of the segmentation fault.

5. Are there any best practices to avoid segmentation faults when using the free() function?

One best practice to avoid segmentation faults when using the free() function is to always check if the pointer being passed to free is not NULL. This can prevent the program from trying to free a memory address that was not properly allocated. Additionally, it is good practice to set any pointers that have been freed to NULL to avoid accidentally trying to free them again.

Similar threads

  • Programming and Computer Science
Replies
3
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
8K
  • Programming and Computer Science
Replies
4
Views
2K
  • Programming and Computer Science
Replies
8
Views
4K
  • Programming and Computer Science
Replies
8
Views
1K
  • Programming and Computer Science
Replies
4
Views
2K
  • Programming and Computer Science
Replies
20
Views
4K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
1K
  • Programming and Computer Science
Replies
2
Views
1K
  • Programming and Computer Science
Replies
1
Views
1K
Back
Top