首页 > *nix技术, 内核技术, 多核优化 > Kernel 3.12里对引用计数器的优化

Kernel 3.12里对引用计数器的优化

2013年10月19日 发表评论 阅读评论 6,748 次浏览

Linux Kernel 3.12新引入了一个对引用计数器更新的优化,这个优化非常Nice,它也可以被应用到用户空间里,下面来看看。
我们知道,引用计数是一种经常被使用到的机制。比如某资源(例如文件)被某对象(下文以进程代称)访问使用时,那么该资源就会把它的引用计数加一,当某进程结束访问时,该资源的引用计数就会减去一,直到最后为0是则将进行资源回收。这就是应用引用计数机制的典型场景。

如果以一个struct数据结构代表某个资源,那么引用计数一般就是作为该结构体的一个字段,例如struct dentry的d_count字段

struct dentry {
	/* RCU lookup touched fields */
	unsigned int d_flags;		/* protected by d_lock */
	seqcount_t d_seq;		/* per dentry seqlock */
	struct hlist_bl_node d_hash;	/* lookup hash list */
	struct dentry *d_parent;	/* parent directory */
	struct qstr d_name;
	struct inode *d_inode;		/* Where the name belongs to - NULL is
					 * negative */
	unsigned char d_iname[DNAME_INLINE_LEN];	/* small names */

	/* Ref lookup also touches following */
	unsigned int d_count;		/* protected by d_lock */
	spinlock_t d_lock;		/* per dentry lock */
	const struct dentry_operations *d_op;
	struct super_block *d_sb;	/* The root of the dentry tree */
	unsigned long d_time;		/* used by d_revalidate */
	void *d_fsdata;			/* fs-specific data */

	struct list_head d_lru;		/* LRU list */
	/*
	 * d_child and d_rcu can share memory
	 */
	union {
		struct list_head d_child;	/* child of parent list */
	 	struct rcu_head d_rcu;
	} d_u;
	struct list_head d_subdirs;	/* our children */
	struct hlist_node d_alias;	/* inode alias list */
};

多个进程同时修改引用计数器时需要进行加锁,当然,我们可以使用atomic_t类型的原子变量,但这只在引用计数字段与结构体的其他字段没有任何相关性时才有用,但大多数情况下,进程必须首先获得对这个结构体的独占,即加锁,才能具备有资格修改这个结构体,比如其中的引用计数字段,因此在这种情况下,不论引用计数字段是不是atomic_t类型,都已经不重要了。比如上面的dentry结构体字段d_count就只是一个普通的unsigned int类型。

下面以struct dentry为例,来展示一下本文所提到的优化是如何做的。
常规的修改d_count需要三步:
1,lock d_lock
2,inc/dec d_count
3,unlock d_lock
当然,在第1步和第3步之间,我们还可以修改struct dentry的其他字段。考虑这么一种特殊情况,如果我仅仅只是要修改一下d_count(有很多这样的场景,比如不再使用某资源时,此时一般也就只是需要去减一下引用计数,而不会对其他任何字段做操作),那么有没有优化的余地呢?
把d_count设置为atomic_t类型可以么?不行,举例:进程1获得了d_lock,且还未释放锁,此时仅仅想要修改一下d_count的进程2直接去修改d_count,必然也需要先去获取d_lock锁,因为d_lock锁存在的意义就是为了保护dentry结构体的任何字段只能被当前获取到锁的进程修改,当然也就包括字段d_count。这又回到了前面所说的,“引用计数字段是不是atomic_t类型,都没有任何意义”。

该轮到lockref出场了,先看其定义

struct lockref {
	union {
#ifdef CONFIG_CMPXCHG_LOCKREF
		aligned_u64 lock_count;
#endif
		struct {
			spinlock_t lock;
			unsigned int count;
		};
	};
};

在Kernel 3.12里,struct dentry的定义相应的被修改为如下

struct dentry {
	/* RCU lookup touched fields */
	unsigned int d_flags;		/* protected by d_lock */
	seqcount_t d_seq;		/* per dentry seqlock */
	struct hlist_bl_node d_hash;	/* lookup hash list */
	struct dentry *d_parent;	/* parent directory */
	struct qstr d_name;
	struct inode *d_inode;		/* Where the name belongs to - NULL is
					 * negative */
	unsigned char d_iname[DNAME_INLINE_LEN];	/* small names */

	/* Ref lookup also touches following */
	struct lockref d_lockref;	/* per-dentry lock and refcount */
	const struct dentry_operations *d_op;
	struct super_block *d_sb;	/* The root of the dentry tree */
	unsigned long d_time;		/* used by d_revalidate */
	void *d_fsdata;			/* fs-specific data */

	struct list_head d_lru;		/* LRU list */
	/*
	 * d_child and d_rcu can share memory
	 */
	union {
		struct list_head d_child;	/* child of parent list */
	 	struct rcu_head d_rcu;
	} d_u;
	struct list_head d_subdirs;	/* our children */
	struct hlist_node d_alias;	/* inode alias list */
};

再来看仅仅只是要修改一下d_count的需求,此时,我们只需要利用cmpxchg对d_lockref字段进行操作即可。cmpxchg是一个机器硬件直接支持的原子指令,我曾详细的介绍过:http://lenky.info/2012/11/17/cmpxchgl/,这里不多累述。

u64 cmpxchg(u64 *location, u64 old, u64 new);

总之,利用cmpxchg把lock和count都考虑进来了(注意这两个字段被合在同一个64位里了,而cmpxchg比较的就是整个64位),当一个进程尝试去修改一下d_count时,只有在lock未锁定的情况下才能成功,这也就满足了d_lock锁存在的意义。这个优化的关键点在于,它把多条指令的操作合而为一,大大避免了冲突的概率,也就相应的降低了所谓的cache-line bouncing(这个概念和false sharing,cache ping pong一致,我在这里有介绍过)。这样的优化导致的结果是在某些测试案例里,最高可提升6倍的性能。

PS:目前只有x86-64上有lockref的完整实现。

完全参考:
https://lwn.net/Articles/565734/

转载请保留地址:http://www.lenky.info/archives/2013/10/2358http://lenky.info/?p=2358


备注:如无特殊说明,文章内容均出自Lenky个人的真实理解而并非存心妄自揣测来故意愚人耳目。由于个人水平有限,虽力求内容正确无误,但仍然难免出错,请勿见怪,如果可以则请留言告之,并欢迎来讨论。另外值得说明的是,Lenky的部分文章以及部分内容参考借鉴了网络上各位网友的热心分享,特别是一些带有完全参考的文章,其后附带的链接内容也许更直接、更丰富,而我只是做了一下归纳&转述,在此也一并表示感谢。关于本站的所有技术文章,欢迎转载,但请遵从CC创作共享协议,而一些私人性质较强的心情随笔,建议不要转载。

法律:根据最新颁布的《信息网络传播权保护条例》,如果您认为本文章的任何内容侵犯了您的权利,请以Email或书面等方式告知,本站将及时删除相关内容或链接。

  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.