cfq + io priorities

Hi,

I've implemented IO nice levels in the CFQ io scheduler. It works as follows.

A process has an assigned io nice level, anywhere from 0 to 20. Both of these end values are "special" - 0 means the process is only allowed to do io if the disk is idle, and 20 means the process io is considered realtime. Realtime IO always gets first access to the disk. Values from 1 to 19 assign 5-95% of disk bandwidth to that process. Any io class is allowed to use all of disk bandwidth in absence of higher priority io.

Idle and realtime IO settings work as expected, but not much tuning has gone into making sure that the individual levels in-between work 100% as expected. It should be good enough for some testing at least, even if it has some holes.

About the patch: stuff like this really needs some resource management abstraction like CKRM. Right now we just look at the tgid of the process. I've added two syscalls for setting and getting io priority. Don't consider this final or anything, it's just easy for testing. Patch has been tested on x86 and ppc, syscalls are also added for x86_64.

I'm attaching the simple ionice tool. It's used as follows:

# ionice -n20 bash

starts a bash shell with realtime io. Beware that io level is inherited on fork, so any program you start from this shell will also run with realtime io.

# ionice -n0 dbench 32

run some dbench thrasher, but only when disk is idle.

Pretty straight forward :-)

For really good results, you probably also want to set cpu nice level. Needless to say, a realtime io process can only submit io when it gets scheduled.

Default IO priority for a new process is 10.

Patch is against bk-current.

===== arch/i386/kernel/entry.S 1.69 vs edited =====

@@ -880,5 +880,7 @@
 	.long sys_utimes
  	.long sys_fadvise64_64
 	.long sys_ni_syscall	/* sys_vserver */
+	.long sys_ioprio_set
+	.long sys_ioprio_get
 
 nr_syscalls=(.-sys_call_table)/4

===== arch/ppc/kernel/misc.S 1.49 vs edited =====

@@ -1385,3 +1385,5 @@
 	.long sys_statfs64
 	.long sys_fstatfs64
 	.long ppc_fadvise64_64
+	.long sys_ioprio_set
+	.long sys_ioprio_get

===== drivers/block/Kconfig.iosched 1.2 vs edited =====

@@ -27,3 +27,11 @@
 	  a disk at any one time, its behaviour is almost identical to the
 	  anticipatory I/O scheduler and so is a good choice.
 
+config IOSCHED_CFQ
+	bool "CFQ I/O scheduler" if EMBEDDED
+	default y
+	---help---
+	  The CFQ I/O scheduler tries to distribute bandwidth equally
+	  among all processes in the system, with the option of assigning
+	  io priorities a process or process group. It should provide a fair
+	  working environment, suitable for desktop systems.

===== drivers/block/Makefile 1.22 vs edited =====

@@ -18,6 +18,7 @@
 obj-$(CONFIG_IOSCHED_NOOP)	+= noop-iosched.o
 obj-$(CONFIG_IOSCHED_AS)	+= as-iosched.o
 obj-$(CONFIG_IOSCHED_DEADLINE)	+= deadline-iosched.o
+obj-$(CONFIG_IOSCHED_CFQ)	+= cfq-iosched.o
 obj-$(CONFIG_MAC_FLOPPY)	+= swim3.o
 obj-$(CONFIG_BLK_DEV_FD)	+= floppy.o
 obj-$(CONFIG_BLK_DEV_FD98)	+= floppy98.o

===== drivers/block/elevator.c 1.52 vs edited =====

@@ -302,6 +302,14 @@
 		e->elevator_put_req_fn(q, rq);
 }
 
+void elv_set_congested(request_queue_t *q)
+{
+	elevator_t *e = &q->elevator;
+
+	if (e->elevator_set_congested_fn)
+		e->elevator_set_congested_fn(q);
+}
+
 int elv_may_queue(request_queue_t *q, int rw)
 {
 	elevator_t *e = &q->elevator;

@@ -309,7 +317,7 @@
 	if (e->elevator_may_queue_fn)
 		return e->elevator_may_queue_fn(q, rw);
 
-	return 0;
+	return 1;
 }
 
 void elv_completed_request(request_queue_t *q, struct request *rq)

===== drivers/block/ll_rw_blk.c 1.221 vs edited =====

===== include/asm-i386/unistd.h 1.30 vs edited =====

@@ -279,8 +279,10 @@
 #define __NR_utimes		271
 #define __NR_fadvise64_64	272
 #define __NR_vserver		273
+#define __NR_ioprio_set		274
+#define __NR_ioprio_get		275
 
-#define NR_syscalls 274
+#define NR_syscalls 276
 
 /* user-visible error numbers are in the range -1 - -124: see <asm-i386/errno.h> */
 

===== include/asm-ppc/unistd.h 1.26 vs edited =====

@@ -259,8 +259,10 @@
 #define __NR_statfs64		252
 #define __NR_fstatfs64		253
 #define __NR_fadvise64_64	254
+#define __NR_ioprio_set		255
+#define __NR_ioprio_get		256
 
-#define __NR_syscalls		255
+#define __NR_syscalls		257
 
 #define __NR(n)	#n
 

===== include/asm-x86_64/unistd.h 1.18 vs edited =====

@@ -532,8 +532,12 @@
 __SYSCALL(__NR_utimes, sys_utimes)
 #define __NR_vserver		236
 __SYSCALL(__NR_vserver, sys_ni_syscall)
+#define __NR_ioprio_set		237
+__SYSCALL(__NR_ioprio_set, sys_ioprio_set);
+#define __NR_ioprio_get		238
+__SYSCALL(__NR_ioprio_get, sys_ioprio_get);
 
-#define __NR_syscall_max __NR_vserver
+#define __NR_syscall_max __ioprio_get
 #ifndef __NO_STUBS
 
 /* user-visible error numbers are in the range -1 - -4095 */

===== include/linux/elevator.h 1.29 vs edited =====

@@ -17,6 +17,7 @@
 typedef struct request *(elevator_request_list_fn) (request_queue_t *, struct request *);
 typedef void (elevator_completed_req_fn) (request_queue_t *, struct request *);
 typedef int (elevator_may_queue_fn) (request_queue_t *, int);
+typedef void (elevator_set_congested_fn) (request_queue_t *);
 
 typedef int (elevator_set_req_fn) (request_queue_t *, struct request *, int);
 typedef void (elevator_put_req_fn) (request_queue_t *, struct request *);

@@ -45,6 +46,7 @@
 	elevator_put_req_fn *elevator_put_req_fn;
 
 	elevator_may_queue_fn *elevator_may_queue_fn;
+	elevator_set_congested_fn *elevator_set_congested_fn;
 
 	elevator_init_fn *elevator_init_fn;
 	elevator_exit_fn *elevator_exit_fn;

@@ -74,6 +76,7 @@
 extern int elv_register_queue(request_queue_t *q);
 extern void elv_unregister_queue(request_queue_t *q);
 extern int elv_may_queue(request_queue_t *, int);
+extern void elv_set_congested(request_queue_t *);
 extern void elv_completed_request(request_queue_t *, struct request *);
 extern int elv_set_request(request_queue_t *, struct request *, int);
 extern void elv_put_request(request_queue_t *, struct request *);

@@ -93,6 +96,11 @@
  * anticipatory I/O scheduler
  */
 extern elevator_t iosched_as;
+
+/*
+ * completely fair queueing I/O scheduler
+ */
+extern elevator_t iosched_cfq;
 
 extern int elevator_init(request_queue_t *, elevator_t *);
 extern void elevator_exit(request_queue_t *);

===== include/linux/fs.h 1.274 vs edited =====

@@ -1408,5 +1408,16 @@
 	return res;
 }
 
+/* io priorities */
+
+#define IOPRIO_NR      21
+
+#define IOPRIO_IDLE	0
+#define IOPRIO_NORM	10
+#define IOPRIO_RT	20
+
+asmlinkage int sys_ioprio_set(int ioprio);
+asmlinkage int sys_ioprio_get(void);
+
 #endif /* __KERNEL__ */
 #endif /* _LINUX_FS_H */

===== include/linux/init_task.h 1.27 vs edited =====

@@ -108,6 +108,7 @@
 	.proc_lock	= SPIN_LOCK_UNLOCKED,				\
 	.switch_lock	= SPIN_LOCK_UNLOCKED,				\
 	.journal_info	= NULL,						\
+	.ioprio		= IOPRIO_NORM,					\
 }
 
 

===== include/linux/sched.h 1.174 vs edited =====

@@ -462,6 +462,8 @@
 
 	struct io_context *io_context;
 
+	int ioprio;
+
 	unsigned long ptrace_message;
 	siginfo_t *last_siginfo; /* For ptrace use.  */
 };

===== kernel/fork.c 1.145 vs edited =====

@@ -1046,6 +1046,7 @@
 	} else
 		link_pid(p, p->pids + PIDTYPE_TGID, &p->group_leader->pids[PIDTYPE_TGID].pid);
 
+	p->ioprio = current->ioprio;
 	nr_threads++;
 	write_unlock_irq(&tasklist_lock);
 	retval = 0;

Jens Axboe

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <getopt.h>
#include <unistd.h>
#include <sys/ptrace.h>
#include <asm/unistd.h>

extern int sys_ioprio_set(int);
extern int sys_ioprio_get(void);

#if X86
#define __NR_ioprio_set 274
#define __NR_ioprio_get 275
#elif PPC
#define __NR_ioprio_set 255
#define __NR_ioprio_get 256
#elif X86-64
#define __NR_ioprio_set 237
#define __NR_ioprio_get 238
#else
#error unkown arch
#endif

_syscall1(int, ioprio_set, int, ioprio);
_syscall0(int, ioprio_get);

int main(int argc, char *argv[])

{
	int ioprio = 2, set = 0, set_pid = 0;
	pid_t pid;
	int c;

	while ((c = getopt(argc, argv, "+n:+p:")) != EOF) {
		switch (c) {
		case 'n':
			ioprio = strtol(optarg, NULL, 10);
			set = 1;
			break;
		case 'p':
			pid = strtoul(optarg, NULL, 10);
			set_pid = 1;
			break;
		}
	}

	if (!set)
		printf("%d\n", ioprio_get());
	else if (argv[optind]) {
		if (ioprio_set(ioprio) == -1) {
			perror("ioprio_set");
			return 1;
		}

		execvp(argv[optind], &argv[optind]);
	}
	return 0;
}

Here's one that works, sorry about that. To compile:

# gcc -Wall -D__X86 -o ionice ionice.c

or other define for PPC or X86_64.

Jens Axboe

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <getopt.h>
#include <unistd.h>
#include <sys/ptrace.h>
#include <asm/unistd.h>

extern int sys_ioprio_set(int);
extern int sys_ioprio_get(void);

#ifdef __X86
#define __NR_ioprio_set 274
#define __NR_ioprio_get 275
#endif

#ifdef __X86_64
#define __NR_ioprio_set 237
#define __NR_ioprio_get 238
#endif

#ifdef __PPC
#define __NR_ioprio_set 255
#define __NR_ioprio_get 256
#endif

#ifndef __NR_ioprio_set
#error set arch
#endif

_syscall1(int, ioprio_set, int, ioprio);
_syscall0(int, ioprio_get);

int main(int argc, char *argv[])

{
	int ioprio = 2, set = 0;
	int c;

	while ((c = getopt(argc, argv, "+n:")) != EOF) {
		switch (c) {
		case 'n':
			ioprio = strtol(optarg, NULL, 10);
			set = 1;
			break;
		}
	}

	if (!set)
		printf("%d\n", ioprio_get());
	else if (argv[optind]) {
		if (ioprio_set(ioprio) == -1) {
			perror("ioprio_set");
			return 1;
		}

		execvp(argv[optind], &argv[optind]);
	}
	return 0;
}

Hi,

And also a new cfq, of course a few embarassing bugs were introduced right before diffing...

I also forgot to include a small intro to the tunables that cfq-prio has, so I'll do that here too. You can find these in /sys/block/<disk>/queue/iosched.

quantum
A batch quantum, an io class is only allowed to submit as much as this number of io requests per turn. Default is 4.

idle_quantum
Like quantum, but for idle io. Default is 1.

queued
A process is able to submit at least this number of io requests, regardless. Default is 4.

grace_rt
The realtime grace period, in jiffies (I'll add user -> kernel conversions later, for now you need to know the clock rate of your arch. Disk is kept idle this long after realtime io completes, to allow more realtime io. Default is 10 ms.

grace_idle
Disk must have been idle for this long before idle io is allowed to be sent to disk. Default is 100ms.

Additionally, should any "normal" io be pending when realtime io is submitted, it's pulled off the dispatch list and put back into the io scheduler. Should any idle io be on the dispatch list when normal or rt io is submitted, that too is pulled back into the scheduler.

===== arch/i386/kernel/entry.S 1.69 vs edited =====

@@ -880,5 +880,7 @@
 	.long sys_utimes
  	.long sys_fadvise64_64
 	.long sys_ni_syscall	/* sys_vserver */
+	.long sys_ioprio_set
+	.long sys_ioprio_get
 
 nr_syscalls=(.-sys_call_table)/4

===== arch/ppc/kernel/misc.S 1.49 vs edited =====

@@ -1385,3 +1385,5 @@
 	.long sys_statfs64
 	.long sys_fstatfs64
 	.long ppc_fadvise64_64
+	.long sys_ioprio_set
+	.long sys_ioprio_get

===== drivers/block/Kconfig.iosched 1.2 vs edited =====

@@ -27,3 +27,11 @@
 	  a disk at any one time, its behaviour is almost identical to the
 	  anticipatory I/O scheduler and so is a good choice.
 
+config IOSCHED_CFQ
+	bool "CFQ I/O scheduler" if EMBEDDED
+	default y
+	---help---
+	  The CFQ I/O scheduler tries to distribute bandwidth equally
+	  among all processes in the system, with the option of assigning
+	  io priorities a process or process group. It should provide a fair
+	  working environment, suitable for desktop systems.

===== drivers/block/Makefile 1.22 vs edited =====

@@ -18,6 +18,7 @@
 obj-$(CONFIG_IOSCHED_NOOP)	+= noop-iosched.o
 obj-$(CONFIG_IOSCHED_AS)	+= as-iosched.o
 obj-$(CONFIG_IOSCHED_DEADLINE)	+= deadline-iosched.o
+obj-$(CONFIG_IOSCHED_CFQ)	+= cfq-iosched.o
 obj-$(CONFIG_MAC_FLOPPY)	+= swim3.o
 obj-$(CONFIG_BLK_DEV_FD)	+= floppy.o
 obj-$(CONFIG_BLK_DEV_FD98)	+= floppy98.o

===== drivers/block/elevator.c 1.52 vs edited =====

@@ -302,6 +302,14 @@
 		e->elevator_put_req_fn(q, rq);
 }
 
+void elv_set_congested(request_queue_t *q)
+{
+	elevator_t *e = &q->elevator;
+
+	if (e->elevator_set_congested_fn)
+		e->elevator_set_congested_fn(q);
+}
+
 int elv_may_queue(request_queue_t *q, int rw)
 {
 	elevator_t *e = &q->elevator;

@@ -309,7 +317,7 @@
 	if (e->elevator_may_queue_fn)
 		return e->elevator_may_queue_fn(q, rw);
 
-	return 0;
+	return 1;
 }
 
 void elv_completed_request(request_queue_t *q, struct request *rq)

===== drivers/block/ll_rw_blk.c 1.221 vs edited =====

===== include/asm-i386/unistd.h 1.30 vs edited =====

@@ -279,8 +279,10 @@
 #define __NR_utimes		271
 #define __NR_fadvise64_64	272
 #define __NR_vserver		273
+#define __NR_ioprio_set		274
+#define __NR_ioprio_get		275
 
-#define NR_syscalls 274
+#define NR_syscalls 276
 
 /* user-visible error numbers are in the range -1 - -124: see <asm-i386/errno.h> */
 

===== include/asm-ppc/unistd.h 1.26 vs edited =====

@@ -259,8 +259,10 @@
 #define __NR_statfs64		252
 #define __NR_fstatfs64		253
 #define __NR_fadvise64_64	254
+#define __NR_ioprio_set		255
+#define __NR_ioprio_get		256
 
-#define __NR_syscalls		255
+#define __NR_syscalls		257
 
 #define __NR(n)	#n
 

===== include/asm-x86_64/unistd.h 1.18 vs edited =====

@@ -532,8 +532,12 @@
 __SYSCALL(__NR_utimes, sys_utimes)
 #define __NR_vserver		236
 __SYSCALL(__NR_vserver, sys_ni_syscall)
+#define __NR_ioprio_set		237
+__SYSCALL(__NR_ioprio_set, sys_ioprio_set);
+#define __NR_ioprio_get		238
+__SYSCALL(__NR_ioprio_get, sys_ioprio_get);
 
-#define __NR_syscall_max __NR_vserver
+#define __NR_syscall_max __ioprio_get
 #ifndef __NO_STUBS
 
 /* user-visible error numbers are in the range -1 - -4095 */

===== include/linux/elevator.h 1.29 vs edited =====

@@ -17,6 +17,7 @@
 typedef struct request *(elevator_request_list_fn) (request_queue_t *, struct request *);
 typedef void (elevator_completed_req_fn) (request_queue_t *, struct request *);
 typedef int (elevator_may_queue_fn) (request_queue_t *, int);
+typedef void (elevator_set_congested_fn) (request_queue_t *);
 
 typedef int (elevator_set_req_fn) (request_queue_t *, struct request *, int);
 typedef void (elevator_put_req_fn) (request_queue_t *, struct request *);

@@ -45,6 +46,7 @@
 	elevator_put_req_fn *elevator_put_req_fn;
 
 	elevator_may_queue_fn *elevator_may_queue_fn;
+	elevator_set_congested_fn *elevator_set_congested_fn;
 
 	elevator_init_fn *elevator_init_fn;
 	elevator_exit_fn *elevator_exit_fn;

@@ -74,6 +76,7 @@
 extern int elv_register_queue(request_queue_t *q);
 extern void elv_unregister_queue(request_queue_t *q);
 extern int elv_may_queue(request_queue_t *, int);
+extern void elv_set_congested(request_queue_t *);
 extern void elv_completed_request(request_queue_t *, struct request *);
 extern int elv_set_request(request_queue_t *, struct request *, int);
 extern void elv_put_request(request_queue_t *, struct request *);

@@ -93,6 +96,11 @@
  * anticipatory I/O scheduler
  */
 extern elevator_t iosched_as;
+
+/*
+ * completely fair queueing I/O scheduler
+ */
+extern elevator_t iosched_cfq;
 
 extern int elevator_init(request_queue_t *, elevator_t *);
 extern void elevator_exit(request_queue_t *);

===== include/linux/fs.h 1.274 vs edited =====

@@ -1408,5 +1408,16 @@
 	return res;
 }
 
+/* io priorities */
+
+#define IOPRIO_NR      21
+
+#define IOPRIO_IDLE	0
+#define IOPRIO_NORM	10
+#define IOPRIO_RT	20
+
+asmlinkage int sys_ioprio_set(int ioprio);
+asmlinkage int sys_ioprio_get(void);
+
 #endif /* __KERNEL__ */
 #endif /* _LINUX_FS_H */

===== include/linux/init_task.h 1.27 vs edited =====

@@ -108,6 +108,7 @@
 	.proc_lock	= SPIN_LOCK_UNLOCKED,				\
 	.switch_lock	= SPIN_LOCK_UNLOCKED,				\
 	.journal_info	= NULL,						\
+	.ioprio		= IOPRIO_NORM,					\
 }
 
 

===== include/linux/sched.h 1.174 vs edited =====

@@ -462,6 +462,8 @@
 
 	struct io_context *io_context;
 
+	int ioprio;
+
 	unsigned long ptrace_message;
 	siginfo_t *last_siginfo; /* For ptrace use.  */
 };

===== kernel/fork.c 1.145 vs edited =====

@@ -1046,6 +1046,7 @@
 	} else
 		link_pid(p, p->pids + PIDTYPE_TGID, &p->group_leader->pids[PIDTYPE_TGID].pid);
 
+	p->ioprio = current->ioprio;
 	nr_threads++;
 	write_unlock_irq(&tasklist_lock);
 	retval = 0;

Jens Axboe

Thanks for putting this in ! It'll be very useful to have some control over I/O priorities.

Currently, cfq is doing bandwidth allocation in terms of number of requests, not bytes. Hence priority inversion can happen if lower priority levels submit larger requests on an average. Any plans to take request sizes into consideration in future ?

Of course, request sizes alone don't determine actual disk bandwidth consumed since their seek position also matters.

Now thats music to our ears :-) Though you've complicated matters by calling the priority level a "class" ! Please consider renaming class to something else (say priolevel ).

Thanks for separating the hashvalue as a macro. It should make it even easier to convert cfq to use a CKRM I/O classes ' priority rather than the submitting task's ioprio value.

-- Shailabh

Yes that needs to be taken into account as well. I'll get another version out soonish that works around that too.

Yeah that's where it gets tricky. It's basically impossible to get absolutely right, it will always be just guidelines. I don't want to over complicate matters.

Done.

Yup that was my intention, to make the transition as smooth as possible.

Jens Axboe

Thats true. Estimating bandwidth by quantity of submitted I/O should be good enough. Doing too many seek
time calculations is not only complex but may be useless if the attached device is doing its own reordering (an increasingly likely
scenario for servers). I guess one could do some simple accounting such as 1+x per request where 1 accounts for the fixed "cost" of a request on I/O bandwidth and x is a request size dependent cost. I'm looking forward to your next version to see what are your thoughts.

Thanks !

I'll try and get out a CKRM variant of CFQ soon - anyway another version is needed to fit into the next version of CKRM core api's that were published on ckrm-tech in the past week
http://sourceforge.net/mailarchive/forum.php?forum=ckrm-tech

Please consider joining the ckrm-tech mailing list (http://lists.sourceforge.net/lists/listinfo/ckrm-tech) and/or cc'ing it on CFQ changes for I/O priorities.

-- Shailabh