lib/libc_r/uthread/uthread_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 #ifdef _THREAD_SAFE
  38 #include <pthread.h>
  39 #include "pthread_private.h"
  40
  41 /* Prototypes: */
  42 static void pq_insert_prio_list(pq_queue_t *pq, int prio);
  43
  44 #if defined(_PTHREADS_INVARIANTS)
  45
  46 static int _pq_active = 0;
  47
  48 #define _PQ_IN_SCHEDQ   (PTHREAD_FLAGS_IN_PRIOQ | PTHREAD_FLAGS_IN_WAITQ | PTHREAD_FLAGS_IN_WORKQ)
  49
  50 #define _PQ_SET_ACTIVE()                _pq_active = 1
  51 #define _PQ_CLEAR_ACTIVE()              _pq_active = 0
  52 #define _PQ_ASSERT_ACTIVE(msg)          do {            \
  53         if (_pq_active == 0)                            \
  54                 PANIC(msg);                             \
  55 } while (0)
  56 #define _PQ_ASSERT_INACTIVE(msg)        do {            \
  57         if (_pq_active != 0)                            \
  58                 PANIC(msg);                             \
  59 } while (0)
  60 #define _PQ_ASSERT_IN_WAITQ(thrd, msg)  do {            \
  61         if (((thrd)->flags & PTHREAD_FLAGS_IN_WAITQ) == 0) \
  62                 PANIC(msg);                             \
  63 } while (0)
  64 #define _PQ_ASSERT_IN_PRIOQ(thrd, msg)  do {            \
  65         if (((thrd)->flags & PTHREAD_FLAGS_IN_PRIOQ) == 0) \
  66                 PANIC(msg);                             \
  67 } while (0)
  68 #define _PQ_ASSERT_NOT_QUEUED(thrd, msg) do {           \
  69         if ((thrd)->flags & _PQ_IN_SCHEDQ)              \
  70                 PANIC(msg);                             \
  71 } while (0)
  72
  73 #else
  74
  75 #define _PQ_SET_ACTIVE()
  76 #define _PQ_CLEAR_ACTIVE()
  77 #define _PQ_ASSERT_ACTIVE(msg)
  78 #define _PQ_ASSERT_INACTIVE(msg)
  79 #define _PQ_ASSERT_IN_WAITQ(thrd, msg)
  80 #define _PQ_ASSERT_IN_PRIOQ(thrd, msg)
  81 #define _PQ_ASSERT_NOT_QUEUED(thrd, msg)
  82 #define _PQ_CHECK_PRIO()
  83
  84 #endif
  85
  86
  87 int
  88 _pq_alloc(pq_queue_t *pq, int minprio, int maxprio)
  89 {
  90         int i, ret = 0;
  91         int prioslots = maxprio - minprio + 1;
  92
  93         if (pq == NULL)
  94                 ret = -1;
  95
  96         /* Create the priority queue with (maxprio - minprio + 1) slots: */
  97         else if ((pq->pq_lists =
  98             (pq_list_t *) malloc(sizeof(pq_list_t) * prioslots)) == NULL)
  99                 ret = -1;
 100
 101         else {
 102                 /* Remember the queue size: */
 103                 pq->pq_size = prioslots;
 104
 105                 ret = _pq_init(pq);
 106
 107         }
 108         return (ret);
 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
 127                 /* Initialize the priority queue: */
 128                 TAILQ_INIT(&pq->pq_queue);
 129                 _PQ_CLEAR_ACTIVE();
 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_remove: pq_active");
 143         _PQ_SET_ACTIVE();
 144         _PQ_ASSERT_IN_PRIOQ(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
 156         /* This thread is now longer in the priority queue. */
 157         pthread->flags &= ~PTHREAD_FLAGS_IN_PRIOQ;
 158
 159         _PQ_CLEAR_ACTIVE();
 160 }
 161
 162
 163 void
 164 _pq_insert_head(pq_queue_t *pq, pthread_t pthread)
 165 {
 166         int prio = pthread->active_priority;
 167
 168         /*
 169          * Make some assertions when debugging is enabled:
 170          */
 171         _PQ_ASSERT_INACTIVE("_pq_insert_head: pq_active");
 172         _PQ_SET_ACTIVE();
 173         _PQ_ASSERT_NOT_QUEUED(pthread,
 174             "_pq_insert_head: Already in priority queue");
 175
 176         TAILQ_INSERT_HEAD(&pq->pq_lists[prio].pl_head, pthread, pqe);
 177         if (pq->pq_lists[prio].pl_queued == 0)
 178                 /* Insert the list into the priority queue: */
 179                 pq_insert_prio_list(pq, prio);
 180
 181         /* Mark this thread as being in the priority queue. */
 182         pthread->flags |= PTHREAD_FLAGS_IN_PRIOQ;
 183
 184         _PQ_CLEAR_ACTIVE();
 185 }
 186
 187
 188 void
 189 _pq_insert_tail(pq_queue_t *pq, pthread_t pthread)
 190 {
 191         int prio = pthread->active_priority;
 192
 193         /*
 194          * Make some assertions when debugging is enabled:
 195          */
 196         _PQ_ASSERT_INACTIVE("_pq_insert_tail: pq_active");
 197         _PQ_SET_ACTIVE();
 198         _PQ_ASSERT_NOT_QUEUED(pthread,
 199             "_pq_insert_tail: Already in priority queue");
 200
 201         TAILQ_INSERT_TAIL(&pq->pq_lists[prio].pl_head, pthread, pqe);
 202         if (pq->pq_lists[prio].pl_queued == 0)
 203                 /* Insert the list into the priority queue: */
 204                 pq_insert_prio_list(pq, prio);
 205
 206         /* Mark this thread as being in the priority queue. */
 207         pthread->flags |= PTHREAD_FLAGS_IN_PRIOQ;
 208
 209         _PQ_CLEAR_ACTIVE();
 210 }
 211
 212
 213 pthread_t
 214 _pq_first(pq_queue_t *pq)
 215 {
 216         pq_list_t *pql;
 217         pthread_t pthread = NULL;
 218
 219         /*
 220          * Make some assertions when debugging is enabled:
 221          */
 222         _PQ_ASSERT_INACTIVE("_pq_first: pq_active");
 223         _PQ_SET_ACTIVE();
 224
 225         while (((pql = TAILQ_FIRST(&pq->pq_queue)) != NULL) &&
 226             (pthread == NULL)) {
 227                 if ((pthread = TAILQ_FIRST(&pql->pl_head)) == NULL) {
 228                         /*
 229                          * The priority list is empty; remove the list
 230                          * from the queue.
 231                          */
 232                         TAILQ_REMOVE(&pq->pq_queue, pql, pl_link);
 233
 234                         /* Mark the list as not being in the queue: */
 235                         pql->pl_queued = 0;
 236                 }
 237         }
 238
 239         _PQ_CLEAR_ACTIVE();
 240         return (pthread);
 241 }
 242
 243
 244 static void
 245 pq_insert_prio_list(pq_queue_t *pq, int prio)
 246 {
 247         pq_list_t *pql;
 248
 249         /*
 250          * Make some assertions when debugging is enabled:
 251          */
 252         _PQ_ASSERT_ACTIVE("pq_insert_prio_list: pq_active");
 253
 254         /*
 255          * The priority queue is in descending priority order.  Start at
 256          * the beginning of the queue and find the list before which the
 257          * new list should be inserted.
 258          */
 259         pql = TAILQ_FIRST(&pq->pq_queue);
 260         while ((pql != NULL) && (pql->pl_prio > prio))
 261                 pql = TAILQ_NEXT(pql, pl_link);
 262
 263         /* Insert the list: */
 264         if (pql == NULL)
 265                 TAILQ_INSERT_TAIL(&pq->pq_queue, &pq->pq_lists[prio], pl_link);
 266         else
 267                 TAILQ_INSERT_BEFORE(pql, &pq->pq_lists[prio], pl_link);
 268
 269         /* Mark this list as being in the queue: */
 270         pq->pq_lists[prio].pl_queued = 1;
 271 }
 272
 273 #if defined(_PTHREADS_INVARIANTS)
 274 void
 275 _waitq_insert(pthread_t pthread)
 276 {
 277         pthread_t tid;
 278
 279         /*
 280          * Make some assertions when debugging is enabled:
 281          */
 282         _PQ_ASSERT_INACTIVE("_waitq_insert: pq_active");
 283         _PQ_SET_ACTIVE();
 284         _PQ_ASSERT_NOT_QUEUED(pthread, "_waitq_insert: Already in queue");
 285
 286         if (pthread->wakeup_time.tv_sec == -1)
 287                 TAILQ_INSERT_TAIL(&_waitingq, pthread, pqe);
 288         else {
 289                 tid = TAILQ_FIRST(&_waitingq);
 290                 while ((tid != NULL) && (tid->wakeup_time.tv_sec != -1) &&
 291                     ((tid->wakeup_time.tv_sec < pthread->wakeup_time.tv_sec) ||
 292                     ((tid->wakeup_time.tv_sec == pthread->wakeup_time.tv_sec) &&
 293                     (tid->wakeup_time.tv_nsec <= pthread->wakeup_time.tv_nsec))))
 294                         tid = TAILQ_NEXT(tid, pqe);
 295                 if (tid == NULL)
 296                         TAILQ_INSERT_TAIL(&_waitingq, pthread, pqe);
 297                 else
 298                         TAILQ_INSERT_BEFORE(tid, pthread, pqe);
 299         }
 300         pthread->flags |= PTHREAD_FLAGS_IN_WAITQ;
 301
 302         _PQ_CLEAR_ACTIVE();
 303 }
 304
 305 void
 306 _waitq_remove(pthread_t pthread)
 307 {
 308         /*
 309          * Make some assertions when debugging is enabled:
 310          */
 311         _PQ_ASSERT_INACTIVE("_waitq_remove: pq_active");
 312         _PQ_SET_ACTIVE();
 313         _PQ_ASSERT_IN_WAITQ(pthread, "_waitq_remove: Not in queue");
 314
 315         TAILQ_REMOVE(&_waitingq, pthread, pqe);
 316         pthread->flags &= ~PTHREAD_FLAGS_IN_WAITQ;
 317
 318         _PQ_CLEAR_ACTIVE();
 319 }
 320
 321 void
 322 _waitq_setactive(void)
 323 {
 324         _PQ_ASSERT_INACTIVE("_waitq_setactive: pq_active");
 325         _PQ_SET_ACTIVE();
 326 }
 327
 328 void
 329 _waitq_clearactive(void)
 330 {
 331         _PQ_ASSERT_ACTIVE("_waitq_clearactive: ! pq_active");
 332         _PQ_CLEAR_ACTIVE();
 333 }
 334 #endif
 335 #endif