+ @param Mtrrs Array holding all MTRR settings.\r
+ @param MtrrCapacity Capacity of the MTRR array.\r
+ @param MtrrCount The count of MTRR settings in array.\r
+ @param BaseAddress Base address.\r
+ @param Length Length.\r
+ @param Type Memory type.\r
+\r
+ @retval RETURN_SUCCESS MTRR setting is appended to array.\r
+ @retval RETURN_OUT_OF_RESOURCES Array is full.\r
+**/\r
+RETURN_STATUS\r
+MtrrLibAppendVariableMtrr (\r
+ IN OUT MTRR_MEMORY_RANGE *Mtrrs,\r
+ IN UINT32 MtrrCapacity,\r
+ IN OUT UINT32 *MtrrCount,\r
+ IN UINT64 BaseAddress,\r
+ IN UINT64 Length,\r
+ IN MTRR_MEMORY_CACHE_TYPE Type\r
+ )\r
+{\r
+ if (*MtrrCount == MtrrCapacity) {\r
+ return RETURN_OUT_OF_RESOURCES;\r
+ }\r
+\r
+ Mtrrs[*MtrrCount].BaseAddress = BaseAddress;\r
+ Mtrrs[*MtrrCount].Length = Length;\r
+ Mtrrs[*MtrrCount].Type = Type;\r
+ (*MtrrCount)++;\r
+ return RETURN_SUCCESS;\r
+}\r
+\r
+/**\r
+ Return the memory type that has the least precedence.\r
+\r
+ @param TypeBits Bit mask of memory type.\r
+\r
+ @retval Memory type that has the least precedence.\r
+**/\r
+MTRR_MEMORY_CACHE_TYPE\r
+MtrrLibLowestType (\r
+ IN UINT8 TypeBits\r
+)\r
+{\r
+ INT8 Type;\r
+\r
+ ASSERT (TypeBits != 0);\r
+ for (Type = 7; (INT8)TypeBits > 0; Type--, TypeBits <<= 1);\r
+ return (MTRR_MEMORY_CACHE_TYPE)Type;\r
+}\r
+\r
+/**\r
+ Return TRUE when the Operand is exactly power of 2.\r
+\r
+ @retval TRUE Operand is exactly power of 2.\r
+ @retval FALSE Operand is not power of 2.\r
+**/\r
+BOOLEAN\r
+MtrrLibIsPowerOfTwo (\r
+ IN UINT64 Operand\r
+)\r
+{\r
+ ASSERT (Operand != 0);\r
+ return (BOOLEAN) ((Operand & (Operand - 1)) == 0);\r
+}\r
+\r
+/**\r
+ Calculate the subtractive path from vector Start to Stop.\r
+\r
+ @param DefaultType Default memory type.\r
+ @param A0 Alignment to use when base address is 0.\r
+ @param Ranges Array holding memory type settings for all memory regions.\r
+ @param RangeCount The count of memory ranges the array holds.\r
+ @param VectorCount The count of vectors in the graph.\r
+ @param Vector Array holding all vectors.\r
+ @param Weight 2-dimention array holding weights between vectors.\r
+ @param Start Start vector.\r
+ @param Stop Stop vector.\r
+ @param Types Type bit mask of memory range from Start to Stop.\r
+ @param TypeCount Number of different memory types from Start to Stop.\r
+ @param Mtrrs Array holding all MTRR settings.\r
+ @param MtrrCapacity Capacity of the MTRR array.\r
+ @param MtrrCount The count of MTRR settings in array.\r
+\r
+ @retval RETURN_SUCCESS The subtractive path is calculated successfully.\r
+ @retval RETURN_OUT_OF_RESOURCES The MTRR setting array is full.\r
+\r
+**/\r
+RETURN_STATUS\r
+MtrrLibCalculateSubtractivePath (\r
+ IN MTRR_MEMORY_CACHE_TYPE DefaultType,\r
+ IN UINT64 A0,\r
+ IN CONST MTRR_MEMORY_RANGE *Ranges,\r
+ IN UINTN RangeCount,\r
+ IN UINT16 VectorCount,\r
+ IN MTRR_LIB_ADDRESS *Vector,\r
+ IN OUT UINT8 *Weight,\r
+ IN UINT16 Start,\r
+ IN UINT16 Stop,\r
+ IN UINT8 Types,\r
+ IN UINT8 TypeCount,\r
+ IN OUT MTRR_MEMORY_RANGE *Mtrrs, OPTIONAL\r
+ IN UINT32 MtrrCapacity, OPTIONAL\r
+ IN OUT UINT32 *MtrrCount OPTIONAL\r
+ )\r
+{\r
+ RETURN_STATUS Status;\r
+ UINT64 Base;\r
+ UINT64 Length;\r
+ UINT8 PrecedentTypes;\r
+ UINTN Index;\r
+ UINT64 HBase;\r
+ UINT64 HLength;\r
+ UINT64 SubLength;\r
+ UINT16 SubStart;\r
+ UINT16 SubStop;\r
+ UINT16 Cur;\r
+ UINT16 Pre;\r
+ MTRR_MEMORY_CACHE_TYPE LowestType;\r
+ MTRR_MEMORY_CACHE_TYPE LowestPrecedentType;\r
+\r
+ Base = Vector[Start].Address;\r
+ Length = Vector[Stop].Address - Base;\r
+\r
+ LowestType = MtrrLibLowestType (Types);\r
+\r
+ //\r
+ // Clear the lowest type (highest bit) to get the precedent types\r
+ //\r
+ PrecedentTypes = ~(1 << LowestType) & Types;\r
+ LowestPrecedentType = MtrrLibLowestType (PrecedentTypes);\r
+\r
+ if (Mtrrs == NULL) {\r
+ Weight[M(Start, Stop)] = ((LowestType == DefaultType) ? 0 : 1);\r
+ Weight[O(Start, Stop)] = ((LowestType == DefaultType) ? 1 : 0);\r
+ }\r
+\r
+ // Add all high level ranges\r
+ HBase = MAX_UINT64;\r
+ HLength = 0;\r
+ for (Index = 0; Index < RangeCount; Index++) {\r
+ if (Length == 0) {\r
+ break;\r
+ }\r
+ if ((Base < Ranges[Index].BaseAddress) || (Ranges[Index].BaseAddress + Ranges[Index].Length <= Base)) {\r
+ continue;\r
+ }\r
+\r
+ //\r
+ // Base is in the Range[Index]\r
+ //\r
+ if (Base + Length > Ranges[Index].BaseAddress + Ranges[Index].Length) {\r
+ SubLength = Ranges[Index].BaseAddress + Ranges[Index].Length - Base;\r
+ } else {\r
+ SubLength = Length;\r
+ }\r
+ if (((1 << Ranges[Index].Type) & PrecedentTypes) != 0) {\r
+ //\r
+ // Meet a range whose types take precedence.\r
+ // Update the [HBase, HBase + HLength) to include the range,\r
+ // [HBase, HBase + HLength) may contain sub ranges with 2 different types, and both take precedence.\r
+ //\r
+ if (HBase == MAX_UINT64) {\r
+ HBase = Base;\r
+ }\r
+ HLength += SubLength;\r
+ }\r
+\r
+ Base += SubLength;\r
+ Length -= SubLength;\r
+\r
+ if (HLength == 0) {\r
+ continue;\r
+ }\r
+\r
+ if ((Ranges[Index].Type == LowestType) || (Length == 0)) { // meet low type or end\r
+\r
+ //\r
+ // Add the MTRRs for each high priority type range\r
+ // the range[HBase, HBase + HLength) contains only two types.\r
+ // We might use positive or subtractive, depending on which way uses less MTRR\r
+ //\r
+ for (SubStart = Start; SubStart <= Stop; SubStart++) {\r
+ if (Vector[SubStart].Address == HBase) {\r
+ break;\r
+ }\r
+ }\r
+\r
+ for (SubStop = SubStart; SubStop <= Stop; SubStop++) {\r
+ if (Vector[SubStop].Address == HBase + HLength) {\r
+ break;\r
+ }\r
+ }\r
+ ASSERT (Vector[SubStart].Address == HBase);\r
+ ASSERT (Vector[SubStop].Address == HBase + HLength);\r
+\r
+ if ((TypeCount == 2) || (SubStart == SubStop - 1)) {\r
+ //\r
+ // add subtractive MTRRs for [HBase, HBase + HLength)\r
+ // [HBase, HBase + HLength) contains only one type.\r
+ // while - loop is to split the range to MTRR - compliant aligned range.\r
+ //\r
+ if (Mtrrs == NULL) {\r
+ Weight[M (Start, Stop)] += (UINT8)(SubStop - SubStart);\r
+ } else {\r
+ while (SubStart != SubStop) {\r
+ Status = MtrrLibAppendVariableMtrr (\r
+ Mtrrs, MtrrCapacity, MtrrCount,\r
+ Vector[SubStart].Address, Vector[SubStart].Length, (MTRR_MEMORY_CACHE_TYPE) Vector[SubStart].Type\r
+ );\r
+ if (RETURN_ERROR (Status)) {\r
+ return Status;\r
+ }\r
+ SubStart++;\r
+ }\r
+ }\r
+ } else {\r
+ ASSERT (TypeCount == 3);\r
+ MtrrLibCalculateLeastMtrrs (VectorCount, Vector, Weight, SubStart, SubStop, TRUE);\r
+\r
+ if (Mtrrs == NULL) {\r
+ Weight[M (Start, Stop)] += Vector[SubStop].Weight;\r
+ } else {\r
+ // When we need to collect the optimal path from SubStart to SubStop\r
+ while (SubStop != SubStart) {\r
+ Cur = SubStop;\r
+ Pre = Vector[Cur].Previous;\r
+ SubStop = Pre;\r
+\r
+ if (Weight[M (Pre, Cur)] != 0) {\r
+ Status = MtrrLibAppendVariableMtrr (\r
+ Mtrrs, MtrrCapacity, MtrrCount,\r
+ Vector[Pre].Address, Vector[Cur].Address - Vector[Pre].Address, LowestPrecedentType\r
+ );\r
+ if (RETURN_ERROR (Status)) {\r
+ return Status;\r
+ }\r
+ }\r
+ if (Pre != Cur - 1) {\r
+ Status = MtrrLibCalculateSubtractivePath (\r
+ DefaultType, A0,\r
+ Ranges, RangeCount,\r
+ VectorCount, Vector, Weight,\r
+ Pre, Cur, PrecedentTypes, 2,\r
+ Mtrrs, MtrrCapacity, MtrrCount\r
+ );\r
+ if (RETURN_ERROR (Status)) {\r
+ return Status;\r
+ }\r
+ }\r
+ }\r
+ }\r
+\r
+ }\r
+ //\r
+ // Reset HBase, HLength\r
+ //\r
+ HBase = MAX_UINT64;\r
+ HLength = 0;\r
+ }\r
+ }\r
+ return RETURN_SUCCESS;\r
+}\r
+\r
+/**\r
+ Calculate MTRR settings to cover the specified memory ranges.\r
+\r
+ @param DefaultType Default memory type.\r
+ @param A0 Alignment to use when base address is 0.\r
+ @param Ranges Memory range array holding the memory type\r
+ settings for all memory address.\r
+ @param RangeCount Count of memory ranges.\r
+ @param Scratch A temporary scratch buffer that is used to perform the calculation.\r
+ This is an optional parameter that may be NULL.\r
+ @param ScratchSize Pointer to the size in bytes of the scratch buffer.\r
+ It may be updated to the actual required size when the calculation\r
+ needs more scratch buffer.\r
+ @param Mtrrs Array holding all MTRR settings.\r
+ @param MtrrCapacity Capacity of the MTRR array.\r
+ @param MtrrCount The count of MTRR settings in array.\r