src/system/kernel/scheduler/scheduler_cpu.h

   1 /*
   2  * Copyright 2013, Paweł Dziepak, pdziepak@quarnos.org.
   3  * Distributed under the terms of the MIT License.
   4  */
   5 #ifndef KERNEL_SCHEDULER_CPU_H
   6 #define KERNEL_SCHEDULER_CPU_H
   7
   8
   9 #include <OS.h>
  10
  11 #include <thread.h>
  12 #include <util/AutoLock.h>
  13 #include <util/Heap.h>
  14 #include <util/MinMaxHeap.h>
  15
  16 #include <cpufreq.h>
  17
  18 #include "RunQueue.h"
  19 #include "scheduler_common.h"
  20 #include "scheduler_modes.h"
  21 #include "scheduler_profiler.h"
  22
  23
  24 namespace Scheduler {
  25
  26
  27 class DebugDumper;
  28
  29 struct ThreadData;
  30 class ThreadProcessing;
  31
  32 struct CPUEntry;
  33 struct CoreEntry;
  34 struct PackageEntry;
  35
  36 // The run queues. Holds the threads ready to run ordered by priority.
  37 // One queue per schedulable target per core. Additionally, each
  38 // logical processor has its sPinnedRunQueues used for scheduling
  39 // pinned threads.
  40 class ThreadRunQueue : public RunQueue<ThreadData, THREAD_MAX_SET_PRIORITY> {
  41 public:
  42                                                 void                    Dump() const;
  43 };
  44
  45 class CPUEntry : public HeapLinkImpl<CPUEntry, int32> {
  46 public:
  47                                                                                 CPUEntry();
  48
  49                                                 void                    Init(int32 id, CoreEntry* core);
  50
  51         inline                          int32                   ID() const      { return fCPUNumber; }
  52         inline                          CoreEntry*              Core() const    { return fCore; }
  53
  54                                                 void                    Start();
  55                                                 void                    Stop();
  56
  57         inline                          void                    EnterScheduler();
  58         inline                          void                    ExitScheduler();
  59
  60         inline                          void                    LockScheduler();
  61         inline                          void                    UnlockScheduler();
  62
  63         inline                          void                    LockRunQueue();
  64         inline                          void                    UnlockRunQueue();
  65
  66                                                 void                    PushFront(ThreadData* thread,
  67                                                                                         int32 priority);
  68                                                 void                    PushBack(ThreadData* thread,
  69                                                                                         int32 priority);
  70                                                 void                    Remove(ThreadData* thread);
  71         inline                          ThreadData*             PeekThread() const;
  72                                                 ThreadData*             PeekIdleThread() const;
  73
  74                                                 void                    UpdatePriority(int32 priority);
  75
  76         inline                          int32                   GetLoad() const { return fLoad; }
  77                                                 void                    ComputeLoad();
  78
  79                                                 ThreadData*             ChooseNextThread(ThreadData* oldThread,
  80                                                                                         bool putAtBack);
  81
  82                                                 void                    TrackActivity(ThreadData* oldThreadData,
  83                                                                                         ThreadData* nextThreadData);
  84
  85                                                 void                    StartQuantumTimer(ThreadData* thread,
  86                                                                                         bool wasPreempted);
  87
  88         static inline           CPUEntry*               GetCPU(int32 cpu);
  89
  90 private:
  91                                                 void                    _RequestPerformanceLevel(
  92                                                                                         ThreadData* threadData);
  93
  94         static                          int32                   _RescheduleEvent(timer* /* unused */);
  95         static                          int32                   _UpdateLoadEvent(timer* /* unused */);
  96
  97                                                 int32                   fCPUNumber;
  98                                                 CoreEntry*              fCore;
  99
 100                                                 rw_spinlock     fSchedulerModeLock;
 101
 102                                                 ThreadRunQueue  fRunQueue;
 103                                                 spinlock                fQueueLock;
 104
 105                                                 int32                   fLoad;
 106
 107                                                 bigtime_t               fMeasureActiveTime;
 108                                                 bigtime_t               fMeasureTime;
 109
 110                                                 bool                    fUpdateLoadEvent;
 111
 112                                                 friend class DebugDumper;
 113 } CACHE_LINE_ALIGN;
 114
 115 class CPUPriorityHeap : public Heap<CPUEntry, int32> {
 116 public:
 117                                                                                 CPUPriorityHeap() { }
 118                                                                                 CPUPriorityHeap(int32 cpuCount);
 119
 120                                                 void                    Dump();
 121 };
 122
 123 class CoreEntry : public MinMaxHeapLinkImpl<CoreEntry, int32>,
 124         public DoublyLinkedListLinkImpl<CoreEntry> {
 125 public:
 126                                                                                 CoreEntry();
 127
 128                                                 void                    Init(int32 id, PackageEntry* package);
 129
 130         inline                          int32                   ID() const      { return fCoreID; }
 131         inline                          PackageEntry*   Package() const { return fPackage; }
 132         inline                          int32                   CPUCount() const
 133                                                                                         { return fCPUCount; }
 134
 135         inline                          void                    LockCPUHeap();
 136         inline                          void                    UnlockCPUHeap();
 137
 138         inline                          CPUPriorityHeap*        CPUHeap();
 139
 140         inline                          int32                   ThreadCount() const;
 141
 142         inline                          void                    LockRunQueue();
 143         inline                          void                    UnlockRunQueue();
 144
 145                                                 void                    PushFront(ThreadData* thread,
 146                                                                                         int32 priority);
 147                                                 void                    PushBack(ThreadData* thread,
 148                                                                                         int32 priority);
 149                                                 void                    Remove(ThreadData* thread);
 150         inline                          ThreadData*             PeekThread() const;
 151
 152         inline                          bigtime_t               GetActiveTime() const;
 153         inline                          void                    IncreaseActiveTime(
 154                                                                                         bigtime_t activeTime);
 155
 156         inline                          int32                   GetLoad() const;
 157         inline                          uint32                  LoadMeasurementEpoch() const
 158                                                                                         { return fLoadMeasurementEpoch; }
 159
 160         inline                          void                    AddLoad(int32 load, uint32 epoch,
 161                                                                                         bool updateLoad);
 162         inline                          uint32                  RemoveLoad(int32 load, bool force);
 163         inline                          void                    ChangeLoad(int32 delta);
 164
 165         inline                          void                    CPUGoesIdle(CPUEntry* cpu);
 166         inline                          void                    CPUWakesUp(CPUEntry* cpu);
 167
 168                                                 void                    AddCPU(CPUEntry* cpu);
 169                                                 void                    RemoveCPU(CPUEntry* cpu,
 170                                                                                         ThreadProcessing&
 171                                                                                                 threadPostProcessing);
 172
 173         static inline           CoreEntry*              GetCore(int32 cpu);
 174
 175 private:
 176                                                 void                    _UpdateLoad(bool forceUpdate = false);
 177
 178         static                          void                    _UnassignThread(Thread* thread,
 179                                                                                         void* core);
 180
 181                                                 int32                   fCoreID;
 182                                                 PackageEntry*   fPackage;
 183
 184                                                 int32                   fCPUCount;
 185                                                 int32                   fIdleCPUCount;
 186                                                 CPUPriorityHeap fCPUHeap;
 187                                                 spinlock                fCPULock;
 188
 189                                                 int32                   fThreadCount;
 190                                                 ThreadRunQueue  fRunQueue;
 191                                                 spinlock                fQueueLock;
 192
 193                                                 bigtime_t               fActiveTime;
 194         mutable                         seqlock                 fActiveTimeLock;
 195
 196                                                 int32                   fLoad;
 197                                                 int32                   fCurrentLoad;
 198                                                 uint32                  fLoadMeasurementEpoch;
 199                                                 bool                    fHighLoad;
 200                                                 bigtime_t               fLastLoadUpdate;
 201                                                 rw_spinlock             fLoadLock;
 202
 203                                                 friend class DebugDumper;
 204 } CACHE_LINE_ALIGN;
 205
 206 class CoreLoadHeap : public MinMaxHeap<CoreEntry, int32> {
 207 public:
 208                                                                                 CoreLoadHeap() { }
 209                                                                                 CoreLoadHeap(int32 coreCount);
 210
 211                                                 void                    Dump();
 212 };
 213
 214 // gPackageEntries are used to decide which core should be woken up from the
 215 // idle state. When aiming for performance we should use as many packages as
 216 // possible with as little cores active in each package as possible (so that the
 217 // package can enter any boost mode if it has one and the active core have more
 218 // of the shared cache for themselves. If power saving is the main priority we
 219 // should keep active cores on as little packages as possible (so that other
 220 // packages can go to the deep state of sleep). The heap stores only packages
 221 // with at least one core active and one core idle. The packages with all cores
 222 // idle are stored in gPackageIdleList (in LIFO manner).
 223 class PackageEntry : public DoublyLinkedListLinkImpl<PackageEntry> {
 224 public:
 225                                                                                         PackageEntry();
 226
 227                                                 void                            Init(int32 id);
 228
 229         inline                          void                            CoreGoesIdle(CoreEntry* core);
 230         inline                          void                            CoreWakesUp(CoreEntry* core);
 231
 232         inline                          CoreEntry*                      GetIdleCore() const;
 233
 234                                                 void                            AddIdleCore(CoreEntry* core);
 235                                                 void                            RemoveIdleCore(CoreEntry* core);
 236
 237         static inline           PackageEntry*           GetMostIdlePackage();
 238         static inline           PackageEntry*           GetLeastIdlePackage();
 239
 240 private:
 241                                                 int32                           fPackageID;
 242
 243                                                 DoublyLinkedList<CoreEntry>     fIdleCores;
 244                                                 int32                           fIdleCoreCount;
 245                                                 int32                           fCoreCount;
 246                                                 rw_spinlock                     fCoreLock;
 247
 248                                                 friend class DebugDumper;
 249 } CACHE_LINE_ALIGN;
 250 typedef DoublyLinkedList<PackageEntry> IdlePackageList;
 251
 252 extern CPUEntry* gCPUEntries;
 253
 254 extern CoreEntry* gCoreEntries;
 255 extern CoreLoadHeap gCoreLoadHeap;
 256 extern CoreLoadHeap gCoreHighLoadHeap;
 257 extern rw_spinlock gCoreHeapsLock;
 258 extern int32 gCoreCount;
 259
 260 extern PackageEntry* gPackageEntries;
 261 extern IdlePackageList gIdlePackageList;
 262 extern rw_spinlock gIdlePackageLock;
 263 extern int32 gPackageCount;
 264
 265
 266 inline void
 267 CPUEntry::EnterScheduler()
 268 {
 269         SCHEDULER_ENTER_FUNCTION();
 270         acquire_read_spinlock(&fSchedulerModeLock);
 271 }
 272
 273
 274 inline void
 275 CPUEntry::ExitScheduler()
 276 {
 277         SCHEDULER_ENTER_FUNCTION();
 278         release_read_spinlock(&fSchedulerModeLock);
 279 }
 280
 281
 282 inline void
 283 CPUEntry::LockScheduler()
 284 {
 285         SCHEDULER_ENTER_FUNCTION();
 286         acquire_write_spinlock(&fSchedulerModeLock);
 287 }
 288
 289
 290 inline void
 291 CPUEntry::UnlockScheduler()
 292 {
 293         SCHEDULER_ENTER_FUNCTION();
 294         release_write_spinlock(&fSchedulerModeLock);
 295 }
 296
 297
 298 inline void
 299 CPUEntry::LockRunQueue()
 300 {
 301         SCHEDULER_ENTER_FUNCTION();
 302         acquire_spinlock(&fQueueLock);
 303 }
 304
 305
 306 inline void
 307 CPUEntry::UnlockRunQueue()
 308 {
 309         SCHEDULER_ENTER_FUNCTION();
 310         release_spinlock(&fQueueLock);
 311 }
 312
 313
 314 /* static */ inline CPUEntry*
 315 CPUEntry::GetCPU(int32 cpu)
 316 {
 317         SCHEDULER_ENTER_FUNCTION();
 318         return &gCPUEntries[cpu];
 319 }
 320
 321
 322 inline void
 323 CoreEntry::LockCPUHeap()
 324 {
 325         SCHEDULER_ENTER_FUNCTION();
 326         acquire_spinlock(&fCPULock);
 327 }
 328
 329
 330 inline void
 331 CoreEntry::UnlockCPUHeap()
 332 {
 333         SCHEDULER_ENTER_FUNCTION();
 334         release_spinlock(&fCPULock);
 335 }
 336
 337
 338 inline CPUPriorityHeap*
 339 CoreEntry::CPUHeap()
 340 {
 341         SCHEDULER_ENTER_FUNCTION();
 342         return &fCPUHeap;
 343 }
 344
 345
 346 inline int32
 347 CoreEntry::ThreadCount() const
 348 {
 349         SCHEDULER_ENTER_FUNCTION();
 350         return fThreadCount + fCPUCount - fIdleCPUCount;
 351 }
 352
 353
 354 inline void
 355 CoreEntry::LockRunQueue()
 356 {
 357         SCHEDULER_ENTER_FUNCTION();
 358         acquire_spinlock(&fQueueLock);
 359 }
 360
 361
 362 inline void
 363 CoreEntry::UnlockRunQueue()
 364 {
 365         SCHEDULER_ENTER_FUNCTION();
 366         release_spinlock(&fQueueLock);
 367 }
 368
 369
 370 inline void
 371 CoreEntry::IncreaseActiveTime(bigtime_t activeTime)
 372 {
 373         SCHEDULER_ENTER_FUNCTION();
 374         WriteSequentialLocker _(fActiveTimeLock);
 375         fActiveTime += activeTime;
 376 }
 377
 378
 379 inline bigtime_t
 380 CoreEntry::GetActiveTime() const
 381 {
 382         SCHEDULER_ENTER_FUNCTION();
 383
 384         bigtime_t activeTime;
 385         uint32 count;
 386         do {
 387                 count = acquire_read_seqlock(&fActiveTimeLock);
 388                 activeTime = fActiveTime;
 389         } while (!release_read_seqlock(&fActiveTimeLock, count));
 390         return activeTime;
 391 }
 392
 393
 394 inline int32
 395 CoreEntry::GetLoad() const
 396 {
 397         SCHEDULER_ENTER_FUNCTION();
 398
 399         ASSERT(fCPUCount > 0);
 400         return fLoad / fCPUCount;
 401 }
 402
 403
 404 inline void
 405 CoreEntry::AddLoad(int32 load, uint32 epoch, bool updateLoad)
 406 {
 407         SCHEDULER_ENTER_FUNCTION();
 408
 409         ASSERT(gTrackCoreLoad);
 410         ASSERT(load >= 0 && load <= kMaxLoad);
 411
 412         ReadSpinLocker locker(fLoadLock);
 413         atomic_add(&fCurrentLoad, load);
 414         if (fLoadMeasurementEpoch != epoch)
 415                 atomic_add(&fLoad, load);
 416         locker.Unlock();
 417
 418         if (updateLoad)
 419                 _UpdateLoad(true);
 420 }
 421
 422
 423 inline uint32
 424 CoreEntry::RemoveLoad(int32 load, bool force)
 425 {
 426         SCHEDULER_ENTER_FUNCTION();
 427
 428         ASSERT(gTrackCoreLoad);
 429         ASSERT(load >= 0 && load <= kMaxLoad);
 430
 431         ReadSpinLocker locker(fLoadLock);
 432         atomic_add(&fCurrentLoad, -load);
 433         if (force) {
 434                 atomic_add(&fLoad, -load);
 435                 locker.Unlock();
 436
 437                 _UpdateLoad(true);
 438         }
 439         return fLoadMeasurementEpoch;
 440 }
 441
 442
 443 inline void
 444 CoreEntry::ChangeLoad(int32 delta)
 445 {
 446         SCHEDULER_ENTER_FUNCTION();
 447
 448         ASSERT(gTrackCoreLoad);
 449         ASSERT(delta >= -kMaxLoad && delta <= kMaxLoad);
 450
 451         if (delta != 0) {
 452                 ReadSpinLocker locker(fLoadLock);
 453                 atomic_add(&fCurrentLoad, delta);
 454                 atomic_add(&fLoad, delta);
 455         }
 456
 457         _UpdateLoad();
 458 }
 459
 460
 461 /* PackageEntry::CoreGoesIdle and PackageEntry::CoreWakesUp have to be defined
 462    before CoreEntry::CPUGoesIdle and CoreEntry::CPUWakesUp. If they weren't
 463    GCC2 wouldn't inline them as, apparently, it doesn't do enough optimization
 464    passes.
 465 */
 466 inline void
 467 PackageEntry::CoreGoesIdle(CoreEntry* core)
 468 {
 469         SCHEDULER_ENTER_FUNCTION();
 470
 471         WriteSpinLocker _(fCoreLock);
 472
 473         ASSERT(fIdleCoreCount >= 0);
 474         ASSERT(fIdleCoreCount < fCoreCount);
 475
 476         fIdleCoreCount++;
 477         fIdleCores.Add(core);
 478
 479         if (fIdleCoreCount == fCoreCount) {
 480                 // package goes idle
 481                 WriteSpinLocker _(gIdlePackageLock);
 482                 gIdlePackageList.Add(this);
 483         }
 484 }
 485
 486
 487 inline void
 488 PackageEntry::CoreWakesUp(CoreEntry* core)
 489 {
 490         SCHEDULER_ENTER_FUNCTION();
 491
 492         WriteSpinLocker _(fCoreLock);
 493
 494         ASSERT(fIdleCoreCount > 0);
 495         ASSERT(fIdleCoreCount <= fCoreCount);
 496
 497         fIdleCoreCount--;
 498         fIdleCores.Remove(core);
 499
 500         if (fIdleCoreCount + 1 == fCoreCount) {
 501                 // package wakes up
 502                 WriteSpinLocker _(gIdlePackageLock);
 503                 gIdlePackageList.Remove(this);
 504         }
 505 }
 506
 507
 508 inline void
 509 CoreEntry::CPUGoesIdle(CPUEntry* /* cpu */)
 510 {
 511         if (gSingleCore)
 512                 return;
 513
 514         ASSERT(fIdleCPUCount < fCPUCount);
 515         if (++fIdleCPUCount == fCPUCount)
 516                 fPackage->CoreGoesIdle(this);
 517 }
 518
 519
 520 inline void
 521 CoreEntry::CPUWakesUp(CPUEntry* /* cpu */)
 522 {
 523         if (gSingleCore)
 524                 return;
 525
 526         ASSERT(fIdleCPUCount > 0);
 527         if (fIdleCPUCount-- == fCPUCount)
 528                 fPackage->CoreWakesUp(this);
 529 }
 530
 531
 532 /* static */ inline CoreEntry*
 533 CoreEntry::GetCore(int32 cpu)
 534 {
 535         SCHEDULER_ENTER_FUNCTION();
 536         return gCPUEntries[cpu].Core();
 537 }
 538
 539
 540 inline CoreEntry*
 541 PackageEntry::GetIdleCore() const
 542 {
 543         SCHEDULER_ENTER_FUNCTION();
 544         return fIdleCores.Last();
 545 }
 546
 547
 548 /* static */ inline PackageEntry*
 549 PackageEntry::GetMostIdlePackage()
 550 {
 551         SCHEDULER_ENTER_FUNCTION();
 552
 553         PackageEntry* current = &gPackageEntries[0];
 554         for (int32 i = 1; i < gPackageCount; i++) {
 555                 if (gPackageEntries[i].fIdleCoreCount > current->fIdleCoreCount)
 556                         current = &gPackageEntries[i];
 557         }
 558
 559         if (current->fIdleCoreCount == 0)
 560                 return NULL;
 561
 562         return current;
 563 }
 564
 565
 566 /* static */ inline PackageEntry*
 567 PackageEntry::GetLeastIdlePackage()
 568 {
 569         SCHEDULER_ENTER_FUNCTION();
 570
 571         PackageEntry* package = NULL;
 572
 573         for (int32 i = 0; i < gPackageCount; i++) {
 574                 PackageEntry* current = &gPackageEntries[i];
 575
 576                 int32 currentIdleCoreCount = current->fIdleCoreCount;
 577                 if (currentIdleCoreCount != 0 && (package == NULL
 578                                 || currentIdleCoreCount < package->fIdleCoreCount)) {
 579                         package = current;
 580                 }
 581         }
 582
 583         return package;
 584 }
 585
 586
 587 }       // namespace Scheduler
 588
 589
 590 #endif  // KERNEL_SCHEDULER_CPU_H
 591