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