e6b8f00426177dcee9c75885930e0dce84224eda
[reactos.git] / reactos / boot / freeldr / freeldr / mm / meminit.c
1 /*
2 * FreeLoader
3 * Copyright (C) 2006-2008 Aleksey Bragin <aleksey@reactos.org>
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 #include <debug.h>
22
23 #ifdef DBG
24 typedef struct
25 {
26 ULONG Type;
27 UCHAR TypeString[20];
28 } FREELDR_MEMORY_TYPE, *PFREELDR_MEMORY_TYPE;
29
30 ULONG MemoryTypeCount = 5;
31 FREELDR_MEMORY_TYPE MemoryTypeArray[] =
32 {
33 { 0, "Unknown Memory" },
34 { BiosMemoryUsable, "Usable Memory" },
35 { BiosMemoryReserved, "Reserved Memory" },
36 { BiosMemoryAcpiReclaim, "ACPI Reclaim Memory" },
37 { BiosMemoryAcpiNvs, "ACPI NVS Memory" },
38 };
39 #endif
40
41 PVOID PageLookupTableAddress = NULL;
42 ULONG TotalPagesInLookupTable = 0;
43 ULONG FreePagesInLookupTable = 0;
44 ULONG LastFreePageHint = 0;
45
46 extern ULONG_PTR MmHeapPointer;
47 extern ULONG_PTR MmHeapStart;
48
49 BOOLEAN MmInitializeMemoryManager(VOID)
50 {
51 BIOS_MEMORY_MAP BiosMemoryMap[32];
52 ULONG BiosMemoryMapEntryCount;
53 #ifdef DBG
54 ULONG Index;
55 #endif
56
57 DbgPrint((DPRINT_MEMORY, "Initializing Memory Manager.\n"));
58
59 RtlZeroMemory(BiosMemoryMap, sizeof(BIOS_MEMORY_MAP) * 32);
60
61 BiosMemoryMapEntryCount = MachGetMemoryMap(BiosMemoryMap, sizeof(BiosMemoryMap) / sizeof(BIOS_MEMORY_MAP));
62
63 #ifdef DBG
64 // Dump the system memory map
65 if (BiosMemoryMapEntryCount != 0)
66 {
67 DbgPrint((DPRINT_MEMORY, "System Memory Map (Base Address, Length, Type):\n"));
68 for (Index=0; Index<BiosMemoryMapEntryCount; Index++)
69 {
70 DbgPrint((DPRINT_MEMORY, "%x%x\t %x%x\t %s\n", BiosMemoryMap[Index].BaseAddress, BiosMemoryMap[Index].Length, MmGetSystemMemoryMapTypeString(BiosMemoryMap[Index].Type)));
71 }
72 }
73 #endif
74
75 // If we got the system memory map then fixup invalid entries
76 if (BiosMemoryMapEntryCount != 0)
77 {
78 MmFixupSystemMemoryMap(BiosMemoryMap, &BiosMemoryMapEntryCount);
79 }
80
81 // Find address for the page lookup table
82 TotalPagesInLookupTable = MmGetAddressablePageCountIncludingHoles(BiosMemoryMap, BiosMemoryMapEntryCount);
83 PageLookupTableAddress = MmFindLocationForPageLookupTable(BiosMemoryMap, BiosMemoryMapEntryCount);
84 LastFreePageHint = TotalPagesInLookupTable;
85
86 if (PageLookupTableAddress == 0)
87 {
88 // If we get here then we probably couldn't
89 // find a contiguous chunk of memory big
90 // enough to hold the page lookup table
91 printf("Error initializing memory manager!\n");
92 return FALSE;
93 }
94
95 // Initialize the page lookup table
96 MmInitPageLookupTable(PageLookupTableAddress, TotalPagesInLookupTable, BiosMemoryMap, BiosMemoryMapEntryCount);
97 MmUpdateLastFreePageHint(PageLookupTableAddress, TotalPagesInLookupTable);
98
99 // Add machine-dependent stuff
100 #ifdef __i386__
101 MmMarkPagesInLookupTable(PageLookupTableAddress, 0x00, 1, LoaderFirmwarePermanent); // realmode int vectors
102 MmMarkPagesInLookupTable(PageLookupTableAddress, 0x01, 7, LoaderFirmwareTemporary); // freeldr stack + cmdline
103 MmMarkPagesInLookupTable(PageLookupTableAddress, 0x08, 0x70, LoaderLoadedProgram); // freeldr image (roughly max. 0x64 pages)
104 MmMarkPagesInLookupTable(PageLookupTableAddress, 0x78, 8, LoaderOsloaderStack); // prot mode stack. BIOSCALLBUFFER
105 MmMarkPagesInLookupTable(PageLookupTableAddress, 0x80, 0x10, LoaderOsloaderHeap); // File system read buffer. FILESYSBUFFER
106 MmMarkPagesInLookupTable(PageLookupTableAddress, 0x90, 0x10, LoaderOsloaderHeap); // Disk read buffer for int 13h. DISKREADBUFFER
107 MmMarkPagesInLookupTable(PageLookupTableAddress, 0xA0, 0x60, LoaderFirmwarePermanent); // ROM / Video
108 MmMarkPagesInLookupTable(PageLookupTableAddress, 0xFFF, 1, LoaderSpecialMemory); // unusable memory
109 #endif
110
111 FreePagesInLookupTable = MmCountFreePagesInLookupTable(PageLookupTableAddress, TotalPagesInLookupTable);
112
113 MmInitializeHeap(PageLookupTableAddress);
114
115 DbgPrint((DPRINT_MEMORY, "Memory Manager initialized. %d pages available.\n", FreePagesInLookupTable));
116 return TRUE;
117 }
118
119 VOID MmInitializeHeap(PVOID PageLookupTable)
120 {
121 ULONG PagesNeeded;
122 ULONG HeapStart;
123
124 // HACK: Make it so it doesn't overlap kernel space
125 MmMarkPagesInLookupTable(PageLookupTableAddress, 0x100, 0xFF, LoaderSystemCode);
126
127 // Find contigious memory block for HEAP:STACK
128 PagesNeeded = HEAP_PAGES + STACK_PAGES;
129 HeapStart = MmFindAvailablePages(PageLookupTable, TotalPagesInLookupTable, PagesNeeded, FALSE);
130
131 // Unapply the hack
132 MmMarkPagesInLookupTable(PageLookupTableAddress, 0x100, 0xFF, LoaderFree);
133
134 if (HeapStart == 0)
135 {
136 UiMessageBox("Critical error: Can't allocate heap!");
137 return;
138 }
139
140 // Initialize BGET
141 bpool(HeapStart << MM_PAGE_SHIFT, PagesNeeded << MM_PAGE_SHIFT);
142
143 // Mark those pages as used
144 MmMarkPagesInLookupTable(PageLookupTableAddress, HeapStart, PagesNeeded, LoaderOsloaderHeap);
145
146 DbgPrint((DPRINT_MEMORY, "Heap initialized, base 0x%08x, pages %d\n", (HeapStart << MM_PAGE_SHIFT), PagesNeeded));
147 }
148
149 #ifdef DBG
150 PUCHAR MmGetSystemMemoryMapTypeString(ULONG Type)
151 {
152 ULONG Index;
153
154 for (Index=1; Index<MemoryTypeCount; Index++)
155 {
156 if (MemoryTypeArray[Index].Type == Type)
157 {
158 return MemoryTypeArray[Index].TypeString;
159 }
160 }
161
162 return MemoryTypeArray[0].TypeString;
163 }
164 #endif
165
166 ULONG MmGetPageNumberFromAddress(PVOID Address)
167 {
168 return ((ULONG)Address) / MM_PAGE_SIZE;
169 }
170
171 PVOID MmGetEndAddressOfAnyMemory(PBIOS_MEMORY_MAP BiosMemoryMap, ULONG MapCount)
172 {
173 ULONGLONG MaxStartAddressSoFar;
174 ULONGLONG EndAddressOfMemory;
175 ULONG Index;
176
177 MaxStartAddressSoFar = 0;
178 EndAddressOfMemory = 0;
179 for (Index=0; Index<MapCount; Index++)
180 {
181 if (MaxStartAddressSoFar <= BiosMemoryMap[Index].BaseAddress)
182 {
183 MaxStartAddressSoFar = BiosMemoryMap[Index].BaseAddress;
184 EndAddressOfMemory = (MaxStartAddressSoFar + BiosMemoryMap[Index].Length);
185 if (EndAddressOfMemory > 0xFFFFFFFF)
186 {
187 EndAddressOfMemory = 0xFFFFFFFF;
188 }
189 }
190 }
191
192 DbgPrint((DPRINT_MEMORY, "MmGetEndAddressOfAnyMemory() returning 0x%x\n", (ULONG)EndAddressOfMemory));
193
194 return (PVOID)(ULONG)EndAddressOfMemory;
195 }
196
197 ULONG MmGetAddressablePageCountIncludingHoles(PBIOS_MEMORY_MAP BiosMemoryMap, ULONG MapCount)
198 {
199 ULONG PageCount;
200 ULONGLONG EndAddress;
201
202 EndAddress = (ULONGLONG)(ULONG)MmGetEndAddressOfAnyMemory(BiosMemoryMap, MapCount);
203
204 // Since MmGetEndAddressOfAnyMemory() won't
205 // return addresses higher than 0xFFFFFFFF
206 // then we need to adjust the end address
207 // to 0x100000000 so we don't get an
208 // off-by-one error
209 if (EndAddress >= 0xFFFFFFFF)
210 {
211 EndAddress = 0x100000000LL;
212
213 DbgPrint((DPRINT_MEMORY, "MmGetEndAddressOfAnyMemory() returned 0xFFFFFFFF, correcting to be 0x100000000.\n"));
214 }
215
216 PageCount = (EndAddress / MM_PAGE_SIZE);
217
218 DbgPrint((DPRINT_MEMORY, "MmGetAddressablePageCountIncludingHoles() returning %d\n", PageCount));
219
220 return PageCount;
221 }
222
223 PVOID MmFindLocationForPageLookupTable(PBIOS_MEMORY_MAP BiosMemoryMap, ULONG MapCount)
224 {
225 ULONG TotalPageCount;
226 ULONG PageLookupTableSize;
227 PVOID PageLookupTableMemAddress;
228 int Index;
229 BIOS_MEMORY_MAP TempBiosMemoryMap[32];
230
231 TotalPageCount = MmGetAddressablePageCountIncludingHoles(BiosMemoryMap, MapCount);
232 PageLookupTableSize = TotalPageCount * sizeof(PAGE_LOOKUP_TABLE_ITEM);
233 PageLookupTableMemAddress = 0;
234
235 RtlCopyMemory(TempBiosMemoryMap, BiosMemoryMap, sizeof(BIOS_MEMORY_MAP) * 32);
236 MmSortBiosMemoryMap(TempBiosMemoryMap, MapCount);
237
238 // Find a place, starting from the highest memory
239 // (thus leaving low memory for kernel/drivers)
240 for (Index=(MapCount-1); Index>=0; Index--)
241 {
242 // If this is usable memory with a big enough length
243 // then we'll put our page lookup table here
244
245 // skip if this is not usable region
246 if (TempBiosMemoryMap[Index].Type != BiosMemoryUsable)
247 continue;
248
249 if (TempBiosMemoryMap[Index].Length >= PageLookupTableSize)
250 {
251 PageLookupTableMemAddress = (PVOID)(ULONG)
252 (TempBiosMemoryMap[Index].BaseAddress + (TempBiosMemoryMap[Index].Length - PageLookupTableSize));
253 break;
254 }
255 }
256
257 DbgPrint((DPRINT_MEMORY, "MmFindLocationForPageLookupTable() returning 0x%x\n", PageLookupTableMemAddress));
258
259 return PageLookupTableMemAddress;
260 }
261
262 VOID MmSortBiosMemoryMap(PBIOS_MEMORY_MAP BiosMemoryMap, ULONG MapCount)
263 {
264 ULONG Index;
265 ULONG LoopCount;
266 BIOS_MEMORY_MAP TempMapItem;
267
268 // Loop once for each entry in the memory map minus one
269 // On each loop iteration go through and sort the memory map
270 for (LoopCount=0; LoopCount<(MapCount-1); LoopCount++)
271 {
272 for (Index=0; Index<(MapCount-1); Index++)
273 {
274 if (BiosMemoryMap[Index].BaseAddress > BiosMemoryMap[Index+1].BaseAddress)
275 {
276 TempMapItem = BiosMemoryMap[Index];
277 BiosMemoryMap[Index] = BiosMemoryMap[Index+1];
278 BiosMemoryMap[Index+1] = TempMapItem;
279 }
280 }
281 }
282 }
283
284 VOID MmInitPageLookupTable(PVOID PageLookupTable, ULONG TotalPageCount, PBIOS_MEMORY_MAP BiosMemoryMap, ULONG MapCount)
285 {
286 ULONG MemoryMapStartPage;
287 ULONG MemoryMapEndPage;
288 ULONG MemoryMapPageCount;
289 ULONG MemoryMapPageAllocated;
290 ULONG PageLookupTableStartPage;
291 ULONG PageLookupTablePageCount;
292 ULONG Index;
293
294 DbgPrint((DPRINT_MEMORY, "MmInitPageLookupTable()\n"));
295
296 // Mark every page as allocated initially
297 // We will go through and mark pages again according to the memory map
298 // But this will mark any holes not described in the map as allocated
299 MmMarkPagesInLookupTable(PageLookupTable, 0, TotalPageCount, LoaderFirmwarePermanent);
300
301 for (Index=0; Index<MapCount; Index++)
302 {
303 MemoryMapStartPage = MmGetPageNumberFromAddress((PVOID)(ULONG)BiosMemoryMap[Index].BaseAddress);
304 MemoryMapEndPage = MmGetPageNumberFromAddress((PVOID)(ULONG)(BiosMemoryMap[Index].BaseAddress + BiosMemoryMap[Index].Length - 1));
305 MemoryMapPageCount = (MemoryMapEndPage - MemoryMapStartPage) + 1;
306
307 switch (BiosMemoryMap[Index].Type)
308 {
309 case BiosMemoryUsable:
310 MemoryMapPageAllocated = LoaderFree;
311 break;
312
313 case BiosMemoryAcpiReclaim:
314 case BiosMemoryAcpiNvs:
315 MemoryMapPageAllocated = LoaderSpecialMemory;
316 break;
317
318 default:
319 MemoryMapPageAllocated = LoaderSpecialMemory;
320 }
321 DbgPrint((DPRINT_MEMORY, "Marking pages as type %d: StartPage: %d PageCount: %d\n", MemoryMapPageAllocated, MemoryMapStartPage, MemoryMapPageCount));
322 MmMarkPagesInLookupTable(PageLookupTable, MemoryMapStartPage, MemoryMapPageCount, MemoryMapPageAllocated);
323 }
324
325 // Mark the pages that the lookup table occupies as reserved
326 PageLookupTableStartPage = MmGetPageNumberFromAddress(PageLookupTable);
327 PageLookupTablePageCount = MmGetPageNumberFromAddress((PVOID)((ULONG_PTR)PageLookupTable + ROUND_UP(TotalPageCount * sizeof(PAGE_LOOKUP_TABLE_ITEM), MM_PAGE_SIZE))) - PageLookupTableStartPage;
328 DbgPrint((DPRINT_MEMORY, "Marking the page lookup table pages as reserved StartPage: %d PageCount: %d\n", PageLookupTableStartPage, PageLookupTablePageCount));
329 MmMarkPagesInLookupTable(PageLookupTable, PageLookupTableStartPage, PageLookupTablePageCount, LoaderFirmwareTemporary);
330 }
331
332 VOID MmMarkPagesInLookupTable(PVOID PageLookupTable, ULONG StartPage, ULONG PageCount, TYPE_OF_MEMORY PageAllocated)
333 {
334 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
335 ULONG Index;
336
337 for (Index=StartPage; Index<(StartPage+PageCount); Index++)
338 {
339 #if 0
340 if ((Index <= (StartPage + 16)) || (Index >= (StartPage+PageCount-16)))
341 {
342 DbgPrint((DPRINT_MEMORY, "Index = %d StartPage = %d PageCount = %d\n", Index, StartPage, PageCount));
343 }
344 #endif
345 RealPageLookupTable[Index].PageAllocated = PageAllocated;
346 RealPageLookupTable[Index].PageAllocationLength = (PageAllocated != LoaderFree) ? 1 : 0;
347 }
348 DbgPrint((DPRINT_MEMORY, "MmMarkPagesInLookupTable() Done\n"));
349 }
350
351 VOID MmAllocatePagesInLookupTable(PVOID PageLookupTable, ULONG StartPage, ULONG PageCount, TYPE_OF_MEMORY MemoryType)
352 {
353 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
354 ULONG Index;
355
356 for (Index=StartPage; Index<(StartPage+PageCount); Index++)
357 {
358 RealPageLookupTable[Index].PageAllocated = MemoryType;
359 RealPageLookupTable[Index].PageAllocationLength = (Index == StartPage) ? PageCount : 0;
360 }
361 }
362
363 ULONG MmCountFreePagesInLookupTable(PVOID PageLookupTable, ULONG TotalPageCount)
364 {
365 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
366 ULONG Index;
367 ULONG FreePageCount;
368
369 FreePageCount = 0;
370 for (Index=0; Index<TotalPageCount; Index++)
371 {
372 if (RealPageLookupTable[Index].PageAllocated == LoaderFree)
373 {
374 FreePageCount++;
375 }
376 }
377
378 return FreePageCount;
379 }
380
381 ULONG MmFindAvailablePages(PVOID PageLookupTable, ULONG TotalPageCount, ULONG PagesNeeded, BOOLEAN FromEnd)
382 {
383 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
384 ULONG AvailablePagesSoFar;
385 ULONG Index;
386
387 if (LastFreePageHint > TotalPageCount)
388 {
389 LastFreePageHint = TotalPageCount;
390 }
391
392 AvailablePagesSoFar = 0;
393 if (FromEnd)
394 {
395 /* Allocate "high" (from end) pages */
396 for (Index=LastFreePageHint-1; Index>0; Index--)
397 {
398 if (RealPageLookupTable[Index].PageAllocated != LoaderFree)
399 {
400 AvailablePagesSoFar = 0;
401 continue;
402 }
403 else
404 {
405 AvailablePagesSoFar++;
406 }
407
408 if (AvailablePagesSoFar >= PagesNeeded)
409 {
410 return Index;
411 }
412 }
413 }
414 else
415 {
416 DbgPrint((DPRINT_MEMORY, "Alloc low memory, LastFreePageHint %d, TPC %d\n", LastFreePageHint, TotalPageCount));
417 /* Allocate "low" pages */
418 for (Index=1; Index < LastFreePageHint; Index++)
419 {
420 if (RealPageLookupTable[Index].PageAllocated != LoaderFree)
421 {
422 AvailablePagesSoFar = 0;
423 continue;
424 }
425 else
426 {
427 AvailablePagesSoFar++;
428 }
429
430 if (AvailablePagesSoFar >= PagesNeeded)
431 {
432 return Index - AvailablePagesSoFar + 1;
433 }
434 }
435 }
436
437 return 0;
438 }
439
440 ULONG MmFindAvailablePagesBeforePage(PVOID PageLookupTable, ULONG TotalPageCount, ULONG PagesNeeded, ULONG LastPage)
441 {
442 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
443 ULONG AvailablePagesSoFar;
444 ULONG Index;
445
446 if (LastPage > TotalPageCount)
447 {
448 return MmFindAvailablePages(PageLookupTable, TotalPageCount, PagesNeeded, TRUE);
449 }
450
451 AvailablePagesSoFar = 0;
452 for (Index=LastPage-1; Index>0; Index--)
453 {
454 if (RealPageLookupTable[Index].PageAllocated != LoaderFree)
455 {
456 AvailablePagesSoFar = 0;
457 continue;
458 }
459 else
460 {
461 AvailablePagesSoFar++;
462 }
463
464 if (AvailablePagesSoFar >= PagesNeeded)
465 {
466 return Index;
467 }
468 }
469
470 return 0;
471 }
472
473 VOID MmFixupSystemMemoryMap(PBIOS_MEMORY_MAP BiosMemoryMap, ULONG* MapCount)
474 {
475 UINT Index;
476 UINT Index2;
477
478 // Loop through each entry in the array
479 for (Index=0; Index<*MapCount; Index++)
480 {
481 // If the entry type isn't usable then remove
482 // it from the memory map (this will help reduce
483 // the size of our lookup table)
484 if (BiosMemoryMap[Index].Type != BiosMemoryUsable)
485 {
486 // Slide every entry after this down one
487 for (Index2=Index; Index2<(*MapCount - 1); Index2++)
488 {
489 BiosMemoryMap[Index2] = BiosMemoryMap[Index2 + 1];
490 }
491 (*MapCount)--;
492 Index--;
493 }
494 }
495 }
496
497 VOID MmUpdateLastFreePageHint(PVOID PageLookupTable, ULONG TotalPageCount)
498 {
499 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
500 ULONG Index;
501
502 for (Index=TotalPageCount-1; Index>0; Index--)
503 {
504 if (RealPageLookupTable[Index].PageAllocated == LoaderFree)
505 {
506 LastFreePageHint = Index + 1;
507 break;
508 }
509 }
510 }
511
512 BOOLEAN MmAreMemoryPagesAvailable(PVOID PageLookupTable, ULONG TotalPageCount, PVOID PageAddress, ULONG PageCount)
513 {
514 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
515 ULONG StartPage;
516 ULONG Index;
517
518 StartPage = MmGetPageNumberFromAddress(PageAddress);
519
520 // Make sure they aren't trying to go past the
521 // end of availabe memory
522 if ((StartPage + PageCount) > TotalPageCount)
523 {
524 return FALSE;
525 }
526
527 for (Index=StartPage; Index<(StartPage + PageCount); Index++)
528 {
529 // If this page is allocated then there obviously isn't
530 // memory availabe so return FALSE
531 if (RealPageLookupTable[Index].PageAllocated != LoaderFree)
532 {
533 return FALSE;
534 }
535 }
536
537 return TRUE;
538 }