2  * Copyright 2010-2015 Samy Al Bahra.
14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
39  * This is an implementation of Anderson's array-based queuing lock.
42 	unsigned int locked;  member
52 	char pad[CK_MD_CACHELINE - sizeof(unsigned int) * 3 - sizeof(void *)];
64 	slots[0].locked = false;  in ck_spinlock_anderson_init()
67 		slots[i].locked = true;  in ck_spinlock_anderson_init()
71 	lock->slots = slots;  in ck_spinlock_anderson_init()
72 	lock->count = count;  in ck_spinlock_anderson_init()
73 	lock->mask = count - 1;  in ck_spinlock_anderson_init()
74 	lock->next = 0;  in ck_spinlock_anderson_init()
78 	 * appropriate wrap-around value in the case of next slot counter  in ck_spinlock_anderson_init()
81 	if (count & (count - 1))  in ck_spinlock_anderson_init()
82 		lock->wrap = (UINT_MAX % count) + 1;  in ck_spinlock_anderson_init()
84 		lock->wrap = 0;  in ck_spinlock_anderson_init()
96 	position = ck_pr_load_uint(&lock->next) & lock->mask;  in ck_spinlock_anderson_locked()
97 	r = ck_pr_load_uint(&lock->slots[position].locked);  in ck_spinlock_anderson_locked()
107 	unsigned int count = lock->count;  in ck_spinlock_anderson_lock()
112 	 * use a compare-and-swap.  in ck_spinlock_anderson_lock()
114 	if (lock->wrap != 0) {  in ck_spinlock_anderson_lock()
115 		position = ck_pr_load_uint(&lock->next);  in ck_spinlock_anderson_lock()
119 				next = lock->wrap;  in ck_spinlock_anderson_lock()
122 		} while (ck_pr_cas_uint_value(&lock->next, position,  in ck_spinlock_anderson_lock()
127 		position = ck_pr_faa_uint(&lock->next, 1);  in ck_spinlock_anderson_lock()
128 		position &= lock->mask;  in ck_spinlock_anderson_lock()
138 	while (ck_pr_load_uint(&lock->slots[position].locked) == true)  in ck_spinlock_anderson_lock()
141 	/* Prepare slot for potential re-use by another thread. */  in ck_spinlock_anderson_lock()
142 	ck_pr_store_uint(&lock->slots[position].locked, true);  in ck_spinlock_anderson_lock()
145 	*slot = lock->slots + position;  in ck_spinlock_anderson_lock()
158 	if (lock->wrap == 0)  in ck_spinlock_anderson_unlock()
159 		position = (slot->position + 1) & lock->mask;  in ck_spinlock_anderson_unlock()
161 		position = (slot->position + 1) % lock->count;  in ck_spinlock_anderson_unlock()
163 	ck_pr_store_uint(&lock->slots[position].locked, false);  in ck_spinlock_anderson_unlock()