ANDROID: Fixed the KMI corruption issue caused by the patch of 72d04bdcf3f7.
Due to 72d04bdcf3f7 ("sbitmap: fix io hung due to race on sbitmap_word
::cleared") directly adding spinlock_t swap_1ock to struct sbitmap_word
in sbitmap.h, KMI was damaged. In order to achieve functionality without
damaging KMI, we can only apply for a block of memory with a size of
map_nr * (sizeof (* sb ->map)+sizeof(spinlock_t)) to ensure that each
struct sbitmap-word receives protection from spinlock.
The actual memory distribution used is as follows:
----------------------
struct sbitmap_word[0]
......................
struct sbitmap_word[n]
-----------------------
spinlock_t swap_lock[0]
.......................
spinlock_t swap_lock[n]
----------------------
sbitmap_word[0] corresponds to swap_lock[0], and sbitmap_word[n]
corresponds to swap_lock[n], and so on.
Fixes: ea86ea2cdced ("sbitmap: ammortize cost of clearing bits")
Signed-off-by: Yang Yang <[email protected]>
Reviewed-by: Ming Lei <[email protected]>
Reviewed-by: Bart Van Assche <[email protected]>
Bug: 382398521
Link: https://lore.kernel.org/r/[email protected]
Change-Id: Idcab0dd5fd7c3147efd05dd6cc51757c2b0464f6
Signed-off-by: liuyu <[email protected]>
Bug: 401681610
diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h
index c09cdcc..d662cf1 100644
--- a/include/linux/sbitmap.h
+++ b/include/linux/sbitmap.h
@@ -36,11 +36,6 @@ 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 9307bf1..e188d4f 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -57,15 +57,69 @@ static inline void update_alloc_hint_after_get(struct sbitmap *sb,
}
}
+/**
+ * sbitmap_spinlock() - Get the spinlock corresponding to sbitmap_work.
+ * @map: The memory address of the index sbitmap_work area.
+ * @map_nr: Number of words (cachelines) being used for the bitmap.
+ * @index: The index of the spinlock.
+ *
+ * this lock: serializes simultaneous updates of ->word and ->cleared.
+ * sbitmap_spinlock is for checking on ->cleared and updating on both
+ * ->cleared and ->word need to be done atomically.
+ * Prevent the following situations from causing block:
+ * 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.
+ *
+ * Return: Returns the spinlock corresponding to index.
+ */
+static spinlock_t *sbitmap_spinlock(struct sbitmap_word *map,
+ unsigned int map_nr, unsigned int index)
+{
+ spinlock_t *base_lock = (spinlock_t *)(&map[map_nr - index]);
+
+ BUG_ON(((unsigned long)base_lock % __alignof__(spinlock_t)));
+ return &base_lock[index];
+}
+
/*
* See if we have deferred clears that we can batch move
*/
static inline bool sbitmap_deferred_clear(struct sbitmap_word *map,
- unsigned int depth, unsigned int alloc_hint, bool wrap)
+ unsigned int depth, unsigned int alloc_hint, bool wrap,
+ unsigned int map_nr, unsigned int index)
{
unsigned long mask, word_mask;
+ spinlock_t *swap_lock = sbitmap_spinlock(map, map_nr, index);
- guard(spinlock_irqsave)(&map->swap_lock);
+ guard(spinlock_irqsave)(swap_lock);
if (!map->cleared) {
if (depth == 0)
@@ -129,14 +183,36 @@ int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift,
sb->alloc_hint = NULL;
}
- sb->map = kvzalloc_node(sb->map_nr * sizeof(*sb->map), flags, node);
+ /* Due to 72d04bdcf3f7 ("sbitmap: fix io hung due to race on sbitmap_word
+ * ::cleared") directly adding spinlock_t swap_1ock to struct sbitmap_word
+ * in sbitmap.h, KMI was damaged. In order to achieve functionality without
+ * damaging KMI, we can only apply for a block of memory with a size of
+ * map_nr * (sizeof (* sb ->map)+sizeof(spinlock_t)) to ensure that each
+ * struct sbitmap-word receives protection from spinlock.
+ * The actual memory distribution used is as follows:
+ * ----------------------
+ * struct sbitmap_word[0]
+ * ......................
+ * struct sbitmap_word[n]
+ * -----------------------
+ * spinlock_t swap_lock[0]
+ * .......................
+ * spinlock_t swap_lock[n]
+ * ----------------------
+ * sbitmap_word[0] corresponds to swap_lock[0], and sbitmap_word[n]
+ * corresponds to swap_lock[n], and so on
+ */
+ sb->map = kvzalloc_node(sb->map_nr * (sizeof(*sb->map) + sizeof(spinlock_t)), flags, node);
if (!sb->map) {
free_percpu(sb->alloc_hint);
return -ENOMEM;
}
- for (i = 0; i < sb->map_nr; i++)
- spin_lock_init(&sb->map[i].swap_lock);
+ for (i = 0; i < sb->map_nr; i++) {
+ spinlock_t *swap_lock = sbitmap_spinlock(&sb->map[i], sb->map_nr, i);
+
+ spin_lock_init(swap_lock);
+ }
return 0;
}
@@ -148,7 +224,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], 0, 0, 0);
+ sbitmap_deferred_clear(&sb->map[i], 0, 0, 0, sb->map_nr, i);
sb->depth = depth;
sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word);
@@ -192,7 +268,9 @@ static int __sbitmap_get_word(unsigned long *word, unsigned long depth,
static int sbitmap_find_bit_in_word(struct sbitmap_word *map,
unsigned int depth,
unsigned int alloc_hint,
- bool wrap)
+ bool wrap,
+ unsigned int map_nr,
+ unsigned int index)
{
int nr;
@@ -201,7 +279,7 @@ static int sbitmap_find_bit_in_word(struct sbitmap_word *map,
alloc_hint, wrap);
if (nr != -1)
break;
- if (!sbitmap_deferred_clear(map, depth, alloc_hint, wrap))
+ if (!sbitmap_deferred_clear(map, depth, alloc_hint, wrap, map_nr, index))
break;
} while (1);
@@ -222,7 +300,8 @@ static int sbitmap_find_bit(struct sbitmap *sb,
min_t(unsigned int,
__map_depth(sb, index),
depth),
- alloc_hint, wrap);
+ alloc_hint, wrap,
+ sb->map_nr, index);
if (nr != -1) {
nr += index << sb->shift;
@@ -523,7 +602,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, 0, 0, 0);
+ sbitmap_deferred_clear(map, 0, 0, 0, sb->map_nr, index);
val = READ_ONCE(map->word);
if (val == (1UL << (map_depth - 1)) - 1)
goto next;
