urcu/workqueue-fifo.h

   1 #ifndef _URCU_WORKQUEUE_FIFO_H
   2 #define _URCU_WORKQUEUE_FIFO_H
   3
   4 /*
   5  * urcu/workqueue-fifo.h
   6  *
   7  * Userspace RCU library - work queue scheme with FIFO semantic
   8  *
   9  * Copyright (c) 2014 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
  10  *
  11  * This library is free software; you can redistribute it and/or
  12  * modify it under the terms of the GNU Lesser General Public
  13  * License as published by the Free Software Foundation; either
  14  * version 2.1 of the License, or (at your option) any later version.
  15  *
  16  * This library is distributed in the hope that it will be useful,
  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  19  * Lesser General Public License for more details.
  20  *
  21  * You should have received a copy of the GNU Lesser General Public
  22  * License along with this library; if not, write to the Free Software
  23  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  24  */
  25
  26 #include <urcu/uatomic.h>
  27 #include <urcu/wfstack.h>
  28 #include <urcu/waitqueue-lifo.h>
  29 #include <urcu/wfcqueue.h>
  30 #include <urcu/rculist.h>
  31 #include <pthread.h>
  32
  33 /*
  34  * We use RCU to steal work from siblings. Therefore, one of RCU flavors
  35  * need to be included before this header. All worker that participate
  36  * in stealing (initialized with the URCU_WORKER_STEAL flag) need to be
  37  * registered RCU readers threads.
  38  */
  39
  40 struct urcu_work {
  41         struct cds_wfcq_node node;
  42 };
  43
  44 struct urcu_workqueue {
  45         /* FIFO work queue */
  46         struct __cds_wfcq_head head;
  47         struct cds_wfcq_tail tail;
  48
  49         /* Associated wait queue for LIFO wait/wakeup */
  50         struct urcu_wait_queue waitqueue;
  51
  52         /* RCU linked list head of siblings for work stealing. */
  53         struct cds_list_head sibling_head;
  54         pthread_mutex_t sibling_lock;   /* Protect sibling list updates */
  55 };
  56
  57 struct urcu_worker {
  58         struct cds_wfcq_head head;
  59         struct cds_wfcq_tail tail;
  60
  61         struct urcu_wait_node wait_node;
  62         /* RCU linked list node of siblings for work stealing. */
  63         struct cds_list_head sibling_node;
  64         int flags;      /* enum urcu_worker_flags */
  65 };
  66
  67 enum urcu_worker_flags {
  68         URCU_WORKER_STEAL       = (1 << 0),
  69 };
  70
  71 static inline
  72 void urcu_workqueue_init(struct urcu_workqueue *queue)
  73 {
  74         __cds_wfcq_init(&queue->head, &queue->tail);
  75         urcu_wait_queue_init(&queue->waitqueue);
  76         CDS_INIT_LIST_HEAD(&queue->sibling_head);
  77 }
  78
  79 static inline
  80 void urcu_queue_work(struct urcu_workqueue *queue, struct urcu_work *work)
  81 {
  82         bool was_empty;
  83
  84         cds_wfcq_node_init(&work->node);
  85
  86         /* Enqueue work. */
  87         was_empty = !cds_wfcq_enqueue(&queue->head, &queue->tail,
  88                         &work->node);
  89         /*
  90          * If workqueue was previously empty, wakeup one worker thread.
  91          * It will eventually grab the entire content of the work-queue
  92          * (therefore grabbing a "work batch"). After having grabbed the
  93          * work batch, while that thread is running and taking care of
  94          * that work batch, when we enqueue more work, we will wake
  95          * another thread (if there is one waiting), which will
  96          * eventually grab the new batch, and so on. This scheme ensures
  97          * that contiguous batch of work are handled by the same thread
  98          * (for locality), and also ensures that we scale work to many
  99          * worker threads when threads are busy enough to still be
 100          * running when work is enqueued.
 101          */
 102         if (was_empty)
 103                 (void) urcu_dequeue_wake_single(&queue->waitqueue);
 104 }
 105
 106 static inline
 107 void urcu_workqueue_wakeup_all(struct urcu_workqueue *queue)
 108 {
 109         struct urcu_waiters waiters;
 110
 111         urcu_move_waiters(&waiters, &queue->waitqueue);
 112         (void) urcu_wake_all_waiters(&waiters);
 113 }
 114
 115 static inline
 116 void urcu_worker_init(struct urcu_worker *worker, int flags)
 117 {
 118         cds_wfcq_init(&worker->head, &worker->tail);
 119         worker->flags = flags;
 120         urcu_wait_node_init(&worker->wait_node, URCU_WAIT_RUNNING);
 121 }
 122
 123 static inline
 124 void urcu_worker_register(struct urcu_workqueue *queue,
 125                 struct urcu_worker *worker)
 126 {
 127         if (worker->flags & URCU_WORKER_STEAL) {
 128                 pthread_mutex_lock(&queue->sibling_lock);
 129                 cds_list_add_rcu(&worker->sibling_node, &queue->sibling_head);
 130                 pthread_mutex_unlock(&queue->sibling_lock);
 131         }
 132 }
 133
 134 static inline
 135 void urcu_worker_unregister(struct urcu_workqueue *queue,
 136                 struct urcu_worker *worker)
 137 {
 138         enum cds_wfcq_ret wfcq_ret;
 139
 140         if (worker->flags & URCU_WORKER_STEAL) {
 141                 pthread_mutex_lock(&queue->sibling_lock);
 142                 cds_list_del_rcu(&worker->sibling_node);
 143                 pthread_mutex_unlock(&queue->sibling_lock);
 144
 145                 /*
 146                  * Wait for grace period before freeing or reusing
 147                  * "worker" because used by RCU linked list.
 148                  */
 149                 synchronize_rcu();
 150         }
 151
 152         /*
 153          * Put any local work we still have back into the workqueue.
 154          */
 155         wfcq_ret = __cds_wfcq_splice_blocking(&queue->head,
 156                         &queue->tail,
 157                         &worker->head,
 158                         &worker->tail);
 159         if (wfcq_ret != CDS_WFCQ_RET_SRC_EMPTY
 160                         && wfcq_ret == CDS_WFCQ_RET_DEST_EMPTY) {
 161                 /*
 162                  * Wakeup worker thread if we have put work back into
 163                  * workqueue that was previously empty.
 164                  */
 165                 (void) urcu_dequeue_wake_single(&queue->waitqueue);
 166         }
 167 }
 168
 169 /*
 170  * Try stealing work from siblings when we have nothing to do.
 171  */
 172 static inline
 173 void ___urcu_steal_work(struct urcu_worker *worker,
 174                 struct urcu_worker *sibling)
 175 {
 176         /*
 177          * Don't bother grabbing the sibling queue lock if it is empty.
 178          */
 179         if (cds_wfcq_empty(&sibling->head, &sibling->tail))
 180                 return;
 181         cds_wfcq_dequeue_lock(&sibling->head, &sibling->tail);
 182         (void) __cds_wfcq_splice_blocking(&worker->head,
 183                         &worker->tail,
 184                         &sibling->head,
 185                         &sibling->tail);
 186         cds_wfcq_dequeue_unlock(&sibling->head, &sibling->tail);
 187 }
 188
 189 static inline
 190 int __urcu_steal_work(struct urcu_workqueue *queue,
 191                 struct urcu_worker *worker)
 192 {
 193         struct urcu_worker *sibling_prev, *sibling_next;
 194         struct cds_list_head *sibling_node;
 195
 196         if (!(worker->flags & URCU_WORKER_STEAL))
 197                 return 0;
 198
 199         rcu_read_lock();
 200
 201         sibling_node = rcu_dereference(worker->sibling_node.next);
 202         if (sibling_node == &queue->sibling_head)
 203                 sibling_node = rcu_dereference(sibling_node->next);
 204         sibling_next = caa_container_of(sibling_node, struct urcu_worker,
 205                         sibling_node);
 206         if (sibling_next != worker)
 207                 ___urcu_steal_work(worker, sibling_next);
 208
 209         sibling_node = rcu_dereference(worker->sibling_node.prev);
 210         if (sibling_node == &queue->sibling_head)
 211                 sibling_node = rcu_dereference(sibling_node->prev);
 212         sibling_prev = caa_container_of(sibling_node, struct urcu_worker,
 213                         sibling_node);
 214         if (sibling_prev != worker && sibling_prev != sibling_next)
 215                 ___urcu_steal_work(worker, sibling_prev);
 216
 217         rcu_read_unlock();
 218
 219         return !cds_wfcq_empty(&worker->head, &worker->tail);
 220 }
 221
 222 static inline
 223 bool ___urcu_wakeup_sibling(struct urcu_worker *sibling)
 224 {
 225         return urcu_adaptative_wake_up(&sibling->wait_node);
 226 }
 227
 228 static inline
 229 bool __urcu_wakeup_siblings(struct urcu_workqueue *queue,
 230                 struct urcu_worker *worker)
 231 {
 232         struct urcu_worker *sibling_prev, *sibling_next;
 233         struct cds_list_head *sibling_node;
 234         bool wakeup_performed = 0;
 235
 236         if (!(worker->flags & URCU_WORKER_STEAL))
 237                 return;
 238
 239         /* Only wakeup siblings if we have work in our own queue. */
 240         if (cds_wfcq_empty(&worker->head, &worker->tail))
 241                 return;
 242
 243         rcu_read_lock();
 244
 245         sibling_node = rcu_dereference(worker->sibling_node.next);
 246         if (sibling_node == &queue->sibling_head)
 247                 sibling_node = rcu_dereference(sibling_node->next);
 248         sibling_next = caa_container_of(sibling_node, struct urcu_worker,
 249                         sibling_node);
 250         if (sibling_next != worker)
 251                 wakeup_performed = ___urcu_wakeup_sibling(sibling_next);
 252         if (wakeup_performed)
 253                 goto end;
 254
 255         sibling_node = rcu_dereference(worker->sibling_node.prev);
 256         if (sibling_node == &queue->sibling_head)
 257                 sibling_node = rcu_dereference(sibling_node->prev);
 258         sibling_prev = caa_container_of(sibling_node, struct urcu_worker,
 259                         sibling_node);
 260         if (sibling_prev != worker && sibling_prev != sibling_next)
 261                 wakeup_performed = ___urcu_wakeup_sibling(sibling_prev);
 262 end:
 263         rcu_read_unlock();
 264
 265         return wakeup_performed;
 266 }
 267
 268 static inline
 269 void urcu_accept_work(struct urcu_workqueue *queue,
 270                 struct urcu_worker *worker,
 271                 int blocking)
 272 {
 273         enum cds_wfcq_ret wfcq_ret;
 274
 275         wfcq_ret = __cds_wfcq_splice_blocking(&worker->head,
 276                         &worker->tail,
 277                         &queue->head,
 278                         &queue->tail);
 279         /* Don't wait if we have work to do. */
 280         if (wfcq_ret != CDS_WFCQ_RET_SRC_EMPTY
 281                         || !cds_wfcq_empty(&worker->head,
 282                                 &worker->tail))
 283                 goto do_work;
 284         /* Try to steal work from sibling instead of blocking */
 285         if (__urcu_steal_work(queue, worker))
 286                 goto do_work;
 287         if (!blocking)
 288                 return;
 289         urcu_wait_set_state(&worker->wait_node,
 290                         URCU_WAIT_WAITING);
 291         if (!CMM_LOAD_SHARED(worker->wait_node.node.next)) {
 292                 int was_empty;
 293
 294                 /*
 295                  * NULL next pointer. We are therefore not in
 296                  * the queue.
 297                  */
 298                 cds_wfs_node_init(&worker->wait_node.node);
 299                 was_empty = !urcu_wait_add(&queue->waitqueue,
 300                                 &worker->wait_node);
 301                 /*
 302                  * If the wait queue was empty, it means we are the
 303                  * first thread to be put back into an otherwise empty
 304                  * wait queue. Re-check if work queue is empty after
 305                  * adding ourself to wait queue, so we can wakeup the
 306                  * top of wait queue since new work have appeared, and
 307                  * work enqueuer may not have seen that it needed to do
 308                  * a wake up.
 309                  */
 310                 if (was_empty && !cds_wfcq_empty(&queue->head,
 311                                                 &queue->tail))
 312                         (void) urcu_dequeue_wake_single(&queue->waitqueue);
 313         } else {
 314                 /*
 315                  * Non-NULL next pointer. We are therefore in
 316                  * the queue, or the dispatcher just removed us
 317                  * from it (after we read the next pointer), and
 318                  * is therefore awakening us. The state will
 319                  * therefore have been changed from WAITING to
 320                  * some other state, which will let the busy
 321                  * wait pass through.
 322                  */
 323         }
 324         urcu_adaptative_busy_wait(&worker->wait_node);
 325         return;
 326
 327 do_work:
 328         /*
 329          * We will be busy handling the work batch, awaken siblings so
 330          * they can steal from us.
 331          */
 332         (void) __urcu_wakeup_siblings(queue, worker);
 333 }
 334
 335 static inline
 336 struct urcu_work *urcu_dequeue_work(struct urcu_worker *worker)
 337 {
 338         struct cds_wfcq_node *node;
 339
 340         /*
 341          * If we are registered for work stealing, we need to dequeue
 342          * safely against siblings.
 343          */
 344         if (worker->flags & URCU_WORKER_STEAL) {
 345                 /*
 346                  * Don't bother grabbing the worker queue lock if it is
 347                  * empty.
 348                  */
 349                 if (cds_wfcq_empty(&worker->head, &worker->tail))
 350                         return NULL;
 351                 node = cds_wfcq_dequeue_blocking(&worker->head,
 352                                 &worker->tail);
 353         } else {
 354                 node = ___cds_wfcq_dequeue_with_state(&worker->head,
 355                                 &worker->tail, NULL, 1, 0);
 356         }
 357         if (!node)
 358                 return NULL;
 359         return caa_container_of(node, struct urcu_work, node);
 360 }
 361
 362 #endif /* _URCU_WORKQUEUE_FIFO_H */