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