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