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
  17 #define POOL_FREE_SIGNATURE   EFI_SIGNATURE_32('p','f','r','0')
  18 typedef struct {
  19   UINT32          Signature;
  20   UINT32          Index;
  21   LIST_ENTRY      Link;
  22 } POOL_FREE;
  23
  24
  25 #define POOL_HEAD_SIGNATURE   EFI_SIGNATURE_32('p','h','d','0')
  26 typedef struct {
  27   UINT32          Signature;
  28   UINT32          Size;
  29   EFI_MEMORY_TYPE Type;
  30   UINTN           Reserved;
  31   CHAR8           Data[1];
  32 } POOL_HEAD;
  33
  34 #define SIZE_OF_POOL_HEAD EFI_FIELD_OFFSET(POOL_HEAD,Data)
  35
  36 #define POOL_TAIL_SIGNATURE   EFI_SIGNATURE_32('p','t','a','l')
  37 typedef struct {
  38   UINT32      Signature;
  39   UINT32      Size;
  40 } POOL_TAIL;
  41
  42
  43 #define POOL_SHIFT  7
  44
  45 #define POOL_OVERHEAD (SIZE_OF_POOL_HEAD + sizeof(POOL_TAIL))
  46
  47 #define HEAD_TO_TAIL(a)   \
  48   ((POOL_TAIL *) (((CHAR8 *) (a)) + (a)->Size - sizeof(POOL_TAIL)));
  49
  50
  51 #define SIZE_TO_LIST(a)   ((a) >> POOL_SHIFT)
  52 #define LIST_TO_SIZE(a)   ((a+1) << POOL_SHIFT)
  53
  54 #define MAX_POOL_LIST       SIZE_TO_LIST(DEFAULT_PAGE_ALLOCATION)
  55
  56 #define MAX_POOL_SIZE     (MAX_ADDRESS - POOL_OVERHEAD)
  57
  58 //
  59 // Globals
  60 //
  61
  62 #define POOL_SIGNATURE  EFI_SIGNATURE_32('p','l','s','t')
  63 typedef struct {
  64     INTN             Signature;
  65     UINTN            Used;
  66     EFI_MEMORY_TYPE  MemoryType;
  67     LIST_ENTRY       FreeList[MAX_POOL_LIST];
  68     LIST_ENTRY       Link;
  69 } POOL;
  70
  71
  72 POOL            PoolHead[EfiMaxMemoryType];
  73 LIST_ENTRY      PoolHeadList;
  74
  75 //
  76 //
  77 //
  78
  79
  80 /**
  81   Called to initialize the pool.
  82
  83 **/
  84 VOID
  85 CoreInitializePool (
  86   VOID
  87   )
  88 {
  89   UINTN  Type;
  90   UINTN  Index;
  91
  92   for (Type=0; Type < EfiMaxMemoryType; Type++) {
  93     PoolHead[Type].Signature  = 0;
  94     PoolHead[Type].Used       = 0;
  95     PoolHead[Type].MemoryType = (EFI_MEMORY_TYPE) Type;
  96     for (Index=0; Index < MAX_POOL_LIST; Index++) {
  97         InitializeListHead (&PoolHead[Type].FreeList[Index]);
  98     }
  99   }
 100   InitializeListHead (&PoolHeadList);
 101 }
 102
 103
 104 /**
 105   Look up pool head for specified memory type.
 106
 107   @param  MemoryType             Memory type of which pool head is looked for
 108
 109   @return Pointer of Corresponding pool head.
 110
 111 **/
 112 POOL *
 113 LookupPoolHead (
 114   IN EFI_MEMORY_TYPE  MemoryType
 115   )
 116 {
 117   LIST_ENTRY      *Link;
 118   POOL            *Pool;
 119   UINTN           Index;
 120
 121   if (MemoryType >= 0 && MemoryType < EfiMaxMemoryType) {
 122     return &PoolHead[MemoryType];
 123   }
 124
 125   if (MemoryType < 0) {
 126
 127     for (Link = PoolHeadList.ForwardLink; Link != &PoolHeadList; Link = Link->ForwardLink) {
 128       Pool = CR(Link, POOL, Link, POOL_SIGNATURE);
 129       if (Pool->MemoryType == MemoryType) {
 130         return Pool;
 131       }
 132     }
 133
 134     Pool = CoreAllocatePoolI (EfiBootServicesData, sizeof (POOL));
 135     if (Pool == NULL) {
 136       return NULL;
 137     }
 138
 139     Pool->Signature = POOL_SIGNATURE;
 140     Pool->Used      = 0;
 141     Pool->MemoryType = MemoryType;
 142     for (Index=0; Index < MAX_POOL_LIST; Index++) {
 143       InitializeListHead (&Pool->FreeList[Index]);
 144     }
 145
 146     InsertHeadList (&PoolHeadList, &Pool->Link);
 147
 148     return Pool;
 149   }
 150
 151   return NULL;
 152 }
 153
 154
 155
 156
 157 /**
 158   Allocate pool of a particular type.
 159
 160   @param  PoolType               Type of pool to allocate
 161   @param  Size                   The amount of pool to allocate
 162   @param  Buffer                 The address to return a pointer to the allocated
 163                                  pool
 164
 165   @retval EFI_INVALID_PARAMETER  PoolType not valid
 166   @retval EFI_OUT_OF_RESOURCES   Size exceeds max pool size or allocation failed.
 167   @retval EFI_SUCCESS            Pool successfully allocated.
 168
 169 **/
 170 EFI_STATUS
 171 EFIAPI
 172 CoreAllocatePool (
 173   IN EFI_MEMORY_TYPE  PoolType,
 174   IN UINTN            Size,
 175   OUT VOID            **Buffer
 176   )
 177 {
 178   EFI_STATUS    Status;
 179
 180   //
 181   // If it's not a valid type, fail it
 182   //
 183   if ((PoolType >= EfiMaxMemoryType && PoolType <= 0x7fffffff) ||
 184        PoolType == EfiConventionalMemory) {
 185     return EFI_INVALID_PARAMETER;
 186   }
 187
 188   *Buffer = NULL;
 189
 190   //
 191   // If size is too large, fail it
 192   // Base on the EFI spec, return status of EFI_OUT_OF_RESOURCES
 193   //
 194   if (Size > MAX_POOL_SIZE) {
 195     return EFI_OUT_OF_RESOURCES;
 196   }
 197
 198   //
 199   // Acquire the memory lock and make the allocation
 200   //
 201   Status = CoreAcquireLockOrFail (&gMemoryLock);
 202   if (EFI_ERROR (Status)) {
 203     return EFI_OUT_OF_RESOURCES;
 204   }
 205
 206   *Buffer = CoreAllocatePoolI (PoolType, Size);
 207   CoreReleaseMemoryLock ();
 208   return (*Buffer != NULL) ? EFI_SUCCESS : EFI_OUT_OF_RESOURCES;
 209 }
 210
 211
 212
 213 /**
 214   Internal function to allocate pool of a particular type.
 215   Caller must have the memory lock held
 216
 217   @param  PoolType               Type of pool to allocate
 218   @param  Size                   The amount of pool to allocate
 219
 220   @return The allocate pool, or NULL
 221
 222 **/
 223 VOID *
 224 CoreAllocatePoolI (
 225   IN EFI_MEMORY_TYPE  PoolType,
 226   IN UINTN            Size
 227   )
 228 {
 229   POOL        *Pool;
 230   POOL_FREE   *Free;
 231   POOL_HEAD   *Head;
 232   POOL_TAIL   *Tail;
 233   CHAR8       *NewPage;
 234   VOID        *Buffer;
 235   UINTN       Index;
 236   UINTN       FSize;
 237   UINTN       Offset;
 238   UINTN       Adjustment;
 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   ALIGN_VARIABLE (Size, Adjustment);
 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 %x (len %x) %,d\n",
 337        PoolType,
 338        Buffer,
 339        Size - POOL_OVERHEAD,
 340       Pool->Used)
 341       );
 342
 343     //
 344     // Account the allocation
 345     //
 346     Pool->Used += Size;
 347
 348   } else {
 349     DEBUG ((DEBUG_ERROR | DEBUG_POOL, "AllocatePool: failed to allocate %d bytes\n", Size));
 350   }
 351
 352   return Buffer;
 353 }
 354
 355
 356
 357
 358 /**
 359   Frees pool.
 360
 361   @param  Buffer                 The allocated pool entry to free
 362
 363   @retval EFI_INVALID_PARAMETER  Buffer is not a valid value.
 364   @retval EFI_SUCCESS            Pool successfully freed.
 365
 366 **/
 367 EFI_STATUS
 368 EFIAPI
 369 CoreFreePool (
 370   IN VOID        *Buffer
 371   )
 372 {
 373   EFI_STATUS Status;
 374
 375   if (NULL == Buffer) {
 376     return EFI_INVALID_PARAMETER;
 377   }
 378
 379   CoreAcquireMemoryLock ();
 380   Status = CoreFreePoolI (Buffer);
 381   CoreReleaseMemoryLock ();
 382   return Status;
 383 }
 384
 385
 386
 387 /**
 388   Internal function to free a pool entry.
 389   Caller must have the memory lock held
 390
 391   @param  Buffer                 The allocated pool entry to free
 392
 393   @retval EFI_INVALID_PARAMETER  Buffer not valid
 394   @retval EFI_SUCCESS            Buffer successfully freed.
 395
 396 **/
 397 EFI_STATUS
 398 CoreFreePoolI (
 399   IN VOID       *Buffer
 400   )
 401 {
 402   POOL        *Pool;
 403   POOL_HEAD   *Head;
 404   POOL_TAIL   *Tail;
 405   POOL_FREE   *Free;
 406   UINTN       Index;
 407   UINTN       NoPages;
 408   UINTN       Size;
 409   CHAR8       *NewPage;
 410   UINTN       FSize;
 411   UINTN       Offset;
 412   BOOLEAN     AllFree;
 413
 414   ASSERT(NULL != Buffer);
 415   //
 416   // Get the head & tail of the pool entry
 417   //
 418   Head = CR (Buffer, POOL_HEAD, Data, POOL_HEAD_SIGNATURE);
 419   ASSERT(NULL != Head);
 420
 421   if (Head->Signature != POOL_HEAD_SIGNATURE) {
 422     return EFI_INVALID_PARAMETER;
 423   }
 424
 425   Tail = HEAD_TO_TAIL (Head);
 426   ASSERT(NULL != Tail);
 427
 428   //
 429   // Debug
 430   //
 431   ASSERT (Tail->Signature == POOL_TAIL_SIGNATURE);
 432   ASSERT (Head->Size == Tail->Size);
 433   ASSERT_LOCKED (&gMemoryLock);
 434
 435   if (Tail->Signature != POOL_TAIL_SIGNATURE) {
 436     return EFI_INVALID_PARAMETER;
 437   }
 438
 439   if (Head->Size != Tail->Size) {
 440     return EFI_INVALID_PARAMETER;
 441   }
 442
 443   //
 444   // Determine the pool type and account for it
 445   //
 446   Size = Head->Size;
 447   Pool = LookupPoolHead (Head->Type);
 448   if (Pool == NULL) {
 449     return EFI_INVALID_PARAMETER;
 450   }
 451   Pool->Used -= Size;
 452   DEBUG ((DEBUG_POOL, "FreePool: %x (len %x) %,d\n", Head->Data, Head->Size - POOL_OVERHEAD, Pool->Used));
 453
 454   //
 455   // Determine the pool list
 456   //
 457   Index = SIZE_TO_LIST(Size);
 458   DEBUG_CLEAR_MEMORY (Head, Size);
 459
 460   //
 461   // If it's not on the list, it must be pool pages
 462   //
 463   if (Index >= MAX_POOL_LIST) {
 464
 465     //
 466     // Return the memory pages back to free memory
 467     //
 468     NoPages = EFI_SIZE_TO_PAGES(Size) + EFI_SIZE_TO_PAGES (DEFAULT_PAGE_ALLOCATION) - 1;
 469     NoPages &= ~(EFI_SIZE_TO_PAGES (DEFAULT_PAGE_ALLOCATION) - 1);
 470     CoreFreePoolPages ((EFI_PHYSICAL_ADDRESS) (UINTN) Head, NoPages);
 471
 472   } else {
 473
 474     //
 475     // Put the pool entry onto the free pool list
 476     //
 477     Free = (POOL_FREE *) Head;
 478     ASSERT(NULL != Free);
 479     Free->Signature = POOL_FREE_SIGNATURE;
 480     Free->Index     = (UINT32)Index;
 481     InsertHeadList (&Pool->FreeList[Index], &Free->Link);
 482
 483     //
 484     // See if all the pool entries in the same page as Free are freed pool
 485     // entries
 486     //
 487     NewPage = (CHAR8 *)((UINTN)Free & ~((DEFAULT_PAGE_ALLOCATION) -1));
 488     Free = (POOL_FREE *) &NewPage[0];
 489     ASSERT(NULL != Free);
 490
 491     if (Free->Signature == POOL_FREE_SIGNATURE) {
 492
 493       Index = Free->Index;
 494
 495       AllFree = TRUE;
 496       Offset = 0;
 497
 498       while ((Offset < DEFAULT_PAGE_ALLOCATION) && (AllFree)) {
 499         FSize = LIST_TO_SIZE(Index);
 500         while (Offset + FSize <= DEFAULT_PAGE_ALLOCATION) {
 501           Free = (POOL_FREE *) &NewPage[Offset];
 502           ASSERT(NULL != Free);
 503           if (Free->Signature != POOL_FREE_SIGNATURE) {
 504             AllFree = FALSE;
 505           }
 506           Offset += FSize;
 507         }
 508         Index -= 1;
 509       }
 510
 511       if (AllFree) {
 512
 513         //
 514         // All of the pool entries in the same page as Free are free pool
 515         // entries
 516         // Remove all of these pool entries from the free loop lists.
 517         //
 518         Free = (POOL_FREE *) &NewPage[0];
 519         ASSERT(NULL != Free);
 520         Index = Free->Index;
 521         Offset = 0;
 522
 523         while (Offset < DEFAULT_PAGE_ALLOCATION) {
 524           FSize = LIST_TO_SIZE(Index);
 525           while (Offset + FSize <= DEFAULT_PAGE_ALLOCATION) {
 526             Free = (POOL_FREE *) &NewPage[Offset];
 527             ASSERT(NULL != Free);
 528             RemoveEntryList (&Free->Link);
 529             Offset += FSize;
 530           }
 531           Index -= 1;
 532         }
 533
 534         //
 535         // Free the page
 536         //
 537         CoreFreePoolPages ((EFI_PHYSICAL_ADDRESS) (UINTN)NewPage, EFI_SIZE_TO_PAGES (DEFAULT_PAGE_ALLOCATION));
 538       }
 539     }
 540   }
 541
 542   //
 543   // If this is an OS specific memory type, then check to see if the last
 544   // portion of that memory type has been freed.  If it has, then free the
 545   // list entry for that memory type
 546   //
 547   if (Pool->MemoryType < 0 && Pool->Used == 0) {
 548     RemoveEntryList (&Pool->Link);
 549     CoreFreePoolI (Pool);
 550   }
 551
 552   return EFI_SUCCESS;
 553 }