Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Date:   Mon, 5 Dec 2022 16:40:12 +0800
From:   Chen Yu <yu.c.chen@intel.com>
To:     Tianchen Ding <dtcccc@linux.alibaba.com>
CC:     Juri Lelli <juri.lelli@redhat.com>,
        Rik van Riel <riel@surriel.com>,
        "Aaron Lu" <aaron.lu@intel.com>,
        Abel Wu <wuyun.abel@bytedance.com>,
        K Prateek Nayak <kprateek.nayak@amd.com>,
        Yicong Yang <yangyicong@hisilicon.com>,
        "Gautham R . Shenoy" <gautham.shenoy@amd.com>,
        Ingo Molnar <mingo@redhat.com>,
        "Dietmar Eggemann" <dietmar.eggemann@arm.com>,
        Steven Rostedt <rostedt@goodmis.org>,
        Ben Segall <bsegall@google.com>,
        Daniel Bristot de Oliveira <bristot@redhat.com>,
        Valentin Schneider <vschneid@redhat.com>,
        Hillf Danton <hdanton@sina.com>,
        Honglei Wang <wanghonglei@didichuxing.com>,
        Len Brown <len.brown@intel.com>,
        Chen Yu <yu.chen.surf@gmail.com>,
        Joel Fernandes <joel@joelfernandes.org>,
        Josh Don <joshdon@google.com>, <linux-kernel@vger.kernel.org>,
        kernel test robot <yujie.liu@intel.com>,
        Peter Zijlstra <peterz@infradead.org>,
        Vincent Guittot <vincent.guittot@linaro.org>,
        Tim Chen <tim.c.chen@intel.com>,
        Mel Gorman <mgorman@techsingularity.net>
Subject: Re: [PATCH v3 2/2] sched/fair: Choose the CPU where short task is
 running during wake up
Message-ID: <Y42ubFckJTOgiYyG@chenyu5-mobl1>
References: <cover.1669862147.git.yu.c.chen@intel.com>
 <0fefba11f59c083256eabff0fbb6c82b9d3bfdf9.1669862147.git.yu.c.chen@intel.com>
 <a71a227a-5f1b-8ebc-bfde-0babf267b7d9@linux.alibaba.com>
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
In-Reply-To: <a71a227a-5f1b-8ebc-bfde-0babf267b7d9@linux.alibaba.com>
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?8oRs5DklYr+p0U5KR5/7Cy/G6kaQP/l0xmK7TeZ/JlXqfTp/gPYXcQpMdMAy?=
 =?us-ascii?Q?e5yveEGHoSXUj2DdmgAMGXbIW6AqJdYbmGmuveACMe+b/cwJm7uLxmntDfxO?=
 =?us-ascii?Q?n7PjgGLl0ySKwv6X0580uCqgInWF8uvfmBw9HCk+jGWqqCwj83708Q5vTzC8?=
 =?us-ascii?Q?JDvxV5jf4bXgHafiyEX3O19wD31JceikJkmIwDNM7qzjNbB3jSg09hyPhaVQ?=
 =?us-ascii?Q?PZLOcF79lXOV4QQcdqVykH8UJBU2utvkLA7FQuqGCVwYzDdARe13Dvx5JX9U?=
 =?us-ascii?Q?ie4Ai1pPmG0C4AQKWXaj/f9hJwN8uVGMGrdA7X8/NI+ek5KQ1BvRb1PABnPx?=
 =?us-ascii?Q?kfbrrKZuEGBqYh607kwD5y0wfq/1UjQ9CGnZoi//e8Xj4VLicD8edc9Vi5II?=
 =?us-ascii?Q?bfQbvvfcHKEysUQ6Zig1C6H0NWYpbJd68wS3xrNTN4tMUorL0yl78QGgPrsN?=
 =?us-ascii?Q?Lnmyhz08mlsx77RddX8rhVR3x5dMncLcvvjCOjodP7Lc9SJHjAurOoOpglpV?=
 =?us-ascii?Q?8bB6O4ROl2wU+J/ic+p2iK3grE9wgiJfvbREBJwaeITVXImrIRB1JadlHhoR?=
 =?us-ascii?Q?841Ep4tYYB0ICUNnqf8KtzkxsvoxZy7hnQWLeRV4E4pYSM1BEGqwKqeWyXRw?=
 =?us-ascii?Q?tguMfRYbhih9Dt7+FPziGW8AX4vRnKnCBrtusuza7H9VAt7PM5ZxvkOgpW7y?=
 =?us-ascii?Q?uekGhkidR1bEiJCRqrYCQ3EdBk39KQbPhERkoVSf47IAKQEY4xRwf4eIsJpE?=
 =?us-ascii?Q?UC1ejFA9I+6sn0JMsQS1PjY3xN1P5mMIzZ7a20vjDwi1Ut2fCtvfL2/1/7L1?=
 =?us-ascii?Q?BUMKPXY36CPo6iULktCoMKiWEQYPPZ3qAN6NGdTVtmy1btwniMHGC9JgMNq6?=
 =?us-ascii?Q?jt0yIqjjFnU0RhP88bida9CX2noYGr4DN3eFyjazwoCrO6AYd6ZPtS6youu7?=
 =?us-ascii?Q?DjRsRGBiTZqMA9SiEOai2PoJOteC6opvfELiid2UJGSrgiHWr4fT6y2DTBIn?=
 =?us-ascii?Q?lxkniEz08oQjfKPGvITT/Z+z/3bsNfGapgH1aPOPq1Jc4NiUD9XwGzhActH1?=
 =?us-ascii?Q?qw7AXXWnrfb+IDz1p0C50P/uYpRTeGuBifAkrkIYKAjtYcctuSV7iwkPhOGj?=
 =?us-ascii?Q?C3iRjW+sJZdAX17lMPKlIRWD3Gw6wOrnn6/mJoutR9Ojm7Es7F3dGuzfLQGw?=
 =?us-ascii?Q?FKLLWXYSXbHCKUTFYFu0NrCUpdUIYEy1Df8ZkAUbp+FODq+nETUW3bpv1DMf?=
 =?us-ascii?Q?IIdHGEyQUXGz3nQvC2KBHHKlb4VqxXslIx22WGhD08LIpE0CuohwQsZNNhA4?=
 =?us-ascii?Q?QkouBY79+VFsiIh8QQK520youqTvei3U09DQbMgmoLwDx+9SFOq/GY3y/50t?=
 =?us-ascii?Q?R4p6egjGRwDKBfAOjYnggeSTLyiOPL/uXDd2sB1oj3b0TxtpwusxmEItxt74?=
 =?us-ascii?Q?kbVBPHjHldPUN6za5mkCEFQP1KuBQQbd1nIUtqKUnCN4lmq3IzihnfVGl7v4?=
 =?us-ascii?Q?r9T68Kn7glVtkHTD6QSj9+vPeYmZvS9o4OatMYchKaDArmS/MUZM2/99diVb?=
 =?us-ascii?Q?DkV3MFBSIPw4SwlkXNlPdK4AM67VwQc0W4cHHrUn?=
X-MS-Exchange-CrossTenant-Network-Message-Id: 3afd590c-0c9c-485f-46ea-08dad69c5f43
X-MS-Exchange-CrossTenant-AuthSource: MN0PR11MB6206.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 05 Dec 2022 08:40:33.2207
 (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: NlG/G/G6oymjWlSmLvdOdByEjBKpHyyTv/Ng0nWVDzOrc9hlHEpROr1PLmJM8SysqQ2nW8GOla9Nl0iXmXI76Q==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: PH7PR11MB7720
X-OriginatorOrg: intel.com
X-Spam-Status: No, score=-7.1 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,
        DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_HI,
        RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_NONE
        autolearn=ham autolearn_force=no version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
        lindbergh.monkeyblade.net
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

On 2022-12-05 at 10:36:25 +0800, Tianchen Ding wrote:
> Hi Chen.
> 
> On 2022/12/1 16:44, Chen Yu wrote:
> > [Problem Statement]
> > For a workload that is doing frequent context switches, the throughput
> > scales well until the number of instances reaches a peak point. After
> > that peak point, the throughput drops significantly if the number of
> > instances continues to increase.
> > 
> > The will-it-scale context_switch1 test case exposes the issue. The
> > test platform has 112 CPUs per LLC domain. The will-it-scale launches
> > 1, 8, 16 ... 112 instances respectively. Each instance is composed
> > of 2 tasks, and each pair of tasks would do ping-pong scheduling via
> > pipe_read() and pipe_write(). No task is bound to any CPU.
> > It is found that, once the number of instances is higher than
> > 56(112 tasks in total, every CPU has 1 task), the throughput
> > drops accordingly if the instance number continues to increase:
> > 
> >            ^
> > throughput|
> >            |                 X
> >            |               X   X X
> >            |             X         X X
> >            |           X               X
> >            |         X                   X
> >            |       X
> >            |     X
> >            |   X
> >            | X
> >            |
> >            +-----------------.------------------->
> >                              56
> >                                   number of instances
> > 
> > [Symptom analysis]
> > 
> > The performance downgrading was caused by a high system idle
> > percentage(around 20% ~ 30%). The CPUs waste a lot of time in
> > idle and do nothing. As a comparison, if set CPU affinity to
> > these workloads and stops them from migrating among CPUs,
> > the idle percentage drops to nearly 0%, and the throughput
> > increases by about 300%. This indicates room for optimization.
> > 
> > The reason for the high idle percentage is different before/after
> > commit f3dd3f674555 ("sched: Remove the limitation of WF_ON_CPU
> > on wakelist if wakee cpu is idle").
> > 
> > [Before the commit]
> > The bottleneck is the runqueue spinlock.
> > 
> > nr_instance          rq lock percentage
> > 1                    1.22%
> > 8                    1.17%
> > 16                   1.20%
> > 24                   1.22%
> > 32                   1.46%
> > 40                   1.61%
> > 48                   1.63%
> > 56                   1.65%
> > --------------------------
> > 64                   3.77%      |
> > 72                   5.90%      | increase
> > 80                   7.95%      |
> > 88                   9.98%      v
> > 96                   11.81%
> > 104                  13.54%
> > 112                  15.13%
> > 
> > And top 2 rq lock hot paths:
> > 
> > (path1):
> > raw_spin_rq_lock_nested.constprop.0;
> > try_to_wake_up;
> > default_wake_function;
> > autoremove_wake_function;
> > __wake_up_common;
> > __wake_up_common_lock;
> > __wake_up_sync_key;
> > pipe_write;
> > new_sync_write;
> > vfs_write;
> > ksys_write;
> > __x64_sys_write;
> > do_syscall_64;
> > entry_SYSCALL_64_after_hwframe;write
> > 
> > (path2):
> > raw_spin_rq_lock_nested.constprop.0;
> > __sched_text_start;
> > schedule_idle;
> > do_idle;
> > cpu_startup_entry;
> > start_secondary;
> > secondary_startup_64_no_verify
> > 
> > task A tries to wake up task B on CPU1, then task A grabs the
> > runqueue lock of CPU1. If CPU1 is about to quit idle, it needs
> > to grab its lock which has been taken by someone else. Then
> > CPU1 takes more time to quit which hurts the performance.
> > 
> > [After the commit]
> > The cause is the race condition between select_task_rq() and
> > the task enqueue.
> > 
> > Suppose there are nr_cpus pairs of ping-pong scheduling
> > tasks. For example, p0' and p0 are ping-pong scheduling,
> > so do p1' <=> p1, and p2'<=> p2. None of these tasks are
> > bound to any CPUs. The problem can be summarized as:
> > more than 1 wakers are stacked on 1 CPU, which slows down
> > waking up their wakees:
> > 
> > CPU0					CPU1				CPU2
> > 
> > p0'					p1' => idle			p2'
> > 
> > try_to_wake_up(p0)							try_to_wake_up(p2);
> > CPU1 = select_task_rq(p0);						CPU1 = select_task_rq(p2);
> > ttwu_queue(p0, CPU1);							ttwu_queue(p2, CPU1);
> >    __ttwu_queue_wakelist(p0, CPU1); =>	ttwu_list->p0
> > 					quiting cpuidle_idle_call()
> > 
> > 					ttwu_list->p2->p0	<=	  __ttwu_queue_wakelist(p2, CPU1);
> > 
> >      WRITE_ONCE(CPU1->ttwu_pending, 1);					    WRITE_ONCE(CPU1->ttwu_pending, 1);
> > 
> > p0' => idle
> > 					sched_ttwu_pending()
> > 					  enqueue_task(p2 and p0)
> > 
> > 					idle => p2
> > 
> > 					...
> > 					p2 time slice expires
> > 					...
> > 									!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
> > 								<===	!!! p2 delays the wake up of p0' !!!
> > 									!!! causes long idle on CPU0     !!!
> > 					p2 => p0			!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
> > 					p0 wakes up p0'
> > 
> > idle => p0'
> > 
> > 
> > 
> > Since there are many waker/wakee pairs in the system, the chain reaction
> > causes many CPUs to be victims. These idle CPUs wait for their waker to
> > be scheduled.
> > 
> > Actually Tiancheng has mentioned above issue here[2].
> > 
> 
> First I want to say that this issue (race condition between selecting idle
> cpu and enqueuing task) always exists before or after the commit
> f3dd3f674555. And I know this is a big issue so in [2] I only try to fix a
> small part of it. Of course I'm glad to see you trying solving this issue
> too :-)
> 
> There may be a bit wrong in your comment about the order.
> "WRITE_ONCE(CPU1->ttwu_pending, 1);" on CPU0 is earlier than CPU1 getting
> "ttwu_list->p0", right?
>
Yes, you are right, I'll refine the comment.

thanks,
Chenyu