boot/freeldr/freeldr/cache/blocklist.c

   1 /*
   2  *  FreeLoader
   3  *  Copyright (C) 1998-2003  Brian Palmer  <brianp@sginet.com>
   4  *
   5  *  This program is free software; you can redistribute it and/or modify
   6  *  it under the terms of the GNU General Public License as published by
   7  *  the Free Software Foundation; either version 2 of the License, or
   8  *  (at your option) any later version.
   9  *
  10  *  This program is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  *  GNU General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU General Public License along
  16  *  with this program; if not, write to the Free Software Foundation, Inc.,
  17  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18  */
  19
  20 #include <freeldr.h>
  21 #include <debug.h>
  22
  23 DBG_DEFAULT_CHANNEL(CACHE);
  24
  25 // Returns a pointer to a CACHE_BLOCK structure
  26 // Adds the block to the cache manager block list
  27 // in cache memory if it isn't already there
  28 PCACHE_BLOCK CacheInternalGetBlockPointer(PCACHE_DRIVE CacheDrive, ULONG BlockNumber)
  29 {
  30     PCACHE_BLOCK    CacheBlock = NULL;
  31
  32     TRACE("CacheInternalGetBlockPointer() BlockNumber = %d\n", BlockNumber);
  33
  34     CacheBlock = CacheInternalFindBlock(CacheDrive, BlockNumber);
  35
  36     if (CacheBlock != NULL)
  37     {
  38         TRACE("Cache hit! BlockNumber: %d CacheBlock->BlockNumber: %d\n", BlockNumber, CacheBlock->BlockNumber);
  39
  40         return CacheBlock;
  41     }
  42
  43     TRACE("Cache miss! BlockNumber: %d\n", BlockNumber);
  44
  45     CacheBlock = CacheInternalAddBlockToCache(CacheDrive, BlockNumber);
  46
  47     // Optimize the block list so it has a LRU structure
  48     CacheInternalOptimizeBlockList(CacheDrive, CacheBlock);
  49
  50     return CacheBlock;
  51 }
  52
  53 PCACHE_BLOCK CacheInternalFindBlock(PCACHE_DRIVE CacheDrive, ULONG BlockNumber)
  54 {
  55     PCACHE_BLOCK    CacheBlock = NULL;
  56
  57     TRACE("CacheInternalFindBlock() BlockNumber = %d\n", BlockNumber);
  58
  59     //
  60     // Make sure the block list has entries before I start searching it.
  61     //
  62     if (!IsListEmpty(&CacheDrive->CacheBlockHead))
  63     {
  64         //
  65         // Search the list and find the BIOS drive number
  66         //
  67         CacheBlock = CONTAINING_RECORD(CacheDrive->CacheBlockHead.Flink, CACHE_BLOCK, ListEntry);
  68
  69         while (&CacheBlock->ListEntry != &CacheDrive->CacheBlockHead)
  70         {
  71             //
  72             // We found the block, so return it
  73             //
  74             if (CacheBlock->BlockNumber == BlockNumber)
  75             {
  76                 //
  77                 // Increment the blocks access count
  78                 //
  79                 CacheBlock->AccessCount++;
  80
  81                 return CacheBlock;
  82             }
  83
  84             CacheBlock = CONTAINING_RECORD(CacheBlock->ListEntry.Flink, CACHE_BLOCK, ListEntry);
  85         }
  86     }
  87
  88     return NULL;
  89 }
  90
  91 PCACHE_BLOCK CacheInternalAddBlockToCache(PCACHE_DRIVE CacheDrive, ULONG BlockNumber)
  92 {
  93     PCACHE_BLOCK    CacheBlock = NULL;
  94
  95     TRACE("CacheInternalAddBlockToCache() BlockNumber = %d\n", BlockNumber);
  96
  97     // Check the size of the cache so we don't exceed our limits
  98     CacheInternalCheckCacheSizeLimits(CacheDrive);
  99
 100     // We will need to add the block to the
 101     // drive's list of cached blocks. So allocate
 102     // the block memory.
 103     CacheBlock = FrLdrTempAlloc(sizeof(CACHE_BLOCK), TAG_CACHE_BLOCK);
 104     if (CacheBlock == NULL)
 105     {
 106         return NULL;
 107     }
 108
 109     // Now initialize the structure and
 110     // allocate room for the block data
 111     RtlZeroMemory(CacheBlock, sizeof(CACHE_BLOCK));
 112     CacheBlock->BlockNumber = BlockNumber;
 113     CacheBlock->BlockData = FrLdrTempAlloc(CacheDrive->BlockSize * CacheDrive->BytesPerSector,
 114                                            TAG_CACHE_DATA);
 115     if (CacheBlock->BlockData ==NULL)
 116     {
 117         FrLdrTempFree(CacheBlock, TAG_CACHE_BLOCK);
 118         return NULL;
 119     }
 120
 121     // Now try to read in the block
 122     if (!MachDiskReadLogicalSectors(CacheDrive->DriveNumber, (BlockNumber * CacheDrive->BlockSize), CacheDrive->BlockSize, (PVOID)DISKREADBUFFER))
 123     {
 124         FrLdrTempFree(CacheBlock->BlockData, TAG_CACHE_DATA);
 125         FrLdrTempFree(CacheBlock, TAG_CACHE_BLOCK);
 126         return NULL;
 127     }
 128     RtlCopyMemory(CacheBlock->BlockData, (PVOID)DISKREADBUFFER, CacheDrive->BlockSize * CacheDrive->BytesPerSector);
 129
 130     // Add it to our list of blocks managed by the cache
 131     InsertTailList(&CacheDrive->CacheBlockHead, &CacheBlock->ListEntry);
 132
 133     // Update the cache data
 134     CacheBlockCount++;
 135     CacheSizeCurrent = CacheBlockCount * (CacheDrive->BlockSize * CacheDrive->BytesPerSector);
 136
 137     CacheInternalDumpBlockList(CacheDrive);
 138
 139     return CacheBlock;
 140 }
 141
 142 BOOLEAN CacheInternalFreeBlock(PCACHE_DRIVE CacheDrive)
 143 {
 144     PCACHE_BLOCK    CacheBlockToFree;
 145
 146     TRACE("CacheInternalFreeBlock()\n");
 147
 148     // Get a pointer to the last item in the block list
 149     // that isn't forced to be in the cache and remove
 150     // it from the list
 151     CacheBlockToFree = CONTAINING_RECORD(CacheDrive->CacheBlockHead.Blink, CACHE_BLOCK, ListEntry);
 152     while (&CacheBlockToFree->ListEntry != &CacheDrive->CacheBlockHead && CacheBlockToFree->LockedInCache == TRUE)
 153     {
 154         CacheBlockToFree = CONTAINING_RECORD(CacheBlockToFree->ListEntry.Blink, CACHE_BLOCK, ListEntry);
 155     }
 156
 157     // No blocks left in cache that can be freed
 158     // so just return
 159     if (IsListEmpty(&CacheDrive->CacheBlockHead))
 160     {
 161         return FALSE;
 162     }
 163
 164     RemoveEntryList(&CacheBlockToFree->ListEntry);
 165
 166     // Free the block memory and the block structure
 167     FrLdrTempFree(CacheBlockToFree->BlockData, TAG_CACHE_DATA);
 168     FrLdrTempFree(CacheBlockToFree, TAG_CACHE_BLOCK);
 169
 170     // Update the cache data
 171     CacheBlockCount--;
 172     CacheSizeCurrent = CacheBlockCount * (CacheDrive->BlockSize * CacheDrive->BytesPerSector);
 173
 174     return TRUE;
 175 }
 176
 177 VOID CacheInternalCheckCacheSizeLimits(PCACHE_DRIVE CacheDrive)
 178 {
 179     SIZE_T        NewCacheSize;
 180
 181     TRACE("CacheInternalCheckCacheSizeLimits()\n");
 182
 183     // Calculate the size of the cache if we added a block
 184     NewCacheSize = (CacheBlockCount + 1) * (CacheDrive->BlockSize * CacheDrive->BytesPerSector);
 185
 186     // Check the new size against the cache size limit
 187     if (NewCacheSize > CacheSizeLimit)
 188     {
 189         CacheInternalFreeBlock(CacheDrive);
 190         CacheInternalDumpBlockList(CacheDrive);
 191     }
 192 }
 193
 194 VOID CacheInternalDumpBlockList(PCACHE_DRIVE CacheDrive)
 195 {
 196     PCACHE_BLOCK    CacheBlock;
 197
 198     TRACE("Dumping block list for BIOS drive 0x%x.\n", CacheDrive->DriveNumber);
 199     TRACE("BytesPerSector: %d.\n", CacheDrive->BytesPerSector);
 200     TRACE("BlockSize: %d.\n", CacheDrive->BlockSize);
 201     TRACE("CacheSizeLimit: %d.\n", CacheSizeLimit);
 202     TRACE("CacheSizeCurrent: %d.\n", CacheSizeCurrent);
 203     TRACE("CacheBlockCount: %d.\n", CacheBlockCount);
 204
 205     CacheBlock = CONTAINING_RECORD(CacheDrive->CacheBlockHead.Flink, CACHE_BLOCK, ListEntry);
 206     while (&CacheBlock->ListEntry != &CacheDrive->CacheBlockHead)
 207     {
 208         TRACE("Cache Block: CacheBlock: 0x%x\n", CacheBlock);
 209         TRACE("Cache Block: Block Number: %d\n", CacheBlock->BlockNumber);
 210         TRACE("Cache Block: Access Count: %d\n", CacheBlock->AccessCount);
 211         TRACE("Cache Block: Block Data: 0x%x\n", CacheBlock->BlockData);
 212         TRACE("Cache Block: Locked In Cache: %d\n", CacheBlock->LockedInCache);
 213
 214         if (CacheBlock->BlockData == NULL)
 215         {
 216             BugCheck("CacheBlock->BlockData == NULL\n");
 217         }
 218
 219         CacheBlock = CONTAINING_RECORD(CacheBlock->ListEntry.Flink, CACHE_BLOCK, ListEntry);
 220     }
 221 }
 222
 223 VOID CacheInternalOptimizeBlockList(PCACHE_DRIVE CacheDrive, PCACHE_BLOCK CacheBlock)
 224 {
 225
 226     TRACE("CacheInternalOptimizeBlockList()\n");
 227
 228     // Don't do this if this block is already at the head of the list
 229     if (&CacheBlock->ListEntry != CacheDrive->CacheBlockHead.Flink)
 230     {
 231         // Remove this item from the block list
 232         RemoveEntryList(&CacheBlock->ListEntry);
 233
 234         // Re-insert it at the head of the list
 235         InsertHeadList(&CacheDrive->CacheBlockHead, &CacheBlock->ListEntry);
 236     }
 237 }