c - 为什么第 33791 个素数 (399137) 会导致 Segmentation Fault？

Question

很明显，数字 399137 本身并不会导致段错误，但我的程序在同一计算中始终崩溃。它计算从 2 到给定限制(默认 1,000,000)的欧拉总和 (phi function) 的值。它通过保持一个线性排序的素数列表来实现这一点，这些素数来自先前计算的欧拉 totient 值。尝试将第 33791 个素数 (339137) 添加到素数列表时会导致段错误。请注意，此计算不会重新分配内存。我尝试使用 gdb 来定位问题，它指向将素数添加到列表中的那一行(见下文)。

为了存储所有低于 100 万的素数，我的程序将动态分配 8192*10*4 字节 (320KB)。需要那么多连续的内存对我来说似乎没有问题。

那么，为什么我的程序在尝试将 339137 添加到素数列表时总是出现段错误？这个段错误的原因是什么？

C代码:

#include <math.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

uint32_t phi       (uint32_t n, uint32_t *primes, uint32_t *count, uint32_t *size);
uint32_t gcd_bin   (uint32_t u, uint32_t v);
uint32_t isPrime   (uint32_t n, uint32_t *primes, uint32_t *count, uint32_t *size);
void     addPrime  (uint32_t n, uint32_t *primes, uint32_t *count, uint32_t *size);
uint32_t isInArr   (uint32_t n, uint32_t *primes, uint32_t count);
uint32_t expand_arr(uint32_t **arr, uint32_t *size);
void     print_arr (uint32_t  *arr, uint32_t count);
uint32_t print_help(char* str);

int main(int argc, char* argv[]) {
  uint32_t z=1000000;         //default
  uint32_t count=0,size = 10; //default
  uint32_t i,n;
//  uint32_t x,y; //max numerator & denominator of ratio
  uint32_t *primes = malloc(size * sizeof(uint32_t));

  if(argc > 1 && !strcmp(argv[1],"--help")) { return print_help(argv[0]); }
  if(argc > 1) {  sscanf(argv[1],"%u",&z); }

  uint32_t old=size;
  for(i=2,/*x=y=1,*/count=0; i<=z; ++i) {
    n = phi(i,primes,&count,&size);
    fprintf(stderr,"\ni=%u phi(i)=%u\t: c=%u s=%u ",i,n,count,size);
  }
//  printf("%u/%u\n",x,y);
  return 0;
}

uint32_t phi(uint32_t n, uint32_t *primes, uint32_t *count, uint32_t *size) {
  uint32_t i,bound;
  // Base case
  if(n < 2)
    return 0;
  // Is Prime? (Lehmer's conjecture)
  if(isPrime(n,primes,count,size))
    return n-1;
  // Even number?
  if((n & 1) == 0 ) {
    int m = n >> 1;
    return ~m & 1 ? phi(m,primes,count,size)<<1 : phi(m,primes,count,size);
  }
  // Find (smallest) prime factor using list of primes
  for(i=0,bound=(uint32_t)sqrt(n); primes[i] < bound && i<*count && (n%primes[i])!=0; ++i);
  uint32_t m = primes[i];
  uint32_t o = n/m;
  uint32_t d = gcd_bin(m, o);
  return d==1 ? phi(m,primes,count,size)*phi(o,primes,count,size)
              : phi(m,primes,count,size)*phi(o,primes,count,size)*(d/phi(d,primes,count,size));
}

uint32_t isPrime(uint32_t n, uint32_t *primes, uint32_t *count, uint32_t *size) {
  uint32_t i,prime,bound;
  for(i=0,prime=1,bound=(uint32_t)sqrt(n)+1; prime && i<*count && primes[i]<=bound; ++i)
    prime = n%primes[i];
  if(prime)
    addPrime(n,primes,count,size);
  return prime;
}

void addPrime(uint32_t n, uint32_t *primes, uint32_t *count, uint32_t *size) {
  if(*count >= *size) {
    if(!expand_arr(&primes,size)) {
      fprintf(stderr,"dying gracefully!");
      exit(1); //realloc failure
    }
  }
  if(!isInArr(n,primes,*count))
    primes[(*count)++] = n; /* ERROR IS HERE APPARENTLY */
}

uint32_t expand_arr(uint32_t **primes, uint32_t *size) {
  *size  *= 2;
  *primes = realloc(*primes, *size * sizeof(uint32_t));
  return *primes!=NULL;
}

uint32_t isInArr(uint32_t n, uint32_t *primes, uint32_t count) {
  uint32_t hi,low,mid,val;
  low = 0; hi = count; // set bounds
  while(low < hi) {    // binary search
    mid = low/2 + hi/2;
    val = primes[mid];
    if(val == n) return  1;
    if(val >  n) hi  = mid;
    if(val <  n) low = mid+1;
  }
  return 0;
}

void print_arr(uint32_t *arr, uint32_t count) {
  uint32_t i;
  for(i=0; i<count; ++i)
    printf("%u,",arr[i]);
  printf("\n");
}

uint32_t gcd_bin(uint32_t u, uint32_t v) {
    /* simple cases (termination) */
    if(u == v)  return u;
    if(u == 0)  return v;
    if(v == 0)  return u;
    /* look for even numbers  */
    if( ~u & 1) {
      if(v & 1) return gcd_bin(u >> 1, v);           /* u is even, v is odd  */
      else      return gcd_bin(u >> 1, v >> 1) << 1; /* u is even, v is even */
    }
    if( ~v & 1) return gcd_bin(u, v >> 1);           /* u is odd,  v is even */
    /* reduce larger argument */                     /* u is odd,  v is odd  */
    return (u > v) ? gcd_bin((u - v) >> 1, v)
                   : gcd_bin((v - u) >> 1, u);
}

uint32_t print_help(char* str) {
  printf("  Usage: %s <limit> \n",str);
  printf("  Calculates the values of euler's totient (phi fnction) \n");
  printf("  from 2 to <limit> inclusively\n");
  printf("  * limit : a decimal number\n");
  printf("          : default = 1000000\n");
  return 0;
}

Answer 1

首先，查找此类错误的最佳工具是 valgrind .忽略所有选项，将其作为 valgrind ./a.out 运行，然后首先修复它报告的问题。重复直到程序正确运行。

现在，在这种情况下，通过代码检查，问题对我来说很明显，因为我知道要寻找什么。通过在 valgrind 的帮助下调试大量此类问题，我学会了要查找的内容。 Valgrind 是你的 friend 。使用它。

uint32_t expand_arr(uint32_t **arr, uint32_t *size);

这个函数扩展了arr参数指向的指针指向的数组，用新指针覆盖旧指针。

void addPrime(uint32_t n, uint32_t *primes, uint32_t *count, uint32_t *size) {
  if(*count >= *size) {
    if(!expand_arr(&primes,size)) {

此函数在 primes 指针上调用 expand_arr，这是一个函数参数，因此是调用者已知的指针的副本 .当 expand_arr 更改 primes 时，仅会影响 addPrime 中的副本，不会来电者的副本；调用者的指针指向释放的内存。

事实上，primes 一直作为函数参数线程化，一直通过 isPrime 和 phi 返回到 main。所有这些函数都需要将 primes 作为指向指针的指针传递，就像 expand_arr 已经做的那样，这样当 expand_arr 调用 realloc。

这是 valgrind 告诉您问题所在的方式:

i=29 phi(i)=28  : c=10 s=10 ==17052== Invalid read of size 4
==17052==    at 0x4009D5: isPrime (test.c:59)
==17052==    by 0x400BC4: phi (test.c:41)
==17052==    by 0x400DCB: main (test.c:28)
==17052==  Address 0x54de040 is 0 bytes inside a block of size 40 free'd
==17052==    at 0x4C2C03E: realloc (vg_replace_malloc.c:662)
==17052==    by 0x4008C9: expand_arr (test.c:79)
==17052==    by 0x400968: addPrime (test.c:68)
==17052==    by 0x400A07: isPrime (test.c:62)
==17052==    by 0x400BC4: phi (test.c:41)
==17052==    by 0x400C50: phi (test.c:53)
==17052==    by 0x400DCB: main (test.c:28)

注意它是如何将你指向 isPrime 作为“无效读取”的位置，并且它直接告诉你你拥有的是一个指向已释放内存的陈旧指针(“内部有 0 个字节”一个大小为 40 的 block free'd") -- 并且它在主循环的第 29 次迭代中发现了问题。