Why is `realloc()` failing on certain mysterious inputs?

Question

I've already spent hours trying to figure out why my program fails on this input, but it's still kind of a mystery to me. First, here's the relevant details to reproduce this error.

Using the files listed below in the same directory, compile with gcc -O0 -g main.c ArrayList.c (note: gcc --version outputs 7.3.0). Afterwards, run ./a.out $((10**9)). You should get the following error:

a.out: malloc.c:2868: mremap_chunk: Assertion `((size + offset) & (GLRO (dl_pagesize) - 1)) == 0' failed.
Aborted (core dumped)

I've already tried debugging through this and the problem doesn't seem to be my code i.e. the error seems to be thrown in realloc's code, but I honestly don't know. If I use ./a.out $((10**10)), the program doesn't fail, which is mysterious to me. The issue seems to be this line:

arraylist->data = realloc(arraylist->data, sizeof(uint64_t) * (arraylist->capacity));

I've read through the man pages for clues to whether I'm calling realloc incorrectly, but nothing jumped out to me. All the program is trying to do is sieve out the non-primes less than sqrt(n) using a modified sieve of eratosthenes. Can someone please help me out? Thanks!

---

main.c:

// main.c
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <math.h>
#include "ArrayList.h"

// Segment addressing.
#define BYTE_IDX(i) i >> 4
#define BIT_IDX(i) (i >> 1) % 8

// Bit manipulation.
#define IS_PRIME(i) ~(S[BYTE_IDX(i)] >> BIT_IDX(i)) & 1U
#define SET_BIT(i) S[BYTE_IDX(i)] |= (1U << BIT_IDX(i))

uint64_t primepi(uint64_t n)
{
    uint64_t sqrtn = (uint64_t)sqrt((double)n);
    uint8_t *S = calloc((sqrtn + 1) / 16, sizeof(uint8_t));

    ArrayList arraylist;
    arraylist_init(&arraylist);

    for (uint64_t i = 3; i * i <= n; i += 2)
        if (IS_PRIME(i))
        {
            arraylist_append(&arraylist, i);
            for (uint64_t j = i * i; j * j <= n; j += 2 * i)
                SET_BIT(j);

        }

    free(S);
    arraylist_free(&arraylist);
    return (uint64_t)0;
}

int main(int argc, char **argv)
{
    uint64_t n = primepi(atoll(argv[1]));
    printf("n = %lu\n", n);
    return 0;
}

ArrayList.h:

/**
 * ArrayList.h
 *
 * Summary:
 *  Provides a specification of the ArrayList data structure.
 */

#define ARRAYLIST_INITIAL_CAPACITY 128

typedef struct {
    uint64_t size;
    uint64_t capacity;
    uint64_t *data;
} ArrayList;

void arraylist_init(ArrayList *arraylist);

void arraylist_append(ArrayList *arraylist, uint64_t value);

uint64_t arraylist_get(ArrayList *arraylist, uint64_t index);

void arraylist_double_capacity_if_full(ArrayList *arraylist);

void arraylist_free(ArrayList *arraylist);

ArrayList.c:

/**
 * ArrayList.c
 *
 * Summary:
 *  Provides an implementation of the ArrayList data structure.
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include "ArrayList.h"

void arraylist_init(ArrayList *arraylist)
{
    // Initialize size and capacity.
    arraylist->size = (uint64_t)0;
    arraylist->capacity = ARRAYLIST_INITIAL_CAPACITY;

    // Allocate memory of the arraylist->data.
    arraylist->data = calloc(arraylist->capacity, sizeof(uint64_t));
}

void arraylist_append(ArrayList *arraylist, uint64_t value)
{
    // Double ArrayList if it is full.
    arraylist_double_capacity_if_full(arraylist);

    // Append the value and increment the size.
    arraylist->data[arraylist->size++] = value;
}

uint64_t arraylist_get(ArrayList *arraylist, uint64_t index)
{
    if (index >= arraylist->size || index < (uint64_t)0)
    {
        printf("Index %lu out of bounds for ArrayList of size %lu\n", index, arraylist->size);
        exit(1);
    }
    return arraylist->data[index];
}

void arraylist_double_capacity_if_full(ArrayList *arraylist)
{
    if (arraylist->size >= arraylist->capacity)
    {
        arraylist->capacity *= (uint64_t)2;
        arraylist->data = realloc(arraylist->data, sizeof(uint64_t) * (arraylist->capacity));
    }
}

void arraylist_free(ArrayList *arraylist)
{
    free(arraylist->data);
}

---

Edit:

Output from running valgrind --tool=memcheck ./a.out $((10**9)):

==31666== Memcheck, a memory error detector
==31666== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==31666== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==31666== Command: ./a.out 1000000000
==31666== 
==31666== Invalid read of size 1
==31666==    at 0x1089E7: primepi (main.c:29)
==31666==    by 0x108AA7: main (main.c:40)
==31666==  Address 0x55cb7f8 is 0 bytes after a block of size 1,976 alloc'd
==31666==    at 0x4C31B25: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==31666==    by 0x108952: primepi (main.c:19)
==31666==    by 0x108AA7: main (main.c:40)
==31666== 
==31666== Invalid write of size 1
==31666==    at 0x108A17: primepi (main.c:29)
==31666==    by 0x108AA7: main (main.c:40)
==31666==  Address 0x55cb7f8 is 0 bytes after a block of size 1,976 alloc'd
==31666==    at 0x4C31B25: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==31666==    by 0x108952: primepi (main.c:19)
==31666==    by 0x108AA7: main (main.c:40)
==31666== 
==31666== Invalid read of size 1
==31666==    at 0x108982: primepi (main.c:25)
==31666==    by 0x108AA7: main (main.c:40)
==31666==  Address 0x55cb7f8 is 0 bytes after a block of size 1,976 alloc'd
==31666==    at 0x4C31B25: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==31666==    by 0x108952: primepi (main.c:19)
==31666==    by 0x108AA7: main (main.c:40)
==31666== 
n = 0
==31666== 
==31666== HEAP SUMMARY:
==31666==     in use at exit: 0 bytes in 0 blocks
==31666==   total heap usage: 8 allocs, 8 frees, 70,584 bytes allocated
==31666== 
==31666== All heap blocks were freed -- no leaks are possible
==31666==
==31666== For counts of detected and suppressed errors, rerun with: -v
==31666== ERROR SUMMARY: 9 errors from 3 contexts (suppressed: 0 from 0)

Answer 1

The problem lies in you SET_BIT macro:

#define SET_BIT(i) S[BYTE_IDX(i)] |= (1U << BIT_IDX(i))

or maybe in your BYTE_IDX macro:

#define BYTE_IDX(i) i >> 4

or maybe in this loop:

for (uint64_t j = i * i; j * j <= n; j += 2 * i)
            SET_BIT(j);

it accesses out of bound the S array.

When:

• argv[1] = "1000000000"
• n = 1000000000
• sqrtn = 31622
• DYNAMIC_ARRAY_SIZE(S) = (sqrtn + 1) / 16 * sizoef(uint8_t) = 1976

the maximum index for S is 1975. Setting SET_BIT macro to:

#define SET_BIT(i)  do{ \
    size_t _a = BYTE_IDX(i); \
    if (_a > 1975)  \
        fprintf(stderr, "Setting byte %ld\n", _a); \
    S[_a] |= (1U << BIT_IDX(i)); \
}while(0)

we can see in the output:

Setting byte 1976 

You are writing out of bound for the S array which overwrites *alloc data - it throws an assertion.

Live code available at onlinedbg.

To your code:

• Using any argument outside macro is bad. If you use S inside a macro pass it as an argument, maybe with a size argument, that way you can write an assertion. You just discovered why IS_PRIME and SET_BIT macros are bad. I like your idea of indexing bitfields very very much - just write a proper library for that, just like for arraylist.
• size_t is the type for storing sizes. Use size_t for ArrayList.size and ArrayList.capacity. Use uint64_t arraylist_get(ArrayList *arraylist, size_t index);. Would be also nice, as you work with big numbers, to check for multiplication overflow, the expressions arraylist->capacity *= (uint64_t)2; and sizeof(uint64_t) * (arraylist->capacity) may overflow.