reference counts

To: tech-kern%NetBSD.org@localhost
Subject: reference counts
From: Taylor R Campbell <campbell+netbsd-tech-kern%mumble.net@localhost>
Date: Sat, 11 Apr 2015 21:51:33 +0000

I would like to introduce an easy-to-use-correctly abstraction for
MP-safe reference counts.  I proposed the attached API, based on many
examples and on discussion with dholland@.

It is designed to address three different use cases:

- Object with lifetime ended by a specific operation which needs to
wait until all users are done.

Example: autoconf device with cdevsw nodes.  xyz_detach must wait for
all open files to be closed, and xyz_open/xyz_close must maintain the
reference count and notify xyz_detach when the last close happens.
(We don't exactly do this currently, but that's a bug.)

- Object in global cache with last-user-frees.

Example: vnodes in vcache.  Last reference must be dropped under the
same lock as removing the vnode from the vcache or at least marking it
unusable.  Otherwise, maintenance of the vnode reference count can be
done with atomic operations.

- Shared objects, not in any global tables, with last-user-frees.

Example: process credentials.  Last user just calls kmem_free, no
table or locks involved.

Thoughts?

/*	$NetBSD$	*/

/*-
 * Copyright (c) 2015 The NetBSD Foundation, Inc.
 * All rights reserved.
 *
 * This code is derived from software contributed to The NetBSD Foundation
 * by Taylor R. Campbell.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#ifndef	_SYS_REFCOUNT_H
#define	_SYS_REFCOUNT_H

#include <sys/types.h>
#include <sys/atomic.h>
#include <sys/condvar.h>
#include <sys/errno.h>
#include <sys/mutex.h>
#include <sys/systm.h>

#include <machine/limits.h>

struct refcount {
	volatile unsigned	rc_value;
};

#if DIAGNOSTIC
static inline bool
refcount_referenced_p(struct refcount *refcount)
{

	return 0 < refcount->rc_value;
}

static inline bool
refcount_exclusive_p(struct refcount *refcount)
{

	KASSERT(refcount_referenced_p(refcount));
	return refcount->rc_value == 1;
}
#endif

static inline void
refcount_init(struct refcount *refcount)
{

	refcount->rc_value = 1;
}

static inline void
refcount_fini(struct refcount *refcount)
{

	KASSERT(!refcount_referenced_p(refcount));
	refcount->rc_value = UINT_MAX;
}

static inline int
refcount_inc(struct refcount *refcount)
{
	unsigned old, new;

	do {
		old = refcount->rc_value;
		if (old == UINT_MAX)
			return EBUSY;
		KASSERT(0 < old);
		new = old + 1;
	} while (atomic_cas_uint(&refcount->rc_value, old, new) != old);

	return 0;
}

static inline bool
refcount_dec_local(struct refcount *refcount)
{
	unsigned old, new;

	do {
		old = refcount->rc_value;
		if (old == 1) {
			/*
			 * Avoid an atomic if we don't need it.  Caller
			 * guarantees that if the reference count is 1,
			 * nobody else can acquire new references.
			 */
			refcount->rc_value = 0;
			return true;
		}
		KASSERT(0 < old);
		new = old - 1;
	} while (atomic_cas_uint(&refcount->rc_value, old, new) != old);

	KASSERT(0 < new);
	return false;
}

static inline bool
refcount_dec_lock(struct refcount *refcount, kmutex_t *interlock)
{
	unsigned old, new;

	do {
		old = refcount->rc_value;
		KASSERT(0 < old);
		if (old == 1) {
			/*
			 * Transition from 1->0 is allowed only under
			 * the interlock.
			 */
			mutex_enter(interlock);
			new = atomic_dec_uint_nv(&refcount->rc_value);
			KASSERT(new != UINT_MAX);
			if (new == 0)
				return true;
			mutex_exit(interlock);
			return false;
		}
		new = old - 1;
	} while (atomic_cas_uint(&refcount->rc_value, old, new) != old);

	return false;
}

static inline void
refcount_dec_signal(struct refcount *refcount, kmutex_t *interlock,
    kcondvar_t *cv)
{

	if (refcount_dec_lock(refcount, interlock)) {
		cv_signal(cv);
		mutex_exit(interlock);
	}
}

static inline void
refcount_dec_broadcast(struct refcount *refcount, kmutex_t *interlock,
    kcondvar_t *cv)
{

	if (refcount_dec_lock(refcount, interlock)) {
		cv_broadcast(cv);
		mutex_exit(interlock);
	}
}

static inline void
refcount_dec_drain(struct refcount *refcount, kmutex_t *interlock,
    kcondvar_t *cv)
{

	ASSERT_SLEEPABLE();
	KASSERT(mutex_owned(interlock));

	if (0 < atomic_dec_uint_nv(&refcount->rc_value))
		do cv_wait(cv, interlock); while (0 < refcount->rc_value);
}

#endif	/* _SYS_REFCOUNT_H */

.\"	$NetBSD$
.\"
.\" Copyright (c) 2015 The NetBSD Foundation, Inc.
.\" All rights reserved.
.\"
.\" This code is derived from software contributed to The NetBSD Foundation
.\" by Taylor R. Campbell.
.\"
.\" Redistribution and use in source and binary forms, with or without
.\" modification, are permitted provided that the following conditions
.\" are met:
.\" 1. Redistributions of source code must retain the above copyright
.\"    notice, this list of conditions and the following disclaimer.
.\" 2. Redistributions in binary form must reproduce the above copyright
.\"    notice, this list of conditions and the following disclaimer in the
.\"    documentation and/or other materials provided with the distribution.
.\"
.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
.\" PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
.\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
.\" POSSIBILITY OF SUCH DAMAGE.
.\"
.Dd April 11, 2015
.Dt REFCOUNT 9
.Os
.Sh NAME
.Nm REFCOUNT
.Nd reference counting
.Sh SYNOPSIS
.In sys/refcount.h
.Ft void
.Fn refcount_init "struct refcount *refcount"
.Ft void
.Fn refcount_fini "struct refcount *refcount"
.Ft int
.Fn refcount_inc "struct refcount *refcount"
.Ft bool
.Fn refcount_dec_local "struct refcount *refcount"
.Ft bool
.Fn refcount_dec_lock "struct refcount *refcount" "kmutex_t *interlock"
.Ft void
.Fn refcount_dec_signal "struct refcount *refcount" "kmutex_t *interlock" \
        "kcondvar_t *cv"
.Ft void
.Fn refcount_dec_broadcast "struct refcount *refcount" "kmutex_t *interlock" \
        "kcondvar_t *cv"
.Ft void
.Fn refcount_dec_drain "struct refcount *refcount" "kmutex_t *interlock" \
        "kcondvar_t *cv"
.Sh DESCRIPTION
.Nm
is an abstraction for maintaining reference counts to objects that may
be shared between multiple threads.
Each object with a reference count should embed a
.Li "struct refcount" ,
which users should treat as opaque and should not inspect or copy.
The
.Li "struct refcount"
must be initialized with
.Fn refcount_init
before use, and finalized with
.Fn refcount_fini
when done.
When acquiring a reference to an object, use
.Fn refcount_inc ,
which increments its reference count.
When releasing a reference to an object, use one of the
.Fn refcount_dec_*
routines.
.Pp
The
.Nm
abstraction supports multiple approaches to freeing objects when they
are no longer referenced:
.Bl -dash
.It
The object's lifetime is ended by an explicit free operation, and the
reference count serves only to notify the free operation when the
object is no longer in use.
.Pp
Users of the object should use
.Fn refcount_dec_signal
or
.Fn refcount_dec_broadcast
to notify the free operation when they are done, and the free operation
should use
.Fn refcount_dec_drain
to wait until there are no users left.
.It
The object is stored in a global cache, and has no explicit free
operation -- its lifetime ends when the last user is done with it, at
which point it must be removed from the cache and freed.
.Pp
Each user of the object should use
.Fn refcount_dec_lock
when done, which returns true and enters a mutex if and only if that
user is the last one.
This allows the last user to safely remove the object from the global
cache without a window during which new references can be acquired.
.It
The object has no explicit free operation and is not stored in any
global tables.
.Pp
Each user of the object should use
.Fn refcount_dec_local
when done, which returns true if and only if that user is the last one,
who can then free the object.
.El
.Pp
The transition from nonzero to zero references is permanent.
It is also guaranteed to happen under an interlock excluding new
references whenever there is a possibility that one thread may acquire
a new reference at the same time another is releasing what would have
been the last one.
.Sh FUNCTIONS
.Bl -tag -width abcd
.It Fn refcount_init refcount
Initialize
.Fa refcount
for use with
.Nm .
.It Fn refcount_fini refcount
Finalize
.Fa refcount .
Further use with
.Nm
is not allowed.
.It Fn refcount_inc refcount
Try to increment
.Fa refcount .
If there are too many other references
.Pq Dv UINT_MAX ,
return
.Dv EBUSY .
Otherwise, return zero.
.It Fn refcount_dec_local refcount
Decrement
.Fa refcount .
If it drops to zero, return true.
Otherwise return false.
.Pp
This is useful
.Em only
when the object whose references are counted by
.Fa refcount
is not stored in any global tables or caches, so that, without
interlocks, if the reference count
.Em would
drop to zero, there is no way for other threads to acquire new
references.
.It Fn refcount_dec_lock refcount interlock
Decrement
.Fa refcount .
If it drops to zero, enter the mutex
.Fa interlock
and return true.
Otherwise return false.
.Pp
May enter
.Fa interlock
even if it returns false, in case another thread acquired a reference
at the same time.
.It Fn refcount_dec_signal refcount interlock cv
Decrement
.Fa refcount .
If it drops to zero, enter the mutex
.Fa interlock ,
signal
.Fa cv ,
and exit
.Fa interlock .
.Pp
May enter
.Fa interlock
even if it does not signal
.Fa cv ,
in case another thread acquired a reference at the same time.
.It Fn refcount_dec_broadcast refcount interlock cv
Decrement
.Fa refcount .
If it drops to zero, enter the mutex
.Fa interlock ,
broadcast
.Fa cv ,
and exit
.Fa interlock .
.Pp
May enter
.Fa interlock
even if it does not broadcast
.Fa cv ,
in case another thread acquired a reference at the same time.
.It Fn refcount_dec_drain refcount interlock cv
Decrement
.Fa refcount ,
and wait under
.Fa interlock
on
.Fa cv
until the reference count drops to zero.
.Pp
The caller must hold
.Fa interlock .
.Pp
May sleep.
.It Fn refcount_referenced_p refcount
Return true if the reference count of
.Fa refcount
is positive, false if zero.
.Pp
May be used only under
.Dv DIAGNOSTIC
for assertions.
Do not make run-time decisions on the basis of
.Fn refcount_referenced_p .
.It Fn refcount_exclusive_p refcount
Return true if caller's reference to
.Fa refcount
is exclusive -- that is, if the reference count of
.Fa refcount
is one.
Otherwise return false.
.Fa refcount
must be referenced: the reference count may not be zero.
.Pp
May be used only under
.Dv DIAGNOSTIC
for assertions.
Do not make run-time decisions on the basis of
.Fn refcount_exclusive_p .
.El
.Sh CODE REFERENCES
The
.Nm
abstraction is implemented in
.Pa sys/sys/refcount.h .
.Sh SEE ALSO
.Xr condvar 9 ,
.Xr mutex 9
.Sh BUGS
There are no examples in this man page.
.Pp
The implementation is untested.

Follow-Ups:
- Re: reference counts
  - From: Masao Uebayashi
- Re: reference counts
  - From: Paul Goyette

Prev by Date: Re: x86 MD MSI/MSI-X implementation
Next by Date: Re: reference counts
Previous by Thread: x86 MD MSI/MSI-X implementation
Next by Thread: Re: reference counts
Indexes:

Home | Main Index | Thread Index | Old Index