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 == LoaderFree) MmHighestPhysicalPage = MemoryDescriptor->BasePage + MemoryDescriptor->PageCount;
 259         }
 260
 261         //
 262         // Check if we got a higher (usable) start page address
 263         //
 264         if (MemoryDescriptor->BasePage < MmLowestPhysicalPage)
 265         {
 266             //
 267             // Yes, remember it if this is real memory
 268             //
 269             MmLowestPhysicalPage = MemoryDescriptor->BasePage;
 270         }
 271     }
 272
 273     TRACE("lo/hi %lx %lxn", MmLowestPhysicalPage, MmHighestPhysicalPage);
 274     PageCount = MmHighestPhysicalPage - MmLowestPhysicalPage;
 275     TRACE("MmGetAddressablePageCountIncludingHoles() returning 0x%x\n", PageCount);
 276     return PageCount;
 277 }
 278
 279 PVOID MmFindLocationForPageLookupTable(ULONG TotalPageCount)
 280 {
 281     const MEMORY_DESCRIPTOR* MemoryDescriptor = NULL;
 282     ULONG PageLookupTableSize;
 283     ULONG PageLookupTablePages;
 284     ULONG PageLookupTableStartPage = 0;
 285     PVOID PageLookupTableMemAddress = NULL;
 286
 287     // Calculate how much pages we need to keep the page lookup table
 288     PageLookupTableSize = TotalPageCount * sizeof(PAGE_LOOKUP_TABLE_ITEM);
 289     PageLookupTablePages = PageLookupTableSize / MM_PAGE_SIZE;
 290
 291     // Search the highest memory block big enough to contain lookup table
 292     while ((MemoryDescriptor = ArcGetMemoryDescriptor(MemoryDescriptor)) != NULL)
 293     {
 294         // Continue, if memory is not free
 295         if (MemoryDescriptor->MemoryType != LoaderFree) continue;
 296
 297         // Continue, if the block is not big enough?
 298         if (MemoryDescriptor->PageCount < PageLookupTablePages) continue;
 299
 300         // Continue, if it is not at a higher address than previous address
 301         if (MemoryDescriptor->BasePage < PageLookupTableStartPage) continue;
 302
 303         // Continue, if the address is too high
 304         if (MemoryDescriptor->BasePage >= MM_MAX_PAGE) continue;
 305
 306         // Memory block is more suitable than the previous one
 307         PageLookupTableStartPage = MemoryDescriptor->BasePage;
 308         PageLookupTableMemAddress = (PVOID)((ULONG_PTR)
 309             (MemoryDescriptor->BasePage + MemoryDescriptor->PageCount) * MM_PAGE_SIZE
 310             - PageLookupTableSize);
 311     }
 312
 313     TRACE("MmFindLocationForPageLookupTable() returning 0x%x\n", PageLookupTableMemAddress);
 314
 315     return PageLookupTableMemAddress;
 316 }
 317
 318 VOID MmInitPageLookupTable(PVOID PageLookupTable, ULONG TotalPageCount)
 319 {
 320     const MEMORY_DESCRIPTOR* MemoryDescriptor = NULL;
 321     TYPE_OF_MEMORY MemoryMapPageAllocated;
 322     ULONG PageLookupTableStartPage;
 323     ULONG PageLookupTablePageCount;
 324
 325     TRACE("MmInitPageLookupTable()\n");
 326
 327     // Mark every page as allocated initially
 328     // We will go through and mark pages again according to the memory map
 329     // But this will mark any holes not described in the map as allocated
 330     MmMarkPagesInLookupTable(PageLookupTable, MmLowestPhysicalPage, TotalPageCount, LoaderFirmwarePermanent);
 331
 332     // Parse the whole memory map
 333     while ((MemoryDescriptor = ArcGetMemoryDescriptor(MemoryDescriptor)) != NULL)
 334     {
 335         TRACE("Got range: 0x%lx-0x%lx, type=%s\n",
 336               MemoryDescriptor->BasePage,
 337               MemoryDescriptor->BasePage + MemoryDescriptor->PageCount,
 338               MmGetSystemMemoryMapTypeString(MemoryDescriptor->MemoryType));
 339
 340         MemoryMapPageAllocated = MemoryDescriptor->MemoryType;
 341
 342         // Mark used pages in the lookup table
 343         TRACE("Marking pages as type %d: StartPage: %d PageCount: %d\n",
 344               MemoryMapPageAllocated, MemoryDescriptor->BasePage, MemoryDescriptor->PageCount);
 345         MmMarkPagesInLookupTable(PageLookupTable,
 346                                  MemoryDescriptor->BasePage,
 347                                  MemoryDescriptor->PageCount,
 348                                  MemoryMapPageAllocated);
 349     }
 350
 351     // Mark the pages that the lookup table occupies as reserved
 352     PageLookupTableStartPage = MmGetPageNumberFromAddress(PageLookupTable);
 353     PageLookupTablePageCount = MmGetPageNumberFromAddress((PVOID)((ULONG_PTR)PageLookupTable + ROUND_UP(TotalPageCount * sizeof(PAGE_LOOKUP_TABLE_ITEM), MM_PAGE_SIZE))) - PageLookupTableStartPage;
 354     TRACE("Marking the page lookup table pages as reserved StartPage: %d PageCount: %d\n", PageLookupTableStartPage, PageLookupTablePageCount);
 355     MmMarkPagesInLookupTable(PageLookupTable, PageLookupTableStartPage, PageLookupTablePageCount, LoaderFirmwareTemporary);
 356 }
 357
 358 VOID MmMarkPagesInLookupTable(PVOID PageLookupTable, ULONG StartPage, ULONG PageCount, TYPE_OF_MEMORY PageAllocated)
 359 {
 360         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
 361         ULONG                                                   Index;
 362         TRACE("MmMarkPagesInLookupTable()\n");
 363
 364     StartPage -= MmLowestPhysicalPage;
 365         for (Index=StartPage; Index<(StartPage+PageCount); Index++)
 366         {
 367 #if 0
 368                 if ((Index <= (StartPage + 16)) || (Index >= (StartPage+PageCount-16)))
 369                 {
 370                         TRACE("Index = %d StartPage = %d PageCount = %d\n", Index, StartPage, PageCount);
 371                 }
 372 #endif
 373                 RealPageLookupTable[Index].PageAllocated = PageAllocated;
 374                 RealPageLookupTable[Index].PageAllocationLength = (PageAllocated != LoaderFree) ? 1 : 0;
 375         }
 376         TRACE("MmMarkPagesInLookupTable() Done\n");
 377 }
 378
 379 VOID MmAllocatePagesInLookupTable(PVOID PageLookupTable, ULONG StartPage, ULONG PageCount, TYPE_OF_MEMORY MemoryType)
 380 {
 381         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
 382         ULONG                                                   Index;
 383
 384     StartPage -= MmLowestPhysicalPage;
 385         for (Index=StartPage; Index<(StartPage+PageCount); Index++)
 386         {
 387                 RealPageLookupTable[Index].PageAllocated = MemoryType;
 388                 RealPageLookupTable[Index].PageAllocationLength = (Index == StartPage) ? PageCount : 0;
 389         }
 390 }
 391
 392 ULONG MmCountFreePagesInLookupTable(PVOID PageLookupTable, ULONG TotalPageCount)
 393 {
 394         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
 395         ULONG                                                   Index;
 396         ULONG                                                   FreePageCount;
 397
 398         FreePageCount = 0;
 399         for (Index=0; Index<TotalPageCount; Index++)
 400         {
 401                 if (RealPageLookupTable[Index].PageAllocated == LoaderFree)
 402                 {
 403                         FreePageCount++;
 404                 }
 405         }
 406
 407         return FreePageCount;
 408 }
 409
 410 ULONG MmFindAvailablePages(PVOID PageLookupTable, ULONG TotalPageCount, ULONG PagesNeeded, BOOLEAN FromEnd)
 411 {
 412         PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
 413         ULONG AvailablePagesSoFar;
 414         ULONG Index;
 415
 416         if (LastFreePageHint > TotalPageCount)
 417         {
 418                 LastFreePageHint = TotalPageCount;
 419         }
 420
 421         AvailablePagesSoFar = 0;
 422         if (FromEnd)
 423         {
 424                 /* Allocate "high" (from end) pages */
 425                 for (Index=LastFreePageHint-1; Index>0; Index--)
 426                 {
 427                         if (RealPageLookupTable[Index].PageAllocated != LoaderFree)
 428                         {
 429                                 AvailablePagesSoFar = 0;
 430                                 continue;
 431                         }
 432                         else
 433                         {
 434                                 AvailablePagesSoFar++;
 435                         }
 436
 437                         if (AvailablePagesSoFar >= PagesNeeded)
 438                         {
 439                                 return Index + MmLowestPhysicalPage;
 440                         }
 441                 }
 442         }
 443         else
 444         {
 445                 TRACE("Alloc low memory, LastFreePageHint %d, TPC %d\n", LastFreePageHint, TotalPageCount);
 446                 /* Allocate "low" pages */
 447                 for (Index=1; Index < LastFreePageHint; Index++)
 448                 {
 449                         if (RealPageLookupTable[Index].PageAllocated != LoaderFree)
 450                         {
 451                                 AvailablePagesSoFar = 0;
 452                                 continue;
 453                         }
 454                         else
 455                         {
 456                                 AvailablePagesSoFar++;
 457                         }
 458
 459                         if (AvailablePagesSoFar >= PagesNeeded)
 460                         {
 461                                 return Index - AvailablePagesSoFar + 1 + MmLowestPhysicalPage;
 462                         }
 463                 }
 464         }
 465
 466         return 0;
 467 }
 468
 469 ULONG MmFindAvailablePagesBeforePage(PVOID PageLookupTable, ULONG TotalPageCount, ULONG PagesNeeded, ULONG LastPage)
 470 {
 471         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
 472         ULONG                                                   AvailablePagesSoFar;
 473         ULONG                                                   Index;
 474
 475         if (LastPage > TotalPageCount)
 476         {
 477                 return MmFindAvailablePages(PageLookupTable, TotalPageCount, PagesNeeded, TRUE);
 478         }
 479
 480         AvailablePagesSoFar = 0;
 481         for (Index=LastPage-1; Index>0; Index--)
 482         {
 483                 if (RealPageLookupTable[Index].PageAllocated != LoaderFree)
 484                 {
 485                         AvailablePagesSoFar = 0;
 486                         continue;
 487                 }
 488                 else
 489                 {
 490                         AvailablePagesSoFar++;
 491                 }
 492
 493                 if (AvailablePagesSoFar >= PagesNeeded)
 494                 {
 495                         return Index + MmLowestPhysicalPage;
 496                 }
 497         }
 498
 499         return 0;
 500 }
 501
 502 VOID MmUpdateLastFreePageHint(PVOID PageLookupTable, ULONG TotalPageCount)
 503 {
 504         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
 505         ULONG                                                   Index;
 506
 507         for (Index=TotalPageCount-1; Index>0; Index--)
 508         {
 509                 if (RealPageLookupTable[Index].PageAllocated == LoaderFree)
 510                 {
 511                         LastFreePageHint = Index + 1 + MmLowestPhysicalPage;
 512                         break;
 513                 }
 514         }
 515 }
 516
 517 BOOLEAN MmAreMemoryPagesAvailable(PVOID PageLookupTable, ULONG TotalPageCount, PVOID PageAddress, ULONG PageCount)
 518 {
 519         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
 520         ULONG                                                   StartPage;
 521         ULONG                                                   Index;
 522
 523         StartPage = MmGetPageNumberFromAddress(PageAddress);
 524
 525         if (StartPage < MmLowestPhysicalPage) return FALSE;
 526
 527     StartPage -= MmLowestPhysicalPage;
 528
 529         // Make sure they aren't trying to go past the
 530         // end of availabe memory
 531         if ((StartPage + PageCount) > TotalPageCount)
 532         {
 533                 return FALSE;
 534         }
 535
 536         for (Index = StartPage; Index < (StartPage + PageCount); Index++)
 537         {
 538                 // If this page is allocated then there obviously isn't
 539                 // memory availabe so return FALSE
 540                 if (RealPageLookupTable[Index].PageAllocated != LoaderFree)
 541                 {
 542                         return FALSE;
 543                 }
 544         }
 545
 546         return TRUE;
 547 }