MdeModulePkg/Core/Dxe/Dispatcher/Dependency.c

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