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 PVOID MmAllocateMemory(ULONG MemorySize)
  56 {
  57         ULONG   PagesNeeded;
  58         ULONG   FirstFreePageFromEnd;
  59         PVOID   MemPointer;
  60
  61         if (MemorySize == 0)
  62         {
  63                 DbgPrint((DPRINT_MEMORY, "MmAllocateMemory() called for 0 bytes. Returning NULL.\n"));
  64                 UiMessageBoxCritical("Memory allocation failed: MmAllocateMemory() called for 0 bytes.");
  65                 return NULL;
  66         }
  67
  68         MemorySize = ROUND_UP(MemorySize, 4);
  69         if (MemorySize <= SubAllocationRest)
  70         {
  71                 MemPointer = (PVOID)((ULONG_PTR)SubAllocationPage + MM_PAGE_SIZE - SubAllocationRest);
  72                 SubAllocationRest -= MemorySize;
  73                 return MemPointer;
  74         }
  75
  76         // Find out how many blocks it will take to
  77         // satisfy this allocation
  78         PagesNeeded = ROUND_UP(MemorySize, MM_PAGE_SIZE) / MM_PAGE_SIZE;
  79
  80         // If we don't have enough available mem
  81         // then return NULL
  82         if (FreePagesInLookupTable < PagesNeeded)
  83         {
  84                 DbgPrint((DPRINT_MEMORY, "Memory allocation failed. Not enough free memory to allocate %d bytes. AllocationCount: %d\n", MemorySize, AllocationCount));
  85                 UiMessageBoxCritical("Memory allocation failed: out of memory.");
  86                 return NULL;
  87         }
  88
  89         FirstFreePageFromEnd = MmFindAvailablePagesFromEnd(PageLookupTableAddress, TotalPagesInLookupTable, PagesNeeded);
  90
  91         if (FirstFreePageFromEnd == 0)
  92         {
  93                 DbgPrint((DPRINT_MEMORY, "Memory allocation failed. Not enough free memory to allocate %d bytes. AllocationCount: %d\n", MemorySize, AllocationCount));
  94                 UiMessageBoxCritical("Memory allocation failed: out of memory.");
  95                 return NULL;
  96         }
  97
  98         MmAllocatePagesInLookupTable(PageLookupTableAddress, FirstFreePageFromEnd, PagesNeeded);
  99
 100         FreePagesInLookupTable -= PagesNeeded;
 101         MemPointer = (PVOID)(FirstFreePageFromEnd * MM_PAGE_SIZE);
 102
 103         if (MemorySize < MM_PAGE_SIZE)
 104         {
 105                 SubAllocationPage = MemPointer;
 106                 SubAllocationRest = MM_PAGE_SIZE - MemorySize;
 107         }
 108
 109
 110 #ifdef DEBUG
 111         IncrementAllocationCount();
 112         DbgPrint((DPRINT_MEMORY, "Allocated %d bytes (%d pages) of memory starting at page %d. AllocCount: %d\n", MemorySize, PagesNeeded, FirstFreePageFromEnd, AllocationCount));
 113         DbgPrint((DPRINT_MEMORY, "Memory allocation pointer: 0x%x\n", MemPointer));
 114         //VerifyHeap();
 115 #endif // DEBUG
 116
 117         // Now return the pointer
 118         return MemPointer;
 119 }
 120
 121 PVOID MmAllocateMemoryAtAddress(ULONG MemorySize, PVOID DesiredAddress)
 122 {
 123         ULONG           PagesNeeded;
 124         ULONG           StartPageNumber;
 125         PVOID   MemPointer;
 126
 127         if (MemorySize == 0)
 128         {
 129                 DbgPrint((DPRINT_MEMORY, "MmAllocateMemoryAtAddress() called for 0 bytes. Returning NULL.\n"));
 130                 UiMessageBoxCritical("Memory allocation failed: MmAllocateMemoryAtAddress() called for 0 bytes.");
 131                 return NULL;
 132         }
 133
 134         // Find out how many blocks it will take to
 135         // satisfy this allocation
 136         PagesNeeded = ROUND_UP(MemorySize, MM_PAGE_SIZE) / MM_PAGE_SIZE;
 137
 138         // Get the starting page number
 139         StartPageNumber = MmGetPageNumberFromAddress(DesiredAddress);
 140
 141         // If we don't have enough available mem
 142         // then return NULL
 143         if (FreePagesInLookupTable < PagesNeeded)
 144         {
 145                 DbgPrint((DPRINT_MEMORY, "Memory allocation failed. Not enough free memory to allocate %d bytes. AllocationCount: %d\n", MemorySize, AllocationCount));
 146                 UiMessageBoxCritical("Memory allocation failed: out of memory.");
 147                 return NULL;
 148         }
 149
 150         if (MmAreMemoryPagesAvailable(PageLookupTableAddress, TotalPagesInLookupTable, DesiredAddress, PagesNeeded) == FALSE)
 151         {
 152                 DbgPrint((DPRINT_MEMORY, "Memory allocation failed. Not enough free memory to allocate %d bytes. AllocationCount: %d\n", MemorySize, AllocationCount));
 153                 UiMessageBoxCritical("Memory allocation failed: out of memory.");
 154                 return NULL;
 155         }
 156
 157         MmAllocatePagesInLookupTable(PageLookupTableAddress, StartPageNumber, PagesNeeded);
 158
 159         FreePagesInLookupTable -= PagesNeeded;
 160         MemPointer = (PVOID)(StartPageNumber * MM_PAGE_SIZE);
 161
 162 #ifdef DEBUG
 163         IncrementAllocationCount();
 164         DbgPrint((DPRINT_MEMORY, "Allocated %d bytes (%d pages) of memory starting at page %d. AllocCount: %d\n", MemorySize, PagesNeeded, StartPageNumber, AllocationCount));
 165         DbgPrint((DPRINT_MEMORY, "Memory allocation pointer: 0x%x\n", MemPointer));
 166         //VerifyHeap();
 167 #endif // DEBUG
 168
 169         // Now return the pointer
 170         return MemPointer;
 171 }
 172
 173 PVOID MmAllocateHighestMemoryBelowAddress(ULONG MemorySize, PVOID DesiredAddress)
 174 {
 175         ULONG           PagesNeeded;
 176         ULONG           FirstFreePageFromEnd;
 177         ULONG           DesiredAddressPageNumber;
 178         PVOID   MemPointer;
 179
 180         if (MemorySize == 0)
 181         {
 182                 DbgPrint((DPRINT_MEMORY, "MmAllocateHighestMemoryBelowAddress() called for 0 bytes. Returning NULL.\n"));
 183                 UiMessageBoxCritical("Memory allocation failed: MmAllocateHighestMemoryBelowAddress() called for 0 bytes.");
 184                 return NULL;
 185         }
 186
 187         // Find out how many blocks it will take to
 188         // satisfy this allocation
 189         PagesNeeded = ROUND_UP(MemorySize, MM_PAGE_SIZE) / MM_PAGE_SIZE;
 190
 191         // Get the page number for their desired address
 192         DesiredAddressPageNumber = (ULONG)DesiredAddress / MM_PAGE_SIZE;
 193
 194         // If we don't have enough available mem
 195         // then return NULL
 196         if (FreePagesInLookupTable < PagesNeeded)
 197         {
 198                 DbgPrint((DPRINT_MEMORY, "Memory allocation failed. Not enough free memory to allocate %d bytes. AllocationCount: %d\n", MemorySize, AllocationCount));
 199                 UiMessageBoxCritical("Memory allocation failed: out of memory.");
 200                 return NULL;
 201         }
 202
 203         FirstFreePageFromEnd = MmFindAvailablePagesBeforePage(PageLookupTableAddress, TotalPagesInLookupTable, PagesNeeded, DesiredAddressPageNumber);
 204
 205         if (FirstFreePageFromEnd == 0)
 206         {
 207                 DbgPrint((DPRINT_MEMORY, "Memory allocation failed. Not enough free memory to allocate %d bytes. AllocationCount: %d\n", MemorySize, AllocationCount));
 208                 UiMessageBoxCritical("Memory allocation failed: out of memory.");
 209                 return NULL;
 210         }
 211
 212         MmAllocatePagesInLookupTable(PageLookupTableAddress, FirstFreePageFromEnd, PagesNeeded);
 213
 214         FreePagesInLookupTable -= PagesNeeded;
 215         MemPointer = (PVOID)(FirstFreePageFromEnd * MM_PAGE_SIZE);
 216
 217 #ifdef DEBUG
 218         IncrementAllocationCount();
 219         DbgPrint((DPRINT_MEMORY, "Allocated %d bytes (%d pages) of memory starting at page %d. AllocCount: %d\n", MemorySize, PagesNeeded, FirstFreePageFromEnd, AllocationCount));
 220         DbgPrint((DPRINT_MEMORY, "Memory allocation pointer: 0x%x\n", MemPointer));
 221         //VerifyHeap();
 222 #endif // DEBUG
 223
 224         // Now return the pointer
 225         return MemPointer;
 226 }
 227
 228 VOID MmFreeMemory(PVOID MemoryPointer)
 229 {
 230         ULONG                                                   PageNumber;
 231         ULONG                                                   PageCount;
 232         ULONG                                                   Idx;
 233         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTableAddress;
 234
 235 #ifdef DEBUG
 236
 237         // Make sure we didn't get a bogus pointer
 238         if (MemoryPointer >= (PVOID)(TotalPagesInLookupTable * MM_PAGE_SIZE))
 239         {
 240                 BugCheck((DPRINT_MEMORY, "Bogus memory pointer (0x%x) passed to MmFreeMemory()\n", MemoryPointer));
 241         }
 242 #endif // DEBUG
 243
 244         // Find out the page number of the first
 245         // page of memory they allocated
 246         PageNumber = MmGetPageNumberFromAddress(MemoryPointer);
 247         PageCount = RealPageLookupTable[PageNumber].PageAllocationLength;
 248
 249 #ifdef DEBUG
 250         // Make sure we didn't get a bogus pointer
 251         if ((PageCount < 1) || (PageCount > (TotalPagesInLookupTable - PageNumber)))
 252         {
 253                 BugCheck((DPRINT_MEMORY, "Invalid page count in lookup table. PageLookupTable[%d].PageAllocationLength = %d\n", PageNumber, RealPageLookupTable[PageNumber].PageAllocationLength));
 254         }
 255
 256         // Loop through our array check all the pages
 257         // to make sure they are allocated with a length of 0
 258         for (Idx=PageNumber+1; Idx<(PageNumber + PageCount); Idx++)
 259         {
 260                 if ((RealPageLookupTable[Idx].PageAllocated != 1) ||
 261                         (RealPageLookupTable[Idx].PageAllocationLength != 0))
 262                 {
 263                         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));
 264                 }
 265         }
 266
 267 #endif
 268
 269         /* If this allocation is only a single page, it could be a sub-allocated page.
 270          * Just don't free it */
 271         if (1 == PageCount)
 272         {
 273                 return;
 274         }
 275
 276         // Loop through our array and mark all the
 277         // blocks as free
 278         for (Idx=PageNumber; Idx<(PageNumber + PageCount); Idx++)
 279         {
 280                 RealPageLookupTable[Idx].PageAllocated = 0;
 281                 RealPageLookupTable[Idx].PageAllocationLength = 0;
 282         }
 283
 284         FreePagesInLookupTable += PageCount;
 285
 286 #ifdef DEBUG
 287         DecrementAllocationCount();
 288         DbgPrint((DPRINT_MEMORY, "Freed %d pages of memory starting at page %d. AllocationCount: %d\n", PageCount, PageNumber, AllocationCount));
 289         //VerifyHeap();
 290 #endif // DEBUG
 291 }
 292
 293 #ifdef DEBUG
 294 VOID VerifyHeap(VOID)
 295 {
 296         ULONG                                                   Idx;
 297         ULONG                                                   Idx2;
 298         ULONG                                                   Count;
 299         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTableAddress;
 300
 301         if (DUMP_MEM_MAP_ON_VERIFY)
 302         {
 303                 DumpMemoryAllocMap();
 304         }
 305
 306         // Loop through the array and verify that
 307         // everything is kosher
 308         for (Idx=0; Idx<TotalPagesInLookupTable; Idx++)
 309         {
 310                 // Check if this block is allocated
 311                 if (RealPageLookupTable[Idx].PageAllocated != 0)
 312                 {
 313                         // This is the first block in the run so it
 314                         // had better have a length that is within range
 315                         if ((RealPageLookupTable[Idx].PageAllocationLength < 1) || (RealPageLookupTable[Idx].PageAllocationLength > (TotalPagesInLookupTable - Idx)))
 316                         {
 317                                 BugCheck((DPRINT_MEMORY, "Allocation length out of range in heap table. PageLookupTable[Idx].PageAllocationLength = %d\n", RealPageLookupTable[Idx].PageAllocationLength));
 318                         }
 319
 320                         // Now go through and verify that the rest of
 321                         // this run has the blocks marked allocated
 322                         // with a length of zero but don't check the
 323                         // first one because we already did
 324                         Count = RealPageLookupTable[Idx].PageAllocationLength;
 325                         for (Idx2=1; Idx2<Count; Idx2++)
 326                         {
 327                                 // Make sure it's allocated
 328                                 if (RealPageLookupTable[Idx + Idx2].PageAllocated == 0)
 329                                 {
 330                                         BugCheck((DPRINT_MEMORY, "Lookup table indicates hole in memory allocation. RealPageLookupTable[Idx + Idx2].PageAllocated == 0\n"));
 331                                 }
 332
 333                                 // Make sure the length is zero
 334                                 if (RealPageLookupTable[Idx + Idx2].PageAllocationLength != 0)
 335                                 {
 336                                         BugCheck((DPRINT_MEMORY, "Allocation chain has non-zero value in non-first block in lookup table. RealPageLookupTable[Idx + Idx2].PageAllocationLength != 0\n"));
 337                                 }
 338                         }
 339
 340                         // Move on to the next run
 341                         Idx += (Count - 1);
 342                 }
 343                 else
 344                 {
 345                         // Nope, not allocated so make sure the length is zero
 346                         if (RealPageLookupTable[Idx].PageAllocationLength != 0)
 347                         {
 348                                 BugCheck((DPRINT_MEMORY, "Free block is start of memory allocation. RealPageLookupTable[Idx].PageAllocationLength != 0\n"));
 349                         }
 350                 }
 351         }
 352 }
 353
 354 VOID DumpMemoryAllocMap(VOID)
 355 {
 356         ULONG                                                   Idx;
 357         PPAGE_LOOKUP_TABLE_ITEM         RealPageLookupTable = (PPAGE_LOOKUP_TABLE_ITEM)PageLookupTableAddress;
 358
 359         DbgPrint((DPRINT_MEMORY, "----------- Memory Allocation Bitmap -----------\n"));
 360
 361         for (Idx=0; Idx<TotalPagesInLookupTable; Idx++)
 362         {
 363                 if ((Idx % 32) == 0)
 364                 {
 365                         DbgPrint((DPRINT_MEMORY, "\n"));
 366                         DbgPrint((DPRINT_MEMORY, "%x:\t", (Idx * MM_PAGE_SIZE)));
 367                 }
 368                 else if ((Idx % 4) == 0)
 369                 {
 370                         DbgPrint((DPRINT_MEMORY, " "));
 371                 }
 372
 373                 switch (RealPageLookupTable[Idx].PageAllocated)
 374                 {
 375                 case 0:
 376                         DbgPrint((DPRINT_MEMORY, "*"));
 377                         break;
 378                 case 1:
 379                         DbgPrint((DPRINT_MEMORY, "A"));
 380                         break;
 381                 case MEMTYPE_RESERVED:
 382                         DbgPrint((DPRINT_MEMORY, "R"));
 383                         break;
 384                 case MEMTYPE_ACPI_RECLAIM:
 385                         DbgPrint((DPRINT_MEMORY, "M"));
 386                         break;
 387                 case MEMTYPE_ACPI_NVS:
 388                         DbgPrint((DPRINT_MEMORY, "N"));
 389                         break;
 390                 default:
 391                         DbgPrint((DPRINT_MEMORY, "X"));
 392                         break;
 393                 }
 394         }
 395
 396         DbgPrint((DPRINT_MEMORY, "\n"));
 397 }
 398
 399 VOID IncrementAllocationCount(VOID)
 400 {
 401         AllocationCount++;
 402 }
 403
 404 VOID DecrementAllocationCount(VOID)
 405 {
 406         AllocationCount--;
 407 }
 408
 409 VOID MemAllocTest(VOID)
 410 {
 411         PVOID   MemPtr1;
 412         PVOID   MemPtr2;
 413         PVOID   MemPtr3;
 414         PVOID   MemPtr4;
 415         PVOID   MemPtr5;
 416
 417         MemPtr1 = MmAllocateMemory(4096);
 418         printf("MemPtr1: 0x%x\n", (int)MemPtr1);
 419         MachConsGetCh();
 420         MemPtr2 = MmAllocateMemory(4096);
 421         printf("MemPtr2: 0x%x\n", (int)MemPtr2);
 422         MachConsGetCh();
 423         MemPtr3 = MmAllocateMemory(4096);
 424         printf("MemPtr3: 0x%x\n", (int)MemPtr3);
 425         DumpMemoryAllocMap();
 426         VerifyHeap();
 427         MachConsGetCh();
 428
 429         MmFreeMemory(MemPtr2);
 430         MachConsGetCh();
 431
 432         MemPtr4 = MmAllocateMemory(2048);
 433         printf("MemPtr4: 0x%x\n", (int)MemPtr4);
 434         MachConsGetCh();
 435         MemPtr5 = MmAllocateMemory(4096);
 436         printf("MemPtr5: 0x%x\n", (int)MemPtr5);
 437         MachConsGetCh();
 438 }
 439 #endif // DEBUG
 440
 441 ULONG GetSystemMemorySize(VOID)
 442 {
 443         return (TotalPagesInLookupTable * MM_PAGE_SIZE);
 444 }