]>
git.proxmox.com Git - mirror_ubuntu-bionic-kernel.git/blob - lib/sbitmap.c
2 * Copyright (C) 2016 Facebook
3 * Copyright (C) 2013-2014 Jens Axboe
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.
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.
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/>.
18 #include <linux/random.h>
19 #include <linux/sbitmap.h>
20 #include <linux/seq_file.h>
22 int sbitmap_init_node(struct sbitmap
*sb
, unsigned int depth
, int shift
,
23 gfp_t flags
, int node
)
25 unsigned int bits_per_word
;
29 shift
= ilog2(BITS_PER_LONG
);
31 * If the bitmap is small, shrink the number of bits per word so
32 * we spread over a few cachelines, at least. If less than 4
33 * bits, just forget about it, it's not going to work optimally
37 while ((4U << shift
) > depth
)
41 bits_per_word
= 1U << shift
;
42 if (bits_per_word
> BITS_PER_LONG
)
47 sb
->map_nr
= DIV_ROUND_UP(sb
->depth
, bits_per_word
);
54 sb
->map
= kzalloc_node(sb
->map_nr
* sizeof(*sb
->map
), flags
, node
);
58 for (i
= 0; i
< sb
->map_nr
; i
++) {
59 sb
->map
[i
].depth
= min(depth
, bits_per_word
);
60 depth
-= sb
->map
[i
].depth
;
64 EXPORT_SYMBOL_GPL(sbitmap_init_node
);
66 void sbitmap_resize(struct sbitmap
*sb
, unsigned int depth
)
68 unsigned int bits_per_word
= 1U << sb
->shift
;
72 sb
->map_nr
= DIV_ROUND_UP(sb
->depth
, bits_per_word
);
74 for (i
= 0; i
< sb
->map_nr
; i
++) {
75 sb
->map
[i
].depth
= min(depth
, bits_per_word
);
76 depth
-= sb
->map
[i
].depth
;
79 EXPORT_SYMBOL_GPL(sbitmap_resize
);
81 static int __sbitmap_get_word(struct sbitmap_word
*word
, unsigned int hint
,
84 unsigned int orig_hint
= hint
;
88 nr
= find_next_zero_bit(&word
->word
, word
->depth
, hint
);
89 if (unlikely(nr
>= word
->depth
)) {
91 * We started with an offset, and we didn't reset the
92 * offset to 0 in a failure case, so start from 0 to
95 if (orig_hint
&& hint
&& wrap
) {
102 if (!test_and_set_bit(nr
, &word
->word
))
106 if (hint
>= word
->depth
- 1)
113 int sbitmap_get(struct sbitmap
*sb
, unsigned int alloc_hint
, bool round_robin
)
115 unsigned int i
, index
;
118 index
= SB_NR_TO_INDEX(sb
, alloc_hint
);
120 for (i
= 0; i
< sb
->map_nr
; i
++) {
121 nr
= __sbitmap_get_word(&sb
->map
[index
],
122 SB_NR_TO_BIT(sb
, alloc_hint
),
125 nr
+= index
<< sb
->shift
;
129 /* Jump to next index. */
131 alloc_hint
= index
<< sb
->shift
;
133 if (index
>= sb
->map_nr
) {
141 EXPORT_SYMBOL_GPL(sbitmap_get
);
143 bool sbitmap_any_bit_set(const struct sbitmap
*sb
)
147 for (i
= 0; i
< sb
->map_nr
; i
++) {
153 EXPORT_SYMBOL_GPL(sbitmap_any_bit_set
);
155 bool sbitmap_any_bit_clear(const struct sbitmap
*sb
)
159 for (i
= 0; i
< sb
->map_nr
; i
++) {
160 const struct sbitmap_word
*word
= &sb
->map
[i
];
163 ret
= find_first_zero_bit(&word
->word
, word
->depth
);
164 if (ret
< word
->depth
)
169 EXPORT_SYMBOL_GPL(sbitmap_any_bit_clear
);
171 unsigned int sbitmap_weight(const struct sbitmap
*sb
)
173 unsigned int i
, weight
= 0;
175 for (i
= 0; i
< sb
->map_nr
; i
++) {
176 const struct sbitmap_word
*word
= &sb
->map
[i
];
178 weight
+= bitmap_weight(&word
->word
, word
->depth
);
182 EXPORT_SYMBOL_GPL(sbitmap_weight
);
184 void sbitmap_show(struct sbitmap
*sb
, struct seq_file
*m
)
186 seq_printf(m
, "depth=%u\n", sb
->depth
);
187 seq_printf(m
, "busy=%u\n", sbitmap_weight(sb
));
188 seq_printf(m
, "bits_per_word=%u\n", 1U << sb
->shift
);
189 seq_printf(m
, "map_nr=%u\n", sb
->map_nr
);
191 EXPORT_SYMBOL_GPL(sbitmap_show
);
193 static inline void emit_byte(struct seq_file
*m
, unsigned int offset
, u8 byte
)
195 if ((offset
& 0xf) == 0) {
198 seq_printf(m
, "%08x:", offset
);
200 if ((offset
& 0x1) == 0)
202 seq_printf(m
, "%02x", byte
);
205 void sbitmap_bitmap_show(struct sbitmap
*sb
, struct seq_file
*m
)
208 unsigned int byte_bits
= 0;
209 unsigned int offset
= 0;
212 for (i
= 0; i
< sb
->map_nr
; i
++) {
213 unsigned long word
= READ_ONCE(sb
->map
[i
].word
);
214 unsigned int word_bits
= READ_ONCE(sb
->map
[i
].depth
);
216 while (word_bits
> 0) {
217 unsigned int bits
= min(8 - byte_bits
, word_bits
);
219 byte
|= (word
& (BIT(bits
) - 1)) << byte_bits
;
221 if (byte_bits
== 8) {
222 emit_byte(m
, offset
, byte
);
232 emit_byte(m
, offset
, byte
);
238 EXPORT_SYMBOL_GPL(sbitmap_bitmap_show
);
240 static unsigned int sbq_calc_wake_batch(unsigned int depth
)
242 unsigned int wake_batch
;
245 * For each batch, we wake up one queue. We need to make sure that our
246 * batch size is small enough that the full depth of the bitmap is
247 * enough to wake up all of the queues.
249 wake_batch
= SBQ_WAKE_BATCH
;
250 if (wake_batch
> depth
/ SBQ_WAIT_QUEUES
)
251 wake_batch
= max(1U, depth
/ SBQ_WAIT_QUEUES
);
256 int sbitmap_queue_init_node(struct sbitmap_queue
*sbq
, unsigned int depth
,
257 int shift
, bool round_robin
, gfp_t flags
, int node
)
262 ret
= sbitmap_init_node(&sbq
->sb
, depth
, shift
, flags
, node
);
266 sbq
->alloc_hint
= alloc_percpu_gfp(unsigned int, flags
);
267 if (!sbq
->alloc_hint
) {
268 sbitmap_free(&sbq
->sb
);
272 if (depth
&& !round_robin
) {
273 for_each_possible_cpu(i
)
274 *per_cpu_ptr(sbq
->alloc_hint
, i
) = prandom_u32() % depth
;
277 sbq
->wake_batch
= sbq_calc_wake_batch(depth
);
278 atomic_set(&sbq
->wake_index
, 0);
280 sbq
->ws
= kzalloc_node(SBQ_WAIT_QUEUES
* sizeof(*sbq
->ws
), flags
, node
);
282 free_percpu(sbq
->alloc_hint
);
283 sbitmap_free(&sbq
->sb
);
287 for (i
= 0; i
< SBQ_WAIT_QUEUES
; i
++) {
288 init_waitqueue_head(&sbq
->ws
[i
].wait
);
289 atomic_set(&sbq
->ws
[i
].wait_cnt
, sbq
->wake_batch
);
292 sbq
->round_robin
= round_robin
;
295 EXPORT_SYMBOL_GPL(sbitmap_queue_init_node
);
297 void sbitmap_queue_resize(struct sbitmap_queue
*sbq
, unsigned int depth
)
299 unsigned int wake_batch
= sbq_calc_wake_batch(depth
);
302 if (sbq
->wake_batch
!= wake_batch
) {
303 WRITE_ONCE(sbq
->wake_batch
, wake_batch
);
305 * Pairs with the memory barrier in sbq_wake_up() to ensure that
306 * the batch size is updated before the wait counts.
308 smp_mb__before_atomic();
309 for (i
= 0; i
< SBQ_WAIT_QUEUES
; i
++)
310 atomic_set(&sbq
->ws
[i
].wait_cnt
, 1);
312 sbitmap_resize(&sbq
->sb
, depth
);
314 EXPORT_SYMBOL_GPL(sbitmap_queue_resize
);
316 int __sbitmap_queue_get(struct sbitmap_queue
*sbq
)
318 unsigned int hint
, depth
;
321 hint
= this_cpu_read(*sbq
->alloc_hint
);
322 depth
= READ_ONCE(sbq
->sb
.depth
);
323 if (unlikely(hint
>= depth
)) {
324 hint
= depth
? prandom_u32() % depth
: 0;
325 this_cpu_write(*sbq
->alloc_hint
, hint
);
327 nr
= sbitmap_get(&sbq
->sb
, hint
, sbq
->round_robin
);
330 /* If the map is full, a hint won't do us much good. */
331 this_cpu_write(*sbq
->alloc_hint
, 0);
332 } else if (nr
== hint
|| unlikely(sbq
->round_robin
)) {
333 /* Only update the hint if we used it. */
335 if (hint
>= depth
- 1)
337 this_cpu_write(*sbq
->alloc_hint
, hint
);
342 EXPORT_SYMBOL_GPL(__sbitmap_queue_get
);
344 static struct sbq_wait_state
*sbq_wake_ptr(struct sbitmap_queue
*sbq
)
348 wake_index
= atomic_read(&sbq
->wake_index
);
349 for (i
= 0; i
< SBQ_WAIT_QUEUES
; i
++) {
350 struct sbq_wait_state
*ws
= &sbq
->ws
[wake_index
];
352 if (waitqueue_active(&ws
->wait
)) {
353 int o
= atomic_read(&sbq
->wake_index
);
356 atomic_cmpxchg(&sbq
->wake_index
, o
, wake_index
);
360 wake_index
= sbq_index_inc(wake_index
);
366 static void sbq_wake_up(struct sbitmap_queue
*sbq
)
368 struct sbq_wait_state
*ws
;
369 unsigned int wake_batch
;
373 * Pairs with the memory barrier in set_current_state() to ensure the
374 * proper ordering of clear_bit()/waitqueue_active() in the waker and
375 * test_and_set_bit()/prepare_to_wait()/finish_wait() in the waiter. See
376 * the comment on waitqueue_active(). This is __after_atomic because we
377 * just did clear_bit() in the caller.
379 smp_mb__after_atomic();
381 ws
= sbq_wake_ptr(sbq
);
385 wait_cnt
= atomic_dec_return(&ws
->wait_cnt
);
387 wake_batch
= READ_ONCE(sbq
->wake_batch
);
389 * Pairs with the memory barrier in sbitmap_queue_resize() to
390 * ensure that we see the batch size update before the wait
393 smp_mb__before_atomic();
395 * If there are concurrent callers to sbq_wake_up(), the last
396 * one to decrement the wait count below zero will bump it back
397 * up. If there is a concurrent resize, the count reset will
398 * either cause the cmpxchg to fail or overwrite after the
401 atomic_cmpxchg(&ws
->wait_cnt
, wait_cnt
, wait_cnt
+ wake_batch
);
402 sbq_index_atomic_inc(&sbq
->wake_index
);
407 void sbitmap_queue_clear(struct sbitmap_queue
*sbq
, unsigned int nr
,
410 sbitmap_clear_bit(&sbq
->sb
, nr
);
412 if (likely(!sbq
->round_robin
&& nr
< sbq
->sb
.depth
))
413 *per_cpu_ptr(sbq
->alloc_hint
, cpu
) = nr
;
415 EXPORT_SYMBOL_GPL(sbitmap_queue_clear
);
417 void sbitmap_queue_wake_all(struct sbitmap_queue
*sbq
)
422 * Pairs with the memory barrier in set_current_state() like in
426 wake_index
= atomic_read(&sbq
->wake_index
);
427 for (i
= 0; i
< SBQ_WAIT_QUEUES
; i
++) {
428 struct sbq_wait_state
*ws
= &sbq
->ws
[wake_index
];
430 if (waitqueue_active(&ws
->wait
))
433 wake_index
= sbq_index_inc(wake_index
);
436 EXPORT_SYMBOL_GPL(sbitmap_queue_wake_all
);
438 void sbitmap_queue_show(struct sbitmap_queue
*sbq
, struct seq_file
*m
)
443 sbitmap_show(&sbq
->sb
, m
);
445 seq_puts(m
, "alloc_hint={");
447 for_each_possible_cpu(i
) {
451 seq_printf(m
, "%u", *per_cpu_ptr(sbq
->alloc_hint
, i
));
455 seq_printf(m
, "wake_batch=%u\n", sbq
->wake_batch
);
456 seq_printf(m
, "wake_index=%d\n", atomic_read(&sbq
->wake_index
));
458 seq_puts(m
, "ws={\n");
459 for (i
= 0; i
< SBQ_WAIT_QUEUES
; i
++) {
460 struct sbq_wait_state
*ws
= &sbq
->ws
[i
];
462 seq_printf(m
, "\t{.wait_cnt=%d, .wait=%s},\n",
463 atomic_read(&ws
->wait_cnt
),
464 waitqueue_active(&ws
->wait
) ? "active" : "inactive");
468 seq_printf(m
, "round_robin=%d\n", sbq
->round_robin
);
470 EXPORT_SYMBOL_GPL(sbitmap_queue_show
);