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