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