1 /* 2 * Fast and scalable bitmap tagging variant. Uses sparser bitmaps spread 3 * over multiple cachelines to avoid ping-pong between multiple submitters 4 * or submitter and completer. Uses rolling wakeups to avoid falling of 5 * the scaling cliff when we run out of tags and have to start putting 6 * submitters to sleep. 7 * 8 * Uses active queue tracking to support fairer distribution of tags 9 * between multiple submitters when a shared tag map is used. 10 * 11 * Copyright (C) 2013-2014 Jens Axboe 12 */ 13 #include <linux/kernel.h> 14 #include <linux/module.h> 15 #include <linux/random.h> 16 17 #include <linux/blk-mq.h> 18 #include "blk.h" 19 #include "blk-mq.h" 20 #include "blk-mq-tag.h" 21 22 static bool bt_has_free_tags(struct blk_mq_bitmap_tags *bt) 23 { 24 int i; 25 26 for (i = 0; i < bt->map_nr; i++) { 27 struct blk_align_bitmap *bm = &bt->map[i]; 28 int ret; 29 30 ret = find_first_zero_bit(&bm->word, bm->depth); 31 if (ret < bm->depth) 32 return true; 33 } 34 35 return false; 36 } 37 38 bool blk_mq_has_free_tags(struct blk_mq_tags *tags) 39 { 40 if (!tags) 41 return true; 42 43 return bt_has_free_tags(&tags->bitmap_tags); 44 } 45 46 static inline int bt_index_inc(int index) 47 { 48 return (index + 1) & (BT_WAIT_QUEUES - 1); 49 } 50 51 static inline void bt_index_atomic_inc(atomic_t *index) 52 { 53 int old = atomic_read(index); 54 int new = bt_index_inc(old); 55 atomic_cmpxchg(index, old, new); 56 } 57 58 /* 59 * If a previously inactive queue goes active, bump the active user count. 60 */ 61 bool __blk_mq_tag_busy(struct blk_mq_hw_ctx *hctx) 62 { 63 if (!test_bit(BLK_MQ_S_TAG_ACTIVE, &hctx->state) && 64 !test_and_set_bit(BLK_MQ_S_TAG_ACTIVE, &hctx->state)) 65 atomic_inc(&hctx->tags->active_queues); 66 67 return true; 68 } 69 70 /* 71 * Wakeup all potentially sleeping on tags 72 */ 73 void blk_mq_tag_wakeup_all(struct blk_mq_tags *tags, bool include_reserve) 74 { 75 struct blk_mq_bitmap_tags *bt; 76 int i, wake_index; 77 78 bt = &tags->bitmap_tags; 79 wake_index = atomic_read(&bt->wake_index); 80 for (i = 0; i < BT_WAIT_QUEUES; i++) { 81 struct bt_wait_state *bs = &bt->bs[wake_index]; 82 83 if (waitqueue_active(&bs->wait)) 84 wake_up(&bs->wait); 85 86 wake_index = bt_index_inc(wake_index); 87 } 88 89 if (include_reserve) { 90 bt = &tags->breserved_tags; 91 if (waitqueue_active(&bt->bs[0].wait)) 92 wake_up(&bt->bs[0].wait); 93 } 94 } 95 96 /* 97 * If a previously busy queue goes inactive, potential waiters could now 98 * be allowed to queue. Wake them up and check. 99 */ 100 void __blk_mq_tag_idle(struct blk_mq_hw_ctx *hctx) 101 { 102 struct blk_mq_tags *tags = hctx->tags; 103 104 if (!test_and_clear_bit(BLK_MQ_S_TAG_ACTIVE, &hctx->state)) 105 return; 106 107 atomic_dec(&tags->active_queues); 108 109 blk_mq_tag_wakeup_all(tags, false); 110 } 111 112 /* 113 * For shared tag users, we track the number of currently active users 114 * and attempt to provide a fair share of the tag depth for each of them. 115 */ 116 static inline bool hctx_may_queue(struct blk_mq_hw_ctx *hctx, 117 struct blk_mq_bitmap_tags *bt) 118 { 119 unsigned int depth, users; 120 121 if (!hctx || !(hctx->flags & BLK_MQ_F_TAG_SHARED)) 122 return true; 123 if (!test_bit(BLK_MQ_S_TAG_ACTIVE, &hctx->state)) 124 return true; 125 126 /* 127 * Don't try dividing an ant 128 */ 129 if (bt->depth == 1) 130 return true; 131 132 users = atomic_read(&hctx->tags->active_queues); 133 if (!users) 134 return true; 135 136 /* 137 * Allow at least some tags 138 */ 139 depth = max((bt->depth + users - 1) / users, 4U); 140 return atomic_read(&hctx->nr_active) < depth; 141 } 142 143 static int __bt_get_word(struct blk_align_bitmap *bm, unsigned int last_tag, 144 bool nowrap) 145 { 146 int tag, org_last_tag = last_tag; 147 148 while (1) { 149 tag = find_next_zero_bit(&bm->word, bm->depth, last_tag); 150 if (unlikely(tag >= bm->depth)) { 151 /* 152 * We started with an offset, and we didn't reset the 153 * offset to 0 in a failure case, so start from 0 to 154 * exhaust the map. 155 */ 156 if (org_last_tag && last_tag && !nowrap) { 157 last_tag = org_last_tag = 0; 158 continue; 159 } 160 return -1; 161 } 162 163 if (!test_and_set_bit(tag, &bm->word)) 164 break; 165 166 last_tag = tag + 1; 167 if (last_tag >= bm->depth - 1) 168 last_tag = 0; 169 } 170 171 return tag; 172 } 173 174 #define BT_ALLOC_RR(tags) (tags->alloc_policy == BLK_TAG_ALLOC_RR) 175 176 /* 177 * Straight forward bitmap tag implementation, where each bit is a tag 178 * (cleared == free, and set == busy). The small twist is using per-cpu 179 * last_tag caches, which blk-mq stores in the blk_mq_ctx software queue 180 * contexts. This enables us to drastically limit the space searched, 181 * without dirtying an extra shared cacheline like we would if we stored 182 * the cache value inside the shared blk_mq_bitmap_tags structure. On top 183 * of that, each word of tags is in a separate cacheline. This means that 184 * multiple users will tend to stick to different cachelines, at least 185 * until the map is exhausted. 186 */ 187 static int __bt_get(struct blk_mq_hw_ctx *hctx, struct blk_mq_bitmap_tags *bt, 188 unsigned int *tag_cache, struct blk_mq_tags *tags) 189 { 190 unsigned int last_tag, org_last_tag; 191 int index, i, tag; 192 193 if (!hctx_may_queue(hctx, bt)) 194 return -1; 195 196 last_tag = org_last_tag = *tag_cache; 197 index = TAG_TO_INDEX(bt, last_tag); 198 199 for (i = 0; i < bt->map_nr; i++) { 200 tag = __bt_get_word(&bt->map[index], TAG_TO_BIT(bt, last_tag), 201 BT_ALLOC_RR(tags)); 202 if (tag != -1) { 203 tag += (index << bt->bits_per_word); 204 goto done; 205 } 206 207 /* 208 * Jump to next index, and reset the last tag to be the 209 * first tag of that index 210 */ 211 index++; 212 last_tag = (index << bt->bits_per_word); 213 214 if (index >= bt->map_nr) { 215 index = 0; 216 last_tag = 0; 217 } 218 } 219 220 *tag_cache = 0; 221 return -1; 222 223 /* 224 * Only update the cache from the allocation path, if we ended 225 * up using the specific cached tag. 226 */ 227 done: 228 if (tag == org_last_tag || unlikely(BT_ALLOC_RR(tags))) { 229 last_tag = tag + 1; 230 if (last_tag >= bt->depth - 1) 231 last_tag = 0; 232 233 *tag_cache = last_tag; 234 } 235 236 return tag; 237 } 238 239 static struct bt_wait_state *bt_wait_ptr(struct blk_mq_bitmap_tags *bt, 240 struct blk_mq_hw_ctx *hctx) 241 { 242 struct bt_wait_state *bs; 243 int wait_index; 244 245 if (!hctx) 246 return &bt->bs[0]; 247 248 wait_index = atomic_read(&hctx->wait_index); 249 bs = &bt->bs[wait_index]; 250 bt_index_atomic_inc(&hctx->wait_index); 251 return bs; 252 } 253 254 static int bt_get(struct blk_mq_alloc_data *data, 255 struct blk_mq_bitmap_tags *bt, 256 struct blk_mq_hw_ctx *hctx, 257 unsigned int *last_tag, struct blk_mq_tags *tags) 258 { 259 struct bt_wait_state *bs; 260 DEFINE_WAIT(wait); 261 int tag; 262 263 tag = __bt_get(hctx, bt, last_tag, tags); 264 if (tag != -1) 265 return tag; 266 267 if (!(data->gfp & __GFP_WAIT)) 268 return -1; 269 270 bs = bt_wait_ptr(bt, hctx); 271 do { 272 prepare_to_wait(&bs->wait, &wait, TASK_UNINTERRUPTIBLE); 273 274 tag = __bt_get(hctx, bt, last_tag, tags); 275 if (tag != -1) 276 break; 277 278 /* 279 * We're out of tags on this hardware queue, kick any 280 * pending IO submits before going to sleep waiting for 281 * some to complete. 282 */ 283 blk_mq_run_hw_queue(hctx, false); 284 285 /* 286 * Retry tag allocation after running the hardware queue, 287 * as running the queue may also have found completions. 288 */ 289 tag = __bt_get(hctx, bt, last_tag, tags); 290 if (tag != -1) 291 break; 292 293 blk_mq_put_ctx(data->ctx); 294 295 io_schedule(); 296 297 data->ctx = blk_mq_get_ctx(data->q); 298 data->hctx = data->q->mq_ops->map_queue(data->q, 299 data->ctx->cpu); 300 if (data->reserved) { 301 bt = &data->hctx->tags->breserved_tags; 302 } else { 303 last_tag = &data->ctx->last_tag; 304 hctx = data->hctx; 305 bt = &hctx->tags->bitmap_tags; 306 } 307 finish_wait(&bs->wait, &wait); 308 bs = bt_wait_ptr(bt, hctx); 309 } while (1); 310 311 finish_wait(&bs->wait, &wait); 312 return tag; 313 } 314 315 static unsigned int __blk_mq_get_tag(struct blk_mq_alloc_data *data) 316 { 317 int tag; 318 319 tag = bt_get(data, &data->hctx->tags->bitmap_tags, data->hctx, 320 &data->ctx->last_tag, data->hctx->tags); 321 if (tag >= 0) 322 return tag + data->hctx->tags->nr_reserved_tags; 323 324 return BLK_MQ_TAG_FAIL; 325 } 326 327 static unsigned int __blk_mq_get_reserved_tag(struct blk_mq_alloc_data *data) 328 { 329 int tag, zero = 0; 330 331 if (unlikely(!data->hctx->tags->nr_reserved_tags)) { 332 WARN_ON_ONCE(1); 333 return BLK_MQ_TAG_FAIL; 334 } 335 336 tag = bt_get(data, &data->hctx->tags->breserved_tags, NULL, &zero, 337 data->hctx->tags); 338 if (tag < 0) 339 return BLK_MQ_TAG_FAIL; 340 341 return tag; 342 } 343 344 unsigned int blk_mq_get_tag(struct blk_mq_alloc_data *data) 345 { 346 if (!data->reserved) 347 return __blk_mq_get_tag(data); 348 349 return __blk_mq_get_reserved_tag(data); 350 } 351 352 static struct bt_wait_state *bt_wake_ptr(struct blk_mq_bitmap_tags *bt) 353 { 354 int i, wake_index; 355 356 wake_index = atomic_read(&bt->wake_index); 357 for (i = 0; i < BT_WAIT_QUEUES; i++) { 358 struct bt_wait_state *bs = &bt->bs[wake_index]; 359 360 if (waitqueue_active(&bs->wait)) { 361 int o = atomic_read(&bt->wake_index); 362 if (wake_index != o) 363 atomic_cmpxchg(&bt->wake_index, o, wake_index); 364 365 return bs; 366 } 367 368 wake_index = bt_index_inc(wake_index); 369 } 370 371 return NULL; 372 } 373 374 static void bt_clear_tag(struct blk_mq_bitmap_tags *bt, unsigned int tag) 375 { 376 const int index = TAG_TO_INDEX(bt, tag); 377 struct bt_wait_state *bs; 378 int wait_cnt; 379 380 clear_bit(TAG_TO_BIT(bt, tag), &bt->map[index].word); 381 382 /* Ensure that the wait list checks occur after clear_bit(). */ 383 smp_mb(); 384 385 bs = bt_wake_ptr(bt); 386 if (!bs) 387 return; 388 389 wait_cnt = atomic_dec_return(&bs->wait_cnt); 390 if (unlikely(wait_cnt < 0)) 391 wait_cnt = atomic_inc_return(&bs->wait_cnt); 392 if (wait_cnt == 0) { 393 atomic_add(bt->wake_cnt, &bs->wait_cnt); 394 bt_index_atomic_inc(&bt->wake_index); 395 wake_up(&bs->wait); 396 } 397 } 398 399 void blk_mq_put_tag(struct blk_mq_hw_ctx *hctx, unsigned int tag, 400 unsigned int *last_tag) 401 { 402 struct blk_mq_tags *tags = hctx->tags; 403 404 if (tag >= tags->nr_reserved_tags) { 405 const int real_tag = tag - tags->nr_reserved_tags; 406 407 BUG_ON(real_tag >= tags->nr_tags); 408 bt_clear_tag(&tags->bitmap_tags, real_tag); 409 if (likely(tags->alloc_policy == BLK_TAG_ALLOC_FIFO)) 410 *last_tag = real_tag; 411 } else { 412 BUG_ON(tag >= tags->nr_reserved_tags); 413 bt_clear_tag(&tags->breserved_tags, tag); 414 } 415 } 416 417 static void bt_for_each(struct blk_mq_hw_ctx *hctx, 418 struct blk_mq_bitmap_tags *bt, unsigned int off, 419 busy_iter_fn *fn, void *data, bool reserved) 420 { 421 struct request *rq; 422 int bit, i; 423 424 for (i = 0; i < bt->map_nr; i++) { 425 struct blk_align_bitmap *bm = &bt->map[i]; 426 427 for (bit = find_first_bit(&bm->word, bm->depth); 428 bit < bm->depth; 429 bit = find_next_bit(&bm->word, bm->depth, bit + 1)) { 430 rq = blk_mq_tag_to_rq(hctx->tags, off + bit); 431 if (rq->q == hctx->queue) 432 fn(hctx, rq, data, reserved); 433 } 434 435 off += (1 << bt->bits_per_word); 436 } 437 } 438 439 void blk_mq_tag_busy_iter(struct blk_mq_hw_ctx *hctx, busy_iter_fn *fn, 440 void *priv) 441 { 442 struct blk_mq_tags *tags = hctx->tags; 443 444 if (tags->nr_reserved_tags) 445 bt_for_each(hctx, &tags->breserved_tags, 0, fn, priv, true); 446 bt_for_each(hctx, &tags->bitmap_tags, tags->nr_reserved_tags, fn, priv, 447 false); 448 } 449 EXPORT_SYMBOL(blk_mq_tag_busy_iter); 450 451 static unsigned int bt_unused_tags(struct blk_mq_bitmap_tags *bt) 452 { 453 unsigned int i, used; 454 455 for (i = 0, used = 0; i < bt->map_nr; i++) { 456 struct blk_align_bitmap *bm = &bt->map[i]; 457 458 used += bitmap_weight(&bm->word, bm->depth); 459 } 460 461 return bt->depth - used; 462 } 463 464 static void bt_update_count(struct blk_mq_bitmap_tags *bt, 465 unsigned int depth) 466 { 467 unsigned int tags_per_word = 1U << bt->bits_per_word; 468 unsigned int map_depth = depth; 469 470 if (depth) { 471 int i; 472 473 for (i = 0; i < bt->map_nr; i++) { 474 bt->map[i].depth = min(map_depth, tags_per_word); 475 map_depth -= bt->map[i].depth; 476 } 477 } 478 479 bt->wake_cnt = BT_WAIT_BATCH; 480 if (bt->wake_cnt > depth / BT_WAIT_QUEUES) 481 bt->wake_cnt = max(1U, depth / BT_WAIT_QUEUES); 482 483 bt->depth = depth; 484 } 485 486 static int bt_alloc(struct blk_mq_bitmap_tags *bt, unsigned int depth, 487 int node, bool reserved) 488 { 489 int i; 490 491 bt->bits_per_word = ilog2(BITS_PER_LONG); 492 493 /* 494 * Depth can be zero for reserved tags, that's not a failure 495 * condition. 496 */ 497 if (depth) { 498 unsigned int nr, tags_per_word; 499 500 tags_per_word = (1 << bt->bits_per_word); 501 502 /* 503 * If the tag space is small, shrink the number of tags 504 * per word so we spread over a few cachelines, at least. 505 * If less than 4 tags, just forget about it, it's not 506 * going to work optimally anyway. 507 */ 508 if (depth >= 4) { 509 while (tags_per_word * 4 > depth) { 510 bt->bits_per_word--; 511 tags_per_word = (1 << bt->bits_per_word); 512 } 513 } 514 515 nr = ALIGN(depth, tags_per_word) / tags_per_word; 516 bt->map = kzalloc_node(nr * sizeof(struct blk_align_bitmap), 517 GFP_KERNEL, node); 518 if (!bt->map) 519 return -ENOMEM; 520 521 bt->map_nr = nr; 522 } 523 524 bt->bs = kzalloc(BT_WAIT_QUEUES * sizeof(*bt->bs), GFP_KERNEL); 525 if (!bt->bs) { 526 kfree(bt->map); 527 bt->map = NULL; 528 return -ENOMEM; 529 } 530 531 bt_update_count(bt, depth); 532 533 for (i = 0; i < BT_WAIT_QUEUES; i++) { 534 init_waitqueue_head(&bt->bs[i].wait); 535 atomic_set(&bt->bs[i].wait_cnt, bt->wake_cnt); 536 } 537 538 return 0; 539 } 540 541 static void bt_free(struct blk_mq_bitmap_tags *bt) 542 { 543 kfree(bt->map); 544 kfree(bt->bs); 545 } 546 547 static struct blk_mq_tags *blk_mq_init_bitmap_tags(struct blk_mq_tags *tags, 548 int node, int alloc_policy) 549 { 550 unsigned int depth = tags->nr_tags - tags->nr_reserved_tags; 551 552 tags->alloc_policy = alloc_policy; 553 554 if (bt_alloc(&tags->bitmap_tags, depth, node, false)) 555 goto enomem; 556 if (bt_alloc(&tags->breserved_tags, tags->nr_reserved_tags, node, true)) 557 goto enomem; 558 559 return tags; 560 enomem: 561 bt_free(&tags->bitmap_tags); 562 kfree(tags); 563 return NULL; 564 } 565 566 struct blk_mq_tags *blk_mq_init_tags(unsigned int total_tags, 567 unsigned int reserved_tags, 568 int node, int alloc_policy) 569 { 570 struct blk_mq_tags *tags; 571 572 if (total_tags > BLK_MQ_TAG_MAX) { 573 pr_err("blk-mq: tag depth too large\n"); 574 return NULL; 575 } 576 577 tags = kzalloc_node(sizeof(*tags), GFP_KERNEL, node); 578 if (!tags) 579 return NULL; 580 581 tags->nr_tags = total_tags; 582 tags->nr_reserved_tags = reserved_tags; 583 584 return blk_mq_init_bitmap_tags(tags, node, alloc_policy); 585 } 586 587 void blk_mq_free_tags(struct blk_mq_tags *tags) 588 { 589 bt_free(&tags->bitmap_tags); 590 bt_free(&tags->breserved_tags); 591 kfree(tags); 592 } 593 594 void blk_mq_tag_init_last_tag(struct blk_mq_tags *tags, unsigned int *tag) 595 { 596 unsigned int depth = tags->nr_tags - tags->nr_reserved_tags; 597 598 *tag = prandom_u32() % depth; 599 } 600 601 int blk_mq_tag_update_depth(struct blk_mq_tags *tags, unsigned int tdepth) 602 { 603 tdepth -= tags->nr_reserved_tags; 604 if (tdepth > tags->nr_tags) 605 return -EINVAL; 606 607 /* 608 * Don't need (or can't) update reserved tags here, they remain 609 * static and should never need resizing. 610 */ 611 bt_update_count(&tags->bitmap_tags, tdepth); 612 blk_mq_tag_wakeup_all(tags, false); 613 return 0; 614 } 615 616 /** 617 * blk_mq_unique_tag() - return a tag that is unique queue-wide 618 * @rq: request for which to compute a unique tag 619 * 620 * The tag field in struct request is unique per hardware queue but not over 621 * all hardware queues. Hence this function that returns a tag with the 622 * hardware context index in the upper bits and the per hardware queue tag in 623 * the lower bits. 624 * 625 * Note: When called for a request that is queued on a non-multiqueue request 626 * queue, the hardware context index is set to zero. 627 */ 628 u32 blk_mq_unique_tag(struct request *rq) 629 { 630 struct request_queue *q = rq->q; 631 struct blk_mq_hw_ctx *hctx; 632 int hwq = 0; 633 634 if (q->mq_ops) { 635 hctx = q->mq_ops->map_queue(q, rq->mq_ctx->cpu); 636 hwq = hctx->queue_num; 637 } 638 639 return (hwq << BLK_MQ_UNIQUE_TAG_BITS) | 640 (rq->tag & BLK_MQ_UNIQUE_TAG_MASK); 641 } 642 EXPORT_SYMBOL(blk_mq_unique_tag); 643 644 ssize_t blk_mq_tag_sysfs_show(struct blk_mq_tags *tags, char *page) 645 { 646 char *orig_page = page; 647 unsigned int free, res; 648 649 if (!tags) 650 return 0; 651 652 page += sprintf(page, "nr_tags=%u, reserved_tags=%u, " 653 "bits_per_word=%u\n", 654 tags->nr_tags, tags->nr_reserved_tags, 655 tags->bitmap_tags.bits_per_word); 656 657 free = bt_unused_tags(&tags->bitmap_tags); 658 res = bt_unused_tags(&tags->breserved_tags); 659 660 page += sprintf(page, "nr_free=%u, nr_reserved=%u\n", free, res); 661 page += sprintf(page, "active_queues=%u\n", atomic_read(&tags->active_queues)); 662 663 return page - orig_page; 664 } 665