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