state-threads-devel — State Threads developers' list

[ST-devel] patch for st-1.5.0: st_recvmsg/st_sendmsg

[Claus A. <sta...@es...>]

For my project I need to transfer file descriptors between applications
and the example from Stevens book uses recvmsg()/sendmsg(), hence
I added those two function to statethreads. The patch is attached.
Would it make sense to add this to the distribution or is it just
overhead that other people don't need?

[ST-devel] ST 1.5.1

[Mike A. <mj...@co...>]

Experimental version 1.5.1 of the State Threads Library is now
available.  It fixes USE_POLL support and adds a user-defined high
resolution timer function.  See the included README file for details.

Download it from:  http://state-threads.sourceforge.net/

As always, your contributions and comments are welcome.
--
Mike Abbott    ma...@us...
State Threads Project co-administrator

[ST-devel] st-1.5.0 patch

[<ge...@co...>]

A small patch to add a new function allowing to replace the default
implementation of st_utime() with the user-provided one.
On Linux/FreeBSD/etc. st_utime() is implemented via gettimeofday()
(a syscall). Sometimes it's desirable to use hi-res time function
implemented more efficiently, e.g. by reading CPU cycle counter.
This patch adds ability to plug in user's implementation of st_utime().

[ST-devel] -DUSE_POLL fix

[<gs...@no...>]

Due to an oversight in the timer performance patch I submitted in
October, the timer code in st-1.5.0 does not compile when USE_POLL
is defined.  The enclosed patch will fix it.
-- 
Andreas Gustafsson, gs...@no...

--- st-1.5.0/sched.c.orig	2004-01-11 14:21:55.000000000 -0800
+++ st-1.5.0/sched.c	2004-04-22 18:25:49.000000000 -0700
@@ -477,10 +477,13 @@
   }
   ST_ASSERT(pollfds <= _ST_POLLFDS + _ST_POLLFDS_SIZE);
 
-  if (ST_CLIST_IS_EMPTY(&_ST_SLEEPQ)) {
+  if (_ST_SLEEPQ == NULL) {
     timeout = -1;
   } else {
-    min_timeout = (_ST_THREAD_PTR(_ST_SLEEPQ.next))->sleep;
+    if (_ST_SLEEPQ->due <= _st_this_vp.last_clock)
+      min_timeout = 0;
+    else
+      min_timeout = _ST_SLEEPQ->due - _st_this_vp.last_clock;
     timeout = (int) (min_timeout / 1000);
   }
 

[ST-devel] State Threads version 1.5.0

[Mike A. <mj...@co...>]

Experimental version 1.5.0 of the State Threads Library is now
available.  It supports more platforms, adds a DNS resolver extension,
and runs faster with many threads.  See the included README file for
details.

This version does not include the asked-for pthreads interoperability or
adequate documentation for the DNS resolver extension.  Maybe they'll be
in 1.5.1.

Download it from:  http://state-threads.sourceforge.net/

As always, your contributions and comments are welcome.
--
Mike Abbott    ma...@us...
State Threads Project co-administrator

[ST-devel] Re: Solaris 64bit mode patch

[Gene <ge...@co...>]

Claus Assmann wrote:

>PS: any comments about using makecontext()?
>Maybe, good idea, not worth it, ...?
>
Don't remember exactly original reasons for not using
makecontext().  Probably because it would require completely
different code path.  Another possible reason is to avoid
system calls on context switch (swap/makecontext() use system
calls, as far as I remember).

[ST-devel] Re: Solaris 64bit mode patch

[Claus A. <sta...@es...>]

On Mon, Dec 08, 2003, Gene wrote:
> Attached is a Solaris 64-bit patch.
> Changes are in "md.h", "Makefile", and "examples/Makefile".

Thanks, "works for me". I forwarded it to two people who encountered
the problem on their machines but haven't heard back yet.

PS: any comments about using makecontext()?
Maybe, good idea, not worth it, ...?

[ST-devel] Solaris 64bit mode patch

[Gene <ge...@co...>]

Attached is a Solaris 64-bit patch.
Changes are in "md.h", "Makefile", and "examples/Makefile".
There are two new build targets: "solaris-64-debug" and
"solaris-64-optimized".

Claus, please give it a try.

Thanks!

Re: [ST-devel] Solaris 64bit mode: crash in longjmp()

[Claus A. <sta...@es...>]

On Sun, Dec 07, 2003, Gene wrote:
> The fact is ST was never ported to 64-bit mode on Solaris.
> In 64-bit mode (LP64) jmp_buf structure is completely different,
> that's why you are getting crashes.

If the structure is different, wouldn't it be more portable to use
makecontext on SysV? I read a paper about GNU Pth where the different
context switching methods are explained and it preferred makecontext
if available (that's why I didn't find hints about a different
layout, I checked sizeof(jmp_buf) and in 64bit mode it was as
expected twice as big as in 32bit mode).

> Now, how do you compile 64-bit mode with gcc? Special compiler
> flags? Do you need special 64-bit gcc version? I have an access
> to Solaris 9 box on Sourceforge farm so I may try to port it
> if that box supports 64-bit mode:

gcc -m64
is all you need (AFAIK), for Sun's compiler its
cc -xarch=v9

Thanks!

Re: [ST-devel] Solaris 64bit mode: crash in longjmp()

[Gene <ge...@co...>]

The fact is ST was never ported to 64-bit mode on Solaris.
In 64-bit mode (LP64) jmp_buf structure is completely different,
that's why you are getting crashes.

Now, how do you compile 64-bit mode with gcc? Special compiler
flags? Do you need special 64-bit gcc version? I have an access
to Solaris 9 box on Sourceforge farm so I may try to port it
if that box supports 64-bit mode:

$ uname -a
SunOS sparc-solaris1 5.9 Generic_112233-03 sun4u sparc SUNW,Ultra-60
$ gcc --version
gcc (GCC) 3.3.1
Copyright (C) 2003 Free Software Foundation, Inc.


Claus Assmann wrote:

>[forwarded from st-users with more information]
>
>Has anyone succeeded compiling and using statethreads in 64bit mode
>on Solaris (8 or 9, using gcc or Sun's C compiler)?  A simple program
>crashes in longjmp():
>
>#0  0xffffffff7ec3b8e8 in longjmp () from /usr/lib/64/libc.so.1
>#1  0x00000001000035a0 in _st_vp_schedule () at sched.c:165
>#2  0x0000000100004e88 in st_usleep (usecs=4294987380) at sync.c:113
>#3  0x0000000100002b48 in main (argc=16777217, argv=0x100006e28) at thr-1.c:120
>
>The program creates one thread and calls st_usleep(timeout); where
>timeout is 1000, to force a context switch. Are there any required
>changes to the stack context switch code in md.h for this combination?
>
>I've tried to use setcontext() etc instead, but didn't get anywhere
>either, the way I used it is probably wrong:
>
>#define MD_SETJMP(env) getcontext(&(env))
>#define MD_LONGJMP(env, val) setcontext(&(env))
>
>_ST_INIT_CONTEXT:
>  if (getcontext(&(thread->context)) != 0)
>        return NULL;
>  (thread)->context.uc_link = NULL;
>  (thread)->context.uc_stack.ss_sp = (void *) (stack->sp);
>  (thread)->context.uc_stack.ss_size = stk_size;
>  (thread)->context.uc_stack.ss_flags = 0;
>  makecontext(&(thread)->context, _st_thread_main, 1);
>

[ST-devel] Solaris 64bit mode: crash in longjmp()

[Claus A. <sta...@es...>]

[forwarded from st-users with more information]

Has anyone succeeded compiling and using statethreads in 64bit mode
on Solaris (8 or 9, using gcc or Sun's C compiler)?  A simple program
crashes in longjmp():

#0  0xffffffff7ec3b8e8 in longjmp () from /usr/lib/64/libc.so.1
#1  0x00000001000035a0 in _st_vp_schedule () at sched.c:165
#2  0x0000000100004e88 in st_usleep (usecs=4294987380) at sync.c:113
#3  0x0000000100002b48 in main (argc=16777217, argv=0x100006e28) at thr-1.c:120

The program creates one thread and calls st_usleep(timeout); where
timeout is 1000, to force a context switch. Are there any required
changes to the stack context switch code in md.h for this combination?

I've tried to use setcontext() etc instead, but didn't get anywhere
either, the way I used it is probably wrong:

#define MD_SETJMP(env) getcontext(&(env))
#define MD_LONGJMP(env, val) setcontext(&(env))

_ST_INIT_CONTEXT:
  if (getcontext(&(thread->context)) != 0)
        return NULL;
  (thread)->context.uc_link = NULL;
  (thread)->context.uc_stack.ss_sp = (void *) (stack->sp);
  (thread)->context.uc_stack.ss_size = stk_size;
  (thread)->context.uc_stack.ss_flags = 0;
  makecontext(&(thread)->context, _st_thread_main, 1);

Re: [ST-devel] Library interoperability problem

[Wesley W. T. <we...@te...>]

On Tue, Nov 18, 2003 at 09:10:26PM -0800, Mike Abbott wrote:
> > Compatibility with libpthread.
> 
> Gene has volunteered to look into this again.  I'm hoping it's something
> simple like copying a magic value from the primordial stack into every
> state thread's stack at creation time, but Gene fears the worst.

He's right to fear the worst; they have a whole struct at the bottom of the
stack (pthread_descr).... and some of those fields have to be consistent with 
all the other state thread stacks, such as p_errno (by value, not pointer).

Ie: your solution is impossible.

I don't think that a pthread specific hack in libst will solve this.
Not to mention, this sort of coupling would make libst brittle.

My personal take on this is that library developers need an alternative.
Something like a 'meta-threading' library which provides mutexes.

When finally linked to a real thread-model, the stubbed methods become calls
to the real threading library. If there is no threading, they are no-ops.

I have a library which already tries to do this called libwthread (for weak
threads) which has the same ABI as pthreads for mutexes and conditions.
However, it is not finished, and I had hope that maybe people could come up
with a better idea. 

The idea was that people could just relink libraries against libwthread and
it would 'just work': noops without threads and do the right thing with
threads. As I wrote it I discovered how tied to pthreads ABI compatibility
would force it to become. Hence, I think another approach which is only API
compatible might be better.

eg: #define pthread_mutex_create wthread_mutex_create ...

-- 
Wesley W. Terpstra <we...@te...>

Re: [ST-devel] current status?

[Gene <ge...@co...>]

One possible explanation: server does active close so you may
run out of available ports on a client side.  The same client
port cannot be reused for 2MSL (30 seconds on Linux?).  Client
can't connect till ports become available, which can lead to
bursty behavior you observed.  Even with 65K ports, the max
sustained request rate from a single IP can't be more than
~2000 req/s (65K/30s).

>I'm currently knee deep in writing a couple of apps that make heavy use of state threads. I'm
>hitting some performance issues at high load. I can reproduce the problem by using the "server"
>example and writing a small app that connects to the "server" and hammers it as fast as it can. A
>little bit of timing shows that it can manage only around 7000 connections/second. Anything above
>that and the "server" seems to lock up for short periods, serving a few connections in spurts,
>then locking up, then serving a few more connections. The jerkiness is more prevalent when there
>are multiple processes hitting a single "server" process. Oh, this is on a P3 Linux 8 box. I'm
>just wondering if this is a queue size problem (although I've bumped it past 10000), an OS problem
>(FD_SETSIZE or somaxconn), or just something to do with state threads?
>

Re: [ST-devel] Library interoperability problem

[Mike A. <mj...@co...>]

> Compatibility with libpthread.

Gene has volunteered to look into this again.  I'm hoping it's something
simple like copying a magic value from the primordial stack into every
state thread's stack at creation time, but Gene fears the worst.
-- 
Mike Abbott    ma...@us...
State Threads Project co-administrator

[ST-devel] windows port [was: Re: Library interop...]

[Mike A. <mj...@co...>]

> Any plans to add windows support in this new version?

There is a win32 port of st-1.0 but nothing newer than that.  We would
welcome a roll-up win32 port of the latest st version, but Gene and I
lack the resources to do it ourselves.  Anyone else?
-- 
Mike Abbott    ma...@us...
State Threads Project co-administrator

RES: [ST-devel] Library interoperability problem (was: current status?)

[Jorge R. <jr...@fo...>]

Any plans to add windows support in this new version?


On Tue, Nov 18, 2003 at 08:35:51AM -0800, Mike Abbott wrote:
> > Just wondering what the current status of State Threads is.
>=20
> Funny you should ask.  Gene and I talked recently about releasing a=20
> new version.  I think the result of the conversation was that Gene had =

> to recover his computer from its disk crash first then he would=20
> forward to me all his changes.  Then I'll make a new version.

[ST-devel] Library interoperability problem (was: current status?)

[Wesley W. T. <we...@te...>]

On Tue, Nov 18, 2003 at 08:35:51AM -0800, Mike Abbott wrote:
> > Just wondering what the current status of State Threads is.
> 
> Funny you should ask.  Gene and I talked recently about releasing a new
> version.  I think the result of the conversation was that Gene had to
> recover his computer from its disk crash first then he would forward to
> me all his changes.  Then I'll make a new version.

Although I know I am just a lowly peon, there is something I think 
REALLY needs to be addressed before the next release:

Compatibility with libpthread.

I don't mean both threading models being used simultaneously, but I do mean
at least link-level compatibility. Right now, many useful libraries which
have nothing thread specific are linked to libpthread.

For example, libxml is not multithreaded; however, it links to libpthreads
so that it can protect global datastructures which would cause it to
segfault under a pthread multi-threaded application.

Most of gnome >= 2.2 also links to pthreads for the same reason. In fact,
nearly all reasonably mature libraries in the open source world get linked
to pthreads for one reason or another.

For those not aware, if you link (in)directly to libpthread, the moment a
non-primordial state thread runs nearly any method, it will die.

I have looked into this problem to some depth; here is what I know:

Pthread and glibc are tightly coupled.
Glibc makes several calls to weak symbols which are provided by pthread.
As long as pthread is not linked, these methods are all NULL and libc does
not end up actually calling them.
Once pthread is linked to an application, whether by a dependent library or
directly, its methods get called regardless of whether or not it is used.
Even something as simple as 'int j = errno;' will end up calling pthreads.
Pthreads on linux looks for thread information at the bottom of the stack.
In state threads, this information is not present.
This means the program segfaults.

This presents a problem for a would-be libst user: If they use libst
they are unable to use a large number of high quality libraries. I like
st a lot, but several times now this choice has forced me to use pthreads.

The scenario where I first ran into this was by linking to libxml.
My program segfaulted immediately after a state thread checked errno.

I find it extremely unlikely that glibc/pthreads will change ABI
compatibility for us. This change could not be backwards compatible 
on their part since they use some inlined macros which get compiled 
into applications. Naturally, this sucks for us, but there it is.

I hope I have convinced you that the current state of affairs is not
acceptable. So now we need to talk solutions or work-arounds.

I have some ideas about how to deal with this, but I'd like to hear what
others think first.

-- 
Wesley W. Terpstra <we...@te...>

Re: [ST-devel] current status?

[Mike A. <mj...@co...>]

> Just wondering what the current status of State Threads is.

Funny you should ask.  Gene and I talked recently about releasing a new
version.  I think the result of the conversation was that Gene had to
recover his computer from its disk crash first then he would forward to
me all his changes.  Then I'll make a new version.

> Andreas Gustafsson posted a patch to the list on 2003-10-15 13:58

Since I no longer have access to a server farm for benchmarking, your
feedback on the efficacy of his patch would be most welcome.

Glad to hear of another happy customer!
-- 
Mike Abbott    ma...@us...
State Threads Project co-administrator

[ST-devel] current status?

[<cu...@ya...>]

Hi Mike Abbott, Gene Shekhtman et al,

Just wondering what the current status of State Threads is. It seems rather quiet on this list.
Have there been any changes or updates that would warrant an incremental release, or even any
tantalizing precursors/snapshots? I tried going through sourceforge cvs, but it looks like you
guys don't check stuff in to cvs.

I'm currently knee deep in writing a couple of apps that make heavy use of state threads. I'm
hitting some performance issues at high load. I can reproduce the problem by using the "server"
example and writing a small app that connects to the "server" and hammers it as fast as it can. A
little bit of timing shows that it can manage only around 7000 connections/second. Anything above
that and the "server" seems to lock up for short periods, serving a few connections in spurts,
then locking up, then serving a few more connections. The jerkiness is more prevalent when there
are multiple processes hitting a single "server" process. Oh, this is on a P3 Linux 8 box. I'm
just wondering if this is a queue size problem (although I've bumped it past 10000), an OS problem
(FD_SETSIZE or somaxconn), or just something to do with state threads?

I noticed, while reading through the archives, that Andreas Gustafsson posted a patch to the list
on 2003-10-15 13:58  that was meant to help state threads timer performance. Has anyone had a
chance to apply this patch to see how it performs?

Any input would be welcomed...

cheers.
Cuong Nguyen.

http://personals.yahoo.com.au - Yahoo! Personals
New people, new possibilities. FREE for a limited time.

[ST-devel] Patches to improve State Threads timer performance

[<gs...@no...>]

State Threads currently uses a sorted doubly linked list to keep track
of threads waiting for a timeout.  This works fine in applications
that have only a small number of threads waiting for timeouts at any
one time, but performance quickly degrades when there are hundreds or
even thousands of waiting threads.  This has turned out to be a
significant performance bottleneck in our applications.

The attached patches remedy this performance problem by replacing the
doubly linked list with a linked heap data structure, which reduces
the asymptotic time complexity of inserting a new waiting thread from
O(N) to O(log n).  We have successfully been using a version of State
Threads with these modifications for several months now.

Please consider integrating these patches into the release.
-- 
Andreas Gustafsson, gs...@no...

diff -u st-1.4.orig/common.h st-1.4/common.h
--- st-1.4.orig/common.h	2002-02-22 12:55:46.000000000 -0800
+++ st-1.4/common.h	2003-10-15 10:26:36.000000000 -0700
@@ -151,7 +151,9 @@
 } _st_cond_t;
 
 
-typedef struct _st_thread {
+typedef struct _st_thread _st_thread_t;
+
+struct _st_thread {
   int state;                  /* Thread's state */
   int flags;                  /* Thread's flags */
 
@@ -166,14 +168,18 @@
 #ifdef DEBUG
   _st_clist_t tlink;          /* For putting on thread queue */
 #endif
-  st_utime_t sleep;           /* Sleep time when thread is sleeping */
+
+  st_utime_t due;             /* Wakeup time when thread is sleeping */
+  _st_thread_t *left;         /* For putting in timeout heap */
+  _st_thread_t *right;
+  int heap_index;
 
   void **private_data;        /* Per thread private data */
 
   _st_cond_t *term;           /* Termination condition variable for join */
 
   jmp_buf context;            /* Thread's context */
-} _st_thread_t;
+};
 
 
 typedef struct _st_mutex {
@@ -197,14 +203,15 @@
 
   _st_clist_t run_q;          /* run queue for this vp */
   _st_clist_t io_q;           /* io queue for this vp */
-  _st_clist_t sleep_q;        /* sleep queue for this vp */
   _st_clist_t zombie_q;       /* zombie queue for this vp */
 #ifdef DEBUG
   _st_clist_t thread_q;       /* all threads of this vp */
 #endif
-  st_utime_t sleep_max;
   int pagesize;
 
+  _st_thread_t *sleep_q;      /* sleep queue for this vp */
+  int sleepq_size;	      /* number of threads on sleep queue */
+
 #ifndef USE_POLL
   int maxfd;
   fd_set fd_read_set, fd_write_set, fd_exception_set;
@@ -237,7 +244,6 @@
 #define _ST_CURRENT_THREAD()            (_st_this_thread)
 #define _ST_SET_CURRENT_THREAD(_thread) (_st_this_thread = (_thread))
 
-#define _ST_SLEEPQMAX                   (_st_this_vp.sleep_max)
 #define _ST_PAGE_SIZE                   (_st_this_vp.pagesize)
 
 #define _ST_FD_READ_SET                 (_st_this_vp.fd_read_set)
@@ -258,6 +264,7 @@
 #define _ST_IOQ                         (_st_this_vp.io_q)
 #define _ST_RUNQ                        (_st_this_vp.run_q)
 #define _ST_SLEEPQ                      (_st_this_vp.sleep_q)
+#define _ST_SLEEPQ_SIZE                 (_st_this_vp.sleepq_size)
 #define _ST_ZOMBIEQ                     (_st_this_vp.zombie_q)
 
 #ifdef DEBUG
diff -u st-1.4.orig/sched.c st-1.4/sched.c
--- st-1.4.orig/sched.c	2002-01-30 19:46:11.000000000 -0800
+++ st-1.4/sched.c	2003-10-15 10:24:13.000000000 -0700
@@ -183,12 +183,14 @@
 
   ST_INIT_CLIST(&_ST_RUNQ);
   ST_INIT_CLIST(&_ST_IOQ);
-  ST_INIT_CLIST(&_ST_SLEEPQ);
   ST_INIT_CLIST(&_ST_ZOMBIEQ);
 #ifdef DEBUG
   ST_INIT_CLIST(&_ST_THREADQ);
 #endif
 
+  _ST_SLEEPQ = NULL;
+  _ST_SLEEPQ_SIZE = 0;
+
 #ifndef USE_POLL
   _st_this_vp.maxfd = -1;
 #else
@@ -286,10 +288,13 @@
   wp = &w;
   ep = &e;
 
-  if (ST_CLIST_IS_EMPTY(&_ST_SLEEPQ)) {
+  if (_ST_SLEEPQ == NULL) {
     tvp = NULL;
   } else {
-    min_timeout = (_ST_THREAD_PTR(_ST_SLEEPQ.next))->sleep;
+    if (_ST_SLEEPQ->due <= _st_this_vp.last_clock)
+      min_timeout = 0;
+    else
+      min_timeout = _ST_SLEEPQ->due - _st_this_vp.last_clock;
     timeout.tv_sec  = (int) (min_timeout / 1000000);
     timeout.tv_usec = (int) (min_timeout % 1000000);
     tvp = &timeout;
@@ -613,43 +618,127 @@
 }
 
 
-void _st_add_sleep_q(_st_thread_t *thread, st_utime_t timeout)
-{
-  st_utime_t sleep;
-  _st_clist_t *q;
-  _st_thread_t *t;
+/*
+ * Insert "thread" into the timeout heap, in the position
+ * specified by thread->heap_index.
+ */
+static _st_thread_t **heap_insert(_st_thread_t *thread) {
+  int target = thread->heap_index;
+  int s = target;
+  _st_thread_t **p = &_ST_SLEEPQ;
+  int bits = 0;
+  int bit;
+  int index = 1;
+
+  while (s) {
+    s >>= 1;
+    bits++;
+  }
+  for (bit = bits - 2; bit >= 0; bit--) {
+    if (thread->due < (*p)->due) {
+      _st_thread_t *t = *p;
+      thread->left = t->left;
+      thread->right = t->right;
+      *p = thread;
+      thread->heap_index = index;
+      thread = t;
+    }
+    index <<= 1;
+    if (target & (1 << bit)) {
+      p = &((*p)->right);
+      index |= 1;
+    } else {
+      p = &((*p)->left);
+    }
+  }
+  thread->heap_index = index;
+  *p = thread;
+  thread->left = thread->right = NULL;
+  return p;
+}
 
-  /* Check if we are longest timeout */
-  if (timeout >= _ST_SLEEPQMAX) {
-    ST_APPEND_LINK(&thread->links, &_ST_SLEEPQ);
-    thread->sleep = timeout - _ST_SLEEPQMAX;
-    _ST_SLEEPQMAX = timeout;
-  } else {
-    /* Sort thread into global sleep queue at appropriate point */
-    sleep = _ST_SLEEPQMAX;
-    q = _ST_SLEEPQ.prev;
-
-    /* Now scan the list backward for where to insert this entry */
-    while (q != &_ST_SLEEPQ) {
-      t = _ST_THREAD_PTR(q);
-      sleep -= t->sleep;
-      if (timeout >= sleep) {
-	/* Found sleeper to insert in front of */
+/*
+ * Delete "thread" from the timeout heap.
+ */
+static void heap_delete(_st_thread_t *thread) {
+  _st_thread_t *t, **p;
+  int bits = 0;
+  int s, bit;
+
+  /* First find and unlink the last heap element */
+  p = &_ST_SLEEPQ;
+  s = _ST_SLEEPQ_SIZE;
+  while (s) {
+    s >>= 1;
+    bits++;
+  }
+  for (bit = bits - 2; bit >= 0; bit--) {
+    if (_ST_SLEEPQ_SIZE & (1 << bit)) {
+      p = &((*p)->right);
+    } else {
+      p = &((*p)->left);
+    }
+  }
+  t = *p;
+  *p = NULL;
+  --_ST_SLEEPQ_SIZE;
+  if (t != thread) {
+    /*
+     * Insert the unlinked last element in place of the element we are deleting
+     */
+    t->heap_index = thread->heap_index;
+    p = heap_insert(t);
+    t = *p;
+    t->left = thread->left;
+    t->right = thread->right;
+
+    /*
+     * Reestablish the heap invariant.
+     */
+    for (;;) {
+      _st_thread_t *y; /* The younger child */
+      int index_tmp;
+      if (t->left == NULL)
+	break;
+      else if (t->right == NULL)
+	y = t->left;
+      else if (t->left->due < t->right->due)
+	y = t->left;
+      else
+	y = t->right;
+      if (t->due > y->due) {
+	_st_thread_t *tl = y->left;
+	_st_thread_t *tr = y->right;
+	*p = y;
+	if (y == t->left) {
+	  y->left = t;
+	  y->right = t->right;
+	  p = &y->left;
+	} else {
+	  y->left = t->left;
+	  y->right = t;
+	  p = &y->right;
+	}
+	t->left = tl;
+	t->right = tr;
+	index_tmp = t->heap_index;
+	t->heap_index = y->heap_index;
+	y->heap_index = index_tmp;
+      } else {
 	break;
       }
-      q = q->prev;
     }
-    thread->sleep = timeout - sleep;
-    ST_INSERT_BEFORE(&thread->links, q);
-
-    /* Subtract our sleep time from the sleeper that follows us */
-    ST_ASSERT(thread->links.next != &_ST_SLEEPQ);
-    t = _ST_THREAD_PTR(thread->links.next);
-    ST_ASSERT(_ST_THREAD_PTR(t->links.prev) == thread);
-    t->sleep -= thread->sleep;
   }
+  thread->left = thread->right = NULL;
+}
+
 
+void _st_add_sleep_q(_st_thread_t *thread, st_utime_t timeout)
+{
+  thread->due = _st_this_vp.last_clock + timeout;
   thread->flags |= _ST_FL_ON_SLEEPQ;
+  thread->heap_index = ++_ST_SLEEPQ_SIZE;
+  heap_insert(thread);
 }
 
 
@@ -658,31 +747,8 @@
  */
 void _st_del_sleep_q(_st_thread_t *thread, int expired)
 {
-  _st_clist_t *q;
-  _st_thread_t *t;
-
-  /* Remove from sleep queue */
-  ST_ASSERT(thread->flags & _ST_FL_ON_SLEEPQ);
-  q = thread->links.next;
-  if (q != &_ST_SLEEPQ) {
-    if (expired) {
-      _ST_SLEEPQMAX -= thread->sleep;
-    } else {
-      t = _ST_THREAD_PTR(q);
-      t->sleep += thread->sleep;
-    }
-  } else {
-    /*
-     * Check if prev is the beginning of the list; if so,
-     * we are the only element on the list.  
-     */
-    if (thread->links.prev != &_ST_SLEEPQ)
-      _ST_SLEEPQMAX -= thread->sleep;
-    else
-      _ST_SLEEPQMAX = 0;
-  }
+  heap_delete(thread);
   thread->flags &= ~_ST_FL_ON_SLEEPQ;
-  ST_REMOVE_LINK(&thread->links);
 }
 
 
@@ -700,18 +766,12 @@
     _st_last_tset = now;
   }
 
-  while (_ST_SLEEPQ.next != &_ST_SLEEPQ) {
-    thread = _ST_THREAD_PTR(_ST_SLEEPQ.next);
+  while (_ST_SLEEPQ != NULL) {
+    thread = _ST_SLEEPQ;
     ST_ASSERT(thread->flags & _ST_FL_ON_SLEEPQ);
-
-    if (elapsed < thread->sleep) {
-      thread->sleep -= elapsed;
-      _ST_SLEEPQMAX -= elapsed;
+    if (thread->due > now)
       break;
-    }
-
     _ST_DEL_SLEEPQ(thread, 1);
-    elapsed -= thread->sleep;
 
     /* If thread is waiting on condition variable, set the time out flag */
     if (thread->state == _ST_ST_COND_WAIT)
@@ -814,6 +874,9 @@
   thread->stack = stack;
   thread->start = start;
   thread->arg = arg;
+  thread->left = 0;
+  thread->right = 0;
+  thread->heap_index = -1;
 
 #ifndef __ia64__
   _ST_INIT_CONTEXT(thread, stack->sp, _st_thread_main);

--- /dev/null	2003-07-14 13:04:09.000000000 -0700
+++ docs/timeout_heap.txt	2003-05-15 13:28:43.000000000 -0700
@@ -0,0 +1,61 @@
+
+How the timeout heap works
+
+This version of ST represents the queue of sleeping threads using a
+heap data structure rather than a sorted linked list.  This improves
+performance when there is a large number of sleeping threads, since
+insertion into a heap takes O(log N) time while insertion into a
+sorted list takes O(N) time.  For example, in one test 1000 threads
+were created, each thread called st_usleep() with a random time
+interval, and then all the threads where immediately interrupted and
+joined before the sleeps had a chance to finish.  The whole process
+was repeated 1000 times, for a total of a million sleep queue
+insertions and removals.  With the old list-based sleep queue, this
+test took 100 seconds; now it takes only 12 seconds.
+
+Heap data structures are typically based on dynamically resized
+arrays.  However, since the existing ST code base was very nicely
+structured around linking the thread objects into pointer-based lists
+without the need for any auxiliary data structures, implementing the
+heap using a similar nodes-and-pointers based approach seemed more
+appropriate for ST than introducing a separate array.
+
+Thus, the new ST timeout heap works by organizing the existing
+_st_thread_t objects in a balanced binary tree, just as they were
+previously organized into a doubly-linked, sorted list.  The global
+_ST_SLEEPQ variable, formerly a linked list head, is now simply a
+pointer to the root of this tree, and the root node of the tree is the
+thread with the earliest timeout.  Each thread object has two child
+pointers, "left" and "right", pointing to threads with later timeouts.
+
+Each node in the tree is numbered with an integer index, corresponding
+to the array index in an array-based heap, and the tree is kept fully
+balanced and left-adjusted at all times.  In other words, the tree
+consists of any number of fully populated top levels, followed by a
+single bottom level which may be partially populated, such that any
+existing nodes form a contiguous block to the left and the spaces for
+missing nodes form a contiguous block to the right. For example, if
+there are nine threads waiting for a timeout, they are numbered and
+arranged in a tree exactly as follows:
+
+              1
+           /     \
+          2       3
+         / \     / \
+        4   5   6   7
+       / \
+      8   9
+
+Each node has either no children, only a left child, or both a left
+and a right child.  Children always time out later than their parents
+(this is called the "heap invariant"), but when a node has two
+children, their mutual order is unspecified - the left child may time
+out before or after the right child.  If a node is numbered N, its
+left child is numbered 2N, and its right child is numbered 2N+1.
+
+There is no pointer from a child to its parent; all pointers point
+downward.  Additions and deletions both work by starting at the root
+and traversing the tree towards the leaves, going left or right
+according to the binary digits forming the index of the destination
+node.  As nodes are added or deleted, existing nodes are rearranged to
+maintain the heap invariant.

Re: [ST-devel] libst + gui = hosted event loop

[Wesley W. T. <we...@te...>]

On Thu, Apr 10, 2003 at 01:19:13PM +0200, Jose Marcio Martins da Cruz wrote:
> The first time I read about state threads, what I found very interesting, and
> surely to many people, is the probable high performance at some internet
> servers, which surely doesn't have any type of graphical interface : web
> servers, smtp servers, proxies, ...

Of course; I think this is what most of us use libst for: fast internet
applications. Also, it is a safer way to get threading than using libpthread
for internet applications in the end-user domain.

For example, my current project uses it for a p2p network.

> I'm afraid of including graphical libraries such as glib, and lack the
> interest of state threads library to high performance servers.

I think I've lost what you meant here?
Could you clarify?

Are you saying libst is not right for you because you don't write scalable
internet servers, and find integrating it with glib too hard?

Certainly libst is not right for all projects.

> But maybe I'm wrong.
> 
> My two cents.

Maybe you're wrong, but maybe you're right, so what did you say? :-)

---
Wes

Re: [ST-devel] libst + gui = hosted event loop

[Jose M. M. da C. <Jos...@en...>]

Hi,


The first time I read about state threads, what I found very interesting, and
surely to many people, is the probable high performance at some internet
servers, which surely doesn't have any type of graphical interface : web
servers, smtp servers, proxies, ...

I'm afraid of including graphical libraries such as glib, and lack the interest
of state threads library to high performance servers.

But maybe I'm wrong.

My two cents.

Jose Marcio


"Wesley W. Terpstra" wrote:
> 
> On Wed, Apr 09, 2003 at 08:43:50PM -0700, fre...@ug... wrote:
> > > On Tue, Mar 11, 2003 at 12:05:38PM -0800, fre...@ug... wrote:
> > >> Perhaps I'm missing some libst issue which would make this impossible,
> > >> but if the GUI is not performance-critical, then why not have it run
> > >> in one pthread, and have all the libst threads and the libst event
> > >> loop (which might include some network client, etc.) in another
> > >> pthread?
> > >
> > > Well, for starters, libst + pthread = crash. :-)
> >
> > I see... indeed, even linking with libpthread causes a segfault for
> > me. Do you know what causes this?
> 
> Yes; pthread replaces some C library methods with new symbols.
> These overloaded methods use a trick to find the thread context.
> They get a bad context, try to read it, and boom!
> 
> I was looking into how to fix this, but got distracted.
> 
> The original problem: libst + gui could be solved by hosting glib on libst.
> I have a source file which accomplishes this; it uses glib's ability to have
> a replaced main event loop. This was enough for me since gtk does not use
> libpthread. I just use st_poll to implement it.
> 
> However, gnome2 does, so anyone who wants to link to both gnome2 and libst
> is ... screwed. That is why I was looking at it, but the pthread code has a
> jungle of #ifdefs around the context locating code. I couldn't decide which
> one it was actually using! At least one of the methods is to round the stack
> up by a fixed stack size and take the base value as the context ptr. It is
> clear why this + st wouldn't work.
> 
> Sorry I didn't post this half-positive result. At the time I was hoping for
> a complete solution, but now I don't have an interest in fixing it.
> 
> ---
> Wes
> 
> -------------------------------------------------------
> This SF.net email is sponsored by: Etnus, makers of TotalView, The debugger
> for complex code. Debugging C/C++ programs can leave you feeling lost and
> disoriented. TotalView can help you find your way. Available on major UNIX
> and Linux platforms. Try it free. www.etnus.com
> _______________________________________________
> State-threads-devel mailing list
> Sta...@li...
> https://lists.sourceforge.net/lists/listinfo/state-threads-devel

-- 
 ---------------------------------------------------------------
 Jose Marcio MARTINS DA CRUZ           Tel. :(33) 01.40.51.93.41
 Ecole Nationale Superieure des Mines de Paris   
 Centre de Calcul                      http://j-chkmail.ensmp.fr
 60, bd Saint Michel                http://www.ensmp.fr/~martins
 75272 - PARIS CEDEX 06      mailto:Jos...@en...        
 ---------------------------------------------------------------

Re: [ST-devel] libst + gui = hosted event loop

[Wesley W. T. <we...@te...>]

On Wed, Apr 09, 2003 at 08:43:50PM -0700, fre...@ug... wrote:
> > On Tue, Mar 11, 2003 at 12:05:38PM -0800, fre...@ug... wrote:
> >> Perhaps I'm missing some libst issue which would make this impossible,
> >> but if the GUI is not performance-critical, then why not have it run
> >> in one pthread, and have all the libst threads and the libst event
> >> loop (which might include some network client, etc.) in another
> >> pthread?
> >
> > Well, for starters, libst + pthread = crash. :-)
> 
> I see... indeed, even linking with libpthread causes a segfault for
> me. Do you know what causes this?

Yes; pthread replaces some C library methods with new symbols.
These overloaded methods use a trick to find the thread context.
They get a bad context, try to read it, and boom!

I was looking into how to fix this, but got distracted.

The original problem: libst + gui could be solved by hosting glib on libst.
I have a source file which accomplishes this; it uses glib's ability to have
a replaced main event loop. This was enough for me since gtk does not use
libpthread. I just use st_poll to implement it.

However, gnome2 does, so anyone who wants to link to both gnome2 and libst
is ... screwed. That is why I was looking at it, but the pthread code has a
jungle of #ifdefs around the context locating code. I couldn't decide which
one it was actually using! At least one of the methods is to round the stack
up by a fixed stack size and take the base value as the context ptr. It is
clear why this + st wouldn't work.

Sorry I didn't post this half-positive result. At the time I was hoping for
a complete solution, but now I don't have an interest in fixing it.

---
Wes

Re: [ST-devel] libst + gui = hosted event loop

[Mike A. <mj...@at...>]

> If you are going to have to put all the IO in exactly one pthread anyways,
> and have to communicate with it somehow, one would probably be better off
> simply making a slave process that the GUI talks to via a pipe.

Simple:  just port glib to st.  I have no knowledge of glib internals,
but I can imagine that it manages just a few file descriptors that never
change (to wait for mouse/keyboard/graphics events).  Maybe porting that
low-level handling to st is actually realistic.

Otherwise I don't see an easy way to mix two or more separate
event-driven architectures.  Port one library to the semantics of
another, or distill out the common parts and port both libraries to a
new, lower-level library that owns all events/fds, or keep them apart in
separate processes.

Re: [ST-devel] libst + gui = hosted event loop

[Wesley W. T. <we...@te...>]

On Tue, Mar 11, 2003 at 12:05:38PM -0800, fre...@ug... wrote:
> Perhaps I'm missing some libst issue which would make this impossible,
> but if the GUI is not performance-critical, then why not have it run
> in one pthread, and have all the libst threads and the libst event
> loop (which might include some network client, etc.) in another
> pthread?

Well, for starters, libst + pthread = crash. :-)

Further, then you throw out all the nice almost-no-locking-required benefits
of using libst. I don't just mean for speed (you're right, it wouldn't be
performance critical), but I mean for stablity---no races, no deadlock.

Finally, what happens if two pthreads use IO functions?

In this case you could have a truly nasty bug where another pthread tries to
context switch into _st_vp_idle -- who knows what this would do. Bad things.

If you are going to have to put all the IO in exactly one pthread anyways,
and have to communicate with it somehow, one would probably be better off
simply making a slave process that the GUI talks to via a pipe.

However, I would rather have the option to keep the whole thing as one
simple process.

---
Wes