cache.c

   1 /*
   2  * A simple LRU cache implemention. Even the fstk is a user-space program,
   3  * but we really do need a cache algorithm to make fstk more effective.
   4  *
   5  * This file is from Syslinux_project/core/cache.c. This file can
   6  * be redistributed under the terms of the GNU Public License.
   7  */
   8
   9 #include <stdio.h>
  10 #include <string.h>
  11
  12 #include "tfs.h"
  13 #include "cache.h"
  14
  15
  16 /* The cache data, we just make it be 32K, and it's enough for us */
  17 #define CACHE_SIZE      (32 << 10)
  18
  19 static char cache_data[CACHE_SIZE];
  20
  21 #define MAX_CACHE_ENTRIES 64     /* assume we have a block size as 512 */
  22 static struct cache_struct cache_head;
  23 static struct cache_struct cache[MAX_CACHE_ENTRIES];
  24 static int cache_entries = 0;
  25
  26 /*
  27  * Initialize the cache data structres
  28  */
  29 void cache_init(struct tfs_sb_info *sbi)
  30 {
  31         struct cache_struct *prev, *cur;
  32         char *data = cache_data;
  33         int i;
  34
  35         cache_entries = CACHE_SIZE >> sbi->s_block_shift;
  36         if (cache_entries > MAX_CACHE_ENTRIES)
  37                 cache_entries = MAX_CACHE_ENTRIES;
  38
  39         cache_head.prev = &cache[cache_entries-1];
  40         cache_head.prev->next = &cache_head;
  41         prev = &cache_head;
  42
  43         for (i = 0; i < cache_entries; i++) {
  44                 cur = &cache[i];
  45                 cur->block   = 0;
  46                 cur->prev    = prev;
  47                 prev->next   = cur;
  48                 cur->data    = data;
  49                 data += sbi->s_block_size;
  50                 prev = cur++;
  51         }
  52 }
  53
  54
  55 /*
  56  * Check for a particular BLOCK in the block cache,
  57  * and if it is already there, just do nothing and return;
  58  * otherwise load it and updata the relative cache
  59  * structre with data pointer.
  60  */
  61 struct cache_struct* get_cache_block(struct tfs_sb_info *sbi, uint32_t block)
  62 {
  63         struct cache_struct *head = &cache_head;
  64         struct cache_struct *last = head->prev;
  65         /* let's find it from the end, 'cause the endest is the freshest */
  66         struct cache_struct *cs = head->prev;
  67         int i;
  68
  69         if (!block) {
  70                 printf("ERR: we got a ZERO block number that's not we want!\n");
  71                 return NULL;
  72         }
  73
  74         /* it's aleardy the freshest, so nothing we need do , just return it */
  75         if (cs->block == block)
  76                 goto out;
  77
  78         for (i = 0; i < cache_entries; i ++) {
  79                 if (cs->block == block)
  80                         break;
  81                 else
  82                         cs = cs->prev;
  83         }
  84
  85         /* missed, so we need to load it */
  86         if (i == cache_entries) {
  87                 /* store it at the head of real cache */
  88                 cs = head->next;
  89                 cs->block = block;
  90                 tfs_bread(sbi, block, cs->data);
  91         }
  92
  93         /* remove cs from current position in list */
  94         cs->prev->next = cs->next;
  95         cs->next->prev = cs->prev;
  96
  97         /* add to just before head node */
  98         last->next = cs;
  99         cs->prev = last;
 100         head->prev = cs;
 101         cs->next = head;
 102 out:
 103         return cs;
 104 }
 105
 106
 107 /**
 108  * Just print the sector, and according the LRU algorithm,
 109  * Left most value is the most least secotr, and Right most
 110  * value is the most Recent sector. I see it's a Left Right Used
 111  * (LRU) algorithm; Just kidding:)
 112  */
 113 void print_cache(void)
 114 {
 115         int i = 0;
 116         struct cache_struct *cs = &cache_head;
 117         for (; i < cache_entries; i++) {
 118                 cs = cs->next;
 119                 printf("%d(%p) \n", cs->block, cs->data);
 120         }
 121
 122         printf("\n");
 123 }