mm: fs: invalidate BH LRU during page migration

[linux.git] / lib / sbitmap.c

diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index d693d9213ceb26f39d8e92a876e7b4787199ef76..47b3691058eb693a68de6a31403527f5dcc4e2c4 100644 (file)
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -9,6 +9,54 @@
 #include <linux/sbitmap.h>
 #include <linux/seq_file.h>
 
 #include <linux/sbitmap.h>
 #include <linux/seq_file.h>
 

+static int init_alloc_hint(struct sbitmap *sb, gfp_t flags)
+{
+       unsigned depth = sb->depth;
+
+       sb->alloc_hint = alloc_percpu_gfp(unsigned int, flags);
+       if (!sb->alloc_hint)
+               return -ENOMEM;
+
+       if (depth && !sb->round_robin) {
+               int i;
+
+               for_each_possible_cpu(i)
+                       *per_cpu_ptr(sb->alloc_hint, i) = prandom_u32() % depth;
+       }
+       return 0;
+}
+
+static inline unsigned update_alloc_hint_before_get(struct sbitmap *sb,
+                                                   unsigned int depth)
+{
+       unsigned hint;
+
+       hint = this_cpu_read(*sb->alloc_hint);
+       if (unlikely(hint >= depth)) {
+               hint = depth ? prandom_u32() % depth : 0;
+               this_cpu_write(*sb->alloc_hint, hint);
+       }
+
+       return hint;
+}
+
+static inline void update_alloc_hint_after_get(struct sbitmap *sb,
+                                              unsigned int depth,
+                                              unsigned int hint,
+                                              unsigned int nr)
+{
+       if (nr == -1) {
+               /* If the map is full, a hint won't do us much good. */
+               this_cpu_write(*sb->alloc_hint, 0);
+       } else if (nr == hint || unlikely(sb->round_robin)) {
+               /* Only update the hint if we used it. */
+               hint = nr + 1;
+               if (hint >= depth - 1)
+                       hint = 0;
+               this_cpu_write(*sb->alloc_hint, hint);
+       }
+}
+

 /*
  * See if we have deferred clears that we can batch move
  */
 /*
  * See if we have deferred clears that we can batch move
  */


@@ -33,24 +81,15 @@ static inline bool sbitmap_deferred_clear(struct sbitmap_word *map)
 }
 
 int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift,
 }
 
 int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift,

-                     gfp_t flags, int node)
+                     gfp_t flags, int node, bool round_robin,
+                     bool alloc_hint)

 {
        unsigned int bits_per_word;
        unsigned int i;
 
 {
        unsigned int bits_per_word;
        unsigned int i;
 

-       if (shift < 0) {
-               shift = ilog2(BITS_PER_LONG);
-               /*
-                * If the bitmap is small, shrink the number of bits per word so
-                * we spread over a few cachelines, at least. If less than 4
-                * bits, just forget about it, it's not going to work optimally
-                * anyway.
-                */
-               if (depth >= 4) {
-                       while ((4U << shift) > depth)
-                               shift--;
-               }
-       }
+       if (shift < 0)
+               shift = sbitmap_calculate_shift(depth);
+

        bits_per_word = 1U << shift;
        if (bits_per_word > BITS_PER_LONG)
                return -EINVAL;
        bits_per_word = 1U << shift;
        if (bits_per_word > BITS_PER_LONG)
                return -EINVAL;


@@ -58,15 +97,25 @@ 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->shift = shift;
        sb->depth = depth;
        sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word);

+       sb->round_robin = round_robin;

 
        if (depth == 0) {
                sb->map = NULL;
                return 0;
        }
 
 
        if (depth == 0) {
                sb->map = NULL;
                return 0;
        }
 

+       if (alloc_hint) {
+               if (init_alloc_hint(sb, flags))
+                       return -ENOMEM;
+       } else {
+               sb->alloc_hint = NULL;
+       }
+

        sb->map = kcalloc_node(sb->map_nr, sizeof(*sb->map), flags, node);
        sb->map = kcalloc_node(sb->map_nr, sizeof(*sb->map), flags, node);

-       if (!sb->map)
+       if (!sb->map) {
+               free_percpu(sb->alloc_hint);

                return -ENOMEM;
                return -ENOMEM;

+       }

 
        for (i = 0; i < sb->map_nr; i++) {
                sb->map[i].depth = min(depth, bits_per_word);
 
        for (i = 0; i < sb->map_nr; i++) {
                sb->map[i].depth = min(depth, bits_per_word);


@@ -129,14 +178,14 @@ static int __sbitmap_get_word(unsigned long *word, unsigned long depth,
 }
 
 static int sbitmap_find_bit_in_index(struct sbitmap *sb, int index,
 }
 
 static int sbitmap_find_bit_in_index(struct sbitmap *sb, int index,

-                                    unsigned int alloc_hint, bool round_robin)
+                                    unsigned int alloc_hint)

 {
        struct sbitmap_word *map = &sb->map[index];
        int nr;
 
        do {
                nr = __sbitmap_get_word(&map->word, map->depth, alloc_hint,
 {
        struct sbitmap_word *map = &sb->map[index];
        int nr;
 
        do {
                nr = __sbitmap_get_word(&map->word, map->depth, alloc_hint,

-                                       !round_robin);
+                                       !sb->round_robin);

                if (nr != -1)
                        break;
                if (!sbitmap_deferred_clear(map))
                if (nr != -1)
                        break;
                if (!sbitmap_deferred_clear(map))


@@ -146,7 +195,7 @@ static int sbitmap_find_bit_in_index(struct sbitmap *sb, int index,
        return nr;
 }
 
        return nr;
 }
 

-int sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint, bool round_robin)
+static int __sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint)

 {
        unsigned int i, index;
        int nr = -1;
 {
        unsigned int i, index;
        int nr = -1;


@@ -158,14 +207,13 @@ int sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint, bool round_robin)
         * alloc_hint to find the right word index. No point in looping
         * twice in find_next_zero_bit() for that case.
         */
         * alloc_hint to find the right word index. No point in looping
         * twice in find_next_zero_bit() for that case.
         */

-       if (round_robin)
+       if (sb->round_robin)

                alloc_hint = SB_NR_TO_BIT(sb, alloc_hint);
        else
                alloc_hint = 0;
 
        for (i = 0; i < sb->map_nr; i++) {
                alloc_hint = SB_NR_TO_BIT(sb, alloc_hint);
        else
                alloc_hint = 0;
 
        for (i = 0; i < sb->map_nr; i++) {

-               nr = sbitmap_find_bit_in_index(sb, index, alloc_hint,
-                                               round_robin);
+               nr = sbitmap_find_bit_in_index(sb, index, alloc_hint);

                if (nr != -1) {
                        nr += index << sb->shift;
                        break;
                if (nr != -1) {
                        nr += index << sb->shift;
                        break;


@@ -179,10 +227,27 @@ int sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint, bool round_robin)
 
        return nr;
 }
 
        return nr;
 }

+
+int sbitmap_get(struct sbitmap *sb)
+{
+       int nr;
+       unsigned int hint, depth;
+
+       if (WARN_ON_ONCE(unlikely(!sb->alloc_hint)))
+               return -1;
+
+       depth = READ_ONCE(sb->depth);
+       hint = update_alloc_hint_before_get(sb, depth);
+       nr = __sbitmap_get(sb, hint);
+       update_alloc_hint_after_get(sb, depth, hint, nr);
+
+       return nr;
+}

 EXPORT_SYMBOL_GPL(sbitmap_get);
 
 EXPORT_SYMBOL_GPL(sbitmap_get);
 

-int sbitmap_get_shallow(struct sbitmap *sb, unsigned int alloc_hint,
-                       unsigned long shallow_depth)
+static int __sbitmap_get_shallow(struct sbitmap *sb,
+                                unsigned int alloc_hint,
+                                unsigned long shallow_depth)

 {
        unsigned int i, index;
        int nr = -1;
 {
        unsigned int i, index;
        int nr = -1;


@@ -214,6 +279,22 @@ again:
 
        return nr;
 }
 
        return nr;
 }

+
+int sbitmap_get_shallow(struct sbitmap *sb, unsigned long shallow_depth)
+{
+       int nr;
+       unsigned int hint, depth;
+
+       if (WARN_ON_ONCE(unlikely(!sb->alloc_hint)))
+               return -1;
+
+       depth = READ_ONCE(sb->depth);
+       hint = update_alloc_hint_before_get(sb, depth);
+       nr = __sbitmap_get_shallow(sb, hint, shallow_depth);
+       update_alloc_hint_after_get(sb, depth, hint, nr);
+
+       return nr;
+}

 EXPORT_SYMBOL_GPL(sbitmap_get_shallow);
 
 bool sbitmap_any_bit_set(const struct sbitmap *sb)
 EXPORT_SYMBOL_GPL(sbitmap_get_shallow);
 
 bool sbitmap_any_bit_set(const struct sbitmap *sb)


@@ -243,20 +324,21 @@ static unsigned int __sbitmap_weight(const struct sbitmap *sb, bool set)
        return weight;
 }
 
        return weight;
 }
 

-static unsigned int sbitmap_weight(const struct sbitmap *sb)
+static unsigned int sbitmap_cleared(const struct sbitmap *sb)

 {
 {

-       return __sbitmap_weight(sb, true);
+       return __sbitmap_weight(sb, false);

 }
 
 }
 

-static unsigned int sbitmap_cleared(const struct sbitmap *sb)
+unsigned int sbitmap_weight(const struct sbitmap *sb)

 {
 {

-       return __sbitmap_weight(sb, false);
+       return __sbitmap_weight(sb, true) - sbitmap_cleared(sb);

 }
 }

+EXPORT_SYMBOL_GPL(sbitmap_weight);

 
 void sbitmap_show(struct sbitmap *sb, struct seq_file *m)
 {
        seq_printf(m, "depth=%u\n", sb->depth);
 
 void sbitmap_show(struct sbitmap *sb, struct seq_file *m)
 {
        seq_printf(m, "depth=%u\n", sb->depth);

-       seq_printf(m, "busy=%u\n", sbitmap_weight(sb) - sbitmap_cleared(sb));
+       seq_printf(m, "busy=%u\n", sbitmap_weight(sb));

        seq_printf(m, "cleared=%u\n", sbitmap_cleared(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, "cleared=%u\n", sbitmap_cleared(sb));
        seq_printf(m, "bits_per_word=%u\n", 1U << sb->shift);
        seq_printf(m, "map_nr=%u\n", sb->map_nr);


@@ -350,21 +432,11 @@ int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth,
        int ret;
        int i;
 
        int ret;
        int i;
 

-       ret = sbitmap_init_node(&sbq->sb, depth, shift, flags, node);
+       ret = sbitmap_init_node(&sbq->sb, depth, shift, flags, node,
+                               round_robin, true);

        if (ret)
                return ret;
 
        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->min_shallow_depth = UINT_MAX;
        sbq->wake_batch = sbq_calc_wake_batch(sbq, depth);
        atomic_set(&sbq->wake_index, 0);
        sbq->min_shallow_depth = UINT_MAX;
        sbq->wake_batch = sbq_calc_wake_batch(sbq, depth);
        atomic_set(&sbq->wake_index, 0);


@@ -372,7 +444,6 @@ int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth,
 
        sbq->ws = kzalloc_node(SBQ_WAIT_QUEUES * sizeof(*sbq->ws), flags, node);
        if (!sbq->ws) {
 
        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;
        }
                sbitmap_free(&sbq->sb);
                return -ENOMEM;
        }


@@ -382,7 +453,6 @@ int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth,
                atomic_set(&sbq->ws[i].wait_cnt, sbq->wake_batch);
        }
 
                atomic_set(&sbq->ws[i].wait_cnt, sbq->wake_batch);
        }
 

-       sbq->round_robin = round_robin;

        return 0;
 }
 EXPORT_SYMBOL_GPL(sbitmap_queue_init_node);
        return 0;
 }
 EXPORT_SYMBOL_GPL(sbitmap_queue_init_node);


@@ -415,60 +485,16 @@ EXPORT_SYMBOL_GPL(sbitmap_queue_resize);
 
 int __sbitmap_queue_get(struct sbitmap_queue *sbq)
 {
 
 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;
+       return sbitmap_get(&sbq->sb);

 }
 EXPORT_SYMBOL_GPL(__sbitmap_queue_get);
 
 int __sbitmap_queue_get_shallow(struct sbitmap_queue *sbq,
                                unsigned int shallow_depth)
 {
 }
 EXPORT_SYMBOL_GPL(__sbitmap_queue_get);
 
 int __sbitmap_queue_get_shallow(struct sbitmap_queue *sbq,
                                unsigned int shallow_depth)
 {

-       unsigned int hint, depth;
-       int nr;
-

        WARN_ON_ONCE(shallow_depth < sbq->min_shallow_depth);
 
        WARN_ON_ONCE(shallow_depth < sbq->min_shallow_depth);
 

-       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_shallow(&sbq->sb, hint, shallow_depth);
-
-       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;
+       return sbitmap_get_shallow(&sbq->sb, shallow_depth);

 }
 EXPORT_SYMBOL_GPL(__sbitmap_queue_get_shallow);
 
 }
 EXPORT_SYMBOL_GPL(__sbitmap_queue_get_shallow);
 


@@ -576,8 +602,8 @@ void sbitmap_queue_clear(struct sbitmap_queue *sbq, unsigned int nr,
        smp_mb__after_atomic();
        sbitmap_queue_wake_up(sbq);
 
        smp_mb__after_atomic();
        sbitmap_queue_wake_up(sbq);
 

-       if (likely(!sbq->round_robin && nr < sbq->sb.depth))
-               *per_cpu_ptr(sbq->alloc_hint, cpu) = nr;
+       if (likely(!sbq->sb.round_robin && nr < sbq->sb.depth))
+               *per_cpu_ptr(sbq->sb.alloc_hint, cpu) = nr;

 }
 EXPORT_SYMBOL_GPL(sbitmap_queue_clear);
 
 }
 EXPORT_SYMBOL_GPL(sbitmap_queue_clear);
 


@@ -615,7 +641,7 @@ void sbitmap_queue_show(struct sbitmap_queue *sbq, struct seq_file *m)
                if (!first)
                        seq_puts(m, ", ");
                first = false;
                if (!first)
                        seq_puts(m, ", ");
                first = false;

-               seq_printf(m, "%u", *per_cpu_ptr(sbq->alloc_hint, i));
+               seq_printf(m, "%u", *per_cpu_ptr(sbq->sb.alloc_hint, i));

        }
        seq_puts(m, "}\n");
 
        }
        seq_puts(m, "}\n");
 


@@ -633,7 +659,7 @@ void sbitmap_queue_show(struct sbitmap_queue *sbq, struct seq_file *m)
        }
        seq_puts(m, "}\n");
 
        }
        seq_puts(m, "}\n");
 

-       seq_printf(m, "round_robin=%d\n", sbq->round_robin);
+       seq_printf(m, "round_robin=%d\n", sbq->sb.round_robin);

        seq_printf(m, "min_shallow_depth=%u\n", sbq->min_shallow_depth);
 }
 EXPORT_SYMBOL_GPL(sbitmap_queue_show);
        seq_printf(m, "min_shallow_depth=%u\n", sbq->min_shallow_depth);
 }
 EXPORT_SYMBOL_GPL(sbitmap_queue_show);