MdeModulePkg/Core/Dxe/Dispatcher/dependency.c

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