- Revert 44301
[reactos.git] / boot / freeldr / freeldr / mm / meminit.c
1 /*
2 * FreeLoader
3 * Copyright (C) 2006-2008 Aleksey Bragin <aleksey@reactos.org>
4 * Copyright (C) 2006-2009 Hervé Poussineau <hpoussin@reactos.org>
5 *
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.
10 *
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.
15 *
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.
19 */
20
21 #include <freeldr.h>
22 #include <debug.h>
23
24 #if DBG
25 typedef struct
26 {
27 MEMORY_TYPE Type;
28 PCSTR TypeString;
29 } FREELDR_MEMORY_TYPE, *PFREELDR_MEMORY_TYPE;
30
31 FREELDR_MEMORY_TYPE MemoryTypeArray[] =
32 {
33 { MemoryMaximum, "Unknown memory" },
34 { MemoryExceptionBlock, "Exception block" },
35 { MemorySystemBlock, "System block" },
36 { MemoryFree, "Free memory" },
37 { MemoryBad, "Bad memory" },
38 { MemoryLoadedProgram, "Loaded program" },
39 { MemoryFirmwareTemporary, "Firmware temporary" },
40 { MemoryFirmwarePermanent, "Firmware permanent" },
41 { MemoryFreeContiguous, "Free contiguous memory" },
42 { MemorySpecialMemory, "Special memory" },
43 };
44 ULONG MemoryTypeCount = sizeof(MemoryTypeArray) / sizeof(MemoryTypeArray[0]);
45 #endif
46
47 PVOID PageLookupTableAddress = NULL;
48 ULONG TotalPagesInLookupTable = 0;
49 ULONG FreePagesInLookupTable = 0;
50 ULONG LastFreePageHint = 0;
51
52 extern ULONG_PTR MmHeapPointer;
53 extern ULONG_PTR MmHeapStart;
54
55 BOOLEAN MmInitializeMemoryManager(VOID)
56 {
57 #if DBG
58 MEMORY_DESCRIPTOR* MemoryDescriptor = NULL;
59 #endif
60
61 DPRINTM(DPRINT_MEMORY, "Initializing Memory Manager.\n");
62
63 #if DBG
64 // Dump the system memory map
65 DPRINTM(DPRINT_MEMORY, "System Memory Map (Base Address, Length, Type):\n");
66 while ((MemoryDescriptor = ArcGetMemoryDescriptor(MemoryDescriptor)) != NULL)
67 {
68 DPRINTM(DPRINT_MEMORY, "%x\t %x\t %s\n",
69 MemoryDescriptor->BasePage * MM_PAGE_SIZE,
70 MemoryDescriptor->PageCount * MM_PAGE_SIZE,
71 MmGetSystemMemoryMapTypeString(MemoryDescriptor->MemoryType));
72 }
73 #endif
74
75 // Find address for the page lookup table
76 TotalPagesInLookupTable = MmGetAddressablePageCountIncludingHoles();
77 PageLookupTableAddress = MmFindLocationForPageLookupTable(TotalPagesInLookupTable);
78 LastFreePageHint = TotalPagesInLookupTable;
79
80 if (PageLookupTableAddress == 0)
81 {
82 // If we get here then we probably couldn't
83 // find a contiguous chunk of memory big
84 // enough to hold the page lookup table
85 printf("Error initializing memory manager!\n");
86 return FALSE;
87 }
88
89 // Initialize the page lookup table
90 MmInitPageLookupTable(PageLookupTableAddress, TotalPagesInLookupTable);
91 MmUpdateLastFreePageHint(PageLookupTableAddress, TotalPagesInLookupTable);
92
93 FreePagesInLookupTable = MmCountFreePagesInLookupTable(PageLookupTableAddress, TotalPagesInLookupTable);
94
95 MmInitializeHeap(PageLookupTableAddress);
96
97 DPRINTM(DPRINT_MEMORY, "Memory Manager initialized. %d pages available.\n", FreePagesInLookupTable);
98 return TRUE;
99 }
100
101 VOID MmInitializeHeap(PVOID PageLookupTable)
102 {
103 ULONG PagesNeeded;
104 ULONG HeapStart;
105
106 // HACK: Make it so it doesn't overlap kernel space
107 MmMarkPagesInLookupTable(PageLookupTableAddress, 0x100, 0xFF, LoaderSystemCode);
108
109 // Find contigious memory block for HEAP:STACK
110 PagesNeeded = HEAP_PAGES + STACK_PAGES;
111 HeapStart = MmFindAvailablePages(PageLookupTable, TotalPagesInLookupTable, PagesNeeded, FALSE);
112
113 // Unapply the hack
114 MmMarkPagesInLookupTable(PageLookupTableAddress, 0x100, 0xFF, LoaderFree);
115
116 if (HeapStart == 0)
117 {
118 UiMessageBox("Critical error: Can't allocate heap!");
119 return;
120 }
121
122 // Initialize BGET
123 bpool(HeapStart << MM_PAGE_SHIFT, PagesNeeded << MM_PAGE_SHIFT);
124
125 // Mark those pages as used
126 MmMarkPagesInLookupTable(PageLookupTableAddress, HeapStart, PagesNeeded, LoaderOsloaderHeap);
127
128 DPRINTM(DPRINT_MEMORY, "Heap initialized, base 0x%08x, pages %d\n", (HeapStart << MM_PAGE_SHIFT), PagesNeeded);
129 }
130
131 #if DBG
132 PCSTR MmGetSystemMemoryMapTypeString(MEMORY_TYPE Type)
133 {
134 ULONG Index;
135
136 for (Index=1; Index<MemoryTypeCount; Index++)
137 {
138 if (MemoryTypeArray[Index].Type == Type)
139 {
140 return MemoryTypeArray[Index].TypeString;
141 }
142 }
143
144 return MemoryTypeArray[0].TypeString;
145 }
146 #endif
147
148 ULONG MmGetPageNumberFromAddress(PVOID Address)
149 {
150 return ((ULONG_PTR)Address) / MM_PAGE_SIZE;
151 }
152
153 ULONG MmGetAddressablePageCountIncludingHoles(VOID)
154 {
155 MEMORY_DESCRIPTOR* MemoryDescriptor = NULL;
156 ULONG EndPage = 0;
157
158 //
159 // Go through the whole memory map to get max address
160 //
161 while ((MemoryDescriptor = ArcGetMemoryDescriptor(MemoryDescriptor)) != NULL)
162 {
163 //
164 // Check if we got a higher end page address
165 //
166 if (MemoryDescriptor->BasePage + MemoryDescriptor->PageCount > EndPage)
167 {
168 //
169 // Yes, remember it
170 //
171 EndPage = MemoryDescriptor->BasePage + MemoryDescriptor->PageCount;
172 }
173 }
174
175 DPRINTM(DPRINT_MEMORY, "MmGetAddressablePageCountIncludingHoles() returning 0x%x\n", EndPage);
176
177 return EndPage;
178 }
179
180 PVOID MmFindLocationForPageLookupTable(ULONG TotalPageCount)
181 {
182 MEMORY_DESCRIPTOR* MemoryDescriptor = NULL;
183 ULONG PageLookupTableSize;
184 ULONG PageLookupTablePages;
185 ULONG PageLookupTableStartPage = 0;
186 PVOID PageLookupTableMemAddress = NULL;
187
188 //
189 // Calculate how much pages we need to keep the page lookup table
190 //
191 PageLookupTableSize = TotalPageCount * sizeof(PAGE_LOOKUP_TABLE_ITEM);
192 PageLookupTablePages = PageLookupTableSize / MM_PAGE_SIZE;
193
194 //
195 // Search the highest memory block big enough to contain lookup table
196 //
197 while ((MemoryDescriptor = ArcGetMemoryDescriptor(MemoryDescriptor)) != NULL)
198 {
199 //
200 // Is it suitable memory?
201 //
202 if (MemoryDescriptor->MemoryType != MemoryFree)
203 {
204 //
205 // No. Process next descriptor
206 //
207 continue;
208 }
209
210 //
211 // Is the block big enough?
212 //
213 if (MemoryDescriptor->PageCount < PageLookupTablePages)
214 {
215 //
216 // No. Process next descriptor
217 //
218 continue;
219 }
220
221 //
222 // Is it at a higher address than previous suitable address?
223 //
224 if (MemoryDescriptor->BasePage < PageLookupTableStartPage)
225 {
226 //
227 // No. Process next descriptor
228 //
229 continue;
230 }
231
232 //
233 // Memory block is more suitable than the previous one
234 //
235 PageLookupTableStartPage = MemoryDescriptor->BasePage;
236 PageLookupTableMemAddress = (PVOID)((ULONG_PTR)
237 (MemoryDescriptor->BasePage + MemoryDescriptor->PageCount) * MM_PAGE_SIZE
238 - PageLookupTableSize);
239 }
240
241 DPRINTM(DPRINT_MEMORY, "MmFindLocationForPageLookupTable() returning 0x%x\n", PageLookupTableMemAddress);
242
243 return PageLookupTableMemAddress;
244 }
245
246 VOID MmInitPageLookupTable(PVOID PageLookupTable, ULONG TotalPageCount)
247 {
248 MEMORY_DESCRIPTOR* MemoryDescriptor = NULL;
249 TYPE_OF_MEMORY MemoryMapPageAllocated;
250 ULONG PageLookupTableStartPage;
251 ULONG PageLookupTablePageCount;
252
253 DPRINTM(DPRINT_MEMORY, "MmInitPageLookupTable()\n");
254
255 //
256 // Mark every page as allocated initially
257 // We will go through and mark pages again according to the memory map
258 // But this will mark any holes not described in the map as allocated
259 //
260 MmMarkPagesInLookupTable(PageLookupTable, 0, TotalPageCount, LoaderFirmwarePermanent);
261
262 //
263 // Parse the whole memory map
264 //
265 while ((MemoryDescriptor = ArcGetMemoryDescriptor(MemoryDescriptor)) != NULL)
266 {
267 //
268 // Convert ARC memory type to loader memory type
269 //
270 switch (MemoryDescriptor->MemoryType)
271 {
272 case MemoryFree:
273 {
274 //
275 // Allocatable memory
276 //
277 MemoryMapPageAllocated = LoaderFree;
278 break;
279 }
280 case MemoryFirmwarePermanent:
281 {
282 //
283 // Firmware permanent memory
284 //
285 MemoryMapPageAllocated = LoaderFirmwarePermanent;
286 break;
287 }
288 case MemoryFirmwareTemporary:
289 {
290 //
291 // Firmware temporary memory
292 //
293 MemoryMapPageAllocated = LoaderFirmwareTemporary;
294 break;
295 }
296 case MemoryLoadedProgram:
297 {
298 //
299 // Bootloader code
300 //
301 MemoryMapPageAllocated = LoaderLoadedProgram;
302 break;
303 }
304 case MemorySpecialMemory:
305 {
306 //
307 // Special reserved memory
308 //
309 MemoryMapPageAllocated = LoaderSpecialMemory;
310 break;
311 }
312 default:
313 {
314 //
315 // Put something sensible here, which won't be overwritten
316 //
317 MemoryMapPageAllocated = LoaderSpecialMemory;
318 break;
319 }
320 }
321
322 //
323 // Mark used pages in the lookup table
324 //
325 DPRINTM(DPRINT_MEMORY, "Marking pages as type %d: StartPage: %d PageCount: %d\n", MemoryMapPageAllocated, MemoryDescriptor->BasePage, MemoryDescriptor->PageCount);
326 MmMarkPagesInLookupTable(PageLookupTable, MemoryDescriptor->BasePage, MemoryDescriptor->PageCount, MemoryMapPageAllocated);
327 }
328
329 //
330 // Mark the pages that the lookup table occupies as reserved
331 //
332 PageLookupTableStartPage = MmGetPageNumberFromAddress(PageLookupTable);
333 PageLookupTablePageCount = MmGetPageNumberFromAddress((PVOID)((ULONG_PTR)PageLookupTable + ROUND_UP(TotalPageCount * sizeof(PAGE_LOOKUP_TABLE_ITEM), MM_PAGE_SIZE))) - PageLookupTableStartPage;
334 DPRINTM(DPRINT_MEMORY, "Marking the page lookup table pages as reserved StartPage: %d PageCount: %d\n", PageLookupTableStartPage, PageLookupTablePageCount);
335 MmMarkPagesInLookupTable(PageLookupTable, PageLookupTableStartPage, PageLookupTablePageCount, LoaderFirmwareTemporary);
336 }
337
338 VOID MmMarkPagesInLookupTable(PVOID PageLookupTable, ULONG StartPage, ULONG PageCount, TYPE_OF_MEMORY PageAllocated)
339 {
340 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
341 ULONG Index;
342
343 for (Index=StartPage; Index<(StartPage+PageCount); Index++)
344 {
345 #if 0
346 if ((Index <= (StartPage + 16)) || (Index >= (StartPage+PageCount-16)))
347 {
348 DPRINTM(DPRINT_MEMORY, "Index = %d StartPage = %d PageCount = %d\n", Index, StartPage, PageCount);
349 }
350 #endif
351 RealPageLookupTable[Index].PageAllocated = PageAllocated;
352 RealPageLookupTable[Index].PageAllocationLength = (PageAllocated != LoaderFree) ? 1 : 0;
353 }
354 DPRINTM(DPRINT_MEMORY, "MmMarkPagesInLookupTable() Done\n");
355 }
356
357 VOID MmAllocatePagesInLookupTable(PVOID PageLookupTable, ULONG StartPage, ULONG PageCount, TYPE_OF_MEMORY MemoryType)
358 {
359 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
360 ULONG Index;
361
362 for (Index=StartPage; Index<(StartPage+PageCount); Index++)
363 {
364 RealPageLookupTable[Index].PageAllocated = MemoryType;
365 RealPageLookupTable[Index].PageAllocationLength = (Index == StartPage) ? PageCount : 0;
366 }
367 }
368
369 ULONG MmCountFreePagesInLookupTable(PVOID PageLookupTable, ULONG TotalPageCount)
370 {
371 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
372 ULONG Index;
373 ULONG FreePageCount;
374
375 FreePageCount = 0;
376 for (Index=0; Index<TotalPageCount; Index++)
377 {
378 if (RealPageLookupTable[Index].PageAllocated == LoaderFree)
379 {
380 FreePageCount++;
381 }
382 }
383
384 return FreePageCount;
385 }
386
387 ULONG MmFindAvailablePages(PVOID PageLookupTable, ULONG TotalPageCount, ULONG PagesNeeded, BOOLEAN FromEnd)
388 {
389 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
390 ULONG AvailablePagesSoFar;
391 ULONG Index;
392
393 if (LastFreePageHint > TotalPageCount)
394 {
395 LastFreePageHint = TotalPageCount;
396 }
397
398 AvailablePagesSoFar = 0;
399 if (FromEnd)
400 {
401 /* Allocate "high" (from end) pages */
402 for (Index=LastFreePageHint-1; Index>0; Index--)
403 {
404 if (RealPageLookupTable[Index].PageAllocated != LoaderFree)
405 {
406 AvailablePagesSoFar = 0;
407 continue;
408 }
409 else
410 {
411 AvailablePagesSoFar++;
412 }
413
414 if (AvailablePagesSoFar >= PagesNeeded)
415 {
416 return Index;
417 }
418 }
419 }
420 else
421 {
422 DPRINTM(DPRINT_MEMORY, "Alloc low memory, LastFreePageHint %d, TPC %d\n", LastFreePageHint, TotalPageCount);
423 /* Allocate "low" pages */
424 for (Index=1; Index < LastFreePageHint; Index++)
425 {
426 if (RealPageLookupTable[Index].PageAllocated != LoaderFree)
427 {
428 AvailablePagesSoFar = 0;
429 continue;
430 }
431 else
432 {
433 AvailablePagesSoFar++;
434 }
435
436 if (AvailablePagesSoFar >= PagesNeeded)
437 {
438 return Index - AvailablePagesSoFar + 1;
439 }
440 }
441 }
442
443 return 0;
444 }
445
446 ULONG MmFindAvailablePagesBeforePage(PVOID PageLookupTable, ULONG TotalPageCount, ULONG PagesNeeded, ULONG LastPage)
447 {
448 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
449 ULONG AvailablePagesSoFar;
450 ULONG Index;
451
452 if (LastPage > TotalPageCount)
453 {
454 return MmFindAvailablePages(PageLookupTable, TotalPageCount, PagesNeeded, TRUE);
455 }
456
457 AvailablePagesSoFar = 0;
458 for (Index=LastPage-1; Index>0; Index--)
459 {
460 if (RealPageLookupTable[Index].PageAllocated != LoaderFree)
461 {
462 AvailablePagesSoFar = 0;
463 continue;
464 }
465 else
466 {
467 AvailablePagesSoFar++;
468 }
469
470 if (AvailablePagesSoFar >= PagesNeeded)
471 {
472 return Index;
473 }
474 }
475
476 return 0;
477 }
478
479 VOID MmUpdateLastFreePageHint(PVOID PageLookupTable, ULONG TotalPageCount)
480 {
481 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
482 ULONG Index;
483
484 for (Index=TotalPageCount-1; Index>0; Index--)
485 {
486 if (RealPageLookupTable[Index].PageAllocated == LoaderFree)
487 {
488 LastFreePageHint = Index + 1;
489 break;
490 }
491 }
492 }
493
494 BOOLEAN MmAreMemoryPagesAvailable(PVOID PageLookupTable, ULONG TotalPageCount, PVOID PageAddress, ULONG PageCount)
495 {
496 PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
497 ULONG StartPage;
498 ULONG Index;
499
500 StartPage = MmGetPageNumberFromAddress(PageAddress);
501
502 // Make sure they aren't trying to go past the
503 // end of availabe memory
504 if ((StartPage + PageCount) > TotalPageCount)
505 {
506 return FALSE;
507 }
508
509 for (Index=StartPage; Index<(StartPage + PageCount); Index++)
510 {
511 // If this page is allocated then there obviously isn't
512 // memory availabe so return FALSE
513 if (RealPageLookupTable[Index].PageAllocated != LoaderFree)
514 {
515 return FALSE;
516 }
517 }
518
519 return TRUE;
520 }