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