I was just browsing the Parrot source, and noticed that the threading
implementation is a bit Unix/pthread-centric. For example:

* COND_WAIT takes a mutex because that's how pthreads works, but Win32
condition variables (called "events") are kernel objects that do not
require any other object to be associated with them. I think this
could be cleaned up with further abstraction.

* CLEANUP_PUSH doesn't have any Win32 analog that I know of, although
it's not clear why this might be needed for Parrot anyway. Right now
it just looks like it's used to prevent threads from abandoning a
mutex, which isn't a problem with Win32.

The big issue, though, is with the IO thread. On NT the IO is already
async and there are no signals (Ctrl+C is handled with a callback), so
each interpreter thread should just be able to handle all of this in
the check_events functions. That is, AIO and timers allow you to
specify a completion callback (asynchronous procedure call) that gets
executed once you tell the OS that you're ready for them (e.g. via
Sleep), so the whole event dispatching system may not even be
necessary. Win9x doesn't have async IO on files, so it still might
require separate threads to do IOs.

Note that the Windows message queue does not really get involved here
(unless you want it to), as it is mainly for threads that have UIs or
use COM/DDE.

Anyway, it seems to me that all this event/IO stuff needs
significantly more abstraction in order to prevent it from becoming a
hacked-up mess of #ifdefs. However, I couldn't find any docs on this,
so I just guessed how it all works based on the source. Feel free to
whack me with a cluestick if I'm wrong about anything.

GNS

Not quite. COND_WAIT takes an opaque type defined by the platform, that
happens to be a mutex for the pthreads based implementation.

Yes. And it'll very likely go away. But anyway - it's a define by the
platform. So you can define it being a noop for win32.

Not all. We need to do check_events() for e.g. message passing too.

I'm not sure, if we even should support Win9{8,5}.

Yep. The system-specific stuff should be split into platform files. A
common Parrot API then talks to platform code.

The current state of the implemented pthread model is summarized in
docs/dev/events.pod.

Au contraire. Your analysis is precise. Do you like to take a shot at a
Win32 threads/event model? So we could figure out the necessary
splitting of API/implementation.

leo

At 12:57 PM +0100 11/15/04, Leopold Toetsch wrote:

Yep. This is important to note -- the joys of portability often means
that functions in the source carry parameters that might not actually
get used. That's the case here, since POSIX threads (which the unices
and VMS use for their threading model) requires a mutex. I fully
expect we'll have similar bits carried around to accomodate windows
too.

And notifications, and possibly cleanup of objects with finalizers.

Nope. Or, rather, we officially don't care if we run on Win9x/WinME.
If we do, swell. If not, well...

Win9x isn't particularly special here. We feel the same about
AmigaDOS, VMS 5.5, HP/UX 10.x, SunOS, Linux 1.x, and BeOS. Amongst
others.

Yeah. The event stuff's definitely primitive, and not much thought's
been given to it as of yet.
--
                                Dan

--------------------------------------it's like this-------------------
Dan Sugalski                          even samurai
d...@sidhe.org                         have teddy bears and even
                                       teddy bears get drunk

It should, but it doesn't. Here's the definition:
#  define COND_WAIT(c,m) pthread_cond_wait(&c, &m)
It explicitly takes a condition and a mutex, while it should just be
passed a Parrot_cond (or something like that):

typedef struct {
#ifdef pthreads
    pthread_mutex_t m;
    pthread_cond_t c;
#elseif Win32
    HANDLE h;
#endif

I'd be happy with simply implementing Win9x as a non-threaded
platform. Of course, hopefully nobody will even ask...

Thanks, I didn't see that. My problem isn't with what the
implementation does, though -- it's that I don't understand the
rationale. I can understand why there would need to be a global event
thread (timers, GC, DoD), but why would passing a message from one
thread to another need to be serialized through a global event queue?

And as for IO, I see the obvious advantages of performing synchronous
IO functions in a separate thread to make them asynchronous, but that
sounds like the job of a worker thread pool. There are many ways to
implement this, but serializing them all through one queue sounds like
a bottleneck to me.

OK. I think I need to have a better understanding on what events
actually are, though. Who sends them? What do they mean? Which signals
do we actually care about? What are notifications? How will AIO
actually be handled? You know, that sort of thing... Maybe there
should be a PDD for it?

GNS

You are already in the POSIX specific part.

1) During configure parrot includes platform code from files located in
  config/gen/platform/*/

2) if a platform doesn't have an implementation the ../generic/
directory is used.

3) $ find config -name threads.h
config/gen/platform/generic/threads.h

So there is no win32/threads.h (yet ;)

If the implementation needs some additional libraries, the hints/* are
consulted e.g.

config/init/hints/linux.pl:    $libs .= ' -lpthread';

We'll see. But as Parrot's IO system is gonna be asynchronous in core, I
doubt that we'll support it.

The main reason for the global event queue isn't message passing. The
reason is POSIX signals. Basically you aren't allowed to do anything
serious in a signal handler, especially you aren't allowed to broadcast
a condition or something.
So I came up with that experimental code of one thread doing signals.

Yes. The AIO library is doing that anyway i.e. utilizing a thread pool
for IO operations.

Dan did post a series of documents to the list some time ago. Sorry I'be
no exact subject, but with relevant keywords like "events" you should
find it.

leo

It came from thr_pthread.h, so it should be POSIX. The issue here is
that it's #define COND_WAIT(c,m) instead of #define COND_WAIT(c).
Every place in the code, whether it's Win32 or POSIX, is going to have
to pass in a condition variable and a mutex. Just because Win32 will
ignore the second parameter, that isn't going to prevent the code from
creating the mutex, initializing it, and passing it in.

Obviously Parrot has to run on non-threaded platforms where the kernel
threading and AIO stuff just won't work. You can still do user
threads, but file IO will still block everything.

Yes, there has to be a separate thread to get signals, and each thread
needs its own event queue, but why does the process have a global
event_queue? I suppose there are generic events that could be handled
just by the next thread to call check_events, but that isn't what this
sounds like.

I don't see why there needs to be a separate thread to listen for IOs
to finish. Can't that be the same thread that listens for signals?
That is, the IO thread just spends its whole life doing select(). If
it got a signal, select() should return EINTR, so the thread could
then check a flag to see which signal was raised, queue the event in
the proper queue(s), and call select() again.

OK, I think I understand why...the event thread is in a loop waiting
for somebody to tell it that there's an event in the global event
queue...which is really the part I don't get yet.

Yeah, I remember reading some of his discussions with Damien Neil
because I think I went to school with him.

Anyway, here's my first draft for a Win32 event model:

As for a Win32 event model, I think I should clarify what I'm talking
about when I say Win32.

Win32 IS NOT: The MS Services for Unix package provides a POSIX
subsystem for Windows called Interix which is completely separate from
Win32 (i.e. no GUI is possible, no Win SDK calls are available). It
has fork(), symlinks, pthreads, SysV IPC, POSIX signals, pttys, and
maybe even AIO. This config would be compiled like any other Unix
variant with its own idiosyncracies.

Win32 IS PROBABLY NOT: There are various POSIX emulation layers for
Win32, such as cygwin and MinGW. These provide many function calls
that Unix programs expect, but only to the degree that the Win32
subsystem allows (e.g. chmod likely will not do anything sensible).
Since these programs still run under the Win32 subsystem, Windows GUIs
are still possible. I don't know how these will interact with my event
model.

Win32 IS: This is the standard Win32 API as defined by NT4.0sp6a and
higher. If you want to drop support for NT4, then we go to Win2k, but
don't gain much.

GUI message queues in Win32 are per thread. Each thread has a message
queue that is autovivified. Any window that a thread creates has its
messages sent to that thread's queue. However, there is no reason that
a message actually has to have an associated window. You can send any
thread in any process a message, so long as the thread has had its
queue autovivified and is not crossing security boundaries.

All files or things that look like files can be opened for async
access. For example, sockets, files, and pipes can all be async. Any
read, write, lock, unlock, or ioctl call can either signal a condition
var (Win32 calls them "events", and they don't have POSIX cond_var
semantics) or cause an event to be queued to an IO completion port.
Read and write calls also have the option to queue a callback upon
completion, but since this will only run when we check for them, I
don't think this is useful.

An IOCompletionPort is just an object that can queue completion
events. Once an async file handle has been associated with an IOCP,
any IOs on that handle will cause an event to be sent to the IOCP when
complete. When a thread reads an event it will block until one is
available, then receive the oldest one. Any number of threads may wait
at once, although the most recent waiter gets the next event to
minimize context switches and cache misses. Since any thread can post
an arbitrary message to an IOCP, this may serve as our main event
queue.

Win32 has no signals as POSIX describes them, but there is a way to
specify a routine to get called asynchronously when your terminal
receives a CTRL+C, CTRL+BREAK, the close box is clicked, or the system
is being shut down.

I don't see a need for specific event or IO threads, so I propose a
pool of worker threads (starting at 1, created as needed, possibly up
to N where N is somewhere around the number of CPUs). These threads
all just sit around waiting on the IOCP until something happens. When
an IO completes, obviously an IO completion event would be queued.
When somebody hits CTRL+C, the signal handler would post a CTRL+C
event to the queue. When somebody needs a procedure to be run, they
post a callback event.

Timers are implemented with WaitableTimer objects. One of the pool
threads can set a timer to run a callback when the timer fires. This
callback would do the same event dispatching that getting an IOCP
event would do.

If a thread wants to send an event to another thread, it would do the
event dispatching itself. I don't see any reason it has to go through
the main event queue.

To actually perform an IO, the interpreter thread would pin the buffer
to prevent it from getting GC'd and call the IO function. When the IO
completes, the event will get queued to the IOCP and eventually a pool
thread will dequeue it. At this point it's safe to unpin the R/W
buffer. Now, depending on what the caller asked for, either the IO op
is just marked as completed, or a callback event is dispatched to the
thread that started the IO.

The most important part for windows, of course, is how to handle
Windows messages. I think that a process should just be able to
install a module which will have a procedure that runs whenever
check_events gets called. The thread would process all events in its
queues, then call the Windows message processing functions. If anybody
registered event handlers for messages, they get dispatched, otherwise
Windows will handle them normally. Note that these messages (e.g. "the
system is low on battery") may not be associated with a particular
window.

Finally, a note for JIT core writers: Win32 allows you to suspend
individual threads. So when a thread gets an important signal, you can
queue it, suspend the thread, adjust its stack frame or code so the
next return or jump will be to check_events, and resume the thread.

GNS

It's mainly intended for broadcasts and timers. POSIX signals are weird
and more or less broken from platform to platform. The only reliable way
to get at them is to block the desired signal in all but one thread.
This signal gets converted to a global event and from there it can be
put into specifc threads if they have installed signal handlers for that
signal.

But as said the existing code is experimental and is likely to change a
lot.

That's the plan yes. AIO completion can be delivered as a signal.

Well, the event thread is handling timer events on behalf of an
interpreter.

[ long win32 proposal ]

I've to read through that some more times.

Do you alread have ideas for a common API, or where to split the
existing threads.c into platform and common code?

leo

Well in the mentioned (TODO) platform/win32/threads.h you have to define
your own COND_WAIT(c, m) - this is the interface of that macro, as POSIX
needs the mutex, but you would ignore the 2nd parameter.

Please have a look at the empty defines in include/parrot/threads.h.

The problem is a different one: the COND_INIT macro just passes a
condition location, the mutex is created in a second step, which isn't
needed for windows. OTOH a mutex aka critical section is needed
separatly.

So we should probably define these macros to be:

  COND_INIT(c, m)
  COND_DESTROY(c, m)

see src/tsq.c for usage.

Does win32 require more info to create conditions/mutexes or would these
macros suffice?

[ I'll try to answer more in a separate thread ]

leo

OK; let me know if you have any questions on how the Win32 stuff
works. I tried to explain things that are unlike POSIX, but of course
it makes sense to me.

I didn't see anything in thread.c that was platform specific -- or at
least nothing that looked like it wouldn't work on Win32. Obviously
thr_win32.h will be much different than thr_pthreads.h.

As for a common API, I suppose we would have to figure out how the
modules would interact. In the case of IO (any function names I made
up have capital letters to distinguish them from anything that may be
in the current codebase):

* There is some generic IO code that sets up IO and event objects, and
it sits below the buffering layer. All this stuff is going to be
thread-safe so the low-level IO code shouldn't have to worry about it.
This generic IO code sets up the IO and Event objects indicating what
file, which operation (read/write/lock/unlock), what to do when the
operation completes, how many bytes, file position, and any memory
buffer needed. Then it would pass this information to the OS-specific
code.

So this generic code (say, StartIO()) would create an IO object that
contains the file object, a pointer to the r/w buffer if the operation
requires it, and a file position and byte count if the operation uses
it. It would also contain an event object indicating what to do in
case of failure or completion. StartIO pins the memory buffer, locks
the IO object, and calls Win32AsyncRead or whatever.

The XXXAsyncYYY funtcion starts the IO and returns to StartIO which
unlocks the IO object and returns it to the caller. That can then be
passed into functions to find out if it's complete, cancel it, etc.

If XXX is Win32, the module would just start Read/WriteFile; if it's
Solaris, maybe it'll call aioread/write; if it's POSIX without aio
(e.g. Linux), it'll start up a new thread to do a blocking read/write.

When the IO completes, the XXX code figures out the return code and
how many bytes read/written. This information is passed to the generic
CompleteIO(), which locks the IO object, updates the status (return
code, byte count), unpins the buffer, dispatches the event as
described by the Event object, and unlocks the IO object.

* In the case of timers, there would be XXXCreateTimer and
XXXCancelTimer, while the XXX code would need to call FireTimer().

* I suppose there should be an XXXQueueEvent function as well, but I'm
not certain of its uses. Actual EventDispatch() would be a generic
function that puts an event into a thread's queue and notifies the
thread. I am not sure how to handle general events like RunGC.

* GUI message handlers need to dispatch events synchronously. So the
generic check_events function would call XXXGetGUIMessages which would
need to dispatch the messages to whatever registered for them in that
thread. Since this would amount to method dispatch instead of event
dispatch, it would probably need something special for this.

GNS

Win32 doesn't require anything else, but I don't think I like this
idea. If you do COND_INIT(c, m) and Win32 ignores the 'm', what
happens when some code goes to LOCK(m)? It would work under POSIX but
break under Win32. I think there should be an opaque struct that
contains c,m for POSIX and c for Win32.

GNS

The mutex in COND_INIT is specific to that condition, it can't get
reused in unrelated places. But it is used to synchronize {push,pop,
wait_for}_entry. How is e.g. tsq.c:push_entry() synchronized then on Win32?

Works for me too, modulo above sync issues.

leo

At 8:42 AM -0500 11/19/04, Gabe Schaffer wrote:

This'll mean that every mutex will have a corresponding condition
variable, something that I'm not sure we need.

On the other hand, I can't picture us having so many of these that it
makes any difference at all, so I don't have a problem with it. It
isn't a good general-purpose thread solution (there are plenty of
good reasons to unbundle these) but we don't really *need* a
general-purpose solution. :)

Parrot's locks will all have wait/signal/broadcast capabilities. We
should go rename the macros and rejig the code. This may have to wait
a little -- we're cleaning up the last of subs, I've still got the
string stuff outstanding, and I promised Sam Ruby I'd deal with
classes and metaclasses next.

So much time, so little to do. No, wait, that's not right...
--
                                Dan

--------------------------------------it's like this-------------------
Dan Sugalski                          even samurai
d...@sidhe.org                         have teddy bears and even
                                       teddy bears get drunk

Really? I'm not sure I understand what broadcast does on a lock. Are
you talking about something like P5's condpair? If so, why not just
cop that code? Of course, I don't have a clue what it does on Win32,
so maybe that's not such a good idea.

GNS

Actually, that part works in Win32. Since the queue uses the mutex for
synchronizing access to the queue, it doesn't matter that Win32
wouldn't need it for the condition var.

The problem would only occur when the condition variable doesn't have
anything that it's guarding access to. For example, a thread might be
waiting for a timer to fire. This thread would wait on a condition
variable that would be signalled by the timer thread. Under POSIX, the
newly awoken thread would own a mutex which it wouldn't really need
for anything.

I think that maybe what we need is a MUTEX, a CONDITION, and a
QUEUE_CONDITION. The QUEUE_CONDITION would always contain a mutex and
a condition, while the CONDITION would have a c,m for POSIX and just c
for Win32.

Also, note that with Win32 conditions you must indicate at creation
time whether you want to Signal or Broadcast. Emulating POSIX
semantics on Win32 are tricky, and it's probably overkill for these
purposes.

GNS

Currently we have COND only for the task queues. But if we need
conditions in other places, QUEUE_CONDITION is misleading.
So the current set of macros for existing stuff is ok?

Yeah. I've looked at some emulation libraries. And right, we don't need
the emulation, we just need an equivalent functionality.

I'd say: just give it a try. Where semantics don't fit, we can either
abstract the inferface or put a few #ifdefs in place, which, given the
big differences in events/threads/process philosophy, should be ok, if
they don't clutter the source too much.

leo

It should do.

I agree with this. However, it is entirely possible that somebody will
assume one set of semantics and end up with a race condition that's
hard to debug on another.

That's no problem except where a given COND can be either signalled or
broadcast to. Since Win32 cannot have a single condition that allows
both, each instance will have to decide. In the case of your TSQ,
e.g., it may be necessary to simply eliminate the queue_broadcast()
function -- which is probably not a big deal because I don't see it
called anywhere.

GNS

Such issues need good comments in source code. Does that imply that we
need:

  COND_INIT_SIGNAL
  COND_INIT_BROADCAST

leo

Yes, that is what I would recommend.

GNS