LinuxQuestions.org
Welcome to the most active Linux Forum on the web.
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 09-11-2011, 02:42 AM   #1
marian57
LQ Newbie
 
Registered: Aug 2010
Posts: 6

Rep: Reputation: 1
Freeing dynamically allocated memory in a C recursive function


Hi! all
I have a problem in a C program; it crashes while on 'free()' inside a recursive function, the message being that it cannot find a pointer on the heap.
It computes factorial numbers of biiig length using strings of digits rather than numeric variables. Because I could not find the bug, I modified the program so that I can use a loop instead than recursion if I choose to do so; well the problem disappears, using a loop, and the rest of the code (doing 'N * (N - 1) etc.) remains the same.
In recursive mode there is some kind of overflow, I can see it using 'printf()' but am not able to fix it, and all that the recursive function does is allocating memory to accommodate 'N -1' N - 1 times then copies 'N' to that memory, calls a function to do the actual '- 1' operation, and calls a 'multiplication' function which returns the partial result. Exactly the same thing, using the same functions happens in the 'loopit()' function; the only difference is that in this case I can normally free the allocate memory.
In the 'multiplication' function 'realloc()' is called when needed, ad that seems to be part of the bug, but that (exactly the same) is done in either modes, and when linked to '-ldmalloc' all memory results as freed in 'loop' mode, but "free()' is crashing in 'recurse' mode.
The only way I am able to get it to work in recursive mode is by calculating the total number of digits in the eventual factorial, then
allocating that length + 2 to the 'number' string in 'main()', and passing the size as a pointer to the other functions; that way 'realloc()' needs not be called, but it involves calculating the number o digits before hand.
So probably 'realloc()' is the problem, but it is called extensively in 'loop' mode without problems.
I'm attaching the source, but this version cannot do the job explained above (number of digits in advance), so it crashes in 'recurse' mode on big numbers.
Thank you for having read all this, and some suggestions would be appreciated.
Regards marian57

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#ifdef DMALLOC
#include <dmalloc.h>
#endif

#define MESS "Usage:\n\
<prog> [-h]|[-l <num1> [<num2>]]\n\
Description:\n\
Computes the factorial of 'num1', or multiplies 'num1' by 'num2'.\n\
Options:\n\
-h - Print this\n\
-l - Compute the factorial of 'num1' using a loop, rather than recursion."

int NOREC = 0;

char *loopit(char *nu, int *sz);
char *fact(char *n, int *sz);
char *mulstr(char *st1, char *st2, int *s);
char *subone(char *sb);
char *reverse(char *rv);

/* ************************************************************************ */
int main(int argc, char **argv) {
int l = 0, i, num1 = -1, num2 = -1;
for(i = 1; i < argc; i++) {
if(!strcmp(argv[i], "-h")) {
puts(MESS);
return 0;
}
else if(!strcmp(argv[i], "-l"))
NOREC = 1;
else if(isdigit(*argv[i])) {
if(num1 == -1)
num1 = atoi(argv[i]);
else if(num2 == -1)
num2 = atoi(argv[i]);
else {
puts("\aMaximum 2 numbers.");
puts(MESS);
exit(1);
}
}
else {
puts("\aInvalid argument.");
puts(MESS);
exit(1);
}
}
if(num1 == -1 && num2 == -1)
puts("\a\nWe need a number.");
else if(num1 > -1 && num2 > -1) {
int sz = 16;
char *m1 = malloc(sz), *m2 = malloc(sz);
if(!m1 || !m2) {
perror("Allocation m1/m2");
exit(1);
}
sprintf(m1, "%d", num1);
sprintf(m2, "%d", num2);
m1 = mulstr(m1, m2, &sz);
printf("%d * %d =\n %s\n", num1, num2, m1);
}
else {
int num = num1;
for(; {
if(!*argv[1]) {
puts("\n<Enter> another number.");
scanf("%d", &num);
if(num < 0)
return 0;
while(getchar() != '\n');
}
system("clear");
int s = 16; /* The size which will grow to the eventual length of n1!. */
char *n1 = malloc(s);
sprintf(n1, "%d", num);
if(NOREC)
n1 = loopit(n1, &s);
else
n1 = fact(n1, &s);
l = strlen(n1);
printf("%d! = %s\nused %d bytes\nis %d digits long.\n", num, n1, s, l);
free(n1);
argv[1] = "";
num = -1;
}
}
return 0;
}

/* Computes N! usinf a loop. */
/* ************************************************************************ */
char *loopit(char *nu, int *sz) {
char *snu = malloc(strlen(nu) + 1);
if(!snu) {
perror("Allocation snu");
exit(1);
}
strcpy(snu, nu);
while(strcmp(snu, "1")) {
*sz = strlen(nu) + 1;
snu = subone(snu);
if(!strcmp(snu, "1"))
break;
nu = mulstr(nu, snu, sz);
}
free(snu);
return nu;
}

/* Recursively computes N! in the form of string f. */
/* ************************************************************************ */
char *fact(char *f, int *s) {
if(!strcmp(f, "1") || !strcmp(f, "0"))
strcpy(f, "1");
else {
char *mone = malloc(strlen(f) + *s + 10);
if(!mone) {
perror("Allocation mone");
exit(1);
}
strcpy(mone, f);
mone = subone(mone);
if(f && *f && mone && *mone) {
if(strcmp(mone, "1"))
f = mulstr(f, fact(mone, s), s);
free(mone);
}
else {
printf("ERROR\a empty string.\n");
getchar();
}
}
return f;
}

/* Multiplies a * b in the form of strings st1 and st2. */
/* ************************************************************************ */
char *mulstr(char *st1, char *st2, int *s) {
char *m1 = st1, *m2 = st2, *p1 = NULL, *p2 = NULL;
char **lines = NULL;
char *swap = NULL;
int i, j, k, l2 = 0, l1 = 0, cr;
if(strlen(st1) < strlen(st2)) {
m1 = st2;
m2 = st1; /* Pointer to the short string */
}
l2 = strlen(m2);
l1 = strlen(m1);
if((lines = (char**)malloc(sizeof(char*) * l2)) == NULL) {
perror("Allocation lines 0");
exit(1);
}
for(i = 0; i < l2; i++) {
if((lines[i] = (char*)malloc(l1 + l2 + 2)) == NULL) {
perror("Allocation 1");
exit(1);
}
}
p2 = m2 + l2 - 1;
i = 0;
cr = 0;
while(p2 >= m2) {
int n2 = *p2 - 48, n5 = 0;
j = 0;
p1 = m1 + l1 - 1;
cr = 0;
while(p1 >= m1) {
int n1 = *p1 - 48, n3 = n1 * n2 + cr, n4 = n3 / 10;
n5 = n3 % 10;
lines[i][j++] = n5 + 48;
cr = n4;
p1--;
}
lines[i][j++] = cr + 48;
lines[i][j] = 0;
for(k = i; k < l2 - 1; k++)
strcat(lines[i], "0");
lines[i] = reverse(lines[i]);
for(k = 0; k < i; k++)
strcat(lines[i], "0");
i++;
p2--;
}
if(*s < l1 + l2 + 2) {
*s = l1 + l2 + 2;
if((st1 = (char*)realloc(st1, *s)) == NULL) {
perror("Allocation st1 re");
exit(1);
}
}
memset(st1, 48, l1 + l2 + 2);
*(st1 + l1 + l2 + 1) = 0;
cr = 0;
for(k = l1 + l2 - 1; k >= 0; k--) {
int dtot = 0, d1, d2;
for(i = 0; i < l2; i++)
dtot += (lines[i][k] - 48);
dtot += cr;
d1 = dtot / 10;
d2 = dtot % 10;
cr = d1;
st1[k + 1] = d2 + 48;
}
st1[0] = cr + 48;
st1[l1 + l2 + 1] = 0;
if((swap = (char*)malloc(*s)) == NULL) {
perror("Allocation swap");
exit(1);
}
strcpy(swap, st1);
while(*swap && *swap == '0')
memmove(swap, swap + 1, strlen(swap));
strcpy(st1, swap);
free(swap);
for(i = 0; i < l2; i++)
free(lines[i]);
free(lines);
return st1;
}

/* Reverses a string of digits. */
/* ************************************************************************ */
char *reverse(char *rv) {
int ln = strlen(rv);
char *p = rv + ln - 1, *tmp = alloca(ln + 1);
int j = 0;
if(!tmp) {
perror("Allocation tmp");
exit(1);
}
while(p >= rv) {
*(tmp + j++) = *p;
p--;
}
*(tmp + j) = 0;
strcpy(rv, tmp);
return rv;
}

/* 'subtracts' 1 from a string of digits. */
/* ************************************************************************ */
char *subone(char *sb) {
int nm = atoi(sb) -1;
sprintf(sb, "%d", nm);
return sb;
}

Last edited by marian57; 09-11-2011 at 06:31 AM.
 
Old 09-11-2011, 03:51 AM   #2
paulsm4
Guru
 
Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863
Blog Entries: 1

Rep: Reputation: Disabled
Hi -

1. Please use code tags. Here is the offending module:
Code:
char *
subone(char *sb) {
  char *p = sb + strlen(sb) - 1;
  char *swap = alloca(strlen(sb) + 1);
  while(p >= sb) {
    int dig = *p - 48;
    if(dig > 0) {
      *p = dig + 47;
      break;
    }
    else
     *p = 57;
    p--;
  }
  strcpy(swap, sb);
  while(*swap && *swap == '0')
    memmove(swap, swap + 1, strlen(swap));
  strcpy(sb, swap);
  return sb;
}
2. The positive comments:
a) You're calling malloc() and alloca() with "strlen()+1" - good!

b) You're pairing "free()" with "malloc()" in "loopit()", etc - good!

3. I'm frankly not sure what's wrong with "subone(char *sb)". But with all due respect, I would encourage you to simply re-write it. Think of what you're TRYING to do ... and do it differently. Simpler. K.I.S.S.

IMHO .. PSM
 
1 members found this post helpful.
Old 09-11-2011, 06:39 AM   #3
marian57
LQ Newbie
 
Registered: Aug 2010
Posts: 6

Original Poster
Rep: Reputation: 1
Thank you K.I.S.S.
That function was very silly; I was thinking in term of looong strings, but that string could not grow longer than 100000 or so or it would take a lifetime to compute.
However the bug is still there; I thought I had been a bit too lucky to get an answer so quickly.
Regards marian57
 
Old 09-11-2011, 09:09 AM   #4
johnsfine
Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,138

Rep: Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127
Skimming through the code from the top, the first bug I spotted was
Code:
f = mulstr(f, fact(mone, s), s);
free(mone);
When you call fact(mone,s) that can realloc the buffer pointed to by mone. So the subsequent free(mone) corrupts the memory pool.

So I think you wanted:

Code:
mone = fact(mone, s);
f = mulstr(f, mone, s);
free(mone);
Quote:
Originally Posted by paulsm4 View Post
Here is the offending module:
Wrong. The location of the symptom of a bug is just the location of the symptom of the bug, not necessarily the location of the bug.

Backtracking from the symptom of this kind of bug to the cause takes a lot of knowledge and patience in the debugger, and usually isn't required. That's why I skimmed through the code looking for the bug instead of even trying a debugger.

"Fixing" the code around the symptom (as you apparently convinced marian57 to try) is an even worse choice. (It drives me nuts every time programmers working with or for me make that mistake). At best, that accomplishes nothing (as it did for marian57 this time). More often, it moves the symptom around and adds to the confusion and causes you to add more bugs or leave bugs in the final product that you should have resolved.

Quote:
Originally Posted by marian57 View Post
I thought I had been a bit too lucky to get an answer so quickly.
I think it is still very quick. But maybe it could have been quicker.

I don't know who might have looked at your initial question before I did who might have noticed the bug if you had formatted the question properly (code tags and proper indentation on the code and better paragraph structure and white space on the question).

Maybe paulsm4 would have spotted the bug, instead of testing the code, if it had been properly indented. The important part of your code is very tiny. Only the lack of indenting makes the important parts hard to spot making the bug harder to spot.

Because of the bad formatting, I skipped your post the first time I noticed it. I was bored and came back to it an hour later. So if a better formatted post didn't get you an answer much earlier from someone else, it would at least have gotten you my answer an hour earlier.

Last edited by johnsfine; 09-11-2011 at 09:35 AM.
 
1 members found this post helpful.
Old 09-11-2011, 02:01 PM   #5
paulsm4
Guru
 
Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863
Blog Entries: 1

Rep: Reputation: Disabled
@johnsfine -

I didn't "test" the code; I just glanced at it, satisfied myself that that a few of the most common errors (malloc (strlen), or multiple free's) were NOT the problem, and tried to politely suggest to the OP that "subone" was "sub-optimal".

I DIDN'T notice that "fact()" was playing games with "mone". Mea culpa.

But johnsfine, please get get the heck off your high horse and stop being such a condescending twit. OK?
 
Old 09-11-2011, 02:25 PM   #6
johnsfine
Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,138

Rep: Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127Reputation: 1127
Quote:
Originally Posted by paulsm4 View Post
I didn't "test" the code; I just glanced at it, satisfied myself that that a few of the most common errors (malloc (strlen), or multiple free's) were NOT the problem, and tried to politely suggest to the OP that "subone" was "sub-optimal".
I completely misunderstood your "Here is the offending module". Forums tend toward that kind of miscommunication. The OP apparently reacted to something in your post, motivating focus on that sub optimal function with the misguided belief that effort was toward correcting the bug. I stand by my stated viewpoint that such efforts are a counter productive response to unstable bugs.

Quote:
I DIDN'T notice that "fact()" was playing games with "mone". Mea culpa.
I understand that as saying you understood something in my post as saying you are somehow at fault for not noticing the bug. One of us is misunderstanding: I said nothing to imply you were at fault for not noticing the bug, and I clearly said the opposite. The bad formatting of the original post was responsible for some delay in someone noticing the bug.

As for the rest of your post, I don't think a direct reply would be constructive.

Last edited by johnsfine; 09-11-2011 at 02:29 PM.
 
Old 09-11-2011, 02:57 PM   #7
ta0kira
Senior Member
 
Registered: Sep 2004
Distribution: FreeBSD 9.1, Kubuntu 12.10
Posts: 3,078

Rep: Reputation: Disabled
That seems like a whole lot of code for what it does. My suggestion is to start over. If you're going with the same algorithm, at least break your procedures up into smaller ones.
Kevin Barry
 
1 members found this post helpful.
Old 09-11-2011, 07:58 PM   #8
marian57
LQ Newbie
 
Registered: Aug 2010
Posts: 6

Original Poster
Rep: Reputation: 1
Thanks johnsfine for showing me the bug

Thanks all of you
I'm only a retired boilermaker, who has picked up a bit of C on the web.
What I wanted to do there (totally useless) was to overcome the limits a factorial can have using any numeric types.
I simply took the idea from a tutorial that was using int variables. I could see, using printf() that the pointers being freed were not those pointing to 'mone', but I had not even thought about doing fact(mone, s); I vas concentrating on 'f' which was my target, and all the memory addresses were messed up.
As for not indenting the code; I had posted on another site where 4 leading blanks were needed for lines of code, so I used sed to produce such a file, but here it didn't work. I will read the FAQ and make sure to do things right in future.
Regards marian57
 
1 members found this post helpful.
  


Reply

Tags
dynamic, programming, recursive


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] C: Segmentation fault when freeing allocated 2D array aihaike Programming 2 06-02-2011 12:12 AM
local dynamically allocated array in fortran otoomet Programming 5 10-21-2009 09:28 AM
Freeing memory allocated in a function con Programming 4 01-02-2006 04:25 AM
In C, using qsort for dynamically allocated array ntmsz Programming 7 08-23-2005 11:33 AM
Need help: Seg fault, Memcpy, and dynamically allocated arrays benobi Programming 3 06-09-2005 11:58 PM


All times are GMT -5. The time now is 03:04 AM.

Main Menu
Advertisement
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