Skip to contentSkip to conversation

sbitmap: boundary checks for resized bitmap

PATCH In review Hannes Reinecke 2 participants 3 messages Feb 15, 2017 – Mar 1, 2017

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 sbitmap: boundary checks for resized bitmap

If the sbitmap gets resized we need to ensure not to overflow the original allocation. And we should limit the search in sbitmap_any_bit_set() to the available depth to avoid looking into unused space.

---
 include/linux/sbitmap.h |  5 +++++
 lib/sbitmap.c           | 12 +++++++++---
 2 files changed, 14 insertions(+), 3 deletions(-)
include/linux/sbitmap.h +5 -0
index d4e0a20..5ed3815 100644
@@ -61,6 +61,11 @@ struct sbitmap {
 	unsigned int map_nr;
 
 	/**
+	 * @map_nr: Number of words (cachelines) allocated for the bitmap.
+	 */
+	unsigned int max_map_nr;
+
+	/**
 	 * @map: Allocated bitmap.
 	 */
 	struct sbitmap_word *map;
lib/sbitmap.c +9 -3
index 55e11c4..f6f18b7 100644
@@ -44,7 +44,7 @@ int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift,
 
 	sb->shift = shift;
 	sb->depth = depth;
-	sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word);
+	sb->map_nr = sb->max_map_nr = DIV_ROUND_UP(sb->depth, bits_per_word);
 
 	if (depth == 0) {
 		sb->map = NULL;
@@ -70,7 +70,8 @@ void sbitmap_resize(struct sbitmap *sb, unsigned int depth)
 
 	sb->depth = depth;
 	sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word);
-
+	if (sb->map_nr > sb->max_map_nr)
+		sb->map_nr = sb->max_map_nr;
 	for (i = 0; i < sb->map_nr; i++) {
 		sb->map[i].depth = min(depth, bits_per_word);
 		depth -= sb->map[i].depth;
@@ -145,7 +146,11 @@ bool sbitmap_any_bit_set(const struct sbitmap *sb)
 	unsigned int i;
 
 	for (i = 0; i < sb->map_nr; i++) {
-		if (sb->map[i].word)
+		const struct sbitmap_word *word = &sb->map[i];
+		unsigned long ret;
+
+		ret = find_first_bit(&word->word, word->depth);
+		if (ret < word->depth)
 			return true;
 	}
 	return false;
@@ -187,6 +192,7 @@ void sbitmap_show(struct sbitmap *sb, struct seq_file *m)
 	seq_printf(m, "busy=%u\n", sbitmap_weight(sb));
 	seq_printf(m, "bits_per_word=%u\n", 1U << sb->shift);
 	seq_printf(m, "map_nr=%u\n", sb->map_nr);
+	seq_printf(m, "max_map_nr=%u\n", sb->max_map_nr);
 }
 EXPORT_SYMBOL_GPL(sbitmap_show);
 
Signature · 1 line
1.8.5.6
#1 lore raw
Quoted 4 lines · Hannes Reinecke

If the sbitmap gets resized we need to ensure not to overflow the original allocation. And we should limit the search in sbitmap_any_bit_set() to the available depth to avoid looking into unused space.

Hey, Hannes, I don't really like this change. It's easy enough for the caller to keep track of this and check themselves if they really care. I even included a comment in sbitmap.h to that effect:

/**
* sbitmap_resize() - Resize a &struct sbitmap.
* @sb: Bitmap to resize.
* @depth: New number of bits to resize to.
*
* Doesn't reallocate anything. It's up to the caller to ensure that the new
* depth doesn't exceed the depth that the sb was initialized with. */

As for the sbitmap_any_bit_set() change, the bits beyond the actual depth should all be zero, so I don't think that change is worth it, either.

Thanks!

#2 lore raw
Quoted 10 lines · Omar Sandoval
Quoted 4 lines · Hannes Reinecke

If the sbitmap gets resized we need to ensure not to overflow the original allocation. And we should limit the search in sbitmap_any_bit_set() to the available depth to avoid looking into unused space.

Hey, Hannes, I don't really like this change. It's easy enough for the caller to keep track of this and check themselves if they really care. I even included a comment in sbitmap.h to that effect:

Okay.

Quoted 10 lines

/**
* sbitmap_resize() - Resize a &struct sbitmap.
* @sb: Bitmap to resize.
* @depth: New number of bits to resize to.
*
* Doesn't reallocate anything. It's up to the caller to ensure that the new
* depth doesn't exceed the depth that the sb was initialized with. */

Quoted 4 lines

As for the sbitmap_any_bit_set() change, the bits beyond the actual depth should all be zero, so I don't think that change is worth it, either.

Hmm. That would be okay if we can be sure that the remaining bits really are zero. Which probably would need to be checked by the caller, too.

So yeah, if you don't like it, okay.
Just ignore it then.

Cheers,

Hannes

Signature · 4 lines
Dr. Hannes Reinecke		      zSeries & Storage
[email protected]			      +49 911 74053 688
SUSE LINUX Products GmbH, Maxfeldstr. 5, 90409 N�rnberg
GF: J. Hawn, J. Guild, F. Imend�rffer, HRB 16746 (AG N�rnberg)