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