2 * Copyright (c) 1998 Daniel Eischen <eischen@vigrid.com>.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. All advertising materials mentioning features or use of this software
14 * must display the following acknowledgement:
15 * This product includes software developed by Daniel Eischen.
16 * 4. Neither the name of the author nor the names of any co-contributors
17 * may be used to endorse or promote products derived from this software
18 * without specific prior written permission.
20 * THIS SOFTWARE IS PROVIDED BY DANIEL EISCHEN AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * $FreeBSD: src/lib/libc_r/uthread/uthread_priority_queue.c,v 1.5.2.3 2002/10/22 14:44:03 fjoe Exp $
33 * $DragonFly: src/lib/libc_r/uthread/uthread_priority_queue.c,v 1.2 2003/06/17 06:26:48 dillon Exp $
36 #include <sys/queue.h>
39 #include "pthread_private.h"
42 static void pq_insert_prio_list(pq_queue_t
*pq
, int prio
);
44 #if defined(_PTHREADS_INVARIANTS)
46 static int _pq_active
= 0;
48 #define _PQ_IN_SCHEDQ (PTHREAD_FLAGS_IN_PRIOQ | PTHREAD_FLAGS_IN_WAITQ | PTHREAD_FLAGS_IN_WORKQ)
50 #define _PQ_SET_ACTIVE() _pq_active = 1
51 #define _PQ_CLEAR_ACTIVE() _pq_active = 0
52 #define _PQ_ASSERT_ACTIVE(msg) do { \
53 if (_pq_active == 0) \
56 #define _PQ_ASSERT_INACTIVE(msg) do { \
57 if (_pq_active != 0) \
60 #define _PQ_ASSERT_IN_WAITQ(thrd, msg) do { \
61 if (((thrd)->flags & PTHREAD_FLAGS_IN_WAITQ) == 0) \
64 #define _PQ_ASSERT_IN_PRIOQ(thrd, msg) do { \
65 if (((thrd)->flags & PTHREAD_FLAGS_IN_PRIOQ) == 0) \
68 #define _PQ_ASSERT_NOT_QUEUED(thrd, msg) do { \
69 if (((thrd)->flags & _PQ_IN_SCHEDQ) != 0) \
72 #define _PQ_ASSERT_PROTECTED(msg) \
73 PTHREAD_ASSERT((_thread_kern_in_sched != 0) || \
74 ((_get_curthread())->sig_defer_count > 0) ||\
75 (_sig_in_handler != 0), msg);
79 #define _PQ_SET_ACTIVE()
80 #define _PQ_CLEAR_ACTIVE()
81 #define _PQ_ASSERT_ACTIVE(msg)
82 #define _PQ_ASSERT_INACTIVE(msg)
83 #define _PQ_ASSERT_IN_WAITQ(thrd, msg)
84 #define _PQ_ASSERT_IN_PRIOQ(thrd, msg)
85 #define _PQ_ASSERT_NOT_QUEUED(thrd, msg)
86 #define _PQ_ASSERT_PROTECTED(msg)
91 _pq_alloc(pq_queue_t
*pq
, int minprio
, int maxprio
)
94 int prioslots
= maxprio
- minprio
+ 1;
99 /* Create the priority queue with (maxprio - minprio + 1) slots: */
100 else if ((pq
->pq_lists
=
101 (pq_list_t
*) malloc(sizeof(pq_list_t
) * prioslots
)) == NULL
)
105 /* Remember the queue size: */
106 pq
->pq_size
= prioslots
;
113 _pq_init(pq_queue_t
*pq
)
117 if ((pq
== NULL
) || (pq
->pq_lists
== NULL
))
121 /* Initialize the queue for each priority slot: */
122 for (i
= 0; i
< pq
->pq_size
; i
++) {
123 TAILQ_INIT(&pq
->pq_lists
[i
].pl_head
);
124 pq
->pq_lists
[i
].pl_prio
= i
;
125 pq
->pq_lists
[i
].pl_queued
= 0;
128 /* Initialize the priority queue: */
129 TAILQ_INIT(&pq
->pq_queue
);
136 _pq_remove(pq_queue_t
*pq
, pthread_t pthread
)
138 int prio
= pthread
->active_priority
;
141 * Make some assertions when debugging is enabled:
143 _PQ_ASSERT_INACTIVE("_pq_remove: pq_active");
145 _PQ_ASSERT_IN_PRIOQ(pthread
, "_pq_remove: Not in priority queue");
146 _PQ_ASSERT_PROTECTED("_pq_remove: prioq not protected!");
149 * Remove this thread from priority list. Note that if
150 * the priority list becomes empty, it is not removed
151 * from the priority queue because another thread may be
152 * added to the priority list (resulting in a needless
153 * removal/insertion). Priority lists are only removed
154 * from the priority queue when _pq_first is called.
156 TAILQ_REMOVE(&pq
->pq_lists
[prio
].pl_head
, pthread
, pqe
);
158 /* This thread is now longer in the priority queue. */
159 pthread
->flags
&= ~PTHREAD_FLAGS_IN_PRIOQ
;
166 _pq_insert_head(pq_queue_t
*pq
, pthread_t pthread
)
171 * Don't insert suspended threads into the priority queue.
172 * The caller is responsible for setting the threads state.
174 if ((pthread
->flags
& PTHREAD_FLAGS_SUSPENDED
) != 0) {
175 /* Make sure the threads state is suspended. */
176 if (pthread
->state
!= PS_SUSPENDED
)
177 PTHREAD_SET_STATE(pthread
, PS_SUSPENDED
);
180 * Make some assertions when debugging is enabled:
182 _PQ_ASSERT_INACTIVE("_pq_insert_head: pq_active");
184 _PQ_ASSERT_NOT_QUEUED(pthread
,
185 "_pq_insert_head: Already in priority queue");
186 _PQ_ASSERT_PROTECTED("_pq_insert_head: prioq not protected!");
188 prio
= pthread
->active_priority
;
189 TAILQ_INSERT_HEAD(&pq
->pq_lists
[prio
].pl_head
, pthread
, pqe
);
190 if (pq
->pq_lists
[prio
].pl_queued
== 0)
191 /* Insert the list into the priority queue: */
192 pq_insert_prio_list(pq
, prio
);
194 /* Mark this thread as being in the priority queue. */
195 pthread
->flags
|= PTHREAD_FLAGS_IN_PRIOQ
;
203 _pq_insert_tail(pq_queue_t
*pq
, pthread_t pthread
)
208 * Don't insert suspended threads into the priority queue.
209 * The caller is responsible for setting the threads state.
211 if ((pthread
->flags
& PTHREAD_FLAGS_SUSPENDED
) != 0) {
212 /* Make sure the threads state is suspended. */
213 if (pthread
->state
!= PS_SUSPENDED
)
214 PTHREAD_SET_STATE(pthread
, PS_SUSPENDED
);
217 * Make some assertions when debugging is enabled:
219 _PQ_ASSERT_INACTIVE("_pq_insert_tail: pq_active");
221 _PQ_ASSERT_NOT_QUEUED(pthread
,
222 "_pq_insert_tail: Already in priority queue");
223 _PQ_ASSERT_PROTECTED("_pq_insert_tail: prioq not protected!");
225 prio
= pthread
->active_priority
;
226 TAILQ_INSERT_TAIL(&pq
->pq_lists
[prio
].pl_head
, pthread
, pqe
);
227 if (pq
->pq_lists
[prio
].pl_queued
== 0)
228 /* Insert the list into the priority queue: */
229 pq_insert_prio_list(pq
, prio
);
231 /* Mark this thread as being in the priority queue. */
232 pthread
->flags
|= PTHREAD_FLAGS_IN_PRIOQ
;
240 _pq_first(pq_queue_t
*pq
)
243 pthread_t pthread
= NULL
;
246 * Make some assertions when debugging is enabled:
248 _PQ_ASSERT_INACTIVE("_pq_first: pq_active");
250 _PQ_ASSERT_PROTECTED("_pq_first: prioq not protected!");
252 while (((pql
= TAILQ_FIRST(&pq
->pq_queue
)) != NULL
) &&
254 if ((pthread
= TAILQ_FIRST(&pql
->pl_head
)) == NULL
) {
256 * The priority list is empty; remove the list
259 TAILQ_REMOVE(&pq
->pq_queue
, pql
, pl_link
);
261 /* Mark the list as not being in the queue: */
263 } else if ((pthread
->flags
& PTHREAD_FLAGS_SUSPENDED
) != 0) {
265 * This thread is suspended; remove it from the
266 * list and ensure its state is suspended.
268 TAILQ_REMOVE(&pql
->pl_head
, pthread
, pqe
);
269 PTHREAD_SET_STATE(pthread
, PS_SUSPENDED
);
271 /* This thread is now longer in the priority queue. */
272 pthread
->flags
&= ~PTHREAD_FLAGS_IN_PRIOQ
;
283 pq_insert_prio_list(pq_queue_t
*pq
, int prio
)
288 * Make some assertions when debugging is enabled:
290 _PQ_ASSERT_ACTIVE("pq_insert_prio_list: pq_active");
291 _PQ_ASSERT_PROTECTED("_pq_insert_prio_list: prioq not protected!");
294 * The priority queue is in descending priority order. Start at
295 * the beginning of the queue and find the list before which the
296 * new list should be inserted.
298 pql
= TAILQ_FIRST(&pq
->pq_queue
);
299 while ((pql
!= NULL
) && (pql
->pl_prio
> prio
))
300 pql
= TAILQ_NEXT(pql
, pl_link
);
302 /* Insert the list: */
304 TAILQ_INSERT_TAIL(&pq
->pq_queue
, &pq
->pq_lists
[prio
], pl_link
);
306 TAILQ_INSERT_BEFORE(pql
, &pq
->pq_lists
[prio
], pl_link
);
308 /* Mark this list as being in the queue: */
309 pq
->pq_lists
[prio
].pl_queued
= 1;
313 _waitq_insert(pthread_t pthread
)
318 * Make some assertions when debugging is enabled:
320 _PQ_ASSERT_INACTIVE("_waitq_insert: pq_active");
322 _PQ_ASSERT_NOT_QUEUED(pthread
, "_waitq_insert: Already in queue");
324 if (pthread
->wakeup_time
.tv_sec
== -1)
325 TAILQ_INSERT_TAIL(&_waitingq
, pthread
, pqe
);
327 tid
= TAILQ_FIRST(&_waitingq
);
328 while ((tid
!= NULL
) && (tid
->wakeup_time
.tv_sec
!= -1) &&
329 ((tid
->wakeup_time
.tv_sec
< pthread
->wakeup_time
.tv_sec
) ||
330 ((tid
->wakeup_time
.tv_sec
== pthread
->wakeup_time
.tv_sec
) &&
331 (tid
->wakeup_time
.tv_nsec
<= pthread
->wakeup_time
.tv_nsec
))))
332 tid
= TAILQ_NEXT(tid
, pqe
);
334 TAILQ_INSERT_TAIL(&_waitingq
, pthread
, pqe
);
336 TAILQ_INSERT_BEFORE(tid
, pthread
, pqe
);
338 pthread
->flags
|= PTHREAD_FLAGS_IN_WAITQ
;
344 _waitq_remove(pthread_t pthread
)
347 * Make some assertions when debugging is enabled:
349 _PQ_ASSERT_INACTIVE("_waitq_remove: pq_active");
351 _PQ_ASSERT_IN_WAITQ(pthread
, "_waitq_remove: Not in queue");
353 TAILQ_REMOVE(&_waitingq
, pthread
, pqe
);
354 pthread
->flags
&= ~PTHREAD_FLAGS_IN_WAITQ
;
360 _waitq_setactive(void)
362 _PQ_ASSERT_INACTIVE("_waitq_setactive: pq_active");
367 _waitq_clearactive(void)
369 _PQ_ASSERT_ACTIVE("_waitq_clearactive: ! pq_active");