lib/libkse/thread/thr_priority_queue.c

   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 #include <stdlib.h>
  35 #include <sys/queue.h>
  36 #include <string.h>
  37 #include <pthread.h>
  38 #include "thr_private.h"
  39
  40 /* Prototypes: */
  41 static void pq_insert_prio_list(pq_queue_t *pq, int prio);
  42
  43 #if defined(_PTHREADS_INVARIANTS)
  44
  45 #define PQ_IN_SCHEDQ    (THR_FLAGS_IN_RUNQ | THR_FLAGS_IN_WAITQ)
  46
  47 #define PQ_SET_ACTIVE(pq)               (pq)->pq_flags |= PQF_ACTIVE
  48 #define PQ_CLEAR_ACTIVE(pq)             (pq)->pq_flags &= ~PQF_ACTIVE
  49 #define PQ_ASSERT_ACTIVE(pq, msg)       do {            \
  50         if (((pq)->pq_flags & PQF_ACTIVE) == 0)         \
  51                 PANIC(msg);                             \
  52 } while (0)
  53 #define PQ_ASSERT_INACTIVE(pq, msg)     do {            \
  54         if (((pq)->pq_flags & PQF_ACTIVE) != 0)         \
  55                 PANIC(msg);                             \
  56 } while (0)
  57 #define PQ_ASSERT_IN_WAITQ(thrd, msg)   do {            \
  58         if (((thrd)->flags & THR_FLAGS_IN_WAITQ) == 0) \
  59                 PANIC(msg);                             \
  60 } while (0)
  61 #define PQ_ASSERT_IN_RUNQ(thrd, msg)    do {            \
  62         if (((thrd)->flags & THR_FLAGS_IN_RUNQ) == 0) \
  63                 PANIC(msg);                             \
  64 } while (0)
  65 #define PQ_ASSERT_NOT_QUEUED(thrd, msg) do {            \
  66         if (((thrd)->flags & PQ_IN_SCHEDQ) != 0)        \
  67                 PANIC(msg);                             \
  68 } while (0)
  69
  70 #else
  71
  72 #define PQ_SET_ACTIVE(pq)
  73 #define PQ_CLEAR_ACTIVE(pq)
  74 #define PQ_ASSERT_ACTIVE(pq, msg)
  75 #define PQ_ASSERT_INACTIVE(pq, msg)
  76 #define PQ_ASSERT_IN_WAITQ(thrd, msg)
  77 #define PQ_ASSERT_IN_RUNQ(thrd, msg)
  78 #define PQ_ASSERT_NOT_QUEUED(thrd, msg)
  79
  80 #endif
  81
  82 int
  83 _pq_alloc(pq_queue_t *pq, int minprio, int maxprio)
  84 {
  85         int ret = 0;
  86         int prioslots = maxprio - minprio + 1;
  87
  88         if (pq == NULL)
  89                 ret = -1;
  90
  91         /* Create the priority queue with (maxprio - minprio + 1) slots: */
  92         else if ((pq->pq_lists =
  93             (pq_list_t *) malloc(sizeof(pq_list_t) * prioslots)) == NULL)
  94                 ret = -1;
  95
  96         else {
  97                 /* Remember the queue size: */
  98                 pq->pq_size = prioslots;
  99                 ret = _pq_init(pq);
 100         }
 101         return (ret);
 102 }
 103
 104 void
 105 _pq_free(pq_queue_t *pq)
 106 {
 107         if ((pq != NULL) && (pq->pq_lists != NULL))
 108                 free(pq->pq_lists);
 109 }
 110
 111 int
 112 _pq_init(pq_queue_t *pq)
 113 {
 114         int i, ret = 0;
 115
 116         if ((pq == NULL) || (pq->pq_lists == NULL))
 117                 ret = -1;
 118
 119         else {
 120                 /* Initialize the queue for each priority slot: */
 121                 for (i = 0; i < pq->pq_size; i++) {
 122                         TAILQ_INIT(&pq->pq_lists[i].pl_head);
 123                         pq->pq_lists[i].pl_prio = i;
 124                         pq->pq_lists[i].pl_queued = 0;
 125                 }
 126                 /* Initialize the priority queue: */
 127                 TAILQ_INIT(&pq->pq_queue);
 128                 pq->pq_flags = 0;
 129                 pq->pq_threads = 0;
 130         }
 131         return (ret);
 132 }
 133
 134 void
 135 _pq_remove(pq_queue_t *pq, pthread_t pthread)
 136 {
 137         int prio = pthread->active_priority;
 138
 139         /*
 140          * Make some assertions when debugging is enabled:
 141          */
 142         PQ_ASSERT_INACTIVE(pq, "_pq_remove: pq_active");
 143         PQ_SET_ACTIVE(pq);
 144         PQ_ASSERT_IN_RUNQ(pthread, "_pq_remove: Not in priority queue");
 145
 146         /*
 147          * Remove this thread from priority list.  Note that if
 148          * the priority list becomes empty, it is not removed
 149          * from the priority queue because another thread may be
 150          * added to the priority list (resulting in a needless
 151          * removal/insertion).  Priority lists are only removed
 152          * from the priority queue when _pq_first is called.
 153          */
 154         TAILQ_REMOVE(&pq->pq_lists[prio].pl_head, pthread, pqe);
 155         pq->pq_threads--;
 156         /* This thread is now longer in the priority queue. */
 157         pthread->flags &= ~THR_FLAGS_IN_RUNQ;
 158
 159         PQ_CLEAR_ACTIVE(pq);
 160 }
 161
 162
 163 void
 164 _pq_insert_head(pq_queue_t *pq, pthread_t pthread)
 165 {
 166         int prio;
 167
 168         /*
 169          * Make some assertions when debugging is enabled:
 170          */
 171         PQ_ASSERT_INACTIVE(pq, "_pq_insert_head: pq_active");
 172         PQ_SET_ACTIVE(pq);
 173         PQ_ASSERT_NOT_QUEUED(pthread,
 174             "_pq_insert_head: Already in priority queue");
 175
 176         prio = pthread->active_priority;
 177         TAILQ_INSERT_HEAD(&pq->pq_lists[prio].pl_head, pthread, pqe);
 178         if (pq->pq_lists[prio].pl_queued == 0)
 179                 /* Insert the list into the priority queue: */
 180                 pq_insert_prio_list(pq, prio);
 181         pq->pq_threads++;
 182         /* Mark this thread as being in the priority queue. */
 183         pthread->flags |= THR_FLAGS_IN_RUNQ;
 184
 185         PQ_CLEAR_ACTIVE(pq);
 186 }
 187
 188
 189 void
 190 _pq_insert_tail(pq_queue_t *pq, pthread_t pthread)
 191 {
 192         int prio;
 193
 194         /*
 195          * Make some assertions when debugging is enabled:
 196          */
 197         PQ_ASSERT_INACTIVE(pq, "_pq_insert_tail: pq_active");
 198         PQ_SET_ACTIVE(pq);
 199         PQ_ASSERT_NOT_QUEUED(pthread,
 200             "_pq_insert_tail: Already in priority queue");
 201
 202         prio = pthread->active_priority;
 203         TAILQ_INSERT_TAIL(&pq->pq_lists[prio].pl_head, pthread, pqe);
 204         if (pq->pq_lists[prio].pl_queued == 0)
 205                 /* Insert the list into the priority queue: */
 206                 pq_insert_prio_list(pq, prio);
 207         pq->pq_threads++;
 208         /* Mark this thread as being in the priority queue. */
 209         pthread->flags |= THR_FLAGS_IN_RUNQ;
 210
 211         PQ_CLEAR_ACTIVE(pq);
 212 }
 213
 214
 215 pthread_t
 216 _pq_first(pq_queue_t *pq)
 217 {
 218         pq_list_t *pql;
 219         pthread_t pthread = NULL;
 220
 221         /*
 222          * Make some assertions when debugging is enabled:
 223          */
 224         PQ_ASSERT_INACTIVE(pq, "_pq_first: pq_active");
 225         PQ_SET_ACTIVE(pq);
 226
 227         while (((pql = TAILQ_FIRST(&pq->pq_queue)) != NULL) &&
 228             (pthread == NULL)) {
 229                 if ((pthread = TAILQ_FIRST(&pql->pl_head)) == NULL) {
 230                         /*
 231                          * The priority list is empty; remove the list
 232                          * from the queue.
 233                          */
 234                         TAILQ_REMOVE(&pq->pq_queue, pql, pl_link);
 235
 236                         /* Mark the list as not being in the queue: */
 237                         pql->pl_queued = 0;
 238                 }
 239         }
 240
 241         PQ_CLEAR_ACTIVE(pq);
 242         return (pthread);
 243 }
 244
 245 /*
 246  * Select a thread which is allowed to run by debugger, we probably
 247  * should merge the function into _pq_first if that function is only
 248  * used by scheduler to select a thread.
 249  */
 250 pthread_t
 251 _pq_first_debug(pq_queue_t *pq)
 252 {
 253         pq_list_t *pql, *pqlnext = NULL;
 254         pthread_t pthread = NULL;
 255
 256         /*
 257          * Make some assertions when debugging is enabled:
 258          */
 259         PQ_ASSERT_INACTIVE(pq, "_pq_first: pq_active");
 260         PQ_SET_ACTIVE(pq);
 261
 262         for (pql = TAILQ_FIRST(&pq->pq_queue);
 263              pql != NULL && pthread == NULL; pql = pqlnext) {
 264                 if ((pthread = TAILQ_FIRST(&pql->pl_head)) == NULL) {
 265                         /*
 266                          * The priority list is empty; remove the list
 267                          * from the queue.
 268                          */
 269                         pqlnext = TAILQ_NEXT(pql, pl_link);
 270                         TAILQ_REMOVE(&pq->pq_queue, pql, pl_link);
 271
 272                         /* Mark the list as not being in the queue: */
 273                         pql->pl_queued = 0;
 274                 } else {
 275                         /*
 276                          * note there may be a suspension event during this
 277                          * test, If TMDF_SUSPEND is set after we tested it,
 278                          * we will run the thread, this seems be a problem,
 279                          * fortunatly, when we are being debugged, all context
 280                          * switch will be done by kse_switchin, that is a
 281                          * syscall, kse_switchin will check the flag again,
 282                          * the thread will be returned via upcall, so next
 283                          * time, UTS won't run the thread.
 284                          */
 285                         while (pthread != NULL && !DBG_CAN_RUN(pthread)) {
 286                                 pthread = TAILQ_NEXT(pthread, pqe);
 287                         }
 288                         if (pthread == NULL)
 289                                 pqlnext = TAILQ_NEXT(pql, pl_link);
 290                 }
 291         }
 292
 293         PQ_CLEAR_ACTIVE(pq);
 294         return (pthread);
 295 }
 296
 297 static void
 298 pq_insert_prio_list(pq_queue_t *pq, int prio)
 299 {
 300         pq_list_t *pql;
 301
 302         /*
 303          * Make some assertions when debugging is enabled:
 304          */
 305         PQ_ASSERT_ACTIVE(pq, "pq_insert_prio_list: pq_active");
 306
 307         /*
 308          * The priority queue is in descending priority order.  Start at
 309          * the beginning of the queue and find the list before which the
 310          * new list should be inserted.
 311          */
 312         pql = TAILQ_FIRST(&pq->pq_queue);
 313         while ((pql != NULL) && (pql->pl_prio > prio))
 314                 pql = TAILQ_NEXT(pql, pl_link);
 315
 316         /* Insert the list: */
 317         if (pql == NULL)
 318                 TAILQ_INSERT_TAIL(&pq->pq_queue, &pq->pq_lists[prio], pl_link);
 319         else
 320                 TAILQ_INSERT_BEFORE(pql, &pq->pq_lists[prio], pl_link);
 321
 322         /* Mark this list as being in the queue: */
 323         pq->pq_lists[prio].pl_queued = 1;
 324 }