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(first, &_top, cur);
  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(new_top, &_top, result);
  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((T*)NULL, &_top);
 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