Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1725166 > unrolled thread

[RFC PATCH 02/11] refcount: Implement inc/decrement-and-return functions

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  [RFC PATCH 02/11] refcount: Implement inc/decrement-and-return  functions David Howells <dhowells@redhat.com> - 2017-09-01 17:50 +0200
    Re: [RFC PATCH 02/11] refcount: Implement inc/decrement-and-return  functions Peter Zijlstra <peterz@infradead.org> - 2017-09-01 18:50 +0200
      Re: [RFC PATCH 02/11] refcount: Implement inc/decrement-and-return functions David Howells <dhowells@redhat.com> - 2017-09-01 23:20 +0200
        Re: [RFC PATCH 02/11] refcount: Implement inc/decrement-and-return  functions Peter Zijlstra <peterz@infradead.org> - 2017-09-02 00:00 +0200
          Re: [RFC PATCH 02/11] refcount: Implement inc/decrement-and-return  functions Peter Zijlstra <peterz@infradead.org> - 2017-09-02 00:10 +0200
          Re: [RFC PATCH 02/11] refcount: Implement inc/decrement-and-return functions David Howells <dhowells@redhat.com> - 2017-09-02 01:00 +0200
            Re: [RFC PATCH 02/11] refcount: Implement inc/decrement-and-return  functions Peter Zijlstra <peterz@infradead.org> - 2017-09-04 09:40 +0200
    Re: [RFC PATCH 02/11] refcount: Implement inc/decrement-and-return  functions Christoph Hellwig <hch@infradead.org> - 2017-09-04 17:40 +0200
      Re: [RFC PATCH 02/11] refcount: Implement inc/decrement-and-return functions David Howells <dhowells@redhat.com> - 2017-09-04 18:10 +0200
        Re: [RFC PATCH 02/11] refcount: Implement inc/decrement-and-return  functions Christoph Hellwig <hch@infradead.org> - 2017-09-05 08:50 +0200

#1725166 — [RFC PATCH 02/11] refcount: Implement inc/decrement-and-return functions

Implement functions that increment or decrement a refcount_t object and
return the value.  The dec-and-ret function can be used to maintain a
counter in a cache where 1 means the object is unused, but available and
the garbage collector can use refcount_dec_if_one() to make the object
unavailable.  Further, both functions can be used to accurately trace the
refcount (refcount_inc() followed by refcount_read() can't be considered
accurate).

The interface is as follows:

	unsigned int refcount_dec_return(refcount_t *r);
	unsigned int refcount_inc_return(refcount_t *r);

instead.

Signed-off-by: David Howells <dhowells@redhat.com>
cc: Peter Zijlstra <peterz@infradead.org>
cc: Kees Cook <keescook@chromium.org>
---

 include/linux/refcount.h |   12 ++++++++
 lib/refcount.c           |   67 ++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 79 insertions(+)

diff --git a/include/linux/refcount.h b/include/linux/refcount.h
index 591792c8e5b0..566c0cea7343 100644
--- a/include/linux/refcount.h
+++ b/include/linux/refcount.h
@@ -52,6 +52,8 @@ extern __must_check bool refcount_sub_and_test(unsigned int i, refcount_t *r);
 
 extern __must_check bool refcount_dec_and_test(refcount_t *r);
 extern void refcount_dec(refcount_t *r);
+extern __must_check unsigned int refcount_inc_return(refcount_t *r);
+extern __must_check unsigned int refcount_dec_return(refcount_t *r);
 #else
 static inline __must_check bool refcount_add_not_zero(unsigned int i, refcount_t *r)
 {
@@ -87,6 +89,16 @@ static inline void refcount_dec(refcount_t *r)
 {
 	atomic_dec(&r->refs);
 }
+
+static inline unsigned int refcount_inc_return(refcount_t *r)
+{
+	return atomic_inc_return(&r->refs);
+}
+
+static inline unsigned int refcount_dec_return(refcount_t *r)
+{
+	return atomic_dec_return(&r->refs);
+}
 #endif /* CONFIG_REFCOUNT_FULL */
 
 extern __must_check bool refcount_dec_if_one(refcount_t *r);
diff --git a/lib/refcount.c b/lib/refcount.c
index 5d0582a9480c..3a1d800bf830 100644
--- a/lib/refcount.c
+++ b/lib/refcount.c
@@ -154,6 +154,40 @@ void refcount_inc(refcount_t *r)
 EXPORT_SYMBOL(refcount_inc);
 
 /**
+ * refcount_inc_return - increment a refcount and return the new value
+ * @r: the refcount to increment
+ *
+ * Similar to atomic_inc_return(), but will saturate at UINT_MAX and WARN.
+ *
+ * Provides no memory ordering, it is assumed the caller has guaranteed the
+ * object memory to be stable (RCU, etc.). It does provide a control dependency
+ * and thereby orders future stores. See the comment on top.
+ *
+ * Return: the new value.
+ */
+unsigned int refcount_inc_return(refcount_t *r)
+{
+	unsigned int new, val = atomic_read(&r->refs);
+
+	do {
+		new = val + 1;
+
+		if (!val) {
+			WARN_ONCE(!val, "refcount_t: increment on 0; use-after-free.\n");
+			return 0;
+		}
+
+		if (unlikely(!new))
+			return UINT_MAX;
+
+	} while (!atomic_try_cmpxchg_relaxed(&r->refs, &val, new));
+
+	WARN_ONCE(new == UINT_MAX, "refcount_t: saturated; leaking memory.\n");
+	return new;
+}
+EXPORT_SYMBOL(refcount_inc_return);
+
+/**
  * refcount_sub_and_test - subtract from a refcount and test if it is 0
  * @i: amount to subtract from the refcount
  * @r: the refcount
@@ -227,6 +261,39 @@ void refcount_dec(refcount_t *r)
 	WARN_ONCE(refcount_dec_and_test(r), "refcount_t: decrement hit 0; leaking memory.\n");
 }
 EXPORT_SYMBOL(refcount_dec);
+
+/**
+ * refcount_dec_return - Decrement a refcount and return the new value.
+ * @r: the refcount
+ *
+ * Similar to atomic_dec_return(), it will WARN on underflow and fail to
+ * decrement when saturated at UINT_MAX.  It isn't permitted to use this to
+ * decrement a counter to 0.
+ *
+ * Provides release memory ordering, such that prior loads and stores are done
+ * before.
+ */
+unsigned int refcount_dec_return(refcount_t *r)
+{
+	unsigned int new, val = atomic_read(&r->refs);
+
+	do {
+		if (unlikely(val == UINT_MAX))
+			return val;
+
+		new = val - 1;
+		if (unlikely(val == 0)) {
+			WARN_ONCE(val == 0, "refcount_t: underflow; use-after-free.\n");
+			return val;
+		}
+
+		WARN_ONCE(val == 1, "refcount_t: decrement hit 0; leaking memory.\n");
+
+	} while (!atomic_try_cmpxchg_release(&r->refs, &val, new));
+
+	return new;
+}
+EXPORT_SYMBOL(refcount_dec);
 #endif /* CONFIG_REFCOUNT_FULL */
 
 /**

[toc] | [next] | [standalone]

#1725212

On Fri, Sep 01, 2017 at 04:41:01PM +0100, David Howells wrote:
> Implement functions that increment or decrement a refcount_t object and
> return the value.  The dec-and-ret function can be used to maintain a
> counter in a cache where 1 means the object is unused, but available and
> the garbage collector can use refcount_dec_if_one() to make the object
> unavailable.  Further, both functions can be used to accurately trace the
> refcount (refcount_inc() followed by refcount_read() can't be considered
> accurate).
> 
> The interface is as follows:
> 
> 	unsigned int refcount_dec_return(refcount_t *r);
> 	unsigned int refcount_inc_return(refcount_t *r);
> 

I'm not immediately seeing how wanting 1 to mean unused leads to
requiring these two functions.

If you'll remember, I did that for inode_count and only needed
dec_unless().

[toc] | [prev] | [next] | [standalone]

#1725346 — Re: [RFC PATCH 02/11] refcount: Implement inc/decrement-and-return functions

Peter Zijlstra <peterz@infradead.org> wrote:

> > 	unsigned int refcount_dec_return(refcount_t *r);
> > 	unsigned int refcount_inc_return(refcount_t *r);
> > 
> 
> I'm not immediately seeing how wanting 1 to mean unused leads to
> requiring these two functions.

Did you read the other other part of the description?

	Further, both functions can be used to accurately trace the refcount
	(refcount_inc() followed by refcount_read() can't be considered
	accurate).

> If you'll remember, I did that for inode_count and only needed
> dec_unless().

I don't remember.  inode_count?  I can't find such a thing - did you mean
i_count?  I don't find anything matching "dec_unless.*i_count" either.

David

[toc] | [prev] | [next] | [standalone]

#1725381

On Fri, Sep 01, 2017 at 10:15:39PM +0100, David Howells wrote:
> Peter Zijlstra <peterz@infradead.org> wrote:
> 
> > > 	unsigned int refcount_dec_return(refcount_t *r);
> > > 	unsigned int refcount_inc_return(refcount_t *r);
> > > 
> > 
> > I'm not immediately seeing how wanting 1 to mean unused leads to
> > requiring these two functions.
> 
> Did you read the other other part of the description?
> 
> 	Further, both functions can be used to accurately trace the refcount
> 	(refcount_inc() followed by refcount_read() can't be considered
> 	accurate).

I must admit to having overlooked that. But can we treat the two issues
separately? They are quite distinct.

> > If you'll remember, I did that for inode_count and only needed
> > dec_unless().
> 
> I don't remember.  inode_count?  I can't find such a thing - did you mean
> i_count?  I don't find anything matching "dec_unless.*i_count" either.

Ah, yes, i_count. See these:

https://lkml.kernel.org/r/20170224162044.479190330@infradead.org
https://lkml.kernel.org/r/20170224162044.548813302@infradead.org

But looking at them, i_count was rather special, a normal GC based
scheme doesn't need anything new AFAICT:

add:
	spin_lock(&map->lock)
	refcount_set(&obj->refs, 1);
	map_link(map, obj);
	spin_unlock(&map->lock);

lookup:
	rcu_read_lock();
	obj = map_find(map, key);
	if (obj && !refcount_inc_not_zero(&obj->refs))
	  obj = NULL;
	rcu_read_unlock();

	if (obj) {
	  /* use obj */
	  refcount_dec(&obj->refs); /* should never hit 0 */
	}

GC:
	spin_lock(&map->lock);
	map_for_each_obj_safe(obj, map) {
	  if (refcount_dec_if_one(&obj->refs)) {
	    map_unlink(map, obj);
	    rcu_free(obj);
	  }
	}
	spin_unlock(&map->lock);

[toc] | [prev] | [next] | [standalone]

#1725384

On Fri, Sep 01, 2017 at 11:50:03PM +0200, Peter Zijlstra wrote:
> > Did you read the other other part of the description?
> > 
> > 	Further, both functions can be used to accurately trace the refcount
> > 	(refcount_inc() followed by refcount_read() can't be considered
> > 	accurate).
> 
> I must admit to having overlooked that. But can we treat the two issues
> separately? They are quite distinct.

So for tracing purposes inc_return/dec_return don't cover the full set.

In particular: inc_not_zero, dec_not_one and dec_and_*lock are not
covered.

dec_if_one I suppose we only care about the success case, in which case
we knew it was one by inference.

[toc] | [prev] | [next] | [standalone]

#1725395 — Re: [RFC PATCH 02/11] refcount: Implement inc/decrement-and-return functions

Peter Zijlstra <peterz@infradead.org> wrote:

> 	if (obj) {
> 	  /* use obj */
> 	  refcount_dec(&obj->refs); /* should never hit 0 */
> 	}

You've missed a bit: We need to tell the gc to run when we reduce the refcount
to 1:

	if (obj) {
		...
		if (refcount_dec_return(&obj->refs) == 1)
			schedule_gc();
	}

David

[toc] | [prev] | [next] | [standalone]

#1725889

On Fri, Sep 01, 2017 at 11:51:53PM +0100, David Howells wrote:
> Peter Zijlstra <peterz@infradead.org> wrote:
> 
> > 	if (obj) {
> > 	  /* use obj */
> > 	  refcount_dec(&obj->refs); /* should never hit 0 */
> > 	}
> 
> You've missed a bit: We need to tell the gc to run when we reduce the refcount
> to 1:
> 
> 	if (obj) {
> 		...
> 		if (refcount_dec_return(&obj->refs) == 1)
> 			schedule_gc();
> 	}

Ah, so that isn't fundamental to having a GC. But yes if that's your
requirement, then this makes sense.

Please clarify in the Changelog.

[toc] | [prev] | [next] | [standalone]

#1726142

On Fri, Sep 01, 2017 at 04:41:01PM +0100, David Howells wrote:
> Implement functions that increment or decrement a refcount_t object and
> return the value.  The dec-and-ret function can be used to maintain a
> counter in a cache where 1 means the object is unused, but available and
> the garbage collector can use refcount_dec_if_one() to make the object
> unavailable.  Further, both functions can be used to accurately trace the
> refcount (refcount_inc() followed by refcount_read() can't be considered
> accurate).

Please just use a different interface for that instead of overloading
refcount_t.  The main use case of that type is that it is so simple that
it is hard to get wrong (and have additional checking if things go
wrong)

[toc] | [prev] | [next] | [standalone]

#1726162 — Re: [RFC PATCH 02/11] refcount: Implement inc/decrement-and-return functions

Christoph Hellwig <hch@infradead.org> wrote:

> > Implement functions that increment or decrement a refcount_t object and
> > return the value.  The dec-and-ret function can be used to maintain a
> > counter in a cache where 1 means the object is unused, but available and
> > the garbage collector can use refcount_dec_if_one() to make the object
> > unavailable.  Further, both functions can be used to accurately trace the
> > refcount (refcount_inc() followed by refcount_read() can't be considered
> > accurate).
> 
> Please just use a different interface for that instead of overloading
> refcount_t.  The main use case of that type is that it is so simple that
> it is hard to get wrong (and have additional checking if things go
> wrong)

Which bit are you objecting to?  Wanting to use a refcount_t with 1 to
represent an otherwise-unreferenced object sat in a cache?  Or wanting to
display accurate usage counts when tracing gets and puts of objects?

David

[toc] | [prev] | [next] | [standalone]

#1726375

On Mon, Sep 04, 2017 at 05:08:29PM +0100, David Howells wrote:
> Which bit are you objecting to?  Wanting to use a refcount_t with 1 to
> represent an otherwise-unreferenced object sat in a cache?  Or wanting to
> display accurate usage counts when tracing gets and puts of objects?

Primarily the first, but also any feature creap of the refcount_t in
general.

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web