reactos/boot/freeldr/freeldr/mm/mm.c

   1 /*
   2  *  FreeLoader
   3  *  Copyright (C) 1998-2003  Brian Palmer  <brianp@sginet.com>
   4  *
   5  *  This program is free software; you can redistribute it and/or modify
   6  *  it under the terms of the GNU General Public License as published by
   7  *  the Free Software Foundation; either version 2 of the License, or
   8  *  (at your option) any later version.
   9  *
  10  *  This program is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  *  GNU General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU General Public License
  16  *  along with this program; if not, write to the Free Software
  17  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18  */
  19
  20 #include <freeldr.h>
  21 #include <debug.h>
  22
  23 ULONG                   AllocationCount = 0;
  24
  25 #ifdef DBG
  26 VOID            VerifyHeap(VOID);
  27 VOID            DumpMemoryAllocMap(VOID);
  28 VOID            IncrementAllocationCount(VOID);
  29 VOID            DecrementAllocationCount(VOID);
  30 VOID            MemAllocTest(VOID);
  31 #endif // DBG
  32
  33 /*
  34  * Hack alert
  35  * Normally, we allocate whole pages. This is ofcourse wastefull for small
  36  * allocations (a few bytes). So, for small allocations (smaller than a page)
  37  * we sub-allocate. When the first small allocation is done, a page is
  38  * requested. We keep a pointer to that page in SubAllocationPage. The alloc
  39  * is satisfied by returning a pointer to the beginning of the page. We also
  40  * keep track of how many bytes are still available in the page in SubAllocationRest.
  41  * When the next small request comes in, we try to allocate it just after the
  42  * memory previously allocated. If it won't fit, we allocate a new page and
  43  * the whole process starts again.
  44  * Note that suballocations are done back-to-back, there's no bookkeeping at all.
  45  * That also means that we cannot really free suballocations. So, when a free is
  46  * done and it is determined that this might be a free of a sub-allocation, we
  47  * just no-op the free.
  48  * Perhaps we should use the heap routines from ntdll here.
  49  */
  50 static PVOID    SubAllocationPage = NULL;
  51 static unsigned SubAllocationRest = 0;
  52
  53 BOOLEAN AllocateFromEnd = TRUE;
  54
  55 VOID MmChangeAllocationPolicy(BOOLEAN PolicyAllocatePagesFromEnd)
  56 {
  57         AllocateFromEnd = PolicyAllocatePagesFromEnd;
  58 }
  59
  60 PVOID MmAllocateMemoryWithType(ULONG MemorySize, TYPE_OF_MEMORY MemoryType)
  61 {
  62         ULONG   PagesNeeded;
  63         ULONG   FirstFreePageFromEnd;
  64         PVOID   MemPointer;
  65
  66         if (MemorySize == 0)
  67         {
  68                 DbgPrint((DPRINT_MEMORY, "MmAllocateMemory() called for 0 bytes. Returning NULL.\n"));
  69                 UiMessageBoxCritical("Memory allocation failed: MmAllocateMemory() called for 0 bytes.");
  70                 return NULL;
  71         }
  72
  73         MemorySize = ROUND_UP(MemorySize, 4);
  74         if (MemorySize <= SubAllocationRest)
  75         {
  76                 MemPointer = (PVOID)((ULONG_PTR)SubAllocationPage + MM_PAGE_SIZE - SubAllocationRest);
  77                 SubAllocationRest -= MemorySize;
  78                 return MemPointer;
  79         }
  80
  81         // Find out how many blocks it will take to
  82         // satisfy this allocation
  83         PagesNeeded = ROUND_UP(MemorySize, MM_PAGE_SIZE) / MM_PAGE_SIZE;
  84
  85         // If we don't have enough available mem
  86         // then return NULL
  87         if (FreePagesInLookupTable < PagesNeeded)
  88         {
  89                 DbgPrint((DPRINT_MEMORY, "Memory allocation failed in MmAllocateMemory(). Not enough free memory to allocate %d bytes. AllocationCount: %d\n", MemorySize, AllocationCount));
  90                 UiMessageBoxCritical("Memory allocation failed: out of memory.");
  91                 return NULL;
  92         }
  93
  94         FirstFreePageFromEnd = MmFindAvailablePages(PageLookupTableAddress, TotalPagesInLookupTable, PagesNeeded, AllocateFromEnd);
  95
  96         if (FirstFreePageFromEnd == (ULONG)-1)
  97         {
  98                 DbgPrint((DPRINT_MEMORY, "Memory allocation failed in MmAllocateMemory(). Not enough free memory to allocate %d bytes. AllocationCount: %d\n", MemorySize, AllocationCount));
  99                 UiMessageBoxCritical("Memory allocation failed: out of memory.");
 100                 return NULL;
 101         }
 102
 103         MmAllocatePagesInLookupTable(PageLookupTableAddress, FirstFreePageFromEnd, PagesNeeded, MemoryType);
 104
 105         FreePagesInLookupTable -= PagesNeeded;
 106         MemPointer = (PVOID)(FirstFreePageFromEnd * MM_PAGE_SIZE);
 107
 108         if (MemorySize < MM_PAGE_SIZE)
 109         {
 110                 SubAllocationPage = MemPointer;
 111                 SubAllocationRest = MM_PAGE_SIZE - MemorySize;
 112         }
 113
 114
 115 #ifdef DBG
 116         IncrementAllocationCount();
 117         DbgPrint((DPRINT_MEMORY, "Allocated %d bytes (%d pages) of memory starting at page %d. AllocCount: %d\n", MemorySize, PagesNeeded, FirstFreePageFromEnd, AllocationCount));
 118         DbgPrint((DPRINT_MEMORY, "Memory allocation pointer: 0x%x\n", MemPointer));
 119         //VerifyHeap();
 120 #endif // DBG
 121
 122         // Now return the pointer
 123         return MemPointer;
 124 }
 125
 126 PVOID MmAllocateMemory(ULONG MemorySize)
 127 {
 128         // Temporary forwarder...
 129         return MmAllocateMemoryWithType(MemorySize, LoaderOsloaderHeap);
 130 }
 131
 132 PVOID MmAllocateMemoryAtAddress(ULONG MemorySize, PVOID DesiredAddress, TYPE_OF_MEMORY MemoryType)
 133 {
 134         ULONG           PagesNeeded;
 135         ULONG           StartPageNumber;
 136         PVOID   MemPointer;
 137
 138         if (MemorySize == 0)
 139         {
 140                 DbgPrint((DPRINT_MEMORY, "MmAllocateMemoryAtAddress() called for 0 bytes. Returning NULL.\n"));
 141                 UiMessageBoxCritical("Memory allocation failed: MmAllocateMemoryAtAddress() called for 0 bytes.");
 142                 return NULL;
 143         }
 144
 145         // Find out how many blocks it will take to
 146         // satisfy this allocation
 147         PagesNeeded = ROUND_UP(MemorySize, MM_PAGE_SIZE) / MM_PAGE_SIZE;
 148
 149         // Get the starting page number
 150         StartPageNumber = MmGetPageNumberFromAddress(DesiredAddress);
 151
 152         // If we don't have enough available mem
 153         // then return NULL
 154         if (FreePagesInLookupTable < PagesNeeded)
 155         {
 156                 DbgPrint((DPRINT_MEMORY, "Memory allocation failed in MmAllocateMemoryAtAddress(). "
 157                         "Not enough free memory to allocate %d bytes (requesting %d pages but have only %d). "
 158                         "AllocationCount: %d\n", MemorySize, PagesNeeded, FreePagesInLookupTable, AllocationCount));
 159                 UiMessageBoxCritical("Memory allocation failed: out of memory.");
 160                 return NULL;
 161         }
 162
 163         if (MmAreMemoryPagesAvailable(PageLookupTableAddress, TotalPagesInLookupTable, DesiredAddress, PagesNeeded) == FALSE)
 164         {
 165                 DbgPrint((DPRINT_MEMORY, "Memory allocation failed in MmAllocateMemoryAtAddress(). "
 166                         "Not enough free memory to allocate %d bytes at address %p. AllocationCount: %d\n",
 167                         MemorySize, DesiredAddress, AllocationCount));
 168
 169                 // Don't tell this to user since caller should try to alloc this memory
 170                 // at a different address
 171                 //UiMessageBoxCritical("Memory allocation failed: out of memory.");
 172                 return NULL;
 173         }
 174
 175         MmAllocatePagesInLookupTable(PageLookupTableAddress, StartPageNumber, PagesNeeded, MemoryType);
 176
 177         FreePagesInLookupTable -= PagesNeeded;
 178         MemPointer = (PVOID)(StartPageNumber * MM_PAGE_SIZE);
 179
 180 #ifdef DBG
 181         IncrementAllocationCount();
 182         DbgPrint((DPRINT_MEMORY, "Allocated %d bytes (%d pages) of memory starting at page %d. AllocCount: %d\n", MemorySize, PagesNeeded, StartPageNumber, AllocationCount));
 183         DbgPrint((DPRINT_MEMORY, "Memory allocation pointer: 0x%x\n", MemPointer));
 184         //VerifyHeap();
 185 #endif // DBG
 186
 187         // Now return the pointer
 188         return MemPointer;
 189 }
 190
 191 PVOID MmAllocateHighestMemoryBelowAddress(ULONG MemorySize, PVOID DesiredAddress, TYPE_OF_MEMORY MemoryType)
 192 {
 193         ULONG           PagesNeeded;
 194         ULONG           FirstFreePageFromEnd;
 195         ULONG           DesiredAddressPageNumber;
 196         PVOID   MemPointer;
 197
 198         if (MemorySize == 0)
 199         {
 200                 DbgPrint((DPRINT_MEMORY, "MmAllocateHighestMemoryBelowAddress() called for 0 bytes. Returning NULL.\n"));
 201                 UiMessageBoxCritical("Memory allocation failed: MmAllocateHighestMemoryBelowAddress() called for 0 bytes.");
 202                 return NULL;
 203         }
 204
 205         // Find out how many blocks it will take to
 206         // satisfy this allocation
 207         PagesNeeded = ROUND_UP(MemorySize, MM_PAGE_SIZE) / MM_PAGE_SIZE;
 208
 209         // Get the page number for their desired address
 210         DesiredAddressPageNumber = (ULONG)DesiredAddress / MM_PAGE_SIZE;
 211
 212         // If we don't have enough available mem
 213         // then return NULL
 214         if (FreePagesInLookupTable < PagesNeeded)
 215         {
 216                 DbgPrint((DPRINT_MEMORY, "Memory allocation failed in MmAllocateHighestMemoryBelowAddress(). Not enough free memory to allocate %d bytes. AllocationCount: %d\n", MemorySize, AllocationCount));
 217                 UiMessageBoxCritical("Memory allocation failed: out of memory.");
 218                 return NULL;
 219         }
 220
 221         FirstFreePageFromEnd = MmFindAvailablePagesBeforePage(PageLookupTableAddress, TotalPagesInLookupTable, PagesNeeded, DesiredAddressPageNumber);
 222
 223         if (FirstFreePageFromEnd == 0)
 224         {
 225                 DbgPrint((DPRINT_MEMORY, "Memory allocation failed in MmAllocateHighestMemoryBelowAddress(). Not enough free memory to allocate %d bytes. AllocationCount: %d\n", MemorySize, AllocationCount));
 226                 UiMessageBoxCritical("Memory allocation failed: out of memory.");
 227                 return NULL;
 228         }
 229
 230         MmAllocatePagesInLookupTable(PageLookupTableAddress, FirstFreePageFromEnd, PagesNeeded, MemoryType);
 231
 232         FreePagesInLookupTable -= PagesNeeded;
 233         MemPointer = (PVOID)(FirstFreePageFromEnd * MM_PAGE_SIZE);
 234
 235 #ifdef DBG
 236         IncrementAllocationCount();
 237         DbgPrint((DPRINT_MEMORY, "Allocated %d bytes (%d pages) of memory starting at page %d. AllocCount: %d\n", MemorySize, PagesNeeded, FirstFreePageFromEnd, AllocationCount));
 238         DbgPrint((DPRINT_MEMORY, "Memory allocation pointer: 0x%x\n", MemPointer));
 239         //VerifyHeap();
 240 #endif // DBG
 241
 242         // Now return the pointer
 243         return MemPointer;
 244 }
 245
 246 VOID MmFreeMemory(PVOID MemoryPointer)
 247 {
 248         ULONG                                                   PageNumber;
 249         ULONG                                                   PageCount;
 250         ULONG                                                   Idx;
 251         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTableAddress;
 252
 253 #ifdef DBG
 254
 255         // Make sure we didn't get a bogus pointer
 256         if (MemoryPointer >= (PVOID)(TotalPagesInLookupTable * MM_PAGE_SIZE))
 257         {
 258                 BugCheck((DPRINT_MEMORY, "Bogus memory pointer (0x%x) passed to MmFreeMemory()\n", MemoryPointer));
 259         }
 260 #endif // DBG
 261
 262         // Find out the page number of the first
 263         // page of memory they allocated
 264         PageNumber = MmGetPageNumberFromAddress(MemoryPointer);
 265         PageCount = RealPageLookupTable[PageNumber].PageAllocationLength;
 266
 267 #ifdef DBG
 268         // Make sure we didn't get a bogus pointer
 269         if ((PageCount < 1) || (PageCount > (TotalPagesInLookupTable - PageNumber)))
 270         {
 271                 BugCheck((DPRINT_MEMORY, "Invalid page count in lookup table. PageLookupTable[%d].PageAllocationLength = %d\n", PageNumber, RealPageLookupTable[PageNumber].PageAllocationLength));
 272         }
 273
 274         // Loop through our array check all the pages
 275         // to make sure they are allocated with a length of 0
 276         for (Idx=PageNumber+1; Idx<(PageNumber + PageCount); Idx++)
 277         {
 278                 if ((RealPageLookupTable[Idx].PageAllocated == LoaderFree) ||
 279                         (RealPageLookupTable[Idx].PageAllocationLength != 0))
 280                 {
 281                         BugCheck((DPRINT_MEMORY, "Invalid page entry in lookup table, PageAllocated should = 1 and PageAllocationLength should = 0 because this is not the first block in the run. PageLookupTable[%d].PageAllocated = %d PageLookupTable[%d].PageAllocationLength = %d\n", PageNumber, RealPageLookupTable[PageNumber].PageAllocated, PageNumber, RealPageLookupTable[PageNumber].PageAllocationLength));
 282                 }
 283         }
 284
 285 #endif
 286
 287         /* If this allocation is only a single page, it could be a sub-allocated page.
 288          * Just don't free it */
 289         if (1 == PageCount)
 290         {
 291                 return;
 292         }
 293
 294         // Loop through our array and mark all the
 295         // blocks as free
 296         for (Idx=PageNumber; Idx<(PageNumber + PageCount); Idx++)
 297         {
 298                 RealPageLookupTable[Idx].PageAllocated = LoaderFree;
 299                 RealPageLookupTable[Idx].PageAllocationLength = 0;
 300         }
 301
 302         FreePagesInLookupTable += PageCount;
 303
 304 #ifdef DBG
 305         DecrementAllocationCount();
 306         DbgPrint((DPRINT_MEMORY, "Freed %d pages of memory starting at page %d. AllocationCount: %d\n", PageCount, PageNumber, AllocationCount));
 307         //VerifyHeap();
 308 #endif // DBG
 309 }
 310
 311 PVOID MmHeapAlloc(ULONG MemorySize)
 312 {
 313         // Stub for WinLdr
 314         return NULL;
 315 }
 316
 317 VOID MmHeapFree(PVOID MemoryPointer)
 318 {
 319         // Stub for WinLdr
 320 }
 321
 322
 323 #ifdef DBG
 324 VOID VerifyHeap(VOID)
 325 {
 326         ULONG                                                   Idx;
 327         ULONG                                                   Idx2;
 328         ULONG                                                   Count;
 329         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTableAddress;
 330
 331         if (DUMP_MEM_MAP_ON_VERIFY)
 332         {
 333                 DumpMemoryAllocMap();
 334         }
 335
 336         // Loop through the array and verify that
 337         // everything is kosher
 338         for (Idx=0; Idx<TotalPagesInLookupTable; Idx++)
 339         {
 340                 // Check if this block is allocated
 341                 if (RealPageLookupTable[Idx].PageAllocated != LoaderFree)
 342                 {
 343                         // This is the first block in the run so it
 344                         // had better have a length that is within range
 345                         if ((RealPageLookupTable[Idx].PageAllocationLength < 1) || (RealPageLookupTable[Idx].PageAllocationLength > (TotalPagesInLookupTable - Idx)))
 346                         {
 347                                 BugCheck((DPRINT_MEMORY, "Allocation length out of range in heap table. PageLookupTable[Idx].PageAllocationLength = %d\n", RealPageLookupTable[Idx].PageAllocationLength));
 348                         }
 349
 350                         // Now go through and verify that the rest of
 351                         // this run has the blocks marked allocated
 352                         // with a length of zero but don't check the
 353                         // first one because we already did
 354                         Count = RealPageLookupTable[Idx].PageAllocationLength;
 355                         for (Idx2=1; Idx2<Count; Idx2++)
 356                         {
 357                                 // Make sure it's allocated
 358                                 if (RealPageLookupTable[Idx + Idx2].PageAllocated == LoaderFree)
 359                                 {
 360                                         BugCheck((DPRINT_MEMORY, "Lookup table indicates hole in memory allocation. RealPageLookupTable[Idx + Idx2].PageAllocated == 0\n"));
 361                                 }
 362
 363                                 // Make sure the length is zero
 364                                 if (RealPageLookupTable[Idx + Idx2].PageAllocationLength != 0)
 365                                 {
 366                                         BugCheck((DPRINT_MEMORY, "Allocation chain has non-zero value in non-first block in lookup table. RealPageLookupTable[Idx + Idx2].PageAllocationLength != 0\n"));
 367                                 }
 368                         }
 369
 370                         // Move on to the next run
 371                         Idx += (Count - 1);
 372                 }
 373                 else
 374                 {
 375                         // Nope, not allocated so make sure the length is zero
 376                         if (RealPageLookupTable[Idx].PageAllocationLength != 0)
 377                         {
 378                                 BugCheck((DPRINT_MEMORY, "Free block is start of memory allocation. RealPageLookupTable[Idx].PageAllocationLength != 0\n"));
 379                         }
 380                 }
 381         }
 382 }
 383
 384 VOID DumpMemoryAllocMap(VOID)
 385 {
 386         ULONG                                                   Idx;
 387         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTableAddress;
 388
 389         DbgPrint((DPRINT_MEMORY, "----------- Memory Allocation Bitmap -----------\n"));
 390
 391         for (Idx=0; Idx<TotalPagesInLookupTable; Idx++)
 392         {
 393                 if ((Idx % 32) == 0)
 394                 {
 395                         DbgPrint((DPRINT_MEMORY, "\n"));
 396                         DbgPrint((DPRINT_MEMORY, "%x:\t", (Idx * MM_PAGE_SIZE)));
 397                 }
 398                 else if ((Idx % 4) == 0)
 399                 {
 400                         DbgPrint((DPRINT_MEMORY, " "));
 401                 }
 402
 403                 switch (RealPageLookupTable[Idx].PageAllocated)
 404                 {
 405                 case LoaderFree:
 406                         DbgPrint((DPRINT_MEMORY, "*"));
 407                         break;
 408                 case LoaderBad:
 409                         DbgPrint((DPRINT_MEMORY, "-"));
 410                         break;
 411                 case LoaderLoadedProgram:
 412                         DbgPrint((DPRINT_MEMORY, "O"));
 413                         break;
 414                 case LoaderFirmwareTemporary:
 415                         DbgPrint((DPRINT_MEMORY, "T"));
 416                         break;
 417                 case LoaderFirmwarePermanent:
 418                         DbgPrint((DPRINT_MEMORY, "P"));
 419                         break;
 420                 case LoaderOsloaderHeap:
 421                         DbgPrint((DPRINT_MEMORY, "H"));
 422                         break;
 423                 case LoaderOsloaderStack:
 424                         DbgPrint((DPRINT_MEMORY, "S"));
 425                         break;
 426                 case LoaderSystemCode:
 427                         DbgPrint((DPRINT_MEMORY, "K"));
 428                         break;
 429                 case LoaderHalCode:
 430                         DbgPrint((DPRINT_MEMORY, "L"));
 431                         break;
 432                 case LoaderBootDriver:
 433                         DbgPrint((DPRINT_MEMORY, "B"));
 434                         break;
 435                 case LoaderStartupPcrPage:
 436                         DbgPrint((DPRINT_MEMORY, "G"));
 437                         break;
 438                 case LoaderRegistryData:
 439                         DbgPrint((DPRINT_MEMORY, "R"));
 440                         break;
 441                 case LoaderMemoryData:
 442                         DbgPrint((DPRINT_MEMORY, "M"));
 443                         break;
 444                 case LoaderNlsData:
 445                         DbgPrint((DPRINT_MEMORY, "N"));
 446                         break;
 447                 case LoaderSpecialMemory:
 448                         DbgPrint((DPRINT_MEMORY, "C"));
 449                         break;
 450                 default:
 451                         DbgPrint((DPRINT_MEMORY, "?"));
 452                         break;
 453                 }
 454         }
 455
 456         DbgPrint((DPRINT_MEMORY, "\n"));
 457 }
 458
 459 VOID IncrementAllocationCount(VOID)
 460 {
 461         AllocationCount++;
 462 }
 463
 464 VOID DecrementAllocationCount(VOID)
 465 {
 466         AllocationCount--;
 467 }
 468
 469 VOID MemAllocTest(VOID)
 470 {
 471         PVOID   MemPtr1;
 472         PVOID   MemPtr2;
 473         PVOID   MemPtr3;
 474         PVOID   MemPtr4;
 475         PVOID   MemPtr5;
 476
 477         MemPtr1 = MmAllocateMemory(4096);
 478         printf("MemPtr1: 0x%x\n", (int)MemPtr1);
 479         MachConsGetCh();
 480         MemPtr2 = MmAllocateMemory(4096);
 481         printf("MemPtr2: 0x%x\n", (int)MemPtr2);
 482         MachConsGetCh();
 483         MemPtr3 = MmAllocateMemory(4096);
 484         printf("MemPtr3: 0x%x\n", (int)MemPtr3);
 485         DumpMemoryAllocMap();
 486         VerifyHeap();
 487         MachConsGetCh();
 488
 489         MmFreeMemory(MemPtr2);
 490         MachConsGetCh();
 491
 492         MemPtr4 = MmAllocateMemory(2048);
 493         printf("MemPtr4: 0x%x\n", (int)MemPtr4);
 494         MachConsGetCh();
 495         MemPtr5 = MmAllocateMemory(4096);
 496         printf("MemPtr5: 0x%x\n", (int)MemPtr5);
 497         MachConsGetCh();
 498 }
 499 #endif // DBG
 500
 501 ULONG GetSystemMemorySize(VOID)
 502 {
 503         return (TotalPagesInLookupTable * MM_PAGE_SIZE);
 504 }
 505
 506 PPAGE_LOOKUP_TABLE_ITEM MmGetMemoryMap(ULONG *NoEntries)
 507 {
 508         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTableAddress;
 509
 510         *NoEntries = TotalPagesInLookupTable;
 511
 512         return RealPageLookupTable;
 513 }