Module Name: src
Committed By: pgoyette
Date: Fri Jul 15 02:29:19 UTC 2016
Modified Files:
src/sys/kern [pgoyette-localcount]: files.kern
Added Files:
src/sys/kern [pgoyette-localcount]: subr_localcount.c
src/sys/sys [pgoyette-localcount]: localcount.h
Log Message:
Initial import of localcount(9) as proposed by riastradh@
This version compiles, but nothing uses it, yet.
To generate a diff of this commit:
cvs rdiff -u -r1.11 -r1.11.2.1 src/sys/kern/files.kern
cvs rdiff -u -r0 -r1.1.2.1 src/sys/kern/subr_localcount.c
cvs rdiff -u -r0 -r1.1.2.1 src/sys/sys/localcount.h
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/sys/kern/files.kern
diff -u src/sys/kern/files.kern:1.11 src/sys/kern/files.kern:1.11.2.1
--- src/sys/kern/files.kern:1.11 Sat Apr 9 06:21:16 2016
+++ src/sys/kern/files.kern Fri Jul 15 02:29:19 2016
@@ -1,4 +1,4 @@
-# $NetBSD: files.kern,v 1.11 2016/04/09 06:21:16 riastradh Exp $
+# $NetBSD: files.kern,v 1.11.2.1 2016/07/15 02:29:19 pgoyette Exp $
#
# kernel sources
@@ -113,6 +113,7 @@ file kern/subr_kcpuset.c kern
file kern/subr_kmem.c kern
file kern/subr_kobj.c kern
file kern/subr_kobj_vfs.c kern
+file kern/subr_localcount.c kern
file kern/subr_lockdebug.c kern
file kern/subr_log.c kern
file kern/subr_lwp_specificdata.c kern
Added files:
Index: src/sys/kern/subr_localcount.c
diff -u /dev/null src/sys/kern/subr_localcount.c:1.1.2.1
--- /dev/null Fri Jul 15 02:29:19 2016
+++ src/sys/kern/subr_localcount.c Fri Jul 15 02:29:19 2016
@@ -0,0 +1,248 @@
+/* $NetBSD: subr_localcount.c,v 1.1.2.1 2016/07/15 02:29:19 pgoyette Exp $ */
+
+/*-
+ * Copyright (c) 2016 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.
+ */
+
+/*
+ * CPU-local reference counts
+ *
+ * localcount(9) is a reference-counting scheme that involves no
+ * interprocessor synchronization most of the time, at the cost of
+ * eight bytes of memory per CPU per object and at the cost of
+ * expensive interprocessor synchronization to drain references.
+ *
+ * localcount(9) references may be held across sleeps, may be
+ * transferred from CPU to CPU or thread to thread: they behave
+ * semantically like typical reference counts, with different
+ * pragmatic performance characteristics.
+ */
+
+#include <sys/cdefs.h>
+__KERNEL_RCSID(0, "$NetBSD: subr_localcount.c,v 1.1.2.1 2016/07/15 02:29:19 pgoyette Exp $");
+
+#include <sys/param.h>
+#include <sys/localcount.h>
+#include <sys/types.h>
+#include <sys/condvar.h>
+#include <sys/errno.h>
+#include <sys/mutex.h>
+#include <sys/percpu.h>
+#include <sys/xcall.h>
+
+/*
+ * localcount_init(lc)
+ *
+ * Initialize a localcount object. Returns 0 on success, error
+ * code on failure. May fail to allocate memory for percpu(9).
+ *
+ * The caller must call localcount_drain and then localcount_fini
+ * when done with lc.
+ */
+static void localcount_xc(void *, void *);
+
+int
+localcount_init(struct localcount *lc)
+{
+
+ lc->lc_totalp = NULL;
+ lc->lc_percpu = percpu_alloc(sizeof(int64_t));
+ if (lc->lc_percpu == NULL)
+ return ENOMEM;
+
+ return 0;
+}
+
+/*
+ * localcount_drain(lc, cv, interlock)
+ *
+ * Wait for all acquired references to lc to drain. Caller must
+ * hold interlock; localcount_drain releases it during cross-calls
+ * and waits on cv. The cv and interlock passed here must be the
+ * same as are passed to localcount_release for this lc.
+ *
+ * Caller must guarantee that no new references can be acquired
+ * with localcount_acquire before calling localcount_drain. For
+ * example, any object that may be found in a list and acquired
+ * must be removed from the list before localcount_drain.
+ *
+ * The localcount object lc may be used only with localcount_fini
+ * after this, unless reinitialized after localcount_fini with
+ * localcount_init.
+ */
+void
+localcount_drain(struct localcount *lc, kcondvar_t *cv, kmutex_t *interlock)
+{
+ int64_t total = 0;
+
+ KASSERT(mutex_owned(interlock));
+ KASSERT(lc->lc_totalp == NULL);
+
+ /* Mark it draining. */
+ lc->lc_totalp = &total;
+
+ /*
+ * Count up all references on all CPUs.
+ *
+ * This serves as a global memory barrier: after xc_wait, all
+ * CPUs will have witnessed the nonnull value of lc->lc_totalp,
+ * so that it is safe to wait on the cv for them.
+ */
+ mutex_exit(interlock);
+ xc_wait(xc_broadcast(0, &localcount_xc, lc, interlock));
+ mutex_enter(interlock);
+
+ /* Wait for remaining references to drain. */
+ while (total != 0) {
+ /*
+ * At this point, now that we have added up all
+ * references on all CPUs, the total had better be
+ * nonnegative.
+ */
+ KASSERTMSG((0 < total),
+ "negatively referenced localcount: %p, %"PRId64,
+ lc, total);
+ cv_wait(cv, interlock);
+ }
+
+ /* Paranoia: Cause any further use of lc->lc_totalp to crash. */
+ lc->lc_totalp = (void *)(uintptr_t)1;
+}
+
+/*
+ * localcount_fini(lc)
+ *
+ * Finalize a localcount object, releasing any memory allocated
+ * for it. Caller must have already called localcount_drain.
+ */
+void
+localcount_fini(struct localcount *lc)
+{
+
+ KASSERT(lc->lc_totalp == (void *)(uintptr_t)1);
+ percpu_free(lc->lc_percpu, sizeof(uint64_t));
+}
+
+static void
+localcount_xc(void *cookie0, void *cookie1)
+{
+ struct localcount *lc = cookie0;
+ kmutex_t *interlock = cookie1;
+ int64_t *localp;
+
+ mutex_enter(interlock);
+ localp = percpu_getref(lc->lc_percpu);
+ *lc->lc_totalp += *localp;
+ percpu_putref(lc->lc_percpu);
+ mutex_exit(interlock);
+}
+
+static void
+localcount_adjust(struct localcount *lc, int delta)
+{
+ int64_t *localp;
+
+ localp = percpu_getref(lc->lc_percpu);
+ *localp += delta;
+ percpu_putref(lc->lc_percpu);
+}
+
+/*
+ * localcount_acquire(lc)
+ *
+ * Acquire a reference to lc.
+ *
+ * The reference may be held across sleeps and may be migrated
+ * from CPU to CPU, or even thread to thread -- it is only
+ * counted, not associated with a particular concrete owner.
+ *
+ * Involves no interprocessor synchronization. May be used in any
+ * context: while a lock is held, within a pserialize(9) read
+ * section, in hard interrupt context (provided other users block
+ * hard interrupts), in soft interrupt context, in thread context,
+ * &c.
+ *
+ * Caller must guarantee that there is no concurrent
+ * localcount_drain. For example, any object that may be found in
+ * a list and acquired must be removed from the list before
+ * localcount_drain.
+ */
+void
+localcount_acquire(struct localcount *lc)
+{
+
+ KASSERT(lc->lc_totalp == NULL);
+ localcount_adjust(lc, +1);
+}
+
+/*
+ * localcount_release(lc, cv, interlock)
+ *
+ * Release a reference to lc. If there is a concurrent
+ * localcount_drain and this may be the last reference, notify
+ * localcount_drain by acquiring interlock, waking cv, and
+ * releasing interlock. The cv and interlock passed here must be
+ * the same as are passed to localcount_drain for this lc.
+ *
+ * Involves no interprocessor synchronization unless there is a
+ * concurrent localcount_drain in progress.
+ */
+void
+localcount_release(struct localcount *lc, kcondvar_t *cv, kmutex_t *interlock)
+{
+ int s;
+
+ /*
+ * Block xcall so that if someone begins draining after we see
+ * lc->lc_totalp as null, then they won't start cv_wait until
+ * after they have counted this CPU's contributions.
+ *
+ * Otherwise, localcount_drain may notice an extant reference
+ * from this CPU and cv_wait for it, but having seen
+ * lc->lc_totalp as null, this CPU will not wake
+ * localcount_drain.
+ */
+ s = splsoftserial();
+
+ if (__predict_false(lc->lc_totalp != NULL)) {
+ /*
+ * Slow path -- wake localcount_drain in case this is
+ * the last reference.
+ */
+ mutex_enter(interlock);
+ localcount_adjust(lc, -1);
+ *lc->lc_totalp -= 1;
+ if (*lc->lc_totalp == 0)
+ cv_broadcast(cv);
+ mutex_exit(interlock);
+ goto out;
+ }
+
+ localcount_adjust(lc, -1);
+out: splx(s);
+}
Index: src/sys/sys/localcount.h
diff -u /dev/null src/sys/sys/localcount.h:1.1.2.1
--- /dev/null Fri Jul 15 02:29:19 2016
+++ src/sys/sys/localcount.h Fri Jul 15 02:29:19 2016
@@ -0,0 +1,58 @@
+/* $NetBSD: localcount.h,v 1.1.2.1 2016/07/15 02:29:19 pgoyette Exp $ */
+
+/*-
+ * Copyright (c) 2016 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_LOCALCOUNT_H
+#define _SYS_LOCALCOUNT_H
+
+#ifndef _KERNEL
+#error <sys/localcount.h> is for kernel consumers only.
+#endif
+
+#include <sys/types.h>
+
+struct kcondvar;
+struct kmutex;
+struct percpu;
+
+struct localcount {
+ int64_t *lc_totalp;
+ struct percpu *lc_percpu; /* int64_t */
+};
+
+int localcount_init(struct localcount *);
+void localcount_drain(struct localcount *, struct kcondvar *,
+ struct kmutex *);
+void localcount_fini(struct localcount *);
+void localcount_acquire(struct localcount *);
+void localcount_release(struct localcount *, struct kcondvar *,
+ struct kmutex *);
+
+#endif /* _SYS_LOCALCOUNT_H */
