Patchwork [RFC,01/12] coroutine: Add gtk-vnc coroutines library

login
register
mail settings
Submitter Stefan Hajnoczi
Date Jan. 22, 2011, 9:29 a.m.
Message ID <1295688567-25496-2-git-send-email-stefanha@linux.vnet.ibm.com>
Download mbox | patch
Permalink /patch/79989/
State New
Headers show

Comments

Stefan Hajnoczi - Jan. 22, 2011, 9:29 a.m.
Asynchronous image format code is becoming very complex.  Let's try
using coroutines to write sequential code without callbacks but use
coroutines to switch stacks under the hood.

Signed-off-by: Stefan Hajnoczi <stefanha@linux.vnet.ibm.com>
---
 Makefile.objs        |    2 +-
 continuation.c       |   87 +++++++++++++++++++++++++++++++++
 continuation.h       |   58 ++++++++++++++++++++++
 coroutine.h          |   72 +++++++++++++++++++++++++++
 coroutine_ucontext.c |  131 ++++++++++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 349 insertions(+), 1 deletions(-)
 create mode 100644 continuation.c
 create mode 100644 continuation.h
 create mode 100644 coroutine.h
 create mode 100644 coroutine_ucontext.c
Avi Kivity - Jan. 26, 2011, 3:25 p.m.
On 01/22/2011 11:29 AM, Stefan Hajnoczi wrote:
> Asynchronous image format code is becoming very complex.  Let's try
> using coroutines to write sequential code without callbacks but use
> coroutines to switch stacks under the hood.
>
>
> +
> +int cc_swap(struct continuation *from, struct continuation *to)
> +{
> +	to->exited = 0;
> +	if (getcontext(&to->last) == -1)
> +		return -1;
> +	else if (to->exited == 0)
> +		to->exited = 1;
> +	else if (to->exited == 1)
> +		return 1;
> +
> +	return swapcontext(&from->uc,&to->uc);
> +}

swapcontext() is very slow, involving the fpu and a syscall.

A nice trick I've used in the past is to use getcontext/makecontext for 
the initial setup and setjmp/longjmp for switching.  Of course this can 
be done later, as an optimization.
Anthony Liguori - Jan. 26, 2011, 4 p.m.
On 01/26/2011 09:25 AM, Avi Kivity wrote:
> On 01/22/2011 11:29 AM, Stefan Hajnoczi wrote:
>> Asynchronous image format code is becoming very complex.  Let's try
>> using coroutines to write sequential code without callbacks but use
>> coroutines to switch stacks under the hood.
>>
>>
>> +
>> +int cc_swap(struct continuation *from, struct continuation *to)
>> +{
>> +    to->exited = 0;
>> +    if (getcontext(&to->last) == -1)
>> +        return -1;
>> +    else if (to->exited == 0)
>> +        to->exited = 1;
>> +    else if (to->exited == 1)
>> +        return 1;
>> +
>> +    return swapcontext(&from->uc,&to->uc);
>> +}
>
> swapcontext() is very slow, involving the fpu and a syscall.
>
> A nice trick I've used in the past is to use getcontext/makecontext 
> for the initial setup and setjmp/longjmp for switching.  Of course 
> this can be done later, as an optimization.

Yeah, there are further optimizations that can be had but really, it's 
not important here.  In fact, I'd rather start with the threaded version 
just because it's far more portable than ucontext.

Regards,

Anthony Liguori
Avi Kivity - Jan. 26, 2011, 4:13 p.m.
On 01/26/2011 06:00 PM, Anthony Liguori wrote:
> On 01/26/2011 09:25 AM, Avi Kivity wrote:
>> On 01/22/2011 11:29 AM, Stefan Hajnoczi wrote:
>>> Asynchronous image format code is becoming very complex.  Let's try
>>> using coroutines to write sequential code without callbacks but use
>>> coroutines to switch stacks under the hood.
>>>
>>>
>>> +
>>> +int cc_swap(struct continuation *from, struct continuation *to)
>>> +{
>>> +    to->exited = 0;
>>> +    if (getcontext(&to->last) == -1)
>>> +        return -1;
>>> +    else if (to->exited == 0)
>>> +        to->exited = 1;
>>> +    else if (to->exited == 1)
>>> +        return 1;
>>> +
>>> +    return swapcontext(&from->uc,&to->uc);
>>> +}
>>
>> swapcontext() is very slow, involving the fpu and a syscall.
>>
>> A nice trick I've used in the past is to use getcontext/makecontext 
>> for the initial setup and setjmp/longjmp for switching.  Of course 
>> this can be done later, as an optimization.
>
> Yeah, there are further optimizations that can be had but really, it's 
> not important here.  In fact, I'd rather start with the threaded 
> version just because it's far more portable than ucontext.
>

What do you mean by threaded version?
Anthony Liguori - Jan. 26, 2011, 4:19 p.m.
On 01/26/2011 10:13 AM, Avi Kivity wrote:
> On 01/26/2011 06:00 PM, Anthony Liguori wrote:
>> On 01/26/2011 09:25 AM, Avi Kivity wrote:
>>> On 01/22/2011 11:29 AM, Stefan Hajnoczi wrote:
>>>> Asynchronous image format code is becoming very complex.  Let's try
>>>> using coroutines to write sequential code without callbacks but use
>>>> coroutines to switch stacks under the hood.
>>>>
>>>>
>>>> +
>>>> +int cc_swap(struct continuation *from, struct continuation *to)
>>>> +{
>>>> +    to->exited = 0;
>>>> +    if (getcontext(&to->last) == -1)
>>>> +        return -1;
>>>> +    else if (to->exited == 0)
>>>> +        to->exited = 1;
>>>> +    else if (to->exited == 1)
>>>> +        return 1;
>>>> +
>>>> +    return swapcontext(&from->uc,&to->uc);
>>>> +}
>>>
>>> swapcontext() is very slow, involving the fpu and a syscall.
>>>
>>> A nice trick I've used in the past is to use getcontext/makecontext 
>>> for the initial setup and setjmp/longjmp for switching.  Of course 
>>> this can be done later, as an optimization.
>>
>> Yeah, there are further optimizations that can be had but really, 
>> it's not important here.  In fact, I'd rather start with the threaded 
>> version just because it's far more portable than ucontext.
>>
>
> What do you mean by threaded version?

Stefan didn't post it, but the original code also has a GThread based 
implementation when ucontext isn't available (like on Windows).  It uses 
a mutex to control the execution of the coroutines.

Regards,

Anthony Liguori
Anthony Liguori - Jan. 26, 2011, 4:21 p.m.
On 01/26/2011 10:13 AM, Avi Kivity wrote:
> On 01/26/2011 06:00 PM, Anthony Liguori wrote:
>> On 01/26/2011 09:25 AM, Avi Kivity wrote:
>>> On 01/22/2011 11:29 AM, Stefan Hajnoczi wrote:
>>>> Asynchronous image format code is becoming very complex.  Let's try
>>>> using coroutines to write sequential code without callbacks but use
>>>> coroutines to switch stacks under the hood.
>>>>
>>>>
>>>> +
>>>> +int cc_swap(struct continuation *from, struct continuation *to)
>>>> +{
>>>> +    to->exited = 0;
>>>> +    if (getcontext(&to->last) == -1)
>>>> +        return -1;
>>>> +    else if (to->exited == 0)
>>>> +        to->exited = 1;
>>>> +    else if (to->exited == 1)
>>>> +        return 1;
>>>> +
>>>> +    return swapcontext(&from->uc,&to->uc);
>>>> +}
>>>
>>> swapcontext() is very slow, involving the fpu and a syscall.
>>>
>>> A nice trick I've used in the past is to use getcontext/makecontext 
>>> for the initial setup and setjmp/longjmp for switching.  Of course 
>>> this can be done later, as an optimization.
>>
>> Yeah, there are further optimizations that can be had but really, 
>> it's not important here.  In fact, I'd rather start with the threaded 
>> version just because it's far more portable than ucontext.
>>
>
> What do you mean by threaded version?

http://git.gnome.org/browse/gtk-vnc/tree/src/coroutine_gthread.c

Regards,

Anthony Liguori
Avi Kivity - Jan. 26, 2011, 4:22 p.m.
On 01/26/2011 06:19 PM, Anthony Liguori wrote:
>> What do you mean by threaded version?
>
>
> Stefan didn't post it, but the original code also has a GThread based 
> implementation when ucontext isn't available (like on Windows).  It 
> uses a mutex to control the execution of the coroutines.

Ah ok.  These can all be hidden under a single API.

btw, I think Windows does provide support for user-level threads under 
the name Fibers.
Anthony Liguori - Jan. 26, 2011, 4:29 p.m.
On 01/26/2011 10:22 AM, Avi Kivity wrote:
> On 01/26/2011 06:19 PM, Anthony Liguori wrote:
>>> What do you mean by threaded version?
>>
>>
>> Stefan didn't post it, but the original code also has a GThread based 
>> implementation when ucontext isn't available (like on Windows).  It 
>> uses a mutex to control the execution of the coroutines.
>
> Ah ok.  These can all be hidden under a single API.

It is, that's the point of the coroutine abstraction :-)


> btw, I think Windows does provide support for user-level threads under 
> the name Fibers.

Yes, I never got around to implementing it though.  There was something 
odd about them that I thought would be difficult to use but I can't 
remember the details.

Regards,

Anthony Liguori

Patch

diff --git a/Makefile.objs b/Makefile.objs
index c3e52c5..ae26396 100644
--- a/Makefile.objs
+++ b/Makefile.objs
@@ -15,7 +15,7 @@  oslib-obj-$(CONFIG_POSIX) += oslib-posix.o
 
 block-obj-y = cutils.o cache-utils.o qemu-malloc.o qemu-option.o module.o
 block-obj-y += nbd.o block.o aio.o aes.o qemu-config.o
-block-obj-$(CONFIG_POSIX) += posix-aio-compat.o
+block-obj-$(CONFIG_POSIX) += posix-aio-compat.o continuation.o coroutine_ucontext.o
 block-obj-$(CONFIG_LINUX_AIO) += linux-aio.o
 
 block-nested-y += raw.o cow.o qcow.o vdi.o vmdk.o cloop.o dmg.o bochs.o vpc.o vvfat.o
diff --git a/continuation.c b/continuation.c
new file mode 100644
index 0000000..f61aeb5
--- /dev/null
+++ b/continuation.c
@@ -0,0 +1,87 @@ 
+/*
+ * GTK VNC Widget
+ *
+ * Copyright (C) 2006  Anthony Liguori <anthony@codemonkey.ws>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.0 of the License, or (at your option) any later version.
+ *
+ * This library 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
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301 USA
+ */
+
+#include "continuation.h"
+
+/*
+ * va_args to makecontext() must be type 'int', so passing
+ * the pointer we need may require several int args. This
+ * union is a quick hack to let us do that
+ */
+union cc_arg {
+	void *p;
+	int i[2];
+};
+
+static void continuation_trampoline(int i0, int i1)
+{
+	union cc_arg arg;
+	struct continuation *cc;
+	arg.i[0] = i0;
+	arg.i[1] = i1;
+	cc = arg.p;
+
+	cc->entry(cc);
+}
+
+int cc_init(struct continuation *cc)
+{
+	volatile union cc_arg arg;
+	arg.p = cc;
+	if (getcontext(&cc->uc) == -1)
+		return -1;
+
+	cc->uc.uc_link = &cc->last;
+	cc->uc.uc_stack.ss_sp = cc->stack;
+	cc->uc.uc_stack.ss_size = cc->stack_size;
+	cc->uc.uc_stack.ss_flags = 0;
+
+	makecontext(&cc->uc, (void *)continuation_trampoline, 2, arg.i[0], arg.i[1]);
+
+	return 0;
+}
+
+int cc_release(struct continuation *cc)
+{
+	if (cc->release)
+		return cc->release(cc);
+
+	return 0;
+}
+
+int cc_swap(struct continuation *from, struct continuation *to)
+{
+	to->exited = 0;
+	if (getcontext(&to->last) == -1)
+		return -1;
+	else if (to->exited == 0)
+		to->exited = 1;
+	else if (to->exited == 1)
+		return 1;
+
+	return swapcontext(&from->uc, &to->uc);
+}
+/*
+ * Local variables:
+ *  c-indent-level: 8
+ *  c-basic-offset: 8
+ *  tab-width: 8
+ * End:
+ */
diff --git a/continuation.h b/continuation.h
new file mode 100644
index 0000000..585788e
--- /dev/null
+++ b/continuation.h
@@ -0,0 +1,58 @@ 
+/*
+ * GTK VNC Widget
+ *
+ * Copyright (C) 2006  Anthony Liguori <anthony@codemonkey.ws>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.0 of the License, or (at your option) any later version.
+ *
+ * This library 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
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301 USA
+ */
+
+#ifndef _CONTINUATION_H_
+#define _CONTINUATION_H_
+
+#include <ucontext.h>
+
+struct continuation
+{
+	char *stack;
+	size_t stack_size;
+	void (*entry)(struct continuation *cc);
+	int (*release)(struct continuation *cc);
+
+	/* private */
+	ucontext_t uc;
+	ucontext_t last;
+	int exited;
+};
+
+int cc_init(struct continuation *cc);
+
+int cc_release(struct continuation *cc);
+
+/* you can use an uninitialized struct continuation for from if you do not have
+   the current continuation handy. */
+int cc_swap(struct continuation *from, struct continuation *to);
+
+#define offset_of(type, member) ((unsigned long)(&((type *)0)->member))
+#define container_of(obj, type, member) \
+        (type *)(((char *)obj) - offset_of(type, member))
+
+#endif
+/*
+ * Local variables:
+ *  c-indent-level: 8
+ *  c-basic-offset: 8
+ *  tab-width: 8
+ * End:
+ */
diff --git a/coroutine.h b/coroutine.h
new file mode 100644
index 0000000..5316535
--- /dev/null
+++ b/coroutine.h
@@ -0,0 +1,72 @@ 
+/*
+ * GTK VNC Widget
+ *
+ * Copyright (C) 2006  Anthony Liguori <anthony@codemonkey.ws>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.0 of the License, or (at your option) any later version.
+ *
+ * This library 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
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301 USA
+ */
+
+#ifndef _COROUTINE_H_
+#define _COROUTINE_H_
+
+#define WITH_UCONTEXT 1
+
+#if WITH_UCONTEXT
+#include "continuation.h"
+#else
+#include <glib.h>
+#endif
+
+struct coroutine
+{
+	size_t stack_size;
+	void *(*entry)(void *);
+	int (*release)(struct coroutine *);
+
+	/* read-only */
+	int exited;
+
+	/* private */
+	struct coroutine *caller;
+	void *data;
+
+#if WITH_UCONTEXT
+	struct continuation cc;
+#else
+	GThread *thread;
+	gboolean runnable;
+#endif
+};
+
+int coroutine_init(struct coroutine *co);
+
+int coroutine_release(struct coroutine *co);
+
+void *coroutine_swap(struct coroutine *from, struct coroutine *to, void *arg);
+
+struct coroutine *coroutine_self(void);
+
+void *coroutine_yieldto(struct coroutine *to, void *arg);
+
+void *coroutine_yield(void *arg);
+
+#endif
+/*
+ * Local variables:
+ *  c-indent-level: 8
+ *  c-basic-offset: 8
+ *  tab-width: 8
+ * End:
+ */
diff --git a/coroutine_ucontext.c b/coroutine_ucontext.c
new file mode 100644
index 0000000..25e8687
--- /dev/null
+++ b/coroutine_ucontext.c
@@ -0,0 +1,131 @@ 
+/*
+ * GTK VNC Widget
+ *
+ * Copyright (C) 2006  Anthony Liguori <anthony@codemonkey.ws>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.0 of the License, or (at your option) any later version.
+ *
+ * This library 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
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301 USA
+ */
+
+#include <sys/types.h>
+#include <sys/mman.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include "coroutine.h"
+
+int coroutine_release(struct coroutine *co)
+{
+	return cc_release(&co->cc);
+}
+
+static int _coroutine_release(struct continuation *cc)
+{
+	struct coroutine *co = container_of(cc, struct coroutine, cc);
+
+	if (co->release) {
+		int ret = co->release(co);
+		if (ret < 0)
+			return ret;
+	}
+
+	co->caller = NULL;
+
+	return 0;
+}
+
+static void coroutine_trampoline(struct continuation *cc)
+{
+	struct coroutine *co = container_of(cc, struct coroutine, cc);
+	co->data = co->entry(co->data);
+}
+
+int coroutine_init(struct coroutine *co)
+{
+	if (co->stack_size == 0)
+		co->stack_size = 16 << 20;
+
+	co->cc.stack_size = co->stack_size;
+	co->cc.stack = mmap(0, co->stack_size,
+			    PROT_READ | PROT_WRITE,
+			    MAP_PRIVATE | MAP_ANONYMOUS,
+			    -1, 0);
+	if (co->cc.stack == MAP_FAILED)
+		return -1;
+	co->cc.entry = coroutine_trampoline;
+	co->cc.release = _coroutine_release;
+	co->exited = 0;
+
+	return cc_init(&co->cc);
+}
+
+#if 0
+static __thread struct coroutine leader;
+static __thread struct coroutine *current;
+#else
+static struct coroutine leader;
+static struct coroutine *current;
+#endif
+
+struct coroutine *coroutine_self(void)
+{
+	if (current == NULL)
+		current = &leader;
+	return current;
+}
+
+void *coroutine_swap(struct coroutine *from, struct coroutine *to, void *arg)
+{
+	int ret;
+	to->data = arg;
+	current = to;
+	ret = cc_swap(&from->cc, &to->cc);
+	if (ret == 0)
+		return from->data;
+	else if (ret == 1) {
+		coroutine_release(to);
+		current = &leader;
+		to->exited = 1;
+		return to->data;
+	}
+
+	return NULL;
+}
+
+void *coroutine_yieldto(struct coroutine *to, void *arg)
+{
+	if (to->caller) {
+		fprintf(stderr, "Co-routine is re-entering itself\n");
+		abort();
+	}
+	to->caller = coroutine_self();
+	return coroutine_swap(coroutine_self(), to, arg);
+}
+
+void *coroutine_yield(void *arg)
+{
+	struct coroutine *to = coroutine_self()->caller;
+	if (!to) {
+		fprintf(stderr, "Co-routine is yielding to no one\n");
+		abort();
+	}
+	coroutine_self()->caller = NULL;
+	return coroutine_swap(coroutine_self(), to, arg);
+}
+/*
+ * Local variables:
+ *  c-indent-level: 8
+ *  c-basic-offset: 8
+ *  tab-width: 8
+ * End:
+ */