context-switching overhead in X, ioport(), 2.6.8.1

while debugging/improving scheduling latencies i got the following strange latency report from Lee Revell:

http://krustophenia.net/testresults.php?dataset=2.6.8.1-P6#/var/www/2.6.8.1-P6

this trace shows a 120 usec latency caused by XFree86, on a 600 MHz x86 system. Looking closer reveals:

00000002 0.006ms (+0.003ms): __switch_to (schedule) 00000002 0.088ms (+0.082ms): finish_task_switch (schedule)

it took more than 80 usecs for XFree86 to do a context-switch!

it turns out that the reason for this (massive) context-switching overhead is the following change in 2.6.8:

[PATCH] larger IO bitmaps

To demonstrate the effect of this change i've written ioperm-latency.c (attached), which gives the following on vanilla 2.6.8.1:

  # ./ioperm-latency
  default no ioperm:             scheduling latency: 2528 cycles
  turning on port 80 ioperm:     scheduling latency: 10563 cycles
  turning on port 65535 ioperm:  scheduling latency: 10517 cycles

the ChangeSet says:

Now, with the lazy bitmap allocation and per-CPU TSS, this will really not drain any resources I think.

this is plain wrong. An increase in the IO bitmap size introduces per-context-switch overhead as well: we now have to copy an 8K bitmap every time XFree86 context-switches - even though XFree86 never uses ports higher than 1024! I've straced XFree86 on a number of x86 systems and in every instance ioperm() was used - so i'd say the majority of x86 Linux systems running 2.6.8.1 are affected by this problem.

This not only causes lots of overhead, it also trashes ~16K out of the L1 and L2 caches, on every context-switch. It's as if XFree86 did a L1 cache flush on every context-switch ...

the simple solution would be to revert IO_BITMAP_BITS back to 1024 and release 2.6.8.2?

I've implemented another solution as well, which tracks the highest-enabled port # for every task and does the copying of the bitmap intelligently. (patch attached) The patched kernel gives:

  # ./ioperm-latency
  default no ioperm:             scheduling latency: 2423 cycles
  turning on port 80 ioperm:     scheduling latency: 2503 cycles
  turning on port 65535 ioperm:  scheduling latency: 10607 cycles

this is much more acceptable - the full overhead only occurs in the very unlikely event of a task using the high ioport range. X doesnt suffer any significant overhead.

(tracking the maximum allowed port # also allows a simplification of io_bitmap handling: e.g. we dont do the invalid-offset trick anymore - the IO bitmap in the TSS is always valid and secure.)

I tested the patch on x86 SMP and UP, it works fine for me. I tested boundary conditions as well, it all seems secure.

Ingo

#include <errno.h>
#include <stdio.h>
#include <sched.h>
#include <signal.h>
#include <sys/io.h>
#include <stdlib.h>
#include <unistd.h>
#include <linux/unistd.h>

#define CYCLES(x) asm volatile ("rdtsc" :"=a" (x)::"edx")

#define __NR_sched_set_affinity 241
_syscall3 (int, sched_set_affinity, pid_t, pid, unsigned int, mask_len, unsigned long *, mask)

/*
* Use a pair of RT processes bound to the same CPU to measure
* context-switch overhead:
*/
static void measure(void)

{
	unsigned long i, min = ~0UL, pid, mask = 1, t1, t2;

	sched_set_affinity(0, sizeof(mask), &mask);

	pid = fork();
	if (!pid)
		for (;;) {
			asm volatile ("sti; nop; cli");
			sched_yield();
		}

	sched_yield();
	for (i = 0; i < 100; i++) {
		asm volatile ("sti; nop; cli");
		CYCLES(t1);
		sched_yield();
		CYCLES(t2);
		if (i > 10) {
			if (t2 - t1 < min)
				min = t2 - t1;
		}
	}
	asm volatile ("sti");

	kill(pid, 9);
	printf("scheduling latency: %ld cycles\n", min);
	sched_yield();
}

int main(void)

{
	struct sched_param p = { sched_priority: 2 };
	unsigned long mask = 1;

	if (iopl(3)) {
		printf("need to run as root!\n");
		exit(-1);
	}
	sched_setscheduler(0, SCHED_FIFO, &p);
	sched_set_affinity(0, sizeof(mask), &mask);

	printf("default no ioperm:             ");
	measure();

	printf("turning on port 80 ioperm:     ");
	ioperm(0x80,1,1);
	measure();

	printf("turning on port 65535 ioperm:  ");
	if (ioperm(0xffff,1,1))
		printf("FAILED - older kernel.\n");
	else
		measure();

	return 0;
}

it taskes for X.org/XFree86 more than 80 usecs to do a context-switch!

it turns out that the reason for this (massive) context-switching overhead is the following change in 2.6.8:

[PATCH] larger IO bitmaps

the simple solution is to revert the change. I've implemented another solution as well, which tracks the highest-enabled port # for every task and does the copying of the bitmap intelligently. (patch attached) The patched kernel gives:

  # ./ioperm-latency
  default no ioperm:             scheduling latency: 2423 cycles
  turning on port 80 ioperm:     scheduling latency: 2503 cycles
  turning on port 65535 ioperm:  scheduling latency: 10607 cycles

this is much more acceptable - the full overhead only occurs in the very unlikely event of a task using the high ioport range.

tracking the maximum allowed port # also allows a simplification of io_bitmap handling: e.g. we dont do the invalid-offset trick anymore - the IO bitmap in the TSS is always valid and secure.

I tested the patch on x86 SMP and UP, it works fine for me. I tested boundary conditions as well, it all seems secure.

@@ -56,6 +56,7 @@ static void set_bitmap(unsigned long *bi
  */
 asmlinkage long sys_ioperm(unsigned long from, unsigned long num, int turn_on)
 {
+	unsigned int i, max_long, bytes, bytes_updated;
 	struct thread_struct * t = &current->thread;
 	struct tss_struct * tss;
 	unsigned long *bitmap;

@@ -81,16 +82,34 @@ asmlinkage long sys_ioperm(unsigned long
 
 	/*
 	 * do it in the per-thread copy and in the TSS ...
+	 *
+	 * Disable preemption via get_cpu() - we must not switch away
+	 * because the ->io_bitmap_max value must match the bitmap
+	 * contents:
 	 */
-	set_bitmap(t->io_bitmap_ptr, from, num, !turn_on);
 	tss = init_tss + get_cpu();
-	if (tss->io_bitmap_base == IO_BITMAP_OFFSET) { /* already active? */
-		set_bitmap(tss->io_bitmap, from, num, !turn_on);
-	} else {
-		memcpy(tss->io_bitmap, t->io_bitmap_ptr, IO_BITMAP_BYTES);
-		tss->io_bitmap_base = IO_BITMAP_OFFSET; /* Activate it in the TSS */
-	}
+
+	set_bitmap(t->io_bitmap_ptr, from, num, !turn_on);
+
+	/*
+	 * Search for a (possibly new) maximum. This is simple and stupid,
+	 * to keep it obviously correct:
+	 */
+	max_long = 0;
+	for (i = 0; i < IO_BITMAP_LONGS; i++)
+		if (t->io_bitmap_ptr[i] != ~0UL)
+			max_long = i;
+
+	bytes = (max_long + 1) * sizeof(long);
+	bytes_updated = max(bytes, t->io_bitmap_max);
+
+	t->io_bitmap_max = bytes;
+
+	/* Update the TSS: */
+	memcpy(tss->io_bitmap, t->io_bitmap_ptr, bytes_updated);
+
 	put_cpu();
+
 	return 0;
 }
 

@@ -422,6 +422,8 @@ struct thread_struct {
 	unsigned int		saved_fs, saved_gs;
 /* IO permissions */
 	unsigned long	*io_bitmap_ptr;
+/* max allowed port in the bitmap, in bytes: */
+	unsigned int	io_bitmap_max;
 };
 
 #define INIT_THREAD  {							\

@@ -442,7 +444,7 @@ struct thread_struct {
 	.esp1		= sizeof(init_tss[0]) + (long)&init_tss[0],	\
 	.ss1		= __KERNEL_CS,					\
 	.ldt		= GDT_ENTRY_LDT,				\
-	.io_bitmap_base	= INVALID_IO_BITMAP_OFFSET,			\
+	.io_bitmap_base	= offsetof(struct tss_struct,io_bitmap),	\
 	.io_bitmap	= { [ 0 ... IO_BITMAP_LONGS] = ~0 },		\
 }
 

FWIW, I would recommend a sparse bitmap implementation for the ioport stuff. Something simple like:

struct set_ent {
	u32 pos;
	u32 bits;
	struct set_ent *next;
};

static inline int is_set(struct set_ent *head, int pos)

{
	while (head != NULL) {
		if (pos >= head->pos) {
			if (pos < head->pos + 32) {
				if (head->bits &
				    (1 << (pos - head->pos)))
					return 1;
			}
			break;
		}

		head = head->next;
	}
	return 0;
}

You get the idea.

The problem is that the sparse bitmap would have to be unpacked to the "dense" bitmap that lives in the TSS on context switch. AFAICS, that would involve walking the previous task's spare bitmap, clearing all the ports it had access to, and then walking the next task's sparse bitmap and opening access to its ports. I doubt this would be a big win over what Ingo says usually reduces to a 128 byte or less memcpy(), especially when you consider the added complexity.

The only big speedup I can see is in the case of only one task having anything set in its IO bitmap at all. I assume that most desktops running a single X server fall in to this degenerate case, please correct me if I'm wrong. There we could simply set the TSS's io_bitmap_base to IO_BITMAP_OFFSET when switching to the IO bitmap'ed task, and set it back to INVALID_IO_BITMAP_OFFSET when we context switch away. That way the entire thing is accomplished with a single 4-byte store per context switch until a second IO bitmap'ed app is started, in which case we'd have to fall back to memcpy()ing. Seems like too much complexity for what amounts to a microoptimization, though.

BTW Ingo, have you looked at changing the almost identical code in arch/x86-64? Or did it not get its bitmap expanded?

-Ryan

Can someone supply a link to the original LKML post with the ioport change? I was not able to find it in my mailbox nor in the archives.

Lee

Here's what I could dig up:

ftp://ftp.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.7/2.6.7-mm2/broken-out/larger-io-bitmap.patch
http://www.uwsg.iu.edu/hypermail/linux/kernel/0211.0/0477.html
http://www.uwsg.iu.edu/hypermail/linux/kernel/9807.1/1079.html

Looks like x86-64 does in fact need a similar change to the x86 one. It's late here, but it should be pretty trivial to port over.

-Ryan