1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
|
// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// Semaphore implementation exposed to Go.
// Intended use is provide a sleep and wakeup
// primitive that can be used in the contended case
// of other synchronization primitives.
// Thus it targets the same goal as Linux's futex,
// but it has much simpler semantics.
//
// That is, don't think of these as semaphores.
// Think of them as a way to implement sleep and wakeup
// such that every sleep is paired with a single wakeup,
// even if, due to races, the wakeup happens before the sleep.
//
// See Mullender and Cox, ``Semaphores in Plan 9,''
// http://swtch.com/semaphore.pdf
package sync
#include "runtime.h"
#include "arch.h"
typedef struct Sema Sema;
struct Sema
{
uint32 volatile* addr;
G* g;
int64 releasetime;
Sema* prev;
Sema* next;
};
typedef struct SemaRoot SemaRoot;
struct SemaRoot
{
Lock;
Sema* head;
Sema* tail;
// Number of waiters. Read w/o the lock.
uint32 volatile nwait;
};
// Prime to not correlate with any user patterns.
#define SEMTABLESZ 251
struct semtable
{
SemaRoot;
uint8 pad[CacheLineSize-sizeof(SemaRoot)];
};
static struct semtable semtable[SEMTABLESZ];
static SemaRoot*
semroot(uint32 volatile *addr)
{
return &semtable[((uintptr)addr >> 3) % SEMTABLESZ];
}
static void
semqueue(SemaRoot *root, uint32 volatile *addr, Sema *s)
{
s->g = runtime_g();
s->addr = addr;
s->next = nil;
s->prev = root->tail;
if(root->tail)
root->tail->next = s;
else
root->head = s;
root->tail = s;
}
static void
semdequeue(SemaRoot *root, Sema *s)
{
if(s->next)
s->next->prev = s->prev;
else
root->tail = s->prev;
if(s->prev)
s->prev->next = s->next;
else
root->head = s->next;
s->prev = nil;
s->next = nil;
}
static int32
cansemacquire(uint32 volatile *addr)
{
uint32 v;
while((v = runtime_atomicload(addr)) > 0)
if(runtime_cas(addr, v, v-1))
return 1;
return 0;
}
static void
semacquireimpl(uint32 volatile *addr, int32 profile)
{
Sema s; // Needs to be allocated on stack, otherwise garbage collector could deallocate it
SemaRoot *root;
int64 t0;
// Easy case.
if(cansemacquire(addr))
return;
// Harder case:
// increment waiter count
// try cansemacquire one more time, return if succeeded
// enqueue itself as a waiter
// sleep
// (waiter descriptor is dequeued by signaler)
root = semroot(addr);
t0 = 0;
s.releasetime = 0;
if(profile && runtime_blockprofilerate > 0) {
t0 = runtime_cputicks();
s.releasetime = -1;
}
for(;;) {
runtime_lock(root);
// Add ourselves to nwait to disable "easy case" in semrelease.
runtime_xadd(&root->nwait, 1);
// Check cansemacquire to avoid missed wakeup.
if(cansemacquire(addr)) {
runtime_xadd(&root->nwait, -1);
runtime_unlock(root);
return;
}
// Any semrelease after the cansemacquire knows we're waiting
// (we set nwait above), so go to sleep.
semqueue(root, addr, &s);
runtime_park(runtime_unlock, root, "semacquire");
if(cansemacquire(addr)) {
if(t0)
runtime_blockevent(s.releasetime - t0, 3);
return;
}
}
}
void
runtime_semacquire(uint32 volatile *addr)
{
semacquireimpl(addr, 0);
}
void
runtime_semrelease(uint32 volatile *addr)
{
Sema *s;
SemaRoot *root;
root = semroot(addr);
runtime_xadd(addr, 1);
// Easy case: no waiters?
// This check must happen after the xadd, to avoid a missed wakeup
// (see loop in semacquire).
if(runtime_atomicload(&root->nwait) == 0)
return;
// Harder case: search for a waiter and wake it.
runtime_lock(root);
if(runtime_atomicload(&root->nwait) == 0) {
// The count is already consumed by another goroutine,
// so no need to wake up another goroutine.
runtime_unlock(root);
return;
}
for(s = root->head; s; s = s->next) {
if(s->addr == addr) {
runtime_xadd(&root->nwait, -1);
semdequeue(root, s);
break;
}
}
runtime_unlock(root);
if(s) {
if(s->releasetime)
s->releasetime = runtime_cputicks();
runtime_ready(s->g);
}
}
func runtime_Semacquire(addr *uint32) {
semacquireimpl(addr, 1);
}
func runtime_Semrelease(addr *uint32) {
runtime_semrelease(addr);
}
|
