MdeModulePkg/Core/Dxe/Mem/Pool.c

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