Skip to contentSkip to conversation

throttling tree patches

PATCH In review Mike Galbraith 3 participants 22 messages Mar 24, 2006 – Mar 25, 2006

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 throttling tree patches

Greetings,

I've broken down my throttling tree into 6 patches, which I'll send as replies to this start-point.

Patch 1/6

Ignore timewarps caused by SMP timestamp rounding. Also, don't stamp a task with a computed timestamp, stamp with the already called clock.

kernel/sched.c renamed from kernel/sched.c.org +14 -4
@@ -805,6 +805,16 @@
 	unsigned long long __sleep_time = now - p->timestamp;
 	unsigned long sleep_time;
 
+	/*
+	 * On SMP systems, a task can go to sleep on one CPU and
+	 * wake up on another.  When this happens, the timestamp
+	 * is rounded to the nearest tick, which can lead to now
+	 * being less than p->timestamp for short sleeps. Ignore
+	 * these, they're insignificant.
+	 */
+	if (unlikely(now < p->timestamp))
+		__sleep_time = 0ULL;
+
 	if (batch_task(p))
 		sleep_time = 0;
 	else {
@@ -871,20 +881,20 @@
  */
 static void activate_task(task_t *p, runqueue_t *rq, int local)
 {
-	unsigned long long now;
+	unsigned long long now, comp;
 
-	now = sched_clock();
+	now = comp = sched_clock();
 #ifdef CONFIG_SMP
 	if (!local) {
 		/* Compensate for drifting sched_clock */
 		runqueue_t *this_rq = this_rq();
-		now = (now - this_rq->timestamp_last_tick)
+		comp = (now - this_rq->timestamp_last_tick)
 			+ rq->timestamp_last_tick;
 	}
 #endif
 
 	if (!rt_task(p))
-		p->prio = recalc_task_prio(p, now);
+		p->prio = recalc_task_prio(p, comp);
 
 	/*
 	 * This checks to make sure it's not an uninterruptible task
#1 lore raw

patch 2/6

This patch just fixes a bug waiting for a place to happen. If anyone ever decides to use TASK_NONINTERACTIVE along with TASK_UNINTERRUPTIBLE, bad things will happen.

kernel/sched.c renamed from kernel/sched.c-1.timewarp +2 -2
@@ -1418,7 +1418,7 @@
 
 out_activate:
 #endif /* CONFIG_SMP */
-	if (old_state == TASK_UNINTERRUPTIBLE) {
+	if (old_state & TASK_UNINTERRUPTIBLE) {
 		rq->nr_uninterruptible--;
 		/*
 		 * Tasks on involuntary sleep don't earn
@@ -3125,7 +3125,7 @@
 				unlikely(signal_pending(prev))))
 			prev->state = TASK_RUNNING;
 		else {
-			if (prev->state == TASK_UNINTERRUPTIBLE)
+			if (prev->state & TASK_UNINTERRUPTIBLE)
 				rq->nr_uninterruptible++;
 			deactivate_task(prev, rq);
 		}
#2 lore raw

patch 3/6

This patch does various interactivity cleanups.

1. Removes the barrier between kernel threads and user tasks wrt dynamic priority handling.

2. Removes the priority barrier for IO.

3. Treats TASK_INTERACTIVE as a transition point that all tasks must stop at prior to being promoted further.

4. Moves division out of the fast path and into scheduler_tick(). While doing so, tightens timeslice accounting, since it's free, and is the flip-side of the reason for having nanosecond sched_clock().

include/linux/sched.h renamed from include/linux/sched.h.org +1 -0
@@ -741,6 +741,7 @@
 	unsigned long policy;
 	cpumask_t cpus_allowed;
 	unsigned int time_slice, first_time_slice;
+	long slice_time_ns;
 
 #ifdef CONFIG_SCHEDSTATS
 	struct sched_info sched_info;
kernel/sched.c renamed from kernel/sched.c-2.uninterruptible +80 -53

239 lines not on this page · raw message

#3 lore raw

patch 4/6

This patch implements the throttling.

Throttling is done via computing a slice_avg, which is the upper limit of what a task's sleep_avg may be and be sane. When a task begins to consume more CPU than it's sleep_avg indicates it should, the task will be throttled. A task which conforms to expectations can save credit for later use, which allows interactive tasks to do a burst of activity without being throttled. When their reserve is exhausted however, that's the end of high ussage at high priority.

include/linux/sched.h renamed from include/linux/sched.h.org +2 -2
@@ -733,14 +733,14 @@
 	unsigned short ioprio;
 	unsigned int btrace_seq;
 
-	unsigned long sleep_avg;
+	unsigned long sleep_avg, last_slice, throttle;
 	unsigned long long timestamp, last_ran;
 	unsigned long long sched_time; /* sched_clock time spent running */
 	enum sleep_type sleep_type;
 
 	unsigned long policy;
 	cpumask_t cpus_allowed;
-	unsigned int time_slice, first_time_slice;
+	unsigned int time_slice, slice_info;
 	long slice_time_ns;
 
 #ifdef CONFIG_SCHEDSTATS
kernel/sched.c renamed from kernel/sched.c-3.interactivity +243 -22

340 lines not on this page · raw message

#4 lore raw

patch 5/6

This patch tightens timeslice accounting the rest of the way, such that a task which has received more than it's slice due to missing with the timer interrupt will have the excess deducted from their next slice.

kernel/sched.c renamed from kernel/sched.c-4.throttle +18 -3
@@ -2924,13 +2924,28 @@
 	unsigned int slice = last_slice(p);
 	unsigned int slice_avg, cpu, idle;
 	long run_time = -1 * p->slice_time_ns;
+	long slice_time_ns = task_timeslice_ns(p);
 	int w = MAX_BONUS, delta, bonus;
 
 	/*
-	 * Update time_slice.
+	 * Update time_slice.  Account for unused fragment,
+	 * or excess time received due to missed tick.
 	 */
-	p->slice_time_ns = task_timeslice_ns(p);
-	p->time_slice = task_timeslice(p);
+	p->slice_time_ns += slice_time_ns;
+	/*
+	 * Not common, but this does happen on SMP systems.
+	 * Timeslice theft of this magnitude has never been
+	 * observed in the wild, so assume that this is BS,
+	 * and give the poor task it's full slice.  Theory:
+	 * mostly idle task migrates between CPUs numerous
+	 * times during it's slice, timestamp rounding leads
+	 * to wildly inaccurate calculation.  Rounding has
+	 * maximum effect on those who stretch their slice,
+	 * but is also fairly meaningless, so ignore it.
+	 */
+	if (unlikely(p->slice_time_ns < NS_TICK))
+		p->slice_time_ns = slice_time_ns;
+	p->time_slice = NS_TO_JIFFIES(p->slice_time_ns);
 	set_last_slice(p, p->time_slice);
 
 	/*
#5 lore raw

patch 6/6

This patch exports throttling tuning knobs to userland. Should be useful for testing, and in easily discarded should my throttling stuff make it into mm, and survive the experience.

include/linux/sysctl.h renamed from include/linux/sysctl.h.org +2 -0
@@ -148,6 +148,8 @@
 	KERN_SPIN_RETRY=70,	/* int: number of spinlock retries */
 	KERN_ACPI_VIDEO_FLAGS=71, /* int: flags for setting up video after ACPI sleep */
 	KERN_IA64_UNALIGNED=72, /* int: ia64 unaligned userland trap enable */
+	KERN_SCHED_THROTTLE1=73,  /* int: throttling credit period 1 in secs */
+	KERN_SCHED_THROTTLE2=74,  /* int: throttling credit period 2 in secs */
 };
 
 
kernel/sysctl.c renamed from kernel/sysctl.c.org +30 -6
@@ -73,6 +73,9 @@
 extern int pid_max_min, pid_max_max;
 extern int sysctl_drop_caches;
 extern int percpu_pagelist_fraction;
+extern int credit_c1;
+extern int credit_c2;
+extern int credit_max;
 
 #if defined(CONFIG_X86_LOCAL_APIC) && defined(CONFIG_X86)
 int unknown_nmi_panic;
@@ -230,6 +233,11 @@
 	{ .ctl_name = 0 }
 };
 
+/* Constants for minimum and maximum testing in vm_table and
+ * kern_table.  We use these as one-element integer vectors. */
+static int zero;
+static int one_hundred = 100;
+
 static ctl_table kern_table[] = {
 	{
 		.ctl_name	= KERN_OSTYPE,
@@ -684,15 +692,31 @@
 		.proc_handler	= &proc_dointvec,
 	},
 #endif
+	{
+		.ctl_name	= KERN_SCHED_THROTTLE1,
+		.procname	= "credit_c1",
+		.data		= &credit_c1,
+		.maxlen		= sizeof (int),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec_minmax,
+		.strategy	= &sysctl_intvec,
+		.extra1		= &zero,
+		.extra2		= &credit_max,
+	},
+	{
+		.ctl_name	= KERN_SCHED_THROTTLE2,
+		.procname	= "credit_c2",
+		.data		= &credit_c2,
+		.maxlen		= sizeof (int),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec_minmax,
+		.strategy	= &sysctl_intvec,
+		.extra1		= &zero,
+		.extra2		= &credit_max,
+	},
 	{ .ctl_name = 0 }
 };
 
-/* Constants for minimum and maximum testing in vm_table.
-   We use these as one-element integer vectors. */
-static int zero;
-static int one_hundred = 100;
-
-
 static ctl_table vm_table[] = {
 	{
 		.ctl_name	= VM_OVERCOMMIT_MEMORY,
kernel/sched.c renamed from kernel/sched.c-5.slice_accounting +5 -4
@@ -220,11 +220,12 @@
  *           credit that fits in 32 bits jiffies is 42949 seconds.
  */
 
-#define CREDIT_C1 10
-#define CREDIT_C2 14400
+int credit_c1 = 10;
+int credit_c2 = 14400;
+int credit_max = 42949;
 
-#define C1 (CREDIT_C1 * MAX_BONUS * HZ)
-#define C2 (CREDIT_C2 * MAX_BONUS * HZ + C1)
+#define C1 (credit_c1 * MAX_BONUS * HZ)
+#define C2 (credit_c2 * MAX_BONUS * HZ + C1)
 #define C3 (MAX_BONUS * C2)
 
 #define credit_exhausted(p, credit) \
#16 lore raw
In reply to Mike Galbraith
Quoted 1 line · Mike Galbraith

Greetings,

/me waves

Quoted 2 lines

Ignore timewarps caused by SMP timestamp rounding. Also, don't stamp a task with a computed timestamp, stamp with the already called clock.

Looks good. Actually now < p->timestamp is not going to only happen on SMP. Once every I don't know how often the sched_clock seems to return a value that appears to have been in the past (I believe Peter has instrumented this).

kernel/sched.c line 816

Quoted 3 lines
kernel/sched.c renamed from kernel/sched.c.org +1 -0
+		__sleep_time = 0ULL;

I don't think the ULL is necessary.

Quoted 8 lines
kernel/sched.c renamed from kernel/sched.c.org +2 -2
-	unsigned long long now;
+	unsigned long long now, comp;
 
-	now = sched_clock();
+	now = comp = sched_clock();
 #ifdef CONFIG_SMP
 	if (!local) {
 		/* Compensate for drifting sched_clock */

kernel/sched.c line 897

Quoted 10 lines
kernel/sched.c renamed from kernel/sched.c.org +2 -2
 		runqueue_t *this_rq = this_rq();
-		now = (now - this_rq->timestamp_last_tick)
+		comp = (now - this_rq->timestamp_last_tick)
 			+ rq->timestamp_last_tick;
 	}
 #endif
 
 	if (!rt_task(p))
-		p->prio = recalc_task_prio(p, now);
+		p->prio = recalc_task_prio(p, comp);

Seems wasteful of a very expensive (on 32bit) unsigned long long on uniprocessor builds.

Cheers,
Con

#8 lore raw
In reply to Mike Galbraith
Quoted 11 lines · Mike Galbraith

patch 4/6

This patch implements the throttling.

Throttling is done via computing a slice_avg, which is the upper limit of what a task's sleep_avg may be and be sane. When a task begins to consume more CPU than it's sleep_avg indicates it should, the task will be throttled. A task which conforms to expectations can save credit for later use, which allows interactive tasks to do a burst of activity without being throttled. When their reserve is exhausted however, that's the end of high ussage at high priority.

Looks ok. The description of credit still sounds cryptic.

kernel/sched.c line 228

Quoted 3 lines
kernel/sched.c renamed from kernel/sched.c-3.interactivity +3 -0
+#define C1 (CREDIT_C1 * MAX_BONUS * HZ)
+#define C2 (CREDIT_C2 * MAX_BONUS * HZ + C1)
+#define C3 (MAX_BONUS * C2)

Macro names that short are asking for trouble...

...
else looks good. After we've cleaned out all the sched patches from -mm it would be nice to get this work in. The values of C1 and particularly C2 _sound_ large but may well be appropriate since you've been hard at work on this. I'll have to have a play for myself (if I ever find spare cycles on my miniscule selection of hardware) with them when they hit -mm.

Cheers,
Con

#9 lore raw
In reply to Mike Galbraith
Quoted 1 line · Mike Galbraith

This patch does various interactivity cleanups.

I have trouble with this patch. By your own admission this patch does 4 different things which one patch shouldn't.

Quoted 2 lines

1. Removes the barrier between kernel threads and user tasks wrt dynamic priority handling.

This is a bad idea. Subjecting a priority ceiling to kernel threads because they spend a long time idle is not the same as a user task that may be an idle bomb. Most kernel threads do sleep for extended periods and will always end up hitting this ceiling. That could lead to some difficult to understand latencies in scheduling of kernel threads, even if they are nice -5 because they'll expire very easily.

Quoted 1 line

2. Removes the priority barrier for IO.

Bad again. This caused the biggest detriment on interbench numbers and is by far the most palpable interactivity killer in linux. I/O hurts us lots and this change will be very noticeable.

Quoted 2 lines

3. Treats TASK_INTERACTIVE as a transition point that all tasks must stop at prior to being promoted further.

Why? Makes no sense. You end up getting hiccups in the rise of priority of tasks instead of it happening smoothly with sleep.

Quoted 3 lines

4. Moves division out of the fast path and into scheduler_tick(). While doing so, tightens timeslice accounting, since it's free, and is the flip-side of the reason for having nanosecond sched_clock().

Seems fine.

Cheers,
Con

#10 lore raw
Quoted 5 lines · Con Kolivas
Quoted 1 line · Mike Galbraith

This patch does various interactivity cleanups.

I have trouble with this patch. By your own admission this patch does 4 different things which one patch shouldn't.

They're all part of the same thing, they're just cleanup.

Quoted 6 lines
Quoted 2 lines

1. Removes the barrier between kernel threads and user tasks wrt dynamic priority handling.

This is a bad idea. Subjecting a priority ceiling to kernel threads because they spend a long time idle is not the same as a user task that may be an idle bomb.

Kernel threads don't make the transition, they're sitting there with a fully loaded sleep_avg. You stop on the way up, sure, but once there, a long sleep doesn't truncate you. Try it.

Quoted 4 lines

Most kernel threads do sleep for extended periods and will always
end up hitting this ceiling. That could lead to some difficult to understand latencies in scheduling of kernel threads, even if they are nice -5 because they'll expire very easily.

No, they won't. Furthermore, any kernel thread which cannot tolerate dynamic priority semantics should not use them, they should be RT.

Quoted 5 lines
Quoted 1 line

2. Removes the priority barrier for IO.

Bad again. This caused the biggest detriment on interbench numbers and is by far the most palpable interactivity killer in linux. I/O hurts us lots and this change will be very noticeable.

This barrier is artificial, and has been demonstrated to be harmful to some loads. Being practical, if this is demonstrated to still cause trouble, I'll happily re-introduce it with a follow-up patch.

Quoted 5 lines
Quoted 2 lines

3. Treats TASK_INTERACTIVE as a transition point that all tasks must stop at prior to being promoted further.

Why? Makes no sense. You end up getting hiccups in the rise of priority of tasks instead of it happening smoothly with sleep.

Quite the opposite, it makes perfect sense. Taking the long sleeper to the artificial barrier of prio 16 as stock does is the very reason that thud totally destroys the interactive experience. I'd love to remove this barrier too, and have 'purity', but OTOH, the interactive border _is_ a transition point where the scheduler changes behavior. This is a transition point in fact, so treating it as such is indeed correct.

-Mike

#11 lore raw
Quoted 8 lines · Mike Galbraith
Quoted 5 lines · Con Kolivas
Quoted 1 line · Mike Galbraith

This patch does various interactivity cleanups.

I have trouble with this patch. By your own admission this patch does 4 different things which one patch shouldn't.

They're all part of the same thing, they're just cleanup.

Cleanup? Something that changes behaviour is not cleanup.

Quoted 11 lines
Quoted 7 lines
Quoted 3 lines

1. Removes the barrier between kernel threads and user tasks wrt dynamic priority handling.

This is a bad idea. Subjecting a priority ceiling to kernel threads because they spend a long time idle is not the same as a user task that may be an idle bomb.

Kernel threads don't make the transition, they're sitting there with a fully loaded sleep_avg. You stop on the way up, sure, but once there, a long sleep doesn't truncate you. Try it.

Threads like kswapd do not have a fully loaded sleep_avg.

Quoted 7 lines
Quoted 4 lines

Most kernel threads do sleep for extended periods and will always
end up hitting this ceiling. That could lead to some difficult to understand latencies in scheduling of kernel threads, even if they are nice -5 because they'll expire very easily.

No, they won't. Furthermore, any kernel thread which cannot tolerate dynamic priority semantics should not use them, they should be RT.

Very few kernel threads should require RT just to work as you just said, yet you'll make it harder for them with your changed dynamic priority semantics. We already know they are not going to be misbehaving userspace tasks and they deserve simpler semantics than the full interactivity estimator gives.

Quoted 8 lines
Quoted 5 lines
Quoted 1 line

2. Removes the priority barrier for IO.

Bad again. This caused the biggest detriment on interbench numbers and is by far the most palpable interactivity killer in linux. I/O hurts us lots and this change will be very noticeable.

This barrier is artificial, and has been demonstrated to be harmful to some loads.

Which?

Quoted 2 lines

Being practical, if this is demonstrated to still cause trouble, I'll happily re-introduce it with a follow-up patch.

Trouble occurs months afterwards this hits mainline since you'll get almost noone testing it in -mm. It was put there because it hurt interactivity and you're removing it because you don't like that we have to put a special case there?

Quoted 6 lines
Quoted 5 lines
Quoted 2 lines

3. Treats TASK_INTERACTIVE as a transition point that all tasks must stop at prior to being promoted further.

Why? Makes no sense. You end up getting hiccups in the rise of priority of tasks instead of it happening smoothly with sleep.

Quoted 6 lines

Quite the opposite, it makes perfect sense. Taking the long sleeper to the artificial barrier of prio 16 as stock does is the very reason that thud totally destroys the interactive experience. I'd love to remove this barrier too, and have 'purity', but OTOH, the interactive border _is_ a transition point where the scheduler changes behavior. This is a transition point in fact, so treating it as such is indeed correct.

And what does it actually achieve making this change is my question?

I feel this discussion may degenerate beyond this point. Should we say to agree to disagree at this point? I don't like these changes.

Cheers,
Con

#12 lore raw
Quoted 11 lines · Con Kolivas
Quoted 8 lines · Mike Galbraith
Quoted 5 lines · Con Kolivas
Quoted 1 line · Mike Galbraith

This patch does various interactivity cleanups.

I have trouble with this patch. By your own admission this patch does 4 different things which one patch shouldn't.

They're all part of the same thing, they're just cleanup.

Cleanup? Something that changes behaviour is not cleanup.

A semantic cleanup remains a cleanup.

Quoted 7 lines
Quoted 7 lines
Quoted 6 lines
Quoted 2 lines

1. Removes the barrier between kernel threads and user tasks wrt dynamic priority handling.

This is a bad idea. Subjecting a priority ceiling to kernel threads because they spend a long time idle is not the same as a user task that may be an idle bomb.

Quoted 5 lines
Quoted 3 lines

Kernel threads don't make the transition, they're sitting there with a fully loaded sleep_avg. You stop on the way up, sure, but once there, a long sleep doesn't truncate you. Try it.

Threads like kswapd do not have a fully loaded sleep_avg.

Huh? I've yet to see kswapd non-interactive. If I do, I'll have grounds to party, because the box would otherwise have been a doorstop.

Quoted 5 lines
Quoted 5 lines
Quoted 4 lines

Most kernel threads do sleep for extended periods and will always
end up hitting this ceiling. That could lead to some difficult to understand latencies in scheduling of kernel threads, even if they are nice -5 because they'll expire very easily.

Quoted 7 lines
Quoted 2 lines

No, they won't. Furthermore, any kernel thread which cannot tolerate dynamic priority semantics should not use them, they should be RT.

Very few kernel threads should require RT just to work as you just said, yet you'll make it harder for them with your changed dynamic priority semantics. We already know they are not going to be misbehaving userspace tasks and they deserve simpler semantics than the full interactivity estimator gives.

They don't need to be treated special, and it is flat wrong to do so. Try the patch set and you'll see that they continue to work just fine.

Consider this: why should 10 copies of knfsd have any more right than 10 copies of apache to utterly monopolize my cpu? Fact is, there is no difference. Both are acting on behalf other user tasks. The fact that one is a kernel thread means nothing.

Quoted 10 lines
Quoted 8 lines
Quoted 5 lines
Quoted 1 line

2. Removes the priority barrier for IO.

Bad again. This caused the biggest detriment on interbench numbers and is by far the most palpable interactivity killer in linux. I/O hurts us lots and this change will be very noticeable.

This barrier is artificial, and has been demonstrated to be harmful to some loads.

Which?

Remember the demonstration of dd being starved?

Quoted 7 lines
Quoted 2 lines

Being practical, if this is demonstrated to still cause trouble, I'll happily re-introduce it with a follow-up patch.

Trouble occurs months afterwards this hits mainline since you'll get almost noone testing it in -mm. It was put there because it hurt interactivity and you're removing it because you don't like that we have to put a special case there?

Throttling changes this. Believe it or not, I didn't just run around with a machete looking for things to chop to ribbons.

Quoted 6 lines
Quoted 6 lines
Quoted 5 lines
Quoted 2 lines

3. Treats TASK_INTERACTIVE as a transition point that all tasks must stop at prior to being promoted further.

Why? Makes no sense. You end up getting hiccups in the rise of priority of tasks instead of it happening smoothly with sleep.

Quoted 8 lines
Quoted 6 lines

Quite the opposite, it makes perfect sense. Taking the long sleeper to the artificial barrier of prio 16 as stock does is the very reason that thud totally destroys the interactive experience. I'd love to remove this barrier too, and have 'purity', but OTOH, the interactive border _is_ a transition point where the scheduler changes behavior. This is a transition point in fact, so treating it as such is indeed correct.

And what does it actually achieve making this change is my question?

It achieves precisely what the comment you placed there some odd years ago says it should achieve. Thud is a pure cpu hog that sleeps for a while to charge it's battery for an intentional attack. It was written specifically to demonstrate the problem with allowing a long sleep to rocket you to the top of the world as stock code does. Try running the stock kernel with irman2 and thud running, then you'll certainly understand what this change achieves.

Quoted 2 lines

I feel this discussion may degenerate beyond this point. Should we say to agree to disagree at this point? I don't like these changes.

Why should it degenerate? You express your concerns, I answer them. You don't have to agree with me, and I don't have to agree with you. That's no reason for the discussion to degenerate.

-Mike

#13 lore raw
Quoted 7 lines · Mike Galbraith
Quoted 2 lines · Con Kolivas

I feel this discussion may degenerate beyond this point. Should we say to agree to disagree at this point? I don't like these changes.

Why should it degenerate? You express your concerns, I answer them. You don't have to agree with me, and I don't have to agree with you. That's no reason for the discussion to degenerate.

By degenerate I mean get stuck in an endless loop. I don't have the energy for cyclical discussions where no conclusive endpoint can ever be reached. That is the nature of what we're discussing. Everything is some sort of compromise and you're moving one set of compromises for another which means this can be debated forever without a right or wrong.

The merits of throttling seem obvious with a sliding scale between interactivity and fairness. These other changes, to me, do not. On the interactivity side I only have interbench for hard data, and it is showing me regressions consistent with my concerns from these other "cleanups". You'll trade some other advantage for these and we'll repeat the discussion all over again. Rinse and repeat.

Cheers,
Con

#14 lore raw
Quoted 15 lines · Con Kolivas
Quoted 7 lines · Mike Galbraith
Quoted 2 lines · Con Kolivas

I feel this discussion may degenerate beyond this point. Should we say to agree to disagree at this point? I don't like these changes.

Why should it degenerate? You express your concerns, I answer them. You don't have to agree with me, and I don't have to agree with you. That's no reason for the discussion to degenerate.

By degenerate I mean get stuck in an endless loop. I don't have the energy for cyclical discussions where no conclusive endpoint can ever be reached. That is the nature of what we're discussing. Everything is some sort of compromise and you're moving one set of compromises for another which means this can be debated forever without a right or wrong.

Quoted 6 lines

The merits of throttling seem obvious with a sliding scale between interactivity and fairness. These other changes, to me, do not. On the interactivity side I only have interbench for hard data, and it is showing me regressions consistent with my concerns from these other "cleanups". You'll trade some other advantage for these and we'll repeat the discussion all over again. Rinse and repeat.

So be it. We shall agree to disagree.

I'll close with this. I'm not basing any of my changes on a benchmark, I'm basing them on real life applications and exploits written by people who were experiencing problems with their real life applications. It is my carefully considered opinion that those changes which you so strongly oppose are important.

-Mike

#17 lore raw
In reply to Con Kolivas
Quoted 9 lines · Con Kolivas
Quoted 1 line · Mike Galbraith

Greetings,

/me waves

Quoted 2 lines

Ignore timewarps caused by SMP timestamp rounding. Also, don't stamp a task with a computed timestamp, stamp with the already called clock.

Looks good. Actually now < p->timestamp is not going to only happen on SMP. Once every I don't know how often the sched_clock seems to return a value that appears to have been in the past (I believe Peter has instrumented this).

I haven't bothered to check if it still occurs for quite a long while. I just check for time deltas being negative and if they are negative I make them zero and move on. As far as I can remember I only ever saw this when measuring "delay" (i.e. time on the run queue waiting to get on to a CPU which can be quite short :-) when the systems not heavily loaded) as other time intervals that I measure (i.e. time on CPU and sleep time) are generally long enough for the error in the delta not being big enough to make the value negative.

Quoted 22 lines

kernel/sched.c line 816

Quoted 4 lines
kernel/sched.c renamed from kernel/sched.c.org +1 -0
+		__sleep_time = 0ULL;

I don't think the ULL is necessary.

Quoted 15 lines
kernel/sched.c renamed from kernel/sched.c.org +3 -3
-	unsigned long long now;
+	unsigned long long now, comp;
 
-	now = sched_clock();
+	now = comp = sched_clock();
 #ifdef CONFIG_SMP
 	if (!local) {
 		/* Compensate for drifting sched_clock */
 		runqueue_t *this_rq = this_rq();
-		now = (now - this_rq->timestamp_last_tick)
+		comp = (now - this_rq->timestamp_last_tick)
 			+ rq->timestamp_last_tick;
 	}
 #endif
Quoted 5 lines

kernel/sched.c line 897

Quoted 3 lines
kernel/sched.c renamed from kernel/sched.c.org +1 -1
 	if (!rt_task(p))
-		p->prio = recalc_task_prio(p, now);
+		p->prio = recalc_task_prio(p, comp);

Seems wasteful of a very expensive (on 32bit) unsigned long long on uniprocessor builds.

Unsigned long long is necessary in order to avoid overflow when dealing with nano seconds but (if you reorganized the expressions and made the desired precedence explicit) you could probably use something smaller for the difference between the two timestamp_lats_tick values. More importantly, I think that the original code which used the computed "now" was correct as otherwise the task's timestamp will not have the correct time for its CPU.

Of course, this all hinges on the differences between the run queues' timestamp_last_tick fields being a true measure of the time drift between them. I've never been wholly convinced of that but as long as any error is much smaller than the drift it's probably worth doing.

Peter
PS I think that some inline functions to handle timestamp adjustment wouldn't hurt.
PPS I'm not sure that the timstamp adjustment in __migrate_task() is completely valid as the timestamp will be modified in activate_task() using the wrong clock. I need to study this more to see if I convince myself one way or the other.

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
#20 lore raw
In reply to Mike Galbraith
Quoted 15 lines · Mike Galbraith

Greetings,

I've broken down my throttling tree into 6 patches, which I'll send as replies to this start-point.

Patch 1/6

Ignore timewarps caused by SMP timestamp rounding. Also, don't stamp a task with a computed timestamp, stamp with the already called clock.

kernel/sched.c line 811

Quoted 7 lines
kernel/sched.c renamed from kernel/sched.c.org +4 -0
@@ -805,6 +805,16 @@
 	unsigned long long __sleep_time = now - p->timestamp;
 	unsigned long sleep_time;
 
+	/*
+	 * On SMP systems, a task can go to sleep on one CPU and
+	 * wake up on another.  When this happens, the timestamp
+	 * is rounded to the nearest tick,

Is this true? There's no rounding that I can see. An attempt is made to adjust the timestamp for the drift between time as seen from the two CPUs but there's no deliberate rounding involved. Of course, that's not to say that the adjustment is accurate as I'm not convinced that the difference between the run queues' timestamp_last_tick is a always totally accurate measure of the drift in their clocks (due to possible races -- I may be wrong).

Of course, that doesn't mean that this chunk of code isn't required just that the comment is misleading.

Quoted 25 lines

which can lead to now

kernel/sched.c renamed from kernel/sched.c.org +9 -3
+	 * being less than p->timestamp for short sleeps. Ignore
+	 * these, they're insignificant.
+	 */
+	if (unlikely(now < p->timestamp))
+		__sleep_time = 0ULL;
+
 	if (batch_task(p))
 		sleep_time = 0;
 	else {
@@ -871,20 +881,20 @@
  */
 static void activate_task(task_t *p, runqueue_t *rq, int local)
 {
-	unsigned long long now;
+	unsigned long long now, comp;
 
-	now = sched_clock();
+	now = comp = sched_clock();
 #ifdef CONFIG_SMP
 	if (!local) {
 		/* Compensate for drifting sched_clock */
 		runqueue_t *this_rq = this_rq();
-		now = (now - this_rq->timestamp_last_tick)
+		comp = (now - this_rq->timestamp_last_tick)

kernel/sched.c line 900

Quoted 10 lines
kernel/sched.c renamed from kernel/sched.c.org +1 -1
 			+ rq->timestamp_last_tick;
 	}
 #endif
 
 	if (!rt_task(p))
-		p->prio = recalc_task_prio(p, now);
+		p->prio = recalc_task_prio(p, comp);
 
 	/*
 	 * This checks to make sure it's not an uninterruptible task

I think that this will end up with p->timestamp being set with a time appropriate to the current task's CPU rather than its own.

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
#18 lore raw
In reply to Peter Williams
Quoted 9 lines · Peter Williams
Quoted 6 lines · Con Kolivas

kernel/sched.c line 897

Quoted 3 lines
kernel/sched.c renamed from kernel/sched.c.org +1 -1
 	if (!rt_task(p))
-		p->prio = recalc_task_prio(p, now);
+		p->prio = recalc_task_prio(p, comp);

Seems wasteful of a very expensive (on 32bit) unsigned long long on uniprocessor builds.

Quoted 7 lines

Unsigned long long is necessary in order to avoid overflow when dealing with nano seconds but (if you reorganized the expressions and made the desired precedence explicit) you could probably use something smaller for the difference between the two timestamp_lats_tick values. More importantly, I think that the original code which used the computed "now" was correct as otherwise the task's timestamp will not have the correct time for its CPU.

I can live with it either way. On my SMT box, the rounding is much worse than the actual drift, that's microseconds, but the rounding turns it into milliseconds.

Quoted 4 lines

Of course, this all hinges on the differences between the run queues' timestamp_last_tick fields being a true measure of the time drift between them. I've never been wholly convinced of that but as long as any error is much smaller than the drift it's probably worth doing.

On a real SMP, this adjusting of timestamps probably helps (dunno, no have), on my box it's doomed to do more harm than good. To me, the only thing that really matters is ignoring the bogus transition.

-Mike

#21 lore raw
In reply to Peter Williams
Quoted 19 lines · Peter Williams
Quoted 18 lines · Mike Galbraith

Greetings,

I've broken down my throttling tree into 6 patches, which I'll send as replies to this start-point.

Patch 1/6

Ignore timewarps caused by SMP timestamp rounding. Also, don't stamp a task with a computed timestamp, stamp with the already called clock.

kernel/sched.c renamed from kernel/sched.c.org +0 -0
@@ -805,6 +805,16 @@
 	unsigned long long __sleep_time = now - p->timestamp;
 	unsigned long sleep_time;
 
Quoted 6 lines

kernel/sched.c

Quoted 4 lines
kernel/sched.c renamed from kernel/sched.c.org +4 -0
+	/*
+	 * On SMP systems, a task can go to sleep on one CPU and
+	 * wake up on another.  When this happens, the timestamp
+	 * is rounded to the nearest tick,

Is this true? There's no rounding that I can see.

Instrumenting it looked the same as rounding down, putting now in the past was the result.

Quoted 2 lines

Of course, that doesn't mean that this chunk of code isn't required just that the comment is misleading.

I'm not attached to the comment.

-Mike

#19 lore raw

PATCH 1/1 ignore timewarps

In reply to Mike Galbraith

Greetings,

The patch below is a correction to patch 1 of my throttling tree series.

The only thing that really matters is that timewarps are ignored, whatever the cause. This patch does that, and only that.

-Mike

kernel/sched.c renamed from kernel/sched.c.org +9 -0
@@ -805,6 +805,15 @@
 	unsigned long long __sleep_time = now - p->timestamp;
 	unsigned long sleep_time;
 
+	/*
+	 * On SMP systems, a task can go to sleep on one CPU
+	 * and wake up on another.  When this happens, now can
+	 * end up being less than p->timestamp for short sleeps.
+	 * Ignore these, they're insignificant.
+	 */
+	if (unlikely(now < p->timestamp))
+		__sleep_time = 0;
+
 	if (batch_task(p))
 		sleep_time = 0;
 	else {