11fb62fb0SOlivier Houchard /*
21fb62fb0SOlivier Houchard * Copyright 2010-2015 Samy Al Bahra.
31fb62fb0SOlivier Houchard * All rights reserved.
41fb62fb0SOlivier Houchard *
51fb62fb0SOlivier Houchard * Redistribution and use in source and binary forms, with or without
61fb62fb0SOlivier Houchard * modification, are permitted provided that the following conditions
71fb62fb0SOlivier Houchard * are met:
81fb62fb0SOlivier Houchard * 1. Redistributions of source code must retain the above copyright
91fb62fb0SOlivier Houchard * notice, this list of conditions and the following disclaimer.
101fb62fb0SOlivier Houchard * 2. Redistributions in binary form must reproduce the above copyright
111fb62fb0SOlivier Houchard * notice, this list of conditions and the following disclaimer in the
121fb62fb0SOlivier Houchard * documentation and/or other materials provided with the distribution.
131fb62fb0SOlivier Houchard *
141fb62fb0SOlivier Houchard * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
151fb62fb0SOlivier Houchard * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
161fb62fb0SOlivier Houchard * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
171fb62fb0SOlivier Houchard * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
181fb62fb0SOlivier Houchard * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
191fb62fb0SOlivier Houchard * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
201fb62fb0SOlivier Houchard * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
211fb62fb0SOlivier Houchard * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
221fb62fb0SOlivier Houchard * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
231fb62fb0SOlivier Houchard * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
241fb62fb0SOlivier Houchard * SUCH DAMAGE.
251fb62fb0SOlivier Houchard */
261fb62fb0SOlivier Houchard
271fb62fb0SOlivier Houchard #ifndef CK_SPINLOCK_DEC_H
281fb62fb0SOlivier Houchard #define CK_SPINLOCK_DEC_H
291fb62fb0SOlivier Houchard
301fb62fb0SOlivier Houchard #include <ck_backoff.h>
311fb62fb0SOlivier Houchard #include <ck_cc.h>
321fb62fb0SOlivier Houchard #include <ck_elide.h>
331fb62fb0SOlivier Houchard #include <ck_pr.h>
341fb62fb0SOlivier Houchard #include <ck_stdbool.h>
351fb62fb0SOlivier Houchard
361fb62fb0SOlivier Houchard #ifndef CK_F_SPINLOCK_DEC
371fb62fb0SOlivier Houchard #define CK_F_SPINLOCK_DEC
381fb62fb0SOlivier Houchard /*
391fb62fb0SOlivier Houchard * This is similar to the CACAS lock but makes use of an atomic decrement
401fb62fb0SOlivier Houchard * operation to check if the lock value was decremented to 0 from 1. The
411fb62fb0SOlivier Houchard * idea is that a decrement operation is cheaper than a compare-and-swap.
421fb62fb0SOlivier Houchard */
431fb62fb0SOlivier Houchard struct ck_spinlock_dec {
441fb62fb0SOlivier Houchard unsigned int value;
451fb62fb0SOlivier Houchard };
461fb62fb0SOlivier Houchard typedef struct ck_spinlock_dec ck_spinlock_dec_t;
471fb62fb0SOlivier Houchard
481fb62fb0SOlivier Houchard #define CK_SPINLOCK_DEC_INITIALIZER {1}
491fb62fb0SOlivier Houchard
501fb62fb0SOlivier Houchard CK_CC_INLINE static void
ck_spinlock_dec_init(struct ck_spinlock_dec * lock)511fb62fb0SOlivier Houchard ck_spinlock_dec_init(struct ck_spinlock_dec *lock)
521fb62fb0SOlivier Houchard {
531fb62fb0SOlivier Houchard
541fb62fb0SOlivier Houchard lock->value = 1;
551fb62fb0SOlivier Houchard ck_pr_barrier();
561fb62fb0SOlivier Houchard return;
571fb62fb0SOlivier Houchard }
581fb62fb0SOlivier Houchard
591fb62fb0SOlivier Houchard CK_CC_INLINE static bool
ck_spinlock_dec_trylock(struct ck_spinlock_dec * lock)601fb62fb0SOlivier Houchard ck_spinlock_dec_trylock(struct ck_spinlock_dec *lock)
611fb62fb0SOlivier Houchard {
621fb62fb0SOlivier Houchard unsigned int value;
631fb62fb0SOlivier Houchard
641fb62fb0SOlivier Houchard value = ck_pr_fas_uint(&lock->value, 0);
651fb62fb0SOlivier Houchard ck_pr_fence_lock();
661fb62fb0SOlivier Houchard return value == 1;
671fb62fb0SOlivier Houchard }
681fb62fb0SOlivier Houchard
691fb62fb0SOlivier Houchard CK_CC_INLINE static bool
ck_spinlock_dec_locked(struct ck_spinlock_dec * lock)701fb62fb0SOlivier Houchard ck_spinlock_dec_locked(struct ck_spinlock_dec *lock)
711fb62fb0SOlivier Houchard {
721fb62fb0SOlivier Houchard bool r;
731fb62fb0SOlivier Houchard
741fb62fb0SOlivier Houchard r = ck_pr_load_uint(&lock->value) != 1;
751fb62fb0SOlivier Houchard ck_pr_fence_acquire();
761fb62fb0SOlivier Houchard return r;
771fb62fb0SOlivier Houchard }
781fb62fb0SOlivier Houchard
791fb62fb0SOlivier Houchard CK_CC_INLINE static void
ck_spinlock_dec_lock(struct ck_spinlock_dec * lock)801fb62fb0SOlivier Houchard ck_spinlock_dec_lock(struct ck_spinlock_dec *lock)
811fb62fb0SOlivier Houchard {
821fb62fb0SOlivier Houchard bool r;
831fb62fb0SOlivier Houchard
841fb62fb0SOlivier Houchard for (;;) {
851fb62fb0SOlivier Houchard /*
861fb62fb0SOlivier Houchard * Only one thread is guaranteed to decrement lock to 0.
871fb62fb0SOlivier Houchard * Overflow must be protected against. No more than
881fb62fb0SOlivier Houchard * UINT_MAX lock requests can happen while the lock is held.
891fb62fb0SOlivier Houchard */
901fb62fb0SOlivier Houchard ck_pr_dec_uint_zero(&lock->value, &r);
911fb62fb0SOlivier Houchard if (r == true)
921fb62fb0SOlivier Houchard break;
931fb62fb0SOlivier Houchard
941fb62fb0SOlivier Houchard /* Load value without generating write cycles. */
951fb62fb0SOlivier Houchard while (ck_pr_load_uint(&lock->value) != 1)
961fb62fb0SOlivier Houchard ck_pr_stall();
971fb62fb0SOlivier Houchard }
981fb62fb0SOlivier Houchard
991fb62fb0SOlivier Houchard ck_pr_fence_lock();
1001fb62fb0SOlivier Houchard return;
1011fb62fb0SOlivier Houchard }
1021fb62fb0SOlivier Houchard
1031fb62fb0SOlivier Houchard CK_CC_INLINE static void
ck_spinlock_dec_lock_eb(struct ck_spinlock_dec * lock)1041fb62fb0SOlivier Houchard ck_spinlock_dec_lock_eb(struct ck_spinlock_dec *lock)
1051fb62fb0SOlivier Houchard {
1061fb62fb0SOlivier Houchard ck_backoff_t backoff = CK_BACKOFF_INITIALIZER;
1071fb62fb0SOlivier Houchard bool r;
1081fb62fb0SOlivier Houchard
1091fb62fb0SOlivier Houchard for (;;) {
1101fb62fb0SOlivier Houchard ck_pr_dec_uint_zero(&lock->value, &r);
1111fb62fb0SOlivier Houchard if (r == true)
1121fb62fb0SOlivier Houchard break;
1131fb62fb0SOlivier Houchard
114*271ce402SOlivier Houchard while (ck_pr_load_uint(&lock->value) != 1)
1151fb62fb0SOlivier Houchard ck_backoff_eb(&backoff);
1161fb62fb0SOlivier Houchard }
1171fb62fb0SOlivier Houchard
1181fb62fb0SOlivier Houchard ck_pr_fence_lock();
1191fb62fb0SOlivier Houchard return;
1201fb62fb0SOlivier Houchard }
1211fb62fb0SOlivier Houchard
1221fb62fb0SOlivier Houchard CK_CC_INLINE static void
ck_spinlock_dec_unlock(struct ck_spinlock_dec * lock)1231fb62fb0SOlivier Houchard ck_spinlock_dec_unlock(struct ck_spinlock_dec *lock)
1241fb62fb0SOlivier Houchard {
1251fb62fb0SOlivier Houchard
1261fb62fb0SOlivier Houchard ck_pr_fence_unlock();
1271fb62fb0SOlivier Houchard
1281fb62fb0SOlivier Houchard /*
1291fb62fb0SOlivier Houchard * Unconditionally set lock value to 1 so someone can decrement lock
1301fb62fb0SOlivier Houchard * to 0.
1311fb62fb0SOlivier Houchard */
1321fb62fb0SOlivier Houchard ck_pr_store_uint(&lock->value, 1);
1331fb62fb0SOlivier Houchard return;
1341fb62fb0SOlivier Houchard }
1351fb62fb0SOlivier Houchard
1361fb62fb0SOlivier Houchard CK_ELIDE_PROTOTYPE(ck_spinlock_dec, ck_spinlock_dec_t,
1371fb62fb0SOlivier Houchard ck_spinlock_dec_locked, ck_spinlock_dec_lock,
1381fb62fb0SOlivier Houchard ck_spinlock_dec_locked, ck_spinlock_dec_unlock)
1391fb62fb0SOlivier Houchard
1401fb62fb0SOlivier Houchard CK_ELIDE_TRYLOCK_PROTOTYPE(ck_spinlock_dec, ck_spinlock_dec_t,
1411fb62fb0SOlivier Houchard ck_spinlock_dec_locked, ck_spinlock_dec_trylock)
1421fb62fb0SOlivier Houchard
1431fb62fb0SOlivier Houchard #endif /* CK_F_SPINLOCK_DEC */
1441fb62fb0SOlivier Houchard #endif /* CK_SPINLOCK_DEC_H */
145