folly/experimental/flat_combining/test/FlatCombiningExamples.h

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   3  *
   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
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  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.
  15  */
  16
  17 #pragma once
  18
  19 #include <atomic>
  20 #include <memory>
  21 #include <mutex>
  22
  23 #include <folly/experimental/flat_combining/FlatCombining.h>
  24 #include <folly/synchronization/Baton.h>
  25
  26 namespace folly {
  27
  28 struct Line {
  29   FOLLY_ALIGN_TO_AVOID_FALSE_SHARING
  30   uint64_t val_;
  31 };
  32
  33 class Data { // Sequential data structure
  34  public:
  35   explicit Data(size_t size) : size_(size) {
  36     x_ = std::make_unique<Line[]>(size_);
  37   }
  38
  39   uint64_t getVal() {
  40     uint64_t val = x_[0].val_;
  41     for (size_t i = 1; i < size_; ++i) {
  42       assert(x_[i].val_ == val);
  43     }
  44     return val;
  45   }
  46
  47   // add
  48
  49   void add(uint64_t val) {
  50     uint64_t oldval = x_[0].val_;
  51     for (size_t i = 0; i < size_; ++i) {
  52       assert(x_[i].val_ == oldval);
  53       x_[i].val_ = oldval + val;
  54     }
  55   }
  56
  57   uint64_t fetchAdd(uint64_t val) {
  58     uint64_t res = x_[0].val_;
  59     for (size_t i = 0; i < size_; ++i) {
  60       assert(x_[i].val_ == res);
  61       x_[i].val_ += val;
  62     }
  63     return res;
  64   }
  65
  66  private:
  67   size_t size_;
  68   std::unique_ptr<Line[]> x_;
  69 };
  70
  71 // Example of FC concurrent data structure using simple interface
  72
  73 template <
  74     typename Mutex = std::mutex,
  75     template <typename> class Atom = std::atomic>
  76 class FcSimpleExample
  77     : public FlatCombining<FcSimpleExample<Mutex, Atom>, Mutex, Atom> {
  78   using FC = FlatCombining<FcSimpleExample<Mutex, Atom>, Mutex, Atom>;
  79   using Rec = typename FC::Rec;
  80
  81  public:
  82   explicit FcSimpleExample(
  83       size_t size,
  84       bool dedicated = true,
  85       uint32_t numRecs = 0,
  86       uint32_t maxOps = 0)
  87       : FC(dedicated, numRecs, maxOps), data_(size) {}
  88
  89   uint64_t getVal() {
  90     return data_.getVal();
  91   }
  92
  93   // add
  94
  95   void addNoFC(uint64_t val) {
  96     this->requestNoFC([&] { data_.add(val); });
  97   }
  98
  99   void add(uint64_t val, Rec* rec = nullptr) {
 100     auto opFn = [&, val] { // asynchronous -- capture val by value
 101       data_.add(val);
 102     };
 103     this->requestFC(opFn, rec, false);
 104   }
 105
 106   // fetchAdd
 107
 108   uint64_t fetchAddNoFC(uint64_t val) {
 109     uint64_t res;
 110     auto opFn = [&] { res = data_.fetchAdd(val); };
 111     this->requestNoFC(opFn);
 112     return res;
 113   }
 114
 115   uint64_t fetchAdd(uint64_t val, Rec* rec = nullptr) {
 116     uint64_t res;
 117     auto opFn = [&] { res = data_.fetchAdd(val); };
 118     this->requestFC(opFn, rec);
 119     return res;
 120   }
 121
 122  private:
 123   Data data_;
 124 };
 125
 126 // Example of FC data structure using custom request processing
 127
 128 class Req {
 129  public:
 130   enum class Type { ADD, FETCHADD };
 131
 132   void setType(Type type) {
 133     type_ = type;
 134   }
 135
 136   Type getType() {
 137     return type_;
 138   }
 139
 140   void setVal(uint64_t val) {
 141     val_ = val;
 142   }
 143
 144   uint64_t getVal() {
 145     return val_;
 146   }
 147
 148   void setRes(uint64_t res) {
 149     res_ = res;
 150   }
 151
 152   uint64_t getRes() {
 153     return res_;
 154   }
 155
 156  private:
 157   Type type_;
 158   uint64_t val_;
 159   uint64_t res_;
 160 };
 161
 162 template <
 163     typename Req,
 164     typename Mutex = std::mutex,
 165     template <typename> class Atom = std::atomic>
 166 class FcCustomExample : public FlatCombining<
 167                             FcCustomExample<Req, Mutex, Atom>,
 168                             Mutex,
 169                             Atom,
 170                             Req> {
 171   using FC = FlatCombining<FcCustomExample<Req, Mutex, Atom>, Mutex, Atom, Req>;
 172   using Rec = typename FC::Rec;
 173
 174  public:
 175   explicit FcCustomExample(
 176       int size,
 177       bool dedicated = true,
 178       uint32_t numRecs = 0,
 179       uint32_t maxOps = 0)
 180       : FC(dedicated, numRecs, maxOps), data_(size) {}
 181
 182   uint64_t getVal() {
 183     return data_.getVal();
 184   }
 185
 186   // add
 187
 188   void addNoFC(uint64_t val) {
 189     this->requestNoFC([&] { data_.add(val); });
 190   }
 191
 192   void add(uint64_t val, Rec* rec = nullptr) {
 193     auto opFn = [&, val] { data_.add(val); };
 194     auto fillFn = [&](Req& req) {
 195       req.setType(Req::Type::ADD);
 196       req.setVal(val);
 197     };
 198     this->requestFC(opFn, fillFn, rec, false); // asynchronous
 199   }
 200
 201   // fetchAdd
 202
 203   uint64_t fetchAddNoFC(uint64_t val) {
 204     uint64_t res;
 205     auto opFn = [&] { res = data_.fetchAdd(val); };
 206     this->requestNoFC(opFn);
 207     return res;
 208   }
 209
 210   uint64_t fetchAdd(uint64_t val, Rec* rec = nullptr) {
 211     uint64_t res;
 212     auto opFn = [&] { res = data_.fetchAdd(val); };
 213     auto fillFn = [&](Req& req) {
 214       req.setType(Req::Type::FETCHADD);
 215       req.setVal(val);
 216     };
 217     auto resFn = [&](Req& req) { res = req.getRes(); };
 218     this->requestFC(opFn, fillFn, resFn, rec);
 219     return res;
 220   }
 221
 222   // custom combined op processing - overrides FlatCombining::combinedOp(Req&)
 223   void combinedOp(Req& req) {
 224     switch (req.getType()) {
 225       case Req::Type::ADD: {
 226         data_.add(req.getVal());
 227       } break;
 228       case Req::Type::FETCHADD: {
 229         req.setRes(data_.fetchAdd(req.getVal()));
 230       } break;
 231       default: { assert(false); }
 232     }
 233   }
 234
 235  private:
 236   Data data_;
 237 };
 238
 239 } // namespace folly