Implement a lockfree ABA-safe smart pointer.

    * Use algorithm from lockfree stack as basis.
    * Convert lockfree stack to use new ABA-safe pointer.
    * Convert trace service to use ABA-safe pointers on client
      buffer pages to resolve futex hang due to page reuse.

Change-Id: Ib6645f2281db8fa5d81103c1753e548976615797
CQ: FW633818
Backport: release-fips830
Reviewed-on: http://gfw160.aus.stglabs.ibm.com:8080/gerrit/16042
Tested-by: Jenkins Server
Reviewed-by: Brian Silver <bsilver@us.ibm.com>
Reviewed-by: Daniel M. Crowell <dcrowell@us.ibm.com>
Reviewed-by: A. Patrick Williams III <iawillia@us.ibm.com>

2 files changed, 276 insertions, 30 deletions

diff --git a/src/include/util/lockfree/abaptr.H b/src/include/util/lockfree/abaptr.H
new file mode 100644
index 000000000..ed13f83ca
--- /dev/null
+++ b/src/include/util/lockfree/abaptr.H
@@ -0,0 +1,205 @@
+/* IBM_PROLOG_BEGIN_TAG                                                   */
+/* This is an automatically generated prolog.                             */
+/*                                                                        */
+/* $Source: src/include/util/lockfree/abaptr.H $                          */
+/*                                                                        */
+/* OpenPOWER HostBoot Project                                             */
+/*                                                                        */
+/* Contributors Listed Below - COPYRIGHT 2015                             */
+/* [+] International Business Machines Corp.                              */
+/*                                                                        */
+/*                                                                        */
+/* Licensed under the Apache License, Version 2.0 (the "License");        */
+/* you may not use this file except in compliance with the License.       */
+/* You may obtain a copy of the License at                                */
+/*                                                                        */
+/*     http://www.apache.org/licenses/LICENSE-2.0                         */
+/*                                                                        */
+/* Unless required by applicable law or agreed to in writing, software    */
+/* distributed under the License is distributed on an "AS IS" BASIS,      */
+/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or        */
+/* implied. See the License for the specific language governing           */
+/* permissions and limitations under the License.                         */
+/*                                                                        */
+/* IBM_PROLOG_END_TAG                                                     */
+#ifndef __UTIL_LOCKFREE_ABAPTR_H
+#define __UTIL_LOCKFREE_ABAPTR_H
+
+#include <stdint.h>
+#include <assert.h>
+
+namespace Util
+{
+    namespace Lockfree
+    {
+        /** ABA-safe smart pointer class.
+         *
+         *  Lockfree algorithms often utilize atomic operations like
+         *  'compare-and-swap' to identify conditions when another thread
+         *  has caused contention and already modified the same data this
+         *  thread is attempting to modify.  The 'ABA' problem, or 'A-B-A',
+         *  is a common problem class in lockfree algorithms.
+         *
+         *  The desired behavior between two threads is a sequence such as:
+         *     1) 'A' reads a value and begins some calculation.
+         *     2) 'B' updates the value read by 'A'.
+         *     3) 'A' attempts to atomically update the value but fails
+         *        because 'B' has already modified the value in step 2.
+         *
+         *  The typical solution to this program sequence is an atomic update,
+         *  like compare-and-swap, that fails when the value is different
+         *  between steps 1 and 3.
+         *
+         *  When operating with pointers, it is quite possible for a pointer
+         *  to be reused.  Due to pointer reuse, the step 2 update could
+         *  write the same value back as what was read in step 1.  If this
+         *  happens, step 3 will appear to succeed even though it should not.
+         *  This is the ABA problem.  (ABA affects any atomic algorithm where
+         *  values can be reused, but especially impacts pointers)
+         *
+         *  A common 'trick' to solve the ABA problem with pointers, and the
+         *  one implemented here, is to use a rolling value in the upper
+         *  part of a pointer.  The upper N bits are reserved for this rolling
+         *  value and the bottom 64-N bits can be masked off to obtain the
+         *  real pointer value.  N-bits of rolling value results in a
+         *  (1 / 2^N) probability of an incorrectly-successful step 3 when
+         *  there is pointer reuse.
+         *
+         *  Since Hostboot heap memory addresses are all well below 4GB, we
+         *  can use the upper 32 bits as the rolling value.  This yields us
+         *  probability sufficiently close to zero of a pointer reuse at the
+         *  same time as a value reuse.
+         *
+         *  This class acts as a smart-pointer specifically for maintaining
+         *  the ABA-solution properties.
+         */
+        template <typename _T>
+            class AbaPtr
+            {
+                public:
+                    /** Default constructor - set everything to NULL. */
+                    AbaPtr() : original(NULL), ptr(NULL), counter(0) {};
+
+                    /** Construct from existing pointer value. */
+                    explicit AbaPtr(_T* i_ptr) : original(i_ptr),
+                            ptr(_getPtr(i_ptr)),
+                            counter(_getCounter(i_ptr))
+                    {
+                    }
+
+                    /** Assignment operator */
+                    AbaPtr& operator=(_T* i_ptr)
+                    {
+                        original = i_ptr;
+                        ptr = _getPtr(i_ptr);
+                        counter = _getCounter(i_ptr);
+                        return *this;
+                    }
+
+                    /** Set pointer portion.  Update count. */
+                    AbaPtr& set(_T* i_ptr)
+                    {
+                        ptr = _getPtr(i_ptr);
+                        counter++;
+
+                        return *this;
+                    }
+
+                    /** Get pointer. */
+                    _T* get() const
+                    {
+                        return ptr;
+                    }
+
+                    /** Dereference operator. */
+                    _T& operator*() const
+                    {
+                        return *ptr;
+                    }
+
+                    /** Dereference operator. */
+                    _T* operator->() const
+                    {
+                        return ptr;
+                    }
+
+                    /** Perform atomic update of pointer, with ABA properties.
+                     *
+                     *  @param[in] o_ptr - Pointer location to be updated.
+                     *
+                     *  Updates o_ptr with the ABA pointer value from this
+                     *  object if the o_ptr still contains the 'original'
+                     *  value from time of construction or assignment.
+                     */
+                    bool update(_T** o_ptr)
+                    {
+                        return __sync_bool_compare_and_swap(o_ptr,
+                                                            original,
+                                                            _getVal());
+                    }
+
+                    bool update(_T* volatile* o_ptr)
+                    {
+                        return __sync_bool_compare_and_swap(o_ptr,
+                                                            original,
+                                                            _getVal());
+                    }
+
+
+                    /** Get count */
+                    uint32_t count() const
+                    {
+                        return counter;
+                    }
+
+                    /** Set count */
+                    void setCount(uint32_t i_count)
+                    {
+                        counter = i_count;
+                    }
+
+                    /** Get full value */
+                    _T* value() const { return _getVal(); }
+
+                protected:
+
+                    /** Utility function to get 'pointer' part of ABA value. */
+                    static _T* _getPtr(_T* i_ptr)
+                    {
+                        CPPASSERT(sizeof(_T*) == sizeof(uint64_t));
+                        return reinterpret_cast<_T*>(
+                            reinterpret_cast<uint64_t>(i_ptr) & 0x0FFFFFFFFull
+                        );
+                    }
+
+                    /** Utility function to get 'counter' part of ABA value. */
+                    static uint32_t _getCounter(_T* i_ptr)
+                    {
+                        CPPASSERT(sizeof(_T*) == sizeof(uint64_t));
+                        return (reinterpret_cast<uint64_t>(i_ptr) >> 32) &
+                            0x0FFFFFFFFull;
+                    }
+
+                    /** Reconstruct ABA poitner value from components. */
+                    _T* _getVal() const
+                    {
+                        CPPASSERT(sizeof(_T*) == sizeof(uint64_t));
+                        return reinterpret_cast<_T*>(
+                            (static_cast<uint64_t>(counter) << 32) |
+                            (reinterpret_cast<uint64_t>(ptr))
+                        );
+                    }
+
+                private:
+                    /** Prevent operator== because it isn't intuitive for this
+                     *  object. */
+                    bool operator==(const AbaPtr<_T>& i) const;
+
+                    _T* original;
+                    _T* ptr;
+                    uint32_t counter;
+            };
+    }
+}
+
+#endif
diff --git a/src/include/util/lockfree/stack.H b/src/include/util/lockfree/stack.H
index 6cbcd10a5..d6d022a0b 100644
--- a/src/include/util/lockfree/stack.H
+++ b/src/include/util/lockfree/stack.H
@@ -5,7 +5,9 @@
 /*                                                                        */
 /* OpenPOWER HostBoot Project                                             */
 /*                                                                        */
-/* COPYRIGHT International Business Machines Corp. 2010,2014              */
+/* Contributors Listed Below - COPYRIGHT 2010,2015                        */
+/* [+] International Business Machines Corp.                              */
+/*                                                                        */
 /*                                                                        */
 /* Licensed under the Apache License, Version 2.0 (the "License");        */
 /* you may not use this file except in compliance with the License.       */
@@ -25,18 +27,34 @@
 
 #include <stddef.h>
 #include <assert.h>
+#include <util/lockfree/abaptr.H>
 
 namespace Util
 {
     namespace Lockfree
     {
+        /** This is a lockfree stack implementation.
+         *
+         *  This is an intrusive container design, meaning elements being
+         *  added to the stack must have a 'next' member of _T* type.
+         *
+         *  Using the ABAPtr, performs a lockfree implementation of a stack.
+         *  The stack also protects against minor corruption by ensuring that
+         *  the 'next' pointer inside each stored element maintains a magic
+         *  token.
+         *
+         *  Note: Since this uses the ABAPtr pattern, all pointers must be
+         *  only 32-bits in length.
+         */
         template <typename _T>
             class Stack
             {
                 public:
                     Stack() : head(NULL) {};
 
+                    /** Pop an element from the stack. */
                     _T* pop();
+                    /** Push an element to the stack. */
                     void push(_T*);
 
                     /**
@@ -48,50 +66,73 @@ namespace Util
 
                 private:
                     _T* head;
+
+                    enum { TOKEN = 0x5354414B };
             };
 
         template <typename _T>
             _T* Stack<_T>::first()
             {
-                _T * _head = head;
-                return (_T*) (((uint64_t)_head) & 0x00000000FFFFFFFF);
+                // Use AbaPtr to extract just the pointer part.
+                return AbaPtr<_T>(head).get();
             }
 
         template <typename _T>
             _T* Stack<_T>::pop()
             {
-                _T * _head = head;
-                _T * h = (_T*) (((uint64_t)_head) & 0x00000000FFFFFFFF);
-                if (NULL == h) return h;
-                uint64_t token = ((uint64_t)_head) >> 32;
-                token++;
-                uint64_t h_next_v = (uint64_t)(h->next);
-                _T * h_next = (_T*) ((h_next_v & 0x00000000FFFFFFFF) |
-                                     (token << 32));
-                if (!__sync_bool_compare_and_swap(&head,
-                                                  _head,
-                                                  h_next))
-                    return pop();
-
-                crit_assert((h_next_v >> 32) == 0x5354414B);
-                return h;
+                // Save the original head as an AbaPtr.
+                AbaPtr<_T> _head = AbaPtr<_T>(head);
+
+                // Extract the pointer part and check for empty stack.
+                _T* original = _head.get();
+                if (unlikely(NULL == original)) return NULL;
+
+                // Set the head pointer to match the current 'next'.
+                AbaPtr<_T> _next = AbaPtr<_T>(original->next);
+                _head.set(_next.get());
+
+                // Attempt atomic update.  On fail, rerun function and try
+                // again.
+                if (unlikely(!_head.update(&head)))
+                {
+                    return this->pop();
+                }
+
+                // Verify the element wasn't corrupted.
+                // Note: we can't do this until after the atomic has been
+                // successful because otherwise it is possible another thread
+                // has already taken the original head element and so we can't
+                // trust the original->next value.
+                crit_assert(_next.count() == TOKEN);
+
+                // Return the element we popped.
+                return original;
             }
 
         template <typename _T>
             void Stack<_T>::push(_T* p)
             {
-                _T* _head = head;
-                p->next = (_T*) ((((uint64_t)_head) & 0x00000000FFFFFFFF) |
-                          0x5354414B00000000);
-                uint64_t token = ((uint64_t)_head) >> 32;
-                token++;
-
-                _T* _p = (_T*) (((uint64_t)p) | (token << 32));
-
-                if (!__sync_bool_compare_and_swap(&head,
-                                                  _head,
-                                                  _p))
-                    push(p);
+                // Save the original head as an AbaPtr.
+                AbaPtr<_T> _head = AbaPtr<_T>(head);
+
+
+                // Create a 'p->next' AbaPtr and set it to head.
+                AbaPtr<_T> _next = AbaPtr<_T>(p->next);
+                _next.set(_head.get());
+                _next.setCount(TOKEN); // p->next token for corruption detect.
+
+                // Update 'p->next'.
+                // If this fails we have a memory corruption because someone
+                // modified a pointer inside the struct we control.
+                crit_assert(_next.update(&p->next));
+
+                // Atomically update head to point at the new element.
+                // On fail, rerun function and try again.
+                _head.set(p);
+                if (!_head.update(&head))
+                {
+                    return push(p);
+                }
             }
     }
 }