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 24namespace Scheduler { 25 26 27class DebugDumper; 28 29struct ThreadData; 30class ThreadProcessing; 31 32class CPUEntry; 33class CoreEntry; 34class 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. 40class ThreadRunQueue : public RunQueue<ThreadData, THREAD_MAX_SET_PRIORITY> { 41public: 42 void Dump() const; 43}; 44 45class CPUEntry : public HeapLinkImpl<CPUEntry, int32> { 46public: 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 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 90private: 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 115class CPUPriorityHeap : public Heap<CPUEntry, int32> { 116public: 117 CPUPriorityHeap() { } 118 CPUPriorityHeap(int32 cpuCount); 119 120 void Dump(); 121}; 122 123class CoreEntry : public MinMaxHeapLinkImpl<CoreEntry, int32>, 124 public DoublyLinkedListLinkImpl<CoreEntry> { 125public: 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 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 175private: 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 206class CoreLoadHeap : public MinMaxHeap<CoreEntry, int32> { 207public: 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). 223class PackageEntry : public DoublyLinkedListLinkImpl<PackageEntry> { 224public: 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 240private: 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; 250typedef DoublyLinkedList<PackageEntry> IdlePackageList; 251 252extern CPUEntry* gCPUEntries; 253 254extern CoreEntry* gCoreEntries; 255extern CoreLoadHeap gCoreLoadHeap; 256extern CoreLoadHeap gCoreHighLoadHeap; 257extern rw_spinlock gCoreHeapsLock; 258extern int32 gCoreCount; 259 260extern PackageEntry* gPackageEntries; 261extern IdlePackageList gIdlePackageList; 262extern rw_spinlock gIdlePackageLock; 263extern int32 gPackageCount; 264 265 266inline void 267CPUEntry::EnterScheduler() 268{ 269 SCHEDULER_ENTER_FUNCTION(); 270 acquire_read_spinlock(&fSchedulerModeLock); 271} 272 273 274inline void 275CPUEntry::ExitScheduler() 276{ 277 SCHEDULER_ENTER_FUNCTION(); 278 release_read_spinlock(&fSchedulerModeLock); 279} 280 281 282inline void 283CPUEntry::LockScheduler() 284{ 285 SCHEDULER_ENTER_FUNCTION(); 286 acquire_write_spinlock(&fSchedulerModeLock); 287} 288 289 290inline void 291CPUEntry::UnlockScheduler() 292{ 293 SCHEDULER_ENTER_FUNCTION(); 294 release_write_spinlock(&fSchedulerModeLock); 295} 296 297 298inline void 299CPUEntry::LockRunQueue() 300{ 301 SCHEDULER_ENTER_FUNCTION(); 302 acquire_spinlock(&fQueueLock); 303} 304 305 306inline void 307CPUEntry::UnlockRunQueue() 308{ 309 SCHEDULER_ENTER_FUNCTION(); 310 release_spinlock(&fQueueLock); 311} 312 313 314/* static */ inline CPUEntry* 315CPUEntry::GetCPU(int32 cpu) 316{ 317 SCHEDULER_ENTER_FUNCTION(); 318 return &gCPUEntries[cpu]; 319} 320 321 322inline void 323CoreEntry::LockCPUHeap() 324{ 325 SCHEDULER_ENTER_FUNCTION(); 326 acquire_spinlock(&fCPULock); 327} 328 329 330inline void 331CoreEntry::UnlockCPUHeap() 332{ 333 SCHEDULER_ENTER_FUNCTION(); 334 release_spinlock(&fCPULock); 335} 336 337 338inline CPUPriorityHeap* 339CoreEntry::CPUHeap() 340{ 341 SCHEDULER_ENTER_FUNCTION(); 342 return &fCPUHeap; 343} 344 345 346inline int32 347CoreEntry::ThreadCount() const 348{ 349 SCHEDULER_ENTER_FUNCTION(); 350 return fThreadCount + fCPUCount - fIdleCPUCount; 351} 352 353 354inline void 355CoreEntry::LockRunQueue() 356{ 357 SCHEDULER_ENTER_FUNCTION(); 358 acquire_spinlock(&fQueueLock); 359} 360 361 362inline void 363CoreEntry::UnlockRunQueue() 364{ 365 SCHEDULER_ENTER_FUNCTION(); 366 release_spinlock(&fQueueLock); 367} 368 369 370inline void 371CoreEntry::IncreaseActiveTime(bigtime_t activeTime) 372{ 373 SCHEDULER_ENTER_FUNCTION(); 374 WriteSequentialLocker _(fActiveTimeLock); 375 fActiveTime += activeTime; 376} 377 378 379inline bigtime_t 380CoreEntry::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 394inline int32 395CoreEntry::GetLoad() const 396{ 397 SCHEDULER_ENTER_FUNCTION(); 398 399 ASSERT(fCPUCount > 0); 400 return std::min(fLoad / fCPUCount, kMaxLoad); 401} 402 403 404inline void 405CoreEntry::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 423inline uint32 424CoreEntry::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 443inline void 444CoreEntry::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*/ 466inline void 467PackageEntry::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 487inline void 488PackageEntry::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 508inline void 509CoreEntry::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 520inline void 521CoreEntry::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* 533CoreEntry::GetCore(int32 cpu) 534{ 535 SCHEDULER_ENTER_FUNCTION(); 536 return gCPUEntries[cpu].Core(); 537} 538 539 540inline CoreEntry* 541PackageEntry::GetIdleCore() const 542{ 543 SCHEDULER_ENTER_FUNCTION(); 544 return fIdleCores.Last(); 545} 546 547 548/* static */ inline PackageEntry* 549PackageEntry::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* 567PackageEntry::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 592