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
|
// 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 runtime
#include "runtime.h"
typedef struct Sema Sema;
struct Sema
{
uint32 volatile *addr;
G *g;
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
static union
{
SemaRoot;
// Modern processors tend to have 64-byte cache lines,
// potentially with 128-byte effective cache line size for reading.
// While there are hypothetical architectures
// with 16-4096 byte cache lines, 128 looks like a good compromise.
uint8 pad[128];
} semtable[SEMTABLESZ];
static SemaRoot*
semroot(uint32 *addr)
{
return &semtable[((uintptr)addr >> 3) % SEMTABLESZ];
}
static void
semqueue(SemaRoot *root, uint32 volatile *addr, Sema *s)
{
s->g = 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 *addr)
{
uint32 v;
while((v = runtime·atomicload(addr)) > 0)
if(runtime·cas(addr, v, v-1))
return 1;
return 0;
}
void
runtime·semacquire(uint32 volatile *addr)
{
Sema s;
SemaRoot *root;
// 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);
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);
g->status = Gwaiting;
runtime·unlock(root);
runtime·gosched();
if(cansemacquire(addr))
return;
}
}
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)
runtime·ready(s->g);
}
func Semacquire(addr *uint32) {
runtime·semacquire(addr);
}
func Semrelease(addr *uint32) {
runtime·semrelease(addr);
}
|
