reactos/boot/freeldr/freeldr/mm/meminit.c

   1 /*
   2  *  FreeLoader
   3  *  Copyright (C) 1998-2003  Brian Palmer  <brianp@sginet.com>
   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 BOOLEAN MmInitializeMemoryManager(VOID)
  47 {
  48         BIOS_MEMORY_MAP BiosMemoryMap[32];
  49         ULONG           BiosMemoryMapEntryCount;
  50 #ifdef DBG
  51         ULONG           Index;
  52 #endif
  53
  54         DbgPrint((DPRINT_MEMORY, "Initializing Memory Manager.\n"));
  55
  56         RtlZeroMemory(BiosMemoryMap, sizeof(BIOS_MEMORY_MAP) * 32);
  57
  58         BiosMemoryMapEntryCount = MachGetMemoryMap(BiosMemoryMap, sizeof(BiosMemoryMap) / sizeof(BIOS_MEMORY_MAP));
  59
  60 #ifdef DBG
  61         // Dump the system memory map
  62         if (BiosMemoryMapEntryCount != 0)
  63         {
  64                 DbgPrint((DPRINT_MEMORY, "System Memory Map (Base Address, Length, Type):\n"));
  65                 for (Index=0; Index<BiosMemoryMapEntryCount; Index++)
  66                 {
  67                         DbgPrint((DPRINT_MEMORY, "%x%x\t %x%x\t %s\n", BiosMemoryMap[Index].BaseAddress, BiosMemoryMap[Index].Length, MmGetSystemMemoryMapTypeString(BiosMemoryMap[Index].Type)));
  68                 }
  69         }
  70 #endif
  71
  72         // If we got the system memory map then fixup invalid entries
  73         if (BiosMemoryMapEntryCount != 0)
  74         {
  75                 MmFixupSystemMemoryMap(BiosMemoryMap, &BiosMemoryMapEntryCount);
  76         }
  77
  78         // Find address for the page lookup table
  79         TotalPagesInLookupTable = MmGetAddressablePageCountIncludingHoles(BiosMemoryMap, BiosMemoryMapEntryCount);
  80         PageLookupTableAddress = MmFindLocationForPageLookupTable(BiosMemoryMap, BiosMemoryMapEntryCount);
  81         LastFreePageHint = TotalPagesInLookupTable;
  82
  83         if (PageLookupTableAddress == 0)
  84         {
  85                 // If we get here then we probably couldn't
  86                 // find a contiguous chunk of memory big
  87                 // enough to hold the page lookup table
  88                 printf("Error initializing memory manager!\n");
  89                 return FALSE;
  90         }
  91
  92         // Initialize the page lookup table
  93         MmInitPageLookupTable(PageLookupTableAddress, TotalPagesInLookupTable, BiosMemoryMap, BiosMemoryMapEntryCount);
  94         MmUpdateLastFreePageHint(PageLookupTableAddress, TotalPagesInLookupTable);
  95
  96         FreePagesInLookupTable = MmCountFreePagesInLookupTable(PageLookupTableAddress, TotalPagesInLookupTable);
  97
  98         DbgPrint((DPRINT_MEMORY, "Memory Manager initialized. %d pages available.\n", FreePagesInLookupTable));
  99         return TRUE;
 100 }
 101
 102 #ifdef DBG
 103 PUCHAR MmGetSystemMemoryMapTypeString(ULONG Type)
 104 {
 105         ULONG           Index;
 106
 107         for (Index=1; Index<MemoryTypeCount; Index++)
 108         {
 109                 if (MemoryTypeArray[Index].Type == Type)
 110                 {
 111                         return MemoryTypeArray[Index].TypeString;
 112                 }
 113         }
 114
 115         return MemoryTypeArray[0].TypeString;
 116 }
 117 #endif
 118
 119 ULONG MmGetPageNumberFromAddress(PVOID Address)
 120 {
 121         return ((ULONG)Address) / MM_PAGE_SIZE;
 122 }
 123
 124 PVOID MmGetEndAddressOfAnyMemory(PBIOS_MEMORY_MAP BiosMemoryMap, ULONG MapCount)
 125 {
 126         ULONGLONG               MaxStartAddressSoFar;
 127         ULONGLONG               EndAddressOfMemory;
 128         ULONG           Index;
 129
 130         MaxStartAddressSoFar = 0;
 131         EndAddressOfMemory = 0;
 132         for (Index=0; Index<MapCount; Index++)
 133         {
 134                 if (MaxStartAddressSoFar <= BiosMemoryMap[Index].BaseAddress)
 135                 {
 136                         MaxStartAddressSoFar = BiosMemoryMap[Index].BaseAddress;
 137                         EndAddressOfMemory = (MaxStartAddressSoFar + BiosMemoryMap[Index].Length);
 138                         if (EndAddressOfMemory > 0xFFFFFFFF)
 139                         {
 140                                 EndAddressOfMemory = 0xFFFFFFFF;
 141                         }
 142                 }
 143         }
 144
 145         DbgPrint((DPRINT_MEMORY, "MmGetEndAddressOfAnyMemory() returning 0x%x\n", (ULONG)EndAddressOfMemory));
 146
 147         return (PVOID)(ULONG)EndAddressOfMemory;
 148 }
 149
 150 ULONG MmGetAddressablePageCountIncludingHoles(PBIOS_MEMORY_MAP BiosMemoryMap, ULONG MapCount)
 151 {
 152         ULONG           PageCount;
 153         ULONGLONG               EndAddress;
 154
 155         EndAddress = (ULONGLONG)(ULONG)MmGetEndAddressOfAnyMemory(BiosMemoryMap, MapCount);
 156
 157         // Since MmGetEndAddressOfAnyMemory() won't
 158         // return addresses higher than 0xFFFFFFFF
 159         // then we need to adjust the end address
 160         // to 0x100000000 so we don't get an
 161         // off-by-one error
 162         if (EndAddress >= 0xFFFFFFFF)
 163         {
 164                 EndAddress = 0x100000000LL;
 165
 166                 DbgPrint((DPRINT_MEMORY, "MmGetEndAddressOfAnyMemory() returned 0xFFFFFFFF, correcting to be 0x100000000.\n"));
 167         }
 168
 169         PageCount = (EndAddress / MM_PAGE_SIZE);
 170
 171         DbgPrint((DPRINT_MEMORY, "MmGetAddressablePageCountIncludingHoles() returning %d\n", PageCount));
 172
 173         return PageCount;
 174 }
 175
 176 PVOID MmFindLocationForPageLookupTable(PBIOS_MEMORY_MAP BiosMemoryMap, ULONG MapCount)
 177 {
 178         ULONG                                   TotalPageCount;
 179         ULONG                                   PageLookupTableSize;
 180         PVOID                           PageLookupTableMemAddress;
 181         int                                     Index;
 182         BIOS_MEMORY_MAP         TempBiosMemoryMap[32];
 183
 184         TotalPageCount = MmGetAddressablePageCountIncludingHoles(BiosMemoryMap, MapCount);
 185         PageLookupTableSize = TotalPageCount * sizeof(PAGE_LOOKUP_TABLE_ITEM);
 186         PageLookupTableMemAddress = 0;
 187
 188         RtlCopyMemory(TempBiosMemoryMap, BiosMemoryMap, sizeof(BIOS_MEMORY_MAP) * 32);
 189         MmSortBiosMemoryMap(TempBiosMemoryMap, MapCount);
 190
 191         for (Index=(MapCount-1); Index>=0; Index--)
 192         {
 193                 // If this is usable memory with a big enough length
 194                 // then we'll put our page lookup table here
 195                 if (TempBiosMemoryMap[Index].Type == BiosMemoryUsable && TempBiosMemoryMap[Index].Length >= PageLookupTableSize)
 196                 {
 197                         PageLookupTableMemAddress = (PVOID)(ULONG)(TempBiosMemoryMap[Index].BaseAddress + (TempBiosMemoryMap[Index].Length - PageLookupTableSize));
 198                         break;
 199                 }
 200         }
 201
 202         DbgPrint((DPRINT_MEMORY, "MmFindLocationForPageLookupTable() returning 0x%x\n", PageLookupTableMemAddress));
 203
 204         return PageLookupTableMemAddress;
 205 }
 206
 207 VOID MmSortBiosMemoryMap(PBIOS_MEMORY_MAP BiosMemoryMap, ULONG MapCount)
 208 {
 209         ULONG                                   Index;
 210         ULONG                                   LoopCount;
 211         BIOS_MEMORY_MAP         TempMapItem;
 212
 213         // Loop once for each entry in the memory map minus one
 214         // On each loop iteration go through and sort the memory map
 215         for (LoopCount=0; LoopCount<(MapCount-1); LoopCount++)
 216         {
 217                 for (Index=0; Index<(MapCount-1); Index++)
 218                 {
 219                         if (BiosMemoryMap[Index].BaseAddress > BiosMemoryMap[Index+1].BaseAddress)
 220                         {
 221                                 TempMapItem = BiosMemoryMap[Index];
 222                                 BiosMemoryMap[Index] = BiosMemoryMap[Index+1];
 223                                 BiosMemoryMap[Index+1] = TempMapItem;
 224                         }
 225                 }
 226         }
 227 }
 228
 229 VOID MmInitPageLookupTable(PVOID PageLookupTable, ULONG TotalPageCount, PBIOS_MEMORY_MAP BiosMemoryMap, ULONG MapCount)
 230 {
 231         ULONG           MemoryMapStartPage;
 232         ULONG           MemoryMapEndPage;
 233         ULONG           MemoryMapPageCount;
 234         ULONG           MemoryMapPageAllocated;
 235         ULONG           PageLookupTableStartPage;
 236         ULONG           PageLookupTablePageCount;
 237         ULONG           Index;
 238
 239         DbgPrint((DPRINT_MEMORY, "MmInitPageLookupTable()\n"));
 240
 241         // Mark every page as allocated initially
 242         // We will go through and mark pages again according to the memory map
 243         // But this will mark any holes not described in the map as allocated
 244         MmMarkPagesInLookupTable(PageLookupTable, 0, TotalPageCount, 1);
 245
 246         for (Index=0; Index<MapCount; Index++)
 247         {
 248                 MemoryMapStartPage = MmGetPageNumberFromAddress((PVOID)(ULONG)BiosMemoryMap[Index].BaseAddress);
 249                 MemoryMapEndPage = MmGetPageNumberFromAddress((PVOID)(ULONG)(BiosMemoryMap[Index].BaseAddress + BiosMemoryMap[Index].Length - 1));
 250                 MemoryMapPageCount = (MemoryMapEndPage - MemoryMapStartPage) + 1;
 251                 MemoryMapPageAllocated = (BiosMemoryMap[Index].Type == BiosMemoryUsable) ? LoaderFree : LoaderFirmwarePermanent;/*BiosMemoryMap[Index].Type*/;
 252                 DbgPrint((DPRINT_MEMORY, "Marking pages as type %d: StartPage: %d PageCount: %d\n", MemoryMapPageAllocated, MemoryMapStartPage, MemoryMapPageCount));
 253                 MmMarkPagesInLookupTable(PageLookupTable, MemoryMapStartPage, MemoryMapPageCount, MemoryMapPageAllocated);
 254         }
 255
 256         // Mark the low memory region below 1MB as reserved (256 pages in region)
 257         DbgPrint((DPRINT_MEMORY, "Marking the low 1MB region as reserved.\n"));
 258         MmMarkPagesInLookupTable(PageLookupTable, 0, 256, LoaderFirmwarePermanent);
 259
 260         // Mark the pages that the lookup table occupies as reserved
 261         PageLookupTableStartPage = MmGetPageNumberFromAddress(PageLookupTable);
 262         PageLookupTablePageCount = MmGetPageNumberFromAddress((PVOID)((ULONG_PTR)PageLookupTable + ROUND_UP(TotalPageCount * sizeof(PAGE_LOOKUP_TABLE_ITEM), MM_PAGE_SIZE))) - PageLookupTableStartPage;
 263         DbgPrint((DPRINT_MEMORY, "Marking the page lookup table pages as reserved StartPage: %d PageCount: %d\n", PageLookupTableStartPage, PageLookupTablePageCount));
 264         MmMarkPagesInLookupTable(PageLookupTable, PageLookupTableStartPage, PageLookupTablePageCount, LoaderFirmwareTemporary);
 265 }
 266
 267 VOID MmMarkPagesInLookupTable(PVOID PageLookupTable, ULONG StartPage, ULONG PageCount, TYPE_OF_MEMORY PageAllocated)
 268 {
 269         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
 270         ULONG                                                   Index;
 271
 272         for (Index=StartPage; Index<(StartPage+PageCount); Index++)
 273         {
 274                 if ((Index <= (StartPage + 16)) || (Index >= (StartPage+PageCount-16)))
 275                 {
 276                         DbgPrint((DPRINT_MEMORY, "Index = %d StartPage = %d PageCount = %d\n", Index, StartPage, PageCount));
 277                 }
 278                 RealPageLookupTable[Index].PageAllocated = PageAllocated;
 279                 RealPageLookupTable[Index].PageAllocationLength = (PageAllocated != LoaderFree) ? 1 : 0;
 280         }
 281         DbgPrint((DPRINT_MEMORY, "MmMarkPagesInLookupTable() Done\n"));
 282 }
 283
 284 VOID MmAllocatePagesInLookupTable(PVOID PageLookupTable, ULONG StartPage, ULONG PageCount)
 285 {
 286         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
 287         ULONG                                                   Index;
 288
 289         for (Index=StartPage; Index<(StartPage+PageCount); Index++)
 290         {
 291                 RealPageLookupTable[Index].PageAllocated = LoaderSystemCode;
 292                 RealPageLookupTable[Index].PageAllocationLength = (Index == StartPage) ? PageCount : 0;
 293         }
 294 }
 295
 296 ULONG MmCountFreePagesInLookupTable(PVOID PageLookupTable, ULONG TotalPageCount)
 297 {
 298         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
 299         ULONG                                                   Index;
 300         ULONG                                                   FreePageCount;
 301
 302         FreePageCount = 0;
 303         for (Index=0; Index<TotalPageCount; Index++)
 304         {
 305                 if (RealPageLookupTable[Index].PageAllocated == LoaderFree)
 306                 {
 307                         FreePageCount++;
 308                 }
 309         }
 310
 311         return FreePageCount;
 312 }
 313
 314 ULONG MmFindAvailablePages(PVOID PageLookupTable, ULONG TotalPageCount, ULONG PagesNeeded, BOOLEAN FromEnd)
 315 {
 316         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
 317         ULONG                                                   AvailablePagesSoFar;
 318         ULONG                                                   Index;
 319
 320         if (LastFreePageHint > TotalPageCount)
 321         {
 322                 LastFreePageHint = TotalPageCount;
 323         }
 324
 325         AvailablePagesSoFar = 0;
 326         if (FromEnd)
 327         {
 328                 /* Allocate "high" (from end) pages */
 329                 for (Index=LastFreePageHint-1; Index>0; Index--)
 330                 {
 331                         if (RealPageLookupTable[Index].PageAllocated != LoaderFree)
 332                         {
 333                                 AvailablePagesSoFar = 0;
 334                                 continue;
 335                         }
 336                         else
 337                         {
 338                                 AvailablePagesSoFar++;
 339                         }
 340
 341                         if (AvailablePagesSoFar >= PagesNeeded)
 342                         {
 343                                 return Index;
 344                         }
 345                 }
 346         }
 347         else
 348         {
 349                 DbgPrint((DPRINT_MEMORY, "Alloc low memory, LastFreePageHint %d, TPC %d\n", LastFreePageHint, TotalPageCount));
 350                 /* Allocate "low" pages */
 351                 for (Index=1; Index < LastFreePageHint; Index++)
 352                 {
 353                         if (RealPageLookupTable[Index].PageAllocated != LoaderFree)
 354                         {
 355                                 AvailablePagesSoFar = 0;
 356                                 continue;
 357                         }
 358                         else
 359                         {
 360                                 AvailablePagesSoFar++;
 361                         }
 362
 363                         if (AvailablePagesSoFar >= PagesNeeded)
 364                         {
 365                                 return Index - AvailablePagesSoFar + 1;
 366                         }
 367                 }
 368         }
 369
 370         return 0;
 371 }
 372
 373 ULONG MmFindAvailablePagesBeforePage(PVOID PageLookupTable, ULONG TotalPageCount, ULONG PagesNeeded, ULONG LastPage)
 374 {
 375         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
 376         ULONG                                                   AvailablePagesSoFar;
 377         ULONG                                                   Index;
 378
 379         if (LastPage > TotalPageCount)
 380         {
 381                 return MmFindAvailablePages(PageLookupTable, TotalPageCount, PagesNeeded, TRUE);
 382         }
 383
 384         AvailablePagesSoFar = 0;
 385         for (Index=LastPage-1; Index>0; Index--)
 386         {
 387                 if (RealPageLookupTable[Index].PageAllocated != LoaderFree)
 388                 {
 389                         AvailablePagesSoFar = 0;
 390                         continue;
 391                 }
 392                 else
 393                 {
 394                         AvailablePagesSoFar++;
 395                 }
 396
 397                 if (AvailablePagesSoFar >= PagesNeeded)
 398                 {
 399                         return Index;
 400                 }
 401         }
 402
 403         return 0;
 404 }
 405
 406 VOID MmFixupSystemMemoryMap(PBIOS_MEMORY_MAP BiosMemoryMap, ULONG* MapCount)
 407 {
 408         UINT            Index;
 409         UINT            Index2;
 410
 411         // Loop through each entry in the array
 412         for (Index=0; Index<*MapCount; Index++)
 413         {
 414                 // If the entry type isn't usable then remove
 415                 // it from the memory map (this will help reduce
 416                 // the size of our lookup table)
 417                 if (BiosMemoryMap[Index].Type != BiosMemoryUsable)
 418                 {
 419                         // Slide every entry after this down one
 420                         for (Index2=Index; Index2<(*MapCount - 1); Index2++)
 421                         {
 422                                 BiosMemoryMap[Index2] = BiosMemoryMap[Index2 + 1];
 423                         }
 424                         (*MapCount)--;
 425                         Index--;
 426                 }
 427         }
 428 }
 429
 430 VOID MmUpdateLastFreePageHint(PVOID PageLookupTable, ULONG TotalPageCount)
 431 {
 432         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
 433         ULONG                                                   Index;
 434
 435         for (Index=TotalPageCount-1; Index>0; Index--)
 436         {
 437                 if (RealPageLookupTable[Index].PageAllocated == LoaderFree)
 438                 {
 439                         LastFreePageHint = Index + 1;
 440                         break;
 441                 }
 442         }
 443 }
 444
 445 BOOLEAN MmAreMemoryPagesAvailable(PVOID PageLookupTable, ULONG TotalPageCount, PVOID PageAddress, ULONG PageCount)
 446 {
 447         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
 448         ULONG                                                   StartPage;
 449         ULONG                                                   Index;
 450
 451         StartPage = MmGetPageNumberFromAddress(PageAddress);
 452
 453         // Make sure they aren't trying to go past the
 454         // end of availabe memory
 455         if ((StartPage + PageCount) > TotalPageCount)
 456         {
 457                 return FALSE;
 458         }
 459
 460         for (Index=StartPage; Index<(StartPage + PageCount); Index++)
 461         {
 462                 // If this page is allocated then there obviously isn't
 463                 // memory availabe so return FALSE
 464                 if (RealPageLookupTable[Index].PageAllocated != LoaderFree)
 465                 {
 466                         return FALSE;
 467                 }
 468         }
 469
 470         return TRUE;
 471 }