1 /** @file 2 DXE 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 - 2010, 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 "DxeMain.h" 20 21 // 22 // Global stack used to evaluate dependency expressions 23 // 24 BOOLEAN *mDepexEvaluationStack = NULL; 25 BOOLEAN *mDepexEvaluationStackEnd = NULL; 26 BOOLEAN *mDepexEvaluationStackPointer = NULL; 27 28 // 29 // Worker functions 30 // 31 32 33 /** 34 Grow size of the Depex stack 35 36 @retval EFI_SUCCESS Stack successfully growed. 37 @retval EFI_OUT_OF_RESOURCES There is not enough system memory to grow the stack. 38 39 **/ 40 EFI_STATUS 41 GrowDepexStack ( 42 VOID 43 ) 44 { 45 BOOLEAN *NewStack; 46 UINTN Size; 47 48 Size = DEPEX_STACK_SIZE_INCREMENT; 49 if (mDepexEvaluationStack != NULL) { 50 Size = Size + (mDepexEvaluationStackEnd - mDepexEvaluationStack); 51 } 52 53 NewStack = AllocatePool (Size * sizeof (BOOLEAN)); 54 if (NewStack == NULL) { 55 return EFI_OUT_OF_RESOURCES; 56 } 57 58 if (mDepexEvaluationStack != NULL) { 59 // 60 // Copy to Old Stack to the New Stack 61 // 62 CopyMem ( 63 NewStack, 64 mDepexEvaluationStack, 65 (mDepexEvaluationStackEnd - mDepexEvaluationStack) * sizeof (BOOLEAN) 66 ); 67 68 // 69 // Free The Old Stack 70 // 71 FreePool (mDepexEvaluationStack); 72 } 73 74 // 75 // Make the Stack pointer point to the old data in the new stack 76 // 77 mDepexEvaluationStackPointer = NewStack + (mDepexEvaluationStackPointer - mDepexEvaluationStack); 78 mDepexEvaluationStack = NewStack; 79 mDepexEvaluationStackEnd = NewStack + Size; 80 81 return EFI_SUCCESS; 82 } 83 84 85 86 /** 87 Push an element onto the Boolean Stack. 88 89 @param Value BOOLEAN to push. 90 91 @retval EFI_SUCCESS The value was pushed onto the stack. 92 @retval EFI_OUT_OF_RESOURCES There is not enough system memory to grow the stack. 93 94 **/ 95 EFI_STATUS 96 PushBool ( 97 IN BOOLEAN Value 98 ) 99 { 100 EFI_STATUS Status; 101 102 // 103 // Check for a stack overflow condition 104 // 105 if (mDepexEvaluationStackPointer == mDepexEvaluationStackEnd) { 106 // 107 // Grow the stack 108 // 109 Status = GrowDepexStack (); 110 if (EFI_ERROR (Status)) { 111 return Status; 112 } 113 } 114 115 // 116 // Push the item onto the stack 117 // 118 *mDepexEvaluationStackPointer = Value; 119 mDepexEvaluationStackPointer++; 120 121 return EFI_SUCCESS; 122 } 123 124 125 126 /** 127 Pop an element from the Boolean stack. 128 129 @param Value BOOLEAN to pop. 130 131 @retval EFI_SUCCESS The value was popped onto the stack. 132 @retval EFI_ACCESS_DENIED The pop operation underflowed the stack. 133 134 **/ 135 EFI_STATUS 136 PopBool ( 137 OUT BOOLEAN *Value 138 ) 139 { 140 // 141 // Check for a stack underflow condition 142 // 143 if (mDepexEvaluationStackPointer == mDepexEvaluationStack) { 144 return EFI_ACCESS_DENIED; 145 } 146 147 // 148 // Pop the item off the stack 149 // 150 mDepexEvaluationStackPointer--; 151 *Value = *mDepexEvaluationStackPointer; 152 return EFI_SUCCESS; 153 } 154 155 156 157 /** 158 Preprocess dependency expression and update DriverEntry to reflect the 159 state of Before, After, and SOR dependencies. If DriverEntry->Before 160 or DriverEntry->After is set it will never be cleared. If SOR is set 161 it will be cleared by CoreSchedule(), and then the driver can be 162 dispatched. 163 164 @param DriverEntry DriverEntry element to update . 165 166 @retval EFI_SUCCESS It always works. 167 168 **/ 169 EFI_STATUS 170 CorePreProcessDepex ( 171 IN EFI_CORE_DRIVER_ENTRY *DriverEntry 172 ) 173 { 174 UINT8 *Iterator; 175 176 Iterator = DriverEntry->Depex; 177 if (*Iterator == EFI_DEP_SOR) { 178 DriverEntry->Unrequested = TRUE; 179 } else { 180 DriverEntry->Dependent = TRUE; 181 } 182 183 if (*Iterator == EFI_DEP_BEFORE) { 184 DriverEntry->Before = TRUE; 185 } else if (*Iterator == EFI_DEP_AFTER) { 186 DriverEntry->After = TRUE; 187 } 188 189 if (DriverEntry->Before || DriverEntry->After) { 190 CopyMem (&DriverEntry->BeforeAfterGuid, Iterator + 1, sizeof (EFI_GUID)); 191 } 192 193 return EFI_SUCCESS; 194 } 195 196 197 198 /** 199 This is the POSTFIX version of the dependency evaluator. This code does 200 not need to handle Before or After, as it is not valid to call this 201 routine in this case. The SOR is just ignored and is a nop in the grammer. 202 POSTFIX means all the math is done on top of the stack. 203 204 @param DriverEntry DriverEntry element to update. 205 206 @retval TRUE If driver is ready to run. 207 @retval FALSE If driver is not ready to run or some fatal error 208 was found. 209 210 **/ 211 BOOLEAN 212 CoreIsSchedulable ( 213 IN EFI_CORE_DRIVER_ENTRY *DriverEntry 214 ) 215 { 216 EFI_STATUS Status; 217 UINT8 *Iterator; 218 BOOLEAN Operator; 219 BOOLEAN Operator2; 220 EFI_GUID DriverGuid; 221 VOID *Interface; 222 223 Operator = FALSE; 224 Operator2 = FALSE; 225 226 if (DriverEntry->After || DriverEntry->Before) { 227 // 228 // If Before or After Depex skip as CoreInsertOnScheduledQueueWhileProcessingBeforeAndAfter () 229 // processes them. 230 // 231 return FALSE; 232 } 233 234 DEBUG ((DEBUG_DISPATCH, "Evaluate DXE DEPEX for FFS(%g)\n", &DriverEntry->FileName)); 235 236 if (DriverEntry->Depex == NULL) { 237 // 238 // A NULL Depex means treat the driver like an UEFI 2.0 thing. 239 // 240 Status = CoreAllEfiServicesAvailable (); 241 DEBUG ((DEBUG_DISPATCH, " All UEFI Services Available = ")); 242 if (EFI_ERROR (Status)) { 243 DEBUG ((DEBUG_DISPATCH, "FALSE\n RESULT = FALSE\n")); 244 return FALSE; 245 } 246 DEBUG ((DEBUG_DISPATCH, "TRUE\n RESULT = TRUE\n")); 247 return TRUE; 248 } 249 250 // 251 // Clean out memory leaks in Depex Boolean stack. Leaks are only caused by 252 // incorrectly formed DEPEX expressions 253 // 254 mDepexEvaluationStackPointer = mDepexEvaluationStack; 255 256 257 Iterator = DriverEntry->Depex; 258 259 while (TRUE) { 260 // 261 // Check to see if we are attempting to fetch dependency expression instructions 262 // past the end of the dependency expression. 263 // 264 if (((UINTN)Iterator - (UINTN)DriverEntry->Depex) >= DriverEntry->DepexSize) { 265 DEBUG ((DEBUG_DISPATCH, " RESULT = FALSE (Attempt to fetch past end of depex)\n")); 266 return FALSE; 267 } 268 269 // 270 // Look at the opcode of the dependency expression instruction. 271 // 272 switch (*Iterator) { 273 case EFI_DEP_BEFORE: 274 case EFI_DEP_AFTER: 275 // 276 // For a well-formed Dependency Expression, the code should never get here. 277 // The BEFORE and AFTER are processed prior to this routine's invocation. 278 // If the code flow arrives at this point, there was a BEFORE or AFTER 279 // that were not the first opcodes. 280 // 281 DEBUG ((DEBUG_DISPATCH, " RESULT = FALSE (Unexpected BEFORE or AFTER opcode)\n")); 282 ASSERT (FALSE); 283 case EFI_DEP_SOR: 284 // 285 // These opcodes can only appear once as the first opcode. If it is found 286 // at any other location, then the dependency expression evaluates to FALSE 287 // 288 if (Iterator != DriverEntry->Depex) { 289 DEBUG ((DEBUG_DISPATCH, " SOR\n")); 290 DEBUG ((DEBUG_DISPATCH, " RESULT = FALSE (Unexpected SOR opcode)\n")); 291 return FALSE; 292 } 293 DEBUG ((DEBUG_DISPATCH, " SOR = Requested\n")); 294 // 295 // Otherwise, it is the first opcode and should be treated as a NOP. 296 // 297 break; 298 299 case EFI_DEP_PUSH: 300 // 301 // Push operator is followed by a GUID. Test to see if the GUID protocol 302 // is installed and push the boolean result on the stack. 303 // 304 CopyMem (&DriverGuid, Iterator + 1, sizeof (EFI_GUID)); 305 306 Status = CoreLocateProtocol (&DriverGuid, NULL, &Interface); 307 308 if (EFI_ERROR (Status)) { 309 DEBUG ((DEBUG_DISPATCH, " PUSH GUID(%g) = FALSE\n", &DriverGuid)); 310 Status = PushBool (FALSE); 311 } else { 312 DEBUG ((DEBUG_DISPATCH, " PUSH GUID(%g) = TRUE\n", &DriverGuid)); 313 *Iterator = EFI_DEP_REPLACE_TRUE; 314 Status = PushBool (TRUE); 315 } 316 if (EFI_ERROR (Status)) { 317 DEBUG ((DEBUG_DISPATCH, " RESULT = FALSE (Unexpected error)\n")); 318 return FALSE; 319 } 320 321 Iterator += sizeof (EFI_GUID); 322 break; 323 324 case EFI_DEP_AND: 325 DEBUG ((DEBUG_DISPATCH, " AND\n")); 326 Status = PopBool (&Operator); 327 if (EFI_ERROR (Status)) { 328 DEBUG ((DEBUG_DISPATCH, " RESULT = FALSE (Unexpected error)\n")); 329 return FALSE; 330 } 331 332 Status = PopBool (&Operator2); 333 if (EFI_ERROR (Status)) { 334 DEBUG ((DEBUG_DISPATCH, " RESULT = FALSE (Unexpected error)\n")); 335 return FALSE; 336 } 337 338 Status = PushBool ((BOOLEAN)(Operator && Operator2)); 339 if (EFI_ERROR (Status)) { 340 DEBUG ((DEBUG_DISPATCH, " RESULT = FALSE (Unexpected error)\n")); 341 return FALSE; 342 } 343 break; 344 345 case EFI_DEP_OR: 346 DEBUG ((DEBUG_DISPATCH, " OR\n")); 347 Status = PopBool (&Operator); 348 if (EFI_ERROR (Status)) { 349 DEBUG ((DEBUG_DISPATCH, " RESULT = FALSE (Unexpected error)\n")); 350 return FALSE; 351 } 352 353 Status = PopBool (&Operator2); 354 if (EFI_ERROR (Status)) { 355 DEBUG ((DEBUG_DISPATCH, " RESULT = FALSE (Unexpected error)\n")); 356 return FALSE; 357 } 358 359 Status = PushBool ((BOOLEAN)(Operator || Operator2)); 360 if (EFI_ERROR (Status)) { 361 DEBUG ((DEBUG_DISPATCH, " RESULT = FALSE (Unexpected error)\n")); 362 return FALSE; 363 } 364 break; 365 366 case EFI_DEP_NOT: 367 DEBUG ((DEBUG_DISPATCH, " NOT\n")); 368 Status = PopBool (&Operator); 369 if (EFI_ERROR (Status)) { 370 DEBUG ((DEBUG_DISPATCH, " RESULT = FALSE (Unexpected error)\n")); 371 return FALSE; 372 } 373 374 Status = PushBool ((BOOLEAN)(!Operator)); 375 if (EFI_ERROR (Status)) { 376 DEBUG ((DEBUG_DISPATCH, " RESULT = FALSE (Unexpected error)\n")); 377 return FALSE; 378 } 379 break; 380 381 case EFI_DEP_TRUE: 382 DEBUG ((DEBUG_DISPATCH, " TRUE\n")); 383 Status = PushBool (TRUE); 384 if (EFI_ERROR (Status)) { 385 DEBUG ((DEBUG_DISPATCH, " RESULT = FALSE (Unexpected error)\n")); 386 return FALSE; 387 } 388 break; 389 390 case EFI_DEP_FALSE: 391 DEBUG ((DEBUG_DISPATCH, " FALSE\n")); 392 Status = PushBool (FALSE); 393 if (EFI_ERROR (Status)) { 394 DEBUG ((DEBUG_DISPATCH, " RESULT = FALSE (Unexpected error)\n")); 395 return FALSE; 396 } 397 break; 398 399 case EFI_DEP_END: 400 DEBUG ((DEBUG_DISPATCH, " END\n")); 401 Status = PopBool (&Operator); 402 if (EFI_ERROR (Status)) { 403 DEBUG ((DEBUG_DISPATCH, " RESULT = FALSE (Unexpected error)\n")); 404 return FALSE; 405 } 406 DEBUG ((DEBUG_DISPATCH, " RESULT = %a\n", Operator ? "TRUE" : "FALSE")); 407 return Operator; 408 409 case EFI_DEP_REPLACE_TRUE: 410 CopyMem (&DriverGuid, Iterator + 1, sizeof (EFI_GUID)); 411 DEBUG ((DEBUG_DISPATCH, " PUSH GUID(%g) = TRUE\n", &DriverGuid)); 412 413 Status = PushBool (TRUE); 414 if (EFI_ERROR (Status)) { 415 DEBUG ((DEBUG_DISPATCH, " RESULT = FALSE (Unexpected error)\n")); 416 return FALSE; 417 } 418 419 Iterator += sizeof (EFI_GUID); 420 break; 421 422 default: 423 DEBUG ((DEBUG_DISPATCH, " RESULT = FALSE (Unknown opcode)\n")); 424 goto Done; 425 } 426 427 // 428 // Skip over the Dependency Op Code we just processed in the switch. 429 // The math is done out of order, but it should not matter. That is 430 // we may add in the sizeof (EFI_GUID) before we account for the OP Code. 431 // This is not an issue, since we just need the correct end result. You 432 // need to be careful using Iterator in the loop as it's intermediate value 433 // may be strange. 434 // 435 Iterator++; 436 } 437 438 Done: 439 return FALSE; 440 } 441 442 443
