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 PFREELDR_MEMORY_DESCRIPTOR BiosMemoryMap;
  63 ULONG BiosMemoryMapEntryCount;
  64
  65 extern ULONG_PTR        MmHeapPointer;
  66 extern ULONG_PTR        MmHeapStart;
  67
  68 ULONG
  69 AddMemoryDescriptor(
  70     IN OUT PFREELDR_MEMORY_DESCRIPTOR List,
  71     IN ULONG MaxCount,
  72     IN PFN_NUMBER BasePage,
  73     IN PFN_NUMBER PageCount,
  74     IN TYPE_OF_MEMORY 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 FREELDR_MEMORY_DESCRIPTOR*
 151 ArcGetMemoryDescriptor(const FREELDR_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 FREELDR_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. 0x%x 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 FREELDR_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)
 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 %lx\n", 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 FREELDR_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 != LoaderFree) 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 FREELDR_MEMORY_DESCRIPTOR* MemoryDescriptor = NULL;
 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         // Mark used pages in the lookup table
 336
 337         if (MemoryDescriptor->BasePage + MemoryDescriptor->PageCount <= TotalPageCount)
 338         {
 339             TRACE("Marking pages 0x%lx-0x%lx as type %s\n",
 340                   MemoryDescriptor->BasePage,
 341                   MemoryDescriptor->BasePage + MemoryDescriptor->PageCount,
 342                   MmGetSystemMemoryMapTypeString(MemoryDescriptor->MemoryType));
 343             MmMarkPagesInLookupTable(PageLookupTable,
 344                                      MemoryDescriptor->BasePage,
 345                                      MemoryDescriptor->PageCount,
 346                                      MemoryDescriptor->MemoryType);
 347         }
 348         else
 349             TRACE("Ignoring pages 0x%lx-0x%lx (%s)\n",
 350                   MemoryDescriptor->BasePage,
 351                   MemoryDescriptor->BasePage + MemoryDescriptor->PageCount,
 352                   MmGetSystemMemoryMapTypeString(MemoryDescriptor->MemoryType));
 353     }
 354
 355     // Mark the pages that the lookup table occupies as reserved
 356     PageLookupTableStartPage = MmGetPageNumberFromAddress(PageLookupTable);
 357     PageLookupTablePageCount = MmGetPageNumberFromAddress((PVOID)((ULONG_PTR)PageLookupTable + ROUND_UP(TotalPageCount * sizeof(PAGE_LOOKUP_TABLE_ITEM), MM_PAGE_SIZE))) - PageLookupTableStartPage;
 358     TRACE("Marking the page lookup table pages as reserved StartPage: 0x%x PageCount: 0x%x\n", PageLookupTableStartPage, PageLookupTablePageCount);
 359     MmMarkPagesInLookupTable(PageLookupTable, PageLookupTableStartPage, PageLookupTablePageCount, LoaderFirmwareTemporary);
 360 }
 361
 362 VOID MmMarkPagesInLookupTable(PVOID PageLookupTable, ULONG StartPage, ULONG PageCount, TYPE_OF_MEMORY PageAllocated)
 363 {
 364         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
 365         ULONG                                                   Index;
 366         TRACE("MmMarkPagesInLookupTable()\n");
 367
 368     /* Validate the range */
 369     if ((StartPage < MmLowestPhysicalPage) ||
 370         ((StartPage + PageCount - 1) > MmHighestPhysicalPage))
 371     {
 372         ERR("Memory (0x%lx:0x%lx) outside of lookup table! Valid range: 0x%lx-0x%lx.\n",
 373             StartPage, PageCount, MmLowestPhysicalPage, MmHighestPhysicalPage);
 374         return;
 375     }
 376
 377     StartPage -= MmLowestPhysicalPage;
 378         for (Index=StartPage; Index<(StartPage+PageCount); Index++)
 379         {
 380 #if 0
 381                 if ((Index <= (StartPage + 16)) || (Index >= (StartPage+PageCount-16)))
 382                 {
 383                         TRACE("Index = 0x%x StartPage = 0x%x PageCount = 0x%x\n", Index, StartPage, PageCount);
 384                 }
 385 #endif
 386                 RealPageLookupTable[Index].PageAllocated = PageAllocated;
 387                 RealPageLookupTable[Index].PageAllocationLength = (PageAllocated != LoaderFree) ? 1 : 0;
 388         }
 389         TRACE("MmMarkPagesInLookupTable() Done\n");
 390 }
 391
 392 VOID MmAllocatePagesInLookupTable(PVOID PageLookupTable, ULONG StartPage, ULONG PageCount, TYPE_OF_MEMORY MemoryType)
 393 {
 394         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
 395         ULONG                                                   Index;
 396
 397     StartPage -= MmLowestPhysicalPage;
 398         for (Index=StartPage; Index<(StartPage+PageCount); Index++)
 399         {
 400                 RealPageLookupTable[Index].PageAllocated = MemoryType;
 401                 RealPageLookupTable[Index].PageAllocationLength = (Index == StartPage) ? PageCount : 0;
 402         }
 403 }
 404
 405 ULONG MmCountFreePagesInLookupTable(PVOID PageLookupTable, ULONG TotalPageCount)
 406 {
 407         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
 408         ULONG                                                   Index;
 409         ULONG                                                   FreePageCount;
 410
 411         FreePageCount = 0;
 412         for (Index=0; Index<TotalPageCount; Index++)
 413         {
 414                 if (RealPageLookupTable[Index].PageAllocated == LoaderFree)
 415                 {
 416                         FreePageCount++;
 417                 }
 418         }
 419
 420         return FreePageCount;
 421 }
 422
 423 ULONG MmFindAvailablePages(PVOID PageLookupTable, ULONG TotalPageCount, ULONG PagesNeeded, BOOLEAN FromEnd)
 424 {
 425         PPAGE_LOOKUP_TABLE_ITEM RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
 426         ULONG AvailablePagesSoFar;
 427         ULONG Index;
 428
 429         if (LastFreePageHint > TotalPageCount)
 430         {
 431                 LastFreePageHint = TotalPageCount;
 432         }
 433
 434         AvailablePagesSoFar = 0;
 435         if (FromEnd)
 436         {
 437                 /* Allocate "high" (from end) pages */
 438                 for (Index=LastFreePageHint-1; Index>0; Index--)
 439                 {
 440                         if (RealPageLookupTable[Index].PageAllocated != LoaderFree)
 441                         {
 442                                 AvailablePagesSoFar = 0;
 443                                 continue;
 444                         }
 445                         else
 446                         {
 447                                 AvailablePagesSoFar++;
 448                         }
 449
 450                         if (AvailablePagesSoFar >= PagesNeeded)
 451                         {
 452                                 return Index + MmLowestPhysicalPage;
 453                         }
 454                 }
 455         }
 456         else
 457         {
 458                 TRACE("Alloc low memory, LastFreePageHint 0x%x, TPC 0x%x\n", LastFreePageHint, TotalPageCount);
 459                 /* Allocate "low" pages */
 460                 for (Index=1; Index < LastFreePageHint; Index++)
 461                 {
 462                         if (RealPageLookupTable[Index].PageAllocated != LoaderFree)
 463                         {
 464                                 AvailablePagesSoFar = 0;
 465                                 continue;
 466                         }
 467                         else
 468                         {
 469                                 AvailablePagesSoFar++;
 470                         }
 471
 472                         if (AvailablePagesSoFar >= PagesNeeded)
 473                         {
 474                                 return Index - AvailablePagesSoFar + 1 + MmLowestPhysicalPage;
 475                         }
 476                 }
 477         }
 478
 479         return 0;
 480 }
 481
 482 ULONG MmFindAvailablePagesBeforePage(PVOID PageLookupTable, ULONG TotalPageCount, ULONG PagesNeeded, ULONG LastPage)
 483 {
 484         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
 485         ULONG                                                   AvailablePagesSoFar;
 486         ULONG                                                   Index;
 487
 488         if (LastPage > TotalPageCount)
 489         {
 490                 return MmFindAvailablePages(PageLookupTable, TotalPageCount, PagesNeeded, TRUE);
 491         }
 492
 493         AvailablePagesSoFar = 0;
 494         for (Index=LastPage-1; Index>0; Index--)
 495         {
 496                 if (RealPageLookupTable[Index].PageAllocated != LoaderFree)
 497                 {
 498                         AvailablePagesSoFar = 0;
 499                         continue;
 500                 }
 501                 else
 502                 {
 503                         AvailablePagesSoFar++;
 504                 }
 505
 506                 if (AvailablePagesSoFar >= PagesNeeded)
 507                 {
 508                         return Index + MmLowestPhysicalPage;
 509                 }
 510         }
 511
 512         return 0;
 513 }
 514
 515 VOID MmUpdateLastFreePageHint(PVOID PageLookupTable, ULONG TotalPageCount)
 516 {
 517         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
 518         ULONG                                                   Index;
 519
 520         for (Index=TotalPageCount-1; Index>0; Index--)
 521         {
 522                 if (RealPageLookupTable[Index].PageAllocated == LoaderFree)
 523                 {
 524                         LastFreePageHint = Index + 1 + MmLowestPhysicalPage;
 525                         break;
 526                 }
 527         }
 528 }
 529
 530 BOOLEAN MmAreMemoryPagesAvailable(PVOID PageLookupTable, ULONG TotalPageCount, PVOID PageAddress, ULONG PageCount)
 531 {
 532         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTable;
 533         ULONG                                                   StartPage;
 534         ULONG                                                   Index;
 535
 536         StartPage = MmGetPageNumberFromAddress(PageAddress);
 537
 538         if (StartPage < MmLowestPhysicalPage) return FALSE;
 539
 540     StartPage -= MmLowestPhysicalPage;
 541
 542         // Make sure they aren't trying to go past the
 543         // end of availabe memory
 544         if ((StartPage + PageCount) > TotalPageCount)
 545         {
 546                 return FALSE;
 547         }
 548
 549         for (Index = StartPage; Index < (StartPage + PageCount); Index++)
 550         {
 551                 // If this page is allocated then there obviously isn't
 552                 // memory availabe so return FALSE
 553                 if (RealPageLookupTable[Index].PageAllocated != LoaderFree)
 554                 {
 555                         return FALSE;
 556                 }
 557         }
 558
 559         return TRUE;
 560 }