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