MdeModulePkg/Core/Dxe/Mem/Pool.c

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