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

[Lai Jiangshan]

The pthread APIs don't have proxies APIs, so I have to
reinvent the wheel.

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