pthread_rwlock.cpp revision 08ee8d2030fbc73c4c144e819dd68806b0351cbe
1a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner/* 2a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * Copyright (C) 2010 The Android Open Source Project 3a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * All rights reserved. 4a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * 5a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * Redistribution and use in source and binary forms, with or without 6a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * modification, are permitted provided that the following conditions 7a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * are met: 8a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * * Redistributions of source code must retain the above copyright 9a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * notice, this list of conditions and the following disclaimer. 10a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * * Redistributions in binary form must reproduce the above copyright 11a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * notice, this list of conditions and the following disclaimer in 12a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * the documentation and/or other materials provided with the 13a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * distribution. 14a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * 15a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 16a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 17a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 18a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 19a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 20a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 21a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS 22a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 23a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 24a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 25a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * SUCH DAMAGE. 27a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner */ 28a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner 29a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner#include <errno.h> 3008ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui#include <stdatomic.h> 3176f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle 3276f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle#include "pthread_internal.h" 3376f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle#include "private/bionic_futex.h" 3404303f5a8ab9a992f3671d46b6ee2171582cbd61Elliott Hughes#include "private/bionic_time_conversions.h" 35a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner 36a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner/* Technical note: 37a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * 38a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * Possible states of a read/write lock: 39a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * 40a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * - no readers and no writer (unlocked) 41a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * - one or more readers sharing the lock at the same time (read-locked) 42a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * - one writer holding the lock (write-lock) 43a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * 44a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * Additionally: 45a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * - trying to get the write-lock while there are any readers blocks 46a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * - trying to get the read-lock while there is a writer blocks 4776f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle * - a single thread can acquire the lock multiple times in read mode 4876f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle * 4976f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle * - Posix states that behavior is undefined (may deadlock) if a thread tries 5076f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle * to acquire the lock 5176f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle * - in write mode while already holding the lock (whether in read or write mode) 5276f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle * - in read mode while already holding the lock in write mode. 5376f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle * - This implementation will return EDEADLK in "write after write" and "read after 5476f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle * write" cases and will deadlock in write after read case. 55a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * 5692687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle * TODO: As it stands now, pending_readers and pending_writers could be merged into a 5776f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle * a single waiters variable. Keeping them separate adds a bit of clarity and keeps 5876f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle * the door open for a writer-biased implementation. 59a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner * 60a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner */ 61a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner 6292687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle#define RWLOCKATTR_DEFAULT 0 6392687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle#define RWLOCKATTR_SHARED_MASK 0x0010 64a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner 6592687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravlestatic inline bool rwlock_is_shared(const pthread_rwlock_t* rwlock) { 6692687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle return rwlock->attr == PTHREAD_PROCESS_SHARED; 6792687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle} 6876f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle 6992687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravlestatic bool timespec_from_absolute(timespec* rel_timeout, const timespec* abs_timeout) { 7092687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle if (abs_timeout != NULL) { 7104303f5a8ab9a992f3671d46b6ee2171582cbd61Elliott Hughes if (!timespec_from_absolute_timespec(*rel_timeout, *abs_timeout, CLOCK_REALTIME)) { 7292687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle return false; 7392687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle } 7492687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle } 7592687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle return true; 7692687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle} 77a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner 7892687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravleint pthread_rwlockattr_init(pthread_rwlockattr_t* attr) { 7976f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle *attr = PTHREAD_PROCESS_PRIVATE; 8076f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle return 0; 81a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner} 82a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner 8392687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravleint pthread_rwlockattr_destroy(pthread_rwlockattr_t* attr) { 8476f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle *attr = -1; 8576f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle return 0; 86a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner} 87a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner 8892687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravleint pthread_rwlockattr_setpshared(pthread_rwlockattr_t* attr, int pshared) { 8976f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle switch (pshared) { 90a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner case PTHREAD_PROCESS_PRIVATE: 91a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner case PTHREAD_PROCESS_SHARED: 9276f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle *attr = pshared; 9376f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle return 0; 94a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner default: 9576f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle return EINVAL; 9676f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle } 97a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner} 98a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner 99c3f114037dbf028896310609fd28cf2b3da99c4dElliott Hughesint pthread_rwlockattr_getpshared(const pthread_rwlockattr_t* attr, int* pshared) { 10076f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle *pshared = *attr; 10176f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle return 0; 102a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner} 103a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner 10408ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cuistatic inline atomic_int* STATE_ATOMIC_POINTER(pthread_rwlock_t* rwlock) { 10508ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui static_assert(sizeof(atomic_int) == sizeof(rwlock->state), 10608ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui "rwlock->state should actually be atomic_int in implementation."); 10708ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui 10808ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // We prefer casting to atomic_int instead of declaring rwlock->state to be atomic_int directly. 10908ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // Because using the second method pollutes pthread.h, and causes an error when compiling libcxx. 11008ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui return reinterpret_cast<atomic_int*>(&rwlock->state); 11108ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui} 11208ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui 11308ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cuistatic inline atomic_int* WRITER_THREAD_ID_ATOMIC_POINTER(pthread_rwlock_t* rwlock) { 11408ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui static_assert(sizeof(atomic_int) == sizeof(rwlock->writer_thread_id), 11508ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui "rwlock->writer_thread_id should actually be atomic_int in implementation."); 11608ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui 11708ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui return reinterpret_cast<atomic_int*>(&rwlock->writer_thread_id); 11808ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui} 11908ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui 12008ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cuistatic inline atomic_uint* PENDING_READERS_ATOMIC_POINTER(pthread_rwlock_t* rwlock) { 12108ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui static_assert(sizeof(atomic_uint) == sizeof(rwlock->pending_readers), 12208ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui "rwlock->pending_readers should actually be atomic_uint in implementation."); 12308ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui 12408ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui return reinterpret_cast<atomic_uint*>(&rwlock->pending_readers); 12508ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui} 12608ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui 12708ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cuistatic inline atomic_uint* PENDING_WRITERS_ATOMIC_POINTER(pthread_rwlock_t* rwlock) { 12808ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui static_assert(sizeof(atomic_uint) == sizeof(rwlock->pending_writers), 12908ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui "rwlock->pending_writers should actually be atomic_uint in implementation."); 13008ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui 13108ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui return reinterpret_cast<atomic_uint*>(&rwlock->pending_writers); 13208ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui} 13308ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui 13492687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravleint pthread_rwlock_init(pthread_rwlock_t* rwlock, const pthread_rwlockattr_t* attr) { 13508ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui if (__predict_true(attr == NULL)) { 13608ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui rwlock->attr = 0; 13708ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui } else { 13876f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle switch (*attr) { 13976f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle case PTHREAD_PROCESS_SHARED: 14076f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle case PTHREAD_PROCESS_PRIVATE: 14176f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle rwlock->attr= *attr; 14276f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle break; 14376f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle default: 14476f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle return EINVAL; 145a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner } 14676f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle } 147a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner 14808ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_init(STATE_ATOMIC_POINTER(rwlock), 0); 14908ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_init(WRITER_THREAD_ID_ATOMIC_POINTER(rwlock), 0); 15008ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_init(PENDING_READERS_ATOMIC_POINTER(rwlock), 0); 15108ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_init(PENDING_WRITERS_ATOMIC_POINTER(rwlock), 0); 152a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner 15376f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle return 0; 154a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner} 155a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner 15692687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravleint pthread_rwlock_destroy(pthread_rwlock_t* rwlock) { 15776f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle if (rwlock->state != 0) { 15876f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle return EBUSY; 15976f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle } 16076f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle return 0; 161a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner} 162a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner 163c3f114037dbf028896310609fd28cf2b3da99c4dElliott Hughesstatic int __pthread_rwlock_timedrdlock(pthread_rwlock_t* rwlock, const timespec* abs_timeout) { 16408ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui if (__predict_false(__get_thread()->tid == 16508ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_load_explicit(WRITER_THREAD_ID_ATOMIC_POINTER(rwlock), memory_order_relaxed))) { 16676f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle return EDEADLK; 16776f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle } 168c3f114037dbf028896310609fd28cf2b3da99c4dElliott Hughes 16992687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle timespec ts; 17092687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle timespec* rel_timeout = (abs_timeout == NULL) ? NULL : &ts; 17108ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui 17208ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_int* state_ptr = STATE_ATOMIC_POINTER(rwlock); 17308ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui 17408ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui while (true) { 17508ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui int cur_state = atomic_load_explicit(state_ptr, memory_order_relaxed); 17676f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle if (__predict_true(cur_state >= 0)) { 17708ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui if (atomic_compare_exchange_weak_explicit(state_ptr, &cur_state, cur_state + 1, 17808ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui memory_order_acquire, memory_order_relaxed)) { 17908ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui return 0; 18008ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui } 18176f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle } else { 18292687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle if (!timespec_from_absolute(rel_timeout, abs_timeout)) { 18392687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle return ETIMEDOUT; 18476f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle } 18508ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_uint* pending_readers_ptr = PENDING_READERS_ATOMIC_POINTER(rwlock); 18608ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui 18708ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // To avoid losing wake ups, the pending_readers increment should be observed before 18808ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // futex_wait by all threads. A seq_cst fence instead of a seq_cst operation is used 18908ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // here. Because only a seq_cst fence can ensure sequential consistency for non-atomic 19008ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // operations in futex_wait. 19108ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_fetch_add_explicit(pending_readers_ptr, 1, memory_order_relaxed); 19208ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_thread_fence(memory_order_seq_cst); 19308ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui int ret = __futex_wait_ex(state_ptr, rwlock_is_shared(rwlock), cur_state, rel_timeout); 19408ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_fetch_sub_explicit(pending_readers_ptr, 1, memory_order_relaxed); 19592687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle if (ret == -ETIMEDOUT) { 19692687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle return ETIMEDOUT; 19776f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle } 198c3f114037dbf028896310609fd28cf2b3da99c4dElliott Hughes } 19908ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui } 200c3f114037dbf028896310609fd28cf2b3da99c4dElliott Hughes} 201a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner 202c3f114037dbf028896310609fd28cf2b3da99c4dElliott Hughesstatic int __pthread_rwlock_timedwrlock(pthread_rwlock_t* rwlock, const timespec* abs_timeout) { 20308ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui if (__predict_false(__get_thread()->tid == 20408ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_load_explicit(WRITER_THREAD_ID_ATOMIC_POINTER(rwlock), memory_order_relaxed))) { 20576f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle return EDEADLK; 206c3f114037dbf028896310609fd28cf2b3da99c4dElliott Hughes } 20776f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle 20892687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle timespec ts; 20992687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle timespec* rel_timeout = (abs_timeout == NULL) ? NULL : &ts; 21008ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui 21108ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_int* state_ptr = STATE_ATOMIC_POINTER(rwlock); 21208ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui 21308ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui while (true) { 21408ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui int cur_state = atomic_load_explicit(state_ptr, memory_order_relaxed); 21576f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle if (__predict_true(cur_state == 0)) { 21608ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui if (atomic_compare_exchange_weak_explicit(state_ptr, &cur_state, -1, 21708ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui memory_order_acquire, memory_order_relaxed)) { 21808ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // writer_thread_id is protected by rwlock and can only be modified in rwlock write 21908ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // owner thread. Other threads may read it for EDEADLK error checking, atomic operation 22008ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // is safe enough for it. 22108ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_store_explicit(WRITER_THREAD_ID_ATOMIC_POINTER(rwlock), __get_thread()->tid, 22208ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui memory_order_relaxed); 22308ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui return 0; 22408ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui } 22576f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle } else { 22692687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle if (!timespec_from_absolute(rel_timeout, abs_timeout)) { 22792687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle return ETIMEDOUT; 22876f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle } 22908ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui 23008ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_uint* pending_writers_ptr = PENDING_WRITERS_ATOMIC_POINTER(rwlock); 23108ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui 23208ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // To avoid losing wake ups, the pending_writers increment should be observed before 23308ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // futex_wait by all threads. A seq_cst fence instead of a seq_cst operation is used 23408ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // here. Because only a seq_cst fence can ensure sequential consistency for non-atomic 23508ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // operations in futex_wait. 23608ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_fetch_add_explicit(pending_writers_ptr, 1, memory_order_relaxed); 23708ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_thread_fence(memory_order_seq_cst); 23808ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui int ret = __futex_wait_ex(state_ptr, rwlock_is_shared(rwlock), cur_state, rel_timeout); 23908ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_fetch_sub_explicit(pending_writers_ptr, 1, memory_order_relaxed); 24092687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle if (ret == -ETIMEDOUT) { 24192687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle return ETIMEDOUT; 24276f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle } 24376f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle } 24408ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui } 245c3f114037dbf028896310609fd28cf2b3da99c4dElliott Hughes} 246c3f114037dbf028896310609fd28cf2b3da99c4dElliott Hughes 247c3f114037dbf028896310609fd28cf2b3da99c4dElliott Hughesint pthread_rwlock_rdlock(pthread_rwlock_t* rwlock) { 248c3f114037dbf028896310609fd28cf2b3da99c4dElliott Hughes return __pthread_rwlock_timedrdlock(rwlock, NULL); 249a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner} 250a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner 25192687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravleint pthread_rwlock_timedrdlock(pthread_rwlock_t* rwlock, const timespec* abs_timeout) { 25292687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle return __pthread_rwlock_timedrdlock(rwlock, abs_timeout); 25392687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle} 25492687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle 25592687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravleint pthread_rwlock_tryrdlock(pthread_rwlock_t* rwlock) { 25608ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_int* state_ptr = STATE_ATOMIC_POINTER(rwlock); 25708ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui int cur_state = atomic_load_explicit(state_ptr, memory_order_relaxed); 25808ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui 25908ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui while (cur_state >= 0) { 26008ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui if (atomic_compare_exchange_weak_explicit(state_ptr, &cur_state, cur_state + 1, 26108ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui memory_order_acquire, memory_order_relaxed)) { 26208ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui return 0; 26308ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui } 26476f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle } 2651b676ea5fba4af0f3a11ca0c31a40825f2157601Calin Juravle return EBUSY; 266a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner} 267a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner 268c3f114037dbf028896310609fd28cf2b3da99c4dElliott Hughesint pthread_rwlock_wrlock(pthread_rwlock_t* rwlock) { 269c3f114037dbf028896310609fd28cf2b3da99c4dElliott Hughes return __pthread_rwlock_timedwrlock(rwlock, NULL); 270a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner} 271a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner 27292687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravleint pthread_rwlock_timedwrlock(pthread_rwlock_t* rwlock, const timespec* abs_timeout) { 27392687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle return __pthread_rwlock_timedwrlock(rwlock, abs_timeout); 27492687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle} 27592687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravle 27692687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravleint pthread_rwlock_trywrlock(pthread_rwlock_t* rwlock) { 27708ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_int* state_ptr = STATE_ATOMIC_POINTER(rwlock); 27808ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui int cur_state = atomic_load_explicit(state_ptr, memory_order_relaxed); 27908ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui 28008ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui while (cur_state == 0) { 28108ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui if (atomic_compare_exchange_weak_explicit(state_ptr, &cur_state, -1, 28208ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui memory_order_acquire, memory_order_relaxed)) { 28308ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui int tid = __get_thread()->tid; 28408ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_store_explicit(WRITER_THREAD_ID_ATOMIC_POINTER(rwlock), tid, memory_order_relaxed); 28508ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui return 0; 28608ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui } 28776f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle } 2881b676ea5fba4af0f3a11ca0c31a40825f2157601Calin Juravle return EBUSY; 289a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner} 290a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner 291a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner 29292687e41bcf108957944dafa80a9bfda219bfb0fCalin Juravleint pthread_rwlock_unlock(pthread_rwlock_t* rwlock) { 29376f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle int tid = __get_thread()->tid; 29408ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_int* state_ptr = STATE_ATOMIC_POINTER(rwlock); 29508ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_uint* pending_readers_ptr = PENDING_READERS_ATOMIC_POINTER(rwlock); 29608ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_uint* pending_writers_ptr = PENDING_WRITERS_ATOMIC_POINTER(rwlock); 29708ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui 29808ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui int cur_state = atomic_load_explicit(state_ptr, memory_order_relaxed); 29908ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui if (__predict_false(cur_state == 0)) { 30008ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui return EPERM; 30108ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui } else if (cur_state == -1) { 30208ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_int* writer_thread_id_ptr = WRITER_THREAD_ID_ATOMIC_POINTER(rwlock); 30308ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui if (atomic_load_explicit(writer_thread_id_ptr, memory_order_relaxed) != tid) { 30476f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle return EPERM; 305a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner } 30608ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // We're no longer the owner. 30708ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_store_explicit(writer_thread_id_ptr, 0, memory_order_relaxed); 30808ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // Change state from -1 to 0. 30908ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_store_explicit(state_ptr, 0, memory_order_release); 31008ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui goto wakeup_waiters; 31108ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui 31208ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui } else { // cur_state > 0 31308ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // Reduce state by 1. 31408ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui while (!atomic_compare_exchange_weak_explicit(state_ptr, &cur_state, cur_state - 1, 31508ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui memory_order_release, memory_order_relaxed)) { 31608ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui if (cur_state <= 0) { 31776f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle return EPERM; 31876f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle } 319a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner } 32008ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui if (cur_state == 1) { 32108ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui goto wakeup_waiters; 32208ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui } 32308ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui } 32408ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui return 0; 32576f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle 32608ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cuiwakeup_waiters: 32708ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // To avoid losing wake ups, the update of state should be observed before reading 32808ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // pending_readers/pending_writers by all threads. Use read locking as an example: 32908ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // read locking thread unlocking thread 33008ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // pending_readers++; state = 0; 33108ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // seq_cst fence seq_cst fence 33208ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // read state for futex_wait read pending_readers for futex_wake 33308ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // 33408ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // So when locking and unlocking threads are running in parallel, we will not get 33508ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // in a situation that the locking thread reads state as negative and needs to wait, 33608ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui // while the unlocking thread reads pending_readers as zero and doesn't need to wake up waiters. 33708ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_thread_fence(memory_order_seq_cst); 33808ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui if (__predict_false(atomic_load_explicit(pending_readers_ptr, memory_order_relaxed) > 0 || 33908ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui atomic_load_explicit(pending_writers_ptr, memory_order_relaxed) > 0)) { 34008ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui __futex_wake_ex(state_ptr, rwlock_is_shared(rwlock), INT_MAX); 34108ee8d2030fbc73c4c144e819dd68806b0351cbeYabin Cui } 34276f352eec12d8938101e5ae33429c72797c3aa23Calin Juravle return 0; 343a418c3b8370cae1c80fbe9a06e7e53025da5d6f0David 'Digit' Turner} 344