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