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
35 #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) \
75 #define _PQ_SET_ACTIVE()
76 #define _PQ_CLEAR_ACTIVE()
77 #define _PQ_ASSERT_ACTIVE(msg)
78 #define _PQ_ASSERT_INACTIVE(msg)
79 #define _PQ_ASSERT_IN_WAITQ(thrd, msg)
80 #define _PQ_ASSERT_IN_PRIOQ(thrd, msg)
81 #define _PQ_ASSERT_NOT_QUEUED(thrd, msg)
82 #define _PQ_CHECK_PRIO()
88 _pq_alloc(pq_queue_t *pq, int minprio, int maxprio)
91 int prioslots = maxprio - minprio + 1;
96 /* Create the priority queue with (maxprio - minprio + 1) slots: */
97 else if ((pq->pq_lists =
98 (pq_list_t *) malloc(sizeof(pq_list_t) * prioslots)) == NULL)
102 /* Remember the queue size: */
103 pq->pq_size = prioslots;
112 _pq_init(pq_queue_t *pq)
116 if ((pq == NULL) || (pq->pq_lists == NULL))
120 /* Initialize the queue for each priority slot: */
121 for (i = 0; i < pq->pq_size; i++) {
122 TAILQ_INIT(&pq->pq_lists[i].pl_head);
123 pq->pq_lists[i].pl_prio = i;
124 pq->pq_lists[i].pl_queued = 0;
127 /* Initialize the priority queue: */
128 TAILQ_INIT(&pq->pq_queue);
135 _pq_remove(pq_queue_t *pq, pthread_t pthread)
137 int prio = pthread->active_priority;
140 * Make some assertions when debugging is enabled:
142 _PQ_ASSERT_INACTIVE("_pq_remove: pq_active");
144 _PQ_ASSERT_IN_PRIOQ(pthread, "_pq_remove: Not in priority queue");
147 * Remove this thread from priority list. Note that if
148 * the priority list becomes empty, it is not removed
149 * from the priority queue because another thread may be
150 * added to the priority list (resulting in a needless
151 * removal/insertion). Priority lists are only removed
152 * from the priority queue when _pq_first is called.
154 TAILQ_REMOVE(&pq->pq_lists[prio].pl_head, pthread, pqe);
156 /* This thread is now longer in the priority queue. */
157 pthread->flags &= ~PTHREAD_FLAGS_IN_PRIOQ;
164 _pq_insert_head(pq_queue_t *pq, pthread_t pthread)
166 int prio = pthread->active_priority;
169 * Make some assertions when debugging is enabled:
171 _PQ_ASSERT_INACTIVE("_pq_insert_head: pq_active");
173 _PQ_ASSERT_NOT_QUEUED(pthread,
174 "_pq_insert_head: Already in priority queue");
176 TAILQ_INSERT_HEAD(&pq->pq_lists[prio].pl_head, pthread, pqe);
177 if (pq->pq_lists[prio].pl_queued == 0)
178 /* Insert the list into the priority queue: */
179 pq_insert_prio_list(pq, prio);
181 /* Mark this thread as being in the priority queue. */
182 pthread->flags |= PTHREAD_FLAGS_IN_PRIOQ;
189 _pq_insert_tail(pq_queue_t *pq, pthread_t pthread)
191 int prio = pthread->active_priority;
194 * Make some assertions when debugging is enabled:
196 _PQ_ASSERT_INACTIVE("_pq_insert_tail: pq_active");
198 _PQ_ASSERT_NOT_QUEUED(pthread,
199 "_pq_insert_tail: Already in priority queue");
201 TAILQ_INSERT_TAIL(&pq->pq_lists[prio].pl_head, pthread, pqe);
202 if (pq->pq_lists[prio].pl_queued == 0)
203 /* Insert the list into the priority queue: */
204 pq_insert_prio_list(pq, prio);
206 /* Mark this thread as being in the priority queue. */
207 pthread->flags |= PTHREAD_FLAGS_IN_PRIOQ;
214 _pq_first(pq_queue_t *pq)
217 pthread_t pthread = NULL;
220 * Make some assertions when debugging is enabled:
222 _PQ_ASSERT_INACTIVE("_pq_first: pq_active");
225 while (((pql = TAILQ_FIRST(&pq->pq_queue)) != NULL) &&
227 if ((pthread = TAILQ_FIRST(&pql->pl_head)) == NULL) {
229 * The priority list is empty; remove the list
232 TAILQ_REMOVE(&pq->pq_queue, pql, pl_link);
234 /* Mark the list as not being in the queue: */
245 pq_insert_prio_list(pq_queue_t *pq, int prio)
250 * Make some assertions when debugging is enabled:
252 _PQ_ASSERT_ACTIVE("pq_insert_prio_list: pq_active");
255 * The priority queue is in descending priority order. Start at
256 * the beginning of the queue and find the list before which the
257 * new list should be inserted.
259 pql = TAILQ_FIRST(&pq->pq_queue);
260 while ((pql != NULL) && (pql->pl_prio > prio))
261 pql = TAILQ_NEXT(pql, pl_link);
263 /* Insert the list: */
265 TAILQ_INSERT_TAIL(&pq->pq_queue, &pq->pq_lists[prio], pl_link);
267 TAILQ_INSERT_BEFORE(pql, &pq->pq_lists[prio], pl_link);
269 /* Mark this list as being in the queue: */
270 pq->pq_lists[prio].pl_queued = 1;
273 #if defined(_PTHREADS_INVARIANTS)
275 _waitq_insert(pthread_t pthread)
280 * Make some assertions when debugging is enabled:
282 _PQ_ASSERT_INACTIVE("_waitq_insert: pq_active");
284 _PQ_ASSERT_NOT_QUEUED(pthread, "_waitq_insert: Already in queue");
286 if (pthread->wakeup_time.tv_sec == -1)
287 TAILQ_INSERT_TAIL(&_waitingq, pthread, pqe);
289 tid = TAILQ_FIRST(&_waitingq);
290 while ((tid != NULL) && (tid->wakeup_time.tv_sec != -1) &&
291 ((tid->wakeup_time.tv_sec < pthread->wakeup_time.tv_sec) ||
292 ((tid->wakeup_time.tv_sec == pthread->wakeup_time.tv_sec) &&
293 (tid->wakeup_time.tv_nsec <= pthread->wakeup_time.tv_nsec))))
294 tid = TAILQ_NEXT(tid, pqe);
296 TAILQ_INSERT_TAIL(&_waitingq, pthread, pqe);
298 TAILQ_INSERT_BEFORE(tid, pthread, pqe);
300 pthread->flags |= PTHREAD_FLAGS_IN_WAITQ;
306 _waitq_remove(pthread_t pthread)
309 * Make some assertions when debugging is enabled:
311 _PQ_ASSERT_INACTIVE("_waitq_remove: pq_active");
313 _PQ_ASSERT_IN_WAITQ(pthread, "_waitq_remove: Not in queue");
315 TAILQ_REMOVE(&_waitingq, pthread, pqe);
316 pthread->flags &= ~PTHREAD_FLAGS_IN_WAITQ;
322 _waitq_setactive(void)
324 _PQ_ASSERT_INACTIVE("_waitq_setactive: pq_active");
329 _waitq_clearactive(void)
331 _PQ_ASSERT_ACTIVE("_waitq_clearactive: ! pq_active");