MdeModulePkg/Core/Dxe/Dispatcher/dependency.c

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