freeldr/freeldr/memory.c

   1 /*
   2  *  FreeLoader
   3  *  Copyright (C) 2001  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 "memory.h"
  22 #include "stdlib.h"
  23 #include "debug.h"
  24 #include "tui.h"
  25
  26
  27 //
  28 // Define this to 1 if you want the entire contents
  29 // of the memory allocation bitmap displayed
  30 // when a chunk is allocated or freed
  31 //
  32 #define DUMP_MEM_MAP_ON_VERIFY  0
  33
  34 #define MEM_BLOCK_SIZE  256
  35
  36 typedef struct
  37 {
  38         BOOL    MemBlockAllocated;              // Is this block allocated or free
  39         ULONG   BlocksAllocated;                // Block length, in multiples of 256 bytes
  40 } MEMBLOCK, *PMEMBLOCK;
  41
  42 PVOID           HeapBaseAddress = NULL;
  43 ULONG           HeapLengthInBytes = 0;
  44 ULONG           HeapMemBlockCount = 0;
  45 PMEMBLOCK       HeapMemBlockArray = NULL;
  46
  47 #ifdef DEBUG
  48 ULONG           AllocationCount = 0;
  49
  50 VOID            VerifyHeap(VOID);
  51 VOID            DumpMemoryAllocMap(VOID);
  52 VOID            IncrementAllocationCount(VOID);
  53 VOID            DecrementAllocationCount(VOID);
  54 VOID            MemAllocTest(VOID);
  55 #endif DEBUG
  56
  57 VOID InitMemoryManager(PVOID BaseAddress, ULONG Length)
  58 {
  59         ULONG   MemBlocks;
  60
  61         // Calculate how many memory blocks we have
  62         MemBlocks = (Length / MEM_BLOCK_SIZE);
  63
  64         // Adjust the heap length so we can reserve
  65         // enough storage space for the MEMBLOCK array
  66         Length -= (MemBlocks * sizeof(MEMBLOCK));
  67
  68         // Initialize our tracking variables
  69         HeapBaseAddress = BaseAddress;
  70         HeapLengthInBytes = Length;
  71         HeapMemBlockCount = (HeapLengthInBytes / MEM_BLOCK_SIZE);
  72         HeapMemBlockArray = (PMEMBLOCK)(HeapBaseAddress + HeapLengthInBytes);
  73
  74         // Clear the memory
  75         ZeroMemory(HeapBaseAddress, HeapLengthInBytes);
  76         ZeroMemory(HeapMemBlockArray, (HeapMemBlockCount * sizeof(MEMBLOCK)));
  77
  78 #ifdef DEBUG
  79         DbgPrint((DPRINT_MEMORY, "Memory Manager initialized. BaseAddress = 0x%x Length = 0x%x. %d blocks in heap.\n", BaseAddress, Length, HeapMemBlockCount));
  80         //MemAllocTest();
  81 #endif
  82 }
  83
  84 PVOID AllocateMemory(ULONG NumberOfBytes)
  85 {
  86         ULONG   BlocksNeeded;
  87         ULONG   Idx;
  88         ULONG   NumFree;
  89         PVOID   MemPointer;
  90
  91         if (NumberOfBytes == 0)
  92         {
  93                 DbgPrint((DPRINT_MEMORY, "AllocateMemory() called for 0 bytes. Returning NULL.\n"));
  94                 return NULL;
  95         }
  96
  97         // Find out how many blocks it will take to
  98         // satisfy this allocation
  99         BlocksNeeded = ROUND_UP(NumberOfBytes, MEM_BLOCK_SIZE) / MEM_BLOCK_SIZE;
 100
 101         // Now loop through our array of blocks and
 102         // see if we have enough space
 103         for (Idx=0,NumFree=0; Idx<HeapMemBlockCount; Idx++)
 104         {
 105                 // Check this block and see if it is already allocated
 106                 // If so reset our counter and continue the loop
 107                 if (HeapMemBlockArray[Idx].MemBlockAllocated)
 108                 {
 109                         NumFree = 0;
 110                         continue;
 111                 }
 112                 else
 113                 {
 114                         // It is free memory so lets increment our count
 115                         NumFree++;
 116                 }
 117
 118                 // If we have found enough blocks to satisfy the request
 119                 // then we're done searching
 120                 if (NumFree >= BlocksNeeded)
 121                 {
 122                         break;
 123                 }
 124         }
 125         Idx++;
 126
 127         // If we don't have enough available mem
 128         // then return NULL
 129         if (NumFree < BlocksNeeded)
 130         {
 131                 DbgPrint((DPRINT_MEMORY, "Memory allocation failed. Not enough free memory to allocate %d bytes. AllocationCount: %d\n", NumberOfBytes, AllocationCount));
 132                 MessageBox("Memory allocation failed: out of memory.");
 133                 return NULL;
 134         }
 135
 136         // Subtract the block count from Idx and we have
 137         // the start block of the memory
 138         Idx -= NumFree;
 139
 140         // Now we know which block to give them
 141         MemPointer = HeapBaseAddress + (Idx * MEM_BLOCK_SIZE);
 142
 143         // Now loop through and mark all the blocks as allocated
 144         for (NumFree=0; NumFree<BlocksNeeded; NumFree++)
 145         {
 146                 HeapMemBlockArray[Idx + NumFree].MemBlockAllocated = TRUE;
 147                 HeapMemBlockArray[Idx + NumFree].BlocksAllocated = NumFree ? 0 : BlocksNeeded; // Mark only the first block with the count
 148         }
 149
 150 #ifdef DEBUG
 151         IncrementAllocationCount();
 152         DbgPrint((DPRINT_MEMORY, "Allocated %d bytes (%d blocks) of memory starting at block %d. AllocCount: %d\n", NumberOfBytes, BlocksNeeded, Idx, AllocationCount));
 153         VerifyHeap();
 154 #endif DEBUG
 155
 156         // Now return the pointer
 157         return MemPointer;
 158 }
 159
 160 VOID FreeMemory(PVOID MemBlock)
 161 {
 162         ULONG   BlockNumber;
 163         ULONG   BlockCount;
 164         ULONG   Idx;
 165
 166 #ifdef DEBUG
 167
 168         // Make sure we didn't get a bogus pointer
 169         if ((MemBlock < HeapBaseAddress) || (MemBlock > (HeapBaseAddress + HeapLengthInBytes)))
 170         {
 171                 BugCheck((DPRINT_MEMORY, "Bogus memory pointer (0x%x) passed to FreeMemory()\n", MemBlock));
 172         }
 173 #endif DEBUG
 174
 175         // Find out the block number if the first
 176         // block of memory they allocated
 177         BlockNumber = (MemBlock - HeapBaseAddress) / MEM_BLOCK_SIZE;
 178         BlockCount = HeapMemBlockArray[BlockNumber].BlocksAllocated;
 179
 180 #ifdef DEBUG
 181         // Make sure we didn't get a bogus pointer
 182         if ((BlockCount < 1) || (BlockCount > HeapMemBlockCount))
 183         {
 184                 BugCheck((DPRINT_MEMORY, "Invalid block count in heap page header. HeapMemBlockArray[BlockNumber].BlocksAllocated = %d\n", HeapMemBlockArray[BlockNumber].BlocksAllocated));
 185         }
 186 #endif
 187
 188         // Loop through our array and mark all the
 189         // blocks as free
 190         for (Idx=BlockNumber; Idx<(BlockNumber + BlockCount); Idx++)
 191         {
 192                 HeapMemBlockArray[Idx].MemBlockAllocated = FALSE;
 193                 HeapMemBlockArray[Idx].BlocksAllocated = 0;
 194         }
 195
 196 #ifdef DEBUG
 197         DecrementAllocationCount();
 198         DbgPrint((DPRINT_MEMORY, "Freed %d blocks of memory starting at block %d. AllocationCount: %d\n", BlockCount, BlockNumber, AllocationCount));
 199         VerifyHeap();
 200 #endif DEBUG
 201 }
 202
 203 #ifdef DEBUG
 204 VOID VerifyHeap(VOID)
 205 {
 206         ULONG   Idx;
 207         ULONG   Idx2;
 208         ULONG   Count;
 209
 210         if (DUMP_MEM_MAP_ON_VERIFY)
 211         {
 212                 DumpMemoryAllocMap();
 213         }
 214
 215         // Loop through the array and verify that
 216         // everything is kosher
 217         for (Idx=0; Idx<HeapMemBlockCount; Idx++)
 218         {
 219                 // Check if this block is allocation
 220                 if (HeapMemBlockArray[Idx].MemBlockAllocated)
 221                 {
 222                         // This is the first block in the run so it
 223                         // had better have a length that is within range
 224                         if ((HeapMemBlockArray[Idx].BlocksAllocated < 1) || (HeapMemBlockArray[Idx].BlocksAllocated > (HeapMemBlockCount - Idx)))
 225                         {
 226                                 BugCheck((DPRINT_MEMORY, "Allocation length out of range in heap table. HeapMemBlockArray[Idx].BlocksAllocated = %d\n", HeapMemBlockArray[Idx].BlocksAllocated));
 227                         }
 228
 229                         // Now go through and verify that the rest of
 230                         // this run has the blocks marked allocated
 231                         // with a length of zero but don't check the
 232                         // first one because we already did
 233                         Count = HeapMemBlockArray[Idx].BlocksAllocated;
 234                         for (Idx2=1; Idx2<Count; Idx2++)
 235                         {
 236                                 // Make sure it's allocated
 237                                 if (HeapMemBlockArray[Idx + Idx2].MemBlockAllocated != TRUE)
 238                                 {
 239                                         BugCheck((DPRINT_MEMORY, "Heap table indicates hole in memory allocation. HeapMemBlockArray[Idx + Idx2].MemBlockAllocated != TRUE\n"));
 240                                 }
 241
 242                                 // Make sure the length is zero
 243                                 if (HeapMemBlockArray[Idx + Idx2].BlocksAllocated != 0)
 244                                 {
 245                                         BugCheck((DPRINT_MEMORY, "Allocation chain has non-zero value in non-first block in heap table. HeapMemBlockArray[Idx + Idx2].BlocksAllocated != 0\n"));
 246                                 }
 247                         }
 248
 249                         // Move on to the next run
 250                         Idx += (Count - 1);
 251                 }
 252                 else
 253                 {
 254                         // Nope, not allocated so make sure the length is zero
 255                         if (HeapMemBlockArray[Idx].BlocksAllocated != 0)
 256                         {
 257                                 BugCheck((DPRINT_MEMORY, "Free block is start of memory allocation. HeapMemBlockArray[Idx].BlocksAllocated != 0\n"));
 258                         }
 259                 }
 260         }
 261 }
 262
 263 VOID DumpMemoryAllocMap(VOID)
 264 {
 265         ULONG   Idx;
 266
 267         DbgPrint((DPRINT_MEMORY, "----------- Memory Allocation Bitmap -----------\n"));
 268
 269         for (Idx=0; Idx<HeapMemBlockCount; Idx++)
 270         {
 271                 if ((Idx % 32) == 0)
 272                 {
 273                         DbgPrint((DPRINT_MEMORY, "\n%x:\t", (Idx * 256)));
 274                 }
 275                 else if ((Idx % 4) == 0)
 276                 {
 277                         DbgPrint((DPRINT_MEMORY, " "));
 278                 }
 279
 280                 if (HeapMemBlockArray[Idx].MemBlockAllocated)
 281                 {
 282                         DbgPrint((DPRINT_MEMORY, "X"));
 283                 }
 284                 else
 285                 {
 286                         DbgPrint((DPRINT_MEMORY, "*"));
 287                 }
 288         }
 289
 290         DbgPrint((DPRINT_MEMORY, "\n"));
 291 }
 292
 293 VOID IncrementAllocationCount(VOID)
 294 {
 295         AllocationCount++;
 296 }
 297
 298 VOID DecrementAllocationCount(VOID)
 299 {
 300         AllocationCount--;
 301 }
 302
 303 VOID MemAllocTest(VOID)
 304 {
 305         PVOID   MemPtr1;
 306         PVOID   MemPtr2;
 307         PVOID   MemPtr3;
 308         PVOID   MemPtr4;
 309         PVOID   MemPtr5;
 310
 311         MemPtr1 = AllocateMemory(4096);
 312         printf("MemPtr1: 0x%x\n", (int)MemPtr1);
 313         getch();
 314         MemPtr2 = AllocateMemory(4096);
 315         printf("MemPtr2: 0x%x\n", (int)MemPtr2);
 316         getch();
 317         MemPtr3 = AllocateMemory(4096);
 318         printf("MemPtr3: 0x%x\n", (int)MemPtr3);
 319         DumpMemoryAllocMap();
 320         VerifyHeap();
 321         getch();
 322
 323         FreeMemory(MemPtr2);
 324         getch();
 325
 326         MemPtr4 = AllocateMemory(2048);
 327         printf("MemPtr4: 0x%x\n", (int)MemPtr4);
 328         getch();
 329         MemPtr5 = AllocateMemory(4096);
 330         printf("MemPtr5: 0x%x\n", (int)MemPtr5);
 331         getch();
 332 }
 333 #endif DEBUG