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(LockFreeStack);
  73 
  74 public:
  75   LockFreeStack() : _top(NULL) {}
  76   ~LockFreeStack() { assert(empty(), "stack not empty"); }
  77 
  78   // Atomically removes the top object from this stack and returns a
  79   // pointer to that object, or NULL if this stack is empty. Acts as a
  80   // full memory barrier. Subject to ABA behavior; callers must ensure
  81   // usage is safe.
  82   T* pop() {
  83     T* result = top();
  84     T* old;
  85     do {
  86       old = result;
  87       T* new_top = NULL;
  88       if (result != NULL) {
  89         new_top = next(*result);
  90       }
  91       // CAS even on empty pop, for consistent membar bahavior.
  92       result = Atomic::cmpxchg(&_top, result, new_top);
  93     } while (result != old);
  94     if (result != NULL) {
  95       set_next(*result, NULL);
  96     }
  97     return result;
  98   }
  99 
 100   // Atomically exchange the list of elements with NULL, returning the old
 101   // list of elements.  Acts as a full memory barrier.
 102   // postcondition: empty()
 103   T* pop_all() {
 104     return Atomic::xchg(&_top, (T*)NULL);
 105   }
 106 
 107   // Atomically adds value to the top of this stack.  Acts as a full
 108   // memory barrier.
 109   void push(T& value) {
 110     assert(next(value) == NULL, "precondition");
 111     prepend_impl(&value, &value);
 112   }
 113 
 114   // Atomically adds the list of objects (designated by first and
 115   // last) before the objects already in this stack, in the same order
 116   // as in the list. Acts as a full memory barrier.
 117   // precondition: next(last) == NULL.
 118   // postcondition: top() == &first, next(last) == old top().
 119   void prepend(T& first, T& last) {
 120     assert(next(last) == NULL, "precondition");
 121 #ifdef ASSERT
 122     for (T* p = &first; p != &last; p = next(*p)) {
 123       assert(p != NULL, "invalid prepend list");
 124     }
 125 #endif
 126     prepend_impl(&first, &last);
 127   }
 128 
 129   // Atomically adds the list of objects headed by first before the
 130   // objects already in this stack, in the same order as in the list.
 131   // Acts as a full memory barrier.
 132   // postcondition: top() == &first.
 133   void prepend(T& first) {
 134     T* last = &first;
 135     while (true) {
 136       T* step_to = next(*last);
 137       if (step_to == NULL) break;
 138       last = step_to;
 139     }
 140     prepend_impl(&first, last);
 141   }
 142 
 143   // Return true if the stack is empty.
 144   bool empty() const { return top() == NULL; }
 145 
 146   // Return the most recently pushed element, or NULL if the stack is empty.
 147   // The returned element is not removed from the stack.
 148   T* top() const { return Atomic::load(&_top); }
 149 
 150   // Return the number of objects in the stack.  There must be no concurrent
 151   // pops while the length is being determined.
 152   size_t length() const {
 153     size_t result = 0;
 154     for (const T* current = top(); current != NULL; current = next(*current)) {
 155       ++result;
 156     }
 157     return result;
 158   }
 159 
 160   // Return the entry following value in the list used by the
 161   // specialized LockFreeStack class.
 162   static T* next(const T& value) {
 163     return Atomic::load(next_ptr(const_cast<T&>(value)));
 164   }
 165 
 166   // Set the entry following value to new_next in the list used by the
 167   // specialized LockFreeStack class.  Not thread-safe; in particular,
 168   // if value is in an instance of this specialization of LockFreeStack,
 169   // there must be no concurrent push or pop operations on that stack.
 170   static void set_next(T& value, T* new_next) {
 171     Atomic::store(next_ptr(value), new_next);
 172   }
 173 };
 174 
 175 #endif // SHARE_UTILITIES_LOCKFREESTACK_HPP