/*
 * Implementation of the Global Interpreter Lock (GIL).
 */

#include <stdlib.h>
#include <errno.h>

#include "pycore_atomic.h"


/*
 Notes about the implementation:

 - The GIL is just a boolean variable (locked) whose access is protected
 by a mutex (gil_mutex), and whose changes are signalled by a condition
 variable (gil_cond). gil_mutex is taken for short periods of time,
 and therefore mostly uncontended.

 - In the GIL-holding thread, the main loop (PyEval_EvalFrameEx) must be
 able to release the GIL on demand by another thread. A volatile boolean
 variable (gil_drop_request) is used for that purpose, which is checked
 at every turn of the eval loop. That variable is set after a wait of
 `interval` microseconds on `gil_cond` has timed out.

 [Actually, another volatile boolean variable (eval_breaker) is used
 which ORs several conditions into one. Volatile booleans are
 sufficient as inter-thread signalling means since Python is run
 on cache-coherent architectures only.]

 - A thread wanting to take the GIL will first let pass a given amount of
 time (`interval` microseconds) before setting gil_drop_request. This
 encourages a defined switching period, but doesn't enforce it since
 opcodes can take an arbitrary time to execute.

 The `interval` value is available for the user to read and modify
 using the Python API `sys.{get,set}switchinterval()`.

 - When a thread releases the GIL and gil_drop_request is set, that thread
 ensures that another GIL-awaiting thread gets scheduled.
 It does so by waiting on a condition variable (switch_cond) until
 the value of last_holder is changed to something else than its
 own thread state pointer, indicating that another thread was able to
 take the GIL.

 This is meant to prohibit the latency-adverse behaviour on multi-core
 machines where one thread would speculatively release the GIL, but still
 run and end up being the first to re-acquire it, making the "timeslices"
 much longer than expected.
 (Note: this mechanism is enabled with FORCE_SWITCHING above)
*/

#include "condvar.h"

#define MUTEX_INIT(mut) \
 if (PyMUTEX_INIT(&(mut))) { \
 Py_FatalError("PyMUTEX_INIT(" #mut ") failed"); };
#define MUTEX_FINI(mut) \
 if (PyMUTEX_FINI(&(mut))) { \
 Py_FatalError("PyMUTEX_FINI(" #mut ") failed"); };
#define MUTEX_LOCK_CC(mut) \
 if (PyMUTEX_LOCK(&(mut))) { \
 Py_FatalError("PyMUTEX_LOCK(" #mut ") failed"); };
#define MUTEX_UNLOCK(mut) \
 if (PyMUTEX_UNLOCK(&(mut))) { \
 Py_FatalError("PyMUTEX_UNLOCK(" #mut ") failed"); };

#define COND_INIT(cond) \
 if (PyCOND_INIT(&(cond))) { \
 Py_FatalError("PyCOND_INIT(" #cond ") failed"); };
#define COND_FINI(cond) \
 if (PyCOND_FINI(&(cond))) { \
 Py_FatalError("PyCOND_FINI(" #cond ") failed"); };
#define COND_SIGNAL(cond) \
 if (PyCOND_SIGNAL(&(cond))) { \
 Py_FatalError("PyCOND_SIGNAL(" #cond ") failed"); };
#define COND_WAIT(cond, mut) \
 if (PyCOND_WAIT(&(cond), &(mut))) { \
 Py_FatalError("PyCOND_WAIT(" #cond ") failed"); };
#define COND_TIMED_WAIT(cond, mut, microseconds, timeout_result) \
 { \
 int r = PyCOND_TIMEDWAIT(&(cond), &(mut), (microseconds)); \
 if (r < 0) \
 Py_FatalError("PyCOND_WAIT(" #cond ") failed"); \
 if (r) /* 1 == timeout, 2 == impl. can't say, so assume timeout */ \
 timeout_result = 1; \
 else \
 timeout_result = 0; \
 } \


#define DEFAULT_INTERVAL 5000

static void _gil_initialize(struct _gil_runtime_state *gil)
{
 _Py_atomic_int uninitialized = {-1};
 gil->locked = uninitialized;
 gil->interval = DEFAULT_INTERVAL;
}

static int gil_created(struct _gil_runtime_state *gil)
{
 return (_Py_atomic_load_explicit(&gil->locked, _Py_memory_order_acquire) >= 0);
}

static void create_gil(struct _gil_runtime_state *gil)
{
 MUTEX_INIT(gil->mutex);
#ifdef FORCE_SWITCHING
 MUTEX_INIT(gil->switch_mutex);
#endif
 COND_INIT(gil->cond);
#ifdef FORCE_SWITCHING
 COND_INIT(gil->switch_cond);
#endif
 _Py_atomic_store_relaxed(&gil->last_holder, 0);
 _Py_ANNOTATE_RWLOCK_CREATE(&gil->locked);
 _Py_atomic_store_explicit(&gil->locked, 0, _Py_memory_order_release);
}

static void destroy_gil(struct _gil_runtime_state *gil)
{
 /* some pthread-like implementations tie the mutex to the cond
 * and must have the cond destroyed first.
 */
 COND_FINI(gil->cond);
 MUTEX_FINI(gil->mutex);
#ifdef FORCE_SWITCHING
 COND_FINI(gil->switch_cond);
 MUTEX_FINI(gil->switch_mutex);
#endif
 _Py_atomic_store_explicit(&gil->locked, -1,
 _Py_memory_order_release);
 _Py_ANNOTATE_RWLOCK_DESTROY(&gil->locked);
}

static void recreate_gil(struct _gil_runtime_state *gil)
{
 _Py_ANNOTATE_RWLOCK_DESTROY(&gil->locked);
 /* XXX should we destroy the old OS resources here? */
 create_gil(gil);
}

static void
drop_gil(struct _ceval_runtime_state *ceval, PyThreadState *tstate)
{
 struct _gil_runtime_state *gil = &ceval->gil;
 if (!_Py_atomic_load_relaxed(&gil->locked)) {
 Py_FatalError("drop_gil: GIL is not locked");
 }

 /* tstate is allowed to be NULL (early interpreter init) */
 if (tstate != NULL) {
 /* Sub-interpreter support: threads might have been switched
 under our feet using PyThreadState_Swap(). Fix the GIL last
 holder variable so that our heuristics work. */
 _Py_atomic_store_relaxed(&gil->last_holder, (uintptr_t)tstate);
 }

 MUTEX_LOCK_CC(gil->mutex);
 _Py_ANNOTATE_RWLOCK_RELEASED(&gil->locked, /*is_write=*/1);
 _Py_atomic_store_relaxed(&gil->locked, 0);
 COND_SIGNAL(gil->cond);
 MUTEX_UNLOCK(gil->mutex);

#ifdef FORCE_SWITCHING
 if (_Py_atomic_load_relaxed(&ceval->gil_drop_request) && tstate != NULL) {
 MUTEX_LOCK_CC(gil->switch_mutex);
 /* Not switched yet => wait */
 if (((PyThreadState*)_Py_atomic_load_relaxed(&gil->last_holder)) == tstate)
 {
 RESET_GIL_DROP_REQUEST(ceval);
 /* NOTE: if COND_WAIT does not atomically start waiting when
 releasing the mutex, another thread can run through, take
 the GIL and drop it again, and reset the condition
 before we even had a chance to wait for it. */
 COND_WAIT(gil->switch_cond, gil->switch_mutex);
 }
 MUTEX_UNLOCK(gil->switch_mutex);
 }
#endif
}

static void
take_gil(struct _ceval_runtime_state *ceval, PyThreadState *tstate)
{
 if (tstate == NULL) {
 Py_FatalError("take_gil: NULL tstate");
 }

 struct _gil_runtime_state *gil = &ceval->gil;
 int err = errno;
 MUTEX_LOCK_CC(gil->mutex);

 if (!_Py_atomic_load_relaxed(&gil->locked)) {
 goto _ready;
 }

 while (_Py_atomic_load_relaxed(&gil->locked)) {
 int timed_out = 0;
 unsigned long saved_switchnum;

 saved_switchnum = gil->switch_number;


 unsigned long interval = (gil->interval >= 1 ? gil->interval : 1);
 COND_TIMED_WAIT(gil->cond, gil->mutex, interval, timed_out);
 /* If we timed out and no switch occurred in the meantime, it is time
 to ask the GIL-holding thread to drop it. */
 if (timed_out &&
 _Py_atomic_load_relaxed(&gil->locked) &&
 gil->switch_number == saved_switchnum)
 {
 SET_GIL_DROP_REQUEST(ceval);
 }
 }
_ready:
#ifdef FORCE_SWITCHING
 /* This mutex must be taken before modifying gil->last_holder:
 see drop_gil(). */
 MUTEX_LOCK_CC(gil->switch_mutex);
#endif
 /* We now hold the GIL */
 _Py_atomic_store_relaxed(&gil->locked, 1);
 _Py_ANNOTATE_RWLOCK_ACQUIRED(&gil->locked, /*is_write=*/1);

 if (tstate != (PyThreadState*)_Py_atomic_load_relaxed(&gil->last_holder)) {
 _Py_atomic_store_relaxed(&gil->last_holder, (uintptr_t)tstate);
 ++gil->switch_number;
 }

#ifdef FORCE_SWITCHING
 COND_SIGNAL(gil->switch_cond);
 MUTEX_UNLOCK(gil->switch_mutex);
#endif
 if (_Py_atomic_load_relaxed(&ceval->gil_drop_request)) {
 RESET_GIL_DROP_REQUEST(ceval);
 }
 if (tstate->async_exc != NULL) {
 _PyEval_SignalAsyncExc(ceval);
 }

 MUTEX_UNLOCK(gil->mutex);
 errno = err;
}

void _PyEval_SetSwitchInterval(unsigned long microseconds)
{
 _PyRuntime.ceval.gil.interval = microseconds;
}

unsigned long _PyEval_GetSwitchInterval()
{
 return _PyRuntime.ceval.gil.interval;
}