1 /* 2 * Copyright (c) 2019, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 * 23 */ 24 25 #ifndef SHARE_UTILITIES_LOCKFREESTACK_HPP 26 #define SHARE_UTILITIES_LOCKFREESTACK_HPP 27 28 #include "runtime/atomic.hpp" 29 #include "utilities/debug.hpp" 30 #include "utilities/macros.hpp" 31 32 // The LockFreeStack class template provides a lock-free LIFO. The objects 33 // in the sequence are intrusively linked via a member in the objects. As 34 // a result, there is no allocation involved in adding objects to the stack 35 // or removing them from the stack. 36 // 37 // To be used in a LockFreeStack of objects of type T, an object of 38 // type T must have a list entry member of type T* volatile, with an 39 // non-member accessor function returning a pointer to that member. A 40 // LockFreeStack is associated with the class of its elements and an 41 // entry member from that class. 42 // 43 // An object can be in multiple stacks at the same time, so long as 44 // each stack uses a different entry member. That is, the class of the 45 // object must have multiple LockFreeStack entry members, one for each 46 // stack in which the object may simultaneously be an element. 47 // 48 // LockFreeStacks support polymorphic elements. Because the objects 49 // in a stack are externally managed, rather than being embedded 50 // values in the stack, the actual type of such objects may be more 51 // specific than the stack's element type. 52 // 53 // \tparam T is the class of the elements in the stack. 54 // 55 // \tparam next_ptr is a function pointer. Applying this function to 56 // an object of type T must return a pointer to the list entry member 57 // of the object associated with the LockFreeStack type. 58 template<typename T, T* volatile* (*next_ptr)(T&)> 59 class LockFreeStack { 60 T* volatile _top; 61 62 void prepend_impl(T* first, T* last) { 63 T* cur = top(); 64 T* old; 65 do { 66 old = cur; 67 set_next(*last, cur); 68 cur = Atomic::cmpxchg(&_top, cur, first); 69 } while (old != cur); 70 } 71 72 // Noncopyable. 73 LockFreeStack(const LockFreeStack&); 74 LockFreeStack& operator=(const LockFreeStack&); 75 76 public: 77 LockFreeStack() : _top(NULL) {} 78 ~LockFreeStack() { assert(empty(), "stack not empty"); } 79 80 // Atomically removes the top object from this stack and returns a 81 // pointer to that object, or NULL if this stack is empty. Acts as a 82 // full memory barrier. Subject to ABA behavior; callers must ensure 83 // usage is safe. 84 T* pop() { 85 T* result = top(); 86 T* old; 87 do { 88 old = result; 89 T* new_top = NULL; 90 if (result != NULL) { 91 new_top = next(*result); 92 } 93 // CAS even on empty pop, for consistent membar bahavior. 94 result = Atomic::cmpxchg(&_top, result, new_top); 95 } while (result != old); 96 if (result != NULL) { 97 set_next(*result, NULL); 98 } 99 return result; 100 } 101 102 // Atomically exchange the list of elements with NULL, returning the old 103 // list of elements. Acts as a full memory barrier. 104 // postcondition: empty() 105 T* pop_all() { 106 return Atomic::xchg(&_top, (T*)NULL); 107 } 108 109 // Atomically adds value to the top of this stack. Acts as a full 110 // memory barrier. 111 void push(T& value) { 112 assert(next(value) == NULL, "precondition"); 113 prepend_impl(&value, &value); 114 } 115 116 // Atomically adds the list of objects (designated by first and 117 // last) before the objects already in this stack, in the same order 118 // as in the list. Acts as a full memory barrier. 119 // precondition: next(last) == NULL. 120 // postcondition: top() == &first, next(last) == old top(). 121 void prepend(T& first, T& last) { 122 assert(next(last) == NULL, "precondition"); 123 #ifdef ASSERT 124 for (T* p = &first; p != &last; p = next(*p)) { 125 assert(p != NULL, "invalid prepend list"); 126 } 127 #endif 128 prepend_impl(&first, &last); 129 } 130 131 // Atomically adds the list of objects headed by first before the 132 // objects already in this stack, in the same order as in the list. 133 // Acts as a full memory barrier. 134 // postcondition: top() == &first. 135 void prepend(T& first) { 136 T* last = &first; 137 while (true) { 138 T* step_to = next(*last); 139 if (step_to == NULL) break; 140 last = step_to; 141 } 142 prepend_impl(&first, last); 143 } 144 145 // Return true if the stack is empty. 146 bool empty() const { return top() == NULL; } 147 148 // Return the most recently pushed element, or NULL if the stack is empty. 149 // The returned element is not removed from the stack. 150 T* top() const { return Atomic::load(&_top); } 151 152 // Return the number of objects in the stack. There must be no concurrent 153 // pops while the length is being determined. 154 size_t length() const { 155 size_t result = 0; 156 for (const T* current = top(); current != NULL; current = next(*current)) { 157 ++result; 158 } 159 return result; 160 } 161 162 // Return the entry following value in the list used by the 163 // specialized LockFreeStack class. 164 static T* next(const T& value) { 165 return Atomic::load(next_ptr(const_cast<T&>(value))); 166 } 167 168 // Set the entry following value to new_next in the list used by the 169 // specialized LockFreeStack class. Not thread-safe; in particular, 170 // if value is in an instance of this specialization of LockFreeStack, 171 // there must be no concurrent push or pop operations on that stack. 172 static void set_next(T& value, T* new_next) { 173 Atomic::store(next_ptr(value), new_next); 174 } 175 }; 176 177 #endif // SHARE_UTILITIES_LOCKFREESTACK_HPP