EdkModulePkg/Core/Dxe/Mem/pool.c

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