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

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 6f1145ee588d 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 14 matching lines...) Expand all
25 { 25 {
26 uint32 volatile *addr; 26 uint32 volatile *addr;
27 G *g; 27 G *g;
28 Sema *prev; 28 Sema *prev;
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 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.
50 // While there are hypothetical architectures 50 // While there are hypothetical architectures
51 // with 16-4096 byte cache lines, 128 looks like a good compromise. 51 // with 16-4096 byte cache lines, 128 looks like a good compromise.
52 uint8 pad[128]; 52 uint8 pad[128];
53 } semtable[SEMTABLESZ]; 53 } semtable[SEMTABLESZ];
54 54
55 static SemaRoot * 55 static SemaRoot*
56 semroot(uint32 *addr) 56 semroot(uint32 *addr)
57 { 57 {
58 return &semtable[((uintptr)addr >> 3) % SEMTABLESZ]; 58 return &semtable[((uintptr)addr >> 3) % SEMTABLESZ];
59 } 59 }
60 60
61 static void 61 static void
62 semqueue(SemaRoot *root, uint32 volatile *addr, Sema *s) 62 semqueue(SemaRoot *root, uint32 volatile *addr, Sema *s)
63 { 63 {
64 s->g = g; 64 s->g = g;
65 s->addr = addr; 65 s->addr = addr;
(...skipping 19 matching lines...) Expand all
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->lock); 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)) {
122 » » » runtime·unlock(&root->lock); 124 » » » runtime·xadd(&root->nwait, -1);
123 » » » runtime·xadd(&root->cnt, -1); 125 » » » runtime·unlock(root);
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->lock); 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 (incremented the counter and there is 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-up it). 154 » // Harder case: search for a waiter and wake it.
148 » runtime·lock(&root->lock); 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 = 0;
155 » » » else
156 » » » » semdequeue(root, s);
157 break; 166 break;
158 } 167 }
159 } 168 }
160 » runtime·unlock(&root->lock); 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