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