| Message ID | 20240715091125.36381-1-yang.yang@vivo.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | [v7] sbitmap: fix io hung due to race on sbitmap_word::cleared | expand |
On 7/15/24 2:11 AM, Yang Yang wrote: > + > + /** > + * @swap_lock: serializes simultaneous updates of ->word and ->cleared > + */ > + spinlock_t swap_lock; > } ____cacheline_aligned_in_smp; Thank you for having updated this comment. > -static inline bool sbitmap_deferred_clear(struct sbitmap_word *map) > +static inline bool sbitmap_deferred_clear(struct sbitmap_word *map, > + unsigned int depth, unsigned int alloc_hint, bool wrap) > { > - unsigned long mask; > + unsigned long mask, word_mask; > + bool ret = false; > > - if (!READ_ONCE(map->cleared)) > - return false; > + guard(spinlock_irqsave)(&map->swap_lock); > + > + if (!map->cleared) { > + if (depth > 0) { > + word_mask = (~0UL) >> (BITS_PER_LONG - depth); > + /* > + * The current behavior is to always retry after moving > + * ->cleared to word, and we change it to retry in case > + * of any free bits. To avoid an infinite loop, we need > + * to take wrap & alloc_hint into account, otherwise a > + * soft lockup may occur. > + */ > + if (!wrap && alloc_hint) > + word_mask &= ~((1UL << alloc_hint) - 1); > + > + if ((READ_ONCE(map->word) & word_mask) == word_mask) > + ret = false; > + else > + ret = true; > + } > + > + return ret; > + } Now that guard()() is being used, the local variable 'ret' can be eliminated. The if (READ_ONCE() ...) statement can be changed into the following: return (READ_ONCE(map->word) & word_mask) != word_mask; and "return ret;" can be changed into "return false;". Additionally, the indentation depth can be reduced by changing "if (depth > 0) {" ... into "if (depth == 0) return false;". Otherwise this patch looks good to me. Thanks, Bart.
On 2024/7/16 1:26, Bart Van Assche wrote: > On 7/15/24 2:11 AM, Yang Yang wrote: >> + >> + /** >> + * @swap_lock: serializes simultaneous updates of ->word and ->cleared >> + */ >> + spinlock_t swap_lock; >> } ____cacheline_aligned_in_smp; > > Thank you for having updated this comment. > >> -static inline bool sbitmap_deferred_clear(struct sbitmap_word *map) >> +static inline bool sbitmap_deferred_clear(struct sbitmap_word *map, >> + unsigned int depth, unsigned int alloc_hint, bool wrap) >> { >> - unsigned long mask; >> + unsigned long mask, word_mask; >> + bool ret = false; >> - if (!READ_ONCE(map->cleared)) >> - return false; >> + guard(spinlock_irqsave)(&map->swap_lock); >> + >> + if (!map->cleared) { >> + if (depth > 0) { >> + word_mask = (~0UL) >> (BITS_PER_LONG - depth); >> + /* >> + * The current behavior is to always retry after moving >> + * ->cleared to word, and we change it to retry in case >> + * of any free bits. To avoid an infinite loop, we need >> + * to take wrap & alloc_hint into account, otherwise a >> + * soft lockup may occur. >> + */ >> + if (!wrap && alloc_hint) >> + word_mask &= ~((1UL << alloc_hint) - 1); >> + >> + if ((READ_ONCE(map->word) & word_mask) == word_mask) >> + ret = false; >> + else >> + ret = true; >> + } >> + >> + return ret; >> + } > > Now that guard()() is being used, the local variable 'ret' can be eliminated. The if > (READ_ONCE() ...) statement can be changed into the > following: return (READ_ONCE(map->word) & word_mask) != word_mask; > and "return ret;" can be changed into "return false;". Additionally, > the indentation depth can be reduced by changing "if (depth > 0) {" ... > into "if (depth == 0) return false;". This looks much better, I will make these changes in the next version. Thanks. > > Otherwise this patch looks good to me. > > Thanks, > > Bart.
diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h index d662cf136021..c09cdcc99471 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: serializes simultaneous updates of ->word and ->cleared + */ + spinlock_t swap_lock; } ____cacheline_aligned_in_smp; /** diff --git a/lib/sbitmap.c b/lib/sbitmap.c index 1e453f825c05..3c00fe4b74fc 100644 --- a/lib/sbitmap.c +++ b/lib/sbitmap.c @@ -60,12 +60,35 @@ static inline void update_alloc_hint_after_get(struct sbitmap *sb, /* * See if we have deferred clears that we can batch move */ -static inline bool sbitmap_deferred_clear(struct sbitmap_word *map) +static inline bool sbitmap_deferred_clear(struct sbitmap_word *map, + unsigned int depth, unsigned int alloc_hint, bool wrap) { - unsigned long mask; + unsigned long mask, word_mask; + bool ret = false; - if (!READ_ONCE(map->cleared)) - return false; + guard(spinlock_irqsave)(&map->swap_lock); + + if (!map->cleared) { + if (depth > 0) { + word_mask = (~0UL) >> (BITS_PER_LONG - depth); + /* + * The current behavior is to always retry after moving + * ->cleared to word, and we change it to retry in case + * of any free bits. To avoid an infinite loop, we need + * to take wrap & alloc_hint into account, otherwise a + * soft lockup may occur. + */ + if (!wrap && alloc_hint) + word_mask &= ~((1UL << alloc_hint) - 1); + + if ((READ_ONCE(map->word) & word_mask) == word_mask) + ret = false; + else + ret = true; + } + + return ret; + } /* * First get a stable cleared mask, setting the old mask to 0. @@ -85,6 +108,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 +140,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); @@ -126,7 +153,7 @@ void sbitmap_resize(struct sbitmap *sb, unsigned int depth) unsigned int i; for (i = 0; i < sb->map_nr; i++) - sbitmap_deferred_clear(&sb->map[i]); + sbitmap_deferred_clear(&sb->map[i], 0, 0, 0); sb->depth = depth; sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word); @@ -179,7 +206,7 @@ static int sbitmap_find_bit_in_word(struct sbitmap_word *map, alloc_hint, wrap); if (nr != -1) break; - if (!sbitmap_deferred_clear(map)) + if (!sbitmap_deferred_clear(map, depth, alloc_hint, wrap)) break; } while (1); @@ -496,7 +523,7 @@ unsigned long __sbitmap_queue_get_batch(struct sbitmap_queue *sbq, int nr_tags, unsigned int map_depth = __map_depth(sb, index); unsigned long val; - sbitmap_deferred_clear(map); + sbitmap_deferred_clear(map, 0, 0, 0); val = READ_ONCE(map->word); if (val == (1UL << (map_depth - 1)) - 1) goto next;
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. This patch achieves two purposes: 1. Check on ->cleared and update on both ->cleared and ->word need to be done atomically, and using spinlock could be the simplest solution. 2. Add extra check in sbitmap_deferred_clear(), to identify whether ->word has free bits. Fixes: ea86ea2cdced ("sbitmap: ammortize cost of clearing bits") Signed-off-by: Yang Yang <yang.yang@vivo.com> Reviewed-by: Ming Lei <ming.lei@redhat.com> --- Changes from v6: - Use guard() for locking by suggestion - Modify comments by suggestion Changes from v5: - Modify commit message - Change the fixes tag Changes from v4: - Add some comments according to suggestion Changes from v3: - Add more arguments to sbitmap_deferred_clear(), for those who don't care about the return value, just pass 0 - Consider the situation when using sbitmap_get_shallow() - Consider the situation when ->round_robin is true - Modify commit message Changes from v2: - Modify commit message by suggestion - Add extra check in sbitmap_deferred_clear() by suggestion Changes from v1: - simply revert commit 661d4f55a794 ("sbitmap: remove swap_lock") --- include/linux/sbitmap.h | 5 +++++ lib/sbitmap.c | 41 ++++++++++++++++++++++++++++++++++------- 2 files changed, 39 insertions(+), 7 deletions(-)