ceph/src/rgw/rgw_period_history.cc

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3
   4 #include "rgw_period_history.h"
   5 #include "rgw_rados.h"
   6
   7 #include "include/assert.h"
   8
   9 #define dout_subsys ceph_subsys_rgw
  10
  11 #undef dout_prefix
  12 #define dout_prefix (*_dout << "rgw period history: ")
  13
  14 /// an ordered history of consecutive periods
  15 class RGWPeriodHistory::History : public bi::avl_set_base_hook<> {
  16  public:
  17   std::deque<RGWPeriod> periods;
  18
  19   epoch_t get_oldest_epoch() const {
  20     return periods.front().get_realm_epoch();
  21   }
  22   epoch_t get_newest_epoch() const {
  23     return periods.back().get_realm_epoch();
  24   }
  25   bool contains(epoch_t epoch) const {
  26     return get_oldest_epoch() <= epoch && epoch <= get_newest_epoch();
  27   }
  28   RGWPeriod& get(epoch_t epoch) {
  29     return periods[epoch - get_oldest_epoch()];
  30   }
  31   const RGWPeriod& get(epoch_t epoch) const {
  32     return periods[epoch - get_oldest_epoch()];
  33   }
  34   const std::string& get_predecessor_id() const {
  35     return periods.front().get_predecessor();
  36   }
  37 };
  38
  39 /// value comparison for avl_set
  40 bool operator<(const RGWPeriodHistory::History& lhs,
  41                const RGWPeriodHistory::History& rhs)
  42 {
  43   return lhs.get_newest_epoch() < rhs.get_newest_epoch();
  44 }
  45
  46 /// key-value comparison for avl_set
  47 struct NewestEpochLess {
  48   bool operator()(const RGWPeriodHistory::History& value, epoch_t key) const {
  49     return value.get_newest_epoch() < key;
  50   }
  51 };
  52
  53
  54 using Cursor = RGWPeriodHistory::Cursor;
  55
  56 const RGWPeriod& Cursor::get_period() const
  57 {
  58   std::lock_guard<std::mutex> lock(*mutex);
  59   return history->get(epoch);
  60 }
  61 bool Cursor::has_prev() const
  62 {
  63   std::lock_guard<std::mutex> lock(*mutex);
  64   return epoch > history->get_oldest_epoch();
  65 }
  66 bool Cursor::has_next() const
  67 {
  68   std::lock_guard<std::mutex> lock(*mutex);
  69   return epoch < history->get_newest_epoch();
  70 }
  71
  72 bool operator==(const Cursor& lhs, const Cursor& rhs)
  73 {
  74   return lhs.history == rhs.history && lhs.epoch == rhs.epoch;
  75 }
  76
  77 bool operator!=(const Cursor& lhs, const Cursor& rhs)
  78 {
  79   return !(lhs == rhs);
  80 }
  81
  82 class RGWPeriodHistory::Impl final {
  83  public:
  84   Impl(CephContext* cct, Puller* puller, const RGWPeriod& current_period);
  85   ~Impl();
  86
  87   Cursor get_current() const { return current_cursor; }
  88   Cursor attach(RGWPeriod&& period);
  89   Cursor insert(RGWPeriod&& period);
  90   Cursor lookup(epoch_t realm_epoch);
  91
  92  private:
  93   /// an intrusive set of histories, ordered by their newest epoch. although
  94   /// the newest epoch of each history is mutable, the ordering cannot change
  95   /// because we prevent the histories from overlapping
  96   using Set = bi::avl_set<RGWPeriodHistory::History>;
  97
  98   /// insert the given period into the period history, creating new unconnected
  99   /// histories or merging existing histories as necessary. expects the caller
 100   /// to hold a lock on mutex. returns a valid cursor regardless of whether it
 101   /// ends up in current_history, though cursors in other histories are only
 102   /// valid within the context of the lock
 103   Cursor insert_locked(RGWPeriod&& period);
 104
 105   /// merge the periods from the src history onto the end of the dst history,
 106   /// and return an iterator to the merged history
 107   Set::iterator merge(Set::iterator dst, Set::iterator src);
 108
 109   /// construct a Cursor object using Cursor's private constuctor
 110   Cursor make_cursor(Set::const_iterator history, epoch_t epoch);
 111
 112   CephContext *const cct;
 113   Puller *const puller; //< interface for pulling missing periods
 114   Cursor current_cursor; //< Cursor to realm's current period
 115
 116   mutable std::mutex mutex; //< protects the histories
 117
 118   /// set of disjoint histories that are missing intermediate periods needed to
 119   /// connect them together
 120   Set histories;
 121
 122   /// iterator to the history that contains the realm's current period
 123   Set::const_iterator current_history;
 124 };
 125
 126 RGWPeriodHistory::Impl::Impl(CephContext* cct, Puller* puller,
 127                              const RGWPeriod& current_period)
 128   : cct(cct), puller(puller)
 129 {
 130   if (!current_period.get_id().empty()) {
 131     // copy the current period into a new history
 132     auto history = new History;
 133     history->periods.push_back(current_period);
 134
 135     // insert as our current history
 136     current_history = histories.insert(*history).first;
 137
 138     // get a cursor to the current period
 139     current_cursor = make_cursor(current_history, current_period.get_realm_epoch());
 140   }
 141 }
 142
 143 RGWPeriodHistory::Impl::~Impl()
 144 {
 145   // clear the histories and delete each entry
 146   histories.clear_and_dispose(std::default_delete<History>{});
 147 }
 148
 149 Cursor RGWPeriodHistory::Impl::attach(RGWPeriod&& period)
 150 {
 151   if (current_history == histories.end()) {
 152     return Cursor{-EINVAL};
 153   }
 154
 155   const auto epoch = period.get_realm_epoch();
 156
 157   std::string predecessor_id;
 158   for (;;) {
 159     {
 160       // hold the lock over insert, and while accessing the unsafe cursor
 161       std::lock_guard<std::mutex> lock(mutex);
 162
 163       auto cursor = insert_locked(std::move(period));
 164       if (!cursor) {
 165         return cursor;
 166       }
 167       if (current_history->contains(epoch)) {
 168         break; // the history is complete
 169       }
 170
 171       // take the predecessor id of the most recent history
 172       if (cursor.get_epoch() > current_cursor.get_epoch()) {
 173         predecessor_id = cursor.history->get_predecessor_id();
 174       } else {
 175         predecessor_id = current_history->get_predecessor_id();
 176       }
 177     }
 178
 179     if (predecessor_id.empty()) {
 180       lderr(cct) << "reached a period with an empty predecessor id" << dendl;
 181       return Cursor{-EINVAL};
 182     }
 183
 184     // pull the period outside of the lock
 185     int r = puller->pull(predecessor_id, period);
 186     if (r < 0) {
 187       return Cursor{r};
 188     }
 189   }
 190
 191   // return a cursor to the requested period
 192   return make_cursor(current_history, epoch);
 193 }
 194
 195 Cursor RGWPeriodHistory::Impl::insert(RGWPeriod&& period)
 196 {
 197   if (current_history == histories.end()) {
 198     return Cursor{-EINVAL};
 199   }
 200
 201   std::lock_guard<std::mutex> lock(mutex);
 202
 203   auto cursor = insert_locked(std::move(period));
 204
 205   if (cursor.get_error()) {
 206     return cursor;
 207   }
 208   // we can only provide cursors that are safe to use outside of the mutex if
 209   // they're within the current_history, because other histories can disappear
 210   // in a merge. see merge() for the special handling of current_history
 211   if (cursor.history == &*current_history) {
 212     return cursor;
 213   }
 214   return Cursor{};
 215 }
 216
 217 Cursor RGWPeriodHistory::Impl::lookup(epoch_t realm_epoch)
 218 {
 219   if (current_history != histories.end() &&
 220       current_history->contains(realm_epoch)) {
 221     return make_cursor(current_history, realm_epoch);
 222   }
 223   return Cursor{};
 224 }
 225
 226 Cursor RGWPeriodHistory::Impl::insert_locked(RGWPeriod&& period)
 227 {
 228   auto epoch = period.get_realm_epoch();
 229
 230   // find the first history whose newest epoch comes at or after this period
 231   auto i = histories.lower_bound(epoch, NewestEpochLess{});
 232
 233   if (i == histories.end()) {
 234     // epoch is past the end of our newest history
 235     auto last = --Set::iterator{i}; // last = i - 1
 236
 237     if (epoch == last->get_newest_epoch() + 1) {
 238       // insert at the back of the last history
 239       last->periods.emplace_back(std::move(period));
 240       return make_cursor(last, epoch);
 241     }
 242
 243     // create a new history for this period
 244     auto history = new History;
 245     history->periods.emplace_back(std::move(period));
 246     histories.insert(last, *history);
 247
 248     i = Set::s_iterator_to(*history);
 249     return make_cursor(i, epoch);
 250   }
 251
 252   if (i->contains(epoch)) {
 253     // already resident in this history
 254     auto& existing = i->get(epoch);
 255     // verify that the period ids match; otherwise we've forked the history
 256     if (period.get_id() != existing.get_id()) {
 257       lderr(cct) << "Got two different periods, " << period.get_id()
 258           << " and " << existing.get_id() << ", with the same realm epoch "
 259           << epoch << "! This indicates a fork in the period history." << dendl;
 260       return Cursor{-EEXIST};
 261     }
 262     // update the existing period if we got a newer period epoch
 263     if (period.get_epoch() > existing.get_epoch()) {
 264       existing = std::move(period);
 265     }
 266     return make_cursor(i, epoch);
 267   }
 268
 269   if (epoch + 1 == i->get_oldest_epoch()) {
 270     // insert at the front of this history
 271     i->periods.emplace_front(std::move(period));
 272
 273     // try to merge with the previous history
 274     if (i != histories.begin()) {
 275       auto prev = --Set::iterator{i};
 276       if (epoch == prev->get_newest_epoch() + 1) {
 277         i = merge(prev, i);
 278       }
 279     }
 280     return make_cursor(i, epoch);
 281   }
 282
 283   if (i != histories.begin()) {
 284     auto prev = --Set::iterator{i};
 285     if (epoch == prev->get_newest_epoch() + 1) {
 286       // insert at the back of the previous history
 287       prev->periods.emplace_back(std::move(period));
 288       return make_cursor(prev, epoch);
 289     }
 290   }
 291
 292   // create a new history for this period
 293   auto history = new History;
 294   history->periods.emplace_back(std::move(period));
 295   histories.insert(i, *history);
 296
 297   i = Set::s_iterator_to(*history);
 298   return make_cursor(i, epoch);
 299 }
 300
 301 RGWPeriodHistory::Impl::Set::iterator
 302 RGWPeriodHistory::Impl::merge(Set::iterator dst, Set::iterator src)
 303 {
 304   assert(dst->get_newest_epoch() + 1 == src->get_oldest_epoch());
 305
 306   // always merge into current_history
 307   if (src == current_history) {
 308     // move the periods from dst onto the front of src
 309     src->periods.insert(src->periods.begin(),
 310                         std::make_move_iterator(dst->periods.begin()),
 311                         std::make_move_iterator(dst->periods.end()));
 312     histories.erase_and_dispose(dst, std::default_delete<History>{});
 313     return src;
 314   }
 315
 316   // move the periods from src onto the end of dst
 317   dst->periods.insert(dst->periods.end(),
 318                       std::make_move_iterator(src->periods.begin()),
 319                       std::make_move_iterator(src->periods.end()));
 320   histories.erase_and_dispose(src, std::default_delete<History>{});
 321   return dst;
 322 }
 323
 324 Cursor RGWPeriodHistory::Impl::make_cursor(Set::const_iterator history,
 325                                            epoch_t epoch) {
 326   return Cursor{&*history, &mutex, epoch};
 327 }
 328
 329
 330 RGWPeriodHistory::RGWPeriodHistory(CephContext* cct, Puller* puller,
 331                                    const RGWPeriod& current_period)
 332   : impl(new Impl(cct, puller, current_period)) {}
 333
 334 RGWPeriodHistory::~RGWPeriodHistory() = default;
 335
 336 Cursor RGWPeriodHistory::get_current() const
 337 {
 338   return impl->get_current();
 339 }
 340 Cursor RGWPeriodHistory::attach(RGWPeriod&& period)
 341 {
 342   return impl->attach(std::move(period));
 343 }
 344 Cursor RGWPeriodHistory::insert(RGWPeriod&& period)
 345 {
 346   return impl->insert(std::move(period));
 347 }
 348 Cursor RGWPeriodHistory::lookup(epoch_t realm_epoch)
 349 {
 350   return impl->lookup(realm_epoch);
 351 }