text: // SPDX-FileCopyrightText: Copyright (c) 2018-2019 Virginia Tech
  // SPDX-License-Identifier: Apache-2.0
  #ifndef __KERNEL__
  #include "mvrlu.h"
  #else
  #include <linux/mvrlu.h>
  #endif
  
  #include "mvrlu_i.h"
  #include "debug.h"
  #include "port.h"
  
  /*
   * Global data structures
   */
  static mvrlu_thread_list_t g_live_threads ____cacheline_aligned2;
  static mvrlu_thread_list_t g_zombie_threads ____cacheline_aligned2;
  static mvrlu_qp_thread_t g_qp_thread ____cacheline_aligned2;
  
  #ifdef MVRLU_ENABLE_STATS
  static mvrlu_stat_t g_stat ____cacheline_aligned2;
  #endif
  
  /*
   * Forward declarations
   */
  
  static void qp_update_qp_clk_for_reclaim(mvrlu_qp_thread_t *qp_thread,
  					 mvrlu_thread_struct_t *thread);
  static int wakeup_qp_thread_for_reclaim(void);
  static void print_config(void);
  
  /*
   * Clock-related functions
   */
  
  #ifndef MVRLU_ORDO_TIMESTAMPING
  static volatile unsigned long
  	__g_wrt_clk[2 * CACHE_DEFAULT_PADDING] ____cacheline_aligned2;
  #define g_wrt_clk __g_wrt_clk[CACHE_DEFAULT_PADDING]
  #define gte_clock(__t1, __t2) ((__t1) >= (__t2))
  #define lte_clock(__t1, __t2) ((__t1) <= (__t2))
  #define get_clock() g_wrt_clk
  #define get_clock_relaxed() get_clock()
  #define init_clock()                                                           \
  	do {                                                                   \
  		g_wrt_clk = 0;                                                 \
  	} while (0)
  #define new_clock(__x) (g_wrt_clk + 1)
  #define advance_clock() smp_faa(&g_wrt_clk, 1)
  #define correct_qp_clk(qp_clk) qp_clk
  #else /* MVRLU_ORDO_TIMESTAMPING */
  #include "ordo_clock.h"
  #define gte_clock(__t1, __t2) ordo_gt_clock(__t1, __t2)
  #define lte_clock(__t1, __t2) ordo_lt_clock(__t1, __t2)
  #define get_clock() ordo_get_clock()
  #define get_clock_relaxed() ordo_get_clock_relaxed()
  #define init_clock() ordo_clock_init()
  #define new_clock(__local_clk) ordo_new_clock((__local_clk) + ordo_boundary())
  #define advance_clock()
  #define correct_qp_clk(qp_clk) qp_clk - ordo_boundary()
  #endif /* MVRLU_ORDO_TIMESTAMPING */
  
  /*
   * Utility functions
   */
  
  #define log_to_thread(__log)                                                   \
  	({                                                                     \
  		void *p = (void *)(__log);                                     \
  		void *q;                                                       \
  		q = p - ((size_t) & ((mvrlu_thread_struct_t *)0)->log);        \
  		(mvrlu_thread_struct_t *)q;                                    \
  	})
  
  #define list_to_thread(__list)                                                 \
  	({                                                                     \
  		void *p = (void *)(__list);                                    \
  		void *q;                                                       \
  		q = p - ((size_t) & ((mvrlu_thread_struct_t *)0)->list);       \
  		(mvrlu_thread_struct_t *)q;                                    \
  	})
  
  #define chs_to_thread(__chs)                                                   \
  	({                                                                     \
  		void *p = (void *)(__chs)->cpy_hdr.p_wrt_clk;                  \
  		void *q;                                                       \
  		q = p - ((size_t) & ((mvrlu_wrt_set_t *)0)->wrt_clk);          \
  		((mvrlu_wrt_set_t *)q)->thread;                                \
  	})
  
  static inline void assert_chs_type(const mvrlu_cpy_hdr_struct_t *chs)
  {
  	mvrlu_assert(chs->obj_hdr.type == TYPE_WRT_SET ||
  		     chs->obj_hdr.type == TYPE_COPY ||
  		     chs->obj_hdr.type == TYPE_FREE ||
  		     chs->obj_hdr.type == TYPE_BOGUS);
  }
  
  /*
   * Statistics functions
   */
  
  #ifdef MVRLU_ENABLE_STATS
  #define stat_thread_inc(self, x) stat_inc(&(self)->stat, stat_##x)
  #define stat_thread_acc(self, x, y) stat_acc(&(self)->stat, stat_##x, y)
  #define stat_thread_max(self, x, y) stat_max(&(self)->stat, stat_##x, y)
  #define stat_qp_inc(qp, x) stat_inc(&(qp)->stat, stat_##x)
  #define stat_qp_acc(qp, x, y) stat_acc(&(qp)->stat, stat_##x, y)
  #define stat_qp_max(qp, x, y) stat_max(&(qp)->stat, stat_##x, y)
  #define stat_log_inc(log, x) stat_thread_inc(log_to_thread(log), x)
  #define stat_log_acc(log, x, y) stat_thread_acc(log_to_thread(log), x, y)
  #define stat_log_max(log, x, y) stat_thread_max(log_to_thread(log), x, y)
  #define stat_thread_merge(self) stat_atomic_merge(&g_stat, &(self)->stat)
  #define stat_qp_merge(qp) stat_atomic_merge(&g_stat, &(qp)->stat)
  #else /* MVRLU_ENABLE_STATS */
  #define stat_thread_inc(self, x)
  #define stat_thread_acc(self, x, y)
  #define stat_thread_max(self, x, y)
  #define stat_qp_inc(qp, x)
  #define stat_qp_acc(qp, x, y)
  #define stat_qp_max(qp, x, y)
  #define stat_log_inc(log, x)
  #define stat_log_acc(log, x, y)
  #define stat_log_max(log, x, y)
  #define stat_thread_merge(self)
  #define stat_qp_merge(qp)
  #endif /* MVRLU_ENABLE_STATS */
  
  static const char *stat_get_name(int s)
  {
  /*
  	 * Check out following implementation tricks:
  	 * - C preprocessor applications
  	 *   https://bit.ly/2H1sC5G
  	 * - Stringification
  	 *   https://gcc.gnu.org/onlinedocs/gcc-4.1.2/cpp/Stringification.html
  	 * - Designated Initializers in C
  	 *   https://www.geeksforgeeks.org/designated-initializers-c/
  	 */
  #undef S
  #define S(x) [stat_##x] = #x,
  	static const char *stat_string[stat_max__ + 1] = { STAT_NAMES };
  
  	mvrlu_assert(s >= 0 && s < stat_max__);
  	return stat_string[s];
  }
  
  static void stat_print_cnt(mvrlu_stat_t *stat)
  {
  	int i;
  	for (i = 0; i < stat_max__; ++i) {
  		printf("  %30s = %lu\n", stat_get_name(i), stat->cnt[i]);
  	}
  }
  
  static void stat_reset(mvrlu_stat_t *stat)
  {
  	int i;
  	for (i = 0; i < stat_max__; ++i) {
  		stat->cnt[i] = 0;
  	}
  }
  static void stat_atomic_merge(mvrlu_stat_t *tgt, mvrlu_stat_t *src)
  {
  	int i;
  	for (i = 0; i < stat_max__; ++i) {
  		smp_faa(&tgt->cnt[i], src->cnt[i]);
  	}
  }
  
  static inline void stat_inc(mvrlu_stat_t *stat, int s)
  {
  	stat->cnt[s]++;
  }
  
  static inline void stat_acc(mvrlu_stat_t *stat, int s, unsigned long v)
  {
  	stat->cnt[s] += v;
  }
  
  static inline void stat_max(mvrlu_stat_t *stat, int s, unsigned long v)
  {
  	if (v > stat->cnt[s])
  		stat->cnt[s] = v;
  }
  
  /*
   * thread information
   */
  
  static inline void init_mvrlu_list(mvrlu_list_t *list)
  {
  	list->next = list;
  	list->prev = list;
  }
  
  static inline void mvrlu_list_add(mvrlu_list_t *new, mvrlu_list_t *head)
  {
  	head->next->prev = new;
  	new->next = head->next;
  	new->prev = head;
  	head->next = new;
  }
  
  static inline void mvrlu_list_del(mvrlu_list_t *entry)
  {
  	entry->next->prev = entry->prev;
  	entry->prev->next = entry->next;
  }
  
  static inline int mvrlu_list_empty(const mvrlu_list_t *head)
  {
  	return head->next == head && head->prev == head;
  }
  
  static inline void mvrlu_list_rotate_left(mvrlu_list_t *head)
  {
  	/* Rotate a list in counterclockwise direction:
  	 *
  	 * Before rotation:
  	 *  [T3]->{{H}}->[T0]->[T1]->[T2]
  	 *  /|\                       |
  	 *   +------------------------+
  	 *
  	 * After rotation:
  	 *  [T3]->[T0]->{{H}}->[T1]->[T2]
  	 *  /|\                       |
  	 *   +------------------------+
  	 */
  	if (!mvrlu_list_empty(head)) {
  		mvrlu_list_t *first;
  		first = head->next;
  		mvrlu_list_del(first);
  		mvrlu_list_add(first, head->prev);
  	}
  }
  
  #define thread_list_for_each_safe(tl, pos, n, thread)                          \
  	for (pos = (tl)->list.next, n = (pos)->next,                           \
  	    thread = list_to_thread(pos);                                      \
  	     pos != &(tl)->list;                                               \
  	     pos = n, n = (pos)->next, thread = list_to_thread(pos))
  
  static inline int thread_list_has_waiter(mvrlu_thread_list_t *tl)
  {
  	return tl->thread_wait;
  }
  
  static inline void init_thread_list(mvrlu_thread_list_t *tl)
  {
  	port_spin_init(&tl->lock);
  
  	tl->cur_tid = 0;
  	tl->num = 0;
  	init_mvrlu_list(&tl->list);
  }
  
  static inline void thread_list_destroy(mvrlu_thread_list_t *tl)
  {
  	port_spin_destroy(&tl->lock);
  }
  
  static inline void thread_list_lock(mvrlu_thread_list_t *tl)
  {
  	/* Lock acquisition with a normal priority */
  	port_spin_lock(&tl->lock);
  }
  
  static inline void thread_list_lock_force(mvrlu_thread_list_t *tl)
  {
  	/* Lock acquisition with a high priority
  	 * which turns on the thread_wait flag
  	 * so a lengthy task can stop voluntarily
  	 * stop and resume later. */
  	if (!port_spin_trylock(&tl->lock)) {
  		smp_cas(&tl->thread_wait, 0, 1);
  		port_spin_lock(&tl->lock);
  	}
  }
  
  static inline void thread_list_unlock(mvrlu_thread_list_t *tl)
  {
  	if (tl->thread_wait)
  		smp_atomic_store(&tl->thread_wait, 0);
  	port_spin_unlock(&tl->lock);
  }
  
  static inline void thread_list_add(mvrlu_thread_list_t *tl,
  				   mvrlu_thread_struct_t *self)
  {
  	thread_list_lock_force(tl);
  	{
  		self->tid = tl->cur_tid++;
  		tl->num++;
  		mvrlu_list_add(&self->list, &tl->list);
  	}
  	thread_list_unlock(tl);
  }
  
  static inline void thread_list_del_unsafe(mvrlu_thread_list_t *tl,
  					  mvrlu_thread_struct_t *self)
  {
  	tl->num--;
  	mvrlu_list_del(&self->list);
  	self->list.prev = self->list.next = NULL;
  }
  
  static inline void thread_list_del(mvrlu_thread_list_t *tl,
  				   mvrlu_thread_struct_t *self)
  {
  	thread_list_lock_force(tl);
  	{
  		thread_list_del_unsafe(tl, self);
  	}
  	thread_list_unlock(tl);
  }
  
  static inline void thread_list_rotate_left_unsafe(mvrlu_thread_list_t *tl)
  {
  	/* NOTE: A caller should hold a lock */
  	mvrlu_list_rotate_left(&tl->list);
  }
  
  /*
   * Object access functions
   */
  
  static inline mvrlu_act_hdr_struct_t *obj_to_ahs(void *obj)
  {
  	mvrlu_act_hdr_struct_t *ahs = obj;
  	return &ahs[-1];
  }
  
  static inline mvrlu_act_hdr_struct_t *vobj_to_ahs(volatile void *vobj)
  {
  	return obj_to_ahs((void *)vobj);
  }
  
  static inline mvrlu_cpy_hdr_struct_t *obj_to_chs(void *obj)
  {
  	mvrlu_cpy_hdr_struct_t *chs = obj;
  	return &chs[-1];
  }
  
  static inline mvrlu_cpy_hdr_struct_t *vobj_to_chs(volatile void *vobj)
  {
  	return obj_to_chs((void *)vobj);
  }
  
  static inline mvrlu_obj_hdr_t *obj_to_obj_hdr(void *obj)
  {
  	mvrlu_obj_hdr_t *ohdr = obj;
  	return &ohdr[-1];
  }
  
  static inline mvrlu_obj_hdr_t *vobj_to_obj_hdr(volatile void *vobj)
  {
  	return obj_to_obj_hdr((void *)vobj);
  }
  
  static inline int is_obj_actual(mvrlu_obj_hdr_t *obj_hdr)
  {
  #ifdef MVRLU_DISABLE_ADDR_ACTUAL_TYPE_CHECKING
  	/* Test object type based on its type information
  	 * in the header. It may cause one cache miss. */
  	return obj_hdr->type == TYPE_ACTUAL;
  #else
  	/* Test if an object is in the log region or not.
  	 * If not, it is an actual object. We avoid one
  	 * memory reference so we may avoid one cache miss. */
  	return !port_addr_in_log_region(obj_hdr);
  #endif /* MVRLU_DISABLE_ADDR_ACTUAL_TYPE_CHECKING */
  }
  
  static inline void *get_act_obj(void *obj)
  {
  	mvrlu_obj_hdr_t *obj_hdr = obj_to_obj_hdr(obj);
  
  	if (likely(is_obj_actual(obj_hdr)))
  		return obj;
  	return (void *)obj_to_chs(obj)->cpy_hdr.p_act;
  }
  
  static inline unsigned int align_uint_to_cacheline(unsigned int unum)
  {
  	return (unum + ~MVRLU_CACHE_LINE_MASK) & MVRLU_CACHE_LINE_MASK;
  }
  
  static inline void *align_ptr_to_cacheline(void *p)
  {
  	return (void *)(((unsigned long)p + ~MVRLU_CACHE_LINE_MASK) &
  			MVRLU_CACHE_LINE_MASK);
  }
  
  /*
   * Object copy operations
   */
  
  static inline unsigned int get_log_size(const mvrlu_cpy_hdr_struct_t *chs)
  {
  	return chs->obj_hdr.obj_size + chs->obj_hdr.padding_size;
  }
  
  static inline unsigned long get_wrt_clk(const mvrlu_cpy_hdr_struct_t *chs)
  {
  	unsigned long wrt_clk;
  
  	wrt_clk = chs->cpy_hdr.__wrt_clk;
  	if (unlikely(wrt_clk == MAX_VERSION)) {
  		smp_rmb();
  		wrt_clk = *chs->cpy_hdr.p_wrt_clk;
  	}
  	return wrt_clk;
  }
  
  static int try_lock_obj(mvrlu_act_hdr_struct_t *ahs, volatile void *p_old_copy,
  			volatile void *p_new_copy)
  {
  	int ret;
  
  	if (ahs->act_hdr.p_lock != NULL || ahs->obj_hdr.p_copy != p_old_copy)
  		return 0;
  
  	ret = smp_cas(&ahs->act_hdr.p_lock, NULL, p_new_copy);
  	if (!ret)
  		return 0; /* smp_cas() failed */
  
  	if (unlikely(ahs->obj_hdr.p_copy != p_old_copy)) {
  		/* If it is ABA, unlock and return false */
  		smp_wmb();
  		ahs->act_hdr.p_lock = NULL;
  		return 0;
  	}
  
  	/* Finally succeeded. Updating p_copy of p_new_copy
  	 * will be done upon commit. */
  	return 1;
  }
  
  static void try_detach_obj(mvrlu_cpy_hdr_struct_t *chs)
  {
  	mvrlu_act_hdr_struct_t *ahs;
  	void *p_act, *p_copy;
  
  	/* If the object is the latest object after qp2, the
  	 * p_copy needs to be set to NULL */
  
  	/* Copy to the actual object when it is the latest copy */
  	p_act = (void *)chs->cpy_hdr.p_act;
  	ahs = obj_to_ahs(p_act);
  	p_copy = (void *)chs->obj_hdr.obj;
  	if (ahs->obj_hdr.p_copy != p_copy)
  		return;
  
  	/* Set p_copy of the actual object to NULL */
  	if (smp_cas(&ahs->obj_hdr.p_copy, p_copy, NULL)) {
  		/* Succeed in detaching the object */
  		return;
  	}
  }
  
  static int try_writeback_obj(mvrlu_cpy_hdr_struct_t *chs)
  {
  	mvrlu_act_hdr_struct_t *ahs;
  	void *p_act, *p_copy;
  
  	/* Copy to the actual object when it is the latest copy */
  	p_act = (void *)chs->cpy_hdr.p_act;
  	ahs = obj_to_ahs(p_act);
  	p_copy = (void *)chs->obj_hdr.obj;
  	if (ahs->obj_hdr.p_copy != p_copy)
  		return 0;
  
  	/* Write back the copy to the master */
  	memcpy(p_act, p_copy, chs->obj_hdr.obj_size);
  	smp_wmb_tso();
  	return 1;
  }
  
  static void free_obj(mvrlu_cpy_hdr_struct_t *chs)
  {
  #ifdef MVRLU_ENABLE_FREE_POISIONING
  	mvrlu_act_hdr_struct_t *ahs;
  	ahs = vobj_to_ahs(chs->cpy_hdr.p_act);
  	memset((void *)chs->cpy_hdr.p_act, MVRLU_FREE_POSION,
  	       ahs->obj_hdr.obj_size);
  	memset((void *)ahs, MVRLU_FREE_POSION, sizeof(*ahs));
  #endif
  
  	port_free(vobj_to_ahs(chs->cpy_hdr.p_act));
  }
  
  /*
   * Log operations
   */
  
  static inline unsigned long log_used(mvrlu_log_t *log)
  {
  	unsigned long used = log->tail_cnt - log->head_cnt;
  	stat_log_max(log, max_log_used_bytes, used);
  	return used;
  }
  
  static inline unsigned int log_index(unsigned long cnt)
  {
  	return cnt & ~MVRLU_LOG_MASK;
  }
  
  static inline void *log_at(mvrlu_log_t *log, unsigned long cnt)
  {
  	return (void *)&log->buffer[log_index(cnt)];
  }
  
  static inline mvrlu_wrt_set_struct_t *log_at_wss(mvrlu_log_t *log,
  						 unsigned long cnt)
  {
  	mvrlu_wrt_set_struct_t *wss;
  	wss = (mvrlu_wrt_set_struct_t *)log_at(log, cnt);
  	mvrlu_assert(wss->chs.obj_hdr.type == TYPE_WRT_SET);
  	return wss;
  }
  
  static inline mvrlu_cpy_hdr_struct_t *log_at_chs(mvrlu_log_t *log,
  						 unsigned long cnt)
  {
  	mvrlu_cpy_hdr_struct_t *chs;
  	chs = (mvrlu_cpy_hdr_struct_t *)log_at(log, cnt);
  	mvrlu_assert(chs == align_ptr_to_cacheline(chs));
  	return chs;
  }
  
  static inline unsigned int add_extra_padding(mvrlu_log_t *log,
  					     unsigned int log_size,
  					     unsigned int extra_size, int bogus)
  {
  	unsigned int padding = 0;
  
  	extra_size = extra_size + sizeof(mvrlu_cpy_hdr_struct_t);
  	extra_size = align_uint_to_cacheline(extra_size);
  
  	if (bogus == 0 && log_index(log->tail_cnt + log_size + extra_size) <
  				  log_index(log->tail_cnt)) {
  		padding = MVRLU_LOG_SIZE - log_index(log->tail_cnt + log_size);
  	}
  	if (padding) {
  		mvrlu_assert(log_index(log->tail_cnt + log_size + padding) ==
  			     0);
  	}
  
  	return padding;
  }
  static mvrlu_cpy_hdr_struct_t *log_alloc(mvrlu_log_t *log,
  					 unsigned int obj_size, int *bogus)
  {
  	mvrlu_cpy_hdr_struct_t *chs;
  	mvrlu_wrt_set_struct_t *wss;
  	unsigned int log_size;
  	unsigned int extra_pad;
  
  	/* Make log_size cacheline aligned */
  	log_size = obj_size + sizeof(mvrlu_cpy_hdr_struct_t);
  	log_size = align_uint_to_cacheline(log_size);
  	mvrlu_assert(log_size < MVRLU_LOG_SIZE);
  
  	/* If an allocation wraps around the end of a log,
  	 * insert a bogus object to prevent such case in real
  	 * object access.
  	 *
  	 *   +-----------------------------------+
  	 *   |                             |bogus|
  	 *   +-----------------------------------+
  	 *      \                           \
  	 *       \                           +- 1) log->tail_cnt
  	 *        +- 2) log->tail_cnt + log_size
  	 */
  
  	if (log_index(log->tail_cnt + log_size) < log_index(log->tail_cnt)) {
  		unsigned int bogus_size;
  
  		chs = log_at(log, log->tail_cnt);
  		memset(chs, 0, sizeof(*chs));
  		bogus_size = MVRLU_LOG_SIZE - log_index(log->tail_cnt);
  		chs->obj_hdr.padding_size = bogus_size;
  		chs->obj_hdr.type = TYPE_BOGUS;
  
  		log->tail_cnt += bogus_size;
  		mvrlu_assert(log_index(log->tail_cnt) == 0);
  		*bogus = 1;
  	}
  	mvrlu_assert(log_index(log->tail_cnt) <
  		     log_index(log->tail_cnt + log_size));
  	extra_pad = add_extra_padding(log, log_size, sizeof(*wss), *bogus);
  	log_size += extra_pad;
  
  	/*
  	 *   +--- mvrlu_cpy_hdr_struct_t ---+
  	 *  /                                \
  	 * +---------------------------------------------+----
  	 * | mvrlu_cpy_hdr_t | mvrlu_obj_hdr  | copy obj | ...
  	 * +---------------------------------------------+----
  	 */
  	chs = log_at(log, log->tail_cnt);
  	memset(chs, 0, sizeof(*chs));
  	chs->cpy_hdr.__wrt_clk = MAX_VERSION;
  	chs->obj_hdr.obj_size = obj_size;
  	chs->obj_hdr.padding_size = log_size - obj_size;
  	return chs;
  }
  
  static mvrlu_cpy_hdr_struct_t *log_append_begin(mvrlu_log_t *log,
  						volatile void *p_act,
  						unsigned int obj_size,
  						int *bogus)
  {
  	mvrlu_cpy_hdr_struct_t *chs;
  	*bogus = 0;
  
  	/* Add a write set if it is not allocated */
  	if (unlikely(!log->cur_wrt_set)) {
  		mvrlu_wrt_set_t *ws;
  		mvrlu_assert(log_index(log->tail_cnt) <
  			     log_index(log->tail_cnt + sizeof(*ws)));
  		chs = log_alloc(log, sizeof(*ws), bogus);
  		ws = (mvrlu_wrt_set_t *)chs->obj_hdr.obj;
  		chs->cpy_hdr.p_wrt_clk = &ws->wrt_clk;
  		chs->obj_hdr.type = TYPE_WRT_SET;
  		ws->wrt_clk = MAX_VERSION;
  		ws->num_objs = 0;
  		ws->start_tail_cnt = log->tail_cnt;
  		ws->thread = log_to_thread(log);
  		log->cur_wrt_set = ws;
  		log->tail_cnt += get_log_size(chs);
  		mvrlu_assert(*bogus == 0);
  	}
  
  	/* allocate an object */
  	chs = log_alloc(log, obj_size, bogus);
  	chs->cpy_hdr.p_wrt_clk = &log->cur_wrt_set->wrt_clk;
  	chs->cpy_hdr.p_act = p_act;
  	chs->obj_hdr.type = TYPE_COPY;
  	return chs;
  }
  
  static inline void log_append_abort(mvrlu_log_t *log,
  				    mvrlu_cpy_hdr_struct_t *chs)
  {
  	/* Do nothing since tail_cnt and num_objs are not updated yet.
  	 * Let's keep this for readability of the code. */
  }
  
  static inline void log_append_end(mvrlu_log_t *log, mvrlu_cpy_hdr_struct_t *chs,
  				  int bogus_allocated)
  {
  	log->tail_cnt += get_log_size(chs);
  	log->cur_wrt_set->num_objs++;
  	if (bogus_allocated) {
  		log->cur_wrt_set->num_objs++;
  	}
  }
  
  static inline unsigned long ws_iter_begin(mvrlu_wrt_set_t *ws)
  {
  	mvrlu_cpy_hdr_struct_t *chs;
  
  	chs = obj_to_chs(ws);
  	return ws->start_tail_cnt + get_log_size(chs);
  }
  
  static inline unsigned long ws_iter_next(unsigned long iter,
  					 mvrlu_cpy_hdr_struct_t *chs)
  {
  	return iter + get_log_size(chs);
  }
  
  static inline int fp_is_free(mvrlu_free_ptrs_t *free_ptrs,
  			     mvrlu_act_hdr_struct_t *ahs)
  {
  	void *p_act;
  	unsigned int i;
  
  	p_act = ahs->obj_hdr.obj;
  	for (i = 0; i < free_ptrs->num_ptrs; ++i) {
  		if (free_ptrs->ptrs[i] == p_act)
  			return 1;
  	}
  	return 0;
  }
  
  static inline void fp_reset(mvrlu_free_ptrs_t *free_ptrs)
  {
  	free_ptrs->num_ptrs = 0;
  }
  
  #define ws_for_each(log, ws, obj_idx, log_cnt)                                 \
  	for ((obj_idx) = 0, (log_cnt) = ws_iter_begin(ws);                     \
  	     (obj_idx) < (ws)->num_objs;                                       \
  	     ++(obj_idx), (log_cnt) = ws_iter_next(log_cnt, chs))
  
  static void ws_move_lock_to_copy(mvrlu_log_t *log, mvrlu_free_ptrs_t *free_ptrs)
  {
  	mvrlu_wrt_set_t *ws;
  	mvrlu_cpy_hdr_struct_t *chs;
  	unsigned long cnt;
  	unsigned long wrt_clk_next;
  	unsigned int num_free;
  	unsigned int i;
  
  	ws = log->cur_wrt_set;
  	num_free = free_ptrs->num_ptrs;
  	ws_for_each (log, ws, i, cnt) {
  		mvrlu_act_hdr_struct_t *ahs;
  		volatile void *p_old_copy, *p_old_copy2;
  
  		chs = log_at_chs(log, cnt);
  		assert_chs_type(chs);
  		if (unlikely(chs->obj_hdr.type == TYPE_BOGUS)) {
  			continue;
  		}
  		ahs = vobj_to_ahs(chs->cpy_hdr.p_act);
  		mvrlu_assert(chs->obj_hdr.type == TYPE_COPY);
  		mvrlu_assert(ahs->act_hdr.p_lock == chs->obj_hdr.obj);
  
  		/* If an object is free()-ed, change its type. */
  		if (unlikely(num_free > 0 && fp_is_free(free_ptrs, ahs))) {
  			chs->obj_hdr.type = TYPE_FREE;
  			--num_free;
  			/* Freed copy should not be accessible
  			 * from the version chain. */
  			continue;
  		}
  
  		/* If the size of copied object is zero, that is
  		 * for try_lock_const() so we do not insert it
  		 * to the version list. */
  		if (!chs->obj_hdr.obj_size)
  			continue;
  
  		/* Move a locked object to the version chain
  		 * of an actual object. */
  		p_old_copy = ahs->obj_hdr.p_copy;
  
  		while (1) {
  			/* Initialize p_copy and wrt_clk_next. */
  			chs->obj_hdr.p_copy = p_old_copy;
  			if (p_old_copy == NULL)
  				chs->cpy_hdr.wrt_clk_next = MIN_VERSION;
  			else {
  				wrt_clk_next =
  					get_wrt_clk(vobj_to_chs(p_old_copy));
  				chs->cpy_hdr.wrt_clk_next = wrt_clk_next;
  			}
  			mvrlu_assert(chs->cpy_hdr.wrt_clk_next != MAX_VERSION);
  			smp_wmb_tso();
  
  			/* Since p_copy of p_act can be set to NULL upon
  			 * reclaim, we should update it using smp_cas(). */
  			if (smp_cas_v(&ahs->obj_hdr.p_copy, p_old_copy,
  				      chs->obj_hdr.obj, p_old_copy2))
  				break;
  
  			/* smp_cas_v() failed. Retry.
  			 * p_old_copy2 is updated by smp_cas_v(). */
  			p_old_copy = p_old_copy2;
  		}
  		mvrlu_assert(ahs->obj_hdr.p_copy == chs->obj_hdr.obj);
  	}
  }
  
  static void ws_unlock(mvrlu_log_t *log, unsigned long wrt_clk)
  {
  	mvrlu_wrt_set_t *ws;
  	mvrlu_cpy_hdr_struct_t *chs;
  	unsigned long cnt;
  	unsigned int i;
  
  	ws = log->cur_wrt_set;
  	wrt_clk = ws->wrt_clk;
  	ws_for_each (log, ws, i, cnt) {
  		chs = log_at_chs(log, cnt);
  		assert_chs_type(chs);
  		if (unlikely(chs->obj_hdr.type == TYPE_BOGUS)) {
  			continue;
  		}
  		mvrlu_assert(chs->obj_hdr.type == TYPE_COPY ||
  			     chs->obj_hdr.type == TYPE_FREE);
  
  		/* Mark version */
  		if (wrt_clk != MAX_VERSION) {
  			chs->cpy_hdr.__wrt_clk = wrt_clk;
  			smp_wmb_tso();
  		}
  
  		/* Unlock */
  		if (likely(chs->obj_hdr.type == TYPE_COPY)) {
  			mvrlu_act_hdr_struct_t *ahs;
  			ahs = vobj_to_ahs(chs->cpy_hdr.p_act);
  			mvrlu_assert(ahs->act_hdr.p_lock == chs->obj_hdr.obj);
  			ahs->act_hdr.p_lock = NULL;
  		}
  	}
  }
  
  static void log_commit(mvrlu_log_t *log, mvrlu_free_ptrs_t *free_ptrs,
  		       unsigned long local_clk)
  {
  	mvrlu_assert(log->cur_wrt_set);
  	mvrlu_assert(obj_to_chs(log->cur_wrt_set)->obj_hdr.type ==
  		     TYPE_WRT_SET);
  
  	/* Move a committed object to its version chain */
  	ws_move_lock_to_copy(log, free_ptrs);
  	smp_wmb();
  
  	/* Make them public atomically */
  	smp_atomic_store(&log->cur_wrt_set->wrt_clk, new_clock(local_clk));
  
  	/* Advance global clock */
  	advance_clock();
  
  	/* Unlock objects with marking wrt_clk */
  	ws_unlock(log, log->cur_wrt_set->wrt_clk);
  
  	/* Clean up */
  	log->cur_wrt_set = NULL;
  	fp_reset(free_ptrs);
  }
  
  static void log_abort(mvrlu_log_t *log, mvrlu_free_ptrs_t *free_ptrs)
  {
  	/* Unlock objects without marking wrt_clk */
  	ws_unlock(log, MAX_VERSION);
  
  	/* Reset the current write set */
  	log->tail_cnt = log->cur_wrt_set->start_tail_cnt;
  	log->cur_wrt_set = NULL;
  	fp_reset(free_ptrs);
  }
  
  static inline int try_lock(volatile unsigned int *lock)
  {
  	if (*lock == 0 && smp_cas(lock, 0, 1))
  		return 1;
  	return 0;
  }
  
  static inline void unlock(volatile unsigned int *lock)
  {
  	*lock = 0;
  }
  
  static void log_reclaim(mvrlu_log_t *log)
  {
  	/*
  	 * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  	 *                       MV-RLU
  	 *                       ======
  	 *
  	 *                           head'
  	 *            head           qp2        qp1    tail
  	 *              \           /          /      /
  	 *     +---------+====================+------+------+
  	 *     |         |..........|/////////|      |      |
  	 *     +---------+====================+------+------+
  	 *               ~~~~~~~~~~>
  	 *               reclaim
  	 *                          ~~~~~~~~~~>
  	 *                          writeback
  	 *
  	 * 1. (qp1, tail)
  	 *   - The master is still accessible.
  	 * 2. (qp2, qp1]
  	 *   - Nobody accesses the master because all threads
  	 *   access the copy. Thus, we can safely write back
  	 *   the copy to the master.
  	 *   - Write back only if the copy is the latest.
  	 *   - While nobody accesses the master, the copy is
  	 *   still accessible. So we cannot free the master yet.
  	 * 3. [head, qp2]
  	 *   - Nobobdy accesses this copy because a thread
  	 *   accesses either of the master or a newer copy.
  	 *   Thus, we can safely reclaim this copy.
  	 *   - Since nobody accesses either the master
  	 *   or the copy, we can free the master.
  	 * 4. head' = qp2
  	 *   - head is updated to qp2 because log reclamation
  	 *   will resume from qp2.
  	 *
  	 */
  
  	mvrlu_wrt_set_t *ws;
  	mvrlu_wrt_set_struct_t *wss;
  	mvrlu_cpy_hdr_struct_t *chs;
  	unsigned long cnt;
  	unsigned long qp_clk1;
  	unsigned long qp_clk2;
  	unsigned int i;
  	unsigned long start_cnt;
  	unsigned long tail_cnt;
  	unsigned int index;
  	int reclaim;
  	int try_writeback;
  
  	if (!log->need_reclaim)
  		return;
  	if (!try_lock(&log->reclaim_lock))
  		return;
  
  	qp_clk1 = log->qp_clk1;
  	qp_clk2 = log->qp_clk2;
  	start_cnt = log->head_cnt;
  	tail_cnt = log->tail_cnt;
  	while (start_cnt < tail_cnt) {
  		reclaim = 0;
  		try_writeback = 0;
  		index = log_index(start_cnt);
  		wss = log_at_wss(log, index);
  		ws = &(wss->wrt_set);
  
  		if (gte_clock(ws->wrt_clk, qp_clk1) && ws->wrt_clk != qp_clk1)
  			break;
  		else if (lte_clock(ws->wrt_clk, qp_clk2))
  			reclaim = 1;
  		else if (lte_clock(ws->wrt_clk, qp_clk1))
  			try_writeback = 1;
  
  		ws_for_each (log, ws, i, cnt) {
  			chs = log_at_chs(log, cnt);
  			assert_chs_type(chs);
  			switch (chs->obj_hdr.type) {
  			case TYPE_COPY:
  				if (try_writeback && try_writeback_obj(chs))
  					try_detach_obj(chs);
  				stat_log_inc(log, n_reclaim_copy);
  				break;
  			case TYPE_FREE:
  				if (reclaim) {
  					free_obj(chs);
  					stat_log_inc(log, n_reclaim_free);
  				}
  				break;
  			case TYPE_BOGUS:
  				break; /* Do nothing */
  			default:
  				mvrlu_assert(0 && "Never be here");
  				break;
  			}
  			mvrlu_assert(cnt <= log->tail_cnt);
  		}
  		start_cnt = cnt;
  		mvrlu_assert(start_cnt <= log->tail_cnt);
  		if (reclaim)
  			log->head_cnt = start_cnt;
  		stat_log_inc(log, n_reclaim_wrt_set);
  	}
  	stat_log_inc(log, n_reclaim);
  	log->need_reclaim = 0;
  
  	unlock(&log->reclaim_lock);
  }
  
  static void log_reclaim_force(mvrlu_log_t *log)
  {
  	if (log->need_reclaim) {
  		log_reclaim(log);
  		return;
  	}
  
  	if (log->head_cnt != log->tail_cnt) {
  		int count = 0; /* TODO FIXME */
  		wakeup_qp_thread_for_reclaim();
  		do {
  			port_cpu_relax_and_yield();
  			smp_mb();
  			count++;
  			if (count == 1000) {
  				wakeup_qp_thread_for_reclaim();
  				count = 0;
  			}
  		} while (!log->need_reclaim);
  		log_reclaim(log);
  	}
  }
  
  /*
   * Quiescent detection functions
   */
  
  static void qp_init(mvrlu_qp_thread_t *qp_thread, unsigned long qp_clk)
  {
  	mvrlu_thread_struct_t *thread;
  	mvrlu_list_t *pos, *n;
  
  	thread_list_lock(&g_live_threads);
  	{
  		thread_list_for_each_safe (&g_live_threads, pos, n, thread) {
  			thread->qp_info.run_cnt = thread->run_cnt;
  			thread->qp_info.need_wait =
  				thread->qp_info.run_cnt & 0x1;
  		}
  	}
  	thread_list_unlock(&g_live_threads);
  }
  
  static void qp_wait(mvrlu_qp_thread_t *qp_thread, unsigned long qp_clk)
  {
  	mvrlu_thread_struct_t *thread;
  	mvrlu_list_t *pos, *n;
  
  retry:
  	thread_list_lock(&g_live_threads);
  	{
  		thread_list_for_each_safe (&g_live_threads, pos, n, thread) {
  			if (!thread->qp_info.need_wait)
  				continue;
  
  			while (1) {
  				/* Check if a thread passed quiescent period. */
  				if (thread->qp_info.run_cnt !=
  					    thread->run_cnt ||
  				    gte_clock(thread->local_clk, qp_clk)) {
  					thread->qp_info.need_wait = 0;
  					break;
  				}
  
  				/* If a thread is waiting for adding or deleting
  				 * from/to the thread list, yield and retry. */
  				if (thread_list_has_waiter(&g_live_threads)) {
  					thread_list_unlock(&g_live_threads);
  					goto retry;
  				}
  
  				port_cpu_relax_and_yield();
  				smp_mb();
  			}
  		}
  	}
  	thread_list_unlock(&g_live_threads);
  }
  
  static void qp_take_nap(mvrlu_qp_thread_t *qp_thread)
  {
  	port_initiate_nap(&qp_thread->cond_mutex, &qp_thread->cond,
  			  MVRLU_QP_INTERVAL_USEC);
  }
  
  static void qp_detect(mvrlu_qp_thread_t *qp_thread)
  {
  	unsigned long qp_clk;
  
  	qp_clk = get_clock();
  	qp_init(qp_thread, qp_clk);
  	stat_qp_inc(qp_thread, n_qp_detect);
  	if (!qp_thread->need_reclaim) {
  		qp_take_nap(qp_thread);
  		stat_qp_inc(qp_thread, n_qp_nap);
  	}
  	qp_wait(qp_thread, qp_clk);
  	qp_thread->qp_clk = correct_qp_clk(qp_clk);
  }
  
  static void qp_help_reclaim_log(mvrlu_qp_thread_t *qp_thread)
  {
  	mvrlu_thread_struct_t *thread;
  	mvrlu_list_t *pos, *n;
  
  retry:
  	thread_list_lock(&g_live_threads);
  	{
  		smp_mb();
  		thread_list_for_each_safe (&g_live_threads, pos, n, thread) {
  			/* If a thread is waiting for adding or deleting
  			 * from/to the thread list, yield and retry. */
  			if (thread_list_has_waiter(&g_live_threads)) {
  				thread_list_unlock(&g_live_threads);
  				goto retry;
  			}
  
  			/* Help reclaiming */
  			if (thread->log.need_reclaim) {
  				log_reclaim(&thread->log);
  				stat_qp_inc(qp_thread, n_qp_help_reclaim);
  			}
  		}
  
  		/* Rotate the thread list counter clockwise for fairness. */
  		thread_list_rotate_left_unsafe(&g_live_threads);
  	}
  	thread_list_unlock(&g_live_threads);
  }
  
  static void qp_reap_zombie_threads(mvrlu_qp_thread_t *qp_thread)
  {
  	mvrlu_thread_struct_t *thread;
  	mvrlu_list_t *pos, *n;
  
  retry:
  	thread_list_lock(&g_zombie_threads);
  	{
  		smp_mb();
  		thread_list_for_each_safe (&g_zombie_threads, pos, n, thread) {
  			/* If a thread is waiting for adding or deleting
  			 * from/to the thread list, yield and retry. */
  			if (thread_list_has_waiter(&g_zombie_threads)) {
  				thread_list_unlock(&g_zombie_threads);
  				goto retry;
  			}
  
  			/* Enforce reclaiming logs */
  			qp_update_qp_clk_for_reclaim(qp_thread, thread);
  			log_reclaim(&thread->log);
  
  			/* If the log is completely reclaimed, try next thread */
  			if (thread->log.head_cnt != thread->log.tail_cnt)
  				continue;
  
  			/* Free log buffer if it is not yet freed */
  			if (thread->log.buffer) {
  				port_free_log_mem((void *)thread->log.buffer);
  				thread->log.buffer = NULL;
  				stat_thread_merge(thread);
  				stat_qp_inc(qp_thread, n_qp_zombie_reclaim);
  			}
  
  			/* If it is a dead zombie, reap */
  			if (thread->live_status == THREAD_DEAD_ZOMBIE) {
  				thread_list_del_unsafe(&g_zombie_threads,
  						       thread);
  				mvrlu_thread_free(thread);
  			}
  		}
  	}
  	thread_list_unlock(&g_zombie_threads);
  }
  
  static int qp_check_reclaim_done(mvrlu_qp_thread_t *qp_thread)
  {
  	mvrlu_thread_struct_t *thread;
  	mvrlu_list_t *pos, *n;
  	int rc = 1;
  
  	thread_list_lock(&g_live_threads);
  	{
  		smp_mb();
  		thread_list_for_each_safe (&g_live_threads, pos, n, thread) {
  			if (thread->log.need_reclaim) {
  				rc = 0;
  				break;
  			}
  		}
  	}
  	thread_list_unlock(&g_live_threads);
  	return rc;
  }
  
  static void qp_update_qp_clk_for_reclaim(mvrlu_qp_thread_t *qp_thread,
  					 mvrlu_thread_struct_t *thread)
  {
  	thread->log.qp_clk2 = thread->log.qp_clk1;
  	thread->log.qp_clk1 = qp_thread->qp_clk;
  	thread->log.need_reclaim = 1;
  }
  
  static void qp_trigger_reclaim(mvrlu_qp_thread_t *qp_thread)
  {
  	mvrlu_thread_struct_t *thread;
  	mvrlu_list_t *pos, *n;
  
  	thread_list_lock(&g_live_threads);
  	{
  		thread_list_for_each_safe (&g_live_threads, pos, n, thread) {
  			qp_update_qp_clk_for_reclaim(qp_thread, thread);
  		}
  	}
  	thread_list_unlock(&g_live_threads);
  	smp_mb();
  }
  
  static void __qp_thread_main(void *arg)
  {
  	mvrlu_qp_thread_t *qp_thread = arg;
  	int reclaim_done;
  	int i;
  
  	/* qp detection loop */
  	reclaim_done = 1;
  	while (!qp_thread->stop_requested) {
  		qp_detect(qp_thread);
  
  		if (!reclaim_done) {
  			qp_reap_zombie_threads(qp_thread);
  			qp_help_reclaim_log(qp_thread);
  			reclaim_done = qp_check_reclaim_done(qp_thread);
  			if (reclaim_done) {
  				smp_cas(&qp_thread->need_reclaim, 1, 0);
  				smp_mb();
  			}
  		}
  
  		if (reclaim_done && qp_thread->need_reclaim) {
  			reclaim_done = 0;
  			qp_trigger_reclaim(qp_thread);
  		}
  	}
  
  	/* This is the final reclamation so we should completely reclaim
  	 * all logs. To do that, we have to reclaim twice because we need
  	 * two qp duration for complete reclamation. */
  	for (i = 0; i < 2; ++i) {
  		qp_thread->qp_clk = get_clock();
  		qp_reap_zombie_threads(qp_thread);
  	}
  }
  
  #ifdef __KERNEL__
  static int qp_thread_main(void *arg)
  {
  	__qp_thread_main(arg);
  	return 0;
  }
  #else
  static void *qp_thread_main(void *arg)
  {
  	__qp_thread_main(arg);
  	return NULL;
  }
  #endif
  
  static int init_qp_thread(mvrlu_qp_thread_t *qp_thread)
  {
  	int rc;
  
  	memset(qp_thread, 0, sizeof(*qp_thread));
  	port_cond_init(&qp_thread->cond);
  	port_mutex_init(&qp_thread->cond_mutex);
  	rc = port_create_thread("qp_thread", &qp_thread->thread,
  				&qp_thread_main, qp_thread,
  				&qp_thread->completion);
  	if (rc) {
  		mvrlu_trace_global("Error creating builder thread: %d\n", rc);
  		return rc;
  	}
  	return 0;
  }
  
  static inline void wakeup_qp_thread(mvrlu_qp_thread_t *qp_thread)
  {
  	port_initiate_wakeup(&qp_thread->cond_mutex, &qp_thread->cond);
  }
  
  static void finish_qp_thread(mvrlu_qp_thread_t *qp_thread)
  {
  	wakeup_qp_thread(qp_thread);
  
  	smp_atomic_store(&qp_thread->stop_requested, 1);
  	smp_mb();
  
  	port_wait_for_finish(&qp_thread->thread, &qp_thread->completion);
  	port_mutex_destroy(&qp_thread->cond_mutex);
  	port_cond_destroy(&qp_thread->cond);
  	stat_qp_merge(qp_thread);
  }
  
  static inline int wakeup_qp_thread_for_reclaim(void)
  {
  	mvrlu_qp_thread_t *qp_thread = &g_qp_thread;
  
  	if (!qp_thread->need_reclaim &&
  	    smp_cas(&qp_thread->need_reclaim, 0, 1)) {
  		wakeup_qp_thread(qp_thread);
  		return 1;
  	}
  	return 0;
  }
  
  /*
   * External APIs
   */
  
  int __init mvrlu_init(void)
  {
  	static int init = 0;
  	int rc;
  
  	/* Compile time sanity check */
  	static_assert(sizeof(mvrlu_act_hdr_struct_t) < L1_CACHE_BYTES);
  	static_assert(sizeof(mvrlu_cpy_hdr_struct_t) < L1_CACHE_BYTES);
  	static_assert((MVRLU_LOG_SIZE & (MVRLU_LOG_SIZE - 1)) == 0);
  
  	/* Make sure whether it is initialized once */
  	if (!smp_cas(&init, 0, 1))
  		return -EBUSY;
  
  	/* Initialize */
  	init_clock();
  	init_thread_list(&g_live_threads);
  	init_thread_list(&g_zombie_threads);
  	rc = port_log_region_init(MVRLU_LOG_SIZE, MVRLU_MAX_THREAD_NUM);
  	if (rc) {
  		mvrlu_trace_global("Fail to initialize a log region\n");
  		return rc;
  	}
  	rc = init_qp_thread(&g_qp_thread);
  	if (rc) {
  		mvrlu_trace_global("Fail to initialize a qp thread\n");
  		return rc;
  	}
  
  	return 0;
  }
  early_initcall(mvrlu_init);
  
  void mvrlu_finish(void)
  {
  	finish_qp_thread(&g_qp_thread);
  	thread_list_destroy(&g_live_threads);
  	thread_list_destroy(&g_zombie_threads);
  	port_log_region_destroy();
  }
  
  mvrlu_thread_struct_t *mvrlu_thread_alloc(void)
  {
  	return port_alloc(sizeof(mvrlu_thread_struct_t));
  }
  EXPORT_SYMBOL(mvrlu_thread_alloc);
  
  void mvrlu_thread_free(mvrlu_thread_struct_t *self)
  {
  	smp_atomic_store(&self->live_status, THREAD_DEAD_ZOMBIE);
  
  	/* If the log is not completely reclaimed yet,
  	 * defer the free until it is completely reclaimed.
  	 * In this case, we just move the thread to the zombie
  	 * list and the qp thread will eventually reclaim
  	 * the log. */
  	smp_mb();
  	if (self->log.head_cnt == self->log.tail_cnt)
  		port_free(self);
  }
  EXPORT_SYMBOL(mvrlu_thread_free);
  
  void mvrlu_thread_init(mvrlu_thread_struct_t *self)
  {
  	/* Zero out self */
  	memset(self, 0, sizeof(*self));
  
  	/* Allocate cacheline-aligned log space */
  	self->log.buffer = port_alloc_log_mem();
  	mvrlu_assert(self->log.buffer ==
  		     align_ptr_to_cacheline((void *)self->log.buffer));
  
  	/* Add this to the global list */
  	thread_list_add(&g_live_threads, self);
  	smp_mb();
  }
  EXPORT_SYMBOL(mvrlu_thread_init);
  
  void mvrlu_thread_finish(mvrlu_thread_struct_t *self)
  {
  	/* Reclaim data as much as it can */
  	if (self->log.need_reclaim)
  		log_reclaim(&self->log);
  
  	/* Deregister this thread from the live list */
  	self->qp_info.need_wait = 0;
  	thread_list_del(&g_live_threads, self);
  
  	/* If the log is empty, free log space and update statistics */
  	smp_mb();
  	if (self->log.head_cnt == self->log.tail_cnt) {
  		port_free_log_mem((void *)self->log.buffer);
  		self->log.buffer = NULL;
  		stat_thread_merge(self);
  	}
  	/* Otherwise add it to the zombie list to reclaim the log later */
  	else {
  		smp_atomic_store(&self->live_status, THREAD_LIVE_ZOMBIE);
  		thread_list_add(&g_zombie_threads, self);
  	}
  }
  EXPORT_SYMBOL(mvrlu_thread_finish);
  
  void *mvrlu_alloc_x(size_t size, unsigned int flags)
  {
  	mvrlu_act_hdr_struct_t *ahs;
  
  	ahs = (void *)port_alloc_x(sizeof(*ahs) + size, flags);
  	if (unlikely(ahs == NULL))
  		return NULL;
  
  	memset(ahs, 0, sizeof(*ahs));
  	ahs->obj_hdr.type = TYPE_ACTUAL;
  	ahs->obj_hdr.obj_size = size;
  	return ahs->obj_hdr.obj;
  }
  EXPORT_SYMBOL(mvrlu_alloc_x);
  
  void *mvrlu_alloc(size_t size)
  {
  	return mvrlu_alloc_x(size, PORT_DEFAULT_ALLOC_FLAG);
  }
  EXPORT_SYMBOL(mvrlu_alloc);
  
  void mvrlu_free(mvrlu_thread_struct_t *self, void *obj)
  {
  	void *p_act;
  
  	if (unlikely(obj == NULL))
  		return;
  
  	if (unlikely(self == NULL)) {
  		port_free(obj_to_ahs(obj));
  		return;
  	}
  	mvrlu_assert(self->run_cnt & 0x1);
  
  	p_act = get_act_obj(obj);
  	mvrlu_warning(obj_to_ahs(p_act)->act_hdr.p_lock != NULL);
  
  	self->free_ptrs.ptrs[self->free_ptrs.num_ptrs++] = p_act;
  	mvrlu_assert(self->free_ptrs.num_ptrs < MVRLU_MAX_FREE_PTRS);
  }
  EXPORT_SYMBOL(mvrlu_free);
  
  void mvrlu_reader_lock(mvrlu_thread_struct_t *self)
  {
  	/* Secure a large enough log space */
  	if (unlikely(self->log.need_reclaim))
  		log_reclaim(&self->log);
  	/* - capacity water mark */
  	if (unlikely(log_used(&self->log) >= MVRLU_LOG_HIGH_MARK)) {
  		do {
  			log_reclaim_force(&self->log);
  			stat_thread_inc(self, n_high_mark_block);
  		} while (log_used(&self->log) >= MVRLU_LOG_HIGH_MARK);
  	}
  
  	/* Object data writes should not be reordered with metadata writes. */
  	smp_wmb_tso();
  
  	/* Get it started */
  	smp_faa(&(self->run_cnt), 1);
  	self->num_act_obj = 0;
  	self->num_deref = 0;
  	self->local_clk = get_clock_relaxed();
  
  	/* Get the latest view */
  	smp_rmb();
  
  	stat_thread_inc(self, n_starts);
  	mvrlu_assert(self->log.cur_wrt_set == NULL);
  	mvrlu_assert(self->free_ptrs.num_ptrs == 0);
  }
  EXPORT_SYMBOL(mvrlu_reader_lock);
  
  void mvrlu_reader_unlock(mvrlu_thread_struct_t *self)
  {
  	/* Object data writes should not be reordered with metadata writes. */
  	smp_wmb_tso();
  
  	mvrlu_assert(self->run_cnt & 0x1);
  	self->run_cnt++;
  
  	/* If dereference takes too much overhead, reclaim log */
  	/* - dereference water mark */
  	if (self->num_deref && self->num_act_obj > MVRLU_DEREF_MIN_ACT_OBJ &&
  	    self->num_act_obj < (MVRLU_DEREF_MARK * self->num_deref)) {
  		wakeup_qp_thread_for_reclaim();
  	}
  
  	/* If write or log reclaim is needed, we need write memory
  	 * barrier to avoid reordering of metadata updates. */
  	if (self->is_write_detected || self->log.need_reclaim) {
  		if (self->is_write_detected) {
  			self->is_write_detected = 0;
  			log_commit(&self->log, &self->free_ptrs,
  				   self->local_clk);
  		}
  
  		if (unlikely(self->log.need_reclaim))
  			log_reclaim(&self->log);
  
  		if (unlikely(log_used(&self->log) >= MVRLU_LOG_LOW_MARK)) {
  			if (wakeup_qp_thread_for_reclaim()) {
  				stat_thread_inc(self, n_low_mark_wakeup);
  			}
  		}
  		smp_wmb();
  	}
  
  	stat_thread_inc(self, n_finish);
  	mvrlu_assert(self->log.cur_wrt_set == NULL);
  	mvrlu_assert(self->free_ptrs.num_ptrs == 0);
  }
  EXPORT_SYMBOL(mvrlu_reader_unlock);
  
  void mvrlu_abort(mvrlu_thread_struct_t *self)
  {
  	/* Object data writes should not be reordered with metadata writes. */
  	smp_wmb_tso();
  
  	mvrlu_assert(self->run_cnt & 0x1);
  	self->run_cnt++;
  
  	if (self->log.cur_wrt_set) {
  		log_abort(&self->log, &self->free_ptrs);
  		self->is_write_detected = 0;
  	}
  
  	if (unlikely(self->log.need_reclaim))
  		log_reclaim(&self->log);
  
  	/* Prepare next mvrlu_reader_lock() by performing memory barrier. */
  	smp_mb();
  
  	stat_thread_inc(self, n_aborts);
  	mvrlu_assert(self->log.cur_wrt_set == NULL);
  	mvrlu_assert(self->free_ptrs.num_ptrs == 0);
  }
  EXPORT_SYMBOL(mvrlu_abort);
  
  void *mvrlu_deref(mvrlu_thread_struct_t *self, void *obj)
  {
  	volatile void *p_act, *p_copy;
  	mvrlu_cpy_hdr_struct_t *chs;
  	unsigned long wrt_clk;
  	unsigned long qp_clk2;
  
  	if (unlikely(!obj))
  		return NULL;
  
  	p_act = get_act_obj(obj);
  	mvrlu_assert(p_act && vobj_to_obj_hdr(p_act)->type == TYPE_ACTUAL);
  	self->num_act_obj++;
  
  	p_copy = vobj_to_obj_hdr(p_act)->p_copy;
  	if (unlikely(p_copy)) {
  		qp_clk2 = self->log.qp_clk2;
  		self->num_deref++;
  		do {
  			chs = vobj_to_chs(p_copy);
  			wrt_clk = get_wrt_clk(chs);
  			if (lte_clock(wrt_clk, self->local_clk))
  				return (void *)p_copy;
  
  			if (unlikely(lte_clock(chs->cpy_hdr.wrt_clk_next,
  					       qp_clk2)))
  				break;
  			p_copy = chs->obj_hdr.p_copy;
  		} while (p_copy);
  	}
  	return (void *)p_act;
  }
  EXPORT_SYMBOL(mvrlu_deref);
  
  int _mvrlu_try_lock(mvrlu_thread_struct_t *self, void **pp_obj, size_t size)
  {
  	volatile void *p_act, *p_lock, *p_old_copy, *p_new_copy;
  	mvrlu_act_hdr_struct_t *ahs;
  	mvrlu_cpy_hdr_struct_t *chs;
  	void *obj;
  	int bogus_allocated;
  
  	obj = *pp_obj;
  	mvrlu_warning(obj != NULL);
  
  	p_act = get_act_obj(obj);
  	mvrlu_assert(p_act && vobj_to_obj_hdr(p_act)->type == TYPE_ACTUAL);
  
  	/* If an object is already locked, it cannot lock again
  	 * except when a lock is locked again by the same thread. */
  	ahs = vobj_to_ahs(p_act);
  	p_lock = ahs->act_hdr.p_lock;
  	if (unlikely(p_lock)) {
  #ifdef MVRLU_NESTED_LOCKING
  		if (self == chs_to_thread(vobj_to_chs(p_lock))) {
  			/* If the lock is acquired by the same thread,
  			 * allow to lock again according to the original
  			 * RLU semantics.
  			 *
  			 * WARNING: We do not promote immutable try_lock_const()
  			 * to mutable try_lock_const().
  			 */
  			mvrlu_warning(size <= ahs->obj_hdr.obj_size);
  			*pp_obj = (void *)p_lock;
  			return 1;
  		}
  #endif
  		return 0;
  	}
  
  	/* To maintain a linear version history, we should allow
  	 * lock acquisition only when the local version of a thread
  	 * is greater or equal to the writer version of an object.
  	 * Otherwise it allows inconsistent, mixed, views
  	 * of the local version and the writer version.
  	 * That is because acquiring a lock fundamentally means
  	 * advancing the version. */
  	p_old_copy = ahs->obj_hdr.p_copy;
  	if (p_old_copy) {
  		chs = vobj_to_chs(p_old_copy);
  		/* It guarantees that clock gap between two versions of
  		 * an object is greater than 2x ORDO_BOUNDARY. */
  		if (!lte_clock(get_wrt_clk(chs), self->local_clk))
  			return 0;
  	}
  
  	/* Secure log space and initialize a header */
  	chs = log_append_begin(&self->log, p_act, size, &bogus_allocated);
  	p_new_copy = (volatile void *)chs->obj_hdr.obj;
  
  	/* Try lock */
  	if (!try_lock_obj(ahs, p_old_copy, p_new_copy)) {
  		log_append_abort(&self->log, chs);
  		return 0;
  	}
  
  	/* Duplicate the copy */
  	if (!p_old_copy)
  		memcpy((void *)p_new_copy, (void *)p_act, size);
  	else
  		memcpy((void *)p_new_copy, (void *)p_old_copy, size);
  	log_append_end(&self->log, chs, bogus_allocated);
  
  	/* Succeed in locking */
  	if (self->is_write_detected == 0)
  		self->is_write_detected = 1;
  	*pp_obj = (void *)p_new_copy;
  
  	mvrlu_assert(ahs->act_hdr.p_lock);
  	return 1;
  }
  EXPORT_SYMBOL(_mvrlu_try_lock);
  
  int _mvrlu_try_lock_const(mvrlu_thread_struct_t *self, void *obj, size_t size)
  {
  	/* Try_lock_const is nothing but a try lock with size zero
  	 * so we can omit copy from/to p_act.
  	 *
  	 * NOTE: obj is not updated after the call (not void ** but void *) */
  	return _mvrlu_try_lock(self, &obj, 0);
  }
  EXPORT_SYMBOL(_mvrlu_try_lock_const);
  
  int mvrlu_cmp_ptrs(void *obj1, void *obj2)
  {
  	if (likely(obj1 != NULL))
  		obj1 = get_act_obj(obj1);
  	if (likely(obj2 != NULL))
  		obj2 = get_act_obj(obj2);
  	return obj1 == obj2;
  }
  EXPORT_SYMBOL(mvrlu_cmp_ptrs);
  
  void _mvrlu_assign_pointer(void **p_ptr, void *obj)
  {
  	if (likely(obj != NULL))
  		obj = get_act_obj(obj);
  	*p_ptr = obj;
  }
  EXPORT_SYMBOL(_mvrlu_assign_pointer);
  
  void mvrlu_flush_log(mvrlu_thread_struct_t *self)
  {
  	while (self->log.head_cnt != self->log.tail_cnt) {
  		log_reclaim_force(&self->log);
  	}
  #ifdef MVRLU_ENABLE_STATS
  	stat_reset(&(self)->stat);
  #endif
  }
  EXPORT_SYMBOL(mvrlu_flush_log);
  
  void mvrlu_print_stats(void)
  {
  	printf("=================================================\n");
  	printf("MV-RLU configuration:\n");
  	printf("-------------------------------------------------\n");
  	print_config();
  	printf("-------------------------------------------------\n");
  
  	/* It should be called after mvrlu_finish(). */
  #ifdef MVRLU_ENABLE_STATS
  	printf("MV-RLU statistics:\n");
  	printf("-------------------------------------------------\n");
  	stat_print_cnt(&g_stat);
  	printf("-------------------------------------------------\n");
  #endif
  }
  
  static void print_config(void)
  {
  	printf(MVRLU_COLOR_GREEN
  #ifdef MVRLU_ORDO_TIMESTAMPING
  	       "  MVRLU_ORDO_TIMESTAMPING = 1\n"
  #else
  	       "  MVRLU_ORDO_TIMESTAMPING = 0\n"
  #endif
  	       MVRLU_COLOR_RESET);
  	printf(MVRLU_COLOR_GREEN "  MVRLU_LOG_SIZE = %ld\n" MVRLU_COLOR_RESET,
  	       MVRLU_LOG_SIZE);
  	printf(MVRLU_COLOR_GREEN
  	       "  MVRLU_LOG_LOW_MARK = %ld\n" MVRLU_COLOR_RESET,
  	       MVRLU_LOG_LOW_MARK);
  	printf(MVRLU_COLOR_GREEN
  	       "  MVRLU_LOG_HIGH_MARK = %ld\n" MVRLU_COLOR_RESET,
  	       MVRLU_LOG_HIGH_MARK);
  #ifdef MVRLU_ENABLE_ASSERT
  	printf(MVRLU_COLOR_RED "  MVRLU_ENABLE_ASSERT is on.          "
  			       "DO NOT USE FOR BENCHMARK!\n" MVRLU_COLOR_RESET);
  #endif
  #ifdef MVRLU_ENABLE_FREE_POISIONING
  	printf(MVRLU_COLOR_RED "  MVRLU_ENABLE_FREE_POISIONING is on. "
  			       "DO NOT USE FOR BENCHMARK!\n" MVRLU_COLOR_RESET);
  #endif
  #ifdef MVRLU_ENABLE_STATS
  	printf(MVRLU_COLOR_RED "  MVRLU_ENABLE_STATS is on.       "
  			       "DO NOT USE FOR BENCHMARK!\n" MVRLU_COLOR_RESET);
  #endif
  #ifdef MVRLU_TIME_MEASUREMENT
  	printf(MVRLU_COLOR_RED "  MVRLU_TIME_MEASUREMENT is on.       "
  			       "DO NOT USE FOR BENCHMARK!\n" MVRLU_COLOR_RESET);
  #endif
  #if defined(MVRLU_ENABLE_TRACE_0) || defined(MVRLU_ENABLE_TRACE_1) ||          \
  	defined(MVRLU_ENABLE_TRACE_2) || defined(MVRLU_ENABLE_TRACE_3)
  	printf(MVRLU_COLOR_MAGENTA
  	       "  MVRLU_ENABLE_TRACE_*  is on.        "
  	       "IT MAY AFFECT BENCHMARK RESULTS!\n" MVRLU_COLOR_RESET);
  #endif
  }
  EXPORT_SYMBOL(mvrlu_print_stats);
  