Received-SPF: pass (google.com: domain of linux-kernel+bounces-203975-linux.lists.archive=gmail.com@vger.kernel.org designates 147.75.199.223 as permitted sender) client-ip=147.75.199.223;
Message-ID: <477a2cb7-bd93-4f1c-a10e-ae7585425a02@vivo.com>
Date: Thu, 6 Jun 2024 17:20:19 +0800
User-Agent: Mozilla Thunderbird
Subject: Re: [PATCH v2] sbitmap: fix io hung due to race on
 sbitmap_word::cleared
Content-Language: en-US
To: Ming Lei <ming.lei@redhat.com>
Cc: Jens Axboe <axboe@kernel.dk>, Andrew Morton <akpm@linux-foundation.org>,
 Pavel Begunkov <asml.silence@gmail.com>, linux-kernel@vger.kernel.org,
 linux-block@vger.kernel.org, "yukuai (C)" <yukuai3@huawei.com>,
 Yu Kuai <yukuai1@huaweicloud.com>
References: <20240604031124.2261-1-yang.yang@vivo.com>
 <CAFj5m9KV7OJ4_KjbSkpdtfrKamoLzV6EH-mJP3=y+VvoYOzC3w@mail.gmail.com>
 <aa7246f9-f7df-3054-077e-eb21c7f423ac@huaweicloud.com>
 <ZmEpIBL2Ot5cwRyv@fedora> <bebf237c-1223-43e9-93f1-10a32c4923af@vivo.com>
 <ZmF7JsJYlUmp5xTj@fedora>
From: YangYang <yang.yang@vivo.com>
In-Reply-To: <ZmF7JsJYlUmp5xTj@fedora>
Content-Type: text/plain; charset=UTF-8; format=flowed
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?Ny81Uk1PdlVHT0RSVDlyMGJMenJvcU50M3BZMk1HVGRwTTVyd0RvaWpHT2U1?=
 =?utf-8?B?SEdBZ0hKcW9jeEwxbGxtaVNYMzZuMWRGUmRseXlDcUJ5cFBTNlEyc3FCYXlz?=
 =?utf-8?B?S2tDQnlaS2VNVjExQXVNNVdHdFY5Q2wrOVNKMFpXUW4xTTZFNHZhQ0xiNGlG?=
 =?utf-8?B?c1RJYzVXc2hqbXlIdS9mcEV3UnZtL1BSRkxLanNzaGlOdE5BYURVSENVeDhh?=
 =?utf-8?B?ekZBcUdiWWdvYVpaQ3hOMFpEdG1YRituMXg1VmtyMEllWkY3dEExWkJrUzBm?=
 =?utf-8?B?OERFalJOT2M1VnpjcmcxVTh5VFZUQmhiZlZMQzN1UFBOOWMxRkR2KzBKL0t2?=
 =?utf-8?B?OWJScHNmYnFGQTgrQnRLaWo3Q29uOVhXVUJBYnlsUWZkNmw1ZzJVWUZxdnhN?=
 =?utf-8?B?R05BNHpMblI5LzJ4clBaQ08vbEtTb1czampPelFLQWYrSnZWR29aTkMxeWgw?=
 =?utf-8?B?SldOZTdjSExkTWxaMXV5ZEdFVUtwVUxaZkxmNzd0V2dNTDVIZlNyK3VnUm5I?=
 =?utf-8?B?THg2WEt0TGtvUW9kU2Q1c1l2eHBZWTlWd01wT2JzaGUyelE4YXdDSXJ2aFB0?=
 =?utf-8?B?QkhrQmlkOWdlaWlzSmRVS1RZRHZ1YzllcWF2Z0hJaWx3dEJ4V2tHWHFrYmxj?=
 =?utf-8?B?UDVveEhjeWhBZncvb1FaTjcvclNPeWJhR042R0l4am12UVp3L29WRTRpVEF4?=
 =?utf-8?B?bTZIQVNKVm1LVXN5NDZUeHBKQm1Rck9EWXdzdTlhS3Nxakd1eWZlYjducGc1?=
 =?utf-8?B?cW43ZDRGVC9wUEgyREx5MUMxL2dySzg4Y0ZxY0NHUVZMenBUbmU2UnBkbGlS?=
 =?utf-8?B?NE9FYkQrRmltMXFBd1IrMnJyUmVZVzRHN3JyOUFWd3RPcVJlbFZ0YW85UW9s?=
 =?utf-8?B?OWVhRVV1NUVlTTY2dHJlcDF0dVlteGxhem1EOTlVeS9RMWVQcTk5aFBBSTZ3?=
 =?utf-8?B?b0JoNjNSQWRLczZXWVJ2NjE1dGNJVEsrWTd5RnZrdVp0U0Y2eVFFMjV5Nzlr?=
 =?utf-8?B?RXFGblMvTU1PRnNrbUVacU1oYnpmc2FpR2lrbnNlblo3Vjd5ejVwUldhY016?=
 =?utf-8?B?Y0JJUE9JMkErTGpFZ2tWYTEzQTVDZ1JUQ0I0Rm9VVnlxZGM1eElSWEJkUGRR?=
 =?utf-8?B?N0ZNaU91NGtxaTBPMVVmMTQwNE5UWGlPZzNJTUFJaDNmczZkMDFzUllCMXdD?=
 =?utf-8?B?VTdWNHJyNDFsSXB6OEErZGZOemg0ZUR2VWhJZ1lxazhqaDNYS2ZiWGwxUkdW?=
 =?utf-8?B?aHZFYzdDMmhPSXRtYXhYRlBlSG9XL0pNS0pHRTc0Q25rRGNuNnlPb29hUFZO?=
 =?utf-8?B?cDJMME9lUVovUXRlelRWelpUUHlGY3Njc0g5cmlPM3BaMlFZcnJEOWlrS09m?=
 =?utf-8?B?Uy9sQWRBQnI5YzZva3dwcEZKNm5pKzJCRmtxVWIzNEM1eGwvdzB1MEtCU2Iy?=
 =?utf-8?B?OWJuZFNiN3U0Y0gyMVZRS0ppT2w4QytRT1FUMDRqOXlMZnladDdQa3Z6R0c1?=
 =?utf-8?B?OE44YTV1anBZYWhrQUZHRVdVMTBDdkpRbkttd2FTZVBISFUvdlV5KzcxUG9Y?=
 =?utf-8?B?ek9CMVRpZkROWmxZSXZaRStod0tqb3k2Yk9vSmJReXluUXF1Q0tzcFRjdDY0?=
 =?utf-8?B?enVYUXJVUThYazBZOEVsb1hYZ1Vodk5NQXZMMjJ6VzA0WnlXTks5dENNRlhN?=
 =?utf-8?B?QWs4eERDM1FlZkJqZHJTU1N4Tyt1eVErK2FFNmkrU0Qra2NTQmtvOUpNZzJB?=
 =?utf-8?B?U2NIVUpraUZIQVdkTm9BWVd3cTZDYmZWOFFUK1oxcWJlWVVCRjlEVXNCcCtq?=
 =?utf-8?B?WGxGb1l2TGpQZlhOcm1IMXdpRWJpYlhTTjF2SENJU3FUblFZMHgvYjRMVXM1?=
 =?utf-8?B?L2pxQlNMUjJnOGFCQjZpZ3JyWGNoUjNRTHBKaTFZczF2Tlgzd2tHS0JQTFND?=
 =?utf-8?B?c0Q4czFOV1BscGJBRUd0MmVPbE9pemJWdHczbFo2MjRJMXZMUlVqb281Ulpi?=
 =?utf-8?B?bmNwUXpzVjRRY2FzNTFmaGluRW1xMk9vaXdpNk4ycmFiWmh3R09qRzQzQy84?=
 =?utf-8?B?aGFQaVJhaWtmL3Y2bWxXUFVoZVp2OGJpWUU0dGVEMElrM3RHbzN6RkJSOS9s?=
 =?utf-8?Q?UhmUF23MYAJ1va01U4qFDfnNw?=
X-OriginatorOrg: vivo.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 14f1aaa2-0114-41b8-20f3-08dc8609e545
X-MS-Exchange-CrossTenant-AuthSource: KL1PR06MB7401.apcprd06.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 06 Jun 2024 09:20:24.0502
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 923e42dc-48d5-4cbe-b582-1a797a6412ed
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: 8l5Qt6w6QYqwraRK45yc+oYcbybpPnLWamplaHBXVkeXWl0cAfqEFEQYRNL5wi7I0tI5Hh4MN53MkcIvKqD/UA==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: TYZPR06MB7172

On 2024/6/6 17:02, Ming Lei wrote:
> On Thu, Jun 06, 2024 at 03:21:38PM +0800, YangYang wrote:
>> On 2024/6/6 11:12, Ming Lei wrote:
>>> On Tue, Jun 04, 2024 at 02:12:22PM +0800, Yu Kuai wrote:
>>>> Hi,
>>>>
>>>> 在 2024/06/04 11:25, Ming Lei 写道:
>>>>> On Tue, Jun 4, 2024 at 11:12 AM Yang Yang <yang.yang@vivo.com> wrote:
>>>>>>
>>>>>> Configuration for sbq:
>>>>>>      depth=64, wake_batch=6, shift=6, map_nr=1
>>>>>>
>>>>>> 1. There are 64 requests in progress:
>>>>>>      map->word = 0xFFFFFFFFFFFFFFFF
>>>>>> 2. After all the 64 requests complete, and no more requests come:
>>>>>>      map->word = 0xFFFFFFFFFFFFFFFF, map->cleared = 0xFFFFFFFFFFFFFFFF
>>>>>> 3. Now two tasks try to allocate requests:
>>>>>>      T1:                                       T2:
>>>>>>      __blk_mq_get_tag                          .
>>>>>>      __sbitmap_queue_get                       .
>>>>>>      sbitmap_get                               .
>>>>>>      sbitmap_find_bit                          .
>>>>>>      sbitmap_find_bit_in_word                  .
>>>>>>      __sbitmap_get_word  -> nr=-1              __blk_mq_get_tag
>>>>>>      sbitmap_deferred_clear                    __sbitmap_queue_get
>>>>>>      /* map->cleared=0xFFFFFFFFFFFFFFFF */     sbitmap_find_bit
>>>>>>        if (!READ_ONCE(map->cleared))           sbitmap_find_bit_in_word
>>>>>>          return false;                         __sbitmap_get_word -> nr=-1
>>>>>>        mask = xchg(&map->cleared, 0)           sbitmap_deferred_clear
>>>>>>        atomic_long_andnot()                    /* map->cleared=0 */
>>>>>>                                                  if (!(map->cleared))
>>>>>>                                                    return false;
>>>>>>                                         /*
>>>>>>                                          * map->cleared is cleared by T1
>>>>>>                                          * T2 fail to acquire the tag
>>>>>>                                          */
>>>>>>
>>>>>> 4. T2 is the sole tag waiter. When T1 puts the tag, T2 cannot be woken
>>>>>> up due to the wake_batch being set at 6. If no more requests come, T1
>>>>>> will wait here indefinitely.
>>>>>>
>>>>>> To fix this issue, simply revert commit 661d4f55a794 ("sbitmap:
>>>>>> remove swap_lock"), which causes this issue.
>>>>>
>>>>> I'd suggest to add the following words in commit log:
>>>>>
>>>>> Check on ->cleared and update on both ->cleared and ->word need to be
>>>>> done atomically, and using spinlock could be the simplest solution.
>>>>>
>>>>> Otherwise, the patch looks fine for me.
>>>>
>>>> Maybe I'm noob, but I'm confused how can this fix the problem, looks
>>>> like the race condition doesn't change.
>>>>
>>>> In sbitmap_find_bit_in_word:
>>>>
>>>> 1) __sbitmap_get_word read word;
>>>> 2) sbitmap_deferred_clear clear cleared;
>>>> 3) sbitmap_deferred_clear update word;
>>>>
>>>> 2) and 3) are done atomically while 1) can still concurrent with 3):
>>>
>>> After 1) fails, sbitmap_deferred_clear() is called with spinlock,
>>> then it is pretty easy to solve the race, such as, the following patch
>>> against the revert patch.
>>>
>>>
>>> diff --git a/lib/sbitmap.c b/lib/sbitmap.c
>>> index dee02a0266a6..c015ecd8e10e 100644
>>> --- a/lib/sbitmap.c
>>> +++ b/lib/sbitmap.c
>>> @@ -63,13 +63,15 @@ static inline void update_alloc_hint_after_get(struct sbitmap *sb,
>>>    static inline bool sbitmap_deferred_clear(struct sbitmap_word *map)
>>>    {
>>>    	unsigned long mask;
>>> -	bool ret = false;
>>>    	unsigned long flags;
>>> +	bool ret;
>>>    	spin_lock_irqsave(&map->swap_lock, flags);
>>> -	if (!map->cleared)
>>> +	if (!map->cleared) {
>>> +		ret = !!map->word;
>>
>> After atomic_long_andnot(mask, (atomic_long_t *)&map->word), map->word
>> may be 0 if all requests have completed, or not 0 if some requests are
>> still in flight.
> 
> setting ->word is lockless, but zeroing ->word is serialized with ->swap_lock.
> 
>> Therefore, using !!map->word to determine the
>> availability of free tags is inaccurate.
> 
> The check should be changed to decide if any free bit is available in
> map->word instead of !!map->word, and 'shift' need to be passed in
> sbitmap_deferred_clear().
> 
> Just be curious, do you have reproducer for this issue?

It's hard to reproduce, but it's reproducible. We've encountered this
issue several times.

Thanks

> 
> Thanks,
> Ming
>