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
  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: */
  44 static 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
  85 int
  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
 107 void
 108 _pq_free(pq_queue_t *pq)
 109 {
 110         if ((pq != NULL) && (pq->pq_lists != NULL))
 111                 free(pq->pq_lists);
 112 }
 113
 114 int
 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
 137 void
 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
 166 void
 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
 192 void
 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
 218 pthread_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  */
 253 pthread_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
 300 static void
 301 pq_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 }