[PATCH v3 0/2] optimize the bfq queue idle judgment

[PATCH v3 0/2] optimize the bfq queue idle judgment

[Yu Kuai]

Changes in V3:
 - Instead of tracking each queue in root group, tracking root group
 directly just like non-root group does.
 - remove patch 3,4 from these series.

Chagnes in V2:
 - as suggested by Paolo, add support to track if root_group have any
 pending requests, and use that to handle the situation when only one
 group is activated while root group doesn't have any pending requests.
 - modify commit message in patch 2

Yu Kuai (2):
  block, bfq: counted root group into 'num_groups_with_pending_reqs'
  block, bfq: do not idle if only one cgroup is activated

 block/bfq-iosched.c | 40 ++++++++++++++++++++++++++++--------
 block/bfq-wf2q.c    | 50 +++++++++++++++++++++++++++++++++------------
 2 files changed, 69 insertions(+), 21 deletions(-)

-- 
2.31.1

[PATCH v3 1/2] block, bfq: counted root group into 'num_groups_with_pending_reqs'

[Yu Kuai]

'num_groups_with_pending_reqs' represents how many groups that are
not root group and have pending requests. This patch also counted
root group into 'num_groups_with_pending_reqs'.

Signed-off-by: Yu Kuai <yukuai3@huawei.com>
---
 block/bfq-iosched.c | 36 ++++++++++++++++++++++++++------
 block/bfq-wf2q.c    | 50 +++++++++++++++++++++++++++++++++------------
 2 files changed, 67 insertions(+), 19 deletions(-)

diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c
index fec18118dc30..d251735383f7 100644
--- a/block/bfq-iosched.c
+++ b/block/bfq-iosched.c
@@ -852,6 +852,16 @@ void __bfq_weights_tree_remove(struct bfq_data *bfqd,
 	bfq_put_queue(bfqq);
 }
 
+static inline void
+bfq_clear_group_with_pending_reqs(struct bfq_data *bfqd,
+				  struct bfq_entity *entity)
+{
+	if (entity->in_groups_with_pending_reqs) {
+		entity->in_groups_with_pending_reqs = false;
+		bfqd->num_groups_with_pending_reqs--;
+	}
+}
+
 /*
  * Invoke __bfq_weights_tree_remove on bfqq and decrement the number
  * of active groups for each queue's inactive parent entity.
@@ -860,9 +870,25 @@ void bfq_weights_tree_remove(struct bfq_data *bfqd,
 			     struct bfq_queue *bfqq)
 {
 	struct bfq_entity *entity = bfqq->entity.parent;
+	struct bfq_sched_data *sd;
+
+	/*
+	 * If the bfq queue is in root group, the decrement of
+	 * num_groups_with_pending_reqs is performed immediately upon the
+	 * deactivation of entity.
+	 */
+	if (!entity) {
+		entity = &bfqd->root_group->entity;
+		sd = entity->my_sched_data;
+
+		if (!sd->in_service_entity)
+			bfq_clear_group_with_pending_reqs(bfqd, entity);
+
+		return;
+	}
 
 	for_each_entity(entity) {
-		struct bfq_sched_data *sd = entity->my_sched_data;
+		sd = entity->my_sched_data;
 
 		if (sd->next_in_service || sd->in_service_entity) {
 			/*
@@ -880,7 +906,8 @@ void bfq_weights_tree_remove(struct bfq_data *bfqd,
 		}
 
 		/*
-		 * The decrement of num_groups_with_pending_reqs is
+		 * If the bfq queue is not in root group,
+		 * the decrement of num_groups_with_pending_reqs is
 		 * not performed immediately upon the deactivation of
 		 * entity, but it is delayed to when it also happens
 		 * that the first leaf descendant bfqq of entity gets
@@ -889,10 +916,7 @@ void bfq_weights_tree_remove(struct bfq_data *bfqd,
 		 * needed. See the comments on
 		 * num_groups_with_pending_reqs for details.
 		 */
-		if (entity->in_groups_with_pending_reqs) {
-			entity->in_groups_with_pending_reqs = false;
-			bfqd->num_groups_with_pending_reqs--;
-		}
+		bfq_clear_group_with_pending_reqs(bfqd, entity);
 	}
 
 	/*
diff --git a/block/bfq-wf2q.c b/block/bfq-wf2q.c
index b74cc0da118e..5c70973c65ea 100644
--- a/block/bfq-wf2q.c
+++ b/block/bfq-wf2q.c
@@ -945,6 +945,42 @@ static void bfq_update_fin_time_enqueue(struct bfq_entity *entity,
 
 	bfq_active_insert(st, entity);
 }
+#ifdef CONFIG_BFQ_GROUP_IOSCHED
+static inline void
+bfq_set_group_with_pending_reqs(struct bfq_data *bfqd,
+				struct bfq_entity *entity)
+{
+	if (!entity->in_groups_with_pending_reqs) {
+		entity->in_groups_with_pending_reqs = true;
+		bfqd->num_groups_with_pending_reqs++;
+	}
+}
+
+static void bfq_update_groups_with_pending_reqs(struct bfq_entity *entity)
+{
+	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
+
+	if (bfqq) {
+		/*
+		 * If the entity represents bfq_queue, and the queue belongs to
+		 * root cgroup.
+		 */
+		if (!entity->parent)
+			bfq_set_group_with_pending_reqs(bfqq->bfqd,
+				&bfqq->bfqd->root_group->entity);
+	} else {
+		/* If the entity represents bfq_group. */
+		struct bfq_group *bfqg =
+			container_of(entity, struct bfq_group, entity);
+		struct bfq_data *bfqd = bfqg->bfqd;
+
+		bfq_set_group_with_pending_reqs(bfqd, entity);
+	}
+}
+#else
+#define bfq_update_groups_with_pending_reqs(struct bfq_entity *entity) \
+	do {} while (0)
+#endif
 
 /**
  * __bfq_activate_entity - handle activation of entity.
@@ -999,19 +1035,7 @@ static void __bfq_activate_entity(struct bfq_entity *entity,
 		entity->on_st_or_in_serv = true;
 	}
 
-#ifdef CONFIG_BFQ_GROUP_IOSCHED
-	if (!bfq_entity_to_bfqq(entity)) { /* bfq_group */
-		struct bfq_group *bfqg =
-			container_of(entity, struct bfq_group, entity);
-		struct bfq_data *bfqd = bfqg->bfqd;
-
-		if (!entity->in_groups_with_pending_reqs) {
-			entity->in_groups_with_pending_reqs = true;
-			bfqd->num_groups_with_pending_reqs++;
-		}
-	}
-#endif
-
+	bfq_update_groups_with_pending_reqs(entity);
 	bfq_update_fin_time_enqueue(entity, st, backshifted);
 }
 
-- 
2.31.1

[PATCH v3 2/2] block, bfq: do not idle if only one cgroup is activated

[Yu Kuai]

If only one group is activated, there is no need to guarantee the
same share of the throughput of queues in the same group.

Test procedure:
run "fio -numjobs=1 -ioengine=psync -bs=4k -direct=1 -rw=randread..."
multiple times in the same cgroup.

Test result: total bandwidth(Mib/s)
| total jobs | before this patch | after this patch      |
| ---------- | ----------------- | --------------------- |
| 1          | 33.8              | 33.8                  |
| 2          | 33.8              | 65.4 (32.7 each job)  |
| 4          | 33.8              | 106.8 (26.7 each job) |
| 8          | 33.8              | 126.4 (15.8 each job) |

By the way, if I test with "fio -numjobs=1/2/4/8 ...", test result is
the same with or without this patch. This is because bfq_queue can
be merged in this situation.

Signed-off-by: Yu Kuai <yukuai3@huawei.com>
---
 block/bfq-iosched.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c
index d251735383f7..8d94f511bee8 100644
--- a/block/bfq-iosched.c
+++ b/block/bfq-iosched.c
@@ -709,7 +709,7 @@ bfq_pos_tree_add_move(struct bfq_data *bfqd, struct bfq_queue *bfqq)
  * much easier to maintain the needed state:
  * 1) all active queues have the same weight,
  * 2) all active queues belong to the same I/O-priority class,
- * 3) there are no active groups.
+ * 3) there are one active group at most.
  * In particular, the last condition is always true if hierarchical
  * support or the cgroups interface are not enabled, thus no state
  * needs to be maintained in this case.
@@ -741,7 +741,7 @@ static bool bfq_asymmetric_scenario(struct bfq_data *bfqd,
 
 	return varied_queue_weights || multiple_classes_busy
 #ifdef CONFIG_BFQ_GROUP_IOSCHED
-	       || bfqd->num_groups_with_pending_reqs > 0
+	       || bfqd->num_groups_with_pending_reqs > 1
 #endif
 		;
 }
-- 
2.31.1

Re: [PATCH v3 1/2] block, bfq: counted root group into 'num_groups_with_pending_reqs'

[kernel test robot]

[-- Attachment #1: Type: text/plain, Size: 5232 bytes --]

Hi Yu,

Thank you for the patch! Yet something to improve:

[auto build test ERROR on axboe-block/for-next]
[also build test ERROR on v5.15-rc5 next-20211013]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch]

url:    https://github.com/0day-ci/linux/commits/Yu-Kuai/optimize-the-bfq-queue-idle-judgment/20211013-191413
base:   https://git.kernel.org/pub/scm/linux/kernel/git/axboe/linux-block.git for-next
config: arc-randconfig-r043-20211013 (attached as .config)
compiler: arc-elf-gcc (GCC) 11.2.0
reproduce (this is a W=1 build):
        wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
        chmod +x ~/bin/make.cross
        # https://github.com/0day-ci/linux/commit/59e859f9efae59f2fb2a850b44953800e06f5eb0
        git remote add linux-review https://github.com/0day-ci/linux
        git fetch --no-tags linux-review Yu-Kuai/optimize-the-bfq-queue-idle-judgment/20211013-191413
        git checkout 59e859f9efae59f2fb2a850b44953800e06f5eb0
        # save the attached .config to linux build tree
        mkdir build_dir
        COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-11.2.0 make.cross O=build_dir ARCH=arc SHELL=/bin/bash block/

If you fix the issue, kindly add following tag as appropriate
Reported-by: kernel test robot <lkp@intel.com>

All errors (new ones prefixed by >>):

>> block/bfq-wf2q.c:981:52: error: expected ',' or ')', found "bfq_entity"
     981 | #define bfq_update_groups_with_pending_reqs(struct bfq_entity *entity) \
         |                                                    ^~~~~~~~~~
   block/bfq-wf2q.c: In function '__bfq_activate_entity':
>> block/bfq-wf2q.c:1038:9: error: implicit declaration of function 'bfq_update_groups_with_pending_reqs' [-Werror=implicit-function-declaration]
    1038 |         bfq_update_groups_with_pending_reqs(entity);
         |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   cc1: some warnings being treated as errors


vim +981 block/bfq-wf2q.c

   958	
   959	static void bfq_update_groups_with_pending_reqs(struct bfq_entity *entity)
   960	{
   961		struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
   962	
   963		if (bfqq) {
   964			/*
   965			 * If the entity represents bfq_queue, and the queue belongs to
   966			 * root cgroup.
   967			 */
   968			if (!entity->parent)
   969				bfq_set_group_with_pending_reqs(bfqq->bfqd,
   970					&bfqq->bfqd->root_group->entity);
   971		} else {
   972			/* If the entity represents bfq_group. */
   973			struct bfq_group *bfqg =
   974				container_of(entity, struct bfq_group, entity);
   975			struct bfq_data *bfqd = bfqg->bfqd;
   976	
   977			bfq_set_group_with_pending_reqs(bfqd, entity);
   978		}
   979	}
   980	#else
 > 981	#define bfq_update_groups_with_pending_reqs(struct bfq_entity *entity) \
   982		do {} while (0)
   983	#endif
   984	
   985	/**
   986	 * __bfq_activate_entity - handle activation of entity.
   987	 * @entity: the entity being activated.
   988	 * @non_blocking_wait_rq: true if entity was waiting for a request
   989	 *
   990	 * Called for a 'true' activation, i.e., if entity is not active and
   991	 * one of its children receives a new request.
   992	 *
   993	 * Basically, this function updates the timestamps of entity and
   994	 * inserts entity into its active tree, after possibly extracting it
   995	 * from its idle tree.
   996	 */
   997	static void __bfq_activate_entity(struct bfq_entity *entity,
   998					  bool non_blocking_wait_rq)
   999	{
  1000		struct bfq_service_tree *st = bfq_entity_service_tree(entity);
  1001		bool backshifted = false;
  1002		unsigned long long min_vstart;
  1003	
  1004		/* See comments on bfq_fqq_update_budg_for_activation */
  1005		if (non_blocking_wait_rq && bfq_gt(st->vtime, entity->finish)) {
  1006			backshifted = true;
  1007			min_vstart = entity->finish;
  1008		} else
  1009			min_vstart = st->vtime;
  1010	
  1011		if (entity->tree == &st->idle) {
  1012			/*
  1013			 * Must be on the idle tree, bfq_idle_extract() will
  1014			 * check for that.
  1015			 */
  1016			bfq_idle_extract(st, entity);
  1017			entity->start = bfq_gt(min_vstart, entity->finish) ?
  1018				min_vstart : entity->finish;
  1019		} else {
  1020			/*
  1021			 * The finish time of the entity may be invalid, and
  1022			 * it is in the past for sure, otherwise the queue
  1023			 * would have been on the idle tree.
  1024			 */
  1025			entity->start = min_vstart;
  1026			st->wsum += entity->weight;
  1027			/*
  1028			 * entity is about to be inserted into a service tree,
  1029			 * and then set in service: get a reference to make
  1030			 * sure entity does not disappear until it is no
  1031			 * longer in service or scheduled for service.
  1032			 */
  1033			bfq_get_entity(entity);
  1034	
  1035			entity->on_st_or_in_serv = true;
  1036		}
  1037	
> 1038		bfq_update_groups_with_pending_reqs(entity);
  1039		bfq_update_fin_time_enqueue(entity, st, backshifted);
  1040	}
  1041	

---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all@lists.01.org

[-- Attachment #2: .config.gz --]
[-- Type: application/gzip, Size: 34339 bytes --]

Re: [PATCH v3 1/2] block, bfq: counted root group into 'num_groups_with_pending_reqs'

[kernel test robot]

[-- Attachment #1: Type: text/plain, Size: 5153 bytes --]

Hi Yu,

Thank you for the patch! Yet something to improve:

[auto build test ERROR on axboe-block/for-next]
[also build test ERROR on v5.15-rc5 next-20211013]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch]

url:    https://github.com/0day-ci/linux/commits/Yu-Kuai/optimize-the-bfq-queue-idle-judgment/20211013-191413
base:   https://git.kernel.org/pub/scm/linux/kernel/git/axboe/linux-block.git for-next
config: hexagon-randconfig-r045-20211013 (attached as .config)
compiler: clang version 14.0.0 (https://github.com/llvm/llvm-project b6a8c695542b2987eb9a203d5663a0740cb4725f)
reproduce (this is a W=1 build):
        wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
        chmod +x ~/bin/make.cross
        # https://github.com/0day-ci/linux/commit/59e859f9efae59f2fb2a850b44953800e06f5eb0
        git remote add linux-review https://github.com/0day-ci/linux
        git fetch --no-tags linux-review Yu-Kuai/optimize-the-bfq-queue-idle-judgment/20211013-191413
        git checkout 59e859f9efae59f2fb2a850b44953800e06f5eb0
        # save the attached .config to linux build tree
        mkdir build_dir
        COMPILER_INSTALL_PATH=$HOME/0day COMPILER=clang make.cross W=1 O=build_dir ARCH=hexagon SHELL=/bin/bash

If you fix the issue, kindly add following tag as appropriate
Reported-by: kernel test robot <lkp@intel.com>

All errors (new ones prefixed by >>):

>> block/bfq-wf2q.c:981:52: error: expected comma in macro parameter list
   #define bfq_update_groups_with_pending_reqs(struct bfq_entity *entity) \
                                                      ^
>> block/bfq-wf2q.c:1038:2: error: implicit declaration of function 'bfq_update_groups_with_pending_reqs' [-Werror,-Wimplicit-function-declaration]
           bfq_update_groups_with_pending_reqs(entity);
           ^
   2 errors generated.


vim +981 block/bfq-wf2q.c

   958	
   959	static void bfq_update_groups_with_pending_reqs(struct bfq_entity *entity)
   960	{
   961		struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
   962	
   963		if (bfqq) {
   964			/*
   965			 * If the entity represents bfq_queue, and the queue belongs to
   966			 * root cgroup.
   967			 */
   968			if (!entity->parent)
   969				bfq_set_group_with_pending_reqs(bfqq->bfqd,
   970					&bfqq->bfqd->root_group->entity);
   971		} else {
   972			/* If the entity represents bfq_group. */
   973			struct bfq_group *bfqg =
   974				container_of(entity, struct bfq_group, entity);
   975			struct bfq_data *bfqd = bfqg->bfqd;
   976	
   977			bfq_set_group_with_pending_reqs(bfqd, entity);
   978		}
   979	}
   980	#else
 > 981	#define bfq_update_groups_with_pending_reqs(struct bfq_entity *entity) \
   982		do {} while (0)
   983	#endif
   984	
   985	/**
   986	 * __bfq_activate_entity - handle activation of entity.
   987	 * @entity: the entity being activated.
   988	 * @non_blocking_wait_rq: true if entity was waiting for a request
   989	 *
   990	 * Called for a 'true' activation, i.e., if entity is not active and
   991	 * one of its children receives a new request.
   992	 *
   993	 * Basically, this function updates the timestamps of entity and
   994	 * inserts entity into its active tree, after possibly extracting it
   995	 * from its idle tree.
   996	 */
   997	static void __bfq_activate_entity(struct bfq_entity *entity,
   998					  bool non_blocking_wait_rq)
   999	{
  1000		struct bfq_service_tree *st = bfq_entity_service_tree(entity);
  1001		bool backshifted = false;
  1002		unsigned long long min_vstart;
  1003	
  1004		/* See comments on bfq_fqq_update_budg_for_activation */
  1005		if (non_blocking_wait_rq && bfq_gt(st->vtime, entity->finish)) {
  1006			backshifted = true;
  1007			min_vstart = entity->finish;
  1008		} else
  1009			min_vstart = st->vtime;
  1010	
  1011		if (entity->tree == &st->idle) {
  1012			/*
  1013			 * Must be on the idle tree, bfq_idle_extract() will
  1014			 * check for that.
  1015			 */
  1016			bfq_idle_extract(st, entity);
  1017			entity->start = bfq_gt(min_vstart, entity->finish) ?
  1018				min_vstart : entity->finish;
  1019		} else {
  1020			/*
  1021			 * The finish time of the entity may be invalid, and
  1022			 * it is in the past for sure, otherwise the queue
  1023			 * would have been on the idle tree.
  1024			 */
  1025			entity->start = min_vstart;
  1026			st->wsum += entity->weight;
  1027			/*
  1028			 * entity is about to be inserted into a service tree,
  1029			 * and then set in service: get a reference to make
  1030			 * sure entity does not disappear until it is no
  1031			 * longer in service or scheduled for service.
  1032			 */
  1033			bfq_get_entity(entity);
  1034	
  1035			entity->on_st_or_in_serv = true;
  1036		}
  1037	
> 1038		bfq_update_groups_with_pending_reqs(entity);
  1039		bfq_update_fin_time_enqueue(entity, st, backshifted);
  1040	}
  1041	

---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all@lists.01.org

[-- Attachment #2: .config.gz --]
[-- Type: application/gzip, Size: 28686 bytes --]