MdeModulePkg/Core/Dxe/Mem/pool.c

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