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 header for each memory type.
  73 //
  74 POOL            mPoolHead[EfiMaxMemoryType];
  75
  76 //
  77 // List of pool header to search for the appropriate memory type.
  78 //
  79 LIST_ENTRY      mPoolHeadList = INITIALIZE_LIST_HEAD_VARIABLE (mPoolHeadList);
  80
  81
  82 /**
  83   Called to initialize the pool.
  84
  85 **/
  86 VOID
  87 CoreInitializePool (
  88   VOID
  89   )
  90 {
  91   UINTN  Type;
  92   UINTN  Index;
  93
  94   for (Type=0; Type < EfiMaxMemoryType; Type++) {
  95     mPoolHead[Type].Signature  = 0;
  96     mPoolHead[Type].Used       = 0;
  97     mPoolHead[Type].MemoryType = (EFI_MEMORY_TYPE) Type;
  98     for (Index=0; Index < MAX_POOL_LIST; Index++) {
  99         InitializeListHead (&mPoolHead[Type].FreeList[Index]);
 100     }
 101   }
 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 POOL *
 114 LookupPoolHead (
 115   IN EFI_MEMORY_TYPE  MemoryType
 116   )
 117 {
 118   LIST_ENTRY      *Link;
 119   POOL            *Pool;
 120   UINTN           Index;
 121
 122   if (MemoryType >= 0 && MemoryType < EfiMaxMemoryType) {
 123     return &mPoolHead[MemoryType];
 124   }
 125
 126   if (MemoryType < 0) {
 127
 128     for (Link = mPoolHeadList.ForwardLink; Link != &mPoolHeadList; Link = Link->ForwardLink) {
 129       Pool = CR(Link, POOL, Link, POOL_SIGNATURE);
 130       if (Pool->MemoryType == MemoryType) {
 131         return Pool;
 132       }
 133     }
 134
 135     Pool = CoreAllocatePoolI (EfiBootServicesData, sizeof (POOL));
 136     if (Pool == NULL) {
 137       return NULL;
 138     }
 139
 140     Pool->Signature = POOL_SIGNATURE;
 141     Pool->Used      = 0;
 142     Pool->MemoryType = MemoryType;
 143     for (Index=0; Index < MAX_POOL_LIST; Index++) {
 144       InitializeListHead (&Pool->FreeList[Index]);
 145     }
 146
 147     InsertHeadList (&mPoolHeadList, &Pool->Link);
 148
 149     return Pool;
 150   }
 151
 152   return NULL;
 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       NoPages;
 239
 240   ASSERT_LOCKED (&gMemoryLock);
 241
 242   //
 243   // Adjust the size by the pool header & tail overhead
 244   //
 245
 246   //
 247   // Adjusting the Size to be of proper alignment so that
 248   // we don't get an unaligned access fault later when
 249   // pool_Tail is being initialized
 250   //
 251   Size = ALIGN_VARIABLE (Size);
 252
 253   Size += POOL_OVERHEAD;
 254   Index = SIZE_TO_LIST(Size);
 255   Pool = LookupPoolHead (PoolType);
 256   if (Pool== NULL) {
 257     return NULL;
 258   }
 259   Head = NULL;
 260
 261   //
 262   // If allocation is over max size, just allocate pages for the request
 263   // (slow)
 264   //
 265   if (Index >= MAX_POOL_LIST) {
 266     NoPages = EFI_SIZE_TO_PAGES(Size) + EFI_SIZE_TO_PAGES (DEFAULT_PAGE_ALLOCATION) - 1;
 267     NoPages &= ~(EFI_SIZE_TO_PAGES (DEFAULT_PAGE_ALLOCATION) - 1);
 268     Head = CoreAllocatePoolPages (PoolType, NoPages, DEFAULT_PAGE_ALLOCATION);
 269     goto Done;
 270   }
 271
 272   //
 273   // If there's no free pool in the proper list size, go get some more pages
 274   //
 275   if (IsListEmpty (&Pool->FreeList[Index])) {
 276
 277     //
 278     // Get another page
 279     //
 280     NewPage = CoreAllocatePoolPages(PoolType, EFI_SIZE_TO_PAGES (DEFAULT_PAGE_ALLOCATION), DEFAULT_PAGE_ALLOCATION);
 281     if (NewPage == NULL) {
 282       goto Done;
 283     }
 284
 285     //
 286     // Carve up new page into free pool blocks
 287     //
 288     Offset = 0;
 289     while (Offset < DEFAULT_PAGE_ALLOCATION) {
 290       ASSERT (Index < MAX_POOL_LIST);
 291       FSize = LIST_TO_SIZE(Index);
 292
 293       while (Offset + FSize <= DEFAULT_PAGE_ALLOCATION) {
 294         Free = (POOL_FREE *) &NewPage[Offset];
 295         Free->Signature = POOL_FREE_SIGNATURE;
 296         Free->Index     = (UINT32)Index;
 297         InsertHeadList (&Pool->FreeList[Index], &Free->Link);
 298         Offset += FSize;
 299       }
 300
 301       Index -= 1;
 302     }
 303
 304     ASSERT (Offset == DEFAULT_PAGE_ALLOCATION);
 305     Index = SIZE_TO_LIST(Size);
 306   }
 307
 308   //
 309   // Remove entry from free pool list
 310   //
 311   Free = CR (Pool->FreeList[Index].ForwardLink, POOL_FREE, Link, POOL_FREE_SIGNATURE);
 312   RemoveEntryList (&Free->Link);
 313
 314   Head = (POOL_HEAD *) Free;
 315
 316 Done:
 317   Buffer = NULL;
 318
 319   if (Head != NULL) {
 320
 321     //
 322     // If we have a pool buffer, fill in the header & tail info
 323     //
 324     Head->Signature = POOL_HEAD_SIGNATURE;
 325     Head->Size      = (UINT32) Size;
 326     Head->Type      = (EFI_MEMORY_TYPE) PoolType;
 327     Tail            = HEAD_TO_TAIL (Head);
 328     Tail->Signature = POOL_TAIL_SIGNATURE;
 329     Tail->Size      = (UINT32) Size;
 330     Buffer          = Head->Data;
 331     DEBUG_CLEAR_MEMORY (Buffer, Size - POOL_OVERHEAD);
 332
 333     DEBUG ((
 334       DEBUG_POOL,
 335       "AllocatePoolI: Type %x, Addr %p (len %lx) %,ld\n", PoolType,
 336       Buffer,
 337       (UINT64)(Size - POOL_OVERHEAD),
 338       (UINT64) Pool->Used
 339       ));
 340
 341     //
 342     // Account the allocation
 343     //
 344     Pool->Used += Size;
 345
 346   } else {
 347     DEBUG ((DEBUG_ERROR | DEBUG_POOL, "AllocatePool: failed to allocate %ld bytes\n", (UINT64) Size));
 348   }
 349
 350   return Buffer;
 351 }
 352
 353
 354
 355 /**
 356   Frees pool.
 357
 358   @param  Buffer                 The allocated pool entry to free
 359
 360   @retval EFI_INVALID_PARAMETER  Buffer is not a valid value.
 361   @retval EFI_SUCCESS            Pool successfully freed.
 362
 363 **/
 364 EFI_STATUS
 365 EFIAPI
 366 CoreFreePool (
 367   IN VOID        *Buffer
 368   )
 369 {
 370   EFI_STATUS Status;
 371
 372   if (Buffer == NULL) {
 373     return EFI_INVALID_PARAMETER;
 374   }
 375
 376   CoreAcquireMemoryLock ();
 377   Status = CoreFreePoolI (Buffer);
 378   CoreReleaseMemoryLock ();
 379   return Status;
 380 }
 381
 382
 383
 384 /**
 385   Internal function to free a pool entry.
 386   Caller must have the memory lock held
 387
 388   @param  Buffer                 The allocated pool entry to free
 389
 390   @retval EFI_INVALID_PARAMETER  Buffer not valid
 391   @retval EFI_SUCCESS            Buffer successfully freed.
 392
 393 **/
 394 EFI_STATUS
 395 CoreFreePoolI (
 396   IN VOID       *Buffer
 397   )
 398 {
 399   POOL        *Pool;
 400   POOL_HEAD   *Head;
 401   POOL_TAIL   *Tail;
 402   POOL_FREE   *Free;
 403   UINTN       Index;
 404   UINTN       NoPages;
 405   UINTN       Size;
 406   CHAR8       *NewPage;
 407   UINTN       FSize;
 408   UINTN       Offset;
 409   BOOLEAN     AllFree;
 410
 411   ASSERT(Buffer != NULL);
 412   //
 413   // Get the head & tail of the pool entry
 414   //
 415   Head = CR (Buffer, POOL_HEAD, Data, POOL_HEAD_SIGNATURE);
 416   ASSERT(Head != NULL);
 417
 418   if (Head->Signature != POOL_HEAD_SIGNATURE) {
 419     return EFI_INVALID_PARAMETER;
 420   }
 421
 422   Tail = HEAD_TO_TAIL (Head);
 423   ASSERT(Tail != NULL);
 424
 425   //
 426   // Debug
 427   //
 428   ASSERT (Tail->Signature == POOL_TAIL_SIGNATURE);
 429   ASSERT (Head->Size == Tail->Size);
 430   ASSERT_LOCKED (&gMemoryLock);
 431
 432   if (Tail->Signature != POOL_TAIL_SIGNATURE) {
 433     return EFI_INVALID_PARAMETER;
 434   }
 435
 436   if (Head->Size != Tail->Size) {
 437     return EFI_INVALID_PARAMETER;
 438   }
 439
 440   //
 441   // Determine the pool type and account for it
 442   //
 443   Size = Head->Size;
 444   Pool = LookupPoolHead (Head->Type);
 445   if (Pool == NULL) {
 446     return EFI_INVALID_PARAMETER;
 447   }
 448   Pool->Used -= Size;
 449   DEBUG ((DEBUG_POOL, "FreePool: %p (len %lx) %,ld\n", Head->Data, (UINT64)(Head->Size - POOL_OVERHEAD), (UINT64) Pool->Used));
 450
 451   //
 452   // Determine the pool list
 453   //
 454   Index = SIZE_TO_LIST(Size);
 455   DEBUG_CLEAR_MEMORY (Head, Size);
 456
 457   //
 458   // If it's not on the list, it must be pool pages
 459   //
 460   if (Index >= MAX_POOL_LIST) {
 461
 462     //
 463     // Return the memory pages back to free memory
 464     //
 465     NoPages = EFI_SIZE_TO_PAGES(Size) + EFI_SIZE_TO_PAGES (DEFAULT_PAGE_ALLOCATION) - 1;
 466     NoPages &= ~(EFI_SIZE_TO_PAGES (DEFAULT_PAGE_ALLOCATION) - 1);
 467     CoreFreePoolPages ((EFI_PHYSICAL_ADDRESS) (UINTN) Head, NoPages);
 468
 469   } else {
 470
 471     //
 472     // Put the pool entry onto the free pool list
 473     //
 474     Free = (POOL_FREE *) Head;
 475     ASSERT(Free != NULL);
 476     Free->Signature = POOL_FREE_SIGNATURE;
 477     Free->Index     = (UINT32)Index;
 478     InsertHeadList (&Pool->FreeList[Index], &Free->Link);
 479
 480     //
 481     // See if all the pool entries in the same page as Free are freed pool
 482     // entries
 483     //
 484     NewPage = (CHAR8 *)((UINTN)Free & ~((DEFAULT_PAGE_ALLOCATION) -1));
 485     Free = (POOL_FREE *) &NewPage[0];
 486     ASSERT(Free != NULL);
 487
 488     if (Free->Signature == POOL_FREE_SIGNATURE) {
 489
 490       Index = Free->Index;
 491
 492       AllFree = TRUE;
 493       Offset = 0;
 494
 495       while ((Offset < DEFAULT_PAGE_ALLOCATION) && (AllFree)) {
 496         FSize = LIST_TO_SIZE(Index);
 497         while (Offset + FSize <= DEFAULT_PAGE_ALLOCATION) {
 498           Free = (POOL_FREE *) &NewPage[Offset];
 499           ASSERT(Free != NULL);
 500           if (Free->Signature != POOL_FREE_SIGNATURE) {
 501             AllFree = FALSE;
 502           }
 503           Offset += FSize;
 504         }
 505         Index -= 1;
 506       }
 507
 508       if (AllFree) {
 509
 510         //
 511         // All of the pool entries in the same page as Free are free pool
 512         // entries
 513         // Remove all of these pool entries from the free loop lists.
 514         //
 515         Free = (POOL_FREE *) &NewPage[0];
 516         ASSERT(Free != NULL);
 517         Index = Free->Index;
 518         Offset = 0;
 519
 520         while (Offset < DEFAULT_PAGE_ALLOCATION) {
 521           FSize = LIST_TO_SIZE(Index);
 522           while (Offset + FSize <= DEFAULT_PAGE_ALLOCATION) {
 523             Free = (POOL_FREE *) &NewPage[Offset];
 524             ASSERT(Free != NULL);
 525             RemoveEntryList (&Free->Link);
 526             Offset += FSize;
 527           }
 528           Index -= 1;
 529         }
 530
 531         //
 532         // Free the page
 533         //
 534         CoreFreePoolPages ((EFI_PHYSICAL_ADDRESS) (UINTN)NewPage, EFI_SIZE_TO_PAGES (DEFAULT_PAGE_ALLOCATION));
 535       }
 536     }
 537   }
 538
 539   //
 540   // If this is an OS specific memory type, then check to see if the last
 541   // portion of that memory type has been freed.  If it has, then free the
 542   // list entry for that memory type
 543   //
 544   if (Pool->MemoryType < 0 && Pool->Used == 0) {
 545     RemoveEntryList (&Pool->Link);
 546     CoreFreePoolI (Pool);
 547   }
 548
 549   return EFI_SUCCESS;
 550 }