Received-SPF: pass (google.com: domain of linux-kernel+bounces-198363-linux.lists.archive=gmail.com@vger.kernel.org designates 139.178.88.99 as permitted sender) client-ip=139.178.88.99;
Date: Mon, 3 Jun 2024 00:40:26 +0800
From: Chen Yu <yu.c.chen@intel.com>
To: Tim Chen <tim.c.chen@linux.intel.com>
CC: Peter Zijlstra <peterz@infradead.org>, Ingo Molnar <mingo@redhat.com>,
	Vincent Guittot <vincent.guittot@linaro.org>, <linux-kernel@vger.kernel.org>,
	Vinicius Gomes <vinicius.gomes@intel.com>
Subject: Re: [PATCH] sched/balance: Skip unnecessary updates to idle load
 balancer's flags
Message-ID: <Zlygeqy+SVs1KZYW@chenyu5-mobl2>
References: <20240531205452.65781-1-tim.c.chen@linux.intel.com>
Content-Type: text/plain; charset="utf-8"
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <20240531205452.65781-1-tim.c.chen@linux.intel.com>
Precedence: bulk
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?utf-8?B?SDFvTzFySjREZitWS25KbXRsWWxoTjZ6SEFka0kvcjlQQ3Byc05pUlZxL01a?=
 =?utf-8?B?cW93S1kxbEd0ZndRaHgwQ0JLL2VjSUwvaVphNFlPK2orRys4eDJKeWNkUGQv?=
 =?utf-8?B?cWhsWjlUMXM1Tm1FYlV6NzRXSkVncjlOVE1hdWlCcU1WSXM3Q3RBYUN5RzZC?=
 =?utf-8?B?WDM1eHFEbTdEbHZNV3dUU0tuTmp4blVLNHNXeE81dkdGUTUvUHJUUVhsWm1E?=
 =?utf-8?B?dzM3QldITWZ2anY0VTkyQUplWThwRFRJVmJYeVN6SVpRdDZzR2FDSHhaQ29z?=
 =?utf-8?B?UXJMajZpbk14cXR4NVdXakxsbHR0ZDRxajJudjN5MUdIOUY1Q1RCaFRhOURF?=
 =?utf-8?B?ZkVjZVM2NXBiS0V3Zkg3bFNRVUViODJjNDRmTWwzeFpHcDJmTm04OEl6U3Ru?=
 =?utf-8?B?V1l6Y0JiYkhKWXh2NlZla0Zpakt6UG80cVNFRGR1dXpEY0trdUtSejVNWUh4?=
 =?utf-8?B?cWxwSmxkQUdHcUVBUGtJbWxOZHVnZGVaVXhXNmdzZnIrb2hhM1FlbzRLTUda?=
 =?utf-8?B?MnA5TnI3YXV2bDJWWXNHbzJtbmpKRWphMGdBU1Y3SVI0M25qSDllcGE5dmJR?=
 =?utf-8?B?YzArSnZpVlZlWllsayt2LzN1Wk8ybXVmalprUWtRd0RCZFI1ZlllNElrQVBi?=
 =?utf-8?B?VzZNUW4vOS95Tmp6OE9tZHJXWG1wTy9KTTF1OCt1WHIyVkc3R1Z5ZTBvYS84?=
 =?utf-8?B?c090S1plam91WVYzc3RPMFBzMFBDSFMxMTgzd2lQQXdzUUNYYlM0Q3FCcWwv?=
 =?utf-8?B?dTE5TTdXWjFNS1JEOGFTUEI5aTJ0QmI0V3I4NjVoRkdXVURYY0E4QjNGWFdD?=
 =?utf-8?B?THNQTHp1TWFYSXNKVCtqaVJ6aEpnRDd6MlNmOGVKSWY0SjF4WWcyZ1FEUlZ0?=
 =?utf-8?B?eGpWcC9POW0wWFhWUzhKRVk2bUcra0pUOW9ZcUVJVFVPMlYzT3J2MzJiOGN2?=
 =?utf-8?B?Qy82RTMzV2prYU9abWIycStoQ25vVWQzV09uekgySTV5Q1F5RmY0dzBKNzY3?=
 =?utf-8?B?eGVEWCttRDJRaFJET0pnc0RXMGlxL2lWblF5eTVJSVJyZlBOeVBmUjc0c0xs?=
 =?utf-8?B?aHg0V2VZZmt5dVR6TUJPWWRpL2o2cTdDekNuWEtmN1llY0dkQ1pmcHlYd3RO?=
 =?utf-8?B?bEtRVUZsY3NoS0pwZ3cyUE1mc2pmbmR2QWFXLzZRNFpxZzBoZmx1TE5UREZ1?=
 =?utf-8?B?VjljdDFvbWhRU1JxWVVuSitOak4rZEcrRjdka3NVVzg2RlNNT2xrUTk3R25U?=
 =?utf-8?B?NGtUNkNGazVRZndwb0JpZWRvZnFHVHZHK0RZNjhxY0czNmVxTXhmSzZKNmlI?=
 =?utf-8?B?YnlOZDRJMHc2ek9TN1orb2crRUNjTDUyUmlUZHR3WUFVdElSVUZCQlBoT052?=
 =?utf-8?B?dllvMnV4NWdRSEp3U3RBQ2YvWVhMWHIrNk1nZDM3RlUrT01yVGZpY01sOVVF?=
 =?utf-8?B?YWp0aDE1VUNPa1FsaENHQno4dzljWlQ4QjFIOFNSdnhMNEh1Q3BXVjlad0R1?=
 =?utf-8?B?NWhJekF0WXlFaWhzNGhSUE9KUTlUNURHV2xHNmIvUTFENUQ3endBYldIQ3Qv?=
 =?utf-8?B?MG1kRXZ5NTNCSHQyUkZ4QzZJRVFFbnhKS1ZQbmtyd0R5UHZCdklaRXlhVGlO?=
 =?utf-8?B?SWpJdERocXVzekNxbW1VZktGNisvbzFIWWRnd0N1V1FlTXBrZVBVUVh0Z2Jk?=
 =?utf-8?B?SFk0ZkhLZkpuallBdmhwWkpGeXhwa0pDZ1NEYlA1bUpvYVQvSU1lQ0tjSlJD?=
 =?utf-8?B?K3ZVY1lCSXJVam43QjJudU5Md1U0d0VubFNqSWdPbmVkM1lKbnVTa2M3OEs4?=
 =?utf-8?B?eVV3ZjhXc3ptVlJNWVR0UDVhdVE4WGRkTk9tZ2gwamR5S3NoY1F0ejdpaXoz?=
 =?utf-8?B?eDlrbUV4NEFDcU5QdERLa3EwdEZBNFFXcGd1ajEvUTVMLytLZ0dKclRabjNG?=
 =?utf-8?B?SThxeXp4Qmd1RllRNmdQN08yZS9BUy9pb3h2V1ZMR3hqWkRTbGNxejV6eWVB?=
 =?utf-8?B?UGd0VjM0d1k0UkhVNVY2ZFhCNiswVXBHcXRWczQwb0E0cElXN2wvclZZL1Fz?=
 =?utf-8?B?bnozcG8vaE15bGl3S2w0eUYyV0lkcXd3OXl0SHpPT0dCVmE5cFZQK2tPSWt0?=
 =?utf-8?Q?Qs3vzyPZro1B+HMPKW9SGlTEg?=
X-MS-Exchange-CrossTenant-Network-Message-Id: 4dda8cce-aefc-47c2-6c32-08dc8322ba45
X-MS-Exchange-CrossTenant-AuthSource: DM4PR11MB6020.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 02 Jun 2024 16:40:35.8434
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 46c98d88-e344-4ed4-8496-4ed7712e255d
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: fLCVp3WvQHa9lP/MxxEtiWXOR1/tufWOKJlNLZuUpKBP1R+aBVyZEdIm7AItNDfgIyITUZDimRSB+oxtmF4IrQ==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: CY8PR11MB6843
X-OriginatorOrg: intel.com

On 2024-05-31 at 13:54:52 -0700, Tim Chen wrote:
> We observed that the overhead on trigger_load_balance(), now renamed
> sched_balance_trigger(), has risen with a system's core counts.
> 
> For an OLTP workload running 6.8 kernel on a 2 socket x86 systems
> having 96 cores/socket, we saw that 0.7% cpu cycles are spent in
> trigger_load_balance(). On older systems with fewer cores/socket, this
> function's overhead was less than 0.1%.
> 
> The cause of this overhead was that there are multiple cpus calling
> kick_ilb(flags), updating the balancing work needed to a common idle
> load balancer cpu. The ilb_cpu's flags field got updated unconditionally
> with atomic_fetch_or().  The atomic read and writes to ilb_cpu's flags
> causes much cache bouncing and cpu cycles overhead. This is seen in the
> annotated profile below.
> 
>              kick_ilb():
>              if (ilb_cpu < 0)
>                test   %r14d,%r14d
>              ↑ js     6c
>              flags = atomic_fetch_or(flags, nohz_flags(ilb_cpu));
>                mov    $0x2d600,%rdi
>                movslq %r14d,%r8
>                mov    %rdi,%rdx
>                add    -0x7dd0c3e0(,%r8,8),%rdx
>              arch_atomic_read():
>   0.01         mov    0x64(%rdx),%esi
>  35.58         add    $0x64,%rdx
>              arch_atomic_fetch_or():
> 
>              static __always_inline int arch_atomic_fetch_or(int i, atomic_t *v)
>              {
>              int val = arch_atomic_read(v);
> 
>              do { } while (!arch_atomic_try_cmpxchg(v, &val, val | i));
>   0.03  157:   mov    %r12d,%ecx
>              arch_atomic_try_cmpxchg():
>              return arch_try_cmpxchg(&v->counter, old, new);
>   0.00         mov    %esi,%eax
>              arch_atomic_fetch_or():
>              do { } while (!arch_atomic_try_cmpxchg(v, &val, val | i));
>                or     %esi,%ecx
>              arch_atomic_try_cmpxchg():
>              return arch_try_cmpxchg(&v->counter, old, new);
>   0.01         lock   cmpxchg %ecx,(%rdx)
>  42.96       ↓ jne    2d2
>              kick_ilb():
> 
> With instrumentation, we found that 81% of the updates do not result in
> any change in the ilb_cpu's flags.  That is, multiple cpus are asking
> the ilb_cpu to do the same things over and over again, before the ilb_cpu
> has a chance to run NOHZ load balance.
> 
> Skip updates to ilb_cpu's flags if no new work needs to be done.
> Such updates do not change ilb_cpu's NOHZ flags.  This requires an extra
> atomic read but it is less expensive than frequent unnecessary atomic
> updates that generate cache bounces.

A race condition is that many CPUs choose the same ilb_cpu and ask it to trigger
the nohz idle balance. This is because find_new_ilb() always finds the first
nohz idle CPU. I wonder if we could change the
for_each_cpu_and(ilb_cpu, nohz.idle_cpus_mask, hk_mask)
into
for_each_cpu_wrap(ilb_cpu,  cpumask_and(nohz.idle_cpus_mask, hk_mask), this_cpu+1) 
so different ilb_cpu might be found by different CPUs.
Then the extra atomic read could brings less cache bounces.

> 
> We saw that on the OLTP workload, cpu cycles from trigger_load_balance()
> (or sched_balance_trigger()) got reduced from 0.7% to 0.2%.
> 
> Signed-off-by: Tim Chen <tim.c.chen@linux.intel.com>
> ---
>  kernel/sched/fair.c | 7 +++++++
>  1 file changed, 7 insertions(+)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 8a5b1ae0aa55..9ab6dff6d8ac 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -11891,6 +11891,13 @@ static void kick_ilb(unsigned int flags)
>  	if (ilb_cpu < 0)
>  		return;
>  
> +	/*
> +	 * Don't bother if no new NOHZ balance work items for ilb_cpu,
> +	 * i.e. all bits in flags are already set in ilb_cpu.
> +	 */
> +	if ((atomic_read(nohz_flags(ilb_cpu)) & flags) == flags)

Maybe also mention in the comment that when above statement is true, the
current ilb_cpu's flags is not 0 and in NOHZ_KICK_MASK, so return directly
here is safe(anyway just 2 cents)

Reviewed-by: Chen Yu <yu.c.chen@intel.com>

thanks,
Chenyu

> +		return;
> +
>  	/*
>  	 * Access to rq::nohz_csd is serialized by NOHZ_KICK_MASK; he who sets
>  	 * the first flag owns it; cleared by nohz_csd_func().
> -- 
> 2.32.0
>