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