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