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 KiRequestReschedule(CCHAR Processor)
  27 {
  28     PKPCR Pcr;
  29
  30     Pcr = (PKPCR)(KPCR_BASE + Processor * PAGE_SIZE);
  31     Pcr->Prcb->QuantumEnd = TRUE;
  32     KiIpiSendRequest(1 << Processor, IPI_DPC);
  33 }
  34
  35 static
  36 VOID
  37 KiInsertIntoThreadList(KPRIORITY Priority,
  38                        PKTHREAD Thread)
  39 {
  40     ASSERT(Ready == Thread->State);
  41     ASSERT(Thread->Priority == Priority);
  42
  43     if (Priority >= MAXIMUM_PRIORITY || Priority < LOW_PRIORITY) {
  44
  45         DPRINT1("Invalid thread priority (%d)\n", Priority);
  46         KEBUGCHECK(0);
  47     }
  48
  49     InsertTailList(&PriorityListHead[Priority], &Thread->WaitListEntry);
  50     PriorityListMask |= (1 << Priority);
  51 }
  52
  53 static
  54 VOID
  55 KiRemoveFromThreadList(PKTHREAD Thread)
  56 {
  57     ASSERT(Ready == Thread->State);
  58     RemoveEntryList(&Thread->WaitListEntry);
  59     if (IsListEmpty(&PriorityListHead[(ULONG)Thread->Priority])) {
  60
  61         PriorityListMask &= ~(1 << Thread->Priority);
  62     }
  63 }
  64
  65 static
  66 PKTHREAD
  67 KiScanThreadList(KPRIORITY Priority,
  68                  KAFFINITY Affinity)
  69 {
  70     PKTHREAD current;
  71     ULONG Mask;
  72
  73     Mask = (1 << Priority);
  74
  75     if (PriorityListMask & Mask) {
  76
  77         LIST_FOR_EACH(current, &PriorityListHead[Priority], KTHREAD, WaitListEntry) {
  78
  79             if (current->State != Ready) {
  80
  81                 DPRINT1("%p/%d\n", current, current->State);
  82             }
  83
  84             ASSERT(current->State == Ready);
  85
  86             if (current->Affinity & Affinity) {
  87
  88                 KiRemoveFromThreadList(current);
  89                 return(current);
  90             }
  91         }
  92     }
  93
  94     return(NULL);
  95 }
  96
  97 BOOLEAN
  98 STDCALL
  99 KiDispatchThreadNoLock(ULONG NewThreadStatus)
 100 {
 101     KPRIORITY CurrentPriority;
 102     PKTHREAD Candidate;
 103     ULONG Affinity;
 104     PKTHREAD CurrentThread = KeGetCurrentThread();
 105     BOOLEAN ApcState;
 106
 107     DPRINT("KiDispatchThreadNoLock() %d/%d/%d/%d\n", KeGetCurrentProcessorNumber(),
 108             CurrentThread, NewThreadStatus, CurrentThread->State);
 109
 110     CurrentThread->State = (UCHAR)NewThreadStatus;
 111
 112     if (NewThreadStatus == Ready) {
 113
 114         KiInsertIntoThreadList(CurrentThread->Priority,
 115                                CurrentThread);
 116     }
 117
 118     Affinity = 1 << KeGetCurrentProcessorNumber();
 119
 120     for (CurrentPriority = HIGH_PRIORITY; CurrentPriority >= LOW_PRIORITY; CurrentPriority--) {
 121
 122         Candidate = KiScanThreadList(CurrentPriority, Affinity);
 123
 124         if (Candidate == CurrentThread) {
 125
 126             Candidate->State = Running;
 127             KiReleaseDispatcherLockFromDpcLevel();
 128             return FALSE;
 129         }
 130
 131         if (Candidate != NULL) {
 132
 133             PKTHREAD OldThread;
 134             PKTHREAD IdleThread;
 135
 136             DPRINT("Scheduling %x(%d)\n",Candidate, CurrentPriority);
 137
 138             Candidate->State = Running;
 139
 140             OldThread = CurrentThread;
 141             CurrentThread = Candidate;
 142             IdleThread = KeGetCurrentPrcb()->IdleThread;
 143
 144             if (OldThread == IdleThread) {
 145
 146                 KiIdleSummary &= ~Affinity;
 147
 148             } else if (CurrentThread == IdleThread) {
 149
 150                 KiIdleSummary |= Affinity;
 151             }
 152
 153             MmUpdatePageDir((PEPROCESS)PsGetCurrentProcess(),((PETHREAD)CurrentThread)->ThreadsProcess, sizeof(EPROCESS));
 154
 155             /* Special note for Filip: This will release the Dispatcher DB Lock ;-) -- Alex */
 156             DPRINT("You are : %x, swapping to: %x.\n", OldThread, CurrentThread);
 157             KeGetCurrentPrcb()->CurrentThread = CurrentThread;
 158             ApcState = KiSwapContext(OldThread, CurrentThread);
 159             DPRINT("You are : %x, swapped from: %x\n", OldThread, CurrentThread);
 160             return ApcState;
 161         }
 162     }
 163
 164     DPRINT1("CRITICAL: No threads are ready (CPU%d)\n", KeGetCurrentProcessorNumber());
 165     KEBUGCHECK(0);
 166     return FALSE;
 167 }
 168
 169 NTSTATUS
 170 FASTCALL
 171 KiSwapThread(IN PKTHREAD CurrentThread,
 172              IN PKPRCB Prcb)
 173 {
 174     BOOLEAN ApcState;
 175     ASSERT(KeGetCurrentIrql() >= DISPATCH_LEVEL);
 176
 177     /* Find a new thread to run */
 178     ApcState = KiDispatchThreadNoLock(Waiting);
 179
 180     /* Check if we need to deliver APCs */
 181     if (ApcState)
 182     {
 183         /* Lower to APC_LEVEL */
 184         KeLowerIrql(APC_LEVEL);
 185
 186         /* Deliver APCs */
 187         KiDeliverApc(KernelMode, NULL, NULL);
 188         ASSERT(CurrentThread->WaitIrql == 0);
 189     }
 190
 191     /* Lower IRQL back to what it was */
 192     KfLowerIrql(CurrentThread->WaitIrql);
 193
 194     /* Return the wait status */
 195     return CurrentThread->WaitStatus;
 196 }
 197
 198 VOID
 199 STDCALL
 200 KiDispatchThread(ULONG NewThreadStatus)
 201 {
 202     KIRQL OldIrql;
 203
 204     if (KeGetCurrentPrcb()->IdleThread == NULL) {
 205         return;
 206     }
 207
 208     OldIrql = KiAcquireDispatcherLock();
 209     KiDispatchThreadNoLock(NewThreadStatus);
 210     KeLowerIrql(OldIrql);
 211 }
 212
 213 VOID
 214 NTAPI
 215 KiReadyThread(IN PKTHREAD Thread)
 216 {
 217     IN PKPROCESS Process = Thread->ApcState.Process;
 218
 219     /* Check if the process is paged out */
 220     if (Process->State != ProcessInMemory)
 221     {
 222         /* We don't page out processes in ROS */
 223         ASSERT(FALSE);
 224     }
 225     else if (!Thread->KernelStackResident)
 226     {
 227         /* Increase the stack count */
 228         ASSERT(Process->StackCount != MAXULONG_PTR);
 229         Process->StackCount++;
 230
 231         /* Set the thread to transition */
 232         ASSERT(Thread->State != Transition);
 233         Thread->State = Transition;
 234
 235         /* The stack is always resident in ROS */
 236         ASSERT(FALSE);
 237     }
 238     else
 239     {
 240         /* Insert the thread on the deferred ready list */
 241 #if 0
 242         KiInsertDeferredReadyList(Thread);
 243 #else
 244         /* Insert the thread into the thread list */
 245         Thread->State = Ready;
 246         KiInsertIntoThreadList(Thread->Priority, Thread);
 247 #endif
 248     }
 249 }
 250
 251 VOID
 252 STDCALL
 253 KiAdjustQuantumThread(IN PKTHREAD Thread)
 254 {
 255     KPRIORITY Priority;
 256
 257     /* Don't adjust for RT threads */
 258     if ((Thread->Priority < LOW_REALTIME_PRIORITY) &&
 259         Thread->BasePriority < LOW_REALTIME_PRIORITY - 2)
 260     {
 261         /* Decrease Quantum by one and see if we've ran out */
 262         if (--Thread->Quantum <= 0)
 263         {
 264             /* Return quantum */
 265             Thread->Quantum = Thread->QuantumReset;
 266
 267             /* Calculate new Priority */
 268             Priority = Thread->Priority - (Thread->PriorityDecrement + 1);
 269
 270             /* Normalize it if we've gone too low */
 271             if (Priority < Thread->BasePriority) Priority = Thread->BasePriority;
 272
 273             /* Reset the priority decrement, we've done it */
 274             Thread->PriorityDecrement = 0;
 275
 276             /* Set the new priority, if needed */
 277             if (Priority != Thread->Priority)
 278             {
 279                 /*
 280                  * FIXME: This should be a call to KiSetPriorityThread but
 281                  * due to the current ""scheduler"" in ROS, it can't be done
 282                  * cleanly since it actualyl dispatches threads instead.
 283                  */
 284                 Thread->Priority = (SCHAR)Priority;
 285             }
 286             else
 287             {
 288                 /* FIXME: Priority hasn't changed, find a new thread */
 289             }
 290         }
 291     }
 292
 293     /* Nothing to do... */
 294     return;
 295 }
 296
 297 VOID
 298 STDCALL
 299 KiSetPriorityThread(PKTHREAD Thread,
 300                     KPRIORITY Priority,
 301                     PBOOLEAN Released)
 302 {
 303     KPRIORITY OldPriority = Thread->Priority;
 304     ULONG Mask;
 305     int i;
 306     PKPCR Pcr;
 307     DPRINT("Changing prio to : %lx\n", Priority);
 308
 309     /* Check if priority changed */
 310     if (OldPriority != Priority)
 311     {
 312         /* Set it */
 313         Thread->Priority = (SCHAR)Priority;
 314
 315         /* Choose action based on thread's state */
 316         if (Thread->State == Ready)
 317         {
 318             /* Remove it from the current queue */
 319             KiRemoveFromThreadList(Thread);
 320
 321             /* Re-insert it at its current priority */
 322             KiInsertIntoThreadList(Priority, Thread);
 323
 324             /* Check if the old priority was lower */
 325             if (KeGetCurrentThread()->Priority < Priority)
 326             {
 327                 /* Dispatch it immediately */
 328                 KiDispatchThreadNoLock(Ready);
 329                 *Released = TRUE;
 330                 return;
 331             }
 332         }
 333         else if (Thread->State == Running)
 334         {
 335             /* Check if the new priority is lower */
 336             if (Priority < OldPriority)
 337             {
 338                 /* Check for threads with a higher priority */
 339                 Mask = ~((1 << (Priority + 1)) - 1);
 340                 if (PriorityListMask & Mask)
 341                 {
 342                     /* Found a thread, is it us? */
 343                     if (Thread == KeGetCurrentThread())
 344                     {
 345                         /* Dispatch us */
 346                         KiDispatchThreadNoLock(Ready);
 347                         *Released = TRUE;
 348                         return;
 349                     }
 350                     else
 351                     {
 352                         /* Loop every CPU */
 353                         for (i = 0; i < KeNumberProcessors; i++)
 354                         {
 355                             /* Get the PCR for this CPU */
 356                             Pcr = (PKPCR)(KPCR_BASE + i * PAGE_SIZE);
 357
 358                             /* Reschedule if the new one is already on a CPU */
 359                             if (Pcr->Prcb->CurrentThread == Thread)
 360                             {
 361                                 KiReleaseDispatcherLockFromDpcLevel();
 362                                 KiRequestReschedule(i);
 363                                 *Released = TRUE;
 364                                 return;
 365                             }
 366                         }
 367                     }
 368                 }
 369             }
 370         }
 371     }
 372
 373     /* Return to caller */
 374     *Released = FALSE;
 375     return;
 376 }
 377
 378 KAFFINITY
 379 NTAPI
 380 KiSetAffinityThread(IN PKTHREAD Thread,
 381                     IN KAFFINITY Affinity,
 382                     PBOOLEAN Released)
 383 {
 384     KAFFINITY OldAffinity;
 385     ULONG ProcessorMask;
 386     CCHAR i;
 387     PKPCR Pcr;
 388
 389     /* Make sure that the affinity is valid */
 390     if (((Affinity & Thread->ApcState.Process->Affinity) != (Affinity)) ||
 391         (!Affinity))
 392     {
 393         /* Bugcheck the system */
 394         KeBugCheck(INVALID_AFFINITY_SET);
 395     }
 396
 397     /* Get the old affinity */
 398     OldAffinity = Thread->UserAffinity;
 399
 400     Thread->UserAffinity = Affinity;
 401
 402     if (Thread->SystemAffinityActive == FALSE) {
 403
 404         Thread->Affinity = Affinity;
 405
 406         if (Thread->State == Running) {
 407
 408             ProcessorMask = 1 << KeGetCurrentProcessorNumber();
 409             if (Thread == KeGetCurrentThread()) {
 410
 411                 if (!(Affinity & ProcessorMask)) {
 412
 413                     KiDispatchThreadNoLock(Ready);
 414                     *Released = TRUE;
 415                     return OldAffinity;
 416                 }
 417
 418             } else {
 419
 420                 for (i = 0; i < KeNumberProcessors; i++) {
 421
 422                     Pcr = (PKPCR)(KPCR_BASE + i * PAGE_SIZE);
 423                     if (Pcr->Prcb->CurrentThread == Thread) {
 424
 425                         if (!(Affinity & ProcessorMask)) {
 426
 427                             KiReleaseDispatcherLockFromDpcLevel();
 428                             KiRequestReschedule(i);
 429                             *Released = TRUE;
 430                             return OldAffinity;
 431                         }
 432
 433                         break;
 434                     }
 435                 }
 436
 437                 ASSERT (i < KeNumberProcessors);
 438             }
 439         }
 440     }
 441
 442     *Released = FALSE;
 443     return OldAffinity;
 444 }
 445
 446 /*
 447  * @implemented
 448  */
 449 NTSTATUS
 450 NTAPI
 451 NtYieldExecution(VOID)
 452 {
 453     //
 454     // TODO (nothing too hard, just want to test out other code)
 455     //
 456     //DPRINT1("NO YIELD PERFORMED! If you see this, contact Alex\n");
 457     //return STATUS_NO_YIELD_PERFORMED;
 458     KiDispatchThread(Ready);
 459     return STATUS_SUCCESS;
 460 }
 461