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