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

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

Issue 4631059: code review 4631059: runtime: replace Semacquire/Semrelease implementation (Closed)
Left Patch Set: diff -r 607e0f74161f https://go.googlecode.com/hg/ Created 12 years, 9 months ago
Right Patch Set: diff -r 607e0f74161f https://go.googlecode.com/hg/ Created 12 years, 9 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 | « src/pkg/runtime/runtime.h ('k') | no next file » | 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.
(...skipping 18 matching lines...) Expand all
29 Sema *next; 29 Sema *next;
30 }; 30 };
31 31
32 typedef struct SemaRoot SemaRoot; 32 typedef struct SemaRoot SemaRoot;
33 struct SemaRoot 33 struct SemaRoot
34 { 34 {
35 Lock; 35 Lock;
36 Sema *head; 36 Sema *head;
37 Sema *tail; 37 Sema *tail;
38 // Number of waiters. Read w/o the lock. 38 // Number of waiters. Read w/o the lock.
39 » uint32 volatile cnt; 39 » uint32 volatile nwait;
40 }; 40 };
41 41
42 // Prime to not correlate with any user patterns. 42 // Prime to not correlate with any user patterns.
43 #define SEMTABLESZ 251 43 #define SEMTABLESZ 251
44 44
45 static union 45 static union
46 { 46 {
47 SemaRoot; 47 SemaRoot;
48 // Modern processors tend to have 64-byte cache lines, 48 // Modern processors tend to have 64-byte cache lines,
49 // potentially with 128-byte effective cache line size for reading. 49 // potentially with 128-byte effective cache line size for reading.
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after
85 root->head = s->next; 85 root->head = s->next;
86 s->prev = nil; 86 s->prev = nil;
87 s->next = nil; 87 s->next = nil;
88 } 88 }
89 89
90 static int32 90 static int32
91 cansemacquire(uint32 *addr) 91 cansemacquire(uint32 *addr)
92 { 92 {
93 uint32 v; 93 uint32 v;
94 94
95 » while((v = *addr) > 0) 95 » while((v = runtime·atomicload(addr)) > 0)
96 if(runtime·cas(addr, v, v-1)) 96 if(runtime·cas(addr, v, v-1))
97 return 1; 97 return 1;
98 return 0; 98 return 0;
99 } 99 }
100 100
101 void 101 void
102 runtime·semacquire(uint32 volatile *addr) 102 runtime·semacquire(uint32 volatile *addr)
103 { 103 {
104 Sema s; 104 Sema s;
105 SemaRoot *root; 105 SemaRoot *root;
106 106
107 // Easy case. 107 // Easy case.
108 if(cansemacquire(addr)) 108 if(cansemacquire(addr))
109 return; 109 return;
110 110
111 // Harder case: 111 // Harder case:
112 // increment waiter count 112 // increment waiter count
113 // try cansemacquire one more time, return if succeeded 113 // try cansemacquire one more time, return if succeeded
114 // enqueue itself as a waiter 114 // enqueue itself as a waiter
115 // sleep 115 // sleep
116 // (waiter descriptor is dequeued by signaler) 116 // (waiter descriptor is dequeued by signaler)
117 root = semroot(addr); 117 root = semroot(addr);
118 for(;;) { 118 for(;;) {
119 runtime·lock(root); 119 runtime·lock(root);
120 » » runtime·xadd(&root->cnt, 1); 120 » » // Add ourselves to nwait to disable "easy case" in semrelease.
121 » » runtime·xadd(&root->nwait, 1);
122 » » // Check cansemacquire to avoid missed wakeup.
121 if(cansemacquire(addr)) { 123 if(cansemacquire(addr)) {
124 runtime·xadd(&root->nwait, -1);
122 runtime·unlock(root); 125 runtime·unlock(root);
123 runtime·xadd(&root->cnt, -1);
124 return; 126 return;
125 } 127 }
128 // Any semrelease after the cansemacquire knows we're waiting
129 // (we set nwait above), so go to sleep.
126 semqueue(root, addr, &s); 130 semqueue(root, addr, &s);
127 g->status = Gwaiting; 131 g->status = Gwaiting;
128 runtime·unlock(root); 132 runtime·unlock(root);
129 runtime·gosched(); 133 runtime·gosched();
130 if(cansemacquire(addr)) 134 if(cansemacquire(addr))
131 return; 135 return;
132 } 136 }
133 } 137 }
134 138
135 void 139 void
136 runtime·semrelease(uint32 volatile *addr) 140 runtime·semrelease(uint32 volatile *addr)
137 { 141 {
138 Sema *s; 142 Sema *s;
139 SemaRoot *root; 143 SemaRoot *root;
140 144
141 // Easy case: no waiters?
142 root = semroot(addr); 145 root = semroot(addr);
143 runtime·xadd(addr, 1); 146 runtime·xadd(addr, 1);
144 » if(runtime·atomicload(&root->cnt) == 0) 147
148 » // Easy case: no waiters?
149 » // This check must happen after the xadd, to avoid a missed wakeup
150 » // (see loop in semacquire).
151 » if(runtime·atomicload(&root->nwait) == 0)
145 return; 152 return;
146 153
147 // Harder case: search for a waiter and wake it. 154 // Harder case: search for a waiter and wake it.
148 runtime·lock(root); 155 runtime·lock(root);
156 if(runtime·atomicload(&root->nwait) == 0) {
157 // The count is already consumed by another goroutine,
158 // so no need to wake up another goroutine.
159 runtime·unlock(root);
160 return;
161 }
149 for(s = root->head; s; s = s->next) { 162 for(s = root->head; s; s = s->next) {
150 if(s->addr == addr) { 163 if(s->addr == addr) {
151 » » » // The count is already consumed by another goroutine, 164 » » » runtime·xadd(&root->nwait, -1);
152 » » » // so no need to wake up another goroutine. 165 » » » semdequeue(root, s);
153 » » » if(runtime·atomicload(&root->cnt) == 0)
154 » » » » s = nil;
155 » » » else
156 » » » » semdequeue(root, s);
157 break; 166 break;
158 } 167 }
159 } 168 }
160 runtime·unlock(root); 169 runtime·unlock(root);
161 » if(s) { 170 » if(s)
162 » » runtime·xadd(&root->cnt, -1);
163 runtime·ready(s->g); 171 runtime·ready(s->g);
164 }
165 } 172 }
166 173
167 func Semacquire(addr *uint32) { 174 func Semacquire(addr *uint32) {
168 runtime·semacquire(addr); 175 runtime·semacquire(addr);
169 } 176 }
170 177
171 func Semrelease(addr *uint32) { 178 func Semrelease(addr *uint32) {
172 runtime·semrelease(addr); 179 runtime·semrelease(addr);
173 } 180 }
LEFTRIGHT

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