Почему 33791-е число (399137) вызывает ошибку сегментации?

Таким образом, очевидно, что число 399137 само по себе не вызывает ошибки сегментации, но моя программа постоянно падает при одном и том же вычислении. Он вычисляет значения коэффициента Эйлера (фи-функции) от 2 до заданного предела (по умолчанию 1 000 000). Он делает это, сохраняя линейно упорядоченный список простых чисел из ранее вычисленных значений Эйлера. При попытке добавить 33791-е простое число (339137) в список простых чисел возникает ошибка сегментации. Обратите внимание, что при этом вычислении память не перераспределяется. Я попытался использовать gdb, чтобы найти проблему, и он указал на строку, где простое число добавляется в список (см. ниже).

Чтобы сохранить все простые числа меньше 1 миллиона, моя программа динамически выделяла 8192*10*4 байт (320KB). Требование такого большого количества непрерывной памяти не кажется мне проблематичным.

Так почему же моя программа постоянно имеет ошибку сегментации при попытке добавить 339137 в список простых чисел? В чем причина этой ошибки сегментации?

C Code:

#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;
}

person recursion.ninja    schedule 11.06.2013    source источник
comment
попытался начать позже в основной последовательности, например. начиная с 2 вместо 1, и посмотрите, не вызовет ли 33792-е простое число segfault? Если это так, то у вас где-то есть ошибка переполнения памяти.   -  person Marc B    schedule 11.06.2013
comment
Что произойдет, если вы перекодируете это, чтобы предварительно выделить основной буфер один раз до размера, превышающего размер, при котором происходит сбой. Это может помочь изолировать область от этой части кода и упростить управление. Я лично не являюсь поклонником схем realloc и предпочел бы, чтобы один буфер был достаточно большим, чтобы вместить все ваши простые числа, но я также понимаю, что бывают случаи, когда это необходимо.   -  person Michael Dorgan    schedule 11.06.2013
comment
Я бы предложил использовать valgrind для запуска вашего приложения. Он показывает 605 ошибок в 59 контекстах. Думаю, тебе есть что пожевать.   -  person Bryan Olivier    schedule 11.06.2013
comment
@MarcB Я отредактировал тест на простоту, включив в начало следующее: if(~n & 1) return 0;, чтобы пропустить 2 как простое число. Программа вылетает, когда счетчик достигает 337991; пытаясь вычислить 33792-е простое число (399149).   -  person recursion.ninja    schedule 11.06.2013
comment
Это намеренно написано, чтобы быть слишком сложным? Мне это кажется довольно сложным...   -  person Mats Petersson    schedule 11.06.2013
comment
@BryanOlivier Я запустил valgrind и заметил много invalid read, есть предложения, в чем может быть проблема?   -  person recursion.ninja    schedule 11.06.2013
comment
@MarcB и MichaelDorgan Жаль, что первые два комментария были догадками. Есть инструменты (спасибо, @BryanOlivier), которые устраняют догадки при отладке... @awashburn: assert кажется одним из инструментов, который может быть вам полезен...   -  person autistic    schedule 11.06.2013
comment
@awashburn Valgrind расскажет вам, где проблемы... Какое руководство вы читаете?   -  person autistic    schedule 11.06.2013
comment
@awashburn Как правило, вы всегда хотите исправить самую первую проблему, о которой вам сообщает valgrind. Все последующие ошибки, по крайней мере потенциально, являются тем, что мы называем вторичным повреждением -- могло бы не произойти, если бы не произошла первоначальная ошибка.   -  person zwol    schedule 11.06.2013
comment
@awashburn На первый взгляд кажется, что вы обращаетесь к уже освобожденной памяти.   -  person Bryan Olivier    schedule 11.06.2013


Ответы (1)


Во-первых, лучший инструмент для поиска ошибок такого типа — valgrind. Игнорируйте все параметры и просто запустите его как valgrind ./a.out, а затем устраните самую первую проблему, о которой он сообщает. Повторяйте, пока программа не заработает правильно.

Теперь, в этом случае, проблема очевидна для меня из проверки кода, потому что я знаю, что искать. Я узнал, на что обращать внимание, отлажив бесчисленное количество этих проблем с помощью valgrind. Валгринд — твой друг. Используй это.

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

Эта функция вызывает expand_arr для указателя primes, который является параметром функции и, следовательно, является копией указателя, известного вызывающей стороне. Когда 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 освобождено") -- и что проблема обнаружена на 29-й итерации основного цикла.

person zwol    schedule 11.06.2013
comment
Итерация 29 --> 29 — 10-е простое число --> память была только что расширена! Имеет смысл! Большое спасибо за ваш опытный взгляд на проблему. Я попробую использовать указатели на массив во всех функциях программы и посмотрю, исправит ли это ошибки времени выполнения. - person recursion.ninja; 11.06.2013
comment
Верно. Одна из вещей, которую valgrind делает для вас, — убедиться, что realloc всегда делает недействительным старый указатель, а не просто иногда. Вы, вероятно, получали сбои на простом 33791, потому что ваша библиотека C избегала перемещения блока памяти до тех пор, пока это не было абсолютно необходимо, что произошло при выделении примерно 132 КБ (33791 * 4 = 132 * 1024 - 4). - person zwol; 11.06.2013
comment
Указатели на массив для всех вызовов функций были решением. Я изменил сигнатуры функций, чтобы они содержали двойные указатели разыменования (uint32_t **primes), и я изменил код доступа к массиву, чтобы специально разыменовать массив перед модификацией ((*primes)[ (*count)++ ] = n). Это было решением! Никаких ошибок сегментации, и анализ valgrind чистый! - person recursion.ninja; 11.06.2013