^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) /* SPDX-License-Identifier: GPL-2.0 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * MCS lock defines
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) * This file contains the main data structure and API definitions of MCS lock.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) * The MCS lock (proposed by Mellor-Crummey and Scott) is a simple spin-lock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) * with the desirable properties of being fair, and with each cpu trying
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) * to acquire the lock spinning on a local variable.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) * It avoids expensive cache bouncings that common test-and-set spin-lock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) * implementations incur.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) #ifndef __LINUX_MCS_SPINLOCK_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) #define __LINUX_MCS_SPINLOCK_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) #include <asm/mcs_spinlock.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) struct mcs_spinlock {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) struct mcs_spinlock *next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) int locked; /* 1 if lock acquired */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) int count; /* nesting count, see qspinlock.c */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) #ifndef arch_mcs_spin_lock_contended
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) * Using smp_cond_load_acquire() provides the acquire semantics
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) * required so that subsequent operations happen after the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) * lock is acquired. Additionally, some architectures such as
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) * ARM64 would like to do spin-waiting instead of purely
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) * spinning, and smp_cond_load_acquire() provides that behavior.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) #define arch_mcs_spin_lock_contended(l) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) do { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) smp_cond_load_acquire(l, VAL); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) } while (0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) #ifndef arch_mcs_spin_unlock_contended
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) * smp_store_release() provides a memory barrier to ensure all
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) * operations in the critical section has been completed before
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) * unlocking.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) #define arch_mcs_spin_unlock_contended(l) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) smp_store_release((l), 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) * Note: the smp_load_acquire/smp_store_release pair is not
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) * sufficient to form a full memory barrier across
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) * cpus for many architectures (except x86) for mcs_unlock and mcs_lock.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) * For applications that need a full barrier across multiple cpus
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) * with mcs_unlock and mcs_lock pair, smp_mb__after_unlock_lock() should be
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) * used after mcs_lock.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) * In order to acquire the lock, the caller should declare a local node and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) * pass a reference of the node to this function in addition to the lock.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) * If the lock has already been acquired, then this will proceed to spin
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) * on this node->locked until the previous lock holder sets the node->locked
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) * in mcs_spin_unlock().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) static inline
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) struct mcs_spinlock *prev;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) /* Init node */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) node->locked = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) node->next = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) * We rely on the full barrier with global transitivity implied by the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) * below xchg() to order the initialization stores above against any
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) * observation of @node. And to provide the ACQUIRE ordering associated
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) * with a LOCK primitive.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) prev = xchg(lock, node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) if (likely(prev == NULL)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) * Lock acquired, don't need to set node->locked to 1. Threads
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) * only spin on its own node->locked value for lock acquisition.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) * However, since this thread can immediately acquire the lock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) * and does not proceed to spin on its own node->locked, this
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) * value won't be used. If a debug mode is needed to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) * audit lock status, then set node->locked value here.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) WRITE_ONCE(prev->next, node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) /* Wait until the lock holder passes the lock down. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) arch_mcs_spin_lock_contended(&node->locked);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) * Releases the lock. The caller should pass in the corresponding node that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) * was used to acquire the lock.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) static inline
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) struct mcs_spinlock *next = READ_ONCE(node->next);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) if (likely(!next)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) * Release the lock by setting it to NULL
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) if (likely(cmpxchg_release(lock, node, NULL) == node))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) /* Wait until the next pointer is set */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) while (!(next = READ_ONCE(node->next)))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) cpu_relax();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) /* Pass lock to next waiter. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) arch_mcs_spin_unlock_contended(&next->locked);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) #endif /* __LINUX_MCS_SPINLOCK_H */
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags