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         clear_bit(TAG_TO_BIT(bt, tag), &bt->map[index].word);
 240
 241         bs = bt_wake_ptr(bt);
 242         if (bs && atomic_dec_and_test(&bs->wait_cnt)) {
 243                 smp_mb__after_clear_bit();
 244                 atomic_set(&bs->wait_cnt, bt->wake_cnt);
 245                 bt_index_inc(&bt->wake_index);
 246                 wake_up(&bs->wait);
 247         }
 248 }
 249
 250 static void __blk_mq_put_tag(struct blk_mq_tags *tags, unsigned int tag)
 251 {
 252         BUG_ON(tag >= tags->nr_tags);
 253
 254         bt_clear_tag(&tags->bitmap_tags, tag);
 255 }
 256
 257 static void __blk_mq_put_reserved_tag(struct blk_mq_tags *tags,
 258                                       unsigned int tag)
 259 {
 260         BUG_ON(tag >= tags->nr_reserved_tags);
 261
 262         bt_clear_tag(&tags->breserved_tags, tag);
 263 }
 264
 265 void blk_mq_put_tag(struct blk_mq_tags *tags, unsigned int tag,
 266                     unsigned int *last_tag)
 267 {
 268         if (tag >= tags->nr_reserved_tags) {
 269                 const int real_tag = tag - tags->nr_reserved_tags;
 270
 271                 __blk_mq_put_tag(tags, real_tag);
 272                 *last_tag = real_tag;
 273         } else
 274                 __blk_mq_put_reserved_tag(tags, tag);
 275 }
 276
 277 static void bt_for_each_free(struct blk_mq_bitmap_tags *bt,
 278                              unsigned long *free_map, unsigned int off)
 279 {
 280         int i;
 281
 282         for (i = 0; i < bt->map_nr; i++) {
 283                 struct blk_mq_bitmap *bm = &bt->map[i];
 284                 int bit = 0;
 285
 286                 do {
 287                         bit = find_next_zero_bit(&bm->word, bm->depth, bit);
 288                         if (bit >= bm->depth)
 289                                 break;
 290
 291                         __set_bit(bit + off, free_map);
 292                         bit++;
 293                 } while (1);
 294
 295                 off += (1 << bt->bits_per_word);
 296         }
 297 }
 298
 299 void blk_mq_tag_busy_iter(struct blk_mq_tags *tags,
 300                           void (*fn)(void *, unsigned long *), void *data)
 301 {
 302         unsigned long *tag_map;
 303         size_t map_size;
 304
 305         map_size = ALIGN(tags->nr_tags, BITS_PER_LONG) / BITS_PER_LONG;
 306         tag_map = kzalloc(map_size * sizeof(unsigned long), GFP_ATOMIC);
 307         if (!tag_map)
 308                 return;
 309
 310         bt_for_each_free(&tags->bitmap_tags, tag_map, tags->nr_reserved_tags);
 311         if (tags->nr_reserved_tags)
 312                 bt_for_each_free(&tags->breserved_tags, tag_map, 0);
 313
 314         fn(data, tag_map);
 315         kfree(tag_map);
 316 }
 317
 318 static unsigned int bt_unused_tags(struct blk_mq_bitmap_tags *bt)
 319 {
 320         unsigned int i, used;
 321
 322         for (i = 0, used = 0; i < bt->map_nr; i++) {
 323                 struct blk_mq_bitmap *bm = &bt->map[i];
 324
 325                 used += bitmap_weight(&bm->word, bm->depth);
 326         }
 327
 328         return bt->depth - used;
 329 }
 330
 331 static int bt_alloc(struct blk_mq_bitmap_tags *bt, unsigned int depth,
 332                         int node, bool reserved)
 333 {
 334         int i;
 335
 336         bt->bits_per_word = ilog2(BITS_PER_LONG);
 337
 338         /*
 339          * Depth can be zero for reserved tags, that's not a failure
 340          * condition.
 341          */
 342         if (depth) {
 343                 unsigned int nr, i, map_depth, tags_per_word;
 344
 345                 tags_per_word = (1 << bt->bits_per_word);
 346
 347                 /*
 348                  * If the tag space is small, shrink the number of tags
 349                  * per word so we spread over a few cachelines, at least.
 350                  * If less than 4 tags, just forget about it, it's not
 351                  * going to work optimally anyway.
 352                  */
 353                 if (depth >= 4) {
 354                         while (tags_per_word * 4 > depth) {
 355                                 bt->bits_per_word--;
 356                                 tags_per_word = (1 << bt->bits_per_word);
 357                         }
 358                 }
 359
 360                 nr = ALIGN(depth, tags_per_word) / tags_per_word;
 361                 bt->map = kzalloc_node(nr * sizeof(struct blk_mq_bitmap),
 362                                                 GFP_KERNEL, node);
 363                 if (!bt->map)
 364                         return -ENOMEM;
 365
 366                 bt->map_nr = nr;
 367                 map_depth = depth;
 368                 for (i = 0; i < nr; i++) {
 369                         bt->map[i].depth = min(map_depth, tags_per_word);
 370                         map_depth -= tags_per_word;
 371                 }
 372         }
 373
 374         bt->bs = kzalloc(BT_WAIT_QUEUES * sizeof(*bt->bs), GFP_KERNEL);
 375         if (!bt->bs) {
 376                 kfree(bt->map);
 377                 return -ENOMEM;
 378         }
 379
 380         for (i = 0; i < BT_WAIT_QUEUES; i++)
 381                 init_waitqueue_head(&bt->bs[i].wait);
 382
 383         bt->wake_cnt = BT_WAIT_BATCH;
 384         if (bt->wake_cnt > depth / 4)
 385                 bt->wake_cnt = max(1U, depth / 4);
 386
 387         bt->depth = depth;
 388         return 0;
 389 }
 390
 391 static void bt_free(struct blk_mq_bitmap_tags *bt)
 392 {
 393         kfree(bt->map);
 394         kfree(bt->bs);
 395 }
 396
 397 static struct blk_mq_tags *blk_mq_init_bitmap_tags(struct blk_mq_tags *tags,
 398                                                    int node)
 399 {
 400         unsigned int depth = tags->nr_tags - tags->nr_reserved_tags;
 401
 402         if (bt_alloc(&tags->bitmap_tags, depth, node, false))
 403                 goto enomem;
 404         if (bt_alloc(&tags->breserved_tags, tags->nr_reserved_tags, node, true))
 405                 goto enomem;
 406
 407         return tags;
 408 enomem:
 409         bt_free(&tags->bitmap_tags);
 410         kfree(tags);
 411         return NULL;
 412 }
 413
 414 struct blk_mq_tags *blk_mq_init_tags(unsigned int total_tags,
 415                                      unsigned int reserved_tags, int node)
 416 {
 417         unsigned int nr_tags, nr_cache;
 418         struct blk_mq_tags *tags;
 419
 420         if (total_tags > BLK_MQ_TAG_MAX) {
 421                 pr_err("blk-mq: tag depth too large\n");
 422                 return NULL;
 423         }
 424
 425         tags = kzalloc_node(sizeof(*tags), GFP_KERNEL, node);
 426         if (!tags)
 427                 return NULL;
 428
 429         nr_tags = total_tags - reserved_tags;
 430         nr_cache = nr_tags / num_online_cpus();
 431
 432         tags->nr_tags = total_tags;
 433         tags->nr_reserved_tags = reserved_tags;
 434
 435         return blk_mq_init_bitmap_tags(tags, node);
 436 }
 437
 438 void blk_mq_free_tags(struct blk_mq_tags *tags)
 439 {
 440         bt_free(&tags->bitmap_tags);
 441         bt_free(&tags->breserved_tags);
 442         kfree(tags);
 443 }
 444
 445 void blk_mq_tag_init_last_tag(struct blk_mq_tags *tags, unsigned int *tag)
 446 {
 447         unsigned int depth = tags->nr_tags - tags->nr_reserved_tags;
 448
 449         if (depth > 1)
 450                 *tag = prandom_u32() % (depth - 1);
 451         else
 452                 *tag = 0;
 453 }
 454
 455 ssize_t blk_mq_tag_sysfs_show(struct blk_mq_tags *tags, char *page)
 456 {
 457         char *orig_page = page;
 458         unsigned int free, res;
 459
 460         if (!tags)
 461                 return 0;
 462
 463         page += sprintf(page, "nr_tags=%u, reserved_tags=%u, "
 464                         "bits_per_word=%u\n",
 465                         tags->nr_tags, tags->nr_reserved_tags,
 466                         tags->bitmap_tags.bits_per_word);
 467
 468         free = bt_unused_tags(&tags->bitmap_tags);
 469         res = bt_unused_tags(&tags->breserved_tags);
 470
 471         page += sprintf(page, "nr_free=%u, nr_reserved=%u\n", free, res);
 472
 473         return page - orig_page;
 474 }