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