

CPU時間を計測する課題のプログラムを作成しています。  
下記のプログラム２つをコンパイルし、実行してみたところ  
普通のコンパイルだと問題なく実行されるのですが、課題で指示された最適化オプション `-O2` を付けてコンパイルして実行すると、Segmentation
fault (コアダンプ)が表示されます。どこに間違いがあるのでしょうか。よろしければ教えて下さい。

エラーメッセージは以下のように表示されます。  
コンパイラはCygwinです。

[code]

    megum@DESKTOP-E9B0HPJ ~/B8
    $ gcc -O2 iata_db.c iata_cpu3.c
    
    megum@DESKTOP-E9B0HPJ ~/B8
    $ ./a
    key = AAC
    Segmentation fault (コアダンプ)
    
[/code]

iata_data.csvの内容を貼り付けると文字数がオーバーするのでリンク先のデータをコピーしたものになります。

<http://www.photius.com/wfb2001/airport_codes_alpha.html>

[code]

    #include <stdio.h>
    #include <time.h>
    #include "iata_db.h"
    
    int main(void)
    {
      db_t db;
      char key[KEY_LEN+1];
      char *data;
        int i;
     
        
      db_init(&db);
      db_hash_load(&db);
    
      /* 空港コードを入力するとデータを出力; EOFまで繰り返し実行 */
      for (;;) {
        fprintf(stderr, "key = ");
        if (scanf(KEY_FMT, key)==EOF) { break; }
        clock_t clk_start, clk_end;
        clk_start = clock();
        for(i=0; i<=100000; i++)
        {
            data = db_hash_search(&db, key);
        }
        clk_end = clock();
        fprintf(stderr, "cpu = %11.6f [sec]\n", (double) (clk_end-clk_start)/CLOCKS_PER_SEC);
        if (data==NULL) { printf("NO RECORD\n"); }
        else { printf("%s => %s\n", key, data); }
      }
    
      return 0;
    }
    
[/code]

[code]

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <assert.h>
    #include "iata_db.h"
    /* c が改行記号かどうか判定するマクロ */
    #define IS_EOL(c) ((c)=='\n' || (c)=='\r')
    
    /* iata_db.c の内部だけで使用する関数 */
    static void extract_data(char line[], char key[], char data[]);
    static void record_set(record_t *r, char key[], char data[]);
    
    void db_init(db_t *db)
    /* db_t 型変数の初期化 */
    {
      int i;
      db->n = 0;
      for (i=0; i<MAX_RECORDS; i++) {
        strcpy(db->record[i].key, "");
        db->record[i].data = NULL;
      }
    }
    
    void db_load(db_t *db)
    /* db_t 型変数にファイル IATA_F からデータを読み込む */
    {
      FILE *fp;
      char line[KEY_LEN+1+DATA_LEN+1];
      char key[KEY_LEN+1];
      char data[DATA_LEN+1];
    
      /* ファイルのオープン */
      if ((fp=fopen(IATA_F, "r"))==NULL) {
        fprintf(stderr, "ファイル (%s) が開けません\n", IATA_F);
        exit(1);
      }
    
      /* データの読み込み */  
      while (fgets(line, DATA_LEN, fp) != NULL) {
        /* 入力データ数が収容可能最大レコード数を超えたらエラー */
        if (MAX_RECORDS<=db->n) {
          fprintf(stderr, "MAX_RECORDS(%d) <= n(%d)\n", MAX_RECORDS, db->n);
          exit(1);
        }
        /* line から key と data を切り出す */
        extract_data(line, key, data); 
        /* db->n 番目のレコードに key と data を格納し, db->n を1増やす */
        record_set(&db->record[db->n], key, data); 
        db->n++;
      }
    
      fclose(fp);
    }
    
    static void record_set(record_t *r, char key[], char data[])
    /* r の指すレコードに key と data を書き込む (data は動的割当て) */
    {
      assert(r!=NULL);
      assert(key!=NULL);
      assert(data!=NULL);
      /* key */
      assert(strlen(key)<=KEY_LEN); 
      strcpy(r->key, key);
      /* data */
      assert(strlen(data)<=DATA_LEN); 
      r->data = (char*) malloc(sizeof(char)*(strlen(data)+1));
      strcpy(r->data, data);
    }
    
    static void extract_data(char line[], char key[], char data[])
    /* line から key と data を抽出する*/
    {
      assert(line!=NULL);
      assert(key!=NULL);
      assert(data!=NULL);
      int k;
    
      /*  ファイルの1行が長過ぎて line に収容できていないことがないかのチェック */
      /*  line の末尾が改行でない → 1行が長過ぎるのでエラー */
      if (! IS_EOL( line[strlen(line)-1] ) ) {
        fprintf(stderr, "line length exceeded line size\n");
        exit(1);
      }
    
      /* 先頭の KEY_LEN 文字が key */
      int p_key = 0;
      for (k=0; k<KEY_LEN; k++) {
        key[k] = line[p_key+k]; 
      }
      key[k] = '\0';
    
      /* KEY_LEN+1 文字目以降改行記号までが data */
      int p_data = KEY_LEN+1;
      for (k=0; k<DATA_LEN; k++) {
        if (IS_EOL(line[p_data+k])) { break; }
        data[k] = line[p_data+k];
      }
      data[k] = '\0';
    }
    
    void db_dump(db_t *db)
    /* db_t 型変数の全データを出力する */
    {
        int i;
        for(i=0; i<MAX_RECORDS; i++)
        {
            printf("[  %d]", i);
            if(db->record[i].data != NULL)
            {
                printf("%s %s", db->record[i].key, db->record[i].data);
            }
            printf("\n");
        }
    }
    
    char *db_linear_search(db_t *db, char key[])
    {
        int i;
        for(i=0; i<MAX_RECORDS; i++)
        {
            if(strcmp(key,db->record[i].key)==0)
            {
                return db->record[i].data;
                break;
            }
        }
        return NULL;
    }
    
    char *db_binary_search(db_t *db, char key[KEY_LEN+1])
    {
        int low=0;
        int high=db->n-1;
        int mid;
        for(;;)
        {
            mid=(high+low)/2;
            if(strcmp(key,db->record[mid].key)==0)
            {
                return db->record[mid].data;
            }
            else if(strcmp(key,db->record[mid].key)> 0)
            {
                low = mid + 1;
            }
            else if(strcmp(key,db->record[mid].key)< 0)
            {
                high = mid - 1;
            }
            if(high < low){break;}
        }
        return NULL;
    }
    
    int db_hash_f(char key[])
    {
      int i;
      int v = 0;
      for (i=0; key[i]!='\0'; i++) {
        v = (v<<5) + (key[i]-'A');
      }
      return v % MAX_RECORDS;
    }
    
    void db_hash_load(db_t *db)
    {
      FILE *fp;
      char line[KEY_LEN+1+DATA_LEN+1];
      char key[KEY_LEN+1];
      char data[DATA_LEN+1];
        int h;
        int m = MAX_RECORDS;
    
      /* ファイルのオープン */
      if ((fp=fopen(IATA_F, "r"))==NULL) {
        fprintf(stderr, "ファイル (%s) が開けません\n", IATA_F);
        exit(1);
      }
    
      /* データの読み込み */  
      while (fgets(line, DATA_LEN, fp) != NULL) {
        /* 入力データ数が収容可能最大レコード数を超えたらエラー */
        if (MAX_RECORDS<=db->n) {
          fprintf(stderr, "MAX_RECORDS(%d) <= n(%d)\n", MAX_RECORDS, db->n);
          exit(1);
        }
        /* line から key と data を切り出す */
        extract_data(line, key, data); 
        /* db->n 番目のレコードに key と data を格納し, db->n を1増やす */
        h = db_hash_f(key);
        while(strcmp(db->record[h].key, "")!= 0)
        {
            h++;
            if(h == m){h = h - m;}
        }
        record_set(&db->record[h], key, data); 
    
      }
    
      fclose(fp);
    }
    
    char *db_hash_search(db_t *db, char key[KEY_LEN+1])
    {
        int h;
        int i;
        int m = MAX_RECORDS;
        for(i=0; i<= MAX_RECORDS; i++)
        {
            if(strcmp(db->record[h].key, key)==0)
            {
                return db->record[h].data;
                break;
            }
            h++;
            if(h == m){h = h - m;}
        }
        return NULL;
    }
    
[/code]

[code]

    /*
      次の行の __USE_MINI__ が定義されていると iata_mini.csv が, 
      次の行がコメントアウトされていると iata_data.csv が使われる
    */
    /*#define __USE_MINI__*/
    
    #ifdef __USE_MINI__
    /* テスト版の定義 */
    #define IATA_F "iata_mini.csv"  /* 空港データのファイル */
    #define MAX_RECORDS 16 /* レコード数の上限 */
    #else
    /* フルセット版の定義 */
    #define IATA_F "iata_data.csv"  /* 空港データのファイル */
    #define MAX_RECORDS 6000  /* レコード数の上限 */
    #endif
    
    
    #define KEY_LEN 3  /* 空港コード (キー) の文字数 */
    #define KEY_FMT "%3s"  /* 空港コード (キー) の入力用フォーマット */
    #define DATA_LEN 127  /* 空港データの最大文字数 */
    
    
    /* 1 レコードのデータ */
    typedef struct {
      char key[KEY_LEN+1];  /* 空港コード (キー) */
      char* data;  /* 空港の詳細データ (文字配列) へのポインタ */
    } record_t;
    
    
    /* データベース (全データ) */
    typedef struct {
      int n;  /* データ (レコード) 数 */
      record_t record[MAX_RECORDS];  /* データ (レコード) の配列 */
    } db_t;
    
    
    void db_init(db_t *db); /* 初期化 */
    void db_load(db_t *db); /* ファイルからデータを読み込む */
    void db_dump(db_t *db); /* ダンプ (全データ出力) */
    
    char *db_linear_search(db_t *db, char key[]); /* 線形探索 */
    char *db_binary_search(db_t *db, char key[]); /* 二分探索 */
    
    int db_hash_f(char key[]); /* ハッシュ関数 */
    void db_hash_load(db_t *db); /* データを読み込む (ハッシュ用) */
    char *db_hash_search(db_t *db, char key[]); /* ハッシュによる探索 */
    
[/code]


CC BY-SA 4.0
2021-11-21T03:22:44.440
83735
2023-11-08T02:02:55.343
2022-07-27T04:54:00.977
3060
49169
question
c windows
Segmentation fault (コアダンプ)の原因が分かりません。


`db_hash_search()` 関数の実行速度を計測してるようですが  
この中の auto変数 `h` が初期化されてない模様  
(通常は stackエリアから割り当てられるので, 内容は不定 ~~, もしくは stackエリアの内容秘匿するための何か, が割り当てられるはず~~ )

この処理は, もしかすると, 前回呼び出した検索の続きから 処理行おうとしてる？かもなので  
たぶん, static にする必要があるかも (staticならば, 未初期化は 0)

[code]

    char *db_hash_search(db_t *db, char key[KEY_LEN+1])
    {
        static int h; // <== 変更
        int i;
    
[/code]

* * *

編集: (位置のランダム化, により内容変化するかもだが, auto変数関係なさそうなので削除)


CC BY-SA 4.0
2021-11-22T06:15:50.360
83760
2021-11-23T00:50:42.973
2021-11-23T00:50:42.973
43025
43025
83735
answer


おそらくコアダンプはたまたま発生した現象だと思われます。  
以下に示すように潜在的なバグがあって、それが動作時の条件により現れたものでしょう。

Cygwin(gcc)ではなくVC++でデフォルトのチェックを外してコンパイル出来るようにしてデバッグ実行したところでは、コメントで指摘した`iata_db.c`の`db_hash_search(...)`の`if
(strcmp(db->record[h].key, key) ==
0)`の行でアクセス違反の例外となり、その時の`h`の内容は`変数は最適化されたため、使用できません。`という表示になりました。

変数`h`を何か固定の値で初期化しておく(@oririさん回答のようにstatic変数にしても良いのかも？)といった対策でも動作はしますが、そう言えば関数名`db_hash_search(...)`のハッシュに相当する処理が無いように見受けられました。

そうやって`iata_db.c`を見ると一つ上の`db_hash_load(...)`に似たような形の処理があり、そこでは変数`h`を`db_hash_f(key);`で設定してから類似のループと文字列比較の処理が行われています。

ということで、現在`int
h;`と定義だけして未初期化の変数を以下のように`db_hash_f(key)`で初期化するのが、関数の名前的にも正しいやり方だと思われます。

[code]

    char *db_hash_search(db_t *db, char key[KEY_LEN+1])
    {
        int h = db_hash_f(key); // <== 変更
        int i;
    以下省略
    
[/code]


CC BY-SA 4.0
2021-11-24T03:58:32.533
83783
2021-11-24T03:58:32.533
26370
83735
answer