1828fc1d3f2a3769debaec1c3383d101c971d9ec
[reactos.git] / boot / freeldr / freeldr / lib / 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, DiskReadBuffer))
123 {
124 FrLdrTempFree(CacheBlock->BlockData, TAG_CACHE_DATA);
125 FrLdrTempFree(CacheBlock, TAG_CACHE_BLOCK);
126 return NULL;
127 }
128 RtlCopyMemory(CacheBlock->BlockData, 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)
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 }