Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754014AbYKLIhT (ORCPT ); Wed, 12 Nov 2008 03:37:19 -0500 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S1753345AbYKLIgr (ORCPT ); Wed, 12 Nov 2008 03:36:47 -0500 Received: from TYO201.gate.nec.co.jp ([202.32.8.193]:45785 "EHLO tyo201.gate.nec.co.jp" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753298AbYKLIgo (ORCPT ); Wed, 12 Nov 2008 03:36:44 -0500 From: "Satoshi UCHIDA" To: , , , , "'Ryo Tsuruta'" , "'Andrea Righi'" , , , Cc: "'Andrew Morton'" , "'SUGAWARA Tomoyoshi'" , , References: <000c01c9449e$c5bcdc20$51369460$@jp.nec.com> In-Reply-To: <000c01c9449e$c5bcdc20$51369460$@jp.nec.com> Subject: [PATCH][cfq-cgroups][09/12] Develop service tree control. Date: Wed, 12 Nov 2008 17:29:37 +0900 Message-ID: <001601c944a0$ccb01e00$66105a00$@jp.nec.com> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Mailer: Microsoft Office Outlook 12.0 Thread-Index: AclEnsU5YPNAeH0jT4OGyB1wwkbE/wAAfWdA Content-Language: ja Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 13595 Lines: 501 This patch introduces and controls a service tree for cfq data, namely group layer control. This functions expand IPRIO_BE class section of traditional CFQ scheduler. Signed-off-by: Satoshi UCHIDA --- block/cfq-cgroup.c | 266 +++++++++++++++++++++++++++++++++++++++++++ block/cfq-iosched.c | 32 ++++- include/linux/cfq-iosched.h | 32 +++++- 3 files changed, 323 insertions(+), 7 deletions(-) diff --git a/block/cfq-cgroup.c b/block/cfq-cgroup.c index 99f3d94..ff652fe 100644 --- a/block/cfq-cgroup.c +++ b/block/cfq-cgroup.c @@ -15,8 +15,11 @@ #include #include +#define CFQ_CGROUP_SLICE_SCALE (5) #define CFQ_CGROUP_MAX_IOPRIO (7) +static const int cfq_cgroup_slice = HZ / 10; + static struct cfq_ops cfq_cgroup_op; struct cfq_cgroup { @@ -27,6 +30,28 @@ struct cfq_cgroup { unsigned int siblings; }; +enum cfqd_state_flags { + CFQ_CFQD_FLAG_on_rr = 0, /* on round-robin busy list */ + CFQ_CFQD_FLAG_slice_new, /* no requests dispatched in slice */ +}; + +#define CFQ_CFQD_FNS(name) \ +static inline void cfq_mark_cfqd_##name(struct cfq_data *cfqd) \ +{ \ + (cfqd)->flags |= (1 << CFQ_CFQD_FLAG_##name); \ +} \ +static inline void cfq_clear_cfqd_##name(struct cfq_data *cfqd) \ +{ \ + (cfqd)->flags &= ~(1 << CFQ_CFQD_FLAG_##name); \ +} \ +static inline int cfq_cfqd_##name(const struct cfq_data *cfqd) \ +{ \ + return ((cfqd)->flags & (1 << CFQ_CFQD_FLAG_##name)) != 0; \ +} + +CFQ_CFQD_FNS(on_rr); +CFQ_CFQD_FNS(slice_new); +#undef CFQ_CFQD_FNS static inline struct cfq_cgroup *cgroup_to_cfq_cgroup(struct cgroup *cont) { @@ -49,6 +74,11 @@ static void cfq_cgroup_init_driver_data_opt(struct cfq_driver_data *cfqdd, { cfqdd->sibling_tree = RB_ROOT; cfqdd->siblings = 0; + + cfqdd->service_tree = CFQ_RB_ROOT; + cfqdd->busy_data = 0; + + cfqdd->cfq_cgroup_slice = cfq_cgroup_slice; } static void cfq_driver_sibling_tree_add(struct cfq_driver_data *cfqdd, @@ -155,6 +185,8 @@ __cfq_cgroup_init_queue(struct request_queue *q, struct cfq_driver_data *cfqdd) RB_CLEAR_NODE(&cfqd->sib_node); RB_CLEAR_NODE(&cfqd->group_node); + RB_CLEAR_NODE(&cfqd->rb_node); + cfqd->rb_key = 0; cfq_driver_sibling_tree_add(cfqd->cfqdd, cfqd); @@ -294,6 +326,237 @@ static void cfq_cgroup_destroy(struct cgroup_subsys *ss, struct cgroup *cont) /* + * service tree control. + */ +static inline int cfq_cgroup_slice_used(struct cfq_data *cfqd) +{ + if (cfq_cfqd_slice_new(cfqd)) + return 0; + if (time_before(jiffies, cfqd->slice_end)) + return 0; + + return 1; +} + +static inline int +cfq_cgroup_prio_slice(struct cfq_data *cfqd, unsigned short prio) +{ + const int base_slice = cfqd->cfqdd->cfq_cgroup_slice; + + WARN_ON(prio >= IOPRIO_BE_NR); + + return base_slice + (base_slice/CFQ_CGROUP_SLICE_SCALE * + (CFQ_CGROUP_MAX_IOPRIO / 2 - prio)); +} + +static inline void +cfq_cgroup_set_prio_slice(struct cfq_data *cfqd) +{ + cfqd->slice_end = cfq_cgroup_prio_slice(cfqd, cfqd->ioprio) + + jiffies; +} + +static unsigned long cfq_cgroup_slice_offset(struct cfq_data *cfqd) +{ + return (cfqd->cfqdd->busy_data - 1) * + (cfq_cgroup_prio_slice(cfqd, 0) - + cfq_cgroup_prio_slice(cfqd, cfqd->ioprio)); +} + +static void cfq_cgroup_service_tree_add(struct cfq_data *cfqd, int add_front) +{ + struct rb_node **p, *parent; + struct cfq_data *__cfqd; + struct cfq_driver_data *cfqdd = cfqd->cfqdd; + unsigned long rb_key; + int left; + + if (!add_front) { + rb_key = cfq_cgroup_slice_offset(cfqd) + jiffies; + rb_key += cfqd->slice_resid; + cfqd->slice_resid = 0; + } else + rb_key = 0; + + if (!RB_EMPTY_NODE(&cfqd->rb_node)) { + if (rb_key == cfqd->rb_key) + return; + cfq_rb_erase(&cfqd->rb_node, &cfqdd->service_tree); + } + + left = 1; + parent = NULL; + p = &cfqdd->service_tree.rb.rb_node; + while (*p) { + struct rb_node **n; + + parent = *p; + __cfqd = rb_entry(parent, struct cfq_data, rb_node); + + if (rb_key < __cfqd->rb_key) + n = &(*p)->rb_left; + else + n = &(*p)->rb_right; + + if (n == &(*p)->rb_right) + left = 0; + + p = n; + } + + if (left) + cfqdd->service_tree.left = &cfqd->rb_node; + + cfqd->rb_key = rb_key; + rb_link_node(&cfqd->rb_node, parent, p); + rb_insert_color(&cfqd->rb_node, &cfqdd->service_tree.rb); +} + +static void __cfq_cgroup_slice_expired(struct cfq_driver_data *cfqdd, + struct cfq_data *cfqd, int timed_out) +{ + if (timed_out && !cfq_cfqd_slice_new(cfqd)) + cfqd->slice_resid = cfqd->slice_end - jiffies; + + if (cfq_cfqd_on_rr(cfqd)) + cfq_cgroup_service_tree_add(cfqd, 0); + + if (cfqd == cfqdd->active_data) + cfqdd->active_data = NULL; +} + +static inline void +cfq_cgroup_slice_expired(struct cfq_driver_data *cfqdd, int timed_out) +{ + struct cfq_data *cfqd = cfqdd->active_data; + + if (cfqd) { + cfq_slice_expired(cfqd, 1); + __cfq_cgroup_slice_expired(cfqdd, cfqd, timed_out); + } +} + +static struct cfq_data *cfq_cgroup_rb_first(struct cfq_rb_root *root) +{ + if (!root->left) + root->left = rb_first(&root->rb); + + if (root->left) + return rb_entry(root->left, struct cfq_data, rb_node); + + return NULL; +} + +static struct cfq_data *cfq_cgroup_get_next_data(struct cfq_driver_data *cfqdd) +{ + if (RB_EMPTY_ROOT(&cfqdd->service_tree.rb)) + return NULL; + + return cfq_cgroup_rb_first(&cfqdd->service_tree); +} + +static void __cfq_cgroup_set_active_data(struct cfq_driver_data*cfqdd, + struct cfq_data *cfqd) +{ + if (cfqd) { + cfqd->slice_end = 0; + cfq_mark_cfqd_slice_new(cfqd); + } + + cfqdd->active_data = cfqd; +} + +static struct cfq_data * +cfq_cgroup_set_active_data(struct cfq_driver_data *cfqdd) +{ + struct cfq_data *cfqd; + + cfqd = cfq_cgroup_get_next_data(cfqdd); + __cfq_cgroup_set_active_data(cfqdd , cfqd); + + return cfqd; +} + +struct cfq_data *cfq_cgroup_select_data(struct cfq_driver_data *cfqdd) +{ + struct cfq_data *cfqd; + + cfqd = cfqdd->active_data; + if (!cfqd) + goto new_data; + + if (cfq_cgroup_slice_used(cfqd)) + goto expire; + + if (!RB_EMPTY_ROOT(&cfqd->service_tree.rb)) + goto keep_data; + + if (wait_request_checker(cfqd)) + goto keep_data; + +expire: + cfq_cgroup_slice_expired(cfqdd, 0); +new_data: + cfqd = cfq_cgroup_set_active_data(cfqdd); +keep_data: + return cfqd; +} + +int cfq_cgroup_forced_dispatch(struct cfq_data *cfqd) +{ + struct cfq_driver_data *cfqdd = cfqd->cfqdd; + int dispatched = 0; + + while ((cfqd = cfq_cgroup_rb_first(&cfqdd->service_tree)) != NULL) + dispatched += cfq_forced_dispatch(cfqd); + + cfq_cgroup_slice_expired(cfqdd, 0); + + BUG_ON(cfqdd->busy_data); + + return dispatched; +} + +int cfq_cgroup_dispatch_requests(struct request_queue *q, int force) +{ + struct cfq_data *cfqd = q->elevator->elevator_data; + struct cfq_driver_data *cfqdd = cfqd->cfqdd; + int dispatched; + + if (!cfqdd->busy_data) + return 0; + + if (unlikely(force)) + return cfq_cgroup_forced_dispatch(cfqd); + + dispatched = 0; + cfqd = cfq_cgroup_select_data(cfqdd); + + if (cfqd) + dispatched = cfq_queue_dispatch_requests(cfqd, force); + + return dispatched; +} + +int cfq_cgroup_completed_request_opt(struct cfq_data *cfqd) +{ + if (cfqd->cfqdd->active_data == cfqd) { + if (cfq_cfqd_slice_new(cfqd)) { + cfq_cgroup_set_prio_slice(cfqd); + cfq_clear_cfqd_slice_new(cfqd); + + } + if (cfq_cgroup_slice_used(cfqd)) { + cfq_cgroup_slice_expired(cfqd->cfqdd, 1); + return 0; + } + return 1; + } + + return 0; +} + +/* * cgroupfs parts below --> */ static void @@ -680,6 +943,7 @@ static struct elevator_type iosched_cfq_cgroup = { static struct cfq_ops cfq_cgroup_op = { .cfq_init_driver_data_opt_fn = cfq_cgroup_init_driver_data_opt, + .cfq_completed_request_opt_fn = cfq_cgroup_completed_request_opt, }; static int __init cfq_cgroup_init(void) @@ -687,6 +951,8 @@ static int __init cfq_cgroup_init(void) iosched_cfq_cgroup.ops = iosched_cfq.ops; iosched_cfq_cgroup.ops.elevator_init_fn = cfq_cgroup_init_queue; iosched_cfq_cgroup.ops.elevator_exit_fn = cfq_cgroup_exit_queue; + iosched_cfq_cgroup.ops.elevator_dispatch_fn = + cfq_cgroup_dispatch_requests, elv_register(&iosched_cfq_cgroup); diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c index fd1ed0c..5fbef85 100644 --- a/block/cfq-iosched.c +++ b/block/cfq-iosched.c @@ -354,7 +354,7 @@ static struct cfq_queue *cfq_rb_first(struct cfq_rb_root *root) return NULL; } -static void cfq_rb_erase(struct rb_node *n, struct cfq_rb_root *root) +void cfq_rb_erase(struct rb_node *n, struct cfq_rb_root *root) { if (root->left == n) root->left = NULL; @@ -751,7 +751,7 @@ __cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq, } } -static inline void cfq_slice_expired(struct cfq_data *cfqd, int timed_out) +inline void cfq_slice_expired(struct cfq_data *cfqd, int timed_out) { struct cfq_queue *cfqq = cfqd->active_queue; @@ -932,6 +932,16 @@ cfq_prio_to_maxrq(struct cfq_data *cfqd, struct cfq_queue *cfqq) return 2 * (base_rq + base_rq * (CFQ_PRIO_LISTS - 1 - cfqq->ioprio)); } +int wait_request_checker(struct cfq_data *cfqd) +{ + struct cfq_queue *cfqq = cfqd->active_queue; + if (cfqq) + return timer_pending(&cfqd->cfqdd->idle_slice_timer) + || (cfqq->dispatched && cfq_cfqq_idle_window(cfqq)); + else + return 0; +} + /* * Select a queue for service. If we have a current active queue, * check whether to continue servicing it, or retrieve and set a new one. @@ -1047,7 +1057,7 @@ static int __cfq_forced_dispatch_cfqq(struct cfq_queue *cfqq) * Drain our current requests. Used for barriers and when switching * io schedulers on-the-fly. */ -static int cfq_forced_dispatch(struct cfq_data *cfqd) +int cfq_forced_dispatch(struct cfq_data *cfqd) { struct cfq_queue *cfqq; int dispatched = 0; @@ -1063,9 +1073,8 @@ static int cfq_forced_dispatch(struct cfq_data *cfqd) return dispatched; } -static int cfq_dispatch_requests(struct request_queue *q, int force) +int cfq_queue_dispatch_requests(struct cfq_data *cfqd, int force) { - struct cfq_data *cfqd = q->elevator->elevator_data; struct cfq_queue *cfqq; struct cfq_driver_data *cfqdd = cfqd->cfqdd; int dispatched; @@ -1105,6 +1114,13 @@ static int cfq_dispatch_requests(struct request_queue *q, int force) return dispatched; } +static int cfq_dispatch_requests(struct request_queue *q, int force) +{ + struct cfq_data *cfqd = q->elevator->elevator_data; + + return cfq_queue_dispatch_requests(cfqd, force); +} + /* * task holds one reference to the queue, dropped when task exits. each rq * in-flight on this queue also holds a reference, dropped when rq is freed. @@ -1876,6 +1892,7 @@ static void cfq_completed_request(struct request_queue *q, struct request *rq) struct cfq_driver_data *cfqdd = cfqd->cfqdd; const int sync = rq_is_sync(rq); unsigned long now; + int flag = 1; now = jiffies; cfq_log_cfqq(cfqd, cfqq, "complete"); @@ -1900,7 +1917,10 @@ static void cfq_completed_request(struct request_queue *q, struct request *rq) * If this is the active queue, check if it needs to be expired, * or if we want to idle in case it has no pending requests. */ - if (cfqd->active_queue == cfqq) { + if (cfqd->cfqdd->op->cfq_completed_request_opt_fn) + flag = cfqd->cfqdd->op->cfq_completed_request_opt_fn(cfqd); + + if ((flag) && (cfqd->active_queue == cfqq)) { if (cfq_cfqq_slice_new(cfqq)) { cfq_set_prio_slice(cfqd, cfqq); cfq_clear_cfqq_slice_new(cfqq); diff --git a/include/linux/cfq-iosched.h b/include/linux/cfq-iosched.h index b58d476..30702c9 100644 --- a/include/linux/cfq-iosched.h +++ b/include/linux/cfq-iosched.h @@ -54,6 +54,15 @@ struct cfq_driver_data { /* device siblings */ struct rb_root sibling_tree; unsigned int siblings; + + /* + * rr list of cfq_data with requests and the count of them + */ + struct cfq_rb_root service_tree; + unsigned int busy_data; + struct cfq_data *active_data; + + unsigned int cfq_cgroup_slice; #endif }; @@ -100,6 +109,20 @@ struct cfq_data { struct cfq_cgroup *cfqc; /* group_tree member for cfq_cgroup */ struct rb_node group_node; + + /* service_tree member */ + struct rb_node rb_node; + /* service_tree key */ + unsigned long rb_key; + + /* + * slice parameter + */ + unsigned long slice_end; + long slice_resid; + + /* various state flags, see below */ + unsigned int flags; #endif }; @@ -108,14 +131,21 @@ struct cfq_data { */ typedef void (cfq_init_driver_data_opt_fn)(struct cfq_driver_data *, struct cfq_data *); +typedef int (cfq_completed_request_opt_fn)(struct cfq_data *); struct cfq_ops { cfq_init_driver_data_opt_fn *cfq_init_driver_data_opt_fn; + cfq_completed_request_opt_fn *cfq_completed_request_opt_fn; }; extern struct elevator_type iosched_cfq; extern struct cfq_data *cfq_init_cfq_data(struct request_queue *, struct cfq_driver_data *, struct cfq_ops *); -extern void cfq_free_cfq_data(struct cfq_data *cfqd); +extern void cfq_free_cfq_data(struct cfq_data *); +extern void cfq_rb_erase(struct rb_node *, struct cfq_rb_root *); +extern void cfq_slice_expired(struct cfq_data *, int); +extern int wait_request_checker(struct cfq_data *cfqd); +extern int cfq_forced_dispatch(struct cfq_data *); +extern int cfq_queue_dispatch_requests(struct cfq_data *, int); #endif /* _LINUX_CFQ_IOSCHED_H */ -- 1.5.6.5 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/