xref: /openbmc/linux/block/bfq-iosched.h (revision 4da722ca)
1 /*
2  * Header file for the BFQ I/O scheduler: data structures and
3  * prototypes of interface functions among BFQ components.
4  *
5  *  This program is free software; you can redistribute it and/or
6  *  modify it under the terms of the GNU General Public License as
7  *  published by the Free Software Foundation; either version 2 of the
8  *  License, or (at your option) any later version.
9  *
10  *  This program is distributed in the hope that it will be useful,
11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13  *  General Public License for more details.
14  */
15 #ifndef _BFQ_H
16 #define _BFQ_H
17 
18 #include <linux/blktrace_api.h>
19 #include <linux/hrtimer.h>
20 #include <linux/blk-cgroup.h>
21 
22 #define BFQ_IOPRIO_CLASSES	3
23 #define BFQ_CL_IDLE_TIMEOUT	(HZ/5)
24 
25 #define BFQ_MIN_WEIGHT			1
26 #define BFQ_MAX_WEIGHT			1000
27 #define BFQ_WEIGHT_CONVERSION_COEFF	10
28 
29 #define BFQ_DEFAULT_QUEUE_IOPRIO	4
30 
31 #define BFQ_WEIGHT_LEGACY_DFL	100
32 #define BFQ_DEFAULT_GRP_IOPRIO	0
33 #define BFQ_DEFAULT_GRP_CLASS	IOPRIO_CLASS_BE
34 
35 /*
36  * Soft real-time applications are extremely more latency sensitive
37  * than interactive ones. Over-raise the weight of the former to
38  * privilege them against the latter.
39  */
40 #define BFQ_SOFTRT_WEIGHT_FACTOR	100
41 
42 struct bfq_entity;
43 
44 /**
45  * struct bfq_service_tree - per ioprio_class service tree.
46  *
47  * Each service tree represents a B-WF2Q+ scheduler on its own.  Each
48  * ioprio_class has its own independent scheduler, and so its own
49  * bfq_service_tree.  All the fields are protected by the queue lock
50  * of the containing bfqd.
51  */
52 struct bfq_service_tree {
53 	/* tree for active entities (i.e., those backlogged) */
54 	struct rb_root active;
55 	/* tree for idle entities (i.e., not backlogged, with V <= F_i)*/
56 	struct rb_root idle;
57 
58 	/* idle entity with minimum F_i */
59 	struct bfq_entity *first_idle;
60 	/* idle entity with maximum F_i */
61 	struct bfq_entity *last_idle;
62 
63 	/* scheduler virtual time */
64 	u64 vtime;
65 	/* scheduler weight sum; active and idle entities contribute to it */
66 	unsigned long wsum;
67 };
68 
69 /**
70  * struct bfq_sched_data - multi-class scheduler.
71  *
72  * bfq_sched_data is the basic scheduler queue.  It supports three
73  * ioprio_classes, and can be used either as a toplevel queue or as an
74  * intermediate queue on a hierarchical setup.  @next_in_service
75  * points to the active entity of the sched_data service trees that
76  * will be scheduled next. It is used to reduce the number of steps
77  * needed for each hierarchical-schedule update.
78  *
79  * The supported ioprio_classes are the same as in CFQ, in descending
80  * priority order, IOPRIO_CLASS_RT, IOPRIO_CLASS_BE, IOPRIO_CLASS_IDLE.
81  * Requests from higher priority queues are served before all the
82  * requests from lower priority queues; among requests of the same
83  * queue requests are served according to B-WF2Q+.
84  * All the fields are protected by the queue lock of the containing bfqd.
85  */
86 struct bfq_sched_data {
87 	/* entity in service */
88 	struct bfq_entity *in_service_entity;
89 	/* head-of-line entity (see comments above) */
90 	struct bfq_entity *next_in_service;
91 	/* array of service trees, one per ioprio_class */
92 	struct bfq_service_tree service_tree[BFQ_IOPRIO_CLASSES];
93 	/* last time CLASS_IDLE was served */
94 	unsigned long bfq_class_idle_last_service;
95 
96 };
97 
98 /**
99  * struct bfq_weight_counter - counter of the number of all active entities
100  *                             with a given weight.
101  */
102 struct bfq_weight_counter {
103 	unsigned int weight; /* weight of the entities this counter refers to */
104 	unsigned int num_active; /* nr of active entities with this weight */
105 	/*
106 	 * Weights tree member (see bfq_data's @queue_weights_tree and
107 	 * @group_weights_tree)
108 	 */
109 	struct rb_node weights_node;
110 };
111 
112 /**
113  * struct bfq_entity - schedulable entity.
114  *
115  * A bfq_entity is used to represent either a bfq_queue (leaf node in the
116  * cgroup hierarchy) or a bfq_group into the upper level scheduler.  Each
117  * entity belongs to the sched_data of the parent group in the cgroup
118  * hierarchy.  Non-leaf entities have also their own sched_data, stored
119  * in @my_sched_data.
120  *
121  * Each entity stores independently its priority values; this would
122  * allow different weights on different devices, but this
123  * functionality is not exported to userspace by now.  Priorities and
124  * weights are updated lazily, first storing the new values into the
125  * new_* fields, then setting the @prio_changed flag.  As soon as
126  * there is a transition in the entity state that allows the priority
127  * update to take place the effective and the requested priority
128  * values are synchronized.
129  *
130  * Unless cgroups are used, the weight value is calculated from the
131  * ioprio to export the same interface as CFQ.  When dealing with
132  * ``well-behaved'' queues (i.e., queues that do not spend too much
133  * time to consume their budget and have true sequential behavior, and
134  * when there are no external factors breaking anticipation) the
135  * relative weights at each level of the cgroups hierarchy should be
136  * guaranteed.  All the fields are protected by the queue lock of the
137  * containing bfqd.
138  */
139 struct bfq_entity {
140 	/* service_tree member */
141 	struct rb_node rb_node;
142 	/* pointer to the weight counter associated with this entity */
143 	struct bfq_weight_counter *weight_counter;
144 
145 	/*
146 	 * Flag, true if the entity is on a tree (either the active or
147 	 * the idle one of its service_tree) or is in service.
148 	 */
149 	bool on_st;
150 
151 	/* B-WF2Q+ start and finish timestamps [sectors/weight] */
152 	u64 start, finish;
153 
154 	/* tree the entity is enqueued into; %NULL if not on a tree */
155 	struct rb_root *tree;
156 
157 	/*
158 	 * minimum start time of the (active) subtree rooted at this
159 	 * entity; used for O(log N) lookups into active trees
160 	 */
161 	u64 min_start;
162 
163 	/* amount of service received during the last service slot */
164 	int service;
165 
166 	/* budget, used also to calculate F_i: F_i = S_i + @budget / @weight */
167 	int budget;
168 
169 	/* weight of the queue */
170 	int weight;
171 	/* next weight if a change is in progress */
172 	int new_weight;
173 
174 	/* original weight, used to implement weight boosting */
175 	int orig_weight;
176 
177 	/* parent entity, for hierarchical scheduling */
178 	struct bfq_entity *parent;
179 
180 	/*
181 	 * For non-leaf nodes in the hierarchy, the associated
182 	 * scheduler queue, %NULL on leaf nodes.
183 	 */
184 	struct bfq_sched_data *my_sched_data;
185 	/* the scheduler queue this entity belongs to */
186 	struct bfq_sched_data *sched_data;
187 
188 	/* flag, set to request a weight, ioprio or ioprio_class change  */
189 	int prio_changed;
190 };
191 
192 struct bfq_group;
193 
194 /**
195  * struct bfq_ttime - per process thinktime stats.
196  */
197 struct bfq_ttime {
198 	/* completion time of the last request */
199 	u64 last_end_request;
200 
201 	/* total process thinktime */
202 	u64 ttime_total;
203 	/* number of thinktime samples */
204 	unsigned long ttime_samples;
205 	/* average process thinktime */
206 	u64 ttime_mean;
207 };
208 
209 /**
210  * struct bfq_queue - leaf schedulable entity.
211  *
212  * A bfq_queue is a leaf request queue; it can be associated with an
213  * io_context or more, if it  is  async or shared  between  cooperating
214  * processes. @cgroup holds a reference to the cgroup, to be sure that it
215  * does not disappear while a bfqq still references it (mostly to avoid
216  * races between request issuing and task migration followed by cgroup
217  * destruction).
218  * All the fields are protected by the queue lock of the containing bfqd.
219  */
220 struct bfq_queue {
221 	/* reference counter */
222 	int ref;
223 	/* parent bfq_data */
224 	struct bfq_data *bfqd;
225 
226 	/* current ioprio and ioprio class */
227 	unsigned short ioprio, ioprio_class;
228 	/* next ioprio and ioprio class if a change is in progress */
229 	unsigned short new_ioprio, new_ioprio_class;
230 
231 	/*
232 	 * Shared bfq_queue if queue is cooperating with one or more
233 	 * other queues.
234 	 */
235 	struct bfq_queue *new_bfqq;
236 	/* request-position tree member (see bfq_group's @rq_pos_tree) */
237 	struct rb_node pos_node;
238 	/* request-position tree root (see bfq_group's @rq_pos_tree) */
239 	struct rb_root *pos_root;
240 
241 	/* sorted list of pending requests */
242 	struct rb_root sort_list;
243 	/* if fifo isn't expired, next request to serve */
244 	struct request *next_rq;
245 	/* number of sync and async requests queued */
246 	int queued[2];
247 	/* number of requests currently allocated */
248 	int allocated;
249 	/* number of pending metadata requests */
250 	int meta_pending;
251 	/* fifo list of requests in sort_list */
252 	struct list_head fifo;
253 
254 	/* entity representing this queue in the scheduler */
255 	struct bfq_entity entity;
256 
257 	/* maximum budget allowed from the feedback mechanism */
258 	int max_budget;
259 	/* budget expiration (in jiffies) */
260 	unsigned long budget_timeout;
261 
262 	/* number of requests on the dispatch list or inside driver */
263 	int dispatched;
264 
265 	/* status flags */
266 	unsigned long flags;
267 
268 	/* node for active/idle bfqq list inside parent bfqd */
269 	struct list_head bfqq_list;
270 
271 	/* associated @bfq_ttime struct */
272 	struct bfq_ttime ttime;
273 
274 	/* bit vector: a 1 for each seeky requests in history */
275 	u32 seek_history;
276 
277 	/* node for the device's burst list */
278 	struct hlist_node burst_list_node;
279 
280 	/* position of the last request enqueued */
281 	sector_t last_request_pos;
282 
283 	/* Number of consecutive pairs of request completion and
284 	 * arrival, such that the queue becomes idle after the
285 	 * completion, but the next request arrives within an idle
286 	 * time slice; used only if the queue's IO_bound flag has been
287 	 * cleared.
288 	 */
289 	unsigned int requests_within_timer;
290 
291 	/* pid of the process owning the queue, used for logging purposes */
292 	pid_t pid;
293 
294 	/*
295 	 * Pointer to the bfq_io_cq owning the bfq_queue, set to %NULL
296 	 * if the queue is shared.
297 	 */
298 	struct bfq_io_cq *bic;
299 
300 	/* current maximum weight-raising time for this queue */
301 	unsigned long wr_cur_max_time;
302 	/*
303 	 * Minimum time instant such that, only if a new request is
304 	 * enqueued after this time instant in an idle @bfq_queue with
305 	 * no outstanding requests, then the task associated with the
306 	 * queue it is deemed as soft real-time (see the comments on
307 	 * the function bfq_bfqq_softrt_next_start())
308 	 */
309 	unsigned long soft_rt_next_start;
310 	/*
311 	 * Start time of the current weight-raising period if
312 	 * the @bfq-queue is being weight-raised, otherwise
313 	 * finish time of the last weight-raising period.
314 	 */
315 	unsigned long last_wr_start_finish;
316 	/* factor by which the weight of this queue is multiplied */
317 	unsigned int wr_coeff;
318 	/*
319 	 * Time of the last transition of the @bfq_queue from idle to
320 	 * backlogged.
321 	 */
322 	unsigned long last_idle_bklogged;
323 	/*
324 	 * Cumulative service received from the @bfq_queue since the
325 	 * last transition from idle to backlogged.
326 	 */
327 	unsigned long service_from_backlogged;
328 
329 	/*
330 	 * Value of wr start time when switching to soft rt
331 	 */
332 	unsigned long wr_start_at_switch_to_srt;
333 
334 	unsigned long split_time; /* time of last split */
335 };
336 
337 /**
338  * struct bfq_io_cq - per (request_queue, io_context) structure.
339  */
340 struct bfq_io_cq {
341 	/* associated io_cq structure */
342 	struct io_cq icq; /* must be the first member */
343 	/* array of two process queues, the sync and the async */
344 	struct bfq_queue *bfqq[2];
345 	/* per (request_queue, blkcg) ioprio */
346 	int ioprio;
347 #ifdef CONFIG_BFQ_GROUP_IOSCHED
348 	uint64_t blkcg_serial_nr; /* the current blkcg serial */
349 #endif
350 	/*
351 	 * Snapshot of the idle window before merging; taken to
352 	 * remember this value while the queue is merged, so as to be
353 	 * able to restore it in case of split.
354 	 */
355 	bool saved_idle_window;
356 	/*
357 	 * Same purpose as the previous two fields for the I/O bound
358 	 * classification of a queue.
359 	 */
360 	bool saved_IO_bound;
361 
362 	/*
363 	 * Same purpose as the previous fields for the value of the
364 	 * field keeping the queue's belonging to a large burst
365 	 */
366 	bool saved_in_large_burst;
367 	/*
368 	 * True if the queue belonged to a burst list before its merge
369 	 * with another cooperating queue.
370 	 */
371 	bool was_in_burst_list;
372 
373 	/*
374 	 * Similar to previous fields: save wr information.
375 	 */
376 	unsigned long saved_wr_coeff;
377 	unsigned long saved_last_wr_start_finish;
378 	unsigned long saved_wr_start_at_switch_to_srt;
379 	unsigned int saved_wr_cur_max_time;
380 	struct bfq_ttime saved_ttime;
381 };
382 
383 enum bfq_device_speed {
384 	BFQ_BFQD_FAST,
385 	BFQ_BFQD_SLOW,
386 };
387 
388 /**
389  * struct bfq_data - per-device data structure.
390  *
391  * All the fields are protected by @lock.
392  */
393 struct bfq_data {
394 	/* device request queue */
395 	struct request_queue *queue;
396 	/* dispatch queue */
397 	struct list_head dispatch;
398 
399 	/* root bfq_group for the device */
400 	struct bfq_group *root_group;
401 
402 	/*
403 	 * rbtree of weight counters of @bfq_queues, sorted by
404 	 * weight. Used to keep track of whether all @bfq_queues have
405 	 * the same weight. The tree contains one counter for each
406 	 * distinct weight associated to some active and not
407 	 * weight-raised @bfq_queue (see the comments to the functions
408 	 * bfq_weights_tree_[add|remove] for further details).
409 	 */
410 	struct rb_root queue_weights_tree;
411 	/*
412 	 * rbtree of non-queue @bfq_entity weight counters, sorted by
413 	 * weight. Used to keep track of whether all @bfq_groups have
414 	 * the same weight. The tree contains one counter for each
415 	 * distinct weight associated to some active @bfq_group (see
416 	 * the comments to the functions bfq_weights_tree_[add|remove]
417 	 * for further details).
418 	 */
419 	struct rb_root group_weights_tree;
420 
421 	/*
422 	 * Number of bfq_queues containing requests (including the
423 	 * queue in service, even if it is idling).
424 	 */
425 	int busy_queues;
426 	/* number of weight-raised busy @bfq_queues */
427 	int wr_busy_queues;
428 	/* number of queued requests */
429 	int queued;
430 	/* number of requests dispatched and waiting for completion */
431 	int rq_in_driver;
432 
433 	/*
434 	 * Maximum number of requests in driver in the last
435 	 * @hw_tag_samples completed requests.
436 	 */
437 	int max_rq_in_driver;
438 	/* number of samples used to calculate hw_tag */
439 	int hw_tag_samples;
440 	/* flag set to one if the driver is showing a queueing behavior */
441 	int hw_tag;
442 
443 	/* number of budgets assigned */
444 	int budgets_assigned;
445 
446 	/*
447 	 * Timer set when idling (waiting) for the next request from
448 	 * the queue in service.
449 	 */
450 	struct hrtimer idle_slice_timer;
451 
452 	/* bfq_queue in service */
453 	struct bfq_queue *in_service_queue;
454 
455 	/* on-disk position of the last served request */
456 	sector_t last_position;
457 
458 	/* time of last request completion (ns) */
459 	u64 last_completion;
460 
461 	/* time of first rq dispatch in current observation interval (ns) */
462 	u64 first_dispatch;
463 	/* time of last rq dispatch in current observation interval (ns) */
464 	u64 last_dispatch;
465 
466 	/* beginning of the last budget */
467 	ktime_t last_budget_start;
468 	/* beginning of the last idle slice */
469 	ktime_t last_idling_start;
470 
471 	/* number of samples in current observation interval */
472 	int peak_rate_samples;
473 	/* num of samples of seq dispatches in current observation interval */
474 	u32 sequential_samples;
475 	/* total num of sectors transferred in current observation interval */
476 	u64 tot_sectors_dispatched;
477 	/* max rq size seen during current observation interval (sectors) */
478 	u32 last_rq_max_size;
479 	/* time elapsed from first dispatch in current observ. interval (us) */
480 	u64 delta_from_first;
481 	/*
482 	 * Current estimate of the device peak rate, measured in
483 	 * [BFQ_RATE_SHIFT * sectors/usec]. The left-shift by
484 	 * BFQ_RATE_SHIFT is performed to increase precision in
485 	 * fixed-point calculations.
486 	 */
487 	u32 peak_rate;
488 
489 	/* maximum budget allotted to a bfq_queue before rescheduling */
490 	int bfq_max_budget;
491 
492 	/* list of all the bfq_queues active on the device */
493 	struct list_head active_list;
494 	/* list of all the bfq_queues idle on the device */
495 	struct list_head idle_list;
496 
497 	/*
498 	 * Timeout for async/sync requests; when it fires, requests
499 	 * are served in fifo order.
500 	 */
501 	u64 bfq_fifo_expire[2];
502 	/* weight of backward seeks wrt forward ones */
503 	unsigned int bfq_back_penalty;
504 	/* maximum allowed backward seek */
505 	unsigned int bfq_back_max;
506 	/* maximum idling time */
507 	u32 bfq_slice_idle;
508 
509 	/* user-configured max budget value (0 for auto-tuning) */
510 	int bfq_user_max_budget;
511 	/*
512 	 * Timeout for bfq_queues to consume their budget; used to
513 	 * prevent seeky queues from imposing long latencies to
514 	 * sequential or quasi-sequential ones (this also implies that
515 	 * seeky queues cannot receive guarantees in the service
516 	 * domain; after a timeout they are charged for the time they
517 	 * have been in service, to preserve fairness among them, but
518 	 * without service-domain guarantees).
519 	 */
520 	unsigned int bfq_timeout;
521 
522 	/*
523 	 * Number of consecutive requests that must be issued within
524 	 * the idle time slice to set again idling to a queue which
525 	 * was marked as non-I/O-bound (see the definition of the
526 	 * IO_bound flag for further details).
527 	 */
528 	unsigned int bfq_requests_within_timer;
529 
530 	/*
531 	 * Force device idling whenever needed to provide accurate
532 	 * service guarantees, without caring about throughput
533 	 * issues. CAVEAT: this may even increase latencies, in case
534 	 * of useless idling for processes that did stop doing I/O.
535 	 */
536 	bool strict_guarantees;
537 
538 	/*
539 	 * Last time at which a queue entered the current burst of
540 	 * queues being activated shortly after each other; for more
541 	 * details about this and the following parameters related to
542 	 * a burst of activations, see the comments on the function
543 	 * bfq_handle_burst.
544 	 */
545 	unsigned long last_ins_in_burst;
546 	/*
547 	 * Reference time interval used to decide whether a queue has
548 	 * been activated shortly after @last_ins_in_burst.
549 	 */
550 	unsigned long bfq_burst_interval;
551 	/* number of queues in the current burst of queue activations */
552 	int burst_size;
553 
554 	/* common parent entity for the queues in the burst */
555 	struct bfq_entity *burst_parent_entity;
556 	/* Maximum burst size above which the current queue-activation
557 	 * burst is deemed as 'large'.
558 	 */
559 	unsigned long bfq_large_burst_thresh;
560 	/* true if a large queue-activation burst is in progress */
561 	bool large_burst;
562 	/*
563 	 * Head of the burst list (as for the above fields, more
564 	 * details in the comments on the function bfq_handle_burst).
565 	 */
566 	struct hlist_head burst_list;
567 
568 	/* if set to true, low-latency heuristics are enabled */
569 	bool low_latency;
570 	/*
571 	 * Maximum factor by which the weight of a weight-raised queue
572 	 * is multiplied.
573 	 */
574 	unsigned int bfq_wr_coeff;
575 	/* maximum duration of a weight-raising period (jiffies) */
576 	unsigned int bfq_wr_max_time;
577 
578 	/* Maximum weight-raising duration for soft real-time processes */
579 	unsigned int bfq_wr_rt_max_time;
580 	/*
581 	 * Minimum idle period after which weight-raising may be
582 	 * reactivated for a queue (in jiffies).
583 	 */
584 	unsigned int bfq_wr_min_idle_time;
585 	/*
586 	 * Minimum period between request arrivals after which
587 	 * weight-raising may be reactivated for an already busy async
588 	 * queue (in jiffies).
589 	 */
590 	unsigned long bfq_wr_min_inter_arr_async;
591 
592 	/* Max service-rate for a soft real-time queue, in sectors/sec */
593 	unsigned int bfq_wr_max_softrt_rate;
594 	/*
595 	 * Cached value of the product R*T, used for computing the
596 	 * maximum duration of weight raising automatically.
597 	 */
598 	u64 RT_prod;
599 	/* device-speed class for the low-latency heuristic */
600 	enum bfq_device_speed device_speed;
601 
602 	/* fallback dummy bfqq for extreme OOM conditions */
603 	struct bfq_queue oom_bfqq;
604 
605 	spinlock_t lock;
606 
607 	/*
608 	 * bic associated with the task issuing current bio for
609 	 * merging. This and the next field are used as a support to
610 	 * be able to perform the bic lookup, needed by bio-merge
611 	 * functions, before the scheduler lock is taken, and thus
612 	 * avoid taking the request-queue lock while the scheduler
613 	 * lock is being held.
614 	 */
615 	struct bfq_io_cq *bio_bic;
616 	/* bfqq associated with the task issuing current bio for merging */
617 	struct bfq_queue *bio_bfqq;
618 };
619 
620 enum bfqq_state_flags {
621 	BFQQF_just_created = 0,	/* queue just allocated */
622 	BFQQF_busy,		/* has requests or is in service */
623 	BFQQF_wait_request,	/* waiting for a request */
624 	BFQQF_non_blocking_wait_rq, /*
625 				     * waiting for a request
626 				     * without idling the device
627 				     */
628 	BFQQF_fifo_expire,	/* FIFO checked in this slice */
629 	BFQQF_idle_window,	/* slice idling enabled */
630 	BFQQF_sync,		/* synchronous queue */
631 	BFQQF_IO_bound,		/*
632 				 * bfqq has timed-out at least once
633 				 * having consumed at most 2/10 of
634 				 * its budget
635 				 */
636 	BFQQF_in_large_burst,	/*
637 				 * bfqq activated in a large burst,
638 				 * see comments to bfq_handle_burst.
639 				 */
640 	BFQQF_softrt_update,	/*
641 				 * may need softrt-next-start
642 				 * update
643 				 */
644 	BFQQF_coop,		/* bfqq is shared */
645 	BFQQF_split_coop	/* shared bfqq will be split */
646 };
647 
648 #define BFQ_BFQQ_FNS(name)						\
649 void bfq_mark_bfqq_##name(struct bfq_queue *bfqq);			\
650 void bfq_clear_bfqq_##name(struct bfq_queue *bfqq);			\
651 int bfq_bfqq_##name(const struct bfq_queue *bfqq);
652 
653 BFQ_BFQQ_FNS(just_created);
654 BFQ_BFQQ_FNS(busy);
655 BFQ_BFQQ_FNS(wait_request);
656 BFQ_BFQQ_FNS(non_blocking_wait_rq);
657 BFQ_BFQQ_FNS(fifo_expire);
658 BFQ_BFQQ_FNS(idle_window);
659 BFQ_BFQQ_FNS(sync);
660 BFQ_BFQQ_FNS(IO_bound);
661 BFQ_BFQQ_FNS(in_large_burst);
662 BFQ_BFQQ_FNS(coop);
663 BFQ_BFQQ_FNS(split_coop);
664 BFQ_BFQQ_FNS(softrt_update);
665 #undef BFQ_BFQQ_FNS
666 
667 /* Expiration reasons. */
668 enum bfqq_expiration {
669 	BFQQE_TOO_IDLE = 0,		/*
670 					 * queue has been idling for
671 					 * too long
672 					 */
673 	BFQQE_BUDGET_TIMEOUT,	/* budget took too long to be used */
674 	BFQQE_BUDGET_EXHAUSTED,	/* budget consumed */
675 	BFQQE_NO_MORE_REQUESTS,	/* the queue has no more requests */
676 	BFQQE_PREEMPTED		/* preemption in progress */
677 };
678 
679 struct bfqg_stats {
680 #ifdef CONFIG_BFQ_GROUP_IOSCHED
681 	/* number of ios merged */
682 	struct blkg_rwstat		merged;
683 	/* total time spent on device in ns, may not be accurate w/ queueing */
684 	struct blkg_rwstat		service_time;
685 	/* total time spent waiting in scheduler queue in ns */
686 	struct blkg_rwstat		wait_time;
687 	/* number of IOs queued up */
688 	struct blkg_rwstat		queued;
689 	/* total disk time and nr sectors dispatched by this group */
690 	struct blkg_stat		time;
691 	/* sum of number of ios queued across all samples */
692 	struct blkg_stat		avg_queue_size_sum;
693 	/* count of samples taken for average */
694 	struct blkg_stat		avg_queue_size_samples;
695 	/* how many times this group has been removed from service tree */
696 	struct blkg_stat		dequeue;
697 	/* total time spent waiting for it to be assigned a timeslice. */
698 	struct blkg_stat		group_wait_time;
699 	/* time spent idling for this blkcg_gq */
700 	struct blkg_stat		idle_time;
701 	/* total time with empty current active q with other requests queued */
702 	struct blkg_stat		empty_time;
703 	/* fields after this shouldn't be cleared on stat reset */
704 	uint64_t			start_group_wait_time;
705 	uint64_t			start_idle_time;
706 	uint64_t			start_empty_time;
707 	uint16_t			flags;
708 #endif	/* CONFIG_BFQ_GROUP_IOSCHED */
709 };
710 
711 #ifdef CONFIG_BFQ_GROUP_IOSCHED
712 
713 /*
714  * struct bfq_group_data - per-blkcg storage for the blkio subsystem.
715  *
716  * @ps: @blkcg_policy_storage that this structure inherits
717  * @weight: weight of the bfq_group
718  */
719 struct bfq_group_data {
720 	/* must be the first member */
721 	struct blkcg_policy_data pd;
722 
723 	unsigned int weight;
724 };
725 
726 /**
727  * struct bfq_group - per (device, cgroup) data structure.
728  * @entity: schedulable entity to insert into the parent group sched_data.
729  * @sched_data: own sched_data, to contain child entities (they may be
730  *              both bfq_queues and bfq_groups).
731  * @bfqd: the bfq_data for the device this group acts upon.
732  * @async_bfqq: array of async queues for all the tasks belonging to
733  *              the group, one queue per ioprio value per ioprio_class,
734  *              except for the idle class that has only one queue.
735  * @async_idle_bfqq: async queue for the idle class (ioprio is ignored).
736  * @my_entity: pointer to @entity, %NULL for the toplevel group; used
737  *             to avoid too many special cases during group creation/
738  *             migration.
739  * @stats: stats for this bfqg.
740  * @active_entities: number of active entities belonging to the group;
741  *                   unused for the root group. Used to know whether there
742  *                   are groups with more than one active @bfq_entity
743  *                   (see the comments to the function
744  *                   bfq_bfqq_may_idle()).
745  * @rq_pos_tree: rbtree sorted by next_request position, used when
746  *               determining if two or more queues have interleaving
747  *               requests (see bfq_find_close_cooperator()).
748  *
749  * Each (device, cgroup) pair has its own bfq_group, i.e., for each cgroup
750  * there is a set of bfq_groups, each one collecting the lower-level
751  * entities belonging to the group that are acting on the same device.
752  *
753  * Locking works as follows:
754  *    o @bfqd is protected by the queue lock, RCU is used to access it
755  *      from the readers.
756  *    o All the other fields are protected by the @bfqd queue lock.
757  */
758 struct bfq_group {
759 	/* must be the first member */
760 	struct blkg_policy_data pd;
761 
762 	/* cached path for this blkg (see comments in bfq_bic_update_cgroup) */
763 	char blkg_path[128];
764 
765 	/* reference counter (see comments in bfq_bic_update_cgroup) */
766 	int ref;
767 
768 	struct bfq_entity entity;
769 	struct bfq_sched_data sched_data;
770 
771 	void *bfqd;
772 
773 	struct bfq_queue *async_bfqq[2][IOPRIO_BE_NR];
774 	struct bfq_queue *async_idle_bfqq;
775 
776 	struct bfq_entity *my_entity;
777 
778 	int active_entities;
779 
780 	struct rb_root rq_pos_tree;
781 
782 	struct bfqg_stats stats;
783 };
784 
785 #else
786 struct bfq_group {
787 	struct bfq_sched_data sched_data;
788 
789 	struct bfq_queue *async_bfqq[2][IOPRIO_BE_NR];
790 	struct bfq_queue *async_idle_bfqq;
791 
792 	struct rb_root rq_pos_tree;
793 };
794 #endif
795 
796 struct bfq_queue *bfq_entity_to_bfqq(struct bfq_entity *entity);
797 
798 /* --------------- main algorithm interface ----------------- */
799 
800 #define BFQ_SERVICE_TREE_INIT	((struct bfq_service_tree)		\
801 				{ RB_ROOT, RB_ROOT, NULL, NULL, 0, 0 })
802 
803 extern const int bfq_timeout;
804 
805 struct bfq_queue *bic_to_bfqq(struct bfq_io_cq *bic, bool is_sync);
806 void bic_set_bfqq(struct bfq_io_cq *bic, struct bfq_queue *bfqq, bool is_sync);
807 struct bfq_data *bic_to_bfqd(struct bfq_io_cq *bic);
808 void bfq_requeue_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq);
809 void bfq_pos_tree_add_move(struct bfq_data *bfqd, struct bfq_queue *bfqq);
810 void bfq_weights_tree_add(struct bfq_data *bfqd, struct bfq_entity *entity,
811 			  struct rb_root *root);
812 void bfq_weights_tree_remove(struct bfq_data *bfqd, struct bfq_entity *entity,
813 			     struct rb_root *root);
814 void bfq_bfqq_expire(struct bfq_data *bfqd, struct bfq_queue *bfqq,
815 		     bool compensate, enum bfqq_expiration reason);
816 void bfq_put_queue(struct bfq_queue *bfqq);
817 void bfq_end_wr_async_queues(struct bfq_data *bfqd, struct bfq_group *bfqg);
818 void bfq_schedule_dispatch(struct bfq_data *bfqd);
819 void bfq_put_async_queues(struct bfq_data *bfqd, struct bfq_group *bfqg);
820 
821 /* ------------ end of main algorithm interface -------------- */
822 
823 /* ---------------- cgroups-support interface ---------------- */
824 
825 void bfqg_stats_update_io_add(struct bfq_group *bfqg, struct bfq_queue *bfqq,
826 			      unsigned int op);
827 void bfqg_stats_update_io_remove(struct bfq_group *bfqg, unsigned int op);
828 void bfqg_stats_update_io_merged(struct bfq_group *bfqg, unsigned int op);
829 void bfqg_stats_update_completion(struct bfq_group *bfqg, uint64_t start_time,
830 				  uint64_t io_start_time, unsigned int op);
831 void bfqg_stats_update_dequeue(struct bfq_group *bfqg);
832 void bfqg_stats_set_start_empty_time(struct bfq_group *bfqg);
833 void bfqg_stats_update_idle_time(struct bfq_group *bfqg);
834 void bfqg_stats_set_start_idle_time(struct bfq_group *bfqg);
835 void bfqg_stats_update_avg_queue_size(struct bfq_group *bfqg);
836 void bfq_bfqq_move(struct bfq_data *bfqd, struct bfq_queue *bfqq,
837 		   struct bfq_group *bfqg);
838 
839 void bfq_init_entity(struct bfq_entity *entity, struct bfq_group *bfqg);
840 void bfq_bic_update_cgroup(struct bfq_io_cq *bic, struct bio *bio);
841 void bfq_end_wr_async(struct bfq_data *bfqd);
842 struct bfq_group *bfq_find_set_group(struct bfq_data *bfqd,
843 				     struct blkcg *blkcg);
844 struct blkcg_gq *bfqg_to_blkg(struct bfq_group *bfqg);
845 struct bfq_group *bfqq_group(struct bfq_queue *bfqq);
846 struct bfq_group *bfq_create_group_hierarchy(struct bfq_data *bfqd, int node);
847 void bfqg_and_blkg_put(struct bfq_group *bfqg);
848 
849 #ifdef CONFIG_BFQ_GROUP_IOSCHED
850 extern struct cftype bfq_blkcg_legacy_files[];
851 extern struct cftype bfq_blkg_files[];
852 extern struct blkcg_policy blkcg_policy_bfq;
853 #endif
854 
855 /* ------------- end of cgroups-support interface ------------- */
856 
857 /* - interface of the internal hierarchical B-WF2Q+ scheduler - */
858 
859 #ifdef CONFIG_BFQ_GROUP_IOSCHED
860 /* both next loops stop at one of the child entities of the root group */
861 #define for_each_entity(entity)	\
862 	for (; entity ; entity = entity->parent)
863 
864 /*
865  * For each iteration, compute parent in advance, so as to be safe if
866  * entity is deallocated during the iteration. Such a deallocation may
867  * happen as a consequence of a bfq_put_queue that frees the bfq_queue
868  * containing entity.
869  */
870 #define for_each_entity_safe(entity, parent) \
871 	for (; entity && ({ parent = entity->parent; 1; }); entity = parent)
872 
873 #else /* CONFIG_BFQ_GROUP_IOSCHED */
874 /*
875  * Next two macros are fake loops when cgroups support is not
876  * enabled. I fact, in such a case, there is only one level to go up
877  * (to reach the root group).
878  */
879 #define for_each_entity(entity)	\
880 	for (; entity ; entity = NULL)
881 
882 #define for_each_entity_safe(entity, parent) \
883 	for (parent = NULL; entity ; entity = parent)
884 #endif /* CONFIG_BFQ_GROUP_IOSCHED */
885 
886 struct bfq_group *bfq_bfqq_to_bfqg(struct bfq_queue *bfqq);
887 struct bfq_queue *bfq_entity_to_bfqq(struct bfq_entity *entity);
888 struct bfq_service_tree *bfq_entity_service_tree(struct bfq_entity *entity);
889 struct bfq_entity *bfq_entity_of(struct rb_node *node);
890 unsigned short bfq_ioprio_to_weight(int ioprio);
891 void bfq_put_idle_entity(struct bfq_service_tree *st,
892 			 struct bfq_entity *entity);
893 struct bfq_service_tree *
894 __bfq_entity_update_weight_prio(struct bfq_service_tree *old_st,
895 				struct bfq_entity *entity,
896 				bool update_class_too);
897 void bfq_bfqq_served(struct bfq_queue *bfqq, int served);
898 void bfq_bfqq_charge_time(struct bfq_data *bfqd, struct bfq_queue *bfqq,
899 			  unsigned long time_ms);
900 bool __bfq_deactivate_entity(struct bfq_entity *entity,
901 			     bool ins_into_idle_tree);
902 bool next_queue_may_preempt(struct bfq_data *bfqd);
903 struct bfq_queue *bfq_get_next_queue(struct bfq_data *bfqd);
904 void __bfq_bfqd_reset_in_service(struct bfq_data *bfqd);
905 void bfq_deactivate_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq,
906 			 bool ins_into_idle_tree, bool expiration);
907 void bfq_activate_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq);
908 void bfq_requeue_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq);
909 void bfq_del_bfqq_busy(struct bfq_data *bfqd, struct bfq_queue *bfqq,
910 		       bool expiration);
911 void bfq_add_bfqq_busy(struct bfq_data *bfqd, struct bfq_queue *bfqq);
912 
913 /* --------------- end of interface of B-WF2Q+ ---------------- */
914 
915 /* Logging facilities. */
916 #ifdef CONFIG_BFQ_GROUP_IOSCHED
917 struct bfq_group *bfqq_group(struct bfq_queue *bfqq);
918 
919 #define bfq_log_bfqq(bfqd, bfqq, fmt, args...)	do {			\
920 	blk_add_trace_msg((bfqd)->queue, "bfq%d%c %s " fmt, (bfqq)->pid,\
921 			bfq_bfqq_sync((bfqq)) ? 'S' : 'A',		\
922 			bfqq_group(bfqq)->blkg_path, ##args);		\
923 } while (0)
924 
925 #define bfq_log_bfqg(bfqd, bfqg, fmt, args...)	\
926 	blk_add_trace_msg((bfqd)->queue, "%s " fmt, (bfqg)->blkg_path, ##args)
927 
928 #else /* CONFIG_BFQ_GROUP_IOSCHED */
929 
930 #define bfq_log_bfqq(bfqd, bfqq, fmt, args...)	\
931 	blk_add_trace_msg((bfqd)->queue, "bfq%d%c " fmt, (bfqq)->pid,	\
932 			bfq_bfqq_sync((bfqq)) ? 'S' : 'A',		\
933 				##args)
934 #define bfq_log_bfqg(bfqd, bfqg, fmt, args...)		do {} while (0)
935 
936 #endif /* CONFIG_BFQ_GROUP_IOSCHED */
937 
938 #define bfq_log(bfqd, fmt, args...) \
939 	blk_add_trace_msg((bfqd)->queue, "bfq " fmt, ##args)
940 
941 #endif /* _BFQ_H */
942