path: root/src/librbd/cache/pwl/LogMap.cc

// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
// vim: ts=8 sw=2 smarttab

#include "LogMap.h"
#include "include/ceph_assert.h"
#include "librbd/Utils.h"
#include "librbd/cache/pwl/LogEntry.h"

namespace librbd {
namespace cache {
namespace pwl {

#define dout_subsys ceph_subsys_rbd_pwl
#undef dout_prefix
#define dout_prefix *_dout << "librbd::cache::pwl::LogMap: " << this << " " \
                           <<  __func__ << ": "
template <typename T>
std::ostream &operator<<(std::ostream &os,
                         LogMapEntry<T> &e) {
  os << "block_extent=" << e.block_extent
     << ", log_entry=[" << e.log_entry << "]";
  return os;
}

template <typename T>
LogMapEntry<T>::LogMapEntry(const BlockExtent block_extent,
                            std::shared_ptr<T> log_entry)
  : block_extent(block_extent) , log_entry(log_entry) {
}

template <typename T>
LogMapEntry<T>::LogMapEntry(std::shared_ptr<T> log_entry)
  : block_extent(log_entry->block_extent()) , log_entry(log_entry) {
}

template <typename T>
LogMap<T>::LogMap(CephContext *cct)
  : m_cct(cct),
    m_lock(ceph::make_mutex(pwl::unique_lock_name(
           "librbd::cache::pwl::LogMap::m_lock", this))) {
}

/**
 * Add a write log entry to the map. Subsequent queries for blocks
 * within this log entry's extent will find this log entry. Portions
 * of prior write log entries overlapping with this log entry will
 * be replaced in the map by this log entry.
 *
 * The map_entries field of the log entry object will be updated to
 * contain this map entry.
 *
 * The map_entries fields of all log entries overlapping with this
 * entry will be updated to remove the regions that overlap with
 * this.
 */
template <typename T>
void LogMap<T>::add_log_entry(std::shared_ptr<T> log_entry) {
  std::lock_guard locker(m_lock);
  add_log_entry_locked(log_entry);
}

template <typename T>
void LogMap<T>::add_log_entries(std::list<std::shared_ptr<T>> &log_entries) {
  std::lock_guard locker(m_lock);
  ldout(m_cct, 20) << dendl;
  for (auto &log_entry : log_entries) {
    add_log_entry_locked(log_entry);
  }
}

/**
 * Remove any map entries that refer to the supplied write log
 * entry.
 */
template <typename T>
void LogMap<T>::remove_log_entry(std::shared_ptr<T> log_entry) {
  std::lock_guard locker(m_lock);
  remove_log_entry_locked(log_entry);
}

template <typename T>
void LogMap<T>::remove_log_entries(std::list<std::shared_ptr<T>> &log_entries) {
  std::lock_guard locker(m_lock);
  ldout(m_cct, 20) << dendl;
  for (auto &log_entry : log_entries) {
    remove_log_entry_locked(log_entry);
  }
}

/**
 * Returns the list of all write log entries that overlap the specified block
 * extent. This doesn't tell you which portions of these entries overlap the
 * extent, or each other. For that, use find_map_entries(). A log entry may
 * appear in the list more than once, if multiple map entries refer to it
 * (e.g. the middle of that write log entry has been overwritten).
 */
template <typename T>
std::list<std::shared_ptr<T>> LogMap<T>::find_log_entries(BlockExtent block_extent) {
  std::lock_guard locker(m_lock);
  ldout(m_cct, 20) << dendl;
  return find_log_entries_locked(block_extent);
}

/**
 * Returns the list of all write log map entries that overlap the
 * specified block extent.
 */
template <typename T>
LogMapEntries<T> LogMap<T>::find_map_entries(BlockExtent block_extent) {
  std::lock_guard locker(m_lock);
  ldout(m_cct, 20) << dendl;
  return find_map_entries_locked(block_extent);
}

template <typename T>
void LogMap<T>::add_log_entry_locked(std::shared_ptr<T> log_entry) {
  LogMapEntry<T> map_entry(log_entry);
  ldout(m_cct, 20) << "block_extent=" << map_entry.block_extent
                   << dendl;
  ceph_assert(ceph_mutex_is_locked_by_me(m_lock));
  LogMapEntries<T> overlap_entries = find_map_entries_locked(map_entry.block_extent);
  for (auto &entry : overlap_entries) {
    ldout(m_cct, 20) << entry << dendl;
    if (map_entry.block_extent.block_start <= entry.block_extent.block_start) {
      if (map_entry.block_extent.block_end >= entry.block_extent.block_end) {
        ldout(m_cct, 20) << "map entry completely occluded by new log entry" << dendl;
        remove_map_entry_locked(entry);
      } else {
        ceph_assert(map_entry.block_extent.block_end < entry.block_extent.block_end);
        /* The new entry occludes the beginning of the old entry */
        BlockExtent adjusted_extent(map_entry.block_extent.block_end,
                                    entry.block_extent.block_end);
        adjust_map_entry_locked(entry, adjusted_extent);
      }
    } else {
      if (map_entry.block_extent.block_end >= entry.block_extent.block_end) {
        /* The new entry occludes the end of the old entry */
        BlockExtent adjusted_extent(entry.block_extent.block_start,
                                    map_entry.block_extent.block_start);
        adjust_map_entry_locked(entry, adjusted_extent);
      } else {
        /* The new entry splits the old entry */
        split_map_entry_locked(entry, map_entry.block_extent);
      }
    }
  }
  add_map_entry_locked(map_entry);
}

template <typename T>
void LogMap<T>::remove_log_entry_locked(std::shared_ptr<T> log_entry) {
  ldout(m_cct, 20) << "*log_entry=" << *log_entry << dendl;
  ceph_assert(ceph_mutex_is_locked_by_me(m_lock));

  LogMapEntries<T> possible_hits = find_map_entries_locked(log_entry->block_extent());
  for (auto &possible_hit : possible_hits) {
    if (possible_hit.log_entry == log_entry) {
      /* This map entry refers to the specified log entry */
      remove_map_entry_locked(possible_hit);
    }
  }
}

template <typename T>
void LogMap<T>::add_map_entry_locked(LogMapEntry<T> &map_entry) {
  ceph_assert(map_entry.log_entry);
  m_block_to_log_entry_map.insert(map_entry);
  map_entry.log_entry->inc_map_ref();
}

template <typename T>
void LogMap<T>::remove_map_entry_locked(LogMapEntry<T> &map_entry) {
  auto it = m_block_to_log_entry_map.find(map_entry);
  ceph_assert(it != m_block_to_log_entry_map.end());

  LogMapEntry<T> erased = *it;
  m_block_to_log_entry_map.erase(it);
  erased.log_entry->dec_map_ref();
  if (0 == erased.log_entry->get_map_ref()) {
    ldout(m_cct, 20) << "log entry has zero map entries: " << erased.log_entry << dendl;
  }
}

template <typename T>
void LogMap<T>::adjust_map_entry_locked(LogMapEntry<T> &map_entry, BlockExtent &new_extent) {
  auto it = m_block_to_log_entry_map.find(map_entry);
  ceph_assert(it != m_block_to_log_entry_map.end());

  LogMapEntry<T> adjusted = *it;
  m_block_to_log_entry_map.erase(it);

  m_block_to_log_entry_map.insert(LogMapEntry<T>(new_extent, adjusted.log_entry));
}

template <typename T>
void LogMap<T>::split_map_entry_locked(LogMapEntry<T> &map_entry, BlockExtent &removed_extent) {
  auto it = m_block_to_log_entry_map.find(map_entry);
  ceph_assert(it != m_block_to_log_entry_map.end());

  LogMapEntry<T> split = *it;
  m_block_to_log_entry_map.erase(it);

  BlockExtent left_extent(split.block_extent.block_start,
                          removed_extent.block_start);
  m_block_to_log_entry_map.insert(LogMapEntry<T>(left_extent, split.log_entry));

  BlockExtent right_extent(removed_extent.block_end,
                           split.block_extent.block_end);
  m_block_to_log_entry_map.insert(LogMapEntry<T>(right_extent, split.log_entry));

  split.log_entry->inc_map_ref();
}

template <typename T>
std::list<std::shared_ptr<T>> LogMap<T>::find_log_entries_locked(const BlockExtent &block_extent) {
  std::list<std::shared_ptr<T>> overlaps;
  ldout(m_cct, 20) << "block_extent=" << block_extent << dendl;

  ceph_assert(ceph_mutex_is_locked_by_me(m_lock));
  LogMapEntries<T> map_entries = find_map_entries_locked(block_extent);
  for (auto &map_entry : map_entries) {
    overlaps.emplace_back(map_entry.log_entry);
  }
  return overlaps;
}

/**
 * TODO: Generalize this to do some arbitrary thing to each map
 * extent, instead of returning a list.
 */
template <typename T>
LogMapEntries<T> LogMap<T>::find_map_entries_locked(const BlockExtent &block_extent) {
  LogMapEntries<T> overlaps;

  ldout(m_cct, 20) << "block_extent=" << block_extent << dendl;
  ceph_assert(ceph_mutex_is_locked_by_me(m_lock));
  auto p = m_block_to_log_entry_map.equal_range(LogMapEntry<T>(block_extent));
  ldout(m_cct, 20) << "count=" << std::distance(p.first, p.second) << dendl;
  for ( auto i = p.first; i != p.second; ++i ) {
    LogMapEntry<T> entry = *i;
    overlaps.emplace_back(entry);
    ldout(m_cct, 20) << entry << dendl;
  }
  return overlaps;
}

/* We map block extents to write log entries, or portions of write log
 * entries. These are both represented by a WriteLogMapEntry. When a
 * GenericWriteLogEntry is added to this map, a WriteLogMapEntry is created to
 * represent the entire block extent of the GenericWriteLogEntry, and the
 * WriteLogMapEntry is added to the set.
 *
 * The set must not contain overlapping WriteLogMapEntrys. WriteLogMapEntrys
 * in the set that overlap with one being added are adjusted (shrunk, split,
 * or removed) before the new entry is added.
 *
 * This comparison works despite the ambiguity because we ensure the set
 * contains no overlapping entries. This comparison works to find entries
 * that overlap with a given block extent because equal_range() returns the
 * first entry in which the extent doesn't end before the given extent
 * starts, and the last entry for which the extent starts before the given
 * extent ends (the first entry that the key is less than, and the last entry
 * that is less than the key).
 */
template <typename T>
bool LogMap<T>::LogMapEntryCompare::operator()(const LogMapEntry<T> &lhs,
                                               const LogMapEntry<T> &rhs) const {
  if (lhs.block_extent.block_end <= rhs.block_extent.block_start) {
    return true;
  }
  return false;
}

} //namespace pwl
} //namespace cache
} //namespace librbd

template class librbd::cache::pwl::LogMap<librbd::cache::pwl::GenericWriteLogEntry>;