[ltt-dev] [RFC PATCHv2 2/5] urcu:implement userspace lock

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> The pthread APIs don't have proxies APIs, so I have to
> reinvent the wheel.

What is a lock proxy API ? References would be welcome, ideally in the
form of extra comments in the code (with explanations and citing
references).

Thanks,

Mathieu

> 
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
>  urcu-wait-lock-impl.h |  121 +++++++++++++++++++++++++++++++++++++++++++++++++
>  urcu/futex.h          |    2 +
>  2 files changed, 123 insertions(+), 0 deletions(-)
>  create mode 100644 urcu-wait-lock-impl.h
> 
> diff --git a/urcu-wait-lock-impl.h b/urcu-wait-lock-impl.h
> new file mode 100644
> index 0000000..88a21db
> --- /dev/null
> +++ b/urcu-wait-lock-impl.h
> @@ -0,0 +1,121 @@
> +/*
> + * urcu-wait-lock-impl.h
> + *
> + * Userspace lock based on futex with proxies APIs for waiting
> + *
> + * Copyright (c) 2011 Lai Jiangshan <laijs at cn.fujitsu.com>
> + *
> + * This library is free software; you can redistribute it and/or
> + * modify it under the terms of the GNU Lesser General Public
> + * License as published by the Free Software Foundation; either
> + * version 2.1 of the License, or (at your option) any later version.
> + *
> + * This library is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
> + * Lesser General Public License for more details.
> + *
> + * You should have received a copy of the GNU Lesser General Public
> + * License along with this library; if not, write to the Free Software
> + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> + */
> +
> +#include <assert.h>
> +
> +static inline int32_t uwl_onwer(int32_t *lock)
> +{
> +	return _CMM_LOAD_SHARED(*lock) & ~FUTEX_WAITERS;
> +}
> +
> +static inline void uwl_set_unlock(int32_t *lock)
> +{
> +	_CMM_STORE_SHARED(*lock, 0);
> +}
> +
> +static inline void uwl_proxy_lock(int32_t *lock, int32_t proxy_owner)
> +{
> +	assert(_CMM_LOAD_SHARED(*lock) == 0);
> +	_CMM_STORE_SHARED(*lock, proxy_owner);
> +}
> +
> +static inline void uwl_proxy_unlock(int32_t *lock)
> +{
> +	uwl_set_unlock(lock);
> +}
> +
> +static void uwl_lock(int32_t *lock, int32_t self)
> +{
> +	for (;;) {
> +		int32_t o = _CMM_LOAD_SHARED(*lock);
> +
> +		if (likely(o == 0)) {
> +			o = uatomic_cmpxchg(lock, 0, self);
> +			if (likely(o == 0))
> +				return;
> +		}
> +
> +		if ((o & FUTEX_WAITERS) == 0) {
> +			if (uatomic_cmpxchg(lock, o, o | FUTEX_WAITERS) != o)
> +				continue;
> +		}
> +
> +		futex_async(lock, FUTEX_WAIT, o | FUTEX_WAITERS, NULL, NULL, 0);
> +		self = self | FUTEX_WAITERS;
> +	}
> +}
> +
> +/*
> + * returns:
> + * -2:  error, lock is held by other.
> + * -1:  error, lock is not held by anyone.
> + *  0:  success unlock.
> + *  1:  failed to unlock when have waiters.
> + */
> +static int uwl_try_unlock(int32_t *lock, int32_t self)
> +{
> +	int32_t o = _CMM_LOAD_SHARED(*lock);
> +
> +	if (likely(o == self)) {
> +		o = uatomic_cmpxchg(lock, self, 0);
> +		if (likely(o == self))
> +			return 0;
> +	}
> +
> +	if (o == (self | FUTEX_WAITERS))
> +		return 1;
> +	if (!o)
> +		return -1;
> +	else
> +		return -2;
> +}
> +
> +static void uwl_slow_unlock(int32_t *lock)
> +{
> +	uwl_set_unlock(lock);
> +	futex_async(lock, FUTEX_WAKE, 1, NULL, NULL, 0);
> +}
> +
> +static void uwl_unlock(int32_t *lock, int32_t self)
> +{
> +	int ret = uwl_try_unlock(lock, self);
> +
> +	assert(ret == 0 || ret == 1);
> +
> +	if (unlikely(ret == 1))
> +		uwl_slow_unlock(lock);
> +}
> +
> +/*
> + * The same as uwl_unlock(), but it accepts the state that
> + * "lock is not held by anyone" which is caused by proxy_unlock.
> + */
> +static void uwl_unlock_if_not_proxy_unlocked(int32_t *lock, int32_t self)
> +{
> +	int ret = uwl_try_unlock(lock, self);
> +
> +	assert(ret == -1 || ret == 0 || ret == 1);
> +
> +	if (unlikely(ret == 1))
> +		uwl_slow_unlock(lock);
> +}
> +
> diff --git a/urcu/futex.h b/urcu/futex.h
> index 98acc12..e47c307 100644
> --- a/urcu/futex.h
> +++ b/urcu/futex.h
> @@ -31,6 +31,8 @@ extern "C" {
>  #define FUTEX_WAIT		0
>  #define FUTEX_WAKE		1
>  
> +#define FUTEX_WAITERS		0x80000000
> +
>  /*
>   * sys_futex compatibility header.
>   * Use *only* *either of* futex_noasync OR futex_async on a given address.
> -- 
> 1.7.4.4
> 

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com