1 files changed, 71 insertions, 30 deletions

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);
+                }
             }
     }
 }