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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
|
// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
// vim: ts=8 sw=2 smarttab
//
// Ceph - scalable distributed file system
//
// Copyright (C) 2018 Red Hat, Inc.
//
// This is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License version 2.1, as published by the Free Software
// Foundation. See file COPYING.
//
#ifndef CEPH_COMMON_CONTAINERS_H
#define CEPH_COMMON_CONTAINERS_H
#include <cstdint>
#include <type_traits>
namespace ceph::containers {
// tiny_vector – CPU friendly, small_vector-like container for mutexes,
// atomics and other non-movable things.
//
// The purpose of the container is to store arbitrary number of objects
// with absolutely minimal requirements regarding constructibility
// and assignability while minimizing memory indirection.
// There is no obligation for MoveConstructibility, CopyConstructibility,
// MoveAssignability, CopyAssignability nor even DefaultConstructibility
// which allows to handle std::mutexes, std::atomics or any type embedding
// them.
//
// Few requirements translate into tiny interface. The container isn't
// Copy- nor MoveConstructible. Although it does offer random access
// iterator, insertion in the middle is not allowed. The maximum number
// of elements must be known at run-time. This shouldn't be an issue in
// the intended use case: sharding.
//
// For the special case of no internal slots (InternalCapacity eq 0),
// tiny_vector doesn't require moving any elements (changing pointers
// is enough), and thus should be MoveConstructibile.
//
// Alternatives:
// 1. std::vector<boost::optional<ValueT>> initialized with the known
// size and emplace_backed(). boost::optional inside provides
// the DefaultConstructibility. Imposes extra memory indirection.
// 2. boost::container::small_vector + boost::optional always
// requires MoveConstructibility.
// 3. boost::container::static_vector feed via emplace_back().
// Good for performance but enforces upper limit on elements count.
// For sharding this means we can't handle arbitrary number of
// shards (weird configs).
// 4. std::unique_ptr<ValueT>: extra indirection together with memory
// fragmentation.
template<typename Value, std::size_t InternalCapacity = 0>
class tiny_vector {
// NOTE: to avoid false sharing consider aligning to cache line
using storage_unit_t = \
std::aligned_storage_t<sizeof(Value), alignof(Value)>;
std::size_t _size = 0;
storage_unit_t* const data = nullptr;
storage_unit_t internal[InternalCapacity];
public:
typedef std::size_t size_type;
typedef std::add_lvalue_reference_t<Value> reference;
typedef std::add_const_t<reference> const_reference;
typedef std::add_pointer_t<Value> pointer;
// emplacer is the piece of weirdness that comes from handling
// unmovable-and-uncopyable things. The only way to instantiate
// such types I know is to create instances in-place perfectly
// forwarding necessary data to constructor.
// Abstracting that is the exact purpose of emplacer.
//
// The usage scenario is:
// 1. The tiny_vector's ctor is provided with a) maximum number
// of instances and b) a callable taking emplacer.
// 2. The callable can (but isn't obliged to!) use emplacer to
// construct an instance without knowing at which address
// in memory it will be put. Callable is also supplied with
// an unique integer from the range <0, maximum number of
// instances).
// 3. If callable decides to instantiate, it calls ::emplace
// of emplacer passing all arguments required by the type
// hold in tiny_vector.
//
// Example:
// ```
// static constexpr const num_internally_allocated_slots = 32;
// tiny_vector<T, num_internally_allocated_slots> mytinyvec {
// num_of_instances,
// [](const size_t i, auto emplacer) {
// emplacer.emplace(argument_for_T_ctor);
// }
// }
// ```
//
// For the sake of supporting the ceph::make_mutex() family of
// factories, which relies on C++17's guaranteed copy elision,
// the emplacer provides `data()` to retrieve the location for
// constructing the instance with placement-new. This is handy
// as the `emplace()` depends on perfect forwarding, and thus
// interfere with the elision for cases like:
// ```
// emplacer.emplace(ceph::make_mutex("mtx-name"));
// ```
// See: https://stackoverflow.com/a/52498826
class emplacer {
friend class tiny_vector;
tiny_vector* parent;
emplacer(tiny_vector* const parent)
: parent(parent) {
}
public:
void* data() {
void* const ret = &parent->data[parent->_size++];
parent = nullptr;
return ret;
}
template<class... Args>
void emplace(Args&&... args) {
if (parent) {
new (data()) Value(std::forward<Args>(args)...);
}
}
};
template<typename F>
tiny_vector(const std::size_t count, F&& f)
: data(count <= InternalCapacity ? internal
: new storage_unit_t[count]) {
for (std::size_t i = 0; i < count; ++i) {
// caller MAY emplace up to `count` elements but it IS NOT
// obliged to do so. The emplacer guarantees that the limit
// will never be exceeded.
f(i, emplacer(this));
}
}
~tiny_vector() {
for (auto& elem : *this) {
elem.~Value();
}
const auto data_addr = reinterpret_cast<std::uintptr_t>(data);
const auto this_addr = reinterpret_cast<std::uintptr_t>(this);
if (data_addr < this_addr ||
data_addr >= this_addr + sizeof(*this)) {
delete[] data;
}
}
reference operator[](size_type pos) {
return reinterpret_cast<reference>(data[pos]);
}
const_reference operator[](size_type pos) const {
return reinterpret_cast<const_reference>(data[pos]);
}
size_type size() const {
return _size;
}
pointer begin() {
return reinterpret_cast<pointer>(&data[0]);
}
pointer end() {
return reinterpret_cast<pointer>(&data[_size]);
}
const pointer begin() const {
return reinterpret_cast<pointer>(&data[0]);
}
const pointer end() const {
return reinterpret_cast<pointer>(&data[_size]);
}
const pointer cbegin() const {
return reinterpret_cast<pointer>(&data[0]);
}
const pointer cend() const {
return reinterpret_cast<pointer>(&data[_size]);
}
};
} // namespace ceph::containers
#endif // CEPH_COMMON_CONTAINERS_H
|
