]> git.proxmox.com Git - mirror_edk2.git/blob - MdeModulePkg/Core/Dxe/Mem/Pool.c
ebb2fceedd8050c7202a20791b8ee278ece4ab91
[mirror_edk2.git] / MdeModulePkg / Core / Dxe / Mem / Pool.c
1 /** @file
2 UEFI Memory pool management functions.
3
4 Copyright (c) 2006 - 2016, Intel Corporation. All rights reserved.<BR>
5 This program and the accompanying materials
6 are licensed and made available under the terms and conditions of the BSD License
7 which accompanies this distribution. The full text of the license may be found at
8 http://opensource.org/licenses/bsd-license.php
9
10 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
11 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
12
13 **/
14
15 #include "DxeMain.h"
16 #include "Imem.h"
17
18 STATIC EFI_LOCK mPoolMemoryLock = EFI_INITIALIZE_LOCK_VARIABLE (TPL_NOTIFY);
19
20 #define POOL_FREE_SIGNATURE SIGNATURE_32('p','f','r','0')
21 typedef struct {
22 UINT32 Signature;
23 UINT32 Index;
24 LIST_ENTRY Link;
25 } POOL_FREE;
26
27
28 #define POOL_HEAD_SIGNATURE SIGNATURE_32('p','h','d','0')
29 typedef struct {
30 UINT32 Signature;
31 UINT32 Reserved;
32 EFI_MEMORY_TYPE Type;
33 UINTN Size;
34 CHAR8 Data[1];
35 } POOL_HEAD;
36
37 #define SIZE_OF_POOL_HEAD OFFSET_OF(POOL_HEAD,Data)
38
39 #define POOL_TAIL_SIGNATURE SIGNATURE_32('p','t','a','l')
40 typedef struct {
41 UINT32 Signature;
42 UINT32 Reserved;
43 UINTN Size;
44 } POOL_TAIL;
45
46 #define POOL_OVERHEAD (SIZE_OF_POOL_HEAD + sizeof(POOL_TAIL))
47
48 #define HEAD_TO_TAIL(a) \
49 ((POOL_TAIL *) (((CHAR8 *) (a)) + (a)->Size - sizeof(POOL_TAIL)));
50
51 //
52 // Each element is the sum of the 2 previous ones: this allows us to migrate
53 // blocks between bins by splitting them up, while not wasting too much memory
54 // as we would in a strict power-of-2 sequence
55 //
56 STATIC CONST UINT16 mPoolSizeTable[] = {
57 128, 256, 384, 640, 1024, 1664, 2688, 4352, 7040, 11392, 18432, 29824
58 };
59
60 #define SIZE_TO_LIST(a) (GetPoolIndexFromSize (a))
61 #define LIST_TO_SIZE(a) (mPoolSizeTable [a])
62
63 #define MAX_POOL_LIST (ARRAY_SIZE (mPoolSizeTable))
64
65 #define MAX_POOL_SIZE (MAX_ADDRESS - POOL_OVERHEAD)
66
67 //
68 // Globals
69 //
70
71 #define POOL_SIGNATURE SIGNATURE_32('p','l','s','t')
72 typedef struct {
73 INTN Signature;
74 UINTN Used;
75 EFI_MEMORY_TYPE MemoryType;
76 LIST_ENTRY FreeList[MAX_POOL_LIST];
77 LIST_ENTRY Link;
78 } POOL;
79
80 //
81 // Pool header for each memory type.
82 //
83 POOL mPoolHead[EfiMaxMemoryType];
84
85 //
86 // List of pool header to search for the appropriate memory type.
87 //
88 LIST_ENTRY mPoolHeadList = INITIALIZE_LIST_HEAD_VARIABLE (mPoolHeadList);
89
90 /**
91 Get pool size table index from the specified size.
92
93 @param Size The specified size to get index from pool table.
94
95 @return The index of pool size table.
96
97 **/
98 STATIC
99 UINTN
100 GetPoolIndexFromSize (
101 UINTN Size
102 )
103 {
104 UINTN Index;
105
106 for (Index = 0; Index < MAX_POOL_LIST; Index++) {
107 if (mPoolSizeTable [Index] >= Size) {
108 return Index;
109 }
110 }
111 return MAX_POOL_LIST;
112 }
113
114 /**
115 Called to initialize the pool.
116
117 **/
118 VOID
119 CoreInitializePool (
120 VOID
121 )
122 {
123 UINTN Type;
124 UINTN Index;
125
126 for (Type=0; Type < EfiMaxMemoryType; Type++) {
127 mPoolHead[Type].Signature = 0;
128 mPoolHead[Type].Used = 0;
129 mPoolHead[Type].MemoryType = (EFI_MEMORY_TYPE) Type;
130 for (Index=0; Index < MAX_POOL_LIST; Index++) {
131 InitializeListHead (&mPoolHead[Type].FreeList[Index]);
132 }
133 }
134 }
135
136
137 /**
138 Look up pool head for specified memory type.
139
140 @param MemoryType Memory type of which pool head is looked for
141
142 @return Pointer of Corresponding pool head.
143
144 **/
145 POOL *
146 LookupPoolHead (
147 IN EFI_MEMORY_TYPE MemoryType
148 )
149 {
150 LIST_ENTRY *Link;
151 POOL *Pool;
152 UINTN Index;
153
154 if ((UINT32)MemoryType < EfiMaxMemoryType) {
155 return &mPoolHead[MemoryType];
156 }
157
158 //
159 // MemoryType values in the range 0x80000000..0xFFFFFFFF are reserved for use by UEFI
160 // OS loaders that are provided by operating system vendors.
161 // MemoryType values in the range 0x70000000..0x7FFFFFFF are reserved for OEM use.
162 //
163 if ((UINT32) MemoryType >= MEMORY_TYPE_OEM_RESERVED_MIN) {
164
165 for (Link = mPoolHeadList.ForwardLink; Link != &mPoolHeadList; Link = Link->ForwardLink) {
166 Pool = CR(Link, POOL, Link, POOL_SIGNATURE);
167 if (Pool->MemoryType == MemoryType) {
168 return Pool;
169 }
170 }
171
172 Pool = CoreAllocatePoolI (EfiBootServicesData, sizeof (POOL));
173 if (Pool == NULL) {
174 return NULL;
175 }
176
177 Pool->Signature = POOL_SIGNATURE;
178 Pool->Used = 0;
179 Pool->MemoryType = MemoryType;
180 for (Index=0; Index < MAX_POOL_LIST; Index++) {
181 InitializeListHead (&Pool->FreeList[Index]);
182 }
183
184 InsertHeadList (&mPoolHeadList, &Pool->Link);
185
186 return Pool;
187 }
188
189 return NULL;
190 }
191
192
193
194 /**
195 Allocate pool of a particular type.
196
197 @param PoolType Type of pool to allocate
198 @param Size The amount of pool to allocate
199 @param Buffer The address to return a pointer to the allocated
200 pool
201
202 @retval EFI_INVALID_PARAMETER Buffer is NULL.
203 PoolType is in the range EfiMaxMemoryType..0x6FFFFFFF.
204 PoolType is EfiPersistentMemory.
205 @retval EFI_OUT_OF_RESOURCES Size exceeds max pool size or allocation failed.
206 @retval EFI_SUCCESS Pool successfully allocated.
207
208 **/
209 EFI_STATUS
210 EFIAPI
211 CoreInternalAllocatePool (
212 IN EFI_MEMORY_TYPE PoolType,
213 IN UINTN Size,
214 OUT VOID **Buffer
215 )
216 {
217 EFI_STATUS Status;
218
219 //
220 // If it's not a valid type, fail it
221 //
222 if ((PoolType >= EfiMaxMemoryType && PoolType < MEMORY_TYPE_OEM_RESERVED_MIN) ||
223 (PoolType == EfiConventionalMemory) || (PoolType == EfiPersistentMemory)) {
224 return EFI_INVALID_PARAMETER;
225 }
226
227 if (Buffer == NULL) {
228 return EFI_INVALID_PARAMETER;
229 }
230
231 *Buffer = NULL;
232
233 //
234 // If size is too large, fail it
235 // Base on the EFI spec, return status of EFI_OUT_OF_RESOURCES
236 //
237 if (Size > MAX_POOL_SIZE) {
238 return EFI_OUT_OF_RESOURCES;
239 }
240
241 //
242 // Acquire the memory lock and make the allocation
243 //
244 Status = CoreAcquireLockOrFail (&mPoolMemoryLock);
245 if (EFI_ERROR (Status)) {
246 return EFI_OUT_OF_RESOURCES;
247 }
248
249 *Buffer = CoreAllocatePoolI (PoolType, Size);
250 CoreReleaseLock (&mPoolMemoryLock);
251 return (*Buffer != NULL) ? EFI_SUCCESS : EFI_OUT_OF_RESOURCES;
252 }
253
254 /**
255 Allocate pool of a particular type.
256
257 @param PoolType Type of pool to allocate
258 @param Size The amount of pool to allocate
259 @param Buffer The address to return a pointer to the allocated
260 pool
261
262 @retval EFI_INVALID_PARAMETER Buffer is NULL.
263 PoolType is in the range EfiMaxMemoryType..0x6FFFFFFF.
264 PoolType is EfiPersistentMemory.
265 @retval EFI_OUT_OF_RESOURCES Size exceeds max pool size or allocation failed.
266 @retval EFI_SUCCESS Pool successfully allocated.
267
268 **/
269 EFI_STATUS
270 EFIAPI
271 CoreAllocatePool (
272 IN EFI_MEMORY_TYPE PoolType,
273 IN UINTN Size,
274 OUT VOID **Buffer
275 )
276 {
277 EFI_STATUS Status;
278
279 Status = CoreInternalAllocatePool (PoolType, Size, Buffer);
280 if (!EFI_ERROR (Status)) {
281 CoreUpdateProfile (
282 (EFI_PHYSICAL_ADDRESS) (UINTN) RETURN_ADDRESS (0),
283 MemoryProfileActionAllocatePool,
284 PoolType,
285 Size,
286 *Buffer,
287 NULL
288 );
289 InstallMemoryAttributesTableOnMemoryAllocation (PoolType);
290 }
291 return Status;
292 }
293
294 STATIC
295 VOID *
296 CoreAllocatePoolPagesI (
297 IN EFI_MEMORY_TYPE PoolType,
298 IN UINTN NoPages,
299 IN UINTN Granularity
300 )
301 {
302 VOID *Buffer;
303 EFI_STATUS Status;
304
305 Status = CoreAcquireLockOrFail (&gMemoryLock);
306 if (EFI_ERROR (Status)) {
307 return NULL;
308 }
309
310 Buffer = CoreAllocatePoolPages (PoolType, NoPages, Granularity);
311 CoreReleaseMemoryLock ();
312
313 return Buffer;
314 }
315
316 /**
317 Internal function to allocate pool of a particular type.
318 Caller must have the memory lock held
319
320 @param PoolType Type of pool to allocate
321 @param Size The amount of pool to allocate
322
323 @return The allocate pool, or NULL
324
325 **/
326 VOID *
327 CoreAllocatePoolI (
328 IN EFI_MEMORY_TYPE PoolType,
329 IN UINTN Size
330 )
331 {
332 POOL *Pool;
333 POOL_FREE *Free;
334 POOL_HEAD *Head;
335 POOL_TAIL *Tail;
336 CHAR8 *NewPage;
337 VOID *Buffer;
338 UINTN Index;
339 UINTN FSize;
340 UINTN Offset, MaxOffset;
341 UINTN NoPages;
342 UINTN Granularity;
343
344 ASSERT_LOCKED (&mPoolMemoryLock);
345
346 if (PoolType == EfiACPIReclaimMemory ||
347 PoolType == EfiACPIMemoryNVS ||
348 PoolType == EfiRuntimeServicesCode ||
349 PoolType == EfiRuntimeServicesData) {
350
351 Granularity = EFI_ACPI_RUNTIME_PAGE_ALLOCATION_ALIGNMENT;
352 } else {
353 Granularity = DEFAULT_PAGE_ALLOCATION;
354 }
355
356 //
357 // Adjust the size by the pool header & tail overhead
358 //
359
360 //
361 // Adjusting the Size to be of proper alignment so that
362 // we don't get an unaligned access fault later when
363 // pool_Tail is being initialized
364 //
365 Size = ALIGN_VARIABLE (Size);
366
367 Size += POOL_OVERHEAD;
368 Index = SIZE_TO_LIST(Size);
369 Pool = LookupPoolHead (PoolType);
370 if (Pool== NULL) {
371 return NULL;
372 }
373 Head = NULL;
374
375 //
376 // If allocation is over max size, just allocate pages for the request
377 // (slow)
378 //
379 if (Index >= SIZE_TO_LIST (Granularity)) {
380 NoPages = EFI_SIZE_TO_PAGES(Size) + EFI_SIZE_TO_PAGES (Granularity) - 1;
381 NoPages &= ~(UINTN)(EFI_SIZE_TO_PAGES (Granularity) - 1);
382 Head = CoreAllocatePoolPagesI (PoolType, NoPages, Granularity);
383 goto Done;
384 }
385
386 //
387 // If there's no free pool in the proper list size, go get some more pages
388 //
389 if (IsListEmpty (&Pool->FreeList[Index])) {
390
391 Offset = LIST_TO_SIZE (Index);
392 MaxOffset = Granularity;
393
394 //
395 // Check the bins holding larger blocks, and carve one up if needed
396 //
397 while (++Index < SIZE_TO_LIST (Granularity)) {
398 if (!IsListEmpty (&Pool->FreeList[Index])) {
399 Free = CR (Pool->FreeList[Index].ForwardLink, POOL_FREE, Link, POOL_FREE_SIGNATURE);
400 RemoveEntryList (&Free->Link);
401 NewPage = (VOID *) Free;
402 MaxOffset = LIST_TO_SIZE (Index);
403 goto Carve;
404 }
405 }
406
407 //
408 // Get another page
409 //
410 NewPage = CoreAllocatePoolPagesI (PoolType, EFI_SIZE_TO_PAGES (Granularity), Granularity);
411 if (NewPage == NULL) {
412 goto Done;
413 }
414
415 //
416 // Serve the allocation request from the head of the allocated block
417 //
418 Carve:
419 Head = (POOL_HEAD *) NewPage;
420
421 //
422 // Carve up remaining space into free pool blocks
423 //
424 Index--;
425 while (Offset < MaxOffset) {
426 ASSERT (Index < MAX_POOL_LIST);
427 FSize = LIST_TO_SIZE(Index);
428
429 while (Offset + FSize <= MaxOffset) {
430 Free = (POOL_FREE *) &NewPage[Offset];
431 Free->Signature = POOL_FREE_SIGNATURE;
432 Free->Index = (UINT32)Index;
433 InsertHeadList (&Pool->FreeList[Index], &Free->Link);
434 Offset += FSize;
435 }
436 Index -= 1;
437 }
438
439 ASSERT (Offset == MaxOffset);
440 goto Done;
441 }
442
443 //
444 // Remove entry from free pool list
445 //
446 Free = CR (Pool->FreeList[Index].ForwardLink, POOL_FREE, Link, POOL_FREE_SIGNATURE);
447 RemoveEntryList (&Free->Link);
448
449 Head = (POOL_HEAD *) Free;
450
451 Done:
452 Buffer = NULL;
453
454 if (Head != NULL) {
455
456 //
457 // If we have a pool buffer, fill in the header & tail info
458 //
459 Head->Signature = POOL_HEAD_SIGNATURE;
460 Head->Size = Size;
461 Head->Type = (EFI_MEMORY_TYPE) PoolType;
462 Tail = HEAD_TO_TAIL (Head);
463 Tail->Signature = POOL_TAIL_SIGNATURE;
464 Tail->Size = Size;
465 Buffer = Head->Data;
466 DEBUG_CLEAR_MEMORY (Buffer, Size - POOL_OVERHEAD);
467
468 DEBUG ((
469 DEBUG_POOL,
470 "AllocatePoolI: Type %x, Addr %p (len %lx) %,ld\n", PoolType,
471 Buffer,
472 (UINT64)(Size - POOL_OVERHEAD),
473 (UINT64) Pool->Used
474 ));
475
476 //
477 // Account the allocation
478 //
479 Pool->Used += Size;
480
481 } else {
482 DEBUG ((DEBUG_ERROR | DEBUG_POOL, "AllocatePool: failed to allocate %ld bytes\n", (UINT64) Size));
483 }
484
485 return Buffer;
486 }
487
488
489
490 /**
491 Frees pool.
492
493 @param Buffer The allocated pool entry to free
494 @param PoolType Pointer to pool type
495
496 @retval EFI_INVALID_PARAMETER Buffer is not a valid value.
497 @retval EFI_SUCCESS Pool successfully freed.
498
499 **/
500 EFI_STATUS
501 EFIAPI
502 CoreInternalFreePool (
503 IN VOID *Buffer,
504 OUT EFI_MEMORY_TYPE *PoolType OPTIONAL
505 )
506 {
507 EFI_STATUS Status;
508
509 if (Buffer == NULL) {
510 return EFI_INVALID_PARAMETER;
511 }
512
513 CoreAcquireLock (&mPoolMemoryLock);
514 Status = CoreFreePoolI (Buffer, PoolType);
515 CoreReleaseLock (&mPoolMemoryLock);
516 return Status;
517 }
518
519 /**
520 Frees pool.
521
522 @param Buffer The allocated pool entry to free
523
524 @retval EFI_INVALID_PARAMETER Buffer is not a valid value.
525 @retval EFI_SUCCESS Pool successfully freed.
526
527 **/
528 EFI_STATUS
529 EFIAPI
530 CoreFreePool (
531 IN VOID *Buffer
532 )
533 {
534 EFI_STATUS Status;
535 EFI_MEMORY_TYPE PoolType;
536
537 Status = CoreInternalFreePool (Buffer, &PoolType);
538 if (!EFI_ERROR (Status)) {
539 CoreUpdateProfile (
540 (EFI_PHYSICAL_ADDRESS) (UINTN) RETURN_ADDRESS (0),
541 MemoryProfileActionFreePool,
542 PoolType,
543 0,
544 Buffer,
545 NULL
546 );
547 InstallMemoryAttributesTableOnMemoryAllocation (PoolType);
548 }
549 return Status;
550 }
551
552 STATIC
553 VOID
554 CoreFreePoolPagesI (
555 IN EFI_MEMORY_TYPE PoolType,
556 IN EFI_PHYSICAL_ADDRESS Memory,
557 IN UINTN NoPages
558 )
559 {
560 CoreAcquireMemoryLock ();
561 CoreFreePoolPages (Memory, NoPages);
562 CoreReleaseMemoryLock ();
563 }
564
565 /**
566 Internal function to free a pool entry.
567 Caller must have the memory lock held
568
569 @param Buffer The allocated pool entry to free
570 @param PoolType Pointer to pool type
571
572 @retval EFI_INVALID_PARAMETER Buffer not valid
573 @retval EFI_SUCCESS Buffer successfully freed.
574
575 **/
576 EFI_STATUS
577 CoreFreePoolI (
578 IN VOID *Buffer,
579 OUT EFI_MEMORY_TYPE *PoolType OPTIONAL
580 )
581 {
582 POOL *Pool;
583 POOL_HEAD *Head;
584 POOL_TAIL *Tail;
585 POOL_FREE *Free;
586 UINTN Index;
587 UINTN NoPages;
588 UINTN Size;
589 CHAR8 *NewPage;
590 UINTN Offset;
591 BOOLEAN AllFree;
592 UINTN Granularity;
593
594 ASSERT(Buffer != NULL);
595 //
596 // Get the head & tail of the pool entry
597 //
598 Head = CR (Buffer, POOL_HEAD, Data, POOL_HEAD_SIGNATURE);
599 ASSERT(Head != NULL);
600
601 if (Head->Signature != POOL_HEAD_SIGNATURE) {
602 return EFI_INVALID_PARAMETER;
603 }
604
605 Tail = HEAD_TO_TAIL (Head);
606 ASSERT(Tail != NULL);
607
608 //
609 // Debug
610 //
611 ASSERT (Tail->Signature == POOL_TAIL_SIGNATURE);
612 ASSERT (Head->Size == Tail->Size);
613 ASSERT_LOCKED (&mPoolMemoryLock);
614
615 if (Tail->Signature != POOL_TAIL_SIGNATURE) {
616 return EFI_INVALID_PARAMETER;
617 }
618
619 if (Head->Size != Tail->Size) {
620 return EFI_INVALID_PARAMETER;
621 }
622
623 //
624 // Determine the pool type and account for it
625 //
626 Size = Head->Size;
627 Pool = LookupPoolHead (Head->Type);
628 if (Pool == NULL) {
629 return EFI_INVALID_PARAMETER;
630 }
631 Pool->Used -= Size;
632 DEBUG ((DEBUG_POOL, "FreePool: %p (len %lx) %,ld\n", Head->Data, (UINT64)(Head->Size - POOL_OVERHEAD), (UINT64) Pool->Used));
633
634 if (Head->Type == EfiACPIReclaimMemory ||
635 Head->Type == EfiACPIMemoryNVS ||
636 Head->Type == EfiRuntimeServicesCode ||
637 Head->Type == EfiRuntimeServicesData) {
638
639 Granularity = EFI_ACPI_RUNTIME_PAGE_ALLOCATION_ALIGNMENT;
640 } else {
641 Granularity = DEFAULT_PAGE_ALLOCATION;
642 }
643
644 if (PoolType != NULL) {
645 *PoolType = Head->Type;
646 }
647
648 //
649 // Determine the pool list
650 //
651 Index = SIZE_TO_LIST(Size);
652 DEBUG_CLEAR_MEMORY (Head, Size);
653
654 //
655 // If it's not on the list, it must be pool pages
656 //
657 if (Index >= SIZE_TO_LIST (Granularity)) {
658
659 //
660 // Return the memory pages back to free memory
661 //
662 NoPages = EFI_SIZE_TO_PAGES(Size) + EFI_SIZE_TO_PAGES (Granularity) - 1;
663 NoPages &= ~(UINTN)(EFI_SIZE_TO_PAGES (Granularity) - 1);
664 CoreFreePoolPagesI (Pool->MemoryType, (EFI_PHYSICAL_ADDRESS) (UINTN) Head, NoPages);
665
666 } else {
667
668 //
669 // Put the pool entry onto the free pool list
670 //
671 Free = (POOL_FREE *) Head;
672 ASSERT(Free != NULL);
673 Free->Signature = POOL_FREE_SIGNATURE;
674 Free->Index = (UINT32)Index;
675 InsertHeadList (&Pool->FreeList[Index], &Free->Link);
676
677 //
678 // See if all the pool entries in the same page as Free are freed pool
679 // entries
680 //
681 NewPage = (CHAR8 *)((UINTN)Free & ~(Granularity - 1));
682 Free = (POOL_FREE *) &NewPage[0];
683 ASSERT(Free != NULL);
684
685 if (Free->Signature == POOL_FREE_SIGNATURE) {
686
687 AllFree = TRUE;
688 Offset = 0;
689
690 while ((Offset < Granularity) && (AllFree)) {
691 Free = (POOL_FREE *) &NewPage[Offset];
692 ASSERT(Free != NULL);
693 if (Free->Signature != POOL_FREE_SIGNATURE) {
694 AllFree = FALSE;
695 }
696 Offset += LIST_TO_SIZE(Free->Index);
697 }
698
699 if (AllFree) {
700
701 //
702 // All of the pool entries in the same page as Free are free pool
703 // entries
704 // Remove all of these pool entries from the free loop lists.
705 //
706 Free = (POOL_FREE *) &NewPage[0];
707 ASSERT(Free != NULL);
708 Offset = 0;
709
710 while (Offset < Granularity) {
711 Free = (POOL_FREE *) &NewPage[Offset];
712 ASSERT(Free != NULL);
713 RemoveEntryList (&Free->Link);
714 Offset += LIST_TO_SIZE(Free->Index);
715 }
716
717 //
718 // Free the page
719 //
720 CoreFreePoolPagesI (Pool->MemoryType, (EFI_PHYSICAL_ADDRESS) (UINTN)NewPage,
721 EFI_SIZE_TO_PAGES (Granularity));
722 }
723 }
724 }
725
726 //
727 // If this is an OS/OEM specific memory type, then check to see if the last
728 // portion of that memory type has been freed. If it has, then free the
729 // list entry for that memory type
730 //
731 if (((UINT32) Pool->MemoryType >= MEMORY_TYPE_OEM_RESERVED_MIN) && Pool->Used == 0) {
732 RemoveEntryList (&Pool->Link);
733 CoreFreePoolI (Pool, NULL);
734 }
735
736 return EFI_SUCCESS;
737 }
738