+++ /dev/null
-// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
-// vim: ts=8 sw=2 smarttab
-/*
- * Ceph - scalable distributed file system
- *
- * Copyright (C) 2016 Red Hat
- *
- * This is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License version 2.1, as published by the Free Software
- * Foundation. See file COPYING.
- *
- */
-
-#ifndef EXTENT_CACHE_H
-#define EXTENT_CACHE_H
-
-#include <map>
-#include <list>
-#include <vector>
-#include <utility>
-#include <boost/optional.hpp>
-#include <boost/intrusive/set.hpp>
-#include <boost/intrusive/list.hpp>
-#include "include/interval_set.h"
-#include "common/interval_map.h"
-#include "include/buffer.h"
-#include "common/hobject.h"
-
-/**
- ExtentCache
-
- The main purpose of this cache is to ensure that we can pipeline
- overlapping partial overwrites.
-
- To that end we need to ensure that an extent pinned for an operation is
- live until that operation completes. However, a particular extent
- might be pinned by multiple operations (several pipelined writes
- on the same object).
-
- 1) When we complete an operation, we only look at extents owned only
- by that operation.
- 2) Per-extent overhead is fixed size.
- 2) Per-operation metadata is fixed size.
-
- This is simple enough to realize with two main structures:
- - extent: contains a pointer to the pin owning it and intrusive list
- pointers to other extents owned by the same pin
- - pin_state: contains the list head for extents owned by it
-
- This works as long as we only need to remember one "owner" for
- each extent. To make this work, we'll need to leverage some
- invariants guaranteed by higher layers:
-
- 1) Writes on a particular object must be ordered
- 2) A particular object will have outstanding reads or writes, but not
- both (note that you can have a read while a write is committed, but
- not applied).
-
- Our strategy therefore will be to have whichever in-progress op will
- finish "last" be the owner of a particular extent. For now, we won't
- cache reads, so 2) simply means that we can assume that reads and
- recovery operations imply no unstable extents on the object in
- question.
-
- Write: WaitRead -> WaitCommit -> Complete
-
- Invariant 1) above actually indicates that we can't have writes
- bypassing the WaitRead state while there are writes waiting on
- Reads. Thus, the set of operations pinning a particular extent
- must always complete in order or arrival.
-
- This suggests that a particular extent may be in only the following
- states:
-
-
- 0) Empty (not in the map at all)
- 1) Write Pending N
- - Some write with reqid <= N is currently fetching the data for
- this extent
- - The extent must persist until Write reqid N completes
- - All ops pinning this extent are writes in the WaitRead state of
- the Write pipeline (there must be an in progress write, so no
- reads can be in progress).
- 2) Write Pinned N:
- - This extent has data corresponding to some reqid M <= N
- - The extent must persist until Write reqid N commits
- - All ops pinning this extent are writes in some Write
- state (all are possible). Reads are not possible
- in this state (or the others) due to 2).
-
- All of the above suggests that there are 3 things users can
- ask of the cache corresponding to the 3 Write pipelines
- states.
- */
-
-/// If someone wants these types, but not ExtentCache, move to another file
-struct bl_split_merge {
- bufferlist split(
- uint64_t offset,
- uint64_t length,
- bufferlist &bl) const {
- bufferlist out;
- out.substr_of(bl, offset, length);
- return out;
- }
- bool can_merge(const bufferlist &left, const bufferlist &right) const {
- return true;
- }
- bufferlist merge(bufferlist &&left, bufferlist &&right) const {
- bufferlist bl;
- bl.claim(left);
- bl.claim_append(right);
- return bl;
- }
- uint64_t length(const bufferlist &b) const { return b.length(); }
-};
-using extent_set = interval_set<uint64_t>;
-using extent_map = interval_map<uint64_t, bufferlist, bl_split_merge>;
-
-class ExtentCache {
- struct object_extent_set;
- struct pin_state;
-private:
-
- struct extent {
- object_extent_set *parent_extent_set = nullptr;
- pin_state *parent_pin_state = nullptr;
- boost::intrusive::set_member_hook<> extent_set_member;
- boost::intrusive::list_member_hook<> pin_list_member;
-
- uint64_t offset;
- uint64_t length;
- boost::optional<bufferlist> bl;
-
- uint64_t get_length() const {
- return length;
- }
-
- bool is_pending() const {
- return bl == boost::none;
- }
-
- bool pinned_by_write() const {
- assert(parent_pin_state);
- return parent_pin_state->is_write();
- }
-
- uint64_t pin_tid() const {
- assert(parent_pin_state);
- return parent_pin_state->tid;
- }
-
- extent(uint64_t offset, bufferlist _bl)
- : offset(offset), length(_bl.length()), bl(_bl) {}
-
- extent(uint64_t offset, uint64_t length)
- : offset(offset), length(length) {}
-
- bool operator<(const extent &rhs) const {
- return offset < rhs.offset;
- }
- private:
- // can briefly violate the two link invariant, used in unlink() and move()
- void _link_pin_state(pin_state &pin_state);
- void _unlink_pin_state();
- public:
- void unlink();
- void link(object_extent_set &parent_extent_set, pin_state &pin_state);
- void move(pin_state &to);
- };
-
- struct object_extent_set : boost::intrusive::set_base_hook<> {
- hobject_t oid;
- object_extent_set(const hobject_t &oid) : oid(oid) {}
-
- using set_member_options = boost::intrusive::member_hook<
- extent,
- boost::intrusive::set_member_hook<>,
- &extent::extent_set_member>;
- using set = boost::intrusive::set<extent, set_member_options>;
- set extent_set;
-
- bool operator<(const object_extent_set &rhs) const {
- return oid < rhs.oid;
- }
-
- struct uint_cmp {
- bool operator()(uint64_t lhs, const extent &rhs) const {
- return lhs < rhs.offset;
- }
- bool operator()(const extent &lhs, uint64_t rhs) const {
- return lhs.offset < rhs;
- }
- };
- std::pair<set::iterator, set::iterator> get_containing_range(
- uint64_t offset, uint64_t length);
-
- void erase(uint64_t offset, uint64_t length);
-
- struct update_action {
- enum type {
- NONE,
- UPDATE_PIN
- };
- type action = NONE;
- boost::optional<bufferlist> bl;
- };
- template <typename F>
- void traverse_update(
- pin_state &pin,
- uint64_t offset,
- uint64_t length,
- F &&f) {
- auto range = get_containing_range(offset, length);
-
- if (range.first == range.second || range.first->offset > offset) {
- uint64_t extlen = range.first == range.second ?
- length : range.first->offset - offset;
-
- update_action action;
- f(offset, extlen, nullptr, &action);
- assert(!action.bl || action.bl->length() == extlen);
- if (action.action == update_action::UPDATE_PIN) {
- extent *ext = action.bl ?
- new extent(offset, *action.bl) :
- new extent(offset, extlen);
- ext->link(*this, pin);
- } else {
- assert(!action.bl);
- }
- }
-
- for (auto p = range.first; p != range.second;) {
- extent *ext = &*p;
- ++p;
-
- uint64_t extoff = MAX(ext->offset, offset);
- uint64_t extlen = MIN(
- ext->length - (extoff - ext->offset),
- offset + length - extoff);
-
- update_action action;
- f(extoff, extlen, ext, &action);
- assert(!action.bl || action.bl->length() == extlen);
- extent *final_extent = nullptr;
- if (action.action == update_action::NONE) {
- final_extent = ext;
- } else {
- pin_state *ps = ext->parent_pin_state;
- ext->unlink();
- if ((ext->offset < offset) &&
- (ext->offset + ext->get_length() > offset)) {
- extent *head = nullptr;
- if (ext->bl) {
- bufferlist bl;
- bl.substr_of(
- *(ext->bl),
- 0,
- offset - ext->offset);
- head = new extent(ext->offset, bl);
- } else {
- head = new extent(
- ext->offset, offset - ext->offset);
- }
- head->link(*this, *ps);
- }
- if ((ext->offset + ext->length > offset + length) &&
- (offset + length > ext->offset)) {
- uint64_t nlen =
- (ext->offset + ext->get_length()) - (offset + length);
- extent *tail = nullptr;
- if (ext->bl) {
- bufferlist bl;
- bl.substr_of(
- *(ext->bl),
- ext->get_length() - nlen,
- nlen);
- tail = new extent(offset + length, bl);
- } else {
- tail = new extent(offset + length, nlen);
- }
- tail->link(*this, *ps);
- }
- if (action.action == update_action::UPDATE_PIN) {
- if (ext->bl) {
- bufferlist bl;
- bl.substr_of(
- *(ext->bl),
- extoff - ext->offset,
- extlen);
- final_extent = new ExtentCache::extent(
- extoff,
- bl);
- } else {
- final_extent = new ExtentCache::extent(
- extoff, extlen);
- }
- final_extent->link(*this, pin);
- }
- delete ext;
- }
-
- if (action.bl) {
- assert(final_extent);
- assert(final_extent->length == action.bl->length());
- final_extent->bl = *(action.bl);
- }
-
- uint64_t next_off = p == range.second ?
- offset + length : p->offset;
- if (extoff + extlen < next_off) {
- uint64_t tailoff = extoff + extlen;
- uint64_t taillen = next_off - tailoff;
-
- update_action action;
- f(tailoff, taillen, nullptr, &action);
- assert(!action.bl || action.bl->length() == taillen);
- if (action.action == update_action::UPDATE_PIN) {
- extent *ext = action.bl ?
- new extent(tailoff, *action.bl) :
- new extent(tailoff, taillen);
- ext->link(*this, pin);
- } else {
- assert(!action.bl);
- }
- }
- }
- }
- };
- struct Cmp {
- bool operator()(const hobject_t &oid, const object_extent_set &rhs) const {
- return oid < rhs.oid;
- }
- bool operator()(const object_extent_set &lhs, const hobject_t &oid) const {
- return lhs.oid < oid;
- }
- };
-
- object_extent_set &get_or_create(const hobject_t &oid);
- object_extent_set *get_if_exists(const hobject_t &oid);
-
- void remove_and_destroy_if_empty(object_extent_set &set);
- using cache_set = boost::intrusive::set<object_extent_set>;
- cache_set per_object_caches;
-
- uint64_t next_write_tid = 1;
- uint64_t next_read_tid = 1;
- struct pin_state {
- uint64_t tid = 0;
- enum pin_type_t {
- NONE,
- WRITE,
- };
- pin_type_t pin_type = NONE;
- bool is_write() const { return pin_type == WRITE; }
-
- pin_state(const pin_state &other) = delete;
- pin_state &operator=(const pin_state &other) = delete;
- pin_state(pin_state &&other) = delete;
- pin_state() = default;
-
- using list_member_options = boost::intrusive::member_hook<
- extent,
- boost::intrusive::list_member_hook<>,
- &extent::pin_list_member>;
- using list = boost::intrusive::list<extent, list_member_options>;
- list pin_list;
- ~pin_state() {
- assert(pin_list.empty());
- assert(tid == 0);
- assert(pin_type == NONE);
- }
- void _open(uint64_t in_tid, pin_type_t in_type) {
- assert(pin_type == NONE);
- assert(in_tid > 0);
- tid = in_tid;
- pin_type = in_type;
- }
- };
-
- void release_pin(pin_state &p) {
- for (auto iter = p.pin_list.begin(); iter != p.pin_list.end(); ) {
- unique_ptr<extent> extent(&*iter); // we now own this
- iter++; // unlink will invalidate
- assert(extent->parent_extent_set);
- auto &eset = *(extent->parent_extent_set);
- extent->unlink();
- remove_and_destroy_if_empty(eset);
- }
- p.tid = 0;
- p.pin_type = pin_state::NONE;
- }
-
-public:
- class write_pin : private pin_state {
- friend class ExtentCache;
- private:
- void open(uint64_t in_tid) {
- _open(in_tid, pin_state::WRITE);
- }
- public:
- write_pin() : pin_state() {}
- };
-
- void open_write_pin(write_pin &pin) {
- pin.open(next_write_tid++);
- }
-
- /**
- * Reserves extents required for rmw, and learn
- * which need to be read
- *
- * Pins all extents in to_write. Returns subset of to_read not
- * currently present in the cache. Caller must obtain those
- * extents before calling get_remaining_extents_for_rmw.
- *
- * Transition table:
- * - Empty -> Write Pending pin.reqid
- * - Write Pending N -> Write Pending pin.reqid
- * - Write Pinned N -> Write Pinned pin.reqid
- *
- * @param oid [in] object undergoing rmw
- * @param pin [in,out] pin to use (obtained from create_write_pin)
- * @param to_write [in] extents which will be written
- * @param to_read [in] extents to read prior to write (must be subset
- * of to_write)
- * @return subset of to_read which isn't already present or pending
- */
- extent_set reserve_extents_for_rmw(
- const hobject_t &oid,
- write_pin &pin,
- const extent_set &to_write,
- const extent_set &to_read);
-
- /**
- * Gets extents required for rmw not returned from
- * reserve_extents_for_rmw
- *
- * Requested extents (to_get) must be the set to_read \ the set
- * returned from reserve_extents_for_rmw. No transition table,
- * all extents at this point must be present and already pinned
- * for this pin by reserve_extents_for_rmw.
- *
- * @param oid [in] object
- * @param pin [in,out] pin associated with this IO
- * @param to_get [in] extents to get (see above for restrictions)
- * @return map of buffers from to_get
- */
- extent_map get_remaining_extents_for_rmw(
- const hobject_t &oid,
- write_pin &pin,
- const extent_set &to_get);
-
- /**
- * Updates the cache to reflect the rmw write
- *
- * All presented extents must already have been specified in
- * reserve_extents_for_rmw under to_write.
- *
- * Transition table:
- * - Empty -> invalid, must call reserve_extents_for_rmw first
- * - Write Pending N -> Write Pinned N, update buffer
- * (assert N >= pin.reqid)
- * - Write Pinned N -> Update buffer (assert N >= pin.reqid)
- *
- * @param oid [in] object
- * @param pin [in,out] pin associated with this IO
- * @param extents [in] map of buffers to update
- * @return void
- */
- void present_rmw_update(
- const hobject_t &oid,
- write_pin &pin,
- const extent_map &extents);
-
- /**
- * Release all buffers pinned by pin
- */
- void release_write_pin(
- write_pin &pin) {
- release_pin(pin);
- }
-
- ostream &print(
- ostream &out) const;
-};
-
-ostream &operator<<(ostream &lhs, const ExtentCache &cache);
-
-#endif
Code Review / stor4nfv.git / blobdiff