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