1 /* $OpenBSD: uthread_priority_queue.c,v 1.4 2001/09/04 23:28:31 fgsch Exp $ */
2 /*
3 * Copyright (c) 1998 Daniel Eischen <eischen@vigrid.com>.
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * 3. All advertising materials mentioning features or use of this software
15 * must display the following acknowledgement:
16 * This product includes software developed by Daniel Eischen.
17 * 4. Neither the name of the author nor the names of any co-contributors
18 * may be used to endorse or promote products derived from this software
19 * without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY DANIEL EISCHEN AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 *
33 * $FreeBSD: uthread_priority_queue.c,v 1.3 1999/08/28 00:03:43 peter Exp $
34 */
35 #include <stdlib.h>
36 #include <sys/queue.h>
37 #include <string.h>
38 #ifdef _THREAD_SAFE
39 #include <pthread.h>
40 #include "pthread_private.h"
41
42 /* Prototypes: */
43 static void pq_insert_prio_list(pq_queue_t *pq, int prio);
44
45 #if defined(_PTHREADS_INVARIANTS)
46
47 static int _pq_active = 0;
48
49 #define _PQ_IN_SCHEDQ (PTHREAD_FLAGS_IN_PRIOQ | PTHREAD_FLAGS_IN_WAITQ | PTHREAD_FLAGS_IN_WORKQ)
50
51 #define _PQ_SET_ACTIVE() _pq_active = 1
52 #define _PQ_CLEAR_ACTIVE() _pq_active = 0
53 #define _PQ_ASSERT_ACTIVE(msg) do { \
54 if (_pq_active == 0) \
55 PANIC(msg); \
56 } while (0)
57 #define _PQ_ASSERT_INACTIVE(msg) do { \
58 if (_pq_active != 0) \
59 PANIC(msg); \
60 } while (0)
61 #define _PQ_ASSERT_IN_WAITQ(thrd, msg) do { \
62 if (((thrd)->flags & PTHREAD_FLAGS_IN_WAITQ) == 0) \
63 PANIC(msg); \
64 } while (0)
65 #define _PQ_ASSERT_IN_PRIOQ(thrd, msg) do { \
66 if (((thrd)->flags & PTHREAD_FLAGS_IN_PRIOQ) == 0) \
67 PANIC(msg); \
68 } while (0)
69 #define _PQ_ASSERT_NOT_QUEUED(thrd, msg) do { \
70 if (((thrd)->flags & _PQ_IN_SCHEDQ) != 0) \
71 PANIC(msg); \
72 } while (0)
73
74 #else
75
76 #define _PQ_SET_ACTIVE()
77 #define _PQ_CLEAR_ACTIVE()
78 #define _PQ_ASSERT_ACTIVE(msg)
79 #define _PQ_ASSERT_INACTIVE(msg)
80 #define _PQ_ASSERT_IN_WAITQ(thrd, msg)
81 #define _PQ_ASSERT_IN_PRIOQ(thrd, msg)
82 #define _PQ_ASSERT_NOT_QUEUED(thrd, msg)
83
84 #endif
85
86 int
_pq_alloc(pq_queue_t * pq,int minprio,int maxprio)87 _pq_alloc(pq_queue_t *pq, int minprio, int maxprio)
88 {
89 int ret = 0;
90 int prioslots = maxprio - minprio + 1;
91
92 if (pq == NULL)
93 ret = -1;
94
95 /* Create the priority queue with (maxprio - minprio + 1) slots: */
96 else if ((pq->pq_lists =
97 (pq_list_t *) malloc(sizeof(pq_list_t) * prioslots)) == NULL)
98 ret = -1;
99
100 else {
101 /* Remember the queue size: */
102 pq->pq_size = prioslots;
103 ret = _pq_init(pq);
104 }
105 return (ret);
106 }
107
108 int
_pq_init(pq_queue_t * pq)109 _pq_init(pq_queue_t *pq)
110 {
111 int i, ret = 0;
112
113 if ((pq == NULL) || (pq->pq_lists == NULL))
114 ret = -1;
115
116 else {
117 /* Initialize the queue for each priority slot: */
118 for (i = 0; i < pq->pq_size; i++) {
119 TAILQ_INIT(&pq->pq_lists[i].pl_head);
120 pq->pq_lists[i].pl_prio = i;
121 pq->pq_lists[i].pl_queued = 0;
122 }
123
124 /* Initialize the priority queue: */
125 TAILQ_INIT(&pq->pq_queue);
126 _PQ_CLEAR_ACTIVE();
127 }
128 return (ret);
129 }
130
131 void
_pq_remove(pq_queue_t * pq,pthread_t pthread)132 _pq_remove(pq_queue_t *pq, pthread_t pthread)
133 {
134 int prio = pthread->active_priority;
135
136 /*
137 * Make some assertions when debugging is enabled:
138 */
139 _PQ_ASSERT_INACTIVE("_pq_remove: pq_active");
140 _PQ_SET_ACTIVE();
141 _PQ_ASSERT_IN_PRIOQ(pthread, "_pq_remove: Not in priority queue");
142
143 /*
144 * Remove this thread from priority list. Note that if
145 * the priority list becomes empty, it is not removed
146 * from the priority queue because another thread may be
147 * added to the priority list (resulting in a needless
148 * removal/insertion). Priority lists are only removed
149 * from the priority queue when _pq_first is called.
150 */
151 TAILQ_REMOVE(&pq->pq_lists[prio].pl_head, pthread, pqe);
152
153 /* This thread is now longer in the priority queue. */
154 pthread->flags &= ~PTHREAD_FLAGS_IN_PRIOQ;
155
156 _PQ_CLEAR_ACTIVE();
157 }
158
159
160 void
_pq_insert_head(pq_queue_t * pq,pthread_t pthread)161 _pq_insert_head(pq_queue_t *pq, pthread_t pthread)
162 {
163 int prio = pthread->active_priority;
164
165 /*
166 * Make some assertions when debugging is enabled:
167 */
168 _PQ_ASSERT_INACTIVE("_pq_insert_head: pq_active");
169 _PQ_SET_ACTIVE();
170 _PQ_ASSERT_NOT_QUEUED(pthread,
171 "_pq_insert_head: Already in priority queue");
172
173 TAILQ_INSERT_HEAD(&pq->pq_lists[prio].pl_head, pthread, pqe);
174 if (pq->pq_lists[prio].pl_queued == 0)
175 /* Insert the list into the priority queue: */
176 pq_insert_prio_list(pq, prio);
177
178 /* Mark this thread as being in the priority queue. */
179 pthread->flags |= PTHREAD_FLAGS_IN_PRIOQ;
180
181 _PQ_CLEAR_ACTIVE();
182 }
183
184
185 void
_pq_insert_tail(pq_queue_t * pq,pthread_t pthread)186 _pq_insert_tail(pq_queue_t *pq, pthread_t pthread)
187 {
188 int prio = pthread->active_priority;
189
190 /*
191 * Make some assertions when debugging is enabled:
192 */
193 _PQ_ASSERT_INACTIVE("_pq_insert_tail: pq_active");
194 _PQ_SET_ACTIVE();
195 _PQ_ASSERT_NOT_QUEUED(pthread,
196 "_pq_insert_tail: Already in priority queue");
197
198 TAILQ_INSERT_TAIL(&pq->pq_lists[prio].pl_head, pthread, pqe);
199 if (pq->pq_lists[prio].pl_queued == 0)
200 /* Insert the list into the priority queue: */
201 pq_insert_prio_list(pq, prio);
202
203 /* Mark this thread as being in the priority queue. */
204 pthread->flags |= PTHREAD_FLAGS_IN_PRIOQ;
205
206 _PQ_CLEAR_ACTIVE();
207 }
208
209
210 pthread_t
_pq_first(pq_queue_t * pq)211 _pq_first(pq_queue_t *pq)
212 {
213 pq_list_t *pql;
214 pthread_t pthread = NULL;
215
216 /*
217 * Make some assertions when debugging is enabled:
218 */
219 _PQ_ASSERT_INACTIVE("_pq_first: pq_active");
220 _PQ_SET_ACTIVE();
221
222 while (((pql = TAILQ_FIRST(&pq->pq_queue)) != NULL) &&
223 (pthread == NULL)) {
224 if ((pthread = TAILQ_FIRST(&pql->pl_head)) == NULL) {
225 /*
226 * The priority list is empty; remove the list
227 * from the queue.
228 */
229 TAILQ_REMOVE(&pq->pq_queue, pql, pl_link);
230
231 /* Mark the list as not being in the queue: */
232 pql->pl_queued = 0;
233 }
234 }
235
236 _PQ_CLEAR_ACTIVE();
237 return (pthread);
238 }
239
240
241 static void
pq_insert_prio_list(pq_queue_t * pq,int prio)242 pq_insert_prio_list(pq_queue_t *pq, int prio)
243 {
244 pq_list_t *pql;
245
246 /*
247 * Make some assertions when debugging is enabled:
248 */
249 _PQ_ASSERT_ACTIVE("pq_insert_prio_list: pq_active");
250
251 /*
252 * The priority queue is in descending priority order. Start at
253 * the beginning of the queue and find the list before which the
254 * new list should be inserted.
255 */
256 pql = TAILQ_FIRST(&pq->pq_queue);
257 while ((pql != NULL) && (pql->pl_prio > prio))
258 pql = TAILQ_NEXT(pql, pl_link);
259
260 /* Insert the list: */
261 if (pql == NULL)
262 TAILQ_INSERT_TAIL(&pq->pq_queue, &pq->pq_lists[prio], pl_link);
263 else
264 TAILQ_INSERT_BEFORE(pql, &pq->pq_lists[prio], pl_link);
265
266 /* Mark this list as being in the queue: */
267 pq->pq_lists[prio].pl_queued = 1;
268 }
269
270 void
_waitq_insert(pthread_t pthread)271 _waitq_insert(pthread_t pthread)
272 {
273 pthread_t tid;
274
275 /*
276 * Make some assertions when debugging is enabled:
277 */
278 _PQ_ASSERT_INACTIVE("_waitq_insert: pq_active");
279 _PQ_SET_ACTIVE();
280 _PQ_ASSERT_NOT_QUEUED(pthread, "_waitq_insert: Already in queue");
281
282 if (pthread->wakeup_time.tv_sec == -1)
283 TAILQ_INSERT_TAIL(&_waitingq, pthread, pqe);
284 else {
285 tid = TAILQ_FIRST(&_waitingq);
286 while ((tid != NULL) && (tid->wakeup_time.tv_sec != -1) &&
287 ((tid->wakeup_time.tv_sec < pthread->wakeup_time.tv_sec) ||
288 ((tid->wakeup_time.tv_sec == pthread->wakeup_time.tv_sec) &&
289 (tid->wakeup_time.tv_nsec <= pthread->wakeup_time.tv_nsec))))
290 tid = TAILQ_NEXT(tid, pqe);
291 if (tid == NULL)
292 TAILQ_INSERT_TAIL(&_waitingq, pthread, pqe);
293 else
294 TAILQ_INSERT_BEFORE(tid, pthread, pqe);
295 }
296 pthread->flags |= PTHREAD_FLAGS_IN_WAITQ;
297
298 _PQ_CLEAR_ACTIVE();
299 }
300
301 void
_waitq_remove(pthread_t pthread)302 _waitq_remove(pthread_t pthread)
303 {
304 /*
305 * Make some assertions when debugging is enabled:
306 */
307 _PQ_ASSERT_INACTIVE("_waitq_remove: pq_active");
308 _PQ_SET_ACTIVE();
309 _PQ_ASSERT_IN_WAITQ(pthread, "_waitq_remove: Not in queue");
310
311 TAILQ_REMOVE(&_waitingq, pthread, pqe);
312 pthread->flags &= ~PTHREAD_FLAGS_IN_WAITQ;
313
314 _PQ_CLEAR_ACTIVE();
315 }
316
317 void
_waitq_setactive(void)318 _waitq_setactive(void)
319 {
320 _PQ_ASSERT_INACTIVE("_waitq_setactive: pq_active");
321 _PQ_SET_ACTIVE();
322 }
323
324 void
_waitq_clearactive(void)325 _waitq_clearactive(void)
326 {
327 _PQ_ASSERT_ACTIVE("_waitq_clearactive: ! pq_active");
328 _PQ_CLEAR_ACTIVE();
329 }
330 #endif
331