Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(462)

Delta Between Two Patch Sets: src/pkg/runtime/sema.goc

Issue 11573043: sync: faster Cond (Closed)
Left Patch Set: diff -r f98e0eb03af9 https://dvyukov%40google.com@code.google.com/p/go/ Created 10 years, 8 months ago
Right Patch Set: diff -r ebf9b6a68289 https://dvyukov%40google.com@code.google.com/p/go/ Created 10 years, 7 months ago
Left:
Right:
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
Left: Side by side diff | Download
Right: Side by side diff | Download
« no previous file with change/comment | « no previous file | src/pkg/sync/cond.go » ('j') | no next file with change/comment »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
LEFTRIGHT
1 // Copyright 2009 The Go Authors. All rights reserved. 1 // Copyright 2009 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style 2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file. 3 // license that can be found in the LICENSE file.
4 4
5 // Semaphore implementation exposed to Go. 5 // Semaphore implementation exposed to Go.
6 // Intended use is provide a sleep and wakeup 6 // Intended use is provide a sleep and wakeup
7 // primitive that can be used in the contended case 7 // primitive that can be used in the contended case
8 // of other synchronization primitives. 8 // of other synchronization primitives.
9 // Thus it targets the same goal as Linux's futex, 9 // Thus it targets the same goal as Linux's futex,
10 // but it has much simpler semantics. 10 // but it has much simpler semantics.
11 // 11 //
12 // That is, don't think of these as semaphores. 12 // That is, don't think of these as semaphores.
13 // Think of them as a way to implement sleep and wakeup 13 // Think of them as a way to implement sleep and wakeup
14 // such that every sleep is paired with a single wakeup, 14 // such that every sleep is paired with a single wakeup,
15 // even if, due to races, the wakeup happens before the sleep. 15 // even if, due to races, the wakeup happens before the sleep.
16 // 16 //
17 // See Mullender and Cox, ``Semaphores in Plan 9,'' 17 // See Mullender and Cox, ``Semaphores in Plan 9,''
18 // http://swtch.com/semaphore.pdf 18 // http://swtch.com/semaphore.pdf
19 19
20 package sync 20 package sync
21 #include "runtime.h" 21 #include "runtime.h"
22 #include "arch_GOARCH.h" 22 #include "arch_GOARCH.h"
23 23
24 typedef struct Sema Sema; 24 typedef struct SemaWaiter SemaWaiter;
25 struct Sema 25 struct SemaWaiter
26 { 26 {
27 uint32 volatile* addr; 27 uint32 volatile* addr;
28 G* g; 28 G* g;
29 int64 releasetime; 29 int64 releasetime;
30 » Sema*» prev; 30 » int32» nrelease;» // -1 for acquire
31 » Sema*» next; 31 » SemaWaiter*» prev;
32 » SemaWaiter*» next;
32 }; 33 };
33 34
34 typedef struct SemaRoot SemaRoot; 35 typedef struct SemaRoot SemaRoot;
35 struct SemaRoot 36 struct SemaRoot
36 { 37 {
37 Lock; 38 Lock;
38 » Sema*» head; 39 » SemaWaiter*» head;
39 » Sema*» tail; 40 » SemaWaiter*» tail;
40 // Number of waiters. Read w/o the lock. 41 // Number of waiters. Read w/o the lock.
41 uint32 volatile nwait; 42 uint32 volatile nwait;
42 }; 43 };
43 44
44 // Prime to not correlate with any user patterns. 45 // Prime to not correlate with any user patterns.
45 #define SEMTABLESZ 251 46 #define SEMTABLESZ 251
46 47
47 struct semtable 48 struct semtable
48 { 49 {
49 SemaRoot; 50 SemaRoot;
50 uint8 pad[CacheLineSize-sizeof(SemaRoot)]; 51 uint8 pad[CacheLineSize-sizeof(SemaRoot)];
51 }; 52 };
52 #pragma dataflag 16 /* mark semtable as 'no pointers', hiding from garbage colle ctor */ 53 #pragma dataflag 16 /* mark semtable as 'no pointers', hiding from garbage colle ctor */
53 static struct semtable semtable[SEMTABLESZ]; 54 static struct semtable semtable[SEMTABLESZ];
54 55
55 static SemaRoot* 56 static SemaRoot*
56 semroot(uint32 *addr) 57 semroot(uint32 *addr)
57 { 58 {
58 return &semtable[((uintptr)addr >> 3) % SEMTABLESZ]; 59 return &semtable[((uintptr)addr >> 3) % SEMTABLESZ];
59 } 60 }
60 61
61 static void 62 static void
62 semqueue(SemaRoot *root, uint32 volatile *addr, Sema *s) 63 semqueue(SemaRoot *root, uint32 volatile *addr, SemaWaiter *s)
63 { 64 {
64 s->g = g; 65 s->g = g;
65 s->addr = addr; 66 s->addr = addr;
66 s->next = nil; 67 s->next = nil;
67 s->prev = root->tail; 68 s->prev = root->tail;
68 if(root->tail) 69 if(root->tail)
69 root->tail->next = s; 70 root->tail->next = s;
70 else 71 else
71 root->head = s; 72 root->head = s;
72 root->tail = s; 73 root->tail = s;
73 } 74 }
74 75
75 static void 76 static void
76 semdequeue(SemaRoot *root, Sema *s) 77 semdequeue(SemaRoot *root, SemaWaiter *s)
77 { 78 {
78 if(s->next) 79 if(s->next)
79 s->next->prev = s->prev; 80 s->next->prev = s->prev;
80 else 81 else
81 root->tail = s->prev; 82 root->tail = s->prev;
82 if(s->prev) 83 if(s->prev)
83 s->prev->next = s->next; 84 s->prev->next = s->next;
84 else 85 else
85 root->head = s->next; 86 root->head = s->next;
86 s->prev = nil; 87 s->prev = nil;
87 s->next = nil; 88 s->next = nil;
88 } 89 }
89 90
90 static int32 91 static int32
91 cansemacquire(uint32 *addr) 92 cansemacquire(uint32 *addr)
92 { 93 {
93 uint32 v; 94 uint32 v;
94 95
95 while((v = runtime·atomicload(addr)) > 0) 96 while((v = runtime·atomicload(addr)) > 0)
96 if(runtime·cas(addr, v, v-1)) 97 if(runtime·cas(addr, v, v-1))
97 return 1; 98 return 1;
98 return 0; 99 return 0;
99 } 100 }
100 101
101 static void 102 void
102 semacquireimpl(uint32 volatile *addr, int32 profile) 103 runtime·semacquire(uint32 volatile *addr, bool profile)
103 { 104 {
104 » Sema s;»// Needs to be allocated on stack, otherwise garbage collector c ould deallocate it 105 » SemaWaiter s;» // Needs to be allocated on stack, otherwise garbage col lector could deallocate it
105 SemaRoot *root; 106 SemaRoot *root;
106 int64 t0; 107 int64 t0;
107 ········ 108 ········
108 // Easy case. 109 // Easy case.
109 if(cansemacquire(addr)) 110 if(cansemacquire(addr))
110 return; 111 return;
111 112
112 // Harder case: 113 // Harder case:
113 // increment waiter count 114 // increment waiter count
114 // try cansemacquire one more time, return if succeeded 115 // try cansemacquire one more time, return if succeeded
(...skipping 23 matching lines...) Expand all
138 runtime·park(runtime·unlock, root, "semacquire"); 139 runtime·park(runtime·unlock, root, "semacquire");
139 if(cansemacquire(addr)) { 140 if(cansemacquire(addr)) {
140 if(t0) 141 if(t0)
141 runtime·blockevent(s.releasetime - t0, 3); 142 runtime·blockevent(s.releasetime - t0, 3);
142 return; 143 return;
143 } 144 }
144 } 145 }
145 } 146 }
146 147
147 void 148 void
148 runtime·semacquire(uint32 volatile *addr)
149 {
150 semacquireimpl(addr, 0);
151 }
152
153 void
154 runtime·semrelease(uint32 volatile *addr) 149 runtime·semrelease(uint32 volatile *addr)
155 { 150 {
156 » Sema *s; 151 » SemaWaiter *s;
157 SemaRoot *root; 152 SemaRoot *root;
158 153
159 root = semroot(addr); 154 root = semroot(addr);
160 runtime·xadd(addr, 1); 155 runtime·xadd(addr, 1);
161 156
162 // Easy case: no waiters? 157 // Easy case: no waiters?
163 // This check must happen after the xadd, to avoid a missed wakeup 158 // This check must happen after the xadd, to avoid a missed wakeup
164 // (see loop in semacquire). 159 // (see loop in semacquire).
165 if(runtime·atomicload(&root->nwait) == 0) 160 if(runtime·atomicload(&root->nwait) == 0)
166 return; 161 return;
(...skipping 14 matching lines...) Expand all
181 } 176 }
182 } 177 }
183 runtime·unlock(root); 178 runtime·unlock(root);
184 if(s) { 179 if(s) {
185 if(s->releasetime) 180 if(s->releasetime)
186 s->releasetime = runtime·cputicks(); 181 s->releasetime = runtime·cputicks();
187 runtime·ready(s->g); 182 runtime·ready(s->g);
188 } 183 }
189 } 184 }
190 185
186 // TODO(dvyukov): move to netpoll.goc once it's used by all OSes.
187 void net·runtime_Semacquire(uint32 *addr)
188 {
189 runtime·semacquire(addr, true);
190 }
191
192 void net·runtime_Semrelease(uint32 *addr)
193 {
194 runtime·semrelease(addr);
195 }
196
191 func runtime_Semacquire(addr *uint32) { 197 func runtime_Semacquire(addr *uint32) {
192 » semacquireimpl(addr, 1); 198 » runtime·semacquire(addr, true);
193 } 199 }
194 200
195 func runtime_Semrelease(addr *uint32) { 201 func runtime_Semrelease(addr *uint32) {
196 runtime·semrelease(addr); 202 runtime·semrelease(addr);
197 } 203 }
198 204
199 typedef struct SyncSema SyncSema; 205 typedef struct SyncSema SyncSema;
200 typedef struct SyncSemaWaiter SyncSemaWaiter;
201
202 struct SyncSema 206 struct SyncSema
203 { 207 {
204 Lock; 208 Lock;
205 » SyncSemaWaiter*»head; 209 » SemaWaiter*» head;
206 » SyncSemaWaiter*»tail; 210 » SemaWaiter*» tail;
207 }; 211 };
208 212
209 struct SyncSemaWaiter 213 func runtime_Syncsemcheck(size uintptr) {
210 { 214 » if(size != sizeof(SyncSema)) {
211 » G*» g; 215 » » runtime·printf("bad SyncSema size: sync:%D runtime:%D\n", (int64 )size, (int64)sizeof(SyncSema));
212 » int32» nrelease;» // -1 for acquire 216 » » runtime·throw("bad SyncSema size");
213 » int64» releasetime; 217 » }
214 » SyncSemaWaiter*»next; 218 }
215 }; 219
216 220 // Syncsemacquire waits for a pairing Syncsemrelease on the same semaphore s.
217 func runtime_Syncsemacquire(s *SyncSema) { 221 func runtime_Syncsemacquire(s *SyncSema) {
218 » SyncSemaWaiter w, *wake; 222 » SemaWaiter w, *wake;
219 int64 t0; 223 int64 t0;
220 224
221 w.g = g; 225 w.g = g;
222 w.nrelease = -1; 226 w.nrelease = -1;
223 w.next = nil; 227 w.next = nil;
224 w.releasetime = 0; 228 w.releasetime = 0;
225 t0 = 0; 229 t0 = 0;
226 if(runtime·blockprofilerate > 0) { 230 if(runtime·blockprofilerate > 0) {
227 t0 = runtime·cputicks(); 231 t0 = runtime·cputicks();
228 w.releasetime = -1; 232 w.releasetime = -1;
(...skipping 19 matching lines...) Expand all
248 s->head = &w; 252 s->head = &w;
249 else 253 else
250 s->tail->next = &w; 254 s->tail->next = &w;
251 s->tail = &w; 255 s->tail = &w;
252 runtime·park(runtime·unlock, s, "semacquire"); 256 runtime·park(runtime·unlock, s, "semacquire");
253 if(t0) 257 if(t0)
254 runtime·blockevent(w.releasetime - t0, 2); 258 runtime·blockevent(w.releasetime - t0, 2);
255 } 259 }
256 } 260 }
257 261
262 // Syncsemrelease waits for n pairing Syncsemacquire on the same semaphore s.
258 func runtime_Syncsemrelease(s *SyncSema, n uint32) { 263 func runtime_Syncsemrelease(s *SyncSema, n uint32) {
259 » SyncSemaWaiter w, *wake; 264 » SemaWaiter w, *wake;
260 265
261 w.g = g; 266 w.g = g;
262 w.nrelease = (int32)n; 267 w.nrelease = (int32)n;
263 w.next = nil; 268 w.next = nil;
264 w.releasetime = 0; 269 w.releasetime = 0;
265 270
266 runtime·lock(s); 271 runtime·lock(s);
267 while(w.nrelease > 0 && s->head && s->head->nrelease < 0) { 272 while(w.nrelease > 0 && s->head && s->head->nrelease < 0) {
268 // have pending acquire, satisfy it 273 // have pending acquire, satisfy it
269 wake = s->head; 274 wake = s->head;
270 s->head = wake->next; 275 s->head = wake->next;
271 if(s->head == nil) 276 if(s->head == nil)
272 s->tail = nil; 277 s->tail = nil;
273 if(wake->releasetime) 278 if(wake->releasetime)
274 wake->releasetime = runtime·cputicks(); 279 wake->releasetime = runtime·cputicks();
275 runtime·ready(wake->g); 280 runtime·ready(wake->g);
276 w.nrelease--; 281 w.nrelease--;
277 } 282 }
278 if(w.nrelease > 0) { 283 if(w.nrelease > 0) {
279 // enqueue itself 284 // enqueue itself
280 if(s->tail == nil) 285 if(s->tail == nil)
281 s->head = &w; 286 s->head = &w;
282 else 287 else
283 s->tail->next = &w; 288 s->tail->next = &w;
284 s->tail = &w; 289 s->tail = &w;
285 runtime·park(runtime·unlock, s, "semarelease"); 290 runtime·park(runtime·unlock, s, "semarelease");
286 } else 291 } else
287 runtime·unlock(s); 292 runtime·unlock(s);
288 } 293 }
LEFTRIGHT

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b