contrib/bind9/lib/isc/include/isc/queue.h

   1 /*
   2  * Copyright (C) 2011-2013  Internet Systems Consortium, Inc. ("ISC")
   3  *
   4  * Permission to use, copy, modify, and/or distribute this software for any
   5  * purpose with or without fee is hereby granted, provided that the above
   6  * copyright notice and this permission notice appear in all copies.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
   9  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  10  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
  11  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
  12  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  13  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  14  * PERFORMANCE OF THIS SOFTWARE.
  15  */
  16
  17 /* $Id$ */
  18
  19 /*
  20  * This is a generic implementation of a two-lock concurrent queue.
  21  * There are built-in mutex locks for the head and tail of the queue,
  22  * allowing elements to be safely added and removed at the same time.
  23  *
  24  * NULL is "end of list"
  25  * -1 is "not linked"
  26  */
  27
  28 #ifndef ISC_QUEUE_H
  29 #define ISC_QUEUE_H 1
  30 #include <isc/assertions.h>
  31 #include <isc/boolean.h>
  32 #include <isc/mutex.h>
  33
  34 #ifdef ISC_QUEUE_CHECKINIT
  35 #define ISC_QLINK_INSIST(x) ISC_INSIST(x)
  36 #else
  37 #define ISC_QLINK_INSIST(x) (void)0
  38 #endif
  39
  40 #define ISC_QLINK(type) struct { type *prev, *next; }
  41
  42 #define ISC_QLINK_INIT(elt, link) \
  43         do { \
  44                 (elt)->link.next = (elt)->link.prev = (void *)(-1); \
  45         } while(0)
  46
  47 #define ISC_QLINK_LINKED(elt, link) ((void*)(elt)->link.next != (void*)(-1))
  48
  49 #define ISC_QUEUE(type) struct { \
  50         type *head, *tail; \
  51         isc_mutex_t headlock, taillock; \
  52 }
  53
  54 #define ISC_QUEUE_INIT(queue, link) \
  55         do { \
  56                 (void) isc_mutex_init(&(queue).taillock); \
  57                 (void) isc_mutex_init(&(queue).headlock); \
  58                 (queue).tail = (queue).head = NULL; \
  59         } while (0)
  60
  61 #define ISC_QUEUE_EMPTY(queue) ISC_TF((queue).head == NULL)
  62
  63 #define ISC_QUEUE_DESTROY(queue) \
  64         do { \
  65                 ISC_QLINK_INSIST(ISC_QUEUE_EMPTY(queue)); \
  66                 (void) isc_mutex_destroy(&(queue).taillock); \
  67                 (void) isc_mutex_destroy(&(queue).headlock); \
  68         } while (0)
  69
  70 /*
  71  * queues are meant to separate the locks at either end.  For best effect, that
  72  * means keeping the ends separate - i.e. non-empty queues work best.
  73  *
  74  * a push to an empty queue has to take the pop lock to update
  75  * the pop side of the queue.
  76  * Popping the last entry has to take the push lock to update
  77  * the push side of the queue.
  78  *
  79  * The order is (pop, push), because a pop is presumably in the
  80  * latency path and a push is when we're done.
  81  *
  82  * We do an MT hot test in push to see if we need both locks, so we can
  83  * acquire them in order.  Hopefully that makes the case where we get
  84  * the push lock and find we need the pop lock (and have to release it) rare.
  85  *
  86  * > 1 entry - no collision, push works on one end, pop on the other
  87  *   0 entry - headlock race
  88  *     pop wins - return(NULL), push adds new as both head/tail
  89  *     push wins - updates head/tail, becomes 1 entry case.
  90  *   1 entry - taillock race
  91  *     pop wins - return(pop) sets head/tail NULL, becomes 0 entry case
  92  *     push wins - updates {head,tail}->link.next, pop updates head
  93  *                 with new ->link.next and doesn't update tail
  94  *
  95  */
  96 #define ISC_QUEUE_PUSH(queue, elt, link) \
  97         do { \
  98                 isc_boolean_t headlocked = ISC_FALSE; \
  99                 ISC_QLINK_INSIST(!ISC_QLINK_LINKED(elt, link)); \
 100                 if ((queue).head == NULL) { \
 101                         LOCK(&(queue).headlock); \
 102                         headlocked = ISC_TRUE; \
 103                 } \
 104                 LOCK(&(queue).taillock); \
 105                 if ((queue).tail == NULL && !headlocked) { \
 106                         UNLOCK(&(queue).taillock); \
 107                         LOCK(&(queue).headlock); \
 108                         LOCK(&(queue).taillock); \
 109                         headlocked = ISC_TRUE; \
 110                 } \
 111                 (elt)->link.prev = (queue).tail; \
 112                 (elt)->link.next = NULL; \
 113                 if ((queue).tail != NULL) \
 114                         (queue).tail->link.next = (elt); \
 115                 (queue).tail = (elt); \
 116                 UNLOCK(&(queue).taillock); \
 117                 if (headlocked) { \
 118                         if ((queue).head == NULL) \
 119                                 (queue).head = (elt); \
 120                         UNLOCK(&(queue).headlock); \
 121                 } \
 122         } while (0)
 123
 124 #define ISC_QUEUE_POP(queue, link, ret) \
 125         do { \
 126                 LOCK(&(queue).headlock); \
 127                 ret = (queue).head; \
 128                 while (ret != NULL) { \
 129                         if (ret->link.next == NULL) { \
 130                                 LOCK(&(queue).taillock); \
 131                                 if (ret->link.next == NULL) { \
 132                                         (queue).head = (queue).tail = NULL; \
 133                                         UNLOCK(&(queue).taillock); \
 134                                         break; \
 135                                 }\
 136                                 UNLOCK(&(queue).taillock); \
 137                         } \
 138                         (queue).head = ret->link.next; \
 139                         (queue).head->link.prev = NULL; \
 140                         break; \
 141                 } \
 142                 UNLOCK(&(queue).headlock); \
 143                 if (ret != NULL) \
 144                         (ret)->link.next = (ret)->link.prev = (void *)(-1); \
 145         } while(0)
 146
 147 #define ISC_QUEUE_UNLINK(queue, elt, link) \
 148         do { \
 149                 ISC_QLINK_INSIST(ISC_QLINK_LINKED(elt, link)); \
 150                 LOCK(&(queue).headlock); \
 151                 LOCK(&(queue).taillock); \
 152                 if ((elt)->link.prev == NULL) \
 153                         (queue).head = (elt)->link.next; \
 154                 else \
 155                         (elt)->link.prev->link.next = (elt)->link.next; \
 156                 if ((elt)->link.next == NULL) \
 157                         (queue).tail = (elt)->link.prev; \
 158                 else \
 159                         (elt)->link.next->link.prev = (elt)->link.prev; \
 160                 UNLOCK(&(queue).taillock); \
 161                 UNLOCK(&(queue).headlock); \
 162                 (elt)->link.next = (elt)->link.prev = (void *)(-1); \
 163         } while(0)
 164
 165 #endif /* ISC_QUEUE_H */