Skip to contentSkip to conversation

futex: robust futex support

robust-futex-1 David Singleton 5 participants 15 messages Jan 14, 2006 – Jan 23, 2006

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

Andrew,

The original code for this patch was supplied by Todd Kneisel.

Robust futexes provide a locking mechanism that can be shared between user mode processes. The major difference between robust futexes and regular futexes is that when the owner of a robust futex dies, the next task waiting on the futex will be awakened, will get ownership of the futex lock, and will receive the error status EOWNERDEAD.

Robust futexes allow the system to gracefuly continue if an application dies while holding a futex, without leaving waiting threads hung or requiring the system to be rebooted to clear the hang.

Robust futexes are structures hung on a linked list on the inode. The list is scanned at exit time to find any futexes still held by the dying thread. The structures backing the futex are removed when a dentry reference count drops to zero. The exit path cleans up and locked futexes and the dentry reference count handles cleaning up robust futex resources.

This implimentation supports shared pthread_mutexes, pthread_mutexes mmapped either in a file or in mmapped anonymous memory.

Ulrich Drepper has a glibc that handles non-shared (malloc'd pthread_mutexes) all in user space. This patch returns -ENOTSHARED from register futex if it is not a shared futex so his glibc can handle the non-shared pthread_mutexes without kernel support.

The structure for robustness has its own slab cache, making it easy track how many robust futexes are in the system through /proc/slabinfo.

Robust futexes have been tested fairly well in the community using realtime-preempt patch, which supports both robust and priority inheriting pthread_mutexes. There is a simple test suite, originally also supplied by Todd Kneisel, that tests basic robustness using regular futexes that have robust attribute applied. They've also been tested using the fusyn posix test suite, with minor modifications to make the fusyn tests run with the NPTL libraries.

 fs/dcache.c                 |    2 
 fs/inode.c                  |    4 
 include/asm-generic/errno.h |    1 
 include/linux/fs.h          |    2 
 include/linux/futex.h       |   33 +++
 init/Kconfig                |    9 
 kernel/exit.c               |    2 
 kernel/futex.c              |  426 +++++++++++++++++++++++++++++++++++++++++++-
 8 files changed, 471 insertions(+), 8 deletions(-)
fs/dcache.c +2 -0
Index: linux-2.6.15/fs/dcache.c
===================================================================
@@ -33,6 +33,7 @@
 #include <linux/seqlock.h>
 #include <linux/swap.h>
 #include <linux/bootmem.h>
+#include <linux/futex.h>
 
 /* #define DCACHE_DEBUG 1 */
 
@@ -161,6 +162,7 @@ repeat:
 		return;
 	}
 
+	futex_free_robust_list(dentry->d_inode);
 	/*
 	 * AV: ->d_delete() is _NOT_ allowed to block now.
 	 */
fs/inode.c +4 -0
Index: linux-2.6.15/fs/inode.c
===================================================================
@@ -23,6 +23,7 @@
 #include <linux/bootmem.h>
 #include <linux/inotify.h>
 #include <linux/mount.h>
+#include <linux/futex.h>
 
 /*
  * This is needed for the following functions:
@@ -208,6 +209,9 @@ void inode_init_once(struct inode *inode
 	INIT_LIST_HEAD(&inode->inotify_watches);
 	sema_init(&inode->inotify_sem, 1);
 #endif
+#ifdef CONFIG_ROBUST_FUTEX
+	futex_init_inode(inode);
+#endif
 }
 
 EXPORT_SYMBOL(inode_init_once);
include/linux/fs.h +2 -0
Index: linux-2.6.15/include/linux/fs.h
===================================================================
@@ -383,6 +383,8 @@ struct address_space {
 	spinlock_t		private_lock;	/* for use by the address_space */
 	struct list_head	private_list;	/* ditto */
 	struct address_space	*assoc_mapping;	/* ditto */
+	struct list_head	robust_list;	/* list of robust futexes */
+	struct semaphore	robust_sem;	/* semaphore for robust */
 } __attribute__((aligned(sizeof(long))));
 	/*
 	 * On most architectures that alignment is already the case; but
include/linux/futex.h +33 -0
Index: linux-2.6.15/include/linux/futex.h
===================================================================
@@ -10,6 +10,38 @@
 #define FUTEX_REQUEUE		3
 #define FUTEX_CMP_REQUEUE	4
 #define FUTEX_WAKE_OP		5
+#define FUTEX_REGISTER          6
+#define FUTEX_DEREGISTER        7
+#define FUTEX_RECOVER           8
+
+#ifdef __KERNEL__
+
+#ifdef CONFIG_ROBUST_FUTEX
+
+#define FUTEX_WAITERS				0x80000000
+#define FUTEX_OWNER_DIED			0x40000000
+#define FUTEX_NOT_RECOVERABLE			0x20000000
+#define FUTEX_FLAGS (FUTEX_WAITERS | FUTEX_OWNER_DIED | FUTEX_NOT_RECOVERABLE)
+#define FUTEX_PID                             ~(FUTEX_FLAGS)
+
+#define FUTEX_ATTR_SHARED                       0x10000000
+
+/*
+ * Used to track registered robust futexes. Attached to linked list in inodes.
+ */
+static inline void futex_init_inode(struct inode *inode)
+{
+        INIT_LIST_HEAD(&inode->i_data.robust_list);
+        init_MUTEX(&inode->i_data.robust_sem);
+}
+
+extern void futex_free_robust_list(struct inode *inode);
+extern void exit_futex(struct task_struct *tsk);
+#else
+# define futex_free_robust_list(a)      do { } while (0)
+# define exit_futex(b)                  do { } while (0)
+#define futex_init_inode(a) 		do { } while (0)
+#endif
 
 long do_futex(unsigned long uaddr, int op, int val,
 		unsigned long timeout, unsigned long uaddr2, int val2,
@@ -41,3 +73,4 @@ long do_futex(unsigned long uaddr, int o
    | ((oparg & 0xfff) << 12) | (cmparg & 0xfff))
 
 #endif
+#endif
kernel/exit.c +2 -0
Index: linux-2.6.15/kernel/exit.c
===================================================================
@@ -31,6 +31,7 @@
 #include <linux/signal.h>
 #include <linux/cn_proc.h>
 #include <linux/mutex.h>
+#include <linux/futex.h>
 
 #include <asm/uaccess.h>
 #include <asm/unistd.h>
@@ -847,6 +848,7 @@ fastcall NORET_TYPE void do_exit(long co
 		exit_itimers(tsk->signal);
 		acct_process(code);
 	}
+	exit_futex(tsk);
 	exit_mm(tsk);
 
 	exit_sem(tsk);
kernel/futex.c +418 -8

528 lines not on this page · raw message

init/Kconfig +9 -0
Index: linux-2.6.15/init/Kconfig
===================================================================
@@ -348,6 +348,15 @@ config FUTEX
 	  support for "fast userspace mutexes".  The resulting kernel may not
 	  run glibc-based applications correctly.
 
+config ROBUST_FUTEX
+	bool "Enable robust futex support"
+	depends on FUTEX
+	default y
+	help
+	  Enable this option if you want to use robust user space mutexes.
+	  Enabling this option slows down the exit path of the kernel for
+	  all processes.  Robust futexes will run glibc-based applications correctly.
+
 config EPOLL
 	bool "Enable eventpoll support" if EMBEDDED
 	default y
include/asm-generic/errno.h +1 -0
Index: linux-2.6.15/include/asm-generic/errno.h
===================================================================
@@ -105,5 +105,6 @@
 /* for robust mutexes */
 #define	EOWNERDEAD	130	/* Owner died */
 #define	ENOTRECOVERABLE	131	/* State not recoverable */
+#define ENOTSHARED	132	/* no pshared attribute */
 
 #endif
#1 lore raw

On 1/13/06, David Singleton <[email protected]> wrote:
=============================================

include/asm-generic/errno.h line 108

Quoted 7 lines
include/asm-generic/errno.h +1 -0
@@ -105,5 +105,6 @@
 /* for robust mutexes */
 #define        EOWNERDEAD      130     /* Owner died */
 #define        ENOTRECOVERABLE 131     /* State not recoverable */
+#define ENOTSHARED     132     /* no pshared attribute */

Do not introduce a new error code if at all possible. Adding userlang-visible error codes means the ABI changes due to the stupid _sys_errlist variable. Just reuse an error code which cannot be returned in the futex code so far and which has some kind of resemblence with what the error means.

#2 lore raw
Quoted 15 lines · Ulrich Drepper

On 1/13/06, David Singleton <[email protected]> wrote:
=============================================

include/asm-generic/errno.h line 108

Quoted 7 lines
include/asm-generic/errno.h +1 -0
@@ -105,5 +105,6 @@
 /* for robust mutexes */
 #define        EOWNERDEAD      130     /* Owner died */
 #define        ENOTRECOVERABLE 131     /* State not recoverable */
+#define ENOTSHARED     132     /* no pshared attribute */

Do not introduce a new error code if at all possible. Adding userlang-visible error codes means the ABI changes due to the stupid _sys_errlist variable. Just reuse an error code which cannot be returned in the futex code so far and which has some kind of resemblence with what the error means.

can you suggest some error codes you like to use? I'll use whatever you suggest.

thanks

David

#3 lore raw
Quoted 2 lines · david singleton

can you suggest some error codes you like to use? I'll use whatever you suggest.

How about EADDRNOTAVAIL. The error message kind of makes sense, even though "address" is misused. And there definitely won't be a clash with other error codes because it's currently only used in network contexts.

#4 lore raw
Quoted 8 lines · Ulrich Drepper
Quoted 4 lines · david singleton

can you suggest some error codes you like to use? I'll use whatever you suggest.

Quoted 6 lines

How about EADDRNOTAVAIL. The error message kind of makes sense, even though "address" is misused. And there definitely won't be a clash with other error codes because it's currently only used in network contexts.

Will do. I'm testing a patch that addresses Andi's suggestions now and I'll add the return code today.

thanks

#5 lore raw
In reply to Ulrich Drepper
Quoted 9 lines · Ulrich Drepper
Quoted 2 lines · david singleton

can you suggest some error codes you like to use? I'll use whatever you suggest.

How about EADDRNOTAVAIL. The error message kind of makes sense, even though "address" is misused. And there definitely won't be a clash with other error codes because it's currently only used in network contexts.

Ulrich,
I've fixed another memory leak in free_robust_list. The entries in
the slab caches
now look correct through the full test suite up to 7500 threads. Does your glibc
work correctly with this patch?

kernel/futex.c +2 -0
diff -u linux-2.6.15/kernel/futex.c linux-2.6.15/kernel/futex.c
@@ -917,6 +917,8 @@
        up(&mapping->robust_head->robust_sem);
 
        kmem_cache_free(file_futex_cachep, futex_head);
+       mapping->robust_head = NULL;
+
        return;
 }
 

The new full patch is attached, and at

http://source.mvista.com/~dsingleton/robust–futex-3

David

#6 lore raw
Quoted 5 lines · david singleton

I've fixed another memory leak in free_robust_list. The entries in
the slab caches
now look correct through the full test suite up to 7500 threads. Does
your glibc
work correctly with this patch?

I'll see shortly.

But looking at the patch, I don't understand the use of FUTEX_ATTR_SHARED. The EADDRNOTAVAIL error is something the kernel has to return if the address is not that of an object in a shared memory region. It's not information directly provided by the user of futex_register.

So, I suggest removing the attr parameter from futex_register and after get_futex_key, when you know where the futex is actually located, return -EADDRNOTAVAIL if the futex is in private memory.

#7 lore raw
In reply to david singleton

And another thing: semaphores are on their way out. So, in futex_deregister and in futex_head, shouldn't you use mutexes? I don't see that you realy need semaphores.

In futex_register, you define mm and initialize it with current->mm. That's OK. But why then are you using

+ down_read(&current->mm->mmap_sem);

just a few lines below?

And finally (for now): in get_futex_key the VMA containing the futex is determined. And yet, in futex_register you have an identical find_extend_vma call. I don't know how expensive this function is. But I would assume that at least the error handling in futex_register can go away since the VMA cannot be torn down while mmap_sem is taken, right? But perhaps this just points to more inconsistencies. Why is the list/sem lookup in get_futex_key? Only to share the code with futex_deregister. But is that really worth it? The majority of calls to get_futex_key come from all the other call sites so the code you added is only a cost without any gain. Especially since you could in futex_register do the whole thing without any additional cost and because most of the new tests in get_futex_key are again tested in futex_register (to determined shared vs non-shared) and do not have to be tested in futex_deregister (we know the futex is in shared memory).

I suggest that if find_extend_vma is sufficiently expensive, pass a pointer to a variable of that type to get_futex_key. If it is cheap, don't do anything. Pull the new code in get_futex_key into futex_register and futex_deregister, optimize out unnecessary code, and merge with the rest of the functions. It'll be much less invasive.

#8 lore raw

Ulrich,
I've incorporated your suggestions, wih the exception of passing the
pthreaad
mutex attribute into the kernel for futex_register. I'd like to be able to pass the attributes associated with the pthread_mutex into the kernel so the kernel can support whatever attributes are on the mutex without having to change the interface between glibc and the kernel.

If we pass the attributes in for robustness we don't have to change
the interface if/when the kernel supports other attributes, like priority inheritance.

Let me know what you think of the implementation, and thanks
for the suggestions, they made the patch much less intrusive.

David

The original code for this patch was supplied by Todd Kneisel.

Incorporated changes suggested by Urich Drepper.

 fs/dcache.c           |    2
 include/linux/fs.h    |    2
 include/linux/futex.h |   33 ++++
 init/Kconfig          |    9 +
 kernel/exit.c         |    2
 kernel/futex.c        |  395 
++++++++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 443 insertions(+)
Quoted 32 lines · Ulrich Drepper

And another thing: semaphores are on their way out. So, in futex_deregister and in futex_head, shouldn't you use mutexes? I don't see that you realy need semaphores.

In futex_register, you define mm and initialize it with current->mm. That's OK. But why then are you using

+ down_read(&current->mm->mmap_sem);

just a few lines below?

And finally (for now): in get_futex_key the VMA containing the futex is determined. And yet, in futex_register you have an identical find_extend_vma call. I don't know how expensive this function is. But I would assume that at least the error handling in futex_register can go away since the VMA cannot be torn down while mmap_sem is taken, right? But perhaps this just points to more inconsistencies. Why is the list/sem lookup in get_futex_key? Only to share the code with futex_deregister. But is that really worth it? The majority of calls to get_futex_key come from all the other call sites so the code you added is only a cost without any gain. Especially since you could in futex_register do the whole thing without any additional cost and because most of the new tests in get_futex_key are again tested in futex_register (to determined shared vs non-shared) and do not have to be tested in futex_deregister (we know the futex is in shared memory).

I suggest that if find_extend_vma is sufficiently expensive, pass a pointer to a variable of that type to get_futex_key. If it is cheap, don't do anything. Pull the new code in get_futex_key into futex_register and futex_deregister, optimize out unnecessary code, and merge with the rest of the functions. It'll be much less invasive.

#9 lore raw

Review struct address_space { · line 388

Quoted 10 lines · david singleton

[-ENOCHANGELOG]

(quoted diff) +1 -0
@@ -383,6 +384,7 @@ struct address_space {
 	spinlock_t		private_lock;	/* for use by the address_space */
 	struct list_head	private_list;	/* ditto */
 	struct address_space	*assoc_mapping;	/* ditto */
+	struct futex_head	*robust_head;	/* list of robust futexes */
 } __attribute__((aligned(sizeof(long))));

It's worth putting this field inside CONFIG_ROBUST_FUTEX

Review struct address_space {

Quoted 5 lines
(quoted diff) +5 -0
+#else
+# define futex_free_robust_list(a)      do { } while (0)
+# define exit_futex(b)                  do { } while (0)
+#define futex_init_inode(a) 		do { } while (0)
+#endif

Indenting went wonky.

Quoted 6 lines

+/*
+ * Robust futexes provide a locking mechanism that can be shared between
+ * user mode processes. The major difference between robust futexes and
+ * regular futexes is that when the owner of a robust futex dies, the
+ * next task waiting on the futex will be awakened, will get ownership
+ * of the futex lock, and will receive the error status EOWNERDEAD.

Quoted 8 lines

+ *
+ * A robust futex is a 32 bit integer stored in user mode shared memory.
+ * Bit 31 indicates that there are tasks waiting on the futex.
+ * Bit 30 indicates that the task that owned the futex has died.
+ * Bit 29 indicates that the futex is not recoverable and cannot be used.
+ * Bits 0-28 are the pid of the task that owns the futex lock, or zero if
+ * the futex is not locked.
+ */

Nice comment!

Quoted 8 lines
(quoted diff) +8 -0
+/**
+ * futex_free_robust_list - release the list of registered futexes.
+ * @inode: inode that may be a memory mapped file
+ *
+ * Called from dput() when a dentry reference count reaches zero.
+ * If the dentry is associated with a memory mapped file, then
+ * release the list of registered robust futexes that are contained
+ * in that mapping.

Review

Quoted 10 lines
(quoted diff) +10 -0
+ */
+void futex_free_robust_list(struct inode *inode)
+{
+	struct address_space *mapping;
+	struct list_head *head;
+ 	struct futex_robust *this, *next;
+	struct futex_head *futex_head = NULL;
+
+	if (inode == NULL)
+		return;

Is this test needed?

This function is called when a dentry's refcount falls to zero. But there could be other refs to this inode which might get upset at having their robust futexes thrown away. Shouldn't this be based on inode destruction rather than dentry?

Review

Quoted 3 lines
(quoted diff) +3 -0
+	mapping = inode->i_mapping;
+	if (mapping == NULL)
+		return;

inodes never have a null ->i_mapping

Quoted 5 lines
(quoted diff) +5 -0
+	if (mapping->robust_head == NULL)
+		return;
+
+	if (list_empty(&mapping->robust_head->robust_list))
+		return;

Review

Quoted 10 lines
(quoted diff) +10 -0
+
+	mutex_lock(&mapping->robust_head->robust_mutex);
+
+	head = &mapping->robust_head->robust_list;
+	futex_head = mapping->robust_head;
+
+	list_for_each_entry_safe(this, next, head, list) {
+		list_del(&this->list);
+		kmem_cache_free(robust_futex_cachep, this);
+	}

If we're throwing away the entire contents of the list, there's no need to detach items as we go.

Quoted 17 lines
(quoted diff) +17 -0
+/**
+ * get_shared_uaddr - convert a shared futex_key to a user addr.
+ * @key: a futex_key that identifies a futex.
+ * @vma: a vma that may contain the futex
+ *
+ * Shared futex_keys identify a futex that is contained in a vma,
+ * and so may be shared.
+ * Returns zero if futex is not contained in @vma
+ */
+static unsigned long get_shared_uaddr(union futex_key *key,
+				      struct vm_area_struct *vma)
+{
+	unsigned long uaddr = 0;
+	unsigned long tmpaddr;
+	struct address_space *mapping;
+
+	mapping = vma->vm_file->f_mapping;

Review

Quoted 10 lines
(quoted diff) +10 -0
+	if (key->shared.inode == mapping->host) {
+		tmpaddr = ((key->shared.pgoff - vma->vm_pgoff) << PAGE_SHIFT)
+				+ (key->shared.offset & ~0x1)
+				+ vma->vm_start;
+		if (tmpaddr >= vma->vm_start && tmpaddr < vma->vm_end)
+			uaddr = tmpaddr;
+	}
+
+	return uaddr;
+}

What locking guarantees that vma->vm_file->f_mapping continues to exist? Bear in mind that another thread which shares this thread's files can close fds, unlink files, munmap files, etc.

Quoted 24 lines
(quoted diff) +24 -0
+/**
+ * find_owned_futex - find futexes owned by the current task
+ * @tsk: task that is exiting
+ * @vma: vma containing robust futexes
+ * @head: list head for list of robust futexes
+ * @mutex: mutex that protects the list
+ *
+ * Walk the list of registered robust futexes for this @vma,
+ * setting the %FUTEX_OWNER_DIED flag on those futexes owned
+ * by the current, exiting task.
+ */
+static void
+find_owned_futex(struct task_struct *tsk, struct vm_area_struct *vma,
+		 struct list_head *head, struct mutex *mutex)
+{
+	struct futex_robust *this, *next;
+ 	unsigned long uaddr;
+	int value;
+
+	mutex_lock(mutex);
+
+	list_for_each_entry_safe(this, next, head, list) {
+
+		uaddr = get_futex_uaddr(&this->key, vma);

Review

Quoted 10 lines
(quoted diff) +10 -0
+		if (uaddr == 0)
+			continue;
+
+		mutex_unlock(mutex);
+		up_read(&tsk->mm->mmap_sem);
+		get_user(value, (int __user *)uaddr);
+		if ((value & FUTEX_PID) == tsk->pid) {
+			value |= FUTEX_OWNER_DIED;
+			futex_wake(uaddr, 1);
+			put_user(value, (int *__user)uaddr);

That's a bit unconventional - normally we'd perform the other-task-visible write and _then_ wake up the other task. What prevents the woken task from waking then seeing the not-yet-written-to value?

Quoted 21 lines
(quoted diff) +21 -0
+void exit_futex(struct task_struct *tsk)
+{
+	struct mm_struct *mm;
+	struct list_head *robust;
+	struct vm_area_struct *vma;
+	struct mutex *mutex;
+
+	mm = current->mm;
+	if (mm==NULL)
+		return;
+
+	down_read(&mm->mmap_sem);
+
+	for (vma = mm->mmap; vma != NULL; vma = vma->vm_next) {
+		if (vma->vm_file == NULL)
+			continue;
+
+		if (vma->vm_file->f_mapping == NULL)
+			continue;
+
+		if (vma->vm_file->f_mapping->robust_head == NULL)

Review

Quoted 10 lines
(quoted diff) +10 -0
+			continue;
+
+		robust = &vma->vm_file->f_mapping->robust_head->robust_list;
+
+		if (list_empty(robust))
+			continue;
+
+		mutex = &vma->vm_file->f_mapping->robust_head->robust_mutex;
+
+		find_owned_futex(tsk, vma, robust, mutex);

The name "find_owned_mutex" is a bit misleading - it implies that it is some lookup function which has no side-effects. But find_owned_futex() actually makes significant state changes.

Review

Quoted 8 lines
(quoted diff) +8 -0
+
+	if (vma->vm_file && vma->vm_file->f_mapping) {
+		if (vma->vm_file->f_mapping->robust_head == NULL)
+			init_robust_list(vma->vm_file->f_mapping, file_futex);
+		else
+			kmem_cache_free(file_futex_cachep, file_futex);
+		head = &vma->vm_file->f_mapping->robust_head->robust_list;
+		mutex = &vma->vm_file->f_mapping->robust_head->robust_mutex;

The patch in general does an awful lot of these lengthy pointer chases. It's more readable to create temporaries to avoid this. Sometimes it generates better code, too.

The kmem_cache_free above is a bit sad. It means that in the common case we'll allocate a file_futex and then free it again. It's legal to do GFP_KERNEL allocations within mmap_sem, so I suggest you switch this to allocate-only-if-needed.

Review

Quoted 6 lines
(quoted diff) +6 -0
+	} else {
+		ret = -EADDRNOTAVAIL;
+		kmem_cache_free(robust_futex_cachep, robust);
+		kmem_cache_free(file_futex_cachep, file_futex);
+		goto out_unlock;
+	}

Again, we could have checked whether we needed to allocate these before allocating them.

Review

Quoted 4 lines
(quoted diff) +4 -0
+	if (vma->vm_file && vma->vm_file->f_mapping &&
+	    vma->vm_file->f_mapping->robust_head) {
+		mutex = &vma->vm_file->f_mapping->robust_head->robust_mutex;
+		head = &vma->vm_file->f_mapping->robust_head->robust_list;

Pointer chasing, again...

Review

Quoted 3 lines
(quoted diff) +3 -0
+
+	list_for_each_entry_safe(this, next, head, list) {
+		if (match_futex (&this->key, &key)) {

^
A stray space got in there.

Review

Quoted 5 lines
(quoted diff) +4 -0
+#ifdef CONFIG_ROBUST_FUTEX
+	robust_futex_cachep = kmem_cache_create("robust_futex", sizeof(struct futex_robust), 0, 0, NULL, NULL);
+	file_futex_cachep = kmem_cache_create("file_futex", sizeof(struct futex_head), 0, 0, NULL, NULL);
+#endif

A bit of 80-column wrapping needed there please.

Are futex_heads likely to be allocated in sufficient volume to justify their own slab cache, rather than using kmalloc()? The speed is the same - if anything, kmalloc() will be faster because its text and data are more likely to be in CPU cache.

#10 lore raw

Andrew,
I have incorporated the changes you suggested, with the exception of
the check
for a NULL mm in exit_futex. Apparently there is a task that exits in
the boot path
that has a null mm and causes the kernel to crash on boot without this
check.

 fs/inode.c                    |    2
 include/linux/fs.h       |    4
 include/linux/futex.h |   33 ++++
 init/Kconfig                 |    9 +
 kernel/exit.c               |    2
 kernel/futex.c             |  398 
++++++++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 448 insertions(+)

David

Quoted 119 lines · Andrew Morton

Review struct address_space { · line 388

Quoted 10 lines · david singleton

[-ENOCHANGELOG]

(quoted diff) +1 -0
@@ -383,6 +384,7 @@ struct address_space {
 	spinlock_t		private_lock;	/* for use by the address_space */
 	struct list_head	private_list;	/* ditto */
 	struct address_space	*assoc_mapping;	/* ditto */
+	struct futex_head	*robust_head;	/* list of robust futexes */
 } __attribute__((aligned(sizeof(long))));

It's worth putting this field inside CONFIG_ROBUST_FUTEX

Review struct address_space {

Quoted 5 lines
(quoted diff) +5 -0
+#else
+# define futex_free_robust_list(a)      do { } while (0)
+# define exit_futex(b)                  do { } while (0)
+#define futex_init_inode(a) 		do { } while (0)
+#endif

Indenting went wonky.

Quoted 12 lines

+/*
+ * Robust futexes provide a locking mechanism that can be shared between
+ * user mode processes. The major difference between robust futexes and
+ * regular futexes is that when the owner of a robust futex dies, the
+ * next task waiting on the futex will be awakened, will get ownership
+ * of the futex lock, and will receive the error status EOWNERDEAD.
+ *
+ * A robust futex is a 32 bit integer stored in user mode shared memory.

Quoted 8 lines

+ * Bit 31 indicates that there are tasks waiting on the futex.
+ * Bit 30 indicates that the task that owned the futex has died.
+ * Bit 29 indicates that the futex is not recoverable and cannot be used.
+ * Bits 0-28 are the pid of the task that owns the futex lock, or zero if
+ * the futex is not locked.
+ */

Nice comment!

Quoted 8 lines
(quoted diff) +8 -0
+/**
+ * futex_free_robust_list - release the list of registered futexes.
+ * @inode: inode that may be a memory mapped file
+ *
+ * Called from dput() when a dentry reference count reaches zero.
+ * If the dentry is associated with a memory mapped file, then
+ * release the list of registered robust futexes that are contained
+ * in that mapping.

Review

Quoted 10 lines
(quoted diff) +10 -0
+ */
+void futex_free_robust_list(struct inode *inode)
+{
+	struct address_space *mapping;
+	struct list_head *head;
+ 	struct futex_robust *this, *next;
+	struct futex_head *futex_head = NULL;
+
+	if (inode == NULL)
+		return;

Is this test needed?

This function is called when a dentry's refcount falls to zero. But there could be other refs to this inode which might get upset at having their robust futexes thrown away. Shouldn't this be based on inode destruction rather than dentry?

Review

Quoted 3 lines
(quoted diff) +3 -0
+	mapping = inode->i_mapping;
+	if (mapping == NULL)
+		return;

inodes never have a null ->i_mapping

Quoted 5 lines
(quoted diff) +5 -0
+	if (mapping->robust_head == NULL)
+		return;
+
+	if (list_empty(&mapping->robust_head->robust_list))
+		return;

Review

Quoted 10 lines
(quoted diff) +10 -0
+
+	mutex_lock(&mapping->robust_head->robust_mutex);
+
+	head = &mapping->robust_head->robust_list;
+	futex_head = mapping->robust_head;
+
+	list_for_each_entry_safe(this, next, head, list) {
+		list_del(&this->list);
+		kmem_cache_free(robust_futex_cachep, this);
+	}

If we're throwing away the entire contents of the list, there's no need to detach items as we go.

Quoted 23 lines
(quoted diff) +23 -0
+/**
+ * get_shared_uaddr - convert a shared futex_key to a user addr.
+ * @key: a futex_key that identifies a futex.
+ * @vma: a vma that may contain the futex
+ *
+ * Shared futex_keys identify a futex that is contained in a vma,
+ * and so may be shared.
+ * Returns zero if futex is not contained in @vma
+ */
+static unsigned long get_shared_uaddr(union futex_key *key,
+				      struct vm_area_struct *vma)
+{
+	unsigned long uaddr = 0;
+	unsigned long tmpaddr;
+	struct address_space *mapping;
+
+	mapping = vma->vm_file->f_mapping;
+	if (key->shared.inode == mapping->host) {
+		tmpaddr = ((key->shared.pgoff - vma->vm_pgoff) << PAGE_SHIFT)
+				+ (key->shared.offset & ~0x1)
+				+ vma->vm_start;
+		if (tmpaddr >= vma->vm_start && tmpaddr < vma->vm_end)
+			uaddr = tmpaddr;
Quoted 8 lines

Review

Quoted 4 lines
(quoted diff) +4 -0
+	}
+
+	return uaddr;
+}

What locking guarantees that vma->vm_file->f_mapping continues to exist? Bear in mind that another thread which shares this thread's files can close fds, unlink files, munmap files, etc.

This is called under the mmap_sem.

Quoted 127 lines
Quoted 25 lines
(quoted diff) +24 -0
+/**
+ * find_owned_futex - find futexes owned by the current task
+ * @tsk: task that is exiting
+ * @vma: vma containing robust futexes
+ * @head: list head for list of robust futexes
+ * @mutex: mutex that protects the list
+ *
+ * Walk the list of registered robust futexes for this @vma,
+ * setting the %FUTEX_OWNER_DIED flag on those futexes owned
+ * by the current, exiting task.
+ */
+static void
+find_owned_futex(struct task_struct *tsk, struct vm_area_struct *vma,
+		 struct list_head *head, struct mutex *mutex)
+{
+	struct futex_robust *this, *next;
+ 	unsigned long uaddr;
+	int value;
+
+	mutex_lock(mutex);
+
+	list_for_each_entry_safe(this, next, head, list) {
+
+		uaddr = get_futex_uaddr(&this->key, vma);

Review

Quoted 10 lines
(quoted diff) +10 -0
+		if (uaddr == 0)
+			continue;
+
+		mutex_unlock(mutex);
+		up_read(&tsk->mm->mmap_sem);
+		get_user(value, (int __user *)uaddr);
+		if ((value & FUTEX_PID) == tsk->pid) {
+			value |= FUTEX_OWNER_DIED;
+			futex_wake(uaddr, 1);
+			put_user(value, (int *__user)uaddr);

That's a bit unconventional - normally we'd perform the other-task-visible write and _then_ wake up the other task. What prevents the woken task from waking then seeing the not-yet-written-to value?

Quoted 21 lines
(quoted diff) +21 -0
+void exit_futex(struct task_struct *tsk)
+{
+	struct mm_struct *mm;
+	struct list_head *robust;
+	struct vm_area_struct *vma;
+	struct mutex *mutex;
+
+	mm = current->mm;
+	if (mm==NULL)
+		return;
+
+	down_read(&mm->mmap_sem);
+
+	for (vma = mm->mmap; vma != NULL; vma = vma->vm_next) {
+		if (vma->vm_file == NULL)
+			continue;
+
+		if (vma->vm_file->f_mapping == NULL)
+			continue;
+
+		if (vma->vm_file->f_mapping->robust_head == NULL)

Review

Quoted 10 lines
(quoted diff) +10 -0
+			continue;
+
+		robust = &vma->vm_file->f_mapping->robust_head->robust_list;
+
+		if (list_empty(robust))
+			continue;
+
+		mutex = &vma->vm_file->f_mapping->robust_head->robust_mutex;
+
+		find_owned_futex(tsk, vma, robust, mutex);

The name "find_owned_mutex" is a bit misleading - it implies that it is some lookup function which has no side-effects. But find_owned_futex() actually makes significant state changes.

Review

Quoted 8 lines
(quoted diff) +8 -0
+
+	if (vma->vm_file && vma->vm_file->f_mapping) {
+		if (vma->vm_file->f_mapping->robust_head == NULL)
+			init_robust_list(vma->vm_file->f_mapping, file_futex);
+		else
+			kmem_cache_free(file_futex_cachep, file_futex);
+		head = &vma->vm_file->f_mapping->robust_head->robust_list;
+		mutex = &vma->vm_file->f_mapping->robust_head->robust_mutex;

The patch in general does an awful lot of these lengthy pointer chases. It's more readable to create temporaries to avoid this. Sometimes it generates better code, too.

The kmem_cache_free above is a bit sad. It means that in the common case we'll allocate a file_futex and then free it again. It's legal to do GFP_KERNEL allocations within mmap_sem, so I suggest you switch this to allocate-only-if-needed.

Review

Quoted 6 lines
(quoted diff) +6 -0
+	} else {
+		ret = -EADDRNOTAVAIL;
+		kmem_cache_free(robust_futex_cachep, robust);
+		kmem_cache_free(file_futex_cachep, file_futex);
+		goto out_unlock;
+	}

Again, we could have checked whether we needed to allocate these before allocating them.

Review

Quoted 4 lines
(quoted diff) +4 -0
+	if (vma->vm_file && vma->vm_file->f_mapping &&
+	    vma->vm_file->f_mapping->robust_head) {
+		mutex = &vma->vm_file->f_mapping->robust_head->robust_mutex;
+		head = &vma->vm_file->f_mapping->robust_head->robust_list;

Pointer chasing, again...

Review

Quoted 3 lines
(quoted diff) +3 -0
+
+	list_for_each_entry_safe(this, next, head, list) {
+		if (match_futex (&this->key, &key)) {

^
A stray space got in there.

Quoted 7 lines
(quoted diff) +2 -0
+#ifdef CONFIG_ROBUST_FUTEX
+	robust_futex_cachep = kmem_cache_create("robust_futex", 

sizeof(struct futex_robust), 0, 0, NULL, NULL);

(quoted diff) +1 -0
+	file_futex_cachep = kmem_cache_create("file_futex", sizeof(struct 

futex_head), 0, 0, NULL, NULL);
+#endif

A bit of 80-column wrapping needed there please.

Quoted 4 lines

Are futex_heads likely to be allocated in sufficient volume to justify their own slab cache, rather than using kmalloc()? The speed is the same - if anything, kmalloc() will be faster because its text and data are more likely to be in CPU cache.

My tests typically use a slab to a slab and a half of futex_heads. In the real world I honestly don't know how many will be allocated. Can we leave it in it's own cache for testing? It sure helps debugging if the entries in the futex_head cache match exactly what the test application is using.

Quoted 1 line
#11 lore raw
In reply to Andrew Morton
Quoted 11 lines · Andrew Morton
Quoted 10 lines · david singleton
(quoted diff) +10 -0
+	if (mapping->robust_head == NULL)
+		return;
+
+	if (list_empty(&mapping->robust_head->robust_list))
+		return;
+
+	mutex_lock(&mapping->robust_head->robust_mutex);
+
+	head = &mapping->robust_head->robust_list;
+	futex_head = mapping->robust_head;
Quoted 8 lines

Review

Quoted 5 lines
(quoted diff) +5 -0
+
+	list_for_each_entry_safe(this, next, head, list) {
+		list_del(&this->list);
+		kmem_cache_free(robust_futex_cachep, this);
+	}

If we're throwing away the entire contents of the list, there's no need to detach items as we go.

Couldn't even detach the list elements first by

list_splice_init(&mapping->robust_head->robust_list, head);

and free the list from "head" after releasing the mutex? This would reduce lock contention, no?

Quoted 11 lines

Review

Quoted 4 lines
(quoted diff) +4 -0
+#ifdef CONFIG_ROBUST_FUTEX
+	robust_futex_cachep = kmem_cache_create("robust_futex", sizeof(struct futex_robust), 0, 0, NULL, NULL);
+	file_futex_cachep = kmem_cache_create("file_futex", sizeof(struct futex_head), 0, 0, NULL, NULL);
+#endif

A bit of 80-column wrapping needed there please.

Are futex_heads likely to be allocated in sufficient volume to justify their own slab cache, rather than using kmalloc()? The speed is the same - if anything, kmalloc() will be faster because its text and data are more likely to be in CPU cache.

The goal here was to do cheap futex accounting, as described in the documentation to this patch.

Regards

Ingo Oeser

#12 lore raw
Quoted 9 lines · Ingo Oeser
Quoted 8 lines

Review

Quoted 5 lines
(quoted diff) +4 -0
+	list_for_each_entry_safe(this, next, head, list) {
+		list_del(&this->list);
+		kmem_cache_free(robust_futex_cachep, this);
+	}

If we're throwing away the entire contents of the list, there's no need to detach items as we go.

Quoted 6 lines

Couldn't even detach the list elements first by

list_splice_init(&mapping->robust_head->robust_list, head);

and free the list from "head" after releasing the mutex? This would reduce lock contention, no?

Yes, it would reduce lock contention nicely.

#13 lore raw
Quoted 10 lines · Andrew Morton
Quoted 9 lines · Ingo Oeser
Quoted 8 lines

Review

Quoted 5 lines
(quoted diff) +4 -0
+	list_for_each_entry_safe(this, next, head, list) {
+		list_del(&this->list);
+		kmem_cache_free(robust_futex_cachep, this);
+	}

If we're throwing away the entire contents of the list, there's no need to detach items as we go.

Quoted 9 lines
Quoted 6 lines

Couldn't even detach the list elements first by

list_splice_init(&mapping->robust_head->robust_list, head);

and free the list from "head" after releasing the mutex? This would reduce lock contention, no?

Yes, it would reduce lock contention nicely.

Incorporated changes suggested by Andrew Morton and Ingo Oeser.

 fs/inode.c            |    2
 include/linux/fs.h    |    4
 include/linux/futex.h |   33 ++++
 init/Kconfig          |    9 +
 kernel/exit.c         |    2
 kernel/futex.c        |  399 
++++++++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 449 insertions(+)

David

#14 lore raw
In reply to Andrew Morton
Quoted 21 lines · Andrew Morton
Quoted 8 lines
(quoted diff) +8 -0
+/**
+ * futex_free_robust_list - release the list of registered futexes.
+ * @inode: inode that may be a memory mapped file
+ *
+ * Called from dput() when a dentry reference count reaches zero.
+ * If the dentry is associated with a memory mapped file, then
+ * release the list of registered robust futexes that are contained
+ * in that mapping.

Review

Quoted 10 lines
(quoted diff) +10 -0
+ */
+void futex_free_robust_list(struct inode *inode)
+{
+     struct address_space *mapping;
+     struct list_head *head;
+     struct futex_robust *this, *next;
+     struct futex_head *futex_head = NULL;
+
+     if (inode == NULL)
+             return;

Is this test needed?

Quoted 5 lines

This function is called when a dentry's refcount falls to zero. But there could be other refs to this inode which might get upset at having their robust futexes thrown away. Shouldn't this be based on inode destruction rather than dentry?

In an early version, it was based on inode destruction. But inodes are not destroyed
at process termination. If I understand the code, they're cached so that another process that opens the same file will not have to build the inode from scratch.

So I based it on the dentry's refcount falling to zero, which occurs at process termination. I did consider the problem of other references to the inode. The only
scenario I could come up with was mapping the file using hard links. Then there would be multiple dentrys referencing the same inode. This could be fixed by adding a refcount to the futex_robust structure, but I never got around to doing this.

Todd.