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 "namespace.h"
37 #include <sys/queue.h>
40 #include "un-namespace.h"
41 #include "thr_private.h"
44 static void pq_insert_prio_list(pq_queue_t *pq, int prio);
46 #if defined(_PTHREADS_INVARIANTS)
48 #define PQ_IN_SCHEDQ (THR_FLAGS_IN_RUNQ | THR_FLAGS_IN_WAITQ)
50 #define PQ_SET_ACTIVE(pq) (pq)->pq_flags |= PQF_ACTIVE
51 #define PQ_CLEAR_ACTIVE(pq) (pq)->pq_flags &= ~PQF_ACTIVE
52 #define PQ_ASSERT_ACTIVE(pq, msg) do { \
53 if (((pq)->pq_flags & PQF_ACTIVE) == 0) \
56 #define PQ_ASSERT_INACTIVE(pq, msg) do { \
57 if (((pq)->pq_flags & PQF_ACTIVE) != 0) \
60 #define PQ_ASSERT_IN_WAITQ(thrd, msg) do { \
61 if (((thrd)->flags & THR_FLAGS_IN_WAITQ) == 0) \
64 #define PQ_ASSERT_IN_RUNQ(thrd, msg) do { \
65 if (((thrd)->flags & THR_FLAGS_IN_RUNQ) == 0) \
68 #define PQ_ASSERT_NOT_QUEUED(thrd, msg) do { \
69 if (((thrd)->flags & PQ_IN_SCHEDQ) != 0) \
75 #define PQ_SET_ACTIVE(pq)
76 #define PQ_CLEAR_ACTIVE(pq)
77 #define PQ_ASSERT_ACTIVE(pq, msg)
78 #define PQ_ASSERT_INACTIVE(pq, msg)
79 #define PQ_ASSERT_IN_WAITQ(thrd, msg)
80 #define PQ_ASSERT_IN_RUNQ(thrd, msg)
81 #define PQ_ASSERT_NOT_QUEUED(thrd, msg)
86 _pq_alloc(pq_queue_t *pq, int minprio, int maxprio)
89 int prioslots = maxprio - minprio + 1;
94 /* Create the priority queue with (maxprio - minprio + 1) slots: */
95 else if ((pq->pq_lists =
96 (pq_list_t *) malloc(sizeof(pq_list_t) * prioslots)) == NULL)
100 /* Remember the queue size: */
101 pq->pq_size = prioslots;
108 _pq_free(pq_queue_t *pq)
110 if ((pq != NULL) && (pq->pq_lists != NULL))
115 _pq_init(pq_queue_t *pq)
119 if ((pq == NULL) || (pq->pq_lists == NULL))
123 /* Initialize the queue for each priority slot: */
124 for (i = 0; i < pq->pq_size; i++) {
125 TAILQ_INIT(&pq->pq_lists[i].pl_head);
126 pq->pq_lists[i].pl_prio = i;
127 pq->pq_lists[i].pl_queued = 0;
129 /* Initialize the priority queue: */
130 TAILQ_INIT(&pq->pq_queue);
138 _pq_remove(pq_queue_t *pq, pthread_t pthread)
140 int prio = pthread->active_priority;
143 * Make some assertions when debugging is enabled:
145 PQ_ASSERT_INACTIVE(pq, "_pq_remove: pq_active");
147 PQ_ASSERT_IN_RUNQ(pthread, "_pq_remove: Not in priority queue");
150 * Remove this thread from priority list. Note that if
151 * the priority list becomes empty, it is not removed
152 * from the priority queue because another thread may be
153 * added to the priority list (resulting in a needless
154 * removal/insertion). Priority lists are only removed
155 * from the priority queue when _pq_first is called.
157 TAILQ_REMOVE(&pq->pq_lists[prio].pl_head, pthread, pqe);
159 /* This thread is now longer in the priority queue. */
160 pthread->flags &= ~THR_FLAGS_IN_RUNQ;
167 _pq_insert_head(pq_queue_t *pq, pthread_t pthread)
172 * Make some assertions when debugging is enabled:
174 PQ_ASSERT_INACTIVE(pq, "_pq_insert_head: pq_active");
176 PQ_ASSERT_NOT_QUEUED(pthread,
177 "_pq_insert_head: Already in priority queue");
179 prio = pthread->active_priority;
180 TAILQ_INSERT_HEAD(&pq->pq_lists[prio].pl_head, pthread, pqe);
181 if (pq->pq_lists[prio].pl_queued == 0)
182 /* Insert the list into the priority queue: */
183 pq_insert_prio_list(pq, prio);
185 /* Mark this thread as being in the priority queue. */
186 pthread->flags |= THR_FLAGS_IN_RUNQ;
193 _pq_insert_tail(pq_queue_t *pq, pthread_t pthread)
198 * Make some assertions when debugging is enabled:
200 PQ_ASSERT_INACTIVE(pq, "_pq_insert_tail: pq_active");
202 PQ_ASSERT_NOT_QUEUED(pthread,
203 "_pq_insert_tail: Already in priority queue");
205 prio = pthread->active_priority;
206 TAILQ_INSERT_TAIL(&pq->pq_lists[prio].pl_head, pthread, pqe);
207 if (pq->pq_lists[prio].pl_queued == 0)
208 /* Insert the list into the priority queue: */
209 pq_insert_prio_list(pq, prio);
211 /* Mark this thread as being in the priority queue. */
212 pthread->flags |= THR_FLAGS_IN_RUNQ;
219 _pq_first(pq_queue_t *pq)
222 pthread_t pthread = NULL;
225 * Make some assertions when debugging is enabled:
227 PQ_ASSERT_INACTIVE(pq, "_pq_first: pq_active");
230 while (((pql = TAILQ_FIRST(&pq->pq_queue)) != NULL) &&
232 if ((pthread = TAILQ_FIRST(&pql->pl_head)) == NULL) {
234 * The priority list is empty; remove the list
237 TAILQ_REMOVE(&pq->pq_queue, pql, pl_link);
239 /* Mark the list as not being in the queue: */
249 * Select a thread which is allowed to run by debugger, we probably
250 * should merge the function into _pq_first if that function is only
251 * used by scheduler to select a thread.
254 _pq_first_debug(pq_queue_t *pq)
256 pq_list_t *pql, *pqlnext = NULL;
257 pthread_t pthread = NULL;
260 * Make some assertions when debugging is enabled:
262 PQ_ASSERT_INACTIVE(pq, "_pq_first: pq_active");
265 for (pql = TAILQ_FIRST(&pq->pq_queue);
266 pql != NULL && pthread == NULL; pql = pqlnext) {
267 if ((pthread = TAILQ_FIRST(&pql->pl_head)) == NULL) {
269 * The priority list is empty; remove the list
272 pqlnext = TAILQ_NEXT(pql, pl_link);
273 TAILQ_REMOVE(&pq->pq_queue, pql, pl_link);
275 /* Mark the list as not being in the queue: */
279 * note there may be a suspension event during this
280 * test, If TMDF_SUSPEND is set after we tested it,
281 * we will run the thread, this seems be a problem,
282 * fortunatly, when we are being debugged, all context
283 * switch will be done by kse_switchin, that is a
284 * syscall, kse_switchin will check the flag again,
285 * the thread will be returned via upcall, so next
286 * time, UTS won't run the thread.
288 while (pthread != NULL && !DBG_CAN_RUN(pthread)) {
289 pthread = TAILQ_NEXT(pthread, pqe);
292 pqlnext = TAILQ_NEXT(pql, pl_link);
301 pq_insert_prio_list(pq_queue_t *pq, int prio)
306 * Make some assertions when debugging is enabled:
308 PQ_ASSERT_ACTIVE(pq, "pq_insert_prio_list: pq_active");
311 * The priority queue is in descending priority order. Start at
312 * the beginning of the queue and find the list before which the
313 * new list should be inserted.
315 pql = TAILQ_FIRST(&pq->pq_queue);
316 while ((pql != NULL) && (pql->pl_prio > prio))
317 pql = TAILQ_NEXT(pql, pl_link);
319 /* Insert the list: */
321 TAILQ_INSERT_TAIL(&pq->pq_queue, &pq->pq_lists[prio], pl_link);
323 TAILQ_INSERT_BEFORE(pql, &pq->pq_lists[prio], pl_link);
325 /* Mark this list as being in the queue: */
326 pq->pq_lists[prio].pl_queued = 1;