[PATCH V4 14/16] block, bfq: handle bursts of queue activations

[Paolo Valente]

From: Arianna Avanzini 

Many popular I/O-intensive services or applications spawn or
reactivate many parallel threads/processes during short time
intervals. Examples are systemd during boot or git grep.  These
services or applications benefit mostly from a high throughput: the
quicker the I/O generated by their processes is cumulatively served,
the sooner the target job of these services or applications gets
completed. As a consequence, it is almost always counterproductive to
weight-raise any of the queues associated to the processes of these
services or applications: in most cases it would just lower the
throughput, mainly because weight-raising also implies device idling.

To address this issue, an I/O scheduler needs, first, to detect which
queues are associated with these services or applications. In this
respect, we have that, from the I/O-scheduler standpoint, these
services or applications cause bursts of activations, i.e.,
activations of different queues occurring shortly after each
other. However, a shorter burst of activations may be caused also by
the start of an application that does not consist in a lot of parallel
I/O-bound threads (see the comments on the function bfq_handle_burst
for details).

In view of these facts, this commit introduces:
1) an heuristic to detect (only) bursts of queue activations caused by
   services or applications consisting in many parallel I/O-bound
   threads;
2) the prevention of device idling and weight-raising for the queues
   belonging to these bursts.

Signed-off-by: Arianna Avanzini 
Signed-off-by: Paolo Valente 
---
 block/bfq-iosched.c | 404 ++--
 1 file changed, 389 insertions(+), 15 deletions(-)

diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c
index 549f030..b7e3c86 100644
--- a/block/bfq-iosched.c
+++ b/block/bfq-iosched.c
@@ -360,6 +360,10 @@ struct bfq_queue {
 
/* bit vector: a 1 for each seeky requests in history */
u32 seek_history;
+
+   /* node for the device's burst list */
+   struct hlist_node burst_list_node;
+
/* position of the last request enqueued */
sector_t last_request_pos;
 
@@ -443,6 +447,17 @@ struct bfq_io_cq {
bool saved_IO_bound;
 
/*
+* Same purpose as the previous fields for the value of the
+* field keeping the queue's belonging to a large burst
+*/
+   bool saved_in_large_burst;
+   /*
+* True if the queue belonged to a burst list before its merge
+* with another cooperating queue.
+*/
+   bool was_in_burst_list;
+
+   /*
 * Similar to previous fields: save wr information.
 */
unsigned long saved_wr_coeff;
@@ -609,6 +624,36 @@ struct bfq_data {
 */
bool strict_guarantees;
 
+   /*
+* Last time at which a queue entered the current burst of
+* queues being activated shortly after each other; for more
+* details about this and the following parameters related to
+* a burst of activations, see the comments on the function
+* bfq_handle_burst.
+*/
+   unsigned long last_ins_in_burst;
+   /*
+* Reference time interval used to decide whether a queue has
+* been activated shortly after @last_ins_in_burst.
+*/
+   unsigned long bfq_burst_interval;
+   /* number of queues in the current burst of queue activations */
+   int burst_size;
+
+   /* common parent entity for the queues in the burst */
+   struct bfq_entity *burst_parent_entity;
+   /* Maximum burst size above which the current queue-activation
+* burst is deemed as 'large'.
+*/
+   unsigned long bfq_large_burst_thresh;
+   /* true if a large queue-activation burst is in progress */
+   bool large_burst;
+   /*
+* Head of the burst list (as for the above fields, more
+* details in the comments on the function bfq_handle_burst).
+*/
+   struct hlist_head burst_list;
+
/* if set to true, low-latency heuristics are enabled */
bool low_latency;
/*
@@ -671,7 +716,8 @@ struct bfq_data {
 };
 
 enum bfqq_state_flags {
-   BFQQF_busy = 0, /* has requests or is in service */
+   BFQQF_just_created = 0, /* queue just allocated */
+   BFQQF_busy, /* has requests or is in service */
BFQQF_wait_request, /* waiting for a request */
BFQQF_non_blocking_wait_rq, /*
 * waiting for a request
@@ -685,6 +731,10 @@ enum bfqq_state_flags {
 * having consumed at most 2/10 of
 * its budget
 */
+   BFQQF_in_large_burst,   /*
+* bfqq activated in a large burst,
+* see 

[PATCH V4 14/16] block, bfq: handle bursts of queue activations

[Paolo Valente]

From: Arianna Avanzini 

Many popular I/O-intensive services or applications spawn or
reactivate many parallel threads/processes during short time
intervals. Examples are systemd during boot or git grep.  These
services or applications benefit mostly from a high throughput: the
quicker the I/O generated by their processes is cumulatively served,
the sooner the target job of these services or applications gets
completed. As a consequence, it is almost always counterproductive to
weight-raise any of the queues associated to the processes of these
services or applications: in most cases it would just lower the
throughput, mainly because weight-raising also implies device idling.

To address this issue, an I/O scheduler needs, first, to detect which
queues are associated with these services or applications. In this
respect, we have that, from the I/O-scheduler standpoint, these
services or applications cause bursts of activations, i.e.,
activations of different queues occurring shortly after each
other. However, a shorter burst of activations may be caused also by
the start of an application that does not consist in a lot of parallel
I/O-bound threads (see the comments on the function bfq_handle_burst
for details).

In view of these facts, this commit introduces:
1) an heuristic to detect (only) bursts of queue activations caused by
   services or applications consisting in many parallel I/O-bound
   threads;
2) the prevention of device idling and weight-raising for the queues
   belonging to these bursts.

Signed-off-by: Arianna Avanzini 
Signed-off-by: Paolo Valente 
---
 block/bfq-iosched.c | 404 ++--
 1 file changed, 389 insertions(+), 15 deletions(-)

diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c
index 549f030..b7e3c86 100644
--- a/block/bfq-iosched.c
+++ b/block/bfq-iosched.c
@@ -360,6 +360,10 @@ struct bfq_queue {
 
/* bit vector: a 1 for each seeky requests in history */
u32 seek_history;
+
+   /* node for the device's burst list */
+   struct hlist_node burst_list_node;
+
/* position of the last request enqueued */
sector_t last_request_pos;
 
@@ -443,6 +447,17 @@ struct bfq_io_cq {
bool saved_IO_bound;
 
/*
+* Same purpose as the previous fields for the value of the
+* field keeping the queue's belonging to a large burst
+*/
+   bool saved_in_large_burst;
+   /*
+* True if the queue belonged to a burst list before its merge
+* with another cooperating queue.
+*/
+   bool was_in_burst_list;
+
+   /*
 * Similar to previous fields: save wr information.
 */
unsigned long saved_wr_coeff;
@@ -609,6 +624,36 @@ struct bfq_data {
 */
bool strict_guarantees;
 
+   /*
+* Last time at which a queue entered the current burst of
+* queues being activated shortly after each other; for more
+* details about this and the following parameters related to
+* a burst of activations, see the comments on the function
+* bfq_handle_burst.
+*/
+   unsigned long last_ins_in_burst;
+   /*
+* Reference time interval used to decide whether a queue has
+* been activated shortly after @last_ins_in_burst.
+*/
+   unsigned long bfq_burst_interval;
+   /* number of queues in the current burst of queue activations */
+   int burst_size;
+
+   /* common parent entity for the queues in the burst */
+   struct bfq_entity *burst_parent_entity;
+   /* Maximum burst size above which the current queue-activation
+* burst is deemed as 'large'.
+*/
+   unsigned long bfq_large_burst_thresh;
+   /* true if a large queue-activation burst is in progress */
+   bool large_burst;
+   /*
+* Head of the burst list (as for the above fields, more
+* details in the comments on the function bfq_handle_burst).
+*/
+   struct hlist_head burst_list;
+
/* if set to true, low-latency heuristics are enabled */
bool low_latency;
/*
@@ -671,7 +716,8 @@ struct bfq_data {
 };
 
 enum bfqq_state_flags {
-   BFQQF_busy = 0, /* has requests or is in service */
+   BFQQF_just_created = 0, /* queue just allocated */
+   BFQQF_busy, /* has requests or is in service */
BFQQF_wait_request, /* waiting for a request */
BFQQF_non_blocking_wait_rq, /*
 * waiting for a request
@@ -685,6 +731,10 @@ enum bfqq_state_flags {
 * having consumed at most 2/10 of
 * its budget
 */
+   BFQQF_in_large_burst,   /*
+* bfqq activated in a large burst,
+* see comments to bfq_handle_burst.
+*/