1 /** @file
2 PEI Dispatcher Dependency Evaluator
3
4 This routine evaluates a dependency expression (DEPENDENCY_EXPRESSION) to determine
5 if a driver can be scheduled for execution. The criteria for
6 schedulability is that the dependency expression is satisfied.
7
8 Copyright (c) 2006 - 2018, Intel Corporation. All rights reserved.<BR>
9 SPDX-License-Identifier: BSD-2-Clause-Patent
10
11 **/
12
13 #include "PeiMain.h"
14 #include "Dependency.h"
15
16 /**
17
18 This routine determines if a PPI has been installed.
19 The truth value of a GUID is determined by if the PPI has
20 been published and can be queried from the PPI database.
21
22
23 @param PeiServices An indirect pointer to the EFI_PEI_SERVICES table published by the PEI Foundation
24 @param Stack Reference to EVAL_STACK_ENTRY that contains PPI GUID to check
25
26 @retval TRUE if the PPI is already installed.
27 @retval FALSE if the PPI has yet to be installed.
28
29 **/
30 BOOLEAN
IsPpiInstalled(IN EFI_PEI_SERVICES ** PeiServices,IN EVAL_STACK_ENTRY * Stack)31 IsPpiInstalled (
32 IN EFI_PEI_SERVICES **PeiServices,
33 IN EVAL_STACK_ENTRY *Stack
34 )
35 {
36 VOID *PeiInstance;
37 EFI_STATUS Status;
38 EFI_GUID PpiGuid;
39
40 //
41 // If there is no GUID to evaluate, just return current result on stack.
42 //
43 if (Stack->Operator == NULL) {
44 return Stack->Result;
45 }
46
47 //
48 // Copy the Guid into a locale variable so that there are no
49 // possibilities of alignment faults for cross-compilation
50 // environments such as Intel?Itanium(TM).
51 //
52 CopyMem(&PpiGuid, Stack->Operator, sizeof(EFI_GUID));
53
54 //
55 // Check if the PPI is installed.
56 //
57 Status = PeiServicesLocatePpi(
58 &PpiGuid, // GUID
59 0, // INSTANCE
60 NULL, // EFI_PEI_PPI_DESCRIPTOR
61 &PeiInstance // PPI
62 );
63
64 if (EFI_ERROR(Status)) {
65 return FALSE;
66 }
67
68 return TRUE;
69 }
70
71 /**
72
73 This is the POSTFIX version of the dependency evaluator. When a
74 PUSH [PPI GUID] is encountered, a pointer to the GUID is stored on
75 the evaluation stack. When that entry is poped from the evaluation
76 stack, the PPI is checked if it is installed. This method allows
77 some time savings as not all PPIs must be checked for certain
78 operation types (AND, OR).
79
80
81 @param PeiServices An indirect pointer to the EFI_PEI_SERVICES table published by the PEI Foundation
82 @param DependencyExpression Pointer to a dependency expression. The Grammar adheres to
83 the BNF described above and is stored in postfix notation.
84
85 @retval TRUE if it is a well-formed Grammar
86 @retval FALSE if the dependency expression overflows the evaluation stack
87 if the dependency expression underflows the evaluation stack
88 if the dependency expression is not a well-formed Grammar.
89
90 **/
91 BOOLEAN
PeimDispatchReadiness(IN EFI_PEI_SERVICES ** PeiServices,IN VOID * DependencyExpression)92 PeimDispatchReadiness (
93 IN EFI_PEI_SERVICES **PeiServices,
94 IN VOID *DependencyExpression
95 )
96 {
97 DEPENDENCY_EXPRESSION_OPERAND *Iterator;
98 EVAL_STACK_ENTRY *StackPtr;
99 EVAL_STACK_ENTRY EvalStack[MAX_GRAMMAR_SIZE];
100
101 Iterator = DependencyExpression;
102
103 StackPtr = EvalStack;
104
105 while (TRUE) {
106
107 switch (*(Iterator++)) {
108
109 //
110 // For performance reason we put the frequently used items in front of
111 // the rarely used items
112 //
113
114 case (EFI_DEP_PUSH):
115 //
116 // Check to make sure the dependency grammar doesn't overflow the
117 // EvalStack on the push
118 //
119 if (StackPtr > &EvalStack[MAX_GRAMMAR_SIZE-1]) {
120 DEBUG ((DEBUG_DISPATCH, " RESULT = FALSE (Underflow Error)\n"));
121 return FALSE;
122 }
123
124 //
125 // Push the pointer to the PUSH opcode operator (pointer to PPI GUID)
126 // We will evaluate if the PPI is insalled on the POP operation.
127 //
128 StackPtr->Operator = (VOID *) Iterator;
129 Iterator = Iterator + sizeof (EFI_GUID);
130 DEBUG ((DEBUG_DISPATCH, " PUSH GUID(%g) = %a\n", StackPtr->Operator, IsPpiInstalled (PeiServices, StackPtr) ? "TRUE" : "FALSE"));
131 StackPtr++;
132 break;
133
134 case (EFI_DEP_AND):
135 case (EFI_DEP_OR):
136 if (*(Iterator - 1) == EFI_DEP_AND) {
137 DEBUG ((DEBUG_DISPATCH, " AND\n"));
138 } else {
139 DEBUG ((DEBUG_DISPATCH, " OR\n"));
140 }
141 //
142 // Check to make sure the dependency grammar doesn't underflow the
143 // EvalStack on the two POPs for the AND operation. Don't need to
144 // check for the overflow on PUSHing the result since we already
145 // did two POPs.
146 //
147 if (StackPtr < &EvalStack[2]) {
148 DEBUG ((DEBUG_DISPATCH, " RESULT = FALSE (Underflow Error)\n"));
149 return FALSE;
150 }
151
152 //
153 // Evaluate the first POPed operator only. If the operand is
154 // EFI_DEP_AND and the POPed operator evaluates to FALSE, or the
155 // operand is EFI_DEP_OR and the POPed operator evaluates to TRUE,
156 // we don't need to check the second operator, and the result will be
157 // evaluation of the POPed operator. Otherwise, don't POP the second
158 // operator since it will now evaluate to the final result on the
159 // next operand that causes a POP.
160 //
161 StackPtr--;
162 //
163 // Iterator has increased by 1 after we retrieve the operand, so here we
164 // should get the value pointed by (Iterator - 1), in order to obtain the
165 // same operand.
166 //
167 if (*(Iterator - 1) == EFI_DEP_AND) {
168 if (!(IsPpiInstalled (PeiServices, StackPtr))) {
169 (StackPtr-1)->Result = FALSE;
170 (StackPtr-1)->Operator = NULL;
171 }
172 } else {
173 if (IsPpiInstalled (PeiServices, StackPtr)) {
174 (StackPtr-1)->Result = TRUE;
175 (StackPtr-1)->Operator = NULL;
176 }
177 }
178 break;
179
180 case (EFI_DEP_END):
181 DEBUG ((DEBUG_DISPATCH, " END\n"));
182 StackPtr--;
183 //
184 // Check to make sure EvalStack is balanced. If not, then there is
185 // an error in the dependency grammar, so return EFI_INVALID_PARAMETER.
186 //
187 if (StackPtr != &EvalStack[0]) {
188 DEBUG ((DEBUG_DISPATCH, " RESULT = FALSE (Underflow Error)\n"));
189 return FALSE;
190 }
191 DEBUG ((DEBUG_DISPATCH, " RESULT = %a\n", IsPpiInstalled (PeiServices, StackPtr) ? "TRUE" : "FALSE"));
192 return IsPpiInstalled (PeiServices, StackPtr);
193
194 case (EFI_DEP_NOT):
195 DEBUG ((DEBUG_DISPATCH, " NOT\n"));
196 //
197 // Check to make sure the dependency grammar doesn't underflow the
198 // EvalStack on the POP for the NOT operation. Don't need to
199 // check for the overflow on PUSHing the result since we already
200 // did a POP.
201 //
202 if (StackPtr < &EvalStack[1]) {
203 DEBUG ((DEBUG_DISPATCH, " RESULT = FALSE (Underflow Error)\n"));
204 return FALSE;
205 }
206 (StackPtr-1)->Result = (BOOLEAN) !IsPpiInstalled (PeiServices, (StackPtr-1));
207 (StackPtr-1)->Operator = NULL;
208 break;
209
210 case (EFI_DEP_TRUE):
211 case (EFI_DEP_FALSE):
212 if (*(Iterator - 1) == EFI_DEP_TRUE) {
213 DEBUG ((DEBUG_DISPATCH, " TRUE\n"));
214 } else {
215 DEBUG ((DEBUG_DISPATCH, " FALSE\n"));
216 }
217 //
218 // Check to make sure the dependency grammar doesn't overflow the
219 // EvalStack on the push
220 //
221 if (StackPtr > &EvalStack[MAX_GRAMMAR_SIZE-1]) {
222 DEBUG ((DEBUG_DISPATCH, " RESULT = FALSE (Underflow Error)\n"));
223 return FALSE;
224 }
225 //
226 // Iterator has increased by 1 after we retrieve the operand, so here we
227 // should get the value pointed by (Iterator - 1), in order to obtain the
228 // same operand.
229 //
230 if (*(Iterator - 1) == EFI_DEP_TRUE) {
231 StackPtr->Result = TRUE;
232 } else {
233 StackPtr->Result = FALSE;
234 }
235 StackPtr->Operator = NULL;
236 StackPtr++;
237 break;
238
239 default:
240 DEBUG ((DEBUG_DISPATCH, " RESULT = FALSE (Invalid opcode)\n"));
241 //
242 // The grammar should never arrive here
243 //
244 return FALSE;
245 }
246 }
247 }
248