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