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
|
// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
#pragma once
#include "common.h"
#include <algorithm>
namespace vespamalloc {
/**
* @brief Pointer and tag - use instead of bare pointer for cmpSwap()
*
* When making a lock-free data structure by using cmpSwap
* on pointers, you'll often run into the "ABA problem", see
* http://en.wikipedia.org/wiki/ABA_problem for details.
* The TaggedPtr makes it easy to do the woraround with tag bits,
* but requires the double-word compare-and-swap instruction.
* Very early Amd K7/8 CPUs are lacking this and will fail (Illegal Instruction).
**/
struct TaggedPtrT {
TaggedPtrT() noexcept : _ptr(nullptr), _tag(0) { }
TaggedPtrT(void *h, size_t t) noexcept : _ptr(h), _tag(t) {}
void *_ptr;
size_t _tag;
};
#if defined(__x86_64__)
struct AtomicTaggedPtr {
AtomicTaggedPtr() noexcept : _ptr(nullptr), _tag(0) { }
AtomicTaggedPtr(void *h, size_t t) noexcept : _ptr(h), _tag(t) {}
AtomicTaggedPtr load(std::memory_order = std::memory_order_seq_cst) {
// Note that this is NOT an atomic load. The current use as the initial load
// in a compare_exchange loop is safe as a teared load will just give a retry.
return *this;
}
void store(AtomicTaggedPtr ptr) {
// Note that this is NOT an atomic store. The current use is in a unit test as an initial
// store before any threads are started. Just done so to keep api compatible with std::atomic as
// that is the preferred implementation..
*this = ptr;
}
bool
compare_exchange_weak(AtomicTaggedPtr & oldPtr, AtomicTaggedPtr newPtr, std::memory_order, std::memory_order) {
char result;
__asm__ volatile (
"lock ;"
"cmpxchg16b %6;"
"setz %1;"
: "+m" (*this),
"=q" (result),
"+a" (oldPtr._ptr),
"+d" (oldPtr._tag)
: "b" (newPtr._ptr),
"c" (newPtr._tag)
: "cc", "memory"
);
return result;
}
void *_ptr;
size_t _tag;
} __attribute__ ((aligned (16)));
using TaggedPtr = AtomicTaggedPtr;
#else
using TaggedPtr = TaggedPtrT;
using AtomicTaggedPtr = std::atomic<TaggedPtr>;
#endif
class AFListBase
{
public:
using HeadPtr = TaggedPtr;
using AtomicHeadPtr = AtomicTaggedPtr;
AFListBase() noexcept : _next(nullptr) { }
void setNext(AFListBase * csl) noexcept { _next = csl; }
static void linkInList(AtomicHeadPtr & head, AFListBase * list) noexcept;
static void linkIn(AtomicHeadPtr & head, AFListBase * csl, AFListBase * tail) noexcept;
protected:
AFListBase * getNext() noexcept { return _next; }
static AFListBase * linkOut(AtomicHeadPtr & head) noexcept;
private:
AFListBase *_next;
};
template <typename MemBlockPtrT>
class AFList : public AFListBase
{
public:
typedef size_t CountT;
enum { NumBlocks = 126 };
AFList() noexcept : _count(0) { }
[[nodiscard]] CountT count() const noexcept { return _count; }
void add(MemBlockPtrT & ptr) noexcept {
ptr.free();
PARANOID_CHECK2( if (full()) { *(int*)0=0; });
_memBlockList[_count++] = ptr;
}
void sub(MemBlockPtrT & mem) noexcept {
if (empty()) {
return;
}
mem = _memBlockList[--_count];
}
[[nodiscard]] bool empty() const noexcept { return (_count == 0); }
[[nodiscard]] bool full() const noexcept { return (_count == NumBlocks); }
size_t fill(void * mem, SizeClassT sc, size_t blocksPerChunk = NumBlocks) noexcept;
AFList * getNext() noexcept { return static_cast<AFList *>(AFListBase::getNext()); }
static AFList * linkOut(AtomicHeadPtr & head) noexcept {
return static_cast<AFList *>(AFListBase::linkOut(head));
}
private:
CountT _count;
MemBlockPtrT _memBlockList[NumBlocks];
};
template <typename MemBlockPtrT>
size_t AFList<MemBlockPtrT>::fill(void * mem, SizeClassT sc, size_t blocksPerChunk) noexcept
{
size_t sz = MemBlockPtrT::classSize(sc);
int retval(std::max(0, int(blocksPerChunk-_count)));
char * first = (char *) mem;
for(int i=0; i < retval; i++) {
_memBlockList[_count] = MemBlockPtrT(first + i*sz, MemBlockPtrT::unAdjustSize(sz));
_memBlockList[_count].free();
_count++;
}
return retval;
}
}
|
