From: Vivek Goyal <vgoyal@redhat.com> To: linux-kernel@vger.kernel.org, containers@lists.linux-foundation.org, dm-devel@redhat.com, jens.axboe@oracle.com, nauman@google.com, dpshah@google.com, ryov@valinux.co.jp, guijianfeng@cn.fujitsu.com, balbir@linux.vnet.ibm.com, righi.andrea@gmail.com Cc: lizf@cn.fujitsu.com, mikew@google.com, fchecconi@gmail.com, paolo.valente@unimore.it, fernando@oss.ntt.co.jp, s-uchida@ap.jp.nec.com, taka@valinux.co.jp, jmoyer@redhat.com, dhaval@linux.vnet.ibm.com, m-ikeda@ds.jp.nec.com, agk@redhat.com, vgoyal@redhat.com, akpm@linux-foundation.org, peterz@infradead.org Subject: [PATCH 03/24] io-controller: bfq support of in-class preemption Date: Fri, 24 Jul 2009 16:27:33 -0400 [thread overview] Message-ID: <1248467274-32073-4-git-send-email-vgoyal@redhat.com> (raw) In-Reply-To: <1248467274-32073-1-git-send-email-vgoyal@redhat.com> o Generally preemption is associated with cross class where if an request from RT class is pending it will preempt the ongoing BE or IDLE class request. o CFQ also does in-class preemtions like a sync request queue preempting the async request queue. In that case it looks like preempting queue gains share and it is not fair. o Implement the similar functionality in bfq so that we can retain the existing CFQ behavior. o This patch creates a bypass path so that a queue can be put at the front of the service tree (add_front, similar to CFQ), so that it will be selected next to run. That's a different thing that in the process this queue gains share. Signed-off-by: Vivek Goyal <vgoyal@redhat.com> --- block/elevator-fq.c | 46 +++++++++++++++++++++++++++++++++++++++++----- 1 files changed, 41 insertions(+), 5 deletions(-) diff --git a/block/elevator-fq.c b/block/elevator-fq.c index e5f39cf..f1ab0dc 100644 --- a/block/elevator-fq.c +++ b/block/elevator-fq.c @@ -267,7 +267,8 @@ static void bfq_get_entity(struct io_entity *entity) elv_get_ioq(ioq); } -static void bfq_init_entity(struct io_entity *entity, struct io_group *iog) +static inline void +bfq_init_entity(struct io_entity *entity, struct io_group *iog) { entity->sched_data = &iog->sched_data; } @@ -580,7 +581,7 @@ static struct io_entity *bfq_lookup_next_entity(struct io_sched_data *sd, * service received if @entity is active) of the queue to calculate its * timestamps. */ -static void __bfq_activate_entity(struct io_entity *entity) +static void __bfq_activate_entity(struct io_entity *entity, int add_front) { struct io_sched_data *sd = entity->sched_data; struct io_service_tree *st = io_entity_service_tree(entity); @@ -625,7 +626,42 @@ static void __bfq_activate_entity(struct io_entity *entity) } st = __bfq_entity_update_prio(st, entity); - bfq_calc_finish(entity, entity->budget); + /* + * This is to emulate cfq like functionality where preemption can + * happen with-in same class, like sync queue preempting async queue + * May be this is not a very good idea from fairness point of view + * as preempting queue gains share. Keeping it for now. + */ + if (add_front) { + struct io_entity *next_entity; + + /* + * Determine the entity which will be dispatched next + * Use sd->next_active once hierarchical patch is applied + */ + next_entity = bfq_lookup_next_entity(sd, 0); + + if (next_entity && next_entity != entity) { + struct io_service_tree *new_st; + u64 delta; + + new_st = io_entity_service_tree(next_entity); + + /* + * At this point, both entities should belong to + * same service tree as cross service tree preemption + * is automatically taken care by algorithm + */ + BUG_ON(new_st != st); + entity->finish = next_entity->finish - 1; + delta = bfq_delta(entity->budget, entity->weight); + entity->start = entity->finish - delta; + if (bfq_gt(entity->start, st->vtime)) + entity->start = st->vtime; + } + } else { + bfq_calc_finish(entity, entity->budget); + } bfq_active_insert(st, entity); } @@ -633,9 +669,9 @@ static void __bfq_activate_entity(struct io_entity *entity) * bfq_activate_entity - activate an entity. * @entity: the entity to activate. */ -static void bfq_activate_entity(struct io_entity *entity) +static void bfq_activate_entity(struct io_entity *entity, int add_front) { - __bfq_activate_entity(entity); + __bfq_activate_entity(entity, add_front); } /** -- 1.6.0.6
WARNING: multiple messages have this Message-ID (diff)
From: Vivek Goyal <vgoyal@redhat.com> To: linux-kernel@vger.kernel.org, containers@lists.linux-foundation.org, dm-devel@redhat.com, jens.axboe@oracle.com, nauman@google.com, dpshah@google.com, ryov@valinux.co.jp, guijianfeng@c Cc: paolo.valente@unimore.it, dhaval@linux.vnet.ibm.com, peterz@infradead.org, fernando@oss.ntt.co.jp, lizf@cn.fujitsu.com, jmoyer@redhat.com, mikew@google.com, fchecconi@gmail.com, vgoyal@redhat.com, s-uchida@ap.jp.nec.com, akpm@linux-foundation.org, agk@redhat.com, m-ikeda@ds.jp.nec.com Subject: [PATCH 03/24] io-controller: bfq support of in-class preemption Date: Fri, 24 Jul 2009 16:27:33 -0400 [thread overview] Message-ID: <1248467274-32073-4-git-send-email-vgoyal@redhat.com> (raw) In-Reply-To: <1248467274-32073-1-git-send-email-vgoyal@redhat.com> o Generally preemption is associated with cross class where if an request from RT class is pending it will preempt the ongoing BE or IDLE class request. o CFQ also does in-class preemtions like a sync request queue preempting the async request queue. In that case it looks like preempting queue gains share and it is not fair. o Implement the similar functionality in bfq so that we can retain the existing CFQ behavior. o This patch creates a bypass path so that a queue can be put at the front of the service tree (add_front, similar to CFQ), so that it will be selected next to run. That's a different thing that in the process this queue gains share. Signed-off-by: Vivek Goyal <vgoyal@redhat.com> --- block/elevator-fq.c | 46 +++++++++++++++++++++++++++++++++++++++++----- 1 files changed, 41 insertions(+), 5 deletions(-) diff --git a/block/elevator-fq.c b/block/elevator-fq.c index e5f39cf..f1ab0dc 100644 --- a/block/elevator-fq.c +++ b/block/elevator-fq.c @@ -267,7 +267,8 @@ static void bfq_get_entity(struct io_entity *entity) elv_get_ioq(ioq); } -static void bfq_init_entity(struct io_entity *entity, struct io_group *iog) +static inline void +bfq_init_entity(struct io_entity *entity, struct io_group *iog) { entity->sched_data = &iog->sched_data; } @@ -580,7 +581,7 @@ static struct io_entity *bfq_lookup_next_entity(struct io_sched_data *sd, * service received if @entity is active) of the queue to calculate its * timestamps. */ -static void __bfq_activate_entity(struct io_entity *entity) +static void __bfq_activate_entity(struct io_entity *entity, int add_front) { struct io_sched_data *sd = entity->sched_data; struct io_service_tree *st = io_entity_service_tree(entity); @@ -625,7 +626,42 @@ static void __bfq_activate_entity(struct io_entity *entity) } st = __bfq_entity_update_prio(st, entity); - bfq_calc_finish(entity, entity->budget); + /* + * This is to emulate cfq like functionality where preemption can + * happen with-in same class, like sync queue preempting async queue + * May be this is not a very good idea from fairness point of view + * as preempting queue gains share. Keeping it for now. + */ + if (add_front) { + struct io_entity *next_entity; + + /* + * Determine the entity which will be dispatched next + * Use sd->next_active once hierarchical patch is applied + */ + next_entity = bfq_lookup_next_entity(sd, 0); + + if (next_entity && next_entity != entity) { + struct io_service_tree *new_st; + u64 delta; + + new_st = io_entity_service_tree(next_entity); + + /* + * At this point, both entities should belong to + * same service tree as cross service tree preemption + * is automatically taken care by algorithm + */ + BUG_ON(new_st != st); + entity->finish = next_entity->finish - 1; + delta = bfq_delta(entity->budget, entity->weight); + entity->start = entity->finish - delta; + if (bfq_gt(entity->start, st->vtime)) + entity->start = st->vtime; + } + } else { + bfq_calc_finish(entity, entity->budget); + } bfq_active_insert(st, entity); } @@ -633,9 +669,9 @@ static void __bfq_activate_entity(struct io_entity *entity) * bfq_activate_entity - activate an entity. * @entity: the entity to activate. */ -static void bfq_activate_entity(struct io_entity *entity) +static void bfq_activate_entity(struct io_entity *entity, int add_front) { - __bfq_activate_entity(entity); + __bfq_activate_entity(entity, add_front); } /** -- 1.6.0.6
next prev parent reply other threads:[~2009-07-24 20:33 UTC|newest] Thread overview: 120+ messages / expand[flat|nested] mbox.gz Atom feed top 2009-07-24 20:27 [RFC] IO scheduler based IO controller V7 Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal 2009-07-24 20:27 ` [PATCH 01/24] io-controller: Documentation Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal 2009-07-24 20:27 ` [PATCH 02/24] io-controller: Core of the B-WF2Q+ scheduler Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal [this message] 2009-07-24 20:27 ` [PATCH 03/24] io-controller: bfq support of in-class preemption Vivek Goyal 2009-07-27 16:54 ` Jerome Marchand [not found] ` <4A6DDBDE.8020608-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> 2009-07-27 22:41 ` Vivek Goyal 2009-07-27 22:41 ` Vivek Goyal 2009-07-27 22:41 ` Vivek Goyal [not found] ` <20090727224138.GA3702-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> 2009-07-28 11:44 ` Jerome Marchand 2009-07-28 11:44 ` Jerome Marchand 2009-07-28 13:52 ` Vivek Goyal 2009-07-28 13:52 ` Vivek Goyal 2009-07-28 14:29 ` Jerome Marchand 2009-07-28 15:03 ` Vivek Goyal 2009-07-28 15:03 ` Vivek Goyal 2009-07-28 15:37 ` Jerome Marchand [not found] ` <4A6F1B4F.6080709-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> 2009-07-28 18:45 ` Vivek Goyal 2009-07-28 18:45 ` Vivek Goyal 2009-07-28 18:45 ` Vivek Goyal [not found] ` <20090728150310.GA3870-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> 2009-07-28 15:37 ` Jerome Marchand [not found] ` <4A6F0B32.7060801-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> 2009-07-28 15:03 ` Vivek Goyal [not found] ` <20090728135212.GC6133-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> 2009-07-28 14:29 ` Jerome Marchand [not found] ` <4A6EE4A0.6080700-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> 2009-07-28 13:52 ` Vivek Goyal [not found] ` <1248467274-32073-4-git-send-email-vgoyal-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> 2009-07-27 16:54 ` Jerome Marchand 2009-07-24 20:27 ` [PATCH 04/24] io-controller: Common flat fair queuing code in elevaotor layer Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal 2009-07-24 20:27 ` [PATCH 05/24] io-controller: Modify cfq to make use of flat elevator fair queuing Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal [not found] ` <1248467274-32073-6-git-send-email-vgoyal-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> 2009-07-30 6:30 ` Gui Jianfeng 2009-07-30 15:42 ` Jerome Marchand 2009-07-30 6:30 ` Gui Jianfeng [not found] ` <4A713E10.2030204-BthXqXjhjHXQFUHtdCDX3A@public.gmane.org> 2009-07-31 13:18 ` Vivek Goyal 2009-07-31 13:18 ` Vivek Goyal 2009-07-31 13:18 ` Vivek Goyal 2009-07-30 15:42 ` Jerome Marchand [not found] ` <4A71BF76.6040709-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> 2009-07-30 18:30 ` Vivek Goyal 2009-07-30 18:30 ` Vivek Goyal 2009-07-30 18:30 ` Vivek Goyal 2009-07-24 20:27 ` [PATCH 06/24] io-controller: core bfq scheduler changes for hierarchical setup Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal 2009-07-24 20:27 ` [PATCH 07/24] io-controller: cgroup related changes for hierarchical group support Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal 2009-07-24 20:27 ` [PATCH 08/24] io-controller: Common hierarchical fair queuing code in elevaotor layer Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal 2009-07-24 20:27 ` [PATCH 09/24] io-controller: cfq changes to use " Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal 2009-07-24 20:27 ` [PATCH 11/24] io-controller: Debug hierarchical IO scheduling Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal 2009-07-24 20:27 ` [PATCH 12/24] io-controller: Introduce group idling Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal 2009-07-24 20:27 ` [PATCH 13/24] io-controller: Wait for requests to complete from last queue before new queue is scheduled Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal 2009-07-24 20:27 ` [PATCH 14/24] io-controller: Separate out queue and data Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal 2009-07-24 20:27 ` [PATCH 15/24] io-conroller: Prepare elevator layer for single queue schedulers Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal 2009-07-24 20:27 ` [PATCH 16/24] io-controller: noop changes for hierarchical fair queuing Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal 2009-07-24 20:27 ` [PATCH 17/24] io-controller: deadline " Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal 2009-07-24 20:27 ` [PATCH 18/24] io-controller: anticipatory " Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal [not found] ` <1248467274-32073-1-git-send-email-vgoyal-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> 2009-07-24 20:27 ` [PATCH 01/24] io-controller: Documentation Vivek Goyal 2009-07-24 20:27 ` [PATCH 02/24] io-controller: Core of the B-WF2Q+ scheduler Vivek Goyal 2009-07-24 20:27 ` [PATCH 03/24] io-controller: bfq support of in-class preemption Vivek Goyal 2009-07-24 20:27 ` [PATCH 04/24] io-controller: Common flat fair queuing code in elevaotor layer Vivek Goyal 2009-07-24 20:27 ` [PATCH 05/24] io-controller: Modify cfq to make use of flat elevator fair queuing Vivek Goyal 2009-07-24 20:27 ` [PATCH 06/24] io-controller: core bfq scheduler changes for hierarchical setup Vivek Goyal 2009-07-24 20:27 ` [PATCH 07/24] io-controller: cgroup related changes for hierarchical group support Vivek Goyal 2009-07-24 20:27 ` [PATCH 08/24] io-controller: Common hierarchical fair queuing code in elevaotor layer Vivek Goyal 2009-07-24 20:27 ` [PATCH 09/24] io-controller: cfq changes to use " Vivek Goyal 2009-07-24 20:27 ` [PATCH 10/24] io-controller: Export disk time used and nr sectors dipatched through cgroups Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal 2009-07-24 20:27 ` [PATCH 11/24] io-controller: Debug hierarchical IO scheduling Vivek Goyal 2009-07-24 20:27 ` [PATCH 12/24] io-controller: Introduce group idling Vivek Goyal 2009-07-24 20:27 ` [PATCH 13/24] io-controller: Wait for requests to complete from last queue before new queue is scheduled Vivek Goyal 2009-07-24 20:27 ` [PATCH 14/24] io-controller: Separate out queue and data Vivek Goyal 2009-07-24 20:27 ` [PATCH 15/24] io-conroller: Prepare elevator layer for single queue schedulers Vivek Goyal 2009-07-24 20:27 ` [PATCH 16/24] io-controller: noop changes for hierarchical fair queuing Vivek Goyal 2009-07-24 20:27 ` [PATCH 17/24] io-controller: deadline " Vivek Goyal 2009-07-24 20:27 ` [PATCH 18/24] io-controller: anticipatory " Vivek Goyal 2009-07-24 20:27 ` [PATCH 19/24] blkio_cgroup patches from Ryo to track async bios Vivek Goyal 2009-07-24 20:27 ` [PATCH 20/24] io-controller: map async requests to appropriate cgroup Vivek Goyal 2009-07-24 20:27 ` [PATCH 21/24] io-controller: Per cgroup request descriptor support Vivek Goyal 2009-07-24 20:27 ` [PATCH 22/24] io-controller: Per io group bdi congestion interface Vivek Goyal 2009-07-24 20:27 ` [PATCH 23/24] io-controller: Support per cgroup per device weights and io class Vivek Goyal 2009-07-24 20:27 ` [PATCH 24/24] map sync requests to group using bio tracking info Vivek Goyal 2009-07-31 5:21 ` [RFC] IO scheduler based IO controller V7 Gui Jianfeng 2009-07-24 20:27 ` [PATCH 19/24] blkio_cgroup patches from Ryo to track async bios Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal 2009-07-24 20:27 ` [PATCH 20/24] io-controller: map async requests to appropriate cgroup Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal 2009-07-24 20:27 ` [PATCH 21/24] io-controller: Per cgroup request descriptor support Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal 2009-07-24 20:27 ` [PATCH 22/24] io-controller: Per io group bdi congestion interface Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal 2009-08-08 8:14 ` Gui Jianfeng [not found] ` <1248467274-32073-23-git-send-email-vgoyal-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> 2009-08-08 8:14 ` Gui Jianfeng 2009-07-24 20:27 ` [PATCH 23/24] io-controller: Support per cgroup per device weights and io class Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal 2009-07-24 20:27 ` [PATCH 24/24] map sync requests to group using bio tracking info Vivek Goyal 2009-07-24 20:27 ` Vivek Goyal 2009-07-31 5:21 ` [RFC] IO scheduler based IO controller V7 Gui Jianfeng 2009-07-31 5:21 ` Gui Jianfeng [not found] ` <4A727F6F.9010005-BthXqXjhjHXQFUHtdCDX3A@public.gmane.org> 2009-07-31 13:13 ` Vivek Goyal 2009-07-31 13:13 ` Vivek Goyal 2009-07-31 13:13 ` Vivek Goyal 2009-08-03 0:40 ` Gui Jianfeng 2009-08-04 0:48 ` Gui Jianfeng [not found] ` <4A778540.5050502-BthXqXjhjHXQFUHtdCDX3A@public.gmane.org> 2009-08-04 1:30 ` Vivek Goyal 2009-08-04 1:30 ` Vivek Goyal 2009-08-04 1:30 ` Vivek Goyal 2009-08-18 0:42 ` Gui Jianfeng [not found] ` <20090804013001.GB2282-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> 2009-08-18 0:42 ` Gui Jianfeng [not found] ` <20090731131359.GA3668-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> 2009-08-03 0:40 ` Gui Jianfeng 2009-08-04 0:48 ` Gui Jianfeng
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=1248467274-32073-4-git-send-email-vgoyal@redhat.com \ --to=vgoyal@redhat.com \ --cc=agk@redhat.com \ --cc=akpm@linux-foundation.org \ --cc=balbir@linux.vnet.ibm.com \ --cc=containers@lists.linux-foundation.org \ --cc=dhaval@linux.vnet.ibm.com \ --cc=dm-devel@redhat.com \ --cc=dpshah@google.com \ --cc=fchecconi@gmail.com \ --cc=fernando@oss.ntt.co.jp \ --cc=guijianfeng@cn.fujitsu.com \ --cc=jens.axboe@oracle.com \ --cc=jmoyer@redhat.com \ --cc=linux-kernel@vger.kernel.org \ --cc=lizf@cn.fujitsu.com \ --cc=m-ikeda@ds.jp.nec.com \ --cc=mikew@google.com \ --cc=nauman@google.com \ --cc=paolo.valente@unimore.it \ --cc=peterz@infradead.org \ --cc=righi.andrea@gmail.com \ --cc=ryov@valinux.co.jp \ --cc=s-uchida@ap.jp.nec.com \ --cc=taka@valinux.co.jp \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.