C言語 mallocを使えない環境でキャッシュを作る

Question

c言語でmallocが使えない環境(fpgaへの実装を想定、固定長配列で実装)で簡単なキャッシュを作ろうとしています。

//main.c
#include <stdlib.h>
#include <stdio.h>

#define TIMEOUT_SECOND 2

#define MAXOBJ 16
#define BUF_SIZE 10
#define BUF_LENGTH 100
#define INVALID_LENGTH 7

int cache(char recvBuffer[BUF_LENGTH]);

int intTries = 0;
int main(int argc, char *argv[]) {
    
    char recvBuffer1[MAX_BUFSIZE] = "bbtest";
    
    for (int i = 0; i < 10; ++i) {
        int result1 = cache(recvBuffer1);
        //int result2 = cache(recvBuffer2);

        printf("result1 is : %d\n", result1);
       
    }
    return 0;
}

//cache.c
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <assert.h>

#define MSG_FAILURE -1
#define MAX_MSGSIZE 100
#define MAX_BUFSIZE (MAX_MSGSIZE + 1)
#define MAX_TRIES 5
#define TIMEOUT_SECOND 2
#define ARRAY_SIZE 100

#define MAXOBJ 16
#define BUF_SIZE 10
#define BUF_LENGTH 100
#define INVALID_LENGTH 7


int cache(char *recvBuffer){

    //cache definition--------------------------------------------------
    static char *cache[BUF_SIZE];
    char invalid[8] = "invalid";

    static char buffer1[BUF_LENGTH] = "invalid";
    cache[0] = &buffer1[0];
    static char buffer2[BUF_LENGTH] = "invalid";
    cache[1] = &buffer2[0];
    static char buffer3[BUF_LENGTH] = "invalid";
    cache[2] = &buffer3[0];
    static char buffer4[BUF_LENGTH] = "invalid";
    cache[3] = &buffer4[0];
    static char buffer5[BUF_LENGTH] = "invalid";
    cache[4] = &buffer5[0];
    static char buffer6[BUF_LENGTH] = "invalid";
    cache[5] = &buffer6[0];
    static char buffer7[BUF_LENGTH] = "invalid";
    cache[6] = &buffer7[0];
    static char buffer8[BUF_LENGTH] = "invalid";
    cache[7] = &buffer8[0];
    static char buffer9[BUF_LENGTH] = "invalid";
    cache[8] = &buffer9[0];
    static char buffer10[BUF_LENGTH] = "invalid";
    cache[9] = &buffer10[0];
    
    //print cache-----------------------------------------------------
    
    for (int b = 0; b < BUF_SIZE; b++) {
        printf("Cache[%d]: ", b);
        for (int j = 0; j <INVALID_LENGTH ; ++j) {
            printf("%c", *(cache[b] + j));
        }
        printf("\n");
    }
    printf("\n-------------------------------\n");
    
    //ここでPutかGetかを判別する。
    if ( *(uint16_t *)recvBuffer == 0x6262){//Put  0x6262==bb
        
        //空いている場所を探す
        printf("Putが実行\n");
        printf("recvBuffer is: %s\n", recvBuffer);
        int flag = 1;
        for (int d = 0; d < BUF_SIZE; d++) {
            //cache[d]がinvalidか照合
            for (int j = 0; j < INVALID_LENGTH; j++) {
                if (*(cache[d] + j) != invalid[j]){
                    flag = 0;//cache[d]は空いている
                    printf("Cache[%d]の%cは%cと一致していない\n", d, *(cache[d]+j), invalid[j]);
                }
            }
            //cache[d]がinvalidのとき→現状、1つでも一致すればよくなってしまっている
            if (flag == 1) {
                printf("Cache[%d]はinvalid!!\n", d);
                cache[d] = recvBuffer; //[0]にはflagが入っているため
                //無事キャッシュに格納完了
                break;
            }
        }
        //キャッシュが満杯の時、古いのを捨てる
        if (flag == 0) {
            printf("cache full----------------------------------\n");
            cache[8] = recvBuffer; //適当に８番目を入れ替える
        }
        //
        //キャッシュの中身を表示
        printf("\n-------------------------------\n");
        printf("new Cache is : \n");
        for (int c = 0; c < BUF_SIZE; c++) {
            printf("Cache[%d]: ", c);
            for (int j = 0; j < INVALID_LENGTH; ++j) {
                printf("%c", *(cache[c] + j));
            }
            printf("\n");
        }
        return 0;//Putなので返すものはない
        //-------------------------------------
    } else if(*(uint16_t *)recvBuffer == 0x6161){   //Getのとき  0x6161==aa
        printf("Getが実行\n");
        for (int i = 0; i < BUF_SIZE; i++) {
            if (recvBuffer[i+1] == *cache[i]) {
                printf("Cache Hit!");
                return 1; //Cache hitのときは1を返すようにする
                break;
                //sendBuffer_fromserver[0] = '1';
            }
        }
        //for文が最後まで実装されたらキャッシュミス
        printf("Cache Miss!\n");
        return 2; //cache miss のときは2を返すようにする
    }
}

上のプログラムを取り敢えず作成したのですが、main中で「cache」を呼び出すとそのたびに

char *cache[BUF_SIZE];

をしてしまうのでやはり毎回初期化されてしまっています。
main中でcache[BUF_SIZE]をしたいのですが、いろいろ試行錯誤してもうまくいきませんでした。。

どなたか解決策を思いつく方ご教授頂けると幸いです。

---

現在の進捗

char *cache[BUF_SIZE];

を

static char *cache[BUF_SIZE];

に修正。

for (int a = 0; a < BUF_SIZE; a++) {
char buffer[BUF_LENGTH] = "invalid";
cache[a] = &buffer[0];
}

を

static char *cache[BUF_SIZE];
    char invalid[8] = "invalid";

    static char buffer1[BUF_LENGTH] = "invalid";
    cache[0] = &buffer1[0];
    static char buffer2[BUF_LENGTH] = "invalid";
    cache[1] = &buffer2[0];
    static char buffer3[BUF_LENGTH] = "invalid";
    cache[2] = &buffer3[0];
    static char buffer4[BUF_LENGTH] = "invalid";
    cache[3] = &buffer4[0];
    static char buffer5[BUF_LENGTH] = "invalid";
    cache[4] = &buffer5[0];
    static char buffer6[BUF_LENGTH] = "invalid";
    cache[5] = &buffer6[0];
    static char buffer7[BUF_LENGTH] = "invalid";
    cache[6] = &buffer7[0];
    static char buffer8[BUF_LENGTH] = "invalid";
    cache[7] = &buffer8[0];
    static char buffer9[BUF_LENGTH] = "invalid";
    cache[8] = &buffer9[0];
    static char buffer10[BUF_LENGTH] = "invalid";
    cache[9] = &buffer10[0];

に書き下し。

Comments

[jimbe]

どういう動きをさせようとしているのか, コーディングが合っているのか間違っているのかが不明な個所が多く, 読み取れません. どのような仕様でしょうか.
パラメータのポインタを直値と比較していますが, FPGA に入れないと単体テストも出来ないということでしょうか.

[yu_2_8_2]

ご回答ありがとうございます。情報不足の質問となってしまっており申し訳ありません。
FPGAに入れないと単体テストが出来ないわけではなく、現段階ではキャッシュ部分のみの実装をしております。
仕様といたしましては、[BUF_SIZE]個を保持するキャッシュで、それぞれサイズ[BUF_LENGTH]の文字列を格納するものを作りたいです。
現在、main中ではキャッシュに文字列を挿入する際しか実装していませんが、
キャッシュに文字列を挿入する際には0を返し、
ある文字列と同じ文字列がキャッシュ中に存在していれば1を返す、
なければ0を返すようにしています。
キャッシュへの挿入/キャッシュ中に存在するかの確認は文字列の最初の2文字(aaかbbか)で判別するようにしています。
お手数おかけしますがどうぞよろしくお願いいたします。

[jimbe]

> 文字列の最初の2文字(aaかbbか)で判別
失礼しました, ポインタと直値の比較に見えたのは文字列だったのですね. 勘違いでした.

ところで, ヒットしたかを返すのはともかく, 挿入か確認かでデータを変えるという仕様はあるのでしょうか.
キャッシュというと, 有るかを確認し, 有ればそれを返し, 無ければ挿入した上でそれを返す…というイメージなのですが.

Answer 1

Compile and Execute C Online (GNU GCC v7.1.1) でテストしました.
若干(?)仕様を変えています.

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

#define BUF_SIZE 3 //テストのために少なく
#define BUF_LENGTH 100

static char *cacheLine[BUF_SIZE];
static char cacheBuffer[BUF_SIZE][BUF_LENGTH];

void initCache() {
    for(int i=0; i<BUF_SIZE; i++) {
        cacheLine[i] = cacheBuffer[i];
        *cacheLine[i] = '\0';
    }
}

int cache(const char *data) {
    int result = 2; //無かった->上書き追加
    int i;
    for(i=0; i<BUF_SIZE; i++) {
        if(*cacheLine[i] == '\0') {
            result = 1; //無かった->新規追加
            break;
        } else if(strcmp(cacheLine[i], data) == 0) {
            result = 0; //有った
            break;
        }
    }
    if(result == 2) i = BUF_SIZE-1;
    if(result != 0) strcpy(cacheLine[i], data);
    if(i > 0) {
        char *p = cacheLine[i];
        for(; i>0; i--) cacheLine[i] = cacheLine[i-1];
        cacheLine[0] = p;
    }
    return result;
}

//キャッシュの中身を表示
void printCache() {
    printf("- cache -------------\n");
    for(int i=0; i<BUF_SIZE; i++) {
        printf("%d: ", i);
        printf(*cacheLine[i]=='\0'?"(invalid)":"'%s'", cacheLine[i]);
        printf("\n");
    }
    printf("---------------------\n");
}

int main() {
    char *testdatas[] = { "test","data","abc","0123456789","qwerty" };
    initCache();
    srand((unsigned int)time(NULL));
    for(int i=0; i<10; i++) {
        char *data = testdatas[rand()%5];
        int result = cache(data);
        printf("str='%s' result=%d\n", data, result);
    }
    printCache();
    return 0;
}

str='test' result=1
str='qwerty' result=1
str='qwerty' result=0
str='abc' result=1
str='abc' result=0
str='0123456789' result=2
str='abc' result=0
str='test' result=2
str='abc' result=0
str='abc' result=0
- cache -------------
0: 'abc'
1: 'test'
2: '0123456789'
---------------------

Answer 2

char *cache[BUF_SIZE];

ローカル変数で、ポインタの配列を宣言してますが、これでいいのですか？

for (int a = 0; a < BUF_SIZE; a++) {

    char buffer[BUF_LENGTH] = "invalid";
    cache[a] = &buffer[0];
}

このbufferという配列はこのfor文を抜けると無効になりますが、これでいいのですか？
また、&buffer[0];のアドレス値はいくらループさせようと同一値ですが、これでいいのですか？

他にもいろいろありますが。。

Comments

[yu_2_8_2]

ご回答ありがとうございます。ご指摘の通り、
char *cache[BUF_SIZE];　を　static char *cache[BUF_SIZE];　に、
上記for文を取り払ってみたのですが未だ上手くいきません。
できましたらその他の問題点も教えていただけますか？

[yumetodo]

>ローカル変数で、ポインタの配列を宣言してますが、これでいいのですか？

がスルーされているのはこれで意図した挙動ということですかね？本当に？

[y_waiwai]

最後のソースコードですが、それのすべての配列はローカル変数ですが、
ローカル変数というのは、その関数が終了すると開放、消滅してしまいます。
その配列をその関数の中だけで使うならそんでいいですけど、あなたのやりたいことはそれでいいんでしょうか

Answer 3

main中で「cache」を呼び出すとそのたびに
char *cache[BUF_SIZE];
をしてしまうのでやはり毎回初期化されてしまっています

「そのたびに char *cache[BUF_SIZE]; をしてしまう」はC言語プログラマが語る日本語として意味不明・いかがなものか？と思いますが、私は質問者の気持ちをこう想像します。

cache() 関数が持つデータを、一回目の呼出しの時だけ初期化したい。
二回目の呼出し以降では、初期化せず、前回の値を引き続き使いたい。
それができないなら、せめて main() から一回だけ初期化処理を呼び出すようにしたい。

cache() 関数が持つべきデータとは、次の2種類のようです。

• char buffer1[]〜buffer10[]、10個の文字型（char型？）配列
• char *cache[BUF_SIZE]、即ち要素数10個のポインタ配列

cache() 関数の中に、初期化済みか否かを示す static なフラグ変数を設けるのが定石じゃないでしょうか。そうすれば main() から初期化関数を呼ぶ必要はなくなります。質問者は一回だけ初期化したいものが何か分かってるでしょうから、細かくは書きませんが、

int cache(char *recvBuffer)
{
    static int needInitialize = 1; // 要初期化フラグ

    if (needInitialize == 1) {     // 未初期化？なら
        needInitialize = 0;        // 初期化済みにする

        // 以下に、一回だけ初期化したいことを列挙する
        cache[0] = &buffer1[0];    // 一回だけ初期化したいのは、これ？
    }
    // 以下は、呼びだされた時の通常処理

初期化について。
cache[0] = &buffer1[0]; ですが、&buffer1[0] は配列の先頭アドレスですから配列名だけで cache[0] = buffer1;　と書けます。
さらに、buffer1[] 〜 buffer10[] は **static な配列ですから、これらの先頭アドレス10個はリンク時に確定する「定数」**です。よって、次のように書いて最初から初期化できます。

    static char buffer1[BUF_LENGTH] = "invalid";
    // （途中省略）
    static char buffer10[BUF_LENGTH] = "invalid";
    static char *cache[BUF_SIZE] = {
        // 最初から初期化してしまえ
        buffer1, buffer2, buffer3, buffer4, buffer5, 
        buffer6, buffer7, buffer8, buffer9, buffer10,
    };

これで、上に書いた要初期化フラグを使うことなく、実行開始時に初期化が済んでしまうので、これだけで解決する可能性もあります。
少なくともPutとGetの対応が取れていない。初期化だけの問題じゃないね。先は長そうだｗ

---

ボンクラでも大体わかりましたw。以下、感想です。答えなくても良いから考えてみて。

• コンパイルエラーが出ない程度には書ける。この段階では悪くない。
• でもやろうとしていることがヘン。データ構造、cache() 関数が何を返すか等、再考したほうが良い。
• キャッシュ中に見つかったエントリを、今後どう使いたいのか。
• エントリが空いてる・使っているの区別の付け方、エントリの探し方がいまいち重たい・分かりにくい・（バグってる？）感じ。
• cache()に渡す文字列の先頭2文字でput・getを指定するって、どうなの？その2文字も一緒にキャッシュするの？今のコードだとputした文字列を絶対探せない感じになってる。
• 素直なやり方は、もうひとつ引数を設けてput・getの操作を指定するか、put関数・get関数に分けるか、だと思う。関数を分ければ初期化関数は簡単に書ける。
• malloc() が使えたとしたら、どうしたかったのだろうか。
• キャッシュするデータが文字列なら <string.h> 系の strcmp(), strcpy() などを使うとか。
• 文字列なら "%c" 表示を繰り返すのでなく、"%s" で一気に表示しちゃえばすっきりするのに。

Comments

[rubato6809]

Ｃの書き方が不慣れな上に、ロジックがアヤシイ感じｗ

Answer 4

詳しく見てないですがstatic変数ではだめなのですか？

Comments

[yu_2_8_2]

char *cache[BUF_SIZE];
を
static char *cache[BUF_SIZE];
にしてもうまくいきませんでした。。