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

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

Issue 11573043: sync: faster Cond (Closed)
Left Patch Set: 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:
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
(no file at all)
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 void 102 void
102 runtime·semacquire(uint32 volatile *addr, bool 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 25 matching lines...) Expand all
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·semrelease(uint32 volatile *addr) 149 runtime·semrelease(uint32 volatile *addr)
149 { 150 {
150 » Sema *s; 151 » SemaWaiter *s;
151 SemaRoot *root; 152 SemaRoot *root;
152 153
153 root = semroot(addr); 154 root = semroot(addr);
154 runtime·xadd(addr, 1); 155 runtime·xadd(addr, 1);
155 156
156 // Easy case: no waiters? 157 // Easy case: no waiters?
157 // 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
158 // (see loop in semacquire). 159 // (see loop in semacquire).
159 if(runtime·atomicload(&root->nwait) == 0) 160 if(runtime·atomicload(&root->nwait) == 0)
160 return; 161 return;
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after
193 runtime·semrelease(addr); 194 runtime·semrelease(addr);
194 } 195 }
195 196
196 func runtime_Semacquire(addr *uint32) { 197 func runtime_Semacquire(addr *uint32) {
197 runtime·semacquire(addr, true); 198 runtime·semacquire(addr, true);
198 } 199 }
199 200
200 func runtime_Semrelease(addr *uint32) { 201 func runtime_Semrelease(addr *uint32) {
201 runtime·semrelease(addr); 202 runtime·semrelease(addr);
202 } 203 }
204
205 typedef struct SyncSema SyncSema;
206 struct SyncSema
207 {
208 Lock;
209 SemaWaiter* head;
210 SemaWaiter* tail;
211 };
212
213 func runtime_Syncsemcheck(size uintptr) {
214 if(size != sizeof(SyncSema)) {
215 runtime·printf("bad SyncSema size: sync:%D runtime:%D\n", (int64 )size, (int64)sizeof(SyncSema));
216 runtime·throw("bad SyncSema size");
217 }
218 }
219
220 // Syncsemacquire waits for a pairing Syncsemrelease on the same semaphore s.
221 func runtime_Syncsemacquire(s *SyncSema) {
222 SemaWaiter w, *wake;
223 int64 t0;
224
225 w.g = g;
226 w.nrelease = -1;
227 w.next = nil;
228 w.releasetime = 0;
229 t0 = 0;
230 if(runtime·blockprofilerate > 0) {
231 t0 = runtime·cputicks();
232 w.releasetime = -1;
233 }
234
235 runtime·lock(s);
236 if(s->head && s->head->nrelease > 0) {
237 // have pending release, consume it
238 wake = nil;
239 s->head->nrelease--;
240 if(s->head->nrelease == 0) {
241 wake = s->head;
242 s->head = wake->next;
243 if(s->head == nil)
244 s->tail = nil;
245 }
246 runtime·unlock(s);
247 if(wake)
248 runtime·ready(wake->g);
249 } else {
250 // enqueue itself
251 if(s->tail == nil)
252 s->head = &w;
253 else
254 s->tail->next = &w;
255 s->tail = &w;
256 runtime·park(runtime·unlock, s, "semacquire");
257 if(t0)
258 runtime·blockevent(w.releasetime - t0, 2);
259 }
260 }
261
262 // Syncsemrelease waits for n pairing Syncsemacquire on the same semaphore s.
263 func runtime_Syncsemrelease(s *SyncSema, n uint32) {
264 SemaWaiter w, *wake;
265
266 w.g = g;
267 w.nrelease = (int32)n;
268 w.next = nil;
269 w.releasetime = 0;
270
271 runtime·lock(s);
272 while(w.nrelease > 0 && s->head && s->head->nrelease < 0) {
273 // have pending acquire, satisfy it
274 wake = s->head;
275 s->head = wake->next;
276 if(s->head == nil)
277 s->tail = nil;
278 if(wake->releasetime)
279 wake->releasetime = runtime·cputicks();
280 runtime·ready(wake->g);
281 w.nrelease--;
282 }
283 if(w.nrelease > 0) {
284 // enqueue itself
285 if(s->tail == nil)
286 s->head = &w;
287 else
288 s->tail->next = &w;
289 s->tail = &w;
290 runtime·park(runtime·unlock, s, "semarelease");
291 } else
292 runtime·unlock(s);
293 }
LEFTRIGHT

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