]>
Commit | Line | Data |
---|---|---|
9f95a23c TL |
1 | // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- |
2 | // vim: ts=8 sw=2 smarttab | |
3 | // | |
4 | // Ceph - scalable distributed file system | |
5 | // | |
6 | // Copyright (C) 2018 Red Hat, Inc. | |
7 | // | |
8 | // This is free software; you can redistribute it and/or | |
9 | // modify it under the terms of the GNU Lesser General Public | |
10 | // License version 2.1, as published by the Free Software | |
11 | // Foundation. See file COPYING. | |
12 | // | |
13 | ||
14 | #ifndef CEPH_COMMON_CONTAINERS_H | |
15 | #define CEPH_COMMON_CONTAINERS_H | |
16 | ||
17 | #include <cstdint> | |
18 | #include <type_traits> | |
19 | ||
20 | namespace ceph::containers { | |
21 | ||
22 | // tiny_vector – CPU friendly, small_vector-like container for mutexes, | |
23 | // atomics and other non-movable things. | |
24 | // | |
25 | // The purpose of the container is to store arbitrary number of objects | |
26 | // with absolutely minimal requirements regarding constructibility | |
27 | // and assignability while minimizing memory indirection. | |
28 | // There is no obligation for MoveConstructibility, CopyConstructibility, | |
29 | // MoveAssignability, CopyAssignability nor even DefaultConstructibility | |
30 | // which allows to handle std::mutexes, std::atomics or any type embedding | |
31 | // them. | |
32 | // | |
33 | // Few requirements translate into tiny interface. The container isn't | |
34 | // Copy- nor MoveConstructible. Although it does offer random access | |
35 | // iterator, insertion in the middle is not allowed. The maximum number | |
36 | // of elements must be known at run-time. This shouldn't be an issue in | |
37 | // the intended use case: sharding. | |
38 | // | |
39 | // For the special case of no internal slots (InternalCapacity eq 0), | |
40 | // tiny_vector doesn't require moving any elements (changing pointers | |
41 | // is enough), and thus should be MoveConstructibile. | |
42 | // | |
43 | // Alternatives: | |
44 | // 1. std::vector<boost::optional<ValueT>> initialized with the known | |
45 | // size and emplace_backed(). boost::optional inside provides | |
46 | // the DefaultConstructibility. Imposes extra memory indirection. | |
47 | // 2. boost::container::small_vector + boost::optional always | |
48 | // requires MoveConstructibility. | |
49 | // 3. boost::container::static_vector feed via emplace_back(). | |
50 | // Good for performance but enforces upper limit on elements count. | |
51 | // For sharding this means we can't handle arbitrary number of | |
52 | // shards (weird configs). | |
53 | // 4. std::unique_ptr<ValueT>: extra indirection together with memory | |
54 | // fragmentation. | |
55 | ||
56 | template<typename Value, std::size_t InternalCapacity = 0> | |
57 | class tiny_vector { | |
58 | // NOTE: to avoid false sharing consider aligning to cache line | |
59 | using storage_unit_t = \ | |
60 | std::aligned_storage_t<sizeof(Value), alignof(Value)>; | |
61 | ||
62 | std::size_t _size = 0; | |
63 | storage_unit_t* const data = nullptr; | |
64 | storage_unit_t internal[InternalCapacity]; | |
65 | ||
66 | public: | |
67 | typedef std::size_t size_type; | |
68 | typedef std::add_lvalue_reference_t<Value> reference; | |
69 | typedef std::add_const_t<reference> const_reference; | |
70 | typedef std::add_pointer_t<Value> pointer; | |
71 | ||
72 | // emplacer is the piece of weirdness that comes from handling | |
73 | // unmovable-and-uncopyable things. The only way to instantiate | |
74 | // such types I know is to create instances in-place perfectly | |
75 | // forwarding necessary data to constructor. | |
76 | // Abstracting that is the exact purpose of emplacer. | |
77 | // | |
78 | // The usage scenario is: | |
79 | // 1. The tiny_vector's ctor is provided with a) maximum number | |
80 | // of instances and b) a callable taking emplacer. | |
81 | // 2. The callable can (but isn't obliged to!) use emplacer to | |
82 | // construct an instance without knowing at which address | |
83 | // in memory it will be put. Callable is also supplied with | |
84 | // an unique integer from the range <0, maximum number of | |
85 | // instances). | |
86 | // 3. If callable decides to instantiate, it calls ::emplace | |
87 | // of emplacer passing all arguments required by the type | |
88 | // hold in tiny_vector. | |
89 | // | |
90 | // Example: | |
91 | // ``` | |
92 | // static constexpr const num_internally_allocated_slots = 32; | |
93 | // tiny_vector<T, num_internally_allocated_slots> mytinyvec { | |
94 | // num_of_instances, | |
95 | // [](const size_t i, auto emplacer) { | |
96 | // emplacer.emplace(argument_for_T_ctor); | |
97 | // } | |
98 | // } | |
99 | // ``` | |
100 | // | |
101 | // For the sake of supporting the ceph::make_mutex() family of | |
102 | // factories, which relies on C++17's guaranteed copy elision, | |
103 | // the emplacer provides `data()` to retrieve the location for | |
104 | // constructing the instance with placement-new. This is handy | |
105 | // as the `emplace()` depends on perfect forwarding, and thus | |
106 | // interfere with the elision for cases like: | |
107 | // ``` | |
108 | // emplacer.emplace(ceph::make_mutex("mtx-name")); | |
109 | // ``` | |
110 | // See: https://stackoverflow.com/a/52498826 | |
111 | ||
112 | class emplacer { | |
113 | friend class tiny_vector; | |
114 | ||
115 | tiny_vector* parent; | |
116 | emplacer(tiny_vector* const parent) | |
117 | : parent(parent) { | |
118 | } | |
119 | ||
120 | public: | |
121 | void* data() { | |
122 | void* const ret = &parent->data[parent->_size++]; | |
123 | parent = nullptr; | |
124 | return ret; | |
125 | } | |
126 | ||
127 | template<class... Args> | |
128 | void emplace(Args&&... args) { | |
129 | if (parent) { | |
130 | new (data()) Value(std::forward<Args>(args)...); | |
131 | } | |
132 | } | |
133 | }; | |
134 | ||
135 | template<typename F> | |
136 | tiny_vector(const std::size_t count, F&& f) | |
137 | : data(count <= InternalCapacity ? internal | |
138 | : new storage_unit_t[count]) { | |
139 | for (std::size_t i = 0; i < count; ++i) { | |
140 | // caller MAY emplace up to `count` elements but it IS NOT | |
141 | // obliged to do so. The emplacer guarantees that the limit | |
142 | // will never be exceeded. | |
143 | f(i, emplacer(this)); | |
144 | } | |
145 | } | |
146 | ||
147 | ~tiny_vector() { | |
148 | for (auto& elem : *this) { | |
149 | elem.~Value(); | |
150 | } | |
151 | ||
152 | const auto data_addr = reinterpret_cast<std::uintptr_t>(data); | |
153 | const auto this_addr = reinterpret_cast<std::uintptr_t>(this); | |
154 | if (data_addr < this_addr || | |
155 | data_addr >= this_addr + sizeof(*this)) { | |
156 | delete[] data; | |
157 | } | |
158 | } | |
159 | ||
160 | reference operator[](size_type pos) { | |
161 | return reinterpret_cast<reference>(data[pos]); | |
162 | } | |
163 | const_reference operator[](size_type pos) const { | |
164 | return reinterpret_cast<const_reference>(data[pos]); | |
165 | } | |
166 | ||
167 | size_type size() const { | |
168 | return _size; | |
169 | } | |
170 | ||
171 | pointer begin() { | |
172 | return reinterpret_cast<pointer>(&data[0]); | |
173 | } | |
174 | pointer end() { | |
175 | return reinterpret_cast<pointer>(&data[_size]); | |
176 | } | |
177 | ||
178 | const pointer begin() const { | |
179 | return reinterpret_cast<pointer>(&data[0]); | |
180 | } | |
181 | const pointer end() const { | |
182 | return reinterpret_cast<pointer>(&data[_size]); | |
183 | } | |
184 | ||
185 | const pointer cbegin() const { | |
186 | return reinterpret_cast<pointer>(&data[0]); | |
187 | } | |
188 | const pointer cend() const { | |
189 | return reinterpret_cast<pointer>(&data[_size]); | |
190 | } | |
191 | }; | |
192 | ||
193 | } // namespace ceph::containers | |
194 | ||
195 | #endif // CEPH_COMMON_CONTAINERS_H |