OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libgo/] [runtime/] [sema.goc] - Blame information for rev 764

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 747 jeremybenn
// Copyright 2009 The Go Authors. All rights reserved.
2
// Use of this source code is governed by a BSD-style
3
// license that can be found in the LICENSE file.
4
 
5
// Semaphore implementation exposed to Go.
6
// Intended use is provide a sleep and wakeup
7
// primitive that can be used in the contended case
8
// of other synchronization primitives.
9
// Thus it targets the same goal as Linux's futex,
10
// but it has much simpler semantics.
11
//
12
// That is, don't think of these as semaphores.
13
// Think of them as a way to implement sleep and wakeup
14
// such that every sleep is paired with a single wakeup,
15
// even if, due to races, the wakeup happens before the sleep.
16
//
17
// See Mullender and Cox, ``Semaphores in Plan 9,''
18
// http://swtch.com/semaphore.pdf
19
 
20
package runtime
21
#include "runtime.h"
22
#include "arch.h"
23
 
24
typedef struct Sema Sema;
25
struct Sema
26
{
27
        uint32 volatile *addr;
28
        G *g;
29
        Sema *prev;
30
        Sema *next;
31
};
32
 
33
typedef struct SemaRoot SemaRoot;
34
struct SemaRoot
35
{
36
        Lock;
37
        Sema *head;
38
        Sema *tail;
39
        // Number of waiters. Read w/o the lock.
40
        uint32 volatile nwait;
41
};
42
 
43
// Prime to not correlate with any user patterns.
44
#define SEMTABLESZ 251
45
 
46
static union
47
{
48
        SemaRoot;
49
        uint8 pad[CacheLineSize];
50
} semtable[SEMTABLESZ];
51
 
52
static SemaRoot*
53
semroot(uint32 volatile *addr)
54
{
55
        return &semtable[((uintptr)addr >> 3) % SEMTABLESZ];
56
}
57
 
58
static void
59
semqueue(SemaRoot *root, uint32 volatile *addr, Sema *s)
60
{
61
        s->g = runtime_g();
62
        s->addr = addr;
63
        s->next = nil;
64
        s->prev = root->tail;
65
        if(root->tail)
66
                root->tail->next = s;
67
        else
68
                root->head = s;
69
        root->tail = s;
70
}
71
 
72
static void
73
semdequeue(SemaRoot *root, Sema *s)
74
{
75
        if(s->next)
76
                s->next->prev = s->prev;
77
        else
78
                root->tail = s->prev;
79
        if(s->prev)
80
                s->prev->next = s->next;
81
        else
82
                root->head = s->next;
83
        s->prev = nil;
84
        s->next = nil;
85
}
86
 
87
static int32
88
cansemacquire(uint32 volatile *addr)
89
{
90
        uint32 v;
91
 
92
        while((v = runtime_atomicload(addr)) > 0)
93
                if(runtime_cas(addr, v, v-1))
94
                        return 1;
95
        return 0;
96
}
97
 
98
void
99
runtime_semacquire(uint32 volatile *addr)
100
{
101
        G *g;
102
        Sema s;
103
        SemaRoot *root;
104
 
105
        // Easy case.
106
        if(cansemacquire(addr))
107
                return;
108
 
109
        // Harder case:
110
        //      increment waiter count
111
        //      try cansemacquire one more time, return if succeeded
112
        //      enqueue itself as a waiter
113
        //      sleep
114
        //      (waiter descriptor is dequeued by signaler)
115
        g = runtime_g();
116
        root = semroot(addr);
117
        for(;;) {
118
 
119
                runtime_lock(root);
120
                // Add ourselves to nwait to disable "easy case" in semrelease.
121
                runtime_xadd(&root->nwait, 1);
122
                // Check cansemacquire to avoid missed wakeup.
123
                if(cansemacquire(addr)) {
124
                        runtime_xadd(&root->nwait, -1);
125
                        runtime_unlock(root);
126
                        return;
127
                }
128
                // Any semrelease after the cansemacquire knows we're waiting
129
                // (we set nwait above), so go to sleep.
130
                semqueue(root, addr, &s);
131
                g->status = Gwaiting;
132
                g->waitreason = "semacquire";
133
                runtime_unlock(root);
134
                runtime_gosched();
135
                if(cansemacquire(addr))
136
                        return;
137
        }
138
}
139
 
140
void
141
runtime_semrelease(uint32 volatile *addr)
142
{
143
        Sema *s;
144
        SemaRoot *root;
145
 
146
        root = semroot(addr);
147
        runtime_xadd(addr, 1);
148
 
149
        // Easy case: no waiters?
150
        // This check must happen after the xadd, to avoid a missed wakeup
151
        // (see loop in semacquire).
152
        if(runtime_atomicload(&root->nwait) == 0)
153
                return;
154
 
155
        // Harder case: search for a waiter and wake it.
156
        runtime_lock(root);
157
        if(runtime_atomicload(&root->nwait) == 0) {
158
                // The count is already consumed by another goroutine,
159
                // so no need to wake up another goroutine.
160
                runtime_unlock(root);
161
                return;
162
        }
163
        for(s = root->head; s; s = s->next) {
164
                if(s->addr == addr) {
165
                        runtime_xadd(&root->nwait, -1);
166
                        semdequeue(root, s);
167
                        break;
168
                }
169
        }
170
        runtime_unlock(root);
171
        if(s)
172
                runtime_ready(s->g);
173
}
174
 
175
func Semacquire(addr *uint32) {
176
        runtime_semacquire(addr);
177
}
178
 
179
func Semrelease(addr *uint32) {
180
        runtime_semrelease(addr);
181
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.