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