summaryrefslogtreecommitdiffstats
path: root/src/osd/ExtentCache.h
blob: 972228cd077e20a022bc71289e03e47988e2bbbb (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
// -*- 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 <optional>
#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 {
  ceph::buffer::list split(
    uint64_t offset,
    uint64_t length,
    ceph::buffer::list &bl) const {
    ceph::buffer::list out;
    out.substr_of(bl, offset, length);
    return out;
  }
  bool can_merge(const ceph::buffer::list &left, const ceph::buffer::list &right) const {
    return true;
  }
  ceph::buffer::list merge(ceph::buffer::list &&left, ceph::buffer::list &&right) const {
    ceph::buffer::list bl{std::move(left)};
    bl.claim_append(right);
    return bl;
  }
  uint64_t length(const ceph::buffer::list &b) const { return b.length(); }
};
using extent_set = interval_set<uint64_t>;
using extent_map = interval_map<uint64_t, ceph::buffer::list, 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;
    std::optional<ceph::buffer::list> bl;

    uint64_t get_length() const {
      return length;
    }

    bool is_pending() const {
      return bl == std::nullopt;
    }

    bool pinned_by_write() const {
      ceph_assert(parent_pin_state);
      return parent_pin_state->is_write();
    }

    uint64_t pin_tid() const {
      ceph_assert(parent_pin_state);
      return parent_pin_state->tid;
    }

    extent(uint64_t offset, ceph::buffer::list _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;
    explicit 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;
      std::optional<ceph::buffer::list> 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);
	ceph_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 {
	  ceph_assert(!action.bl);
	}
      }

      for (auto p = range.first; p != range.second;) {
	extent *ext = &*p;
	++p;

	uint64_t extoff = std::max(ext->offset, offset);
	uint64_t extlen = std::min(
	  ext->length - (extoff - ext->offset),
	  offset + length - extoff);

	update_action action;
	f(extoff, extlen, ext, &action);
	ceph_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) {
	      ceph::buffer::list 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) {
	      ceph::buffer::list 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) {
	      ceph::buffer::list 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) {
	  ceph_assert(final_extent);
	  ceph_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);
	  ceph_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 {
	    ceph_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() {
      ceph_assert(pin_list.empty());
      ceph_assert(tid == 0);
      ceph_assert(pin_type == NONE);
    }
    void _open(uint64_t in_tid, pin_type_t in_type) {
      ceph_assert(pin_type == NONE);
      ceph_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(); ) {
      std::unique_ptr<extent> extent(&*iter); // we now own this
      iter++; // unlink will invalidate
      ceph_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);
  }

  std::ostream &print(std::ostream &out) const;
};

std::ostream &operator <<(std::ostream &lhs, const ExtentCache &cache);

#endif