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: src/lib/libc_r/uthread/uthread_priority_queue.c,v 1.5.2.3 2002/10/22 14:44:03 fjoe Exp $
  33  */
  34 #include <stdlib.h>
  35 #include <sys/queue.h>
  36 #include <string.h>
  37 #include <pthread.h>
  38 #include "pthread_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 static int _pq_active = 0;
  46
  47 #define _PQ_IN_SCHEDQ   (PTHREAD_FLAGS_IN_PRIOQ | PTHREAD_FLAGS_IN_WAITQ | PTHREAD_FLAGS_IN_WORKQ)
  48
  49 #define _PQ_SET_ACTIVE()                _pq_active = 1
  50 #define _PQ_CLEAR_ACTIVE()              _pq_active = 0
  51 #define _PQ_ASSERT_ACTIVE(msg)          do {            \
  52         if (_pq_active == 0)                            \
  53                 PANIC(msg);                             \
  54 } while (0)
  55 #define _PQ_ASSERT_INACTIVE(msg)        do {            \
  56         if (_pq_active != 0)                            \
  57                 PANIC(msg);                             \
  58 } while (0)
  59 #define _PQ_ASSERT_IN_WAITQ(thrd, msg)  do {            \
  60         if (((thrd)->flags & PTHREAD_FLAGS_IN_WAITQ) == 0) \
  61                 PANIC(msg);                             \
  62 } while (0)
  63 #define _PQ_ASSERT_IN_PRIOQ(thrd, msg)  do {            \
  64         if (((thrd)->flags & PTHREAD_FLAGS_IN_PRIOQ) == 0) \
  65                 PANIC(msg);                             \
  66 } while (0)
  67 #define _PQ_ASSERT_NOT_QUEUED(thrd, msg) do {           \
  68         if (((thrd)->flags & _PQ_IN_SCHEDQ) != 0)       \
  69                 PANIC(msg);                             \
  70 } while (0)
  71 #define _PQ_ASSERT_PROTECTED(msg)                       \
  72         PTHREAD_ASSERT((_thread_kern_in_sched != 0) ||  \
  73             ((_get_curthread())->sig_defer_count > 0) ||\
  74             (_sig_in_handler != 0), msg);
  75
  76 #else
  77
  78 #define _PQ_SET_ACTIVE()
  79 #define _PQ_CLEAR_ACTIVE()
  80 #define _PQ_ASSERT_ACTIVE(msg)
  81 #define _PQ_ASSERT_INACTIVE(msg)
  82 #define _PQ_ASSERT_IN_WAITQ(thrd, msg)
  83 #define _PQ_ASSERT_IN_PRIOQ(thrd, msg)
  84 #define _PQ_ASSERT_NOT_QUEUED(thrd, msg)
  85 #define _PQ_ASSERT_PROTECTED(msg)
  86
  87 #endif
  88
  89 int
  90 _pq_alloc(pq_queue_t *pq, int minprio, int maxprio)
  91 {
  92         int ret = 0;
  93         int prioslots = maxprio - minprio + 1;
  94
  95         if (pq == NULL)
  96                 ret = -1;
  97
  98         /* Create the priority queue with (maxprio - minprio + 1) slots: */
  99         else if ((pq->pq_lists =
 100             (pq_list_t *) malloc(sizeof(pq_list_t) * prioslots)) == NULL)
 101                 ret = -1;
 102
 103         else {
 104                 /* Remember the queue size: */
 105                 pq->pq_size = prioslots;
 106                 ret = _pq_init(pq);
 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         _PQ_ASSERT_PROTECTED("_pq_remove: prioq not protected!");
 146
 147         /*
 148          * Remove this thread from priority list.  Note that if
 149          * the priority list becomes empty, it is not removed
 150          * from the priority queue because another thread may be
 151          * added to the priority list (resulting in a needless
 152          * removal/insertion).  Priority lists are only removed
 153          * from the priority queue when _pq_first is called.
 154          */
 155         TAILQ_REMOVE(&pq->pq_lists[prio].pl_head, pthread, pqe);
 156
 157         /* This thread is now longer in the priority queue. */
 158         pthread->flags &= ~PTHREAD_FLAGS_IN_PRIOQ;
 159
 160         _PQ_CLEAR_ACTIVE();
 161 }
 162
 163
 164 void
 165 _pq_insert_head(pq_queue_t *pq, pthread_t pthread)
 166 {
 167         int prio;
 168
 169         /*
 170          * Don't insert suspended threads into the priority queue.
 171          * The caller is responsible for setting the threads state.
 172          */
 173         if ((pthread->flags & PTHREAD_FLAGS_SUSPENDED) != 0) {
 174                 /* Make sure the threads state is suspended. */
 175                 if (pthread->state != PS_SUSPENDED)
 176                         PTHREAD_SET_STATE(pthread, PS_SUSPENDED);
 177         } else {
 178                 /*
 179                  * Make some assertions when debugging is enabled:
 180                  */
 181                 _PQ_ASSERT_INACTIVE("_pq_insert_head: pq_active");
 182                 _PQ_SET_ACTIVE();
 183                 _PQ_ASSERT_NOT_QUEUED(pthread,
 184                     "_pq_insert_head: Already in priority queue");
 185                 _PQ_ASSERT_PROTECTED("_pq_insert_head: prioq not protected!");
 186
 187                 prio = pthread->active_priority;
 188                 TAILQ_INSERT_HEAD(&pq->pq_lists[prio].pl_head, pthread, pqe);
 189                 if (pq->pq_lists[prio].pl_queued == 0)
 190                         /* Insert the list into the priority queue: */
 191                         pq_insert_prio_list(pq, prio);
 192
 193                 /* Mark this thread as being in the priority queue. */
 194                 pthread->flags |= PTHREAD_FLAGS_IN_PRIOQ;
 195
 196                 _PQ_CLEAR_ACTIVE();
 197         }
 198 }
 199
 200
 201 void
 202 _pq_insert_tail(pq_queue_t *pq, pthread_t pthread)
 203 {
 204         int prio;
 205
 206         /*
 207          * Don't insert suspended threads into the priority queue.
 208          * The caller is responsible for setting the threads state.
 209          */
 210         if ((pthread->flags & PTHREAD_FLAGS_SUSPENDED) != 0) {
 211                 /* Make sure the threads state is suspended. */
 212                 if (pthread->state != PS_SUSPENDED)
 213                         PTHREAD_SET_STATE(pthread, PS_SUSPENDED);
 214         } else {
 215                 /*
 216                  * Make some assertions when debugging is enabled:
 217                  */
 218                 _PQ_ASSERT_INACTIVE("_pq_insert_tail: pq_active");
 219                 _PQ_SET_ACTIVE();
 220                 _PQ_ASSERT_NOT_QUEUED(pthread,
 221                     "_pq_insert_tail: Already in priority queue");
 222                 _PQ_ASSERT_PROTECTED("_pq_insert_tail: prioq not protected!");
 223
 224                 prio = pthread->active_priority;
 225                 TAILQ_INSERT_TAIL(&pq->pq_lists[prio].pl_head, pthread, pqe);
 226                 if (pq->pq_lists[prio].pl_queued == 0)
 227                         /* Insert the list into the priority queue: */
 228                         pq_insert_prio_list(pq, prio);
 229
 230                 /* Mark this thread as being in the priority queue. */
 231                 pthread->flags |= PTHREAD_FLAGS_IN_PRIOQ;
 232
 233                 _PQ_CLEAR_ACTIVE();
 234         }
 235 }
 236
 237
 238 pthread_t
 239 _pq_first(pq_queue_t *pq)
 240 {
 241         pq_list_t *pql;
 242         pthread_t pthread = NULL;
 243
 244         /*
 245          * Make some assertions when debugging is enabled:
 246          */
 247         _PQ_ASSERT_INACTIVE("_pq_first: pq_active");
 248         _PQ_SET_ACTIVE();
 249         _PQ_ASSERT_PROTECTED("_pq_first: prioq not protected!");
 250
 251         while (((pql = TAILQ_FIRST(&pq->pq_queue)) != NULL) &&
 252             (pthread == NULL)) {
 253                 if ((pthread = TAILQ_FIRST(&pql->pl_head)) == NULL) {
 254                         /*
 255                          * The priority list is empty; remove the list
 256                          * from the queue.
 257                          */
 258                         TAILQ_REMOVE(&pq->pq_queue, pql, pl_link);
 259
 260                         /* Mark the list as not being in the queue: */
 261                         pql->pl_queued = 0;
 262                 } else if ((pthread->flags & PTHREAD_FLAGS_SUSPENDED) != 0) {
 263                         /*
 264                          * This thread is suspended; remove it from the
 265                          * list and ensure its state is suspended.
 266                          */
 267                         TAILQ_REMOVE(&pql->pl_head, pthread, pqe);
 268                         PTHREAD_SET_STATE(pthread, PS_SUSPENDED);
 269
 270                         /* This thread is now longer in the priority queue. */
 271                         pthread->flags &= ~PTHREAD_FLAGS_IN_PRIOQ;
 272                         pthread = NULL;
 273                 }
 274         }
 275
 276         _PQ_CLEAR_ACTIVE();
 277         return (pthread);
 278 }
 279
 280
 281 static void
 282 pq_insert_prio_list(pq_queue_t *pq, int prio)
 283 {
 284         pq_list_t *pql;
 285
 286         /*
 287          * Make some assertions when debugging is enabled:
 288          */
 289         _PQ_ASSERT_ACTIVE("pq_insert_prio_list: pq_active");
 290         _PQ_ASSERT_PROTECTED("_pq_insert_prio_list: prioq not protected!");
 291
 292         /*
 293          * The priority queue is in descending priority order.  Start at
 294          * the beginning of the queue and find the list before which the
 295          * new list should be inserted.
 296          */
 297         pql = TAILQ_FIRST(&pq->pq_queue);
 298         while ((pql != NULL) && (pql->pl_prio > prio))
 299                 pql = TAILQ_NEXT(pql, pl_link);
 300
 301         /* Insert the list: */
 302         if (pql == NULL)
 303                 TAILQ_INSERT_TAIL(&pq->pq_queue, &pq->pq_lists[prio], pl_link);
 304         else
 305                 TAILQ_INSERT_BEFORE(pql, &pq->pq_lists[prio], pl_link);
 306
 307         /* Mark this list as being in the queue: */
 308         pq->pq_lists[prio].pl_queued = 1;
 309 }
 310
 311 void
 312 _waitq_insert(pthread_t pthread)
 313 {
 314         pthread_t       tid;
 315
 316         /*
 317          * Make some assertions when debugging is enabled:
 318          */
 319         _PQ_ASSERT_INACTIVE("_waitq_insert: pq_active");
 320         _PQ_SET_ACTIVE();
 321         _PQ_ASSERT_NOT_QUEUED(pthread, "_waitq_insert: Already in queue");
 322
 323         if (pthread->wakeup_time.tv_sec == -1)
 324                 TAILQ_INSERT_TAIL(&_waitingq, pthread, pqe);
 325         else {
 326                 tid = TAILQ_FIRST(&_waitingq);
 327                 while ((tid != NULL) && (tid->wakeup_time.tv_sec != -1) &&
 328                     ((tid->wakeup_time.tv_sec < pthread->wakeup_time.tv_sec) ||
 329                     ((tid->wakeup_time.tv_sec == pthread->wakeup_time.tv_sec) &&
 330                     (tid->wakeup_time.tv_nsec <= pthread->wakeup_time.tv_nsec))))
 331                         tid = TAILQ_NEXT(tid, pqe);
 332                 if (tid == NULL)
 333                         TAILQ_INSERT_TAIL(&_waitingq, pthread, pqe);
 334                 else
 335                         TAILQ_INSERT_BEFORE(tid, pthread, pqe);
 336         }
 337         pthread->flags |= PTHREAD_FLAGS_IN_WAITQ;
 338
 339         _PQ_CLEAR_ACTIVE();
 340 }
 341
 342 void
 343 _waitq_remove(pthread_t pthread)
 344 {
 345         /*
 346          * Make some assertions when debugging is enabled:
 347          */
 348         _PQ_ASSERT_INACTIVE("_waitq_remove: pq_active");
 349         _PQ_SET_ACTIVE();
 350         _PQ_ASSERT_IN_WAITQ(pthread, "_waitq_remove: Not in queue");
 351
 352         TAILQ_REMOVE(&_waitingq, pthread, pqe);
 353         pthread->flags &= ~PTHREAD_FLAGS_IN_WAITQ;
 354
 355         _PQ_CLEAR_ACTIVE();
 356 }
 357
 358 void
 359 _waitq_setactive(void)
 360 {
 361         _PQ_ASSERT_INACTIVE("_waitq_setactive: pq_active");
 362         _PQ_SET_ACTIVE();
 363 }
 364
 365 void
 366 _waitq_clearactive(void)
 367 {
 368         _PQ_ASSERT_ACTIVE("_waitq_clearactive: ! pq_active");
 369         _PQ_CLEAR_ACTIVE();
 370 }