+/* Planned state progressions:
+ *
+ * none -> flight:
+ *
+ * unmap_gc_page(). No blockers (GC_NONE can be left at any * moment).
+ *
+ * flight -> message:
+ *
+ * happens when a master thread enters its trap.
+ *
+ * The only blocker for flight mode is the master thread itself
+ * (GC_FLIGHT can't be left until the master thread traps).
+ *
+ * message -> invoked:
+ *
+ * happens after each (other) thread is notified, i.e. it will
+ * eventually stop (already stopped). map_gc_page().
+ *
+ * Each thread with empty CSP disagrees to leave GC_MESSAGE phase.
+ *
+ * invoked -> collect:
+ *
+ * happens when every gc-inhibitor comes to completion (that's
+ * normally pending interrupt trap).
+ *
+ * NB gc_stop_the_world, if it happens in non-master thread, "takes
+ * over" as a master, also deregistering itself as a blocker
+ * (i.e. it's ready to leave GC_INVOKED, but now it objects to
+ * leaving GC_COLLECT; this "usurpation" doesn't require any change
+ * to GC_COLLECT counter: for the counter, it's immaterial _which_
+ * thread is waiting).
+ *
+ * collect -> none:
+ *
+ * happens at gc_start_the_world (that should always happen in the
+ * master).
+ *
+ * Any thread waiting until GC end now continues.
+ */
+struct gc_state {
+ /* Flag: conditions are initialized */
+ boolean initialized;
+
+ /* Per-process lock for gc_state */
+ pthread_mutex_t lock;
+
+ /* Conditions: one per phase */
+ pthread_cond_t phase_cond[GC_NPHASES];
+
+ /* For each [current or future] phase, a number of threads not yet ready to
+ * leave it */
+ int phase_wait[GC_NPHASES];
+
+ /* Master thread controlling the topmost stop/gc/start sequence */
+ struct thread* master;
+ struct thread* collector;
+
+ /* Current GC phase */
+ gc_phase_t phase;
+};
+
+static struct gc_state gc_state = {
+ .lock = PTHREAD_MUTEX_INITIALIZER,
+ .phase = GC_NONE,
+};
+
+void
+gc_state_lock()
+{
+ odxprint(safepoints,"GC state [%p] to be locked",gc_state.lock);
+ gc_assert(0==pthread_mutex_lock(&gc_state.lock));
+ if (gc_state.master) {
+ fprintf(stderr,"GC state lock glitch [%p] in thread %p phase %d\n",
+ gc_state.master,arch_os_get_current_thread(),gc_state.phase);
+ odxprint(safepoints,"GC state lock glitch [%p]",gc_state.master);
+ }
+ gc_assert(!gc_state.master);
+ gc_state.master = arch_os_get_current_thread();
+ if (!gc_state.initialized) {
+ int i;
+ for (i=GC_NONE; i<GC_NPHASES; ++i)
+ pthread_cond_init(&gc_state.phase_cond[i],NULL);
+ gc_state.initialized = 1;
+ }
+ odxprint(safepoints,"GC state [%p] locked in phase %d",gc_state.lock, gc_state.phase);
+}
+
+void
+gc_state_unlock()
+{
+ odxprint(safepoints,"GC state to be unlocked in phase %d",gc_state.phase);
+ gc_assert(arch_os_get_current_thread()==gc_state.master);
+ gc_state.master = NULL;
+ gc_assert(0==pthread_mutex_unlock(&gc_state.lock));
+ odxprint(safepoints,"%s","GC state unlocked");
+}
+
+void
+gc_state_wait(gc_phase_t phase)
+{
+ struct thread* self = arch_os_get_current_thread();
+ odxprint(safepoints,"Waiting for %d -> %d [%d holders]",
+ gc_state.phase,phase,gc_state.phase_wait[gc_state.phase]);
+ gc_assert(gc_state.master == self);
+ gc_state.master = NULL;
+ while(gc_state.phase != phase && !(phase == GC_QUIET && (gc_state.phase > GC_QUIET)))
+ pthread_cond_wait(&gc_state.phase_cond[phase],&gc_state.lock);
+ gc_assert(gc_state.master == NULL);
+ gc_state.master = self;
+}
+
+static void
+set_csp_from_context(struct thread *self, os_context_t *ctx)
+{
+ void **sp = (void **) *os_context_register_addr(ctx, reg_SP);
+ /* On POSIX platforms, it is sufficient to investigate only the part
+ * of the stack that was live before the interrupt, because in
+ * addition, we consider interrupt contexts explicitly. On Windows,
+ * however, we do not keep an explicit stack of exception contexts,
+ * and instead arrange for the conservative stack scan to also cover
+ * the context implicitly. The obvious way to do that is to start
+ * at the context itself: */
+#ifdef LISP_FEATURE_WIN32
+ gc_assert((void **) ctx < sp);
+ sp = (void**) ctx;
+#endif
+ gc_assert((void **)self->control_stack_start
+ <= sp && sp
+ < (void **)self->control_stack_end);
+ *self->csp_around_foreign_call = (lispobj) sp;
+}
+
+\f
+static inline gc_phase_t gc_phase_next(gc_phase_t old) {
+ return (old+1) % GC_NPHASES;
+}
+
+static inline gc_phase_t thread_gc_phase(struct thread* p)
+{
+ boolean inhibit = (SymbolTlValue(GC_INHIBIT,p)==T)||
+ (SymbolTlValue(IN_WITHOUT_GCING,p)==IN_WITHOUT_GCING);
+
+ boolean inprogress =
+ (SymbolTlValue(GC_PENDING,p)!=T&& SymbolTlValue(GC_PENDING,p)!=NIL);
+
+ return
+ inprogress ? (gc_state.collector && (gc_state.collector != p)
+ ? GC_NONE : GC_QUIET)
+ : (inhibit ? GC_INVOKED : GC_NONE);
+}
+
+static inline void thread_gc_promote(struct thread* p, gc_phase_t cur, gc_phase_t old) {
+ if (old != GC_NONE)
+ gc_state.phase_wait[old]--;
+ if (cur != GC_NONE) {
+ gc_state.phase_wait[cur]++;
+ }
+ if (cur != GC_NONE)
+ SetTlSymbolValue(STOP_FOR_GC_PENDING,T,p);
+}
+
+/* set_thread_csp_access -- alter page permissions for not-in-Lisp
+ flag (Lisp Stack Top) of the thread `p'. The flag may be modified
+ if `writable' is true.
+
+ Return true if there is a non-null value in the flag.
+
+ When a thread enters C code or leaves it, a per-thread location is
+ modified. That machine word serves as a not-in-Lisp flag; for
+ convenience, when in C, it's filled with a topmost stack location
+ that may contain Lisp data. When thread is in Lisp, the word
+ contains NULL.
+
+ GENCGC uses each thread's flag value for conservative garbage collection.
+
+ There is a full VM page reserved for this word; page permissions
+ are switched to read-only for race-free examine + wait + use
+ scenarios. */
+static inline boolean
+set_thread_csp_access(struct thread* p, boolean writable)
+{
+ os_protect((os_vm_address_t) p->csp_around_foreign_call,
+ THREAD_CSP_PAGE_SIZE,
+ writable? (OS_VM_PROT_READ|OS_VM_PROT_WRITE)
+ : (OS_VM_PROT_READ));
+ return !!*p->csp_around_foreign_call;
+}
+
+static inline void gc_notify_early()
+{
+ struct thread *self = arch_os_get_current_thread(), *p;
+ odxprint(safepoints,"%s","global notification");
+ pthread_mutex_lock(&all_threads_lock);
+ for_each_thread(p) {
+ if (p==self)
+ continue;
+ odxprint(safepoints,"notifying thread %p csp %p",p,*p->csp_around_foreign_call);
+ if (!set_thread_csp_access(p,0)) {
+ thread_gc_promote(p, gc_state.phase, GC_NONE);
+ } else {
+ thread_gc_promote(p, thread_gc_phase(p), GC_NONE);
+ }
+ }
+ pthread_mutex_unlock(&all_threads_lock);
+}
+
+static inline void gc_notify_final()
+{
+ struct thread *p;
+ odxprint(safepoints,"%s","global notification");
+ gc_state.phase_wait[gc_state.phase]=0;
+ pthread_mutex_lock(&all_threads_lock);
+ for_each_thread(p) {
+ if (p == gc_state.collector)
+ continue;
+ odxprint(safepoints,"notifying thread %p csp %p",p,*p->csp_around_foreign_call);
+ if (!set_thread_csp_access(p,0)) {
+ thread_gc_promote(p, gc_state.phase, GC_NONE);
+ }
+ }
+ pthread_mutex_unlock(&all_threads_lock);
+}
+
+static inline void gc_done()
+{
+ struct thread *self = arch_os_get_current_thread(), *p;
+ boolean inhibit = (SymbolTlValue(GC_INHIBIT,self)==T);
+
+ odxprint(safepoints,"%s","global denotification");
+ pthread_mutex_lock(&all_threads_lock);
+ for_each_thread(p) {
+ if (inhibit && (SymbolTlValue(GC_PENDING,p)==T))
+ SetTlSymbolValue(GC_PENDING,NIL,p);
+ set_thread_csp_access(p,1);
+ }
+ pthread_mutex_unlock(&all_threads_lock);
+}
+
+static inline void gc_handle_phase()
+{
+ odxprint(safepoints,"Entering phase %d",gc_state.phase);
+ switch (gc_state.phase) {
+ case GC_FLIGHT:
+ unmap_gc_page();
+ break;
+ case GC_MESSAGE:
+ gc_notify_early();
+ break;
+ case GC_INVOKED:
+ map_gc_page();
+ break;
+ case GC_SETTLED:
+ gc_notify_final();
+ unmap_gc_page();
+ break;
+ case GC_COLLECT:
+ map_gc_page();
+ break;
+ case GC_NONE:
+ gc_done();
+ break;
+ default:
+ break;
+ }
+}
+
+
+/* become ready to leave the <old> phase, but unready to leave the <new> phase;
+ * `old' can be GC_NONE, it means this thread weren't blocking any state. `cur'
+ * can be GC_NONE, it means this thread wouldn't block GC_NONE, but still wait
+ * for it. */
+static inline void gc_advance(gc_phase_t cur, gc_phase_t old) {
+ odxprint(safepoints,"GC advance request %d -> %d in phase %d",old,cur,gc_state.phase);
+ if (cur == old)
+ return;
+ if (cur == gc_state.phase)
+ return;
+ if (old < gc_state.phase)
+ old = GC_NONE;
+ if (old != GC_NONE) {
+ gc_state.phase_wait[old]--;
+ odxprint(safepoints,"%d holders of phase %d without me",gc_state.phase_wait[old],old);
+ }
+ if (cur != GC_NONE) {
+ gc_state.phase_wait[cur]++;
+ odxprint(safepoints,"%d holders of phase %d with me",gc_state.phase_wait[cur],cur);
+ }
+ /* roll forth as long as there's no waiters */
+ while (gc_state.phase_wait[gc_state.phase]==0
+ && gc_state.phase != cur) {
+ gc_state.phase = gc_phase_next(gc_state.phase);
+ odxprint(safepoints,"no blockers, direct advance to %d",gc_state.phase);
+ gc_handle_phase();
+ pthread_cond_broadcast(&gc_state.phase_cond[gc_state.phase]);
+ }
+ odxprint(safepoints,"going to wait for %d threads",gc_state.phase_wait[gc_state.phase]);
+ gc_state_wait(cur);
+}
+
+void
+thread_register_gc_trigger()
+{
+ odxprint(misc, "/thread_register_gc_trigger");
+ struct thread *self = arch_os_get_current_thread();
+ gc_state_lock();
+ if (gc_state.phase == GC_NONE &&
+ SymbolTlValue(IN_SAFEPOINT,self)!=T &&
+ thread_gc_phase(self)==GC_NONE) {
+ gc_advance(GC_FLIGHT,GC_NONE);
+ }
+ gc_state_unlock();
+}
+