From 55c553ae8c7937be4a7e10e0c7a727d132317e89 Mon Sep 17 00:00:00 2001 From: gVisor bot Date: Tue, 18 Feb 2020 15:17:45 -0800 Subject: Add //pkg/syncevent. Package syncevent is intended to subsume ~all uses of channels in the sentry (including //pkg/waiter), as well as //pkg/sleep. Compared to channels: - Delivery of events to a syncevent.Receiver allows *synchronous* execution of an arbitrary callback, whereas delivery of events to a channel requires a goroutine to receive from that channel, resulting in substantial scheduling overhead. (This is also part of the motivation for the waiter package.) - syncevent.Waiter can wait on multiple event sources without the high O(N) overhead of select. (This is the same motivation as for the sleep package.) Compared to the waiter package: - syncevent.Waiters are intended to be persistent (i.e. per-kernel.Task), and syncevent.Broadcaster (analogous to waiter.Queue) is a hash table rather than a linked list, such that blocking is (usually) allocation-free. - syncevent.Source (analogous to waiter.Waitable) does not include an equivalent to waiter.Waitable.Readiness(), since this is inappropriate for transient events (see e.g. //pkg/sentry/kernel/time.ClockEventSource). Compared to the sleep package: - syncevent events are represented by bits in a bitmask rather than discrete sleep.Waker objects, reducing overhead and making it feasible to broadcast events to multiple syncevent.Receivers. - syncevent.Receiver invokes an arbitrary callback, which is required by the sentry's epoll implementation. (syncevent.Waiter, which is analogous to sleep.Sleeper, pairs a syncevent.Receiver with a callback that wakes a waiting goroutine; the implementation of this aspect is nearly identical to that of sleep.Sleeper, except that it represents *runtime.g as unsafe.Pointer rather than uintptr.) - syncevent.Waiter.Wait (analogous to sleep.Sleeper.Fetch(block=true)) does not automatically un-assert returned events. This is useful in cases where the path for handling an event is not the same as the path that observes it, such as for application signals (a la Linux's TIF_SIGPENDING). - Unlike sleep.Sleeper, which Fetches Wakers in the order that they were Asserted, the event bitmasks used by syncevent.Receiver have no way of preserving event arrival order. (This is similar to select, which goes out of its way to randomize event ordering.) The disadvantage of the syncevent package is that, since events are represented by bits in a uint64 bitmask, each syncevent.Receiver can "only" multiplex between 64 distinct events; this does not affect any known use case. Benchmarks: BenchmarkBroadcasterSubscribeUnsubscribe BenchmarkBroadcasterSubscribeUnsubscribe-12 45133884 26.3 ns/op BenchmarkMapSubscribeUnsubscribe BenchmarkMapSubscribeUnsubscribe-12 28504662 41.8 ns/op BenchmarkQueueSubscribeUnsubscribe BenchmarkQueueSubscribeUnsubscribe-12 22747668 45.6 ns/op BenchmarkBroadcasterSubscribeUnsubscribeBatch BenchmarkBroadcasterSubscribeUnsubscribeBatch-12 31609177 37.8 ns/op BenchmarkMapSubscribeUnsubscribeBatch BenchmarkMapSubscribeUnsubscribeBatch-12 17563906 62.1 ns/op BenchmarkQueueSubscribeUnsubscribeBatch BenchmarkQueueSubscribeUnsubscribeBatch-12 26248838 46.6 ns/op BenchmarkBroadcasterBroadcastRedundant BenchmarkBroadcasterBroadcastRedundant/0 BenchmarkBroadcasterBroadcastRedundant/0-12 100907563 11.8 ns/op BenchmarkBroadcasterBroadcastRedundant/1 BenchmarkBroadcasterBroadcastRedundant/1-12 85103068 13.3 ns/op BenchmarkBroadcasterBroadcastRedundant/4 BenchmarkBroadcasterBroadcastRedundant/4-12 52716502 22.3 ns/op BenchmarkBroadcasterBroadcastRedundant/16 BenchmarkBroadcasterBroadcastRedundant/16-12 20278165 58.7 ns/op BenchmarkBroadcasterBroadcastRedundant/64 BenchmarkBroadcasterBroadcastRedundant/64-12 5905428 205 ns/op BenchmarkMapBroadcastRedundant BenchmarkMapBroadcastRedundant/0 BenchmarkMapBroadcastRedundant/0-12 87532734 13.5 ns/op BenchmarkMapBroadcastRedundant/1 BenchmarkMapBroadcastRedundant/1-12 28488411 36.3 ns/op BenchmarkMapBroadcastRedundant/4 BenchmarkMapBroadcastRedundant/4-12 19628920 60.9 ns/op BenchmarkMapBroadcastRedundant/16 BenchmarkMapBroadcastRedundant/16-12 6026980 192 ns/op BenchmarkMapBroadcastRedundant/64 BenchmarkMapBroadcastRedundant/64-12 1640858 754 ns/op BenchmarkQueueBroadcastRedundant BenchmarkQueueBroadcastRedundant/0 BenchmarkQueueBroadcastRedundant/0-12 96904807 12.0 ns/op BenchmarkQueueBroadcastRedundant/1 BenchmarkQueueBroadcastRedundant/1-12 73521873 16.3 ns/op BenchmarkQueueBroadcastRedundant/4 BenchmarkQueueBroadcastRedundant/4-12 39209468 31.2 ns/op BenchmarkQueueBroadcastRedundant/16 BenchmarkQueueBroadcastRedundant/16-12 10810058 105 ns/op BenchmarkQueueBroadcastRedundant/64 BenchmarkQueueBroadcastRedundant/64-12 2998046 376 ns/op BenchmarkBroadcasterBroadcastAck BenchmarkBroadcasterBroadcastAck/1 BenchmarkBroadcasterBroadcastAck/1-12 44472397 26.4 ns/op BenchmarkBroadcasterBroadcastAck/4 BenchmarkBroadcasterBroadcastAck/4-12 17653509 69.7 ns/op BenchmarkBroadcasterBroadcastAck/16 BenchmarkBroadcasterBroadcastAck/16-12 4082617 260 ns/op BenchmarkBroadcasterBroadcastAck/64 BenchmarkBroadcasterBroadcastAck/64-12 1220534 1027 ns/op BenchmarkMapBroadcastAck BenchmarkMapBroadcastAck/1 BenchmarkMapBroadcastAck/1-12 26760705 44.2 ns/op BenchmarkMapBroadcastAck/4 BenchmarkMapBroadcastAck/4-12 11495636 100 ns/op BenchmarkMapBroadcastAck/16 BenchmarkMapBroadcastAck/16-12 2937590 343 ns/op BenchmarkMapBroadcastAck/64 BenchmarkMapBroadcastAck/64-12 861037 1344 ns/op BenchmarkQueueBroadcastAck BenchmarkQueueBroadcastAck/1 BenchmarkQueueBroadcastAck/1-12 19832679 55.0 ns/op BenchmarkQueueBroadcastAck/4 BenchmarkQueueBroadcastAck/4-12 5618214 189 ns/op BenchmarkQueueBroadcastAck/16 BenchmarkQueueBroadcastAck/16-12 1569980 713 ns/op BenchmarkQueueBroadcastAck/64 BenchmarkQueueBroadcastAck/64-12 437672 2814 ns/op BenchmarkWaiterNotifyRedundant BenchmarkWaiterNotifyRedundant-12 650823090 1.96 ns/op BenchmarkSleeperNotifyRedundant BenchmarkSleeperNotifyRedundant-12 619871544 1.61 ns/op BenchmarkChannelNotifyRedundant BenchmarkChannelNotifyRedundant-12 298903778 3.67 ns/op BenchmarkWaiterNotifyWaitAck BenchmarkWaiterNotifyWaitAck-12 68358360 17.8 ns/op BenchmarkSleeperNotifyWaitAck BenchmarkSleeperNotifyWaitAck-12 25044883 41.2 ns/op BenchmarkChannelNotifyWaitAck BenchmarkChannelNotifyWaitAck-12 29572404 40.2 ns/op BenchmarkSleeperMultiNotifyWaitAck BenchmarkSleeperMultiNotifyWaitAck-12 16122969 73.8 ns/op BenchmarkWaiterTempNotifyWaitAck BenchmarkWaiterTempNotifyWaitAck-12 46111489 25.8 ns/op BenchmarkSleeperTempNotifyWaitAck BenchmarkSleeperTempNotifyWaitAck-12 15541882 73.6 ns/op BenchmarkWaiterNotifyWaitMultiAck BenchmarkWaiterNotifyWaitMultiAck-12 65878500 18.2 ns/op BenchmarkSleeperNotifyWaitMultiAck BenchmarkSleeperNotifyWaitMultiAck-12 28798623 41.5 ns/op BenchmarkChannelNotifyWaitMultiAck BenchmarkChannelNotifyWaitMultiAck-12 11308468 101 ns/op BenchmarkWaiterNotifyAsyncWaitAck BenchmarkWaiterNotifyAsyncWaitAck-12 2475387 492 ns/op BenchmarkSleeperNotifyAsyncWaitAck BenchmarkSleeperNotifyAsyncWaitAck-12 2184507 518 ns/op BenchmarkChannelNotifyAsyncWaitAck BenchmarkChannelNotifyAsyncWaitAck-12 2120365 562 ns/op BenchmarkWaiterNotifyAsyncWaitMultiAck BenchmarkWaiterNotifyAsyncWaitMultiAck-12 2351247 494 ns/op BenchmarkSleeperNotifyAsyncWaitMultiAck BenchmarkSleeperNotifyAsyncWaitMultiAck-12 2205799 522 ns/op BenchmarkChannelNotifyAsyncWaitMultiAck BenchmarkChannelNotifyAsyncWaitMultiAck-12 1238079 928 ns/op Updates #1074 PiperOrigin-RevId: 295834087 --- pkg/syncevent/receiver.go | 103 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 103 insertions(+) create mode 100644 pkg/syncevent/receiver.go (limited to 'pkg/syncevent/receiver.go') diff --git a/pkg/syncevent/receiver.go b/pkg/syncevent/receiver.go new file mode 100644 index 000000000..5c86e5400 --- /dev/null +++ b/pkg/syncevent/receiver.go @@ -0,0 +1,103 @@ +// Copyright 2020 The gVisor Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package syncevent + +import ( + "sync/atomic" + + "gvisor.dev/gvisor/pkg/atomicbitops" +) + +// Receiver is an event sink that holds pending events and invokes a callback +// whenever new events become pending. Receiver's methods may be called +// concurrently from multiple goroutines. +// +// Receiver.Init() must be called before first use. +type Receiver struct { + // pending is the set of pending events. pending is accessed using atomic + // memory operations. + pending uint64 + + // cb is notified when new events become pending. cb is immutable after + // Init(). + cb ReceiverCallback +} + +// ReceiverCallback receives callbacks from a Receiver. +type ReceiverCallback interface { + // NotifyPending is called when the corresponding Receiver has new pending + // events. + // + // NotifyPending is called synchronously from Receiver.Notify(), so + // implementations must not take locks that may be held by callers of + // Receiver.Notify(). NotifyPending may be called concurrently from + // multiple goroutines. + NotifyPending() +} + +// Init must be called before first use of r. +func (r *Receiver) Init(cb ReceiverCallback) { + r.cb = cb +} + +// Pending returns the set of pending events. +func (r *Receiver) Pending() Set { + return Set(atomic.LoadUint64(&r.pending)) +} + +// Notify sets the given events as pending. +func (r *Receiver) Notify(es Set) { + p := Set(atomic.LoadUint64(&r.pending)) + // Optimization: Skip the atomic CAS on r.pending if all events are + // already pending. + if p&es == es { + return + } + // When this is uncontended (the common case), CAS is faster than + // atomic-OR because the former is inlined and the latter (which we + // implement in assembly ourselves) is not. + if !atomic.CompareAndSwapUint64(&r.pending, uint64(p), uint64(p|es)) { + // If the CAS fails, fall back to atomic-OR. + atomicbitops.OrUint64(&r.pending, uint64(es)) + } + r.cb.NotifyPending() +} + +// Ack unsets the given events as pending. +func (r *Receiver) Ack(es Set) { + p := Set(atomic.LoadUint64(&r.pending)) + // Optimization: Skip the atomic CAS on r.pending if all events are + // already not pending. + if p&es == 0 { + return + } + // When this is uncontended (the common case), CAS is faster than + // atomic-AND because the former is inlined and the latter (which we + // implement in assembly ourselves) is not. + if !atomic.CompareAndSwapUint64(&r.pending, uint64(p), uint64(p&^es)) { + // If the CAS fails, fall back to atomic-AND. + atomicbitops.AndUint64(&r.pending, ^uint64(es)) + } +} + +// PendingAndAckAll unsets all events as pending and returns the set of +// previously-pending events. +// +// PendingAndAckAll should only be used in preference to a call to Pending +// followed by a conditional call to Ack when the caller expects events to be +// pending (e.g. after a call to ReceiverCallback.NotifyPending()). +func (r *Receiver) PendingAndAckAll() Set { + return Set(atomic.SwapUint64(&r.pending, 0)) +} -- cgit v1.2.3