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