Skip to contentSkip to conversation

Generic percpu refcounting

PATCH Applied Kent Overstreet 3 participants 6 messages May 31, 2013 – Jun 5, 2013

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

PATCH 1/1 Generic percpu refcounting

This implements a refcount with similar semantics to atomic_get()/atomic_dec_and_test() - but percpu.

It also implements two stage shutdown, as we need it to tear down the percpu counts. Before dropping the initial refcount, you must call percpu_ref_kill(); this puts the refcount in "shutting down mode" and switches back to a single atomic refcount with the appropriate barriers (synchronize_rcu()).

It's also legal to call percpu_ref_kill() multiple times - it only returns true once, so callers don't have to reimplement shutdown synchronization.

[[email protected]: fix build]
[[email protected]: coding-style tweak]
Cc Zach Brown <[email protected]>
Cc Felipe Balbi <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc Mark Fasheh <[email protected]>
Cc Joel Becker <[email protected]>
Cc Rusty Russell <[email protected]>
Cc Jens Axboe <[email protected]>
Cc Asai Thambi S P <[email protected]>
Cc Selvan Mani <[email protected]>
Cc Sam Bradshaw <[email protected]>
Cc Jeff Moyer <[email protected]>
Cc Al Viro <[email protected]>
Cc Benjamin LaHaise <[email protected]>
Cc Tejun Heo <[email protected]>
Cc Oleg Nesterov <[email protected]>
Cc Christoph Lameter <[email protected]>
Cc Ingo Molnar <[email protected]>
---
 include/linux/percpu-refcount.h | 122 ++++++++++++++++++++++++++++++++++++++
 lib/Makefile                    |   2 +-
 lib/percpu-refcount.c           | 128 ++++++++++++++++++++++++++++++++++++++++
 3 files changed, 251 insertions(+), 1 deletion(-)
 create mode 100644 include/linux/percpu-refcount.h
 create mode 100644 lib/percpu-refcount.c
include/linux/percpu-refcount.h new file +122 -0
new file mode 100644
index 0000000..24b31ef
@@ -0,0 +1,122 @@
+/*
+ * Percpu refcounts:
+ * (C) 2012 Google, Inc.
+ * Author: Kent Overstreet <[email protected]>
+ *
+ * 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_release)(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_release	*release;
+	struct rcu_head		rcu;
+};
+
+int percpu_ref_init(struct percpu_ref *, percpu_ref_release *);
+void percpu_ref_kill(struct percpu_ref *ref);
+
+#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
+ *
+ * Analagous to atomic_inc().
+  */
+static inline void percpu_ref_get(struct percpu_ref *ref)
+{
+	unsigned __percpu *pcpu_count;
+
+	preempt_disable();
+
+	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);
+
+	preempt_enable();
+}
+
+/**
+ * percpu_ref_put - decrement a percpu refcount
+ *
+ * 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;
+
+	preempt_disable();
+
+	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);
+
+	preempt_enable();
+}
+
+#endif
lib/Makefile +1 -1
index c55a037..386db4b 100644
@@ -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
lib/percpu-refcount.c new file +128 -0

128 lines not on this page · raw message

Signature · 1 line
1.8.2.1
maintainer Applied
#1 lore raw
Quoted 26 lines · Kent Overstreet

This implements a refcount with similar semantics to atomic_get()/atomic_dec_and_test() - but percpu.

It also implements two stage shutdown, as we need it to tear down the percpu counts. Before dropping the initial refcount, you must call percpu_ref_kill(); this puts the refcount in "shutting down mode" and switches back to a single atomic refcount with the appropriate barriers (synchronize_rcu()).

It's also legal to call percpu_ref_kill() multiple times - it only returns true once, so callers don't have to reimplement shutdown synchronization.

[[email protected]: fix build]
[[email protected]: coding-style tweak]
Cc Zach Brown <[email protected]>
Cc Felipe Balbi <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc Mark Fasheh <[email protected]>
Cc Joel Becker <[email protected]>
Cc Rusty Russell <[email protected]>
Cc Jens Axboe <[email protected]>
Cc Asai Thambi S P <[email protected]>
Cc Selvan Mani <[email protected]>
Cc Sam Bradshaw <[email protected]>
Cc Jeff Moyer <[email protected]>
Quoted 8 lines
Cc Al Viro <[email protected]>
Cc Benjamin LaHaise <[email protected]>
Cc Tejun Heo <[email protected]>
Cc Oleg Nesterov <[email protected]>
Cc Christoph Lameter <[email protected]>
Cc Ingo Molnar <[email protected]>

Applied to percpu/for-3.11. Andrew, I removed your SOB as the patch is routed outside -mm. Please let me know if you want reviewed/ackd-by added.

git://git.kernel.org/pub/scm/linux/kernel/git/tj/percpu.git for-3.11

Thanks a lot!

Signature · 1 line
tejun
#2 lore raw

PATCH 1/1 percpu-refcount: Don't use silly cmpxchg()

In reply to Kent Overstreet

The cmpxcgh() was just to ensure the debug check didn't race, which was a bit excessive. The caller is supposed to do the appropriate synchronization, which means percpu_ref_kill() can just do a simple store.

---
 lib/percpu-refcount.c | 19 ++++---------------
 1 file changed, 4 insertions(+), 15 deletions(-)
lib/percpu-refcount.c +4 -15
index e65820a..04be7ea 100644
@@ -107,22 +107,11 @@ static void percpu_ref_kill_rcu(struct rcu_head *rcu)
  */
 void percpu_ref_kill(struct percpu_ref *ref)
 {
-	unsigned __percpu *pcpu_count, *old, *new;
+	WARN_ONCE(REF_STATUS(ref->pcpu_count) == PCPU_REF_DEAD,
+		  "percpu_ref_kill() called more than once!\n");
 
-	pcpu_count = ACCESS_ONCE(ref->pcpu_count);
-
-	do {
-		if (REF_STATUS(pcpu_count) == PCPU_REF_DEAD) {
-			WARN(1, "percpu_ref_kill() called more than once!\n");
-			return;
-		}
-
-		old = pcpu_count;
-		new = (unsigned __percpu *)
-			(((unsigned long) pcpu_count)|PCPU_REF_DEAD);
-
-		pcpu_count = cmpxchg(&ref->pcpu_count, old, new);
-	} while (pcpu_count != old);
+	ref->pcpu_count = (unsigned __percpu *)
+		(((unsigned long) ref->pcpu_count)|PCPU_REF_DEAD);
 
 	call_rcu(&ref->rcu, percpu_ref_kill_rcu);
 }
Signature · 1 line
1.8.2.1
maintainer Applied
#3 lore raw

Re: [PATCH] percpu-refcount: Don't use silly cmpxchg()

Quoted 6 lines · Kent Overstreet

The cmpxcgh() was just to ensure the debug check didn't race, which was a bit excessive. The caller is supposed to do the appropriate synchronization, which means percpu_ref_kill() can just do a simple store.

Applied to percpu/for-3.11.

The only concern I have left now is that we now have bitwise-and and test instead of just test in the hot path (get/put) to test whether the percpu part is alive. As x86 has single and-and-test instruction which doesn't require an output register, this only adds a single instruction but this may lead to more overhead on other architectures.

The and-and-test was added because RCU free needs to have access to the percpu pointer after the pointer is killed and can be removed by adding another field to struct percpu_ref which remembers the pointer separately from the original percpu pointer, which I think is a better trade-off given that it makes the hot path lighter and adding another pointer field to struct percpu_ref isn't really gonna affect anything. Plus, it'd also make the code simpler.

Anyways, it's not a big concern at this point and we can address it later.

Thanks a lot, everyone!

Signature · 1 line
tejun
#4 lore raw
In reply to Kent Overstreet
Quoted 17 lines · Kent Overstreet

This implements a refcount with similar semantics to atomic_get()/atomic_dec_and_test() - but percpu.

It also implements two stage shutdown, as we need it to tear down the percpu counts. Before dropping the initial refcount, you must call percpu_ref_kill(); this puts the refcount in "shutting down mode" and switches back to a single atomic refcount with the appropriate barriers (synchronize_rcu()).

It's also legal to call percpu_ref_kill() multiple times - it only returns true once, so callers don't have to reimplement shutdown synchronization.

include/linux/percpu-refcount.h new file +5 -0
+static inline void percpu_ref_get(struct percpu_ref *ref)
+{
+	unsigned __percpu *pcpu_count;
+
+	preempt_disable();

include/linux/percpu-refcount.h line 98

Quoted 10 lines
include/linux/percpu-refcount.h new file +10 -0
+
+	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);
+
+	preempt_enable();
+}

I think this should be rcu_read_lock(), which is currently equivalent but theoretically different.

Does your percpu_ref_kill() *really* need to be nonblocking? (I'd have to read your other patches which use this to be sure). Otherwise, just use synchronize_rcu(), and get rid of the release function...

Cheers,
Rusty.

maintainer
#5 lore raw
Quoted 2 lines · Rusty Russell

I think this should be rcu_read_lock(), which is currently equivalent but theoretically different.

I suggested using preempt_disable/enable() along with sched RCU. I thought that was better for some reason but I was probably misremembering something. rcu_read_lock/unlock() w/ synchronize_rcu() should be fine too. I don't care either way.

Quoted 3 lines

Does your percpu_ref_kill() *really* need to be nonblocking? (I'd have to read your other patches which use this to be sure). Otherwise, just use synchronize_rcu(), and get rid of the release function...

synchronize_rcu() can always become problematic and should always be avoided for generic things which may be used in various ways. They develop into very long latencies pretty quickly when chained back to back.

Thanks.

Signature · 1 line
tejun