19c2e74daSPawel Dziepak/*
29c2e74daSPawel Dziepak * Copyright 2013, Pawe�� Dziepak, pdziepak@quarnos.org.
39c2e74daSPawel Dziepak * Distributed under the terms of the MIT License.
49c2e74daSPawel Dziepak */
59c2e74daSPawel Dziepak
69c2e74daSPawel Dziepak
7d287274dSPawel Dziepak#include <util/atomic.h>
89c2e74daSPawel Dziepak#include <util/AutoLock.h>
99c2e74daSPawel Dziepak
109c2e74daSPawel Dziepak#include "scheduler_common.h"
11d287274dSPawel Dziepak#include "scheduler_cpu.h"
129c2e74daSPawel Dziepak#include "scheduler_modes.h"
1396dcc73bSPawel Dziepak#include "scheduler_profiler.h"
14d287274dSPawel Dziepak#include "scheduler_thread.h"
159c2e74daSPawel Dziepak
169c2e74daSPawel Dziepak
179c2e74daSPawel Dziepakusing namespace Scheduler;
189c2e74daSPawel Dziepak
199c2e74daSPawel Dziepak
2007218997SPawel Dziepakconst bigtime_t kCacheExpire = 100000;
2107218997SPawel Dziepak
22d287274dSPawel Dziepakstatic CoreEntry* sSmallTaskCore;
239c2e74daSPawel Dziepak
249c2e74daSPawel Dziepak
2513a89839SPawel Dziepakstatic void
2660e198f2SPawel Dziepakswitch_to_mode()
2713a89839SPawel Dziepak{
28d287274dSPawel Dziepak	sSmallTaskCore = NULL;
2913a89839SPawel Dziepak}
3013a89839SPawel Dziepak
3113a89839SPawel Dziepak
3213a89839SPawel Dziepakstatic void
3313a89839SPawel Dziepakset_cpu_enabled(int32 cpu, bool enabled)
3413a89839SPawel Dziepak{
3513a89839SPawel Dziepak	if (!enabled)
36d287274dSPawel Dziepak		sSmallTaskCore = NULL;
3713a89839SPawel Dziepak}
3813a89839SPawel Dziepak
3913a89839SPawel Dziepak
409c2e74daSPawel Dziepakstatic bool
41d287274dSPawel Dziepakhas_cache_expired(const ThreadData* threadData)
429c2e74daSPawel Dziepak{
4396dcc73bSPawel Dziepak	SCHEDULER_ENTER_FUNCTION();
442d52abbdSPawel Dziepak	if (threadData->WentSleep() == 0)
452d52abbdSPawel Dziepak		return false;
46b24ea642SPawel Dziepak	return system_time() - threadData->WentSleep() > kCacheExpire;
479c2e74daSPawel Dziepak}
489c2e74daSPawel Dziepak
499c2e74daSPawel Dziepak
50d287274dSPawel Dziepakstatic CoreEntry*
5160e198f2SPawel Dziepakchoose_small_task_core()
529c2e74daSPawel Dziepak{
5396dcc73bSPawel Dziepak	SCHEDULER_ENTER_FUNCTION();
5496dcc73bSPawel Dziepak
551700e825SPawel Dziepak	ReadSpinLocker coreLocker(gCoreHeapsLock);
56d287274dSPawel Dziepak	CoreEntry* core = gCoreLoadHeap.PeekMaximum();
57d287274dSPawel Dziepak	if (core == NULL)
58ecfd4449SPawel Dziepak		return sSmallTaskCore;
59ecfd4449SPawel Dziepak
60d287274dSPawel Dziepak	CoreEntry* smallTaskCore
61d287274dSPawel Dziepak		= atomic_pointer_test_and_set(&sSmallTaskCore, core, (CoreEntry*)NULL);
62d287274dSPawel Dziepak	if (smallTaskCore == NULL)
63ecfd4449SPawel Dziepak		return core;
64ecfd4449SPawel Dziepak	return smallTaskCore;
659c2e74daSPawel Dziepak}
669c2e74daSPawel Dziepak
679c2e74daSPawel Dziepak
6865741c8bSPawel Dziepakstatic CoreEntry*
6960e198f2SPawel Dziepakchoose_idle_core()
7065741c8bSPawel Dziepak{
7196dcc73bSPawel Dziepak	SCHEDULER_ENTER_FUNCTION();
7296dcc73bSPawel Dziepak
7360e198f2SPawel Dziepak	PackageEntry* package = PackageEntry::GetLeastIdlePackage();
74d287274dSPawel Dziepak
7560e198f2SPawel Dziepak	if (package == NULL)
76d287274dSPawel Dziepak		package = gIdlePackageList.Last();
7765741c8bSPawel Dziepak
7860e198f2SPawel Dziepak	if (package != NULL)
7960e198f2SPawel Dziepak		return package->GetIdleCore();
8065741c8bSPawel Dziepak
8165741c8bSPawel Dziepak	return NULL;
8265741c8bSPawel Dziepak}
8365741c8bSPawel Dziepak
8465741c8bSPawel Dziepak
85d287274dSPawel Dziepakstatic CoreEntry*
86d287274dSPawel Dziepakchoose_core(const ThreadData* threadData)
879c2e74daSPawel Dziepak{
8896dcc73bSPawel Dziepak	SCHEDULER_ENTER_FUNCTION();
8996dcc73bSPawel Dziepak
90d287274dSPawel Dziepak	CoreEntry* core = NULL;
919c2e74daSPawel Dziepak
92f9ee217aSPawel Dziepak	// try to pack all threads on one core
93f9ee217aSPawel Dziepak	core = choose_small_task_core();
94f9ee217aSPawel Dziepak
95d287274dSPawel Dziepak	if (core == NULL || core->GetLoad() + threadData->GetLoad() >= kHighLoad) {
9665741c8bSPawel Dziepak		ReadSpinLocker coreLocker(gCoreHeapsLock);
97d287274dSPawel Dziepak
98f9ee217aSPawel Dziepak		// run immediately on already woken core
99d287274dSPawel Dziepak		core = gCoreLoadHeap.PeekMinimum();
100d287274dSPawel Dziepak		if (core == NULL) {
10165741c8bSPawel Dziepak			coreLocker.Unlock();
10265741c8bSPawel Dziepak
103d287274dSPawel Dziepak			core = choose_idle_core();
10465741c8bSPawel Dziepak
105d287274dSPawel Dziepak			if (core == NULL) {
106f9ee217aSPawel Dziepak				coreLocker.Lock();
107d287274dSPawel Dziepak				core = gCoreHighLoadHeap.PeekMinimum();
108f9ee217aSPawel Dziepak			}
10965741c8bSPawel Dziepak		}
1109c2e74daSPawel Dziepak	}
1119c2e74daSPawel Dziepak
112d287274dSPawel Dziepak	ASSERT(core != NULL);
113d287274dSPawel Dziepak	return core;
1149c2e74daSPawel Dziepak}
1159c2e74daSPawel Dziepak
1169c2e74daSPawel Dziepak
1171bba129cSPawel Dziepakstatic CoreEntry*
1181bba129cSPawel Dziepakrebalance(const ThreadData* threadData)
1199c2e74daSPawel Dziepak{
12096dcc73bSPawel Dziepak	SCHEDULER_ENTER_FUNCTION();
12196dcc73bSPawel Dziepak
1229c2e74daSPawel Dziepak	ASSERT(!gSingleCore);
1239c2e74daSPawel Dziepak
12460e198f2SPawel Dziepak	CoreEntry* core = threadData->Core();
1259c2e74daSPawel Dziepak
126d287274dSPawel Dziepak	int32 coreLoad = core->GetLoad();
127a2634874SPawel Dziepak	int32 threadLoad = threadData->GetLoad() / core->CPUCount();
1281a7eb502SPawel Dziepak	if (coreLoad > kHighLoad) {
129ecfd4449SPawel Dziepak		if (sSmallTaskCore == core) {
130d287274dSPawel Dziepak			sSmallTaskCore = NULL;
1311bba129cSPawel Dziepak			CoreEntry* smallTaskCore = choose_small_task_core();
132d287274dSPawel Dziepak
133c37c2aa4SPawel Dziepak			if (threadLoad > coreLoad / 3)
1341bba129cSPawel Dziepak				return core;
1351bba129cSPawel Dziepak			return coreLoad > kVeryHighLoad ? smallTaskCore : core;
136ecfd4449SPawel Dziepak		}
137683b9bbfSPawel Dziepak
138c37c2aa4SPawel Dziepak		if (threadLoad >= coreLoad / 2)
1391bba129cSPawel Dziepak			return core;
140f9ee217aSPawel Dziepak
1411700e825SPawel Dziepak		ReadSpinLocker coreLocker(gCoreHeapsLock);
142d287274dSPawel Dziepak		CoreEntry* other = gCoreLoadHeap.PeekMaximum();
143683b9bbfSPawel Dziepak		if (other == NULL)
144d287274dSPawel Dziepak			other = gCoreHighLoadHeap.PeekMinimum();
1451700e825SPawel Dziepak		coreLocker.Unlock();
14665741c8bSPawel Dziepak		ASSERT(other != NULL);
147c37c2aa4SPawel Dziepak
148c37c2aa4SPawel Dziepak		int32 coreNewLoad = coreLoad - threadLoad;
149c37c2aa4SPawel Dziepak		int32 otherNewLoad = other->GetLoad() + threadLoad;
1501bba129cSPawel Dziepak		return coreNewLoad - otherNewLoad >= kLoadDifference / 2 ? other : core;
1519c2e74daSPawel Dziepak	}
1529c2e74daSPawel Dziepak
153f9ee217aSPawel Dziepak	if (coreLoad >= kMediumLoad)
1541bba129cSPawel Dziepak		return core;
155f9ee217aSPawel Dziepak
156d287274dSPawel Dziepak	CoreEntry* smallTaskCore = choose_small_task_core();
157d287274dSPawel Dziepak	if (smallTaskCore == NULL)
1581bba129cSPawel Dziepak		return core;
1591bba129cSPawel Dziepak	return smallTaskCore->GetLoad() + threadLoad < kHighLoad
1601bba129cSPawel Dziepak		? smallTaskCore : core;
1619c2e74daSPawel Dziepak}
1629c2e74daSPawel Dziepak
1639c2e74daSPawel Dziepak
164c4ac37a3SPawel Dziepakstatic inline void
16560e198f2SPawel Dziepakpack_irqs()
166c4ac37a3SPawel Dziepak{
16796dcc73bSPawel Dziepak	SCHEDULER_ENTER_FUNCTION();
16896dcc73bSPawel Dziepak
169d287274dSPawel Dziepak	CoreEntry* smallTaskCore = atomic_pointer_get(&sSmallTaskCore);
170d287274dSPawel Dziepak	if (smallTaskCore == NULL)
171d287274dSPawel Dziepak		return;
172d287274dSPawel Dziepak
173c4ac37a3SPawel Dziepak	cpu_ent* cpu = get_cpu_struct();
174d287274dSPawel Dziepak	if (smallTaskCore == CoreEntry::GetCore(cpu->cpu_num))
175d287274dSPawel Dziepak		return;
176c4ac37a3SPawel Dziepak
177c4ac37a3SPawel Dziepak	SpinLocker locker(cpu->irqs_lock);
178d287274dSPawel Dziepak	while (list_get_first_item(&cpu->irqs) != NULL) {
179c4ac37a3SPawel Dziepak		irq_assignment* irq = (irq_assignment*)list_get_first_item(&cpu->irqs);
180c4ac37a3SPawel Dziepak		locker.Unlock();
181c4ac37a3SPawel Dziepak
182ef8e55a1SPawel Dziepak		int32 newCPU = smallTaskCore->CPUHeap()->PeekRoot()->ID();
183c4ac37a3SPawel Dziepak
184c4ac37a3SPawel Dziepak		if (newCPU != cpu->cpu_num)
185c4ac37a3SPawel Dziepak			assign_io_interrupt_to_cpu(irq->irq, newCPU);
186c4ac37a3SPawel Dziepak
187c4ac37a3SPawel Dziepak		locker.Lock();
188c4ac37a3SPawel Dziepak	}
189c4ac37a3SPawel Dziepak}
190c4ac37a3SPawel Dziepak
191c4ac37a3SPawel Dziepak
192c4ac37a3SPawel Dziepakstatic void
193c4ac37a3SPawel Dziepakrebalance_irqs(bool idle)
194c4ac37a3SPawel Dziepak{
19596dcc73bSPawel Dziepak	SCHEDULER_ENTER_FUNCTION();
19696dcc73bSPawel Dziepak
197d287274dSPawel Dziepak	if (idle && sSmallTaskCore != NULL) {
198c4ac37a3SPawel Dziepak		pack_irqs();
199c4ac37a3SPawel Dziepak		return;
200c4ac37a3SPawel Dziepak	}
201c4ac37a3SPawel Dziepak
202d287274dSPawel Dziepak	if (idle || sSmallTaskCore != NULL)
203c4ac37a3SPawel Dziepak		return;
204c4ac37a3SPawel Dziepak
205c4ac37a3SPawel Dziepak	cpu_ent* cpu = get_cpu_struct();
206c4ac37a3SPawel Dziepak	SpinLocker locker(cpu->irqs_lock);
207c4ac37a3SPawel Dziepak
208c4ac37a3SPawel Dziepak	irq_assignment* chosen = NULL;
209c4ac37a3SPawel Dziepak	irq_assignment* irq = (irq_assignment*)list_get_first_item(&cpu->irqs);
210c4ac37a3SPawel Dziepak
211c4ac37a3SPawel Dziepak	while (irq != NULL) {
212c4ac37a3SPawel Dziepak		if (chosen == NULL || chosen->load < irq->load)
213c4ac37a3SPawel Dziepak			chosen = irq;
214c4ac37a3SPawel Dziepak		irq = (irq_assignment*)list_get_next_item(&cpu->irqs, irq);
215c4ac37a3SPawel Dziepak	}
216c4ac37a3SPawel Dziepak
217c4ac37a3SPawel Dziepak	locker.Unlock();
218c4ac37a3SPawel Dziepak
219c4ac37a3SPawel Dziepak	if (chosen == NULL || chosen->load < kLowLoad)
220c4ac37a3SPawel Dziepak		return;
221c4ac37a3SPawel Dziepak
22265741c8bSPawel Dziepak	ReadSpinLocker coreLocker(gCoreHeapsLock);
223d287274dSPawel Dziepak	CoreEntry* other = gCoreLoadHeap.PeekMinimum();
22465741c8bSPawel Dziepak	coreLocker.Unlock();
225c4ac37a3SPawel Dziepak	if (other == NULL)
226c4ac37a3SPawel Dziepak		return;
227ef8e55a1SPawel Dziepak	int32 newCPU = other->CPUHeap()->PeekRoot()->ID();
228c4ac37a3SPawel Dziepak
229d287274dSPawel Dziepak	CoreEntry* core = CoreEntry::GetCore(smp_get_current_cpu());
230d287274dSPawel Dziepak	if (other == core)
231c4ac37a3SPawel Dziepak		return;
232d287274dSPawel Dziepak	if (other->GetLoad() + kLoadDifference >= core->GetLoad())
233c4ac37a3SPawel Dziepak		return;
234c4ac37a3SPawel Dziepak
235c4ac37a3SPawel Dziepak	assign_io_interrupt_to_cpu(chosen->irq, newCPU);
236c4ac37a3SPawel Dziepak}
237c4ac37a3SPawel Dziepak
238c4ac37a3SPawel Dziepak
2399c2e74daSPawel Dziepakscheduler_mode_operations gSchedulerPowerSavingMode = {
2409c2e74daSPawel Dziepak	"power saving",
2419c2e74daSPawel Dziepak
242093c2202SPawel Dziepak	2000,
243093c2202SPawel Dziepak	500,
244093c2202SPawel Dziepak	{ 3, 10 },
24507218997SPawel Dziepak
246093c2202SPawel Dziepak	20000,
24707218997SPawel Dziepak
2489c2e74daSPawel Dziepak	switch_to_mode,
24913a89839SPawel Dziepak	set_cpu_enabled,
2509c2e74daSPawel Dziepak	has_cache_expired,
2519c2e74daSPawel Dziepak	choose_core,
2521bba129cSPawel Dziepak	rebalance,
253c4ac37a3SPawel Dziepak	rebalance_irqs,
2549c2e74daSPawel Dziepak};
2559c2e74daSPawel Dziepak
256