Back to home page

LXR

 
 

    


0001 /*
0002  * Copyright (C) 2016 Facebook
0003  * Copyright (C) 2013-2014 Jens Axboe
0004  *
0005  * This program is free software; you can redistribute it and/or
0006  * modify it under the terms of the GNU General Public
0007  * License v2 as published by the Free Software Foundation.
0008  *
0009  * This program is distributed in the hope that it will be useful,
0010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
0011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
0012  * General Public License for more details.
0013  *
0014  * You should have received a copy of the GNU General Public License
0015  * along with this program.  If not, see <https://www.gnu.org/licenses/>.
0016  */
0017 
0018 #include <linux/random.h>
0019 #include <linux/sbitmap.h>
0020 
0021 int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift,
0022               gfp_t flags, int node)
0023 {
0024     unsigned int bits_per_word;
0025     unsigned int i;
0026 
0027     if (shift < 0) {
0028         shift = ilog2(BITS_PER_LONG);
0029         /*
0030          * If the bitmap is small, shrink the number of bits per word so
0031          * we spread over a few cachelines, at least. If less than 4
0032          * bits, just forget about it, it's not going to work optimally
0033          * anyway.
0034          */
0035         if (depth >= 4) {
0036             while ((4U << shift) > depth)
0037                 shift--;
0038         }
0039     }
0040     bits_per_word = 1U << shift;
0041     if (bits_per_word > BITS_PER_LONG)
0042         return -EINVAL;
0043 
0044     sb->shift = shift;
0045     sb->depth = depth;
0046     sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word);
0047 
0048     if (depth == 0) {
0049         sb->map = NULL;
0050         return 0;
0051     }
0052 
0053     sb->map = kzalloc_node(sb->map_nr * sizeof(*sb->map), flags, node);
0054     if (!sb->map)
0055         return -ENOMEM;
0056 
0057     for (i = 0; i < sb->map_nr; i++) {
0058         sb->map[i].depth = min(depth, bits_per_word);
0059         depth -= sb->map[i].depth;
0060     }
0061     return 0;
0062 }
0063 EXPORT_SYMBOL_GPL(sbitmap_init_node);
0064 
0065 void sbitmap_resize(struct sbitmap *sb, unsigned int depth)
0066 {
0067     unsigned int bits_per_word = 1U << sb->shift;
0068     unsigned int i;
0069 
0070     sb->depth = depth;
0071     sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word);
0072 
0073     for (i = 0; i < sb->map_nr; i++) {
0074         sb->map[i].depth = min(depth, bits_per_word);
0075         depth -= sb->map[i].depth;
0076     }
0077 }
0078 EXPORT_SYMBOL_GPL(sbitmap_resize);
0079 
0080 static int __sbitmap_get_word(struct sbitmap_word *word, unsigned int hint,
0081                   bool wrap)
0082 {
0083     unsigned int orig_hint = hint;
0084     int nr;
0085 
0086     while (1) {
0087         nr = find_next_zero_bit(&word->word, word->depth, hint);
0088         if (unlikely(nr >= word->depth)) {
0089             /*
0090              * We started with an offset, and we didn't reset the
0091              * offset to 0 in a failure case, so start from 0 to
0092              * exhaust the map.
0093              */
0094             if (orig_hint && hint && wrap) {
0095                 hint = orig_hint = 0;
0096                 continue;
0097             }
0098             return -1;
0099         }
0100 
0101         if (!test_and_set_bit(nr, &word->word))
0102             break;
0103 
0104         hint = nr + 1;
0105         if (hint >= word->depth - 1)
0106             hint = 0;
0107     }
0108 
0109     return nr;
0110 }
0111 
0112 int sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint, bool round_robin)
0113 {
0114     unsigned int i, index;
0115     int nr = -1;
0116 
0117     index = SB_NR_TO_INDEX(sb, alloc_hint);
0118 
0119     for (i = 0; i < sb->map_nr; i++) {
0120         nr = __sbitmap_get_word(&sb->map[index],
0121                     SB_NR_TO_BIT(sb, alloc_hint),
0122                     !round_robin);
0123         if (nr != -1) {
0124             nr += index << sb->shift;
0125             break;
0126         }
0127 
0128         /* Jump to next index. */
0129         index++;
0130         alloc_hint = index << sb->shift;
0131 
0132         if (index >= sb->map_nr) {
0133             index = 0;
0134             alloc_hint = 0;
0135         }
0136     }
0137 
0138     return nr;
0139 }
0140 EXPORT_SYMBOL_GPL(sbitmap_get);
0141 
0142 bool sbitmap_any_bit_set(const struct sbitmap *sb)
0143 {
0144     unsigned int i;
0145 
0146     for (i = 0; i < sb->map_nr; i++) {
0147         if (sb->map[i].word)
0148             return true;
0149     }
0150     return false;
0151 }
0152 EXPORT_SYMBOL_GPL(sbitmap_any_bit_set);
0153 
0154 bool sbitmap_any_bit_clear(const struct sbitmap *sb)
0155 {
0156     unsigned int i;
0157 
0158     for (i = 0; i < sb->map_nr; i++) {
0159         const struct sbitmap_word *word = &sb->map[i];
0160         unsigned long ret;
0161 
0162         ret = find_first_zero_bit(&word->word, word->depth);
0163         if (ret < word->depth)
0164             return true;
0165     }
0166     return false;
0167 }
0168 EXPORT_SYMBOL_GPL(sbitmap_any_bit_clear);
0169 
0170 unsigned int sbitmap_weight(const struct sbitmap *sb)
0171 {
0172     unsigned int i, weight = 0;
0173 
0174     for (i = 0; i < sb->map_nr; i++) {
0175         const struct sbitmap_word *word = &sb->map[i];
0176 
0177         weight += bitmap_weight(&word->word, word->depth);
0178     }
0179     return weight;
0180 }
0181 EXPORT_SYMBOL_GPL(sbitmap_weight);
0182 
0183 static unsigned int sbq_calc_wake_batch(unsigned int depth)
0184 {
0185     unsigned int wake_batch;
0186 
0187     /*
0188      * For each batch, we wake up one queue. We need to make sure that our
0189      * batch size is small enough that the full depth of the bitmap is
0190      * enough to wake up all of the queues.
0191      */
0192     wake_batch = SBQ_WAKE_BATCH;
0193     if (wake_batch > depth / SBQ_WAIT_QUEUES)
0194         wake_batch = max(1U, depth / SBQ_WAIT_QUEUES);
0195 
0196     return wake_batch;
0197 }
0198 
0199 int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth,
0200                 int shift, bool round_robin, gfp_t flags, int node)
0201 {
0202     int ret;
0203     int i;
0204 
0205     ret = sbitmap_init_node(&sbq->sb, depth, shift, flags, node);
0206     if (ret)
0207         return ret;
0208 
0209     sbq->alloc_hint = alloc_percpu_gfp(unsigned int, flags);
0210     if (!sbq->alloc_hint) {
0211         sbitmap_free(&sbq->sb);
0212         return -ENOMEM;
0213     }
0214 
0215     if (depth && !round_robin) {
0216         for_each_possible_cpu(i)
0217             *per_cpu_ptr(sbq->alloc_hint, i) = prandom_u32() % depth;
0218     }
0219 
0220     sbq->wake_batch = sbq_calc_wake_batch(depth);
0221     atomic_set(&sbq->wake_index, 0);
0222 
0223     sbq->ws = kzalloc_node(SBQ_WAIT_QUEUES * sizeof(*sbq->ws), flags, node);
0224     if (!sbq->ws) {
0225         free_percpu(sbq->alloc_hint);
0226         sbitmap_free(&sbq->sb);
0227         return -ENOMEM;
0228     }
0229 
0230     for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
0231         init_waitqueue_head(&sbq->ws[i].wait);
0232         atomic_set(&sbq->ws[i].wait_cnt, sbq->wake_batch);
0233     }
0234 
0235     sbq->round_robin = round_robin;
0236     return 0;
0237 }
0238 EXPORT_SYMBOL_GPL(sbitmap_queue_init_node);
0239 
0240 void sbitmap_queue_resize(struct sbitmap_queue *sbq, unsigned int depth)
0241 {
0242     sbq->wake_batch = sbq_calc_wake_batch(depth);
0243     sbitmap_resize(&sbq->sb, depth);
0244 }
0245 EXPORT_SYMBOL_GPL(sbitmap_queue_resize);
0246 
0247 int __sbitmap_queue_get(struct sbitmap_queue *sbq)
0248 {
0249     unsigned int hint, depth;
0250     int nr;
0251 
0252     hint = this_cpu_read(*sbq->alloc_hint);
0253     depth = READ_ONCE(sbq->sb.depth);
0254     if (unlikely(hint >= depth)) {
0255         hint = depth ? prandom_u32() % depth : 0;
0256         this_cpu_write(*sbq->alloc_hint, hint);
0257     }
0258     nr = sbitmap_get(&sbq->sb, hint, sbq->round_robin);
0259 
0260     if (nr == -1) {
0261         /* If the map is full, a hint won't do us much good. */
0262         this_cpu_write(*sbq->alloc_hint, 0);
0263     } else if (nr == hint || unlikely(sbq->round_robin)) {
0264         /* Only update the hint if we used it. */
0265         hint = nr + 1;
0266         if (hint >= depth - 1)
0267             hint = 0;
0268         this_cpu_write(*sbq->alloc_hint, hint);
0269     }
0270 
0271     return nr;
0272 }
0273 EXPORT_SYMBOL_GPL(__sbitmap_queue_get);
0274 
0275 static struct sbq_wait_state *sbq_wake_ptr(struct sbitmap_queue *sbq)
0276 {
0277     int i, wake_index;
0278 
0279     wake_index = atomic_read(&sbq->wake_index);
0280     for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
0281         struct sbq_wait_state *ws = &sbq->ws[wake_index];
0282 
0283         if (waitqueue_active(&ws->wait)) {
0284             int o = atomic_read(&sbq->wake_index);
0285 
0286             if (wake_index != o)
0287                 atomic_cmpxchg(&sbq->wake_index, o, wake_index);
0288             return ws;
0289         }
0290 
0291         wake_index = sbq_index_inc(wake_index);
0292     }
0293 
0294     return NULL;
0295 }
0296 
0297 static void sbq_wake_up(struct sbitmap_queue *sbq)
0298 {
0299     struct sbq_wait_state *ws;
0300     int wait_cnt;
0301 
0302     /* Ensure that the wait list checks occur after clear_bit(). */
0303     smp_mb();
0304 
0305     ws = sbq_wake_ptr(sbq);
0306     if (!ws)
0307         return;
0308 
0309     wait_cnt = atomic_dec_return(&ws->wait_cnt);
0310     if (unlikely(wait_cnt < 0))
0311         wait_cnt = atomic_inc_return(&ws->wait_cnt);
0312     if (wait_cnt == 0) {
0313         atomic_add(sbq->wake_batch, &ws->wait_cnt);
0314         sbq_index_atomic_inc(&sbq->wake_index);
0315         wake_up(&ws->wait);
0316     }
0317 }
0318 
0319 void sbitmap_queue_clear(struct sbitmap_queue *sbq, unsigned int nr,
0320              unsigned int cpu)
0321 {
0322     sbitmap_clear_bit(&sbq->sb, nr);
0323     sbq_wake_up(sbq);
0324     if (likely(!sbq->round_robin && nr < sbq->sb.depth))
0325         *per_cpu_ptr(sbq->alloc_hint, cpu) = nr;
0326 }
0327 EXPORT_SYMBOL_GPL(sbitmap_queue_clear);
0328 
0329 void sbitmap_queue_wake_all(struct sbitmap_queue *sbq)
0330 {
0331     int i, wake_index;
0332 
0333     /*
0334      * Make sure all changes prior to this are visible from other CPUs.
0335      */
0336     smp_mb();
0337     wake_index = atomic_read(&sbq->wake_index);
0338     for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
0339         struct sbq_wait_state *ws = &sbq->ws[wake_index];
0340 
0341         if (waitqueue_active(&ws->wait))
0342             wake_up(&ws->wait);
0343 
0344         wake_index = sbq_index_inc(wake_index);
0345     }
0346 }
0347 EXPORT_SYMBOL_GPL(sbitmap_queue_wake_all);