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