source/cache.c

   1 /*
   2  cache.c
   3  The cache is not visible to the user. It should be flushed
   4  when any file is closed or changes are made to the filesystem.
   5
   6  This cache implements a least-used-page replacement policy. This will
   7  distribute sectors evenly over the pages, so if less than the maximum
   8  pages are used at once, they should all eventually remain in the cache.
   9  This also has the benefit of throwing out old sectors, so as not to keep
  10  too many stale pages around.
  11
  12  Copyright (c) 2006 Michael "Chishm" Chisholm
  13
  14  Redistribution and use in source and binary forms, with or without modification,
  15  are permitted provided that the following conditions are met:
  16
  17   1. Redistributions of source code must retain the above copyright notice,
  18      this list of conditions and the following disclaimer.
  19   2. Redistributions in binary form must reproduce the above copyright notice,
  20      this list of conditions and the following disclaimer in the documentation and/or
  21      other materials provided with the distribution.
  22   3. The name of the author may not be used to endorse or promote products derived
  23      from this software without specific prior written permission.
  24
  25  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
  26  WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
  27  AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE
  28  LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  30  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  31  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  32  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
  33  EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  34 */
  35
  36 #include <string.h>
  37 #include <limits.h>
  38
  39 #include "common.h"
  40 #include "cache.h"
  41 #include "disc.h"
  42
  43 #include "mem_allocate.h"
  44 #include "bit_ops.h"
  45 #include "file_allocation_table.h"
  46
  47 #define CACHE_FREE UINT_MAX
  48
  49 CACHE* _FAT_cache_constructor (unsigned int numberOfPages, unsigned int sectorsPerPage, const DISC_INTERFACE* discInterface) {
  50         CACHE* cache;
  51         unsigned int i;
  52         CACHE_ENTRY* cacheEntries;
  53
  54         if (numberOfPages < 2) {
  55                 numberOfPages = 2;
  56         }
  57
  58         if (sectorsPerPage < 8) {
  59                 sectorsPerPage = 8;
  60         }
  61
  62         cache = (CACHE*) _FAT_mem_allocate (sizeof(CACHE));
  63         if (cache == NULL) {
  64                 return NULL;
  65         }
  66
  67         cache->disc = discInterface;
  68         cache->numberOfPages = numberOfPages;
  69         cache->sectorsPerPage = sectorsPerPage;
  70
  71
  72         cacheEntries = (CACHE_ENTRY*) _FAT_mem_allocate ( sizeof(CACHE_ENTRY) * numberOfPages);
  73         if (cacheEntries == NULL) {
  74                 _FAT_mem_free (cache);
  75                 return NULL;
  76         }
  77
  78         for (i = 0; i < numberOfPages; i++) {
  79                 cacheEntries[i].sector = CACHE_FREE;
  80                 cacheEntries[i].count = 0;
  81                 cacheEntries[i].last_access = 0;
  82                 cacheEntries[i].dirty = false;
  83                 cacheEntries[i].cache = (uint8_t*) _FAT_mem_align ( sectorsPerPage * BYTES_PER_READ );
  84         }
  85
  86         cache->cacheEntries = cacheEntries;
  87
  88         return cache;
  89 }
  90
  91 void _FAT_cache_destructor (CACHE* cache) {
  92         unsigned int i;
  93         // Clear out cache before destroying it
  94         _FAT_cache_flush(cache);
  95
  96         // Free memory in reverse allocation order
  97         for (i = 0; i < cache->numberOfPages; i++) {
  98                 _FAT_mem_free (cache->cacheEntries[i].cache);
  99         }
 100         _FAT_mem_free (cache->cacheEntries);
 101         _FAT_mem_free (cache);
 102 }
 103
 104 static u32 accessCounter = 0;
 105
 106 static u32 accessTime(){
 107         accessCounter++;
 108         return accessCounter;
 109 }
 110
 111 /*
 112 Retrieve a sector's page from the cache. If it is not found in the cache,
 113 load it into the cache and return the page it was loaded to.
 114 Return CACHE_FREE on error.
 115 */
 116 static unsigned int _FAT_cache_getSector (CACHE* cache, sec_t sector, void* buffer) {
 117         unsigned int i;
 118         CACHE_ENTRY* cacheEntries = cache->cacheEntries;
 119         unsigned int numberOfPages = cache->numberOfPages;
 120         unsigned int sectorsPerPage = cache->sectorsPerPage;
 121
 122         unsigned int oldUsed = 0;
 123         unsigned int oldAccess = cacheEntries[0].last_access;
 124
 125         for (i = 0; i < numberOfPages ; i++) {
 126                 if ( sector>=cacheEntries[i].sector && sector < cacheEntries[i].sector+cacheEntries[i].count) {
 127                         cacheEntries[i].last_access = accessTime();
 128                         memcpy(buffer, cacheEntries[i].cache + ((sector - cacheEntries[i].sector)*BYTES_PER_READ), BYTES_PER_READ);
 129                         return true;
 130                 }
 131                 // While searching for the desired sector, also search for the least recently used page
 132                 if ( (cacheEntries[i].sector == CACHE_FREE) || (cacheEntries[i].last_access < oldAccess) ) {
 133                         oldUsed = i;
 134                         oldAccess = cacheEntries[i].last_access;
 135                 }
 136         }
 137
 138
 139         // If it didn't, replace the least used cache page with the desired sector
 140         if ((cacheEntries[oldUsed].sector != CACHE_FREE) && (cacheEntries[oldUsed].dirty == true)) {
 141                 // Write the page back to disc if it has been written to
 142                 if (!_FAT_disc_writeSectors (cache->disc, cacheEntries[oldUsed].sector, cacheEntries[oldUsed].count, cacheEntries[oldUsed].cache)) {
 143                         return false;
 144                 }
 145                 cacheEntries[oldUsed].dirty = false;
 146         }
 147
 148         // Load the new sector into the cache
 149         if (!_FAT_disc_readSectors (cache->disc, sector, sectorsPerPage, cacheEntries[oldUsed].cache)) {
 150                 return false;
 151         }
 152         cacheEntries[oldUsed].sector = sector;
 153         cacheEntries[oldUsed].count = sectorsPerPage;
 154         // Increment the usage count, don't reset it
 155         // This creates a paging policy of least recently used PAGE, not sector
 156         cacheEntries[oldUsed].last_access = accessTime();
 157         memcpy(buffer, cacheEntries[oldUsed].cache, BYTES_PER_READ);
 158         return true;
 159 }
 160
 161 bool _FAT_cache_getSectors (CACHE* cache, sec_t sector, sec_t numSectors, void* buffer) {
 162         unsigned int i;
 163         CACHE_ENTRY* cacheEntries = cache->cacheEntries;
 164         unsigned int numberOfPages = cache->numberOfPages;
 165         sec_t sec;
 166         sec_t secs_to_read;
 167
 168         unsigned int oldUsed = 0;
 169         unsigned int oldAccess = cacheEntries[0].last_access;
 170
 171         while(numSectors>0)
 172         {
 173                 i=0;
 174                 while (i < numberOfPages ) {
 175                         if ( sector>=cacheEntries[i].sector && sector < cacheEntries[i].sector+cacheEntries[i].count) {
 176                                 sec=sector-cacheEntries[i].sector;
 177                                 secs_to_read=cacheEntries[i].count-sec;
 178                                 if(secs_to_read>numSectors)secs_to_read=numSectors;
 179                                 memcpy(buffer,cacheEntries[i].cache + (sec*BYTES_PER_READ), secs_to_read*BYTES_PER_READ);
 180                                 cacheEntries[i].last_access = accessTime();
 181                                 numSectors=numSectors-secs_to_read;
 182                                 if(numSectors==0) return true;
 183                                 buffer+=secs_to_read*BYTES_PER_READ;
 184                                 sector+=secs_to_read;
 185                                 i=-1; // recheck all pages again
 186                                 oldUsed = 0;
 187                                 oldAccess = cacheEntries[0].last_access;
 188
 189                         }
 190                         else // While searching for the desired sector, also search for the least recently used page
 191                         if ( (cacheEntries[i].sector == CACHE_FREE) || (cacheEntries[i].last_access < oldAccess) ) {
 192                                 oldUsed = i;
 193                                 oldAccess = cacheEntries[i].last_access;
 194                         }
 195                         i++;
 196             }
 197                 // If it didn't, replace the least recently used cache page with the desired sector
 198                 if ((cacheEntries[oldUsed].sector != CACHE_FREE) && (cacheEntries[oldUsed].dirty == true)) {
 199                         // Write the page back to disc if it has been written to
 200                         if (!_FAT_disc_writeSectors (cache->disc, cacheEntries[oldUsed].sector, cacheEntries[oldUsed].count, cacheEntries[oldUsed].cache)) {
 201                                 return false;
 202                         }
 203                         cacheEntries[oldUsed].dirty = false;
 204                 }
 205
 206                 cacheEntries[oldUsed].sector = sector;
 207                 cacheEntries[oldUsed].count = cache->sectorsPerPage;
 208
 209                 if (!_FAT_disc_readSectors (cache->disc, sector, cacheEntries[oldUsed].count,  cacheEntries[oldUsed].cache)) {
 210                         return false;
 211                 }
 212
 213                 // Increment the usage count, don't reset it
 214                 // This creates a paging policy of least used PAGE, not sector
 215                 cacheEntries[oldUsed].last_access = accessTime();
 216
 217                 sec=0;
 218                 secs_to_read=cacheEntries[oldUsed].count-sec;
 219                 if(secs_to_read>numSectors)secs_to_read=numSectors;
 220                 memcpy(buffer,cacheEntries[oldUsed].cache + (sec*BYTES_PER_READ), secs_to_read*BYTES_PER_READ);
 221                 numSectors=numSectors-secs_to_read;
 222                 if(numSectors==0) return true;
 223                 buffer+=secs_to_read*BYTES_PER_READ;
 224
 225                 sector+=secs_to_read;
 226                 oldUsed = 0;
 227                 oldAccess = cacheEntries[0].last_access;
 228         }
 229         return false;
 230 }
 231
 232 /*
 233 Reads some data from a cache page, determined by the sector number
 234 */
 235 bool _FAT_cache_readPartialSector (CACHE* cache, void* buffer, sec_t sector, unsigned int offset, size_t size) {
 236         void* sec;
 237
 238         if (offset + size > BYTES_PER_READ) {
 239                 return false;
 240         }
 241         sec = (void*) _FAT_mem_align ( BYTES_PER_READ );
 242         if(sec == NULL) return false;
 243         if(! _FAT_cache_getSector(cache, sector, sec) ) {
 244                 _FAT_mem_free(sec);
 245                 return false;
 246         }
 247         memcpy(buffer, sec + offset, size);
 248         _FAT_mem_free(sec);
 249         return true;
 250 }
 251
 252 bool _FAT_cache_readLittleEndianValue (CACHE* cache, uint32_t *value, sec_t sector, unsigned int offset, int num_bytes) {
 253   uint8_t buf[4];
 254   if (!_FAT_cache_readPartialSector(cache, buf, sector, offset, num_bytes)) return false;
 255
 256   switch(num_bytes) {
 257   case 1: *value = buf[0]; break;
 258   case 2: *value = u8array_to_u16(buf,0); break;
 259   case 4: *value = u8array_to_u32(buf,0); break;
 260   default: return false;
 261   }
 262   return true;
 263 }
 264
 265 /*
 266 Writes some data to a cache page, making sure it is loaded into memory first.
 267 */
 268 bool _FAT_cache_writePartialSector (CACHE* cache, const void* buffer, sec_t sector, unsigned int offset, size_t size) {
 269         unsigned int i;
 270         void* sec;
 271         CACHE_ENTRY* cacheEntries = cache->cacheEntries;
 272         unsigned int numberOfPages = cache->numberOfPages;
 273
 274         if (offset + size > BYTES_PER_READ) {
 275                 return false;
 276         }
 277
 278         //To be sure sector is in cache
 279         sec = (void*) _FAT_mem_align ( BYTES_PER_READ );
 280         if(sec == NULL) return false;
 281         if(! _FAT_cache_getSector(cache, sector, sec) ) {
 282                 _FAT_mem_free(sec);
 283                 return false;
 284         }
 285         _FAT_mem_free(sec);
 286
 287         //Find where sector is and write
 288         for (i = 0; i < numberOfPages ; i++) {
 289                 if ( sector>=cacheEntries[i].sector && sector < cacheEntries[i].sector+cacheEntries[i].count) {
 290                         cacheEntries[i].last_access = accessTime();
 291                         memcpy (cacheEntries[i].cache + ((sector-cacheEntries[i].sector)*BYTES_PER_READ) + offset, buffer, size);
 292                         cache->cacheEntries[i].dirty = true;
 293                         return true;
 294             }
 295         }
 296         return false;
 297 }
 298
 299 bool _FAT_cache_writeLittleEndianValue (CACHE* cache, const uint32_t value, sec_t sector, unsigned int offset, int size) {
 300   uint8_t buf[4] = {0, 0, 0, 0};
 301
 302   switch(size) {
 303   case 1: buf[0] = value; break;
 304   case 2: u16_to_u8array(buf, 0, value); break;
 305   case 4: u32_to_u8array(buf, 0, value); break;
 306   default: return false;
 307   }
 308
 309   return _FAT_cache_writePartialSector(cache, buf, sector, offset, size);
 310 }
 311
 312 /*
 313 Writes some data to a cache page, zeroing out the page first
 314 */
 315 bool _FAT_cache_eraseWritePartialSector (CACHE* cache, const void* buffer, sec_t sector, unsigned int offset, size_t size) {
 316         unsigned int i;
 317         void* sec;
 318         CACHE_ENTRY* cacheEntries = cache->cacheEntries;
 319         unsigned int numberOfPages = cache->numberOfPages;
 320
 321         if (offset + size > BYTES_PER_READ) {
 322                 return false;
 323         }
 324
 325         //To be sure sector is in cache
 326         sec = (void*) _FAT_mem_align ( BYTES_PER_READ );
 327         if(sec == NULL) return false;
 328         if(! _FAT_cache_getSector(cache, sector, sec) ) {
 329                 _FAT_mem_free(sec);
 330                 return false;
 331         }
 332         _FAT_mem_free(sec);
 333
 334         //Find where sector is and write
 335         for (i = 0; i < numberOfPages ; i++) {
 336                 if ( sector>=cacheEntries[i].sector && sector < cacheEntries[i].sector+cacheEntries[i].count) {
 337                         cacheEntries[i].last_access = accessTime();
 338                         memset (cacheEntries[i].cache + ((sector-cacheEntries[i].sector)*BYTES_PER_READ), 0, BYTES_PER_READ);
 339                         memcpy (cacheEntries[i].cache + ((sector-cacheEntries[i].sector)*BYTES_PER_READ) + offset, buffer, size);
 340                         cache->cacheEntries[i].dirty = true;
 341                         return true;
 342             }
 343         }
 344         return false;
 345 }
 346
 347 bool _FAT_cache_writeSectors (CACHE* cache, sec_t sector, sec_t numSectors, const void* buffer) {
 348         unsigned int i;
 349         CACHE_ENTRY* cacheEntries = cache->cacheEntries;
 350         unsigned int numberOfPages = cache->numberOfPages;
 351         sec_t sec;
 352         sec_t secs_to_write;
 353
 354         unsigned int oldUsed = 0;
 355         unsigned int oldAccess = cacheEntries[0].last_access;
 356
 357         while(numSectors>0)
 358         {
 359                 i=0;
 360                 while (i < numberOfPages ) {
 361                         if ( (sector>=cacheEntries[i].sector && sector < cacheEntries[i].sector+cacheEntries[i].count) ||
 362                                  (sector == cacheEntries[i].sector+cacheEntries[i].count && cacheEntries[i].count < cache->sectorsPerPage)) {
 363                                 sec=sector-cacheEntries[i].sector;
 364                                 secs_to_write=cache->sectorsPerPage-sec;
 365                                 if(secs_to_write>numSectors)secs_to_write=numSectors;
 366                                 memcpy(cacheEntries[i].cache + (sec*BYTES_PER_READ), buffer, secs_to_write*BYTES_PER_READ);
 367                                 cacheEntries[i].last_access = accessTime();
 368                                 cacheEntries[i].dirty = true;
 369                                 cacheEntries[i].count = sec + secs_to_write;
 370                                 numSectors=numSectors-secs_to_write;
 371                                 if(numSectors==0) return true;
 372                                 buffer+=secs_to_write*BYTES_PER_READ;
 373                                 sector+=secs_to_write;
 374                                 i=-1; // recheck all pages again
 375                                 oldUsed = 0;
 376                                 oldAccess = cacheEntries[0].last_access;
 377
 378                         }
 379                         else // While searching for the desired sector, also search for the least recently used page
 380                         if ( (cacheEntries[i].sector == CACHE_FREE) || (cacheEntries[i].last_access < oldAccess) ) {
 381                                 oldUsed = i;
 382                                 oldAccess = cacheEntries[i].last_access;
 383                         }
 384                         i++;
 385             }
 386                 // If it didn't, replace the least recently used cache page with the desired sector
 387                 if ((cacheEntries[oldUsed].sector != CACHE_FREE) && (cacheEntries[oldUsed].dirty == true)) {
 388                         // Write the page back to disc if it has been written to
 389                         if (!_FAT_disc_writeSectors (cache->disc, cacheEntries[oldUsed].sector, cacheEntries[oldUsed].count, cacheEntries[oldUsed].cache)) {
 390                                 return false;
 391                         }
 392                         cacheEntries[oldUsed].dirty = false;
 393                 }
 394
 395                 secs_to_write=numSectors;
 396                 if(secs_to_write>cache->sectorsPerPage)secs_to_write=cache->sectorsPerPage;
 397                 cacheEntries[oldUsed].sector = sector;
 398                 cacheEntries[oldUsed].count = secs_to_write;
 399
 400                 memcpy(cacheEntries[oldUsed].cache, buffer, secs_to_write*BYTES_PER_READ);
 401                 buffer+=secs_to_write*BYTES_PER_READ;
 402                 sector+=secs_to_write;
 403                 numSectors=numSectors-secs_to_write;
 404
 405                 // Increment the usage count, don't reset it
 406                 // This creates a paging policy of least used PAGE, not sector
 407                 cacheEntries[oldUsed].last_access = accessTime();
 408                 cacheEntries[oldUsed].dirty = true;
 409                 if(numSectors==0) return true;
 410                 oldUsed = 0;
 411                 oldAccess = cacheEntries[0].last_access;
 412         }
 413         return false;
 414 }
 415
 416 /*
 417 Flushes all dirty pages to disc, clearing the dirty flag.
 418 */
 419 bool _FAT_cache_flush (CACHE* cache) {
 420         unsigned int i;
 421
 422         for (i = 0; i < cache->numberOfPages; i++) {
 423                 if (cache->cacheEntries[i].dirty) {
 424                         if (!_FAT_disc_writeSectors (cache->disc, cache->cacheEntries[i].sector, cache->cacheEntries[i].count, cache->cacheEntries[i].cache)) {
 425                                 return false;
 426                         }
 427                 }
 428                 cache->cacheEntries[i].dirty = false;
 429         }
 430
 431         return true;
 432 }
 433
 434 void _FAT_cache_invalidate (CACHE* cache) {
 435         unsigned int i;
 436         _FAT_cache_flush(cache);
 437         for (i = 0; i < cache->numberOfPages; i++) {
 438                 cache->cacheEntries[i].sector = CACHE_FREE;
 439                 cache->cacheEntries[i].last_access = 0;
 440                 cache->cacheEntries[i].count = 0;
 441                 cache->cacheEntries[i].dirty = false;
 442         }
 443 }