1 // Copyright 2019 The gVisor Authors.
2 //
3 // Use of this source code is governed by a BSD-style
4 // license that can be found in the LICENSE file.
5 6 package sync
7 8 import (
9 "sync/atomic"
10 )
11 12 // SeqCount is a synchronization primitive for optimistic reader/writer
13 // synchronization in cases where readers can work with stale data and
14 // therefore do not need to block writers.
15 //
16 // Compared to sync/atomic.Value:
17 //
18 // - Mutation of SeqCount-protected data does not require memory allocation,
19 // whereas atomic.Value generally does. This is a significant advantage when
20 // writes are common.
21 //
22 // - Atomic reads of SeqCount-protected data require copying. This is a
23 // disadvantage when atomic reads are common.
24 //
25 // - SeqCount may be more flexible: correct use of SeqCount.ReadOk allows other
26 // operations to be made atomic with reads of SeqCount-protected data.
27 //
28 // - SeqCount is more cumbersome to use; atomic reads of SeqCount-protected
29 // data require instantiating function templates using go_generics (see
30 // seqatomic.go).
31 type SeqCount struct {
32 // epoch is incremented by BeginWrite and EndWrite, such that epoch is odd
33 // if a writer critical section is active, and a read from data protected
34 // by this SeqCount is atomic iff epoch is the same even value before and
35 // after the read.
36 epoch uint32
37 }
38 39 // SeqCountEpoch tracks writer critical sections in a SeqCount.
40 type SeqCountEpoch uint32
41 42 // BeginRead indicates the beginning of a reader critical section. Reader
43 // critical sections DO NOT BLOCK writer critical sections, so operations in a
44 // reader critical section MAY RACE with writer critical sections. Races are
45 // detected by ReadOk at the end of the reader critical section. Thus, the
46 // low-level structure of readers is generally:
47 //
48 // for {
49 // epoch := seq.BeginRead()
50 // // do something idempotent with seq-protected data
51 // if seq.ReadOk(epoch) {
52 // break
53 // }
54 // }
55 //
56 // However, since reader critical sections may race with writer critical
57 // sections, the Go race detector will (accurately) flag data races in readers
58 // using this pattern. Most users of SeqCount will need to use the
59 // SeqAtomicLoad function template in seqatomic.go.
60 func (s *SeqCount) BeginRead() SeqCountEpoch {
61 if epoch := atomic.LoadUint32(&s.epoch); epoch&1 == 0 {
62 return SeqCountEpoch(epoch)
63 }
64 return s.beginReadSlow()
65 }
66 67 func (s *SeqCount) beginReadSlow() SeqCountEpoch {
68 i := 0
69 for {
70 if canSpin(i) {
71 i++
72 doSpin()
73 } else {
74 goyield()
75 }
76 if epoch := atomic.LoadUint32(&s.epoch); epoch&1 == 0 {
77 return SeqCountEpoch(epoch)
78 }
79 }
80 }
81 82 // ReadOk returns true if the reader critical section initiated by a previous
83 // call to BeginRead() that returned epoch did not race with any writer critical
84 // sections.
85 //
86 // ReadOk may be called any number of times during a reader critical section.
87 // Reader critical sections do not need to be explicitly terminated; the last
88 // call to ReadOk is implicitly the end of the reader critical section.
89 func (s *SeqCount) ReadOk(epoch SeqCountEpoch) bool {
90 MemoryFenceReads()
91 return atomic.LoadUint32(&s.epoch) == uint32(epoch)
92 }
93 94 // BeginWrite indicates the beginning of a writer critical section.
95 //
96 // SeqCount does not support concurrent writer critical sections; clients with
97 // concurrent writers must synchronize them using e.g. sync.Mutex.
98 func (s *SeqCount) BeginWrite() {
99 if epoch := atomic.AddUint32(&s.epoch, 1); epoch&1 == 0 {
100 panic("SeqCount.BeginWrite during writer critical section")
101 }
102 }
103 104 // BeginWriteOk combines the semantics of ReadOk and BeginWrite. If the reader
105 // critical section initiated by a previous call to BeginRead() that returned
106 // epoch did not race with any writer critical sections, it begins a writer
107 // critical section and returns true. Otherwise it does nothing and returns
108 // false.
109 func (s *SeqCount) BeginWriteOk(epoch SeqCountEpoch) bool {
110 return atomic.CompareAndSwapUint32(&s.epoch, uint32(epoch), uint32(epoch)+1)
111 }
112 113 // EndWrite ends the effect of a preceding BeginWrite or successful
114 // BeginWriteOk.
115 func (s *SeqCount) EndWrite() {
116 if epoch := atomic.AddUint32(&s.epoch, 1); epoch&1 != 0 {
117 panic("SeqCount.EndWrite outside writer critical section")
118 }
119 }
120