diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index 928b82a..f736c52 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -246,10 +246,15 @@
 
 int __sbitmap_queue_get(struct sbitmap_queue *sbq)
 {
-	unsigned int hint;
+	unsigned int hint, depth;
 	int nr;
 
 	hint = this_cpu_read(*sbq->alloc_hint);
+	depth = READ_ONCE(sbq->sb.depth);
+	if (unlikely(hint >= depth)) {
+		hint = depth ? prandom_u32() % depth : 0;
+		this_cpu_write(*sbq->alloc_hint, hint);
+	}
 	nr = sbitmap_get(&sbq->sb, hint, sbq->round_robin);
 
 	if (nr == -1) {
@@ -258,7 +263,7 @@
 	} else if (nr == hint || unlikely(sbq->round_robin)) {
 		/* Only update the hint if we used it. */
 		hint = nr + 1;
-		if (hint >= sbq->sb.depth - 1)
+		if (hint >= depth - 1)
 			hint = 0;
 		this_cpu_write(*sbq->alloc_hint, hint);
 	}