realloc(): invalid next size for an int array-CodePudding

I'm trying to find the number of primes under an integer given as argument.

The way it works is there is a loop that goes over the odd numbers starting from the last prime 2 to the number of primes under the sqrt of the argument.

As you can see, this is recursive, where is the base case is when argument is less than 6, it returns 1. There is a global list of primes starting with {3}, that gets allocated more memory when a new prime is found.

Anyway here's the code. I put some printfs for debugging.

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int number_of_primes = 1;
int s(int number);
int *primes;
int main(int argc, char *argv[])
{
    primes = (int *)malloc(sizeof(int));
    primes[0] = 3;
    printf("\nNumber of primes under %i is %i\n", atoi(argv[1]), s(atoi(argv[1]))   1);
    free(primes);
}

int s(int number)
{
    printf("the number is %i\n", number);
    if (number < 5)
    {
        return 1;
    }
    int limit = s((int)sqrt(number))   1;
    printf("limit is %i\n", limit);
    // For every odd number after the last prime to number
    for (int odd = primes[limit - 2]; odd < number   1; odd = odd   2)
    {
        printf("primes are: ");
        for (int i = 0; i < number_of_primes; i  )
        {
            printf("%i, ", primes[i]);
        }
        printf("\n");
        printf("\ncurrent odd is %i, number is %i, limit is %i\n", odd, number, limit);
        // If it is not a multiple of any of any primes
        for (int prime_index = 0; prime_index < limit; prime_index  )
        {
            printf("prime_index is %i, and primes[prime_index] is %i\n", prime_index, primes[prime_index]);
            if (primes[prime_index])
            {
                if (odd % primes[prime_index] == 0)
                {
                    break;
                }
            }
            if (prime_index == limit - 1)
            {
                printf("new_prime_is %i, number_of_primes is %i, and primes[number_of_primes - 1] is %i\n", odd, number_of_primes, primes[number_of_primes - 1]);
                primes = realloc(primes, sizeof(int));
                primes[number_of_primes] = odd;
                number_of_primes  ;
            }
        }
    }
    return number_of_primes;
}

For some reason, this works until the argument is 29. Then I get

the number is 29
the number is 5
the number is 2
limit is 2
primes are: 3, 

current odd is 3, number is 5, limit is 2
prime_index is 0, and primes[prime_index] is 3
primes are: 3, 

current odd is 5, number is 5, limit is 2
prime_index is 0, and primes[prime_index] is 3
prime_index is 1, and primes[prime_index] is 0
new_prime_is 5, number_of_primes is 1, and primes[number_of_primes - 1] is 3
limit is 3
primes are: 3, 5, 

current odd is 5, number is 29, limit is 3
prime_index is 0, and primes[prime_index] is 3
prime_index is 1, and primes[prime_index] is 5
primes are: 3, 5, 

current odd is 7, number is 29, limit is 3
prime_index is 0, and primes[prime_index] is 3
prime_index is 1, and primes[prime_index] is 5
prime_index is 2, and primes[prime_index] is 0
new_prime_is 7, number_of_primes is 2, and primes[number_of_primes - 1] is 5
primes are: 3, 5, 7, 

current odd is 9, number is 29, limit is 3
prime_index is 0, and primes[prime_index] is 3
primes are: 3, 5, 7, 

current odd is 11, number is 29, limit is 3
prime_index is 0, and primes[prime_index] is 3
prime_index is 1, and primes[prime_index] is 5
prime_index is 2, and primes[prime_index] is 7
new_prime_is 11, number_of_primes is 3, and primes[number_of_primes - 1] is 7
primes are: 3, 5, 7, 11, 

current odd is 13, number is 29, limit is 3
prime_index is 0, and primes[prime_index] is 3
prime_index is 1, and primes[prime_index] is 5
prime_index is 2, and primes[prime_index] is 7
new_prime_is 13, number_of_primes is 4, and primes[number_of_primes - 1] is 11
primes are: 3, 5, 7, 11, 13, 

current odd is 15, number is 29, limit is 3
prime_index is 0, and primes[prime_index] is 3
primes are: 3, 5, 7, 11, 13, 

current odd is 17, number is 29, limit is 3
prime_index is 0, and primes[prime_index] is 3
prime_index is 1, and primes[prime_index] is 5
prime_index is 2, and primes[prime_index] is 7
new_prime_is 17, number_of_primes is 5, and primes[number_of_primes - 1] is 13
primes are: 3, 5, 7, 11, 13, 17, 

current odd is 19, number is 29, limit is 3
prime_index is 0, and primes[prime_index] is 3
prime_index is 1, and primes[prime_index] is 5
prime_index is 2, and primes[prime_index] is 7
new_prime_is 19, number_of_primes is 6, and primes[number_of_primes - 1] is 17
primes are: 3, 5, 7, 11, 13, 17, 19, 

current odd is 21, number is 29, limit is 3
prime_index is 0, and primes[prime_index] is 3
primes are: 3, 5, 7, 11, 13, 17, 19, 

current odd is 23, number is 29, limit is 3
prime_index is 0, and primes[prime_index] is 3
prime_index is 1, and primes[prime_index] is 5
prime_index is 2, and primes[prime_index] is 7
new_prime_is 23, number_of_primes is 7, and primes[number_of_primes - 1] is 19
primes are: 3, 5, 7, 11, 13, 17, 19, 23, 

current odd is 25, number is 29, limit is 3
prime_index is 0, and primes[prime_index] is 3
prime_index is 1, and primes[prime_index] is 5
primes are: 3, 5, 7, 11, 13, 17, 19, 23, 

current odd is 27, number is 29, limit is 3
prime_index is 0, and primes[prime_index] is 3
primes are: 3, 5, 7, 11, 13, 17, 19, 23, 

current odd is 29, number is 29, limit is 3
prime_index is 0, and primes[prime_index] is 3
prime_index is 1, and primes[prime_index] is 5
prime_index is 2, and primes[prime_index] is 7
new_prime_is 29, number_of_primes is 8, and primes[number_of_primes - 1] is 23
realloc(): invalid next size
Aborted (core dumped)

When I run valgrind I get a bunch of invalid reads.

CodePudding user response：

Your memory management is wrong.

Both:

primes = (int *)malloc(sizeof(int));
/* and */
primes = realloc(primes, sizeof(int));

Allocates memory only for one integer. You access the allocated object outside the allocated memory and it a UB (undefined behavior) which manifests itself by the error shown

To allocate (or allocate memory for size integers you need to:

primes = malloc(size * sizeof(*primes));
/* and */
int *tmp = realloc(primes, size * sizeof(*primes));
if(tmp) primes = tmp;
else {/* memory allocation error handling*/ }

Use objects not types in sizeofs