diff options
author | Patrick Williams <iawillia@us.ibm.com> | 2015-02-26 20:43:59 -0600 |
---|---|---|
committer | A. Patrick Williams III <iawillia@us.ibm.com> | 2015-04-24 11:35:17 -0500 |
commit | 598385f7a41daf08999fd8ff2051aa7b176c3ff4 (patch) | |
tree | a0103534a976fc8cfedbe2fe1839ac6261274558 /src/include/util | |
parent | fd19d6a67096de27c5b417dceb5fbb89a3833590 (diff) | |
download | talos-hostboot-598385f7a41daf08999fd8ff2051aa7b176c3ff4.tar.gz talos-hostboot-598385f7a41daf08999fd8ff2051aa7b176c3ff4.zip |
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>
Diffstat (limited to 'src/include/util')
-rw-r--r-- | src/include/util/lockfree/abaptr.H | 205 | ||||
-rw-r--r-- | src/include/util/lockfree/stack.H | 101 |
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); + } } } } |