dmitry_vk's notes

More progress in Windows threading for SBCL

There is some progress on Windows threads for SBCL.

I am using the code shown below as a test. As of now, it does run without hanging. That is, concurrent memory allocation in multiple threads with concurrent garbage collection requests is now working. I will check it more thoroughly on a beefier 4-core computer for multiple hours to ensure that the approach is right, but for now it seems to be working fine.

(defun cons-lot (stream char)
  (sleep 2)
  (loop
    (loop repeat 10
      for ar = (make-array (* 1024 1024 1/2) :initial-element 0)
      do (setf (aref ar 1000) 112))
    (format stream "~A" char)
    (finish-output stream)))

(defun threaded-cons-lot (n)
  (loop
    with stream = *standard-output*
    repeat n
    do (sb-thread:make-thread (lambda () (cons-lot stream #\.)))))

(threaded-cons-lot 4)

After all, lack of asynchronous IPC in Windows API is noticeable. Correct thread suspension is achievable in POSIX (it takes to carefully manipulate signal mask to ensure that the signal does not arrive at unfortunate moments), while it becomes very fragile on Windows. There are not a lot of options for asynchronous thread communication: basically, we can use SuspendThread and analyze and manipulate the thread state (which is very non-trivial). Another option is to implement cooperative thread suspension in which the thread itself should on its own periodically check whether it should suspend or interrupt. I don't claim to be an expert in this area, but it seems to be a significant drawback of Windows APIs in the IPC area.

(On the other note, thread synchronization in Windows is quite tricky and fragile due to internals of asynchronous inter-thread communication. For example, asynchronous procedure call may cause a thread waiting on a synchronization event to miss a notification from PulseAll function.)

In SBCL, garbage collection is implemented in the following manner:

  1. The thread discovers that it is time to do a garbage collection cycle. The thread may discover this either while performing an allocation (in which case the thread is inside a pseudo-atomic section with signals masked) or due to explicit call to SB-EXT:GC (in which case the thread is not in the pseudo-atomic case).
  2. The thread locks the *ALREADY-IN-GC* mutex whils having its signals unmasked. This is required in order for multiple threads to be able to invoke the garbage collection: one thread will take the lock and other threads will be stoppable (since the signals are unmasked).
  3. The thread that has locked the mutex sends the SIG_STOP_FOR_GC signal to all other threads and awaits for them to actually stop. When the thread stops, it set its thread.state field to STATE_SUSPENDED and signals the thread's state_cond condition variable.
  4. The threads receive the signals and suspend themselves. The key point is that the thread will receive the signal only when it is ready to handle it. For example, the thread is able to handle the signal and suspend while it is blocked trying to lock the *ALREADY-IN-GC* mutex.
  5. When all threads are suspended, a garbage collection is performed. While one thread performs the garbage collection, all threads are waiting on the state_cond conditional variables.
  6. Threads have their state set to STATE_RUNNING and are resumed.

In Win32 API there are significant challenges with the 4th item. There is no way to have the thread code execute some code in such a way that would be safe for the thread without having the thread be in some special state. If we ignore safety then there is the SetThreadContext function that lets us redirect the thread to arbitrary code. If we limit the thread only to some special state, then there is the QueueUserAPC function, but APCs (async procedure calls) are invoked only while the thread is in some special state - that is, while it's blocked on SleepEx, WaitForSingleObjectEx or WaitForMultipleObjectsEx.

As an alternative, there a different technique to achieve thread notification which is used in the JVM. A special code sequence is inserted in some locations of a program that somehow checks whether the thread should suspend or interrupt or do something special. This request can be communicated via the memory protection attributes of a special memory page so that accessing it is normally a no-op but in special circumstances it would redirect the thread to the signal handler. This is a viable approach but it requires more work and requires the thread to periodically do something.

So my plan is as follows. Since I can't make the thread stop in safe way, then I will have to resort to more complicated way of stopping threads using SuspendThread. For garbage collection, there are two hazards - if another thread locks something that is needed for a garbage collector, and if the garbage collector witnesses an object in the middle of its initilization. That's why all the locks used by the garbage collector must be taken right at the start of garbage collection cycle. An incomplete object initialization corresponds to a pseudo-atomic section; therefore we can set the thread's pseudo-atomic-interrupted flag so that the thread would know that it should stop as it leaves the pseudo-atomic section. If a thread is inside a pseudo-atomic and tries to invoke the garbage collection then it must grab the GC mutex - therefore we use ptread_mutex_trylock instead of pthread_mutex_lock so that one thread would successfully grab the mutex and the other threads would know to stop. And the thread a normal state is stopped with the SuspendThread with all of its locks kept held which means that the garbage collector must not take the same locks to avoid deadlocking. And the starting and stopping of the GC is done with a pair of AutoResetEvents: gc_suspend_event and gc_resume_event.

Now I need to verify the proper functioning of the thread stopping and come up with a way to interrupt running threads which is, for example, used by SLIME to interrupt long-running processes.