Changeset 8953

Timestamp:

07/15/11 11:28:59 (23 months ago)

Author:

jdenton

Message:

Updates to memory entry functions.

Files:

• branches/Orange-Branch/src/client/usrint/ucache.c (modified) (10 diffs)

branches/Orange-Branch/src/client/usrint/ucache.c

@@ -108 +108 @@
         {
                 mtbl->mem[i].item = NIL;
+                mtbl->mem[i].tag = NIL;
+                mtbl->mem[i].next = NIL;
+                mtbl->mem[i].lru_prev = NIL;
+                mtbl->mem[i].lru_next = NIL;
         }
         /* set up list of free hash table entries */
@@ -121 +125 @@
 {
         struct file_table_s *ftbl = &(ucache->ftbl);
-        uint32_t ret = ftbl->free_blk;
-        if((int32_t)ret!=NIL){
+        uint32_t free_blk = ftbl->free_blk;
+        if((int32_t)free_blk!=NIL){
                 /* Use zero since free_blks have no ititialized mem tables */
-                ftbl->free_blk = ucache->b[ret].mtbl[0].free_list; 
-                return ret;
+                ftbl->free_blk = ucache->b[free_blk].mtbl[0].free_list; 
+                return free_blk;
         }
         else{
@@ -135 +139 @@
 static void put_free_blk(int blk)
 {
+        if(DBG)fprintf(out, "freeing blk @ index = %d\n", blk);
         struct file_table_s *ftbl = &(ucache->ftbl);
         ucache->b[blk].mtbl[0].free_list = ftbl->free_blk;
@@ -155 +160 @@
         }
         else{
-                /*      EVICT?  */
                 if(DBG)fprintf(out, "\terror getting free file entry...\n");
                 return NIL;
@@ -188 +192 @@
         if((int16_t)ret!=NIL){
                 mtbl->free_list = mtbl->mem[ret].next;
+                mtbl->mem[ret].next = NIL;
+                mtbl->mem[ret].lru_prev = NIL;
+                mtbl->mem[ret].lru_next = NIL;
                 return ret;
         }
         else{
-                /*      EVICT?  */
+                /*      EVICT LRU       */
                 return NIL;
         }
@@ -198 +205 @@
 static void put_free_ment(struct mem_table_s *mtbl, int ent)
 {
-        mtbl->mem[ent].next = mtbl->free_list;
-        mtbl->free_list = ent;
+        if(DBG)fprintf(out, "freeing memory entry = %d\n", ent);
+        /*      Reset ment values       */
+        mtbl->mem[ent].tag = NIL;
+        mtbl->mem[ent].item = NIL;
+        mtbl->mem[ent].dirty_next = NIL;
+        mtbl->mem[ent].lru_next = NIL;
+        mtbl->mem[ent].lru_prev = NIL;
+        /*      Update free list to include this entry  */
+        if(ent>(MEM_TABLE_HASH_MAX-1)){
+                mtbl->mem[ent].next = mtbl->free_list;
+                mtbl->free_list = ent;
+        }
 }
 
@@ -292 +309 @@
         uint32_t free_mtbl_blk;
         uint16_t free_mtbl_ent; 
-        /*      Create fre mtbls if none are available  */
+        /*      Create free mtbls if none are available */
         if(get_next_free_mtbl(&free_mtbl_blk, &free_mtbl_ent)!=1){
                 /*      Attempt to intitialize remaining blocks' memory tables  */
@@ -299 +316 @@
                         add_free_mtbls(ucache->ftbl.free_blk);
                         get_next_free_mtbl(&free_mtbl_blk, &free_mtbl_ent);
-                        //continue
                 }
                 else{
@@ -319 +335 @@
                         /*      point new head's "next" to former head  */
                         current->next = free_fent;      
-                        //if(DBG)fprintf(out, "\tnew head's next = %d\n", (int16_t)current->next);
                 }
                 else{   /*      No free file entries available: policy? */
+                        if(DBG)fprintf(out, "\terror: no free file entries\n");
                         /*      Evict or return NIL     */
-                        if(DBG)fprintf(out, "\terror: no free file entries");
-                        return (struct mem_table_s *)NIL;
+                        if(F_EVICT){    /*      EVICT   */
+                                uint16_t temp_ndx = current->next;
+                                current = &(ftbl->file[current->next]);
+                                uint16_t next = current->next;
+                                put_free_fent(temp_ndx);
+                                /*      May need to do more here        ...mtbls?*/
+                                free_fent = get_free_fent();
+                                current = &(ftbl->file[free_fent]);
+                                current->next = next;
+                        }
+                        else{   /*      Return NIL      */
+                                return (struct mem_table_s *)NIL;
+                        }
+
+
                 }
         }
@@ -364 +393 @@
         uint32_t tmp_blk = ftbl->free_mtbl_blk;
         uint16_t tmp_ent = ftbl->free_mtbl_ent;
-
         /*      newly free mtbl becomes new head of free mtbl list      */
         ftbl->free_mtbl_blk = file_mtbl_blk;
         ftbl->free_mtbl_ent = file_mtbl_ent;
-
         /* Point to the next free mtbl (the former head)        */
         mtbl->free_list_blk = tmp_blk;
         mtbl->free_list = tmp_ent;
-        
         /*      Free the file entry     */
         ftbl->file[file_ent_prev_index].next = ftbl->file[file_ent_index].next;
-        put_free_fent(file_ent_index);  //not okay restore links
+        put_free_fent(file_ent_index);
         if(DBG)fprintf(out, "\tremoval sucessful\n");
-        //print the values to ensure they really got set
-        //if(DBG)fprintf(out, "\ttag_id\t\t0X%X\n", ftbl->file[file_ent_index].tag_id);
-        //if(DBG)fprintf(out, "\ttag_handle\t0X%llX\n", ftbl->file[file_ent_index].tag_handle);
         return(1);
 }
 
-static void *lookup_mem(struct mem_table_s *mtbl, uint64_t offset)
-{
+static void *lookup_mem(struct mem_table_s *mtbl, 
+                                        uint64_t offset, 
+                                        uint32_t *item_index,
+                                        uint16_t *mem_ent_index,
+                                        uint16_t *mem_ent_prev_index)
+{
+        if(DBG)fprintf(out, "performing ment lookup...\n");
+        /*      index into mem hash table       */
+        unsigned int index = offset % MEM_TABLE_HASH_MAX;
+        if(DBG)fprintf(out, "\toffset: 0X%llX hashes to index: %u\n", offset, index);
+        struct mem_ent_s *current = &(mtbl->mem[index]);
+        int16_t p,c,n;  /*      previous, current, next memory entry index in mtbl      */
+        p = NIL; c = index; n = current->next;
+        while(1){
+                //if(DBG)fprintf(out, "\tp=%d\tc=%d\tn=%d\n", (int)p, (int)c, (int)n);
+                //tags match?
+                if(offset==current->tag){
+                        if(DBG)fprintf(out, "\tmatch located: 0X%llX==0X%llX\n", offset, current->tag);
+                        //possibly update LRU list based on lookup?
+                        
+                        /*      If params !NULL, set their values       */
+                        if(item_index!=NULL && mem_ent_index!=NULL && 
+                                mem_ent_prev_index!=NULL){
+                                        *item_index = current->item;
+                                        *mem_ent_index = c;
+                                        *mem_ent_prev_index = p;
+                        }
+                        return (void *)(&ucache->b[current->item].mblk);
+                }
+                else{
+                        //if(DBG)fprintf(out, "\t0X%llX!=0X%llX\n", offset, current->tag);
+                        //if next available iterate
+                        if((int16_t)current->next==NIL){
+                                if(DBG)fprintf(out, "\tmemory entry not found\n");
+                                return (struct mem_table_s *)NIL;
+                        }
+                        else{
+                                //fprintf(out, "\tnext really not null: %d!=-1\n", (int)(current->next)); 
+                                current = &(mtbl->mem[current->next]);
+                                p=c; c=n; n=current->next;
+                                //if(DBG)fprintf(out, "\titerating across chain: next index = %d\n", (int16_t)n);
+                        }
+                }
+        }
+}
+
+
+void print_lru(struct mem_table_s *mtbl){
+        if(DBG)fprintf(out, "\tno ment\n");
+        if(DBG)fprintf(out, "\tprinting lru list:\n");
+        if(DBG)fprintf(out, "\t\tlru: %d\n", (int16_t)mtbl->lru_last);
+        uint16_t current= mtbl->lru_last; 
+        while((int16_t)current!=NIL){
+                current = mtbl->mem[current].lru_prev;
+                if(DBG)fprintf(out, "\t\tprev: %d\n", (int16_t)current); 
+        }
+}
+
+void update_lru(struct mem_table_s *mtbl, 
+                                        uint16_t index){
+                        if(DBG)fprintf(out, "updating lru...\n");
+                        if((int16_t)index<MEM_TABLE_HASH_MAX){
+                                if(DBG)fprintf(out, "\t%d<MEM_TABLE_HASH_MAX, not adding to LRU\n", index);
+                                return;
+                        }
+                        /*      update LRU List */
+                        if((int16_t)mtbl->lru_first==NIL && (int16_t)mtbl->lru_last==NIL){
+                                if(DBG)fprintf(out, "\tsetting lru first and last\n");
+                                mtbl->lru_first = index;
+                                mtbl->lru_last = index;
+                                mtbl->mem[index].lru_prev = NIL;
+                                mtbl->mem[index].lru_next = NIL;
+                        }
+                        else if(mtbl->lru_first==mtbl->lru_last){
+                                if(mtbl->lru_first!=index){//if not already the first and last
+                                        if(DBG)fprintf(out, "\tinserting second record in LRU\n");
+                                        mtbl->mem[mtbl->lru_last].lru_prev = index;     //point tail.prev to new
+                                        mtbl->mem[index].lru_prev = NIL;                        //point new.prev to nil
+                                        mtbl->mem[index].lru_next = mtbl->lru_last;     //point the new.next to the tail
+                                        mtbl->lru_first = index;                                        //point the head to the new
+                                }
+                        }
+                        else{
+                                if(DBG)fprintf(out, "\trepairing previous LRU links and inserting record in LRU\n");
+                                /*      repair links    */      
+                                if((int16_t)mtbl->mem[index].lru_prev!=NIL){
+                                        mtbl->mem[mtbl->mem[index].lru_prev].lru_next = 
+                                                mtbl->mem[index].lru_next;
+                                }
+                                if((int16_t)mtbl->mem[index].lru_next!=NIL){
+                                        mtbl->mem[mtbl->mem[index].lru_next].lru_prev =         
+                                                mtbl->mem[index].lru_prev;
+                                }
+                                /*      update nodes own link   */
+                                mtbl->mem[mtbl->lru_first].lru_prev = index; 
+                                mtbl->mem[index].lru_next = mtbl->lru_first;
+                                mtbl->mem[index].lru_prev = NIL;
+                        /*      Finally, establish this entry as the first on lru       */
+                                mtbl->lru_first = index;
+                        }
+}
+
+/*      Set the block index where data is stored        */
+static void *set_item(struct mem_table_s *mtbl, 
+                                        uint64_t offset, 
+                                        uint16_t index){        
+                int free_blk = get_free_blk();
+                if(free_blk!=NIL){      /*      got block       */
+                        /*      increment num_blocks used by this mtbl  */
+                        mtbl->num_blocks++;
+                        update_lru(mtbl, index);
+                        if(DBG)fprintf(out, "\tsuccessfully inserted into ment\n");
+                        /*      set item to block number        */
+                        mtbl->mem[index].tag = offset;
+                        mtbl->mem[index].item = free_blk;
+                        return (void *)&(ucache->b[free_blk]); 
+                }
+                else{   /*      NIL     */
+                        if(DBG)fprintf(out, "\tno blk\n");
+                        return (void *)NIL;
+                }
 }
 
 static void *insert_mem(struct mem_table_s *mtbl, uint64_t offset)
 {
+        if(DBG)fprintf(out, "trying to insert mem...\n");
+        /*      index into mem hash table       */
+        unsigned int index = offset % MEM_TABLE_HASH_MAX;
+        if(DBG)fprintf(out, "\toffset: 0X%llX hashes to index: %u\n", offset, index);
+        struct mem_ent_s *current = &(mtbl->mem[index]);
+        /*      lookup first    */
+        void *returnValue = lookup_mem(mtbl, offset, NULL, NULL, NULL);
+        if((int)returnValue!=NIL){
+                if(DBG)fprintf(out, "\tblock for this offset already exists @ 0X%X", (unsigned int)returnValue);
+                return returnValue;
+        }
+        if(DBG)fprintf(out, "\tlookup returned NIL\n");
+        if((int64_t)mtbl->mem[index].tag!=NIL){ /*      if head occupied, need to get free ment */
+                int mentIndex = get_free_ment(mtbl);
+                if(mentIndex==NIL){     /*      no free memory entry available  */
+                        //print_lru(mtbl);
+                        uint16_t lru = mtbl->lru_last;  
+                        if(DBG)fprintf(out, "evicting memory entry = %d\n", lru);
+                        remove_mem(mtbl, mtbl->mem[lru].tag);   /*      evict LRU ment  */
+                        mentIndex = get_free_ment(mtbl);                /*      try to get ment again */
+
+                }
+                if(mentIndex!=NIL){
+                        if(DBG)fprintf(out, "\tfound free memory entry @ index = %d\n", mentIndex);
+                        /*      insert after head of chain      */
+                        uint16_t next_ment = current->next;
+                        current->next = mentIndex;
+                        mtbl->mem[mentIndex].next = next_ment;
+                        return set_item(mtbl, offset, mentIndex);       
+                }
+        }
+        else{   /*      No need to iterate to next in chain, just use head      */
+                return set_item(mtbl, offset, index);                                   
+        }
 }
 
 static int remove_mem(struct mem_table_s *mtbl, uint64_t offset)
 {
-}
-
-/* externally visible API */
-#if 0
-int ucache_open_file(PVFS_object_ref *handle)
-{
-}
-
-void *ucache_lookup(PVFS_object_ref *handle, uint64_t offset)
-{
-}
-
-void *ucache_insert(PVFS_object_ref *handle, uint64_t offset)
-{
-}
-
-int ucache_remove(PVFS_object_ref *handle, uint64_t offset)
-{
-}
-
-int ucache_flush(PVFS_object_ref *handle)
-{
-}
-
-int ucache_close_file(PVFS_object_ref *handle)
-{
-}
-#endif
+        if(DBG)fprintf(out, "trying to remove memory entry...\n");
+        //some indexes...
+        int32_t item_index;
+        int16_t mem_ent_index;
+        int16_t mem_ent_prev_index;
+
+        void *retValue = lookup_mem(mtbl, offset, &item_index, &mem_ent_index, &mem_ent_prev_index);
+
+        /*      Verify we've recieved the necessary info        */
+        if((int)retValue==NIL){
+                if(DBG)fprintf(out, "\tremoval error: memory entry not found matching offset");
+                return NIL;
+        }
+
+        /*      Remove from LRU */
+                /*      update each of adjacent nodes' link     */
+        if((int16_t)mtbl->mem[mem_ent_index].lru_prev!=NIL){
+                mtbl->mem[mtbl->mem[mem_ent_index].lru_prev].lru_next = mtbl->mem[mem_ent_index].lru_next;
+        }
+        if((int16_t)mtbl->mem[mem_ent_index].lru_next!=NIL){
+                mtbl->mem[mtbl->mem[mem_ent_index].lru_next].lru_prev = mtbl->mem[mem_ent_index].lru_prev;
+        }
+
+        if(mem_ent_index==mtbl->lru_first){ /* is node the head */
+                mtbl->lru_first = mtbl->mem[mem_ent_index].lru_next;    
+        }
+        if(mem_ent_index==mtbl->lru_last){ /* is node the tail */
+                mtbl->lru_last = mtbl->mem[mem_ent_index].lru_prev;
+        }
+        /*      Remove from Dirty if Dirty      */
+
+        /*      add memory block back to free list      */
+        put_free_blk(item_index);
+        
+        /*      Repair link     */
+        if((int16_t)mem_ent_prev_index!=NIL){
+                mtbl->mem[mem_ent_prev_index].next = mtbl->mem[mem_ent_index].next;
+        }
+        /*      newly free mem entry becomes new head of free mem entry list if less than hash table max        */
+        put_free_ment(mtbl, mem_ent_index);
+        mtbl->num_blocks--;
+        if(DBG)fprintf(out, "\tmemory entry removal sucessful\n");
+        return(1);
+}
+