Received-SPF: pass (google.com: domain of linux-kernel+bounces-102112-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: <33ff03f7-0301-42fb-842f-17f21426cdc7@amd.com>
Date: Wed, 13 Mar 2024 22:24:58 +0530
User-Agent: Mozilla Thunderbird
Subject: Re: [PATCH] rcu: Reduce synchronize_rcu() delays when all wait heads
 are in use
Content-Language: en-US
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>
From: Neeraj Upadhyay <Neeraj.Upadhyay@amd.com>
In-Reply-To: <ZfHXrTUHRhAVjBOE@localhost.localdomain>
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?TDNNb283NE1OUXVTOXZYN2xLYzczN2FLdEdFbHpPS2ZTZGVLYmRmaXUzMjZq?=
 =?utf-8?B?S01tUUE5SzdWS1J5cHErWnNGT1lHdHZVQjEvT2trTHJFM3hNOFQvMmFLN3B3?=
 =?utf-8?B?Nzh6cGhmdDlIY0lsTUpjR3hFeCs4a2loSmpSNnZ5ZWRLbHB4b1JTK0ZuTnZR?=
 =?utf-8?B?VGlPd2RnbzhRYjBnRzlCK1dpMCtUMm1lT0JacXI2UmFBRUVwdlNaMmpoSllw?=
 =?utf-8?B?WHM0MmttYVBFVkdaN1VRZ2R4MHk3Z2x6a3VhemtKWkNtRmpSRERMemU0YU03?=
 =?utf-8?B?eUVnc3dwMTdudGs0YnJkbi9UekpmcVo2Z2I4MlBqMzlRRnZKUVBpVTVEVncz?=
 =?utf-8?B?SkVEaThEbmo1WUZEN3FqVXNUeHZsZzVhNnNHRDhKeGg0R0JNZjNxTzlpWUhJ?=
 =?utf-8?B?eXVTaUJPNHU1ZHArZHlwVVhMNlk3UUlLbmdsa3l4bkJTdnNSd2E1VmN3aXc4?=
 =?utf-8?B?UEdYb3pOb3M3UFJpbEUvVVByY0drMUJUR2VUdEJaYk93QVo0cUpMZ0dER1BX?=
 =?utf-8?B?alNiQUc5YTJDcTlhVkhmOC9VTUViZXVYeS9LWUo5QVd2emt3ZEp3dExSWUN5?=
 =?utf-8?B?TnBYNk95RC9wSXRaMTZJME5Bbm56VFdPK1ZqTFBoYnRxOG1McFQrWjQzY1hC?=
 =?utf-8?B?SmVxcmRIVlZyTEtGa2pDK1pVenVBTkZza1pobmZJMFB5bEcycDhDZmxYSU92?=
 =?utf-8?B?V1ErODdVNmJ2MURwU0YwallHQUM3LzhqZ0lQU2czVVZLeDZhM1hhQ3d3azZv?=
 =?utf-8?B?ZmVvM0liVDd2TCtqd0p0RFVZemFrSW9sOHlhNUJsdXpNOWh6TjdyUlNScy9N?=
 =?utf-8?B?QTNtVGRlRktNVVA4TVJ0elJiMElBUzZyQ082UzNSYlZ6c1FXS0pNbnA0YjJ0?=
 =?utf-8?B?bk1vMVZJWlBCVm94dSt6dGdXZFZDa1o3SVFiMmE4dFpQMEd1ZzdJK3RGczlu?=
 =?utf-8?B?UXFyejMrVnhSWDdXQ1FwTUIvS1RNQmQzWXZzSTVobUpQajI1Um5ndE53SFZp?=
 =?utf-8?B?ckxXVTdxdnZwV3FwUnlZenhlbUluL0JuWDNLeFc0azVhdE5mNWZEc1hVM2Nw?=
 =?utf-8?B?YnV0Qm84VVVkV1NCcHloc054THMvZ2xvN0M2blRoak1uSjhTZjZvSWpYM2xx?=
 =?utf-8?B?Q3dJY2FER3lkdFMvemFiV1prM1MrSzNmZ0FJcW8rSHVvSjdmOVVSU3Jzb0dW?=
 =?utf-8?B?OFdJOWVkN3BvbkljM1hsR1dVWVZyZkNuRFE1UUR0QklNQU5Md3hsbUNwUFJa?=
 =?utf-8?B?d0d2WXlvdGhabzY0bHVqWnRyT2dJOGtkTkJSa1NvV1RSUllOejZlY3o2eWlQ?=
 =?utf-8?B?WU5yRWlYb1QwWWV2MDZhdENUUzBQRlRPWmMxZ04yOEtURm54bDF3OFhjL1ox?=
 =?utf-8?B?TGVoL1lWUVRQaXhSOC95MHFiWnZsZG52MCtBY1NZQU91SzhJV1ZlZzlMVnRU?=
 =?utf-8?B?eDZTQ01GWHl2NHQ5N1Z4bWp4bjhBa0xUQ3NGdCt1M2U5V1dPRzFtczRHWWlI?=
 =?utf-8?B?QXNPeWpKN2JUY2NncDJKV1Z1SE5pYkZ2ams2eUM5UWNBeEZWL1Z3dU04eXFi?=
 =?utf-8?B?cUkrK0lJd3Nyd3o3cjczTG93L1V0QjVMWm5jNHZvOGhOWUhIR083dGFLUFJX?=
 =?utf-8?B?dDkxVm5JamwwUGJtRC9BejFHN2VQdWtRSFVZZ0RQcmp5SytXSUpjYUxBVmxj?=
 =?utf-8?B?bFZRWG5waFd0bGsrdGFjNVh0RW9vMnhZaG9tSUVrQ3gveVY2UmNZTkVmd05h?=
 =?utf-8?B?cUZlSlhqZkNoODhmMGllZGRibHhUeEZuYjN4NVFwcUdmdHJZK0prNm01bjlt?=
 =?utf-8?B?VndQSXI1dnFSMG5RRWxPWWR3aUdaNm9mVVRya3J6N2NaL1lhQTBkS3ZheGVx?=
 =?utf-8?B?WnBwWEVOZmk5TVllYlRKV1FyK05VMXAvWGM0UjgzcnI3Q05pRUJUMmdpQkNs?=
 =?utf-8?B?Yk9ndWZDQUV2UkNuLzdiSFhQNkNZeTYva1UyTXRvaUJpWnBsVVpvRkFZazBz?=
 =?utf-8?B?WGVlS2REUXdhcjJ2L001TGJuRzBheWZIZVZWOXEzY0wzZzIyS0xaeUVyRTVC?=
 =?utf-8?B?R1RtSVlBVVBiQmZCalRlRTNrOXNvTHIrZFM2eVhldFlrY3dKSWpVSUhWc0h0?=
 =?utf-8?Q?R2PY8Sj4ZVe48Euzcznvy+28b?=
X-OriginatorOrg: amd.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 4fb2ba2e-10b5-4273-fb78-08dc437e56da
X-MS-Exchange-CrossTenant-AuthSource: DS0PR12MB6608.namprd12.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 13 Mar 2024 16:55:08.5714
 (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: qPSPU14E6AGAVRPhl2gfr+XdctZwbFyUBlpvNWV50CeNOZTLjQSVJJJa9XBJXGyQgQuTlr72rlCqzsbrWadWqg==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: IA1PR12MB8553

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!


Thanks
Neeraj