469,326 Members | 1,351 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,326 developers. It's quick & easy.

Dinamic Array Allocation problems

hi, I'm writing a program a kind of calculator that should work with very big numbers (thousand of digits). So, numbers are rappresented by a struct that contains a pointer to integer, e 2 int for dimension of the array e number of digits.
the pointer is than used for the malloc of the array...
my 2 problems are:

1)some time, when I use my exp function I get the error:

*** glibc detected *** ./a.out: free(): invalid size: 0x0975a328 ***
======= Backtrace: =========
/lib/tls/i686/cmov/libc.so.6[0xb7e8b604]
/lib/tls/i686/cmov/libc.so.6[0xb7e8eabc]
/lib/tls/i686/cmov/libc.so.6(__libc_malloc+0x95)[0xb7e8f9c5]
./a.out[0x804a8ab]
./a.out[0x804bb52]
./a.out[0x804ba3d]
./a.out[0x804ba3d]
./a.out[0x804ba3d]
./a.out[0x804ba3d]
./a.out[0x804ba3d]
./a.out[0x804ba3d]
./a.out[0x8049e32]
./a.out[0x8048892]
/lib/tls/i686/cmov/libc.so.6(__libc_start_main+0xe5)[0xb7e32775]
./a.out[0x8048401]

and other stuff... can It be becouse it is a recursive function?

the second and biggest problem is that when the number becomes too large (something like 1000 digits) I get a segmentation fault... there are strange problems with arrays of this dimension?

the code is very big but you can find it at:
http://www.speedyshare.com/403525688.html

ps: I've deleted the free() functions... It caused too many errors...

thanks for you help, and sorry for my eng...
Jun 28 '09 #1
25 6140
donbock
2,422 Expert 2GB
Are you using malloc (or calloc) to dynamically allocate memory; and free to release dynamically allocated memory?

If so, are you trapping the exceptional case when malloc/calloc return an error because there is no available memory to allocate? If not, then you need to do so.

The "free(): invalid size: 0x0975a328" message sounds like you are trying to free a block of memory that wasn't dynamically allocated. This could happen if you free the same block twice; or if the pointer argument gets corrupted somewhere between being returned by malloc and being passed back to free.

Dynamic memory allocation works fine with recursive functions ... provided that you don't run out of memory. You want to be careful to free memory as soon as it isn't needed.

A general problem is memory fragmentation -- when the pattern of free's doesn't match the pattern of malloc's, so small freed blocks are not contiguous, leading eventually to the circumstance where malloc for a large block fails (despite there being more than enough memory) because no portion of free heap space is large enough to satisfy the request.
Jun 29 '09 #2
thanks for the reply, I don't use free and I'm not trapping that case... how to do it? something like:
a=malloc(d*sizeof(int));
if(a==NULL) {printf("error"); exit(1);}

does it works? I will try this afternoon...
Jun 29 '09 #3
it does't work.... and for the segmentation fault problem?
Jun 29 '09 #4
donbock
2,422 Expert 2GB
So ... I gather from your terse response that you added the error traps to all malloc/calloc/realloc function calls; and that none of the traps were taken; and that the program continues to fail as it did before -- with a run-time segmentation fault.

"Segmentation fault" means that you tried to access nonexistent memory. The most common ways to do this include:
  • dereferencing a NULL pointer;
  • dereferencing a pointer into dynamic memory after the memory has been freed;
  • dereferencing a corrupted pointer;
  • accessing past the end of a dynamic memory block, typically by using a too-large array index.

1. Examine the segmentation fault error message. It should report the address where the fault occurred. Compare that address to your link map to see which function contains the offending instruction. Presumably the offending instruction dereferences a pointer into one of your allocated memory blocks. Look carefully to make sure that pointer does indeed point into a valid memory block. Also look carefully to make sure you're not accessing past the end of that block (for instance, with a too-large array index).

2. I notice your backtrace was almost all raw hexadecimal addresses. Temporarily make all of your functions global (by removing "static" keyword). See if that induces the backtrace to report function names.

I will try to look at your source code, but it may be quite awhile before I have time to work through such a large source file. It would help if you provided the segmentation fault backtrace, decoding the hex addresses into function names.
Jun 29 '09 #5
sorry for newbie question... but when you say "link map" what does it means??
and I don't know what is a global function and what is not, so maybe are all global... I will post the code again with the add you said.
however, I've 2 kind of errors... this one:
free(): invalid size: 0x0975a328
caused by the exp function (espone in the code), and the second one, that say just "segmentation fault" when the number of digits is >1000...
Jun 29 '09 #6
JosAH
11,448 Expert 8TB
@stararic
The 'invalid size' error most likely originates from corrupted memory or a pointer value you're trying to free() that you haven't malloc()'d. A segmentation fault most likely originates from corrupted memory or buffer overflows.

kind regards,

Jos
Jun 29 '09 #7
donbock
2,422 Expert 2GB
Expand|Select|Wrap|Line Numbers
  1. int *VerificaDimezzamento(int array[], int n, int *d)
  2.    {
  3.    int *b, i;
  4.    if(n<=(*d)/4)
  5.       {
  6.       b=malloc(((*d)/4)*sizeof(int));
  7.       for(i=0; i<n;i++) 
  8.          b[i]=array[i];
  9.       for(;i<((*d)/4);i++)
  10.          b[i]=0;
  11.       *d=2*(*d);
  12.       return b;
  13.       }
  14.    return array;
  15.    }
I don't understand what this function is trying to do; but I notice that the size of the memory allocation is (*d)/4 times sizeof(int), but it sets *d to 2*(*d). That difference between the size of the allocation and the new value of *d contrasts with VerificaRaddoppio.


Expand|Select|Wrap|Line Numbers
  1. typedef struct el {int *array; int n; int d; struct el *succ;} elemento;
  2. ...
  3. elemento pop(pile *pila)
  4.    {
  5.    elemento a;
  6.    pile tmp;
  7.    if(pila!=NULL)
  8.       {
  9.       a=**pila;
  10.       tmp=*pila;
  11.       *pila=(*pila)->succ;
  12.       return a;
  13.       }
  14.    else 
  15.       {
  16.       printf("pila vuota!"); 
  17.       return a;
  18.       }
  19. }
Are you sure that *pila is never NULL (like if the pile is empty)? If it is ever NULL then the line 'a=**pila' will provoke a segmentation fault.

If pila is NULL then this function returns an uninitialized elemento without any warning to the caller. In that case, there will probably be a segmentation fault if the caller tries to dereference the array or succ fields of the uninitialized elemento.


I haven't gone very far into this source file yet.

In general, this code makes little attempt to verify that pointers aren't NULL before dereferencing them. It is good practice to get in the habit of always checking pointers. This may result in some unnecessary checks, but it may save you many months of unnecessary debugging over the extent of your programming career.

By the way, you would be doing yourself a favor by adding some comments to this program.

Forget about my earlier suggestion to make the functions global.
Jun 29 '09 #8
thaks, for first one "VerificaDimezzamento", I never use it, so I I have removed it. the second one "pop" is now:
elemento pop(pile *pila)
{elemento a;pile tmp;
if(*pila!=NULL){
a=**pila;
tmp=*pila;
*pila=(*pila)->succ;
return a;}
else {printf("pila vuota!"); exit(1);}
}

I'm adding some things to the code, I will post it soon. I know about the comments:D
Jun 29 '09 #9
donbock
2,422 Expert 2GB
@stararic
Please use CODE tags. The following code snippet is much easier to read:
Expand|Select|Wrap|Line Numbers
  1. elemento pop(pile *pila)
  2.    {
  3.    elemento a;
  4.    pile tmp;
  5.    if(*pila!=NULL)
  6.       {
  7.       a=**pila;
  8.       tmp=*pila;
  9.       *pila=(*pila)->succ;
  10.       return a;
  11.       }
  12.    else 
  13.       {
  14.       printf("pila vuota!"); 
  15.       exit(1);
  16.       }
  17.    }
By the way, you should still confirm that pila is not NULL before dereferencing it. Why is tmp there if you don't use it? Now that you have removed elemento 'a' from the pile, you don't want anybody to use a.succ to peek into the pile -- it is good linked-list hygiene to set a.succ to NULL before returning 'a'.

By the way, with all the 'free' calls removed this program is one huge memory leak -- especially the recursive functions. That isn't causing your current problems (as long as malloc returns successfully), but should be fixed before you consider your program done.
Jun 29 '09 #10
Expand|Select|Wrap|Line Numbers
  1. elemento pop(pile *pila)
  2. {elemento a;pile tmp;
  3.     if(*pila!=NULL){
  4.         a=**pila;
  5.         *pila=(*pila)->succ;
  6. a.succ=NULL;
  7.         return a;}
  8.         else {printf("pila vuota!"); exit(1);}
  9. }
  10.  
that's ok??
Jun 29 '09 #11
donbock
2,422 Expert 2GB
That's good, but you should check if pila is NULL before you dereference it to check if *pila is NULL.

Whenever you see a pointer being dereferenced with '*' you should ask yourself if there is any chance for that pointer to be NULL.

Whenever you see a pointer being dereferenced with '->' you should ask yourself if there is any chance for that pointer to be NULL.
Jun 29 '09 #12
uhm understood... now the code is here:
http://www.speedyshare.com/675628446.html
it still doesn't work... I'm trying to change the use of memory, but I'm not sure I'm doing good becouse there are still a lot of errors... thanks again for you help... Without you I'm in very big trouble, this is a project for an universitary exam...
Jun 29 '09 #13
donbock
2,422 Expert 2GB
@stararic
Typically, there is a compiler option that causes a "link map" to be generated. The link map is a list of all global (that is, not-static) identiifers along with the address of each. You will have to look at your compiler documentation to discover how your specific compiler supports this feature.
Jun 30 '09 #14
donbock
2,422 Expert 2GB
@stararic
Please post specific questions or complete descriptions of actual compiler or run-time faults. I'm reluctant to provide too much general assistance.
Jul 1 '09 #15
ok... now I use 2 functions for the allocation of memori:

Expand|Select|Wrap|Line Numbers
  1. void resize(int *array, int *d, int dim)
  2. {    if(dim>MAXDIM){printf("raggiunta dim max"); exit(2);}
  3.  
  4.         array=realloc(array,(dim)*sizeof(int));
  5.         if(array==NULL) {printf("errore: impossibile allocare altra memoria"); exit(2);}
  6.         if(d==NULL){printf("errore: '*' su puntatore a NULL"); exit(2);}
  7.         *d=dim;
  8.  
  9. }
  10.  
  11. elemento inizializza (int dim)
  12. {int i;elemento a;
  13.     if(dim>MAXDIM){printf("raggiunta dim max"); exit(2);}
  14.     a.array=malloc(dim*sizeof(int));
  15.     if(a.array==NULL) {printf("errore: impossibile allocare altra memoria"); exit(2);}
  16.     a.array[0]=1;
  17.     for(i=1;i<dim;i++)a.array[i]=0;
  18.     a.d=dim;
  19.     a.succ=NULL;
  20.     a.n=1;
  21.     return a;
  22. }
  23.  
And remember the type elemento:
Expand|Select|Wrap|Line Numbers
  1. typedef struct el {int *array; int n; int d; struct el *succ;} elemento;
  2.  
when I use this in the function:
Expand|Select|Wrap|Line Numbers
  1. elemento DecToBin(elemento a)
  2. {elemento decimale,tmp1,resto, binario,zero;
  3. int i,j,tmp;
  4.  
  5. zero=inizializza(2);
  6. zero.array[1]=0;
  7. zero.n++;
  8.  
  9. decimale=inizializza(a.d);
  10. decimale.n=a.n;
  11. binario=inizializza(2);
  12. resto=inizializza(2);    
  13. tmp1=decimale;
  14.  
  15. for(i=0;i<decimale.n;i++) decimale.array[i]=a.array[i];
  16. while(maggiore(decimale,zero)==0)
  17. {decimale=DivSemplice(tmp1,1,2);
  18.     binario.array[binario.n]=tmp1.array[tmp1.n-1]%2;
  19.     tmp1=decimale;        
  20.     decimale=tmp1;
  21.     binario.n++;
  22.     if(binario.n==binario.d) resize(binario.array,&(binario.d), 2*binario.n);
  23.  
  24. }
  25.  
  26. for(i=1, j=binario.n-1;i<j;i++,j--)  {tmp=binario.array[j];binario.array[j]=binario.array[i];binario.array[i]=tmp;}
  27. if(decimale.array[0]==1)binario.array[0]=1;
  28. else binario.array[0]=-1;
  29.  
I get:

*** glibc detected *** /home/richard/progettino/calc: realloc(): invalid next size: 0x088c90e0 ***
======= Backtrace: =========
/lib/tls/i686/cmov/libc.so.6[0xb7f46604]
/lib/tls/i686/cmov/libc.so.6[0xb7f4a1b1]
/lib/tls/i686/cmov/libc.so.6(realloc+0x106)[0xb7f4aee6]
/home/richard/progettino/calc[0x8048c2f]
/home/richard/progettino/calc[0x804b8b5]
/home/richard/progettino/calc[0x8048831]
/lib/tls/i686/cmov/libc.so.6(__libc_start_main+0xe5)[0xb7eed775]
/home/richard/progettino/calc[0x80484a1]
======= Memory map: ========
08048000-0804d000 r-xp 00000000 08:01 5105080 /home/richard/progettino/calc
0804d000-0804e000 r--p 00004000 08:01 5105080 /home/richard/progettino/calc
0804e000-0804f000 rw-p 00005000 08:01 5105080 /home/richard/progettino/calc
088c9000-088ea000 rw-p 088c9000 00:00 0 [heap]
b7d00000-b7d21000 rw-p b7d00000 00:00 0
b7d21000-b7e00000 ---p b7d21000 00:00 0
b7ed6000-b7ed7000 rw-p b7ed6000 00:00 0
b7ed7000-b8033000 r-xp 00000000 08:01 2786520 /lib/tls/i686/cmov/libc-2.9.so
b8033000-b8034000 ---p 0015c000 08:01 2786520 /lib/tls/i686/cmov/libc-2.9.so
b8034000-b8036000 r--p 0015c000 08:01 2786520 /lib/tls/i686/cmov/libc-2.9.so
b8036000-b8037000 rw-p 0015e000 08:01 2786520 /lib/tls/i686/cmov/libc-2.9.so
b8037000-b803a000 rw-p b8037000 00:00 0
b803c000-b8049000 r-xp 00000000 08:01 2768961 /lib/libgcc_s.so.1
b8049000-b804a000 r--p 0000c000 08:01 2768961 /lib/libgcc_s.so.1
b804a000-b804b000 rw-p 0000d000 08:01 2768961 /lib/libgcc_s.so.1
b804b000-b804f000 rw-p b804b000 00:00 0
b804f000-b8050000 r-xp b804f000 00:00 0 [vdso]
b8050000-b806c000 r-xp 00000000 08:01 2768919 /lib/ld-2.9.so
b806c000-b806d000 r--p 0001b000 08:01 2768919 /lib/ld-2.9.so
b806d000-b806e000 rw-p 0001c000 08:01 2768919 /lib/ld-2.9.so
bfd58000-bfd6d000 rw-p bffeb000 00:00 0 [stack]

Program received signal SIGABRT, Aborted.
0xb804f430 in __kernel_vsyscall ()

the program is compiled with gcc -Wall --pedantic and for the run time I used gdb... Please save me:(
Jul 1 '09 #16
donbock
2,422 Expert 2GB
Regarding your function resize, the realloc function may not be able to extend the specified memory block. In that case, it allocates a new block with the larger size, copies the contents of the original block into the new block, and frees the original block. Therefore, you need to be able to accommodate the value of the 'array' pointer changing after you call resize. That is, the pointer value returned by realloc needs to be written into the array field of the relevant elemento.

You should check if realloc is used anywhere else.
Jul 1 '09 #17
there is not other function who use realloc...
Jul 2 '09 #18
I've not undestand what is the problem...
Jul 2 '09 #19
donbock
2,422 Expert 2GB
@stararic
Have you changed how function resize is used in accordance with my advice in Message #17? Did that have any effect?
Jul 2 '09 #20
how can i do it? something like:
Expand|Select|Wrap|Line Numbers
  1. void resize(int *array, int *d, int dim)
  2. {int *tmp;int i;
  3.         if(array==NULL){printf("array null in resize"); exit(2);}
  4.         if(dim>MAXDIM){printf("raggiunta dim max"); exit(2);}
  5.         tmp=malloc((dim)*sizeof(int));
  6.         if(array==NULL) {printf("errore: impossibile allocare altra memoria"); exit(2);}
  7.         for(i=0;i<=*d;i++) tmp[i]=array[i]; for(;i<=dim;i++) tmp[i]=0;
  8.         free(array);
  9.         array=tmp;}
  10.         if(d==NULL){printf("errore: '*' su puntatore a NULL"); exit(2);}
  11.         *d=dim;
  12.  
  13. }
  14.  
doesn't work at all...
*** glibc detected *** ./calc: free(): invalid next size (fast): 0x0970c030 ***

realloc returns NULL if it cannot extend the array's block? if yes, I can do something like


Expand|Select|Wrap|Line Numbers
  1.  
  2. void resize(int *array, int *d, int dim)
  3.  {int i, *tmp;  
  4.   if(dim>MAXDIM){printf("raggiunta dim max"); exit(2);}
  5.          array=realloc(array,(dim)*sizeof(int));
  6.          if(array==NULL) {
  7.                 tmp=malloc((dim)*sizeof(int));
  8.         if(array==NULL) {printf("errore: impossibile allocare altra memoria"); exit(2);}
  9.         for(i=0;i<=*d;i++) tmp[i]=array[i]; for(;i<=dim;i++) tmp[i]=0;
  10.         free(array);
  11.         array=tmp;}
  12.        if(d==NULL){printf("errore: '*' su puntatore a NULL"); exit(2);}
  13.        *d=dim;
  14. }
  15.  
  16.  

Is this what you means in msg 17?
Jul 2 '09 #21
donbock
2,422 Expert 2GB
1. Change resize to return a pointer to the resized array.
2. Change each resize caller so that they copy that returned pointer into the relevant elemento array field. There is no necessity for the resize callers to compare the returned pointer to NULL since resize does that for you; but there is also no harm in it either.

Or change resize so that you pass it two parameters: a pointer to an elemento and the desired new size. Resize could then update the array and dim fields of the elemento itself.
Jul 2 '09 #22
But when I use resize, if a is an element I do:
resize(a.array, &(a.d), dim);
so when in resize i do array=realloc(array,dim)); it is supposed to change the value of "array" to the pointer at the new block, and "array" is the array field of elemento... So I think I've done what you suggenst when I call resize... Is it wrong?Doesn't work with a void function?
Jul 2 '09 #23
ohhhhhh my god it seems working! no resize error with the code:

Expand|Select|Wrap|Line Numbers
  1.  int *resize(int *array, int *d, int dim)
  2.   {int i, *tmp;  
  3.    if(dim>MAXDIM){printf("raggiunta dim max"); exit(2);}
  4.           array=realloc(array,(dim)*sizeof(int));
  5.           if(array==NULL) {
  6.                  tmp=malloc((dim)*sizeof(int));
  7.         if(array==NULL) {printf("errore: impossibile allocare altra memoria"); exit(2);}
  8.          for(i=0;i<=*d;i++) tmp[i]=array[i]; for(;i<=dim;i++) tmp[i]=0;
  9.          free(array);
  10.          array=tmp;}
  11.         if(d==NULL){printf("errore: '*' su puntatore a NULL"); exit(2);}
  12.         *d=dim;
  13. return array;
  14.  }
  15.  
  16.  
but really I don't understand why... Now there is just some double free error, above all after some iterations of the code. maybe there is some wrong free... I will check for it. thanks a lot
Jul 2 '09 #24
donbock
2,422 Expert 2GB
@stararic
Lines 9-10,15-21 are unnecessary. If realloc fails then it is unlikely that malloc will succeed.

If you decide to keep malloc as a backup to realloc then you need to fix some run-time faults. You only enter this block if realloc fails ... that is, if array is set to NULL. That means that lines 16 and 19 will fail. You can fix these failures by assigning the realloc return value to a new variable to avoid corrupting array.

Also, line 11 should be checking tmp, not array.

Also, line 15 dereferences pointer d before it is verified to be non-NULL.
Jul 2 '09 #25
yes... I've fixed it, and the double free error too... now I'm checking arounf for some other problem, debbuggin, trying the program and commenting it... tks again
Jul 2 '09 #26

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

7 posts views Thread by masood.iqbal | last post: by
6 posts views Thread by gp | last post: by
6 posts views Thread by Vamsee | last post: by
4 posts views Thread by Simon Schaap | last post: by
7 posts views Thread by Jake Thompson | last post: by
10 posts views Thread by javuchi | last post: by
4 posts views Thread by Silas Silva | last post: by
1 post views Thread by CARIGAR | last post: by
reply views Thread by zhoujie | last post: by
reply views Thread by harlem98 | last post: by
reply views Thread by listenups61195 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.