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
/ MEM_UNIT_SIZE
) / 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
& (MEM_UNIT_SIZE
- 1)) {
248 RealAllocSize
= (AllocSize
/ MEM_UNIT_SIZE
+ 1) * MEM_UNIT_SIZE
;
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 (
265 RealAllocSize
/ MEM_UNIT_SIZE
267 if (!EFI_ERROR (Status
)) {
272 gBS
->RestoreTPL (OldTpl
);
274 if (!EFI_ERROR (Status
)) {
275 ZeroMem (*Pool
, AllocSize
);
281 // There is no enough memory,
282 // Create a new Memory Block
286 // if pool size is larger than NORMAL_MEMORY_BLOCK_UNIT_IN_PAGES,
287 // just allocate a large enough memory block.
289 if (RealAllocSize
> EFI_PAGES_TO_SIZE (NORMAL_MEMORY_BLOCK_UNIT_IN_PAGES
)) {
290 MemoryBlockSizeInPages
= EFI_SIZE_TO_PAGES (RealAllocSize
) + 1;
292 MemoryBlockSizeInPages
= NORMAL_MEMORY_BLOCK_UNIT_IN_PAGES
;
295 Status
= CreateMemoryBlock (HcDev
, &NewMemoryHeader
, MemoryBlockSizeInPages
);
296 if (EFI_ERROR (Status
)) {
300 OldTpl
= gBS
->RaiseTPL (EFI_TPL_NOTIFY
+ 1);
303 // Link the new Memory Block to the Memory Header list
305 InsertMemoryHeaderToList (MemoryHeader
, NewMemoryHeader
);
307 Status
= AllocMemInMemoryBlock (
310 RealAllocSize
/ MEM_UNIT_SIZE
313 gBS
->RestoreTPL (OldTpl
);
315 if (!EFI_ERROR (Status
)) {
316 ZeroMem (*Pool
, AllocSize
);
324 IN USB2_HC_DEV
*HcDev
,
338 AllocSize - Pool size
346 MEMORY_MANAGE_HEADER
*MemoryHeader
;
347 MEMORY_MANAGE_HEADER
*TempHeaderPtr
;
356 OldTpl
= gBS
->RaiseTPL (EFI_TPL_NOTIFY
+ 1);
358 MemoryHeader
= HcDev
->MemoryHeader
;
361 // allocate unit is 32 byte (align on 32 byte)
363 if (AllocSize
& (MEM_UNIT_SIZE
- 1)) {
364 RealAllocSize
= (AllocSize
/ MEM_UNIT_SIZE
+ 1) * MEM_UNIT_SIZE
;
366 RealAllocSize
= AllocSize
;
370 // scan the memory header linked list for
371 // the asigned memory to free.
373 for (TempHeaderPtr
= MemoryHeader
; TempHeaderPtr
!= NULL
; TempHeaderPtr
= TempHeaderPtr
->Next
) {
375 if ((Pool
>= TempHeaderPtr
->MemoryBlockPtr
) &&
376 ((Pool
+ RealAllocSize
) <= (TempHeaderPtr
->MemoryBlockPtr
+ TempHeaderPtr
->MemoryBlockSizeInBytes
))
379 // Pool is in the Memory Block area,
380 // find the start byte and bit in the bit array
382 StartBytePos
= ((Pool
- TempHeaderPtr
->MemoryBlockPtr
) / MEM_UNIT_SIZE
) / 8;
383 StartBitPos
= (UINT8
) (((Pool
- TempHeaderPtr
->MemoryBlockPtr
) / MEM_UNIT_SIZE
) & 0x7);
386 // reset associated bits in bit arry
388 for (Index
= StartBytePos
, Index2
= StartBitPos
, Count
= 0; Count
< (RealAllocSize
/ MEM_UNIT_SIZE
); Count
++) {
389 ASSERT ((TempHeaderPtr
->BitArrayPtr
[Index
] & bit (Index2
) )== bit (Index2
));
391 TempHeaderPtr
->BitArrayPtr
[Index
] ^= (UINT8
) (bit (Index2
));
406 // Release emptied memory blocks (only if the memory block is not
407 // the first one in the memory header list
409 for (TempHeaderPtr
= MemoryHeader
->Next
; TempHeaderPtr
!= NULL
;) {
411 ASSERT (MemoryHeader
->Next
!= NULL
);
413 if (IsMemoryBlockEmptied (TempHeaderPtr
)) {
415 DelinkMemoryBlock (MemoryHeader
, TempHeaderPtr
);
417 // when the TempHeaderPtr is freed in FreeMemoryHeader(),
418 // the TempHeaderPtr is pointing to nonsense content.
420 gBS
->RestoreTPL (OldTpl
);
421 FreeMemoryHeader (HcDev
, TempHeaderPtr
);
422 OldTpl
= gBS
->RaiseTPL (EFI_TPL_NOTIFY
+ 1);
424 // reset the TempHeaderPtr, continue search for
425 // another empty memory block.
427 TempHeaderPtr
= MemoryHeader
->Next
;
431 TempHeaderPtr
= TempHeaderPtr
->Next
;
434 gBS
->RestoreTPL (OldTpl
);
438 InsertMemoryHeaderToList (
439 IN MEMORY_MANAGE_HEADER
*MemoryHeader
,
440 IN MEMORY_MANAGE_HEADER
*NewMemoryHeader
446 Insert Memory Header To List
450 MemoryHeader - MEMORY_MANAGE_HEADER
451 NewMemoryHeader - MEMORY_MANAGE_HEADER
459 MEMORY_MANAGE_HEADER
*TempHeaderPtr
;
461 for (TempHeaderPtr
= MemoryHeader
; TempHeaderPtr
!= NULL
; TempHeaderPtr
= TempHeaderPtr
->Next
) {
462 if (TempHeaderPtr
->Next
== NULL
) {
463 TempHeaderPtr
->Next
= NewMemoryHeader
;
470 AllocMemInMemoryBlock (
471 IN MEMORY_MANAGE_HEADER
*MemoryHeader
,
473 IN UINTN NumberOfMemoryUnit
479 Alloc Memory In MemoryBlock
483 MemoryHeader - MEMORY_MANAGE_HEADER
484 Pool - Place to store pointer to memory
485 NumberOfMemoryUnit - Number Of Memory Unit
490 EFI_NOT_FOUND Can't find the free memory
505 ByteValue
= MemoryHeader
->BitArrayPtr
[0];
509 for (TempBytePos
= 0; TempBytePos
< MemoryHeader
->BitArraySizeInBytes
;) {
512 // Pop out BitValue from a byte in TempBytePos.
514 BitValue
= (UINT8
) (ByteValue
& 0x1);
517 // right shift the byte
519 ByteValue
= ByteValue
>> 1;
523 // Found a free bit, the NumberOfZeros only record the number
524 // of those consecutive zeros
528 // Found enough consecutive free space, break the loop
530 if (NumberOfZeros
>= NumberOfMemoryUnit
) {
535 // Encountering a '1', meant the bit is ocupied.
537 if (NumberOfZeros
>= NumberOfMemoryUnit
) {
539 // Found enough consecutive free space,break the loop
544 // the NumberOfZeros only record the number of those consecutive zeros,
545 // so reset the NumberOfZeros to 0 when encountering '1' before finding
546 // enough consecutive '0's
550 // reset the (FoundBytePos,FoundBitPos) to the position of '1'
552 FoundBytePos
= TempBytePos
;
558 // step forward a bit
563 // step forward a byte, getting the byte value,
564 // and reset the bit pos.
567 ByteValue
= MemoryHeader
->BitArrayPtr
[TempBytePos
];
572 if (NumberOfZeros
< NumberOfMemoryUnit
) {
573 return EFI_NOT_FOUND
;
577 // Found enough free space.
581 // The values recorded in (FoundBytePos,FoundBitPos) have two conditions:
582 // 1)(FoundBytePos,FoundBitPos) record the position
583 // of the last '1' before the consecutive '0's, it must
584 // be adjusted to the start position of the consecutive '0's.
585 // 2)the start address of the consecutive '0's is just the start of
586 // the bitarray. so no need to adjust the values of
587 // (FoundBytePos,FoundBitPos).
589 if ((MemoryHeader
->BitArrayPtr
[FoundBytePos
] & bit (FoundBitPos
)) != 0) {
594 // Have the (FoundBytePos,FoundBitPos) make sense.
596 if (FoundBitPos
> 7) {
602 // Set the memory as allocated
604 for (TempBytePos
= FoundBytePos
, Index
= FoundBitPos
, Count
= 0; Count
< NumberOfMemoryUnit
; Count
++) {
606 ASSERT ((MemoryHeader
->BitArrayPtr
[TempBytePos
] & bit (Index
) )== 0);
607 MemoryHeader
->BitArrayPtr
[TempBytePos
] |= bit (Index
);
615 *Pool
= MemoryHeader
->MemoryBlockPtr
+ (FoundBytePos
* 8 + FoundBitPos
) * MEM_UNIT_SIZE
;
621 IsMemoryBlockEmptied (
622 IN MEMORY_MANAGE_HEADER
*MemoryHeaderPtr
628 Is Memory Block Emptied
632 MemoryHeaderPtr - MEMORY_MANAGE_HEADER
643 for (Index
= 0; Index
< MemoryHeaderPtr
->BitArraySizeInBytes
; Index
++) {
644 if (MemoryHeaderPtr
->BitArrayPtr
[Index
] != 0) {
654 IN MEMORY_MANAGE_HEADER
*FirstMemoryHeader
,
655 IN MEMORY_MANAGE_HEADER
*NeedFreeMemoryHeader
665 FirstMemoryHeader - MEMORY_MANAGE_HEADER
666 NeedFreeMemoryHeader - MEMORY_MANAGE_HEADER
674 MEMORY_MANAGE_HEADER
*TempHeaderPtr
;
676 if ((FirstMemoryHeader
== NULL
) || (NeedFreeMemoryHeader
== NULL
)) {
680 for (TempHeaderPtr
= FirstMemoryHeader
; TempHeaderPtr
!= NULL
; TempHeaderPtr
= TempHeaderPtr
->Next
) {
682 if (TempHeaderPtr
->Next
== NeedFreeMemoryHeader
) {
684 // Link the before and after
686 TempHeaderPtr
->Next
= NeedFreeMemoryHeader
->Next
;
687 NeedFreeMemoryHeader
->Next
= NULL
;
694 InitialMemoryManagement (
695 IN USB2_HC_DEV
*HcDev
701 Initialize Memory Management
710 EFI_DEVICE_ERROR Fail
715 MEMORY_MANAGE_HEADER
*MemoryHeader
;
718 MemPages
= NORMAL_MEMORY_BLOCK_UNIT_IN_PAGES
;
719 Status
= CreateMemoryBlock (HcDev
, &MemoryHeader
, MemPages
);
720 if (EFI_ERROR (Status
)) {
721 Status
= EFI_OUT_OF_RESOURCES
;
725 HcDev
->MemoryHeader
= MemoryHeader
;
732 DeinitialMemoryManagement (
733 IN USB2_HC_DEV
*HcDev
739 Deinitialize Memory Management
748 EFI_DEVICE_ERROR Fail
752 MEMORY_MANAGE_HEADER
*TempHeaderPtr
;
754 for (TempHeaderPtr
= HcDev
->MemoryHeader
->Next
; TempHeaderPtr
!= NULL
;) {
756 DelinkMemoryBlock (HcDev
->MemoryHeader
, TempHeaderPtr
);
758 // when the TempHeaderPtr is freed in FreeMemoryHeader(),
759 // the TempHeaderPtr is pointing to nonsense content.
761 FreeMemoryHeader (HcDev
, TempHeaderPtr
);
763 // reset the TempHeaderPtr,continue free another memory block.
765 TempHeaderPtr
= HcDev
->MemoryHeader
->Next
;
768 FreeMemoryHeader (HcDev
, HcDev
->MemoryHeader
);