144963Sjb/*
244963Sjb * Copyright (c) 1998 Daniel Eischen <eischen@vigrid.com>.
344963Sjb * All rights reserved.
444963Sjb *
544963Sjb * Redistribution and use in source and binary forms, with or without
644963Sjb * modification, are permitted provided that the following conditions
744963Sjb * are met:
844963Sjb * 1. Redistributions of source code must retain the above copyright
944963Sjb *    notice, this list of conditions and the following disclaimer.
1044963Sjb * 2. Redistributions in binary form must reproduce the above copyright
1144963Sjb *    notice, this list of conditions and the following disclaimer in the
1244963Sjb *    documentation and/or other materials provided with the distribution.
1344963Sjb * 3. All advertising materials mentioning features or use of this software
1444963Sjb *    must display the following acknowledgement:
1544963Sjb *	This product includes software developed by Daniel Eischen.
1644963Sjb * 4. Neither the name of the author nor the names of any co-contributors
1744963Sjb *    may be used to endorse or promote products derived from this software
1844963Sjb *    without specific prior written permission.
1944963Sjb *
2044963Sjb * THIS SOFTWARE IS PROVIDED BY DANIEL EISCHEN AND CONTRIBUTORS ``AS IS'' AND
2144963Sjb * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
2244963Sjb * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
2344963Sjb * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
2444963Sjb * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
2544963Sjb * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
2644963Sjb * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
2744963Sjb * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
2844963Sjb * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
2944963Sjb * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
3044963Sjb * SUCH DAMAGE.
3144963Sjb *
3250476Speter * $FreeBSD$
3344963Sjb */
34174112Sdeischen
35174112Sdeischen#include "namespace.h"
3644963Sjb#include <stdlib.h>
3744963Sjb#include <sys/queue.h>
3844963Sjb#include <string.h>
3944963Sjb#include <pthread.h>
40174112Sdeischen#include "un-namespace.h"
41103388Smini#include "thr_private.h"
4244963Sjb
4344963Sjb/* Prototypes: */
4444963Sjbstatic void pq_insert_prio_list(pq_queue_t *pq, int prio);
4544963Sjb
4648046Sjb#if defined(_PTHREADS_INVARIANTS)
4744963Sjb
48113658Sdeischen#define PQ_IN_SCHEDQ	(THR_FLAGS_IN_RUNQ | THR_FLAGS_IN_WAITQ)
4948046Sjb
50113658Sdeischen#define PQ_SET_ACTIVE(pq)		(pq)->pq_flags |= PQF_ACTIVE
51113658Sdeischen#define PQ_CLEAR_ACTIVE(pq)		(pq)->pq_flags &= ~PQF_ACTIVE
52113658Sdeischen#define PQ_ASSERT_ACTIVE(pq, msg)	do {		\
53113658Sdeischen	if (((pq)->pq_flags & PQF_ACTIVE) == 0)		\
5448046Sjb		PANIC(msg);				\
5548046Sjb} while (0)
56113658Sdeischen#define PQ_ASSERT_INACTIVE(pq, msg)	do {		\
57113658Sdeischen	if (((pq)->pq_flags & PQF_ACTIVE) != 0)		\
5848046Sjb		PANIC(msg);				\
5948046Sjb} while (0)
60113658Sdeischen#define PQ_ASSERT_IN_WAITQ(thrd, msg)	do {		\
61113658Sdeischen	if (((thrd)->flags & THR_FLAGS_IN_WAITQ) == 0) \
6248046Sjb		PANIC(msg);				\
6348046Sjb} while (0)
64113658Sdeischen#define PQ_ASSERT_IN_RUNQ(thrd, msg)	do {		\
65113658Sdeischen	if (((thrd)->flags & THR_FLAGS_IN_RUNQ) == 0) \
6648046Sjb		PANIC(msg);				\
6748046Sjb} while (0)
68113658Sdeischen#define PQ_ASSERT_NOT_QUEUED(thrd, msg) do {		\
69113658Sdeischen	if (((thrd)->flags & PQ_IN_SCHEDQ) != 0)	\
7048046Sjb		PANIC(msg);				\
7148046Sjb} while (0)
7248046Sjb
7348046Sjb#else
7448046Sjb
75113658Sdeischen#define PQ_SET_ACTIVE(pq)
76113658Sdeischen#define PQ_CLEAR_ACTIVE(pq)
77113658Sdeischen#define PQ_ASSERT_ACTIVE(pq, msg)
78113658Sdeischen#define PQ_ASSERT_INACTIVE(pq, msg)
79113658Sdeischen#define PQ_ASSERT_IN_WAITQ(thrd, msg)
80113658Sdeischen#define PQ_ASSERT_IN_RUNQ(thrd, msg)
81113658Sdeischen#define PQ_ASSERT_NOT_QUEUED(thrd, msg)
8248046Sjb
8348046Sjb#endif
8448046Sjb
8544963Sjbint
8648046Sjb_pq_alloc(pq_queue_t *pq, int minprio, int maxprio)
8744963Sjb{
8855194Sdeischen	int ret = 0;
8944963Sjb	int prioslots = maxprio - minprio + 1;
9044963Sjb
9144963Sjb	if (pq == NULL)
9244963Sjb		ret = -1;
9344963Sjb
9444963Sjb	/* Create the priority queue with (maxprio - minprio + 1) slots: */
9544963Sjb	else if	((pq->pq_lists =
9644963Sjb	    (pq_list_t *) malloc(sizeof(pq_list_t) * prioslots)) == NULL)
9744963Sjb		ret = -1;
9844963Sjb
9944963Sjb	else {
10048046Sjb		/* Remember the queue size: */
10148046Sjb		pq->pq_size = prioslots;
10248046Sjb		ret = _pq_init(pq);
10348046Sjb	}
10448046Sjb	return (ret);
10548046Sjb}
10648046Sjb
107113661Sdeischenvoid
108113661Sdeischen_pq_free(pq_queue_t *pq)
109113661Sdeischen{
110113661Sdeischen	if ((pq != NULL) && (pq->pq_lists != NULL))
111113661Sdeischen		free(pq->pq_lists);
112113661Sdeischen}
113113661Sdeischen
11448046Sjbint
11548046Sjb_pq_init(pq_queue_t *pq)
11648046Sjb{
11748046Sjb	int i, ret = 0;
11848046Sjb
11948046Sjb	if ((pq == NULL) || (pq->pq_lists == NULL))
12048046Sjb		ret = -1;
12148046Sjb
12248046Sjb	else {
12344963Sjb		/* Initialize the queue for each priority slot: */
12448046Sjb		for (i = 0; i < pq->pq_size; i++) {
12544963Sjb			TAILQ_INIT(&pq->pq_lists[i].pl_head);
12644963Sjb			pq->pq_lists[i].pl_prio = i;
12744963Sjb			pq->pq_lists[i].pl_queued = 0;
12844963Sjb		}
12944963Sjb		/* Initialize the priority queue: */
13044963Sjb		TAILQ_INIT(&pq->pq_queue);
131113658Sdeischen		pq->pq_flags = 0;
132114187Sdeischen		pq->pq_threads = 0;
13344963Sjb	}
13444963Sjb	return (ret);
13544963Sjb}
13644963Sjb
13744963Sjbvoid
13844963Sjb_pq_remove(pq_queue_t *pq, pthread_t pthread)
13944963Sjb{
14044963Sjb	int prio = pthread->active_priority;
14144963Sjb
14248046Sjb	/*
14348046Sjb	 * Make some assertions when debugging is enabled:
14448046Sjb	 */
145113658Sdeischen	PQ_ASSERT_INACTIVE(pq, "_pq_remove: pq_active");
146113658Sdeischen	PQ_SET_ACTIVE(pq);
147113658Sdeischen	PQ_ASSERT_IN_RUNQ(pthread, "_pq_remove: Not in priority queue");
14848046Sjb
14948046Sjb	/*
15048046Sjb	 * Remove this thread from priority list.  Note that if
15148046Sjb	 * the priority list becomes empty, it is not removed
15248046Sjb	 * from the priority queue because another thread may be
15348046Sjb	 * added to the priority list (resulting in a needless
15448046Sjb	 * removal/insertion).  Priority lists are only removed
15548046Sjb	 * from the priority queue when _pq_first is called.
15648046Sjb	 */
15744963Sjb	TAILQ_REMOVE(&pq->pq_lists[prio].pl_head, pthread, pqe);
158114187Sdeischen	pq->pq_threads--;
15948046Sjb	/* This thread is now longer in the priority queue. */
160113658Sdeischen	pthread->flags &= ~THR_FLAGS_IN_RUNQ;
161114187Sdeischen
162113658Sdeischen	PQ_CLEAR_ACTIVE(pq);
16344963Sjb}
16444963Sjb
16544963Sjb
16644963Sjbvoid
16744963Sjb_pq_insert_head(pq_queue_t *pq, pthread_t pthread)
16844963Sjb{
16997204Sdeischen	int prio;
17044963Sjb
17148046Sjb	/*
172113658Sdeischen	 * Make some assertions when debugging is enabled:
17348046Sjb	 */
174113658Sdeischen	PQ_ASSERT_INACTIVE(pq, "_pq_insert_head: pq_active");
175113658Sdeischen	PQ_SET_ACTIVE(pq);
176113658Sdeischen	PQ_ASSERT_NOT_QUEUED(pthread,
177113658Sdeischen	    "_pq_insert_head: Already in priority queue");
17848046Sjb
179113658Sdeischen	prio = pthread->active_priority;
180113658Sdeischen	TAILQ_INSERT_HEAD(&pq->pq_lists[prio].pl_head, pthread, pqe);
181113658Sdeischen	if (pq->pq_lists[prio].pl_queued == 0)
182113658Sdeischen		/* Insert the list into the priority queue: */
183113658Sdeischen		pq_insert_prio_list(pq, prio);
184114187Sdeischen	pq->pq_threads++;
185113658Sdeischen	/* Mark this thread as being in the priority queue. */
186113658Sdeischen	pthread->flags |= THR_FLAGS_IN_RUNQ;
18748046Sjb
188113658Sdeischen	PQ_CLEAR_ACTIVE(pq);
18944963Sjb}
19044963Sjb
19144963Sjb
19244963Sjbvoid
19344963Sjb_pq_insert_tail(pq_queue_t *pq, pthread_t pthread)
19444963Sjb{
19597204Sdeischen	int prio;
19644963Sjb
19748046Sjb	/*
198113658Sdeischen	 * Make some assertions when debugging is enabled:
19948046Sjb	 */
200113658Sdeischen	PQ_ASSERT_INACTIVE(pq, "_pq_insert_tail: pq_active");
201113658Sdeischen	PQ_SET_ACTIVE(pq);
202113658Sdeischen	PQ_ASSERT_NOT_QUEUED(pthread,
203113658Sdeischen	    "_pq_insert_tail: Already in priority queue");
20448046Sjb
205113658Sdeischen	prio = pthread->active_priority;
206113658Sdeischen	TAILQ_INSERT_TAIL(&pq->pq_lists[prio].pl_head, pthread, pqe);
207113658Sdeischen	if (pq->pq_lists[prio].pl_queued == 0)
208113658Sdeischen		/* Insert the list into the priority queue: */
209113658Sdeischen		pq_insert_prio_list(pq, prio);
210114187Sdeischen	pq->pq_threads++;
211113658Sdeischen	/* Mark this thread as being in the priority queue. */
212113658Sdeischen	pthread->flags |= THR_FLAGS_IN_RUNQ;
21348046Sjb
214113658Sdeischen	PQ_CLEAR_ACTIVE(pq);
21544963Sjb}
21644963Sjb
21744963Sjb
21844963Sjbpthread_t
21944963Sjb_pq_first(pq_queue_t *pq)
22044963Sjb{
22144963Sjb	pq_list_t *pql;
22244963Sjb	pthread_t pthread = NULL;
22344963Sjb
22448046Sjb	/*
22548046Sjb	 * Make some assertions when debugging is enabled:
22648046Sjb	 */
227113658Sdeischen	PQ_ASSERT_INACTIVE(pq, "_pq_first: pq_active");
228113658Sdeischen	PQ_SET_ACTIVE(pq);
22948046Sjb
23044963Sjb	while (((pql = TAILQ_FIRST(&pq->pq_queue)) != NULL) &&
23144963Sjb	    (pthread == NULL)) {
23244963Sjb		if ((pthread = TAILQ_FIRST(&pql->pl_head)) == NULL) {
23344963Sjb			/*
23444963Sjb			 * The priority list is empty; remove the list
23544963Sjb			 * from the queue.
23644963Sjb			 */
23744963Sjb			TAILQ_REMOVE(&pq->pq_queue, pql, pl_link);
23844963Sjb
23944963Sjb			/* Mark the list as not being in the queue: */
24044963Sjb			pql->pl_queued = 0;
24144963Sjb		}
24244963Sjb	}
24348046Sjb
244113658Sdeischen	PQ_CLEAR_ACTIVE(pq);
24544963Sjb	return (pthread);
24644963Sjb}
24744963Sjb
248132120Sdavidxu/*
249132120Sdavidxu * Select a thread which is allowed to run by debugger, we probably
250132120Sdavidxu * should merge the function into _pq_first if that function is only
251132120Sdavidxu * used by scheduler to select a thread.
252132120Sdavidxu */
253132120Sdavidxupthread_t
254132120Sdavidxu_pq_first_debug(pq_queue_t *pq)
255132120Sdavidxu{
256132120Sdavidxu	pq_list_t *pql, *pqlnext = NULL;
257132120Sdavidxu	pthread_t pthread = NULL;
25844963Sjb
259132120Sdavidxu	/*
260132120Sdavidxu	 * Make some assertions when debugging is enabled:
261132120Sdavidxu	 */
262132120Sdavidxu	PQ_ASSERT_INACTIVE(pq, "_pq_first: pq_active");
263132120Sdavidxu	PQ_SET_ACTIVE(pq);
264132120Sdavidxu
265132120Sdavidxu	for (pql = TAILQ_FIRST(&pq->pq_queue);
266132120Sdavidxu	     pql != NULL && pthread == NULL; pql = pqlnext) {
267132120Sdavidxu		if ((pthread = TAILQ_FIRST(&pql->pl_head)) == NULL) {
268132120Sdavidxu			/*
269132120Sdavidxu			 * The priority list is empty; remove the list
270132120Sdavidxu			 * from the queue.
271132120Sdavidxu			 */
272132120Sdavidxu			pqlnext = TAILQ_NEXT(pql, pl_link);
273132120Sdavidxu			TAILQ_REMOVE(&pq->pq_queue, pql, pl_link);
274132120Sdavidxu
275132120Sdavidxu			/* Mark the list as not being in the queue: */
276132120Sdavidxu			pql->pl_queued = 0;
277132120Sdavidxu		} else {
278132120Sdavidxu			/*
279132120Sdavidxu			 * note there may be a suspension event during this
280133047Sdavidxu			 * test, If TMDF_SUSPEND is set after we tested it,
281132120Sdavidxu			 * we will run the thread, this seems be a problem,
282132120Sdavidxu			 * fortunatly, when we are being debugged, all context
283132120Sdavidxu			 * switch will be done by kse_switchin, that is a
284132120Sdavidxu			 * syscall, kse_switchin will check the flag again,
285132120Sdavidxu			 * the thread will be returned via upcall, so next
286132120Sdavidxu			 * time, UTS won't run the thread.
287132120Sdavidxu			 */
288132120Sdavidxu			while (pthread != NULL && !DBG_CAN_RUN(pthread)) {
289132120Sdavidxu				pthread = TAILQ_NEXT(pthread, pqe);
290132120Sdavidxu			}
291132120Sdavidxu			if (pthread == NULL)
292132120Sdavidxu				pqlnext = TAILQ_NEXT(pql, pl_link);
293132120Sdavidxu		}
294132120Sdavidxu	}
295132120Sdavidxu
296132120Sdavidxu	PQ_CLEAR_ACTIVE(pq);
297132120Sdavidxu	return (pthread);
298132120Sdavidxu}
299132120Sdavidxu
30044963Sjbstatic void
30144963Sjbpq_insert_prio_list(pq_queue_t *pq, int prio)
30244963Sjb{
30344963Sjb	pq_list_t *pql;
30444963Sjb
30544963Sjb	/*
30648046Sjb	 * Make some assertions when debugging is enabled:
30748046Sjb	 */
308113658Sdeischen	PQ_ASSERT_ACTIVE(pq, "pq_insert_prio_list: pq_active");
30948046Sjb
31048046Sjb	/*
31144963Sjb	 * The priority queue is in descending priority order.  Start at
31244963Sjb	 * the beginning of the queue and find the list before which the
31348046Sjb	 * new list should be inserted.
31444963Sjb	 */
31544963Sjb	pql = TAILQ_FIRST(&pq->pq_queue);
31644963Sjb	while ((pql != NULL) && (pql->pl_prio > prio))
31744963Sjb		pql = TAILQ_NEXT(pql, pl_link);
31844963Sjb
31944963Sjb	/* Insert the list: */
32044963Sjb	if (pql == NULL)
32144963Sjb		TAILQ_INSERT_TAIL(&pq->pq_queue, &pq->pq_lists[prio], pl_link);
32244963Sjb	else
32344963Sjb		TAILQ_INSERT_BEFORE(pql, &pq->pq_lists[prio], pl_link);
32444963Sjb
32544963Sjb	/* Mark this list as being in the queue: */
32644963Sjb	pq->pq_lists[prio].pl_queued = 1;
32744963Sjb}
328