atomiclist.h

/*-
 * Copyright (c) 2020 Ryo Shimizu <[email protected]>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#ifndef _ATOMICLIST_H_
#define _ATOMICLIST_H_

/*
 * atomic (lock-less) linked List
 */
#include <sys/cdefs.h>
#include <sys/param.h>
#include <sys/types.h>
#include <sys/inttypes.h>
#include <sys/atomic.h>

/*#define ALISTDEBUG*/

#define _ALIST_MARK_PTR(ptr)		\
	((__typeof((ptr)))((uintptr_t)(ptr) | 1ul))
#define _ALIST_UNMARK_PTR(ptr)		\
	((__typeof((ptr)))((uintptr_t)(ptr) & ~1ul))
#define _ALIST_PTR_MARKED_P(ptr)	((uintptr_t)(ptr) & 1ul)

#ifndef ALISTDEBUG
#define _ALIST_CNT_DECL(name)
#define _ALIST_CNT_INC(head, name)	__nothing
#define ALIST_DUMPSTAT(head)
#else /* ALISTDEBUG */
#define _ALIST_CNT_DECL(name)		uint64_t alh_ctr_##name;
#define _ALIST_CNT_INC(head, name)	atomic_inc_64(&(head)->alh_ctr_##name)
#define _ALIST_CNT_PRINT(head, name)	\
	printf("%-24s = %"PRIu64"\n", #name, (head)->alh_ctr_##name)
#define ALIST_DUMPSTAT(head)						\
	do {								\
		_ALIST_CNT_PRINT(head, inserted);			\
		_ALIST_CNT_PRINT(head, removed_alreadymarked);		\
		_ALIST_CNT_PRINT(head, removed_markfailed);		\
		_ALIST_CNT_PRINT(head, removed_firsttime);		\
		_ALIST_CNT_PRINT(head, removed_casfailed);		\
		_ALIST_CNT_PRINT(head, remove_iterate);			\
		_ALIST_CNT_PRINT(head, remove_iterate_casfail);		\
		_ALIST_CNT_PRINT(head, remove_iterate_already);		\
		_ALIST_CNT_PRINT(head, remove_iterate_removed);		\
		_ALIST_CNT_PRINT(head, remove_reserved);		\
		_ALIST_CNT_PRINT(head, unref_cas_failed);		\
		_ALIST_CNT_PRINT(head, free_called);			\
	} while (0/*CONSTCOND*/)
#endif /* ALISTDEBUG */

#define ALIST_HEAD(name, type)						\
struct name {								\
	struct type *alh_first; /* list head */				\
	struct type *alh_rfirst; /* removed (reserved) list head */	\
	unsigned int alh_refcnt;					\
	/* counters */							\
	_ALIST_CNT_DECL(inserted)					\
	_ALIST_CNT_DECL(removed_alreadymarked)				\
	_ALIST_CNT_DECL(removed_markfailed)				\
	_ALIST_CNT_DECL(removed_firsttime)				\
	_ALIST_CNT_DECL(removed_casfailed)				\
	_ALIST_CNT_DECL(remove_iterate)					\
	_ALIST_CNT_DECL(remove_iterate_casfail)				\
	_ALIST_CNT_DECL(remove_iterate_already)				\
	_ALIST_CNT_DECL(remove_iterate_removed)				\
	_ALIST_CNT_DECL(remove_reserved)				\
	_ALIST_CNT_DECL(unref_cas_failed)				\
	_ALIST_CNT_DECL(free_called)					\
} __aligned(COHERENCY_UNIT)

#define ALIST_HEAD_INITIALIZER(head)					\
	{ .alh_first = NULL, .alh_rfirst = NULL, .alh_refcnt = 0 }

#define ALIST_ENTRY(type)						\
struct {								\
	struct type *ale_next;						\
	struct type *ale_rnext;						\
}

#define ALIST_FIRST(head)		((head)->alh_first)
#define ALIST_END(head)			NULL
#define ALIST_EMPTY(head)		((head)->alh_first == NULL)
#define ALIST_NEXT(elm, field)		((elm)->field.ale_next)

#define _ALIST_RFIRST(head)		((head)->alh_rfirst)
#define _ALIST_RNEXT(elm, field)	((elm)->field.ale_rnext)

#define ALIST_INIT(head)						\
	do {								\
		ALIST_FIRST(head) = ALIST_END(head);			\
	} while (/*CONSTCOND*/0)

#define ALIST_INSERT_HEAD(head, elm, field)				\
	do for (;;) {							\
		__typeof(*(elm)) *__al_i_elm = ALIST_FIRST(head);	\
		ALIST_NEXT(elm, field) = __al_i_elm;			\
		if (atomic_cas_ptr(&ALIST_FIRST(head),			\
		    __al_i_elm, (elm)) != __al_i_elm) {			\
			/* retry until it succeeds */			\
			continue;					\
		}							\
		_ALIST_CNT_INC(head, inserted);				\
		break;							\
	} while (0/*CONSTCOND*/)

#define _ALIST_RESERVE(head, elm, field)				\
	do for (;;) {							\
		__typeof(*(elm)) *__al_i_elm = _ALIST_RFIRST(head);	\
		_ALIST_RNEXT(elm, field) = __al_i_elm;			\
		if (atomic_cas_ptr(&_ALIST_RFIRST(head),		\
		    __al_i_elm, (elm)) != __al_i_elm)			\
			continue;					\
		_ALIST_CNT_INC(head, remove_reserved);			\
		break;							\
	} while (0/*CONSTCOND*/)

/* Is this element is marked as removed? */
#define ALIST_REMOVED_P(elm, field)					\
	_ALIST_PTR_MARKED_P(ALIST_NEXT((elm), field))

/*
 * The element being deleted may still be in the list.
 * Elements marked with REMOVED will be skipped.
 */
#define ALIST_FOREACH(ppvar, var, head, field)				\
	for ((ppvar) = &ALIST_FIRST(head), (var) = *(ppvar);		\
	    (var) != NULL;						\
	    (_ALIST_UNMARK_PTR(*(ppvar)) == (var)) ?			\
	    ((ppvar) = &ALIST_NEXT((var), field)) : 0,			\
	    (var) = _ALIST_UNMARK_PTR(*(ppvar)))			\
		if (!_ALIST_PTR_MARKED_P(ALIST_NEXT((var), field)))

/*
 * If a collision occurs, just mark it. it is not actually removed.
 * To remove it from the list completely, use ALIST_PURGE_REMOVED().
 */
#define ALIST_REMOVE_ASYNC(head, pp, elm, field)			\
	do for (;;) {							\
		__typeof(*(elm)) *__al_elm1, *__al_elm2;		\
		__al_elm1 = ALIST_NEXT((elm), field);			\
		__al_elm2 = _ALIST_MARK_PTR(__al_elm1);			\
		if (_ALIST_PTR_MARKED_P(__al_elm1)) {			\
			/*						\
			 * already marked.				\
			 * will be removed by other thread		\
			 */						\
			_ALIST_CNT_INC(head, removed_alreadymarked);	\
			break;						\
		} else if (atomic_cas_ptr(&ALIST_NEXT((elm), field),	\
		    __al_elm1, __al_elm2) != __al_elm1) {		\
			/*						\
			 * mark failed.					\
			 * other threads inserted or removed after me?	\
			 * retry to mark.				\
			 */						\
			_ALIST_CNT_INC(head, removed_markfailed);	\
			continue;					\
		} else {						\
			__al_elm1 = (elm);				\
			__al_elm2 = _ALIST_UNMARK_PTR(__al_elm2);	\
			if (atomic_cas_ptr((pp), __al_elm1, __al_elm2)	\
				    == __al_elm1) {			\
				_ALIST_CNT_INC(head, removed_firsttime);\
				_ALIST_RESERVE(head, elm, field);	\
				break;					\
			}						\
			/*						\
			 * The element could not be removed from the	\
			 * list. (previous element is removed?)		\
			 * but this element is marked for REMOVED.	\
			 */						\
			_ALIST_CNT_INC(head, removed_casfailed);	\
		}							\
		break;							\
	} while (0/*CONSTCOND*/)

#define ALIST_PURGE_REMOVED(head, field)				\
	do for (;;) {							\
		__typeof(*((head)->alh_first)) **__al_pp;		\
		__typeof(*((head)->alh_first)) *__al_elm;		\
		__typeof(*((head)->alh_first)) *__al_elm1;		\
		__typeof(*((head)->alh_first)) *__al_elm2;		\
		/* iterate from head */					\
		_ALIST_CNT_INC(head, remove_iterate);			\
		__al_pp = &ALIST_FIRST(head);				\
		for (;;) {						\
			__al_elm = _ALIST_UNMARK_PTR(*__al_pp);		\
			if (__al_elm == NULL)				\
				break;					\
			__al_elm1 = ALIST_NEXT(__al_elm, field);	\
			if (_ALIST_PTR_MARKED_P(__al_elm1)) {		\
				__al_elm2 =				\
				    _ALIST_UNMARK_PTR(__al_elm1);	\
				if ((__al_elm1 =			\
				    atomic_cas_ptr(__al_pp, __al_elm,	\
				    __al_elm2)) != __al_elm) {		\
					/* retry from head */		\
					_ALIST_CNT_INC(head,		\
					    remove_iterate_casfail);	\
					__al_pp = &ALIST_FIRST(head);	\
					continue;			\
				} else if (__al_elm1 == __al_elm2) {	\
					/* already removed. try next */	\
					_ALIST_CNT_INC(head,		\
					    remove_iterate_already);	\
					__al_pp = &ALIST_NEXT(		\
					    __al_elm2, field);		\
				} else {				\
					_ALIST_CNT_INC(head,		\
					    remove_iterate_removed);	\
					_ALIST_RESERVE(head, __al_elm,	\
					    field);			\
				}					\
			} else {					\
				__al_pp = &ALIST_NEXT(__al_elm, field);	\
			}						\
		}							\
		break;							\
	} while (0/*CONSTCOND*/)

#define ALIST_REF(head)							\
	atomic_inc_uint(&((head)->alh_refcnt))

#define ALIST_UNREF(head, field, _freefunc, _freearg)			\
	do for (;;) {							\
		__typeof(*((head)->alh_rfirst)) *__al_rp1, *__al_rp2;	\
		if ((head)->alh_refcnt == 1) {				\
			/*						\
			 * At this moment, refcnt could be >=2.		\
			 * However, ALIST_PURGE_REMOVED() can be	\
			 * executed in parallel without any problem.	\
			 */						\
			ALIST_PURGE_REMOVED(head, field);		\
		}							\
		__al_rp1 = (head)->alh_rfirst;				\
		if (atomic_dec_uint_nv(&((head)->alh_refcnt)) == 0) {	\
			__al_rp2 = atomic_cas_ptr(&(head)->alh_rfirst,	\
			    __al_rp1, NULL);				\
			if (__al_rp1 != __al_rp2) {			\
				/*					\
				 * The case of refcnt 1,2,1,0...	\
				 * If another thread does ALIST_REF,	\
				 * ALIST_REMOVE_ASYNC, or ALIST_UNREF	\
				 * between the time it reads alh_rfirst \
				 * and do atomic_dec_uint_nv()		\
				 */					\
				_ALIST_CNT_INC(head, unref_cas_failed);	\
				ALIST_REF(head);			\
				continue;				\
			}						\
			if (__al_rp1 == __al_rp2) {			\
				for (; __al_rp1 != NULL; __al_rp1 =	\
				    _ALIST_RNEXT(__al_rp1, field)) {	\
					_ALIST_CNT_INC(head,		\
					    free_called);		\
					_freefunc(head, __al_rp1,	\
					    _freearg);			\
				}					\
			}						\
		}							\
		break;							\
	} while (0/*CONSTCOND*/)

#endif /* _ALIST_H_ */