3 * Copyright (C) 2006-2008 Aleksey Bragin <aleksey@reactos.org>
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.
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.
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.
28 } FREELDR_MEMORY_TYPE
, *PFREELDR_MEMORY_TYPE
;
30 ULONG MemoryTypeCount
= 5;
31 FREELDR_MEMORY_TYPE MemoryTypeArray
[] =
33 { 0, "Unknown Memory" },
34 { BiosMemoryUsable
, "Usable Memory" },
35 { BiosMemoryReserved
, "Reserved Memory" },
36 { BiosMemoryAcpiReclaim
, "ACPI Reclaim Memory" },
37 { BiosMemoryAcpiNvs
, "ACPI NVS Memory" },
41 PVOID PageLookupTableAddress
= NULL
;
42 ULONG TotalPagesInLookupTable
= 0;
43 ULONG FreePagesInLookupTable
= 0;
44 ULONG LastFreePageHint
= 0;
46 extern ULONG_PTR MmHeapPointer
;
47 extern ULONG_PTR MmHeapStart
;
49 BOOLEAN
MmInitializeMemoryManager(VOID
)
51 BIOS_MEMORY_MAP BiosMemoryMap
[32];
52 ULONG BiosMemoryMapEntryCount
;
57 DbgPrint((DPRINT_MEMORY
, "Initializing Memory Manager.\n"));
59 RtlZeroMemory(BiosMemoryMap
, sizeof(BIOS_MEMORY_MAP
) * 32);
61 BiosMemoryMapEntryCount
= MachGetMemoryMap(BiosMemoryMap
, sizeof(BiosMemoryMap
) / sizeof(BIOS_MEMORY_MAP
));
64 // Dump the system memory map
65 if (BiosMemoryMapEntryCount
!= 0)
67 DbgPrint((DPRINT_MEMORY
, "System Memory Map (Base Address, Length, Type):\n"));
68 for (Index
=0; Index
<BiosMemoryMapEntryCount
; Index
++)
70 DbgPrint((DPRINT_MEMORY
, "%x%x\t %x%x\t %s\n", BiosMemoryMap
[Index
].BaseAddress
, BiosMemoryMap
[Index
].Length
, MmGetSystemMemoryMapTypeString(BiosMemoryMap
[Index
].Type
)));
75 // If we got the system memory map then fixup invalid entries
76 if (BiosMemoryMapEntryCount
!= 0)
78 MmFixupSystemMemoryMap(BiosMemoryMap
, &BiosMemoryMapEntryCount
);
81 // Find address for the page lookup table
82 TotalPagesInLookupTable
= MmGetAddressablePageCountIncludingHoles(BiosMemoryMap
, BiosMemoryMapEntryCount
);
83 PageLookupTableAddress
= MmFindLocationForPageLookupTable(BiosMemoryMap
, BiosMemoryMapEntryCount
);
84 LastFreePageHint
= TotalPagesInLookupTable
;
86 if (PageLookupTableAddress
== 0)
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");
95 // Initialize the page lookup table
96 MmInitPageLookupTable(PageLookupTableAddress
, TotalPagesInLookupTable
, BiosMemoryMap
, BiosMemoryMapEntryCount
);
97 MmUpdateLastFreePageHint(PageLookupTableAddress
, TotalPagesInLookupTable
);
99 // Add machine-dependent stuff
100 #if defined (__i386__) || defined (_M_AMD64)
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
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)
115 FreePagesInLookupTable
= MmCountFreePagesInLookupTable(PageLookupTableAddress
, TotalPagesInLookupTable
);
117 MmInitializeHeap(PageLookupTableAddress
);
119 DbgPrint((DPRINT_MEMORY
, "Memory Manager initialized. %d pages available.\n", FreePagesInLookupTable
));
123 VOID
MmInitializeHeap(PVOID PageLookupTable
)
128 // HACK: Make it so it doesn't overlap kernel space
129 MmMarkPagesInLookupTable(PageLookupTableAddress
, 0x100, 0xFF, LoaderSystemCode
);
131 // Find contigious memory block for HEAP:STACK
132 PagesNeeded
= HEAP_PAGES
+ STACK_PAGES
;
133 HeapStart
= MmFindAvailablePages(PageLookupTable
, TotalPagesInLookupTable
, PagesNeeded
, FALSE
);
136 MmMarkPagesInLookupTable(PageLookupTableAddress
, 0x100, 0xFF, LoaderFree
);
140 UiMessageBox("Critical error: Can't allocate heap!");
145 bpool(HeapStart
<< MM_PAGE_SHIFT
, PagesNeeded
<< MM_PAGE_SHIFT
);
147 // Mark those pages as used
148 MmMarkPagesInLookupTable(PageLookupTableAddress
, HeapStart
, PagesNeeded
, LoaderOsloaderHeap
);
150 DbgPrint((DPRINT_MEMORY
, "Heap initialized, base 0x%08x, pages %d\n", (HeapStart
<< MM_PAGE_SHIFT
), PagesNeeded
));
154 PUCHAR
MmGetSystemMemoryMapTypeString(ULONG Type
)
158 for (Index
=1; Index
<MemoryTypeCount
; Index
++)
160 if (MemoryTypeArray
[Index
].Type
== Type
)
162 return MemoryTypeArray
[Index
].TypeString
;
166 return MemoryTypeArray
[0].TypeString
;
170 ULONG
MmGetPageNumberFromAddress(PVOID Address
)
172 return ((ULONG_PTR
)Address
) / MM_PAGE_SIZE
;
175 PVOID
MmGetEndAddressOfAnyMemory(PBIOS_MEMORY_MAP BiosMemoryMap
, ULONG MapCount
)
177 ULONGLONG MaxStartAddressSoFar
;
178 ULONGLONG EndAddressOfMemory
;
181 MaxStartAddressSoFar
= 0;
182 EndAddressOfMemory
= 0;
183 for (Index
=0; Index
<MapCount
; Index
++)
185 if (MaxStartAddressSoFar
<= BiosMemoryMap
[Index
].BaseAddress
)
187 MaxStartAddressSoFar
= BiosMemoryMap
[Index
].BaseAddress
;
188 EndAddressOfMemory
= (MaxStartAddressSoFar
+ BiosMemoryMap
[Index
].Length
);
189 if (EndAddressOfMemory
> 0xFFFFFFFF)
191 EndAddressOfMemory
= 0xFFFFFFFF;
196 DbgPrint((DPRINT_MEMORY
, "MmGetEndAddressOfAnyMemory() returning 0x%x\n", (ULONG
)EndAddressOfMemory
));
198 return (PVOID
)(ULONG_PTR
)EndAddressOfMemory
;
201 ULONG
MmGetAddressablePageCountIncludingHoles(PBIOS_MEMORY_MAP BiosMemoryMap
, ULONG MapCount
)
204 ULONGLONG EndAddress
;
206 EndAddress
= (ULONGLONG
)(ULONG_PTR
)MmGetEndAddressOfAnyMemory(BiosMemoryMap
, MapCount
);
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
213 if (EndAddress
>= 0xFFFFFFFF)
215 EndAddress
= 0x100000000LL
;
217 DbgPrint((DPRINT_MEMORY
, "MmGetEndAddressOfAnyMemory() returned 0xFFFFFFFF, correcting to be 0x100000000.\n"));
220 PageCount
= (EndAddress
/ MM_PAGE_SIZE
);
222 DbgPrint((DPRINT_MEMORY
, "MmGetAddressablePageCountIncludingHoles() returning %d\n", PageCount
));
227 PVOID
MmFindLocationForPageLookupTable(PBIOS_MEMORY_MAP BiosMemoryMap
, ULONG MapCount
)
229 ULONG TotalPageCount
;
230 ULONG PageLookupTableSize
;
231 PVOID PageLookupTableMemAddress
;
233 BIOS_MEMORY_MAP TempBiosMemoryMap
[32];
235 TotalPageCount
= MmGetAddressablePageCountIncludingHoles(BiosMemoryMap
, MapCount
);
236 PageLookupTableSize
= TotalPageCount
* sizeof(PAGE_LOOKUP_TABLE_ITEM
);
237 PageLookupTableMemAddress
= 0;
239 RtlCopyMemory(TempBiosMemoryMap
, BiosMemoryMap
, sizeof(BIOS_MEMORY_MAP
) * 32);
240 MmSortBiosMemoryMap(TempBiosMemoryMap
, MapCount
);
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
--)
246 // If this is usable memory with a big enough length
247 // then we'll put our page lookup table here
249 // skip if this is not usable region
250 if (TempBiosMemoryMap
[Index
].Type
!= BiosMemoryUsable
)
253 if (TempBiosMemoryMap
[Index
].Length
>= PageLookupTableSize
)
255 PageLookupTableMemAddress
= (PVOID
)(ULONG_PTR
)
256 (TempBiosMemoryMap
[Index
].BaseAddress
+ (TempBiosMemoryMap
[Index
].Length
- PageLookupTableSize
));
261 DbgPrint((DPRINT_MEMORY
, "MmFindLocationForPageLookupTable() returning 0x%x\n", PageLookupTableMemAddress
));
263 return PageLookupTableMemAddress
;
266 VOID
MmSortBiosMemoryMap(PBIOS_MEMORY_MAP BiosMemoryMap
, ULONG MapCount
)
270 BIOS_MEMORY_MAP TempMapItem
;
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
++)
276 for (Index
=0; Index
<(MapCount
-1); Index
++)
278 if (BiosMemoryMap
[Index
].BaseAddress
> BiosMemoryMap
[Index
+1].BaseAddress
)
280 TempMapItem
= BiosMemoryMap
[Index
];
281 BiosMemoryMap
[Index
] = BiosMemoryMap
[Index
+1];
282 BiosMemoryMap
[Index
+1] = TempMapItem
;
288 VOID
MmInitPageLookupTable(PVOID PageLookupTable
, ULONG TotalPageCount
, PBIOS_MEMORY_MAP BiosMemoryMap
, ULONG MapCount
)
290 ULONG MemoryMapStartPage
;
291 ULONG MemoryMapEndPage
;
292 ULONG MemoryMapPageCount
;
293 ULONG MemoryMapPageAllocated
;
294 ULONG PageLookupTableStartPage
;
295 ULONG PageLookupTablePageCount
;
298 DbgPrint((DPRINT_MEMORY
, "MmInitPageLookupTable()\n"));
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
);
305 for (Index
=0; Index
<MapCount
; Index
++)
307 MemoryMapStartPage
= MmGetPageNumberFromAddress((PVOID
)(ULONG_PTR
)BiosMemoryMap
[Index
].BaseAddress
);
308 MemoryMapEndPage
= MmGetPageNumberFromAddress((PVOID
)(ULONG_PTR
)(BiosMemoryMap
[Index
].BaseAddress
+ BiosMemoryMap
[Index
].Length
- 1));
309 MemoryMapPageCount
= (MemoryMapEndPage
- MemoryMapStartPage
) + 1;
311 switch (BiosMemoryMap
[Index
].Type
)
313 case BiosMemoryUsable
:
314 MemoryMapPageAllocated
= LoaderFree
;
317 case BiosMemoryAcpiReclaim
:
318 case BiosMemoryAcpiNvs
:
319 MemoryMapPageAllocated
= LoaderSpecialMemory
;
323 MemoryMapPageAllocated
= LoaderSpecialMemory
;
325 DbgPrint((DPRINT_MEMORY
, "Marking pages as type %d: StartPage: %d PageCount: %d\n", MemoryMapPageAllocated
, MemoryMapStartPage
, MemoryMapPageCount
));
326 MmMarkPagesInLookupTable(PageLookupTable
, MemoryMapStartPage
, MemoryMapPageCount
, MemoryMapPageAllocated
);
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
);
336 VOID
MmMarkPagesInLookupTable(PVOID PageLookupTable
, ULONG StartPage
, ULONG PageCount
, TYPE_OF_MEMORY PageAllocated
)
338 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable
= (PPAGE_LOOKUP_TABLE_ITEM
)PageLookupTable
;
341 for (Index
=StartPage
; Index
<(StartPage
+PageCount
); Index
++)
344 if ((Index
<= (StartPage
+ 16)) || (Index
>= (StartPage
+PageCount
-16)))
346 DbgPrint((DPRINT_MEMORY
, "Index = %d StartPage = %d PageCount = %d\n", Index
, StartPage
, PageCount
));
349 RealPageLookupTable
[Index
].PageAllocated
= PageAllocated
;
350 RealPageLookupTable
[Index
].PageAllocationLength
= (PageAllocated
!= LoaderFree
) ? 1 : 0;
352 DbgPrint((DPRINT_MEMORY
, "MmMarkPagesInLookupTable() Done\n"));
355 VOID
MmAllocatePagesInLookupTable(PVOID PageLookupTable
, ULONG StartPage
, ULONG PageCount
, TYPE_OF_MEMORY MemoryType
)
357 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable
= (PPAGE_LOOKUP_TABLE_ITEM
)PageLookupTable
;
360 for (Index
=StartPage
; Index
<(StartPage
+PageCount
); Index
++)
362 RealPageLookupTable
[Index
].PageAllocated
= MemoryType
;
363 RealPageLookupTable
[Index
].PageAllocationLength
= (Index
== StartPage
) ? PageCount
: 0;
367 ULONG
MmCountFreePagesInLookupTable(PVOID PageLookupTable
, ULONG TotalPageCount
)
369 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable
= (PPAGE_LOOKUP_TABLE_ITEM
)PageLookupTable
;
374 for (Index
=0; Index
<TotalPageCount
; Index
++)
376 if (RealPageLookupTable
[Index
].PageAllocated
== LoaderFree
)
382 return FreePageCount
;
385 ULONG
MmFindAvailablePages(PVOID PageLookupTable
, ULONG TotalPageCount
, ULONG PagesNeeded
, BOOLEAN FromEnd
)
387 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable
= (PPAGE_LOOKUP_TABLE_ITEM
)PageLookupTable
;
388 ULONG AvailablePagesSoFar
;
391 if (LastFreePageHint
> TotalPageCount
)
393 LastFreePageHint
= TotalPageCount
;
396 AvailablePagesSoFar
= 0;
399 /* Allocate "high" (from end) pages */
400 for (Index
=LastFreePageHint
-1; Index
>0; Index
--)
402 if (RealPageLookupTable
[Index
].PageAllocated
!= LoaderFree
)
404 AvailablePagesSoFar
= 0;
409 AvailablePagesSoFar
++;
412 if (AvailablePagesSoFar
>= PagesNeeded
)
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
++)
424 if (RealPageLookupTable
[Index
].PageAllocated
!= LoaderFree
)
426 AvailablePagesSoFar
= 0;
431 AvailablePagesSoFar
++;
434 if (AvailablePagesSoFar
>= PagesNeeded
)
436 return Index
- AvailablePagesSoFar
+ 1;
444 ULONG
MmFindAvailablePagesBeforePage(PVOID PageLookupTable
, ULONG TotalPageCount
, ULONG PagesNeeded
, ULONG LastPage
)
446 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable
= (PPAGE_LOOKUP_TABLE_ITEM
)PageLookupTable
;
447 ULONG AvailablePagesSoFar
;
450 if (LastPage
> TotalPageCount
)
452 return MmFindAvailablePages(PageLookupTable
, TotalPageCount
, PagesNeeded
, TRUE
);
455 AvailablePagesSoFar
= 0;
456 for (Index
=LastPage
-1; Index
>0; Index
--)
458 if (RealPageLookupTable
[Index
].PageAllocated
!= LoaderFree
)
460 AvailablePagesSoFar
= 0;
465 AvailablePagesSoFar
++;
468 if (AvailablePagesSoFar
>= PagesNeeded
)
477 VOID
MmFixupSystemMemoryMap(PBIOS_MEMORY_MAP BiosMemoryMap
, ULONG
* MapCount
)
482 // Loop through each entry in the array
483 for (Index
=0; Index
<*MapCount
; Index
++)
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
)
490 // Slide every entry after this down one
491 for (Index2
=Index
; Index2
<(*MapCount
- 1); Index2
++)
493 BiosMemoryMap
[Index2
] = BiosMemoryMap
[Index2
+ 1];
501 VOID
MmUpdateLastFreePageHint(PVOID PageLookupTable
, ULONG TotalPageCount
)
503 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable
= (PPAGE_LOOKUP_TABLE_ITEM
)PageLookupTable
;
506 for (Index
=TotalPageCount
-1; Index
>0; Index
--)
508 if (RealPageLookupTable
[Index
].PageAllocated
== LoaderFree
)
510 LastFreePageHint
= Index
+ 1;
516 BOOLEAN
MmAreMemoryPagesAvailable(PVOID PageLookupTable
, ULONG TotalPageCount
, PVOID PageAddress
, ULONG PageCount
)
518 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable
= (PPAGE_LOOKUP_TABLE_ITEM
)PageLookupTable
;
522 StartPage
= MmGetPageNumberFromAddress(PageAddress
);
524 // Make sure they aren't trying to go past the
525 // end of availabe memory
526 if ((StartPage
+ PageCount
) > TotalPageCount
)
531 for (Index
=StartPage
; Index
<(StartPage
+ PageCount
); Index
++)
533 // If this page is allocated then there obviously isn't
534 // memory availabe so return FALSE
535 if (RealPageLookupTable
[Index
].PageAllocated
!= LoaderFree
)