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