Merge branch 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/dtor/input

[cascardo/linux.git] / lib / sbitmap.c

diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index dfc084a..2cecf05 100644 (file)
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -15,6 +15,7 @@
  * 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,
@@ -168,7 +169,7 @@ EXPORT_SYMBOL_GPL(sbitmap_any_bit_clear);
 
 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];
@@ -196,7 +197,7 @@ static unsigned int sbq_calc_wake_batch(unsigned int depth)
 }
 
 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;
@@ -205,11 +206,23 @@ int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth,
        if (ret)
                return ret;
 
+       sbq->alloc_hint = alloc_percpu_gfp(unsigned int, flags);
+       if (!sbq->alloc_hint) {
+               sbitmap_free(&sbq->sb);
+               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);
 
-       sbq->ws = kzalloc(SBQ_WAIT_QUEUES * sizeof(*sbq->ws), flags);
+       sbq->ws = kzalloc_node(SBQ_WAIT_QUEUES * sizeof(*sbq->ws), flags, node);
        if (!sbq->ws) {
+               free_percpu(sbq->alloc_hint);
                sbitmap_free(&sbq->sb);
                return -ENOMEM;
        }
@@ -218,6 +231,8 @@ int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth,
                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);
@@ -229,6 +244,34 @@ void sbitmap_queue_resize(struct sbitmap_queue *sbq, unsigned int depth)
 }
 EXPORT_SYMBOL_GPL(sbitmap_queue_resize);
 
+int __sbitmap_queue_get(struct sbitmap_queue *sbq)
+{
+       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) {
+               /* 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(sbq->round_robin)) {
+               /* Only update the hint if we used it. */
+               hint = nr + 1;
+               if (hint >= depth - 1)
+                       hint = 0;
+               this_cpu_write(*sbq->alloc_hint, hint);
+       }
+
+       return nr;
+}
+EXPORT_SYMBOL_GPL(__sbitmap_queue_get);
+
 static struct sbq_wait_state *sbq_wake_ptr(struct sbitmap_queue *sbq)
 {
        int i, wake_index;
@@ -273,10 +316,13 @@ static void sbq_wake_up(struct sbitmap_queue *sbq)
        }
 }
 
-void sbitmap_queue_clear(struct sbitmap_queue *sbq, unsigned int nr)
+void sbitmap_queue_clear(struct sbitmap_queue *sbq, unsigned int nr,
+                        unsigned int cpu)
 {
        sbitmap_clear_bit(&sbq->sb, nr);
        sbq_wake_up(sbq);
+       if (likely(!sbq->round_robin && nr < sbq->sb.depth))
+               *per_cpu_ptr(sbq->alloc_hint, cpu) = nr;
 }
 EXPORT_SYMBOL_GPL(sbitmap_queue_clear);