From owner-svn-src-head@freebsd.org Thu May 10 17:55:28 2018 Return-Path: Delivered-To: svn-src-head@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 50EA9FD1E80; Thu, 10 May 2018 17:55:28 +0000 (UTC) (envelope-from mmacy@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client CN "mxrelay.nyi.freebsd.org", Issuer "Let's Encrypt Authority X3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id F1A18755D8; Thu, 10 May 2018 17:55:27 +0000 (UTC) (envelope-from mmacy@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id D27ED23C16; Thu, 10 May 2018 17:55:27 +0000 (UTC) (envelope-from mmacy@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id w4AHtR6M028912; Thu, 10 May 2018 17:55:27 GMT (envelope-from mmacy@FreeBSD.org) Received: (from mmacy@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id w4AHtPRt028900; Thu, 10 May 2018 17:55:25 GMT (envelope-from mmacy@FreeBSD.org) Message-Id: <201805101755.w4AHtPRt028900@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: mmacy set sender to mmacy@FreeBSD.org using -f From: Matt Macy Date: Thu, 10 May 2018 17:55:25 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r333466 - in head: contrib/bmake sys/conf sys/kern sys/modules/epoch_test sys/sys sys/tests/epoch X-SVN-Group: head X-SVN-Commit-Author: mmacy X-SVN-Commit-Paths: in head: contrib/bmake sys/conf sys/kern sys/modules/epoch_test sys/sys sys/tests/epoch X-SVN-Commit-Revision: 333466 X-SVN-Commit-Repository: base MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-head@freebsd.org X-Mailman-Version: 2.1.25 Precedence: list List-Id: SVN commit messages for the src tree for head/-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 10 May 2018 17:55:28 -0000 Author: mmacy Date: Thu May 10 17:55:24 2018 New Revision: 333466 URL: https://svnweb.freebsd.org/changeset/base/333466 Log: Add simple preempt safe epoch API Read locking is over used in the kernel to guarantee liveness. This API makes it easy to provide livenes guarantees without atomics. Includes epoch_test kernel module to stress test the API. Documentation will follow initial use case. Test case and improvements to preemption handling in response to discussion with mjg@ Reviewed by: imp@, shurd@ Approved by: sbruno@ Added: head/sys/kern/subr_epoch.c (contents, props changed) head/sys/modules/epoch_test/ head/sys/modules/epoch_test/Makefile (contents, props changed) head/sys/sys/epoch.h (contents, props changed) head/sys/tests/epoch/ head/sys/tests/epoch/epoch_test.c (contents, props changed) Modified: head/contrib/bmake/job.c head/sys/conf/files head/sys/conf/kern.pre.mk head/sys/kern/kern_malloc.c head/sys/kern/kern_synch.c head/sys/kern/subr_trap.c head/sys/kern/subr_turnstile.c head/sys/sys/proc.h head/sys/sys/turnstile.h Modified: head/contrib/bmake/job.c ============================================================================== --- head/contrib/bmake/job.c Thu May 10 17:22:04 2018 (r333465) +++ head/contrib/bmake/job.c Thu May 10 17:55:24 2018 (r333466) @@ -2121,13 +2121,15 @@ Job_CatchOutput(void) { int nready; Job *job; - int i; + int i, pollToken; (void)fflush(stdout); + pollToken = 0; + /* The first fd in the list is the job token pipe */ do { - nready = poll(fds + 1 - wantToken, nfds - 1 + wantToken, POLL_MSEC); + nready = poll(fds + 1 - pollToken, nfds - 1 + pollToken, POLL_MSEC); } while (nready < 0 && errno == EINTR); if (nready < 0) Modified: head/sys/conf/files ============================================================================== --- head/sys/conf/files Thu May 10 17:22:04 2018 (r333465) +++ head/sys/conf/files Thu May 10 17:55:24 2018 (r333466) @@ -3891,6 +3891,7 @@ kern/subr_compressor.c standard \ kern/subr_counter.c standard kern/subr_devstat.c standard kern/subr_disk.c standard +kern/subr_epoch.c standard kern/subr_eventhandler.c standard kern/subr_fattime.c standard kern/subr_firmware.c optional firmware Modified: head/sys/conf/kern.pre.mk ============================================================================== --- head/sys/conf/kern.pre.mk Thu May 10 17:22:04 2018 (r333465) +++ head/sys/conf/kern.pre.mk Thu May 10 17:55:24 2018 (r333466) @@ -77,7 +77,7 @@ COPTFLAGS+= ${_CPUCFLAGS} .endif NOSTDINC= -nostdinc -INCLUDES= ${NOSTDINC} ${INCLMAGIC} -I. -I$S +INCLUDES= ${NOSTDINC} ${INCLMAGIC} -I. -I$S -I$S/contrib/ck/include CFLAGS= ${COPTFLAGS} ${DEBUG} CFLAGS+= ${INCLUDES} -D_KERNEL -DHAVE_KERNEL_OPTION_HEADERS -include opt_global.h Modified: head/sys/kern/kern_malloc.c ============================================================================== --- head/sys/kern/kern_malloc.c Thu May 10 17:22:04 2018 (r333465) +++ head/sys/kern/kern_malloc.c Thu May 10 17:55:24 2018 (r333466) @@ -514,9 +514,12 @@ malloc_dbg(caddr_t *vap, size_t *sizep, struct malloc_ } } #endif - if (flags & M_WAITOK) + if (flags & M_WAITOK) { KASSERT(curthread->td_intr_nesting_level == 0, ("malloc(M_WAITOK) in interrupt context")); + KASSERT(curthread->td_epochnest == 0, + ("malloc(M_WAITOK) in epoch context")); + } KASSERT(curthread->td_critnest == 0 || SCHEDULER_STOPPED(), ("malloc: called with spinlock or critical section held")); Modified: head/sys/kern/kern_synch.c ============================================================================== --- head/sys/kern/kern_synch.c Thu May 10 17:22:04 2018 (r333465) +++ head/sys/kern/kern_synch.c Thu May 10 17:55:24 2018 (r333466) @@ -147,6 +147,7 @@ _sleep(void *ident, struct lock_object *lock, int prio ("sleeping without a lock")); KASSERT(ident != NULL, ("_sleep: NULL ident")); KASSERT(TD_IS_RUNNING(td), ("_sleep: curthread not running")); + KASSERT(td->td_epochnest == 0, ("sleeping in an epoch section")); if (priority & PDROP) KASSERT(lock != NULL && lock != &Giant.lock_object, ("PDROP requires a non-Giant lock")); Added: head/sys/kern/subr_epoch.c ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/sys/kern/subr_epoch.c Thu May 10 17:55:24 2018 (r333466) @@ -0,0 +1,508 @@ +/*- + * Copyright (c) 2018, Matthew Macy + * + * 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. Neither the name of Matthew Macy nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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 COPYRIGHT OWNER 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. + */ + +#include +__FBSDID("$FreeBSD$"); + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include + +MALLOC_DEFINE(M_EPOCH, "epoch", "epoch based reclamation"); + +/* arbitrary --- needs benchmarking */ +#define MAX_ADAPTIVE_SPIN 5000 + +SYSCTL_NODE(_kern, OID_AUTO, epoch, CTLFLAG_RW, 0, "epoch information"); +SYSCTL_NODE(_kern_epoch, OID_AUTO, stats, CTLFLAG_RW, 0, "epoch stats"); + +/* Stats. */ +static counter_u64_t block_count; +SYSCTL_COUNTER_U64(_kern_epoch_stats, OID_AUTO, nblocked, CTLFLAG_RW, + &block_count, "# of times a thread was in an epoch when epoch_wait was called"); +static counter_u64_t migrate_count; +SYSCTL_COUNTER_U64(_kern_epoch_stats, OID_AUTO, migrations, CTLFLAG_RW, + &migrate_count, "# of times thread was migrated to another CPU in epoch_wait"); +static counter_u64_t turnstile_count; +SYSCTL_COUNTER_U64(_kern_epoch_stats, OID_AUTO, ncontended, CTLFLAG_RW, + &turnstile_count, "# of times a thread was blocked on a lock in an epoch during an epoch_wait"); +static counter_u64_t switch_count; +SYSCTL_COUNTER_U64(_kern_epoch_stats, OID_AUTO, switches, CTLFLAG_RW, + &switch_count, "# of times a thread voluntarily context switched in epoch_wait"); + +typedef struct epoch_cb { + void (*ec_callback)(epoch_context_t); + STAILQ_ENTRY(epoch_cb) ec_link; +} *epoch_cb_t; + +TAILQ_HEAD(threadlist, thread); + +typedef struct epoch_record { + ck_epoch_record_t er_record; + volatile struct threadlist er_tdlist; + uint32_t er_cpuid; +} *epoch_record_t; + +struct epoch_pcpu_state { + struct epoch_record eps_record; + volatile int eps_waiters; +} __aligned(CACHE_LINE_SIZE); + +struct epoch { + struct ck_epoch e_epoch; + struct mtx e_lock; + struct grouptask e_gtask; + STAILQ_HEAD(, epoch_cb) e_cblist; + struct epoch_pcpu_state *e_pcpu_dom[MAXMEMDOM]; + struct epoch_pcpu_state *e_pcpu[0]; +}; + +static __read_mostly int domcount[MAXMEMDOM]; +static __read_mostly int domoffsets[MAXMEMDOM]; +static __read_mostly int inited; + +static void epoch_call_task(void *context); +static bool usedomains = true; + +static void +epoch_init(void *arg __unused) +{ + int domain, count; + + count = domain = 0; + domoffsets[0] = 0; + for (domain = 0; domain < vm_ndomains; domain++) { + domcount[domain] = CPU_COUNT(&cpuset_domain[domain]); + if (bootverbose) + printf("domcount[%d] %d\n", domain, domcount[domain]); + } + for (domain = 1; domain < vm_ndomains; domain++) + domoffsets[domain] = domoffsets[domain-1] + domcount[domain-1]; + + for (domain = 0; domain < vm_ndomains; domain++) { + if (domcount[domain] == 0) { + usedomains = false; + break; + } + } + + block_count = counter_u64_alloc(M_WAITOK); + migrate_count = counter_u64_alloc(M_WAITOK); + turnstile_count = counter_u64_alloc(M_WAITOK); + switch_count = counter_u64_alloc(M_WAITOK); + inited = 1; +} +SYSINIT(epoch, SI_SUB_CPU + 1, SI_ORDER_FIRST, epoch_init, NULL); + +static void +epoch_init_numa(epoch_t epoch) +{ + int domain, cpu_offset; + struct epoch_pcpu_state *eps; + epoch_record_t er; + + for (domain = 0; domain < vm_ndomains; domain++) { + eps = malloc_domain(sizeof(*eps)*domcount[domain], M_EPOCH, + domain, M_ZERO|M_WAITOK); + epoch->e_pcpu_dom[domain] = eps; + cpu_offset = domoffsets[domain]; + for (int i = 0; i < domcount[domain]; i++, eps++) { + epoch->e_pcpu[cpu_offset + i] = eps; + er = &eps->eps_record; + ck_epoch_register(&epoch->e_epoch, &er->er_record, NULL); + TAILQ_INIT((struct threadlist *)(uintptr_t)&er->er_tdlist); + er->er_cpuid = cpu_offset + i; + } + } +} + +static void +epoch_init_legacy(epoch_t epoch) +{ + struct epoch_pcpu_state *eps; + epoch_record_t er; + + eps = malloc(sizeof(*eps)*mp_ncpus, M_EPOCH, M_ZERO|M_WAITOK); + epoch->e_pcpu_dom[0] = eps; + for (int i = 0; i < mp_ncpus; i++, eps++) { + epoch->e_pcpu[i] = eps; + er = &eps->eps_record; + ck_epoch_register(&epoch->e_epoch, &er->er_record, NULL); + TAILQ_INIT((struct threadlist *)(uintptr_t)&er->er_tdlist); + er->er_cpuid = i; + } +} + +epoch_t +epoch_alloc(void) +{ + epoch_t epoch; + + if (__predict_false(!inited)) + panic("%s called too early in boot", __func__); + epoch = malloc(sizeof(struct epoch) + mp_ncpus*sizeof(void*), + M_EPOCH, M_ZERO|M_WAITOK); + ck_epoch_init(&epoch->e_epoch); + mtx_init(&epoch->e_lock, "epoch cblist", NULL, MTX_DEF); + STAILQ_INIT(&epoch->e_cblist); + taskqgroup_config_gtask_init(epoch, &epoch->e_gtask, epoch_call_task, "epoch call task"); + if (usedomains) + epoch_init_numa(epoch); + else + epoch_init_legacy(epoch); + return (epoch); +} + +void +epoch_free(epoch_t epoch) +{ + int domain; +#ifdef INVARIANTS + struct epoch_pcpu_state *eps; + int cpu; + + CPU_FOREACH(cpu) { + eps = epoch->e_pcpu[cpu]; + MPASS(TAILQ_EMPTY(&eps->eps_record.er_tdlist)); + } +#endif + mtx_destroy(&epoch->e_lock); + taskqgroup_config_gtask_deinit(&epoch->e_gtask); + if (usedomains) + for (domain = 0; domain < vm_ndomains; domain++) + free_domain(epoch->e_pcpu_dom[domain], M_EPOCH); + else + free(epoch->e_pcpu_dom[0], M_EPOCH); + free(epoch, M_EPOCH); +} + +#define INIT_CHECK(epoch) \ + do { \ + if (__predict_false((epoch) == NULL)) \ + return; \ + } while (0) + +void +epoch_enter(epoch_t epoch) +{ + struct epoch_pcpu_state *eps; + struct thread *td; + + INIT_CHECK(epoch); + + td = curthread; + critical_enter(); + eps = epoch->e_pcpu[curcpu]; + td->td_epochnest++; + MPASS(td->td_epochnest < UCHAR_MAX - 2); + if (td->td_epochnest == 1) + TAILQ_INSERT_TAIL(&eps->eps_record.er_tdlist, td, td_epochq); +#ifdef INVARIANTS + if (td->td_epochnest > 1) { + struct thread *curtd; + int found = 0; + + TAILQ_FOREACH(curtd, &eps->eps_record.er_tdlist, td_epochq) + if (curtd == td) + found = 1; + KASSERT(found, ("recursing on a second epoch")); + } +#endif + sched_pin(); + ck_epoch_begin(&eps->eps_record.er_record, NULL); + critical_exit(); +} + +void +epoch_enter_nopreempt(epoch_t epoch) +{ + struct epoch_pcpu_state *eps; + + INIT_CHECK(epoch); + critical_enter(); + eps = epoch->e_pcpu[curcpu]; + curthread->td_epochnest++; + MPASS(curthread->td_epochnest < UCHAR_MAX - 2); + ck_epoch_begin(&eps->eps_record.er_record, NULL); +} + +void +epoch_exit(epoch_t epoch) +{ + struct epoch_pcpu_state *eps; + struct thread *td; + + td = curthread; + INIT_CHECK(epoch); + critical_enter(); + eps = epoch->e_pcpu[curcpu]; + sched_unpin(); + ck_epoch_end(&eps->eps_record.er_record, NULL); + td->td_epochnest--; + if (td->td_epochnest == 0) + TAILQ_REMOVE(&eps->eps_record.er_tdlist, td, td_epochq); + critical_exit(); +} + +void +epoch_exit_nopreempt(epoch_t epoch) +{ + struct epoch_pcpu_state *eps; + + INIT_CHECK(epoch); + MPASS(curthread->td_critnest); + eps = epoch->e_pcpu[curcpu]; + ck_epoch_end(&eps->eps_record.er_record, NULL); + curthread->td_epochnest--; + critical_exit(); +} + +/* + * epoch_block_handler is a callback from the ck code when another thread is + * currently in an epoch section. + */ +static void +epoch_block_handler(struct ck_epoch *global __unused, ck_epoch_record_t *cr, + void *arg __unused) +{ + epoch_record_t record; + struct epoch_pcpu_state *eps; + struct thread *td, *tdwait, *owner; + struct turnstile *ts; + struct lock_object *lock; + u_char prio; + int spincount; + + eps = arg; + record = __containerof(cr, struct epoch_record, er_record); + td = curthread; + spincount = 0; + counter_u64_add(block_count, 1); + if (record->er_cpuid != curcpu) { + /* + * If the head of the list is running, we can wait for it + * to remove itself from the list and thus save us the + * overhead of a migration + */ + if ((tdwait = TAILQ_FIRST(&record->er_tdlist)) != NULL && + TD_IS_RUNNING(tdwait)) { + while (tdwait == TAILQ_FIRST(&record->er_tdlist) && + TD_IS_RUNNING(tdwait) && spincount++ < MAX_ADAPTIVE_SPIN) { + cpu_spinwait(); + } + return; + } + + /* + * Being on the same CPU as that of the record on which + * we need to wait allows us access to the thread + * list associated with that CPU. We can then examine the + * oldest thread in the queue and wait on its turnstile + * until it resumes and so on until a grace period + * elapses. + * + */ + counter_u64_add(migrate_count, 1); + sched_bind(td, record->er_cpuid); + /* + * At this point we need to return to the ck code + * to scan to see if a grace period has elapsed. + * We can't move on to check the thread list, because + * in the meantime new threads may have arrived that + * in fact belong to a different epoch. + */ + return; + } + /* + * Try to find a thread in an epoch section on this CPU + * waiting on a turnstile. Otherwise find the lowest + * priority thread (highest prio value) and drop our priority + * to match to allow it to run. + */ + prio = 0; + TAILQ_FOREACH(tdwait, &record->er_tdlist, td_epochq) { + if (td->td_priority > prio) + prio = td->td_priority; + if (TD_IS_INHIBITED(tdwait) && TD_ON_LOCK(tdwait) && + ((ts = tdwait->td_blocked) != NULL)) { + /* + * We unlock td to allow turnstile_wait to reacquire the + * the thread lock. Before unlocking it we enter a critical + * section to prevent preemption after we reenable interrupts + * by dropping the thread lock in order to prevent tdwait + * from getting to run. + */ + critical_enter(); + thread_unlock(td); + owner = turnstile_lock(ts, &lock); + /* + * The owner pointer indicates that the lock succeeded. Only + * in case we hold the lock and the turnstile we locked is still + * the one that tdwait is blocked on can we continue. Otherwise + * The turnstile pointer has been changed out from underneath + * us, as in the case where the lock holder has signalled tdwait, + * and we need to continue. + */ + if (owner != NULL && ts == tdwait->td_blocked) { + MPASS(TD_IS_INHIBITED(tdwait) && TD_ON_LOCK(tdwait)); + critical_exit(); + turnstile_wait(ts, owner, tdwait->td_tsqueue); + counter_u64_add(turnstile_count, 1); + thread_lock(td); + return; + } else if (owner != NULL) + turnstile_unlock(ts, lock); + thread_lock(td); + critical_exit(); + KASSERT(td->td_locks == 0, + ("%d locks held", td->td_locks)); + } + } + /* + * We didn't find any threads actually blocked on a lock + * we have nothing to do except set our priority to match + * that of the lowest value on the queue and context switch + * away. + */ + counter_u64_add(switch_count, 1); + sched_prio(td, prio); + mi_switch(SW_VOL | SWT_RELINQUISH, NULL); + + /* + * Release the thread lock while yielding to + * allow other threads to acquire the lock + * pointed to by TDQ_LOCKPTR(td). Else a + * deadlock like situation might happen. (HPS) + */ + thread_unlock(td); + thread_lock(td); +} + +void +epoch_wait(epoch_t epoch) +{ + struct thread *td; + int was_bound; + int old_cpu; + int old_pinned; + u_char old_prio; + + INIT_CHECK(epoch); + + WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, + "epoch_wait() can sleep"); + + td = curthread; + KASSERT(td->td_epochnest == 0, ("epoch_wait() in the middle of an epoch section")); + thread_lock(td); + + DROP_GIANT(); + + old_cpu = PCPU_GET(cpuid); + old_pinned = td->td_pinned; + old_prio = td->td_priority; + was_bound = sched_is_bound(td); + sched_unbind(td); + td->td_pinned = 0; + sched_bind(td, old_cpu); + + ck_epoch_synchronize_wait(&epoch->e_epoch, epoch_block_handler, NULL); + + /* restore CPU binding, if any */ + if (was_bound != 0) { + sched_bind(td, old_cpu); + } else { + /* get thread back to initial CPU, if any */ + if (old_pinned != 0) + sched_bind(td, old_cpu); + sched_unbind(td); + } + /* restore pinned after bind */ + td->td_pinned = old_pinned; + + /* restore thread priority */ + sched_prio(td, old_prio); + thread_unlock(td); + + PICKUP_GIANT(); +} + +void +epoch_call(epoch_t epoch, epoch_context_t ctx, void (*callback) (epoch_context_t)) +{ + epoch_cb_t cb; + + cb = (void *)ctx; + cb->ec_callback = callback; + mtx_lock(&epoch->e_lock); + STAILQ_INSERT_TAIL(&epoch->e_cblist, cb, ec_link); + GROUPTASK_ENQUEUE(&epoch->e_gtask); + mtx_unlock(&epoch->e_lock); +} + +static void +epoch_call_task(void *context) +{ + epoch_t epoch; + epoch_cb_t cb; + STAILQ_HEAD(, epoch_cb) tmp_head; + + epoch = context; + STAILQ_INIT(&tmp_head); + + mtx_lock(&epoch->e_lock); + STAILQ_CONCAT(&tmp_head, &epoch->e_cblist); + mtx_unlock(&epoch->e_lock); + + epoch_wait(epoch); + + while ((cb = STAILQ_FIRST(&tmp_head)) != NULL) + cb->ec_callback((void*)cb); +} + +int +in_epoch(void) +{ + return (curthread->td_epochnest != 0); +} Modified: head/sys/kern/subr_trap.c ============================================================================== --- head/sys/kern/subr_trap.c Thu May 10 17:22:04 2018 (r333465) +++ head/sys/kern/subr_trap.c Thu May 10 17:55:24 2018 (r333466) @@ -161,6 +161,8 @@ userret(struct thread *td, struct trapframe *frame) WITNESS_WARN(WARN_PANIC, NULL, "userret: returning"); KASSERT(td->td_critnest == 0, ("userret: Returning in a critical section")); + KASSERT(td->td_epochnest == 0, + ("userret: Returning in an epoch section")); KASSERT(td->td_locks == 0, ("userret: Returning with %d locks held", td->td_locks)); KASSERT(td->td_rw_rlocks == 0, Modified: head/sys/kern/subr_turnstile.c ============================================================================== --- head/sys/kern/subr_turnstile.c Thu May 10 17:22:04 2018 (r333465) +++ head/sys/kern/subr_turnstile.c Thu May 10 17:55:24 2018 (r333466) @@ -566,6 +566,45 @@ turnstile_trywait(struct lock_object *lock) return (ts); } +struct thread * +turnstile_lock(struct turnstile *ts, struct lock_object **lockp) +{ + struct turnstile_chain *tc; + struct lock_object *lock; + + if ((lock = ts->ts_lockobj) == NULL) + return (NULL); + tc = TC_LOOKUP(lock); + mtx_lock_spin(&tc->tc_lock); + mtx_lock_spin(&ts->ts_lock); + if (__predict_false(lock != ts->ts_lockobj)) { + mtx_unlock_spin(&tc->tc_lock); + mtx_unlock_spin(&ts->ts_lock); + return (NULL); + } + *lockp = lock; + return (ts->ts_owner); +} + +void +turnstile_unlock(struct turnstile *ts, struct lock_object *lock) +{ + struct turnstile_chain *tc; + + mtx_assert(&ts->ts_lock, MA_OWNED); + mtx_unlock_spin(&ts->ts_lock); + if (ts == curthread->td_turnstile) + ts->ts_lockobj = NULL; + tc = TC_LOOKUP(lock); + mtx_unlock_spin(&tc->tc_lock); +} + +void +turnstile_assert(struct turnstile *ts) +{ + MPASS(ts->ts_lockobj == NULL); +} + void turnstile_cancel(struct turnstile *ts) { Added: head/sys/modules/epoch_test/Makefile ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/sys/modules/epoch_test/Makefile Thu May 10 17:55:24 2018 (r333466) @@ -0,0 +1,7 @@ +# $FreeBSD$ + +.PATH: ${SRCTOP}/sys/tests/epoch +KMOD= epoch_test +SRCS= epoch_test.c + +.include Added: head/sys/sys/epoch.h ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/sys/sys/epoch.h Thu May 10 17:55:24 2018 (r333466) @@ -0,0 +1,51 @@ +/*- + * Copyright (c) 2018, Matthew Macy + * + * 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. Neither the name of Matthew Macy nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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 COPYRIGHT OWNER 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. + * + * $FreeBSD$ + */ + +#ifndef _SYS_EPOCH_H_ +#define _SYS_EPOCH_H_ + +struct epoch; +typedef struct epoch *epoch_t; + +struct epoch_context { + void *data[2]; +} __aligned(sizeof(void *)); + +typedef struct epoch_context *epoch_context_t; + +epoch_t epoch_alloc(void); +void epoch_free(epoch_t epoch); +void epoch_enter(epoch_t epoch); +void epoch_exit(epoch_t epoch); +void epoch_enter_nopreempt(epoch_t epoch); +void epoch_exit_nopreempt(epoch_t epoch); +void epoch_wait(epoch_t epoch); +void epoch_call(epoch_t epoch, epoch_context_t ctx, void (*callback) (epoch_context_t)); +int in_epoch(void); + +#endif Modified: head/sys/sys/proc.h ============================================================================== --- head/sys/sys/proc.h Thu May 10 17:22:04 2018 (r333465) +++ head/sys/sys/proc.h Thu May 10 17:55:24 2018 (r333466) @@ -243,6 +243,7 @@ struct thread { /* Cleared during fork1() */ #define td_startzero td_flags + u_char td_epochnest; /* (k) Private thread epoch nest counter */ int td_flags; /* (t) TDF_* flags. */ int td_inhibitors; /* (t) Why can not run. */ int td_pflags; /* (k) Private thread (TDP_*) flags. */ @@ -355,6 +356,7 @@ struct thread { int td_lastcpu; /* (t) Last cpu we were on. */ int td_oncpu; /* (t) Which cpu we are on. */ void *td_lkpi_task; /* LinuxKPI task struct pointer */ + TAILQ_ENTRY(thread) td_epochq; /* (t) Epoch queue. */ }; struct thread0_storage { Modified: head/sys/sys/turnstile.h ============================================================================== --- head/sys/sys/turnstile.h Thu May 10 17:22:04 2018 (r333465) +++ head/sys/sys/turnstile.h Thu May 10 17:55:24 2018 (r333466) @@ -104,6 +104,8 @@ int turnstile_signal(struct turnstile *, int); struct turnstile *turnstile_trywait(struct lock_object *); void turnstile_unpend(struct turnstile *, int); void turnstile_wait(struct turnstile *, struct thread *, int); - +struct thread *turnstile_lock(struct turnstile *, struct lock_object **); +void turnstile_unlock(struct turnstile *, struct lock_object *); +void turnstile_assert(struct turnstile *); #endif /* _KERNEL */ #endif /* _SYS_TURNSTILE_H_ */ Added: head/sys/tests/epoch/epoch_test.c ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/sys/tests/epoch/epoch_test.c Thu May 10 17:55:24 2018 (r333466) @@ -0,0 +1,211 @@ +/*- + * Copyright (c) 2018, Matthew Macy + * + * 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. Neither the name of Matthew Macy nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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 COPYRIGHT OWNER 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. + */ + +#include +__FBSDID("$FreeBSD$"); + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + + +struct epoch_test_instance { + int threadid; +}; + +static int inited; +static int iterations; +#define ET_EXITING 0x1 +static volatile int state_flags; +static struct mtx state_mtx __aligned(CACHE_LINE_SIZE*2); +MTX_SYSINIT(state_mtx, &state_mtx, "epoch state mutex", MTX_DEF); +static struct mtx mutexA __aligned(CACHE_LINE_SIZE*2); +MTX_SYSINIT(mutexA, &mutexA, "epoch mutexA", MTX_DEF); +static struct mtx mutexB __aligned(CACHE_LINE_SIZE*2); +MTX_SYSINIT(mutexB, &mutexB, "epoch mutexB", MTX_DEF); +epoch_t test_epoch; + +static void +epoch_testcase1(struct epoch_test_instance *eti) +{ + int i, startticks; + struct mtx *mtxp; + + startticks = ticks; + i = 0; + if (eti->threadid & 0x1) + mtxp = &mutexA; + else + mtxp = &mutexB; + + while (i < iterations) { + epoch_enter(test_epoch); + mtx_lock(mtxp); + i++; + mtx_unlock(mtxp); + epoch_exit(test_epoch); + epoch_wait(test_epoch); + } + printf("test1: thread: %d took %d ticks to complete %d iterations\n", + eti->threadid, ticks - startticks, iterations); +} + +static void +epoch_testcase2(struct epoch_test_instance *eti) +{ + int i, startticks; + struct mtx *mtxp; + + startticks = ticks; + i = 0; + mtxp = &mutexA; + + while (i < iterations) { + epoch_enter(test_epoch); + mtx_lock(mtxp); + DELAY(1); + i++; + mtx_unlock(mtxp); + epoch_exit(test_epoch); + epoch_wait(test_epoch); + } + printf("test2: thread: %d took %d ticks to complete %d iterations\n", + eti->threadid, ticks - startticks, iterations); +} + +static void +testloop(void *arg) { + + mtx_lock(&state_mtx); + while ((state_flags & ET_EXITING) == 0) { + msleep(&state_mtx, &state_mtx, 0, "epoch start wait", 0); + if (state_flags & ET_EXITING) + goto out; + mtx_unlock(&state_mtx); + epoch_testcase2(arg); + pause("W", 500); + epoch_testcase1(arg); + mtx_lock(&state_mtx); + } + out: + mtx_unlock(&state_mtx); + kthread_exit(); +} + +static struct thread *testthreads[MAXCPU]; +static struct epoch_test_instance etilist[MAXCPU]; + +static int +test_modinit(void) +{ + int i, error; + + test_epoch = epoch_alloc(); + for (i = 0; i < mp_ncpus; i++) { + etilist[i].threadid = i; + error = kthread_add(testloop, &etilist[i], NULL, &testthreads[i], + 0, 0, "epoch_test_%d", i); + if (error) { + printf("%s: kthread_add(epoch_test): error %d", __func__, + error); + } + } + inited = 1; + return (0); +} + +static int +epochtest_execute(SYSCTL_HANDLER_ARGS) +{ + int error, v; + + if (inited == 0) + return (ENOENT); + + v = 0; + error = sysctl_handle_int(oidp, &v, 0, req); + if (error) + return (error); + if (req->newptr == NULL) + return (error); + if (v == 0) + return (0); + mtx_lock(&state_mtx); + iterations = v; + wakeup(&state_mtx); + mtx_unlock(&state_mtx); + + return (0); +} + +SYSCTL_NODE(_kern, OID_AUTO, epochtest, CTLFLAG_RW, 0, "Epoch Test Framework"); +SYSCTL_PROC(_kern_epochtest, OID_AUTO, runtest, (CTLTYPE_INT | CTLFLAG_RW), + 0, 0, epochtest_execute, "I", "Execute an epoch test"); + +static int +epoch_test_module_event_handler(module_t mod, int what, void *arg __unused) +{ + int err; + + switch (what) { + case MOD_LOAD: + if ((err = test_modinit()) != 0) + return (err); + break; + case MOD_UNLOAD: + mtx_lock(&state_mtx); + state_flags = ET_EXITING; + wakeup(&state_mtx); + mtx_unlock(&state_mtx); + /* yes --- gross */ + pause("epoch unload", 3*hz); + break; + default: + return (EOPNOTSUPP); + } + + return (0); +} + +static moduledata_t epoch_test_moduledata = { + "epoch_test", + epoch_test_module_event_handler, + NULL +}; + +MODULE_VERSION(epoch_test, 1); +DECLARE_MODULE(epoch_test, epoch_test_moduledata, SI_SUB_PSEUDO, SI_ORDER_ANY);