blob: d6d022a0b3c38798b85b215d0c28a2f78996b7a9 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
/* IBM_PROLOG_BEGIN_TAG */
/* This is an automatically generated prolog. */
/* */
/* $Source: src/include/util/lockfree/stack.H $ */
/* */
/* OpenPOWER HostBoot Project */
/* */
/* 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. */
/* 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_STACK_H
#define __UTIL_LOCKFREE_STACK_H
#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*);
/**
* Get a pointer to the first element in the stack
* @return the pointer to the first element
* @Note: SMP safety of this pointer is not guaranteed.
*/
_T* first();
private:
_T* head;
enum { TOKEN = 0x5354414B };
};
template <typename _T>
_T* Stack<_T>::first()
{
// Use AbaPtr to extract just the pointer part.
return AbaPtr<_T>(head).get();
}
template <typename _T>
_T* Stack<_T>::pop()
{
// 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)
{
// 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);
}
}
}
}
#endif
|
