* along with this program. If not, see <https://www.gnu.org/licenses/>.
*/
+#include <linux/random.h>
#include <linux/sbitmap.h>
int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift,
unsigned int sbitmap_weight(const struct sbitmap *sb)
{
- unsigned int i, weight;
+ unsigned int i, weight = 0;
for (i = 0; i < sb->map_nr; i++) {
const struct sbitmap_word *word = &sb->map[i];
}
int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth,
- int shift, gfp_t flags, int node)
+ int shift, bool round_robin, gfp_t flags, int node)
{
int ret;
int i;
return -ENOMEM;
}
+ if (depth && !round_robin) {
+ for_each_possible_cpu(i)
+ *per_cpu_ptr(sbq->alloc_hint, i) = prandom_u32() % depth;
+ }
+
sbq->wake_batch = sbq_calc_wake_batch(depth);
atomic_set(&sbq->wake_index, 0);
init_waitqueue_head(&sbq->ws[i].wait);
atomic_set(&sbq->ws[i].wait_cnt, sbq->wake_batch);
}
+
+ sbq->round_robin = round_robin;
return 0;
}
EXPORT_SYMBOL_GPL(sbitmap_queue_init_node);
}
EXPORT_SYMBOL_GPL(sbitmap_queue_resize);
-int __sbitmap_queue_get(struct sbitmap_queue *sbq, bool round_robin)
+int __sbitmap_queue_get(struct sbitmap_queue *sbq)
{
- unsigned int hint;
+ unsigned int hint, depth;
int nr;
hint = this_cpu_read(*sbq->alloc_hint);
- nr = sbitmap_get(&sbq->sb, hint, round_robin);
+ 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) {
/* If the map is full, a hint won't do us much good. */
this_cpu_write(*sbq->alloc_hint, 0);
- } else if (nr == hint || unlikely(round_robin)) {
+ } 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);
}
}
void sbitmap_queue_clear(struct sbitmap_queue *sbq, unsigned int nr,
- bool round_robin, unsigned int cpu)
+ unsigned int cpu)
{
sbitmap_clear_bit(&sbq->sb, nr);
sbq_wake_up(sbq);
- if (likely(!round_robin))
+ if (likely(!sbq->round_robin && nr < sbq->sb.depth))
*per_cpu_ptr(sbq->alloc_hint, cpu) = nr;
}
EXPORT_SYMBOL_GPL(sbitmap_queue_clear);