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
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.
27 IN USB2_HC_DEV
*HcDev
,
28 OUT MEMORY_MANAGE_HEADER
**MemoryHeader
,
29 IN UINTN MemoryBlockSizeInPages
35 Use PciIo->AllocateBuffer to allocate common buffer for the memory block,
36 and use PciIo->Map to map the common buffer for Bus Master Read/Write.
41 MemoryHeader - MEMORY_MANAGE_HEADER to output
42 MemoryBlockSizeInPages - MemoryBlockSizeInPages
47 EFI_OUT_OF_RESOURCES Fail for no resources
48 EFI_UNSUPPORTED Unsupported currently
54 EFI_PHYSICAL_ADDRESS MappedAddress
;
55 UINTN MemoryBlockSizeInBytes
;
59 // Allocate memory for MemoryHeader
61 *MemoryHeader
= AllocateZeroPool (sizeof (MEMORY_MANAGE_HEADER
));
62 if (*MemoryHeader
== NULL
) {
63 return EFI_OUT_OF_RESOURCES
;
66 (*MemoryHeader
)->Next
= NULL
;
69 // set Memory block size
71 (*MemoryHeader
)->MemoryBlockSizeInBytes
= EFI_PAGES_TO_SIZE (MemoryBlockSizeInPages
);
74 // each bit in Bit Array will manage 32 bytes memory in memory block
76 (*MemoryHeader
)->BitArraySizeInBytes
= ((*MemoryHeader
)->MemoryBlockSizeInBytes
/ 32) / 8;
79 // Allocate memory for BitArray
81 (*MemoryHeader
)->BitArrayPtr
= AllocateZeroPool ((*MemoryHeader
)->BitArraySizeInBytes
);
82 if ((*MemoryHeader
)->BitArrayPtr
== NULL
) {
83 gBS
->FreePool (*MemoryHeader
);
84 return EFI_OUT_OF_RESOURCES
;
88 // Memory Block uses MemoryBlockSizeInPages pages,
89 // and it is allocated as common buffer use.
91 Status
= HcDev
->PciIo
->AllocateBuffer (
95 MemoryBlockSizeInPages
,
99 if (EFI_ERROR (Status
)) {
100 gBS
->FreePool ((*MemoryHeader
)->BitArrayPtr
);
101 gBS
->FreePool (*MemoryHeader
);
102 return EFI_OUT_OF_RESOURCES
;
105 MemoryBlockSizeInBytes
= EFI_PAGES_TO_SIZE (MemoryBlockSizeInPages
);
106 Status
= HcDev
->PciIo
->Map (
108 EfiPciIoOperationBusMasterCommonBuffer
,
110 &MemoryBlockSizeInBytes
,
115 // If returned Mapped size is less than the size
116 // we request,do not support.
118 if (EFI_ERROR (Status
) || (MemoryBlockSizeInBytes
!= EFI_PAGES_TO_SIZE (MemoryBlockSizeInPages
))) {
119 HcDev
->PciIo
->FreeBuffer (HcDev
->PciIo
, MemoryBlockSizeInPages
, CommonBuffer
);
120 gBS
->FreePool ((*MemoryHeader
)->BitArrayPtr
);
121 gBS
->FreePool (*MemoryHeader
);
122 return EFI_UNSUPPORTED
;
126 // Data structure involved by host controller
127 // should be restricted into the same 4G
129 if (HcDev
->Is64BitCapable
!= 0) {
130 if (HcDev
->High32BitAddr
!= GET_32B_TO_63B (MappedAddress
)) {
131 HcDev
->PciIo
->Unmap (HcDev
->PciIo
, Mapping
);
132 HcDev
->PciIo
->FreeBuffer (HcDev
->PciIo
, MemoryBlockSizeInPages
, CommonBuffer
);
133 gBS
->FreePool ((*MemoryHeader
)->BitArrayPtr
);
134 gBS
->FreePool (*MemoryHeader
);
135 return EFI_UNSUPPORTED
;
140 // Set Memory block initial address
142 (*MemoryHeader
)->MemoryBlockPtr
= (UINT8
*) ((UINTN
) MappedAddress
);
143 (*MemoryHeader
)->Mapping
= Mapping
;
146 (*MemoryHeader
)->MemoryBlockPtr
,
147 EFI_PAGES_TO_SIZE (MemoryBlockSizeInPages
)
155 IN USB2_HC_DEV
*HcDev
,
156 IN MEMORY_MANAGE_HEADER
*MemoryHeader
167 MemoryHeader - MemoryHeader to be freed
172 EFI_INVALID_PARAMETER Parameter is error
176 if ((MemoryHeader
== NULL
) || (HcDev
== NULL
)) {
177 return EFI_INVALID_PARAMETER
;
180 // unmap the common buffer used by the memory block
182 HcDev
->PciIo
->Unmap (HcDev
->PciIo
, MemoryHeader
->Mapping
);
185 // free common buffer
187 HcDev
->PciIo
->FreeBuffer (
189 EFI_SIZE_TO_PAGES (MemoryHeader
->MemoryBlockSizeInBytes
),
190 MemoryHeader
->MemoryBlockPtr
195 gBS
->FreePool (MemoryHeader
->BitArrayPtr
);
197 // free memory header
199 gBS
->FreePool (MemoryHeader
);
206 IN USB2_HC_DEV
*HcDev
,
219 Pool - Place to store pointer to the memory buffer
220 AllocSize - Alloc Size
225 EFI_DEVICE_ERROR Fail
229 MEMORY_MANAGE_HEADER
*MemoryHeader
;
230 MEMORY_MANAGE_HEADER
*TempHeaderPtr
;
231 MEMORY_MANAGE_HEADER
*NewMemoryHeader
;
233 UINTN MemoryBlockSizeInPages
;
239 MemoryHeader
= HcDev
->MemoryHeader
;
240 ASSERT (MemoryHeader
!= NULL
);
242 OldTpl
= gBS
->RaiseTPL (EFI_TPL_NOTIFY
+ 1);
245 // allocate unit is 32 bytes (align on 32 byte)
247 if (AllocSize
& 0x1F) {
248 RealAllocSize
= (AllocSize
/ 32 + 1) * 32;
250 RealAllocSize
= AllocSize
;
254 // There may be linked MemoryHeaders.
255 // To allocate a free pool in Memory blocks,
256 // must search in the MemoryHeader link list
257 // until enough free pool is found.
259 Status
= EFI_NOT_FOUND
;
260 for (TempHeaderPtr
= MemoryHeader
; TempHeaderPtr
!= NULL
; TempHeaderPtr
= TempHeaderPtr
->Next
) {
262 Status
= AllocMemInMemoryBlock (
267 if (!EFI_ERROR (Status
)) {
268 ZeroMem (*Pool
, AllocSize
);
269 gBS
->RestoreTPL (OldTpl
);
274 gBS
->RestoreTPL (OldTpl
);
277 // There is no enough memory,
278 // Create a new Memory Block
282 // if pool size is larger than NORMAL_MEMORY_BLOCK_UNIT_IN_PAGES,
283 // just allocate a large enough memory block.
285 if (RealAllocSize
> EFI_PAGES_TO_SIZE (NORMAL_MEMORY_BLOCK_UNIT_IN_PAGES
)) {
286 MemoryBlockSizeInPages
= EFI_SIZE_TO_PAGES (RealAllocSize
) + 1;
288 MemoryBlockSizeInPages
= NORMAL_MEMORY_BLOCK_UNIT_IN_PAGES
;
291 Status
= CreateMemoryBlock (HcDev
, &NewMemoryHeader
, MemoryBlockSizeInPages
);
292 if (EFI_ERROR (Status
)) {
296 OldTpl
= gBS
->RaiseTPL (EFI_TPL_NOTIFY
+ 1);
299 // Link the new Memory Block to the Memory Header list
301 InsertMemoryHeaderToList (MemoryHeader
, NewMemoryHeader
);
303 Status
= AllocMemInMemoryBlock (
308 if (!EFI_ERROR (Status
)) {
309 ZeroMem (*Pool
, AllocSize
);
312 gBS
->RestoreTPL (OldTpl
);
318 IN USB2_HC_DEV
*HcDev
,
332 AllocSize - Pool size
340 MEMORY_MANAGE_HEADER
*MemoryHeader
;
341 MEMORY_MANAGE_HEADER
*TempHeaderPtr
;
350 OldTpl
= gBS
->RaiseTPL (EFI_TPL_NOTIFY
+ 1);
352 MemoryHeader
= HcDev
->MemoryHeader
;
355 // allocate unit is 32 byte (align on 32 byte)
357 if (AllocSize
& 0x1F) {
358 RealAllocSize
= (AllocSize
/ 32 + 1) * 32;
360 RealAllocSize
= AllocSize
;
364 // scan the memory header linked list for
365 // the asigned memory to free.
367 for (TempHeaderPtr
= MemoryHeader
; TempHeaderPtr
!= NULL
; TempHeaderPtr
= TempHeaderPtr
->Next
) {
369 if ((Pool
>= TempHeaderPtr
->MemoryBlockPtr
) &&
370 ((Pool
+ RealAllocSize
) <= (TempHeaderPtr
->MemoryBlockPtr
+ TempHeaderPtr
->MemoryBlockSizeInBytes
))
373 // Pool is in the Memory Block area,
374 // find the start byte and bit in the bit array
376 StartBytePos
= ((Pool
- TempHeaderPtr
->MemoryBlockPtr
) / 32) / 8;
377 StartBitPos
= (UINT8
) (((Pool
- TempHeaderPtr
->MemoryBlockPtr
) / 32) & 0x7);
380 // reset associated bits in bit arry
382 for (Index
= StartBytePos
, Index2
= StartBitPos
, Count
= 0; Count
< (RealAllocSize
/ 32); Count
++) {
383 TempHeaderPtr
->BitArrayPtr
[Index
] ^= (UINT8
) (bit (Index2
));
398 // Release emptied memory blocks (only if the memory block is not
399 // the first one in the memory header list
401 for (TempHeaderPtr
= MemoryHeader
->Next
; TempHeaderPtr
!= NULL
;) {
403 ASSERT (MemoryHeader
->Next
!= NULL
);
405 if (IsMemoryBlockEmptied (TempHeaderPtr
)) {
407 DelinkMemoryBlock (MemoryHeader
, TempHeaderPtr
);
409 // when the TempHeaderPtr is freed in FreeMemoryHeader(),
410 // the TempHeaderPtr is pointing to nonsense content.
412 gBS
->RestoreTPL (OldTpl
);
413 FreeMemoryHeader (HcDev
, TempHeaderPtr
);
414 OldTpl
= gBS
->RaiseTPL (EFI_TPL_NOTIFY
+ 1);
416 // reset the TempHeaderPtr, continue search for
417 // another empty memory block.
419 TempHeaderPtr
= MemoryHeader
->Next
;
423 TempHeaderPtr
= TempHeaderPtr
->Next
;
426 gBS
->RestoreTPL (OldTpl
);
430 InsertMemoryHeaderToList (
431 IN MEMORY_MANAGE_HEADER
*MemoryHeader
,
432 IN MEMORY_MANAGE_HEADER
*NewMemoryHeader
438 Insert Memory Header To List
442 MemoryHeader - MEMORY_MANAGE_HEADER
443 NewMemoryHeader - MEMORY_MANAGE_HEADER
451 MEMORY_MANAGE_HEADER
*TempHeaderPtr
;
453 for (TempHeaderPtr
= MemoryHeader
; TempHeaderPtr
!= NULL
; TempHeaderPtr
= TempHeaderPtr
->Next
) {
454 if (TempHeaderPtr
->Next
== NULL
) {
455 TempHeaderPtr
->Next
= NewMemoryHeader
;
462 AllocMemInMemoryBlock (
463 IN MEMORY_MANAGE_HEADER
*MemoryHeader
,
465 IN UINTN NumberOfMemoryUnit
471 Alloc Memory In MemoryBlock
475 MemoryHeader - MEMORY_MANAGE_HEADER
476 Pool - Place to store pointer to memory
477 NumberOfMemoryUnit - Number Of Memory Unit
482 EFI_NOT_FOUND Can't find the free memory
497 ByteValue
= MemoryHeader
->BitArrayPtr
[0];
501 for (TempBytePos
= 0; TempBytePos
< MemoryHeader
->BitArraySizeInBytes
;) {
504 // Pop out BitValue from a byte in TempBytePos.
506 BitValue
= (UINT8
) (ByteValue
& 0x1);
509 // right shift the byte
515 // Found a free bit, the NumberOfZeros only record the number
516 // of those consecutive zeros
520 // Found enough consecutive free space, break the loop
522 if (NumberOfZeros
>= NumberOfMemoryUnit
) {
527 // Encountering a '1', meant the bit is ocupied.
529 if (NumberOfZeros
>= NumberOfMemoryUnit
) {
531 // Found enough consecutive free space,break the loop
536 // the NumberOfZeros only record the number of those consecutive zeros,
537 // so reset the NumberOfZeros to 0 when encountering '1' before finding
538 // enough consecutive '0's
542 // reset the (FoundBytePos,FoundBitPos) to the position of '1'
544 FoundBytePos
= TempBytePos
;
550 // step forward a bit
555 // step forward a byte, getting the byte value,
556 // and reset the bit pos.
559 ByteValue
= MemoryHeader
->BitArrayPtr
[TempBytePos
];
564 if (NumberOfZeros
< NumberOfMemoryUnit
) {
565 return EFI_NOT_FOUND
;
569 // Found enough free space.
573 // The values recorded in (FoundBytePos,FoundBitPos) have two conditions:
574 // 1)(FoundBytePos,FoundBitPos) record the position
575 // of the last '1' before the consecutive '0's, it must
576 // be adjusted to the start position of the consecutive '0's.
577 // 2)the start address of the consecutive '0's is just the start of
578 // the bitarray. so no need to adjust the values of
579 // (FoundBytePos,FoundBitPos).
581 if ((MemoryHeader
->BitArrayPtr
[FoundBytePos
] & bit (FoundBitPos
)) != 0) {
586 // Have the (FoundBytePos,FoundBitPos) make sense.
588 if (FoundBitPos
> 7) {
594 // Set the memory as allocated
596 for (TempBytePos
= FoundBytePos
, Index
= FoundBitPos
, Count
= 0; Count
< NumberOfMemoryUnit
; Count
++) {
598 MemoryHeader
->BitArrayPtr
[TempBytePos
] |= bit (Index
);
606 *Pool
= MemoryHeader
->MemoryBlockPtr
+ (FoundBytePos
* 8 + FoundBitPos
) * 32;
612 IsMemoryBlockEmptied (
613 IN MEMORY_MANAGE_HEADER
*MemoryHeaderPtr
619 Is Memory Block Emptied
623 MemoryHeaderPtr - MEMORY_MANAGE_HEADER
634 for (Index
= 0; Index
< MemoryHeaderPtr
->BitArraySizeInBytes
; Index
++) {
635 if (MemoryHeaderPtr
->BitArrayPtr
[Index
] != 0) {
645 IN MEMORY_MANAGE_HEADER
*FirstMemoryHeader
,
646 IN MEMORY_MANAGE_HEADER
*NeedFreeMemoryHeader
656 FirstMemoryHeader - MEMORY_MANAGE_HEADER
657 NeedFreeMemoryHeader - MEMORY_MANAGE_HEADER
665 MEMORY_MANAGE_HEADER
*TempHeaderPtr
;
667 if ((FirstMemoryHeader
== NULL
) || (NeedFreeMemoryHeader
== NULL
)) {
671 for (TempHeaderPtr
= FirstMemoryHeader
; TempHeaderPtr
!= NULL
; TempHeaderPtr
= TempHeaderPtr
->Next
) {
673 if (TempHeaderPtr
->Next
== NeedFreeMemoryHeader
) {
675 // Link the before and after
677 TempHeaderPtr
->Next
= NeedFreeMemoryHeader
->Next
;
684 InitialMemoryManagement (
685 IN USB2_HC_DEV
*HcDev
691 Initialize Memory Management
700 EFI_DEVICE_ERROR Fail
705 MEMORY_MANAGE_HEADER
*MemoryHeader
;
708 MemPages
= NORMAL_MEMORY_BLOCK_UNIT_IN_PAGES
;
709 Status
= CreateMemoryBlock (HcDev
, &MemoryHeader
, MemPages
);
710 if (EFI_ERROR (Status
)) {
711 Status
= EFI_OUT_OF_RESOURCES
;
715 HcDev
->MemoryHeader
= MemoryHeader
;
722 DeinitialMemoryManagement (
723 IN USB2_HC_DEV
*HcDev
729 Deinitialize Memory Management
738 EFI_DEVICE_ERROR Fail
742 MEMORY_MANAGE_HEADER
*TempHeaderPtr
;
744 for (TempHeaderPtr
= HcDev
->MemoryHeader
->Next
; TempHeaderPtr
!= NULL
;) {
746 DelinkMemoryBlock (HcDev
->MemoryHeader
, TempHeaderPtr
);
748 // when the TempHeaderPtr is freed in FreeMemoryHeader(),
749 // the TempHeaderPtr is pointing to nonsense content.
751 FreeMemoryHeader (HcDev
, TempHeaderPtr
);
753 // reset the TempHeaderPtr,continue free another memory block.
755 TempHeaderPtr
= HcDev
->MemoryHeader
->Next
;
758 FreeMemoryHeader (HcDev
, HcDev
->MemoryHeader
);