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