Attachment 206091 Details for Bug 245338 – back port changes from RT Linux mainline

[patch] back port changes from RT Linux mainline

peterz-file_table-backport.patch (text/plain), 30.01 KB, created by Steven Rostedt on 2007-09-25 20:29:03 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Steven Rostedt

Created: 2007-09-25 20:29:03 UTC

Size: 30.01 KB

patch

obsolete

>
>rollup of the s_files conversion
>
>split up patch queue attached, seems to build, will boot-test in a bit.
>
>---
>Index: linux-2.6.21-rt-hack/fs/file_table.c
>===================================================================
>--- linux-2.6.21-rt-hack.orig/fs/file_table.c
>+++ linux-2.6.21-rt-hack/fs/file_table.c
>@@ -29,9 +29,6 @@ struct files_stat_struct files_stat = {
> 	.max_files = NR_FILE
> };
> 
>-/* public. Not pretty! */
>-__cacheline_aligned_in_smp DEFINE_SPINLOCK(files_lock);
>-
> static struct percpu_counter nr_files __cacheline_aligned_in_smp;
> 
> static inline void file_free_rcu(struct rcu_head *head)
>@@ -245,201 +242,35 @@ void put_filp(struct file *file)
> 	}
> }
> 
>-enum {
>-	FILEVEC_SIZE = 15
>-};
>-
>-struct filevec {
>-	unsigned long nr;
>-	struct file *files[FILEVEC_SIZE];
>-};
>-
>-static DEFINE_PER_CPU_LOCKED(struct filevec, sb_fvec);
>-
>-static inline unsigned int filevec_size(struct filevec *fvec)
>-{
>-	return FILEVEC_SIZE - fvec->nr;
>-}
>-
>-static inline unsigned int filevec_count(struct filevec *fvec)
>-{
>-	return fvec->nr;
>-}
>-
>-static inline void filevec_reinit(struct filevec *fvec)
>-{
>-	fvec->nr = 0;
>-}
>-
>-static inline unsigned int filevec_add(struct filevec *fvec, struct file *filp)
>+void file_move(struct file *file, struct percpu_list *list)
> {
>-	rcu_assign_pointer(fvec->files[fvec->nr], filp);
>-
>-	/*
>-	 * Here we do icky stuff in order to avoid flushing the per cpu filevec
>-	 * on list removal.
>-	 *
>-	 * We store the location on the per cpu filevec in the as of yet unused
>-	 * fu_llist.next field and toggle bit 0 to indicate we done so. This
>-	 * allows the removal code to set the filevec entry to NULL, thereby
>-	 * avoiding the list add.
>-	 *
>-	 * Abuse the fu_llist.lock for protection.
>-	 */
>-	spin_lock(&filp->f_u.fu_llist.lock);
>-	filp->f_u.fu_llist.next = (void *)&fvec->files[fvec->nr];
>-	__set_bit(0, (void *)&filp->f_u.fu_llist.next);
>-	spin_unlock(&filp->f_u.fu_llist.lock);
>-
>-	fvec->nr++;
>-	return filevec_size(fvec);
>-}
>-
>-static void __filevec_add(struct filevec *fvec)
>-{
>-	int i;
>-
>-	for (i = 0; i < filevec_count(fvec); i++) {
>-		struct file *filp;
>-
>-		/*
>-		 * see the comment in filevec_add();
>-		 * need RCU because a concurrent remove might have deleted
>-		 * the entry from under us.
>-		 */
>-		rcu_read_lock();
>-		filp = rcu_dereference(fvec->files[i]);
>-		/*
>-		 * the simple case, its gone - NEXT!
>-		 */
>-		if (!filp) {
>-			rcu_read_unlock();
>-			continue;
>-		}
>-
>-		spin_lock(&filp->f_u.fu_llist.lock);
>-		/*
>-		 * If the entry really is still there, add it!
>-		 */
>-		if (rcu_dereference(fvec->files[i])) {
>-			struct super_block *sb =
>-				filp->f_mapping->host->i_sb;
>-
>-			__lock_list_add(&filp->f_u.fu_llist, &sb->s_files);
>-		}
>-		spin_unlock(&filp->f_u.fu_llist.lock);
>-		rcu_read_unlock();
>-	}
>-	filevec_reinit(fvec);
>-}
>-
>-/*
>- * Flush files per-CPU workqueue:
>- */
>-static struct workqueue_struct *flush_files_workqueue;
>-
>-int __init flush_files_init(void)
>-{
>-        flush_files_workqueue = create_workqueue("flush_filesd");
>-        if (!flush_files_workqueue)
>-                panic("Failed to create flush_filesd\n");
>-
>-	return 0;
>-}
>-
>-__initcall(flush_files_init);
>-
>-static void filevec_add_drain(void)
>-{
>-	int cpu;
>-	struct filevec *fvec = &get_cpu_var_locked(sb_fvec, &cpu);
>-	if (filevec_count(fvec))
>-		__filevec_add(fvec);
>-	put_cpu_var_locked(sb_fvec, cpu);
>-}
>-
>-static void filevec_add_drain_per_cpu(struct work_struct *none)
>-{
>-	filevec_add_drain();
>-}
>+	if (!list)
>+		return;
> 
>-int filevec_add_drain_all(void)
>-{
>-	return schedule_on_each_cpu_wq(flush_files_workqueue,
>-				       filevec_add_drain_per_cpu);
>+	file_kill(file);
>+	percpu_list_add(list, &file->f_u.fu_llist);
> }
>-EXPORT_SYMBOL_GPL(filevec_add_drain_all);
> 
> void file_kill(struct file *file)
> {
> 	if (file && file->f_mapping && file->f_mapping->host) {
> 		struct super_block *sb = file->f_mapping->host->i_sb;
> 		if (sb)
>-			barrier_sync(&sb->s_barrier);
>+			synchronize_qrcu(&sb->s_qrcu);
> 	}
> 
>-	if (file_flag(file, F_SUPERBLOCK)) {
>-		void **ptr;
>-
>-		file_flag_clear(file, F_SUPERBLOCK);
>-
>-		/*
>-		 * If bit 0 of the fu_llist.next pointer is set we're still
>-		 * enqueued on a per cpu filevec, in that case clear the entry
>-		 * and we're done.
>-		 */
>-		spin_lock(&file->f_u.fu_llist.lock);
>-		ptr = (void **)file->f_u.fu_llist.next;
>-		if (__test_and_clear_bit(0, (void *)&ptr)) {
>-			rcu_assign_pointer(*ptr, NULL);
>-			INIT_LIST_HEAD(&file->f_u.fu_llist.head);
>-			spin_unlock(&file->f_u.fu_llist.lock);
>-			return;
>-		}
>-		spin_unlock(&file->f_u.fu_llist.lock);
>-
>-		if (!list_empty(&file->f_u.fu_list))
>-			lock_list_del_init(&file->f_u.fu_llist);
>-
>-	} else if (!list_empty(&file->f_u.fu_list)) {
>-		file_list_lock();
>-		list_del_init(&file->f_u.fu_list);
>-		file_list_unlock();
>-	}
>-}
>-
>-void file_move(struct file *file, struct list_head *list)
>-{
>-	struct super_block *sb;
>-
>-	if (!list)
>-		return;
>-
>-	file_kill(file);
>-
>-	sb = file->f_mapping->host->i_sb;
>-	if (list == &sb->s_files.head) {
>-		int cpu;
>-		struct filevec *fvec = &get_cpu_var_locked(sb_fvec, &cpu);
>-		file_flag_set(file, F_SUPERBLOCK);
>-		if (!filevec_add(fvec, file))
>-			__filevec_add(fvec);
>-		put_cpu_var_locked(sb_fvec, cpu);
>-	} else {
>-		file_list_lock();
>-		list_add(&file->f_u.fu_list, list);
>-		file_list_unlock();
>-	}
>+	lock_list_del_init(&file->f_u.fu_llist);
> }
> 
> int fs_may_remount_ro(struct super_block *sb)
> {
> 	struct file *file;
>+	int idx;
> 
> 	/* Check that no files are currently opened for writing. */
>-	barrier_lock(&sb->s_barrier);
>-	filevec_add_drain_all();
>-	lock_list_for_each_entry(file, &sb->s_files, f_u.fu_llist) {
>+	idx = qrcu_read_lock(&sb->s_qrcu);
>+	percpu_list_fold(&sb->s_files);
>+	lock_list_for_each_entry(file, percpu_list_head(&sb->s_files), f_u.fu_llist) {
> 		struct inode *inode = file->f_path.dentry->d_inode;
> 
> 		/* File with pending delete? */
>@@ -450,11 +281,11 @@ int fs_may_remount_ro(struct super_block
> 		if (S_ISREG(inode->i_mode) && (file->f_mode & FMODE_WRITE))
> 			goto too_bad;
> 	}
>-	barrier_unlock(&sb->s_barrier);
>+	qrcu_read_unlock(&sb->s_qrcu, idx);
> 	return 1; /* Tis' cool bro. */
> too_bad:
> 	lock_list_for_each_entry_stop(file, f_u.fu_llist);
>-	barrier_unlock(&sb->s_barrier);
>+	qrcu_read_unlock(&sb->s_qrcu, idx);
> 	return 0;
> }
> 
>Index: linux-2.6.21-rt-hack/fs/open.c
>===================================================================
>--- linux-2.6.21-rt-hack.orig/fs/open.c
>+++ linux-2.6.21-rt-hack/fs/open.c
>@@ -692,7 +692,7 @@ static struct file *__dentry_open(struct
> 	f->f_path.mnt = mnt;
> 	f->f_pos = 0;
> 	f->f_op = fops_get(inode->i_fop);
>-	file_move(f, &inode->i_sb->s_files.head);
>+	file_move(f, &inode->i_sb->s_files);
> 
> 	if (!open && f->f_op)
> 		open = f->f_op->open;
>Index: linux-2.6.21-rt-hack/fs/proc/generic.c
>===================================================================
>--- linux-2.6.21-rt-hack.orig/fs/proc/generic.c
>+++ linux-2.6.21-rt-hack/fs/proc/generic.c
>@@ -571,7 +571,7 @@ static void proc_kill_inodes(struct proc
> 	/*
> 	 * Actually it's a partial revoke().
> 	 */
>-	lock_list_for_each_entry(filp, &sb->s_files, f_u.fu_llist) {
>+	lock_list_for_each_entry(filp, percpu_list_head(&sb->s_files), f_u.fu_llist) {
> 		struct dentry * dentry = filp->f_path.dentry;
> 		struct inode * inode;
> 		const struct file_operations *fops;
>@@ -730,9 +730,9 @@ void remove_proc_entry(const char *name,
> 	if (!parent && xlate_proc_name(name, &parent, &fn) != 0)
> 		goto out;
> 	len = strlen(fn);
>-	filevec_add_drain_all();
>-
> again:
>+	percpu_list_fold(&proc_mnt->mnt_sb->s_files);
>+
> 	spin_lock(&proc_subdir_lock);
> 	for (p = &parent->subdir; *p; p=&(*p)->next ) {
> 		if (!proc_match(len, fn, *p))
>Index: linux-2.6.21-rt-hack/fs/super.c
>===================================================================
>--- linux-2.6.21-rt-hack.orig/fs/super.c
>+++ linux-2.6.21-rt-hack/fs/super.c
>@@ -67,8 +67,8 @@ static struct super_block *alloc_super(s
> 		}
> 		INIT_LIST_HEAD(&s->s_dirty);
> 		INIT_LIST_HEAD(&s->s_io);
>-		INIT_LOCK_LIST_HEAD(&s->s_files);
>-		init_barrier(&s->s_barrier);
>+		percpu_list_init(&s->s_files);
>+		init_qrcu_struct(&s->s_qrcu);
> 		INIT_LIST_HEAD(&s->s_instances);
> 		INIT_HLIST_HEAD(&s->s_anon);
> 		INIT_LIST_HEAD(&s->s_inodes);
>@@ -107,6 +107,7 @@ out:
>  */
> static inline void destroy_super(struct super_block *s)
> {
>+	percpu_list_destroy(&s->s_files);
> 	security_sb_free(s);
> 	kfree(s);
> }
>@@ -568,14 +569,15 @@ out:
> static void mark_files_ro(struct super_block *sb)
> {
> 	struct file *f;
>+	int idx;
> 
>-	barrier_lock(&sb->s_barrier);
>-	filevec_add_drain_all();
>-	lock_list_for_each_entry(f, &sb->s_files, f_u.fu_llist) {
>+	idx = qrcu_read_lock(&sb->s_qrcu);
>+	percpu_list_fold(&sb->s_files);
>+	lock_list_for_each_entry(f, percpu_list_head(&sb->s_files), f_u.fu_llist) {
> 		if (S_ISREG(f->f_path.dentry->d_inode->i_mode) && file_count(f))
> 			f->f_mode &= ~FMODE_WRITE;
> 	}
>-	barrier_unlock(&sb->s_barrier);
>+	qrcu_read_unlock(&sb->s_qrcu, idx);
> }
> 
> /**
>Index: linux-2.6.21-rt-hack/include/linux/fs.h
>===================================================================
>--- linux-2.6.21-rt-hack.orig/include/linux/fs.h
>+++ linux-2.6.21-rt-hack/include/linux/fs.h
>@@ -276,13 +276,13 @@ extern int dir_notify_enable;
> #include <linux/cache.h>
> #include <linux/kobject.h>
> #include <linux/list.h>
>-#include <linux/lock_list.h>
>+#include <linux/percpu_list.h>
> #include <linux/radix-tree.h>
> #include <linux/prio_tree.h>
> #include <linux/init.h>
> #include <linux/pid.h>
> #include <linux/mutex.h>
>-#include <linux/barrier.h>
>+#include <linux/srcu.h>
> 
> #include <asm/atomic.h>
> #include <asm/semaphore.h>
>@@ -710,14 +710,10 @@ struct file_ra_state {
> 
> struct file {
> 	/*
>-	 * fu_list becomes invalid after file_free is called and queued via
>+	 * fu_llist becomes invalid after file_free is called and queued via
> 	 * fu_rcuhead for RCU freeing
>-	 * fu_llist is used for the superblock s_files list; its crucial that
>-	 * the spinlock contained therein is not clobbered by other uses of
>-	 * the union.
> 	 */
> 	union {
>-		struct list_head	fu_list;
> 		struct lock_list_head	fu_llist;
> 		struct rcu_head 	fu_rcuhead;
> 	} f_u;
>@@ -747,29 +743,10 @@ struct file {
> #endif /* #ifdef CONFIG_EPOLL */
> 	struct address_space	*f_mapping;
> };
>-extern spinlock_t files_lock;
>-#define file_list_lock() spin_lock(&files_lock);
>-#define file_list_unlock() spin_unlock(&files_lock);
>-
>-/*
>- * steal the upper 8 bits from the read-a-head flags
>- */
>-#define F_SHIFT		24
>-
>-#define F_SUPERBLOCK	0
>-
>-#define file_flag_set(file, flag)	\
>-	__set_bit((flag) + F_SHIFT, &(file)->f_ra.flags)
>-#define file_flag_clear(file, flag)	\
>-	__clear_bit((flag) + F_SHIFT, &(file)->f_ra.flags)
>-#define file_flag(file, flag)		\
>-	test_bit((flag) + F_SHIFT, &(file)->f_ra.flags)
> 
> #define get_file(x)	atomic_inc(&(x)->f_count)
> #define file_count(x)	atomic_read(&(x)->f_count)
> 
>-extern int filevec_add_drain_all(void);
>-
> #define	MAX_NON_LFS	((1UL<<31) - 1)
> 
> /* Page cache limit. The filesystems should put that into their s_maxbytes 
>@@ -951,8 +928,8 @@ struct super_block {
> 	struct list_head	s_dirty;	/* dirty inodes */
> 	struct list_head	s_io;		/* parked for writeback */
> 	struct hlist_head	s_anon;		/* anonymous dentries for (nfs) exporting */
>-	struct lock_list_head	s_files;
>-	struct barrier		s_barrier;
>+	struct percpu_list	s_files;
>+	struct qrcu_struct	s_qrcu;
> 
> 	struct block_device	*s_bdev;
> 	struct list_head	s_instances;
>@@ -1719,7 +1696,7 @@ static inline void insert_inode_hash(str
> }
> 
> extern struct file * get_empty_filp(void);
>-extern void file_move(struct file *f, struct list_head *list);
>+extern void file_move(struct file *f, struct percpu_list *list);
> extern void file_kill(struct file *f);
> #ifdef CONFIG_BLOCK
> struct bio;
>Index: linux-2.6.21-rt-hack/lib/Makefile
>===================================================================
>--- linux-2.6.21-rt-hack.orig/lib/Makefile
>+++ linux-2.6.21-rt-hack/lib/Makefile
>@@ -2,8 +2,8 @@
> # Makefile for some libs needed in the kernel.
> #
> 
>-lib-y := ctype.o string.o vsprintf.o cmdline.o lock_list.o \
>-	 rbtree.o radix-tree.o dump_stack.o \
>+lib-y := ctype.o string.o vsprintf.o cmdline.o \
>+	 rbtree.o radix-tree.o dump_stack.o lock_list.o \
> 	 idr.o div64.o int_sqrt.o bitmap.o extable.o prio_tree.o \
> 	 sha1.o irq_regs.o reciprocal_div.o
> 
>Index: linux-2.6.21-rt-hack/mm/readahead.c
>===================================================================
>--- linux-2.6.21-rt-hack.orig/mm/readahead.c
>+++ linux-2.6.21-rt-hack/mm/readahead.c
>@@ -69,7 +69,7 @@ static inline void reset_ahead_window(st
> static inline void ra_off(struct file_ra_state *ra)
> {
> 	ra->start = 0;
>-	ra->flags &= (~0UL) << F_SHIFT;
>+	ra->flags = 0;
> 	ra->size = 0;
> 	reset_ahead_window(ra);
> 	return;
>Index: linux-2.6.21-rt-hack/security/selinux/selinuxfs.c
>===================================================================
>--- linux-2.6.21-rt-hack.orig/security/selinux/selinuxfs.c
>+++ linux-2.6.21-rt-hack/security/selinux/selinuxfs.c
>@@ -943,6 +943,7 @@ static void sel_remove_bools(struct dent
> 	struct list_head *node;
> 	struct file *filp;
> 	struct super_block *sb = de->d_sb;
>+	int idx;
> 
> 	spin_lock(&dcache_lock);
> 	node = de->d_subdirs.next;
>@@ -963,9 +964,9 @@ static void sel_remove_bools(struct dent
> 
> 	spin_unlock(&dcache_lock);
> 
>-	barrier_lock(&sb->s_barrier);
>-	filevec_add_drain_all();
>-	lock_list_for_each_entry(filp, &sb->s_files, f_u.fu_llist) {
>+	idx = qrcu_read_lock(&sb->s_qrcu);
>+	percpu_list_fold(&sb->s_files);
>+	lock_list_for_each_entry(filp, percpu_list_head(&sb->s_files), f_u.fu_llist) {
> 		struct dentry * dentry = filp->f_path.dentry;
> 
> 		if (dentry->d_parent != de) {
>@@ -973,7 +974,7 @@ static void sel_remove_bools(struct dent
> 		}
> 		filp->f_op = NULL;
> 	}
>-	barrier_unlock(&sb->s_barrier);
>+	qrcu_read_unlock(&sb->s_qrcu, idx);
> }
> 
> #define BOOL_DIR_NAME "booleans"
>Index: linux-2.6.21-rt-hack/include/linux/lock_list.h
>===================================================================
>--- linux-2.6.21-rt-hack.orig/include/linux/lock_list.h
>+++ linux-2.6.21-rt-hack/include/linux/lock_list.h
>@@ -38,41 +38,15 @@ static inline void INIT_LOCK_LIST_HEAD(s
> /*
>  * Passed pointers are assumed stable by external means (refcount, rcu)
>  */
>-extern void __lock_list_add(struct lock_list_head *new,
>-			    struct lock_list_head *list);
>-
>-static inline void lock_list_add(struct lock_list_head *new,
>-			    struct lock_list_head *list)
>-{
>-	spin_lock(&new->lock);
>-	__lock_list_add(new, list);
>-	spin_unlock(&new->lock);
>-}
>-
>+extern void lock_list_add(struct lock_list_head *new,
>+			  struct lock_list_head *list);
> extern void lock_list_del_init(struct lock_list_head *entry);
>+extern void lock_list_splice_init(struct lock_list_head *list,
>+				  struct lock_list_head *head);
> 
>-static inline
> struct lock_list_head *lock_list_next_entry(struct lock_list_head *list,
>-					    struct lock_list_head *entry)
>-{
>-	struct lock_list_head *next = entry->next;
>-	if (likely(next != list)) {
>-		lock_set_subclass(&entry->lock.dep_map,
>-				  LOCK_LIST_NESTING_CUR, _THIS_IP_);
>-		spin_lock_nested(&next->lock, LOCK_LIST_NESTING_NEXT);
>-		BUG_ON(entry->next != next);
>-	} else
>-		next = NULL;
>-	spin_unlock(&entry->lock);
>-	return next;
>-}
>-
>-static inline
>-struct lock_list_head *lock_list_first_entry(struct lock_list_head *list)
>-{
>-	spin_lock(&list->lock);
>-	return lock_list_next_entry(list, list);
>-}
>+					    struct lock_list_head *entry);
>+struct lock_list_head *lock_list_first_entry(struct lock_list_head *list);
> 
> #define lock_list_for_each_entry(pos, list, member)			\
> 	for (pos = list_entry(lock_list_first_entry(list), 		\
>@@ -81,6 +55,18 @@ struct lock_list_head *lock_list_first_e
> 	     pos = list_entry(lock_list_next_entry(list, &pos->member),	\
> 			      typeof(*pos), member))
> 
>+/*
>+ * to be used when iteration is terminated by breaking out of the
>+ * lock_list_for_each_entry() loop.
>+ *
>+ * 	lock_list_for_each_entry(i, list, member) {
>+ * 		if (cond) {
>+ * 			lock_list_for_each_entry_stop(i, member);
>+ * 			goto foo;
>+ * 		}
>+ * 	}
>+ *
>+ */
> #define lock_list_for_each_entry_stop(pos, member)			\
> 	spin_unlock(&(pos->member.lock))
> 
>Index: linux-2.6.21-rt-hack/lib/lock_list.c
>===================================================================
>--- linux-2.6.21-rt-hack.orig/lib/lock_list.c
>+++ linux-2.6.21-rt-hack/lib/lock_list.c
>@@ -11,31 +11,37 @@
>  *
>  * Passed pointers are assumed to be stable by external means such as
>  * refcounts or RCU. The individual list entries are assumed to be RCU
>- * freed (requirement of __lock_list_del).
>+ * freed (requirement of __lock_list).
>  */
> 
> #include <linux/lock_list.h>
> 
>-void __lock_list_add(struct lock_list_head *new,
>-		     struct lock_list_head *list)
>+void lock_list_add(struct lock_list_head *new,
>+		   struct lock_list_head *list)
> {
>-	struct lock_list_head *next;
>-
>+	spin_lock(&new->lock);
> 	spin_lock_nested(&list->lock, LOCK_LIST_NESTING_PREV);
>-	next = list->next;
>-	__list_add(&new->head, &list->head, &next->head);
>+	__list_add(&new->head, &list->head, &list->next->head);
> 	spin_unlock(&list->lock);
>+	spin_unlock(&new->lock);
> }
> 
>-void lock_list_del_init(struct lock_list_head *entry)
>+static spinlock_t *__lock_list(struct lock_list_head *entry)
> {
>-	struct lock_list_head *prev, *next;
>+	struct lock_list_head *prev;
>+	spinlock_t *lock = NULL;
> 
>-	rcu_read_lock();
> again:
>+	/*
>+	 * all modifications are done under spinlocks
>+	 * but this read is not, the unlock acks as a wmb
>+	 * for modifications.
>+	 */
>+	smp_rmb();
>+
> 	prev = entry->prev;
> 	if (prev == entry)
>-		goto out;
>+		goto one;
> 	spin_lock_nested(&prev->lock, LOCK_LIST_NESTING_PREV);
> 	if (unlikely(entry->prev != prev)) {
> 		/*
>@@ -44,12 +50,112 @@ again:
> 		spin_unlock(&prev->lock);
> 		goto again;
> 	}
>+	lock = &prev->lock;
>+one:
> 	spin_lock_nested(&entry->lock, LOCK_LIST_NESTING_CUR);
>-	next = entry->next;
>-	__list_del(&prev->head, &next->head);
>-	INIT_LIST_HEAD(&entry->head);
>+	return lock;
>+}
>+
>+/*
>+ * deadlock galore...
>+ *
>+ * when using __lock_list to lock the list head we get this:
>+ *
>+ *     lock H      2               1
>+ *     lock 1      a       b
>+ *     lock 2              A       B
>+ *
>+ *     list: ..-> [H] <-> [1] <-> [2] <-..
>+ *
>+ * obvious dead-lock, to solve this we must use a reverse order
>+ * when trying to acquire a double lock on the head:
>+ *
>+ *     lock H r    1               2
>+ *     lock 1      a       b
>+ *     lock 2              A       B
>+ *
>+ *     list: ..-> [H] <-> [1] <-> [2] <-..
>+ */
>+static spinlock_t *__lock_list_reverse(struct lock_list_head *entry)
>+{
>+	struct lock_list_head *prev;
>+	spinlock_t *lock = NULL;
>+
>+	spin_lock(&entry->lock);
>+again:
>+	/*
>+	 * all modifications are done under spinlocks
>+	 * but this read is not, the unlock acks as a wmb
>+	 * for modifications.
>+	 */
>+	smp_rmb();
>+	prev = entry->prev;
>+	if (prev == entry)
>+		goto done;
>+
>+	spin_lock_nested(&prev->lock, LOCK_LIST_NESTING_PREV);
>+	if (unlikely(entry->prev != prev)) {
>+		/*
>+		 * we lost
>+		 */
>+		spin_unlock(&prev->lock);
>+		goto again;
>+	}
>+	lock = &prev->lock;
>+done:
>+	return lock;
>+}
>+
>+void lock_list_del_init(struct lock_list_head *entry)
>+{
>+	spinlock_t *lock;
>+
>+	rcu_read_lock();
>+	lock = __lock_list(entry);
>+	list_del_init(&entry->head);
> 	spin_unlock(&entry->lock);
>-	spin_unlock(&prev->lock);
>-out:
>+	if (lock)
>+		spin_unlock(lock);
>+	rcu_read_unlock();
>+}
>+
>+void lock_list_splice_init(struct lock_list_head *list,
>+			struct lock_list_head *head)
>+{
>+	spinlock_t *lock;
>+
>+	rcu_read_lock();
>+	lock = __lock_list_reverse(list);
>+	if (!list_empty(&list->head)) {
>+		spin_lock_nested(&head->lock, LOCK_LIST_NESTING_NEXT);
>+		__list_splice(&list->head, &head->head);
>+		INIT_LIST_HEAD(&list->head);
>+		spin_unlock(&head->lock);
>+	}
>+	spin_unlock(&list->lock);
>+	if (lock)
>+		spin_unlock(lock);
> 	rcu_read_unlock();
> }
>+
>+struct lock_list_head *lock_list_next_entry(struct lock_list_head *list,
>+					    struct lock_list_head *entry)
>+{
>+	struct lock_list_head *next = entry->next;
>+	if (likely(next != list)) {
>+		lock_set_subclass(&entry->lock.dep_map,
>+				  LOCK_LIST_NESTING_CUR, _THIS_IP_);
>+		spin_lock_nested(&next->lock, LOCK_LIST_NESTING_NEXT);
>+		BUG_ON(entry->next != next);
>+	} else
>+		next = NULL;
>+	spin_unlock(&entry->lock);
>+	return next;
>+}
>+
>+struct lock_list_head *lock_list_first_entry(struct lock_list_head *list)
>+{
>+	spin_lock(&list->lock);
>+	return lock_list_next_entry(list, list);
>+}
>+
>Index: linux-2.6.21-rt-hack/kernel/lockdep.c
>===================================================================
>--- linux-2.6.21-rt-hack.orig/kernel/lockdep.c
>+++ linux-2.6.21-rt-hack/kernel/lockdep.c
>@@ -2561,6 +2561,9 @@ lock_set_subclass(struct lockdep_map *lo
> {
> 	unsigned long flags;
> 
>+	if (unlikely(!lock_stat && !prove_locking))
>+		return;
>+
> 	if (unlikely(current->lockdep_recursion))
> 		return;
> 
>Index: linux-2.6.21-rt-hack/include/linux/srcu.h
>===================================================================
>--- linux-2.6.21-rt-hack.orig/include/linux/srcu.h
>+++ linux-2.6.21-rt-hack/include/linux/srcu.h
>@@ -27,6 +27,8 @@
> #ifndef _LINUX_SRCU_H
> #define _LINUX_SRCU_H
> 
>+#include <linux/wait.h>
>+
> struct srcu_struct_array {
> 	int c[2];
> };
>@@ -50,4 +52,24 @@ void srcu_read_unlock(struct srcu_struct
> void synchronize_srcu(struct srcu_struct *sp);
> long srcu_batches_completed(struct srcu_struct *sp);
> 
>+/*
>+ * fully compatible with srcu, but optimized for writers.
>+ */
>+
>+struct qrcu_struct {
>+	int completed;
>+	atomic_t ctr[2];
>+	wait_queue_head_t wq;
>+	struct mutex mutex;
>+};
>+
>+int init_qrcu_struct(struct qrcu_struct *qp);
>+int qrcu_read_lock(struct qrcu_struct *qp);
>+void qrcu_read_unlock(struct qrcu_struct *qp, int idx);
>+void synchronize_qrcu(struct qrcu_struct *qp);
>+
>+static inline void cleanup_qrcu_struct(struct qrcu_struct *qp)
>+{
>+}
>+
> #endif
>Index: linux-2.6.21-rt-hack/kernel/srcu.c
>===================================================================
>--- linux-2.6.21-rt-hack.orig/kernel/srcu.c
>+++ linux-2.6.21-rt-hack/kernel/srcu.c
>@@ -256,3 +256,89 @@ EXPORT_SYMBOL_GPL(srcu_read_unlock);
> EXPORT_SYMBOL_GPL(synchronize_srcu);
> EXPORT_SYMBOL_GPL(srcu_batches_completed);
> EXPORT_SYMBOL_GPL(srcu_readers_active);
>+
>+int init_qrcu_struct(struct qrcu_struct *qp)
>+{
>+	qp->completed = 0;
>+	atomic_set(qp->ctr + 0, 1);
>+	atomic_set(qp->ctr + 1, 0);
>+	init_waitqueue_head(&qp->wq);
>+	mutex_init(&qp->mutex);
>+
>+	return 0;
>+}
>+
>+int qrcu_read_lock(struct qrcu_struct *qp)
>+{
>+	for (;;) {
>+		int idx = qp->completed & 0x1;
>+		if (likely(atomic_inc_not_zero(qp->ctr + idx)))
>+			return idx;
>+	}
>+}
>+
>+void qrcu_read_unlock(struct qrcu_struct *qp, int idx)
>+{
>+	if (atomic_dec_and_test(qp->ctr + idx))
>+		wake_up(&qp->wq);
>+}
>+
>+void synchronize_qrcu(struct qrcu_struct *qp)
>+{
>+	int idx;
>+
>+	smp_mb();  /* Force preceding change to happen before fastpath check. */
>+
>+	/*
>+	 * Fastpath: If the two counters sum to "1" at a given point in
>+	 * time, there are no readers.  However, it takes two separate
>+	 * loads to sample both counters, which won't occur simultaneously.
>+	 * So we might race with a counter switch, so that we might see
>+	 * ctr[0]==0, then the counter might switch, then we might see
>+	 * ctr[1]==1 (unbeknownst to us because there is a reader still
>+	 * there).  So we do a read memory barrier and recheck.  If the
>+	 * same race happens again, there must have been a second counter
>+	 * switch.  This second counter switch could not have happened
>+	 * until all preceding readers finished, so if the condition
>+	 * is true both times, we may safely proceed.
>+	 *
>+	 * This relies critically on the atomic increment and atomic
>+	 * decrement being seen as executing in order.
>+	 */
>+
>+	if (atomic_read(&qp->ctr[0]) + atomic_read(&qp->ctr[1]) <= 1) {
>+		smp_rmb();  /* Keep two checks independent. */
>+		if (atomic_read(&qp->ctr[0]) + atomic_read(&qp->ctr[1]) <= 1)
>+			goto out;
>+	}
>+
>+	mutex_lock(&qp->mutex);
>+
>+	idx = qp->completed & 0x1;
>+	if (atomic_read(qp->ctr + idx) == 1)
>+		goto out_unlock;
>+
>+	atomic_inc(qp->ctr + (idx ^ 0x1));
>+
>+	/*
>+	 * Prevent subsequent decrement from being seen before previous
>+	 * increment -- such an inversion could cause the fastpath
>+	 * above to falsely conclude that there were no readers.  Also,
>+	 * reduce the likelihood that qrcu_read_lock() will loop.
>+	 */
>+
>+	smp_mb__after_atomic_inc();
>+	qp->completed++;
>+
>+	atomic_dec(qp->ctr + idx);
>+	__wait_event(qp->wq, !atomic_read(qp->ctr + idx));
>+out_unlock:
>+	mutex_unlock(&qp->mutex);
>+out:
>+	smp_mb(); /* force subsequent free after qrcu_read_unlock(). */
>+}
>+
>+EXPORT_SYMBOL_GPL(init_qrcu_struct);
>+EXPORT_SYMBOL_GPL(qrcu_read_lock);
>+EXPORT_SYMBOL_GPL(qrcu_read_unlock);
>+EXPORT_SYMBOL_GPL(synchronize_qrcu);
>Index: linux-2.6.21-rt-hack/include/linux/percpu_list.h
>===================================================================
>--- /dev/null
>+++ linux-2.6.21-rt-hack/include/linux/percpu_list.h
>@@ -0,0 +1,119 @@
>+#ifndef _LINUX_PERCPU_LIST_H
>+#define _LINUX_PERCPU_LIST_H
>+
>+#include <linux/lock_list.h>
>+#include <linux/percpu.h>
>+
>+#ifdef CONFIG_SMP
>+
>+struct percpu_list_element {
>+	spinlock_t lock;
>+	unsigned long nr;
>+	struct lock_list_head list;
>+};
>+
>+struct percpu_list {
>+	struct lock_list_head list;
>+	struct percpu_list_element *percpu_list;
>+};
>+
>+static inline
>+void percpu_list_init(struct percpu_list *pcl)
>+{
>+	int cpu;
>+
>+	INIT_LOCK_LIST_HEAD(&pcl->list);
>+	pcl->percpu_list = alloc_percpu(struct percpu_list_element);
>+
>+	for_each_possible_cpu(cpu) {
>+		struct percpu_list_element *pcle;
>+
>+		pcle = per_cpu_ptr(pcl->percpu_list, cpu);
>+		spin_lock_init(&pcle->lock);
>+		pcle->nr = 0;
>+		INIT_LOCK_LIST_HEAD(&pcle->list);
>+	}
>+}
>+
>+static inline
>+void percpu_list_destroy(struct percpu_list *pcl)
>+{
>+	free_percpu(pcl->percpu_list);
>+}
>+
>+static inline
>+void percpu_list_fold_cpu(struct percpu_list *pcl, int cpu)
>+{
>+	struct percpu_list_element *pcle = per_cpu_ptr(pcl->percpu_list, cpu);
>+
>+	spin_lock(&pcle->lock);
>+	if (pcle->nr) {
>+		pcle->nr = 0;
>+		lock_list_splice_init(&pcle->list, &pcl->list);
>+	}
>+	spin_unlock(&pcle->lock);
>+}
>+
>+static inline
>+void percpu_list_add(struct percpu_list *pcl, struct lock_list_head *elm)
>+{
>+	struct percpu_list_element *pcle;
>+	int cpu = raw_smp_processor_id();
>+	unsigned long nr;
>+
>+	pcle = per_cpu_ptr(pcl->percpu_list, cpu);
>+	spin_lock(&pcle->lock);
>+	nr = ++pcle->nr;
>+	lock_list_add(elm, &pcle->list);
>+	spin_unlock(&pcle->lock);
>+
>+	if (nr >= 16)
>+		percpu_list_fold_cpu(pcl, cpu);
>+}
>+
>+static inline
>+void percpu_list_fold(struct percpu_list *pcl)
>+{
>+	int cpu;
>+
>+	for_each_possible_cpu(cpu)
>+		percpu_list_fold_cpu(pcl, cpu);
>+}
>+
>+#else /* CONFIG_SMP */
>+
>+struct percpu_list {
>+	struct lock_list_head list;
>+}
>+
>+static inline
>+void percpu_list_init(struct percpu_list *pcl)
>+{
>+	INIT_LOCK_LIST_HEAD(&pcl->list);
>+}
>+
>+static inline
>+void percpu_list_destroy(struct percpu_list *pcl)
>+{
>+}
>+
>+static inline
>+void percpu_list_add(struct percpu_list *pcl, struct lock_list_head *elm)
>+{
>+	lock_list_add(elm, &pcl->list);
>+}
>+
>+static inline
>+void percpu_list_fold(struct percpu_list *pcl)
>+{
>+}
>+
>+#endif
>+
>+static inline
>+struct lock_list_head *percpu_list_head(struct percpu_list *pcl)
>+{
>+	return &pcl->list;
>+}
>+
>+#endif /* _LINUX_PERCPU_LIST_H */
>Index: linux-2.6.21-rt-hack/drivers/char/tty_io.c
>===================================================================
>--- linux-2.6.21-rt-hack.orig/drivers/char/tty_io.c
>+++ linux-2.6.21-rt-hack/drivers/char/tty_io.c
>@@ -237,14 +237,13 @@ int tty_paranoia_check(struct tty_struct
> static int check_tty_count(struct tty_struct *tty, const char *routine)
> {
> #ifdef CHECK_TTY_COUNT
>-	struct list_head *p;
>+	struct file *filp;
> 	int count = 0;
>-	
>-	file_list_lock();
>-	list_for_each(p, &tty->tty_files) {
>+
>+	percpu_list_fold(&tty->tty_files);
>+	lock_list_for_each_entry(filp, percpu_list_head(&tty->tty_files), f_u.fu_llist)
> 		count++;
>-	}
>-	file_list_unlock();
>+
> 	if (tty->driver->type == TTY_DRIVER_TYPE_PTY &&
> 	    tty->driver->subtype == PTY_TYPE_SLAVE &&
> 	    tty->link && tty->link->count)
>@@ -1308,9 +1307,8 @@ static void do_tty_hangup(struct work_st
> 	spin_unlock(&redirect_lock);
> 	
> 	check_tty_count(tty, "do_tty_hangup");
>-	file_list_lock();
> 	/* This breaks for file handles being sent over AF_UNIX sockets ? */
>-	list_for_each_entry(filp, &tty->tty_files, f_u.fu_list) {
>+	lock_list_for_each_entry(filp, percpu_list_head(&tty->tty_files), f_u.fu_llist) {
> 		if (filp->f_op->write == redirected_tty_write)
> 			cons_filp = filp;
> 		if (filp->f_op->write != tty_write)
>@@ -1319,7 +1317,6 @@ static void do_tty_hangup(struct work_st
> 		tty_fasync(-1, filp, 0);	/* can't block */
> 		filp->f_op = &hung_up_tty_fops;
> 	}
>-	file_list_unlock();
> 	
> 	/* FIXME! What are the locking issues here? This may me overdoing things..
> 	 * this question is especially important now that we've removed the irqlock. */
>@@ -2169,9 +2166,9 @@ static void release_one_tty(struct tty_s
> 	tty->magic = 0;
> 	tty->driver->refcount--;
> 
>-	file_list_lock();
>-	list_del_init(&tty->tty_files);
>-	file_list_unlock();
>+	percpu_list_fold(&tty->tty_files);
>+	lock_list_del_init(percpu_list_head(&tty->tty_files));
>+	percpu_list_destroy(&tty->tty_files);
> 
> 	free_tty_struct(tty);
> }
>@@ -3588,7 +3585,7 @@ static void initialize_tty_struct(struct
> 	mutex_init(&tty->atomic_read_lock);
> 	mutex_init(&tty->atomic_write_lock);
> 	spin_lock_init(&tty->read_lock);
>-	INIT_LIST_HEAD(&tty->tty_files);
>+	percpu_list_init(&tty->tty_files);
> 	INIT_WORK(&tty->SAK_work, do_SAK_work);
> }
> 
>Index: linux-2.6.21-rt-hack/include/linux/tty.h
>===================================================================
>--- linux-2.6.21-rt-hack.orig/include/linux/tty.h
>+++ linux-2.6.21-rt-hack/include/linux/tty.h
>@@ -216,7 +216,7 @@ struct tty_struct {
> 	struct work_struct hangup_work;
> 	void *disc_data;
> 	void *driver_data;
>-	struct list_head tty_files;
>+	struct percpu_list tty_files;
> 
> #define N_TTY_BUF_SIZE 4096
> 	
>Index: linux-2.6.21-rt-hack/security/selinux/hooks.c
>===================================================================
>--- linux-2.6.21-rt-hack.orig/security/selinux/hooks.c
>+++ linux-2.6.21-rt-hack/security/selinux/hooks.c
>@@ -1743,8 +1743,11 @@ static inline void flush_unauthorized_fi
> 	mutex_lock(&tty_mutex);
> 	tty = get_current_tty();
> 	if (tty) {
>-		file_list_lock();
>-		file = list_entry(tty->tty_files.next, typeof(*file), f_u.fu_list);
>+		lock_list_for_each_entry(file,
>+				percpu_list_head(&tty->tty_files),
>+				f_u.fu_llist)
>+			break;
>+
> 		if (file) {
> 			/* Revalidate access to controlling tty.
> 			   Use inode_has_perm on the tty inode directly rather
>@@ -1756,8 +1759,8 @@ static inline void flush_unauthorized_fi
> 					   FILE__READ | FILE__WRITE, NULL)) {
> 				drop_tty = 1;
> 			}
>+			lock_list_for_each_entry_stop(file, f_u.fu_llist);
> 		}
>-		file_list_unlock();
> 
> 		/* Reset controlling tty. */
> 		if (drop_tty)

Actions: View | Diff

Attachments on bug 245338: 158902 | 159057 | 159599 | 206091