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>
38 #include "pthread_private.h"
41 static void pq_insert_prio_list(pq_queue_t *pq, int prio);
43 #if defined(_PTHREADS_INVARIANTS)
45 static int _pq_active = 0;
47 #define _PQ_IN_SCHEDQ (PTHREAD_FLAGS_IN_PRIOQ | PTHREAD_FLAGS_IN_WAITQ | PTHREAD_FLAGS_IN_WORKQ)
49 #define _PQ_SET_ACTIVE() _pq_active = 1
50 #define _PQ_CLEAR_ACTIVE() _pq_active = 0
51 #define _PQ_ASSERT_ACTIVE(msg) do { \
52 if (_pq_active == 0) \
55 #define _PQ_ASSERT_INACTIVE(msg) do { \
56 if (_pq_active != 0) \
59 #define _PQ_ASSERT_IN_WAITQ(thrd, msg) do { \
60 if (((thrd)->flags & PTHREAD_FLAGS_IN_WAITQ) == 0) \
63 #define _PQ_ASSERT_IN_PRIOQ(thrd, msg) do { \
64 if (((thrd)->flags & PTHREAD_FLAGS_IN_PRIOQ) == 0) \
67 #define _PQ_ASSERT_NOT_QUEUED(thrd, msg) do { \
68 if (((thrd)->flags & _PQ_IN_SCHEDQ) != 0) \
71 #define _PQ_ASSERT_PROTECTED(msg) \
72 PTHREAD_ASSERT((_thread_kern_in_sched != 0) || \
73 ((_get_curthread())->sig_defer_count > 0) ||\
74 (_sig_in_handler != 0), msg);
78 #define _PQ_SET_ACTIVE()
79 #define _PQ_CLEAR_ACTIVE()
80 #define _PQ_ASSERT_ACTIVE(msg)
81 #define _PQ_ASSERT_INACTIVE(msg)
82 #define _PQ_ASSERT_IN_WAITQ(thrd, msg)
83 #define _PQ_ASSERT_IN_PRIOQ(thrd, msg)
84 #define _PQ_ASSERT_NOT_QUEUED(thrd, msg)
85 #define _PQ_ASSERT_PROTECTED(msg)
90 _pq_alloc(pq_queue_t *pq, int minprio, int maxprio)
93 int prioslots = maxprio - minprio + 1;
98 /* Create the priority queue with (maxprio - minprio + 1) slots: */
99 else if ((pq->pq_lists =
100 (pq_list_t *) malloc(sizeof(pq_list_t) * prioslots)) == NULL)
104 /* Remember the queue size: */
105 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");
145 _PQ_ASSERT_PROTECTED("_pq_remove: prioq not protected!");
148 * Remove this thread from priority list. Note that if
149 * the priority list becomes empty, it is not removed
150 * from the priority queue because another thread may be
151 * added to the priority list (resulting in a needless
152 * removal/insertion). Priority lists are only removed
153 * from the priority queue when _pq_first is called.
155 TAILQ_REMOVE(&pq->pq_lists[prio].pl_head, pthread, pqe);
157 /* This thread is now longer in the priority queue. */
158 pthread->flags &= ~PTHREAD_FLAGS_IN_PRIOQ;
165 _pq_insert_head(pq_queue_t *pq, pthread_t pthread)
170 * Don't insert suspended threads into the priority queue.
171 * The caller is responsible for setting the threads state.
173 if ((pthread->flags & PTHREAD_FLAGS_SUSPENDED) != 0) {
174 /* Make sure the threads state is suspended. */
175 if (pthread->state != PS_SUSPENDED)
176 PTHREAD_SET_STATE(pthread, PS_SUSPENDED);
179 * Make some assertions when debugging is enabled:
181 _PQ_ASSERT_INACTIVE("_pq_insert_head: pq_active");
183 _PQ_ASSERT_NOT_QUEUED(pthread,
184 "_pq_insert_head: Already in priority queue");
185 _PQ_ASSERT_PROTECTED("_pq_insert_head: prioq not protected!");
187 prio = pthread->active_priority;
188 TAILQ_INSERT_HEAD(&pq->pq_lists[prio].pl_head, pthread, pqe);
189 if (pq->pq_lists[prio].pl_queued == 0)
190 /* Insert the list into the priority queue: */
191 pq_insert_prio_list(pq, prio);
193 /* Mark this thread as being in the priority queue. */
194 pthread->flags |= PTHREAD_FLAGS_IN_PRIOQ;
202 _pq_insert_tail(pq_queue_t *pq, pthread_t pthread)
207 * Don't insert suspended threads into the priority queue.
208 * The caller is responsible for setting the threads state.
210 if ((pthread->flags & PTHREAD_FLAGS_SUSPENDED) != 0) {
211 /* Make sure the threads state is suspended. */
212 if (pthread->state != PS_SUSPENDED)
213 PTHREAD_SET_STATE(pthread, PS_SUSPENDED);
216 * Make some assertions when debugging is enabled:
218 _PQ_ASSERT_INACTIVE("_pq_insert_tail: pq_active");
220 _PQ_ASSERT_NOT_QUEUED(pthread,
221 "_pq_insert_tail: Already in priority queue");
222 _PQ_ASSERT_PROTECTED("_pq_insert_tail: prioq not protected!");
224 prio = pthread->active_priority;
225 TAILQ_INSERT_TAIL(&pq->pq_lists[prio].pl_head, pthread, pqe);
226 if (pq->pq_lists[prio].pl_queued == 0)
227 /* Insert the list into the priority queue: */
228 pq_insert_prio_list(pq, prio);
230 /* Mark this thread as being in the priority queue. */
231 pthread->flags |= PTHREAD_FLAGS_IN_PRIOQ;
239 _pq_first(pq_queue_t *pq)
242 pthread_t pthread = NULL;
245 * Make some assertions when debugging is enabled:
247 _PQ_ASSERT_INACTIVE("_pq_first: pq_active");
249 _PQ_ASSERT_PROTECTED("_pq_first: prioq not protected!");
251 while (((pql = TAILQ_FIRST(&pq->pq_queue)) != NULL) &&
253 if ((pthread = TAILQ_FIRST(&pql->pl_head)) == NULL) {
255 * The priority list is empty; remove the list
258 TAILQ_REMOVE(&pq->pq_queue, pql, pl_link);
260 /* Mark the list as not being in the queue: */
262 } else if ((pthread->flags & PTHREAD_FLAGS_SUSPENDED) != 0) {
264 * This thread is suspended; remove it from the
265 * list and ensure its state is suspended.
267 TAILQ_REMOVE(&pql->pl_head, pthread, pqe);
268 PTHREAD_SET_STATE(pthread, PS_SUSPENDED);
270 /* This thread is now longer in the priority queue. */
271 pthread->flags &= ~PTHREAD_FLAGS_IN_PRIOQ;
282 pq_insert_prio_list(pq_queue_t *pq, int prio)
287 * Make some assertions when debugging is enabled:
289 _PQ_ASSERT_ACTIVE("pq_insert_prio_list: pq_active");
290 _PQ_ASSERT_PROTECTED("_pq_insert_prio_list: prioq not protected!");
293 * The priority queue is in descending priority order. Start at
294 * the beginning of the queue and find the list before which the
295 * new list should be inserted.
297 pql = TAILQ_FIRST(&pq->pq_queue);
298 while ((pql != NULL) && (pql->pl_prio > prio))
299 pql = TAILQ_NEXT(pql, pl_link);
301 /* Insert the list: */
303 TAILQ_INSERT_TAIL(&pq->pq_queue, &pq->pq_lists[prio], pl_link);
305 TAILQ_INSERT_BEFORE(pql, &pq->pq_lists[prio], pl_link);
307 /* Mark this list as being in the queue: */
308 pq->pq_lists[prio].pl_queued = 1;
312 _waitq_insert(pthread_t pthread)
317 * Make some assertions when debugging is enabled:
319 _PQ_ASSERT_INACTIVE("_waitq_insert: pq_active");
321 _PQ_ASSERT_NOT_QUEUED(pthread, "_waitq_insert: Already in queue");
323 if (pthread->wakeup_time.tv_sec == -1)
324 TAILQ_INSERT_TAIL(&_waitingq, pthread, pqe);
326 tid = TAILQ_FIRST(&_waitingq);
327 while ((tid != NULL) && (tid->wakeup_time.tv_sec != -1) &&
328 ((tid->wakeup_time.tv_sec < pthread->wakeup_time.tv_sec) ||
329 ((tid->wakeup_time.tv_sec == pthread->wakeup_time.tv_sec) &&
330 (tid->wakeup_time.tv_nsec <= pthread->wakeup_time.tv_nsec))))
331 tid = TAILQ_NEXT(tid, pqe);
333 TAILQ_INSERT_TAIL(&_waitingq, pthread, pqe);
335 TAILQ_INSERT_BEFORE(tid, pthread, pqe);
337 pthread->flags |= PTHREAD_FLAGS_IN_WAITQ;
343 _waitq_remove(pthread_t pthread)
346 * Make some assertions when debugging is enabled:
348 _PQ_ASSERT_INACTIVE("_waitq_remove: pq_active");
350 _PQ_ASSERT_IN_WAITQ(pthread, "_waitq_remove: Not in queue");
352 TAILQ_REMOVE(&_waitingq, pthread, pqe);
353 pthread->flags &= ~PTHREAD_FLAGS_IN_WAITQ;
359 _waitq_setactive(void)
361 _PQ_ASSERT_INACTIVE("_waitq_setactive: pq_active");
366 _waitq_clearactive(void)
368 _PQ_ASSERT_ACTIVE("_waitq_clearactive: ! pq_active");