Dinamic Array Allocation problems

[stararic]

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...

[donbock]

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.

[stararic]

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...

[stararic]

it does't work.... and for the segmentation fault problem?

[donbock]

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.

[stararic]

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...

[JosAH]

@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

[donbock]

int *VerificaDimezzamento(int array[], int n, int *d)
   {
   int *b, i;
   if(n<=(*d)/4)
      {
      b=malloc(((*d)/4)*sizeof(int));
      for(i=0; i<n;i++) 
         b[i]=array[i];
      for(;i<((*d)/4);i++)
         b[i]=0;
      *d=2*(*d);
      return b;
      }
   return array;
   }

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.

typedef struct el {int *array; int n; int d; struct el *succ;} elemento;
...
elemento pop(pile *pila)
   {
   elemento a;
   pile tmp;
   if(pila!=NULL)
      {
      a=**pila;
      tmp=*pila;
      *pila=(*pila)->succ;
      return a;
      }
   else 
      {
      printf("pila vuota!"); 
      return a;
      }
}

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.

[stararic]

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

[donbock]

@stararic
Please use CODE tags. The following code snippet is much easier to read:

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

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.

[stararic]

elemento pop(pile *pila)
{elemento a;pile tmp;
    if(*pila!=NULL){
        a=**pila;
        *pila=(*pila)->succ;
a.succ=NULL;
        return a;}
        else {printf("pila vuota!"); exit(1);}
}
 

that's ok??

[donbock]

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.

[stararic]

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...

[donbock]

@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.

[donbock]

@stararic
Please post specific questions or complete descriptions of actual compiler or run-time faults. I'm reluctant to provide too much general assistance.

[stararic]

ok... now I use 2 functions for the allocation of memori:

void resize(int *array, int *d, int dim)
{    if(dim>MAXDIM){printf("raggiunta dim max"); exit(2);}
 
        array=realloc(array,(dim)*sizeof(int));
        if(array==NULL) {printf("errore: impossibile allocare altra memoria"); exit(2);}
        if(d==NULL){printf("errore: '*' su puntatore a NULL"); exit(2);}
        *d=dim;
 
}
 
elemento inizializza (int dim)
{int i;elemento a;
    if(dim>MAXDIM){printf("raggiunta dim max"); exit(2);}
    a.array=malloc(dim*sizeof(int));
    if(a.array==NULL) {printf("errore: impossibile allocare altra memoria"); exit(2);}
    a.array[0]=1;
    for(i=1;i<dim;i++)a.array[i]=0;
    a.d=dim;
    a.succ=NULL;
    a.n=1;
    return a;
}
 

And remember the type elemento:

typedef struct el {int *array; int n; int d; struct el *succ;} elemento;
 

when I use this in the function:

elemento DecToBin(elemento a)
{elemento decimale,tmp1,resto, binario,zero;
int i,j,tmp;
 
zero=inizializza(2);
zero.array[1]=0;
zero.n++;
 
decimale=inizializza(a.d);
decimale.n=a.n;
binario=inizializza(2);
resto=inizializza(2);    
tmp1=decimale;
 
for(i=0;i<decimale.n;i++) decimale.array[i]=a.array[i];
while(maggiore(decimale,zero)==0)
{decimale=DivSemplice(tmp1,1,2);
    binario.array[binario.n]=tmp1.array[tmp1.n-1]%2;
    tmp1=decimale;        
    decimale=tmp1;
    binario.n++;
    if(binario.n==binario.d) resize(binario.array,&(binario.d), 2*binario.n);
 
}
 
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;}
if(decimale.array[0]==1)binario.array[0]=1;
else binario.array[0]=-1;
 

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:(

[donbock]

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.

[stararic]

there is not other function who use realloc...

[stararic]

I've not undestand what is the problem...

[donbock]

@stararic
Have you changed how function resize is used in accordance with my advice in Message #17? Did that have any effect?

[stararic]

how can i do it? something like:

void resize(int *array, int *d, int dim)
{int *tmp;int i;
        if(array==NULL){printf("array null in resize"); exit(2);}
        if(dim>MAXDIM){printf("raggiunta dim max"); exit(2);}
        tmp=malloc((dim)*sizeof(int));
        if(array==NULL) {printf("errore: impossibile allocare altra memoria"); exit(2);}
        for(i=0;i<=*d;i++) tmp[i]=array[i]; for(;i<=dim;i++) tmp[i]=0;
        free(array);
        array=tmp;}
        if(d==NULL){printf("errore: '*' su puntatore a NULL"); exit(2);}
        *d=dim;
 
}
 

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

 
void resize(int *array, int *d, int dim)
 {int i, *tmp;  
  if(dim>MAXDIM){printf("raggiunta dim max"); exit(2);}
         array=realloc(array,(dim)*sizeof(int));
         if(array==NULL) {
                tmp=malloc((dim)*sizeof(int));
        if(array==NULL) {printf("errore: impossibile allocare altra memoria"); exit(2);}
        for(i=0;i<=*d;i++) tmp[i]=array[i]; for(;i<=dim;i++) tmp[i]=0;
        free(array);
        array=tmp;}
       if(d==NULL){printf("errore: '*' su puntatore a NULL"); exit(2);}
       *d=dim;
}
 
 

Is this what you means in msg 17?

[donbock]

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.

[stararic]

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?

[stararic]

ohhhhhh my god it seems working! no resize error with the code:

 int *resize(int *array, int *d, int dim)
  {int i, *tmp;  
   if(dim>MAXDIM){printf("raggiunta dim max"); exit(2);}
          array=realloc(array,(dim)*sizeof(int));
          if(array==NULL) {
                 tmp=malloc((dim)*sizeof(int));
        if(array==NULL) {printf("errore: impossibile allocare altra memoria"); exit(2);}
         for(i=0;i<=*d;i++) tmp[i]=array[i]; for(;i<=dim;i++) tmp[i]=0;
         free(array);
         array=tmp;}
        if(d==NULL){printf("errore: '*' su puntatore a NULL"); exit(2);}
        *d=dim;
return array;
 }
 
 

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

[donbock]

@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.

[stararic]

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