Skip to contentSkip to conversation

robust futexes for 2.6.12-rc6

RFC/Patch Todd Kneisel 2 participants 3 messages Jun 15, 2005 – Jun 16, 2005

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

This patch adds robust futex support to the existing sys_futex system call. The patch applies to 2.6.12-rc6. I have tested this code on an IA64 SMP system. Any comments or discussion will be welcome.

Sys_futex provides operations on futexes that can be local to a process, or shared between processes by placing the futex in shared memory. However, if a process terminates while it owns a locked shared futex, any other processes that uses the same futex will hang.

If a process terminates while it owns a locked robust futex, the ownership of the lock will be transferred to the next waiting process, the waiting process will be awakened and will receive the status EOWNERDEAD. If there is no waiting process at the time of termination, then the next process that attempts to wait will receive ownership of the futex and the EOWNERDEAD status. The new owner can recover the futex and unlock it, in which case the futex can continue to be used. If the new owner only unlocks the futex, then the futex becomes unrecoverable and any attempt to use the futex will get the status ENOTRECOVERABLE.

The patch does not change the existing sys_futex operations on non-robust mutexes, so the patch should not affect existing code that uses futexes. New op codes are added to the sys_futex system call for use by code that requires robust futexes. I have a patch to glibc and the nptl thread library that uses robust futexes. We are in the process of getting copyright assignments to the Free Software Foundation so that we can submit the glibc and nptl patches.

Robust futexes have a different format from the non-robust futexes. The non-robust futexes can have the values 0 (unlocked), 1 (locked) or 2 (locked with waiters). In a robust futex the high bit indicates if there are processes waiting on the futex, the next bit indicates if the owning process died, and the next bit indicates if the futex is not recoverable. The rest of the futex contains the pid of the task that owns the futex lock or zero if the futex is not locked.

For this code to work, robust futexes must be in shared memory.

I plan to create a kernel config option for this code.

Robust futexes must be registered with the kernel when created and deregistered when no longer required. Process termination will clean up any registered futexes that were not deregistered.

Memory is allocated when a futex is registered. This memory is freed when the reference count of the memory mapped file's dentry reaches zero. There is a problem here if the memory mapped file has hard links. This would result in multiple dentrys for the file. The memory would be freed when the reference count of any dentry reached zero, while the file is still mapped by other dentrys. I believe I can fix this by adding a reference count for the allocated memory. This is on my to-do list.

fs/dcache.c +3 -0
diff -uprN -X dontdiff linux-2.6.12-rc6/fs/dcache.c linux-2.6.12-todd/fs/dcache.c
@@ -32,6 +32,7 @@
 #include <linux/seqlock.h>
 #include <linux/swap.h>
 #include <linux/bootmem.h>
+#include <linux/futex.h>
 
 /* #define DCACHE_DEBUG 1 */
 
@@ -158,6 +159,8 @@ repeat:
 		return;
 	}
 
+	futex_free_robust_list(dentry->d_inode);
+
 	/*
 	 * AV: ->d_delete() is _NOT_ allowed to block now.
 	 */
fs/inode.c +2 -0
diff -uprN -X dontdiff linux-2.6.12-rc6/fs/inode.c linux-2.6.12-todd/fs/inode.c
@@ -202,6 +202,8 @@ void inode_init_once(struct inode *inode
 	INIT_LIST_HEAD(&inode->i_data.i_mmap_nonlinear);
 	spin_lock_init(&inode->i_lock);
 	i_size_ordered_init(inode);
+	INIT_LIST_HEAD(&inode->i_data.robust_list);
+	init_MUTEX(&inode->i_data.robust_sem);
 }
 
 EXPORT_SYMBOL(inode_init_once);
include/linux/fs.h +2 -0
diff -uprN -X dontdiff linux-2.6.12-rc6/include/linux/fs.h linux-2.6.12-todd/include/linux/fs.h
@@ -350,6 +350,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;	/* protect list of robust futexes */
 } __attribute__((aligned(sizeof(long))));
 	/*
 	 * On most architectures that alignment is already the case; but
include/linux/futex.h +11 -0
diff -uprN -X dontdiff linux-2.6.12-rc6/include/linux/futex.h linux-2.6.12-todd/include/linux/futex.h
@@ -1,6 +1,8 @@
 #ifndef _LINUX_FUTEX_H
 #define _LINUX_FUTEX_H
 
+#include <linux/fs.h>
+
 /* Second argument to futex syscall */
 
 
@@ -9,9 +11,18 @@
 #define FUTEX_FD (2)
 #define FUTEX_REQUEUE (3)
 #define FUTEX_CMP_REQUEUE (4)
+#define FUTEX_WAIT_ROBUST (5)
+#define FUTEX_WAKE_ROBUST (6)
+#define FUTEX_REGISTER (7)
+#define FUTEX_DEREGISTER (8)
+#define FUTEX_RECOVER (9)
 
 long do_futex(unsigned long uaddr, int op, int val,
 		unsigned long timeout, unsigned long uaddr2, int val2,
 		int val3);
 
+void futex_free_robust_list(struct inode *inode);
+
+void exit_futex(void);
+
 #endif
kernel/exit.c +3 -0
diff -uprN -X dontdiff linux-2.6.12-rc6/kernel/exit.c linux-2.6.12-todd/kernel/exit.c
@@ -28,6 +28,7 @@
 #include <linux/cpuset.h>
 #include <linux/syscalls.h>
 #include <linux/signal.h>
+#include <linux/futex.h>
 
 #include <asm/uaccess.h>
 #include <asm/unistd.h>
@@ -815,6 +816,8 @@ fastcall NORET_TYPE void do_exit(long co
  		del_timer_sync(&tsk->signal->real_timer);
 		acct_process(code);
 	}
+
+	exit_futex();
 	exit_mm(tsk);
 
 	exit_sem(tsk);
kernel/futex.c +555 -2

617 lines not on this page · raw message

#1 lore raw
Quoted 3 lines · Todd Kneisel

This patch adds robust futex support to the existing sys_futex system call. The patch applies to 2.6.12-rc6. I have tested this code on an IA64 SMP system. Any comments or discussion will be welcome.

How does this compare to the robust mutexes portion of the stuff that Inaky was working on?

Chris

#2 lore raw

Chris Friesen <[email protected]> wrote on 06/15/2005 09:22:32 PM:

Quoted 2 lines
Quoted 1 line · Todd Kneisel

This patch adds robust futex support to the existing sys_futex system

call.

Quoted 1 line
Quoted 1 line

The patch applies to 2.6.12-rc6. I have tested this code on an IA64

SMP

Quoted 6 lines
Quoted 1 line

system. Any comments or discussion will be welcome.

How does this compare to the robust mutexes portion of the stuff that Inaky was working on?

Chris

It's my understanding that Inaky is redesigning the locking mechanism that the kernel provides for use by the NPTL thread library. I'm adding robustness to the existing locking mechanism.

Inaky's code adds five system calls, one for each operation, where I am adding operations to the existing sys_futex call.

Inaky's code is more complex due to the priority inheritance features. I'm not doing priority inheritance. The application that Bull is developing does not require priority inheritance.

The user interface in the NPTL thread library should be the same. The API is based on the Solaris implementation of robust mutexes. It's not based on Solaris code, only on the documentation of the API.

I believe that Inaky's NPTL implementation intends to have two NPTL libraries on the system. The standard one that uses sys_futex, and an RTNPTL that uses his new system calls. I hope to get my changes into the standard NPTL library.

Todd