block/blk-mq-tag.c

   1 #include <linux/kernel.h>
   2 #include <linux/module.h>
   3 #include <linux/random.h>
   4
   5 #include <linux/blk-mq.h>
   6 #include "blk.h"
   7 #include "blk-mq.h"
   8 #include "blk-mq-tag.h"
   9
  10 void blk_mq_wait_for_tags(struct blk_mq_tags *tags, struct blk_mq_hw_ctx *hctx,
  11                           bool reserved)
  12 {
  13         int tag, zero = 0;
  14
  15         tag = blk_mq_get_tag(tags, hctx, &zero, __GFP_WAIT, reserved);
  16         blk_mq_put_tag(tags, tag, &zero);
  17 }
  18
  19 static bool bt_has_free_tags(struct blk_mq_bitmap_tags *bt)
  20 {
  21         int i;
  22
  23         for (i = 0; i < bt->map_nr; i++) {
  24                 struct blk_mq_bitmap *bm = &bt->map[i];
  25                 int ret;
  26
  27                 ret = find_first_zero_bit(&bm->word, bm->depth);
  28                 if (ret < bm->depth)
  29                         return true;
  30         }
  31
  32         return false;
  33 }
  34
  35 bool blk_mq_has_free_tags(struct blk_mq_tags *tags)
  36 {
  37         if (!tags)
  38                 return true;
  39
  40         return bt_has_free_tags(&tags->bitmap_tags);
  41 }
  42
  43 static int __bt_get_word(struct blk_mq_bitmap *bm, unsigned int last_tag)
  44 {
  45         int tag, org_last_tag, end;
  46
  47         org_last_tag = last_tag;
  48         end = bm->depth;
  49         do {
  50 restart:
  51                 tag = find_next_zero_bit(&bm->word, end, last_tag);
  52                 if (unlikely(tag >= end)) {
  53                         /*
  54                          * We started with an offset, start from 0 to
  55                          * exhaust the map.
  56                          */
  57                         if (org_last_tag && last_tag) {
  58                                 end = last_tag;
  59                                 last_tag = 0;
  60                                 goto restart;
  61                         }
  62                         return -1;
  63                 }
  64                 last_tag = tag + 1;
  65         } while (test_and_set_bit_lock(tag, &bm->word));
  66
  67         return tag;
  68 }
  69
  70 /*
  71  * Straight forward bitmap tag implementation, where each bit is a tag
  72  * (cleared == free, and set == busy). The small twist is using per-cpu
  73  * last_tag caches, which blk-mq stores in the blk_mq_ctx software queue
  74  * contexts. This enables us to drastically limit the space searched,
  75  * without dirtying an extra shared cacheline like we would if we stored
  76  * the cache value inside the shared blk_mq_bitmap_tags structure. On top
  77  * of that, each word of tags is in a separate cacheline. This means that
  78  * multiple users will tend to stick to different cachelines, at least
  79  * until the map is exhausted.
  80  */
  81 static int __bt_get(struct blk_mq_bitmap_tags *bt, unsigned int *tag_cache)
  82 {
  83         unsigned int last_tag, org_last_tag;
  84         int index, i, tag;
  85
  86         last_tag = org_last_tag = *tag_cache;
  87         index = TAG_TO_INDEX(bt, last_tag);
  88
  89         for (i = 0; i < bt->map_nr; i++) {
  90                 tag = __bt_get_word(&bt->map[index], TAG_TO_BIT(bt, last_tag));
  91                 if (tag != -1) {
  92                         tag += (index << bt->bits_per_word);
  93                         goto done;
  94                 }
  95
  96                 last_tag = 0;
  97                 if (++index >= bt->map_nr)
  98                         index = 0;
  99         }
 100
 101         *tag_cache = 0;
 102         return -1;
 103
 104         /*
 105          * Only update the cache from the allocation path, if we ended
 106          * up using the specific cached tag.
 107          */
 108 done:
 109         if (tag == org_last_tag) {
 110                 last_tag = tag + 1;
 111                 if (last_tag >= bt->depth - 1)
 112                         last_tag = 0;
 113
 114                 *tag_cache = last_tag;
 115         }
 116
 117         return tag;
 118 }
 119
 120 static inline void bt_index_inc(unsigned int *index)
 121 {
 122         *index = (*index + 1) & (BT_WAIT_QUEUES - 1);
 123 }
 124
 125 static struct bt_wait_state *bt_wait_ptr(struct blk_mq_bitmap_tags *bt,
 126                                          struct blk_mq_hw_ctx *hctx)
 127 {
 128         struct bt_wait_state *bs;
 129
 130         if (!hctx)
 131                 return &bt->bs[0];
 132
 133         bs = &bt->bs[hctx->wait_index];
 134         bt_index_inc(&hctx->wait_index);
 135         return bs;
 136 }
 137
 138 static int bt_get(struct blk_mq_bitmap_tags *bt, struct blk_mq_hw_ctx *hctx,
 139                   unsigned int *last_tag, gfp_t gfp)
 140 {
 141         struct bt_wait_state *bs;
 142         DEFINE_WAIT(wait);
 143         int tag;
 144
 145         tag = __bt_get(bt, last_tag);
 146         if (tag != -1)
 147                 return tag;
 148
 149         if (!(gfp & __GFP_WAIT))
 150                 return -1;
 151
 152         bs = bt_wait_ptr(bt, hctx);
 153         do {
 154                 bool was_empty;
 155
 156                 was_empty = list_empty(&wait.task_list);
 157                 prepare_to_wait(&bs->wait, &wait, TASK_UNINTERRUPTIBLE);
 158
 159                 tag = __bt_get(bt, last_tag);
 160                 if (tag != -1)
 161                         break;
 162
 163                 if (was_empty)
 164                         atomic_set(&bs->wait_cnt, bt->wake_cnt);
 165
 166                 io_schedule();
 167         } while (1);
 168
 169         finish_wait(&bs->wait, &wait);
 170         return tag;
 171 }
 172
 173 static unsigned int __blk_mq_get_tag(struct blk_mq_tags *tags,
 174                                      struct blk_mq_hw_ctx *hctx,
 175                                      unsigned int *last_tag, gfp_t gfp)
 176 {
 177         int tag;
 178
 179         tag = bt_get(&tags->bitmap_tags, hctx, last_tag, gfp);
 180         if (tag >= 0)
 181                 return tag + tags->nr_reserved_tags;
 182
 183         return BLK_MQ_TAG_FAIL;
 184 }
 185
 186 static unsigned int __blk_mq_get_reserved_tag(struct blk_mq_tags *tags,
 187                                               gfp_t gfp)
 188 {
 189         int tag, zero = 0;
 190
 191         if (unlikely(!tags->nr_reserved_tags)) {
 192                 WARN_ON_ONCE(1);
 193                 return BLK_MQ_TAG_FAIL;
 194         }
 195
 196         tag = bt_get(&tags->breserved_tags, NULL, &zero, gfp);
 197         if (tag < 0)
 198                 return BLK_MQ_TAG_FAIL;
 199
 200         return tag;
 201 }
 202
 203 unsigned int blk_mq_get_tag(struct blk_mq_tags *tags,
 204                             struct blk_mq_hw_ctx *hctx, unsigned int *last_tag,
 205                             gfp_t gfp, bool reserved)
 206 {
 207         if (!reserved)
 208                 return __blk_mq_get_tag(tags, hctx, last_tag, gfp);
 209
 210         return __blk_mq_get_reserved_tag(tags, gfp);
 211 }
 212
 213 static struct bt_wait_state *bt_wake_ptr(struct blk_mq_bitmap_tags *bt)
 214 {
 215         int i, wake_index;
 216
 217         wake_index = bt->wake_index;
 218         for (i = 0; i < BT_WAIT_QUEUES; i++) {
 219                 struct bt_wait_state *bs = &bt->bs[wake_index];
 220
 221                 if (waitqueue_active(&bs->wait)) {
 222                         if (wake_index != bt->wake_index)
 223                                 bt->wake_index = wake_index;
 224
 225                         return bs;
 226                 }
 227
 228                 bt_index_inc(&wake_index);
 229         }
 230
 231         return NULL;
 232 }
 233
 234 static void bt_clear_tag(struct blk_mq_bitmap_tags *bt, unsigned int tag)
 235 {
 236         const int index = TAG_TO_INDEX(bt, tag);
 237         struct bt_wait_state *bs;
 238
 239         /*
 240          * The unlock memory barrier need to order access to req in free
 241          * path and clearing tag bit
 242          */
 243         clear_bit_unlock(TAG_TO_BIT(bt, tag), &bt->map[index].word);
 244
 245         bs = bt_wake_ptr(bt);
 246         if (bs && atomic_dec_and_test(&bs->wait_cnt)) {
 247                 smp_mb__after_clear_bit();
 248                 atomic_set(&bs->wait_cnt, bt->wake_cnt);
 249                 bt_index_inc(&bt->wake_index);
 250                 wake_up(&bs->wait);
 251         }
 252 }
 253
 254 static void __blk_mq_put_tag(struct blk_mq_tags *tags, unsigned int tag)
 255 {
 256         BUG_ON(tag >= tags->nr_tags);
 257
 258         bt_clear_tag(&tags->bitmap_tags, tag);
 259 }
 260
 261 static void __blk_mq_put_reserved_tag(struct blk_mq_tags *tags,
 262                                       unsigned int tag)
 263 {
 264         BUG_ON(tag >= tags->nr_reserved_tags);
 265
 266         bt_clear_tag(&tags->breserved_tags, tag);
 267 }
 268
 269 void blk_mq_put_tag(struct blk_mq_tags *tags, unsigned int tag,
 270                     unsigned int *last_tag)
 271 {
 272         if (tag >= tags->nr_reserved_tags) {
 273                 const int real_tag = tag - tags->nr_reserved_tags;
 274
 275                 __blk_mq_put_tag(tags, real_tag);
 276                 *last_tag = real_tag;
 277         } else
 278                 __blk_mq_put_reserved_tag(tags, tag);
 279 }
 280
 281 static void bt_for_each_free(struct blk_mq_bitmap_tags *bt,
 282                              unsigned long *free_map, unsigned int off)
 283 {
 284         int i;
 285
 286         for (i = 0; i < bt->map_nr; i++) {
 287                 struct blk_mq_bitmap *bm = &bt->map[i];
 288                 int bit = 0;
 289
 290                 do {
 291                         bit = find_next_zero_bit(&bm->word, bm->depth, bit);
 292                         if (bit >= bm->depth)
 293                                 break;
 294
 295                         __set_bit(bit + off, free_map);
 296                         bit++;
 297                 } while (1);
 298
 299                 off += (1 << bt->bits_per_word);
 300         }
 301 }
 302
 303 void blk_mq_tag_busy_iter(struct blk_mq_tags *tags,
 304                           void (*fn)(void *, unsigned long *), void *data)
 305 {
 306         unsigned long *tag_map;
 307         size_t map_size;
 308
 309         map_size = ALIGN(tags->nr_tags, BITS_PER_LONG) / BITS_PER_LONG;
 310         tag_map = kzalloc(map_size * sizeof(unsigned long), GFP_ATOMIC);
 311         if (!tag_map)
 312                 return;
 313
 314         bt_for_each_free(&tags->bitmap_tags, tag_map, tags->nr_reserved_tags);
 315         if (tags->nr_reserved_tags)
 316                 bt_for_each_free(&tags->breserved_tags, tag_map, 0);
 317
 318         fn(data, tag_map);
 319         kfree(tag_map);
 320 }
 321
 322 static unsigned int bt_unused_tags(struct blk_mq_bitmap_tags *bt)
 323 {
 324         unsigned int i, used;
 325
 326         for (i = 0, used = 0; i < bt->map_nr; i++) {
 327                 struct blk_mq_bitmap *bm = &bt->map[i];
 328
 329                 used += bitmap_weight(&bm->word, bm->depth);
 330         }
 331
 332         return bt->depth - used;
 333 }
 334
 335 static int bt_alloc(struct blk_mq_bitmap_tags *bt, unsigned int depth,
 336                         int node, bool reserved)
 337 {
 338         int i;
 339
 340         bt->bits_per_word = ilog2(BITS_PER_LONG);
 341
 342         /*
 343          * Depth can be zero for reserved tags, that's not a failure
 344          * condition.
 345          */
 346         if (depth) {
 347                 unsigned int nr, i, map_depth, tags_per_word;
 348
 349                 tags_per_word = (1 << bt->bits_per_word);
 350
 351                 /*
 352                  * If the tag space is small, shrink the number of tags
 353                  * per word so we spread over a few cachelines, at least.
 354                  * If less than 4 tags, just forget about it, it's not
 355                  * going to work optimally anyway.
 356                  */
 357                 if (depth >= 4) {
 358                         while (tags_per_word * 4 > depth) {
 359                                 bt->bits_per_word--;
 360                                 tags_per_word = (1 << bt->bits_per_word);
 361                         }
 362                 }
 363
 364                 nr = ALIGN(depth, tags_per_word) / tags_per_word;
 365                 bt->map = kzalloc_node(nr * sizeof(struct blk_mq_bitmap),
 366                                                 GFP_KERNEL, node);
 367                 if (!bt->map)
 368                         return -ENOMEM;
 369
 370                 bt->map_nr = nr;
 371                 map_depth = depth;
 372                 for (i = 0; i < nr; i++) {
 373                         bt->map[i].depth = min(map_depth, tags_per_word);
 374                         map_depth -= tags_per_word;
 375                 }
 376         }
 377
 378         bt->bs = kzalloc(BT_WAIT_QUEUES * sizeof(*bt->bs), GFP_KERNEL);
 379         if (!bt->bs) {
 380                 kfree(bt->map);
 381                 return -ENOMEM;
 382         }
 383
 384         for (i = 0; i < BT_WAIT_QUEUES; i++)
 385                 init_waitqueue_head(&bt->bs[i].wait);
 386
 387         bt->wake_cnt = BT_WAIT_BATCH;
 388         if (bt->wake_cnt > depth / 4)
 389                 bt->wake_cnt = max(1U, depth / 4);
 390
 391         bt->depth = depth;
 392         return 0;
 393 }
 394
 395 static void bt_free(struct blk_mq_bitmap_tags *bt)
 396 {
 397         kfree(bt->map);
 398         kfree(bt->bs);
 399 }
 400
 401 static struct blk_mq_tags *blk_mq_init_bitmap_tags(struct blk_mq_tags *tags,
 402                                                    int node)
 403 {
 404         unsigned int depth = tags->nr_tags - tags->nr_reserved_tags;
 405
 406         if (bt_alloc(&tags->bitmap_tags, depth, node, false))
 407                 goto enomem;
 408         if (bt_alloc(&tags->breserved_tags, tags->nr_reserved_tags, node, true))
 409                 goto enomem;
 410
 411         return tags;
 412 enomem:
 413         bt_free(&tags->bitmap_tags);
 414         kfree(tags);
 415         return NULL;
 416 }
 417
 418 struct blk_mq_tags *blk_mq_init_tags(unsigned int total_tags,
 419                                      unsigned int reserved_tags, int node)
 420 {
 421         unsigned int nr_tags, nr_cache;
 422         struct blk_mq_tags *tags;
 423
 424         if (total_tags > BLK_MQ_TAG_MAX) {
 425                 pr_err("blk-mq: tag depth too large\n");
 426                 return NULL;
 427         }
 428
 429         tags = kzalloc_node(sizeof(*tags), GFP_KERNEL, node);
 430         if (!tags)
 431                 return NULL;
 432
 433         nr_tags = total_tags - reserved_tags;
 434         nr_cache = nr_tags / num_online_cpus();
 435
 436         tags->nr_tags = total_tags;
 437         tags->nr_reserved_tags = reserved_tags;
 438
 439         return blk_mq_init_bitmap_tags(tags, node);
 440 }
 441
 442 void blk_mq_free_tags(struct blk_mq_tags *tags)
 443 {
 444         bt_free(&tags->bitmap_tags);
 445         bt_free(&tags->breserved_tags);
 446         kfree(tags);
 447 }
 448
 449 void blk_mq_tag_init_last_tag(struct blk_mq_tags *tags, unsigned int *tag)
 450 {
 451         unsigned int depth = tags->nr_tags - tags->nr_reserved_tags;
 452
 453         if (depth > 1)
 454                 *tag = prandom_u32() % (depth - 1);
 455         else
 456                 *tag = 0;
 457 }
 458
 459 ssize_t blk_mq_tag_sysfs_show(struct blk_mq_tags *tags, char *page)
 460 {
 461         char *orig_page = page;
 462         unsigned int free, res;
 463
 464         if (!tags)
 465                 return 0;
 466
 467         page += sprintf(page, "nr_tags=%u, reserved_tags=%u, "
 468                         "bits_per_word=%u\n",
 469                         tags->nr_tags, tags->nr_reserved_tags,
 470                         tags->bitmap_tags.bits_per_word);
 471
 472         free = bt_unused_tags(&tags->bitmap_tags);
 473         res = bt_unused_tags(&tags->breserved_tags);
 474
 475         page += sprintf(page, "nr_free=%u, nr_reserved=%u\n", free, res);
 476
 477         return page - orig_page;
 478 }