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 = MmHeapAlloc(sizeof(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 = MmHeapAlloc(CacheDrive->BlockSize * CacheDrive->BytesPerSector);
 114         if (CacheBlock->BlockData ==NULL)
 115         {
 116                 MmHeapFree(CacheBlock);
 117                 return NULL;
 118         }
 119
 120         // Now try to read in the block
 121         if (!MachDiskReadLogicalSectors(CacheDrive->DriveNumber, (BlockNumber * CacheDrive->BlockSize), CacheDrive->BlockSize, (PVOID)DISKREADBUFFER))
 122         {
 123                 MmHeapFree(CacheBlock->BlockData);
 124                 MmHeapFree(CacheBlock);
 125                 return NULL;
 126         }
 127         RtlCopyMemory(CacheBlock->BlockData, (PVOID)DISKREADBUFFER, CacheDrive->BlockSize * CacheDrive->BytesPerSector);
 128
 129         // Add it to our list of blocks managed by the cache
 130         InsertTailList(&CacheDrive->CacheBlockHead, &CacheBlock->ListEntry);
 131
 132         // Update the cache data
 133         CacheBlockCount++;
 134         CacheSizeCurrent = CacheBlockCount * (CacheDrive->BlockSize * CacheDrive->BytesPerSector);
 135
 136         CacheInternalDumpBlockList(CacheDrive);
 137
 138         return CacheBlock;
 139 }
 140
 141 BOOLEAN CacheInternalFreeBlock(PCACHE_DRIVE CacheDrive)
 142 {
 143         PCACHE_BLOCK    CacheBlockToFree;
 144
 145         TRACE("CacheInternalFreeBlock()\n");
 146
 147         // Get a pointer to the last item in the block list
 148         // that isn't forced to be in the cache and remove
 149         // it from the list
 150         CacheBlockToFree = CONTAINING_RECORD(CacheDrive->CacheBlockHead.Blink, CACHE_BLOCK, ListEntry);
 151         while (&CacheBlockToFree->ListEntry != &CacheDrive->CacheBlockHead && CacheBlockToFree->LockedInCache == TRUE)
 152         {
 153                 CacheBlockToFree = CONTAINING_RECORD(CacheBlockToFree->ListEntry.Blink, CACHE_BLOCK, ListEntry);
 154         }
 155
 156         // No blocks left in cache that can be freed
 157         // so just return
 158         if (IsListEmpty(&CacheDrive->CacheBlockHead))
 159         {
 160                 return FALSE;
 161         }
 162
 163         RemoveEntryList(&CacheBlockToFree->ListEntry);
 164
 165         // Free the block memory and the block structure
 166         MmHeapFree(CacheBlockToFree->BlockData);
 167         MmHeapFree(CacheBlockToFree);
 168
 169         // Update the cache data
 170         CacheBlockCount--;
 171         CacheSizeCurrent = CacheBlockCount * (CacheDrive->BlockSize * CacheDrive->BytesPerSector);
 172
 173         return TRUE;
 174 }
 175
 176 VOID CacheInternalCheckCacheSizeLimits(PCACHE_DRIVE CacheDrive)
 177 {
 178         SIZE_T          NewCacheSize;
 179
 180         TRACE("CacheInternalCheckCacheSizeLimits()\n");
 181
 182         // Calculate the size of the cache if we added a block
 183         NewCacheSize = (CacheBlockCount + 1) * (CacheDrive->BlockSize * CacheDrive->BytesPerSector);
 184
 185         // Check the new size against the cache size limit
 186         if (NewCacheSize > CacheSizeLimit)
 187         {
 188                 CacheInternalFreeBlock(CacheDrive);
 189                 CacheInternalDumpBlockList(CacheDrive);
 190         }
 191 }
 192
 193 VOID CacheInternalDumpBlockList(PCACHE_DRIVE CacheDrive)
 194 {
 195         PCACHE_BLOCK    CacheBlock;
 196
 197         TRACE("Dumping block list for BIOS drive 0x%x.\n", CacheDrive->DriveNumber);
 198         TRACE("BytesPerSector: %d.\n", CacheDrive->BytesPerSector);
 199         TRACE("BlockSize: %d.\n", CacheDrive->BlockSize);
 200         TRACE("CacheSizeLimit: %d.\n", CacheSizeLimit);
 201         TRACE("CacheSizeCurrent: %d.\n", CacheSizeCurrent);
 202         TRACE("CacheBlockCount: %d.\n", CacheBlockCount);
 203
 204         CacheBlock = CONTAINING_RECORD(CacheDrive->CacheBlockHead.Flink, CACHE_BLOCK, ListEntry);
 205         while (&CacheBlock->ListEntry != &CacheDrive->CacheBlockHead)
 206         {
 207                 TRACE("Cache Block: CacheBlock: 0x%x\n", CacheBlock);
 208                 TRACE("Cache Block: Block Number: %d\n", CacheBlock->BlockNumber);
 209                 TRACE("Cache Block: Access Count: %d\n", CacheBlock->AccessCount);
 210                 TRACE("Cache Block: Block Data: 0x%x\n", CacheBlock->BlockData);
 211                 TRACE("Cache Block: Locked In Cache: %d\n", CacheBlock->LockedInCache);
 212
 213                 if (CacheBlock->BlockData == NULL)
 214                 {
 215                         BugCheck("CacheBlock->BlockData == NULL\n");
 216                 }
 217
 218                 CacheBlock = CONTAINING_RECORD(CacheBlock->ListEntry.Flink, CACHE_BLOCK, ListEntry);
 219         }
 220 }
 221
 222 VOID CacheInternalOptimizeBlockList(PCACHE_DRIVE CacheDrive, PCACHE_BLOCK CacheBlock)
 223 {
 224
 225         TRACE("CacheInternalOptimizeBlockList()\n");
 226
 227         // Don't do this if this block is already at the head of the list
 228         if (&CacheBlock->ListEntry != CacheDrive->CacheBlockHead.Flink)
 229         {
 230                 // Remove this item from the block list
 231                 RemoveEntryList(&CacheBlock->ListEntry);
 232
 233                 // Re-insert it at the head of the list
 234                 InsertHeadList(&CacheDrive->CacheBlockHead, &CacheBlock->ListEntry);
 235         }
 236 }