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