reactos/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
  16  *  along with this program; if not, write to the Free Software
  17  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18  */
  19
  20 #include <freeldr.h>
  21
  22 #define NDEBUG
  23 #include <debug.h>
  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         DbgPrint((DPRINT_CACHE, "CacheInternalGetBlockPointer() BlockNumber = %d\n", BlockNumber));
  33
  34         CacheBlock = CacheInternalFindBlock(CacheDrive, BlockNumber);
  35
  36         if (CacheBlock != NULL)
  37         {
  38                 DbgPrint((DPRINT_CACHE, "Cache hit! BlockNumber: %d CacheBlock->BlockNumber: %d\n", BlockNumber, CacheBlock->BlockNumber));
  39
  40                 return CacheBlock;
  41         }
  42
  43         DbgPrint((DPRINT_CACHE, "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         DbgPrint((DPRINT_CACHE, "CacheInternalFindBlock() BlockNumber = %d\n", BlockNumber));
  58
  59         //
  60         // Make sure the block list has entries before I start searching it.
  61         //
  62         if (!RtlListIsEmpty((PLIST_ITEM)CacheDrive->CacheBlockHead))
  63         {
  64                 //
  65                 // Search the list and find the BIOS drive number
  66                 //
  67                 CacheBlock = CacheDrive->CacheBlockHead;
  68
  69                 while (CacheBlock != NULL)
  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 = (PCACHE_BLOCK)RtlListGetNext((PLIST_ITEM)CacheBlock);
  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         DbgPrint((DPRINT_CACHE, "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 = MmAllocateMemory(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 = MmAllocateMemory(CacheDrive->BlockSize * CacheDrive->BytesPerSector);
 114         if (CacheBlock->BlockData ==NULL)
 115         {
 116                 MmFreeMemory(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                 MmFreeMemory(CacheBlock->BlockData);
 124                 MmFreeMemory(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         if (CacheDrive->CacheBlockHead == NULL)
 131         {
 132                 CacheDrive->CacheBlockHead = CacheBlock;
 133         }
 134         else
 135         {
 136                 RtlListInsertTail((PLIST_ITEM)CacheDrive->CacheBlockHead, (PLIST_ITEM)CacheBlock);
 137         }
 138
 139         // Update the cache data
 140         CacheBlockCount++;
 141         CacheSizeCurrent = CacheBlockCount * (CacheDrive->BlockSize * CacheDrive->BytesPerSector);
 142
 143         CacheInternalDumpBlockList(CacheDrive);
 144
 145         return CacheBlock;
 146 }
 147
 148 BOOL CacheInternalFreeBlock(PCACHE_DRIVE CacheDrive)
 149 {
 150         PCACHE_BLOCK    CacheBlockToFree;
 151
 152         DbgPrint((DPRINT_CACHE, "CacheInternalFreeBlock()\n"));
 153
 154         // Get a pointer to the last item in the block list
 155         // that isn't forced to be in the cache and remove
 156         // it from the list
 157         CacheBlockToFree = (PCACHE_BLOCK)RtlListGetTail((PLIST_ITEM)CacheDrive->CacheBlockHead);
 158         while (CacheBlockToFree != NULL && CacheBlockToFree->LockedInCache == TRUE)
 159         {
 160                 CacheBlockToFree = (PCACHE_BLOCK)RtlListGetPrevious((PLIST_ITEM)CacheBlockToFree);
 161         }
 162
 163         // No blocks left in cache that can be freed
 164         // so just return
 165         if (CacheBlockToFree == NULL)
 166         {
 167                 return FALSE;
 168         }
 169
 170         //
 171         // If we are freeing the head of the list then update it's pointer
 172         //
 173         if (CacheBlockToFree == CacheDrive->CacheBlockHead)
 174         {
 175                 CacheDrive->CacheBlockHead = (PCACHE_BLOCK)RtlListGetNext((PLIST_ITEM)CacheBlockToFree);
 176         }
 177
 178         RtlListRemoveEntry((PLIST_ITEM)CacheBlockToFree);
 179
 180         // Free the block memory and the block structure
 181         MmFreeMemory(CacheBlockToFree->BlockData);
 182         MmFreeMemory(CacheBlockToFree);
 183
 184         // Update the cache data
 185         CacheBlockCount--;
 186         CacheSizeCurrent = CacheBlockCount * (CacheDrive->BlockSize * CacheDrive->BytesPerSector);
 187
 188         return TRUE;
 189 }
 190
 191 VOID CacheInternalCheckCacheSizeLimits(PCACHE_DRIVE CacheDrive)
 192 {
 193         ULONG           NewCacheSize;
 194
 195         DbgPrint((DPRINT_CACHE, "CacheInternalCheckCacheSizeLimits()\n"));
 196
 197         // Calculate the size of the cache if we added a block
 198         NewCacheSize = (CacheBlockCount + 1) * (CacheDrive->BlockSize * CacheDrive->BytesPerSector);
 199
 200         // Check the new size against the cache size limit
 201         if (NewCacheSize > CacheSizeLimit)
 202         {
 203                 CacheInternalFreeBlock(CacheDrive);
 204                 CacheInternalDumpBlockList(CacheDrive);
 205         }
 206 }
 207
 208 VOID CacheInternalDumpBlockList(PCACHE_DRIVE CacheDrive)
 209 {
 210         PCACHE_BLOCK    CacheBlock;
 211
 212         DbgPrint((DPRINT_CACHE, "Dumping block list for BIOS drive 0x%x.\n", CacheDrive->DriveNumber));
 213         DbgPrint((DPRINT_CACHE, "BytesPerSector: %d.\n", CacheDrive->BytesPerSector));
 214         DbgPrint((DPRINT_CACHE, "BlockSize: %d.\n", CacheDrive->BlockSize));
 215         DbgPrint((DPRINT_CACHE, "CacheSizeLimit: %d.\n", CacheSizeLimit));
 216         DbgPrint((DPRINT_CACHE, "CacheSizeCurrent: %d.\n", CacheSizeCurrent));
 217         DbgPrint((DPRINT_CACHE, "CacheBlockCount: %d.\n", CacheBlockCount));
 218         DbgPrint((DPRINT_CACHE, "Dumping %d cache blocks.\n", RtlListCountEntries((PLIST_ITEM)CacheDrive->CacheBlockHead)));
 219
 220         CacheBlock = CacheDrive->CacheBlockHead;
 221         while (CacheBlock != NULL)
 222         {
 223                 DbgPrint((DPRINT_CACHE, "Cache Block: CacheBlock: 0x%x\n", CacheBlock));
 224                 DbgPrint((DPRINT_CACHE, "Cache Block: Block Number: %d\n", CacheBlock->BlockNumber));
 225                 DbgPrint((DPRINT_CACHE, "Cache Block: Access Count: %d\n", CacheBlock->AccessCount));
 226                 DbgPrint((DPRINT_CACHE, "Cache Block: Block Data: 0x%x\n", CacheBlock->BlockData));
 227                 DbgPrint((DPRINT_CACHE, "Cache Block: Locked In Cache: %d\n", CacheBlock->LockedInCache));
 228
 229                 if (CacheBlock->BlockData == NULL)
 230                 {
 231                         BugCheck((DPRINT_CACHE, "What the heck?!?\n"));
 232                 }
 233
 234                 CacheBlock = (PCACHE_BLOCK)RtlListGetNext((PLIST_ITEM)CacheBlock);
 235         }
 236 }
 237
 238 VOID CacheInternalOptimizeBlockList(PCACHE_DRIVE CacheDrive, PCACHE_BLOCK CacheBlock)
 239 {
 240
 241         DbgPrint((DPRINT_CACHE, "CacheInternalOptimizeBlockList()\n"));
 242
 243         // Don't do this if this block is already at the head of the list
 244         if (CacheBlock != CacheDrive->CacheBlockHead)
 245         {
 246                 // Remove this item from the block list
 247                 RtlListRemoveEntry((PLIST_ITEM)CacheBlock);
 248
 249                 // Re-insert it at the head of the list
 250                 RtlListInsertHead((PLIST_ITEM)CacheDrive->CacheBlockHead, (PLIST_ITEM)CacheBlock);
 251
 252                 // Update the head pointer
 253                 CacheDrive->CacheBlockHead = CacheBlock;
 254         }
 255 }