]> git.proxmox.com Git - mirror_edk2.git/blob - MdeModulePkg/Core/Dxe/Mem/Pool.c
projects / mirror_edk2.git / blob
? search:


2980e2293e3d1dadd59e4130cb6c7387aef8beda
[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 ((EFI_PHYSICAL_ADDRESS) (UINTN) RETURN_ADDRESS (0), MemoryProfileActionAllocatePool, PoolType, Size, *Buffer);
280 InstallMemoryAttributesTableOnMemoryAllocation (PoolType);
281 }
282 return Status;
283 }
284
285 /**
286 Internal function to allocate pool of a particular type.
287 Caller must have the memory lock held
288
289 @param PoolType Type of pool to allocate
290 @param Size The amount of pool to allocate
291
292 @return The allocate pool, or NULL
293
294 **/
295 VOID *
296 CoreAllocatePoolI (
297 IN EFI_MEMORY_TYPE PoolType,
298 IN UINTN Size
299 )
300 {
301 POOL *Pool;
302 POOL_FREE *Free;
303 POOL_HEAD *Head;
304 POOL_TAIL *Tail;
305 CHAR8 *NewPage;
306 VOID *Buffer;
307 UINTN Index;
308 UINTN FSize;
309 UINTN Offset, MaxOffset;
310 UINTN NoPages;
311 UINTN Granularity;
312
313 ASSERT_LOCKED (&gMemoryLock);
314
315 if (PoolType == EfiACPIReclaimMemory ||
316 PoolType == EfiACPIMemoryNVS ||
317 PoolType == EfiRuntimeServicesCode ||
318 PoolType == EfiRuntimeServicesData) {
319
320 Granularity = EFI_ACPI_RUNTIME_PAGE_ALLOCATION_ALIGNMENT;
321 } else {
322 Granularity = DEFAULT_PAGE_ALLOCATION;
323 }
324
325 //
326 // Adjust the size by the pool header & tail overhead
327 //
328
329 //
330 // Adjusting the Size to be of proper alignment so that
331 // we don't get an unaligned access fault later when
332 // pool_Tail is being initialized
333 //
334 Size = ALIGN_VARIABLE (Size);
335
336 Size += POOL_OVERHEAD;
337 Index = SIZE_TO_LIST(Size);
338 Pool = LookupPoolHead (PoolType);
339 if (Pool== NULL) {
340 return NULL;
341 }
342 Head = NULL;
343
344 //
345 // If allocation is over max size, just allocate pages for the request
346 // (slow)
347 //
348 if (Index >= SIZE_TO_LIST (Granularity)) {
349 NoPages = EFI_SIZE_TO_PAGES(Size) + EFI_SIZE_TO_PAGES (Granularity) - 1;
350 NoPages &= ~(UINTN)(EFI_SIZE_TO_PAGES (Granularity) - 1);
351 Head = CoreAllocatePoolPages (PoolType, NoPages, Granularity);
352 goto Done;
353 }
354
355 //
356 // If there's no free pool in the proper list size, go get some more pages
357 //
358 if (IsListEmpty (&Pool->FreeList[Index])) {
359
360 Offset = LIST_TO_SIZE (Index);
361 MaxOffset = Granularity;
362
363 //
364 // Check the bins holding larger blocks, and carve one up if needed
365 //
366 while (++Index < SIZE_TO_LIST (Granularity)) {
367 if (!IsListEmpty (&Pool->FreeList[Index])) {
368 Free = CR (Pool->FreeList[Index].ForwardLink, POOL_FREE, Link, POOL_FREE_SIGNATURE);
369 RemoveEntryList (&Free->Link);
370 NewPage = (VOID *) Free;
371 MaxOffset = LIST_TO_SIZE (Index);
372 goto Carve;
373 }
374 }
375
376 //
377 // Get another page
378 //
379 NewPage = CoreAllocatePoolPages(PoolType, EFI_SIZE_TO_PAGES (Granularity), Granularity);
380 if (NewPage == NULL) {
381 goto Done;
382 }
383
384 //
385 // Serve the allocation request from the head of the allocated block
386 //
387 Carve:
388 Head = (POOL_HEAD *) NewPage;
389
390 //
391 // Carve up remaining space into free pool blocks
392 //
393 Index--;
394 while (Offset < MaxOffset) {
395 ASSERT (Index < MAX_POOL_LIST);
396 FSize = LIST_TO_SIZE(Index);
397
398 while (Offset + FSize <= MaxOffset) {
399 Free = (POOL_FREE *) &NewPage[Offset];
400 Free->Signature = POOL_FREE_SIGNATURE;
401 Free->Index = (UINT32)Index;
402 InsertHeadList (&Pool->FreeList[Index], &Free->Link);
403 Offset += FSize;
404 }
405 Index -= 1;
406 }
407
408 ASSERT (Offset == MaxOffset);
409 goto Done;
410 }
411
412 //
413 // Remove entry from free pool list
414 //
415 Free = CR (Pool->FreeList[Index].ForwardLink, POOL_FREE, Link, POOL_FREE_SIGNATURE);
416 RemoveEntryList (&Free->Link);
417
418 Head = (POOL_HEAD *) Free;
419
420 Done:
421 Buffer = NULL;
422
423 if (Head != NULL) {
424
425 //
426 // If we have a pool buffer, fill in the header & tail info
427 //
428 Head->Signature = POOL_HEAD_SIGNATURE;
429 Head->Size = Size;
430 Head->Type = (EFI_MEMORY_TYPE) PoolType;
431 Tail = HEAD_TO_TAIL (Head);
432 Tail->Signature = POOL_TAIL_SIGNATURE;
433 Tail->Size = Size;
434 Buffer = Head->Data;
435 DEBUG_CLEAR_MEMORY (Buffer, Size - POOL_OVERHEAD);
436
437 DEBUG ((
438 DEBUG_POOL,
439 "AllocatePoolI: Type %x, Addr %p (len %lx) %,ld\n", PoolType,
440 Buffer,
441 (UINT64)(Size - POOL_OVERHEAD),
442 (UINT64) Pool->Used
443 ));
444
445 //
446 // Account the allocation
447 //
448 Pool->Used += Size;
449
450 } else {
451 DEBUG ((DEBUG_ERROR | DEBUG_POOL, "AllocatePool: failed to allocate %ld bytes\n", (UINT64) Size));
452 }
453
454 return Buffer;
455 }
456
457
458
459 /**
460 Frees pool.
461
462 @param Buffer The allocated pool entry to free
463 @param PoolType Pointer to pool type
464
465 @retval EFI_INVALID_PARAMETER Buffer is not a valid value.
466 @retval EFI_SUCCESS Pool successfully freed.
467
468 **/
469 EFI_STATUS
470 EFIAPI
471 CoreInternalFreePool (
472 IN VOID *Buffer,
473 OUT EFI_MEMORY_TYPE *PoolType OPTIONAL
474 )
475 {
476 EFI_STATUS Status;
477
478 if (Buffer == NULL) {
479 return EFI_INVALID_PARAMETER;
480 }
481
482 CoreAcquireMemoryLock ();
483 Status = CoreFreePoolI (Buffer, PoolType);
484 CoreReleaseMemoryLock ();
485 return Status;
486 }
487
488 /**
489 Frees pool.
490
491 @param Buffer The allocated pool entry to free
492
493 @retval EFI_INVALID_PARAMETER Buffer is not a valid value.
494 @retval EFI_SUCCESS Pool successfully freed.
495
496 **/
497 EFI_STATUS
498 EFIAPI
499 CoreFreePool (
500 IN VOID *Buffer
501 )
502 {
503 EFI_STATUS Status;
504 EFI_MEMORY_TYPE PoolType;
505
506 Status = CoreInternalFreePool (Buffer, &PoolType);
507 if (!EFI_ERROR (Status)) {
508 CoreUpdateProfile ((EFI_PHYSICAL_ADDRESS) (UINTN) RETURN_ADDRESS (0), MemoryProfileActionFreePool, PoolType, 0, Buffer);
509 InstallMemoryAttributesTableOnMemoryAllocation (PoolType);
510 }
511 return Status;
512 }
513
514 /**
515 Internal function to free a pool entry.
516 Caller must have the memory lock held
517
518 @param Buffer The allocated pool entry to free
519 @param PoolType Pointer to pool type
520
521 @retval EFI_INVALID_PARAMETER Buffer not valid
522 @retval EFI_SUCCESS Buffer successfully freed.
523
524 **/
525 EFI_STATUS
526 CoreFreePoolI (
527 IN VOID *Buffer,
528 OUT EFI_MEMORY_TYPE *PoolType OPTIONAL
529 )
530 {
531 POOL *Pool;
532 POOL_HEAD *Head;
533 POOL_TAIL *Tail;
534 POOL_FREE *Free;
535 UINTN Index;
536 UINTN NoPages;
537 UINTN Size;
538 CHAR8 *NewPage;
539 UINTN Offset;
540 BOOLEAN AllFree;
541 UINTN Granularity;
542
543 ASSERT(Buffer != NULL);
544 //
545 // Get the head & tail of the pool entry
546 //
547 Head = CR (Buffer, POOL_HEAD, Data, POOL_HEAD_SIGNATURE);
548 ASSERT(Head != NULL);
549
550 if (Head->Signature != POOL_HEAD_SIGNATURE) {
551 return EFI_INVALID_PARAMETER;
552 }
553
554 Tail = HEAD_TO_TAIL (Head);
555 ASSERT(Tail != NULL);
556
557 //
558 // Debug
559 //
560 ASSERT (Tail->Signature == POOL_TAIL_SIGNATURE);
561 ASSERT (Head->Size == Tail->Size);
562 ASSERT_LOCKED (&gMemoryLock);
563
564 if (Tail->Signature != POOL_TAIL_SIGNATURE) {
565 return EFI_INVALID_PARAMETER;
566 }
567
568 if (Head->Size != Tail->Size) {
569 return EFI_INVALID_PARAMETER;
570 }
571
572 //
573 // Determine the pool type and account for it
574 //
575 Size = Head->Size;
576 Pool = LookupPoolHead (Head->Type);
577 if (Pool == NULL) {
578 return EFI_INVALID_PARAMETER;
579 }
580 Pool->Used -= Size;
581 DEBUG ((DEBUG_POOL, "FreePool: %p (len %lx) %,ld\n", Head->Data, (UINT64)(Head->Size - POOL_OVERHEAD), (UINT64) Pool->Used));
582
583 if (Head->Type == EfiACPIReclaimMemory ||
584 Head->Type == EfiACPIMemoryNVS ||
585 Head->Type == EfiRuntimeServicesCode ||
586 Head->Type == EfiRuntimeServicesData) {
587
588 Granularity = EFI_ACPI_RUNTIME_PAGE_ALLOCATION_ALIGNMENT;
589 } else {
590 Granularity = DEFAULT_PAGE_ALLOCATION;
591 }
592
593 if (PoolType != NULL) {
594 *PoolType = Head->Type;
595 }
596
597 //
598 // Determine the pool list
599 //
600 Index = SIZE_TO_LIST(Size);
601 DEBUG_CLEAR_MEMORY (Head, Size);
602
603 //
604 // If it's not on the list, it must be pool pages
605 //
606 if (Index >= SIZE_TO_LIST (Granularity)) {
607
608 //
609 // Return the memory pages back to free memory
610 //
611 NoPages = EFI_SIZE_TO_PAGES(Size) + EFI_SIZE_TO_PAGES (Granularity) - 1;
612 NoPages &= ~(UINTN)(EFI_SIZE_TO_PAGES (Granularity) - 1);
613 CoreFreePoolPages ((EFI_PHYSICAL_ADDRESS) (UINTN) Head, NoPages);
614
615 } else {
616
617 //
618 // Put the pool entry onto the free pool list
619 //
620 Free = (POOL_FREE *) Head;
621 ASSERT(Free != NULL);
622 Free->Signature = POOL_FREE_SIGNATURE;
623 Free->Index = (UINT32)Index;
624 InsertHeadList (&Pool->FreeList[Index], &Free->Link);
625
626 //
627 // See if all the pool entries in the same page as Free are freed pool
628 // entries
629 //
630 NewPage = (CHAR8 *)((UINTN)Free & ~(Granularity - 1));
631 Free = (POOL_FREE *) &NewPage[0];
632 ASSERT(Free != NULL);
633
634 if (Free->Signature == POOL_FREE_SIGNATURE) {
635
636 AllFree = TRUE;
637 Offset = 0;
638
639 while ((Offset < Granularity) && (AllFree)) {
640 Free = (POOL_FREE *) &NewPage[Offset];
641 ASSERT(Free != NULL);
642 if (Free->Signature != POOL_FREE_SIGNATURE) {
643 AllFree = FALSE;
644 }
645 Offset += LIST_TO_SIZE(Free->Index);
646 }
647
648 if (AllFree) {
649
650 //
651 // All of the pool entries in the same page as Free are free pool
652 // entries
653 // Remove all of these pool entries from the free loop lists.
654 //
655 Free = (POOL_FREE *) &NewPage[0];
656 ASSERT(Free != NULL);
657 Offset = 0;
658
659 while (Offset < Granularity) {
660 Free = (POOL_FREE *) &NewPage[Offset];
661 ASSERT(Free != NULL);
662 RemoveEntryList (&Free->Link);
663 Offset += LIST_TO_SIZE(Free->Index);
664 }
665
666 //
667 // Free the page
668 //
669 CoreFreePoolPages ((EFI_PHYSICAL_ADDRESS) (UINTN)NewPage, EFI_SIZE_TO_PAGES (Granularity));
670 }
671 }
672 }
673
674 //
675 // If this is an OS/OEM specific memory type, then check to see if the last
676 // portion of that memory type has been freed. If it has, then free the
677 // list entry for that memory type
678 //
679 if (((UINT32) Pool->MemoryType >= MEMORY_TYPE_OEM_RESERVED_MIN) && Pool->Used == 0) {
680 RemoveEntryList (&Pool->Link);
681 CoreFreePoolI (Pool, NULL);
682 }
683
684 return EFI_SUCCESS;
685 }
686
EFI Development Kit II mirror for PVE