// Copyright (c) 2009-2009 Nokia Corporation and/or its subsidiary(-ies).

// All rights reserved.

// This component and the accompanying materials are made available

// under the terms of the License "Eclipse Public License v1.0"

// which accompanies this distribution, and is available

// at the URL "http://www.eclipse.org/legal/epl-v10.html".

//

// Initial Contributors:

// Nokia Corporation - initial contribution.

//

// Contributors:

//

// Description:

// e32\nkernsmp\nk_bal.cpp

// 

//

// NThreadBase member data

#define __INCLUDE_NTHREADBASE_DEFINES__

// TDfc member data

#define __INCLUDE_TDFC_DEFINES__

#include "nk_bal.h"

#include "nk_priv.h"

#include "nk_irq.h"

#include <e32cmn.h>

/******************************************************************************

 * Load balancing

 ******************************************************************************/

enum TCCState

	{

	ECCReqPending = 0x80000000u,

	ECCReqDeferred = 0x40000000u,

	ECCPowerUpInProgress = 0x20000000u,

	ECCPowerDownInProgress = 0x10000000u,

	ECCRebalanceRequired = 0x08000000u,

	ECCRebalanceTimerQueued = 0x04000000u,

	ECCPeriodicBalancingActive = 0x02000000u,

	};

const TUint K_CpuMask	= 0x1fu;

const TUint K_Keep		= 0x20u;

const TUint K_SameCpu	= 0x40u;

const TUint K_NewCpu	= 0x80u;

const TUint K_CpuSticky	= 0x40u;

const TUint K_CheckCpu	= 0x100u;

#define	PERCENT(fsd, percent)					(((fsd)*(percent)+50)/100)

const TUint K_LB_HeavyThreshold					= PERCENT(4095, 90);

const TUint K_LB_GravelThreshold_RunAvg			= PERCENT(4095, 1);

const TUint K_LB_GravelThreshold_RunActAvg		= PERCENT(4095, 50);

const TInt	K_LB_HeavyCapacityThreshold			= PERCENT(4095, 1);

const TInt	K_LB_BalanceInterval				= 107;

const TInt	K_LB_CpuLoadDiffThreshold			= 128;

//const TUint K_LB_HeavyStateThreshold			= 128;

const TUint K_LB_HeavyPriorityThreshold			= 25;

inline TBool IsHeavy(NSchedulable* a)

	{

	TUint x = 0xffu ^ a->iLbInfo.iLbHeavy;

	return (x&(x-1))==0;

	}

inline TBool IsNew(NSchedulable* a)

	{ return a->iLbState & NSchedulable::ELbState_PerCpu; }

struct SPerPri : public SDblQue

	{

	inline SPerPri() : iTotalRun(0), iTotalAct(0), iCount(0), iHeavy(0) {}

	TUint32	iTotalRun;

	TUint32	iTotalAct;

	TUint16	iCount;

	TUint16	iHeavy;

	};

struct SCpuAvailability

	{

	enum

		{

		EIdle = 4095,

		EMaxedOut = -268435456,

		EUnavailable = KMinTInt

		};

	void	Init(TUint32 aActive);

	TInt	FindMax() const;

	TInt	FindMax(NSchedulable* aS) const;

	TInt	PickCpu(NSchedulable* aS, TBool aDropped) const;

	TInt	SetMaxed(TInt aCpu);

	void	AddLoad(TInt aCpu, TInt aLoad);

	inline	TInt operator[](TInt aCpu) const

		{	return iRemain[aCpu]; }

	inline	TInt TotalRemain() const

		{	return iTotalRemain; }

	TInt	iRemain[KMaxCpus];

	TInt	iCount;

	TInt	iTotalRemain;

	};

TUint32 HotWarmUnit;

TUint32 LB_DormantThreshold;

volatile TUint32 LBDelayed = 0;

void CalcHotWarm(TUint8& aOut, TUint64 aTime)

	{

	TUint8 out = 0;

	if (aTime>0)

		{

		aTime /= TUint64(HotWarmUnit);

		if (I64HIGH(aTime))

			out = 255;

		else

			{

			aTime *= aTime;

			out = __e32_find_ms1_64(aTime) + 1;

			}

		}

	aOut = (TUint8)out;

	}

void TScheduler::InitLB()

	{

	TScheduler& s = TheScheduler;

	TDfcQue* rbQ = s.iRebalanceDfcQ;

	s.iBalanceTimer.SetDfcQ(rbQ);

	s.iCCReactivateDfc.SetDfcQ(rbQ);

	s.iCCRequestDfc.SetDfcQ(rbQ);

	s.iCCPowerDownDfc.SetDfcQ(rbQ);

	NThreadBase* lbt = rbQ->iThread;

	lbt->iRebalanceAttr = 1;

	TUint32 f = NKern::CpuTimeMeasFreq();

	HotWarmUnit = f / 1000000;

	TUint8 y = 0;

	CalcHotWarm(y, f/5);

	LB_DormantThreshold = y;

	__KTRACE_OPT(KBOOT,DEBUGPRINT("InitLB()"));

	__KTRACE_OPT(KBOOT,DEBUGPRINT("LB_DormantThreshold=%d", LB_DormantThreshold));

	}

void TSubScheduler::GetLbThreads(SDblQue& aQ)

	{

	NKern::Lock();

	iReadyListLock.LockOnly();

	if (!iLbQ.IsEmpty())

		{

		aQ.MoveFrom(&iLbQ);

		iLbCounter ^= NSchedulable::ELbState_Generation;

		}

	iReadyListLock.UnlockOnly();

	NKern::Unlock();

	}

void TScheduler::GetLbThreads(SDblQue& aQ)

	{

	NKern::Lock();

	iBalanceListLock.LockOnly();

	if (!iBalanceList.IsEmpty())

		{

		aQ.MoveFrom(&iBalanceList);

		iLbCounter ^= NSchedulable::ELbState_Generation;

		}

	iBalanceListLock.UnlockOnly();

	NKern::Unlock();

	}

void NSchedulable::InitLbInfo()

	{

	}

void NSchedulable::NominalPriorityChanged()

	{

	}

void NSchedulable::LbDone(TUint aFlags)

	{

	BTrace8(BTrace::EHSched, BTrace::ELbDone, this, aFlags);

#ifdef KSCHED3

	if (IsGroup())

		{

		__KTRACE_OPT(KSCHED3,DEBUGPRINT("LbDone %G %x", this, aFlags));

		}

	else

		{

		__KTRACE_OPT(KSCHED3,DEBUGPRINT("LbDone %T %x", this, aFlags));

		}

#endif

	TBool keep = aFlags & K_Keep;

	TInt cpu = aFlags & K_CpuMask;

	TBool setcpu = aFlags & K_NewCpu;

	TBool keepcpu = aFlags & K_SameCpu;

	TBool checkcpu = aFlags & K_CheckCpu;

	LAcqSLock();

	TBool died = iLbState & ELbState_ExtraRef;

	if (keep && !died)

		{

		TScheduler& s = TheScheduler;

		s.iBalanceListLock.LockOnly();

		s.iBalanceList.Add(&iLbLink);

		iLbState = s.iLbCounter;

		s.iBalanceListLock.UnlockOnly();

		if (setcpu)

			SetCpuAffinityT(cpu | KCpuAffinityPref | (aFlags & K_CpuSticky));

		else

			{

			if (!keepcpu)

				iPreferredCpu = 0;

			if (checkcpu)

				SetCpuAffinityT(NTHREADBASE_CPU_AFFINITY_MASK);	// move it if it's on a core which is shutting down

			}

		}

	else

		{

		if (!keepcpu)

			iPreferredCpu = 0;

		iLbState = ELbState_Inactive;

		iLbLink.iNext = 0;

		iLbInfo.iRecentTime.i64 = 0;

		iLbInfo.iRecentCpuTime.i64 = 0;

		iLbInfo.iRecentActiveTime.i64 = 0;

		iLbInfo.iLbRunAvg = 0;

		iLbInfo.iLbActAvg = 0;

		iLbInfo.iLbRunActAvg = 0;

		if (checkcpu && !died)

			SetCpuAffinityT(NTHREADBASE_CPU_AFFINITY_MASK);	// move it if it's on a core which is shutting down

		}

	RelSLockU();

	if (died)

		{

		NKern::Lock();

		DropRef();

		NKern::Unlock();

		}

	}

void CalcRatio(TUint16& aRatio, TUint64 aN, TUint64 aD)

	{

	TInt ms1 = __e32_find_ms1_64(aD);

	if (ms1 < 0)

		{

		aRatio = 4095;

		return;

		}

	if (ms1 >= 20)

		{

		TInt shift = ms1 - 19;

		aD >>= shift;

		aN >>= shift;

		}

	// aD, aN now < 2^20

	TUint32 d = I64LOW(aD);

	TUint32 n = I64LOW(aN);

	if (n>d) n=d;

	TUint32 r = (n*4095+(d>>1))/d;

	if (r>4095) r=4095;	// shouldn't really happen

	aRatio = (TUint16)r;

	}

void CalcRatios(TUint16& aRT, TUint16& aAT, TUint16& aRA, TUint64 aDT, TUint64 aDR, TUint64 aDA)

	{

	TInt ms1 = __e32_find_ms1_64(aDT);

	if (ms1 >= 20)

		{

		TInt shift = ms1 - 19;

		aDT >>= shift;

		aDR >>= shift;

		aDA >>= shift;

		}

	// aDT, aDR, aDA now all < 2^20

	TUint32 t = I64LOW(aDT);

	TUint32 rtd = I64LOW(aDR);

	TUint32 atd = I64LOW(aDA);

	if (rtd>t) rtd=t;

	if (atd>t) atd=t;

	TUint32 rtt = (rtd*4095+(t>>1))/t;

	TUint32 att = (atd*4095+(t>>1))/t;

	TUint32 rta = atd ? (rtd*4095+(atd>>1))/atd : 0;

	if (rta>4095) rta=4095;	// shouldn't really happen

	aRT = (TUint16)rtt;

	aAT = (TUint16)att;

	aRA = (TUint16)rta;

	}

void NSchedulable::GetLbStats(TUint64 aTime)

	{

	SCpuStats stats;

	LAcqSLock();

	if (IsGroup())

		{

		NThreadGroup* g = (NThreadGroup*)this;

		if (g->iNThreadList.IsEmpty())

			iLbInfo.iLbNomPri = 1;

		else

			{

			NThreadBase* t = (NThreadBase*)g->iNThreadList.First();

			iLbInfo.iLbNomPri = t->iNominalPri;

			}

		}

	else

		iLbInfo.iLbNomPri = ((NThreadBase*)this)->iNominalPri;

	GetCpuStatsT(E_AllStats, stats);

	iLbInfo.iRecentTime.i64 += aTime;

	iLbInfo.iRecentCpuTime.i64 += stats.iRunTimeDelta;

	iLbInfo.iRecentActiveTime.i64 += stats.iActiveTimeDelta;

	TUint32 aff = iCpuAffinity;

	RelSLockU();

	CalcRatios(iLbInfo.iLbRunTime, iLbInfo.iLbActTime, iLbInfo.iLbRunAct, aTime, stats.iRunTimeDelta, stats.iActiveTimeDelta);

	iLbInfo.iLbRunAvg = TUint16((iLbInfo.iLbRunAvg + iLbInfo.iLbRunTime) >> 1);

	iLbInfo.iLbActAvg = TUint16((iLbInfo.iLbActAvg + iLbInfo.iLbActTime) >> 1);

	CalcRatio(iLbInfo.iLbRunActAvg, iLbInfo.iRecentCpuTime.i64, iLbInfo.iRecentActiveTime.i64);

	if (aff & NTHREADBASE_CPU_AFFINITY_MASK)

		iLbInfo.iLbAffinity = (TUint8)(aff & 0xff);

	else

		iLbInfo.iLbAffinity = 1u << aff;

	CalcHotWarm(iLbInfo.iLbHot, stats.iLastRunTime);

	CalcHotWarm(iLbInfo.iLbWarm, stats.iLastActiveTime);

	if (IsNew(this))

		{

		if (iLbInfo.iLbNomPri <= K_LB_HeavyPriorityThreshold)

			iLbInfo.iLbHeavy = 0xffu;

		else

			iLbInfo.iLbHeavy = 0;

		}

	iLbInfo.iLbHeavy >>= 1;

	if (iLbInfo.iLbActTime > K_LB_HeavyThreshold)

		iLbInfo.iLbHeavy |= 0x80u;

/*

	TUint64 blx = NKern::CpuTimeMeasFreq();

	blx *= 3;

	if (i_NSchedulable_Spare3 && iLbInfo.iLbRunActAvg<400 && stats.iActiveTime>blx)

		{

		__crash();

		}

*/	}

void AddToSortedQueue(SPerPri* aQ, NSchedulable* aS)

	{

	TInt k = aS->iLbInfo.iLbNomPri;

	if (k >= KNumPriorities)

		k = KNumPriorities;

	SPerPri* q = aQ + k;

	TBool h = IsHeavy(aS);

	SDblQueLink* anchor = &q->iA;

	SDblQueLink* p = q->First();

	for (; p!=anchor; p=p->iNext)

		{

		NSchedulable* s = _LOFF(p, NSchedulable, iLbLink);

		if (h)

			{

			if (!IsHeavy(s))

				continue;

			if (aS->iLbInfo.iLbRunActAvg < s->iLbInfo.iLbRunActAvg)

				break;

			}

		else

			{

			if (IsHeavy(s))

				break;

			if (aS->iLbInfo.iLbRunAvg > s->iLbInfo.iLbRunAvg)

				break;

			}

		}

	aS->iLbLink.InsertBefore(p);

	++q->iCount;

	if (h)

		{

		++q->iHeavy;

		}

	else

		{

		q->iTotalRun += aS->iLbInfo.iLbRunAvg;

		if (q->iTotalRun>4095)

			q->iTotalRun=4095;

		q->iTotalAct += aS->iLbInfo.iLbActAvg;

		}

	}

void SCpuAvailability::Init(TUint32 a)

	{

	iCount = __e32_find_ms1_32(a) + 1;

	iTotalRemain = 0;

	TInt i;

	for (i=0; i<KMaxCpus; ++i)

		{

		if (a & (1<<i))

			{

			iRemain[i] = EIdle;

			iTotalRemain += EIdle;

			}

		else

			iRemain[i] = EUnavailable;

		}

	}

TInt SCpuAvailability::SetMaxed(TInt aCpu)

	{

	TInt x = iRemain[aCpu];

	if (x>0)

		iTotalRemain -= x;

	iRemain[aCpu] = EMaxedOut;

	return x;

	}

void SCpuAvailability::AddLoad(TInt aCpu, TInt aLoad)

	{

	if (TUint32(aLoad) > TUint32(EIdle))

		__crash();

	TInt& x = iRemain[aCpu];

	TInt orig = x;

	x -= aLoad;

	if (x < EMaxedOut)

		x = EMaxedOut;

	if (orig > 0)

		iTotalRemain -= ((orig > aLoad) ? aLoad : orig);

	}

TInt SCpuAvailability::FindMax() const

	{

	TInt maxv = KMinTInt;

	TInt maxi = -1;

	TInt i;

	for (i=0; i<iCount; ++i)

		{

		if (iRemain[i] > maxv)

			{

			maxv = iRemain[i];

			maxi = i;

			}

		}

	return maxi;

	}

TInt SCpuAvailability::FindMax(NSchedulable* aS) const

	{

	TUint32 s = aS->iLbInfo.iLbAffinity;

	s &= TheScheduler.iThreadAcceptCpus;

	if ( (s&(s-1)) == 0 )

		return __e32_find_ms1_32(s);

	TInt maxv = KMinTInt;

	TInt maxi = -1;

	TInt i = 0;

	for (; s; s>>=1, ++i)

		{

		if ((s&1) && iRemain[i] > maxv)

			{

			maxv = iRemain[i];

			maxi = i;

			}

		}

	return maxi;

	}

TInt SCpuAvailability::PickCpu(NSchedulable* aS, TBool aDropped) const

	{

	TUint32 s0 = aS->iLbInfo.iLbAffinity & TheScheduler.iThreadAcceptCpus;

	TUint32 s = s0;

//	BTrace12(BTrace::EHSched, 0x90u, aS, s, aPtr);

	if ( (s&(s-1)) == 0 )

		return __e32_find_ms1_32(s);

	TInt maxv = KMinTInt;

	TInt maxi = -1;

	TInt i = 0;

	for (; s; s>>=1, ++i)

		{

//		BTrace12(BTrace::EHSched, 0x91u, s, maxv, aPtr[i]);

		if ((s&1) && iRemain[i] > maxv)

			{

			maxv = iRemain[i];

			maxi = i;

			}

		}

	if (IsNew(aS))

		{

		// this thread hasn't run for a while

		// pick the highest numbered CPU with a near-maximum availability

		i = __e32_find_ms1_32(s0);

		for (; i>maxi; --i)

			{

			if ( (s0&(1u<<i)) && maxv-iRemain[i]<K_LB_CpuLoadDiffThreshold)

				return i;

			}

		}

	else

		{

		// this thread has run recently - see if we can keep it on the same CPU

		TInt threshold = aDropped ? 1 : (TInt)K_LB_CpuLoadDiffThreshold;

		TInt lcpu = aS->iLastCpu;

		if ( (s0&(1u<<lcpu)) && maxv-iRemain[lcpu]<threshold)

			return lcpu;

		}

	// use highest availability CPU

	return maxi;

	}

void TScheduler::BalanceTimerExpired(TAny* aPtr)

	{

	((TScheduler*)aPtr)->PeriodicBalance();

	}

TBool TScheduler::ReBalance(SDblQue& aQ, TBool aCC)

	{

	ModifyCCState(~ECCRebalanceRequired, 0);

	SPerPri sbq[KNumPriorities+1];

	NSchedulable* s = 0;

	TInt i;

	TUint64 now = NKern::Timestamp();

	TUint64 lbt = iLastBalanceTime;

	iLastBalanceTime = now;

	TUint64 bpl = now - lbt;		// balance period length

	TUint cc = aCC ? K_CheckCpu : 0;

	TInt nact = __e32_bit_count_32(iThreadAcceptCpus);	// number of CPUs available

	// aQ holds list of threads/groups to be considered

	TInt ns = 0;	// number for further consideration

	TInt nd = 0;	// number dropped this time round

	SCpuAvailability avail;

	avail.Init(iThreadAcceptCpus);