/* file: cache.c * author: Robert S. Laramee * class: cs720/820 * date started: 12 Mar 98 * date "finished": 09 Apr 98 * project: assignment 3 * description: see xread.c for a description */ #include/* for printf(), scanf(), fopen(), fclose() etc. */ #include /* for errno */ #include /* for realpath() on panama.unh.edu */ #include /* for realpath(), getcwd() on panama.unh.edu */ #include /* for realpath() on alberti.unh.edu */ #include /* for strlen(), strcat(), strcmp(), strcpy() */ #include /* for open(), lseek() */ #include /* for open() */ #include /* for open() */ #include /* for read(), write(), lseek() */ #include "cache.h" /* contains definitions of cache data structures */ #define SUCCESS 1 int num_free = CACHE_SIZE; /* number of packets on free list */ /* this function * 1. allocates the memory space for the cache * 2. links all the cache packets on to the cache packet free list and * 3. also sets up the hash table which is just an array of pointers to * CACHE_PKTs */ void init_it() { int i =0; CACHE_PKT *original, *new; cp_free_list = NULL; /* initialize pointers to NULL */ cp_lru_head = NULL; cp_lru_tail = NULL; /* this sets up the free list */ if ((cp_free_list = (CACHE_PKT *)malloc (sizeof(CACHE_PKT))) != NULL) { cp_free_list->c_free_next = NULL; cp_free_list->c_lru_prev = NULL; cp_free_list->c_lru_next = NULL; cp_free_list->bollock_num = 0; cp_free_list->block_size = 0; } if ((new = (CACHE_PKT *)malloc (sizeof(CACHE_PKT))) == NULL) { printf("\n no memory for malloc() \n"); exit(EXIT_FAILURE); } new->c_free_next = NULL; new->c_lru_prev = NULL; new->c_lru_next = NULL; new->bollock_num = -1; new->block_size = 0; cp_free_list->c_free_next = new; for (i=2; i < CACHE_SIZE; i++) { original = new; // save previous pointer if ((new = (CACHE_PKT *)malloc (sizeof(CACHE_PKT))) == NULL) { printf("\n no memory for malloc() \n"); exit(EXIT_FAILURE); } new->c_free_next = NULL; new->c_lru_prev = NULL; new->c_lru_next = NULL; new->bollock_num = -(i); new->block_size = 0; original->c_free_next = new; } /* end for() */ /* initialize the hash table pointers to NULL */ for (i=0; i < HASH_SIZE; i++) { hash_table[i] = NULL; } free(new); /* no memory leaks here */ } /* end init_it() */ /* If cache free list is not empty, this function unlinks one cache packet * from the free list and returns a pointer to the same. If the free list * is empty, a null pointer is returned. */ CACHE_PKT *get_cache_free() { int i, free_count=0; CACHE_PKT *second_to_last, *last; if (num_free == 0) { return NULL; } /* go to the end of the free list, and count the packets */ last = cp_free_list; while ( last->c_free_next != NULL) { last = last->c_free_next; free_count++; } /* go to second to last packet and set its c_free_next pointer to NULL */ second_to_last = cp_free_list; for(i=0; i < free_count-1; i++) { second_to_last = second_to_last->c_free_next; } second_to_last->c_free_next = NULL; num_free--; return last; } /* Given a file name and the block number, this function checks to see if * the block is in the cache. If it is, it is moved to the head of the * least recently used queue. */ int locate_block_in_cache(char *p_file_name, long bollock_num , CACHE_PKT **p_p_cache_pkt) { int i; CACHE_PKT *original, *this, *temp; /* see if the block is in the hash table based on block number * AND file name. */ for (i=0; i < HASH_SIZE; i++) { /* printf("locate_bollock_in_cache():: hash_table[%d] = %d \n" , i, hash_table[i]); */ if (hash_table[i] != NULL) { this = hash_table[i]; if( (this->bollock_num == bollock_num) && (strcmp(this->file_name, p_file_name) == 0) ) { printf("bytes located in cache \n"); /* IF the packet is not already at the head of the LRU list THEN * put it at the head of the LRU list */ if (hash_table[i] != cp_lru_head) { original = hash_table[i]; // save original pointer this = hash_table[i]; // set this pointer this = this->c_lru_next; // move to next packet this->c_lru_prev = original->c_lru_prev; // reset its // previous pointer if (original->c_lru_prev != NULL) {// IF its previous pointer // is not NULL this = this->c_lru_prev; // move to new previous pkt this->c_lru_next = original->c_lru_next; // reset its next pointer } else { // ELSE IF its previous // was NULL THEN this is cp_lru_tail = this; // the new tail } original->c_lru_prev = cp_lru_head; // reset previous pointer cp_lru_head->c_lru_next = original; // reset heads next ptr cp_lru_head = original; // reset new head } return SUCCESS; } /* end if(this->bollock_num == temp->bollock_num) */ } /* end of if (hash_table[i] != NULL) */ } /* end of for() loop */ printf("bytes read from disk \n"); return -1; } /* end of locate_block_in_cache() */ /* This function inserts the packet pointed to by p_cache_pkt in the hash * table and the LRU list. */ void put_block_in_cache(char *p_file_name, long bollock_num , CACHE_PKT **p_p_cache_pkt) { CACHE_PKT *temp; int hash_index; /* index into hash table based on file name */ char temp_file[FILE_NAME_SIZE]; /* IF the LRU list is NULL THEN * Insert the given block * set the head and tail pointers to the current block * ELSE * put the current block at the head of the LRU list */ if (cp_lru_head == NULL) { cp_lru_head = *p_p_cache_pkt; cp_lru_tail = *p_p_cache_pkt; cp_lru_head->bollock_num = bollock_num; } else { cp_lru_head->c_lru_next = *p_p_cache_pkt;// 1 set new next pointer temp = cp_lru_head; // save old head pointer cp_lru_head = *p_p_cache_pkt; // 2 set new head pointer cp_lru_head->c_lru_prev = temp; // 3 set new heads prev ptr cp_lru_head->bollock_num = bollock_num;// 4 set new heads bollock num } realpath(p_file_name, temp_file); hash_index = (strlen(temp_file) + bollock_num) % HASH_SIZE; while (hash_table[hash_index] != NULL) { // find the next free // hash index pointer in hash_index++; // case of a collision } // and update the pointer hash_table[hash_index] = *p_p_cache_pkt; // in the hash table } /* end put_block_in_cache() */ /* This function tries to locate the bollock_num in the file referenced by * p_file_name. If the block is not in the cache, this function frees (or * gets a free cache packet) that is later used by the read operation to * store a data block. * calls: locate_block_in_cache() * get_cache_free() */ int get_block_for_read(char *p_file_name, long bollock_num , CACHE_PKT **p_p_cache_pkt) { int from_fd, hash_index; char temp_file[FILE_NAME_SIZE]; CACHE_PKT *free_pkt, *temp; CACHE_PKT *new_head, *second_to_last; /* initially, index into the hash table */ if((locate_block_in_cache(p_file_name, bollock_num, p_p_cache_pkt)) == SUCCESS) { return SUCCESS; } else { /* ELSE the block was not found in the cache */ /* get a new cache packet from the free list * IF we got a free packet THEN * return it (by setting the free_pkt pointer passed to * get_block_for_read() from main() ) */ free_pkt = get_cache_free(); if (free_pkt != NULL) { *p_p_cache_pkt = free_pkt; } else { // use the packet at the end of the LRU list *p_p_cache_pkt = cp_lru_tail; // return ptr to tail new_head = cp_lru_tail; // save old tail ptr second_to_last = cp_lru_tail->c_lru_next; // save 2nd to last ptr /* set the hash_table entry for the cu_lru_tail to NULL */ realpath(cp_lru_tail->file_name, temp_file); hash_index = (strlen(temp_file) + cp_lru_tail->bollock_num) % HASH_SIZE; hash_table[hash_index] = NULL; /* update all the pointers */ second_to_last->c_lru_prev = NULL; // 1 set new tails prev ptr cp_lru_tail = second_to_last; // 2 set new tail new_head->c_lru_prev = cp_lru_head; // 3 set new heads prev ptr new_head->c_lru_next = NULL; // 4 set new head next ptr cp_lru_head->c_lru_next = new_head; // 5 set old heads next ptr cp_lru_head = new_head; // 6 reset head of LRU list cp_lru_head->bollock_num = bollock_num;// 7 set new bollock number /* update file_name_pointer */ strncpy(cp_lru_head->file_name, p_file_name, FILE_NAME_SIZE); /* read bytes from disk and copy them to the block */ if((from_fd = open(p_file_name, O_RDONLY)) == -1) { fprintf(stderr, "Error cannot open %s: %s \n" , p_file_name, strerror(errno)); exit(EXIT_FAILURE); } if (lseek(from_fd, bollock_num * BLOCK_SIZE, SEEK_SET) != (bollock_num * BLOCK_SIZE)) { fprintf(stderr, "Error with offset in file %s: %s \n" , p_file_name, strerror(errno)); exit(EXIT_FAILURE); } if (read(from_fd, cp_lru_head->file_data, BLOCK_SIZE) != BLOCK_SIZE) { fprintf(stderr, "Error reading file %s: %s \n" , p_file_name, strerror(errno)); exit(EXIT_FAILURE); } close(from_fd); realpath(p_file_name, temp_file); hash_index = (strlen(temp_file) + bollock_num) % HASH_SIZE; while (hash_table[hash_index] != NULL) { // find next available // hash index to avoid hash_index++; // collisions } hash_table[hash_index] = *p_p_cache_pkt; hash_table[hash_index] = cp_lru_head; temp = hash_table[hash_index]; // update hash table temp->bollock_num = bollock_num; // pointer return SUCCESS; } return -1; } } /* end get_block_for_read */