queueing spinlocks?
Subsystems (17)
RFC PATCH 1/1 queueing spinlocks?
I've implemented a sort of spin local, queueing MCS lock that uses per-cpu nodes that can be shared by multiple locks. I guess it is preferable to remove global locks, but some don't seem to be going anywhere soon.
The only issue is that only one set of nodes can be actively used for a lock at once, so if we want to nest these locks, we have to use different sets for each one. This shouldn't be much of a problem because we don't have too many "big" locks, and yet fewer ones that are nested in one another.
With this modification to MCS locks, each lock is pretty small in size, so it could even be used for some per-object locks if we really wanted.
I've converted dcache lock as well... it shows improved results on a 64-way Altix. Unfortunately this adds an extra atomic to the unlock path. I didn't look too hard at array based queue locks, there might be a a type of those that would work better.
include/linux/mcslock.h new file +76 -0
@@ -0,0 +1,76 @@ +/* +* "Shared-node" MCS lock. +* Nick Piggin <[email protected]> +*/ +#ifndef _LINUX_MCSLOCK_H +#define _LINUX_MCSLOCK_H + +#include <linux/types.h> +#include <linux/kernel.h> +#include <linux/irqflags.h> +#include <asm/atomic.h> +#include <asm/system.h> +#include <asm/processor.h> + +#ifndef CONFIG_SMP +typdef struct { +} mcslock_t; + +static inline void mcs_lock_init (mcslock_t *lock) +{ +} + +static inline int mcs_is_locked (mcslock_t *lock) +{ +return 0 ; +} + +static inline void mcs_unlock_wait (mcslock_t *lock) +{ +} + +static inline void mcs_lock (mcslock_t *lock,int nest) +{ +} +static inline int mcs_trylock (mcslock_t *lock,int nest) +{ +return 1 ; +} +static inline void mcs_unlock (mcslock_t *lock,int nest) +{ +} + +#else /*!CONFIG_SMP*/ + +typedef struct { +atomic_t cpu; +}mcslock_t ; + +#define MCS_CPU_NONE 0x7fffffff + +#define DEFINE_MCS_LOCK (name) mcslock_t name = { .cpu = ATOMIC_INIT(MCS_CPU_NONE) } +static inline void mcs_lock_init (mcslock_t *lock) +{ +atomic_set (&lock->cpu,MCS_CPU_NONE );/* unlocked */ +} + +static inline int mcs_is_locked (mcslock_t *lock) +{ +return atomic_read (&lock->cpu) !=MCS_CPU_NONE ; +} + +static inline void mcs_unlock_wait (mcslock_t *lock) +{ +while (mcs_is_locked (lock)) +cpu_relax (); +} + +extern void mcs_lock (mcslock_t *lock,int nest); +extern int mcs_trylock (mcslock_t *lock,int nest); +extern void mcs_unlock (mcslock_t *lock,int nest); + +#endif /*!CONFIG_SMP*/ + +extern int atomic_dec_and_mcslock (atomic_t *atomic,mcslock_t *lock,int nest); + +#endif
lib/Makefile +2 -1
@@ -19,7 +19,8 @@ lib-$(CONFIG_SMP) += cpumask.o lib-y += kobject.o kref.o klist.o obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \ - bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o + bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \ + mcslock.o ifeq ($(CONFIG_DEBUG_KOBJECT),y) CFLAGS_kobject.o += -DDEBUG
lib/mcslock.c new file +72 -0
72 lines not on this page · raw message
fs/dcache.c +77 -76
544 lines not on this page · raw message
include/linux/dcache.h +4 -3
@@ -7,6 +7,7 @@#include <linux/spinlock.h> #include <linux/cache.h> #include <linux/rcupdate.h> +#include <linux/mcslock.h> struct nameidata ;struct path ;
@@ -177,7 +178,7 @@ d_iput: no no no yes#define DCACHE_INOTIFY_PARENT_WATCHED 0x0020/* Parent inode is watched */ -extern spinlock_t dcache_lock; +extern mcslock_t dcache_lock;extern seqlock_t rename_lock;/**
@@ -206,11 +207,11 @@ static inline void __d_drop(struct dentrstatic inline void d_drop (struct dentry *dentry) { -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );spin_lock (&dentry->d_lock);__d_drop (dentry);spin_unlock (&dentry->d_lock); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 ); }static inline int dname_external (struct dentry *dentry)
fs/configfs/configfs_internal.h +2 -2
@@ -117,7 +117,7 @@ static inline struct config_item *config {struct config_item * item =NULL ; -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );if (!d_unhashed (dentry)) {struct configfs_dirent * sd = dentry->d_fsdata;if (sd->s_type &CONFIGFS_ITEM_LINK ) {
@@ -126,7 +126,7 @@ static inline struct config_item *config }else item =config_item_get (sd->s_element); } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );return item; }
fs/configfs/inode.c +3 -3
@@ -218,17 +218,17 @@ void configfs_drop_dentry(struct configfstruct dentry * dentry = sd->s_dentry;if (dentry) { -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );spin_lock (&dentry->d_lock);if (!(d_unhashed (dentry) && dentry->d_inode)) {dget_locked (dentry);__d_drop (dentry);spin_unlock (&dentry->d_lock); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );simple_unlink (parent->d_inode, dentry); }else {spin_unlock (&dentry->d_lock); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 ); } } }
fs/inotify.c +2 -2
@@ -163,7 +163,7 @@ static void set_dentry_child_flags(struc {struct dentry *alias; -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );list_for_each_entry (alias, &inode->i_dentry, d_alias) {struct dentry *child;
@@ -179,7 +179,7 @@ static void set_dentry_child_flags(strucspin_unlock (&child->d_lock); } } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 ); }/*
fs/libfs.c +8 -8
@@ -95,7 +95,7 @@ loff_t dcache_dir_lseek(struct file *filstruct dentry *cursor = file->private_data;loff_t n = file->f_pos -2 ; -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );list_del (&cursor->d_u.d_child); p = file->f_path.dentry->d_subdirs.next;while (n && p != &file->f_path.dentry->d_subdirs) {
@@ -106,7 +106,7 @@ loff_t dcache_dir_lseek(struct file *fil p = p->next; }list_add_tail (&cursor->d_u.d_child, p); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 ); } }mutex_unlock (&file->f_path.dentry->d_inode->i_mutex);
@@ -149,7 +149,7 @@ int dcache_readdir(struct file * filp, v i++;/* fallthrough */ default : -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );if (filp->f_pos ==2 )list_move (q, &dentry->d_subdirs);
@@ -159,19 +159,19 @@ int dcache_readdir(struct file * filp, vif (d_unhashed (next) || !next->d_inode)continue ; -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );if (filldir (dirent, next->d_name.name, next->d_name.len, filp->f_pos, next->d_inode->i_ino,dt_type (next->d_inode)) <0 )return 0 ; -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );/* next is still alive */ list_move (q, p); p = q; filp->f_pos++; } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 ); }return 0 ; }
@@ -273,13 +273,13 @@ int simple_empty(struct dentry *dentry)struct dentry *child;int ret =0 ; -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );list_for_each_entry (child, &dentry->d_subdirs, d_u.d_child)if (simple_positive (child)) goto out; ret =1 ; out: -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );return ret; }
fs/namei.c +5 -5
@@ -776,14 +776,14 @@ static __always_inline void follow_dotdobreak ; }read_unlock (&fs->lock); -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );if (nd->path.dentry != nd->path.mnt->mnt_root) { nd->path.dentry =dget (nd->path.dentry->d_parent); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );dput (old);break ; } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );spin_lock (&vfsmount_lock); parent = nd->path.mnt->mnt_parent;if (parent == nd->path.mnt) {
@@ -2125,12 +2125,12 @@ void dentry_unhash(struct dentry *dentry {dget (dentry);shrink_dcache_parent (dentry); -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );spin_lock (&dentry->d_lock);if (atomic_read (&dentry->d_count) ==2 )__d_drop (dentry);spin_unlock (&dentry->d_lock); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 ); }int vfs_rmdir (struct inode *dir,struct dentry *dentry)
fs/seq_file.c +2 -2
@@ -412,9 +412,9 @@ int seq_path_root(struct seq_file *m, stchar *s = m->buf + m->count;char *p; -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 ); p =__d_path (path, root, s, m->size - m->count); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 ); err =PTR_ERR (p);if (!IS_ERR (p)) { s =mangle_path (s, p, esc);
fs/sysfs/dir.c +3 -3
@@ -520,7 +520,7 @@ static void sysfs_drop_dentry(struct sys* dput to immediately free the dentry if it is not in use. */ repeat: -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );list_for_each_entry (dentry, &inode->i_dentry, d_alias) {if (d_unhashed (dentry))continue ;
@@ -528,11 +528,11 @@ repeat:spin_lock (&dentry->d_lock);__d_drop (dentry);spin_unlock (&dentry->d_lock); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );dput (dentry); goto repeat; } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );/* adjust nlink and update timestamp */ mutex_lock (&inode->i_mutex);
lib/dec_and_lock.c +17 -1
@@ -1,5 +1,6 @@#include <linux/module.h> #include <linux/spinlock.h> +#include <linux/mcslock.h> #include <asm/atomic.h> /*
@@ -31,5 +32,20 @@ int _atomic_dec_and_lock(atomic_t *atomispin_unlock (lock);return 0 ; } -EXPORT_SYMBOL (_atomic_dec_and_lock); + +int atomic_dec_and_mcslock (atomic_t *atomic,mcslock_t *lock,int nest) +{ +#ifdef CONFIG_SMP +/* Subtract 1 from counter unless that drops it to 0 (ie. it was 1) */ +if (atomic_add_unless (atomic,-1 ,1 )) +return 0 ; +#endif +/* Otherwise do it the slow way */ +mcs_lock (lock, nest); +if (atomic_dec_and_test (atomic)) +return 1 ; +mcs_unlock (lock, nest); +return 0 ; +} +EXPORT_SYMBOL (atomic_dec_and_mcslock);
arch/powerpc/platforms/cell/spufs/inode.c +3 -3
@@ -159,18 +159,18 @@ static void spufs_prune_dir(struct dentrmutex_lock (&dir->d_inode->i_mutex);list_for_each_entry_safe (dentry, tmp, &dir->d_subdirs, d_u.d_child) { -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );spin_lock (&dentry->d_lock);if (!(d_unhashed (dentry)) && dentry->d_inode) {dget_locked (dentry);__d_drop (dentry);spin_unlock (&dentry->d_lock);simple_unlink (dir->d_inode, dentry); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );dput (dentry); }else {spin_unlock (&dentry->d_lock); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 ); } }shrink_dcache_parent (dir);
drivers/infiniband/hw/ipath/ipath_fs.c +3 -3
@@ -275,17 +275,17 @@ static int remove_file(struct dentry *pa goto bail; } -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );spin_lock (&tmp->d_lock);if (!(d_unhashed (tmp) && tmp->d_inode)) {dget_locked (tmp);__d_drop (tmp);spin_unlock (&tmp->d_lock); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );simple_unlink (parent->d_inode, tmp); }else {spin_unlock (&tmp->d_lock); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 ); } ret =0 ;
drivers/usb/core/inode.c +3 -3
@@ -342,17 +342,17 @@ static int usbfs_empty (struct dentry *d {struct list_head *list; -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );list_for_each (list, &dentry->d_subdirs) { struct dentry *de = list_entry(list, struct dentry, d_u.d_child);if (usbfs_positive (de)) { -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );return 0 ; } } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );return 1 ; }
fs/affs/amigaffs.c +2 -2
@@ -128,7 +128,7 @@ affs_fix_dcache(struct dentry *dentry, uvoid *data = dentry->d_fsdata;struct list_head *head, *next; -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 ); head = &inode->i_dentry; next = head->next;while (next != head) {
@@ -139,7 +139,7 @@ affs_fix_dcache(struct dentry *dentry, u } next = next->next; } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 ); }
fs/autofs4/expire.c +14 -14
@@ -146,7 +146,7 @@ static int autofs4_tree_busy(struct vfsmif (!simple_positive (top))return 1 ; -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );for (p = top; p; p =next_dentry (p, top)) {/* Negative dentry - give up */ if (!simple_positive (p))
@@ -156,7 +156,7 @@ static int autofs4_tree_busy(struct vfsm p, (int) p->d_name.len, p->d_name.name); p =dget (p); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );/* * Is someone visiting anywhere in the subtree ?
@@ -193,9 +193,9 @@ static int autofs4_tree_busy(struct vfsm } }dput (p); -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 ); } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );/* Timeout of a tree mount is ultimately determined by its top dentry */ if (!autofs4_can_expire (top, timeout, do_now))
@@ -214,7 +214,7 @@ static struct dentry *autofs4_check_leavDPRINTK ("parent %p %.*s" , parent, (int )parent->d_name.len, parent->d_name.name); -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );for (p = parent; p; p =next_dentry (p, parent)) {/* Negative dentry - give up */ if (!simple_positive (p))
@@ -224,7 +224,7 @@ static struct dentry *autofs4_check_leav p, (int) p->d_name.len, p->d_name.name); p =dget (p); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );if (d_mountpoint (p)) {/* Can we umount this guy */
@@ -237,9 +237,9 @@ static struct dentry *autofs4_check_leav } cont:dput (p); -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 ); } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );return NULL ; }
@@ -303,7 +303,7 @@ static struct dentry *autofs4_expire_ind now = jiffies; timeout = sbi->exp_timeout; -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 ); next = root->d_subdirs.next;/* On exit from the loop expire is set to a dgot dentry
@@ -318,7 +318,7 @@ static struct dentry *autofs4_expire_ind } dentry =dget (dentry); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );spin_lock (&sbi->fs_lock); ino =autofs4_dentry_ino (dentry);
@@ -383,10 +383,10 @@ static struct dentry *autofs4_expire_ind next:spin_unlock (&sbi->fs_lock);dput (dentry); -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 ); next = next->next; } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );return NULL ; found:
@@ -396,9 +396,9 @@ found: ino->flags |=AUTOFS_INF_EXPIRING ;init_completion (&ino->expire_complete);spin_unlock (&sbi->fs_lock); -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );list_move (&expired->d_parent->d_subdirs, &expired->d_u.d_child); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );return expired; }
fs/autofs4/inode.c +6 -6
@@ -107,7 +107,7 @@ static void autofs4_force_release(structif (!sbi->sb->s_root)return ; -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 ); repeat: next = this_parent->d_subdirs.next; resume:
@@ -126,13 +126,13 @@ resume: } next = next->next; -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );DPRINTK ("dentry %p %.*s" , dentry, (int )dentry->d_name.len, dentry->d_name.name);dput (dentry); -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 ); }if (this_parent != sbi->sb->s_root) {
@@ -140,14 +140,14 @@ resume: next = this_parent->d_u.d_child.next; this_parent = this_parent->d_parent; -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );DPRINTK ("parent dentry %p %.*s" , dentry, (int )dentry->d_name.len, dentry->d_name.name);dput (dentry); -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 ); goto resume; } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 ); }void autofs4_kill_sb (struct super_block *sb)
fs/autofs4/root.c +20 -20
@@ -92,12 +92,12 @@ static int autofs4_dir_open(struct inode* autofs file system so just let the libfs routines handle * it. */ -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );if (!d_mountpoint (dentry) &&__simple_empty (dentry)) { -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );return -ENOENT ; } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 ); out:return dcache_dir_open (inode, file);
@@ -211,10 +211,10 @@ static void *autofs4_follow_link(struct* multi-mount with no root mount offset. So don't try to * mount it again. */ -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );if (dentry->d_flags &DCACHE_AUTOFS_PENDING || (!d_mountpoint (dentry) &&__simple_empty (dentry))) { -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 ); status =try_to_fill_dentry (dentry,0 );if (status)
@@ -222,7 +222,7 @@ static void *autofs4_follow_link(struct goto follow; } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 ); follow:/* * If there is no root mount it must be an autofs
@@ -293,13 +293,13 @@ static int autofs4_revalidate(struct denreturn 0 ;/* Check for a non-mountpoint directory with no contents */ -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );if (S_ISDIR (dentry->d_inode->i_mode) && !d_mountpoint (dentry) &&__simple_empty (dentry)) {DPRINTK ("dentry=%p %.*s, emptydir" , dentry, dentry->d_name.len, dentry->d_name.name); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );/* The daemon never causes a mount to trigger */ if (oz_mode)
@@ -315,7 +315,7 @@ static int autofs4_revalidate(struct denreturn status; } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );return 1 ; }
@@ -367,7 +367,7 @@ static struct dentry *autofs4_lookup_actconst unsigned char *str = name->name;struct list_head *p, *head; -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );spin_lock (&sbi->lookup_lock); head = &sbi->active_list;list_for_each (p, head) {
@@ -400,14 +400,14 @@ static struct dentry *autofs4_lookup_actdget (dentry);spin_unlock (&dentry->d_lock);spin_unlock (&sbi->lookup_lock); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );return dentry; } next:spin_unlock (&dentry->d_lock); }spin_unlock (&sbi->lookup_lock); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );return NULL ; }
@@ -419,7 +419,7 @@ static struct dentry *autofs4_lookup_expconst unsigned char *str = name->name;struct list_head *p, *head; -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );spin_lock (&sbi->lookup_lock); head = &sbi->expiring_list;list_for_each (p, head) {
@@ -452,14 +452,14 @@ static struct dentry *autofs4_lookup_expdget (dentry);spin_unlock (&dentry->d_lock);spin_unlock (&sbi->lookup_lock); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );return dentry; } next:spin_unlock (&dentry->d_lock); }spin_unlock (&sbi->lookup_lock); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );return NULL ; }
@@ -704,7 +704,7 @@ static int autofs4_dir_unlink(struct ino dir->i_mtime =CURRENT_TIME ; -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );spin_lock (&sbi->lookup_lock);if (list_empty (&ino->expiring))list_add (&ino->expiring, &sbi->expiring_list);
@@ -712,7 +712,7 @@ static int autofs4_dir_unlink(struct inospin_lock (&dentry->d_lock);__d_drop (dentry);spin_unlock (&dentry->d_lock); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );return 0 ; }
@@ -729,9 +729,9 @@ static int autofs4_dir_rmdir(struct inodif (!autofs4_oz_mode (sbi))return -EACCES ; -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );if (!list_empty (&dentry->d_subdirs)) { -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );return -ENOTEMPTY ; }spin_lock (&sbi->lookup_lock);
@@ -741,7 +741,7 @@ static int autofs4_dir_rmdir(struct inodspin_lock (&dentry->d_lock);__d_drop (dentry);spin_unlock (&dentry->d_lock); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );if (atomic_dec_and_test (&ino->count)) { p_ino =autofs4_dentry_ino (dentry->d_parent);
fs/autofs4/waitq.c +3 -3
@@ -190,12 +190,12 @@ static int autofs4_getpath(struct autofschar *p;int len =0 ; -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );for (tmp = dentry ; tmp != root ; tmp = tmp->d_parent) len += tmp->d_name.len +1 ;if (!len || --len >NAME_MAX ) { -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );return 0 ; }
@@ -208,7 +208,7 @@ static int autofs4_getpath(struct autofs p -= tmp->d_name.len;strncpy (p, tmp->d_name.name, tmp->d_name.len); } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );return len; }
fs/coda/cache.c +2 -2
@@ -86,7 +86,7 @@ static void coda_flag_children(struct destruct list_head *child;struct dentry *de; -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );list_for_each (child, &parent->d_subdirs) { de = list_entry(child, struct dentry, d_u.d_child);
@@ -95,7 +95,7 @@ static void coda_flag_children(struct decontinue ;coda_flag_inode (de->d_inode, flag); } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );return ; }
fs/exportfs/expfs.c +4 -4
@@ -46,20 +46,20 @@ find_acceptable_alias(struct dentry *resif (acceptable (context, result))return result; -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );list_for_each_entry (dentry, &result->d_inode->i_dentry, d_alias) {dget_locked (dentry); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );if (toput)dput (toput);if (dentry != result &&acceptable (context, dentry)) {dput (result);return dentry; } -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 ); toput = dentry; } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );if (toput)dput (toput);
fs/ncpfs/dir.c +3 -3
@@ -364,7 +364,7 @@ ncp_dget_fpos(struct dentry *dentry, str }/* If a pointer is invalid, we search the dentry. */ -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 ); next = parent->d_subdirs.next;while (next != &parent->d_subdirs) { dent = list_entry(next, struct dentry, d_u.d_child);
@@ -373,12 +373,12 @@ ncp_dget_fpos(struct dentry *dentry, strdget_locked (dent); else dent =NULL ; -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 ); goto out; } next = next->next; } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );return NULL ; out:
fs/ncpfs/ncplib_kernel.h +4 -4
@@ -192,7 +192,7 @@ ncp_renew_dentries(struct dentry *parentstruct list_head *next;struct dentry *dentry; -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 ); next = parent->d_subdirs.next;while (next != &parent->d_subdirs) { dentry = list_entry(next, struct dentry, d_u.d_child);
@@ -204,7 +204,7 @@ ncp_renew_dentries(struct dentry *parent next = next->next; } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 ); } static inline void
@@ -214,7 +214,7 @@ ncp_invalidate_dircache_entries(struct dstruct list_head *next;struct dentry *dentry; -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 ); next = parent->d_subdirs.next;while (next != &parent->d_subdirs) { dentry = list_entry(next, struct dentry, d_u.d_child);
@@ -222,7 +222,7 @@ ncp_invalidate_dircache_entries(struct dncp_age_dentry (server, dentry); next = next->next; } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 ); }struct ncp_cache_head {
fs/nfs/dir.c +3 -3
@@ -1422,11 +1422,11 @@ static int nfs_unlink(struct inode *dir,dfprintk (VFS ,"NFS: unlink(%s/%ld, %s)\n" , dir->i_sb->s_id, dir->i_ino, dentry->d_name.name); -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );spin_lock (&dentry->d_lock);if (atomic_read (&dentry->d_count) >1 ) {spin_unlock (&dentry->d_lock); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );/* Start asynchronous writeout of the inode */ write_inode_now (dentry->d_inode,0 ); error =nfs_sillyrename (dir, dentry);
@@ -1437,7 +1437,7 @@ static int nfs_unlink(struct inode *dir, need_rehash =1 ; }spin_unlock (&dentry->d_lock); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 ); error =nfs_safe_remove (dentry);if (!error || error == -ENOENT ) {nfs_set_verifier (dentry,nfs_save_change_attribute (dir));
fs/nfs/getroot.c +2 -2
@@ -65,9 +65,9 @@ static int nfs_superblock_set_dummy_root* This again causes shrink_dcache_for_umount_subtree() to * Oops, since the test for IS_ROOT() will fail. */ -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );list_del_init (&sb->s_root->d_alias); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 ); }return 0 ; }
fs/nfs/namespace.c +3 -3
@@ -53,7 +53,7 @@ char *nfs_path(const char *base, *--end ='\0' ; buflen--; -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );while (!IS_ROOT (dentry) && dentry != droot) { namelen = dentry->d_name.len; buflen -= namelen +1 ;
@@ -64,7 +64,7 @@ char *nfs_path(const char *base, *--end ='/' ; dentry = dentry->d_parent; } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 ); namelen =strlen (base);/* Strip off excess slashes in base string */ while (namelen >0 && base[namelen -1 ] =='/' )
@@ -76,7 +76,7 @@ char *nfs_path(const char *base,memcpy (end, base, namelen);return end; Elong_unlock: -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 ); Elong:return ERR_PTR (-ENAMETOOLONG ); }
fs/ocfs2/dcache.c +2 -2
@@ -139,7 +139,7 @@ struct dentry *ocfs2_find_local_alias(ststruct list_head *p;struct dentry *dentry =NULL ; -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );list_for_each (p, &inode->i_dentry) { dentry = list_entry(p, struct dentry, d_alias);
@@ -155,7 +155,7 @@ struct dentry *ocfs2_find_local_alias(st dentry =NULL ; } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );return dentry; }
fs/smbfs/cache.c +4 -4
@@ -62,7 +62,7 @@ smb_invalidate_dircache_entries(struct dstruct list_head *next;struct dentry *dentry; -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 ); next = parent->d_subdirs.next;while (next != &parent->d_subdirs) { dentry = list_entry(next, struct dentry, d_u.d_child);
@@ -70,7 +70,7 @@ smb_invalidate_dircache_entries(struct dsmb_age_dentry (server, dentry); next = next->next; } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 ); }/*
@@ -96,7 +96,7 @@ smb_dget_fpos(struct dentry *dentry, str }/* If a pointer is invalid, we search the dentry. */ -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 ); next = parent->d_subdirs.next;while (next != &parent->d_subdirs) { dent = list_entry(next, struct dentry, d_u.d_child);
@@ -111,7 +111,7 @@ smb_dget_fpos(struct dentry *dentry, str } dent =NULL ; out_unlock: -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );return dent; }
kernel/cgroup.c +6 -6
@@ -645,7 +645,7 @@ static void cgroup_clear_directory(strucstruct list_head *node;BUG_ON (!mutex_is_locked (&dentry->d_inode->i_mutex)); -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 ); node = dentry->d_subdirs.next;while (node != &dentry->d_subdirs) { struct dentry *d = list_entry(node, struct dentry, d_u.d_child);
@@ -655,15 +655,15 @@ static void cgroup_clear_directory(struc* directory with child cgroups */ BUG_ON (d->d_inode->i_mode &S_IFDIR ); d =dget_locked (d); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );d_delete (d);simple_unlink (dentry->d_inode, d);dput (d); -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 ); } node = dentry->d_subdirs.next; } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 ); }/*
@@ -673,9 +673,9 @@ static void cgroup_d_remove_dir(struct d {cgroup_clear_directory (dentry); -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );list_del_init (&dentry->d_u.d_child); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );remove_dir (dentry); }
net/sunrpc/rpc_pipe.c +2 -2
@@ -533,7 +533,7 @@ static void rpc_depopulate(struct dentrymutex_lock_nested (&dir->i_mutex,I_MUTEX_CHILD ); repeat: -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 );list_for_each_safe (pos, next, &parent->d_subdirs) { dentry = list_entry(pos, struct dentry, d_u.d_child); if (!dentry->d_inode ||
@@ -551,7 +551,7 @@ repeat: }else spin_unlock (&dentry->d_lock); } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );if (n) { do { dentry = dvec[--n];
security/selinux/selinuxfs.c +4 -4
@@ -1011,7 +1011,7 @@ static void sel_remove_entries(struct de {struct list_head *node; -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 ); node = de->d_subdirs.next;while (node != &de->d_subdirs) { struct dentry *d = list_entry(node, struct dentry, d_u.d_child);
@@ -1019,16 +1019,16 @@ static void sel_remove_entries(struct deif (d->d_inode) { d =dget_locked (d); -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 );d_delete (d);simple_unlink (de->d_inode, d);dput (d); -spin_lock (&dcache_lock); +mcs_lock (&dcache_lock,0 ); } node = de->d_subdirs.next; } -spin_unlock (&dcache_lock); +mcs_unlock (&dcache_lock,0 ); }#define BOOL_DIR_NAME "booleans"
Hi Nick,
Cool stuff...see inline
Quoted 87 lines · Nick Piggin
I've implemented a sort of spin local, queueing MCS lock that uses per-cpu nodes that can be shared by multiple locks. I guess it is preferable to remove global locks, but some don't seem to be going anywhere soon.
The only issue is that only one set of nodes can be actively used for a lock at once, so if we want to nest these locks, we have to use different sets for each one. This shouldn't be much of a problem because we don't have too many "big" locks, and yet fewer ones that are nested in one another.
With this modification to MCS locks, each lock is pretty small in size, so it could even be used for some per-object locks if we really wanted.
I've converted dcache lock as well... it shows improved results on a 64-way Altix. Unfortunately this adds an extra atomic to the unlock path. I didn't look too hard at array based queue locks, there might be a a type of those that would work better.
Index:
linux-2.6/include/linux/mcslock.h
===================================================================include/linux/mcslock.h new file +64
-0@@ -0,0 +1,76 @@ +/* +* "Shared-node" MCS lock. +* Nick Piggin <[email protected]> +*/ +#ifndef _LINUX_MCSLOCK_H +#define _LINUX_MCSLOCK_H + +#include <linux/types.h> +#include <linux/kernel.h> +#include <linux/irqflags.h> +#include <asm/atomic.h> +#include <asm/system.h> +#include <asm/processor.h> + +#ifndef CONFIG_SMP +typdef struct { +} mcslock_t; + +static inline void mcs_lock_init(mcslock_t *lock) +{ +} + +static inline int mcs_is_locked(mcslock_t *lock) +{ + return 0; +} + +static inline void mcs_unlock_wait(mcslock_t *lock) +{ +} + +static inline void mcs_lock(mcslock_t *lock, int nest) +{ +} +static inline int mcs_trylock(mcslock_t *lock, int nest) +{ + return 1; +} +static inline void mcs_unlock(mcslock_t *lock, int nest) +{ +} + +#else /*!CONFIG_SMP*/ + +typedef struct { + atomic_t cpu; +} mcslock_t; + +#define MCS_CPU_NONE 0x7fffffff + +#define DEFINE_MCS_LOCK(name) mcslock_t name = { .cpu = ATOMIC_INIT(MCS_CPU_NONE) } +static inline void mcs_lock_init(mcslock_t *lock) +{ + atomic_set(&lock->cpu, MCS_CPU_NONE); /* unlocked */ +} + +static inline int mcs_is_locked(mcslock_t *lock) +{ + return atomic_read(&lock->cpu) != MCS_CPU_NONE; +} + +static inline void mcs_unlock_wait(mcslock_t *lock) +{ + while (mcs_is_locked(lock))
include/linux/mcslock.h line 74
Quoted 10 lines
include/linux/mcslock.h new file +10
-0+ cpu_relax(); +} + +extern void mcs_lock (mcslock_t *lock,int nest); +extern int mcs_trylock (mcslock_t *lock,int nest); +extern void mcs_unlock (mcslock_t *lock,int nest); + +#endif /*!CONFIG_SMP*/ + +extern int atomic_dec_and_mcslock (atomic_t *atomic,mcslock_t *lock,int nest);
I would prefer to see this done as a polymorhpic atomic_dec_and_lock() call with something like Ingo's "PICK_OP" method (currently used in -rt) rather than expanding the atomic_X namespace. I haven't looked into it to make sure its plausible, but I do not see any reasons from 30k feet why it would not. Its not a huge deal either way, but just something to consider.
-Greg
[resend, as the first had a problem going out]
Hi Nick,
Cool stuff...see inline
Quoted 87 lines · Nick Piggin
I've implemented a sort of spin local, queueing MCS lock that uses per-cpu nodes that can be shared by multiple locks. I guess it is preferable to remove global locks, but some don't seem to be going anywhere soon.
The only issue is that only one set of nodes can be actively used for a lock at once, so if we want to nest these locks, we have to use different sets for each one. This shouldn't be much of a problem because we don't have too many "big" locks, and yet fewer ones that are nested in one another.
With this modification to MCS locks, each lock is pretty small in size, so it could even be used for some per-object locks if we really wanted.
I've converted dcache lock as well... it shows improved results on a 64-way Altix. Unfortunately this adds an extra atomic to the unlock path. I didn't look too hard at array based queue locks, there might be a a type of those that would work better.
Index:
linux-2.6/include/linux/mcslock.h
===================================================================include/linux/mcslock.h new file +64
-0@@ -0,0 +1,76 @@ +/* +* "Shared-node" MCS lock. +* Nick Piggin <[email protected]> +*/ +#ifndef _LINUX_MCSLOCK_H +#define _LINUX_MCSLOCK_H + +#include <linux/types.h> +#include <linux/kernel.h> +#include <linux/irqflags.h> +#include <asm/atomic.h> +#include <asm/system.h> +#include <asm/processor.h> + +#ifndef CONFIG_SMP +typdef struct { +} mcslock_t; + +static inline void mcs_lock_init(mcslock_t *lock) +{ +} + +static inline int mcs_is_locked(mcslock_t *lock) +{ + return 0; +} + +static inline void mcs_unlock_wait(mcslock_t *lock) +{ +} + +static inline void mcs_lock(mcslock_t *lock, int nest) +{ +} +static inline int mcs_trylock(mcslock_t *lock, int nest) +{ + return 1; +} +static inline void mcs_unlock(mcslock_t *lock, int nest) +{ +} + +#else /*!CONFIG_SMP*/ + +typedef struct { + atomic_t cpu; +} mcslock_t; + +#define MCS_CPU_NONE 0x7fffffff + +#define DEFINE_MCS_LOCK(name) mcslock_t name = { .cpu = ATOMIC_INIT(MCS_CPU_NONE) } +static inline void mcs_lock_init(mcslock_t *lock) +{ + atomic_set(&lock->cpu, MCS_CPU_NONE); /* unlocked */ +} + +static inline int mcs_is_locked(mcslock_t *lock) +{ + return atomic_read(&lock->cpu) != MCS_CPU_NONE; +} + +static inline void mcs_unlock_wait(mcslock_t *lock) +{ + while (mcs_is_locked(lock))
include/linux/mcslock.h line 74
Quoted 10 lines
include/linux/mcslock.h new file +10
-0+ cpu_relax(); +} + +extern void mcs_lock (mcslock_t *lock,int nest); +extern int mcs_trylock (mcslock_t *lock,int nest); +extern void mcs_unlock (mcslock_t *lock,int nest); + +#endif /*!CONFIG_SMP*/ + +extern int atomic_dec_and_mcslock (atomic_t *atomic,mcslock_t *lock,int nest);
I would prefer to see this done as a polymorhpic atomic_dec_and_lock() call with something like Ingo's "PICK_OP" method (currently used in -rt) rather than expanding the atomic_X namespace. I haven't looked into it to make sure its plausible, but I do not see any reasons from 30k feet why it would not. Its not a huge deal either way, but just something to consider.
-Greg