ceph/src/librbd/cache/pwl/LogMap.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 "LogMap.h"
   5 #include "include/ceph_assert.h"
   6 #include "librbd/Utils.h"
   7 #include "librbd/cache/pwl/LogEntry.h"
   8
   9 namespace librbd {
  10 namespace cache {
  11 namespace pwl {
  12
  13 #define dout_subsys ceph_subsys_rbd_pwl
  14 #undef dout_prefix
  15 #define dout_prefix *_dout << "librbd::cache::pwl::LogMap: " << this << " " \
  16                            <<  __func__ << ": "
  17 template <typename T>
  18 std::ostream &operator<<(std::ostream &os,
  19                          LogMapEntry<T> &e) {
  20   os << "block_extent=" << e.block_extent << ", "
  21      << "log_entry=[" << e.log_entry << "]";
  22   return os;
  23 }
  24
  25 template <typename T>
  26 LogMapEntry<T>::LogMapEntry(const BlockExtent block_extent,
  27                             std::shared_ptr<T> log_entry)
  28   : block_extent(block_extent) , log_entry(log_entry) {
  29 }
  30
  31 template <typename T>
  32 LogMapEntry<T>::LogMapEntry(std::shared_ptr<T> log_entry)
  33   : block_extent(log_entry->block_extent()) , log_entry(log_entry) {
  34 }
  35
  36 template <typename T>
  37 LogMap<T>::LogMap(CephContext *cct)
  38   : m_cct(cct),
  39     m_lock(ceph::make_mutex(pwl::unique_lock_name(
  40            "librbd::cache::pwl::LogMap::m_lock", this))) {
  41 }
  42
  43 /**
  44  * Add a write log entry to the map. Subsequent queries for blocks
  45  * within this log entry's extent will find this log entry. Portions
  46  * of prior write log entries overlapping with this log entry will
  47  * be replaced in the map by this log entry.
  48  *
  49  * The map_entries field of the log entry object will be updated to
  50  * contain this map entry.
  51  *
  52  * The map_entries fields of all log entries overlapping with this
  53  * entry will be updated to remove the regions that overlap with
  54  * this.
  55  */
  56 template <typename T>
  57 void LogMap<T>::add_log_entry(std::shared_ptr<T> log_entry) {
  58   std::lock_guard locker(m_lock);
  59   add_log_entry_locked(log_entry);
  60 }
  61
  62 template <typename T>
  63 void LogMap<T>::add_log_entries(std::list<std::shared_ptr<T>> &log_entries) {
  64   std::lock_guard locker(m_lock);
  65   ldout(m_cct, 20) << dendl;
  66   for (auto &log_entry : log_entries) {
  67     add_log_entry_locked(log_entry);
  68   }
  69 }
  70
  71 /**
  72  * Remove any map entries that refer to the supplied write log
  73  * entry.
  74  */
  75 template <typename T>
  76 void LogMap<T>::remove_log_entry(std::shared_ptr<T> log_entry) {
  77   std::lock_guard locker(m_lock);
  78   remove_log_entry_locked(log_entry);
  79 }
  80
  81 template <typename T>
  82 void LogMap<T>::remove_log_entries(std::list<std::shared_ptr<T>> &log_entries) {
  83   std::lock_guard locker(m_lock);
  84   ldout(m_cct, 20) << dendl;
  85   for (auto &log_entry : log_entries) {
  86     remove_log_entry_locked(log_entry);
  87   }
  88 }
  89
  90 /**
  91  * Returns the list of all write log entries that overlap the specified block
  92  * extent. This doesn't tell you which portions of these entries overlap the
  93  * extent, or each other. For that, use find_map_entries(). A log entry may
  94  * appear in the list more than once, if multiple map entries refer to it
  95  * (e.g. the middle of that write log entry has been overwritten).
  96  */
  97 template <typename T>
  98 std::list<std::shared_ptr<T>> LogMap<T>::find_log_entries(BlockExtent block_extent) {
  99   std::lock_guard locker(m_lock);
 100   ldout(m_cct, 20) << dendl;
 101   return find_log_entries_locked(block_extent);
 102 }
 103
 104 /**
 105  * Returns the list of all write log map entries that overlap the
 106  * specified block extent.
 107  */
 108 template <typename T>
 109 LogMapEntries<T> LogMap<T>::find_map_entries(BlockExtent block_extent) {
 110   std::lock_guard locker(m_lock);
 111   ldout(m_cct, 20) << dendl;
 112   return find_map_entries_locked(block_extent);
 113 }
 114
 115 template <typename T>
 116 void LogMap<T>::add_log_entry_locked(std::shared_ptr<T> log_entry) {
 117   LogMapEntry<T> map_entry(log_entry);
 118   ldout(m_cct, 20) << "block_extent=" << map_entry.block_extent
 119                    << dendl;
 120   ceph_assert(ceph_mutex_is_locked_by_me(m_lock));
 121   LogMapEntries<T> overlap_entries = find_map_entries_locked(map_entry.block_extent);
 122   for (auto &entry : overlap_entries) {
 123     ldout(m_cct, 20) << entry << dendl;
 124     if (map_entry.block_extent.block_start <= entry.block_extent.block_start) {
 125       if (map_entry.block_extent.block_end >= entry.block_extent.block_end) {
 126         ldout(m_cct, 20) << "map entry completely occluded by new log entry" << dendl;
 127         remove_map_entry_locked(entry);
 128       } else {
 129         ceph_assert(map_entry.block_extent.block_end < entry.block_extent.block_end);
 130         /* The new entry occludes the beginning of the old entry */
 131         BlockExtent adjusted_extent(map_entry.block_extent.block_end,
 132                                     entry.block_extent.block_end);
 133         adjust_map_entry_locked(entry, adjusted_extent);
 134       }
 135     } else {
 136       if (map_entry.block_extent.block_end >= entry.block_extent.block_end) {
 137         /* The new entry occludes the end of the old entry */
 138         BlockExtent adjusted_extent(entry.block_extent.block_start,
 139                                     map_entry.block_extent.block_start);
 140         adjust_map_entry_locked(entry, adjusted_extent);
 141       } else {
 142         /* The new entry splits the old entry */
 143         split_map_entry_locked(entry, map_entry.block_extent);
 144       }
 145     }
 146   }
 147   add_map_entry_locked(map_entry);
 148 }
 149
 150 template <typename T>
 151 void LogMap<T>::remove_log_entry_locked(std::shared_ptr<T> log_entry) {
 152   ldout(m_cct, 20) << "*log_entry=" << *log_entry << dendl;
 153   ceph_assert(ceph_mutex_is_locked_by_me(m_lock));
 154
 155   LogMapEntries<T> possible_hits = find_map_entries_locked(log_entry->block_extent());
 156   for (auto &possible_hit : possible_hits) {
 157     if (possible_hit.log_entry == log_entry) {
 158       /* This map entry refers to the specified log entry */
 159       remove_map_entry_locked(possible_hit);
 160     }
 161   }
 162 }
 163
 164 template <typename T>
 165 void LogMap<T>::add_map_entry_locked(LogMapEntry<T> &map_entry) {
 166   ceph_assert(map_entry.log_entry);
 167   m_block_to_log_entry_map.insert(map_entry);
 168   map_entry.log_entry->inc_map_ref();
 169 }
 170
 171 template <typename T>
 172 void LogMap<T>::remove_map_entry_locked(LogMapEntry<T> &map_entry) {
 173   auto it = m_block_to_log_entry_map.find(map_entry);
 174   ceph_assert(it != m_block_to_log_entry_map.end());
 175
 176   LogMapEntry<T> erased = *it;
 177   m_block_to_log_entry_map.erase(it);
 178   erased.log_entry->dec_map_ref();
 179   if (0 == erased.log_entry->get_map_ref()) {
 180     ldout(m_cct, 20) << "log entry has zero map entries: " << erased.log_entry << dendl;
 181   }
 182 }
 183
 184 template <typename T>
 185 void LogMap<T>::adjust_map_entry_locked(LogMapEntry<T> &map_entry, BlockExtent &new_extent) {
 186   auto it = m_block_to_log_entry_map.find(map_entry);
 187   ceph_assert(it != m_block_to_log_entry_map.end());
 188
 189   LogMapEntry<T> adjusted = *it;
 190   m_block_to_log_entry_map.erase(it);
 191
 192   m_block_to_log_entry_map.insert(LogMapEntry<T>(new_extent, adjusted.log_entry));
 193 }
 194
 195 template <typename T>
 196 void LogMap<T>::split_map_entry_locked(LogMapEntry<T> &map_entry, BlockExtent &removed_extent) {
 197   auto it = m_block_to_log_entry_map.find(map_entry);
 198   ceph_assert(it != m_block_to_log_entry_map.end());
 199
 200   LogMapEntry<T> split = *it;
 201   m_block_to_log_entry_map.erase(it);
 202
 203   BlockExtent left_extent(split.block_extent.block_start,
 204                           removed_extent.block_start);
 205   m_block_to_log_entry_map.insert(LogMapEntry<T>(left_extent, split.log_entry));
 206
 207   BlockExtent right_extent(removed_extent.block_end,
 208                            split.block_extent.block_end);
 209   m_block_to_log_entry_map.insert(LogMapEntry<T>(right_extent, split.log_entry));
 210
 211   split.log_entry->inc_map_ref();
 212 }
 213
 214 template <typename T>
 215 std::list<std::shared_ptr<T>> LogMap<T>::find_log_entries_locked(const BlockExtent &block_extent) {
 216   std::list<std::shared_ptr<T>> overlaps;
 217   ldout(m_cct, 20) << "block_extent=" << block_extent << dendl;
 218
 219   ceph_assert(ceph_mutex_is_locked_by_me(m_lock));
 220   LogMapEntries<T> map_entries = find_map_entries_locked(block_extent);
 221   for (auto &map_entry : map_entries) {
 222     overlaps.emplace_back(map_entry.log_entry);
 223   }
 224   return overlaps;
 225 }
 226
 227 /**
 228  * TODO: Generalize this to do some arbitrary thing to each map
 229  * extent, instead of returning a list.
 230  */
 231 template <typename T>
 232 LogMapEntries<T> LogMap<T>::find_map_entries_locked(const BlockExtent &block_extent) {
 233   LogMapEntries<T> overlaps;
 234
 235   ldout(m_cct, 20) << "block_extent=" << block_extent << dendl;
 236   ceph_assert(ceph_mutex_is_locked_by_me(m_lock));
 237   auto p = m_block_to_log_entry_map.equal_range(LogMapEntry<T>(block_extent));
 238   ldout(m_cct, 20) << "count=" << std::distance(p.first, p.second) << dendl;
 239   for ( auto i = p.first; i != p.second; ++i ) {
 240     LogMapEntry<T> entry = *i;
 241     overlaps.emplace_back(entry);
 242     ldout(m_cct, 20) << entry << dendl;
 243   }
 244   return overlaps;
 245 }
 246
 247 /* We map block extents to write log entries, or portions of write log
 248  * entries. These are both represented by a WriteLogMapEntry. When a
 249  * GenericWriteLogEntry is added to this map, a WriteLogMapEntry is created to
 250  * represent the entire block extent of the GenericWriteLogEntry, and the
 251  * WriteLogMapEntry is added to the set.
 252  *
 253  * The set must not contain overlapping WriteLogMapEntrys. WriteLogMapEntrys
 254  * in the set that overlap with one being added are adjusted (shrunk, split,
 255  * or removed) before the new entry is added.
 256  *
 257  * This comparison works despite the ambiguity because we ensure the set
 258  * contains no overlapping entries. This comparison works to find entries
 259  * that overlap with a given block extent because equal_range() returns the
 260  * first entry in which the extent doesn't end before the given extent
 261  * starts, and the last entry for which the extent starts before the given
 262  * extent ends (the first entry that the key is less than, and the last entry
 263  * that is less than the key).
 264  */
 265 template <typename T>
 266 bool LogMap<T>::LogMapEntryCompare::operator()(const LogMapEntry<T> &lhs,
 267                                                const LogMapEntry<T> &rhs) const {
 268   if (lhs.block_extent.block_end <= rhs.block_extent.block_start) {
 269     return true;
 270   }
 271   return false;
 272 }
 273
 274 } //namespace pwl
 275 } //namespace cache
 276 } //namespace librbd
 277
 278 template class librbd::cache::pwl::LogMap<librbd::cache::pwl::GenericWriteLogEntry>;