| /* plock - progressive locks |
| * |
| * Copyright (C) 2012-2017 Willy Tarreau <w@1wt.eu> |
| * |
| * Permission is hereby granted, free of charge, to any person obtaining |
| * a copy of this software and associated documentation files (the |
| * "Software"), to deal in the Software without restriction, including |
| * without limitation the rights to use, copy, modify, merge, publish, |
| * distribute, sublicense, and/or sell copies of the Software, and to |
| * permit persons to whom the Software is furnished to do so, subject to |
| * the following conditions: |
| * |
| * The above copyright notice and this permission notice shall be |
| * included in all copies or substantial portions of the Software. |
| * |
| * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
| * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES |
| * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
| * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT |
| * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, |
| * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
| * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR |
| * OTHER DEALINGS IN THE SOFTWARE. |
| */ |
| |
| #include "atomic-ops.h" |
| #ifdef _POSIX_PRIORITY_SCHEDULING |
| #include <sched.h> |
| #endif |
| |
| /* 64 bit */ |
| #define PLOCK64_RL_1 0x0000000000000004ULL |
| #define PLOCK64_RL_2PL 0x00000000FFFFFFF8ULL |
| #define PLOCK64_RL_ANY 0x00000000FFFFFFFCULL |
| #define PLOCK64_SL_1 0x0000000100000000ULL |
| #define PLOCK64_SL_ANY 0x0000000300000000ULL |
| #define PLOCK64_WL_1 0x0000000400000000ULL |
| #define PLOCK64_WL_2PL 0xFFFFFFF800000000ULL |
| #define PLOCK64_WL_ANY 0xFFFFFFFC00000000ULL |
| |
| /* 32 bit */ |
| #define PLOCK32_RL_1 0x00000004 |
| #define PLOCK32_RL_2PL 0x0000FFF8 |
| #define PLOCK32_RL_ANY 0x0000FFFC |
| #define PLOCK32_SL_1 0x00010000 |
| #define PLOCK32_SL_ANY 0x00030000 |
| #define PLOCK32_WL_1 0x00040000 |
| #define PLOCK32_WL_2PL 0xFFF80000 |
| #define PLOCK32_WL_ANY 0xFFFC0000 |
| |
| /* dereferences <*p> as unsigned long without causing aliasing issues */ |
| #define pl_deref_long(p) ({ volatile unsigned long *__pl_l = (unsigned long *)(p); *__pl_l; }) |
| |
| /* dereferences <*p> as unsigned int without causing aliasing issues */ |
| #define pl_deref_int(p) ({ volatile unsigned int *__pl_i = (unsigned int *)(p); *__pl_i; }) |
| |
| /* This function waits for <lock> to release all bits covered by <mask>, and |
| * enforces an exponential backoff using CPU pauses to limit the pollution to |
| * the other threads' caches. The progression follows (1.5^N)-1, limited to |
| * 16384 iterations, which is way sufficient even for very large numbers of |
| * threads. It's possible to disable exponential backoff (EBO) for debugging |
| * purposes by setting PLOCK_DISABLE_EBO, in which case the function will be |
| * replaced with a simpler macro. This may for example be useful to more |
| * easily track callers' CPU usage. The macro was not designed to be used |
| * outside of the functions defined here. |
| */ |
| #if defined(PLOCK_DISABLE_EBO) |
| #define pl_wait_unlock_long(lock, mask) \ |
| ({ \ |
| unsigned long _r; \ |
| do { \ |
| pl_cpu_relax(); \ |
| _r = pl_deref_long(lock); \ |
| } while (_r & mask); \ |
| _r; /* return value */ \ |
| }) |
| #else |
| __attribute__((unused,noinline,no_instrument_function)) |
| static unsigned long pl_wait_unlock_long(const unsigned long *lock, const unsigned long mask) |
| { |
| unsigned long ret; |
| unsigned int m = 0; |
| |
| do { |
| unsigned int loops = m; |
| |
| #ifdef _POSIX_PRIORITY_SCHEDULING |
| if (loops >= 65536) { |
| sched_yield(); |
| loops -= 32768; |
| } |
| #endif |
| for (; loops >= 200; loops -= 10) |
| pl_cpu_relax(); |
| |
| for (; loops >= 1; loops--) |
| pl_barrier(); |
| |
| ret = pl_deref_long(lock); |
| if (__builtin_expect(ret & mask, 0) == 0) |
| break; |
| |
| /* the below produces an exponential growth with loops to lower |
| * values and still growing. This allows competing threads to |
| * wait different times once the threshold is reached. |
| */ |
| m = ((m + (m >> 1)) + 2) & 0x3ffff; |
| } while (1); |
| |
| return ret; |
| } |
| #endif /* PLOCK_DISABLE_EBO */ |
| |
| /* This function waits for <lock> to release all bits covered by <mask>, and |
| * enforces an exponential backoff using CPU pauses to limit the pollution to |
| * the other threads' caches. The progression follows (2^N)-1, limited to 255 |
| * iterations, which is way sufficient even for very large numbers of threads. |
| * The function slightly benefits from size optimization under gcc, but Clang |
| * cannot do it, so it's not done here, as it doesn't make a big difference. |
| * It is possible to disable exponential backoff (EBO) for debugging purposes |
| * by setting PLOCK_DISABLE_EBO, in which case the function will be replaced |
| * with a simpler macro. This may for example be useful to more easily track |
| * callers' CPU usage. The macro was not designed to be used outside of the |
| * functions defined here. |
| */ |
| #if defined(PLOCK_DISABLE_EBO) |
| #define pl_wait_unlock_int(lock, mask) \ |
| ({ \ |
| unsigned int _r; \ |
| do { \ |
| pl_cpu_relax(); \ |
| _r = pl_deref_int(lock); \ |
| } while (_r & mask); \ |
| _r; /* return value */ \ |
| }) |
| #else |
| __attribute__((unused,noinline,no_instrument_function)) |
| static unsigned int pl_wait_unlock_int(const unsigned int *lock, const unsigned int mask) |
| { |
| unsigned int ret; |
| unsigned int m = 0; |
| |
| do { |
| unsigned int loops = m; |
| |
| #ifdef _POSIX_PRIORITY_SCHEDULING |
| if (loops >= 65536) { |
| sched_yield(); |
| loops -= 32768; |
| } |
| #endif |
| for (; loops >= 200; loops -= 10) |
| pl_cpu_relax(); |
| |
| for (; loops >= 1; loops--) |
| pl_barrier(); |
| |
| ret = pl_deref_int(lock); |
| if (__builtin_expect(ret & mask, 0) == 0) |
| break; |
| |
| /* the below produces an exponential growth with loops to lower |
| * values and still growing. This allows competing threads to |
| * wait different times once the threshold is reached. |
| */ |
| m = ((m + (m >> 1)) + 2) & 0x3ffff; |
| } while (1); |
| |
| return ret; |
| } |
| #endif /* PLOCK_DISABLE_EBO */ |
| |
| /* This function waits for <lock> to change from value <prev> and returns the |
| * new value. It enforces an exponential backoff using CPU pauses to limit the |
| * pollution to the other threads' caches. The progression follows (2^N)-1, |
| * limited to 255 iterations, which is way sufficient even for very large |
| * numbers of threads. It is designed to be called after a first test which |
| * retrieves the previous value, so it starts by waiting. The function slightly |
| * benefits from size optimization under gcc, but Clang cannot do it, so it's |
| * not done here, as it doesn't make a big difference. |
| */ |
| __attribute__((unused,noinline,no_instrument_function)) |
| static unsigned long pl_wait_new_long(const unsigned long *lock, const unsigned long prev) |
| { |
| unsigned char m = 0; |
| unsigned long curr; |
| |
| do { |
| unsigned char loops = m + 1; |
| m = (m << 1) + 1; |
| do { |
| pl_cpu_relax(); |
| } while (__builtin_expect(--loops, 0)); |
| curr = pl_deref_long(lock); |
| } while (__builtin_expect(curr == prev, 0)); |
| return curr; |
| } |
| |
| /* This function waits for <lock> to change from value <prev> and returns the |
| * new value. It enforces an exponential backoff using CPU pauses to limit the |
| * pollution to the other threads' caches. The progression follows (2^N)-1, |
| * limited to 255 iterations, which is way sufficient even for very large |
| * numbers of threads. It is designed to be called after a first test which |
| * retrieves the previous value, so it starts by waiting. The function slightly |
| * benefits from size optimization under gcc, but Clang cannot do it, so it's |
| * not done here, as it doesn't make a big difference. |
| */ |
| __attribute__((unused,noinline,no_instrument_function)) |
| static unsigned int pl_wait_new_int(const unsigned int *lock, const unsigned int prev) |
| { |
| unsigned char m = 0; |
| unsigned int curr; |
| |
| do { |
| unsigned char loops = m + 1; |
| m = (m << 1) + 1; |
| do { |
| pl_cpu_relax(); |
| } while (__builtin_expect(--loops, 0)); |
| curr = pl_deref_int(lock); |
| } while (__builtin_expect(curr == prev, 0)); |
| return curr; |
| } |
| |
| /* request shared read access (R), return non-zero on success, otherwise 0 */ |
| #define pl_try_r(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| register unsigned long __pl_r = pl_deref_long(lock) & PLOCK64_WL_ANY; \ |
| pl_barrier(); \ |
| if (!__builtin_expect(__pl_r, 0)) { \ |
| __pl_r = pl_xadd((lock), PLOCK64_RL_1) & PLOCK64_WL_ANY; \ |
| if (__builtin_expect(__pl_r, 0)) \ |
| pl_sub((lock), PLOCK64_RL_1); \ |
| } \ |
| !__pl_r; /* return value */ \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| register unsigned int __pl_r = pl_deref_int(lock) & PLOCK32_WL_ANY; \ |
| pl_barrier(); \ |
| if (!__builtin_expect(__pl_r, 0)) { \ |
| __pl_r = pl_xadd((lock), PLOCK32_RL_1) & PLOCK32_WL_ANY; \ |
| if (__builtin_expect(__pl_r, 0)) \ |
| pl_sub((lock), PLOCK32_RL_1); \ |
| } \ |
| !__pl_r; /* return value */ \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_try_r__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_try_r__(__FILE__,__LINE__); \ |
| 0; \ |
| }) \ |
| ) |
| |
| /* request shared read access (R) and wait for it. In order not to disturb a W |
| * lock waiting for all readers to leave, we first check if a W lock is held |
| * before trying to claim the R lock. |
| */ |
| #define pl_take_r(lock) \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| register unsigned long *__lk_r = (unsigned long *)(lock); \ |
| register unsigned long __set_r = PLOCK64_RL_1; \ |
| register unsigned long __msk_r = PLOCK64_WL_ANY; \ |
| while (1) { \ |
| if (__builtin_expect(pl_deref_long(__lk_r) & __msk_r, 0)) \ |
| pl_wait_unlock_long(__lk_r, __msk_r); \ |
| if (!__builtin_expect(pl_xadd(__lk_r, __set_r) & __msk_r, 0)) \ |
| break; \ |
| pl_sub(__lk_r, __set_r); \ |
| } \ |
| pl_barrier(); \ |
| 0; \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| register unsigned int *__lk_r = (unsigned int *)(lock); \ |
| register unsigned int __set_r = PLOCK32_RL_1; \ |
| register unsigned int __msk_r = PLOCK32_WL_ANY; \ |
| while (1) { \ |
| if (__builtin_expect(pl_deref_int(__lk_r) & __msk_r, 0)) \ |
| pl_wait_unlock_int(__lk_r, __msk_r); \ |
| if (!__builtin_expect(pl_xadd(__lk_r, __set_r) & __msk_r, 0)) \ |
| break; \ |
| pl_sub(__lk_r, __set_r); \ |
| } \ |
| pl_barrier(); \ |
| 0; \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_take_r__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_take_r__(__FILE__,__LINE__); \ |
| 0; \ |
| }) |
| |
| /* release the read access (R) lock */ |
| #define pl_drop_r(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| pl_barrier(); \ |
| pl_sub(lock, PLOCK64_RL_1); \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| pl_barrier(); \ |
| pl_sub(lock, PLOCK32_RL_1); \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_drop_r__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_drop_r__(__FILE__,__LINE__); \ |
| }) \ |
| ) |
| |
| /* request a seek access (S), return non-zero on success, otherwise 0 */ |
| #define pl_try_s(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| register unsigned long __pl_r = pl_deref_long(lock); \ |
| pl_barrier(); \ |
| if (!__builtin_expect(__pl_r & (PLOCK64_WL_ANY | PLOCK64_SL_ANY), 0)) { \ |
| __pl_r = pl_xadd((lock), PLOCK64_SL_1 | PLOCK64_RL_1) & \ |
| (PLOCK64_WL_ANY | PLOCK64_SL_ANY); \ |
| if (__builtin_expect(__pl_r, 0)) \ |
| pl_sub((lock), PLOCK64_SL_1 | PLOCK64_RL_1); \ |
| } \ |
| !__pl_r; /* return value */ \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| register unsigned int __pl_r = pl_deref_int(lock); \ |
| pl_barrier(); \ |
| if (!__builtin_expect(__pl_r & (PLOCK32_WL_ANY | PLOCK32_SL_ANY), 0)) { \ |
| __pl_r = pl_xadd((lock), PLOCK32_SL_1 | PLOCK32_RL_1) & \ |
| (PLOCK32_WL_ANY | PLOCK32_SL_ANY); \ |
| if (__builtin_expect(__pl_r, 0)) \ |
| pl_sub((lock), PLOCK32_SL_1 | PLOCK32_RL_1); \ |
| } \ |
| !__pl_r; /* return value */ \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_try_s__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_try_s__(__FILE__,__LINE__); \ |
| 0; \ |
| }) \ |
| ) |
| |
| /* request a seek access (S) and wait for it. The lock is immediately claimed, |
| * and only upon failure an exponential backoff is used. S locks rarely compete |
| * with W locks so S will generally not disturb W. As the S lock may be used as |
| * a spinlock, it's important to grab it as fast as possible. |
| */ |
| #define pl_take_s(lock) \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| register unsigned long *__lk_r = (unsigned long *)(lock); \ |
| register unsigned long __set_r = PLOCK64_SL_1 | PLOCK64_RL_1; \ |
| register unsigned long __msk_r = PLOCK64_WL_ANY | PLOCK64_SL_ANY; \ |
| while (1) { \ |
| if (!__builtin_expect(pl_xadd(__lk_r, __set_r) & __msk_r, 0)) \ |
| break; \ |
| pl_sub(__lk_r, __set_r); \ |
| pl_wait_unlock_long(__lk_r, __msk_r); \ |
| } \ |
| pl_barrier(); \ |
| 0; \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| register unsigned int *__lk_r = (unsigned int *)(lock); \ |
| register unsigned int __set_r = PLOCK32_SL_1 | PLOCK32_RL_1; \ |
| register unsigned int __msk_r = PLOCK32_WL_ANY | PLOCK32_SL_ANY; \ |
| while (1) { \ |
| if (!__builtin_expect(pl_xadd(__lk_r, __set_r) & __msk_r, 0)) \ |
| break; \ |
| pl_sub(__lk_r, __set_r); \ |
| pl_wait_unlock_int(__lk_r, __msk_r); \ |
| } \ |
| pl_barrier(); \ |
| 0; \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_take_s__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_take_s__(__FILE__,__LINE__); \ |
| 0; \ |
| }) |
| |
| /* release the seek access (S) lock */ |
| #define pl_drop_s(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| pl_barrier(); \ |
| pl_sub(lock, PLOCK64_SL_1 + PLOCK64_RL_1); \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| pl_barrier(); \ |
| pl_sub(lock, PLOCK32_SL_1 + PLOCK32_RL_1); \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_drop_s__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_drop_s__(__FILE__,__LINE__); \ |
| }) \ |
| ) |
| |
| /* drop the S lock and go back to the R lock */ |
| #define pl_stor(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| pl_barrier(); \ |
| pl_sub(lock, PLOCK64_SL_1); \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| pl_barrier(); \ |
| pl_sub(lock, PLOCK32_SL_1); \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_stor__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_stor__(__FILE__,__LINE__); \ |
| }) \ |
| ) |
| |
| /* take the W lock under the S lock */ |
| #define pl_stow(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| register unsigned long __pl_r = pl_xadd((lock), PLOCK64_WL_1); \ |
| while ((__pl_r & PLOCK64_RL_ANY) != PLOCK64_RL_1) \ |
| __pl_r = pl_deref_long(lock); \ |
| pl_barrier(); \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| register unsigned int __pl_r = pl_xadd((lock), PLOCK32_WL_1); \ |
| while ((__pl_r & PLOCK32_RL_ANY) != PLOCK32_RL_1) \ |
| __pl_r = pl_deref_int(lock); \ |
| pl_barrier(); \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_stow__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_stow__(__FILE__,__LINE__); \ |
| }) \ |
| ) |
| |
| /* drop the W lock and go back to the S lock */ |
| #define pl_wtos(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| pl_barrier(); \ |
| pl_sub(lock, PLOCK64_WL_1); \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| pl_barrier(); \ |
| pl_sub(lock, PLOCK32_WL_1); \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_wtos__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_wtos__(__FILE__,__LINE__); \ |
| }) \ |
| ) |
| |
| /* drop the W lock and go back to the R lock */ |
| #define pl_wtor(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| pl_barrier(); \ |
| pl_sub(lock, PLOCK64_WL_1 | PLOCK64_SL_1); \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| pl_barrier(); \ |
| pl_sub(lock, PLOCK32_WL_1 | PLOCK32_SL_1); \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_wtor__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_wtor__(__FILE__,__LINE__); \ |
| }) \ |
| ) |
| |
| /* request a write access (W), return non-zero on success, otherwise 0. |
| * |
| * Below there is something important : by taking both W and S, we will cause |
| * an overflow of W at 4/5 of the maximum value that can be stored into W due |
| * to the fact that S is 2 bits, so we're effectively adding 5 to the word |
| * composed by W:S. But for all words multiple of 4 bits, the maximum value is |
| * multiple of 15 thus of 5. So the largest value we can store with all bits |
| * set to one will be met by adding 5, and then adding 5 again will place value |
| * 1 in W and value 0 in S, so we never leave W with 0. Also, even upon such an |
| * overflow, there's no risk to confuse it with an atomic lock because R is not |
| * null since it will not have overflown. For 32-bit locks, this situation |
| * happens when exactly 13108 threads try to grab the lock at once, W=1, S=0 |
| * and R=13108. For 64-bit locks, it happens at 858993460 concurrent writers |
| * where W=1, S=0 and R=858993460. |
| */ |
| #define pl_try_w(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| register unsigned long __pl_r = pl_deref_long(lock); \ |
| pl_barrier(); \ |
| if (!__builtin_expect(__pl_r & (PLOCK64_WL_ANY | PLOCK64_SL_ANY), 0)) { \ |
| __pl_r = pl_xadd((lock), PLOCK64_WL_1 | PLOCK64_SL_1 | PLOCK64_RL_1); \ |
| if (__builtin_expect(__pl_r & (PLOCK64_WL_ANY | PLOCK64_SL_ANY), 0)) { \ |
| /* a writer, seeker or atomic is present, let's leave */ \ |
| pl_sub((lock), PLOCK64_WL_1 | PLOCK64_SL_1 | PLOCK64_RL_1); \ |
| __pl_r &= (PLOCK64_WL_ANY | PLOCK64_SL_ANY); /* return value */\ |
| } else { \ |
| /* wait for all other readers to leave */ \ |
| while (__pl_r) \ |
| __pl_r = pl_deref_long(lock) - \ |
| (PLOCK64_WL_1 | PLOCK64_SL_1 | PLOCK64_RL_1); \ |
| } \ |
| } \ |
| !__pl_r; /* return value */ \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| register unsigned int __pl_r = pl_deref_int(lock); \ |
| pl_barrier(); \ |
| if (!__builtin_expect(__pl_r & (PLOCK32_WL_ANY | PLOCK32_SL_ANY), 0)) { \ |
| __pl_r = pl_xadd((lock), PLOCK32_WL_1 | PLOCK32_SL_1 | PLOCK32_RL_1); \ |
| if (__builtin_expect(__pl_r & (PLOCK32_WL_ANY | PLOCK32_SL_ANY), 0)) { \ |
| /* a writer, seeker or atomic is present, let's leave */ \ |
| pl_sub((lock), PLOCK32_WL_1 | PLOCK32_SL_1 | PLOCK32_RL_1); \ |
| __pl_r &= (PLOCK32_WL_ANY | PLOCK32_SL_ANY); /* return value */\ |
| } else { \ |
| /* wait for all other readers to leave */ \ |
| while (__pl_r) \ |
| __pl_r = pl_deref_int(lock) - \ |
| (PLOCK32_WL_1 | PLOCK32_SL_1 | PLOCK32_RL_1); \ |
| } \ |
| } \ |
| !__pl_r; /* return value */ \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_try_w__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_try_w__(__FILE__,__LINE__); \ |
| 0; \ |
| }) \ |
| ) |
| |
| /* request a write access (W) and wait for it. The lock is immediately claimed, |
| * and only upon failure an exponential backoff is used. |
| */ |
| #define pl_take_w(lock) \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| register unsigned long *__lk_r = (unsigned long *)(lock); \ |
| register unsigned long __set_r = PLOCK64_WL_1 | PLOCK64_SL_1 | PLOCK64_RL_1; \ |
| register unsigned long __msk_r = PLOCK64_WL_ANY | PLOCK64_SL_ANY; \ |
| register unsigned long __pl_r; \ |
| while (1) { \ |
| __pl_r = pl_xadd(__lk_r, __set_r); \ |
| if (!__builtin_expect(__pl_r & __msk_r, 0)) \ |
| break; \ |
| pl_sub(__lk_r, __set_r); \ |
| __pl_r = pl_wait_unlock_long(__lk_r, __msk_r); \ |
| } \ |
| /* wait for all other readers to leave */ \ |
| while (__builtin_expect(__pl_r, 0)) \ |
| __pl_r = pl_deref_long(__lk_r) - __set_r; \ |
| pl_barrier(); \ |
| 0; \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| register unsigned int *__lk_r = (unsigned int *)(lock); \ |
| register unsigned int __set_r = PLOCK32_WL_1 | PLOCK32_SL_1 | PLOCK32_RL_1; \ |
| register unsigned int __msk_r = PLOCK32_WL_ANY | PLOCK32_SL_ANY; \ |
| register unsigned int __pl_r; \ |
| while (1) { \ |
| __pl_r = pl_xadd(__lk_r, __set_r); \ |
| if (!__builtin_expect(__pl_r & __msk_r, 0)) \ |
| break; \ |
| pl_sub(__lk_r, __set_r); \ |
| __pl_r = pl_wait_unlock_int(__lk_r, __msk_r); \ |
| } \ |
| /* wait for all other readers to leave */ \ |
| while (__builtin_expect(__pl_r, 0)) \ |
| __pl_r = pl_deref_int(__lk_r) - __set_r; \ |
| pl_barrier(); \ |
| 0; \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_take_w__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_take_w__(__FILE__,__LINE__); \ |
| 0; \ |
| }) |
| |
| /* drop the write (W) lock entirely */ |
| #define pl_drop_w(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| pl_barrier(); \ |
| pl_sub(lock, PLOCK64_WL_1 | PLOCK64_SL_1 | PLOCK64_RL_1); \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| pl_barrier(); \ |
| pl_sub(lock, PLOCK32_WL_1 | PLOCK32_SL_1 | PLOCK32_RL_1); \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_drop_w__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_drop_w__(__FILE__,__LINE__); \ |
| }) \ |
| ) |
| |
| /* Try to upgrade from R to S, return non-zero on success, otherwise 0. |
| * This lock will fail if S or W are already held. In case of failure to grab |
| * the lock, it MUST NOT be retried without first dropping R, or it may never |
| * complete due to S waiting for R to leave before upgrading to W. |
| */ |
| #define pl_try_rtos(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| register unsigned long __pl_r = pl_deref_long(lock); \ |
| pl_barrier(); \ |
| if (!__builtin_expect(__pl_r & (PLOCK64_WL_ANY | PLOCK64_SL_ANY), 0)) { \ |
| __pl_r = pl_xadd((lock), PLOCK64_SL_1) & \ |
| (PLOCK64_WL_ANY | PLOCK64_SL_ANY); \ |
| if (__builtin_expect(__pl_r, 0)) \ |
| pl_sub((lock), PLOCK64_SL_1); \ |
| } \ |
| !__pl_r; /* return value */ \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| register unsigned int __pl_r = pl_deref_int(lock); \ |
| pl_barrier(); \ |
| if (!__builtin_expect(__pl_r & (PLOCK32_WL_ANY | PLOCK32_SL_ANY), 0)) { \ |
| __pl_r = pl_xadd((lock), PLOCK32_SL_1) & \ |
| (PLOCK32_WL_ANY | PLOCK32_SL_ANY); \ |
| if (__builtin_expect(__pl_r, 0)) \ |
| pl_sub((lock), PLOCK32_SL_1); \ |
| } \ |
| !__pl_r; /* return value */ \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_try_rtos__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_try_rtos__(__FILE__,__LINE__); \ |
| 0; \ |
| }) \ |
| ) |
| |
| |
| /* Try to upgrade from R to W, return non-zero on success, otherwise 0. |
| * This lock will fail if S or W are already held. In case of failure to grab |
| * the lock, it MUST NOT be retried without first dropping R, or it may never |
| * complete due to S waiting for R to leave before upgrading to W. It waits for |
| * the last readers to leave. |
| */ |
| #define pl_try_rtow(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| register unsigned long *__lk_r = (unsigned long *)(lock); \ |
| register unsigned long __set_r = PLOCK64_WL_1 | PLOCK64_SL_1; \ |
| register unsigned long __msk_r = PLOCK64_WL_ANY | PLOCK64_SL_ANY; \ |
| register unsigned long __pl_r; \ |
| pl_barrier(); \ |
| while (1) { \ |
| __pl_r = pl_xadd(__lk_r, __set_r); \ |
| if (__builtin_expect(__pl_r & __msk_r, 0)) { \ |
| if (pl_xadd(__lk_r, - __set_r)) \ |
| break; /* the caller needs to drop the lock now */ \ |
| continue; /* lock was released, try again */ \ |
| } \ |
| /* ok we're the only writer, wait for readers to leave */ \ |
| while (__builtin_expect(__pl_r, 0)) \ |
| __pl_r = pl_deref_long(__lk_r) - (PLOCK64_WL_1|PLOCK64_SL_1|PLOCK64_RL_1); \ |
| /* now return with __pl_r = 0 */ \ |
| break; \ |
| } \ |
| !__pl_r; /* return value */ \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| register unsigned int *__lk_r = (unsigned int *)(lock); \ |
| register unsigned int __set_r = PLOCK32_WL_1 | PLOCK32_SL_1; \ |
| register unsigned int __msk_r = PLOCK32_WL_ANY | PLOCK32_SL_ANY; \ |
| register unsigned int __pl_r; \ |
| pl_barrier(); \ |
| while (1) { \ |
| __pl_r = pl_xadd(__lk_r, __set_r); \ |
| if (__builtin_expect(__pl_r & __msk_r, 0)) { \ |
| if (pl_xadd(__lk_r, - __set_r)) \ |
| break; /* the caller needs to drop the lock now */ \ |
| continue; /* lock was released, try again */ \ |
| } \ |
| /* ok we're the only writer, wait for readers to leave */ \ |
| while (__builtin_expect(__pl_r, 0)) \ |
| __pl_r = pl_deref_int(__lk_r) - (PLOCK32_WL_1|PLOCK32_SL_1|PLOCK32_RL_1); \ |
| /* now return with __pl_r = 0 */ \ |
| break; \ |
| } \ |
| !__pl_r; /* return value */ \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_try_rtow__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_try_rtow__(__FILE__,__LINE__); \ |
| 0; \ |
| }) \ |
| ) |
| |
| |
| /* request atomic write access (A), return non-zero on success, otherwise 0. |
| * It's a bit tricky as we only use the W bits for this and want to distinguish |
| * between other atomic users and regular lock users. We have to give up if an |
| * S lock appears. It's possible that such a lock stays hidden in the W bits |
| * after an overflow, but in this case R is still held, ensuring we stay in the |
| * loop until we discover the conflict. The lock only return successfully if all |
| * readers are gone (or converted to A). |
| */ |
| #define pl_try_a(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| register unsigned long __pl_r = pl_deref_long(lock) & PLOCK64_SL_ANY; \ |
| pl_barrier(); \ |
| if (!__builtin_expect(__pl_r, 0)) { \ |
| __pl_r = pl_xadd((lock), PLOCK64_WL_1); \ |
| while (1) { \ |
| if (__builtin_expect(__pl_r & PLOCK64_SL_ANY, 0)) { \ |
| pl_sub((lock), PLOCK64_WL_1); \ |
| break; /* return !__pl_r */ \ |
| } \ |
| __pl_r &= PLOCK64_RL_ANY; \ |
| if (!__builtin_expect(__pl_r, 0)) \ |
| break; /* return !__pl_r */ \ |
| __pl_r = pl_deref_long(lock); \ |
| } \ |
| } \ |
| !__pl_r; /* return value */ \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| register unsigned int __pl_r = pl_deref_int(lock) & PLOCK32_SL_ANY; \ |
| pl_barrier(); \ |
| if (!__builtin_expect(__pl_r, 0)) { \ |
| __pl_r = pl_xadd((lock), PLOCK32_WL_1); \ |
| while (1) { \ |
| if (__builtin_expect(__pl_r & PLOCK32_SL_ANY, 0)) { \ |
| pl_sub((lock), PLOCK32_WL_1); \ |
| break; /* return !__pl_r */ \ |
| } \ |
| __pl_r &= PLOCK32_RL_ANY; \ |
| if (!__builtin_expect(__pl_r, 0)) \ |
| break; /* return !__pl_r */ \ |
| __pl_r = pl_deref_int(lock); \ |
| } \ |
| } \ |
| !__pl_r; /* return value */ \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_try_a__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_try_a__(__FILE__,__LINE__); \ |
| 0; \ |
| }) \ |
| ) |
| |
| /* request atomic write access (A) and wait for it. See comments in pl_try_a() for |
| * explanations. |
| */ |
| #define pl_take_a(lock) \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| register unsigned long *__lk_r = (unsigned long *)(lock); \ |
| register unsigned long __set_r = PLOCK64_WL_1; \ |
| register unsigned long __msk_r = PLOCK64_SL_ANY; \ |
| register unsigned long __pl_r; \ |
| __pl_r = pl_xadd(__lk_r, __set_r); \ |
| while (__builtin_expect(__pl_r & PLOCK64_RL_ANY, 0)) { \ |
| if (__builtin_expect(__pl_r & __msk_r, 0)) { \ |
| pl_sub(__lk_r, __set_r); \ |
| pl_wait_unlock_long(__lk_r, __msk_r); \ |
| __pl_r = pl_xadd(__lk_r, __set_r); \ |
| continue; \ |
| } \ |
| /* wait for all readers to leave or upgrade */ \ |
| pl_cpu_relax(); pl_cpu_relax(); pl_cpu_relax(); \ |
| __pl_r = pl_deref_long(lock); \ |
| } \ |
| pl_barrier(); \ |
| 0; \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| register unsigned int *__lk_r = (unsigned int *)(lock); \ |
| register unsigned int __set_r = PLOCK32_WL_1; \ |
| register unsigned int __msk_r = PLOCK32_SL_ANY; \ |
| register unsigned int __pl_r; \ |
| __pl_r = pl_xadd(__lk_r, __set_r); \ |
| while (__builtin_expect(__pl_r & PLOCK32_RL_ANY, 0)) { \ |
| if (__builtin_expect(__pl_r & __msk_r, 0)) { \ |
| pl_sub(__lk_r, __set_r); \ |
| pl_wait_unlock_int(__lk_r, __msk_r); \ |
| __pl_r = pl_xadd(__lk_r, __set_r); \ |
| continue; \ |
| } \ |
| /* wait for all readers to leave or upgrade */ \ |
| pl_cpu_relax(); pl_cpu_relax(); pl_cpu_relax(); \ |
| __pl_r = pl_deref_int(lock); \ |
| } \ |
| pl_barrier(); \ |
| 0; \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_take_a__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_take_a__(__FILE__,__LINE__); \ |
| 0; \ |
| }) |
| |
| /* release atomic write access (A) lock */ |
| #define pl_drop_a(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| pl_barrier(); \ |
| pl_sub(lock, PLOCK64_WL_1); \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| pl_barrier(); \ |
| pl_sub(lock, PLOCK32_WL_1); \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_drop_a__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_drop_a__(__FILE__,__LINE__); \ |
| }) \ |
| ) |
| |
| /* Downgrade A to R. Inc(R), dec(W) then wait for W==0 */ |
| #define pl_ator(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| register unsigned long *__lk_r = (unsigned long *)(lock); \ |
| register unsigned long __set_r = PLOCK64_RL_1 - PLOCK64_WL_1; \ |
| register unsigned long __msk_r = PLOCK64_WL_ANY; \ |
| register unsigned long __pl_r = pl_xadd(__lk_r, __set_r) + __set_r; \ |
| while (__builtin_expect(__pl_r & __msk_r, 0)) { \ |
| __pl_r = pl_wait_unlock_long(__lk_r, __msk_r); \ |
| } \ |
| pl_barrier(); \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| register unsigned int *__lk_r = (unsigned int *)(lock); \ |
| register unsigned int __set_r = PLOCK32_RL_1 - PLOCK32_WL_1; \ |
| register unsigned int __msk_r = PLOCK32_WL_ANY; \ |
| register unsigned int __pl_r = pl_xadd(__lk_r, __set_r) + __set_r; \ |
| while (__builtin_expect(__pl_r & __msk_r, 0)) { \ |
| __pl_r = pl_wait_unlock_int(__lk_r, __msk_r); \ |
| } \ |
| pl_barrier(); \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_ator__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_ator__(__FILE__,__LINE__); \ |
| }) \ |
| ) |
| |
| /* Try to upgrade from R to A, return non-zero on success, otherwise 0. |
| * This lock will fail if S is held or appears while waiting (typically due to |
| * a previous grab that was disguised as a W due to an overflow). In case of |
| * failure to grab the lock, it MUST NOT be retried without first dropping R, |
| * or it may never complete due to S waiting for R to leave before upgrading |
| * to W. The lock succeeds once there's no more R (ie all of them have either |
| * completed or were turned to A). |
| */ |
| #define pl_try_rtoa(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| register unsigned long __pl_r = pl_deref_long(lock) & PLOCK64_SL_ANY; \ |
| pl_barrier(); \ |
| if (!__builtin_expect(__pl_r, 0)) { \ |
| __pl_r = pl_xadd((lock), PLOCK64_WL_1 - PLOCK64_RL_1); \ |
| while (1) { \ |
| if (__builtin_expect(__pl_r & PLOCK64_SL_ANY, 0)) { \ |
| pl_sub((lock), PLOCK64_WL_1 - PLOCK64_RL_1); \ |
| break; /* return !__pl_r */ \ |
| } \ |
| __pl_r &= PLOCK64_RL_ANY; \ |
| if (!__builtin_expect(__pl_r, 0)) \ |
| break; /* return !__pl_r */ \ |
| __pl_r = pl_deref_long(lock); \ |
| } \ |
| } \ |
| !__pl_r; /* return value */ \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| register unsigned int __pl_r = pl_deref_int(lock) & PLOCK32_SL_ANY; \ |
| pl_barrier(); \ |
| if (!__builtin_expect(__pl_r, 0)) { \ |
| __pl_r = pl_xadd((lock), PLOCK32_WL_1 - PLOCK32_RL_1); \ |
| while (1) { \ |
| if (__builtin_expect(__pl_r & PLOCK32_SL_ANY, 0)) { \ |
| pl_sub((lock), PLOCK32_WL_1 - PLOCK32_RL_1); \ |
| break; /* return !__pl_r */ \ |
| } \ |
| __pl_r &= PLOCK32_RL_ANY; \ |
| if (!__builtin_expect(__pl_r, 0)) \ |
| break; /* return !__pl_r */ \ |
| __pl_r = pl_deref_int(lock); \ |
| } \ |
| } \ |
| !__pl_r; /* return value */ \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_try_rtoa__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_try_rtoa__(__FILE__,__LINE__); \ |
| 0; \ |
| }) \ |
| ) |
| |
| |
| /* |
| * The following operations cover the multiple writers model : U->R->J->C->A |
| */ |
| |
| |
| /* Upgrade R to J. Inc(W) then wait for R==W or S != 0 */ |
| #define pl_rtoj(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| register unsigned long *__lk_r = (unsigned long *)(lock); \ |
| register unsigned long __pl_r = pl_xadd(__lk_r, PLOCK64_WL_1) + PLOCK64_WL_1; \ |
| register unsigned char __m = 0; \ |
| while (!(__pl_r & PLOCK64_SL_ANY) && \ |
| (__pl_r / PLOCK64_WL_1 != (__pl_r & PLOCK64_RL_ANY) / PLOCK64_RL_1)) { \ |
| unsigned char __loops = __m + 1; \ |
| __m = (__m << 1) + 1; \ |
| do { \ |
| pl_cpu_relax(); \ |
| pl_cpu_relax(); \ |
| } while (--__loops); \ |
| __pl_r = pl_deref_long(__lk_r); \ |
| } \ |
| pl_barrier(); \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| register unsigned int *__lk_r = (unsigned int *)(lock); \ |
| register unsigned int __pl_r = pl_xadd(__lk_r, PLOCK32_WL_1) + PLOCK32_WL_1; \ |
| register unsigned char __m = 0; \ |
| while (!(__pl_r & PLOCK32_SL_ANY) && \ |
| (__pl_r / PLOCK32_WL_1 != (__pl_r & PLOCK32_RL_ANY) / PLOCK32_RL_1)) { \ |
| unsigned char __loops = __m + 1; \ |
| __m = (__m << 1) + 1; \ |
| do { \ |
| pl_cpu_relax(); \ |
| pl_cpu_relax(); \ |
| } while (--__loops); \ |
| __pl_r = pl_deref_int(__lk_r); \ |
| } \ |
| pl_barrier(); \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_rtoj__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_rtoj__(__FILE__,__LINE__); \ |
| }) \ |
| ) |
| |
| /* Upgrade J to C. Set S. Only one thread needs to do it though it's idempotent */ |
| #define pl_jtoc(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| register unsigned long *__lk_r = (unsigned long *)(lock); \ |
| register unsigned long __pl_r = pl_deref_long(__lk_r); \ |
| if (!(__pl_r & PLOCK64_SL_ANY)) \ |
| pl_or(__lk_r, PLOCK64_SL_1); \ |
| pl_barrier(); \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| register unsigned int *__lk_r = (unsigned int *)(lock); \ |
| register unsigned int __pl_r = pl_deref_int(__lk_r); \ |
| if (!(__pl_r & PLOCK32_SL_ANY)) \ |
| pl_or(__lk_r, PLOCK32_SL_1); \ |
| pl_barrier(); \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_jtoc__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_jtoc__(__FILE__,__LINE__); \ |
| }) \ |
| ) |
| |
| /* Upgrade R to C. Inc(W) then wait for R==W or S != 0 */ |
| #define pl_rtoc(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| register unsigned long *__lk_r = (unsigned long *)(lock); \ |
| register unsigned long __pl_r = pl_xadd(__lk_r, PLOCK64_WL_1) + PLOCK64_WL_1; \ |
| register unsigned char __m = 0; \ |
| while (__builtin_expect(!(__pl_r & PLOCK64_SL_ANY), 0)) { \ |
| unsigned char __loops; \ |
| if (__pl_r / PLOCK64_WL_1 == (__pl_r & PLOCK64_RL_ANY) / PLOCK64_RL_1) { \ |
| pl_or(__lk_r, PLOCK64_SL_1); \ |
| break; \ |
| } \ |
| __loops = __m + 1; \ |
| __m = (__m << 1) + 1; \ |
| do { \ |
| pl_cpu_relax(); \ |
| pl_cpu_relax(); \ |
| } while (--__loops); \ |
| __pl_r = pl_deref_long(__lk_r); \ |
| } \ |
| pl_barrier(); \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| register unsigned int *__lk_r = (unsigned int *)(lock); \ |
| register unsigned int __pl_r = pl_xadd(__lk_r, PLOCK32_WL_1) + PLOCK32_WL_1; \ |
| register unsigned char __m = 0; \ |
| while (__builtin_expect(!(__pl_r & PLOCK32_SL_ANY), 0)) { \ |
| unsigned char __loops; \ |
| if (__pl_r / PLOCK32_WL_1 == (__pl_r & PLOCK32_RL_ANY) / PLOCK32_RL_1) { \ |
| pl_or(__lk_r, PLOCK32_SL_1); \ |
| break; \ |
| } \ |
| __loops = __m + 1; \ |
| __m = (__m << 1) + 1; \ |
| do { \ |
| pl_cpu_relax(); \ |
| pl_cpu_relax(); \ |
| } while (--__loops); \ |
| __pl_r = pl_deref_int(__lk_r); \ |
| } \ |
| pl_barrier(); \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_rtoj__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_rtoj__(__FILE__,__LINE__); \ |
| }) \ |
| ) |
| |
| /* Drop the claim (C) lock : R--,W-- then clear S if !R */ |
| #define pl_drop_c(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| register unsigned long *__lk_r = (unsigned long *)(lock); \ |
| register unsigned long __set_r = - PLOCK64_RL_1 - PLOCK64_WL_1; \ |
| register unsigned long __pl_r = pl_xadd(__lk_r, __set_r) + __set_r; \ |
| if (!(__pl_r & PLOCK64_RL_ANY)) \ |
| pl_and(__lk_r, ~PLOCK64_SL_1); \ |
| pl_barrier(); \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| register unsigned int *__lk_r = (unsigned int *)(lock); \ |
| register unsigned int __set_r = - PLOCK32_RL_1 - PLOCK32_WL_1; \ |
| register unsigned int __pl_r = pl_xadd(__lk_r, __set_r) + __set_r; \ |
| if (!(__pl_r & PLOCK32_RL_ANY)) \ |
| pl_and(__lk_r, ~PLOCK32_SL_1); \ |
| pl_barrier(); \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_drop_c__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_drop_c__(__FILE__,__LINE__); \ |
| }) \ |
| ) |
| |
| /* Upgrade C to A. R-- then wait for !S or clear S if !R */ |
| #define pl_ctoa(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| register unsigned long *__lk_r = (unsigned long *)(lock); \ |
| register unsigned long __pl_r = pl_xadd(__lk_r, -PLOCK64_RL_1) - PLOCK64_RL_1; \ |
| while (__pl_r & PLOCK64_SL_ANY) { \ |
| if (!(__pl_r & PLOCK64_RL_ANY)) { \ |
| pl_and(__lk_r, ~PLOCK64_SL_1); \ |
| break; \ |
| } \ |
| pl_cpu_relax(); \ |
| pl_cpu_relax(); \ |
| __pl_r = pl_deref_long(__lk_r); \ |
| } \ |
| pl_barrier(); \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| register unsigned int *__lk_r = (unsigned int *)(lock); \ |
| register unsigned int __pl_r = pl_xadd(__lk_r, -PLOCK32_RL_1) - PLOCK32_RL_1; \ |
| while (__pl_r & PLOCK32_SL_ANY) { \ |
| if (!(__pl_r & PLOCK32_RL_ANY)) { \ |
| pl_and(__lk_r, ~PLOCK32_SL_1); \ |
| break; \ |
| } \ |
| pl_cpu_relax(); \ |
| pl_cpu_relax(); \ |
| __pl_r = pl_deref_int(__lk_r); \ |
| } \ |
| pl_barrier(); \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_ctoa__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_ctoa__(__FILE__,__LINE__); \ |
| }) \ |
| ) |
| |
| /* downgrade the atomic write access lock (A) to join (J) */ |
| #define pl_atoj(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| pl_barrier(); \ |
| pl_add(lock, PLOCK64_RL_1); \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| pl_barrier(); \ |
| pl_add(lock, PLOCK32_RL_1); \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_atoj__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_atoj__(__FILE__,__LINE__); \ |
| }) \ |
| ) |
| |
| /* Returns non-zero if the thread calling it is the last writer, otherwise zero. It is |
| * designed to be called before pl_drop_j(), pl_drop_c() or pl_drop_a() for operations |
| * which need to be called only once. |
| */ |
| #define pl_last_writer(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| !(pl_deref_long(lock) & PLOCK64_WL_2PL); \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| !(pl_deref_int(lock) & PLOCK32_WL_2PL); \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_last_j__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_last_j__(__FILE__,__LINE__); \ |
| 0; \ |
| }) \ |
| ) |
| |
| /* attempt to get an exclusive write access via the J lock and wait for it. |
| * Only one thread may succeed in this operation. It will not conflict with |
| * other users and will first wait for all writers to leave, then for all |
| * readers to leave before starting. This offers a solution to obtain an |
| * exclusive access to a shared resource in the R/J/C/A model. A concurrent |
| * take_a() will wait for this one to finish first. Using a CAS instead of XADD |
| * should make the operation converge slightly faster. Returns non-zero on |
| * success otherwise 0. |
| */ |
| #define pl_try_j(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| register unsigned long *__lk_r = (unsigned long *)(lock); \ |
| register unsigned long __set_r = PLOCK64_WL_1 | PLOCK64_RL_1; \ |
| register unsigned long __msk_r = PLOCK64_WL_ANY; \ |
| register unsigned long __pl_r; \ |
| register unsigned char __m; \ |
| pl_wait_unlock_long(__lk_r, __msk_r); \ |
| __pl_r = pl_xadd(__lk_r, __set_r) + __set_r; \ |
| /* wait for all other readers to leave */ \ |
| __m = 0; \ |
| while (__builtin_expect(__pl_r & PLOCK64_RL_2PL, 0)) { \ |
| unsigned char __loops; \ |
| /* give up on other writers */ \ |
| if (__builtin_expect(__pl_r & PLOCK64_WL_2PL, 0)) { \ |
| pl_sub(__lk_r, __set_r); \ |
| __pl_r = 0; /* failed to get the lock */ \ |
| break; \ |
| } \ |
| __loops = __m + 1; \ |
| __m = (__m << 1) + 1; \ |
| do { \ |
| pl_cpu_relax(); \ |
| pl_cpu_relax(); \ |
| } while (--__loops); \ |
| __pl_r = pl_deref_long(__lk_r); \ |
| } \ |
| pl_barrier(); \ |
| __pl_r; /* return value, cannot be null on success */ \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| register unsigned int *__lk_r = (unsigned int *)(lock); \ |
| register unsigned int __set_r = PLOCK32_WL_1 | PLOCK32_RL_1; \ |
| register unsigned int __msk_r = PLOCK32_WL_ANY; \ |
| register unsigned int __pl_r; \ |
| register unsigned char __m; \ |
| pl_wait_unlock_int(__lk_r, __msk_r); \ |
| __pl_r = pl_xadd(__lk_r, __set_r) + __set_r; \ |
| /* wait for all other readers to leave */ \ |
| __m = 0; \ |
| while (__builtin_expect(__pl_r & PLOCK32_RL_2PL, 0)) { \ |
| unsigned char __loops; \ |
| /* but rollback on other writers */ \ |
| if (__builtin_expect(__pl_r & PLOCK32_WL_2PL, 0)) { \ |
| pl_sub(__lk_r, __set_r); \ |
| __pl_r = 0; /* failed to get the lock */ \ |
| break; \ |
| } \ |
| __loops = __m + 1; \ |
| __m = (__m << 1) + 1; \ |
| do { \ |
| pl_cpu_relax(); \ |
| pl_cpu_relax(); \ |
| } while (--__loops); \ |
| __pl_r = pl_deref_int(__lk_r); \ |
| } \ |
| pl_barrier(); \ |
| __pl_r; /* return value, cannot be null on success */ \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_try_j__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_try_j__(__FILE__,__LINE__); \ |
| 0; \ |
| }) \ |
| ) |
| |
| /* request an exclusive write access via the J lock and wait for it. Only one |
| * thread may succeed in this operation. It will not conflict with other users |
| * and will first wait for all writers to leave, then for all readers to leave |
| * before starting. This offers a solution to obtain an exclusive access to a |
| * shared resource in the R/J/C/A model. A concurrent take_a() will wait for |
| * this one to finish first. Using a CAS instead of XADD should make the |
| * operation converge slightly faster. |
| */ |
| #define pl_take_j(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| __label__ __retry; \ |
| register unsigned long *__lk_r = (unsigned long *)(lock); \ |
| register unsigned long __set_r = PLOCK64_WL_1 | PLOCK64_RL_1; \ |
| register unsigned long __msk_r = PLOCK64_WL_ANY; \ |
| register unsigned long __pl_r; \ |
| register unsigned char __m; \ |
| __retry: \ |
| pl_wait_unlock_long(__lk_r, __msk_r); \ |
| __pl_r = pl_xadd(__lk_r, __set_r) + __set_r; \ |
| /* wait for all other readers to leave */ \ |
| __m = 0; \ |
| while (__builtin_expect(__pl_r & PLOCK64_RL_2PL, 0)) { \ |
| unsigned char __loops; \ |
| /* but rollback on other writers */ \ |
| if (__builtin_expect(__pl_r & PLOCK64_WL_2PL, 0)) { \ |
| pl_sub(__lk_r, __set_r); \ |
| goto __retry; \ |
| } \ |
| __loops = __m + 1; \ |
| __m = (__m << 1) + 1; \ |
| do { \ |
| pl_cpu_relax(); \ |
| pl_cpu_relax(); \ |
| } while (--__loops); \ |
| __pl_r = pl_deref_long(__lk_r); \ |
| } \ |
| pl_barrier(); \ |
| 0; \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| __label__ __retry; \ |
| register unsigned int *__lk_r = (unsigned int *)(lock); \ |
| register unsigned int __set_r = PLOCK32_WL_1 | PLOCK32_RL_1; \ |
| register unsigned int __msk_r = PLOCK32_WL_ANY; \ |
| register unsigned int __pl_r; \ |
| register unsigned char __m; \ |
| __retry: \ |
| pl_wait_unlock_int(__lk_r, __msk_r); \ |
| __pl_r = pl_xadd(__lk_r, __set_r) + __set_r; \ |
| /* wait for all other readers to leave */ \ |
| __m = 0; \ |
| while (__builtin_expect(__pl_r & PLOCK32_RL_2PL, 0)) { \ |
| unsigned char __loops; \ |
| /* but rollback on other writers */ \ |
| if (__builtin_expect(__pl_r & PLOCK32_WL_2PL, 0)) { \ |
| pl_sub(__lk_r, __set_r); \ |
| goto __retry; \ |
| } \ |
| __loops = __m + 1; \ |
| __m = (__m << 1) + 1; \ |
| do { \ |
| pl_cpu_relax(); \ |
| pl_cpu_relax(); \ |
| } while (--__loops); \ |
| __pl_r = pl_deref_int(__lk_r); \ |
| } \ |
| pl_barrier(); \ |
| 0; \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_take_j__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_take_j__(__FILE__,__LINE__); \ |
| 0; \ |
| }) \ |
| ) |
| |
| /* drop the join (J) lock entirely */ |
| #define pl_drop_j(lock) ( \ |
| (sizeof(long) == 8 && sizeof(*(lock)) == 8) ? ({ \ |
| pl_barrier(); \ |
| pl_sub(lock, PLOCK64_WL_1 | PLOCK64_RL_1); \ |
| }) : (sizeof(*(lock)) == 4) ? ({ \ |
| pl_barrier(); \ |
| pl_sub(lock, PLOCK32_WL_1 | PLOCK32_RL_1); \ |
| }) : ({ \ |
| void __unsupported_argument_size_for_pl_drop_j__(char *,int); \ |
| if (sizeof(*(lock)) != 4 && (sizeof(long) != 8 || sizeof(*(lock)) != 8)) \ |
| __unsupported_argument_size_for_pl_drop_j__(__FILE__,__LINE__); \ |
| }) \ |
| ) |
| |
| /* |
| * The part below is for Low Overhead R/W locks (LORW). These ones are not |
| * upgradable and not necessarily fair but they try to be fast when uncontended |
| * and to limit the cost and perturbation during contention. Writers always |
| * have precedence over readers to preserve latency as much as possible. |
| * |
| * The principle is to offer a fast no-contention path and a limited total |
| * number of writes for the contended path. Since R/W locks are expected to be |
| * used in situations where there is a benefit in separating reads from writes, |
| * it is expected that reads are common (typ >= 50%) and that there is often at |
| * least one reader (otherwise a spinlock wouldn't be a problem). As such, a |
| * reader will try to pass instantly, detect contention and immediately retract |
| * and wait in the queue in case there is contention. A writer will first also |
| * try to pass instantly, and if it fails due to pending readers, it will mark |
| * that it's waiting so that readers stop entering. This will leave the writer |
| * waiting as close as possible to the point of being granted access. New |
| * writers will also notice this previous contention and will wait outside. |
| * This means that a successful access for a reader or a writer requires a |
| * single CAS, and a contended attempt will require one failed CAS and one |
| * successful XADD for a reader, or an optional OR and a N+1 CAS for the |
| * writer. |
| * |
| * A counter of shared users indicates the number of active readers, while a |
| * (single-bit) counter of exclusive writers indicates whether the lock is |
| * currently held for writes. This distinction also permits to use a single |
| * function to release the lock if desired, since the exclusive bit indicates |
| * the state of the caller of unlock(). The WRQ bit is cleared during the |
| * unlock. |
| * |
| * Layout: (32/64 bit): |
| * 31 2 1 0 |
| * +-----------+--------------+-----+-----+ |
| * | | SHR | WRQ | EXC | |
| * +-----------+--------------+-----+-----+ |
| * |
| * In order to minimize operations, the WRQ bit is held during EXC so that the |
| * write waiter that had to fight for EXC doesn't have to release WRQ during |
| * its operations, and will just drop it along with EXC upon unlock. |
| * |
| * This means the following costs: |
| * reader: |
| * success: 1 CAS |
| * failure: 1 CAS + 1 XADD |
| * unlock: 1 SUB |
| * writer: |
| * success: 1 RD + 1 CAS |
| * failure: 1 RD + 1 CAS + 0/1 OR + N CAS |
| * unlock: 1 AND |
| */ |
| |
| #define PLOCK_LORW_EXC_BIT ((sizeof(long) == 8) ? 0 : 0) |
| #define PLOCK_LORW_EXC_SIZE ((sizeof(long) == 8) ? 1 : 1) |
| #define PLOCK_LORW_EXC_BASE (1UL << PLOCK_LORW_EXC_BIT) |
| #define PLOCK_LORW_EXC_MASK (((1UL << PLOCK_LORW_EXC_SIZE) - 1UL) << PLOCK_LORW_EXC_BIT) |
| |
| #define PLOCK_LORW_WRQ_BIT ((sizeof(long) == 8) ? 1 : 1) |
| #define PLOCK_LORW_WRQ_SIZE ((sizeof(long) == 8) ? 1 : 1) |
| #define PLOCK_LORW_WRQ_BASE (1UL << PLOCK_LORW_WRQ_BIT) |
| #define PLOCK_LORW_WRQ_MASK (((1UL << PLOCK_LORW_WRQ_SIZE) - 1UL) << PLOCK_LORW_WRQ_BIT) |
| |
| #define PLOCK_LORW_SHR_BIT ((sizeof(long) == 8) ? 2 : 2) |
| #define PLOCK_LORW_SHR_SIZE ((sizeof(long) == 8) ? 30 : 30) |
| #define PLOCK_LORW_SHR_BASE (1UL << PLOCK_LORW_SHR_BIT) |
| #define PLOCK_LORW_SHR_MASK (((1UL << PLOCK_LORW_SHR_SIZE) - 1UL) << PLOCK_LORW_SHR_BIT) |
| |
| __attribute__((unused,always_inline,no_instrument_function)) |
| static inline void pl_lorw_rdlock(unsigned long *lock) |
| { |
| unsigned long lk = 0; |
| |
| /* First, assume we're alone and try to get the read lock (fast path). |
| * It often works because read locks are often used on low-contention |
| * structs. |
| */ |
| lk = pl_cmpxchg(lock, 0, PLOCK_LORW_SHR_BASE); |
| if (!lk) |
| return; |
| |
| /* so we were not alone, make sure there's no writer waiting for the |
| * lock to be empty of visitors. |
| */ |
| if (lk & PLOCK_LORW_WRQ_MASK) |
| lk = pl_wait_unlock_long(lock, PLOCK_LORW_WRQ_MASK); |
| |
| /* count us as visitor among others */ |
| lk = pl_xadd(lock, PLOCK_LORW_SHR_BASE); |
| |
| /* wait for end of exclusive access if any */ |
| if (lk & PLOCK_LORW_EXC_MASK) |
| lk = pl_wait_unlock_long(lock, PLOCK_LORW_EXC_MASK); |
| } |
| |
| |
| __attribute__((unused,always_inline,no_instrument_function)) |
| static inline void pl_lorw_wrlock(unsigned long *lock) |
| { |
| unsigned long lk = 0; |
| unsigned long old = 0; |
| |
| /* first, make sure another writer is not already blocked waiting for |
| * readers to leave. Note that tests have shown that it can be even |
| * faster to avoid the first check and to unconditionally wait. |
| */ |
| lk = pl_deref_long(lock); |
| if (__builtin_expect(lk & PLOCK_LORW_WRQ_MASK, 1)) |
| lk = pl_wait_unlock_long(lock, PLOCK_LORW_WRQ_MASK); |
| |
| do { |
| /* let's check for the two sources of contention at once */ |
| |
| if (__builtin_expect(lk & (PLOCK_LORW_SHR_MASK | PLOCK_LORW_EXC_MASK), 1)) { |
| /* check if there are still readers coming. If so, close the door and |
| * wait for them to leave. |
| */ |
| if (lk & PLOCK_LORW_SHR_MASK) { |
| /* note below, an OR is significantly cheaper than BTS or XADD */ |
| if (!(lk & PLOCK_LORW_WRQ_MASK)) |
| pl_or(lock, PLOCK_LORW_WRQ_BASE); |
| lk = pl_wait_unlock_long(lock, PLOCK_LORW_SHR_MASK); |
| } |
| |
| /* And also wait for a previous writer to finish. */ |
| if (lk & PLOCK_LORW_EXC_MASK) |
| lk = pl_wait_unlock_long(lock, PLOCK_LORW_EXC_MASK); |
| } |
| |
| /* A fresh new reader may appear right now if there were none |
| * above and we didn't close the door. |
| */ |
| old = lk & ~PLOCK_LORW_SHR_MASK & ~PLOCK_LORW_EXC_MASK; |
| lk = pl_cmpxchg(lock, old, old | PLOCK_LORW_EXC_BASE); |
| } while (lk != old); |
| |
| /* done, not waiting anymore, the WRQ bit if any, will be dropped by the |
| * unlock |
| */ |
| } |
| |
| |
| __attribute__((unused,always_inline,no_instrument_function)) |
| static inline void pl_lorw_rdunlock(unsigned long *lock) |
| { |
| pl_sub(lock, PLOCK_LORW_SHR_BASE); |
| } |
| |
| __attribute__((unused,always_inline,no_instrument_function)) |
| static inline void pl_lorw_wrunlock(unsigned long *lock) |
| { |
| pl_and(lock, ~(PLOCK_LORW_WRQ_MASK | PLOCK_LORW_EXC_MASK)); |
| } |
| |
| __attribute__((unused,always_inline,no_instrument_function)) |
| static inline void pl_lorw_unlock(unsigned long *lock) |
| { |
| if (pl_deref_long(lock) & PLOCK_LORW_EXC_MASK) |
| pl_lorw_wrunlock(lock); |
| else |
| pl_lorw_rdunlock(lock); |
| } |