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. 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   Operator = FALSE;
 224   Operator2 = FALSE;
 225
 226   if (DriverEntry->After || DriverEntry->Before) {
 227     //
 228     // If Before or After Depex skip as CoreInsertOnScheduledQueueWhileProcessingBeforeAndAfter ()
 229     // processes them.
 230     //
 231     return FALSE;
 232   }
 233
 234   if (DriverEntry->Depex == NULL) {
 235     //
 236     // A NULL Depex means treat the driver like an UEFI 2.0 thing.
 237     //
 238     Status = CoreAllEfiServicesAvailable ();
 239     if (EFI_ERROR (Status)) {
 240       return FALSE;
 241     }
 242     return TRUE;
 243   }
 244
 245   //
 246   // Clean out memory leaks in Depex Boolean stack. Leaks are only caused by
 247   // incorrectly formed DEPEX expressions
 248   //
 249   mDepexEvaluationStackPointer = mDepexEvaluationStack;
 250
 251
 252   Iterator = DriverEntry->Depex;
 253
 254   while (TRUE) {
 255     //
 256     // Check to see if we are attempting to fetch dependency expression instructions
 257     // past the end of the dependency expression.
 258     //
 259     if (((UINTN)Iterator - (UINTN)DriverEntry->Depex) >= DriverEntry->DepexSize) {
 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       ASSERT (FALSE);
 276     case EFI_DEP_SOR:
 277       //
 278       // These opcodes can only appear once as the first opcode.  If it is found
 279       // at any other location, then the dependency expression evaluates to FALSE
 280       //
 281       if (Iterator != DriverEntry->Depex) {
 282         return FALSE;
 283       }
 284       //
 285       // Otherwise, it is the first opcode and should be treated as a NOP.
 286       //
 287       break;
 288
 289     case EFI_DEP_PUSH:
 290       //
 291       // Push operator is followed by a GUID. Test to see if the GUID protocol
 292       // is installed and push the boolean result on the stack.
 293       //
 294       CopyMem (&DriverGuid, Iterator + 1, sizeof (EFI_GUID));
 295
 296       Status = CoreLocateProtocol (&DriverGuid, NULL, &Interface);
 297
 298       if (EFI_ERROR (Status)) {
 299         Status = PushBool (FALSE);
 300       } else {
 301         *Iterator = EFI_DEP_REPLACE_TRUE;
 302         Status = PushBool (TRUE);
 303       }
 304       if (EFI_ERROR (Status)) {
 305         return FALSE;
 306       }
 307
 308       Iterator += sizeof (EFI_GUID);
 309       break;
 310
 311     case EFI_DEP_AND:
 312       Status = PopBool (&Operator);
 313       if (EFI_ERROR (Status)) {
 314         return FALSE;
 315       }
 316
 317       Status = PopBool (&Operator2);
 318       if (EFI_ERROR (Status)) {
 319         return FALSE;
 320       }
 321
 322       Status = PushBool ((BOOLEAN)(Operator && Operator2));
 323       if (EFI_ERROR (Status)) {
 324         return FALSE;
 325       }
 326       break;
 327
 328     case EFI_DEP_OR:
 329       Status = PopBool (&Operator);
 330       if (EFI_ERROR (Status)) {
 331         return FALSE;
 332       }
 333
 334       Status = PopBool (&Operator2);
 335       if (EFI_ERROR (Status)) {
 336         return FALSE;
 337       }
 338
 339       Status = PushBool ((BOOLEAN)(Operator || Operator2));
 340       if (EFI_ERROR (Status)) {
 341         return FALSE;
 342       }
 343       break;
 344
 345     case EFI_DEP_NOT:
 346       Status = PopBool (&Operator);
 347       if (EFI_ERROR (Status)) {
 348         return FALSE;
 349       }
 350
 351       Status = PushBool ((BOOLEAN)(!Operator));
 352       if (EFI_ERROR (Status)) {
 353         return FALSE;
 354       }
 355       break;
 356
 357     case EFI_DEP_TRUE:
 358       Status = PushBool (TRUE);
 359       if (EFI_ERROR (Status)) {
 360         return FALSE;
 361       }
 362       break;
 363
 364     case EFI_DEP_FALSE:
 365       Status = PushBool (FALSE);
 366       if (EFI_ERROR (Status)) {
 367         return FALSE;
 368       }
 369       break;
 370
 371     case EFI_DEP_END:
 372       Status = PopBool (&Operator);
 373       if (EFI_ERROR (Status)) {
 374         return FALSE;
 375       }
 376       return Operator;
 377
 378     case EFI_DEP_REPLACE_TRUE:
 379       Status = PushBool (TRUE);
 380       if (EFI_ERROR (Status)) {
 381         return FALSE;
 382       }
 383
 384       Iterator += sizeof (EFI_GUID);
 385       break;
 386
 387     default:
 388       goto Done;
 389     }
 390
 391     //
 392     // Skip over the Dependency Op Code we just processed in the switch.
 393     // The math is done out of order, but it should not matter. That is
 394     // we may add in the sizeof (EFI_GUID) before we account for the OP Code.
 395     // This is not an issue, since we just need the correct end result. You
 396     // need to be careful using Iterator in the loop as it's intermediate value
 397     // may be strange.
 398     //
 399     Iterator++;
 400   }
 401
 402 Done:
 403   return FALSE;
 404 }
 405
 406