Re: [SCHED] wrong priority calc - SIMPLE test case

[Mike Galbraith <efault@gmx.de>]

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

At 12:11 PM 1/9/2006 +0100, Mike Galbraith wrote:

>Care to try an experiment?...

Oops.  I guess I should send one that's not mixed p1 and p0.  Sorry about 
that :-/

Anyway, if anyone wants to see a functional demonstration, just try 
this.  Remove the TASK_NONINTERACTIVE in fs/pipe.c in both the stock kernel 
and this modified one so Davide Libenzi's excellent sleep pattern exploit 
(irman2) can work [1], and do the below all at the same time ...

make -j4 bzImage
irman2
thud 3

With the stock kernel, I got bored after a half an hour, and stopped the 
kernel build.  It had produced 40 .o files.  The modified kernel finished 
in 20 minutes vs the 8 minutes it took to produce the same 504 .o files if 
not under load.

         -Mike

1.  it just so happens that Davide wrote irman2 using pipes... he could 
have done something else.  if anyone doesn't think this is a fair test, 
just use Paolo's much simpler exploit instead.  the result will be about 
the same. 

[-- Attachment #2: sched_throttle --]
[-- Type: application/octet-stream, Size: 3655 bytes --]

--- linux-2.6.15/include/linux/sched.h.org	Tue Jan  3 09:26:50 2006
+++ linux-2.6.15/include/linux/sched.h	Sat Jan  7 14:45:37 2006
@@ -701,8 +701,8 @@
 
 	unsigned short ioprio;
 
-	unsigned long sleep_avg;
-	unsigned long long timestamp, last_ran;
+	unsigned long sleep_avg, slice_avg;
+	unsigned long long timestamp, last_ran, last_slice;
 	unsigned long long sched_time; /* sched_clock time spent running */
 	int activated;
 
--- linux-2.6.15/kernel/sched.c.org	Sat Jan  7 16:22:13 2006
+++ linux-2.6.15/kernel/sched.c	Mon Jan  9 11:50:40 2006
@@ -47,6 +47,7 @@
 #include <linux/syscalls.h>
 #include <linux/times.h>
 #include <linux/acct.h>
+#include <linux/jiffies.h>
 #include <asm/tlb.h>
 
 #include <asm/unistd.h>
@@ -1353,7 +1354,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
@@ -1492,6 +1493,8 @@
 	 */
 	p->sleep_avg = JIFFIES_TO_NS(CURRENT_BONUS(p) *
 		CHILD_PENALTY / 100 * MAX_SLEEP_AVG / MAX_BONUS);
+	p->slice_avg = NS_MAX_SLEEP_AVG;
+	p->last_slice = sched_clock();
 
 	p->prio = effective_prio(p);
 
@@ -2646,6 +2649,12 @@
 	runqueue_t *rq = this_rq();
 	task_t *p = current;
 	unsigned long long now = sched_clock();
+#if 1
+	static unsigned long printme = 0;
+
+	if (unlikely(!printme))
+		printme = jiffies;
+#endif
 
 	update_cpu_clock(p, rq, now);
 
@@ -2679,6 +2688,7 @@
 		if ((p->policy == SCHED_RR) && !--p->time_slice) {
 			p->time_slice = task_timeslice(p);
 			p->first_time_slice = 0;
+			p->last_slice = now;
 			set_tsk_need_resched(p);
 
 			/* put it at the end of the queue: */
@@ -2687,12 +2697,40 @@
 		goto out_unlock;
 	}
 	if (!--p->time_slice) {
+		unsigned long long nsecs = now - p->last_slice;
+		unsigned long idle, ticks;
+		int w = 10;
+
 		dequeue_task(p, rq->active);
 		set_tsk_need_resched(p);
 		p->prio = effective_prio(p);
 		p->time_slice = task_timeslice(p);
 		p->first_time_slice = 0;
 
+		if (nsecs > ~0UL)
+			nsecs = ~0UL;
+		ticks = NS_TO_JIFFIES((unsigned long) nsecs);
+		if (ticks < p->time_slice)
+			ticks = p->time_slice;
+		idle = 100 - (100 * p->time_slice / ticks);
+		p->slice_avg /= NS_MAX_SLEEP_AVG / 100;
+		/*
+		 * If we're improving our behaviour, speed up the improvement's
+		 * effect so we don't over throttle.
+		 */
+		if (idle > p->slice_avg + 10)
+			w -= (100 * p->slice_avg / idle) / 10;
+		p->slice_avg = (w * p->slice_avg + idle) / (w + 1);
+		p->slice_avg *= NS_MAX_SLEEP_AVG / 100;
+		p->last_slice = now;
+#if 1
+		if (p->mm && time_after(jiffies, printme + HZ)) {
+			printk(KERN_DEBUG"%s pid:%d sle:%ld sli:%ld tic:%ld idle:%ld w:%d\n",
+				p->comm,p->pid,p->sleep_avg,p->slice_avg,ticks,idle,w);
+			printme =  jiffies + HZ;
+	}
+#endif
+
 		if (!rq->expired_timestamp)
 			rq->expired_timestamp = jiffies;
 		if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) {
@@ -3010,7 +3048,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);
 		}
@@ -3095,6 +3133,13 @@
 	prev->sleep_avg -= run_time;
 	if ((long)prev->sleep_avg <= 0)
 		prev->sleep_avg = 0;
+	if (prev->state & (TASK_INTERRUPTIBLE|TASK_UNINTERRUPTIBLE) &&
+			prev->sleep_avg > prev->slice_avg + (NS_MAX_SLEEP_AVG/10) &&
+			!rt_task(prev))
+		prev->state |= TASK_NONINTERACTIVE;
+	if (!rt_task(next) && !(next->time_slice % DEF_TIMESLICE))
+		next->last_slice = now;
+
 	prev->timestamp = prev->last_ran = now;
 
 	sched_info_switch(prev, next);

[-- Attachment #3: irman2.c --]
[-- Type: text/plain, Size: 4107 bytes --]

/*
 *  irman by Davide Libenzi ( irman load generator )
 *  Copyright (C) 2003  Davide Libenzi
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 *  Davide Libenzi <davidel@xmailserver.org>
 *
 */

#include <sys/types.h>
#include <sys/stat.h>
#include <sys/time.h>
#include <sys/socket.h>
#include <sys/signal.h>
#include <sys/resource.h>
#include <fcntl.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>


#define BUFSIZE (1024 * 32)


static int *pipes, *child;
static int num_pipes, num_active, num_child;
static unsigned long burn_ms;
static char buf1[BUFSIZE], buf2[BUFSIZE];
static volatile sig_atomic_t run = 1;
pid_t parent;

static void signal_all(int signum) {
	if (getpid() == parent) {
		while (num_child >= 0) {
			kill(child[num_child], SIGKILL);
			num_child--;
		}
		exit(0);
	} else if (signum == SIGKILL || getppid() == 1)
		run = 0;
}

unsigned long long getustime(void) {
	struct timeval tm;

	gettimeofday(&tm, NULL);
	return (unsigned long long) tm.tv_sec * 1000ULL + (unsigned long long) tm.tv_usec / 1000ULL;
}


int burn_ms_cpu(unsigned long ms) {
	int i, cmp = 0;
	unsigned long long ts;

	ts = getustime();
	do {
		for (i = 0; i < 4; i++)
			cmp += memcmp(buf1, buf2, BUFSIZE);
	} while (ts + ms > getustime());
	return cmp;
}


pid_t hog_process(void) {
	pid_t pid;

	if (!(pid = fork())) {
		while (run) {
			printf("HOG running %u\n", time(NULL));
			burn_ms_cpu(burn_ms);
		}
		exit(0);
	}
	return pid;
}


pid_t irman_process(int n) {
	int nn;
	pid_t pid;
	u_char ch;

	if (!(pid = fork())) {
		if ((nn = n + num_active) >= num_pipes)
			nn -= num_pipes;
		while (run) {
			printf("reading %u\n", n);
			read(pipes[2 * n], &ch, 1);
			burn_ms_cpu(burn_ms);
			printf("writing %u\n", nn);
			write(pipes[2 * nn + 1], "s", 1);
		}
		exit(0);
	}
	return pid;
}

int main (int argc, char **argv) {
	struct rlimit rl;
	int i, c;
	long work;
	int *cp, run_secs = 0;
	extern char *optarg;
	struct sigaction action;

	parent = getpid();
	num_pipes = 40;
	num_active = 1;
	burn_ms = 300;
	while ((c = getopt(argc, argv, "n:b:a:s:")) != -1) {
		switch (c) {
		case 'n':
			num_pipes = atoi(optarg);
			break;
		case 'b':
			burn_ms = atoi(optarg);
			break;
		case 'a':
			num_active = atoi(optarg);
			break;
		case 's':
			run_secs = 1 + atoi(optarg);
			break;
		default:
			fprintf(stderr, "Illegal argument \"%c\"\n", c);
			exit(1);
		}
	}

	rl.rlim_cur = rl.rlim_max = num_pipes * 2 + 50;
	if (setrlimit(RLIMIT_NOFILE, &rl) == -1) {
		perror("setrlimit"); 
		exit(1);
	}

	pipes = calloc(num_pipes * 2, sizeof(int));
	if (pipes == NULL) {
		perror("malloc");
		exit(1);
	}

	child = calloc(num_pipes, sizeof(int));
	if (child == NULL) {
		perror("malloc");
		exit(1);
	}

	for (cp = pipes, i = 0; i < num_pipes; i++, cp += 2) {
		if (pipe(cp) == -1) {
			perror("pipe");
			exit(1);
		}
	}

	memset(buf1, 'f', sizeof(buf1));
	memset(buf2, 'f', sizeof(buf2));

	sigemptyset(&action.sa_mask);
	/* establish termination handler */
	action.sa_handler = signal_all;
	action.sa_flags = SA_NODEFER;
	if (sigaction(SIGTERM, &action, NULL) == -1) {
		perror("Could not install signal handler");
		exit(1);
	}

	for (i = 0; i < num_pipes; i++)
		child[i] = irman_process(i);

	child[i] = hog_process();
	num_child = i;

	for (i = 0; i < num_active; i++)
		write(pipes[2 * i + 1], "s", 1);

	while (--run_secs)
		sleep(1);
	signal_all(SIGKILL);
	exit(0);
}


[-- Attachment #4: thud.c --]
[-- Type: text/plain, Size: 1279 bytes --]

/* thud.c */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/time.h>
#include <time.h>
#include <sched.h>

/* These are used as strings so that strcmp can be used as a delay loop */
char *s1, *s2;

/* 20000 is fine on my 333MHz Celeron. Adjust so that system time is not
   excessive */
#define DELAY 20000

void busy_wait(long sec, long usec)
{
  struct timeval tv;
  long long end_usec;
  gettimeofday(&tv,0);
  end_usec=(long long)(sec+tv.tv_sec)*1000000 + tv.tv_usec+usec;
  while (((long long)tv.tv_sec*1000000 + tv.tv_usec) < end_usec)
  {
    gettimeofday(&tv,0);
#if 1 /* MIKEDIDIT */
    strcmp(s1,s2); /* yuck */
#else
    sched_yield();
#endif
  }
}

int main(int argc, char**argv)
{
  struct timespec st={10,50000000};
  int n=DELAY;
  int parent=1;

  if (argc<2) {fprintf(stderr,"Syntax: thud <children>\n"); return 0; }

  s1=malloc(n);
  s2=malloc(n);
  memset(s1,33,n);
  memset(s2,33,n);
  s1[n-1]=0;
  s2[n-1]=0;

  n=atoi(argv[1]);
  fprintf(stderr,"starting %d children\n",n);
  for (; n>0; n--)
    if (fork()==0) { sched_yield(); parent=0; break; }
  while (1)
  {
    nanosleep(&st, 0);
    if (parent) printf("running...");
    if (parent) fflush(stdout);
    busy_wait(6,0);
    if (parent) printf("done\n");
  }
  return 0;
}