1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
|
/*
* Copyright (c) 2017 Richard Braun.
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*
*
* Priority propagation capable sleep queues.
*
* Turnstiles are used to build sleeping synchronization primitives where
* ownership applies, such as mutexes. They allow threads with different
* priorities to contend on the same synchronization object without
* unbounded priority inversion.
*/
#ifndef KERN_TURNSTILE_H
#define KERN_TURNSTILE_H
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <kern/init.h>
#include <kern/plist.h>
#include <kern/spinlock.h>
#include <kern/thread.h>
#include <kern/turnstile_types.h>
struct turnstile;
/*
* Turnstile thread data.
*/
struct turnstile_td;
static inline bool
turnstile_td_locked(const struct turnstile_td *td)
{
return spinlock_locked(&td->lock);
}
/*
* Initialize turnstile thread data.
*/
static inline void
turnstile_td_init(struct turnstile_td *td)
{
spinlock_init(&td->lock);
td->turnstile = NULL;
td->waiter = NULL;
plist_init(&td->owned_turnstiles);
td->top_global_priority = 0;
}
/*
* Turnstile thread data locking functions.
*/
static inline void
turnstile_td_lock(struct turnstile_td *td)
{
spinlock_lock(&td->lock);
}
static inline int
turnstile_td_trylock(struct turnstile_td *td)
{
return spinlock_trylock(&td->lock);
}
static inline void
turnstile_td_unlock(struct turnstile_td *td)
{
spinlock_unlock(&td->lock);
}
/*
* Functions managing the turnstile a thread is sleeping in.
*/
static inline void
turnstile_td_set_turnstile(struct turnstile_td *td,
struct turnstile *turnstile)
{
td->turnstile = turnstile;
}
static inline struct turnstile *
turnstile_td_get_turnstile(const struct turnstile_td *td)
{
return td->turnstile;
}
/*
* Propagate priority starting at the thread containing the given thread data.
*/
void turnstile_td_propagate_priority(struct turnstile_td *td);
/*
* Create/destroy a turnstile.
*/
struct turnstile * turnstile_create(void);
void turnstile_destroy(struct turnstile *turnstile);
/*
* Acquire/release a turnstile.
*
* Acquiring a turnstile serializes all access and disables preemption.
*/
struct turnstile * turnstile_acquire(const void *sync_obj);
void turnstile_release(struct turnstile *turnstile);
/*
* Lend/return a turnstile.
*
* A thread lends its private turnstile to the turnstile module in
* order to prepare its sleep. The turnstile obtained on lending
* is either the thread's turnstile, or an already existing turnstile
* for this synchronization object if another thread is waiting.
*
* When multiple threads are waiting on the same turnstile, the extra
* turnstiles lent are kept in an internal free list, used when threads
* are awoken to return a turnstile to them.
*
* Note that the turnstile returned may not be the one lent.
*
* The turnstile obtained when lending is automatically acquired.
*/
struct turnstile * turnstile_lend(const void *sync_obj);
void turnstile_return(struct turnstile *turnstile);
/*
* Return true if the given turnstile has no waiters.
*
* The turnstile must be acquired when calling this function.
*/
bool turnstile_empty(const struct turnstile *turnstile);
/*
* Wait for a wake up on the given turnstile.
*
* The turnstile must be lent when calling this function. It is
* released and later reacquired before returning from this function.
*
* Unless a timeout occurs, the calling thread is considered a waiter
* as long as it didn't reacquire the turnstile. This means that signalling
* a turnstile has no immediate visible effect on the number of waiters,
* e.g. if a single thread is waiting and another signals the turnstile,
* the turnstile is not immediately considered empty.
*
* If owner isn't NULL, it must refer to the thread currently owning
* the associated synchronization object. The priority of the caller
* is propagated to the chain of turnstiles and owners as necessary
* to prevent unbounded priority inversion.
*
* When bounding the duration of the wait, the caller must pass an absolute
* time in ticks, and ETIMEDOUT is returned if that time is reached before
* the turnstile is signalled. In addition, if a timeout occurs, the calling
* thread isn't considered a waiter any more. Other threads may be able to
* acquire the turnstile and consider it empty, despite the fact that threads
* may not have returned from this function yet.
*/
void turnstile_wait(struct turnstile *turnstile, const char *wchan,
struct thread *owner);
int turnstile_timedwait(struct turnstile *turnstile, const char *wchan,
struct thread *owner, uint64_t ticks);
/*
* Wake up a thread waiting on the given turnstile, if any.
*
* The turnstile must be acquired when calling this function.
* Since a turnstile must be lent (and in turn is automatically
* acquired) when waiting, and acquired in order to signal it,
* wake-ups are serialized and cannot be missed.
*/
void turnstile_signal(struct turnstile *turnstile);
/*
* Own/disown a turnstile.
*
* The turnstile must be lent when taking ownership, acquired when
* releasing it.
*
* Ownership must be updated atomically with regard to the ownership
* of the associated synchronization object.
*/
void turnstile_own(struct turnstile *turnstile);
void turnstile_disown(struct turnstile *turnstile);
/*
* This init operation provides :
* - turnstile creation
* - module fully initialized
*/
INIT_OP_DECLARE(turnstile_setup);
#endif /* KERN_TURNSTILE_H */
|
