时间戳

首页 > 解决方案 > 为什么 `realloc()` 在某些神秘的输入上会失败？

c - 为什么 `realloc()` 在某些神秘的输入上会失败？

问题描述

我已经花了几个小时试图弄清楚为什么我的程序在这个输入上失败了，但这对我来说仍然是个谜。首先，这是重现此错误的相关详细信息。

使用同一目录中列出的文件，使用gcc -O0 -g main.c ArrayList.c（注意：gcc --version输出7.3.0）进行编译。之后，运行./a.out $((10**9))。您应该收到以下错误：

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

我已经尝试过调试，但问题似乎不是我的代码，即错误似乎是在realloc's 的代码中抛出的，但老实说我不知道​​。如果我使用./a.out $((10**10))，程序不会失败，这对我来说很神秘。问题似乎是这一行：

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

我已经通读了手册页以获取有关我是否错误地调用 realloc 的线索，但没有任何东西跳出来给我。该程序试图做的就是使用改进的埃拉托色筛筛法筛出小于 sqrt(n) 的非素数。有人可以帮我吗？谢谢！

主.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;
}

数组列表.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);

数组列表.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);
}

编辑：

运行输出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)

标签： cmemoryrealloc

解决方案

问题在于您的 SET_BIT 宏：

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

或者也许在您的 BYTE_IDX 宏中：

#define BYTE_IDX(i) i >> 4

或者也许在这个循环中：

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

它越界访问S数组。

什么时候：

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

S 的最大索引为 1975。将 SET_BIT 宏设置为：

#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)

我们可以在输出中看到：

Setting byte 1976

您正在为覆盖 *alloc 数据的 S 数组写入越界 - 它会引发一个断言。

可在onlinedbg获得实时代码。

到您的代码：

  • 在宏之外使用任何参数都是不好的。如果您S在宏内部使用，则将其作为参数传递，可能带有大小参数，这样您就可以编写断言。IS_PRIME您刚刚发现了为什么SET_BIT宏不好。我非常喜欢你索引位域的想法——只需为此编写一个适当的库，就像 arraylist 一样。
  • size_t是存储大小的类型。使用 size_tArrayList.size和ArrayList.capacity。使用uint64_t arraylist_get(ArrayList *arraylist, size_t index);. arraylist->capacity *= (uint64_t)2;当您使用大数字时，检查乘法溢出、表达式和sizeof(uint64_t) * (arraylist->capacity)可能溢出也会很好。

推荐阅读