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