Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Mike Galbraith]

[-- Attachment #1: Type: text/plain, Size: 908 bytes --]

At 02:51 PM 7/13/2003 -0700, Davide Libenzi wrote:

>This should (hopefully) avoid other tasks starvation exploits :
>
>http://www.xmailserver.org/linux-patches/softrr.html

Yes, that ~works.  I couldn't starve root to death as a SCHED_SOFTRR user, 
but the system was very sluggish, with keystrokes taking uncomfortably 
long.  I also had some sound skips due to inheritance.  If I activate 
xmms's gl visualization under load, it inherits SCHED_SOFTRR, says "oink" 
in a very deep voice, and other xmms threads expire.  Maybe tasks shouldn't 
inherit SCHED_SOFTRR?

While testing, I spotted something pretty strange.  It's not specific to 
SCHED_SOFTRR, SCHED_RR causes it too.  If I fire up xmms's gl visualization 
with either policy, X stops getting enough sleep credit to stay at a usable 
priority even when cpu usage is low.  Fully repeatable weirdness.  See 
attached top snapshots.

         -Mike 

[-- Attachment #2: xx --]
[-- Type: application/octet-stream, Size: 3242 bytes --]

--------------------------------- Abby Normal ---------------------------
top - 05:44:20 up  1:27,  4 users,  load average: 3.93, 4.71, 5.00
Tasks:  83 total,   4 running,  79 sleeping,   0 stopped,   0 zombie
Cpu(s):  90.5% user,   9.5% system,   0.0% nice,   0.0% idle,   0.0% IO-wait
Mem:    125712k total,   112860k used,    12852k free,     5048k buffers
Swap:   265064k total,    16900k used,   248164k free,    50020k cached

  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  Command
 5035 mikeg     -2   0 28136 7328 9952 S 67.6  5.8   8:19.60 xmms
 4532 root      25   0 62800  12m  46m R  8.6  9.8   3:38.64 X
 4596 root     -51   0  7232 4720 5256 S  4.8  3.8   0:21.90 artsd
 4647 root      15   0 20100 8300  18m R  4.8  6.6   0:23.19 kdeinit
 8611 mikeg     -2   0 28136 7328 9952 S  4.8  5.8   0:19.16 xmms
 5011 mikeg     -2   0 28136 7328 9952 S  3.8  5.8   0:28.75 xmms
 4651 root      15   0  1800 1800 1640 R  2.9  1.4   0:55.81 top
 4564 root      15   0 19068 6660  17m S  1.0  5.3   0:09.84 kdeinit
 8618 mikeg     -2   0 28136 7328 9952 R  1.0  5.8   0:01.94 xmms
    1 root      15   0  1380  500 1336 S  0.0  0.4   0:04.23 init
    2 root      34  19     0    0    0 S  0.0  0.0   0:00.00 ksoftirqd/0
    3 root       5 -10     0    0    0 S  0.0  0.0   0:00.21 events/0
    4 root       5 -10     0    0    0 S  0.0  0.0   0:00.29 kblockd/0
    5 root      15   0     0    0    0 S  0.0  0.0   0:00.15 kapmd
    6 root      15   0     0    0    0 S  0.0  0.0   0:00.00 pdflush
    7 root      15   0     0    0    0 S  0.0  0.0   0:00.33 pdflush
    8 root      15   0     0    0    0 S  0.0  0.0   0:01.02 kswapd0

--------------------------------- Norm Normal ---------------------------
top - 06:00:22 up  1:43,  4 users,  load average: 1.48, 2.39, 3.46
Tasks:  85 total,   2 running,  83 sleeping,   0 stopped,   0 zombie
Cpu(s):  94.2% user,   5.8% system,   0.0% nice,   0.0% idle,   0.0% IO-wait
Mem:    125712k total,   120700k used,     5012k free,     6288k buffers
Swap:   265064k total,    15896k used,   249168k free,    53276k cached

  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  Command
 8784 root      25   0 28016 8784 9952 R 65.0  7.0   0:35.71 xmms
 4532 root      15   0 62816  12m  46m S 19.4  9.9   5:46.30 X
 8781 root      15   0 28016 8784 9952 S  4.9  7.0   0:02.72 xmms
 4651 root      16   0  1800 1800 1640 R  3.9  1.4   1:23.98 top
 8786 root      15   0 28016 8784 9952 S  3.9  7.0   0:01.48 xmms
 4596 root     -51   0  7232 4720 5256 S  1.9  3.8   0:32.01 artsd
 4614 root      15   0 19640 7628  18m S  1.0  6.1   0:11.21 kdeinit
 4647 root      15   0 20292 8440  18m S  1.0  6.7   0:35.55 kdeinit
    1 root      15   0  1380  500 1336 S  0.0  0.4   0:04.25 init
    2 root      34  19     0    0    0 S  0.0  0.0   0:00.00 ksoftirqd/0
    3 root       5 -10     0    0    0 S  0.0  0.0   0:00.28 events/0
    4 root       5 -10     0    0    0 S  0.0  0.0   0:00.29 kblockd/0
    5 root      15   0     0    0    0 S  0.0  0.0   0:00.22 kapmd
    6 root      15   0     0    0    0 S  0.0  0.0   0:00.00 pdflush
    7 root      15   0     0    0    0 S  0.0  0.0   0:00.35 pdflush
    8 root      15   0     0    0    0 S  0.0  0.0   0:01.02 kswapd0

[patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Davide Libenzi]

This should (hopefully) avoid other tasks starvation exploits :

http://www.xmailserver.org/linux-patches/softrr.html

Making SCHED_TS_KSOFTRR a proc tunable might be an option.



- Davide




diff -Nru linux-2.5.74.vanilla/include/linux/sched.h linux-2.5.74.mod/include/linux/sched.h
--- linux-2.5.74.vanilla/include/linux/sched.h	Mon Jul  7 16:57:33 2003
+++ linux-2.5.74.mod/include/linux/sched.h	Sun Jul 13 14:33:10 2003
@@ -124,6 +124,8 @@
 #define SCHED_NORMAL		0
 #define SCHED_FIFO		1
 #define SCHED_RR		2
+#define SCHED_SOFTRR		3
+

 struct sched_param {
 	int sched_priority;
diff -Nru linux-2.5.74.vanilla/kernel/sched.c linux-2.5.74.mod/kernel/sched.c
--- linux-2.5.74.vanilla/kernel/sched.c	Mon Jul  7 16:57:33 2003
+++ linux-2.5.74.mod/kernel/sched.c	Sun Jul 13 14:45:42 2003
@@ -76,6 +76,7 @@
 #define MAX_SLEEP_AVG		(10*HZ)
 #define STARVATION_LIMIT	(10*HZ)
 #define NODE_THRESHOLD		125
+#define SCHED_TS_KSOFTRR	4

 /*
  * If a task is 'interactive' then we reinsert it in the active
@@ -158,7 +159,7 @@
 struct runqueue {
 	spinlock_t lock;
 	unsigned long nr_running, nr_switches, expired_timestamp,
-			nr_uninterruptible;
+		nr_uninterruptible, ts_timestamp;
 	task_t *curr, *idle;
 	struct mm_struct *prev_mm;
 	prio_array_t *active, *expired, arrays[2];
@@ -1175,6 +1176,7 @@
 void scheduler_tick(int user_ticks, int sys_ticks)
 {
 	int cpu = smp_processor_id();
+	unsigned int time_slice;
 	runqueue_t *rq = this_rq();
 	task_t *p = current;

@@ -1216,17 +1218,32 @@
 		p->sleep_avg--;
 	if (unlikely(rt_task(p))) {
 		/*
-		 * RR tasks need a special form of timeslice management.
+		 * RR and SOFTRR tasks need a special form of timeslice management.
 		 * FIFO tasks have no timeslices.
 		 */
-		if ((p->policy == SCHED_RR) && !--p->time_slice) {
-			p->time_slice = task_timeslice(p);
+		if ((p->policy == SCHED_RR || p->policy == SCHED_SOFTRR) &&
+		    !--p->time_slice) {
+			p->time_slice = time_slice = task_timeslice(p);
 			p->first_time_slice = 0;
 			set_tsk_need_resched(p);

-			/* put it at the end of the queue: */
+			/*
+			 * We rotate SCHED_RR like POSIX states. On the
+			 * contrary, SCHED_SOFTRR are real-time tasks without
+			 * attitude and we do not want them to starve other
+			 * tasks while we want them to be able to preempt
+			 * SCHED_NORMAL tasks. The rule is that SCHED_SOFTRR
+			 * will be expired if they require roughly more then
+			 * 1/SCHED_TS_KSOFTRR percent of CPU time.
+			 */
 			dequeue_task(p, rq->active);
-			enqueue_task(p, rq->active);
+			if (p->policy == SCHED_RR ||
+			    (jiffies - rq->ts_timestamp) > SCHED_TS_KSOFTRR * time_slice)
+				enqueue_task(p, rq->active);
+			else
+				enqueue_task(p, rq->expired);
+
+			rq->ts_timestamp = jiffies;
 		}
 		goto out_unlock;
 	}
@@ -1243,6 +1260,8 @@
 			enqueue_task(p, rq->expired);
 		} else
 			enqueue_task(p, rq->active);
+
+		rq->ts_timestamp = jiffies;
 	}
 out_unlock:
 	spin_unlock(&rq->lock);
@@ -1740,12 +1759,22 @@
 	else {
 		retval = -EINVAL;
 		if (policy != SCHED_FIFO && policy != SCHED_RR &&
-				policy != SCHED_NORMAL)
+				policy != SCHED_NORMAL && policy != SCHED_SOFTRR)
 			goto out_unlock;
 	}

 	/*
-	 * Valid priorities for SCHED_FIFO and SCHED_RR are
+	 * If the caller requested a SCHED_RR policy without having the
+	 * necessary rights, we downgrade the policy to SCHED_SOFTRR. This
+	 * is currrently here to enable to test the new SOFTRR realtime
+	 * policy with existing programs that try to ask for SCHED_RR. Not
+	 * sure if this should remain as permanent feature.
+	 */
+	if (policy == SCHED_RR && !capable(CAP_SYS_NICE))
+		policy = SCHED_SOFTRR;
+
+	/*
+	 * Valid priorities for SCHED_FIFO, SCHED_RR and SCHED_SOFTRR are
 	 * 1..MAX_USER_RT_PRIO-1, valid priority for SCHED_NORMAL is 0.
 	 */
 	retval = -EINVAL;
@@ -2069,6 +2098,7 @@
 	switch (policy) {
 	case SCHED_FIFO:
 	case SCHED_RR:
+	case SCHED_SOFTRR:
 		ret = MAX_USER_RT_PRIO-1;
 		break;
 	case SCHED_NORMAL:
@@ -2092,6 +2122,7 @@
 	switch (policy) {
 	case SCHED_FIFO:
 	case SCHED_RR:
+	case SCHED_SOFTRR:
 		ret = 1;
 		break;
 	case SCHED_NORMAL:

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Daniel Phillips]

Hi Davide,

On Sunday 13 July 2003 22:51, Davide Libenzi wrote:
> This should (hopefully) avoid other tasks starvation exploits :
>
> http://www.xmailserver.org/linux-patches/softrr.html

   "We will define a new scheduler policy SCHED_SOFTRR that will make the
   target task to run with realtime priority while, at the same time, we will
   enforce a bound for the CPU time the process itself will consume."

This needs to be a global bound, not per-task, otherwise realtime tasks can 
starve the system, as others have noted.

But the patch has a much bigger problem: there is no way a SOFTRR task can be 
realtime as long as higher priority non-realtime tasks can preempt it.  The 
new dynamic priority adjustment makes it certain that we will regularly see 
normal tasks with priority elevated above so-called realtime tasks.  Even 
without dynamic priority adjustment, any higher priority system task can 
unwttingly make a mockery of realtime schedules.

So this approach will not produce the desired result.  To do this properly, 
each realtime task has to have greater priority than any nonrealtime task, 
and obviously, a global bound on realtime CPU share has to be enforced.

Regards,

Daniel

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Mike Galbraith]

At 03:05 PM 8/9/2003 +0100, Daniel Phillips wrote:
>Hi Davide,
>
>On Sunday 13 July 2003 22:51, Davide Libenzi wrote:
> > This should (hopefully) avoid other tasks starvation exploits :
> >
> > http://www.xmailserver.org/linux-patches/softrr.html
>
>    "We will define a new scheduler policy SCHED_SOFTRR that will make the
>    target task to run with realtime priority while, at the same time, we will
>    enforce a bound for the CPU time the process itself will consume."
>
>This needs to be a global bound, not per-task, otherwise realtime tasks can
>starve the system, as others have noted.
>
>But the patch has a much bigger problem: there is no way a SOFTRR task can be
>realtime as long as higher priority non-realtime tasks can preempt it.  The
>new dynamic priority adjustment makes it certain that we will regularly see
>normal tasks with priority elevated above so-called realtime tasks.  Even
>without dynamic priority adjustment, any higher priority system task can
>unwttingly make a mockery of realtime schedules.

Not so.  Dynamic priority adjustment will not put a SCHED_OTHER task above 
SCHED_RR, SCHED_FIFO or SCHED_SOFTRR, so they won't preempt.  Try 
this.  Make a SCHED_FIFO task loop, then try to change vt's.  You won't 
ever get there from here unless you have made 'events' a higher priority 
realtime task than your SCHED_FIFO cpu hog.  (not equal, must be higher 
because SCHED_FIFO can't be requeued via timeslice expiration... since it 
doesn't have one)

I do see ~problems with this idea though...

1.  SCHED_SOFTRR tasks can disturb (root) SCHED_RR/SCHED_FIFO tasks as is. 
SCHED_SOFTRR should probably be a separate band, above SCHED_OTHER, but 
below realtime queues.

2.   It's not useful for video (I see no difference between realtime 
component of video vs audio), and if the cpu restriction were opened up 
enough to become useful, you'd end up with ~pure SCHED_RR, which you can no 
way allow Joe User access to.  As a SCHED_LOWLATENCY, it seems like it 
might be useful, but I wonder how useful.

         -Mike 

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Daniel Phillips]

On Saturday 09 August 2003 18:47, Mike Galbraith wrote:
> 1.  SCHED_SOFTRR tasks can disturb (root) SCHED_RR/SCHED_FIFO tasks as is.

What do you mean by "disturb"?

Regards,

Daniel

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Mike Galbraith]

At 12:58 AM 8/10/2003 +0100, Daniel Phillips wrote:
>On Saturday 09 August 2003 18:47, Mike Galbraith wrote:
> > 1.  SCHED_SOFTRR tasks can disturb (root) SCHED_RR/SCHED_FIFO tasks as is.
>
>What do you mean by "disturb"?

Preempt, and/or occupy cpu space which would otherwise be available for the 
root realtime task.  If a SCHED_SOFTRR task or tasks share the same queue 
with an SCHED_RR task, or occupy a higher queue, runtime of the 
SCHED_SOFTRR tasks[s] will have an effect on the root realtime task.  OTOH, 
if SCHED_SOFTRR queues were below the 'full potency' realtime queues, they 
would be able to neither preempt, not round-robin with the root authorized 
realtime task.

         -Mike 

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Daniel Phillips]

On Saturday 09 August 2003 18:47, Mike Galbraith wrote:
> > But the patch has a much bigger problem: there is no way a SOFTRR task can
> > be realtime as long as higher priority non-realtime tasks can preempt it.
> > The new dynamic priority adjustment makes it certain that we will
> > regularly see normal tasks with priority elevated above so-called
> > realtime tasks.  Even without dynamic priority adjustment, any higher
> > priority system task can unwttingly make a mockery of realtime schedules.
>
> Not so.

Yes so.  A SCHED_NORMAL task with priority n can execute even when a 
SCHED_FIFO/RR/SOFTRR task of priority n-1 is ready.  In the case of FIFO and 
RR we don't care because they're already unusable by normal users but in the 
case of SOFTRR it defeats the intended realtime gaurantee.

> Dynamic priority adjustment will not put a SCHED_OTHER task above
> SCHED_RR, SCHED_FIFO or SCHED_SOFTRR, so they won't preempt.

Are you sure?  I suppose that depends on the particular flavor of dynamic 
priority adjustment.  The last I saw, dynamic priority can adjust the task 
priority by 5 up or down.  If I'm wrong, please show me why and hopefully 
point at specific code.

On the other hand, this doesn't really matter, because the first problem above 
still exists, and causes the same result: attempted realtime scheduling that 
isn't.

Regards,

Daniel

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Mike Galbraith]

At 01:41 AM 8/10/2003 +0100, Daniel Phillips wrote:
>On Saturday 09 August 2003 18:47, Mike Galbraith wrote:
> > > But the patch has a much bigger problem: there is no way a SOFTRR 
> task can
> > > be realtime as long as higher priority non-realtime tasks can preempt it.
> > > The new dynamic priority adjustment makes it certain that we will
> > > regularly see normal tasks with priority elevated above so-called
> > > realtime tasks.  Even without dynamic priority adjustment, any higher
> > > priority system task can unwttingly make a mockery of realtime schedules.
> >
> > Not so.
>
>Yes so.  A SCHED_NORMAL task with priority n can execute even when a
>SCHED_FIFO/RR/SOFTRR task of priority n-1 is ready.  In the case of FIFO and
>RR we don't care because they're already unusable by normal users but in the
>case of SOFTRR it defeats the intended realtime gaurantee.

No, _not_ so.  How is the SCHED_NORMAL (didn't that used to be called 
SCHED_OTHER?) task ever going to receive the cpu when a realtime task is 
runnable given that 1. task selection is done via sched_find_first_bit(), 
and 2. realtime queues reside at the top of the array?

> > Dynamic priority adjustment will not put a SCHED_OTHER task above
> > SCHED_RR, SCHED_FIFO or SCHED_SOFTRR, so they won't preempt.
>
>Are you sure?  I suppose that depends on the particular flavor of dynamic
>priority adjustment.  The last I saw, dynamic priority can adjust the task
>priority by 5 up or down.  If I'm wrong, please show me why and hopefully
>point at specific code.

See the definition of rt_task() in sched.c, and the comments in sched.h 
beginning at line 266.

         -Mike 

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Daniel Phillips]

On Sunday 10 August 2003 07:41, Mike Galbraith wrote:
> At 01:41 AM 8/10/2003 +0100, Daniel Phillips wrote:
> >On Saturday 09 August 2003 18:47, Mike Galbraith wrote:
> > > > But the patch has a much bigger problem: there is no way a SOFTRR task 
> > > > can be realtime as long as higher priority non-realtime tasks can preempt
> > > > it. The new dynamic priority adjustment makes it certain that we will
> > > > regularly see normal tasks with priority elevated above so-called
> > > > realtime tasks.  Even without dynamic priority adjustment, any higher
> > > > priority system task can unwttingly make a mockery of realtime
> > > > schedules.
> > >
> > > Not so.
> >
> >Yes so.  A SCHED_NORMAL task with priority n can execute even when a
> >SCHED_FIFO/RR/SOFTRR task of priority n-1 is ready.  In the case of FIFO
> > and RR we don't care because they're already unusable by normal users but
> > in the case of SOFTRR it defeats the intended realtime gaurantee.
>
> No, _not_ so.  How is the SCHED_NORMAL (didn't that used to be called
> SCHED_OTHER?)

That was just me learning the (funky) terminology.

> task ever going to receive the cpu when a realtime task is
> runnable given that 1. task selection is done via sched_find_first_bit(),
> and 2. realtime queues reside at the top of the array?

OK, got it.  I'd overlooked the strict separation into realtime and
timesliced bands somehow.

> > > Dynamic priority adjustment will not put a SCHED_OTHER task above
> > > SCHED_RR, SCHED_FIFO or SCHED_SOFTRR, so they won't preempt.
> >
> >Are you sure?  I suppose that depends on the particular flavor of dynamic
> >priority adjustment.  The last I saw, dynamic priority can adjust the task
> >priority by 5 up or down.  If I'm wrong, please show me why and hopefully
> >point at specific code.
>
> See the definition of rt_task() in sched.c, and the comments in sched.h
> beginning at line 266.

OK, I believe you now, and this is good, as my fear of high-priority
SCHED_OTHER tasks getting in the way of SOFTRR tasks was bogus. So lets
go back and look at your two concerns:

> 1.  SCHED_SOFTRR tasks can disturb (root) SCHED_RR/SCHED_FIFO tasks as is.
> SCHED_SOFTRR should probably be a separate band, above SCHED_OTHER, but
> below realtime queues.

Nobody promises that root's SCHED_RR/FIFO tasks can get any particular share
of the cpu, only that they will get some CPU provided that all higher-priority
tasks play nicely.  Normal users can take advantage of this hospitality by
taking up to a certain, administer-configured share of the CPU for their own
dark purposes.  Everything is roses and cherries, we haven't broken any rules,
and there's no DoS here.  (Assuming we change the realtime CPU bound to be
global instead of task-local.)

> 2.   It's not useful for video (I see no difference between realtime
> component of video vs audio), and if the cpu restriction were opened up
> enough to become useful, you'd end up with ~pure SCHED_RR, which you can no
> way allow Joe User access to.  As a SCHED_LOWLATENCY, it seems like it
> might be useful, but I wonder how useful.

It's perfectly usable for video, though the administrator may have to
configure a considerably larger share of the cpu for SOFTRR in that case,
especially if a software codec is being used.  I don't see any reason why
the administrator of a single-user system could not make 95% of it available
for realtime media.  The remaining 5% will still be more than a 486 (probably)
which is enough to take care of all the things that the system absolutely
needs to take care of.

That said, I'm only interested in audio at the moment.  If everything works
out, it will be a non-change to use it for video as well.

Regards,

Daniel

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Mike Galbraith]

At 04:46 PM 8/10/2003 +0100, Daniel Phillips wrote:
>On Sunday 10 August 2003 07:41, Mike Galbraith wrote:
>So lets go back and look at your two concerns:
>
> > 1.  SCHED_SOFTRR tasks can disturb (root) SCHED_RR/SCHED_FIFO tasks as is.
> > SCHED_SOFTRR should probably be a separate band, above SCHED_OTHER, but
> > below realtime queues.
>
>Nobody promises that root's SCHED_RR/FIFO tasks can get any particular share
>of the cpu, only that they will get some CPU provided that all higher-priority
>tasks play nicely.  Normal users can take advantage of this hospitality by
>taking up to a certain, administer-configured share of the CPU for their own
>dark purposes.  Everything is roses and cherries, we haven't broken any rules,
>and there's no DoS here.  (Assuming we change the realtime CPU bound to be
>global instead of task-local.)

(Davide already did the global cpu limit)

No, there is no DoS possibility, but it feels a little... unclean.  It 
doesn't appear to accomplish anything other than bypassing 'you must be 
this tall (godly stature) to use this API'.  No matter what limit you put 
on the cpu usage, that amount can (xlat: probably will) be abused.

> > 2.   It's not useful for video (I see no difference between realtime
> > component of video vs audio), and if the cpu restriction were opened up
> > enough to become useful, you'd end up with ~pure SCHED_RR, which you can no
> > way allow Joe User access to.  As a SCHED_LOWLATENCY, it seems like it
> > might be useful, but I wonder how useful.
>
>It's perfectly usable for video, though the administrator may have to
>configure a considerably larger share of the cpu for SOFTRR in that case,
>especially if a software codec is being used.  I don't see any reason why
>the administrator of a single-user system could not make 95% of it available
>for realtime media.  The remaining 5% will still be more than a 486 (probably)
>which is enough to take care of all the things that the system absolutely
>needs to take care of.

On my little box, I'd have to relinquish control of over 50% of my cpu at 
_minimum_ to some random application developer.  (not)

>That said, I'm only interested in audio at the moment.  If everything works
>out, it will be a non-change to use it for video as well.

Oh, I'm sure it'll work.  What I tested briefly worked fine.  However, I'm 
not sure that it's a good (or bad) idea.

         -Mike 

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Daniel Phillips]

On Sunday 10 August 2003 18:49, Mike Galbraith wrote:
> It doesn't appear to accomplish anything other than bypassing 'you must be
> this tall (godly stature) to use this API'.

But it is a big deal.  It means Linux can have superior audio performance 
out-of-the-box, without having to run sound apps suid.  From what I've seen,  
you do not want to let a typical sound app have free reign over your machine.  
Not that they're malicious, but they do seem to be breeding grounds for 
buffer overflows, races, dangling pointers, etc.

> No matter what limit you put on the cpu usage, that amount can (xlat:
> probably will) be abused.

How?  Anybody user can run an empty loop right now and it will have 
approximately the same effect, i.e., it will use some cpu, big deal.  The 
other danger is that the latency of certain kernel threads could be 
increased, e.g., kswapd, ksoftirqd, keventd.  Here, a malicious softrr 
application could only cause increased latency during the realtime slice, so 
there's a cap on that.  And anyway, why aren't those kernel threads running 
with realtime priority in the first place?

While we're in here: what should be the maximum realtime priority granted to a 
normal user?  It should probably be another adminstrator knob.

> On my little box, I'd have to relinquish control of over 50% of my cpu at
> _minimum_ to some random application developer.  (not)

It's your decision[tm].  At least you know that slowing down your kernel 
compile is about the worst fallout you can expect from being wanton and 
promiscuous with your chmod +x's.  More precisely, if you do get rooted, it 
will have nothing to do with softrr ;-)

The idea is, if the administrator decides not to let them have realtime 
priority, sound apps will just have to do the best they can, with large 
buffers etc, as they have been forced to until now.

> ...I'm sure it'll work.  What I tested briefly worked fine.  However, I'm
> not sure that it's a good (or bad) idea.

Well, perhaps it's time to get a word from a couple guys out there in the 
trenches.  Takashi, Conrad, any thoughts on the relative importance of this?  
(Technical details are earlier in this thread.)

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Mike Galbraith]

At 09:28 PM 8/10/2003 +0100, Daniel Phillips wrote:

>there's a cap on that.  And anyway, why aren't those kernel threads running
>with realtime priority in the first place?

Good question.  events, kblockd and aio at least look like they should.

>While we're in here: what should be the maximum realtime priority granted 
>to a
>normal user?  It should probably be another adminstrator knob.

That's an easy one.. the top of the SCHED_SOFTRR range ;)

         -Mike 

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Takashi Iwai]

At Sun, 10 Aug 2003 21:28:49 +0100,
Daniel Phillips wrote:
> 
> On Sunday 10 August 2003 18:49, Mike Galbraith wrote:
> > It doesn't appear to accomplish anything other than bypassing 'you must be
> > this tall (godly stature) to use this API'.
> 
> But it is a big deal.  It means Linux can have superior audio performance 
> out-of-the-box, without having to run sound apps suid.  From what I've seen,  
> you do not want to let a typical sound app have free reign over your machine.  
> Not that they're malicious, but they do seem to be breeding grounds for 
> buffer overflows, races, dangling pointers, etc.
 
well, although i see also a big win by this step, too, i understand
also a same "fear" for getting the system too free for all users.
at least, the current situation is that there is no user/task
restriction at all.  so, if you set up 50% soft-RR, you'll always have
a danger that anon user takes 50% all the time.
i think it would be nice if we have additionally some user/task-base
restrictions, too.

perhaps it's a job of some wrapper library.  suppose a library which
works like utempter library: checking the calling process
path whether it's a registered one, and gives the RT and mlock
capabilities to the caller in return.  these capabilities are dropped
after executing the syscalls in the wrapper lib.
this requires CAP_SETPCAP capability and one suid-root exec binary...


> > ...I'm sure it'll work.  What I tested briefly worked fine.  However, I'm
> > not sure that it's a good (or bad) idea.
> 
> Well, perhaps it's time to get a word from a couple guys out there in the 
> trenches.  Takashi, Conrad, any thoughts on the relative importance of this?  
> (Technical details are earlier in this thread.)

ok, there are mainly two directions for audio apps.

1. player programs like xmms
2. real-time audio systems (and apps) like JACK.

so, what we'll gain by soft-RR?

in the first case, which most of us are facinig, we can have the
higher priority for the audio thread with soft-RR quite easily and
more safely.  the audio-thread needs usually woken up every 0.1 or 0.2
seconds fairly precisely.  this is a main reason of drop out in
playing mp3's.  other threads (main control, decoding, graphic, etc.)
are not necessarily scheduled with a higher priority at all.

in the second case, the higher RT-priority is a "must".  since the
whole process-chain is supposed to run in a low latency, they should
be scheduled in RT.
IMO, in this area, the soft-RR is a best choice.  it prevents a
lock-up even if one of the RT-scheduled processes gets crazy.  it
guarantees the rock-stable system as an audio workstation.

as said, i think the permission is another question.  there can be
better solutions.
but even without the (default) permission to normal users, the soft-RR
scheduler is surely a great help for RT apps.

-- 
Takashi Iwai <tiwai@suse.de>		SuSE Linux AG - www.suse.de
ALSA Developer				ALSA Project - www.alsa-project.org

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Roger Larsson]

On Saturday 09 August 2003 19.47, Mike Galbraith wrote:
> At 03:05 PM 8/9/2003 +0100, Daniel Phillips wrote:
> >Hi Davide,
> >
> >On Sunday 13 July 2003 22:51, Davide Libenzi wrote:
> > > This should (hopefully) avoid other tasks starvation exploits :
> > >
> > > http://www.xmailserver.org/linux-patches/softrr.html
> >
> >    "We will define a new scheduler policy SCHED_SOFTRR that will make the
> >    target task to run with realtime priority while, at the same time, we
> > will enforce a bound for the CPU time the process itself will consume."
> >
> >This needs to be a global bound, not per-task, otherwise realtime tasks
> > can starve the system, as others have noted.
> >
> >But the patch has a much bigger problem: there is no way a SOFTRR task can
> > be realtime as long as higher priority non-realtime tasks can preempt it.
> >  The new dynamic priority adjustment makes it certain that we will
> > regularly see normal tasks with priority elevated above so-called
> > realtime tasks.  Even without dynamic priority adjustment, any higher
> > priority system task can unwttingly make a mockery of realtime schedules.
>
> Not so.  Dynamic priority adjustment will not put a SCHED_OTHER task above
> SCHED_RR, SCHED_FIFO or SCHED_SOFTRR, so they won't preempt.  Try
> this.  Make a SCHED_FIFO task loop, then try to change vt's.  You won't
> ever get there from here unless you have made 'events' a higher priority
> realtime task than your SCHED_FIFO cpu hog.  (not equal, must be higher
> because SCHED_FIFO can't be requeued via timeslice expiration... since it
> doesn't have one)
>
> I do see ~problems with this idea though...
>
> 1.  SCHED_SOFTRR tasks can disturb (root) SCHED_RR/SCHED_FIFO tasks as is.
> SCHED_SOFTRR should probably be a separate band, above SCHED_OTHER, but
> below realtime queues.
>

I would prefere to have it as a sub range "min real RT" <SOFT_RR range < mean 
real RT. Using SOFTRR time slice that is inverse proportional with the level 
might also be beneficial.

> 2.   It's not useful for video (I see no difference between realtime
> component of video vs audio), and if the cpu restriction were opened up
> enough to become useful, you'd end up with ~pure SCHED_RR, which you can no
> way allow Joe User access to.  As a SCHED_LOWLATENCY, it seems like it
> might be useful, but I wonder how useful.

Why shouldn't it be useful with video, is a frame processing burst longer than 
a time slice? The rule for when to and how to revert a SCHED_SOFTRR can be 
changed.

*	SCHED_FIFO requests from non root should also be treated as SCHED_SOFTRR

/Rogerl

-- 
Roger Larsson
Skellefteå
Sweden

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Nick Piggin]

Roger Larsson wrote:

>*	SCHED_FIFO requests from non root should also be treated as SCHED_SOFTRR
>
>

I hope computers don't one day become so fast that SCHED_SOFTRR is
required for skipless mp3 decoding, but if they do, then I think
SCHED_SOFTRR should drop its weird polymorphing semantics ;)

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Mike Galbraith]

At 03:43 PM 8/10/2003 +1000, Nick Piggin wrote:


>Roger Larsson wrote:
>
>>*       SCHED_FIFO requests from non root should also be treated as 
>>SCHED_SOFTRR
>>
>
>I hope computers don't one day become so fast that SCHED_SOFTRR is
>required for skipless mp3 decoding, but if they do, then I think
>SCHED_SOFTRR should drop its weird polymorphing semantics ;)

:)  My box is slow enough to handle them just fine, as long as I make sure 
that oinkers don't share the same queue with the light weight player.

The only reason I can see that some form of realtime scheduling is really 
_required_ to prevent skippage is because of the dirty page writeout thing, 
which Andrew has fixed as much as is practical for realtime tasks.  There 
is another side to that though... if you're going to make a vm scrubbing 
exception for realtime tasks, it seems to me to follow, that rt task's mm 
should be exempted from scrubbers as well (to a point).

wrt SCHED_FIFO, you couldn't handle those with SOFTRR as is, because the 
cpu restriction is calculated using the task's timeslice... which 
SCHED_FIFO tasks don't have.  Making SCHED_FIFO available in any form would 
require addition of some means of detecting cpu usage.  (and if you create 
any run limit, you may as well just use a timeslice, which turns it right 
back into SCHED_RR).

         -Mike 

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Nick Piggin]

Mike Galbraith wrote:

> At 03:43 PM 8/10/2003 +1000, Nick Piggin wrote:
>
>
>> Roger Larsson wrote:
>>
>>> *       SCHED_FIFO requests from non root should also be treated as 
>>> SCHED_SOFTRR
>>>
>>
>> I hope computers don't one day become so fast that SCHED_SOFTRR is
>> required for skipless mp3 decoding, but if they do, then I think
>> SCHED_SOFTRR should drop its weird polymorphing semantics ;)
>
>
> :)  My box is slow enough to handle them just fine, as long as I make 
> sure that oinkers don't share the same queue with the light weight 
> player.


Just my (unsuccessful) attempt at humor! I think SCHED_SOFTRR is great,
although probably fills a quite small niche between SCHED_OTHER and
the realtime scheduling while being a possibility for security problems
(don't know, maybe that that is sorted?). But...

Some of the people saying playback needs to be realtime are right for
absolutely 100%, but seem to have forgotten that their pentium 100 did
just fine, and that a skip now and again probably doesn't signal the
end of the world.

I think its fairly obvious that it indicates there are problems with
the general purpose scheduler. Thankfully it is getting addressed,
which makes this just a rant ;)

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Mike Galbraith]

At 05:56 PM 8/10/2003 +1000, Nick Piggin wrote:


>Mike Galbraith wrote:
>
>>At 03:43 PM 8/10/2003 +1000, Nick Piggin wrote:
>>
>>
>>>Roger Larsson wrote:
>>>
>>>>*       SCHED_FIFO requests from non root should also be treated as 
>>>>SCHED_SOFTRR
>>>
>>>I hope computers don't one day become so fast that SCHED_SOFTRR is
>>>required for skipless mp3 decoding, but if they do, then I think
>>>SCHED_SOFTRR should drop its weird polymorphing semantics ;)
>>
>>
>>:)  My box is slow enough to handle them just fine, as long as I make 
>>sure that oinkers don't share the same queue with the light weight player.
>
>
>Just my (unsuccessful) attempt at humor!

(was successful here... made for wide grin:)

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[jw schultz]

On Sun, Aug 10, 2003 at 10:18:43AM +0200, Mike Galbraith wrote:
> At 05:56 PM 8/10/2003 +1000, Nick Piggin wrote:
> 
> 
> >Mike Galbraith wrote:
> >
> >>At 03:43 PM 8/10/2003 +1000, Nick Piggin wrote:
> >>
> >>
> >>>Roger Larsson wrote:
> >>>
> >>>>*       SCHED_FIFO requests from non root should also be treated as 
> >>>>SCHED_SOFTRR
> >>>
> >>>I hope computers don't one day become so fast that SCHED_SOFTRR is
> >>>required for skipless mp3 decoding, but if they do, then I think
> >>>SCHED_SOFTRR should drop its weird polymorphing semantics ;)
> >>
> >>
> >>:)  My box is slow enough to handle them just fine, as long as I make 
> >>sure that oinkers don't share the same queue with the light weight player.
> >
> >
> >Just my (unsuccessful) attempt at humor!
> 
> (was successful here... made for wide grin:)

Here too.

You know, that SCHED_SOFTRR is almost sounding like it
should be a SCHED_RESERVED where you could specify a
quantity of CPU time reserved for each task in
SCHED_RESERVED individually rather like isochronous which
was brought up earlier by Con.  Of course you'd have to make
sure some time was unreservable.

-- 
________________________________________________________________
	J.W. Schultz            Pegasystems Technologies
	email address:		jw@pegasys.ws

		Remember Cernan and Schmitt

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Roger Larsson]

On Sunday 10 August 2003 07.43, Nick Piggin wrote:
> Roger Larsson wrote:
> >*	SCHED_FIFO requests from non root should also be treated as SCHED_SOFTRR
>
> I hope computers don't one day become so fast that SCHED_SOFTRR is
> required for skipless mp3 decoding, but if they do, then I think
> SCHED_SOFTRR should drop its weird polymorphing semantics ;)

After some tinking...

Neither SCHED_FIFO nor SCHED_RR should automatically be promoted to 
SCHED_SOFTRR in the kernel.

* If a process knows about SCHED_SOFTRR it should use that.
  (example: arts should use SCHED_SOFTRR not SCHED_FIFO)
  Problem: what to do when compiling for UN*Xes that does not have SOFTRR.
  [Is there any other UN*X that have something resembling of this? What do
   they call it?]

* Cases where the code has not been modified should be handled by a wrapper
  (library). setscheduler is a weak symbol isn't it?

/RogerL

-- 
Roger Larsson
Skellefteå
Sweden

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Takashi Iwai]

At Mon, 11 Aug 2003 19:01:13 +0200,
Roger Larsson wrote:
> 
> On Sunday 10 August 2003 07.43, Nick Piggin wrote:
> > Roger Larsson wrote:
> > >*	SCHED_FIFO requests from non root should also be treated as SCHED_SOFTRR
> >
> > I hope computers don't one day become so fast that SCHED_SOFTRR is
> > required for skipless mp3 decoding, but if they do, then I think
> > SCHED_SOFTRR should drop its weird polymorphing semantics ;)
> 
> After some tinking...
> 
> Neither SCHED_FIFO nor SCHED_RR should automatically be promoted to 
> SCHED_SOFTRR in the kernel.
> 
> * If a process knows about SCHED_SOFTRR it should use that.
>   (example: arts should use SCHED_SOFTRR not SCHED_FIFO)
>   Problem: what to do when compiling for UN*Xes that does not have SOFTRR.
>   [Is there any other UN*X that have something resembling of this? What do
>    they call it?]
> 
> * Cases where the code has not been modified should be handled by a wrapper
>   (library). setscheduler is a weak symbol isn't it?

i agree here.

i understand it's introduced for convenience, but the apps are anyway
to be modified to adapt SOFTRR with normal users in most cases
(e.g. checking the uid, etc)...


Takashi

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Mike Galbraith]

At 04:05 AM 8/10/2003 +0200, Roger Larsson wrote:
>On Saturday 09 August 2003 19.47, Mike Galbraith wrote:
> > At 03:05 PM 8/9/2003 +0100, Daniel Phillips wrote:
> > >Hi Davide,
> > >
> > >On Sunday 13 July 2003 22:51, Davide Libenzi wrote:
> > > > This should (hopefully) avoid other tasks starvation exploits :
> > > >
> > > > http://www.xmailserver.org/linux-patches/softrr.html
> > >
> > >    "We will define a new scheduler policy SCHED_SOFTRR that will make the
> > >    target task to run with realtime priority while, at the same time, we
> > > will enforce a bound for the CPU time the process itself will consume."
> > >
> > >This needs to be a global bound, not per-task, otherwise realtime tasks
> > > can starve the system, as others have noted.
> > >
> > >But the patch has a much bigger problem: there is no way a SOFTRR task can
> > > be realtime as long as higher priority non-realtime tasks can preempt it.
> > >  The new dynamic priority adjustment makes it certain that we will
> > > regularly see normal tasks with priority elevated above so-called
> > > realtime tasks.  Even without dynamic priority adjustment, any higher
> > > priority system task can unwttingly make a mockery of realtime schedules.
> >
> > Not so.  Dynamic priority adjustment will not put a SCHED_OTHER task above
> > SCHED_RR, SCHED_FIFO or SCHED_SOFTRR, so they won't preempt.  Try
> > this.  Make a SCHED_FIFO task loop, then try to change vt's.  You won't
> > ever get there from here unless you have made 'events' a higher priority
> > realtime task than your SCHED_FIFO cpu hog.  (not equal, must be higher
> > because SCHED_FIFO can't be requeued via timeslice expiration... since it
> > doesn't have one)
> >
> > I do see ~problems with this idea though...
> >
> > 1.  SCHED_SOFTRR tasks can disturb (root) SCHED_RR/SCHED_FIFO tasks as is.
> > SCHED_SOFTRR should probably be a separate band, above SCHED_OTHER, but
> > below realtime queues.
> >
>
>I would prefere to have it as a sub range "min real RT" <SOFT_RR range < mean
>real RT. Using SOFTRR time slice that is inverse proportional with the level
>might also be beneficial.

Yes, if there are more than one running, you reduce scheduler latency.  It 
seems to me that it would also be useful to include short term cpu history 
into priority scaling, such that if a task starts consuming it's slice, it 
would be quickly detected, and that task would only be able to dork up 
others latency requirements for a slice or two before being demoted.

> > 2.   It's not useful for video (I see no difference between realtime
> > component of video vs audio), and if the cpu restriction were opened up
> > enough to become useful, you'd end up with ~pure SCHED_RR, which you can no
> > way allow Joe User access to.  As a SCHED_LOWLATENCY, it seems like it
> > might be useful, but I wonder how useful.
>
>Why shouldn't it be useful with video, is a frame processing burst longer 
>than
>a time slice? The rule for when to and how to revert a SCHED_SOFTRR can be
>changed.

Everything I've seen says "you need at least a 300Mhz cpu to decode".  My 
little cpu is 500Mhz, so I'd have to make more than half of my total 
computational power available for SCHED_SOFTRR tasks for video decode in 
realtime to work.  Even on my single user box, I wouldn't want to have to 
fight for cpu because some random developer decided to use 
SCHED_SOFTRR.  If I make that much cpu available, someone will try to use 
it.  Personally, I think you should need authorization for even tiny 
amounts of cpu at this priority.

         -Mike 

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Rob Landley]

On Sunday 10 August 2003 03:11, Mike Galbraith wrote:
> Everything I've seen says "you need at least a 300Mhz cpu to decode".  My
> little cpu is 500Mhz, so I'd have to make more than half of my total
> computational power available for SCHED_SOFTRR tasks for video decode in
> realtime to work.  Even on my single user box, I wouldn't want to have to
> fight for cpu because some random developer decided to use
> SCHED_SOFTRR.  If I make that much cpu available, someone will try to use
> it.  Personally, I think you should need authorization for even tiny
> amounts of cpu at this priority.
>
>          -Mike

Perhaps you want some kind of extension to "renice" to allow a running process 
to be have its percent chopped back then?  (Without necessarily affecting the 
global reserve?)

Shouldn't require root, just require running as the same user as the process.  
(if you can 'kill -SIGSTOP" a task, you should be able to reduce its 
priority...)

Rob

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Pavel Machek]

Hi!

> >> 2.   It's not useful for video (I see no difference between realtime
> >> component of video vs audio), and if the cpu restriction were opened up
> >> enough to become useful, you'd end up with ~pure SCHED_RR, which you can 
> >no
> >> way allow Joe User access to.  As a SCHED_LOWLATENCY, it seems like it
> >> might be useful, but I wonder how useful.
> >
> >Why shouldn't it be useful with video, is a frame processing burst longer 
> >than
> >a time slice? The rule for when to and how to revert a SCHED_SOFTRR can be
> >changed.
> 
> Everything I've seen says "you need at least a 300Mhz cpu to decode".  My 
> little cpu is 500Mhz, so I'd have to make more than half of my total 
> computational power available for SCHED_SOFTRR tasks for video decode in 
> realtime to work.  Even on my single user box, I wouldn't want to have to 
> fight for cpu because some random developer decided to use 
> SCHED_SOFTRR.  If I make that much cpu available, someone will try to use 
> it.  Personally, I think you should need authorization for even tiny 
> amounts of cpu at this priority.

What about only offering SCHED_SOFTRR to people logged in on console,
similar to way cdrom and /dev/dsp is handled on newer boxes?
								Pavel
-- 
When do you have a heart between your knees?
[Johanka's followup: and *two* hearts?]

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Mike Galbraith]

At 01:35 AM 8/13/2003 +0200, Pavel Machek wrote:
>Hi!
>
> > >> 2.   It's not useful for video (I see no difference between realtime
> > >> component of video vs audio), and if the cpu restriction were opened up
> > >> enough to become useful, you'd end up with ~pure SCHED_RR, which you 
> can
> > >no
> > >> way allow Joe User access to.  As a SCHED_LOWLATENCY, it seems like it
> > >> might be useful, but I wonder how useful.
> > >
> > >Why shouldn't it be useful with video, is a frame processing burst longer
> > >than
> > >a time slice? The rule for when to and how to revert a SCHED_SOFTRR can be
> > >changed.
> >
> > Everything I've seen says "you need at least a 300Mhz cpu to decode".  My
> > little cpu is 500Mhz, so I'd have to make more than half of my total
> > computational power available for SCHED_SOFTRR tasks for video decode in
> > realtime to work.  Even on my single user box, I wouldn't want to have to
> > fight for cpu because some random developer decided to use
> > SCHED_SOFTRR.  If I make that much cpu available, someone will try to use
> > it.  Personally, I think you should need authorization for even tiny
> > amounts of cpu at this priority.
>
>What about only offering SCHED_SOFTRR to people logged in on console,
>similar to way cdrom and /dev/dsp is handled on newer boxes?

I'm always logged in on console, so with no authorization required, it'd 
always be available to every task I start.

         -Mike 

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Pavel Machek]

Hi!

> >> >> 2.   It's not useful for video (I see no difference between realtime
> >> >> component of video vs audio), and if the cpu restriction were opened 
> >up
> >> >> enough to become useful, you'd end up with ~pure SCHED_RR, which you 
> >can
> >> >no
> >> >> way allow Joe User access to.  As a SCHED_LOWLATENCY, it seems like it
> >> >> might be useful, but I wonder how useful.
> >> >
> >> >Why shouldn't it be useful with video, is a frame processing burst 
> >longer
> >> >than
> >> >a time slice? The rule for when to and how to revert a SCHED_SOFTRR can 
> >be
> >> >changed.
> >>
> >> Everything I've seen says "you need at least a 300Mhz cpu to decode".  My
> >> little cpu is 500Mhz, so I'd have to make more than half of my total
> >> computational power available for SCHED_SOFTRR tasks for video decode in
> >> realtime to work.  Even on my single user box, I wouldn't want to have to
> >> fight for cpu because some random developer decided to use
> >> SCHED_SOFTRR.  If I make that much cpu available, someone will try to use
> >> it.  Personally, I think you should need authorization for even tiny
> >> amounts of cpu at this priority.
> >
> >What about only offering SCHED_SOFTRR to people logged in on console,
> >similar to way cdrom and /dev/dsp is handled on newer boxes?
> 
> I'm always logged in on console, so with no authorization required, it'd 
> always be available to every task I start.

Which is pretty much okay. Remember that UID (not PID) is security
barier. If one of your processes is able to do X, all other processes
running under your PID are able to do X, too. (Modulo processes with
few differend PIDs, its more complicated then.)

								Pavel
-- 
When do you have a heart between your knees?
[Johanka's followup: and *two* hearts?]

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Davide Libenzi]

On Mon, 14 Jul 2003, Mike Galbraith wrote:

> At 02:51 PM 7/13/2003 -0700, Davide Libenzi wrote:
>
> >This should (hopefully) avoid other tasks starvation exploits :
> >
> >http://www.xmailserver.org/linux-patches/softrr.html
>
> Yes, that ~works.  I couldn't starve root to death as a SCHED_SOFTRR user,
> but the system was very sluggish, with keystrokes taking uncomfortably
> long.  I also had some sound skips due to inheritance.  If I activate
> xmms's gl visualization under load, it inherits SCHED_SOFTRR, says "oink"
> in a very deep voice, and other xmms threads expire.  Maybe tasks shouldn't
> inherit SCHED_SOFTRR?

You might want to increase the K_something from 4 (25% CPU time) to a
lower value. Also, SOFTRR tasks should get a lower timeslice while they're
currently getting the RR one. The SOFTRR policy should be used by MM apps
in a way that the thread that uses it does the minimum amount of work in
there. Like the thing we do with IRQ processing.



> While testing, I spotted something pretty strange.  It's not specific to
> SCHED_SOFTRR, SCHED_RR causes it too.  If I fire up xmms's gl visualization
> with either policy, X stops getting enough sleep credit to stay at a usable
> priority even when cpu usage is low.  Fully repeatable weirdness.  See
> attached top snapshots.

RT tasks are pretty powerfull and should not be used to run everything ;)
What I was seeking with this patch was 1) deterministic latency 2) stave
protection.



- Davide

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Jamie Lokier]

Mike Galbraith wrote:
> I also had some sound skips due to inheritance.  If I activate
> xmms's gl visualization under load, it inherits SCHED_SOFTRR, says
> "oink" in a very deep voice, and other xmms threads expire.  Maybe
> tasks shouldn't inherit SCHED_SOFTRR?

That's likely a bug in xmms - it shouldn't be passing the normal
SCHED_RR state to the gl visualizer.

Maybe SOFTRR should penalise the most CPU-using SOFTRR tasks, leaving
the remaining ones in the real-time state.

-- Jamie

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Davide Libenzi]

On Mon, 14 Jul 2003, Jamie Lokier wrote:

> Mike Galbraith wrote:
> > I also had some sound skips due to inheritance.  If I activate
> > xmms's gl visualization under load, it inherits SCHED_SOFTRR, says
> > "oink" in a very deep voice, and other xmms threads expire.  Maybe
> > tasks shouldn't inherit SCHED_SOFTRR?
>
> That's likely a bug in xmms - it shouldn't be passing the normal
> SCHED_RR state to the gl visualizer.
>
> Maybe SOFTRR should penalise the most CPU-using SOFTRR tasks, leaving
> the remaining ones in the real-time state.

Since xmms is unlikely already supporting SOFTRR :) I believe that he did
what I did with RealPlay, let it get the policy for inheritance. In my
case RealPlay (only with sound) did not skip even under thud.c load.



- Davide

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Mike Galbraith]

At 08:24 AM 7/14/2003 +0100, Jamie Lokier wrote:
>Mike Galbraith wrote:
> > I also had some sound skips due to inheritance.  If I activate
> > xmms's gl visualization under load, it inherits SCHED_SOFTRR, says
> > "oink" in a very deep voice, and other xmms threads expire.  Maybe
> > tasks shouldn't inherit SCHED_SOFTRR?
>
>That's likely a bug in xmms - it shouldn't be passing the normal
>SCHED_RR state to the gl visualizer.

If I set xmms SCHED_RR, it does drop it for the visualizer.  (I promptly 
re-set it to test the X oddness) I presume it's stumbling over the policy.

         -Mike 

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Mike Galbraith]

At 12:12 AM 7/14/2003 -0700, Davide Libenzi wrote:
>On Mon, 14 Jul 2003, Mike Galbraith wrote:
> > While testing, I spotted something pretty strange.  It's not specific to
> > SCHED_SOFTRR, SCHED_RR causes it too.  If I fire up xmms's gl visualization
> > with either policy, X stops getting enough sleep credit to stay at a usable
> > priority even when cpu usage is low.  Fully repeatable weirdness.  See
> > attached top snapshots.
>
>RT tasks are pretty powerfull and should not be used to run everything ;)
>What I was seeking with this patch was 1) deterministic latency 2) stave
>protection.

Yes, I know.  I only fired up the cpu hog as a test to see that the 
protection would kick in.  I did do that too though, ran _everything_... 
the whole X/KDE beast SCHED_SOFTRR for grins :)

I should have reported the strangeness in a different thread, it has 
nothing to do with your patch.

         -Mike  

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Davide Libenzi]

On Mon, 14 Jul 2003, Mike Galbraith wrote:

> At 12:12 AM 7/14/2003 -0700, Davide Libenzi wrote:
> >On Mon, 14 Jul 2003, Mike Galbraith wrote:
> > > While testing, I spotted something pretty strange.  It's not specific to
> > > SCHED_SOFTRR, SCHED_RR causes it too.  If I fire up xmms's gl visualization
> > > with either policy, X stops getting enough sleep credit to stay at a usable
> > > priority even when cpu usage is low.  Fully repeatable weirdness.  See
> > > attached top snapshots.
> >
> >RT tasks are pretty powerfull and should not be used to run everything ;)
> >What I was seeking with this patch was 1) deterministic latency 2) stave
> >protection.
>
> Yes, I know.  I only fired up the cpu hog as a test to see that the
> protection would kick in.  I did do that too though, ran _everything_...
> the whole X/KDE beast SCHED_SOFTRR for grins :)
>
> I should have reported the strangeness in a different thread, it has
> nothing to do with your patch.

Did you try the skip resistance test by running XMMS alone with audio ?
Also, trying the whole player running with SOFTRR does not match the
effective use MM apps will do of it. Usually inside MM apps the data
decoder (that might suck CPU) lives in another thread and the thread that
is actually responsible for timings simply fetch the prepared data.



- Davide

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Mike Galbraith]

At 08:09 AM 7/14/2003 -0700, Davide Libenzi wrote:
>On Mon, 14 Jul 2003, Mike Galbraith wrote:
>
> > At 12:12 AM 7/14/2003 -0700, Davide Libenzi wrote:
> > >On Mon, 14 Jul 2003, Mike Galbraith wrote:
> > > > While testing, I spotted something pretty strange.  It's not 
> specific to
> > > > SCHED_SOFTRR, SCHED_RR causes it too.  If I fire up xmms's gl 
> visualization
> > > > with either policy, X stops getting enough sleep credit to stay at 
> a usable
> > > > priority even when cpu usage is low.  Fully repeatable weirdness.  See
> > > > attached top snapshots.
> > >
> > >RT tasks are pretty powerfull and should not be used to run everything ;)
> > >What I was seeking with this patch was 1) deterministic latency 2) stave
> > >protection.
> >
> > Yes, I know.  I only fired up the cpu hog as a test to see that the
> > protection would kick in.  I did do that too though, ran _everything_...
> > the whole X/KDE beast SCHED_SOFTRR for grins :)
> >
> > I should have reported the strangeness in a different thread, it has
> > nothing to do with your patch.
>
>Did you try the skip resistance test by running XMMS alone with audio ?

Yes, and it worked fine.  No cpu load I tossed at it caused a skip.

         -Mike 

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Davide Libenzi]

On Mon, 14 Jul 2003, Mike Galbraith wrote:

> Yes, and it worked fine.  No cpu load I tossed at it caused a skip.

I tried yesterday a thud.c load and it did not get a single skip here
either. It is interesting what thud.c can do to latency (let's not talk
about irman because things get really nasty). With a simple `thud 5` the
latency rised to more then one full second, as you can see by the graphs
inside the SOFTRR page. No buffer size can cope with that.



- Davide

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Mike Galbraith]

At 10:22 AM 7/14/2003 -0700, Davide Libenzi wrote:
>On Mon, 14 Jul 2003, Mike Galbraith wrote:
>
> > Yes, and it worked fine.  No cpu load I tossed at it caused a skip.
>
>I tried yesterday a thud.c load and it did not get a single skip here
>either. It is interesting what thud.c can do to latency (let's not talk
>about irman because things get really nasty). With a simple `thud 5` the
>latency rised to more then one full second, as you can see by the graphs
>inside the SOFTRR page. No buffer size can cope with that.

Yes, thud is well named.  It's easy to kill, but not so easy to kill 
without hurting important dynamic response characteristics and/or 
interactivity.

For sound purposes, all you have to do is make damn sure that thud/others 
can't get to the queue where your sound client lives.  I'm using a very 
short term weighted slice_avg for that... your %cpu is calculated for each 
slice, and once you approach interactive status, it doubles for each 
priority you climb.  That makes it very hard indeed for a cpu hog to ever 
reach the top.  Almost nothing can touch xmms here.  It doesn't provide the 
nearly 100% guarantee that SOFT_RR does, but otoh, it's absolutely 
impossible to abuse.

(my best interactive effort combined that with non-linear decay, and 
throttled backboost to offset the fairness pain that X any friends feel... 
it's quite good, but [butt ugly and:] not quite good enough)

         -Mike 

Re: [patch] SCHED_SOFTRR starve-free linux scheduling policy ...

[Davide Libenzi]

On Tue, 15 Jul 2003, Mike Galbraith wrote:

> At 10:22 AM 7/14/2003 -0700, Davide Libenzi wrote:
> >On Mon, 14 Jul 2003, Mike Galbraith wrote:
> >
> > > Yes, and it worked fine.  No cpu load I tossed at it caused a skip.
> >
> >I tried yesterday a thud.c load and it did not get a single skip here
> >either. It is interesting what thud.c can do to latency (let's not talk
> >about irman because things get really nasty). With a simple `thud 5` the
> >latency rised to more then one full second, as you can see by the graphs
> >inside the SOFTRR page. No buffer size can cope with that.
>
> Yes, thud is well named.  It's easy to kill, but not so easy to kill
> without hurting important dynamic response characteristics and/or
> interactivity.

The problem with thud and irman is not the sound. If it was only that I'd
be rather happy. Try to get the simplified version of the irman I dropped
inside the SOFTRR (didn't try to original, it's maybe even worse) page and
run it with '-n 40 -b 350' for example. Then try to buld a kernel.
Yesterday on my Athlon 1GHz 768MB of RAM where usually the kernel takes
8:33 to build (2.5), after 15 minutes I had only two lines printed on my
screen. We can easily say that sound can break under those corner cases,
but we cannot say that anything but super-interactive tasks will run on
such a system. This is Unix and ppl still uses it in a multiuser fashion.
In every system (not only in computer science) where there is no fairness,
there will be someone ready to take advantage (exploit) of it. We use to
sacrify fairness for interactivity, and this is good since interactivity
is a good thing. Whatever you tune your sleep->burn cycle, someone will be
able to exploit it by trying to get the more CPU you give away to
interactive tasks. This multiplied for a limited number of tasks will make
the system to hugely suck away CPU from anything but super-interactive
tasks. We need to have a limit to the CPU that we assign to interactive
tasks (something like 70/30 or whatever), so that we don't completely
starve the non-interactive world (see "Scheduler woes" post). This is
critical for multiuser systems IMHO.




- Davide