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 class CPUEntry; 33 class CoreEntry; 34 class 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 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 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 std::min(fLoad / fCPUCount, kMaxLoad); 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 592