From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932280AbcHNO1l (ORCPT ); Sun, 14 Aug 2016 10:27:41 -0400 Received: from ms01.sssup.it ([193.205.80.99]:31224 "EHLO sssup.it" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S932178AbcHNO1j (ORCPT ); Sun, 14 Aug 2016 10:27:39 -0400 From: Tommaso Cucinotta To: Luca Abeni , Juri Lelli , Peter Zijlstra , Ingo Molnar Cc: linux-kernel@vger.kernel.org, linux-dl@retis.sssup.it, Tommaso Cucinotta , Juri Lelli Subject: [RFC PATCH 1/3] sched/deadline: refactor cpu heap code Date: Sun, 14 Aug 2016 16:27:06 +0200 Message-Id: <1471184828-12644-2-git-send-email-tommaso.cucinotta@sssup.it> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1471184828-12644-1-git-send-email-tommaso.cucinotta@sssup.it> References: <1468880275-4338-1-git-send-email-tommaso.cucinotta@sssup.it> <1471184828-12644-1-git-send-email-tommaso.cucinotta@sssup.it> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 1. heapify up factored out in new dedicated function heapify_up() (avoids repetition of same code) 2. call to cpudl_change_key() replaced with heapify_up() when cpudl_set actually inserts a new node in the heap 3. cpudl_change_key() replaced with heapify() that heapifies up or down as needed. Cc: Peter Zijlstra Cc: Juri Lelli Cc: Luca Abeni Reviewed-by: Luca Abeni Reviewed-by: Juri Lelli Signed-off-by: Tommaso Cucinotta --- kernel/sched/cpudeadline.c | 50 +++++++++++++++++++++------------------------- 1 file changed, 23 insertions(+), 27 deletions(-) diff --git a/kernel/sched/cpudeadline.c b/kernel/sched/cpudeadline.c index d418449..0acb0d4 100644 --- a/kernel/sched/cpudeadline.c +++ b/kernel/sched/cpudeadline.c @@ -41,7 +41,7 @@ static void cpudl_exchange(struct cpudl *cp, int a, int b) swap(cp->elements[cpu_a].idx, cp->elements[cpu_b].idx); } -static void cpudl_heapify(struct cpudl *cp, int idx) +static void cpudl_heapify_down(struct cpudl *cp, int idx) { int l, r, largest; @@ -66,23 +66,24 @@ static void cpudl_heapify(struct cpudl *cp, int idx) } } -static void cpudl_change_key(struct cpudl *cp, int idx, u64 new_dl) +static void cpudl_heapify_up(struct cpudl *cp, int idx) { - WARN_ON(idx == IDX_INVALID || !cpu_present(idx)); - - if (dl_time_before(new_dl, cp->elements[idx].dl)) { - cp->elements[idx].dl = new_dl; - cpudl_heapify(cp, idx); - } else { - cp->elements[idx].dl = new_dl; - while (idx > 0 && dl_time_before(cp->elements[parent(idx)].dl, - cp->elements[idx].dl)) { - cpudl_exchange(cp, idx, parent(idx)); - idx = parent(idx); - } + while (idx > 0 && dl_time_before(cp->elements[parent(idx)].dl, + cp->elements[idx].dl)) { + cpudl_exchange(cp, idx, parent(idx)); + idx = parent(idx); } } +static void cpudl_heapify(struct cpudl *cp, int idx) +{ + if (idx > 0 && dl_time_before(cp->elements[parent(idx)].dl, + cp->elements[idx].dl)) + cpudl_heapify_up(cp, idx); + else + cpudl_heapify_down(cp, idx); +} + static inline int cpudl_maximum(struct cpudl *cp) { return cp->elements[0].cpu; @@ -154,27 +155,22 @@ void cpudl_set(struct cpudl *cp, int cpu, u64 dl, int is_valid) cp->size--; cp->elements[new_cpu].idx = old_idx; cp->elements[cpu].idx = IDX_INVALID; - while (old_idx > 0 && dl_time_before( - cp->elements[parent(old_idx)].dl, - cp->elements[old_idx].dl)) { - cpudl_exchange(cp, old_idx, parent(old_idx)); - old_idx = parent(old_idx); - } + cpudl_heapify(cp, old_idx); cpumask_set_cpu(cpu, cp->free_cpus); - cpudl_heapify(cp, old_idx); goto out; } if (old_idx == IDX_INVALID) { - cp->size++; - cp->elements[cp->size - 1].dl = dl; - cp->elements[cp->size - 1].cpu = cpu; - cp->elements[cpu].idx = cp->size - 1; - cpudl_change_key(cp, cp->size - 1, dl); + int new_idx = cp->size++; + cp->elements[new_idx].dl = dl; + cp->elements[new_idx].cpu = cpu; + cp->elements[cpu].idx = new_idx; + cpudl_heapify_up(cp, new_idx); cpumask_clear_cpu(cpu, cp->free_cpus); } else { - cpudl_change_key(cp, old_idx, dl); + cp->elements[old_idx].dl = dl; + cpudl_heapify(cp, old_idx); } out: -- 2.7.4