bb87a9abb268f2883467d74e8f4ac5118147e452
[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 #elif __arm__
110 MmMarkPagesInLookupTable(PageLookupTableAddress, 0x00, 1, LoaderFirmwarePermanent); // arm exception handlers
111 MmMarkPagesInLookupTable(PageLookupTableAddress, 0x01, 7, LoaderFirmwareTemporary); // arm board block + freeldr stack + cmdline
112 MmMarkPagesInLookupTable(PageLookupTableAddress, 0x08, 0x70, LoaderLoadedProgram); // freeldr image (roughly max. 0x64 pages)
113 #endif
114
115 FreePagesInLookupTable = MmCountFreePagesInLookupTable(PageLookupTableAddress, TotalPagesInLookupTable);
116
117 MmInitializeHeap(PageLookupTableAddress);
118
119 DbgPrint((DPRINT_MEMORY, "Memory Manager initialized. %d pages available.\n", FreePagesInLookupTable));
120 return TRUE;
121 }
122
123 VOID MmInitializeHeap(PVOID PageLookupTable)
124 {
125 ULONG PagesNeeded;
126 ULONG HeapStart;
127
128 // HACK: Make it so it doesn't overlap kernel space
129 MmMarkPagesInLookupTable(PageLookupTableAddress, 0x100, 0xFF, LoaderSystemCode);
130
131 // Find contigious memory block for HEAP:STACK
132 PagesNeeded = HEAP_PAGES + STACK_PAGES;
133 HeapStart = MmFindAvailablePages(PageLookupTable, TotalPagesInLookupTable, PagesNeeded, FALSE);
134
135 // Unapply the hack
136 MmMarkPagesInLookupTable(PageLookupTableAddress, 0x100, 0xFF, LoaderFree);
137
138 if (HeapStart == 0)
139 {
140 UiMessageBox("Critical error: Can't allocate heap!");
141 return;
142 }
143
144 // Initialize BGET
145 bpool(HeapStart << MM_PAGE_SHIFT, PagesNeeded << MM_PAGE_SHIFT);
146
147 // Mark those pages as used
148 MmMarkPagesInLookupTable(PageLookupTableAddress, HeapStart, PagesNeeded, LoaderOsloaderHeap);
149
150 DbgPrint((DPRINT_MEMORY, "Heap initialized, base 0x%08x, pages %d\n", (HeapStart << MM_PAGE_SHIFT), PagesNeeded));
151 }
152
153 #ifdef DBG
154 PUCHAR MmGetSystemMemoryMapTypeString(ULONG Type)
155 {
156 ULONG Index;
157
158 for (Index=1; Index<MemoryTypeCount; Index++)
159 {
160 if (MemoryTypeArray[Index].Type == Type)
161 {
162 return MemoryTypeArray[Index].TypeString;
163 }
164 }
165
166 return MemoryTypeArray[0].TypeString;
167 }
168 #endif
169
170 ULONG MmGetPageNumberFromAddress(PVOID Address)
171 {
172 return ((ULONG)Address) / MM_PAGE_SIZE;
173 }
174
175 PVOID MmGetEndAddressOfAnyMemory(PBIOS_MEMORY_MAP BiosMemoryMap, ULONG MapCount)
176 {
177 ULONGLONG MaxStartAddressSoFar;
178 ULONGLONG EndAddressOfMemory;
179 ULONG Index;
180
181 MaxStartAddressSoFar = 0;
182 EndAddressOfMemory = 0;
183 for (Index=0; Index<MapCount; Index++)
184 {
185 if (MaxStartAddressSoFar <= BiosMemoryMap[Index].BaseAddress)
186 {
187 MaxStartAddressSoFar = BiosMemoryMap[Index].BaseAddress;
188 EndAddressOfMemory = (MaxStartAddressSoFar + BiosMemoryMap[Index].Length);
189 if (EndAddressOfMemory > 0xFFFFFFFF)
190 {
191 EndAddressOfMemory = 0xFFFFFFFF;
192 }
193 }
194 }
195
196 DbgPrint((DPRINT_MEMORY, "MmGetEndAddressOfAnyMemory() returning 0x%x\n", (ULONG)EndAddressOfMemory));
197
198 return (PVOID)(ULONG)EndAddressOfMemory;
199 }
200
201 ULONG MmGetAddressablePageCountIncludingHoles(PBIOS_MEMORY_MAP BiosMemoryMap, ULONG MapCount)
202 {
203 ULONG PageCount;
204 ULONGLONG EndAddress;
205
206 EndAddress = (ULONGLONG)(ULONG)MmGetEndAddressOfAnyMemory(BiosMemoryMap, MapCount);
207
208 // Since MmGetEndAddressOfAnyMemory() won't
209 // return addresses higher than 0xFFFFFFFF
210 // then we need to adjust the end address
211 // to 0x100000000 so we don't get an
212 // off-by-one error
213 if (EndAddress >= 0xFFFFFFFF)
214 {
215 EndAddress = 0x100000000LL;
216
217 DbgPrint((DPRINT_MEMORY, "MmGetEndAddressOfAnyMemory() returned 0xFFFFFFFF, correcting to be 0x100000000.\n"));
218 }
219
220 PageCount = (EndAddress / MM_PAGE_SIZE);
221
222 DbgPrint((DPRINT_MEMORY, "MmGetAddressablePageCountIncludingHoles() returning %d\n", PageCount));
223
224 return PageCount;
225 }
226
227 PVOID MmFindLocationForPageLookupTable(PBIOS_MEMORY_MAP BiosMemoryMap, ULONG MapCount)
228 {
229 ULONG TotalPageCount;
230 ULONG PageLookupTableSize;
231 PVOID PageLookupTableMemAddress;
232 int Index;
233 BIOS_MEMORY_MAP TempBiosMemoryMap[32];
234
235 TotalPageCount = MmGetAddressablePageCountIncludingHoles(BiosMemoryMap, MapCount);
236 PageLookupTableSize = TotalPageCount * sizeof(PAGE_LOOKUP_TABLE_ITEM);
237 PageLookupTableMemAddress = 0;
238
239 RtlCopyMemory(TempBiosMemoryMap, BiosMemoryMap, sizeof(BIOS_MEMORY_MAP) * 32);
240 MmSortBiosMemoryMap(TempBiosMemoryMap, MapCount);
241
242 // Find a place, starting from the highest memory
243 // (thus leaving low memory for kernel/drivers)
244 for (Index=(MapCount-1); Index>=0; Index--)
245 {
246 // If this is usable memory with a big enough length
247 // then we'll put our page lookup table here
248
249 // skip if this is not usable region
250 if (TempBiosMemoryMap[Index].Type != BiosMemoryUsable)
251 continue;
252
253 if (TempBiosMemoryMap[Index].Length >= PageLookupTableSize)
254 {
255 PageLookupTableMemAddress = (PVOID)(ULONG)
256 (TempBiosMemoryMap[Index].BaseAddress + (TempBiosMemoryMap[Index].Length - PageLookupTableSize));
257 break;
258 }
259 }
260
261 DbgPrint((DPRINT_MEMORY, "MmFindLocationForPageLookupTable() returning 0x%x\n", PageLookupTableMemAddress));
262
263 return PageLookupTableMemAddress;
264 }
265
266 VOID MmSortBiosMemoryMap(PBIOS_MEMORY_MAP BiosMemoryMap, ULONG MapCount)
267 {
268 ULONG Index;
269 ULONG LoopCount;
270 BIOS_MEMORY_MAP TempMapItem;
271
272 // Loop once for each entry in the memory map minus one
273 // On each loop iteration go through and sort the memory map
274 for (LoopCount=0; LoopCount<(MapCount-1); LoopCount++)
275 {
276 for (Index=0; Index<(MapCount-1); Index++)
277 {
278 if (BiosMemoryMap[Index].BaseAddress > BiosMemoryMap[Index+1].BaseAddress)
279 {
280 TempMapItem = BiosMemoryMap[Index];
281 BiosMemoryMap[Index] = BiosMemoryMap[Index+1];
282 BiosMemoryMap[Index+1] = TempMapItem;
283 }
284 }
285 }
286 }
287
288 VOID MmInitPageLookupTable(PVOID PageLookupTable, ULONG TotalPageCount, PBIOS_MEMORY_MAP BiosMemoryMap, ULONG MapCount)
289 {
290 ULONG MemoryMapStartPage;
291 ULONG MemoryMapEndPage;
292 ULONG MemoryMapPageCount;
293 ULONG MemoryMapPageAllocated;
294 ULONG PageLookupTableStartPage;
295 ULONG PageLookupTablePageCount;
296 ULONG Index;
297
298 DbgPrint((DPRINT_MEMORY, "MmInitPageLookupTable()\n"));
299
300 // Mark every page as allocated initially
301 // We will go through and mark pages again according to the memory map
302 // But this will mark any holes not described in the map as allocated
303 MmMarkPagesInLookupTable(PageLookupTable, 0, TotalPageCount, LoaderFirmwarePermanent);
304
305 for (Index=0; Index<MapCount; Index++)
306 {
307 MemoryMapStartPage = MmGetPageNumberFromAddress((PVOID)(ULONG)BiosMemoryMap[Index].BaseAddress);
308 MemoryMapEndPage = MmGetPageNumberFromAddress((PVOID)(ULONG)(BiosMemoryMap[Index].BaseAddress + BiosMemoryMap[Index].Length - 1));
309 MemoryMapPageCount = (MemoryMapEndPage - MemoryMapStartPage) + 1;
310
311 switch (BiosMemoryMap[Index].Type)
312 {
313 case BiosMemoryUsable:
314 MemoryMapPageAllocated = LoaderFree;
315 break;
316
317 case BiosMemoryAcpiReclaim:
318 case BiosMemoryAcpiNvs:
319 MemoryMapPageAllocated = LoaderSpecialMemory;
320 break;
321
322 default:
323 MemoryMapPageAllocated = LoaderSpecialMemory;
324 }
325 DbgPrint((DPRINT_MEMORY, "Marking pages as type %d: StartPage: %d PageCount: %d\n", MemoryMapPageAllocated, MemoryMapStartPage, MemoryMapPageCount));
326 MmMarkPagesInLookupTable(PageLookupTable, MemoryMapStartPage, MemoryMapPageCount, MemoryMapPageAllocated);
327 }
328
329 // Mark the pages that the lookup table occupies as reserved
330 PageLookupTableStartPage = MmGetPageNumberFromAddress(PageLookupTable);
331 PageLookupTablePageCount = MmGetPageNumberFromAddress((PVOID)((ULONG_PTR)PageLookupTable + ROUND_UP(TotalPageCount * sizeof(PAGE_LOOKUP_TABLE_ITEM), MM_PAGE_SIZE))) - PageLookupTableStartPage;
332 DbgPrint((DPRINT_MEMORY, "Marking the page lookup table pages as reserved StartPage: %d PageCount: %d\n", PageLookupTableStartPage, PageLookupTablePageCount));
333 MmMarkPagesInLookupTable(PageLookupTable, PageLookupTableStartPage, PageLookupTablePageCount, LoaderFirmwareTemporary);
334 }
335
336 VOID MmMarkPagesInLookupTable(PVOID PageLookupTable, ULONG StartPage, ULONG PageCount, TYPE_OF_MEMORY PageAllocated)
337 {
338 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
339 ULONG Index;
340
341 for (Index=StartPage; Index<(StartPage+PageCount); Index++)
342 {
343 #if 0
344 if ((Index <= (StartPage + 16)) || (Index >= (StartPage+PageCount-16)))
345 {
346 DbgPrint((DPRINT_MEMORY, "Index = %d StartPage = %d PageCount = %d\n", Index, StartPage, PageCount));
347 }
348 #endif
349 RealPageLookupTable[Index].PageAllocated = PageAllocated;
350 RealPageLookupTable[Index].PageAllocationLength = (PageAllocated != LoaderFree) ? 1 : 0;
351 }
352 DbgPrint((DPRINT_MEMORY, "MmMarkPagesInLookupTable() Done\n"));
353 }
354
355 VOID MmAllocatePagesInLookupTable(PVOID PageLookupTable, ULONG StartPage, ULONG PageCount, TYPE_OF_MEMORY MemoryType)
356 {
357 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
358 ULONG Index;
359
360 for (Index=StartPage; Index<(StartPage+PageCount); Index++)
361 {
362 RealPageLookupTable[Index].PageAllocated = MemoryType;
363 RealPageLookupTable[Index].PageAllocationLength = (Index == StartPage) ? PageCount : 0;
364 }
365 }
366
367 ULONG MmCountFreePagesInLookupTable(PVOID PageLookupTable, ULONG TotalPageCount)
368 {
369 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
370 ULONG Index;
371 ULONG FreePageCount;
372
373 FreePageCount = 0;
374 for (Index=0; Index<TotalPageCount; Index++)
375 {
376 if (RealPageLookupTable[Index].PageAllocated == LoaderFree)
377 {
378 FreePageCount++;
379 }
380 }
381
382 return FreePageCount;
383 }
384
385 ULONG MmFindAvailablePages(PVOID PageLookupTable, ULONG TotalPageCount, ULONG PagesNeeded, BOOLEAN FromEnd)
386 {
387 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
388 ULONG AvailablePagesSoFar;
389 ULONG Index;
390
391 if (LastFreePageHint > TotalPageCount)
392 {
393 LastFreePageHint = TotalPageCount;
394 }
395
396 AvailablePagesSoFar = 0;
397 if (FromEnd)
398 {
399 /* Allocate "high" (from end) pages */
400 for (Index=LastFreePageHint-1; Index>0; Index--)
401 {
402 if (RealPageLookupTable[Index].PageAllocated != LoaderFree)
403 {
404 AvailablePagesSoFar = 0;
405 continue;
406 }
407 else
408 {
409 AvailablePagesSoFar++;
410 }
411
412 if (AvailablePagesSoFar >= PagesNeeded)
413 {
414 return Index;
415 }
416 }
417 }
418 else
419 {
420 DbgPrint((DPRINT_MEMORY, "Alloc low memory, LastFreePageHint %d, TPC %d\n", LastFreePageHint, TotalPageCount));
421 /* Allocate "low" pages */
422 for (Index=1; Index < LastFreePageHint; Index++)
423 {
424 if (RealPageLookupTable[Index].PageAllocated != LoaderFree)
425 {
426 AvailablePagesSoFar = 0;
427 continue;
428 }
429 else
430 {
431 AvailablePagesSoFar++;
432 }
433
434 if (AvailablePagesSoFar >= PagesNeeded)
435 {
436 return Index - AvailablePagesSoFar + 1;
437 }
438 }
439 }
440
441 return 0;
442 }
443
444 ULONG MmFindAvailablePagesBeforePage(PVOID PageLookupTable, ULONG TotalPageCount, ULONG PagesNeeded, ULONG LastPage)
445 {
446 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
447 ULONG AvailablePagesSoFar;
448 ULONG Index;
449
450 if (LastPage > TotalPageCount)
451 {
452 return MmFindAvailablePages(PageLookupTable, TotalPageCount, PagesNeeded, TRUE);
453 }
454
455 AvailablePagesSoFar = 0;
456 for (Index=LastPage-1; Index>0; Index--)
457 {
458 if (RealPageLookupTable[Index].PageAllocated != LoaderFree)
459 {
460 AvailablePagesSoFar = 0;
461 continue;
462 }
463 else
464 {
465 AvailablePagesSoFar++;
466 }
467
468 if (AvailablePagesSoFar >= PagesNeeded)
469 {
470 return Index;
471 }
472 }
473
474 return 0;
475 }
476
477 VOID MmFixupSystemMemoryMap(PBIOS_MEMORY_MAP BiosMemoryMap, ULONG* MapCount)
478 {
479 UINT Index;
480 UINT Index2;
481
482 // Loop through each entry in the array
483 for (Index=0; Index<*MapCount; Index++)
484 {
485 // If the entry type isn't usable then remove
486 // it from the memory map (this will help reduce
487 // the size of our lookup table)
488 if (BiosMemoryMap[Index].Type != BiosMemoryUsable)
489 {
490 // Slide every entry after this down one
491 for (Index2=Index; Index2<(*MapCount - 1); Index2++)
492 {
493 BiosMemoryMap[Index2] = BiosMemoryMap[Index2 + 1];
494 }
495 (*MapCount)--;
496 Index--;
497 }
498 }
499 }
500
501 VOID MmUpdateLastFreePageHint(PVOID PageLookupTable, ULONG TotalPageCount)
502 {
503 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
504 ULONG Index;
505
506 for (Index=TotalPageCount-1; Index>0; Index--)
507 {
508 if (RealPageLookupTable[Index].PageAllocated == LoaderFree)
509 {
510 LastFreePageHint = Index + 1;
511 break;
512 }
513 }
514 }
515
516 BOOLEAN MmAreMemoryPagesAvailable(PVOID PageLookupTable, ULONG TotalPageCount, PVOID PageAddress, ULONG PageCount)
517 {
518 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
519 ULONG StartPage;
520 ULONG Index;
521
522 StartPage = MmGetPageNumberFromAddress(PageAddress);
523
524 // Make sure they aren't trying to go past the
525 // end of availabe memory
526 if ((StartPage + PageCount) > TotalPageCount)
527 {
528 return FALSE;
529 }
530
531 for (Index=StartPage; Index<(StartPage + PageCount); Index++)
532 {
533 // If this page is allocated then there obviously isn't
534 // memory availabe so return FALSE
535 if (RealPageLookupTable[Index].PageAllocated != LoaderFree)
536 {
537 return FALSE;
538 }
539 }
540
541 return TRUE;
542 }