workbench/fs/fat/cache.c

   1 /*
   2     Copyright © 2010, The AROS Development Team. All rights reserved.
   3     $Id$
   4
   5     Disk cache.
   6  */
   7
   8 /*
   9  * This is an LRU copyback cache.
  10  *
  11  * The cache consists of a fixed number of cache blocks, each of which can
  12  * hold a contiguous range of disk blocks (each range is of a fixed
  13  * length). Each range is addressed by its base block number, calculated by
  14  * applying a mask to the requested block number.
  15  *
  16  * Each cache block contains two Exec list nodes, so it can be part of two
  17  * lists simultaneously. The first node links a block into a hash table
  18  * list, while the second links it into either the free list or the dirty
  19  * list. Initially, all cache blocks are present in the free list, and are
  20  * absent from the hash table.
  21  *
  22  * When a disk block is requested by the client, the range that contains
  23  * that disk block is calculated. The range is then sought by looking up
  24  * the hash table. Each position in the hash table holds a list containing
  25  * all cache blocks (henceforth referred to as a block: individual disk
  26  * blocks are not used internally) that map to that hash location. Each
  27  * list in the hash table is typically very short, so look-up time is
  28  * quick.
  29  *
  30  * If the requested range is not in the hash table, a cache block is
  31  * removed from the head of the free list and from any hash table list it
  32  * is in, and used to read the appropriate range from disk. This block is
  33  * then added to the hash table at its new location.
  34  *
  35  * Two elements are returned to the client when a requested block is found:
  36  * an opaque cache block handle, and a pointer to the data buffer.
  37  *
  38  * When a range is freed, it remains in the hash table so that it can be
  39  * found quickly if needed again. Unless dirty, it is also added to the
  40  * tail of the free list through its second list node. The block then
  41  * remains in the hash table until reused for a different range.
  42  *
  43  * If a disk block is marked dirty by the client, the entire containing
  44  * range is marked dirty and added to the tail of the dirty list through
  45  * the cache block's second node. The dirty list is flushed periodically
  46  * (currently once per second), and additionally whenever the free list
  47  * becomes empty.
  48  *
  49  */
  50
  51 #include <dos/dos.h>
  52
  53 #include <proto/exec.h>
  54 #include <proto/dos.h>
  55 #include <clib/alib_protos.h>
  56
  57 #include "cache.h"
  58 #include "fat_fs.h"
  59 #include "fat_protos.h"
  60
  61 #define RANGE_SHIFT 5
  62 #define RANGE_SIZE (1 << RANGE_SHIFT)
  63 #define RANGE_MASK (RANGE_SIZE - 1)
  64
  65 #define NODE2(A) \
  66    ((struct BlockRange *)(((A) != NULL) ? \
  67    (((BYTE *)(A)) - (IPTR)&((struct BlockRange *)NULL)->node2) : NULL))
  68
  69
  70 APTR Cache_CreateCache(ULONG hash_size, ULONG block_count, ULONG block_size)
  71 {
  72     struct Cache *c;
  73     ULONG i;
  74     BOOL success = TRUE;
  75     struct BlockRange *b;
  76
  77     /* Allocate cache structure */
  78
  79     if((c = AllocVec(sizeof(struct Cache), MEMF_PUBLIC | MEMF_CLEAR)) == NULL)
  80         success = FALSE;
  81
  82     if(success)
  83     {
  84         c->block_size = block_size;
  85         c->block_count = block_count;
  86         c->hash_size = hash_size;
  87
  88         /* Allocate hash table */
  89
  90         c->hash_table = AllocVec(sizeof(struct MinList) * hash_size,
  91             MEMF_PUBLIC | MEMF_CLEAR);
  92         if(c->hash_table == NULL)
  93             success = FALSE;
  94
  95         /* Initialise each hash location's list, and free and dirty lists */
  96
  97         for(i = 0; i < hash_size && success; i++)
  98             NewList((struct List *)&c->hash_table[i]);
  99         NewList((struct List *)&c->free_list);
 100         NewList((struct List *)&c->dirty_list);
 101
 102         /* Allocate cache blocks and add them to the free list */
 103
 104         c->blocks = AllocVec(sizeof(APTR) * block_count,
 105             MEMF_PUBLIC | MEMF_CLEAR);
 106         if(c == NULL)
 107             success = FALSE;
 108
 109         for(i = 0; i < block_count && success; i++)
 110         {
 111             b = AllocVec(sizeof(struct BlockRange)
 112                 + (c->block_size << RANGE_SHIFT), MEMF_PUBLIC);
 113             b->use_count = 0;
 114             b->state = BS_EMPTY;
 115             b->num = 0;
 116             b->data = (UBYTE *)b + sizeof(struct BlockRange);
 117
 118             if(b != NULL)
 119                 c->blocks[i] = b;
 120             else
 121                 success = FALSE;
 122
 123             if(success)
 124                 AddTail((struct List *)&c->free_list,
 125                     (struct Node *)&b->node2);
 126         }
 127     }
 128
 129     if(!success)
 130     {
 131         Cache_DestroyCache(c);
 132         c = NULL;
 133     }
 134
 135     return c;
 136 }
 137
 138
 139 VOID Cache_DestroyCache(APTR cache)
 140 {
 141     struct Cache *c = cache;
 142     ULONG i;
 143
 144     Cache_Flush(c);
 145
 146     for(i = 0; i < c->block_count; i++)
 147         FreeVec(c->blocks[i]);
 148     FreeVec(c->blocks);
 149     FreeVec(c->hash_table);
 150     FreeVec(c);
 151 }
 152
 153
 154 APTR Cache_GetBlock(APTR cache, ULONG blockNum, UBYTE **data)
 155 {
 156     struct Cache *c = cache;
 157     struct BlockRange *b = NULL, *b2;
 158     ULONG error = 0, data_offset;
 159     struct MinList *l =
 160         &c->hash_table[(blockNum >> RANGE_SHIFT) & (c->hash_size - 1)];
 161     struct MinNode *n;
 162
 163     /* Change block number to the start block of a range and get byte offset
 164      * within range */
 165
 166     data_offset = (blockNum - (blockNum & ~RANGE_MASK)) * c->block_size;
 167     blockNum &= ~RANGE_MASK;
 168
 169     /* Check existing valid blocks first */
 170
 171     ForeachNode(l, b2)
 172     {
 173         if(b2->num == blockNum)
 174             b = b2;
 175     }
 176
 177     if(b != NULL)
 178     {
 179         /* Block found, so increment its usage count and remove it from the
 180          * free list */
 181
 182         if(b->use_count++ == 0)
 183         {
 184             if(b->state != BS_DIRTY)
 185                 Remove((struct Node *)&b->node2);
 186         }
 187     }
 188     else
 189     {
 190         /* Get a free buffer to read block from disk */
 191
 192         n = (struct MinNode *)RemHead((struct List *)&c->free_list);
 193         if(n == NULL)
 194         {
 195             /* No free blocks, so flush dirty list to try and free up some
 196              * more blocks, then try again */
 197
 198             Cache_Flush(c);
 199             n = (struct MinNode *)RemHead((struct List *)&c->free_list);
 200         }
 201
 202         if(n != NULL)
 203         {
 204             b = (struct BlockRange *)NODE2(n);
 205
 206             /* Read the block from disk */
 207
 208             if((error = AccessDisk(FALSE, blockNum, RANGE_SIZE,
 209                 c->block_size, b->data)) == 0)
 210             {
 211                 /* Remove block from its old position in the hash */
 212
 213                 if(b->state == BS_VALID)
 214                     Remove((struct Node *)b);
 215
 216                 /* Add it to the hash at the new location */
 217
 218                 AddHead((struct List *)l, (struct Node *)&b->node1);
 219                 b->num = blockNum;
 220                 b->state = BS_VALID;
 221                 b->use_count = 1;
 222             }
 223             else
 224             {
 225                 /* Read failed, so put the block back on the free list */
 226
 227                 b->state = BS_EMPTY;
 228                 AddHead((struct List *)&c->free_list,
 229                     (struct Node *)&b->node2);
 230                 b = NULL;
 231             }
 232         }
 233         else
 234             error = ERROR_NO_FREE_STORE;
 235     }
 236
 237     /* Set data pointer and error, and return cache block handle */
 238
 239     *data = b->data + data_offset;
 240     SetIoErr(error);
 241
 242     return b;
 243 }
 244
 245
 246 VOID Cache_FreeBlock(APTR cache, APTR block)
 247 {
 248     struct Cache *c = cache;
 249     struct BlockRange *b = block;
 250
 251     /* Decrement usage count */
 252
 253     b->use_count--;
 254
 255     /* Put an unused block at the end of the free list unless it's dirty */
 256
 257     if(b->use_count == 0 && b->state != BS_DIRTY)
 258         AddTail((struct List *)&c->free_list, (struct Node *)&b->node2);
 259
 260     return;
 261 }
 262
 263
 264 VOID Cache_MarkBlockDirty(APTR cache, APTR block)
 265 {
 266     struct Cache *c = cache;
 267     struct BlockRange *b = block;
 268
 269     if(b->state != BS_DIRTY)
 270     {
 271         b->state = BS_DIRTY;
 272         AddTail((struct List *)&c->dirty_list, (struct Node *)&b->node2);
 273     }
 274
 275     return;
 276 }
 277
 278
 279 BOOL Cache_Flush(APTR cache)
 280 {
 281     struct Cache *c = cache;
 282     ULONG error = 0;
 283     struct MinNode *n;
 284     struct BlockRange *b;
 285
 286     while((n = (struct MinNode *)RemHead((struct List *)&c->dirty_list))
 287         != NULL && error == 0)
 288     {
 289         /* Write dirty block range to disk */
 290
 291         b = NODE2(n);
 292         error = AccessDisk(TRUE, b->num, RANGE_SIZE, c->block_size, b->data);
 293
 294         /* Transfer block range to free list if unused, or put back on dirty
 295          * list upon an error */
 296
 297         if(error == 0)
 298         {
 299             b->state = BS_VALID;
 300             if(b->use_count == 0)
 301                 AddTail((struct List *)&c->free_list, (struct Node *)&b->node2);
 302         }
 303         else
 304             AddHead((struct List *)&c->dirty_list, (struct Node *)&b->node2);
 305     }
 306
 307     SetIoErr(error);
 308     return error == 0;
 309 }
 310