MdeModulePkg/Core/Dxe/Mem/Pool.c

   1 /** @file
   2   UEFI Memory pool management functions.
   3
   4 Copyright (c) 2006 - 2015, 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   //
 160   if ((INT32)MemoryType < 0) {
 161
 162     for (Link = mPoolHeadList.ForwardLink; Link != &mPoolHeadList; Link = Link->ForwardLink) {
 163       Pool = CR(Link, POOL, Link, POOL_SIGNATURE);
 164       if (Pool->MemoryType == MemoryType) {
 165         return Pool;
 166       }
 167     }
 168
 169     Pool = CoreAllocatePoolI (EfiBootServicesData, sizeof (POOL));
 170     if (Pool == NULL) {
 171       return NULL;
 172     }
 173
 174     Pool->Signature = POOL_SIGNATURE;
 175     Pool->Used      = 0;
 176     Pool->MemoryType = MemoryType;
 177     for (Index=0; Index < MAX_POOL_LIST; Index++) {
 178       InitializeListHead (&Pool->FreeList[Index]);
 179     }
 180
 181     InsertHeadList (&mPoolHeadList, &Pool->Link);
 182
 183     return Pool;
 184   }
 185
 186   return NULL;
 187 }
 188
 189
 190
 191 /**
 192   Allocate pool of a particular type.
 193
 194   @param  PoolType               Type of pool to allocate
 195   @param  Size                   The amount of pool to allocate
 196   @param  Buffer                 The address to return a pointer to the allocated
 197                                  pool
 198
 199   @retval EFI_INVALID_PARAMETER  PoolType not valid or Buffer is NULL.
 200                                  PoolType was EfiPersistentMemory.
 201   @retval EFI_OUT_OF_RESOURCES   Size exceeds max pool size or allocation failed.
 202   @retval EFI_SUCCESS            Pool successfully allocated.
 203
 204 **/
 205 EFI_STATUS
 206 EFIAPI
 207 CoreInternalAllocatePool (
 208   IN EFI_MEMORY_TYPE  PoolType,
 209   IN UINTN            Size,
 210   OUT VOID            **Buffer
 211   )
 212 {
 213   EFI_STATUS    Status;
 214
 215   //
 216   // If it's not a valid type, fail it
 217   //
 218   if ((PoolType >= EfiMaxMemoryType && PoolType <= 0x7fffffff) ||
 219        (PoolType == EfiConventionalMemory) || (PoolType == EfiPersistentMemory)) {
 220     return EFI_INVALID_PARAMETER;
 221   }
 222
 223   if (Buffer == NULL) {
 224     return EFI_INVALID_PARAMETER;
 225   }
 226
 227   *Buffer = NULL;
 228
 229   //
 230   // If size is too large, fail it
 231   // Base on the EFI spec, return status of EFI_OUT_OF_RESOURCES
 232   //
 233   if (Size > MAX_POOL_SIZE) {
 234     return EFI_OUT_OF_RESOURCES;
 235   }
 236
 237   //
 238   // Acquire the memory lock and make the allocation
 239   //
 240   Status = CoreAcquireLockOrFail (&gMemoryLock);
 241   if (EFI_ERROR (Status)) {
 242     return EFI_OUT_OF_RESOURCES;
 243   }
 244
 245   *Buffer = CoreAllocatePoolI (PoolType, Size);
 246   CoreReleaseMemoryLock ();
 247   return (*Buffer != NULL) ? EFI_SUCCESS : EFI_OUT_OF_RESOURCES;
 248 }
 249
 250 /**
 251   Allocate pool of a particular type.
 252
 253   @param  PoolType               Type of pool to allocate
 254   @param  Size                   The amount of pool to allocate
 255   @param  Buffer                 The address to return a pointer to the allocated
 256                                  pool
 257
 258   @retval EFI_INVALID_PARAMETER  PoolType not valid or Buffer is NULL.
 259   @retval EFI_OUT_OF_RESOURCES   Size exceeds max pool size or allocation failed.
 260   @retval EFI_SUCCESS            Pool successfully allocated.
 261
 262 **/
 263 EFI_STATUS
 264 EFIAPI
 265 CoreAllocatePool (
 266   IN EFI_MEMORY_TYPE  PoolType,
 267   IN UINTN            Size,
 268   OUT VOID            **Buffer
 269   )
 270 {
 271   EFI_STATUS  Status;
 272
 273   Status = CoreInternalAllocatePool (PoolType, Size, Buffer);
 274   if (!EFI_ERROR (Status)) {
 275     CoreUpdateProfile ((EFI_PHYSICAL_ADDRESS) (UINTN) RETURN_ADDRESS (0), MemoryProfileActionAllocatePool, PoolType, Size, *Buffer);
 276   }
 277   return Status;
 278 }
 279
 280 /**
 281   Internal function to allocate pool of a particular type.
 282   Caller must have the memory lock held
 283
 284   @param  PoolType               Type of pool to allocate
 285   @param  Size                   The amount of pool to allocate
 286
 287   @return The allocate pool, or NULL
 288
 289 **/
 290 VOID *
 291 CoreAllocatePoolI (
 292   IN EFI_MEMORY_TYPE  PoolType,
 293   IN UINTN            Size
 294   )
 295 {
 296   POOL        *Pool;
 297   POOL_FREE   *Free;
 298   POOL_HEAD   *Head;
 299   POOL_TAIL   *Tail;
 300   CHAR8       *NewPage;
 301   VOID        *Buffer;
 302   UINTN       Index;
 303   UINTN       FSize;
 304   UINTN       Offset, MaxOffset;
 305   UINTN       NoPages;
 306   UINTN       Granularity;
 307
 308   ASSERT_LOCKED (&gMemoryLock);
 309
 310   if  (PoolType == EfiACPIReclaimMemory   ||
 311        PoolType == EfiACPIMemoryNVS       ||
 312        PoolType == EfiRuntimeServicesCode ||
 313        PoolType == EfiRuntimeServicesData) {
 314
 315     Granularity = EFI_ACPI_RUNTIME_PAGE_ALLOCATION_ALIGNMENT;
 316   } else {
 317     Granularity = DEFAULT_PAGE_ALLOCATION;
 318   }
 319
 320   //
 321   // Adjust the size by the pool header & tail overhead
 322   //
 323
 324   //
 325   // Adjusting the Size to be of proper alignment so that
 326   // we don't get an unaligned access fault later when
 327   // pool_Tail is being initialized
 328   //
 329   Size = ALIGN_VARIABLE (Size);
 330
 331   Size += POOL_OVERHEAD;
 332   Index = SIZE_TO_LIST(Size);
 333   Pool = LookupPoolHead (PoolType);
 334   if (Pool== NULL) {
 335     return NULL;
 336   }
 337   Head = NULL;
 338
 339   //
 340   // If allocation is over max size, just allocate pages for the request
 341   // (slow)
 342   //
 343   if (Index >= SIZE_TO_LIST (Granularity)) {
 344     NoPages = EFI_SIZE_TO_PAGES(Size) + EFI_SIZE_TO_PAGES (Granularity) - 1;
 345     NoPages &= ~(UINTN)(EFI_SIZE_TO_PAGES (Granularity) - 1);
 346     Head = CoreAllocatePoolPages (PoolType, NoPages, Granularity);
 347     goto Done;
 348   }
 349
 350   //
 351   // If there's no free pool in the proper list size, go get some more pages
 352   //
 353   if (IsListEmpty (&Pool->FreeList[Index])) {
 354
 355     Offset = LIST_TO_SIZE (Index);
 356     MaxOffset = Granularity;
 357
 358     //
 359     // Check the bins holding larger blocks, and carve one up if needed
 360     //
 361     while (++Index < SIZE_TO_LIST (Granularity)) {
 362       if (!IsListEmpty (&Pool->FreeList[Index])) {
 363         Free = CR (Pool->FreeList[Index].ForwardLink, POOL_FREE, Link, POOL_FREE_SIGNATURE);
 364         RemoveEntryList (&Free->Link);
 365         NewPage = (VOID *) Free;
 366         MaxOffset = LIST_TO_SIZE (Index);
 367         goto Carve;
 368       }
 369     }
 370
 371     //
 372     // Get another page
 373     //
 374     NewPage = CoreAllocatePoolPages(PoolType, EFI_SIZE_TO_PAGES (Granularity), Granularity);
 375     if (NewPage == NULL) {
 376       goto Done;
 377     }
 378
 379     //
 380     // Serve the allocation request from the head of the allocated block
 381     //
 382 Carve:
 383     Head = (POOL_HEAD *) NewPage;
 384
 385     //
 386     // Carve up remaining space into free pool blocks
 387     //
 388     Index--;
 389     while (Offset < MaxOffset) {
 390       ASSERT (Index < MAX_POOL_LIST);
 391       FSize = LIST_TO_SIZE(Index);
 392
 393       while (Offset + FSize <= MaxOffset) {
 394         Free = (POOL_FREE *) &NewPage[Offset];
 395         Free->Signature = POOL_FREE_SIGNATURE;
 396         Free->Index     = (UINT32)Index;
 397         InsertHeadList (&Pool->FreeList[Index], &Free->Link);
 398         Offset += FSize;
 399       }
 400       Index -= 1;
 401     }
 402
 403     ASSERT (Offset == MaxOffset);
 404     goto Done;
 405   }
 406
 407   //
 408   // Remove entry from free pool list
 409   //
 410   Free = CR (Pool->FreeList[Index].ForwardLink, POOL_FREE, Link, POOL_FREE_SIGNATURE);
 411   RemoveEntryList (&Free->Link);
 412
 413   Head = (POOL_HEAD *) Free;
 414
 415 Done:
 416   Buffer = NULL;
 417
 418   if (Head != NULL) {
 419
 420     //
 421     // If we have a pool buffer, fill in the header & tail info
 422     //
 423     Head->Signature = POOL_HEAD_SIGNATURE;
 424     Head->Size      = Size;
 425     Head->Type      = (EFI_MEMORY_TYPE) PoolType;
 426     Tail            = HEAD_TO_TAIL (Head);
 427     Tail->Signature = POOL_TAIL_SIGNATURE;
 428     Tail->Size      = Size;
 429     Buffer          = Head->Data;
 430     DEBUG_CLEAR_MEMORY (Buffer, Size - POOL_OVERHEAD);
 431
 432     DEBUG ((
 433       DEBUG_POOL,
 434       "AllocatePoolI: Type %x, Addr %p (len %lx) %,ld\n", PoolType,
 435       Buffer,
 436       (UINT64)(Size - POOL_OVERHEAD),
 437       (UINT64) Pool->Used
 438       ));
 439
 440     //
 441     // Account the allocation
 442     //
 443     Pool->Used += Size;
 444
 445   } else {
 446     DEBUG ((DEBUG_ERROR | DEBUG_POOL, "AllocatePool: failed to allocate %ld bytes\n", (UINT64) Size));
 447   }
 448
 449   return Buffer;
 450 }
 451
 452
 453
 454 /**
 455   Frees pool.
 456
 457   @param  Buffer                 The allocated pool entry to free
 458
 459   @retval EFI_INVALID_PARAMETER  Buffer is not a valid value.
 460   @retval EFI_SUCCESS            Pool successfully freed.
 461
 462 **/
 463 EFI_STATUS
 464 EFIAPI
 465 CoreInternalFreePool (
 466   IN VOID        *Buffer
 467   )
 468 {
 469   EFI_STATUS Status;
 470
 471   if (Buffer == NULL) {
 472     return EFI_INVALID_PARAMETER;
 473   }
 474
 475   CoreAcquireMemoryLock ();
 476   Status = CoreFreePoolI (Buffer);
 477   CoreReleaseMemoryLock ();
 478   return Status;
 479 }
 480
 481 /**
 482   Frees pool.
 483
 484   @param  Buffer                 The allocated pool entry to free
 485
 486   @retval EFI_INVALID_PARAMETER  Buffer is not a valid value.
 487   @retval EFI_SUCCESS            Pool successfully freed.
 488
 489 **/
 490 EFI_STATUS
 491 EFIAPI
 492 CoreFreePool (
 493   IN VOID  *Buffer
 494   )
 495 {
 496   EFI_STATUS  Status;
 497
 498   Status = CoreInternalFreePool (Buffer);
 499   if (!EFI_ERROR (Status)) {
 500     CoreUpdateProfile ((EFI_PHYSICAL_ADDRESS) (UINTN) RETURN_ADDRESS (0), MemoryProfileActionFreePool, (EFI_MEMORY_TYPE) 0, 0, Buffer);
 501   }
 502   return Status;
 503 }
 504
 505 /**
 506   Internal function to free a pool entry.
 507   Caller must have the memory lock held
 508
 509   @param  Buffer                 The allocated pool entry to free
 510
 511   @retval EFI_INVALID_PARAMETER  Buffer not valid
 512   @retval EFI_SUCCESS            Buffer successfully freed.
 513
 514 **/
 515 EFI_STATUS
 516 CoreFreePoolI (
 517   IN VOID       *Buffer
 518   )
 519 {
 520   POOL        *Pool;
 521   POOL_HEAD   *Head;
 522   POOL_TAIL   *Tail;
 523   POOL_FREE   *Free;
 524   UINTN       Index;
 525   UINTN       NoPages;
 526   UINTN       Size;
 527   CHAR8       *NewPage;
 528   UINTN       Offset;
 529   BOOLEAN     AllFree;
 530   UINTN       Granularity;
 531
 532   ASSERT(Buffer != NULL);
 533   //
 534   // Get the head & tail of the pool entry
 535   //
 536   Head = CR (Buffer, POOL_HEAD, Data, POOL_HEAD_SIGNATURE);
 537   ASSERT(Head != NULL);
 538
 539   if (Head->Signature != POOL_HEAD_SIGNATURE) {
 540     return EFI_INVALID_PARAMETER;
 541   }
 542
 543   Tail = HEAD_TO_TAIL (Head);
 544   ASSERT(Tail != NULL);
 545
 546   //
 547   // Debug
 548   //
 549   ASSERT (Tail->Signature == POOL_TAIL_SIGNATURE);
 550   ASSERT (Head->Size == Tail->Size);
 551   ASSERT_LOCKED (&gMemoryLock);
 552
 553   if (Tail->Signature != POOL_TAIL_SIGNATURE) {
 554     return EFI_INVALID_PARAMETER;
 555   }
 556
 557   if (Head->Size != Tail->Size) {
 558     return EFI_INVALID_PARAMETER;
 559   }
 560
 561   //
 562   // Determine the pool type and account for it
 563   //
 564   Size = Head->Size;
 565   Pool = LookupPoolHead (Head->Type);
 566   if (Pool == NULL) {
 567     return EFI_INVALID_PARAMETER;
 568   }
 569   Pool->Used -= Size;
 570   DEBUG ((DEBUG_POOL, "FreePool: %p (len %lx) %,ld\n", Head->Data, (UINT64)(Head->Size - POOL_OVERHEAD), (UINT64) Pool->Used));
 571
 572   if  (Head->Type == EfiACPIReclaimMemory   ||
 573        Head->Type == EfiACPIMemoryNVS       ||
 574        Head->Type == EfiRuntimeServicesCode ||
 575        Head->Type == EfiRuntimeServicesData) {
 576
 577     Granularity = EFI_ACPI_RUNTIME_PAGE_ALLOCATION_ALIGNMENT;
 578   } else {
 579     Granularity = DEFAULT_PAGE_ALLOCATION;
 580   }
 581
 582   //
 583   // Determine the pool list
 584   //
 585   Index = SIZE_TO_LIST(Size);
 586   DEBUG_CLEAR_MEMORY (Head, Size);
 587
 588   //
 589   // If it's not on the list, it must be pool pages
 590   //
 591   if (Index >= SIZE_TO_LIST (Granularity)) {
 592
 593     //
 594     // Return the memory pages back to free memory
 595     //
 596     NoPages = EFI_SIZE_TO_PAGES(Size) + EFI_SIZE_TO_PAGES (Granularity) - 1;
 597     NoPages &= ~(UINTN)(EFI_SIZE_TO_PAGES (Granularity) - 1);
 598     CoreFreePoolPages ((EFI_PHYSICAL_ADDRESS) (UINTN) Head, NoPages);
 599
 600   } else {
 601
 602     //
 603     // Put the pool entry onto the free pool list
 604     //
 605     Free = (POOL_FREE *) Head;
 606     ASSERT(Free != NULL);
 607     Free->Signature = POOL_FREE_SIGNATURE;
 608     Free->Index     = (UINT32)Index;
 609     InsertHeadList (&Pool->FreeList[Index], &Free->Link);
 610
 611     //
 612     // See if all the pool entries in the same page as Free are freed pool
 613     // entries
 614     //
 615     NewPage = (CHAR8 *)((UINTN)Free & ~(Granularity - 1));
 616     Free = (POOL_FREE *) &NewPage[0];
 617     ASSERT(Free != NULL);
 618
 619     if (Free->Signature == POOL_FREE_SIGNATURE) {
 620
 621       AllFree = TRUE;
 622       Offset = 0;
 623
 624       while ((Offset < Granularity) && (AllFree)) {
 625         Free = (POOL_FREE *) &NewPage[Offset];
 626         ASSERT(Free != NULL);
 627         if (Free->Signature != POOL_FREE_SIGNATURE) {
 628           AllFree = FALSE;
 629         }
 630         Offset += LIST_TO_SIZE(Free->Index);
 631       }
 632
 633       if (AllFree) {
 634
 635         //
 636         // All of the pool entries in the same page as Free are free pool
 637         // entries
 638         // Remove all of these pool entries from the free loop lists.
 639         //
 640         Free = (POOL_FREE *) &NewPage[0];
 641         ASSERT(Free != NULL);
 642         Offset = 0;
 643
 644         while (Offset < Granularity) {
 645           Free = (POOL_FREE *) &NewPage[Offset];
 646           ASSERT(Free != NULL);
 647           RemoveEntryList (&Free->Link);
 648           Offset += LIST_TO_SIZE(Free->Index);
 649         }
 650
 651         //
 652         // Free the page
 653         //
 654         CoreFreePoolPages ((EFI_PHYSICAL_ADDRESS) (UINTN)NewPage, EFI_SIZE_TO_PAGES (Granularity));
 655       }
 656     }
 657   }
 658
 659   //
 660   // If this is an OS specific memory type, then check to see if the last
 661   // portion of that memory type has been freed.  If it has, then free the
 662   // list entry for that memory type
 663   //
 664   if ((INT32)Pool->MemoryType < 0 && Pool->Used == 0) {
 665     RemoveEntryList (&Pool->Link);
 666     CoreFreePoolI (Pool);
 667   }
 668
 669   return EFI_SUCCESS;
 670 }
 671