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