root/branches/Orange-Branch/src/client/usrint/ucache.c @ 9025

Revision 9025, 54.2 KB (checked in by jdenton, 21 months ago)

Integrating ucache with usrint (in progress):

Added a parameter to the pvfs_alloc_descriptor function in openfile-util:

the parameter is a pointer to a PVFS_object_ref.
the parameter can be NULL or it is used by the ucache to identify the file being inserted.

Added calls to ucache in openfile-util.c:

specifically in functions:

pvfs_alloc_descriptor
pvfs_free descriptor

ucache updates include the introduction of block level locks which may be needed
Line 
1/*
2 * (C) 2011 Clemson University
3 *
4 * See COPYING in top-level directory.
5 */
6
7/* Experimental cache for user data
8 * Currently under development.
9 *
10 * Note: When unsigned ints are set to NIL, their values are based on type:
11 *   ex: 16      0xFFFF 
12 *       32      0XFFFFFFFF
13 *       64      0XFFFFFFFFFFFFFFFF
14 *   ALL EQUAL THE SIGNED REPRESENTATION OF -1, CALLED NIL IN ucache.h 
15 */
16
17#include "ucache.h"
18
19/* Global Variables */
20static FILE *out;                   /* For Logging Purposes */
21
22static union user_cache_u *ucache;
23static int ucache_blk_cnt;
24
25static ucache_lock_t *ucache_locks; /* will refer to the shmem of all ucache locks */
26static ucache_lock_t *ucache_lock;  /* Global Lock maintaining concurrency */
27static ucache_lock_t *ucache_block_lock;
28
29/* Internal Only Function Declarations */
30
31/* Locking */
32static int lock_init(ucache_lock_t * lock);
33static int lock_lock(ucache_lock_t * lock);
34static int lock_unlock(ucache_lock_t * lock);
35static int lock_destroy(ucache_lock_t * lock);
36
37/* Initialization */
38static void add_free_mtbls(int blk);
39static void init_memory_table(int blk, int ent);
40
41/* Gets */
42static int get_next_free_mtbl(uint32_t *free_mtbl_blk, uint16_t *free_mtbl_ent);
43static int get_free_fent(void);
44static int get_free_ment(struct mem_table_s *mtbl);
45static uint16_t get_free_blk(void);
46
47/* Puts */
48static void put_free_mtbl(struct mem_table_s *mtbl, struct file_ent_s *file);
49static void put_free_fent(int fent);
50static void put_free_ment(struct mem_table_s *mtbl, int ent);
51static void put_free_blk(int blk);
52
53/* File Entry Chain Iterator */
54static int file_done(int index);
55static int file_next(struct file_table_s *ftbl, int index);
56
57/* Memory Entry Chain Iterator */
58static int ment_done(int index);
59static int ment_next(struct mem_table_s *mtbl, int index);
60
61/* Dirty List Iterator */
62static int dirty_done(uint16_t index);
63static int dirty_next(struct mem_table_s *mtbl, uint16_t index);
64
65/* File and Memory Insertion */
66static struct mem_table_s *insert_file(uint32_t fs_id, uint64_t handle);
67static void *insert_mem(struct mem_table_s *mtbl, uint64_t offset);
68static void *set_item(struct mem_table_s *mtbl,uint64_t offset, uint16_t index);
69
70/* File and Memory Lookup */
71static struct mem_table_s *lookup_file(
72    uint32_t fs_id,
73    uint64_t handle,
74    uint32_t *file_mtbl_blk,    /* Can be NULL if not desired TODO: remove these later? */
75    uint16_t *file_mtbl_ent, 
76    uint16_t *file_ent_index,
77    uint16_t *file_ent_prev_index
78);
79static void *lookup_mem(struct mem_table_s *mtbl,
80                    uint64_t offset,
81                    uint32_t *item_index,
82                    uint16_t *mem_ent_index,
83                    uint16_t *mem_ent_prev_index
84);
85
86/* File and Memory Entry Removal */
87static int remove_file(uint32_t fs_id, uint64_t handle);
88static void remove_all_memory_entries(struct mem_table_s *mtbl);
89static int remove_mem(struct mem_table_s *mtbl, uint64_t offset);
90
91/* Eviction Utilities */
92static int evict_file(unsigned int index);
93static int locate_max_mtbl(struct mem_table_s **mtbl);
94static void update_lru(struct mem_table_s *mtbl, uint16_t index);
95static int evict_LRU(struct mem_table_s *mtbl);
96
97/* List Printing Functions */
98/*
99 * static void print_lru(struct mem_table_s *mtbl);
100 * static void print_dirty(struct mem_table_s *mtbl);
101 */
102
103/*  Externally Visible API
104 *      The following functions are thread/processor safe regarding the cache
105 *      tables and data.     
106 */
107
108/**  Initializes the cache.
109 *  Mainly, it aquires a shared memory segment used to cache data.
110 *
111 *  This function also initializes the the FTBL and some MTBLs.
112 *
113 *  The whole cache is protected by a locking mechanism to maintain concurrency.
114 *  Currently using posix semaphores
115 */
116void ucache_initialize(void)
117{
118    int i = 0;
119
120    /* Aquire shared memory for ucache_locks */
121    ucache_locks = shmat(shmget(ftok(GET_KEY_FILE, 'a'), (LOCK_SIZE
122           * (BLOCKS_IN_CACHE + 1)), CACHE_FLAGS), NULL, AT_FLAGS);
123    /* Global Cache lock stored in first LOCK_SIZE position */
124    ucache_lock = ucache_locks;
125
126    /* Initialize Global Cache Lock */
127    lock_init(ucache_lock);
128    lock_lock(ucache_lock);
129
130    /* The next BLOCKS_IN_CACHE number of block locks follow the global lock */
131    ucache_block_lock = ucache_locks + 1;
132    /* Initialize Block Level Locks */
133    for(i = 0; i < BLOCKS_IN_CACHE; i++)
134    {
135        lock_init(get_block_lock(i));
136    }
137
138    /* Aquire shared memory for ucache */
139    int key;
140    int id;
141    char *key_file_path;
142    /*  Direct output   */
143    if(!out)out = stdout;
144    /* Note: had to set: kernel.shmmax amd kernel.shmall */
145    /* set up shared memory region */
146    key_file_path = GET_KEY_FILE;
147    key = ftok(key_file_path, PROJ_ID);
148    id = shmget(key, CACHE_SIZE, CACHE_FLAGS);
149    ucache = shmat(id, NULL, AT_FLAGS);
150    ucache_blk_cnt = BLOCKS_IN_CACHE;
151    if(DBG)
152    {
153        fprintf(out, "key:\t\t\t0X%X\n", key);
154        fprintf(out, "id:\t\t\t%d\n", id);
155        fprintf(out, "ucache ptr:\t\t0X%X\n", (unsigned int)ucache);
156    }
157    /* initialize mtbl free list table */
158    ucache->ftbl.free_mtbl_blk = NIL;
159    ucache->ftbl.free_mtbl_ent = NIL;
160    add_free_mtbls(0);
161    /* set up list of free blocks */
162    ucache->ftbl.free_blk = 1;
163    for (i = 1; i < ucache_blk_cnt - 1; i++)
164    {
165        ucache->b[i].mtbl[0].free_list = i+1;
166    }
167    ucache->b[ucache_blk_cnt - 1].mtbl[0].free_list = NIL;
168    /* set up file hash table */
169    for (i = 0; i < FILE_TABLE_HASH_MAX; i++)
170    {
171        ucache->ftbl.file[i].tag_handle = NIL;
172        ucache->ftbl.file[i].tag_id = NIL;
173        ucache->ftbl.file[i].mtbl_blk = NIL;
174        ucache->ftbl.file[i].mtbl_ent = NIL;
175        ucache->ftbl.file[i].next = NIL;
176    }
177    /* set up list of free hash table entries */
178    ucache->ftbl.free_list = FILE_TABLE_HASH_MAX;
179    for (i = FILE_TABLE_HASH_MAX; i < FILE_TABLE_ENTRY_COUNT - 1; i++)
180    {
181        ucache->ftbl.file[i].mtbl_blk = NIL;
182        ucache->ftbl.file[i].mtbl_ent = NIL;
183        ucache->ftbl.file[i].next = i+1;
184    }
185    ucache->ftbl.file[FILE_TABLE_ENTRY_COUNT - 1].next = NIL;
186    lock_unlock(ucache_lock);
187}
188
189int ucache_open_file(PVFS_fs_id *fs_id, PVFS_handle *handle,
190                                    struct mem_table_s *mtbl
191)
192{
193    lock_lock(ucache_lock);
194    mtbl= lookup_file((uint32_t)(*fs_id), (uint64_t)(*handle), NULL, NULL, NULL,
195                                                                          NULL);
196    if((int)mtbl==NIL)
197    {
198        mtbl = insert_file((uint32_t)*fs_id, (uint64_t)*handle);
199        if((int)mtbl==NIL)
200        {   /* Error - Could not insert */
201            lock_unlock(ucache_lock);
202            return -1;
203        }
204        else
205        {
206            /* File Inserted*/
207            lock_unlock(ucache_lock);
208            return 1;
209        }
210    }
211    else
212    {
213        /* File was previously Inserted */
214        lock_unlock(ucache_lock);
215        return 0;
216    }
217}
218
219/** Returns ptr to block in cache based on file and offset */
220void *ucache_lookup(PVFS_fs_id *fs_id, PVFS_handle *handle, uint64_t offset)
221{
222    lock_lock(ucache_lock);
223    struct mem_table_s *mtbl= lookup_file(
224        (uint32_t)(*fs_id), (uint64_t)(*handle), NULL, NULL, NULL, NULL);
225    if((int)mtbl!=NIL)
226    {
227        char *retVal = (char *)lookup_mem(mtbl, (uint64_t)offset, NULL, NULL,
228                                                                        NULL);
229        lock_unlock(ucache_lock);
230        return((void *)retVal);
231    }
232    lock_unlock(ucache_lock);
233    return (void *)NIL;
234}
235
236/** Prepares the data structures for block storage.
237 * On success, returns a pointer to where the block of data should be written.
238 * On failure, returns NIL.
239 */
240void *ucache_insert(PVFS_fs_id *fs_id, PVFS_handle *handle, uint64_t offset)
241{
242    lock_lock(ucache_lock);
243    struct mem_table_s *mtbl= lookup_file(
244        (uint32_t)(*fs_id), (uint64_t)(*handle), NULL, NULL, NULL, NULL);
245    if((int)mtbl==NIL)
246    {
247        lock_unlock(ucache_lock);
248        return (void *)NIL;
249    }
250    else
251    {
252        if(remove_mem(mtbl, (uint64_t)offset)==NIL){
253            lock_unlock(ucache_lock);
254            return (void *)NIL;
255        }
256        char * retVal= insert_mem(mtbl, (uint64_t)offset);
257        lock_unlock(ucache_lock);
258        return ((void *)retVal);
259    }
260}
261
262/**  Removes a cached block of data from mtbl */
263int ucache_remove(PVFS_fs_id *fs_id, PVFS_handle *handle, uint64_t offset)
264{
265    lock_lock(ucache_lock);
266    struct mem_table_s *mtbl= lookup_file(
267        (uint32_t)(*fs_id), (uint64_t)(*handle), NULL, NULL, NULL, NULL);
268    if((int)mtbl!=NIL)
269    {
270        int retVal = remove_mem(mtbl, (uint64_t)offset);
271        lock_unlock(ucache_lock);
272        return retVal;
273    }       
274    lock_unlock(ucache_lock);
275    return NIL;
276}
277
278/** Flushes dirty blocks to the I/O Nodes */
279int ucache_flush(PVFS_fs_id *fs_id, PVFS_handle *handle)
280{
281    lock_lock(ucache_lock);
282    struct mem_table_s *mtbl= lookup_file(
283        (uint32_t)(*fs_id), (uint64_t)(*handle), NULL, NULL, NULL, NULL);
284    if((int)mtbl==NIL)
285    {
286        return NIL;
287    }
288    int i;
289    for(i=mtbl->dirty_list; !dirty_done(i); i=dirty_next(mtbl, i)){
290        struct mem_ent_s *ment = &(mtbl->mem[i]);
291        mtbl->mem[i].dirty_next = NIL;
292        if((int64_t)ment->tag==NIL || (int32_t)ment->item==NIL){
293            break;
294        }
295        /* //flush block to disk   - 2 means write */
296        //iocommon_readorwrite_nocache(2,);
297    }
298    mtbl->dirty_list = NIL;
299    lock_unlock(ucache_lock);
300    return 1;
301}
302
303/** Removes all memory entries in the mtbl corresponding to the file info
304 * provided as parameters. It also removes the mtbl and the file entry from
305 * the cache.
306 */
307int ucache_close_file(PVFS_fs_id *fs_id, PVFS_handle *handle)
308{
309    lock_lock(ucache_lock);
310    uint32_t file_mtbl_blk;
311    uint16_t file_mtbl_ent;
312    uint16_t file_ent_index;
313    uint16_t file_ent_prev_index;
314    struct mem_table_s *mtbl= lookup_file(
315        (uint32_t)(*fs_id),
316        (uint64_t)(*handle),
317        &file_mtbl_blk,
318        &file_mtbl_ent,
319        &file_ent_index,
320        &file_ent_prev_index);
321    if((int)mtbl==NIL)
322    {
323        lock_unlock(ucache_lock);
324        return NIL;
325    }
326    remove_all_memory_entries(mtbl);
327    struct file_ent_s *file = &(ucache->ftbl.file[file_ent_index]);
328    put_free_mtbl(mtbl, file);
329    put_free_fent(file_ent_index);
330    lock_unlock(ucache_lock);
331    return 1;
332}
333
334/** Decrements the reference count of a particular mtbl. */
335void ucache_dec_ref_cnt(struct mem_table_s * mtbl)
336{
337    lock_lock(ucache_lock);
338    /* decrement ref_cnt of mtbl */
339    if(mtbl->ref_cnt!=0)
340        mtbl->ref_cnt--;
341    lock_unlock(ucache_lock);
342}
343
344/** Increments the reference count of a particular mtbl. */
345void ucache_inc_ref_cnt(struct mem_table_s * mtbl)
346{
347    lock_lock(ucache_lock);
348    /* increment ref_cnt of mtbl */
349    mtbl->ref_cnt++;
350    lock_unlock(ucache_lock);
351}
352
353/** Dumps all cache related information. */
354void ucache_info(
355    FILE *out,
356    union user_cache_u *ucache,
357    ucache_lock_t *ucache_lock)
358{
359    fprintf(out, "\n#defines:\n");
360    /* First, print many of the #define values */
361    fprintf(out, "MEM_TABLE_ENTRY_COUNT = %d\n", MEM_TABLE_ENTRY_COUNT);
362    fprintf(out, "FILE_TABLE_ENTRY_COUNT = %d\n", FILE_TABLE_ENTRY_COUNT);
363    fprintf(out, "CACHE_BLOCK_SIZE_K = %d\n", CACHE_BLOCK_SIZE_K);
364    fprintf(out, "MEM_TABLE_HASH_MAX = %d\n", MEM_TABLE_HASH_MAX);
365    fprintf(out, "FILE_TABLE_HASH_MAX = %d\n", FILE_TABLE_HASH_MAX);
366    fprintf(out, "MTBL_PER_BLOCK  = %d\n", MTBL_PER_BLOCK );
367    fprintf(out, "GET_KEY_FILE = %s\n", GET_KEY_FILE);
368    fprintf(out, "PROJ_ID = %d\n", PROJ_ID);
369    fprintf(out, "BLOCKS_IN_CACHE = %d\n", BLOCKS_IN_CACHE);
370    fprintf(out, "CACHE_SIZE = %d(B)\t%d(MB)\n", CACHE_SIZE,
371                                    (CACHE_SIZE/(1024*1024)));
372    fprintf(out, "AT_FLAGS = %d\n", AT_FLAGS);
373    fprintf(out, "SVSHM_MODE = %d\n", SVSHM_MODE);
374    fprintf(out, "CACHE_FLAGS = %d\n", CACHE_FLAGS);
375    fprintf(out, "NIL = %d\n\n", NIL);   
376
377    /* Lock's Shared Memory Info */
378    fprintf(out, "address of ucache_lock ptr:\t0X%X\n",
379                            (unsigned int) &ucache_lock);
380    fprintf(out, "ucache_lock ptr:\t\t0X%X\n", (unsigned int) ucache_lock);
381    /* Lock's Value */
382    int lockValue = 0;
383    #if LOCK_TYPE == 0
384    ucache_lock_getvalue(ucache_lock, &lockValue);
385    #endif
386    fprintf(out, "ucache_lock value = %d\n", lockValue);
387    /* ucache Shared Memory Info */
388    fprintf(out, "address of ucache ptr:\t0X%X\n", (unsigned int)&ucache);
389    fprintf(out, "ucache ptr:\t\t0X%X\n", (unsigned int)ucache);
390
391    struct file_table_s *ftbl = &(ucache->ftbl);
392
393    /* FTBL Info */
394    fprintf(out, "ftbl ptr:\t\t0X%X\n", (unsigned int)&(ucache->ftbl));
395    fprintf(out, "free_blk = %d\n", (int32_t)ftbl->free_blk);
396    fprintf(out, "free_mtbl_blk = %d\n", (int32_t)ftbl->free_mtbl_blk);
397    fprintf(out, "free_mtbl_ent = %d\n", (int16_t)ftbl->free_mtbl_ent);
398    fprintf(out, "free_list = %d\n", (int16_t)ftbl->free_list);
399
400    /* Other Free Blocks */
401    fprintf(out, "\nIterating Over Free Blocks:\n\n");
402    unsigned int i;
403    for(i = ftbl->free_blk; (int16_t)i != NIL; i = ucache->b[i].mtbl[0].
404                                                              free_list)
405    {
406        fprintf(out, "Free Block:\tCurrent: %d\tNext: %d\n", i,
407                               ucache->b[i].mtbl[0].free_list);
408    }
409    fprintf(out, "End of Free Blocks List\n");
410
411    /* Iterate Over Free Mtbls */
412    fprintf(out, "\nIterating Over Free Mtbls:\n");
413    uint32_t current_blk = ftbl->free_mtbl_blk;
414    uint16_t current_ent = ftbl->free_mtbl_ent;
415    while((int16_t)current_blk != NIL)
416    {
417        fprintf(out, "free mtbl: block = %d\tentry = %d\n",
418                (int16_t)current_blk, (int16_t)current_ent);
419        current_blk = (uint16_t)ucache->b[current_blk].mtbl[current_ent].
420                                                            free_list_blk;
421        current_ent = (uint16_t)ucache->b[current_blk].mtbl[current_ent].
422                                                                free_list;
423    }
424    fprintf(out, "End of Free Mtbl List\n\n");
425   
426    /* Iterating Over Free File Entries */
427    fprintf(out, "Iterating Over Free File Entries:\n");
428    uint16_t current_fent;
429    for(current_fent = ftbl->free_list; (int16_t)current_fent!=NIL;
430                      current_fent = ftbl->file[current_fent].next)
431    {
432        fprintf(out, "free file entry: index = %d\n", (int16_t)current_fent);
433    }
434    fprintf(out, "End of Free File Entry List\n\n");
435
436    fprintf(out, "Iterating Over File Entries in Hash Table:\n\n");
437    /* iterate over file table entries */
438    for(i = 0; i < FILE_TABLE_HASH_MAX; i++)
439    {
440        if(((int64_t)ftbl->file[i].tag_handle != NIL) &&
441               ((int64_t)ftbl->file[i].tag_handle != 0))
442        {
443            /* iterate accross file table chain */
444            int j;
445            for(j = i; !file_done(j); j = file_next(ftbl, j))
446            {
447                fprintf(out, "FILE ENTRY INDEX %d ********************\n", j);
448                struct file_ent_s * fent = &(ftbl->file[j]);
449                fprintf(out, "tag_handle = 0X%llX\n",
450                            (uint64_t)fent->tag_handle);
451                fprintf(out, "tag_id = 0X%X\n", (uint32_t)fent->tag_id);
452                fprintf(out, "mtbl_blk = %d\n", (int32_t)fent->mtbl_blk);
453                fprintf(out, "mtbl_ent = %d\n", (int16_t)fent->mtbl_ent);
454                fprintf(out, "next = %d\n", (int16_t)fent->next);
455
456                struct mem_table_s * mtbl = &(ucache->b[fent->mtbl_blk].
457                                                    mtbl[fent->mtbl_ent]);
458                fprintf(out, "\tMTBL INFO ********************\n");
459                fprintf(out, "\tnum_blocks = %d\n", (int16_t)mtbl->num_blocks);
460                fprintf(out, "\tfree_list = %d\n", (int16_t)mtbl->free_list);
461                fprintf(out, "\tfree_list_blk = %d\n",
462                        (int16_t)mtbl->free_list_blk);
463                fprintf(out, "\tlru_first = %d\n", (int16_t)mtbl->lru_first);
464                fprintf(out, "\tlru_last = %d\n", (int16_t)mtbl->lru_last);
465                fprintf(out, "\tdirty_list = %d\n", (int16_t)mtbl->dirty_list);
466                fprintf(out, "\tref_cnt = %d\n\n", (int16_t)mtbl->ref_cnt);
467
468                /* Iterate Over Memory Entries */
469                int k;
470                for(k = 0; k < MEM_TABLE_HASH_MAX; k++)
471                {
472                    if(((int64_t)mtbl->mem[k].tag != NIL) &&
473                            ((int64_t)mtbl->mem[k].tag != 0))
474                    {
475                        int l;
476                        for(l = k; !ment_done(l); l = ment_next(mtbl, l)){
477                            struct mem_ent_s * ment = &(mtbl->mem[l]);
478                            fprintf(out, "\t\tMEMORY ENTRY INDEX %d ***********"
479                                                              "*********\n", l);
480                            fprintf(out, "\t\ttag = 0X%llX\n",
481                                            (uint64_t)ment->tag);
482                            fprintf(out, "\t\titem = %d\n",
483                                            (int32_t)ment->item);
484                            fprintf(out, "\t\tnext = %d\n",
485                                            (int16_t)ment->next);
486                            fprintf(out, "\t\tdirty_next = %d\n",
487                                        (int16_t)ment->dirty_next);
488                            fprintf(out, "\t\tlru_next = %d\n",
489                                            (int16_t)ment->lru_next);
490                            fprintf(out, "\t\tlru_prev = %d\n\n",
491                                            (int16_t)ment->lru_prev);
492                        }
493                    }
494                    else
495                        if((uint16_t)mtbl->num_blocks != 0)
496                        {
497                            fprintf(out, "\tvacant memory entry @ index = %d\n",
498                                                                             k);
499                        }
500                }
501            }
502            fprintf(out, "End of chain @ Hash Table Index %d\n\n", i);
503        }
504        else
505            fprintf(out, "vacant file entry @ index = %d\n", i);
506    }
507}
508
509/** Returns a pointer to the block level lock corresponding to the block_index.
510 */
511ucache_lock_t * get_block_lock(int block_index)
512{
513    return (ucache_block_lock + block_index);
514}
515
516/***************************************** End of Externally Visible API */
517
518
519/* Beginning of internal only (static) functions */
520
521/** Initializes the proper lock based on the LOCK_TYPE */
522static int lock_init(ucache_lock_t * lock)
523{
524    /*  Set pshared (2nd arg) to non-zero value to share semaphore b/w forked
525     *  processes
526     */
527    /* TODO: ability to disable locking */
528    #if LOCK_TYPE==0
529    return sem_init(lock, 1, 1);
530    #elif LOCK_TYPE==1
531    return pthread_mutex_init(lock, NULL);
532    #elif LOCK_TYPE==2
533    return pthread_spin_init(lock, 1);
534    #endif
535}
536
537/** Returns 0 when lock is locked; otherwise, return -1 and sets errno */
538static int lock_lock(ucache_lock_t * lock)
539{
540    #if LOCK_TYPE==0
541    return sem_wait(lock);
542    #elif LOCK_TYPE==1
543    return pthread_mutex_lock(lock);
544    #elif LOCK_TYPE==2
545    return pthread_spin_lock(lock);
546    #endif   
547}
548
549/** If successful, return zero; otherwise, return -1 and sets errno */
550static int lock_unlock(ucache_lock_t * lock)
551{
552    #if LOCK_TYPE==0
553    return sem_post(lock);
554    #elif LOCK_TYPE==1
555    return pthread_mutex_unlock(lock);
556    #elif LOCK_TYPE==2
557    return pthread_spin_unlock(lock);
558    #endif
559}
560
561/** Upon successful completion, returns zero;
562 * Otherwise, returns -1 and sets errno.
563 */
564#if (LOCK_TYPE == 0)
565int ucache_lock_getvalue(ucache_lock_t * lock, int *sval)
566{
567    return sem_getvalue(lock, sval);
568}
569#endif
570
571/** Upon successful completion, returns zero.
572 * Otherwise, returns 1 and sets errno.
573 */
574static int lock_destroy(ucache_lock_t * lock)
575{
576    #if (LOCK_TYPE == 0)
577    return sem_destroy(lock);
578    #elif (LOCK_TYPE == 1)
579    return pthread_mutex_destroy(lock);
580    #elif (LOCK_TYPE == 2)
581    return pthread_spin_destroy(lock);
582    #endif
583}
584
585/* Dirty List Iterator */
586/** Returns true if current index is NIL, otherwise, returns 0 */
587static int dirty_done(uint16_t index)
588{
589    return ((int16_t)index==NIL);
590}
591
592/** Returns the next index in the dirty list for the provided mtbl and index */
593static int dirty_next(struct mem_table_s *mtbl, uint16_t index)
594{
595    return mtbl->mem[index].dirty_next;
596}
597
598/*  Memory Entry Chain Iterator */
599/** Returns true if current index is NIL, otherwise, returns 0 */
600static int ment_done(int index)
601{
602    return ((int16_t)index==NIL);
603}
604
605/** Returns the next index in the memory entry chain for the provided mtbl
606 * and index.
607 */
608static int ment_next(struct mem_table_s *mtbl, int index)
609{
610    return mtbl->mem[index].next;
611}
612
613/*  File Entry Chain Iterator   */
614/** Returns true if current index is NIL, otherwise, returns 0 */
615static int file_done(int index)
616{
617    return ((int16_t)index==NIL);
618}
619
620/** Returns the next index in the file entry chain for the provided mtbl
621 * and index.
622 */
623static int file_next(struct file_table_s *ftbl, int index)
624{
625    return ftbl->file[index].next;
626}
627
628/**This function should only be called when the ftbl has no free mtbls.
629 * It initizializes MTBL_PER_BLOCK additional mtbls in the block provided,
630 * meaning this block will no longer be used for storing file data but
631 * hash table related data instead.
632 */
633static void add_free_mtbls(int blk)
634{
635    int i, start_mtbl;
636    struct file_table_s *ftbl = &(ucache->ftbl);
637    union cache_block_u *b = &(ucache->b[blk]);
638
639    /* add mtbls in blk to ftbl free list */
640    if (blk == 0)
641    {
642        start_mtbl = 1; /* skip blk 0 ent 0 which is ftbl */
643    }
644    else
645    {
646        start_mtbl = 0;
647    }
648    for (i = start_mtbl; i < MTBL_PER_BLOCK - 1; i++)
649    {
650        b->mtbl[i].free_list_blk = blk;
651        b->mtbl[i].free_list = i + 1;
652    }
653    b->mtbl[i].free_list_blk = NIL;
654    b->mtbl[i].free_list = NIL;
655    ftbl->free_mtbl_blk = blk;
656    ftbl->free_mtbl_ent = start_mtbl;   
657}
658
659/** Initializes a mtbl which is a hash table of memory entries.
660 * The mtbl will be located at the provided entry index within
661 * the provided block.
662 */
663static void init_memory_table(int blk, int ent)
664{
665    int i;
666    struct mem_table_s *mtbl = &(ucache->b[blk].mtbl[ent]);
667    mtbl->lru_first = NIL;
668    mtbl->lru_last = NIL;
669    mtbl->dirty_list = NIL;
670    mtbl->num_blocks = 0;
671    mtbl->ref_cnt = 0;
672    /* set up hash table */
673    for (i = 0; i < MEM_TABLE_HASH_MAX; i++)
674    {
675        mtbl->mem[i].item = NIL;
676        mtbl->mem[i].tag = NIL;
677        mtbl->mem[i].next = NIL;
678        mtbl->mem[i].lru_prev = NIL;
679        mtbl->mem[i].lru_next = NIL;
680    }
681    /* set up list of free hash table entries */
682    mtbl->free_list = MEM_TABLE_HASH_MAX;
683    for (i = MEM_TABLE_HASH_MAX; i < MEM_TABLE_ENTRY_COUNT - 1; i++)
684    {
685        mtbl->mem[i].next = i+1;
686    }
687    mtbl->mem[MEM_TABLE_ENTRY_COUNT - 1].next = NIL;
688}
689
690/** This function asks the file table if a free block is avaialable.
691 * If so, returns the block's index; otherwise, returns NIL.
692 */
693static uint16_t get_free_blk(void)
694{
695    struct file_table_s *ftbl = &(ucache->ftbl);
696    uint16_t free_blk = ftbl->free_blk;
697    if((int16_t)free_blk!=NIL)
698    {   
699        /* Use mtbl index zero since free_blks have no ititialized mem tables */
700        ftbl->free_blk = ucache->b[free_blk].mtbl[0].free_list;
701        return free_blk;
702    }
703    return NIL;
704
705}
706
707/** Accepts an index corresponding to a block that is put back on the file
708 * table free list.
709 */
710static void put_free_blk(int blk)
711{
712    if(DBG)fprintf(out, "freeing blk @ index = %d\n", blk);
713    struct file_table_s *ftbl = &(ucache->ftbl);
714    /* set the block's next value to the current head of the block free list */
715    ucache->b[blk].mtbl[0].free_list = ftbl->free_blk;
716    /* set this to NIL, since only used when mtbl is on mtbl free list */
717    ucache->b[blk].mtbl[0].free_list_blk = NIL;
718    /* blk is now the head of the ftbl blk free list */
719    ftbl->free_blk = blk;
720}
721
722/** Consults the file table to retrieve an index corresponding to a file entry
723 * If available, returns the file entry index, otherwise returns NIL.
724 */
725static int get_free_fent(void)
726{
727    if(DBG)fprintf(out, "trying to get free file entry...\n");
728    struct file_table_s *ftbl = &(ucache->ftbl);
729    uint16_t entry = ftbl->free_list;
730    if((int16_t)entry!=NIL)
731    {
732        ftbl->free_list = ftbl->file[entry].next;
733        ftbl->file[entry].next = NIL;
734        if(DBG)fprintf(out, "\tfree file entry index = %u\n", entry);
735        return entry;
736    }
737    else{
738        if(DBG)fprintf(out, "\tno free file entry...\n");
739        return NIL;
740    }
741}
742
743/** Places the file entry located at the provided index back on the file table's
744 * free file entry list. If the index is < FILE_TABLE_HASH_MAX, then set next
745 * to NIL since this index must remain the head of the linked list. Otherwise,
746 * set next to the current head of fent free list and set the free list head to
747 * the provided index.
748 */
749static void put_free_fent(int fent)
750{
751    if(DBG)fprintf(out, "freeing file entry = %d\n", fent);
752    struct file_table_s *ftbl = &(ucache->ftbl);
753    ftbl->file[fent].tag_handle = NIL;
754    ftbl->file[fent].tag_id = NIL;
755    if(fent<FILE_TABLE_HASH_MAX)
756    {
757        ftbl->file[fent].next = NIL;
758    }
759    else
760    {
761        /* Set next index to the current head of the free list */
762        ftbl->file[fent].next = ftbl->free_list;
763        /* Set fent index as the head of the free_list */
764        ftbl->free_list = fent;
765    }
766}
767
768/** Consults the provided mtbl's memory entry free list to get the index of the
769 * next free memory entry. Returns the index if one is available, otherwise
770 * returns NIL.
771 */
772static int get_free_ment(struct mem_table_s *mtbl)
773{
774    uint16_t ment = mtbl->free_list;
775    if((int16_t)ment!=NIL)
776    {
777        mtbl->free_list = mtbl->mem[ment].next;
778        mtbl->mem[ment].next = NIL;
779/*      mtbl->mem[ment].lru_prev = NIL;
780        mtbl->mem[ment].lru_next = NIL; */
781    }
782    return ment;
783}
784
785/** Puts the memory entry corresponding to the provided mtbl and entry index
786 * back on the mtbl's memory entry free list.
787 *
788 * If the entry index is < MEM_TABLE_HASH_MAX, then set next to NIL since this
789 * index must remain the head of the linked list. Otherwise, set next to the
790 * current head of ment free list and set the free list head to the provided
791 * index.
792 */
793static void put_free_ment(struct mem_table_s *mtbl, int ent)
794{
795    if(DBG)fprintf(out, "freeing memory entry = %d\n", ent);
796    /* Reset ment values */
797    mtbl->mem[ent].tag = NIL;
798    mtbl->mem[ent].item = NIL;
799    mtbl->mem[ent].dirty_next = NIL;
800    mtbl->mem[ent].lru_next = NIL;
801    mtbl->mem[ent].lru_prev = NIL;
802    if(ent<MEM_TABLE_HASH_MAX)
803    {
804        mtbl->mem[ent].next = NIL;
805    }
806    else{
807        /* Set next index to the current head of the free list */
808        mtbl->mem[ent].next = mtbl->free_list;
809        /* Update free list to include this entry */
810        mtbl->free_list = ent;
811    }
812}
813
814/** Perform a file lookup on the ucache using the provided fs_id and handle.
815 *
816 * Additional parameters (references) may used that will be set to values
817 * pertaining to mtbl and file entry location. If NULL is passed in place of
818 * these parameters, then they cannot be set.
819 *
820 * If the file is found, a pointer to the mtbl is returned and the parameter
821 * references set accordingly. Otherwise, NIL is returned.
822 */
823static struct mem_table_s *lookup_file(
824    uint32_t fs_id,
825    uint64_t handle,
826    uint32_t *file_mtbl_blk,
827    uint16_t *file_mtbl_ent,
828    uint16_t *file_ent_index,
829    uint16_t *file_ent_prev_index
830)
831{
832    if(DBG)fprintf(out, "performing lookup...\n");
833
834    /* Index into file hash table */
835    int index = handle % FILE_TABLE_HASH_MAX;
836    if(DBG)fprintf(out, "\thashed index: %d\n", index);
837
838    struct file_table_s *ftbl = &(ucache->ftbl);
839    struct file_ent_s *current = &(ftbl->file[index]);
840
841    /* previous, current, next fent index */
842    uint16_t p = NIL;
843    uint16_t c = index;
844    uint16_t n = current->next;
845
846    while(1)
847    {
848        if(DBG)fprintf(out, "\tp=%d\tc=%d\tn=%d\n", (int16_t)p, (int16_t)c,
849                                                                (int16_t)n);
850        if((current->tag_id == fs_id) && (current->tag_handle == handle))
851        {
852            if(DBG)fprintf(out, "\tFile located in chain\n");
853            /* If params !NULL, set their values */
854            if(file_mtbl_blk!=NULL && file_mtbl_ent!=NULL &&
855                file_ent_index!=NULL && file_ent_prev_index!=NULL)
856            {
857                    *file_mtbl_blk = current->mtbl_blk;
858                    *file_mtbl_ent = current->mtbl_ent;
859                    *file_ent_index = c;
860                    *file_ent_prev_index = p;
861            }
862            return (struct mem_table_s *)&(ucache->b[current->mtbl_blk].mtbl[
863                                                            current->mtbl_ent]);
864        }
865        /* No match yet */
866        else   
867        {
868            if((int16_t)current->next == NIL)
869            {
870                if(DBG)fprintf(out, "\tlookup failure: mtbl not found\n");
871                return (struct mem_table_s *)NIL;
872            }
873            else
874            {
875                current = &(ftbl->file[current->next]);
876                p=c; c=n; n=current->next;
877                if(DBG)fprintf(out,
878                    "\tIterating across the chain, next=%d\n",
879                    (int16_t)current->next);   
880            }
881
882        }
883    }   
884}
885
886/** Function that locates the next free mtbl.
887 * On success, Returns 1 and sets reference parameters to proper indexes.
888 * On failure, returns NIL;
889 */
890static int get_next_free_mtbl(uint32_t *free_mtbl_blk, uint16_t *free_mtbl_ent)
891{
892        struct file_table_s *ftbl = &(ucache->ftbl);
893
894        /* Get next free mtbl_blk and ent from ftbl */
895        *free_mtbl_blk = ftbl->free_mtbl_blk;
896        *free_mtbl_ent = ftbl->free_mtbl_ent;
897
898        /* Is free mtbl_blk available? */
899        if(((int32_t)*free_mtbl_blk == NIL) || ((int16_t)*free_mtbl_ent == NIL))
900        {
901            return NIL;
902        }
903
904        /* Update ftbl to contain new next free mtbl */
905        ftbl->free_mtbl_blk = ucache->b[*free_mtbl_blk].mtbl[*free_mtbl_ent].
906                                                                free_list_blk;
907        ftbl->free_mtbl_ent = ucache->b[*free_mtbl_blk].mtbl[*free_mtbl_ent].
908                                                                    free_list;
909
910        /* Set free info to NIL - NECESSARY? */
911        ucache->b[*free_mtbl_blk].mtbl[*free_mtbl_ent].free_list = NIL;
912        ucache->b[*free_mtbl_blk].mtbl[*free_mtbl_ent].free_list_blk = NIL;
913        return 1;
914}
915
916/** Removes all memory entries belonging to mtbl and places corresponding blocks
917 * back on the ftbl block free list, provided the mtbl->ref_cnt is 0. 
918 */
919static void remove_all_memory_entries(struct mem_table_s *mtbl)
920{
921    /* Don't do anything if this mtbl is referenced.*/
922    if(mtbl->ref_cnt != 0)
923    {
924        return;
925    }
926
927    int i;
928    for(i = 0; i < MEM_TABLE_HASH_MAX; i++)
929    {
930        if(DBG)fprintf(out, "\tremoving memory entry %d\n", i);
931        int j;
932        for(j = i;!ment_done(j); j = ment_next(mtbl, j))
933        {
934            /* Current Memory Entry */
935            struct mem_ent_s *ment = &(mtbl->mem[j]);
936            if(DBG)fprintf(out, "\t(tag, item)=(%lld, %d)\n",
937                    (int64_t)ment->tag,(int32_t)ment->item);
938            /*  Account for empty head of ment chain    */
939            if(((int64_t)ment->tag == NIL) || ((int32_t)ment->item == NIL))
940            {
941                break;
942            }
943            put_free_blk(ment->item);
944            put_free_ment(mtbl, j);
945        }
946    }
947}
948
949/** Places the provided mtbl back on the ftbl's mtbl free list provided it
950 * isn't currently referenced.
951 */
952static void put_free_mtbl(struct mem_table_s *mtbl, struct file_ent_s *file)
953{
954    /* Don't do anything if this mtbl is referenced.*/
955    if(mtbl->ref_cnt != 0)
956    {
957        return;
958    }
959
960    /* Remove mtbl */
961    mtbl->num_blocks = 0;   /* number of used blocks in this mtbl */
962    mtbl->lru_first = NIL;  /* index of first block on lru list */
963    mtbl->lru_last = NIL;   /* index of last block on lru list */
964    mtbl->dirty_list = NIL; /* index of first dirty block */
965    mtbl->ref_cnt = 0;      /* number of clients using this record */
966
967    /* Add mem_table back to free list */
968    /* Temporarily store copy of current head (the new next) */
969    uint32_t tmp_blk = ucache->ftbl.free_mtbl_blk;
970    uint16_t tmp_ent = ucache->ftbl.free_mtbl_ent;
971    /* newly free mtbl becomes new head of free mtbl list */
972    ucache->ftbl.free_mtbl_blk = file->mtbl_blk;
973    ucache->ftbl.free_mtbl_ent = file->mtbl_ent;
974    /* Point to the next free mtbl (the former head) */
975    mtbl->free_list_blk = tmp_blk;
976    mtbl->free_list = tmp_ent;
977}
978
979/** Evict the file entry at the provided index.
980 * On Success, returns 1. If file is currently referenced, do not evict and
981 * return 0.
982 */
983/*  evict the file @ index, must be less than FILE_TABLE_HASH_MAX   */
984static int evict_file(unsigned int index)
985{
986    if(DBG)fprintf(out, "evicting data @ index %d...\n", index);
987    struct file_ent_s *file = &(ucache->ftbl.file[index]);
988    struct mem_table_s *mtbl =
989        &(ucache->b[file->mtbl_blk].mtbl[file->mtbl_ent]);
990
991    if(mtbl->ref_cnt != 0){
992        return 0;
993    }
994
995    remove_all_memory_entries(mtbl);
996    put_free_mtbl(mtbl, file);
997
998    /* Prepare fent for its next occupant */
999    file->tag_handle = NIL;
1000    file->tag_id = NIL;
1001    file->mtbl_blk = NIL;   /* block index of this mtbl */
1002    file->mtbl_ent = NIL;   /* entry index of this mtbl */
1003    return 1;
1004}
1005
1006/** Insert information about file into ucache (no file data inserted)
1007 * Returns pointer to mtbl on success.
1008 *
1009 * Returns NIL if necessary data structures could not be aquired from the free
1010 * lists or through an eviction policy (meaning references are held).
1011 */
1012static struct mem_table_s *insert_file(uint32_t fs_id, uint64_t handle)
1013{
1014    if(DBG)fprintf(out, "trying to insert file...\n");
1015    struct file_table_s *ftbl = &(ucache->ftbl);
1016    struct file_ent_s *current;     /* Current ptr for iteration */
1017    uint16_t free_fent = NIL;       /* Index of next free fent */
1018    /* index into file hash table */
1019    unsigned int index = handle % FILE_TABLE_HASH_MAX;
1020    if(DBG)fprintf(out, "\thashed index: %u\n", index);
1021    current = &(ftbl->file[index]);
1022    /* Get free mtbl */
1023    uint32_t free_mtbl_blk = NIL;
1024    uint16_t free_mtbl_ent = NIL;
1025    /* Create free mtbls if none are available */
1026    if(get_next_free_mtbl(&free_mtbl_blk, &free_mtbl_ent) != 1)
1027    {   
1028        if((int16_t)ucache->ftbl.free_blk == NIL)
1029        {
1030            /* Evict a block from mtbl with most mem entries */
1031            struct mem_table_s *max_mtbl;
1032            locate_max_mtbl(&max_mtbl);
1033            if(DBG)fprintf(out, "\tget_free_mtbl returned NIL\n");
1034            if(DBG)fprintf(out, "\tevicting blk from max mtbl: has %d entries\n"
1035                                                        ,max_mtbl->num_blocks);
1036            evict_LRU(max_mtbl);
1037        }
1038        /* Intitialize remaining blocks' memory tables */
1039        if((int16_t)ucache->ftbl.free_blk != NIL)
1040        {
1041            if(DBG)fprintf(out, "\tadding memory tables to free block\n");
1042            add_free_mtbls(ucache->ftbl.free_blk);
1043            get_next_free_mtbl(&free_mtbl_blk, &free_mtbl_ent);
1044        }
1045    }
1046
1047    /* Insert at index, relocating data @ index if occupied */
1048    if(((int32_t)current->mtbl_blk != NIL) &&
1049        ((int16_t)current->mtbl_ent != NIL))
1050    {
1051        if(DBG)fprintf(out, "\tmust relocate head data\n");
1052        /* get free file entry and update ftbl */
1053        free_fent = get_free_fent();
1054        if((int16_t)free_fent != NIL)
1055        {
1056            /* copy data from 1 struct to the other */
1057            ftbl->file[free_fent] = *current;   
1058            /* point new head's "next" to former head */
1059            current->next = free_fent; 
1060        }
1061        else
1062        {   /* No free file entries available: policy? */
1063            if(DBG)fprintf(out, "\tno free file entries\n");
1064            /* Attempt to evict a file in a chain corresponding to the hashed
1065             * index into the ftbl.
1066             * Return NIL if it isn't possible.
1067             */
1068            /* Stop when the file has been evicted or end of chain reached */
1069            int file_evicted = evict_file(index);
1070            int i;
1071            for(i = index; !file_done(i) && (!file_evicted); i =
1072                                            file_next(ftbl,index))
1073            {
1074                i = ftbl->file[i].next;
1075                current = &(ftbl->file[i]);
1076                file_evicted = evict_file((unsigned int)i);
1077            }
1078            if(!file_evicted)
1079            {
1080                /* Could not get file entry */
1081                return (struct mem_table_s *)NIL;
1082            }
1083        }
1084    }
1085    else
1086    {
1087        if(DBG)fprintf(out, "\tno head data @ index\n");
1088    }
1089    /* Insert file data @ index */
1090    current->tag_id = fs_id;
1091    current->tag_handle = handle;
1092    /* Update fent with it's new mtbl: blk and ent */
1093    current->mtbl_blk = free_mtbl_blk;
1094    current->mtbl_ent = free_mtbl_ent;
1095    /* Initialize Memory Table */
1096    init_memory_table(free_mtbl_blk, free_mtbl_ent);
1097    if(DBG)fprintf(out, "\trecieved free memory table: 0X%X\n",
1098        (unsigned int)&(ucache->b[current->mtbl_blk].mtbl[current->mtbl_ent]));
1099    return &(ucache->b[current->mtbl_blk].mtbl[current->mtbl_ent]);
1100}
1101
1102/** Remove file entry and memory table of file identified by parameters
1103 * Returns 1 following removal
1104 * Returns NIL if file is referenced or if the file could not be located.
1105 */
1106static int remove_file(uint32_t fs_id, uint64_t handle)
1107{
1108    if(DBG)fprintf(out, "trying to remove file...\n");
1109    uint32_t file_mtbl_blk = NIL;
1110    uint16_t file_mtbl_ent = NIL;
1111    uint16_t file_ent_index = NIL;
1112    uint16_t file_ent_prev_index = NIL;
1113
1114    struct file_table_s *ftbl = &(ucache->ftbl);
1115    struct mem_table_s *mtbl = lookup_file(fs_id, handle, &file_mtbl_blk,
1116                    &file_mtbl_ent, &file_ent_index, &file_ent_prev_index);
1117
1118    if(mtbl->ref_cnt != 0)
1119    {
1120        if(DBG)fprintf(out, "\tremoval failure: ref_cnt==%d\n", mtbl->ref_cnt);
1121        return NIL;
1122    }
1123
1124    /* Verify we've recieved the necessary info */
1125    if(((int32_t)file_mtbl_blk == NIL) || ((int16_t)file_mtbl_ent == NIL))
1126    {
1127        if(DBG)fprintf(out, "\tremoval failure: no mtbl matching file\n");
1128        return NIL;
1129    }
1130
1131    /* Free the mtbl */
1132    put_free_mtbl(mtbl, &(ftbl->file[file_ent_index]));
1133
1134    /* Free the file entry */
1135    ftbl->file[file_ent_prev_index].next = ftbl->file[file_ent_index].next;
1136    put_free_fent(file_ent_index);
1137
1138    if(DBG)fprintf(out, "\tremoval sucessful\n");
1139    return(1);
1140}
1141
1142/** Lookup the memory location of a block of data in cache that is identified
1143 * by the mtbl and offset parameters.
1144 *
1145 * If located, returns a pointer to memory where the desired block of data is
1146 * stored. Otherwise, NIL is returned.
1147 *
1148 * Additional parameters (references) may be used that will be set to values
1149 * pertaining to the memory entry's location. If NULLs are passed in place of
1150 * these parameters, then they will not be set.
1151 */
1152static void *lookup_mem(struct mem_table_s *mtbl,
1153                    uint64_t offset,
1154                    uint32_t *item_index,
1155                    uint16_t *mem_ent_index,
1156                    uint16_t *mem_ent_prev_index)
1157{
1158    if(DBG)fprintf(out, "performing ment lookup...\n");
1159
1160    /* index into mem hash table */
1161    unsigned int index = offset % MEM_TABLE_HASH_MAX;
1162    if(DBG)fprintf(out, "\toffset: 0X%llX hashes to index: %u\n", offset,
1163                                                              index);
1164
1165    struct mem_ent_s *current = &(mtbl->mem[index]);
1166
1167    /* previous, current, next memory entry index in mtbl */
1168    int16_t p = NIL;
1169    int16_t c = index;
1170    int16_t n = current->next; 
1171
1172    while(1)
1173    {
1174        if(offset == current->tag)
1175        {
1176            if(DBG)fprintf(out, "\tmatch located: 0X%llX==0X%llX\n", offset,
1177                                                            current->tag);
1178
1179            /* If parameters !NULL, set their values */
1180            if((item_index != NULL) && (mem_ent_index != NULL) &&
1181                                    (mem_ent_prev_index != NULL))
1182            {
1183                    *item_index = current->item;
1184                    *mem_ent_index = c;
1185                    *mem_ent_prev_index = p;
1186            }
1187            return (void *)(&ucache->b[current->item].mblk);
1188        }
1189        else
1190        {
1191            if((int16_t)current->next == NIL)
1192            {
1193                if(DBG)fprintf(out, "\tmemory entry not found\n");
1194                return (struct mem_table_s *)NIL;
1195            }
1196            else
1197            {
1198                /* Iterate */
1199                current = &(mtbl->mem[current->next]);
1200                p = c;
1201                c = n;
1202                n = current->next;
1203            }
1204        }
1205    }
1206}
1207
1208/** Update the provided mtbl's LRU doubly-linked list by placing the memory
1209 * entry, identified by the provided index, at the head of the list (lru_first).
1210 *
1211 */
1212static void update_lru(struct mem_table_s *mtbl, uint16_t index)
1213{
1214            if(DBG)fprintf(out, "updating lru...\n");
1215            /* Do not place an entry with index < MEM_TABLE_HASH_MAX because
1216             * they must remain the heads of the hash table chains
1217             */
1218            if((int16_t)index < MEM_TABLE_HASH_MAX)
1219            {
1220                if(DBG)fprintf(out,
1221                        "\t%d<MEM_TABLE_HASH_MAX, not adding to LRU\n", index);
1222                return;
1223            }
1224 
1225            /* First memory entry used becomes the head and tail of the list */
1226            if(((int16_t)mtbl->lru_first == NIL) &&
1227                    ((int16_t)mtbl->lru_last == NIL))
1228            {
1229                if(DBG)fprintf(out, "\tsetting lru first and last\n");
1230                mtbl->lru_first = index;
1231                mtbl->lru_last = index;
1232                mtbl->mem[index].lru_prev = NIL;
1233                mtbl->mem[index].lru_next = NIL;
1234            }
1235            /* 2nd Memory Entry */
1236            else if(mtbl->lru_first == mtbl->lru_last)
1237            {
1238                /* Do nothing if this index is already the only entry */
1239                if(mtbl->lru_first == index)
1240                {
1241                    return;
1242                }
1243                else
1244                {   /* Must be 2nd unique memory entry */
1245                    if(DBG)fprintf(out, "\tinserting second record in LRU\n");
1246                    /* point tail.prev to new */
1247                    mtbl->mem[mtbl->lru_last].lru_prev = index;
1248                    /* point new.prev to NIL */ 
1249                    mtbl->mem[index].lru_prev = NIL;
1250                    /* point the new.next to the tail */     
1251                    mtbl->mem[index].lru_next = mtbl->lru_last;
1252                    /* point the head to the new */ 
1253                    mtbl->lru_first = index;                   
1254                }
1255            }
1256            /* 3rd+ Memory Entry */
1257            else
1258            {
1259                if(DBG)fprintf(out, "\trepairing previous LRU links and "
1260                                            "inserting record in LRU\n");
1261                /* repair links */ 
1262                if((int16_t)mtbl->mem[index].lru_prev != NIL)
1263                {
1264                    mtbl->mem[mtbl->mem[index].lru_prev].lru_next =
1265                        mtbl->mem[index].lru_next;
1266                }
1267                if((int16_t)mtbl->mem[index].lru_next != NIL)
1268                {
1269                    mtbl->mem[mtbl->mem[index].lru_next].lru_prev =     
1270                        mtbl->mem[index].lru_prev;
1271                }
1272                /* update nodes own link */
1273                mtbl->mem[mtbl->lru_first].lru_prev = index;
1274                mtbl->mem[index].lru_next = mtbl->lru_first;
1275                mtbl->mem[index].lru_prev = NIL;
1276                /* Finally, establish this entry as the first on LRU list */
1277                mtbl->lru_first = index;
1278            }
1279}
1280
1281/** Searches the ftbl for the mtbl with the most entries.
1282 * Returns the number of memory entries the max mtbl has. The double ptr
1283 * parameter is used to store a reference to the mtbl pointer with the most
1284 * memory entries.
1285 */
1286static int locate_max_mtbl(struct mem_table_s **mtbl)
1287{
1288    if(DBG)fprintf(out, "locating mtbl with most entries...\n");
1289    struct file_table_s *ftbl = &(ucache->ftbl);
1290    uint32_t index_of_max_blk = NIL;
1291    uint16_t index_of_max_ent = NIL;
1292    uint16_t value_of_max = 0;
1293    /* Iterate over file hash table indices */
1294    int i;
1295    for(i = 0; i < FILE_TABLE_HASH_MAX; i++)
1296    {
1297        if(DBG)fprintf(out, "\texamining ftbl index %d\n", i);
1298        /* Iterate over hash table chain */
1299        int j;
1300        for(j = i; !file_done(j); j = file_next(ftbl, j))
1301        {
1302            struct file_ent_s *fent = &(ftbl->file[j]);
1303            if(DBG)fprintf(out, "\t(blk, ent)=(%d, %d)\n", fent->mtbl_blk,
1304                                                    (int16_t)fent->mtbl_ent);
1305            //TODO: this might can be removed: test it
1306            if(((int32_t)fent->mtbl_blk == NIL) ||
1307                    ((int16_t)fent->mtbl_ent==NIL))
1308            {
1309                break;
1310            }
1311            /* Examine the mtbl's value of num_blocks to see if it's the
1312             * greatest.
1313             */
1314            struct mem_table_s *current_mtbl = &(ucache->b[fent->mtbl_blk].
1315                                                        mtbl[fent->mtbl_ent]);
1316            if(current_mtbl->num_blocks > value_of_max)
1317            {
1318                if(DBG)fprintf(out, "\tmax updated @ %d\n", j);
1319                *mtbl = current_mtbl; /* Set the parameter to this mtbl */
1320                index_of_max_blk = fent->mtbl_blk;
1321                index_of_max_ent = fent->mtbl_ent;
1322                value_of_max = (*mtbl)->num_blocks;
1323            }
1324        }
1325    }
1326    return value_of_max;
1327}
1328
1329/** Evicts the LRU memory entry from the tail (lru_last) of the provided
1330 * mtbl's LRU list.
1331 * Returns 1 on success; 0 on failure, meaning there was no lru
1332 */
1333static int evict_LRU(struct mem_table_s *mtbl)
1334{
1335    if(DBG)fprintf(out, "evicting LRU...\n");
1336    if(mtbl->num_blocks != 0)
1337    {
1338        remove_mem(mtbl, mtbl->mem[mtbl->lru_last].tag);
1339        return 1;
1340    }
1341    else
1342    {   /*  Worst Case  */
1343        if(DBG)fprintf(out, "\tno LRU on this mtbl\n");
1344        return 0;
1345    }
1346}
1347
1348
1349/** Used to obtain a block for storage of data identified by the offset
1350 * parameter and maintained in the mtbl at the memory entry identified by the
1351 * index parameter.
1352 *
1353 * If a free block could be aquired, returns the memory address of the block
1354 * just inserted. Otherwise, returns NIL.
1355 */
1356static void *set_item(struct mem_table_s *mtbl,
1357                    uint64_t offset,
1358                    uint16_t index)
1359{   
1360        int16_t free_blk = get_free_blk();
1361        /* No Free Blocks Available */
1362        if(free_blk == NIL)
1363        {
1364            if(DBG)fprintf(out, "\tget_free_blk returned NIL, attempting "
1365                                                      "removal of LRU\n");
1366            //TODO this probably wont work since we cannot evict a block that is current referenced
1367            evict_LRU(mtbl);
1368            free_blk = get_free_blk();
1369        }
1370       
1371        /* After Eviction Routine - No Free Blocks Available, Evict from mtbl
1372         * with the most memory entries (and therefore blocks)
1373         */
1374        if(free_blk == NIL)   
1375        {
1376            struct mem_table_s *max_mtbl;
1377            locate_max_mtbl(&max_mtbl);
1378            if(DBG)fprintf(out, "\tget_free_blk returned NIL, evicting a block "
1379                  "from max mtbl which has %d entries\n", max_mtbl->num_blocks);
1380            evict_LRU(max_mtbl);
1381            free_blk = get_free_blk();
1382        }
1383        /* A Free Block is Avaiable for Use */
1384        if(free_blk != NIL)
1385        {
1386            mtbl->num_blocks++;
1387            update_lru(mtbl, index);
1388            if(DBG)fprintf(out, "\tsuccessfully inserted memory entry @ blk: "
1389                                                  "%d\n", (int16_t) free_blk);
1390            /* set item to block number */
1391            mtbl->mem[index].tag = offset;
1392            mtbl->mem[index].item = free_blk;
1393            /* add block index to head of dirty list */
1394            if(DBG)fprintf(out, "\tadding memory entry to dirty list\n");
1395            mtbl->mem[index].dirty_next = mtbl->dirty_list;
1396            mtbl->dirty_list = index;
1397            /* Return the address of the block where data is stored */
1398            return (void *)&(ucache->b[free_blk]);
1399        }
1400    return (void *)(NIL);
1401}
1402
1403/** Requests a location in memory to place the data identified by the mtbl and
1404 * offset parameters. Also inserts the necessary info into the mtbl.
1405 *
1406 */
1407static void *insert_mem(struct mem_table_s *mtbl, uint64_t offset)
1408{
1409    if(DBG)fprintf(out, "trying to insert mem...\n");
1410
1411    /* Index into mem hash table */
1412    unsigned int index = offset % MEM_TABLE_HASH_MAX;
1413    if(DBG)fprintf(out, "\toffset: 0X%llX hashes to index: %u\n",
1414                                                  offset, index);
1415
1416    struct mem_ent_s *current = &(mtbl->mem[index]);
1417    /* Lookup first */
1418    void *returnValue = lookup_mem(mtbl, offset, NULL, NULL, NULL);
1419    if((int)returnValue != NIL)
1420    {
1421        if(DBG)fprintf(out, "\tblock for this offset already exists @ 0X%X",
1422                                                 (unsigned int)returnValue);
1423        /* Already exists in mtbl so just return a ptr to the blk */
1424        return returnValue;
1425    }
1426
1427    /* Entry doesn't exist, insertion required */
1428    if(DBG)fprintf(out, "\tlookup returned NIL\n");
1429    if((int64_t)mtbl->mem[index].tag != NIL)
1430    {
1431        /* If head occupied, need to get free ment */
1432        int mentIndex = get_free_ment(mtbl);
1433        if(mentIndex == NIL)
1434        {   /* No free ment available, so attempt eviction, and try again */
1435            if(DBG)fprintf(out, "\tno ment\n");
1436            evict_LRU(mtbl);
1437            mentIndex = get_free_ment(mtbl);
1438        }
1439        /* Procede with memory insertion if eviction was successful */
1440        if(mentIndex != NIL)
1441        {   
1442            if(DBG)fprintf(out, "\tfound free memory entry @ index = %d\n",
1443                                                                mentIndex);
1444            /* Insert directly after head of chain */
1445            uint16_t next_ment = current->next;
1446            current->next = mentIndex;
1447            mtbl->mem[mentIndex].next = next_ment;
1448            return set_item(mtbl, offset, mentIndex);   
1449        }
1450        /* Eviction Failed */
1451        else
1452        {
1453            return (void *)NULL;
1454        }
1455    }
1456    /* Head vacant. No need to iterate to next in chain, just use head */
1457    return set_item(mtbl, offset, index);
1458}
1459
1460/** Removes all table info regarding the block identified by the mtbl and
1461 * offset, provided the mtbl has a reference count of 0 and the entry exists.
1462 *
1463 * On success returns 1, on failure returns 0.
1464 *
1465 */
1466static int remove_mem(struct mem_table_s *mtbl, uint64_t offset)
1467{
1468    if(DBG)fprintf(out, "trying to remove memory entry...\n");
1469    /* Some Indices */
1470    uint32_t item_index = NIL;
1471    uint16_t mem_ent_index = NIL;
1472    uint16_t mem_ent_prev_index = NIL;
1473
1474
1475    /* Previous, Current, Next */
1476    uint16_t p = NIL;
1477    uint16_t c = NIL;
1478    uint16_t n = NIL;   
1479
1480    /* Check reference count */
1481    if(mtbl->ref_cnt != 0)
1482    {
1483        if(DBG)fprintf(out, "removal failure: ref_cnt==%d\n", mtbl->ref_cnt);
1484        return 0;
1485    }
1486    void *retValue = lookup_mem(mtbl, offset, &item_index, &mem_ent_index,
1487                                                     &mem_ent_prev_index);
1488    /* Verify we've recieved the necessary info */
1489    if((int)retValue == NIL)
1490    {
1491        if(DBG)fprintf(out, "\tremoval failure: memory entry not found "
1492                                                      "matching offset");
1493        return 0;
1494    }
1495    /* Remove from LRU */
1496    /* Update each of the adjacent nodes' link */
1497    if((int16_t)mtbl->mem[mem_ent_index].lru_prev != NIL)
1498    {
1499        mtbl->mem[mtbl->mem[mem_ent_index].lru_prev].lru_next =
1500                             mtbl->mem[mem_ent_index].lru_next;
1501    }
1502    if((int16_t)mtbl->mem[mem_ent_index].lru_next != NIL)
1503    {
1504        mtbl->mem[mtbl->mem[mem_ent_index].lru_next].lru_prev =
1505                             mtbl->mem[mem_ent_index].lru_prev;
1506    }
1507    if(mem_ent_index == mtbl->lru_first)
1508    {   
1509        /* Is node the head? */
1510        mtbl->lru_first = mtbl->mem[mem_ent_index].lru_next;   
1511    }
1512    if(mem_ent_index == mtbl->lru_last)
1513    {   
1514        /* Is node the tail? */
1515        mtbl->lru_last = mtbl->mem[mem_ent_index].lru_prev;
1516    }
1517    /* Remove from dirty list if Dirty */
1518    if(DBG)fprintf(out, "\tremoving from dirty list\n");
1519
1520    c = mtbl->dirty_list;
1521    n = mtbl->mem[c].dirty_next;
1522
1523    while(c != mem_ent_index)
1524    {
1525        p = c;
1526        c = n;
1527        n = mtbl->mem[c].dirty_next;
1528        if((int16_t)c == NIL)
1529        {
1530                break;
1531        }
1532    }
1533    if((int16_t)c != NIL)
1534    {   
1535        /* If memory entry was located on the dirty_list */
1536        mtbl->mem[p].dirty_next = mtbl->mem[c].dirty_next;
1537        mtbl->mem[c].dirty_next = NIL;
1538    }
1539    /* Add memory block back to free list */
1540    put_free_blk(item_index);
1541    /* Repair link */
1542    if((int16_t)mem_ent_prev_index != NIL)
1543    {
1544        mtbl->mem[mem_ent_prev_index].next = mtbl->mem[mem_ent_index].next;
1545    }
1546    /* Newly free mem entry becomes new head of free mem entry list if index
1547     * is less than hash table max
1548     */
1549    put_free_ment(mtbl, mem_ent_index);
1550    mtbl->num_blocks--;
1551    if(DBG)fprintf(out, "\tmemory entry removal sucessful\n");
1552    return 1;
1553}
1554
1555/*  The following two functions are provided for error checking purposes.
1556static void print_lru(struct mem_table_s *mtbl)
1557{
1558    if(DBG)fprintf(out, "\tprinting lru list:\n");
1559    if(DBG)fprintf(out, "\t\tlru: %d\n", (int16_t)mtbl->lru_last);
1560    uint16_t current= mtbl->lru_last;
1561    while((int16_t)current!=NIL)
1562    {
1563        current = mtbl->mem[current].lru_prev;
1564        if(DBG)fprintf(out, "\t\tprev: %d\n", (int16_t)current);
1565    }
1566}
1567
1568static void print_dirty(struct mem_table_s *mtbl)
1569{
1570    if(DBG)fprintf(out, "\tprinting dirty list:\n");
1571    if(DBG)fprintf(out, "\t\tdirty_list head: %d\n",\
1572        (int16_t)mtbl->dirty_list);
1573    uint16_t current= mtbl->dirty_list;
1574    while((int16_t)current!=NIL)
1575    {
1576        if(DBG)fprintf(out, "\t\tcurrent: %d\tnext: %d\n",
1577            (int16_t)current,
1578            (int16_t)mtbl->mem[current].dirty_next);
1579        current = mtbl->mem[current].dirty_next;
1580    }
1581}
1582 */
1583
1584/*  End of Internal Only Functions    */
1585
1586/*
1587 * Local variables:
1588 *  c-indent-level: 4
1589 *  c-basic-offset: 4
1590 * End:
1591 *
1592 * vim: ts=8 sts=4 sw=4 expandtab
1593 */
Note: See TracBrowser for help on using the browser.