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

     2 // All rights reserved.

     3 // This component and the accompanying materials are made available

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

     5 // which accompanies this distribution, and is available

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

     7 //

     8 // Initial Contributors:

     9 // Nokia Corporation - initial contribution.

    10 //

    11 // Contributors:

    12 //

    13 // Description:

    14 // e32\nkernsmp\nk_bal.cpp

    15 // 

    16 //

    17 

    18 // NThreadBase member data

    19 #define __INCLUDE_NTHREADBASE_DEFINES__

    20 

    21 // TDfc member data

    22 #define __INCLUDE_TDFC_DEFINES__

    23 

    24 #include "nk_bal.h"

    25 

    26 #include "nk_priv.h"

    27 #include "nk_irq.h"

    28 

    29 #include <e32cmn.h>

    30 

    31 /******************************************************************************

    32  * Load balancing

    33  ******************************************************************************/

    34 

    35 enum TCCState

    36 	{

    37 	ECCReqPending = 0x80000000u,

    38 	ECCReqDeferred = 0x40000000u,

    39 	ECCPowerUpInProgress = 0x20000000u,

    40 	ECCPowerDownInProgress = 0x10000000u,

    41 	ECCRebalanceRequired = 0x08000000u,

    42 	ECCRebalanceTimerQueued = 0x04000000u,

    43 	ECCPeriodicBalancingActive = 0x02000000u,

    44 	};

    45 

    46 const TUint K_CpuMask	= 0x1fu;

    47 const TUint K_Keep		= 0x20u;

    48 const TUint K_SameCpu	= 0x40u;

    49 const TUint K_NewCpu	= 0x80u;

    50 const TUint K_CpuSticky	= 0x40u;

    51 const TUint K_CheckCpu	= 0x100u;

    52 

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

    54 

    55 const TUint K_LB_HeavyThreshold					= PERCENT(4095, 90);

    56 const TUint K_LB_GravelThreshold_RunAvg			= PERCENT(4095, 1);

    57 const TUint K_LB_GravelThreshold_RunActAvg		= PERCENT(4095, 50);

    58 const TInt	K_LB_HeavyCapacityThreshold			= PERCENT(4095, 1);

    59 const TInt	K_LB_BalanceInterval				= 107;

    60 const TInt	K_LB_CpuLoadDiffThreshold			= 128;

    61 

    62 //const TUint K_LB_HeavyStateThreshold			= 128;

    63 const TUint K_LB_HeavyPriorityThreshold			= 25;

    64 

    65 inline TBool IsHeavy(NSchedulable* a)

    66 	{

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

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

    69 	}

    70 

    71 inline TBool IsNew(NSchedulable* a)

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

    73 

    74 struct SPerPri : public SDblQue

    75 	{

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

    77 

    78 	TUint32	iTotalRun;

    79 	TUint32	iTotalAct;

    80 	TUint16	iCount;

    81 	TUint16	iHeavy;

    82 	};

    83 

    84 struct SCpuAvailability

    85 	{

    86 	enum

    87 		{

    88 		EIdle = 4095,

    89 		EMaxedOut = -268435456,

    90 		EUnavailable = KMinTInt

    91 		};

    92 

    93 	void	Init(TUint32 aActive);

    94 	TInt	FindMax() const;

    95 	TInt	FindMax(NSchedulable* aS) const;

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

    97 	TInt	SetMaxed(TInt aCpu);

    98 	void	AddLoad(TInt aCpu, TInt aLoad);

    99 	inline	TInt operator[](TInt aCpu) const

   100 		{	return iRemain[aCpu]; }

   101 	inline	TInt TotalRemain() const

   102 		{	return iTotalRemain; }

   103 

   104 	TInt	iRemain[KMaxCpus];

   105 	TInt	iCount;

   106 	TInt	iTotalRemain;

   107 	};

   108 

   109 TUint32 HotWarmUnit;

   110 TUint32 LB_DormantThreshold;

   111 volatile TUint32 LBDelayed = 0;

   112 

   113 void CalcHotWarm(TUint8& aOut, TUint64 aTime)

   114 	{

   115 	TUint8 out = 0;

   116 	if (aTime>0)

   117 		{

   118 		aTime /= TUint64(HotWarmUnit);

   119 		if (I64HIGH(aTime))

   120 			out = 255;

   121 		else

   122 			{

   123 			aTime *= aTime;

   124 			out = __e32_find_ms1_64(aTime) + 1;

   125 			}

   126 		}

   127 	aOut = (TUint8)out;

   128 	}

   129 

   130 void TScheduler::InitLB()

   131 	{

   132 	TScheduler& s = TheScheduler;

   133 	TDfcQue* rbQ = s.iRebalanceDfcQ;

   134 	s.iBalanceTimer.SetDfcQ(rbQ);

   135 	s.iCCReactivateDfc.SetDfcQ(rbQ);

   136 	s.iCCRequestDfc.SetDfcQ(rbQ);

   137 	s.iCCPowerDownDfc.SetDfcQ(rbQ);

   138 	NThreadBase* lbt = rbQ->iThread;

   139 	lbt->iRebalanceAttr = 1;

   140 	TUint32 f = NKern::CpuTimeMeasFreq();

   141 	HotWarmUnit = f / 1000000;

   142 	TUint8 y = 0;

   143 	CalcHotWarm(y, f/5);

   144 	LB_DormantThreshold = y;

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

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

   147 	}

   148 

   149 void TSubScheduler::GetLbThreads(SDblQue& aQ)

   150 	{

   151 	NKern::Lock();

   152 	iReadyListLock.LockOnly();

   153 	if (!iLbQ.IsEmpty())

   154 		{

   155 		aQ.MoveFrom(&iLbQ);

   156 		iLbCounter ^= NSchedulable::ELbState_Generation;

   157 		}

   158 	iReadyListLock.UnlockOnly();

   159 	NKern::Unlock();

   160 	}

   161 

   162 void TScheduler::GetLbThreads(SDblQue& aQ)

   163 	{

   164 	NKern::Lock();

   165 	iBalanceListLock.LockOnly();

   166 	if (!iBalanceList.IsEmpty())

   167 		{

   168 		aQ.MoveFrom(&iBalanceList);

   169 		iLbCounter ^= NSchedulable::ELbState_Generation;

   170 		}

   171 	iBalanceListLock.UnlockOnly();

   172 	NKern::Unlock();

   173 	}

   174 

   175 void NSchedulable::InitLbInfo()

   176 	{

   177 	}

   178 

   179 void NSchedulable::NominalPriorityChanged()

   180 	{

   181 	}

   182 

   183 void NSchedulable::LbDone(TUint aFlags)

   184 	{

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

   186 #ifdef KSCHED3

   187 	if (IsGroup())

   188 		{

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

   190 		}

   191 	else

   192 		{

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

   194 		}

   195 #endif

   196 	TBool keep = aFlags & K_Keep;

   197 	TInt cpu = aFlags & K_CpuMask;

   198 	TBool setcpu = aFlags & K_NewCpu;

   199 	TBool keepcpu = aFlags & K_SameCpu;

   200 	TBool checkcpu = aFlags & K_CheckCpu;

   201 	LAcqSLock();

   202 	TBool died = iLbState & ELbState_ExtraRef;

   203 	if (keep && !died)

   204 		{

   205 		TScheduler& s = TheScheduler;

   206 		s.iBalanceListLock.LockOnly();

   207 		s.iBalanceList.Add(&iLbLink);

   208 		iLbState = s.iLbCounter;

   209 		s.iBalanceListLock.UnlockOnly();

   210 		if (setcpu)

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

   212 		else

   213 			{

   214 			if (!keepcpu)

   215 				iPreferredCpu = 0;

   216 			if (checkcpu)

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

   218 			}

   219 		}

   220 	else

   221 		{

   222 		if (!keepcpu)

   223 			iPreferredCpu = 0;

   224 		iLbState = ELbState_Inactive;

   225 		iLbLink.iNext = 0;

   226 		iLbInfo.iRecentTime.i64 = 0;

   227 		iLbInfo.iRecentCpuTime.i64 = 0;

   228 		iLbInfo.iRecentActiveTime.i64 = 0;

   229 		iLbInfo.iLbRunAvg = 0;

   230 		iLbInfo.iLbActAvg = 0;

   231 		iLbInfo.iLbRunActAvg = 0;

   232 		if (checkcpu && !died)

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

   234 		}

   235 	RelSLockU();

   236 	if (died)

   237 		{

   238 		NKern::Lock();

   239 		DropRef();

   240 		NKern::Unlock();

   241 		}

   242 	}

   243 

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

   245 	{

   246 	TInt ms1 = __e32_find_ms1_64(aD);

   247 	if (ms1 < 0)

   248 		{

   249 		aRatio = 4095;

   250 		return;

   251 		}

   252 	if (ms1 >= 20)

   253 		{

   254 		TInt shift = ms1 - 19;

   255 		aD >>= shift;

   256 		aN >>= shift;

   257 		}

   258 	// aD, aN now < 2^20

   259 	TUint32 d = I64LOW(aD);

   260 	TUint32 n = I64LOW(aN);

   261 	if (n>d) n=d;

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

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

   264 	aRatio = (TUint16)r;

   265 	}

   266 

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

   268 	{

   269 	TInt ms1 = __e32_find_ms1_64(aDT);

   270 	if (ms1 >= 20)

   271 		{

   272 		TInt shift = ms1 - 19;

   273 		aDT >>= shift;

   274 		aDR >>= shift;

   275 		aDA >>= shift;

   276 		}

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

   278 	TUint32 t = I64LOW(aDT);

   279 	TUint32 rtd = I64LOW(aDR);

   280 	TUint32 atd = I64LOW(aDA);

   281 	if (rtd>t) rtd=t;

   282 	if (atd>t) atd=t;

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

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

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

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

   287 	aRT = (TUint16)rtt;

   288 	aAT = (TUint16)att;

   289 	aRA = (TUint16)rta;

   290 	}

   291 

   292 void NSchedulable::GetLbStats(TUint64 aTime)

   293 	{

   294 	SCpuStats stats;

   295 	LAcqSLock();

   296 	if (IsGroup())

   297 		{

   298 		NThreadGroup* g = (NThreadGroup*)this;

   299 		if (g->iNThreadList.IsEmpty())

   300 			iLbInfo.iLbNomPri = 1;

   301 		else

   302 			{

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

   304 			iLbInfo.iLbNomPri = t->iNominalPri;

   305 			}

   306 		}

   307 	else

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

   309 	GetCpuStatsT(E_AllStats, stats);

   310 	iLbInfo.iRecentTime.i64 += aTime;

   311 	iLbInfo.iRecentCpuTime.i64 += stats.iRunTimeDelta;

   312 	iLbInfo.iRecentActiveTime.i64 += stats.iActiveTimeDelta;

   313 	TUint32 aff = iCpuAffinity;

   314 	RelSLockU();

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

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

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

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

   319 

   320 	if (aff & NTHREADBASE_CPU_AFFINITY_MASK)

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

   322 	else

   323 		iLbInfo.iLbAffinity = 1u << aff;

   324 	CalcHotWarm(iLbInfo.iLbHot, stats.iLastRunTime);

   325 	CalcHotWarm(iLbInfo.iLbWarm, stats.iLastActiveTime);

   326 	if (IsNew(this))

   327 		{

   328 		if (iLbInfo.iLbNomPri <= K_LB_HeavyPriorityThreshold)

   329 			iLbInfo.iLbHeavy = 0xffu;

   330 		else

   331 			iLbInfo.iLbHeavy = 0;

   332 		}

   333 	iLbInfo.iLbHeavy >>= 1;

   334 	if (iLbInfo.iLbActTime > K_LB_HeavyThreshold)

   335 		iLbInfo.iLbHeavy |= 0x80u;

   336 /*

   337 	TUint64 blx = NKern::CpuTimeMeasFreq();

   338 	blx *= 3;

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

   340 		{

   341 		__crash();

   342 		}

   343 */	}

   344 

   345 void AddToSortedQueue(SPerPri* aQ, NSchedulable* aS)

   346 	{

   347 	TInt k = aS->iLbInfo.iLbNomPri;

   348 	if (k >= KNumPriorities)

   349 		k = KNumPriorities;

   350 	SPerPri* q = aQ + k;

   351 	TBool h = IsHeavy(aS);

   352 	SDblQueLink* anchor = &q->iA;

   353 	SDblQueLink* p = q->First();

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

   355 		{

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

   357 		if (h)

   358 			{

   359 			if (!IsHeavy(s))

   360 				continue;

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

   362 				break;

   363 			}

   364 		else

   365 			{

   366 			if (IsHeavy(s))

   367 				break;

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

   369 				break;

   370 			}

   371 		}

   372 	aS->iLbLink.InsertBefore(p);

   373 	++q->iCount;

   374 	if (h)

   375 		{

   376 		++q->iHeavy;

   377 		}

   378 	else

   379 		{

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

   381 		if (q->iTotalRun>4095)

   382 			q->iTotalRun=4095;

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

   384 		}

   385 	}

   386 

   387 void SCpuAvailability::Init(TUint32 a)

   388 	{

   389 	iCount = __e32_find_ms1_32(a) + 1;

   390 	iTotalRemain = 0;

   391 	TInt i;

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

   393 		{

   394 		if (a & (1<<i))

   395 			{

   396 			iRemain[i] = EIdle;

   397 			iTotalRemain += EIdle;

   398 			}

   399 		else

   400 			iRemain[i] = EUnavailable;

   401 		}

   402 	}

   403 

   404 TInt SCpuAvailability::SetMaxed(TInt aCpu)

   405 	{

   406 	TInt x = iRemain[aCpu];

   407 	if (x>0)

   408 		iTotalRemain -= x;

   409 	iRemain[aCpu] = EMaxedOut;

   410 	return x;

   411 	}

   412 

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

   414 	{

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

   416 		__crash();

   417 	TInt& x = iRemain[aCpu];

   418 	TInt orig = x;

   419 	x -= aLoad;

   420 	if (x < EMaxedOut)

   421 		x = EMaxedOut;

   422 	if (orig > 0)

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

   424 	}

   425 

   426 TInt SCpuAvailability::FindMax() const

   427 	{

   428 	TInt maxv = KMinTInt;

   429 	TInt maxi = -1;

   430 	TInt i;

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

   432 		{

   433 		if (iRemain[i] > maxv)

   434 			{

   435 			maxv = iRemain[i];

   436 			maxi = i;

   437 			}

   438 		}

   439 	return maxi;

   440 	}

   441 

   442 TInt SCpuAvailability::FindMax(NSchedulable* aS) const

   443 	{

   444 	TUint32 s = aS->iLbInfo.iLbAffinity;

   445 	s &= TheScheduler.iThreadAcceptCpus;

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

   447 		return __e32_find_ms1_32(s);

   448 	TInt maxv = KMinTInt;

   449 	TInt maxi = -1;

   450 	TInt i = 0;

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

   452 		{

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

   454 			{

   455 			maxv = iRemain[i];

   456 			maxi = i;

   457 			}

   458 		}

   459 	return maxi;

   460 	}

   461 

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

   463 	{

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

   465 	TUint32 s = s0;

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

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

   468 		return __e32_find_ms1_32(s);

   469 	TInt maxv = KMinTInt;

   470 	TInt maxi = -1;

   471 	TInt i = 0;

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

   473 		{

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

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

   476 			{

   477 			maxv = iRemain[i];

   478 			maxi = i;

   479 			}

   480 		}

   481 	if (IsNew(aS))

   482 		{

   483 		// this thread hasn't run for a while

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

   485 		i = __e32_find_ms1_32(s0);

   486 		for (; i>maxi; --i)

   487 			{

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

   489 				return i;

   490 			}

   491 		}

   492 	else

   493 		{

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

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

   496 		TInt lcpu = aS->iLastCpu;

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

   498 			return lcpu;

   499 		}

   500 	// use highest availability CPU

   501 	return maxi;

   502 	}

   503 

   504 void TScheduler::BalanceTimerExpired(TAny* aPtr)

   505 	{

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

   507 	}

   508 

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

   510 	{

   511 	ModifyCCState(~ECCRebalanceRequired, 0);

   512 

   513 	SPerPri sbq[KNumPriorities+1];

   514 	NSchedulable* s = 0;

   515 	TInt i;

   516 	TUint64 now = NKern::Timestamp();

   517 	TUint64 lbt = iLastBalanceTime;

   518 	iLastBalanceTime = now;

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

   520 	TUint cc = aCC ? K_CheckCpu : 0;

   521 

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

   523 

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

   525 	TInt ns = 0;	// number for further consideration

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

   527 	SCpuAvailability avail;

   528 	avail.Init(iThreadAcceptCpus);

   529 	TUint32 gravel = 0;

   530 	TInt totalN = 0;

   531 	TInt checked = 0;

   532 	while (!aQ.IsEmpty())

   533 		{

   534 		NThread* t = 0;

   535 		++totalN;

   536 		s = _LOFF(aQ.First()->Deque(), NSchedulable, iLbLink);

   537 		if (!s->IsGroup())

   538 			{

   539 			t = (NThread*)s;

   540 			if (t->iRebalanceAttr & 1)

   541 				++checked;

   542 			}

   543 		s->GetLbStats(bpl);

   544 		if (

   545 			(s->iLbInfo.iLbWarm >= LB_DormantThreshold)	// hasn't run for a while

   546 		||	(s->iLbInfo.iLbWarm>0 && s->iLbInfo.iLbRunAvg<K_LB_GravelThreshold_RunAvg && s->iLbInfo.iLbRunActAvg>K_LB_GravelThreshold_RunActAvg)	// gravel

   547 		)

   548 			{

   549 			TUint32 a = s->iLbInfo.iLbAffinity;

   550 			if ( (a&(a-1)) == 0)

   551 				avail.AddLoad(__e32_find_ms1_32(a), s->iLbInfo.iLbRunAvg);

   552 			else

   553 				gravel += s->iLbInfo.iLbRunAvg;

   554 			if (!IsNew(s))

   555 				++nd;

   556 			s->LbDone(cc);		// drop it

   557 			}

   558 		else if (nact==1)

   559 			{

   560 			s->LbDone(cc|K_Keep);	// keep it but only 1 CPU so don't balance

   561 			}

   562 		else if (t && t->iCoreCycling)

   563 			{

   564 			s->LbDone(cc|K_Keep);	// keep it but don't balance

   565 			}

   566 		else

   567 			{

   568 			++ns;

   569 			AddToSortedQueue(&sbq[0], s);

   570 			}

   571 		}

   572 

   573 	gravel /= TUint(nact);

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

   575 		{

   576 		if (iThreadAcceptCpus & (1<<i))

   577 			avail.AddLoad(i, gravel);

   578 		}

   579 	if (ns>0)

   580 		{

   581 		TInt k;

   582 		for (k=KNumPriorities; k>=0; --k)

   583 			{

   584 			SPerPri& q = sbq[k];

   585 			if (q.iCount==0)

   586 				{

   587 				__NK_ASSERT_ALWAYS(q.IsEmpty());

   588 				continue;

   589 				}

   590 			if (nact==0)

   591 				goto dump_remaining;

   592 			while (!q.IsEmpty())

   593 				{

   594 				s = _LOFF(q.First(), NSchedulable, iLbLink);

   595 //				BTrace12(BTrace::EHSched, 0x80u, s, s->iLbInfo.iLbRunAvg, s->iLbInfo.iLbRunActAvg);

   596 				if (IsHeavy(s))

   597 					break;

   598 				s->iLbLink.Deque();

   599 				TInt cpu = avail.PickCpu(s, nd);

   600 //				BTrace12(BTrace::EHSched, 0x81u, cpu, remain[cpu], totalremain);

   601 				avail.AddLoad(cpu, s->iLbInfo.iLbRunAvg);

   602 //				BTrace8(BTrace::EHSched, 0x82u, remain[cpu], totalremain);

   603 				s->LbDone(cc|K_Keep|K_NewCpu|cpu);

   604 				}

   605 			if (q.iHeavy > nact)

   606 				{

   607 				TInt hr = avail.TotalRemain() / q.iHeavy;

   608 				TInt n = q.iHeavy;

   609 				TInt j;

   610 				for (j=0; j<nact; ++j)

   611 					{

   612 					// don't bother about keeping same CPU since we must rotate

   613 					// threads between CPUs to even out the run times.

   614 					TInt cpu = avail.FindMax();

   615 //					BTrace12(BTrace::EHSched, 0x83u, cpu, remain[cpu], totalremain);

   616 					TInt capacity = avail.SetMaxed(cpu);

   617 //					BTrace8(BTrace::EHSched, 0x84u, remain[cpu], totalremain);

   618 					TInt nh = 0;

   619 					if (hr > K_LB_HeavyCapacityThreshold)

   620 						{

   621 						if (j == nact-1)

   622 							nh = n;

   623 						else

   624 							nh = capacity / hr;

   625 						}

   626 					else

   627 						nh = n / (nact-j);

   628 					n -= nh;

   629 					for (; nh>0; --nh)

   630 						{

   631 						if (q.IsEmpty())

   632 							__crash();

   633 						s = _LOFF(q.First()->Deque(), NSchedulable, iLbLink);

   634 						s->LbDone(cc|K_Keep|K_NewCpu|cpu);

   635 						}

   636 					}

   637 				nact = 0;

   638 				}

   639 			else

   640 				{

   641 				while (!q.IsEmpty())

   642 					{

   643 					s = _LOFF(q.First()->Deque(), NSchedulable, iLbLink);

   644 					TInt cpu = avail.PickCpu(s, nd);

   645 //					BTrace12(BTrace::EHSched, 0x85u, cpu, remain[cpu], totalremain);

   646 					avail.SetMaxed(cpu);

   647 //					BTrace8(BTrace::EHSched, 0x86u, remain[cpu], totalremain);

   648 					s->LbDone(cc|K_Keep|K_NewCpu|cpu);

   649 					--nact;

   650 					}

   651 				}

   652 			__NK_ASSERT_ALWAYS(q.IsEmpty());

   653 			if (nact==0)

   654 				{

   655 dump_remaining:

   656 				while (!q.IsEmpty())

   657 					{

   658 //					BTrace4(BTrace::EHSched, 0x87u, s);

   659 					s = _LOFF(q.First()->Deque(), NSchedulable, iLbLink);

   660 					s->LbDone(cc|K_Keep);	// keep it but lose preferred CPU

   661 					}

   662 				continue;

   663 				}

   664 			}

   665 		}

   666 

   667 	// return TRUE if the only threads which ran were this one and the NTimer thread

   668 	return (totalN==2 && checked==2);

   669 	}

   670 

   671 void TScheduler::PeriodicBalance()

   672 	{

   673 	iNeedBal = 0;

   674 	ModifyCCState( ~ECCRebalanceTimerQueued, 0 );

   675 	SDblQue rbq;	// raw balance queue

   676 	GetLbThreads(rbq);

   677 	TInt i;

   678 	for (i=0; i<iNumCpus; ++i)

   679 		iSub[i]->GetLbThreads(rbq);

   680 	TBool bored = ReBalance(rbq, FALSE);

   681 	if (!bored || iNeedBal)

   682 		StartRebalanceTimer(FALSE);

   683 	}

   684 

   685 

   686 void TScheduler::StartPeriodicBalancing()

   687 	{

   688 #ifdef KBOOT

   689 	__KTRACE_OPT(KBOOT,DEBUGPRINT("StartPeriodicBalancing()"));

   690 	TInt i;

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

   692 		{

   693 		TSubScheduler& ss = TheSubSchedulers[i];

   694 		volatile TUint32* p = (volatile TUint32*)ss.iUncached;

   695 		__KTRACE_OPT(KBOOT,DEBUGPRINT("CPU %1d: iUncached=%08x -> %08x %08x %08x %08x", i, p, p[0], p[1], p[2], p[3]));

   696 		}

   697 #endif

   698 	TheScheduler.StartRebalanceTimer(TRUE);

   699 	}

   700 

   701 void TScheduler::StartRebalanceTimer(TBool aRestart)

   702 	{

   703 	TInt interval = K_LB_BalanceInterval;

   704 	TUint32 mask = aRestart ? (ECCRebalanceTimerQueued|ECCPeriodicBalancingActive) : (ECCRebalanceTimerQueued);

   705 	TUint32 orig = ModifyCCState(~mask, mask);

   706 	TUint32 ns = (orig &~ mask) ^ mask;

   707 	__KTRACE_OPT(KSCHED3,DEBUGPRINT("StrtRbTmr %08x %08x %08x", mask, orig, ns));

   708 	if ((ns & ECCPeriodicBalancingActive) && !(orig & ECCRebalanceTimerQueued))

   709 		{

   710 		TInt r = KErrArgument;

   711 		if (orig & ECCPeriodicBalancingActive)

   712 			{

   713 			r = iBalanceTimer.Again(interval);

   714 			if (r == KErrArgument)

   715 				{

   716 				++LBDelayed;	// so we can see if this happened

   717 				}

   718 			}

   719 		if (r == KErrArgument)

   720 			{

   721 			r = iBalanceTimer.OneShot(interval);

   722 			}

   723 		if (r != KErrNone)

   724 			__crash();

   725 		}

   726 	}

   727 

   728 void TScheduler::StopRebalanceTimer(TBool aTemp)

   729 	{

   730 	TUint32 mask = aTemp ? ECCRebalanceTimerQueued : (ECCRebalanceTimerQueued|ECCPeriodicBalancingActive);

   731 	TUint32 orig = ModifyCCState(~mask, 0);

   732 	__KTRACE_OPT(KSCHED3,DEBUGPRINT("StopRbTmr %08x %08x", mask, orig));

   733 	if (orig & ECCRebalanceTimerQueued)

   734 		iBalanceTimer.Cancel();

   735 	}

   736 

   737 

   738 

   739 /******************************************************************************

   740  * Core Control

   741  ******************************************************************************/

   742 

   743 /*

   744 

   745 TScheduler fields used for core control:

   746 

   747 iThreadAcceptCpus

   748 	Bit n = 1 iff CPU n is available to threads with no specific affinity.

   749 	Bits corresponding to existing CPUs are set at boot time.

   750 	Subsequently this word is only modified by load balancer thread.

   751 	Bit n is cleared when a decision is made to shut down core n.

   752 

   753 

   754 iIpiAcceptCpus

   755 	Bit n = 1 iff CPU n is accepting generic IPIs

   756 	Bits corresponding to existing CPUs are set at boot time.

   757 	Bit n is cleared when CPU n makes the decision to ask the idle handler to power down

   758 		At the same time, bit n of iCpusGoingDown is set.

   759 	Bit n is set when CPU n returns from the idle handler after waking up.

   760 	Protected by iGenIPILock

   761 

   762 iCpusComingUp

   763 	Bit n = 1 iff CPU n is in the process of powering up

   764 	All bits zero at boot

   765 	Bit n set when the load balancer decides to initiate power up of CPU n, provided iCCDeferCount==0

   766 	Bit n cleared when the load balancer sets iThreadAcceptCpus bit n

   767 	Protected by iGenIPILock

   768 

   769 iCpusGoingDown

   770 	Bit n = 1 iff CPU n is in the process of powering down and is no longer accepting IPIs

   771 	All bits zero at boot

   772 	Bit n is set when CPU n makes the decision to ask the idle handler to power down

   773 	?Bit n is cleared when?

   774 		- when TCoreCycler observes the CPU has detached

   775 		- when the load balancer observes the CPU has detached

   776 		- when the load balancer decides to reactivate the CPU

   777 	Protected by iGenIPILock

   778 

   779 iCCDeferCount

   780 	If this is positive CPUs being shut down will not proceed to clear iIpiAcceptCpus

   781 	In this case bits can be set in iIpiAcceptCpus but cannot be cleared.

   782 	Also (iIpiAcceptCpus|iCpusComingUp) remains constant

   783 	Protected by iGenIPILock

   784 

   785 iCCSyncCpus

   786 	Bit n = 1 iff a change has been made to iThreadAcceptCpus which CPU n should observe

   787 	but it has not yet observed it.

   788 	Bit n set by the load balancer after a change is made to iThreadAcceptCpus, provided bit n

   789 	is also set in iIpiAcceptCpus.

   790 	Bit n cleared when CPU n services the core control sync IPI if iKernCSLocked==0 or the

   791 	next time iKernCSLocked becomes zero otherwise.

   792 

   793 iCCReactivateCpus

   794 	Bit n = 1 if CPU n is being reactivated after being removed from iThreadAcceptCpus

   795 	Bit n is set if a thread is made ready, cannot be assigned to any active CPU on

   796 		account of affinity restrictions and is assigned to CPU n.

   797 	Bit n is also set when CPU n wakes up from being retired.

   798 	Protected by iGenIPILock

   799 

   800 iCCState

   801 	Bit 31 (ECCReqPending)	Set when an external request to change the number of cores is in progress

   802 

   803 iCCRequestLevel

   804 	The number of CPUs last requested to be active.

   805 

   806 iGenIPILock

   807 

   808 iCCSyncIDFC

   809 	Runs when all CPUs have observed a change to iThreadAcceptCpus

   810 

   811 iCCReactivateDfc

   812 	Runs whenever one or more bits have been set in iCCReactivateCpus

   813 

   814 iCCRequestDfc

   815 	Runs whenever a request is received to change the number of active cores

   816 

   817 TSubScheduler fields used for core control:

   818 

   819 

   820 */

   821 

   822 void TScheduler::CCUnDefer()

   823 	{

   824 	TUint32 powerOn = 0;

   825 	TBool doDeferredReq = FALSE;

   826 	TInt irq = iGenIPILock.LockIrqSave();

   827 	if (--iCCDeferCount == 0)

   828 		{

   829 		// Kick cores waiting to power off

   830 		__holler();

   831 

   832 		// See if any cores are waiting to power on

   833 		powerOn = iCCReactivateCpus &~ iCpusComingUp;

   834 

   835 		// See if a core control request has been deferred

   836 		if (iCCState & ECCReqDeferred)

   837 			{

   838 			if (iCpusComingUp==0 && iCCReactivateCpus==0)

   839 				doDeferredReq = TRUE;

   840 			}

   841 		}

   842 	iGenIPILock.UnlockIrqRestore(irq);

   843 	if (powerOn)

   844 		iCCReactivateDfc.Enque();

   845 	if (doDeferredReq)

   846 		iCCRequestDfc.Enque();

   847 	}

   848 

   849 void TScheduler::CCSyncDone(TAny* aPtr)

   850 	{

   851 	NFastSemaphore* s = (NFastSemaphore*)aPtr;

   852 	s->Signal();

   853 	}

   854 

   855 void CCSyncIPI(TGenericIPI*)

   856 	{

   857 	TScheduler& s = TheScheduler;

   858 	TSubScheduler& ss = SubScheduler();

   859 	if (ss.iKernLockCount)

   860 		{

   861 		ss.iCCSyncPending = 1;

   862 		ss.iRescheduleNeededFlag = 1;

   863 		return;

   864 		}

   865 	TUint32 m = ss.iCpuMask;

   866 	if (__e32_atomic_and_ord32(&s.iCCSyncCpus, ~m)==m)

   867 		{

   868 		s.iCCSyncIDFC.Add();

   869 		}

   870 	}

   871 

   872 void TScheduler::ChangeThreadAcceptCpus(TUint32 aNewMask)

   873 	{

   874 	NThread* lbt = LBThread();

   875 	if (NKern::CurrentThread() != lbt)

   876 		__crash();

   877 	TInt irq = iGenIPILock.LockIrqSave();

   878 	++iCCDeferCount;

   879 	iThreadAcceptCpus = aNewMask;

   880 	TUint32 cpus = iIpiAcceptCpus;

   881 	iCCSyncCpus = cpus;

   882 	iCpusComingUp &= ~aNewMask;

   883 	iGenIPILock.UnlockIrqRestore(irq);

   884 

   885 	NFastSemaphore sem(0);

   886 	iCCSyncIDFC.iPtr = &sem;

   887 	TGenericIPI ipi;

   888 	ipi.Queue(&CCSyncIPI, cpus);

   889 

   890 	NKern::FSWait(&sem);

   891 	CCUnDefer();

   892 	}

   893 

   894 template<int N> struct Log2 {};

   895 

   896 TEMPLATE_SPECIALIZATION struct Log2<1> { enum {Log=0u}; };

   897 TEMPLATE_SPECIALIZATION struct Log2<2> { enum {Log=1u}; };

   898 TEMPLATE_SPECIALIZATION struct Log2<4> { enum {Log=2u}; };

   899 TEMPLATE_SPECIALIZATION struct Log2<8> { enum {Log=3u}; };

   900 TEMPLATE_SPECIALIZATION struct Log2<16> { enum {Log=4u}; };

   901 TEMPLATE_SPECIALIZATION struct Log2<32> { enum {Log=5u}; };

   902 

   903 

   904 class TCpuSet

   905 	{

   906 public:

   907 	enum {

   908 		EBitsPerTUint8Shift=3u,

   909 		EBitsPerTUint32Shift=EBitsPerTUint8Shift+Log2<sizeof(TUint32)>::Log,

   910 		EBitsPerTUint8=1u<<EBitsPerTUint8Shift,

   911 		EBitsPerTUint32=1u<<EBitsPerTUint32Shift,

   912 		EWords=1u<<(KMaxCpus-EBitsPerTUint32Shift),

   913 		EBytes=1u<<(KMaxCpus-EBitsPerTUint8Shift),

   914 		EBits=1u<<KMaxCpus,

   915 		};

   916 public:

   917 	TCpuSet(TUint32 aMask);

   918 	void Consider(TUint32 aAffinity);

   919 	TCpuSet& operator&=(const TCpuSet&);

   920 	TCpuSet& operator|=(const TCpuSet&);

   921 	TCpuSet& Not();

   922 	TBool IsEmpty() const;

   923 	TInt Profile(TInt* aOut) const;

   924 	TUint32 Select(TInt aDesiredNumber, TUint32 aCurrent, TUint32 aIgnore) const;

   925 private:

   926 	/**

   927 	Bitfield: Bit n	= bit (n%8) of byte INT(n/8)

   928 					= bit (n%32) of word INT(n/32)

   929 	Bit n is set if the subset S of CPUs represented by the bits of n in the

   930 	canonical way (i.e. x \in S <=> bit x of n = 1) is acceptable.

   931 	*/

   932 	TUint32	iMask[EWords];

   933 	};

   934 

   935 TCpuSet::TCpuSet(TUint32 aM)

   936 	{

   937 	memset(iMask, 0, sizeof(iMask));

   938 	TInt i;

   939 	TUint32 m=1;	// empty set only

   940 	for (i=0; i<EBitsPerTUint32Shift; ++i)

   941 		{

   942 		TUint32 ibit = 1u<<i;

   943 		if (aM & ibit)

   944 			m |= (m<<ibit);

   945 		}

   946 	iMask[0] = m;

   947 	for (; i<KMaxCpus; ++i)

   948 		{

   949 		TUint32 ibit = 1u<<i;

   950 		if (aM & ibit)

   951 			{

   952 			TInt ws = 1<<(i-EBitsPerTUint32Shift);

   953 			TInt j;

   954 			for (j=0; j<ws; ++j)

   955 				iMask[ws+j] = iMask[j];

   956 			}

   957 		}

   958 	}

   959 

   960 TCpuSet& TCpuSet::operator&=(const TCpuSet& aS)

   961 	{

   962 	TInt i;

   963 	for (i=0; i<EWords; ++i)

   964 		iMask[i] &= aS.iMask[i];

   965 	return *this;

   966 	}

   967 

   968 TCpuSet& TCpuSet::operator|=(const TCpuSet& aS)

   969 	{

   970 	TInt i;

   971 	for (i=0; i<EWords; ++i)

   972 		iMask[i] |= aS.iMask[i];

   973 	return *this;

   974 	}

   975 

   976 TCpuSet& TCpuSet::Not()

   977 	{

   978 	TInt i;

   979 	for (i=0; i<EWords; ++i)

   980 		iMask[i] = ~iMask[i];

   981 	return *this;

   982 	}

   983 

   984 TBool TCpuSet::IsEmpty() const

   985 	{

   986 	TInt i;

   987 	TUint32 x = 0;

   988 	for (i=0; i<EWords; ++i)

   989 		x |= iMask[i];

   990 	return !x;

   991 	}

   992 

   993 void TCpuSet::Consider(TUint32 aAffinity)

   994 	{

   995 	TUint32 am = AffinityToMask(aAffinity);

   996 	am &= EBits-1;

   997 	if (am == EBits-1 || am==0)

   998 		return;	// no restrictions

   999 

  1000 	TCpuSet bad(am ^ (EBits-1));	// sets incompatible with aAffinity

  1001 	TInt i;

  1002 	for (i=0; i<EWords; ++i)

  1003 		iMask[i] &= ~bad.iMask[i];	// knock out sets incompatible with aAffinity

  1004 	}

  1005 

  1006 const TUint32 Pmask[6] =

  1007 	{

  1008 	0x00000001,			// no bits set

  1009 	0x00010116,			// 1 bit set (10000, 01000, 00100, 00010, 00001 -> 16,8,4,2,1)

  1010 	0x01161668,			// 2 bits set (11000, 10100, 10010, 10001, 01100, 01010, 01001, 00110, 00101, 00011 -> 24,20,18,17,12,10,9,6,5,3)

  1011 	0x16686880,			// 3 bits set (11100, 11010, 11001, 10110, 10101, 10011, 01110, 01101, 01011, 00111 -> 28,26,25,22,21,19,14,13,11,7)

  1012 	0x68808000,			// 4 bits set (11110, 11101, 11011, 10111, 01111 -> 30,29,27,23,15)

  1013 	0x80000000			// 5 bits set

  1014 	};

  1015 

  1016 /**

  1017 	Sets aOut[n] = number of entries with n CPUs present (0<=n<=KMaxCpus)

  1018 	Returns total number of entries

  1019 */

  1020 TInt TCpuSet::Profile(TInt* aOut) const

  1021 	{

  1022 	TInt i,j;

  1023 	TInt r = 0;

  1024 	memset(aOut, 0, (KMaxCpus+1)*sizeof(TInt));

  1025 	for (i=0; i<EWords; ++i)

  1026 		{

  1027 		TUint32 m = iMask[i];

  1028 		if (!m)

  1029 			continue;

  1030 		TInt n1 = __e32_bit_count_32(i);

  1031 		for (j=0; j<=EBitsPerTUint32Shift; ++j)

  1032 			{

  1033 			TInt dr = __e32_bit_count_32(m & Pmask[j]);

  1034 			r += dr;

  1035 			aOut[n1+j] += dr;

  1036 			}

  1037 		}

  1038 	return r;

  1039 	}

  1040 

  1041 /**

  1042 	Given a desired number of active cores and the mask of currently

  1043 	running cores, returns the new mask of active cores.

  1044 */

  1045 TUint32 TCpuSet::Select(TInt aDesiredNumber, TUint32 aCurrent, TUint32 aIgnore) const

  1046 	{

  1047 	TInt max = __e32_bit_count_32(aCurrent);

  1048 	if (aDesiredNumber > max)

  1049 		return 0;

  1050 	TInt profile[KMaxCpus+1] = {0};

  1051 	Profile(profile);

  1052 	TInt dn;

  1053 	for (dn=aDesiredNumber; dn<=max && profile[dn]==0; ++dn)

  1054 		{}

  1055 	if (dn > max)

  1056 		return 0;

  1057 	TInt wix;

  1058 	TUint32 bestMask = 0;

  1059 	TInt bestDiff = KMaxTInt;

  1060 	TInt stop = max - dn;

  1061 	for (wix=0; wix<EWords; ++wix)

  1062 		{

  1063 		TUint32 candidate = wix << EBitsPerTUint32Shift;

  1064 		TUint32 m = iMask[wix];

  1065 		if (!m)

  1066 			continue;

  1067 		TInt n1 = __e32_bit_count_32(wix);

  1068 		if (n1 > dn)

  1069 			continue;

  1070 		m &= Pmask[dn-n1];

  1071 		for (; m; m>>=1, ++candidate)

  1072 			{

  1073 			if (!(m&1))

  1074 				continue;

  1075 			TUint32 diff = (candidate&~aIgnore) ^ aCurrent;

  1076 			TInt wt = __e32_bit_count_32(diff);

  1077 			if (wt < bestDiff)

  1078 				{

  1079 				bestDiff = wt;

  1080 				bestMask = candidate;

  1081 				if (bestDiff == stop)

  1082 					{

  1083 					wix = EWords;

  1084 					break;

  1085 					}

  1086 				}

  1087 			}

  1088 		}

  1089 	return bestMask;

  1090 	}

  1091 

  1092 void NSchedulable::LbTransfer(SDblQue& aDestQ)

  1093 	{

  1094 	if (iLbState & ELbState_PerCpu)

  1095 		{

  1096 		TSubScheduler* ss = &TheSubSchedulers[iLbState & ELbState_CpuMask];

  1097 		ss->iReadyListLock.LockOnly();

  1098 		if (iLbState == ss->iLbCounter)

  1099 			{

  1100 			iLbLink.Deque();

  1101 			}

  1102 		ss->iReadyListLock.UnlockOnly();

  1103 		}

  1104 	else if ((iLbState & ELbState_CpuMask) == ELbState_Global)

  1105 		{

  1106 		TScheduler& s = TheScheduler;

  1107 		s.iBalanceListLock.LockOnly();

  1108 		if (iLbState == s.iLbCounter)

  1109 			{

  1110 			iLbLink.Deque();

  1111 			}

  1112 		s.iBalanceListLock.UnlockOnly();

  1113 		}

  1114 	else if (iLbState != ELbState_Inactive)

  1115 		{

  1116 		// shouldn't happen

  1117 		__crash();

  1118 		}

  1119 	iLbState = ELbState_Temp;

  1120 	aDestQ.Add(&iLbLink);

  1121 	}

  1122 

  1123 void GetAll(SDblQue& aOutQ, SIterDQ* aInQ)

  1124 	{

  1125 	TScheduler& s = TheScheduler;

  1126 	SIterDQIterator iter;

  1127 	TInt maxSteps = NKern::NumberOfCpus() + 2;

  1128 	TInt r;

  1129 	NKern::Lock();

  1130 	s.iEnumerateLock.LockOnly();

  1131 	iter.Attach(aInQ);

  1132 	FOREVER

  1133 		{

  1134 		SIterDQLink* link = 0;