On Fri, Nov 18, 2016 at 05:06:55PM +0000, Will Deacon wrote:
> On Fri, Nov 18, 2016 at 12:37:18PM +0100, Peter Zijlstra wrote:
> > On Fri, Nov 18, 2016 at 10:07:26AM +0000, Reshetova, Elena wrote:
> > > 
> > > Peter do you have the changes to the refcount_t interface compare to
> > > the version in this patch? 
> > 
> > > We are now starting working on atomic_t --> refcount_t conversions and
> > > it would save a bit of work to have latest version from you that we
> > > can be based upon. 
> > 
> > The latestest version below, mostly just comment changes since last
> > time.
> > 
> > ---
> > Subject: refcount_t: A special purpose refcount type
> > From: Peter Zijlstra <pet...@infradead.org>
> > Date: Mon Nov 14 18:06:19 CET 2016
> > 
> > Provide refcount_t, an atomic_t like primitive built just for
> > refcounting.
> > 
> > It provides saturation semantics such that overflow becomes impossible
> > and thereby 'spurious' use-after-free is avoided.
> > 
> > Signed-off-by: Peter Zijlstra (Intel) <pet...@infradead.org>
> > ---
> >  include/linux/refcount.h |  241 
> > +++++++++++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 241 insertions(+)
> > 
> > --- /dev/null
> > +++ b/include/linux/refcount.h
> > @@ -0,0 +1,241 @@
> > +#ifndef _LINUX_REFCOUNT_H
> > +#define _LINUX_REFCOUNT_H
> > +
> > +/*
> > + * Variant of atomic_t specialized for reference counts.
> > + *
> > + * The interface matches the atomic_t interface (to aid in porting) but 
> > only
> > + * provides the few functions one should use for reference counting.
> > + *
> > + * It differs in that the counter saturates at UINT_MAX and will not move 
> > once
> > + * there. This avoids wrapping the counter and causing 'spurious'
> > + * use-after-free issues.
> > + *
> > + * Memory ordering rules are slightly relaxed wrt regular atomic_t 
> > functions
> > + * and provide only what is strictly required for refcounts.
> > + *
> > + * The increments are fully relaxed; these will not provide ordering. The
> > + * rationale is that whatever is used to obtain the object we're 
> > increasing the
> > + * reference count on will provide the ordering. For locked data 
> > structures,
> > + * its the lock acquire, for RCU/lockless data structures its the dependent
> > + * load.
> > + *
> > + * Do note that inc_not_zero() provides a control dependency which will 
> > order
> > + * future stores against the inc, this ensures we'll never modify the 
> > object
> > + * if we did not in fact acquire a reference.
> > + *
> > + * The decrements will provide release order, such that all the prior 
> > loads and
> > + * stores will be issued before, it also provides a control dependency, 
> > which
> > + * will order us against the subsequent free().
> > + *
> > + * The control dependency is against the load of the cmpxchg (ll/sc) that
> > + * succeeded. This means the stores aren't fully ordered, but this is fine
> > + * because the 1->0 transition indicates no concurrency.
> > + *
> > + * Note that the allocator is responsible for ordering things between 
> > free()
> > + * and alloc().
> > + *
> > + *
> > + * Note: the implementation hard relies on increments, bigger than 1 
> > additions
> > + *       need explicit overflow -> saturation logic.
> > + *
> > + */
> > +
> > +#include <linux/atomic.h>
> > +#include <linux/bug.h>
> > +#include <linux/mutex.h>
> > +#include <linux/spinlock.h>
> > +
> > +typedef struct refcount_struct {
> > +   atomic_t refs;
> > +} refcount_t;
> > +
> > +#define REFCOUNT_INIT(n)   { .refs = ATOMIC_INIT(n), }
> > +
> > +static inline void refcount_set(refcount_t *r, int n)
> > +{
> > +   atomic_set(&r->refs, n);
> > +}
> > +
> > +static inline unsigned int refcount_read(const refcount_t *r)
> > +{
> > +   return atomic_read(&r->refs);
> > +}
> 
> Minor nit, but it might be worth being consistent in our usage of int
> (parameter to refcount_set) and unsigned int (return value of
> refcount_read).
> 
> > +
> > +/*
> > + * Similar to atomic_inc(), will saturate at UINT_MAX and WARN.
> > + *
> > + * Provides no memory ordering, it is assumed the caller already has a
> > + * reference on the object, will WARN when this is not so.
> > + */
> > +static inline void refcount_inc(refcount_t *r)
> > +{
> > +   unsigned int old, new, val = atomic_read(&r->refs);
> > +
> > +   for (;;) {
> > +           WARN(!val, "refcount_t: increment on 0; use-after-free.\n");
> > +
> > +           if (unlikely(val == UINT_MAX))
> > +                   return;
> > +
> > +           new = val + 1;
> > +           old = atomic_cmpxchg_relaxed(&r->refs, val, new);
> > +           if (old == val)
> > +                   break;
> > +
> > +           val = old;
> > +   }
> > +
> > +   WARN(new == UINT_MAX, "refcount_t: saturated; leaking memory.\n");
> > +}
> > +
> > +/*
> > + * Similar to atomic_inc_not_zero(), 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.
> > + */
> > +static inline __must_check
> > +bool refcount_inc_not_zero(refcount_t *r)
> > +{
> > +   unsigned int old, new, val = atomic_read(&r->refs);
> > +
> > +   for (;;) {
> > +           if (!val)
> > +                   return false;
> > +
> > +           if (unlikely(val == UINT_MAX))
> > +                   return true;
> > +
> > +           new = val + 1;
> > +           old = atomic_cmpxchg_relaxed(&r->refs, val, new);
> > +           if (old == val)
> > +                   break;
> > +
> > +           val = old;
> 
> Hmm, it's a shame this code is duplicated from refcount_inc, but I suppose
> you can actually be racing against the counter going to zero here and really
> need to check it each time round the loop. Humph. That said, given that
> refcount_inc WARNs if the thing is zero, maybe that could just call
> refcount_inc_not_zero and warn if it returns false? Does it matter that
> we don't actually do the increment?
> 
> > +   }
> > +
> > +   WARN(new == UINT_MAX, "refcount_t: saturated; leaking memory.\n");
> > +
> > +   return true;
> > +}
> > +
> > +/*
> > + * Similar to atomic_dec_and_test(), it will WARN on underflow and fail to
> > + * decrement when saturated at UINT_MAX.
> 
> It also fails to decrement in the underflow case (which is fine, but not
> obvious from the comment). Same thing below.
> 

Maybe a table in the comment like the following helps?

/*
 * T: return true, F: return fasle
 * W: trigger WARNING
 * N: no effect
 *
 *                      |       value before ops                  |
 *                      |   0   |   1   | UINT_MAX - 1 | UINT_MAX |
 * ---------------------+-------+-------+--------------+----------+
 * inc()                |  W    |       |      W       |      N   |
 * inc_not_zero()       |   FN  |   T   |      WT      |    WTN   |
 * dec_and_test()       |  WFN  |   T   |       F      |     FN   |
 * dec_and_mutex_lock() |  WFN  |   T   |       F      |     FN   |
 * dec_and_spin_lock()  |  WFN  |   T   |       F      |     FN   |
 */

Regards,
Boqun


> > + *
> > + * Provides release memory ordering, such that prior loads and stores are 
> > done
> > + * before, and provides a control dependency such that free() must come 
> > after.
> > + * See the comment on top.
> > + */
> > +static inline __must_check
> > +bool refcount_dec_and_test(refcount_t *r)
> > +{
> > +   unsigned int old, new, val = atomic_read(&r->refs);
> > +
> > +   for (;;) {
> > +           if (val == UINT_MAX)
> > +                   return false;
> > +
> > +           new = val - 1;
> > +           if (WARN(new > val, "refcount_t: underflow; use-after-free.\n"))
> > +                   return false;
> 
> Wouldn't it be clearer to compare val with 0 before doing the decrement?
> 
> Will

Attachment: signature.asc
Description: PGP signature

Reply via email to