MdeModulePkg/Core/Dxe/Mem/Pool.c

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