Received-SPF: pass (google.com: domain of linux-kernel+bounces-203912-linux.lists.archive=gmail.com@vger.kernel.org designates 147.75.199.223 as permitted sender) client-ip=147.75.199.223;
Message-ID: <35bd4fe6-5ed0-4446-8fab-f86909212e60@vivo.com>
Date: Thu, 6 Jun 2024 16:55:17 +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: Yu Kuai <yukuai1@huaweicloud.com>, 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>
References: <20240604031124.2261-1-yang.yang@vivo.com>
 <CAFj5m9KV7OJ4_KjbSkpdtfrKamoLzV6EH-mJP3=y+VvoYOzC3w@mail.gmail.com>
 <aa7246f9-f7df-3054-077e-eb21c7f423ac@huaweicloud.com>
From: YangYang <yang.yang@vivo.com>
In-Reply-To: <aa7246f9-f7df-3054-077e-eb21c7f423ac@huaweicloud.com>
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?M3RPbnFDN2VScEk0SW5EYk9zQU0zbFkvVXFERmtPaWl4TVBJYUZTSlFJY05P?=
 =?utf-8?B?WnhvWWtTNzNjRFl6SDUxb3ZDZXAvVHNmbXlrSHNabzRSdWFpa3EzbS9HRVRU?=
 =?utf-8?B?dTRoUis3Sk5ndlRGdkl4SXpxVHVJb0s3VFBkYWM4VHVwRFBKSitmRldtU08y?=
 =?utf-8?B?V3NHbDVvc04vekx4SDlsR0crT0YwZEFmY1FreWhYNGNTd01lSWZ2NHFyNnNB?=
 =?utf-8?B?TUF6OWNJQ1ZWYk1sUlhnYS9ua0lwam4rV2RtVEQ1V2dlc2t0OGtVMXl2V3ZM?=
 =?utf-8?B?OWxhYTJ1QVdJUjhEV3ZHMzR4ZUpkQ3RudXBVUFZyMW1TSCs5S3V6WVRDRHRl?=
 =?utf-8?B?Vi9RRHljSWlBMDJ6NU5mdW9QT3RrQjFmUGo1Vy9tVzBLMTBwdmtXaWlwNnVM?=
 =?utf-8?B?cEhWRlFwQy94T0tVd2krb3d6VjBPZG53c0xibEpmM2JXYzFlY2tocTkyamFZ?=
 =?utf-8?B?cm1LS3dpeWd3c3liLzUxbGtrMEpkLzZlWUJKT3UzQ01sVzZqT1JHblExZ3FK?=
 =?utf-8?B?a1dQR3JiNW4vM3NYcFE5S3VJSGUzelZLWTR5N2pXK0JUZzZWVVJJSVdua3l3?=
 =?utf-8?B?SDljdUh1OEQ5RkI3THF3a0pUSG5Ed05jSFkvWXNnOUFDK2FGcE9UUEZNMExC?=
 =?utf-8?B?Q2V4aUNlbGowUFVSQVdMblpBcXhFM1E4VzVVS3haajVxNjdjYUsydWNMaTVD?=
 =?utf-8?B?WkdDR0FvSUJvMlp6Z1I3VlNnQlk5VWtPemUxZUxHQkpRZHgvM0gwYjVpWTl6?=
 =?utf-8?B?eTJScUcza1NBRFQ5c3YralVjS0dxdXNoNTJRUWhEVEVzWVhBZDZ6NHRBOG9u?=
 =?utf-8?B?UDI3dlFaQmlQdzhpN2F3Tk9RTzF1Lzg4Wk52cDRoZWVlUFMwTEhuYkpGWXY0?=
 =?utf-8?B?YmF0YUd6ZTF5ZkdIMDUvNDRrM0RodnVld1E0NnlPTStmSCtmaU5FODBUR3dD?=
 =?utf-8?B?MS9VM25ndTZKc3krOFhnVEdYVEsza1BoUjFKTjFPaEIzV1g3cVNWSHdzQlB0?=
 =?utf-8?B?TGRjdjZEMFhHNHovcklkcFpGeFBDSzZnb2xRdkFzNFY3Y2sxS0FjQWd0STR4?=
 =?utf-8?B?NlIxOFZhTWF6V3lFTXJhRHZPalMyai8zZlJ6V0ZrNy9MSWRaaGpLMDlGTlpY?=
 =?utf-8?B?ZlZMWkNESHhGWEVPc0hzcGoxTW50L0FOYVdRYzZqbDkyd05URlQxM2N0UGhG?=
 =?utf-8?B?b21HVS8rb1creXhLQTUwdlZlbDFUU25rTzN2U2JXb3I3S0JWRHh5a2VNaXFH?=
 =?utf-8?B?elZCNU83aFdnYlIveVBxb2lzZGdGZjFyR1VOMWFYRTBKWUt2cFVLaWpIa2Zh?=
 =?utf-8?B?UHRRWTQ1TEU4Umc5dlpocThjSVVPcWNka1Q4UWtRK1pmMWcrbkFPOVZiZUxx?=
 =?utf-8?B?OTBCVlFOZGdBOE02bkZkbWhzd3BOQUhDVGdLZ0ZjbVhSdCtDeG0wOGpMaWRC?=
 =?utf-8?B?RGxseVBuVms3RmJKUy9ld3NyNC9jR2d6S1NGekxnK3pRSkpjTDlBQUl6Qncr?=
 =?utf-8?B?d3FJV0dsbVV6bXJzUXk3aUFDdVBSVmxFNXM2ZVNIWW9sL0lBTGdXT3JtQVZ3?=
 =?utf-8?B?T2Qvb1RuRjNPNnFUKytHYjJ5aXNaTnNBVVlWTWVpaTBXcUZKWUE4TExoV29s?=
 =?utf-8?B?K0hOemdiZUZZSUtZN0htc0RrUXU5MXJyaW9UVytLZjNCRThaSTg4UGhaMWhU?=
 =?utf-8?B?ZlJrbGxFMForT2UxZTFoM3FzemdkRkd4Z2wxM2tQRWJxblFoMmdKb0RGN01m?=
 =?utf-8?B?b29MN3h0Q2ZGNi9ubTdrd05COGNKeWk3VzVndW9jSGxCdHN1OGd6VjBrQ2VC?=
 =?utf-8?B?WGl2cWlCSm5kQXoxdWlsQnRRMENhejIrMDI4TElYT251WVgrZm8xdUZCd2cz?=
 =?utf-8?B?V3ZsTFRrck4xalg4WjFCUy95TUxEZ1EraWpDQzBUdkZNMW4wK2M3L0NzVzdF?=
 =?utf-8?B?QkpHbGVZRmpSYVJoK2N6ZGxNWVV5YTFVTnp1dWFESTVFRkpXaVY2NjVQMDkw?=
 =?utf-8?B?M3dSdGVZc05KdEJMTFFPUFI0N3F2Q2xWOEFQMmRwVm5RSFR5ckhRWGM2akxI?=
 =?utf-8?B?N3hMSVRJRm82M1YzQzNiQ0NubWxYYk9EbVJQZS9GSmVXc0Ird0VhTVUxM21u?=
 =?utf-8?Q?EDNi/k0DwCilZm+2Oe22wwOWG?=
X-OriginatorOrg: vivo.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 5835f2ca-cd68-433d-f617-08dc8606652f
X-MS-Exchange-CrossTenant-AuthSource: KL1PR06MB7401.apcprd06.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 06 Jun 2024 08:55:20.6411
 (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: Ql3Pr+JC6sEnnke4pXpvk5psTzeQCU+L6Ei22UAoLjXd4nCJ7tiU8Pwg5FhWM1B6mWIzW5geZONG8KTnAvsVhg==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: TYZPR06MB6699

On 2024/6/4 14:12, 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):
> 
> t1:
> sbitmap_find_bit_in_word
>   __sbitmap_get_word
>   -> read old word, return -1
>          t2:
>          sbitmap_find_bit_in_word
>           __sbitmap_get_word
>           -> read old word, return -1
>   sbitmap_deferred_clear
>   -> clear cleared and update word
>          sbitmap_deferred_clear
>          -> cleared is cleared, fail
> 
> BYW, I still think it's fine to fix this problem by trying the
> __sbitmap_get_word() at least one more time if __sbitmap_get_word()
> failed.

How about this one:
1. Add extra check in sbitmap_find_bit_in_word() referenced from
    Yu kuai's suggestion.
2. Change from atomic_long_andnot to atomic_long_fetch_andnot_release

---
  include/linux/sbitmap.h |  5 +++++
  lib/sbitmap.c           | 23 ++++++++++++++++++-----
  2 files changed, 23 insertions(+), 5 deletions(-)

diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h
index d662cf136021..ec0b0e73c906 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_lock: Held while swapping word <-> cleared
+    */
+   spinlock_t swap_lock;
  } ____cacheline_aligned_in_smp;

  /**
diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index 1e453f825c05..63dadf91e40b 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -63,9 +63,13 @@ 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;

-   if (!READ_ONCE(map->cleared))
-       return false;
+   spin_lock_irqsave(&map->swap_lock, flags);
+
+   if (!map->cleared)
+       goto out_unlock;

     /*
      * First get a stable cleared mask, setting the old mask to 0.
@@ -75,9 +79,12 @@ static inline bool sbitmap_deferred_clear(struct sbitmap_word *map)
     /*
      * Now clear the masked bits in our free word
      */
-   atomic_long_andnot(mask, (atomic_long_t *)&map->word);
+   atomic_long_fetch_andnot_release(mask, (atomic_long_t *)&map->word);
     BUILD_BUG_ON(sizeof(atomic_long_t) != sizeof(map->word));
-   return true;
+   ret = true;
+out_unlock:
+   spin_unlock_irqrestore(&map->swap_lock, flags);
+   return ret;
  }

  int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift,
@@ -85,6 +92,7 @@ int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift,
               bool alloc_hint)
  {
     unsigned int bits_per_word;
+   int i;

     if (shift < 0)
         shift = sbitmap_calculate_shift(depth);
@@ -116,6 +124,9 @@ int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift,
         return -ENOMEM;
     }

+   for (i = 0; i < sb->map_nr; i++)
+       spin_lock_init(&sb->map[i].swap_lock);
+
     return 0;
  }
  EXPORT_SYMBOL_GPL(sbitmap_init_node);
@@ -175,11 +186,13 @@ static int sbitmap_find_bit_in_word(struct sbitmap_word *map,
     int nr;

     do {
+       unsigned long cleared = READ_ONCE(map->cleared);
+
         nr = __sbitmap_get_word(&map->word, depth,
                     alloc_hint, wrap);
         if (nr != -1)
             break;
-       if (!sbitmap_deferred_clear(map))
+       if (!sbitmap_deferred_clear(map) && !cleared)
             break;
     } while (1);

-- 
2.34.1

> 
> Thanks,
> Kuai
> 
>>
>> Thanks,
>>
>>
>> .
>>
>