1 /* 2 A modified version of Bounded MPMC queue by Dmitry Vyukov. 3 4 Original code from: 5 http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue 6 7 licensed by Dmitry Vyukov under the terms below: 8 9 Simplified BSD license 10 11 Copyright (c) 2010-2011 Dmitry Vyukov. All rights reserved. 12 Redistribution and use in source and binary forms, with or without modification, 13 are permitted provided that the following conditions are met: 14 1. Redistributions of source code must retain the above copyright notice, this list of 15 conditions and the following disclaimer. 16 17 2. Redistributions in binary form must reproduce the above copyright notice, this list 18 of conditions and the following disclaimer in the documentation and/or other materials 19 provided with the distribution. 20 21 THIS SOFTWARE IS PROVIDED BY DMITRY VYUKOV "AS IS" AND ANY EXPRESS OR IMPLIED 22 WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 23 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT 24 SHALL DMITRY VYUKOV OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 25 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 26 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, 27 OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 28 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE 29 OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 30 ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 32 The views and conclusions contained in the software and documentation are those of the authors and 33 should not be interpreted as representing official policies, either expressed or implied, of Dmitry Vyukov. 34 */ 35 36 /* 37 The code in its current form adds the license below: 38 39 Copyright(c) 2015 Gabi Melman. 40 Distributed under the MIT License (http://opensource.org/licenses/MIT) 41 42 */ 43 44 #pragma once 45 46 #include <spdlog/common.h> 47 48 #include <atomic> 49 #include <utility> 50 51 namespace spdlog 52 { 53 namespace details 54 { 55 56 template<typename T> 57 class mpmc_bounded_queue 58 { 59 public: 60 61 using item_type = T; mpmc_bounded_queue(size_t buffer_size)62 mpmc_bounded_queue(size_t buffer_size) 63 :max_size_(buffer_size), 64 buffer_(new cell_t [buffer_size]), 65 buffer_mask_(buffer_size - 1) 66 { 67 //queue size must be power of two 68 if(!((buffer_size >= 2) && ((buffer_size & (buffer_size - 1)) == 0))) 69 throw spdlog_ex("async logger queue size must be power of two"); 70 71 for (size_t i = 0; i != buffer_size; i += 1) 72 buffer_[i].sequence_.store(i, std::memory_order_relaxed); 73 enqueue_pos_.store(0, std::memory_order_relaxed); 74 dequeue_pos_.store(0, std::memory_order_relaxed); 75 } 76 ~mpmc_bounded_queue()77 ~mpmc_bounded_queue() 78 { 79 delete [] buffer_; 80 } 81 82 enqueue(T && data)83 bool enqueue(T&& data) 84 { 85 cell_t* cell; 86 size_t pos = enqueue_pos_.load(std::memory_order_relaxed); 87 for (;;) 88 { 89 cell = &buffer_[pos & buffer_mask_]; 90 size_t seq = cell->sequence_.load(std::memory_order_acquire); 91 intptr_t dif = (intptr_t)seq - (intptr_t)pos; 92 if (dif == 0) 93 { 94 if (enqueue_pos_.compare_exchange_weak(pos, pos + 1, std::memory_order_relaxed)) 95 break; 96 } 97 else if (dif < 0) 98 { 99 return false; 100 } 101 else 102 { 103 pos = enqueue_pos_.load(std::memory_order_relaxed); 104 } 105 } 106 cell->data_ = std::move(data); 107 cell->sequence_.store(pos + 1, std::memory_order_release); 108 return true; 109 } 110 dequeue(T & data)111 bool dequeue(T& data) 112 { 113 cell_t* cell; 114 size_t pos = dequeue_pos_.load(std::memory_order_relaxed); 115 for (;;) 116 { 117 cell = &buffer_[pos & buffer_mask_]; 118 size_t seq = 119 cell->sequence_.load(std::memory_order_acquire); 120 intptr_t dif = (intptr_t)seq - (intptr_t)(pos + 1); 121 if (dif == 0) 122 { 123 if (dequeue_pos_.compare_exchange_weak(pos, pos + 1, std::memory_order_relaxed)) 124 break; 125 } 126 else if (dif < 0) 127 return false; 128 else 129 pos = dequeue_pos_.load(std::memory_order_relaxed); 130 } 131 data = std::move(cell->data_); 132 cell->sequence_.store(pos + buffer_mask_ + 1, std::memory_order_release); 133 return true; 134 } 135 approx_size()136 size_t approx_size() 137 { 138 size_t first_pos = dequeue_pos_.load(std::memory_order_relaxed); 139 size_t last_pos = enqueue_pos_.load(std::memory_order_relaxed); 140 if (last_pos <= first_pos) 141 return 0; 142 auto size = last_pos - first_pos; 143 return size < max_size_ ? size : max_size_; 144 } 145 146 private: 147 struct cell_t 148 { 149 std::atomic<size_t> sequence_; 150 T data_; 151 }; 152 153 size_t const max_size_; 154 155 static size_t const cacheline_size = 64; 156 typedef char cacheline_pad_t [cacheline_size]; 157 158 cacheline_pad_t pad0_; 159 cell_t* const buffer_; 160 size_t const buffer_mask_; 161 cacheline_pad_t pad1_; 162 std::atomic<size_t> enqueue_pos_; 163 cacheline_pad_t pad2_; 164 std::atomic<size_t> dequeue_pos_; 165 cacheline_pad_t pad3_; 166 167 mpmc_bounded_queue(mpmc_bounded_queue const&) = delete; 168 void operator= (mpmc_bounded_queue const&) = delete; 169 }; 170 171 } // ns details 172 } // ns spdlog 173