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