Index: abi/include/abi/synch.h
===================================================================
--- abi/include/abi/synch.h	(revision f6372be92e3eaec95762607dcf097844741b51b5)
+++ abi/include/abi/synch.h	(revision b59318e5ac29b0f8d47f0b4407a9f99be6ad5654)
@@ -45,4 +45,6 @@
 /** Interruptible operation. */
 #define SYNCH_FLAGS_INTERRUPTIBLE  (1 << 1)
+/** Futex operation (makes sleep with timeout composable). */
+#define SYNCH_FLAGS_FUTEX          (1 << 2)
 
 #endif
Index: kernel/generic/include/proc/thread.h
===================================================================
--- kernel/generic/include/proc/thread.h	(revision f6372be92e3eaec95762607dcf097844741b51b5)
+++ kernel/generic/include/proc/thread.h	(revision b59318e5ac29b0f8d47f0b4407a9f99be6ad5654)
@@ -112,4 +112,12 @@
 	/** If true, the thread can be interrupted from sleep. */
 	bool sleep_interruptible;
+
+	/**
+	 * If true, and this thread's sleep returns without a wakeup
+	 * (timed out or interrupted), waitq ignores the next wakeup.
+	 * This is necessary for futex to be able to handle those conditions.
+	 */
+	bool sleep_composable;
+
 	/** Wait queue in which this thread sleeps. */
 	waitq_t *sleep_queue;
Index: kernel/generic/include/synch/futex.h
===================================================================
--- kernel/generic/include/synch/futex.h	(revision f6372be92e3eaec95762607dcf097844741b51b5)
+++ kernel/generic/include/synch/futex.h	(revision b59318e5ac29b0f8d47f0b4407a9f99be6ad5654)
@@ -53,5 +53,5 @@
 
 extern void futex_init(void);
-extern sys_errno_t sys_futex_sleep(uintptr_t);
+extern sys_errno_t sys_futex_sleep(uintptr_t, uintptr_t);
 extern sys_errno_t sys_futex_wakeup(uintptr_t);
 
Index: kernel/generic/include/synch/waitq.h
===================================================================
--- kernel/generic/include/synch/waitq.h	(revision f6372be92e3eaec95762607dcf097844741b51b5)
+++ kernel/generic/include/synch/waitq.h	(revision b59318e5ac29b0f8d47f0b4407a9f99be6ad5654)
@@ -62,4 +62,7 @@
 	int missed_wakeups;
 
+	/** Number of wakeups that need to be ignored due to futex timeout. */
+	int ignore_wakeups;
+
 	/** List of sleeping threads for which there was no missed_wakeup. */
 	list_t sleepers;
Index: kernel/generic/src/proc/thread.c
===================================================================
--- kernel/generic/src/proc/thread.c	(revision f6372be92e3eaec95762607dcf097844741b51b5)
+++ kernel/generic/src/proc/thread.c	(revision b59318e5ac29b0f8d47f0b4407a9f99be6ad5654)
@@ -383,4 +383,5 @@
 	timeout_initialize(&thread->sleep_timeout);
 	thread->sleep_interruptible = false;
+	thread->sleep_composable = false;
 	thread->sleep_queue = NULL;
 	thread->timeout_pending = false;
Index: kernel/generic/src/synch/futex.c
===================================================================
--- kernel/generic/src/synch/futex.c	(revision f6372be92e3eaec95762607dcf097844741b51b5)
+++ kernel/generic/src/synch/futex.c	(revision b59318e5ac29b0f8d47f0b4407a9f99be6ad5654)
@@ -398,7 +398,10 @@
 }
 
-/** Sleep in futex wait queue.
- *
- * @param uaddr		Userspace address of the futex counter.
+/** Sleep in futex wait queue with a timeout.
+ *  If the sleep times out or is interrupted, the next wakeup is ignored.
+ *  The userspace portion of the call must handle this condition.
+ *
+ * @param uaddr	 	Userspace address of the futex counter.
+ * @param timeout	Maximum number of useconds to sleep. 0 means no limit.
  *
  * @return		If there is no physical mapping for uaddr ENOENT is
@@ -406,5 +409,5 @@
  *                      waitq_sleep_timeout().
  */
-sys_errno_t sys_futex_sleep(uintptr_t uaddr)
+sys_errno_t sys_futex_sleep(uintptr_t uaddr, uintptr_t timeout)
 {
 	futex_t *futex = get_futex(uaddr);
@@ -417,6 +420,6 @@
 #endif
 
-	errno_t rc = waitq_sleep_timeout(
-	    &futex->wq, 0, SYNCH_FLAGS_INTERRUPTIBLE, NULL);
+	errno_t rc = waitq_sleep_timeout(&futex->wq, timeout,
+	    SYNCH_FLAGS_INTERRUPTIBLE | SYNCH_FLAGS_FUTEX, NULL);
 
 #ifdef CONFIG_UDEBUG
Index: kernel/generic/src/synch/waitq.c
===================================================================
--- kernel/generic/src/synch/waitq.c	(revision f6372be92e3eaec95762607dcf097844741b51b5)
+++ kernel/generic/src/synch/waitq.c	(revision b59318e5ac29b0f8d47f0b4407a9f99be6ad5654)
@@ -57,4 +57,5 @@
 #include <adt/list.h>
 #include <arch/cycle.h>
+#include <mem.h>
 
 static void waitq_sleep_timed_out(void *);
@@ -71,7 +72,7 @@
 void waitq_initialize(waitq_t *wq)
 {
+	memsetb(wq, sizeof(*wq), 0);
 	irq_spinlock_initialize(&wq->lock, "wq.lock");
 	list_initialize(&wq->sleepers);
-	wq->missed_wakeups = 0;
 }
 
@@ -114,4 +115,6 @@
 		thread->saved_context = thread->sleep_timeout_context;
 		do_wakeup = true;
+		if (thread->sleep_composable)
+			wq->ignore_wakeups++;
 		thread->sleep_queue = NULL;
 		irq_spinlock_unlock(&wq->lock, false);
@@ -176,4 +179,6 @@
 		list_remove(&thread->wq_link);
 		thread->saved_context = thread->sleep_interruption_context;
+		if (thread->sleep_composable)
+			wq->ignore_wakeups++;
 		do_wakeup = true;
 		thread->sleep_queue = NULL;
@@ -393,4 +398,6 @@
 	 */
 	irq_spinlock_lock(&THREAD->lock, false);
+
+	THREAD->sleep_composable = (flags & SYNCH_FLAGS_FUTEX);
 
 	if (flags & SYNCH_FLAGS_INTERRUPTIBLE) {
@@ -538,4 +545,12 @@
 	assert(irq_spinlock_locked(&wq->lock));
 
+	if (wq->ignore_wakeups > 0) {
+		if (mode == WAKEUP_FIRST) {
+			wq->ignore_wakeups--;
+			return;
+		}
+		wq->ignore_wakeups = 0;
+	}
+
 loop:
 	if (list_empty(&wq->sleepers)) {
Index: uspace/lib/c/include/futex.h
===================================================================
--- uspace/lib/c/include/futex.h	(revision f6372be92e3eaec95762607dcf097844741b51b5)
+++ uspace/lib/c/include/futex.h	(revision b59318e5ac29b0f8d47f0b4407a9f99be6ad5654)
@@ -36,4 +36,5 @@
 #define LIBC_FUTEX_H_
 
+#include <assert.h>
 #include <atomic.h>
 #include <errno.h>
@@ -98,17 +99,42 @@
 }
 
-/** Down the futex.
+/** Down the futex with timeout, composably.
+ *
+ * This means that when the operation fails due to a timeout or being
+ * interrupted, the next futex_up() is ignored, which allows certain kinds of
+ * composition of synchronization primitives.
+ *
+ * In most other circumstances, regular futex_down_timeout() is a better choice.
  *
  * @param futex Futex.
  *
  * @return ENOENT if there is no such virtual address.
+ * @return ETIMEOUT if timeout expires.
  * @return EOK on success.
  * @return Error code from <errno.h> otherwise.
  *
  */
-static inline errno_t futex_down(futex_t *futex)
+static inline errno_t futex_down_composable(futex_t *futex, struct timeval *expires)
 {
+	// TODO: Add tests for this.
+
+	/* No timeout by default. */
+	suseconds_t timeout = 0;
+
+	if (expires) {
+		struct timeval tv;
+		getuptime(&tv);
+		if (tv_gteq(&tv, expires)) {
+			/* We can't just return ETIMEOUT. That wouldn't be composable. */
+			timeout = 1;
+		} else {
+			timeout = tv_sub_diff(expires, &tv);
+		}
+
+		assert(timeout > 0);
+	}
+
 	if ((atomic_signed_t) atomic_predec(&futex->val) < 0)
-		return (errno_t) __SYSCALL1(SYS_FUTEX_SLEEP, (sysarg_t) &futex->val.count);
+		return (errno_t) __SYSCALL2(SYS_FUTEX_SLEEP, (sysarg_t) &futex->val.count, (sysarg_t) timeout);
 
 	return EOK;
@@ -132,4 +158,31 @@
 }
 
+static inline errno_t futex_down_timeout(futex_t *futex, struct timeval *expires)
+{
+	/*
+	 * This combination of a "composable" sleep followed by futex_up() on
+	 * failure is necessary to prevent breakage due to certain race
+	 * conditions.
+	 */
+	errno_t rc = futex_down_composable(futex, expires);
+	if (rc != EOK)
+		futex_up(futex);
+	return rc;
+}
+
+/** Down the futex.
+ *
+ * @param futex Futex.
+ *
+ * @return ENOENT if there is no such virtual address.
+ * @return EOK on success.
+ * @return Error code from <errno.h> otherwise.
+ *
+ */
+static inline errno_t futex_down(futex_t *futex)
+{
+	return futex_down_timeout(futex, NULL);
+}
+
 #endif
 
