reactos/ntoskrnl/ke/thrdschd.c

   1 /*
   2  * PROJECT:         ReactOS Kernel
   3  * LICENSE:         GPL - See COPYING in the top level directory
   4  * FILE:            ntoskrnl/ke/thrdschd.c
   5  * PURPOSE:         Kernel Thread Scheduler (Affinity, Priority, Scheduling)
   6  * PROGRAMMERS:     Alex Ionescu (alex.ionescu@reactos.org)
   7  */
   8
   9 /* INCLUDES ******************************************************************/
  10
  11 #include <ntoskrnl.h>
  12 #define NDEBUG
  13 #include <debug.h>
  14
  15 /* GLOBALS *******************************************************************/
  16
  17 LIST_ENTRY PriorityListHead[MAXIMUM_PRIORITY];
  18 ULONG PriorityListMask = 0;
  19 ULONG KiIdleSummary;
  20 ULONG KiIdleSMTSummary;
  21
  22 /* FUNCTIONS *****************************************************************/
  23
  24 static
  25 VOID
  26 KiInsertIntoThreadList(KPRIORITY Priority,
  27                        PKTHREAD Thread)
  28 {
  29     ASSERT(Ready == Thread->State);
  30     ASSERT(Thread->Priority == Priority);
  31
  32     if (Priority >= MAXIMUM_PRIORITY || Priority < LOW_PRIORITY) {
  33
  34         DPRINT1("Invalid thread priority (%d)\n", Priority);
  35         KEBUGCHECK(0);
  36     }
  37
  38     InsertTailList(&PriorityListHead[Priority], &Thread->WaitListEntry);
  39     PriorityListMask |= (1 << Priority);
  40 }
  41
  42 static
  43 VOID
  44 KiRemoveFromThreadList(PKTHREAD Thread)
  45 {
  46     ASSERT(Ready == Thread->State);
  47     RemoveEntryList(&Thread->WaitListEntry);
  48     if (IsListEmpty(&PriorityListHead[(ULONG)Thread->Priority])) {
  49
  50         PriorityListMask &= ~(1 << Thread->Priority);
  51     }
  52 }
  53
  54 static
  55 PKTHREAD
  56 KiScanThreadList(KPRIORITY Priority,
  57                  KAFFINITY Affinity)
  58 {
  59     PKTHREAD current;
  60     ULONG Mask;
  61
  62     Mask = (1 << Priority);
  63
  64     if (PriorityListMask & Mask) {
  65
  66         LIST_FOR_EACH(current, &PriorityListHead[Priority], KTHREAD, WaitListEntry) {
  67
  68             if (current->State != Ready) {
  69
  70                 DPRINT1("%p/%d\n", current, current->State);
  71             }
  72
  73             ASSERT(current->State == Ready);
  74
  75             if (current->Affinity & Affinity) {
  76
  77                 KiRemoveFromThreadList(current);
  78                 return(current);
  79             }
  80         }
  81     }
  82
  83     return(NULL);
  84 }
  85
  86 BOOLEAN
  87 STDCALL
  88 KiDispatchThreadNoLock(ULONG NewThreadStatus)
  89 {
  90     KPRIORITY CurrentPriority;
  91     PKTHREAD Candidate;
  92     ULONG Affinity;
  93     PKTHREAD CurrentThread = KeGetCurrentThread();
  94     BOOLEAN ApcState;
  95
  96     DPRINT("KiDispatchThreadNoLock() %d/%d/%d/%d\n", KeGetCurrentProcessorNumber(),
  97             CurrentThread, NewThreadStatus, CurrentThread->State);
  98
  99     CurrentThread->State = (UCHAR)NewThreadStatus;
 100
 101     if (NewThreadStatus == Ready) {
 102
 103         KiInsertIntoThreadList(CurrentThread->Priority,
 104                                CurrentThread);
 105     }
 106
 107     Affinity = 1 << KeGetCurrentProcessorNumber();
 108
 109     for (CurrentPriority = HIGH_PRIORITY; CurrentPriority >= LOW_PRIORITY; CurrentPriority--) {
 110
 111         Candidate = KiScanThreadList(CurrentPriority, Affinity);
 112
 113         if (Candidate == CurrentThread) {
 114
 115             Candidate->State = Running;
 116             KiReleaseDispatcherLockFromDpcLevel();
 117             return FALSE;
 118         }
 119
 120         if (Candidate != NULL) {
 121
 122             PKTHREAD OldThread;
 123             PKTHREAD IdleThread;
 124
 125             DPRINT("Scheduling %x(%d)\n",Candidate, CurrentPriority);
 126
 127             Candidate->State = Running;
 128
 129             OldThread = CurrentThread;
 130             CurrentThread = Candidate;
 131             IdleThread = KeGetCurrentPrcb()->IdleThread;
 132
 133             if (OldThread == IdleThread) {
 134
 135                 KiIdleSummary &= ~Affinity;
 136
 137             } else if (CurrentThread == IdleThread) {
 138
 139                 KiIdleSummary |= Affinity;
 140             }
 141
 142             MmUpdatePageDir((PEPROCESS)PsGetCurrentProcess(),((PETHREAD)CurrentThread)->ThreadsProcess, sizeof(EPROCESS));
 143
 144             /* Special note for Filip: This will release the Dispatcher DB Lock ;-) -- Alex */
 145             DPRINT("You are : %x, swapping to: %x.\n", OldThread, CurrentThread);
 146             KeGetCurrentPrcb()->CurrentThread = CurrentThread;
 147             ApcState = KiSwapContext(OldThread, CurrentThread);
 148             DPRINT("You are : %x, swapped from: %x\n", OldThread, CurrentThread);
 149             return ApcState;
 150         }
 151     }
 152
 153     DPRINT1("CRITICAL: No threads are ready (CPU%d)\n", KeGetCurrentProcessorNumber());
 154     KEBUGCHECK(0);
 155     return FALSE;
 156 }
 157
 158 VOID
 159 NTAPI
 160 KiDeferredReadyThread(IN PKTHREAD Thread)
 161 {
 162     /* FIXME: Not yet implemented */
 163     KEBUGCHECK(0);
 164 }
 165
 166 PKTHREAD
 167 FASTCALL
 168 KiSelectNextThread(IN PKPRCB Prcb)
 169 {
 170     PKTHREAD Thread;
 171
 172     /* Select a ready thread */
 173     Thread = KiSelectReadyThread(0, Prcb);
 174     if (!Thread)
 175     {
 176         /* Didn't find any, get the current idle thread */
 177         Thread = Prcb->IdleThread;
 178
 179         /* Enable idle scheduling */
 180         InterlockedOr(&KiIdleSummary, Prcb->SetMember);
 181         Prcb->IdleSchedule = TRUE;
 182
 183         /* FIXME: SMT support */
 184     }
 185
 186     /* Sanity checks and return the thread */
 187     ASSERT(Thread != NULL);
 188     ASSERT((Thread->BasePriority == 0) || (Thread->Priority != 0));
 189     return Thread;
 190 }
 191
 192 NTSTATUS
 193 FASTCALL
 194 KiSwapThread(IN PKTHREAD CurrentThread,
 195              IN PKPRCB Prcb)
 196 {
 197     BOOLEAN ApcState;
 198     ASSERT(KeGetCurrentIrql() >= DISPATCH_LEVEL);
 199
 200 #ifdef NEW_SCHEDULER
 201
 202 #else
 203     /* Find a new thread to run */
 204     ApcState = KiDispatchThreadNoLock(Waiting);
 205 #endif
 206
 207     /* Check if we need to deliver APCs */
 208     if (ApcState)
 209     {
 210         /* Lower to APC_LEVEL */
 211         KeLowerIrql(APC_LEVEL);
 212
 213         /* Deliver APCs */
 214         KiDeliverApc(KernelMode, NULL, NULL);
 215         ASSERT(CurrentThread->WaitIrql == 0);
 216     }
 217
 218     /* Lower IRQL back to what it was */
 219     KfLowerIrql(CurrentThread->WaitIrql);
 220
 221     /* Return the wait status */
 222     return CurrentThread->WaitStatus;
 223 }
 224
 225 VOID
 226 STDCALL
 227 KiDispatchThread(ULONG NewThreadStatus)
 228 {
 229     KIRQL OldIrql;
 230
 231     if (KeGetCurrentPrcb()->IdleThread == NULL) {
 232         return;
 233     }
 234
 235     OldIrql = KiAcquireDispatcherLock();
 236     KiDispatchThreadNoLock(NewThreadStatus);
 237     KeLowerIrql(OldIrql);
 238 }
 239
 240 VOID
 241 NTAPI
 242 KiReadyThread(IN PKTHREAD Thread)
 243 {
 244     IN PKPROCESS Process = Thread->ApcState.Process;
 245
 246     /* Check if the process is paged out */
 247     if (Process->State != ProcessInMemory)
 248     {
 249         /* We don't page out processes in ROS */
 250         ASSERT(FALSE);
 251     }
 252     else if (!Thread->KernelStackResident)
 253     {
 254         /* Increase the stack count */
 255         ASSERT(Process->StackCount != MAXULONG_PTR);
 256         Process->StackCount++;
 257
 258         /* Set the thread to transition */
 259         ASSERT(Thread->State != Transition);
 260         Thread->State = Transition;
 261
 262         /* The stack is always resident in ROS */
 263         ASSERT(FALSE);
 264     }
 265     else
 266     {
 267         /* Insert the thread on the deferred ready list */
 268 #ifdef NEW_SCHEDULER
 269         KiInsertDeferredReadyList(Thread);
 270 #else
 271         /* Insert the thread into the thread list */
 272         Thread->State = Ready;
 273         KiInsertIntoThreadList(Thread->Priority, Thread);
 274 #endif
 275     }
 276 }
 277
 278 VOID
 279 NTAPI
 280 KiAdjustQuantumThread(IN PKTHREAD Thread)
 281 {
 282     PKPRCB Prcb = KeGetCurrentPrcb();
 283
 284     /* Acquire thread and PRCB lock */
 285     KiAcquireThreadLock(Thread);
 286     KiAcquirePrcbLock(Prcb);
 287
 288     /* Don't adjust for RT threads */
 289     if ((Thread->Priority < LOW_REALTIME_PRIORITY) &&
 290         (Thread->BasePriority < (LOW_REALTIME_PRIORITY - 2)))
 291     {
 292         /* Decrease Quantum by one and see if we've ran out */
 293         if (--Thread->Quantum <= 0)
 294         {
 295             /* Return quantum */
 296             Thread->Quantum = Thread->QuantumReset;
 297
 298             /* Calculate new Priority */
 299             Thread->Priority = KiComputeNewPriority(Thread, 1);
 300
 301 #ifdef NEW_SCHEDULER
 302             /* Check if there's no next thread scheduled */
 303             if (!Prcb->NextThread)
 304             {
 305                 /* Select a ready thread and check if we found one */
 306                 NextThread = KiSelectReadyThread(Thread->Priority, Prcb);
 307                 if (NextThread)
 308                 {
 309                     /* Set it on standby and switch to it */
 310                     NextThread->State = Standby;
 311                     Prcb->NextThread = NextThread;
 312                 }
 313             }
 314             else
 315             {
 316                 /* This thread can be preempted again */
 317                 Thread->Preempted = FALSE;
 318             }
 319 #else
 320             /* We need to dispatch a new thread */
 321             KiDispatchThread(Ready);
 322 #endif
 323         }
 324     }
 325
 326     /* Release locks */
 327     KiReleasePrcbLock(Prcb);
 328     KiReleaseThreadLock(Thread);
 329 }
 330
 331 VOID
 332 STDCALL
 333 KiSetPriorityThread(IN PKTHREAD Thread,
 334                     IN KPRIORITY Priority,
 335                     OUT PBOOLEAN Released)
 336 {
 337     PKPRCB Prcb;
 338     ULONG Processor;
 339     BOOLEAN RequestInterrupt = FALSE;
 340     KPRIORITY OldPriority;
 341     PKTHREAD NewThread;
 342     ASSERT((Priority >= 0) && (Priority <= HIGH_PRIORITY));
 343
 344     /* Check if priority changed */
 345     if (Thread->Priority != Priority)
 346     {
 347         /* Loop priority setting in case we need to start over */
 348         for (;;)
 349         {
 350             /* Choose action based on thread's state */
 351             if (Thread->State == Ready)
 352             {
 353                 /* Make sure we're not on the ready queue */
 354                 if (Thread->ProcessReadyQueue)
 355                 {
 356                     /* Get the PRCB for the thread and lock it */
 357                     Processor = Thread->NextProcessor;
 358                     Prcb = KiProcessorBlock[Processor];
 359                     KiAcquirePrcbLock(Prcb);
 360
 361                     /* Make sure the thread is still ready and on this CPU */
 362                     if ((Thread->State == Ready) &&
 363                         (Thread->NextProcessor == Prcb->Number))
 364                     {
 365                         /* Sanity check */
 366                         ASSERT((Prcb->ReadySummary &
 367                                 PRIORITY_MASK(Thread->Priority)));
 368
 369                         /* Remove it from the current queue */
 370 #ifdef NEW_SCHEDULER
 371                         if (RemoveEntryList(&Thread->WaitListEntry))
 372                         {
 373                             /* Update the ready summary */
 374                             Prcb->ReadySummary ^= PRIORITY_MASK(Thread->Priority);
 375                         }
 376 #else
 377                         KiRemoveFromThreadList(Thread);
 378 #endif
 379
 380                         /* Update priority */
 381                         Thread->Priority = (SCHAR)Priority;
 382
 383                         /* Re-insert it at its current priority */
 384 #ifndef NEW_SCHEDULER
 385                         KiInsertIntoThreadList(Priority, Thread);
 386                         KiDispatchThreadNoLock(Ready);
 387                         *Released = TRUE;
 388 #else
 389                         KiInsertDeferredReadyList(Thread);
 390 #endif
 391
 392                         /* Release the PRCB Lock */
 393                         KiReleasePrcbLock(Prcb);
 394                     }
 395                     else
 396                     {
 397                         /* Release the lock and loop again */
 398                         KEBUGCHECK(0);
 399                         KiReleasePrcbLock(Prcb);
 400                         continue;
 401                     }
 402                 }
 403                 else
 404                 {
 405                     /* It's already on the ready queue, just update priority */
 406                     Thread->Priority = (SCHAR)Priority;
 407                 }
 408             }
 409             else if (Thread->State == Standby)
 410             {
 411                 /* Get the PRCB for the thread and lock it */
 412                 KEBUGCHECK(0);
 413                 Processor = Thread->NextProcessor;
 414                 Prcb = KiProcessorBlock[Processor];
 415                 KiAcquirePrcbLock(Prcb);
 416
 417                 /* Check if we're still the next thread to run */
 418                 if (Thread == Prcb->NextThread)
 419                 {
 420                     /* Get the old priority and update ours */
 421                     OldPriority = Thread->Priority;
 422                     Thread->Priority = (SCHAR)Priority;
 423
 424                     /* Check if there was a change */
 425                     if (Priority < OldPriority)
 426                     {
 427                         /* Find a new thread */
 428                         NewThread = KiSelectReadyThread(Priority + 1, Prcb);
 429                         if (NewThread)
 430                         {
 431                             /* Found a new one, set it on standby */
 432                             NewThread->State = Standby;
 433                             Prcb->NextThread = NewThread;
 434
 435                             /* Dispatch our thread */
 436                             KiInsertDeferredReadyList(Thread);
 437                         }
 438                     }
 439
 440                     /* Release the PRCB lock */
 441                     KiReleasePrcbLock(Prcb);
 442                 }
 443                 else
 444                 {
 445                     /* Release the lock and try again */
 446                     KiReleasePrcbLock(Prcb);
 447                     continue;
 448                 }
 449             }
 450             else if (Thread->State == Running)
 451             {
 452                 /* Get the PRCB for the thread and lock it */
 453                 Processor = Thread->NextProcessor;
 454                 Prcb = KiProcessorBlock[Processor];
 455                 KiAcquirePrcbLock(Prcb);
 456
 457                 /* Check if we're still the current thread running */
 458                 if (Thread == Prcb->CurrentThread)
 459                 {
 460                     /* Get the old priority and update ours */
 461                     OldPriority = Thread->Priority;
 462                     Thread->Priority = (SCHAR)Priority;
 463
 464                     /* Check if there was a change and there's no new thread */
 465                     if ((Priority < OldPriority) && !(Prcb->NextThread))
 466                     {
 467 #ifdef NEW_SCHEDULER
 468                         /* Find a new thread */
 469                         NewThread = KiSelectReadyThread(Priority + 1, Prcb);
 470                         if (NewThread)
 471                         {
 472                             /* Found a new one, set it on standby */
 473                             NewThread->State = Standby;
 474                             Prcb->NextThread = NewThread;
 475
 476                             /* Request an interrupt */
 477                             RequestInterrupt = TRUE;
 478                         }
 479 #else
 480                         /* Check for threads with a higher priority */
 481                         if (PriorityListMask & ~((1 << (Priority + 1)) - 1))
 482                         {
 483                             /* Found a thread, is it us? */
 484                             if (Thread == KeGetCurrentThread())
 485                             {
 486                                 /* Dispatch us */
 487                                 KiDispatchThreadNoLock(Ready);
 488                                 *Released = TRUE;
 489                                 return;
 490                             }
 491                         }
 492 #endif
 493                     }
 494
 495                     /* Release the lock and check if we need an interrupt */
 496                     KiReleasePrcbLock(Prcb);
 497                     if (RequestInterrupt)
 498                     {
 499                         /* Check if we're running on another CPU */
 500                         if (KeGetCurrentProcessorNumber() != Processor)
 501                         {
 502                             /* We are, send an IPI */
 503                             KiIpiSendRequest(AFFINITY_MASK(Processor), IPI_DPC);
 504                         }
 505                     }
 506                 }
 507                 else
 508                 {
 509                     /* Thread changed, release lock and restart */
 510                     KiReleasePrcbLock(Prcb);
 511                     continue;
 512                 }
 513             }
 514             else if (Thread->State == DeferredReady)
 515             {
 516                 /* FIXME: TODO */
 517                 DPRINT1("Deferred state not yet supported\n");
 518                 KEBUGCHECK(0);
 519             }
 520             else
 521             {
 522                 /* Any other state, just change priority */
 523                 Thread->Priority = (SCHAR)Priority;
 524             }
 525
 526             /* If we got here, then thread state was consistent, so bail out */
 527             break;
 528         }
 529     }
 530
 531     /* Return to caller */
 532     *Released = FALSE;
 533 }
 534
 535 KAFFINITY
 536 FASTCALL
 537 KiSetAffinityThread(IN PKTHREAD Thread,
 538                     IN KAFFINITY Affinity)
 539 {
 540     KAFFINITY OldAffinity;
 541
 542     /* Get the current affinity */
 543     OldAffinity = Thread->UserAffinity;
 544
 545     /* Make sure that the affinity is valid */
 546     if (((Affinity & Thread->ApcState.Process->Affinity) != (Affinity)) ||
 547         (!Affinity))
 548     {
 549         /* Bugcheck the system */
 550         KeBugCheck(INVALID_AFFINITY_SET);
 551     }
 552
 553     /* Update the new affinity */
 554     Thread->UserAffinity = Affinity;
 555
 556     /* Check if system affinity is disabled */
 557     if (!Thread->SystemAffinityActive)
 558     {
 559         /* FIXME: TODO */
 560         DPRINT1("Affinity support disabled!\n");
 561     }
 562
 563     /* Return the old affinity */
 564     return OldAffinity;
 565 }
 566
 567 /*
 568  * @implemented
 569  */
 570 NTSTATUS
 571 NTAPI
 572 NtYieldExecution(VOID)
 573 {
 574     //
 575     // TODO (nothing too hard, just want to test out other code)
 576     //
 577     //DPRINT1("NO YIELD PERFORMED! If you see this, contact Alex\n");
 578     //return STATUS_NO_YIELD_PERFORMED;
 579     KiDispatchThread(Ready);
 580     return STATUS_SUCCESS;
 581 }
 582
 583