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