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