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
ID()52 inline int32 ID() const { return fCPUNumber; }
Core()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
GetLoad()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:
CPUPriorityHeap()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
ID()131 inline int32 ID() const { return fCoreID; }
Package()132 inline PackageEntry* Package() const { return fPackage; }
CPUCount()133 inline int32 CPUCount() const
134 { return fCPUCount; }
CPUMask()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;
LoadMeasurementEpoch()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:
CoreLoadHeap()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
EnterScheduler()271 CPUEntry::EnterScheduler()
272 {
273 SCHEDULER_ENTER_FUNCTION();
274 acquire_read_spinlock(&fSchedulerModeLock);
275 }
276
277
278 inline void
ExitScheduler()279 CPUEntry::ExitScheduler()
280 {
281 SCHEDULER_ENTER_FUNCTION();
282 release_read_spinlock(&fSchedulerModeLock);
283 }
284
285
286 inline void
LockScheduler()287 CPUEntry::LockScheduler()
288 {
289 SCHEDULER_ENTER_FUNCTION();
290 acquire_write_spinlock(&fSchedulerModeLock);
291 }
292
293
294 inline void
UnlockScheduler()295 CPUEntry::UnlockScheduler()
296 {
297 SCHEDULER_ENTER_FUNCTION();
298 release_write_spinlock(&fSchedulerModeLock);
299 }
300
301
302 inline void
LockRunQueue()303 CPUEntry::LockRunQueue()
304 {
305 SCHEDULER_ENTER_FUNCTION();
306 acquire_spinlock(&fQueueLock);
307 }
308
309
310 inline void
UnlockRunQueue()311 CPUEntry::UnlockRunQueue()
312 {
313 SCHEDULER_ENTER_FUNCTION();
314 release_spinlock(&fQueueLock);
315 }
316
317
318 /* static */ inline CPUEntry*
GetCPU(int32 cpu)319 CPUEntry::GetCPU(int32 cpu)
320 {
321 SCHEDULER_ENTER_FUNCTION();
322 return &gCPUEntries[cpu];
323 }
324
325
326 inline void
LockCPUHeap()327 CoreEntry::LockCPUHeap()
328 {
329 SCHEDULER_ENTER_FUNCTION();
330 acquire_spinlock(&fCPULock);
331 }
332
333
334 inline void
UnlockCPUHeap()335 CoreEntry::UnlockCPUHeap()
336 {
337 SCHEDULER_ENTER_FUNCTION();
338 release_spinlock(&fCPULock);
339 }
340
341
342 inline CPUPriorityHeap*
CPUHeap()343 CoreEntry::CPUHeap()
344 {
345 SCHEDULER_ENTER_FUNCTION();
346 return &fCPUHeap;
347 }
348
349
350 inline int32
ThreadCount()351 CoreEntry::ThreadCount() const
352 {
353 SCHEDULER_ENTER_FUNCTION();
354 return fThreadCount + fCPUCount - fIdleCPUCount;
355 }
356
357
358 inline void
LockRunQueue()359 CoreEntry::LockRunQueue()
360 {
361 SCHEDULER_ENTER_FUNCTION();
362 acquire_spinlock(&fQueueLock);
363 }
364
365
366 inline void
UnlockRunQueue()367 CoreEntry::UnlockRunQueue()
368 {
369 SCHEDULER_ENTER_FUNCTION();
370 release_spinlock(&fQueueLock);
371 }
372
373
374 inline void
IncreaseActiveTime(bigtime_t activeTime)375 CoreEntry::IncreaseActiveTime(bigtime_t activeTime)
376 {
377 SCHEDULER_ENTER_FUNCTION();
378 WriteSequentialLocker _(fActiveTimeLock);
379 fActiveTime += activeTime;
380 }
381
382
383 inline bigtime_t
GetActiveTime()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
GetLoad()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
AddLoad(int32 load,uint32 epoch,bool updateLoad)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
RemoveLoad(int32 load,bool force)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
ChangeLoad(int32 delta)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
CoreGoesIdle(CoreEntry * core)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
CoreWakesUp(CoreEntry * core)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
CPUGoesIdle(CPUEntry *)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
CPUWakesUp(CPUEntry *)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*
GetCore(int32 cpu)537 CoreEntry::GetCore(int32 cpu)
538 {
539 SCHEDULER_ENTER_FUNCTION();
540 return gCPUEntries[cpu].Core();
541 }
542
543
544 inline CoreEntry*
GetIdleCore(int32 index)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*
GetMostIdlePackage()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*
GetLeastIdlePackage()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