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 - 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   DEBUG ((DEBUG_DISPATCH, "Evaluate DXE DEPEX for FFS(%g)\n", &DriverEntry->FileName));
 224
 225   Operator = FALSE;
 226   Operator2 = FALSE;
 227
 228   if (DriverEntry->After || DriverEntry->Before) {
 229     //
 230     // If Before or After Depex skip as CoreInsertOnScheduledQueueWhileProcessingBeforeAndAfter ()
 231     // processes them.
 232     //
 233     return FALSE;
 234   }
 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