diff options
author | Linus Torvalds <torvalds@linux-foundation.org> | 2013-07-03 06:52:14 +0400 |
---|---|---|
committer | Linus Torvalds <torvalds@linux-foundation.org> | 2013-07-03 06:52:14 +0400 |
commit | 13cc56013842a847a0f6ff805d9ed9181e753ef8 (patch) | |
tree | 76b55717efc36f83c934ee894a8522e8a28eb57f | |
parent | 7c6809ff2bd63d4c97ce9e0b94d39d5180842c48 (diff) | |
parent | a4244454df1296e90cc961c1b636b1176ef0d9a0 (diff) | |
download | linux-13cc56013842a847a0f6ff805d9ed9181e753ef8.tar.xz |
Merge branch 'for-3.11' of git://git.kernel.org/pub/scm/linux/kernel/git/tj/percpu
Pull per-cpu changes from Tejun Heo:
"This pull request contains Kent's per-cpu reference counter. It has
gone through several iterations since the last time and the dynamic
allocation is gone.
The usual usage is relatively straight-forward although async kill
confirm interface, which is not used int most cases, is somewhat icky.
There also are some interface concerns - e.g. I'm not sure about
passing in @relesae callback during init as that becomes funny when we
later implement synchronous kill_and_drain - but nothing too serious
and it's quite useable now.
cgroup_subsys_state refcnting has already been converted and we should
convert module refcnt (Kent?)"
* 'for-3.11' of git://git.kernel.org/pub/scm/linux/kernel/git/tj/percpu:
percpu-refcount: use RCU-sched insted of normal RCU
percpu-refcount: implement percpu_tryget() along with percpu_ref_kill_and_confirm()
percpu-refcount: implement percpu_ref_cancel_init()
percpu-refcount: add __must_check to percpu_ref_init() and don't use ACCESS_ONCE() in percpu_ref_kill_rcu()
percpu-refcount: cosmetic updates
percpu-refcount: consistently use plain (non-sched) RCU
percpu-refcount: Don't use silly cmpxchg()
percpu: implement generic percpu refcounting
-rw-r--r-- | include/linux/percpu-refcount.h | 174 | ||||
-rw-r--r-- | lib/Makefile | 2 | ||||
-rw-r--r-- | lib/percpu-refcount.c | 158 |
3 files changed, 333 insertions, 1 deletions
diff --git a/include/linux/percpu-refcount.h b/include/linux/percpu-refcount.h new file mode 100644 index 000000000000..95961f0bf62d --- /dev/null +++ b/include/linux/percpu-refcount.h @@ -0,0 +1,174 @@ +/* + * Percpu refcounts: + * (C) 2012 Google, Inc. + * Author: Kent Overstreet <koverstreet@google.com> + * + * This implements a refcount with similar semantics to atomic_t - atomic_inc(), + * atomic_dec_and_test() - but percpu. + * + * There's one important difference between percpu refs and normal atomic_t + * refcounts; you have to keep track of your initial refcount, and then when you + * start shutting down you call percpu_ref_kill() _before_ dropping the initial + * refcount. + * + * The refcount will have a range of 0 to ((1U << 31) - 1), i.e. one bit less + * than an atomic_t - this is because of the way shutdown works, see + * percpu_ref_kill()/PCPU_COUNT_BIAS. + * + * Before you call percpu_ref_kill(), percpu_ref_put() does not check for the + * refcount hitting 0 - it can't, if it was in percpu mode. percpu_ref_kill() + * puts the ref back in single atomic_t mode, collecting the per cpu refs and + * issuing the appropriate barriers, and then marks the ref as shutting down so + * that percpu_ref_put() will check for the ref hitting 0. After it returns, + * it's safe to drop the initial ref. + * + * USAGE: + * + * See fs/aio.c for some example usage; it's used there for struct kioctx, which + * is created when userspaces calls io_setup(), and destroyed when userspace + * calls io_destroy() or the process exits. + * + * In the aio code, kill_ioctx() is called when we wish to destroy a kioctx; it + * calls percpu_ref_kill(), then hlist_del_rcu() and sychronize_rcu() to remove + * the kioctx from the proccess's list of kioctxs - after that, there can't be + * any new users of the kioctx (from lookup_ioctx()) and it's then safe to drop + * the initial ref with percpu_ref_put(). + * + * Code that does a two stage shutdown like this often needs some kind of + * explicit synchronization to ensure the initial refcount can only be dropped + * once - percpu_ref_kill() does this for you, it returns true once and false if + * someone else already called it. The aio code uses it this way, but it's not + * necessary if the code has some other mechanism to synchronize teardown. + * around. + */ + +#ifndef _LINUX_PERCPU_REFCOUNT_H +#define _LINUX_PERCPU_REFCOUNT_H + +#include <linux/atomic.h> +#include <linux/kernel.h> +#include <linux/percpu.h> +#include <linux/rcupdate.h> + +struct percpu_ref; +typedef void (percpu_ref_func_t)(struct percpu_ref *); + +struct percpu_ref { + atomic_t count; + /* + * The low bit of the pointer indicates whether the ref is in percpu + * mode; if set, then get/put will manipulate the atomic_t (this is a + * hack because we need to keep the pointer around for + * percpu_ref_kill_rcu()) + */ + unsigned __percpu *pcpu_count; + percpu_ref_func_t *release; + percpu_ref_func_t *confirm_kill; + struct rcu_head rcu; +}; + +int __must_check percpu_ref_init(struct percpu_ref *ref, + percpu_ref_func_t *release); +void percpu_ref_cancel_init(struct percpu_ref *ref); +void percpu_ref_kill_and_confirm(struct percpu_ref *ref, + percpu_ref_func_t *confirm_kill); + +/** + * percpu_ref_kill - drop the initial ref + * @ref: percpu_ref to kill + * + * Must be used to drop the initial ref on a percpu refcount; must be called + * precisely once before shutdown. + * + * Puts @ref in non percpu mode, then does a call_rcu() before gathering up the + * percpu counters and dropping the initial ref. + */ +static inline void percpu_ref_kill(struct percpu_ref *ref) +{ + return percpu_ref_kill_and_confirm(ref, NULL); +} + +#define PCPU_STATUS_BITS 2 +#define PCPU_STATUS_MASK ((1 << PCPU_STATUS_BITS) - 1) +#define PCPU_REF_PTR 0 +#define PCPU_REF_DEAD 1 + +#define REF_STATUS(count) (((unsigned long) count) & PCPU_STATUS_MASK) + +/** + * percpu_ref_get - increment a percpu refcount + * @ref: percpu_ref to get + * + * Analagous to atomic_inc(). + */ +static inline void percpu_ref_get(struct percpu_ref *ref) +{ + unsigned __percpu *pcpu_count; + + rcu_read_lock_sched(); + + pcpu_count = ACCESS_ONCE(ref->pcpu_count); + + if (likely(REF_STATUS(pcpu_count) == PCPU_REF_PTR)) + __this_cpu_inc(*pcpu_count); + else + atomic_inc(&ref->count); + + rcu_read_unlock_sched(); +} + +/** + * percpu_ref_tryget - try to increment a percpu refcount + * @ref: percpu_ref to try-get + * + * Increment a percpu refcount unless it has already been killed. Returns + * %true on success; %false on failure. + * + * Completion of percpu_ref_kill() in itself doesn't guarantee that tryget + * will fail. For such guarantee, percpu_ref_kill_and_confirm() should be + * used. After the confirm_kill callback is invoked, it's guaranteed that + * no new reference will be given out by percpu_ref_tryget(). + */ +static inline bool percpu_ref_tryget(struct percpu_ref *ref) +{ + unsigned __percpu *pcpu_count; + int ret = false; + + rcu_read_lock_sched(); + + pcpu_count = ACCESS_ONCE(ref->pcpu_count); + + if (likely(REF_STATUS(pcpu_count) == PCPU_REF_PTR)) { + __this_cpu_inc(*pcpu_count); + ret = true; + } + + rcu_read_unlock_sched(); + + return ret; +} + +/** + * percpu_ref_put - decrement a percpu refcount + * @ref: percpu_ref to put + * + * Decrement the refcount, and if 0, call the release function (which was passed + * to percpu_ref_init()) + */ +static inline void percpu_ref_put(struct percpu_ref *ref) +{ + unsigned __percpu *pcpu_count; + + rcu_read_lock_sched(); + + pcpu_count = ACCESS_ONCE(ref->pcpu_count); + + if (likely(REF_STATUS(pcpu_count) == PCPU_REF_PTR)) + __this_cpu_dec(*pcpu_count); + else if (unlikely(atomic_dec_and_test(&ref->count))) + ref->release(ref); + + rcu_read_unlock_sched(); +} + +#endif diff --git a/lib/Makefile b/lib/Makefile index 22f0f4e8a9e1..8f8d385187f2 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -13,7 +13,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \ sha1.o md5.o irq_regs.o reciprocal_div.o argv_split.o \ proportions.o flex_proportions.o prio_heap.o ratelimit.o show_mem.o \ is_single_threaded.o plist.o decompress.o kobject_uevent.o \ - earlycpio.o + earlycpio.o percpu-refcount.o obj-$(CONFIG_ARCH_HAS_DEBUG_STRICT_USER_COPY_CHECKS) += usercopy.o lib-$(CONFIG_MMU) += ioremap.o diff --git a/lib/percpu-refcount.c b/lib/percpu-refcount.c new file mode 100644 index 000000000000..7deeb6297a48 --- /dev/null +++ b/lib/percpu-refcount.c @@ -0,0 +1,158 @@ +#define pr_fmt(fmt) "%s: " fmt "\n", __func__ + +#include <linux/kernel.h> +#include <linux/percpu-refcount.h> + +/* + * Initially, a percpu refcount is just a set of percpu counters. Initially, we + * don't try to detect the ref hitting 0 - which means that get/put can just + * increment or decrement the local counter. Note that the counter on a + * particular cpu can (and will) wrap - this is fine, when we go to shutdown the + * percpu counters will all sum to the correct value + * + * (More precisely: because moduler arithmatic is commutative the sum of all the + * pcpu_count vars will be equal to what it would have been if all the gets and + * puts were done to a single integer, even if some of the percpu integers + * overflow or underflow). + * + * The real trick to implementing percpu refcounts is shutdown. We can't detect + * the ref hitting 0 on every put - this would require global synchronization + * and defeat the whole purpose of using percpu refs. + * + * What we do is require the user to keep track of the initial refcount; we know + * the ref can't hit 0 before the user drops the initial ref, so as long as we + * convert to non percpu mode before the initial ref is dropped everything + * works. + * + * Converting to non percpu mode is done with some RCUish stuff in + * percpu_ref_kill. Additionally, we need a bias value so that the atomic_t + * can't hit 0 before we've added up all the percpu refs. + */ + +#define PCPU_COUNT_BIAS (1U << 31) + +/** + * percpu_ref_init - initialize a percpu refcount + * @ref: percpu_ref to initialize + * @release: function which will be called when refcount hits 0 + * + * Initializes the refcount in single atomic counter mode with a refcount of 1; + * analagous to atomic_set(ref, 1). + * + * Note that @release must not sleep - it may potentially be called from RCU + * callback context by percpu_ref_kill(). + */ +int percpu_ref_init(struct percpu_ref *ref, percpu_ref_func_t *release) +{ + atomic_set(&ref->count, 1 + PCPU_COUNT_BIAS); + + ref->pcpu_count = alloc_percpu(unsigned); + if (!ref->pcpu_count) + return -ENOMEM; + + ref->release = release; + return 0; +} + +/** + * percpu_ref_cancel_init - cancel percpu_ref_init() + * @ref: percpu_ref to cancel init for + * + * Once a percpu_ref is initialized, its destruction is initiated by + * percpu_ref_kill() and completes asynchronously, which can be painful to + * do when destroying a half-constructed object in init failure path. + * + * This function destroys @ref without invoking @ref->release and the + * memory area containing it can be freed immediately on return. To + * prevent accidental misuse, it's required that @ref has finished + * percpu_ref_init(), whether successful or not, but never used. + * + * The weird name and usage restriction are to prevent people from using + * this function by mistake for normal shutdown instead of + * percpu_ref_kill(). + */ +void percpu_ref_cancel_init(struct percpu_ref *ref) +{ + unsigned __percpu *pcpu_count = ref->pcpu_count; + int cpu; + + WARN_ON_ONCE(atomic_read(&ref->count) != 1 + PCPU_COUNT_BIAS); + + if (pcpu_count) { + for_each_possible_cpu(cpu) + WARN_ON_ONCE(*per_cpu_ptr(pcpu_count, cpu)); + free_percpu(ref->pcpu_count); + } +} + +static void percpu_ref_kill_rcu(struct rcu_head *rcu) +{ + struct percpu_ref *ref = container_of(rcu, struct percpu_ref, rcu); + unsigned __percpu *pcpu_count = ref->pcpu_count; + unsigned count = 0; + int cpu; + + /* Mask out PCPU_REF_DEAD */ + pcpu_count = (unsigned __percpu *) + (((unsigned long) pcpu_count) & ~PCPU_STATUS_MASK); + + for_each_possible_cpu(cpu) + count += *per_cpu_ptr(pcpu_count, cpu); + + free_percpu(pcpu_count); + + pr_debug("global %i pcpu %i", atomic_read(&ref->count), (int) count); + + /* + * It's crucial that we sum the percpu counters _before_ adding the sum + * to &ref->count; since gets could be happening on one cpu while puts + * happen on another, adding a single cpu's count could cause + * @ref->count to hit 0 before we've got a consistent value - but the + * sum of all the counts will be consistent and correct. + * + * Subtracting the bias value then has to happen _after_ adding count to + * &ref->count; we need the bias value to prevent &ref->count from + * reaching 0 before we add the percpu counts. But doing it at the same + * time is equivalent and saves us atomic operations: + */ + + atomic_add((int) count - PCPU_COUNT_BIAS, &ref->count); + + /* @ref is viewed as dead on all CPUs, send out kill confirmation */ + if (ref->confirm_kill) + ref->confirm_kill(ref); + + /* + * Now we're in single atomic_t mode with a consistent refcount, so it's + * safe to drop our initial ref: + */ + percpu_ref_put(ref); +} + +/** + * percpu_ref_kill_and_confirm - drop the initial ref and schedule confirmation + * @ref: percpu_ref to kill + * @confirm_kill: optional confirmation callback + * + * Equivalent to percpu_ref_kill() but also schedules kill confirmation if + * @confirm_kill is not NULL. @confirm_kill, which may not block, will be + * called after @ref is seen as dead from all CPUs - all further + * invocations of percpu_ref_tryget() will fail. See percpu_ref_tryget() + * for more details. + * + * Due to the way percpu_ref is implemented, @confirm_kill will be called + * after at least one full RCU grace period has passed but this is an + * implementation detail and callers must not depend on it. + */ +void percpu_ref_kill_and_confirm(struct percpu_ref *ref, + percpu_ref_func_t *confirm_kill) +{ + WARN_ONCE(REF_STATUS(ref->pcpu_count) == PCPU_REF_DEAD, + "percpu_ref_kill() called more than once!\n"); + + ref->pcpu_count = (unsigned __percpu *) + (((unsigned long) ref->pcpu_count)|PCPU_REF_DEAD); + ref->confirm_kill = confirm_kill; + + call_rcu_sched(&ref->rcu, percpu_ref_kill_rcu); +} |