
This document describes the state of threads and lutexes, primarly on
Darwin (MacOS X) on Intel, but I have also begin to try to make this
work on FreeBSD and linux. Currently things build and run, but there
are some underlying problems that cause the build to be unstable.

====================================
CURRENT STATUS
====================================

 * x86/darwin - builds and runs, both threads.impure.lisp and
   timer.impure.lisp fail. gc.impure.lisp works, which is good, but
   the other two tests indicate that there are still significant
   problems.
 
 * x86-64/linux - builds and runs, but threads.impure.lisp (SEMAPHORE
   MUTIPLE-SIGNALS) fails. It does, however, get farther than it does
   in the x86/darwin case. This failure suggests that there may be
   correctness problems in the lutex logic, in addition to platform
   specific bugs.

 * x86/freebsd - like the darwin case, this builds and runs, but fails
   even more severely than in the Darwin case. This has even caused a
   kernel panic on my only freebsd machine (which also happens to be
   my mailserver). I'm planning to upgarde to freebsd to 6.0 and will
   investigate if this helps the situation.

====================================
NEXT BUG NUMBER: 14
====================================

====================================
OPEN BUGS
====================================

1. Threaded builds cannont run slam.sh on themselves. A build with a
   threaded host will build from sources, but slam.sh does not work. A
   non-threaded host can run slam.sh fine.

5. Currently we'll die after 8192 total threads have been created. We
   need to manage our own LDT to fix this until Apple fixes their
   OS. i386_set_ldt LDT_AUTO_ALLOC doesn't reuse freed LDT's
   (radar:4492548).

7. sb-threads/sb-lutex/x86/freebsd builds build and run and simple
   thread creation tests work, but threads.impure.lisp and
   timer.impure.lisp fail. The failure mode is rather severe,
   including a kernel panic in one instance.

12. Ocassionally we don't wake from lutex_wait on MacOS.

13. Compiling swank from slime fails with a TYPE-ERROR

====================================
FIXED BUGS
====================================

(note that this section is, almost by definition, rather incomplete,
but rather should serve as a reminder to anyone looking at this what
some of the issues we had to deal with where)

 * Need to pin the mutex and the lutex before calling futex-wake,
   futex-wait, etc... Orignally we either weren't pinning anything or
   were just pinning the mutex. We need to make sure the lutex doesn't
   move out from under us as well.

 * Set %fs to 0 when freeing the LDT

 * semaphore_signal, and friends, occasionally fail with an error
   KERN_INVALID_NAME or KERN_INVALID_RIGHT. This is bad. It's possible
   the OS is doing something very wrong here, it's also possible we're
   trashing the semaphore before we hand it off to the OS. Using
   carbon semaphores seems to fix this problem.

8. Misaligned stack in arrange_return_to_lisp

9. Bogus decrement value for EBP in arrange_return_to_lisp, should have
   remained 8, not been set to 10.

2. Occasional Illegal Instruction Errors. These seem to be caused by
   the way were freeing the thread structs. If we queue the thread
   structs for later deletion, instead of having the next created
   thread delete the previously freed on, the problem seems to go
   away.

3. threads.impure.lisp and timer.impure.lisp fail. See 8 (fixed) and 9
   (fixed).

6. sb-threads/sb-lutex/x86-64/linux builds hang in the
   threads.impure.lisp. This suggests that, in addition to whatever
   platform specific problems we're seeing on Darwin, there may be
   some flaws in the lutex logic that need to be addressed.

10. Failure after handling a deferred(PA) signal. I think this is
    fixed.

11. Memory Corruption

4. Leaking semaphores? We don't use semaphores at the moment, so this
   is fixed.



====================================
Lutexes
====================================

[NJF to describe lutexes, with a pointer to the lutex API in the SBCL
internals documentation]

====================================
Semaphores
====================================

We have a number of options for semaphores: POSIX/BSD semaphores
(sem_wait and friends), Mach semaphores, and Carbon semaphores. The
problem with POSIX semaphores on Darwin is that sem_init is not
supported. The only way to create a semaphore is with sem_open, which
means named semaphores. This might not be horrible, but sounds
somewhat expensive. Mach semaphores have an API similar to the POSIX
semaphores and a semaphore_create routine that seems similar in spirit
to sem_init. These sound good, except that user programs aren't
supposed to call semaphore_create and semaphore_destroy for some
reason. Finally, this leaves Carbon semaphores, which appear to be a
thin veneer on top of the mach semaphores. The choice of which
semaphore type to use is a build-time option, with posix being the
default (WHICH DOESN'T WORK ON OS X!), and :mach-semaphores and
:carbon-semaphores specifying Mach or Carbon semaphores,
respectively. If we ever expect any support on semaphore problems from
Apple, we should use Carbon semaphores. If we want to maximize speed,
at the expense of violating Apple's do-not-use edict, we should use
Mach semaphores.

Currently, both Mach and Carbon semaphores exhibit similar problems at
the same place in the code in excuting threads.impure.lisp and
timer.impure.lisp.

====================================
Signalling
====================================

We added a new signal, SIG_RESUME_FROM_GC in hopes of getting better
behavior from Darwin's not-RT signalling mechanism. The non-darwin way
of doing things uses the same signal, STOP_STOP_FOR_GC to signal to
threads both that the should suspend and resume. First, a
SIG_STOP_FOR_GC is sent to the thread to tell it to suspend itself and
then a second SIG_STOP_FOR_GC is sent to telll the tread to begin
running again. The problem for Darwin is that, in the absence of POSIX
Real-Time (RT) threads, if we were handling the first SIG_STOP_FOR_GC
and the second signal was issued, the signal was being dropped on the
floor. We have now way of knowing when the signal handler finishes
running, so we can't know when it is safe to send the second
signal. Using another signal, SIG_RESUME_FROM_GC, causes the signal to
be queued and dispatched appropriately after the first handler
finishes.

====================================
Thread Local Storage
====================================

We use the %fs register for setting up segments for TLS, this allows
for much more efficient access of thread local variables than having
to use pthread_special everywhere.

Darwin supports %fs with the i386_set_ldt. We set this up in
arch_os_thread_cleanup, which is wrongly in bsd-os.c. This should get
moved to x86-bsd-os.c, but we'll save this for an arch-os cleanup at
some point.

The ldt gets freed in arch_os_thread_cleanup by setting the %fs to 0
and then setting the ldt to NULL. Make sure to set %fs to 0 here or
bad things happen on the way to destroying the thread!

====================================
Build Features
====================================

:mach-semaphores
:carbon-semaphores

Choose one on of :mach-semaphores or :carbon-semaphores. Choosing
neither gives you posix Semaphores which fail as Darwin doesn't have
sem_init. Note: we should be able to make this work with sem_open, but
haven't done so yet.

:restore-tls-segment-register-from-context

The :restore-tls-segment-register-from-context feature indicates that
we need to restore %fs from the signal handler context. On Linux, the
%fs register comes preloaded with the threads appropriate %fs value,
on Darwin we need to load it from the context. It's a reasonable
approach that Apple has taken here and other OSes may require this as
well, therefore it's a feature rather than an arch/os specific ifdef.

====================================
DEBUGGING NOTES
====================================

The two tests that stress threads, timer.impure.lisp and
threads.impure.lisp both fail.

1. threads.impure.lisp

this test currently fails in one of two ways

1A. sometimes we get a SIGILL
and the process terminates while trying to free a thread

2. timer.impure.lisp

this test fails with a segmentation violation:

/Entering RELEASE-MUTEX
/waking semaphore @ 0x601100, *semaphore=0x100004
/ TLS: restoring fs: 0x97 in memory_fault_handler
/MPSignalSemaphore said 0
Memory fault at: 0x10297d14, PC: 102d6613
/returning from interrupt_handle_now(14, info, context)
Stack pointer: 6a06668
heap WP violation? fault_addr=10297d14, page_index=663
0: (BACKTRACE 8 #<SYNONYM-STREAM :SYMBOL *TERMINAL-IO* {10143539}>)
/ TLS: restoring fs: 0x97 in memory_fault_handler
Memory fault at: 0x11d45598, PC: 102927a9
Stack pointer: 6a06668
heap WP violation? fault_addr=11d45598, page_index=7493
1: (ERROR "segmentation violation at #X~X")
2: ((FLET #:G188))
3: (SB-UNIX::SIGSEGV-HANDLER
    #<unused argument>
    #<unused argument>
    #.(SB-SYS:INT-SAP #X06A06C3A))
4: (SB-SYS:INVOKE-INTERRUPTION #<CLOSURE (LAMBDA #) {1243D0C5}>)
5: ("foreign function: call_into_lisp")
6: ("foreign function: funcall3")
7: ("foreign function: interrupt_handle_now")
/done coercing DATUM to CONDITION
/signalling CONDITION from within ERROR
/done signalling CONDITION within ERROR
unhandled SIMPLE-ERROR in thread #<SB-THREAD:THREAD {1243CD71}>:
  segmentation violation at #X7F2706A0

reducing the number of timer alarms in the timer streams test from 200
to 20 or so makes the situation better, but we still occasionally
fail, so there's some underlying problem we need to address.

====================================
OTHER RANDOM NOTES
====================================

1. Are we sure we're getting the stack alignment right deferred
   signals? Could this be causing a problem for us?

2. It's really too bad we can't step across an
   EXC_BAD_ACCESS. (radar:4480172, closed, duplicate, who knows what
   the non-duplicate bug number is)

3. I'm not sure I get why lutexes work at all. What is the problem
   that going to futexes (as opposed to just posix semaphores) solves
   in the first place? It seems as though all we have is a wrapper
   around posix sempahores. Is this good enough? Does it case
   performance problems? Does it cause correctness problems?


====================================
NOTES FROM SOLVED PROBLEMS
====================================


1B. if we make it through 1A we later catch a SIGSEGV:

interrupting child #<THREAD {1222A701}>
/WITH-MUTEX
/Entering RELEASE-MUTEX
/waking semaphore @ 0x3f8000, *semaphore=0x100080
/MPSignalSemaphore said 0
/ TLS: restoring fs: 0x1a7 in low_level_maybe_now_maybe_later
/maybe_defer_handler(5d42,29),thread=117460480: not deferred
/ TLS: restoring fs: 0x1a7 in low_level_interrupt_handle_now
/ TLS: restoring fs: 0x1a7 in interrupt_thread_handler
/arrange_return_to_lisp_function: preparing to go back
/WITH-MUTEX
/Entering RELEASE-MUTEX
/waking semaphore @ 0x3f8000, *semaphore=0x100080
/MPSignalSemaphore said 0
child pid #<THREAD {1222A701}>
/ TLS: restoring fs: 0x1a7 in interrupt_handle_now
/entering interrupt_handle_now(11, info, context)
/calling Lisp-level handler
/entering ERROR, argument list=..
0x1222cc5b
/cold-printing ERROR arguments one by one..
0x1222cc4f
/done cold-printing ERROR arguments
/entering INFINITE-ERROR-PROTECTOR, *CURRENT-ERROR-DEPTH*=..
0x00000000
/returning normally from INFINITE-ERROR-PROTECTOR
/back from INFINITE-ERROR-PROTECTOR
/in INFINITE-ERROR-PROTECT, incremented error depth
c/ TLS: restoring fs: 0x1a7 in memory_fault_handler
Memory fault at: 0x10012fac, PC: 10b8868b
Stack pointer: da12400
heap WP violation? fault_addr=10012fac, page_index=18
0: (BACKTRACE 8 #<SYNONYM-STREAM :SYMBOL *TERMINAL-IO* {10143539}>)
1: (ERROR "segmentation violation at #X~X")
2: ((FLET #:G188))
3: (SB-UNIX::SIGSEGV-HANDLER
    #<unused argument>
    #<unused argument>
    #.(SB-SYS:INT-SAP #X0DA12BFA))
4: (SB-SYS:INVOKE-INTERRUPTION #<CLOSURE (LAMBDA #) {1222C8AD}>)
5: ("foreign function: call_into_lisp")
6: ("foreign function: funcall3")
7: ("foreign function: interrupt_handle_now")
/done coercing DATUM to CONDITION
/signalling CONDITION from within ERROR
/done signalling CONDITION within ERROR
/ TLS: restoring fs: 0x1a7 in memory_fault_handler
Memory fault at: 0x100fbfd0, PC: 1048b8ed
Stack pointer: da12608
heap WP violation? fault_addr=100fbfd0, page_index=251
/ TLS: restoring fs: 0x1a7 in memory_fault_handler
Memory fault at: 0x10220758, PC: 1048b96e
Stack pointer: da12608
heap WP violation? fault_addr=10220758, page_index=544
/ TLS: restoring fs: 0x1a7 in memory_fault_handler
Memory fault at: 0x1021f778, PC: 1048b9f1
Stack pointer: da12608
heap WP violation? fault_addr=1021f778, page_index=543

debugger invoked on a SIMPLE-ERROR in thread #<THREAD {1222A701}>:
  segmentation violation at #X7F270DA1

The locking tests are failing. A mimimal-ish test case for this is:


(in-package sb-thread)

(defun test-interrupt (function-to-interrupt &optional quit-p)
  (let ((child  (make-thread function-to-interrupt)))
    ;;(format t "gdb ./src/runtime/sbcl ~A~%attach ~A~%" child child)
    (sleep 2)
    (format t "interrupting child ~A~%" child)
    (interrupt-thread child
                      (lambda ()
                        (format t "child pid ~A~%" *current-thread*)
                        (when quit-p (sb-ext:quit))))
    (sleep 1)
    child))

(progn
  (let ((child (test-interrupt (lambda () (loop)))))  (terminate-thread child))
  (let ((child (test-interrupt (lambda () (loop)))))  (terminate-thread child))
  (let ((child (test-interrupt (lambda () (loop)))))  (terminate-thread child))
  (let ((child (test-interrupt (lambda () (loop)))))  (terminate-thread child)))

This usually fails with a segmentation fault. Interstingy, if one
comments out the interrupt-thread form, things seem ok, so the problem
may lie within interrupt-thread. There was a major problem here before
which was that the stack that gets created in
arrange_return_to_lisp_function was not properly ABI-aligned (it was
not guaranteed to be on a 16-byte boundary). I have tried to fix
this in interrupt.c:arrange_return_to_lisp_function and in
x86-assem.S:post_signal_tramp, but it's possible that there are more
lurking bugs here, or, of course, that they're entirely
elsewhere. More investigation needed.

RESOLUTION: It turns out that the stack was not properly ABI-aligned
(16-bytes) and we were trying to build a fake stack frame for use by
the signal handling mechanism to return control to post_signal_tramp
which would then call function. Aligning the stack to 16-bytes made
things better, but there was still this SIGSEGV problem. I made the
mistake of bumping the amount by which we were decrementing EBP to 10
from 8, thinking this was the number, in words, by which we needed to
displace EBP. Turns out this is in fact bytes, and we wanted to stay
at 8 bytes. Leaving this at 8 fixes the SIGSEGV.


====================================
LUTEX CONDITION-WAIT/CONDITION-NOTIFY
====================================


jsnell> we need to use the pthread_mutex of the lutex of the mutex
        that's passed to sb-thread:condition-wait in lutex_wait and
        lutex_wake

jsnell> I think it doesn't need to be done for -notify, and the mutex
        manipulations in lutex_wake and lutex_wait can be removed. and
        the lutex condition-wait should just consist of calling to
        lutex_wait

slyrus> so we keep the cond_ calls in lutex_wait and _wake, but remove
        the mutex calls?

jsnell> hmm... though I haven't really thought of what should happen
        with mutex-value for lutexes

jsnell> no, obviously you need to pass the lutex of the queue to lutex_wake

jsnell> you need to pass the lutex of both queue and mutex and use
	pthread_cond_wait(queue_lutex->condition_variable,
	mutex_lutex->mutex)

jsnell> blech. after this, get-mutex will need to be changed too, to
        unconditionally call %lutex-lock, instead of trying to take
        the fast path with%instance-set-condit ional

jsnell> and the lutex condition-wait should then be something like
        (let ((old-value (mutex-value mutex)) (%lutex-wait ...) (setf
        (mutex-value mutex) old-value))), to ensure that the
        mutex-value slot is consistent with cond_wait
        releasing/acquiring the lock

Ok, all of this is in place, but we occasionally stil don't wake from waiting.

====================================
GC THREADS BUG
====================================

1) walking the registers in the context
2) figuring out if the point to dynamic space
3) getting the page
4) checking dont_move == 1?

On Darwin, the machine context does not contain the actual register
values, but rather a pointer to an i386_thread_state (or
ppc_thread_state on PPC) which contains the actual register
values. When scavenging the interrupt context, we need to make sure
that these values are preseved, instead of the values in the context
itself.
