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