3 * Copyright (C) 2006-2008 Aleksey Bragin <aleksey@reactos.org>
4 * Copyright (C) 2006-2009 Hervé Poussineau <hpoussin@reactos.org>
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License along
17 * with this program; if not, write to the Free Software Foundation, Inc.,
18 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
24 DBG_DEFAULT_CHANNEL(MEMORY
);
31 } FREELDR_MEMORY_TYPE
, *PFREELDR_MEMORY_TYPE
;
33 FREELDR_MEMORY_TYPE MemoryTypeArray
[] =
35 { LoaderMaximum
, "Unknown memory" },
36 { LoaderFree
, "Free memory" },
37 { LoaderBad
, "Bad memory" },
38 { LoaderLoadedProgram
, "LoadedProgram" },
39 { LoaderFirmwareTemporary
, "FirmwareTemporary" },
40 { LoaderFirmwarePermanent
, "FirmwarePermanent" },
41 { LoaderOsloaderHeap
, "OsloaderHeap" },
42 { LoaderOsloaderStack
, "OsloaderStack" },
43 { LoaderSystemCode
, "SystemCode" },
44 { LoaderHalCode
, "HalCode" },
45 { LoaderBootDriver
, "BootDriver" },
46 { LoaderRegistryData
, "RegistryData" },
47 { LoaderMemoryData
, "MemoryData" },
48 { LoaderNlsData
, "NlsData" },
49 { LoaderSpecialMemory
, "SpecialMemory" },
50 { LoaderReserve
, "Reserve" },
52 ULONG MemoryTypeCount
= sizeof(MemoryTypeArray
) / sizeof(MemoryTypeArray
[0]);
55 PVOID PageLookupTableAddress
= NULL
;
56 PFN_NUMBER TotalPagesInLookupTable
= 0;
57 PFN_NUMBER FreePagesInLookupTable
= 0;
58 PFN_NUMBER LastFreePageHint
= 0;
59 PFN_NUMBER MmLowestPhysicalPage
= 0xFFFFFFFF;
60 PFN_NUMBER MmHighestPhysicalPage
= 0;
62 PFREELDR_MEMORY_DESCRIPTOR BiosMemoryMap
;
63 ULONG BiosMemoryMapEntryCount
;
67 IN OUT PFREELDR_MEMORY_DESCRIPTOR List
,
69 IN PFN_NUMBER BasePage
,
70 IN PFN_NUMBER PageCount
,
71 IN TYPE_OF_MEMORY MemoryType
)
75 TRACE("AddMemoryDescriptor(0x%lx-0x%lx [0x%lx pages])\n",
76 BasePage
, BasePage
+ PageCount
, PageCount
);
78 /* Scan through all existing descriptors */
79 for (i
= 0, c
= 0; (c
< MaxCount
) && (List
[c
].PageCount
!= 0); c
++)
81 /* Count entries completely below the new range */
82 if (List
[i
].BasePage
+ List
[i
].PageCount
<= BasePage
) i
++;
85 /* Check if the list is full */
86 if (c
>= MaxCount
) return c
;
88 /* Is there an existing descriptor starting before the new range */
89 while ((i
< c
) && (List
[i
].BasePage
<= BasePage
))
91 /* The end of the existing one is the minimum for the new range */
92 NextBase
= List
[i
].BasePage
+ List
[i
].PageCount
;
94 /* Bail out, if everything is trimmed away */
95 if ((BasePage
+ PageCount
) <= NextBase
) return c
;
97 /* Trim the naew range at the lower end */
98 PageCount
-= (NextBase
- BasePage
);
101 /* Go to the next entry and repeat */
105 ASSERT(PageCount
> 0);
107 /* Are there still entries above? */
110 /* Shift the following entries one up */
111 RtlMoveMemory(&List
[i
+1], &List
[i
], (c
- i
) * sizeof(List
[0]));
113 /* Insert the new range */
114 List
[i
].BasePage
= BasePage
;
115 List
[i
].PageCount
= min(PageCount
, List
[i
+1].BasePage
- BasePage
);
116 List
[i
].MemoryType
= MemoryType
;
119 TRACE("Inserting at i=%ld: (0x%lx:0x%lx)\n",
120 i
, List
[i
].BasePage
, List
[i
].PageCount
);
122 /* Check if the range was trimmed */
123 if (PageCount
> List
[i
].PageCount
)
125 /* Recursively process the trimmed part */
126 c
= AddMemoryDescriptor(List
,
128 BasePage
+ List
[i
].PageCount
,
129 PageCount
- List
[i
].PageCount
,
135 /* We can simply add the range here */
136 TRACE("Adding i=%ld: (0x%lx:0x%lx)\n", i
, BasePage
, PageCount
);
137 List
[i
].BasePage
= BasePage
;
138 List
[i
].PageCount
= PageCount
;
139 List
[i
].MemoryType
= MemoryType
;
143 /* Return the new count */
147 const FREELDR_MEMORY_DESCRIPTOR
*
148 ArcGetMemoryDescriptor(const FREELDR_MEMORY_DESCRIPTOR
* Current
)
152 return BiosMemoryMap
;
157 if (Current
->PageCount
== 0) return NULL
;
164 MmCheckFreeldrImageFile()
166 PIMAGE_NT_HEADERS NtHeaders
;
167 PIMAGE_FILE_HEADER FileHeader
;
168 PIMAGE_OPTIONAL_HEADER OptionalHeader
;
170 /* Get the NT headers */
171 NtHeaders
= RtlImageNtHeader(&__ImageBase
);
174 ERR("Could not get NtHeaders!\n");
178 /* Check the file header */
179 FileHeader
= &NtHeaders
->FileHeader
;
180 if ((FileHeader
->Machine
!= IMAGE_FILE_MACHINE_NATIVE
) ||
181 (FileHeader
->NumberOfSections
!= FREELDR_SECTION_COUNT
) ||
182 (FileHeader
->PointerToSymbolTable
!= 0) ||
183 (FileHeader
->NumberOfSymbols
!= 0) ||
184 (FileHeader
->SizeOfOptionalHeader
!= sizeof(IMAGE_OPTIONAL_HEADER
)))
186 ERR("FreeLdr FileHeader is invalid.\n");
187 BugCheckInfo
[0] = FileHeader
->Machine
;
188 BugCheckInfo
[1] = FileHeader
->NumberOfSections
;
189 BugCheckInfo
[2] = FileHeader
->PointerToSymbolTable
;
190 BugCheckInfo
[3] = FileHeader
->NumberOfSymbols
;
191 BugCheckInfo
[4] = FileHeader
->SizeOfOptionalHeader
;
195 /* Check the optional header */
196 OptionalHeader
= &NtHeaders
->OptionalHeader
;
197 if ((OptionalHeader
->Magic
!= IMAGE_NT_OPTIONAL_HDR_MAGIC
) ||
198 (OptionalHeader
->Subsystem
!= 1) || // native
199 (OptionalHeader
->ImageBase
!= FREELDR_PE_BASE
) ||
200 (OptionalHeader
->SizeOfImage
> MAX_FREELDR_PE_SIZE
) ||
201 (OptionalHeader
->SectionAlignment
!= OptionalHeader
->FileAlignment
))
203 ERR("FreeLdr OptionalHeader is invalid.\n");
204 BugCheckInfo
[0] = 0x80000000 | (OptionalHeader
->Subsystem
<< 16) | OptionalHeader
->Magic
;
205 BugCheckInfo
[1] = OptionalHeader
->ImageBase
;
206 BugCheckInfo
[2] = OptionalHeader
->SizeOfImage
;
207 BugCheckInfo
[3] = OptionalHeader
->SectionAlignment
;
208 BugCheckInfo
[4] = OptionalHeader
->FileAlignment
;
215 BOOLEAN
MmInitializeMemoryManager(VOID
)
218 const FREELDR_MEMORY_DESCRIPTOR
* MemoryDescriptor
= NULL
;
221 TRACE("Initializing Memory Manager.\n");
223 /* Check the freeldr binary */
224 if (!MmCheckFreeldrImageFile())
226 FrLdrBugCheck(FREELDR_IMAGE_CORRUPTION
);
229 BiosMemoryMap
= MachVtbl
.GetMemoryMap(&BiosMemoryMapEntryCount
);
232 // Dump the system memory map
233 TRACE("System Memory Map (Base Address, Length, Type):\n");
234 while ((MemoryDescriptor
= ArcGetMemoryDescriptor(MemoryDescriptor
)) != NULL
)
236 TRACE("%x\t %x\t %s\n",
237 MemoryDescriptor
->BasePage
* MM_PAGE_SIZE
,
238 MemoryDescriptor
->PageCount
* MM_PAGE_SIZE
,
239 MmGetSystemMemoryMapTypeString(MemoryDescriptor
->MemoryType
));
243 // Find address for the page lookup table
244 TotalPagesInLookupTable
= MmGetAddressablePageCountIncludingHoles();
245 PageLookupTableAddress
= MmFindLocationForPageLookupTable(TotalPagesInLookupTable
);
246 LastFreePageHint
= MmHighestPhysicalPage
;
248 if (PageLookupTableAddress
== 0)
250 // If we get here then we probably couldn't
251 // find a contiguous chunk of memory big
252 // enough to hold the page lookup table
253 printf("Error initializing memory manager!\n");
257 // Initialize the page lookup table
258 MmInitPageLookupTable(PageLookupTableAddress
, TotalPagesInLookupTable
);
260 MmUpdateLastFreePageHint(PageLookupTableAddress
, TotalPagesInLookupTable
);
262 FreePagesInLookupTable
= MmCountFreePagesInLookupTable(PageLookupTableAddress
,
263 TotalPagesInLookupTable
);
265 MmInitializeHeap(PageLookupTableAddress
);
267 TRACE("Memory Manager initialized. 0x%x pages available.\n", FreePagesInLookupTable
);
274 PCSTR
MmGetSystemMemoryMapTypeString(TYPE_OF_MEMORY Type
)
278 for (Index
=1; Index
<MemoryTypeCount
; Index
++)
280 if (MemoryTypeArray
[Index
].Type
== Type
)
282 return MemoryTypeArray
[Index
].TypeString
;
286 return MemoryTypeArray
[0].TypeString
;
290 PFN_NUMBER
MmGetPageNumberFromAddress(PVOID Address
)
292 return ((ULONG_PTR
)Address
) / MM_PAGE_SIZE
;
295 PFN_NUMBER
MmGetAddressablePageCountIncludingHoles(VOID
)
297 const FREELDR_MEMORY_DESCRIPTOR
* MemoryDescriptor
= NULL
;
298 PFN_NUMBER PageCount
;
301 // Go through the whole memory map to get max address
303 while ((MemoryDescriptor
= ArcGetMemoryDescriptor(MemoryDescriptor
)) != NULL
)
306 // Check if we got a higher end page address
308 if (MemoryDescriptor
->BasePage
+ MemoryDescriptor
->PageCount
> MmHighestPhysicalPage
)
311 // Yes, remember it if this is real memory
313 if (MemoryDescriptor
->MemoryType
== LoaderFree
)
314 MmHighestPhysicalPage
= MemoryDescriptor
->BasePage
+ MemoryDescriptor
->PageCount
;
318 // Check if we got a higher (usable) start page address
320 if (MemoryDescriptor
->BasePage
< MmLowestPhysicalPage
)
323 // Yes, remember it if this is real memory
325 MmLowestPhysicalPage
= MemoryDescriptor
->BasePage
;
329 TRACE("lo/hi %lx %lx\n", MmLowestPhysicalPage
, MmHighestPhysicalPage
);
330 PageCount
= MmHighestPhysicalPage
- MmLowestPhysicalPage
;
331 TRACE("MmGetAddressablePageCountIncludingHoles() returning 0x%x\n", PageCount
);
335 PVOID
MmFindLocationForPageLookupTable(PFN_NUMBER TotalPageCount
)
337 const FREELDR_MEMORY_DESCRIPTOR
* MemoryDescriptor
= NULL
;
338 SIZE_T PageLookupTableSize
;
339 PFN_NUMBER PageLookupTablePages
;
340 PFN_NUMBER PageLookupTableStartPage
= 0;
341 PVOID PageLookupTableMemAddress
= NULL
;
343 // Calculate how much pages we need to keep the page lookup table
344 PageLookupTableSize
= TotalPageCount
* sizeof(PAGE_LOOKUP_TABLE_ITEM
);
345 PageLookupTablePages
= PageLookupTableSize
/ MM_PAGE_SIZE
;
347 // Search the highest memory block big enough to contain lookup table
348 while ((MemoryDescriptor
= ArcGetMemoryDescriptor(MemoryDescriptor
)) != NULL
)
350 // Continue, if memory is not free
351 if (MemoryDescriptor
->MemoryType
!= LoaderFree
) continue;
353 // Continue, if the block is not big enough?
354 if (MemoryDescriptor
->PageCount
< PageLookupTablePages
) continue;
356 // Continue, if it is not at a higher address than previous address
357 if (MemoryDescriptor
->BasePage
< PageLookupTableStartPage
) continue;
359 // Continue, if the address is too high
360 if (MemoryDescriptor
->BasePage
>= MM_MAX_PAGE
) continue;
362 // Memory block is more suitable than the previous one
363 PageLookupTableStartPage
= MemoryDescriptor
->BasePage
;
364 PageLookupTableMemAddress
= (PVOID
)((ULONG_PTR
)
365 (MemoryDescriptor
->BasePage
+ MemoryDescriptor
->PageCount
) * MM_PAGE_SIZE
366 - PageLookupTableSize
);
369 TRACE("MmFindLocationForPageLookupTable() returning 0x%x\n", PageLookupTableMemAddress
);
371 return PageLookupTableMemAddress
;
374 VOID
MmInitPageLookupTable(PVOID PageLookupTable
, PFN_NUMBER TotalPageCount
)
376 const FREELDR_MEMORY_DESCRIPTOR
* MemoryDescriptor
= NULL
;
377 PFN_NUMBER PageLookupTableStartPage
;
378 PFN_NUMBER PageLookupTablePageCount
;
380 TRACE("MmInitPageLookupTable()\n");
382 // Mark every page as allocated initially
383 // We will go through and mark pages again according to the memory map
384 // But this will mark any holes not described in the map as allocated
385 MmMarkPagesInLookupTable(PageLookupTable
, MmLowestPhysicalPage
, TotalPageCount
, LoaderFirmwarePermanent
);
387 // Parse the whole memory map
388 while ((MemoryDescriptor
= ArcGetMemoryDescriptor(MemoryDescriptor
)) != NULL
)
390 // Mark used pages in the lookup table
392 if (MemoryDescriptor
->BasePage
+ MemoryDescriptor
->PageCount
<= TotalPageCount
)
394 TRACE("Marking pages 0x%lx-0x%lx as type %s\n",
395 MemoryDescriptor
->BasePage
,
396 MemoryDescriptor
->BasePage
+ MemoryDescriptor
->PageCount
,
397 MmGetSystemMemoryMapTypeString(MemoryDescriptor
->MemoryType
));
398 MmMarkPagesInLookupTable(PageLookupTable
,
399 MemoryDescriptor
->BasePage
,
400 MemoryDescriptor
->PageCount
,
401 MemoryDescriptor
->MemoryType
);
404 TRACE("Ignoring pages 0x%lx-0x%lx (%s)\n",
405 MemoryDescriptor
->BasePage
,
406 MemoryDescriptor
->BasePage
+ MemoryDescriptor
->PageCount
,
407 MmGetSystemMemoryMapTypeString(MemoryDescriptor
->MemoryType
));
410 // Mark the pages that the lookup table occupies as reserved
411 PageLookupTableStartPage
= MmGetPageNumberFromAddress(PageLookupTable
);
412 PageLookupTablePageCount
= MmGetPageNumberFromAddress((PVOID
)((ULONG_PTR
)PageLookupTable
+ ROUND_UP(TotalPageCount
* sizeof(PAGE_LOOKUP_TABLE_ITEM
), MM_PAGE_SIZE
))) - PageLookupTableStartPage
;
413 TRACE("Marking the page lookup table pages as reserved StartPage: 0x%x PageCount: 0x%x\n", PageLookupTableStartPage
, PageLookupTablePageCount
);
414 MmMarkPagesInLookupTable(PageLookupTable
, PageLookupTableStartPage
, PageLookupTablePageCount
, LoaderFirmwareTemporary
);
417 VOID
MmMarkPagesInLookupTable(PVOID PageLookupTable
, PFN_NUMBER StartPage
, PFN_NUMBER PageCount
, TYPE_OF_MEMORY PageAllocated
)
419 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable
= (PPAGE_LOOKUP_TABLE_ITEM
)PageLookupTable
;
421 TRACE("MmMarkPagesInLookupTable()\n");
423 /* Validate the range */
424 if ((StartPage
< MmLowestPhysicalPage
) ||
425 ((StartPage
+ PageCount
- 1) > MmHighestPhysicalPage
))
427 ERR("Memory (0x%lx:0x%lx) outside of lookup table! Valid range: 0x%lx-0x%lx.\n",
428 StartPage
, PageCount
, MmLowestPhysicalPage
, MmHighestPhysicalPage
);
432 StartPage
-= MmLowestPhysicalPage
;
433 for (Index
=StartPage
; Index
<(StartPage
+PageCount
); Index
++)
436 if ((Index
<= (StartPage
+ 16)) || (Index
>= (StartPage
+PageCount
-16)))
438 TRACE("Index = 0x%x StartPage = 0x%x PageCount = 0x%x\n", Index
, StartPage
, PageCount
);
441 RealPageLookupTable
[Index
].PageAllocated
= PageAllocated
;
442 RealPageLookupTable
[Index
].PageAllocationLength
= (PageAllocated
!= LoaderFree
) ? 1 : 0;
444 TRACE("MmMarkPagesInLookupTable() Done\n");
447 VOID
MmAllocatePagesInLookupTable(PVOID PageLookupTable
, PFN_NUMBER StartPage
, PFN_NUMBER PageCount
, TYPE_OF_MEMORY MemoryType
)
449 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable
= (PPAGE_LOOKUP_TABLE_ITEM
)PageLookupTable
;
452 StartPage
-= MmLowestPhysicalPage
;
453 for (Index
=StartPage
; Index
<(StartPage
+PageCount
); Index
++)
455 RealPageLookupTable
[Index
].PageAllocated
= MemoryType
;
456 RealPageLookupTable
[Index
].PageAllocationLength
= (Index
== StartPage
) ? PageCount
: 0;
460 PFN_NUMBER
MmCountFreePagesInLookupTable(PVOID PageLookupTable
, PFN_NUMBER TotalPageCount
)
462 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable
= (PPAGE_LOOKUP_TABLE_ITEM
)PageLookupTable
;
464 PFN_NUMBER FreePageCount
;
467 for (Index
=0; Index
<TotalPageCount
; Index
++)
469 if (RealPageLookupTable
[Index
].PageAllocated
== LoaderFree
)
475 return FreePageCount
;
478 PFN_NUMBER
MmFindAvailablePages(PVOID PageLookupTable
, PFN_NUMBER TotalPageCount
, PFN_NUMBER PagesNeeded
, BOOLEAN FromEnd
)
480 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable
= (PPAGE_LOOKUP_TABLE_ITEM
)PageLookupTable
;
481 PFN_NUMBER AvailablePagesSoFar
;
484 if (LastFreePageHint
> TotalPageCount
)
486 LastFreePageHint
= TotalPageCount
;
489 AvailablePagesSoFar
= 0;
492 /* Allocate "high" (from end) pages */
493 for (Index
=LastFreePageHint
-1; Index
>0; Index
--)
495 if (RealPageLookupTable
[Index
].PageAllocated
!= LoaderFree
)
497 AvailablePagesSoFar
= 0;
502 AvailablePagesSoFar
++;
505 if (AvailablePagesSoFar
>= PagesNeeded
)
507 return Index
+ MmLowestPhysicalPage
;
513 TRACE("Alloc low memory, LastFreePageHint 0x%x, TPC 0x%x\n", LastFreePageHint
, TotalPageCount
);
514 /* Allocate "low" pages */
515 for (Index
=1; Index
< LastFreePageHint
; Index
++)
517 if (RealPageLookupTable
[Index
].PageAllocated
!= LoaderFree
)
519 AvailablePagesSoFar
= 0;
524 AvailablePagesSoFar
++;
527 if (AvailablePagesSoFar
>= PagesNeeded
)
529 return Index
- AvailablePagesSoFar
+ 1 + MmLowestPhysicalPage
;
537 PFN_NUMBER
MmFindAvailablePagesBeforePage(PVOID PageLookupTable
, PFN_NUMBER TotalPageCount
, PFN_NUMBER PagesNeeded
, PFN_NUMBER LastPage
)
539 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable
= (PPAGE_LOOKUP_TABLE_ITEM
)PageLookupTable
;
540 PFN_NUMBER AvailablePagesSoFar
;
543 if (LastPage
> TotalPageCount
)
545 return MmFindAvailablePages(PageLookupTable
, TotalPageCount
, PagesNeeded
, TRUE
);
548 AvailablePagesSoFar
= 0;
549 for (Index
=LastPage
-1; Index
>0; Index
--)
551 if (RealPageLookupTable
[Index
].PageAllocated
!= LoaderFree
)
553 AvailablePagesSoFar
= 0;
558 AvailablePagesSoFar
++;
561 if (AvailablePagesSoFar
>= PagesNeeded
)
563 return Index
+ MmLowestPhysicalPage
;
570 VOID
MmUpdateLastFreePageHint(PVOID PageLookupTable
, PFN_NUMBER TotalPageCount
)
572 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable
= (PPAGE_LOOKUP_TABLE_ITEM
)PageLookupTable
;
575 for (Index
=TotalPageCount
-1; Index
>0; Index
--)
577 if (RealPageLookupTable
[Index
].PageAllocated
== LoaderFree
)
579 LastFreePageHint
= Index
+ 1 + MmLowestPhysicalPage
;
585 BOOLEAN
MmAreMemoryPagesAvailable(PVOID PageLookupTable
, PFN_NUMBER TotalPageCount
, PVOID PageAddress
, PFN_NUMBER PageCount
)
587 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable
= (PPAGE_LOOKUP_TABLE_ITEM
)PageLookupTable
;
588 PFN_NUMBER StartPage
;
591 StartPage
= MmGetPageNumberFromAddress(PageAddress
);
593 if (StartPage
< MmLowestPhysicalPage
) return FALSE
;
595 StartPage
-= MmLowestPhysicalPage
;
597 // Make sure they aren't trying to go past the
598 // end of availabe memory
599 if ((StartPage
+ PageCount
) > TotalPageCount
)
604 for (Index
= StartPage
; Index
< (StartPage
+ PageCount
); Index
++)
606 // If this page is allocated then there obviously isn't
607 // memory availabe so return FALSE
608 if (RealPageLookupTable
[Index
].PageAllocated
!= LoaderFree
)