GNU MP: Cannot reallocate memory - Why?

[hunson]

Hey everyone,


I am again playing with the GMP library and experiencing some problems with code.


The program I am trying to write generates prime number candidates and eliminates composite numbers by simple trail division.
The main for-loop generates the candidate with GMP and checks for a prime factor with previously generated primes (sieve of the erastothenes).

[...]    mpz_t tmp_a;
    mpz_t tmp_b;
    mpz_t n;
    mpz_t m;
    mpz_t base;
    mpz_t mod_result;

    //////////init
    mpz_init(tmp_a);
    mpz_init(tmp_b);
    mpz_init(n);
    mpz_init(m);
    mpz_init(mod_result);
    mpz_set_str(m,middle,10);
    mpz_init_set_ui(base,10);

[...] sieve of the erastothenes

for(p=1;p<num_primes;p++) //start at 1, skipping primes_lst[0] = 2, no even numbers were generated
    {
        for (e = n_min;e < n_max;e+=2)
        {
            printf("%d\n",e);
            if (candidates[index] == 1)
            {
                f = (int)((e-len_m)/2);
                //10^e-xxx*10^f-1
                mpz_pow_ui(tmp_a,base,e);
                mpz_pow_ui(tmp_b,base,f);
                mpz_mul(tmp_b,m,tmp_b);
                mpz_sub(n,tmp_a,tmp_b);
                //mpz_add(n,tmp_a,tmp_b);
                //mpz_add_ui(n,n,1);
                mpz_sub_ui(n,n,1);
                //mpz_mod_ui(mod_result,n,primes_lst[p]);
                if (mpz_mod_ui(mod_result,n,primes_lst[p]) == 0)
                {
                    count_eliminated++;
                    candidates[index] = 0;
                }
            }
            if (e % 1111 == 0)
            {
                printf("\r%d candidates eliminated, p = %d \n", count_eliminated, primes_lst[p]);
                fflush(stdout);
            }
            index++;
        }
        index=0;
    }
[...]

The code worked fine at some point, but know I get a "GNU MP: Cannot reallocate memory (old_size=80 new_size=84)" error after a couple of loop-iterations. What am I doing wrong here? I initialized the mpz variables and cleared them at the end. The amount of memory GMP tries to allocate does not seem to much...

My programming skills are mediocre and I am new to programming in c. Any hint in the right direction is appreciated.


regards



hunson

[paulunderwood]

How is index controlled?

It might be easier to debug if you attached the whole program.

[hunson]

Here is the whole code.

#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
#include <math.h>
#include <string.h>
#include <time.h>

int main()
{
    mpz_t tmp_a;
    mpz_t tmp_b;
    mpz_t n;
    mpz_t m;
    mpz_t base;
    mpz_t mod_result;
    unsigned int e,f;
    clock_t start;
    char middle[] = "77777";
    unsigned int n_min = 10;
    unsigned int n_max = 10000;

    if (n_min % 2 == 0)
    {
        n_min +=1;
        printf("n_min was even, starting at n_min+1\n");
    }

    char *candidates;
    candidates = malloc(sizeof(char) * floor((n_max-n_min)/2));
    int len_m = sizeof(middle)-1;
    char ABC_header[32];

    #define sieve_depth 1000
    #define num_primes 168 //we know how many primes there are below sieve_depth
    //  n         PI(n)
    //  100       25
    //  150       35
    //  500       95
    //  1000      168
    //  10000     1229
    //  50000     5133
    //  100000    9592
    //  750000    60238
    //  1000000   78498
    //  10000000  664579

    char *primes;
    primes = malloc(sizeof(char) * sieve_depth);
    unsigned long x,i,y,z,p;
    unsigned int primes_lst[num_primes];
    unsigned int count_primes = 0;
    unsigned int count_eliminated = 0;
    unsigned int index = 0;
    unsigned int array_size = lroundf((n_max-n_min)/2);
    unsigned int cnt_candidate = 0;
    unsigned int cnt_primes = 0;
    FILE *fp;
    //////////init
    mpz_init(tmp_a);
    mpz_init(tmp_b);
    mpz_init(n);
    mpz_init(m);
    mpz_init(mod_result);
    mpz_set_str(m,middle,10);
    mpz_init_set_ui(base,10);
    //////////////
    fp = fopen("candidates.txt", "w");
    if(fp == NULL)
    {
        printf("file can't be opened\n");
        exit(1);
    }
    //write ABC header
    strcat(ABC_header, "ABC 10^$a-");
    strcat(ABC_header, middle);
    strcat(ABC_header,"*10^$b-1\n");
    fprintf(fp, ABC_header);
    start = clock();

     //////////////////////////////
    //sieve of erastothenes
    //fill array with 1, all numbers are prime
    for (i=0;i<=sieve_depth;i++)
    {
        primes[i] = 1;
    }
    //sieve, from 2 to sqrt(max)
    for (x = 2;x*x < sieve_depth;x++)
    {
        if (primes[x] == 1)
        {
          for (y = 2*x;y<=sieve_depth;y += x) //remove multiples of x, x-wide-steps
          {
            primes[y] = 0;
          }
        }
    }

    for (z = 2;z<sieve_depth;z++)
    {
      if (primes[z] == 1)
      {
        primes_lst[cnt_primes] = z;
        cnt_primes++;
      }
    }
    //////////////////////////////



    //fill candidates array with ones
    for (e = 0;e <= array_size;e++)
    {
        candidates[e] = 1;
    }

    //trail division "sieve"
    printf("%d\n",primes_lst[10]);
    //exit(0);
    for(p=1;p<num_primes;p++) //start at 1, skipping primes_lst[0] = 2, no even numbers were generated
    {
        for (e = n_min;e < n_max;e+=2)
        {
            printf("%d\n",e);
            if (candidates[index] == 1)
            {
                f = (int)((e-len_m)/2);
                //10^e-xxx*10^f-1
                mpz_pow_ui(tmp_a,base,e);
                mpz_pow_ui(tmp_b,base,f);
                mpz_mul(tmp_b,m,tmp_b);
                mpz_sub(n,tmp_a,tmp_b);
                //mpz_add(n,tmp_a,tmp_b);
                //mpz_add_ui(n,n,1);
                mpz_sub_ui(n,n,1);
                //mpz_mod_ui(mod_result,n,primes_lst[p]);
                if (mpz_mod_ui(mod_result,n,primes_lst[p]) == 0)
              //  if (mpz_fdiv_ui(n,primes_lst[p]) == 0)
                {
                    count_eliminated++;
                    candidates[index] = 0;
                }
            }
            if (e % 1111 == 0)
            {
                printf("\r%d candidates eliminated, p = %d \n", count_eliminated, primes_lst[p]);
                fflush(stdout);
            }
            index++;
        }
        index=0;
    }

    //write candidates to file
    for (i=0;i<=array_size;i++)
    {
        e = n_min+(i*2);
        f = (int)((e-len_m)/2);
        if (candidates[i] == 1)
        {
            fprintf(fp, "%d %d\n", e,f);
        }
    }
    printf("%d candidates left\n", (n_max-n_min)/2-count_eliminated);
    printf("\n%f\n", (float)(clock()-start)/CLOCKS_PER_SEC);
    //cleanup
    free(primes_lst);
    free(candidates);
    mpz_clear(tmp_a);
    mpz_clear(tmp_b);
    mpz_clear(n);
    mpz_clear(m);
    mpz_clear(base);
    mpz_clear(mod_result);
    fclose(fp);
    return 0;
}

[paulunderwood]

gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/11/lto-wrapper
OFFLOAD_TARGET_NAMES=nvptx-none:amdgcn-amdhsa
OFFLOAD_TARGET_DEFAULT=1
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Debian 11.2.0-13' --with-bugurl=file:///usr/share/doc/gcc-11/README.Bugs --enable-languages=c,ada,c++,go,brig,d,fortran,objc,obj-c++,m2 --prefix=/usr --with-gcc-major-version-only --program-suffix=-11 --program-prefix=x86_64-linux-gnu- --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --libdir=/usr/lib --enable-nls --enable-bootstrap --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --with-default-libstdcxx-abi=new --enable-gnu-unique-object --disable-vtable-verify --enable-plugin --enable-default-pie --with-system-zlib --enable-libphobos-checking=release --with-target-system-zlib=auto --enable-objc-gc=auto --enable-multiarch --disable-werror --enable-cet --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --enable-multilib --with-tune=generic --enable-offload-targets=nvptx-none=/build/gcc-11-KdLYb3/gcc-11-11.2.0/debian/tmp-nvptx/usr,amdgcn-amdhsa=/build/gcc-11-KdLYb3/gcc-11-11.2.0/debian/tmp-gcn/usr --without-cuda-driver --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu --with-build-config=bootstrap-lto-lean --enable-link-serialization=2
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 11.2.0 (Debian 11.2.0-13)

gcc -o hunson hunson.c -lgmp
hunson.c: In function ‘main’:
hunson.c:167:5: warning: ‘free’ called on unallocated object ‘primes_lst’ [-Wfree-nonheap-object]
  167 |     free(primes_lst);
      |     ^~~~~~~~~~~~~~~~
hunson.c:50:18: note: declared here
   50 |     unsigned int primes_lst[num_primes];
      |                  ^~~~~~~~~~

Commenting out line 167 makes the program run.

[paulunderwood]

I get "corrupted size vs. prev_size" which means you have a memory leak somewhere caused by out-of-bounds access.

[paulunderwood]

I changed to primes = malloc(sizeof(int) * sieve_depth); and now get no errors

[henryzz]

Originally Posted by paulunderwood

I changed to primes = malloc(sizeof(int) * sieve_depth); and now get no errors

Seems odd to me that you needed to do that. Is this just masking another issue by making the memory allocation bigger?

edit: Could assigning ints to elements of a char array be causing issues? I believe it will cast it normally but I am not certain it would for an array.

[paulunderwood]

Originally Posted by henryzz

Seems odd to me that you needed to do that. Is this just masking another issue by making the memory allocation bigger?

edit: Could assigning ints to elements of a char array be causing issues? I believe it will cast it normally but I am not certain it would for an array.

primes[] is assigned 0 and 1 which are 4 bytes -- char is 1 byte.

To save save memory space the coder could use char and assign and test '0' and '1'. Or use a smaller integer type.

[henryzz]

Originally Posted by paulunderwood

primes[] is assigned 0 and 1 which are 4 bytes -- char is 1 byte.

To save save memory space the coder could use char and assign and test '0' and '1'. Or use a smaller integer type.

My concern is that one assignment is overwriting four array elements. Could assign (char) 0 or (char) 1 or '\0' or '\1' to assign one element without complicating things by using the ASCII values of 0 and 1.

[bsquared]

The compiler should know to cast 0 and 1 hardcoded constants into the appropriate size (char). The problem is that the primes array is being overrun by this line:

for (i=0;i<=sieve_depth;i++)

It was only initialized with sieve_depth elements and that loop goes over sieve_depth+1 values.

Later it also tries to read past the end of the allocated primes array.

The 'candidates' array has a similar problem, but changing '<=' to '<' in loops using sieve_depth fixed it for me.

[paulunderwood]

Originally Posted by bsquared

The compiler should know to cast 0 and 1 hardcoded constants into the appropriate size (char). The problem is that the primes array is being overrun by this line:

for (i=0;i<=sieve_depth;i++)

It was only initialized with sieve_depth elements and that loop goes over sieve_depth+1 values.

Later it also tries to read past the end of the allocated primes array.

The 'candidates' array has a similar problem, but changing '<=' to '<' in loops using sieve_depth fixed it for me.

Nice one. I had narrowed it down to a problem with SOE.