Merge tag 'pstore-v5.0-rc4' of git://git.kernel.org/pub/scm/linux/kernel/git/kees...
[linux-2.6-microblaze.git] / lib / sbitmap.c
1 /*
2  * Copyright (C) 2016 Facebook
3  * Copyright (C) 2013-2014 Jens Axboe
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public
7  * License v2 as published by the Free Software Foundation.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  * General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program.  If not, see <https://www.gnu.org/licenses/>.
16  */
17
18 #include <linux/sched.h>
19 #include <linux/random.h>
20 #include <linux/sbitmap.h>
21 #include <linux/seq_file.h>
22
23 /*
24  * See if we have deferred clears that we can batch move
25  */
26 static inline bool sbitmap_deferred_clear(struct sbitmap *sb, int index)
27 {
28         unsigned long mask, val;
29         bool ret = false;
30         unsigned long flags;
31
32         spin_lock_irqsave(&sb->map[index].swap_lock, flags);
33
34         if (!sb->map[index].cleared)
35                 goto out_unlock;
36
37         /*
38          * First get a stable cleared mask, setting the old mask to 0.
39          */
40         do {
41                 mask = sb->map[index].cleared;
42         } while (cmpxchg(&sb->map[index].cleared, mask, 0) != mask);
43
44         /*
45          * Now clear the masked bits in our free word
46          */
47         do {
48                 val = sb->map[index].word;
49         } while (cmpxchg(&sb->map[index].word, val, val & ~mask) != val);
50
51         ret = true;
52 out_unlock:
53         spin_unlock_irqrestore(&sb->map[index].swap_lock, flags);
54         return ret;
55 }
56
57 int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift,
58                       gfp_t flags, int node)
59 {
60         unsigned int bits_per_word;
61         unsigned int i;
62
63         if (shift < 0) {
64                 shift = ilog2(BITS_PER_LONG);
65                 /*
66                  * If the bitmap is small, shrink the number of bits per word so
67                  * we spread over a few cachelines, at least. If less than 4
68                  * bits, just forget about it, it's not going to work optimally
69                  * anyway.
70                  */
71                 if (depth >= 4) {
72                         while ((4U << shift) > depth)
73                                 shift--;
74                 }
75         }
76         bits_per_word = 1U << shift;
77         if (bits_per_word > BITS_PER_LONG)
78                 return -EINVAL;
79
80         sb->shift = shift;
81         sb->depth = depth;
82         sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word);
83
84         if (depth == 0) {
85                 sb->map = NULL;
86                 return 0;
87         }
88
89         sb->map = kcalloc_node(sb->map_nr, sizeof(*sb->map), flags, node);
90         if (!sb->map)
91                 return -ENOMEM;
92
93         for (i = 0; i < sb->map_nr; i++) {
94                 sb->map[i].depth = min(depth, bits_per_word);
95                 depth -= sb->map[i].depth;
96                 spin_lock_init(&sb->map[i].swap_lock);
97         }
98         return 0;
99 }
100 EXPORT_SYMBOL_GPL(sbitmap_init_node);
101
102 void sbitmap_resize(struct sbitmap *sb, unsigned int depth)
103 {
104         unsigned int bits_per_word = 1U << sb->shift;
105         unsigned int i;
106
107         for (i = 0; i < sb->map_nr; i++)
108                 sbitmap_deferred_clear(sb, i);
109
110         sb->depth = depth;
111         sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word);
112
113         for (i = 0; i < sb->map_nr; i++) {
114                 sb->map[i].depth = min(depth, bits_per_word);
115                 depth -= sb->map[i].depth;
116         }
117 }
118 EXPORT_SYMBOL_GPL(sbitmap_resize);
119
120 static int __sbitmap_get_word(unsigned long *word, unsigned long depth,
121                               unsigned int hint, bool wrap)
122 {
123         unsigned int orig_hint = hint;
124         int nr;
125
126         while (1) {
127                 nr = find_next_zero_bit(word, depth, hint);
128                 if (unlikely(nr >= depth)) {
129                         /*
130                          * We started with an offset, and we didn't reset the
131                          * offset to 0 in a failure case, so start from 0 to
132                          * exhaust the map.
133                          */
134                         if (orig_hint && hint && wrap) {
135                                 hint = orig_hint = 0;
136                                 continue;
137                         }
138                         return -1;
139                 }
140
141                 if (!test_and_set_bit_lock(nr, word))
142                         break;
143
144                 hint = nr + 1;
145                 if (hint >= depth - 1)
146                         hint = 0;
147         }
148
149         return nr;
150 }
151
152 static int sbitmap_find_bit_in_index(struct sbitmap *sb, int index,
153                                      unsigned int alloc_hint, bool round_robin)
154 {
155         int nr;
156
157         do {
158                 nr = __sbitmap_get_word(&sb->map[index].word,
159                                         sb->map[index].depth, alloc_hint,
160                                         !round_robin);
161                 if (nr != -1)
162                         break;
163                 if (!sbitmap_deferred_clear(sb, index))
164                         break;
165         } while (1);
166
167         return nr;
168 }
169
170 int sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint, bool round_robin)
171 {
172         unsigned int i, index;
173         int nr = -1;
174
175         index = SB_NR_TO_INDEX(sb, alloc_hint);
176
177         /*
178          * Unless we're doing round robin tag allocation, just use the
179          * alloc_hint to find the right word index. No point in looping
180          * twice in find_next_zero_bit() for that case.
181          */
182         if (round_robin)
183                 alloc_hint = SB_NR_TO_BIT(sb, alloc_hint);
184         else
185                 alloc_hint = 0;
186
187         for (i = 0; i < sb->map_nr; i++) {
188                 nr = sbitmap_find_bit_in_index(sb, index, alloc_hint,
189                                                 round_robin);
190                 if (nr != -1) {
191                         nr += index << sb->shift;
192                         break;
193                 }
194
195                 /* Jump to next index. */
196                 alloc_hint = 0;
197                 if (++index >= sb->map_nr)
198                         index = 0;
199         }
200
201         return nr;
202 }
203 EXPORT_SYMBOL_GPL(sbitmap_get);
204
205 int sbitmap_get_shallow(struct sbitmap *sb, unsigned int alloc_hint,
206                         unsigned long shallow_depth)
207 {
208         unsigned int i, index;
209         int nr = -1;
210
211         index = SB_NR_TO_INDEX(sb, alloc_hint);
212
213         for (i = 0; i < sb->map_nr; i++) {
214 again:
215                 nr = __sbitmap_get_word(&sb->map[index].word,
216                                         min(sb->map[index].depth, shallow_depth),
217                                         SB_NR_TO_BIT(sb, alloc_hint), true);
218                 if (nr != -1) {
219                         nr += index << sb->shift;
220                         break;
221                 }
222
223                 if (sbitmap_deferred_clear(sb, index))
224                         goto again;
225
226                 /* Jump to next index. */
227                 index++;
228                 alloc_hint = index << sb->shift;
229
230                 if (index >= sb->map_nr) {
231                         index = 0;
232                         alloc_hint = 0;
233                 }
234         }
235
236         return nr;
237 }
238 EXPORT_SYMBOL_GPL(sbitmap_get_shallow);
239
240 bool sbitmap_any_bit_set(const struct sbitmap *sb)
241 {
242         unsigned int i;
243
244         for (i = 0; i < sb->map_nr; i++) {
245                 if (sb->map[i].word & ~sb->map[i].cleared)
246                         return true;
247         }
248         return false;
249 }
250 EXPORT_SYMBOL_GPL(sbitmap_any_bit_set);
251
252 bool sbitmap_any_bit_clear(const struct sbitmap *sb)
253 {
254         unsigned int i;
255
256         for (i = 0; i < sb->map_nr; i++) {
257                 const struct sbitmap_word *word = &sb->map[i];
258                 unsigned long mask = word->word & ~word->cleared;
259                 unsigned long ret;
260
261                 ret = find_first_zero_bit(&mask, word->depth);
262                 if (ret < word->depth)
263                         return true;
264         }
265         return false;
266 }
267 EXPORT_SYMBOL_GPL(sbitmap_any_bit_clear);
268
269 static unsigned int __sbitmap_weight(const struct sbitmap *sb, bool set)
270 {
271         unsigned int i, weight = 0;
272
273         for (i = 0; i < sb->map_nr; i++) {
274                 const struct sbitmap_word *word = &sb->map[i];
275
276                 if (set)
277                         weight += bitmap_weight(&word->word, word->depth);
278                 else
279                         weight += bitmap_weight(&word->cleared, word->depth);
280         }
281         return weight;
282 }
283
284 static unsigned int sbitmap_weight(const struct sbitmap *sb)
285 {
286         return __sbitmap_weight(sb, true);
287 }
288
289 static unsigned int sbitmap_cleared(const struct sbitmap *sb)
290 {
291         return __sbitmap_weight(sb, false);
292 }
293
294 void sbitmap_show(struct sbitmap *sb, struct seq_file *m)
295 {
296         seq_printf(m, "depth=%u\n", sb->depth);
297         seq_printf(m, "busy=%u\n", sbitmap_weight(sb) - sbitmap_cleared(sb));
298         seq_printf(m, "cleared=%u\n", sbitmap_cleared(sb));
299         seq_printf(m, "bits_per_word=%u\n", 1U << sb->shift);
300         seq_printf(m, "map_nr=%u\n", sb->map_nr);
301 }
302 EXPORT_SYMBOL_GPL(sbitmap_show);
303
304 static inline void emit_byte(struct seq_file *m, unsigned int offset, u8 byte)
305 {
306         if ((offset & 0xf) == 0) {
307                 if (offset != 0)
308                         seq_putc(m, '\n');
309                 seq_printf(m, "%08x:", offset);
310         }
311         if ((offset & 0x1) == 0)
312                 seq_putc(m, ' ');
313         seq_printf(m, "%02x", byte);
314 }
315
316 void sbitmap_bitmap_show(struct sbitmap *sb, struct seq_file *m)
317 {
318         u8 byte = 0;
319         unsigned int byte_bits = 0;
320         unsigned int offset = 0;
321         int i;
322
323         for (i = 0; i < sb->map_nr; i++) {
324                 unsigned long word = READ_ONCE(sb->map[i].word);
325                 unsigned int word_bits = READ_ONCE(sb->map[i].depth);
326
327                 while (word_bits > 0) {
328                         unsigned int bits = min(8 - byte_bits, word_bits);
329
330                         byte |= (word & (BIT(bits) - 1)) << byte_bits;
331                         byte_bits += bits;
332                         if (byte_bits == 8) {
333                                 emit_byte(m, offset, byte);
334                                 byte = 0;
335                                 byte_bits = 0;
336                                 offset++;
337                         }
338                         word >>= bits;
339                         word_bits -= bits;
340                 }
341         }
342         if (byte_bits) {
343                 emit_byte(m, offset, byte);
344                 offset++;
345         }
346         if (offset)
347                 seq_putc(m, '\n');
348 }
349 EXPORT_SYMBOL_GPL(sbitmap_bitmap_show);
350
351 static unsigned int sbq_calc_wake_batch(struct sbitmap_queue *sbq,
352                                         unsigned int depth)
353 {
354         unsigned int wake_batch;
355         unsigned int shallow_depth;
356
357         /*
358          * For each batch, we wake up one queue. We need to make sure that our
359          * batch size is small enough that the full depth of the bitmap,
360          * potentially limited by a shallow depth, is enough to wake up all of
361          * the queues.
362          *
363          * Each full word of the bitmap has bits_per_word bits, and there might
364          * be a partial word. There are depth / bits_per_word full words and
365          * depth % bits_per_word bits left over. In bitwise arithmetic:
366          *
367          * bits_per_word = 1 << shift
368          * depth / bits_per_word = depth >> shift
369          * depth % bits_per_word = depth & ((1 << shift) - 1)
370          *
371          * Each word can be limited to sbq->min_shallow_depth bits.
372          */
373         shallow_depth = min(1U << sbq->sb.shift, sbq->min_shallow_depth);
374         depth = ((depth >> sbq->sb.shift) * shallow_depth +
375                  min(depth & ((1U << sbq->sb.shift) - 1), shallow_depth));
376         wake_batch = clamp_t(unsigned int, depth / SBQ_WAIT_QUEUES, 1,
377                              SBQ_WAKE_BATCH);
378
379         return wake_batch;
380 }
381
382 int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth,
383                             int shift, bool round_robin, gfp_t flags, int node)
384 {
385         int ret;
386         int i;
387
388         ret = sbitmap_init_node(&sbq->sb, depth, shift, flags, node);
389         if (ret)
390                 return ret;
391
392         sbq->alloc_hint = alloc_percpu_gfp(unsigned int, flags);
393         if (!sbq->alloc_hint) {
394                 sbitmap_free(&sbq->sb);
395                 return -ENOMEM;
396         }
397
398         if (depth && !round_robin) {
399                 for_each_possible_cpu(i)
400                         *per_cpu_ptr(sbq->alloc_hint, i) = prandom_u32() % depth;
401         }
402
403         sbq->min_shallow_depth = UINT_MAX;
404         sbq->wake_batch = sbq_calc_wake_batch(sbq, depth);
405         atomic_set(&sbq->wake_index, 0);
406         atomic_set(&sbq->ws_active, 0);
407
408         sbq->ws = kzalloc_node(SBQ_WAIT_QUEUES * sizeof(*sbq->ws), flags, node);
409         if (!sbq->ws) {
410                 free_percpu(sbq->alloc_hint);
411                 sbitmap_free(&sbq->sb);
412                 return -ENOMEM;
413         }
414
415         for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
416                 init_waitqueue_head(&sbq->ws[i].wait);
417                 atomic_set(&sbq->ws[i].wait_cnt, sbq->wake_batch);
418         }
419
420         sbq->round_robin = round_robin;
421         return 0;
422 }
423 EXPORT_SYMBOL_GPL(sbitmap_queue_init_node);
424
425 static void sbitmap_queue_update_wake_batch(struct sbitmap_queue *sbq,
426                                             unsigned int depth)
427 {
428         unsigned int wake_batch = sbq_calc_wake_batch(sbq, depth);
429         int i;
430
431         if (sbq->wake_batch != wake_batch) {
432                 WRITE_ONCE(sbq->wake_batch, wake_batch);
433                 /*
434                  * Pairs with the memory barrier in sbitmap_queue_wake_up()
435                  * to ensure that the batch size is updated before the wait
436                  * counts.
437                  */
438                 smp_mb__before_atomic();
439                 for (i = 0; i < SBQ_WAIT_QUEUES; i++)
440                         atomic_set(&sbq->ws[i].wait_cnt, 1);
441         }
442 }
443
444 void sbitmap_queue_resize(struct sbitmap_queue *sbq, unsigned int depth)
445 {
446         sbitmap_queue_update_wake_batch(sbq, depth);
447         sbitmap_resize(&sbq->sb, depth);
448 }
449 EXPORT_SYMBOL_GPL(sbitmap_queue_resize);
450
451 int __sbitmap_queue_get(struct sbitmap_queue *sbq)
452 {
453         unsigned int hint, depth;
454         int nr;
455
456         hint = this_cpu_read(*sbq->alloc_hint);
457         depth = READ_ONCE(sbq->sb.depth);
458         if (unlikely(hint >= depth)) {
459                 hint = depth ? prandom_u32() % depth : 0;
460                 this_cpu_write(*sbq->alloc_hint, hint);
461         }
462         nr = sbitmap_get(&sbq->sb, hint, sbq->round_robin);
463
464         if (nr == -1) {
465                 /* If the map is full, a hint won't do us much good. */
466                 this_cpu_write(*sbq->alloc_hint, 0);
467         } else if (nr == hint || unlikely(sbq->round_robin)) {
468                 /* Only update the hint if we used it. */
469                 hint = nr + 1;
470                 if (hint >= depth - 1)
471                         hint = 0;
472                 this_cpu_write(*sbq->alloc_hint, hint);
473         }
474
475         return nr;
476 }
477 EXPORT_SYMBOL_GPL(__sbitmap_queue_get);
478
479 int __sbitmap_queue_get_shallow(struct sbitmap_queue *sbq,
480                                 unsigned int shallow_depth)
481 {
482         unsigned int hint, depth;
483         int nr;
484
485         WARN_ON_ONCE(shallow_depth < sbq->min_shallow_depth);
486
487         hint = this_cpu_read(*sbq->alloc_hint);
488         depth = READ_ONCE(sbq->sb.depth);
489         if (unlikely(hint >= depth)) {
490                 hint = depth ? prandom_u32() % depth : 0;
491                 this_cpu_write(*sbq->alloc_hint, hint);
492         }
493         nr = sbitmap_get_shallow(&sbq->sb, hint, shallow_depth);
494
495         if (nr == -1) {
496                 /* If the map is full, a hint won't do us much good. */
497                 this_cpu_write(*sbq->alloc_hint, 0);
498         } else if (nr == hint || unlikely(sbq->round_robin)) {
499                 /* Only update the hint if we used it. */
500                 hint = nr + 1;
501                 if (hint >= depth - 1)
502                         hint = 0;
503                 this_cpu_write(*sbq->alloc_hint, hint);
504         }
505
506         return nr;
507 }
508 EXPORT_SYMBOL_GPL(__sbitmap_queue_get_shallow);
509
510 void sbitmap_queue_min_shallow_depth(struct sbitmap_queue *sbq,
511                                      unsigned int min_shallow_depth)
512 {
513         sbq->min_shallow_depth = min_shallow_depth;
514         sbitmap_queue_update_wake_batch(sbq, sbq->sb.depth);
515 }
516 EXPORT_SYMBOL_GPL(sbitmap_queue_min_shallow_depth);
517
518 static struct sbq_wait_state *sbq_wake_ptr(struct sbitmap_queue *sbq)
519 {
520         int i, wake_index;
521
522         if (!atomic_read(&sbq->ws_active))
523                 return NULL;
524
525         wake_index = atomic_read(&sbq->wake_index);
526         for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
527                 struct sbq_wait_state *ws = &sbq->ws[wake_index];
528
529                 if (waitqueue_active(&ws->wait)) {
530                         int o = atomic_read(&sbq->wake_index);
531
532                         if (wake_index != o)
533                                 atomic_cmpxchg(&sbq->wake_index, o, wake_index);
534                         return ws;
535                 }
536
537                 wake_index = sbq_index_inc(wake_index);
538         }
539
540         return NULL;
541 }
542
543 static bool __sbq_wake_up(struct sbitmap_queue *sbq)
544 {
545         struct sbq_wait_state *ws;
546         unsigned int wake_batch;
547         int wait_cnt;
548
549         ws = sbq_wake_ptr(sbq);
550         if (!ws)
551                 return false;
552
553         wait_cnt = atomic_dec_return(&ws->wait_cnt);
554         if (wait_cnt <= 0) {
555                 int ret;
556
557                 wake_batch = READ_ONCE(sbq->wake_batch);
558
559                 /*
560                  * Pairs with the memory barrier in sbitmap_queue_resize() to
561                  * ensure that we see the batch size update before the wait
562                  * count is reset.
563                  */
564                 smp_mb__before_atomic();
565
566                 /*
567                  * For concurrent callers of this, the one that failed the
568                  * atomic_cmpxhcg() race should call this function again
569                  * to wakeup a new batch on a different 'ws'.
570                  */
571                 ret = atomic_cmpxchg(&ws->wait_cnt, wait_cnt, wake_batch);
572                 if (ret == wait_cnt) {
573                         sbq_index_atomic_inc(&sbq->wake_index);
574                         wake_up_nr(&ws->wait, wake_batch);
575                         return false;
576                 }
577
578                 return true;
579         }
580
581         return false;
582 }
583
584 void sbitmap_queue_wake_up(struct sbitmap_queue *sbq)
585 {
586         while (__sbq_wake_up(sbq))
587                 ;
588 }
589 EXPORT_SYMBOL_GPL(sbitmap_queue_wake_up);
590
591 void sbitmap_queue_clear(struct sbitmap_queue *sbq, unsigned int nr,
592                          unsigned int cpu)
593 {
594         sbitmap_deferred_clear_bit(&sbq->sb, nr);
595
596         /*
597          * Pairs with the memory barrier in set_current_state() to ensure the
598          * proper ordering of clear_bit_unlock()/waitqueue_active() in the waker
599          * and test_and_set_bit_lock()/prepare_to_wait()/finish_wait() in the
600          * waiter. See the comment on waitqueue_active().
601          */
602         smp_mb__after_atomic();
603         sbitmap_queue_wake_up(sbq);
604
605         if (likely(!sbq->round_robin && nr < sbq->sb.depth))
606                 *per_cpu_ptr(sbq->alloc_hint, cpu) = nr;
607 }
608 EXPORT_SYMBOL_GPL(sbitmap_queue_clear);
609
610 void sbitmap_queue_wake_all(struct sbitmap_queue *sbq)
611 {
612         int i, wake_index;
613
614         /*
615          * Pairs with the memory barrier in set_current_state() like in
616          * sbitmap_queue_wake_up().
617          */
618         smp_mb();
619         wake_index = atomic_read(&sbq->wake_index);
620         for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
621                 struct sbq_wait_state *ws = &sbq->ws[wake_index];
622
623                 if (waitqueue_active(&ws->wait))
624                         wake_up(&ws->wait);
625
626                 wake_index = sbq_index_inc(wake_index);
627         }
628 }
629 EXPORT_SYMBOL_GPL(sbitmap_queue_wake_all);
630
631 void sbitmap_queue_show(struct sbitmap_queue *sbq, struct seq_file *m)
632 {
633         bool first;
634         int i;
635
636         sbitmap_show(&sbq->sb, m);
637
638         seq_puts(m, "alloc_hint={");
639         first = true;
640         for_each_possible_cpu(i) {
641                 if (!first)
642                         seq_puts(m, ", ");
643                 first = false;
644                 seq_printf(m, "%u", *per_cpu_ptr(sbq->alloc_hint, i));
645         }
646         seq_puts(m, "}\n");
647
648         seq_printf(m, "wake_batch=%u\n", sbq->wake_batch);
649         seq_printf(m, "wake_index=%d\n", atomic_read(&sbq->wake_index));
650         seq_printf(m, "ws_active=%d\n", atomic_read(&sbq->ws_active));
651
652         seq_puts(m, "ws={\n");
653         for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
654                 struct sbq_wait_state *ws = &sbq->ws[i];
655
656                 seq_printf(m, "\t{.wait_cnt=%d, .wait=%s},\n",
657                            atomic_read(&ws->wait_cnt),
658                            waitqueue_active(&ws->wait) ? "active" : "inactive");
659         }
660         seq_puts(m, "}\n");
661
662         seq_printf(m, "round_robin=%d\n", sbq->round_robin);
663         seq_printf(m, "min_shallow_depth=%u\n", sbq->min_shallow_depth);
664 }
665 EXPORT_SYMBOL_GPL(sbitmap_queue_show);
666
667 void sbitmap_add_wait_queue(struct sbitmap_queue *sbq,
668                             struct sbq_wait_state *ws,
669                             struct sbq_wait *sbq_wait)
670 {
671         if (!sbq_wait->sbq) {
672                 sbq_wait->sbq = sbq;
673                 atomic_inc(&sbq->ws_active);
674         }
675         add_wait_queue(&ws->wait, &sbq_wait->wait);
676 }
677 EXPORT_SYMBOL_GPL(sbitmap_add_wait_queue);
678
679 void sbitmap_del_wait_queue(struct sbq_wait *sbq_wait)
680 {
681         list_del_init(&sbq_wait->wait.entry);
682         if (sbq_wait->sbq) {
683                 atomic_dec(&sbq_wait->sbq->ws_active);
684                 sbq_wait->sbq = NULL;
685         }
686 }
687 EXPORT_SYMBOL_GPL(sbitmap_del_wait_queue);
688
689 void sbitmap_prepare_to_wait(struct sbitmap_queue *sbq,
690                              struct sbq_wait_state *ws,
691                              struct sbq_wait *sbq_wait, int state)
692 {
693         if (!sbq_wait->sbq) {
694                 atomic_inc(&sbq->ws_active);
695                 sbq_wait->sbq = sbq;
696         }
697         prepare_to_wait_exclusive(&ws->wait, &sbq_wait->wait, state);
698 }
699 EXPORT_SYMBOL_GPL(sbitmap_prepare_to_wait);
700
701 void sbitmap_finish_wait(struct sbitmap_queue *sbq, struct sbq_wait_state *ws,
702                          struct sbq_wait *sbq_wait)
703 {
704         finish_wait(&ws->wait, &sbq_wait->wait);
705         if (sbq_wait->sbq) {
706                 atomic_dec(&sbq->ws_active);
707                 sbq_wait->sbq = NULL;
708         }
709 }
710 EXPORT_SYMBOL_GPL(sbitmap_finish_wait);