Received-SPF: pass (google.com: domain of linux-kernel+bounces-193962-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: <da901f5c-c14e-4e1c-b3c0-d3dead195ca1@vivo.com>
Date: Wed, 29 May 2024 18:31:09 +0800
User-Agent: Mozilla Thunderbird
From: YangYang <yang.yang@vivo.com>
Subject: Re: [RFC PATCH] sbitmap: fix io hung due to race on
 sbitmap_word::cleared
To: Jens Axboe <axboe@kernel.dk>, Andrew Morton <akpm@linux-foundation.org>,
 Pavel Begunkov <asml.silence@gmail.com>
Cc: linux-kernel@vger.kernel.org, linux-block@vger.kernel.org
References: <20240527042654.2404-1-yang.yang@vivo.com>
Content-Language: en-US
In-Reply-To: <20240527042654.2404-1-yang.yang@vivo.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: bulk
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0:
	=?utf-8?B?NkRwSVA3dVZlUCt3S1FLV05KY2xWSHk0YVZmTGRyU1ozNU5zdXlXUWpoT2ZC?=
 =?utf-8?B?KzFiSG1sblhRNjRNcFRCSjJSWTBkNUpCVnhKd001MzY2WlR0V3VHWTlKZFpx?=
 =?utf-8?B?UHNUeU10Y1J2aTNVcVpKbUNmazlIak5wTzFDOEVFdkhJYU1hOThISTl1VjEr?=
 =?utf-8?B?OTRneHFnU1lmdjYxY3UyZkdPeGN3YkJWZ2RpaVVTeENRa3QyNjdxQnJEd1I2?=
 =?utf-8?B?N013OFczY0NId3JoNGowMmh2dFZnandBNmJERDJmenZ5a25pTzdwOTdKbjRX?=
 =?utf-8?B?WC9FeVlLbldOTWJ6YzMwVnBINVVMODgxZ012ZjJQVmRnaVFkbGF1Vm9rbnZN?=
 =?utf-8?B?clhzVW5DSFgyNVZSeStpTzNzU081Q1RGMDgvc0tVK0p2ZkFGcXAvdERIUEMx?=
 =?utf-8?B?Qy9qcmxqbFBBRHljSzBFUEZDcGFQSkNHV3FUUW5sZHkvZ1kwOFBja0RkTkcx?=
 =?utf-8?B?V3R5b0ppMGRDZURZczZvVE1vS3g4dW5LblgydnZydVhBOVdhMkd5QlF1Umk5?=
 =?utf-8?B?VTVUaytpQ2xrdEVDWE4xUGdTNlgxU3BqTUdyTTNnZkh3SVBJTFdIb1c0MzF0?=
 =?utf-8?B?OTh6am0xcVB5MlozS1UvTWpWWXNxMlFicmh6NGs2NzV4aE1tQUQya1gvbXJi?=
 =?utf-8?B?UnVzUHZlc014Q29sTXh1OE0yMkxST2NrMll6YUtrbGk2Qks4ajF5K0lUSFd1?=
 =?utf-8?B?cWw3a3MvYk9jRmhTb2xVNHQxTEQvaGhQc0dHWGVhb3h1MkZ6OUlHWjR5MC85?=
 =?utf-8?B?ODE5WlJxZmtYcG1raDBPUDRYdE9lOGIrMW0wQWErMXhKS0xIQ2RLZUR0MlB1?=
 =?utf-8?B?RDJXWXdEOGhvbEcyNG5qdGZLS0pkVnhQdURUaEFPNjJrWElQTmZFNUJEa2E1?=
 =?utf-8?B?ZzZkbWZCT0s4dCtGQ2VCQ01DYzZ1NW9WNlB2OEhnTWtUUWVMaktERDNzdTJi?=
 =?utf-8?B?MjMxdk8rRzVKZHFmakVsRUZOSVEwY2dhdVJieTIzT3J6Q3NaejBzdS9wK3ps?=
 =?utf-8?B?WDBkdUpNMXJ6TTh3elc3Z1ovbTlaL2hiZWx1RTZSUjczQndIQXpxbjVvTW5l?=
 =?utf-8?B?bEVxcWF6NHhDSWVpMkhuMXBiVjV3SnJqd3IzY2FYYnA4emR4ZWRZS0xtNDZZ?=
 =?utf-8?B?d092emkwOHNPNk9GR2RwSyt5N1RwSEc3OFVsR1dsODFEU29hNUZEVmh6VTZa?=
 =?utf-8?B?eTFvWVQ0RzF0TzZ6bzJBa0FsLzE3TUxNdXJpSlUyWHFjVjJlZ050aVJ0aGxG?=
 =?utf-8?B?UVBxSzJBNDcyKzVlbzVtWWFKUFJDSlRKWEMvNFIzYkhSTktHTHEyQnptbWpZ?=
 =?utf-8?B?OGR1MDk2Qm1wWHo5K1lZT2NIT0o3c0RqeENoQWlFamJvN1RKcnZTZkRFa3E2?=
 =?utf-8?B?Y01nTDFvdEdKRXpUdVc0M2ZGUXQ2QzNEQWNiMGN6cDZOUXdvb2RWeDdlMTMw?=
 =?utf-8?B?aHQ4SlVLdWlTY2JnR3J5OHFQVW00VGtUS3ptcFhUWUVuTTBRekszd0h6M2hy?=
 =?utf-8?B?a3d4VnpsQVh6ZDYweDlqcTBrcXJrN2kyZFNiOElpVmxKWUh3U2wrWlBtVXQr?=
 =?utf-8?B?aVBteTM1UjBNc0psU1JybGZBclVrQmNYYk11Q1N1K1phSW9vS0JTL3lXVXg1?=
 =?utf-8?B?K1NrNzdIK1JpWUZ5SExJUlZJZHpnUjlnQjhqdTBqOEZwUmwySUhIc2FZQjNU?=
 =?utf-8?B?aGd2L0pvaUhhZDRvNzlORjE4UXJjekJsKzQ3SjZya0ZhVTlVTWhVTkxOSzU3?=
 =?utf-8?B?RTR2OVZOTlVoL1Urb3FnSjZ2WW5DTjlpUHNQTHQ4VGc3NFc5a2lQRHZKL3V1?=
 =?utf-8?B?amlnVTFaSVR1T2R2YktybFdKR0k2anExRDJLdERWTUVnUEoralNXTzdnZHl2?=
 =?utf-8?B?VDNIaWNzYi94cGxSR3IrUW5nZ01rbHVuQnZaSWk5dVQ4TFFndENEUGlKMEJV?=
 =?utf-8?B?U2RURFNuUHJNQXpTYkcxNFp3NGMwYVJoSU9XUXl4dmlKUUlPR0h1TUZGbVNx?=
 =?utf-8?B?ZGZwMmlwanZnWmNqUFF4dTFyNlZyMDF1TnNYTmZ1OCtZZEw5L0tIK2NrVjNN?=
 =?utf-8?B?UnNLSS9WVUt3R0VSK21LYWN6M0l6MzJQRGQrc3MwU25tbTcrak5EQlgrYW1p?=
 =?utf-8?Q?lrNrDK3b0fnGVM6G7ExbPDl/9?=
X-OriginatorOrg: vivo.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 243af9ef-fcf9-45f4-be8c-08dc7fca7610
X-MS-Exchange-CrossTenant-AuthSource: KL1PR06MB7401.apcprd06.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 29 May 2024 10:31:12.1823
 (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: kkZiyU+c2KPifPKdbGfrIvwMrjKZAbSh6nWC5zDektAWhsmNo/pf+3ZzM7SclJeZK9DETjEguM0sCKrUGuUSgA==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: TYSPR06MB6541

On 2024/5/27 12:26, Yang Yang 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.

Right at this moment, if a new task attempts to switch the elevator, these
tasks may hang forever.

   T2:                      T3:                          T4:
   blk_mq_submit_bio        .                            .
   __blk_mq_alloc_requests  .                            .
   blk_mq_get_tag           .                            .
   io_schedule              .                            .
                            elevator_switch              .
                            blk_mq_freeze_queue          .
                            blk_freeze_queue_start       .
                            q->mq_freeze_depth=1         .
                            blk_mq_freeze_queue_wait     .
                                                         blk_mq_submit_bio
                                                         __bio_queue_enter
                                                         wait_event(!q->mq_freeze_depth)

> 
> Fix this issue by adding a new flag swap_inprogress to indicate whether
> the swap is ongoing.
> 
> Fixes: 661d4f55a794 ("sbitmap: remove swap_lock")
> Signed-off-by: Yang Yang <yang.yang@vivo.com>
> ---
>   include/linux/sbitmap.h |  5 +++++
>   lib/sbitmap.c           | 22 ++++++++++++++++++++--
>   2 files changed, 25 insertions(+), 2 deletions(-)
> 
> diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h
> index d662cf136021..b88a9e4997ab 100644
> --- a/include/linux/sbitmap.h
> +++ b/include/linux/sbitmap.h
> @@ -36,6 +36,11 @@ struct sbitmap_word {
>   	 * @cleared: word holding cleared bits
>   	 */
>   	unsigned long cleared ____cacheline_aligned_in_smp;
> +
> +	/**
> +	 * @swap_inprogress: set to 1 when swapping word <-> cleared
> +	 */
> +	atomic_t swap_inprogress;
>   } ____cacheline_aligned_in_smp;
>   
>   /**
> diff --git a/lib/sbitmap.c b/lib/sbitmap.c
> index 1e453f825c05..d4bb258fe8b0 100644
> --- a/lib/sbitmap.c
> +++ b/lib/sbitmap.c
> @@ -62,10 +62,19 @@ static inline void update_alloc_hint_after_get(struct sbitmap *sb,
>    */
>   static inline bool sbitmap_deferred_clear(struct sbitmap_word *map)
>   {
> -	unsigned long mask;
> +	unsigned long mask, flags;
> +	int zero = 0;
>   
> -	if (!READ_ONCE(map->cleared))
> +	if (!READ_ONCE(map->cleared)) {
> +		if (atomic_read(&map->swap_inprogress))
> +			goto out_wait;
>   		return false;
> +	}
> +
> +	if (!atomic_try_cmpxchg(&map->swap_inprogress, &zero, 1))
> +		goto out_wait;
> +
> +	local_irq_save(flags);
>   
>   	/*
>   	 * First get a stable cleared mask, setting the old mask to 0.
> @@ -77,6 +86,15 @@ static inline bool sbitmap_deferred_clear(struct sbitmap_word *map)
>   	 */
>   	atomic_long_andnot(mask, (atomic_long_t *)&map->word);
>   	BUILD_BUG_ON(sizeof(atomic_long_t) != sizeof(map->word));
> +
> +	atomic_set(&map->swap_inprogress, 0);
> +	smp_mb__after_atomic();
> +	local_irq_restore(flags);
> +	return true;
> +
> +out_wait:
> +	while (atomic_read(&map->swap_inprogress))
> +		;
>   	return true;
>   }
>