kyber-iosched.c

   1// SPDX-License-Identifier: GPL-2.0
   2/*
   3 * The Kyber I/O scheduler. Controls latency by throttling queue depths using
   4 * scalable techniques.
   5 *
   6 * Copyright (C) 2017 Facebook
   7 */
   8
   9#include <linux/kernel.h>
  10#include <linux/blkdev.h>
  11#include <linux/module.h>
  12#include <linux/sbitmap.h>
  13
  14#include <trace/events/block.h>
  15
  16#include "elevator.h"
  17#include "blk.h"
  18#include "blk-mq.h"
  19#include "blk-mq-debugfs.h"
  20#include "blk-mq-sched.h"
  21
  22#define CREATE_TRACE_POINTS
  23#include <trace/events/kyber.h>
  24
  25/*
  26 * Scheduling domains: the device is divided into multiple domains based on the
  27 * request type.
  28 */
  29enum {
  30	KYBER_READ,
  31	KYBER_WRITE,
  32	KYBER_DISCARD,
  33	KYBER_OTHER,
  34	KYBER_NUM_DOMAINS,
  35};
  36
  37static const char *kyber_domain_names[] = {
  38	[KYBER_READ] = "READ",
  39	[KYBER_WRITE] = "WRITE",
  40	[KYBER_DISCARD] = "DISCARD",
  41	[KYBER_OTHER] = "OTHER",
  42};
  43
  44enum {
  45	/*
  46	 * In order to prevent starvation of synchronous requests by a flood of
  47	 * asynchronous requests, we reserve 25% of requests for synchronous
  48	 * operations.
  49	 */
  50	KYBER_ASYNC_PERCENT = 75,
  51};
  52
  53/*
  54 * Maximum device-wide depth for each scheduling domain.
  55 *
  56 * Even for fast devices with lots of tags like NVMe, you can saturate the
  57 * device with only a fraction of the maximum possible queue depth. So, we cap
  58 * these to a reasonable value.
  59 */
  60static const unsigned int kyber_depth[] = {
  61	[KYBER_READ] = 256,
  62	[KYBER_WRITE] = 128,
  63	[KYBER_DISCARD] = 64,
  64	[KYBER_OTHER] = 16,
  65};
  66
  67/*
  68 * Default latency targets for each scheduling domain.
  69 */
  70static const u64 kyber_latency_targets[] = {
  71	[KYBER_READ] = 2ULL * NSEC_PER_MSEC,
  72	[KYBER_WRITE] = 10ULL * NSEC_PER_MSEC,
  73	[KYBER_DISCARD] = 5ULL * NSEC_PER_SEC,
  74};
  75
  76/*
  77 * Batch size (number of requests we'll dispatch in a row) for each scheduling
  78 * domain.
  79 */
  80static const unsigned int kyber_batch_size[] = {
  81	[KYBER_READ] = 16,
  82	[KYBER_WRITE] = 8,
  83	[KYBER_DISCARD] = 1,
  84	[KYBER_OTHER] = 1,
  85};
  86
  87/*
  88 * Requests latencies are recorded in a histogram with buckets defined relative
  89 * to the target latency:
  90 *
  91 * <= 1/4 * target latency
  92 * <= 1/2 * target latency
  93 * <= 3/4 * target latency
  94 * <= target latency
  95 * <= 1 1/4 * target latency
  96 * <= 1 1/2 * target latency
  97 * <= 1 3/4 * target latency
  98 * > 1 3/4 * target latency
  99 */
 100enum {
 101	/*
 102	 * The width of the latency histogram buckets is
 103	 * 1 / (1 << KYBER_LATENCY_SHIFT) * target latency.
 104	 */
 105	KYBER_LATENCY_SHIFT = 2,
 106	/*
 107	 * The first (1 << KYBER_LATENCY_SHIFT) buckets are <= target latency,
 108	 * thus, "good".
 109	 */
 110	KYBER_GOOD_BUCKETS = 1 << KYBER_LATENCY_SHIFT,
 111	/* There are also (1 << KYBER_LATENCY_SHIFT) "bad" buckets. */
 112	KYBER_LATENCY_BUCKETS = 2 << KYBER_LATENCY_SHIFT,
 113};
 114
 115/*
 116 * We measure both the total latency and the I/O latency (i.e., latency after
 117 * submitting to the device).
 118 */
 119enum {
 120	KYBER_TOTAL_LATENCY,
 121	KYBER_IO_LATENCY,
 122};
 123
 124static const char *kyber_latency_type_names[] = {
 125	[KYBER_TOTAL_LATENCY] = "total",
 126	[KYBER_IO_LATENCY] = "I/O",
 127};
 128
 129/*
 130 * Per-cpu latency histograms: total latency and I/O latency for each scheduling
 131 * domain except for KYBER_OTHER.
 132 */
 133struct kyber_cpu_latency {
 134	atomic_t buckets[KYBER_OTHER][2][KYBER_LATENCY_BUCKETS];
 135};
 136
 137/*
 138 * There is a same mapping between ctx & hctx and kcq & khd,
 139 * we use request->mq_ctx->index_hw to index the kcq in khd.
 140 */
 141struct kyber_ctx_queue {
 142	/*
 143	 * Used to ensure operations on rq_list and kcq_map to be an atmoic one.
 144	 * Also protect the rqs on rq_list when merge.
 145	 */
 146	spinlock_t lock;
 147	struct list_head rq_list[KYBER_NUM_DOMAINS];
 148} ____cacheline_aligned_in_smp;
 149
 150struct kyber_queue_data {
 151	struct request_queue *q;
 152	dev_t dev;
 153
 154	/*
 155	 * Each scheduling domain has a limited number of in-flight requests
 156	 * device-wide, limited by these tokens.
 157	 */
 158	struct sbitmap_queue domain_tokens[KYBER_NUM_DOMAINS];
 159
 160	/* Number of allowed async requests. */
 161	unsigned int async_depth;
 162
 163	struct kyber_cpu_latency __percpu *cpu_latency;
 164
 165	/* Timer for stats aggregation and adjusting domain tokens. */
 166	struct timer_list timer;
 167
 168	unsigned int latency_buckets[KYBER_OTHER][2][KYBER_LATENCY_BUCKETS];
 169
 170	unsigned long latency_timeout[KYBER_OTHER];
 171
 172	int domain_p99[KYBER_OTHER];
 173
 174	/* Target latencies in nanoseconds. */
 175	u64 latency_targets[KYBER_OTHER];
 176};
 177
 178struct kyber_hctx_data {
 179	spinlock_t lock;
 180	struct list_head rqs[KYBER_NUM_DOMAINS];
 181	unsigned int cur_domain;
 182	unsigned int batching;
 183	struct kyber_ctx_queue *kcqs;
 184	struct sbitmap kcq_map[KYBER_NUM_DOMAINS];
 185	struct sbq_wait domain_wait[KYBER_NUM_DOMAINS];
 186	struct sbq_wait_state *domain_ws[KYBER_NUM_DOMAINS];
 187	atomic_t wait_index[KYBER_NUM_DOMAINS];
 188};
 189
 190static int kyber_domain_wake(wait_queue_entry_t *wait, unsigned mode, int flags,
 191			     void *key);
 192
 193static unsigned int kyber_sched_domain(blk_opf_t opf)
 194{
 195	switch (opf & REQ_OP_MASK) {
 196	case REQ_OP_READ:
 197		return KYBER_READ;
 198	case REQ_OP_WRITE:
 199		return KYBER_WRITE;
 200	case REQ_OP_DISCARD:
 201		return KYBER_DISCARD;
 202	default:
 203		return KYBER_OTHER;
 204	}
 205}
 206
 207static void flush_latency_buckets(struct kyber_queue_data *kqd,
 208				  struct kyber_cpu_latency *cpu_latency,
 209				  unsigned int sched_domain, unsigned int type)
 210{
 211	unsigned int *buckets = kqd->latency_buckets[sched_domain][type];
 212	atomic_t *cpu_buckets = cpu_latency->buckets[sched_domain][type];
 213	unsigned int bucket;
 214
 215	for (bucket = 0; bucket < KYBER_LATENCY_BUCKETS; bucket++)
 216		buckets[bucket] += atomic_xchg(&cpu_buckets[bucket], 0);
 217}
 218
 219/*
 220 * Calculate the histogram bucket with the given percentile rank, or -1 if there
 221 * aren't enough samples yet.
 222 */
 223static int calculate_percentile(struct kyber_queue_data *kqd,
 224				unsigned int sched_domain, unsigned int type,
 225				unsigned int percentile)
 226{
 227	unsigned int *buckets = kqd->latency_buckets[sched_domain][type];
 228	unsigned int bucket, samples = 0, percentile_samples;
 229
 230	for (bucket = 0; bucket < KYBER_LATENCY_BUCKETS; bucket++)
 231		samples += buckets[bucket];
 232
 233	if (!samples)
 234		return -1;
 235
 236	/*
 237	 * We do the calculation once we have 500 samples or one second passes
 238	 * since the first sample was recorded, whichever comes first.
 239	 */
 240	if (!kqd->latency_timeout[sched_domain])
 241		kqd->latency_timeout[sched_domain] = max(jiffies + HZ, 1UL);
 242	if (samples < 500 &&
 243	    time_is_after_jiffies(kqd->latency_timeout[sched_domain])) {
 244		return -1;
 245	}
 246	kqd->latency_timeout[sched_domain] = 0;
 247
 248	percentile_samples = DIV_ROUND_UP(samples * percentile, 100);
 249	for (bucket = 0; bucket < KYBER_LATENCY_BUCKETS - 1; bucket++) {
 250		if (buckets[bucket] >= percentile_samples)
 251			break;
 252		percentile_samples -= buckets[bucket];
 253	}
 254	memset(buckets, 0, sizeof(kqd->latency_buckets[sched_domain][type]));
 255
 256	trace_kyber_latency(kqd->dev, kyber_domain_names[sched_domain],
 257			    kyber_latency_type_names[type], percentile,
 258			    bucket + 1, 1 << KYBER_LATENCY_SHIFT, samples);
 259
 260	return bucket;
 261}
 262
 263static void kyber_resize_domain(struct kyber_queue_data *kqd,
 264				unsigned int sched_domain, unsigned int depth)
 265{
 266	depth = clamp(depth, 1U, kyber_depth[sched_domain]);
 267	if (depth != kqd->domain_tokens[sched_domain].sb.depth) {
 268		sbitmap_queue_resize(&kqd->domain_tokens[sched_domain], depth);
 269		trace_kyber_adjust(kqd->dev, kyber_domain_names[sched_domain],
 270				   depth);
 271	}
 272}
 273
 274static void kyber_timer_fn(struct timer_list *t)
 275{
 276	struct kyber_queue_data *kqd = timer_container_of(kqd, t, timer);
 277	unsigned int sched_domain;
 278	int cpu;
 279	bool bad = false;
 280
 281	/* Sum all of the per-cpu latency histograms. */
 282	for_each_online_cpu(cpu) {
 283		struct kyber_cpu_latency *cpu_latency;
 284
 285		cpu_latency = per_cpu_ptr(kqd->cpu_latency, cpu);
 286		for (sched_domain = 0; sched_domain < KYBER_OTHER; sched_domain++) {
 287			flush_latency_buckets(kqd, cpu_latency, sched_domain,
 288					      KYBER_TOTAL_LATENCY);
 289			flush_latency_buckets(kqd, cpu_latency, sched_domain,
 290					      KYBER_IO_LATENCY);
 291		}
 292	}
 293
 294	/*
 295	 * Check if any domains have a high I/O latency, which might indicate
 296	 * congestion in the device. Note that we use the p90; we don't want to
 297	 * be too sensitive to outliers here.
 298	 */
 299	for (sched_domain = 0; sched_domain < KYBER_OTHER; sched_domain++) {
 300		int p90;
 301
 302		p90 = calculate_percentile(kqd, sched_domain, KYBER_IO_LATENCY,
 303					   90);
 304		if (p90 >= KYBER_GOOD_BUCKETS)
 305			bad = true;
 306	}
 307
 308	/*
 309	 * Adjust the scheduling domain depths. If we determined that there was
 310	 * congestion, we throttle all domains with good latencies. Either way,
 311	 * we ease up on throttling domains with bad latencies.
 312	 */
 313	for (sched_domain = 0; sched_domain < KYBER_OTHER; sched_domain++) {
 314		unsigned int orig_depth, depth;
 315		int p99;
 316
 317		p99 = calculate_percentile(kqd, sched_domain,
 318					   KYBER_TOTAL_LATENCY, 99);
 319		/*
 320		 * This is kind of subtle: different domains will not
 321		 * necessarily have enough samples to calculate the latency
 322		 * percentiles during the same window, so we have to remember
 323		 * the p99 for the next time we observe congestion; once we do,
 324		 * we don't want to throttle again until we get more data, so we
 325		 * reset it to -1.
 326		 */
 327		if (bad) {
 328			if (p99 < 0)
 329				p99 = kqd->domain_p99[sched_domain];
 330			kqd->domain_p99[sched_domain] = -1;
 331		} else if (p99 >= 0) {
 332			kqd->domain_p99[sched_domain] = p99;
 333		}
 334		if (p99 < 0)
 335			continue;
 336
 337		/*
 338		 * If this domain has bad latency, throttle less. Otherwise,
 339		 * throttle more iff we determined that there is congestion.
 340		 *
 341		 * The new depth is scaled linearly with the p99 latency vs the
 342		 * latency target. E.g., if the p99 is 3/4 of the target, then
 343		 * we throttle down to 3/4 of the current depth, and if the p99
 344		 * is 2x the target, then we double the depth.
 345		 */
 346		if (bad || p99 >= KYBER_GOOD_BUCKETS) {
 347			orig_depth = kqd->domain_tokens[sched_domain].sb.depth;
 348			depth = (orig_depth * (p99 + 1)) >> KYBER_LATENCY_SHIFT;
 349			kyber_resize_domain(kqd, sched_domain, depth);
 350		}
 351	}
 352}
 353
 354static struct kyber_queue_data *kyber_queue_data_alloc(struct request_queue *q)
 355{
 356	struct kyber_queue_data *kqd;
 357	int ret = -ENOMEM;
 358	int i;
 359
 360	kqd = kzalloc_node(sizeof(*kqd), GFP_KERNEL, q->node);
 361	if (!kqd)
 362		goto err;
 363
 364	kqd->q = q;
 365	kqd->dev = disk_devt(q->disk);
 366
 367	kqd->cpu_latency = alloc_percpu_gfp(struct kyber_cpu_latency,
 368					    GFP_KERNEL | __GFP_ZERO);
 369	if (!kqd->cpu_latency)
 370		goto err_kqd;
 371
 372	timer_setup(&kqd->timer, kyber_timer_fn, 0);
 373
 374	for (i = 0; i < KYBER_NUM_DOMAINS; i++) {
 375		WARN_ON(!kyber_depth[i]);
 376		WARN_ON(!kyber_batch_size[i]);
 377		ret = sbitmap_queue_init_node(&kqd->domain_tokens[i],
 378					      kyber_depth[i], -1, false,
 379					      GFP_KERNEL, q->node);
 380		if (ret) {
 381			while (--i >= 0)
 382				sbitmap_queue_free(&kqd->domain_tokens[i]);
 383			goto err_buckets;
 384		}
 385	}
 386
 387	for (i = 0; i < KYBER_OTHER; i++) {
 388		kqd->domain_p99[i] = -1;
 389		kqd->latency_targets[i] = kyber_latency_targets[i];
 390	}
 391
 392	return kqd;
 393
 394err_buckets:
 395	free_percpu(kqd->cpu_latency);
 396err_kqd:
 397	kfree(kqd);
 398err:
 399	return ERR_PTR(ret);
 400}
 401
 402static void kyber_depth_updated(struct request_queue *q)
 403{
 404	struct kyber_queue_data *kqd = q->elevator->elevator_data;
 405
 406	kqd->async_depth = q->nr_requests * KYBER_ASYNC_PERCENT / 100U;
 407	blk_mq_set_min_shallow_depth(q, kqd->async_depth);
 408}
 409
 410static int kyber_init_sched(struct request_queue *q, struct elevator_queue *eq)
 411{
 412	blk_stat_enable_accounting(q);
 413
 414	blk_queue_flag_clear(QUEUE_FLAG_SQ_SCHED, q);
 415
 416	q->elevator = eq;
 417	kyber_depth_updated(q);
 418
 419	return 0;
 420}
 421
 422static void *kyber_alloc_sched_data(struct request_queue *q)
 423{
 424	struct kyber_queue_data *kqd;
 425
 426	kqd = kyber_queue_data_alloc(q);
 427	if (IS_ERR(kqd))
 428		return NULL;
 429
 430	return kqd;
 431}
 432
 433static void kyber_exit_sched(struct elevator_queue *e)
 434{
 435	struct kyber_queue_data *kqd = e->elevator_data;
 436
 437	timer_shutdown_sync(&kqd->timer);
 438	blk_stat_disable_accounting(kqd->q);
 439}
 440
 441static void kyber_free_sched_data(void *elv_data)
 442{
 443	struct kyber_queue_data *kqd = elv_data;
 444	int i;
 445
 446	if (!kqd)
 447		return;
 448
 449	for (i = 0; i < KYBER_NUM_DOMAINS; i++)
 450		sbitmap_queue_free(&kqd->domain_tokens[i]);
 451	free_percpu(kqd->cpu_latency);
 452	kfree(kqd);
 453}
 454
 455static void kyber_ctx_queue_init(struct kyber_ctx_queue *kcq)
 456{
 457	unsigned int i;
 458
 459	spin_lock_init(&kcq->lock);
 460	for (i = 0; i < KYBER_NUM_DOMAINS; i++)
 461		INIT_LIST_HEAD(&kcq->rq_list[i]);
 462}
 463
 464static int kyber_init_hctx(struct blk_mq_hw_ctx *hctx, unsigned int hctx_idx)
 465{
 466	struct kyber_hctx_data *khd;
 467	int i;
 468
 469	khd = kmalloc_node(sizeof(*khd), GFP_KERNEL, hctx->numa_node);
 470	if (!khd)
 471		return -ENOMEM;
 472
 473	khd->kcqs = kmalloc_array_node(hctx->nr_ctx,
 474				       sizeof(struct kyber_ctx_queue),
 475				       GFP_KERNEL, hctx->numa_node);
 476	if (!khd->kcqs)
 477		goto err_khd;
 478
 479	for (i = 0; i < hctx->nr_ctx; i++)
 480		kyber_ctx_queue_init(&khd->kcqs[i]);
 481
 482	for (i = 0; i < KYBER_NUM_DOMAINS; i++) {
 483		if (sbitmap_init_node(&khd->kcq_map[i], hctx->nr_ctx,
 484				      ilog2(8), GFP_KERNEL, hctx->numa_node,
 485				      false, false)) {
 486			while (--i >= 0)
 487				sbitmap_free(&khd->kcq_map[i]);
 488			goto err_kcqs;
 489		}
 490	}
 491
 492	spin_lock_init(&khd->lock);
 493
 494	for (i = 0; i < KYBER_NUM_DOMAINS; i++) {
 495		INIT_LIST_HEAD(&khd->rqs[i]);
 496		khd->domain_wait[i].sbq = NULL;
 497		init_waitqueue_func_entry(&khd->domain_wait[i].wait,
 498					  kyber_domain_wake);
 499		khd->domain_wait[i].wait.private = hctx;
 500		INIT_LIST_HEAD(&khd->domain_wait[i].wait.entry);
 501		atomic_set(&khd->wait_index[i], 0);
 502	}
 503
 504	khd->cur_domain = 0;
 505	khd->batching = 0;
 506
 507	hctx->sched_data = khd;
 508
 509	return 0;
 510
 511err_kcqs:
 512	kfree(khd->kcqs);
 513err_khd:
 514	kfree(khd);
 515	return -ENOMEM;
 516}
 517
 518static void kyber_exit_hctx(struct blk_mq_hw_ctx *hctx, unsigned int hctx_idx)
 519{
 520	struct kyber_hctx_data *khd = hctx->sched_data;
 521	int i;
 522
 523	for (i = 0; i < KYBER_NUM_DOMAINS; i++)
 524		sbitmap_free(&khd->kcq_map[i]);
 525	kfree(khd->kcqs);
 526	kfree(hctx->sched_data);
 527}
 528
 529static int rq_get_domain_token(struct request *rq)
 530{
 531	return (long)rq->elv.priv[0];
 532}
 533
 534static void rq_set_domain_token(struct request *rq, int token)
 535{
 536	rq->elv.priv[0] = (void *)(long)token;
 537}
 538
 539static void rq_clear_domain_token(struct kyber_queue_data *kqd,
 540				  struct request *rq)
 541{
 542	unsigned int sched_domain;
 543	int nr;
 544
 545	nr = rq_get_domain_token(rq);
 546	if (nr != -1) {
 547		sched_domain = kyber_sched_domain(rq->cmd_flags);
 548		sbitmap_queue_clear(&kqd->domain_tokens[sched_domain], nr,
 549				    rq->mq_ctx->cpu);
 550	}
 551}
 552
 553static void kyber_limit_depth(blk_opf_t opf, struct blk_mq_alloc_data *data)
 554{
 555	/*
 556	 * We use the scheduler tags as per-hardware queue queueing tokens.
 557	 * Async requests can be limited at this stage.
 558	 */
 559	if (!blk_mq_is_sync_read(opf)) {
 560		struct kyber_queue_data *kqd = data->q->elevator->elevator_data;
 561
 562		data->shallow_depth = kqd->async_depth;
 563	}
 564}
 565
 566static bool kyber_bio_merge(struct request_queue *q, struct bio *bio,
 567		unsigned int nr_segs)
 568{
 569	struct blk_mq_ctx *ctx = blk_mq_get_ctx(q);
 570	struct blk_mq_hw_ctx *hctx = blk_mq_map_queue(bio->bi_opf, ctx);
 571	struct kyber_hctx_data *khd = hctx->sched_data;
 572	struct kyber_ctx_queue *kcq = &khd->kcqs[ctx->index_hw[hctx->type]];
 573	unsigned int sched_domain = kyber_sched_domain(bio->bi_opf);
 574	struct list_head *rq_list = &kcq->rq_list[sched_domain];
 575	bool merged;
 576
 577	spin_lock(&kcq->lock);
 578	merged = blk_bio_list_merge(hctx->queue, rq_list, bio, nr_segs);
 579	spin_unlock(&kcq->lock);
 580
 581	return merged;
 582}
 583
 584static void kyber_prepare_request(struct request *rq)
 585{
 586	rq_set_domain_token(rq, -1);
 587}
 588
 589static void kyber_insert_requests(struct blk_mq_hw_ctx *hctx,
 590				  struct list_head *rq_list,
 591				  blk_insert_t flags)
 592{
 593	struct kyber_hctx_data *khd = hctx->sched_data;
 594	struct request *rq, *next;
 595
 596	list_for_each_entry_safe(rq, next, rq_list, queuelist) {
 597		unsigned int sched_domain = kyber_sched_domain(rq->cmd_flags);
 598		struct kyber_ctx_queue *kcq = &khd->kcqs[rq->mq_ctx->index_hw[hctx->type]];
 599		struct list_head *head = &kcq->rq_list[sched_domain];
 600
 601		spin_lock(&kcq->lock);
 602		trace_block_rq_insert(rq);
 603		if (flags & BLK_MQ_INSERT_AT_HEAD)
 604			list_move(&rq->queuelist, head);
 605		else
 606			list_move_tail(&rq->queuelist, head);
 607		sbitmap_set_bit(&khd->kcq_map[sched_domain],
 608				rq->mq_ctx->index_hw[hctx->type]);
 609		spin_unlock(&kcq->lock);
 610	}
 611}
 612
 613static void kyber_finish_request(struct request *rq)
 614{
 615	struct kyber_queue_data *kqd = rq->q->elevator->elevator_data;
 616
 617	rq_clear_domain_token(kqd, rq);
 618}
 619
 620static void add_latency_sample(struct kyber_cpu_latency *cpu_latency,
 621			       unsigned int sched_domain, unsigned int type,
 622			       u64 target, u64 latency)
 623{
 624	unsigned int bucket;
 625	u64 divisor;
 626
 627	if (latency > 0) {
 628		divisor = max_t(u64, target >> KYBER_LATENCY_SHIFT, 1);
 629		bucket = min_t(unsigned int, div64_u64(latency - 1, divisor),
 630			       KYBER_LATENCY_BUCKETS - 1);
 631	} else {
 632		bucket = 0;
 633	}
 634
 635	atomic_inc(&cpu_latency->buckets[sched_domain][type][bucket]);
 636}
 637
 638static void kyber_completed_request(struct request *rq, u64 now)
 639{
 640	struct kyber_queue_data *kqd = rq->q->elevator->elevator_data;
 641	struct kyber_cpu_latency *cpu_latency;
 642	unsigned int sched_domain;
 643	u64 target;
 644
 645	sched_domain = kyber_sched_domain(rq->cmd_flags);
 646	if (sched_domain == KYBER_OTHER)
 647		return;
 648
 649	cpu_latency = get_cpu_ptr(kqd->cpu_latency);
 650	target = kqd->latency_targets[sched_domain];
 651	add_latency_sample(cpu_latency, sched_domain, KYBER_TOTAL_LATENCY,
 652			   target, now - rq->start_time_ns);
 653	add_latency_sample(cpu_latency, sched_domain, KYBER_IO_LATENCY, target,
 654			   now - rq->io_start_time_ns);
 655	put_cpu_ptr(kqd->cpu_latency);
 656
 657	timer_reduce(&kqd->timer, jiffies + HZ / 10);
 658}
 659
 660struct flush_kcq_data {
 661	struct kyber_hctx_data *khd;
 662	unsigned int sched_domain;
 663	struct list_head *list;
 664};
 665
 666static bool flush_busy_kcq(struct sbitmap *sb, unsigned int bitnr, void *data)
 667{
 668	struct flush_kcq_data *flush_data = data;
 669	struct kyber_ctx_queue *kcq = &flush_data->khd->kcqs[bitnr];
 670
 671	spin_lock(&kcq->lock);
 672	list_splice_tail_init(&kcq->rq_list[flush_data->sched_domain],
 673			      flush_data->list);
 674	sbitmap_clear_bit(sb, bitnr);
 675	spin_unlock(&kcq->lock);
 676
 677	return true;
 678}
 679
 680static void kyber_flush_busy_kcqs(struct kyber_hctx_data *khd,
 681				  unsigned int sched_domain,
 682				  struct list_head *list)
 683{
 684	struct flush_kcq_data data = {
 685		.khd = khd,
 686		.sched_domain = sched_domain,
 687		.list = list,
 688	};
 689
 690	sbitmap_for_each_set(&khd->kcq_map[sched_domain],
 691			     flush_busy_kcq, &data);
 692}
 693
 694static int kyber_domain_wake(wait_queue_entry_t *wqe, unsigned mode, int flags,
 695			     void *key)
 696{
 697	struct blk_mq_hw_ctx *hctx = READ_ONCE(wqe->private);
 698	struct sbq_wait *wait = container_of(wqe, struct sbq_wait, wait);
 699
 700	sbitmap_del_wait_queue(wait);
 701	blk_mq_run_hw_queue(hctx, true);
 702	return 1;
 703}
 704
 705static int kyber_get_domain_token(struct kyber_queue_data *kqd,
 706				  struct kyber_hctx_data *khd,
 707				  struct blk_mq_hw_ctx *hctx)
 708{
 709	unsigned int sched_domain = khd->cur_domain;
 710	struct sbitmap_queue *domain_tokens = &kqd->domain_tokens[sched_domain];
 711	struct sbq_wait *wait = &khd->domain_wait[sched_domain];
 712	struct sbq_wait_state *ws;
 713	int nr;
 714
 715	nr = __sbitmap_queue_get(domain_tokens);
 716
 717	/*
 718	 * If we failed to get a domain token, make sure the hardware queue is
 719	 * run when one becomes available. Note that this is serialized on
 720	 * khd->lock, but we still need to be careful about the waker.
 721	 */
 722	if (nr < 0 && list_empty_careful(&wait->wait.entry)) {
 723		ws = sbq_wait_ptr(domain_tokens,
 724				  &khd->wait_index[sched_domain]);
 725		khd->domain_ws[sched_domain] = ws;
 726		sbitmap_add_wait_queue(domain_tokens, ws, wait);
 727
 728		/*
 729		 * Try again in case a token was freed before we got on the wait
 730		 * queue.
 731		 */
 732		nr = __sbitmap_queue_get(domain_tokens);
 733	}
 734
 735	/*
 736	 * If we got a token while we were on the wait queue, remove ourselves
 737	 * from the wait queue to ensure that all wake ups make forward
 738	 * progress. It's possible that the waker already deleted the entry
 739	 * between the !list_empty_careful() check and us grabbing the lock, but
 740	 * list_del_init() is okay with that.
 741	 */
 742	if (nr >= 0 && !list_empty_careful(&wait->wait.entry)) {
 743		ws = khd->domain_ws[sched_domain];
 744		spin_lock_irq(&ws->wait.lock);
 745		sbitmap_del_wait_queue(wait);
 746		spin_unlock_irq(&ws->wait.lock);
 747	}
 748
 749	return nr;
 750}
 751
 752static struct request *
 753kyber_dispatch_cur_domain(struct kyber_queue_data *kqd,
 754			  struct kyber_hctx_data *khd,
 755			  struct blk_mq_hw_ctx *hctx)
 756{
 757	struct list_head *rqs;
 758	struct request *rq;
 759	int nr;
 760
 761	rqs = &khd->rqs[khd->cur_domain];
 762
 763	/*
 764	 * If we already have a flushed request, then we just need to get a
 765	 * token for it. Otherwise, if there are pending requests in the kcqs,
 766	 * flush the kcqs, but only if we can get a token. If not, we should
 767	 * leave the requests in the kcqs so that they can be merged. Note that
 768	 * khd->lock serializes the flushes, so if we observed any bit set in
 769	 * the kcq_map, we will always get a request.
 770	 */
 771	rq = list_first_entry_or_null(rqs, struct request, queuelist);
 772	if (rq) {
 773		nr = kyber_get_domain_token(kqd, khd, hctx);
 774		if (nr >= 0) {
 775			khd->batching++;
 776			rq_set_domain_token(rq, nr);
 777			list_del_init(&rq->queuelist);
 778			return rq;
 779		} else {
 780			trace_kyber_throttled(kqd->dev,
 781					      kyber_domain_names[khd->cur_domain]);
 782		}
 783	} else if (sbitmap_any_bit_set(&khd->kcq_map[khd->cur_domain])) {
 784		nr = kyber_get_domain_token(kqd, khd, hctx);
 785		if (nr >= 0) {
 786			kyber_flush_busy_kcqs(khd, khd->cur_domain, rqs);
 787			rq = list_first_entry(rqs, struct request, queuelist);
 788			khd->batching++;
 789			rq_set_domain_token(rq, nr);
 790			list_del_init(&rq->queuelist);
 791			return rq;
 792		} else {
 793			trace_kyber_throttled(kqd->dev,
 794					      kyber_domain_names[khd->cur_domain]);
 795		}
 796	}
 797
 798	/* There were either no pending requests or no tokens. */
 799	return NULL;
 800}
 801
 802static struct request *kyber_dispatch_request(struct blk_mq_hw_ctx *hctx)
 803{
 804	struct kyber_queue_data *kqd = hctx->queue->elevator->elevator_data;
 805	struct kyber_hctx_data *khd = hctx->sched_data;
 806	struct request *rq;
 807	int i;
 808
 809	spin_lock(&khd->lock);
 810
 811	/*
 812	 * First, if we are still entitled to batch, try to dispatch a request
 813	 * from the batch.
 814	 */
 815	if (khd->batching < kyber_batch_size[khd->cur_domain]) {
 816		rq = kyber_dispatch_cur_domain(kqd, khd, hctx);
 817		if (rq)
 818			goto out;
 819	}
 820
 821	/*
 822	 * Either,
 823	 * 1. We were no longer entitled to a batch.
 824	 * 2. The domain we were batching didn't have any requests.
 825	 * 3. The domain we were batching was out of tokens.
 826	 *
 827	 * Start another batch. Note that this wraps back around to the original
 828	 * domain if no other domains have requests or tokens.
 829	 */
 830	khd->batching = 0;
 831	for (i = 0; i < KYBER_NUM_DOMAINS; i++) {
 832		if (khd->cur_domain == KYBER_NUM_DOMAINS - 1)
 833			khd->cur_domain = 0;
 834		else
 835			khd->cur_domain++;
 836
 837		rq = kyber_dispatch_cur_domain(kqd, khd, hctx);
 838		if (rq)
 839			goto out;
 840	}
 841
 842	rq = NULL;
 843out:
 844	spin_unlock(&khd->lock);
 845	return rq;
 846}
 847
 848static bool kyber_has_work(struct blk_mq_hw_ctx *hctx)
 849{
 850	struct kyber_hctx_data *khd = hctx->sched_data;
 851	int i;
 852
 853	for (i = 0; i < KYBER_NUM_DOMAINS; i++) {
 854		if (!list_empty_careful(&khd->rqs[i]) ||
 855		    sbitmap_any_bit_set(&khd->kcq_map[i]))
 856			return true;
 857	}
 858
 859	return false;
 860}
 861
 862#define KYBER_LAT_SHOW_STORE(domain, name)				\
 863static ssize_t kyber_##name##_lat_show(struct elevator_queue *e,	\
 864				       char *page)			\
 865{									\
 866	struct kyber_queue_data *kqd = e->elevator_data;		\
 867									\
 868	return sprintf(page, "%llu\n", kqd->latency_targets[domain]);	\
 869}									\
 870									\
 871static ssize_t kyber_##name##_lat_store(struct elevator_queue *e,	\
 872					const char *page, size_t count)	\
 873{									\
 874	struct kyber_queue_data *kqd = e->elevator_data;		\
 875	unsigned long long nsec;					\
 876	int ret;							\
 877									\
 878	ret = kstrtoull(page, 10, &nsec);				\
 879	if (ret)							\
 880		return ret;						\
 881									\
 882	kqd->latency_targets[domain] = nsec;				\
 883									\
 884	return count;							\
 885}
 886KYBER_LAT_SHOW_STORE(KYBER_READ, read);
 887KYBER_LAT_SHOW_STORE(KYBER_WRITE, write);
 888#undef KYBER_LAT_SHOW_STORE
 889
 890#define KYBER_LAT_ATTR(op) __ATTR(op##_lat_nsec, 0644, kyber_##op##_lat_show, kyber_##op##_lat_store)
 891static const struct elv_fs_entry kyber_sched_attrs[] = {
 892	KYBER_LAT_ATTR(read),
 893	KYBER_LAT_ATTR(write),
 894	__ATTR_NULL
 895};
 896#undef KYBER_LAT_ATTR
 897
 898#ifdef CONFIG_BLK_DEBUG_FS
 899#define KYBER_DEBUGFS_DOMAIN_ATTRS(domain, name)			\
 900static int kyber_##name##_tokens_show(void *data, struct seq_file *m)	\
 901{									\
 902	struct request_queue *q = data;					\
 903	struct kyber_queue_data *kqd = q->elevator->elevator_data;	\
 904									\
 905	sbitmap_queue_show(&kqd->domain_tokens[domain], m);		\
 906	return 0;							\
 907}									\
 908									\
 909static void *kyber_##name##_rqs_start(struct seq_file *m, loff_t *pos)	\
 910	__acquires(&khd->lock)						\
 911{									\
 912	struct blk_mq_hw_ctx *hctx = m->private;			\
 913	struct kyber_hctx_data *khd = hctx->sched_data;			\
 914									\
 915	spin_lock(&khd->lock);						\
 916	return seq_list_start(&khd->rqs[domain], *pos);			\
 917}									\
 918									\
 919static void *kyber_##name##_rqs_next(struct seq_file *m, void *v,	\
 920				     loff_t *pos)			\
 921{									\
 922	struct blk_mq_hw_ctx *hctx = m->private;			\
 923	struct kyber_hctx_data *khd = hctx->sched_data;			\
 924									\
 925	return seq_list_next(v, &khd->rqs[domain], pos);		\
 926}									\
 927									\
 928static void kyber_##name##_rqs_stop(struct seq_file *m, void *v)	\
 929	__releases(&khd->lock)						\
 930{									\
 931	struct blk_mq_hw_ctx *hctx = m->private;			\
 932	struct kyber_hctx_data *khd = hctx->sched_data;			\
 933									\
 934	spin_unlock(&khd->lock);					\
 935}									\
 936									\
 937static const struct seq_operations kyber_##name##_rqs_seq_ops = {	\
 938	.start	= kyber_##name##_rqs_start,				\
 939	.next	= kyber_##name##_rqs_next,				\
 940	.stop	= kyber_##name##_rqs_stop,				\
 941	.show	= blk_mq_debugfs_rq_show,				\
 942};									\
 943									\
 944static int kyber_##name##_waiting_show(void *data, struct seq_file *m)	\
 945{									\
 946	struct blk_mq_hw_ctx *hctx = data;				\
 947	struct kyber_hctx_data *khd = hctx->sched_data;			\
 948	wait_queue_entry_t *wait = &khd->domain_wait[domain].wait;	\
 949									\
 950	seq_printf(m, "%d\n", !list_empty_careful(&wait->entry));	\
 951	return 0;							\
 952}
 953KYBER_DEBUGFS_DOMAIN_ATTRS(KYBER_READ, read)
 954KYBER_DEBUGFS_DOMAIN_ATTRS(KYBER_WRITE, write)
 955KYBER_DEBUGFS_DOMAIN_ATTRS(KYBER_DISCARD, discard)
 956KYBER_DEBUGFS_DOMAIN_ATTRS(KYBER_OTHER, other)
 957#undef KYBER_DEBUGFS_DOMAIN_ATTRS
 958
 959static int kyber_async_depth_show(void *data, struct seq_file *m)
 960{
 961	struct request_queue *q = data;
 962	struct kyber_queue_data *kqd = q->elevator->elevator_data;
 963
 964	seq_printf(m, "%u\n", kqd->async_depth);
 965	return 0;
 966}
 967
 968static int kyber_cur_domain_show(void *data, struct seq_file *m)
 969{
 970	struct blk_mq_hw_ctx *hctx = data;
 971	struct kyber_hctx_data *khd = hctx->sched_data;
 972
 973	seq_printf(m, "%s\n", kyber_domain_names[khd->cur_domain]);
 974	return 0;
 975}
 976
 977static int kyber_batching_show(void *data, struct seq_file *m)
 978{
 979	struct blk_mq_hw_ctx *hctx = data;
 980	struct kyber_hctx_data *khd = hctx->sched_data;
 981
 982	seq_printf(m, "%u\n", khd->batching);
 983	return 0;
 984}
 985
 986#define KYBER_QUEUE_DOMAIN_ATTRS(name)	\
 987	{#name "_tokens", 0400, kyber_##name##_tokens_show}
 988static const struct blk_mq_debugfs_attr kyber_queue_debugfs_attrs[] = {
 989	KYBER_QUEUE_DOMAIN_ATTRS(read),
 990	KYBER_QUEUE_DOMAIN_ATTRS(write),
 991	KYBER_QUEUE_DOMAIN_ATTRS(discard),
 992	KYBER_QUEUE_DOMAIN_ATTRS(other),
 993	{"async_depth", 0400, kyber_async_depth_show},
 994	{},
 995};
 996#undef KYBER_QUEUE_DOMAIN_ATTRS
 997
 998#define KYBER_HCTX_DOMAIN_ATTRS(name)					\
 999	{#name "_rqs", 0400, .seq_ops = &kyber_##name##_rqs_seq_ops},	\
1000	{#name "_waiting", 0400, kyber_##name##_waiting_show}
1001static const struct blk_mq_debugfs_attr kyber_hctx_debugfs_attrs[] = {
1002	KYBER_HCTX_DOMAIN_ATTRS(read),
1003	KYBER_HCTX_DOMAIN_ATTRS(write),
1004	KYBER_HCTX_DOMAIN_ATTRS(discard),
1005	KYBER_HCTX_DOMAIN_ATTRS(other),
1006	{"cur_domain", 0400, kyber_cur_domain_show},
1007	{"batching", 0400, kyber_batching_show},
1008	{},
1009};
1010#undef KYBER_HCTX_DOMAIN_ATTRS
1011#endif
1012
1013static struct elevator_type kyber_sched = {
1014	.ops = {
1015		.init_sched = kyber_init_sched,
1016		.exit_sched = kyber_exit_sched,
1017		.init_hctx = kyber_init_hctx,
1018		.exit_hctx = kyber_exit_hctx,
1019		.alloc_sched_data = kyber_alloc_sched_data,
1020		.free_sched_data = kyber_free_sched_data,
1021		.limit_depth = kyber_limit_depth,
1022		.bio_merge = kyber_bio_merge,
1023		.prepare_request = kyber_prepare_request,
1024		.insert_requests = kyber_insert_requests,
1025		.finish_request = kyber_finish_request,
1026		.requeue_request = kyber_finish_request,
1027		.completed_request = kyber_completed_request,
1028		.dispatch_request = kyber_dispatch_request,
1029		.has_work = kyber_has_work,
1030		.depth_updated = kyber_depth_updated,
1031	},
1032#ifdef CONFIG_BLK_DEBUG_FS
1033	.queue_debugfs_attrs = kyber_queue_debugfs_attrs,
1034	.hctx_debugfs_attrs = kyber_hctx_debugfs_attrs,
1035#endif
1036	.elevator_attrs = kyber_sched_attrs,
1037	.elevator_name = "kyber",
1038	.elevator_owner = THIS_MODULE,
1039};
1040
1041static int __init kyber_init(void)
1042{
1043	return elv_register(&kyber_sched);
1044}
1045
1046static void __exit kyber_exit(void)
1047{
1048	elv_unregister(&kyber_sched);
1049}
1050
1051module_init(kyber_init);
1052module_exit(kyber_exit);
1053
1054MODULE_AUTHOR("Omar Sandoval");
1055MODULE_LICENSE("GPL");
1056MODULE_DESCRIPTION("Kyber I/O scheduler");