Received-SPF: pass (google.com: domain of linux-kernel+bounces-102313-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:45e3:2400::1 as permitted sender) client-ip=2604:1380:45e3:2400::1;
Message-ID: <af5168ae-973a-46dc-8766-d1949cc82ec8@amd.com>
Date: Wed, 13 Mar 2024 23:19:08 +0530
User-Agent: Mozilla Thunderbird
Subject: Re: [PATCH] rcu: Reduce synchronize_rcu() delays when all wait heads
 are in use
Content-Language: en-US
From: Neeraj Upadhyay <Neeraj.Upadhyay@amd.com>
To: Frederic Weisbecker <frederic@kernel.org>
Cc: paulmck@kernel.org, joel@joelfernandes.org, josh@joshtriplett.org,
 boqun.feng@gmail.com, rostedt@goodmis.org, mathieu.desnoyers@efficios.com,
 jiangshanlai@gmail.com, qiang.zhang1211@gmail.com, rcu@vger.kernel.org,
 linux-kernel@vger.kernel.org, neeraj.upadhyay@kernel.org
References: <20240313083228.233247-1-Neeraj.Upadhyay@amd.com>
 <ZfHDwPkPHulJHrD0@localhost.localdomain>
 <35e009c4-d52c-4b96-ba10-afa0be9dfd5e@amd.com>
 <ZfHXrTUHRhAVjBOE@localhost.localdomain>
 <33ff03f7-0301-42fb-842f-17f21426cdc7@amd.com>
 <ZfHfNo_J-XZX0BS3@localhost.localdomain>
 <3f544c35-365c-4782-8dd6-f523b257f867@amd.com>
In-Reply-To: <3f544c35-365c-4782-8dd6-f523b257f867@amd.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Precedence: bulk
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0:
	=?utf-8?B?Wm9za2xqWlF1M2YzSGVaOE9JWjEraWplWTFuRDFkTnYyZ1Z6OExCV0NzTmRh?=
 =?utf-8?B?WlFYb2ZrMGFUT2FxOGRXdklwOEpLYVNId0k4aWJZK0xrN2hGQld0aW8vcllj?=
 =?utf-8?B?cFd0NDhEMTFqb0dVSk5YVHhpUDd1MjNKYUYvdUlTeU1YQThTL2xQTVM1MDBr?=
 =?utf-8?B?UFRmSWNvUlJPbEZ1SXczVjR2R2t3UzE0ZWpsRSsvRmx1enM3dFp5REM3eTRE?=
 =?utf-8?B?VEFVb29sMktPSUpKdjFLam1Nc29UZmRCeUdsMDE3elZETlNrOGVVVXBMWStC?=
 =?utf-8?B?SHA4Y1hxdS90NVVpUDVCNjlDN3dDZkR0cjlaQnNvVVljTUZOZml5dk13M1BC?=
 =?utf-8?B?ZkZKOVJoUmNMVG5wVzI2Q3hYbzlrSEp6d2kzREZPZGpwSVExS0w0c3IvUmtJ?=
 =?utf-8?B?dlpDYVFQYm1ndGtFSEptKzhmREx5bThtNy91M015dEdGWFVpNm55ampTaUxN?=
 =?utf-8?B?UWRBb1ZwUHJkbUlVb2JWT0dXRW1QZitaUS9YMHRpNHhwcDdRMjJOQnRXbkF5?=
 =?utf-8?B?NGx2RURCekxNUENqMFRIREVtQzNISEV3LzhxUGNHOG1LMDZOclpyaHJCaDRV?=
 =?utf-8?B?TTZidU00UXJsU2o2NnBta2NibUxrL2JMMHY3a3F5SFAzbkNINlZSREFUeVBO?=
 =?utf-8?B?cTAwVEtHOGI4NW1KU3JqWklMakg4QkdHYWNlUkNtUzJtOUV2UWM4WHpqdncy?=
 =?utf-8?B?Q01NT1hpNzgyZU5zQW1XTU5NY0ZrMGcwdFpKUFREblo5WHEzdW9IVWVCOUJo?=
 =?utf-8?B?T1UvTTV1Ri84Z084dHhGSVE4U2crSGxIdTNzWW95OXZXeUNZYmZLTDI5UUZW?=
 =?utf-8?B?czRERUw0L1pvenJzZnNOZFh6TWx0b29GZnlWSTkrVURmL1JjTGtwRFl5Rnd3?=
 =?utf-8?B?NzdFRVQvRlBnZ0M2OTliTkZxRi9qenRjZHpVVEtaTktEUzlYWFd0OENDWk9U?=
 =?utf-8?B?OHdKMTNPT0tnSG1FQ2E0QS9kYURRdy9oL0tvYmlHMkdwaXZVTGxiVlZJSHYx?=
 =?utf-8?B?TksxL0pkK3lsQWZEbWgxY2lKbnU4MGJRSmFSQWY5Z1p6YjU0WlZQNlJ3aXpm?=
 =?utf-8?B?ekU4WU9hNmU5ell0MDBPTGptcGtNb1hSc2hhM0VHZ3hkRWp0TDlGU25yY2h5?=
 =?utf-8?B?QjR2akFmR05NbFFqWnZWTFFtWko2SVJXam9xYnBNNGRuRVR6K1gwaytiUExq?=
 =?utf-8?B?c1cxTlRYNWJHaUxLdWdNL1krUFcwV3JQSGNOcEJxcCt0QkQrYzdyKzZxRjFL?=
 =?utf-8?B?QjlkZ09BVnllQmhvREw0K1F2bWlaZ3VOekllVDhhd3ArL1p5MXZuaEZpV3JV?=
 =?utf-8?B?dUlubXU4T0xNUDdDNGkwRTZ5U0J2WFY3Q21Vd1RWQ2dyQWI5MmVKc3U2MDZN?=
 =?utf-8?B?cGVUWlpUVHZUN1VMZnhTQjlnb1hYWWlUamZFb29JQnRZUFN6QXFFTk1OS2tG?=
 =?utf-8?B?NHp2aXhlVHhwcXk3UlkxeHc1TExMdWtaL09VREdqV0Roa3BxWFpWSm12RGFT?=
 =?utf-8?B?bmVVcjJWWWhYMjZ1cVRyeU5jNTZpQlg5a1BEUm9CanR2TGQxZDBwV3NUR3Y1?=
 =?utf-8?B?WjlaV0VqbVcya1hPSU1Fa3g1bXlBME5DMm01ZW9KMFdkRUVlWFhaQldQWUVp?=
 =?utf-8?B?bTlxODFiTmJzTnIzeHh4MS9Vb2oxTGJQdE00OUZlYkcvVVpDKzFRdnBqSDVk?=
 =?utf-8?B?dURtbXRwRzd3WVZaWElCcTRrYnpIVm1peUhaOWxqVlZnYXM4UkRDQ0dublQ4?=
 =?utf-8?B?ay8xdWE1OXQyaitXYmxNOFFwcFVKTCtBTDFERFdhRGtsYWRPanRzOGlaREsx?=
 =?utf-8?B?aHc4bTlkL1NWY1dCdElHOHBiaExHYURWUzU1RVBId3RNZTFtSmlvODZNc1Q5?=
 =?utf-8?B?ZW9HZnB1OU1DWWpacnhRZ0JuSGl2ZUw5S2xmbkQyeVJHYlpsQWZzM1dHbEMy?=
 =?utf-8?B?UjJ2YmpkTU4rb2xkRFhFZ0tMbGgxYzJ5cWxnR1d3S2c5ZlNKa3FIUXdXb1Nz?=
 =?utf-8?B?WVNXcEJsN1FTcFJCeHNiaGFDYlo0bllvcGFIQmIzRjNnc3N1REowZlZqazVi?=
 =?utf-8?B?ZzhVUlQ1UFhpb1h0MGVzaVdlbHlIaW9ZUjZyejBLdVEycjJReDYrbXU2VXZs?=
 =?utf-8?Q?Fw0IXhc3mgZoEITgA93jRCCYM?=
X-OriginatorOrg: amd.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 2ecfcc66-f309-48d1-c676-08dc4385e7e9
X-MS-Exchange-CrossTenant-AuthSource: DS0PR12MB6608.namprd12.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 13 Mar 2024 17:49:18.4397
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 3dd8961f-e488-4e60-8e11-a82d994e183d
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: 7c6dx2Jphd3W5yCEV1edti1xebCb+tRU1gK33Gkrto1oNBJBIG1b/pNic/hUUL93IPorTspfVo+vAGR1oy46kQ==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SN7PR12MB8769


On 3/13/2024 10:56 PM, Neeraj Upadhyay wrote:
> 
> 
> On 3/13/2024 10:45 PM, Frederic Weisbecker wrote:
>> Le Wed, Mar 13, 2024 at 10:24:58PM +0530, Neeraj Upadhyay a écrit :
>>> Hi Frederic,
>>>
>>> On 3/13/2024 10:13 PM, Frederic Weisbecker wrote:
>>>> Le Wed, Mar 13, 2024 at 09:41:58PM +0530, Neeraj Upadhyay a écrit :
>>>>> Hi Frederic,
>>>>>
>>>>> On 3/13/2024 8:48 PM, Frederic Weisbecker wrote:
>>>>>> Le Wed, Mar 13, 2024 at 02:02:28PM +0530, Neeraj Upadhyay a écrit :
>>>>>>> When all wait heads are in use, which can happen when
>>>>>>> rcu_sr_normal_gp_cleanup_work()'s callback processing
>>>>>>> is slow, any new synchronize_rcu() user's rcu_synchronize
>>>>>>> node's processing is deferred to future GP periods. This
>>>>>>> can result in long list of synchronize_rcu() invocations
>>>>>>> waiting for full grace period processing, which can delay
>>>>>>> freeing of memory. Mitigate this problem by using first
>>>>>>> node in the list as wait tail when all wait heads are in use.
>>>>>>> While methods to speed up callback processing would be needed
>>>>>>> to recover from this situation, allowing new nodes to complete
>>>>>>> their grace period can help prevent delays due to a fixed
>>>>>>> number of wait head nodes.
>>>>>>>
>>>>>>> Signed-off-by: Neeraj Upadhyay <Neeraj.Upadhyay@amd.com>
>>>>>>> ---
>>>>>>>  kernel/rcu/tree.c | 27 +++++++++++++--------------
>>>>>>>  1 file changed, 13 insertions(+), 14 deletions(-)
>>>>>>>
>>>>>>> diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
>>>>>>> index 9fbb5ab57c84..bdccce1ed62f 100644
>>>>>>> --- a/kernel/rcu/tree.c
>>>>>>> +++ b/kernel/rcu/tree.c
>>>>>>> @@ -1470,14 +1470,11 @@ static void rcu_poll_gp_seq_end_unlocked(unsigned long *snap)
>>>>>>>   * for this new grace period. Given that there are a fixed
>>>>>>>   * number of wait nodes, if all wait nodes are in use
>>>>>>>   * (which can happen when kworker callback processing
>>>>>>> - * is delayed) and additional grace period is requested.
>>>>>>> - * This means, a system is slow in processing callbacks.
>>>>>>> - *
>>>>>>> - * TODO: If a slow processing is detected, a first node
>>>>>>> - * in the llist should be used as a wait-tail for this
>>>>>>> - * grace period, therefore users which should wait due
>>>>>>> - * to a slow process are handled by _this_ grace period
>>>>>>> - * and not next.
>>>>>>> + * is delayed), first node in the llist is used as wait
>>>>>>> + * tail for this grace period. This means, the first node
>>>>>>> + * has to go through additional grace periods before it is
>>>>>>> + * part of the wait callbacks. This should be ok, as
>>>>>>> + * the system is slow in processing callbacks anyway.
>>>>>>>   *
>>>>>>>   * Below is an illustration of how the done and wait
>>>>>>>   * tail pointers move from one set of rcu_synchronize nodes
>>>>>>> @@ -1725,15 +1722,17 @@ static bool rcu_sr_normal_gp_init(void)
>>>>>>>  		return start_new_poll;
>>>>>>>  
>>>>>>>  	wait_head = rcu_sr_get_wait_head();
>>>>>>> -	if (!wait_head) {
>>>>>>> -		// Kick another GP to retry.
>>>>>>> +	if (wait_head) {
>>>>>>> +		/* Inject a wait-dummy-node. */
>>>>>>> +		llist_add(wait_head, &rcu_state.srs_next);
>>>>>>> +	} else {
>>>>>>> +		// Kick another GP for first node.
>>>>>>>  		start_new_poll = true;
>>>>>>> -		return start_new_poll;
>>>>>>> +		if (first == rcu_state.srs_done_tail)
>>>>>>> +			return start_new_poll;
>>>>>>> +		wait_head = first;
>>>>>>
>>>>>> This means you're setting a non-wait-head as srs_wait_tail, right?
>>>>>> Doesn't it trigger the following warning in rcu_sr_normal_gp_cleanup():
>>>>>>
>>>>>> 	WARN_ON_ONCE(!rcu_sr_is_wait_head(wait_tail));
>>>>>>
>>>>>
>>>>> Oh I missed it. Will fix it, thanks!
>>>>>
>>>>>> Also there is a risk that this non-wait-head gets later assigned as
>>>>>> rcu_state.srs_done_tail. And then this pending sr may not be completed
>>>>>> until the next grace period calling rcu_sr_normal_gp_cleanup()? (Because
>>>>>> the work doesn't take care of rcu_state.srs_done_tail itself). And then
>>>>>> the delay can be arbitrary.
>>>>>>
>>>>>
>>>>> That is correct. Only the first node suffers from deferred GP.
>>>>> If there are large number of callbacks which got added after
>>>>> last available wait head was queued, all those callbacks (except one)
>>>>> can still have a GP assigned to them.
>>>>>
>>>>>> And the next grace period completing this sr (that non-wait-head set
>>>>>> as rcu_state.srs_done_tail) and thus allowing its caller to wipe it out
>>>>>> of its stack may race with the cleanup work dereferencing it?
>>>>>>
>>>>>
>>>>> This sr can only be completed when done tail moves to new node. Till
>>>>> then, it gets deferred continuously. So, we won't be entering into
>>>>> the situation where the sr processing is complete while done tail is pointing
>>>>> to it. Please correct me if I am missing something here.
>>>>
>>>> Ok I'm confused as usual. Let's take a practical case. Is the following
>>>> sequence possible?
>>>>
>>>> 1) wait_tail = NULL
>>>>    done_tail = WH4->SR4->WH3->SR3->WH2->SR2->WH1->SR1...
>>>>
>>>> Initial layout
>>>>
>>>> 2) wait_tail = SR5 -> WH4...
>>>>    done_tail = WH4->SR4->WH3->SR3->WH2->SR2->WH1->SR1...
>>>>
>>>> New GP
>>>>
>>>> 3) wait_tail = NULL
>>>>    done_tail = SR5->WH4->SR4->WH3->SR3->WH2->SR2->WH1->SR1...
>>>>
>>>> GP completes, normal cleanup
>>>>
>>>> 3) wait_tail = SR6->SR5...
>>>>    done_tail = SR5->WH4->SR4->WH3->SR2->WH2->SR1->WH1->SR1...
>>>>
>>>> New GP
>>>>
>>>> 4) GP completes and SR5 is completed by rcu_sr_normal_gp_cleanup(). So
>>>>    the caller releases it from the stack. But before rcu_sr_normal_gp_cleanup()
>>>>    overwrites done_tail to SR6->WH4->SR4.... , the workqueue manages to run
>>>>    and concurrently dereferences SR5.
>>>>
>>>> But I bet I'm missing something obvious in the middle, preventing that...
>>>
>>> Your analysis looks correct to me. Maybe, one way to fix this can be that
>>> rcu_sr_normal_gp_cleanup() stops processing nodes in its context,
>>> when it reaches done tail and done tail is not a wait head. I will
>>> think more on this, thanks!
>>
>> That alone is probably not enough. In the end you may end up with a real
>> pending sr stuck as done tail without completion, until one day a
>> new real queue comes up, preferably with a real wait head in order not
>> to get stuck with a new sr as done tail.
>>
> 
> But after point 4 in your sequence, rcu_sr_normal_gp_cleanup() would move
> the done tail to SR6 and queue a new work, which will process SR5,
> so, we will be able to progress real pending srs?
> 
> 

Missed one point. We will continue initiating new GP until first node cb
is processed, which can happen when a wait head becomes available.


Thanks
Neeraj

> Thanks
> Neeraj
> 
>>>
>>>
>>> Thanks
>>> Neeraj