Блог

Я пишу программу для моделирования политик кэша. В настоящее время я пытаюсь создать политику slru. Случайные данные и т. Д. На мой взгляд, мой код работает: p . Когда я запускаю его, иногда это работает, но иногда и нет. Я использовал gdb, но не смог найти свою ошибку.

 //------ Include Files-----
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

//---- Define Values----
#define SIZE 50             // Size of elements to create
#define theta 5            // Theta for zipfian distribution
#define min 1              // Min item size in units
#define max 1000000        // Max item size in units
#define Cachepercent 0.01   // Cache percent of total size
#define asking_number 500   // Numbers to ask the cache
#define file_sketch 100    // Number for sketch the numbers near min file size


//= Function prototypes
void IDs(int array[2][SIZE]);                                                                           //Set random IDs
void zipfian(int array[2][SIZE]);                                                           // Zipfian distributed file sizes
void asking_numbers(int IDs[]);                                                             // Main array as files in memory and IDs are the ids he is going top ask for.
int cacheSize(int array[2][SIZE]);                                                          // Find cache size
int FindelEmentsInCache(int *cache, int CSize);                                               // Count how many elements are in cache
int *FindinCache(int *cache, int element, int CSize);                                       // Find Element in cache NULL if not exists
int cacheleft(int *cache, int CSize);                                                       // Compute how much size we have left
void write_dt(int DT[2][SIZE],int element,int ITcounter);                                   // Write Dt when its not in dt
void find_and_write_dt(int DT[2][SIZE],int element,int ITcounter);                          // Write dt when it already exists
void multiply(int array[2][SIZE], int DT[2][SIZE], int multiplied[2][SIZE], int ITcounter); // Function to do multiplies between Size and Dt
void kick(int array[2][SIZE], int DT[2][SIZE], int multiplied[2][SIZE], int element_to_write, int R, int *cache, int CSize, int el);
void write_in_cache(int el_to_swap, int *cache, int CSize);


//=========================
//=                       =
//=       Driver          =
//=                       =
//=========================
int main(int argc, char *argv[]){
int counter;
int array[2][SIZE];         // main array with stored data
int asking_IDs[asking_number]; //array of items to ask
int CSize;  //cache size
int *cache; //pointer to cache
int toobig=0, miss=0, hit=0; //too big to get into cache
int asked_id; //id randomly asked
int ITcounter; //Counter to see when we access something
int el; //count of elements in cache
int *found; //pos of element
int R; //Size of cache left
int *PosToWrite; //Where to write
int Dt[2][SIZE]; //Dt values array
int multiplied[2][SIZE];
int *pos;

srand(time(NULL));

//Set array to 0
for(counter=0; counter<SIZE; counter  ){
    Dt[0][counter]=0;
    Dt[1][counter]=0;
    multiplied[0][counter]=0;
    multiplied[1][counter]=0;
}


IDs(array);                   //Random IDs
zipfian(array);

asking_numbers(asking_IDs);

    
CSize=cacheSize(array); //Cache size
CSize=(int)CSize*Cachepercent;


cache = (int *)malloc((CSize)*sizeof(int)); //Allocating memory
if(cache==NULL){ //Check for error
    printf("Error allocating memory!nExiting...n");
    exit(-1);
}
pos=cache;
while(pos<cache CSize){
        *pos=0;
        pos  ;
    }

for(ITcounter=0; ITcounter<asking_number; ITcounter  ){
    
    asked_id = asking_IDs[ITcounter];
    el=FindelEmentsInCache(cache, CSize); //find how many elements are in cache
    
    if(array[1][asked_id-1]>=CSize 1){
        printf("Not worth to get it into the cache with id: %dn", array[0][asked_id-1]);
        multiply(array, Dt, multiplied, ITcounter);
        toobig  ;
        continue;
    }
    
    //search if exists in cache
    found=FindinCache(cache, asked_id, CSize);
    if(found==NULL){
       R = cacheleft(cache, CSize);
       if(R >= array[1][asked_id-1]   1){
          PosToWrite=cache; //start from the beggining of the cache  
          // fint pointer of last element and write the asked element in cache
            while(*PosToWrite!=0){
                PosToWrite  ;
            }
            *PosToWrite=array[1][asked_id-1]; //Write size here
            for(counter=0; counter<array[1][asked_id-1]; counter  ){
                PosToWrite = PosToWrite   1;
                *PosToWrite = asked_id; //write value
            }
       }
       
       else{
            kick(array, Dt, multiplied, array[1][asked_id-1], R, cache, CSize, el);
            PosToWrite=cache;
            while(*PosToWrite!=0){
                PosToWrite  ;
            }
            *PosToWrite=array[1][asked_id-1];
            PosToWrite  ;
            for(counter=0; counter<array[1][asked_id-1]; counter  ){
                *PosToWrite = asked_id; //write value
                PosToWrite = PosToWrite   1;
            }
            printf("Wrote in cache %d times %dn", asked_id, counter);
            for(counter=0; counter< CSize; counter  ){
                printf("%d ", *(cache counter));
            }
            printf("n");
        }
        write_dt(Dt, asked_id, ITcounter);
        miss  ;
    }
    else if(found != NULL){
        find_and_write_dt(Dt, asked_id, ITcounter);
        hit  ;
    }
//printf("IT counter: %dn", ITcounter);
multiply(array, Dt, multiplied, ITcounter);

}

for(counter=0; counter< CSize; counter  ){
    printf("%d ", *(cache counter));
}
printf("n");

free(cache);// Free memory allocated


for(counter=0; counter<el; counter  ){
    printf("DT array: %d with IT: %dn", Dt[0][counter], Dt[1][counter]);
}
for(counter=0; counter<el; counter  ){
    printf("Multiplied array: %d with s*dt: %dn", multiplied[0][counter], multiplied[1][counter]);
}

printf("We had %d hits!nWe had %d misses!nAnd total elemnts that we did not get into the cache were %dn", hit, miss, toobig);

return(0);
}









//----Functions----

//Create IDs in range of SIZE(working)
void IDs(int array[2][SIZE]){
int counter; //Counter for loop

for(counter=1; counter<SIZE 1; counter  ){
    array[0][counter-1]=counter;
}
}

//Random zipfian for file size(working)
void zipfian(int array[2][SIZE]){

int counter;
double probs[SIZE];
double sum=0;
double temp, power;

// Create probs
for(counter=0; counter<SIZE; counter  ){
    temp=(double) 1/(double)array[0][counter];
    power=pow(temp, theta);
    probs[counter]=power;
    sum=sum probs[counter];
}

for(counter=0; counter<SIZE; counter  ){
    probs[counter]=probs[counter]/sum;
}

//Size equal to a plus prob*b
for(counter=0; counter<SIZE; counter  ){
    array[1][counter]=(int)(min   ((max/file_sketch)*probs[counter])*rand()/RAND_MAX);
}

}

//Function asks for random ids(working)
void asking_numbers(int IDs[]){
int counter;  // Counter for loop to create random IDs in range of SIZE
int rid;      // Random ID to ask the cache

for(counter=0; counter<asking_number; counter  ){
    rid = (int)(rand()/(float)RAND_MAX * (float)SIZE);
    if(rid==0){
        if(counter>=0){
            counter--;
        }
    }
    else{
        IDs[counter]=rid;
    }
}

}

//Find cache size to allocate(Working properly)
int cacheSize(int array[2][SIZE]){
int counter;//counter
int size=0;//Size

for(counter=0; counter<SIZE; counter  ){
    size = size   array[1][counter];
}

return(size);

}

//Return number of elements in cache direct(working)
int FindelEmentsInCache(int *cache, int CSize){

int count=0; //number of elements in cache
int *loop;

loop=cache;

//pointer aritmetic to go throu the whole cache
while(loop <= cache CSize ){
    if(*loop==0){
        return(count);
    }
    count  ;
    loop=loop   1   *loop;
}

return(count);
}  


//return position in cache(Working)
int *FindinCache(int *cache, int element, int CSize){
int size; //element size
int *pos; //position

pos=cache;



while(pos<cache CSize){
    size=*pos;
    pos  ;
    
    if(*pos==element){
        return(pos);
    }
    else{
        pos=pos size;
    }
}

return(NULL);
}

//Free storage left(Working)
int cacheleft(int *cache, int CSize){
int size=0;
int *pos;

pos=cache;

while(pos<cache CSize){
    if(*pos==0){break;}
    size = 1   size   *pos;
    pos = pos   *pos   1;
   
    
}
return(CSize-size);
}

//Writing dt's
void write_dt(int DT[2][SIZE],int element,int ITcounter){
int counter;

for(counter=0; counter<SIZE; counter  ){
    if(DT[0][counter]==0){
        DT[0][counter]=element;
        DT[1][counter]=ITcounter;
        return;
    }
}

}

// Update dt's
void find_and_write_dt(int DT[2][SIZE],int element,int ITcounter){
int counter;

for(counter=0; counter<SIZE; counter  ){
    if(DT[0][counter]==element){
        DT[1][counter]=ITcounter;
        return;
    }
}
}


void multiply(int array[2][SIZE], int DT[2][SIZE], int multiplied[2][SIZE], int ITcounter){
int counter;

for(counter=0; counter<SIZE; counter  ){
    if(DT[0][counter]==0){
        return;
    }
    multiplied[0][counter]=DT[0][counter]; //Write element's id
    multiplied[1][counter]=(ITcounter-DT[1][counter])*array[1][(DT[0][counter])-1]; // compute size*dt
}
}
void kick(int array[2][SIZE], int DT[2][SIZE], int multiplied[2][SIZE], int element_to_write, int R, int *cache, int CSize, int el){
int counter;
int size;
int sum_of_size;
int max_mult, el_at_max;

sum_of_size=R;
size=array[1][element_to_write-1];



do{
    //find biggest multiplied
    max_mult=multiplied[1][0];
    el_at_max=multiplied[0][0];
    for(counter=1; counter<el; counter  ){
        if(max_mult<multiplied[1][counter]){
            max_mult=multiplied[1][counter];
            el_at_max=multiplied[0][counter];
        }
    }
    //kick multiplied and set 0
    for(counter=0; counter<el; counter  ){
        if(multiplied[0][counter]==el_at_max){
            multiplied[0][counter]=0;
            multiplied[1][counter]=0;
            break;
        }
    }

    //fix multiplied array
    while(counter<el){
        multiplied[0][counter]=multiplied[0][counter 1];
        multiplied[1][counter]=multiplied[1][counter 1];
        counter  ;
    }
    
    //find element to kick in dt and set it to 0
    for(counter=0; counter<el; counter  ){
        if(DT[0][counter]==el_at_max){
            DT[0][counter]=0;
            DT[1][counter]=0;
            break;
        }
        if(counter==el-1){printf("WTF!!!n");}
    }
    
    //fix dt array
    while(counter<el){
        DT[0][counter]=DT[0][counter 1];
        DT[1][counter]=DT[1][counter 1];
        counter  ;
    }
    
    //find it in cache
    write_in_cache(el_at_max, cache, CSize);
    
    sum_of_size=sum_of_size array[1][el_at_max-1];
    
}
while(sum_of_size<size 1); //do until size is enough

return;
}

void write_in_cache(int el_to_swap, int *cache, int CSize){
int *pos, *cpy;
int counter;

    pos=FindinCache(cache, el_to_swap, CSize);
    if(pos==NULL){
        printf("Something went wrong item %d is not in cache!!!nExiting...n", el_to_swap);
        for(counter=0; counter< CSize; counter  ){
            printf("%d ", *(cache counter));
        }
        printf("n");
        free(cache);
        exit (-1);
    }
    //fix cache
    //Check for errors 2many pointers
    pos=pos-1;
    cpy=pos *pos;
    cpy=cpy 1;
    while(cpy<cache CSize){
        *pos=*cpy;
        pos  ;
        cpy  ;
    }
    pos  ;
    while(pos<cache CSize){
        *pos=0;
        pos  ;
    }

return;
}
 

У меня есть указатель, выделенный для имитации кэша, который имеет 10% от общего размера элементов, которые создаются случайным образом, но распределяются по размеру.С помощью политики:
-> элемент в кэше имеет штамп, в котором указано время последнего обращения.
-> если мы нажали просто обновить штамп
-> если пропустить размер вычисления * штампуйте и нажимайте на самый большой, пока у нужного мне элемента не будет достаточно места в кэше
-> если слишком большой, нет необходимости помещать его в кеш
, поэтому с функцией kick моя программа не всегда работает, но без нее она работает отлично!!
я пытаюсь отладить его с помощью valgrind, но я не могу понять, почему я принимаю эти ошибки:

 ==3830== Command: ./test
==3830== 
==3830== Invalid read of size 4
==3830==    at 0x109349: FindinCache (test.c:278)
==3830==    by 0x108BD7: main (test.c:100)
==3830==  Address 0x55cd1a8 is 0 bytes after a block of size 360 alloc'd
==3830==    at 0x4C31B0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3830==    by 0x108A93: main (test.c:75)
==3830==
Not worth to get it into the cache with id: 1
==3830== Invalid read of size 4
==3830==    at 0x1092DD: FindelEmentsInCache (test.c:254)
==3830==    by 0x108B3D: main (test.c:90)
==3830==  Address 0x55cd1a8 is 0 bytes after a block of size 360 alloc'd
==3830==    at 0x4C31B0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3830==    by 0x108A93: main (test.c:75)
==3830==   
==3830== 
==3830== HEAP SUMMARY:
==3830==     in use at exit: 0 bytes in 0 blocks
==3830==   total heap usage: 2 allocs, 2 frees, 1,384 bytes allocated
==3830== 
==3830== All heap blocks were freed -- no leaks are possible
==3830== 
==3830== For counts of detected and suppressed errors, rerun with: -v
==3830== ERROR SUMMARY: 284 errors from 2 contexts (suppressed: 0 from 0)
 

Если вы считаете, что ваш код правильный, но Valgrind обнаруживает и выдает ошибку, то в 99% случаев вы ошибаетесь, а Valgrind прав.

Ошибки говорят о том, что вы читаете дальше конца блока памяти malloc’d.

Обычно это не вызывает ошибки сегментации. Это произойдет только в том случае, если вы попытаетесь получить доступ к адресу памяти, который не сопоставлен или сопоставлен с неправильными разрешениями. Поскольку сопоставление выполняется блоками размером не менее 4 КБ (на x86 и amd64), то обычно чтение всего на 4 байта за пределы массива не вызывает сбоя в сегменте.