fairsched-A5 for 2.5.66

This patch is a forward port of the fairsched-2.4.19 patch by Rik van Riel, which ensures all competing users get an equal share of cpu time.

Since the earlier patch applied to the classic O(n) process scheduler, and this one applies to the standard 2.5 O(1) one, the mapping isn't one-to-one but rather more complex.

The news:

Original 2.4.19 version:       Rik van Riel, [email protected]
Forward ported 2.5.66 version: Antonio Vargas, [email protected]

A0: initial layout for code and data

A1: introduce runqueue handling related to per-user cpu share

A2: add proper locking and O(1) behaviour

A3: perform all work with a kernel thread

A4: introduced a new priority array to park pending tasks,
works when running in debug mode using printk

A5: A4 never worked when using printk. It works for user==root,
but fails when we introduce any other user in the system. Added lotsa printk to trace the thing, but I don't know why it fails or how to make it work. HELP!!!

I've put it up on this URL:

http://www.cocodriloo.com/~wind/fairsched/index.html

Hope a more scheduler-related experienced kernel hacker can help me on this issue.

Greets, Antonio.

This patch is a forward port of the fairsched-2.4.19 patch by Rik van Riel, which ensures all competing users get an equal share of cpu time.

Since the earlier patch applied to the classic O(n) process scheduler, and this one applies to the standard 2.5 O(1) one, the mapping isn't one-to-one but rather more complex.

Original 2.4.19 version:       Rik van Riel, [email protected]
Forward ported 2.5.66 version: Antonio Vargas, [email protected]

A0: initial layout for code and data

A1: introduce runqueue handling related to per-user cpu share

A2: add proper locking and O(1) behaviour

A3: perform all work with a kernel thread

A4: introduced a new priority array to park pending tasks,
works when running in debug mode using printk

A5: A4 never worked when using printk. It works for user==root,
but fails when we introduce any other user in the system. Added lotsa printk to trace the thing, but I don't know why it fails or how to make it work. HELP!!!

 include/linux/init_task.h |    2 
 include/linux/sched.h     |   14 ++
 include/linux/sysctl.h    |    1 
 kernel/fork.c             |    1 
 kernel/sched.c            |  120 +++++++++++++++++++-
 kernel/sysctl.c           |    3 
 kernel/user.c             |  265 +++++++++++++++++++++++++++++++++++++++++++++-
 7 files changed, 397 insertions(+), 9 deletions(-)

diff -puN include/linux/init_task.h~fairsched-A5 include/linux/init_task.h
@@ -73,6 +73,8 @@
 	.active_mm	= &init_mm,					\
 	.run_list	= LIST_HEAD_INIT(tsk.run_list),			\
 	.time_slice	= HZ,						\
+	.reserved_time_slice	= HZ,					\
+	.user_tasks	= LIST_HEAD_INIT(tsk.user_tasks),		\
 	.tasks		= LIST_HEAD_INIT(tsk.tasks),			\
 	.ptrace_children= LIST_HEAD_INIT(tsk.ptrace_children),		\
 	.ptrace_list	= LIST_HEAD_INIT(tsk.ptrace_list),		\

diff -puN include/linux/sched.h~fairsched-A5 include/linux/sched.h
@@ -280,6 +280,16 @@ struct user_struct {
 	/* Hash table maintenance information */
 	struct list_head uidhash_list;
 	uid_t uid;
+
+	/* User list */
+	struct list_head user_list;
+
+	/* Task list for this user, and protecting spinlock */
+	struct list_head task_list;
+	spinlock_t task_list_lock;
+
+	/* Per-user timeslice management */
+	unsigned int time_slice;
 };
 
 #define get_current_user() ({ 				\

@@ -333,7 +343,11 @@ struct task_struct {
 	unsigned long policy;
 	unsigned long cpus_allowed;
 	unsigned int time_slice, first_time_slice;
+	unsigned int reserved_time_slice;
+
+	struct work_struct work_to_user;
 
+	struct list_head user_tasks;
 	struct list_head tasks;
 	struct list_head ptrace_children;
 	struct list_head ptrace_list;

diff -puN include/linux/sysctl.h~fairsched-A5 include/linux/sysctl.h
@@ -129,6 +129,7 @@ enum
 	KERN_CADPID=54,		/* int: PID of the process to notify on CAD */
 	KERN_PIDMAX=55,		/* int: PID # limit */
   	KERN_CORE_PATTERN=56,	/* string: pattern for core-file names */
+	KERN_FAIRSCHED=57,	/* switch per-user fair cpu scheduler*/
 };
 
 

diff -puN kernel/fork.c~fairsched-A5 kernel/fork.c
@@ -917,6 +917,7 @@ static struct task_struct *copy_process(
 	 * the parent if the child exits early enough.
 	 */
 	p->first_time_slice = 1;
+	p->reserved_time_slice = 0;
 	current->time_slice >>= 1;
 	p->last_run = jiffies;
 	if (!current->time_slice) {

diff -puN kernel/sysctl.c~fairsched-A5 kernel/sysctl.c
@@ -57,6 +57,7 @@ extern char core_pattern[];
 extern int cad_pid;
 extern int pid_max;
 extern int sysctl_lower_zone_protection;
+extern int fairsched;
 
 /* this is needed for the proc_dointvec_minmax for [fs_]overflow UID and GID */
 static int maxolduid = 65535;

@@ -263,6 +264,8 @@ static ctl_table kern_table[] = {
 #endif
 	{KERN_PIDMAX, "pid_max", &pid_max, sizeof (int),
 	 0600, NULL, &proc_dointvec},
+	{KERN_FAIRSCHED, "fairsched", &fairsched, sizeof (int),
+	 0644, NULL, &proc_dointvec},
 	{0}
 };
 

_

Script started on Mon Apr 14 18:21:05 2003 ]0;[email protected]: /home/wind/src/kernel/compilecompile$ uml-run

core file size        (blocks, -c) 4096
data seg size         (kbytes, -d) unlimited
file size             (blocks, -f) unlimited
max locked memory     (kbytes, -l) unlimited
max memory size       (kbytes, -m) unlimited

open files (-n) 1024
pipe size (512 bytes, -p) 8
stack size (kbytes, -s) 8192
cpu time (seconds, -t) unlimited
max user processes (-u) 1023
virtual memory (kbytes, -v) unlimited
Checking for the skas3 patch in the host...found
Checking for /proc/mm...found
Linux version 2.5.66-1um ([email protected]) (gcc version 2.95.4 20011002 (Debian prerelease)) #17 SMP Mon Apr 14 17:48:16 CEST 2003 On node 0 totalpages: 8192
DMA zone: 8192 pages, LIFO batch:2
Normal zone: 0 pages, LIFO batch:1
HighMem zone: 0 pages, LIFO batch:1
Building zonelist for node : 0
Kernel command line: root=/dev/ubd0 ubd0=../root init=/init.sh
PID hash table entries: 16 (order 4: 128 bytes)
Calibrating delay loop... 792.99 BogoMIPS
Memory: 29800k available
Dentry cache hash table entries: 4096 (order: 2, 16384 bytes)
Inode-cache hash table entries: 4096 (order: 2, 16384 bytes)
Mount-cache hash table entries: 512 (order: 0, 4096 bytes)
-> /dev
-> /dev/console
-> /root
Checking for host processor cmov support...No
Checking for host processor xmm support...No
Checking that ptrace can change system call numbers...OK
Checking that host ptys support output SIGIO...Yes
Checking that host ptys support SIGIO on close...No, enabling workaround
POSIX conformance testing by UNIFIX
os_set_fd_async : Failed to fcntl F_SETOWN (or F_SETSIG) fd 4 to pid -1577223120, errno = 1
Starting migration thread for cpu 0
G10: perhaps lock uidhash
G10: perhaps lock uidhash
CPUS done 32
Linux NoNET1.0 for Linux 2.6
B10: before lock rq a0170b20
B20: lock rq a0170b20
B30: unlock rq a0170b20
G10: perhaps lock uidhash
BIO: pool of 256 setup, 14Kb (56 bytes/bio)

biovec pool[0]:   1 bvecs:  56 entries (12 bytes)
biovec pool[1]:   4 bvecs:  28 entries (48 bytes)
biovec pool[2]:  16 bvecs:  14 entries (192 bytes)
biovec pool[3]:  64 bvecs:   7 entries (768 bytes)
biovec pool[4]: 128 bvecs:   3 entries (1536 bytes)
biovec pool[5]: 256 bvecs:   1 entries (3072 bytes)

block request queues:
4/16384 requests per read queue
4/16384 requests per write queue
enter congestion at 2047
exit congestion at 2049
mconsole (version 2) initialized on /home/wind/.uml/sAhrcA/mconsole Initializing stdio console driver
B10: before lock rq a0170b20
B20: lock rq a0170b20
B30: unlock rq a0170b20
G10: perhaps lock uidhash
G10: perhaps lock uidhash
G10: perhaps lock uidhash
G10: perhaps lock uidhash
G10: perhaps lock uidhash
RAMDISK driver initialized: 16 RAM disks of 4096K size 1024 blocksize
blk_init_queue: queue a024c500 inited
ubd0: unknown partition table
VFS: Mounted root (ext2 filesystem) readonly.
B10: before lock rq a0170b20
B20: lock rq a0170b20
B30: unlock rq a0170b20
B10: before lock rq a0170b20
B20: lock rq a0170b20
B30: unlock rq a0170b20
EXT2-fs warning: mounting unchecked fs, running e2fsck is recommended
B10: before lock rq a0170b20
B20: lock rq a0170b20
B30: unlock rq a0170b20
B10: before lock rq a0170b20
B20: lock rq a0170b20
B30: unlock rq a0170b20
B10: before lock rq a0170b20
B20: lock rq a0170b20
B30: unlock rq a0170b20

root@(none):/# su user1
B10: before lock rq a0170b20
B20: lock rq a0170b20
B30: unlock rq a0170b20
su[15]: + console root-user1

PAM_unix[15]: (su) session opened for user user1 by (uid=0)
F10: lock uidhash
F20: unlock uidhash
F25: new user 1001
F30: lock uidhash
F40: unlock uidhash
G10: perhaps lock uidhash
B10: before lock rq a0170b20
B20: lock rq a0170b20
B30: unlock rq a0170b20
B40: send_task_to_user a02e9814
B50: send_task_to_user a02e9814 done
D10: send_task_to_user a02e9814 enter
D20: before lock uidhash
D30: lock uidhash
D40: inc user 1001
D50: unlock uidhash
D60: before lock task_list 1001
D70: lock task_list 1001
D80: unlock task_list 1001
D90: dec user 1001

Kernel panic: Segfault with no mm

]0;[email protected]: /home/wind/src/kernel/compilecompile$ exit

Script done on Mon Apr 14 18:21:31 2003