#ifndef JEMALLOC_INTERNAL_MUTEX_H
#define JEMALLOC_INTERNAL_MUTEX_H

#include "jemalloc/internal/atomic.h"
#include "jemalloc/internal/mutex_prof.h"
#include "jemalloc/internal/tsd.h"
#include "jemalloc/internal/witness.h"

typedef enum {
	/* Can only acquire one mutex of a given witness rank at a time. */
	malloc_mutex_rank_exclusive,
	/*
	 * Can acquire multiple mutexes of the same witness rank, but in
	 * address-ascending order only.
	 */
	malloc_mutex_address_ordered
} malloc_mutex_lock_order_t;

typedef struct malloc_mutex_s malloc_mutex_t;
struct malloc_mutex_s {
	union {
		struct {
			/*
			 * prof_data is defined first to reduce cacheline
			 * bouncing: the data is not touched by the mutex holder
			 * during unlocking, while might be modified by
			 * contenders.  Having it before the mutex itself could
			 * avoid prefetching a modified cacheline (for the
			 * unlocking thread).
			 */
			mutex_prof_data_t	prof_data;
#ifdef _WIN32
#  if _WIN32_WINNT >= 0x0600
			SRWLOCK         	lock;
#  else
			CRITICAL_SECTION	lock;
#  endif
#elif (defined(JEMALLOC_OS_UNFAIR_LOCK))
			os_unfair_lock		lock;
#elif (defined(JEMALLOC_MUTEX_INIT_CB))
			pthread_mutex_t		lock;
			malloc_mutex_t		*postponed_next;
#else
			pthread_mutex_t		lock;
#endif
			/* 
			 * Hint flag to avoid exclusive cache line contention
			 * during spin waiting
			 */
			atomic_b_t		locked;
		};
		/*
		 * We only touch witness when configured w/ debug.  However we
		 * keep the field in a union when !debug so that we don't have
		 * to pollute the code base with #ifdefs, while avoid paying the
		 * memory cost.
		 */
#if !defined(JEMALLOC_DEBUG)
		witness_t			witness;
		malloc_mutex_lock_order_t	lock_order;
#endif
	};

#if defined(JEMALLOC_DEBUG)
	witness_t			witness;
	malloc_mutex_lock_order_t	lock_order;
#endif
};

/*
 * Based on benchmark results, a fixed spin with this amount of retries works
 * well for our critical sections.
 */
#define MALLOC_MUTEX_MAX_SPIN 250

#ifdef _WIN32
#  if _WIN32_WINNT >= 0x0600
#    define MALLOC_MUTEX_LOCK(m)    AcquireSRWLockExclusive(&(m)->lock)
#    define MALLOC_MUTEX_UNLOCK(m)  ReleaseSRWLockExclusive(&(m)->lock)
#    define MALLOC_MUTEX_TRYLOCK(m) (!TryAcquireSRWLockExclusive(&(m)->lock))
#  else
#    define MALLOC_MUTEX_LOCK(m)    EnterCriticalSection(&(m)->lock)
#    define MALLOC_MUTEX_UNLOCK(m)  LeaveCriticalSection(&(m)->lock)
#    define MALLOC_MUTEX_TRYLOCK(m) (!TryEnterCriticalSection(&(m)->lock))
#  endif
#elif (defined(JEMALLOC_OS_UNFAIR_LOCK))
#    define MALLOC_MUTEX_LOCK(m)    os_unfair_lock_lock(&(m)->lock)
#    define MALLOC_MUTEX_UNLOCK(m)  os_unfair_lock_unlock(&(m)->lock)
#    define MALLOC_MUTEX_TRYLOCK(m) (!os_unfair_lock_trylock(&(m)->lock))
#else
#    define MALLOC_MUTEX_LOCK(m)    pthread_mutex_lock(&(m)->lock)
#    define MALLOC_MUTEX_UNLOCK(m)  pthread_mutex_unlock(&(m)->lock)
#    define MALLOC_MUTEX_TRYLOCK(m) (pthread_mutex_trylock(&(m)->lock) != 0)
#endif

#define LOCK_PROF_DATA_INITIALIZER					\
    {NSTIME_ZERO_INITIALIZER, NSTIME_ZERO_INITIALIZER, 0, 0, 0,		\
	    ATOMIC_INIT(0), 0, NULL, 0}

#ifdef _WIN32
#  define MALLOC_MUTEX_INITIALIZER
#elif (defined(JEMALLOC_OS_UNFAIR_LOCK))
#  if defined(JEMALLOC_DEBUG)
#    define MALLOC_MUTEX_INITIALIZER					\
  {{{LOCK_PROF_DATA_INITIALIZER, OS_UNFAIR_LOCK_INIT, ATOMIC_INIT(false)}}, \
         WITNESS_INITIALIZER("mutex", WITNESS_RANK_OMIT), 0}
#  else
#    define MALLOC_MUTEX_INITIALIZER                      \
  {{{LOCK_PROF_DATA_INITIALIZER, OS_UNFAIR_LOCK_INIT, ATOMIC_INIT(false)}},  \
      WITNESS_INITIALIZER("mutex", WITNESS_RANK_OMIT)}
#  endif
#elif (defined(JEMALLOC_MUTEX_INIT_CB))
#  if (defined(JEMALLOC_DEBUG))
#     define MALLOC_MUTEX_INITIALIZER					\
      {{{LOCK_PROF_DATA_INITIALIZER, PTHREAD_MUTEX_INITIALIZER, NULL, ATOMIC_INIT(false)}},	\
           WITNESS_INITIALIZER("mutex", WITNESS_RANK_OMIT), 0}
#  else
#     define MALLOC_MUTEX_INITIALIZER					\
      {{{LOCK_PROF_DATA_INITIALIZER, PTHREAD_MUTEX_INITIALIZER, NULL, ATOMIC_INIT(false)}},	\
           WITNESS_INITIALIZER("mutex", WITNESS_RANK_OMIT)}
#  endif

#else
#    define MALLOC_MUTEX_TYPE PTHREAD_MUTEX_DEFAULT
#  if defined(JEMALLOC_DEBUG)
#    define MALLOC_MUTEX_INITIALIZER					\
     {{{LOCK_PROF_DATA_INITIALIZER, PTHREAD_MUTEX_INITIALIZER, ATOMIC_INIT(false)}}, \
           WITNESS_INITIALIZER("mutex", WITNESS_RANK_OMIT), 0}
#  else
#    define MALLOC_MUTEX_INITIALIZER                          \
     {{{LOCK_PROF_DATA_INITIALIZER, PTHREAD_MUTEX_INITIALIZER, ATOMIC_INIT(false)}},	\
      WITNESS_INITIALIZER("mutex", WITNESS_RANK_OMIT)}
#  endif
#endif

#ifdef JEMALLOC_LAZY_LOCK
extern bool isthreaded;
#else
#  undef isthreaded /* Undo private_namespace.h definition. */
#  define isthreaded true
#endif

bool malloc_mutex_init(malloc_mutex_t *mutex, const char *name,
    witness_rank_t rank, malloc_mutex_lock_order_t lock_order);
void malloc_mutex_prefork(tsdn_t *tsdn, malloc_mutex_t *mutex);
void malloc_mutex_postfork_parent(tsdn_t *tsdn, malloc_mutex_t *mutex);
void malloc_mutex_postfork_child(tsdn_t *tsdn, malloc_mutex_t *mutex);
bool malloc_mutex_boot(void);
void malloc_mutex_prof_data_reset(tsdn_t *tsdn, malloc_mutex_t *mutex);

void malloc_mutex_lock_slow(malloc_mutex_t *mutex);

static inline void
malloc_mutex_lock_final(malloc_mutex_t *mutex) {
	MALLOC_MUTEX_LOCK(mutex);
	atomic_store_b(&mutex->locked, true, ATOMIC_RELAXED);
}

static inline bool
malloc_mutex_trylock_final(malloc_mutex_t *mutex) {
	return MALLOC_MUTEX_TRYLOCK(mutex);
}

static inline void
mutex_owner_stats_update(tsdn_t *tsdn, malloc_mutex_t *mutex) {
	if (config_stats) {
		mutex_prof_data_t *data = &mutex->prof_data;
		data->n_lock_ops++;
		if (data->prev_owner != tsdn) {
			data->prev_owner = tsdn;
			data->n_owner_switches++;
		}
	}
}

/* Trylock: return false if the lock is successfully acquired. */
static inline bool
malloc_mutex_trylock(tsdn_t *tsdn, malloc_mutex_t *mutex) {
	witness_assert_not_owner(tsdn_witness_tsdp_get(tsdn), &mutex->witness);
	if (isthreaded) {
		if (malloc_mutex_trylock_final(mutex)) {
			atomic_store_b(&mutex->locked, true, ATOMIC_RELAXED);
			return true;
		}
		mutex_owner_stats_update(tsdn, mutex);
	}
	witness_lock(tsdn_witness_tsdp_get(tsdn), &mutex->witness);

	return false;
}

/* Aggregate lock prof data. */
static inline void
malloc_mutex_prof_merge(mutex_prof_data_t *sum, mutex_prof_data_t *data) {
	nstime_add(&sum->tot_wait_time, &data->tot_wait_time);
	if (nstime_compare(&sum->max_wait_time, &data->max_wait_time) < 0) {
		nstime_copy(&sum->max_wait_time, &data->max_wait_time);
	}

	sum->n_wait_times += data->n_wait_times;
	sum->n_spin_acquired += data->n_spin_acquired;

	if (sum->max_n_thds < data->max_n_thds) {
		sum->max_n_thds = data->max_n_thds;
	}
	uint32_t cur_n_waiting_thds = atomic_load_u32(&sum->n_waiting_thds,
	    ATOMIC_RELAXED);
	uint32_t new_n_waiting_thds = cur_n_waiting_thds + atomic_load_u32(
	    &data->n_waiting_thds, ATOMIC_RELAXED);
	atomic_store_u32(&sum->n_waiting_thds, new_n_waiting_thds,
	    ATOMIC_RELAXED);
	sum->n_owner_switches += data->n_owner_switches;
	sum->n_lock_ops += data->n_lock_ops;
}

static inline void
malloc_mutex_lock(tsdn_t *tsdn, malloc_mutex_t *mutex) {
	witness_assert_not_owner(tsdn_witness_tsdp_get(tsdn), &mutex->witness);
	if (isthreaded) {
		if (malloc_mutex_trylock_final(mutex)) {
			malloc_mutex_lock_slow(mutex);
			atomic_store_b(&mutex->locked, true, ATOMIC_RELAXED);
		}
		mutex_owner_stats_update(tsdn, mutex);
	}
	witness_lock(tsdn_witness_tsdp_get(tsdn), &mutex->witness);
}

static inline void
malloc_mutex_unlock(tsdn_t *tsdn, malloc_mutex_t *mutex) {
	atomic_store_b(&mutex->locked, false, ATOMIC_RELAXED);
	witness_unlock(tsdn_witness_tsdp_get(tsdn), &mutex->witness);
	if (isthreaded) {
		MALLOC_MUTEX_UNLOCK(mutex);
	}
}

static inline void
malloc_mutex_assert_owner(tsdn_t *tsdn, malloc_mutex_t *mutex) {
	witness_assert_owner(tsdn_witness_tsdp_get(tsdn), &mutex->witness);
}

static inline void
malloc_mutex_assert_not_owner(tsdn_t *tsdn, malloc_mutex_t *mutex) {
	witness_assert_not_owner(tsdn_witness_tsdp_get(tsdn), &mutex->witness);
}

/* Copy the prof data from mutex for processing. */
static inline void
malloc_mutex_prof_read(tsdn_t *tsdn, mutex_prof_data_t *data,
    malloc_mutex_t *mutex) {
	mutex_prof_data_t *source = &mutex->prof_data;
	/* Can only read holding the mutex. */
	malloc_mutex_assert_owner(tsdn, mutex);

	/*
	 * Not *really* allowed (we shouldn't be doing non-atomic loads of
	 * atomic data), but the mutex protection makes this safe, and writing
	 * a member-for-member copy is tedious for this situation.
	 */
	*data = *source;
	/* n_wait_thds is not reported (modified w/o locking). */
	atomic_store_u32(&data->n_waiting_thds, 0, ATOMIC_RELAXED);
}

static inline void
malloc_mutex_prof_accum(tsdn_t *tsdn, mutex_prof_data_t *data,
    malloc_mutex_t *mutex) {
	mutex_prof_data_t *source = &mutex->prof_data;
	/* Can only read holding the mutex. */
	malloc_mutex_assert_owner(tsdn, mutex);

	nstime_add(&data->tot_wait_time, &source->tot_wait_time);
	if (nstime_compare(&source->max_wait_time, &data->max_wait_time) > 0) {
		nstime_copy(&data->max_wait_time, &source->max_wait_time);
	}
	data->n_wait_times += source->n_wait_times;
	data->n_spin_acquired += source->n_spin_acquired;
	if (data->max_n_thds < source->max_n_thds) {
		data->max_n_thds = source->max_n_thds;
	}
	/* n_wait_thds is not reported. */
	atomic_store_u32(&data->n_waiting_thds, 0, ATOMIC_RELAXED);
	data->n_owner_switches += source->n_owner_switches;
	data->n_lock_ops += source->n_lock_ops;
}

#endif /* JEMALLOC_INTERNAL_MUTEX_H */