LKML Archive on
 help / color / Atom feed
From: Tommaso Cucinotta <>
To: Luca Abeni <>,
	Juri Lelli <>,
	Peter Zijlstra <>,
	Ingo Molnar <>
	Tommaso Cucinotta <>,
	Juri Lelli <>
Subject: [RFC PATCH 1/4] Minimally invasive deadline wrap-around bugfix for SCHED_DEADLINE cpu heap
Date: Tue, 19 Jul 2016 11:44:50 +0200
Message-ID: <> (raw)
In-Reply-To: <>

Current code in cpudeadline.c has a bug in re-heapifying when adding a
new element at the end of the heap, because a deadline value of 0 is
temporarily set in the new elem, then cpudl_change_key() is called
with the actual elem deadline as param. However, the function compares
the new deadline to set with the one previously in the elem, which is
0.  So, if current absolute deadlines grew so much to have negative
values as s64, the comparison in cpudl_change_key() makes the wrong
decision.  Instead, as from dl_time_before(), the kernel should handle
correctly abs deadlines wrap-arounds.

This patch fixes the problem with a minimally invasive change that
forces cpudl_change_key() to heapify up in this case.

Cc: Peter Zijlstra <>
Cc: Juri Lelli <>
Cc: Luca Abeni <>
Reviewed-by: Luca Abeni <>
Signed-off-by: Tommaso Cucinotta <>
 kernel/sched/cpudeadline.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/sched/cpudeadline.c b/kernel/sched/cpudeadline.c
index 5be5882..d418449 100644
--- a/kernel/sched/cpudeadline.c
+++ b/kernel/sched/cpudeadline.c
@@ -168,7 +168,7 @@ void cpudl_set(struct cpudl *cp, int cpu, u64 dl, int is_valid)
 	if (old_idx == IDX_INVALID) {
-		cp->elements[cp->size - 1].dl = 0;
+		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);

  reply index

Thread overview: 12+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2016-07-19  9:44 SCHED_DEADLINE cpudeadline.{h,c} fixup Tommaso Cucinotta
2016-07-19  9:44 ` Tommaso Cucinotta [this message]
2016-08-01 11:43   ` [RFC PATCH 1/4] Minimally invasive deadline wrap-around bugfix for SCHED_DEADLINE cpu heap Juri Lelli
2016-08-01 12:57     ` Juri Lelli
2016-08-10 18:00   ` [tip:sched/core] sched/deadline: Fix wrap-around in DL heap tip-bot for Tommaso Cucinotta
2016-07-19  9:44 ` [RFC PATCH 2/4] SCHED_DEADLINE cpu heap code clarification/refactory Tommaso Cucinotta
2016-08-01 16:30   ` Juri Lelli
2016-07-19  9:44 ` [RFC PATCH 3/4] Make deadline max-heap faster avoiding real swaps on heapify ops Tommaso Cucinotta
2016-08-02 11:38   ` Juri Lelli
2016-08-08 14:04   ` Peter Zijlstra
2016-07-19  9:44 ` [RFC PATCH 4/4] Split cpudl_set() into cpudl_set() and cpudl_clear() Tommaso Cucinotta
2016-08-02 11:52   ` Juri Lelli

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:

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \ \ \ \ \ \ \ \ \ \

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

LKML Archive on

Archives are clonable:
	git clone --mirror lkml/git/0.git
	git clone --mirror lkml/git/1.git
	git clone --mirror lkml/git/2.git
	git clone --mirror lkml/git/3.git
	git clone --mirror lkml/git/4.git
	git clone --mirror lkml/git/5.git
	git clone --mirror lkml/git/6.git
	git clone --mirror lkml/git/7.git
	git clone --mirror lkml/git/8.git
	git clone --mirror lkml/git/9.git
	git clone --mirror lkml/git/10.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 lkml lkml/ \
	public-inbox-index lkml

Example config snippet for mirrors

Newsgroup available over NNTP:

AGPL code for this site: git clone