1/*
2 * Copyright (c) 1998 Daniel Eischen <eischen@vigrid.com>.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
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.
19 *
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
30 * SUCH DAMAGE.
31 *
32 * $FreeBSD$
33 */
34
35#include "namespace.h"
36#include <stdlib.h>
37#include <sys/queue.h>
38#include <string.h>
39#include <pthread.h>
40#include "un-namespace.h"
41#include "thr_private.h"
42
43/* Prototypes: */
44static void pq_insert_prio_list(pq_queue_t *pq, int prio);
45
46#if defined(_PTHREADS_INVARIANTS)
47
48#define PQ_IN_SCHEDQ	(THR_FLAGS_IN_RUNQ | THR_FLAGS_IN_WAITQ)
49
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)		\
54		PANIC(msg);				\
55} while (0)
56#define PQ_ASSERT_INACTIVE(pq, msg)	do {		\
57	if (((pq)->pq_flags & PQF_ACTIVE) != 0)		\
58		PANIC(msg);				\
59} while (0)
60#define PQ_ASSERT_IN_WAITQ(thrd, msg)	do {		\
61	if (((thrd)->flags & THR_FLAGS_IN_WAITQ) == 0) \
62		PANIC(msg);				\
63} while (0)
64#define PQ_ASSERT_IN_RUNQ(thrd, msg)	do {		\
65	if (((thrd)->flags & THR_FLAGS_IN_RUNQ) == 0) \
66		PANIC(msg);				\
67} while (0)
68#define PQ_ASSERT_NOT_QUEUED(thrd, msg) do {		\
69	if (((thrd)->flags & PQ_IN_SCHEDQ) != 0)	\
70		PANIC(msg);				\
71} while (0)
72
73#else
74
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)
82
83#endif
84
85int
86_pq_alloc(pq_queue_t *pq, int minprio, int maxprio)
87{
88	int ret = 0;
89	int prioslots = maxprio - minprio + 1;
90
91	if (pq == NULL)
92		ret = -1;
93
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)
97		ret = -1;
98
99	else {
100		/* Remember the queue size: */
101		pq->pq_size = prioslots;
102		ret = _pq_init(pq);
103	}
104	return (ret);
105}
106
107void
108_pq_free(pq_queue_t *pq)
109{
110	if ((pq != NULL) && (pq->pq_lists != NULL))
111		free(pq->pq_lists);
112}
113
114int
115_pq_init(pq_queue_t *pq)
116{
117	int i, ret = 0;
118
119	if ((pq == NULL) || (pq->pq_lists == NULL))
120		ret = -1;
121
122	else {
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;
128		}
129		/* Initialize the priority queue: */
130		TAILQ_INIT(&pq->pq_queue);
131		pq->pq_flags = 0;
132		pq->pq_threads = 0;
133	}
134	return (ret);
135}
136
137void
138_pq_remove(pq_queue_t *pq, pthread_t pthread)
139{
140	int prio = pthread->active_priority;
141
142	/*
143	 * Make some assertions when debugging is enabled:
144	 */
145	PQ_ASSERT_INACTIVE(pq, "_pq_remove: pq_active");
146	PQ_SET_ACTIVE(pq);
147	PQ_ASSERT_IN_RUNQ(pthread, "_pq_remove: Not in priority queue");
148
149	/*
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.
156	 */
157	TAILQ_REMOVE(&pq->pq_lists[prio].pl_head, pthread, pqe);
158	pq->pq_threads--;
159	/* This thread is now longer in the priority queue. */
160	pthread->flags &= ~THR_FLAGS_IN_RUNQ;
161
162	PQ_CLEAR_ACTIVE(pq);
163}
164
165
166void
167_pq_insert_head(pq_queue_t *pq, pthread_t pthread)
168{
169	int prio;
170
171	/*
172	 * Make some assertions when debugging is enabled:
173	 */
174	PQ_ASSERT_INACTIVE(pq, "_pq_insert_head: pq_active");
175	PQ_SET_ACTIVE(pq);
176	PQ_ASSERT_NOT_QUEUED(pthread,
177	    "_pq_insert_head: Already in priority queue");
178
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);
184	pq->pq_threads++;
185	/* Mark this thread as being in the priority queue. */
186	pthread->flags |= THR_FLAGS_IN_RUNQ;
187
188	PQ_CLEAR_ACTIVE(pq);
189}
190
191
192void
193_pq_insert_tail(pq_queue_t *pq, pthread_t pthread)
194{
195	int prio;
196
197	/*
198	 * Make some assertions when debugging is enabled:
199	 */
200	PQ_ASSERT_INACTIVE(pq, "_pq_insert_tail: pq_active");
201	PQ_SET_ACTIVE(pq);
202	PQ_ASSERT_NOT_QUEUED(pthread,
203	    "_pq_insert_tail: Already in priority queue");
204
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);
210	pq->pq_threads++;
211	/* Mark this thread as being in the priority queue. */
212	pthread->flags |= THR_FLAGS_IN_RUNQ;
213
214	PQ_CLEAR_ACTIVE(pq);
215}
216
217
218pthread_t
219_pq_first(pq_queue_t *pq)
220{
221	pq_list_t *pql;
222	pthread_t pthread = NULL;
223
224	/*
225	 * Make some assertions when debugging is enabled:
226	 */
227	PQ_ASSERT_INACTIVE(pq, "_pq_first: pq_active");
228	PQ_SET_ACTIVE(pq);
229
230	while (((pql = TAILQ_FIRST(&pq->pq_queue)) != NULL) &&
231	    (pthread == NULL)) {
232		if ((pthread = TAILQ_FIRST(&pql->pl_head)) == NULL) {
233			/*
234			 * The priority list is empty; remove the list
235			 * from the queue.
236			 */
237			TAILQ_REMOVE(&pq->pq_queue, pql, pl_link);
238
239			/* Mark the list as not being in the queue: */
240			pql->pl_queued = 0;
241		}
242	}
243
244	PQ_CLEAR_ACTIVE(pq);
245	return (pthread);
246}
247
248/*
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.
252 */
253pthread_t
254_pq_first_debug(pq_queue_t *pq)
255{
256	pq_list_t *pql, *pqlnext = NULL;
257	pthread_t pthread = NULL;
258
259	/*
260	 * Make some assertions when debugging is enabled:
261	 */
262	PQ_ASSERT_INACTIVE(pq, "_pq_first: pq_active");
263	PQ_SET_ACTIVE(pq);
264
265	for (pql = TAILQ_FIRST(&pq->pq_queue);
266	     pql != NULL && pthread == NULL; pql = pqlnext) {
267		if ((pthread = TAILQ_FIRST(&pql->pl_head)) == NULL) {
268			/*
269			 * The priority list is empty; remove the list
270			 * from the queue.
271			 */
272			pqlnext = TAILQ_NEXT(pql, pl_link);
273			TAILQ_REMOVE(&pq->pq_queue, pql, pl_link);
274
275			/* Mark the list as not being in the queue: */
276			pql->pl_queued = 0;
277		} else {
278			/*
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.
287			 */
288			while (pthread != NULL && !DBG_CAN_RUN(pthread)) {
289				pthread = TAILQ_NEXT(pthread, pqe);
290			}
291			if (pthread == NULL)
292				pqlnext = TAILQ_NEXT(pql, pl_link);
293		}
294	}
295
296	PQ_CLEAR_ACTIVE(pq);
297	return (pthread);
298}
299
300static void
301pq_insert_prio_list(pq_queue_t *pq, int prio)
302{
303	pq_list_t *pql;
304
305	/*
306	 * Make some assertions when debugging is enabled:
307	 */
308	PQ_ASSERT_ACTIVE(pq, "pq_insert_prio_list: pq_active");
309
310	/*
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.
314	 */
315	pql = TAILQ_FIRST(&pq->pq_queue);
316	while ((pql != NULL) && (pql->pl_prio > prio))
317		pql = TAILQ_NEXT(pql, pl_link);
318
319	/* Insert the list: */
320	if (pql == NULL)
321		TAILQ_INSERT_TAIL(&pq->pq_queue, &pq->pq_lists[prio], pl_link);
322	else
323		TAILQ_INSERT_BEFORE(pql, &pq->pq_lists[prio], pl_link);
324
325	/* Mark this list as being in the queue: */
326	pq->pq_lists[prio].pl_queued = 1;
327}
328