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