1 /* 2 * 3 * Copyright 2016 gRPC authors. 4 * 5 * Licensed under the Apache License, Version 2.0 (the "License"); 6 * you may not use this file except in compliance with the License. 7 * You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 * 17 */ 18 19 #ifndef GRPC_CORE_LIB_GPR_MPSCQ_H 20 #define GRPC_CORE_LIB_GPR_MPSCQ_H 21 22 #include <grpc/support/port_platform.h> 23 24 #include <grpc/support/atm.h> 25 #include <grpc/support/sync.h> 26 #include <stdbool.h> 27 #include <stddef.h> 28 29 // Multiple-producer single-consumer lock free queue, based upon the 30 // implementation from Dmitry Vyukov here: 31 // http://www.1024cores.net/home/lock-free-algorithms/queues/intrusive-mpsc-node-based-queue 32 33 // List node (include this in a data structure at the top, and add application 34 // fields after it - to simulate inheritance) 35 typedef struct gpr_mpscq_node { 36 gpr_atm next; 37 } gpr_mpscq_node; 38 39 // Actual queue type 40 typedef struct gpr_mpscq { 41 gpr_atm head; 42 // make sure head & tail don't share a cacheline 43 char padding[GPR_CACHELINE_SIZE]; 44 gpr_mpscq_node* tail; 45 gpr_mpscq_node stub; 46 } gpr_mpscq; 47 48 void gpr_mpscq_init(gpr_mpscq* q); 49 void gpr_mpscq_destroy(gpr_mpscq* q); 50 // Push a node 51 // Thread safe - can be called from multiple threads concurrently 52 // Returns true if this was possibly the first node (may return true 53 // sporadically, will not return false sporadically) 54 bool gpr_mpscq_push(gpr_mpscq* q, gpr_mpscq_node* n); 55 // Pop a node (returns NULL if no node is ready - which doesn't indicate that 56 // the queue is empty!!) 57 // Thread compatible - can only be called from one thread at a time 58 gpr_mpscq_node* gpr_mpscq_pop(gpr_mpscq* q); 59 // Pop a node; sets *empty to true if the queue is empty, or false if it is not 60 gpr_mpscq_node* gpr_mpscq_pop_and_check_end(gpr_mpscq* q, bool* empty); 61 62 // An mpscq with a lock: it's safe to pop from multiple threads, but doing 63 // only one thread will succeed concurrently 64 typedef struct gpr_locked_mpscq { 65 gpr_mpscq queue; 66 gpr_mu mu; 67 } gpr_locked_mpscq; 68 69 void gpr_locked_mpscq_init(gpr_locked_mpscq* q); 70 void gpr_locked_mpscq_destroy(gpr_locked_mpscq* q); 71 // Push a node 72 // Thread safe - can be called from multiple threads concurrently 73 // Returns true if this was possibly the first node (may return true 74 // sporadically, will not return false sporadically) 75 bool gpr_locked_mpscq_push(gpr_locked_mpscq* q, gpr_mpscq_node* n); 76 77 // Pop a node (returns NULL if no node is ready - which doesn't indicate that 78 // the queue is empty!!) 79 // Thread safe - can be called from multiple threads concurrently 80 gpr_mpscq_node* gpr_locked_mpscq_try_pop(gpr_locked_mpscq* q); 81 82 // Pop a node. Returns NULL only if the queue was empty at some point after 83 // calling this function 84 gpr_mpscq_node* gpr_locked_mpscq_pop(gpr_locked_mpscq* q); 85 86 #endif /* GRPC_CORE_LIB_GPR_MPSCQ_H */ 87
