by Werg22
Tags: fault, free, segmentation
 P: 1,520 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.  /* 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); }
 P: 587 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?
 P: 1,520 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. /* 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:  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.
Mentor
P: 14,457

In this new version you are not allocating anything. Why are you using free at all?
 P: 1,520 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.
 Mentor P: 14,457 The test doesn't do any dynamic allocation. You are freeing something that hasn't been allocated.
 P: 534 When you have something like 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.
 P: 1,520 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).
 Mentor P: 14,457 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.
P: 587
 Quote by D H 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?)
 P: 534 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.
P: 1,520
 Quote by D H 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).

 Quote by Coin 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.

 Quote by adriank 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?
 P: 534 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.
Mentor
P: 14,457
 Quote by Werg22 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;

 Quote by adriank 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.
 P: 534 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.
 P: 1,520 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.

 Related Discussions Engineering, Comp Sci, & Technology Homework 1 Engineering, Comp Sci, & Technology Homework 2 Programming & Computer Science 5 General Math 0 Computing & Technology 5