2 * Copyright 2017-present Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
23 #include <folly/experimental/flat_combining/FlatCombining.h>
24 #include <folly/synchronization/Baton.h>
28 struct alignas(hardware_destructive_interference_size) Line {
32 class Data { // Sequential data structure
34 explicit Data(size_t size) : size_(size) {
35 x_ = std::make_unique<Line[]>(size_);
39 uint64_t val = x_[0].val_;
40 for (size_t i = 1; i < size_; ++i) {
41 assert(x_[i].val_ == val);
48 void add(uint64_t val) {
49 uint64_t oldval = x_[0].val_;
50 for (size_t i = 0; i < size_; ++i) {
51 assert(x_[i].val_ == oldval);
52 x_[i].val_ = oldval + val;
56 uint64_t fetchAdd(uint64_t val) {
57 uint64_t res = x_[0].val_;
58 for (size_t i = 0; i < size_; ++i) {
59 assert(x_[i].val_ == res);
67 std::unique_ptr<Line[]> x_;
70 // Example of FC concurrent data structure using simple interface
73 typename Mutex = std::mutex,
74 template <typename> class Atom = std::atomic>
76 : public FlatCombining<FcSimpleExample<Mutex, Atom>, Mutex, Atom> {
77 using FC = FlatCombining<FcSimpleExample<Mutex, Atom>, Mutex, Atom>;
78 using Rec = typename FC::Rec;
81 explicit FcSimpleExample(
83 bool dedicated = true,
86 : FC(dedicated, numRecs, maxOps), data_(size) {}
89 return data_.getVal();
94 void addNoFC(uint64_t val) {
95 this->requestNoFC([&] { data_.add(val); });
98 void add(uint64_t val, Rec* rec = nullptr) {
99 auto opFn = [&, val] { // asynchronous -- capture val by value
102 this->requestFC(opFn, rec, false);
107 uint64_t fetchAddNoFC(uint64_t val) {
109 auto opFn = [&] { res = data_.fetchAdd(val); };
110 this->requestNoFC(opFn);
114 uint64_t fetchAdd(uint64_t val, Rec* rec = nullptr) {
116 auto opFn = [&] { res = data_.fetchAdd(val); };
117 this->requestFC(opFn, rec);
125 // Example of FC data structure using custom request processing
129 enum class Type { ADD, FETCHADD };
131 void setType(Type type) {
139 void setVal(uint64_t val) {
147 void setRes(uint64_t res) {
163 typename Mutex = std::mutex,
164 template <typename> class Atom = std::atomic>
165 class FcCustomExample : public FlatCombining<
166 FcCustomExample<Req, Mutex, Atom>,
170 using FC = FlatCombining<FcCustomExample<Req, Mutex, Atom>, Mutex, Atom, Req>;
171 using Rec = typename FC::Rec;
174 explicit FcCustomExample(
176 bool dedicated = true,
177 uint32_t numRecs = 0,
179 : FC(dedicated, numRecs, maxOps), data_(size) {}
182 return data_.getVal();
187 void addNoFC(uint64_t val) {
188 this->requestNoFC([&] { data_.add(val); });
191 void add(uint64_t val, Rec* rec = nullptr) {
192 auto opFn = [&, val] { data_.add(val); };
193 auto fillFn = [&](Req& req) {
194 req.setType(Req::Type::ADD);
197 this->requestFC(opFn, fillFn, rec, false); // asynchronous
202 uint64_t fetchAddNoFC(uint64_t val) {
204 auto opFn = [&] { res = data_.fetchAdd(val); };
205 this->requestNoFC(opFn);
209 uint64_t fetchAdd(uint64_t val, Rec* rec = nullptr) {
211 auto opFn = [&] { res = data_.fetchAdd(val); };
212 auto fillFn = [&](Req& req) {
213 req.setType(Req::Type::FETCHADD);
216 auto resFn = [&](Req& req) { res = req.getRes(); };
217 this->requestFC(opFn, fillFn, resFn, rec);
221 // custom combined op processing - overrides FlatCombining::combinedOp(Req&)
222 void combinedOp(Req& req) {
223 switch (req.getType()) {
224 case Req::Type::ADD: {
225 data_.add(req.getVal());
227 case Req::Type::FETCHADD: {
228 req.setRes(data_.fetchAdd(req.getVal()));
230 default: { assert(false); }