From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752154AbcEQWnV (ORCPT ); Tue, 17 May 2016 18:43:21 -0400 Received: from ms01.sssup.it ([193.205.80.99]:29092 "EHLO sssup.it" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752008AbcEQWnU (ORCPT ); Tue, 17 May 2016 18:43:20 -0400 Subject: Re: SCHED_DEADLINE cpudeadline.{h,c} fixup To: luca abeni References: <5739EE84.9070801@sssup.it> <20160517134655.266c7201@utopia> Cc: linux-kernel , Peter Zijlstra , Juri Lelli , mingo@redhat.com From: Tommaso Cucinotta Message-ID: <573B9E82.3040502@sssup.it> Date: Wed, 18 May 2016 00:43:14 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.7.2 MIME-Version: 1.0 In-Reply-To: <20160517134655.266c7201@utopia> Content-Type: multipart/mixed; boundary="------------020307070905030608090506" Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org This is a multi-part message in MIME format. --------------020307070905030608090506 Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 7bit On 17/05/2016 13:46, luca abeni wrote: > Maybe the ... change can be split in a separate > patch, which is a bugfix (and IMHO uncontroversial)? Ok, the bugfix alone might look like the attached. Couldn't avoid the little refactoring of the multiple occurrences of the same loop up the heap into the heapify_up(), mirroring the heapify() that was already there (renamed heapify_down() for clarity). I'll rebase the speed-up patch on top of this, if it's a better approach. Anyone with further comments? Thanks again! T. -- Tommaso Cucinotta, Computer Engineering PhD Associate Professor at the Real-Time Systems Laboratory (ReTiS) Scuola Superiore Sant'Anna, Pisa, Italy http://retis.sssup.it/people/tommaso --------------020307070905030608090506 Content-Type: text/x-patch; name="0001-Deadline-wrap-around-bugfix-for-the-SCHED_DEADLINE-c.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename*0="0001-Deadline-wrap-around-bugfix-for-the-SCHED_DEADLINE-c.pa"; filename*1="tch" >>From cfaa75eb77843f7da875a54c7e6631b271bf0663 Mon Sep 17 00:00:00 2001 From: Tommaso Cucinotta Date: Tue, 17 May 2016 15:54:11 +0200 Subject: [PATCH] Deadline wrap-around bugfix for the SCHED_DEADLINE cpu heap. --- kernel/sched/cpudeadline.c | 38 +++++++++++++++++++------------------- 1 file changed, 19 insertions(+), 19 deletions(-) diff --git a/kernel/sched/cpudeadline.c b/kernel/sched/cpudeadline.c index 5be5882..3c42702 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,20 +66,25 @@ static void cpudl_heapify(struct cpudl *cp, int idx) } } +static void cpudl_heapify_up(struct cpudl *cp, int 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_change_key(struct cpudl *cp, int idx, u64 new_dl) { 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); + cpudl_heapify_down(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); - } + cpudl_heapify_up(cp, idx); } } @@ -154,24 +159,19 @@ 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_up(cp, old_idx); cpumask_set_cpu(cpu, cp->free_cpus); - cpudl_heapify(cp, old_idx); + cpudl_heapify_down(cp, old_idx); goto out; } if (old_idx == IDX_INVALID) { - cp->size++; - cp->elements[cp->size - 1].dl = 0; - cp->elements[cp->size - 1].cpu = cpu; - cp->elements[cpu].idx = cp->size - 1; - cpudl_change_key(cp, cp->size - 1, dl); + int size1 = cp->size++; + cp->elements[size1].dl = dl; + cp->elements[size1].cpu = cpu; + cp->elements[cpu].idx = size1; + cpudl_heapify_up(cp, size1); cpumask_clear_cpu(cpu, cp->free_cpus); } else { cpudl_change_key(cp, old_idx, dl); -- 2.7.4 --------------020307070905030608090506--